// org id GEhwQUzK6088geMhP32RRVZ2gKcVn8vpgw30CsBQVAw=
//! Manipulating the internal representation of files and directories
//! tracked by Pijul (i.e. adding files, removing files, getting file
//! names…).
//!
//! Pijul tracks files in two different ways: one is the *graph*,
//! where changes are applied. The other one is the *working copy*,
//! where some filesystem changes are not yet recorded. The purpose of
//! this double representation is to be able to compare a file from
//! the graph with its version in the working copy, even if its name
//! has changed in the working copy.
//!
//! The functions of this module work at exactly one of these two
//! levels. Changing the graph is done by recording and applying a
//! change, and changing the working copy is done either by some of the
//! functions in this module, or by outputting the graph to the
//! working copy (using the [output module](../output/index.html)).
use crate::changestore::*;
use crate::pristine::*;
use crate::small_string::*;
use crate::Error;
use std::iter::Iterator;

pub(crate) fn create_new_inode<T: MutTxnT>(txn: &mut T) -> Inode {
    let mut already_taken = true;
    let mut inode: Inode = Inode::ROOT;
    while already_taken {
        inode = Inode::random();
        already_taken = txn.get_revtree(inode, None).is_some();
    }
    inode
}

/// Test whether `inode` is the inode of a directory (as opposed to a
/// file).
pub fn is_directory<T: TxnT>(txn: &T, inode: Inode) -> bool {
    if inode == Inode::ROOT {
        return true;
    }
    let pathid = OwnedPathId {
        parent_inode: inode,
        basename: SmallString::new(),
    };
    for (pid, _) in txn.iter_tree(pathid.clone(), None) {
        if pid < pathid {
            continue;
        } else if pid > pathid {
            break;
        }
        return true;
    }
    false
}

fn closest_in_repo_ancestor<'a, T: TxnT>(
    txn: &T,
    path: &'a str,
) -> (Inode, std::iter::Peekable<crate::path::Components<'a>>) {
    let mut components = crate::path::components(path).peekable();
    let mut fileid = OwnedPathId {
        parent_inode: Inode::ROOT,
        basename: SmallString::new(),
    };
    while let Some(c) = components.peek() {
        trace!("component {:?}", c);
        fileid.basename = SmallString::from_str(c);
        trace!("{:?}", fileid);
        let mut found = false;
        for (id, inode) in txn.iter_tree(fileid.clone(), None) {
            trace!(
                "id = {:?}, inode = {:?}, cmp = {:?}",
                id,
                inode,
                id.cmp(&fileid)
            );
            if id > fileid {
                break;
            } else if id < fileid {
                continue;
            }
            if !found {
                fileid.parent_inode = inode;
            }
            found = true;
        }
        if found {
            components.next();
        } else {
            break;
        }
    }
    (fileid.parent_inode, components)
}

/// Find the inode corresponding to that path, or return an error if
/// there's no such inode.
pub fn find_inode<T: TxnT>(txn: &T, path: &str) -> Result<Inode, anyhow::Error> {
    debug!("find_inode");
    let (inode, mut remaining_path_components) = closest_in_repo_ancestor(txn, path);
    debug!("/find_inode");
    if let Some(c) = remaining_path_components.next() {
        debug!("c = {:?}", c);
        Err((Error::FileNotInRepo {
            path: path.to_string(),
        })
        .into())
    } else {
        Ok(inode)
    }
}

/// Returns whether a path is registered in the working copy.
pub fn is_tracked<T: TxnT>(txn: &T, path: &str) -> bool {
    debug!("is_tracked {:?}", path);
    let (_, mut remaining_path_components) = closest_in_repo_ancestor(txn, path);
    debug!("/is_tracked {:?}", path);
    remaining_path_components.next().is_none()
}

