feat(pkgs/lf-make-map): Ensure that it works (for a depth=1)

1 files changed, 148 insertions, 23 deletions

diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
index d3d9505e..02f040b7 100644
--- a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
@@ -1,10 +1,9 @@
-use std::{
-    arch::x86_64::_MM_FROUND_CUR_DIRECTION, cmp::Ordering, collections::HashMap, fmt::Display, mem,
-};
+use std::{collections::HashMap, fmt::Display};
 
-use log::{debug, info};
+use anyhow::{bail, Result};
+use log::{debug, trace};
 
-use super::{error, MapKey};
+use super::MapKey;
 
 /// A prefix tree
 pub struct MappingTree {
@@ -42,6 +41,7 @@ impl MappingTree {
 
         Some(current_node)
     }
+
     /// Returns the node at the key, otherwise None. The node can be changed
     pub fn get_mut(&mut self, key: &[MapKey]) -> Option<&mut Node> {
         let mut current_node = &mut self.root;
@@ -81,12 +81,16 @@ impl MappingTree {
         (current_node, current_key)
     }
 
-    pub fn include(&mut self, path: &str) {
+    pub fn include(&mut self, path: &str) -> Result<()> {
         let associated_key = MapKey::new_ones_from_path(path, 1);
-        self.insert(&associated_key, path);
+        self.insert(&associated_key, path)
+    }
+
+    pub fn insert(&mut self, key: &[MapKey], path: &str) -> Result<()> {
+        self.insert_node(key, Node::new_child(path.to_owned()))
     }
 
-    pub fn insert(&mut self, key: &[MapKey], path: &str) {
+    pub fn insert_node(&mut self, key: &[MapKey], node: Node) -> Result<()> {
         let (_node, found_key) = self.try_get(key).clone();
 
         if found_key != key {
@@ -106,7 +110,7 @@ impl MappingTree {
                 current_location.push(ch.to_owned());
 
                 let next_node = if counter == needed_nodes_length {
-                    Node::new_child(path.to_owned())
+                    node.clone()
                 } else {
                     Node::new_parent()
                 };
@@ -138,7 +142,7 @@ impl MappingTree {
 
                         children.insert(
                             MapKey {
-                                key: ".".to_owned(),
+                                key: '.',
                                 part_path: ".".to_owned(),
                                 resolution: 1,
                             },
@@ -162,6 +166,49 @@ impl MappingTree {
                 counter += 1;
             }
         } else {
+            fn reduce_string(a: &str) -> Option<char> {
+                let first_char = a.chars().take(1).last().expect("Should contain one char");
+
+                if a.chars().all(|ch| ch == first_char) {
+                    return Some(first_char);
+                } else {
+                    return None;
+                }
+            }
+            fn check_subset(a: &str, b: &str) -> bool {
+                if a.len() > b.len() {
+                    let a_prefix: String = a.chars().take(b.len()).collect();
+                    let a_suffix: String = a.chars().skip(b.len()).collect();
+
+                    if a_prefix == b {
+                        let clean_suffix = reduce_string(&a_suffix);
+                        if let Some(ch) = clean_suffix {
+                            ch == b.chars().last().expect("Will match")
+                        } else {
+                            false
+                        }
+                    } else {
+                        false
+                    }
+                } else if b.len() > a.len() {
+                    let b_prefix: String = b.chars().take(a.len()).collect();
+                    let b_suffix: String = b.chars().skip(a.len()).collect();
+
+                    if b_prefix == a {
+                        let clean_suffix = reduce_string(&b_suffix);
+                        if let Some(ch) = clean_suffix {
+                            ch == a.chars().last().expect("Will match")
+                        } else {
+                            false
+                        }
+                    } else {
+                        false
+                    }
+                } else {
+                    a == b
+                }
+            }
+
             // Another node was already inserted with the same key!
             // So we simple increase the resolution of the other node and this node, until their
             // keys are not the same anymore.
@@ -170,38 +217,116 @@ impl MappingTree {
             // 1. Change both keys, until they are not equal any more
             // 2. Move the wrongly placed node to the new place.
             // 3. Insert our node.
-            let mut foreign_key = found_key.last().expect("This will exist").clone();
-            let mut our_key = key.last().expect("This will exist").clone();
+            let mut foreign_key = vec![found_key.last().expect("This will exist").clone()];
+            let mut our_key = vec![key.last().expect("This will exist").clone()];
 
             debug!(
                 "'{}' ('{}') and '{}' ('{}') are the same, try to find a better combination!",
-                our_key, our_key.part_path, foreign_key, foreign_key.part_path,
+                MapKey::display(&our_key),
+                our_key[0].part_path,
+                MapKey::display(&foreign_key),
+                foreign_key[0].part_path,
             );
 
+            // The 'a' and 'b' stuff is here, to ensure that both returning None will not match
+            // this condition.
+            if reduce_string(&foreign_key[0].part_path).unwrap_or('a')
+                == reduce_string(&our_key[0].part_path).unwrap_or('b')
+            {
+                bail!(
+                    "\
+The foreign_key ('{}', path_part: '{}' -> '{}') and our_key ('{}', path_part: '{}' -> '{}') \
+have an identical path_part (when duplicated chars are removed)!
+I cannot extended them via incrementation.
+Please rename the paths to fix this.
+                        ",
+                    MapKey::display(&foreign_key),
+                    &foreign_key[0].part_path,
+                    reduce_string(&foreign_key[0].part_path).expect("Is some here"),
+                    MapKey::display(&our_key),
+                    &our_key[0].part_path,
+                    reduce_string(&our_key[0].part_path).expect("Is some here"),
+                );
+            }
+
+            if check_subset(&foreign_key[0].part_path, &our_key[0].part_path) {
+                bail!(
+                    "\
+The foreign_key ('{}', path_part: '{}') and our_key ('{}', path_part: '{}') \
+are subsets of one another!
+A discrimination through incrementation will not work!
+Please rename the paths to fix this.
+                        ",
+                    MapKey::display(&foreign_key),
+                    &foreign_key[0].part_path,
+                    MapKey::display(&our_key),
+                    &our_key[0].part_path,
+                );
+            }
+
             while our_key == foreign_key {
-                our_key.increment();
-                foreign_key.increment();
+                our_key = our_key[0].increment(our_key[our_key.len() - 1].resolution + 1);
+                foreign_key =
+                    foreign_key[0].increment(foreign_key[foreign_key.len() - 1].resolution + 1);
+                debug!(
+                    "Now its: '{}' ('{}') and '{}' ('{}')",
+                    MapKey::display(&our_key),
+                    our_key[0].part_path,
+                    MapKey::display(&foreign_key),
+                    foreign_key[0].part_path,
+                );
             }
+            assert_eq!(our_key.len(), foreign_key.len());
 
             debug!(
                 "Found a better one: '{}' ('{}') and '{}' ('{}')",
-                our_key, our_key.part_path, foreign_key, foreign_key.part_path,
+                MapKey::display(&our_key),
+                our_key[0].part_path,
+                MapKey::display(&foreign_key),
+                foreign_key[0].part_path,
             );
 
             let parent = self
-                .get_mut(&found_key[..found_key.len() - 1])
-                .expect("This node will exist");
+                .get_mut(&found_key[..=&found_key.len() - 2])
+                .expect("This will exist");
 
             if let NodeValue::Parent { children } = &mut parent.value {
-                let old = children
-                    .remove(found_key.last().expect("This will exist"))
-                    .expect("This will be there");
-                children.insert(foreign_key, old);
-                children.insert(our_key, Node::new_child(path.to_owned()));
+                if let NodeValue::Child { path: _ } = children
+                    .get(found_key.last().expect("Exists"))
+                    .expect("This node also exists")
+                    .value
+                {
+                    let old = children
+                        .remove(found_key.last().expect("This will exist"))
+                        .expect("This will be there");
+
+                    let full_foreign_key: Vec<_> = found_key
+                        .clone()
+                        .into_iter()
+                        .rev()
+                        .skip(1)
+                        .rev()
+                        .chain(foreign_key.clone().into_iter())
+                        .collect();
+                    self.insert_node(&full_foreign_key, old.clone())?;
+                }
+
+                let full_our_key: Vec<_> = key
+                    .to_vec()
+                    .into_iter()
+                    .rev()
+                    .skip(1)
+                    .rev()
+                    .chain(our_key.clone().into_iter())
+                    .collect();
+
+                self.insert_node(&full_our_key, node.clone())?;
             } else {
                 unreachable!("This node will be a parent");
             }
         }
+
+        Ok(())
     }
 }