Bug#19194 (Right recursion in parser for CASE causes excessive stack usage,

  limitation)

Note to the reviewer
====================

Warning: reviewing this patch is somewhat involved.
Due to the nature of several issues all affecting the same area,
fixing separately each issue is not practical, since each fix can not be
implemented and tested independently.
In particular, the issues with
- rule recursion
- nested case statements
- forward jump resolution (backpatch list)
are tightly coupled (see below).

Definitions
===========

The expression
  CASE expr
  WHEN expr THEN expr
  WHEN expr THEN expr
  ...
  END
is a "Simple Case Expression".

The expression
  CASE
  WHEN expr THEN expr
  WHEN expr THEN expr
  ...
  END
is a "Searched Case Expression".

The statement
  CASE expr
  WHEN expr THEN stmts
  WHEN expr THEN stmts
  ...
  END CASE
is a "Simple Case Statement".

The statement
  CASE
  WHEN expr THEN stmts
  WHEN expr THEN stmts
  ...
  END CASE
is a "Searched Case Statement".

A "Left Recursive" rule is like
  list:
      element
    | list element
    ;

A "Right Recursive" rule is like
  list:
      element
    | element list
    ;

Left and right recursion produces the same language, the difference only
affects the *order* in which the text is parsed.

In a descendant parser (usually written manually), right recursion works
very well, and is typically implemented with a while loop.
In an ascendant parser (yacc/bison) left recursion works very well,
and is implemented naturally by the parser stack.
In both cases, using the wrong type or recursion is very bad and should be
avoided, as it causes technical issues with the parser implementation.

Before this change
==================

The "Simple Case Expression" and "Searched Case Expression" were both
implemented by the "when_list" and "when_list2" rules, which are left
recursive (ok).

These rules, however, used lex->when_list instead of using the parser stack,
which is more complex that necessary, and potentially dangerous because
of other rules using THD::reset_lex.

The "Simple Case Statement" and "Searched Case Statements" were implemented
by the "sp_case", "sp_whens" and in part by "sp_proc_stmt" rules.
Both cases were right recursive (bad).

The grammar involved was convoluted, and is assumed to be the results of
tweaks to get the code generation to work, but is not what someone would
naturally write.

In addition, using a common rule for both "Simple" and "Searched" case
statements was implemented with sp_head::m_flags |= IN_SIMPLE_CASE,
which is a flag and not a stack, and therefore does not take into account
*nested* case statements. This leads to incorrect generated code, and either
a server crash or an incorrect result.

With regards to the backpatch mechanism, a *different* backpatch list was
created for each jump from "WHEN expr THEN stmt" to "END CASE", which
relied on the grammar to be right recursive.
This is a mis-use of the backpatch list, since this list can resolve
multiple references to the same target at once.

The optimizer algorithm used to detect dead code in the "assembly" SQL
instructions, implemented by sp_head::opt_mark(uint ip), was recursive
in some cases (a conditional jump pointing forward to another conditional
jump).
In case of specially crafted code, like
- a long list of "IF expr THEN stmt END IF"
- a long CASE statement
this would actually cause a server crash with a stack overflow.
In general, having a stack that grows proportionally with user data (the
SQL code given by the client in a CREATE PROCEDURE) is to be avoided.

In debug builds only, creating a SP / SF / Trigger which had a significant
amount of code would spend --literally-- several minutes in sp_head::create,
because of the debug code involved with DBUG_PRINT("info", ("Code %s ...
There are several issues with this code:
- in a CASE with 5 000 WHEN, there are 15 000 instructions generated,
  which create a sting representation of the code which is 500 000 bytes
  long,
- using a String instead of an io stream causes performances to degrade
  to a total server freeze, as time is spent doing realloc of a buffer
  always too short,
- Printing a 500 000 long string in the debug log is too verbose,
- Generating this string even when DBUG_PRINT is off is useless,
- Having code that potentially can affect the server behavior, used with
  #ifdef / #endif is useful in some cases, but is also a bad practice.

After this change
=================

"Case Expressions" (both simple and searched) have been simplified to
not use LEX::when_list, which has been removed.

Considering all the issues affecting case statements, the grammar for these
has been totally re written.

The existing actions, used to generate "assembly" sp_inst* code, have been
preserved but moved in the new grammar, with the following changes:

a) Bison rules are no longer shared between "Simple" and "Searched" case
statements, because a stack instead of a flag is required to handle them.
Nested statements are handled naturally by the parser stack, which by
definition uses the correct rule in the correct context.
Nested statements of the opposite type (simple vs searched) works correctly.
The flag sp_head::IN_SIMPLE_CASE is no longer used.
This is a step towards resolution of WL#2999, which correctly identified
that temporary parsing flags do not belong to sp_head.
The code in the action is shared by mean of the case_stmt_action_xxx()
helpers.

b) The backpatch mechanism, used to resolve forward jumps in the generated
code, has been changed to:
- create a label for the instruction following 'END CASE',
- register each jump at the end of a "WHEN expr THEN stmt" in a *unique*
  backpatch list associated with the 'END CASE' label
