dag.rs

//! Code for an editable, undoable forest of syntax trees.

use crate::arena::Arena;
use crate::ast;
use crate::ast::{Ast, AstClass};

use crate::core::{Direction, Path, Side};
use std::{collections::HashMap, hash::Hash};

/// The two possible locations where an edit could cause nodes to be replaced
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum EditLocation {
    /// The edit caused the cursor to be replaced
    Cursor = 0,
    /// The edit caused the parent to be replaced
    Parent = 1,
}

impl EditLocation {
    /// How many steps above the cursor was the edit made
    #[inline]
    fn steps_above_cursor(self) -> usize {
        self as usize
    }
}

/// An enum that's returned when any of the 'edit' methods in [`Dag`] are successful.
#[allow(missing_docs)]
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
pub enum EditSuccess<C: AstClass> {
    Undo,
    Redo,
    Move(usize, Direction),
    Replace(C),
    InsertChild(C),
    InsertNextToCursor { side: Side, class: C },
    Delete { name: String },
}

impl<C: AstClass> EditSuccess<C> {
    /// Writes an info message of a successful action using `info!`
    fn log_message(self) {
        match self {
            EditSuccess::Undo => log::info!("Undoing one change"),
            EditSuccess::Redo => log::info!("Redoing one change"),
            EditSuccess::Move(n, Direction::Up) => log::info!("Moving {} levels up the tree", n),
            EditSuccess::Move(n, Direction::Down) => {
                log::info!("Moving {} levels down the tree", n)
            }
            EditSuccess::Move(n, Direction::Prev) => {
                log::info!("Moving to {}th previous sibling", n)
            }
            EditSuccess::Move(n, Direction::Next) => log::info!("Moving to {}th next sibling", n),
            EditSuccess::Replace(class) => {
                log::info!("Replacing with '{}'/{}", class.to_char(), class.name())
            }
            EditSuccess::InsertChild(class) => {
                log::info!(
                    "Inserting '{}'/{} as new child",
                    class.to_char(),
                    class.name()
                )
            }
            EditSuccess::InsertNextToCursor { side, class } => log::info!(
                "Inserting '{}'/{} {} the cursor",
                class.to_char(),
                class.name(),
                side.relational_word()
            ),
            EditSuccess::Delete { name } => log::info!("Deleting {}", name),
        }
    }
}

/// An error that represents an error in any of the 'edit' methods in [`Dag`].
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
pub enum EditErr<C: AstClass> {
    /* MOVEMENT ERRORS */
    /// Trying to move to a sibling of the root
    MoveToSiblingOfRoot,

    /* EDITING ERRORS */
    /// Trying to undo the earliest change
    NoChangesToUndo,
    /// Trying to redo the latest change
    NoChangesToRedo,
    /// The user typed a char that doesn't correspond to any node
    CharNotANode(char),
    /// Trying to insert a node that cannot be root node
    CannotBeRoot(C),
    /// Trying to insert a node that cannot be a child of the cursor
    CannotBeChild {
        /// The class representing the disallowed child type
        class: C,
        /// The [`display_name`](Ast::display_name) of the parent node
        parent_name: String,
    },
    /// Trying to replace many children
    ReplaceError {
        /// Current node index
        current_child_index: usize,
        /// Last node index
        last_child_index: usize,
        /// Node count
        node_count: usize,
    },
    /// There were no nodes to insert
    NoNodesToInsert,
    /// An error was generated by the Ast code when trying to insert a node
    InsertError(ast::InsertError),
    /// An error was generated by the Ast code when trying to delete a node
    DeleteError(ast::DeleteError),
    /// Trying to add a sibling to the root
    AddSiblingToRoot,
    /// Trying to delete the root
    DeletingRoot,
}

impl<C: AstClass> EditErr<C> {
    /// Writes an warning message of the encountered error using either `warn!` or `error!`,
    /// depending on the severity of the error
    fn log_message(self) {
        match self {
            EditErr::MoveToSiblingOfRoot => log::warn!("Can't move to a sibling of the root."),
            EditErr::NoChangesToUndo => log::warn!("No changes to undo."),
            EditErr::NoChangesToRedo => log::warn!("No changes to redo."),
            EditErr::NoNodesToInsert => log::warn!("No nodes to insert."),
            EditErr::InsertError(e) => log::warn!("{}", e),
            EditErr::DeleteError(e) => log::warn!("{}", e),
            EditErr::CharNotANode(c) => log::warn!("'{}' doesn't correspond to any node type.", c),
            EditErr::CannotBeRoot(c) => {
                log::warn!("'{}' cannot be root", c.name())
            }
            EditErr::CannotBeChild { class, parent_name } => {
                log::warn!("'{}' cannot be a child of {}", class.name(), parent_name)
            }
            EditErr::ReplaceError {
                current_child_index,
                last_child_index,
                node_count,
            } => {
                log::warn!(
                    "Current child index: {}, Last child index {}, to be replaced node count {}",
                    current_child_index,
                    last_child_index,
                    node_count,
                )
            }
            EditErr::AddSiblingToRoot => log::warn!("Can't add siblings to the root."),
            EditErr::DeletingRoot => log::warn!("Can't delete the root."),
        }
    }
}

impl<C: AstClass> From<ast::InsertError> for EditErr<C> {
    fn from(e: ast::InsertError) -> EditErr<C> {
        EditErr::InsertError(e)
    }
}

impl<C: AstClass> From<ast::DeleteError> for EditErr<C> {
    fn from(e: ast::DeleteError) -> EditErr<C> {
        EditErr::DeleteError(e)
    }
}

/// An alias for [`Result`] that is the return type of all of [`Dag`]'s edit methods.
pub type EditResult<C> = Result<EditSuccess<C>, EditErr<C>>;

/// A trait-extension that provides a convenient way convert [`EditResult`]s into log messages.
pub trait LogMessage {
    /// Log the current result's message to the appropriate log channel.
    fn log_message(self);
}

impl<C: AstClass> LogMessage for EditResult<C> {
    /// Consumes this `EditResult` and logs an appropriate summary report (using `info!` for
    /// [`EditSuccess`]es and `warn!` or `error!` for [`EditErr`]s).
    fn log_message(self) {
        match self {
            Ok(ok) => ok.log_message(),
            Err(err) => err.log_message(),
        }
    }
}

/// A specification of things which can be inserted into a syntax tree
#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
pub enum Insertable {
    /// Insert the node given by a certain [`char`] some number of times
    CountedNode(usize, char),
}

impl std::fmt::Display for Insertable {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Insertable::CountedNode(count, c) => write!(f, "{}{}", count, c),
        }
    }
}

/// A representation of a single edit, along with the cursor locations around it
struct Snapshot<'arena, Node: Ast<'arena>> {
    cursor_before: Path,
    root: &'arena Node,
    cursor_after: Path,
}

impl<'arena, Node: Ast<'arena>> Snapshot<'arena, Node> {
    fn new(cursor_before: Path, root: &'arena Node, cursor_after: Path) -> Self {
        Snapshot {
            cursor_before,
            root,
            cursor_after,
        }
    }
}

/// A datastructure that stores the history of a tree as a Dag (Directed Acyclic Graph) of
/// **immutable** nodes.
///
/// This means that every node that has ever been created exists somewhere in the Dag, and when
/// changes are made, every ancestor of that node is cloned until the root is reached and that
/// root becomes the new 'current' root.  This is very similar to the way Git handles commits -
/// each node is like a file/directory and each root is a commit.
///
/// Therefore, moving back through the history is as simple as reading a different root node from
/// the `roots` vector, and following its descendants through the Dag of nodes.
pub struct Dag<'arena, Node: Ast<'arena>> {
    /// The arena in which all the `Node`s will be stored
    arena: &'arena Arena<Node>,
    /// A [`Vec`] containing a reference to the root node at every edit in the undo history.  This
    /// is required to always have length at least one.
    root_history: Vec<Snapshot<'arena, Node>>,
    /// An index into [`root_history`](Dag::root_history) of the current edit.  This is required to
    /// be in `0..root_history.len()`.
    history_index: usize,
    current_cursor_path: Path,
    cursor_location_history: HashMap<usize, usize>,
}

