/ Check-in [f968d43f]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Rebalance FTS expressions after parsing to limit recursion during evaluation. Avoid recursion when deleting FTS expression trees. Enforce a limit on the depth of an expression tree.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts3-expr-rebalance
Files: files | file ages | folders
SHA1: f968d43f80cc2f236e7d09ba1e8278343e2b6976
User & Date: dan 2013-04-25 20:34:02
Context
2013-04-26
06:58
Merge latest trunk changes. check-in: 4d08e74d user: dan tags: fts3-expr-rebalance
2013-04-25
20:34
Rebalance FTS expressions after parsing to limit recursion during evaluation. Avoid recursion when deleting FTS expression trees. Enforce a limit on the depth of an expression tree. check-in: f968d43f user: dan tags: fts3-expr-rebalance
2013-04-22
23:38
Fix harmless compiler warnings. check-in: 1a1cf5aa user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3_expr.c.

   636    636           if( !pNot ){
   637    637             sqlite3Fts3ExprFree(p);
   638    638             rc = SQLITE_NOMEM;
   639    639             goto exprparse_out;
   640    640           }
   641    641           pNot->eType = FTSQUERY_NOT;
   642    642           pNot->pRight = p;
          643  +        p->pParent = pNot;
   643    644           if( pNotBranch ){
   644    645             pNot->pLeft = pNotBranch;
          646  +          pNotBranch->pParent = pNot;
   645    647           }
   646    648           pNotBranch = pNot;
   647    649           p = pPrev;
   648    650         }else{
   649    651           int eType = p->eType;
   650    652           isPhrase = (eType==FTSQUERY_PHRASE || p->pLeft);
   651    653   
................................................................................
   725    727           rc = SQLITE_ERROR;
   726    728         }else{
   727    729           Fts3Expr *pIter = pNotBranch;
   728    730           while( pIter->pLeft ){
   729    731             pIter = pIter->pLeft;
   730    732           }
   731    733           pIter->pLeft = pRet;
          734  +        pRet->pParent = pIter;
   732    735           pRet = pNotBranch;
   733    736         }
   734    737       }
   735    738     }
   736    739     *pnConsumed = n - nIn;
   737    740   
   738    741   exprparse_out:
