aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPhilipp Janda <siffiejoe@gmx.net>2016-01-22 15:58:48 +0100
committerPhilipp Janda <siffiejoe@gmx.net>2016-01-22 15:58:48 +0100
commitca85188590e677edcc9290d29e69a3692187c826 (patch)
tree6223894654ff62468f1086423caf31f459e7861b
parentabf4ea9645ce3ff0c390a57ab3e3e4f82d9a4035 (diff)
downloadlua-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.h58
-rw-r--r--lstrlib.c277
-rw-r--r--ltablib.c378
-rw-r--r--lutf8lib.c13
4 files changed, 485 insertions, 241 deletions
diff --git a/lprefix.h b/lprefix.h
index aa1350b..cba5bbc 100644
--- a/lprefix.h
+++ b/lprefix.h
@@ -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
89static 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
94static 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
117static int str_pack (lua_State *L); 137static int str_pack (lua_State *L);
118static int str_packsize (lua_State *L); 138static int str_packsize (lua_State *L);
119static int str_unpack (lua_State *L); 139static 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
diff --git a/lstrlib.c b/lstrlib.c
index a650b76..fe30e34 100644
--- a/lstrlib.c
+++ b/lstrlib.c
@@ -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
209typedef struct MatchState { 212typedef 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
603static 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
617static void reprepstate (MatchState *ms) {
618 ms->level = 0;
619 lua_assert(ms->matchdepth == MAXCCALLS);
620}
621
622
586static int str_find_aux (lua_State *L, int find) { 623static 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' */
681typedef struct GMatchState {
682 const char *src; /* current position */
683 const char *p; /* pattern */
684 MatchState ms; /* match state */
685} GMatchState;
686
687
648static int gmatch_aux (lua_State *L) { 688static 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
677static int gmatch (lua_State *L) { 706static 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*/
851static 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
859static 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
890static 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
813static void addquoted (lua_State *L, luaL_Buffer *b, int arg) { 925static 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 }
diff --git a/ltablib.c b/ltablib.c
index 8f78afb..b3c9a7c 100644
--- a/ltablib.c
+++ b/ltablib.c
@@ -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*/
26typedef 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
36static 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*/
36static void checktab (lua_State *L, int arg, TabA *ta) { 46static 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)
59static int maxn (lua_State *L) { 62static 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
76static int tinsert (lua_State *L) { 79static 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
104static int tremove (lua_State *L) { 106static 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*/
121static int tmove (lua_State *L) { 128static 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
156static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) { 160static 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
165static int tconcat (lua_State *L) { 169static 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
205static int unpack (lua_State *L) { 207static 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
236static 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*/
254static 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
273static 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*/
241static int sort_comp (lua_State *L, int a, int b) { 283static 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
256static 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*/
306static 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*/
343static 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*/
355static 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
319static int sort (lua_State *L) { 409static 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
diff --git a/lutf8lib.c b/lutf8lib.c
index be4f087..9042582 100644
--- a/lutf8lib.c
+++ b/lutf8lib.c
@@ -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*/
39static const char *utf8_decode (const char *o, int *val) { 40static 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
237static struct luaL_Reg funcs[] = { 238static 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
249LUAMOD_API int luaopen_utf8 (lua_State *L) { 250LUAMOD_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}