SQLite

Fts5ExprPhrase *sqlite3Fts5ParseTerm(
  Fts5Parse *pParse, 
  Fts5ExprPhrase *pPhrase, 
  Fts5Token *pToken,
  int bPrefix
);

void sqlite3Fts5ParseSetCaret(Fts5ExprPhrase*);

Fts5ExprNearset *sqlite3Fts5ParseNearset(
  Fts5Parse*, 
  Fts5ExprNearset*,
  Fts5ExprPhrase* 
);

#define fts5ExprNodeNext(a,b,c,d) (b)->xNext((a), (b), (c), (d))

/*
** An instance of the following structure represents a single search term
** or term prefix.
*/
struct Fts5ExprTerm {
  u8 bPrefix;                     /* True for a prefix term */
  u8 bFirst;                      /* True if token must be first in column */
  char *zTerm;                    /* nul-terminated term */
  Fts5IndexIter *pIter;           /* Iterator for this term */
  Fts5ExprTerm *pSynonym;         /* Pointer to first in list of synonyms */
};

/*
** A phrase. One or more terms that must appear in a contiguous sequence

    case '{':  tok = FTS5_LCP;   break;
    case '}':  tok = FTS5_RCP;   break;
    case ':':  tok = FTS5_COLON; break;
    case ',':  tok = FTS5_COMMA; break;
    case '+':  tok = FTS5_PLUS;  break;
    case '*':  tok = FTS5_STAR;  break;
    case '-':  tok = FTS5_MINUS; break;
    case '^':  tok = FTS5_CARET; break;
    case '\0': tok = FTS5_EOF;   break;

    case '"': {
      const char *z2;
      tok = FTS5_STRING;

      for(z2=&z[1]; 1; z2++){

  int *pbMatch                    /* OUT: Set to true if really a match */
){
  Fts5PoslistWriter writer = {0};
  Fts5PoslistReader aStatic[4];
  Fts5PoslistReader *aIter = aStatic;
  int i;
  int rc = SQLITE_OK;
  int bFirst = pPhrase->aTerm[0].bFirst;
  
  fts5BufferZero(&pPhrase->poslist);

  /* If the aStatic[] array is not large enough, allocate a large array
  ** using sqlite3_malloc(). This approach could be improved upon. */
  if( pPhrase->nTerm>ArraySize(aStatic) ){
    int nByte = sizeof(Fts5PoslistReader) * pPhrase->nTerm;

          }
          if( pPos->iPos>iAdj ) iPos = pPos->iPos-i;
        }
      }
    }while( bMatch==0 );

    /* Append position iPos to the output */
    if( bFirst==0 || FTS5_POS2OFFSET(iPos)==0 ){
      rc = sqlite3Fts5PoslistWriterAppend(&pPhrase->poslist, &writer, iPos);
      if( rc!=SQLITE_OK ) goto ismatch_out;
    }

    for(i=0; i<pPhrase->nTerm; i++){
      if( sqlite3Fts5PoslistReaderNext(&aIter[i]) ) goto ismatch_out;
    }
  }

 ismatch_out:

    int i;

    /* Check that each phrase in the nearset matches the current row.
    ** Populate the pPhrase->poslist buffers at the same time. If any
    ** phrase is not a match, break out of the loop early.  */
    for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      if( pPhrase->nTerm>1 || pPhrase->aTerm[0].pSynonym 
       || pNear->pColset || pPhrase->aTerm[0].bFirst
      ){
        int bMatch = 0;
        rc = fts5ExprPhraseIsMatch(pNode, pPhrase, &bMatch);
        if( bMatch==0 ) break;
      }else{
        Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
        fts5BufferSet(&rc, &pPhrase->poslist, pIter->nData, pIter->pData);
      }

  int bMatch;                     /* True if all terms are at the same rowid */
  const int bDesc = pExpr->bDesc;

  /* Check that this node should not be FTS5_TERM */
  assert( pNear->nPhrase>1 
       || pNear->apPhrase[0]->nTerm>1 
       || pNear->apPhrase[0]->aTerm[0].pSynonym
       || pNear->apPhrase[0]->aTerm[0].bFirst
  );

  /* Initialize iLast, the "lastest" rowid any iterator points to. If the
  ** iterator skips through rowids in the default ascending order, this means
  ** the maximum rowid. Or, if the iterator is "ORDER BY rowid DESC", then it
  ** means the minimum rowid.  */
  if( pLeft->aTerm[0].pSynonym ){

        sqlite3_free(pSyn);
      }
    }
    if( pPhrase->poslist.nSpace>0 ) fts5BufferFree(&pPhrase->poslist);
    sqlite3_free(pPhrase);
  }
}