................................................................................
   740    743       sqlite3Fts3ExprFree(pRet);
   741    744       sqlite3Fts3ExprFree(pNotBranch);
   742    745       pRet = 0;
   743    746     }
   744    747     *ppExpr = pRet;
   745    748     return rc;
   746    749   }
          750  +
          751  +/*
          752  +** Return SQLITE_ERROR if the maximum depth of the expression tree passed 
          753  +** as the only argument is more than nMaxDepth.
          754  +*/
          755  +static int fts3ExprCheckDepth(Fts3Expr *p, int nMaxDepth){
          756  +  int rc = SQLITE_OK;
          757  +  if( p ){
          758  +    if( nMaxDepth==0 ){ 
          759  +      rc = SQLITE_ERROR;
          760  +    }else{
          761  +      rc = fts3ExprCheckDepth(p->pLeft, nMaxDepth-1);
          762  +      if( rc==SQLITE_OK ){
          763  +        rc = fts3ExprCheckDepth(p->pRight, nMaxDepth-1);
          764  +      }
          765  +    }
          766  +  }
          767  +  return rc;
          768  +}
          769  +
          770  +/*
          771  +** This function attempts to transform the expression tree at (*pp) to
          772  +** an equivalent but more balanced form. The tree is modified in place.
          773  +** If successful, SQLITE_OK is returned and (*pp) set to point to the 
          774  +** new root expression node. 
          775  +**
          776  +** nMaxDepth is the maximum allowable depth of the balanced sub-tree.
          777  +**
          778  +** Otherwise, if an error occurs, an SQLite error code is returned and 
          779  +** expression (*pp) freed.
          780  +*/
          781  +static int fts3ExprBalance(Fts3Expr **pp, int nMaxDepth){
          782  +  int rc = SQLITE_OK;             /* Return code */
          783  +  Fts3Expr *pRoot = *pp;          /* Initial root node */
          784  +  Fts3Expr *pFree = 0;            /* List of free nodes. Linked by pParent. */
          785  +  int eType = pRoot->eType;       /* Type of node in this tree */
          786  +
          787  +  if( nMaxDepth==0 ){
          788  +    rc = SQLITE_ERROR;
          789  +  }
          790  +
          791  +  if( rc==SQLITE_OK && (eType==FTSQUERY_AND || eType==FTSQUERY_OR) ){
          792  +    Fts3Expr **apLeaf;
          793  +    apLeaf = (Fts3Expr **)sqlite3_malloc(sizeof(Fts3Expr *) * nMaxDepth);
          794  +    if( 0==apLeaf ){
          795  +      rc = SQLITE_NOMEM;
          796  +    }else{
          797  +      memset(apLeaf, 0, sizeof(Fts3Expr *) * nMaxDepth);
          798  +    }
          799  +
          800  +    if( rc==SQLITE_OK ){
          801  +      int i;
          802  +      Fts3Expr *p;
          803  +
          804  +      /* Set $p to point to the left-most leaf in the tree of eType nodes. */
          805  +      for(p=pRoot; p->eType==eType; p=p->pLeft){
          806  +        assert( p->pParent==0 || p->pParent->pLeft==p );
          807  +        assert( p->pLeft && p->pRight );
          808  +      }
          809  +
          810  +      /* This loop runs once for each leaf in the tree of eType nodes. */
          811  +      while( 1 ){
          812  +        int iLvl;
          813  +        Fts3Expr *pParent = p->pParent;     /* Current parent of p */
          814  +
          815  +        assert( pParent==0 || pParent->pLeft==p );
          816  +        p->pParent = 0;
          817  +        if( pParent ){
          818  +          pParent->pLeft = 0;
          819  +        }else{
          820  +          pRoot = 0;
          821  +        }
          822  +        rc = fts3ExprBalance(&p, nMaxDepth-1);
          823  +        if( rc!=SQLITE_OK ) break;
          824  +
          825  +        for(iLvl=0; p && iLvl<nMaxDepth; iLvl++){
          826  +          if( apLeaf[iLvl]==0 ){
          827  +            apLeaf[iLvl] = p;
          828  +            p = 0;
          829  +          }else{
          830  +            assert( pFree );
          831  +            pFree->pLeft = apLeaf[iLvl];
          832  +            pFree->pRight = p;
          833  +            pFree->pLeft->pParent = pFree;
          834  +            pFree->pRight->pParent = pFree;
          835  +
          836  +            p = pFree;
          837  +            pFree = pFree->pParent;
          838  +            p->pParent = 0;
          839  +            apLeaf[iLvl] = 0;
          840  +          }
          841  +        }
          842  +        if( p ){
          843  +          sqlite3Fts3ExprFree(p);
          844  +          rc = SQLITE_ERROR;
          845  +          break;
          846  +        }
          847  +
          848  +        /* If that was the last leaf node, break out of the loop */
          849  +        if( pParent==0 ) break;
          850  +
          851  +        /* Set $p to point to the next leaf in the tree of eType nodes */
          852  +        for(p=pParent->pRight; p->eType==eType; p=p->pLeft);
          853  +
          854  +        /* Remove pParent from the original tree. */
          855  +        assert( pParent->pParent==0 || pParent->pParent->pLeft==pParent );
          856  +        pParent->pRight->pParent = pParent->pParent;
          857  +        if( pParent->pParent ){
          858  +          pParent->pParent->pLeft = pParent->pRight;
          859  +        }else{
          860  +          assert( pParent==pRoot );
          861  +          pRoot = pParent->pRight;
          862  +        }
          863  +
          864  +        /* Link pParent into the free node list. It will be used as an
          865  +        ** internal node of the new tree.  */
          866  +        pParent->pParent = pFree;
          867  +        pFree = pParent;
          868  +      }
          869  +
          870  +      if( rc==SQLITE_OK ){
          871  +        p = 0;
          872  +        for(i=0; i<nMaxDepth; i++){
          873  +          if( apLeaf[i] ){
          874  +            if( p==0 ){
          875  +              p = apLeaf[i];
          876  +              p->pParent = 0;
          877  +            }else{
          878  +              pFree->pRight = p;
          879  +              pFree->pLeft = apLeaf[i];
          880  +              pFree->pLeft->pParent = pFree;
          881  +              pFree->pRight->pParent = pFree;
          882  +
          883  +              p = pFree;
          884  +              pFree = pFree->pParent;
          885  +              p->pParent = 0;
          886  +            }
          887  +          }
          888  +        }
          889  +        pRoot = p;
          890  +      }else{
          891  +        /* An error occurred. Delete the contents of the apLeaf[] array 
          892  +        ** and pFree list. Everything else is cleaned up by the call to
          893  +        ** sqlite3Fts3ExprFree(pRoot) below.  */
          894  +        Fts3Expr *pDel;
          895  +        for(i=0; i<nMaxDepth; i++){
          896  +          sqlite3Fts3ExprFree(apLeaf[i]);
          897  +        }
          898  +        while( pDel=pFree ){
          899  +          pFree = pDel->pParent;
          900  +          sqlite3_free(pDel);
          901  +        }
          902  +      }
          903  +
          904  +      assert( pFree==0 );
          905  +      sqlite3_free( apLeaf );
          906  +    }
          907  +  }
          908  +
          909  +  if( rc!=SQLITE_OK ){
          910  +    sqlite3Fts3ExprFree(pRoot);
          911  +    pRoot = 0;
          912  +  }
          913  +  *pp = pRoot;
          914  +  return rc;
          915  +}
          916  +
          917  +/*
          918  +** This function is similar to sqlite3Fts3ExprParse(), with the following
          919  +** differences:
          920  +**
          921  +**   1. It does not do expression rebalancing.
          922  +**   2. It does not check that the expression does not exceed the 
          923  +**      maximum allowable depth.
          924  +**   3. Even if it fails, *ppExpr may still be set to point to an 
          925  +**      expression tree. It should be deleted using sqlite3Fts3ExprFree()
          926  +**      in this case.
          927  +*/
          928  +static int fts3ExprParseUnbalanced(
          929  +  sqlite3_tokenizer *pTokenizer,      /* Tokenizer module */
          930  +  int iLangid,                        /* Language id for tokenizer */
          931  +  char **azCol,                       /* Array of column names for fts3 table */
          932  +  int bFts4,                          /* True to allow FTS4-only syntax */
          933  +  int nCol,                           /* Number of entries in azCol[] */
          934  +  int iDefaultCol,                    /* Default column to query */
          935  +  const char *z, int n,               /* Text of MATCH query */
          936  +  Fts3Expr **ppExpr                   /* OUT: Parsed query structure */
          937  +){
          938  +  static const int MAX_EXPR_DEPTH = 12;
          939  +  int nParsed;
          940  +  int rc;
          941  +  ParseContext sParse;
          942  +
          943  +  memset(&sParse, 0, sizeof(ParseContext));
          944  +  sParse.pTokenizer = pTokenizer;
          945  +  sParse.iLangid = iLangid;
          946  +  sParse.azCol = (const char **)azCol;
          947  +  sParse.nCol = nCol;
          948  +  sParse.iDefaultCol = iDefaultCol;
          949  +  sParse.bFts4 = bFts4;
          950  +  if( z==0 ){
          951  +    *ppExpr = 0;
          952  +    return SQLITE_OK;
          953  +  }
          954  +  if( n<0 ){
          955  +    n = (int)strlen(z);
          956  +  }
          957  +  rc = fts3ExprParse(&sParse, z, n, ppExpr, &nParsed);
          958  +  assert( rc==SQLITE_OK || *ppExpr==0 );
          959  +
          960  +  /* Check for mismatched parenthesis */
          961  +  if( rc==SQLITE_OK && sParse.nNest ){
          962  +    rc = SQLITE_ERROR;
          963  +  }
          964  +  
          965  +  return rc;
          966  +}
   747    967   
   748    968   /*
   749    969   ** Parameters z and n contain a pointer to and length of a buffer containing
   750    970   ** an fts3 query expression, respectively. This function attempts to parse the
   751    971   ** query expression and create a tree of Fts3Expr structures representing the
   752    972   ** parsed expression. If successful, *ppExpr is set to point to the head
   753    973   ** of the parsed expression tree and SQLITE_OK is returned. If an error
................................................................................
   775    995     char **azCol,                       /* Array of column names for fts3 table */
   776    996     int bFts4,                          /* True to allow FTS4-only syntax */
   777    997     int nCol,                           /* Number of entries in azCol[] */
   778    998     int iDefaultCol,                    /* Default column to query */
   779    999     const char *z, int n,               /* Text of MATCH query */
   780   1000     Fts3Expr **ppExpr                   /* OUT: Parsed query structure */
   781   1001   ){
   782         -  int nParsed;
   783         -  int rc;
   784         -  ParseContext sParse;
   785         -
   786         -  memset(&sParse, 0, sizeof(ParseContext));
   787         -  sParse.pTokenizer = pTokenizer;
   788         -  sParse.iLangid = iLangid;
   789         -  sParse.azCol = (const char **)azCol;
   790         -  sParse.nCol = nCol;
   791         -  sParse.iDefaultCol = iDefaultCol;
   792         -  sParse.bFts4 = bFts4;
   793         -  if( z==0 ){
   794         -    *ppExpr = 0;
   795         -    return SQLITE_OK;
         1002  +  static const int MAX_EXPR_DEPTH = 12;
         1003  +  int rc = fts3ExprParseUnbalanced(
         1004  +      pTokenizer, iLangid, azCol, bFts4, nCol, iDefaultCol, z, n, ppExpr
         1005  +  );
         1006  +  
         1007  +  /* Rebalance the expression. And check that its depth does not exceed
         1008  +  ** MAX_EXPR_DEPTH.  */
         1009  +  if( rc==SQLITE_OK && *ppExpr ){
         1010  +    rc = fts3ExprBalance(ppExpr, MAX_EXPR_DEPTH);
         1011  +    if( rc==SQLITE_OK ){
         1012  +      rc = fts3ExprCheckDepth(*ppExpr, MAX_EXPR_DEPTH);
         1013  +    }
   796   1014     }
   797         -  if( n<0 ){
   798         -    n = (int)strlen(z);
   799         -  }
   800         -  rc = fts3ExprParse(&sParse, z, n, ppExpr, &nParsed);
   801         -
   802         -  /* Check for mismatched parenthesis */
   803         -  if( rc==SQLITE_OK && sParse.nNest ){
   804         -    rc = SQLITE_ERROR;
         1015  +  if( rc!=SQLITE_OK ){
   805   1016       sqlite3Fts3ExprFree(*ppExpr);
   806   1017       *ppExpr = 0;
   807   1018     }
   808   1019   
   809   1020     return rc;
   810   1021   }
         1022  +
         1023  +/*
         1024  +** Free a single node of an expression tree.
         1025  +*/
         1026  +static void fts3FreeExprNode(Fts3Expr *p){
         1027  +  assert( p->eType==FTSQUERY_PHRASE || p->pPhrase==0 );
         1028  +  sqlite3Fts3EvalPhraseCleanup(p->pPhrase);
         1029  +  sqlite3_free(p->aMI);
         1030  +  sqlite3_free(p);
         1031  +}
   811   1032   
   812   1033   /*
   813   1034   ** Free a parsed fts3 query expression allocated by sqlite3Fts3ExprParse().
         1035  +**
         1036  +** This function would be simpler if it recursively called itself. But
         1037  +** that would mean passing a sufficiently large expression to ExprParse()
         1038  +** could cause a stack overflow.
   814   1039   */
   815         -void sqlite3Fts3ExprFree(Fts3Expr *p){
   816         -  if( p ){
   817         -    assert( p->eType==FTSQUERY_PHRASE || p->pPhrase==0 );
   818         -    sqlite3Fts3ExprFree(p->pLeft);
   819         -    sqlite3Fts3ExprFree(p->pRight);
   820         -    sqlite3Fts3EvalPhraseCleanup(p->pPhrase);
   821         -    sqlite3_free(p->aMI);
   822         -    sqlite3_free(p);
         1040  +void sqlite3Fts3ExprFree(Fts3Expr *pDel){
         1041  +  Fts3Expr *p;
         1042  +  assert( pDel==0 || pDel->pParent==0 );
         1043  +  for(p=pDel; p && (p->pLeft||p->pRight); p=(p->pLeft ? p->pLeft : p->pRight)){
         1044  +    assert( p->pParent==0 || p==p->pParent->pRight || p==p->pParent->pLeft );
         1045  +  }
         1046  +  while( p ){
         1047  +    Fts3Expr *pParent = p->pParent;
         1048  +    fts3FreeExprNode(p);
         1049  +    if( pParent && p==pParent->pLeft && pParent->pRight ){
         1050  +      p = pParent->pRight;
         1051  +      while( p && (p->pLeft || p->pRight) ){
         1052  +        assert( p==p->pParent->pRight || p==p->pParent->pLeft );
         1053  +        p = (p->pLeft ? p->pLeft : p->pRight);
         1054  +      }
         1055  +    }else{
         1056  +      p = pParent;
         1057  +    }
   823   1058     }
   824   1059   }
   825   1060   
   826   1061   /****************************************************************************
   827   1062   *****************************************************************************
   828   1063   ** Everything after this point is just test code.
   829   1064   */
................................................................................
   867   1102   ** sqlite3_free() to release the memory. If an OOM condition is encountered,
   868   1103   ** NULL is returned.
   869   1104   **
   870   1105   ** If the second argument is not NULL, then its contents are prepended to 
   871   1106   ** the returned expression text and then freed using sqlite3_free().
   872   1107   */
   873   1108   static char *exprToString(Fts3Expr *pExpr, char *zBuf){
         1109  +  if( pExpr==0 ){
         1110  +    return sqlite3_mprintf("");
         1111  +  }
   874   1112     switch( pExpr->eType ){
   875   1113       case FTSQUERY_PHRASE: {
   876   1114         Fts3Phrase *pPhrase = pExpr->pPhrase;
   877   1115         int i;
   878   1116         zBuf = sqlite3_mprintf(
   879   1117             "%zPHRASE %d 0", zBuf, pPhrase->iColumn);
   880   1118         for(i=0; zBuf && i<pPhrase->nToken; i++){
................................................................................
   974   1212       sqlite3_result_error_nomem(context);
   975   1213       goto exprtest_out;
   976   1214     }
   977   1215     for(ii=0; ii<nCol; ii++){
   978   1216       azCol[ii] = (char *)sqlite3_value_text(argv[ii+2]);
   979   1217     }
   980   1218   
   981         -  rc = sqlite3Fts3ExprParse(
   982         -      pTokenizer, 0, azCol, 0, nCol, nCol, zExpr, nExpr, &pExpr
   983         -  );
         1219  +  if( sqlite3_user_data(context) ){
         1220  +    rc = sqlite3Fts3ExprParse(
         1221  +        pTokenizer, 0, azCol, 0, nCol, nCol, zExpr, nExpr, &pExpr
         1222  +    );
         1223  +    assert( rc==SQLITE_OK || pExpr==0 );
         1224  +  }else{
         1225  +    rc = fts3ExprParseUnbalanced(
         1226  +        pTokenizer, 0, azCol, 0, nCol, nCol, zExpr, nExpr, &pExpr
         1227  +    );
         1228  +  }
         1229  +
   984   1230     if( rc!=SQLITE_OK && rc!=SQLITE_NOMEM ){
         1231  +    sqlite3Fts3ExprFree(pExpr);
   985   1232       sqlite3_result_error(context, "Error parsing expression", -1);
   986   1233     }else if( rc==SQLITE_NOMEM || !(zBuf = exprToString(pExpr, 0)) ){
   987   1234       sqlite3_result_error_nomem(context);
   988   1235     }else{
   989   1236       sqlite3_result_text(context, zBuf, -1, SQLITE_TRANSIENT);
   990   1237       sqlite3_free(zBuf);
   991   1238     }
................................................................................
  1000   1247   }
  1001   1248   
  1002   1249   /*
  1003   1250   ** Register the query expression parser test function fts3_exprtest() 
  1004   1251   ** with database connection db. 
  1005   1252   */
  1006   1253   int sqlite3Fts3ExprInitTestInterface(sqlite3* db){
  1007         -  return sqlite3_create_function(
         1254  +  int rc = sqlite3_create_function(
  1008   1255         db, "fts3_exprtest", -1, SQLITE_UTF8, 0, fts3ExprTest, 0, 0
  1009   1256     );
         1257  +  if( rc==SQLITE_OK ){
         1258  +    rc = sqlite3_create_function(db, "fts3_exprtest_rebalance", 
         1259  +        -1, SQLITE_UTF8, (void *)1, fts3ExprTest, 0, 0
         1260  +    );
         1261  +  }
         1262  +  return rc;
  1010   1263   }
  1011   1264   
  1012   1265   #endif
  1013   1266   #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */

Added test/fts3expr3.test.

            1  +# 2009 January 1
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#*************************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this script is testing the part of the FTS3 expression
           13  +# parser that rebalances large expressions.
           14  +#
           15  +# $Id: fts3expr2.test,v 1.2 2009/06/05 17:09:12 drh Exp $
           16  +#
           17  +
           18  +set testdir [file dirname $argv0]
           19  +source $testdir/tester.tcl
           20  +source $testdir/malloc_common.tcl
           21  +set ::testprefix fts3expr3
           22  +
           23  +# If SQLITE_ENABLE_FTS3 is defined, omit this file.
           24  +ifcapable !fts3 {
           25  +  finish_test
           26  +  return
           27  +}
           28  +
           29  +set sqlite_fts3_enable_parentheses 1
           30  +
           31  +proc strip_phrase_data {L} {
           32  +  if {[lindex $L 0] eq "PHRASE"} {
           33  +    return [list P [lrange $L 3 end]]
           34  +  }
           35  +  return [list \
           36  +    [lindex $L 0] \
           37  +    [strip_phrase_data [lindex $L 1]] \
           38  +    [strip_phrase_data [lindex $L 2]] \
           39  +  ]
           40  +}
           41  +proc test_fts3expr2 {expr} {
           42  +  strip_phrase_data [
           43  +    db one {SELECT fts3_exprtest_rebalance('simple', $expr, 'a', 'b', 'c')}
           44  +  ]
           45  +}
           46  +
           47  +proc balanced_exprtree_structure {nEntry} {
           48  +  set L [list]
           49  +  for {set i 1} {$i <= $nEntry} {incr i} {
           50  +    lappend L xxx
           51  +  }
           52  +  while {[llength $L] > 1} {
           53  +    set N [list]
           54  +    if {[llength $L] % 2} {
           55  +      foreach {a b} [lrange $L 0 end-1] { lappend N [list AND $a $b] }
           56  +      lappend N [lindex $L end]
           57  +    } else {
           58  +      foreach {a b} $L { lappend N [list AND $a $b] }
           59  +    }
           60  +    set L $N
           61  +  }
           62  +  return [lindex $L 0]
           63  +}
           64  +
           65  +proc balanced_and_tree {nEntry} {
           66  +  set query [balanced_exprtree_structure $nEntry]
           67  +  if {$query == "xxx"} {
           68  +    return "P 1"
           69  +  }
           70  +  for {set i 1} {$i <= $nEntry} {incr i} {
           71  +    regsub xxx $query "{P $i}" query
           72  +  }
           73  +  return $query
           74  +}
           75  +
           76  +proc random_tree_structure {nEntry bParen op} {
           77  +  set query xxx
           78  +  for {set i 1} {$i < $nEntry} {incr i} {
           79  +    set x1 [expr int(rand()*4.0)]
           80  +    set x2 [expr int(rand()*2.0)]
           81  +    if {$x1==0 && $bParen} {
           82  +      set query "($query)"
           83  +    }
           84  +    if {$x2} {
           85  +      set query "xxx $op $query"
           86  +    } else {
           87  +      set query "$query $op xxx"
           88  +    }
           89  +  }
           90  +  return $query
           91  +}
           92  +
           93  +proc random_and_query {nEntry {bParen 0}} {
           94  +  set query [random_tree_structure $nEntry $bParen AND]
           95  +  for {set i 1} {$i <= $nEntry} {incr i} {
           96  +    regsub xxx $query $i query
           97  +  }
           98  +  return $query
           99  +}
          100  +
          101  +proc random_or_query {nEntry} {
          102  +  set query [random_tree_structure $nEntry 1 OR]
          103  +  for {set i 1} {$i <= $nEntry} {incr i} {
          104  +    regsub xxx $query $i query
          105  +  }
          106  +  return $query
          107  +}
          108  +
          109  +proc random_andor_query {nEntry} {
          110  +  set query [random_tree_structure $nEntry 1 AND]
          111  +  for {set i 1} {$i <= $nEntry} {incr i} {
          112  +    regsub xxx $query "([random_or_query $nEntry])" query
          113  +  }
          114  +  return $query
          115  +}
          116  +
          117  +proc balanced_andor_tree {nEntry} {
          118  +  set tree [balanced_exprtree_structure $nEntry]
          119  +  set node "{[balanced_and_tree $nEntry]}"
          120  +  regsub -all AND $node OR node
          121  +  regsub -all xxx $tree $node tree
          122  +  return $tree
          123  +}
          124  +
          125  +# Test that queries like "1 AND 2 AND 3 AND 4..." are transformed to 
          126  +# balanced trees by FTS.
          127  +#
          128  +for {set i 1} {$i < 100} {incr i} {
          129  +  do_test 1.$i {
          130  +    test_fts3expr2 [random_and_query $i]
          131  +  } [balanced_and_tree $i]
          132  +}
          133  +
          134  +# Same again, except with parenthesis inserted at arbitrary points.
          135  +#
          136  +for {set i 1} {$i < 100} {incr i} {
          137  +  do_test 2.$i {
          138  +    test_fts3expr2 [random_and_query $i 1]
          139  +  } [balanced_and_tree $i]
          140  +}
          141  +
          142  +# Now attempt to balance two AND trees joined by an OR.
          143  +#
          144  +for {set i 1} {$i < 100} {incr i} {
          145  +  do_test 3.$i {
          146  +    test_fts3expr2 "[random_and_query $i 1] OR [random_and_query $i 1]"
          147  +  } [list OR [balanced_and_tree $i] [balanced_and_tree $i]]
          148  +}
          149  +
          150  +# Try trees of AND nodes with leaves that are themselves trees of OR nodes.
          151  +#
          152  +for {set i 2} {$i < 32} {incr i} {
          153  +  do_test 3.$i {
          154  +    test_fts3expr2 [random_andor_query $i]
          155  +  } [balanced_andor_tree $i]
          156  +}
          157  +
          158  +# These exceed the depth limit. 
          159  +#
          160  +for {set i 33} {$i < 40} {incr i} {
          161  +  do_test 3.$i {
          162  +    list [catch {test_fts3expr2 [random_andor_query $i]} msg] $msg
          163  +  } {1 {Error parsing expression}}
          164  +}
          165  +
          166  +# This also exceeds the depth limit. 
          167  +#
          168  +do_test 4.1 {
          169  +  set q "1"
          170  +  for {set i 2} {$i < 5000} {incr i} {
          171  +    append q " AND $i"
          172  +  }
          173  +  list [catch {test_fts3expr2 $q} msg] $msg
          174  +} {1 {Error parsing expression}}
          175  +
          176  +proc create_toggle_tree {nDepth} {
          177  +  if {$nDepth == 0} { return xxx }
          178  +  set nNew [expr $nDepth-1]
          179  +  if {$nDepth % 2} {
          180  +    return "([create_toggle_tree $nNew]) OR ([create_toggle_tree $nNew])"
          181  +  }
          182  +  return "([create_toggle_tree $nNew]) AND ([create_toggle_tree $nNew])"
          183  +}
          184  +
          185  +do_test 4.2 {
          186  +  list [catch {test_fts3expr2 [create_toggle_tree 17]} msg] $msg
          187  +} {1 {Error parsing expression}}
          188  +
          189  +set query [random_andor_query 12]
          190  +set result [balanced_andor_tree 12]
          191  +do_faultsim_test fts3expr3-fault-1 -faults oom-* -body {
          192  +  test_fts3expr2 $::query
          193  +} -test {
          194  +  faultsim_test_result [list 0 $::result]
          195  +}
          196  +
          197  +set sqlite_fts3_enable_parentheses 0
          198  +finish_test
          199  +
          200  +
          201  +
          202  +

Changes to test/permutations.test.

   182    182     All FTS3 tests except fts3rnd.test.
   183    183   } -files {
   184    184     fts3aa.test fts3ab.test fts3ac.test fts3ad.test fts3ae.test
   185    185     fts3af.test fts3ag.test fts3ah.test fts3ai.test fts3aj.test
   186    186     fts3ak.test fts3al.test fts3am.test fts3an.test fts3ao.test
   187    187     fts3atoken.test fts3b.test fts3c.test fts3cov.test fts3d.test
   188    188     fts3defer.test fts3defer2.test fts3e.test fts3expr.test fts3expr2.test 
          189  +  fts3expr3.test
   189    190     fts3near.test fts3query.test fts3shared.test fts3snippet.test 
   190    191     fts3sort.test
   191    192     fts3fault.test fts3malloc.test fts3matchinfo.test
   192    193     fts3aux1.test fts3comp1.test fts3auto.test
   193    194     fts4aa.test fts4content.test
   194    195     fts3conf.test fts3prefix.test fts3fault2.test fts3corrupt.test
   195    196     fts3corrupt2.test fts3first.test fts4langid.test fts4merge.test