Key-Value Store with Nested Transactions

Implement run_commands(commands), an in-memory key-value store that processes a list of command strings and supports arbitrarily nested transactions. Keys and values are whitespace-free strings. The function returns the list of output lines, exactly as they would be printed, so every item is a string: GET contributes the value or the literal string "NULL", COUNTVALUES contributes the count as a string, and a ROLLBACK or COMMIT with no open transaction contributes "ERROR".

Reads inside a transaction see its own changes and those of every enclosing transaction. Rolling back an inner transaction restores the enclosing state exactly. A committed inner transaction becomes part of its parent, so rolling the parent back afterwards discards the child's changes too. COUNTVALUES always reflects the currently visible state.

The mechanic: one main map holds the visible state and a second map holds value counts, so GET and COUNTVALUES are O(1) and never walk anything. Beside them sits a stack of undo logs, one frame per open transaction. Every write (SET or DELETE) first records the key's prior state in the top frame (but only the first time that frame touches the key), then goes through a single write path that keeps the counts map in step. ROLLBACK pops one frame and replays it through that same write path. COMMIT pops the top frame and merges it into the parent frame, keeping the parent's entry wherever both recorded the same key (the parent's is older); when there is no parent the frame is simply dropped, because the main map is already current.

Three details decide whether this works:

• Record only on the first write to a key in that frame. SET a 1; BEGIN; SET a 2; SET a 3; ROLLBACK must restore 1, not 2.
• "Did not exist" is a real state to record. A key first written (or a key deleted) inside a transaction needs a sentinel distinct from every real value, so rollback knows to delete rather than restore something.
• Commit merges must not overwrite the parent's record. The parent's entry describes the state at the parent's BEGIN; the child's describes a later moment. Take the child's entries only for keys the parent has not seen.

This shape never copies the store, and it does not recurse, so nesting thousands of levels deep costs nothing and cannot overflow the call stack. Tests include a case with 250,000 commands over a large key space; a design that snapshots the store on BEGIN, or rescans it on every COUNTVALUES, does far too much work to finish in time.

Example: SET a 10 / BEGIN / SET a 20 / BEGIN / SET a 30 / GET a / COMMIT / GET a / ROLLBACK / GET a returns {"30", "30", "10"}.

• GET a inside the innermost transaction sees 30.
• COMMIT folds the inner transaction into the outer one: a stays 30, but the outer undo log still remembers a -> 10 from its own BEGIN.
• ROLLBACK of the outer transaction therefore discards the committed inner change as well, restoring 10.

Example: SET a 10 / SET b 10 / COUNTVALUES 10 / BEGIN / DELETE a / COUNTVALUES 10 / ROLLBACK / COUNTVALUES 10 returns {"2", "1", "2"}: the delete is visible inside the transaction and undone by the rollback, and the counts track it exactly.

Input format: each test in tests/*.in is laid out as:

• Line 1: L n, the mode letter and the number of commands.
• Next n lines: one command each, exactly the string run_commands receives (SET key value, GET key, DELETE key, COUNTVALUES value, BEGIN, ROLLBACK, or COMMIT).

A performance test is instead the single line G 250000 12345 (mode G): the harness builds the n commands itself from the seed and compares a checksum of run_commands's output lines, so your function still receives an ordinary list of command strings.

Test 02.in reads:

L 8
ROLLBACK
COMMIT
GET x
BEGIN
SET x 1
COMMIT
GET x
ROLLBACK

This is 8 commands: the opening ROLLBACK and COMMIT run with no transaction open, so each contributes ERROR; GET x sees nothing yet and contributes NULL; the committed SET x 1 makes the next GET x contribute 1; and the final ROLLBACK has nothing left to undo, so it contributes ERROR again.

Where you'll use it:

• 1146. Snapshot Array
• 432. All O`one Data Structure
• 981. Time Based Key-Value Store