From f46d845f6c1218b8e38725be1339de28dc15396e Mon Sep 17 00:00:00 2001
From: Benedikt Peetz <benedikt.peetz@b-peetz.de>
Date: Thu, 9 May 2024 11:10:36 +0200
Subject: feat(pkgs/lf-make-map): Support depths > 2
---
sys/nixpkgs/pkgs/lf-make-map/src/main.rs | 128 ++++--
.../pkgs/lf-make-map/src/mapping/map_tree.rs | 436 ---------------------
.../lf-make-map/src/mapping/map_tree/display.rs | 88 +++++
.../lf-make-map/src/mapping/map_tree/iterator.rs | 45 +++
.../pkgs/lf-make-map/src/mapping/map_tree/mod.rs | 424 ++++++++++++++++++++
5 files changed, 654 insertions(+), 467 deletions(-)
delete mode 100644 sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
create mode 100644 sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/display.rs
create mode 100644 sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/iterator.rs
create mode 100644 sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/mod.rs
(limited to 'sys/nixpkgs/pkgs')
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/main.rs b/sys/nixpkgs/pkgs/lf-make-map/src/main.rs
index 362b28db..ccda1f14 100644
--- a/sys/nixpkgs/pkgs/lf-make-map/src/main.rs
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/main.rs
@@ -1,10 +1,14 @@
-use anyhow::Context;
+use std::path::{Path, PathBuf};
+
+use anyhow::{Context, Result};
use clap::Parser;
use cli::Args;
-use log::trace;
+use log::{debug, trace};
use mapping::map_tree::MappingTree;
use walkdir::{DirEntry, WalkDir};
+use crate::mapping::MapKey;
+
mod cli;
mod mapping;
@@ -23,39 +27,64 @@ fn main() -> anyhow::Result<()> {
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()
- )
- })?;
+ trace!("Processing '{}'..", dir.display());
+ let path = strip_path(&dir, &args.home_name)?;
- 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()
+ mappings
+ .include(path_to_str(path)?)
+ .with_context(|| format!("Failed to include path: '{}'", path.display()))?;
+ }
+
+ let home = path_to_str(&args.home_name)?.to_owned();
+
+ let mut current_depth = 1;
+ while current_depth != args.depth {
+ for (key, value) in mappings.iter() {
+ trace!(
+ "Adding to child ('{}' -> '{}')",
+ MapKey::display(&key),
+ value
+ );
+
+ let mut local_mappings = MappingTree::new();
+ for dir in WalkDir::new(extend(&home, &value)?)
+ .min_depth(1)
+ .max_depth(1)
+ .into_iter()
+ .filter_entry(|e| is_dir(e) && !is_hidden(e))
+ {
+ let directory = dir
+ .with_context(|| format!("Failed to read dir ('{}')", home.clone() + &value))?;
+ let path_to_strip = &PathBuf::from(extend(&home, &value)?);
+ let path = strip_path(&directory.path(), &path_to_strip)?;
+ trace!(
+ "Including: '{}' (after stripping '{}' from '{}' -> '{}' + '/' + '{}')",
+ path.display(),
+ directory.path().display(),
+ path_to_strip.display(),
+ home,
+ value
+ );
+
+ let gen_key = MapKey::new_ones_from_path(path_to_str(path)?, 1);
+ local_mappings
+ .insert(
+ &gen_key,
+ path_to_str(strip_path(&directory.path(), &PathBuf::from(&home))?)?,
)
- })?)
- .with_context(|| format!("Failed to include path: '{}'", path.display()))?;
+ .with_context(|| format!("Failed to include path: '{}'", path.display()))?;
+ }
+
+ trace!("{}", local_mappings);
- trace!("Processed '{}'..", directory.path().display());
+ trace!(
+ "'{}' -> '{:#?}'",
+ MapKey::display(&key),
+ local_mappings.root_node()
+ );
+ mappings.interleave(&key, local_mappings.root_node().to_owned())?;
}
+ current_depth += 1;
}
println!("{}", mappings);
@@ -63,10 +92,47 @@ because it can't be turned to a string
Ok(())
}
+fn extend(base: &str, value: &str) -> Result<String> {
+ let base_path = PathBuf::from(base);
+ let value_path = PathBuf::from(value);
+
+ Ok(path_to_str(&base_path.join(&value_path))?.to_owned())
+}
+
+fn is_hidden(entry: &DirEntry) -> bool {
+ entry
+ .file_name()
+ .to_str()
+ .map(|s| s.starts_with("."))
+ .unwrap_or(false)
+}
+
fn is_dir(entry: &DirEntry) -> bool {
entry.file_type().is_dir()
}
+fn strip_path<'a>(path: &'a Path, to_strip: &Path) -> Result<&'a Path> {
+ path.strip_prefix(&to_strip).with_context(|| {
+ format!(
+ "'{}' is not under the specified home path ('{}')!",
+ path.display(),
+ to_strip.display()
+ )
+ })
+}
+
+fn path_to_str(path: &Path) -> Result<&str> {
+ path.to_str().with_context(|| {
+ format!(
+ "\
+Can't derive a keymapping from path: '{}' \
+because it can't be turned to a string
+",
+ path.display()
+ )
+ })
+}
+
// 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/map_tree.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
deleted file mode 100644
index 02f040b7..00000000
--- a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs
+++ /dev/null
@@ -1,436 +0,0 @@
-use std::{collections::HashMap, fmt::Display};
-
-use anyhow::{bail, Result};
-use log::{debug, trace};
-
-use super::MapKey;
-
-/// A prefix tree
-pub struct MappingTree {
- root: Node,
-}
-
-#[derive(Clone, Debug, PartialEq, Eq)]
-pub enum NodeValue {
- Parent { children: HashMap<MapKey, Node> },
- Child { path: String },
-}
-
-#[derive(Clone, Debug, PartialEq, Eq)]
-pub struct Node {
- value: NodeValue,
-}
-
-impl MappingTree {
- pub fn new() -> Self {
- Self {
- root: Node::new_parent(),
- }
- }
-
- /// Returns the node at the key, otherwise None
- pub fn get(&self, key: &[MapKey]) -> Option<&Node> {
- let mut current_node = &self.root;
- for ch in key.iter() {
- if let NodeValue::Parent { children } = ¤t_node.value {
- current_node = children.get(&ch)?
- } else {
- return None;
- }
- }
-
- 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;
- for ch in key.iter() {
- 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, Vec<MapKey>) {
- let mut current_node = &self.root;
- let mut current_key = vec![];
-
- for ch in key.iter() {
- if let NodeValue::Parent { children } = ¤t_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, current_key);
- }
- }
-
- (current_node, current_key)
- }
-
- pub fn include(&mut self, path: &str) -> Result<()> {
- let associated_key = MapKey::new_ones_from_path(path, 1);
- 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_node(&mut self, key: &[MapKey], node: Node) -> Result<()> {
- let (_node, found_key) = self.try_get(key).clone();
-
- if found_key != key {
- let needed_nodes_key = key
- .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(&found_key[..])
- .expect("This should always exists");
- 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.clone()
- } else {
- Node::new_parent()
- };
-
- current_node = match ¤t_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: '.',
- 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")
- }
- };
-
- 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.
- // 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 = 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!",
- 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 = 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 '{}' ('{}')",
- 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() - 2])
- .expect("This will exist");
-
- if let NodeValue::Parent { children } = &mut parent.value {
- 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(())
- }
-}
-
-impl Node {
- pub fn new_child(path: String) -> Self {
- Self {
- value: NodeValue::Child { path },
- }
- }
- pub fn new_parent() -> Self {
- Self {
- value: NodeValue::Parent {
- children: HashMap::new(),
- },
- }
- }
-}
-
-impl Display for MappingTree {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- 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 node_value = match &node.value {
- NodeValue::Parent { children: _ } => "<Parent>",
- NodeValue::Child { path } => path,
- };
-
- let new_idention = if !has_parent {
- String::new()
- } else if is_last {
- indention.replace('│', " ") + " "
- } else {
- 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(&location),
- node_value,
- )?;
-
- match &node.value {
- NodeValue::Parent { children } => {
- let value_length = children.len();
- let mut 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(), vec![], false, false, f)?;
-
- Ok(())
- }
-}
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/display.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/display.rs
new file mode 100644
index 00000000..778ade95
--- /dev/null
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/display.rs
@@ -0,0 +1,88 @@
+use std::fmt::Display;
+
+use crate::mapping::{
+ map_tree::{Node, NodeValue},
+ MapKey,
+};
+
+use super::MappingTree;
+
+impl Display for MappingTree {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ fn write_node(
+ f: &mut std::fmt::Formatter<'_>,
+ node: &Node,
+ indention: String,
+ location: Vec<MapKey>,
+ is_last: bool,
+ is_root: bool,
+ ) -> std::fmt::Result {
+ let node_value = match &node.value {
+ NodeValue::Parent { children: _ } => "<Parent>".to_owned(),
+ NodeValue::Child { path, extandable } => {
+ path.to_owned() + if *extandable { " [exten.]" } else { " [stop]" }
+ }
+ };
+
+ let new_idention = indention.clone()
+ + if is_root {
+ ""
+ } else {
+ match is_last {
+ true => " ",
+ false => "│ ",
+ }
+ };
+
+ let bullet = match is_last {
+ true => String::from("└── "),
+ false => String::from("├── "),
+ };
+
+ if is_root {
+ write!(f, ": {}\n", node_value)?;
+ } else {
+ write!(
+ f,
+ "{}{}\x1b[1;33m{}\x1b[0m: {}\n",
+ indention,
+ bullet,
+ MapKey::display(&location),
+ node_value,
+ )?;
+ };
+
+ match &node.value {
+ NodeValue::Parent { children } => {
+ let mut children_vec: Vec<(&MapKey, &Node)> = children.iter().collect();
+ children_vec.sort_by(|(a, _), (b, _)| a.key.cmp(&b.key));
+
+ let mut counter = 1;
+ for (key, child) in &children_vec {
+ let mut new_location = location.clone();
+ new_location.push((*key).to_owned());
+
+ write_node(
+ f,
+ child,
+ new_idention.clone(),
+ new_location.clone(),
+ counter == children_vec.len(),
+ false,
+ )?;
+ counter += 1;
+ }
+ }
+ NodeValue::Child { path: _, extandable: _ } => {
+ // Do nothing and stop the recursion
+ }
+ }
+
+ Ok(())
+ }
+
+ write_node(f, &self.root, String::new(), vec![], false, true)?;
+
+ Ok(())
+ }
+}
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/iterator.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/iterator.rs
new file mode 100644
index 00000000..33c27540
--- /dev/null
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/iterator.rs
@@ -0,0 +1,45 @@
+use crate::mapping::MapKey;
+
+use super::{MappingTree, Node, NodeValue};
+
+pub struct MappingTreeIterator {
+ children: Vec<(Vec<MapKey>, String)>,
+}
+
+impl MappingTreeIterator {
+ pub fn new(tree: &MappingTree) -> Self {
+ let children = extract_child(vec![], &tree.root);
+
+ Self { children }
+ }
+}
+
+fn extract_child(current_key: Vec<MapKey>, node: &Node) -> Vec<(Vec<MapKey>, String)> {
+ match &node.value {
+ NodeValue::Parent { children } => children
+ .iter()
+ .map(|(key, value)| {
+ let mut new_key = current_key.clone();
+ new_key.push(key.to_owned());
+
+ extract_child(new_key, value)
+ })
+ .flatten()
+ .collect(),
+ NodeValue::Child { path, extandable } => {
+ if *extandable {
+ vec![(current_key, path.to_string())]
+ } else {
+ vec![]
+ }
+ }
+ }
+}
+
+impl Iterator for MappingTreeIterator {
+ type Item = (Vec<MapKey>, String);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.children.pop()
+ }
+}
diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/mod.rs b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/mod.rs
new file mode 100644
index 00000000..44adc483
--- /dev/null
+++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree/mod.rs
@@ -0,0 +1,424 @@
+use std::{collections::HashMap, mem};
+
+use anyhow::{bail, Result};
+use log::debug;
+
+use self::iterator::MappingTreeIterator;
+
+use super::MapKey;
+
+pub mod display;
+pub mod iterator;
+
+/// A prefix tree
+#[derive(Debug)]
+pub struct MappingTree {
+ root: Node,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum NodeValue {
+ Parent { children: HashMap<MapKey, Node> },
+ Child { path: String, extandable: bool },
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct Node {
+ value: NodeValue,
+}
+
+impl MappingTree {
+ pub fn new() -> Self {
+ Self {
+ root: Node::new_parent(),
+ }
+ }
+
+ pub fn root_node(&self) -> &Node {
+ &self.root
+ }
+
+ pub fn iter(&self) -> MappingTreeIterator {
+ MappingTreeIterator::new(&self)
+ }
+
+ /// Returns the node at the key, otherwise None
+ pub fn get(&self, key: &[MapKey]) -> Option<&Node> {
+ let mut current_node = &self.root;
+ for ch in key.iter() {
+ if let NodeValue::Parent { children } = ¤t_node.value {
+ current_node = children.get(&ch)?
+ } else {
+ return None;
+ }
+ }
+
+ 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;
+ for ch in key.iter() {
+ 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, Vec<MapKey>) {
+ let mut current_node = &self.root;
+ let mut current_key = vec![];
+
+ for ch in key.iter() {
+ if let NodeValue::Parent { children } = ¤t_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, current_key);
+ }
+ }
+
+ (current_node, current_key)
+ }
+
+ pub fn include(&mut self, path: &str) -> Result<()> {
+ let associated_key = MapKey::new_ones_from_path(path, 1);
+ 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 interleave(&mut self, key: &[MapKey], node: Node) -> Result<()> {
+ let want_to_be_parent = self.get_mut(&key).expect("This value exists");
+ let (parent_value, _parent_children) = if let NodeValue::Parent { children } = node.value {
+ (
+ NodeValue::Parent {
+ children: children.clone(),
+ },
+ children,
+ )
+ } else {
+ unreachable!("This value will be a parent")
+ };
+
+ let child_value = mem::replace(&mut want_to_be_parent.value, parent_value);
+ assert!(matches!(
+ child_value,
+ NodeValue::Child {
+ path: _,
+ extandable: _
+ }
+ ));
+
+ let child_value = if let NodeValue::Child { path, extandable } = child_value {
+ NodeValue::Child {
+ path,
+ extandable: false,
+ }
+ } else {
+ unreachable!("This is only a child value")
+ };
+
+ let child = Node { value: child_value };
+
+ let mut new_key = key.to_vec();
+ new_key.push(MapKey {
+ key: '.',
+ part_path: ".".to_owned(),
+ resolution: 1,
+ });
+ self.insert_node(&new_key, child)?;
+ Ok(())
+ }
+
+ pub fn replace_node(&mut self, key: &[MapKey], node: Node) -> Node {
+ let parent = self.get_mut(&key[..key.len() - 1]).expect("Must be some");
+
+ if let NodeValue::Parent { children } = &mut parent.value {
+ children
+ .insert(key[key.len() - 1].clone(), node)
+ .expect("This must exist, otherwise insert would have been used")
+ } else {
+ unreachable!("All parent nodes should be parent nodes");
+ }
+ }
+
+ pub fn insert_node(&mut self, key: &[MapKey], node: Node) -> Result<()> {
+ let (_node, found_key) = self.try_get(key).clone();
+
+ if found_key != key {
+ let needed_nodes_key = key
+ .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(&found_key[..])
+ .expect("This should always exists");
+ 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.clone()
+ } else {
+ Node::new_parent()
+ };
+
+ current_node = match ¤t_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,
+ extandable: _,
+ } => {
+ // 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: '.',
+ 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")
+ }
+ };
+
+ 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.
+ // 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 = 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!",
+ 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 = 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 '{}' ('{}')",
+ 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 will exist");
+
+ if let NodeValue::Parent { children } = &mut parent.value {
+ if let NodeValue::Child {
+ path: _,
+ extandable: _,
+ } = 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(())
+ }
+}
+
+impl Node {
+ pub fn new_child(path: String) -> Self {
+ Self {
+ value: NodeValue::Child {
+ path,
+ extandable: true,
+ },
+ }
+ }
+ pub fn new_parent() -> Self {
+ Self {
+ value: NodeValue::Parent {
+ children: HashMap::new(),
+ },
+ }
+ }
+}
--
cgit 1.4.1