Fix LP BUG#718593

Analysis:
Build_equal_items_for_cond() rewrites the WHERE clause in such a way,
that it may merge the list join->cond_equal->current_level with the
list of child Items in an AND condition of the WHERE clause.

The place where this is done is:
static COND *build_equal_items_for_cond(THD *thd, COND *cond,
                                        COND_EQUAL *inherited)
{
  ...
      if (and_level)
    {
      args->concat(&eq_list);
      args->concat((List<Item> *)&cond_equal.current_level);
    }
  ...
}

As a result, later transformations on the WHERE clause may change the
structure of the list join->cond_equal->current_level without knowing this.

Specifically in this bug, Item_in_subselect::inject_in_to_exists_cond
creates a new AND of the old WHERE clause and the IN->EXISTS conditions.
It then calls fix_fields() for the new AND. Among other things, fix_fields
flattens all nested ANDs into one by merging the AND argument lists.

When there is a cond_equal for the JOIN, its list of Item_equal objects
is attached to the end of the original AND. When a lower-level AND is
merged into the top-level one, the argument list of the lower-level AND
is concatenated to the list of multiple equalities in the upper-level AND.

As a result, when substitute_for_best_equal_field processes the 
multiple equalities, it turns out that the multiple equality list contains
the Items from the lower-level AND which were concatenated to the end of
the join->cond_equal->current_level list. This results in a crash because
this list must not contain any other Items except for the previously found
Item_equal ones.

Solution:
When performing IN->EXIST predicate injection, and the where clause is an
AND, detach the list of Item_equal objects before calling fix_fields on
the injected where clause.

After fix_fields is done, reattach back the multiple equalities list to
the end of the argument list of the new AND.

7 files changed, 121 insertions, 6 deletions

diff --git a/mysql-test/r/subselect3.result b/mysql-test/r/subselect3.result
index f246ac7a42e..d295e32bf09 100644
--- a/mysql-test/r/subselect3.result
+++ b/mysql-test/r/subselect3.result
@@ -163,7 +163,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	5	test.t1.b	1	100.00	Using where
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and (`test`.`t2`.`a` = `test`.`t1`.`b`) and trigcond(((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`) or isnull(`test`.`t1`.`a`)))) having trigcond(<is_not_null_test>(`test`.`t1`.`a`))))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and trigcond(((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`) or isnull(`test`.`t1`.`a`))) and (`test`.`t2`.`a` = `test`.`t1`.`b`)) having trigcond(<is_not_null_test>(`test`.`t1`.`a`))))) AS `Z` from `test`.`t3`
 drop table t1, t2, t3;
 create table t1 (a int NOT NULL, b int NOT NULL, key(a));
 insert into t1 values 
@@ -191,7 +191,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	4	test.t1.b	1	100.00	Using where
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and (`test`.`t2`.`a` = `test`.`t1`.`b`) and trigcond((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`)))))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and trigcond((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`)) and (`test`.`t2`.`a` = `test`.`t1`.`b`))))) AS `Z` from `test`.`t3`
 drop table t1,t2,t3;
 create table t1 (oref int, grp int);
 insert into t1 (oref, grp) values
diff --git a/mysql-test/r/subselect3_jcl6.result b/mysql-test/r/subselect3_jcl6.result
index ec8a66d948a..8a3871e1651 100644
--- a/mysql-test/r/subselect3_jcl6.result
+++ b/mysql-test/r/subselect3_jcl6.result
@@ -170,7 +170,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	5	test.t1.b	1	100.00	Using where; Using join buffer (flat, BKA join)
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and (`test`.`t2`.`a` = `test`.`t1`.`b`) and trigcond(((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`) or isnull(`test`.`t1`.`a`)))) having trigcond(<is_not_null_test>(`test`.`t1`.`a`))))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and trigcond(((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`) or isnull(`test`.`t1`.`a`))) and (`test`.`t2`.`a` = `test`.`t1`.`b`)) having trigcond(<is_not_null_test>(`test`.`t1`.`a`))))) AS `Z` from `test`.`t3`
 drop table t1, t2, t3;
 create table t1 (a int NOT NULL, b int NOT NULL, key(a));
 insert into t1 values 
@@ -198,7 +198,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	4	test.t1.b	1	100.00	Using where; Using join buffer (flat, BKA join)
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and (`test`.`t2`.`a` = `test`.`t1`.`b`) and trigcond((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`)))))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`b` = `test`.`t3`.`oref`) and trigcond((<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`)) and (`test`.`t2`.`a` = `test`.`t1`.`b`))))) AS `Z` from `test`.`t3`
 drop table t1,t2,t3;
 create table t1 (oref int, grp int);
 insert into t1 (oref, grp) values
