MDEV-30248 Infinite sequence of recursive calls when processing embedded CTE

This patch fixes the patch for bug MDEV-30248 that unsatisfactorily
resolved the problem of resolution of references to CTE. In some cases
when such a reference has the same table name as the name of one of
CTEs containing this reference the reference could be resolved incorrectly
that led to an invalid select tree where units could be mutually dependent.
This in its turn could lead to an infinite sequence of recursive calls or
to falls into infinite loops.

The patch also removes LEX::resolve_references_to_cte_in_hanging_cte() as
with the new code for resolution of CTE references the call of this
function is not needed anymore.

Approved by Oleksandr Byelkin <sanja@mariadb.com>

5 files changed, 311 insertions, 81 deletions

diff --git a/mysql-test/main/cte_recursive.result b/mysql-test/main/cte_recursive.result
index c4b66794e3d..e7aeeffcdbe 100644
--- a/mysql-test/main/cte_recursive.result
+++ b/mysql-test/main/cte_recursive.result
@@ -5604,5 +5604,177 @@ r
 3
 drop table t1,t2,t3,x;
 #
+# MDEV-30248: Embedded non-recursive CTE referring to base table 'x'
+#             within a CTE with name 'x' used in a subquery from
+#             select list of another CTE
+#
+CREATE TABLE x (a int) ENGINE=MyISAM;
+INSERT INTO x VALUES (3),(7),(1);
+CREATE TABLE t1 (b int) ENGINE=MYISAM;
+INSERT INTO t1 VALUES (1);
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+c
+1
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT b FROM t1)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+c
+1
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH y AS (SELECT a FROM x AS t) SELECT b FROM t1)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+c
+1
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH y(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM y)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+c
+3
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM x)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+c
+3
+WITH x AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT x.c from x;
+c
+1
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT 2 AS b)
+SELECT r1.b FROM x AS r1, x AS r2 WHERE r1.b=r2.b
+) AS c
+)
+SELECT cte.c from cte;
+c
+2
+DROP TABLE x;
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+ERROR 42S02: Table 'test.x' doesn't exist
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT b FROM t1)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+ERROR 42S02: Table 'test.x' doesn't exist
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH y AS (SELECT a FROM x AS t) SELECT b FROM t1)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+ERROR 42S02: Table 'test.x' doesn't exist
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH y(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM y)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+ERROR 42S02: Table 'test.x' doesn't exist
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM x)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT cte.c FROM cte;
+ERROR 42S02: Table 'test.x' doesn't exist
+WITH x AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)
+SELECT b FROM x AS r
+) AS c
+)
+SELECT x.c from x;
+ERROR 42S02: Table 'test.x' doesn't exist
+WITH cte AS
+(
+SELECT
+(
+WITH x AS
+(WITH x AS (SELECT a FROM x AS t) SELECT 2 AS b)
+SELECT r1.b FROM x AS r1, x AS r2 WHERE r1.b=r2.b
+) AS c
+)
+SELECT cte.c from cte;
+ERROR 42S02: Table 'test.x' doesn't exist
+DROP TABLE t1;
+#
 # End of 10.3 tests
 #
diff --git a/mysql-test/main/cte_recursive.test b/mysql-test/main/cte_recursive.test
index 270a5023d31..f4dafbf9294 100644
--- a/mysql-test/main/cte_recursive.test
+++ b/mysql-test/main/cte_recursive.test
@@ -3872,5 +3872,128 @@ select * from cte;
 drop table t1,t2,t3,x;
 
 --echo #
