SQLite

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.198 2006/01/14 08:02:28 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)

      pTerm = &pWC->a[idxTerm];
      pWC->a[idxNew].iParent = idxTerm;
    }
    pTerm->nChild = 2;
  }
#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */

#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
  /* Attempt to convert OR-connected terms into an IN operator so that
  ** they can make use of indices.  Example:
  **
  **      x = expr1  OR  expr2 = x  OR  x = expr3
  **
  ** is converted into
  **
  **      x IN (expr1,expr2,expr3)
  **
  ** This optimization must be omitted if OMIT_SUBQUERY is defined because
  ** the compiler for the the IN operator is part of sub-queries.
  */
  else if( pExpr->op==TK_OR ){
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;

# 2004 November 10
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is testing the ALTER TABLE statement.
#
# $Id: alter.test,v 1.14 2006/01/14 08:02:28 danielk1977 Exp $
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# If SQLITE_OMIT_ALTERTABLE is defined, omit this file.
ifcapable !altertable {

do_test alter-5.1 {
  string length $::tbl_name
} {7}
do_test alter-5.2 {
  execsql "
    CREATE TABLE ${tbl_name}(a, b, c);
  "
  set ::oid [execsql {SELECT max(oid) FROM sqlite_master}]
  execsql {
    SELECT sql FROM sqlite_master WHERE oid = $::oid;

  }
} "{CREATE TABLE ${::tbl_name}(a, b, c)}"
set ::tbl_name2 "abcXdef"
do_test alter-5.2 {
  execsql "
    ALTER TABLE $::tbl_name RENAME TO $::tbl_name2 
  "
  execsql {
    SELECT sql FROM sqlite_master WHERE oid = $::oid;

  }
} "{CREATE TABLE '${::tbl_name2}'(a, b, c)}"
do_test alter-5.3 {
  execsql "
    ALTER TABLE $::tbl_name2 RENAME TO $::tbl_name
  "
  execsql {
    SELECT sql FROM sqlite_master WHERE oid = $::oid;

  }
} "{CREATE TABLE '${::tbl_name}'(a, b, c)}"
set ::col_name ghi\1234\jkl
do_test alter-5.4 {
  execsql "
    ALTER TABLE $::tbl_name ADD COLUMN $::col_name VARCHAR
  "
  execsql {
    SELECT sql FROM sqlite_master WHERE oid = $::oid;

  }
} "{CREATE TABLE '${::tbl_name}'(a, b, c, $::col_name VARCHAR)}"
set ::col_name2 B\3421\A
do_test alter-5.5 {
  db close
  sqlite3 db test.db
  execsql "
    ALTER TABLE $::tbl_name ADD COLUMN $::col_name2
  "
  execsql {
    SELECT sql FROM sqlite_master WHERE oid = $::oid;

  }
} "{CREATE TABLE '${::tbl_name}'(a, b, c, $::col_name VARCHAR, $::col_name2)}"
do_test alter-5.6 {
  execsql "
    INSERT INTO ${::tbl_name} VALUES(1, 2, 3, 4, 5);
    SELECT $::col_name, $::col_name2 FROM $::tbl_name;
  "
} {4 5}

finish_test

# 2005 November 2
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing CHECK constraints
#
# $Id: check.test,v 1.7 2006/01/14 08:02:28 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Only run these tests if the build includes support for CHECK constraints
ifcapable !check {
  finish_test

} {1 {constraint failed}}
do_test check-2.6 {
  catchsql {
    INSERT INTO t2 VALUES(NULL, NULL, 3.14159);
  }
} {1 {constraint failed}}

ifcapable subquery {
  do_test check-3.1 {
    catchsql {
      CREATE TABLE t3(
        x, y, z,
        CHECK( x<(SELECT min(x) FROM t1) )
      );
    }
  } {1 {subqueries prohibited in CHECK constraints}}
}

do_test check-3.2 {
  execsql {
    SELECT name FROM sqlite_master ORDER BY name
  }
} {t1 t2}
do_test check-3.3 {
  catchsql {

# 2006 January 02
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is descending indices.
#
# $Id: descidx3.test,v 1.2 2006/01/14 08:02:28 danielk1977 Exp $
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# This procedure sets the value of the file-format in file 'test.db'
# to $newval. Also, the schema cookie is incremented.

} {5 2 4 3 8 6 7 9}
do_test descidx3-3.5 {
  execsql {
    SELECT i FROM t1 WHERE b>-9999 AND b<x'ffffffff'
  }
} {9 7 6 8 3 4 2 5}

ifcapable subquery {
  # If the subquery capability is not compiled in to the binary, then
  # the IN(...) operator is not available. Hence these tests cannot be 
  # run.
  do_test descidx3-4.1 {
    execsql {
      UPDATE t1 SET a=2 WHERE i<6;
      SELECT i FROM t1 WHERE a IN (1,2) AND b>0 AND b<'zzz';
    }
  } {8 6 2 4 3}
  do_test descidx3-4.2 {
    execsql {
      UPDATE t1 SET a=1;
      SELECT i FROM t1 WHERE a IN (1,2) AND b>0 AND b<'zzz';
    }
  } {2 4 3 8 6}
  do_test descidx3-4.3 {
    execsql {
      UPDATE t1 SET b=2;
      SELECT i FROM t1 WHERE a IN (1,2) AND b>0 AND b<'zzz';
    }
  } {9 7 6 8 3 4 2 5 1}
}

finish_test

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests for miscellanous features that were
# left out of other test files.
#
# $Id: misc2.test,v 1.23 2006/01/14 08:02:28 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable {trigger} {
# Test for ticket #360
#

# Ticket #1229.  Sometimes when a "NEW.X" appears in a SELECT without
# a FROM clause deep within a trigger, the code generator is unable to
# trace the NEW.X back to an original table and thus figure out its
# declared datatype.
#
# The SQL code below was causing a segfault.
#
ifcapable subquery {
  do_test misc2-10.1 {
    execsql {
      CREATE TABLE t1229(x);
      CREATE TRIGGER r1229 BEFORE INSERT ON t1229 BEGIN
        INSERT INTO t1229 SELECT y FROM (SELECT new.x y);
      END;
      INSERT INTO t1229 VALUES(1);
    }
  } {}
}

finish_test

#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests for miscellanous features that were
# left out of other test files.
#
# $Id: misc5.test,v 1.9 2006/01/14 08:02:28 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build records using the MakeRecord opcode such that the size of the 
# header is at the transition point in the size of a varint.
#

4611686018427387903\
4611686018427387904\
4611686018427387905"

# Ticket #1210.  Do proper reference counting of Table structures
# so that deeply nested SELECT statements can be flattened correctly.
#
ifcapable subquery {
  do_test misc5-3.1 {
    execsql {
      CREATE TABLE songs(songid, artist, timesplayed);
      INSERT INTO songs VALUES(1,'one',1);
      INSERT INTO songs VALUES(2,'one',2);
      INSERT INTO songs VALUES(3,'two',3);
      INSERT INTO songs VALUES(4,'three',5);
      INSERT INTO songs VALUES(5,'one',7);
      INSERT INTO songs VALUES(6,'two',11);
      SELECT DISTINCT artist 
      FROM (    
       SELECT DISTINCT artist    
       FROM songs      
       WHERE songid IN (    
        SELECT songid    
        FROM songs    
        WHERE LOWER(artist) = (    
          SELECT DISTINCT LOWER(artist)    
          FROM (      
            SELECT DISTINCT artist,sum(timesplayed) AS total      
            FROM songs      
            GROUP BY LOWER(artist)      
            ORDER BY total DESC      
            LIMIT 10    
          )    
          WHERE artist <> '' 
        )  
       )       
      )  
      ORDER BY LOWER(artist) ASC;
    }
  } {two}
}

# Ticket #1370.  Do not overwrite small files (less than 1024 bytes)
# when trying to open them as a database.
#
do_test misc5-4.1 {
  db close
  file delete -force test.db

# 2001 September 15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: select1.test,v 1.47 2006/01/14 08:02:28 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Try to select on a non-existant table.
#
do_test select1-1.1 {

    }
  } {x 1 x 3}
} ;# ifcapable compound


# Check for a VDBE stack growth problem that existed at one point.
#
ifcapable subquery {
  do_test select1-13.1 {
    execsql {
      BEGIN;
      create TABLE abc(a, b, c, PRIMARY KEY(a, b));
      INSERT INTO abc VALUES(1, 1, 1);
    }
    for {set i 0} {$i<10} {incr i} {
      execsql {
        INSERT INTO abc SELECT a+(select max(a) FROM abc), 
            b+(select max(a) FROM abc), c+(select max(a) FROM abc) FROM abc;
      }
    }
    execsql {COMMIT}
  
    # This used to seg-fault when the problem existed.
    execsql {
      SELECT count(
        (SELECT a FROM abc WHERE a = NULL AND b >= upper.c) 
      ) FROM abc AS upper;
    }
  } {0}
}

finish_test

# 2005 December 30
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# $Id: shared.test,v 1.12 2006/01/14 08:02:29 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl
db close

ifcapable !shared_cache {
  finish_test

  "
  execsql {SELECT * FROM sqlite_master} db2
  execsql {PRAGMA read_uncommitted = 1} db2

  set ret [list]
  db2 eval {SELECT i FROM seq} {
    if {$i < 4} {
      set max [execsql {SELECT max(i) FROM seq}]
      db eval {
        INSERT INTO seq SELECT i + $max, x FROM seq;
      }
    }
    lappend ret $i
  }
  set ret
} {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16}
do_test shared-3.1.2 {

#
# NOTE:  Yes, in spite of the name of this file (tkt1443.test) this
# test is for ticket #1433 not #1443.  I mistyped the name when I was
# creating the file and I had already checked in the file by the wrong
# name be the time I noticed the error.  With CVS it is a really hassle
# to change filenames, so I'll just leave it as is.  No harm done.
#
# $Id: tkt1443.test,v 1.3 2006/01/14 08:02:29 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

ifcapable !subquery {
  finish_test
  return
}

# Construct the sample database.
#
do_test tkt1443-1.0 {
  sqlite3 db :memory:
  execsql {
    CREATE TABLE Items(

#
# This file implements tests to verify that ticket #1449 has been
# fixed.  
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Somewhere in tkt1449-1.1 is a VIEW definition that uses a subquery.
# So we cannot run this file if subqueries are not available.
ifcapable !subquery {
  finish_test
  return
}

# The following schema generated problems in ticket #1449.  We've retained
# the original schema here because it is some unbelievably complex, it seemed
# like a good test case for SQLite.
#
do_test tkt1449-1.1 {
  execsql {

  }
} {}
do_test tkt1473-1.9 {
  execsql {
    SELECT 1 FROM t1 WHERE a=0 UNION SELECT 2 FROM t1 WHERE b=0
  }
} {}

# Everything from this point on depends on sub-queries. So skip it
# if sub-queries are not available.
ifcapable !subquery {
  finish_test
  return
}

do_test tkt1473-2.2 {
  execsql {
    SELECT (SELECT 1 FROM t1 WHERE a=1 UNION ALL SELECT 2 FROM t1 WHERE b=0)
  }
} {1}
do_test tkt1473-2.3 {

  }
} {1 {} {} {} {} 2 1 3 3 1}
do_test tkt1537-1.3 {
  execsql {
    SELECT * FROM t2 LEFT JOIN t1 ON a1=b OR a2=b;
  }
} {3 1 2 1 3 4 {} {} {} {}}
ifcapable subquery {
  do_test tkt1537-1.4 {
    execsql {
      SELECT * FROM t1 LEFT JOIN t2 ON b IN (a1,a2);
    }
  } {1 {} {} {} {} 2 1 3 3 1}
  do_test tkt1537-1.5 {
    execsql {
      SELECT * FROM t2 LEFT JOIN t1 ON b IN (a2,a1);
    }
  } {3 1 2 1 3 4 {} {} {} {}}
}
do_test tkt1537-1.6 {
  execsql {
    CREATE INDEX t1a1 ON t1(a1);
    CREATE INDEX t1a2 ON t1(a2);
    CREATE INDEX t2b ON t2(b);
    SELECT * FROM t1 LEFT JOIN t2 ON a1=b OR a2=b;
  }
} {1 {} {} {} {} 2 1 3 3 1}
do_test tkt1537-1.7 {
  execsql {
    SELECT * FROM t2 LEFT JOIN t1 ON a1=b OR a2=b;
  }
} {3 1 2 1 3 4 {} {} {} {}}

ifcapable subquery {
  do_test tkt1537-1.8 {
    execsql {
      SELECT * FROM t1 LEFT JOIN t2 ON b IN (a1,a2);
    }
  } {1 {} {} {} {} 2 1 3 3 1}
  do_test tkt1537-1.9 {
    execsql {
      SELECT * FROM t2 LEFT JOIN t1 ON b IN (a2,a1);
    }
  } {3 1 2 1 3 4 {} {} {} {}}
}

execsql {
  DROP INDEX t1a1;
  DROP INDEX t1a2;
  DROP INDEX t2b;
}

# 2002 February 26
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing VIEW statements.
#
# $Id: view.test,v 1.28 2006/01/14 08:02:29 danielk1977 Exp $
set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Omit this entire file if the library is not configured with views enabled.
ifcapable !view {
  finish_test
  return

    CREATE TABLE t4(a COLLATE NOCASE);
    INSERT INTO t4 VALUES('This');
    INSERT INTO t4 VALUES('this');
    INSERT INTO t4 VALUES('THIS');
    SELECT * FROM t4 WHERE a = 'THIS';
  }
} {This this THIS}
ifcapable subquery {
  do_test view-11.2 {
    execsql {
      SELECT * FROM (SELECT * FROM t4) WHERE a = 'THIS';
    }
  } {This this THIS}
}
do_test view-11.3 {
  execsql {
    CREATE VIEW v11 AS SELECT * FROM t4;
    SELECT * FROM v11 WHERE a = 'THIS';
  }
} {This this THIS}

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.6 2006/01/14 08:02:29 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build some test data
#
do_test where2-1.0 {

  queryplan {
    SELECT * FROM t1 ORDER BY rowid DESC LIMIT 2
  }
} {100 6 10201 10207 99 6 10000 10006 nosort t1 *}

# The IN operator can be used by indices at multiple layers
#
ifcapable subquery {
  do_test where2-4.1 {
    queryplan {
      SELECT * FROM t1 WHERE z IN (10207,10006) AND y IN (10000,10201)
                       AND x>0 AND x<10
      ORDER BY w
    }
  } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx}
  do_test where2-4.2 {
    queryplan {
      SELECT * FROM t1 WHERE z IN (10207,10006) AND y=10000
                       AND x>0 AND x<10
      ORDER BY w
    }
  } {99 6 10000 10006 sort t1 i1zyx}
  do_test where2-4.3 {
    queryplan {
      SELECT * FROM t1 WHERE z=10006 AND y IN (10000,10201)
                       AND x>0 AND x<10
      ORDER BY w
    }
  } {99 6 10000 10006 sort t1 i1zyx}
  do_test where2-4.4 {
    queryplan {
      SELECT * FROM t1 WHERE z IN (SELECT 10207 UNION SELECT 10006)
                       AND y IN (10000,10201)
                       AND x>0 AND x<10
      ORDER BY w
    }
  } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx}
  do_test where2-4.5 {
    queryplan {
      SELECT * FROM t1 WHERE z IN (SELECT 10207 UNION SELECT 10006)
                       AND y IN (SELECT 10000 UNION SELECT 10201)
                       AND x>0 AND x<10
      ORDER BY w
    }
  } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx}
  do_test where2-4.6 {
    queryplan {
      SELECT * FROM t1
       WHERE x IN (1,2,3,4,5,6,7,8)
         AND y IN (10000,10001,10002,10003,10004,10005)
       ORDER BY 2
    }
  } {99 6 10000 10006 sort t1 i1xy}

  # Duplicate entires on the RHS of an IN operator do not cause duplicate
  # output rows.
  #
  do_test where2-4.6 {
    queryplan {
      SELECT * FROM t1 WHERE z IN (10207,10006,10006,10207)
      ORDER BY w
    }
  } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx}
  do_test where2-4.7 {
    queryplan {
      SELECT * FROM t1 WHERE z IN (
         SELECT 10207 UNION ALL SELECT 10006
         UNION ALL SELECT 10006 UNION ALL SELECT 10207)
      ORDER BY w
    }
  } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx}

} ;# ifcapable subquery

