history_stack/lib.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
//! A crate implementing generic history managers that can act as building blocks for transactional
//! state and reversible computations
#![no_std]
#![forbid(unsafe_code)]
#![warn(clippy::alloc_instead_of_core, clippy::std_instead_of_alloc)]
#![warn(clippy::pedantic, clippy::cargo)]
#![allow(clippy::module_name_repetitions)]
#![warn(missing_docs, clippy::missing_docs_in_private_items)]
extern crate alloc;
use core::{cmp, fmt, hash, ops};
use alloc::vec::Vec;
/// A wrapper over a `T` that provides a primitive history mechanism by use of a stack of `T`. It
/// can be pushed to or popped from to save the current value or pop out a previously saved value
/// in LIFO (stack) order.
///
/// `HistoryStack` is also "transparently T", meaning the default traits it implements all act like
/// the current value of T, so hashing `HistoryStack<T>` and T produce the same hash, Eq and Ord work
/// the same etc. This also includes `Display`, but does not include `Debug`.
#[derive(Clone, Default, Debug)]
pub struct HistoryStack<T> {
/// The history stack, this starts out empty and should only be modified via pushing and popping
stack: Vec<T>,
/// The current value, since `HistoryStack<T>` acts like a T, this is always initialized to
/// some value
current: T,
}
impl<T: fmt::Display> fmt::Display for HistoryStack<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.current.fmt(f)
}
}
impl<T> HistoryStack<T> {
/// Create a new `HistoryStack` whose current value is set to `v`, with no history
pub const fn new(v: T) -> Self {
Self {
stack: Vec::new(),
current: v,
}
}
/// Pop a value from the stack and set it as the current value, returning the previous current
/// value.
///
/// Returns `None` in the case that there was no previous value from the stack, current is also
/// unchanged.
pub fn pop(&mut self) -> Option<T> {
match self.stack.pop() {
Some(last) => Some(core::mem::replace(&mut self.current, last)),
None => None,
}
}
/// Pushes a value into the current value, and pushes the previously current value into the
/// stack.
pub fn push_value(&mut self, v: T) {
self.stack.push(core::mem::replace(&mut self.current, v));
}
/// Makes a [`Clone::clone`] of the current value and pushes it to the stack, leaving the
/// current value untouched
pub fn push(&mut self)
where
T: Clone,
{
self.stack.push(self.current.clone());
}
}
impl<T> ops::Deref for HistoryStack<T> {
type Target = T;
fn deref(&self) -> &Self::Target {
&self.current
}
}
impl<T> ops::DerefMut for HistoryStack<T> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.current
}
}
impl<T: PartialEq> PartialEq<T> for HistoryStack<T> {
fn eq(&self, other: &T) -> bool {
&self.current == other
}
}
impl<T: PartialEq> PartialEq for HistoryStack<T> {
fn eq(&self, other: &Self) -> bool {
self.current == other.current
}
}
impl<T: Eq> Eq for HistoryStack<T> {}
impl<T: PartialOrd> PartialOrd for HistoryStack<T> {
fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
self.current.partial_cmp(&other.current)
}
}
impl<T: PartialOrd> PartialOrd<T> for HistoryStack<T> {
fn partial_cmp(&self, other: &T) -> Option<cmp::Ordering> {
self.current.partial_cmp(other)
}
}
impl<T: Ord> Ord for HistoryStack<T> {
fn cmp(&self, other: &Self) -> cmp::Ordering {
self.current.cmp(&other.current)
}
}
impl<T: hash::Hash> hash::Hash for HistoryStack<T> {
fn hash<H: hash::Hasher>(&self, state: &mut H) {
self.current.hash(state);
}
}
/// A structure which allows you to undo and redo changes based on saved states of `T`.
///
/// To use, simply [`save`](UndoStack::save), [`undo`](UndoStack::undo), and
/// [`redo`](UndoStack::redo) later if needed;
/// ```rust
/// # use history_stack::UndoStack;
/// // Create with initial state
/// let mut undo = UndoStack::new(5u8);
///
/// // make a savepoint and get a reference to the new current value
/// // our stack looks like [5, 5] currently, our current value being the second
/// let newref = undo.save();
///
/// // we modified the new current value, our stack looks like [5, 10] now
/// *newref *= 2;
///
/// // but we made a mistake! we want to go back now, and since we are
/// // sure we saved earlier we can unwrap here to get the Ok variant
/// // our stack still looks like [5, 10], but now we point to the 5
/// let oldref = undo.undo().unwrap();
///
/// // turns out it wasnt a mistake, lets redo and unwrap to be sure we got the newer value
/// undo.redo().unwrap();
///
/// // UndoStack implements Deref and DerefMut, we can make sure we got the new value like this
/// assert_eq!(undo, 10);
/// ```
///
/// This is useful when you want to be able to make changes in a way where you can undo a change,
/// and then reapply it later, but do not wish to write a complex incremental structure that could
/// track changes like that. This type provides a generic (read: you can use it on anything)
/// interface to achieve that effect, even if it may use more memory than a more targeted approach.
///
/// `UndoStack` is also "transparently T", meaning the default traits it implements all act like
/// the current value of T, so hashing `UndoStack<T>` and T produce the same hash, Eq and Ord work
/// the same etc. This also includes `Display`, but does not include `Debug`.
#[derive(Clone, Debug)]
pub struct UndoStack<T> {
/// History of the undostack that includes the current value somewhere within
history: Vec<T>,
/// Index into history that represents the current value
current: usize,
}
impl<T: Default> Default for UndoStack<T> {
fn default() -> Self {
Self {
history: alloc::vec![T::default()],
current: 0,
}
}
}
impl<T: fmt::Display> fmt::Display for UndoStack<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.inner().fmt(f)
}
}
impl<T> UndoStack<T> {
/// Creates a new `UndoStack` with a starting value to act as the current value
pub fn new(start: T) -> Self {
Self {
history: alloc::vec![start],
current: 0,
}
}
/// Drops any values that exist after the current value
fn invalidate_future(&mut self) {
// we have hit undo if these values do not match up, so we must invalidate the redo stack
// it is safe to do current+1 because current is <history.len() which is stored
// as usize aswell
if self.current + 1 != self.history.len() {
// see above for +1 safety
self.history.truncate(self.current + 1);
}
}
/// Pushes a value assuming the current value is the last value
/// returns a reference to the new current value (the value that was just pushed)
fn push_unchecked(&mut self, val: T) -> &mut T {
self.history.push(val);
// +1 safety: current is always less than history.len(), which would panic on overflow
self.current += 1;
&mut self.history[self.current]
}
/// Saves the current T to history and invalidates any data that may be used to redo
/// This will [`Drop`] any T that exist later in history than the current edit point.
///
/// Returns a reference to the new current value
///
/// # Panics
/// This will panic if allocation failed
pub fn save(&mut self) -> &mut T
where
T: Clone,
{
self.invariant_ck();
self.invalidate_future();
// safe to unwrap here because history is always nonempty
let val = self.history.last().unwrap().clone();
self.push_unchecked(val)
}
/// Pushes the given value to the stack, making it the new current value and invalidating
/// future history, returns a reference to the new current value
///
/// This is functionally identical to [`save`](UndoStack::save) but does not have a `Clone`
/// bound, instead sourcing its new value from the caller.
///
/// # Panics
/// This will panic if allocation failed
pub fn push(&mut self, new_current: T) -> &mut T {
self.invariant_ck();
self.invalidate_future();
self.push_unchecked(new_current)
}
/// If there is a previous state in the history stack, backtrack to that and return `Ok(&mut T)`
/// to the new current value, otherwise return `Err(&mut T)` to the unchanged current value.
#[allow(clippy::missing_errors_doc)]
pub fn undo(&mut self) -> Result<&mut T, &mut T> {
self.invariant_ck();
match self.current.checked_sub(1) {
Some(n) => {
self.current = n;
Ok(&mut self.history[self.current])
}
None => {
// current was 0
Err(&mut self.history[0])
}
}
}
/// If there is a future state in the history stack that has been undone from, redo to that
/// position and return `Ok(&mut T)` of the new current value after advancing, else return
/// `Err(&mut T)` of the current unchanged value, if there was no future history.
#[allow(clippy::missing_errors_doc)]
pub fn redo(&mut self) -> Result<&mut T, &mut T> {
self.invariant_ck();
if self.current + 1 == self.history.len() {
Err(&mut self.history[self.current])
} else {
self.current += 1;
Ok(&mut self.history[self.current])
}
}
/// function that runs in debug and checks all trivial invariants of `UndoStack`
fn invariant_ck(&self) {
debug_assert!(
!self.history.is_empty(),
"UndoStack: history was empty, this indicates a bug in UndoStack"
);
debug_assert!(self.current < self.history.len(), "UndoStack: current was not less than history length, this indicates a bug in UndoStack");
}
/// Gets a reference to the current value
/// used to implement traits via T without accidental recursion
fn inner(&self) -> &T {
self
}
}
impl<T> ops::Deref for UndoStack<T> {
type Target = T;
fn deref(&self) -> &Self::Target {
&self.history[self.current]
}
}
impl<T> ops::DerefMut for UndoStack<T> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.history[self.current]
}
}
impl<T: PartialEq> PartialEq<T> for UndoStack<T> {
fn eq(&self, other: &T) -> bool {
self.inner() == other
}
}
impl<T: PartialEq> PartialEq for UndoStack<T> {
fn eq(&self, other: &Self) -> bool {
self.inner() == other.inner()
}
}
impl<T: Eq> Eq for UndoStack<T> {}
impl<T: PartialOrd> PartialOrd for UndoStack<T> {
fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
self.inner().partial_cmp(other.inner())
}
}
impl<T: PartialOrd> PartialOrd<T> for UndoStack<T> {
fn partial_cmp(&self, other: &T) -> Option<cmp::Ordering> {
self.inner().partial_cmp(other)
}
}
impl<T: Ord> Ord for UndoStack<T> {
fn cmp(&self, other: &Self) -> cmp::Ordering {
self.inner().cmp(other.inner())
}
}
impl<T: hash::Hash> hash::Hash for UndoStack<T> {
fn hash<H: hash::Hasher>(&self, state: &mut H) {
self.inner().hash(state);
}
}
#[test]
fn undo_stack() {
let mut g = UndoStack::new(0u8);
*g.save() += 1;
assert_eq!(g, 1);
assert_eq!(*g.undo().unwrap(), 0);
assert_eq!(*g.redo().unwrap(), 1);
assert!(g.undo().is_ok());
*g.save() += 2;
assert!(g.redo().is_err());
}
#[test]
fn history_stack() {
let mut g = HistoryStack::new(0u8);
g.push_value(5);
assert_eq!(g, 5);
assert_eq!(g.pop(), Some(5));
assert_eq!(g, 0);
}