feat(pkgs/lf-make-map): Implement all needed details to produce first mappings

The only bug left right know, is that multiple same mappings can be
generated because of the ways the types interact with each other.

5 files changed, 312 insertions, 172 deletions

diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/generator/mod.rs b/sys/nixpkgs/pkgs/lf-make-map/src/generator/mod.rs
deleted file mode 100644
index c03b33dc..00000000
--- a/sys/nixpkgs/pkgs/lf-make-map/src/generator/mod.rs
+++ /dev/null
@@ -1,51 +0,0 @@
-use std::path::PathBuf;
-
-use anyhow::{Context, Result};
-use log::trace;
-use walkdir::{DirEntry, WalkDir};
-
-use crate::mapping::{map_tree::MappingTree, MapKey, Mapping};
-
-pub struct MappingsGenerator {
-    mappings: MappingTree,
-    paths_to_process: Vec<PathBuf>,
-}
-
-fn is_dir(entry: &DirEntry) -> bool {
-    entry.file_type().is_dir()
-}
-
-impl MappingsGenerator {
-    pub async fn new(
-        directories_to_scan: Vec<PathBuf>,
-        max_depth: usize,
-        home_path: PathBuf,
-    ) -> Result<Self> {
-        let mut mappings = MappingTree::new();
-
-        for dir in directories_to_scan {
-            for dir2 in WalkDir::new(&dir)
-                .max_depth(max_depth)
-                .into_iter()
-                .filter_entry(|e| is_dir(e))
-            {
-                let directory =
-                    dir2.with_context(|| format!("Failed to read dir ('{}')", &dir.display()))?;
-
-                trace!("Processed '{}'..", directory.path().display());
-
-                let mapping = Mapping::new(&home_path, directory.path().to_path_buf());
-                let mapping_key = mapping.key.clone();
-                mappings.insert(&mapping_key, mapping).with_context(|| {
-                    format!(
-                        "Failed to insert '{}' for path: '{}'\nMapTree is now: \n{}",
-                        MapKey::display(&mapping_key),
-                        directory.path().display(),
-                        mappings,
-                    )
-                })?;
-            }
-        }
-        todo!()
-    }
-}
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/main.rs b/sys/nixpkgs/pkgs/lf-make-map/src/main.rs
index dbfe5ec7..8a1ca602 100644
--- a/sys/nixpkgs/pkgs/lf-make-map/src/main.rs
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/main.rs
@@ -1,14 +1,14 @@
 use anyhow::Context;
 use clap::Parser;
 use cli::Args;
-use generator::MappingsGenerator;
+use log::trace;
+use mapping::map_tree::MappingTree;
+use walkdir::{DirEntry, WalkDir};
 
 mod cli;
-mod generator;
 mod mapping;
 