diff --git a/mysql-test/r/subselect4.result b/mysql-test/r/subselect4.result
index 9d2fd087afb..2b3249ff69c 100644
--- a/mysql-test/r/subselect4.result
+++ b/mysql-test/r/subselect4.result
@@ -1654,3 +1654,49 @@ f1b	f2b	f3b
 10	5	d1d
 set @@optimizer_switch=@save_optimizer_switch;
 drop table t0,t1,t2;
+#                                                                                                                                                     
+# LP BUG#718593 Crash in substitute_for_best_equal_field -> eliminate_item_equal -> 
+# Item_field::find_item_equal -> Item_equal::contains
+#                                                                                                                                                     
+set @save_optimizer_switch=@@optimizer_switch;
+SET @@optimizer_switch = 'semijoin=off';
+CREATE TABLE t1 ( f3 int(11), f10 varchar(1), f11 varchar(1)) ;
+INSERT IGNORE INTO t1 VALUES (6,'f','f'),(2,'d','d');
+CREATE TABLE t2 ( f12 int(11), f13 int(11)) ;
+insert into t2 values (1,2), (3,4);
+EXPLAIN
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+SELECT alias2.f3
+FROM t1 AS alias1 JOIN t1 AS alias2 ON alias2.f10 = alias1.f11
+WHERE alias1.f11 OR alias1.f3 = 50 AND alias1.f10
+);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	alias1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	alias2	ALL	NULL	NULL	NULL	NULL	2	Using where; Using join buffer (flat, BNL join)
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+SELECT alias2.f3
+FROM t1 AS alias1 JOIN t1 AS alias2 ON alias2.f10 = alias1.f11
+WHERE alias1.f11 OR alias1.f3 = 50 AND alias1.f10
+);
+f12	f13
+EXPLAIN
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+SELECT alias2.f3
+FROM t1 AS alias1, t1 AS alias2
+WHERE (alias2.f10 = alias1.f11) AND (alias1.f11 OR alias1.f3 = 50 AND alias1.f10));
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	alias1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	alias2	ALL	NULL	NULL	NULL	NULL	2	Using where; Using join buffer (flat, BNL join)
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+SELECT alias2.f3
+FROM t1 AS alias1, t1 AS alias2
+WHERE (alias2.f10 = alias1.f11) AND (alias1.f11 OR alias1.f3 = 50 AND alias1.f10));
+f12	f13
+set @@optimizer_switch=@save_optimizer_switch;
+drop table t1, t2;
diff --git a/mysql-test/r/subselect_mat_cost_bugs.result b/mysql-test/r/subselect_mat_cost_bugs.result
index a3abda164fb..cd0a6c716bb 100644
--- a/mysql-test/r/subselect_mat_cost_bugs.result
+++ b/mysql-test/r/subselect_mat_cost_bugs.result
@@ -94,7 +94,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t1a	ref	c2	c2	5	test.t1b.pk	2	100.00	Using where
 Warnings:
 Note	1276	Field or reference 'test.t1.pk' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` where <expr_cache><`test`.`t1`.`c1`,`test`.`t1`.`pk`>(<in_optimizer>(`test`.`t1`.`c1`,<exists>(select `test`.`t1a`.`c1` from `test`.`t1b` join `test`.`t2` left join `test`.`t1a` on((2 and (`test`.`t1a`.`c2` = `test`.`t1b`.`pk`))) where (`test`.`t1`.`pk` and (`test`.`t1b`.`c4` = `test`.`t2`.`c3`) and (<cache>(`test`.`t1`.`c1`) = `test`.`t1a`.`c1`)))))
+Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` where <expr_cache><`test`.`t1`.`c1`,`test`.`t1`.`pk`>(<in_optimizer>(`test`.`t1`.`c1`,<exists>(select `test`.`t1a`.`c1` from `test`.`t1b` join `test`.`t2` left join `test`.`t1a` on((2 and (`test`.`t1a`.`c2` = `test`.`t1b`.`pk`))) where (`test`.`t1`.`pk` and (<cache>(`test`.`t1`.`c1`) = `test`.`t1a`.`c1`) and (`test`.`t1b`.`c4` = `test`.`t2`.`c3`)))))
 SELECT pk
 FROM t1
 WHERE c1 IN
