# include "sqlite3ext.h" 
extern const sqlite3_api_routines *sqlite3_api;
#endif

#include "sqlite3.h"
#include "fts3_tokenizer.h"
#include "fts3_hash.h"













/*
** This constant controls how often segments are merged. Once there are
** FTS3_MERGE_COUNT segments of level N, they are merged into a single
** segment of level N+1.
*/
#define FTS3_MERGE_COUNT 16

# include "sqlite3ext.h" 
extern const sqlite3_api_routines *sqlite3_api;
#endif

#include "sqlite3.h"
#include "fts3_tokenizer.h"
#include "fts3_hash.h"

/*
** This constant determines the maximum depth of an FTS expression tree
** that the library will create and use. FTS uses recursion to perform 
** various operations on the query tree, so the disadvantage of a large
** limit is that it may allow very large queries to use large amounts
** of stack space (perhaps causing a stack overflow).
*/
#ifndef SQLITE_FTS3_MAX_EXPR_DEPTH
# define SQLITE_FTS3_MAX_EXPR_DEPTH 12
#endif


/*
** This constant controls how often segments are merged. Once there are
** FTS3_MERGE_COUNT segments of level N, they are merged into a single
** segment of level N+1.
*/
#define FTS3_MERGE_COUNT 16

  int bFts4,                          /* True to allow FTS4-only syntax */
  int nCol,                           /* Number of entries in azCol[] */
  int iDefaultCol,                    /* Default column to query */
  const char *z, int n,               /* Text of MATCH query */
  Fts3Expr **ppExpr,                  /* OUT: Parsed query structure */
  char **pzErr                        /* OUT: Error message (sqlite3_malloc) */
){
  static const int MAX_EXPR_DEPTH = 12;
  int rc = fts3ExprParseUnbalanced(
      pTokenizer, iLangid, azCol, bFts4, nCol, iDefaultCol, z, n, ppExpr
  );
  
  /* Rebalance the expression. And check that its depth does not exceed
  ** MAX_EXPR_DEPTH.  */
  if( rc==SQLITE_OK && *ppExpr ){
    rc = fts3ExprBalance(ppExpr, MAX_EXPR_DEPTH);
    if( rc==SQLITE_OK ){
      rc = fts3ExprCheckDepth(*ppExpr, MAX_EXPR_DEPTH);
    }
  }

  if( rc!=SQLITE_OK ){
    sqlite3Fts3ExprFree(*ppExpr);
    *ppExpr = 0;
    if( rc==SQLITE_TOOBIG ){
      *pzErr = sqlite3_mprintf(
          "FTS expression tree is too large (maximum depth %d)", MAX_EXPR_DEPTH

      );
      rc = SQLITE_ERROR;
    }else if( rc==SQLITE_ERROR ){
      *pzErr = sqlite3_mprintf("malformed MATCH expression: [%s]", z);
    }
  }

  int bFts4,                          /* True to allow FTS4-only syntax */
  int nCol,                           /* Number of entries in azCol[] */
  int iDefaultCol,                    /* Default column to query */
  const char *z, int n,               /* Text of MATCH query */
  Fts3Expr **ppExpr,                  /* OUT: Parsed query structure */
  char **pzErr                        /* OUT: Error message (sqlite3_malloc) */
){

  int rc = fts3ExprParseUnbalanced(
      pTokenizer, iLangid, azCol, bFts4, nCol, iDefaultCol, z, n, ppExpr
  );
  
  /* Rebalance the expression. And check that its depth does not exceed
  ** SQLITE_FTS3_MAX_EXPR_DEPTH.  */
  if( rc==SQLITE_OK && *ppExpr ){
    rc = fts3ExprBalance(ppExpr, SQLITE_FTS3_MAX_EXPR_DEPTH);
    if( rc==SQLITE_OK ){
      rc = fts3ExprCheckDepth(*ppExpr, SQLITE_FTS3_MAX_EXPR_DEPTH);
    }
  }

  if( rc!=SQLITE_OK ){
    sqlite3Fts3ExprFree(*ppExpr);
    *ppExpr = 0;
    if( rc==SQLITE_TOOBIG ){
      *pzErr = sqlite3_mprintf(
          "FTS expression tree is too large (maximum depth %d)", 
          SQLITE_FTS3_MAX_EXPR_DEPTH
      );
      rc = SQLITE_ERROR;
    }else if( rc==SQLITE_ERROR ){
      *pzErr = sqlite3_mprintf("malformed MATCH expression: [%s]", z);
    }
  }

    0x02A00801, 0x02A01801, 0x02A02C01, 0x02A08C09, 0x02A0D804,
    0x02A1D004, 0x02A20002, 0x02A2D011, 0x02A33802, 0x02A38012,
    0x02A3E003, 0x02A4980A, 0x02A51C0D, 0x02A57C01, 0x02A60004,
    0x02A6CC1B, 0x02A77802, 0x02A8A40E, 0x02A90C01, 0x02A93002,
    0x02A97004, 0x02A9DC03, 0x02A9EC01, 0x02AAC001, 0x02AAC803,
    0x02AADC02, 0x02AAF802, 0x02AB0401, 0x02AB7802, 0x02ABAC07,
    0x02ABD402, 0x02AF8C0B, 0x03600001, 0x036DFC02, 0x036FFC02,
    0x037FFC02, 0x03E3FC01, 0x03EC7801, 0x03ECA401, 0x03EEC810,
    0x03F4F802, 0x03F7F002, 0x03F8001A, 0x03F88007, 0x03F8C023,
    0x03F95013, 0x03F9A004, 0x03FBFC01, 0x03FC040F, 0x03FC6807,
    0x03FCEC06, 0x03FD6C0B, 0x03FF8007, 0x03FFA007, 0x03FFE405,
    0x04040003, 0x0404DC09, 0x0405E411, 0x0406400C, 0x0407402E,
    0x040E7C01, 0x040F4001, 0x04215C01, 0x04247C01, 0x0424FC01,
    0x04280403, 0x04281402, 0x04283004, 0x0428E003, 0x0428FC01,
    0x04294009, 0x0429FC01, 0x042CE407, 0x04400003, 0x0440E016,
    0x04420003, 0x0442C012, 0x04440003, 0x04449C0E, 0x04450004,
    0x04460003, 0x0446CC0E, 0x04471404, 0x045AAC0D, 0x0491C004,
    0x05BD442E, 0x05BE3C04, 0x074000F6, 0x07440027, 0x0744A4B5,
    0x07480046, 0x074C0057, 0x075B0401, 0x075B6C01, 0x075BEC01,
    0x075C5401, 0x075CD401, 0x075D3C01, 0x075DBC01, 0x075E2401,
    0x075EA401, 0x075F0C01, 0x07BBC002, 0x07C0002C, 0x07C0C064,
    0x07C2800F, 0x07C2C40E, 0x07C3040F, 0x07C3440F, 0x07C4401F,
    0x07C4C03C, 0x07C5C02B, 0x07C7981D, 0x07C8402B, 0x07C90009,
    0x07C94002, 0x07CC0021, 0x07CCC006, 0x07CCDC46, 0x07CE0014,
    0x07CE8025, 0x07CF1805, 0x07CF8011, 0x07D0003F, 0x07D10001,
    0x07D108B6, 0x07D3E404, 0x07D4003E, 0x07D50004, 0x07D54018,
    0x07D7EC46, 0x07D9140B, 0x07DA0046, 0x07DC0074, 0x38000401,
    0x38008060, 0x380400F0, 0x3C000001, 0x3FFFF401, 0x40000001,
    0x43FFF401,
  };
  static const unsigned int aAscii[4] = {
    0xFFFFFFFF, 0xFC00FFFF, 0xF8000001, 0xF8000001,
  };

  if( c<128 ){
    return ( (aAscii[c >> 5] & (1 << (c & 0x001F)))==0 );

    0x02A00801, 0x02A01801, 0x02A02C01, 0x02A08C09, 0x02A0D804,
    0x02A1D004, 0x02A20002, 0x02A2D011, 0x02A33802, 0x02A38012,
    0x02A3E003, 0x02A4980A, 0x02A51C0D, 0x02A57C01, 0x02A60004,
    0x02A6CC1B, 0x02A77802, 0x02A8A40E, 0x02A90C01, 0x02A93002,
    0x02A97004, 0x02A9DC03, 0x02A9EC01, 0x02AAC001, 0x02AAC803,
    0x02AADC02, 0x02AAF802, 0x02AB0401, 0x02AB7802, 0x02ABAC07,
    0x02ABD402, 0x02AF8C0B, 0x03600001, 0x036DFC02, 0x036FFC02,
    0x037FFC01, 0x03EC7801, 0x03ECA401, 0x03EEC810, 0x03F4F802,
    0x03F7F002, 0x03F8001A, 0x03F88007, 0x03F8C023, 0x03F95013,
    0x03F9A004, 0x03FBFC01, 0x03FC040F, 0x03FC6807, 0x03FCEC06,
    0x03FD6C0B, 0x03FF8007, 0x03FFA007, 0x03FFE405, 0x04040003,
    0x0404DC09, 0x0405E411, 0x0406400C, 0x0407402E, 0x040E7C01,
    0x040F4001, 0x04215C01, 0x04247C01, 0x0424FC01, 0x04280403,
    0x04281402, 0x04283004, 0x0428E003, 0x0428FC01, 0x04294009,
    0x0429FC01, 0x042CE407, 0x04400003, 0x0440E016, 0x04420003,
    0x0442C012, 0x04440003, 0x04449C0E, 0x04450004, 0x04460003,
    0x0446CC0E, 0x04471404, 0x045AAC0D, 0x0491C004, 0x05BD442E,
    0x05BE3C04, 0x074000F6, 0x07440027, 0x0744A4B5, 0x07480046,
    0x074C0057, 0x075B0401, 0x075B6C01, 0x075BEC01, 0x075C5401,
    0x075CD401, 0x075D3C01, 0x075DBC01, 0x075E2401, 0x075EA401,
    0x075F0C01, 0x07BBC002, 0x07C0002C, 0x07C0C064, 0x07C2800F,
    0x07C2C40E, 0x07C3040F, 0x07C3440F, 0x07C4401F, 0x07C4C03C,
    0x07C5C02B, 0x07C7981D, 0x07C8402B, 0x07C90009, 0x07C94002,
    0x07CC0021, 0x07CCC006, 0x07CCDC46, 0x07CE0014, 0x07CE8025,
    0x07CF1805, 0x07CF8011, 0x07D0003F, 0x07D10001, 0x07D108B6,
    0x07D3E404, 0x07D4003E, 0x07D50004, 0x07D54018, 0x07D7EC46,
    0x07D9140B, 0x07DA0046, 0x07DC0074, 0x38000401, 0x38008060,
    0x380400F0,

  };
  static const unsigned int aAscii[4] = {
    0xFFFFFFFF, 0xFC00FFFF, 0xF8000001, 0xF8000001,
  };

  if( c<128 ){
    return ( (aAscii[c >> 5] & (1 << (c & 0x001F)))==0 );

    if {$line == ""} continue

    set fields [split $line ";"]
    if {[llength $fields] != [llength $lField]} { error "parse error: $line" }
    foreach $lField $fields {}

    set iCode [expr "0x$code"]

    set bAlnum [expr {[lsearch {L N} [string range $general_category 0 0]]>=0}]



    if { !$bAlnum } { lappend lRet $iCode }
  }

  close $fd
  set lRet
}
................................................................................
        iLo = iTest+1;
      }else{
        iHi = iTest-1;
      }
    }
    assert( aEntry[0]<key );
    assert( key>=aEntry[iRes] );
    return (c >= ((aEntry[iRes]>>10) + (aEntry[iRes]&0x3FF)));
  }
  return 1;}
  puts "\}"
}

