use crate::change::*;
use crate::small_string::*;
use std::cell::RefCell;
use std::collections::{HashMap, HashSet};
use std::io::Write;
use std::rc::Rc;

mod change_id;
pub use change_id::*;
mod vertex;
pub use vertex::*;
mod edge;
pub use edge::*;
mod hash;
pub use hash::*;
mod inode;
pub use inode::*;
mod inode_metadata;
pub use inode_metadata::*;
mod path_id;
pub use path_id::*;
mod merkle;
pub use merkle::*;
#[cfg(feature = "dump")]
pub mod channel_dump;

pub trait Base32: Sized {
    fn to_base32(&self) -> String;
    fn from_base32(b: &[u8]) -> Option<Self>;
}

pub mod sanakirja;

pub type ApplyTimestamp = u64;

pub struct ChannelRef<T: ChannelTxnT> {
    pub(crate) r: Rc<RefCell<T::Channel>>,
}

impl<T: ChannelTxnT> Clone for ChannelRef<T> {
    fn clone(&self) -> Self {
        ChannelRef { r: self.r.clone() }
    }
}

impl<T: TxnT> RemoteRef<T> {
    pub fn name(&self) -> &str {
        self.name.as_str()
    }
}

impl<T: ChannelTxnT> ChannelRef<T> {
    pub fn borrow(&self) -> std::cell::Ref<T::Channel> {
        self.r.borrow()
    }
    pub fn borrow_mut(&mut self) -> std::cell::RefMut<T::Channel> {
        self.r.borrow_mut()
    }
}

pub struct Remote<T: TxnT> {
    pub remote: T::Remote,
    pub rev: T::Revremote,
    pub states: T::Remotestates,
}

pub struct RemoteRef<T: TxnT> {
    db: Rc<RefCell<Remote<T>>>,
    name: SmallString,
}

impl<T: TxnT> Clone for RemoteRef<T> {
    fn clone(&self) -> Self {
        RemoteRef {
            db: self.db.clone(),
            name: self.name.clone(),
        }
    }
}

impl<T: TxnT> RemoteRef<T> {
    pub fn borrow(&self) -> std::cell::Ref<Remote<T>> {
        self.db.borrow()
    }
    pub fn borrow_mut(&mut self) -> std::cell::RefMut<Remote<T>> {
        self.db.borrow_mut()
    }
}

#[derive(Debug, Error)]
pub enum HashPrefixError<T: std::error::Error + 'static> {
    #[error("Failed to parse hash prefix: {0}")]
    Parse(String),
    #[error("Ambiguous hash prefix: {0}")]
    Ambiguous(String),
    #[error("Change not found: {0}")]
    NotFound(String),
    #[error(transparent)]
    Txn(T),
}

#[derive(Debug, Error)]
pub enum ForkError<T: std::error::Error + 'static> {
    #[error("Channel name already exists: {0}")]
    ChannelNameExists(String),
    #[error(transparent)]
    Txn(T),
}

#[derive(Debug, Error)]
#[error(transparent)]
pub struct TxnErr<E: std::error::Error + 'static>(pub E);

pub trait GraphTxnT: Sized {
    type GraphError: std::error::Error + Send + Sync + 'static;
    table!(graph);
    get!(graph, Vertex<ChangeId>, Edge, GraphError);
    /// Returns the external hash of an internal change identifier, if
    /// the change is known.
    fn get_external(&self, p: ChangeId) -> Result<Option<Hash>, TxnErr<Self::GraphError>>;

    /// Returns the internal change identifier of change with external
    /// hash `hash`, if the change is known.
    fn get_internal(&self, p: Hash) -> Result<Option<ChangeId>, TxnErr<Self::GraphError>>;

    type Adj;
    fn init_adj(
        &self,
        g: &Self::Graph,
        v: Vertex<ChangeId>,
        dest: Position<ChangeId>,
        min: EdgeFlags,
        max: EdgeFlags,
    ) -> Result<Self::Adj, TxnErr<Self::GraphError>>;
    fn next_adj(
        &self,
        g: &Self::Graph,
        a: &mut Self::Adj,
    ) -> Option<Result<Edge, TxnErr<Self::GraphError>>>;

    fn find_block(
        &self,
        graph: &Self::Graph,
        p: Position<ChangeId>,
    ) -> Result<Vertex<ChangeId>, BlockError<Self::GraphError>>;

    fn find_block_end(
        &self,
        graph: &Self::Graph,
        p: Position<ChangeId>,
    ) -> Result<Vertex<ChangeId>, BlockError<Self::GraphError>>;
}

pub trait ChannelTxnT: GraphTxnT {
    type Channel;

    fn name(channel: &Self::Channel) -> &str;
    fn graph(channel: &Self::Channel) -> &Self::Graph;
    fn apply_counter(channel: &Self::Channel) -> u64;
    fn last_modified(channel: &Self::Channel) -> u64;
    fn changes(channel: &Self::Channel) -> &Self::Changeset;
    fn rev_changes(channel: &Self::Channel) -> &Self::RevChangeset;

    type Changeset;
    type RevChangeset;
    fn get_changeset(
        &self,
        channel: &Self::Changeset,
        c: ChangeId,
    ) -> Result<Option<u64>, TxnErr<Self::GraphError>>;
    fn get_revchangeset(
        &self,
        channel: &Self::RevChangeset,
        c: u64,
    ) -> Result<Option<(ChangeId, Merkle)>, TxnErr<Self::GraphError>>;

    type ChangesetCursor;
    fn cursor_changeset<'txn>(
        &'txn self,
        channel: &Self::Changeset,
        pos: Option<ChangeId>,
    ) -> Result<
        crate::pristine::Cursor<Self, &'txn Self, Self::ChangesetCursor, ChangeId, u64>,
        TxnErr<Self::GraphError>,
    >;
    fn cursor_changeset_next(
        &self,
        cursor: &mut Self::ChangesetCursor,
    ) -> Result<Option<(ChangeId, u64)>, TxnErr<Self::GraphError>>;

    fn cursor_changeset_prev(
        &self,
        cursor: &mut Self::ChangesetCursor,
    ) -> Result<Option<(ChangeId, u64)>, TxnErr<Self::GraphError>>;

    type RevchangesetCursor;
    fn cursor_revchangeset_ref<RT: std::ops::Deref<Target = Self>>(
        txn: RT,
        channel: &Self::RevChangeset,
        pos: Option<u64>,
    ) -> Result<
        Cursor<Self, RT, Self::RevchangesetCursor, u64, (ChangeId, Merkle)>,
        TxnErr<Self::GraphError>,
    >;
    fn rev_cursor_revchangeset<'txn>(
        &'txn self,
        channel: &Self::RevChangeset,
        pos: Option<u64>,
    ) -> Result<
        RevCursor<Self, &'txn Self, Self::RevchangesetCursor, u64, (ChangeId, Merkle)>,
        TxnErr<Self::GraphError>,
    >;
    fn cursor_revchangeset_next(
        &self,
        cursor: &mut Self::RevchangesetCursor,
    ) -> Result<Option<(u64, (ChangeId, Merkle))>, TxnErr<Self::GraphError>>;

    fn cursor_revchangeset_prev(
        &self,
        cursor: &mut Self::RevchangesetCursor,
    ) -> Result<Option<(u64, (ChangeId, Merkle))>, TxnErr<Self::GraphError>>;

    fn channel_has_state(
        &self,
        channel: &Self::Channel,
        hash: Merkle,
    ) -> Result<Option<u64>, TxnErr<Self::GraphError>>;
}

