Memento Design Pattern

public final class Canvas {

    private List<Shape> shapes = new ArrayList<>();
    private Map<ShapeId, Integer> zOrder = new HashMap<>();

    /** The memento. Private constructor and private fields: only Canvas can
     *  read it, which is the entire point of the pattern. */
    public static final class Memento {
        private final List<Shape> shapes;
        private final Map<ShapeId, Integer> zOrder;

        private Memento(List<Shape> shapes, Map<ShapeId, Integer> zOrder) {
            this.shapes = shapes;
            this.zOrder = zOrder;
        }
    }

    public Memento save() {
        // DEEP copy. `new ArrayList<>(shapes)` copies the list but shares the
        // Shape objects — mutate one afterwards and your "snapshot" changes too.
        return new Memento(
                shapes.stream().map(Shape::copy).toList(),
                Map.copyOf(zOrder));
    }

    public void restore(Memento m) {
        this.shapes = new ArrayList<>(m.shapes);
        this.zOrder = new HashMap<>(m.zOrder);
    }
}

/** The caretaker holds mementos and cannot see inside a single one. */
public final class UndoStack {
    private final Deque<Canvas.Memento> stack = new ArrayDeque<>();

    public void record(Canvas canvas) { stack.push(canvas.save()); }

    public void undo(Canvas canvas) {
        if (!stack.isEmpty()) canvas.restore(stack.pop());
    }
}

// Serialization is NOT a substitute: it exposes the fields to anything that can
// read the stream, which gives away the encapsulation you came for.

import copy
from dataclasses import dataclass, field


@dataclass(frozen=True)
class _Memento:
    """Leading underscore is the whole enforcement mechanism Python offers.

    There is no `private`, so the opacity is a convention. Freezing the
    dataclass at least stops the caretaker mutating a snapshot by accident,
    which is the failure that actually happens.
    """
    shapes: tuple[Shape, ...]
    z_order: tuple[tuple[ShapeId, int], ...]


class Canvas:
    def __init__(self) -> None:
        self._shapes: list[Shape] = []
        self._z_order: dict[ShapeId, int] = {}

    def save(self) -> _Memento:
        # deepcopy, not copy: a shallow copy of the list shares the Shape
        # objects, so moving a shape later would silently rewrite history.
        return _Memento(
            shapes=tuple(copy.deepcopy(s) for s in self._shapes),
            z_order=tuple(self._z_order.items()),
        )

    def restore(self, memento: _Memento) -> None:
        self._shapes = [copy.deepcopy(s) for s in memento.shapes]
        self._z_order = dict(memento.z_order)


class UndoStack:
    def __init__(self) -> None:
        self._stack: list[_Memento] = []

    def record(self, canvas: Canvas) -> None: self._stack.append(canvas.save())

    def undo(self, canvas: Canvas) -> None:
        if self._stack:
            canvas.restore(self._stack.pop())


# deepcopy is correct and slow. For big documents, prefer immutable structures
# and STRUCTURAL SHARING: if shapes never mutate, a snapshot is just a reference
# to the current tuple, and unchanged sub-trees are shared between snapshots.

class Canvas {
public:
    class Memento {
        // Only Canvas can construct or read one.
        friend class Canvas;
        Memento(std::vector<Shape> shapes, ZOrder z)
            : shapes_(std::move(shapes)), z_(std::move(z)) {}

        std::vector<Shape> shapes_;
        ZOrder z_;
    };

    Memento save() const { return Memento{shapes_, z_}; }   // value semantics = deep copy

    void restore(const Memento& m) {
        shapes_ = m.shapes_;
        z_ = m.z_;
    }

private:
    std::vector<Shape> shapes_;
    ZOrder z_;
};

// `friend` is the cleanest expression of Memento in any of these languages:
// the compiler enforces that exactly one other class may look inside.
//
// C++ value semantics also make the deep copy automatic — copying a
// vector<Shape> copies the shapes. The trap is the opposite one: if Shape
// holds a raw pointer or a shared_ptr to mutable data, the copy shares it and
// your snapshot is not a snapshot. Prefer value types inside a memento.
//
// For large documents, hold shared_ptr<const State> instead: snapshots then
// share unchanged data and cost a pointer copy each.

public sealed class Canvas
{
    private ImmutableList<Shape> _shapes = ImmutableList<Shape>.Empty;
    private ImmutableDictionary<ShapeId, int> _zOrder = ImmutableDictionary<ShapeId, int>.Empty;

    // The memento type is nested and private-constructed: the caretaker can
    // hold a CanvasMemento but cannot read or build one.
    public sealed class CanvasMemento
    {
        internal ImmutableList<Shape> Shapes { get; }
        internal ImmutableDictionary<ShapeId, int> ZOrder { get; }