/// Find the filename leading from the root to ~inode~.
pub fn inode_filename<T: TxnT>(txn: &T, inode: Inode) -> Option<String> {
    let mut components = Vec::new();
    let mut current = inode;
    loop {
        match txn.get_revtree(current, None) {
            Some(v) => {
                components.push(v.basename);
                current = v.parent_inode.clone();
                if current == Inode::ROOT {
                    break;
                }
            }
            None => {
                debug!("filename_of_inode: not in tree");
                return None;
            }
        }
    }

    let mut path = String::new();
    for c in components.iter().rev() {
        if !path.is_empty() {
            path.push('/')
        }
        path.push_str(c.as_str());
    }
    Some(path)
}

/// Record the information that `parent_inode` is now a parent of
/// file `filename`, and `filename` has inode `child_inode`.
fn make_new_child<T: MutTxnT>(
    txn: &mut T,
    parent_inode: Inode,
    filename: &str,
    is_dir: bool,
    child_inode: Option<Inode>,
) -> Result<Inode, anyhow::Error> {
    let parent_id = OwnedPathId {
        parent_inode: parent_inode,
        basename: SmallString::from_str(filename),
    };

    if let Some(inode) = txn.get_tree(parent_id.as_file_id(), None) {
        debug!("inode = {:?}", inode);
        if let Some(child) = child_inode {
            if child == inode {
                // No need to do anything.
                Ok(inode)
            } else {
                del_tree_with_rev(txn, parent_id.as_file_id(), inode)?;
                if let Some(vertex) = txn.get_inodes(inode, None) {
                    del_inodes_with_rev(txn, inode, vertex)?;
                }
                put_tree_with_rev(txn, parent_id.as_file_id(), child)?;
                Ok(child)
            }
        } else {
            Err((Error::FileAlreadyInRepo {
                path: filename.to_string(),
            })
            .into())
        }
    } else {
        let child_inode = match child_inode {
            None => create_new_inode(txn),
            Some(i) => i,
        };
        debug!("make_new_child: {:?} {:?}", parent_id, child_inode);
        put_tree_with_rev(txn, parent_id.as_file_id(), child_inode)?;

        if is_dir {
            let dir_id = OwnedPathId {
                parent_inode: child_inode,
                basename: SmallString::new(),
            };
            txn.put_tree(dir_id.as_file_id(), child_inode)?;
        };
        Ok(child_inode)
    }
}

pub(crate) fn add_inode<T: MutTxnT>(
    txn: &mut T,
    inode: Option<Inode>,
    path: &str,
    is_dir: bool,
) -> Result<(), anyhow::Error> {
    debug!("add_inode");
    if let Some(parent) = crate::path::parent(path) {
        let (current_inode, unrecorded_path) = closest_in_repo_ancestor(txn, parent);
        let mut current_inode = current_inode;
        debug!("add_inode: closest = {:?}", current_inode);
        for c in unrecorded_path {
            debug!("unrecorded: {:?}", c);
            current_inode = make_new_child(txn, current_inode, c, true, None)?
        }
        let file_name = crate::path::file_name(path).unwrap();
        debug!("add_inode: file_name = {:?}", file_name);
        make_new_child(txn, current_inode, file_name, is_dir, inode)?;
    }
    Ok(())
}

/// Move an inode (file or directory) from `origin` to `destination`,
/// (in the working copy).
///
/// **Warning**: both `origin` and `destination` must be full paths to
/// the inode being moved (unlike e.g. in the `mv` Unix command).
pub fn move_file<T: MutTxnT>(
    txn: &mut T,
    origin: &str,
    destination: &str,
) -> Result<(), anyhow::Error> {
    debug!("move_file: {},{}", origin, destination);
    move_file_by_inode(txn, find_inode(txn, origin)?, destination)?;
    Ok(())
}

pub fn move_file_by_inode<T: MutTxnT>(
    txn: &mut T,
    inode: Inode,
    destination: &str,
) -> Result<(), anyhow::Error> {
    let fileref = txn.get_revtree(inode, None).unwrap().to_owned();
    debug!("fileref = {:?}", fileref);
    del_tree_with_rev(txn, fileref.as_file_id(), inode)?;
    debug!("inode={:?} destination={}", inode, destination);
    let is_dir = txn
        .get_tree(
            (OwnedPathId {
                parent_inode: inode,
                basename: SmallString::new(),
            })
            .as_file_id(),
            None,
        )
        .is_some();
    add_inode(txn, Some(inode), destination, is_dir)?;
    Ok(())
}

