third-party/mruby/mrbgems/mruby-string-ext/src/string.c

   1 #include <string.h>
   2 #include <mruby.h>
   3 #include <mruby/array.h>
   4 #include <mruby/class.h>
   5 #include <mruby/string.h>
   6 #include <mruby/range.h>
   7
   8 static mrb_value
   9 mrb_str_getbyte(mrb_state *mrb, mrb_value str)
  10 {
  11   mrb_int pos;
  12   mrb_get_args(mrb, "i", &pos);
  13
  14   if (pos < 0)
  15     pos += RSTRING_LEN(str);
  16   if (pos < 0 ||  RSTRING_LEN(str) <= pos)
  17     return mrb_nil_value();
  18
  19   return mrb_fixnum_value((unsigned char)RSTRING_PTR(str)[pos]);
  20 }
  21
  22 static mrb_value
  23 mrb_str_setbyte(mrb_state *mrb, mrb_value str)
  24 {
  25   mrb_int pos, byte;
  26   mrb_int len;
  27
  28   mrb_get_args(mrb, "ii", &pos, &byte);
  29
  30   len = RSTRING_LEN(str);
  31   if (pos < -len || len <= pos)
  32     mrb_raisef(mrb, E_INDEX_ERROR, "index %S is out of array", mrb_fixnum_value(pos));
  33   if (pos < 0)
  34     pos += len;
  35
  36   mrb_str_modify(mrb, mrb_str_ptr(str));
  37   byte &= 0xff;
  38   RSTRING_PTR(str)[pos] = (unsigned char)byte;
  39   return mrb_fixnum_value((unsigned char)byte);
  40 }
  41
  42 static mrb_value
  43 mrb_str_byteslice(mrb_state *mrb, mrb_value str)
  44 {
  45   mrb_value a1;
  46   mrb_int len;
  47
  48   if (mrb_get_argc(mrb) == 2) {
  49     mrb_int pos;
  50     mrb_get_args(mrb, "ii", &pos, &len);
  51     return mrb_str_substr(mrb, str, pos, len);
  52   }
  53   mrb_get_args(mrb, "o|i", &a1, &len);
  54   switch (mrb_type(a1)) {
  55   case MRB_TT_RANGE:
  56     {
  57       mrb_int beg;
  58
  59       len = RSTRING_LEN(str);
  60       switch (mrb_range_beg_len(mrb, a1, &beg, &len, len, TRUE)) {
  61       case 0:                   /* not range */
  62         break;
  63       case 1:                   /* range */
  64         return mrb_str_substr(mrb, str, beg, len);
  65       case 2:                   /* out of range */
  66         mrb_raisef(mrb, E_RANGE_ERROR, "%S out of range", a1);
  67         break;
  68       }
  69       return mrb_nil_value();
  70     }
  71 #ifndef MRB_WITHOUT_FLOAT
  72   case MRB_TT_FLOAT:
  73     a1 = mrb_fixnum_value((mrb_int)mrb_float(a1));
  74     /* fall through */
  75 #endif
  76   case MRB_TT_FIXNUM:
  77     return mrb_str_substr(mrb, str, mrb_fixnum(a1), 1);
  78   default:
  79     mrb_raise(mrb, E_TYPE_ERROR, "wrong type of argument");
  80   }
  81   /* not reached */
  82   return mrb_nil_value();
  83 }
  84
  85 /*
  86  *  call-seq:
  87  *     str.swapcase!   -> str or nil
  88  *
  89  *  Equivalent to <code>String#swapcase</code>, but modifies the receiver in
  90  *  place, returning <i>str</i>, or <code>nil</code> if no changes were made.
  91  *  Note: case conversion is effective only in ASCII region.
  92  */
  93 static mrb_value
  94 mrb_str_swapcase_bang(mrb_state *mrb, mrb_value str)
  95 {
  96   char *p, *pend;
  97   int modify = 0;
  98   struct RString *s = mrb_str_ptr(str);
  99
 100   mrb_str_modify(mrb, s);
 101   p = RSTRING_PTR(str);
 102   pend = p + RSTRING_LEN(str);
 103   while (p < pend) {
 104     if (ISUPPER(*p)) {
 105       *p = TOLOWER(*p);
 106       modify = 1;
 107     }
 108     else if (ISLOWER(*p)) {
 109       *p = TOUPPER(*p);
 110       modify = 1;
 111     }
 112     p++;
 113   }
 114
 115   if (modify) return str;
 116   return mrb_nil_value();
 117 }
 118
 119 /*
 120  *  call-seq:
 121  *     str.swapcase   -> new_str
 122  *
 123  *  Returns a copy of <i>str</i> with uppercase alphabetic characters converted
 124  *  to lowercase and lowercase characters converted to uppercase.
 125  *  Note: case conversion is effective only in ASCII region.
 126  *
 127  *     "Hello".swapcase          #=> "hELLO"
 128  *     "cYbEr_PuNk11".swapcase   #=> "CyBeR_pUnK11"
 129  */
 130 static mrb_value
 131 mrb_str_swapcase(mrb_state *mrb, mrb_value self)
 132 {
 133   mrb_value str;
 134
 135   str = mrb_str_dup(mrb, self);
 136   mrb_str_swapcase_bang(mrb, str);
 137   return str;
 138 }
 139
 140 static mrb_value mrb_fixnum_chr(mrb_state *mrb, mrb_value num);
 141
 142 /*
 143  *  call-seq:
 144  *     str << integer       -> str
 145  *     str.concat(integer)  -> str
 146  *     str << obj           -> str
 147  *     str.concat(obj)      -> str
 148  *
 149  *  Append---Concatenates the given object to <i>str</i>. If the object is a
 150  *  <code>Integer</code>, it is considered as a codepoint, and is converted
 151  *  to a character before concatenation.
 152  *
 153  *     a = "hello "
 154  *     a << "world"   #=> "hello world"
 155  *     a.concat(33)   #=> "hello world!"
 156  */
 157 static mrb_value
 158 mrb_str_concat_m(mrb_state *mrb, mrb_value self)
 159 {
 160   mrb_value str;
 161
 162   mrb_get_args(mrb, "o", &str);
 163   if (mrb_fixnum_p(str))
 164     str = mrb_fixnum_chr(mrb, str);
 165   else
 166     str = mrb_ensure_string_type(mrb, str);
 167   mrb_str_concat(mrb, self, str);
 168   return self;
 169 }
 170
 171 /*
 172  *  call-seq:
 173  *     str.start_with?([prefixes]+)   -> true or false
 174  *
 175  *  Returns true if +str+ starts with one of the +prefixes+ given.
 176  *
 177  *    "hello".start_with?("hell")               #=> true
 178  *
 179  *    # returns true if one of the prefixes matches.
 180  *    "hello".start_with?("heaven", "hell")     #=> true
 181  *    "hello".start_with?("heaven", "paradise") #=> false
 182  *    "h".start_with?("heaven", "hell")         #=> false
 183  */
 184 static mrb_value
 185 mrb_str_start_with(mrb_state *mrb, mrb_value self)
 186 {
 187   mrb_value *argv, sub;
 188   mrb_int argc, i;
 189   mrb_get_args(mrb, "*", &argv, &argc);
 190
 191   for (i = 0; i < argc; i++) {
 192     size_t len_l, len_r;
 193     int ai = mrb_gc_arena_save(mrb);
 194     sub = mrb_ensure_string_type(mrb, argv[i]);
 195     mrb_gc_arena_restore(mrb, ai);
 196     len_l = RSTRING_LEN(self);
 197     len_r = RSTRING_LEN(sub);
 198     if (len_l >= len_r) {
 199       if (memcmp(RSTRING_PTR(self), RSTRING_PTR(sub), len_r) == 0) {
 200         return mrb_true_value();
 201       }
 202     }
 203   }
 204   return mrb_false_value();
 205 }
 206
 207 /*
 208  *  call-seq:
 209  *     str.end_with?([suffixes]+)   -> true or false
 210  *
 211  *  Returns true if +str+ ends with one of the +suffixes+ given.
 212  */
 213 static mrb_value
 214 mrb_str_end_with(mrb_state *mrb, mrb_value self)
 215 {
 216   mrb_value *argv, sub;
 217   mrb_int argc, i;
 218   mrb_get_args(mrb, "*", &argv, &argc);
 219
 220   for (i = 0; i < argc; i++) {
 221     size_t len_l, len_r;
 222     int ai = mrb_gc_arena_save(mrb);
 223     sub = mrb_ensure_string_type(mrb, argv[i]);
 224     mrb_gc_arena_restore(mrb, ai);
 225     len_l = RSTRING_LEN(self);
 226     len_r = RSTRING_LEN(sub);
 227     if (len_l >= len_r) {
 228       if (memcmp(RSTRING_PTR(self) + (len_l - len_r),
 229                  RSTRING_PTR(sub),
 230                  len_r) == 0) {
 231         return mrb_true_value();
 232       }
 233     }
 234   }
 235   return mrb_false_value();
 236 }
 237
 238 enum tr_pattern_type {
 239   TR_UNINITIALIZED = 0,
 240   TR_IN_ORDER  = 1,
 241   TR_RANGE = 2,
 242 };
 243
 244 /*
 245   #tr Pattern syntax
 246
 247   <syntax> ::= (<pattern>)* | '^' (<pattern>)*
 248   <pattern> ::= <in order> | <range>
 249   <in order> ::= (<ch>)+
 250   <range> ::= <ch> '-' <ch>
 251 */
 252 struct tr_pattern {
 253   uint8_t type;         // 1:in-order, 2:range
 254   mrb_bool flag_reverse : 1;
 255   mrb_bool flag_on_heap : 1;
 256   uint16_t n;
 257   union {
 258     uint16_t start_pos;
 259     char ch[2];
 260   } val;
 261   struct tr_pattern *next;
 262 };
 263
 264 #define STATIC_TR_PATTERN { 0 }
 265
 266 static inline void
 267 tr_free_pattern(mrb_state *mrb, struct tr_pattern *pat)
 268 {
 269   while (pat) {
 270     struct tr_pattern *p = pat->next;
 271     if (pat->flag_on_heap) {
 272       mrb_free(mrb, pat);
 273     }
 274     pat = p;
 275   }
 276 }
 277
 278 static struct tr_pattern*
 279 tr_parse_pattern(mrb_state *mrb, struct tr_pattern *ret, const mrb_value v_pattern, mrb_bool flag_reverse_enable)
 280 {
 281   const char *pattern = RSTRING_PTR(v_pattern);
 282   mrb_int pattern_length = RSTRING_LEN(v_pattern);
 283   mrb_bool flag_reverse = FALSE;
 284   struct tr_pattern *pat1;
 285   mrb_int i = 0;
 286
 287   if(flag_reverse_enable && pattern_length >= 2 && pattern[0] == '^') {
 288     flag_reverse = TRUE;
 289     i++;
 290   }
 291
 292   while (i < pattern_length) {
 293     /* is range pattern ? */
 294     mrb_bool const ret_uninit = (ret->type == TR_UNINITIALIZED);
 295     pat1 = ret_uninit
 296            ? ret
 297            : (struct tr_pattern*)mrb_malloc_simple(mrb, sizeof(struct tr_pattern));
 298     if ((i+2) < pattern_length && pattern[i] != '\\' && pattern[i+1] == '-') {
 299       if (pat1 == NULL && ret) {
 300       nomem:
 301         tr_free_pattern(mrb, ret);
 302         mrb_exc_raise(mrb, mrb_obj_value(mrb->nomem_err));
 303         return NULL;            /* not reached */
 304       }
 305       pat1->type = TR_RANGE;
 306       pat1->flag_reverse = flag_reverse;
 307       pat1->flag_on_heap = !ret_uninit;
 308       pat1->n = pattern[i+2] - pattern[i] + 1;
 309       pat1->next = NULL;
 310       pat1->val.ch[0] = pattern[i];
 311       pat1->val.ch[1] = pattern[i+2];
 312       i += 3;
 313     }
 314     else {
 315       /* in order pattern. */
 316       mrb_int start_pos = i++;
 317       mrb_int len;
 318
 319       while (i < pattern_length) {
 320         if ((i+2) < pattern_length && pattern[i] != '\\' && pattern[i+1] == '-')
 321           break;
 322         i++;
 323       }
 324
 325       len = i - start_pos;
 326       if (len > UINT16_MAX) {
 327         mrb_raise(mrb, E_ARGUMENT_ERROR, "tr pattern too long (max 65536)");
 328       }
 329       if (pat1 == NULL && ret) {
 330         goto nomem;
 331       }
 332       pat1->type = TR_IN_ORDER;
 333       pat1->flag_reverse = flag_reverse;
 334       pat1->flag_on_heap = !ret_uninit;
 335       pat1->n = len;
 336       pat1->next = NULL;
 337       pat1->val.start_pos = start_pos;
 338     }
 339
 340     if (ret == NULL || ret_uninit) {
 341       ret = pat1;
 342     }
 343     else {
 344       struct tr_pattern *p = ret;
 345       while (p->next != NULL) {
 346         p = p->next;
 347       }
 348       p->next = pat1;
 349     }
 350   }
 351
 352   return ret;
 353 }
 354
 355 static inline mrb_int
 356 tr_find_character(const struct tr_pattern *pat, const char *pat_str, int ch)
 357 {
 358   mrb_int ret = -1;
 359   mrb_int n_sum = 0;
 360   mrb_int flag_reverse = pat ? pat->flag_reverse : 0;
 361
 362   while (pat != NULL) {
 363     if (pat->type == TR_IN_ORDER) {
 364       int i;
 365       for (i = 0; i < pat->n; i++) {
 366         if (pat_str[pat->val.start_pos + i] == ch) ret = n_sum + i;
 367       }
 368     }
 369     else if (pat->type == TR_RANGE) {
 370       if (pat->val.ch[0] <= ch && ch <= pat->val.ch[1])
 371         ret = n_sum + ch - pat->val.ch[0];
 372     }
 373     else {
 374       mrb_assert(pat->type == TR_UNINITIALIZED);
 375     }
 376     n_sum += pat->n;
 377     pat = pat->next;
 378   }
 379
 380   if (flag_reverse) {
 381     return (ret < 0) ? MRB_INT_MAX : -1;
 382   }
 383   return ret;
 384 }
 385
 386 static inline mrb_int
 387 tr_get_character(const struct tr_pattern *pat, const char *pat_str, mrb_int n_th)
 388 {
 389   mrb_int n_sum = 0;
 390
 391   while (pat != NULL) {
 392     if (n_th < (n_sum + pat->n)) {
 393       mrb_int i = (n_th - n_sum);
 394
 395       switch (pat->type) {
 396       case TR_IN_ORDER:
 397         return pat_str[pat->val.start_pos + i];
 398       case TR_RANGE:
 399         return pat->val.ch[0]+i;
 400       case TR_UNINITIALIZED:
 401         return -1;
 402       }
 403     }
 404     if (pat->next == NULL) {
 405       switch (pat->type) {
 406       case TR_IN_ORDER:
 407         return pat_str[pat->val.start_pos + pat->n - 1];
 408       case TR_RANGE:
 409         return pat->val.ch[1];
 410       case TR_UNINITIALIZED:
 411         return -1;
 412       }
 413     }
 414     n_sum += pat->n;
 415     pat = pat->next;
 416   }
 417
 418   return -1;
 419 }
 420
 421 static inline void
 422 tr_bitmap_set(uint8_t bitmap[32], uint8_t ch)
 423 {
 424   uint8_t idx1 = ch / 8;
 425   uint8_t idx2 = ch % 8;
 426   bitmap[idx1] |= (1<<idx2);
 427 }
 428
 429 static inline mrb_bool
 430 tr_bitmap_detect(uint8_t bitmap[32], uint8_t ch)
 431 {
 432   uint8_t idx1 = ch / 8;
 433   uint8_t idx2 = ch % 8;
 434   if (bitmap[idx1] & (1<<idx2))
 435     return TRUE;
 436   return FALSE;
 437 }
 438
 439 /* compile patter to bitmap */
 440 static void
 441 tr_compile_pattern(const struct tr_pattern *pat, mrb_value pstr, uint8_t bitmap[32])
 442 {
 443   const char *pattern = RSTRING_PTR(pstr);
 444   mrb_int flag_reverse = pat ? pat->flag_reverse : 0;
 445   int i;
 446
 447   for (i=0; i<32; i++) {
 448     bitmap[i] = 0;
 449   }
 450   while (pat != NULL) {
 451     if (pat->type == TR_IN_ORDER) {
 452       for (i = 0; i < pat->n; i++) {
 453         tr_bitmap_set(bitmap, pattern[pat->val.start_pos + i]);
 454       }
 455     }
 456     else if (pat->type == TR_RANGE) {
 457       for (i = pat->val.ch[0]; i < pat->val.ch[1]; i++) {
 458         tr_bitmap_set(bitmap, i);
 459       }
 460     }
 461     else {
 462       mrb_assert(pat->type == TR_UNINITIALIZED);
 463     }
 464     pat = pat->next;
 465   }
 466
 467   if (flag_reverse) {
 468     for (i=0; i<32; i++) {
 469       bitmap[i] ^= 0xff;
 470     }
 471   }
 472 }
 473
 474 static mrb_bool
 475 str_tr(mrb_state *mrb, mrb_value str, mrb_value p1, mrb_value p2, mrb_bool squeeze)
 476 {
 477   struct tr_pattern pat = STATIC_TR_PATTERN;
 478   struct tr_pattern rep_storage = STATIC_TR_PATTERN;
 479   char *s;
 480   mrb_int len;
 481   mrb_int i;
 482   mrb_int j;
 483   mrb_bool flag_changed = FALSE;
 484   mrb_int lastch = -1;
 485   struct tr_pattern *rep;
 486
 487   mrb_str_modify(mrb, mrb_str_ptr(str));
 488   tr_parse_pattern(mrb, &pat, p1, TRUE);
 489   rep = tr_parse_pattern(mrb, &rep_storage, p2, FALSE);
 490   s = RSTRING_PTR(str);
 491   len = RSTRING_LEN(str);
 492
 493   for (i=j=0; i<len; i++,j++) {
 494     mrb_int n = tr_find_character(&pat, RSTRING_PTR(p1), s[i]);
 495
 496     if (i>j) s[j] = s[i];
 497     if (n >= 0) {
 498       flag_changed = TRUE;
 499       if (rep == NULL) {
 500         j--;
 501       }
 502       else {
 503         mrb_int c = tr_get_character(rep, RSTRING_PTR(p2), n);
 504
 505         if (c < 0 || (squeeze && c == lastch)) {
 506           j--;
 507           continue;
 508         }
 509         if (c > 0x80) {
 510           mrb_raisef(mrb, E_ARGUMENT_ERROR, "character (%S) out of range",
 511                      mrb_fixnum_value((mrb_int)c));
 512         }
 513         lastch = c;
 514         s[i] = (char)c;
 515       }
 516     }
 517   }
 518
 519   tr_free_pattern(mrb, &pat);
 520   tr_free_pattern(mrb, rep);
 521
 522   if (flag_changed) {
 523     RSTR_SET_LEN(RSTRING(str), j);
 524     RSTRING_PTR(str)[j] = 0;
 525   }
 526   return flag_changed;
 527 }
 528
 529 /*
 530  * call-seq:
 531  *   str.tr(from_str, to_str)   => new_str
 532  *
 533  * Returns a copy of str with the characters in from_str replaced by the
 534  * corresponding characters in to_str.  If to_str is shorter than from_str,
 535  * it is padded with its last character in order to maintain the
 536  * correspondence.
 537  *
 538  *  "hello".tr('el', 'ip')      #=> "hippo"
 539  *  "hello".tr('aeiou', '*')    #=> "h*ll*"
 540  *  "hello".tr('aeiou', 'AA*')  #=> "hAll*"
 541  *
 542  * Both strings may use the c1-c2 notation to denote ranges of characters,
 543  * and from_str may start with a ^, which denotes all characters except
 544  * those listed.
 545  *
 546  *  "hello".tr('a-y', 'b-z')    #=> "ifmmp"
 547  *  "hello".tr('^aeiou', '*')   #=> "*e**o"
 548  *
 549  * The backslash character \ can be used to escape ^ or - and is otherwise
 550  * ignored unless it appears at the end of a range or the end of the
 551  * from_str or to_str:
 552  *
 553  *
 554  *  "hello^world".tr("\\^aeiou", "*") #=> "h*ll**w*rld"
 555  *  "hello-world".tr("a\\-eo", "*")   #=> "h*ll**w*rld"
 556  *
 557  *  "hello\r\nworld".tr("\r", "")   #=> "hello\nworld"
 558  *  "hello\r\nworld".tr("\\r", "")  #=> "hello\r\nwold"
 559  *  "hello\r\nworld".tr("\\\r", "") #=> "hello\nworld"
 560  *
 561  *  "X['\\b']".tr("X\\", "")   #=> "['b']"
 562  *  "X['\\b']".tr("X-\\]", "") #=> "'b'"
 563  *
 564  *  Note: conversion is effective only in ASCII region.
 565  */
 566 static mrb_value
 567 mrb_str_tr(mrb_state *mrb, mrb_value str)
 568 {
 569   mrb_value dup;
 570   mrb_value p1, p2;
 571
 572   mrb_get_args(mrb, "SS", &p1, &p2);
 573   dup = mrb_str_dup(mrb, str);
 574   str_tr(mrb, dup, p1, p2, FALSE);
 575   return dup;
 576 }
 577
 578 /*
 579  * call-seq:
 580  *   str.tr!(from_str, to_str)   -> str or nil
 581  *
 582  * Translates str in place, using the same rules as String#tr.
 583  * Returns str, or nil if no changes were made.
 584  */
 585 static mrb_value
 586 mrb_str_tr_bang(mrb_state *mrb, mrb_value str)
 587 {
 588   mrb_value p1, p2;
 589
 590   mrb_get_args(mrb, "SS", &p1, &p2);
 591   if (str_tr(mrb, str, p1, p2, FALSE)) {
 592     return str;
 593   }
 594   return mrb_nil_value();
 595 }
 596
 597 /*
 598  * call-seq:
 599  *   str.tr_s(from_str, to_str)   -> new_str
 600  *
 601  * Processes a copy of str as described under String#tr, then removes
 602  * duplicate characters in regions that were affected by the translation.
 603  *
 604  *  "hello".tr_s('l', 'r')     #=> "hero"
 605  *  "hello".tr_s('el', '*')    #=> "h*o"
 606  *  "hello".tr_s('el', 'hx')   #=> "hhxo"
 607  */
 608 static mrb_value
 609 mrb_str_tr_s(mrb_state *mrb, mrb_value str)
 610 {
 611   mrb_value dup;
 612   mrb_value p1, p2;
 613
 614   mrb_get_args(mrb, "SS", &p1, &p2);
 615   dup = mrb_str_dup(mrb, str);
 616   str_tr(mrb, dup, p1, p2, TRUE);
 617   return dup;
 618 }
 619
 620 /*
 621  * call-seq:
 622  *   str.tr_s!(from_str, to_str)   -> str or nil
 623  *
 624  * Performs String#tr_s processing on str in place, returning
 625  * str, or nil if no changes were made.
 626  */
 627 static mrb_value
 628 mrb_str_tr_s_bang(mrb_state *mrb, mrb_value str)
 629 {
 630   mrb_value p1, p2;
 631
 632   mrb_get_args(mrb, "SS", &p1, &p2);
 633   if (str_tr(mrb, str, p1, p2, TRUE)) {
 634     return str;
 635   }
 636   return mrb_nil_value();
 637 }
 638
 639 static mrb_bool
 640 str_squeeze(mrb_state *mrb, mrb_value str, mrb_value v_pat)
 641 {
 642   struct tr_pattern pat_storage = STATIC_TR_PATTERN;
 643   struct tr_pattern *pat = NULL;
 644   mrb_int i, j;
 645   char *s;
 646   mrb_int len;
 647   mrb_bool flag_changed = FALSE;
 648   mrb_int lastch = -1;
 649   uint8_t bitmap[32];
 650
 651   mrb_str_modify(mrb, mrb_str_ptr(str));
 652   if (!mrb_nil_p(v_pat)) {
 653     pat = tr_parse_pattern(mrb, &pat_storage, v_pat, TRUE);
 654     tr_compile_pattern(pat, v_pat, bitmap);
 655     tr_free_pattern(mrb, pat);
 656   }
 657   s = RSTRING_PTR(str);
 658   len = RSTRING_LEN(str);
 659
 660   if (pat) {
 661     for (i=j=0; i<len; i++,j++) {
 662       if (i>j) s[j] = s[i];
 663       if (tr_bitmap_detect(bitmap, s[i]) && s[i] == lastch) {
 664         flag_changed = TRUE;
 665         j--;
 666       }
 667       lastch = s[i];
 668     }
 669   }
 670   else {
 671     for (i=j=0; i<len; i++,j++) {
 672       if (i>j) s[j] = s[i];
 673       if (s[i] >= 0 && s[i] == lastch) {
 674         flag_changed = TRUE;
 675         j--;
 676       }
 677       lastch = s[i];
 678     }
 679   }
 680
 681   if (flag_changed) {
 682     RSTR_SET_LEN(RSTRING(str), j);
 683     RSTRING_PTR(str)[j] = 0;
 684   }
 685   return flag_changed;
 686 }
 687
 688 /*
 689  * call-seq:
 690  *   str.squeeze([other_str])    -> new_str
 691  *
 692  * Builds a set of characters from the other_str
 693  * parameter(s) using the procedure described for String#count. Returns a
 694  * new string where runs of the same character that occur in this set are
 695  * replaced by a single character. If no arguments are given, all runs of
 696  * identical characters are replaced by a single character.
 697  *
 698  *  "yellow moon".squeeze                  #=> "yelow mon"
 699  *  "  now   is  the".squeeze(" ")         #=> " now is the"
 700  *  "putters shoot balls".squeeze("m-z")   #=> "puters shot balls"
 701  */
 702 static mrb_value
 703 mrb_str_squeeze(mrb_state *mrb, mrb_value str)
 704 {
 705   mrb_value pat = mrb_nil_value();
 706   mrb_value dup;
 707
 708   mrb_get_args(mrb, "|S", &pat);
 709   dup = mrb_str_dup(mrb, str);
 710   str_squeeze(mrb, dup, pat);
 711   return dup;
 712 }
 713
 714 /*
 715  * call-seq:
 716  *   str.squeeze!([other_str])   -> str or nil
 717  *
 718  * Squeezes str in place, returning either str, or nil if no
 719  * changes were made.
 720  */
 721 static mrb_value
 722 mrb_str_squeeze_bang(mrb_state *mrb, mrb_value str)
 723 {
 724   mrb_value pat = mrb_nil_value();
 725
 726   mrb_get_args(mrb, "|S", &pat);
 727   if (str_squeeze(mrb, str, pat)) {
 728     return str;
 729   }
 730   return mrb_nil_value();
 731 }
 732
 733 static mrb_bool
 734 str_delete(mrb_state *mrb, mrb_value str, mrb_value v_pat)
 735 {
 736   struct tr_pattern pat = STATIC_TR_PATTERN;
 737   mrb_int i, j;
 738   char *s;
 739   mrb_int len;
 740   mrb_bool flag_changed = FALSE;
 741   uint8_t bitmap[32];
 742
 743   mrb_str_modify(mrb, mrb_str_ptr(str));
 744   tr_parse_pattern(mrb, &pat, v_pat, TRUE);
 745   tr_compile_pattern(&pat, v_pat, bitmap);
 746   tr_free_pattern(mrb, &pat);
 747
 748   s = RSTRING_PTR(str);
 749   len = RSTRING_LEN(str);
 750
 751   for (i=j=0; i<len; i++,j++) {
 752     if (i>j) s[j] = s[i];
 753     if (tr_bitmap_detect(bitmap, s[i])) {
 754       flag_changed = TRUE;
 755       j--;
 756     }
 757   }
 758   if (flag_changed) {
 759     RSTR_SET_LEN(RSTRING(str), j);
 760     RSTRING_PTR(str)[j] = 0;
 761   }
 762   return flag_changed;
 763 }
 764
 765 static mrb_value
 766 mrb_str_delete(mrb_state *mrb, mrb_value str)
 767 {
 768   mrb_value pat;
 769   mrb_value dup;
 770
 771   mrb_get_args(mrb, "S", &pat);
 772   dup = mrb_str_dup(mrb, str);
 773   str_delete(mrb, dup, pat);
 774   return dup;
 775 }
 776
 777 static mrb_value
 778 mrb_str_delete_bang(mrb_state *mrb, mrb_value str)
 779 {
 780   mrb_value pat;
 781
 782   mrb_get_args(mrb, "S", &pat);
 783   if (str_delete(mrb, str, pat)) {
 784     return str;
 785   }
 786   return mrb_nil_value();
 787 }
 788
 789 /*
 790  * call_seq:
 791  *   str.count([other_str])   -> integer
 792  *
 793  * Each other_str parameter defines a set of characters to count.  The
 794  * intersection of these sets defines the characters to count in str.  Any
 795  * other_str that starts with a caret ^ is negated.  The sequence c1-c2
 796  * means all characters between c1 and c2.  The backslash character \ can
 797  * be used to escape ^ or - and is otherwise ignored unless it appears at
 798  * the end of a sequence or the end of a other_str.
 799  */
 800 static mrb_value
 801 mrb_str_count(mrb_state *mrb, mrb_value str)
 802 {
 803   mrb_value v_pat = mrb_nil_value();
 804   mrb_int i;
 805   char *s;
 806   mrb_int len;
 807   mrb_int count = 0;
 808   struct tr_pattern pat = STATIC_TR_PATTERN;
 809   uint8_t bitmap[32];
 810
 811   mrb_get_args(mrb, "S", &v_pat);
 812   tr_parse_pattern(mrb, &pat, v_pat, TRUE);
 813   tr_compile_pattern(&pat, v_pat, bitmap);
 814   tr_free_pattern(mrb, &pat);
 815
 816   s = RSTRING_PTR(str);
 817   len = RSTRING_LEN(str);
 818   for (i = 0; i < len; i++) {
 819     if (tr_bitmap_detect(bitmap, s[i])) count++;
 820   }
 821   return mrb_fixnum_value(count);
 822 }
 823
 824 static mrb_value
 825 mrb_str_hex(mrb_state *mrb, mrb_value self)
 826 {
 827   return mrb_str_to_inum(mrb, self, 16, FALSE);
 828 }
 829
 830 static mrb_value
 831 mrb_str_oct(mrb_state *mrb, mrb_value self)
 832 {
 833   return mrb_str_to_inum(mrb, self, 8, FALSE);
 834 }
 835
 836 /*
 837  *  call-seq:
 838  *     string.chr    ->  string
 839  *
 840  *  Returns a one-character string at the beginning of the string.
 841  *
 842  *     a = "abcde"
 843  *     a.chr    #=> "a"
 844  */
 845 static mrb_value
 846 mrb_str_chr(mrb_state *mrb, mrb_value self)
 847 {
 848   return mrb_str_substr(mrb, self, 0, 1);
 849 }
 850
 851 static mrb_value
 852 mrb_fixnum_chr(mrb_state *mrb, mrb_value num)
 853 {
 854   mrb_int cp = mrb_fixnum(num);
 855 #ifdef MRB_UTF8_STRING
 856   char utf8[4];
 857   mrb_int len;
 858
 859   if (cp < 0 || 0x10FFFF < cp) {
 860     mrb_raisef(mrb, E_RANGE_ERROR, "%S out of char range", num);
 861   }
 862   if (cp < 0x80) {
 863     utf8[0] = (char)cp;
 864     len = 1;
 865   }
 866   else if (cp < 0x800) {
 867     utf8[0] = (char)(0xC0 | (cp >> 6));
 868     utf8[1] = (char)(0x80 | (cp & 0x3F));
 869     len = 2;
 870   }
 871   else if (cp < 0x10000) {
 872     utf8[0] = (char)(0xE0 |  (cp >> 12));
 873     utf8[1] = (char)(0x80 | ((cp >>  6) & 0x3F));
 874     utf8[2] = (char)(0x80 | ( cp        & 0x3F));
 875     len = 3;
 876   }
 877   else {
 878     utf8[0] = (char)(0xF0 |  (cp >> 18));
 879     utf8[1] = (char)(0x80 | ((cp >> 12) & 0x3F));
 880     utf8[2] = (char)(0x80 | ((cp >>  6) & 0x3F));
 881     utf8[3] = (char)(0x80 | ( cp        & 0x3F));
 882     len = 4;
 883   }
 884   return mrb_str_new(mrb, utf8, len);
 885 #else
 886   char c;
 887
 888   if (cp < 0 || 0xff < cp) {
 889     mrb_raisef(mrb, E_RANGE_ERROR, "%S out of char range", num);
 890   }
 891   c = (char)cp;
 892   return mrb_str_new(mrb, &c, 1);
 893 #endif
 894 }
 895
 896 /*
 897  *  call-seq:
 898  *     string.succ    ->  string
 899  *
 900  *  Returns next sequence of the string;
 901  *
 902  *     a = "abc"
 903  *     a.succ    #=> "abd"
 904  */
 905 static mrb_value
 906 mrb_str_succ_bang(mrb_state *mrb, mrb_value self)
 907 {
 908   mrb_value result;
 909   unsigned char *p, *e, *b, *t;
 910   const char *prepend;
 911   struct RString *s = mrb_str_ptr(self);
 912   mrb_int l;
 913
 914   if (RSTRING_LEN(self) == 0)
 915     return self;
 916
 917   mrb_str_modify(mrb, s);
 918   l = RSTRING_LEN(self);
 919   b = p = (unsigned char*) RSTRING_PTR(self);
 920   t = e = p + l;
 921   *(e--) = 0;
 922
 923   // find trailing ascii/number
 924   while (e >= b) {
 925     if (ISALNUM(*e))
 926       break;
 927     e--;
 928   }
 929   if (e < b) {
 930     e = p + l - 1;
 931     result = mrb_str_new_lit(mrb, "");
 932   }
 933   else {
 934     // find leading letter of the ascii/number
 935     b = e;
 936     while (b > p) {
 937       if (!ISALNUM(*b) || (ISALNUM(*b) && *b != '9' && *b != 'z' && *b != 'Z'))
 938         break;
 939       b--;
 940     }
 941     if (!ISALNUM(*b))
 942       b++;
 943     result = mrb_str_new(mrb, (char*) p, b - p);
 944   }
 945
 946   while (e >= b) {
 947     if (!ISALNUM(*e)) {
 948       if (*e == 0xff) {
 949         mrb_str_cat_lit(mrb, result, "\x01");
 950         (*e) = 0;
 951       }
 952       else
 953         (*e)++;
 954       break;
 955     }
 956     prepend = NULL;
 957     if (*e == '9') {
 958       if (e == b) prepend = "1";
 959       *e = '0';
 960     }
 961     else if (*e == 'z') {
 962       if (e == b) prepend = "a";
 963       *e = 'a';
 964     }
 965     else if (*e == 'Z') {
 966       if (e == b) prepend = "A";
 967       *e = 'A';
 968     }
 969     else {
 970       (*e)++;
 971       break;
 972     }
 973     if (prepend) mrb_str_cat_cstr(mrb, result, prepend);
 974     e--;
 975   }
 976   result = mrb_str_cat(mrb, result, (char*) b, t - b);
 977   l = RSTRING_LEN(result);
 978   mrb_str_resize(mrb, self, l);
 979   memcpy(RSTRING_PTR(self), RSTRING_PTR(result), l);
 980   return self;
 981 }
 982
 983 static mrb_value
 984 mrb_str_succ(mrb_state *mrb, mrb_value self)
 985 {
 986   mrb_value str;
 987
 988   str = mrb_str_dup(mrb, self);
 989   mrb_str_succ_bang(mrb, str);
 990   return str;
 991 }
 992
 993 #ifdef MRB_UTF8_STRING
 994 static const char utf8len_codepage_zero[256] =
 995 {
 996   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 997   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 998   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 999   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1000   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1001   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1002   2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1003   3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,
1004 };
1005
1006 static mrb_int
1007 utf8code(unsigned char* p)
1008 {
1009   mrb_int len;
1010
1011   if (p[0] < 0x80)
1012     return p[0];
1013
1014   len = utf8len_codepage_zero[p[0]];
1015   if (len > 1 && (p[1] & 0xc0) == 0x80) {
1016     if (len == 2)
1017       return ((p[0] & 0x1f) << 6) + (p[1] & 0x3f);
1018     if ((p[2] & 0xc0) == 0x80) {
1019       if (len == 3)
1020         return ((p[0] & 0x0f) << 12) + ((p[1] & 0x3f) << 6)
1021           + (p[2] & 0x3f);
1022       if ((p[3] & 0xc0) == 0x80) {
1023         if (len == 4)
1024           return ((p[0] & 0x07) << 18) + ((p[1] & 0x3f) << 12)
1025             + ((p[2] & 0x3f) << 6) + (p[3] & 0x3f);
1026         if ((p[4] & 0xc0) == 0x80) {
1027           if (len == 5)
1028             return ((p[0] & 0x03) << 24) + ((p[1] & 0x3f) << 18)
1029               + ((p[2] & 0x3f) << 12) + ((p[3] & 0x3f) << 6)
1030               + (p[4] & 0x3f);
1031           if ((p[5] & 0xc0) == 0x80 && len == 6)
1032             return ((p[0] & 0x01) << 30) + ((p[1] & 0x3f) << 24)
1033               + ((p[2] & 0x3f) << 18) + ((p[3] & 0x3f) << 12)
1034               + ((p[4] & 0x3f) << 6) + (p[5] & 0x3f);
1035         }
1036       }
1037     }
1038   }
1039   return p[0];
1040 }
1041
1042 static mrb_value
1043 mrb_str_ord(mrb_state* mrb, mrb_value str)
1044 {
1045   if (RSTRING_LEN(str) == 0)
1046     mrb_raise(mrb, E_ARGUMENT_ERROR, "empty string");
1047   return mrb_fixnum_value(utf8code((unsigned char*) RSTRING_PTR(str)));
1048 }
1049 #else
1050 static mrb_value
1051 mrb_str_ord(mrb_state* mrb, mrb_value str)
1052 {
1053   if (RSTRING_LEN(str) == 0)
1054     mrb_raise(mrb, E_ARGUMENT_ERROR, "empty string");
1055   return mrb_fixnum_value((unsigned char)RSTRING_PTR(str)[0]);
1056 }
1057 #endif
1058
1059 /*
1060  *  call-seq:
1061  *     str.delete_prefix!(prefix) -> self or nil
1062  *
1063  *  Deletes leading <code>prefix</code> from <i>str</i>, returning
1064  *  <code>nil</code> if no change was made.
1065  *
1066  *     "hello".delete_prefix!("hel") #=> "lo"
1067  *     "hello".delete_prefix!("llo") #=> nil
1068  */
1069 static mrb_value
1070 mrb_str_del_prefix_bang(mrb_state *mrb, mrb_value self)
1071 {
1072   mrb_int plen, slen;
1073   char *ptr, *s;
1074   struct RString *str = RSTRING(self);
1075
1076   mrb_get_args(mrb, "s", &ptr, &plen);
1077   slen = RSTR_LEN(str);
1078   if (plen > slen) return mrb_nil_value();
1079   s = RSTR_PTR(str);
1080   if (memcmp(s, ptr, plen) != 0) return mrb_nil_value();
1081   if (!MRB_FROZEN_P(str) && (RSTR_SHARED_P(str) || RSTR_FSHARED_P(str))) {
1082     str->as.heap.ptr += plen;
1083   }
1084   else {
1085     mrb_str_modify(mrb, str);
1086     s = RSTR_PTR(str);
1087     memmove(s, s+plen, slen-plen);
1088   }
1089   RSTR_SET_LEN(str, slen-plen);
1090   return self;
1091 }
1092
1093 /*
1094  *  call-seq:
1095  *     str.delete_prefix(prefix) -> new_str
1096  *
1097  *  Returns a copy of <i>str</i> with leading <code>prefix</code> deleted.
1098  *
1099  *     "hello".delete_prefix("hel") #=> "lo"
1100  *     "hello".delete_prefix("llo") #=> "hello"
1101  */
1102 static mrb_value
1103 mrb_str_del_prefix(mrb_state *mrb, mrb_value self)
1104 {
1105   mrb_int plen, slen;
1106   char *ptr;
1107
1108   mrb_get_args(mrb, "s", &ptr, &plen);
1109   slen = RSTRING_LEN(self);
1110   if (plen > slen) return mrb_str_dup(mrb, self);
1111   if (memcmp(RSTRING_PTR(self), ptr, plen) != 0)
1112     return mrb_str_dup(mrb, self);
1113   return mrb_str_substr(mrb, self, plen, slen-plen);
1114 }
1115
1116 /*
1117  *  call-seq:
1118  *     str.delete_suffix!(suffix) -> self or nil
1119  *
1120  *  Deletes trailing <code>suffix</code> from <i>str</i>, returning
1121  *  <code>nil</code> if no change was made.
1122  *
1123  *     "hello".delete_suffix!("llo") #=> "he"
1124  *     "hello".delete_suffix!("hel") #=> nil
1125  */
1126 static mrb_value
1127 mrb_str_del_suffix_bang(mrb_state *mrb, mrb_value self)
1128 {
1129   mrb_int plen, slen;
1130   char *ptr, *s;
1131   struct RString *str = RSTRING(self);
1132
1133   mrb_get_args(mrb, "s", &ptr, &plen);
1134   slen = RSTR_LEN(str);
1135   if (plen > slen) return mrb_nil_value();
1136   s = RSTR_PTR(str);
1137   if (memcmp(s+slen-plen, ptr, plen) != 0) return mrb_nil_value();
1138   if (!MRB_FROZEN_P(str) && (RSTR_SHARED_P(str) || RSTR_FSHARED_P(str))) {
1139     /* no need to modify string */
1140   }
1141   else {
1142     mrb_str_modify(mrb, str);
1143   }
1144   RSTR_SET_LEN(str, slen-plen);
1145   return self;
1146 }
1147
1148 /*
1149  *  call-seq:
1150  *     str.delete_suffix(suffix) -> new_str
1151  *
1152  *  Returns a copy of <i>str</i> with leading <code>suffix</code> deleted.
1153  *
1154  *     "hello".delete_suffix("hel") #=> "lo"
1155  *     "hello".delete_suffix("llo") #=> "hello"
1156  */
1157 static mrb_value
1158 mrb_str_del_suffix(mrb_state *mrb, mrb_value self)
1159 {
1160   mrb_int plen, slen;
1161   char *ptr;
1162
1163   mrb_get_args(mrb, "s", &ptr, &plen);
1164   slen = RSTRING_LEN(self);
1165   if (plen > slen) return mrb_str_dup(mrb, self);
1166   if (memcmp(RSTRING_PTR(self)+slen-plen, ptr, plen) != 0)
1167     return mrb_str_dup(mrb, self);
1168   return mrb_str_substr(mrb, self, 0, slen-plen);
1169 }
1170
1171 static mrb_value
1172 mrb_str_lines(mrb_state *mrb, mrb_value self)
1173 {
1174   mrb_value result;
1175   int ai;
1176   mrb_int len;
1177   char *b = RSTRING_PTR(self);
1178   char *p = b, *t;
1179   char *e = b + RSTRING_LEN(self);
1180
1181   mrb_get_args(mrb, "");
1182
1183   result = mrb_ary_new(mrb);
1184   ai = mrb_gc_arena_save(mrb);
1185   while (p < e) {
1186     t = p;
1187     while (p < e && *p != '\n') p++;
1188     if (*p == '\n') p++;
1189     len = (mrb_int) (p - t);
1190     mrb_ary_push(mrb, result, mrb_str_new(mrb, t, len));
1191     mrb_gc_arena_restore(mrb, ai);
1192   }
1193   return result;
1194 }
1195
1196 void
1197 mrb_mruby_string_ext_gem_init(mrb_state* mrb)
1198 {
1199   struct RClass * s = mrb->string_class;
1200
1201   mrb_define_method(mrb, s, "dump",            mrb_str_dump,            MRB_ARGS_NONE());
1202   mrb_define_method(mrb, s, "getbyte",         mrb_str_getbyte,         MRB_ARGS_REQ(1));
1203   mrb_define_method(mrb, s, "setbyte",         mrb_str_setbyte,         MRB_ARGS_REQ(2));
1204   mrb_define_method(mrb, s, "byteslice",       mrb_str_byteslice,       MRB_ARGS_REQ(1)|MRB_ARGS_OPT(1));
1205   mrb_define_method(mrb, s, "swapcase!",       mrb_str_swapcase_bang,   MRB_ARGS_NONE());
1206   mrb_define_method(mrb, s, "swapcase",        mrb_str_swapcase,        MRB_ARGS_NONE());
1207   mrb_define_method(mrb, s, "concat",          mrb_str_concat_m,        MRB_ARGS_REQ(1));
1208   mrb_define_method(mrb, s, "<<",              mrb_str_concat_m,        MRB_ARGS_REQ(1));
1209   mrb_define_method(mrb, s, "count",           mrb_str_count,           MRB_ARGS_REQ(1));
1210   mrb_define_method(mrb, s, "tr",              mrb_str_tr,              MRB_ARGS_REQ(2));
1211   mrb_define_method(mrb, s, "tr!",             mrb_str_tr_bang,         MRB_ARGS_REQ(2));
1212   mrb_define_method(mrb, s, "tr_s",            mrb_str_tr_s,            MRB_ARGS_REQ(2));
1213   mrb_define_method(mrb, s, "tr_s!",           mrb_str_tr_s_bang,       MRB_ARGS_REQ(2));
1214   mrb_define_method(mrb, s, "squeeze",         mrb_str_squeeze,         MRB_ARGS_OPT(1));
1215   mrb_define_method(mrb, s, "squeeze!",        mrb_str_squeeze_bang,    MRB_ARGS_OPT(1));
1216   mrb_define_method(mrb, s, "delete",          mrb_str_delete,          MRB_ARGS_REQ(1));
1217   mrb_define_method(mrb, s, "delete!",         mrb_str_delete_bang,     MRB_ARGS_REQ(1));
1218   mrb_define_method(mrb, s, "start_with?",     mrb_str_start_with,      MRB_ARGS_REST());
1219   mrb_define_method(mrb, s, "end_with?",       mrb_str_end_with,        MRB_ARGS_REST());
1220   mrb_define_method(mrb, s, "hex",             mrb_str_hex,             MRB_ARGS_NONE());
1221   mrb_define_method(mrb, s, "oct",             mrb_str_oct,             MRB_ARGS_NONE());
1222   mrb_define_method(mrb, s, "chr",             mrb_str_chr,             MRB_ARGS_NONE());
1223   mrb_define_method(mrb, s, "succ",            mrb_str_succ,            MRB_ARGS_NONE());
1224   mrb_define_method(mrb, s, "succ!",           mrb_str_succ_bang,       MRB_ARGS_NONE());
1225   mrb_define_alias(mrb,  s, "next",            "succ");
1226   mrb_define_alias(mrb,  s, "next!",           "succ!");
1227   mrb_define_method(mrb, s, "ord",             mrb_str_ord,             MRB_ARGS_NONE());
1228   mrb_define_method(mrb, s, "delete_prefix!",  mrb_str_del_prefix_bang, MRB_ARGS_REQ(1));
1229   mrb_define_method(mrb, s, "delete_prefix",   mrb_str_del_prefix,      MRB_ARGS_REQ(1));
1230   mrb_define_method(mrb, s, "delete_suffix!",  mrb_str_del_suffix_bang, MRB_ARGS_REQ(1));
1231   mrb_define_method(mrb, s, "delete_suffix",   mrb_str_del_suffix,      MRB_ARGS_REQ(1));
1232
1233   mrb_define_method(mrb, s, "__lines",         mrb_str_lines,           MRB_ARGS_NONE());
1234   mrb_define_method(mrb, mrb->fixnum_class, "chr", mrb_fixnum_chr, MRB_ARGS_NONE());
1235 }
1236
1237 void
1238 mrb_mruby_string_ext_gem_final(mrb_state* mrb)
1239 {
1240 }