        internal CanvasMemento(ImmutableList<Shape> shapes, ImmutableDictionary<ShapeId, int> z)
            => (Shapes, ZOrder) = (shapes, z);
    }

    // Immutable collections make save() O(1): nothing is copied, because
    // nothing can change underneath the snapshot.
    public CanvasMemento Save() => new(_shapes, _zOrder);

    public void Restore(CanvasMemento memento)
        => (_shapes, _zOrder) = (memento.Shapes, memento.ZOrder);
}

public sealed class UndoStack
{
    private readonly Stack<Canvas.CanvasMemento> _stack = new();

    public void Record(Canvas canvas) => _stack.Push(canvas.Save());
    public void Undo(Canvas canvas) { if (_stack.TryPop(out var m)) canvas.Restore(m); }
}

// This is the version worth copying into other languages: with immutable data,
// Memento stops being about copying and becomes about keeping references.

class Canvas {
  #shapes = []
  #zOrder = new Map()

  // #private fields are genuinely private at runtime, so the returned object
  // can hold state that only Canvas methods can read back.
  save() {
    return Object.freeze({
      // structuredClone deep-copies without JSON's losses: it preserves Map,
      // Set, Date and cyclic references, none of which survive
      // JSON.parse(JSON.stringify(x)) — the copy people usually reach for.
      shapes: structuredClone(this.#shapes),
      zOrder: structuredClone(this.#zOrder),
    })
  }

  restore(memento) {
    this.#shapes = structuredClone(memento.shapes)
    this.#zOrder = structuredClone(memento.zOrder)
  }
}

class UndoStack {
  #stack = []
  record(canvas) { this.#stack.push(canvas.save()) }
  undo(canvas) {
    const memento = this.#stack.pop()
    if (memento) canvas.restore(memento)
  }
}

// Redux time-travel debugging is this pattern at application scale: the store
// keeps previous states, and because reducers return new objects instead of
// mutating, each "snapshot" shares all the unchanged parts of the tree.

package editor

// Go has no private-to-another-type, so opacity comes from the PACKAGE:
// unexported fields are invisible outside this file's package, which is
// exactly the boundary the pattern needs.

type memento struct {
	shapes []Shape
	zOrder map[ShapeID]int
}

type Canvas struct {
	shapes []Shape
	zOrder map[ShapeID]int
}

func (c *Canvas) Save() *memento {
	// The trap: `append([]Shape(nil), c.shapes...)` copies the SLICE but the
	// elements are copied by value only if Shape has no reference fields. A
	// Shape holding a []Point or a map shares that data with the snapshot.
	shapes := make([]Shape, len(c.shapes))
	for i, s := range c.shapes {
		shapes[i] = s.Clone()          // deep clone, per shape
	}

	z := make(map[ShapeID]int, len(c.zOrder))
	maps.Copy(z, c.zOrder)             // maps are references — always copy

	return &memento{shapes: shapes, zOrder: z}
}

func (c *Canvas) Restore(m *memento) {
	c.shapes = slices.Clone(m.shapes)
	c.zOrder = maps.Clone(m.zOrder)
}

// UndoStack holds []*memento and can't touch a field of one from another
// package — the compiler enforces the caretaker's ignorance.

type ShapeId = string & { readonly __brand: 'ShapeId' }

// The memento type is exported as an OPAQUE token: callers can hold it and
// pass it back, and the type system refuses to let them read it.
declare const memento: unique symbol
export type CanvasMemento = { readonly [memento]: true }

interface InternalMemento extends CanvasMemento {
  readonly shapes: readonly Shape[]
  readonly zOrder: ReadonlyMap<ShapeId, number>
}

export class Canvas {
  #shapes: readonly Shape[] = []
  #zOrder: ReadonlyMap<ShapeId, number> = new Map()

  save(): CanvasMemento {
    // Everything is readonly, so the snapshot is just a pair of references —
    // no copying, and nothing can change underneath it.
    return { shapes: this.#shapes, zOrder: this.#zOrder } as InternalMemento
  }

  restore(m: CanvasMemento): void {
    const internal = m as InternalMemento
    this.#shapes = internal.shapes
    this.#zOrder = internal.zOrder
  }
}

export class UndoStack {
  #stack: CanvasMemento[] = []
  record(canvas: Canvas): void { this.#stack.push(canvas.save()) }
  undo(canvas: Canvas): void {
    const m = this.#stack.pop()
    if (m) canvas.restore(m)
  }
  // `m.shapes` here is a compile error — the caretaker holds a token, not data.
}