gabriel / muse public
aw_map.py python
254 lines 9.2 KB
Raw
sha256:8de4334a98c945aace420969d389ad678aa926d4ab4e886b2ac4c4241cb3bf2b revert: keep pyproject.toml in canonical PEP 440 form Sonnet 4.6 patch 73 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 import logging
32 import secrets
33 from typing import TypedDict
34
35 type _StrMap = dict[str, str]
36 logger = logging.getLogger(__name__)
37
38 class AWMapEntry(TypedDict):
39 """A single (key, value, token) triple in an :class:`AWMap`.
40
41 ``key`` is the map key (e.g. a file path or dimension name).
42 ``value`` is the associated value (e.g. a content hash).
43 ``token`` is the unique identifier of this specific *setting* of the key;
44 it is regenerated on every ``set`` call so concurrent sets of the same key
45 by different agents can be distinguished.
46 """
47
48 key: str
49 value: str
50 token: str
51
52 class AWMapDict(TypedDict):
53 """Wire format for a complete :class:`AWMap`.
54
55 ``entries`` holds all live ``(key, value, token)`` triples.
56 ``tombstones`` holds all token strings that have been removed.
57 """
58
59 entries: list[AWMapEntry]
60 tombstones: list[str]
61
62 class AWMap:
63 """Add-Wins Map — an unordered map CRDT where adds win over concurrent removes.
64
65 Keys and values are strings. Each logical key may temporarily have
66 multiple (value, token) pairs during concurrent writes; the visible value
67 for a key is resolved by taking the entry with the lexicographically
68 greatest token among all live entries for that key. This gives a
69 deterministic LWW-like resolution for concurrent writes to the same key
70 without requiring wall-clock timestamps.
71
72 All mutating methods return new :class:`AWMap` instances; ``self`` is
73 never modified.
74
75 Example::
76
77 m = AWMap()
78 m = m.set("tempo", "120bpm")
79 m = m.set("key", "C major")
80 assert m.get("tempo") == "120bpm"
81 assert m.get("key") == "C major"
82 assert m.remove("tempo").get("tempo") is None
83 """
84
85 def __init__(
86 self,
87 entries: set[tuple[str, str, str]] | None = None,
88 tombstones: set[str] | None = None,
89 ) -> None:
90 """Initialise an AW-Map, optionally pre-populated.
91
92 Args:
93 entries: Set of ``(key, value, token)`` triples (live entries).
94 tombstones: Set of removed token strings.
95 """
96 self._entries: set[tuple[str, str, str]] = set(entries) if entries else set()
97 self._tombstones: set[str] = set(tombstones) if tombstones else set()
98
99 # ------------------------------------------------------------------
100 # Mutations (return new AWMap)
101 # ------------------------------------------------------------------
102
103 def set(self, key: str, value: str) -> AWMap:
104 """Set *key* to *value*, replacing all existing live entries for *key*.
105
106 Old tokens for *key* are tombstoned; a new token is generated for the
107 new value, giving the add-wins property for concurrent operations.
108
109 Args:
110 key: The map key to set.
111 value: The new value to associate with *key*.
112
113 Returns:
114 A new :class:`AWMap` with *key* updated to *value*.
115 """
116 # Tombstone all existing live entries for key
117 existing_tokens = {t for k, v, t in self._entries if k == key and t not in self._tombstones}
118 new_tombstones = self._tombstones | existing_tokens
119 new_entries = {e for e in self._entries if not (e[0] == key and e[2] in existing_tokens)}
120 # Add new entry with fresh token
121 new_token = secrets.token_hex(16)
122 new_entries.add((key, value, new_token))
123 return AWMap(new_entries, new_tombstones)
124
125 def remove(self, key: str) -> AWMap:
126 """Remove *key* by tombstoning all currently observed tokens for it.
127
128 Concurrent adds with new tokens survive this remove.
129
130 Args:
131 key: The map key to remove.
132
133 Returns:
134 A new :class:`AWMap` with *key* removed.
135 """
136 observed_tokens = {t for k, v, t in self._entries if k == key}
137 new_tombstones = self._tombstones | observed_tokens
138 new_entries = {e for e in self._entries if not (e[0] == key)}
139 return AWMap(new_entries, new_tombstones)
140
141 # ------------------------------------------------------------------
142 # CRDT join
143 # ------------------------------------------------------------------
144
145 def join(self, other: AWMap) -> AWMap:
146 """Return the lattice join — union of entries minus all tombstones.
147
148 Args:
149 other: The AW-Map to merge with.
150
151 Returns:
152 A new :class:`AWMap` that is the join of ``self`` and *other*.
153 """
154 all_tombstones = self._tombstones | other._tombstones
155 all_raw_entries = self._entries | other._entries
156 live_entries = {e for e in all_raw_entries if e[2] not in all_tombstones}
157 return AWMap(live_entries, all_tombstones)
158
159 # ------------------------------------------------------------------
160 # Query
161 # ------------------------------------------------------------------
162
163 def get(self, key: str) -> str | None:
164 """Return the current value for *key*, or ``None`` if absent.
165
166 When multiple live entries exist for *key* (due to concurrent un-joined
167 writes), the one with the lexicographically greatest token is returned.
168 This gives a deterministic, consistent result without wall-clock time.
169
170 Args:
171 key: The map key to look up.
172
173 Returns:
174 The value string, or ``None`` if *key* has no live entry.
175 """
176 live = [(v, t) for k, v, t in self._entries if k == key and t not in self._tombstones]
177 if not live:
178 return None
179 return max(live, key=lambda pair: pair[1])[0]
180
181 def keys(self) -> frozenset[str]:
182 """Return the set of keys with at least one live entry.
183
184 Returns:
185 Frozenset of key strings currently in the map.
186 """
187 return frozenset(k for k, v, t in self._entries if t not in self._tombstones)
188
189 def to_plain_dict(self) -> _StrMap:
190 """Return a plain ``{key: value}`` dict of visible entries.
191
192 Concurrent-write conflicts are resolved by lexicographic token order
193 (the same rule as :meth:`get`).
194
195 Returns:
196 ``{key: resolved_value}`` for all live keys.
197 """
198 result: _StrMap = {}
199 for k in self.keys():
200 v = self.get(k)
201 if v is not None:
202 result[k] = v
203 return result
204
205 def __contains__(self, key: str) -> bool:
206 return key in self.keys()
207
208 # ------------------------------------------------------------------
209 # Serialisation
210 # ------------------------------------------------------------------
211
212 def to_dict(self) -> AWMapDict:
213 """Return a JSON-serialisable :class:`AWMapDict`.
214
215 Returns:
216 Dict with ``"entries"`` and ``"tombstones"`` lists.
217 """
218 entries: list[AWMapEntry] = [
219 {"key": k, "value": v, "token": t}
220 for k, v, t in sorted(self._entries)
221 ]
222 return {"entries": entries, "tombstones": sorted(self._tombstones)}
223
224 @classmethod
225 def from_dict(cls, data: AWMapDict) -> AWMap:
226 """Reconstruct an :class:`AWMap` from its wire representation.
227
228 Args:
229 data: Dict as produced by :meth:`to_dict`.
230
231 Returns:
232 A new :class:`AWMap`.
233 """
234 entries = {(e["key"], e["value"], e["token"]) for e in data["entries"]}
235 tombstones = set(data["tombstones"])
236 return cls(entries, tombstones)
237
238 # ------------------------------------------------------------------
239 # Python dunder helpers
240 # ------------------------------------------------------------------
241
242 def equivalent(self, other: AWMap) -> bool:
243 """Return ``True`` if both AW-Maps have the same visible key-value pairs and tombstones.
244
245 Args:
246 other: The AW-Map to compare against.
247
248 Returns:
249 ``True`` when plain dict views and tombstone sets are identical.
250 """
251 return self.to_plain_dict() == other.to_plain_dict() and self._tombstones == other._tombstones
252
253 def __repr__(self) -> str:
254 return f"AWMap(keys={set(self.keys())!r})"
File History 3 commits
sha256:8de4334a98c945aace420969d389ad678aa926d4ab4e886b2ac4c4241cb3bf2b revert: keep pyproject.toml in canonical PEP 440 form Sonnet 4.6 patch 73 days ago
sha256:a317886dc0496c4af7b285b3e41c86c4c34ea2e79afc63b8829aadb1ada7903f chore: bump version to 0.2.0rc15 to match musehub#113 fix release Sonnet 4.6 patch 73 days ago
sha256:f3b726b50f0aee3622bba751e0a67aa7ae4cf75a798477dbce581940b6a9cf70 feat: migrate invariants cache to .muse/cache/invariants.ms… Sonnet 4.6 patch 141 days ago