pub(crate) fn rec_delete<T: MutTxnT>(
    txn: &mut T,
    parent: OwnedPathId,
    inode: Inode,
    update_inodes: bool,
) -> Result<(), anyhow::Error> {
    let file_id = OwnedPathId {
        parent_inode: inode,
        basename: SmallString::new(),
    };
    let mut children = Vec::new();
    let mut is_dir = false;
    for (k, inode) in txn.iter_tree(file_id.clone(), None) {
        if k.parent_inode > file_id.parent_inode {
            break;
        } else if k.parent_inode < file_id.parent_inode {
            continue;
        }
        is_dir = true;
        if !k.basename.is_empty() {
            children.push((k, inode))
        }
    }
    for (k, inode_) in children {
        assert_ne!(inode, inode_);
        rec_delete(txn, k, inode_, update_inodes)?;
    }
    debug!(
        "rec_delete: {:?}, {:?}, {:?}, {:?}",
        parent, file_id, inode, is_dir
    );
    if is_dir {
        assert!(txn.del_tree(file_id.as_file_id(), Some(inode))?);
    }
    if del_tree_with_rev(txn, parent.as_file_id(), inode)? {
        if let Some(vertex) = txn.get_inodes(inode, None) {
            del_inodes_with_rev(txn, inode, vertex)?;
        }
    } else {
        debug!(
            "rec_delete: {:?} {:?} not present",
            parent.as_file_id(),
            inode
        );
    }
    Ok(())
}

/// Removes a file from the repository.
pub fn remove_file<T: MutTxnT>(txn: &mut T, path: &str) -> Result<(), anyhow::Error> {
    debug!("remove file {:?}", path);
    let inode = find_inode(txn, path)?;
    let parent = txn.get_revtree(inode, None).unwrap().to_owned();
    debug!("remove file {:?} {:?}", parent, inode);
    rec_delete(txn, parent, inode, false)?;
    Ok(())
}

/// An iterator over the children (i.e. one level down) of an inode in
/// the working copy.
///
/// Constructed using
/// [`working_copy_children`](fn.working_copy_children.html).
pub struct WorkingCopyChildren<'txn, T: TxnT> {
    iter: crate::pristine::Cursor<T, &'txn T, T::TreeCursor, OwnedPathId, Inode>,
    inode: Inode,
}

impl<'txn, T: TxnT> Iterator for WorkingCopyChildren<'txn, T> {
    type Item = (SmallString, Inode);
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some((k, v)) = self.iter.next() {
                if k.parent_inode == self.inode {
                    if k.basename.len() > 0 {
                        return Some((k.basename, v));
                    }
                } else if k.parent_inode > self.inode {
                    return None;
                }
            } else {
                return None;
            }
        }
    }
}

/// Returns a list of the children of an inode, in the working copy.
pub fn working_copy_children<'txn, T: TxnT>(
    txn: &'txn T,
    inode: Inode,
) -> WorkingCopyChildren<'txn, T> {
    WorkingCopyChildren {
        iter: txn.iter_tree(
            OwnedPathId {
                parent_inode: inode,
                basename: SmallString::new(),
            },
            None,
        ),
        inode,
    }
}

/// An iterator over all the paths in the working copy.
///
/// Constructed using [`iter_working_copy`](fn.iter_working_copy.html).
pub struct WorkingCopyIterator<'txn, T: TxnT> {
    stack: Vec<(Inode, String)>,
    txn: &'txn T,
}

