// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! A utility class for implementing "snapshottable" things; a snapshottable data structure permits
//! you to take a snapshot (via `start_snapshot`) and then, after making some changes, elect either
//! to rollback to the start of the snapshot or commit those changes.
//!
//! This vector is intended to be used as part of an abstraction, not serve as a complete
//! abstraction on its own. As such, while it will roll back most changes on its own, it also
//! supports a `get_mut` operation that gives you an arbitrary mutable pointer into the vector. To
//! ensure that any changes you make this with this pointer are rolled back, you must invoke
//! `record` to record any changes you make and also supplying a delegate capable of reversing
//! those changes.

use self::UndoLog::*;

use std::fmt;
use std::mem;
use std::ops;

#[derive(Debug)]
pub enum UndoLog<D: SnapshotVecDelegate> {
    /// New variable with given index was created.
    NewElem(usize),

    /// Variable with given index was changed *from* the given value.
    SetElem(usize, D::Value),

    /// Extensible set of actions
    Other(D::Undo),
}

pub struct SnapshotVec<D: SnapshotVecDelegate> {
    values: Vec<D::Value>,
    undo_log: Vec<UndoLog<D>>,
    num_open_snapshots: usize,
}

impl<D> fmt::Debug for SnapshotVec<D>
    where D: SnapshotVecDelegate,
          D: fmt::Debug,
          D::Undo: fmt::Debug,
          D::Value: fmt::Debug
{
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        fmt.debug_struct("SnapshotVec")
            .field("values", &self.values)
            .field("undo_log", &self.undo_log)
            .field("num_open_snapshots", &self.num_open_snapshots)
            .finish()
    }
}

// Snapshots are tokens that should be created/consumed linearly.
pub struct Snapshot {
    // Length of the undo log at the time the snapshot was taken.
    length: usize,
}

pub trait SnapshotVecDelegate {
    type Value;
    type Undo;

    fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
}

// HACK(eddyb) manual impl avoids `Default` bound on `D`.
impl<D: SnapshotVecDelegate> Default for SnapshotVec<D> {
    fn default() -> Self {
        SnapshotVec {
            values: Vec::new(),
            undo_log: Vec::new(),
            num_open_snapshots: 0,
        }
    }
}

impl<D: SnapshotVecDelegate> SnapshotVec<D> {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn with_capacity(c: usize) -> SnapshotVec<D> {
        SnapshotVec {
            values: Vec::with_capacity(c),
            undo_log: Vec::new(),
            num_open_snapshots: 0,
        }
    }

    fn in_snapshot(&self) -> bool {
        self.num_open_snapshots > 0
    }

    pub fn record(&mut self, action: D::Undo) {
        if self.in_snapshot() {
            self.undo_log.push(Other(action));
        }
    }

    pub fn len(&self) -> usize {
        self.values.len()
    }

    pub fn push(&mut self, elem: D::Value) -> usize {
        let len = self.values.len();
        self.values.push(elem);

        if self.in_snapshot() {
            self.undo_log.push(NewElem(len));
        }

        len
    }

    pub fn get(&self, index: usize) -> &D::Value {
        &self.values[index]
    }

    /// Reserve space for new values, just like an ordinary vec.
    pub fn reserve(&mut self, additional: usize) {
        // This is not affected by snapshots or anything.
        self.values.reserve(additional);
    }

    /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
    /// automatically, so you should be sure call `record()` with some sort of suitable undo
    /// action.
    pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
        &mut self.values[index]
    }

    /// Updates the element at the given index. The old value will saved (and perhaps restored) if
    /// a snapshot is active.
    pub fn set(&mut self, index: usize, new_elem: D::Value) {
        let old_elem = mem::replace(&mut self.values[index], new_elem);
        if self.in_snapshot() {
            self.undo_log.push(SetElem(index, old_elem));
        }
    }

    /// Updates all elements. Potentially more efficient -- but
    /// otherwise equivalent to -- invoking `set` for each element.
    pub fn set_all(&mut self, mut new_elems: impl FnMut(usize) -> D::Value) {
        if !self.in_snapshot() {
            for (slot, index) in self.values.iter_mut().zip(0..) {
                *slot = new_elems(index);
            }
        } else {
            for i in 0..self.values.len() {
                self.set(i, new_elems(i));
            }
        }
    }

    pub fn update<OP>(&mut self, index: usize, op: OP)
    where
        OP: FnOnce(&mut D::Value),
        D::Value: Clone,
    {
        if self.in_snapshot() {
            let old_elem = self.values[index].clone();
            self.undo_log.push(SetElem(index, old_elem));
        }
        op(&mut self.values[index]);
    }

    pub fn start_snapshot(&mut self) -> Snapshot {
        let length = self.undo_log.len();
        self.num_open_snapshots += 1;
        Snapshot { length: length }
    }

    pub fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[UndoLog<D>] {
        &self.undo_log[snapshot.length..]
    }

    fn assert_open_snapshot(&self, snapshot: &Snapshot) {
        // Failures here may indicate a failure to follow a stack discipline.
        assert!(self.undo_log.len() >= snapshot.length);
        assert!(self.num_open_snapshots > 0);
    }

    pub fn rollback_to(&mut self, snapshot: Snapshot) {
        debug!("rollback_to({})", snapshot.length);

        self.assert_open_snapshot(&snapshot);

        while self.undo_log.len() > snapshot.length {
            match self.undo_log.pop().unwrap() {
                NewElem(i) => {
                    self.values.pop();
                    assert!(self.values.len() == i);
                }

                SetElem(i, v) => {
                    self.values[i] = v;
                }

                Other(u) => {
                    D::reverse(&mut self.values, u);
                }
            }
        }

        self.num_open_snapshots -= 1;
    }

    /// Commits all changes since the last snapshot. Of course, they
    /// can still be undone if there is a snapshot further out.
    pub fn commit(&mut self, snapshot: Snapshot) {
        debug!("commit({})", snapshot.length);

        self.assert_open_snapshot(&snapshot);

        if self.num_open_snapshots == 1 {
            // The root snapshot. It's safe to clear the undo log because
            // there's no snapshot further out that we might need to roll back
            // to.
            assert!(snapshot.length == 0);
            self.undo_log.clear();
        }

        self.num_open_snapshots -= 1;
    }
}

