diff options
Diffstat (limited to 'pkgs/sources/lf-make-map/src/mapping')
5 files changed, 721 insertions, 0 deletions
diff --git a/pkgs/sources/lf-make-map/src/mapping/map_tree/display.rs b/pkgs/sources/lf-make-map/src/mapping/map_tree/display.rs new file mode 100644 index 00000000..65302e1e --- /dev/null +++ b/pkgs/sources/lf-make-map/src/mapping/map_tree/display.rs @@ -0,0 +1,91 @@ +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/pkgs/sources/lf-make-map/src/mapping/map_tree/iterator.rs b/pkgs/sources/lf-make-map/src/mapping/map_tree/iterator.rs new file mode 100644 index 00000000..4364bb2b --- /dev/null +++ b/pkgs/sources/lf-make-map/src/mapping/map_tree/iterator.rs @@ -0,0 +1,53 @@ +use crate::mapping::MapKey; + +use super::{MappingTree, Node, NodeValue}; + +pub struct MappingTreeIterator { + children: Vec<(Vec<MapKey>, String)>, +} + +impl MappingTreeIterator { + pub fn new(tree: &MappingTree, ignore_extendable: bool) -> Self { + let children = extract_child(vec![], &tree.root, ignore_extendable); + + Self { children } + } +} + +fn extract_child( + current_key: Vec<MapKey>, + node: &Node, + ignore_extendable: bool, +) -> 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, ignore_extendable) + }) + .flatten() + .collect(), + NodeValue::Child { path, extandable } => { + if ignore_extendable { + vec![(current_key, path.to_string())] + } else { + 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/pkgs/sources/lf-make-map/src/mapping/map_tree/lf_mapping.rs b/pkgs/sources/lf-make-map/src/mapping/map_tree/lf_mapping.rs new file mode 100644 index 00000000..6d9c7a0d --- /dev/null +++ b/pkgs/sources/lf-make-map/src/mapping/map_tree/lf_mapping.rs @@ -0,0 +1,19 @@ +use std::path::PathBuf; + +use crate::mapping::MapKey; + +use super::MappingTree; + +impl MappingTree { + pub fn to_lf_mappings(self, home_path: PathBuf) -> String { + self.iter(true) + .map(|(key, value)| { + format!( + "map g{} cd \"{}\"\n", + MapKey::display(&key), + home_path.join(&value).display() + ) + }) + .collect() + } +} diff --git a/pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs b/pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs new file mode 100644 index 00000000..35e6d91d --- /dev/null +++ b/pkgs/sources/lf-make-map/src/mapping/map_tree/mod.rs @@ -0,0 +1,402 @@ +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; +pub mod lf_mapping; + +/// 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, ignore_extendable: bool) -> MappingTreeIterator { + MappingTreeIterator::new(&self, ignore_extendable) + } + + /// 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 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, + ); + } + + 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(), + }, + } + } +} diff --git a/pkgs/sources/lf-make-map/src/mapping/mod.rs b/pkgs/sources/lf-make-map/src/mapping/mod.rs new file mode 100644 index 00000000..114fdca0 --- /dev/null +++ b/pkgs/sources/lf-make-map/src/mapping/mod.rs @@ -0,0 +1,156 @@ +use std::{ + fmt::{Display, Write}, + hash::Hash, +}; + +use log::debug; + +pub mod map_tree; + +#[derive(Clone, Debug, Eq)] +pub struct MapKey { + pub key: char, + + resolution: usize, + + /// Part of the path, used to derive the key + part_path: String, +} + +impl Hash for MapKey { + fn hash<H: std::hash::Hasher>(&self, state: &mut H) { + self.key.hash(state) + } +} + +impl PartialEq for MapKey { + fn eq(&self, other: &Self) -> bool { + self.key == other.key + } +} + +impl MapKey { + pub fn new_from_part_path(part_path: &str, resolution: usize) -> Vec<Self> { + let key = Self::part_path_to_key(&part_path, resolution); + + key.chars() + .map(|ch| Self { + key: ch, + resolution, + part_path: part_path.to_owned(), + }) + .collect() + } + + pub fn new_ones_from_path(path: &str, number_of_chars: usize) -> Vec<Self> { + let key: Vec<MapKey> = path + .split('/') + .map(|part| Self::new_from_part_path(part, number_of_chars)) + .flatten() + .collect(); + + debug!( + "Generated full MapKeys: '{}' -> '{}'", + path, + MapKey::display(&key) + ); + key + } + + pub fn increment(&self, target_resolution: usize) -> Vec<Self> { + let new_resolution = target_resolution; + + // debug!("Incrementing: '{}' ('{}')", &self, &self.part_path); + + let added_chars = if new_resolution < self.part_path.len() { + MapKey::part_path_to_key(&self.part_path, new_resolution) + } else { + let mut generated_chars = + MapKey::part_path_to_key(&self.part_path, self.part_path.len()); + + generated_chars.extend( + (0..(new_resolution - self.part_path.len())) + .into_iter() + .map(|_| self.part_path.chars().last().expect("This will exists")), + ); + + generated_chars + }; + + let part_path = self.part_path.clone(); + let output: Vec<Self> = added_chars + .chars() + .enumerate() + .map(|(res, ch)| MapKey { + key: ch, + resolution: res + 1, + part_path: part_path.clone(), + }) + .collect(); + + // debug!("Finished increment: '{}' ('{}')", MapKey::display(&output), output[0].part_path); + output + } + + 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 { + fn make(pat: char, part: &str, number_of_chars: usize) -> String { + let mut acc = String::new(); + + if !part.split(pat).all(|part| part.len() > 0) { + panic!( + "\ +Can't turn this path '{}' to a mapping. +This should not happen, please report the bug!", + part + ) + } + + let mut last_working = None; + for i in 0..number_of_chars { + for str in part.split(pat) { + if acc.len() != number_of_chars { + acc.push(match str.chars().nth(i) { + Some(ch) => ch, + None => { + if let Some(last) = last_working { + str.chars().nth(last).expect("This should always exist") + } else { + last_working = Some(i - 1); + str.chars().nth(i - 1).expect("This should always exist") + } + } + }) + } + } + } + + acc + } + + let value = if part.contains('_') && !part.starts_with('_') && !part.ends_with('_') { + make('_', part, number_of_chars) + } else if part.contains('-') && !part.starts_with('-') && !part.ends_with('-') { + make('-', part, number_of_chars) + } else { + part.chars().take(number_of_chars).collect::<String>() + }; + + assert_eq!( + value.len(), + number_of_chars, + "'{}' does not have expected length of: {}", + value, + number_of_chars + ); + value + } +} + +impl Display for MapKey { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.write_char(self.key) + } +} |