Fix some problems with multi-column IN(SELECT...) processing.

FossilOrigin-Name: 719a3b2035a335ca8b9704646b1d641011e3ea0e

8 files changed, 195 insertions, 77 deletions

diff --git a/manifest b/manifest
index fd048d6c5..8b4409d2f 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Merge\slatest\strunk\schanges\sinto\sthis\sbranch.
-D 2016-07-26T18:15:35.133
+C Fix\ssome\sproblems\swith\smulti-column\sIN(SELECT...)\sprocessing.
+D 2016-07-27T19:33:04.107
 F Makefile.in 6c20d44f72d4564f11652b26291a214c8367e5db
 F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434
 F Makefile.msc d66d0395c38571aab3804f8db0fa20707ae4609a
@@ -337,7 +337,7 @@ F src/ctime.c 61949e83c4c36e37195a8398ebc752780b534d95
 F src/date.c 1cc9fb516ec9932c6fd4d2a0d2f8bc4480145c39
 F src/dbstat.c 4f6f7f52b49beb9636ffbd517cfe44a402ba4ad0
 F src/delete.c 4aba4214a377ce8ddde2d2e609777bcc8235200f
-F src/expr.c f84861eaaf557df45bb8f4513a78a05fbb0ad368
+F src/expr.c bee29fbb017db26ad1189d35b2a7fe6ff8da3722
 F src/fault.c 160a0c015b6c2629d3899ed2daf63d75754a32bb
 F src/fkey.c bc4145347595b7770f9a598cff1c848302cf5413
 F src/func.c 61a4114cf7004f10c542cfabbab9f2bcb9033045
@@ -381,14 +381,14 @@ F src/pragma.h 64c78a648751b9f4f297276c4eb7507b14b4628c
 F src/prepare.c 22df6171aec1d86904ed2ad30c2348a5748aa04e
 F src/printf.c a5f0ca08ddede803c241266abb46356ec748ded1
 F src/random.c ba2679f80ec82c4190062d756f22d0c358180696
-F src/resolve.c 5c4d301a855d0245ddcc27365ddcbddd2f244665
+F src/resolve.c d5516a3818748c50f98c18e4601a746e90929f1c
 F src/rowset.c 7b7e7e479212e65b723bf40128c7b36dc5afdfac
 F src/select.c 0115f5d222f5cf9b5511ec4072088417354d738a
 F src/shell.c 9351fc6de11e1d908648c0a92d85627138e3dee5
 F src/sqlite.h.in c6e68a4a47610631822a4f8f83a44c9f75339331
 F src/sqlite3.rc 5121c9e10c3964d5755191c80dd1180c122fc3a8
 F src/sqlite3ext.h 46f300b6e300e0fa916d7d58c44b53415b8471a9
-F src/sqliteInt.h a78e53083262e9a10fd1f09a8777755253c00b44
+F src/sqliteInt.h 9a6af8787f03f54ce02ff88bd45f89bb600c3a4c
 F src/sqliteLimit.h c0373387c287c8d0932510b5547ecde31b5da247
 F src/status.c 5b18f9526900f61189ab0b83f1ef41d9f871a2ab
 F src/table.c 5226df15ab9179b9ed558d89575ea0ce37b03fc9
@@ -463,7 +463,7 @@ F src/vxworks.h d2988f4e5a61a4dfe82c6524dd3d6e4f2ce3cdb9
 F src/wal.c 02eeecc265f6ffd0597378f5d8ae9070b62a406a
 F src/wal.h 6dd221ed384afdc204bc61e25c23ef7fd5a511f2
 F src/walker.c 0f142b5bd3ed2041fc52d773880748b212e63354
-F src/where.c e7054b2c1fe31fef5136e5735d7958f5c2c7707d
+F src/where.c 0b370db8ce08fac93a098f27eaf425d2269be376
 F src/whereInt.h 14dd243e13b81cbb0a66063d38b70f93a7d6e613
 F src/wherecode.c 3aff7683566af3428f865904aafa7efb1fbd8701
 F src/whereexpr.c b896f8ff6a53cbd3daaee84ec33e39098762bb46
