Avoid recursion while processing ELSIF lists in plpgsql.

tglsfdc · tglsfdc · commit 051d1ba7a02d · 2011-10-27T15:21:51.000-04:00
The original implementation of ELSIF in plpgsql converted the construct
into nested simple IF statements.  This was prone to stack overflow with
long ELSIF lists, in two different ways.  First, it's difficult to generate
the parsetree without using right-recursion in the bison grammar, and
that's prone to parser stack overflow since nothing can be reduced until
the whole list has been read.  Second, we'd recurse during execution, thus
creating an unnecessary risk of execution-time stack overflow.  Rewrite
so that the ELSIF list is represented as a flat list, scanned via iteration
not recursion, and generated through left-recursion in the grammar.
Per a gripe from Håvard Kongsgård.
diff --git a/src/pl/plpgsql/src/gram.y b/src/pl/plpgsql/src/gram.y
@@ -186,7 +186,7 @@ static	List			*read_raise_options(void);
 
 %type <str>		any_identifier opt_block_label opt_label
 
-%type <list>	proc_sect proc_stmts stmt_else
+%type <list>	proc_sect proc_stmts stmt_elsifs stmt_else
 %type <loop_body>	loop_body
 %type <stmt>	proc_stmt pl_block
 %type <stmt>	stmt_assign stmt_if stmt_loop stmt_while stmt_exit
@@ -1007,55 +1007,43 @@ assign_var		: T_DATUM
 					}
 				;
 
-stmt_if			: K_IF expr_until_then proc_sect stmt_else K_END K_IF ';'
+stmt_if			: K_IF expr_until_then proc_sect stmt_elsifs stmt_else K_END K_IF ';'
 					{
 						PLpgSQL_stmt_if *new;
 
 						new = palloc0(sizeof(PLpgSQL_stmt_if));
 						new->cmd_type	= PLPGSQL_STMT_IF;
 						new->lineno		= plpgsql_location_to_lineno(@1);
 						new->cond		= $2;
-						new->true_body	= $3;
-						new->false_body = $4;
+						new->then_body	= $3;
+						new->elsif_list = $4;
+						new->else_body  = $5;
 
 						$$ = (PLpgSQL_stmt *)new;
 					}
 				;
 
-stmt_else		:
+stmt_elsifs		:
 					{
 						$$ = NIL;
 					}