impl<D: SnapshotVecDelegate> ops::Deref for SnapshotVec<D> {
    type Target = [D::Value];
    fn deref(&self) -> &[D::Value] {
        &*self.values
    }
}

impl<D: SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
    fn deref_mut(&mut self) -> &mut [D::Value] {
        &mut *self.values
    }
}

impl<D: SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
    type Output = D::Value;
    fn index(&self, index: usize) -> &D::Value {
        self.get(index)
    }
}

impl<D: SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
    fn index_mut(&mut self, index: usize) -> &mut D::Value {
        self.get_mut(index)
    }
}

impl<D: SnapshotVecDelegate> Extend<D::Value> for SnapshotVec<D> {
    fn extend<T>(&mut self, iterable: T)
    where
        T: IntoIterator<Item = D::Value>,
    {
        let initial_len = self.values.len();
        self.values.extend(iterable);
        let final_len = self.values.len();

        if self.in_snapshot() {
            self.undo_log.extend((initial_len..final_len).map(|len| NewElem(len)));
        }
    }
}

impl<D: SnapshotVecDelegate> Clone for SnapshotVec<D>
where
    D::Value: Clone,
    D::Undo: Clone,
{
    fn clone(&self) -> Self {
        SnapshotVec {
            values: self.values.clone(),
            undo_log: self.undo_log.clone(),
            num_open_snapshots: self.num_open_snapshots,
        }
    }
}

impl<D: SnapshotVecDelegate> Clone for UndoLog<D>
where
    D::Value: Clone,
    D::Undo: Clone,
{
    fn clone(&self) -> Self {
        match *self {
            NewElem(i) => NewElem(i),
            SetElem(i, ref v) => SetElem(i, v.clone()),
            Other(ref u) => Other(u.clone()),
        }
    }
}

impl SnapshotVecDelegate for i32 {
    type Value = i32;
    type Undo = ();

    fn reverse(_: &mut Vec<i32>, _: ()) {}
}

#[test]
fn basic() {
    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
    assert!(!vec.in_snapshot());
    assert_eq!(vec.len(), 0);
    vec.push(22);
    vec.push(33);
    assert_eq!(vec.len(), 2);
    assert_eq!(*vec.get(0), 22);
    assert_eq!(*vec.get(1), 33);
    vec.set(1, 34);
    assert_eq!(vec.len(), 2);
    assert_eq!(*vec.get(0), 22);
    assert_eq!(*vec.get(1), 34);

    let snapshot = vec.start_snapshot();
    assert!(vec.in_snapshot());

    vec.push(44);
    vec.push(55);
    vec.set(1, 35);
    assert_eq!(vec.len(), 4);
    assert_eq!(*vec.get(0), 22);
    assert_eq!(*vec.get(1), 35);
    assert_eq!(*vec.get(2), 44);
    assert_eq!(*vec.get(3), 55);

    vec.rollback_to(snapshot);
    assert!(!vec.in_snapshot());

    assert_eq!(vec.len(), 2);
    assert_eq!(*vec.get(0), 22);
    assert_eq!(*vec.get(1), 34);
}

#[test]
#[should_panic]
fn out_of_order() {
    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
    vec.push(22);
    let snapshot1 = vec.start_snapshot();
    vec.push(33);
    let snapshot2 = vec.start_snapshot();
    vec.push(44);
    vec.rollback_to(snapshot1); // bogus, but accepted
    vec.rollback_to(snapshot2); // asserts
}

#[test]
fn nested_commit_then_rollback() {
    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
    vec.push(22);
    let snapshot1 = vec.start_snapshot();
    let snapshot2 = vec.start_snapshot();
    vec.set(0, 23);
    vec.commit(snapshot2);
    assert_eq!(*vec.get(0), 23);
    vec.rollback_to(snapshot1);
    assert_eq!(*vec.get(0), 22);
}