SQLite

    pLoop->cId = '0';
#endif
    return 1;
  }
  return 0;
}

#ifdef SQLITE_SCHEMA_LINT
static char *whereAppendPrintf(sqlite3 *db, const char *zFmt, ...){
  va_list ap;
  char *zRes = 0;
  va_start(ap, zFmt);
  zRes = sqlite3_vmprintf(zFmt, ap);
  if( zRes==0 ){
    db->mallocFailed = 1;
  }else if( db->mallocFailed ){
    sqlite3_free(zRes);
    zRes = 0;
  }
  va_end(ap);
  return zRes;
}

/*
** Append a representation of term pTerm to the string in zIn and return
** the result. Or, if an OOM occurs, free zIn and return a NULL pointer.
*/
static char *whereAppendSingleTerm(
  Parse *pParse,
  Table *pTab,
  int bOr,
  char *zIn,
  WhereTerm *pTerm
){
  char *zBuf;
  sqlite3 *db = pParse->db;
  Expr *pX = pTerm->pExpr;
  CollSeq *pColl;
  const char *zOp = 0;

  if( pTerm->eOperator & (WO_IS|WO_EQ|WO_IN) ){
    zOp = "eq";
  }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GE|WO_GT) ){
    zOp = "range";
  }
  pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);

  if( zOp ){
    const char *zFmt = bOr ? "%z{{%s %s %s %lld}}" : "%z{%s %s %s %lld}";
    zBuf = whereAppendPrintf(db, zFmt, zIn, 
        zOp, pTab->aCol[pTerm->u.leftColumn].zName, 
        (pColl ? pColl->zName : "BINARY"),
        pTerm->prereqRight
    );
  }else{
    zBuf = zIn;
  }

  return zBuf;
}

static char *whereTraceWC(
  Parse *pParse, 
  struct SrcList_item *pItem,
  char *zIn,
  WhereClause *pWC
){
  sqlite3 *db = pParse->db;
  Table *pTab = pItem->pTab;
  char *zBuf = zIn;
  int iCol;
  int ii;
  int bFirst = 1;

  /* List of WO_SINGLE constraints */
  for(iCol=0; iCol<pTab->nCol; iCol++){
    int opMask = WO_SINGLE; 
    WhereScan scan;
    WhereTerm *pTerm;
    for(pTerm=whereScanInit(&scan, pWC, pItem->iCursor, iCol, opMask, 0);
        pTerm;
        pTerm=whereScanNext(&scan)
    ){
      assert( iCol==pTerm->u.leftColumn );
      if( bFirst==0 ) zBuf = whereAppendPrintf(db, "%z ", zBuf);
      zBuf = whereAppendSingleTerm(pParse, pTab, pWC->op==TK_OR, zBuf, pTerm);
      bFirst = 0;
    }
  }

  /* Add composite - (WO_OR|WO_AND) - constraints */
  for(ii=0; ii<pWC->nTerm; ii++){
    WhereTerm *pTerm = &pWC->a[ii];
    if( pTerm->eOperator & (WO_OR|WO_AND) ){
      const char *zFmt = ((pTerm->eOperator&WO_OR) ? "%z%s{or " : "%z%s{");
      zBuf = whereAppendPrintf(db, zFmt, zBuf, bFirst ? "" : " ");
      zBuf = whereTraceWC(pParse, pItem, zBuf, &pTerm->u.pOrInfo->wc);
      zBuf = whereAppendPrintf(db, "%z}", zBuf);
      bFirst = 0;
    }
  }

  return zBuf;
}

