From ca85188590e677edcc9290d29e69a3692187c826 Mon Sep 17 00:00:00 2001 From: Philipp Janda Date: Fri, 22 Jan 2016 15:58:48 +0100 Subject: Update backports. The backports of lstrlib.c, ltablib.c, and lutf8lib.c have been updated to Lua version 5.3.2. --- lprefix.h | 58 +++++++--- lstrlib.c | 277 +++++++++++++++++++++++++++++++------------- ltablib.c | 378 ++++++++++++++++++++++++++++++++++++++----------------------- lutf8lib.c | 13 ++- 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 @@ #undef LUAMOD_API #define LUAMOD_API extern + #ifdef lutf8lib_c # define luaopen_utf8 luaopen_compat53_utf8 # include @@ -81,24 +82,18 @@ static const char *compat53_utf8_escape (lua_State* L, ...) { compat53_utf8_escape(L, l) #endif + #ifdef ltablib_c # define luaopen_table luaopen_compat53_table -/* lua_rawgeti in compat53.h is implemented as a macro, so the - * function signature doesn't match when you use a function pointer - */ -static int compat53_rawgeti (lua_State *L, int i, lua_Integer n) { - return lua_rawgeti(L, i, n); -} -# undef lua_rawgeti -# define lua_rawgeti compat53_rawgeti -static void compat53_rawseti (lua_State *L, int i, lua_Integer n) { - lua_rawseti(L, i, (int)n); -} -# undef lua_rawseti -# define lua_rawseti compat53_rawseti +# ifndef LUA_MAXINTEGER +/* conservative estimate: */ +# define LUA_MAXINTEGER INT_MAX +# endif #endif /* ltablib_c */ + #ifdef lstrlib_c +#include #include /* move the string library open function out of the way (we only take * the string packing functions)! @@ -112,8 +107,33 @@ static void compat53_rawseti (lua_State *L, int i, lua_Integer n) { # if LUA_VERSION_NUM < 503 /* lstrlib assumes that lua_Integer and lua_Unsigned have the same * size, so we use the unsigned equivalent of ptrdiff_t! */ -# define lua_Unsigned size_t +# define lua_Unsigned size_t # endif +# ifndef l_mathlim +# ifdef LUA_NUMBER_DOUBLE +# define l_mathlim(n) (DBL_##n) +# else +# define l_mathlim(n) (FLT_##n) +# endif +# endif +# ifndef l_mathop +# ifdef LUA_NUMBER_DOUBLE +# define l_mathop(op) op +# else +# define l_mathop(op) op##f +# endif +# endif +# ifndef lua_getlocaledecpoint +# define lua_getlocaledecpoint() (localeconv()->decimal_point[0]) +# endif +# ifndef l_sprintf +# if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L +# define l_sprintf(s,sz,f,i) (snprintf(s, sz, f, i)) +# else +# define l_sprintf(s,sz,f,i) ((void)(sz), sprintf(s, f, i)) +# endif +# endif + static int str_pack (lua_State *L); static int str_packsize (lua_State *L); static int str_unpack (lua_State *L); @@ -127,12 +147,20 @@ LUAMOD_API int luaopen_compat53_string (lua_State *L) { luaL_newlib(L, funcs); return 1; } +/* fake CLANG feature detection on other compilers */ +# ifndef __has_attribute +# define __has_attribute(x) 0 +# endif /* make luaopen_string(_XXX) static, so it (and all other referenced * string functions) won't be included in the resulting dll * (hopefully). */ # undef LUAMOD_API -# define LUAMOD_API static +# if defined(__GNUC__) || __has_attribute(__unused__) +# define LUAMOD_API __attribute__((__unused__)) static +# else +# define LUAMOD_API static +# endif #endif /* lstrlib.c */ #endif diff --git a/lstrlib.c b/lstrlib.c index a650b76..fe30e34 100644 --- a/lstrlib.c +++ b/lstrlib.c @@ -1,5 +1,5 @@ /* -** $Id: lstrlib.c,v 1.221 2014/12/11 14:03:07 roberto Exp $ +** $Id: lstrlib.c,v 1.239 2015/11/25 16:28:17 roberto Exp $ ** Standard library for string operations and pattern-matching ** See Copyright Notice in lua.h */ @@ -11,6 +11,7 @@ #include +#include #include #include #include @@ -40,8 +41,10 @@ ** Some sizes are better limited to fit in 'int', but must also fit in ** 'size_t'. (We assume that 'lua_Integer' cannot be smaller than 'int'.) */ +#define MAX_SIZET ((size_t)(~(size_t)0)) + #define MAXSIZE \ - (sizeof(size_t) < sizeof(int) ? (~(size_t)0) : (size_t)(INT_MAX)) + (sizeof(size_t) < sizeof(int) ? MAX_SIZET : (size_t)(INT_MAX)) @@ -70,7 +73,7 @@ static int str_sub (lua_State *L) { if (start < 1) start = 1; if (end > (lua_Integer)l) end = l; if (start <= end) - lua_pushlstring(L, s + start - 1, (size_t)(end - start + 1)); + lua_pushlstring(L, s + start - 1, (size_t)(end - start) + 1); else lua_pushliteral(L, ""); return 1; } @@ -149,9 +152,9 @@ static int str_byte (lua_State *L) { if (posi < 1) posi = 1; if (pose > (lua_Integer)l) pose = l; if (posi > pose) return 0; /* empty interval; return no values */ - n = (int)(pose - posi + 1); - if (posi + n <= pose) /* arithmetic overflow? */ + if (pose - posi >= INT_MAX) /* arithmetic overflow? */ return luaL_error(L, "string slice too long"); + n = (int)(pose - posi) + 1; luaL_checkstack(L, n, "string slice too long"); for (i=0; inrep-- == 0) + luaL_error(ms->L, "pattern too complex"); switch (*ep) { /* handle optional suffix */ case '?': { /* optional */ const char *res; @@ -499,7 +516,7 @@ static const char *match (MatchState *ms, const char *s, const char *p) { } case '+': /* 1 or more repetitions */ s++; /* 1 match already done */ - /* go through */ + /* FALLTHROUGH */ case '*': /* 0 or more repetitions */ s = max_expand(ms, s, p, ep); break; @@ -554,7 +571,7 @@ static void push_onecapture (MatchState *ms, int i, const char *s, ptrdiff_t l = ms->capture[i].len; if (l == CAP_UNFINISHED) luaL_error(ms->L, "unfinished capture"); if (l == CAP_POSITION) - lua_pushinteger(ms->L, ms->capture[i].init - ms->src_init + 1); + lua_pushinteger(ms->L, (ms->capture[i].init - ms->src_init) + 1); else lua_pushlstring(ms->L, ms->capture[i].init, l); } @@ -583,6 +600,26 @@ static int nospecials (const char *p, size_t l) { } +static void prepstate (MatchState *ms, lua_State *L, + const char *s, size_t ls, const char *p, size_t lp) { + ms->L = L; + ms->matchdepth = MAXCCALLS; + ms->src_init = s; + ms->src_end = s + ls; + ms->p_end = p + lp; + if (ls < (MAX_SIZET - B_REPS) / A_REPS) + ms->nrep = A_REPS * ls + B_REPS; + else /* overflow (very long subject) */ + ms->nrep = MAX_SIZET; /* no limit */ +} + + +static void reprepstate (MatchState *ms) { + ms->level = 0; + lua_assert(ms->matchdepth == MAXCCALLS); +} + + static int str_find_aux (lua_State *L, int find) { size_t ls, lp; const char *s = luaL_checklstring(L, 1, &ls); @@ -598,8 +635,8 @@ static int str_find_aux (lua_State *L, int find) { /* do a plain search */ const char *s2 = lmemfind(s + init - 1, ls - (size_t)init + 1, p, lp); if (s2) { - lua_pushinteger(L, s2 - s + 1); - lua_pushinteger(L, s2 - s + lp); + lua_pushinteger(L, (s2 - s) + 1); + lua_pushinteger(L, (s2 - s) + lp); return 2; } } @@ -610,18 +647,13 @@ static int str_find_aux (lua_State *L, int find) { if (anchor) { p++; lp--; /* skip anchor character */ } - ms.L = L; - ms.matchdepth = MAXCCALLS; - ms.src_init = s; - ms.src_end = s + ls; - ms.p_end = p + lp; + prepstate(&ms, L, s, ls, p, lp); do { const char *res; - ms.level = 0; - lua_assert(ms.matchdepth == MAXCCALLS); + reprepstate(&ms); if ((res=match(&ms, s1, p)) != NULL) { if (find) { - lua_pushinteger(L, s1 - s + 1); /* start */ + lua_pushinteger(L, (s1 - s) + 1); /* start */ lua_pushinteger(L, res - s); /* end */ return push_captures(&ms, NULL, 0) + 2; } @@ -645,29 +677,26 @@ static int str_match (lua_State *L) { } +/* state for 'gmatch' */ +typedef struct GMatchState { + const char *src; /* current position */ + const char *p; /* pattern */ + MatchState ms; /* match state */ +} GMatchState; + + static int gmatch_aux (lua_State *L) { - MatchState ms; - size_t ls, lp; - const char *s = lua_tolstring(L, lua_upvalueindex(1), &ls); - const char *p = lua_tolstring(L, lua_upvalueindex(2), &lp); + GMatchState *gm = (GMatchState *)lua_touserdata(L, lua_upvalueindex(3)); const char *src; - ms.L = L; - ms.matchdepth = MAXCCALLS; - ms.src_init = s; - ms.src_end = s+ls; - ms.p_end = p + lp; - for (src = s + (size_t)lua_tointeger(L, lua_upvalueindex(3)); - src <= ms.src_end; - src++) { + for (src = gm->src; src <= gm->ms.src_end; src++) { const char *e; - ms.level = 0; - lua_assert(ms.matchdepth == MAXCCALLS); - if ((e = match(&ms, src, p)) != NULL) { - lua_Integer newstart = e-s; - if (e == src) newstart++; /* empty match? go at least one position */ - lua_pushinteger(L, newstart); - lua_replace(L, lua_upvalueindex(3)); - return push_captures(&ms, src, e); + reprepstate(&gm->ms); + if ((e = match(&gm->ms, src, gm->p)) != NULL) { + if (e == src) /* empty match? */ + gm->src =src + 1; /* go at least one position */ + else + gm->src = e; + return push_captures(&gm->ms, src, e); } } return 0; /* not found */ @@ -675,10 +704,14 @@ static int gmatch_aux (lua_State *L) { static int gmatch (lua_State *L) { - luaL_checkstring(L, 1); - luaL_checkstring(L, 2); - lua_settop(L, 2); - lua_pushinteger(L, 0); + size_t ls, lp; + const char *s = luaL_checklstring(L, 1, &ls); + const char *p = luaL_checklstring(L, 2, &lp); + GMatchState *gm; + lua_settop(L, 2); /* keep them on closure to avoid being collected */ + gm = (GMatchState *)lua_newuserdata(L, sizeof(GMatchState)); + prepstate(&gm->ms, L, s, ls, p, lp); + gm->src = s; gm->p = p; lua_pushcclosure(L, gmatch_aux, 3); return 1; } @@ -760,17 +793,11 @@ static int str_gsub (lua_State *L) { if (anchor) { p++; lp--; /* skip anchor character */ } - ms.L = L; - ms.matchdepth = MAXCCALLS; - ms.src_init = src; - ms.src_end = src+srcl; - ms.p_end = p + lp; + prepstate(&ms, L, src, srcl, p, lp); while (n < max_s) { const char *e; - ms.level = 0; - lua_assert(ms.matchdepth == MAXCCALLS); - e = match(&ms, src, p); - if (e) { + reprepstate(&ms); + if ((e = match(&ms, src, p)) != NULL) { n++; add_value(&ms, &b, src, e, tr); } @@ -797,17 +824,102 @@ static int str_gsub (lua_State *L) { ** ======================================================= */ -/* maximum size of each formatted item (> len(format('%99.99f', -1e308))) */ -#define MAX_ITEM 512 +#if !defined(lua_number2strx) /* { */ + +/* +** Hexadecimal floating-point formatter +*/ + +#include +#include + +#define SIZELENMOD (sizeof(LUA_NUMBER_FRMLEN)/sizeof(char)) + + +/* +** Number of bits that goes into the first digit. It can be any value +** between 1 and 4; the following definition tries to align the number +** to nibble boundaries by making what is left after that first digit a +** multiple of 4. +*/ +#define L_NBFD ((l_mathlim(MANT_DIG) - 1)%4 + 1) + + +/* +** Add integer part of 'x' to buffer and return new 'x' +*/ +static lua_Number adddigit (char *buff, int n, lua_Number x) { + lua_Number dd = l_mathop(floor)(x); /* get integer part from 'x' */ + int d = (int)dd; + buff[n] = (d < 10 ? d + '0' : d - 10 + 'a'); /* add to buffer */ + return x - dd; /* return what is left */ +} + + +static int num2straux (char *buff, int sz, lua_Number x) { + if (x != x || x == HUGE_VAL || x == -HUGE_VAL) /* inf or NaN? */ + return l_sprintf(buff, sz, LUA_NUMBER_FMT, x); /* equal to '%g' */ + else if (x == 0) { /* can be -0... */ + /* create "0" or "-0" followed by exponent */ + return l_sprintf(buff, sz, LUA_NUMBER_FMT "x0p+0", x); + } + else { + int e; + lua_Number m = l_mathop(frexp)(x, &e); /* 'x' fraction and exponent */ + int n = 0; /* character count */ + if (m < 0) { /* is number negative? */ + buff[n++] = '-'; /* add signal */ + m = -m; /* make it positive */ + } + buff[n++] = '0'; buff[n++] = 'x'; /* add "0x" */ + m = adddigit(buff, n++, m * (1 << L_NBFD)); /* add first digit */ + e -= L_NBFD; /* this digit goes before the radix point */ + if (m > 0) { /* more digits? */ + buff[n++] = lua_getlocaledecpoint(); /* add radix point */ + do { /* add as many digits as needed */ + m = adddigit(buff, n++, m * 16); + } while (m > 0); + } + n += l_sprintf(buff + n, sz - n, "p%+d", e); /* add exponent */ + lua_assert(n < sz); + return n; + } +} + + +static int lua_number2strx (lua_State *L, char *buff, int sz, + const char *fmt, lua_Number x) { + int n = num2straux(buff, sz, x); + if (fmt[SIZELENMOD] == 'A') { + int i; + for (i = 0; i < n; i++) + buff[i] = toupper(uchar(buff[i])); + } + else if (fmt[SIZELENMOD] != 'a') + luaL_error(L, "modifiers for format '%%a'/'%%A' not implemented"); + return n; +} + +#endif /* } */ + + +/* +** Maximum size of each formatted item. This maximum size is produced +** by format('%.99f', -maxfloat), and is equal to 99 + 3 ('-', '.', +** and '\0') + number of decimal digits to represent maxfloat (which +** is maximum exponent + 1). (99+3+1 then rounded to 120 for "extra +** expenses", such as locale-dependent stuff) +*/ +#define MAX_ITEM (120 + l_mathlim(MAX_10_EXP)) + /* valid flags in a format specification */ #define FLAGS "-+ #0" /* ** maximum size of each format specification (such as "%-099.99d") -** (+2 for length modifiers; +10 accounts for %99.99x plus margin of error) */ -#define MAX_FORMAT (sizeof(FLAGS) + 2 + 10) +#define MAX_FORMAT 32 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) { else if (*s == '\0' || iscntrl(uchar(*s))) { char buff[10]; if (!isdigit(uchar(*(s+1)))) - sprintf(buff, "\\%d", (int)uchar(*s)); + l_sprintf(buff, sizeof(buff), "\\%d", (int)uchar(*s)); else - sprintf(buff, "\\%03d", (int)uchar(*s)); + l_sprintf(buff, sizeof(buff), "\\%03d", (int)uchar(*s)); luaL_addstring(b, buff); } else @@ -849,8 +961,8 @@ static const char *scanformat (lua_State *L, const char *strfrmt, char *form) { if (isdigit(uchar(*p))) luaL_error(L, "invalid format (width or precision too long)"); *(form++) = '%'; - memcpy(form, strfrmt, (p - strfrmt + 1) * sizeof(char)); - form += p - strfrmt + 1; + memcpy(form, strfrmt, ((p - strfrmt) + 1) * sizeof(char)); + form += (p - strfrmt) + 1; *form = '\0'; return p; } @@ -891,23 +1003,25 @@ static int str_format (lua_State *L) { strfrmt = scanformat(L, strfrmt, form); switch (*strfrmt++) { case 'c': { - nb = sprintf(buff, form, (int)luaL_checkinteger(L, arg)); + nb = l_sprintf(buff, MAX_ITEM, form, (int)luaL_checkinteger(L, arg)); break; } case 'd': case 'i': case 'o': case 'u': case 'x': case 'X': { lua_Integer n = luaL_checkinteger(L, arg); addlenmod(form, LUA_INTEGER_FRMLEN); - nb = sprintf(buff, form, n); + nb = l_sprintf(buff, MAX_ITEM, form, n); break; } -#if defined(LUA_USE_AFORMAT) case 'a': case 'A': -#endif + addlenmod(form, LUA_NUMBER_FRMLEN); + nb = lua_number2strx(L, buff, MAX_ITEM, form, + luaL_checknumber(L, arg)); + break; case 'e': case 'E': case 'f': case 'g': case 'G': { addlenmod(form, LUA_NUMBER_FRMLEN); - nb = sprintf(buff, form, luaL_checknumber(L, arg)); + nb = l_sprintf(buff, MAX_ITEM, form, luaL_checknumber(L, arg)); break; } case 'q': { @@ -917,23 +1031,27 @@ static int str_format (lua_State *L) { case 's': { size_t l; const char *s = luaL_tolstring(L, arg, &l); - if (!strchr(form, '.') && l >= 100) { - /* no precision and string is too long to be formatted; - keep original string */ - luaL_addvalue(&b); - break; - } + if (form[2] == '\0') /* no modifiers? */ + luaL_addvalue(&b); /* keep entire string */ else { - nb = sprintf(buff, form, s); - lua_pop(L, 1); /* remove result from 'luaL_tolstring' */ - break; + luaL_argcheck(L, l == strlen(s), arg, "string contains zeros"); + if (!strchr(form, '.') && l >= 100) { + /* no precision and string is too long to be formatted */ + luaL_addvalue(&b); /* keep entire string */ + } + else { /* format the string into 'buff' */ + nb = l_sprintf(buff, MAX_ITEM, form, s); + lua_pop(L, 1); /* remove result from 'luaL_tolstring' */ + } } + break; } default: { /* also treat cases 'pnLlh' */ return luaL_error(L, "invalid option '%%%c' to 'format'", *(strfrmt - 1)); } } + lua_assert(nb < MAX_ITEM); luaL_addsize(&b, nb); } } @@ -1225,8 +1343,13 @@ static int str_pack (lua_State *L) { case Kchar: { /* fixed-size string */ size_t len; const char *s = luaL_checklstring(L, arg, &len); - luaL_argcheck(L, len == (size_t)size, arg, "wrong length"); - luaL_addlstring(&b, s, size); + if ((size_t)size <= len) /* string larger than (or equal to) needed? */ + luaL_addlstring(&b, s, size); /* truncate string to asked size */ + else { /* string smaller than needed */ + luaL_addlstring(&b, s, len); /* add it all */ + while (len++ < (size_t)size) /* pad extra space */ + luaL_addchar(&b, LUA_PACKPADBYTE); + } break; } case Kstring: { /* strings with length count */ @@ -1249,7 +1372,7 @@ static int str_pack (lua_State *L) { totalsize += len + 1; break; } - case Kpadding: luaL_addchar(&b, LUA_PACKPADBYTE); /* go through */ + case Kpadding: luaL_addchar(&b, LUA_PACKPADBYTE); /* FALLTHROUGH */ case Kpaddalign: case Knop: arg--; /* undo increment */ break; @@ -1276,7 +1399,7 @@ static int str_packsize (lua_State *L) { case Kstring: /* strings with length count */ case Kzstr: /* zero-terminated string */ luaL_argerror(L, 1, "variable-length format"); - break; + /* call never return, but to avoid warnings: *//* FALLTHROUGH */ default: break; } } diff --git a/ltablib.c b/ltablib.c index 8f78afb..b3c9a7c 100644 --- a/ltablib.c +++ b/ltablib.c @@ -1,5 +1,5 @@ /* -** $Id: ltablib.c,v 1.79 2014/11/02 19:19:04 roberto Exp $ +** $Id: ltablib.c,v 1.90 2015/11/25 12:48:57 roberto Exp $ ** Library for Table Manipulation ** See Copyright Notice in lua.h */ @@ -12,6 +12,7 @@ #include #include +#include #include "lua.h" @@ -19,42 +20,44 @@ #include "lualib.h" - /* -** Structure with table-access functions +** Operations that an object must define to mimic a table +** (some functions only need some of them) */ -typedef struct { - int (*geti) (lua_State *L, int idx, lua_Integer n); - void (*seti) (lua_State *L, int idx, lua_Integer n); -} TabA; +#define TAB_R 1 /* read */ +#define TAB_W 2 /* write */ +#define TAB_L 4 /* length */ +#define TAB_RW (TAB_R | TAB_W) /* read/write */ + + +#define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n)) + + +static int checkfield (lua_State *L, const char *key, int n) { + lua_pushstring(L, key); + return (lua_rawget(L, -n) != LUA_TNIL); +} /* -** Check that 'arg' has a table and set access functions in 'ta' to raw -** or non-raw according to the presence of corresponding metamethods. +** Check that 'arg' either is a table or can behave like one (that is, +** has a metatable with the required metamethods) */ -static void checktab (lua_State *L, int arg, TabA *ta) { - ta->geti = NULL; ta->seti = NULL; - if (lua_getmetatable(L, arg)) { - lua_pushliteral(L, "__index"); /* 'index' metamethod */ - if (lua_rawget(L, -2) != LUA_TNIL) - ta->geti = lua_geti; - lua_pushliteral(L, "__newindex"); /* 'newindex' metamethod */ - if (lua_rawget(L, -3) != LUA_TNIL) - ta->seti = lua_seti; - lua_pop(L, 3); /* pop metatable plus both metamethods */ - } - if (ta->geti == NULL || ta->seti == NULL) { - luaL_checktype(L, arg, LUA_TTABLE); /* must be table for raw methods */ - if (ta->geti == NULL) ta->geti = lua_rawgeti; - if (ta->seti == NULL) ta->seti = lua_rawseti; +static void checktab (lua_State *L, int arg, int what) { + if (lua_type(L, arg) != LUA_TTABLE) { /* is it not a table? */ + int n = 1; /* number of elements to pop */ + if (lua_getmetatable(L, arg) && /* must have metatable */ + (!(what & TAB_R) || checkfield(L, "__index", ++n)) && + (!(what & TAB_W) || checkfield(L, "__newindex", ++n)) && + (!(what & TAB_L) || checkfield(L, "__len", ++n))) { + lua_pop(L, n); /* pop metatable and tested metamethods */ + } + else + luaL_argerror(L, arg, "table expected"); /* force an error */ } } -#define aux_getn(L,n,ta) (checktab(L, n, ta), luaL_len(L, n)) - - #if defined(LUA_COMPAT_MAXN) static int maxn (lua_State *L) { lua_Number max = 0; @@ -74,8 +77,7 @@ static int maxn (lua_State *L) { static int tinsert (lua_State *L) { - TabA ta; - lua_Integer e = aux_getn(L, 1, &ta) + 1; /* first empty element */ + lua_Integer e = aux_getn(L, 1, TAB_RW) + 1; /* first empty element */ lua_Integer pos; /* where to insert new element */ switch (lua_gettop(L)) { case 2: { /* called with only 2 arguments */ @@ -87,8 +89,8 @@ static int tinsert (lua_State *L) { pos = luaL_checkinteger(L, 2); /* 2nd argument is the position */ luaL_argcheck(L, 1 <= pos && pos <= e, 2, "position out of bounds"); for (i = e; i > pos; i--) { /* move up elements */ - (*ta.geti)(L, 1, i - 1); - (*ta.seti)(L, 1, i); /* t[i] = t[i - 1] */ + lua_geti(L, 1, i - 1); + lua_seti(L, 1, i); /* t[i] = t[i - 1] */ } break; } @@ -96,55 +98,57 @@ static int tinsert (lua_State *L) { return luaL_error(L, "wrong number of arguments to 'insert'"); } } - (*ta.seti)(L, 1, pos); /* t[pos] = v */ + lua_seti(L, 1, pos); /* t[pos] = v */ return 0; } static int tremove (lua_State *L) { - TabA ta; - lua_Integer size = aux_getn(L, 1, &ta); + lua_Integer size = aux_getn(L, 1, TAB_RW); lua_Integer pos = luaL_optinteger(L, 2, size); if (pos != size) /* validate 'pos' if given */ luaL_argcheck(L, 1 <= pos && pos <= size + 1, 1, "position out of bounds"); - (*ta.geti)(L, 1, pos); /* result = t[pos] */ + lua_geti(L, 1, pos); /* result = t[pos] */ for ( ; pos < size; pos++) { - (*ta.geti)(L, 1, pos + 1); - (*ta.seti)(L, 1, pos); /* t[pos] = t[pos + 1] */ + lua_geti(L, 1, pos + 1); + lua_seti(L, 1, pos); /* t[pos] = t[pos + 1] */ } lua_pushnil(L); - (*ta.seti)(L, 1, pos); /* t[pos] = nil */ + lua_seti(L, 1, pos); /* t[pos] = nil */ return 1; } +/* +** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever +** possible, copy in increasing order, which is better for rehashing. +** "possible" means destination after original range, or smaller +** than origin, or copying to another table. +*/ static int tmove (lua_State *L) { - TabA ta; lua_Integer f = luaL_checkinteger(L, 2); lua_Integer e = luaL_checkinteger(L, 3); lua_Integer t = luaL_checkinteger(L, 4); int tt = !lua_isnoneornil(L, 5) ? 5 : 1; /* destination table */ - /* the following restriction avoids several problems with overflows */ - luaL_argcheck(L, f > 0, 2, "initial position must be positive"); + checktab(L, 1, TAB_R); + checktab(L, tt, TAB_W); if (e >= f) { /* otherwise, nothing to move */ lua_Integer n, i; - ta.geti = (luaL_getmetafield(L, 1, "__index") == LUA_TNIL) - ? (luaL_checktype(L, 1, LUA_TTABLE), lua_rawgeti) - : lua_geti; - ta.seti = (luaL_getmetafield(L, tt, "__newindex") == LUA_TNIL) - ? (luaL_checktype(L, tt, LUA_TTABLE), lua_rawseti) - : lua_seti; + luaL_argcheck(L, f > 0 || e < LUA_MAXINTEGER + f, 3, + "too many elements to move"); n = e - f + 1; /* number of elements to move */ - if (t > f) { - for (i = n - 1; i >= 0; i--) { - (*ta.geti)(L, 1, f + i); - (*ta.seti)(L, tt, t + i); + luaL_argcheck(L, t <= LUA_MAXINTEGER - n + 1, 4, + "destination wrap around"); + if (t > e || t <= f || tt != 1) { + for (i = 0; i < n; i++) { + lua_geti(L, 1, f + i); + lua_seti(L, tt, t + i); } } else { - for (i = 0; i < n; i++) { - (*ta.geti)(L, 1, f + i); - (*ta.seti)(L, tt, t + i); + for (i = n - 1; i >= 0; i--) { + lua_geti(L, 1, f + i); + lua_seti(L, tt, t + i); } } } @@ -153,8 +157,8 @@ static int tmove (lua_State *L) { } -static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) { - (*ta->geti)(L, 1, i); +static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) { + lua_geti(L, 1, i); if (!lua_isstring(L, -1)) luaL_error(L, "invalid value (%s) at index %d in table for 'concat'", luaL_typename(L, -1), i); @@ -163,21 +167,19 @@ static void addfield (lua_State *L, luaL_Buffer *b, TabA *ta, lua_Integer i) { static int tconcat (lua_State *L) { - TabA ta; luaL_Buffer b; + lua_Integer last = aux_getn(L, 1, TAB_R); size_t lsep; - lua_Integer i, last; const char *sep = luaL_optlstring(L, 2, "", &lsep); - checktab(L, 1, &ta); - i = luaL_optinteger(L, 3, 1); - last = luaL_opt(L, luaL_checkinteger, 4, luaL_len(L, 1)); + lua_Integer i = luaL_optinteger(L, 3, 1); + last = luaL_opt(L, luaL_checkinteger, 4, last); luaL_buffinit(L, &b); for (; i < last; i++) { - addfield(L, &b, &ta, i); + addfield(L, &b, i); luaL_addlstring(&b, sep, lsep); } if (i == last) /* add last value (if interval was not empty) */ - addfield(L, &b, &ta, i); + addfield(L, &b, i); luaL_pushresult(&b); return 1; } @@ -195,7 +197,7 @@ static int pack (lua_State *L) { lua_createtable(L, n, 1); /* create result table */ lua_insert(L, 1); /* put it at index 1 */ for (i = n; i >= 1; i--) /* assign elements */ - lua_rawseti(L, 1, i); + lua_seti(L, 1, i); lua_pushinteger(L, n); lua_setfield(L, 1, "n"); /* t.n = number of elements */ return 1; /* return table */ @@ -203,20 +205,17 @@ static int pack (lua_State *L) { static int unpack (lua_State *L) { - TabA ta; - lua_Integer i, e; lua_Unsigned n; - checktab(L, 1, &ta); - i = luaL_optinteger(L, 2, 1); - e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); + lua_Integer i = luaL_optinteger(L, 2, 1); + lua_Integer e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1)); if (i > e) return 0; /* empty range */ n = (lua_Unsigned)e - i; /* number of elements minus 1 (avoid overflows) */ if (n >= (unsigned int)INT_MAX || !lua_checkstack(L, (int)(++n))) return luaL_error(L, "too many results to unpack"); - do { /* must have at least one element */ - (*ta.geti)(L, 1, i); /* push arg[i..e] */ - } while (i++ < e); - + for (; i < e; i++) { /* push arg[i..e - 1] (to avoid overflows) */ + lua_geti(L, 1, i); + } + lua_geti(L, 1, e); /* push last element */ return (int)n; } @@ -233,97 +232,190 @@ static int unpack (lua_State *L) { */ -static void set2 (lua_State *L, TabA *ta, int i, int j) { - (*ta->seti)(L, 1, i); - (*ta->seti)(L, 1, j); +/* +** Produce a "random" 'unsigned int' to randomize pivot choice. This +** macro is used only when 'sort' detects a big imbalance in the result +** of a partition. (If you don't want/need this "randomness", ~0 is a +** good choice.) +*/ +#if !defined(l_randomizePivot) /* { */ + +#include + +/* size of 'e' measured in number of 'unsigned int's */ +#define sof(e) (sizeof(e) / sizeof(unsigned int)) + +/* +** Use 'time' and 'clock' as sources of "randomness". Because we don't +** know the types 'clock_t' and 'time_t', we cannot cast them to +** anything without risking overflows. A safe way to use their values +** is to copy them to an array of a known type and use the array values. +*/ +static unsigned int l_randomizePivot (void) { + clock_t c = clock(); + time_t t = time(NULL); + unsigned int buff[sof(c) + sof(t)]; + unsigned int i, rnd = 0; + memcpy(buff, &c, sof(c) * sizeof(unsigned int)); + memcpy(buff + sof(c), &t, sof(t) * sizeof(unsigned int)); + for (i = 0; i < sof(buff); i++) + rnd += buff[i]; + return rnd; +} + +#endif /* } */ + + +/* arrays larger than 'RANLIMIT' may use randomized pivots */ +#define RANLIMIT 100u + + +static void set2 (lua_State *L, unsigned int i, unsigned int j) { + lua_seti(L, 1, i); + lua_seti(L, 1, j); } + +/* +** Return true iff value at stack index 'a' is less than the value at +** index 'b' (according to the order of the sort). +*/ static int sort_comp (lua_State *L, int a, int b) { - if (!lua_isnil(L, 2)) { /* function? */ + if (lua_isnil(L, 2)) /* no function? */ + return lua_compare(L, a, b, LUA_OPLT); /* a < b */ + else { /* function */ int res; - lua_pushvalue(L, 2); + lua_pushvalue(L, 2); /* push function */ lua_pushvalue(L, a-1); /* -1 to compensate function */ lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ - lua_call(L, 2, 1); - res = lua_toboolean(L, -1); - lua_pop(L, 1); + lua_call(L, 2, 1); /* call function */ + res = lua_toboolean(L, -1); /* get result */ + lua_pop(L, 1); /* pop result */ return res; } - else /* a < b? */ - return lua_compare(L, a, b, LUA_OPLT); } -static void auxsort (lua_State *L, TabA *ta, int l, int u) { - while (l < u) { /* for tail recursion */ - int i, j; - /* sort elements a[l], a[(l+u)/2] and a[u] */ - (*ta->geti)(L, 1, l); - (*ta->geti)(L, 1, u); - if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ - set2(L, ta, l, u); /* swap a[l] - a[u] */ + +/* +** Does the partition: Pivot P is at the top of the stack. +** precondition: a[lo] <= P == a[up-1] <= a[up], +** so it only needs to do the partition from lo + 1 to up - 2. +** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] +** returns 'i'. +*/ +static unsigned int partition (lua_State *L, unsigned int lo, + unsigned int up) { + unsigned int i = lo; /* will be incremented before first use */ + unsigned int j = up - 1; /* will be decremented before first use */ + /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ + for (;;) { + /* next loop: repeat ++i while a[i] < P */ + while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { + if (i == up - 1) /* a[i] < P but a[up - 1] == P ?? */ + luaL_error(L, "invalid order function for sorting"); + lua_pop(L, 1); /* remove a[i] */ + } + /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ + /* next loop: repeat --j while P < a[j] */ + while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { + if (j < i) /* j < i but a[j] > P ?? */ + luaL_error(L, "invalid order function for sorting"); + lua_pop(L, 1); /* remove a[j] */ + } + /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ + if (j < i) { /* no elements out of place? */ + /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ + lua_pop(L, 1); /* pop a[j] */ + /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ + set2(L, up - 1, i); + return i; + } + /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ + set2(L, i, j); + } +} + + +/* +** Choose an element in the middle (2nd-3th quarters) of [lo,up] +** "randomized" by 'rnd' +*/ +static unsigned int choosePivot (unsigned int lo, unsigned int up, + unsigned int rnd) { + unsigned int r4 = (unsigned int)(up - lo) / 4u; /* range/4 */ + unsigned int p = rnd % (r4 * 2) + (lo + r4); + lua_assert(lo + r4 <= p && p <= up - r4); + return p; +} + + +/* +** QuickSort algorithm (recursive function) +*/ +static void auxsort (lua_State *L, unsigned int lo, unsigned int up, + unsigned int rnd) { + while (lo < up) { /* loop for tail recursion */ + unsigned int p; /* Pivot index */ + unsigned int n; /* to be used later */ + /* sort elements 'lo', 'p', and 'up' */ + lua_geti(L, 1, lo); + lua_geti(L, 1, up); + if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ + set2(L, lo, up); /* swap a[lo] - a[up] */ else - lua_pop(L, 2); - if (u-l == 1) break; /* only 2 elements */ - i = (l+u)/2; - (*ta->geti)(L, 1, i); - (*ta->geti)(L, 1, l); - if (sort_comp(L, -2, -1)) /* a[i]geti)(L, 1, u); - if (sort_comp(L, -1, -2)) /* a[u]geti)(L, 1, i); /* Pivot */ - lua_pushvalue(L, -1); - (*ta->geti)(L, 1, u-1); - set2(L, ta, i, u-1); - /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ - i = l; j = u-1; - for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ - /* repeat ++i until a[i] >= P */ - while ((*ta->geti)(L, 1, ++i), sort_comp(L, -1, -2)) { - if (i>=u) luaL_error(L, "invalid order function for sorting"); - lua_pop(L, 1); /* remove a[i] */ - } - /* repeat --j until a[j] <= P */ - while ((*ta->geti)(L, 1, --j), sort_comp(L, -3, -1)) { - if (j<=l) luaL_error(L, "invalid order function for sorting"); - lua_pop(L, 1); /* remove a[j] */ - } - if (jgeti)(L, 1, u-1); - (*ta->geti)(L, 1, i); - set2(L, ta, u-1, i); /* swap pivot (a[u-1]) with a[i] */ - /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ - /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ - if (i-l < u-i) { - j=l; i=i-1; l=i+2; + if (up - lo == 2) /* only 3 elements? */ + return; /* already sorted */ + lua_geti(L, 1, p); /* get middle element (Pivot) */ + lua_pushvalue(L, -1); /* push Pivot */ + lua_geti(L, 1, up - 1); /* push a[up - 1] */ + set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ + p = partition(L, lo, up); + /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ + if (p - lo < up - p) { /* lower interval is smaller? */ + auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ + n = p - lo; /* size of smaller interval */ + lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ } else { - j=i+1; i=u; u=j-2; + auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ + n = up - p; /* size of smaller interval */ + up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ } - auxsort(L, ta, j, i); /* call recursively the smaller one */ - } /* repeat the routine for the larger one */ + if ((up - lo) / 128u > n) /* partition too imbalanced? */ + rnd = l_randomizePivot(); /* try a new randomization */ + } /* tail call auxsort(L, lo, up, rnd) */ } + static int sort (lua_State *L) { - TabA ta; - int n = (int)aux_getn(L, 1, &ta); - luaL_checkstack(L, 50, ""); /* assume array is smaller than 2^50 */ - if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ - luaL_checktype(L, 2, LUA_TFUNCTION); - lua_settop(L, 2); /* make sure there are two arguments */ - auxsort(L, &ta, 1, n); + lua_Integer n = aux_getn(L, 1, TAB_RW); + if (n > 1) { /* non-trivial interval? */ + luaL_argcheck(L, n < INT_MAX, 1, "array too big"); + luaL_checkstack(L, 40, ""); /* assume array is smaller than 2^40 */ + if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ + luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ + lua_settop(L, 2); /* make sure there are two arguments */ + auxsort(L, 1, (unsigned int)n, 0u); + } return 0; } diff --git a/lutf8lib.c b/lutf8lib.c index be4f087..9042582 100644 --- a/lutf8lib.c +++ b/lutf8lib.c @@ -1,5 +1,5 @@ /* -** $Id: lutf8lib.c,v 1.13 2014/11/02 19:19:04 roberto Exp $ +** $Id: lutf8lib.c,v 1.15 2015/03/28 19:16:55 roberto Exp $ ** Standard library for UTF-8 manipulation ** See Copyright Notice in lua.h */ @@ -11,6 +11,7 @@ #include +#include #include #include @@ -37,7 +38,7 @@ static lua_Integer u_posrelat (lua_Integer pos, size_t len) { ** Decode one UTF-8 sequence, returning NULL if byte sequence is invalid. */ static const char *utf8_decode (const char *o, int *val) { - static unsigned int limits[] = {0xFF, 0x7F, 0x7FF, 0xFFFF}; + static const unsigned int limits[] = {0xFF, 0x7F, 0x7FF, 0xFFFF}; const unsigned char *s = (const unsigned char *)o; unsigned int c = s[0]; unsigned int res = 0; /* final result */ @@ -106,9 +107,9 @@ static int codepoint (lua_State *L) { luaL_argcheck(L, posi >= 1, 2, "out of range"); luaL_argcheck(L, pose <= (lua_Integer)len, 3, "out of range"); if (posi > pose) return 0; /* empty interval; return no values */ - n = (int)(pose - posi + 1); - if (posi + n <= pose) /* (lua_Integer -> int) overflow? */ + if (pose - posi >= INT_MAX) /* (lua_Integer -> int) overflow? */ return luaL_error(L, "string slice too long"); + n = (int)(pose - posi) + 1; luaL_checkstack(L, n, "string slice too long"); n = 0; se = s + pose; @@ -234,7 +235,7 @@ static int iter_codes (lua_State *L) { #define UTF8PATT "[\0-\x7F\xC2-\xF4][\x80-\xBF]*" -static struct luaL_Reg funcs[] = { +static const luaL_Reg funcs[] = { {"offset", byteoffset}, {"codepoint", codepoint}, {"char", utfchar}, @@ -248,7 +249,7 @@ static struct luaL_Reg funcs[] = { LUAMOD_API int luaopen_utf8 (lua_State *L) { luaL_newlib(L, funcs); - lua_pushliteral(L, UTF8PATT); + lua_pushlstring(L, UTF8PATT, sizeof(UTF8PATT)/sizeof(char) - 1); lua_setfield(L, -2, "charpattern"); return 1; } -- cgit v1.2.3-55-g6feb