+--echo # MDEV-30248: Embedded non-recursive CTE referring to base table 'x'
+--echo #             within a CTE with name 'x' used in a subquery from
+--echo #             select list of another CTE
+--echo #
+
+CREATE TABLE x (a int) ENGINE=MyISAM;
+INSERT INTO x VALUES (3),(7),(1);
+CREATE TABLE t1 (b int) ENGINE=MYISAM;
+INSERT INTO t1 VALUES (1);
+
+let $q1=
+WITH cte AS
+(
+  SELECT
+    (
+      WITH x AS
+      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)
+      SELECT b FROM x AS r
+    ) AS c
+)
+SELECT cte.c FROM cte;
+eval $q1;
+
+let $q2=
+WITH cte AS
+(
+  SELECT
+    (
+      WITH x AS
+      (WITH x AS (SELECT a FROM x AS t) SELECT b FROM t1)
+      SELECT b FROM x AS r
+    ) AS c
+)
+SELECT cte.c FROM cte;
+eval $q2;
+
+let $q3=
+WITH cte AS
+(
+  SELECT
+    (
+      WITH x AS
+      (WITH y AS (SELECT a FROM x AS t) SELECT b FROM t1)
+      SELECT b FROM x AS r
+    ) AS c
+)
+SELECT cte.c FROM cte;
+eval $q3;
+
+
+let $q4=
+WITH cte AS
+(
+  SELECT
+    (
+      WITH x AS
+      (WITH y(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM y)
+      SELECT b FROM x AS r
+    ) AS c
+)
+SELECT cte.c FROM cte;
+eval $q4;
+
+let $q5=
+WITH cte AS
+(
+  SELECT
+    (
+      WITH x AS
+      (WITH x(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM x)
+      SELECT b FROM x AS r
+    ) AS c
+)
+SELECT cte.c FROM cte;
+eval $q5;
+
+let $q6=
+WITH x AS
+(
+  SELECT
+    (
+      WITH x AS
+      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)
+      SELECT b FROM x AS r
+    ) AS c
+)
+SELECT x.c from x;
+eval $q6;
+
+let $q7=
+WITH cte AS
+(
+  SELECT
+    (
+      WITH x AS
+      (WITH x AS (SELECT a FROM x AS t) SELECT 2 AS b)
+      SELECT r1.b FROM x AS r1, x AS r2 WHERE r1.b=r2.b
+    ) AS c
+)
+SELECT cte.c from cte;
+eval $q7;
+
+
+DROP TABLE x;
+
+--ERROR ER_NO_SUCH_TABLE
+eval $q1;
+--ERROR ER_NO_SUCH_TABLE
+eval $q2;
+--ERROR ER_NO_SUCH_TABLE
+eval $q3;
+--ERROR ER_NO_SUCH_TABLE
+eval $q4;
+--ERROR ER_NO_SUCH_TABLE
+eval $q5;
+--ERROR ER_NO_SUCH_TABLE
+eval $q6;
+--ERROR ER_NO_SUCH_TABLE
+eval $q7;
+
+DROP TABLE t1;
+
+--echo #
 --echo # End of 10.3 tests
 --echo #
diff --git a/sql/sql_cte.cc b/sql/sql_cte.cc
index d7e3eec78e8..b3b54d7fe59 100644
--- a/sql/sql_cte.cc
+++ b/sql/sql_cte.cc
@@ -93,49 +93,6 @@ bool LEX::check_dependencies_in_with_clauses()
 
 /**
   @brief
-    Resolve references to CTE in specification of hanging CTE
-
-  @details
-    A CTE to which there are no references in the query is called hanging CTE.
-    Although such CTE is not used for execution its specification must be
-    subject to context analysis. All errors concerning references to
-    non-existing tables or fields occurred in the specification must be
-    reported as well as all other errors caught at the prepare stage.
-    The specification of a hanging CTE might contain references to other
-    CTE outside of the specification and within it if the specification
-    contains a with clause. This function resolves all such references for
-    all hanging CTEs encountered in the processed query.
-
-  @retval
-    false   on success
-    true    on failure
-*/
-
-bool
-LEX::resolve_references_to_cte_in_hanging_cte()
-{
-  for (With_clause *with_clause= with_clauses_list;
-       with_clause; with_clause= with_clause->next_with_clause)
-  {
-    for (With_element *with_elem= with_clause->with_list.first;
-         with_elem; with_elem= with_elem->next)
-    {
-      if (!with_elem->is_referenced())
-      {
-        TABLE_LIST *first_tbl=
-                     with_elem->spec->first_select()->table_list.first;
-        TABLE_LIST **with_elem_end_pos= with_elem->head->tables_pos.end_pos;
-        if (first_tbl && resolve_references_to_cte(first_tbl, with_elem_end_pos))
-          return true;
-      }
-    }
-  }
-  return false;
-}
-
-
-/**
-  @brief
     Resolve table references to CTE from a sub-chain of table references
 
   @param tables      Points to the beginning of the sub-chain
@@ -279,8 +236,6 @@ LEX::check_cte_dependencies_and_resolve_references()
     return false;
   if (resolve_references_to_cte(query_tables, query_tables_last))
     return true;
-  if (resolve_references_to_cte_in_hanging_cte())
-    return true;
   return false;
 }
 
@@ -479,47 +434,33 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl,
                                              st_unit_ctxt_elem *ctxt)
 {
   With_element *found= 0;
+  st_select_lex_unit *top_unit= 0;
   for (st_unit_ctxt_elem *unit_ctxt_elem= ctxt;
        unit_ctxt_elem;
        unit_ctxt_elem= unit_ctxt_elem->prev)
   {
     st_select_lex_unit *unit= unit_ctxt_elem->unit;
     With_clause *with_clause= unit->with_clause;
-    /*
-      First look for the table definition in the with clause attached to 'unit'
-      if there is any such clause.
-    */
     if (with_clause)
     {
-      found= with_clause->find_table_def(tbl, NULL);
+      /*
+        If the reference to tbl that has to be resolved belongs to
+        the FROM clause of a descendant of top_unit->with_element
+        and this with element belongs to with_clause then this
+        element must be used as the barrier for the search in the
+        the list of CTEs from with_clause unless the clause contains
+        RECURSIVE.
+      */
+      With_element *barrier= 0;
+      if (top_unit && !with_clause->with_recursive &&
+          top_unit->with_element &&
+          top_unit->with_element->get_owner() == with_clause)
+        barrier= top_unit->with_element;
+      found= with_clause->find_table_def(tbl, barrier);
       if (found)
         break;
     }
-    /*
-      If 'unit' is the unit that defines a with element then reset 'unit'
-      to the unit whose attached with clause contains this with element.
-    */
-    With_element *with_elem= unit->with_element;
-    if (with_elem)
-    {
-      if (!(unit_ctxt_elem= unit_ctxt_elem->prev))
-        break;
-      unit= unit_ctxt_elem->unit;
-    }
-    with_clause= unit->with_clause;
-    /*
-      Now look for the table definition in this with clause. If the with clause
-      contains RECURSIVE the search is performed through all CTE definitions in
-      clause, otherwise up to the definition of 'with_elem' unless it is NULL.
-    */
-    if (with_clause)
-    {
-      found= with_clause->find_table_def(tbl,
-                                         with_clause->with_recursive ?
-			                 NULL : with_elem);
-      if (found)
-	break;
-    }
+    top_unit= unit;
   }
   return found;
 }