static void whereTraceBuilder(
  Parse *pParse,
  WhereLoopBuilder *p
){
  sqlite3 *db = pParse->db;
  if( db->xTrace ){
    WhereInfo *pWInfo = p->pWInfo;
    int nTablist = pWInfo->pTabList->nSrc;
    int ii;

    /* Loop through each element of the FROM clause. Ignore any sub-selects
    ** or views. Invoke the xTrace() callback once for each real table. */
    for(ii=0; ii<nTablist; ii++){
      char *zBuf = 0;
      int iCol;
      int nCol;
      Table *pTab;

      struct SrcList_item *pItem = &pWInfo->pTabList->a[ii];
      if( pItem->pSelect ) continue;
      pTab = pItem->pTab;
      nCol = pTab->nCol;

      /* Append the table name to the buffer. */
      zBuf = whereAppendPrintf(db, "%s", pTab->zName);

      /* Append the list of columns required to create a covering index */
      zBuf = whereAppendPrintf(db, "%z {cols", zBuf);
      if( 0==(pItem->colUsed & ((u64)1 << (sizeof(Bitmask)*8-1))) ){
        for(iCol=0; iCol<nCol; iCol++){
          if( iCol==(sizeof(Bitmask)*8-1) ) break;
          if( pItem->colUsed & ((u64)1 << iCol) ){
            zBuf = whereAppendPrintf(db, "%z %s", zBuf, pTab->aCol[iCol].zName);
          }
        }
      }
      zBuf = whereAppendPrintf(db, "%z} ", zBuf);

      /* Append the contents of WHERE clause */
      zBuf = whereTraceWC(pParse, pItem, zBuf, p->pWC);

      /* Pass the buffer to the xTrace() callback, then free it */
      db->xTrace(db->pTraceArg, zBuf);
      sqlite3DbFree(db, zBuf);
    }
  }
}
#else
# define whereTraceBuilder(x,y)
#endif

/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
**

  if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */
    int i;
    for(i=0; i<sWLB.pWC->nTerm; i++){
      whereTermPrint(&sWLB.pWC->a[i], i);
    }
  }
#endif

  /* Schema-lint xTrace callback */
  whereTraceBuilder(pParse, &sWLB);

  if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
    rc = whereLoopAddAll(&sWLB);
    if( rc ) goto whereBeginError;
  
#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace ){    /* Display all of the WhereLoop objects */

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

proc xTrace {zMsg} {
  lappend ::trace_out $zMsg
}
db trace xTrace

proc do_trace_test {tn sql res} {
  uplevel [list do_test $tn [subst -nocommands {
    set ::trace_out [list]
    set stmt [sqlite3_prepare db "$sql" -1 x]
    sqlite3_finalize [set stmt]
    set ::trace_out
  }] [list {*}$res]]
}


do_execsql_test 1.0 {
  CREATE TABLE t1(a, b, c);
  CREATE TABLE t2(x, y, z);
}

do_trace_test 1.1 {
  SELECT b, c, y, z FROM t1, t2 WHERE c=? AND z=?
} {
  {t1 {cols b c} {eq c BINARY 0}}
  {t2 {cols y z} {eq z BINARY 0}}
}

do_trace_test 1.2 {
  SELECT a FROM t1 WHERE b>10
} {
  {t1 {cols a b} {range b BINARY 0}}
}

do_trace_test 1.3 {
  SELECT b FROM t1 WHERE b IN (10, 20, 30)
} {
  {t1 {cols b} {eq b BINARY 0}}
}

do_trace_test 1.4 {
  SELECT * FROM t1, t2 WHERE x=a
} {
  {t1 {cols a b c} {eq a BINARY 2}} 
  {t2 {cols x y z} {eq x BINARY 1}}
}

do_trace_test 1.5 {
  SELECT * FROM t1 WHERE a IN (1, 2, 3)
} {
  {t1 {cols a b c} {eq a BINARY 0}}
}

#-----------------------------------------------------------------------
# Cases involving OR clauses in the WHERE clause.
#
do_trace_test 2.1 {
  SELECT * FROM t1 WHERE a=? OR b=?
} {
  {t1 {cols a b c} {or {{eq a BINARY 0}} {{eq b BINARY 0}}}}
}

