lstrlib.c (57546B)
1 /* 2 ** $Id: lstrlib.c $ 3 ** Standard library for string operations and pattern-matching 4 ** See Copyright Notice in lua.h 5 */ 6 7 #define lstrlib_c 8 #define LUA_LIB 9 10 #include "lprefix.h" 11 12 13 #include <ctype.h> 14 #include <float.h> 15 #include <limits.h> 16 #include <locale.h> 17 #include <math.h> 18 #include <stddef.h> 19 #include <stdio.h> 20 #include <stdlib.h> 21 #include <string.h> 22 23 #include "lua.h" 24 25 #include "lauxlib.h" 26 #include "lualib.h" 27 #include "llimits.h" 28 29 30 /* 31 ** maximum number of captures that a pattern can do during 32 ** pattern-matching. This limit is arbitrary, but must fit in 33 ** an unsigned char. 34 */ 35 #if !defined(LUA_MAXCAPTURES) 36 #define LUA_MAXCAPTURES 32 37 #endif 38 39 40 static int str_len (lua_State *L) { 41 size_t l; 42 luaL_checklstring(L, 1, &l); 43 lua_pushinteger(L, (lua_Integer)l); 44 return 1; 45 } 46 47 48 /* 49 ** translate a relative initial string position 50 ** (negative means back from end): clip result to [1, inf). 51 ** The length of any string in Lua must fit in a lua_Integer, 52 ** so there are no overflows in the casts. 53 ** The inverted comparison avoids a possible overflow 54 ** computing '-pos'. 55 */ 56 static size_t posrelatI (lua_Integer pos, size_t len) { 57 if (pos > 0) 58 return (size_t)pos; 59 else if (pos == 0) 60 return 1; 61 else if (pos < -(lua_Integer)len) /* inverted comparison */ 62 return 1; /* clip to 1 */ 63 else return len + (size_t)pos + 1; 64 } 65 66 67 /* 68 ** Gets an optional ending string position from argument 'arg', 69 ** with default value 'def'. 70 ** Negative means back from end: clip result to [0, len] 71 */ 72 static size_t getendpos (lua_State *L, int arg, lua_Integer def, 73 size_t len) { 74 lua_Integer pos = luaL_optinteger(L, arg, def); 75 if (pos > (lua_Integer)len) 76 return len; 77 else if (pos >= 0) 78 return (size_t)pos; 79 else if (pos < -(lua_Integer)len) 80 return 0; 81 else return len + (size_t)pos + 1; 82 } 83 84 85 static int str_sub (lua_State *L) { 86 size_t l; 87 const char *s = luaL_checklstring(L, 1, &l); 88 size_t start = posrelatI(luaL_checkinteger(L, 2), l); 89 size_t end = getendpos(L, 3, -1, l); 90 if (start <= end) 91 lua_pushlstring(L, s + start - 1, (end - start) + 1); 92 else lua_pushliteral(L, ""); 93 return 1; 94 } 95 96 97 static int str_reverse (lua_State *L) { 98 size_t l, i; 99 luaL_Buffer b; 100 const char *s = luaL_checklstring(L, 1, &l); 101 char *p = luaL_buffinitsize(L, &b, l); 102 for (i = 0; i < l; i++) 103 p[i] = s[l - i - 1]; 104 luaL_pushresultsize(&b, l); 105 return 1; 106 } 107 108 109 static int str_lower (lua_State *L) { 110 size_t l; 111 size_t i; 112 luaL_Buffer b; 113 const char *s = luaL_checklstring(L, 1, &l); 114 char *p = luaL_buffinitsize(L, &b, l); 115 for (i=0; i<l; i++) 116 p[i] = cast_char(tolower(cast_uchar(s[i]))); 117 luaL_pushresultsize(&b, l); 118 return 1; 119 } 120 121 122 static int str_upper (lua_State *L) { 123 size_t l; 124 size_t i; 125 luaL_Buffer b; 126 const char *s = luaL_checklstring(L, 1, &l); 127 char *p = luaL_buffinitsize(L, &b, l); 128 for (i=0; i<l; i++) 129 p[i] = cast_char(toupper(cast_uchar(s[i]))); 130 luaL_pushresultsize(&b, l); 131 return 1; 132 } 133 134 135 static int str_rep (lua_State *L) { 136 size_t l, lsep; 137 const char *s = luaL_checklstring(L, 1, &l); 138 lua_Integer n = luaL_checkinteger(L, 2); 139 const char *sep = luaL_optlstring(L, 3, "", &lsep); 140 if (n <= 0) 141 lua_pushliteral(L, ""); 142 else if (l_unlikely(l + lsep < l || l + lsep > MAX_SIZE / cast_sizet(n))) 143 return luaL_error(L, "resulting string too large"); 144 else { 145 size_t totallen = ((size_t)n * (l + lsep)) - lsep; 146 luaL_Buffer b; 147 char *p = luaL_buffinitsize(L, &b, totallen); 148 while (n-- > 1) { /* first n-1 copies (followed by separator) */ 149 memcpy(p, s, l * sizeof(char)); p += l; 150 if (lsep > 0) { /* empty 'memcpy' is not that cheap */ 151 memcpy(p, sep, lsep * sizeof(char)); 152 p += lsep; 153 } 154 } 155 memcpy(p, s, l * sizeof(char)); /* last copy (not followed by separator) */ 156 luaL_pushresultsize(&b, totallen); 157 } 158 return 1; 159 } 160 161 162 static int str_byte (lua_State *L) { 163 size_t l; 164 const char *s = luaL_checklstring(L, 1, &l); 165 lua_Integer pi = luaL_optinteger(L, 2, 1); 166 size_t posi = posrelatI(pi, l); 167 size_t pose = getendpos(L, 3, pi, l); 168 int n, i; 169 if (posi > pose) return 0; /* empty interval; return no values */ 170 if (l_unlikely(pose - posi >= (size_t)INT_MAX)) /* arithmetic overflow? */ 171 return luaL_error(L, "string slice too long"); 172 n = (int)(pose - posi) + 1; 173 luaL_checkstack(L, n, "string slice too long"); 174 for (i=0; i<n; i++) 175 lua_pushinteger(L, cast_uchar(s[posi + cast_uint(i) - 1])); 176 return n; 177 } 178 179 180 static int str_char (lua_State *L) { 181 int n = lua_gettop(L); /* number of arguments */ 182 int i; 183 luaL_Buffer b; 184 char *p = luaL_buffinitsize(L, &b, cast_uint(n)); 185 for (i=1; i<=n; i++) { 186 lua_Unsigned c = (lua_Unsigned)luaL_checkinteger(L, i); 187 luaL_argcheck(L, c <= (lua_Unsigned)UCHAR_MAX, i, "value out of range"); 188 p[i - 1] = cast_char(cast_uchar(c)); 189 } 190 luaL_pushresultsize(&b, cast_uint(n)); 191 return 1; 192 } 193 194 195 /* 196 ** Buffer to store the result of 'string.dump'. It must be initialized 197 ** after the call to 'lua_dump', to ensure that the function is on the 198 ** top of the stack when 'lua_dump' is called. ('luaL_buffinit' might 199 ** push stuff.) 200 */ 201 struct str_Writer { 202 int init; /* true iff buffer has been initialized */ 203 luaL_Buffer B; 204 }; 205 206 207 static int writer (lua_State *L, const void *b, size_t size, void *ud) { 208 struct str_Writer *state = (struct str_Writer *)ud; 209 if (!state->init) { 210 state->init = 1; 211 luaL_buffinit(L, &state->B); 212 } 213 if (b == NULL) { /* finishing dump? */ 214 luaL_pushresult(&state->B); /* push result */ 215 lua_replace(L, 1); /* move it to reserved slot */ 216 } 217 else 218 luaL_addlstring(&state->B, (const char *)b, size); 219 return 0; 220 } 221 222 223 static int str_dump (lua_State *L) { 224 struct str_Writer state; 225 int strip = lua_toboolean(L, 2); 226 luaL_argcheck(L, lua_type(L, 1) == LUA_TFUNCTION && !lua_iscfunction(L, 1), 227 1, "Lua function expected"); 228 /* ensure function is on the top of the stack and vacate slot 1 */ 229 lua_pushvalue(L, 1); 230 state.init = 0; 231 lua_dump(L, writer, &state, strip); 232 lua_settop(L, 1); /* leave final result on top */ 233 return 1; 234 } 235 236 237 238 /* 239 ** {====================================================== 240 ** METAMETHODS 241 ** ======================================================= 242 */ 243 244 #if defined(LUA_NOCVTS2N) /* { */ 245 246 /* no coercion from strings to numbers */ 247 248 static const luaL_Reg stringmetamethods[] = { 249 {"__index", NULL}, /* placeholder */ 250 {NULL, NULL} 251 }; 252 253 #else /* }{ */ 254 255 static int tonum (lua_State *L, int arg) { 256 if (lua_type(L, arg) == LUA_TNUMBER) { /* already a number? */ 257 lua_pushvalue(L, arg); 258 return 1; 259 } 260 else { /* check whether it is a numerical string */ 261 size_t len; 262 const char *s = lua_tolstring(L, arg, &len); 263 return (s != NULL && lua_stringtonumber(L, s) == len + 1); 264 } 265 } 266 267 268 static void trymt (lua_State *L, const char *mtname) { 269 lua_settop(L, 2); /* back to the original arguments */ 270 if (l_unlikely(lua_type(L, 2) == LUA_TSTRING || 271 !luaL_getmetafield(L, 2, mtname))) 272 luaL_error(L, "attempt to %s a '%s' with a '%s'", mtname + 2, 273 luaL_typename(L, -2), luaL_typename(L, -1)); 274 lua_insert(L, -3); /* put metamethod before arguments */ 275 lua_call(L, 2, 1); /* call metamethod */ 276 } 277 278 279 static int arith (lua_State *L, int op, const char *mtname) { 280 if (tonum(L, 1) && tonum(L, 2)) 281 lua_arith(L, op); /* result will be on the top */ 282 else 283 trymt(L, mtname); 284 return 1; 285 } 286 287 288 static int arith_add (lua_State *L) { 289 return arith(L, LUA_OPADD, "__add"); 290 } 291 292 static int arith_sub (lua_State *L) { 293 return arith(L, LUA_OPSUB, "__sub"); 294 } 295 296 static int arith_mul (lua_State *L) { 297 return arith(L, LUA_OPMUL, "__mul"); 298 } 299 300 static int arith_mod (lua_State *L) { 301 return arith(L, LUA_OPMOD, "__mod"); 302 } 303 304 static int arith_pow (lua_State *L) { 305 return arith(L, LUA_OPPOW, "__pow"); 306 } 307 308 static int arith_div (lua_State *L) { 309 return arith(L, LUA_OPDIV, "__div"); 310 } 311 312 static int arith_idiv (lua_State *L) { 313 return arith(L, LUA_OPIDIV, "__idiv"); 314 } 315 316 static int arith_unm (lua_State *L) { 317 return arith(L, LUA_OPUNM, "__unm"); 318 } 319 320 321 static const luaL_Reg stringmetamethods[] = { 322 {"__add", arith_add}, 323 {"__sub", arith_sub}, 324 {"__mul", arith_mul}, 325 {"__mod", arith_mod}, 326 {"__pow", arith_pow}, 327 {"__div", arith_div}, 328 {"__idiv", arith_idiv}, 329 {"__unm", arith_unm}, 330 {"__index", NULL}, /* placeholder */ 331 {NULL, NULL} 332 }; 333 334 #endif /* } */ 335 336 /* }====================================================== */ 337 338 /* 339 ** {====================================================== 340 ** PATTERN MATCHING 341 ** ======================================================= 342 */ 343 344 345 #define CAP_UNFINISHED (-1) 346 #define CAP_POSITION (-2) 347 348 349 typedef struct MatchState { 350 const char *src_init; /* init of source string */ 351 const char *src_end; /* end ('\0') of source string */ 352 const char *p_end; /* end ('\0') of pattern */ 353 lua_State *L; 354 int matchdepth; /* control for recursive depth (to avoid C stack overflow) */ 355 int level; /* total number of captures (finished or unfinished) */ 356 struct { 357 const char *init; 358 ptrdiff_t len; /* length or special value (CAP_*) */ 359 } capture[LUA_MAXCAPTURES]; 360 } MatchState; 361 362 363 /* recursive function */ 364 static const char *match (MatchState *ms, const char *s, const char *p); 365 366 367 /* maximum recursion depth for 'match' */ 368 #if !defined(MAXCCALLS) 369 #define MAXCCALLS 200 370 #endif 371 372 373 #define L_ESC '%' 374 #define SPECIALS "^$*+?.([%-" 375 376 377 static int check_capture (MatchState *ms, int l) { 378 l -= '1'; 379 if (l_unlikely(l < 0 || l >= ms->level || 380 ms->capture[l].len == CAP_UNFINISHED)) 381 return luaL_error(ms->L, "invalid capture index %%%d", l + 1); 382 return l; 383 } 384 385 386 static int capture_to_close (MatchState *ms) { 387 int level = ms->level; 388 for (level--; level>=0; level--) 389 if (ms->capture[level].len == CAP_UNFINISHED) return level; 390 return luaL_error(ms->L, "invalid pattern capture"); 391 } 392 393 394 static const char *classend (MatchState *ms, const char *p) { 395 switch (*p++) { 396 case L_ESC: { 397 if (l_unlikely(p == ms->p_end)) 398 luaL_error(ms->L, "malformed pattern (ends with '%%')"); 399 return p+1; 400 } 401 case '[': { 402 if (*p == '^') p++; 403 do { /* look for a ']' */ 404 if (l_unlikely(p == ms->p_end)) 405 luaL_error(ms->L, "malformed pattern (missing ']')"); 406 if (*(p++) == L_ESC && p < ms->p_end) 407 p++; /* skip escapes (e.g. '%]') */ 408 } while (*p != ']'); 409 return p+1; 410 } 411 default: { 412 return p; 413 } 414 } 415 } 416 417 418 static int match_class (int c, int cl) { 419 int res; 420 switch (tolower(cl)) { 421 case 'a' : res = isalpha(c); break; 422 case 'c' : res = iscntrl(c); break; 423 case 'd' : res = isdigit(c); break; 424 case 'g' : res = isgraph(c); break; 425 case 'l' : res = islower(c); break; 426 case 'p' : res = ispunct(c); break; 427 case 's' : res = isspace(c); break; 428 case 'u' : res = isupper(c); break; 429 case 'w' : res = isalnum(c); break; 430 case 'x' : res = isxdigit(c); break; 431 case 'z' : res = (c == 0); break; /* deprecated option */ 432 default: return (cl == c); 433 } 434 return (islower(cl) ? res : !res); 435 } 436 437 438 static int matchbracketclass (int c, const char *p, const char *ec) { 439 int sig = 1; 440 if (*(p+1) == '^') { 441 sig = 0; 442 p++; /* skip the '^' */ 443 } 444 while (++p < ec) { 445 if (*p == L_ESC) { 446 p++; 447 if (match_class(c, cast_uchar(*p))) 448 return sig; 449 } 450 else if ((*(p+1) == '-') && (p+2 < ec)) { 451 p+=2; 452 if (cast_uchar(*(p-2)) <= c && c <= cast_uchar(*p)) 453 return sig; 454 } 455 else if (cast_uchar(*p) == c) return sig; 456 } 457 return !sig; 458 } 459 460 461 static int singlematch (MatchState *ms, const char *s, const char *p, 462 const char *ep) { 463 if (s >= ms->src_end) 464 return 0; 465 else { 466 int c = cast_uchar(*s); 467 switch (*p) { 468 case '.': return 1; /* matches any char */ 469 case L_ESC: return match_class(c, cast_uchar(*(p+1))); 470 case '[': return matchbracketclass(c, p, ep-1); 471 default: return (cast_uchar(*p) == c); 472 } 473 } 474 } 475 476 477 static const char *matchbalance (MatchState *ms, const char *s, 478 const char *p) { 479 if (l_unlikely(p >= ms->p_end - 1)) 480 luaL_error(ms->L, "malformed pattern (missing arguments to '%%b')"); 481 if (*s != *p) return NULL; 482 else { 483 int b = *p; 484 int e = *(p+1); 485 int cont = 1; 486 while (++s < ms->src_end) { 487 if (*s == e) { 488 if (--cont == 0) return s+1; 489 } 490 else if (*s == b) cont++; 491 } 492 } 493 return NULL; /* string ends out of balance */ 494 } 495 496 497 static const char *max_expand (MatchState *ms, const char *s, 498 const char *p, const char *ep) { 499 ptrdiff_t i = 0; /* counts maximum expand for item */ 500 while (singlematch(ms, s + i, p, ep)) 501 i++; 502 /* keeps trying to match with the maximum repetitions */ 503 while (i>=0) { 504 const char *res = match(ms, (s+i), ep+1); 505 if (res) return res; 506 i--; /* else didn't match; reduce 1 repetition to try again */ 507 } 508 return NULL; 509 } 510 511 512 static const char *min_expand (MatchState *ms, const char *s, 513 const char *p, const char *ep) { 514 for (;;) { 515 const char *res = match(ms, s, ep+1); 516 if (res != NULL) 517 return res; 518 else if (singlematch(ms, s, p, ep)) 519 s++; /* try with one more repetition */ 520 else return NULL; 521 } 522 } 523 524 525 static const char *start_capture (MatchState *ms, const char *s, 526 const char *p, int what) { 527 const char *res; 528 int level = ms->level; 529 if (level >= LUA_MAXCAPTURES) luaL_error(ms->L, "too many captures"); 530 ms->capture[level].init = s; 531 ms->capture[level].len = what; 532 ms->level = level+1; 533 if ((res=match(ms, s, p)) == NULL) /* match failed? */ 534 ms->level--; /* undo capture */ 535 return res; 536 } 537 538 539 static const char *end_capture (MatchState *ms, const char *s, 540 const char *p) { 541 int l = capture_to_close(ms); 542 const char *res; 543 ms->capture[l].len = s - ms->capture[l].init; /* close capture */ 544 if ((res = match(ms, s, p)) == NULL) /* match failed? */ 545 ms->capture[l].len = CAP_UNFINISHED; /* undo capture */ 546 return res; 547 } 548 549 550 static const char *match_capture (MatchState *ms, const char *s, int l) { 551 size_t len; 552 l = check_capture(ms, l); 553 len = cast_sizet(ms->capture[l].len); 554 if ((size_t)(ms->src_end-s) >= len && 555 memcmp(ms->capture[l].init, s, len) == 0) 556 return s+len; 557 else return NULL; 558 } 559 560 561 static const char *match (MatchState *ms, const char *s, const char *p) { 562 if (l_unlikely(ms->matchdepth-- == 0)) 563 luaL_error(ms->L, "pattern too complex"); 564 init: /* using goto to optimize tail recursion */ 565 if (p != ms->p_end) { /* end of pattern? */ 566 switch (*p) { 567 case '(': { /* start capture */ 568 if (*(p + 1) == ')') /* position capture? */ 569 s = start_capture(ms, s, p + 2, CAP_POSITION); 570 else 571 s = start_capture(ms, s, p + 1, CAP_UNFINISHED); 572 break; 573 } 574 case ')': { /* end capture */ 575 s = end_capture(ms, s, p + 1); 576 break; 577 } 578 case '$': { 579 if ((p + 1) != ms->p_end) /* is the '$' the last char in pattern? */ 580 goto dflt; /* no; go to default */ 581 s = (s == ms->src_end) ? s : NULL; /* check end of string */ 582 break; 583 } 584 case L_ESC: { /* escaped sequences not in the format class[*+?-]? */ 585 switch (*(p + 1)) { 586 case 'b': { /* balanced string? */ 587 s = matchbalance(ms, s, p + 2); 588 if (s != NULL) { 589 p += 4; goto init; /* return match(ms, s, p + 4); */ 590 } /* else fail (s == NULL) */ 591 break; 592 } 593 case 'f': { /* frontier? */ 594 const char *ep; char previous; 595 p += 2; 596 if (l_unlikely(*p != '[')) 597 luaL_error(ms->L, "missing '[' after '%%f' in pattern"); 598 ep = classend(ms, p); /* points to what is next */ 599 previous = (s == ms->src_init) ? '\0' : *(s - 1); 600 if (!matchbracketclass(cast_uchar(previous), p, ep - 1) && 601 matchbracketclass(cast_uchar(*s), p, ep - 1)) { 602 p = ep; goto init; /* return match(ms, s, ep); */ 603 } 604 s = NULL; /* match failed */ 605 break; 606 } 607 case '0': case '1': case '2': case '3': 608 case '4': case '5': case '6': case '7': 609 case '8': case '9': { /* capture results (%0-%9)? */ 610 s = match_capture(ms, s, cast_uchar(*(p + 1))); 611 if (s != NULL) { 612 p += 2; goto init; /* return match(ms, s, p + 2) */ 613 } 614 break; 615 } 616 default: goto dflt; 617 } 618 break; 619 } 620 default: dflt: { /* pattern class plus optional suffix */ 621 const char *ep = classend(ms, p); /* points to optional suffix */ 622 /* does not match at least once? */ 623 if (!singlematch(ms, s, p, ep)) { 624 if (*ep == '*' || *ep == '?' || *ep == '-') { /* accept empty? */ 625 p = ep + 1; goto init; /* return match(ms, s, ep + 1); */ 626 } 627 else /* '+' or no suffix */ 628 s = NULL; /* fail */ 629 } 630 else { /* matched once */ 631 switch (*ep) { /* handle optional suffix */ 632 case '?': { /* optional */ 633 const char *res; 634 if ((res = match(ms, s + 1, ep + 1)) != NULL) 635 s = res; 636 else { 637 p = ep + 1; goto init; /* else return match(ms, s, ep + 1); */ 638 } 639 break; 640 } 641 case '+': /* 1 or more repetitions */ 642 s++; /* 1 match already done */ 643 /* FALLTHROUGH */ 644 case '*': /* 0 or more repetitions */ 645 s = max_expand(ms, s, p, ep); 646 break; 647 case '-': /* 0 or more repetitions (minimum) */ 648 s = min_expand(ms, s, p, ep); 649 break; 650 default: /* no suffix */ 651 s++; p = ep; goto init; /* return match(ms, s + 1, ep); */ 652 } 653 } 654 break; 655 } 656 } 657 } 658 ms->matchdepth++; 659 return s; 660 } 661 662 663 664 static const char *lmemfind (const char *s1, size_t l1, 665 const char *s2, size_t l2) { 666 if (l2 == 0) return s1; /* empty strings are everywhere */ 667 else if (l2 > l1) return NULL; /* avoids a negative 'l1' */ 668 else { 669 const char *init; /* to search for a '*s2' inside 's1' */ 670 l2--; /* 1st char will be checked by 'memchr' */ 671 l1 = l1-l2; /* 's2' cannot be found after that */ 672 while (l1 > 0 && (init = (const char *)memchr(s1, *s2, l1)) != NULL) { 673 init++; /* 1st char is already checked */ 674 if (memcmp(init, s2+1, l2) == 0) 675 return init-1; 676 else { /* correct 'l1' and 's1' to try again */ 677 l1 -= ct_diff2sz(init - s1); 678 s1 = init; 679 } 680 } 681 return NULL; /* not found */ 682 } 683 } 684 685 686 /* 687 ** get information about the i-th capture. If there are no captures 688 ** and 'i==0', return information about the whole match, which 689 ** is the range 's'..'e'. If the capture is a string, return 690 ** its length and put its address in '*cap'. If it is an integer 691 ** (a position), push it on the stack and return CAP_POSITION. 692 */ 693 static ptrdiff_t get_onecapture (MatchState *ms, int i, const char *s, 694 const char *e, const char **cap) { 695 if (i >= ms->level) { 696 if (l_unlikely(i != 0)) 697 luaL_error(ms->L, "invalid capture index %%%d", i + 1); 698 *cap = s; 699 return (e - s); 700 } 701 else { 702 ptrdiff_t capl = ms->capture[i].len; 703 *cap = ms->capture[i].init; 704 if (l_unlikely(capl == CAP_UNFINISHED)) 705 luaL_error(ms->L, "unfinished capture"); 706 else if (capl == CAP_POSITION) 707 lua_pushinteger(ms->L, 708 ct_diff2S(ms->capture[i].init - ms->src_init) + 1); 709 return capl; 710 } 711 } 712 713 714 /* 715 ** Push the i-th capture on the stack. 716 */ 717 static void push_onecapture (MatchState *ms, int i, const char *s, 718 const char *e) { 719 const char *cap; 720 ptrdiff_t l = get_onecapture(ms, i, s, e, &cap); 721 if (l != CAP_POSITION) 722 lua_pushlstring(ms->L, cap, cast_sizet(l)); 723 /* else position was already pushed */ 724 } 725 726 727 static int push_captures (MatchState *ms, const char *s, const char *e) { 728 int i; 729 int nlevels = (ms->level == 0 && s) ? 1 : ms->level; 730 luaL_checkstack(ms->L, nlevels, "too many captures"); 731 for (i = 0; i < nlevels; i++) 732 push_onecapture(ms, i, s, e); 733 return nlevels; /* number of strings pushed */ 734 } 735 736 737 /* check whether pattern has no special characters */ 738 static int nospecials (const char *p, size_t l) { 739 size_t upto = 0; 740 do { 741 if (strpbrk(p + upto, SPECIALS)) 742 return 0; /* pattern has a special character */ 743 upto += strlen(p + upto) + 1; /* may have more after \0 */ 744 } while (upto <= l); 745 return 1; /* no special chars found */ 746 } 747 748 749 static void prepstate (MatchState *ms, lua_State *L, 750 const char *s, size_t ls, const char *p, size_t lp) { 751 ms->L = L; 752 ms->matchdepth = MAXCCALLS; 753 ms->src_init = s; 754 ms->src_end = s + ls; 755 ms->p_end = p + lp; 756 } 757 758 759 static void reprepstate (MatchState *ms) { 760 ms->level = 0; 761 lua_assert(ms->matchdepth == MAXCCALLS); 762 } 763 764 765 static int str_find_aux (lua_State *L, int find) { 766 size_t ls, lp; 767 const char *s = luaL_checklstring(L, 1, &ls); 768 const char *p = luaL_checklstring(L, 2, &lp); 769 size_t init = posrelatI(luaL_optinteger(L, 3, 1), ls) - 1; 770 if (init > ls) { /* start after string's end? */ 771 luaL_pushfail(L); /* cannot find anything */ 772 return 1; 773 } 774 /* explicit request or no special characters? */ 775 if (find && (lua_toboolean(L, 4) || nospecials(p, lp))) { 776 /* do a plain search */ 777 const char *s2 = lmemfind(s + init, ls - init, p, lp); 778 if (s2) { 779 lua_pushinteger(L, ct_diff2S(s2 - s) + 1); 780 lua_pushinteger(L, cast_st2S(ct_diff2sz(s2 - s) + lp)); 781 return 2; 782 } 783 } 784 else { 785 MatchState ms; 786 const char *s1 = s + init; 787 int anchor = (*p == '^'); 788 if (anchor) { 789 p++; lp--; /* skip anchor character */ 790 } 791 prepstate(&ms, L, s, ls, p, lp); 792 do { 793 const char *res; 794 reprepstate(&ms); 795 if ((res=match(&ms, s1, p)) != NULL) { 796 if (find) { 797 lua_pushinteger(L, ct_diff2S(s1 - s) + 1); /* start */ 798 lua_pushinteger(L, ct_diff2S(res - s)); /* end */ 799 return push_captures(&ms, NULL, 0) + 2; 800 } 801 else 802 return push_captures(&ms, s1, res); 803 } 804 } while (s1++ < ms.src_end && !anchor); 805 } 806 luaL_pushfail(L); /* not found */ 807 return 1; 808 } 809 810 811 static int str_find (lua_State *L) { 812 return str_find_aux(L, 1); 813 } 814 815 816 static int str_match (lua_State *L) { 817 return str_find_aux(L, 0); 818 } 819 820 821 /* state for 'gmatch' */ 822 typedef struct GMatchState { 823 const char *src; /* current position */ 824 const char *p; /* pattern */ 825 const char *lastmatch; /* end of last match */ 826 MatchState ms; /* match state */ 827 } GMatchState; 828 829 830 static int gmatch_aux (lua_State *L) { 831 GMatchState *gm = (GMatchState *)lua_touserdata(L, lua_upvalueindex(3)); 832 const char *src; 833 gm->ms.L = L; 834 for (src = gm->src; src <= gm->ms.src_end; src++) { 835 const char *e; 836 reprepstate(&gm->ms); 837 if ((e = match(&gm->ms, src, gm->p)) != NULL && e != gm->lastmatch) { 838 gm->src = gm->lastmatch = e; 839 return push_captures(&gm->ms, src, e); 840 } 841 } 842 return 0; /* not found */ 843 } 844 845 846 static int gmatch (lua_State *L) { 847 size_t ls, lp; 848 const char *s = luaL_checklstring(L, 1, &ls); 849 const char *p = luaL_checklstring(L, 2, &lp); 850 size_t init = posrelatI(luaL_optinteger(L, 3, 1), ls) - 1; 851 GMatchState *gm; 852 lua_settop(L, 2); /* keep strings on closure to avoid being collected */ 853 gm = (GMatchState *)lua_newuserdatauv(L, sizeof(GMatchState), 0); 854 if (init > ls) /* start after string's end? */ 855 init = ls + 1; /* avoid overflows in 's + init' */ 856 prepstate(&gm->ms, L, s, ls, p, lp); 857 gm->src = s + init; gm->p = p; gm->lastmatch = NULL; 858 lua_pushcclosure(L, gmatch_aux, 3); 859 return 1; 860 } 861 862 863 static void add_s (MatchState *ms, luaL_Buffer *b, const char *s, 864 const char *e) { 865 size_t l; 866 lua_State *L = ms->L; 867 const char *news = lua_tolstring(L, 3, &l); 868 const char *p; 869 while ((p = (char *)memchr(news, L_ESC, l)) != NULL) { 870 luaL_addlstring(b, news, ct_diff2sz(p - news)); 871 p++; /* skip ESC */ 872 if (*p == L_ESC) /* '%%' */ 873 luaL_addchar(b, *p); 874 else if (*p == '0') /* '%0' */ 875 luaL_addlstring(b, s, ct_diff2sz(e - s)); 876 else if (isdigit(cast_uchar(*p))) { /* '%n' */ 877 const char *cap; 878 ptrdiff_t resl = get_onecapture(ms, *p - '1', s, e, &cap); 879 if (resl == CAP_POSITION) 880 luaL_addvalue(b); /* add position to accumulated result */ 881 else 882 luaL_addlstring(b, cap, cast_sizet(resl)); 883 } 884 else 885 luaL_error(L, "invalid use of '%c' in replacement string", L_ESC); 886 l -= ct_diff2sz(p + 1 - news); 887 news = p + 1; 888 } 889 luaL_addlstring(b, news, l); 890 } 891 892 893 /* 894 ** Add the replacement value to the string buffer 'b'. 895 ** Return true if the original string was changed. (Function calls and 896 ** table indexing resulting in nil or false do not change the subject.) 897 */ 898 static int add_value (MatchState *ms, luaL_Buffer *b, const char *s, 899 const char *e, int tr) { 900 lua_State *L = ms->L; 901 switch (tr) { 902 case LUA_TFUNCTION: { /* call the function */ 903 int n; 904 lua_pushvalue(L, 3); /* push the function */ 905 n = push_captures(ms, s, e); /* all captures as arguments */ 906 lua_call(L, n, 1); /* call it */ 907 break; 908 } 909 case LUA_TTABLE: { /* index the table */ 910 push_onecapture(ms, 0, s, e); /* first capture is the index */ 911 lua_gettable(L, 3); 912 break; 913 } 914 default: { /* LUA_TNUMBER or LUA_TSTRING */ 915 add_s(ms, b, s, e); /* add value to the buffer */ 916 return 1; /* something changed */ 917 } 918 } 919 if (!lua_toboolean(L, -1)) { /* nil or false? */ 920 lua_pop(L, 1); /* remove value */ 921 luaL_addlstring(b, s, ct_diff2sz(e - s)); /* keep original text */ 922 return 0; /* no changes */ 923 } 924 else if (l_unlikely(!lua_isstring(L, -1))) 925 return luaL_error(L, "invalid replacement value (a %s)", 926 luaL_typename(L, -1)); 927 else { 928 luaL_addvalue(b); /* add result to accumulator */ 929 return 1; /* something changed */ 930 } 931 } 932 933 934 static int str_gsub (lua_State *L) { 935 size_t srcl, lp; 936 const char *src = luaL_checklstring(L, 1, &srcl); /* subject */ 937 const char *p = luaL_checklstring(L, 2, &lp); /* pattern */ 938 const char *lastmatch = NULL; /* end of last match */ 939 int tr = lua_type(L, 3); /* replacement type */ 940 /* max replacements */ 941 lua_Integer max_s = luaL_optinteger(L, 4, cast_st2S(srcl) + 1); 942 int anchor = (*p == '^'); 943 lua_Integer n = 0; /* replacement count */ 944 int changed = 0; /* change flag */ 945 MatchState ms; 946 luaL_Buffer b; 947 luaL_argexpected(L, tr == LUA_TNUMBER || tr == LUA_TSTRING || 948 tr == LUA_TFUNCTION || tr == LUA_TTABLE, 3, 949 "string/function/table"); 950 luaL_buffinit(L, &b); 951 if (anchor) { 952 p++; lp--; /* skip anchor character */ 953 } 954 prepstate(&ms, L, src, srcl, p, lp); 955 while (n < max_s) { 956 const char *e; 957 reprepstate(&ms); /* (re)prepare state for new match */ 958 if ((e = match(&ms, src, p)) != NULL && e != lastmatch) { /* match? */ 959 n++; 960 changed = add_value(&ms, &b, src, e, tr) | changed; 961 src = lastmatch = e; 962 } 963 else if (src < ms.src_end) /* otherwise, skip one character */ 964 luaL_addchar(&b, *src++); 965 else break; /* end of subject */ 966 if (anchor) break; 967 } 968 if (!changed) /* no changes? */ 969 lua_pushvalue(L, 1); /* return original string */ 970 else { /* something changed */ 971 luaL_addlstring(&b, src, ct_diff2sz(ms.src_end - src)); 972 luaL_pushresult(&b); /* create and return new string */ 973 } 974 lua_pushinteger(L, n); /* number of substitutions */ 975 return 2; 976 } 977 978 /* }====================================================== */ 979 980 981 982 /* 983 ** {====================================================== 984 ** STRING FORMAT 985 ** ======================================================= 986 */ 987 988 #if !defined(lua_number2strx) /* { */ 989 990 /* 991 ** Hexadecimal floating-point formatter 992 */ 993 994 #define SIZELENMOD (sizeof(LUA_NUMBER_FRMLEN)/sizeof(char)) 995 996 997 /* 998 ** Number of bits that goes into the first digit. It can be any value 999 ** between 1 and 4; the following definition tries to align the number 1000 ** to nibble boundaries by making what is left after that first digit a 1001 ** multiple of 4. 1002 */ 1003 #define L_NBFD ((l_floatatt(MANT_DIG) - 1)%4 + 1) 1004 1005 1006 /* 1007 ** Add integer part of 'x' to buffer and return new 'x' 1008 */ 1009 static lua_Number adddigit (char *buff, unsigned n, lua_Number x) { 1010 lua_Number dd = l_mathop(floor)(x); /* get integer part from 'x' */ 1011 int d = (int)dd; 1012 buff[n] = cast_char(d < 10 ? d + '0' : d - 10 + 'a'); /* add to buffer */ 1013 return x - dd; /* return what is left */ 1014 } 1015 1016 1017 static int num2straux (char *buff, unsigned sz, lua_Number x) { 1018 /* if 'inf' or 'NaN', format it like '%g' */ 1019 if (x != x || x == (lua_Number)HUGE_VAL || x == -(lua_Number)HUGE_VAL) 1020 return l_sprintf(buff, sz, LUA_NUMBER_FMT, (LUAI_UACNUMBER)x); 1021 else if (x == 0) { /* can be -0... */ 1022 /* create "0" or "-0" followed by exponent */ 1023 return l_sprintf(buff, sz, LUA_NUMBER_FMT "x0p+0", (LUAI_UACNUMBER)x); 1024 } 1025 else { 1026 int e; 1027 lua_Number m = l_mathop(frexp)(x, &e); /* 'x' fraction and exponent */ 1028 unsigned n = 0; /* character count */ 1029 if (m < 0) { /* is number negative? */ 1030 buff[n++] = '-'; /* add sign */ 1031 m = -m; /* make it positive */ 1032 } 1033 buff[n++] = '0'; buff[n++] = 'x'; /* add "0x" */ 1034 m = adddigit(buff, n++, m * (1 << L_NBFD)); /* add first digit */ 1035 e -= L_NBFD; /* this digit goes before the radix point */ 1036 if (m > 0) { /* more digits? */ 1037 buff[n++] = lua_getlocaledecpoint(); /* add radix point */ 1038 do { /* add as many digits as needed */ 1039 m = adddigit(buff, n++, m * 16); 1040 } while (m > 0); 1041 } 1042 n += cast_uint(l_sprintf(buff + n, sz - n, "p%+d", e)); /* add exponent */ 1043 lua_assert(n < sz); 1044 return cast_int(n); 1045 } 1046 } 1047 1048 1049 static int lua_number2strx (lua_State *L, char *buff, unsigned sz, 1050 const char *fmt, lua_Number x) { 1051 int n = num2straux(buff, sz, x); 1052 if (fmt[SIZELENMOD] == 'A') { 1053 int i; 1054 for (i = 0; i < n; i++) 1055 buff[i] = cast_char(toupper(cast_uchar(buff[i]))); 1056 } 1057 else if (l_unlikely(fmt[SIZELENMOD] != 'a')) 1058 return luaL_error(L, "modifiers for format '%%a'/'%%A' not implemented"); 1059 return n; 1060 } 1061 1062 #endif /* } */ 1063 1064 1065 /* 1066 ** Maximum size for items formatted with '%f'. This size is produced 1067 ** by format('%.99f', -maxfloat), and is equal to 99 + 3 ('-', '.', 1068 ** and '\0') + number of decimal digits to represent maxfloat (which 1069 ** is maximum exponent + 1). (99+3+1, adding some extra, 110) 1070 */ 1071 #define MAX_ITEMF (110 + l_floatatt(MAX_10_EXP)) 1072 1073 1074 /* 1075 ** All formats except '%f' do not need that large limit. The other 1076 ** float formats use exponents, so that they fit in the 99 limit for 1077 ** significant digits; 's' for large strings and 'q' add items directly 1078 ** to the buffer; all integer formats also fit in the 99 limit. The 1079 ** worst case are floats: they may need 99 significant digits, plus 1080 ** '0x', '-', '.', 'e+XXXX', and '\0'. Adding some extra, 120. 1081 */ 1082 #define MAX_ITEM 120 1083 1084 1085 /* valid flags in a format specification */ 1086 #if !defined(L_FMTFLAGSF) 1087 1088 /* valid flags for a, A, e, E, f, F, g, and G conversions */ 1089 #define L_FMTFLAGSF "-+#0 " 1090 1091 /* valid flags for o, x, and X conversions */ 1092 #define L_FMTFLAGSX "-#0" 1093 1094 /* valid flags for d and i conversions */ 1095 #define L_FMTFLAGSI "-+0 " 1096 1097 /* valid flags for u conversions */ 1098 #define L_FMTFLAGSU "-0" 1099 1100 /* valid flags for c, p, and s conversions */ 1101 #define L_FMTFLAGSC "-" 1102 1103 #endif 1104 1105 1106 /* 1107 ** Maximum size of each format specification (such as "%-099.99d"): 1108 ** Initial '%', flags (up to 5), width (2), period, precision (2), 1109 ** length modifier (8), conversion specifier, and final '\0', plus some 1110 ** extra. 1111 */ 1112 #define MAX_FORMAT 32 1113 1114 1115 static void addquoted (luaL_Buffer *b, const char *s, size_t len) { 1116 luaL_addchar(b, '"'); 1117 while (len--) { 1118 if (*s == '"' || *s == '\\' || *s == '\n') { 1119 luaL_addchar(b, '\\'); 1120 luaL_addchar(b, *s); 1121 } 1122 else if (iscntrl(cast_uchar(*s))) { 1123 char buff[10]; 1124 if (!isdigit(cast_uchar(*(s+1)))) 1125 l_sprintf(buff, sizeof(buff), "\\%d", (int)cast_uchar(*s)); 1126 else 1127 l_sprintf(buff, sizeof(buff), "\\%03d", (int)cast_uchar(*s)); 1128 luaL_addstring(b, buff); 1129 } 1130 else 1131 luaL_addchar(b, *s); 1132 s++; 1133 } 1134 luaL_addchar(b, '"'); 1135 } 1136 1137 1138 /* 1139 ** Serialize a floating-point number in such a way that it can be 1140 ** scanned back by Lua. Use hexadecimal format for "common" numbers 1141 ** (to preserve precision); inf, -inf, and NaN are handled separately. 1142 ** (NaN cannot be expressed as a numeral, so we write '(0/0)' for it.) 1143 */ 1144 static int quotefloat (lua_State *L, char *buff, lua_Number n) { 1145 const char *s; /* for the fixed representations */ 1146 if (n == (lua_Number)HUGE_VAL) /* inf? */ 1147 s = "1e9999"; 1148 else if (n == -(lua_Number)HUGE_VAL) /* -inf? */ 1149 s = "-1e9999"; 1150 else if (n != n) /* NaN? */ 1151 s = "(0/0)"; 1152 else { /* format number as hexadecimal */ 1153 int nb = lua_number2strx(L, buff, MAX_ITEM, 1154 "%" LUA_NUMBER_FRMLEN "a", n); 1155 /* ensures that 'buff' string uses a dot as the radix character */ 1156 if (memchr(buff, '.', cast_uint(nb)) == NULL) { /* no dot? */ 1157 char point = lua_getlocaledecpoint(); /* try locale point */ 1158 char *ppoint = (char *)memchr(buff, point, cast_uint(nb)); 1159 if (ppoint) *ppoint = '.'; /* change it to a dot */ 1160 } 1161 return nb; 1162 } 1163 /* for the fixed representations */ 1164 return l_sprintf(buff, MAX_ITEM, "%s", s); 1165 } 1166 1167 1168 static void addliteral (lua_State *L, luaL_Buffer *b, int arg) { 1169 switch (lua_type(L, arg)) { 1170 case LUA_TSTRING: { 1171 size_t len; 1172 const char *s = lua_tolstring(L, arg, &len); 1173 addquoted(b, s, len); 1174 break; 1175 } 1176 case LUA_TNUMBER: { 1177 char *buff = luaL_prepbuffsize(b, MAX_ITEM); 1178 int nb; 1179 if (!lua_isinteger(L, arg)) /* float? */ 1180 nb = quotefloat(L, buff, lua_tonumber(L, arg)); 1181 else { /* integers */ 1182 lua_Integer n = lua_tointeger(L, arg); 1183 const char *format = (n == LUA_MININTEGER) /* corner case? */ 1184 ? "0x%" LUA_INTEGER_FRMLEN "x" /* use hex */ 1185 : LUA_INTEGER_FMT; /* else use default format */ 1186 nb = l_sprintf(buff, MAX_ITEM, format, (LUAI_UACINT)n); 1187 } 1188 luaL_addsize(b, cast_uint(nb)); 1189 break; 1190 } 1191 case LUA_TNIL: case LUA_TBOOLEAN: { 1192 luaL_tolstring(L, arg, NULL); 1193 luaL_addvalue(b); 1194 break; 1195 } 1196 default: { 1197 luaL_argerror(L, arg, "value has no literal form"); 1198 } 1199 } 1200 } 1201 1202 1203 static const char *get2digits (const char *s) { 1204 if (isdigit(cast_uchar(*s))) { 1205 s++; 1206 if (isdigit(cast_uchar(*s))) s++; /* (2 digits at most) */ 1207 } 1208 return s; 1209 } 1210 1211 1212 /* 1213 ** Check whether a conversion specification is valid. When called, 1214 ** first character in 'form' must be '%' and last character must 1215 ** be a valid conversion specifier. 'flags' are the accepted flags; 1216 ** 'precision' signals whether to accept a precision. 1217 */ 1218 static void checkformat (lua_State *L, const char *form, const char *flags, 1219 int precision) { 1220 const char *spec = form + 1; /* skip '%' */ 1221 spec += strspn(spec, flags); /* skip flags */ 1222 if (*spec != '0') { /* a width cannot start with '0' */ 1223 spec = get2digits(spec); /* skip width */ 1224 if (*spec == '.' && precision) { 1225 spec++; 1226 spec = get2digits(spec); /* skip precision */ 1227 } 1228 } 1229 if (!isalpha(cast_uchar(*spec))) /* did not go to the end? */ 1230 luaL_error(L, "invalid conversion specification: '%s'", form); 1231 } 1232 1233 1234 /* 1235 ** Get a conversion specification and copy it to 'form'. 1236 ** Return the address of its last character. 1237 */ 1238 static const char *getformat (lua_State *L, const char *strfrmt, 1239 char *form) { 1240 /* spans flags, width, and precision ('0' is included as a flag) */ 1241 size_t len = strspn(strfrmt, L_FMTFLAGSF "123456789."); 1242 len++; /* adds following character (should be the specifier) */ 1243 /* still needs space for '%', '\0', plus a length modifier */ 1244 if (len >= MAX_FORMAT - 10) 1245 luaL_error(L, "invalid format (too long)"); 1246 *(form++) = '%'; 1247 memcpy(form, strfrmt, len * sizeof(char)); 1248 *(form + len) = '\0'; 1249 return strfrmt + len - 1; 1250 } 1251 1252 1253 /* 1254 ** add length modifier into formats 1255 */ 1256 static void addlenmod (char *form, const char *lenmod) { 1257 size_t l = strlen(form); 1258 size_t lm = strlen(lenmod); 1259 char spec = form[l - 1]; 1260 strcpy(form + l - 1, lenmod); 1261 form[l + lm - 1] = spec; 1262 form[l + lm] = '\0'; 1263 } 1264 1265 1266 static int str_format (lua_State *L) { 1267 int top = lua_gettop(L); 1268 int arg = 1; 1269 size_t sfl; 1270 const char *strfrmt = luaL_checklstring(L, arg, &sfl); 1271 const char *strfrmt_end = strfrmt+sfl; 1272 const char *flags; 1273 luaL_Buffer b; 1274 luaL_buffinit(L, &b); 1275 while (strfrmt < strfrmt_end) { 1276 if (*strfrmt != L_ESC) 1277 luaL_addchar(&b, *strfrmt++); 1278 else if (*++strfrmt == L_ESC) 1279 luaL_addchar(&b, *strfrmt++); /* %% */ 1280 else { /* format item */ 1281 char form[MAX_FORMAT]; /* to store the format ('%...') */ 1282 unsigned maxitem = MAX_ITEM; /* maximum length for the result */ 1283 char *buff = luaL_prepbuffsize(&b, maxitem); /* to put result */ 1284 int nb = 0; /* number of bytes in result */ 1285 if (++arg > top) 1286 return luaL_argerror(L, arg, "no value"); 1287 strfrmt = getformat(L, strfrmt, form); 1288 switch (*strfrmt++) { 1289 case 'c': { 1290 checkformat(L, form, L_FMTFLAGSC, 0); 1291 nb = l_sprintf(buff, maxitem, form, (int)luaL_checkinteger(L, arg)); 1292 break; 1293 } 1294 case 'd': case 'i': 1295 flags = L_FMTFLAGSI; 1296 goto intcase; 1297 case 'u': 1298 flags = L_FMTFLAGSU; 1299 goto intcase; 1300 case 'o': case 'x': case 'X': 1301 flags = L_FMTFLAGSX; 1302 intcase: { 1303 lua_Integer n = luaL_checkinteger(L, arg); 1304 checkformat(L, form, flags, 1); 1305 addlenmod(form, LUA_INTEGER_FRMLEN); 1306 nb = l_sprintf(buff, maxitem, form, (LUAI_UACINT)n); 1307 break; 1308 } 1309 case 'a': case 'A': 1310 checkformat(L, form, L_FMTFLAGSF, 1); 1311 addlenmod(form, LUA_NUMBER_FRMLEN); 1312 nb = lua_number2strx(L, buff, maxitem, form, 1313 luaL_checknumber(L, arg)); 1314 break; 1315 case 'f': 1316 maxitem = MAX_ITEMF; /* extra space for '%f' */ 1317 buff = luaL_prepbuffsize(&b, maxitem); 1318 /* FALLTHROUGH */ 1319 case 'e': case 'E': case 'g': case 'G': { 1320 lua_Number n = luaL_checknumber(L, arg); 1321 checkformat(L, form, L_FMTFLAGSF, 1); 1322 addlenmod(form, LUA_NUMBER_FRMLEN); 1323 nb = l_sprintf(buff, maxitem, form, (LUAI_UACNUMBER)n); 1324 break; 1325 } 1326 case 'p': { 1327 const void *p = lua_topointer(L, arg); 1328 checkformat(L, form, L_FMTFLAGSC, 0); 1329 if (p == NULL) { /* avoid calling 'printf' with argument NULL */ 1330 p = "(null)"; /* result */ 1331 form[strlen(form) - 1] = 's'; /* format it as a string */ 1332 } 1333 nb = l_sprintf(buff, maxitem, form, p); 1334 break; 1335 } 1336 case 'q': { 1337 if (form[2] != '\0') /* modifiers? */ 1338 return luaL_error(L, "specifier '%%q' cannot have modifiers"); 1339 addliteral(L, &b, arg); 1340 break; 1341 } 1342 case 's': { 1343 size_t l; 1344 const char *s = luaL_tolstring(L, arg, &l); 1345 if (form[2] == '\0') /* no modifiers? */ 1346 luaL_addvalue(&b); /* keep entire string */ 1347 else { 1348 luaL_argcheck(L, l == strlen(s), arg, "string contains zeros"); 1349 checkformat(L, form, L_FMTFLAGSC, 1); 1350 if (strchr(form, '.') == NULL && l >= 100) { 1351 /* no precision and string is too long to be formatted */ 1352 luaL_addvalue(&b); /* keep entire string */ 1353 } 1354 else { /* format the string into 'buff' */ 1355 nb = l_sprintf(buff, maxitem, form, s); 1356 lua_pop(L, 1); /* remove result from 'luaL_tolstring' */ 1357 } 1358 } 1359 break; 1360 } 1361 default: { /* also treat cases 'pnLlh' */ 1362 return luaL_error(L, "invalid conversion '%s' to 'format'", form); 1363 } 1364 } 1365 lua_assert(cast_uint(nb) < maxitem); 1366 luaL_addsize(&b, cast_uint(nb)); 1367 } 1368 } 1369 luaL_pushresult(&b); 1370 return 1; 1371 } 1372 1373 /* }====================================================== */ 1374 1375 1376 /* 1377 ** {====================================================== 1378 ** PACK/UNPACK 1379 ** ======================================================= 1380 */ 1381 1382 1383 /* value used for padding */ 1384 #if !defined(LUAL_PACKPADBYTE) 1385 #define LUAL_PACKPADBYTE 0x00 1386 #endif 1387 1388 /* maximum size for the binary representation of an integer */ 1389 #define MAXINTSIZE 16 1390 1391 /* number of bits in a character */ 1392 #define NB CHAR_BIT 1393 1394 /* mask for one character (NB 1's) */ 1395 #define MC ((1 << NB) - 1) 1396 1397 /* size of a lua_Integer */ 1398 #define SZINT ((int)sizeof(lua_Integer)) 1399 1400 1401 /* dummy union to get native endianness */ 1402 static const union { 1403 int dummy; 1404 char little; /* true iff machine is little endian */ 1405 } nativeendian = {1}; 1406 1407 1408 /* 1409 ** information to pack/unpack stuff 1410 */ 1411 typedef struct Header { 1412 lua_State *L; 1413 int islittle; 1414 unsigned maxalign; 1415 } Header; 1416 1417 1418 /* 1419 ** options for pack/unpack 1420 */ 1421 typedef enum KOption { 1422 Kint, /* signed integers */ 1423 Kuint, /* unsigned integers */ 1424 Kfloat, /* single-precision floating-point numbers */ 1425 Knumber, /* Lua "native" floating-point numbers */ 1426 Kdouble, /* double-precision floating-point numbers */ 1427 Kchar, /* fixed-length strings */ 1428 Kstring, /* strings with prefixed length */ 1429 Kzstr, /* zero-terminated strings */ 1430 Kpadding, /* padding */ 1431 Kpaddalign, /* padding for alignment */ 1432 Knop /* no-op (configuration or spaces) */ 1433 } KOption; 1434 1435 1436 /* 1437 ** Read an integer numeral from string 'fmt' or return 'df' if 1438 ** there is no numeral 1439 */ 1440 static int digit (int c) { return '0' <= c && c <= '9'; } 1441 1442 static size_t getnum (const char **fmt, size_t df) { 1443 if (!digit(**fmt)) /* no number? */ 1444 return df; /* return default value */ 1445 else { 1446 size_t a = 0; 1447 do { 1448 a = a*10 + cast_uint(*((*fmt)++) - '0'); 1449 } while (digit(**fmt) && a <= (MAX_SIZE - 9)/10); 1450 return a; 1451 } 1452 } 1453 1454 1455 /* 1456 ** Read an integer numeral and raises an error if it is larger 1457 ** than the maximum size of integers. 1458 */ 1459 static unsigned getnumlimit (Header *h, const char **fmt, size_t df) { 1460 size_t sz = getnum(fmt, df); 1461 if (l_unlikely((sz - 1u) >= MAXINTSIZE)) 1462 return cast_uint(luaL_error(h->L, 1463 "integral size (%d) out of limits [1,%d]", sz, MAXINTSIZE)); 1464 return cast_uint(sz); 1465 } 1466 1467 1468 /* 1469 ** Initialize Header 1470 */ 1471 static void initheader (lua_State *L, Header *h) { 1472 h->L = L; 1473 h->islittle = nativeendian.little; 1474 h->maxalign = 1; 1475 } 1476 1477 1478 /* 1479 ** Read and classify next option. 'size' is filled with option's size. 1480 */ 1481 static KOption getoption (Header *h, const char **fmt, size_t *size) { 1482 /* dummy structure to get native alignment requirements */ 1483 struct cD { char c; union { LUAI_MAXALIGN; } u; }; 1484 int opt = *((*fmt)++); 1485 *size = 0; /* default */ 1486 switch (opt) { 1487 case 'b': *size = sizeof(char); return Kint; 1488 case 'B': *size = sizeof(char); return Kuint; 1489 case 'h': *size = sizeof(short); return Kint; 1490 case 'H': *size = sizeof(short); return Kuint; 1491 case 'l': *size = sizeof(long); return Kint; 1492 case 'L': *size = sizeof(long); return Kuint; 1493 case 'j': *size = sizeof(lua_Integer); return Kint; 1494 case 'J': *size = sizeof(lua_Integer); return Kuint; 1495 case 'T': *size = sizeof(size_t); return Kuint; 1496 case 'f': *size = sizeof(float); return Kfloat; 1497 case 'n': *size = sizeof(lua_Number); return Knumber; 1498 case 'd': *size = sizeof(double); return Kdouble; 1499 case 'i': *size = getnumlimit(h, fmt, sizeof(int)); return Kint; 1500 case 'I': *size = getnumlimit(h, fmt, sizeof(int)); return Kuint; 1501 case 's': *size = getnumlimit(h, fmt, sizeof(size_t)); return Kstring; 1502 case 'c': 1503 *size = getnum(fmt, cast_sizet(-1)); 1504 if (l_unlikely(*size == cast_sizet(-1))) 1505 luaL_error(h->L, "missing size for format option 'c'"); 1506 return Kchar; 1507 case 'z': return Kzstr; 1508 case 'x': *size = 1; return Kpadding; 1509 case 'X': return Kpaddalign; 1510 case ' ': break; 1511 case '<': h->islittle = 1; break; 1512 case '>': h->islittle = 0; break; 1513 case '=': h->islittle = nativeendian.little; break; 1514 case '!': { 1515 const size_t maxalign = offsetof(struct cD, u); 1516 h->maxalign = getnumlimit(h, fmt, maxalign); 1517 break; 1518 } 1519 default: luaL_error(h->L, "invalid format option '%c'", opt); 1520 } 1521 return Knop; 1522 } 1523 1524 1525 /* 1526 ** Read, classify, and fill other details about the next option. 1527 ** 'psize' is filled with option's size, 'notoalign' with its 1528 ** alignment requirements. 1529 ** Local variable 'size' gets the size to be aligned. (Kpadal option 1530 ** always gets its full alignment, other options are limited by 1531 ** the maximum alignment ('maxalign'). Kchar option needs no alignment 1532 ** despite its size. 1533 */ 1534 static KOption getdetails (Header *h, size_t totalsize, const char **fmt, 1535 size_t *psize, unsigned *ntoalign) { 1536 KOption opt = getoption(h, fmt, psize); 1537 size_t align = *psize; /* usually, alignment follows size */ 1538 if (opt == Kpaddalign) { /* 'X' gets alignment from following option */ 1539 if (**fmt == '\0' || getoption(h, fmt, &align) == Kchar || align == 0) 1540 luaL_argerror(h->L, 1, "invalid next option for option 'X'"); 1541 } 1542 if (align <= 1 || opt == Kchar) /* need no alignment? */ 1543 *ntoalign = 0; 1544 else { 1545 if (align > h->maxalign) /* enforce maximum alignment */ 1546 align = h->maxalign; 1547 if (l_unlikely(!ispow2(align))) /* not a power of 2? */ 1548 luaL_argerror(h->L, 1, "format asks for alignment not power of 2"); 1549 else { 1550 /* 'szmoda' = totalsize % align */ 1551 unsigned szmoda = cast_uint(totalsize & (align - 1)); 1552 *ntoalign = cast_uint((align - szmoda) & (align - 1)); 1553 } 1554 } 1555 return opt; 1556 } 1557 1558 1559 /* 1560 ** Pack integer 'n' with 'size' bytes and 'islittle' endianness. 1561 ** The final 'if' handles the case when 'size' is larger than 1562 ** the size of a Lua integer, correcting the extra sign-extension 1563 ** bytes if necessary (by default they would be zeros). 1564 */ 1565 static void packint (luaL_Buffer *b, lua_Unsigned n, 1566 int islittle, unsigned size, int neg) { 1567 char *buff = luaL_prepbuffsize(b, size); 1568 unsigned i; 1569 buff[islittle ? 0 : size - 1] = (char)(n & MC); /* first byte */ 1570 for (i = 1; i < size; i++) { 1571 n >>= NB; 1572 buff[islittle ? i : size - 1 - i] = (char)(n & MC); 1573 } 1574 if (neg && size > SZINT) { /* negative number need sign extension? */ 1575 for (i = SZINT; i < size; i++) /* correct extra bytes */ 1576 buff[islittle ? i : size - 1 - i] = (char)MC; 1577 } 1578 luaL_addsize(b, size); /* add result to buffer */ 1579 } 1580 1581 1582 /* 1583 ** Copy 'size' bytes from 'src' to 'dest', correcting endianness if 1584 ** given 'islittle' is different from native endianness. 1585 */ 1586 static void copywithendian (char *dest, const char *src, 1587 unsigned size, int islittle) { 1588 if (islittle == nativeendian.little) 1589 memcpy(dest, src, size); 1590 else { 1591 dest += size - 1; 1592 while (size-- != 0) 1593 *(dest--) = *(src++); 1594 } 1595 } 1596 1597 1598 static int str_pack (lua_State *L) { 1599 luaL_Buffer b; 1600 Header h; 1601 const char *fmt = luaL_checkstring(L, 1); /* format string */ 1602 int arg = 1; /* current argument to pack */ 1603 size_t totalsize = 0; /* accumulate total size of result */ 1604 initheader(L, &h); 1605 lua_pushnil(L); /* mark to separate arguments from string buffer */ 1606 luaL_buffinit(L, &b); 1607 while (*fmt != '\0') { 1608 unsigned ntoalign; 1609 size_t size; 1610 KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign); 1611 luaL_argcheck(L, size + ntoalign <= MAX_SIZE - totalsize, arg, 1612 "result too long"); 1613 totalsize += ntoalign + size; 1614 while (ntoalign-- > 0) 1615 luaL_addchar(&b, LUAL_PACKPADBYTE); /* fill alignment */ 1616 arg++; 1617 switch (opt) { 1618 case Kint: { /* signed integers */ 1619 lua_Integer n = luaL_checkinteger(L, arg); 1620 if (size < SZINT) { /* need overflow check? */ 1621 lua_Integer lim = (lua_Integer)1 << ((size * NB) - 1); 1622 luaL_argcheck(L, -lim <= n && n < lim, arg, "integer overflow"); 1623 } 1624 packint(&b, (lua_Unsigned)n, h.islittle, cast_uint(size), (n < 0)); 1625 break; 1626 } 1627 case Kuint: { /* unsigned integers */ 1628 lua_Integer n = luaL_checkinteger(L, arg); 1629 if (size < SZINT) /* need overflow check? */ 1630 luaL_argcheck(L, (lua_Unsigned)n < ((lua_Unsigned)1 << (size * NB)), 1631 arg, "unsigned overflow"); 1632 packint(&b, (lua_Unsigned)n, h.islittle, cast_uint(size), 0); 1633 break; 1634 } 1635 case Kfloat: { /* C float */ 1636 float f = (float)luaL_checknumber(L, arg); /* get argument */ 1637 char *buff = luaL_prepbuffsize(&b, sizeof(f)); 1638 /* move 'f' to final result, correcting endianness if needed */ 1639 copywithendian(buff, (char *)&f, sizeof(f), h.islittle); 1640 luaL_addsize(&b, size); 1641 break; 1642 } 1643 case Knumber: { /* Lua float */ 1644 lua_Number f = luaL_checknumber(L, arg); /* get argument */ 1645 char *buff = luaL_prepbuffsize(&b, sizeof(f)); 1646 /* move 'f' to final result, correcting endianness if needed */ 1647 copywithendian(buff, (char *)&f, sizeof(f), h.islittle); 1648 luaL_addsize(&b, size); 1649 break; 1650 } 1651 case Kdouble: { /* C double */ 1652 double f = (double)luaL_checknumber(L, arg); /* get argument */ 1653 char *buff = luaL_prepbuffsize(&b, sizeof(f)); 1654 /* move 'f' to final result, correcting endianness if needed */ 1655 copywithendian(buff, (char *)&f, sizeof(f), h.islittle); 1656 luaL_addsize(&b, size); 1657 break; 1658 } 1659 case Kchar: { /* fixed-size string */ 1660 size_t len; 1661 const char *s = luaL_checklstring(L, arg, &len); 1662 luaL_argcheck(L, len <= size, arg, "string longer than given size"); 1663 luaL_addlstring(&b, s, len); /* add string */ 1664 if (len < size) { /* does it need padding? */ 1665 size_t psize = size - len; /* pad size */ 1666 char *buff = luaL_prepbuffsize(&b, psize); 1667 memset(buff, LUAL_PACKPADBYTE, psize); 1668 luaL_addsize(&b, psize); 1669 } 1670 break; 1671 } 1672 case Kstring: { /* strings with length count */ 1673 size_t len; 1674 const char *s = luaL_checklstring(L, arg, &len); 1675 luaL_argcheck(L, size >= sizeof(lua_Unsigned) || 1676 len < ((lua_Unsigned)1 << (size * NB)), 1677 arg, "string length does not fit in given size"); 1678 /* pack length */ 1679 packint(&b, (lua_Unsigned)len, h.islittle, cast_uint(size), 0); 1680 luaL_addlstring(&b, s, len); 1681 totalsize += len; 1682 break; 1683 } 1684 case Kzstr: { /* zero-terminated string */ 1685 size_t len; 1686 const char *s = luaL_checklstring(L, arg, &len); 1687 luaL_argcheck(L, strlen(s) == len, arg, "string contains zeros"); 1688 luaL_addlstring(&b, s, len); 1689 luaL_addchar(&b, '\0'); /* add zero at the end */ 1690 totalsize += len + 1; 1691 break; 1692 } 1693 case Kpadding: luaL_addchar(&b, LUAL_PACKPADBYTE); /* FALLTHROUGH */ 1694 case Kpaddalign: case Knop: 1695 arg--; /* undo increment */ 1696 break; 1697 } 1698 } 1699 luaL_pushresult(&b); 1700 return 1; 1701 } 1702 1703 1704 static int str_packsize (lua_State *L) { 1705 Header h; 1706 const char *fmt = luaL_checkstring(L, 1); /* format string */ 1707 size_t totalsize = 0; /* accumulate total size of result */ 1708 initheader(L, &h); 1709 while (*fmt != '\0') { 1710 unsigned ntoalign; 1711 size_t size; 1712 KOption opt = getdetails(&h, totalsize, &fmt, &size, &ntoalign); 1713 luaL_argcheck(L, opt != Kstring && opt != Kzstr, 1, 1714 "variable-length format"); 1715 size += ntoalign; /* total space used by option */ 1716 luaL_argcheck(L, totalsize <= LUA_MAXINTEGER - size, 1717 1, "format result too large"); 1718 totalsize += size; 1719 } 1720 lua_pushinteger(L, cast_st2S(totalsize)); 1721 return 1; 1722 } 1723 1724 1725 /* 1726 ** Unpack an integer with 'size' bytes and 'islittle' endianness. 1727 ** If size is smaller than the size of a Lua integer and integer 1728 ** is signed, must do sign extension (propagating the sign to the 1729 ** higher bits); if size is larger than the size of a Lua integer, 1730 ** it must check the unread bytes to see whether they do not cause an 1731 ** overflow. 1732 */ 1733 static lua_Integer unpackint (lua_State *L, const char *str, 1734 int islittle, int size, int issigned) { 1735 lua_Unsigned res = 0; 1736 int i; 1737 int limit = (size <= SZINT) ? size : SZINT; 1738 for (i = limit - 1; i >= 0; i--) { 1739 res <<= NB; 1740 res |= (lua_Unsigned)(unsigned char)str[islittle ? i : size - 1 - i]; 1741 } 1742 if (size < SZINT) { /* real size smaller than lua_Integer? */ 1743 if (issigned) { /* needs sign extension? */ 1744 lua_Unsigned mask = (lua_Unsigned)1 << (size*NB - 1); 1745 res = ((res ^ mask) - mask); /* do sign extension */ 1746 } 1747 } 1748 else if (size > SZINT) { /* must check unread bytes */ 1749 int mask = (!issigned || (lua_Integer)res >= 0) ? 0 : MC; 1750 for (i = limit; i < size; i++) { 1751 if (l_unlikely((unsigned char)str[islittle ? i : size - 1 - i] != mask)) 1752 luaL_error(L, "%d-byte integer does not fit into Lua Integer", size); 1753 } 1754 } 1755 return (lua_Integer)res; 1756 } 1757 1758 1759 static int str_unpack (lua_State *L) { 1760 Header h; 1761 const char *fmt = luaL_checkstring(L, 1); 1762 size_t ld; 1763 const char *data = luaL_checklstring(L, 2, &ld); 1764 size_t pos = posrelatI(luaL_optinteger(L, 3, 1), ld) - 1; 1765 int n = 0; /* number of results */ 1766 luaL_argcheck(L, pos <= ld, 3, "initial position out of string"); 1767 initheader(L, &h); 1768 while (*fmt != '\0') { 1769 unsigned ntoalign; 1770 size_t size; 1771 KOption opt = getdetails(&h, pos, &fmt, &size, &ntoalign); 1772 luaL_argcheck(L, ntoalign + size <= ld - pos, 2, 1773 "data string too short"); 1774 pos += ntoalign; /* skip alignment */ 1775 /* stack space for item + next position */ 1776 luaL_checkstack(L, 2, "too many results"); 1777 n++; 1778 switch (opt) { 1779 case Kint: 1780 case Kuint: { 1781 lua_Integer res = unpackint(L, data + pos, h.islittle, 1782 cast_int(size), (opt == Kint)); 1783 lua_pushinteger(L, res); 1784 break; 1785 } 1786 case Kfloat: { 1787 float f; 1788 copywithendian((char *)&f, data + pos, sizeof(f), h.islittle); 1789 lua_pushnumber(L, (lua_Number)f); 1790 break; 1791 } 1792 case Knumber: { 1793 lua_Number f; 1794 copywithendian((char *)&f, data + pos, sizeof(f), h.islittle); 1795 lua_pushnumber(L, f); 1796 break; 1797 } 1798 case Kdouble: { 1799 double f; 1800 copywithendian((char *)&f, data + pos, sizeof(f), h.islittle); 1801 lua_pushnumber(L, (lua_Number)f); 1802 break; 1803 } 1804 case Kchar: { 1805 lua_pushlstring(L, data + pos, size); 1806 break; 1807 } 1808 case Kstring: { 1809 lua_Unsigned len = (lua_Unsigned)unpackint(L, data + pos, 1810 h.islittle, cast_int(size), 0); 1811 luaL_argcheck(L, len <= ld - pos - size, 2, "data string too short"); 1812 lua_pushlstring(L, data + pos + size, len); 1813 pos += len; /* skip string */ 1814 break; 1815 } 1816 case Kzstr: { 1817 size_t len = strlen(data + pos); 1818 luaL_argcheck(L, pos + len < ld, 2, 1819 "unfinished string for format 'z'"); 1820 lua_pushlstring(L, data + pos, len); 1821 pos += len + 1; /* skip string plus final '\0' */ 1822 break; 1823 } 1824 case Kpaddalign: case Kpadding: case Knop: 1825 n--; /* undo increment */ 1826 break; 1827 } 1828 pos += size; 1829 } 1830 lua_pushinteger(L, cast_st2S(pos) + 1); /* next position */ 1831 return n + 1; 1832 } 1833 1834 /* }====================================================== */ 1835 1836 1837 static const luaL_Reg strlib[] = { 1838 {"byte", str_byte}, 1839 {"char", str_char}, 1840 {"dump", str_dump}, 1841 {"find", str_find}, 1842 {"format", str_format}, 1843 {"gmatch", gmatch}, 1844 {"gsub", str_gsub}, 1845 {"len", str_len}, 1846 {"lower", str_lower}, 1847 {"match", str_match}, 1848 {"rep", str_rep}, 1849 {"reverse", str_reverse}, 1850 {"sub", str_sub}, 1851 {"upper", str_upper}, 1852 {"pack", str_pack}, 1853 {"packsize", str_packsize}, 1854 {"unpack", str_unpack}, 1855 {NULL, NULL} 1856 }; 1857 1858 1859 static void createmetatable (lua_State *L) { 1860 /* table to be metatable for strings */ 1861 luaL_newlibtable(L, stringmetamethods); 1862 luaL_setfuncs(L, stringmetamethods, 0); 1863 lua_pushliteral(L, ""); /* dummy string */ 1864 lua_pushvalue(L, -2); /* copy table */ 1865 lua_setmetatable(L, -2); /* set table as metatable for strings */ 1866 lua_pop(L, 1); /* pop dummy string */ 1867 lua_pushvalue(L, -2); /* get string library */ 1868 lua_setfield(L, -2, "__index"); /* metatable.__index = string */ 1869 lua_pop(L, 1); /* pop metatable */ 1870 } 1871 1872 1873 /* 1874 ** Open string library 1875 */ 1876 LUAMOD_API int luaopen_string (lua_State *L) { 1877 luaL_newlib(L, strlib); 1878 createmetatable(L); 1879 return 1; 1880 } 1881