aaronrene / gabriel-muse public
aw_map.py python
261 lines 9.2 KB
Raw
sha256:660fcac1df3ab28f61862e961890bd2ca8b754fa0242079d93ca1e25037ec8a6 chore(tests): add docstring to tests/__init__.py so rc14 tr… Human 33 days ago
1 """Add-Wins Map (AW-Map) — CRDT map where adds win over concurrent removes.
2
3 An AW-Map is a dictionary where keys map to arbitrary CRDT values (represented
4 as strings — content hashes referencing the object store). The "add-wins"
5 property means that if agent A sets key K and agent B concurrently removes
6 key K, the merged result still contains K with A's value.
7
8 This is built using the same token-tag mechanism as :class:`~muse.core.crdts.or_set.ORSet`:
9 each key entry carries a set of unique tokens; removal tombstones all observed
10 tokens for that key.
11
12 Use cases in Muse:
13 - File manifests (path → content hash) where agent A can add a file while
14 agent B removes a different file.
15 - Plugin configuration maps (dimension → value) for independent per-dimension
16 settings.
17 - Annotation maps (element_id → annotation blob hash).
18
19 **Lattice laws satisfied by** :meth:`join`:
20 1. Commutativity: ``join(a, b) == join(b, a)``
21 2. Associativity: ``join(join(a, b), c) == join(a, join(b, c))``
22 3. Idempotency: ``join(a, a) == a``
23
24 Public API
25 ----------
26 - :class:`AWMapEntry` — ``TypedDict`` for one map entry (key, value, token).
27 - :class:`AWMapDict` — ``TypedDict`` wire format for a complete AW-Map.
28 - :class:`AWMap` — the map itself.
29 """
30
31
32 from __future__ import annotations
33
34 import logging
35 import uuid
36 from typing import TypedDict
37
38
39 type _StrMap = dict[str, str]
40 logger = logging.getLogger(__name__)
41
42
43 class AWMapEntry(TypedDict):
44 """A single (key, value, token) triple in an :class:`AWMap`.
45
46 ``key`` is the map key (e.g. a file path or dimension name).
47 ``value`` is the associated value (e.g. a content hash).
48 ``token`` is the unique identifier of this specific *setting* of the key;
49 it is regenerated on every ``set`` call so concurrent sets of the same key
50 by different agents can be distinguished.
51 """
52
53 key: str
54 value: str
55 token: str
56
57
58 class AWMapDict(TypedDict):
59 """Wire format for a complete :class:`AWMap`.
60
61 ``entries`` holds all live ``(key, value, token)`` triples.
62 ``tombstones`` holds all token strings that have been removed.
63 """
64
65 entries: list[AWMapEntry]
66 tombstones: list[str]
67
68
69 class AWMap:
70 """Add-Wins Map — an unordered map CRDT where adds win over concurrent removes.
71
72 Keys and values are strings. Each logical key may temporarily have
73 multiple (value, token) pairs during concurrent writes; the visible value
74 for a key is resolved by taking the entry with the lexicographically
75 greatest token among all live entries for that key. This gives a
76 deterministic LWW-like resolution for concurrent writes to the same key
77 without requiring wall-clock timestamps.
78
79 All mutating methods return new :class:`AWMap` instances; ``self`` is
80 never modified.
81
82 Example::
83
84 m = AWMap()
85 m = m.set("tempo", "120bpm")
86 m = m.set("key", "C major")
87 assert m.get("tempo") == "120bpm"
88 assert m.get("key") == "C major"
89 assert m.remove("tempo").get("tempo") is None
90 """
91
92 def __init__(
93 self,
94 entries: set[tuple[str, str, str]] | None = None,
95 tombstones: set[str] | None = None,
96 ) -> None:
97 """Initialise an AW-Map, optionally pre-populated.
98
99 Args:
100 entries: Set of ``(key, value, token)`` triples (live entries).
101 tombstones: Set of removed token strings.
102 """
103 self._entries: set[tuple[str, str, str]] = set(entries) if entries else set()
104 self._tombstones: set[str] = set(tombstones) if tombstones else set()
105
106 # ------------------------------------------------------------------
107 # Mutations (return new AWMap)
108 # ------------------------------------------------------------------
109
110 def set(self, key: str, value: str) -> AWMap:
111 """Set *key* to *value*, replacing all existing live entries for *key*.
112
113 Old tokens for *key* are tombstoned; a new token is generated for the
114 new value, giving the add-wins property for concurrent operations.
115
116 Args:
117 key: The map key to set.
118 value: The new value to associate with *key*.
119
120 Returns:
121 A new :class:`AWMap` with *key* updated to *value*.
122 """
123 # Tombstone all existing live entries for key
124 existing_tokens = {t for k, v, t in self._entries if k == key and t not in self._tombstones}
125 new_tombstones = self._tombstones | existing_tokens
126 new_entries = {e for e in self._entries if not (e[0] == key and e[2] in existing_tokens)}
127 # Add new entry with fresh token
128 new_token = str(uuid.uuid4())
129 new_entries.add((key, value, new_token))
130 return AWMap(new_entries, new_tombstones)
131
132 def remove(self, key: str) -> AWMap:
133 """Remove *key* by tombstoning all currently observed tokens for it.
134
135 Concurrent adds with new tokens survive this remove.
136
137 Args:
138 key: The map key to remove.
139
140 Returns:
141 A new :class:`AWMap` with *key* removed.
142 """
143 observed_tokens = {t for k, v, t in self._entries if k == key}
144 new_tombstones = self._tombstones | observed_tokens
145 new_entries = {e for e in self._entries if not (e[0] == key)}
146 return AWMap(new_entries, new_tombstones)
147
148 # ------------------------------------------------------------------
149 # CRDT join
150 # ------------------------------------------------------------------
151
152 def join(self, other: AWMap) -> AWMap:
153 """Return the lattice join — union of entries minus all tombstones.
154
155 Args:
156 other: The AW-Map to merge with.
157
158 Returns:
159 A new :class:`AWMap` that is the join of ``self`` and *other*.
160 """
161 all_tombstones = self._tombstones | other._tombstones
162 all_raw_entries = self._entries | other._entries
163 live_entries = {e for e in all_raw_entries if e[2] not in all_tombstones}
164 return AWMap(live_entries, all_tombstones)
165
166 # ------------------------------------------------------------------
167 # Query
168 # ------------------------------------------------------------------
169
170 def get(self, key: str) -> str | None:
171 """Return the current value for *key*, or ``None`` if absent.
172
173 When multiple live entries exist for *key* (due to concurrent un-joined
174 writes), the one with the lexicographically greatest token is returned.
175 This gives a deterministic, consistent result without wall-clock time.
176
177 Args:
178 key: The map key to look up.
179
180 Returns:
181 The value string, or ``None`` if *key* has no live entry.
182 """
183 live = [(v, t) for k, v, t in self._entries if k == key and t not in self._tombstones]
184 if not live:
185 return None
186 return max(live, key=lambda pair: pair[1])[0]
187
188 def keys(self) -> frozenset[str]:
189 """Return the set of keys with at least one live entry.
190
191 Returns:
192 Frozenset of key strings currently in the map.
193 """
194 return frozenset(k for k, v, t in self._entries if t not in self._tombstones)
195
196 def to_plain_dict(self) -> _StrMap:
197 """Return a plain ``{key: value}`` dict of visible entries.
198
199 Concurrent-write conflicts are resolved by lexicographic token order
200 (the same rule as :meth:`get`).
201
202 Returns:
203 ``{key: resolved_value}`` for all live keys.
204 """
205 result: _StrMap = {}
206 for k in self.keys():
207 v = self.get(k)
208 if v is not None:
209 result[k] = v
210 return result
211
212 def __contains__(self, key: str) -> bool:
213 return key in self.keys()
214
215 # ------------------------------------------------------------------
216 # Serialisation
217 # ------------------------------------------------------------------
218
219 def to_dict(self) -> AWMapDict:
220 """Return a JSON-serialisable :class:`AWMapDict`.
221
222 Returns:
223 Dict with ``"entries"`` and ``"tombstones"`` lists.
224 """
225 entries: list[AWMapEntry] = [
226 {"key": k, "value": v, "token": t}
227 for k, v, t in sorted(self._entries)
228 ]
229 return {"entries": entries, "tombstones": sorted(self._tombstones)}
230
231 @classmethod
232 def from_dict(cls, data: AWMapDict) -> AWMap:
233 """Reconstruct an :class:`AWMap` from its wire representation.
234
235 Args:
236 data: Dict as produced by :meth:`to_dict`.
237
238 Returns:
239 A new :class:`AWMap`.
240 """
241 entries = {(e["key"], e["value"], e["token"]) for e in data["entries"]}
242 tombstones = set(data["tombstones"])
243 return cls(entries, tombstones)
244
245 # ------------------------------------------------------------------
246 # Python dunder helpers
247 # ------------------------------------------------------------------
248
249 def equivalent(self, other: AWMap) -> bool:
250 """Return ``True`` if both AW-Maps have the same visible key-value pairs and tombstones.
251
252 Args:
253 other: The AW-Map to compare against.
254
255 Returns:
256 ``True`` when plain dict views and tombstone sets are identical.
257 """
258 return self.to_plain_dict() == other.to_plain_dict() and self._tombstones == other._tombstones
259
260 def __repr__(self) -> str:
261 return f"AWMap(keys={set(self.keys())!r})"
File History 2 commits
sha256:660fcac1df3ab28f61862e961890bd2ca8b754fa0242079d93ca1e25037ec8a6 chore(tests): add docstring to tests/__init__.py so rc14 tr… Human 33 days ago
sha256:d8316ffae901be06347e16ab55be11868eb519dd16ade3e8aa16a99e662f7e62 baseline: rc14 re-baseline after rc3 store corruption recovery Human patch 33 days ago