/ Hex Artifact Content
Login

Artifact c4d4a7d6327418428c96e0a3a1137c251b8dfbf8:


0000: 23 20 32 30 30 39 20 4a 61 6e 75 61 72 79 20 31  # 2009 January 1
0010: 0a 23 0a 23 20 54 68 65 20 61 75 74 68 6f 72 20  .#.# The author 
0020: 64 69 73 63 6c 61 69 6d 73 20 63 6f 70 79 72 69  disclaims copyri
0030: 67 68 74 20 74 6f 20 74 68 69 73 20 73 6f 75 72  ght to this sour
0040: 63 65 20 63 6f 64 65 2e 20 20 49 6e 20 70 6c 61  ce code.  In pla
0050: 63 65 20 6f 66 0a 23 20 61 20 6c 65 67 61 6c 20  ce of.# a legal 
0060: 6e 6f 74 69 63 65 2c 20 68 65 72 65 20 69 73 20  notice, here is 
0070: 61 20 62 6c 65 73 73 69 6e 67 3a 0a 23 0a 23 20  a blessing:.#.# 
0080: 20 20 20 4d 61 79 20 79 6f 75 20 64 6f 20 67 6f     May you do go
0090: 6f 64 20 61 6e 64 20 6e 6f 74 20 65 76 69 6c 2e  od and not evil.
00a0: 0a 23 20 20 20 20 4d 61 79 20 79 6f 75 20 66 69  .#    May you fi
00b0: 6e 64 20 66 6f 72 67 69 76 65 6e 65 73 73 20 66  nd forgiveness f
00c0: 6f 72 20 79 6f 75 72 73 65 6c 66 20 61 6e 64 20  or yourself and 
00d0: 66 6f 72 67 69 76 65 20 6f 74 68 65 72 73 2e 0a  forgive others..
00e0: 23 20 20 20 20 4d 61 79 20 79 6f 75 20 73 68 61  #    May you sha
00f0: 72 65 20 66 72 65 65 6c 79 2c 20 6e 65 76 65 72  re freely, never
0100: 20 74 61 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61   taking more tha
0110: 6e 20 79 6f 75 20 67 69 76 65 2e 0a 23 0a 23 2a  n you give..#.#*
0120: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 0a 23 20 54 68 69 73 20  ********.# This 
0170: 66 69 6c 65 20 69 6d 70 6c 65 6d 65 6e 74 73 20  file implements 
0180: 72 65 67 72 65 73 73 69 6f 6e 20 74 65 73 74 73  regression tests
0190: 20 66 6f 72 20 53 51 4c 69 74 65 20 6c 69 62 72   for SQLite libr
01a0: 61 72 79 2e 20 20 54 68 65 0a 23 20 66 6f 63 75  ary.  The.# focu
01b0: 73 20 6f 66 20 74 68 69 73 20 73 63 72 69 70 74  s of this script
01c0: 20 69 73 20 74 65 73 74 69 6e 67 20 74 68 65 20   is testing the 
01d0: 70 61 72 74 20 6f 66 20 74 68 65 20 46 54 53 33  part of the FTS3
01e0: 20 65 78 70 72 65 73 73 69 6f 6e 0a 23 20 70 61   expression.# pa
01f0: 72 73 65 72 20 74 68 61 74 20 72 65 62 61 6c 61  rser that rebala
0200: 6e 63 65 73 20 6c 61 72 67 65 20 65 78 70 72 65  nces large expre
0210: 73 73 69 6f 6e 73 2e 0a 23 0a 23 20 24 49 64 3a  ssions..#.# $Id:
0220: 20 66 74 73 33 65 78 70 72 32 2e 74 65 73 74 2c   fts3expr2.test,
0230: 76 20 31 2e 32 20 32 30 30 39 2f 30 36 2f 30 35  v 1.2 2009/06/05
0240: 20 31 37 3a 30 39 3a 31 32 20 64 72 68 20 45 78   17:09:12 drh Ex
0250: 70 20 24 0a 23 0a 0a 73 65 74 20 74 65 73 74 64  p $.#..set testd
0260: 69 72 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65  ir [file dirname
0270: 20 24 61 72 67 76 30 5d 0a 73 6f 75 72 63 65 20   $argv0].source 
0280: 24 74 65 73 74 64 69 72 2f 74 65 73 74 65 72 2e  $testdir/tester.
0290: 74 63 6c 0a 73 6f 75 72 63 65 20 24 74 65 73 74  tcl.source $test
02a0: 64 69 72 2f 6d 61 6c 6c 6f 63 5f 63 6f 6d 6d 6f  dir/malloc_commo
02b0: 6e 2e 74 63 6c 0a 73 65 74 20 3a 3a 74 65 73 74  n.tcl.set ::test
02c0: 70 72 65 66 69 78 20 66 74 73 33 65 78 70 72 33  prefix fts3expr3
02d0: 0a 0a 23 20 49 66 20 53 51 4c 49 54 45 5f 45 4e  ..# If SQLITE_EN
02e0: 41 42 4c 45 5f 46 54 53 33 20 69 73 20 64 65 66  ABLE_FTS3 is def
02f0: 69 6e 65 64 2c 20 6f 6d 69 74 20 74 68 69 73 20  ined, omit this 
0300: 66 69 6c 65 2e 0a 69 66 63 61 70 61 62 6c 65 20  file..ifcapable 
0310: 21 66 74 73 33 20 7b 0a 20 20 66 69 6e 69 73 68  !fts3 {.  finish
0320: 5f 74 65 73 74 0a 20 20 72 65 74 75 72 6e 0a 7d  _test.  return.}
0330: 0a 0a 73 65 74 20 73 71 6c 69 74 65 5f 66 74 73  ..set sqlite_fts
0340: 33 5f 65 6e 61 62 6c 65 5f 70 61 72 65 6e 74 68  3_enable_parenth
0350: 65 73 65 73 20 31 0a 0a 70 72 6f 63 20 73 74 72  eses 1..proc str
0360: 69 70 5f 70 68 72 61 73 65 5f 64 61 74 61 20 7b  ip_phrase_data {
0370: 4c 7d 20 7b 0a 20 20 69 66 20 7b 5b 6c 69 6e 64  L} {.  if {[lind
0380: 65 78 20 24 4c 20 30 5d 20 65 71 20 22 50 48 52  ex $L 0] eq "PHR
0390: 41 53 45 22 7d 20 7b 0a 20 20 20 20 72 65 74 75  ASE"} {.    retu
03a0: 72 6e 20 5b 6c 69 73 74 20 50 20 5b 6c 72 61 6e  rn [list P [lran
03b0: 67 65 20 24 4c 20 33 20 65 6e 64 5d 5d 0a 20 20  ge $L 3 end]].  
03c0: 7d 0a 20 20 72 65 74 75 72 6e 20 5b 6c 69 73 74  }.  return [list
03d0: 20 5c 0a 20 20 20 20 5b 6c 69 6e 64 65 78 20 24   \.    [lindex $
03e0: 4c 20 30 5d 20 5c 0a 20 20 20 20 5b 73 74 72 69  L 0] \.    [stri
03f0: 70 5f 70 68 72 61 73 65 5f 64 61 74 61 20 5b 6c  p_phrase_data [l
0400: 69 6e 64 65 78 20 24 4c 20 31 5d 5d 20 5c 0a 20  index $L 1]] \. 
0410: 20 20 20 5b 73 74 72 69 70 5f 70 68 72 61 73 65     [strip_phrase
0420: 5f 64 61 74 61 20 5b 6c 69 6e 64 65 78 20 24 4c  _data [lindex $L
0430: 20 32 5d 5d 20 5c 0a 20 20 5d 0a 7d 0a 70 72 6f   2]] \.  ].}.pro
0440: 63 20 74 65 73 74 5f 66 74 73 33 65 78 70 72 32  c test_fts3expr2
0450: 20 7b 65 78 70 72 7d 20 7b 0a 20 20 73 74 72 69   {expr} {.  stri
0460: 70 5f 70 68 72 61 73 65 5f 64 61 74 61 20 5b 0a  p_phrase_data [.
0470: 20 20 20 20 64 62 20 6f 6e 65 20 7b 53 45 4c 45      db one {SELE
0480: 43 54 20 66 74 73 33 5f 65 78 70 72 74 65 73 74  CT fts3_exprtest
0490: 5f 72 65 62 61 6c 61 6e 63 65 28 27 73 69 6d 70  _rebalance('simp
04a0: 6c 65 27 2c 20 24 65 78 70 72 2c 20 27 61 27 2c  le', $expr, 'a',
04b0: 20 27 62 27 2c 20 27 63 27 29 7d 0a 20 20 5d 0a   'b', 'c')}.  ].
04c0: 7d 0a 0a 70 72 6f 63 20 62 61 6c 61 6e 63 65 64  }..proc balanced
04d0: 5f 65 78 70 72 74 72 65 65 5f 73 74 72 75 63 74  _exprtree_struct
04e0: 75 72 65 20 7b 6e 45 6e 74 72 79 7d 20 7b 0a 20  ure {nEntry} {. 
04f0: 20 73 65 74 20 4c 20 5b 6c 69 73 74 5d 0a 20 20   set L [list].  
0500: 66 6f 72 20 7b 73 65 74 20 69 20 31 7d 20 7b 24  for {set i 1} {$
0510: 69 20 3c 3d 20 24 6e 45 6e 74 72 79 7d 20 7b 69  i <= $nEntry} {i
0520: 6e 63 72 20 69 7d 20 7b 0a 20 20 20 20 6c 61 70  ncr i} {.    lap
0530: 70 65 6e 64 20 4c 20 78 78 78 0a 20 20 7d 0a 20  pend L xxx.  }. 
0540: 20 77 68 69 6c 65 20 7b 5b 6c 6c 65 6e 67 74 68   while {[llength
0550: 20 24 4c 5d 20 3e 20 31 7d 20 7b 0a 20 20 20 20   $L] > 1} {.    
0560: 73 65 74 20 4e 20 5b 6c 69 73 74 5d 0a 20 20 20  set N [list].   
0570: 20 69 66 20 7b 5b 6c 6c 65 6e 67 74 68 20 24 4c   if {[llength $L
0580: 5d 20 25 20 32 7d 20 7b 0a 20 20 20 20 20 20 66  ] % 2} {.      f
0590: 6f 72 65 61 63 68 20 7b 61 20 62 7d 20 5b 6c 72  oreach {a b} [lr
05a0: 61 6e 67 65 20 24 4c 20 30 20 65 6e 64 2d 31 5d  ange $L 0 end-1]
05b0: 20 7b 20 6c 61 70 70 65 6e 64 20 4e 20 5b 6c 69   { lappend N [li
05c0: 73 74 20 41 4e 44 20 24 61 20 24 62 5d 20 7d 0a  st AND $a $b] }.
05d0: 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20 4e 20        lappend N 
05e0: 5b 6c 69 6e 64 65 78 20 24 4c 20 65 6e 64 5d 0a  [lindex $L end].
05f0: 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 20 20 20      } else {.   
0600: 20 20 20 66 6f 72 65 61 63 68 20 7b 61 20 62 7d     foreach {a b}
0610: 20 24 4c 20 7b 20 6c 61 70 70 65 6e 64 20 4e 20   $L { lappend N 
0620: 5b 6c 69 73 74 20 41 4e 44 20 24 61 20 24 62 5d  [list AND $a $b]
0630: 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 73 65 74   }.    }.    set
0640: 20 4c 20 24 4e 0a 20 20 7d 0a 20 20 72 65 74 75   L $N.  }.  retu
0650: 72 6e 20 5b 6c 69 6e 64 65 78 20 24 4c 20 30 5d  rn [lindex $L 0]
0660: 0a 7d 0a 0a 70 72 6f 63 20 62 61 6c 61 6e 63 65  .}..proc balance
0670: 64 5f 61 6e 64 5f 74 72 65 65 20 7b 6e 45 6e 74  d_and_tree {nEnt
0680: 72 79 7d 20 7b 0a 20 20 73 65 74 20 71 75 65 72  ry} {.  set quer
0690: 79 20 5b 62 61 6c 61 6e 63 65 64 5f 65 78 70 72  y [balanced_expr
06a0: 74 72 65 65 5f 73 74 72 75 63 74 75 72 65 20 24  tree_structure $
06b0: 6e 45 6e 74 72 79 5d 0a 20 20 69 66 20 7b 24 71  nEntry].  if {$q
06c0: 75 65 72 79 20 3d 3d 20 22 78 78 78 22 7d 20 7b  uery == "xxx"} {
06d0: 0a 20 20 20 20 72 65 74 75 72 6e 20 22 50 20 31  .    return "P 1
06e0: 22 0a 20 20 7d 0a 20 20 66 6f 72 20 7b 73 65 74  ".  }.  for {set
06f0: 20 69 20 31 7d 20 7b 24 69 20 3c 3d 20 24 6e 45   i 1} {$i <= $nE
0700: 6e 74 72 79 7d 20 7b 69 6e 63 72 20 69 7d 20 7b  ntry} {incr i} {
0710: 0a 20 20 20 20 72 65 67 73 75 62 20 78 78 78 20  .    regsub xxx 
0720: 24 71 75 65 72 79 20 22 7b 50 20 24 69 7d 22 20  $query "{P $i}" 
0730: 71 75 65 72 79 0a 20 20 7d 0a 20 20 72 65 74 75  query.  }.  retu
0740: 72 6e 20 24 71 75 65 72 79 0a 7d 0a 0a 70 72 6f  rn $query.}..pro
0750: 63 20 72 61 6e 64 6f 6d 5f 74 72 65 65 5f 73 74  c random_tree_st
0760: 72 75 63 74 75 72 65 20 7b 6e 45 6e 74 72 79 20  ructure {nEntry 
0770: 62 50 61 72 65 6e 20 6f 70 7d 20 7b 0a 20 20 73  bParen op} {.  s
0780: 65 74 20 71 75 65 72 79 20 78 78 78 0a 20 20 66  et query xxx.  f
0790: 6f 72 20 7b 73 65 74 20 69 20 31 7d 20 7b 24 69  or {set i 1} {$i
07a0: 20 3c 20 24 6e 45 6e 74 72 79 7d 20 7b 69 6e 63   < $nEntry} {inc
07b0: 72 20 69 7d 20 7b 0a 20 20 20 20 73 65 74 20 78  r i} {.    set x
07c0: 31 20 5b 65 78 70 72 20 69 6e 74 28 72 61 6e 64  1 [expr int(rand
07d0: 28 29 2a 34 2e 30 29 5d 0a 20 20 20 20 73 65 74  ()*4.0)].    set
07e0: 20 78 32 20 5b 65 78 70 72 20 69 6e 74 28 72 61   x2 [expr int(ra
07f0: 6e 64 28 29 2a 32 2e 30 29 5d 0a 20 20 20 20 69  nd()*2.0)].    i
0800: 66 20 7b 24 78 31 3d 3d 30 20 26 26 20 24 62 50  f {$x1==0 && $bP
0810: 61 72 65 6e 7d 20 7b 0a 20 20 20 20 20 20 73 65  aren} {.      se
0820: 74 20 71 75 65 72 79 20 22 28 24 71 75 65 72 79  t query "($query
0830: 29 22 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 20  )".    }.    if 
0840: 7b 24 78 32 7d 20 7b 0a 20 20 20 20 20 20 73 65  {$x2} {.      se
0850: 74 20 71 75 65 72 79 20 22 78 78 78 20 24 6f 70  t query "xxx $op
0860: 20 24 71 75 65 72 79 22 0a 20 20 20 20 7d 20 65   $query".    } e
0870: 6c 73 65 20 7b 0a 20 20 20 20 20 20 73 65 74 20  lse {.      set 
0880: 71 75 65 72 79 20 22 24 71 75 65 72 79 20 24 6f  query "$query $o
0890: 70 20 78 78 78 22 0a 20 20 20 20 7d 0a 20 20 7d  p xxx".    }.  }
08a0: 0a 20 20 72 65 74 75 72 6e 20 24 71 75 65 72 79  .  return $query
08b0: 0a 7d 0a 0a 70 72 6f 63 20 72 61 6e 64 6f 6d 5f  .}..proc random_
08c0: 61 6e 64 5f 71 75 65 72 79 20 7b 6e 45 6e 74 72  and_query {nEntr
08d0: 79 20 7b 62 50 61 72 65 6e 20 30 7d 7d 20 7b 0a  y {bParen 0}} {.
08e0: 20 20 73 65 74 20 71 75 65 72 79 20 5b 72 61 6e    set query [ran
08f0: 64 6f 6d 5f 74 72 65 65 5f 73 74 72 75 63 74 75  dom_tree_structu
0900: 72 65 20 24 6e 45 6e 74 72 79 20 24 62 50 61 72  re $nEntry $bPar
0910: 65 6e 20 41 4e 44 5d 0a 20 20 66 6f 72 20 7b 73  en AND].  for {s
0920: 65 74 20 69 20 31 7d 20 7b 24 69 20 3c 3d 20 24  et i 1} {$i <= $
0930: 6e 45 6e 74 72 79 7d 20 7b 69 6e 63 72 20 69 7d  nEntry} {incr i}
0940: 20 7b 0a 20 20 20 20 72 65 67 73 75 62 20 78 78   {.    regsub xx
0950: 78 20 24 71 75 65 72 79 20 24 69 20 71 75 65 72  x $query $i quer
0960: 79 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 24  y.  }.  return $
0970: 71 75 65 72 79 0a 7d 0a 0a 70 72 6f 63 20 72 61  query.}..proc ra
0980: 6e 64 6f 6d 5f 6f 72 5f 71 75 65 72 79 20 7b 6e  ndom_or_query {n
0990: 45 6e 74 72 79 7d 20 7b 0a 20 20 73 65 74 20 71  Entry} {.  set q
09a0: 75 65 72 79 20 5b 72 61 6e 64 6f 6d 5f 74 72 65  uery [random_tre
09b0: 65 5f 73 74 72 75 63 74 75 72 65 20 24 6e 45 6e  e_structure $nEn
09c0: 74 72 79 20 31 20 4f 52 5d 0a 20 20 66 6f 72 20  try 1 OR].  for 
09d0: 7b 73 65 74 20 69 20 31 7d 20 7b 24 69 20 3c 3d  {set i 1} {$i <=
09e0: 20 24 6e 45 6e 74 72 79 7d 20 7b 69 6e 63 72 20   $nEntry} {incr 
09f0: 69 7d 20 7b 0a 20 20 20 20 72 65 67 73 75 62 20  i} {.    regsub 
0a00: 78 78 78 20 24 71 75 65 72 79 20 24 69 20 71 75  xxx $query $i qu
0a10: 65 72 79 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e  ery.  }.  return
0a20: 20 24 71 75 65 72 79 0a 7d 0a 0a 70 72 6f 63 20   $query.}..proc 
0a30: 72 61 6e 64 6f 6d 5f 61 6e 64 6f 72 5f 71 75 65  random_andor_que
0a40: 72 79 20 7b 6e 45 6e 74 72 79 7d 20 7b 0a 20 20  ry {nEntry} {.  
0a50: 73 65 74 20 71 75 65 72 79 20 5b 72 61 6e 64 6f  set query [rando
0a60: 6d 5f 74 72 65 65 5f 73 74 72 75 63 74 75 72 65  m_tree_structure
0a70: 20 24 6e 45 6e 74 72 79 20 31 20 41 4e 44 5d 0a   $nEntry 1 AND].
0a80: 20 20 66 6f 72 20 7b 73 65 74 20 69 20 31 7d 20    for {set i 1} 
0a90: 7b 24 69 20 3c 3d 20 24 6e 45 6e 74 72 79 7d 20  {$i <= $nEntry} 
0aa0: 7b 69 6e 63 72 20 69 7d 20 7b 0a 20 20 20 20 72  {incr i} {.    r
0ab0: 65 67 73 75 62 20 78 78 78 20 24 71 75 65 72 79  egsub xxx $query
0ac0: 20 22 28 5b 72 61 6e 64 6f 6d 5f 6f 72 5f 71 75   "([random_or_qu
0ad0: 65 72 79 20 24 6e 45 6e 74 72 79 5d 29 22 20 71  ery $nEntry])" q
0ae0: 75 65 72 79 0a 20 20 7d 0a 20 20 72 65 74 75 72  uery.  }.  retur
0af0: 6e 20 24 71 75 65 72 79 0a 7d 0a 0a 70 72 6f 63  n $query.}..proc
0b00: 20 62 61 6c 61 6e 63 65 64 5f 61 6e 64 6f 72 5f   balanced_andor_
0b10: 74 72 65 65 20 7b 6e 45 6e 74 72 79 7d 20 7b 0a  tree {nEntry} {.
0b20: 20 20 73 65 74 20 74 72 65 65 20 5b 62 61 6c 61    set tree [bala
0b30: 6e 63 65 64 5f 65 78 70 72 74 72 65 65 5f 73 74  nced_exprtree_st
0b40: 72 75 63 74 75 72 65 20 24 6e 45 6e 74 72 79 5d  ructure $nEntry]
0b50: 0a 20 20 73 65 74 20 6e 6f 64 65 20 22 7b 5b 62  .  set node "{[b
0b60: 61 6c 61 6e 63 65 64 5f 61 6e 64 5f 74 72 65 65  alanced_and_tree
0b70: 20 24 6e 45 6e 74 72 79 5d 7d 22 0a 20 20 72 65   $nEntry]}".  re
0b80: 67 73 75 62 20 2d 61 6c 6c 20 41 4e 44 20 24 6e  gsub -all AND $n
0b90: 6f 64 65 20 4f 52 20 6e 6f 64 65 0a 20 20 72 65  ode OR node.  re
0ba0: 67 73 75 62 20 2d 61 6c 6c 20 78 78 78 20 24 74  gsub -all xxx $t
0bb0: 72 65 65 20 24 6e 6f 64 65 20 74 72 65 65 0a 20  ree $node tree. 
0bc0: 20 72 65 74 75 72 6e 20 24 74 72 65 65 0a 7d 0a   return $tree.}.
0bd0: 0a 69 66 20 31 20 7b 0a 0a 23 20 54 65 73 74 20  .if 1 {..# Test 
0be0: 74 68 61 74 20 71 75 65 72 69 65 73 20 6c 69 6b  that queries lik
0bf0: 65 20 22 31 20 41 4e 44 20 32 20 41 4e 44 20 33  e "1 AND 2 AND 3
0c00: 20 41 4e 44 20 34 2e 2e 2e 22 20 61 72 65 20 74   AND 4..." are t
0c10: 72 61 6e 73 66 6f 72 6d 65 64 20 74 6f 20 0a 23  ransformed to .#
0c20: 20 62 61 6c 61 6e 63 65 64 20 74 72 65 65 73 20   balanced trees 
0c30: 62 79 20 46 54 53 2e 0a 23 0a 66 6f 72 20 7b 73  by FTS..#.for {s
0c40: 65 74 20 69 20 31 7d 20 7b 24 69 20 3c 20 31 30  et i 1} {$i < 10
0c50: 30 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20 20  0} {incr i} {.  
0c60: 64 6f 5f 74 65 73 74 20 31 2e 24 69 20 7b 0a 20  do_test 1.$i {. 
0c70: 20 20 20 74 65 73 74 5f 66 74 73 33 65 78 70 72     test_fts3expr
0c80: 32 20 5b 72 61 6e 64 6f 6d 5f 61 6e 64 5f 71 75  2 [random_and_qu
0c90: 65 72 79 20 24 69 5d 0a 20 20 7d 20 5b 62 61 6c  ery $i].  } [bal
0ca0: 61 6e 63 65 64 5f 61 6e 64 5f 74 72 65 65 20 24  anced_and_tree $
0cb0: 69 5d 0a 7d 0a 0a 23 20 53 61 6d 65 20 61 67 61  i].}..# Same aga
0cc0: 69 6e 2c 20 65 78 63 65 70 74 20 77 69 74 68 20  in, except with 
0cd0: 70 61 72 65 6e 74 68 65 73 69 73 20 69 6e 73 65  parenthesis inse
0ce0: 72 74 65 64 20 61 74 20 61 72 62 69 74 72 61 72  rted at arbitrar
0cf0: 79 20 70 6f 69 6e 74 73 2e 0a 23 0a 66 6f 72 20  y points..#.for 
0d00: 7b 73 65 74 20 69 20 31 7d 20 7b 24 69 20 3c 20  {set i 1} {$i < 
0d10: 31 30 30 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a  100} {incr i} {.
0d20: 20 20 64 6f 5f 74 65 73 74 20 32 2e 24 69 20 7b    do_test 2.$i {
0d30: 0a 20 20 20 20 74 65 73 74 5f 66 74 73 33 65 78  .    test_fts3ex
0d40: 70 72 32 20 5b 72 61 6e 64 6f 6d 5f 61 6e 64 5f  pr2 [random_and_
0d50: 71 75 65 72 79 20 24 69 20 31 5d 0a 20 20 7d 20  query $i 1].  } 
0d60: 5b 62 61 6c 61 6e 63 65 64 5f 61 6e 64 5f 74 72  [balanced_and_tr
0d70: 65 65 20 24 69 5d 0a 7d 0a 0a 23 20 4e 6f 77 20  ee $i].}..# Now 
0d80: 61 74 74 65 6d 70 74 20 74 6f 20 62 61 6c 61 6e  attempt to balan
0d90: 63 65 20 74 77 6f 20 41 4e 44 20 74 72 65 65 73  ce two AND trees
0da0: 20 6a 6f 69 6e 65 64 20 62 79 20 61 6e 20 4f 52   joined by an OR
0db0: 2e 0a 23 0a 66 6f 72 20 7b 73 65 74 20 69 20 31  ..#.for {set i 1
0dc0: 7d 20 7b 24 69 20 3c 20 31 30 30 7d 20 7b 69 6e  } {$i < 100} {in
0dd0: 63 72 20 69 7d 20 7b 0a 20 20 64 6f 5f 74 65 73  cr i} {.  do_tes
0de0: 74 20 33 2e 24 69 20 7b 0a 20 20 20 20 74 65 73  t 3.$i {.    tes
0df0: 74 5f 66 74 73 33 65 78 70 72 32 20 22 5b 72 61  t_fts3expr2 "[ra
0e00: 6e 64 6f 6d 5f 61 6e 64 5f 71 75 65 72 79 20 24  ndom_and_query $
0e10: 69 20 31 5d 20 4f 52 20 5b 72 61 6e 64 6f 6d 5f  i 1] OR [random_
0e20: 61 6e 64 5f 71 75 65 72 79 20 24 69 20 31 5d 22  and_query $i 1]"
0e30: 0a 20 20 7d 20 5b 6c 69 73 74 20 4f 52 20 5b 62  .  } [list OR [b
0e40: 61 6c 61 6e 63 65 64 5f 61 6e 64 5f 74 72 65 65  alanced_and_tree
0e50: 20 24 69 5d 20 5b 62 61 6c 61 6e 63 65 64 5f 61   $i] [balanced_a
0e60: 6e 64 5f 74 72 65 65 20 24 69 5d 5d 0a 7d 0a 0a  nd_tree $i]].}..
0e70: 23 20 54 72 79 20 74 72 65 65 73 20 6f 66 20 41  # Try trees of A
0e80: 4e 44 20 6e 6f 64 65 73 20 77 69 74 68 20 6c 65  ND nodes with le
0e90: 61 76 65 73 20 74 68 61 74 20 61 72 65 20 74 68  aves that are th
0ea0: 65 6d 73 65 6c 76 65 73 20 74 72 65 65 73 20 6f  emselves trees o
0eb0: 66 20 4f 52 20 6e 6f 64 65 73 2e 0a 23 0a 66 6f  f OR nodes..#.fo
0ec0: 72 20 7b 73 65 74 20 69 20 32 7d 20 7b 24 69 20  r {set i 2} {$i 
0ed0: 3c 20 36 34 7d 20 7b 69 6e 63 72 20 69 20 34 7d  < 64} {incr i 4}
0ee0: 20 7b 0a 20 20 64 6f 5f 74 65 73 74 20 33 2e 24   {.  do_test 3.$
0ef0: 69 20 7b 0a 20 20 20 20 74 65 73 74 5f 66 74 73  i {.    test_fts
0f00: 33 65 78 70 72 32 20 5b 72 61 6e 64 6f 6d 5f 61  3expr2 [random_a
0f10: 6e 64 6f 72 5f 71 75 65 72 79 20 24 69 5d 0a 20  ndor_query $i]. 
0f20: 20 7d 20 5b 62 61 6c 61 6e 63 65 64 5f 61 6e 64   } [balanced_and
0f30: 6f 72 5f 74 72 65 65 20 24 69 5d 0a 7d 0a 0a 23  or_tree $i].}..#
0f40: 20 54 68 65 73 65 20 65 78 63 65 65 64 20 74 68   These exceed th
0f50: 65 20 64 65 70 74 68 20 6c 69 6d 69 74 2e 20 0a  e depth limit. .
0f60: 23 0a 66 6f 72 20 7b 73 65 74 20 69 20 36 35 7d  #.for {set i 65}
0f70: 20 7b 24 69 20 3c 20 37 30 7d 20 7b 69 6e 63 72   {$i < 70} {incr
0f80: 20 69 7d 20 7b 0a 20 20 64 6f 5f 74 65 73 74 20   i} {.  do_test 
0f90: 33 2e 24 69 20 7b 0a 20 20 20 20 6c 69 73 74 20  3.$i {.    list 
0fa0: 5b 63 61 74 63 68 20 7b 74 65 73 74 5f 66 74 73  [catch {test_fts
0fb0: 33 65 78 70 72 32 20 5b 72 61 6e 64 6f 6d 5f 61  3expr2 [random_a
0fc0: 6e 64 6f 72 5f 71 75 65 72 79 20 24 69 5d 7d 20  ndor_query $i]} 
0fd0: 6d 73 67 5d 20 24 6d 73 67 0a 20 20 7d 20 7b 31  msg] $msg.  } {1
0fe0: 20 7b 45 72 72 6f 72 20 70 61 72 73 69 6e 67 20   {Error parsing 
0ff0: 65 78 70 72 65 73 73 69 6f 6e 7d 7d 0a 7d 0a 0a  expression}}.}..
1000: 23 20 54 68 69 73 20 61 6c 73 6f 20 65 78 63 65  # This also exce
1010: 65 64 73 20 74 68 65 20 64 65 70 74 68 20 6c 69  eds the depth li
1020: 6d 69 74 2e 20 0a 23 0a 0a 64 6f 5f 74 65 73 74  mit. .#..do_test
1030: 20 34 2e 31 2e 31 20 7b 0a 20 20 73 65 74 20 71   4.1.1 {.  set q
1040: 20 22 31 22 0a 20 20 66 6f 72 20 7b 73 65 74 20   "1".  for {set 
1050: 69 20 32 7d 20 7b 24 69 20 3c 20 35 30 30 30 7d  i 2} {$i < 5000}
1060: 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20 20 20 20   {incr i} {.    
1070: 61 70 70 65 6e 64 20 71 20 22 20 41 4e 44 20 24  append q " AND $
1080: 69 22 0a 20 20 7d 0a 20 20 6c 69 73 74 20 5b 63  i".  }.  list [c
1090: 61 74 63 68 20 7b 74 65 73 74 5f 66 74 73 33 65  atch {test_fts3e
10a0: 78 70 72 32 20 24 71 7d 20 6d 73 67 5d 20 24 6d  xpr2 $q} msg] $m
10b0: 73 67 0a 7d 20 7b 31 20 7b 45 72 72 6f 72 20 70  sg.} {1 {Error p
10c0: 61 72 73 69 6e 67 20 65 78 70 72 65 73 73 69 6f  arsing expressio
10d0: 6e 7d 7d 0a 64 6f 5f 74 65 73 74 20 34 2e 31 2e  n}}.do_test 4.1.
10e0: 32 20 7b 0a 20 20 73 65 74 20 71 20 22 31 22 0a  2 {.  set q "1".
10f0: 20 20 66 6f 72 20 7b 73 65 74 20 69 20 32 7d 20    for {set i 2} 
1100: 7b 24 69 20 3c 20 34 30 30 30 7d 20 7b 69 6e 63  {$i < 4000} {inc
1110: 72 20 69 7d 20 7b 0a 20 20 20 20 61 70 70 65 6e  r i} {.    appen
1120: 64 20 71 20 22 20 41 4e 44 20 24 69 22 0a 20 20  d q " AND $i".  
1130: 7d 0a 20 20 63 61 74 63 68 20 7b 74 65 73 74 5f  }.  catch {test_
1140: 66 74 73 33 65 78 70 72 32 20 24 71 7d 0a 7d 20  fts3expr2 $q}.} 
1150: 7b 30 7d 0a 0a 70 72 6f 63 20 63 72 65 61 74 65  {0}..proc create
1160: 5f 74 6f 67 67 6c 65 5f 74 72 65 65 20 7b 6e 44  _toggle_tree {nD
1170: 65 70 74 68 7d 20 7b 0a 20 20 69 66 20 7b 24 6e  epth} {.  if {$n
1180: 44 65 70 74 68 20 3d 3d 20 30 7d 20 7b 20 72 65  Depth == 0} { re
1190: 74 75 72 6e 20 78 78 78 20 7d 0a 20 20 73 65 74  turn xxx }.  set
11a0: 20 6e 4e 65 77 20 5b 65 78 70 72 20 24 6e 44 65   nNew [expr $nDe
11b0: 70 74 68 2d 31 5d 0a 20 20 69 66 20 7b 24 6e 44  pth-1].  if {$nD
11c0: 65 70 74 68 20 25 20 32 7d 20 7b 0a 20 20 20 20  epth % 2} {.    
11d0: 72 65 74 75 72 6e 20 22 28 5b 63 72 65 61 74 65  return "([create
11e0: 5f 74 6f 67 67 6c 65 5f 74 72 65 65 20 24 6e 4e  _toggle_tree $nN
11f0: 65 77 5d 29 20 4f 52 20 28 5b 63 72 65 61 74 65  ew]) OR ([create
1200: 5f 74 6f 67 67 6c 65 5f 74 72 65 65 20 24 6e 4e  _toggle_tree $nN
1210: 65 77 5d 29 22 0a 20 20 7d 0a 20 20 72 65 74 75  ew])".  }.  retu
1220: 72 6e 20 22 28 5b 63 72 65 61 74 65 5f 74 6f 67  rn "([create_tog
1230: 67 6c 65 5f 74 72 65 65 20 24 6e 4e 65 77 5d 29  gle_tree $nNew])
1240: 20 41 4e 44 20 28 5b 63 72 65 61 74 65 5f 74 6f   AND ([create_to
1250: 67 67 6c 65 5f 74 72 65 65 20 24 6e 4e 65 77 5d  ggle_tree $nNew]
1260: 29 22 0a 7d 0a 0a 64 6f 5f 74 65 73 74 20 34 2e  )".}..do_test 4.
1270: 32 20 7b 0a 20 20 6c 69 73 74 20 5b 63 61 74 63  2 {.  list [catc
1280: 68 20 7b 74 65 73 74 5f 66 74 73 33 65 78 70 72  h {test_fts3expr
1290: 32 20 5b 63 72 65 61 74 65 5f 74 6f 67 67 6c 65  2 [create_toggle
12a0: 5f 74 72 65 65 20 31 37 5d 7d 20 6d 73 67 5d 20  _tree 17]} msg] 
12b0: 24 6d 73 67 0a 7d 20 7b 31 20 7b 45 72 72 6f 72  $msg.} {1 {Error
12c0: 20 70 61 72 73 69 6e 67 20 65 78 70 72 65 73 73   parsing express
12d0: 69 6f 6e 7d 7d 0a 0a 73 65 74 20 71 75 65 72 79  ion}}..set query
12e0: 20 5b 72 61 6e 64 6f 6d 5f 61 6e 64 6f 72 5f 71   [random_andor_q
12f0: 75 65 72 79 20 31 32 5d 0a 73 65 74 20 72 65 73  uery 12].set res
1300: 75 6c 74 20 5b 62 61 6c 61 6e 63 65 64 5f 61 6e  ult [balanced_an
1310: 64 6f 72 5f 74 72 65 65 20 31 32 5d 0a 64 6f 5f  dor_tree 12].do_
1320: 66 61 75 6c 74 73 69 6d 5f 74 65 73 74 20 66 74  faultsim_test ft
1330: 73 33 65 78 70 72 33 2d 66 61 75 6c 74 2d 31 20  s3expr3-fault-1 
1340: 2d 66 61 75 6c 74 73 20 6f 6f 6d 2d 2a 20 2d 62  -faults oom-* -b
1350: 6f 64 79 20 7b 0a 20 20 74 65 73 74 5f 66 74 73  ody {.  test_fts
1360: 33 65 78 70 72 32 20 24 3a 3a 71 75 65 72 79 0a  3expr2 $::query.
1370: 7d 20 2d 74 65 73 74 20 7b 0a 20 20 66 61 75 6c  } -test {.  faul
1380: 74 73 69 6d 5f 74 65 73 74 5f 72 65 73 75 6c 74  tsim_test_result
1390: 20 5b 6c 69 73 74 20 30 20 24 3a 3a 72 65 73 75   [list 0 $::resu
13a0: 6c 74 5d 0a 7d 0a 0a 7d 0a 0a 23 2d 2d 2d 2d 2d  lt].}..}..#-----
13b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
13c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
13d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
13e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a  --------------..
13f0: 66 6f 72 65 61 63 68 20 7b 74 6e 20 65 78 70 72  foreach {tn expr
1400: 20 72 65 73 7d 20 7b 0a 20 20 31 20 7b 31 20 4f   res} {.  1 {1 O
1410: 52 20 32 20 4f 52 20 33 20 4f 52 20 34 7d 20 20  R 2 OR 3 OR 4}  
1420: 20 20 20 20 20 20 20 20 20 7b 4f 52 20 7b 4f 52           {OR {OR
1430: 20 7b 50 20 31 7d 20 7b 50 20 32 7d 7d 20 7b 4f   {P 1} {P 2}} {O
1440: 52 20 7b 50 20 33 7d 20 7b 50 20 34 7d 7d 7d 20  R {P 3} {P 4}}} 
1450: 0a 20 20 32 20 7b 31 20 4f 52 20 28 32 20 41 4e  .  2 {1 OR (2 AN
1460: 44 20 33 20 41 4e 44 20 34 20 41 4e 44 20 35 29  D 3 AND 4 AND 5)
1470: 7d 20 0a 20 20 20 20 7b 4f 52 20 7b 50 20 31 7d  } .    {OR {P 1}
1480: 20 7b 41 4e 44 20 7b 41 4e 44 20 7b 50 20 32 7d   {AND {AND {P 2}
1490: 20 7b 50 20 33 7d 7d 20 7b 41 4e 44 20 7b 50 20   {P 3}} {AND {P 
14a0: 34 7d 20 7b 50 20 35 7d 7d 7d 7d 0a 20 20 33 20  4} {P 5}}}}.  3 
14b0: 7b 28 32 20 41 4e 44 20 33 20 41 4e 44 20 34 20  {(2 AND 3 AND 4 
14c0: 41 4e 44 20 35 29 20 4f 52 20 31 7d 20 0a 20 20  AND 5) OR 1} .  
14d0: 20 20 7b 4f 52 20 7b 41 4e 44 20 7b 41 4e 44 20    {OR {AND {AND 
14e0: 7b 50 20 32 7d 20 7b 50 20 33 7d 7d 20 7b 41 4e  {P 2} {P 3}} {AN
14f0: 44 20 7b 50 20 34 7d 20 7b 50 20 35 7d 7d 7d 20  D {P 4} {P 5}}} 
1500: 7b 50 20 31 7d 7d 0a 0a 20 20 34 20 7b 31 20 41  {P 1}}..  4 {1 A
1510: 4e 44 20 28 32 20 4f 52 20 33 20 4f 52 20 34 20  ND (2 OR 3 OR 4 
1520: 4f 52 20 35 29 7d 20 0a 20 20 20 20 7b 41 4e 44  OR 5)} .    {AND
1530: 20 7b 50 20 31 7d 20 7b 4f 52 20 7b 4f 52 20 7b   {P 1} {OR {OR {
1540: 50 20 32 7d 20 7b 50 20 33 7d 7d 20 7b 4f 52 20  P 2} {P 3}} {OR 
1550: 7b 50 20 34 7d 20 7b 50 20 35 7d 7d 7d 7d 0a 20  {P 4} {P 5}}}}. 
1560: 20 35 20 7b 28 32 20 4f 52 20 33 20 4f 52 20 34   5 {(2 OR 3 OR 4
1570: 20 4f 52 20 35 29 20 41 4e 44 20 31 7d 20 0a 20   OR 5) AND 1} . 
1580: 20 20 20 7b 41 4e 44 20 7b 4f 52 20 7b 4f 52 20     {AND {OR {OR 
1590: 7b 50 20 32 7d 20 7b 50 20 33 7d 7d 20 7b 4f 52  {P 2} {P 3}} {OR
15a0: 20 7b 50 20 34 7d 20 7b 50 20 35 7d 7d 7d 20 7b   {P 4} {P 5}}} {
15b0: 50 20 31 7d 7d 0a 0a 20 20 36 20 7b 28 32 20 4f  P 1}}..  6 {(2 O
15c0: 52 20 33 20 4f 52 20 34 20 4f 52 20 35 29 20 4e  R 3 OR 4 OR 5) N
15d0: 4f 54 20 31 7d 20 0a 20 20 20 20 7b 4e 4f 54 20  OT 1} .    {NOT 
15e0: 7b 4f 52 20 7b 4f 52 20 7b 50 20 32 7d 20 7b 50  {OR {OR {P 2} {P
15f0: 20 33 7d 7d 20 7b 4f 52 20 7b 50 20 34 7d 20 7b   3}} {OR {P 4} {
1600: 50 20 35 7d 7d 7d 20 7b 50 20 31 7d 7d 0a 0a 20  P 5}}} {P 1}}.. 
1610: 20 37 20 7b 31 20 4e 4f 54 20 28 32 20 4f 52 20   7 {1 NOT (2 OR 
1620: 33 20 4f 52 20 34 20 4f 52 20 35 29 7d 20 0a 20  3 OR 4 OR 5)} . 
1630: 20 20 20 7b 4e 4f 54 20 7b 50 20 31 7d 20 7b 4f     {NOT {P 1} {O
1640: 52 20 7b 4f 52 20 7b 50 20 32 7d 20 7b 50 20 33  R {OR {P 2} {P 3
1650: 7d 7d 20 7b 4f 52 20 7b 50 20 34 7d 20 7b 50 20  }} {OR {P 4} {P 
1660: 35 7d 7d 7d 7d 0a 0a 20 20 38 20 7b 28 31 20 4f  5}}}}..  8 {(1 O
1670: 52 20 32 20 4f 52 20 33 20 4f 52 20 34 29 20 4e  R 2 OR 3 OR 4) N
1680: 4f 54 20 28 35 20 41 4e 44 20 36 20 41 4e 44 20  OT (5 AND 6 AND 
1690: 37 20 41 4e 44 20 38 29 7d 0a 20 20 20 20 7b 4e  7 AND 8)}.    {N
16a0: 4f 54 20 7b 4f 52 20 7b 4f 52 20 7b 50 20 31 7d  OT {OR {OR {P 1}
16b0: 20 7b 50 20 32 7d 7d 20 7b 4f 52 20 7b 50 20 33   {P 2}} {OR {P 3
16c0: 7d 20 7b 50 20 34 7d 7d 7d 20 7b 41 4e 44 20 7b  } {P 4}}} {AND {
16d0: 41 4e 44 20 7b 50 20 35 7d 20 7b 50 20 36 7d 7d  AND {P 5} {P 6}}
16e0: 20 7b 41 4e 44 20 7b 50 20 37 7d 20 7b 50 20 38   {AND {P 7} {P 8
16f0: 7d 7d 7d 7d 0a 7d 20 7b 0a 20 20 64 6f 5f 74 65  }}}}.} {.  do_te
1700: 73 74 20 35 2e 31 2e 24 74 6e 20 7b 0a 20 20 20  st 5.1.$tn {.   
1710: 20 74 65 73 74 5f 66 74 73 33 65 78 70 72 32 20   test_fts3expr2 
1720: 24 65 78 70 72 0a 20 20 7d 20 24 72 65 73 0a 7d  $expr.  } $res.}
1730: 0a 0a 73 65 74 20 73 71 6c 69 74 65 5f 66 74 73  ..set sqlite_fts
1740: 33 5f 65 6e 61 62 6c 65 5f 70 61 72 65 6e 74 68  3_enable_parenth
1750: 65 73 65 73 20 30 0a 66 69 6e 69 73 68 5f 74 65  eses 0.finish_te
1760: 73 74 0a                                         st.