py-12-txn-kvstore

# Transactional key-value store

Implement a file **`solution.py`** containing a class `KVStore` that behaves like an in-memory
key-value map with **nested transactions**.

```python
class KVStore:
    def __init__(self): ...
    def get(self, key):          ...   # current value, or None if absent
    def set(self, key, value):   ...
    def delete(self, key):       ...   # remove key (no-op if absent)
    def keys(self):              ...   # sorted list of currently-visible keys
    def __len__(self):           ...   # number of currently-visible keys

    def begin(self):    ...            # open a new (nested) transaction
    def commit(self):   ...            # merge the innermost open transaction into its parent
    def rollback(self): ...            # discard the innermost open transaction
```

## Semantics

- With **no open transaction**, `set`/`delete` mutate the committed store directly.
- `begin()` opens a transaction. Transactions **nest**: a second `begin()` opens a child of the
  first. All `set`/`delete` calls apply to the **innermost** open transaction only.
- `get`, `keys`, and `__len__` always reflect the **currently-visible** state: the committed store
  overlaid by every open transaction in order (innermost wins). A key `delete`d in an open
  transaction is invisible even if it exists in the committed store.
- `commit()` merges the innermost transaction's changes (both sets and deletes) into its parent
  (the enclosing transaction, or the committed store if it was the outermost). The transaction is
  then closed.
- `rollback()` discards the innermost transaction's changes entirely and closes it.
- `commit()` or `rollback()` with **no open transaction** must raise `RuntimeError`.
- `keys()` returns the visible keys in **sorted order**.

## Example

```python
s = KVStore()
s.set("a", 1)
s.begin()
s.set("a", 2)
s.set("b", 3)
assert s.get("a") == 2          # innermost transaction wins
s.begin()
s.delete("a")
assert s.get("a") is None       # deleted in the inner transaction
assert s.get("b") == 3          # still visible from the outer transaction
s.rollback()                    # discard the inner transaction
assert s.get("a") == 2          # back to the outer transaction's value
s.commit()                      # merge outer transaction into the committed store
assert s.get("a") == 2 and s.get("b") == 3
assert s.keys() == ["a", "b"]
```

import pytest

from solution import KVStore


def test_basic_set_get_delete():
    s = KVStore()
    assert s.get("a") is None
    s.set("a", 1)
    s.set("b", 2)
    assert s.get("a") == 1
    assert s.get("b") == 2
    s.delete("a")
    assert s.get("a") is None
    s.delete("missing")  # no-op, must not raise


def test_len_and_keys_sorted():
    s = KVStore()
    s.set("z", 1)
    s.set("a", 1)
    s.set("m", 1)
    assert s.keys() == ["a", "m", "z"]
    assert len(s) == 3
    s.delete("m")
    assert s.keys() == ["a", "z"]
    assert len(s) == 2


def test_transaction_isolation_then_commit():
    s = KVStore()
    s.set("a", 1)
    s.begin()
    s.set("a", 2)
    s.set("b", 3)
    assert s.get("a") == 2
    assert s.get("b") == 3
    s.commit()
    assert s.get("a") == 2
    assert s.get("b") == 3


def test_rollback_discards_changes():
    s = KVStore()
    s.set("a", 1)
    s.begin()
    s.set("a", 99)
    s.set("b", 5)
    s.rollback()
    assert s.get("a") == 1
    assert s.get("b") is None
    assert s.keys() == ["a"]


def test_delete_within_transaction_is_isolated():
    s = KVStore()
    s.set("a", 1)
    s.begin()
    s.delete("a")
    assert s.get("a") is None
    assert s.keys() == []
    assert len(s) == 0
    s.rollback()
    assert s.get("a") == 1  # delete was rolled back


def test_commit_propagates_delete_to_committed_store():
    s = KVStore()
    s.set("a", 1)
    s.begin()
    s.delete("a")
    s.commit()
    assert s.get("a") is None
    assert s.keys() == []


def test_nested_transactions_inner_rollback():
    s = KVStore()
    s.set("a", 1)
    s.begin()
    s.set("a", 2)
    s.set("b", 3)
    s.begin()
    s.delete("a")
    assert s.get("a") is None
    assert s.get("b") == 3
    s.rollback()             # discard inner
    assert s.get("a") == 2   # outer value restored
    s.commit()               # merge outer into committed
    assert s.get("a") == 2
    assert s.get("b") == 3