do_trace_test 2.2 {
  SELECT * FROM t1 WHERE a=? OR (b=? AND c=?)
} {
  {t1 {cols a b c} {or {{eq a BINARY 0}} {{eq b BINARY 0} {eq c BINARY 0}}}}
}

do_trace_test 2.3 {
  SELECT * FROM t1 WHERE (a=? AND b=?) OR c=?
} {
  {t1 {cols a b c} {or {{eq c BINARY 0}} {{eq a BINARY 0} {eq b BINARY 0}}}}
}

finish_test

set ::G(lSelect)  [list]           ;# List of SELECT statements to analyze
set ::G(database) ""               ;# Name of database or SQL schema file
set ::G(trace)    [list]           ;# List of data from xTrace()
set ::G(verbose)  0                ;# True if -verbose option was passed 

proc usage {} {
  puts stderr "Usage: $::argv0 ?SWITCHES? DATABASE/SCHEMA"
  puts stderr "  Switches are:"
  puts stderr "  -select SQL     (recommend indexes for SQL statement)"
  puts stderr "  -verbose        (increase verbosity of output)"
  puts stderr ""
  exit
}

proc process_cmdline_args {argv} {
  global G
  set nArg [llength $argv]
  set G(database) [lindex $argv end]

  for {set i 0} {$i < [llength $argv]-1} {incr i} {
    set k [lindex $argv $i]
    switch -- $k {
      -select {
        incr i
        if {$i>=[llength $argv]-1} usage
        lappend G(lSelect) [lindex $argv $i]
      }
      -verbose {
        set G(verbose) 1
      }
      default {
        usage
      }
    }
  }
}

proc open_database {} {
  global G
  sqlite3 db ""

  # Check if the "database" file is really an SQLite database. If so, copy
  # it into the temp db just opened. Otherwise, assume that it is an SQL
  # schema and execute it directly.
  set fd [open $G(database)]
  set hdr [read $fd 16]
  if {$hdr == "SQLite format 3\000"} {
    close $fd
    sqlite3 db2 $G(database)
    sqlite3_backup B db main db2 main
    B step 2000000000
    set rc [B finish]
    db2 close
    if {$rc != "SQLITE_OK"} { error "Failed to load database $G(database)" }
  } else {
    append hdr [read $fd]
    db eval $hdr
    close $fd
  }
}

proc analyze_selects {} {
  global G
  set G(trace) ""

  # Collect a line of xTrace output for each loop in the set of SELECT
  # statements.
  proc xTrace {zMsg} { lappend ::G(trace) $zMsg }
  db trace "lappend ::G(trace)"
  foreach s $G(lSelect) {
    set stmt [sqlite3_prepare_v2 db $s -1 dummy]
    set rc [sqlite3_finalize $stmt]
    if {$rc!="SQLITE_OK"} {
      error "Failed to compile SQL: [sqlite3_errmsg db]"
    }
  }

  db trace ""
  if {$G(verbose)} {
    foreach t $G(trace) { puts "trace: $t" }
  }

  # puts $G(trace)
}

# The argument is a list of the form:
#
#    key1 {value1.1 value1.2} key2 {value2.1 value 2.2...}
#
# Values lists may be of any length greater than zero. This function returns
# a list of lists created by pivoting on each values list. i.e. a list
# consisting of the elements:
#
#   {{key1 value1.1} {key2 value2.1}}
#   {{key1 value1.2} {key2 value2.1}}
#   {{key1 value1.1} {key2 value2.2}}
#   {{key1 value1.2} {key2 value2.2}}
#
proc expand_eq_list {L} {
  set ll [list {}]
  for {set i 0} {$i < [llength $L]} {incr i 2} {
    set key [lindex $L $i]
    set new [list]
    foreach piv [lindex $L $i+1] {
      foreach l $ll {
        lappend new [concat $l [list [list $key $piv]]]
      }
    }
    set ll $new
  }

  return $ll
}

