diff.py 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166
  1. """Remote write computation (contract.md §6.4, §15.2).
  2. Pure functions over JSON-shaped documents; no I/O. The plane runs the authoritative write check;
  3. the agent runs the same check before sending so a locked write fails with a clear message and
  4. nothing goes on the wire.
  5. """
  6. from __future__ import annotations
  7. import copy
  8. from typing import Any, Dict, Iterator, List, Optional, Sequence, Tuple
  9. from .paths import Path, covers, encode
  10. Locks = Sequence[tuple[Path, str]]
  11. def json_equal(a: Any, b: Any) -> bool:
  12. """Structural JSON equality: numbers by value, but ``True`` is not ``1``."""
  13. if isinstance(a, bool) or isinstance(b, bool):
  14. return type(a) is type(b) and a == b
  15. if isinstance(a, int | float) and isinstance(b, int | float):
  16. return a == b
  17. if isinstance(a, dict) and isinstance(b, dict):
  18. return a.keys() == b.keys() and all(json_equal(a[k], b[k]) for k in a)
  19. if isinstance(a, list) and isinstance(b, list):
  20. return len(a) == len(b) and all(json_equal(x, y) for x, y in zip(a, b))
  21. return type(a) is type(b) and a == b
  22. def diff(base: dict[str, Any], new: dict[str, Any], prefix: Path = ()) -> tuple[dict[Path, Any], list[Path]]:
  23. """``(set, unset)`` turning ``base`` into ``new`` (§15.2 step 5). A changed list is one
  24. whole-list ``set`` (D8); a key equal to its base value is not sent."""
  25. sets: dict[Path, Any] = {}
  26. unsets: list[Path] = []
  27. for key, value in new.items():
  28. p = prefix + (key,)
  29. if key not in base:
  30. sets[p] = value
  31. elif isinstance(base[key], dict) and isinstance(value, dict):
  32. s, u = diff(base[key], value, p)
  33. sets.update(s)
  34. unsets.extend(u)
  35. elif not json_equal(base[key], value):
  36. sets[p] = value
  37. unsets.extend(prefix + (key,) for key in base if key not in new)
  38. return sets, unsets
  39. def intent_diff(base: dict[str, Any], new: dict[str, Any], prefix: Path = ()) -> tuple[dict[Path, Any], list[Path]]:
  40. """:func:`diff` as a caller's *intent*: the key-level edit a write means, to be re-applied to a
  41. newer document after a CAS conflict (§15.3). A mapping the base did not hold as a mapping
  42. (absent, or a scalar) is expanded to its leaves: writing ``terminal.timeout`` into a profile
  43. with no ``terminal`` section means "set that key", not "replace whatever ``terminal`` holds by
  44. the time the retry runs" — another writer's ``terminal.persistent`` must survive it. Only an
  45. empty mapping stays a whole value (there is no leaf to name); :func:`apply_intent` adds it
  46. without replacing a mapping that appeared meanwhile."""
  47. sets: dict[Path, Any] = {}
  48. unsets: list[Path] = []
  49. for key, value in new.items():
  50. p = prefix + (key,)
  51. old = base.get(key, _ABSENT)
  52. if isinstance(value, dict) and value and not isinstance(old, dict):
  53. s, _ = intent_diff({}, value, p)
  54. sets.update(s)
  55. elif key not in base:
  56. sets[p] = value
  57. elif isinstance(old, dict) and isinstance(value, dict):
  58. s, u = intent_diff(old, value, p)
  59. sets.update(s)
  60. unsets.extend(u)
  61. elif not json_equal(old, value):
  62. sets[p] = value
  63. unsets.extend(prefix + (key,) for key in base if key not in new)
  64. return sets, unsets
  65. _ABSENT = object()
  66. def apply_intent(doc: dict[str, Any], sets: dict[Path, Any], unsets: Sequence[Path]) -> None:
  67. """Apply an :func:`intent_diff` edit to *doc* in place."""
  68. for p, v in sets.items():
  69. if isinstance(v, dict) and not v:
  70. found, cur = _get_path(doc, p)
  71. if found and isinstance(cur, dict):
  72. continue # "make this a mapping": a mapping is already there, with its keys
  73. _set_path(doc, p, copy.deepcopy(v))
  74. for p in unsets:
  75. _pop_path(doc, p)
  76. def _set_path(doc: dict[str, Any], path: Path, value: Any) -> None:
  77. node = doc
  78. for seg in path[:-1]:
  79. if not isinstance(node.get(seg), dict):
  80. node[seg] = {}
  81. node = node[seg]
  82. node[path[-1]] = value
  83. def _pop_path(doc: dict[str, Any], path: Path) -> bool:
  84. node: Any = doc
  85. for seg in path[:-1]:
  86. if not isinstance(node, dict) or not isinstance(node.get(seg), dict):
  87. return False
  88. node = node[seg]
  89. if isinstance(node, dict) and path[-1] in node:
  90. del node[path[-1]]
  91. return True
  92. return False
  93. def _get_path(doc: dict[str, Any], path: Path) -> tuple[bool, Any]:
  94. node: Any = doc
  95. for seg in path:
  96. if not isinstance(node, dict) or seg not in node:
  97. return False, None
  98. node = node[seg]
  99. return True, node
  100. def strip_locked(base: dict[str, Any], new: dict[str, Any], locks: Locks) -> tuple[dict[str, Any], dict[str, Any], list[Path]]:
  101. """Drop every locked path from BOTH documents (§15.2 step 1), so a bulk write neither sets
  102. nor unsets a key it may not touch. Returns the copies and the locked paths whose new value
  103. differed from the effective one (the ones the caller tried to change)."""
  104. base, new = copy.deepcopy(base), copy.deepcopy(new)
  105. changed: list[Path] = []
  106. for lock, _level in locks:
  107. in_base, base_val = _get_path(base, lock)
  108. in_new, new_val = _get_path(new, lock)
  109. if in_base != in_new or (in_new and not json_equal(base_val, new_val)):
  110. changed.append(lock)
  111. _pop_path(base, lock)
  112. _pop_path(new, lock)
  113. return base, new, changed
  114. def _touched(path: Path, value: Any) -> Iterator[tuple[Path, Any]]:
  115. """``(touched path, value written there)`` for ``set path = value`` (§6.4 rule 2): the path
  116. itself and every path inside ``value``, descending through objects only."""
  117. yield path, value
  118. if isinstance(value, dict):
  119. for k, v in value.items():
  120. yield from _touched(path + (k,), v)
  121. def write_check(sets: dict[Path, Any], unsets: Sequence[Path], locks: Locks) -> Optional[tuple[Path, str]]:
  122. """The ``(lock path, level)`` that refuses this write (§6.4 rules 1-3), or None."""
  123. for p in unsets:
  124. for lock, level in locks:
  125. if covers(lock, p):
  126. return lock, level
  127. for p, v in sets.items():
  128. for t, tv in _touched(p, v):
  129. for lock, level in locks:
  130. if covers(lock, t):
  131. return lock, level
  132. # R7: a non-object written at a strict ancestor of a lock would replace the
  133. # locked subtree through deep merge.
  134. if len(t) < len(lock) and covers(t, lock) and not isinstance(tv, dict):
  135. return lock, level
  136. return None
  137. def encode_changes(sets: dict[Path, Any], unsets: Sequence[Path]) -> tuple[dict[str, Any], list[str]]:
  138. return {encode(p): v for p, v in sets.items()}, [encode(p) for p in unsets]