libpijul 0.12.0

use backend::*;
use graph;
use patch::*;
use {Error, Result};

use diff;
use rand;
use std;
use std::collections::HashSet;
use std::fs::metadata;
use std::io::BufRead;
use std::io::Read;
#[cfg(not(windows))]
use std::os::unix::fs::PermissionsExt;
use std::path::{Path, PathBuf};
use std::rc::Rc;

use fs_representation::{RepoRoot, RepoPath};

#[cfg(not(windows))]
fn permissions(attr: &std::fs::Metadata) -> Option<usize> {
    Some(attr.permissions().mode() as usize)
}
#[cfg(windows)]
fn permissions(_: &std::fs::Metadata) -> Option<usize> {
    None
}

fn file_metadata(path: &Path) -> Result<FileMetadata> {
    let attr = metadata(&path)?;
    let permissions = permissions(&attr).unwrap_or(0o755);
    debug!("permissions = {:?}", permissions);
    Ok(FileMetadata::new(permissions & 0o777, attr.is_dir()))
}

impl<U: Transaction, R> GenericTxn<U, R> {
    pub fn globalize_change(
        &self,
        change: Change<ChangeContext<PatchId>>,
    ) -> Change<ChangeContext<Hash>> {
        match change {
            Change::NewNodes {
                up_context,
                down_context,
                flag,
                line_num,
                nodes,
                inode,
            } => Change::NewNodes {
                up_context: up_context
                    .iter()
                    .map(|&k| self.external_key_opt(k))
                    .collect(),
                down_context: down_context
                    .iter()
                    .map(|&k| self.external_key_opt(k))
                    .collect(),
                flag,
                line_num,
                nodes,
                inode,
            },
            Change::NewEdges {
                previous,
                flag,
                edges,
                inode,
            } => Change::NewEdges {
                previous,
                flag,
                edges,
                inode,
            },
        }
    }
    pub fn globalize_record(
        &self,
        change: Record<ChangeContext<PatchId>>,
    ) -> Record<ChangeContext<Hash>> {
        match change {
            Record::FileMove { new_name, del, add } => Record::FileMove {
                new_name,
                del: self.globalize_change(del),
                add: self.globalize_change(add),
            },
            Record::FileDel {
                name,
                del,
                contents,
            } => Record::FileDel {
                name,
                del: self.globalize_change(del),
                contents: contents.map(|del| self.globalize_change(del)),
            },
            Record::FileAdd {
                name,
                add,
                contents,
            } => Record::FileAdd {
                name,
                add: self.globalize_change(add),
                contents: contents.map(|add| self.globalize_change(add)),
            },
            Record::Change {
                file,
                change,
                replacement,
                old_line,
                new_line,
            } => Record::Change {
                file,
                change: self.globalize_change(change),
                replacement: replacement.map(|x| self.globalize_change(x)),
                old_line,
                new_line,
            },
        }
    }
}

pub struct RecordState {
    line_num: LineId,
    updatables: HashSet<InodeUpdate>,
    actions: Vec<Record<ChangeContext<PatchId>>>,
    redundant: Vec<(Key<PatchId>, Edge)>,
}

/// An account of the files that have been added, moved or deleted, as
/// returned by record, and used by apply (when applying a patch
/// created locally) to update the trees and inodes databases.
#[derive(Debug, Hash, PartialEq, Eq)]
pub enum InodeUpdate {
    Add {
        /// `LineId` in the new patch.
        line: LineId,
        /// `FileMetadata` in the updated file.
        meta: FileMetadata,
        /// `Inode` added by this file addition.
        inode: Inode,
    },
    Moved {
        /// `Inode` of the moved file.
        inode: Inode,
        metadata: FileMetadata,
    },
    Deleted {
        /// `Inode` of the deleted file.
        inode: Inode,
    },
}

#[derive(Debug)]
pub enum WorkingFileStatus {
    Moved {
        from: FileMetadata,
        to: FileMetadata,
    },
    Deleted,
    Ok,
    Zombie,
}

pub(crate) fn is_text(x: &[u8]) -> bool {
    x.iter().take(8000).all(|&c| c != 0)
}

