use bytes_cast::BytesCast;

use micro_timer::timed;

use std::convert::TryInto;

use std::path::PathBuf;

use super::path_with_basename::WithBasename;

use crate::dirstate::parsers::clear_ambiguous_mtime;

use crate::dirstate::parsers::pack_entry;

use crate::dirstate::parsers::packed_entry_size;

use crate::dirstate::parsers::parse_dirstate_entries;

use crate::dirstate::parsers::Timestamp;

use crate::matchers::Matcher;

use crate::utils::hg_path::{HgPath, HgPathBuf};

use crate::CopyMapIter;

use crate::DirstateEntry;

use crate::DirstateError;

use crate::DirstateMapError;

use crate::DirstateParents;

use crate::DirstateStatus;

use crate::EntryState;

use crate::FastHashMap;

use crate::PatternFileWarning;

use crate::StateMapIter;

use crate::StatusError;

use crate::StatusOptions;

pub struct DirstateMap {

    pub(super) root: ChildNodes,

    /// Number of nodes anywhere in the tree that have `.entry.is_some()`.

    nodes_with_entry_count: usize,

    /// Number of nodes anywhere in the tree that have

    /// `.copy_source.is_some()`.

    nodes_with_copy_source_count: usize,

}

/// Using a plain `HgPathBuf` of the full path from the repository root as a

/// map key would also work: all paths in a given map have the same parent

/// path, so comparing full paths gives the same result as comparing base

/// names. However `BTreeMap` would waste time always re-comparing the same

/// string prefix.

pub(super) type ChildNodes = FastHashMap<WithBasename<HgPathBuf>, Node>;

/// Represents a file or a directory

#[derive(Default)]

pub(super) struct Node {

    /// `None` for directories

    pub(super) entry: Option<DirstateEntry>,

    pub(super) copy_source: Option<HgPathBuf>,

    pub(super) children: ChildNodes,

    /// How many (non-inclusive) descendants of this node are tracked files

    tracked_descendants_count: usize,

}

impl Node {

    pub(super) fn state(&self) -> Option<EntryState> {

        self.entry.as_ref().map(|entry| entry.state)

    }

}

/// `(full_path, entry, copy_source)`

type NodeDataMut<'a> = (

    &'a WithBasename<HgPathBuf>,

    &'a mut Option<DirstateEntry>,

    &'a mut Option<HgPathBuf>,

);

impl DirstateMap {

    pub fn new() -> Self {

        Self {

            root: ChildNodes::default(),

            nodes_with_entry_count: 0,

            nodes_with_copy_source_count: 0,

        }

    }

    fn get_node(&self, path: &HgPath) -> Option<&Node> {

        let mut children = &self.root;

        let mut components = path.components();

        let mut component =

            components.next().expect("expected at least one components");

        loop {

            let child = children.get(component)?;

            if let Some(next_component) = components.next() {

                component = next_component;

                children = &child.children;

            } else {

                return Some(child);

            }

        }

    }

    /// Returns a mutable reference to the node at `path` if it exists

    ///

    /// This takes `root` instead of `&mut self` so that callers can mutate

    /// other fields while the returned borrow is still valid

    fn get_node_mut<'tree>(

        root: &'tree mut ChildNodes,