pub trait GraphIter: GraphTxnT {
    type GraphCursor;
    fn iter_graph(&self, g: &Self::Graph) -> Result<Self::GraphCursor, TxnErr<Self::GraphError>>;
    fn next_graph(
        &self,
        g: &Self::Graph,
        a: &mut Self::GraphCursor,
    ) -> Option<Result<(Vertex<ChangeId>, Edge), TxnErr<Self::GraphError>>>;
}

#[derive(Debug, Error)]
pub enum BlockError<T: std::error::Error + 'static> {
    #[error(transparent)]
    Txn(T),
    #[error("Block error: {:?}", block)]
    Block { block: Position<ChangeId> },
}

impl<T: std::error::Error + 'static> std::convert::From<TxnErr<T>> for BlockError<T> {
    fn from(e: TxnErr<T>) -> Self {
        BlockError::Txn(e.0)
    }
}

pub trait DepsTxnT: Sized {
    type DepsError: std::error::Error + Send + Sync + 'static;
    table!(revdep);
    table!(dep);
    table_get!(dep, ChangeId, ChangeId, DepsError);
    cursor_ref!(dep, ChangeId, ChangeId, DepsError);
    table_get!(revdep, ChangeId, ChangeId, DepsError);
    fn iter_revdep(
        &self,
        p: ChangeId,
    ) -> Result<Cursor<Self, &Self, Self::DepCursor, ChangeId, ChangeId>, TxnErr<Self::DepsError>>;
    fn iter_dep(
        &self,
        p: ChangeId,
    ) -> Result<Cursor<Self, &Self, Self::DepCursor, ChangeId, ChangeId>, TxnErr<Self::DepsError>>;
    fn iter_dep_ref<RT: std::ops::Deref<Target = Self> + Clone>(
        txn: RT,
        p: ChangeId,
    ) -> Result<Cursor<Self, RT, Self::DepCursor, ChangeId, ChangeId>, TxnErr<Self::DepsError>>;
    fn iter_touched(
        &self,
        p: Position<ChangeId>,
    ) -> Result<
        Cursor<Self, &Self, Self::Touched_filesCursor, Position<ChangeId>, ChangeId>,
        TxnErr<Self::DepsError>,
    >;
    fn iter_rev_touched(
        &self,
        p: ChangeId,
    ) -> Result<
        Cursor<Self, &Self, Self::Rev_touched_filesCursor, ChangeId, Position<ChangeId>>,
        TxnErr<Self::DepsError>,
    >;
    table!(touched_files);
    table!(rev_touched_files);
    table_get!(touched_files, Position<ChangeId>, ChangeId, DepsError);
    table_get!(rev_touched_files, ChangeId, Position<ChangeId>, DepsError);
    iter!(touched_files, Position<ChangeId>, ChangeId, DepsError);
    iter!(rev_touched_files, ChangeId, Position<ChangeId>, DepsError);
}

pub trait TreeTxnT: Sized {
    type TreeError: std::error::Error + Send + Sync + 'static;
    table!(tree);
    table_get!(tree, PathId, Inode, TreeError);
    iter!(tree, OwnedPathId, Inode, TreeError);

    table!(revtree);
    table_get!(revtree, Inode, PathId, TreeError);
    iter!(revtree, Inode, OwnedPathId, TreeError);

    table!(inodes);
    table!(revinodes);
    table_get!(inodes, Inode, Position<ChangeId>, TreeError);
    table_get!(revinodes, Position<ChangeId>, Inode, TreeError);

    table!(partials);
    cursor!(partials, SmallString, Position<ChangeId>, TreeError);
    cursor!(inodes, Inode, Position<ChangeId>, TreeError);
    fn iter_inodes(
        &self,
    ) -> Result<
        Cursor<Self, &Self, Self::InodesCursor, Inode, Position<ChangeId>>,
        TxnErr<Self::TreeError>,
    >;

    #[cfg(debug_assertions)]
    cursor!(revinodes, Position<ChangeId>, Inode, TreeError);
    #[cfg(debug_assertions)]
    fn iter_revinodes(
        &self,
    ) -> Result<
        Cursor<Self, &Self, Self::RevinodesCursor, Position<ChangeId>, Inode>,
        TxnErr<Self::TreeError>,
    >;
    fn iter_partials<'txn>(
        &'txn self,
        channel: &str,
    ) -> Result<
        Cursor<Self, &'txn Self, Self::PartialsCursor, SmallString, Position<ChangeId>>,
        TxnErr<Self::TreeError>,
    >;
}

/// The trait of immutable transactions.
pub trait TxnT:
    GraphTxnT
    + ChannelTxnT
    + DepsTxnT<DepsError = <Self as GraphTxnT>::GraphError>
    + TreeTxnT<TreeError = <Self as GraphTxnT>::GraphError>
{
    table!(channels);
    cursor!(channels, SmallString, (u64, u64, u64, u64, u64, u64));

    fn hash_from_prefix(
        &self,
        prefix: &str,
    ) -> Result<(Hash, ChangeId), HashPrefixError<Self::GraphError>>;
    fn hash_from_prefix_remote(
        &self,
        remote: &RemoteRef<Self>,
        prefix: &str,
    ) -> Result<Hash, HashPrefixError<Self::GraphError>>;

    fn load_channel(
        &self,
        name: &str,
    ) -> Result<Option<ChannelRef<Self>>, TxnErr<Self::GraphError>>;

    fn load_remote(&self, name: &str) -> Result<Option<RemoteRef<Self>>, TxnErr<Self::GraphError>>;

    /// Iterate a function over all channels. The loop stops the first
    /// time `f` returns `false`.
    fn iter_channels<'txn>(
        &'txn self,
        start: &str,
    ) -> Result<ChannelIterator<'txn, Self>, TxnErr<Self::GraphError>>;

    fn iter_remotes<'txn>(
        &'txn self,
        start: &str,
    ) -> Result<RemotesIterator<'txn, Self>, TxnErr<Self::GraphError>>;

    table!(remotes);
    cursor!(remotes, SmallString, (u64, u64, u64));
    table!(remote);
    table!(revremote);
    table!(remotestates);
    cursor!(remote, u64, (Hash, Merkle));
    rev_cursor!(remote, u64, (Hash, Merkle));

    fn iter_remote<'txn>(
        &'txn self,
        remote: &Self::Remote,
        k: u64,
    ) -> Result<
        Cursor<Self, &'txn Self, Self::RemoteCursor, u64, (Hash, Merkle)>,
        TxnErr<Self::GraphError>,
    >;

    fn iter_rev_remote<'txn>(
        &'txn self,
        remote: &Self::Remote,
        k: Option<u64>,
    ) -> Result<
        RevCursor<Self, &'txn Self, Self::RemoteCursor, u64, (Hash, Merkle)>,
        TxnErr<Self::GraphError>,
    >;

    fn get_remote(
        &mut self,
        name: &str,
    ) -> Result<Option<RemoteRef<Self>>, TxnErr<Self::GraphError>>;

    fn last_remote(
        &self,
        remote: &Self::Remote,
    ) -> Result<Option<(u64, (Hash, Merkle))>, TxnErr<Self::GraphError>>;

    fn get_remote_state(
        &self,
        remote: &Self::Remote,
        n: u64,
    ) -> Result<Option<(u64, (Hash, Merkle))>, TxnErr<Self::GraphError>>;

    fn remote_has_change(
        &self,
        remote: &RemoteRef<Self>,
        hash: Hash,
    ) -> Result<bool, TxnErr<Self::GraphError>>;
    fn remote_has_state(
        &self,
        remote: &RemoteRef<Self>,
        hash: Merkle,
    ) -> Result<bool, TxnErr<Self::GraphError>>;
}