impl<'txn, T: TxnT> Iterator for WorkingCopyIterator<'txn, T> {
    type Item = (Inode, String);
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some((inode, name)) = self.stack.pop() {
                let fileid = OwnedPathId {
                    parent_inode: inode,
                    basename: SmallString::from_str(""),
                };
                for (k, v) in self.txn.iter_tree(fileid, None) {
                    if k.parent_inode < inode {
                        continue;
                    } else if k.parent_inode > inode {
                        break;
                    }
                    if k.basename.len() > 0 {
                        let mut name = name.clone();
                        crate::path::push(&mut name, k.basename.as_str());
                        self.stack.push((v, name))
                    }
                }
                if !name.is_empty() {
                    return Some((inode, name));
                }
            } else {
                return None;
            }
        }
    }
}

/// Returns an iterator over all the files in the working copy.
pub fn iter_working_copy<'txn, T: TxnT>(txn: &'txn T, root: Inode) -> WorkingCopyIterator<'txn, T> {
    WorkingCopyIterator {
        stack: vec![(root, String::new())],
        txn,
    }
}

/// An iterator over the children (i.e. a single level down) of an
/// inode key in the graph.
///
/// Constructed using
/// [`iter_graph_children`](fn.iter_graph_children.html).
pub struct GraphChildren<'txn, 'channel, 'changes, T: TxnT, P: ChangeStore + 'changes> {
    txn: &'txn T,
    channel: &'channel Channel<T>,
    adj: AdjacentIterator<'txn, T>,
    changes: &'changes P,
    buf: Vec<u8>,
}

impl<'txn, 'channel, 'changes, T: TxnT, P: ChangeStore + 'changes> Iterator
    for GraphChildren<'txn, 'channel, 'changes, T, P>
{
    type Item = (Position<ChangeId>, InodeMetadata, String);
    fn next(&mut self) -> Option<Self::Item> {
        self.adj.next().map(move |child| {
            let dest = find_block(self.txn, &self.channel, child.dest).unwrap();
            let mut buf = std::mem::replace(&mut self.buf, Vec::new());
            self.changes
                .get_contents(|p| self.txn.get_external(p), dest, &mut buf)
                .unwrap();
            self.buf = buf;
            let (perms, basename) = self.buf.split_at(2);
            let perms = InodeMetadata::from_basename(perms);
            let basename = std::str::from_utf8(basename).unwrap();

            let grandchild = iter_adjacent(
                self.txn,
                &self.channel,
                dest,
                EdgeFlags::FOLDER,
                EdgeFlags::FOLDER | EdgeFlags::PSEUDO | EdgeFlags::BLOCK,
            )
            .next()
            .unwrap();
            (grandchild.dest, perms, basename.to_string())
        })
    }
}

/// Returns a list of files under the given key.  The root key is
/// [`pristine::Vertex::ROOT`](../pristine/constant.Vertex::ROOT.html).
pub fn iter_graph_children<'txn, 'channel, 'changes, T, P>(
    txn: &'txn T,
    changes: &'changes P,
    channel: &'channel Channel<T>,
    key: Position<ChangeId>,
) -> GraphChildren<'txn, 'channel, 'changes, T, P>
where
    T: TxnT,
    P: ChangeStore,
{
    GraphChildren {
        buf: Vec::new(),
        adj: iter_adjacent(
            txn,
            &channel,
            key.inode_vertex(),
            EdgeFlags::FOLDER,
            EdgeFlags::FOLDER | EdgeFlags::PSEUDO | EdgeFlags::BLOCK,
        ),
        txn,
        channel,
        changes,
    }
}

/// An iterator over the basenames of an "inode key" in the graph.
///
/// See [`iter_basenames`](fn.iter_basenames.html).
pub struct GraphBasenames<'txn, 'channel, 'changes, T: TxnT, P: ChangeStore + 'changes> {
    txn: &'txn T,
    channel: &'channel Channel<T>,
    adj: AdjacentIterator<'txn, T>,
    changes: &'changes P,
    buf: Vec<u8>,
}