diff --git a/mysql-test/t/subselect4.test b/mysql-test/t/subselect4.test
index 051375c43ef..4b262a070cc 100644
--- a/mysql-test/t/subselect4.test
+++ b/mysql-test/t/subselect4.test
@@ -1327,3 +1327,46 @@ SELECT * FROM t2 WHERE (f1b) IN (SELECT f1a FROM t1 GROUP BY f1a, f2a);
 set @@optimizer_switch=@save_optimizer_switch;
 
 drop table t0,t1,t2;
+
+--echo #                                                                                                                                                     
+--echo # LP BUG#718593 Crash in substitute_for_best_equal_field -> eliminate_item_equal -> 
+--echo # Item_field::find_item_equal -> Item_equal::contains
+--echo #                                                                                                                                                     
+
+set @save_optimizer_switch=@@optimizer_switch;
+SET @@optimizer_switch = 'semijoin=off';
+
+CREATE TABLE t1 ( f3 int(11), f10 varchar(1), f11 varchar(1)) ;
+INSERT IGNORE INTO t1 VALUES (6,'f','f'),(2,'d','d');
+
+CREATE TABLE t2 ( f12 int(11), f13 int(11)) ;
+insert into t2 values (1,2), (3,4);
+
+EXPLAIN
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+        SELECT alias2.f3
+        FROM t1 AS alias1 JOIN t1 AS alias2 ON alias2.f10 = alias1.f11
+        WHERE alias1.f11 OR alias1.f3 = 50 AND alias1.f10
+);
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+        SELECT alias2.f3
+        FROM t1 AS alias1 JOIN t1 AS alias2 ON alias2.f10 = alias1.f11
+        WHERE alias1.f11 OR alias1.f3 = 50 AND alias1.f10
+);
+
+EXPLAIN
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+        SELECT alias2.f3
+        FROM t1 AS alias1, t1 AS alias2
+        WHERE (alias2.f10 = alias1.f11) AND (alias1.f11 OR alias1.f3 = 50 AND alias1.f10));
+SELECT * FROM t2
+WHERE ( f12 ) IN (
+        SELECT alias2.f3
+        FROM t1 AS alias1, t1 AS alias2
+        WHERE (alias2.f10 = alias1.f11) AND (alias1.f11 OR alias1.f3 = 50 AND alias1.f10));
+
+set @@optimizer_switch=@save_optimizer_switch;
+drop table t1, t2;
diff --git a/sql/item_subselect.cc b/sql/item_subselect.cc
index 28019e850e5..459b025870a 100644
--- a/sql/item_subselect.cc
+++ b/sql/item_subselect.cc
@@ -2061,6 +2061,24 @@ bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
 
   if (where_item)
   {
+    List<Item> *and_args= NULL;
+    /*
+      If the top-level Item of the WHERE clause is an AND, detach the multiple
+      equality list that was attached to the end of the AND argument list by
+      build_equal_items_for_cond(). The multiple equalities must be detached
+      because fix_fields merges lower level AND arguments into the upper AND.
+      As a result, the arguments from lower-level ANDs are concatenated after
+      the multiple equalities. When the multiple equality list is treated as
+      such, it turns out that it contains non-Item_equal object which is wrong.
+    */
+    if (join_arg->conds && join_arg->conds->type() == Item::COND_ITEM &&
+        ((Item_cond*) join_arg->conds)->functype() == Item_func::COND_AND_FUNC)
+    {
+      and_args= ((Item_cond*) join_arg->conds)->argument_list();
+      if (join_arg->cond_equal)
+        and_args->disjoin((List<Item> *) &join_arg->cond_equal->current_level);
+    }
+
     where_item= and_items(join_arg->conds, where_item);
     if (!where_item->fixed && where_item->fix_fields(thd, 0))
       DBUG_RETURN(true);
@@ -2068,6 +2086,14 @@ bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
     thd->change_item_tree(&select_lex->where, where_item);
     select_lex->where->top_level_item();
     join_arg->conds= select_lex->where;
+
+    /* Attach back the list of multiple equalities to the new top-level AND. */
+    if (and_args && join_arg->cond_equal)
+    {
+      /* The argument list of the top-level AND may change after fix fields. */
+      and_args= ((Item_cond*) join_arg->conds)->argument_list();
+      and_args->concat((List<Item> *) &join_arg->cond_equal->current_level);
+    }
   }
 
   if (having_item)
diff --git a/sql/sql_list.h b/sql/sql_list.h
index 2dade14f211..e90f16aeb99 100644
--- a/sql/sql_list.h
+++ b/sql/sql_list.h
@@ -260,7 +260,7 @@ public:
     list_node *node= first;
     list_node *list_first= list->first;
     elements=0;
-    while (node && node != list_first)
+    while (node->info && node != list_first)
     {
       prev= &node->next;
       node= node->next;