- resolve all the forward jumps for this label at once.

In addition, the code involving backpatch has been commented, so that a
reader can now understand by reading matching "Registering" and "Resolving"
comments how the forward jumps are resolved and what target they resolve to,
as this is far from evident when reading the code alone.

The implementation of sp_head::opt_mark() has been revised to avoid
recursive calls from jump instructions, and instead add the jump location
to the list of paths to explore during the flow analysis of the instruction
graph, with a call to sp_head::add_mark_lead().
In addition, the flow analysis will stop if an instruction has already
been marked as reachable, which the previous code failed to do in the
recursive case.
sp_head::opt_mark() is now private, to prevent new calls to this method from
being introduced.

The debug code present in sp_head::create() has been removed.
Considering that SHOW PROCEDURE CODE is also available in debug builds,
and can be used anytime regardless of the trace level, as opposed to
"CREATE PROCEDURE" time and only if the trace was on,
removing the code actually makes debugging easier (usable trace).

Tests have been written to cover the parser overflow (big CASE),
and to cover nested CASE statements.


mysql-test/r/sp-code.result:
  Test cases for nested CASE statements.
mysql-test/t/sp-code.test:
  Test cases for nested CASE statements.
sql/sp_head.cc:
  Re factored opt_mark() to avoid recursion, clean up.
sql/sp_head.h:
  Re factored opt_mark() to avoid recursion, clean up.
sql/sql_lex.cc:
  Removed when_list.
sql/sql_lex.h:
  Removed when_list.
