lua

commit 89c09c8e400806a2059fe8460c7c9db517d16ed7
parent 48baa5e89cfd7e7fbfe03966b50bfcf4f57cc6cd
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date:   Tue, 19 Apr 2016 09:33:42 -0300

match time limit defined by variable 'string.pattlimit'

Diffstat:
M
lstrlib.c
 | 
52
++++++++++++++++++++++++++++++++++++----------------

1 file changed, 36 insertions(+), 16 deletions(-)
diff --git a/lstrlib.c b/lstrlib.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstrlib.c,v 1.244 2016/04/07 15:40:07 roberto Exp roberto $
+** $Id: lstrlib.c,v 1.245 2016/04/08 21:15:02 roberto Exp roberto $
 ** Standard library for string operations and pattern-matching
 ** See Copyright Notice in lua.h
 */
@@ -26,7 +26,8 @@
 
 /*
 ** maximum number of captures that a pattern can do during
-** pattern-matching. This limit is arbitrary.
+** pattern-matching. This limit is arbitrary, but must fit in
+** an unsigned char.
 */
 #if !defined(LUA_MAXCAPTURES)
 #define LUA_MAXCAPTURES		32
@@ -214,9 +215,10 @@ typedef struct MatchState {
   const char *src_end;  /* end ('\0') of source string */
   const char *p_end;  /* end ('\0') of pattern */
   lua_State *L;
-  size_t nrep;  /* limit to avoid non-linear complexity */
+  lua_Unsigned nrep;  /* limit to avoid non-linear complexity */
   int matchdepth;  /* control for recursive depth (to avoid C stack overflow) */
-  int level;  /* total number of captures (finished or unfinished) */
+  unsigned char level;  /* total number of captures (finished or unfinished) */
+  unsigned char usedlimit;  /* true if real limit for 'nrep' was used */
   struct {
     const char *init;
     ptrdiff_t len;
@@ -235,13 +237,12 @@ static const char *match (MatchState *ms, const char *s, const char *p);
 
 
 /*
-** parameters to control the maximum number of operators handled in
-** a match (to avoid non-linear complexity). The maximum will be:
-** (subject length) * A_REPS + B_REPS
+** Maximum number of operators handled in a match before consulting
+** 'string.pattlimit'. (This lower limit is only to avoid wasting time
+** consulting 'string.pattlimit' in simple matches.)
 */
-#if !defined(A_REPS)
-#define A_REPS		4
-#define B_REPS		100000
+#if !defined(PREPATTLIMIT)
+#define PREPATTLIMIT	200
 #endif
 
 
@@ -421,6 +422,27 @@ static const char *end_capture (MatchState *ms, const char *s,
 }
 
 
+static void checklimit (MatchState *ms) {
+  lua_State *L = ms->L;
+  lua_assert(ms->nrep == 0);
+  if (!ms->usedlimit) {  /* have not used 'string.pattlimit' yet? */
+    int top = lua_gettop(L);
+    if (lua_getglobal(L, "string") == LUA_TTABLE &&
+        lua_getfield(L, -1, "pattlimit") != LUA_TNIL) {  /* is it defined? */
+      lua_Unsigned limit = (lua_Unsigned)lua_tointeger(L, -1);  /* get it */
+      if (limit > PREPATTLIMIT)  /* discount cycles already used */
+        ms->nrep = limit - PREPATTLIMIT;
+      ms->usedlimit = 1;  /* do not use 'pattlimit' again */
+    }
+    else  /* no limit defined; set no limit */
+      ms->nrep = ~(lua_Unsigned)0;
+    lua_settop(L, top);  /* pop 'string' table and (maybe) 'pattlimit' */
+  }
+  if (ms->nrep == 0)
+    luaL_error(L, "pattern too complex");
+}
+
+
 static const char *match_capture (MatchState *ms, const char *s, int l) {
   size_t len;
   l = check_capture(ms, l);
@@ -502,8 +524,8 @@ static const char *match (MatchState *ms, const char *s, const char *p) {
             s = NULL;  /* fail */
         }
         else {  /* matched once */
-          if (ms->nrep-- == 0)
-            luaL_error(ms->L, "pattern too complex");
+          if (--ms->nrep == 0)
+            checklimit(ms);
           switch (*ep) {  /* handle optional suffix */
             case '?': {  /* optional */
               const char *res;
@@ -607,10 +629,8 @@ static void prepstate (MatchState *ms, lua_State *L,
   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 */
+  ms->nrep = PREPATTLIMIT;
+  ms->usedlimit = 0;
 }