impl<'txn, 'channel, 'changes, T: TxnT, P: ChangeStore + 'changes> Iterator
    for GraphBasenames<'txn, 'channel, 'changes, T, P>
{
    type Item = (Position<ChangeId>, InodeMetadata, String);
    fn next(&mut self) -> Option<Self::Item> {
        self.adj.next().map(move |parent| {
            let dest = find_block_end(self.txn, &self.channel, parent.dest).unwrap();
            let mut buf = std::mem::replace(&mut self.buf, Vec::new());
            self.changes
                .get_contents(|p| self.txn.get_external(p), dest, &mut buf)
                .unwrap();
            self.buf = buf;
            let (perms, basename) = self.buf.split_at(2);
            let perms = InodeMetadata::from_basename(perms);
            let basename = std::str::from_utf8(basename).unwrap().to_string();
            let grandparent = iter_adjacent(
                self.txn,
                &self.channel,
                dest,
                EdgeFlags::FOLDER | EdgeFlags::PARENT,
                EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::PSEUDO | EdgeFlags::BLOCK,
            )
            .next()
            .unwrap();
            (grandparent.dest, perms, basename)
        })
    }
}

/// List all the basenames of an "inode key" in the graph (more than
/// one name means a conflict).
///
/// See also [`iter_paths`](fn.iter_paths.html).
pub fn iter_basenames<'txn, 'channel, 'changes, T, P>(
    txn: &'txn T,
    changes: &'changes P,
    channel: &'channel Channel<T>,
    pos: Position<ChangeId>,
) -> GraphBasenames<'txn, 'channel, 'changes, T, P>
where
    T: TxnT,
    P: ChangeStore,
{
    GraphBasenames {
        buf: Vec::new(),
        adj: iter_adjacent(
            txn,
            &channel,
            pos.inode_vertex(),
            EdgeFlags::FOLDER | EdgeFlags::PARENT,
            EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::PSEUDO,
        ),
        txn,
        channel,
        changes,
    }
}

/// Traverse the paths in the graph to a key. **Warning:** there might
/// be a number of paths exponential in the number of conflicts.
///
/// This function takes a closure `f`, which gets called on each path
/// with an iterator over the keys from the root to `key`. This
/// function stops when `f` returns `false` (or when all the paths
/// have been traversed).
///
/// See also [`iter_basenames`](fn.iter_basenames.html).
pub fn iter_paths<T: TxnT, F: FnMut(&mut dyn Iterator<Item = Position<ChangeId>>) -> bool>(
    txn: &T,
    channel: &ChannelRef<T>,
    key: Position<ChangeId>,
    mut f: F,
) {
    let channel = channel.r.borrow();
    let mut stack: Vec<(Position<ChangeId>, bool)> = vec![(key, true)];
    while let Some((cur_key, on_stack)) = stack.pop() {
        if cur_key.is_root() {
            if !f(&mut stack
                .iter()
                .filter_map(|(key, on_path)| if *on_path { Some(*key) } else { None }))
            {
                break;
            }
        } else if !on_stack {
            let e = Edge {
                flag: EdgeFlags::FOLDER | EdgeFlags::PARENT,
                dest: Position::ROOT,
                introduced_by: ChangeId::ROOT,
            };
            stack.push((cur_key, true));
            let len = stack.len();
            for (_, parent) in iter_graph(txn, &channel.graph, cur_key.inode_vertex(), Some(e))
                .take_while(|&(k, _)| k == cur_key.inode_vertex())
                .filter(|&(_, ref v)| v.flag.contains(EdgeFlags::FOLDER | EdgeFlags::PARENT))
            {
                let parent_dest = find_block_end(txn, &channel, parent.dest).unwrap();
                for (_, grandparent) in iter_graph(txn, &channel.graph, parent_dest, Some(e))
                    .take_while(|&(k, _)| k == parent_dest)
                    .filter(|&(_, ref v)| v.flag.contains(EdgeFlags::FOLDER | EdgeFlags::PARENT))
                {
                    stack.push((grandparent.dest, false))
                }
            }
            if stack.len() == len {
                stack.pop();
            }
        }
    }
}