sql/sql_yacc.yy:
  Minor clean up for case expressions,
  Major re write for case statements (Bug#19194).
mysql-test/r/sp_stress_case.result:
  New test for massive CASE statements.
mysql-test/t/sp_stress_case.sh:
  New test for massive CASE statements.
mysql-test/t/sp_stress_case.test:
  New test for massive CASE statements.

1 files changed, 415 insertions, 0 deletions

diff --git a/mysql-test/r/sp-code.result b/mysql-test/r/sp-code.result
index 4ae38861d29..0b0ad802b54 100644
--- a/mysql-test/r/sp-code.result
+++ b/mysql-test/r/sp-code.result
@@ -199,6 +199,421 @@ Pos	Instruction
 44	jump 14
 45	stmt 9 "drop temporary table sudoku_work, sud..."
 drop procedure sudoku_solve;
+DROP PROCEDURE IF EXISTS proc_19194_simple;
+DROP PROCEDURE IF EXISTS proc_19194_searched;
+DROP PROCEDURE IF EXISTS proc_19194_nested_1;
+DROP PROCEDURE IF EXISTS proc_19194_nested_2;
+DROP PROCEDURE IF EXISTS proc_19194_nested_3;
+DROP PROCEDURE IF EXISTS proc_19194_nested_4;
+CREATE PROCEDURE proc_19194_simple(i int)
+BEGIN
+DECLARE str CHAR(10);
+CASE i
+WHEN 1 THEN SET str="1";
+WHEN 2 THEN SET str="2";
+WHEN 3 THEN SET str="3";
+ELSE SET str="unknown";
+END CASE;
+SELECT str;
+END|
+CREATE PROCEDURE proc_19194_searched(i int)
+BEGIN
+DECLARE str CHAR(10);
+CASE
+WHEN i=1 THEN SET str="1";
+WHEN i=2 THEN SET str="2";
+WHEN i=3 THEN SET str="3";
+ELSE SET str="unknown";
+END CASE;
+SELECT str;
+END|
+CREATE PROCEDURE proc_19194_nested_1(i int, j int)
+BEGIN
+DECLARE str_i CHAR(10);
+DECLARE str_j CHAR(10);
+CASE i
+WHEN 10 THEN SET str_i="10";
+WHEN 20 THEN
+BEGIN
+set str_i="20";
+CASE
+WHEN j=1 THEN SET str_j="1";
+WHEN j=2 THEN SET str_j="2";
+WHEN j=3 THEN SET str_j="3";
+ELSE SET str_j="unknown";
+END CASE;
+select "i was 20";
+END;
+WHEN 30 THEN SET str_i="30";
+WHEN 40 THEN SET str_i="40";
+ELSE SET str_i="unknown";
+END CASE;
+SELECT str_i, str_j;
+END|
+CREATE PROCEDURE proc_19194_nested_2(i int, j int)
+BEGIN
+DECLARE str_i CHAR(10);
+DECLARE str_j CHAR(10);
+CASE
+WHEN i=10 THEN SET str_i="10";
+WHEN i=20 THEN
+BEGIN
+set str_i="20";
+CASE j
+WHEN 1 THEN SET str_j="1";
+WHEN 2 THEN SET str_j="2";
+WHEN 3 THEN SET str_j="3";
+ELSE SET str_j="unknown";
+END CASE;
+select "i was 20";
+END;
+WHEN i=30 THEN SET str_i="30";
+WHEN i=40 THEN SET str_i="40";
+ELSE SET str_i="unknown";
+END CASE;
+SELECT str_i, str_j;
+END|
+CREATE PROCEDURE proc_19194_nested_3(i int, j int)
+BEGIN
+DECLARE str_i CHAR(10);
+DECLARE str_j CHAR(10);
+CASE i
+WHEN 10 THEN SET str_i="10";
+WHEN 20 THEN
+BEGIN
+set str_i="20";
+CASE j
+WHEN 1 THEN SET str_j="1";
+WHEN 2 THEN SET str_j="2";
+WHEN 3 THEN SET str_j="3";
+ELSE SET str_j="unknown";
+END CASE;
+select "i was 20";
+END;
+WHEN 30 THEN SET str_i="30";
+WHEN 40 THEN SET str_i="40";
+ELSE SET str_i="unknown";
+END CASE;
+SELECT str_i, str_j;
+END|
+CREATE PROCEDURE proc_19194_nested_4(i int, j int)
+BEGIN
+DECLARE str_i CHAR(10);
+DECLARE str_j CHAR(10);
+CASE
+WHEN i=10 THEN SET str_i="10";
+WHEN i=20 THEN
+BEGIN
+set str_i="20";
+CASE
+WHEN j=1 THEN SET str_j="1";
+WHEN j=2 THEN SET str_j="2";
+WHEN j=3 THEN SET str_j="3";
+ELSE SET str_j="unknown";
+END CASE;
+select "i was 20";
+END;
+WHEN i=30 THEN SET str_i="30";
+WHEN i=40 THEN SET str_i="40";
+ELSE SET str_i="unknown";
+END CASE;
+SELECT str_i, str_j;
+END|
+SHOW PROCEDURE CODE proc_19194_simple;
+Pos	Instruction
+0	set str@1 NULL
+1	set_case_expr (12) 0 i@0
+2	jump_if_not 5(12) (case_expr@0 = 1)
+3	set str@1 _latin1'1'
+4	jump 12
+5	jump_if_not 8(12) (case_expr@0 = 2)
+6	set str@1 _latin1'2'
+7	jump 12
+8	jump_if_not 11(12) (case_expr@0 = 3)
+9	set str@1 _latin1'3'
+10	jump 12
+11	set str@1 _latin1'unknown'
+12	stmt 0 "SELECT str"
+SHOW PROCEDURE CODE proc_19194_searched;
+Pos	Instruction
+0	set str@1 NULL
+1	jump_if_not 4(11) (i@0 = 1)
+2	set str@1 _latin1'1'
+3	jump 11
+4	jump_if_not 7(11) (i@0 = 2)
+5	set str@1 _latin1'2'
+6	jump 11
+7	jump_if_not 10(11) (i@0 = 3)
+8	set str@1 _latin1'3'
+9	jump 11
+10	set str@1 _latin1'unknown'
+11	stmt 0 "SELECT str"
+SHOW PROCEDURE CODE proc_19194_nested_1;
+Pos	Instruction
+0	set str_i@2 NULL
+1	set str_j@3 NULL
+2	set_case_expr (27) 0 i@0
+3	jump_if_not 6(27) (case_expr@0 = 10)
+4	set str_i@2 _latin1'10'
+5	jump 27
+6	jump_if_not 20(27) (case_expr@0 = 20)
+7	set str_i@2 _latin1'20'
+8	jump_if_not 11(18) (j@1 = 1)
+9	set str_j@3 _latin1'1'
+10	jump 18
+11	jump_if_not 14(18) (j@1 = 2)
+12	set str_j@3 _latin1'2'
+13	jump 18
+14	jump_if_not 17(18) (j@1 = 3)
+15	set str_j@3 _latin1'3'
+16	jump 18
+17	set str_j@3 _latin1'unknown'
+18	stmt 0 "select "i was 20""
+19	jump 27
+20	jump_if_not 23(27) (case_expr@0 = 30)
+21	set str_i@2 _latin1'30'
+22	jump 27
+23	jump_if_not 26(27) (case_expr@0 = 40)
+24	set str_i@2 _latin1'40'
+25	jump 27
+26	set str_i@2 _latin1'unknown'
+27	stmt 0 "SELECT str_i, str_j"
+SHOW PROCEDURE CODE proc_19194_nested_2;
+Pos	Instruction
+0	set str_i@2 NULL
+1	set str_j@3 NULL
+2	jump_if_not 5(27) (i@0 = 10)
+3	set str_i@2 _latin1'10'
+4	jump 27
+5	jump_if_not 20(27) (i@0 = 20)
+6	set str_i@2 _latin1'20'
+7	set_case_expr (18) 0 j@1
+8	jump_if_not 11(18) (case_expr@0 = 1)
+9	set str_j@3 _latin1'1'
+10	jump 18
+11	jump_if_not 14(18) (case_expr@0 = 2)
+12	set str_j@3 _latin1'2'
+13	jump 18
+14	jump_if_not 17(18) (case_expr@0 = 3)
+15	set str_j@3 _latin1'3'
+16	jump 18
+17	set str_j@3 _latin1'unknown'
+18	stmt 0 "select "i was 20""
+19	jump 27
+20	jump_if_not 23(27) (i@0 = 30)
+21	set str_i@2 _latin1'30'
+22	jump 27
+23	jump_if_not 26(27) (i@0 = 40)
+24	set str_i@2 _latin1'40'
+25	jump 27
+26	set str_i@2 _latin1'unknown'
+27	stmt 0 "SELECT str_i, str_j"
+SHOW PROCEDURE CODE proc_19194_nested_3;
+Pos	Instruction
+0	set str_i@2 NULL
+1	set str_j@3 NULL
+2	set_case_expr (28) 0 i@0
+3	jump_if_not 6(28) (case_expr@0 = 10)
+4	set str_i@2 _latin1'10'
+5	jump 28
+6	jump_if_not 21(28) (case_expr@0 = 20)
+7	set str_i@2 _latin1'20'
+8	set_case_expr (19) 1 j@1
+9	jump_if_not 12(19) (case_expr@1 = 1)
+10	set str_j@3 _latin1'1'
+11	jump 19
+12	jump_if_not 15(19) (case_expr@1 = 2)
+13	set str_j@3 _latin1'2'
+14	jump 19
+15	jump_if_not 18(19) (case_expr@1 = 3)
+16	set str_j@3 _latin1'3'
+17	jump 19
+18	set str_j@3 _latin1'unknown'
+19	stmt 0 "select "i was 20""
+20	jump 28
+21	jump_if_not 24(28) (case_expr@0 = 30)
+22	set str_i@2 _latin1'30'
+23	jump 28
+24	jump_if_not 27(28) (case_expr@0 = 40)
+25	set str_i@2 _latin1'40'
+26	jump 28
+27	set str_i@2 _latin1'unknown'
+28	stmt 0 "SELECT str_i, str_j"
+SHOW PROCEDURE CODE proc_19194_nested_4;
+Pos	Instruction
+0	set str_i@2 NULL
+1	set str_j@3 NULL
+2	jump_if_not 5(26) (i@0 = 10)
+3	set str_i@2 _latin1'10'
+4	jump 26
+5	jump_if_not 19(26) (i@0 = 20)
+6	set str_i@2 _latin1'20'
+7	jump_if_not 10(17) (j@1 = 1)
+8	set str_j@3 _latin1'1'
+9	jump 17
+10	jump_if_not 13(17) (j@1 = 2)
+11	set str_j@3 _latin1'2'
+12	jump 17
+13	jump_if_not 16(17) (j@1 = 3)
+14	set str_j@3 _latin1'3'
+15	jump 17
+16	set str_j@3 _latin1'unknown'
+17	stmt 0 "select "i was 20""
+18	jump 26
+19	jump_if_not 22(26) (i@0 = 30)
+20	set str_i@2 _latin1'30'
+21	jump 26
+22	jump_if_not 25(26) (i@0 = 40)
+23	set str_i@2 _latin1'40'
+24	jump 26
+25	set str_i@2 _latin1'unknown'
+26	stmt 0 "SELECT str_i, str_j"
+CALL proc_19194_nested_1(10, 1);
+str_i	str_j
+10	NULL
+CALL proc_19194_nested_1(25, 1);
+str_i	str_j
+unknown	NULL
+CALL proc_19194_nested_1(20, 1);
+i was 20
+i was 20
+str_i	str_j
+20	1
+CALL proc_19194_nested_1(20, 2);
+i was 20
+i was 20
+str_i	str_j
+20	2
+CALL proc_19194_nested_1(20, 3);
+i was 20
+i was 20
+str_i	str_j
+20	3
+CALL proc_19194_nested_1(20, 4);
+i was 20
+i was 20
+str_i	str_j
+20	unknown
+CALL proc_19194_nested_1(30, 1);
+str_i	str_j
+30	NULL
+CALL proc_19194_nested_1(40, 1);
+str_i	str_j
+40	NULL
+CALL proc_19194_nested_1(0, 0);
+str_i	str_j
+unknown	NULL
+CALL proc_19194_nested_2(10, 1);
+str_i	str_j
+10	NULL
+CALL proc_19194_nested_2(25, 1);
+str_i	str_j
+unknown	NULL
+CALL proc_19194_nested_2(20, 1);
+i was 20
+i was 20
+str_i	str_j
+20	1
+CALL proc_19194_nested_2(20, 2);
+i was 20
+i was 20
+str_i	str_j
+20	2
+CALL proc_19194_nested_2(20, 3);
+i was 20
+i was 20
+str_i	str_j
+20	3
+CALL proc_19194_nested_2(20, 4);
+i was 20
+i was 20
+str_i	str_j
+20	unknown
+CALL proc_19194_nested_2(30, 1);
+str_i	str_j
+30	NULL
+CALL proc_19194_nested_2(40, 1);
+str_i	str_j
+40	NULL
+CALL proc_19194_nested_2(0, 0);
+str_i	str_j
+unknown	NULL
+CALL proc_19194_nested_3(10, 1);
+str_i	str_j
+10	NULL
+CALL proc_19194_nested_3(25, 1);
+str_i	str_j
+unknown	NULL
+CALL proc_19194_nested_3(20, 1);
+i was 20
+i was 20
+str_i	str_j
+20	1
+CALL proc_19194_nested_3(20, 2);
+i was 20
+i was 20
+str_i	str_j
+20	2
+CALL proc_19194_nested_3(20, 3);
+i was 20
+i was 20
+str_i	str_j
+20	3
+CALL proc_19194_nested_3(20, 4);
+i was 20
+i was 20
+str_i	str_j
+20	unknown
+CALL proc_19194_nested_3(30, 1);
+str_i	str_j
+30	NULL
+CALL proc_19194_nested_3(40, 1);
+str_i	str_j
+40	NULL
+CALL proc_19194_nested_3(0, 0);
+str_i	str_j
+unknown	NULL
+CALL proc_19194_nested_4(10, 1);
+str_i	str_j
+10	NULL
+CALL proc_19194_nested_4(25, 1);
+str_i	str_j
+unknown	NULL
+CALL proc_19194_nested_4(20, 1);
+i was 20
+i was 20
+str_i	str_j
+20	1
+CALL proc_19194_nested_4(20, 2);
+i was 20
+i was 20
+str_i	str_j
+20	2
+CALL proc_19194_nested_4(20, 3);
+i was 20
+i was 20
+str_i	str_j
+20	3
+CALL proc_19194_nested_4(20, 4);
+i was 20
+i was 20
+str_i	str_j
+20	unknown
+CALL proc_19194_nested_4(30, 1);
+str_i	str_j
+30	NULL
+CALL proc_19194_nested_4(40, 1);
+str_i	str_j
+40	NULL
+CALL proc_19194_nested_4(0, 0);
+str_i	str_j
+unknown	NULL
+DROP PROCEDURE proc_19194_simple;
+DROP PROCEDURE proc_19194_searched;
+DROP PROCEDURE proc_19194_nested_1;
+DROP PROCEDURE proc_19194_nested_2;
+DROP PROCEDURE proc_19194_nested_3;
+DROP PROCEDURE proc_19194_nested_4;
 DROP PROCEDURE IF EXISTS p1;
 CREATE PROCEDURE p1() CREATE INDEX idx ON t1 (c1);
 SHOW PROCEDURE CODE p1;