tk/tests/textBTree.test

   1 # This file is a Tcl script to test out the B-tree facilities of
   2 # Tk's text widget (the contents of the file "tkTextBTree.c".  There are
   3 # several file with additional tests for other features of text widgets.
   4 # This file is organized in the standard fashion for Tcl tests.
   5 #
   6 # Copyright (c) 1992-1994 The Regents of the University of California.
   7 # Copyright (c) 1994 Sun Microsystems, Inc.
   8 #
   9 # See the file "license.terms" for information on usage and redistribution
  10 # of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  11 #
  12 # RCS: @(#) $Id$
  13
  14 if {[string compare test [info procs test]] == 1} then \
  15   {source defs}
  16
  17 catch {destroy .t}
  18 text .t
  19 .t debug on
  20
  21 test btree-1.1 {basic insertions} {
  22     .t delete 1.0 100000.0
  23     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  24     .t get 1.0 1000000.0
  25 } "Line 1\nLine 2\nLine 3\n"
  26 test btree-1.2 {basic insertions} {
  27     .t delete 1.0 100000.0
  28     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  29     .t insert 1.3 XXX
  30     .t get 1.0 1000000.0
  31 } "LinXXXe 1\nLine 2\nLine 3\n"
  32 test btree-1.3 {basic insertions} {
  33     .t delete 1.0 100000.0
  34     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  35     .t insert 3.0 YYY
  36     .t get 1.0 1000000.0
  37 } "Line 1\nLine 2\nYYYLine 3\n"
  38 test btree-1.4 {basic insertions} {
  39     .t delete 1.0 100000.0
  40     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  41     .t insert 2.1 X\nYY
  42     .t get 1.0 1000000.0
  43 } "Line 1\nLX\nYYine 2\nLine 3\n"
  44 test btree-1.5 {basic insertions} {
  45     .t delete 1.0 100000.0
  46     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  47     .t insert 2.0 X\n\n\n
  48     .t get 1.0 1000000.0
  49 } "Line 1\nX\n\n\nLine 2\nLine 3\n"
  50 test btree-1.6 {basic insertions} {
  51     .t delete 1.0 100000.0
  52     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  53     .t insert 2.6 X\n
  54     .t get 1.0 1000000.0
  55 } "Line 1\nLine 2X\n\nLine 3\n"
  56 test btree-1.7 {insertion before start of text} {
  57     .t delete 1.0 100000.0
  58     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  59     .t insert 0.4 XXX
  60     .t get 1.0 1000000.0
  61 } "XXXLine 1\nLine 2\nLine 3\n"
  62 test btree-1.8 {insertion past end of text} {
  63     .t delete 1.0 100000.0
  64     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  65     .t insert 100.0 ZZ
  66     .t get 1.0 1000000.0
  67 } "Line 1\nLine 2\nLine 3ZZ\n"
  68 test btree-1.9 {insertion before start of line} {
  69     .t delete 1.0 100000.0
  70     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  71     .t insert 2.-3 Q
  72     .t get 1.0 1000000.0
  73 } "Line 1\nQLine 2\nLine 3\n"
  74 test btree-1.10 {insertion past end of line} {
  75     .t delete 1.0 100000.0
  76     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  77     .t insert 2.40 XYZZY
  78     .t get 1.0 1000000.0
  79 } "Line 1\nLine 2XYZZY\nLine 3\n"
  80 test btree-1.11 {insertion past end of last line} {
  81     .t delete 1.0 100000.0
  82     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  83     .t insert 3.40 ABC
  84     .t get 1.0 1000000.0
  85 } "Line 1\nLine 2\nLine 3ABC\n"
  86
  87 test btree-2.1 {basic deletions} {
  88     .t delete 1.0 100000.0
  89     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  90     .t delete 1.0 1.3
  91     .t get 1.0 1000000.0
  92 } "e 1\nLine 2\nLine 3\n"
  93 test btree-2.2 {basic deletions} {
  94     .t delete 1.0 100000.0
  95     .t insert 1.0 "Line 1\nLine 2\nLine 3"
  96     .t delete 2.2
  97     .t get 1.0 1000000.0
  98 } "Line 1\nLie 2\nLine 3\n"
  99 test btree-2.3 {basic deletions} {
 100     .t delete 1.0 100000.0
 101     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 102     .t delete 2.0 2.3
 103     .t get 1.0 1000000.0
 104 } "Line 1\ne 2\nLine 3\n"
 105 test btree-2.4 {deleting whole lines} {
 106     .t delete 1.0 100000.0
 107     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 108     .t delete 1.2 3.0
 109     .t get 1.0 1000000.0
 110 } "LiLine 3\n"
 111 test btree-2.5 {deleting whole lines} {
 112     .t delete 1.0 100000.0
 113     .t insert 1.0 "Line 1\nLine 2\n\n\nLine 5"
 114     .t delete 1.0 5.2
 115     .t get 1.0 1000000.0
 116 } "ne 5\n"
 117 test btree-2.6 {deleting before start of file} {
 118     .t delete 1.0 100000.0
 119     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 120     .t delete 0.3 1.2
 121     .t get 1.0 1000000.0
 122 } "ne 1\nLine 2\nLine 3\n"
 123 test btree-2.7 {deleting after end of file} {
 124     .t delete 1.0 100000.0
 125     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 126     .t delete 10.3
 127     .t get 1.0 1000000.0
 128 } "Line 1\nLine 2\nLine 3\n"
 129 test btree-2.8 {deleting before start of line} {
 130     .t delete 1.0 100000.0
 131     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 132     .t delete 3.-1 3.3
 133     .t get 1.0 1000000.0
 134 } "Line 1\nLine 2\ne 3\n"
 135 test btree-2.9 {deleting before start of line} {
 136     .t delete 1.0 100000.0
 137     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 138     .t delete 1.-1 1.0
 139     .t get 1.0 1000000.0
 140 } "Line 1\nLine 2\nLine 3\n"
 141 test btree-2.10 {deleting after end of line} {
 142     .t delete 1.0 100000.0
 143     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 144     .t delete 1.8 2.1
 145     .t get 1.0 1000000.0
 146 } "Line 1ine 2\nLine 3\n"
 147 test btree-2.11 {deleting after end of last line} {
 148     .t delete 1.0 100000.0
 149     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 150     .t delete 3.8 4.1
 151     .t get 1.0 1000000.0
 152 } "Line 1\nLine 2\nLine 3\n"
 153 test btree-2.12 {deleting before start of file} {
 154     .t delete 1.0 100000.0
 155     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 156     .t delete 1.8 0.0
 157     .t get 1.0 1000000.0
 158 } "Line 1\nLine 2\nLine 3\n"
 159 test btree-2.13 {deleting past end of file} {
 160     .t delete 1.0 100000.0
 161     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 162     .t delete 1.8 4.0
 163     .t get 1.0 1000000.0
 164 } "Line 1\n"
 165 test btree-2.14 {deleting with end before start of line} {
 166     .t delete 1.0 100000.0
 167     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 168     .t delete 1.3 2.-3
 169     .t get 1.0 1000000.0
 170 } "LinLine 2\nLine 3\n"
 171 test btree-2.15 {deleting past end of line} {
 172     .t delete 1.0 100000.0
 173     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 174     .t delete 1.3 1.9
 175     .t get 1.0 1000000.0
 176 } "Lin\nLine 2\nLine 3\n"
 177 test btree-2.16 {deleting past end of line} {
 178     .t delete 1.0 100000.0
 179     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 180     .t delete 3.2 3.15
 181     .t get 1.0 1000000.0
 182 } "Line 1\nLine 2\nLi\n"
 183 test btree-2.17 {deleting past end of line} {
 184     .t delete 1.0 100000.0
 185     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 186     .t delete 3.0 3.15
 187     .t get 1.0 1000000.0
 188 } "Line 1\nLine 2\n\n"
 189 test btree-2.18 {deleting past end of line} {
 190     .t delete 1.0 100000.0
 191     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 192     .t delete 1.0 3.15
 193     .t get 1.0 1000000.0
 194 } "\n"
 195 test btree-2.19 {deleting with negative range} {
 196     .t delete 1.0 100000.0
 197     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 198     .t delete 3.2 2.4
 199     .t get 1.0 1000000.0
 200 } "Line 1\nLine 2\nLine 3\n"
 201 test btree-2.20 {deleting with negative range} {
 202     .t delete 1.0 100000.0
 203     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 204     .t delete 3.2 3.1
 205     .t get 1.0 1000000.0
 206 } "Line 1\nLine 2\nLine 3\n"
 207 test btree-2.21 {deleting with negative range} {
 208     .t delete 1.0 100000.0
 209     .t insert 1.0 "Line 1\nLine 2\nLine 3"
 210     .t delete 3.2 3.2
 211     .t get 1.0 1000000.0
 212 } "Line 1\nLine 2\nLine 3\n"
 213
 214 proc setup {} {
 215     .t delete 1.0 100000.0
 216     .t tag delete x y
 217     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 218     .t tag add x 1.1
 219     .t tag add x 1.5 1.13
 220     .t tag add x 2.2 2.6
 221     .t tag add y 1.5
 222 }
 223
 224 test btree-3.1 {inserting with tags} {
 225     setup
 226     .t insert 1.0 XXX
 227     list [.t tag ranges x] [.t tag ranges y]
 228 } {{1.4 1.5 1.8 1.16 2.2 2.6} {1.8 1.9}}
 229 test btree-3.2 {inserting with tags} {
 230     setup
 231     .t insert 1.15 YYY
 232     list [.t tag ranges x] [.t tag ranges y]
 233 } {{1.1 1.2 1.5 1.13 2.2 2.6} {1.5 1.6}}
 234 test btree-3.3 {inserting with tags} {
 235     setup
 236     .t insert 1.7 ZZZZ
 237     list [.t tag ranges x] [.t tag ranges y]
 238 } {{1.1 1.2 1.5 1.17 2.2 2.6} {1.5 1.6}}
 239 test btree-3.4 {inserting with tags} {
 240     setup
 241     .t insert 1.7 \n\n
 242     list [.t tag ranges x] [.t tag ranges y]
 243 } {{1.1 1.2 1.5 3.6 4.2 4.6} {1.5 1.6}}
 244 test btree-3.5 {inserting with tags} {
 245     setup
 246     .t insert 1.5 A\n
 247     list [.t tag ranges x] [.t tag ranges y]
 248 } {{1.1 1.2 2.0 2.8 3.2 3.6} {2.0 2.1}}
 249 test btree-3.6 {inserting with tags} {
 250     setup
 251     .t insert 1.13 A\n
 252     list [.t tag ranges x] [.t tag ranges y]
 253 } {{1.1 1.2 1.5 1.13 3.2 3.6} {1.5 1.6}}
 254
 255 test btree-4.1 {deleting with tags} {
 256     setup
 257     .t delete 1.6 1.9
 258     list [.t tag ranges x] [.t tag ranges y]
 259 } {{1.1 1.2 1.5 1.10 2.2 2.6} {1.5 1.6}}
 260 test btree-4.2 {deleting with tags} {
 261     setup
 262     .t delete 1.1 2.3
 263     list [.t tag ranges x] [.t tag ranges y]
 264 } {{1.1 1.4} {}}
 265 test btree-4.3 {deleting with tags} {
 266     setup
 267     .t delete 1.4 2.1
 268     list [.t tag ranges x] [.t tag ranges y]
 269 } {{1.1 1.2 1.5 1.9} {}}
 270 test btree-4.4 {deleting with tags} {
 271     setup
 272     .t delete 1.14 2.1
 273     list [.t tag ranges x] [.t tag ranges y]
 274 } {{1.1 1.2 1.5 1.13 1.15 1.19} {1.5 1.6}}
 275 test btree-4.5 {deleting with tags} {
 276     setup
 277     .t delete 1.0 2.10
 278     list [.t tag ranges x] [.t tag ranges y]
 279 } {{} {}}
 280 test btree-4.6 {deleting with tags} {
 281     setup
 282     .t delete 1.0 1.5
 283     list [.t tag ranges x] [.t tag ranges y]
 284 } {{1.0 1.8 2.2 2.6} {1.0 1.1}}
 285 test btree-4.7 {deleting with tags} {
 286     setup
 287     .t delete 1.6 1.9
 288     list [.t tag ranges x] [.t tag ranges y]
 289 } {{1.1 1.2 1.5 1.10 2.2 2.6} {1.5 1.6}}
 290 test btree-4.8 {deleting with tags} {
 291     setup
 292     .t delete 1.5 1.13
 293     list [.t tag ranges x] [.t tag ranges y]
 294 } {{1.1 1.2 2.2 2.6} {}}
 295
 296 set bigText1 {}
 297 for {set i 0} {$i < 10} {incr i} {
 298     append bigText1 "Line $i\n"
 299 }
 300 set bigText2 {}
 301 for {set i 0} {$i < 200} {incr i} {
 302     append bigText2 "Line $i\n"
 303 }
 304 test btree-5.1 {very large inserts, with tags} {
 305     setup
 306     .t insert 1.0 $bigText1
 307     list [.t tag ranges x] [.t tag ranges y]
 308 } {{11.1 11.2 11.5 11.13 12.2 12.6} {11.5 11.6}}
 309 test btree-5.2 {very large inserts, with tags} {
 310     setup
 311     .t insert 1.2 $bigText2
 312     list [.t tag ranges x] [.t tag ranges y]
 313 } {{1.1 1.2 201.3 201.11 202.2 202.6} {201.3 201.4}}
 314 test btree-5.3 {very large inserts, with tags} {
 315     setup
 316     for {set i 0} {$i < 200} {incr i} {
 317         .t insert 1.8 "longer line $i\n"
 318     }
 319     list [.t tag ranges x] [.t tag ranges y] [.t get 1.0 1.100] [.t get 198.0 198.100]
 320 } {{1.1 1.2 1.5 201.5 202.2 202.6} {1.5 1.6} {Text forlonger line 199} {longer line 2}}
 321
 322 test btree-6.1 {very large deletes, with tags} {
 323     setup
 324     .t insert 1.1 $bigText2
 325     .t delete 1.2 201.2
 326     list [.t tag ranges x] [.t tag ranges y]
 327 } {{1.4 1.12 2.2 2.6} {1.4 1.5}}
 328 test btree-6.2 {very large deletes, with tags} {
 329     setup
 330     .t insert 1.1 $bigText2
 331     for {set i 0} {$i < 200} {incr i} {
 332         .t delete 1.2 2.2
 333     }
 334     list [.t tag ranges x] [.t tag ranges y]
 335 } {{1.4 1.12 2.2 2.6} {1.4 1.5}}
 336 test btree-6.3 {very large deletes, with tags} {
 337     setup
 338     .t insert 1.1 $bigText2
 339     .t delete 2.3 10000.0
 340     .t get 1.0 1000.0
 341 } {TLine 0
 342 Lin
 343 }
 344 test btree-6.4 {very large deletes, with tags} {
 345     setup
 346     .t insert 1.1 $bigText2
 347     for {set i 0} {$i < 100} {incr i} {
 348         .t delete 30.0 31.0
 349     }
 350     list [.t tag ranges x] [.t tag ranges y]
 351 } {{101.0 101.1 101.4 101.12 102.2 102.6} {101.4 101.5}}
 352 test btree-6.5 {very large deletes, with tags} {
 353     setup
 354     .t insert 1.1 $bigText2
 355     for {set i 0} {$i < 100} {incr i} {
 356         set j [expr $i+2]
 357         set k [expr 1+2*$i]
 358         .t tag add x $j.1 $j.3
 359         .t tag add y $k.1 $k.6
 360     }
 361     .t delete 2.0 200.0
 362     list [.t tag ranges x] [.t tag ranges y]
 363 } {{3.0 3.1 3.4 3.12 4.2 4.6} {1.1 1.6 3.4 3.5}}
 364 test btree-6.6 {very large deletes, with tags} {
 365     setup
 366     .t insert 1.1 $bigText2
 367     for {set i 0} {$i < 100} {incr i} {
 368         set j [expr $i+2]
 369         set k [expr 1+2*$i]
 370         .t tag add x $j.1 $j.3
 371         .t tag add y $k.1 $k.6
 372     }
 373     for {set i 199} {$i >= 2} {incr i -1} {
 374         .t delete $i.0 [expr $i+1].0
 375     }
 376     list [.t tag ranges x] [.t tag ranges y]
 377 } {{3.0 3.1 3.4 3.12 4.2 4.6} {1.1 1.6 3.4 3.5}}
 378
 379 .t delete 1.0 end
 380 .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 381 set i 1
 382 foreach check {
 383     {1.3 1.6 1.7 2.0 {1.3 1.6 1.7 2.0}}
 384     {1.3 1.6 1.6 2.0 {1.3 2.0}}
 385     {1.3 1.6 1.4 2.0 {1.3 2.0}}
 386     {2.0 4.3 1.4 1.10 {1.4 1.10 2.0 4.3}}
 387     {2.0 4.3 1.4 1.end {1.4 1.19 2.0 4.3}}
 388     {2.0 4.3 1.4 2.0 {1.4 4.3}}
 389     {2.0 4.3 1.4 3.0 {1.4 4.3}}
 390     {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.1 4.2 {1.1 4.2}}
 391     {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.3 4.2 {1.2 4.2}}
 392     {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.1 3.0 {1.1 4.0}}
 393     {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.2 3.0 {1.2 4.0}}
 394 } {
 395     test btree-7.$i {tag addition and removal} {
 396         .t tag remove x 1.0 end
 397         while {[llength $check] > 2} {
 398             .t tag add x [lindex $check 0] [lindex $check 1]
 399             set check [lrange $check 2 end]
 400         }
 401         .t tag ranges x
 402     } [lindex $check [expr [llength $check]-1]]
 403     incr i
 404 }
 405
 406 test btree-8.1 {tag addition and removal, weird ranges} {
 407     .t delete 1.0 100000.0
 408     .t tag delete x
 409     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 410     .t tag add x 0.0 1.3
 411     .t tag ranges x
 412 } {1.0 1.3}
 413 test btree-8.2 {tag addition and removal, weird ranges} {
 414     .t delete 1.0 100000.0
 415     .t tag delete x
 416     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 417     .t tag add x 1.40 2.4
 418     .t tag ranges x
 419 } {1.19 2.4}
 420 test btree-8.3 {tag addition and removal, weird ranges} {
 421     .t delete 1.0 100000.0
 422     .t tag delete x
 423     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 424     .t tag add x 4.40 4.41
 425     .t tag ranges x
 426 } {}
 427 test btree-8.4 {tag addition and removal, weird ranges} {
 428     .t delete 1.0 100000.0
 429     .t tag delete x
 430     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 431     .t tag add x 5.1 5.2
 432     .t tag ranges x
 433 } {}
 434 test btree-8.5 {tag addition and removal, weird ranges} {
 435     .t delete 1.0 100000.0
 436     .t tag delete x
 437     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 438     .t tag add x 1.1 9.0
 439     .t tag ranges x
 440 } {1.1 5.0}
 441 test btree-8.6 {tag addition and removal, weird ranges} {
 442     .t delete 1.0 100000.0
 443     .t tag delete x
 444     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 445     .t tag add x 1.1 1.90
 446     .t tag ranges x
 447 } {1.1 1.19}
 448 test btree-8.7 {tag addition and removal, weird ranges} {
 449     .t delete 1.0 100000.0
 450     .t tag delete x
 451     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 452     .t tag add x 1.1 4.90
 453     .t tag ranges x
 454 } {1.1 4.17}
 455 test btree-8.8 {tag addition and removal, weird ranges} {
 456     .t delete 1.0 100000.0
 457     .t tag delete x
 458     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 459     .t tag add x 3.0 3.0
 460     .t tag ranges x
 461 } {}
 462
 463 test btree-9.1 {tag names} {
 464     setup
 465     .t tag names
 466 } {sel x y}
 467 test btree-9.2 {tag names} {
 468     setup
 469     .t tag add tag1 1.8
 470     .t tag add tag2 1.8
 471     .t tag add tag3 1.7 1.9
 472     .t tag names 1.8
 473 } {x tag1 tag2 tag3}
 474 test btree-9.3 {lots of tag names} {
 475     setup
 476     .t insert 1.2 $bigText2
 477     foreach i {tag1 foo ThisOne {x space} q r s t} {
 478         .t tag add $i 150.2
 479     }
 480     foreach i {u tagA tagB tagC and more {$} \{} {
 481         .t tag add $i 150.1 150.3
 482     }
 483     .t tag names 150.2
 484 } {tag1 foo ThisOne {x space} q r s t u tagA tagB tagC and more {$} \{}
 485 test btree-9.4 {lots of tag names} {
 486     setup
 487     .t insert 1.2 $bigText2
 488     .t tag delete tag1 foo ThisOne more {x space} q r s t u
 489     .t tag delete tagA tagB tagC and {$} \{ more
 490     foreach i {tag1 foo ThisOne more {x space} q r s t} {
 491         .t tag add $i 150.2
 492     }
 493     foreach i {foo ThisOne u tagA tagB tagC and more {$} \{} {
 494         .t tag add $i 150.4
 495     }
 496     .t tag delete tag1 more q r tagA
 497     .t tag names 150.2
 498 } {foo ThisOne {x space} s t}
 499
 500 proc msetup {} {
 501     .t delete 1.0 100000.0
 502     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 503     .t mark set m1 1.2
 504     .t mark set l1 1.2
 505     .t mark gravity l1 left
 506     .t mark set next 1.6
 507     .t mark set x 1.6
 508     .t mark set m2 2.0
 509     .t mark set m3 2.100
 510     .t tag add x 1.3 1.8
 511 }
 512 test btree-10.1 {basic mark facilities} {
 513     msetup
 514     list [lsort [.t mark names]] [.t index m1] [.t index m2] [.t index m3]
 515 } {{current insert l1 m1 m2 m3 next x} 1.2 2.0 2.11}
 516 test btree-10.2 {basic mark facilities} {
 517     msetup
 518     .t mark unset m2
 519     lsort [.t mark names]
 520 } {current insert l1 m1 m3 next x}
 521 test btree-10.3 {basic mark facilities} {
 522     msetup
 523     .t mark set m2 1.8
 524     list [lsort [.t mark names]] [.t index m1] [.t index m2] [.t index m3]
 525 } {{current insert l1 m1 m2 m3 next x} 1.2 1.8 2.11}
 526
 527 test btree-11.1 {marks and inserts} {
 528     msetup
 529     .t insert 1.1 abcde
 530     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 531 } {1.7 1.7 1.11 1.11 2.0 2.11}
 532 test btree-11.2 {marks and inserts} {
 533     msetup
 534     .t insert 1.2 abcde
 535     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 536 } {1.2 1.7 1.11 1.11 2.0 2.11}
 537 test btree-11.3 {marks and inserts} {
 538     msetup
 539     .t insert 1.3 abcde
 540     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 541 } {1.2 1.2 1.11 1.11 2.0 2.11}
 542 test btree-11.4 {marks and inserts} {
 543     msetup
 544     .t insert 1.1 ab\n\ncde
 545     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 546 } {3.4 3.4 3.8 3.8 4.0 4.11}
 547 test btree-11.5 {marks and inserts} {
 548     msetup
 549     .t insert 1.4 ab\n\ncde
 550     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 551 } {1.2 1.2 3.5 3.5 4.0 4.11}
 552 test btree-11.6 {marks and inserts} {
 553     msetup
 554     .t insert 1.7 ab\n\ncde
 555     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 556 } {1.2 1.2 1.6 1.6 4.0 4.11}
 557
 558 test btree-12.1 {marks and deletes} {
 559     msetup
 560     .t delete 1.3 1.5
 561     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 562 } {1.2 1.2 1.4 1.4 2.0 2.11}
 563 test btree-12.2 {marks and deletes} {
 564     msetup
 565     .t delete 1.3 1.8
 566     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 567 } {1.2 1.2 1.3 1.3 2.0 2.11}
 568 test btree-12.3 {marks and deletes} {
 569     msetup
 570     .t delete 1.2 1.8
 571     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 572 } {1.2 1.2 1.2 1.2 2.0 2.11}
 573 test btree-12.4 {marks and deletes} {
 574     msetup
 575     .t delete 1.1 1.8
 576     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 577 } {1.1 1.1 1.1 1.1 2.0 2.11}
 578 test btree-12.5 {marks and deletes} {
 579     msetup
 580     .t delete 1.5 3.1
 581     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 582 } {1.2 1.2 1.5 1.5 1.5 1.5}
 583 test btree-12.6 {marks and deletes} {
 584     msetup
 585     .t mark set m2 4.5
 586     .t delete 1.5 4.1
 587     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 588 } {1.2 1.2 1.5 1.5 1.9 1.5}
 589 test btree-12.7 {marks and deletes} {
 590     msetup
 591     .t mark set m2 4.5
 592     .t mark set m3 4.5
 593     .t mark set m1 4.7
 594     .t delete 1.5 4.1
 595     list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
 596 } {1.2 1.11 1.5 1.5 1.9 1.9}
 597
 598 destroy .t
 599 text .t
 600 test btree-13.1 {tag searching} {
 601     .t delete 1.0 100000.0
 602     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 603     .t tag next x 2.2 2.1
 604 } {}
 605 test btree-13.2 {tag searching} {
 606     .t delete 1.0 100000.0
 607     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 608     .t tag add x 2.2 2.4
 609     .t tag next x 2.2 2.3
 610 } {2.2 2.4}
 611 test btree-13.3 {tag searching} {
 612     .t delete 1.0 100000.0
 613     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 614     .t tag add x 2.2 2.4
 615     .t tag next x 2.3 2.6
 616 } {}
 617 test btree-13.4 {tag searching} {
 618     .t delete 1.0 100000.0
 619     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 620     .t tag add x 2.5 2.8
 621     .t tag next x 2.1 2.6
 622 } {2.5 2.8}
 623 test btree-13.5 {tag searching} {
 624     .t delete 1.0 100000.0
 625     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 626     .t tag add x 2.5 2.8
 627     .t tag next x 2.1 2.5
 628 } {}
 629 test btree-13.6 {tag searching} {
 630     .t delete 1.0 100000.0
 631     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 632     .t tag add x 2.1 2.4
 633     .t tag next x 2.5 2.8
 634 } {}
 635 test btree-13.7 {tag searching} {
 636     .t delete 1.0 100000.0
 637     .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
 638     .t tag add x 2.5 2.8
 639     .t tag next x 2.1 2.4
 640 } {}
 641 test btree-13.8 {tag searching} {
 642     setup
 643     .t insert 1.2 $bigText2
 644     .t tag add x 190.3 191.2
 645     .t tag next x 3.5
 646 } {190.3 191.2}
 647
 648 test btree-14.1 {check tag presence} {
 649     setup
 650     .t insert 1.2 $bigText2
 651     .t tag add x 3.5 3.7
 652     .t tag add y 133.9 141.5
 653     .t tag add z 1.5 180.2
 654     .t tag add q 141.4 142.3
 655     .t tag add x 130.2 145.1
 656     .t tag add a 141.0
 657     .t tag add b 4.3
 658     .t tag add b 7.5
 659     .t tag add b 140.3
 660     for {set i 120} {$i < 160} {incr i} {
 661         .t tag add c $i.4
 662     }
 663     foreach i {a1 a2 a3 a4 a5 a6 a7 a8 a9 10 a11 a12 a13} {
 664         .t tag add $i 122.2
 665     }
 666     .t tag add x 141.3
 667     .t tag names 141.1
 668 } {x y z}
 669
 670 test btree-15.1 {rebalance with empty node} {
 671     catch {destroy .t}
 672     text .t
 673     .t debug 1
 674     .t insert end "1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23"
 675     .t delete 6.0 12.0
 676     .t get 1.0 end
 677 } "1\n2\n3\n4\n5\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23\n"
 678
 679 proc setupBig {} {
 680     .t delete 1.0 end
 681     .t tag delete x y
 682     .t tag configure x -foreground blue
 683     .t tag configure y -underline true
 684     # Create a Btree with 2002 lines (2000 + already existing + phantom at end)
 685     # This generates a level 3 node with 9 children
 686     # Most level 2 nodes cover 216 lines and have 6 children, except the last
 687     # level 2 node covers 274 lines and has 7 children.
 688     # Most level 1 nodes cover 36 lines and have 6 children, except the
 689     # rightmost node has 58 lines and 9 children.
 690     # Level 2: 2002 = 8*216 + 274
 691     # Level 1: 2002 = 54*36 + 58
 692     # Level 0: 2002 = 332*6 + 10
 693     for {set i 0} {$i < 2000} {incr i} {
 694         append x "Line $i abcd efgh ijkl\n"
 695     }
 696     .t insert insert $x
 697     .t debug 1
 698 }
 699
 700 test btree-16.1 {add tag does not push root above level 0} {
 701     catch {destroy .t}
 702     text .t
 703     setupBig
 704     .t tag add x 1.1 1.10
 705     .t tag add x 5.1 5.10
 706     .t tag ranges x
 707 } {1.1 1.10 5.1 5.10}
 708 test btree-16.2 {add tag pushes root up to level 1 node} {
 709     catch {destroy .t}
 710     text .t
 711     .t debug 1
 712     setupBig
 713     .t tag add x 1.1 1.10
 714     .t tag add x 8.1 8.10
 715     .t tag ranges x
 716 } {1.1 1.10 8.1 8.10}
 717 test btree-16.3 {add tag pushes root up to level 2 node} {
 718     .t tag remove x 1.0 end
 719     .t tag add x 8.1 9.10
 720     .t tag add x 180.1 180.end
 721     .t tag ranges x
 722 } {8.1 9.10 180.1 180.23}
 723 test btree-16.4 {add tag pushes root up to level 3 node} {
 724     .t tag remove x 1.0 end
 725     .t tag add y 1.1 2000.0
 726     .t tag add x 1.1 8.10
 727     .t tag add x 180.end 217.0
 728     list [.t tag ranges x] [.t tag ranges y]
 729 } {{1.1 8.10 180.23 217.0} {1.1 2000.0}}
 730 test btree-16.5 {add tag doesn't push root up} {
 731     .t tag remove x 1.0 end
 732     .t tag add x 1.1 8.10
 733     .t tag add x 2000.0 2000.3
 734     .t tag add x 180.end 217.0
 735     .t tag ranges x
 736 } {1.1 8.10 180.23 217.0 2000.0 2000.3}
 737 test btree-16.6 {two node splits at once pushes root up} {
 738     .t delete 1.0 end
 739     for {set i 1} {$i < 10} {incr i} {
 740         .t insert end "Line $i\n"
 741     }
 742     .t tag add x 8.0 8.end
 743     .t tag add y 9.0 end
 744     set x {}
 745     for {} {$i < 50} {incr i} {
 746         append x "Line $i\n"
 747     }
 748     .t insert end $x y
 749     list [.t tag ranges x] [.t tag ranges y]
 750 } {{8.0 8.6} {9.0 51.0}}
 751 # The following find bugs in the SearchStart procedures
 752 test btree-16.7 {Partial tag remove from before first range} {
 753     .t tag remove x 1.0 end
 754     .t tag add x 2.0 2.6
 755     .t tag remove x 1.0 2.0
 756     .t tag ranges x
 757 } {2.0 2.6}
 758 test btree-16.8 {Partial tag remove from before first range} {
 759     .t tag remove x 1.0 end
 760     .t tag add x 2.0 2.6
 761     .t tag remove x 1.0 2.1
 762     .t tag ranges x
 763 } {2.1 2.6}
 764 test btree-16.9 {Partial tag remove from before first range} {
 765     .t tag remove x 1.0 end
 766     .t tag add x 2.0 2.6
 767     .t tag remove x 1.0 2.3
 768     .t tag ranges x
 769 } {2.3 2.6}
 770 test btree-16.10 {Partial tag remove from before first range} {
 771     .t tag remove x 1.0 end
 772     .t tag add x 1.0 2.6
 773     .t tag remove x 1.0 2.5
 774     .t tag ranges x
 775 } {2.5 2.6}
 776 test btree-16.11 {StartSearchBack boundary case} {
 777     .t tag remove x 1.0 end
 778     .t tag add x 1.3 1.4
 779     .t tag prevr x 2.0 1.4
 780 } {}
 781 test btree-16.12 {StartSearchBack boundary case} {
 782     .t tag remove x 1.0 end
 783     .t tag add x 1.3 1.4
 784     .t tag prevr x 2.0 1.3
 785 } {1.3 1.4}
 786 test btree-16.13 {StartSearchBack boundary case} {
 787     .t tag remove x 1.0 end
 788     .t tag add x 1.0 1.4
 789     .t tag prevr x 1.3
 790 } {1.0 1.4}
 791
 792
 793 test btree-17.1 {remove tag does not push root down} {
 794     catch {destroy .t}
 795     text .t
 796     .t debug 0
 797     setupBig
 798     .t tag add x 1.1 5.10
 799     .t tag remove x 3.1 5.end
 800     .t tag ranges x
 801 } {1.1 3.1}
 802 test btree-17.2 {remove tag pushes root from level 1 to level 0} {
 803     .t tag remove x 1.0 end
 804     .t tag add x 1.1 8.10
 805     .t tag remove x 3.1 end
 806     .t tag ranges x
 807 } {1.1 3.1}
 808 test btree-17.3 {remove tag pushes root from level 2 to level 1} {
 809     .t tag remove x 1.0 end
 810     .t tag add x 1.1 180.10
 811     .t tag remove x 35.1 end
 812     .t tag ranges x
 813 } {1.1 35.1}
 814 test btree-17.4 {remove tag doesn't change level 2} {
 815     .t tag remove x 1.0 end
 816     .t tag add x 1.1 180.10
 817     .t tag remove x 35.1 180.0
 818     .t tag ranges x
 819 } {1.1 35.1 180.0 180.10}
 820 test btree-17.5 {remove tag pushes root from level 3 to level 0} {
 821     .t tag remove x 1.0 end
 822     .t tag add x 1.1 1.10
 823     .t tag add x 2000.1 2000.10
 824     .t tag remove x 1.0 2000.0
 825     .t tag ranges x
 826 } {2000.1 2000.10}
 827 test btree-17.6 {text deletion pushes root from level 3 to level 0} {
 828     .t tag remove x 1.0 end
 829     .t tag add x 1.1 1.10
 830     .t tag add x 2000.1 2000.10
 831     .t delete 1.0 "1000.0 lineend +1 char"
 832     .t tag ranges x
 833 } {1000.1 1000.10}
 834
 835 catch {destroy .t}
 836 text .t
 837 test btree-18.1 {tag search back, no tag} {
 838     .t insert 1.0 "Line 1 abcd efgh ijkl\n"
 839     .t tag prev x 1.1 1.1
 840 } {}
 841 test btree-18.2 {tag search back, start at existing range} {
 842     .t tag remove x 1.0 end
 843     .t tag add x 1.1 1.4
 844     .t tag add x 1.8 1.11
 845     .t tag add x 1.16
 846     .t tag prev x 1.1
 847 } {}
 848 test btree-18.3 {tag search back, end at existing range} {
 849     .t tag remove x 1.0 end
 850     .t tag add x 1.1 1.4
 851     .t tag add x 1.8 1.11
 852     .t tag add x 1.16
 853     .t tag prev x 1.3 1.1
 854 } {1.1 1.4}
 855 test btree-18.4 {tag search back, start within range} {
 856     .t tag remove x 1.0 end
 857     .t tag add x 1.1 1.4
 858     .t tag add x 1.8 1.11
 859     .t tag add x 1.16
 860     .t tag prev x 1.10 1.0
 861 } {1.8 1.11}
 862 test btree-18.5 {tag search back, start at end of range} {
 863     .t tag remove x 1.0 end
 864     .t tag add x 1.1 1.4
 865     .t tag add x 1.8 1.11
 866     .t tag add x 1.16
 867     list [.t tag prev x 1.4 1.0] [.t tag prev x 1.11 1.0]
 868 } {{1.1 1.4} {1.8 1.11}}
 869 test btree-18.6 {tag search back, start beyond range, same level 0 node} {
 870     .t tag remove x 1.0 end
 871     .t tag add x 1.1 1.4
 872     .t tag add x 1.8 1.11
 873     .t tag add x 1.16
 874     .t tag prev x 3.0
 875 } {1.16 1.17}
 876 test btree-18.7 {tag search back, outside any range} {
 877     .t tag remove x 1.0 end
 878     .t tag add x 1.1 1.4
 879     .t tag add x 1.16
 880     .t tag prev x 1.8 1.5
 881 } {}
 882 test btree-18.8 {tag search back, start at start of node boundary} {
 883     setupBig
 884     .t tag remove x 1.0 end
 885     .t tag add x 2.5 2.8
 886     .t tag prev x 19.0
 887 } {2.5 2.8}
 888 test btree-18.9 {tag search back, large complex btree spans} {
 889     .t tag remove x 1.0 end
 890     .t tag add x 1.3 1.end
 891     .t tag add x 200.0 220.0
 892     .t tag add x 500.0 520.0
 893     list [.t tag prev x end] [.t tag prev x 433.0]
 894 } {{500.0 520.0} {200.0 220.0}}
 895
 896
 897 destroy .t