SQLite

  Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:
**
**       FTS5_AND                 (nChild, apChild valid)
**       FTS5_OR                  (nChild, apChild valid)
**       FTS5_NOT                 (nChild, apChild valid)
**       FTS5_STRING              (pNear valid)
*/
struct Fts5ExprNode {
  int eType;                      /* Node type */
  int bEof;                       /* True at EOF */
  i64 iRowid;                     /* Current rowid */
  Fts5ExprNearset *pNear;         /* For FTS5_STRING - cluster of phrases */

  /* Child nodes. For a NOT node, this array always contains 2 entries. For 
  ** AND or OR nodes, it contains 2 or more entries.  */
  int nChild;                     /* Number of child nodes */
  Fts5ExprNode *apChild[0];       /* Array of child nodes */
};

/*
** An instance of the following structure represents a single search term
** or term prefix.
*/
struct Fts5ExprTerm {

}

/*
** Free the expression node object passed as the only argument.
*/
void sqlite3Fts5ParseNodeFree(Fts5ExprNode *p){
  if( p ){
    int i;
    for(i=0; i<p->nChild; i++){
      sqlite3Fts5ParseNodeFree(p->apChild[i]);
    }
    sqlite3Fts5ParseNearsetFree(p->pNear);
    sqlite3_free(p);
  }
}

/*
** Free the expression object passed as the only argument.

      }
    }while( bMatch==0 );
  }

  pNode->iRowid = iLast;
  return rc;
}


/*
** IN/OUT parameter (*pa) points to a position list n bytes in size. If
** the position list contains entries for column iCol, then (*pa) is set
** to point to the sub-position-list for that column and the number of
** bytes in it returned. Or, if the argument position list does not
** contain any entries for column iCol, return 0.

  return rc;
}

/* fts5ExprNodeNext() calls fts5ExprNodeNextMatch(). And vice-versa. */
static int fts5ExprNodeNextMatch(Fts5Expr*, Fts5ExprNode*);


/*
** If pExpr is an ASC iterator, this function returns a value with the
** same sign as:
**
**   (iLhs - iRhs)
**
** Otherwise, if this is a DESC iterator, the opposite is returned:
**
**   (iRhs - iLhs)
*/
static int fts5RowidCmp(
  Fts5Expr *pExpr,
  i64 iLhs,
  i64 iRhs
){
  assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
  if( pExpr->bDesc==0 ){
    if( iLhs<iRhs ) return -1;
    return (iLhs > iRhs);
  }else{
    if( iLhs>iRhs ) return -1;
    return (iLhs < iRhs);
  }
}

static void fts5ExprSetEof(Fts5ExprNode *pNode){
  if( pNode ){
    int i;
    pNode->bEof = 1;
    for(i=0; i<pNode->nChild; i++){
      fts5ExprSetEof(pNode->apChild[i]);
    }
  }
}


static int fts5ExprNodeNext(Fts5Expr*, Fts5ExprNode*, int, i64);

/*
** Argument pNode is an FTS5_AND node.
*/
static int fts5ExprAndNextRowid(
  Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
  Fts5ExprNode *pAnd              /* FTS5_AND node to advance */
){
  int iChild;
  i64 iLast = pAnd->iRowid;
  int rc = SQLITE_OK;
  int bMatch;

  assert( pAnd->bEof==0 );
  do {
    bMatch = 1;
    for(iChild=0; iChild<pAnd->nChild; iChild++){
      Fts5ExprNode *pChild = pAnd->apChild[iChild];
      if( 0 && pChild->eType==FTS5_STRING ){
        /* TODO */
      }else{
        int cmp = fts5RowidCmp(pExpr, iLast, pChild->iRowid);
        if( cmp>0 ){
          /* Advance pChild until it points to iLast or laster */
          rc = fts5ExprNodeNext(pExpr, pChild, 1, iLast);
          if( rc!=SQLITE_OK ) return rc;
        }
      }

      /* If the child node is now at EOF, so is the parent AND node. Otherwise,
      ** the child node is guaranteed to have advanced at least as far as
      ** rowid iLast. So if it is not at exactly iLast, pChild->iRowid is the
      ** new lastest rowid seen so far.  */
      assert( pChild->bEof || fts5RowidCmp(pExpr, iLast, pChild->iRowid)<=0 );
      if( pChild->bEof ){
        fts5ExprSetEof(pAnd);
        bMatch = 1;
        break;
      }else if( iLast!=pChild->iRowid ){
        bMatch = 0;
        iLast = pChild->iRowid;
      }
    }
  }while( bMatch==0 );

  pAnd->iRowid = iLast;
  return SQLITE_OK;
}


