third-party/mruby/src/symbol.c

   1 /*
   2 ** symbol.c - Symbol class
   3 **
   4 ** See Copyright Notice in mruby.h
   5 */
   6
   7 #include <limits.h>
   8 #include <string.h>
   9 #include <mruby.h>
  10 #include <mruby/khash.h>
  11 #include <mruby/string.h>
  12 #include <mruby/dump.h>
  13 #include <mruby/class.h>
  14
  15 /* ------------------------------------------------------ */
  16 typedef struct symbol_name {
  17   mrb_bool lit : 1;
  18   uint8_t prev;
  19   uint16_t len;
  20   const char *name;
  21 } symbol_name;
  22
  23 static void
  24 sym_validate_len(mrb_state *mrb, size_t len)
  25 {
  26   if (len >= RITE_LV_NULL_MARK) {
  27     mrb_raise(mrb, E_ARGUMENT_ERROR, "symbol length too long");
  28   }
  29 }
  30
  31 #ifndef MRB_ENABLE_ALL_SYMBOLS
  32 static const char pack_table[] = "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
  33
  34 static mrb_sym
  35 sym_inline_pack(const char *name, uint16_t len)
  36 {
  37   const int lower_length_max = (MRB_SYMBOL_BITSIZE - 2) / 5;
  38   const int mix_length_max   = (MRB_SYMBOL_BITSIZE - 2) / 6;
  39
  40   char c;
  41   const char *p;
  42   int i;
  43   mrb_sym sym = 0;
  44   int lower = 1;
  45
  46   if (len > lower_length_max) return 0; /* too long */
  47   for (i=0; i<len; i++) {
  48     uint32_t bits;
  49
  50     c = name[i];
  51     if (c == 0) return 0;       /* NUL in name */
  52     p = strchr(pack_table, (int)c);
  53     if (p == 0) return 0;       /* non alnum char */
  54     bits = (uint32_t)(p - pack_table)+1;
  55     if (bits > 27) lower = 0;
  56     if (i >= mix_length_max) break;
  57     sym |= bits<<(i*6+2);
  58   }
  59   if (lower) {
  60     sym = 0;
  61     for (i=0; i<len; i++) {
  62       uint32_t bits;
  63
  64       c = name[i];
  65       p = strchr(pack_table, (int)c);
  66       bits = (uint32_t)(p - pack_table)+1;
  67       sym |= bits<<(i*5+2);
  68     }
  69     return sym | 3;
  70   }
  71   if (len > mix_length_max) return 0;
  72   return sym | 1;
  73 }
  74
  75 static const char*
  76 sym_inline_unpack(mrb_sym sym, char *buf, mrb_int *lenp)
  77 {
  78   int bit_per_char = sym&2 ? 5 : 6;  /* all lower case if `sym&2` is true */
  79   int i;
  80
  81   mrb_assert(sym&1);
  82
  83   for (i=0; i<30/bit_per_char; i++) {
  84     uint32_t bits = sym>>(i*bit_per_char+2) & ((1<<bit_per_char)-1);
  85     if (bits == 0) break;
  86     buf[i] = pack_table[bits-1];;
  87   }
  88   buf[i] = '\0';
  89   if (lenp) *lenp = i;
  90   return buf;
  91 }
  92 #endif
  93
  94 uint8_t
  95 symhash(const char *key, size_t len)
  96 {
  97     uint32_t hash, i;
  98
  99     for(hash = i = 0; i < len; ++i) {
 100         hash += key[i];
 101         hash += (hash << 10);
 102         hash ^= (hash >> 6);
 103     }
 104     hash += (hash << 3);
 105     hash ^= (hash >> 11);
 106     hash += (hash << 15);
 107     return hash & 0xff;
 108 }
 109
 110 static mrb_sym
 111 find_symbol(mrb_state *mrb, const char *name, uint16_t len, uint8_t hash)
 112 {
 113   mrb_sym i;
 114   symbol_name *sname;
 115
 116 #ifndef MRB_ENABLE_ALL_SYMBOLS
 117   /* inline symbol */
 118   i = sym_inline_pack(name, len);
 119   if (i > 0) return i;
 120 #endif
 121
 122   i = mrb->symhash[hash];
 123   if (i == 0) return 0;
 124   do {
 125     sname = &mrb->symtbl[i];
 126     if (sname->len == len && memcmp(sname->name, name, len) == 0) {
 127       return i<<1;
 128     }
 129     if (sname->prev == 0xff) {
 130       i -= 0xff;
 131       sname = &mrb->symtbl[i];
 132       while (mrb->symtbl < sname) {
 133         if (sname->len == len && memcmp(sname->name, name, len) == 0) {
 134           return (mrb_sym)(sname - mrb->symtbl)<<1;
 135         }
 136         sname--;
 137       }
 138       return 0;
 139     }
 140     i -= sname->prev;
 141   } while (sname->prev > 0);
 142   return 0;
 143 }
 144
 145 static mrb_sym
 146 sym_intern(mrb_state *mrb, const char *name, size_t len, mrb_bool lit)
 147 {
 148   mrb_sym sym;
 149   symbol_name *sname;
 150   uint8_t hash;
 151
 152   sym_validate_len(mrb, len);
 153   hash = symhash(name, len);
 154   sym = find_symbol(mrb, name, len, hash);
 155   if (sym > 0) return sym;
 156
 157   /* registering a new symbol */
 158   sym = ++mrb->symidx;
 159   if (mrb->symcapa < sym) {
 160     if (mrb->symcapa == 0) mrb->symcapa = 100;
 161     else mrb->symcapa = (size_t)(mrb->symcapa * 6 / 5);
 162     mrb->symtbl = (symbol_name*)mrb_realloc(mrb, mrb->symtbl, sizeof(symbol_name)*(mrb->symcapa+1));
 163   }
 164   sname = &mrb->symtbl[sym];
 165   sname->len = (uint16_t)len;
 166   if (lit || mrb_ro_data_p(name)) {
 167     sname->name = name;
 168     sname->lit = TRUE;
 169   }
 170   else {
 171     char *p = (char *)mrb_malloc(mrb, len+1);
 172     memcpy(p, name, len);
 173     p[len] = 0;
 174     sname->name = (const char*)p;
 175     sname->lit = FALSE;
 176   }
 177   if (mrb->symhash[hash]) {
 178     mrb_sym i = sym - mrb->symhash[hash];
 179     if (i > 0xff)
 180       sname->prev = 0xff;
 181     else
 182       sname->prev = i;
 183   }
 184   else {
 185     sname->prev = 0;
 186   }
 187   mrb->symhash[hash] = sym;
 188
 189   return sym<<1;
 190 }
 191
 192 MRB_API mrb_sym
 193 mrb_intern(mrb_state *mrb, const char *name, size_t len)
 194 {
 195   return sym_intern(mrb, name, len, FALSE);
 196 }
 197
 198 MRB_API mrb_sym
 199 mrb_intern_static(mrb_state *mrb, const char *name, size_t len)
 200 {
 201   return sym_intern(mrb, name, len, TRUE);
 202 }
 203
 204 MRB_API mrb_sym
 205 mrb_intern_cstr(mrb_state *mrb, const char *name)
 206 {
 207   return mrb_intern(mrb, name, strlen(name));
 208 }
 209
 210 MRB_API mrb_sym
 211 mrb_intern_str(mrb_state *mrb, mrb_value str)
 212 {
 213   return mrb_intern(mrb, RSTRING_PTR(str), RSTRING_LEN(str));
 214 }
 215
 216 MRB_API mrb_value
 217 mrb_check_intern(mrb_state *mrb, const char *name, size_t len)
 218 {
 219   mrb_sym sym;
 220
 221   sym_validate_len(mrb, len);
 222   sym = find_symbol(mrb, name, len, symhash(name, len));
 223   if (sym > 0) return mrb_symbol_value(sym);
 224   return mrb_nil_value();
 225 }
 226
 227 MRB_API mrb_value
 228 mrb_check_intern_cstr(mrb_state *mrb, const char *name)
 229 {
 230   return mrb_check_intern(mrb, name, strlen(name));
 231 }
 232
 233 MRB_API mrb_value
 234 mrb_check_intern_str(mrb_state *mrb, mrb_value str)
 235 {
 236   return mrb_check_intern(mrb, RSTRING_PTR(str), RSTRING_LEN(str));
 237 }
 238
 239 static const char*
 240 sym2name_len(mrb_state *mrb, mrb_sym sym, char *buf, mrb_int *lenp)
 241 {
 242 #ifndef MRB_ENABLE_ALL_SYMBOLS
 243   if (sym & 1) {                /* inline packed symbol */
 244     return sym_inline_unpack(sym, buf, lenp);
 245   }
 246 #endif
 247
 248   sym >>= 1;
 249   if (sym == 0 || mrb->symidx < sym) {
 250     if (lenp) *lenp = 0;
 251     return NULL;
 252   }
 253
 254   if (lenp) *lenp = mrb->symtbl[sym].len;
 255   return mrb->symtbl[sym].name;
 256 }
 257
 258 MRB_API const char*
 259 mrb_sym2name_len(mrb_state *mrb, mrb_sym sym, mrb_int *lenp)
 260 {
 261   return sym2name_len(mrb, sym, mrb->symbuf, lenp);
 262 }
 263
 264 void
 265 mrb_free_symtbl(mrb_state *mrb)
 266 {
 267   mrb_sym i, lim;
 268
 269   for (i=1, lim=mrb->symidx+1; i<lim; i++) {
 270     if (!mrb->symtbl[i].lit) {
 271       mrb_free(mrb, (char*)mrb->symtbl[i].name);
 272     }
 273   }
 274   mrb_free(mrb, mrb->symtbl);
 275 }
 276
 277 void
 278 mrb_init_symtbl(mrb_state *mrb)
 279 {
 280 }
 281
 282 /**********************************************************************
 283  * Document-class: Symbol
 284  *
 285  *  <code>Symbol</code> objects represent names and some strings
 286  *  inside the Ruby
 287  *  interpreter. They are generated using the <code>:name</code> and
 288  *  <code>:"string"</code> literals
 289  *  syntax, and by the various <code>to_sym</code> methods. The same
 290  *  <code>Symbol</code> object will be created for a given name or string
 291  *  for the duration of a program's execution, regardless of the context
 292  *  or meaning of that name. Thus if <code>Fred</code> is a constant in
 293  *  one context, a method in another, and a class in a third, the
 294  *  <code>Symbol</code> <code>:Fred</code> will be the same object in
 295  *  all three contexts.
 296  *
 297  *     module One
 298  *       class Fred
 299  *       end
 300  *       $f1 = :Fred
 301  *     end
 302  *     module Two
 303  *       Fred = 1
 304  *       $f2 = :Fred
 305  *     end
 306  *     def Fred()
 307  *     end
 308  *     $f3 = :Fred
 309  *     $f1.object_id   #=> 2514190
 310  *     $f2.object_id   #=> 2514190
 311  *     $f3.object_id   #=> 2514190
 312  *
 313  */
 314
 315 /* 15.2.11.3.2  */
 316 /* 15.2.11.3.3  */
 317 /*
 318  *  call-seq:
 319  *     sym.id2name   -> string
 320  *     sym.to_s      -> string
 321  *
 322  *  Returns the name or string corresponding to <i>sym</i>.
 323  *
 324  *     :fred.id2name   #=> "fred"
 325  */
 326 static mrb_value
 327 sym_to_s(mrb_state *mrb, mrb_value sym)
 328 {
 329   return mrb_sym2str(mrb, mrb_symbol(sym));
 330 }
 331
 332 /* 15.2.11.3.4  */
 333 /*
 334  * call-seq:
 335  *   sym.to_sym   -> sym
 336  *   sym.intern   -> sym
 337  *
 338  * In general, <code>to_sym</code> returns the <code>Symbol</code> corresponding
 339  * to an object. As <i>sym</i> is already a symbol, <code>self</code> is returned
 340  * in this case.
 341  */
 342
 343 static mrb_value
 344 sym_to_sym(mrb_state *mrb, mrb_value sym)
 345 {
 346   return sym;
 347 }
 348
 349 /* 15.2.11.3.5(x)  */
 350 /*
 351  *  call-seq:
 352  *     sym.inspect    -> string
 353  *
 354  *  Returns the representation of <i>sym</i> as a symbol literal.
 355  *
 356  *     :fred.inspect   #=> ":fred"
 357  */
 358
 359 #if __STDC__
 360 # define SIGN_EXTEND_CHAR(c) ((signed char)(c))
 361 #else  /* not __STDC__ */
 362 /* As in Harbison and Steele.  */
 363 # define SIGN_EXTEND_CHAR(c) ((((unsigned char)(c)) ^ 128) - 128)
 364 #endif
 365 #define is_identchar(c) (SIGN_EXTEND_CHAR(c)!=-1&&(ISALNUM(c) || (c) == '_'))
 366
 367 static mrb_bool
 368 is_special_global_name(const char* m)
 369 {
 370   switch (*m) {
 371     case '~': case '*': case '$': case '?': case '!': case '@':
 372     case '/': case '\\': case ';': case ',': case '.': case '=':
 373     case ':': case '<': case '>': case '\"':
 374     case '&': case '`': case '\'': case '+':
 375     case '0':
 376       ++m;
 377       break;
 378     case '-':
 379       ++m;
 380       if (is_identchar(*m)) m += 1;
 381       break;
 382     default:
 383       if (!ISDIGIT(*m)) return FALSE;
 384       do ++m; while (ISDIGIT(*m));
 385       break;
 386   }
 387   return !*m;
 388 }
 389
 390 static mrb_bool
 391 symname_p(const char *name)
 392 {
 393   const char *m = name;
 394   mrb_bool localid = FALSE;
 395
 396   if (!m) return FALSE;
 397   switch (*m) {
 398     case '\0':
 399       return FALSE;
 400
 401     case '$':
 402       if (is_special_global_name(++m)) return TRUE;
 403       goto id;
 404
 405     case '@':
 406       if (*++m == '@') ++m;
 407       goto id;
 408
 409     case '<':
 410       switch (*++m) {
 411         case '<': ++m; break;
 412         case '=': if (*++m == '>') ++m; break;
 413         default: break;
 414       }
 415       break;
 416
 417     case '>':
 418       switch (*++m) {
 419         case '>': case '=': ++m; break;
 420         default: break;
 421       }
 422       break;
 423
 424     case '=':
 425       switch (*++m) {
 426         case '~': ++m; break;
 427         case '=': if (*++m == '=') ++m; break;
 428         default: return FALSE;
 429       }
 430       break;
 431
 432     case '*':
 433       if (*++m == '*') ++m;
 434       break;
 435     case '!':
 436       switch (*++m) {
 437         case '=': case '~': ++m;
 438       }
 439       break;
 440     case '+': case '-':
 441       if (*++m == '@') ++m;
 442       break;
 443     case '|':
 444       if (*++m == '|') ++m;
 445       break;
 446     case '&':
 447       if (*++m == '&') ++m;
 448       break;
 449
 450     case '^': case '/': case '%': case '~': case '`':
 451       ++m;
 452       break;
 453
 454     case '[':
 455       if (*++m != ']') return FALSE;
 456       if (*++m == '=') ++m;
 457       break;
 458
 459     default:
 460       localid = !ISUPPER(*m);
 461 id:
 462       if (*m != '_' && !ISALPHA(*m)) return FALSE;
 463       while (is_identchar(*m)) m += 1;
 464       if (localid) {
 465         switch (*m) {
 466           case '!': case '?': case '=': ++m;
 467           default: break;
 468         }
 469       }
 470       break;
 471   }
 472   return *m ? FALSE : TRUE;
 473 }
 474
 475 static mrb_value
 476 sym_inspect(mrb_state *mrb, mrb_value sym)
 477 {
 478   mrb_value str;
 479   const char *name;
 480   mrb_int len;
 481   mrb_sym id = mrb_symbol(sym);
 482   char *sp;
 483
 484   name = mrb_sym2name_len(mrb, id, &len);
 485   str = mrb_str_new(mrb, 0, len+1);
 486   sp = RSTRING_PTR(str);
 487   RSTRING_PTR(str)[0] = ':';
 488   memcpy(sp+1, name, len);
 489   mrb_assert_int_fit(mrb_int, len, size_t, SIZE_MAX);
 490   if (!symname_p(name) || strlen(name) != (size_t)len) {
 491     str = mrb_str_dump(mrb, str);
 492     sp = RSTRING_PTR(str);
 493     sp[0] = ':';
 494     sp[1] = '"';
 495   }
 496   return str;
 497 }
 498
 499 MRB_API mrb_value
 500 mrb_sym2str(mrb_state *mrb, mrb_sym sym)
 501 {
 502   mrb_int len;
 503   const char *name = mrb_sym2name_len(mrb, sym, &len);
 504
 505   if (!name) return mrb_undef_value(); /* can't happen */
 506   if (sym&1) {                         /* inline symbol */
 507     return mrb_str_new(mrb, name, len);
 508   }
 509   return mrb_str_new_static(mrb, name, len);
 510 }
 511
 512 MRB_API const char*
 513 mrb_sym2name(mrb_state *mrb, mrb_sym sym)
 514 {
 515   mrb_int len;
 516   const char *name = mrb_sym2name_len(mrb, sym, &len);
 517
 518   if (!name) return NULL;
 519   if (symname_p(name) && strlen(name) == (size_t)len) {
 520     return name;
 521   }
 522   else {
 523     mrb_value str;
 524     if (sym&1) {                /* inline symbol */
 525       str = mrb_str_new(mrb, name, len);
 526     }
 527     else {
 528       str = mrb_str_new_static(mrb, name, len);
 529     }
 530     str = mrb_str_dump(mrb, str);
 531     return RSTRING_PTR(str);
 532   }
 533 }
 534
 535 #define lesser(a,b) (((a)>(b))?(b):(a))
 536
 537 static mrb_value
 538 sym_cmp(mrb_state *mrb, mrb_value s1)
 539 {
 540   mrb_value s2;
 541   mrb_sym sym1, sym2;
 542
 543   mrb_get_args(mrb, "o", &s2);
 544   if (mrb_type(s2) != MRB_TT_SYMBOL) return mrb_nil_value();
 545   sym1 = mrb_symbol(s1);
 546   sym2 = mrb_symbol(s2);
 547   if (sym1 == sym2) return mrb_fixnum_value(0);
 548   else {
 549     const char *p1, *p2;
 550     int retval;
 551     mrb_int len, len1, len2;
 552     char buf1[8], buf2[8];
 553
 554     p1 = sym2name_len(mrb, sym1, buf1, &len1);
 555     p2 = sym2name_len(mrb, sym2, buf2, &len2);
 556     len = lesser(len1, len2);
 557     retval = memcmp(p1, p2, len);
 558     if (retval == 0) {
 559       if (len1 == len2) return mrb_fixnum_value(0);
 560       if (len1 > len2)  return mrb_fixnum_value(1);
 561       return mrb_fixnum_value(-1);
 562     }
 563     if (retval > 0) return mrb_fixnum_value(1);
 564     return mrb_fixnum_value(-1);
 565   }
 566 }
 567
 568 void
 569 mrb_init_symbol(mrb_state *mrb)
 570 {
 571   struct RClass *sym;
 572
 573   mrb->symbol_class = sym = mrb_define_class(mrb, "Symbol", mrb->object_class);  /* 15.2.11 */
 574   MRB_SET_INSTANCE_TT(sym, MRB_TT_SYMBOL);
 575   mrb_undef_class_method(mrb,  sym, "new");
 576
 577   mrb_define_method(mrb, sym, "id2name", sym_to_s,    MRB_ARGS_NONE());          /* 15.2.11.3.2 */
 578   mrb_define_method(mrb, sym, "to_s",    sym_to_s,    MRB_ARGS_NONE());          /* 15.2.11.3.3 */
 579   mrb_define_method(mrb, sym, "to_sym",  sym_to_sym,  MRB_ARGS_NONE());          /* 15.2.11.3.4 */
 580   mrb_define_method(mrb, sym, "inspect", sym_inspect, MRB_ARGS_NONE());          /* 15.2.11.3.5(x) */
 581   mrb_define_method(mrb, sym, "<=>",     sym_cmp,     MRB_ARGS_REQ(1));
 582 }