impl<'arena, Node: Ast<'arena>> Dag<'arena, Node> {
    /// Builds a new `Dag`, given the tree it should contain
    pub fn new(arena: &'arena Arena<Node>, root: &'arena Node, cursor_path: Path) -> Self {
        Dag {
            arena,
            root_history: vec![Snapshot::new(
                cursor_path.clone(),
                root,
                cursor_path.clone(),
            )],
            history_index: 0,
            current_cursor_path: cursor_path,
            cursor_location_history: HashMap::new(),
        }
    }

    /* NAVIGATION METHODS */

    /// Returns a reference to the node that is currently the root of the AST.
    pub fn root(&self) -> &'arena Node {
        // This indexing shouldn't panic because we require that `self.history_index` is a valid
        // index into `self.root_history`, and `self.root_history` has at least one element
        self.root_history[self.history_index].root
    }

    /// Returns the cursor node and its direct parent (if such a parent exists)
    pub fn cursor_and_parent(&self) -> (&'arena Node, Option<&'arena Node>) {
        self.current_cursor_path.cursor_and_parent(self.root())
    }

    /// Returns a reference to the node that is currently under the cursor.
    pub fn cursor(&self) -> &'arena Node {
        self.current_cursor_path.cursor(self.root())
    }

    /// Move the cursor a given `distance` in a given [`Direction`] across the tree.
    pub fn move_cursor(
        &mut self,
        distance: usize,
        direction: Direction,
    ) -> EditResult<Node::Class> {
        let (mut current_cursor, cursor_parent) = self.cursor_and_parent();
        let successful_distance = match direction {
            Direction::Down => {
                let mut successful_distance = 0usize;
                while !current_cursor.children().is_empty() && successful_distance < distance {
                    // use current_cursor's memory address as key in hashmap,
                    // look up the previous cursor location in hashmap
                    // if key is not in hashmap, return None, and use 0 as index
                    let current_node_id = current_cursor as *const Node as usize;
                    let index = *self
                        .cursor_location_history
                        .get(&current_node_id)
                        .unwrap_or(&0);
                    self.current_cursor_path.push(index);
                    current_cursor = current_cursor.children()[index];
                    successful_distance += 1;
                }
                successful_distance
            }
            Direction::Up => {
                let mut successful_distance = 0usize;
                while !self.current_cursor_path.is_root() && successful_distance < distance {
                    let (_, parent) = self.cursor_and_parent();
                    // this block of code will run when the current cursor is not on root, so unwrap is ok
                    let parent_node_id = parent.unwrap() as *const Node as usize;
                    // insert or update the parent_node_id and current_cursor_index in hashmap
                    self.cursor_location_history
                        .insert(parent_node_id, self.current_cursor_path.pop().unwrap());
                    successful_distance += 1;
                }
                successful_distance
            }
            Direction::Prev => {
                let index = self
                    .current_cursor_path
                    .last_mut()
                    .ok_or(EditErr::MoveToSiblingOfRoot)?;
                let last_index = *index;
                *index = last_index.saturating_sub(distance);
                // Return the distance that we actually moved
                last_index - *index
            }
            Direction::Next => {
                let index = self
                    .current_cursor_path
                    .last_mut()
                    .ok_or(EditErr::MoveToSiblingOfRoot)?;
                let last_index = *index;
                // We can unwrap here, because the only way for a node to not have a parent is
                // if it's the root.  And if the cursor is at the root, then the ? in the last line
                // would have caught the error.  The subtraction also cannot overflow because the
                // parent of the cursor must have at least the cursor as a child.
                let max_index = cursor_parent.unwrap().children().len() - 1;
                *index = (*index + distance).min(max_index);
                // Return the distance we travelled
                *index - last_index
            }
        };
        Ok(EditSuccess::Move(successful_distance, direction))
    }

    /* HISTORY METHODS */

    /// Move one step back in the tree history
    pub fn undo(&mut self, steps: usize) -> EditResult<Node::Class> {
        log::trace!("Performing undo.");
        // Early return if there are no changes to undo
        if self.history_index == 0 {
            return Err(EditErr::NoChangesToUndo);
        }
        // Move the history index back by one to perform the undo
        self.history_index = self.history_index.saturating_sub(steps);
        // Follow the behaviour of other text editors and update the location of the cursor
        // with its location in the snapshot we are going forward to
        self.current_cursor_path
            .clone_from(&self.root_history[self.history_index + 1].cursor_before);
        log::debug!("Setting cursor path to {:?}", self.current_cursor_path);
        Ok(EditSuccess::Undo)
    }

    /// Move one step forward in the tree history
    pub fn redo(&mut self, steps: usize) -> EditResult<Node::Class> {
        log::trace!("Performing redo.");
        // Early return if there are no changes to redo
        if self.history_index >= self.root_history.len() - 1 {
            return Err(EditErr::NoChangesToRedo);
        }
        // Move the history index forward by one to perform the redo
        self.history_index = (self.history_index + steps).min(self.root_history.len() - 1);
        // Follow the behaviour of other text editors and update the location of the cursor
        // with its location in the snapshot we are going back to
        self.current_cursor_path
            .clone_from(&self.root_history[self.history_index].cursor_after);
        log::debug!("Setting cursor path to {:?}", self.current_cursor_path);
        Ok(EditSuccess::Redo)
    }

    /* EDITING METHODS */

    fn perform_edit(
        &mut self,
        mut edit_func: impl FnMut(
            // The `Dag` being edited
            &mut Self,
            // The parent and the cursor's child index (or `None` if the cursor is at the root)
            Option<(&'arena Node, usize)>,
            // A reference to the node under the cursor
            &'arena Node,
        ) -> Result<
            (Node, EditLocation, EditSuccess<Node::Class>),
            EditErr<Node::Class>,
        >,
    ) -> EditResult<Node::Class> {
        // Generate a vec of pointers to the nodes that we will have to clone.  We have to store
        // this as a vec because the iterator that produces them (cursor_path::NodeIter) can only
        // yield values from the root downwards, whereas we need the nodes in the opposite order.
        let nodes_to_clone: Vec<&Node> = self.current_cursor_path.node_iter(self.root()).collect();
        let old_cursor_path: Path = self.current_cursor_path.clone();

        // Unwrap is safe because `nodes_to_clone` must always contain at least the root
        let mut reverse_node_iter = nodes_to_clone.iter().copied().rev();
        let cursor = reverse_node_iter.next().unwrap();
        // Unwrapping in the closure is safe, because if the cursor does have a parent, then the
        // cursor_path must have at least one element
        let parent_and_index = reverse_node_iter
            .next()
            .map(|node| (node, old_cursor_path.last().unwrap()));

        /* PERFORM THE EDIT */

        let (new_node, edit_location, success) = edit_func(self, parent_and_index, cursor)?;
        let steps_above_cursor = edit_location.steps_above_cursor();

        /* CLONE ALL THE PARENT NODES TO GET A NEW ROOT */

        // Because AST nodes are immutable, we make changes to nodes by entirely cloning the path
        // down to the node under the cursor.  We do this starting at the node under the cursor and
        // work our way up parent by parent until we reach the root of the tree.  At that point,
        // this node becomes the root of the new tree.
        let mut node = self.arena.alloc(new_node);
        // Iterate backwards over the child indices and the nodes, whilst cloning the tree and
        // replacing the correct child reference to point to the newly created node.
        for (n, child_index) in nodes_to_clone
            .iter()
            .rev()
            .skip(1)
            .zip(old_cursor_path.iter().rev())
            .skip(steps_above_cursor)
        {
            let mut cloned_node = (*n).clone();
            cloned_node.replace_child(*child_index, node);
            node = self.arena.alloc(cloned_node);
        }

        /* UPDATE THE HISTORY */

        // Remove future trees from the history vector so that the currently 'checked-out' tree is
        // the most recent tree in the history.
        while self.history_index < self.root_history.len() - 1 {
            // TODO: Deallocate the tree so that we don't get a 'memory leak'
            self.root_history.pop();
        }
        // At this point, `node` contains a reference to the root of the new tree, so we just add
        // this to the history, along with the cursor path.

        log::debug!("current_cursor_path {:?}", self.current_cursor_path);
        self.root_history.push(Snapshot::new(
            old_cursor_path.clone(),
            node,
            self.current_cursor_path.clone(),
        ));
        // Move the history index on by one so that we are pointing at the latest change
        self.history_index = self.root_history.len() - 1;

        /* RETURN SUCCESS */
        Ok(success)
    }

    /// Replaces the current cursor with a node represented by `c`
    pub fn replace_cursor(
        &mut self,
        prefix_count: usize,
        insertable: Insertable,
    ) -> EditResult<Node::Class> {
        let (node_count, class) = match insertable {
            Insertable::CountedNode(count, c) => (
                count,
                Node::Class::from_char(c).ok_or(EditErr::CharNotANode(c))?,
            ),
        };
        // If `count` is 0, then the replacement is exactly equivalent to deleting the cursor.
        //
        // Ideally, replacement should just be implemented as deletion followed by insertion (which
        // would fix at least one existing bug with replacement in JSON objects), but that is not
        // possible in the current architecture because nodes like Json::Field cannot have their
        // children deleted.
        if node_count == 0 {
            self.delete_cursor(prefix_count)?;
            return Ok(EditSuccess::Replace(class));
        }

        // check if on the root
        // get current node's parent
        if prefix_count != 1 {
            if let (_, Some(parent)) = self.cursor_and_parent() {
                // Do boundary check
                let max_index = parent.children().len() - 1;
                // we can unwrap current_cursor_path can't be empty
                let current_child_index = self.current_cursor_path.last().unwrap();
                if current_child_index + prefix_count > max_index {
                    return Err(EditErr::ReplaceError {
                        current_child_index,
                        last_child_index: max_index,
                        node_count: prefix_count,
                    });
                }
            };
        }

        self.perform_edit(
            |this: &mut Self,
             _parent_and_index: Option<(&'arena Node, usize)>,
             cursor: &'arena Node| {
                // Early return if the `class` can't go in the cursor's location
                match _parent_and_index {
                    Some((parent, _cursor_index)) => {
                        let mut cloned_parent = parent.clone();
                        // We can unwrap here, because we know that the cursor is not at the
                        // root and therefore there is at least one segment of the Path.
                        let next_cursor_index = this.current_cursor_path.last_mut().unwrap();
                        // Loop over the prefix count, so that the correct number of nodes get
                        // replaced
                        for _ in 0..prefix_count {
                            // Each time a node gets replaced, replace it with the nodes specified
                            // by the Insertable
                            for j in 0..node_count {
                                let insert_index = *next_cursor_index + j;
                                // Check that the new node would be valid in the insert location,
                                // and return if so
                                if !cloned_parent.is_valid_child(insert_index, class) {
                                    return Err(EditErr::CannotBeChild {
                                        class,
                                        parent_name: parent.display_name(),
                                    });
                                }
                                let new_node = this.arena.alloc(Node::from_class(class));
                                // Because of the short-circuit deletion rule, we know that there
                                // must be at least one node to insert.  Therefore, we can use the
                                // first of these to replace the cursor and treat the rest as
                                // insertions.
                                if j == 0 {
                                    cloned_parent.replace_child(insert_index, new_node);
                                } else {
                                    cloned_parent.insert_child(
                                        new_node,
                                        this.arena,
                                        insert_index,
                                    )?;
                                }
                            }
                            // Move the cursor to **one past** the last node.  This is so that the
                            // next loop iteration starts replacing the next node, and this effect
                            // is corrected by subtracting one after the loop.
                            *next_cursor_index += node_count;
                        }
                        // This will not underflow unless node_count == 0, in which case the
                        // delete short-circuit would stop this code executing
                        *next_cursor_index -= 1;
                        Ok((
                            cloned_parent,
                            EditLocation::Parent,
                            EditSuccess::Replace(class),
                        ))
                    }
                    None => {
                        match (prefix_count * node_count, cursor.is_valid_root(class)) {
                            // This path is unreachable because its condition would trigger the
                            // short-circuiting call to delete
                            (0, _) => unreachable!(),
                            // If we're replacing the root with exactly 1 invalid node, then that's
                            // not OK
                            (1, false) => Err(EditErr::CannotBeRoot(class)),
                            // If we're replacing the root with exactly 1 valid node then it's OK
                            // and we do the replacement
                            (1, true) => Ok((
                                Node::from_class(class),
                                EditLocation::Cursor,
                                EditSuccess::Replace(class),
                            )),
                            // If we're replacing the root with more than 1 node, then this is
                            // equivalent to adding siblings to the root
                            _ => Err(EditErr::AddSiblingToRoot),
                        }
                    }
                }
            },
        )
    }

    /// Updates the internal state so that the tree now contains `new_node` inserted as the last
    /// child of the selected node.  Also moves the cursor so that the new node is selected.
    pub fn insert_child(
        &mut self,
        prefix_count: usize,
        insertable: Insertable,
    ) -> EditResult<Node::Class> {
        let (node_count, class) = match insertable {
            Insertable::CountedNode(count, c) => (
                count,
                Node::Class::from_char(c).ok_or(EditErr::CharNotANode(c))?,
            ),
        };
        let count = prefix_count * node_count;
        // If the count is 0, do nothing and exit
        if count == 0 {
            return Err(EditErr::NoNodesToInsert);
        }
        self.perform_edit(
            |this: &mut Self,
             _parent_and_index: Option<(&'arena Node, usize)>,
             cursor: &'arena Node| {
                log::debug!("Inserting '{}' as a new child.", class.to_char());
                // Clone the node that currently is the cursor, and add the new nodes to the end of
                // the child list
                let mut cloned_cursor = cursor.clone();
                // Add `count` children to the cursor
                for _ in 0..count {
                    // Validate the tree at every step
                    if !cursor.is_valid_child(cursor.children().len(), class) {
                        log::debug!("New node could not be a valid child of the cursor");
                        // Short circuit if `c` couldn't be a valid child of the cursor
                        return Err(EditErr::CannotBeChild {
                            class,
                            parent_name: cursor.display_name(),
                        });
                    }
                    // Add the new child to the children of the cloned cursor
                    cloned_cursor.insert_child(
                        this.arena.alloc(Node::from_class(class)),
                        this.arena,
                        cloned_cursor.children().len(),
                    )?;
                }
                // Move the cursor to the last added child
                this.current_cursor_path
                    .push(cloned_cursor.children().len() - 1);
                // Return success
                Ok((
                    cloned_cursor,
                    EditLocation::Cursor,
                    EditSuccess::InsertChild(class),
                ))
            },
        )
    }

    /// Updates the internal state so that the tree now contains `new_node` inserted as the first
    /// child of the selected node.  Also moves the cursor so that the new node is selected.
    pub fn insert_next_to_cursor(
        &mut self,
        prefix_count: usize,
        insertable: Insertable,
        side: Side,
    ) -> EditResult<Node::Class> {
        let (second_count, class) = match insertable {
            Insertable::CountedNode(count, c) => (
                count,
                Node::Class::from_char(c).ok_or(EditErr::CharNotANode(c))?,
            ),
        };
        // For inserting next to the cursor, we can simply multiply the two counts together to form
        // one single count
        let count = prefix_count * second_count;
        self.perform_edit(
            |this: &mut Self,
             parent_and_index: Option<(&'arena Node, usize)>,
             _cursor: &'arena Node| {
                // Find (and cache) the parent of the cursor.  If the parent of the cursor doesn't
                // exist, the cursor must be the root and we can't insert a node next to the root.
                let (parent, cursor_index) = parent_and_index.ok_or(EditErr::AddSiblingToRoot)?;
                // Calculate the index of the first child
                let insert_start_index = cursor_index
                    + match side {
                        Side::Prev => 0,
                        Side::Next => 1,
                    };
                // Clone the parent, and insert the new nodes to it one by one
                let mut cloned_parent = parent.clone();
                for i in 0..count {
                    let insert_index = insert_start_index + i;
                    // Short circuit if not an insertable char
                    if !parent.is_valid_child(insert_index, class) {
                        return Err(EditErr::CannotBeChild {
                            class,
                            parent_name: parent.display_name(),
                        });
                    }
                    // Add the new child to the children of the cloned cursor
                    cloned_parent.insert_child(
                        this.arena.alloc(Node::from_class(class)),
                        this.arena,
                        insert_index,
                    )?;
                }

                // Move the cursor to the last inserted node.  We can unwrap it here, because
                // inserting siblings to the root would cause an error
                *this.current_cursor_path.last_mut().unwrap() = insert_start_index + count - 1;
                Ok((
                    cloned_parent,
                    EditLocation::Parent,
                    EditSuccess::InsertNextToCursor { side, class },
                ))
            },
        )
    }

    /// Deletes up to `count` nodes after the cursor
    pub fn delete_cursor(&mut self, count: usize) -> EditResult<Node::Class> {
        self.perform_edit(
            |this: &mut Self,
             parent_and_index: Option<(&'arena Node, usize)>,
             cursor: &'arena Node| {
                // Find (and cache) the parent of the cursor.  If the parent of the cursor doesn't
                // exist, the cursor must be the root and we can't delete the root.
                let (parent, cursor_index) = parent_and_index.ok_or(EditErr::DeletingRoot)?;
                // Cache the name of the cursor **before** it gets deleted
                let deleted_node_name = cursor.display_name();

                let mut cloned_parent = parent.clone();
                // Delete the node under the cursor `count` many times, or until we run off the end
                // of the children
                for _ in 0..count {
                    let res = cloned_parent.delete_child(cursor_index);
                    // If we've run off the end of the children, this is not an error - we just
                    // break the loop and stop
                    if let Err(ast::DeleteError::IndexOutOfRange { .. }) = res {
                        break;
                    }
                    // Any other errors are hard errors, so we should stop in those cases
                    res?;
                }

                let new_parents_child_count = cloned_parent.children().len();
                if new_parents_child_count == 0 {
                    // If we remove the only child of a node then we move the cursor up
                    this.current_cursor_path.pop();
                } else if cursor_index == new_parents_child_count {
                    // If we deleted the last child of a node (and this isn't the last child), we
                    // move the cursor back by one.  We can unwrap here because we know we aren't
                    // removing the root
                    *this.current_cursor_path.last_mut().unwrap() -= 1;
                }

                Ok((
                    cloned_parent,
                    EditLocation::Parent,
                    EditSuccess::Delete {
                        name: deleted_node_name,
                    },
                ))
            },
        )
    }

    /* DISPLAY METHODS */

    /// Build the text representation of the current tree into the given [`String`]
    pub fn write_text(&self, string: &mut String, format: &Node::FormatStyle) {
        self.root().write_text(string, format);
    }

    /// Build and return a [`String`] of the current tree
    pub fn to_text(&self, format: &Node::FormatStyle) -> String {
        let mut s = String::new();
        self.write_text(&mut s, format);
        s
    }

    ///  Generate `.dot` code of the internal state of the `Dag`
    pub fn to_dot_code(&self) -> String {
        /// Helper function that recursively builds dot code for the entire subtree of a given node
        fn add_to_graph<'arena, Node: Ast<'arena>>(
            node: &'arena Node,
            digraph_edges: &mut String,
            hmap_nodes: &mut HashMap<usize, String>,
        ) {
            let name = node as *const Node as usize;
            if hmap_nodes.get(&name).is_some() {
                return;
            }
            hmap_nodes.insert(
                name,
                format!("node{} [label={:?}]\n", name, node.debug_name()),
            );

            if !node.children().is_empty() {
                for &child in node.children() {
                    add_to_graph(child, digraph_edges, hmap_nodes);
                }

                let edge = format!("node{} -> ", name);
                digraph_edges.push_str(&edge);

                for i in 0..node.children().len() {
                    let child_name = node.children()[i] as *const Node as usize;
                    if i != node.children().len() - 1 {
                        digraph_edges.push_str(&format!("node{}, ", child_name));
                    } else {
                        digraph_edges.push_str(&format!("node{}", child_name));
                    }
                }
                digraph_edges.push('\n');
            }
        }

        let mut hmap_nodes = HashMap::<usize, String>::new();
        let mut dot_buffer = "digraph G {\nnode [ordering=out]\n".to_owned();
        let mut digraph_edges = "\n".to_owned();
        let digraph_tail = "\n}";

        for snapshot in &self.root_history {
            add_to_graph(snapshot.root, &mut digraph_edges, &mut hmap_nodes);
        }
        for value in hmap_nodes.values() {
            dot_buffer.push_str(value);
        }
        dot_buffer.push('\n');

        dot_buffer.push_str(&digraph_edges);
        dot_buffer.push_str(digraph_tail);

        dot_buffer
    }
}