/// Iterate the graph between `(key, min_flag)` and `(key,
/// max_flag)`, where both bounds are included.
pub(crate) fn iter_adjacent<'txn, T: GraphTxnT>(
    txn: &'txn T,
    graph: &'txn T::Graph,
    key: Vertex<ChangeId>,
    min_flag: EdgeFlags,
    max_flag: EdgeFlags,
) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
    Ok(AdjacentIterator {
        it: txn.init_adj(graph, key, Position::ROOT, min_flag, max_flag)?,
        graph,
        txn,
    })
}

pub(crate) fn iter_alive_children<'txn, T: GraphTxnT>(
    txn: &'txn T,
    graph: &'txn T::Graph,
    key: Vertex<ChangeId>,
) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
    iter_adjacent(
        txn,
        graph,
        key,
        EdgeFlags::empty(),
        EdgeFlags::alive_children(),
    )
}

pub(crate) fn iter_deleted_parents<'txn, T: GraphTxnT>(
    txn: &'txn T,
    graph: &'txn T::Graph,
    key: Vertex<ChangeId>,
) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
    iter_adjacent(
        txn,
        graph,
        key,
        EdgeFlags::DELETED | EdgeFlags::PARENT,
        EdgeFlags::all(),
    )
}

pub(crate) fn iter_adj_all<'txn, T: GraphTxnT>(
    txn: &'txn T,
    graph: &'txn T::Graph,
    key: Vertex<ChangeId>,
) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
    iter_adjacent(txn, graph, key, EdgeFlags::empty(), EdgeFlags::all())
}

pub(crate) fn tree_path<T: TreeTxnT>(
    txn: &T,
    v: Position<ChangeId>,
) -> Result<Option<String>, TxnErr<T::TreeError>> {
    if let Some(mut inode) = txn.get_revinodes(v, None)? {
        let mut components = Vec::new();
        while !inode.is_root() {
            if let Some(next) = txn.get_revtree(inode, None)? {
                components.push(next.basename.as_str().to_string());
                inode = next.parent_inode;
            } else {
                assert!(components.is_empty());
                return Ok(None);
            }
        }
        if let Some(mut result) = components.pop() {
            while let Some(c) = components.pop() {
                result = result + "/" + c.as_str()
            }
            return Ok(Some(result));
        }
    }
    Ok(None)
}

pub(crate) fn internal<T: GraphTxnT>(
    txn: &T,
    h: &Option<Hash>,
    p: ChangeId,
) -> Result<Option<ChangeId>, TxnErr<T::GraphError>> {
    match *h {
        Some(Hash::None) => Ok(Some(ChangeId::ROOT)),
        Some(h) => txn.get_internal(h),
        None => Ok(Some(p)),
    }
}

#[derive(Error, Debug)]
pub enum InconsistentChange<T: std::error::Error + 'static> {
    #[error("Undeclared dependency")]
    UndeclaredDep,
    #[error(transparent)]
    Txn(T),
}

impl<T: std::error::Error + 'static> std::convert::From<TxnErr<T>> for InconsistentChange<T> {
    fn from(e: TxnErr<T>) -> Self {
        InconsistentChange::Txn(e.0)
    }
}

pub(crate) fn internal_pos<T: GraphTxnT>(
    txn: &T,
    pos: &Position<Option<Hash>>,
    change_id: ChangeId,
) -> Result<Position<ChangeId>, InconsistentChange<T::GraphError>> {
    let change = if let Some(p) = pos.change {
        if let Some(p) = txn.get_internal(p)? {
            p
        } else {
            return Err(InconsistentChange::UndeclaredDep);
        }
    } else {
        change_id
    };

    Ok(Position {
        change,
        pos: pos.pos,
    })
}

pub fn changeid_log<'db, 'txn: 'db, T: ChannelTxnT>(
    txn: &'txn T,
    channel: &'db T::Channel,
    from: u64,
) -> Result<Cursor<T, &'txn T, T::RevchangesetCursor, u64, (ChangeId, Merkle)>, TxnErr<T::GraphError>>
{
    T::cursor_revchangeset_ref(txn, T::rev_changes(&channel), Some(from))
}

pub(crate) fn current_state<'db, 'txn: 'db, T: ChannelTxnT>(
    txn: &'txn T,
    channel: &'db T::Channel,
) -> Result<Merkle, TxnErr<T::GraphError>> {
    if let Some(e) = txn
        .rev_cursor_revchangeset(T::rev_changes(&channel), None)?
        .next()
    {
        let (_, (_, m)) = e?;
        Ok(m)
    } else {
        Ok(Merkle::zero())
    }
}

pub(crate) fn changeid_log_ref<T: ChannelTxnT, RT: std::ops::Deref<Target = T>>(
    txn: RT,
    channel: &T::Channel,
    from: u64,
) -> Result<Cursor<T, RT, T::RevchangesetCursor, u64, (ChangeId, Merkle)>, TxnErr<T::GraphError>> {
    Ok(T::cursor_revchangeset_ref(
        txn,
        T::rev_changes(&channel),
        Some(from),
    )?)
}

pub(crate) fn changeid_rev_log<'db, 'txn: 'db, T: ChannelTxnT>(
    txn: &'txn T,
    channel: &'db T::Channel,
    from: Option<u64>,
) -> Result<
    RevCursor<T, &'txn T, T::RevchangesetCursor, u64, (ChangeId, Merkle)>,
    TxnErr<T::GraphError>,
> {
    Ok(txn.rev_cursor_revchangeset(T::rev_changes(&channel), from)?)
}

pub(crate) fn log_for_path<
    'txn,
    'channel,
    T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>,
>(
    txn: &'txn T,
    channel: &'channel T::Channel,
    key: Position<ChangeId>,
    from_timestamp: u64,
) -> Result<PathChangeset<'channel, 'txn, T>, TxnErr<T::GraphError>> {
    Ok(PathChangeset {
        iter: T::cursor_revchangeset_ref(txn, T::rev_changes(&channel), Some(from_timestamp))?,
        txn,
        channel,
        key,
    })
}

pub(crate) fn rev_log_for_path<
    'txn,
    'channel,
    T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>,
>(
    txn: &'txn T,
    channel: &'channel T::Channel,
    key: Position<ChangeId>,
    from_timestamp: u64,
) -> Result<RevPathChangeset<'channel, 'txn, T>, TxnErr<T::GraphError>> {
    Ok(RevPathChangeset {
        iter: txn.rev_cursor_revchangeset(T::rev_changes(&channel), Some(from_timestamp))?,
        txn,
        channel,
        key,
    })
}

/// Is there an alive/pseudo edge from `a` to `b`.
pub(crate) fn test_edge<T: GraphTxnT>(
    txn: &T,
    channel: &T::Graph,
    a: Position<ChangeId>,
    b: Position<ChangeId>,
    min: EdgeFlags,
    max: EdgeFlags,
) -> Result<bool, TxnErr<T::GraphError>> {
    debug!("is_connected {:?} {:?}", a, b);
    let mut adj = txn.init_adj(channel, a.inode_vertex(), b, min, max)?;
    match txn.next_adj(channel, &mut adj) {
        Some(Ok(dest)) => Ok(dest.dest == b),
        Some(Err(e)) => Err(e.into()),
        None => Ok(false),
    }
}

