3 # The author disclaims copyright to this source code. In place of
4 # a legal notice, here is a blessing:
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.
10 #***********************************************************************
11 # This file implements regression tests for SQLite library. The
12 # focus of this script is btree database backend
14 # $Id: btree.test,v 1.35 2005/01/11 10:25:07 danielk1977 Exp $
17 set testdir [file dirname $argv0]
18 source $testdir/tester.tcl
20 ifcapable default_autovacuum {
25 # Basic functionality. Open and close a database.
28 file delete -force test1.bt
29 file delete -force test1.bt-journal
30 set rc [catch {btree_open test1.bt 2000 0} ::b1]
33 # The second element of the list returned by btree_pager_stats is the
34 # number of pages currently checked out. We'll be checking this value
35 # frequently during this test script, to make sure the btree library
36 # is properly releasing the pages it checks out, and thus avoiding
40 lindex [btree_pager_stats $::b1] 1
43 set rc [catch {btree_open test1.bt 2000 0} ::b2]
46 set rc [catch {btree_close $::b2} msg]
50 # Do an insert and verify that the database file grows in size.
53 set rc [catch {btree_begin_transaction $::b1} msg]
57 lindex [btree_pager_stats $::b1] 1
60 set rc [catch {btree_cursor $::b1 1 1} ::c1]
61 if {$rc} {lappend rc $::c1}
65 set rc [catch {btree_insert $::c1 100 1.00} msg]
69 btree_move_to $::c1 100
76 set rc [catch {btree_close_cursor $::c1} msg]
80 set rc [catch {btree_commit $::b1} msg]
87 lindex [btree_pager_stats $::b1] 1
90 # Reopen the database and attempt to read the record that we wrote.
93 set rc [catch {btree_cursor $::b1 1 1} ::c1]
94 if {$rc} {lappend rc $::c1}
98 btree_move_to $::c1 99
101 btree_move_to $::c1 101
104 btree_move_to $::c1 100
113 lindex [btree_pager_stats $::b1] 1
116 # Do some additional inserts
119 btree_begin_transaction $::b1
120 btree_insert $::c1 200 2.00
121 btree_move_to $::c1 200
124 do_test btree-3.1.1 {
125 lindex [btree_pager_stats $::b1] 1
128 btree_insert $::c1 300 3.00
129 btree_move_to $::c1 300
133 btree_insert $::c1 400 4.00
134 btree_move_to $::c1 400
138 btree_insert $::c1 500 5.00
139 btree_move_to $::c1 500
143 btree_insert $::c1 600 6.00
144 btree_move_to $::c1 600
147 #btree_page_dump $::b1 2
149 set rc [btree_move_to $::c1 0]
193 do_test btree-3.20.1 {
197 do_test btree-3.20.2 {
200 # This test case used to test that one couldn't request data from an
201 # invalid cursor. That is now an assert()ed condition.
203 # do_test btree-3.21 {
204 # set rc [catch {btree_data $::c1} res]
206 # } {1 SQLITE_INTERNAL}
208 # Commit the changes, reopen and reread the data
211 set rc [catch {btree_close_cursor $::c1} msg]
214 do_test btree-3.22.1 {
215 lindex [btree_pager_stats $::b1] 1
218 set rc [catch {btree_commit $::b1} msg]
221 do_test btree-3.23.1 {
222 lindex [btree_pager_stats $::b1] 1
228 set rc [catch {btree_cursor $::b1 1 1} ::c1]
229 if {$rc} {lappend rc $::c1}
232 do_test btree-3.25.1 {
233 lindex [btree_pager_stats $::b1] 1
236 set rc [btree_move_to $::c1 0]
284 # This test case used to test that requesting data from an invalid cursor
285 # returned SQLITE_INTERNAL. That is now an assert()ed condition.
287 # do_test btree-3.40 {
288 # set rc [catch {btree_data $::c1} res]
290 # } {1 SQLITE_INTERNAL}
292 lindex [btree_pager_stats $::b1] 1
299 btree_begin_transaction $::b1
300 btree_move_to $::c1 100
303 do_test btree-4.1.1 {
304 lindex [btree_pager_stats $::b1] 1
310 btree_move_to $::c1 100
322 btree_move_to $::c1 0
325 set key [btree_key $::c1]
326 if {[btree_eof $::c1]} break
328 lappend r [btree_data $::c1]
332 } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
334 # Commit and make sure the delete is still there.
338 btree_move_to $::c1 0
341 set key [btree_key $::c1]
342 if {[btree_eof $::c1]} break
344 lappend r [btree_data $::c1]
348 } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
350 # Completely close the database and reopen it. Then check
354 lindex [btree_pager_stats $::b1] 1
357 btree_close_cursor $::c1
358 lindex [btree_pager_stats $::b1] 1
362 set ::b1 [btree_open test1.bt 2000 0]
363 set ::c1 [btree_cursor $::b1 1 1]
364 lindex [btree_pager_stats $::b1] 1
370 set key [btree_key $::c1]
371 if {[btree_eof $::c1]} break
373 lappend r [btree_data $::c1]
377 } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
379 # Try to read and write meta data
383 } {0 0 0 0 0 0 0 0 0 0}
386 btree_update_meta $::b1 0 1 2 3 4 5 6 7 8 9
391 btree_begin_transaction $::b1
393 btree_update_meta $::b1 0 1 2 3 0 5 6 7 8 9
399 } {0 1 2 3 0 5 6 7 8 9}
401 btree_close_cursor $::c1
404 } {0 0 0 0 0 0 0 0 0 0}
406 btree_begin_transaction $::b1
407 btree_update_meta $::b1 0 10 20 30 0 50 60 70 80 90
410 } {0 10 20 30 0 50 60 70 80 90}
412 proc select_all {cursor} {
415 while {![btree_eof $cursor]} {
416 set key [btree_key $cursor]
418 lappend r [btree_data $cursor]
423 proc select_keys {cursor} {
426 while {![btree_eof $cursor]} {
427 set key [btree_key $cursor]
434 # Try to create a new table in the database file
437 set rc [catch {btree_create_table $::b1 0} msg]
441 btree_begin_transaction $::b1
442 set ::t2 [btree_create_table $::b1 0]
444 do_test btree-6.2.1 {
445 lindex [btree_pager_stats $::b1] 1
447 do_test btree-6.2.2 {
448 set ::c2 [btree_cursor $::b1 $::t2 1]
449 lindex [btree_pager_stats $::b1] 1
451 do_test btree-6.2.3 {
452 btree_insert $::c2 ten 10
453 btree_move_to $::c2 ten
458 set ::c1 [btree_cursor $::b1 1 1]
459 lindex [btree_pager_stats $::b1] 1
461 do_test btree-6.3.1 {
463 } {200 2.00 300 3.00 400 4.00 500 5.00 600 6.00}
464 #btree_page_dump $::b1 3
469 # Drop the new table, then create it again anew.
472 btree_begin_transaction $::b1
475 btree_close_cursor $::c2
477 do_test btree-6.6.1 {
478 lindex [btree_pager_stats $::b1] 1
481 btree_close_cursor $::c1
482 btree_drop_table $::b1 $::t2
484 do_test btree-6.7.1 {
485 lindex [btree_get_meta $::b1] 0
488 set ::t2 [btree_create_table $::b1 0]
490 do_test btree-6.8.1 {
491 lindex [btree_get_meta $::b1] 0
494 set ::c2 [btree_cursor $::b1 $::t2 1]
495 lindex [btree_pager_stats $::b1] 1
498 # This test case used to test that requesting the key from an invalid cursor
499 # returned an empty string. But that is now an assert()ed condition.
501 # do_test btree-6.9.1 {
502 # btree_move_to $::c2 {}
506 # If we drop table 1 it just clears the table. Table 1 always exists.
509 btree_close_cursor $::c2
510 btree_drop_table $::b1 1
511 set ::c2 [btree_cursor $::b1 $::t2 1]
512 set ::c1 [btree_cursor $::b1 1 1]
524 btree_close_cursor $::c2
525 lindex [btree_pager_stats $::b1] 1
528 # Check to see that pages defragment properly. To do this test we will
530 # 1. Fill the first page of table 1 with data.
531 # 2. Delete every other entry of table 1.
532 # 3. Insert a single entry that requires more contiguous
533 # space than is available.
536 btree_begin_transaction $::b1
542 # Each record will be 10 bytes in size.
543 # + 100 bytes of database header
544 # + 8 bytes of table header
545 # + 91*10=910 bytes of cells
546 # Totals 1018 bytes. 6 bytes left over
547 # Keys are 1000 through 1090.
548 for {set i 1000} {$i<1091} {incr i} {
550 set data [format %5d $i]
551 btree_insert $::c1 $key $data
553 lrange [btree_cursor_info $::c1] 4 5
555 #btree_tree_dump $::b1 1
557 for {set i 1001} {$i<1091} {incr i 2} {
558 btree_move_to $::c1 $i
561 # Freed 45 blocks. Total freespace is 456
562 # Keys remaining are even numbers between 1000 and 1090, inclusive
563 lrange [btree_cursor_info $::c1] 4 5
565 #btree_tree_dump $::b1 1
567 # The largest free block is 8 bytes long. But there is also a
568 # huge hole between the cell pointer array and the cellcontent.
569 # But if we insert a large enough record, it should force a defrag.
576 btree_insert $::c1 2000 $data
577 btree_move_to $::c1 2000
581 lrange [btree_cursor_info $::c1] 4 5
583 #btree_tree_dump $::b1 1
585 # Delete an entry to make a hole of a known size, then immediately recreate
586 # that entry. This tests the path into allocateSpace where the hole exactly
587 # matches the size of the desired space.
589 # Keys are even numbers between 1000 and 1090 and one record of 2000.
590 # There are 47 keys total.
593 btree_move_to $::c1 1006
595 btree_move_to $::c1 1010
599 lrange [btree_cursor_info $::c1] 4 5
600 } {363 2} ;# Create two new holes of 10 bytes each
601 #btree_page_dump $::b1 1
603 btree_insert $::c1 1006 { 1006}
604 lrange [btree_cursor_info $::c1] 4 5
605 } {353 1} ;# Filled in the first hole
606 btree_page_dump $::b1 1
608 # Make sure the freeSpace() routine properly coaleses adjacent memory blocks
611 btree_move_to $::c1 1012
613 lrange [btree_cursor_info $::c1] 4 5
614 } {363 2} ;# Coalesce with the hole before
615 btree_page_dump $::b1 1
618 btree_move_to $::c1 1008
620 lrange [btree_cursor_info $::c1] 4 5
621 } {468 2} ;# Coalesce with whole after
623 btree_move_to $::c1 1030
625 lrange [btree_cursor_info $::c1] 4 5
626 } {478 3} ;# Make a new hole
628 btree_move_to $::c1 1034
630 lrange [btree_cursor_info $::c1] 4 5
631 } {488 4} ;# Make another hole
633 btree_move_to $::c1 1032
635 lrange [btree_cursor_info $::c1] 4 5
636 } {498 3} ;# The freed space should coalesce on both ends
637 #btree_page_dump $::b1 2
639 lindex [btree_pager_stats $::b1] 1
643 # Check to see that data on overflow pages work correctly.
646 set data "*** This is a very long key "
647 while {[string length $data]<1234} {append data $data}
649 btree_insert $::c1 2020 $data
651 #btree_page_dump $::b1 1
652 do_test btree-8.1.1 {
653 lindex [btree_pager_stats $::b1] 1
655 #btree_pager_ref_dump $::b1
657 btree_move_to $::c1 2020
658 string length [btree_data $::c1]
659 } [string length $::data]
666 do_test btree-8.4.1 {
667 lindex [btree_get_meta $::b1] 0
668 } [expr {int(([string length $::data]-238+1019)/1020)}]
669 do_test btree-8.4.2 {
670 btree_integrity_check $::b1 1 2
673 set data "*** This is an even longer key "
674 while {[string length $data]<2000} {append data $data}
677 btree_insert $::c1 2030 $data
680 btree_move_to $::c1 2030
681 string length [btree_data $::c1]
682 } [string length $::data]
690 do_test btree-8.9.1 {
691 btree_close_cursor $::c1
693 set ::b1 [btree_open test1.bt 2000 0]
694 set ::c1 [btree_cursor $::b1 1 1]
695 btree_move_to $::c1 2030
698 do_test btree-8.9.2 {
699 btree_integrity_check $::b1 1 2
702 btree_begin_transaction $::b1
706 lindex [btree_get_meta $::b1] 0
709 # Now check out keys on overflow pages.
711 do_test btree-8.12.1 {
712 set ::keyprefix "This is a long prefix to a key "
713 while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix}
714 btree_close_cursor $::c1
715 btree_clear_table $::b1 2
716 lindex [btree_get_meta $::b1] 0
718 do_test btree-8.12.2 {
719 btree_integrity_check $::b1 1 2
721 do_test btree-8.12.3 {
722 set ::c1 [btree_cursor $::b1 2 1]
723 btree_insert $::c1 ${::keyprefix}1 1
731 btree_insert $::c1 ${::keyprefix}2 2
732 btree_insert $::c1 ${::keyprefix}3 3
737 btree_move_to $::c1 ${::keyprefix}2
741 btree_move_to $::c1 ${::keyprefix}1
745 btree_move_to $::c1 ${::keyprefix}3
749 lindex [btree_get_meta $::b1] 0
752 btree_move_to $::c1 ${::keyprefix}2
755 #btree_page_dump $::b1 2
761 #btree_page_dump $::b1 2
763 lindex [btree_get_meta $::b1] 0
766 lindex [btree_pager_stats $::b1] 1
768 do_test btree-8.23.1 {
769 btree_close_cursor $::c1
770 btree_drop_table $::b1 2
771 btree_integrity_check $::b1 1
773 do_test btree-8.23.2 {
774 btree_create_table $::b1 0
776 do_test btree-8.23.3 {
777 set ::c1 [btree_cursor $::b1 2 1]
778 lindex [btree_get_meta $::b1] 0
781 lindex [btree_pager_stats $::b1] 1
783 #btree_pager_ref_dump $::b1
785 btree_integrity_check $::b1 1 2
788 # Check page splitting logic
791 for {set i 1} {$i<=19} {incr i} {
792 set key [format %03d $i]
793 set data "*** $key *** $key *** $key *** $key ***"
794 btree_insert $::c1 $key $data
797 #btree_tree_dump $::b1 2
798 #btree_pager_ref_dump $::b1
799 #set pager_refinfo_enable 1
801 btree_insert $::c1 020 {*** 020 *** 020 *** 020 *** 020 ***}
803 } {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020}
804 #btree_page_dump $::b1 2
805 #btree_pager_ref_dump $::b1
806 #set pager_refinfo_enable 0
808 # The previous "select_keys" command left the cursor pointing at the root
809 # page. So there should only be two pages checked out. 2 (the root) and
811 do_test btree-9.2.1 {
812 lindex [btree_pager_stats $::b1] 1
814 for {set i 1} {$i<=20} {incr i} {
815 do_test btree-9.3.$i.1 [subst {
816 btree_move_to $::c1 [format %03d $i]
819 do_test btree-9.3.$i.2 [subst {
820 btree_move_to $::c1 [format %03d $i]
821 string range \[btree_data $::c1\] 0 10
822 }] "*** [format %03d $i] ***"
824 do_test btree-9.4.1 {
825 lindex [btree_pager_stats $::b1] 1
828 # Check the page joining logic.
830 #btree_page_dump $::b1 2
831 #btree_pager_ref_dump $::b1
832 do_test btree-9.4.2 {
833 btree_move_to $::c1 005
836 #btree_page_dump $::b1 2
837 for {set i 1} {$i<=19} {incr i} {
839 do_test btree-9.5.$i.1 [subst {
840 btree_move_to $::c1 [format %03d $i]
843 do_test btree-9.5.$i.2 [subst {
844 btree_move_to $::c1 [format %03d $i]
845 string range \[btree_data $::c1\] 0 10
846 }] "*** [format %03d $i] ***"
848 #btree_pager_ref_dump $::b1
850 btree_close_cursor $::c1
851 lindex [btree_pager_stats $::b1] 1
854 btree_integrity_check $::b1 1 2
858 lindex [btree_pager_stats $::b1] 1
861 btree_integrity_check $::b1 1 2
865 set ::b1 [btree_open test1.bt 2000 0]
866 btree_integrity_check $::b1 1 2
869 # Create a tree of depth two. That is, there is a single divider entry
870 # on the root pages and two leaf pages. Then delete the divider entry
874 btree_begin_transaction $::b1
875 btree_clear_table $::b1 2
876 lindex [btree_pager_stats $::b1] 1
879 set ::c1 [btree_cursor $::b1 2 1]
880 lindex [btree_pager_stats $::b1] 1
883 for {set i 1} {$i<=30} {incr i} {
884 set key [format %03d $i]
885 set data "*** $key *** $key *** $key *** $key ***"
886 btree_insert $::c1 $key $data
889 } {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030}
890 #btree_tree_dump $::b1 2
892 # The divider entry is 012. This is found by uncommenting the
893 # btree_tree_dump call above and looking at the tree. If the page size
894 # changes, this test will no longer work.
895 btree_move_to $::c1 012
898 } {001 002 003 004 005 006 007 008 009 010 011 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030}
899 #btree_pager_ref_dump $::b1
900 #btree_tree_dump $::b1 2
901 for {set i 1} {$i<=30} {incr i} {
902 # Check the number of unreference pages. This should be 3 in most cases,
903 # but 2 when the cursor is pointing to the divider entry which is now 013.
904 do_test btree-10.5.$i {
905 btree_move_to $::c1 [format %03d $i]
906 lindex [btree_pager_stats $::b1] 1
907 } [expr {$i==13?2:3}]
908 #btree_pager_ref_dump $::b1
909 #btree_tree_dump $::b1 2
912 # Create a tree with lots more pages
916 for {set i 31} {$i<=2000} {incr i} {
917 do_test btree-11.1.$i.1 {
918 set key [format %03d $i]
919 set ::data "*** $key *** $key *** $key *** $key ***"
920 btree_insert $::c1 $key $data
921 btree_move_to $::c1 $key
924 do_test btree-11.1.$i.2 {
927 set ::key [format %03d [expr {$i/2}]]
928 if {$::key=="012"} {set ::key 013}
929 do_test btree-11.1.$i.3 {
930 btree_move_to $::c1 $::key
937 # Make sure our reference count is still correct.
940 btree_close_cursor $::c1
941 lindex [btree_pager_stats $::b1] 1
944 set ::c1 [btree_cursor $::b1 2 1]
945 lindex [btree_pager_stats $::b1] 1
948 # Delete the dividers on the root page
950 #btree_page_dump $::b1 2
952 btree_move_to $::c1 1667
954 btree_move_to $::c1 1667
955 set k [btree_key $::c1]
957 set k [btree_next $::c1]
961 #btree_page_dump $::b1 2
963 # Change the data on an intermediate node such that the node becomes overfull
964 # and has to split. We happen to know that intermediate nodes exist on
965 # 337, 401 and 465 by the btree_page_dumps above
968 set ::data {This is going to be a very long data segment}
969 append ::data $::data
970 append ::data $::data
972 btree_insert $::c1 337 $::data
973 btree_move_to $::c1 337
977 btree_insert $::c1 401 $::data
978 btree_move_to $::c1 401
982 btree_insert $::c1 465 $::data
983 btree_move_to $::c1 465
987 btree_move_to $::c1 337
998 btree_move_to $::c1 464
1001 do_test btree-12.8 {
1005 do_test btree-12.9 {
1009 do_test btree-12.10 {
1010 btree_move_to $::c1 400
1013 do_test btree-12.11 {
1017 do_test btree-12.12 {
1021 # btree_commit $::b1
1022 # btree_tree_dump $::b1 1
1023 do_test btree-13.1 {
1024 btree_integrity_check $::b1 1 2
1029 # 1. Do some deletes from the 3-layer tree
1030 # 2. Commit and reopen the database
1031 # 3. Read every 15th entry and make sure it works
1032 # 4. Implement btree_sanity and put it throughout this script
1035 do_test btree-15.98 {
1036 btree_close_cursor $::c1
1037 lindex [btree_pager_stats $::b1] 1
1039 do_test btree-15.99 {
1040 btree_rollback $::b1
1041 lindex [btree_pager_stats $::b1] 1
1043 btree_pager_ref_dump $::b1
1045 # Miscellaneous tests.
1047 # btree-16.1 - Check that a statement cannot be started if a transaction
1049 # btree-16.2 - Check that it is an error to request more payload from a
1050 # btree entry than the entry contains.
1051 do_test btree-16.1 {
1052 catch {btree_begin_statement $::b1} msg
1056 do_test btree-16.2 {
1057 btree_begin_transaction $::b1
1058 set ::c1 [btree_cursor $::b1 2 1]
1059 btree_insert $::c1 1 helloworld
1060 btree_close_cursor $::c1
1063 do_test btree-16.3 {
1064 set ::c1 [btree_cursor $::b1 2 1]
1067 do_test btree-16.4 {
1068 catch {btree_data $::c1 [expr [btree_payload_size $::c1] + 10]} msg
1072 if {$tcl_platform(platform)=="unix"} {
1073 do_test btree-16.5 {
1075 set ::origperm [file attributes test1.bt -permissions]
1076 file attributes test1.bt -permissions o-w,g-w,a-w
1077 set ::b1 [btree_open test1.bt 2000 0]
1078 catch {btree_cursor $::b1 2 1} msg
1079 file attributes test1.bt -permissions $::origperm
1081 set ::b1 [btree_open test1.bt 2000 0]
1086 do_test btree-16.6 {
1087 set ::c1 [btree_cursor $::b1 2 1]
1088 set ::c2 [btree_cursor $::b1 2 1]
1089 btree_begin_transaction $::b1
1090 for {set i 0} {$i<100} {incr i} {
1091 btree_insert $::c1 $i [string repeat helloworld 10]
1094 btree_insert $::c1 100 [string repeat helloworld 10]
1097 do_test btree-16.7 {
1098 btree_close_cursor $::c1
1099 btree_close_cursor $::c2
1101 set ::c1 [btree_cursor $::b1 2 1]
1102 catch {btree_insert $::c1 101 helloworld} msg
1105 do_test btree-16.8 {
1107 catch {btree_delete $::c1} msg
1110 do_test btree-16.9 {
1111 btree_close_cursor $::c1
1112 btree_begin_transaction $::b1
1113 set ::c1 [btree_cursor $::b1 2 0]
1114 catch {btree_insert $::c1 101 helloworld} msg
1117 do_test btree-16.10 {
1118 catch {btree_delete $::c1} msg
1121 do_test btree-16.11 {
1122 btree_close_cursor $::c1
1123 set ::c2 [btree_cursor $::b1 2 1]
1124 set ::c1 [btree_cursor $::b1 2 0]
1125 catch {btree_insert $::c2 101 helloworld} msg
1128 do_test btree-16.12 {
1130 catch {btree_delete $::c2} msg
1133 do_test btree-16.13 {
1134 catch {btree_clear_table $::b1 2} msg
1137 do_test btree-16.14 {
1138 btree_close_cursor $::c1
1139 btree_close_cursor $::c2
1141 catch {btree_clear_table $::b1 2} msg
1144 do_test btree-16.15 {
1145 catch {btree_drop_table $::b1 2} msg
1148 do_test btree-16.16 {
1149 btree_begin_transaction $::b1
1150 set ::c1 [btree_cursor $::b1 2 0]
1151 catch {btree_drop_table $::b1 2} msg
1155 do_test btree-99.1 {