/*
** Compare the values currently indicated by the two nodes as follows:
**
**    res = (*p1) - (*p2)
**
** Nodes that point to values that come later in the iteration order are

    switch( pNode->eType ){
      case FTS5_STRING: {
        rc = fts5ExprNearAdvanceFirst(pExpr, pNode, bFromValid, iFrom);
        break;
      };

      case FTS5_AND: {
        Fts5ExprNode *pLeft = pNode->apChild[0];
        rc = fts5ExprNodeNext(pExpr, pLeft, bFromValid, iFrom);




        break;
      }

      case FTS5_OR: {
        int i;
        int iLast = pNode->iRowid;


        for(i=0; rc==SQLITE_OK && i<pNode->nChild; i++){
          Fts5ExprNode *p1 = pNode->apChild[i];
          assert( p1->bEof || fts5RowidCmp(pExpr, p1->iRowid, iLast)>=0 );
          if( p1->bEof==0 ){
            if( (p1->iRowid==iLast) 
             || (bFromValid && fts5RowidCmp(pExpr, p1->iRowid, iFrom)<0)
            ){
              rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);
            }




          }
        }

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        assert( pNode->nChild==2 );
        rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom);
        break;
      }
    }

    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }

    Fts5ExprNearset *pNear = pNode->pNear;
    int i;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      pPhrase->poslist.n = 0;
    }
  }else{
    int i;
    for(i=0; i<pNode->nChild; i++){
      fts5ExprNodeZeroPoslist(pNode->apChild[i]);
    }
  }
}

static int fts5ExprNodeTest(
  int *pRc, 
  Fts5Expr *pExpr, 
  i64 iRowid,
  Fts5ExprNode *pNode
){
  int bRes = 0;
  if( pNode->bEof || pNode->iRowid!=iRowid ){
    bRes = 0;
  }else {
    switch( pNode->eType ){
      case FTS5_STRING:
        bRes = fts5ExprNearTest(pRc, pExpr, pNode);
        if( *pRc ) bRes = 0;
        break;

      case FTS5_AND: {
        int i;
        for(i=0; i<pNode->nChild; i++){
          if( fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->apChild[i])==0 ){

            break;
          }
        }
        bRes = (i==pNode->nChild);
        if( bRes==0 && i>0 ){
          for(i=0; i<pNode->nChild; i++){
            fts5ExprNodeZeroPoslist(pNode->apChild[i]);
          }
        }

        break;
      }

      case FTS5_OR: {
        int i;
        for(i=0; i<pNode->nChild; i++){
          if( fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->apChild[i]) ){
            bRes = 1;
          }

        }
        break;
      }

      default:
        assert( pNode->eType==FTS5_NOT );
        assert( pNode->nChild==2 );
        bRes = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->apChild[0]);
        break;
    }
  }

  return bRes;
}










/*
** If pNode currently points to a match, this function returns SQLITE_OK
** without modifying it. Otherwise, pNode is advanced until it does point
** to a match or EOF is reached.
*/
static int fts5ExprNodeNextMatch(
  Fts5Expr *pExpr,                /* Expression of which pNode is a part */

        rc = fts5ExprNearNextMatch(pExpr, pNode);
#endif
        rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
        break;
      }

      case FTS5_AND: {
        rc = fts5ExprAndNextRowid(pExpr, pNode);
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *pNext = pNode->apChild[0];
        int i;

        for(i=1; i<pNode->nChild; i++){
          Fts5ExprNode *pChild = pNode->apChild[i];
          if( fts5NodeCompare(pExpr, pNext, pChild)>0 ){

            pNext = pChild;

          }


        }



        pNode->iRowid = pNext->iRowid;







        pNode->bEof = pNext->bEof;

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        Fts5ExprNode *p1 = pNode->apChild[0];
        Fts5ExprNode *p2 = pNode->apChild[1];
        assert( pNode->nChild==2 );

        while( rc==SQLITE_OK && p1->bEof==0 ){
          int cmp = fts5NodeCompare(pExpr, p1, p2);
          if( cmp>0 ){
            rc = fts5ExprNodeNext(pExpr, p2, 1, p1->iRowid);
            cmp = fts5NodeCompare(pExpr, p1, p2);
          }

#if 0
      rc = fts5ExprNearNextMatch(pExpr, pNode);
#endif
      rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
    }

  }else{
    int i;
    for(i=0; i<pNode->nChild && rc==SQLITE_OK; i++){
      rc = fts5ExprNodeFirst(pExpr, pNode->apChild[i]);
    }

    pNode->iRowid = pNode->apChild[0]->iRowid;
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }
  return rc;
}