#[cfg(test)]
mod tests {
    use super::{Dag, EditErr, EditResult, EditSuccess, Insertable};
    use crate::arena::Arena;
    use crate::ast::json::{add_value_to_arena, Class, Json, JsonFormat};
    use crate::ast::Ast;
    use crate::core::{Direction, Path, Side};
    use crate::editor::normal_mode::Action;

    use serde_json::{json, Value};

    /// Extension trait used to add the `execute_action` and `execute_action_once` methods to Dag
    /// (`execute_action` was removed but is incredibly helpful for unit testing).
    trait ExecuteAction {
        fn execute_action_once(&mut self, action: Action) -> EditResult<Class> {
            self.execute_action(1, action)
        }

        fn execute_action(&mut self, count: usize, action: Action) -> EditResult<Class>;
    }

    impl<'arena> ExecuteAction for Dag<'arena, Json<'arena>> {
        fn execute_action(&mut self, count: usize, action: Action) -> EditResult<Class> {
            match action {
                Action::Undo => self.undo(count),
                Action::Redo => self.redo(count),
                Action::MoveCursor(direction) => self.move_cursor(count, direction),
                Action::Replace(c) => self.replace_cursor(count, c),
                Action::InsertChild(c) => self.insert_child(count, c),
                Action::InsertBefore(c) => self.insert_next_to_cursor(count, c, Side::Prev),
                Action::InsertAfter(c) => self.insert_next_to_cursor(count, c, Side::Next),
                Action::Delete => self.delete_cursor(count),
                Action::Quit | Action::Write => unreachable!(),
            }
        }
    }

    fn run_test_ok_count(
        start_tree: Value,
        start_cursor_location: Path,
        count: usize,
        action: Action,
        expected_edit_success: EditSuccess<Class>,
        expected_tree: Value,
        expected_cursor_location: Path,
    ) {
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree, &arena);
        let mut dag = Dag::new(&arena, root, start_cursor_location);

        assert_eq!(
            Ok(expected_edit_success),
            dag.execute_action(count, action),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), expected_tree, "Not equal in tree.");
        assert_eq!(
            expected_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );
    }

    fn run_test_ok(
        start_tree: Value,
        start_cursor_location: Path,
        action: Action,
        expected_edit_success: EditSuccess<Class>,
        expected_tree: Value,
        expected_cursor_location: Path,
    ) {
        run_test_ok_count(
            start_tree,
            start_cursor_location,
            1,
            action,
            expected_edit_success,
            expected_tree,
            expected_cursor_location,
        );
    }

    /// Helper function for successfully moving the cursor the full specified distance
    fn test_movement(
        start_tree: Value,
        start_cursor_location: Path,
        count: usize,
        direction: Direction,
        expected_cursor_location: Path,
    ) {
        test_capped_movement(
            start_tree,
            start_cursor_location,
            count,
            direction,
            count,
            expected_cursor_location,
        );
    }

    /// Helper function for when the specified distance is not necessarily the distance covered.
    fn test_capped_movement(
        start_tree: Value,
        start_cursor_location: Path,
        distance: usize,
        direction: Direction,
        actual_distance: usize,
        expected_cursor_location: Path,
    ) {
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, start_cursor_location);

        assert_eq!(
            Ok(EditSuccess::Move(actual_distance, direction)),
            dag.move_cursor(distance, direction),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree.");
        assert_eq!(
            expected_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );
    }

    fn run_test_err_count(
        start_tree: Value,
        start_cursor_location: Path,
        count: usize,
        action: Action,
        expected_edit_err: EditErr<Class>,
    ) {
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, start_cursor_location.clone());

        assert_eq!(
            Err(expected_edit_err),
            dag.execute_action(count, action),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree.");
        assert_eq!(
            start_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );
    }

    fn run_test_err(
        start_tree: Value,
        start_cursor_location: Path,
        action: Action,
        expected_edit_err: EditErr<Class>,
    ) {
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, start_cursor_location.clone());

        assert_eq!(
            Err(expected_edit_err),
            dag.execute_action_once(action),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree.");
        assert_eq!(
            start_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );
    }

    /* REPLACE */

    /// Helper function specifically to run a replace test
    fn test_single_replace_ok(
        start_tree: Value,
        cursor: Path,
        node: char,
        class: Class,
        end_tree: Value,
    ) {
        run_test_ok(
            start_tree,
            cursor.clone(),
            Action::Replace(Insertable::CountedNode(1, node)),
            EditSuccess::Replace(class),
            end_tree,
            cursor,
        );
    }

    /// Tests the behaviour of replacing with one single node (e.g. `rt` replacing the cursor with
    /// just `true`).
    #[test]
    fn replace_single() {
        // Replace root with one valid char
        test_single_replace_ok(
            json!([true, null]),
            Path::root(),
            'f',
            Class::False,
            json!(false),
        );
        // Replace the root with a char this doesn't correspond to a node
        run_test_err(
            json!(false),
            Path::root(),
            Action::Replace(Insertable::CountedNode(1, 'm')),
            EditErr::CharNotANode('m'),
        );
        // It doesn't matter how big the branch you're replacing is
        test_single_replace_ok(
            json!([true, false]),
            Path::root(),
            'n',
            Class::Null,
            json!(null),
        );
        // Explicitly replacing just the RHS of fields with one node should just be fine
        test_single_replace_ok(
            json!({"key-1": false, "key-2": true}),
            Path::from_vec(vec![1, 1]),
            'n',
            Class::Null,
            json!({"key-1": false, "key-2": null}),
        );
        // Replacing the key with a single string is fine (but clears the key's string)
        test_single_replace_ok(
            json!({"key-1": false, "key-2": true}),
            Path::from_vec(vec![1, 0]),
            's',
            Class::Str,
            json!({"key-1": false, "": true}),
        );
        // Replacing a key with an invalid node is not OK
        run_test_err(
            json!({"key-1": false, "key-2": true}),
            Path::from_vec(vec![1, 0]),
            Action::Replace(Insertable::CountedNode(1, 'n')),
            EditErr::CannotBeChild {
                class: Class::Null,
                parent_name: ("field".to_string()),
            },
        );
    }

    /// This tests the behaviour of inserting using a count specifier with the node (i.e. `r3a`).
    /// In this example, it should have the effect of deleting the cursor and then inserting 3
    /// empty arrays in its place.
    #[test]
    fn replace_nodecounts() {
        // Replace root with too many nodes, of an invalid type
        run_test_err(
            json!(false),
            Path::root(),
            Action::Replace(Insertable::CountedNode(3, 'm')),
            EditErr::CharNotANode('m'),
        );
        // Replace root with too many nodes of a valid type
        run_test_err(
            json!([{"key": "value"}, true]),
            Path::root(),
            Action::Replace(Insertable::CountedNode(3, 's')),
            EditErr::AddSiblingToRoot,
        );
        // Replace root with no nodes
        run_test_err(
            json!([true, false, null]),
            Path::root(),
            Action::Replace(Insertable::CountedNode(0, 's')),
            EditErr::DeletingRoot,
        );
        // Replacing with 0 nodes should be the same as deletion
        run_test_ok(
            json!([true, []]),
            Path::from_vec(vec![1]),
            Action::Replace(Insertable::CountedNode(0, 'n')),
            EditSuccess::Replace(Class::Null),
            json!([true]),
            Path::from_vec(vec![0]),
        );
        // Replacing with exactly one valid node
        run_test_ok(
            json!([true, []]),
            Path::from_vec(vec![1]),
            Action::Replace(Insertable::CountedNode(1, 'n')),
            EditSuccess::Replace(Class::Null),
            json!([true, null]),
            Path::from_vec(vec![1]),
        );
        // Replacing with multiple valid nodes should replace the cursor with several nodes
        // (perhaps not the best action).
        run_test_ok(
            json!([true, []]),
            Path::from_vec(vec![1]),
            Action::Replace(Insertable::CountedNode(4, 'n')),
            EditSuccess::Replace(Class::Null),
            json!([true, null, null, null]),
            Path::from_vec(vec![4]),
        );
        // Replacing a key with too many strings is not OK
        run_test_err(
            json!({"key-1": true, "key-2": false}),
            Path::from_vec(vec![1, 0]),
            Action::Replace(Insertable::CountedNode(3, 'n')),
            EditErr::CannotBeChild {
                class: Class::Null,
                parent_name: ("field".to_string()),
            },
        );
    }

    /// This tests the behaviour of putting counts **in front** of the replace: e.g. `3rt` will
    /// replace the 3 nodes starting with the cursor with `true`:
    /// `[<false>, "", null, null]` goes to `[true, true, <true>, null]`
    #[test]
    fn replace_precount() {
        // `3rt` causes `[<true>, [], "", null]` going to `[true, true, <true>, null]`
        run_test_ok_count(
            json!([true, [], "", null]),
            Path::from_vec(vec![0]),
            3,
            Action::Replace(Insertable::CountedNode(1, 't')),
            EditSuccess::Replace(Class::True),
            json!([true, true, true, null]),
            Path::from_vec(vec![2]),
        );
        // `2r2t` causes `[<true>, [], "", null]` going to `[true, true, true, <true>, "", null]`
        run_test_ok_count(
            json!([true, [], "", null]),
            Path::from_vec(vec![0]),
            2,
            Action::Replace(Insertable::CountedNode(2, 't')),
            EditSuccess::Replace(Class::True),
            json!([true, true, true, true, "", null]),
            Path::from_vec(vec![3]),
        );
        // `2r2t` causes the root to gain siblings, which is not allowed
        run_test_err_count(
            json!([true, [], "", null]),
            Path::root(),
            2,
            Action::Replace(Insertable::CountedNode(2, 't')),
            EditErr::AddSiblingToRoot,
        );
    }

    /* DELETE */

    #[test]
    fn delete_root_err() {
        run_test_err(
            json!([]),
            Path::root(),
            Action::Delete,
            EditErr::DeletingRoot,
        );

        // dag level==1
        run_test_err(
            json!([[], true]),
            Path::root(),
            Action::Delete,
            EditErr::DeletingRoot,
        );
    }

    #[test]
    fn delete_cursor_move() {
        // If the cursor has later siblings, then deletion won't move the cursor
        run_test_ok(
            json!([true, []]),
            Path::from_vec(vec![0]),
            Action::Delete,
            EditSuccess::Delete {
                name: "true".to_string(),
            },
            json!([[]]),
            Path::from_vec(vec![0]),
        );
        // Cursor should move backwards if we deleted the highest-indexed sibling
        run_test_ok(
            json!([true, []]),
            Path::from_vec(vec![1]),
            Action::Delete,
            EditSuccess::Delete {
                name: "array".to_string(),
            },
            json!([true]),
            Path::from_vec(vec![0]),
        );
        // Cursor should move up a level if we've deleted the last child
        run_test_ok(
            json!([true]),
            Path::from_vec(vec![0]),
            Action::Delete,
            EditSuccess::Delete {
                name: "true".to_string(),
            },
            json!([]),
            Path::root(),
        );
    }

    #[test]
    fn delete_counts() {
        // Deleting all of the children in one shot should move the cursor up
        run_test_ok_count(
            json!([true, []]),
            Path::from_vec(vec![0]),
            2,
            Action::Delete,
            EditSuccess::Delete {
                name: "true".to_string(),
            },
            json!([[]]),
            Path::root(),
        );
        // Test deleting exactly the right number of nodes out of the middle of an array
        run_test_ok_count(
            json!([true, null, false, []]),
            Path::from_vec(vec![1]),
            2,
            Action::Delete,
            EditSuccess::Delete {
                name: "null".to_string(),
            },
            json!([true, []]),
            Path::from_vec(vec![1]),
        );
        // Trying to delete more nodes than there are siblings after the cursor is not an error,
        // but it should not continue deleting backwards (this makes `5x` subtly different from
        // `xxxxx`).
        run_test_ok_count(
            json!([true, null, false, []]),
            Path::from_vec(vec![2]),
            4,
            Action::Delete,
            EditSuccess::Delete {
                name: "false".to_string(),
            },
            json!([true, null]),
            Path::from_vec(vec![1]),
        );
    }

    /* MOVEMENT */

    #[test]
    fn move_sideways() {
        // move to previous sibling node of root
        run_test_err(
            json!([]),
            Path::root(),
            Action::MoveCursor(Direction::Prev),
            EditErr::MoveToSiblingOfRoot,
        );
        // move to next sibling node of root
        run_test_err(
            json!([]),
            Path::root(),
            Action::MoveCursor(Direction::Next),
            EditErr::MoveToSiblingOfRoot,
        );
        // move sideways in an array, not reaching the end
        test_movement(
            json!([true, null, false]),
            Path::from_vec(vec![0]),
            1,
            Direction::Next,
            Path::from_vec(vec![1]),
        );
        // move twice sideways in an array, just reaching the end
        test_movement(
            json!([true, null, false]),
            Path::from_vec(vec![0]),
            2,
            Direction::Next,
            Path::from_vec(vec![2]),
        );
        // move twice sideways in an array, just overshooting the end
        test_capped_movement(
            json!([true, null, false]),
            Path::from_vec(vec![0]),
            5,
            Direction::Next,
            2,
            Path::from_vec(vec![2]),
        );
    }

    #[test]
    fn move_down() {
        // move to nonexistent child node of root
        test_capped_movement(json!([]), Path::root(), 1, Direction::Down, 0, Path::root());
        // Move down the tree once
        test_movement(
            json!([true, []]),
            Path::root(),
            1,
            Direction::Down,
            Path::from_vec(vec![0]),
        );
        // Move down the tree to a field.  JSON is '{"key": null}'
        test_movement(
            json!({ "key": null }),
            Path::root(),
            1,
            Direction::Down,
            Path::from_vec(vec![0; 1]),
        );
        // Move down the tree multiple times
        test_movement(
            json!([[{ "key": null }, true], true, {}]),
            Path::root(),
            4,
            Direction::Down,
            Path::from_vec(vec![0; 4]),
        );
        // Move down the tree multiple times, but not as many times as specified.  JSON is
        test_capped_movement(
            json!([[true, { "key": null }], true, {}]),
            Path::root(),
            4,
            Direction::Down,
            2,
            Path::from_vec(vec![0; 2]),
        );
    }

    #[test]
    fn move_up() {
        // move to parent node of root
        test_capped_movement(json!([]), Path::root(), 1, Direction::Up, 0, Path::root());
        // move to root from child
        test_movement(
            json!([false, true]),
            Path::from_vec(vec![1]),
            1,
            Direction::Up,
            Path::root(),
        );
        // move from child not to root
        test_movement(
            json!([true, [false, null]]),
            Path::from_vec(vec![1, 0]),
            1,
            Direction::Up,
            Path::from_vec(vec![1]),
        );
        // move from child to root, multiple times
        test_movement(
            json!([true, [false, null]]),
            Path::from_vec(vec![1, 0]),
            2,
            Direction::Up,
            Path::root(),
        );
        // move to root from child, multiple times (but only 2 of 3 moves are actually possible)
        test_capped_movement(
            json!([true, [false, null]]),
            Path::from_vec(vec![1, 0]),
            3,
            Direction::Up,
            2,
            Path::root(),
        );
    }

    /* UNDO/REDO */

    #[test]
    fn undo_root() {
        let start_tree = json!([]);
        let start_cursor_location = Path::root();
        let end_tree = json!(false);
        let end_cursor_location = Path::root();

        // Initialise the Dag with the `start_tree`
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, start_cursor_location.clone());

        // We start with an empty Json array (`[]`), and we replace it with `false`
        assert_eq!(
            Ok(EditSuccess::Replace(Class::False)),
            dag.replace_cursor(1, Insertable::CountedNode(1, 'f')),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), end_tree, "Not equal in tree.");
        assert_eq!(
            end_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // Undo the change
        assert_eq!(
            Ok(EditSuccess::Undo),
            dag.undo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree.");
        assert_eq!(
            start_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // Dag level == 1
        let start_tree = json!([null, true, false]);
        let start_cursor_location = Path::root();
        // We move the cursor so we expect the cursor to move but no change to occur to the tree
        let end_cursor_location = Path::from_vec(vec![0]);

        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, start_cursor_location);

        assert_eq!(
            Ok(EditSuccess::Move(1, Direction::Down)),
            dag.move_cursor(1, Direction::Down),
            "Not equal in action result (move 0)."
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree (move 0).");
        assert_eq!(
            end_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location (move 0)."
        );

        // undo
        assert_eq!(
            Err(EditErr::NoChangesToUndo),
            dag.undo(1),
            "Not equal in action result (move 1)"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree (move 1).");
        assert_eq!(
            end_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location (move 1)."
        );
    }

    #[test]
    fn redo_root() {
        let start_tree = json!([]);
        let end_tree = json!({});

        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, Path::root());

        assert_eq!(
            Ok(EditSuccess::Replace(Class::Object)),
            dag.replace_cursor(1, Insertable::CountedNode(1, 'o')),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), end_tree, "Not equal in tree.");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // undo
        assert_eq!(
            Ok(EditSuccess::Undo),
            dag.undo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree.");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // redo
        assert_eq!(
            Ok(EditSuccess::Redo),
            dag.redo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), end_tree, "Not equal in tree.");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Not equal in cursor location."
        );

        //Dag level == 1
        let start_tree = json!([null, true, false]);
        let start_cursor_location = Path::root();
        let end_cursor_location = Path::from_vec(vec![0]);

        // Initialise a Dag with the cursor at the root
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, start_cursor_location);

        assert_eq!(
            Ok(EditSuccess::Move(1, Direction::Down)),
            dag.move_cursor(1, Direction::Down),
            "Not equal in action result (move 0)."
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree (move 0).");
        assert_eq!(
            end_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location (move 0)."
        );

        // undo
        assert_eq!(
            Err(EditErr::NoChangesToUndo),
            dag.undo(1),
            "Not equal in action result (move 1)."
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree (move 1).");
        assert_eq!(
            end_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location (move 1). "
        );

        // redo
        assert_eq!(
            Err(EditErr::NoChangesToRedo),
            dag.redo(1),
            "Not equal in action result (move 2)."
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree (move 2).");
        assert_eq!(
            end_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location (move 2)."
        );
    }

    #[test]
    fn undo_redo() {
        // The original snapshot of the tree
        let start_tree = json!([null, true, false]);
        let end_tree = json!(false);

        // Create and initialise Dag to test
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let mut dag = Dag::new(&arena, root, Path::root());

        // Step 1: Replace root with `false`
        println!("Inserting `false`");
        assert_eq!(
            Ok(EditSuccess::Replace(Class::False)),
            dag.replace_cursor(1, Insertable::CountedNode(1, 'f')),
            "Not equal in action result."
        );
        assert_eq!(*dag.root(), end_tree, "Not equal in tree.");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // Perform one undo.  This be successful, because it's undoing the replace-with-false
        println!("Performing first undo");
        assert_eq!(
            Ok(EditSuccess::Undo),
            dag.undo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree.");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // Perform another undo.  This won't be successful, because there's nothing to undo
        println!("Performing the 2nd undo");
        assert_eq!(
            Err(EditErr::NoChangesToUndo),
            dag.undo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Failed undo modified the tree");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Failed undo moved the cursor"
        );

        // Redo the change we undid (this should succeed)
        println!("Performing the 1st redo");
        assert_eq!(
            Ok(EditSuccess::Redo),
            dag.redo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), end_tree, "Not equal in tree.");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // Redo another time, but there are no changes to redo
        println!("Performing the 2nd redo");
        assert_eq!(
            Err(EditErr::NoChangesToRedo),
            dag.redo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), end_tree, "Not equal in tree.");
        assert_eq!(
            Path::root(),
            dag.current_cursor_path,
            "Not equal in cursor location."
        );
    }

    #[test]
    fn multiple_undo_redo() {
        // Step 0: Set up a Dag with an empty JSON array
        let tree_0 = json!([]);
        let arena: Arena<Json> = Arena::new();
        let mut dag = Dag::new(
            &arena,
            add_value_to_arena(tree_0.clone(), &arena),
            Path::root(),
        );

        /* Perform some actions on the tree */

        // Step 1: Insert two trues, so we end up with `[true, <true>]`
        let tree_1 = json!([true, true]);
        assert_eq!(
            dag.insert_child(1, Insertable::CountedNode(2, 't')),
            Ok(EditSuccess::InsertChild(Class::True))
        );
        // Move cursor back a step to `[<true>, true]` (this shouldn't contribute to the history)
        assert_eq!(
            dag.move_cursor(1, Direction::Prev),
            Ok(EditSuccess::Move(1, Direction::Prev))
        );
        // Step 2: Replace the cursor with an object: `[<{}>, true]`
        let tree_2 = json!([{}, true]);
        assert_eq!(
            dag.replace_cursor(1, Insertable::CountedNode(1, 'o')),
            Ok(EditSuccess::Replace(Class::Object))
        );
        // Step 3: Insert null into the object: `[{<"": null>}, true]`
        let tree_3 = json!([{ "": null }, true]);
        assert_eq!(
            dag.insert_child(1, Insertable::CountedNode(1, 'n')),
            Ok(EditSuccess::InsertChild(Class::Null))
        );
        // Move to the null: `[{"": <null>}, true]`
        assert_eq!(
            dag.move_cursor(1, Direction::Down),
            Ok(EditSuccess::Move(1, Direction::Down))
        );
        assert_eq!(
            dag.move_cursor(1, Direction::Next),
            Ok(EditSuccess::Move(1, Direction::Next))
        );
        // Step 4: Replace the null with false: `[{"": <false>}, true]`
        let tree_4 = json!([{"": false}, true]);
        assert_eq!(
            dag.replace_cursor(1, Insertable::CountedNode(1, 'f')),
            Ok(EditSuccess::Replace(Class::False))
        );
        // Move back to the field: `[{<"": false>}, true]`
        assert_eq!(
            dag.move_cursor(1, Direction::Up),
            Ok(EditSuccess::Move(1, Direction::Up))
        );
        // Step 5: Insert a string after the cursor: `[{"": false, <"": "">}, true]`.  This can't be
        // generated by the json! macro (because the two values have the same key), so we use
        // string comparison instead
        let tree_5_str = r#"[{"": false, "": ""}, true]"#;
        assert_eq!(
            dag.insert_next_to_cursor(1, Insertable::CountedNode(1, 's'), Side::Next),
            Ok(EditSuccess::InsertNextToCursor {
                side: Side::Next,
                class: Class::Str
            })
        );
        // Check that the tree is as we expect
        assert_eq!(dag.root().to_text(&JsonFormat::Compact), tree_5_str);
        // 5 - 3 = 2
        assert_eq!(dag.undo(3), Ok(EditSuccess::Undo));
        assert_eq!(*dag.root(), tree_2);
        // 2 + 2 = 4
        assert_eq!(dag.redo(2), Ok(EditSuccess::Redo));
        assert_eq!(*dag.root(), tree_4);
        // 2 + 5 caps out at 5
        assert_eq!(dag.redo(5), Ok(EditSuccess::Redo));
        assert_eq!(dag.root().to_text(&JsonFormat::Compact), tree_5_str);
        // 5 - 1 = 4
        assert_eq!(dag.undo(1), Ok(EditSuccess::Undo));
        assert_eq!(*dag.root(), tree_4);
        // 4 - 1 = 3
        assert_eq!(dag.undo(1), Ok(EditSuccess::Undo));
        assert_eq!(*dag.root(), tree_3);
        // 3 - 2 = 1
        assert_eq!(dag.undo(2), Ok(EditSuccess::Undo));
        assert_eq!(*dag.root(), tree_1);
        // 1 - 2 caps out at 0
        assert_eq!(dag.undo(2), Ok(EditSuccess::Undo));
        assert_eq!(*dag.root(), tree_0);
        // 0 + 5 = 5
        assert_eq!(dag.redo(5), Ok(EditSuccess::Redo));
        assert_eq!(dag.root().to_text(&JsonFormat::Compact), tree_5_str);
    }

    /* INSERT CHILD */

    #[test]
    fn insert_child_single() {
        run_test_ok(
            json!([[], true]),
            Path::from_vec(vec![0]),
            Action::InsertChild(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertChild(Class::False),
            json!([[false], true]),
            Path::from_vec(vec![0, 0]),
        );

        run_test_ok(
            json!([]),
            Path::root(),
            Action::InsertChild(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertChild(Class::False),
            json!([false]),
            Path::from_vec(vec![0]),
        );

        // Dag level == 1

        run_test_ok(
            json!([[], true]),
            Path::root(),
            Action::InsertChild(Insertable::CountedNode(1, 'n')),
            EditSuccess::InsertChild(Class::Null),
            json!([[], true, null]),
            Path::from_vec(vec![2]),
        )
    }

    #[test]
    fn insert_child_nodecount() {
        run_test_ok(
            json!([[], true]),
            Path::from_vec(vec![0]),
            Action::InsertChild(Insertable::CountedNode(3, 'f')),
            EditSuccess::InsertChild(Class::False),
            json!([[false, false, false], true]),
            Path::from_vec(vec![0, 2]),
        );

        run_test_ok(
            json!([]),
            Path::root(),
            Action::InsertChild(Insertable::CountedNode(2, 'f')),
            EditSuccess::InsertChild(Class::False),
            json!([false, false]),
            Path::from_vec(vec![1]),
        );

        // Dag level == 1

        run_test_err(
            json!([[], true]),
            Path::root(),
            Action::InsertChild(Insertable::CountedNode(0, 'n')),
            EditErr::NoNodesToInsert,
        )
    }

    #[test]
    fn insert_child_precount() {
        run_test_ok_count(
            json!([[], true]),
            Path::from_vec(vec![0]),
            3,
            Action::InsertChild(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertChild(Class::False),
            json!([[false, false, false], true]),
            Path::from_vec(vec![0, 2]),
        );

        run_test_ok_count(
            json!([[], true]),
            Path::from_vec(vec![0]),
            2,
            Action::InsertChild(Insertable::CountedNode(2, 'f')),
            EditSuccess::InsertChild(Class::False),
            json!([[false, false, false, false], true]),
            Path::from_vec(vec![0, 3]),
        );

        run_test_ok_count(
            json!([]),
            Path::root(),
            2,
            Action::InsertChild(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertChild(Class::False),
            json!([false, false]),
            Path::from_vec(vec![1]),
        );

        // Dag level == 1

        run_test_err_count(
            json!([[], true]),
            Path::root(),
            10,
            Action::InsertChild(Insertable::CountedNode(0, 'n')),
            EditErr::NoNodesToInsert,
        )
    }
    /* INSERT SIBLING */

    #[test]
    fn insert_after() {
        run_test_err(
            json!([]),
            Path::root(),
            Action::InsertAfter(Insertable::CountedNode(1, 'f')),
            EditErr::AddSiblingToRoot,
        );

        // tree level == 1
        run_test_err(
            json!([[], true]),
            Path::root(),
            Action::InsertAfter(Insertable::CountedNode(1, 'f')),
            EditErr::AddSiblingToRoot,
        );

        run_test_ok(
            json!([true, true]),
            Path::from_vec(vec![1]),
            Action::InsertAfter(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertNextToCursor {
                side: Side::Next,
                class: Class::False,
            },
            json!([true, true, false]),
            Path::from_vec(vec![2]),
        );

        // Dag level == 2
        run_test_ok(
            json!([[null, true], {"value": true}]),
            Path::from_vec(vec![1]),
            Action::InsertAfter(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertNextToCursor {
                side: Side::Next,
                class: Class::False,
            },
            json!([[null, true], {"value": true}, false]),
            Path::from_vec(vec![2]),
        );
    }

    #[test]
    fn insert_before() {
        run_test_err(
            json!([]),
            Path::root(),
            Action::InsertBefore(Insertable::CountedNode(1, 'f')),
            EditErr::AddSiblingToRoot,
        );

        // tree level == 1
        run_test_err(
            json!([[], true]),
            Path::root(),
            Action::InsertBefore(Insertable::CountedNode(1, 'f')),
            EditErr::AddSiblingToRoot,
        );

        run_test_ok(
            json!([[], true]),
            Path::from_vec(vec![0]),
            Action::InsertBefore(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertNextToCursor {
                side: Side::Prev,
                class: Class::False,
            },
            json!([false, [], true]),
            Path::from_vec(vec![0]),
        );

        // Dag level == 2
        run_test_ok(
            json!([[null, true], {"value": true}]),
            Path::from_vec(vec![1]),
            Action::InsertBefore(Insertable::CountedNode(1, 'f')),
            EditSuccess::InsertNextToCursor {
                side: Side::Prev,
                class: Class::False,
            },
            json!([[null, true], false, {"value": true}]),
            Path::from_vec(vec![1]),
        );
    }

    #[test]
    // This is the test cases for issue 27
    fn level_2_undo() {
        // The original snapshot of the tree

        let start_tree = json!([null, {"key": true}, false]);

        let expected_tree = json!([null, {}, false]);

        // Create and initialise Dag to test
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree.clone(), &arena);
        let start_cursor_location = Path::from_vec(vec![1, 0]);
        let expected_cursor_location = Path::from_vec(vec![1]);
        let mut dag = Dag::new(&arena, root, start_cursor_location.clone());

        // Step 1: Delete TestJson::object's child
        println!("Delete `key-value` pair");
        assert_eq!(
            Ok(EditSuccess::Delete {
                name: "field".to_string()
            }),
            dag.delete_cursor(1),
            "Not equal in action result."
        );
        assert_eq!(*dag.root(), expected_tree, "Not equal in tree.");
        assert_eq!(
            expected_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );

        // Perform one undo.
        println!("Performing undo");
        assert_eq!(
            Ok(EditSuccess::Undo),
            dag.undo(1),
            "Not equal in action result"
        );
        assert_eq!(*dag.root(), start_tree, "Not equal in tree.");
        assert_eq!(
            start_cursor_location, dag.current_cursor_path,
            "Not equal in cursor location."
        );
    }

    #[test]
    // This is the test case for issue 88
    fn move_cursor_to_previous_child() {
        let start_tree = json!([null, {"key": true}, false]);

        // Create and initialise Dag to test
        let arena: Arena<Json> = Arena::new();
        let root = add_value_to_arena(start_tree, &arena);

        // Create and initialise Dag to test
        let start_cursor_location = Path::from_vec(vec![]);
        let expected_cursor_location_1 = Path::from_vec(vec![0]);
        let expected_cursor_location_2 = Path::from_vec(vec![1]);
        let expected_cursor_location_3 = Path::from_vec(vec![]);
        let expected_cursor_location_4 = Path::from_vec(vec![1]);
        let expected_cursor_location_5 = Path::from_vec(vec![1, 0]);

        let mut dag = Dag::new(&arena, root, start_cursor_location);

        let ok_1 = dag.move_cursor(1, Direction::Down);
        assert_eq!(dag.current_cursor_path, expected_cursor_location_1);
        assert_eq!(ok_1, Ok(EditSuccess::Move(1, Direction::Down)));
        let ok_2 = dag.move_cursor(1, Direction::Next);
        assert_eq!(dag.current_cursor_path, expected_cursor_location_2);
        assert_eq!(ok_2, Ok(EditSuccess::Move(1, Direction::Next)));
        let ok_3 = dag.move_cursor(1, Direction::Up);
        assert_eq!(dag.current_cursor_path, expected_cursor_location_3);
        assert_eq!(ok_3, Ok(EditSuccess::Move(1, Direction::Up)));
        let ok_4 = dag.move_cursor(1, Direction::Down);
        assert_eq!(dag.current_cursor_path, expected_cursor_location_4);
        assert_eq!(ok_4, Ok(EditSuccess::Move(1, Direction::Down)));
        let ok_5 = dag.move_cursor(1, Direction::Down);
        assert_eq!(dag.current_cursor_path, expected_cursor_location_5);
        assert_eq!(ok_5, Ok(EditSuccess::Move(1, Direction::Down)));
    }

    /// Regression tests for previous bugs
    mod reg {
        use super::*;

        /// This is a regression test for issue #51 (fixed in PR #53), where Sapling crashes if:
        /// 1. The user deletes the cursor when the cursor is the last child of its parent
        /// 2. The user undoes this edit
        /// 3. The user redoes this edit
        #[test]
        fn i_51_delete_cursor_crash_bug() {
            // Create and initialise Dag to test (start with Json `[null]` with the cursor selecting
            // the `null`)
            let arena: Arena<Json> = Arena::new();
            let root = add_value_to_arena(json!([null]), &arena);
            let mut dag = Dag::new(&arena, root, Path::from_vec(vec![0]));

            // Delete the node under the cursor, causing the cursor to move to the root
            assert_eq!(
                Ok(EditSuccess::Delete {
                    name: "null".to_string()
                }),
                dag.delete_cursor(1),
            );
            assert_eq!(dag.current_cursor_path, Path::root());

            // Undo this change, causing the cursor to move back to `null`
            assert_eq!(Ok(EditSuccess::Undo), dag.undo(1));

            // Redo the change.  It's not really important what the tree is here, so long as the Dag
            // doesn't panic when the cursor is generated
            assert_eq!(Ok(EditSuccess::Redo), dag.redo(1));

            let _cursor = dag.cursor();
        }

        /// This is a regression test for issue #68, where Sapling crashes if an invalid char is
        /// used to insert into any node
        #[test]
        fn i_68_invalid_insert_crash() {
            // Create and initialise Dag to test (start with JSON `[null]` with the cursor selecting
            // the `null`)
            let arena: Arena<Json> = Arena::new();
            let root = add_value_to_arena(json!([null]), &arena);
            let mut dag = Dag::new(&arena, root, Path::root());

            // Inserting an invalid char into the array should error gracefully
            assert_eq!(
                Err(EditErr::CharNotANode('x')),
                dag.insert_child(1, Insertable::CountedNode(1, 'x'))
            );

            // Move the cursor to the 'null'
            assert_eq!(
                Ok(EditSuccess::Move(1, Direction::Down)),
                dag.move_cursor(1, Direction::Down)
            );

            // Inserting an invalid char into the array should error gracefully
            assert_eq!(
                Err(EditErr::CharNotANode('x')),
                dag.insert_child(1, Insertable::CountedNode(1, 'x'))
            );
        }

        /// This is a regression test for issue #68, where Sapling crashes if an invalid char is
        /// used to insert into any node
        #[test]
        fn i_68_invalid_replace_crash() {
            // Create and initialise Dag to test (start with JSON `[null]` with the cursor selecting
            // the `null`)
            let arena: Arena<Json> = Arena::new();
            let root = add_value_to_arena(json!([null]), &arena);
            let mut dag = Dag::new(&arena, root, Path::root());

            // Inserting an invalid char into the array should error gracefully
            assert_eq!(
                Err(EditErr::CharNotANode('x')),
                dag.replace_cursor(1, Insertable::CountedNode(1, 'x'))
            );

            // Move the cursor to the 'null'
            assert_eq!(
                Ok(EditSuccess::Move(1, Direction::Down)),
                dag.move_cursor(1, Direction::Down)
            );

            // Inserting an invalid char into the array should error gracefully
            assert_eq!(
                Err(EditErr::CharNotANode('x')),
                dag.replace_cursor(1, Insertable::CountedNode(1, 'x'))
            );
        }

        /// This is a regression test for issue #78, where directly replacing a field results in an
        /// invalid tree.
        #[test]
        #[ignore]
        fn i_78_incorrect_field_replace() {
            run_test_ok(
                // We are selecting the field, not the contained value
                json!({"key": true}),
                Path::from_vec(vec![0]),
                Action::Replace(Insertable::CountedNode(1, 'f')),
                EditSuccess::Replace(Class::False),
                // We'd **expect** a new field to implicitly be created, but that is not the case.
                // Instead the resulting JSON will be `{false}`, which is invalid
                json!({"": false}),
                Path::from_vec(vec![0]),
            );
        }

        /// this is a regression test for pull request #81.
        #[test]
        fn pr_81_undo_add_child_crash() {
            let arena: Arena<Json> = Arena::new();
            let root = add_value_to_arena(json!([null]), &arena);
            let mut dag = Dag::new(&arena, root, Path::from_vec(vec![0]));

            // Replace the root with an array
            dag.delete_cursor(1).unwrap();
            // Add a new child to the cursor/root
            dag.insert_child(1, Insertable::CountedNode(1, 't'))
                .unwrap();
            // Undo this change, which should move us back to the root
            dag.undo(1).unwrap();
            // If the wrong Path for the cursor is loaded, then a non-existent node will be referenced
            // and the code will panic.  It doesn't matter what the cursor is, just so long as the code
            // doesn't panic
            dag.cursor();
        }

        /// this is a regression test for pull request #100.
        #[test]
        fn pr_100_prefix_replace_crash() {
            let arena: Arena<Json> = Arena::new();
            let root = add_value_to_arena(json!([true, false, false]), &arena);
            let mut dag = Dag::new(&arena, root, Path::from_vec(vec![0]));

            // Replace the [true, false, false] to [false, false, false, false]
            assert_eq!(
                Err(EditErr::ReplaceError {
                    current_child_index: 0,
                    last_child_index: 2,
                    node_count: 4
                }),
                dag.replace_cursor(4, Insertable::CountedNode(1, 'f'))
            );
        }
    }
}