#[cfg(feature = "display")]
use crate::Display;
use crate::{At, Checkpoint, Command, Error, Meta, Queue, Record, RecordBuilder, Result, Signal};
#[cfg(feature = "chrono")]
use chrono::{DateTime, TimeZone};
use rustc_hash::FxHashMap;
use std::collections::VecDeque;
#[cfg(feature = "display")]
use std::fmt;
#[derive(Debug)]
pub struct History<R> {
root: usize,
next: usize,
pub(crate) saved: Option<At>,
pub(crate) record: Record<R>,
pub(crate) branches: FxHashMap<usize, Branch<R>>,
}
impl<R> History<R> {
#[inline]
pub fn new(receiver: impl Into<R>) -> History<R> {
History {
root: 0,
next: 1,
saved: None,
record: Record::new(receiver),
branches: FxHashMap::default(),
}
}
#[inline]
pub fn builder() -> HistoryBuilder<R> {
HistoryBuilder {
inner: Record::builder(),
}
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.record.reserve(additional);
}
#[inline]
pub fn capacity(&self) -> usize {
self.record.capacity()
}
#[inline]
pub fn len(&self) -> usize {
self.record.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.record.is_empty()
}
#[inline]
pub fn limit(&self) -> usize {
self.record.limit()
}
#[inline]
pub fn set_limit(&mut self, limit: usize) -> usize {
let len = self.len();
let limit = self.record.set_limit(limit);
let diff = len - self.len();
let root = self.root();
for cursor in 0..diff {
self.rm_child(root, cursor);
}
for branch in self
.branches
.values_mut()
.filter(|branch| branch.parent.branch == root)
{
branch.parent.cursor -= diff;
}
limit
}
#[inline]
pub fn connect(&mut self, f: impl FnMut(Signal) + Send + Sync + 'static) {
self.record.connect(f);
}
#[inline]
pub fn can_undo(&self) -> bool {
self.record.can_undo()
}
#[inline]
pub fn can_redo(&self) -> bool {
self.record.can_redo()
}
#[inline]
pub fn set_saved(&mut self, saved: bool) {
self.record.set_saved(saved);
self.saved = None;
}
#[inline]
pub fn is_saved(&self) -> bool {
self.record.is_saved()
}
#[inline]
pub fn revert(&mut self) -> Option<Result<R>>
where
R: 'static,
{
if self.is_saved() {
self.record.revert()
} else {
self.saved
.and_then(|saved| self.go_to(saved.branch, saved.cursor))
}
}
#[inline]
pub fn root(&self) -> usize {
self.root
}
#[inline]
pub fn cursor(&self) -> usize {
self.record.cursor()
}
#[inline]
pub fn clear(&mut self) {
let old = self.root();
self.root = 0;
self.next = 1;
self.saved = None;
self.record.clear();
self.branches.clear();
if let Some(ref mut f) = self.record.signal {
f(Signal::Root { old, new: 0 });
}
}
#[inline]
pub fn apply(&mut self, command: impl Command<R> + 'static) -> Result<R>
where
R: 'static,
{
self.__apply(Meta::new(command)).map(|_| ())
}
#[inline]
pub(crate) fn __apply(&mut self, meta: Meta<R>) -> std::result::Result<bool, Error<R>>
where
R: 'static,
{
let cursor = self.cursor();
let saved = self.record.saved.filter(|&saved| saved > cursor);
let (merged, commands) = self.record.__apply(meta)?;
if !merged && cursor == self.cursor() {
let root = self.root();
self.rm_child(root, 0);
for branch in self
.branches
.values_mut()
.filter(|branch| branch.parent.branch == root)
{
branch.parent.cursor -= 1;
}
}
if !commands.is_empty() {
let old = self.root();
let new = self.next;
self.next += 1;
self.branches.insert(
old,
Branch {
parent: At {
branch: new,
cursor,
},
commands,
},
);
self.set_root(new, cursor);
match (self.record.saved, saved, self.saved) {
(Some(_), None, None) | (None, None, Some(_)) => self.swap_saved(new, old, cursor),
(None, Some(_), None) => {
self.record.saved = saved;
self.swap_saved(old, new, cursor);
}
(None, None, None) => (),
_ => unreachable!(),
}
if let Some(ref mut f) = self.record.signal {
f(Signal::Root { old, new })
}
}
Ok(merged)
}
#[inline]
#[must_use]
pub fn undo(&mut self) -> Option<Result<R>> {
self.record.undo()
}
#[inline]
#[must_use]
pub fn redo(&mut self) -> Option<Result<R>> {
self.record.redo()
}
#[inline]
#[must_use]
pub fn go_to(&mut self, branch: usize, cursor: usize) -> Option<Result<R>>
where
R: 'static,
{
let root = self.root();
if root == branch {
return self.record.go_to(cursor);
}
for (new, branch) in self.mk_path(branch)? {
let old = self.root();
if let Err(err) = self.record.go_to(branch.parent.cursor).unwrap() {
return Some(Err(err));
}
for meta in branch.commands {
let cursor = self.cursor();
let saved = self.record.saved.filter(|&saved| saved > cursor);
let commands = match self.record.__apply(meta) {
Ok((_, commands)) => commands,
Err(err) => return Some(Err(err)),
};
if !commands.is_empty() {
self.branches.insert(
self.root,
Branch {
parent: At {
branch: new,
cursor,
},
commands,
},
);
self.set_root(new, cursor);
match (self.record.saved, saved, self.saved) {
(Some(_), None, None) | (None, None, Some(_)) => {
self.swap_saved(new, old, cursor);
}
(None, Some(_), None) => {
self.record.saved = saved;
self.swap_saved(old, new, cursor);
}
(None, None, None) => (),
_ => unreachable!(),
}
}
}
}
if let Err(err) = self.record.go_to(cursor)? {
return Some(Err(err));
} else if let Some(ref mut f) = self.record.signal {
f(Signal::Root {
old: root,
new: self.root,
});
}
Some(Ok(()))
}
#[inline]
#[must_use]
#[cfg(feature = "chrono")]
pub fn time_travel<Tz: TimeZone>(&mut self, to: impl AsRef<DateTime<Tz>>) -> Option<Result<R>> {
self.record.time_travel(to)
}
#[inline]
pub fn checkpoint(&mut self) -> Checkpoint<History<R>, R> {
Checkpoint::from(self)
}
#[inline]
pub fn queue(&mut self) -> Queue<History<R>, R> {
Queue::from(self)
}
#[inline]
#[must_use]
#[cfg(feature = "display")]
pub fn to_undo_string(&self) -> Option<String> {
self.record.to_undo_string()
}
#[inline]
#[must_use]
#[cfg(feature = "display")]
pub fn to_redo_string(&self) -> Option<String> {
self.record.to_redo_string()
}
#[inline]
#[cfg(feature = "display")]
pub fn display(&self) -> Display<Self> {
Display::from(self)
}
#[inline]
pub fn as_receiver(&self) -> &R {
self.record.as_receiver()
}
#[inline]
pub fn as_mut_receiver(&mut self) -> &mut R {
self.record.as_mut_receiver()
}
#[inline]
pub fn into_receiver(self) -> R {
self.record.into_receiver()
}
#[inline]
pub fn commands(&self) -> impl Iterator<Item = &impl Command<R>> {
self.record.commands()
}
#[inline]
pub fn branches(&self) -> impl Iterator<Item = &usize> {
self.branches.keys()
}
#[inline]
fn set_root(&mut self, root: usize, cursor: usize) {
let old = self.root();
self.root = root;
debug_assert_ne!(old, root);
for branch in self
.branches
.values_mut()
.filter(|branch| branch.parent.branch == old && branch.parent.cursor <= cursor)
{
branch.parent.branch = root;
}
}
#[inline]
fn swap_saved(&mut self, old: usize, new: usize, cursor: usize) {
debug_assert_ne!(old, new);
if let Some(At { cursor: saved, .. }) = self
.saved
.filter(|at| at.branch == new && at.cursor <= cursor)
{
self.saved = None;
self.record.saved = Some(saved);
if let Some(ref mut f) = self.record.signal {
f(Signal::Saved(true));
}
} else if let Some(saved) = self.record.saved {
self.saved = Some(At {
branch: old,
cursor: saved,
});
self.record.saved = None;
if let Some(ref mut f) = self.record.signal {
f(Signal::Saved(false));
}
}
}
#[inline]
fn rm_child(&mut self, branch: usize, cursor: usize) {
let mut dead: Vec<_> = self
.branches
.iter()
.filter(|&(_, child)| child.parent == At { branch, cursor })
.map(|(&id, _)| id)
.collect();
while let Some(parent) = dead.pop() {
self.branches.remove(&parent).unwrap();
self.saved = self.saved.filter(|saved| saved.branch != parent);
dead.extend(
self.branches
.iter()
.filter(|&(_, child)| child.parent.branch == parent)
.map(|(&id, _)| id),
)
}
}
#[inline]
#[must_use]
fn mk_path(&mut self, mut to: usize) -> Option<impl Iterator<Item = (usize, Branch<R>)>> {
debug_assert_ne!(self.root(), to);
let mut dest = self.branches.remove(&to)?;
let mut i = dest.parent.branch;
let mut path = vec![(to, dest)];
while i != self.root() {
dest = self.branches.remove(&i).unwrap();
to = i;
i = dest.parent.branch;
path.push((to, dest));
}
Some(path.into_iter().rev())
}
}
impl<R: Default> Default for History<R> {
#[inline]
fn default() -> History<R> {
History::new(R::default())
}
}
impl<R> AsRef<R> for History<R> {
#[inline]
fn as_ref(&self) -> &R {
self.as_receiver()
}
}
impl<R> AsMut<R> for History<R> {
#[inline]
fn as_mut(&mut self) -> &mut R {
self.as_mut_receiver()
}
}
impl<R> From<R> for History<R> {
#[inline]
fn from(receiver: R) -> History<R> {
History::new(receiver)
}
}
impl<R> From<Record<R>> for History<R> {
#[inline]
fn from(record: Record<R>) -> History<R> {
History {
root: 0,
next: 1,
saved: None,
record,
branches: FxHashMap::default(),
}
}
}
#[cfg(feature = "display")]
impl<R> fmt::Display for History<R> {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
(&self.display() as &dyn fmt::Display).fmt(f)
}
}
#[derive(Debug)]
pub(crate) struct Branch<R> {
pub(crate) parent: At,
pub(crate) commands: VecDeque<Meta<R>>,
}
#[derive(Debug)]
pub struct HistoryBuilder<R> {
inner: RecordBuilder<R>,
}
impl<R> HistoryBuilder<R> {
#[inline]
pub fn capacity(mut self, capacity: usize) -> HistoryBuilder<R> {
self.inner = self.inner.capacity(capacity);
self
}
#[inline]
pub fn limit(mut self, limit: usize) -> HistoryBuilder<R> {
self.inner = self.inner.limit(limit);
self
}
#[inline]
pub fn saved(mut self, saved: bool) -> HistoryBuilder<R> {
self.inner = self.inner.saved(saved);
self
}
#[inline]
pub fn connect(mut self, f: impl FnMut(Signal) + Send + Sync + 'static) -> HistoryBuilder<R> {
self.inner = self.inner.connect(f);
self
}
#[inline]
pub fn build(self, receiver: impl Into<R>) -> History<R> {
History {
root: 0,
next: 1,
saved: None,
record: self.inner.build(receiver),
branches: FxHashMap::default(),
}
}
}
impl<R: Default> HistoryBuilder<R> {
#[inline]
pub fn default(self) -> History<R> {
self.build(R::default())
}
}
#[cfg(all(test, not(feature = "display")))]
mod tests {
use crate::{Command, History};
use std::error::Error;
#[derive(Debug)]
struct Add(char);
impl Command<String> for Add {
fn apply(&mut self, receiver: &mut String) -> Result<(), Box<dyn Error + Send + Sync>> {
receiver.push(self.0);
Ok(())
}
fn undo(&mut self, receiver: &mut String) -> Result<(), Box<dyn Error + Send + Sync>> {
self.0 = receiver.pop().ok_or("`receiver` is empty")?;
Ok(())
}
}
#[test]
fn go_to() {
let mut history = History::default();
history.apply(Add('a')).unwrap();
history.apply(Add('b')).unwrap();
history.apply(Add('c')).unwrap();
history.apply(Add('d')).unwrap();
history.apply(Add('e')).unwrap();
assert_eq!(history.as_receiver(), "abcde");
history.undo().unwrap().unwrap();
history.undo().unwrap().unwrap();
assert_eq!(history.as_receiver(), "abc");
let abcde = history.root();
history.apply(Add('f')).unwrap();
history.apply(Add('g')).unwrap();
assert_eq!(history.as_receiver(), "abcfg");
history.undo().unwrap().unwrap();
let abcfg = history.root();
history.apply(Add('h')).unwrap();
history.apply(Add('i')).unwrap();
history.apply(Add('j')).unwrap();
assert_eq!(history.as_receiver(), "abcfhij");
history.undo().unwrap().unwrap();
let abcfhij = history.root();
history.apply(Add('k')).unwrap();
assert_eq!(history.as_receiver(), "abcfhik");
history.undo().unwrap().unwrap();
let abcfhik = history.root();
history.apply(Add('l')).unwrap();
assert_eq!(history.as_receiver(), "abcfhil");
history.apply(Add('m')).unwrap();
assert_eq!(history.as_receiver(), "abcfhilm");
let abcfhilm = history.root();
history.go_to(abcde, 2).unwrap().unwrap();
history.apply(Add('n')).unwrap();
history.apply(Add('o')).unwrap();
assert_eq!(history.as_receiver(), "abno");
history.undo().unwrap().unwrap();
let abno = history.root();
history.apply(Add('p')).unwrap();
history.apply(Add('q')).unwrap();
assert_eq!(history.as_receiver(), "abnpq");
let abnpq = history.root();
history.go_to(abcde, 5).unwrap().unwrap();
assert_eq!(history.as_receiver(), "abcde");
history.go_to(abcfg, 5).unwrap().unwrap();
assert_eq!(history.as_receiver(), "abcfg");
history.go_to(abcfhij, 7).unwrap().unwrap();
assert_eq!(history.as_receiver(), "abcfhij");
history.go_to(abcfhik, 7).unwrap().unwrap();
assert_eq!(history.as_receiver(), "abcfhik");
history.go_to(abcfhilm, 8).unwrap().unwrap();
assert_eq!(history.as_receiver(), "abcfhilm");
history.go_to(abno, 4).unwrap().unwrap();
assert_eq!(history.as_receiver(), "abno");
history.go_to(abnpq, 5).unwrap().unwrap();
assert_eq!(history.as_receiver(), "abnpq");
}
}