string.c

   1 /**********************************************************************
   2
   3   string.c -
   4
   5   $Author$
   6   created at: Mon Aug  9 17:12:58 JST 1993
   7
   8   Copyright (C) 1993-2007 Yukihiro Matsumoto
   9   Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
  10   Copyright (C) 2000  Information-technology Promotion Agency, Japan
  11
  12 **********************************************************************/
  13
  14 #include "ruby/internal/config.h"
  15
  16 #include <ctype.h>
  17 #include <errno.h>
  18 #include <math.h>
  19
  20 #ifdef HAVE_UNISTD_H
  21 # include <unistd.h>
  22 #endif
  23
  24 #include "debug_counter.h"
  25 #include "encindex.h"
  26 #include "id.h"
  27 #include "internal.h"
  28 #include "internal/array.h"
  29 #include "internal/compar.h"
  30 #include "internal/compilers.h"
  31 #include "internal/encoding.h"
  32 #include "internal/error.h"
  33 #include "internal/gc.h"
  34 #include "internal/numeric.h"
  35 #include "internal/object.h"
  36 #include "internal/proc.h"
  37 #include "internal/re.h"
  38 #include "internal/sanitizers.h"
  39 #include "internal/string.h"
  40 #include "internal/transcode.h"
  41 #include "probes.h"
  42 #include "ruby/encoding.h"
  43 #include "ruby/re.h"
  44 #include "ruby/util.h"
  45 #include "ruby_assert.h"
  46 #include "vm_sync.h"
  47
  48 #if defined HAVE_CRYPT_R
  49 # if defined HAVE_CRYPT_H
  50 #  include <crypt.h>
  51 # endif
  52 #elif !defined HAVE_CRYPT
  53 # include "missing/crypt.h"
  54 # define HAVE_CRYPT_R 1
  55 #endif
  56
  57 #define BEG(no) (regs->beg[(no)])
  58 #define END(no) (regs->end[(no)])
  59
  60 #undef rb_str_new
  61 #undef rb_usascii_str_new
  62 #undef rb_utf8_str_new
  63 #undef rb_enc_str_new
  64 #undef rb_str_new_cstr
  65 #undef rb_usascii_str_new_cstr
  66 #undef rb_utf8_str_new_cstr
  67 #undef rb_enc_str_new_cstr
  68 #undef rb_external_str_new_cstr
  69 #undef rb_locale_str_new_cstr
  70 #undef rb_str_dup_frozen
  71 #undef rb_str_buf_new_cstr
  72 #undef rb_str_buf_cat
  73 #undef rb_str_buf_cat2
  74 #undef rb_str_cat2
  75 #undef rb_str_cat_cstr
  76 #undef rb_fstring_cstr
  77
  78 VALUE rb_cString;
  79 VALUE rb_cSymbol;
  80
  81 /* Flags of RString
  82  *
  83  * 1:     RSTRING_NOEMBED
  84  *            The string is not embedded. When a string is embedded, the contents
  85  *            follow the header. When a string is not embedded, the contents is
  86  *            on a separately allocated buffer.
  87  * 2:     STR_SHARED (equal to ELTS_SHARED)
  88  *            The string is shared. The buffer this string points to is owned by
  89  *            another string (the shared root).
  90  * 5:     STR_SHARED_ROOT
  91  *            Other strings may point to the contents of this string. When this
  92  *            flag is set, STR_SHARED must not be set.
  93  * 6:     STR_BORROWED
  94  *            When RSTRING_NOEMBED is set and klass is 0, this string is unsafe
  95  *            to be unshared by rb_str_tmp_frozen_release.
  96  * 7:     STR_TMPLOCK
  97  *            The pointer to the buffer is passed to a system call such as
  98  *            read(2). Any modification and realloc is prohibited.
  99  * 8-9:   ENC_CODERANGE
 100  *            Stores the coderange of the string.
 101  * 10-16: ENCODING
 102  *            Stores the encoding of the string.
 103  * 17:    RSTRING_FSTR
 104  *            The string is a fstring. The string is deduplicated in the fstring
 105  *            table.
 106  * 18:    STR_NOFREE
 107  *            Do not free this string's buffer when the string is reclaimed
 108  *            by the garbage collector. Used for when the string buffer is a C
 109  *            string literal.
 110  * 19:    STR_FAKESTR
 111  *            The string is not allocated or managed by the garbage collector.
 112  *            Typically, the string object header (struct RString) is temporarily
 113  *            allocated on C stack.
 114  */
 115
 116 #define RUBY_MAX_CHAR_LEN 16
 117 #define STR_SHARED_ROOT FL_USER5
 118 #define STR_BORROWED FL_USER6
 119 #define STR_TMPLOCK FL_USER7
 120 #define STR_NOFREE FL_USER18
 121 #define STR_FAKESTR FL_USER19
 122
 123 #define STR_SET_NOEMBED(str) do {\
 124     FL_SET((str), STR_NOEMBED);\
 125     FL_UNSET((str), STR_SHARED | STR_SHARED_ROOT | STR_BORROWED);\
 126 } while (0)
 127 #define STR_SET_EMBED(str) FL_UNSET((str), STR_NOEMBED | STR_SHARED | STR_NOFREE)
 128
 129 #define STR_SET_LEN(str, n) do { \
 130     RSTRING(str)->len = (n); \
 131 } while (0)
 132
 133 static inline bool
 134 str_enc_fastpath(VALUE str)
 135 {
 136     // The overwhelming majority of strings are in one of these 3 encodings.
 137     switch (ENCODING_GET_INLINED(str)) {
 138       case ENCINDEX_ASCII_8BIT:
 139       case ENCINDEX_UTF_8:
 140       case ENCINDEX_US_ASCII:
 141         return true;
 142       default:
 143         return false;
 144     }
 145 }
 146
 147 #define TERM_LEN(str) (str_enc_fastpath(str) ? 1 : rb_enc_mbminlen(rb_enc_from_index(ENCODING_GET(str))))
 148 #define TERM_FILL(ptr, termlen) do {\
 149     char *const term_fill_ptr = (ptr);\
 150     const int term_fill_len = (termlen);\
 151     *term_fill_ptr = '\0';\
 152     if (UNLIKELY(term_fill_len > 1))\
 153         memset(term_fill_ptr, 0, term_fill_len);\
 154 } while (0)
 155
 156 #define RESIZE_CAPA(str,capacity) do {\
 157     const int termlen = TERM_LEN(str);\
 158     RESIZE_CAPA_TERM(str,capacity,termlen);\
 159 } while (0)
 160 #define RESIZE_CAPA_TERM(str,capacity,termlen) do {\
 161     if (STR_EMBED_P(str)) {\
 162         if (str_embed_capa(str) < capacity + termlen) {\
 163             char *const tmp = ALLOC_N(char, (size_t)(capacity) + (termlen));\
 164             const long tlen = RSTRING_LEN(str);\
 165             memcpy(tmp, RSTRING_PTR(str), tlen);\
 166             RSTRING(str)->as.heap.ptr = tmp;\
 167             RSTRING(str)->len = tlen;\
 168             STR_SET_NOEMBED(str);\
 169             RSTRING(str)->as.heap.aux.capa = (capacity);\
 170         }\
 171     }\
 172     else {\
 173         RUBY_ASSERT(!FL_TEST((str), STR_SHARED)); \
 174         SIZED_REALLOC_N(RSTRING(str)->as.heap.ptr, char, \
 175                         (size_t)(capacity) + (termlen), STR_HEAP_SIZE(str)); \
 176         RSTRING(str)->as.heap.aux.capa = (capacity);\
 177     }\
 178 } while (0)
 179
 180 #define STR_SET_SHARED(str, shared_str) do { \
 181     if (!FL_TEST(str, STR_FAKESTR)) { \
 182         RUBY_ASSERT(RSTRING_PTR(shared_str) <= RSTRING_PTR(str)); \
 183         RUBY_ASSERT(RSTRING_PTR(str) <= RSTRING_PTR(shared_str) + RSTRING_LEN(shared_str)); \
 184         RB_OBJ_WRITE((str), &RSTRING(str)->as.heap.aux.shared, (shared_str)); \
 185         FL_SET((str), STR_SHARED); \
 186         FL_SET((shared_str), STR_SHARED_ROOT); \
 187         if (RBASIC_CLASS((shared_str)) == 0) /* for CoW-friendliness */ \
 188             FL_SET_RAW((shared_str), STR_BORROWED); \
 189     } \
 190 } while (0)
 191
 192 #define STR_HEAP_PTR(str)  (RSTRING(str)->as.heap.ptr)
 193 #define STR_HEAP_SIZE(str) ((size_t)RSTRING(str)->as.heap.aux.capa + TERM_LEN(str))
 194 /* TODO: include the terminator size in capa. */
 195
 196 #define STR_ENC_GET(str) get_encoding(str)
 197
 198 #if !defined SHARABLE_MIDDLE_SUBSTRING
 199 # define SHARABLE_MIDDLE_SUBSTRING 0
 200 #endif
 201 #if !SHARABLE_MIDDLE_SUBSTRING
 202 #define SHARABLE_SUBSTRING_P(beg, len, end) ((beg) + (len) == (end))
 203 #else
 204 #define SHARABLE_SUBSTRING_P(beg, len, end) 1
 205 #endif
 206
 207
 208 static inline long
 209 str_embed_capa(VALUE str)
 210 {
 211     return rb_gc_obj_slot_size(str) - offsetof(struct RString, as.embed.ary);
 212 }
 213
 214 bool
 215 rb_str_reembeddable_p(VALUE str)
 216 {
 217     return !FL_TEST(str, STR_NOFREE|STR_SHARED_ROOT|STR_SHARED);
 218 }
 219
 220 static inline size_t
 221 rb_str_embed_size(long capa)
 222 {
 223     return offsetof(struct RString, as.embed.ary) + capa;
 224 }
 225
 226 size_t
 227 rb_str_size_as_embedded(VALUE str)
 228 {
 229     size_t real_size;
 230     if (STR_EMBED_P(str)) {
 231         real_size = rb_str_embed_size(RSTRING(str)->len) + TERM_LEN(str);
 232     }
 233     /* if the string is not currently embedded, but it can be embedded, how
 234      * much space would it require */
 235     else if (rb_str_reembeddable_p(str)) {
 236         real_size = rb_str_embed_size(RSTRING(str)->as.heap.aux.capa) + TERM_LEN(str);
 237     }
 238     else {
 239         real_size = sizeof(struct RString);
 240     }
 241     return real_size;
 242 }
 243
 244 static inline bool
 245 STR_EMBEDDABLE_P(long len, long termlen)
 246 {
 247     return rb_gc_size_allocatable_p(rb_str_embed_size(len + termlen));
 248 }
 249
 250 static VALUE str_replace_shared_without_enc(VALUE str2, VALUE str);
 251 static VALUE str_new_frozen(VALUE klass, VALUE orig);
 252 static VALUE str_new_frozen_buffer(VALUE klass, VALUE orig, int copy_encoding);
 253 static VALUE str_new_static(VALUE klass, const char *ptr, long len, int encindex);
 254 static VALUE str_new(VALUE klass, const char *ptr, long len);
 255 static void str_make_independent_expand(VALUE str, long len, long expand, const int termlen);
 256 static inline void str_modifiable(VALUE str);
 257 static VALUE rb_str_downcase(int argc, VALUE *argv, VALUE str);
 258
 259 static inline void
 260 str_make_independent(VALUE str)
 261 {
 262     long len = RSTRING_LEN(str);
 263     int termlen = TERM_LEN(str);
 264     str_make_independent_expand((str), len, 0L, termlen);
 265 }
 266
 267 static inline int str_dependent_p(VALUE str);
 268
 269 void
 270 rb_str_make_independent(VALUE str)
 271 {
 272     if (str_dependent_p(str)) {
 273         str_make_independent(str);
 274     }
 275 }
 276
 277 void
 278 rb_str_make_embedded(VALUE str)
 279 {
 280     RUBY_ASSERT(rb_str_reembeddable_p(str));
 281     RUBY_ASSERT(!STR_EMBED_P(str));
 282
 283     char *buf = RSTRING(str)->as.heap.ptr;
 284     long len = RSTRING(str)->len;
 285
 286     STR_SET_EMBED(str);
 287     STR_SET_LEN(str, len);
 288
 289     if (len > 0) {
 290         memcpy(RSTRING_PTR(str), buf, len);
 291         ruby_xfree(buf);
 292     }
 293
 294     TERM_FILL(RSTRING(str)->as.embed.ary + len, TERM_LEN(str));
 295 }
 296
 297 void
 298 rb_debug_rstring_null_ptr(const char *func)
 299 {
 300     fprintf(stderr, "%s is returning NULL!! "
 301             "SIGSEGV is highly expected to follow immediately.\n"
 302             "If you could reproduce, attach your debugger here, "
 303             "and look at the passed string.\n",
 304             func);
 305 }
 306
 307 /* symbols for [up|down|swap]case/capitalize options */
 308 static VALUE sym_ascii, sym_turkic, sym_lithuanian, sym_fold;
 309
 310 static rb_encoding *
 311 get_encoding(VALUE str)
 312 {
 313     return rb_enc_from_index(ENCODING_GET(str));
 314 }
 315
 316 static void
 317 mustnot_broken(VALUE str)
 318 {
 319     if (is_broken_string(str)) {
 320         rb_raise(rb_eArgError, "invalid byte sequence in %s", rb_enc_name(STR_ENC_GET(str)));
 321     }
 322 }
 323
 324 static void
 325 mustnot_wchar(VALUE str)
 326 {
 327     rb_encoding *enc = STR_ENC_GET(str);
 328     if (rb_enc_mbminlen(enc) > 1) {
 329         rb_raise(rb_eArgError, "wide char encoding: %s", rb_enc_name(enc));
 330     }
 331 }
 332
 333 static int fstring_cmp(VALUE a, VALUE b);
 334
 335 static VALUE register_fstring(VALUE str, bool copy);
 336
 337 const struct st_hash_type rb_fstring_hash_type = {
 338     fstring_cmp,
 339     rb_str_hash,
 340 };
 341
 342 #define BARE_STRING_P(str) (!FL_ANY_RAW(str, FL_EXIVAR) && RBASIC_CLASS(str) == rb_cString)
 343
 344 struct fstr_update_arg {
 345     VALUE fstr;
 346     bool copy;
 347 };
 348
 349 static int
 350 fstr_update_callback(st_data_t *key, st_data_t *value, st_data_t data, int existing)
 351 {
 352
 353     struct fstr_update_arg *arg = (struct fstr_update_arg *)data;
 354     VALUE str = (VALUE)*key;
 355
 356     if (existing) {
 357         /* because of lazy sweep, str may be unmarked already and swept
 358          * at next time */
 359
 360         if (rb_objspace_garbage_object_p(str)) {
 361             arg->fstr = Qundef;
 362             return ST_DELETE;
 363         }
 364
 365         arg->fstr = str;
 366         return ST_STOP;
 367     }
 368     else {
 369         if (FL_TEST_RAW(str, STR_FAKESTR)) {
 370             if (arg->copy) {
 371                 VALUE new_str = str_new(rb_cString, RSTRING(str)->as.heap.ptr, RSTRING(str)->len);
 372                 rb_enc_copy(new_str, str);
 373                 str = new_str;
 374             }
 375             else {
 376                 str = str_new_static(rb_cString, RSTRING(str)->as.heap.ptr,
 377                                      RSTRING(str)->len,
 378                                      ENCODING_GET(str));
 379             }
 380             OBJ_FREEZE_RAW(str);
 381         }
 382         else {
 383             if (!OBJ_FROZEN(str))
 384                 str = str_new_frozen(rb_cString, str);
 385             if (STR_SHARED_P(str)) { /* str should not be shared */
 386                 /* shared substring  */
 387                 str_make_independent(str);
 388                 RUBY_ASSERT(OBJ_FROZEN(str));
 389             }
 390             if (!BARE_STRING_P(str)) {
 391                 str = str_new_frozen(rb_cString, str);
 392             }
 393         }
 394         RBASIC(str)->flags |= RSTRING_FSTR;
 395
 396         *key = *value = arg->fstr = str;
 397         return ST_CONTINUE;
 398     }
 399 }
 400
 401 RUBY_FUNC_EXPORTED
 402 VALUE
 403 rb_fstring(VALUE str)
 404 {
 405     VALUE fstr;
 406     int bare;
 407
 408     Check_Type(str, T_STRING);
 409
 410     if (FL_TEST(str, RSTRING_FSTR))
 411         return str;
 412
 413     bare = BARE_STRING_P(str);
 414     if (!bare) {
 415         if (STR_EMBED_P(str)) {
 416             OBJ_FREEZE_RAW(str);
 417             return str;
 418         }
 419
 420         if (FL_TEST_RAW(str, STR_SHARED_ROOT | STR_SHARED) == STR_SHARED_ROOT) {
 421             RUBY_ASSERT(OBJ_FROZEN(str));
 422             return str;
 423         }
 424     }
 425
 426     if (!FL_TEST_RAW(str, FL_FREEZE | STR_NOFREE))
 427         rb_str_resize(str, RSTRING_LEN(str));
 428
 429     fstr = register_fstring(str, FALSE);
 430
 431     if (!bare) {
 432         str_replace_shared_without_enc(str, fstr);
 433         OBJ_FREEZE_RAW(str);
 434         return str;
 435     }
 436     return fstr;
 437 }
 438
 439 static VALUE
 440 register_fstring(VALUE str, bool copy)
 441 {
 442     struct fstr_update_arg args;
 443     args.copy = copy;
 444
 445     RB_VM_LOCK_ENTER();
 446     {
 447         st_table *frozen_strings = rb_vm_fstring_table();
 448         do {
 449             args.fstr = str;
 450             st_update(frozen_strings, (st_data_t)str, fstr_update_callback, (st_data_t)&args);
 451         } while (UNDEF_P(args.fstr));
 452     }
 453     RB_VM_LOCK_LEAVE();
 454
 455     RUBY_ASSERT(OBJ_FROZEN(args.fstr));
 456     RUBY_ASSERT(!FL_TEST_RAW(args.fstr, STR_FAKESTR));
 457     RUBY_ASSERT(!FL_TEST_RAW(args.fstr, FL_EXIVAR));
 458     RUBY_ASSERT(RBASIC_CLASS(args.fstr) == rb_cString);
 459
 460     return args.fstr;
 461 }
 462
 463 static VALUE
 464 setup_fake_str(struct RString *fake_str, const char *name, long len, int encidx)
 465 {
 466     fake_str->basic.flags = T_STRING|RSTRING_NOEMBED|STR_NOFREE|STR_FAKESTR;
 467     /* SHARED to be allocated by the callback */
 468
 469     if (!name) {
 470         RUBY_ASSERT_ALWAYS(len == 0);
 471         name = "";
 472     }
 473
 474     ENCODING_SET_INLINED((VALUE)fake_str, encidx);
 475
 476     RBASIC_SET_CLASS_RAW((VALUE)fake_str, rb_cString);
 477     fake_str->len = len;
 478     fake_str->as.heap.ptr = (char *)name;
 479     fake_str->as.heap.aux.capa = len;
 480     return (VALUE)fake_str;
 481 }
 482
 483 /*
 484  * set up a fake string which refers a static string literal.
 485  */
 486 VALUE
 487 rb_setup_fake_str(struct RString *fake_str, const char *name, long len, rb_encoding *enc)
 488 {
 489     return setup_fake_str(fake_str, name, len, rb_enc_to_index(enc));
 490 }
 491
 492 /*
 493  * rb_fstring_new and rb_fstring_cstr family create or lookup a frozen
 494  * shared string which refers a static string literal.  `ptr` must
 495  * point a constant string.
 496  */
 497 VALUE
 498 rb_fstring_new(const char *ptr, long len)
 499 {
 500     struct RString fake_str;
 501     return register_fstring(setup_fake_str(&fake_str, ptr, len, ENCINDEX_US_ASCII), FALSE);
 502 }
 503
 504 VALUE
 505 rb_fstring_enc_new(const char *ptr, long len, rb_encoding *enc)
 506 {
 507     struct RString fake_str;
 508     return register_fstring(rb_setup_fake_str(&fake_str, ptr, len, enc), FALSE);
 509 }
 510
 511 VALUE
 512 rb_fstring_cstr(const char *ptr)
 513 {
 514     return rb_fstring_new(ptr, strlen(ptr));
 515 }
 516
 517 static int
 518 fstring_set_class_i(st_data_t key, st_data_t val, st_data_t arg)
 519 {
 520     RBASIC_SET_CLASS((VALUE)key, (VALUE)arg);
 521     return ST_CONTINUE;
 522 }
 523
 524 static int
 525 fstring_cmp(VALUE a, VALUE b)
 526 {
 527     long alen, blen;
 528     const char *aptr, *bptr;
 529     RSTRING_GETMEM(a, aptr, alen);
 530     RSTRING_GETMEM(b, bptr, blen);
 531     return (alen != blen ||
 532             ENCODING_GET(a) != ENCODING_GET(b) ||
 533             memcmp(aptr, bptr, alen) != 0);
 534 }
 535
 536 static inline int
 537 single_byte_optimizable(VALUE str)
 538 {
 539     rb_encoding *enc;
 540
 541     /* Conservative.  It may be ENC_CODERANGE_UNKNOWN. */
 542     if (ENC_CODERANGE(str) == ENC_CODERANGE_7BIT)
 543         return 1;
 544
 545     enc = STR_ENC_GET(str);
 546     if (rb_enc_mbmaxlen(enc) == 1)
 547         return 1;
 548
 549     /* Conservative.  Possibly single byte.
 550      * "\xa1" in Shift_JIS for example. */
 551     return 0;
 552 }
 553
 554 VALUE rb_fs;
 555
 556 static inline const char *
 557 search_nonascii(const char *p, const char *e)
 558 {
 559     const uintptr_t *s, *t;
 560
 561 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)
 562 # if SIZEOF_UINTPTR_T == 8
 563 #  define NONASCII_MASK UINT64_C(0x8080808080808080)
 564 # elif SIZEOF_UINTPTR_T == 4
 565 #  define NONASCII_MASK UINT32_C(0x80808080)
 566 # else
 567 #  error "don't know what to do."
 568 # endif
 569 #else
 570 # if SIZEOF_UINTPTR_T == 8
 571 #  define NONASCII_MASK ((uintptr_t)0x80808080UL << 32 | (uintptr_t)0x80808080UL)
 572 # elif SIZEOF_UINTPTR_T == 4
 573 #  define NONASCII_MASK 0x80808080UL /* or...? */
 574 # else
 575 #  error "don't know what to do."
 576 # endif
 577 #endif
 578
 579     if (UNALIGNED_WORD_ACCESS || e - p >= SIZEOF_VOIDP) {
 580 #if !UNALIGNED_WORD_ACCESS
 581         if ((uintptr_t)p % SIZEOF_VOIDP) {
 582             int l = SIZEOF_VOIDP - (uintptr_t)p % SIZEOF_VOIDP;
 583             p += l;
 584             switch (l) {
 585               default: UNREACHABLE;
 586 #if SIZEOF_VOIDP > 4
 587               case 7: if (p[-7]&0x80) return p-7;
 588               case 6: if (p[-6]&0x80) return p-6;
 589               case 5: if (p[-5]&0x80) return p-5;
 590               case 4: if (p[-4]&0x80) return p-4;
 591 #endif
 592               case 3: if (p[-3]&0x80) return p-3;
 593               case 2: if (p[-2]&0x80) return p-2;
 594               case 1: if (p[-1]&0x80) return p-1;
 595               case 0: break;
 596             }
 597         }
 598 #endif
 599 #if defined(HAVE_BUILTIN___BUILTIN_ASSUME_ALIGNED) &&! UNALIGNED_WORD_ACCESS
 600 #define aligned_ptr(value) \
 601         __builtin_assume_aligned((value), sizeof(uintptr_t))
 602 #else
 603 #define aligned_ptr(value) (uintptr_t *)(value)
 604 #endif
 605         s = aligned_ptr(p);
 606         t = (uintptr_t *)(e - (SIZEOF_VOIDP-1));
 607 #undef aligned_ptr
 608         for (;s < t; s++) {
 609             if (*s & NONASCII_MASK) {
 610 #ifdef WORDS_BIGENDIAN
 611                 return (const char *)s + (nlz_intptr(*s&NONASCII_MASK)>>3);
 612 #else
 613                 return (const char *)s + (ntz_intptr(*s&NONASCII_MASK)>>3);
 614 #endif
 615             }
 616         }
 617         p = (const char *)s;
 618     }
 619
 620     switch (e - p) {
 621       default: UNREACHABLE;
 622 #if SIZEOF_VOIDP > 4
 623       case 7: if (e[-7]&0x80) return e-7;
 624       case 6: if (e[-6]&0x80) return e-6;
 625       case 5: if (e[-5]&0x80) return e-5;
 626       case 4: if (e[-4]&0x80) return e-4;
 627 #endif
 628       case 3: if (e[-3]&0x80) return e-3;
 629       case 2: if (e[-2]&0x80) return e-2;
 630       case 1: if (e[-1]&0x80) return e-1;
 631       case 0: return NULL;
 632     }
 633 }
 634
 635 static int
 636 coderange_scan(const char *p, long len, rb_encoding *enc)
 637 {
 638     const char *e = p + len;
 639
 640     if (rb_enc_to_index(enc) == rb_ascii8bit_encindex()) {
 641         /* enc is ASCII-8BIT.  ASCII-8BIT string never be broken. */
 642         p = search_nonascii(p, e);
 643         return p ? ENC_CODERANGE_VALID : ENC_CODERANGE_7BIT;
 644     }
 645
 646     if (rb_enc_asciicompat(enc)) {
 647         p = search_nonascii(p, e);
 648         if (!p) return ENC_CODERANGE_7BIT;
 649         for (;;) {
 650             int ret = rb_enc_precise_mbclen(p, e, enc);
 651             if (!MBCLEN_CHARFOUND_P(ret)) return ENC_CODERANGE_BROKEN;
 652             p += MBCLEN_CHARFOUND_LEN(ret);
 653             if (p == e) break;
 654             p = search_nonascii(p, e);
 655             if (!p) break;
 656         }
 657     }
 658     else {
 659         while (p < e) {
 660             int ret = rb_enc_precise_mbclen(p, e, enc);
 661             if (!MBCLEN_CHARFOUND_P(ret)) return ENC_CODERANGE_BROKEN;
 662             p += MBCLEN_CHARFOUND_LEN(ret);
 663         }
 664     }
 665     return ENC_CODERANGE_VALID;
 666 }
 667
 668 long
 669 rb_str_coderange_scan_restartable(const char *s, const char *e, rb_encoding *enc, int *cr)
 670 {
 671     const char *p = s;
 672
 673     if (*cr == ENC_CODERANGE_BROKEN)
 674         return e - s;
 675
 676     if (rb_enc_to_index(enc) == rb_ascii8bit_encindex()) {
 677         /* enc is ASCII-8BIT.  ASCII-8BIT string never be broken. */
 678         if (*cr == ENC_CODERANGE_VALID) return e - s;
 679         p = search_nonascii(p, e);
 680         *cr = p ? ENC_CODERANGE_VALID : ENC_CODERANGE_7BIT;
 681         return e - s;
 682     }
 683     else if (rb_enc_asciicompat(enc)) {
 684         p = search_nonascii(p, e);
 685         if (!p) {
 686             if (*cr != ENC_CODERANGE_VALID) *cr = ENC_CODERANGE_7BIT;
 687             return e - s;
 688         }
 689         for (;;) {
 690             int ret = rb_enc_precise_mbclen(p, e, enc);
 691             if (!MBCLEN_CHARFOUND_P(ret)) {
 692                 *cr = MBCLEN_INVALID_P(ret) ? ENC_CODERANGE_BROKEN: ENC_CODERANGE_UNKNOWN;
 693                 return p - s;
 694             }
 695             p += MBCLEN_CHARFOUND_LEN(ret);
 696             if (p == e) break;
 697             p = search_nonascii(p, e);
 698             if (!p) break;
 699         }
 700     }
 701     else {
 702         while (p < e) {
 703             int ret = rb_enc_precise_mbclen(p, e, enc);
 704             if (!MBCLEN_CHARFOUND_P(ret)) {
 705                 *cr = MBCLEN_INVALID_P(ret) ? ENC_CODERANGE_BROKEN: ENC_CODERANGE_UNKNOWN;
 706                 return p - s;
 707             }
 708             p += MBCLEN_CHARFOUND_LEN(ret);
 709         }
 710     }
 711     *cr = ENC_CODERANGE_VALID;
 712     return e - s;
 713 }
 714
 715 static inline void
 716 str_enc_copy(VALUE str1, VALUE str2)
 717 {
 718     rb_enc_set_index(str1, ENCODING_GET(str2));
 719 }
 720
 721 /* Like str_enc_copy, but does not check frozen status of str1.
 722  * You should use this only if you're certain that str1 is not frozen. */
 723 static inline void
 724 str_enc_copy_direct(VALUE str1, VALUE str2)
 725 {
 726     int inlined_encoding = RB_ENCODING_GET_INLINED(str2);
 727     if (inlined_encoding == ENCODING_INLINE_MAX) {
 728         rb_enc_set_index(str1, rb_enc_get_index(str2));
 729     }
 730     else {
 731         ENCODING_SET_INLINED(str1, inlined_encoding);
 732     }
 733 }
 734
 735 static void
 736 rb_enc_cr_str_copy_for_substr(VALUE dest, VALUE src)
 737 {
 738     /* this function is designed for copying encoding and coderange
 739      * from src to new string "dest" which is made from the part of src.
 740      */
 741     str_enc_copy(dest, src);
 742     if (RSTRING_LEN(dest) == 0) {
 743         if (!rb_enc_asciicompat(STR_ENC_GET(src)))
 744             ENC_CODERANGE_SET(dest, ENC_CODERANGE_VALID);
 745         else
 746             ENC_CODERANGE_SET(dest, ENC_CODERANGE_7BIT);
 747         return;
 748     }
 749     switch (ENC_CODERANGE(src)) {
 750       case ENC_CODERANGE_7BIT:
 751         ENC_CODERANGE_SET(dest, ENC_CODERANGE_7BIT);
 752         break;
 753       case ENC_CODERANGE_VALID:
 754         if (!rb_enc_asciicompat(STR_ENC_GET(src)) ||
 755             search_nonascii(RSTRING_PTR(dest), RSTRING_END(dest)))
 756             ENC_CODERANGE_SET(dest, ENC_CODERANGE_VALID);
 757         else
 758             ENC_CODERANGE_SET(dest, ENC_CODERANGE_7BIT);
 759         break;
 760       default:
 761         break;
 762     }
 763 }
 764
 765 static void
 766 rb_enc_cr_str_exact_copy(VALUE dest, VALUE src)
 767 {
 768     str_enc_copy(dest, src);
 769     ENC_CODERANGE_SET(dest, ENC_CODERANGE(src));
 770 }
 771
 772 static int
 773 enc_coderange_scan(VALUE str, rb_encoding *enc)
 774 {
 775     return coderange_scan(RSTRING_PTR(str), RSTRING_LEN(str), enc);
 776 }
 777
 778 int
 779 rb_enc_str_coderange_scan(VALUE str, rb_encoding *enc)
 780 {
 781     return enc_coderange_scan(str, enc);
 782 }
 783
 784 int
 785 rb_enc_str_coderange(VALUE str)
 786 {
 787     int cr = ENC_CODERANGE(str);
 788
 789     if (cr == ENC_CODERANGE_UNKNOWN) {
 790         cr = enc_coderange_scan(str, get_encoding(str));
 791         ENC_CODERANGE_SET(str, cr);
 792     }
 793     return cr;
 794 }
 795
 796 int
 797 rb_enc_str_asciionly_p(VALUE str)
 798 {
 799     rb_encoding *enc = STR_ENC_GET(str);
 800
 801     if (!rb_enc_asciicompat(enc))
 802         return FALSE;
 803     else if (is_ascii_string(str))
 804         return TRUE;
 805     return FALSE;
 806 }
 807
 808 static inline void
 809 str_mod_check(VALUE s, const char *p, long len)
 810 {
 811     if (RSTRING_PTR(s) != p || RSTRING_LEN(s) != len){
 812         rb_raise(rb_eRuntimeError, "string modified");
 813     }
 814 }
 815
 816 static size_t
 817 str_capacity(VALUE str, const int termlen)
 818 {
 819     if (STR_EMBED_P(str)) {
 820         return str_embed_capa(str) - termlen;
 821     }
 822     else if (FL_TEST(str, STR_SHARED|STR_NOFREE)) {
 823         return RSTRING(str)->len;
 824     }
 825     else {
 826         return RSTRING(str)->as.heap.aux.capa;
 827     }
 828 }
 829
 830 size_t
 831 rb_str_capacity(VALUE str)
 832 {
 833     return str_capacity(str, TERM_LEN(str));
 834 }
 835
 836 static inline void
 837 must_not_null(const char *ptr)
 838 {
 839     if (!ptr) {
 840         rb_raise(rb_eArgError, "NULL pointer given");
 841     }
 842 }
 843
 844 static inline VALUE
 845 str_alloc_embed(VALUE klass, size_t capa)
 846 {
 847     size_t size = rb_str_embed_size(capa);
 848     RUBY_ASSERT(size > 0);
 849     RUBY_ASSERT(rb_gc_size_allocatable_p(size));
 850
 851     NEWOBJ_OF(str, struct RString, klass,
 852             T_STRING | (RGENGC_WB_PROTECTED_STRING ? FL_WB_PROTECTED : 0), size, 0);
 853
 854     return (VALUE)str;
 855 }
 856
 857 static inline VALUE
 858 str_alloc_heap(VALUE klass)
 859 {
 860     NEWOBJ_OF(str, struct RString, klass,
 861             T_STRING | STR_NOEMBED | (RGENGC_WB_PROTECTED_STRING ? FL_WB_PROTECTED : 0), sizeof(struct RString), 0);
 862
 863     return (VALUE)str;
 864 }
 865
 866 static inline VALUE
 867 empty_str_alloc(VALUE klass)
 868 {
 869     RUBY_DTRACE_CREATE_HOOK(STRING, 0);
 870     VALUE str = str_alloc_embed(klass, 0);
 871     memset(RSTRING(str)->as.embed.ary, 0, str_embed_capa(str));
 872     return str;
 873 }
 874
 875 static VALUE
 876 str_new0(VALUE klass, const char *ptr, long len, int termlen)
 877 {
 878     VALUE str;
 879
 880     if (len < 0) {
 881         rb_raise(rb_eArgError, "negative string size (or size too big)");
 882     }
 883
 884     RUBY_DTRACE_CREATE_HOOK(STRING, len);
 885
 886     if (STR_EMBEDDABLE_P(len, termlen)) {
 887         str = str_alloc_embed(klass, len + termlen);
 888         if (len == 0) {
 889             ENC_CODERANGE_SET(str, ENC_CODERANGE_7BIT);
 890         }
 891     }
 892     else {
 893         str = str_alloc_heap(klass);
 894         RSTRING(str)->as.heap.aux.capa = len;
 895         /* :FIXME: @shyouhei guesses `len + termlen` is guaranteed to never
 896          * integer overflow.  If we can STATIC_ASSERT that, the following
 897          * mul_add_mul can be reverted to a simple ALLOC_N. */
 898         RSTRING(str)->as.heap.ptr =
 899             rb_xmalloc_mul_add_mul(sizeof(char), len, sizeof(char), termlen);
 900     }
 901     if (ptr) {
 902         memcpy(RSTRING_PTR(str), ptr, len);
 903     }
 904     STR_SET_LEN(str, len);
 905     TERM_FILL(RSTRING_PTR(str) + len, termlen);
 906     return str;
 907 }
 908
 909 static VALUE
 910 str_new(VALUE klass, const char *ptr, long len)
 911 {
 912     return str_new0(klass, ptr, len, 1);
 913 }
 914
 915 VALUE
 916 rb_str_new(const char *ptr, long len)
 917 {
 918     return str_new(rb_cString, ptr, len);
 919 }
 920
 921 VALUE
 922 rb_usascii_str_new(const char *ptr, long len)
 923 {
 924     VALUE str = rb_str_new(ptr, len);
 925     ENCODING_CODERANGE_SET(str, rb_usascii_encindex(), ENC_CODERANGE_7BIT);
 926     return str;
 927 }
 928
 929 VALUE
 930 rb_utf8_str_new(const char *ptr, long len)
 931 {
 932     VALUE str = str_new(rb_cString, ptr, len);
 933     rb_enc_associate_index(str, rb_utf8_encindex());
 934     return str;
 935 }
 936
 937 VALUE
 938 rb_enc_str_new(const char *ptr, long len, rb_encoding *enc)
 939 {
 940     VALUE str;
 941
 942     if (!enc) return rb_str_new(ptr, len);
 943
 944     str = str_new0(rb_cString, ptr, len, rb_enc_mbminlen(enc));
 945     rb_enc_associate(str, enc);
 946     return str;
 947 }
 948
 949 VALUE
 950 rb_str_new_cstr(const char *ptr)
 951 {
 952     must_not_null(ptr);
 953     /* rb_str_new_cstr() can take pointer from non-malloc-generated
 954      * memory regions, and that cannot be detected by the MSAN.  Just
 955      * trust the programmer that the argument passed here is a sane C
 956      * string. */
 957     __msan_unpoison_string(ptr);
 958     return rb_str_new(ptr, strlen(ptr));
 959 }
 960
 961 VALUE
 962 rb_usascii_str_new_cstr(const char *ptr)
 963 {
 964     VALUE str = rb_str_new_cstr(ptr);
 965     ENCODING_CODERANGE_SET(str, rb_usascii_encindex(), ENC_CODERANGE_7BIT);
 966     return str;
 967 }
 968
 969 VALUE
 970 rb_utf8_str_new_cstr(const char *ptr)
 971 {
 972     VALUE str = rb_str_new_cstr(ptr);
 973     rb_enc_associate_index(str, rb_utf8_encindex());
 974     return str;
 975 }
 976
 977 VALUE
 978 rb_enc_str_new_cstr(const char *ptr, rb_encoding *enc)
 979 {
 980     must_not_null(ptr);
 981     if (rb_enc_mbminlen(enc) != 1) {
 982         rb_raise(rb_eArgError, "wchar encoding given");
 983     }
 984     return rb_enc_str_new(ptr, strlen(ptr), enc);
 985 }
 986
 987 static VALUE
 988 str_new_static(VALUE klass, const char *ptr, long len, int encindex)
 989 {
 990     VALUE str;
 991
 992     if (len < 0) {
 993         rb_raise(rb_eArgError, "negative string size (or size too big)");
 994     }
 995
 996     if (!ptr) {
 997         rb_encoding *enc = rb_enc_get_from_index(encindex);
 998         str = str_new0(klass, ptr, len, rb_enc_mbminlen(enc));
 999     }
1000     else {
1001         RUBY_DTRACE_CREATE_HOOK(STRING, len);
1002         str = str_alloc_heap(klass);
1003         RSTRING(str)->len = len;
1004         RSTRING(str)->as.heap.ptr = (char *)ptr;
1005         RSTRING(str)->as.heap.aux.capa = len;
1006         RBASIC(str)->flags |= STR_NOFREE;
1007     }
1008     rb_enc_associate_index(str, encindex);
1009     return str;
1010 }
1011
1012 VALUE
1013 rb_str_new_static(const char *ptr, long len)
1014 {
1015     return str_new_static(rb_cString, ptr, len, 0);
1016 }
1017
1018 VALUE
1019 rb_usascii_str_new_static(const char *ptr, long len)
1020 {
1021     return str_new_static(rb_cString, ptr, len, ENCINDEX_US_ASCII);
1022 }
1023
1024 VALUE
1025 rb_utf8_str_new_static(const char *ptr, long len)
1026 {
1027     return str_new_static(rb_cString, ptr, len, ENCINDEX_UTF_8);
1028 }
1029
1030 VALUE
1031 rb_enc_str_new_static(const char *ptr, long len, rb_encoding *enc)
1032 {
1033     return str_new_static(rb_cString, ptr, len, rb_enc_to_index(enc));
1034 }
1035
1036 static VALUE str_cat_conv_enc_opts(VALUE newstr, long ofs, const char *ptr, long len,
1037                                    rb_encoding *from, rb_encoding *to,
1038                                    int ecflags, VALUE ecopts);
1039
1040 static inline bool
1041 is_enc_ascii_string(VALUE str, rb_encoding *enc)
1042 {
1043     int encidx = rb_enc_to_index(enc);
1044     if (rb_enc_get_index(str) == encidx)
1045         return is_ascii_string(str);
1046     return enc_coderange_scan(str, enc) == ENC_CODERANGE_7BIT;
1047 }
1048
1049 VALUE
1050 rb_str_conv_enc_opts(VALUE str, rb_encoding *from, rb_encoding *to, int ecflags, VALUE ecopts)
1051 {
1052     long len;
1053     const char *ptr;
1054     VALUE newstr;
1055
1056     if (!to) return str;
1057     if (!from) from = rb_enc_get(str);
1058     if (from == to) return str;
1059     if ((rb_enc_asciicompat(to) && is_enc_ascii_string(str, from)) ||
1060         rb_is_ascii8bit_enc(to)) {
1061         if (STR_ENC_GET(str) != to) {
1062             str = rb_str_dup(str);
1063             rb_enc_associate(str, to);
1064         }
1065         return str;
1066     }
1067
1068     RSTRING_GETMEM(str, ptr, len);
1069     newstr = str_cat_conv_enc_opts(rb_str_buf_new(len), 0, ptr, len,
1070                                    from, to, ecflags, ecopts);
1071     if (NIL_P(newstr)) {
1072         /* some error, return original */
1073         return str;
1074     }
1075     return newstr;
1076 }
1077
1078 VALUE
1079 rb_str_cat_conv_enc_opts(VALUE newstr, long ofs, const char *ptr, long len,
1080                          rb_encoding *from, int ecflags, VALUE ecopts)
1081 {
1082     long olen;
1083
1084     olen = RSTRING_LEN(newstr);
1085     if (ofs < -olen || olen < ofs)
1086         rb_raise(rb_eIndexError, "index %ld out of string", ofs);
1087     if (ofs < 0) ofs += olen;
1088     if (!from) {
1089         STR_SET_LEN(newstr, ofs);
1090         return rb_str_cat(newstr, ptr, len);
1091     }
1092
1093     rb_str_modify(newstr);
1094     return str_cat_conv_enc_opts(newstr, ofs, ptr, len, from,
1095                                  rb_enc_get(newstr),
1096                                  ecflags, ecopts);
1097 }
1098
1099 VALUE
1100 rb_str_initialize(VALUE str, const char *ptr, long len, rb_encoding *enc)
1101 {
1102     STR_SET_LEN(str, 0);
1103     rb_enc_associate(str, enc);
1104     rb_str_cat(str, ptr, len);
1105     return str;
1106 }
1107
1108 static VALUE
1109 str_cat_conv_enc_opts(VALUE newstr, long ofs, const char *ptr, long len,
1110                       rb_encoding *from, rb_encoding *to,
1111                       int ecflags, VALUE ecopts)
1112 {
1113     rb_econv_t *ec;
1114     rb_econv_result_t ret;
1115     long olen;
1116     VALUE econv_wrapper;
1117     const unsigned char *start, *sp;
1118     unsigned char *dest, *dp;
1119     size_t converted_output = (size_t)ofs;
1120
1121     olen = rb_str_capacity(newstr);
1122
1123     econv_wrapper = rb_obj_alloc(rb_cEncodingConverter);
1124     RBASIC_CLEAR_CLASS(econv_wrapper);
1125     ec = rb_econv_open_opts(from->name, to->name, ecflags, ecopts);
1126     if (!ec) return Qnil;
1127     DATA_PTR(econv_wrapper) = ec;
1128
1129     sp = (unsigned char*)ptr;
1130     start = sp;
1131     while ((dest = (unsigned char*)RSTRING_PTR(newstr)),
1132            (dp = dest + converted_output),
1133            (ret = rb_econv_convert(ec, &sp, start + len, &dp, dest + olen, 0)),
1134            ret == econv_destination_buffer_full) {
1135         /* destination buffer short */
1136         size_t converted_input = sp - start;
1137         size_t rest = len - converted_input;
1138         converted_output = dp - dest;
1139         rb_str_set_len(newstr, converted_output);
1140         if (converted_input && converted_output &&
1141             rest < (LONG_MAX / converted_output)) {
1142             rest = (rest * converted_output) / converted_input;
1143         }
1144         else {
1145             rest = olen;
1146         }
1147         olen += rest < 2 ? 2 : rest;
1148         rb_str_resize(newstr, olen);
1149     }
1150     DATA_PTR(econv_wrapper) = 0;
1151     rb_econv_close(ec);
1152     switch (ret) {
1153       case econv_finished:
1154         len = dp - (unsigned char*)RSTRING_PTR(newstr);
1155         rb_str_set_len(newstr, len);
1156         rb_enc_associate(newstr, to);
1157         return newstr;
1158
1159       default:
1160         return Qnil;
1161     }
1162 }
1163
1164 VALUE
1165 rb_str_conv_enc(VALUE str, rb_encoding *from, rb_encoding *to)