SQLite Forum

Potentially remove one conditional from Lemon
Login

Potentially remove one conditional from Lemon

(1) By cornerStone-Dev on 2021-01-02 18:11:37 [link] [source]

Hello Forum,

lempar.c, line 1046.

  }while( yypParser->yytos>yypParser->yystack );

Could this be changed to a simple while(1);?

My reasoning is that any false reduction would be caught as a syntax error before actually causing an underflow. The only code flow through this path is a reduce action that I could find. Am I missing something?

Thanks,

Alex

(2) By Richard Hipp (drh) on 2021-01-02 21:28:15 in reply to 1 [link] [source]

The conditional is necessary to correctly handle parser stack overflow errors. With out this conditional, such errors are reported out as syntax errors in SQLite. With other grammars, bad things might happen.

Omitting this conditional does cause a performance increase in the parser, however. So I'm working now to try to figure out a way to deal with stack overflow errors correctly without this conditional - so that we can have both improved performance and correctly reported parser stack overflows.

The following script demonstrates where this conditional is important:

EXPLAIN
SELECT (
 SELECT (
  SELECT (
   SELECT (
    SELECT (
     SELECT (
      SELECT (
       SELECT (
        SELECT (
         SELECT (
          SELECT (
           SELECT (
            SELECT (
             SELECT (
              SELECT (
               SELECT (
                SELECT (
                 SELECT (
                  SELECT (
                   SELECT (
                    SELECT (
                     SELECT (
                      SELECT (
                       SELECT (
                        SELECT (
                         SELECT (
                          SELECT (
                           SELECT (
                            SELECT (
                             SELECT 1
                            )
                           )
                          )
                         )
                        )
                       )
                      )
                     )
                    )
                   )
                  )
                 )
                )
               )
              )
             )
            )
           )
          )
         )
        )
       )
      )
     )
    )
   )
  )
 )
);

(3) By cornerStone-Dev on 2021-01-02 22:03:22 in reply to 2 [link] [source]

This conditional does NOT check for overflow. It checks for UNDERFLOW only. There are other checks in lempar.c that are needed for the OVERFLOW checks.

(4) By Richard Hipp (drh) on 2021-01-02 23:14:08 in reply to 3 [link] [source]

The overflow is detected elsewhere and the stack overflow processing pops the stack to the point where it underflows. It then returns, and the underflow check that you proposed to remove causes the loop to end, reporting the overflow error.

Without the conditional, the loop continues. And from the start state, a "0" token is a syntax error, so the yy_find_shift_action() finds and reports the syntax error.

(5) By Richard Hipp (drh) on 2021-01-02 23:59:50 in reply to 4 [link] [source]

I think check-in 203c049c66238041 is the correct way to omit the conditional in question. That check-in causes SQLite to use 0.13% fewer CPU cycles in our performance tests, according to cachegrind, which is significant. Good catch!

(6) By cornerStone-Dev on 2021-01-03 11:51:17 in reply to 5 [source]

Awesome! I am glad I could contribute in some way to this huge project. I use Lemon and re2c extensively to build tools and programming languages so thank you for freely sharing.