diff options
Diffstat (limited to 'sys/nixpkgs/pkgs/lf-make-map/src/mapping')
| -rw-r--r-- | sys/nixpkgs/pkgs/lf-make-map/src/mapping/error.rs | 6 | ||||
| -rw-r--r-- | sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs | 265 | ||||
| -rw-r--r-- | sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs | 109 |
3 files changed, 267 insertions, 113 deletions
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 } = ¤t_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 } = ¤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; + 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 ¤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: ".".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) } } |