/// Is there an alive/pseudo edge to `a`.
pub(crate) fn is_alive<T: GraphTxnT>(
    txn: &T,
    channel: &T::Graph,
    a: Vertex<ChangeId>,
) -> Result<bool, TxnErr<T::GraphError>> {
    if a.is_root() {
        return Ok(true);
    }
    for e in iter_adjacent(
        txn,
        channel,
        a,
        EdgeFlags::PARENT,
        EdgeFlags::all() - EdgeFlags::DELETED,
    )? {
        let e = e?;
        if !e.flag.contains(EdgeFlags::PSEUDO)
            && (e.flag.contains(EdgeFlags::BLOCK) || a.is_empty())
        {
            return Ok(true);
        }
    }
    Ok(false)
}

pub(crate) fn make_changeid<T: GraphTxnT>(
    txn: &T,
    h: &Hash,
) -> Result<ChangeId, TxnErr<T::GraphError>> {
    if let Some(h) = txn.get_internal(*h)? {
        return Ok(h);
    }
    use byteorder::{ByteOrder, LittleEndian};
    use rand::Rng;
    let mut p = match h {
        Hash::None => return Ok(ChangeId::ROOT),
        Hash::Blake3(ref s) => ChangeId(LittleEndian::read_u64(&s[..])),
    };
    while txn.get_external(p)?.is_some() {
        p = ChangeId(rand::thread_rng().gen());
    }
    Ok(p)
}

#[cfg(debug_assertions)]
pub fn debug_tree<P: AsRef<std::path::Path>, T: TreeTxnT>(
    txn: &T,
    file: P,
) -> Result<(), std::io::Error> {
    let root = OwnedPathId {
        parent_inode: Inode::ROOT,
        basename: SmallString::from_str(""),
    };
    let mut f = std::fs::File::create(file)?;
    for t in txn.iter_tree(root, None).unwrap() {
        writeln!(f, "{:?}", t.unwrap())?
    }
    Ok(())
}

#[cfg(debug_assertions)]
pub fn debug_tree_print<T: TreeTxnT>(txn: &T) {
    let root = OwnedPathId {
        parent_inode: Inode::ROOT,
        basename: SmallString::from_str(""),
    };
    for t in txn.iter_tree(root, None).unwrap() {
        debug!("{:?}", t.unwrap())
    }
}

/// Write the graph of a channel to file `f` in graphviz
/// format. **Warning:** this can be really large on old channels.
#[cfg(debug_assertions)]
pub fn debug_to_file<P: AsRef<std::path::Path>, T: GraphIter + ChannelTxnT>(
    txn: &T,
    channel: &T::Channel,
    f: P,
) -> Result<bool, std::io::Error> {
    info!("debug {:?}", f.as_ref());
    let mut f = std::fs::File::create(f)?;
    let done = debug(txn, T::graph(channel), &mut f)?;
    f.flush()?;
    info!("done debugging {:?}", done);
    Ok(done)
}

#[cfg(debug_assertions)]
pub fn debug_revtree<P: AsRef<std::path::Path>, T: TreeTxnT>(
    txn: &T,
    file: P,
) -> Result<(), std::io::Error> {
    let mut f = std::fs::File::create(file)?;
    for t in txn.iter_revtree(Inode::ROOT, None).unwrap() {
        writeln!(f, "{:?}", t.unwrap())?
    }
    Ok(())
}

#[cfg(debug_assertions)]
pub fn debug_revtree_print<T: TreeTxnT>(txn: &T) {
    for t in txn.iter_revtree(Inode::ROOT, None).unwrap() {
        debug!("{:?}", t.unwrap())
    }
}

#[cfg(debug_assertions)]
pub fn debug_inodes<T: TreeTxnT>(txn: &T) {
    debug!("debug_inodes");
    for t in txn.iter_inodes().unwrap() {
        debug!("debug_inodes = {:?}", t.unwrap())
    }
    debug!("/debug_inodes");
}

#[cfg(debug_assertions)]
pub fn debug_revinodes<T: TreeTxnT>(txn: &T) {
    debug!("debug_revinodes");
    for t in txn.iter_revinodes().unwrap() {
        debug!("debug_revinodes = {:?}", t.unwrap())
    }
    debug!("/debug_revinodes");
}

/// Write the graph of a channel to write `W` in graphviz
/// format. **Warning:** this can be really large on old channels.
#[cfg(debug_assertions)]
pub fn debug<W: Write, T: GraphIter>(
    txn: &T,
    channel: &T::Graph,
    mut f: W,
) -> Result<bool, std::io::Error> {
    let mut cursor = txn.iter_graph(&channel).unwrap();
    writeln!(f, "digraph {{")?;
    let mut keys = std::collections::HashSet::new();
    let mut at_least_one = false;
    while let Some(x) = txn.next_graph(&channel, &mut cursor) {
        let (k, v) = x.unwrap();
        at_least_one = true;
        debug!("debug {:?} {:?}", k, v);
        if keys.insert(k) {
            debug_vertex(&mut f, k)?
        }
        debug_edge(txn, channel, &mut f, k, v)?
    }
    writeln!(f, "}}")?;
    Ok(at_least_one)
}

pub fn check_alive<T: ChannelTxnT + GraphIter>(
    txn: &T,
    channel: &T::Graph,
) -> (
    HashMap<Vertex<ChangeId>, Option<Vertex<ChangeId>>>,
    Vec<(Vertex<ChangeId>, Option<Vertex<ChangeId>>)>,
) {
    // Find the reachable with a DFS.
    let mut reachable = HashSet::new();
    let mut stack = vec![Vertex::ROOT];
    while let Some(v) = stack.pop() {
        if !reachable.insert(v) {
            continue;
        }
        for e in iter_adjacent(
            txn,
            &channel,
            v,
            EdgeFlags::empty(),
            EdgeFlags::all() - EdgeFlags::DELETED - EdgeFlags::PARENT,
        )
        .unwrap()
        {
            let e = e.unwrap();
            stack.push(txn.find_block(&channel, e.dest).unwrap());
        }
    }
    debug!("reachable = {:#?}", reachable);

    // Find the alive
    let mut alive_unreachable = HashMap::new();
    let mut cursor = txn.iter_graph(&channel).unwrap();

    let mut visited = HashSet::new();
    let mut k0 = Vertex::ROOT;
    let mut k0_has_pseudo_parents = false;
    let mut k0_has_regular_parents = false;
    let mut reachable_pseudo = Vec::new();
    while let Some(x) = txn.next_graph(&channel, &mut cursor) {
        let (k, v) = x.unwrap();
        debug!("check_alive, k = {:?}, v = {:?}", k, v);
        if k0 != k {
            if k0_has_pseudo_parents && !k0_has_regular_parents {
                reachable_pseudo.push((
                    k0,
                    find_file(txn, &channel, k0, &mut stack, &mut visited).unwrap(),
                ))
            }
            k0 = k;
            k0_has_pseudo_parents = false;
            k0_has_regular_parents = false;
        }
        if v.flag.contains(EdgeFlags::PARENT)
            && !v.flag.contains(EdgeFlags::FOLDER)
            && !v.flag.contains(EdgeFlags::DELETED)
        {
            if v.flag.contains(EdgeFlags::PSEUDO) {
                k0_has_pseudo_parents = true
            } else {
                k0_has_regular_parents = true
            }
        }

        if v.flag.contains(EdgeFlags::PARENT)
            && (v.flag.contains(EdgeFlags::BLOCK) || k.is_empty())
            && !v.flag.contains(EdgeFlags::DELETED)
            && !reachable.contains(&k)
        {
            let file = find_file(txn, &channel, k, &mut stack, &mut visited).unwrap();
            alive_unreachable.insert(k, file);
        }
    }
    if !k0.is_root() && k0_has_pseudo_parents && !k0_has_regular_parents {
        reachable_pseudo.push((
            k0,
            find_file(txn, &channel, k0, &mut stack, &mut visited).unwrap(),
        ));
    }

    (alive_unreachable, reachable_pseudo)
}

