Refactoring, drop and the Check trait

pmeunier

Nov 23, 2021, 11:03 AM

OHG5NX6KVGKNA7S7SU3MTPOZCN4RRZK2SGZWZ5LIRXUMCYIPUHIAC

Dependencies

• [2] 3QM7P3RR Writing the reference counts when committing
• [3] ECPAFJSB add env_borrow for Txn and MutTxn
• [4] BYI23QWI More tests
• [5] 4Z4GEJTF Version bump
• [6] 7T2CCH3P Fixing a segfault (wrong offset in page_unsized::del)
• [7] 2ZRCQBXP Version bump
• [8] J7LJZBME Setting reverse cursor to last by default
• [9] R27IKHPA Checking equality when we delete
• [10] ACB4A27Z Code coverage
• [11] H3FVSQIQ Unsized pages
• [12] XEU2QVLC Debugging after plugging this into Pijul
• [13] T73WR2BX Cleaner RC increments for keys and values containing references + more comments in `del`
• [14] YWFYZNLZ Cleanup + inter-process concurrency
• [15] GGEFV4YY Some page splits were not properly handled in deletions
• [16] T7QB6QEP Adding debug.rs
• [17] 52X5P7ND Cleaning up the unsized part
• [18] 5LSYTRQ6 More docs, example, and fixing the free page diagnostic function for mutable transactions
• [19] TSMS6W4D Fully commented implementation of Sized nodes + massive cleanup
• [20] FZBLNBGN Diagnostic tools (add_refs, check_free) + cleanup
• [21] Z33OHFPA Version bump
• [22] OTWDDJE7 Trait/type cleanup
• [23] HN6Z5DU4 Cleanup
• [24] LSQ6V7M6 Cleanup + docs
• [25] QYDGYIZR Split trait Representable into its mandatory part and an optional part
• [26] DASFQGOR Debugging
• [27] FQ567GAX Version bumps
• [28] 77TAHKV4 Fixing a logical error (again) in del
• [29] S4V4QZ5C Debugging reference-counting for put
• [30] E4MD6T3L Proofreading and commenting of this crate (massive bug fixes included)
• [31] WS4ZQM4R Debugging, tests, etc.
• [32] G7K2WSVY Fixing unsized iterators
• [33] KMT3MF5N Drop a database
• [34] P5NWMJ2H Version bump
• [35] NXMFNPZ7 Comments + debugging drop
• [36] CCNPHVQC Cleanup, comments, renaming
• [37] OP6SVMOD Resetting history
• [38] 6UVFCERM Formatting, debugging, etc.
• [39] QEUTVAZ4 Splitting btree::page
• [40] W26CFMAQ Improving safety of cursors
• [41] OFINGD26 implementing prev() on cursors (+ some cleanup)
• [42] W2MIZD5B Single file databases + CRC for the root pages (checking the other pages makes everything very slow)
• [43] PUOGOIJ3 Debugging, impls and version bump
• [44] DEKK3RUI Fixing a bug when splitting unsized pages
• [45] SYURNHHL Adding the `put_mut` and `set_left_child` methods
• [46] GPP7KJSF Version bump
• [47] RV2L6CZW A few comments
• [48] ESUI5EUZ Making as_page() unsafe
• [49] ONES3V46 reference counting works for put

Change contents

• file move: sanakirja-core (d--r------) → sanakirja-core (d--r------)
  [1.0]

  [6.17]