/*
** Set the "bFirst" flag on the first token of the phrase passed as the
** only argument.
*/
void sqlite3Fts5ParseSetCaret(Fts5ExprPhrase *pPhrase){
  if( pPhrase && pPhrase->nTerm ){
    pPhrase->aTerm[0].bFirst = 1;
  }
}

/*
** If argument pNear is NULL, then a new Fts5ExprNearset object is allocated
** and populated with pPhrase. Or, if pNear is not NULL, phrase pPhrase is
** appended to it and the results returned.
**
** If an OOM error occurs, both the pNear and pPhrase objects are freed and

        const char *zTerm = p->zTerm;
        rc = fts5ParseTokenize((void*)&sCtx, tflags, zTerm, (int)strlen(zTerm),
            0, 0);
        tflags = FTS5_TOKEN_COLOCATED;
      }
      if( rc==SQLITE_OK ){
        sCtx.pPhrase->aTerm[i].bPrefix = pOrig->aTerm[i].bPrefix;
        sCtx.pPhrase->aTerm[i].bFirst = pOrig->aTerm[i].bFirst;
      }
    }
  }else{
    /* This happens when parsing a token or quoted phrase that contains
    ** no token characters at all. (e.g ... MATCH '""'). */
    sCtx.pPhrase = sqlite3Fts5MallocZero(&rc, sizeof(Fts5ExprPhrase));
  }

  if( rc==SQLITE_OK ){
    /* All the allocations succeeded. Put the expression object together. */
    pNew->pIndex = pExpr->pIndex;
    pNew->pConfig = pExpr->pConfig;
    pNew->nPhrase = 1;
    pNew->apExprPhrase[0] = sCtx.pPhrase;
    pNew->pRoot->pNear->apPhrase[0] = sCtx.pPhrase;
    pNew->pRoot->pNear->nPhrase = 1;
    sCtx.pPhrase->pNode = pNew->pRoot;

    if( pOrig->nTerm==1 
     && pOrig->aTerm[0].pSynonym==0 
     && pOrig->aTerm[0].bFirst==0 
    ){
      pNew->pRoot->eType = FTS5_TERM;
      pNew->pRoot->xNext = fts5ExprNodeNext_TERM;
    }else{
      pNew->pRoot->eType = FTS5_STRING;
      pNew->pRoot->xNext = fts5ExprNodeNext_STRING;
    }
  }else{

static void fts5ExprAssignXNext(Fts5ExprNode *pNode){
  switch( pNode->eType ){
    case FTS5_STRING: {
      Fts5ExprNearset *pNear = pNode->pNear;
      if( pNear->nPhrase==1 && pNear->apPhrase[0]->nTerm==1 
       && pNear->apPhrase[0]->aTerm[0].pSynonym==0
       && pNear->apPhrase[0]->aTerm[0].bFirst==0
      ){
        pNode->eType = FTS5_TERM;
        pNode->xNext = fts5ExprNodeNext_TERM;
      }else{
        pNode->xNext = fts5ExprNodeNext_STRING;
      }
      break;

          pNear->apPhrase[iPhrase]->pNode = pRet;
          if( pNear->apPhrase[iPhrase]->nTerm==0 ){
            pRet->xNext = 0;
            pRet->eType = FTS5_EOF;
          }
        }

        if( pParse->pConfig->eDetail!=FTS5_DETAIL_FULL ){
          Fts5ExprPhrase *pPhrase = pNear->apPhrase[0];
          if( pNear->nPhrase!=1 
           || pPhrase->nTerm>1
           || (pPhrase->nTerm>0 && pPhrase->aTerm[0].bFirst)
          ){
            assert( pParse->rc==SQLITE_OK );
            pParse->rc = SQLITE_ERROR;
            assert( pParse->zErr==0 );
            pParse->zErr = sqlite3_mprintf(
                "fts5: %s queries are not supported (detail!=full)", 
                pNear->nPhrase==1 ? "phrase": "NEAR"
                );
            sqlite3_free(pRet);
            pRet = 0;
          }
        }
      }else{
        fts5ExprAddChildren(pRet, pLeft);
        fts5ExprAddChildren(pRet, pRight);
      }
    }
  }

%type nearset     {Fts5ExprNearset*}
%type nearphrases {Fts5ExprNearset*}
%destructor nearset { sqlite3Fts5ParseNearsetFree($$); }
%destructor nearphrases { sqlite3Fts5ParseNearsetFree($$); }

