gabriel / muse public
test_knowtation_differ.py python
960 lines 35.7 KB
Raw
sha256:660fcac1df3ab28f61862e961890bd2ca8b754fa0242079d93ca1e25037ec8a6 chore(tests): add docstring to tests/__init__.py so rc14 tr… Human 26 days ago
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)
File History 2 commits
sha256:660fcac1df3ab28f61862e961890bd2ca8b754fa0242079d93ca1e25037ec8a6 chore(tests): add docstring to tests/__init__.py so rc14 tr… Human 26 days ago
sha256:d8316ffae901be06347e16ab55be11868eb519dd16ade3e8aa16a99e662f7e62 baseline: rc14 re-baseline after rc3 store corruption recovery Human patch 26 days ago