        path: &HgPath,

    ) -> Option<&'tree mut Node> {

        Self::get_node_mut_tracing_ancestors(root, path, |_| {})

    }

    /// Same as `get_node_mut`, and calls `each_ancestor` for each ancestor of

    /// the node.

    ///

    /// Note that `each_ancestor` may be called (with what would be ancestors)

    /// even if it turns out there is no node at `path`.

    fn get_node_mut_tracing_ancestors<'tree>(

        root: &'tree mut ChildNodes,

        path: &HgPath,

        mut each_ancestor: impl FnMut(&mut Node),

    ) -> Option<&'tree mut Node> {

        let mut children = root;

        let mut components = path.components();

        let mut component =

            components.next().expect("expected at least one components");

        loop {

            let child = children.get_mut(component)?;

            if let Some(next_component) = components.next() {

                each_ancestor(child);

                component = next_component;

                children = &mut child.children;

            } else {

                return Some(child);

            }

        }

    }

    fn get_or_insert_node<'tree>(

        root: &'tree mut ChildNodes,

        path: &HgPath,

    ) -> &'tree mut Node {

        Self::get_or_insert_node_tracing_ancestors(root, path, |_| {})

    }

    fn get_or_insert_node_tracing_ancestors<'tree>(

        root: &'tree mut ChildNodes,

        path: &HgPath,

        mut each_ancestor: impl FnMut(&mut Node),

    ) -> &'tree mut Node {

        let mut child_nodes = root;

        let mut inclusive_ancestor_paths =

            WithBasename::inclusive_ancestors_of(path);

        let mut ancestor_path = inclusive_ancestor_paths

            .next()

            .expect("expected at least one inclusive ancestor");

        loop {

            // TODO: can we avoid allocating an owned key in cases where the

            // map already contains that key, without introducing double

            // lookup?

            let child_node =

                child_nodes.entry(ancestor_path.to_owned()).or_default();

            if let Some(next) = inclusive_ancestor_paths.next() {

                each_ancestor(child_node);

                ancestor_path = next;

                child_nodes = &mut child_node.children;

            } else {

                return child_node;

            }

        }

    }

    fn add_or_remove_file(

        &mut self,

        path: &HgPath,

        old_state: EntryState,

        new_entry: DirstateEntry,

    ) {

        let tracked_count_increment =

            match (old_state.is_tracked(), new_entry.state.is_tracked()) {

                (false, true) => 1,

                (true, false) => -1,

                _ => 0,

            };

        let node = Self::get_or_insert_node_tracing_ancestors(

            &mut self.root,

            path,

            |ancestor| {

                // We can’t use `+= increment` because the counter is unsigned,

                // and we want debug builds to detect accidental underflow

                // through zero

                match tracked_count_increment {

                    1 => ancestor.tracked_descendants_count += 1,

                    -1 => ancestor.tracked_descendants_count -= 1,

                    _ => {}

                }

            },

        );

        if node.entry.is_none() {

            self.nodes_with_entry_count += 1

        }

        node.entry = Some(new_entry)

    }

    fn iter_nodes<'a>(

        &'a self,

    ) -> impl Iterator<Item = (&'a WithBasename<HgPathBuf>, &'a Node)> + 'a

    {

        // Depth first tree traversal.

        //

        // If we could afford internal iteration and recursion,

        // this would look like:

        //

        // ```

        // fn traverse_children(

        //     children: &ChildNodes,

        //     each: &mut impl FnMut(&Node),

        // ) {

        //     for child in children.values() {

        //         traverse_children(&child.children, each);

        //         each(child);

        //     }

        // }

        // ```

        //

        // However we want an external iterator and therefore can’t use the

        // call stack. Use an explicit stack instead:

        let mut stack = Vec::new();

        let mut iter = self.root.iter();

        std::iter::from_fn(move || {

            while let Some((key, child_node)) = iter.next() {

                // Pseudo-recursion

                let new_iter = child_node.children.iter();

                let old_iter = std::mem::replace(&mut iter, new_iter);

                stack.push((key, child_node, old_iter));

            }

            // Found the end of a `children.iter()` iterator.

            if let Some((key, child_node, next_iter)) = stack.pop() {

                // "Return" from pseudo-recursion by restoring state from the

                // explicit stack

                iter = next_iter;

                Some((key, child_node))

            } else {

                // Reached the bottom of the stack, we’re done

                None

            }

        })

    }

    /// Mutable iterator for the `(entry, copy source)` of each node.

    ///

    /// It would not be safe to yield mutable references to nodes themeselves

    /// with `-> impl Iterator<Item = &mut Node>` since child nodes are

    /// reachable from their ancestor nodes, potentially creating multiple

    /// `&mut` references to a given node.

    fn iter_node_data_mut<'a>(

        &'a mut self,

    ) -> impl Iterator<Item = NodeDataMut<'a>> + 'a {

        // Explict stack for pseudo-recursion, see `iter_nodes` above.

        let mut stack = Vec::new();

        let mut iter = self.root.iter_mut();

        std::iter::from_fn(move || {

            while let Some((key, child_node)) = iter.next() {

                // Pseudo-recursion

                let data =

                    (key, &mut child_node.entry, &mut child_node.copy_source);

                let new_iter = child_node.children.iter_mut();

                let old_iter = std::mem::replace(&mut iter, new_iter);

                stack.push((data, old_iter));

            }

            // Found the end of a `children.values_mut()` iterator.

            if let Some((data, next_iter)) = stack.pop() {

                // "Return" from pseudo-recursion by restoring state from the

                // explicit stack

                iter = next_iter;

                Some(data)

            } else {

                // Reached the bottom of the stack, we’re done

                None

            }

        })

    }

}

impl super::dispatch::DirstateMapMethods for DirstateMap {

    fn clear(&mut self) {

        self.root.clear();

        self.nodes_with_entry_count = 0;

        self.nodes_with_copy_source_count = 0;

    }

    fn add_file(

        &mut self,

        filename: &HgPath,

        old_state: EntryState,

        entry: DirstateEntry,

    ) -> Result<(), DirstateMapError> {

        self.add_or_remove_file(filename, old_state, entry);

        Ok(())

    }

    fn remove_file(

        &mut self,

        filename: &HgPath,

        old_state: EntryState,

        size: i32,

    ) -> Result<(), DirstateMapError> {

        let entry = DirstateEntry {

            state: EntryState::Removed,

            mode: 0,

            size,

            mtime: 0,

        };

        self.add_or_remove_file(filename, old_state, entry);

        Ok(())

    }

    fn drop_file(

        &mut self,

        filename: &HgPath,

        old_state: EntryState,

    ) -> Result<bool, DirstateMapError> {

        let was_tracked = old_state.is_tracked();

        if let Some(node) = Self::get_node_mut_tracing_ancestors(

            &mut self.root,

            filename,

            |ancestor| {

                if was_tracked {

                    ancestor.tracked_descendants_count -= 1

                }

            },

        ) {

            let had_entry = node.entry.is_some();

            let had_copy_source = node.copy_source.is_some();

            // TODO: this leaves in the tree a "non-file" node. Should we

            // remove the node instead, together with ancestor nodes for

            // directories that become empty?

            node.entry = None;

            node.copy_source = None;

            if had_entry {

                self.nodes_with_entry_count -= 1

            }

            if had_copy_source {

                self.nodes_with_copy_source_count -= 1

            }

            Ok(had_entry)

        } else {

            assert!(!was_tracked);

            Ok(false)