/ Check-in [11c2d468]
Login

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

Overview
Comment:Add pseudo-random tests of the fts3 expression parser. Revise the fix in (6091). (CVS 6092)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 11c2d4686197fb3f0d601651d5bbb3492af8f0dd
User & Date: danielk1977 2009-01-01 07:08:55
Context
2009-01-01
07:42
Add a couple of extra tests for the fts3 expression parser to improve mcdc coverage. (CVS 6093) check-in: 13146b34 user: danielk1977 tags: trunk
07:08
Add pseudo-random tests of the fts3 expression parser. Revise the fix in (6091). (CVS 6092) check-in: 11c2d468 user: danielk1977 tags: trunk
04:19
Fix a bug parsing "<expr> AND (abc NEAR def)" in fts3_expr.c. (CVS 6091) check-in: d1a6a2ed user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

Changes to ext/fts3/fts3_expr.c.

   528    528             pNot->pRight = pNotBranch;
   529    529           }
   530    530           pNotBranch = pNot;
   531    531         }else{
   532    532           int eType = p->eType;
   533    533           assert( eType!=FTSQUERY_PHRASE || !p->pPhrase->isNot );
   534    534           isPhrase = (eType==FTSQUERY_PHRASE || p->pLeft);
          535  +
          536  +        /* The isRequirePhrase variable is set to true if a phrase or
          537  +        ** an expression contained in parenthesis is required. If a
          538  +        ** binary operator (AND, OR, NOT or NEAR) is encounted when
          539  +        ** isRequirePhrase is set, this is a syntax error.
          540  +        */
   535    541           if( !isPhrase && isRequirePhrase ){
   536    542             sqlite3Fts3ExprFree(p);
   537    543             rc = SQLITE_ERROR;
   538    544             goto exprparse_out;
   539    545           }
   540    546     
   541    547           if( isPhrase && !isRequirePhrase ){
................................................................................
   550    556             }
   551    557             memset(pAnd, 0, sizeof(Fts3Expr));
   552    558             pAnd->eType = FTSQUERY_AND;
   553    559             insertBinaryOperator(&pRet, pPrev, pAnd);
   554    560             pPrev = pAnd;
   555    561           }
   556    562   
   557         -        if( pPrev && (
   558         -            (pPrev->eType==FTSQUERY_NEAR && eType!=FTSQUERY_PHRASE)
   559         -         || (eType==FTSQUERY_NEAR && pPrev->eType!=FTSQUERY_PHRASE && !isPhrase)
   560         -        )){
   561         -          /* This is an attempt to do "phrase NEAR (bracketed expression)"
   562         -          ** or "(bracketed expression) NEAR phrase", both of which are
   563         -          ** illegal. Return an error.
          563  +        /* This test catches attempts to make either operand of a NEAR
          564  +        ** operator something other than a phrase. For example, either of
          565  +        ** the following:
          566  +        **
          567  +        **    (bracketed expression) NEAR phrase
          568  +        **    phrase NEAR (bracketed expression)
          569  +        **
          570  +        ** Return an error in either case.
   564    571             */
          572  +        if( pPrev && (
          573  +            (eType==FTSQUERY_NEAR && !isPhrase && pPrev->eType!=FTSQUERY_PHRASE)
          574  +         || (eType!=FTSQUERY_PHRASE && isPhrase && pPrev->eType==FTSQUERY_NEAR)
          575  +        )){
   565    576             sqlite3Fts3ExprFree(p);
   566    577             rc = SQLITE_ERROR;
   567    578             goto exprparse_out;
   568    579           }
   569    580     
   570    581           if( isPhrase ){
   571    582             if( pRet ){

Changes to test/fts3expr.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #*************************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this script is testing the FTS3 module.
    13     13   #
    14         -# $Id: fts3expr.test,v 1.2 2009/01/01 04:19:51 danielk1977 Exp $
           14  +# $Id: fts3expr.test,v 1.3 2009/01/01 07:08:55 danielk1977 Exp $
    15     15   #
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   # If SQLITE_ENABLE_FTS3 is defined, omit this file.
    21     21   ifcapable !fts3 {
................................................................................
   118    118   do_test fts3expr-3.4 {
   119    119     test_fts3expr2 "(((ab OR cd)))"
   120    120   } {OR ab cd}
   121    121   
   122    122   do_test fts3expr-3.5 {
   123    123     test_fts3expr2 "one AND (two NEAR three)"
   124    124   } {AND one {NEAR/10 two three}}
          125  +do_test fts3expr-3.6 {
          126  +  test_fts3expr2 "one (two NEAR three)"
          127  +} {AND one {NEAR/10 two three}}
          128  +do_test fts3expr-3.7 {
          129  +  test_fts3expr2 "(two NEAR three) one"
          130  +} {AND {NEAR/10 two three} one}
          131  +do_test fts3expr-3.8 {
          132  +  test_fts3expr2 "(two NEAR three) AND one"
          133  +} {AND {NEAR/10 two three} one}
          134  +do_test fts3expr-3.9 {
          135  +  test_fts3expr2 "(two NEAR three) (four five)"
          136  +} {AND {NEAR/10 two three} {AND four five}}
          137  +do_test fts3expr-3.10 {
          138  +  test_fts3expr2 "(two NEAR three) AND (four five)"
          139  +} {AND {NEAR/10 two three} {AND four five}}
          140  +do_test fts3expr-3.11 {
          141  +  test_fts3expr2 "(two NEAR three) (four NEAR five)"
          142  +} {AND {NEAR/10 two three} {NEAR/10 four five}}
          143  +do_test fts3expr-3.12 {
          144  +  test_fts3expr2 "(two NEAR three) OR (four NEAR five)"
          145  +} {OR {NEAR/10 two three} {NEAR/10 four five}}
          146  +
   125    147   
   126    148   #------------------------------------------------------------------------
   127    149   # The following tests, fts3expr-4.*, test the parsers response to syntax
   128    150   # errors in query expressions. This is done using a real fts3 table and
   129    151   # MATCH clauses, not the parser test interface.
   130    152   # 
   131    153   do_test fts3expr-4.1 {

Added test/fts3expr2.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 FTS3 module syntax parser.
           13  +#
           14  +# $Id: fts3expr2.test,v 1.1 2009/01/01 07:08:55 danielk1977 Exp $
           15  +#
           16  +
           17  +set testdir [file dirname $argv0]
           18  +source $testdir/tester.tcl
           19  +
           20  +# If SQLITE_ENABLE_FTS3 is defined, omit this file.
           21  +ifcapable !fts3 {
           22  +  finish_test
           23  +  return
           24  +}
           25  +
           26  +# Test overview:
           27  +# 
           28  +#   The tests in this file are pseudo-randomly generated. They test
           29  +#   the fts3 match expression parser via the test interface
           30  +#   SQL function "fts3_exprtest" (see comments in fts3_expr.c).
           31  +#
           32  +#   Each test case works as follows:
           33  +#   
           34  +#     1. A random expression tree is generated using proc [random_expr_tree].
           35  +#     2. The expression tree is converted to the text of an equivalent
           36  +#        fts3 expression using proc [tree_to_expr].
           37  +#     3. The test SQL function "fts3_exprtest" is used to parse the 
           38  +#        expression text generated in step (2), returning a parsed expression
           39  +#        tree.
           40  +#     4. Test that the tree returned in step (3) matches that generated in 
           41  +#        step (1).
           42  +#
           43  +#   In step (2), 4 different fts3 expressions are created from each 
           44  +#   expression tree by varying the following boolean properties:
           45  +#
           46  +#     * Whether or not superflous parenthesis are included. i.e. if
           47  +#       "a OR b AND (c OR d)" or "a OR (b AND (c OR d))" is generated.
           48  +#
           49  +#     * Whether or not explict AND operators are used. i.e. if
           50  +#     "a OR b AND c" or "a OR b c" is generated.
           51  +#
           52  +
           53  +set sqlite_fts3_enable_parentheses 1
           54  +
           55  +proc strip_phrase_data {L} {
           56  +  if {[lindex $L 0] eq "PHRASE"} {
           57  +    return [list P [lrange $L 3 end]]
           58  +  }
           59  +  return [list \
           60  +    [lindex $L 0] \
           61  +    [strip_phrase_data [lindex $L 1]] \
           62  +    [strip_phrase_data [lindex $L 2]] \
           63  +  ]
           64  +}
           65  +proc test_fts3expr2 {expr} {
           66  +  strip_phrase_data [
           67  +    db one {SELECT fts3_exprtest('simple', $expr, 'a', 'b', 'c')}
           68  +  ]
           69  +}
           70  +
           71  +proc rnd {nMax} { expr {int(rand()*$nMax)} }
           72  +
           73  +proc random_phrase {} {
           74  +  set phrases [list one two three four "one two" "three four"]
           75  +  list P [lindex $phrases [rnd [llength $phrases]]]
           76  +}
           77  +
           78  +# Generate and return a pseudo-random expression tree. Using the same 
           79  +# format returned by the [test_fts3expr2] proc.
           80  +#
           81  +proc random_expr_tree {iHeight} {
           82  +  if {$iHeight==0 || [rnd 3]==0} {
           83  +    return [random_phrase]
           84  +  }
           85  +
           86  +  set operators [list NEAR NOT AND OR]
           87  +  set op [lindex $operators [rnd 4]]
           88  +
           89  +  if {$op eq "NEAR"} {
           90  +    set iDistance [rnd 15]
           91  +    return [list $op/$iDistance [random_phrase] [random_phrase]]
           92  +  }
           93  +
           94  +  set iNH [expr {$iHeight - 1}]
           95  +  return [list $op [random_expr_tree $iNH] [random_expr_tree $iNH]]
           96  +}
           97  +
           98  +# Given an expression tree, generate a corresponding expression.
           99  +#
          100  +proc tree_to_expr {tree all_brackets implicit_and} {
          101  +  set prec(NOT) 2
          102  +  set prec(AND) 3
          103  +  set prec()    3
          104  +  set prec(OR)  4
          105  +
          106  +  set op [lindex $tree 0]
          107  +
          108  +  if {$op eq "P"} {
          109  +    set phrase [lindex $tree 1]
          110  +    if {[llength $phrase]>1} {
          111  +      return "\"$phrase\""
          112  +    } else {
          113  +      return $phrase
          114  +    }
          115  +  }
          116  +
          117  +  if {$op eq "NEAR/10"} {
          118  +    set op "NEAR"
          119  +  }
          120  +  if {$op eq "AND" && $implicit_and} {
          121  +    set op ""
          122  +  }
          123  +
          124  +  set lhs [lindex $tree 1]
          125  +  set rhs [lindex $tree 2]
          126  +  set zLeft  [tree_to_expr $lhs $all_brackets $implicit_and]
          127  +  set zRight [tree_to_expr $rhs $all_brackets $implicit_and]
          128  +
          129  +  set iPrec 5
          130  +  set iLeftPrec 0
          131  +  set iRightPrec 0
          132  +
          133  +  catch {set iPrec      $prec($op)}
          134  +  catch {set iLeftPrec  $prec([lindex $lhs 0])}
          135  +  catch {set iRightPrec $prec([lindex $rhs 0])}
          136  +
          137  +  if {$iLeftPrec > $iPrec || $all_brackets} {
          138  +    set zLeft "($zLeft)"
          139  +  } 
          140  +  if {$iRightPrec >= $iPrec || $all_brackets} {
          141  +    set zRight "($zRight)"
          142  +  } 
          143  +
          144  +  return "$zLeft $op $zRight"
          145  +}
          146  +
          147  +proc do_exprparse_test {name expr tree} {
          148  +  uplevel do_test $name [list "test_fts3expr2 {$expr}"] [list $tree]
          149  +}
          150  +
          151  +for {set iTest 1} {$iTest<500} {incr iTest} {
          152  +  set t [random_expr_tree 4]
          153  +
          154  +  set e1 [tree_to_expr $t 0 0]
          155  +  set e2 [tree_to_expr $t 0 1]
          156  +  set e3 [tree_to_expr $t 1 0]
          157  +  set e4 [tree_to_expr $t 1 1]
          158  +
          159  +  do_exprparse_test fts3expr2-$iTest.1 $e1 $t
          160  +  do_exprparse_test fts3expr2-$iTest.2 $e2 $t
          161  +  do_exprparse_test fts3expr2-$iTest.3 $e3 $t
          162  +  do_exprparse_test fts3expr2-$iTest.4 $e4 $t
          163  +}
          164  +
          165  +set sqlite_fts3_enable_parentheses 0
          166  +finish_test
          167  +