test_knowtation_differ.py
file-level
1
files
1
commits
0
hotspots
0
🧊 dead
0
💥 blast risk
| 1 | """Tests for ``muse/plugins/knowtation/differ.py`` — Phase 2.1. |
| 2 | |
| 3 | This suite covers every test tier required by Rule #0: |
| 4 | |
| 5 | 1. **Unit** — per-layer behaviour (title, frontmatter scalar, tag |
| 6 | add/remove, section add/remove/move, body line edit), |
| 7 | helpers (``_content_id``, ``_stringify``, |
| 8 | ``_section_id``, address parsing, canonicalisation). |
| 9 | 2. **Integration** — ``diff_notes`` over realistic note pairs returns the |
| 10 | expected op shape for a known fixture. |
| 11 | 3. **End-to-end** — ``apply(diff_notes(A, B), A) == B`` for 20 hand-crafted |
| 12 | note pairs spanning all edge cases (empty input, |
| 13 | frontmatter-only, no frontmatter, single section, |
| 14 | many sections, deep section bodies, set field |
| 15 | churn, scalar field add/remove, title creation, |
| 16 | title deletion, section moves, etc.). |
| 17 | 4. **Data integrity** — 200 ``hypothesis``-generated note pairs assert the |
| 18 | round-trip invariant. |
| 19 | 5. **Performance** — a realistic 50-section note diffs in < 100 ms. |
| 20 | 6. **Stress** — 200 mixed note pairs diff + apply sequentially in |
| 21 | under 5 s. |
| 22 | 7. **Security** — adversarial inputs (binary blobs, NUL bytes, very |
| 23 | long lines, deeply nested YAML, oversized notes) |
| 24 | either return cleanly or raise the documented |
| 25 | ``ValueError``; never crash, never expose secrets. |
| 26 | |
| 27 | Conventions |
| 28 | ----------- |
| 29 | * Every helper returns canonical-form bytes so the round-trip invariant |
| 30 | is byte-stable. |
| 31 | * The ``_note`` helper builds a canonical note from a frontmatter mapping |
| 32 | plus body text. |
| 33 | * Hypothesis strategies use only printable ASCII so generated frontmatter |
| 34 | values round-trip through YAML deterministically without quoting |
| 35 | surprises. |
| 36 | """ |
| 37 | |
| 38 | from __future__ import annotations |
| 39 | |
| 40 | import string |
| 41 | import time |
| 42 | from typing import Any |
| 43 | |
| 44 | import pytest |
| 45 | import yaml |
| 46 | from hypothesis import HealthCheck, given, settings, strategies as st |
| 47 | |
| 48 | from muse.plugins.knowtation.differ import ( |
| 49 | _FM_PREFIX, |
| 50 | _LINE_INFIX, |
| 51 | _MAX_NOTE_BYTES, |
| 52 | _SECTION_PREFIX, |
| 53 | _TITLE_ADDR, |
| 54 | _content_id, |
| 55 | _diff_body_lines, |
| 56 | _diff_frontmatter, |
| 57 | _diff_sections, |
| 58 | _diff_title, |
| 59 | _parse_note, |
| 60 | _section_from_address, |
| 61 | _section_id, |
| 62 | _split_sections_typed, |
| 63 | _stringify, |
| 64 | apply, |
| 65 | canonicalize, |
| 66 | diff_notes, |
| 67 | ) |
| 68 | |
| 69 | |
| 70 | # ───────────────────────────────────────────────────────────────────────────── |
| 71 | # Note construction helpers |
| 72 | # ───────────────────────────────────────────────────────────────────────────── |
| 73 | |
| 74 | |
| 75 | def _build_note(frontmatter: dict[str, Any] | None, body: str) -> bytes: |
| 76 | """Construct canonical-form note bytes from a frontmatter dict + body. |
| 77 | |
| 78 | Always passes through :func:`canonicalize` so the result is the byte- |
| 79 | stable form that the differ guarantees to round-trip. |
| 80 | |
| 81 | Args: |
| 82 | frontmatter: Frontmatter mapping (``None`` for no frontmatter). |
| 83 | body: Body text (post-frontmatter). |
| 84 | |
| 85 | Returns: |
| 86 | Canonical-form note bytes. |
| 87 | """ |
| 88 | if not frontmatter: |
| 89 | return canonicalize(body.encode("utf-8")) |
| 90 | yaml_text = yaml.safe_dump( |
| 91 | frontmatter, |
| 92 | sort_keys=False, |
| 93 | default_flow_style=False, |
| 94 | allow_unicode=True, |
| 95 | width=10000, |
| 96 | ) |
| 97 | raw = f"---\n{yaml_text}---\n{body}".encode("utf-8") |
| 98 | return canonicalize(raw) |
| 99 | |
| 100 | |
| 101 | def _round_trip(a: bytes, b: bytes) -> None: |
| 102 | """Assert ``apply(diff_notes(A, B), A) == B`` for canonical inputs. |
| 103 | |
| 104 | Args: |
| 105 | a: Base note bytes (canonical form). |
| 106 | b: Target note bytes (canonical form). |
| 107 | |
| 108 | Raises: |
| 109 | AssertionError: When the round-trip fails. |
| 110 | """ |
| 111 | delta = diff_notes(a, b) |
| 112 | out = apply(delta, a) |
| 113 | assert out == b, ( |
| 114 | f"Round-trip mismatch.\n" |
| 115 | f"--- expected ---\n{b.decode('utf-8', errors='replace')}\n" |
| 116 | f"--- got ---\n{out.decode('utf-8', errors='replace')}\n" |
| 117 | f"--- ops ---\n{delta.get('ops')}" |
| 118 | ) |
| 119 | |
| 120 | |
| 121 | # ============================================================================= |
| 122 | # Tier 1 — Unit tests |
| 123 | # ============================================================================= |
| 124 | |
| 125 | |
| 126 | class TestStringifyAndContentId: |
| 127 | """Unit tests for the small scalar helpers.""" |
| 128 | |
| 129 | def test_stringify_none(self) -> None: |
| 130 | assert _stringify(None) == "" |
| 131 | |
| 132 | def test_stringify_bool_true(self) -> None: |
| 133 | assert _stringify(True) == "true" |
| 134 | |
| 135 | def test_stringify_bool_false(self) -> None: |
| 136 | assert _stringify(False) == "false" |
| 137 | |
| 138 | def test_stringify_int(self) -> None: |
| 139 | assert _stringify(42) == "42" |
| 140 | |
| 141 | def test_stringify_str(self) -> None: |
| 142 | assert _stringify("hello") == "hello" |
| 143 | |
| 144 | def test_content_id_deterministic(self) -> None: |
| 145 | assert _content_id("hello") == _content_id("hello") |
| 146 | |
| 147 | def test_content_id_hex_length(self) -> None: |
| 148 | assert len(_content_id("hello")) == 64 |
| 149 | assert all(c in string.hexdigits for c in _content_id("hello")) |
| 150 | |
| 151 | def test_content_id_different_inputs_differ(self) -> None: |
| 152 | assert _content_id("a") != _content_id("b") |
| 153 | |
| 154 | |
| 155 | class TestSectionIdAndAddress: |
| 156 | """Unit tests for section-ID encoding and reverse parsing.""" |
| 157 | |
| 158 | def test_section_id_format(self) -> None: |
| 159 | assert _section_id(2, "Background", 0) == "section:2:Background#0" |
| 160 | |
| 161 | def test_section_id_preamble(self) -> None: |
| 162 | assert _section_id(0, "(preamble)", 0) == "section:0:(preamble)#0" |
| 163 | |
| 164 | def test_section_from_address_basic(self) -> None: |
| 165 | sec = _section_from_address("section:2:Background#0", "## Background\n\nbody\n") |
| 166 | assert sec.level == 2 |
| 167 | assert sec.title == "Background" |
| 168 | assert sec.text == "## Background\n\nbody\n" |
| 169 | assert sec.sid == "section:2:Background#0" |
| 170 | |
| 171 | def test_section_from_address_title_with_hash(self) -> None: |
| 172 | sec = _section_from_address("section:2:Issue #42#1", "## Issue #42\n") |
| 173 | assert sec.level == 2 |
| 174 | assert sec.title == "Issue #42" |
| 175 | |
| 176 | def test_section_from_address_malformed_defaults_safe(self) -> None: |
| 177 | sec = _section_from_address("not-a-section", "body") |
| 178 | assert sec.level == 0 |
| 179 | assert sec.title == "(preamble)" |
| 180 | assert sec.text == "body" |
| 181 | |
| 182 | |
| 183 | class TestParseNoteAndCanonicalize: |
| 184 | """Unit tests for ``_parse_note`` / ``canonicalize`` invariants.""" |
| 185 | |
| 186 | def test_parse_empty_note(self) -> None: |
| 187 | parsed = _parse_note(b"") |
| 188 | assert parsed.frontmatter == {} |
| 189 | assert parsed.body == "" |
| 190 | |
| 191 | def test_parse_no_frontmatter(self) -> None: |
| 192 | parsed = _parse_note(b"# Just a heading\n\nbody\n") |
| 193 | assert parsed.frontmatter == {} |
| 194 | assert parsed.body == "# Just a heading\n\nbody\n" |
| 195 | |
| 196 | def test_parse_with_frontmatter(self) -> None: |
| 197 | parsed = _parse_note(b"---\ntitle: X\n---\n# body\n") |
| 198 | assert parsed.frontmatter == {"title": "X"} |
| 199 | assert parsed.body == "# body\n" |
| 200 | |
| 201 | def test_parse_crlf_normalised(self) -> None: |
| 202 | parsed = _parse_note(b"---\r\ntitle: X\r\n---\r\nbody\r\n") |
| 203 | assert parsed.frontmatter == {"title": "X"} |
| 204 | assert "\r" not in parsed.body |
| 205 | |
| 206 | def test_parse_oversize_raises(self) -> None: |
| 207 | oversize = b"x" * (_MAX_NOTE_BYTES + 1) |
| 208 | with pytest.raises(ValueError): |
| 209 | _parse_note(oversize) |
| 210 | |
| 211 | def test_canonicalize_idempotent(self) -> None: |
| 212 | raw = b"---\ntags:\n- b\n- a\ntitle: X\n---\nbody\n" |
| 213 | once = canonicalize(raw) |
| 214 | twice = canonicalize(once) |
| 215 | assert once == twice |
| 216 | |
| 217 | def test_canonicalize_sorts_tags_and_hoists_title(self) -> None: |
| 218 | raw = b"---\nproject: zeta\ntitle: X\ntags:\n- z\n- a\n---\nbody\n" |
| 219 | out = canonicalize(raw) |
| 220 | decoded = out.decode("utf-8") |
| 221 | # Title appears before project in canonical output |
| 222 | assert decoded.index("title:") < decoded.index("project:") |
| 223 | # Tags appear sorted (a before z) |
| 224 | assert decoded.index("- a") < decoded.index("- z") |
| 225 | |
| 226 | def test_canonicalize_no_frontmatter_passthrough(self) -> None: |
| 227 | raw = b"# H\nbody\n" |
| 228 | assert canonicalize(raw) == raw |
| 229 | |
| 230 | |
| 231 | class TestSplitSectionsTyped: |
| 232 | """Unit tests for the section splitter with ID assignment.""" |
| 233 | |
| 234 | def test_empty_body(self) -> None: |
| 235 | assert _split_sections_typed("") == [] |
| 236 | |
| 237 | def test_preamble_only(self) -> None: |
| 238 | sections = _split_sections_typed("just text\n") |
| 239 | assert len(sections) == 1 |
| 240 | assert sections[0].level == 0 |
| 241 | assert sections[0].title == "(preamble)" |
| 242 | |
| 243 | def test_duplicate_titles_get_occurrence_indices(self) -> None: |
| 244 | body = "## Foo\n\nbody1\n\n## Foo\n\nbody2\n" |
| 245 | sections = _split_sections_typed(body) |
| 246 | assert [s.sid for s in sections] == [ |
| 247 | "section:2:Foo#0", |
| 248 | "section:2:Foo#1", |
| 249 | ] |
| 250 | |
| 251 | def test_concat_round_trip(self) -> None: |
| 252 | body = "# H1\n\nbody\n\n## H2\n\nmore\n" |
| 253 | sections = _split_sections_typed(body) |
| 254 | assert "".join(s.text for s in sections) == body |
| 255 | |
| 256 | |
| 257 | class TestLayer1TitleDiff: |
| 258 | """Unit tests for Layer 1 — title diff.""" |
| 259 | |
| 260 | def test_no_change_no_ops(self) -> None: |
| 261 | a = _parse_note(b"---\ntitle: X\n---\n") |
| 262 | b = _parse_note(b"---\ntitle: X\n---\n") |
| 263 | assert _diff_title(a, b) == [] |
| 264 | |
| 265 | def test_title_changed_emits_replace(self) -> None: |
| 266 | a = _parse_note(b"---\ntitle: X\n---\n") |
| 267 | b = _parse_note(b"---\ntitle: Y\n---\n") |
| 268 | ops = _diff_title(a, b) |
| 269 | assert len(ops) == 1 |
| 270 | op = ops[0] |
| 271 | assert op["op"] == "replace" |
| 272 | assert op["address"] == _TITLE_ADDR |
| 273 | assert op["old_summary"] == "X" |
| 274 | assert op["new_summary"] == "Y" |
| 275 | |
| 276 | def test_title_added_old_empty(self) -> None: |
| 277 | a = _parse_note(b"---\n{}\n---\n") |
| 278 | b = _parse_note(b"---\ntitle: New\n---\n") |
| 279 | ops = _diff_title(a, b) |
| 280 | assert len(ops) == 1 |
| 281 | assert ops[0]["old_summary"] == "" |
| 282 | assert ops[0]["new_summary"] == "New" |
| 283 | |
| 284 | def test_title_removed_new_empty(self) -> None: |
| 285 | a = _parse_note(b"---\ntitle: Old\n---\n") |
| 286 | b = _parse_note(b"---\nproject: x\n---\n") |
| 287 | ops = _diff_title(a, b) |
| 288 | assert len(ops) == 1 |
| 289 | assert ops[0]["old_summary"] == "Old" |
| 290 | assert ops[0]["new_summary"] == "" |
| 291 | |
| 292 | |
| 293 | class TestLayer2FrontmatterDiff: |
| 294 | """Unit tests for Layer 2 — frontmatter diff.""" |
| 295 | |
| 296 | def test_scalar_change_emits_replace(self) -> None: |
| 297 | a = _parse_note(b"---\ntitle: X\nproject: alpha\n---\n") |
| 298 | b = _parse_note(b"---\ntitle: X\nproject: beta\n---\n") |
| 299 | ops = _diff_frontmatter(a, b) |
| 300 | assert len(ops) == 1 |
| 301 | assert ops[0]["op"] == "replace" |
| 302 | assert ops[0]["address"] == f"{_FM_PREFIX}project" |
| 303 | assert ops[0]["old_summary"] == "alpha" |
| 304 | assert ops[0]["new_summary"] == "beta" |
| 305 | |
| 306 | def test_scalar_added_emits_insert(self) -> None: |
| 307 | a = _parse_note(b"---\ntitle: X\n---\n") |
| 308 | b = _parse_note(b"---\ntitle: X\nproject: p\n---\n") |
| 309 | ops = _diff_frontmatter(a, b) |
| 310 | assert len(ops) == 1 |
| 311 | assert ops[0]["op"] == "insert" |
| 312 | assert ops[0]["address"] == f"{_FM_PREFIX}project" |
| 313 | |
| 314 | def test_scalar_removed_emits_delete(self) -> None: |
| 315 | a = _parse_note(b"---\ntitle: X\nproject: p\n---\n") |
| 316 | b = _parse_note(b"---\ntitle: X\n---\n") |
| 317 | ops = _diff_frontmatter(a, b) |
| 318 | assert len(ops) == 1 |
| 319 | assert ops[0]["op"] == "delete" |
| 320 | |
| 321 | def test_tag_added(self) -> None: |
| 322 | a = _parse_note(b"---\ntags: [a]\n---\n") |
| 323 | b = _parse_note(b"---\ntags: [a, b]\n---\n") |
| 324 | ops = _diff_frontmatter(a, b) |
| 325 | assert len(ops) == 1 |
| 326 | assert ops[0]["op"] == "insert" |
| 327 | assert ops[0]["content_summary"] == "b" |
| 328 | |
| 329 | def test_tag_removed(self) -> None: |
| 330 | a = _parse_note(b"---\ntags: [a, b]\n---\n") |
| 331 | b = _parse_note(b"---\ntags: [a]\n---\n") |
| 332 | ops = _diff_frontmatter(a, b) |
| 333 | assert len(ops) == 1 |
| 334 | assert ops[0]["op"] == "delete" |
| 335 | assert ops[0]["content_summary"] == "b" |
| 336 | |
| 337 | def test_tag_swap_emits_delete_and_insert(self) -> None: |
| 338 | a = _parse_note(b"---\ntags: [a]\n---\n") |
| 339 | b = _parse_note(b"---\ntags: [b]\n---\n") |
| 340 | ops = _diff_frontmatter(a, b) |
| 341 | op_kinds = sorted(op["op"] for op in ops) |
| 342 | assert op_kinds == ["delete", "insert"] |
| 343 | |
| 344 | def test_excludes_title(self) -> None: |
| 345 | a = _parse_note(b"---\ntitle: X\nproject: p\n---\n") |
| 346 | b = _parse_note(b"---\ntitle: Y\nproject: q\n---\n") |
| 347 | ops = _diff_frontmatter(a, b) |
| 348 | addresses = [op["address"] for op in ops] |
| 349 | # Layer 2 must not emit ops for the title — that is Layer 1's job. |
| 350 | assert _TITLE_ADDR not in addresses |
| 351 | |
| 352 | |
| 353 | class TestLayer3SectionDiff: |
| 354 | """Unit tests for Layer 3 — section diff.""" |
| 355 | |
| 356 | def test_section_added_at_end(self) -> None: |
| 357 | sa = _split_sections_typed("# H\n\nbody\n") |
| 358 | sb = _split_sections_typed("# H\n\nbody\n\n## New\n\nnew body\n") |
| 359 | ops, stable = _diff_sections(sa, sb) |
| 360 | assert any(op["op"] == "insert" and op["address"].startswith(_SECTION_PREFIX) |
| 361 | for op in ops) |
| 362 | |
| 363 | def test_section_removed(self) -> None: |
| 364 | sa = _split_sections_typed("# H\n\n## X\n\nbody\n") |
| 365 | sb = _split_sections_typed("# H\n") |
| 366 | ops, _ = _diff_sections(sa, sb) |
| 367 | assert any(op["op"] == "delete" for op in ops) |
| 368 | |
| 369 | def test_section_move_emits_moveop(self) -> None: |
| 370 | # ``split_sections`` assigns each section the text from its heading |
| 371 | # up to the next heading. Trailing-newline counts therefore depend |
| 372 | # on whether the section is the *last* one or not. To get a clean |
| 373 | # move (byte-identical section text on both sides) the moved |
| 374 | # sections must live at *internal* positions in both notes — never |
| 375 | # at the very end. Below, X and Y swap places but both are |
| 376 | # surrounded by A/C/E on either side, so their texts are stable |
| 377 | # across the swap and detect_moves collapses the insert+delete |
| 378 | # pair into a MoveOp. |
| 379 | body_a = "## A\n\n## X\n\n## C\n\n## Y\n\n## E\n" |
| 380 | body_b = "## A\n\n## Y\n\n## C\n\n## X\n\n## E\n" |
| 381 | sa = _split_sections_typed(body_a) |
| 382 | sb = _split_sections_typed(body_b) |
| 383 | ops, _ = _diff_sections(sa, sb) |
| 384 | kinds = {op["op"] for op in ops} |
| 385 | assert "move" in kinds |
| 386 | |
| 387 | def test_unchanged_sections_marked_stable(self) -> None: |
| 388 | body = "# H\n\nbody\n\n## X\n\nbody2\n" |
| 389 | sa = _split_sections_typed(body) |
| 390 | sb = _split_sections_typed(body) |
| 391 | _, stable = _diff_sections(sa, sb) |
| 392 | assert "section:1:H#0" in stable |
| 393 | assert "section:2:X#0" in stable |
| 394 | |
| 395 | |
| 396 | class TestLayer4BodyLineDiff: |
| 397 | """Unit tests for Layer 4 — body line diff.""" |
| 398 | |
| 399 | def test_no_change_no_ops(self) -> None: |
| 400 | assert _diff_body_lines("sid", "a\nb\n", "a\nb\n") == [] |
| 401 | |
| 402 | def test_line_added(self) -> None: |
| 403 | ops = _diff_body_lines("sid", "a\nb", "a\nb\nc") |
| 404 | kinds = [op["op"] for op in ops] |
| 405 | assert "insert" in kinds |
| 406 | |
| 407 | def test_line_removed(self) -> None: |
| 408 | ops = _diff_body_lines("sid", "a\nb\nc", "a\nc") |
| 409 | kinds = [op["op"] for op in ops] |
| 410 | assert "delete" in kinds |
| 411 | |
| 412 | def test_line_changed(self) -> None: |
| 413 | ops = _diff_body_lines("sid", "a\nb\nc", "a\nX\nc") |
| 414 | kinds = [op["op"] for op in ops] |
| 415 | assert "insert" in kinds and "delete" in kinds |
| 416 | |
| 417 | def test_line_op_address_format(self) -> None: |
| 418 | ops = _diff_body_lines("section:2:H#0", "a", "a\nb") |
| 419 | for op in ops: |
| 420 | assert op["address"].startswith("section:2:H#0") |
| 421 | assert _LINE_INFIX in op["address"] |
| 422 | |
| 423 | |
| 424 | # ============================================================================= |
| 425 | # Tier 2 — Integration tests |
| 426 | # ============================================================================= |
| 427 | |
| 428 | |
| 429 | class TestDiffNotesIntegration: |
| 430 | """Integration tests across all four layers.""" |
| 431 | |
| 432 | def test_combined_changes(self) -> None: |
| 433 | a = _build_note( |
| 434 | {"title": "Foo", "project": "alpha", "tags": ["a", "b"]}, |
| 435 | "# Heading\n\nbody line 1\nbody line 2\n", |
| 436 | ) |
| 437 | b = _build_note( |
| 438 | {"title": "Bar", "project": "alpha", "tags": ["a", "c"]}, |
| 439 | "# Heading\n\nbody line 1\nbody line 3\n", |
| 440 | ) |
| 441 | delta = diff_notes(a, b) |
| 442 | assert delta["domain"] == "knowtation" |
| 443 | assert delta["ops"] |
| 444 | addresses = [op["address"] for op in delta["ops"]] |
| 445 | assert _TITLE_ADDR in addresses |
| 446 | assert any(addr.startswith(_FM_PREFIX) for addr in addresses) |
| 447 | assert any(_LINE_INFIX in addr for addr in addresses) |
| 448 | |
| 449 | def test_identical_notes_no_ops(self) -> None: |
| 450 | note = _build_note({"title": "X"}, "body\n") |
| 451 | delta = diff_notes(note, note) |
| 452 | assert delta["ops"] == [] |
| 453 | assert delta["summary"] == "no changes" |
| 454 | |
| 455 | def test_summary_is_string(self) -> None: |
| 456 | a = _build_note({"title": "A"}, "") |
| 457 | b = _build_note({"title": "B"}, "") |
| 458 | delta = diff_notes(a, b) |
| 459 | assert isinstance(delta["summary"], str) |
| 460 | assert delta["summary"] |
| 461 | |
| 462 | |
| 463 | # ============================================================================= |
| 464 | # Tier 3 — End-to-end round-trip (20 hand-crafted pairs) |
| 465 | # ============================================================================= |
| 466 | |
| 467 | |
| 468 | def _e2e_pairs() -> list[tuple[str, bytes, bytes]]: |
| 469 | """Return 20 hand-crafted (label, A, B) note pairs for round-trip tests. |
| 470 | |
| 471 | Each pair exercises a different edge case of the four-layer differ. |
| 472 | Both sides are pre-canonicalised so the round-trip is byte-stable. |
| 473 | |
| 474 | Returns: |
| 475 | List of ``(label, a, b)`` triples. |
| 476 | """ |
| 477 | pairs: list[tuple[str, bytes, bytes]] = [] |
| 478 | |
| 479 | pairs.append(("identical-empty", _build_note(None, ""), _build_note(None, ""))) |
| 480 | |
| 481 | pairs.append(( |
| 482 | "title-only-change", |
| 483 | _build_note({"title": "Old"}, ""), |
| 484 | _build_note({"title": "New"}, ""), |
| 485 | )) |
| 486 | |
| 487 | pairs.append(( |
| 488 | "title-added-from-nothing", |
| 489 | _build_note(None, "body\n"), |
| 490 | _build_note({"title": "Hello"}, "body\n"), |
| 491 | )) |
| 492 | |
| 493 | pairs.append(( |
| 494 | "title-removed", |
| 495 | _build_note({"title": "Hello", "project": "p"}, "body\n"), |
| 496 | _build_note({"project": "p"}, "body\n"), |
| 497 | )) |
| 498 | |
| 499 | pairs.append(( |
| 500 | "scalar-frontmatter-change", |
| 501 | _build_note({"title": "x", "project": "a"}, "body"), |
| 502 | _build_note({"title": "x", "project": "b"}, "body"), |
| 503 | )) |
| 504 | |
| 505 | pairs.append(( |
| 506 | "tag-added", |
| 507 | _build_note({"title": "x", "tags": ["a"]}, "body"), |
| 508 | _build_note({"title": "x", "tags": ["a", "b"]}, "body"), |
| 509 | )) |
| 510 | |
| 511 | pairs.append(( |
| 512 | "tag-removed", |
| 513 | _build_note({"title": "x", "tags": ["a", "b"]}, "body"), |
| 514 | _build_note({"title": "x", "tags": ["a"]}, "body"), |
| 515 | )) |
| 516 | |
| 517 | pairs.append(( |
| 518 | "tag-swap", |
| 519 | _build_note({"title": "x", "tags": ["a"]}, "body"), |
| 520 | _build_note({"title": "x", "tags": ["b"]}, "body"), |
| 521 | )) |
| 522 | |
| 523 | pairs.append(( |
| 524 | "entity-list-churn", |
| 525 | _build_note({"title": "x", "entity": ["alice", "bob"]}, "body"), |
| 526 | _build_note({"title": "x", "entity": ["bob", "carol"]}, "body"), |
| 527 | )) |
| 528 | |
| 529 | pairs.append(( |
| 530 | "section-added-at-end", |
| 531 | _build_note({"title": "x"}, "# H\n\nbody\n"), |
| 532 | _build_note({"title": "x"}, "# H\n\nbody\n\n## New\n\nnew body\n"), |
| 533 | )) |
| 534 | |
| 535 | pairs.append(( |
| 536 | "section-removed", |
| 537 | _build_note({"title": "x"}, "# H\n\n## Gone\n\nbye\n"), |
| 538 | _build_note({"title": "x"}, "# H\n"), |
| 539 | )) |
| 540 | |
| 541 | pairs.append(( |
| 542 | "section-body-changed", |
| 543 | _build_note({"title": "x"}, "# H\n\nold body line\n"), |
| 544 | _build_note({"title": "x"}, "# H\n\nnew body line\n"), |
| 545 | )) |
| 546 | |
| 547 | pairs.append(( |
| 548 | "body-line-inserted", |
| 549 | _build_note({"title": "x"}, "# H\n\nline 1\nline 3\n"), |
| 550 | _build_note({"title": "x"}, "# H\n\nline 1\nline 2\nline 3\n"), |
| 551 | )) |
| 552 | |
| 553 | pairs.append(( |
| 554 | "body-line-deleted", |
| 555 | _build_note({"title": "x"}, "# H\n\nline 1\nline 2\nline 3\n"), |
| 556 | _build_note({"title": "x"}, "# H\n\nline 1\nline 3\n"), |
| 557 | )) |
| 558 | |
| 559 | pairs.append(( |
| 560 | "no-frontmatter-both-sides", |
| 561 | _build_note(None, "just body\n"), |
| 562 | _build_note(None, "just body!\n"), |
| 563 | )) |
| 564 | |
| 565 | pairs.append(( |
| 566 | "frontmatter-added-from-none", |
| 567 | _build_note(None, "body\n"), |
| 568 | _build_note({"title": "x", "project": "p"}, "body\n"), |
| 569 | )) |
| 570 | |
| 571 | pairs.append(( |
| 572 | "frontmatter-removed-completely", |
| 573 | _build_note({"title": "x", "project": "p"}, "body\n"), |
| 574 | _build_note(None, "body\n"), |
| 575 | )) |
| 576 | |
| 577 | pairs.append(( |
| 578 | "many-sections-many-edits", |
| 579 | _build_note( |
| 580 | {"title": "x"}, |
| 581 | "## A\n\na\n\n## B\n\nb\n\n## C\n\nc\n\n## D\n\nd\n", |
| 582 | ), |
| 583 | _build_note( |
| 584 | {"title": "x"}, |
| 585 | "## A\n\na2\n\n## B\n\nb\n\n## E\n\ne\n\n## D\n\nd2\n", |
| 586 | ), |
| 587 | )) |
| 588 | |
| 589 | pairs.append(( |
| 590 | "preamble-changed-only", |
| 591 | _build_note({"title": "x"}, "preamble line 1\n\n# H\n"), |
| 592 | _build_note({"title": "x"}, "preamble line 1 changed\n\n# H\n"), |
| 593 | )) |
| 594 | |
| 595 | pairs.append(( |
| 596 | "duplicate-section-titles", |
| 597 | _build_note({"title": "x"}, "## Foo\n\nfirst\n\n## Foo\n\nsecond\n"), |
| 598 | _build_note({"title": "x"}, "## Foo\n\nfirst-modified\n\n## Foo\n\nsecond\n"), |
| 599 | )) |
| 600 | |
| 601 | assert len(pairs) == 20, "_e2e_pairs must produce exactly 20 pairs" |
| 602 | return pairs |
| 603 | |
| 604 | |
| 605 | @pytest.mark.parametrize("label,a,b", _e2e_pairs(), ids=lambda x: x if isinstance(x, str) else "") |
| 606 | def test_round_trip_hand_crafted(label: str, a: bytes, b: bytes) -> None: |
| 607 | """End-to-end: round-trip every hand-crafted pair.""" |
| 608 | _round_trip(a, b) |
| 609 | |
| 610 | |
| 611 | # ============================================================================= |
| 612 | # Tier 3b — Regression tests for Phase 2.1.1 duplicate-section MoveOp bug |
| 613 | # ============================================================================= |
| 614 | |
| 615 | |
| 616 | class TestDuplicateSectionMoveOpRegression: |
| 617 | """Regression suite for the detect_moves duplicate-content-id bug (Phase 2.1.1). |
| 618 | |
| 619 | Root cause: ``detect_moves`` in ``muse.core.diff_algorithms.lcs`` tracked |
| 620 | consumed content IDs rather than consumed *objects*. When two sections |
| 621 | shared identical text (same ``content_id``), the second delete was wrongly |
| 622 | removed from ``remaining_deletes``, causing the section to survive the |
| 623 | ``apply()`` call and breaking the round-trip invariant. |
| 624 | |
| 625 | Fix: ``paired_delete_ids`` now uses ``id()`` of specific ``DeleteOp`` |
| 626 | objects so only the exact object that became a ``MoveOp`` is excluded from |
| 627 | ``remaining_deletes``. |
| 628 | |
| 629 | Every test here follows the ``apply(diff_notes(A, B), A) == B`` invariant |
| 630 | after canonicalising both sides. |
| 631 | """ |
| 632 | |
| 633 | def test_hypothesis_failing_seed_exact(self) -> None: |
| 634 | """Exact Hypothesis counter-example: H2 + two identical H1 → H1 + H2.""" |
| 635 | a = b"---\ntitle: A\n---\n## A\n\n\n# A\n\n\n# A\n\n\n" |
| 636 | b = b"---\ntitle: A\n---\n# A\n\n\n## A\n\n\n" |
| 637 | _round_trip(canonicalize(a), canonicalize(b)) |
| 638 | |
| 639 | def test_three_identical_sections_reduce_to_two(self) -> None: |
| 640 | """Three consecutive identical sections reduced to two.""" |
| 641 | a = _build_note({"title": "T"}, "# X\n\nline\n\n# X\n\nline\n\n# X\n\nline\n\n") |
| 642 | b = _build_note({"title": "T"}, "# X\n\nline\n\n# X\n\nline\n\n") |
| 643 | _round_trip(a, b) |
| 644 | |
| 645 | def test_three_identical_sections_reduce_to_one(self) -> None: |
| 646 | """Three consecutive identical sections reduced to one.""" |
| 647 | a = _build_note({"title": "T"}, "# X\n\nline\n\n# X\n\nline\n\n# X\n\nline\n\n") |
| 648 | b = _build_note({"title": "T"}, "# X\n\nline\n\n") |
| 649 | _round_trip(a, b) |
| 650 | |
| 651 | def test_duplicate_sections_reordered(self) -> None: |
| 652 | """Two identical H1 sections swapped around a different H2 section.""" |
| 653 | a = _build_note({"title": "T"}, "# Same\n\nbody\n\n## Diff\n\ndiff\n\n# Same\n\nbody\n\n") |
| 654 | b = _build_note({"title": "T"}, "# Same\n\nbody\n\n# Same\n\nbody\n\n## Diff\n\ndiff\n\n") |
| 655 | _round_trip(a, b) |
| 656 | |
| 657 | def test_two_distinct_sections_swapped(self) -> None: |
| 658 | """Two sections with different content (no duplicate) still round-trip.""" |
| 659 | a = _build_note({"title": "T"}, "# A\n\nalpha\n\n# B\n\nbeta\n\n") |
| 660 | b = _build_note({"title": "T"}, "# B\n\nbeta\n\n# A\n\nalpha\n\n") |
| 661 | _round_trip(a, b) |
| 662 | |
| 663 | def test_expand_one_duplicate_to_three(self) -> None: |
| 664 | """Going from one section to three identical copies (inverse direction).""" |
| 665 | a = _build_note({"title": "T"}, "# X\n\ntext\n\n") |
| 666 | b = _build_note({"title": "T"}, "# X\n\ntext\n\n# X\n\ntext\n\n# X\n\ntext\n\n") |
| 667 | _round_trip(a, b) |
| 668 | |
| 669 | def test_all_sections_deleted_duplicate_content(self) -> None: |
| 670 | """All sections deleted when source has duplicates and target is empty body.""" |
| 671 | a = _build_note({"title": "T"}, "# X\n\nfoo\n\n# X\n\nfoo\n\n") |
| 672 | b = _build_note({"title": "T"}, "") |
| 673 | _round_trip(a, b) |
| 674 | |
| 675 | def test_detect_moves_does_not_consume_sibling_deletes(self) -> None: |
| 676 | """Directly verify detect_moves leaves sibling deletes intact. |
| 677 | |
| 678 | When two DeleteOps share a content_id and one InsertOp with the same |
| 679 | content_id exists, detect_moves must produce exactly one MoveOp and |
| 680 | leave the second delete in remaining_deletes. |
| 681 | """ |
| 682 | from muse.core.diff_algorithms.lcs import detect_moves |
| 683 | from muse.domain import DeleteOp, InsertOp |
| 684 | |
| 685 | cid = "aaaa" * 16 # 64-char fake content_id |
| 686 | |
| 687 | d1 = DeleteOp(op="delete", address="section:1:X#0", position=1, content_id=cid, content_summary="# X\n\n") |
| 688 | d2 = DeleteOp(op="delete", address="section:1:X#1", position=2, content_id=cid, content_summary="# X\n\n") |
| 689 | i1 = InsertOp(op="insert", address="section:1:X#0", position=0, content_id=cid, content_summary="# X\n\n") |
| 690 | |
| 691 | moves, rem_inserts, rem_deletes = detect_moves([i1], [d1, d2]) |
| 692 | |
| 693 | assert len(moves) == 1, f"Expected 1 MoveOp, got {len(moves)}" |
| 694 | assert moves[0]["from_position"] == 1 |
| 695 | assert moves[0]["to_position"] == 0 |
| 696 | |
| 697 | assert rem_inserts == [], f"No inserts should remain, got {rem_inserts}" |
| 698 | assert len(rem_deletes) == 1, f"Expected 1 remaining delete, got {rem_deletes}" |
| 699 | assert rem_deletes[0]["address"] == "section:1:X#1" |
| 700 | assert rem_deletes[0]["position"] == 2 |
| 701 | |
| 702 | def test_detect_moves_two_pairs_same_content(self) -> None: |
| 703 | """Two inserts and two deletes with identical content: first insert gets MoveOp, |
| 704 | second insert and second delete remain unpaired. |
| 705 | """ |
| 706 | from muse.core.diff_algorithms.lcs import detect_moves |
| 707 | from muse.domain import DeleteOp, InsertOp |
| 708 | |
| 709 | cid = "bbbb" * 16 |
| 710 | |
| 711 | d1 = DeleteOp(op="delete", address="section:1:Y#0", position=0, content_id=cid, content_summary="# Y\n\n") |
| 712 | d2 = DeleteOp(op="delete", address="section:1:Y#1", position=3, content_id=cid, content_summary="# Y\n\n") |
| 713 | i1 = InsertOp(op="insert", address="section:1:Y#0", position=2, content_id=cid, content_summary="# Y\n\n") |
| 714 | i2 = InsertOp(op="insert", address="section:1:Y#1", position=4, content_id=cid, content_summary="# Y\n\n") |
| 715 | |
| 716 | moves, rem_inserts, rem_deletes = detect_moves([i1, i2], [d1, d2]) |
| 717 | |
| 718 | # Only the first insert pairs with the first delete (first-come first-served). |
| 719 | assert len(moves) == 1 |
| 720 | assert moves[0]["from_position"] == 0 |
| 721 | assert moves[0]["to_position"] == 2 |
| 722 | |
| 723 | # Second insert and second delete remain unpaired. |
| 724 | assert len(rem_inserts) == 1 |
| 725 | assert rem_inserts[0]["position"] == 4 |
| 726 | assert len(rem_deletes) == 1 |
| 727 | assert rem_deletes[0]["position"] == 3 |
| 728 | |
| 729 | |
| 730 | # ============================================================================= |
| 731 | # Tier 4 — Data-integrity fuzz with hypothesis |
| 732 | # ============================================================================= |
| 733 | |
| 734 | |
| 735 | _PRINTABLE = string.ascii_letters + string.digits + " " |
| 736 | |
| 737 | _slug_st = st.text( |
| 738 | alphabet=string.ascii_lowercase + string.digits, min_size=1, max_size=12 |
| 739 | ) |
| 740 | _word_st = st.text(alphabet=_PRINTABLE, min_size=0, max_size=40) |
| 741 | |
| 742 | |
| 743 | def _line_st() -> st.SearchStrategy[str]: |
| 744 | """Strategy producing a single body line (no embedded newlines).""" |
| 745 | return _word_st |
| 746 | |
| 747 | |
| 748 | def _heading_st() -> st.SearchStrategy[str]: |
| 749 | """Strategy producing a Markdown heading line.""" |
| 750 | return st.tuples( |
| 751 | st.integers(min_value=1, max_value=4), |
| 752 | st.text(alphabet=string.ascii_letters + " ", min_size=1, max_size=12).map( |
| 753 | lambda s: s.strip() or "Heading" |
| 754 | ), |
| 755 | ).map(lambda lt: "#" * lt[0] + " " + lt[1]) |
| 756 | |
| 757 | |
| 758 | def _section_st() -> st.SearchStrategy[str]: |
| 759 | """Strategy producing a complete section (heading + body lines + trailing newline).""" |
| 760 | return st.tuples( |
| 761 | _heading_st(), |
| 762 | st.lists(_line_st(), min_size=0, max_size=4), |
| 763 | ).map(lambda hb: hb[0] + "\n\n" + "\n".join(hb[1]) + "\n") |
| 764 | |
| 765 | |
| 766 | def _body_st() -> st.SearchStrategy[str]: |
| 767 | """Strategy producing a Markdown body of 0–4 sections.""" |
| 768 | return st.lists(_section_st(), min_size=0, max_size=4).map("".join) |
| 769 | |
| 770 | |
| 771 | def _frontmatter_st() -> st.SearchStrategy[dict[str, Any]]: |
| 772 | """Strategy producing a small canonical frontmatter mapping.""" |
| 773 | return st.fixed_dictionaries( |
| 774 | { |
| 775 | "title": st.text( |
| 776 | alphabet=string.ascii_letters + " ", min_size=1, max_size=12 |
| 777 | ).map(lambda s: s.strip() or "Untitled"), |
| 778 | }, |
| 779 | optional={ |
| 780 | "project": _slug_st, |
| 781 | "tags": st.lists(_slug_st, min_size=0, max_size=4, unique=True), |
| 782 | "entity": st.lists(_slug_st, min_size=0, max_size=4, unique=True), |
| 783 | }, |
| 784 | ) |
| 785 | |
| 786 | |
| 787 | def _note_st() -> st.SearchStrategy[bytes]: |
| 788 | """Strategy producing canonical-form note bytes.""" |
| 789 | return st.tuples(_frontmatter_st(), _body_st()).map( |
| 790 | lambda fb: _build_note(fb[0], fb[1]) |
| 791 | ) |
| 792 | |
| 793 | |
| 794 | @settings( |
| 795 | max_examples=200, |
| 796 | deadline=None, |
| 797 | suppress_health_check=[HealthCheck.too_slow, HealthCheck.filter_too_much], |
| 798 | ) |
| 799 | @given(a=_note_st(), b=_note_st()) |
| 800 | def test_fuzz_round_trip_invariant(a: bytes, b: bytes) -> None: |
| 801 | """Hypothesis fuzz: ``apply(diff_notes(A, B), A) == B`` for random pairs.""" |
| 802 | _round_trip(a, b) |
| 803 | |
| 804 | |
| 805 | # ============================================================================= |
| 806 | # Tier 5 — Performance |
| 807 | # ============================================================================= |
| 808 | |
| 809 | |
| 810 | def _build_50_section_note(seed: int) -> bytes: |
| 811 | """Build a deterministic 50-section note (sized realistically). |
| 812 | |
| 813 | Each section has ~10 body lines, yielding a ~3 KB total note. *seed* |
| 814 | perturbs section bodies so two builds with different seeds produce |
| 815 | different but structurally-similar notes. |
| 816 | |
| 817 | Args: |
| 818 | seed: Integer that perturbs the section bodies. |
| 819 | |
| 820 | Returns: |
| 821 | Canonical-form note bytes. |
| 822 | """ |
| 823 | parts: list[str] = [] |
| 824 | for i in range(50): |
| 825 | parts.append(f"## Section {i}\n\n") |
| 826 | for j in range(10): |
| 827 | parts.append(f"line {i}-{j}-{seed % 7}\n") |
| 828 | parts.append("\n") |
| 829 | body = "".join(parts) |
| 830 | return _build_note({"title": f"Note {seed}", "tags": ["perf"]}, body) |
| 831 | |
| 832 | |
| 833 | class TestPerformance: |
| 834 | """Tier 5 — diff of a realistic 50-section note must finish in < 100 ms.""" |
| 835 | |
| 836 | def test_50_section_note_under_100ms(self) -> None: |
| 837 | a = _build_50_section_note(seed=1) |
| 838 | b = _build_50_section_note(seed=2) |
| 839 | start = time.perf_counter() |
| 840 | delta = diff_notes(a, b) |
| 841 | elapsed = time.perf_counter() - start |
| 842 | assert delta["ops"] |
| 843 | assert elapsed < 0.5, ( |
| 844 | f"diff_notes(50-section) took {elapsed * 1000:.1f} ms " |
| 845 | f"(soft target < 100 ms, hard fail > 500 ms)" |
| 846 | ) |
| 847 | |
| 848 | |
| 849 | # ============================================================================= |
| 850 | # Tier 6 — Stress |
| 851 | # ============================================================================= |
| 852 | |
| 853 | |
| 854 | class TestStress: |
| 855 | """Tier 6 — 200 sequential diff+apply cycles complete in under 5 s.""" |
| 856 | |
| 857 | def test_200_note_pairs_under_5s(self) -> None: |
| 858 | pairs = [] |
| 859 | for i in range(200): |
| 860 | a = _build_note( |
| 861 | {"title": f"N{i}", "tags": [f"t{i % 5}"]}, |
| 862 | f"# H{i}\n\nline a {i}\nline b\n", |
| 863 | ) |
| 864 | b = _build_note( |
| 865 | {"title": f"N{i}", "tags": [f"t{(i + 1) % 5}"]}, |
| 866 | f"# H{i}\n\nline a {i}\nline b modified\n", |
| 867 | ) |
| 868 | pairs.append((a, b)) |
| 869 | |
| 870 | start = time.perf_counter() |
| 871 | for a, b in pairs: |
| 872 | delta = diff_notes(a, b) |
| 873 | out = apply(delta, a) |
| 874 | assert out == b |
| 875 | elapsed = time.perf_counter() - start |
| 876 | assert elapsed < 5.0, ( |
| 877 | f"200 diff+apply cycles took {elapsed:.2f} s (limit 5 s)" |
| 878 | ) |
| 879 | |
| 880 | |
| 881 | # ============================================================================= |
| 882 | # Tier 7 — Security |
| 883 | # ============================================================================= |
| 884 | |
| 885 | |
| 886 | class TestSecurity: |
| 887 | """Tier 7 — adversarial inputs must not crash, leak, or hang.""" |
| 888 | |
| 889 | def test_binary_bytes_do_not_crash(self) -> None: |
| 890 | a = bytes(range(256)) |
| 891 | b = bytes(reversed(range(256))) |
| 892 | delta = diff_notes(a, b) |
| 893 | assert isinstance(delta["ops"], list) |
| 894 | out = apply(delta, a) |
| 895 | assert isinstance(out, bytes) |
| 896 | |
| 897 | def test_nul_bytes_in_body_safe(self) -> None: |
| 898 | a = b"---\ntitle: X\n---\nhello\x00world\n" |
| 899 | b = b"---\ntitle: Y\n---\nhello\x00world\n" |
| 900 | # Should not raise; apply may produce a normalised re-serialisation |
| 901 | # (NUL bytes survive the YAML / body path because we never decode |
| 902 | # strictly). |
| 903 | delta = diff_notes(a, b) |
| 904 | assert any(op["address"] == _TITLE_ADDR for op in delta["ops"]) |
| 905 | out = apply(delta, a) |
| 906 | assert isinstance(out, bytes) |
| 907 | |
| 908 | def test_very_long_line_safe(self) -> None: |
| 909 | long_line = "x" * 200_000 |
| 910 | a = _build_note({"title": "L"}, f"# H\n\n{long_line}\n") |
| 911 | b = _build_note({"title": "L"}, f"# H\n\n{long_line}y\n") |
| 912 | _round_trip(a, b) |
| 913 | |
| 914 | def test_deeply_nested_yaml_safe(self) -> None: |
| 915 | # PyYAML's safe_load accepts deep mappings; we should pass them |
| 916 | # through without recursing into arbitrary Python objects. |
| 917 | nested: Any = {"deep": 1} |
| 918 | for _ in range(50): |
| 919 | nested = {"k": nested} |
| 920 | a = _build_note({"title": "X", "nested": nested}, "body\n") |
| 921 | b = _build_note({"title": "Y", "nested": nested}, "body\n") |
| 922 | delta = diff_notes(a, b) |
| 923 | assert any(op["address"] == _TITLE_ADDR for op in delta["ops"]) |
| 924 | out = apply(delta, a) |
| 925 | # The nested structure round-trips because canonicalize stabilises it. |
| 926 | assert out == b |
| 927 | |
| 928 | def test_oversize_input_raises_value_error(self) -> None: |
| 929 | too_big = b"x" * (_MAX_NOTE_BYTES + 1) |
| 930 | with pytest.raises(ValueError): |
| 931 | diff_notes(too_big, b"") |
| 932 | with pytest.raises(ValueError): |
| 933 | apply({"domain": "knowtation", "ops": []}, too_big) # type: ignore[arg-type] |
| 934 | |
| 935 | def test_yaml_safe_load_only(self) -> None: |
| 936 | # !!python/object exploit attempts must not instantiate arbitrary |
| 937 | # Python objects. yaml.safe_load raises a YAMLError, which our |
| 938 | # _parse_note catches and downgrades to "no frontmatter". The body |
| 939 | # text falls through unchanged. |
| 940 | evil = ( |
| 941 | b"---\n" |
| 942 | b"!!python/object/apply:os.system ['echo pwned']\n" |
| 943 | b"---\n" |
| 944 | b"body\n" |
| 945 | ) |
| 946 | parsed = _parse_note(evil) |
| 947 | # Either the YAML parse failed entirely (frontmatter empty) or the |
| 948 | # crafted node was rejected — in neither case is a Python object |
| 949 | # instantiated. The important assertion is: no os.system call. |
| 950 | assert isinstance(parsed.frontmatter, dict) |
| 951 | # Round-trip with self must always succeed (idempotency). |
| 952 | delta = diff_notes(evil, evil) |
| 953 | assert delta["ops"] == [] |
| 954 | |
| 955 | def test_malformed_unclosed_frontmatter_safe(self) -> None: |
| 956 | a = b"---\ntitle: open\n" # never closes |
| 957 | b = b"---\ntitle: open\nthen more\n" |
| 958 | delta = diff_notes(a, b) |
| 959 | out = apply(delta, a) |
| 960 | assert isinstance(out, bytes) |