@@ -822,7 +822,7 @@ F test/hook.test 3b7b99d0eece6d279812c2aef6fa08bdfabc633e
 F test/icu.test 73956798bace8982909c00476b216714a6d0559a
 F test/ieee754.test 806fc0ce7f305f57e3331eaceeddcfec9339e607
 F test/imposter1.test c3f1db2d3db2c24611a6596a3fc0ffc14f1466c8
-F test/in.test 41d18d4bcd27c55d0bc6b6ddc8ff9e85e91728a4
+F test/in.test 20c5529986998949908f889c8208b2cd894b2cc9
 F test/in2.test 5d4c61d17493c832f7d2d32bef785119e87bde75
 F test/in3.test 3cbf58c87f4052cee3a58b37b6389777505aa0c0
 F test/in4.test d2b38cba404bc4320f4fe1b595b3d163f212c068
@@ -1019,7 +1019,7 @@ F test/rowhash.test 0bc1d31415e4575d10cacf31e1a66b5cc0f8be81
 F test/rowid.test 5b7509f384f4f6fae1af3c8c104c8ca299fea18d
 F test/rowvalue.test 979738b3d49f1d93e3fee56a71d4446217917abc
 F test/rowvalue2.test 8d5dfe75b8f4d1868a2f91f0356f20d36cba64ff
-F test/rowvalue3.test eeec47b4de27217a012dd142956b01af4e9bd6f2
+F test/rowvalue3.test 587c1056016fa6b7a40a9bf6cb85d5443fa47d96
 F test/rtree.test 0c8d9dd458d6824e59683c19ab2ffa9ef946f798
 F test/run-wordcount.sh 891e89c4c2d16e629cd45951d4ed899ad12afc09
 F test/savepoint.test c671fdbd34cd3bfe1518a777526ada595180cf8d
@@ -1510,7 +1510,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 061b8006034f06a0311b4304c8b14d2c8b0153df 483994a54dee3c7a3801e0e9d3c96fa9dbd8d2fd
-R 675e1e72a3d3f117d790dda9dd43e7d1
+P d4f3d52c5a11fc7ad7e8cad76361edbcef13a12f 4d59df02d3713b3e3804e1a88e676749b2794286
+R 1d3755c62e27d021f9887ac09a170360
 U dan