# The use of an IN operator disables the index as a sorter.
#
do_test where2-5.1 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 ORDER BY w
  }
} {99 6 10000 10006 nosort t1 i1w}

ifcapable subquery {
  do_test where2-5.2 {
    queryplan {
      SELECT * FROM t1 WHERE w IN (99) ORDER BY w
    }
  } {99 6 10000 10006 sort t1 i1w}
}

# Verify that OR clauses get translated into IN operators.
#
set ::idx {}
ifcapable subquery {set ::idx i1w}
do_test where2-6.1 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 ORDER BY +w
  }
} [list 99 6 10000 10006 100 6 10201 10207 sort t1 $::idx]
do_test where2-6.2 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 OR 6=w ORDER BY +w
  }
} [list 6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 $::idx]

do_test where2-6.3 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 OR 6=+w ORDER BY +w
  }
} {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}}
do_test where2-6.4 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR +w=100 OR 6=w ORDER BY +w
  }
} {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}}

set ::idx {}
ifcapable subquery {set ::idx i1zyx}
do_test where2-6.5 {
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} [list 1 0 4 4 2 1 9 10 sort a i1w b $::idx]
do_test where2-6.6 {
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} [list 1 0 4 4 2 1 9 10 sort a i1w b $::idx]

# Unique queries (queries that are guaranteed to return only a single
# row of result) do not call the sorter.  But all tables must give
# a unique result.  If any one table in the join does not give a unique
# result then sorting is necessary.
#
do_test where2-7.1 {

  { "DROP",             "TK_DROP",         ALWAYS                 },
  { "END",              "TK_END",          ALWAYS                 },
  { "EACH",             "TK_EACH",         TRIGGER                },
  { "ELSE",             "TK_ELSE",         ALWAYS                 },
  { "ESCAPE",           "TK_ESCAPE",       ALWAYS                 },
  { "EXCEPT",           "TK_EXCEPT",       COMPOUND               },
  { "EXCLUSIVE",        "TK_EXCLUSIVE",    ALWAYS                 },
  { "EXISTS",           "TK_EXISTS",       ALWAYS                 },
  { "EXPLAIN",          "TK_EXPLAIN",      EXPLAIN                },
  { "FAIL",             "TK_FAIL",         CONFLICT|TRIGGER       },
  { "FOR",              "TK_FOR",          TRIGGER                },
  { "FOREIGN",          "TK_FOREIGN",      FKEY                   },
  { "FROM",             "TK_FROM",         ALWAYS                 },
  { "FULL",             "TK_JOIN_KW",      ALWAYS                 },
  { "GLOB",             "TK_LIKE_KW",      ALWAYS                 },