proc print_test_isalnum {zFunc lRange} {
  foreach range $lRange {
................................................................................
*/

/*
** DO NOT EDIT THIS MACHINE GENERATED FILE.
*/
  }]
  puts ""
  puts "#if !defined(SQLITE_DISABLE_FTS3_UNICODE)"
  puts "#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)"
  puts ""
  puts "#include <assert.h>"
  puts ""
}

proc print_test_main {} {
................................................................................
if {$::generate_test_code} {
  print_test_isalnum sqlite3FtsUnicodeIsalnum $lRange
  print_fold_test sqlite3FtsUnicodeFold $mappings
  print_test_main 
}

puts "#endif /* defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4) */"
puts "#endif /* !defined(SQLITE_DISABLE_FTS3_UNICODE) */"

    if {$line == ""} continue

    set fields [split $line ";"]
    if {[llength $fields] != [llength $lField]} { error "parse error: $line" }
    foreach $lField $fields {}

    set iCode [expr "0x$code"]
    set bAlnum [expr {
         [lsearch {L N} [string range $general_category 0 0]] >= 0
      || $general_category=="Co"
    }]

    if { !$bAlnum } { lappend lRet $iCode }
  }

  close $fd
  set lRet
}
................................................................................
        iLo = iTest+1;
      }else{
        iHi = iTest-1;
      }
    }
    assert( aEntry[0]<key );
    assert( key>=aEntry[iRes] );
    return (((unsigned int)c) >= ((aEntry[iRes]>>10) + (aEntry[iRes]&0x3FF)));
  }
  return 1;}
  puts "\}"
}

