diff options
Diffstat (limited to '')
| -rw-r--r-- | pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs | 337 |
1 files changed, 206 insertions, 131 deletions
diff --git a/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs b/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs index 114fdca0..21392388 100644 --- a/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs +++ b/pkgs/by-name/lf/lf-make-map/src/mapping/mod.rs @@ -1,156 +1,231 @@ -use std::{ - fmt::{Display, Write}, - hash::Hash, -}; - -use log::debug; - -pub mod map_tree; - -#[derive(Clone, Debug, Eq)] -pub struct MapKey { - pub key: char, +// nixos-config - My current NixOS configuration +// +// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de> +// SPDX-License-Identifier: GPL-3.0-or-later +// +// This file is part of my nixos-config. +// +// You should have received a copy of the License along with this program. +// If not, see <https://www.gnu.org/licenses/gpl-3.0.txt>. + +use anyhow::Result; +use keymaps::map_tree::{Node, Trie}; +use log::{Level, debug, log_enabled, trace}; +use map_key::MapKey; + +pub mod lf_mapping; +pub mod map_key; + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +pub struct MapChild { + pub path: String, + pub expendable: bool, +} - resolution: usize, +impl std::fmt::Display for MapChild { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.write_str(&self.path)?; + if !self.expendable { + f.write_str(" [stop]")?; + } - /// Part of the path, used to derive the key - part_path: String, + Ok(()) + } } -impl Hash for MapKey { - fn hash<H: std::hash::Hasher>(&self, state: &mut H) { - self.key.hash(state) +pub struct MappingsTrie(pub Trie<MapKey, MapChild>); +impl std::fmt::Display for MappingsTrie { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + self.0.fmt(f) } } -impl PartialEq for MapKey { - fn eq(&self, other: &Self) -> bool { - self.key == other.key +impl MappingsTrie { + pub fn new() -> Self { + Self(Trie::new()) } -} -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(crate) fn include(&mut self, path: &str) -> Result<()> { + let associated_key = MapKey::new_ones_from_path(path, 1); + self.insert(&associated_key, path) } - 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(crate) fn insert(&mut self, keys: &[MapKey], path: &str) -> Result<()> { + let value = Node::new_child(MapChild { + path: path.to_owned(), + expendable: true, + }); + self.insert_node(keys, value) } - pub fn increment(&self, target_resolution: usize) -> Vec<Self> { - let new_resolution = target_resolution; + pub(crate) fn insert_node( + &mut self, + keys: &[MapKey], + node: Node<MapKey, MapChild>, + ) -> Result<()> { + if let Err(err) = self.0.insert_node(keys, &node) { + match err { + keymaps::error::TrieInsert::KeyAlreadySet(found_keys) => { + // 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 no longer equal. + // 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. + assert_eq!(keys, found_keys); + + let mut foreign_keys = + vec![found_keys.last().expect("This will exist").clone()]; + let mut our_keys = vec![keys.last().expect("This will exist").clone()]; + + debug!( + "'{}' ('{}') and '{}' ('{}') are the same, trying to find a better combination!", + MapKey::display(&our_keys), + our_keys[0].part_path, + MapKey::display(&foreign_keys), + foreign_keys[0].part_path, + ); + + our_keys[0].can_tiebreak_with(&foreign_keys[0])?; + + while our_keys == foreign_keys { + our_keys = + our_keys[0].increment(our_keys[our_keys.len() - 1].resolution + 1); + foreign_keys = foreign_keys[0] + .increment(foreign_keys[foreign_keys.len() - 1].resolution + 1); + debug!( + "Now its: '{}' ('{}') and '{}' ('{}')", + MapKey::display(&our_keys), + our_keys[0].part_path, + MapKey::display(&foreign_keys), + foreign_keys[0].part_path, + ); + } + debug!( + "Found a better one: '{}' ('{}') and '{}' ('{}')", + MapKey::display(&our_keys), + our_keys[0].part_path, + MapKey::display(&foreign_keys), + foreign_keys[0].part_path, + ); + + let parent_keys = &found_keys[..&found_keys.len() - 1]; + + { + if self + .0 + .get(&found_keys) + .expect("This will exist") + .value() + .is_some() + { + // This is a child, we must replace it with a parent. + let other_node = self + .0 + .replace_node(&found_keys, Node::new_parent()) + .expect("This node exists"); + + { + let mut full_foreign_keys = parent_keys.to_vec(); + full_foreign_keys.append(&mut foreign_keys); + self.insert_node(&full_foreign_keys, other_node)?; + } + } + } - // debug!("Incrementing: '{}' ('{}')", &self, &self.part_path); + { + let mut full_our_keys = parent_keys.to_vec(); + full_our_keys.append(&mut our_keys); + self.insert_node(&full_our_keys, node)?; + } - let added_chars = if new_resolution < self.part_path.len() { - MapKey::part_path_to_key(&self.part_path, new_resolution) + Ok(()) + } + keymaps::error::TrieInsert::KeyIncludesChild { + child_key: key, + child_value, + } => { + // 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. + + assert_eq!(key, keys); + + let (fetched_child_value, mut child_key) = self.0.try_get(keys); + assert_eq!(fetched_child_value.value(), Some(&child_value)); + + trace!( + "Replacing child ('{}') with a parent, so that we can continue from this point.", + MapKey::display(&child_key) + ); + + let child = self + .0 + .replace_node(&child_key, Node::new_parent()) + .expect("Node exists"); + assert_eq!(child.value(), Some(&child_value)); + + child_key.push(MapKey { + key: '.', + part_path: ".".to_owned(), + resolution: 1, + }); + self.0 + .insert_node(&child_key, &child) + .expect("We just created a parent here"); + + // Recursive call, because this key could have hit the previous child directly + // (thus it will now trigger the `KeyAlreadySet` error.) + self.insert_node(keys, node) + } + } } 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 + Ok(()) + } } - 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 - ) - } + /// Add a new [`MappingsTrie`] at the position `keys` into this Trie. + pub(crate) fn add_trie(&mut self, keys: &[MapKey], trie: Self) -> Result<()> { + if log_enabled!(Level::Trace) { + trace!("Adding mappings under '{}':", MapKey::display(keys)); + eprintln!("{trie}"); - 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") - } - } - }) - } - } - } + trace!("Self is:"); + eprintln!("{self}"); + } + + let replaced = self + .0 + .replace_node(keys, trie.0.root_node().to_owned()) + .expect("This value exists"); - acc + if log_enabled!(Level::Trace) { + trace!("After replace adding the new trie"); + eprintln!("{self}"); } - 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 - } -} + { + let mut new_keys = keys.to_vec(); + new_keys.push(MapKey { + key: '.', + part_path: ".".to_owned(), + resolution: 1, + }); + + let mut value = replaced.value().expect("Is a child").clone(); + value.expendable = false; + + trace!("Re-inserting '{}' into self.", MapKey::display(keys)); + self.0 + .insert_node(&new_keys, &Node::new_child(value)) + .expect("This key is not used."); + } -impl Display for MapKey { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - f.write_char(self.key) + Ok(()) } } |