** Move to the next document 
**
** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
** is not considered an error if the query does not match any documents.
*/
int sqlite3Fts5ExprNext(Fts5Expr *p){
  int rc;
  Fts5ExprNode *pRoot = p->pRoot;
  do {
    rc = fts5ExprNodeNext(p, pRoot, 0, 0);
  }while( pRoot->bEof==0 
      && fts5ExprNodeTest(&rc, p, pRoot->iRowid, p->pRoot)==0 
      && rc==SQLITE_OK 
  );
  return rc;
}

int sqlite3Fts5ExprEof(Fts5Expr *p){
  return (p->pRoot==0 || p->pRoot->bEof);

){
  if( pNear ){
    pNear->pColset = pColset;
  }else{
    sqlite3_free(pColset);
  }
}

static void fts5ExprAddChildren(Fts5ExprNode *p, Fts5ExprNode *pSub){
  if( p->eType!=FTS5_NOT && pSub->eType==p->eType ){
    int nByte = sizeof(Fts5ExprNode*) * pSub->nChild;
    memcpy(&p->apChild[p->nChild], pSub->apChild, nByte);
    p->nChild += pSub->nChild;
    sqlite3_free(pSub);
  }else{
    p->apChild[p->nChild++] = pSub;
  }
}

/*
** Allocate and return a new expression object. If anything goes wrong (i.e.
** OOM error), leave an error code in pParse and return NULL.
*/
Fts5ExprNode *sqlite3Fts5ParseNode(
  Fts5Parse *pParse,              /* Parse context */
  int eType,                      /* FTS5_STRING, AND, OR or NOT */
  Fts5ExprNode *pLeft,            /* Left hand child expression */
  Fts5ExprNode *pRight,           /* Right hand child expression */
  Fts5ExprNearset *pNear          /* For STRING expressions, the near cluster */
){
  Fts5ExprNode *pRet = 0;

  if( pParse->rc==SQLITE_OK ){
    int nChild = 0;               /* Number of children of returned node */
    int nByte;                    /* Bytes of space to allocate for this node */
 
    assert( (eType!=FTS5_STRING && !pNear)
         || (eType==FTS5_STRING && !pLeft && !pRight)
    );
    if( eType==FTS5_STRING && pNear==0 ) return 0;
    if( eType!=FTS5_STRING && pLeft==0 ) return pRight;
    if( eType!=FTS5_STRING && pRight==0 ) return pLeft;

    if( eType==FTS5_NOT ){
      nChild = 2;
    }else if( eType==FTS5_AND || eType==FTS5_OR ){
      nChild = 2;
      if( pLeft->eType==eType ) nChild += pLeft->nChild-1;
      if( pRight->eType==eType ) nChild += pRight->nChild-1;
    }

    nByte = sizeof(Fts5ExprNode) + sizeof(Fts5ExprNode*)*nChild;
    pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte);

    if( pRet ){
      pRet->eType = eType;


      pRet->pNear = pNear;
      if( eType==FTS5_STRING ){
        int iPhrase;
        for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){
          pNear->apPhrase[iPhrase]->pNode = pRet;
        }
      }else{
        fts5ExprAddChildren(pRet, pLeft);
        fts5ExprAddChildren(pRet, pRight);
      }
    }
  }

  if( pRet==0 ){
    assert( pParse->rc!=SQLITE_OK );
    sqlite3Fts5ParseNodeFree(pLeft);

      if( zRet ) zRet = fts5PrintfAppend(zRet, "}");
      if( zRet==0 ) return 0;
    }

    if( zRet==0 ) return 0;

  }else{
    char const *zOp = 0;
    int i;

    switch( pExpr->eType ){
      case FTS5_AND: zOp = "AND"; break;
      case FTS5_NOT: zOp = "NOT"; break;
      default: 
        assert( pExpr->eType==FTS5_OR );
        zOp = "OR"; 
        break;
    }

    zRet = sqlite3_mprintf("%s", zOp);
    for(i=0; zRet && i<pExpr->nChild; i++){
      char *z = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->apChild[i]);
      if( !z ){
        sqlite3_free(zRet);
        zRet = 0;
      }else{
        zRet = fts5PrintfAppend(zRet, " [%z]", z);
      }


    }
  }

  return zRet;
}