fn find_file<T: GraphTxnT>(
    txn: &T,
    channel: &T::Graph,
    k: Vertex<ChangeId>,
    stack: &mut Vec<Vertex<ChangeId>>,
    visited: &mut HashSet<Vertex<ChangeId>>,
) -> Result<Option<Vertex<ChangeId>>, TxnErr<T::GraphError>> {
    let mut file = None;
    stack.clear();
    stack.push(k);
    visited.clear();
    'outer: while let Some(kk) = stack.pop() {
        if !visited.insert(kk) {
            continue;
        }
        for e in iter_adjacent(txn, &channel, kk, EdgeFlags::PARENT, EdgeFlags::all())? {
            let e = e?;
            if e.flag.contains(EdgeFlags::PARENT) {
                if e.flag.contains(EdgeFlags::FOLDER) {
                    file = Some(kk);
                    break 'outer;
                }
                stack.push(txn.find_block_end(&channel, e.dest).unwrap());
            }
        }
    }
    Ok(file)
}

pub fn debug_root<W: Write, T: GraphTxnT>(
    txn: &T,
    channel: &T::Graph,
    root: Vertex<ChangeId>,
    mut f: W,
    down: bool,
) -> Result<(), std::io::Error> {
    writeln!(f, "digraph {{")?;
    let mut visited = HashSet::new();
    let mut stack = vec![root];
    while let Some(v) = stack.pop() {
        if !visited.insert(v) {
            continue;
        }
        debug_vertex(&mut f, v)?;
        for e in iter_adj_all(txn, &channel, v).unwrap() {
            let e = e.unwrap();
            if e.flag.contains(EdgeFlags::PARENT) ^ down {
                debug_edge(txn, &channel, &mut f, v, e)?;
                let v = if e.flag.contains(EdgeFlags::PARENT) {
                    txn.find_block_end(&channel, e.dest).unwrap()
                } else {
                    txn.find_block(&channel, e.dest).unwrap()
                };
                stack.push(v);
            }
        }
    }
    writeln!(f, "}}")?;
    Ok(())
}

fn debug_vertex<W: std::io::Write>(mut f: W, k: Vertex<ChangeId>) -> Result<(), std::io::Error> {
    writeln!(
        f,
        "node_{}_{}_{}[label=\"{} [{};{}[\"];",
        k.change.to_base32(),
        k.start.0,
        k.end.0,
        k.change.to_base32(),
        k.start.0,
        k.end.0,
    )
}

fn debug_edge<T: GraphTxnT, W: std::io::Write>(
    txn: &T,
    channel: &T::Graph,
    mut f: W,
    k: Vertex<ChangeId>,
    v: Edge,
) -> Result<(), std::io::Error> {
    let style = if v.flag.contains(EdgeFlags::DELETED) {
        ", style=dashed"
    } else if v.flag.contains(EdgeFlags::PSEUDO) {
        ", style=dotted"
    } else {
        ""
    };
    let color = if v.flag.contains(EdgeFlags::PARENT) {
        if v.flag.contains(EdgeFlags::FOLDER) {
            "orange"
        } else {
            "red"
        }
    } else if v.flag.contains(EdgeFlags::FOLDER) {
        "royalblue"
    } else {
        "forestgreen"
    };

    if v.flag.contains(EdgeFlags::PARENT) {
        let dest = if v.dest.change.is_root() {
            Vertex::ROOT
        } else if let Ok(dest) = txn.find_block_end(channel, v.dest) {
            dest
        } else {
            return Ok(());
        };
        writeln!(
            f,
            "node_{}_{}_{} -> node_{}_{}_{} [label=\"{}{}{}\", color=\"{}\"{}];",
            k.change.to_base32(),
            k.start.0,
            k.end.0,
            dest.change.to_base32(),
            dest.start.0,
            dest.end.0,
            if v.flag.contains(EdgeFlags::BLOCK) {
                "["
            } else {
                ""
            },
            v.introduced_by.to_base32(),
            if v.flag.contains(EdgeFlags::BLOCK) {
                "]"
            } else {
                ""
            },
            color,
            style
        )?;
    } else if let Ok(dest) = txn.find_block(&channel, v.dest) {
        writeln!(
            f,
            "node_{}_{}_{} -> node_{}_{}_{} [label=\"{}{}{}\", color=\"{}\"{}];",
            k.change.to_base32(),
            k.start.0,
            k.end.0,
            dest.change.to_base32(),
            dest.start.0,
            dest.end.0,
            if v.flag.contains(EdgeFlags::BLOCK) {
                "["
            } else {
                ""
            },
            v.introduced_by.to_base32(),
            if v.flag.contains(EdgeFlags::BLOCK) {
                "]"
            } else {
                ""
            },
            color,
            style
        )?;
    } else {
        writeln!(
            f,
            "node_{}_{}_{} -> node_{}_{} [label=\"{}{}{}\", color=\"{}\"{}];",
            k.change.to_base32(),
            k.start.0,
            k.end.0,
            v.dest.change.to_base32(),
            v.dest.pos.0,
            if v.flag.contains(EdgeFlags::BLOCK) {
                "["
            } else {
                ""
            },
            v.introduced_by.to_base32(),
            if v.flag.contains(EdgeFlags::BLOCK) {
                "]"
            } else {
                ""
            },
            color,
            style
        )?;
    }
    Ok(())
}

/// A cursor over a table, initialised at a certain value.
pub struct Cursor<T: Sized, RT: std::ops::Deref<Target = T>, Cursor, K, V> {
    pub cursor: Cursor,
    pub txn: RT,
    pub marker: std::marker::PhantomData<(T, K, V)>,
}

pub struct RevCursor<T: Sized, RT: std::ops::Deref<Target = T>, Cursor, K, V> {
    pub cursor: Cursor,
    pub txn: RT,
    pub marker: std::marker::PhantomData<(T, K, V)>,
}

initialized_cursor!(changeset, ChangeId, u64, ChannelTxnT, GraphError);
initialized_cursor!(
    revchangeset,
    u64,
    (ChangeId, Merkle),
    ChannelTxnT,
    GraphError
);
initialized_rev_cursor!(
    revchangeset,
    u64,
    (ChangeId, Merkle),
    ChannelTxnT,
    GraphError
);
initialized_cursor!(tree, OwnedPathId, Inode, TreeTxnT, TreeError);
initialized_cursor!(revtree, Inode, OwnedPathId, TreeTxnT, TreeError);
initialized_cursor!(dep, ChangeId, ChangeId, DepsTxnT, DepsError);
initialized_cursor!(
    partials,
    SmallString,
    Position<ChangeId>,
    TreeTxnT,
    TreeError
);
initialized_cursor!(
    rev_touched_files,
    ChangeId,
    Position<ChangeId>,
    DepsTxnT,
    DepsError
);
initialized_cursor!(
    touched_files,
    Position<ChangeId>,
    ChangeId,
    DepsTxnT,
    DepsError
);
initialized_cursor!(remote, u64, (Hash, Merkle));
initialized_rev_cursor!(remote, u64, (Hash, Merkle));
initialized_cursor!(inodes, Inode, Position<ChangeId>, TreeTxnT, TreeError);
#[cfg(debug_assertions)]
initialized_cursor!(revinodes, Position<ChangeId>, Inode, TreeTxnT, TreeError);

