Debugging

Dependencies

• [2] 52X5P7ND Cleaning up the unsized part
• [3] E4MD6T3L Proofreading and commenting of this crate (massive bug fixes included)
• [4] X3QVVQIS More debugging (del seems to work now)
• [5] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
• [6] QEUTVAZ4 Splitting btree::page
• [7] KX3WVNZW Testing/debugging "rebalance causes split of the root"
• [8] OFINGD26 implementing prev() on cursors (+ some cleanup)
• [9] H3FVSQIQ Unsized pages
• [10] Q7DRIBBR Debugging replace (which cannot be del+put)
• [11] LSQ6V7M6 Cleanup + docs
• [12] 6UVFCERM Formatting, debugging, etc.
• [13] SO25TWFL A few features for integrating it into Pijul
• [14] 7WJNSPEW Using the same definition of the "occupied" field uniform everywhere
• [15] LROAI3NB Two iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though)
• [16] TSMS6W4D Fully commented implementation of Sized nodes + massive cleanup
• [17] OTWDDJE7 Trait/type cleanup
• [18] HN6Z5DU4 Cleanup
• [19] WS4ZQM4R Debugging, tests, etc.
• [20] W26CFMAQ Improving safety of cursors
• [21] T7QB6QEP Adding debug.rs
• [22] XEU2QVLC Debugging after plugging this into Pijul
• [23] 73Z2UB3J Cleanup + comments
• [24] QYDGYIZR Split trait Representable into its mandatory part and an optional part
• [25] OP6SVMOD Resetting history
• [26] ESUI5EUZ Making as_page() unsafe
• [*] T73WR2BX Cleaner RC increments for keys and values containing references + more comments in `del`

Change contents

