Cart with nested transactions

A cart with add(sku, price, qty), remove(sku, qty), set_price(sku, price), quantity(sku) and total(), plus begin(), commit() and rollback() that nest. A support agent might use this: it starts a transaction, tries "swap the blue shirt for the red one and apply the exchange credit", and rolls back the whole attempt if a step fails. Ask:

• Do reads inside a transaction see its uncommitted changes? Yes (read your own writes).
• What does commit do when nested? It folds the inner transaction into the outer one. Nothing is final until the outermost commit; an outer rollback undoes committed inner work too.
• commit or rollback with no open transaction? Return False (or raise; ask).
• Is total() called often? Assume yes: keep it O(1).

Brute force: copy the whole cart onto a stack at every begin; rollback restores the copy. O(cart size) per begin.

Undo log per transaction (O(changes)). The cart's live state is always current. Each open transaction has a log mapping each line it touched to that line's value before the transaction first touched it (None if the line did not exist).

• Write: if the line is not yet in the top log, record its current value. Then change it.
• Rollback: pop the top log and write every recorded value back.
• Commit: pop the top log; if a parent transaction is open, copy entries into the parent's log only for lines the parent has not logged. The parent's entry is older, and the parent's rollback must return to the state before the parent began.

O(1) total. Keep total_cents as a field and adjust it inside the one function that changes a line, _put(sku, line): subtract the old line's amount, add the new one. Rollback writes lines through the same _put, so the total stays right without being logged separately. This is the design point to call out: one write path, used by normal edits and by rollback alike.

Invariants:

1. total_cents equals the sum of price × qty over current lines.
2. Applying the open logs from the top down restores the state at the matching begin.
3. Each log has at most one entry per SKU.

from typing import Dict, List, Optional, Tuple

Line = Tuple[int, int]  # (price_cents, qty)
_ABSENT = None


class Cart:
    def __init__(self) -> None:
        self.lines: Dict[str, Line] = {}
        self.total_cents = 0
        self._logs: List[Dict[str, Optional[Line]]] = []

    # ---- reads ------------------------------------------------------------
    def quantity(self, sku: str) -> int:
        return self.lines.get(sku, (0, 0))[1]

    def total(self) -> int:
        return self.total_cents

    def depth(self) -> int:
        return len(self._logs)

    # ---- writes -----------------------------------------------------------
    def add(self, sku: str, price: int, qty: int = 1) -> None:
        if qty <= 0 or price < 0:
            raise ValueError("qty must be positive, price non-negative")
        old = self.lines.get(sku)
        if old and old[0] != price:
            raise ValueError(f"{sku} is in the cart at a different price; use set_price")
        self._write(sku, (price, (old[1] if old else 0) + qty))

    def remove(self, sku: str, qty: Optional[int] = None) -> bool:
        old = self.lines.get(sku)
        if old is None:
            return False
        left = 0 if qty is None else old[1] - qty
        self._write(sku, (old[0], left) if left > 0 else _ABSENT)
        return True

    def set_price(self, sku: str, price: int) -> bool:
        old = self.lines.get(sku)
        if old is None:
            return False
        self._write(sku, (price, old[1]))
        return True

    # ---- transactions -----------------------------------------------------
    def begin(self) -> None:
        self._logs.append({})

    def rollback(self) -> bool:
        if not self._logs:
            return False
        for sku, before in self._logs.pop().items():
            self._put(sku, before)
        return True

    def commit(self) -> bool:
        if not self._logs:
            return False
        log = self._logs.pop()
        if self._logs:
            parent = self._logs[-1]
            for sku, before in log.items():
                parent.setdefault(sku, before)   # parent's entry is older
        return True

    # ---- the one write path -------------------------------------------------
    def _write(self, sku: str, line: Optional[Line]) -> None:
        if self._logs and sku not in self._logs[-1]:
            self._logs[-1][sku] = self.lines.get(sku, _ABSENT)
        self._put(sku, line)

    def _put(self, sku: str, line: Optional[Line]) -> None:
        old = self.lines.get(sku)
        if old:
            self.total_cents -= old[0] * old[1]
        if line is _ABSENT:
            self.lines.pop(sku, None)
        else:
            self.lines[sku] = line
            self.total_cents += line[0] * line[1]

Space: the cart plus one log entry per touched line per open transaction.

1. commit_all / rollback_all. Close every open transaction at once: rollback applies logs from the top down; commit just clears the stack, since the live state is already current.
2. Promotions and derived values. If the total includes discounts computed from the whole cart, an incremental total no longer works. Recompute on demand and cache with a version number bumped by every _put.
3. Savepoints by name. savepoint("before_swap") and rollback_to("before_swap"): keep the name with each log, and rollback pops logs until it reaches that one.
4. Concurrent sessions. A customer and a support agent editing one cart need isolation: give each session a private write set (an overlay) and validate at commit against a cart version.
5. Durability. Persist only outermost commits: write the merged log to an append-only store, which also gives an audit trail of what the agent changed.

Mid-level (L4)

• Correct cart operations and a working single-level transaction, even if begin copies the cart.
• Handles removal to zero, unknown SKUs and commit or rollback with nothing open.
• Tests rollback after mixed adds, removes and price changes.

Senior (L5)

• Undo log per transaction, with nested commit merging into the parent and keeping the parent's older entry.
• O(1) total maintained through a single write path that rollback also uses, and can explain why that keeps the invariant.
• A randomized test against a snapshot model.

Staff (L6+)

• Discusses when the incremental total breaks (whole-cart promotions) and the caching alternative.
• Extends to savepoints, concurrent sessions with isolation, and durable outermost commits with an audit trail.
• Relates it to the agent use case: an agent's multi-step action must be all-or-nothing and reviewable.