path: root/pkgs/by-name/lf/lf-make-map/src/mapping/map_tree/mod.rs

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 } = &current_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 &current_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(),
            },
        }
    }
}