From 13539f1a411c907a450ea0f64ce75fd1f3ff214d Mon Sep 17 00:00:00 2001 From: Benedikt Peetz Date: Tue, 7 May 2024 22:17:13 +0200 Subject: feat(pkgs/lf-make-map): Ensure that it works (for a depth=1) --- sys/nixpkgs/pkgs/lf-make-map/src/main.rs | 14 +- .../pkgs/lf-make-map/src/mapping/map_tree.rs | 171 +++++++++++++++++--- sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs | 179 ++++++++++----------- 3 files changed, 243 insertions(+), 121 deletions(-) (limited to 'sys') diff --git a/sys/nixpkgs/pkgs/lf-make-map/src/main.rs b/sys/nixpkgs/pkgs/lf-make-map/src/main.rs index 8a1ca602..362b28db 100644 --- a/sys/nixpkgs/pkgs/lf-make-map/src/main.rs +++ b/sys/nixpkgs/pkgs/lf-make-map/src/main.rs @@ -42,15 +42,17 @@ fn main() -> anyhow::Result<()> { ) })?; - mappings.include(path.to_str().with_context(|| { - format!( - "\ + 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() - ) - })?); + path.display() + ) + })?) + .with_context(|| format!("Failed to include path: '{}'", path.display()))?; trace!("Processed '{}'..", directory.path().display()); } 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 { + 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(()) } } 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 8bf6bbe0..129e9673 100644 --- a/sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs +++ b/sys/nixpkgs/pkgs/lf-make-map/src/mapping/mod.rs @@ -1,4 +1,7 @@ -use std::{fmt::Display, hash::Hash}; +use std::{ + fmt::{Display, Write}, + hash::Hash, +}; use log::debug; @@ -7,7 +10,7 @@ pub mod map_tree; #[derive(Clone, Debug, Eq)] pub struct MapKey { - pub key: String, + pub key: char, resolution: usize, @@ -28,29 +31,23 @@ impl PartialEq for MapKey { } impl MapKey { - pub fn new_from_part_path(part_path: &str, resolution: usize) -> Self { + pub fn new_from_part_path(part_path: &str, resolution: usize) -> Vec { let key = Self::part_path_to_key(&part_path, resolution); - Self { - key, - resolution, - part_path: part_path.to_owned(), - } - } - 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); - } + 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 { + pub fn new_ones_from_path(path: &str, number_of_chars: usize) -> Vec { let key: Vec = path .split('/') .map(|part| Self::new_from_part_path(part, number_of_chars)) + .flatten() .collect(); debug!( @@ -61,94 +58,92 @@ impl MapKey { key } + pub fn increment(&self, target_resolution: usize) -> Vec { + 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 + }; + assert_eq!(added_chars.len(), new_resolution,); + + let part_path = self.part_path.clone(); + let output: Vec = 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(); + + 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.split('_') - .map(|ch| ch.chars().take(number_of_chars).collect::>()) - .flatten() - .collect() + make('_', part, number_of_chars) } else if part.contains('-') { - part.split('-') - .map(|ch| ch.chars().take(number_of_chars).collect::>()) - .flatten() - .collect() + make('-', part, number_of_chars) } else { part.chars().take(number_of_chars).collect::() }; + + assert_eq!( + value.len(), + number_of_chars, + "'{}' is not {}", + value, + number_of_chars + ); value } } impl Display for MapKey { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - f.write_str(&self.key) - } -} - -// pub fn gen_hot_key(path: &Path, base_path: &Path, amount_of_chars: usize) -> String { -// let mut return_val = String::from("g"); -// if path_filename_as_str.contains("_") { -// path_filename_as_str.split("_").for_each(|a| { -// return_val.push( -// a.chars() -// .nth(0) -// .expect("All names should have a first char"), -// ) -// }); -// } else { -// if path == base_path { -// return_val.push( -// path_filename_as_str -// .chars() -// .nth(0) -// .expect("All names should have a first char"), -// ); -// } else { -// for a in 0..amount_of_chars { -// return_val.push(if let Some(b) = path_filename_as_str.chars().nth(a) { -// b -// } else { -// path_filename_as_str -// .chars() -// .nth(0) -// .expect("All names should have a first char") -// }); -// } -// } -// } -// if path == base_path { -// return_val.push('.'); -// } -// return_val -// } - -#[cfg(test)] -mod tests { - use super::*; - #[test] - fn gen_hot_key_test() { - let gen1 = gen_hot_key( - Path::new("/home/dt/repos/java_script"), - Path::new("/home/dt/repos"), - 1, - ); - assert_eq!(gen1, "grjs".to_owned()); - } - #[test] - fn gen_hot_key_test_for_same_names() { - let gen1 = gen_hot_key(Path::new("/home/dt/repos/"), Path::new("/home/dt/repos"), 1); - assert_eq!(gen1, "gr.".to_owned()); - } - #[test] - fn gen_hot_key_test_for_non_underscore_name() { - let gen1 = gen_hot_key( - Path::new("/home/dt/repos/rust"), - Path::new("/home/dt/repos"), - 1, - ); - assert_eq!(gen1, "grr".to_owned()); + f.write_char(self.key) } } -- cgit 1.4.1