pub(crate) fn follow_oldest_path<T: TxnT, C: ChangeStore>(
    changes: &C,
    txn: &T,
    channel: &ChannelRef<T>,
    path: &str,
) -> Result<(Position<ChangeId>, bool), anyhow::Error> {
    use crate::pristine::*;
    let channel = channel.borrow();
    debug!("follow_oldest_path = {:?}", path);
    let mut current = Position::ROOT;
    let flag0 = EdgeFlags::FOLDER;
    let flag1 = flag0 | EdgeFlags::BLOCK | EdgeFlags::PSEUDO;
    let mut name_buf = Vec::new();
    let mut ambiguous = false;
    for c in crate::path::components(path) {
        let mut next = None;
        for name in iter_adjacent(txn, &channel, current.inode_vertex(), flag0, flag1) {
            let name_dest = find_block(txn, &channel, name.dest).unwrap();
            name_buf.clear();
            debug!("getting contents {:?}", name);
            changes.get_contents(|h| txn.get_external(h), name_dest, &mut name_buf)?;

            if std::str::from_utf8(&name_buf[2..]) == Ok(c) {
                let age = txn
                    .get_changeset(&channel.changes, name.dest.change, None)
                    .unwrap();
                if let Some((ref mut next, ref mut next_age)) = next {
                    ambiguous = true;
                    if age < *next_age {
                        *next = name_dest;
                        *next_age = age;
                    }
                } else {
                    next = Some((name_dest, age));
                }
            }
        }
        if let Some((next, _)) = next {
            current = iter_adjacent(txn, &channel, next, flag0, flag1)
                .next()
                .unwrap()
                .dest
        } else {
            return Err((Error::FileNotInRepo {
                path: path.to_string(),
            })
            .into());
        }
    }
    Ok((current, ambiguous))
}

pub fn find_path<T: TxnT, C: ChangeStore>(
    changes: &C,
    txn: &T,
    channel: &Channel<T>,
    youngest: bool,
    mut v: Position<ChangeId>,
) -> Result<(String, bool), anyhow::Error> {
    debug!("oldest_path = {:?}", v);
    let mut path = Vec::new();
    let mut name_buf = Vec::new();
    let flag0 = EdgeFlags::FOLDER | EdgeFlags::PARENT;
    let flag1 = EdgeFlags::all();
    let mut all_alive = true;
    while !v.change.is_root() {
        let mut next_v = None;
        let mut alive = false;
        let inode_vertex = find_block_end(txn, &channel, v).unwrap();
        assert_eq!(inode_vertex, v.inode_vertex());
        for name in iter_adjacent(txn, channel, v.inode_vertex(), flag0, flag1) {
            if !name.flag.contains(EdgeFlags::PARENT) {
                continue;
            }
            debug!("oldest_path, name = {:?}", name);
            let age = txn
                .get_changeset(&channel.changes, name.dest.change, None)
                .unwrap();

            let name_dest = find_block_end(txn, &channel, name.dest).unwrap();
            debug!("name_dest = {:?}", name_dest);
            if let Some(next) = iter_adjacent(txn, channel, name_dest, flag0, flag1)
                .filter(|e| e.flag.contains(EdgeFlags::PARENT | EdgeFlags::FOLDER))
                .next()
            {
                debug!("oldest_path, next = {:?}", next);
                if !next.flag.contains(EdgeFlags::DELETED) {
                    alive = true;
                } else if alive {
                    break;
                } else {
                    all_alive = false
                }
                if let Some((_, p_age, _)) = next_v {
                    if (age > p_age) ^ youngest {
                        continue;
                    }
                }
                next_v = Some((name_dest, age, next.dest));
            }
        }
        let (name, _, next) = next_v.unwrap();
        if alive {
            name_buf.clear();
            debug!("getting contents {:?}", name);
            changes.get_contents(|h| txn.get_external(h), name, &mut name_buf)?;
            path.push(std::str::from_utf8(&name_buf[2..]).unwrap().to_string());
        }
        debug!("next = {:?}", next);
        v = next;
    }
    path.reverse();
    Ok((path.join("/"), all_alive))
}