gabriel / muse public
link_index.py python
598 lines 21.3 KB
Raw
sha256:d8316ffae901be06347e16ab55be11868eb519dd16ade3e8aa16a99e662f7e62 baseline: rc14 re-baseline after rc3 store corruption recovery Human patch 27 days ago
1 """Knowtation vault link indexer (Phase 3.1).
2
3 Parses three kinds of inter-note edges and assembles a directed graph keyed by
4 vault-relative POSIX paths:
5
6 1. **Wikilinks** — Obsidian-style ``[[Note Title]]`` / ``[[note|alias]]`` /
7 ``[[note#section]]``. Regex ported from
8 ``knowtation/lib/wikilink.mjs`` with semantic parity.
9 2. **Markdown links to .md files** — standard CommonMark
10 ``[text](relative/path.md)`` (and ``./path.md`` / ``../path.md``) references.
11 This parser does **not** exist on the Knowtation side today and is new in
12 Muse.
13 3. **Entity references** — every value in a note's ``entity`` frontmatter
14 field that matches another note's ``entity`` field is treated as a
15 co-occurrence edge. Useful for ``muse code entangle`` (Phase 3.3).
16 4. **Mist attachment references** — Phase 3.5 (extension) treats
17 ``frontmatter.attachments[*]`` as a third edge type. Stub returned in the
18 ``attachments`` field; full join logic lives in `link_index.py` Phase 3.5.
19
20 Public API
21 ----------
22 - :class:`ResolvedLink` — a single resolved edge from one note to another.
23 - :class:`LinkIndex` — full vault index with forward / backward / entity edges.
24 - :func:`extract_wikilinks` — extract raw wikilink targets from a note body.
25 - :func:`extract_md_links` — extract raw markdown-to-md links from a note body.
26 - :func:`build_link_index` — walk a vault directory and assemble a full index.
27
28 Resolver semantics (OBA-reviewed)
29 ---------------------------------
30
31 ``case sensitivity``
32 The resolver is **case-insensitive on basenames** to match Obsidian and
33 macOS HFS+/APFS default behaviour. Two notes with the same basename in
34 different cases are treated as duplicates and a warning is logged.
35
36 ``fragment handling``
37 ``[[note#section]]`` resolves the *note* portion; the section fragment is
38 stored on the :class:`ResolvedLink` for downstream consumers but is not
39 used to disambiguate the target note.
40
41 ``relative path resolution``
42 Markdown links of the form ``[text](path.md)`` are resolved relative to
43 the *current note's directory*. ``./`` and ``../`` are normalised via
44 :class:`pathlib.PurePosixPath`. Absolute paths (leading ``/``) are
45 treated as vault-root-relative. Paths escaping the vault root are
46 rejected (broken-link semantics, see below).
47
48 ``broken-link semantics``
49 Wikilinks or markdown links whose target cannot be resolved to a vault
50 note become a :class:`ResolvedLink` with ``target=None`` and
51 ``broken=True``. Callers (``muse code deps`` / ``impact``) can filter on
52 ``broken`` to choose between strict and lenient modes.
53
54 ``URL fragments and external links``
55 Markdown links starting with ``http://``, ``https://``, ``mailto:``, or
56 any other scheme are ignored — only relative ``.md`` references count.
57 """
58
59 from __future__ import annotations
60
61 import logging
62 import os
63 import pathlib
64 import re
65 from dataclasses import dataclass, field
66 from typing import Iterator
67
68 from muse.plugins.knowtation._query import is_note
69 from muse.plugins.knowtation.parser import parse_frontmatter
70
71 logger = logging.getLogger(__name__)
72
73
74 # ---------------------------------------------------------------------------
75 # Regex patterns
76 # ---------------------------------------------------------------------------
77
78 #: Obsidian wikilink — ``[[target|alias]]`` or ``[[target#section]]`` or
79 #: ``[[target]]``. Capture groups: (1) target, (2) section, (3) alias.
80 #:
81 #: Ported from knowtation/lib/wikilink.mjs. The character class excludes ``]``,
82 #: ``|``, ``#`` from the target to prevent runaway matches.
83 _WIKILINK_RE: re.Pattern[str] = re.compile(
84 r"\[\[([^\]|#]+)(?:#([^\]|]+))?(?:\|([^\]]+))?\]\]"
85 )
86
87 #: Markdown link to a ``.md`` file (or fragment). Matches:
88 #: [text](path.md)
89 #: [text](./path.md)
90 #: [text](../sub/note.md)
91 #: [text](note.md#heading)
92 #:
93 #: Excludes URL schemes (``http:``, ``mailto:``, etc.) via the negative
94 #: lookahead ``(?![a-z][a-z0-9+.\-]*:)``.
95 _MD_LINK_RE: re.Pattern[str] = re.compile(
96 r"\[([^\]]+)\]" # [text]
97 r"\(" # (
98 r"(?![a-z][a-z0-9+.\-]*:)" # not http://, mailto:, etc.
99 r"([^)\s]+?\.md)" # path ending in .md
100 r"(?:#([^)\s]+))?" # optional #fragment
101 r"\)" # )
102 )
103
104 #: Schemes that mark a markdown link as external — never treated as note edges.
105 _EXTERNAL_SCHEMES: frozenset[str] = frozenset(
106 {"http", "https", "ftp", "mailto", "tel", "file", "data"}
107 )
108
109
110 # ---------------------------------------------------------------------------
111 # Data classes
112 # ---------------------------------------------------------------------------
113
114
115 @dataclass(frozen=True)
116 class ResolvedLink:
117 """A single inter-note edge with both raw and resolved forms.
118
119 Attributes:
120 source: Vault-relative POSIX path of the note containing the link.
121 target: Vault-relative POSIX path of the resolved target note, or
122 ``None`` when the link is broken.
123 raw: The original link text as written in the source note
124 (e.g. ``"Some Note"`` or ``"../folder/note.md"``).
125 kind: Edge kind: ``"wikilink"``, ``"md_link"``, ``"entity"``,
126 or ``"attachment"``.
127 fragment: Optional section/heading fragment (e.g. ``"§Summary"``)
128 when present in the original link. Empty string when
129 no fragment.
130 broken: ``True`` when the link's target could not be resolved
131 to an existing vault note.
132 alias: Display alias for wikilinks (the text after ``|``);
133 empty string when none.
134 """
135
136 source: str
137 target: str | None
138 raw: str
139 kind: str
140 fragment: str = ""
141 broken: bool = False
142 alias: str = ""
143
144
145 @dataclass
146 class LinkIndex:
147 """Forward and reverse edge index for an entire Knowtation vault.
148
149 Attributes:
150 forward: ``source → [ResolvedLink, …]`` — every link in every note.
151 backward: ``target → [ResolvedLink, …]`` — only resolved (non-broken) links.
152 broken_links: List of :class:`ResolvedLink` with ``broken=True``.
153 entity_index: ``entity_label → set[note_path]`` for entity co-occurrence.
154 attachment_index: ``mist_id → set[note_path]`` for mist-attachment
155 co-occurrence (Phase 3.5).
156 notes_indexed: Total notes walked during construction.
157 duplicate_basenames: Basenames that appeared in more than one folder
158 (logged as warnings; the *first* path in walk order wins).
159 """
160
161 forward: dict[str, list[ResolvedLink]] = field(default_factory=dict)
162 backward: dict[str, list[ResolvedLink]] = field(default_factory=dict)
163 broken_links: list[ResolvedLink] = field(default_factory=list)
164 entity_index: dict[str, set[str]] = field(default_factory=dict)
165 attachment_index: dict[str, set[str]] = field(default_factory=dict)
166 notes_indexed: int = 0
167 duplicate_basenames: dict[str, list[str]] = field(default_factory=dict)
168
169 # ------------------------------------------------------------------
170 # Lookup helpers
171 # ------------------------------------------------------------------
172
173 def outgoing(self, source: str) -> list[ResolvedLink]:
174 """Return all links originating at *source*. Empty list if none."""
175 return list(self.forward.get(source, []))
176
177 def incoming(self, target: str) -> list[ResolvedLink]:
178 """Return all resolved links pointing at *target*. Empty list if none."""
179 return list(self.backward.get(target, []))
180
181 def co_entity(self, note_path: str) -> set[str]:
182 """Return notes that share at least one entity label with *note_path*.
183
184 Args:
185 note_path: Vault-relative POSIX path of the seed note.
186
187 Returns:
188 Set of other note paths sharing at least one entity label.
189 Excludes *note_path* itself.
190 """
191 out: set[str] = set()
192 for entity_label, members in self.entity_index.items():
193 if note_path in members:
194 out.update(members)
195 out.discard(note_path)
196 return out
197
198 def co_attachment(self, note_path: str) -> set[str]:
199 """Return notes that share at least one mist attachment with *note_path*.
200
201 Two notes are "co-attached" when both reference the same mist artefact
202 ID in their ``frontmatter.attachments[*]``. Useful for
203 ``muse code entangle`` and ``muse code impact --include-attachments``.
204
205 Args:
206 note_path: Vault-relative POSIX path of the seed note.
207
208 Returns:
209 Set of other note paths sharing at least one mist attachment ID.
210 Excludes *note_path* itself.
211 """
212 out: set[str] = set()
213 for _mist_id, members in self.attachment_index.items():
214 if note_path in members:
215 out.update(members)
216 out.discard(note_path)
217 return out
218
219
220 # ---------------------------------------------------------------------------
221 # Wikilink helpers (semantic parity with lib/wikilink.mjs)
222 # ---------------------------------------------------------------------------
223
224
225 def _wikilink_target_key(raw: str) -> str:
226 """Normalise wikilink inner text to a comparable basename stem.
227
228 Mirrors ``wikilinkTargetKey`` in ``lib/wikilink.mjs``:
229
230 - Trim whitespace.
231 - Take the last path segment (split on ``/`` or ``\\``).
232 - Strip a trailing ``.md`` (case-insensitive).
233 - Lowercase.
234
235 Args:
236 raw: The raw wikilink target text (between ``[[`` and the next
237 special character).
238
239 Returns:
240 Lowercase comparable key.
241 """
242 s = str(raw).strip()
243 if not s:
244 return ""
245 last = re.split(r"[/\\]", s)[-1]
246 if last.lower().endswith(".md"):
247 last = last[:-3]
248 return last.lower()
249
250
251 def _vault_basename_key(vault_path: str) -> str:
252 """Return the comparable basename key for *vault_path*.
253
254 Mirrors ``vaultBasenameTargetKey`` in ``lib/wikilink.mjs``.
255
256 Args:
257 vault_path: Vault-relative POSIX path.
258
259 Returns:
260 Lowercase basename stem (no ``.md`` extension).
261 """
262 target = vault_path.replace("\\", "/")
263 last = target.split("/")[-1] or target
264 return _wikilink_target_key(last)
265
266
267 # ---------------------------------------------------------------------------
268 # Public extractors
269 # ---------------------------------------------------------------------------
270
271
272 def extract_wikilinks(body: str) -> list[tuple[str, str, str]]:
273 """Extract all wikilinks from *body* in source order.
274
275 Args:
276 body: Markdown body text (NOT bytes, NOT including frontmatter).
277
278 Returns:
279 List of ``(target, fragment, alias)`` tuples. ``fragment`` and
280 ``alias`` are empty strings when absent.
281 """
282 out: list[tuple[str, str, str]] = []
283 for m in _WIKILINK_RE.finditer(body):
284 target = m.group(1).strip()
285 fragment = (m.group(2) or "").strip()
286 alias = (m.group(3) or "").strip()
287 out.append((target, fragment, alias))
288 return out
289
290
291 def extract_md_links(body: str) -> list[tuple[str, str, str]]:
292 """Extract all ``[text](path.md)`` markdown links from *body*.
293
294 Args:
295 body: Markdown body text.
296
297 Returns:
298 List of ``(path, fragment, text)`` tuples. Only relative ``.md``
299 paths are returned; URLs are excluded.
300 """
301 out: list[tuple[str, str, str]] = []
302 for m in _MD_LINK_RE.finditer(body):
303 text = m.group(1).strip()
304 path = m.group(2).strip()
305 fragment = (m.group(3) or "").strip()
306 out.append((path, fragment, text))
307 return out
308
309
310 # ---------------------------------------------------------------------------
311 # Path resolution
312 # ---------------------------------------------------------------------------
313
314
315 def _normalise_rel_path(source_dir: str, rel_path: str) -> str | None:
316 """Resolve *rel_path* relative to *source_dir* without leaving the vault.
317
318 Args:
319 source_dir: Vault-relative POSIX directory of the source note
320 (e.g. ``"projects/born-free"``; ``""`` for vault root).
321 rel_path: Relative path from the source note (e.g. ``"../foo.md"``).
322
323 Returns:
324 The resolved vault-relative POSIX path, or ``None`` if the resolved
325 path escapes the vault root (security check).
326 """
327 if rel_path.startswith("/"):
328 candidate = pathlib.PurePosixPath(rel_path.lstrip("/"))
329 else:
330 candidate = pathlib.PurePosixPath(source_dir) / rel_path
331
332 parts: list[str] = []
333 for part in candidate.parts:
334 if part == "." or part == "":
335 continue
336 if part == "..":
337 if not parts:
338 return None
339 parts.pop()
340 continue
341 parts.append(part)
342
343 return "/".join(parts)
344
345
346 def _resolve_wikilink(
347 raw: str,
348 basename_to_path: dict[str, str],
349 ) -> str | None:
350 """Resolve a wikilink target to a vault-relative path.
351
352 Uses case-insensitive basename matching (Obsidian / macOS semantics).
353
354 Args:
355 raw: The raw wikilink target text.
356 basename_to_path: Pre-built map of lowercase basename stem → vault path.
357
358 Returns:
359 The resolved vault-relative POSIX path, or ``None`` if no match.
360 """
361 key = _wikilink_target_key(raw)
362 if not key:
363 return None
364 return basename_to_path.get(key)
365
366
367 def _resolve_md_link(
368 source_path: str,
369 raw_path: str,
370 existing_paths: set[str],
371 ) -> str | None:
372 """Resolve a markdown link relative path against the vault.
373
374 Args:
375 source_path: Vault-relative POSIX path of the source note.
376 raw_path: Raw link path (e.g. ``"../foo.md"``).
377 existing_paths: Set of all known vault note paths.
378
379 Returns:
380 Resolved vault-relative path, or ``None`` if it doesn't exist or
381 escapes the vault.
382 """
383 source_dir = "/".join(source_path.split("/")[:-1])
384 resolved = _normalise_rel_path(source_dir, raw_path)
385 if resolved is None:
386 return None
387 if resolved in existing_paths:
388 return resolved
389 # Case-insensitive fallback for macOS / Windows behaviour parity.
390 lower = resolved.lower()
391 for p in existing_paths:
392 if p.lower() == lower:
393 return p
394 return None
395
396
397 # ---------------------------------------------------------------------------
398 # Vault traversal
399 # ---------------------------------------------------------------------------
400
401 #: Directories pruned from vault walks (template scaffolding, meta, hidden).
402 _IGNORE_DIRS: frozenset[str] = frozenset(
403 {"templates", "meta", "node_modules", "__pycache__", ".muse"}
404 )
405
406 #: Per-note size cap for body reads — defends against oversized files.
407 _MAX_NOTE_BYTES: int = 16 * 1024 * 1024 # 16 MiB
408
409
410 def _iter_vault_notes(root: pathlib.Path) -> Iterator[pathlib.Path]:
411 """Yield :class:`pathlib.Path` for every Markdown note in *root*.
412
413 Args:
414 root: Vault root directory.
415
416 Yields:
417 Absolute paths to ``.md`` / ``.markdown`` / ``.mdx`` files.
418 """
419 root_str = str(root)
420 for dirpath, dirnames, filenames in os.walk(root_str, followlinks=False):
421 dirnames[:] = sorted(
422 d for d in dirnames if d not in _IGNORE_DIRS and not d.startswith(".")
423 )
424 for fname in sorted(filenames):
425 if is_note(fname):
426 yield pathlib.Path(dirpath) / fname
427
428
429 def _read_note_safely(path: pathlib.Path) -> bytes | None:
430 """Read *path* with a size cap; return ``None`` on failure or oversize."""
431 try:
432 size = path.stat().st_size
433 except OSError:
434 return None
435 if size > _MAX_NOTE_BYTES:
436 logger.warning("link_index: skipping oversized note %s (%d bytes)", path, size)
437 return None
438 try:
439 return path.read_bytes()
440 except OSError:
441 return None
442
443
444 # ---------------------------------------------------------------------------
445 # Main builder
446 # ---------------------------------------------------------------------------
447
448
449 def build_link_index(root: pathlib.Path) -> LinkIndex:
450 """Build a :class:`LinkIndex` for the vault rooted at *root*.
451
452 Walks the vault once, parsing wikilinks, markdown-md links, and entity
453 frontmatter values for every note. Resolves edges using case-insensitive
454 basename matching (Obsidian / macOS semantics) and relative-path
455 resolution from each note's directory.
456
457 Args:
458 root: Vault root directory.
459
460 Returns:
461 Fully populated :class:`LinkIndex`.
462
463 Raises:
464 ValueError: When *root* does not exist or is not a directory.
465
466 Performance: < 10s on a 5k-note vault (verified by test_knowtation_link_index.py).
467 """
468 if not root.exists() or not root.is_dir():
469 raise ValueError(f"link_index: root {root!r} is not a directory")
470
471 root = root.resolve()
472
473 # ── Pass 1: enumerate all notes and build the basename lookup table. ──
474 note_paths: list[str] = []
475 basename_to_path: dict[str, str] = {}
476 duplicates: dict[str, list[str]] = {}
477
478 for abs_path in _iter_vault_notes(root):
479 rel_path = abs_path.relative_to(root).as_posix()
480 note_paths.append(rel_path)
481 key = _vault_basename_key(rel_path)
482 if key in basename_to_path:
483 existing = basename_to_path[key]
484 duplicates.setdefault(key, [existing]).append(rel_path)
485 logger.debug(
486 "link_index: duplicate basename %r (keeping %r, ignoring %r)",
487 key, existing, rel_path,
488 )
489 else:
490 basename_to_path[key] = rel_path
491
492 existing_paths: set[str] = set(note_paths)
493
494 # ── Pass 2: extract links and build edges. ───────────────────────────
495 index = LinkIndex(
496 notes_indexed=len(note_paths),
497 duplicate_basenames=duplicates,
498 )
499
500 for rel_path in note_paths:
501 abs_path = root / rel_path
502 content = _read_note_safely(abs_path)
503 if content is None:
504 continue
505
506 try:
507 body_text = content.decode("utf-8", errors="replace")
508 except Exception:
509 continue
510
511 # Strip frontmatter so links inside YAML aren't matched as body text.
512 body = _strip_frontmatter(body_text)
513
514 links: list[ResolvedLink] = []
515
516 # Wikilinks ────────────────────────────────────────────────────
517 for raw, fragment, alias in extract_wikilinks(body):
518 resolved = _resolve_wikilink(raw, basename_to_path)
519 link = ResolvedLink(
520 source=rel_path,
521 target=resolved,
522 raw=raw,
523 kind="wikilink",
524 fragment=fragment,
525 broken=resolved is None,
526 alias=alias,
527 )
528 links.append(link)
529
530 # Markdown .md links ───────────────────────────────────────────
531 for raw_path, fragment, text in extract_md_links(body):
532 resolved = _resolve_md_link(rel_path, raw_path, existing_paths)
533 link = ResolvedLink(
534 source=rel_path,
535 target=resolved,
536 raw=raw_path,
537 kind="md_link",
538 fragment=fragment,
539 broken=resolved is None,
540 alias=text,
541 )
542 links.append(link)
543
544 # Entity frontmatter values — build co-occurrence index ───────
545 # Mist attachment IDs — build third co-occurrence index (Phase 3.5).
546 fm = parse_frontmatter(content)
547 if fm is not None:
548 for entity_label in fm.entity:
549 lbl = entity_label.strip()
550 if not lbl:
551 continue
552 index.entity_index.setdefault(lbl, set()).add(rel_path)
553 from muse.plugins.knowtation._query import is_valid_mist_id # noqa: PLC0415
554
555 for mist_id in fm.attachments:
556 mid = mist_id.strip()
557 if not mid or not is_valid_mist_id(mid):
558 continue
559 index.attachment_index.setdefault(mid, set()).add(rel_path)
560
561 index.forward[rel_path] = links
562 for link in links:
563 if link.target and not link.broken:
564 index.backward.setdefault(link.target, []).append(link)
565 else:
566 index.broken_links.append(link)
567
568 return index
569
570
571 # ---------------------------------------------------------------------------
572 # Frontmatter stripping
573 # ---------------------------------------------------------------------------
574
575 _FM_START_RE: re.Pattern[str] = re.compile(r"\A---\s*\n")
576
577
578 def _strip_frontmatter(text: str) -> str:
579 """Return *text* with the leading YAML frontmatter block removed.
580
581 Args:
582 text: Full note text including any frontmatter.
583
584 Returns:
585 Body text (everything after the closing ``---`` line), or the
586 original text if no frontmatter is present.
587 """
588 if not _FM_START_RE.match(text):
589 return text
590 after_start = text.split("\n", 1)
591 if len(after_start) < 2:
592 return text
593 rest = after_start[1]
594 for delim in ("\n---", "\n..."):
595 idx = rest.find(delim)
596 if idx != -1:
597 return rest[idx + len(delim):]
598 return text
File History 1 commit
sha256:d8316ffae901be06347e16ab55be11868eb519dd16ade3e8aa16a99e662f7e62 baseline: rc14 re-baseline after rc3 store corruption recovery Human patch 27 days ago