def test_nested_commit_merges_into_parent_not_base():
    s = KVStore()
    s.begin()
    s.set("a", 1)
    s.begin()
    s.set("a", 2)
    s.set("b", 3)
    s.commit()               # inner -> outer (NOT committed store yet)
    assert s.get("a") == 2
    assert s.get("b") == 3
    s.rollback()             # discard outer -> everything gone
    assert s.get("a") is None
    assert s.get("b") is None
    assert len(s) == 0


def test_commit_without_transaction_raises():
    s = KVStore()
    with pytest.raises(RuntimeError):
        s.commit()


def test_rollback_without_transaction_raises():
    s = KVStore()
    with pytest.raises(RuntimeError):
        s.rollback()


def test_deep_nesting_visibility_and_merge():
    s = KVStore()
    s.set("k", 0)
    for depth in range(1, 6):
        s.begin()
        s.set("k", depth)
        assert s.get("k") == depth
    # commit all five layers down to the base
    for _ in range(5):
        s.commit()
    assert s.get("k") == 5
    assert s.keys() == ["k"]


def test_reset_value_after_delete_in_same_transaction():
    s = KVStore()
    s.set("a", 1)
    s.begin()
    s.delete("a")
    s.set("a", 7)            # re-add after delete within the same transaction
    assert s.get("a") == 7
    s.commit()
    assert s.get("a") == 7

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
class KVStore:
    def __init__(self):
        self.store = {}
        self.transactions = []

    def get(self, key):
        for transaction in reversed(self.transactions):
            if key in transaction:
                return transaction[key]
        return self.store.get(key)

    def set(self, key, value):
        if self.transactions:
            self.transactions[-1][key] = value
        else:
            self.store[key] = value

    def delete(self, key):
        if self.transactions:
            self.transactions[-1].pop(key, None)
        else:
            self.store.pop(key, None)

    def keys(self):
        visible_keys = set()
        for transaction in reversed(self.transactions):
            visible_keys.update(transaction.keys())
        visible_keys.update(self.store.keys())
        return sorted(visible_keys)

    def __len__(self):
        return len(self.keys())

    def begin(self):
        self.transactions.append({})

    def commit(self):
        if not self.transactions:
            raise RuntimeError("No open transaction to commit.")
        if len(self.transactions) == 1:
            self.transactions.clear()
        else:
            self.transactions[-2].update(self.transactions.pop())

    def rollback(self):
        if not self.transactions:
            raise RuntimeError("No open transaction to rollback.")
        self.transactions.pop()
