/ Hex Artifact Content
Login

Artifact 9e91b8edbcb197bf2e92161aa7696446d96dce5f:


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 23 20 54 65 73 74 20 74 68 61 74 20 71 75 65  .# Test that que
0be0: 72 69 65 73 20 6c 69 6b 65 20 22 31 20 41 4e 44  ries like "1 AND
0bf0: 20 32 20 41 4e 44 20 33 20 41 4e 44 20 34 2e 2e   2 AND 3 AND 4..
0c00: 2e 22 20 61 72 65 20 74 72 61 6e 73 66 6f 72 6d  ." are transform
0c10: 65 64 20 74 6f 20 0a 23 20 62 61 6c 61 6e 63 65  ed to .# balance
0c20: 64 20 74 72 65 65 73 20 62 79 20 46 54 53 2e 0a  d trees by FTS..
0c30: 23 0a 66 6f 72 20 7b 73 65 74 20 69 20 31 7d 20  #.for {set i 1} 
0c40: 7b 24 69 20 3c 20 31 30 30 7d 20 7b 69 6e 63 72  {$i < 100} {incr
0c50: 20 69 7d 20 7b 0a 20 20 64 6f 5f 74 65 73 74 20   i} {.  do_test 
0c60: 31 2e 24 69 20 7b 0a 20 20 20 20 74 65 73 74 5f  1.$i {.    test_
0c70: 66 74 73 33 65 78 70 72 32 20 5b 72 61 6e 64 6f  fts3expr2 [rando
0c80: 6d 5f 61 6e 64 5f 71 75 65 72 79 20 24 69 5d 0a  m_and_query $i].
0c90: 20 20 7d 20 5b 62 61 6c 61 6e 63 65 64 5f 61 6e    } [balanced_an
0ca0: 64 5f 74 72 65 65 20 24 69 5d 0a 7d 0a 0a 23 20  d_tree $i].}..# 
0cb0: 53 61 6d 65 20 61 67 61 69 6e 2c 20 65 78 63 65  Same again, exce
0cc0: 70 74 20 77 69 74 68 20 70 61 72 65 6e 74 68 65  pt with parenthe
0cd0: 73 69 73 20 69 6e 73 65 72 74 65 64 20 61 74 20  sis inserted at 
0ce0: 61 72 62 69 74 72 61 72 79 20 70 6f 69 6e 74 73  arbitrary points
0cf0: 2e 0a 23 0a 66 6f 72 20 7b 73 65 74 20 69 20 31  ..#.for {set i 1
0d00: 7d 20 7b 24 69 20 3c 20 31 30 30 7d 20 7b 69 6e  } {$i < 100} {in
0d10: 63 72 20 69 7d 20 7b 0a 20 20 64 6f 5f 74 65 73  cr i} {.  do_tes
0d20: 74 20 32 2e 24 69 20 7b 0a 20 20 20 20 74 65 73  t 2.$i {.    tes
0d30: 74 5f 66 74 73 33 65 78 70 72 32 20 5b 72 61 6e  t_fts3expr2 [ran
0d40: 64 6f 6d 5f 61 6e 64 5f 71 75 65 72 79 20 24 69  dom_and_query $i
0d50: 20 31 5d 0a 20 20 7d 20 5b 62 61 6c 61 6e 63 65   1].  } [balance
0d60: 64 5f 61 6e 64 5f 74 72 65 65 20 24 69 5d 0a 7d  d_and_tree $i].}
0d70: 0a 0a 23 20 4e 6f 77 20 61 74 74 65 6d 70 74 20  ..# Now attempt 
0d80: 74 6f 20 62 61 6c 61 6e 63 65 20 74 77 6f 20 41  to balance two A
0d90: 4e 44 20 74 72 65 65 73 20 6a 6f 69 6e 65 64 20  ND trees joined 
0da0: 62 79 20 61 6e 20 4f 52 2e 0a 23 0a 66 6f 72 20  by an OR..#.for 
0db0: 7b 73 65 74 20 69 20 31 7d 20 7b 24 69 20 3c 20  {set i 1} {$i < 
0dc0: 31 30 30 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a  100} {incr i} {.
0dd0: 20 20 64 6f 5f 74 65 73 74 20 33 2e 24 69 20 7b    do_test 3.$i {
0de0: 0a 20 20 20 20 74 65 73 74 5f 66 74 73 33 65 78  .    test_fts3ex
0df0: 70 72 32 20 22 5b 72 61 6e 64 6f 6d 5f 61 6e 64  pr2 "[random_and
0e00: 5f 71 75 65 72 79 20 24 69 20 31 5d 20 4f 52 20  _query $i 1] OR 
0e10: 5b 72 61 6e 64 6f 6d 5f 61 6e 64 5f 71 75 65 72  [random_and_quer
0e20: 79 20 24 69 20 31 5d 22 0a 20 20 7d 20 5b 6c 69  y $i 1]".  } [li
0e30: 73 74 20 4f 52 20 5b 62 61 6c 61 6e 63 65 64 5f  st OR [balanced_
0e40: 61 6e 64 5f 74 72 65 65 20 24 69 5d 20 5b 62 61  and_tree $i] [ba
0e50: 6c 61 6e 63 65 64 5f 61 6e 64 5f 74 72 65 65 20  lanced_and_tree 
0e60: 24 69 5d 5d 0a 7d 0a 0a 23 20 54 72 79 20 74 72  $i]].}..# Try tr
0e70: 65 65 73 20 6f 66 20 41 4e 44 20 6e 6f 64 65 73  ees of AND nodes
0e80: 20 77 69 74 68 20 6c 65 61 76 65 73 20 74 68 61   with leaves tha
0e90: 74 20 61 72 65 20 74 68 65 6d 73 65 6c 76 65 73  t are themselves
0ea0: 20 74 72 65 65 73 20 6f 66 20 4f 52 20 6e 6f 64   trees of OR nod
0eb0: 65 73 2e 0a 23 0a 66 6f 72 20 7b 73 65 74 20 69  es..#.for {set i
0ec0: 20 32 7d 20 7b 24 69 20 3c 20 36 34 7d 20 7b 69   2} {$i < 64} {i
0ed0: 6e 63 72 20 69 20 34 7d 20 7b 0a 20 20 64 6f 5f  ncr i 4} {.  do_
0ee0: 74 65 73 74 20 33 2e 24 69 20 7b 0a 20 20 20 20  test 3.$i {.    
0ef0: 74 65 73 74 5f 66 74 73 33 65 78 70 72 32 20 5b  test_fts3expr2 [
0f00: 72 61 6e 64 6f 6d 5f 61 6e 64 6f 72 5f 71 75 65  random_andor_que
0f10: 72 79 20 24 69 5d 0a 20 20 7d 20 5b 62 61 6c 61  ry $i].  } [bala
0f20: 6e 63 65 64 5f 61 6e 64 6f 72 5f 74 72 65 65 20  nced_andor_tree 
0f30: 24 69 5d 0a 7d 0a 0a 23 20 54 68 65 73 65 20 65  $i].}..# These e
0f40: 78 63 65 65 64 20 74 68 65 20 64 65 70 74 68 20  xceed the depth 
0f50: 6c 69 6d 69 74 2e 20 0a 23 0a 66 6f 72 20 7b 73  limit. .#.for {s
0f60: 65 74 20 69 20 36 35 7d 20 7b 24 69 20 3c 20 37  et i 65} {$i < 7
0f70: 30 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20 20  0} {incr i} {.  
0f80: 64 6f 5f 74 65 73 74 20 33 2e 24 69 20 7b 0a 20  do_test 3.$i {. 
0f90: 20 20 20 6c 69 73 74 20 5b 63 61 74 63 68 20 7b     list [catch {
0fa0: 74 65 73 74 5f 66 74 73 33 65 78 70 72 32 20 5b  test_fts3expr2 [
0fb0: 72 61 6e 64 6f 6d 5f 61 6e 64 6f 72 5f 71 75 65  random_andor_que
0fc0: 72 79 20 24 69 5d 7d 20 6d 73 67 5d 20 24 6d 73  ry $i]} msg] $ms
0fd0: 67 0a 20 20 7d 20 7b 31 20 7b 45 72 72 6f 72 20  g.  } {1 {Error 
0fe0: 70 61 72 73 69 6e 67 20 65 78 70 72 65 73 73 69  parsing expressi
0ff0: 6f 6e 7d 7d 0a 7d 0a 0a 23 20 54 68 69 73 20 61  on}}.}..# This a
1000: 6c 73 6f 20 65 78 63 65 65 64 73 20 74 68 65 20  lso exceeds the 
1010: 64 65 70 74 68 20 6c 69 6d 69 74 2e 20 0a 23 0a  depth limit. .#.
1020: 0a 64 6f 5f 74 65 73 74 20 34 2e 31 2e 31 20 7b  .do_test 4.1.1 {
1030: 0a 20 20 73 65 74 20 71 20 22 31 22 0a 20 20 66  .  set q "1".  f
1040: 6f 72 20 7b 73 65 74 20 69 20 32 7d 20 7b 24 69  or {set i 2} {$i
1050: 20 3c 20 35 30 30 30 7d 20 7b 69 6e 63 72 20 69   < 5000} {incr i
1060: 7d 20 7b 0a 20 20 20 20 61 70 70 65 6e 64 20 71  } {.    append q
1070: 20 22 20 41 4e 44 20 24 69 22 0a 20 20 7d 0a 20   " AND $i".  }. 
1080: 20 6c 69 73 74 20 5b 63 61 74 63 68 20 7b 74 65   list [catch {te
1090: 73 74 5f 66 74 73 33 65 78 70 72 32 20 24 71 7d  st_fts3expr2 $q}
10a0: 20 6d 73 67 5d 20 24 6d 73 67 0a 7d 20 7b 31 20   msg] $msg.} {1 
10b0: 7b 45 72 72 6f 72 20 70 61 72 73 69 6e 67 20 65  {Error parsing e
10c0: 78 70 72 65 73 73 69 6f 6e 7d 7d 0a 64 6f 5f 74  xpression}}.do_t
10d0: 65 73 74 20 34 2e 31 2e 32 20 7b 0a 20 20 73 65  est 4.1.2 {.  se
10e0: 74 20 71 20 22 31 22 0a 20 20 66 6f 72 20 7b 73  t q "1".  for {s
10f0: 65 74 20 69 20 32 7d 20 7b 24 69 20 3c 20 34 30  et i 2} {$i < 40
1100: 30 30 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20  00} {incr i} {. 
1110: 20 20 20 61 70 70 65 6e 64 20 71 20 22 20 41 4e     append q " AN
1120: 44 20 24 69 22 0a 20 20 7d 0a 20 20 63 61 74 63  D $i".  }.  catc
1130: 68 20 7b 74 65 73 74 5f 66 74 73 33 65 78 70 72  h {test_fts3expr
1140: 32 20 24 71 7d 0a 7d 20 7b 30 7d 0a 0a 70 72 6f  2 $q}.} {0}..pro
1150: 63 20 63 72 65 61 74 65 5f 74 6f 67 67 6c 65 5f  c create_toggle_
1160: 74 72 65 65 20 7b 6e 44 65 70 74 68 7d 20 7b 0a  tree {nDepth} {.
1170: 20 20 69 66 20 7b 24 6e 44 65 70 74 68 20 3d 3d    if {$nDepth ==
1180: 20 30 7d 20 7b 20 72 65 74 75 72 6e 20 78 78 78   0} { return xxx
1190: 20 7d 0a 20 20 73 65 74 20 6e 4e 65 77 20 5b 65   }.  set nNew [e
11a0: 78 70 72 20 24 6e 44 65 70 74 68 2d 31 5d 0a 20  xpr $nDepth-1]. 
11b0: 20 69 66 20 7b 24 6e 44 65 70 74 68 20 25 20 32   if {$nDepth % 2
11c0: 7d 20 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 22  } {.    return "
11d0: 28 5b 63 72 65 61 74 65 5f 74 6f 67 67 6c 65 5f  ([create_toggle_
11e0: 74 72 65 65 20 24 6e 4e 65 77 5d 29 20 4f 52 20  tree $nNew]) OR 
11f0: 28 5b 63 72 65 61 74 65 5f 74 6f 67 67 6c 65 5f  ([create_toggle_
1200: 74 72 65 65 20 24 6e 4e 65 77 5d 29 22 0a 20 20  tree $nNew])".  
1210: 7d 0a 20 20 72 65 74 75 72 6e 20 22 28 5b 63 72  }.  return "([cr
1220: 65 61 74 65 5f 74 6f 67 67 6c 65 5f 74 72 65 65  eate_toggle_tree
1230: 20 24 6e 4e 65 77 5d 29 20 41 4e 44 20 28 5b 63   $nNew]) AND ([c
1240: 72 65 61 74 65 5f 74 6f 67 67 6c 65 5f 74 72 65  reate_toggle_tre
1250: 65 20 24 6e 4e 65 77 5d 29 22 0a 7d 0a 0a 64 6f  e $nNew])".}..do
1260: 5f 74 65 73 74 20 34 2e 32 20 7b 0a 20 20 6c 69  _test 4.2 {.  li
1270: 73 74 20 5b 63 61 74 63 68 20 7b 74 65 73 74 5f  st [catch {test_
1280: 66 74 73 33 65 78 70 72 32 20 5b 63 72 65 61 74  fts3expr2 [creat
1290: 65 5f 74 6f 67 67 6c 65 5f 74 72 65 65 20 31 37  e_toggle_tree 17
12a0: 5d 7d 20 6d 73 67 5d 20 24 6d 73 67 0a 7d 20 7b  ]} msg] $msg.} {
12b0: 31 20 7b 45 72 72 6f 72 20 70 61 72 73 69 6e 67  1 {Error parsing
12c0: 20 65 78 70 72 65 73 73 69 6f 6e 7d 7d 0a 0a 73   expression}}..s
12d0: 65 74 20 71 75 65 72 79 20 5b 72 61 6e 64 6f 6d  et query [random
12e0: 5f 61 6e 64 6f 72 5f 71 75 65 72 79 20 31 32 5d  _andor_query 12]
12f0: 0a 73 65 74 20 72 65 73 75 6c 74 20 5b 62 61 6c  .set result [bal
1300: 61 6e 63 65 64 5f 61 6e 64 6f 72 5f 74 72 65 65  anced_andor_tree
1310: 20 31 32 5d 0a 64 6f 5f 66 61 75 6c 74 73 69 6d   12].do_faultsim
1320: 5f 74 65 73 74 20 66 74 73 33 65 78 70 72 33 2d  _test fts3expr3-
1330: 66 61 75 6c 74 2d 31 20 2d 66 61 75 6c 74 73 20  fault-1 -faults 
1340: 6f 6f 6d 2d 2a 20 2d 62 6f 64 79 20 7b 0a 20 20  oom-* -body {.  
1350: 74 65 73 74 5f 66 74 73 33 65 78 70 72 32 20 24  test_fts3expr2 $
1360: 3a 3a 71 75 65 72 79 0a 7d 20 2d 74 65 73 74 20  ::query.} -test 
1370: 7b 0a 20 20 66 61 75 6c 74 73 69 6d 5f 74 65 73  {.  faultsim_tes
1380: 74 5f 72 65 73 75 6c 74 20 5b 6c 69 73 74 20 30  t_result [list 0
1390: 20 24 3a 3a 72 65 73 75 6c 74 5d 0a 7d 0a 0a 73   $::result].}..s
13a0: 65 74 20 73 71 6c 69 74 65 5f 66 74 73 33 5f 65  et sqlite_fts3_e
13b0: 6e 61 62 6c 65 5f 70 61 72 65 6e 74 68 65 73 65  nable_parenthese
13c0: 73 20 30 0a 66 69 6e 69 73 68 5f 74 65 73 74 0a  s 0.finish_test.