diff options
author | Philipp Janda <siffiejoe@gmx.net> | 2016-01-22 15:58:48 +0100 |
---|---|---|
committer | Philipp Janda <siffiejoe@gmx.net> | 2016-01-22 15:58:48 +0100 |
commit | ca85188590e677edcc9290d29e69a3692187c826 (patch) | |
tree | 6223894654ff62468f1086423caf31f459e7861b | |
parent | abf4ea9645ce3ff0c390a57ab3e3e4f82d9a4035 (diff) | |
download | lua-compat-5.3-ca85188590e677edcc9290d29e69a3692187c826.tar.gz lua-compat-5.3-ca85188590e677edcc9290d29e69a3692187c826.tar.bz2 lua-compat-5.3-ca85188590e677edcc9290d29e69a3692187c826.zip |
Update backports.
The backports of lstrlib.c, ltablib.c, and lutf8lib.c have been updated
to Lua version 5.3.2.
-rw-r--r-- | lprefix.h | 58 | ||||
-rw-r--r-- | lstrlib.c | 277 | ||||
-rw-r--r-- | ltablib.c | 378 | ||||
-rw-r--r-- | lutf8lib.c | 13 |
4 files changed, 485 insertions, 241 deletions
@@ -48,6 +48,7 @@ | |||
48 | #undef LUAMOD_API | 48 | #undef LUAMOD_API |
49 | #define LUAMOD_API extern | 49 | #define LUAMOD_API extern |
50 | 50 | ||
51 | |||
51 | #ifdef lutf8lib_c | 52 | #ifdef lutf8lib_c |
52 | # define luaopen_utf8 luaopen_compat53_utf8 | 53 | # define luaopen_utf8 luaopen_compat53_utf8 |
53 | # include <stdarg.h> | 54 | # include <stdarg.h> |
@@ -81,24 +82,18 @@ static const char *compat53_utf8_escape (lua_State* L, ...) { | |||
81 | compat53_utf8_escape(L, l) | 82 | compat53_utf8_escape(L, l) |
82 | #endif | 83 | #endif |
83 | 84 | ||
85 | |||
84 | #ifdef ltablib_c | 86 | #ifdef ltablib_c |
85 | # define luaopen_table luaopen_compat53_table | 87 | # define luaopen_table luaopen_compat53_table |
86 | /* lua_rawgeti in compat53.h is implemented as a macro, so the | 88 | # ifndef LUA_MAXINTEGER |
87 | * function signature doesn't match when you use a function pointer | 89 | /* conservative estimate: */ |
88 | */ | 90 | # define LUA_MAXINTEGER INT_MAX |
89 | static int compat53_rawgeti (lua_State *L, int i, lua_Integer n) { | 91 | # endif |
90 | return lua_rawgeti(L, i, n); | ||
91 | } | ||
92 | # undef lua_rawgeti | ||
93 | # define lua_rawgeti compat53_rawgeti | ||
94 | static void compat53_rawseti (lua_State *L, int i, lua_Integer n) { | ||
95 | lua_rawseti(L, i, (int)n); | ||
96 | } | ||
97 | # undef lua_rawseti | ||
98 | # define lua_rawseti compat53_rawseti | ||
99 | #endif /* ltablib_c */ | 92 | #endif /* ltablib_c */ |
100 | 93 | ||
94 | |||
101 | #ifdef lstrlib_c | 95 | #ifdef lstrlib_c |
96 | #include <locale.h> | ||
102 | #include <lualib.h> | 97 | #include <lualib.h> |
103 | /* move the string library open function out of the way (we only take | 98 | /* move the string library open function out of the way (we only take |
104 | * the string packing functions)! | 99 | * the string packing functions)! |
@@ -112,8 +107,33 @@ static void compat53_rawseti (lua_State *L, int i, lua_Integer n) { | |||
112 | # if LUA_VERSION_NUM < 503 | 107 | # if LUA_VERSION_NUM < 503 |
113 | /* lstrlib assumes that lua_Integer and lua_Unsigned have the same | 108 | /* lstrlib assumes that lua_Integer and lua_Unsigned have the same |
114 | * size, so we use the unsigned equivalent of ptrdiff_t! */ | 109 | * size, so we use the unsigned equivalent of ptrdiff_t! */ |
115 | # define lua_Unsigned size_t | 110 | # define lua_Unsigned size_t |
116 | # endif | 111 | # endif |
112 | # ifndef l_mathlim | ||
113 | # ifdef LUA_NUMBER_DOUBLE | ||
114 | # define l_mathlim(n) (DBL_##n) | ||
115 | # else | ||
116 | # define l_mathlim(n) (FLT_##n) | ||
117 | # endif | ||
118 | # endif | ||
119 | # ifndef l_mathop | ||
120 | # ifdef LUA_NUMBER_DOUBLE | ||
121 | # define l_mathop(op) op | ||
122 | # else | ||
123 | # define l_mathop(op) op##f | ||
124 | # endif | ||
125 | # endif | ||
126 | # ifndef lua_getlocaledecpoint | ||
127 | # define lua_getlocaledecpoint() (localeconv()->decimal_point[0]) | ||
128 | # endif | ||
129 | # ifndef l_sprintf | ||
130 | # if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L | ||
131 | # define l_sprintf(s,sz,f,i) (snprintf(s, sz, f, i)) | ||
132 | # else | ||
133 | # define l_sprintf(s,sz,f,i) ((void)(sz), sprintf(s, f, i)) | ||
134 | # endif | ||
135 | # endif | ||
136 | |||
117 | static int str_pack (lua_State *L); | 137 | static int str_pack (lua_State *L); |
118 | static int str_packsize (lua_State *L); | 138 | static int str_packsize (lua_State *L); |
119 | static int str_unpack (lua_State *L); | 139 | static int str_unpack (lua_State *L); |
@@ -127,12 +147,20 @@ LUAMOD_API int luaopen_compat53_string (lua_State *L) { | |||
127 | luaL_newlib(L, funcs); | 147 | luaL_newlib(L, funcs); |
128 | return 1; | 148 | return 1; |
129 | } | 149 | } |
150 | /* fake CLANG feature detection on other compilers */ | ||
151 | # ifndef __has_attribute | ||
152 | # define __has_attribute(x) 0 | ||
153 | # endif | ||
130 | /* make luaopen_string(_XXX) static, so it (and all other referenced | 154 | /* make luaopen_string(_XXX) static, so it (and all other referenced |
131 | * string functions) won't be included in the resulting dll | 155 | * string functions) won't be included in the resulting dll |
132 | * (hopefully). | 156 | * (hopefully). |
133 | */ | 157 | */ |
134 | # undef LUAMOD_API | 158 | # undef LUAMOD_API |
135 | # define LUAMOD_API static | 159 | # if defined(__GNUC__) || __has_attribute(__unused__) |
160 | # define LUAMOD_API __attribute__((__unused__)) static | ||
161 | # else | ||
162 | # define LUAMOD_API static | ||
163 | # endif | ||
136 | #endif /* lstrlib.c */ | 164 | #endif /* lstrlib.c */ |
137 | 165 | ||
138 | #endif | 166 | #endif |
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lstrlib.c,v 1.221 2014/12/11 14:03:07 roberto Exp $ | 2 | ** $Id: lstrlib.c,v 1.239 2015/11/25 16:28:17 roberto Exp $ |
3 | ** Standard library for string operations and pattern-matching | 3 | ** Standard library for string operations and pattern-matching |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -11,6 +11,7 @@ | |||
11 | 11 | ||
12 | 12 | ||
13 | #include <ctype.h> | 13 | #include <ctype.h> |
14 | #include <float.h> | ||
14 | #include <limits.h> | 15 | #include <limits.h> |
15 | #include <stddef.h> | 16 | #include <stddef.h> |
16 | #include <stdio.h> | 17 | #include <stdio.h> |
@@ -40,8 +41,10 @@ | |||
40 | ** Some sizes are better limited to fit in 'int', but must also fit in | 41 | ** Some sizes are better limited to fit in 'int', but must also fit in |
41 | ** 'size_t'. (We assume that 'lua_Integer' cannot be smaller than 'int'.) | 42 | ** 'size_t'. (We assume that 'lua_Integer' cannot be smaller than 'int'.) |
42 | */ | 43 | */ |
44 | #define MAX_SIZET ((size_t)(~(size_t)0)) | ||
45 | |||
43 | #define MAXSIZE \ | 46 | #define MAXSIZE \ |
44 | (sizeof(size_t) < sizeof(int) ? (~(size_t)0) : (size_t)(INT_MAX)) | 47 | (sizeof(size_t) < sizeof(int) ? MAX_SIZET : (size_t)(INT_MAX)) |
45 | 48 | ||
46 | 49 | ||
47 | 50 | ||
@@ -70,7 +73,7 @@ static int str_sub (lua_State *L) { | |||
70 | if (start < 1) start = 1; | 73 | if (start < 1) start = 1; |
71 | if (end > (lua_Integer)l) end = l; | 74 | if (end > (lua_Integer)l) end = l; |
72 | if (start <= end) | 75 | if (start <= end) |
73 | lua_pushlstring(L, s + start - 1, (size_t)(end - start + 1)); | 76 | lua_pushlstring(L, s + start - 1, (size_t)(end - start) + 1); |
74 | else lua_pushliteral(L, ""); | 77 | else lua_pushliteral(L, ""); |
75 | return 1; | 78 | return 1; |
76 | } | 79 | } |
@@ -149,9 +152,9 @@ static int str_byte (lua_State *L) { | |||
149 | if (posi < 1) posi = 1; | 152 | if (posi < 1) posi = 1; |
150 | if (pose > (lua_Integer)l) pose = l; | 153 | if (pose > (lua_Integer)l) pose = l; |
151 | if (posi > pose) return 0; /* empty interval; return no values */ | 154 | if (posi > pose) return 0; /* empty interval; return no values */ |
152 | n = (int)(pose - posi + 1); | 155 | if (pose - posi >= INT_MAX) /* arithmetic overflow? */ |
153 | if (posi + n <= pose) /* arithmetic overflow? */ | ||
154 | return luaL_error(L, "string slice too long"); | 156 | return luaL_error(L, "string slice too long"); |
157 | n = (int)(pose - posi) + 1; | ||
155 | luaL_checkstack(L, n, "string slice too long"); | 158 | luaL_checkstack(L, n, "string slice too long"); |
156 | for (i=0; i<n; i++) | 159 | for (i=0; i<n; i++) |
157 | lua_pushinteger(L, uchar(s[posi+i-1])); | 160 | lua_pushinteger(L, uchar(s[posi+i-1])); |
@@ -207,11 +210,12 @@ static int str_dump (lua_State *L) { | |||
207 | 210 | ||
208 | 211 | ||
209 | typedef struct MatchState { | 212 | typedef struct MatchState { |
210 | int matchdepth; /* control for recursive depth (to avoid C stack overflow) */ | ||
211 | const char *src_init; /* init of source string */ | 213 | const char *src_init; /* init of source string */ |
212 | const char *src_end; /* end ('\0') of source string */ | 214 | const char *src_end; /* end ('\0') of source string */ |
213 | const char *p_end; /* end ('\0') of pattern */ | 215 | const char *p_end; /* end ('\0') of pattern */ |
214 | lua_State *L; | 216 | lua_State *L; |
217 | size_t nrep; /* limit to avoid non-linear complexity */ | ||
218 | int matchdepth; /* control for recursive depth (to avoid C stack overflow) */ | ||
215 | int level; /* total number of captures (finished or unfinished) */ | 219 | int level; /* total number of captures (finished or unfinished) */ |
216 | struct { | 220 | struct { |
217 | const char *init; | 221 | const char *init; |
@@ -230,6 +234,17 @@ static const char *match (MatchState *ms, const char *s, const char *p); | |||
230 | #endif | 234 | #endif |
231 | 235 | ||
232 | 236 | ||
237 | /* | ||
238 | ** parameters to control the maximum number of operators handled in | ||
239 | ** a match (to avoid non-linear complexity). The maximum will be: | ||
240 | ** (subject length) * A_REPS + B_REPS | ||
241 | */ | ||
242 | #if !defined(A_REPS) | ||
243 | #define A_REPS 4 | ||
244 | #define B_REPS 100000 | ||
245 | #endif | ||
246 | |||
247 | |||
233 | #define L_ESC '%' | 248 | #define L_ESC '%' |
234 | #define SPECIALS "^$*+?.([%-" | 249 | #define SPECIALS "^$*+?.([%-" |
235 | 250 | ||
@@ -487,6 +502,8 @@ static const char *match (MatchState *ms, const char *s, const char *p) { | |||
487 | s = NULL; /* fail */ | 502 | s = NULL; /* fail */ |
488 | } | 503 | } |
489 | else { /* matched once */ | 504 | else { /* matched once */ |
505 | if (ms->nrep-- == 0) | ||
506 | luaL_error(ms->L, "pattern too complex"); | ||
490 | switch (*ep) { /* handle optional suffix */ | 507 | switch (*ep) { /* handle optional suffix */ |
491 | case '?': { /* optional */ | 508 | case '?': { /* optional */ |
492 | const char *res; | 509 | const char *res; |
@@ -499,7 +516,7 @@ static const char *match (MatchState *ms, const char *s, const char *p) { | |||
499 | } | 516 | } |
500 | case '+': /* 1 or more repetitions */ | 517 | case '+': /* 1 or more repetitions */ |
501 | s++; /* 1 match already done */ | 518 | s++; /* 1 match already done */ |
502 | /* go through */ | 519 | /* FALLTHROUGH */ |
503 | case '*': /* 0 or more repetitions */ | 520 | case '*': /* 0 or more repetitions */ |
504 | s = max_expand(ms, s, p, ep); | 521 | s = max_expand(ms, s, p, ep); |
505 | break; | 522 | break; |
@@ -554,7 +571,7 @@ static void push_onecapture (MatchState *ms, int i, const char *s, | |||
554 | ptrdiff_t l = ms->capture[i].len; | 571 | ptrdiff_t l = ms->capture[i].len; |
555 | if (l == CAP_UNFINISHED) luaL_error(ms->L, "unfinished capture"); | 572 | if (l == CAP_UNFINISHED) luaL_error(ms->L, "unfinished capture"); |
556 | if (l == CAP_POSITION) | 573 | if (l == CAP_POSITION) |
557 | lua_pushinteger(ms->L, ms->capture[i].init - ms->src_init + 1); | 574 | lua_pushinteger(ms->L, (ms->capture[i].init - ms->src_init) + 1); |
558 | else | 575 | else |
559 | lua_pushlstring(ms->L, ms->capture[i].init, l); | 576 | lua_pushlstring(ms->L, ms->capture[i].init, l); |
560 | } | 577 | } |
@@ -583,6 +600,26 @@ static int nospecials (const char *p, size_t l) { | |||
583 | } | 600 | } |
584 | 601 | ||
585 | 602 | ||
603 | static void prepstate (MatchState *ms, lua_State *L, | ||
604 | const char *s, size_t ls, const char *p, size_t lp) { | ||
605 | ms->L = L; | ||
606 | ms->matchdepth = MAXCCALLS; | ||
607 | ms->src_init = s; | ||
608 | ms->src_end = s + ls; | ||
609 | ms->p_end = p + lp; | ||
610 | if (ls < (MAX_SIZET - B_REPS) / A_REPS) | ||
611 | ms->nrep = A_REPS * ls + B_REPS; | ||
612 | else /* overflow (very long subject) */ | ||
613 | ms->nrep = MAX_SIZET; /* no limit */ | ||
614 | } | ||
615 | |||
616 | |||
617 | static void reprepstate (MatchState *ms) { | ||
618 | ms->level = 0; | ||
619 | lua_assert(ms->matchdepth == MAXCCALLS); | ||
620 | } | ||
621 | |||
622 | |||
586 | static int str_find_aux (lua_State *L, int find) { | 623 | static int str_find_aux (lua_State *L, int find) { |
587 | size_t ls, lp; | 624 | size_t ls, lp; |
588 | const char *s = luaL_checklstring(L, 1, &ls); | 625 | const char *s = luaL_checklstring(L, 1, &ls); |
@@ -598,8 +635,8 @@ static int str_find_aux (lua_State *L, int find) { | |||
598 | /* do a plain search */ | 635 | /* do a plain search */ |
599 | const char *s2 = lmemfind(s + init - 1, ls - (size_t)init + 1, p, lp); | 636 | const char *s2 = lmemfind(s + init - 1, ls - (size_t)init + 1, p, lp); |
600 | if (s2) { | 637 | if (s2) { |
601 | lua_pushinteger(L, s2 - s + 1); | 638 | lua_pushinteger(L, (s2 - s) + 1); |
602 | lua_pushinteger(L, s2 - s + lp); | 639 | lua_pushinteger(L, (s2 - s) + lp); |
603 | return 2; | 640 | return 2; |
604 | } | 641 | } |
605 | } | 642 | } |
@@ -610,18 +647,13 @@ static int str_find_aux (lua_State *L, int find) { | |||
610 | if (anchor) { | 647 | if (anchor) { |
611 | p++; lp--; /* skip anchor character */ | 648 | p++; lp--; /* skip anchor character */ |
612 | } | 649 | } |
613 | ms.L = L; | 650 | prepstate(&ms, L, s, ls, p, lp); |
614 | ms.matchdepth = MAXCCALLS; | ||
615 | ms.src_init = s; | ||
616 | ms.src_end = s + ls; | ||
617 | ms.p_end = p + lp; | ||
618 | do { | 651 | do { |
619 | const char *res; | 652 | const char *res; |
620 | ms.level = 0; | 653 | reprepstate(&ms); |
621 | lua_assert(ms.matchdepth == MAXCCALLS); | ||
622 | if ((res=match(&ms, s1, p)) != NULL) { | 654 | if ((res=match(&ms, s1, p)) != NULL) { |
623 | if (find) { | 655 | if (find) { |
624 | lua_pushinteger(L, s1 - s + 1); /* start */ | 656 | lua_pushinteger(L, (s1 - s) + 1); /* start */ |
625 | lua_pushinteger(L, res - s); /* end */ | 657 | lua_pushinteger(L, res - s); /* end */ |
626 | return push_captures(&ms, NULL, 0) + 2; | 658 | return push_captures(&ms, NULL, 0) + 2; |
627 | } | 659 | } |
@@ -645,29 +677,26 @@ static int str_match (lua_State *L) { | |||
645 | } | 677 | } |
646 | 678 | ||
647 | 679 | ||
680 | /* state for 'gmatch' */ | ||
681 | typedef struct GMatchState { | ||
682 | const char *src; /* current position */ | ||
683 | const char *p; /* pattern */ | ||
684 | MatchState ms; /* match state */ | ||
685 | } GMatchState; | ||
686 | |||
687 | |||
648 | static int gmatch_aux (lua_State *L) { | 688 | static int gmatch_aux (lua_State *L) { |
649 | MatchState ms; | 689 | GMatchState *gm = (GMatchState *)lua_touserdata(L, lua_upvalueindex(3)); |
650 | size_t ls, lp; | ||
651 | const char *s = lua_tolstring(L, lua_upvalueindex(1), &ls); | ||
652 | const char *p = lua_tolstring(L, lua_upvalueindex(2), &lp); | ||
653 | const char *src; | 690 | const char *src; |
654 | ms.L = L; | 691 | for (src = gm->src; src <= gm->ms.src_end; src++) { |
655 | ms.matchdepth = MAXCCALLS; | ||
656 | ms.src_init = s; | ||
657 | ms.src_end = s+ls; | ||
658 | ms.p_end = p + lp; | ||
659 | for (src = s + (size_t)lua_tointeger(L, lua_upvalueindex(3)); | ||
660 | src <= ms.src_end; | ||
661 | src++) { | ||
662 | const char *e; | 692 | const char *e; |
663 | ms.level = 0; | 693 | reprepstate(&gm->ms); |
664 | lua_assert(ms.matchdepth == MAXCCALLS); | 694 | if ((e = match(&gm->ms, src, gm->p)) != NULL) { |
665 | if ((e = match(&ms, src, p)) != NULL) { | 695 | if (e == src) /* empty match? */ |
666 | lua_Integer newstart = e-s; | 696 | gm->src =src + 1; /* go at least one position */ |
667 | if (e == src) newstart++; /* empty match? go at least one position */ | 697 | else |
668 | lua_pushinteger(L, newstart); | 698 | gm->src = e; |
669 | lua_replace(L, lua_upvalueindex(3)); | 699 | return push_captures(&gm->ms, src, e); |
670 | return push_captures(&ms, src, e); | ||
671 | } | 700 | } |
672 | } | 701 | } |
673 | return 0; /* not found */ | 702 | return 0; /* not found */ |
@@ -675,10 +704,14 @@ static int gmatch_aux (lua_State *L) { | |||
675 | 704 | ||
676 | 705 | ||
677 | static int gmatch (lua_State *L) { | 706 | static int gmatch (lua_State *L) { |
678 | luaL_checkstring(L, 1); | 707 | size_t ls, lp; |
679 | luaL_checkstring(L, 2); | 708 | const char *s = luaL_checklstring(L, 1, &ls); |
680 | lua_settop(L, 2); | 709 | const char *p = luaL_checklstring(L, 2, &lp); |
681 | lua_pushinteger(L, 0); | 710 | GMatchState *gm; |
711 | lua_settop(L, 2); /* keep them on closure to avoid being collected */ | ||
712 | gm = (GMatchState *)lua_newuserdata(L, sizeof(GMatchState)); | ||
713 | prepstate(&gm->ms, L, s, ls, p, lp); | ||
714 | gm->src = s; gm->p = p; | ||
682 | lua_pushcclosure(L, gmatch_aux, 3); | 715 | lua_pushcclosure(L, gmatch_aux, 3); |
683 | return 1; | 716 | return 1; |
684 | } | 717 | } |
@@ -760,17 +793,11 @@ static int str_gsub (lua_State *L) { | |||
760 | if (anchor) { | 793 | if (anchor) { |
761 | p++; lp--; /* skip anchor character */ | 794 | p++; lp--; /* skip anchor character */ |
762 | } | 795 | } |
763 | ms.L = L; | 796 | prepstate(&ms, L, src, srcl, p, lp); |
764 | ms.matchdepth = MAXCCALLS; | ||
765 | ms.src_init = src; | ||
766 | ms.src_end = src+srcl; | ||
767 | ms.p_end = p + lp; | ||
768 | while (n < max_s) { | 797 | while (n < max_s) { |
769 | const char *e; | 798 | const char *e; |
770 | ms.level = 0; | 799 | reprepstate(&ms); |
771 | lua_assert(ms.matchdepth == MAXCCALLS); | 800 | if ((e = match(&ms, src, p)) != NULL) { |
772 | e = match(&ms, src, p); | ||
773 | if (e) { | ||
774 | n++; | 801 | n++; |
775 | add_value(&ms, &b, src, e, tr); | 802 | add_value(&ms, &b, src, e, tr); |
776 | } | 803 | } |
@@ -797,17 +824,102 @@ static int str_gsub (lua_State *L) { | |||
797 | ** ======================================================= | 824 | ** ======================================================= |
798 | */ | 825 | */ |
799 | 826 | ||
800 | /* maximum size of each formatted item (> len(format('%99.99f', -1e308))) */ | 827 | #if !defined(lua_number2strx) /* { */ |
801 | #define MAX_ITEM 512 | 828 | |
829 | /* | ||
830 | ** Hexadecimal floating-point formatter | ||
831 | */ | ||
832 | |||
833 | #include <locale.h> | ||
834 | #include <math.h> | ||
835 | |||
836 | #define SIZELENMOD (sizeof(LUA_NUMBER_FRMLEN)/sizeof(char)) | ||
837 | |||
838 | |||
839 | /* | ||
840 | ** Number of bits that goes into the first digit. It can be any value | ||
841 | ** between 1 and 4; the following definition tries to align the number | ||
842 | ** to nibble boundaries by making what is left after that first digit a | ||
843 | ** multiple of 4. | ||
844 | */ | ||
845 | #define L_NBFD ((l_mathlim(MANT_DIG) - 1)%4 + 1) | ||
846 | |||
847 | |||
848 | /* | ||
849 | ** Add integer part of 'x' to buffer and return new 'x' | ||
850 | */ | ||
851 | static lua_Number adddigit (char *buff, int n, lua_Number x) { | ||
852 | lua_Number dd = l_mathop(floor)(x); /* get integer part from 'x' */ | ||
853 | int d = (int)dd; | ||
854 | buff[n] = (d < 10 ? d + '0' : d - 10 + 'a'); /* add to buffer */ | ||
855 | return x - dd; /* return what is left */ | ||
856 | } | ||
857 | |||
858 | |||
859 | static int num2straux (char *buff, int sz, lua_Number x) { | ||
860 | if (x != x || x == HUGE_VAL || x == -HUGE_VAL) /* inf or NaN? */ | ||
861 | return l_sprintf(buff, sz, LUA_NUMBER_FMT, x); /* equal to '%g' */ | ||
862 | else if (x == 0) { /* can be -0... */ | ||
863 | /* create "0" or "-0" followed by exponent */ | ||
864 | return l_sprintf(buff, sz, LUA_NUMBER_FMT "x0p+0", x); | ||
865 | } | ||
866 | else { | ||
867 | int e; | ||
868 | lua_Number m = l_mathop(frexp)(x, &e); /* 'x' fraction and exponent */ | ||
869 | int n = 0; /* character count */ | ||
870 | if (m < 0) { /* is number negative? */ | ||
871 | buff[n++] = '-'; /* add signal */ | ||
872 | m = -m; /* make it positive */ | ||
873 | } | ||
874 | buff[n++] = '0'; buff[n++] = 'x'; /* add "0x" */ | ||
875 | m = adddigit(buff, n++, m * (1 << L_NBFD)); /* add first digit */ | ||
876 | e -= L_NBFD; /* this digit goes before the radix point */ | ||
877 | if (m > 0) { /* more digits? */ | ||
878 | buff[n++] = lua_getlocaledecpoint(); /* add radix point */ | ||
879 | do { /* add as many digits as needed */ | ||
880 | m = adddigit(buff, n++, m * 16); | ||
881 | } while (m > 0); | ||
882 | } | ||
883 | n += l_sprintf(buff + n, sz - n, "p%+d", e); /* add exponent */ | ||
884 | lua_assert(n < sz); | ||
885 | return n; | ||
886 | } | ||
887 | } | ||
888 | |||
889 | |||
890 | static int lua_number2strx (lua_State *L, char *buff, int sz, | ||
891 | const char *fmt, lua_Number x) { | ||
892 | int n = num2straux(buff, sz, x); | ||
893 | if (fmt[SIZELENMOD] == 'A') { | ||
894 | int i; | ||
895 | for (i = 0; i < n; i++) | ||
896 | buff[i] = toupper(uchar(buff[i])); | ||
897 | } | ||
898 | else if (fmt[SIZELENMOD] != 'a') | ||
899 | luaL_error(L, "modifiers for format '%%a'/'%%A' not implemented"); | ||
900 | return n; | ||
901 | } | ||
902 | |||
903 | #endif /* } */ | ||
904 | |||
905 | |||
906 | /* | ||
907 | ** Maximum size of each formatted item. This maximum size is produced | ||
908 | ** by format('%.99f', -maxfloat), and is equal to 99 + 3 ('-', '.', | ||
909 | ** and '\0') + number of decimal digits to represent maxfloat (which | ||
910 | ** is maximum exponent + 1). (99+3+1 then rounded to 120 for "extra | ||
911 | ** expenses", such as locale-dependent stuff) | ||
912 | */ | ||
913 | #define MAX_ITEM (120 + l_mathlim(MAX_10_EXP)) | ||
914 | |||
802 | 915 | ||
803 | /* valid flags in a format specification */ | 916 | /* valid flags in a format specification */ |
804 | #define FLAGS "-+ #0" | 917 | #define FLAGS "-+ #0" |
805 | 918 | ||
806 | /* | 919 | /* |
807 | ** maximum size of each format specification (such as "%-099.99d") | 920 | ** maximum size of each format specification (such as "%-099.99d") |
808 | ** (+2 for length modifiers; +10 accounts for %99.99x plus margin of error) | ||
809 | */ | 921 | */ |
810 | #define MAX_FORMAT (sizeof(FLAGS) + 2 + 10) | 922 | #define MAX_FORMAT 32 |
811 | 923 | ||
812 | 924 | ||
813 | static void addquoted (lua_State *L, luaL_Buffer *b, int arg) { | 925 | static void addquoted (lua_State *L, luaL_Buffer *b, int arg) { |
@@ -822,9 +934,9 @@ static void addquoted (lua_State *L, luaL_Buffer *b, int arg) { | |||
822 | else if (*s == '\0' || iscntrl(uchar(*s))) { | 934 | else if (*s == '\0' || iscntrl(uchar(*s))) { |
823 | char buff[10]; | 935 | char buff[10]; |
824 | if (!isdigit(uchar(*(s+1)))) | 936 | if (!isdigit(uchar(*(s+1)))) |
825 | sprintf(buff, "\\%d", (int)uchar(*s)); | 937 | l_sprintf(buff, sizeof(buff), "\\%d", (int)uchar(*s)); |
826 | else | 938 | else |
827 | sprintf(buff, "\\%03d", (int)uchar(*s)); | 939 | l_sprintf(buff, sizeof(buff), "\\%03d", (int)uchar(*s)); |
828 | luaL_addstring(b, buff); | 940 | luaL_addstring(b, buff); |
829 | } | 941 | } |
830 | else | 942 | else |
@@ -849,8 +961,8 @@ static const char *scanformat (lua_State *L, const char *strfrmt, char *form) { | |||
849 | if (isdigit(uchar(*p))) | 961 | if (isdigit(uchar(*p))) |
850 | luaL_error(L, "invalid format (width or precision too long)"); | 962 | luaL_error(L, "invalid format (width or precision too long)"); |
851 | *(form++) = '%'; | 963 | *(form++) = '%'; |
852 | memcpy(form, strfrmt, (p - strfrmt + 1) * sizeof(char)); | 964 | memcpy(form, strfrmt, ((p - strfrmt) + 1) * sizeof(char)); |
853 | form += p - strfrmt + 1; | 965 | form += (p - strfrmt) + 1; |
854 | *form = '\0'; | 966 | *form = '\0'; |
855 | return p; | 967 | return p; |
856 | } | 968 | } |
@@ -891,23 +1003,25 @@ static int str_format (lua_State *L) { | |||
891 | strfrmt = scanformat(L, strfrmt, form); | 1003 | strfrmt = scanformat(L, strfrmt, form); |
892 | switch (*strfrmt++) { | 1004 | switch (*strfrmt++) { |
893 | case 'c': { | 1005 | case 'c': { |
894 | nb = sprintf(buff, form, (int)luaL_checkinteger(L, arg)); | 1006 | nb = l_sprintf(buff, MAX_ITEM, form, (int)luaL_checkinteger(L, arg)); |
895 | break; | 1007 | break; |
896 | } | 1008 | } |
897 | case 'd': case 'i': | 1009 | case 'd': case 'i': |
898 | case 'o': case 'u': case 'x': case 'X': { | 1010 | case 'o': case 'u': case 'x': case 'X': { |
899 | lua_Integer n = luaL_checkinteger(L, arg); | 1011 | lua_Integer n = luaL_checkinteger(L, arg); |
900 | addlenmod(form, LUA_INTEGER_FRMLEN); | 1012 | addlenmod(form, LUA_INTEGER_FRMLEN); |
901 | nb = sprintf(buff, form, n); | 1013 | nb = l_sprintf(buff, MAX_ITEM, form, n); |
902 | break; | 1014 | break; |
903 | } | 1015 | } |
904 | #if defined(LUA_USE_AFORMAT) | ||
905 | case 'a': case 'A': | 1016 | case 'a': case 'A': |
906 | #endif | 1017 | addlenmod(form, LUA_NUMBER_FRMLEN); |
1018 | nb = lua_number2strx(L, buff, MAX_ITEM, form, | ||
1019 | luaL_checknumber(L, arg)); | ||
1020 | break; | ||
907 | case 'e': case 'E': case 'f': | 1021 | case 'e': case 'E': case 'f': |
908 | case 'g': case 'G': { | 1022 | case 'g': case 'G': { |
909 | addlenmod(form, LUA_NUMBER_FRMLEN); | 1023 | addlenmod(form, LUA_NUMBER_FRMLEN); |
910 | nb = sprintf(buff, form, luaL_checknumber(L, arg)); | 1024 | nb = l_sprintf(buff, MAX_ITEM, form, luaL_checknumber(L, arg)); |
911 | break; | 1025 | break; |
912 | } | 1026 | } |
913 | case 'q': { | 1027 | case 'q': { |
@@ -917,23 +1031,27 @@ static int str_format (lua_State *L) { | |||
917 | case 's': { | 1031 | case 's': { |
918 | size_t l; | 1032 | size_t l; |
919 | const char *s = luaL_tolstring(L, arg, &l); | 1033 | const char *s = luaL_tolstring(L, arg, &l); |
920 | if (!strchr(form, '.') && l >= 100) { | 1034 | if (form[2] == '\0') /* no modifiers? */ |
921 | /* no precision and string is too long to be formatted; | 1035 | luaL_addvalue(&b); /* keep entire string */ |
922 | keep original string */ | ||
923 | luaL_addvalue(&b); | ||
924 | break; | ||
925 | } | ||
926 | else { | 1036 | else { |
927 | nb = sprintf(buff, form, s); | 1037 | luaL_argcheck(L, l == strlen(s), arg, "string contains zeros"); |
928 | lua_pop(L, 1); /* remove result from 'luaL_tolstring' */ | 1038 | if (!strchr(form, '.') && l >= 100) { |
929 | break; | 1039 | /* no precision and string is too long to be formatted */ |
1040 | luaL_addvalue(&b); /* keep entire string */ | ||
1041 | } | ||
1042 | else { /* format the string into 'buff' */ | ||
1043 | nb = l_sprintf(buff, MAX_ITEM, form, s); | ||
1044 | lua_pop(L, 1); /* remove result from 'luaL_tolstring' */ | ||
1045 | } | ||
930 | } | 1046 | } |
1047 | break; | ||
931 | } | 1048 | } |
932 | default: { /* also treat cases 'pnLlh' */ | 1049 | default: { /* also treat cases 'pnLlh' */ |
933 | return luaL_error(L, "invalid option '%%%c' to 'format'", | 1050 | return luaL_error(L, "invalid option '%%%c' to 'format'", |
934 | *(strfrmt - 1)); | 1051 | *(strfrmt - 1)); |
935 | } | 1052 | } |
936 | } | 1053 | } |
1054 | lua_assert(nb < MAX_ITEM); | ||
937 | luaL_addsize(&b, nb); | 1055 | luaL_addsize(&b, nb); |
938 | } | 1056 | } |
939 | } | 1057 | } |
@@ -1225,8 +1343,13 @@ static int str_pack (lua_State *L) { | |||
1225 | case Kchar: { /* fixed-size string */ | 1343 | case Kchar: { /* fixed-size string */ |
1226 | size_t len; | 1344 | size_t len; |
1227 | const char *s = luaL_checklstring(L, arg, &len); | 1345 | const char *s = luaL_checklstring(L, arg, &len); |
1228 | luaL_argcheck(L, len == (size_t)size, arg, "wrong length"); | 1346 | if ((size_t)size <= len) /* string larger than (or equal to) needed? */ |
1229 | luaL_addlstring(&b, s, size); | 1347 | luaL_addlstring(&b, s, size); /* truncate string to asked size */ |
1348 | else { /* string smaller than needed */ | ||
1349 | luaL_addlstring(&b, s, len); /* add it all */ | ||
1350 | while (len++ < (size_t)size) /* pad extra space */ | ||
1351 | luaL_addchar(&b, LUA_PACKPADBYTE); | ||
1352 | } | ||
1230 | break; | 1353 | break; |
1231 | } | 1354 | } |
1232 | case Kstring: { /* strings with length count */ | 1355 | case Kstring: { /* strings with length count */ |
@@ -1249,7 +1372,7 @@ static int str_pack (lua_State *L) { | |||
1249 | totalsize += len + 1; | 1372 | totalsize += len + 1; |
1250 | break; | 1373 | break; |
1251 | } | 1374 | } |
1252 | case Kpadding: luaL_addchar(&b, LUA_PACKPADBYTE); /* go through */ | 1375 | case Kpadding: luaL_addchar(&b, LUA_PACKPADBYTE); /* FALLTHROUGH */ |
1253 | case Kpaddalign: case Knop: | 1376 | case Kpaddalign: case Knop: |
1254 | arg--; /* undo increment */ | 1377 | arg--; /* undo increment */ |
1255 | break; | 1378 | break; |
@@ -1276,7 +1399,7 @@ static int str_packsize (lua_State *L) { | |||
1276 | case Kstring: /* strings with length count */ | 1399 | case Kstring: /* strings with length count */ |
1277 | case Kzstr: /* zero-terminated string */ | 1400 | case Kzstr: /* zero-terminated string */ |
1278 | luaL_argerror(L, 1, "variable-length format"); | 1401 | luaL_argerror(L, 1, "variable-length format"); |
1279 | break; | 1402 | /* call never return, but to avoid warnings: *//* FALLTHROUGH */ |
1280 | default: break; | 1403 | default: break; |
1281 | } | 1404 | } |
1282 | } | 1405 | } |
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: ltablib.c,v 1.79 2014/11/02 19:19:04 roberto Exp $ | 2 | ** $Id: ltablib.c,v 1.90 2015/11/25 12:48:57 roberto Exp $ |
3 | ** Library for Table Manipulation | 3 | ** Library for Table Manipulation |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -12,6 +12,7 @@ | |||
12 | 12 | ||
13 | #include <limits.h> | 13 | #include <limits.h> |
14 | #include <stddef.h> | 14 | #include <stddef.h> |
15 | #include <string.h> | ||
15 | 16 | ||
16 | #include "lua.h" | 17 | #include "lua.h" |
17 | 18 | ||
@@ -19,42 +20,44 @@ | |||
19 | #include "lualib.h" | 20 | #include "lualib.h" |
20 | 21 | ||
21 | 22 | ||
22 | |||
23 | /* | 23 | /* |
24 | ** Structure with table-access functions | 24 | ** Operations that an object must define to mimic a table |
25 | ** (some functions only need some of them) | ||
25 | */ | 26 | */ |
26 | typedef struct { | 27 | #define TAB_R 1 /* read */ |
27 | int (*geti) (lua_State *L, int idx, lua_Integer n); | 28 | #define TAB_W 2 /* write */ |
28 | void (*seti) (lua_State *L, int idx, lua_Integer n); | 29 | #define TAB_L 4 /* length */ |
29 | } TabA; | 30 | #define TAB_RW (TAB_R | TAB_W) /* read/write */ |
31 | |||
32 | |||
33 | #define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) | ||
34 | |||
35 | |||
36 | static int checkfield (lua_State *L, const char *key, int n) { | ||
37 | lua_pushstring(L, key); | ||
38 | return (lua_rawget(L, -n) != LUA_TNIL); | ||
39 | } | ||
30 | 40 | ||
31 | 41 | ||
32 | /* | 42 | /* |
33 | ** Check that 'arg' has a table and set access functions in 'ta' to raw | 43 | ** Check that 'arg' either is a table or can behave like one (that is, |
34 | ** or non-raw according to the presence of corresponding metamethods. | 44 | ** has a metatable with the required metamethods) |
35 | */ | 45 | */ |
36 | static void checktab (lua_State *L, int arg, TabA *ta) { | 46 | static void checktab (lua_State *L, int arg, int what) { |
37 | ta->geti = NULL; ta->seti = NULL; | 47 | if (lua_type(L, arg) != LUA_TTABLE) { /* is it not a table? */ |
38 | if (lua_getmetatable(L, arg)) { | 48 | int n = 1; /* number of elements to pop */ |
39 | lua_pushliteral(L, "__index"); /* 'index' metamethod */ | 49 | if (lua_getmetatable(L, arg) && /* must have metatable */ |
40 | if (lua_rawget(L, -2) != LUA_TNIL) | 50 | (!(what & TAB_R) || checkfield(L, "__index", ++n)) && |
41 | ta->geti = lua_geti; | 51 | (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && |
42 | lua_pushliteral(L, "__newindex"); /* 'newindex' metamethod */ | 52 | (!(what & TAB_L) || checkfield(L, "__len", ++n))) { |
43 | if (lua_rawget(L, -3) != LUA_TNIL) | 53 | lua_pop(L, n); /* pop metatable and tested metamethods */ |
44 | ta->seti = lua_seti; | 54 | } |
45 | lua_pop(L, 3); /* pop metatable plus both metamethods */ | 55 | else |
46 | } | 56 | luaL_argerror(L, arg, "table expected"); /* force an error */ |
47 | if (ta->geti == NULL || ta->seti == NULL) { | ||
48 | luaL_checktype(L, arg, LUA_TTABLE); /* must be table for raw methods */ | ||
49 | if (ta->geti == NULL) ta->geti = lua_rawgeti; | ||
50 | if (ta->seti == NULL) ta->seti = lua_rawseti; | ||
51 | } | 57 | } |
52 | } | 58 | } |
53 | 59 | ||
54 | 60 | ||
55 | #define aux_getn(L,n,ta) (checktab(L, n, ta), luaL_len(L, n)) | ||
56 | |||
57 | |||
58 | #if defined(LUA_COMPAT_MAXN) | 61 | #if defined(LUA_COMPAT_MAXN) |
59 | static int maxn (lua_State *L) { | 62 | static int maxn (lua_State *L) { |
60 | lua_Number max = 0; | 63 | lua_Number max = 0; |
@@ -74,8 +77,7 @@ static int maxn (lua_State *L) { | |||
74 | 77 | ||
75 | 78 | ||
76 | static int tinsert (lua_State *L) { | 79 | static int tinsert (lua_State *L) { |
77 | TabA ta; | 80 | lua_Integer e = aux_getn(L, 1, TAB_RW) + 1; /* first empty element */ |
78 | lua_Integer e = aux_getn(L, 1, &ta) + 1; /* first empty element */ | ||
79 | lua_Integer pos; /* where to insert new element */ | 81 | lua_Integer pos; /* where to insert new element */ |
80 | switch (lua_gettop(L)) { | 82 | switch (lua_gettop(L)) { |
81 | case 2: { /* called with only 2 arguments */ | 83 | case 2: { /* called with only 2 arguments */ |
@@ -87,8 +89,8 @@ static int tinsert (lua_State *L) { | |||
87 | pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ | 89 | pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ |
88 | luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); | 90 | luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); |
89 | for (i = e; i > pos; i--) { /* move up elements */ | 91 | for (i = e; i > pos; i--) { /* move up elements */ |
90 | (*ta.geti)(L, 1, i - 1); | 92 | lua_geti(L, 1, i - 1); |
91 | (*ta.seti)(L, 1, i); /* t[i] = t[i - 1] */ | 93 | lua_seti(L, 1, i); /* t[i] = t[i - 1] */ |
92 | } | 94 | } |
93 | break; | 95 | break; |
94 | } | 96 | } |
@@ -96,55 +98,57 @@ static int tinsert (lua_State *L) { | |||
96 | return luaL_error(L, "wrong number of arguments to 'insert'"); | 98 | return luaL_error(L, "wrong number of arguments to 'insert'"); |
97 | } | 99 | } |
98 | } | 100 | } |
99 | (*ta.seti)(L, 1, pos); /* t[pos] = v */ | 101 | lua_seti(L, 1, pos); /* t[pos] = v */ |
100 | return 0; | 102 | return 0; |
101 | } | 103 | } |
102 | 104 | ||
103 | 105 | ||
104 | static int tremove (lua_State *L) { | 106 | static int tremove (lua_State *L) { |
105 | TabA ta; | 107 | lua_Integer size = aux_getn(L, 1, TAB_RW); |
106 | lua_Integer size = aux_getn(L, 1, &ta); | ||
107 | lua_Integer pos = luaL_optinteger(L, 2, size); | 108 | lua_Integer pos = luaL_optinteger(L, 2, size); |
108 | if (pos != size) /* validate 'pos' if given */ | 109 | if (pos != size) /* validate 'pos' if given */ |
109 | luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); | 110 | luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); |
110 | (*ta.geti)(L, 1, pos); /* result = t[pos] */ | 111 | lua_geti(L, 1, pos); /* result = t[pos] */ |
111 | for ( ; pos < size; pos++) { | 112 | for ( ; pos < size; pos++) { |
112 | (*ta.geti)(L, 1, pos + 1); | 113 | lua_geti(L, 1, pos + 1); |
113 | (*ta.seti)(L, 1, pos); /* t[pos] = t[pos + 1] */ | 114 | lua_seti(L, 1, pos); /* t[pos] = t[pos + 1] */ |
114 | } | 115 | } |
115 | lua_pushnil(L); | 116 | lua_pushnil(L); |
116 | (*ta.seti)(L, 1, pos); /* t[pos] = nil */ | 117 | lua_seti(L, 1, pos); /* t[pos] = nil */ |
117 | return 1; | 118 | return 1; |
118 | } | 119 | } |
119 | 120 | ||
120 | 121 | ||
122 | /* | ||
123 | ** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever | ||
124 | ** possible, copy in increasing order, which is better for rehashing. | ||
125 | ** "possible" means destination after original range, or smaller | ||
126 | ** than origin, or copying to another table. | ||
127 | */ | ||
121 | static int tmove (lua_State *L) { | 128 | static int tmove (lua_State *L) { |
122 | TabA ta; | ||
123 | lua_Integer f = luaL_checkinteger(L, 2); | 129 | lua_Integer f = luaL_checkinteger(L, 2); |
124 | lua_Integer e = luaL_checkinteger(L, 3); | 130 | lua_Integer e = luaL_checkinteger(L, 3); |
125 | lua_Integer t = luaL_checkinteger(L, 4); | 131 | lua_Integer t = luaL_checkinteger(L, 4); |
126 | int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */ | 132 | int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */ |
127 | /* the following restriction avoids several problems with overflows */ | 133 | checktab(L, 1, TAB_R); |
128 | luaL_argcheck(L, f > 0, 2, "initial position must be positive"); | 134 | checktab(L, tt, TAB_W); |
129 | if (e >= f) { /* otherwise, nothing to move */ | 135 | if (e >= f) { /* otherwise, nothing to move */ |
130 | lua_Integer n, i; | 136 | lua_Integer n, i; |
131 | ta.geti = (luaL_getmetafield(L, 1, "__index") == LUA_TNIL) | 137 | luaL_argcheck(L, f > 0 || e < LUA_MAXINTEGER + f, 3, |
132 | ? (luaL_checktype(L, 1, LUA_TTABLE), lua_rawgeti) | 138 | "too many elements to move"); |
133 | : lua_geti; | ||
134 | ta.seti = (luaL_getmetafield(L, tt, "__newindex") == LUA_TNIL) | ||
135 | ? (luaL_checktype(L, tt, LUA_TTABLE), lua_rawseti) | ||
136 | : lua_seti; | ||
137 | n = e - f + 1; /* number of elements to move */ | 139 | n = e - f + 1; /* number of elements to move */ |
138 | if (t > f) { | 140 | luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4, |
139 | for (i = n - 1; i >= 0; i--) { | 141 | "destination wrap around"); |
140 | (*ta.geti)(L, 1, f + i); | 142 | if (t > e || t <= f || tt != 1) { |
141 | (*ta.seti)(L, tt, t + i); | 143 | for (i = 0; i < n; i++) { |
144 | lua_geti(L, 1, f + i); | ||
145 | lua_seti(L, tt, t + i); | ||
142 | } | 146 | } |
143 | } | 147 | } |
144 | else { | 148 | else { |
145 | for (i = 0; i < n; i++) { | 149 | for (i = n - 1; i >= 0; i--) { |
146 | (*ta.geti)(L, 1, f + i); | 150 | lua_geti(L, 1, f + i); |
147 | (*ta.seti)(L, tt, t + i); | 151 | lua_seti(L, tt, t + i); |
148 | } | 152 | } |
149 | } | 153 | } |
150 | } | 154 | } |
@@ -153,8 +157,8 @@ static int tmove (lua_State *L) { | |||
153 | } | 157 | } |
154 | 158 | ||
155 | 159 | ||
156 | static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) { | 160 | static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) { |
157 | (*ta->geti)(L, 1, i); | 161 | lua_geti(L, 1, i); |
158 | if (!lua_isstring(L, -1)) | 162 | if (!lua_isstring(L, -1)) |
159 | luaL_error(L, "invalid value (%s) at index %d in table for 'concat'", | 163 | luaL_error(L, "invalid value (%s) at index %d in table for 'concat'", |
160 | luaL_typename(L, -1), i); | 164 | luaL_typename(L, -1), i); |
@@ -163,21 +167,19 @@ static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) { | |||
163 | 167 | ||
164 | 168 | ||
165 | static int tconcat (lua_State *L) { | 169 | static int tconcat (lua_State *L) { |
166 | TabA ta; | ||
167 | luaL_Buffer b; | 170 | luaL_Buffer b; |
171 | lua_Integer last = aux_getn(L, 1, TAB_R); | ||
168 | size_t lsep; | 172 | size_t lsep; |
169 | lua_Integer i, last; | ||
170 | const char *sep = luaL_optlstring(L, 2, "", &lsep); | 173 | const char *sep = luaL_optlstring(L, 2, "", &lsep); |
171 | checktab(L, 1, &ta); | 174 | lua_Integer i = luaL_optinteger(L, 3, 1); |
172 | i = luaL_optinteger(L, 3, 1); | 175 | last = luaL_opt(L, luaL_checkinteger, 4, last); |
173 | last = luaL_opt(L, luaL_checkinteger, 4, luaL_len(L, 1)); | ||
174 | luaL_buffinit(L, &b); | 176 | luaL_buffinit(L, &b); |
175 | for (; i < last; i++) { | 177 | for (; i < last; i++) { |
176 | addfield(L, &b, &ta, i); | 178 | addfield(L, &b, i); |
177 | luaL_addlstring(&b, sep, lsep); | 179 | luaL_addlstring(&b, sep, lsep); |
178 | } | 180 | } |
179 | if (i == last) /* add last value (if interval was not empty) */ | 181 | if (i == last) /* add last value (if interval was not empty) */ |
180 | addfield(L, &b, &ta, i); | 182 | addfield(L, &b, i); |
181 | luaL_pushresult(&b); | 183 | luaL_pushresult(&b); |
182 | return 1; | 184 | return 1; |
183 | } | 185 | } |
@@ -195,7 +197,7 @@ static int pack (lua_State *L) { | |||
195 | lua_createtable(L, n, 1); /* create result table */ | 197 | lua_createtable(L, n, 1); /* create result table */ |
196 | lua_insert(L, 1); /* put it at index 1 */ | 198 | lua_insert(L, 1); /* put it at index 1 */ |
197 | for (i = n; i >= 1; i--) /* assign elements */ | 199 | for (i = n; i >= 1; i--) /* assign elements */ |
198 | lua_rawseti(L, 1, i); | 200 | lua_seti(L, 1, i); |
199 | lua_pushinteger(L, n); | 201 | lua_pushinteger(L, n); |
200 | lua_setfield(L, 1, "n"); /* t.n = number of elements */ | 202 | lua_setfield(L, 1, "n"); /* t.n = number of elements */ |
201 | return 1; /* return table */ | 203 | return 1; /* return table */ |
@@ -203,20 +205,17 @@ static int pack (lua_State *L) { | |||
203 | 205 | ||
204 | 206 | ||
205 | static int unpack (lua_State *L) { | 207 | static int unpack (lua_State *L) { |
206 | TabA ta; | ||
207 | lua_Integer i, e; | ||
208 | lua_Unsigned n; | 208 | lua_Unsigned n; |
209 | checktab(L, 1, &ta); | 209 | lua_Integer i = luaL_optinteger(L, 2, 1); |
210 | i = luaL_optinteger(L, 2, 1); | 210 | lua_Integer e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); |
211 | e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); | ||
212 | if (i > e) return 0; /* empty range */ | 211 | if (i > e) return 0; /* empty range */ |
213 | n = (lua_Unsigned)e - i; /* number of elements minus 1 (avoid overflows) */ | 212 | n = (lua_Unsigned)e - i; /* number of elements minus 1 (avoid overflows) */ |
214 | if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, (int)(++n))) | 213 | if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, (int)(++n))) |
215 | return luaL_error(L, "too many results to unpack"); | 214 | return luaL_error(L, "too many results to unpack"); |
216 | do { /* must have at least one element */ | 215 | for (; i < e; i++) { /* push arg[i..e - 1] (to avoid overflows) */ |
217 | (*ta.geti)(L, 1, i); /* push arg[i..e] */ | 216 | lua_geti(L, 1, i); |
218 | } while (i++ < e); | 217 | } |
219 | 218 | lua_geti(L, 1, e); /* push last element */ | |
220 | return (int)n; | 219 | return (int)n; |
221 | } | 220 | } |
222 | 221 | ||
@@ -233,97 +232,190 @@ static int unpack (lua_State *L) { | |||
233 | */ | 232 | */ |
234 | 233 | ||
235 | 234 | ||
236 | static void set2 (lua_State *L, TabA *ta, int i, int j) { | 235 | /* |
237 | (*ta->seti)(L, 1, i); | 236 | ** Produce a "random" 'unsigned int' to randomize pivot choice. This |
238 | (*ta->seti)(L, 1, j); | 237 | ** macro is used only when 'sort' detects a big imbalance in the result |
238 | ** of a partition. (If you don't want/need this "randomness", ~0 is a | ||
239 | ** good choice.) | ||
240 | */ | ||
241 | #if !defined(l_randomizePivot) /* { */ | ||
242 | |||
243 | #include <time.h> | ||
244 | |||
245 | /* size of 'e' measured in number of 'unsigned int's */ | ||
246 | #define sof(e) (sizeof(e) / sizeof(unsigned int)) | ||
247 | |||
248 | /* | ||
249 | ** Use 'time' and 'clock' as sources of "randomness". Because we don't | ||
250 | ** know the types 'clock_t' and 'time_t', we cannot cast them to | ||
251 | ** anything without risking overflows. A safe way to use their values | ||
252 | ** is to copy them to an array of a known type and use the array values. | ||
253 | */ | ||
254 | static unsigned int l_randomizePivot (void) { | ||
255 | clock_t c = clock(); | ||
256 | time_t t = time(NULL); | ||
257 | unsigned int buff[sof(c) + sof(t)]; | ||
258 | unsigned int i, rnd = 0; | ||
259 | memcpy(buff, &c, sof(c) * sizeof(unsigned int)); | ||
260 | memcpy(buff + sof(c), &t, sof(t) * sizeof(unsigned int)); | ||
261 | for (i = 0; i < sof(buff); i++) | ||
262 | rnd += buff[i]; | ||
263 | return rnd; | ||
264 | } | ||
265 | |||
266 | #endif /* } */ | ||
267 | |||
268 | |||
269 | /* arrays larger than 'RANLIMIT' may use randomized pivots */ | ||
270 | #define RANLIMIT 100u | ||
271 | |||
272 | |||
273 | static void set2 (lua_State *L, unsigned int i, unsigned int j) { | ||
274 | lua_seti(L, 1, i); | ||
275 | lua_seti(L, 1, j); | ||
239 | } | 276 | } |
240 | 277 | ||
278 | |||
279 | /* | ||
280 | ** Return true iff value at stack index 'a' is less than the value at | ||
281 | ** index 'b' (according to the order of the sort). | ||
282 | */ | ||
241 | static int sort_comp (lua_State *L, int a, int b) { | 283 | static int sort_comp (lua_State *L, int a, int b) { |
242 | if (!lua_isnil(L, 2)) { /* function? */ | 284 | if (lua_isnil(L, 2)) /* no function? */ |
285 | return lua_compare(L, a, b, LUA_OPLT); /* a < b */ | ||
286 | else { /* function */ | ||
243 | int res; | 287 | int res; |
244 | lua_pushvalue(L, 2); | 288 | lua_pushvalue(L, 2); /* push function */ |
245 | lua_pushvalue(L, a-1); /* -1 to compensate function */ | 289 | lua_pushvalue(L, a-1); /* -1 to compensate function */ |
246 | lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ | 290 | lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ |
247 | lua_call(L, 2, 1); | 291 | lua_call(L, 2, 1); /* call function */ |
248 | res = lua_toboolean(L, -1); | 292 | res = lua_toboolean(L, -1); /* get result */ |
249 | lua_pop(L, 1); | 293 | lua_pop(L, 1); /* pop result */ |
250 | return res; | 294 | return res; |
251 | } | 295 | } |
252 | else /* a < b? */ | ||
253 | return lua_compare(L, a, b, LUA_OPLT); | ||
254 | } | 296 | } |
255 | 297 | ||
256 | static void auxsort (lua_State *L, TabA *ta, int l, int u) { | 298 | |
257 | while (l < u) { /* for tail recursion */ | 299 | /* |
258 | int i, j; | 300 | ** Does the partition: Pivot P is at the top of the stack. |
259 | /* sort elements a[l], a[(l+u)/2] and a[u] */ | 301 | ** precondition: a[lo] <= P == a[up-1] <= a[up], |
260 | (*ta->geti)(L, 1, l); | 302 | ** so it only needs to do the partition from lo + 1 to up - 2. |
261 | (*ta->geti)(L, 1, u); | 303 | ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] |
262 | if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ | 304 | ** returns 'i'. |
263 | set2(L, ta, l, u); /* swap a[l] - a[u] */ | 305 | */ |
306 | static unsigned int partition (lua_State *L, unsigned int lo, | ||
307 | unsigned int up) { | ||
308 | unsigned int i = lo; /* will be incremented before first use */ | ||
309 | unsigned int j = up - 1; /* will be decremented before first use */ | ||
310 | /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ | ||
311 | for (;;) { | ||
312 | /* next loop: repeat ++i while a[i] < P */ | ||
313 | while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { | ||
314 | if (i == up - 1) /* a[i] < P but a[up - 1] == P ?? */ | ||
315 | luaL_error(L, "invalid order function for sorting"); | ||
316 | lua_pop(L, 1); /* remove a[i] */ | ||
317 | } | ||
318 | /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ | ||
319 | /* next loop: repeat --j while P < a[j] */ | ||
320 | while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { | ||
321 | if (j < i) /* j < i but a[j] > P ?? */ | ||
322 | luaL_error(L, "invalid order function for sorting"); | ||
323 | lua_pop(L, 1); /* remove a[j] */ | ||
324 | } | ||
325 | /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ | ||
326 | if (j < i) { /* no elements out of place? */ | ||
327 | /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ | ||
328 | lua_pop(L, 1); /* pop a[j] */ | ||
329 | /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ | ||
330 | set2(L, up - 1, i); | ||
331 | return i; | ||
332 | } | ||
333 | /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ | ||
334 | set2(L, i, j); | ||
335 | } | ||
336 | } | ||
337 | |||
338 | |||
339 | /* | ||
340 | ** Choose an element in the middle (2nd-3th quarters) of [lo,up] | ||
341 | ** "randomized" by 'rnd' | ||
342 | */ | ||
343 | static unsigned int choosePivot (unsigned int lo, unsigned int up, | ||
344 | unsigned int rnd) { | ||
345 | unsigned int r4 = (unsigned int)(up - lo) / 4u; /* range/4 */ | ||
346 | unsigned int p = rnd % (r4 * 2) + (lo + r4); | ||
347 | lua_assert(lo + r4 <= p && p <= up - r4); | ||
348 | return p; | ||
349 | } | ||
350 | |||
351 | |||
352 | /* | ||
353 | ** QuickSort algorithm (recursive function) | ||
354 | */ | ||
355 | static void auxsort (lua_State *L, unsigned int lo, unsigned int up, | ||
356 | unsigned int rnd) { | ||
357 | while (lo < up) { /* loop for tail recursion */ | ||
358 | unsigned int p; /* Pivot index */ | ||
359 | unsigned int n; /* to be used later */ | ||
360 | /* sort elements 'lo', 'p', and 'up' */ | ||
361 | lua_geti(L, 1, lo); | ||
362 | lua_geti(L, 1, up); | ||
363 | if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ | ||
364 | set2(L, lo, up); /* swap a[lo] - a[up] */ | ||
264 | else | 365 | else |
265 | lua_pop(L, 2); | 366 | lua_pop(L, 2); /* remove both values */ |
266 | if (u-l == 1) break; /* only 2 elements */ | 367 | if (up - lo == 1) /* only 2 elements? */ |
267 | i = (l+u)/2; | 368 | return; /* already sorted */ |
268 | (*ta->geti)(L, 1, i); | 369 | if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ |
269 | (*ta->geti)(L, 1, l); | 370 | p = (lo + up)/2; /* middle element is a good pivot */ |
270 | if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */ | 371 | else /* for larger intervals, it is worth a random pivot */ |
271 | set2(L, ta, i, l); | 372 | p = choosePivot(lo, up, rnd); |
373 | lua_geti(L, 1, p); | ||
374 | lua_geti(L, 1, lo); | ||
375 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ | ||
376 | set2(L, p, lo); /* swap a[p] - a[lo] */ | ||
272 | else { | 377 | else { |
273 | lua_pop(L, 1); /* remove a[l] */ | 378 | lua_pop(L, 1); /* remove a[lo] */ |
274 | (*ta->geti)(L, 1, u); | 379 | lua_geti(L, 1, up); |
275 | if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ | 380 | if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ |
276 | set2(L, ta, i, u); | 381 | set2(L, p, up); /* swap a[up] - a[p] */ |
277 | else | 382 | else |
278 | lua_pop(L, 2); | 383 | lua_pop(L, 2); |
279 | } | 384 | } |
280 | if (u-l == 2) break; /* only 3 elements */ | 385 | if (up - lo == 2) /* only 3 elements? */ |
281 | (*ta->geti)(L, 1, i); /* Pivot */ | 386 | return; /* already sorted */ |
282 | lua_pushvalue(L, -1); | 387 | lua_geti(L, 1, p); /* get middle element (Pivot) */ |
283 | (*ta->geti)(L, 1, u-1); | 388 | lua_pushvalue(L, -1); /* push Pivot */ |
284 | set2(L, ta, i, u-1); | 389 | lua_geti(L, 1, up - 1); /* push a[up - 1] */ |
285 | /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ | 390 | set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ |
286 | i = l; j = u-1; | 391 | p = partition(L, lo, up); |
287 | for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ | 392 | /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ |
288 | /* repeat ++i until a[i] >= P */ | 393 | if (p - lo < up - p) { /* lower interval is smaller? */ |
289 | while ((*ta->geti)(L, 1, ++i), sort_comp(L, -1, -2)) { | 394 | auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ |
290 | if (i>=u) luaL_error(L, "invalid order function for sorting"); | 395 | n = p - lo; /* size of smaller interval */ |
291 | lua_pop(L, 1); /* remove a[i] */ | 396 | lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ |
292 | } | ||
293 | /* repeat --j until a[j] <= P */ | ||
294 | while ((*ta->geti)(L, 1, --j), sort_comp(L, -3, -1)) { | ||
295 | if (j<=l) luaL_error(L, "invalid order function for sorting"); | ||
296 | lua_pop(L, 1); /* remove a[j] */ | ||
297 | } | ||
298 | if (j<i) { | ||
299 | lua_pop(L, 3); /* pop pivot, a[i], a[j] */ | ||
300 | break; | ||
301 | } | ||
302 | set2(L, ta, i, j); | ||
303 | } | ||
304 | (*ta->geti)(L, 1, u-1); | ||
305 | (*ta->geti)(L, 1, i); | ||
306 | set2(L, ta, u-1, i); /* swap pivot (a[u-1]) with a[i] */ | ||
307 | /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ | ||
308 | /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ | ||
309 | if (i-l < u-i) { | ||
310 | j=l; i=i-1; l=i+2; | ||
311 | } | 397 | } |
312 | else { | 398 | else { |
313 | j=i+1; i=u; u=j-2; | 399 | auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ |
400 | n = up - p; /* size of smaller interval */ | ||
401 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ | ||
314 | } | 402 | } |
315 | auxsort(L, ta, j, i); /* call recursively the smaller one */ | 403 | if ((up - lo) / 128u > n) /* partition too imbalanced? */ |
316 | } /* repeat the routine for the larger one */ | 404 | rnd = l_randomizePivot(); /* try a new randomization */ |
405 | } /* tail call auxsort(L, lo, up, rnd) */ | ||
317 | } | 406 | } |
318 | 407 | ||
408 | |||
319 | static int sort (lua_State *L) { | 409 | static int sort (lua_State *L) { |
320 | TabA ta; | 410 | lua_Integer n = aux_getn(L, 1, TAB_RW); |
321 | int n = (int)aux_getn(L, 1, &ta); | 411 | if (n > 1) { /* non-trivial interval? */ |
322 | luaL_checkstack(L, 50, ""); /* assume array is smaller than 2^50 */ | 412 | luaL_argcheck(L, n < INT_MAX, 1, "array too big"); |
323 | if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ | 413 | luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */ |
324 | luaL_checktype(L, 2, LUA_TFUNCTION); | 414 | if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ |
325 | lua_settop(L, 2); /* make sure there are two arguments */ | 415 | luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ |
326 | auxsort(L, &ta, 1, n); | 416 | lua_settop(L, 2); /* make sure there are two arguments */ |
417 | auxsort(L, 1, (unsigned int)n, 0u); | ||
418 | } | ||
327 | return 0; | 419 | return 0; |
328 | } | 420 | } |
329 | 421 | ||
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lutf8lib.c,v 1.13 2014/11/02 19:19:04 roberto Exp $ | 2 | ** $Id: lutf8lib.c,v 1.15 2015/03/28 19:16:55 roberto Exp $ |
3 | ** Standard library for UTF-8 manipulation | 3 | ** Standard library for UTF-8 manipulation |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -11,6 +11,7 @@ | |||
11 | 11 | ||
12 | 12 | ||
13 | #include <assert.h> | 13 | #include <assert.h> |
14 | #include <limits.h> | ||
14 | #include <stdlib.h> | 15 | #include <stdlib.h> |
15 | #include <string.h> | 16 | #include <string.h> |
16 | 17 | ||
@@ -37,7 +38,7 @@ static lua_Integer u_posrelat (lua_Integer pos, size_t len) { | |||
37 | ** Decode one UTF-8 sequence, returning NULL if byte sequence is invalid. | 38 | ** Decode one UTF-8 sequence, returning NULL if byte sequence is invalid. |
38 | */ | 39 | */ |
39 | static const char *utf8_decode (const char *o, int *val) { | 40 | static const char *utf8_decode (const char *o, int *val) { |
40 | static unsigned int limits[] = {0xFF, 0x7F, 0x7FF, 0xFFFF}; | 41 | static const unsigned int limits[] = {0xFF, 0x7F, 0x7FF, 0xFFFF}; |
41 | const unsigned char *s = (const unsigned char *)o; | 42 | const unsigned char *s = (const unsigned char *)o; |
42 | unsigned int c = s[0]; | 43 | unsigned int c = s[0]; |
43 | unsigned int res = 0; /* final result */ | 44 | unsigned int res = 0; /* final result */ |
@@ -106,9 +107,9 @@ static int codepoint (lua_State *L) { | |||
106 | luaL_argcheck(L, posi >= 1, 2, "out of range"); | 107 | luaL_argcheck(L, posi >= 1, 2, "out of range"); |
107 | luaL_argcheck(L, pose <= (lua_Integer)len, 3, "out of range"); | 108 | luaL_argcheck(L, pose <= (lua_Integer)len, 3, "out of range"); |
108 | if (posi > pose) return 0; /* empty interval; return no values */ | 109 | if (posi > pose) return 0; /* empty interval; return no values */ |
109 | n = (int)(pose - posi + 1); | 110 | if (pose - posi >= INT_MAX) /* (lua_Integer -> int) overflow? */ |
110 | if (posi + n <= pose) /* (lua_Integer -> int) overflow? */ | ||
111 | return luaL_error(L, "string slice too long"); | 111 | return luaL_error(L, "string slice too long"); |
112 | n = (int)(pose - posi) + 1; | ||
112 | luaL_checkstack(L, n, "string slice too long"); | 113 | luaL_checkstack(L, n, "string slice too long"); |
113 | n = 0; | 114 | n = 0; |
114 | se = s + pose; | 115 | se = s + pose; |
@@ -234,7 +235,7 @@ static int iter_codes (lua_State *L) { | |||
234 | #define UTF8PATT "[\0-\x7F\xC2-\xF4][\x80-\xBF]*" | 235 | #define UTF8PATT "[\0-\x7F\xC2-\xF4][\x80-\xBF]*" |
235 | 236 | ||
236 | 237 | ||
237 | static struct luaL_Reg funcs[] = { | 238 | static const luaL_Reg funcs[] = { |
238 | {"offset", byteoffset}, | 239 | {"offset", byteoffset}, |
239 | {"codepoint", codepoint}, | 240 | {"codepoint", codepoint}, |
240 | {"char", utfchar}, | 241 | {"char", utfchar}, |
@@ -248,7 +249,7 @@ static struct luaL_Reg funcs[] = { | |||
248 | 249 | ||
249 | LUAMOD_API int luaopen_utf8 (lua_State *L) { | 250 | LUAMOD_API int luaopen_utf8 (lua_State *L) { |
250 | luaL_newlib(L, funcs); | 251 | luaL_newlib(L, funcs); |
251 | lua_pushliteral(L, UTF8PATT); | 252 | lua_pushlstring(L, UTF8PATT, sizeof(UTF8PATT)/sizeof(char) - 1); |
252 | lua_setfield(L, -2, "charpattern"); | 253 | lua_setfield(L, -2, "charpattern"); |
253 | return 1; | 254 | return 1; |
254 | } | 255 | } |