proc print_test_isalnum {zFunc lRange} {
  foreach range $lRange {
................................................................................
*/

/*
** DO NOT EDIT THIS MACHINE GENERATED FILE.
*/
  }]
  puts ""
  puts "#if defined(SQLITE_ENABLE_FTS4_UNICODE61)"
  puts "#if defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4)"
  puts ""
  puts "#include <assert.h>"
  puts ""
}

proc print_test_main {} {
................................................................................
if {$::generate_test_code} {
  print_test_isalnum sqlite3FtsUnicodeIsalnum $lRange
  print_fold_test sqlite3FtsUnicodeFold $mappings
  print_test_main 
}

puts "#endif /* defined(SQLITE_ENABLE_FTS3) || defined(SQLITE_ENABLE_FTS4) */"
puts "#endif /* !defined(SQLITE_ENABLE_FTS4_UNICODE61) */"

  i = p->nCol-1;
  db = pParse->db;
  zColl = sqlite3NameFromToken(db, pToken);
  if( !zColl ) return;

  if( sqlite3LocateCollSeq(pParse, zColl) ){
    Index *pIdx;

    p->aCol[i].zColl = zColl;
  
    /* If the column is declared as "<name> PRIMARY KEY COLLATE <type>",
    ** then an index may have been created on this column before the
    ** collation type was added. Correct this if it is the case.
    */
    for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){

  i = p->nCol-1;
  db = pParse->db;
  zColl = sqlite3NameFromToken(db, pToken);
  if( !zColl ) return;

  if( sqlite3LocateCollSeq(pParse, zColl) ){
    Index *pIdx;
    sqlite3DbFree(db, p->aCol[i].zColl);
    p->aCol[i].zColl = zColl;
  
    /* If the column is declared as "<name> PRIMARY KEY COLLATE <type>",
    ** then an index may have been created on this column before the
    ** collation type was added. Correct this if it is the case.
    */
    for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){

  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
  int p1, p2;           /* Operands of the opcode used to ends the loop */
  union {               /* Information that depends on plan.wsFlags */
    struct {
      int nIn;              /* Number of entries in aInLoop[] */
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
        u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
      } *aInLoop;           /* Information about each nested IN operator */
    } in;                 /* Used when plan.wsFlags&WHERE_IN_ABLE */
    Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  } u;
  struct WhereLoop *pWLoop;  /* The selected WhereLoop object */
};

/*
** Each instance of this object represents a way of evaluating one
................................................................................
    WhereLoop *pLoop = pLevel->pWLoop;

    if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0
      && pLoop->u.btree.pIndex!=0
      && pLoop->u.btree.pIndex->aSortOrder[iEq]
    ){
      testcase( iEq==0 );
      testcase( iEq==pLevel->plan.u.pIdx->nColumn-1 );
      testcase( iEq>0 && iEq+1<pLevel->plan.u.pIdx->nColumn );
      testcase( bRev );
      bRev = !bRev;
    }
    assert( pX->op==TK_IN );
    iReg = iTarget;
    eType = sqlite3FindInIndex(pParse, pX, 0);
    if( eType==IN_INDEX_INDEX_DESC ){
................................................................................
    }

    /* If there are inequality constraints, check that the value
    ** of the table column that the inequality contrains is not NULL.
    ** If it is, jump to the next iteration of the loop.
    */
    r1 = sqlite3GetTempReg(pParse);
    testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
    testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
    if( (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
      sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
    }
    sqlite3ReleaseTempReg(pParse, r1);

    /* Seek the table cursor, if required */

  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
  int p1, p2;           /* Operands of the opcode used to ends the loop */
  union {               /* Information that depends on pWLoop->wsFlags */
    struct {
      int nIn;              /* Number of entries in aInLoop[] */
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
        u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
      } *aInLoop;           /* Information about each nested IN operator */
    } in;                 /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */
    Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  } u;
  struct WhereLoop *pWLoop;  /* The selected WhereLoop object */
};