static char *fts5ExprPrint(Fts5Config *pConfig, Fts5ExprNode *pExpr){
  char *zRet = 0;

    if( pNear->nPhrase>1 ){
      zRet = fts5PrintfAppend(zRet, ", %d)", pNear->nNear);
      if( zRet==0 ) return 0;
    }

  }else{
    char const *zOp = 0;
    int i;

    switch( pExpr->eType ){
      case FTS5_AND: zOp = " AND "; break;
      case FTS5_NOT: zOp = " NOT "; break;
      default:  
        assert( pExpr->eType==FTS5_OR );
        zOp = " OR "; 
        break;
    }

    for(i=0; i<pExpr->nChild; i++){
      char *z = fts5ExprPrint(pConfig, pExpr->apChild[i]);
      if( z==0 ){
        sqlite3_free(zRet);
        zRet = 0;
      }else{
        int b = (pExpr->apChild[i]->eType!=FTS5_STRING);
        zRet = fts5PrintfAppend(zRet, "%s%s%z%s", 

            (i==0 ? "" : zOp),
            (b?"(":""), z, (b?")":"")
        );
      }
      if( zRet==0 ) break;

    }
  }

  return zRet;
}

/*
** The implementation of user-defined scalar functions fts5_expr() (bTcl==0)

  return $res
}

#-------------------------------------------------------------------------
# Logical operators used by the commands returned by fts5_tcl_expr().
#
proc AND {args} {
  foreach a $args {
    if {[llength $a]==0} { return [list] }
  }
  sort_poslist [concat {*}$args]
}
proc OR {args} {
  sort_poslist [concat {*}$args]
}
proc NOT {a b} {
  if {[llength $b]>0} { return [list] }
  return $a
}

  5  {one AND two}                   {"one" AND "two"}
  6  {one+two}                       {"one" + "two"}
  7  {one AND two OR three}          {("one" AND "two") OR "three"}
  8  {one OR two AND three}          {"one" OR ("two" AND "three")}
  9  {NEAR(one two)}                 {NEAR("one" "two", 10)}
  10 {NEAR("one three"* two, 5)}     {NEAR("one" + "three" * "two", 5)}
  11 {a OR b NOT c}                  {"a" OR ("b" NOT "c")}
  12 "\x20one\x20two\x20three"       {"one" AND "two" AND "three"}
  13 "\x09one\x0Atwo\x0Dthree"       {"one" AND "two" AND "three"}
  14 {"abc""def"}                    {"abc" + "def"}
} {
  do_execsql_test 1.$tn {SELECT fts5_expr($expr)} [list $res]
}

foreach {tn expr res} {
  1 {c1:abc}                           

#-------------------------------------------------------------------------
# OOM in fts5_expr() SQL function.
#
do_faultsim_test 10.1 -faults oom-t* -body {
  db one { SELECT fts5_expr('a AND b NEAR(a b)') }
} -test {
  faultsim_test_result {0 {"a" AND "b" AND NEAR("a" "b", 10)}} 
}

do_faultsim_test 10.2 -faults oom-t* -body {
  db one { SELECT fts5_expr_tcl('x:"a b c" AND b NEAR(a b)', 'ns', 'x') }
} -test {
  set res {AND [ns -col 0 -- {a b c}] [ns -- {b}] [ns -near 10 -- {a} {b}]}
  faultsim_test_result [list 0 $res]
}

do_faultsim_test 10.3 -faults oom-t* -body {
  db one { SELECT fts5_expr('x:a', 'x') }
} -test {
  faultsim_test_result {0 {x : "a"}}