impl<'env, R: rand::Rng> MutTxn<'env, R> {
    /// Create appropriate NewNodes for adding a file.
    fn record_file_addition(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        st: &mut RecordState,
        current_inode: Inode,
        parent_node: Key<Option<PatchId>>,
        realpath: &mut RepoPath<std::path::PathBuf>,
        basename: &str,
    ) -> Result<Option<LineId>> {
        let name_line_num = st.line_num.clone();
        let blank_line_num = st.line_num + 1;
        st.line_num += 2;

        debug!("metadata for {:?}", realpath);
        let path = &repo_root.absolutize(realpath);
        let meta = match file_metadata(&path) {
            Ok(metadata) => metadata,
            Err(e) => return Err(e),
        };
        debug!("meta = {:?}", meta.is_dir());

        let mut name = Vec::with_capacity(basename.len() + 2);
        name.write_metadata(meta).unwrap(); // 2 bytes.
        name.extend(basename.as_bytes());

        let mut nodes = Vec::new();

        st.updatables.insert(InodeUpdate::Add {
            line: blank_line_num.clone(),
            meta: meta,
            inode: current_inode.clone(),
        });
        let up_context_ext = Key {
            patch: if parent_node.line.is_root() {
                Some(Hash::None)
            } else if let Some(patch_id) = parent_node.patch {
                Some(self.external_hash(patch_id).to_owned())
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        let up_context = Key {
            patch: if parent_node.line.is_root() {
                Some(ROOT_PATCH_ID)
            } else if let Some(patch_id) = parent_node.patch {
                Some(patch_id)
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        st.actions.push(Record::FileAdd {
            name: realpath.to_owned(),
            add: Change::NewNodes {
                up_context: vec![up_context],
                line_num: name_line_num,
                down_context: vec![],
                nodes: vec![name, vec![]],
                flag: EdgeFlags::FOLDER_EDGE,
                inode: up_context_ext.clone(),
            },
            contents: None,
        });
        // Reading the file
        if !meta.is_dir() {
            nodes.clear();

            let mut node = Vec::new();
            {
                let mut f = std::fs::File::open(path.as_path())?;
                f.read_to_end(&mut node)?;
            }

            let up_context = Key {
                patch: None,
                line: blank_line_num.clone(),
            };
            let up_context_ext = Key {
                patch: None,
                line: blank_line_num.clone(),
            };
            if is_text(&node) {
                let mut line = Vec::new();
                let mut f = &node[..];
                loop {
                    match f.read_until('\n' as u8, &mut line) {
                        Ok(l) => {
                            if l > 0 {
                                nodes.push(line.clone());
                                line.clear()
                            } else {
                                break;
                            }
                        }
                        Err(_) => break,
                    }
                }
                let len = nodes.len();
                if !nodes.is_empty() {
                    if let Some(Record::FileAdd {
                        ref mut contents, ..
                    }) = st.actions.last_mut()
                    {
                        *contents = Some(Change::NewNodes {
                            up_context: vec![up_context],
                            line_num: st.line_num,
                            down_context: vec![],
                            nodes: nodes,
                            flag: EdgeFlags::empty(),
                            inode: up_context_ext,
                        });
                    }
                }
                st.line_num += len;
            } else if let Some(Record::FileAdd {
                ref mut contents, ..
            }) = st.actions.last_mut()
            {
                *contents = Some(Change::NewNodes {
                    up_context: vec![up_context],
                    line_num: st.line_num,
                    down_context: vec![],
                    nodes: vec![node],
                    flag: EdgeFlags::empty(),
                    inode: up_context_ext,
                });
                st.line_num += 1;
            }
            Ok(None)
        } else {
            Ok(Some(blank_line_num))
        }
    }

    /// Diff for binary files, doesn't bother splitting the file in
    /// lines. This is wasteful, but doesn't break the format, and
    /// doesn't create conflicts inside binary files.
    fn diff_with_binary(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        algorithm: diff::Algorithm,
        inode: Key<Option<Hash>>,
        branch: &Branch,
        st: &mut RecordState,
        ret: &mut graph::Graph,
        path: Rc<RepoPath<PathBuf>>,
    ) -> Result<()> {
        let mut lines_b = Vec::new();
        {
            debug!("opening file for diff: {:?}", path);
            let mut f = std::fs::File::open(repo_root.absolutize(&path))?;
            f.read_to_end(&mut lines_b)?;
        }

        self.diff(
            algorithm,
            inode,
            branch,
            path,
            &mut st.line_num,
            &mut st.actions,
            &mut st.redundant,
            ret,
            &lines_b,
        )
    }

    fn record_moved_file(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        diff_algorithm: diff::Algorithm,
        branch: &Branch,
        realpath: &mut RepoPath<std::path::PathBuf>,
        st: &mut RecordState,
        parent_node: Key<Option<PatchId>>,
        current_node: Key<PatchId>,
        basename: &str,
        new_meta: FileMetadata,
        old_meta: FileMetadata,
    ) -> Result<()> {
        debug!("record_moved_file: parent_node={:?}", parent_node);
        // Delete all former names.
        let mut edges = Vec::new();
        // Now take all grandparents of l2, delete them.

        let mut name = Vec::with_capacity(basename.len() + 2);
        name.write_metadata(new_meta).unwrap();
        name.extend(basename.as_bytes());
        for parent in self.iter_parents(branch, current_node, EdgeFlags::FOLDER_EDGE) {
            debug!("iter_parents: {:?}", parent);
            let previous_name: &[u8] = match self.get_contents(parent.dest) {
                None => &[],
                Some(n) => n.as_slice(),
            };
            let name_changed =
                (&previous_name[2..] != &name[2..]) || (new_meta != old_meta && cfg!(not(windows)));

            for grandparent in self.iter_parents(branch, parent.dest, EdgeFlags::FOLDER_EDGE) {
                debug!("iter_parents: grandparent = {:?}", grandparent);
                let grandparent_changed = if let Some(ref parent_node_patch) = parent_node.patch {
                    *parent_node_patch != grandparent.dest.patch
                        || parent_node.line != grandparent.dest.line
                } else {
                    true
                };
                if grandparent_changed || name_changed {
                    edges.push(NewEdge {
                        from: Key {
                            line: parent.dest.line.clone(),
                            patch: Some(self.external_hash(parent.dest.patch).to_owned()),
                        },
                        to: Key {
                            line: grandparent.dest.line.clone(),
                            patch: Some(self.external_hash(grandparent.dest.patch).to_owned()),
                        },
                        introduced_by: Some(
                            self.external_hash(grandparent.introduced_by).to_owned(),
                        ),
                    })
                }
            }
        }
        debug!("edges:{:?}", edges);
        let up_context_ext = Key {
            patch: if parent_node.line.is_root() {
                Some(Hash::None)
            } else if let Some(parent_patch) = parent_node.patch {
                Some(self.external_hash(parent_patch).to_owned())
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        let up_context = Key {
            patch: if parent_node.line.is_root() {
                Some(ROOT_PATCH_ID)
            } else if let Some(parent_patch) = parent_node.patch {
                Some(parent_patch)
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        if !edges.is_empty() {
            // If this file's name or meta info has changed.
            st.actions.push(Record::FileMove {
                new_name: realpath.to_owned(),
                del: Change::NewEdges {
                    edges: edges,
                    previous: EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE,
                    flag: EdgeFlags::DELETED_EDGE | EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE,
                    inode: up_context_ext.clone(),
                },
                add: Change::NewNodes {
                    up_context: vec![up_context],
                    line_num: st.line_num,
                    down_context: vec![Key {
                        patch: Some(current_node.patch),
                        line: current_node.line.clone(),
                    }],
                    nodes: vec![name],
                    flag: EdgeFlags::FOLDER_EDGE,
                    inode: up_context_ext.clone(),
                },
            });
            st.line_num += 1;
        }
        if !old_meta.is_dir() {
            info!("retrieving");
            let mut ret = self.retrieve(branch, current_node);
            debug!("diff");
            let patch_ext = self.get_external(current_node.patch).unwrap();
            self.diff_with_binary(
                repo_root,
                diff_algorithm,
                Key {
                    patch: Some(patch_ext.to_owned()),
                    line: current_node.line,
                },
                branch,
                st,
                &mut ret,
                Rc::new(realpath.clone()),
            )?;
        };
        Ok(())
    }

    fn record_deleted_file(
        &self,
        st: &mut RecordState,
        branch: &Branch,
        realpath: &RepoPath<impl AsRef<Path>>,
        current_node: Key<PatchId>,
    ) -> Result<()> {
        debug!("record_deleted_file");
        let mut edges = Vec::new();
        let mut previous = EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE;
        // Now take all grandparents of the current node, delete them.
        for parent in self.iter_parents(branch, current_node, EdgeFlags::FOLDER_EDGE) {
            for grandparent in self.iter_parents(branch, parent.dest, EdgeFlags::FOLDER_EDGE) {
                edges.push(NewEdge {
                    from: self.external_key(&parent.dest).unwrap(),
                    to: self.external_key(&grandparent.dest).unwrap(),
                    introduced_by: Some(self.external_hash(grandparent.introduced_by).to_owned()),
                });
                previous = grandparent.flag;
            }
        }
        // If the file is a directory, delete recursively
        let mut file_edges = vec![];
        {
            debug!("del={:?}", current_node);
            let ret = self.retrieve(branch, current_node);
            debug!("ret {:?}", ret);
            for l in ret.lines.iter() {
                if l.key != ROOT_KEY {
                    let ext_key = self.external_key(&l.key).unwrap();
                    debug!("ext_key={:?}", ext_key);
                    for v in self.iter_parents(branch, l.key, EdgeFlags::empty()) {
                        debug!("v={:?}", v);
                        file_edges.push(NewEdge {
                            from: ext_key.clone(),
                            to: self.external_key(&v.dest).unwrap(),
                            introduced_by: Some(self.external_hash(v.introduced_by).to_owned()),
                        });
                        if let Some(inode) = self.get_revinodes(v.dest) {
                            st.updatables.insert(InodeUpdate::Deleted {
                                inode: inode.to_owned(),
                            });
                        }
                    }
                    for v in self.iter_parents(branch, l.key, EdgeFlags::FOLDER_EDGE) {
                        debug!("v={:?}", v);
                        edges.push(NewEdge {
                            from: ext_key.clone(),
                            to: self.external_key(&v.dest).unwrap(),
                            introduced_by: Some(self.external_hash(v.introduced_by).to_owned()),
                        });
                    }
                }
            }
        }

        if !edges.is_empty() {
            st.actions.push(Record::FileDel {
                name: realpath.to_owned(),
                del: Change::NewEdges {
                    edges: edges,
                    previous,
                    flag: EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                    inode: self.external_key(&current_node).unwrap(),
                },
                contents: if file_edges.is_empty() {
                    None
                } else {
                    Some(Change::NewEdges {
                        edges: file_edges,
                        previous: EdgeFlags::PARENT_EDGE,
                        flag: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                        inode: self.external_key(&current_node).unwrap(),
                    })
                },
            });
        }
        Ok(())
    }

    fn record_children(
        &self,
        repo_root:  &RepoRoot<impl AsRef<Path>>,
        diff_algorithm: diff::Algorithm,
        branch: &Branch,
        st: &mut RecordState,
        path: &mut RepoPath<std::path::PathBuf>,
        current_node: Key<Option<PatchId>>,
        current_inode: Inode,
        obsolete_inodes: &mut Vec<Inode>,
    ) -> Result<()> {
        debug!("children of current_inode {}", current_inode.to_hex());
        let file_id = OwnedFileId {
            parent_inode: current_inode.clone(),
            basename: SmallString::from_str(""),
        };
        debug!("iterating tree, starting from {:?}", file_id.as_file_id());
        for (k, v) in self
            .iter_tree(Some((&file_id.as_file_id(), None)))
            .take_while(|&(ref k, _)| k.parent_inode == current_inode)
        {
            debug!("calling record_all recursively, {}", line!());

            if k.basename.len() > 0 {
                // If this is an actual file and not just the "."
                self.record_inode(
                    repo_root,
                    diff_algorithm,
                    branch,
                    st,
                    current_node.clone(), // parent
                    v,                    // current_inode
                    path,
                    obsolete_inodes,
                    k.basename.as_str(),
                )?
            }
        }
        Ok(())
    }

    /// If `inode` is a file known to the current branch, return
    /// whether it's been moved, deleted, or its "status" (including
    /// permissions) has been changed.
    ///
    /// Returns `None` if `inode` is not known to the current branch.
    fn inode_status(&self,
                    repo_root: &RepoRoot<impl AsRef<Path>>,
                    inode: Inode,
                    path: &RepoPath<impl AsRef<Path>>)
                    -> (Option<(WorkingFileStatus, FileHeader)>) {
        match self.get_inodes(inode) {
            Some(file_header) => {
                let old_meta = file_header.metadata;
                let new_meta = file_metadata(&repo_root.absolutize(path)).ok();
                
                debug!("current_node={:?}", file_header);
                debug!("old_attr={:?},int_attr={:?}", old_meta, new_meta);

                let status = match (new_meta, file_header.status) {
                    (Some(new_meta), FileStatus::Moved) => WorkingFileStatus::Moved {
                        from: old_meta,
                        to: new_meta,
                    },
                    (Some(new_meta), _) if old_meta != new_meta => WorkingFileStatus::Moved {
                        from: old_meta,
                        to: new_meta,
                    },
                    (None, _) | (_, FileStatus::Deleted) => WorkingFileStatus::Deleted,
                    (Some(_), FileStatus::Ok) => WorkingFileStatus::Ok,
                    (Some(_), FileStatus::Zombie) => WorkingFileStatus::Zombie,
                };
                Some((status, file_header.clone()))
            }
            None => None,
        }
    }

    fn record_inode(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        diff_algorithm: diff::Algorithm,
        branch: &Branch,
        st: &mut RecordState,
        parent_node: Key<Option<PatchId>>,
        current_inode: Inode,
        realpath: &mut RepoPath<std::path::PathBuf>,
        obsolete_inodes: &mut Vec<Inode>,
        basename: &str,
    ) -> Result<()> {
        realpath.push(basename);
        debug!("realpath: {:?}", realpath);
        debug!("inode: {:?}", current_inode);
        debug!("header: {:?}", self.get_inodes(current_inode));
        let status_header = self.inode_status(repo_root, current_inode, realpath);
        debug!("status_header: {:?}", status_header);
        let mut current_key = match &status_header {
            &Some((_, ref file_header)) => Some(Key {
                patch: Some(file_header.key.patch.clone()),
                line: file_header.key.line.clone(),
            }),
            &None => None,
        };

        match status_header {
            Some((
                WorkingFileStatus::Moved {
                    from: old_meta,
                    to: new_meta,
                },
                file_header,
            )) => {
                st.updatables.insert(InodeUpdate::Moved {
                    inode: current_inode.clone(),
                    metadata: new_meta,
                });
                self.record_moved_file(
                    repo_root,
                    diff_algorithm,
                    branch,
                    realpath,
                    st,
                    parent_node,
                    file_header.key,
                    basename,
                    new_meta,
                    old_meta,
                )?
            }
            Some((WorkingFileStatus::Deleted, file_header)) => {
                st.updatables.insert(InodeUpdate::Deleted {
                    inode: current_inode.clone(),
                });
                self.record_deleted_file(st, branch, realpath, file_header.key)?;
                // If we are deleting a directory, don't recurse,
                // because record_deleted_file already did it.
                realpath.pop();
                return Ok(());
            }
            Some((WorkingFileStatus::Ok, file_header)) => {
                if !file_header.metadata.is_dir() {
                    let mut ret = self.retrieve(branch, file_header.key);
                    debug!("now calling diff {:?}", file_header.key);
                    let inode = Key {
                        patch: Some(self.external_hash(file_header.key.patch).to_owned()),
                        line: file_header.key.line,
                    };
                    self.confirm_path(st, branch, realpath, file_header.key)?;
                    self.diff_with_binary(
                        repo_root,
                        diff_algorithm,
                        inode,
                        branch,
                        st,
                        &mut ret,
                        Rc::new(realpath.clone()),
                    )?;
                } else {
                    // Confirm
                    self.confirm_path(st, branch, &realpath, file_header.key)?;
                }
            }
            Some((WorkingFileStatus::Zombie, _)) => {
                // This file is a zombie, but the user has not
                // specified anything to do with this file, so leave
                // it alone.
            }
            None => {
                if let Ok(new_key) =
                    self.record_file_addition(repo_root, st, current_inode, parent_node,
                                              realpath, basename)
                {
                    current_key = new_key.map(|next| Key {
                        patch: None,
                        line: next,
                    })
                } else {
                    obsolete_inodes.push(current_inode)
                }
            }
        }

        let current_key = current_key;
        debug!("current_node={:?}", current_key);
        if let Some(current_node) = current_key {
            self.record_children(
                repo_root,
                diff_algorithm,
                branch,
                st,
                realpath,
                current_node,
                current_inode,
                obsolete_inodes,
            )?;
        };
        realpath.pop();
        Ok(())
    }

    fn external_newedge(
        &self,
        from: Key<PatchId>,
        to: Key<PatchId>,
        introduced_by: PatchId,
    ) -> NewEdge {
        NewEdge {
            from: Key {
                patch: Some(self.external_hash(from.patch).to_owned()),
                line: from.line,
            },
            to: Key {
                patch: Some(self.external_hash(to.patch).to_owned()),
                line: to.line,
            },
            introduced_by: Some(self.external_hash(introduced_by).to_owned()),
        }
    }

    /// `key` must be a non-root inode key.
    fn confirm_path(
        &self,
        st: &mut RecordState,
        branch: &Branch,
        realpath: &RepoPath<impl AsRef<Path>>,
        key: Key<PatchId>,
    ) -> Result<()> {
        debug!("confirm_path");
        let f = EdgeFlags::PARENT_EDGE | EdgeFlags::FOLDER_EDGE | EdgeFlags::DELETED_EDGE;
        // Are there deleted parent edges?
        let mut edges = Vec::new();
        for v in self.iter_adjacent(branch, key, f, f) {
            debug!("confirm {:?}", v.dest);
            edges.push(self.external_newedge(key, v.dest, v.introduced_by));
            for v_ in self.iter_adjacent(branch, v.dest, f, f) {
                debug!("confirm 2 {:?}", v_.dest);
                edges.push(self.external_newedge(v.dest, v_.dest, v_.introduced_by));
            }
        }

        if !edges.is_empty() {
            let inode = Key {
                patch: Some(self.external_hash(key.patch).to_owned()),
                line: key.line.clone(),
            };
            st.actions.push(Record::FileAdd {
                name: realpath.to_owned(),
                add: Change::NewEdges {
                    edges,
                    previous: EdgeFlags::FOLDER_EDGE
                        | EdgeFlags::PARENT_EDGE
                        | EdgeFlags::DELETED_EDGE,
                    flag: EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE,
                    inode,
                },
                contents: None,
            });
        }
        debug!("/confirm_path");

        Ok(())
    }
}

impl RecordState {
    pub fn new() -> Self {
        RecordState {
            line_num: LineId::new() + 1,
            actions: Vec::new(),
            updatables: HashSet::new(),
            redundant: Vec::new(),
        }
    }

    pub fn finish(self) -> (Vec<Record<ChangeContext<PatchId>>>, HashSet<InodeUpdate>) {
        (self.actions, self.updatables)
    }
}

impl<'env, T: rand::Rng> MutTxn<'env, T> {
    pub fn record(
        &mut self,
        diff_algorithm: diff::Algorithm,
        state: &mut RecordState,
        branch: &Branch,
        working_copy: &RepoRoot<impl AsRef<Path>>,
        prefix: &RepoPath<impl AsRef<Path>>,
    ) -> Result<()> {
        let mut obsolete_inodes = Vec::new();

        match prefix.split() {
            Some ((parent_path, basename)) =>
            {
                let inode = self.find_inode(prefix)?;
                // Key needs to be the parent's node.
                let key: Key<PatchId> = {
                    // find this inode's parent.
                    if let Some(parent) = self.get_revtree(inode) {
                        if parent.parent_inode.is_root() {
                            ROOT_KEY
                        } else if let Some(key) = self.get_inodes(parent.parent_inode) {
                            key.key
                        } else {
                            return Err(Error::FileNotInRepo(prefix.to_path_buf()));
                        }
                    } else {
                        return Err(Error::FileNotInRepo(prefix.to_path_buf()));
                    }
                };
                let key = Key {
                    patch: Some(key.patch),
                    line: key.line,
                };
                self.record_inode(
                    working_copy,
                    diff_algorithm,
                    &branch,
                    state,
                    key,
                    inode,
                    &mut parent_path.to_owned(),
                    &mut obsolete_inodes,
                    &basename.to_str().unwrap(),
                )?
            },
            None => {
                let mut realpath = RepoPath(PathBuf::from(""));
                let key = Key {
                    patch: None,
                    line: LineId::new(),
                };
                self.record_children(
                    working_copy,
                    diff_algorithm,
                    &branch,
                    state,
                    &mut realpath,
                    key,
                    ROOT_INODE,
                    &mut obsolete_inodes,
                )?
                // self.record_root(&branch, &mut st, &mut realpath)?;
            }
        };
        debug!("record done, {} changes", state.actions.len());
        debug!("changes: {:?}", state.actions);

        // try!(self.remove_redundant_edges(&mut branch, &mut st.redundant));
        debug!("remove_redundant_edges done");
        for inode in obsolete_inodes {
            self.rec_delete(inode)?;
        }
        Ok(())
    }
}