-				| K_ELSIF expr_until_then proc_sect stmt_else
-					{
-						/*----------
-						 * Translate the structure:	   into:
-						 *
-						 * IF c1 THEN				   IF c1 THEN
-						 *	 ...						   ...
-						 * ELSIF c2 THEN			   ELSE
-						 *								   IF c2 THEN
-						 *	 ...							   ...
-						 * ELSE							   ELSE
-						 *	 ...							   ...
-						 * END IF						   END IF
-						 *							   END IF
-						 *----------
-						 */
-						PLpgSQL_stmt_if *new_if;
+				| stmt_elsifs K_ELSIF expr_until_then proc_sect
+					{
+						PLpgSQL_if_elsif *new;
 
-						/* first create a new if-statement */
-						new_if = palloc0(sizeof(PLpgSQL_stmt_if));
-						new_if->cmd_type	= PLPGSQL_STMT_IF;
-						new_if->lineno		= plpgsql_location_to_lineno(@1);
-						new_if->cond		= $2;
-						new_if->true_body	= $3;
-						new_if->false_body	= $4;
+						new = palloc0(sizeof(PLpgSQL_if_elsif));
+						new->lineno = plpgsql_location_to_lineno(@2);
+						new->cond   = $3;
+						new->stmts  = $4;
 
-						/* wrap the if-statement in a "container" list */
-						$$ = list_make1(new_if);
+						$$ = lappend($1, new);
 					}
+				;
 
+stmt_else		:
+					{
+						$$ = NIL;
+					}
 				| K_ELSE proc_sect
 					{
 						$$ = $2;
diff --git a/src/pl/plpgsql/src/pl_exec.c b/src/pl/plpgsql/src/pl_exec.c
@@ -1510,22 +1510,24 @@ exec_stmt_if(PLpgSQL_execstate *estate, PLpgSQL_stmt_if *stmt)
 {
 	bool		value;
 	bool		isnull;
+	ListCell   *lc;
 
 	value = exec_eval_boolean(estate, stmt->cond, &isnull);
 	exec_eval_cleanup(estate);
-
 	if (!isnull && value)
+		return exec_stmts(estate, stmt->then_body);
+
+	foreach(lc, stmt->elsif_list)
 	{
-		if (stmt->true_body != NIL)
-			return exec_stmts(estate, stmt->true_body);
-	}
-	else
-	{
-		if (stmt->false_body != NIL)
-			return exec_stmts(estate, stmt->false_body);
+		PLpgSQL_if_elsif *elif = (PLpgSQL_if_elsif *) lfirst(lc);
+
+		value = exec_eval_boolean(estate, elif->cond, &isnull);
+		exec_eval_cleanup(estate);
+		if (!isnull && value)
+			return exec_stmts(estate, elif->stmts);
 	}
 
-	return PLPGSQL_RC_OK;
+	return exec_stmts(estate, stmt->else_body);
 }
 
 
diff --git a/src/pl/plpgsql/src/pl_funcs.c b/src/pl/plpgsql/src/pl_funcs.c
@@ -446,9 +446,18 @@ free_assign(PLpgSQL_stmt_assign *stmt)
 static void
 free_if(PLpgSQL_stmt_if *stmt)
 {
+	ListCell   *l;
+
 	free_expr(stmt->cond);
-	free_stmts(stmt->true_body);
-	free_stmts(stmt->false_body);
+	free_stmts(stmt->then_body);
+	foreach(l, stmt->elsif_list)
+	{
+		PLpgSQL_if_elsif *elif = (PLpgSQL_if_elsif *) lfirst(l);
+
+		free_expr(elif->cond);
+		free_stmts(elif->stmts);
+	}
+	free_stmts(stmt->else_body);
 }
 
 static void
@@ -877,20 +886,29 @@ dump_assign(PLpgSQL_stmt_assign *stmt)
 static void
 dump_if(PLpgSQL_stmt_if *stmt)
 {
+	ListCell   *l;
+
 	dump_ind();
 	printf("IF ");
 	dump_expr(stmt->cond);
 	printf(" THEN\n");
+	dump_stmts(stmt->then_body);
+	foreach(l, stmt->elsif_list)
+	{
+		PLpgSQL_if_elsif *elif = (PLpgSQL_if_elsif *) lfirst(l);
 
-	dump_stmts(stmt->true_body);
-
-	if (stmt->false_body != NIL)
+		dump_ind();
+		printf("    ELSIF ");
+		dump_expr(elif->cond);
+		printf(" THEN\n");
+		dump_stmts(elif->stmts);
+	}
+	if (stmt->else_body != NIL)
 	{
 		dump_ind();
 		printf("    ELSE\n");
-		dump_stmts(stmt->false_body);
+		dump_stmts(stmt->else_body);
 	}
-
 	dump_ind();
 	printf("    ENDIF\n");
 }
diff --git a/src/pl/plpgsql/src/plpgsql.h b/src/pl/plpgsql/src/plpgsql.h
@@ -396,11 +396,19 @@ typedef struct
 {								/* IF statement				*/
 	int			cmd_type;
 	int			lineno;
-	PLpgSQL_expr *cond;
-	List	   *true_body;		/* List of statements */
-	List	   *false_body;		/* List of statements */
+	PLpgSQL_expr *cond;			/* boolean expression for THEN */
+	List	   *then_body;		/* List of statements */
+	List	   *elsif_list;		/* List of PLpgSQL_if_elsif structs */
+	List	   *else_body;		/* List of statements */
 } PLpgSQL_stmt_if;
 
+typedef struct					/* one ELSIF arm of IF statement */
+{
+	int			lineno;
+	PLpgSQL_expr *cond;			/* boolean expression for this case */
+	List	   *stmts;			/* List of statements */
+} PLpgSQL_if_elsif;
+
 
 typedef struct					/* CASE statement */
 {