• edit in sanakirja-core/src/lib.rs at line 59
  [6.212]

  [6.1363]
  + /// If this value is an offset to another page at offset `offset`,

  + /// return `Some(offset)`. Return `None` else.

  + fn drop<T: AllocPage>(&self, txn: &mut T) -> Result<(), T::Error> {

  + for p in self.page_references() {

  + txn.decr_rc(p)?;

  + }

  + Ok(())

  + }

  +
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 214
  [6.7142]→[6.7142:7804](∅→∅)
  − let s = core::slice::from_raw_parts(

  − page.data.as_ptr().add(HDR) as *const u16,

  − hdr.n() as usize,

  − );

  − if let Some(v0) = v0 {

  − s.binary_search_by(|&off| {

  − let off = u16::from_le(off);

  − let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

  − let k = K::from_raw_ptr(txn, k as *const u8);

  − match k.compare(txn, k0) {

  − Ordering::Equal => {

  − let v = V::from_raw_ptr(txn, v as *const u8);

  − v.compare(txn, v0)

  − }

  − cmp => cmp,
  [6.7142]

  [6.7804]
  + lookup_leaf(txn, page, k0, v0, hdr)

  + } else {

  + lookup_internal(txn, page, k0, v0, hdr)

  + }

  + }

  +

  + unsafe fn lookup_internal<T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

  + txn: &T,

  + page: crate::Page,

  + k0: &K,

  + v0: Option<&V>,

  + hdr: &header::Header,

  + ) -> Result<usize, usize> {

  + let s = core::slice::from_raw_parts(

  + page.data.as_ptr().add(HDR) as *const u64,

  + hdr.n() as usize,

  + );

  + if let Some(v0) = v0 {

  + s.binary_search_by(|&off| {

  + let off = u64::from_le(off) & 0xfff;

  + let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

  + let k = K::from_raw_ptr(txn, k);

  + match k.compare(txn, k0) {

  + Ordering::Equal => {

  + let v = V::from_raw_ptr(txn, v);

  + v.compare(txn, v0)
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 241
  [6.7822]→[6.7822:8080](∅→∅),[6.8080]→[6.26:158](∅→∅)
  − })

  − } else {

  − s.binary_search_by(|&off| {

  − let off = u16::from_le(off);

  − let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

  − let k = K::from_raw_ptr(txn, k);

  − match k.compare(txn, k0) {

  − Ordering::Equal => Ordering::Greater,

  − cmp => cmp
  [6.7822]

  [6.158]
  + cmp => cmp,

  + }

  + })

  + } else {

  + match s.binary_search_by(|&off| {

  + let off = u64::from_le(off) & 0xfff;

  + let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

  + let k = K::from_raw_ptr(txn, k);

  + k.compare(txn, k0)

  + }) {

  + Err(i) => Err(i),

  + Ok(mut i) => {

  + // Rewind if there are multiple matching keys.

  + while i > 0 {

  + let off = u64::from_le(s[i-1]) & 0xfff;

  + let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

  + let k = K::from_raw_ptr(txn, k);

  + if let Ordering::Equal = k.compare(txn, k0) {

  + i -= 1

  + } else {

  + break

  + }
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 264
  [6.176]→[6.8115:8130](∅→∅),[6.8115]→[6.8115:8130](∅→∅)
  − })
  [6.176]

  [6.8130]
  + Ok(i)

  + }
• edit in sanakirja-core/src/btree/page_unsized.rs at line 267
  [6.8140]

  [6.8140]
  + }

  + }

  +

  +

  + unsafe fn lookup_leaf<T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

  + txn: &T,

  + page: crate::Page,

  + k0: &K,

  + v0: Option<&V>,

  + hdr: &header::Header,

  + ) -> Result<usize, usize> {

  + let s = core::slice::from_raw_parts(

  + page.data.as_ptr().add(HDR) as *const u16,

  + hdr.n() as usize,

  + );

  + if let Some(v0) = v0 {

  + s.binary_search_by(|&off| {

  + let off = u16::from_le(off);

  + let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

  + let k = K::from_raw_ptr(txn, k as *const u8);

  + match k.compare(txn, k0) {

  + Ordering::Equal => {

  + let v = V::from_raw_ptr(txn, v as *const u8);

  + v.compare(txn, v0)

  + }

  + cmp => cmp,

  + }

  + })
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 296
  [6.8153]→[6.8153:8751](∅→∅)
  − let s = core::slice::from_raw_parts(

  − page.data.as_ptr().add(HDR) as *const u64,

  − hdr.n() as usize,

  − );

  − if let Some(v0) = v0 {

  − s.binary_search_by(|&off| {

  − let off = u64::from_le(off) & 0xfff;

  − let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

  − let k = K::from_raw_ptr(txn, k);

  − match k.compare(txn, k0) {

  − Ordering::Equal => {

  − let v = V::from_raw_ptr(txn, v);

  − v.compare(txn, v0)
  [6.8153]

  [6.8751]
  + match s.binary_search_by(|&off| {

  + let off = u16::from_le(off);

  + let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

  + let k = K::from_raw_ptr(txn, k);

  + k.compare(txn, k0)

  + }) {

  + Err(e) => Err(e),

  + Ok(mut i) => {

  + // Rewind if there are multiple matching keys.

  + while i > 0 {

  + let off = u16::from_le(s[i-1]);

  + let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

  + let k = K::from_raw_ptr(txn, k);

  + if let Ordering::Equal = k.compare(txn, k0) {

  + i -= 1

  + } else {

  + break
• edit in sanakirja-core/src/btree/page_unsized.rs at line 314
  [6.8773]→[6.8773:9097](∅→∅),[6.9097]→[6.177:309](∅→∅)
  − cmp => cmp,

  − }

  − })

  − } else {

  − s.binary_search_by(|&off| {

  − let off = u64::from_le(off) & 0xfff;

  − let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

  − let k = K::from_raw_ptr(txn, k);

  − match k.compare(txn, k0) {

  − Ordering::Equal => Ordering::Greater,

  − cmp => cmp
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 315
  [6.327]→[6.9132:9147](∅→∅),[6.9132]→[6.9132:9147](∅→∅)
  − })
  [6.327]

  [6.9147]
  + Ok(i)

  + }
• edit in sanakirja-core/src/btree/page_unsized.rs at line 321
  [6.2328]

  [6.2328]
  +
• replacement in sanakirja-core/src/btree/mod.rs at line 20
  [6.34498]→[6.34498:34516](∅→∅)
  − pub use del::del;
  [6.34498]

  [6.34516]
  + pub use del::{del, del_no_decr};
• edit in sanakirja-core/src/btree/mod.rs at line 249
  [6.9230]

  [6.52187]
  +

  + impl<K:Storable, V:Storable, P: BTreePage<K, V> + core::fmt::Debug> Storable for Db_<K, V, P> {

  + type PageReferences = core::iter::Once<u64>;

  + fn page_references(&self) -> Self::PageReferences {

  + core::iter::once(self.db)

  + }

  +

  + fn drop<T: AllocPage>(&self, t: &mut T) -> Result<(), T::Error> {

  + drop_(t, self)

  + }

  + }
• replacement in sanakirja-core/src/btree/mod.rs at line 312
  [6.1589]→[6.1589:1624](∅→∅)
  − /// to `(k, v)` if `v.is_some()`).
  [6.1589]

  [6.11514]
  + /// to `(k, v)` if `v.is_some()`), and return `true` if this entry is

  + /// shared with another structure (i.e. the RC of at least one page

  + /// along a path to the entry is at least 2).

  + pub fn get_shared<'a, T: LoadPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage<K, V>>(

  + txn: &'a T,

  + db: &Db_<K, V, P>,

  + k: &K,

  + v: Option<&V>,

  + ) -> Result<Option<(&'a K, &'a V, bool)>, T::Error> {

  +

  + // Set the "cursor stack" by setting a skip list cursor in

  + // each page from the root to the appropriate leaf.

  + let mut last_match = None;

  + let mut page = txn.load_page(db.db)?;

  + let mut is_shared = txn.rc(db.db)? >= 2;

  + // This is a for loop, to allow the compiler to unroll (maybe).

  + for _ in 0..cursor::N_CURSORS {

  + let mut cursor = P::cursor_before(&page);

  + if let Ok((kk, vv, _)) = P::set_cursor(txn, page.as_page(), &mut cursor, k, v) {

  + if v.is_some() {

  + return Ok(Some((kk, vv, is_shared)));

  + }

  + last_match = Some((kk, vv, is_shared));

  + } else if let Some((k, v, _)) = P::current(txn, page.as_page(), &cursor) {

  + // Here, Rust says that `k` and `v` have the same lifetime

  + // as `page`, but we actually know that they're alive for

  + // as long as `txn` doesn't change, so we can safely

  + // extend their lifetimes:

  + unsafe { last_match = Some((core::mem::transmute(k), core::mem::transmute(v), is_shared)) }

  + }

  + // The cursor is set to the first element greater than or

  + // equal to the (k, v) we're looking for, so we need to

  + // explore the left subtree.

  + let next_page = P::left_child(page.as_page(), &cursor);

  + if next_page > 0 {

  + page = txn.load_page(next_page)?;

  + is_shared |= txn.rc(db.db)? >= 2;

  + } else {

  + break;

  + }

  + }

  + Ok(last_match)

  + }

  +

  +

  + /// Get the first entry of a database greater than or equal to `k` (or

  + /// to `(k, v)` if `v.is_some()`), and return `true` if this entry is

  + /// shared with another structure (i.e. the RC of at least one page

  + /// along a path to the entry is at least 2).
• edit in sanakirja-core/src/btree/mod.rs at line 367
  [6.621]

  [6.621]
  +

  + // Unfortunately, since the above function `get_shared` uses this

  + // one in order to get the RC of pages, we can't really refactor,

  + // so this is mostly a copy of the other function.

  +
• edit in sanakirja-core/src/btree/mod.rs at line 409
  [6.809]

  [6.809]
  + ) -> Result<(), T::Error> {

  + drop_(txn, &db)

  + }

  +

  + fn drop_<T: AllocPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage<K, V>>(

  + txn: &mut T,

  + db: &Db_<K, V, P>,
• replacement in sanakirja-core/src/btree/mod.rs at line 475
  [6.13429]→[6.3346:3420](∅→∅),[6.3420]→[6.2387:2442](∅→∅),[6.2387]→[6.2387:2442](∅→∅)
  − for o in k.page_references().chain(v.page_references()) {

  − txn.decr_rc(o)?;

  − }
  [6.13429]

  [6.1194]
  + k.drop(txn)?;

  + v.drop(txn)?;
• replacement in sanakirja-core/src/btree/del.rs at line 103
  [6.7775]→[6.53660:53700](∅→∅),[6.53660]→[6.53660:53700](∅→∅)
  − del_at_cursor(txn, db, &mut cursor)
  [6.7775]

  [6.53700]
  + del_at_cursor(txn, db, &mut cursor, true)

  + }

  +

  +

  + /// If `value` is `None`, delete the first entry for `key` from the

  + /// database, if present. Else, delete the entry for `(key, value)`,

  + /// if present.

  + pub fn del_no_decr<

  + T: AllocPage + LoadPage,

  + K: Storable + ?Sized + PartialEq,

  + V: Storable + ?Sized + PartialEq,

  + P: BTreeMutPage<K, V>,

  + >(

  + txn: &mut T,

  + db: &mut Db_<K, V, P>,

  + key: &K,

  + value: Option<&V>,

  + ) -> Result<bool, T::Error> {

  + let mut cursor = Cursor::new(txn, db)?;

  + // If the key and value weren't found, return.

  + match (cursor.set(txn, key, value)?, value) {

  + (Some((k, v)), Some(value)) if k == key && v == value => {}

  + (Some((k, _)), None) if k == key => {}

  + _ => return Ok(false),

  + }

  + // Else, the cursor is set on `(key, value)` if `value.is_some()`

  + // or on the first entry with key `key` else.

  + //

  + // We delete that position, which might be in a leaf or in an

  + // internal node.

  + del_at_cursor(txn, db, &mut cursor, false)
• edit in sanakirja-core/src/btree/del.rs at line 148
  [6.16194]

  [6.53939]
  + decr_del_rc: bool,
• replacement in sanakirja-core/src/btree/del.rs at line 160
  [6.7959]→[6.37433:37469](∅→∅)
  − if p0 < cursor.first_rc_len() {
  [6.7959]

  [6.9636]
  + //

  + // Note in particular that if p0 == cursor.first_rc_len(), then we

  + // don't need to touch the RC, since we're cloning this page, but

  + // without including a reference to the deleted entry.

  + if decr_del_rc && p0 < cursor.first_rc_len() {
• replacement in sanakirja-core/src/btree/del.rs at line 169
  [6.1194]→[6.3421:3493](∅→∅),[6.3493]→[6.450:479](∅→∅),[6.1260]→[6.450:479](∅→∅),[6.479]→[6.16753:16763](∅→∅),[6.1289]→[6.16753:16763](∅→∅),[6.16753]→[6.16753:16763](∅→∅)
  − for o in delk.page_references().chain(delv.page_references()) {

  − txn.decr_rc(o)?;

  − }
  [6.1194]

  [6.16763]
  + delk.drop(txn)?;

  + delv.drop(txn)?;
• replacement in sanakirja-core/Cargo.toml at line 3
  [6.70812]→[5.26:45](∅→∅)
  − version = "1.2.14"
  [6.70812]

  [6.70847]
  + version = "1.2.16"
• file move: sanakirja (d--r------) → sanakirja (d--r------)
  [1.0]

  [6.71001]
• edit in sanakirja/src/environment/muttxn.rs at line 48
  [6.586]

  [6.2818]
  +

  + /// Offsets of pages free at the start of the transaction.

  + initial_free: (usize, Vec<u64>),

  +
• replacement in sanakirja/src/environment/muttxn.rs at line 56
  [3.39]→[3.39:119](∅→∅)
  − /// Borrow env

  − pub fn env_borrow(&self) -> &Env {

  − self.env.borrow()

  − }
  [3.39]

  [3.119]
  + /// Borrow env

  + pub fn env_borrow(&self) -> &Env {

  + self.env.borrow()

  + }
• edit in sanakirja/src/environment/muttxn.rs at line 97
  [2.602]

  [6.81773]
  + parent.initial_free.0 = self.initial_free.0;
• replacement in sanakirja/src/environment/muttxn.rs at line 183
  [6.10473]→[6.83538:83562](∅→∅),[6.83538]→[6.83538:83562](∅→∅)
  − Ok(MutTxn {
  [6.10473]

  [6.83562]
  +

  + let mut txn = MutTxn {
• edit in sanakirja/src/environment/muttxn.rs at line 202
  [6.83993]

  [6.3330]
  + initial_free: (0, Vec::new()),
• replacement in sanakirja/src/environment/muttxn.rs at line 204
  [6.3365]→[6.84026:84041](∅→∅),[6.84026]→[6.84026:84041](∅→∅)
  − })
  [6.3365]

  [6.84041]
  + };

  + if txn.free > 0 {

  + let free_db: btree::Db<u64, ()> = btree::Db::from_page(txn.free);

  + let mut init = Vec::new();

  + for p in btree::rev_iter(&txn, &free_db, None)? {

  + let (p, _) = p?;

  + init.push(*p)

  + }

  + txn.initial_free = (init.len(), init)

  + }

  +

  + Ok(txn)
• replacement in sanakirja/src/environment/muttxn.rs at line 247
  [6.11529]→[6.11529:11580](∅→∅)
  − debug!("free_db = {:?}", free_db);
  [6.11529]

  [6.11580]
  + debug!("free_db = {:x}", free_db.db);

  + {

  + for p in btree::iter(&self, &free_db, None).unwrap() {

  + debug!("was free: p = {:x}", p.unwrap().0);

  + }

  + for p in self.free_pages.iter().chain(self.free_owned_pages.iter()) {

  + debug!("free_pages {:x}", p);

  + }

  + }

  +

  + // Deleting the pages allocated during this transaction.

  + let mut f = self.initial_free.1.len();

  + while f > self.initial_free.0 {

  + f -= 1;

  + let p = self.initial_free.1[f];

  + btree::del(&mut self, &mut free_db, &p.to_le(), None)?;

  + }

  +
• edit in sanakirja/src/environment/muttxn.rs at line 269
  [6.11879]→[6.11879:12459](∅→∅)
  −

  − // First, set the free table to 0 in this transaction, to

  − // avoid recursing in the calls to `put` below (indeed,

  − // the table of free pages is used when allocating new

  − // pages, which may happen in a call to `put`).

  − self.free = 0;

  −

  − // Then, while there are pages to free, free them. Since

  − // the calls to `put` below might free pages (and add

  − // pages to these two vectors), the (outer) loop might run

  − // for more than one iteration.
• edit in sanakirja/src/environment/muttxn.rs at line 293
  [6.13621]

  [6.85146]
  + }

  + unsafe {

  + debug!(

  + "commit page {:x}: {:?}",

  + p.0.offset,

  + std::slice::from_raw_parts(p.0.data, 32)

  + );
• edit in sanakirja/src/environment/muttxn.rs at line 333
  [6.14477]→[6.14477:14575](∅→∅)
  − debug!("root_db: {:?}", rr);

  − debug!("committing root: {:?} {:?}", r, rr);
• replacement in sanakirja/src/environment/muttxn.rs at line 408
  [6.16496]→[6.16213:16241](∅→∅),[6.86463]→[6.16213:16241](∅→∅),[6.16241]→[6.16497:16534](∅→∅),[6.16241]→[6.86498:86537](∅→∅),[6.16534]→[6.86498:86537](∅→∅),[6.86498]→[6.86498:86537](∅→∅),[6.86537]→[6.16535:16609](∅→∅),[6.16609]→[6.16242:16305](∅→∅),[6.86708]→[6.16242:16305](∅→∅),[6.16305]→[6.19767:19859](∅→∅),[6.16676]→[6.86826:86898](∅→∅),[6.19859]→[6.86826:86898](∅→∅),[6.86826]→[6.86826:86898](∅→∅),[6.86898]→[6.16677:16802](∅→∅)
  − if self.free == 0 {

  − debug!("self.free = 0");

  − return Ok(None);

  − }

  − let mut db: btree::Db<u64, ()> = btree::Db::from_page(self.free);

  − let mut curs = btree::cursor::Cursor::new(self, &db)?;

  − curs.set_last(self)?;

  − let mut f = if let Some((f, ())) = curs.prev(self)? {

  − *f

  − } else {

  − return Ok(None);

  − };

  − // Get the last page that is also free in all other versions.

  − loop {

  − debug!("trying 0x{:x}", f);
  [6.16496]

  [6.16802]
  + while self.initial_free.0 > 0 {

  + self.initial_free.0 -= 1;

  + let f = self.initial_free.1[self.initial_free.0];
• replacement in sanakirja/src/environment/muttxn.rs at line 412
  [6.16841]→[6.16841:17049](∅→∅)
  − break;

  − } else if let Some((f_, ())) = curs.prev(self)? {

  − f = *f_

  − } else {

  − debug!("no more candidate");

  − return Ok(None);
  [6.16841]

  [6.17049]
  + return Ok(Some(f));
• replacement in sanakirja/src/environment/muttxn.rs at line 415
  [6.17073]→[6.17073:17097](∅→∅),[6.17097]→[6.19860:19921](∅→∅),[6.19921]→[6.86955:87002](∅→∅),[6.42064]→[6.86955:87002](∅→∅),[6.86955]→[6.86955:87002](∅→∅)
  −

  − self.free = 0;

  − assert!(btree::del::del(self, &mut db, &f, None)?);

  −

  − self.free = db.db;

  − Ok(Some(f))
  [6.17073]

  [6.87002]
  + Ok(None)
• replacement in sanakirja/src/environment/muttxn.rs at line 505
  [6.1789]→[6.19104:19175](∅→∅)
  − btree::del::del_at_cursor(self, &mut rc_, &mut curs)?;
  [6.1789]

  [6.89113]
  + btree::del::del_at_cursor(self, &mut rc_, &mut curs, true)?;
• replacement in sanakirja/src/environment/muttxn.rs at line 507
  [6.89127]→[6.2424:2478](∅→∅)
  − debug!("incr rc 0x{:x} {:?}", off, rc+1);
  [6.89127]

  [6.19176]
  + debug!("incr rc 0x{:x} {:?}", off, rc + 1);
• edit in sanakirja/src/debug.rs at line 123
  [6.3066]

  [6.2063]
  + }

  + }

  +

  + pub trait Check: core::fmt::Debug {

  + fn add_refs<T: LoadPage>(

  + &self,

  + _txn: &T,

  + _refs: &mut std::collections::BTreeMap<u64, usize>,

  + ) -> Result<(), T::Error>

  + where

  + T::Error: std::fmt::Debug,

  + {

  + Ok(())
• edit in sanakirja/src/debug.rs at line 138
  [6.2071]

  [6.2071]
  +

  + impl Check for u64 {}

  + impl Check for () {}
• edit in sanakirja/src/debug.rs at line 142
  [6.2072]

  [6.2072]
  + impl<K: Check + Ord + UnsizedStorable + ?Sized, V: Check + Ord + UnsizedStorable + ?Sized, P: BTreePage<K, V> + std::fmt::Debug> Check

  + for Db_<K, V, P>

  + {

  + fn add_refs<T: LoadPage>(

  + &self,

  + txn: &T,

  + pages: &mut std::collections::BTreeMap<u64, usize>,

  + ) -> Result<(), T::Error>

  + where

  + T::Error: std::fmt::Debug,

  + {

  + use std::collections::btree_map::Entry;

  + let mut stack = vec![self.db];

  + while let Some(p) = stack.pop() {

  + match pages.entry(p) {

  + Entry::Vacant(e) => {

  + debug!("add_refs: 0x{:x}", p);

  + e.insert(1);

  + let p = txn.load_page(p)?;

  + let mut c = P::cursor_first(&p);

  + let l = P::left_child(p.as_page(), &c);

  + if l > 0 {

  + stack.push(l);

  + }

  + let mut kv = None;

  + while let Some((k, v, r)) = P::next(txn, p.as_page(), &mut c) {

  + debug!("{:?} {:?} {:?}", k, v, kv);

  + if let Some((k_, v_)) = kv {

  + debug!("{:?} {:?} {:?}", k_ > k, k_ == k, v_ > v);

  + if k_ > k || (k_ == k && v_ > v) {

  + debug(txn, &[self], "debug_ord", true);

  + panic!("{:?} {:?} {:?} {:?} {:?}", kv, k_, v_, k_ > k, v_ > v);

  + }

  + }

  + k.add_refs(txn, pages)?;

  + v.add_refs(txn, pages)?;

  + kv = Some((k, v));

  + if r > 0 {

  + stack.push(r);

  + }

  + }

  + }

  + Entry::Occupied(mut e) => {

  + e.insert(e.get() + 1);

  + }

  + }

  + }

  + Ok(())

  + }

  + }

  +
• edit in sanakirja/src/debug.rs at line 269
  [6.4345]→[6.4345:4354](∅→∅),[6.4354]→[6.85:227](∅→∅),[6.227]→[6.4448:4540](∅→∅),[6.4448]→[6.4448:4540](∅→∅),[6.4540]→[6.228:292](∅→∅),[6.292]→[6.4568:5034](∅→∅),[6.4568]→[6.4568:5034](∅→∅),[6.5034]→[6.293:937](∅→∅),[6.937]→[6.5118:5314](∅→∅),[6.5118]→[6.5118:5314](∅→∅)
  − }

  − }

  −

  − pub fn add_refs<T: LoadPage, K: Storable + Ord + ?Sized + std::fmt::Debug, V: Storable + Ord + ?Sized + std::fmt::Debug, P: BTreePage<K, V>>(

  − txn: &T,

  − db: &Db_<K, V, P>,

  − pages: &mut std::collections::BTreeMap<u64, usize>,

  − ) -> Result<(), T::Error>

  − where

  − T::Error: std::fmt::Debug

  − {

  − use std::collections::btree_map::Entry;

  − let mut stack = vec![db.db];

  − while let Some(p) = stack.pop() {

  − match pages.entry(p) {

  − Entry::Vacant(e) => {

  − debug!("add_refs: 0x{:x}", p);

  − e.insert(1);

  − let p = txn.load_page(p)?;

  − let mut c = P::cursor_first(&p);

  − let l = P::left_child(p.as_page(), &c);

  − if l > 0 {

  − stack.push(l);

  − }

  − let mut kv = None;

  − while let Some((k, v, r)) = P::next(txn, p.as_page(), &mut c) {

  − debug!("{:?} {:?} {:?}", k, v, kv);

  − if let Some((k_, v_)) = kv {

  − debug!("{:?} {:?} {:?}", k_ > k, k_ == k, v_ > v);

  − if k_ > k || (k_ == k && v_ > v) {

  − debug(txn, &[db], "debug_ord", true);

  − panic!("{:?} {:?} {:?} {:?} {:?}", kv, k_, v_, k_>k, v_>v);

  − }

  − }

  − kv = Some((k, v));

  − if r > 0 {

  − stack.push(r);

  − }

  − }

  − }

  − Entry::Occupied(mut e) => {

  − e.insert(e.get() + 1);

  − }

  − }
• edit in sanakirja/src/debug.rs at line 270
  [6.3072]→[6.5315:5326](∅→∅)
  − Ok(())
• replacement in sanakirja/src/debug.rs at line 283
  [6.5833]→[6.5833:5878](∅→∅)
  − add_refs(txn, &free_db, pages)?;
  [6.5833]

  [6.5878]
  + free_db.add_refs(txn, pages)?;
• replacement in sanakirja/src/debug.rs at line 288
  [6.6041]→[6.6041:6084](∅→∅)
  − add_refs(txn, &rc_db, pages)?;
  [6.6041]

  [6.6084]
  + rc_db.add_refs(txn, pages)?;
• replacement in sanakirja/src/debug.rs at line 301
  [6.1884]→[6.1884:1925](∅→∅)
  − add_refs(txn, &free_db, pages)?;
  [6.1884]

  [6.1925]
  + free_db.add_refs(txn, pages)?;
• replacement in sanakirja/src/debug.rs at line 305
  [6.2019]→[6.2019:2055](∅→∅)
  − add_refs(txn, &rc, pages)?;
  [6.2019]

  [6.2055]
  + rc.add_refs(txn, pages)?;
• replacement in sanakirja/src/debug.rs at line 310
  [4.6263]→[4.6263:6396](∅→∅)
  − pub fn check_refs<B: std::borrow::Borrow<crate::Env>, T>(txn: &crate::MutTxn<B, T>, refs: &std::collections::BTreeMap<u64, usize>) {
  [4.6263]

  [4.6396]
  + pub fn check_refs<B: std::borrow::Borrow<crate::Env>, T>(

  + txn: &crate::MutTxn<B, T>,

  + refs: &std::collections::BTreeMap<u64, usize>,

  + ) {
• file move: cover (---r------) → cover (---r------)
  [1.0]

  [6.8]
• file move: Cargo.toml (----------) → Cargo.toml (----------)
  [1.0]

  [6.108835]