• replacement in sanakirja-core/src/btree/page_unsized.rs at line 544
  [4.10907]→[4.10907:10928](∅→∅)
  − } else {
  [4.10907]

  [2.16622]
  + } else if m.modified.skip_first {
• edit in sanakirja-core/src/btree/page_unsized.rs at line 554
  [4.1768]

  [4.11117]
  + } else {

  + let mut c1 = m.modified.c1.clone();

  + let mut l = m.modified.l;

  + if l == 0 {

  + Self::move_next(&mut c1);

  + l = m.modified.r;

  + }

  + return Ok(Op::Put(Put::Ok(Self::update_left_child(

  + txn,

  + m.modified.page,

  + m.modified.mutable,

  + &c1,

  + l,

  + )?)));
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 31
  [4.5051]→[4.1615:1679](∅→∅),[4.1976]→[4.1615:1679](∅→∅)
  − if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
  [4.5051]

  [4.23842]
  + let new_left = if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
• edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 50
  [4.24133]

  [4.24133]
  + };

  + // Append the middle element of the concatenation at the end

  + // of the left page. We know the left page to be mutable by

  + // now, and we also know there's enough space to do this.

  + let lc = PageCursor::after(&new_left.0);

  + if let Put::Ok(Ok { freed, page }) = <Page<K, V>>::put(

  + txn, new_left.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  + )? {

  + assert_eq!(freed, 0);

  + page

  + } else {

  + unreachable!()
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 63
  [4.24143]→[4.24143:24156](∅→∅)
  − } else {
  [4.24143]

  [4.5107]
  + } else if m.modified.skip_first {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 76
  [4.994]→[4.2109:2129](∅→∅),[4.2129]→[2.22005:22196](∅→∅),[2.22196]→[4.5210:5330](∅→∅),[4.2129]→[4.5210:5330](∅→∅),[4.5330]→[4.1759:1842](∅→∅),[4.1759]→[4.1759:1842](∅→∅),[4.2375]→[4.2375:2405](∅→∅),[4.2405]→[4.5331:5344](∅→∅)
  − page

  − };

  − // Append the middle element of the concatenation at the end of

  − // the left page. We know the left page to be mutable by now, and

  − // we also know there's enough space to do this.

  − let lc = PageCursor::after(&new_left.0);

  − let new_left = if let Put::Ok(Ok { freed, page }) = <Page<K, V>>::put(

  − txn, new_left.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  − )? {

  − assert_eq!(freed, 0);

  − page
  [4.994]

  [4.1018]
  + // Append the middle element of the concatenation at the end

  + // of the left page. We know the left page to be mutable by

  + // now, and we also know there's enough space to do this.

  + let lc = PageCursor::after(&page.0);

  + if let Put::Ok(Ok { freed, page }) = <Page<K, V>>::put(

  + txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  + )? {

  + assert_eq!(freed, 0);

  + page

  + } else {

  + unreachable!()

  + }

  +
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 90
  [4.1031]→[4.1031:1054](∅→∅)
  − unreachable!()
  [4.1031]

  [4.1054]
  + // Append the middle element of the concatenation at the end

  + // of the left page. We know the left page to be mutable by

  + // now, and we also know there's enough space to do this.

  + let is_dirty = m.modified.page.is_dirty();

  + let lc = PageCursor::after(&m.modified.page);

  + if let Put::Ok(Ok { freed, page }) = <Page<K, V>>::put(

  + txn, m.modified.page, m.modified.mutable, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  + )? {

  + if freed > 0 {

  + let b = if is_dirty { 1 } else { 0 };

  + freed_[0] = freed | b;

  + }

  + page

  + } else {

  + unreachable!()

  + }
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 159
  [4.5800]→[2.23455:23508](∅→∅)
  − if let Put::Ok(Ok { page, freed }) = P::put(
  [4.5800]

  [4.25958]
  + let new_right = if let Put::Ok(Ok { page, freed }) = P::put(
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 171
  [4.26188]→[2.23545:23611](∅→∅)
  − freed_[0] = if is_dirty { freed | 1 } else { freed };
  [4.26188]

  [4.26188]
  + if freed > 0 {

  + freed_[0] = if is_dirty { freed | 1 } else { freed };

  + }

  + page

  + } else {

  + unreachable!()

  + };

  + // Add the middle element of the concatenation as the first

  + // element of the right page. We know the right page is

  + // mutable, since we just modified it (hence the

  + // `assert_eq!(freed, 0)`.

  + if let Put::Ok(Ok { freed, page }) = P::put(

  + txn,

  + new_right.0,

  + true,

  + false,

  + &rc,

  + m.mid.0,

  + m.mid.1,

  + None,

  + r0,

  + rl,

  + )? {

  + debug_assert_eq!(freed, 0);
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 199
  [4.26259]→[4.26259:26272](∅→∅)
  − } else {
  [4.26259]

  [4.5856]
  + } else if m.modified.skip_first {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 211
  [4.1716]→[4.2830:2850](∅→∅),[4.2850]→[2.23716:23983](∅→∅),[4.3234]→[4.1987:2144](∅→∅),[4.6035]→[4.1987:2144](∅→∅),[2.23983]→[4.1987:2144](∅→∅),[4.1987]→[4.1987:2144](∅→∅),[4.2144]→[2.23984:24020](∅→∅),[2.24020]→[4.6036:6049](∅→∅),[4.3070]→[4.6036:6049](∅→∅)
  − page

  − };

  −

  − // Add the middle element of the concatenation as the first

  − // element of the right page. We know the right page is mutable,

  − // since we just modified it (hence the `assert_eq!(freed, 0)`.

  − let new_right = if let Put::Ok(Ok { freed, page }) = P::put(

  − txn,

  − new_right.0,

  − true,

  − false,

  − &rc,

  − m.mid.0,

  − m.mid.1,

  − None,

  − r0,

  − rl,

  − )? {

  − debug_assert_eq!(freed, 0);

  − page
  [4.1716]

  [4.26515]
  + // Add the middle element of the concatenation as the first

  + // element of the right page. We know the right page is

  + // mutable, since we just modified it (hence the

  + // `assert_eq!(freed, 0)`.

  + if let Put::Ok(Ok { freed, page }) = P::put(

  + txn,

  + page.0,

  + true,

  + false,

  + &rc,

  + m.mid.0,

  + m.mid.1,

  + None,

  + r0,

  + rl,

  + )? {

  + debug_assert_eq!(freed, 0);

  + page

  + } else {

  + unreachable!()

  + }
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 233
  [4.26528]→[4.26528:26551](∅→∅)
  − unreachable!()
  [4.26528]

  [4.26551]
  + let is_dirty = m.modified.page.is_dirty();

  + if let Put::Ok(Ok { freed, page }) = P::put(

  + txn,

  + m.modified.page,

  + m.modified.mutable,

  + false,

  + &rc,

  + m.mid.0,

  + m.mid.1,

  + None,

  + r0,

  + rl,

  + )? {

  + if freed > 0 {

  + freed_[0] = if is_dirty { freed | 1 } else { freed };

  + }

  + page

  + } else {

  + unreachable!()

  + }
• edit in sanakirja-core/src/btree/page.rs at line 530
  [4.3351]→[4.17114:17149](∅→∅),[4.3899]→[4.17114:17149](∅→∅),[4.5778]→[4.17114:17149](∅→∅),[4.17114]→[4.17114:17149](∅→∅),[4.17149]→[4.16862:16884](∅→∅),[4.16884]→[4.7950:7973](∅→∅),[4.17176]→[4.7950:7973](∅→∅),[4.7973]→[4.17251:17318](∅→∅),[4.17251]→[4.17251:17318](∅→∅)
  − return Ok(Op::Merged {

  − page,

  − freed,

  − marker: core::marker::PhantomData,

  − });
• replacement in sanakirja-core/src/btree/page.rs at line 555
  [4.3692]→[4.6288:6309](∅→∅),[4.6288]→[4.6288:6309](∅→∅)
  − } else {
  [4.3692]

  [4.17533]
  + } else if m.modified.skip_first {
• edit in sanakirja-core/src/btree/page.rs at line 569
  [4.7893]

  [4.3763]
  + } else {

  + let mut c1 = m.modified.c1.clone();

  + let mut l = m.modified.l;

  + if l == 0 {

  + Self::move_next(&mut c1);

  + l = m.modified.r;

  + }

  + return Ok(Op::Put(Put::Ok(Self::update_left_child(

  + txn,

  + m.modified.page,

  + m.modified.mutable,

  + &c1,

  + l,

  + )?)));
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 29
  [4.9149]→[4.8369:8433](∅→∅),[4.1271]→[4.8369:8433](∅→∅)
  − if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
  [4.9149]

  [4.1336]
  + let page = if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
• edit in sanakirja-core/src/btree/page/rebalance.rs at line 49
  [4.1627]

  [4.1627]
  + };

  + // Append the middle element of the concatenation at the end

  + // of the left page. We know the left page to be mutable by

  + // now, and we also know there's enough space to do this.

  + let lc = PageCursor::after(&page.0);

  + if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(

  + txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  + )? {

  + assert_eq!(freed, 0);

  + page

  + } else {

  + unreachable!()
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 62
  [4.1637]→[4.1637:1650](∅→∅)
  − } else {
  [4.1637]

  [4.9205]
  + } else if m.modified.skip_first {
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 76
  [4.8163]→[4.8163:8176](∅→∅),[4.4690]→[4.1729:1736](∅→∅),[4.8176]→[4.1729:1736](∅→∅),[4.1729]→[4.1729:1736](∅→∅),[4.1736]→[4.22981:23173](∅→∅),[4.23173]→[4.9308:9428](∅→∅),[4.1736]→[4.9308:9428](∅→∅),[4.9428]→[4.8513:8596](∅→∅),[4.8513]→[4.8513:8596](∅→∅),[4.8596]→[4.9429:9472](∅→∅)
  − page

  − };

  −

  − // Append the middle element of the concatenation at the end of

  − // the left page. We know the left page to be mutable by now, and

  − // we also know there's enough space to do this.

  − let lc = PageCursor::after(&new_left.0);

  − let new_left = if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(

  − txn, new_left.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  − )? {

  − assert_eq!(freed, 0);

  − page
  [4.8163]

  [4.2754]
  + // Append the middle element of the concatenation at the end

  + // of the left page. We know the left page to be mutable by

  + // now, and we also know there's enough space to do this.

  + let lc = PageCursor::after(&page.0);

  + if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(

  + txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  + )? {

  + assert_eq!(freed, 0);

  + page

  + } else {

  + unreachable!()

  + }
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 89
  [4.2767]→[4.2767:2790](∅→∅)
  − unreachable!()
  [4.2767]

  [4.2790]
  + let is_dirty = m.modified.page.is_dirty();

  + let lc = PageCursor::after(&m.modified.page);

  + if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(

  + txn, m.modified.page, m.modified.mutable, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

  + )? {

  + if freed > 0 {

  + debug!("freed {:?} {:?}", line!(), freed);

  + let b = if is_dirty { 1 } else { 0 };

  + freed_[0] = freed | b

  + }

  + page

  + } else {

  + unreachable!()

  + }
• replacement in sanakirja-core/src/btree/page/put.rs at line 22
  [2.39373]→[2.39373:39450](∅→∅)
  − if mutable && is_dirty && L::can_alloc::<K, V>(header(page.as_page())) {
  [2.39373]

  [2.39450]
  + if mutable && is_dirty && L::can_alloc::<K, V>(hdr) {
• replacement in sanakirja-core/src/btree/page/put.rs at line 46
  [4.7103]→[2.39971:40015](∅→∅)
  − } else if L::can_compact::<K, V>(hdr) {
  [4.7103]

  [2.40015]
  + } else if replace || L::can_compact::<K, V>(hdr) {
• edit in sanakirja-core/src/btree/del.rs at line 473
  [28.5671]

  [28.5671]
  + if !mod_is_left {

  + let curs = cursor.current_mut();

  + P::move_prev(&mut curs.cursor);

  + }
• replacement in sanakirja-core/src/btree/del.rs at line 717
  [4.13152]→[4.13383:13649](∅→∅)
  − // If there's no insertion, and `m.l == 0`, we are

  − // actually deleting an entry of the root, and so we need

  − // to update the right child of the current entry. The

  − // following moves one step to the right and updates:
  [4.13152]

  [4.13152]
  + // If there's no insertion, and `m.l == 0`, we need to

  + // update the right child of the current entry. The

  + // following moves one step to the right and updates the

  + // left child:
• replacement in sanakirja-core/src/btree/cursor.rs at line 36
  [4.65195]→[4.38910:38975](∅→∅)
  − impl<K: ?Sized, V: ?Sized, P: BTreePage<K, V>> Cursor<K, V, P> {
  [4.65195]

  [4.38975]
  + impl<K: ?Sized + core::fmt::Debug, V: ?Sized, P: BTreePage<K, V>> Cursor<K, V, P> {
• edit in sanakirja/src/environment/muttxn.rs at line 355
  [4.13077]

  [4.86200]
  + assert_ne!(offset, 0);
• edit in sanakirja/src/environment/muttxn.rs at line 364
  [4.13123]

  [4.86294]
  + assert_ne!(offset, 0);
• edit in sanakirja/src/environment/muttxn.rs at line 441
  [4.37584]

  [3.18520]
  + assert_ne!(offset, 0);
• edit in sanakirja/src/environment/muttxn.rs at line 451
  [4.37871]

  [3.18574]
  + assert_ne!(offset, 0);
• replacement in sanakirja/src/debug.rs at line 53
  [4.1275]→[4.1275:1310](∅→∅)
  − {}\";\ncolor=black;",
  [4.1275]

  [4.1310]
  + {} {}\";\ncolor=black;",
• replacement in sanakirja/src/debug.rs at line 56
  [4.1354]→[4.1354:1392](∅→∅)
  − txn.rc(p.offset).unwrap()
  [4.1354]

  [4.1392]
  + txn.rc(p.offset).unwrap(),

  + unsafe { u64::from_le(*(p.data as *const u64).add(1)) & 0xfff }