/// An iterator for nodes adjacent to `key` through an edge with flags smaller than `max_flag`.
pub struct AdjacentIterator<'txn, T: GraphTxnT> {
    it: T::Adj,
    graph: &'txn T::Graph,
    txn: &'txn T,
}

impl<'txn, T: GraphTxnT> Iterator for AdjacentIterator<'txn, T> {
    type Item = Result<Edge, TxnErr<T::GraphError>>;
    fn next(&mut self) -> Option<Self::Item> {
        self.txn.next_adj(self.graph, &mut self.it)
    }
}

pub struct PathChangeset<'channel, 'txn: 'channel, T: ChannelTxnT + DepsTxnT> {
    txn: &'txn T,
    channel: &'channel T::Channel,
    iter: Cursor<T, &'txn T, T::RevchangesetCursor, u64, (ChangeId, Merkle)>,
    key: Position<ChangeId>,
}

pub struct RevPathChangeset<'channel, 'txn: 'channel, T: ChannelTxnT + DepsTxnT> {
    txn: &'txn T,
    channel: &'channel T::Channel,
    iter: RevCursor<T, &'txn T, T::RevchangesetCursor, u64, (ChangeId, Merkle)>,
    key: Position<ChangeId>,
}

impl<
        'channel,
        'txn: 'channel,
        T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>,
    > Iterator for PathChangeset<'channel, 'txn, T>
{
    type Item = Result<Hash, TxnErr<T::GraphError>>;
    fn next(&mut self) -> Option<Self::Item> {
        while let Some(x) = self.iter.next() {
            let (_, (changeid, _)) = match x {
                Ok(x) => x,
                Err(e) => return Some(Err(e)),
            };
            let iter = match self.txn.iter_rev_touched_files(changeid, None) {
                Ok(iter) => iter,
                Err(e) => return Some(Err(e)),
            };
            for x in iter {
                let (p, touched) = match x {
                    Ok(x) => x,
                    Err(e) => return Some(Err(e)),
                };
                if p > changeid {
                    break;
                } else if p < changeid {
                    continue;
                }
                match is_ancestor_of(self.txn, T::graph(&self.channel), self.key, touched) {
                    Ok(true) => return self.txn.get_external(changeid).transpose(),
                    Err(e) => return Some(Err(e)),
                    Ok(false) => {}
                }
            }
        }
        None
    }
}

impl<
        'channel,
        'txn: 'channel,
        T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>,
    > Iterator for RevPathChangeset<'channel, 'txn, T>
{
    type Item = Result<Hash, TxnErr<T::GraphError>>;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let changeid = match self.iter.next()? {
                Err(e) => return Some(Err(e)),
                Ok((_, (changeid, _))) => changeid,
            };
            let iter = match self.txn.iter_rev_touched_files(changeid, None) {
                Ok(iter) => iter,
                Err(e) => return Some(Err(e)),
            };
            for x in iter {
                let (p, touched) = match x {
                    Ok(x) => x,
                    Err(e) => return Some(Err(e)),
                };
                if p > changeid {
                    break;
                } else if p < changeid {
                    continue;
                }
                match is_ancestor_of(self.txn, T::graph(&self.channel), self.key, touched) {
                    Ok(true) => return self.txn.get_external(changeid).transpose(),
                    Err(e) => return Some(Err(e)),
                    Ok(false) => {}
                }
            }
        }
    }
}

fn is_ancestor_of<T: GraphTxnT>(
    txn: &T,
    channel: &T::Graph,
    a: Position<ChangeId>,
    b: Position<ChangeId>,
) -> Result<bool, TxnErr<T::GraphError>> {
    let mut stack = vec![b];
    let mut visited = std::collections::HashSet::new();
    debug!("a = {:?}", a);
    while let Some(b) = stack.pop() {
        debug!("pop {:?}", b);
        if a == b {
            return Ok(true);
        }
        if !visited.insert(b) {
            continue;
        }
        for p in iter_adjacent(
            txn,
            channel,
            b.inode_vertex(),
            EdgeFlags::FOLDER | EdgeFlags::PARENT,
            EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::PSEUDO,
        )? {
            let p = p?;
            // Ok, since `p` is in the channel.
            let parent = txn.find_block_end(channel, p.dest).unwrap();
            for pp in iter_adjacent(
                txn,
                channel,
                parent,
                EdgeFlags::FOLDER | EdgeFlags::PARENT,
                EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::PSEUDO,
            )? {
                let pp = pp?;
                if pp.dest == a {
                    return Ok(true);
                }
                stack.push(pp.dest)
            }
        }
    }
    Ok(false)
}

pub struct ChannelIterator<'txn, T: TxnT> {
    txn: &'txn T,
    cursor: T::ChannelsCursor,
}

impl<'txn, T: TxnT> Iterator for ChannelIterator<'txn, T> {
    type Item = Result<ChannelRef<T>, TxnErr<T::GraphError>>;
    fn next(&mut self) -> Option<Self::Item> {
        // Option<(SmallString, (u64, u64, u64, u64, u64, u64))>
        match self.txn.cursor_channels_next(&mut self.cursor) {
            Err(e) => Some(Err(e)),
            Ok(Some((name, _))) => self.txn.load_channel(name.as_str()).transpose(),
            Ok(None) => None,
        }
    }
}

pub struct RemotesIterator<'txn, T: TxnT> {
    txn: &'txn T,
    cursor: T::RemotesCursor,
}

impl<'txn, T: TxnT> Iterator for RemotesIterator<'txn, T> {
    type Item = Result<RemoteRef<T>, TxnErr<T::GraphError>>;
    fn next(&mut self) -> Option<Self::Item> {
        match self.txn.cursor_remotes_next(&mut self.cursor) {
            Ok(Some((name, _))) => self.txn.load_remote(name.as_str()).transpose(),
            Ok(None) => None,
            Err(e) => Some(Err(e)),
        }
    }
}

pub trait GraphMutTxnT: GraphTxnT {
    put_del!(internal, Hash, ChangeId, GraphError);
    put_del!(external, ChangeId, Hash, GraphError);

    /// Insert a key and a value to a graph. Returns `false` if and only if `(k, v)` was already in the graph, in which case no insertion happened.
    fn put_graph(
        &mut self,
        channel: &mut Self::Graph,
        k: Vertex<ChangeId>,
        v: Edge,
    ) -> Result<bool, TxnErr<Self::GraphError>>;

    /// Delete a key and a value from a graph. Returns `true` if and only if `(k, v)` was in the graph.
    fn del_graph(
        &mut self,
        channel: &mut Self::Graph,
        k: Vertex<ChangeId>,
        v: Option<Edge>,
    ) -> Result<bool, TxnErr<Self::GraphError>>;

    /// Split a key `[a, b[` at position `pos`, yielding two keys `[a,
    /// pos[` and `[pos, b[` linked by an edge.
    fn split_block(
        &mut self,
        graph: &mut Self::Graph,
        key: Vertex<ChangeId>,
        pos: ChangePosition,
        buf: &mut Vec<Edge>,
    ) -> Result<(), TxnErr<Self::GraphError>>;
}

pub trait ChannelMutTxnT: ChannelTxnT + GraphMutTxnT {
    fn graph_mut(channel: &mut Self::Channel) -> &mut Self::Graph;
    fn touch_channel(&mut self, channel: &mut Self::Channel, t: Option<u64>);

