diff options
Diffstat (limited to 'sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs')
| -rw-r--r-- | sys/nixpkgs/pkgs/lf-make-map/src/mapping/map_tree.rs | 171 |
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(()) } } |