-#[tokio::main]
-async fn main() -> anyhow::Result<()> {
+fn main() -> anyhow::Result<()> {
     let args = Args::parse();
 
     stderrlog::new()
@@ -20,14 +20,51 @@ async fn main() -> anyhow::Result<()> {
         .timestamp(stderrlog::Timestamp::Off)
         .init()?;
 
-    // gen_lf_mappings(args.home_name, 0, args.relevant_directories);
-    let map = MappingsGenerator::new(args.relevant_directories, args.depth, args.home_name)
-        .await
-        .context("Failed to initialize mappings generator")?;
+    let mut mappings = MappingTree::new();
+
+    for dir in args.relevant_directories {
+        for dir2 in WalkDir::new(&dir)
+            .max_depth(args.depth)
+            .into_iter()
+            .filter_entry(|e| is_dir(e))
+        {
+            let directory =
+                dir2.with_context(|| format!("Failed to read dir ('{}')", &dir.display()))?;
+
+            let path = directory
+                .path()
+                .strip_prefix(&args.home_name)
+                .with_context(|| {
+                    format!(
+                        "'{}' is not under the specified home path ('{}')!",
+                        directory.path().display(),
+                        args.home_name.display()
+                    )
+                })?;
+
+            mappings.include(path.to_str().with_context(|| {
+                format!(
+                    "\
+Can't derive a keymapping from path: '{}' \
+because it can't be turned to a string
+",
+                    path.display()
+                )
+            })?);
+
+            trace!("Processed '{}'..", directory.path().display());
+        }
+    }
+
+    println!("{}", mappings);
 
     Ok(())
 }
 
+fn is_dir(entry: &DirEntry) -> bool {
+    entry.file_type().is_dir()
+}
+
 // fn gen_lf_mappings(home_name: PathBuf, char_num: usize, rel_dirs: Vec<PathBuf>) {
 //     let mut mappings_vec = vec![];
 //     let mut index_counter = 0;
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/error.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/error.rs
index 2a59ed64..ac772430 100644
--- a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/error.rs
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/error.rs
@@ -1,7 +1,9 @@
 use thiserror::Error;
 
+use super::MapKey;
+
 #[derive(Error, Debug)]
 pub enum Error {
-    #[error("The node at key '{0}' already exists!")]
-    NodeExits(String),
+    #[error("The node at key '{}' already exists!", MapKey::display(&.0))]
+    NodeExits(Vec<MapKey>),
 }
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 90296044..d3d9505e 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,25 +1,31 @@
-use std::{collections::HashMap, fmt::Display, path::PathBuf};
+use std::{
+    arch::x86_64::_MM_FROUND_CUR_DIRECTION, cmp::Ordering, collections::HashMap, fmt::Display, mem,
+};
 
-use super::{error, MapKey, Mapping};
+use log::{debug, info};
+
+use super::{error, MapKey};
 
 /// A prefix tree
 pub struct MappingTree {
     root: Node,
 }
 
-#[derive(Clone)]
-pub struct Node {
-    children: HashMap<MapKey, Node>,
-    value: Option<Mapping>,
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum NodeValue {
+    Parent { children: HashMap<MapKey, Node> },
+    Child { path: String },
+}
 
-    /// The key needed to get to this node
-    location: Vec<MapKey>,
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct Node {
+    value: NodeValue,
 }
 
 impl MappingTree {
     pub fn new() -> Self {
         Self {
-            root: Node::new(vec![], None),
+            root: Node::new_parent(),
         }
     }
 
@@ -27,7 +33,11 @@ impl MappingTree {
     pub fn get(&self, key: &[MapKey]) -> Option<&Node> {
         let mut current_node = &self.root;
         for ch in key.iter() {
-            current_node = current_node.children.get(&ch)?
+            if let NodeValue::Parent { children } = &current_node.value {
+                current_node = children.get(&ch)?
+            } else {
+                return None;
+            }
         }
 
         Some(current_node)
@@ -36,70 +46,176 @@ impl MappingTree {
     pub fn get_mut(&mut self, key: &[MapKey]) -> Option<&mut Node> {
         let mut current_node = &mut self.root;
         for ch in key.iter() {
-            current_node = current_node.children.get_mut(&ch)?
+            if let NodeValue::Parent { children } = &mut current_node.value {
+                current_node = children.get_mut(&ch)?
+            } else {
+                return None;
+            }
         }
 
         Some(current_node)
     }
 
     /// Returns the node at the key, otherwise the last node that matched.
-    pub fn try_get(&self, key: &[MapKey]) -> &Node {
+    pub fn try_get(&self, key: &[MapKey]) -> (&Node, Vec<MapKey>) {
         let mut current_node = &self.root;
+        let mut current_key = vec![];
+
         for ch in key.iter() {
-            if let Some(node) = current_node.children.get(&ch) {
-                current_node = node;
+            if let NodeValue::Parent { children } = &current_node.value {
+                current_node = if let Some(node) = children.get(&ch) {
+                    let (key, _value) = children
+                        .get_key_value(&ch)
+                        .expect("This exists, we checked");
+                    current_key.push(key.clone());
+
+                    node
+                } else {
+                    return (current_node, current_key);
+                };
             } else {
-                return current_node;
+                return (current_node, current_key);
             }
         }
 
-        current_node
+        (current_node, current_key)
+    }
+
+    pub fn include(&mut self, path: &str) {
+        let associated_key = MapKey::new_ones_from_path(path, 1);
+        self.insert(&associated_key, path);
     }
 
-    pub fn insert(&mut self, key: &[MapKey], mapping: Mapping) -> Result<(), error::Error> {
-        let node = self.try_get(key).clone();
-        if node.location.as_slice() != key {
+    pub fn insert(&mut self, key: &[MapKey], path: &str) {
+        let (_node, found_key) = self.try_get(key).clone();
+
+        if found_key != key {
             let needed_nodes_key = key
-                .strip_prefix(node.location.as_slice())
+                .strip_prefix(&found_key[..])
                 .expect("The node's location is a prefix");
+
             let needed_nodes_length = needed_nodes_key.iter().count();
 
             let mut current_node = self
-                .get_mut(&node.location)
+                .get_mut(&found_key[..])
                 .expect("This should always exists");
-            let mut current_location = node.location.clone();
+            let mut current_location = found_key.clone();
             let mut counter = 1;
 
             for ch in needed_nodes_key.iter() {
                 current_location.push(ch.to_owned());
 
                 let next_node = if counter == needed_nodes_length {
-                    Node::new(current_location.clone(), Some(mapping.clone()))
+                    Node::new_child(path.to_owned())
                 } else {
-                    Node::new(current_location.clone(), None)
+                    Node::new_parent()
+                };
+
+                current_node = match &current_node.value {
+                    NodeValue::Parent { children } => {
+                        assert_eq!(children.get(&ch), None);
+
+                        let children =
+                            if let NodeValue::Parent { children } = &mut current_node.value {
+                                children
+                            } else {
+                                unreachable!("This is a parent, we cheched")
+                            };
+
+                        children.insert(ch.to_owned(), next_node);
+                        children.get_mut(&ch).expect("Was just inserted")
+                    }
+                    NodeValue::Child { path } => {
+                        // A node that should be a parent was classified
+                        // as child before:
+                        //
+                        //  1. Remove the child node and replace it with a parent one.
+                        //  2. Add the child node to the parent node as child, but with a '.' as MapKey.
+                        //  3. Add the original node also as child to the parent node.
+
+                        let mut children = HashMap::new();
+                        let move_child_node = Node::new_child(path.to_owned());
+
+                        children.insert(
+                            MapKey {
+                                key: ".".to_owned(),
+                                part_path: ".".to_owned(),
+                                resolution: 1,
+                            },
+                            move_child_node,
+                        );
+                        children.insert(ch.to_owned(), next_node);
+
+                        current_node.value = NodeValue::Parent { children };
+
+                        let children =
+                            if let NodeValue::Parent { children } = &mut current_node.value {
+                                children
+                            } else {
+                                unreachable!("We just inserted the parent value.")
+                            };
+
+                        children.get_mut(&ch).expect("Was just inserted")
+                    }
                 };
 
-                current_node.children.insert(ch.to_owned(), next_node);
-                current_node = current_node
-                    .children
-                    .get_mut(&ch)
-                    .expect("Was just inserted");
                 counter += 1;
             }
         } else {
-            return Err(error::Error::NodeExits(MapKey::display(key)));
-        }
+            // 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.
+            // This only includes the last segment of the `MapKey`
+            //
+            // 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();
 
-        Ok(())
+            debug!(
+                "'{}' ('{}') and '{}' ('{}') are the same, try to find a better combination!",
+                our_key, our_key.part_path, foreign_key, foreign_key.part_path,
+            );
+
+            while our_key == foreign_key {
+                our_key.increment();
+                foreign_key.increment();
+            }
+
+            debug!(
+                "Found a better one: '{}' ('{}') and '{}' ('{}')",
+                our_key, our_key.part_path, foreign_key, foreign_key.part_path,
+            );
+
+            let parent = self
+                .get_mut(&found_key[..found_key.len() - 1])
+                .expect("This node 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()));
+            } else {
+                unreachable!("This node will be a parent");
+            }
+        }
     }
 }
 
 impl Node {
-    pub fn new(location: Vec<MapKey>, mapping: Option<Mapping>) -> Self {
+    pub fn new_child(path: String) -> Self {
         Self {
-            children: HashMap::new(),
-            location,
-            value: mapping,
+            value: NodeValue::Child { path },
+        }
+    }
+    pub fn new_parent() -> Self {
+        Self {
+            value: NodeValue::Parent {
+                children: HashMap::new(),
+            },
         }
     }
 }
@@ -109,24 +225,14 @@ impl Display for MappingTree {
         fn write_node(
             node: &Node,
             indention: String,
+            location: Vec<MapKey>,
             has_parent: bool,
             is_last: bool,
             f: &mut std::fmt::Formatter<'_>,
         ) -> std::fmt::Result {
-            let bullet = if has_parent {
-                if is_last {
-                    String::from("└── ")
-                } else {
-                    String::from("├── ")
-                }
-            } else {
-                String::new()
-            };
-
-            let node_value = if let Some(value) = &node.value {
-                value.to_string()
-            } else {
-                "[No Value]".to_owned()
+            let node_value = match &node.value {
+                NodeValue::Parent { children: _ } => "<Parent>",
+                NodeValue::Child { path } => path,
             };
 
             let new_idention = if !has_parent {
@@ -137,31 +243,68 @@ impl Display for MappingTree {
                 indention.clone() + "│   "
             };
 
+            let bullet = if has_parent {
+                if is_last {
+                    String::from("└── ")
+                } else {
+                    String::from("├── ")
+                }
+            } else {
+                String::new()
+            };
+
             write!(
                 f,
                 "{}{}\x1b[1;33m{}\x1b[0m: {}\n",
                 indention,
                 bullet,
-                MapKey::display(&node.location),
+                MapKey::display(&location),
                 node_value,
             )?;
 
-            let value_length = node.children.len();
-            let mut counter = 1;
+            match &node.value {
+                NodeValue::Parent { children } => {
+                    let value_length = children.len();
+                    let mut counter = 1;
 
-            for child in node.children.values() {
-                if counter == value_length {
-                    write_node(child, new_idention.clone(), true, true, f)?;
-                } else {
-                    write_node(child, new_idention.clone(), true, false, f)?;
-                };
-                counter += 1;
+                    let mut children_vec: Vec<(&MapKey, &Node)> = children.iter().collect();
+                    children_vec.sort_by(|(a, _), (b, _)| a.key.cmp(&b.key));
+
+                    for (key, child) in children_vec {
+                        let mut new_location = location.clone();
+                        new_location.push(key.to_owned());
+
+                        if counter == value_length {
+                            write_node(
+                                child,
+                                new_idention.clone(),
+                                new_location.clone(),
+                                true,
+                                true,
+                                f,
+                            )?;
+                        } else {
+                            write_node(
+                                child,
+                                new_idention.clone(),
+                                new_location.clone(),
+                                true,
+                                false,
+                                f,
+                            )?;
+                        };
+                        counter += 1;
+                    }
+                }
+                NodeValue::Child { path: _ } => {
+                    // Do nothing and stop the recursion
+                }
             }
 
             Ok(())
         }
 
-        write_node(&self.root, String::new(), false, false, f)?;
+        write_node(&self.root, String::new(), vec![], false, false, f)?;
 
         Ok(())
     }
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs
index d05d3417..8bf6bbe0 100644
--- a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs
@@ -1,81 +1,90 @@
-use std::{
-    fmt::Display,
-    path::{Path, PathBuf},
-};
+use std::{fmt::Display, hash::Hash};
 
 use log::debug;
 
 pub mod error;
 pub mod map_tree;
 
-#[derive(Debug, Clone)]
-pub struct Mapping {
-    pub raw_path: PathBuf,
-
-    pub keys: usize,
-
-    pub key: Vec<MapKey>,
-}
-
-#[derive(Clone, Debug, PartialEq, PartialOrd, Ord, Hash, Eq)]
+#[derive(Clone, Debug, Eq)]
 pub struct MapKey {
-    value: String,
-}
+    pub key: String,
 
-impl MapKey {
-    pub fn new(value: String) -> Self {
-        Self { value }
-    }
-    pub fn display(values: &[Self]) -> String {
-        values.iter().map(|value| value.value.clone()).collect()
-    }
+    resolution: usize,
+
+    /// Part of the path, used to derive the key
+    part_path: String,
 }
 
-impl Display for MapKey {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        f.write_str(&self.value)
+impl Hash for MapKey {
+    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
+        self.key.hash(state)
     }
 }
 
-impl Display for Mapping {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        write!(f, "{}", self.raw_path.display())
+impl PartialEq for MapKey {
+    fn eq(&self, other: &Self) -> bool {
+        self.key == other.key
     }
 }
 
-impl Mapping {
-    pub fn new(home_path: &Path, initial_path: PathBuf) -> Mapping {
-        let raw_path = initial_path
-            .strip_prefix(home_path)
-            .expect("Must always be under the `home_path`");
-
-        let key = Self::path_to_keys(raw_path.to_str().expect("Should be a valid &str"));
-
+impl MapKey {
+    pub fn new_from_part_path(part_path: &str, resolution: usize) -> Self {
+        let key = Self::part_path_to_key(&part_path, resolution);
         Self {
-            raw_path: raw_path.to_owned(),
-            keys: key.len(),
             key,
+            resolution,
+            part_path: part_path.to_owned(),
         }
     }
 
-    fn path_to_keys(path: &str) -> Vec<MapKey> {
-        let key: Vec<MapKey> = path.split('/').map(Self::part_path_to_key).collect();
-        debug!("Will insert: '{}' -> '{}'", path, MapKey::display(&key));
+    pub fn increment(&mut self) {
+        if self.resolution < self.part_path.len() {
+            self.resolution += 1;
+            self.key = Self::part_path_to_key(&self.part_path, self.resolution);
+        } else {
+            let last_char = self.key.chars().last().expect("A last value exists");
+            self.key.push(last_char);
+        }
+    }
+
+    pub fn new_ones_from_path(path: &str, number_of_chars: usize) -> Vec<MapKey> {
+        let key: Vec<MapKey> = path
+            .split('/')
+            .map(|part| Self::new_from_part_path(part, number_of_chars))
+            .collect();
+
+        debug!(
+            "Generated full MapKeys: '{}' -> '{}'",
+            path,
+            MapKey::display(&key)
+        );
         key
     }
 
-    fn part_path_to_key(part: &str) -> MapKey {
+    pub fn display(values: &[Self]) -> String {
+        values.iter().map(|value| value.key.clone()).collect()
+    }
+    fn part_path_to_key(part: &str, number_of_chars: usize) -> String {
         let value = if part.contains('_') {
-            part.split('_').filter_map(|ch| ch.chars().nth(0)).collect()
+            part.split('_')
+                .map(|ch| ch.chars().take(number_of_chars).collect::<Vec<char>>())
+                .flatten()
+                .collect()
         } else if part.contains('-') {
-            part.split('-').filter_map(|ch| ch.chars().nth(0)).collect()
+            part.split('-')
+                .map(|ch| ch.chars().take(number_of_chars).collect::<Vec<char>>())
+                .flatten()
+                .collect()
         } else {
-            part.chars()
-                .nth(0)
-                .expect("Must have a first element")
-                .to_string()
+            part.chars().take(number_of_chars).collect::<String>()
         };
-        MapKey::new(value)
+        value
+    }
+}
+
+impl Display for MapKey {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        f.write_str(&self.key)
     }
 }