    /// Add a change and a timestamp to a change table. Returns `None` if and only if `(p, t)` was already in the change table, in which case no insertion happened. Returns the new state else.
    fn put_changes(
        &mut self,
        channel: &mut Self::Channel,
        p: ChangeId,
        t: ApplyTimestamp,
        h: &Hash,
    ) -> Result<Option<Merkle>, TxnErr<Self::GraphError>>;

    /// Delete a change from a change table. Returns `true` if and only if `(p, t)` was in the change table.
    fn del_changes(
        &mut self,
        channel: &mut Self::Channel,
        p: ChangeId,
        t: ApplyTimestamp,
    ) -> Result<bool, TxnErr<Self::GraphError>>;
}

pub trait DepsMutTxnT: DepsTxnT {
    put_del!(dep, ChangeId, ChangeId, DepsError);
    put_del!(revdep, ChangeId, ChangeId, DepsError);
    put_del!(touched_files, Position<ChangeId>, ChangeId, DepsError);
    put_del!(rev_touched_files, ChangeId, Position<ChangeId>, DepsError);
}

pub trait TreeMutTxnT: TreeTxnT {
    put_del!(inodes, Inode, Position<ChangeId>, TreeError);
    put_del!(revinodes, Position<ChangeId>, Inode, TreeError);
    put_del!(tree, PathId, Inode, TreeError);
    put_del!(revtree, Inode, PathId, TreeError);
    fn put_partials(
        &mut self,
        k: &str,
        e: Position<ChangeId>,
    ) -> Result<bool, TxnErr<Self::TreeError>>;

    fn del_partials(
        &mut self,
        k: &str,
        e: Option<Position<ChangeId>>,
    ) -> Result<bool, TxnErr<Self::TreeError>>;
}

/// The trait of immutable transactions.
pub trait MutTxnT:
    GraphMutTxnT
    + ChannelMutTxnT
    + DepsMutTxnT<DepsError = <Self as GraphTxnT>::GraphError>
    + TreeMutTxnT<TreeError = <Self as GraphTxnT>::GraphError>
    + TxnT
{
    /// Open a channel, creating it if it is missing. The return type
    /// is a `Rc<RefCell<…>>` in order to avoid:
    /// - opening the same channel twice. Since a channel contains pointers, that could potentially lead to double-borrow issues. We absolutely have to check that at runtime (hence the `RefCell`).
    /// - writing the channel to disk (if the backend is written on the disk) for every minor operation on the channel.
    ///
    /// Additionally, the `Rc` is used to:
    /// - avoid having to commit channels explicitly (channels are
    /// committed automatically upon committing the transaction), and
    /// - to return a value that doesn't borrow the transaction, so
    /// that the channel can actually be used in a mutable transaction.
    fn open_or_create_channel(&mut self, name: &str) -> Result<ChannelRef<Self>, Self::GraphError>;

    fn fork(
        &mut self,
        channel: &ChannelRef<Self>,
        name: &str,
    ) -> Result<ChannelRef<Self>, ForkError<Self::GraphError>>;

    fn rename_channel(
        &mut self,
        channel: &mut ChannelRef<Self>,
        name: &str,
    ) -> Result<(), ForkError<Self::GraphError>>;

    fn drop_channel(&mut self, name: &str) -> Result<bool, Self::GraphError>;

    /// Commit this transaction.
    fn commit(self) -> Result<(), Self::GraphError>;

    fn open_or_create_remote(&mut self, name: &str) -> Result<RemoteRef<Self>, Self::GraphError>;

    fn put_remote(
        &mut self,
        remote: &mut RemoteRef<Self>,
        k: u64,
        v: (Hash, Merkle),
    ) -> Result<bool, Self::GraphError>;

    fn del_remote(
        &mut self,
        remote: &mut RemoteRef<Self>,
        k: u64,
    ) -> Result<bool, Self::GraphError>;

    fn drop_remote(&mut self, remote: RemoteRef<Self>) -> Result<bool, Self::GraphError>;

    fn drop_named_remote(&mut self, remote: &str) -> Result<bool, Self::GraphError>;
}

pub(crate) fn put_inodes_with_rev<T: TreeMutTxnT>(
    txn: &mut T,
    inode: Inode,
    position: Position<ChangeId>,
) -> Result<(), TxnErr<T::TreeError>> {
    txn.put_inodes(inode, position)?;
    txn.put_revinodes(position, inode)?;
    Ok(())
}

pub(crate) fn del_inodes_with_rev<T: TreeMutTxnT>(
    txn: &mut T,
    inode: Inode,
    position: Position<ChangeId>,
) -> Result<bool, TxnErr<T::TreeError>> {
    if txn.del_inodes(inode, Some(position))? {
        assert!(txn.del_revinodes(position, Some(inode))?);
        Ok(true)
    } else {
        Ok(false)
    }
}

pub(crate) fn put_tree_with_rev<T: TreeMutTxnT>(
    txn: &mut T,
    file_id: PathId,
    inode: Inode,
) -> Result<(), TxnErr<T::TreeError>> {
    txn.put_tree(file_id, inode)?;
    txn.put_revtree(inode, file_id)?;
    Ok(())
}

pub(crate) fn del_tree_with_rev<T: TreeMutTxnT>(
    txn: &mut T,
    file_id: PathId,
    inode: Inode,
) -> Result<bool, TxnErr<T::TreeError>> {
    if txn.del_tree(file_id, Some(inode))? {
        if !file_id.basename.is_empty() {
            assert!(txn.del_revtree(inode, Some(file_id))?);
        }
        Ok(true)
    } else {
        Ok(false)
    }
}

pub(crate) fn del_graph_with_rev<T: GraphMutTxnT>(
    txn: &mut T,
    graph: &mut T::Graph,
    mut flag: EdgeFlags,
    mut k0: Vertex<ChangeId>,
    mut k1: Vertex<ChangeId>,
    introduced_by: ChangeId,
) -> Result<bool, TxnErr<T::GraphError>> {
    if flag.contains(EdgeFlags::PARENT) {
        std::mem::swap(&mut k0, &mut k1);
        flag -= EdgeFlags::PARENT
    }
    debug!("del_graph_with_rev {:?} {:?} {:?}", flag, k0, k1);
    let a = txn.del_graph(
        graph,
        k0,
        Some(Edge {
            flag,
            dest: Position {
                change: k1.change,
                pos: k1.start,
            },
            introduced_by,
        }),
    )?;
    let b = txn.del_graph(
        graph,
        k1,
        Some(Edge {
            flag: flag | EdgeFlags::PARENT,
            dest: Position {
                change: k0.change,
                pos: k0.end,
            },
            introduced_by,
        }),
    )?;
    assert!((a && b) || (!a && !b));
    Ok(a && b)
}

pub(crate) fn put_graph_with_rev<T: GraphMutTxnT>(
    txn: &mut T,
    graph: &mut T::Graph,
    flag: EdgeFlags,
    k0: Vertex<ChangeId>,
    k1: Vertex<ChangeId>,
    introduced_by: ChangeId,
) -> Result<bool, TxnErr<T::GraphError>> {
    debug_assert!(!flag.contains(EdgeFlags::PARENT));
    if k0.change == k1.change {
        assert_ne!(k0.start_pos(), k1.start_pos());
    }
    if introduced_by == ChangeId::ROOT {
        assert!(flag.contains(EdgeFlags::PSEUDO));
    }
    debug!("put_graph_with_rev {:?} {:?} {:?}", k0, k1, flag);
    let a = txn.put_graph(
        graph,
        k0,
        Edge {
            flag,
            dest: Position {
                change: k1.change,
                pos: k1.start,
            },
            introduced_by,
        },
    )?;
    let b = txn.put_graph(
        graph,
        k1,
        Edge {
            flag: flag ^ EdgeFlags::PARENT,
            dest: Position {
                change: k0.change,
                pos: k0.end,
            },
            introduced_by,
        },
    )?;
    assert!((a && b) || (!a && !b));
    Ok(a && b)
}