diff --git a/sql/sql_cte.h b/sql/sql_cte.h
index b2708186008..d9dda3e227b 100644
--- a/sql/sql_cte.h
+++ b/sql/sql_cte.h
@@ -322,8 +322,6 @@ public:
   friend
   bool LEX::resolve_references_to_cte(TABLE_LIST *tables,
                                       TABLE_LIST **tables_last);
-  friend
-  bool LEX::resolve_references_to_cte_in_hanging_cte();
 };
 
 const uint max_number_of_elements_in_with_clause= sizeof(table_map)*8;
@@ -435,9 +433,6 @@ public:
 
   friend
   bool LEX::check_dependencies_in_with_clauses();
-
-  friend
-  bool LEX::resolve_references_to_cte_in_hanging_cte();
 };
 
 inline
diff --git a/sql/sql_lex.h b/sql/sql_lex.h
index febe4cf459e..064d0de8905 100644
--- a/sql/sql_lex.h
+++ b/sql/sql_lex.h
@@ -4051,7 +4051,6 @@ public:
   }
 
   bool check_dependencies_in_with_clauses();
-  bool resolve_references_to_cte_in_hanging_cte();
   bool check_cte_dependencies_and_resolve_references();
   bool resolve_references_to_cte(TABLE_LIST *tables,
                                  TABLE_LIST **tables_last);