gabriel / muse public
graph.py python
367 lines 12.5 KB
Raw
sha256:502e812e12319e30302d07d165425ceeb21687ad30e8af3a439b1f6de36c64d6 fix: update stale tag tests to use label for free-form anno… Sonnet 4.6 19 days ago
1 """Canonical commit DAG traversal primitives for the Muse VCS.
2
3 Every commit-graph walk in Muse — BFS ancestry, range exclusion, reachability,
4 and merge-base search — is built on the three functions exported here. Inline
5 BFS implementations scattered across commands and core modules should be
6 replaced with calls to these primitives.
7
8 Public API
9 ----------
10 walk_dag
11 Generic BFS/DFS DAG walker parameterised on node type T and an adjacency
12 function. The foundational primitive: all other traversals are built on
13 top of this.
14
15 iter_ancestors
16 BFS generator that yields :class:`~muse.core.store.CommitRecord` objects
17 in visit order. Thin wrapper around :func:`walk_dag` with commit-specific
18 adjacency logic.
19
20 ancestor_ids
21 Convenience wrapper around :func:`iter_ancestors` that returns a
22 ``set[str]`` of commit IDs. Used for range exclusion (``A..B``
23 semantics) and ancestry-path filtering.
24
25 find_merge_base
26 Dual-frontier BFS that finds the Lowest Common Ancestor of two commits
27 in O(distance_to_LCA) steps rather than O(total_history).
28
29 Design notes
30 ------------
31 * All traversals use :class:`collections.deque` for O(1) pops.
32 ``list.pop(0)`` or ``list.insert(0, ...)`` would be O(n) per step.
33 * walk_dag calls ``adjacency(node)`` before yielding the node so that
34 wrappers like iter_ancestors can cache the result (avoids double reads).
35 * Missing commits (``read_commit`` returns ``None``) are silently skipped
36 and do not count against ``max_commits``.
37 * The ``gc`` module intentionally reads raw bytes instead of using
38 ``read_commit`` — this is a deliberate robustness choice (survives schema
39 evolution) and is the only sanctioned exception to the "use graph.py"
40 rule.
41 """
42
43 import collections
44 import pathlib
45 from collections.abc import Callable, Iterable, Iterator
46 from typing import AbstractSet, Hashable, Literal, TypeVar
47
48 from muse.core.commits import (
49 CommitRecord,
50 read_commit,
51 )
52
53 T = TypeVar("T", bound=Hashable)
54
55
56 # ---------------------------------------------------------------------------
57 # walk_dag — generic DAG walker
58 # ---------------------------------------------------------------------------
59
60 def walk_dag(
61 starts: "T | Iterable[T]",
62 adjacency: "Callable[[T], Iterable[T]]",
63 *,
64 order: "Literal['bfs', 'dfs']" = "bfs",
65 exclude: "AbstractSet[T]" = frozenset(),
66 prune: "Callable[[T], bool] | None" = None,
67 max_nodes: "int | None" = None,
68 ) -> "Iterator[T]":
69 """Generic BFS/DFS walker over any directed acyclic graph.
70
71 Parameters
72 ----------
73 starts:
74 A single node or an iterable of start nodes. Bare strings are
75 treated as single nodes; all other iterables are expanded.
76 adjacency:
77 Called with a node; returns its immediate neighbours. For commit
78 DAGs, this reads parent IDs. The function is called *before* the
79 node is yielded so wrappers can cache the result.
80 order:
81 ``"bfs"`` (breadth-first, default) or ``"dfs"`` (depth-first).
82 Raises :class:`ValueError` for any other value.
83 exclude:
84 Nodes treated as already-visited. They and their subtrees are
85 never yielded. The caller's set is never mutated.
86 prune:
87 Predicate called on each candidate node. When it returns ``True``
88 the node is *not* yielded and its subtree is not explored.
89 max_nodes:
90 Hard cap on the number of nodes yielded. ``None`` means no limit.
91 ``0`` yields nothing.
92
93 Yields
94 ------
95 T
96 Each node at most once, in BFS or DFS visit order.
97 """
98 if order not in ("bfs", "dfs"):
99 raise ValueError(f"order must be 'bfs' or 'dfs', got {order!r}")
100
101 if isinstance(starts, str):
102 start_list: list[T] = [starts] # type: ignore[list-item]
103 elif hasattr(starts, "__iter__"):
104 start_list = list(starts) # type: ignore[arg-type]
105 else:
106 start_list = [starts]
107
108 seen: set[T] = set(exclude)
109 yielded = 0
110 queue: collections.deque[T] = collections.deque(start_list)
111
112 while queue:
113 if max_nodes is not None and yielded >= max_nodes:
114 return
115
116 node = queue.popleft() if order == "bfs" else queue.pop()
117
118 if node in seen:
119 continue
120 if prune is not None and prune(node):
121 seen.add(node)
122 continue
123
124 seen.add(node)
125 neighbours = list(adjacency(node))
126
127 if order == "bfs":
128 for n in neighbours:
129 if n not in seen:
130 queue.append(n)
131 else:
132 for n in reversed(neighbours):
133 if n not in seen:
134 queue.append(n)
135
136 yield node
137 yielded += 1
138
139 # ---------------------------------------------------------------------------
140 # iter_ancestors
141 # ---------------------------------------------------------------------------
142
143 def iter_ancestors(
144 root: pathlib.Path,
145 starts: "str | Iterable[str]",
146 *,
147 first_parent_only: bool = False,
148 exclude: "AbstractSet[str]" = frozenset(),
149 prune: "Callable[[str], bool] | None" = None,
150 max_commits: "int | None" = None,
151 ) -> "Iterator[CommitRecord]":
152 """BFS over the commit DAG, yielding :class:`CommitRecord` in visit order.
153
154 Thin wrapper around :func:`walk_dag` with commit-specific adjacency logic.
155 This is the **canonical commit-graph walker** for all of Muse. All other
156 BFS, ancestor-set, reachability, or range-exclusion computations should be
157 built on top of this function.
158
159 Parameters
160 ----------
161 root:
162 Repository root directory.
163 starts:
164 A single commit ID string or an iterable of commit ID strings.
165 When more than one ID is given the BFS is seeded from all of them
166 simultaneously (multi-source BFS).
167 first_parent_only:
168 When ``True``, follow only ``parent_commit_id`` (the first/linear
169 parent) and skip ``parent2_commit_id``. Use this for producing
170 linear first-parent history views.
171 exclude:
172 Commit IDs to treat as already-visited. Commits in this set — and
173 all of their ancestors — are never yielded. Use this for
174 range-exclusion (``A..B`` semantics): pass ``ancestor_ids(root, a)``
175 as *exclude* when walking from *b*.
176 max_commits:
177 Hard cap on the number of commits *yielded*. ``None`` means no
178 limit. Missing commits that are skipped do not count against the
179 cap. Useful for safety ceilings on very large repos.
180
181 Yields
182 ------
183 CommitRecord
184 In BFS visit order (roughly newest-first for a linear chain).
185 Each commit is yielded at most once even when reachable via
186 multiple paths. Missing commits are silently skipped.
187
188 Examples
189 --------
190 Walk all ancestors of HEAD::
191
192 for commit in iter_ancestors(root, head_id):
193 process(commit)
194
195 Walk only the first-parent chain::
196
197 ids = [c.commit_id for c in iter_ancestors(root, head, first_parent_only=True)]
198
199 Compute A..B range::
200
201 base_ids = ancestor_ids(root, a_id)
202 for commit in iter_ancestors(root, b_id, exclude=base_ids):
203 print(commit.message)
204
205 Multi-source BFS from all branch tips::
206
207 tips = [read_ref(root, b) for b in all_branches(root)]
208 for commit in iter_ancestors(root, tips):
209 process(commit)
210 """
211 cache: dict[str, CommitRecord] = {}
212
213 def _adjacency(cid: str) -> list[str]:
214 commit = read_commit(root, cid)
215 if commit is None:
216 return []
217 cache[cid] = commit
218 parents: list[str] = []
219 p1 = commit.parent_commit_id
220 p2 = commit.parent2_commit_id
221 if p1:
222 parents.append(p1)
223 if not first_parent_only and p2:
224 parents.append(p2)
225 return parents
226
227 yielded = 0
228 for cid in walk_dag(starts, _adjacency, exclude=exclude, prune=prune):
229 if max_commits is not None and yielded >= max_commits:
230 return
231 commit = cache.get(cid)
232 if commit is None:
233 continue # missing commit — skip without counting against cap
234 yield commit
235 yielded += 1
236
237 # ---------------------------------------------------------------------------
238 # ancestor_ids
239 # ---------------------------------------------------------------------------
240
241 def ancestor_ids(
242 root: pathlib.Path,
243 starts: str | Iterable[str],
244 *,
245 first_parent_only: bool = False,
246 exclude: AbstractSet[str] = frozenset(),
247 max_commits: int | None = None,
248 ) -> set[str]:
249 """Return the set of all commit IDs reachable from *starts*.
250
251 A convenience wrapper around :func:`iter_ancestors` for callers that need
252 a ``set[str]`` of IDs rather than a stream of records.
253
254 Common uses
255 -----------
256 * **Range exclusion** — ``ancestor_ids(root, base_id)`` as the ``exclude``
257 argument to a subsequent :func:`iter_ancestors` call implements
258 ``base..tip`` semantics.
259 * **Ancestry-path filtering** — check whether a commit lies on a direct
260 path between two references.
261 * **Reachability** — determine which commits are live (all IDs reachable
262 from any branch tip).
263
264 Parameters
265 ----------
266 root, starts, first_parent_only, exclude, max_commits:
267 Forwarded to :func:`iter_ancestors` unchanged.
268
269 Returns
270 -------
271 set[str]
272 Commit ID strings (``sha256:…``-prefixed).
273 """
274 return {
275 c.commit_id
276 for c in iter_ancestors(
277 root,
278 starts,
279 first_parent_only=first_parent_only,
280 exclude=exclude,
281 max_commits=max_commits,
282 )
283 }
284
285 # ---------------------------------------------------------------------------
286 # find_merge_base
287 # ---------------------------------------------------------------------------
288
289 def find_merge_base(
290 root: pathlib.Path,
291 commit_id_a: str,
292 commit_id_b: str,
293 *,
294 max_ancestors: int | None = None,
295 ) -> str | None:
296 """Find the Lowest Common Ancestor (LCA) of two commits.
297
298 Uses simultaneous bidirectional BFS — expanding both frontiers one step
299 at a time and stopping as soon as any commit ID appears in both seen sets.
300 This is O(distance_to_LCA) rather than O(total_history), making it
301 efficient even when two commits share a long common ancestry.
302
303 Parameters
304 ----------
305 root:
306 Repository root directory.
307 commit_id_a, commit_id_b:
308 The two commits to find the merge base for.
309 max_ancestors:
310 Hard cap on total commits visited across both frontiers combined.
311 When exceeded, raises :class:`ValueError` so the caller can surface
312 a useful error to the user. ``None`` means no limit.
313
314 Returns
315 -------
316 str | None
317 The LCA commit ID, or ``None`` if the two commits share no common
318 ancestor (disjoint histories).
319
320 Raises
321 ------
322 ValueError
323 When *max_ancestors* is set and the combined ancestor graph exceeds
324 the cap before a common ancestor is found. The message includes the
325 cap value so callers can relay it in user-facing errors.
326 """
327 if commit_id_a == commit_id_b:
328 return commit_id_a
329
330 seen_a: set[str] = {commit_id_a}
331 seen_b: set[str] = {commit_id_b}
332 frontier_a: collections.deque[str] = collections.deque([commit_id_a])
333 frontier_b: collections.deque[str] = collections.deque([commit_id_b])
334 total = 0
335
336 while frontier_a or frontier_b:
337 if max_ancestors is not None and total >= max_ancestors:
338 raise ValueError(
339 f"max_ancestors={max_ancestors:,} exceeded during merge-base search — "
340 "history too deep or DAG is malformed."
341 )
342
343 if frontier_a:
344 cid = frontier_a.popleft()
345 total += 1
346 commit = read_commit(root, cid)
347 if commit is not None:
348 for parent in (commit.parent_commit_id, commit.parent2_commit_id):
349 if parent is not None and parent not in seen_a:
350 seen_a.add(parent)
351 if parent in seen_b:
352 return parent
353 frontier_a.append(parent)
354
355 if frontier_b:
356 cid = frontier_b.popleft()
357 total += 1
358 commit = read_commit(root, cid)
359 if commit is not None:
360 for parent in (commit.parent_commit_id, commit.parent2_commit_id):
361 if parent is not None and parent not in seen_b:
362 seen_b.add(parent)
363 if parent in seen_a:
364 return parent
365 frontier_b.append(parent)
366
367 return None
File History 1 commit
sha256:502e812e12319e30302d07d165425ceeb21687ad30e8af3a439b1f6de36c64d6 fix: update stale tag tests to use label for free-form anno… Sonnet 4.6 19 days ago