nearset(A) ::= phrase(Y). { A = sqlite3Fts5ParseNearset(pParse, 0, Y); }
nearset(A) ::= CARET phrase(Y). { 
  sqlite3Fts5ParseSetCaret(Y);
  A = sqlite3Fts5ParseNearset(pParse, 0, Y); 
}
nearset(A) ::= STRING(X) LP nearphrases(Y) neardist_opt(Z) RP. {
  sqlite3Fts5ParseNear(pParse, &X);
  sqlite3Fts5ParseSetDistance(pParse, Y, &Z);
  A = Y;
}

nearphrases(A) ::= phrase(X). { 

  A = sqlite3Fts5ParseTerm(pParse, 0, &Y, Z);
}

/*
** Optional "*" character.
*/
%type star_opt {int}

star_opt(A) ::= STAR. { A = 1; }
star_opt(A) ::= . { A = 0; }

}

do_faultsim_test 4.2 -faults oom* -body {
  execsql { SELECT rowid FROM t1('{a b c} : (a AND d)') }
} -test {
  faultsim_test_result {0 {2 3}}
}

#-------------------------------------------------------------------------
# Test OOM injection while parsing a CARET expression
#
reset_db
do_execsql_test 5.0 {
  CREATE VIRTUAL TABLE t1 USING fts5(a);
  INSERT INTO t1 VALUES('a b c d');  -- 1
  INSERT INTO t1 VALUES('d a b c');  -- 2
  INSERT INTO t1 VALUES('c d a b');  -- 3
  INSERT INTO t1 VALUES('b c d a');  -- 4
}
do_faultsim_test 5.1 -faults oom* -body {
  execsql { SELECT rowid FROM t1('^a OR ^b') }
} -test {
  faultsim_test_result {0 {1 4}}
}


finish_test

# 2017 November 25
#
# 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.
#
#***********************************************************************

source [file join [file dirname [info script]] fts5_common.tcl]
set testprefix fts5first

ifcapable !fts5 {
  finish_test
  return
}


do_execsql_test 1.0 {
  CREATE VIRTUAL TABLE x1 USING fts5(a, b);
}

foreach {tn expr ok} {
  1 {^abc}           1
  2 {^abc + def}     1
  3 {^ "abc def"}    1
  4 {^"abc def"}     1
  5 {abc ^def}       1
  6 {abc + ^def}     0
  7 {abc ^+ def}     0
  8 {"^abc"}         1
  9 {NEAR(^abc def)} 0
} {
  set res(0) {/1 {fts5: syntax error near .*}/}
  set res(1) {0 {}}

  do_catchsql_test 1.$tn { SELECT * FROM x1($expr) } $res($ok)
}

#-------------------------------------------------------------------------
# 
do_execsql_test 2.0 {
  INSERT INTO x1 VALUES('a b c', 'b c a');
}

foreach {tn expr match} {
  1 {^a} 1
  2 {^b} 1
  3 {^c} 0
  4 {^a + b} 1
  5 {^b + c} 1
  6 {^c + a} 0
  7 {^"c a"} 0
  8 {a:^a} 1
  9 {a:^b} 0
  10 {a:^"a b"} 1
} {
  do_execsql_test 2.$tn { SELECT EXISTS (SELECT rowid FROM x1($expr)) } $match
}

#-------------------------------------------------------------------------
# 
do_execsql_test 3.0 {
  DELETE FROM x1;
  INSERT INTO x1 VALUES('b a', 'c a');
  INSERT INTO x1 VALUES('a a', 'c c');
  INSERT INTO x1 VALUES('a b', 'a a');
}
fts5_aux_test_functions db

foreach {tn expr expect} {
  1 {^a} {{2 1}}
  2 {^c AND ^b} {{0 2} {1 0}}
} {
  do_execsql_test 3.$tn {
    SELECT fts5_test_queryphrase(x1) FROM x1($expr) LIMIT 1
  } [list $expect]
}

#-------------------------------------------------------------------------
# 
do_execsql_test 3.1 {
  CREATE VIRTUAL TABLE x2 USING fts5(a, b, c, detail=column);
}

do_catchsql_test 3.2 {
  SELECT * FROM x2('a + b');
} {1 {fts5: phrase queries are not supported (detail!=full)}}

do_catchsql_test 3.3 {
  SELECT * FROM x2('^a');
} {1 {fts5: phrase queries are not supported (detail!=full)}}
finish_test