-Z b0c1b915de5ec6a4159f97e64d5655ae
+Z 2549ddc5292b60c5848a8cde952880f9
diff --git a/manifest.uuid b/manifest.uuid
index e9f6e44c6..21c747881 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-d4f3d52c5a11fc7ad7e8cad76361edbcef13a12f
\ No newline at end of file
+719a3b2035a335ca8b9704646b1d641011e3ea0e
\ No newline at end of file
diff --git a/src/expr.c b/src/expr.c
index f35ac56f8..3c95136c5 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -2480,20 +2480,20 @@ static void sqlite3ExprCodeIN(
   }else{
   
     /* If the LHS is NULL, then the result is either false or NULL depending
-    ** on whether the RHS is empty or not, respectively.
-    */
-    if( nVector==1 && sqlite3ExprCanBeNull(pExpr->pLeft) ){
-      if( destIfNull==destIfFalse ){
-        /* Shortcut for the common case where the false and NULL outcomes are
-        ** the same. */
-        sqlite3VdbeAddOp2(v, OP_IsNull, r1, destIfNull); VdbeCoverage(v);
-      }else{
-        int addr1 = sqlite3VdbeAddOp1(v, OP_NotNull, r1); VdbeCoverage(v);
-        sqlite3VdbeAddOp2(v, OP_Rewind, pExpr->iTable, destIfFalse);
-        VdbeCoverage(v);
-        sqlite3VdbeGoto(v, destIfNull);
-        sqlite3VdbeJumpHere(v, addr1);
+    ** on whether the RHS is empty or not, respectively.  */
+    if( destIfNull==destIfFalse ){
+      for(i=0; i<nVector; i++){
+        Expr *p = exprVectorField(pExpr->pLeft, i);
+        if( sqlite3ExprCanBeNull(p) ){
+          sqlite3VdbeAddOp2(v, OP_IsNull, r1+aiMap[i], destIfNull);
+        }
       }
+    }else if( nVector==1 && sqlite3ExprCanBeNull(pExpr->pLeft) ){
+      int addr1 = sqlite3VdbeAddOp1(v, OP_NotNull, r1); VdbeCoverage(v);
+      sqlite3VdbeAddOp2(v, OP_Rewind, pExpr->iTable, destIfFalse);
+      VdbeCoverage(v);
+      sqlite3VdbeGoto(v, destIfNull);
+      sqlite3VdbeJumpHere(v, addr1);
     }
   
     if( eType==IN_INDEX_ROWID ){
@@ -2501,7 +2501,7 @@ static void sqlite3ExprCodeIN(
       */
       sqlite3VdbeAddOp3(v, OP_SeekRowid, pExpr->iTable, destIfFalse, r1);
       VdbeCoverage(v);
-    }else if( nVector>1 && eType==IN_INDEX_EPH ){
+    }else if( nVector>1 && eType==IN_INDEX_EPH && destIfNull!=destIfFalse ){
       int regNull = sqlite3GetTempReg(pParse);
       int r2 = sqlite3GetTempReg(pParse);
       int r3 = sqlite3GetTempReg(pParse);
@@ -3494,7 +3494,7 @@ int sqlite3ExprCodeTarget(Parse *pParse, Expr *pExpr, int target){
     }
 
     case TK_VECTOR: {
-      sqlite3ErrorMsg(pParse, "invalid use of row value (1)");
+      sqlite3ErrorMsg(pParse, "invalid use of row value");
       break;
     }
 
diff --git a/src/resolve.c b/src/resolve.c
index cb9f2fbaa..4d8873963 100644
--- a/src/resolve.c
+++ b/src/resolve.c
@@ -767,14 +767,7 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){
         }
 
         if( pExpr->op==TK_SELECT && pExpr->x.pSelect->pEList->nExpr>1 ){
-          if( !ExprHasProperty(pExpr, EP_VectorOk) && 0 ){
-            sqlite3ErrorMsg(pParse, "invalid use of row value");
-          }else{
-            ExprSetProperty(pExpr, EP_Vector);
-          }
-        }
-        if( pExpr->op==TK_IN ){
-          ExprSetProperty(pExpr->pLeft, EP_VectorOk);
+          ExprSetProperty(pExpr, EP_Vector);
         }
       }
       break;
@@ -784,27 +777,8 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){
       break;
     }
 
-    case TK_BETWEEN: {
-      ExprSetProperty(pExpr->pLeft, EP_VectorOk);
-      ExprSetProperty(pExpr->x.pList->a[0].pExpr, EP_VectorOk);
-      ExprSetProperty(pExpr->x.pList->a[1].pExpr, EP_VectorOk);
-      break;
-    }
-
-    case TK_EQ: case TK_NE: case TK_IS: case TK_ISNOT: 
-    case TK_LE: case TK_LT: case TK_GE: case TK_GT: 
-    {
-      ExprSetProperty(pExpr->pLeft, EP_VectorOk);
-      ExprSetProperty(pExpr->pRight, EP_VectorOk);
-      break;
-    };
-
     case TK_VECTOR: {
-      if( !ExprHasProperty(pExpr, EP_VectorOk) ){
-        sqlite3ErrorMsg(pParse, "invalid use of row value");
-      }else{
-        ExprSetProperty(pExpr, EP_Vector);
-      }
+      ExprSetProperty(pExpr, EP_Vector);
       break;
     }
   }
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 1f653c08f..7219732bc 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -2327,8 +2327,7 @@ struct Expr {
 #define EP_CanBeNull 0x100000 /* Can be null despite NOT NULL constraint */
 #define EP_Subquery  0x200000 /* Tree contains a TK_SELECT operator */
 #define EP_Alias     0x400000 /* Is an alias for a result set column */
-#define EP_VectorOk  0x800000 /* This expression may be a row value */
-#define EP_Vector    0x1000000/* This expression is a row value */
+#define EP_Vector    0x800000 /* This expression is a row value */
 
 /*
 ** Combinations of two or more EP_* flags
diff --git a/src/where.c b/src/where.c
index 095891842..6c039c6b7 100644
--- a/src/where.c
+++ b/src/where.c
@@ -3477,20 +3477,38 @@ static i8 wherePathSatisfiesOrderBy(
       rev = revSet = 0;
       distinctColumns = 0;
       for(j=0; j<nColumn; j++){
-        u8 bOnce;   /* True to run the ORDER BY search loop */
+        u8 bOnce = 1; /* True to run the ORDER BY search loop */
 
-        /* Skip over == and IS and ISNULL terms.
-        ** (Also skip IN terms when doing WHERE_ORDERBY_LIMIT processing)
-        */
-        if( j<pLoop->u.btree.nEq
-         && pLoop->nSkip==0
-         && ((i = pLoop->aLTerm[j]->eOperator) & eqOpMask)!=0
-        ){
-          if( i & WO_ISNULL ){
-            testcase( isOrderDistinct );
-            isOrderDistinct = 0;
+        assert( j>=pLoop->u.btree.nEq 
+            || (pLoop->aLTerm[j]==0)==(j<pLoop->nSkip)
+        );
+        if( j<pLoop->u.btree.nEq && j>=pLoop->nSkip ){
+          u16 eOp = pLoop->aLTerm[j]->eOperator;
+
+          /* Skip over == and IS and ISNULL terms.  (Also skip IN terms when
+          ** doing WHERE_ORDERBY_LIMIT processing). 
+          **
+          ** If the current term is a column of an ((?,?) IN (SELECT...)) 
+          ** expression for which the SELECT returns more than one column,
+          ** check that it is the only column used by this loop. Otherwise,
+          ** if it is one of two or more, none of the columns can be
+          ** considered to match an ORDER BY term.  */
+          if( (eOp & eqOpMask)!=0 ){
+            if( eOp & WO_ISNULL ){
+              testcase( isOrderDistinct );
+              isOrderDistinct = 0;
+            }
+            continue;  
+          }else if( eOp & WO_IN ){
+            Expr *pX = pLoop->aLTerm[j]->pExpr;
+            for(i=j+1; i<pLoop->u.btree.nEq; i++){
+              if( pLoop->aLTerm[i]->pExpr==pX ){
+                assert( (pLoop->aLTerm[i]->eOperator & WO_IN) );
+                bOnce = 0;
+                break;
+              }
+            }
           }
-          continue;  
         }
 
         /* Get the column number in the table (iColumn) and sort order
@@ -3519,7 +3537,6 @@ static i8 wherePathSatisfiesOrderBy(
         /* Find the ORDER BY term that corresponds to the j-th column
         ** of the index and mark that ORDER BY term off 
         */
-        bOnce = 1;
         isMatch = 0;
         for(i=0; bOnce && i<nOrderBy; i++){
           if( MASKBIT(i) & obSat ) continue;
@@ -4012,7 +4029,7 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){
       if( pWInfo->nOBSat<=0 ){
         pWInfo->nOBSat = 0;
         if( nLoop>0 ){
-          Bitmask m;
+          Bitmask m = 0;
           int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom,
                       WHERE_ORDERBY_LIMIT, nLoop-1, pFrom->aLoop[nLoop-1], &m);
           if( rc==pWInfo->pOrderBy->nExpr ){
diff --git a/test/in.test b/test/in.test
index c88a4a695..4e1080048 100644
--- a/test/in.test
+++ b/test/in.test
@@ -641,4 +641,15 @@ do_test in-13.X {
   db nullvalue ""
 } {}
 
+# At one point the following was causing valgrind to report a "jump
+# depends on unitialized location" problem.
+#
+do_execsql_test in-14.0 {
+  CREATE TABLE c1(a);
+  INSERT INTO c1 VALUES(1), (2), (4), (3);
+}
+do_execsql_test in-14.1 {
+  SELECT * FROM c1 WHERE a IN (SELECT a FROM c1) ORDER BY 1
+} {1 2 3 4}
+
 finish_test
diff --git a/test/rowvalue3.test b/test/rowvalue3.test
index 78bf21b61..32c86251d 100644
--- a/test/rowvalue3.test
+++ b/test/rowvalue3.test
@@ -17,6 +17,14 @@ set testdir [file dirname $argv0]
 source $testdir/tester.tcl
 set ::testprefix rowvalue3
 
+# Drop all auxiliary indexes from the main database opened by handle [db].
+#
+proc drop_all_indexes {} {
+  set L [db eval {
+    SELECT name FROM sqlite_master WHERE type='index' AND sql LIKE 'create%'
+  }]
+  foreach idx $L { db eval "DROP INDEX $idx" }
+}
 
 do_execsql_test 1.0 {
   CREATE TABLE t1(a, b, c);
@@ -60,8 +68,9 @@ do_execsql_test 2.0 {
 
 foreach {tn idx} {
   1 { }
-  2 {  CREATE INDEX z1idx ON z1(x, y) }
-  3 {  CREATE UNIQUE INDEX z1idx ON z1(x, y) }
+  2 { CREATE INDEX z1idx ON z1(x, y) }
+  3 { CREATE UNIQUE INDEX z1idx ON z1(x, y) }
+  4 { CREATE INDEX z1idx ON kk(a, b) }
 } {
   execsql "DROP INDEX IF EXISTS z1idx"
   execsql $idx
@@ -87,11 +96,119 @@ foreach {tn idx} {
   } {d e f}
 }
 
-explain_i {
-  SELECT * FROM z1 WHERE (x, y) IN (SELECT a, b FROM kk)
-} 
+#-------------------------------------------------------------------------
+#
+
+do_execsql_test 3.0 {
+  CREATE TABLE c1(a, b, c, d);
+  INSERT INTO c1(rowid, a, b) VALUES(1,   NULL, 1);
+  INSERT INTO c1(rowid, a, b) VALUES(2,   2, NULL);
+  INSERT INTO c1(rowid, a, b) VALUES(3,   2, 2);
+  INSERT INTO c1(rowid, a, b) VALUES(4,   3, 3);
+
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(101, 'a', 'b', 1, 1);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(102, 'a', 'b', 1, 2);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(103, 'a', 'b', 1, 3);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(104, 'a', 'b', 2, 1);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(105, 'a', 'b', 2, 2);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(106, 'a', 'b', 2, 3);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(107, 'a', 'b', 3, 1);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(108, 'a', 'b', 3, 2);
+  INSERT INTO c1(rowid, a, b, c, d) VALUES(109, 'a', 'b', 3, 3);
+}
 
-finish_test
 
+foreach {tn idx} {
+  1 { }
+  2 { CREATE INDEX c1ab ON c1(a, b); }
+  3 { CREATE INDEX c1ba ON c1(b, a); }
+
+  4 { CREATE INDEX c1cd ON c1(c, d); }
+  5 { CREATE INDEX c1dc ON c1(d, c); }
+} {
+  drop_all_indexes
+
+  foreach {tn2 sql res} {
+    1 "SELECT (1, 2) IN (SELECT a, b FROM c1)" {0}
+    2 "SELECT (1, 1) IN (SELECT a, b FROM c1)" {{}}
+    3 "SELECT (2, 1) IN (SELECT a, b FROM c1)" {{}}
+    4 "SELECT (2, 2) IN (SELECT a, b FROM c1)" {1}
+    5 "SELECT c, d FROM c1 WHERE (c, d) IN (SELECT d, c FROM c1)"
+      { 1 1 1 2 1 3   2 1 2 2 2 3   3 1 3 2 3 3 }
+
+    6 "SELECT c, d FROM c1 WHERE (c,d) IN (SELECT d, c FROM c1) ORDER BY c DESC"
+      { 3 1 3 2 3 3   2 1 2 2 2 3   1 1 1 2 1 3 }
+
+    7 {
+        SELECT c, d FROM c1 WHERE (c,d) IN (SELECT d, c FROM c1) 
+        ORDER BY c DESC, d ASC
+      } { 3 1 3 2 3 3   2 1 2 2 2 3   1 1 1 2 1 3 }
+
+    8 {
+        SELECT c, d FROM c1 WHERE (c,d) IN (SELECT d, c FROM c1) 
+        ORDER BY c ASC, d DESC
+      } { 1 3 1 2 1 1   2 3 2 2 2 1   3 3 3 2 3 1 }
+
+    9 {
+        SELECT c, d FROM c1 WHERE (c,d) IN (SELECT d, c FROM c1) 
+        ORDER BY c ASC, d ASC
+      } { 1 1 1 2 1 3   2 1 2 2 2 3   3 1 3 2 3 3 }
+    10 {
+        SELECT c, d FROM c1 WHERE (c,d) IN (SELECT d, c FROM c1) 
+        ORDER BY c DESC, d DESC
+      } { 3 3 3 2 3 1   2 3 2 2 2 1   1 3 1 2 1 1 }
+
+  } {
+    do_execsql_test 3.$tn.$tn2 $sql $res
+  }
+}
+
+#-------------------------------------------------------------------------
+
+do_execsql_test 4.0 {
+  CREATE TABLE hh(a, b, c);
+
+  INSERT INTO hh VALUES('a', 'a', 1);
+  INSERT INTO hh VALUES('a', 'b', 2);
+  INSERT INTO hh VALUES('b', 'a', 3);
+  INSERT INTO hh VALUES('b', 'b', 4);
+
+  CREATE TABLE k1(x, y);
+  INSERT INTO k1 VALUES('a', 'a');
+  INSERT INTO k1 VALUES('b', 'b');
+  INSERT INTO k1 VALUES('a', 'b');
+  INSERT INTO k1 VALUES('b', 'a');
+}
+
+foreach {tn idx} {
+  1 { }
+  2 { CREATE INDEX h1 ON hh(a, b); }
+  3 { CREATE UNIQUE INDEX k1idx ON k1(x, y) }
+  4 { CREATE UNIQUE INDEX k1idx ON k1(x, y DESC) }
+  5 { 
+    CREATE INDEX h1 ON hh(a, b);
+    CREATE UNIQUE INDEX k1idx ON k1(x, y); 
+  }
+  6 { 
+    CREATE INDEX h1 ON hh(a, b);
+    CREATE UNIQUE INDEX k1idx ON k1(x, y DESC); 
+  }
+} {
+  drop_all_indexes
+  execsql $idx
+  foreach {tn2 orderby res} {
+    1 "a ASC, b ASC"  {1 2 3 4}
+    2 "a ASC, b DESC" {2 1 4 3}
+    3 "a DESC, b ASC" {3 4 1 2}
+    4 "a DESC, b DESC" {4 3 2 1}
+  } {
+    do_execsql_test 4.$tn.$tn2 "
+      SELECT c FROM hh WHERE (a, b) in (SELECT x, y FROM k1) ORDER BY $orderby
+    " $res
+  }
+}
+
+
+finish_test