proc eqset_to_index {tname eqset {range {}}} {
  global G
  set lCols [list]
  set idxname $tname
  foreach e [concat [lsort $eqset] [list $range]] {
    if {[llength $e]==0} continue
    foreach {c collate} $e {}
    lappend lCols "$c collate $collate"
    append idxname "_$c"
    if {[string compare -nocase binary $collate]!=0} {
      append idxname [string tolower $collate]
    }
  }

  set create_index "CREATE INDEX $idxname ON ${tname}("
  append create_index [join $lCols ", "]
  append create_index ");"

  set G(trial.$idxname) $create_index
}

proc expand_or_cons {L} {
  set lRet [list [list]]
  foreach elem $L {
    set type [lindex $elem 0]
    if {$type=="eq" || $type=="range"} {
      set lNew [list]
      for {set i 0} {$i < [llength $lRet]} {incr i} {
        lappend lNew [concat [lindex $lRet $i] [list $elem]]
      }
      set lRet $lNew
    } elseif {$type=="or"} {
      set lNew [list]
      foreach branch [lrange $elem 1 end] {
        foreach b [expand_or_cons $branch] {
          for {set i 0} {$i < [llength $lRet]} {incr i} {
            lappend lNew [concat [lindex $lRet $i] $b]
          }
        }
      }
      set lRet $lNew
    } 
  }
  return $lRet
}

proc find_trial_indexes {} {
  global G
  foreach t $G(trace) {
    set tname [lindex $t 0]
    catch { array unset mask }

    foreach lCons [expand_or_cons [lrange $t 2 end]] {
      set constraints [list]

      foreach a $lCons {
        set type [lindex $a 0]
        if {$type=="eq" || $type=="range"} {
          set m [lindex $a 3]
          foreach k [array names mask] { set mask([expr ($k & $m)]) 1 }
          set mask($m) 1
          lappend constraints $a
        }
      }

      foreach k [array names mask] {
        catch {array unset eq}
        foreach a $constraints {
          foreach {type col collate m} $a {
            if {($m & $k)==$m} {
              if {$type=="eq"} {
                lappend eq($col) $collate
              } else {
                set range($col.$collate) 1
              }
            }
          }
        }

        #puts "mask=$k eq=[array get eq] range=[array get range]"
        
        set ranges [array names range]
        foreach eqset [expand_eq_list [array get eq]] {
          if {[llength $ranges]==0} {
            eqset_to_index $tname $eqset
          } else {
            foreach r $ranges {
              set bSeen 0
              foreach {c collate} [split $r .] {}
              foreach e $eqset {
                if {[lindex $e 0] == $c} {
                  set bSeen 1
                  break
                }
              }
              if {$bSeen} {
                eqset_to_index $tname $eqset
              } else {
                eqset_to_index $tname $eqset [list $c $collate]
              }
            }
          }
        }
      }
    }
  }

  if {$G(verbose)} {
    foreach k [array names G trial.*] { puts "index: $G($k)" }
  }
}

proc run_trials {} {
  global G

  foreach k [array names G trial.*] {
    set idxname [lindex [split $k .] 1]
    db eval $G($k)
    set pgno [db one {SELECT rootpage FROM sqlite_master WHERE name = $idxname}]
    set IDX($pgno) $idxname
  }
  db eval ANALYZE

  catch { array unset used }
  foreach s $G(lSelect) {
    db eval "EXPLAIN $s" x {
      if {($x(opcode)=="OpenRead" || $x(opcode)=="ReopenIdx")} {
        if {[info exists IDX($x(p2))]} { set used($IDX($x(p2))) 1 }
      }
    }
    foreach idx [array names used] {
      puts $G(trial.$idx)
    }
  }
}

process_cmdline_args $argv
open_database
analyze_selects
find_trial_indexes
run_trials