yyparse(): only check stack size in outer loop
authorDavid Mitchell <davem@iabyn.com>
Sat, 3 Dec 2016 20:58:37 +0000 (20:58 +0000)
committerDavid Mitchell <davem@iabyn.com>
Mon, 5 Dec 2016 11:54:03 +0000 (11:54 +0000)
Rather than checking before each individual shift whether the parse stack
needs extending, only check once per rule, making sure there's enough
space to shift all the items for the longest possible rule

parser.h
perly.c
sv.c
toke.c

index c5a59ab..3c7bb4e 100644 (file)
--- a/parser.h
+++ b/parser.h
@@ -44,7 +44,9 @@ typedef struct yy_parser {
 
     int                    yylen;      /* length of active reduction */
     yy_stack_frame  *stack;    /* base of stack */
-    yy_stack_frame  *stack_max1;/* (top-1)th element of alloacted stack */
+    yy_stack_frame  *stack_maxbase;/* (stack + alloced size - YY_MAXRULE)
+                                    * it's offset by -YY_MAXRULE to make
+                                    * overflow checks quicker */
     yy_stack_frame  *ps;       /* current stack frame */
 
     /* lexer state */
diff --git a/perly.c b/perly.c
index 8f3c5c8..af44956 100644 (file)
--- a/perly.c
+++ b/perly.c
@@ -58,6 +58,15 @@ typedef signed char yysigned_char;
 
 # define YYSIZE_T size_t
 
+/* the max number of RHS shifted elements that can make up a rule.
+ * This should really be auto-generated from the max value in yyr2[]
+ * but that involves extra work, so set it slightly higher than the
+ * current max, and assert each time yyr2[] is accessed.
+ * Used to determine if the parse stack needs extending.
+ */
+
+#define YY_MAXRULE 15
+
 #define YYEOF          0
 #define YYTERROR       1
 
@@ -275,7 +284,7 @@ Perl_yyparse (pTHX_ int gramtype)
     SAVEINT(parser->yyerrstatus);
     SAVEINT(parser->yylen);
     SAVEVPTR(parser->stack);
-    SAVEVPTR(parser->stack_max1);
+    SAVEVPTR(parser->stack_maxbase);
     SAVEVPTR(parser->ps);
 
     /* initialise state for this parse */
@@ -283,7 +292,7 @@ Perl_yyparse (pTHX_ int gramtype)
     parser->yyerrstatus = 0;
     parser->yylen = 0;
     Newx(parser->stack, YYINITDEPTH, yy_stack_frame);
-    parser->stack_max1 = parser->stack + YYINITDEPTH - 1;
+    parser->stack_maxbase = parser->stack + YYINITDEPTH - YY_MAXRULE;
     ps = parser->ps = parser->stack;
     ps->state = 0;
     SAVEDESTRUCTOR_X(S_clear_yystack, parser);
@@ -291,35 +300,31 @@ Perl_yyparse (pTHX_ int gramtype)
     while (1) {
         /* main loop: shift some tokens, then reduce when possible */
 
+        /* grow the stack to accommodate longest possible rule */
+        if (ps >= parser->stack_maxbase) {
+            Size_t pos = ps - parser->stack;
+            Size_t newsize = 2 * (parser->stack_maxbase + YY_MAXRULE
+                                    - parser->stack);
+            /* this will croak on insufficient memory */
+            Renew(parser->stack, newsize, yy_stack_frame);
+            ps = parser->ps = parser->stack + pos;
+            parser->stack_maxbase = parser->stack + newsize - YY_MAXRULE;
+
+            YYDPRINTF((Perl_debug_log,
+                            "parser stack size increased to %lu frames\n",
+                            (unsigned long int)newsize));
+        }
+
         while (1) {
             /* shift a token, or quit when it's possible to reduce */
 
+            assert(ps < parser->stack_maxbase + YY_MAXRULE);
             yystate = ps->state;
 
             YYDPRINTF ((Perl_debug_log, "Entering state %d\n", yystate));
 
             parser->yylen = 0;
 
-            {
-                /* grow the stack? We always leave 1 spare slot,
-                 * in case of a '' -> 'foo' reduction.
-                 * Note that stack_max1 points to the (top-1)th allocated stack
-                 * element to make this check fast */
-
-                if (ps >= parser->stack_max1) {
-                    Size_t pos = ps - parser->stack;
-                    Size_t newsize = 2 * (parser->stack_max1 + 2 - parser->stack);
-                    /* this will croak on insufficient memory */
-                    Renew(parser->stack, newsize, yy_stack_frame);
-                    ps = parser->ps = parser->stack + pos;
-                    parser->stack_max1 = parser->stack + newsize - 1;
-
-                    YYDPRINTF((Perl_debug_log,
-                                    "parser stack size increased to %lu frames\n",
-                                    (unsigned long int)newsize));
-                }
-            }
-
         /* Do appropriate processing given the current state.  */
         /* Read a lookahead token if we need one and don't already have one.  */
 
@@ -407,6 +412,7 @@ Perl_yyparse (pTHX_ int gramtype)
 
         /* yyn is the number of a rule to reduce with.  */
         parser->yylen = yyr2[yyn];
+        assert(parser->yylen <= YY_MAXRULE); /* see defn of YY_MAXRULE above */
 
         /* If YYLEN is nonzero, implement the default value of the action:
           "$$ = $1".
diff --git a/sv.c b/sv.c
index 1eff364..48de19c 100644 (file)
--- a/sv.c
+++ b/sv.c
@@ -13130,7 +13130,7 @@ Perl_parser_dup(pTHX_ const yy_parser *const proto, CLONE_PARAMS *const param)
     parser->old_parser = NULL;
     parser->stack = NULL;
     parser->ps = NULL;
-    parser->stack_max1 = 0;
+    parser->stack_maxbase = NULL;
     /* XXX parser->stack->state = 0; */
 
     /* XXX eventually, just Copy() most of the parser struct ? */
diff --git a/toke.c b/toke.c
index c09302b..936eab5 100644 (file)
--- a/toke.c
+++ b/toke.c
@@ -705,7 +705,7 @@ Perl_lex_start(pTHX_ SV *line, PerlIO *rsfp, U32 flags)
     PL_parser = parser;
 
     parser->stack = NULL;
-    parser->stack_max1 = NULL;
+    parser->stack_maxbase = NULL;
     parser->ps = NULL;
 
     /* on scope exit, free this parser and restore any outer one */