pub(crate) fn register_change<
    T: GraphMutTxnT + DepsMutTxnT<DepsError = <T as GraphTxnT>::GraphError>,
>(
    txn: &mut T,
    internal: ChangeId,
    hash: Hash,
    change: &Change,
) -> Result<(), TxnErr<T::GraphError>> {
    debug!("registering change {:?}", hash);
    txn.put_external(internal, hash)?;
    txn.put_internal(hash, internal)?;
    for dep in change.dependencies.iter() {
        debug!("dep = {:?}", dep);
        let dep_internal = txn.get_internal(*dep)?.unwrap();
        debug!("{:?} depends on {:?}", internal, dep_internal);
        txn.put_revdep(dep_internal, internal)?;
        txn.put_dep(internal, dep_internal)?;
    }
    for hunk in change.changes.iter().flat_map(|r| r.iter()) {
        let (inode, pos) = match *hunk {
            Atom::NewVertex(NewVertex {
                ref inode,
                ref flag,
                ref start,
                ref end,
                ..
            }) => {
                if flag.contains(EdgeFlags::FOLDER) && start == end {
                    (inode, Some(*start))
                } else {
                    (inode, None)
                }
            }
            Atom::EdgeMap(EdgeMap { ref inode, .. }) => (inode, None),
        };
        let change = if let Some(c) = inode.change {
            txn.get_internal(c)?.unwrap_or(internal)
        } else {
            internal
        };
        let inode = Position {
            change,
            pos: inode.pos,
        };
        debug!("touched: {:?} {:?}", inode, internal);
        txn.put_touched_files(inode, internal)?;
        txn.put_rev_touched_files(internal, inode)?;
        if let Some(pos) = pos {
            let inode = Position {
                change: internal,
                pos,
            };
            txn.put_touched_files(inode, internal)?;
            txn.put_rev_touched_files(internal, inode)?;
        }
    }
    Ok(())
}

fn first_state_after<T: ChannelTxnT>(
    txn: &T,
    c: &T::Channel,
    pos: u64,
) -> Result<Option<(u64, Merkle)>, TxnErr<T::GraphError>> {
    for x in T::cursor_revchangeset_ref(txn, T::rev_changes(&c), Some(pos))? {
        let (n, (_, m)) = x?;
        if n >= pos {
            return Ok(Some((n, m)));
        }
    }
    Ok(None)
}

fn last_state<T: ChannelTxnT>(
    txn: &T,
    c: &T::Channel,
) -> Result<Option<(u64, Merkle)>, TxnErr<T::GraphError>> {
    if let Some(e) = txn
        .rev_cursor_revchangeset(T::rev_changes(&c), None)?
        .next()
    {
        let (b, (_, state)) = e?;
        Ok(Some((b, state)))
    } else {
        Ok(None)
    }
}

/// Find the last state of c1 that is also in c0.
pub fn last_common_state<T: ChannelTxnT>(
    txn: &T,
    c0: &T::Channel,
    c1: &T::Channel,
) -> Result<(u64, u64, Merkle), TxnErr<T::GraphError>> {
    let mut a = 0;
    let (mut b, mut state) = if let Some(x) = last_state(txn, c1)? {
        x
    } else {
        return Ok((0, 0, Merkle::zero()));
    };
    if let Some(aa) = txn.channel_has_state(c0, state)? {
        return Ok((aa, b, state));
    }
    let mut aa = 0;
    while a < b {
        let mid = (a + b) / 2;
        let (_, s) = first_state_after(txn, c1, mid)?.unwrap();
        state = s;
        if let Some(aa_) = txn.channel_has_state(c0, state)? {
            aa = aa_;
            a = mid
        } else {
            b = mid
        }
    }
    Ok((aa, a, state))
}

/// Check that each inode in the inodes table maps to an alive vertex,
/// and that each inode in the tree table is reachable by only one
/// path.
pub fn check_tree_inodes<T: GraphTxnT + TreeTxnT>(txn: &T, channel: &T::Graph) {
    // Sanity check
    for x in txn.iter_inodes().unwrap() {
        let (inode, vertex) = x.unwrap();
        let mut inode_ = inode;
        while !inode_.is_root() {
            if let Some(next) = txn.get_revtree(inode_, None).unwrap() {
                inode_ = next.parent_inode;
            } else {
                panic!("inode = {:?}, inode_ = {:?}", inode, inode_);
            }
        }
        if !is_alive(txn, &channel, vertex.inode_vertex()).unwrap() {
            for e in iter_adj_all(txn, channel, vertex.inode_vertex()).unwrap() {
                error!("{:?} {:?} {:?}", inode, vertex, e.unwrap())
            }
            panic!(
                "inode {:?}, vertex {:?}, is not alive, {:?}",
                inode,
                vertex,
                tree_path(txn, vertex)
            )
        }
    }
    let mut h = HashMap::new();
    let id0 = OwnedPathId {
        parent_inode: Inode::ROOT,
        basename: crate::small_string::SmallString::new(),
    };
    for x in txn.iter_tree(id0, None).unwrap() {
        let (id, inode) = x.unwrap();
        if let Some(inode_) = h.insert(id.clone(), inode) {
            panic!("id {:?} maps to two inodes: {:?} {:?}", id, inode, inode_);
        }
    }
}

/// Check that each alive vertex in the graph is reachable, and vice-versa.
pub fn check_alive_debug<T: GraphIter + ChannelTxnT, C: crate::changestore::ChangeStore>(
    changes: &C,
    txn: &T,
    channel: &T::Channel,
    line: u32,
) -> Result<(), std::io::Error> {
    let (alive, reachable) = crate::pristine::check_alive(txn, T::graph(channel));
    let mut h = HashSet::new();
    if !alive.is_empty() {
        for (k, file) in alive.iter() {
            debug!("alive = {:?}, file = {:?}", k, file);
            h.insert(file);
        }
    }
    if !reachable.is_empty() {
        for (k, file) in reachable.iter() {
            debug!("reachable = {:?}, file = {:?}", k, file);
            h.insert(file);
        }
    }
    for file in h.iter() {
        let file_ = file.unwrap().start_pos();

        let (path, _) = crate::fs::find_path(changes, txn, channel, true, file_).unwrap();
        let path = path.replace("/", "_");
        let name = format!(
            "debug_{:?}_{}_{}",
            path,
            file_.change.to_base32(),
            file_.pos.0
        );
        let mut f = std::fs::File::create(&name)?;
        let graph = crate::alive::retrieve::retrieve(txn, T::graph(channel), file_).unwrap();
        graph.debug(changes, txn, T::graph(channel), false, false, &mut f)?;

        let mut f = std::fs::File::create(&format!("{}_all", name))?;
        debug_root(txn, T::graph(channel), file.unwrap(), &mut f, false)?;
    }
    if !h.is_empty() {
        if !alive.is_empty() {
            panic!("alive call line {}: {:?}", line, alive);
        } else {
            panic!("reachable: {:?}", reachable);
        }
    }
    Ok(())
}