pds: mst: add empty layer nodes as needed

This is to match behavior of the upstream Javascript implementation.

Basically, if there is a "layer=2" node and a "layer=0" node, and no
other nodes, there should be a "layer=1" node in between with just the
'left' reference populated.

2 files changed, 28 insertions, 10 deletions

diff --git a/adenosine-pds/src/mst.rs b/adenosine-pds/src/mst.rs
index 23f1fdb..8a28117 100644
--- a/adenosine-pds/src/mst.rs
+++ b/adenosine-pds/src/mst.rs
@@ -223,28 +223,48 @@ pub fn generate_mst(
     serialize_wip_tree(db, root.unwrap_or(empty_node))
 }
 
+// this routine assumes that entries are added in sorted key order. AKA, the `entry` being added is
+// "further right" in the tree than any existing entries
 fn insert_entry(mut node: WipNode, entry: WipEntry) -> WipNode {
-    // if we are higher on tree than existing node, replace it with new layer first
-    if entry.height > node.height {
+    // if we are higher on tree than existing node, replace it (recursively) with new layers first
+    while entry.height > node.height {
         node = WipNode {
-            height: entry.height,
+            height: node.height + 1,
             left: Some(Box::new(node)),
             entries: vec![],
         }
-    };
+    }
     // if we are lower on tree, then need to descend first
     if entry.height < node.height {
-        // we should never be lower down the left than an existing node, and always to the right
+        // if no entries at this node, then we should insert down "left" (which is just "down", not
+        // "before" any entries)
+        if node.entries.is_empty() {
+            if let Some(left) = node.left {
+                node.left = Some(Box::new(insert_entry(*left, entry)));
+                return node;
+            } else {
+                panic!("hit existing totally empty MST node");
+            }
+        }
         let mut last = node.entries.pop().expect("hit empty existing entry list");
         assert!(entry.key > last.key);
         if last.right.is_some() {
             last.right = Some(Box::new(insert_entry(*last.right.unwrap(), entry)));
         } else {
-            last.right = Some(Box::new(WipNode {
+            let mut new_node = WipNode {
                 height: entry.height,
                 left: None,
                 entries: vec![entry],
-            }));
+            };
+            // may need to (recursively) insert multiple filler layers
+            while new_node.height + 1 < node.height {
+                new_node = WipNode {
+                    height: new_node.height + 1,
+                    left: Some(Box::new(new_node)),
+                    entries: vec![],
+                }
+            }
+            last.right = Some(Box::new(new_node));
         }
         node.entries.push(last);
         return node;
diff --git a/adenosine-pds/tests/test_mst_interop.rs b/adenosine-pds/tests/test_mst_interop.rs
index af03fd7..8a5becc 100644
--- a/adenosine-pds/tests/test_mst_interop.rs
+++ b/adenosine-pds/tests/test_mst_interop.rs
@@ -3,7 +3,6 @@ use libipld::Cid;
 use std::collections::BTreeMap;
 use std::str::FromStr;
 
-#[ignore]
 #[test]
 fn test_known_maps() {
     let mut repo = RepoStore::open_ephemeral().unwrap();
@@ -42,6 +41,7 @@ fn test_known_maps() {
     );
 }
 
+// TODO: behavior of these wide-char keys is undefined behavior in string MST
 #[ignore]
 #[test]
 fn test_tricky_map() {
@@ -72,7 +72,6 @@ fn test_trims_top() {
     let l1root = "bafyreihuyj2vzb2vjw3yhxg6dy25achg5fmre6gg5m6fjtxn64bqju4dee";
     let l0root = "bafyreibmijjc63mekkjzl3v2pegngwke5u6cu66g75z6uw27v64bc6ahqi";
 
-
     // NOTE: this test doesn't do much in this case of rust implementation
     let mut trim_map: BTreeMap<String, Cid> = Default::default();
     trim_map.insert("com.example.record/40c73105b48f".to_string(), cid1.clone()); // level 0
@@ -123,7 +122,6 @@ fn test_insertion() {
     assert_eq!(insertion_after_cid.to_string(), l2root);
 }
 
-#[ignore]
 #[test]
 fn test_higher_layers() {
     // "handles new layers that are two higher than existing"