```

[
  {
    "total": 12,
    "answer": "```python\nclass KVStore:\n    def __init__(self):\n        self.store = {}\n        self.transactions = []\n\n    def get(self, key):\n        for transaction in reversed(self.transactions):\n            if key in transaction:\n                return transaction[key]\n        return self.store.get(key)\n\n    def set(self, key, value):\n        if self.transactions:\n            self.transactions[-1][key] = value\n        else:\n            self.store[key] = value\n\n    def delete(self, key):\n        if self.transactions:\n            self.transactions[-1].pop(key, None)\n        else:\n            self.store.pop(key, None)\n\n    def keys(self):\n        visible_keys = set()\n        for transaction in reversed(self.transactions):\n            visible_keys.update(transaction.keys())\n        visible_keys.update(self.store.keys())\n        return sorted(visible_keys)\n\n    def __len__(self):\n        return len(self.keys())\n\n    def begin(self):\n        self.transactions.append({})\n\n    def commit(self):\n        if not self.transactions:\n            raise RuntimeError(\"No open transaction to commit.\")\n        if len(self.transactions) == 1:\n            self.transactions.clear()\n        else:\n            self.transactions[-2].update(self.transactions.pop())\n\n    def rollback(self):\n        if not self.transactions:\n            raise RuntimeError(\"No open transaction to rollback.\")\n        self.transactions.pop()\n```",
    "passed": 6,
    "test_error": " s.commit()\n>       assert s.get(\"a\") is None\nE       AssertionError: assert 1 is None\nE        +  where 1 = get('a')\nE        +    where get = <solution.KVStore object at 0x78a4f2c44170>.get\n\ntest_kvstore.py:73: AssertionError\n___________________ test_nested_transactions_inner_rollback ____________________\n\n    def test_nested_transactions_inner_rollback():\n        s = KVStore()\n        s.set(\"a\", 1)\n        s.begin()\n        s.set(\"a\", 2)\n        s.set(\"b\", 3)\n        s.begin()\n        s.delete(\"a\")\n>       assert s.get(\"a\") is None\nE       AssertionError: assert 2 is None\nE        +  where 2 = get('a')\nE        +    where get = <solution.KVStore object at 0x78a4f2dec1a0>.get\n\ntest_kvstore.py:85: AssertionError\n____________________ test_deep_nesting_visibility_and_merge ____________________\n\n    def test_deep_nesting_visibility_and_merge():\n        s = KVStore()\n        s.set(\"k\", 0)\n        for depth in range(1, 6):\n            s.begin()\n            s.set(\"k\", depth)\n            assert s.get(\"k\") == depth\n        # commit all five layers down to the base\n        for _ in range(5):\n            s.commit()\n>       assert s.get(\"k\") == 5\nE       AssertionError: assert 0 == 5\nE        +  where 0 = get('k')\nE        +    where get = <solution.KVStore object at 0x78a4f2c44560>.get\n\ntest_kvstore.py:132: AssertionError\n______________ test_reset_value_after_delete_in_same_transaction _______________\n\n    def test_reset_value_after_delete_in_same_transaction():\n        s = KVStore()\n        s.set(\"a\", 1)\n        s.begin()\n        s.delete(\"a\")\n        s.set(\"a\", 7)            # re-add after delete within the same transaction\n        assert s.get(\"a\") == 7\n        s.commit()\n>       assert s.get(\"a\") == 7\nE       AssertionError: assert 1 == 7\nE        +  where 1 = get('a')\nE        +    where get = <solution.KVStore object at 0x78a4f2c44c20>.get\n\ntest_kvstore.py:144: AssertionError\n=========================== short test summary info ============================\nFAILED test_kvstore.py::test_transaction_isolation_then_commit - AssertionErr...\nFAILED test_kvstore.py::test_delete_within_transaction_is_isolated - Assertio...\nFAILED test_kvstore.py::test_commit_propagates_delete_to_committed_store - As...\nFAILED test_kvstore.py::test_nested_transactions_inner_rollback - AssertionEr...\nFAILED test_kvstore.py::test_deep_nesting_visibility_and_merge - AssertionErr...\nFAILED test_kvstore.py::test_reset_value_after_delete_in_same_transaction - A...\n6 failed, 6 passed in 0.03s"
  },
  {
    "total": 12,
    "answer": "```python\nclass KVStore:\n    def __init__(self):\n        self.store = {}\n        self.transactions = []\n\n    def get(self, key):\n        for transaction in reversed(self.transactions):\n            if key in transaction:\n                return transaction[key]\n        return self.store.get(key)\n\n    def set(self, key, value):\n        if self.transactions:\n            self.transactions[-1][key] = value\n        else:\n            self.store[key] = value\n\n    def delete(self, key):\n        if self.transactions:\n            self.transactions[-1].pop(key, None)\n        else:\n            self.store.pop(key, None)\n\n    def keys(self):\n        visible_keys = set()\n        for transaction in reversed(self.transactions):\n            visible_keys.update(transaction.keys())\n        visible_keys.update(self.store.keys())\n        return sorted(visible_keys)\n\n    def __len__(self):\n        return len(self.keys())\n\n    def begin(self):\n        self.transactions.append({})\n\n    def commit(self):\n        if not self.transactions:\n            raise RuntimeError(\"No open transaction to commit.\")\n        if len(self.transactions) == 1:\n            self.transactions.clear()\n        else:\n            self.transactions[-2].update(self.transactions.pop())\n\n    def rollback(self):\n        if not self.transactions:\n            raise RuntimeError(\"No open transaction to rollback.\")\n        self.transactions.pop()\n```",
    "passed": 6,
    "test_error": " s.commit()\n>       assert s.get(\"a\") is None\nE       AssertionError: assert 1 is None\nE        +  where 1 = get('a')\nE        +    where get = <solution.KVStore object at 0x7d79b4a4c200>.get\n\ntest_kvstore.py:73: AssertionError\n___________________ test_nested_transactions_inner_rollback ____________________\n\n    def test_nested_transactions_inner_rollback():\n        s = KVStore()\n        s.set(\"a\", 1)\n        s.begin()\n        s.set(\"a\", 2)\n        s.set(\"b\", 3)\n        s.begin()\n        s.delete(\"a\")\n>       assert s.get(\"a\") is None\nE       AssertionError: assert 2 is None\nE        +  where 2 = get('a')\nE        +    where get = <solution.KVStore object at 0x7d79b4ad9730>.get\n\ntest_kvstore.py:85: AssertionError\n____________________ test_deep_nesting_visibility_and_merge ____________________\n\n    def test_deep_nesting_visibility_and_merge():\n        s = KVStore()\n        s.set(\"k\", 0)\n        for depth in range(1, 6):\n            s.begin()\n            s.set(\"k\", depth)\n            assert s.get(\"k\") == depth\n        # commit all five layers down to the base\n        for _ in range(5):\n            s.commit()\n>       assert s.get(\"k\") == 5\nE       AssertionError: assert 0 == 5\nE        +  where 0 = get('k')\nE        +    where get = <solution.KVStore object at 0x7d79b4c2a330>.get\n\ntest_kvstore.py:132: AssertionError\n______________ test_reset_value_after_delete_in_same_transaction _______________\n\n    def test_reset_value_after_delete_in_same_transaction():\n        s = KVStore()\n        s.set(\"a\", 1)\n        s.begin()\n        s.delete(\"a\")\n        s.set(\"a\", 7)            # re-add after delete within the same transaction\n        assert s.get(\"a\") == 7\n        s.commit()\n>       assert s.get(\"a\") == 7\nE       AssertionError: assert 1 == 7\nE        +  where 1 = get('a')\nE        +    where get = <solution.KVStore object at 0x7d79b4a4cc50>.get\n\ntest_kvstore.py:144: AssertionError\n=========================== short test summary info ============================\nFAILED test_kvstore.py::test_transaction_isolation_then_commit - AssertionErr...\nFAILED test_kvstore.py::test_delete_within_transaction_is_isolated - Assertio...\nFAILED test_kvstore.py::test_commit_propagates_delete_to_committed_store - As...\nFAILED test_kvstore.py::test_nested_transactions_inner_rollback - AssertionEr...\nFAILED test_kvstore.py::test_deep_nesting_visibility_and_merge - AssertionErr...\nFAILED test_kvstore.py::test_reset_value_after_delete_in_same_transaction - A...\n6 failed, 6 passed in 0.03s"
  },
  {
    "total": 12,
    "answer": "```python\nclass KVStore:\n    def __init__(self):\n        self.store = {}\n        self.transactions = []\n\n    def get(self, key):\n        for transaction in reversed(self.transactions):\n            if key in transaction:\n                return transaction[key]\n        return self.store.get(key)\n\n    def set(self, key, value):\n        if self.transactions:\n            self.transactions[-1][key] = value\n        else:\n            self.store[key] = value\n\n    def delete(self, key):\n        if self.transactions:\n            self.transactions[-1].pop(key, None)\n        else:\n            self.store.pop(key, None)\n\n    def keys(self):\n        visible_keys = set()\n        for transaction in reversed(self.transactions):\n            visible_keys.update(transaction.keys())\n        visible_keys.update(self.store.keys())\n        return sorted(visible_keys)\n\n    def __len__(self):\n        return len(self.keys())\n\n    def begin(self):\n        self.transactions.append({})\n\n    def commit(self):\n        if not self.transactions:\n            raise RuntimeError(\"No open transaction to commit.\")\n        if len(self.transactions) == 1:\n            self.transactions.clear()\n        else:\n            self.transactions[-2].update(self.transactions.pop())\n\n    def rollback(self):\n        if not self.transactions:\n            raise RuntimeError(\"No open transaction to rollback.\")\n        self.transactions.pop()\n```",
    "passed": 6,
    "test_error": ""
  }
]