/*
** Each instance of this object represents a way of evaluating one
................................................................................
    WhereLoop *pLoop = pLevel->pWLoop;

    if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0
      && pLoop->u.btree.pIndex!=0
      && pLoop->u.btree.pIndex->aSortOrder[iEq]
    ){
      testcase( iEq==0 );


      testcase( bRev );
      bRev = !bRev;
    }
    assert( pX->op==TK_IN );
    iReg = iTarget;
    eType = sqlite3FindInIndex(pParse, pX, 0);
    if( eType==IN_INDEX_INDEX_DESC ){
................................................................................
    }

    /* If there are inequality constraints, check that the value
    ** of the table column that the inequality contrains is not NULL.
    ** If it is, jump to the next iteration of the loop.
    */
    r1 = sqlite3GetTempReg(pParse);
    testcase( pLoop->wsFlags & WHERE_BTM_LIMIT );
    testcase( pLoop->wsFlags & WHERE_TOP_LIMIT );
    if( (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
      sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
    }
    sqlite3ReleaseTempReg(pParse, r1);

    /* Seek the table cursor, if required */

  }
} {{} 1 12 101}
do_test collate1-4.5 {
  execsql {
    DROP TABLE collate1t1;
  }
} {}






























finish_test

  }
} {{} 1 12 101}
do_test collate1-4.5 {
  execsql {
    DROP TABLE collate1t1;
  }
} {}

# A problem reported on the mailing list:  A CREATE TABLE statement
# is allowed to have two or more COLLATE clauses on the same column.
# That probably ought to be an error, but we allow it for backwards
# compatibility.  Just make sure it works and doesn't leak memory.
#
do_test collate1-5.1 {
  execsql {
    CREATE TABLE c5(
      id INTEGER PRIMARY KEY,
      a TEXT COLLATE binary COLLATE nocase COLLATE rtrim,
      b TEXT COLLATE nocase COLLATE binary,
      c TEXT COLLATE rtrim COLLATE binary COLLATE rtrim COLLATE nocase
    );
    INSERT INTO c5 VALUES(1, 'abc','abc','abc');
    INSERT INTO c5 VALUES(2, 'abc   ','ABC','ABC');
    SELECT id FROM c5 WHERE a='abc' ORDER BY id;
  }
} {1 2}
do_test collate1-5.2 {
  execsql {
    SELECT id FROM c5 WHERE b='abc' ORDER BY id;
  }
} {1}
do_test collate1-5.3 {
  execsql {
    SELECT id FROM c5 WHERE c='abc' ORDER BY id;
  }
} {1 2}

finish_test

  do_isspace_test 6.$T.19 $T   {32 160 5760 6158}
  do_isspace_test 6.$T.19 $T   {8192 8193 8194 8195}
  do_isspace_test 6.$T.19 $T   {8196 8197 8198 8199}
  do_isspace_test 6.$T.19 $T   {8200 8201 8202 8239}
  do_isspace_test 6.$T.19 $T   {8287 12288}
}




















finish_test

  do_isspace_test 6.$T.19 $T   {32 160 5760 6158}
  do_isspace_test 6.$T.19 $T   {8192 8193 8194 8195}
  do_isspace_test 6.$T.19 $T   {8196 8197 8198 8199}
  do_isspace_test 6.$T.19 $T   {8200 8201 8202 8239}
  do_isspace_test 6.$T.19 $T   {8287 12288}
}

#-------------------------------------------------------------------------
# Test that the private use ranges are treated as alphanumeric.
#
breakpoint
foreach {tn1 c} {
  1 \ue000 2 \ue001 3 \uf000 4 \uf8fe 5 \uf8ff
} {
  foreach {tn2 config res} {
    1 ""             "0 hello*world hello*world"
    2 "separators=*" "0 hello hello 1 world world"
  } {
    set config [string map [list * $c] $config]
    set input  [string map [list * $c] "hello*world"]
    set output [string map [list * $c] $res]
    do_unicode_token_test3 7.$tn1.$tn2 {*}$config $input $output
  }
}


finish_test

          )
        ) ELSE (
          REM
          REM NOTE: Even when the cleaning step has been disabled, we still
          REM       need to remove the build output for the files we are
          REM       specifically wanting to build for each platform.
          REM
          %__ECHO% DEL /Q sqlite3.dll sqlite3.lib sqlite3.pdb
        )

        REM
        REM NOTE: Call NMAKE with the MSVC makefile to build the "sqlite3.dll"
        REM       binary.  The x86 compiler will be used to compile the native
        REM       command line tools needed during the build process itself.
        REM       Also, disable looking for and/or linking to the native Tcl

          )
        ) ELSE (
          REM
          REM NOTE: Even when the cleaning step has been disabled, we still
          REM       need to remove the build output for the files we are
          REM       specifically wanting to build for each platform.
          REM
          %__ECHO% DEL /Q *.lo sqlite3.dll sqlite3.lib sqlite3.pdb
        )

        REM
        REM NOTE: Call NMAKE with the MSVC makefile to build the "sqlite3.dll"
        REM       binary.  The x86 compiler will be used to compile the native
        REM       command line tools needed during the build process itself.
        REM       Also, disable looking for and/or linking to the native Tcl