fuzzy_match.py 39 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820
  1. #!/usr/bin/env python3
  2. """Fuzzy find-and-replace for LLM-generated edits.
  3. An ordered chain of increasingly permissive strategies (``STRATEGIES``) lets
  4. whitespace, indentation, escaping and Unicode drift in tool-call arguments
  5. still land on the intended region::
  6. new_content, match_count, strategy, error = fuzzy_find_and_replace(
  7. content, old_string, new_string, replace_all=False)
  8. """
  9. import bisect
  10. import re
  11. from difflib import SequenceMatcher
  12. from typing import Callable, Iterable, Optional
  13. Span = tuple[int, int]
  14. IDENTICAL_STRINGS_ERROR = (
  15. "No edit was applied because old_string and new_string are identical. "
  16. "Provide the existing text to replace in old_string and the changed "
  17. "replacement text in new_string.")
  18. UNICODE_MAP = {
  19. "\u201c": '"', "\u201d": '"', # smart double quotes
  20. "\u2018": "'", "\u2019": "'", # smart single quotes
  21. "\u2014": "--", "\u2013": "-", # em/en dashes
  22. "\u2026": "...", "\u00a0": " ", # ellipsis and non-breaking space
  23. "\u2212": "-", # typographic minus (math/scientific docs)
  24. # Space-separator family (Zs): otherwise such files fall to the similarity fallback.
  25. "\u2000": " ", "\u2001": " ", "\u2002": " ", "\u2003": " ",
  26. "\u2004": " ", "\u2005": " ", "\u2006": " ", "\u2007": " ",
  27. "\u2008": " ", "\u2009": " ", "\u200a": " ", "\u202f": " ",
  28. "\u205f": " ", "\u3000": " "}
  29. def _unicode_normalize(text: str) -> str:
  30. """Map typographic Unicode variants to ASCII equivalents."""
  31. for char, repl in UNICODE_MAP.items():
  32. text = text.replace(char, repl)
  33. return text
  34. # ── Position helpers ─────────────────────────────────────────────────────
  35. def _calculate_line_positions(content_lines: list[str], start_line: int,
  36. end_line: int, content_length: int) -> Span:
  37. """Character span covering ``content_lines[start_line:end_line]`` (end exclusive)."""
  38. start_pos = sum(len(line) + 1 for line in content_lines[:start_line])
  39. end_pos = sum(len(line) + 1 for line in content_lines[:end_line]) - 1
  40. return start_pos, min(content_length, end_pos)
  41. def _window_spans(content: str, content_lines: list[str], n: int,
  42. accept: Callable[[int], bool]) -> list[Span]:
  43. """Spans of every ``n``-line window starting at ``i`` for which ``accept(i)``."""
  44. return [
  45. _calculate_line_positions(content_lines, i, i + n, len(content))
  46. for i in range(len(content_lines) - n + 1) if accept(i)]
  47. def _match_transformed_lines(content: str, pattern: str,
  48. transform: Callable[[list[str]], list[str]]) -> list[Span]:
  49. """Match ``pattern`` against ``content`` after applying ``transform`` to each line block."""
  50. content_lines = content.split('\n')
  51. pattern_norm = transform(pattern.split('\n'))
  52. n = len(pattern_norm)
  53. return _window_spans(content, content_lines, n,
  54. lambda i: transform(content_lines[i:i + n]) == pattern_norm)
  55. def _strip_boundary(lines: list[str]) -> list[str]:
  56. """Strip whitespace on the first and last lines only."""
  57. lines = list(lines)
  58. lines[0] = lines[0].strip()
  59. if len(lines) > 1:
  60. lines[-1] = lines[-1].strip()
  61. return lines
  62. def _build_orig_to_norm_map(original: str) -> list[int]:
  63. """Map each original index to its index in ``_unicode_normalize(original)``
  64. (replacements can expand one char into several). Length ``len(original)+1``;
  65. the last entry is a sentinel one past the final character."""
  66. result: list[int] = []
  67. norm_pos = 0
  68. for char in original:
  69. result.append(norm_pos)
  70. repl = UNICODE_MAP.get(char)
  71. norm_pos += len(repl) if repl is not None else 1
  72. result.append(norm_pos)
  73. return result
  74. def _invert_norm_map(orig_to_norm: list[int]) -> dict[int, int]:
  75. """norm_pos -> first original position mapping to it."""
  76. inverted: dict[int, int] = {}
  77. for orig_pos, norm_pos in enumerate(orig_to_norm[:-1]):
  78. inverted.setdefault(norm_pos, orig_pos)
  79. return inverted
  80. def _norm_end_to_orig(orig_to_norm: list[int], orig_start: int, norm_end: int) -> int:
  81. """Walk from ``orig_start`` until the mapped position reaches ``norm_end``."""
  82. orig_len = len(orig_to_norm) - 1
  83. orig_end = orig_start
  84. while orig_end < orig_len and orig_to_norm[orig_end] < norm_end:
  85. orig_end += 1
  86. return orig_end
  87. def _map_positions_norm_to_orig(orig_to_norm: list[int], norm_matches: list[Span]) -> list[Span]:
  88. """Convert spans in the normalised string to original-string spans."""
  89. norm_to_orig_start = _invert_norm_map(orig_to_norm)
  90. results: list[Span] = []
  91. for norm_start, norm_end in norm_matches:
  92. if norm_start in norm_to_orig_start:
  93. orig_start = norm_to_orig_start[norm_start]
  94. results.append((orig_start, _norm_end_to_orig(orig_to_norm, orig_start, norm_end)))
  95. return results
  96. def _map_normalized_positions(original: str, normalized: str,
  97. normalized_matches: list[Span]) -> list[Span]:
  98. """Best-effort span mapping for ``[ \\t]+`` -> ``' '`` whitespace collapsing."""
  99. orig_to_norm = [] # orig_to_norm[i] = position in normalized
  100. orig_idx = norm_idx = 0
  101. while orig_idx < len(original) and norm_idx < len(normalized):
  102. if original[orig_idx] == normalized[norm_idx]:
  103. orig_to_norm.append(norm_idx)
  104. orig_idx += 1
  105. norm_idx += 1
  106. elif original[orig_idx] in ' \t' and normalized[norm_idx] == ' ':
  107. # Collapsed run: advance norm_idx only once the run is consumed.
  108. orig_to_norm.append(norm_idx)
  109. orig_idx += 1
  110. if orig_idx < len(original) and original[orig_idx] not in ' \t':
  111. norm_idx += 1
  112. else:
  113. # Extra whitespace in original, or a mismatch normalization should
  114. # never produce — either way, pin to the current norm_idx.
  115. orig_to_norm.append(norm_idx)
  116. orig_idx += 1
  117. orig_to_norm.extend([len(normalized)] * (len(original) - orig_idx))
  118. norm_to_orig_start = {}
  119. norm_to_orig_end = {}
  120. for orig_pos, norm_pos in enumerate(orig_to_norm):
  121. norm_to_orig_start.setdefault(norm_pos, orig_pos)
  122. norm_to_orig_end[norm_pos] = orig_pos
  123. original_matches = []
  124. for norm_start, norm_end in normalized_matches:
  125. if norm_start in norm_to_orig_start:
  126. orig_start = norm_to_orig_start[norm_start]
  127. else:
  128. orig_start = min(i for i, n in enumerate(orig_to_norm) if n >= norm_start)
  129. if norm_end - 1 in norm_to_orig_end:
  130. orig_end = norm_to_orig_end[norm_end - 1] + 1
  131. else:
  132. orig_end = orig_start + (norm_end - norm_start)
  133. # Absorb trailing collapsed whitespace only when the normalized match
  134. # itself ended in a space; otherwise the first whitespace after the
  135. # match is a word boundary that must survive.
  136. if norm_end < len(normalized) and normalized[norm_end - 1] == ' ':
  137. while orig_end < len(original) and original[orig_end] in ' \t':
  138. orig_end += 1
  139. original_matches.append((orig_start, min(orig_end, len(original))))
  140. return original_matches
  141. # ── Strategies ───────────────────────────────────────────────────────────
  142. # Each takes ``(content, pattern)`` and returns ``(start, end)`` spans in the
  143. # ORIGINAL content.
  144. def _strategy_exact(content: str, pattern: str) -> list[Span]:
  145. """Strategy 1: exact, non-overlapping occurrences (str.replace semantics —
  146. overlapping spans would corrupt the file under replace_all)."""
  147. return [m.span() for m in re.finditer(re.escape(pattern), content)]
  148. def _strategy_line_trimmed(content: str, pattern: str) -> list[Span]:
  149. """Strategy 2: strip each line before comparing."""
  150. return _match_transformed_lines(content, pattern, lambda ls: [l.strip() for l in ls])
  151. def _strategy_whitespace_normalized(content: str, pattern: str) -> list[Span]:
  152. """Strategy 3: collapse runs of spaces/tabs to a single space."""
  153. def normalize(s):
  154. return re.sub(r'[ \t]+', ' ', s)
  155. content_normalized = normalize(content)
  156. matches_in_normalized = _strategy_exact(content_normalized, normalize(pattern))
  157. if not matches_in_normalized:
  158. return []
  159. return _map_normalized_positions(content, content_normalized, matches_in_normalized)
  160. def _strategy_indentation_flexible(content: str, pattern: str) -> list[Span]:
  161. """Strategy 4: ignore leading indentation entirely."""
  162. return _match_transformed_lines(content, pattern, lambda ls: [l.lstrip() for l in ls])
  163. def _strategy_escape_normalized(content: str, pattern: str) -> list[Span]:
  164. """Strategy 5: treat literal ``\\n``/``\\t``/``\\r`` in the pattern as control chars."""
  165. pattern_unescaped = pattern.replace('\\n', '\n').replace('\\t', '\t').replace('\\r', '\r')
  166. if pattern_unescaped == pattern:
  167. return []
  168. return _strategy_exact(content, pattern_unescaped)
  169. def _strategy_trimmed_boundary(content: str, pattern: str) -> list[Span]:
  170. """Strategy 6: strip whitespace on the first and last lines only."""
  171. return _match_transformed_lines(content, pattern, _strip_boundary)
  172. def _strategy_unicode_normalized(content: str, pattern: str) -> list[Span]:
  173. """Strategy 7: exact/line-trimmed match after Unicode->ASCII normalisation of both sides."""
  174. norm_pattern = _unicode_normalize(pattern)
  175. norm_content = _unicode_normalize(content)
  176. if norm_content == content and norm_pattern == pattern:
  177. return []
  178. norm_matches = (_strategy_exact(norm_content, norm_pattern)
  179. or _strategy_line_trimmed(norm_content, norm_pattern))
  180. if not norm_matches:
  181. return []
  182. return _map_positions_norm_to_orig(_build_orig_to_norm_map(content), norm_matches)
  183. def _strategy_block_anchor(content: str, pattern: str) -> list[Span]:
  184. """Strategy 8: anchor on first+last lines, similarity-score the middle."""
  185. pattern_lines = _unicode_normalize(pattern).split('\n')
  186. if len(pattern_lines) < 2:
  187. return []
  188. first_line = pattern_lines[0].strip()
  189. last_line = pattern_lines[-1].strip()
  190. n = len(pattern_lines)
  191. # Match on normalized lines; compute offsets from the ORIGINAL lines so
  192. # multi-char expansions (em-dash -> '--') don't shift positions.
  193. norm_content_lines = _unicode_normalize(content).split('\n')
  194. potential_matches = {
  195. i for i in range(len(norm_content_lines) - n + 1)
  196. if norm_content_lines[i].strip() == first_line
  197. and norm_content_lines[i + n - 1].strip() == last_line}
  198. # Looser thresholds (0.10/0.30) matched unrelated blocks; these are the safe floor.
  199. threshold = 0.50 if len(potential_matches) == 1 else 0.70
  200. pattern_middle = '\n'.join(pattern_lines[1:-1])
  201. def similar(i: int) -> bool:
  202. if i not in potential_matches:
  203. return False
  204. if n <= 2:
  205. return True
  206. content_middle = '\n'.join(norm_content_lines[i + 1:i + n - 1])
  207. return SequenceMatcher(None, content_middle, pattern_middle).ratio() >= threshold
  208. return _window_spans(content, content.split('\n'), n, similar)
  209. def _strategy_context_aware(content: str, pattern: str) -> list[Span]:
  210. """Strategy 9 (last resort): anchored per-line similarity, every non-blank line >= 0.80.
  211. The anchor pre-filter bounds the scan; the all-lines rule stops coincidental matches."""
  212. pattern_lines = pattern.split('\n')
  213. content_lines = content.split('\n')
  214. n = len(pattern_lines)
  215. if n > len(content_lines):
  216. return []
  217. first_pat = pattern_lines[0].strip()
  218. last_pat = pattern_lines[-1].strip()
  219. def _sim(a: str, b: str) -> float:
  220. return 1.0 if a == b else SequenceMatcher(None, a, b).ratio()
  221. def accept(i: int) -> bool:
  222. block_lines = content_lines[i:i + n]
  223. if _sim(first_pat, block_lines[0].strip()) < 0.80:
  224. return False
  225. if _sim(last_pat, block_lines[-1].strip()) < 0.80:
  226. return False
  227. return all(
  228. not p_line.strip() or _sim(p_line.strip(), c_line.strip()) >= 0.80
  229. for p_line, c_line in zip(pattern_lines, block_lines))
  230. return _window_spans(content, content_lines, n, accept)
  231. # Ordered chain: precise strategies first, similarity-based last.
  232. STRATEGIES: list[tuple[str, Callable[[str, str], list[Span]]]] = [
  233. ("exact", _strategy_exact),
  234. ("line_trimmed", _strategy_line_trimmed),
  235. ("whitespace_normalized", _strategy_whitespace_normalized),
  236. ("indentation_flexible", _strategy_indentation_flexible),
  237. ("escape_normalized", _strategy_escape_normalized),
  238. ("trimmed_boundary", _strategy_trimmed_boundary),
  239. ("unicode_normalized", _strategy_unicode_normalized),
  240. ("block_anchor", _strategy_block_anchor),
  241. ("context_aware", _strategy_context_aware)]
  242. # Matches from these only *approximately* resemble old_string — fine for one
  243. # unique replacement, never safe under replace_all.
  244. SIMILARITY_STRATEGIES = frozenset({"block_anchor", "context_aware"})
  245. _PRECISE_STRATEGIES = [entry for entry in STRATEGIES if entry[0] not in SIMILARITY_STRATEGIES]
  246. _SIMILARITY_TIER = [entry for entry in STRATEGIES if entry[0] in SIMILARITY_STRATEGIES]
  247. _WHOLE_LINE_STRATEGIES = [entry for entry in STRATEGIES if entry[0] == "line_trimmed"]
  248. def boundary_note(strategies: Iterable[Optional[str]], target: str = "old_string's",
  249. where: str = "") -> Optional[str]:
  250. """The note for an edit whose span was found by a similarity strategy, else None.
  251. Those strategies accept a window whose lines only resemble the search text, so the spliced span
  252. can land a line off (observed: a duplicated closing delimiter just outside the intended region).
  253. The normalizing strategies still match every line, so their boundaries are exact; they fire on
  254. routine edits (e.g. missing base indentation), where a note would teach the model to ignore it.
  255. Post-write verification cannot catch a shifted span: it only confirms the new content landed.
  256. """
  257. used = list(dict.fromkeys(s for s in strategies if s in SIMILARITY_STRATEGIES))
  258. if not used:
  259. return None
  260. return (
  261. f"Non-exact match (strategy: {', '.join(used)}){where}. The edit span was located "
  262. f"approximately, not matched to {target} literal boundaries — review the diff below to "
  263. "confirm the change landed exactly where intended (a shifted boundary can duplicate or "
  264. "drop a line just outside the edited region)."
  265. )
  266. # ── Orchestrator ─────────────────────────────────────────────────────────
  267. def is_already_applied(content: str, old_string: str, new_string: str) -> bool:
  268. """True when the edit is already present (re-sent edit -> success-shaped no-op).
  269. Conservative: new_string non-trivial (>= 8 chars) and present EXACTLY; old_string gone."""
  270. if not new_string or len(new_string.strip()) < 8 or new_string not in content:
  271. return False
  272. return old_string == new_string or old_string not in content
  273. def _matched_regions(content: str, matches: list[Span]) -> str:
  274. return "".join(content[start:end] for start, end in matches)
  275. def _format_match_locations(content: str, matches: list[Span], cap: int = 5) -> str:
  276. """Render up to ``cap`` match positions as 'L<line>: <snippet>' rows."""
  277. rows = []
  278. for start, _end in matches[:cap]:
  279. line_no = content.count("\n", 0, start) + 1
  280. line_start = content.rfind("\n", 0, start) + 1
  281. line_end = content.find("\n", line_start)
  282. if line_end == -1:
  283. line_end = len(content)
  284. snippet = content[line_start:line_end].strip()
  285. if len(snippet) > 80:
  286. snippet = snippet[:77] + "..."
  287. rows.append(f" L{line_no}: {snippet}")
  288. extra = len(matches) - cap
  289. if extra > 0:
  290. rows.append(f" ... and {extra} more")
  291. return "\n".join(rows)
  292. def fuzzy_find_and_replace(content: str, old_string: str, new_string: str,
  293. replace_all: bool = False, *,
  294. correction_notes: Optional[list[str]] = None) -> tuple[str, int, Optional[str], Optional[str]]:
  295. """Find and replace via the strategy chain.
  296. Returns ``(new_content, match_count, strategy_name, error)``; on failure
  297. ``(content, 0, None, error)``. Successful escape corrections append their
  298. explanation to ``correction_notes`` when supplied by a tool caller.
  299. """
  300. if not old_string:
  301. # Actionable recovery text: a terse "cannot be empty" leaves the model
  302. # re-sending the identical call until the loop detector kills the run
  303. # (upstream report: cline/cline#13970 — Kimi K3 looped on old_text: null).
  304. return content, 0, None, (
  305. "old_string is empty — nothing to match. Set old_string to the exact "
  306. "existing text the replacement should replace (read the file first if "
  307. "unsure). To create a new file or fully rewrite one, use write_file "
  308. "instead. Do not re-send this call unchanged.")
  309. if not old_string.strip():
  310. # Whitespace-only anchors match trivially and mass-replace or
  311. # ambiguity-error; never meaningful.
  312. return content, 0, None, (
  313. "old_string is only whitespace — provide non-blank text to match. Set it "
  314. "to the exact existing text the replacement should replace (read the file "
  315. "first if unsure). Do not re-send this call unchanged.")
  316. # All consumers, including validation and approval previews, must use the
  317. # same correction policy before a fuzzy strategy can match ambiguous text.
  318. from tools.escape_drift_autocorrect import AmbiguousEscapeDriftError, maybe_correct_escape_drift
  319. try:
  320. old_string, new_string, correction_note = maybe_correct_escape_drift(old_string, new_string, content)
  321. except AmbiguousEscapeDriftError as exc:
  322. return content, 0, None, str(exc)
  323. if old_string == new_string:
  324. return content, 0, None, IDENTICAL_STRINGS_ERROR
  325. # A raw precise match wins (the file may really hold `N|` text). Otherwise a read_file
  326. # gutter paste, a single numbered line included, is stripped BEFORE any similarity
  327. # strategy sees it: a `41|` prefix barely moves per-line similarity, so context_aware
  328. # would accept the raw paste and write the prefixes into the file.
  329. result = _run_strategy_chain(content, old_string, new_string, replace_all, _PRECISE_STRATEGIES)
  330. stripped = None if result else _gutter_stripped_old(content, old_string)
  331. if result is None and stripped is not None:
  332. result = _gutter_recovery(content, *stripped, new_string, replace_all, correction_notes)
  333. elif result is None:
  334. result = _run_strategy_chain(content, old_string, new_string, replace_all, _SIMILARITY_TIER)
  335. if result is None:
  336. _note_edit_match(None, "no_match")
  337. return content, 0, None, "Could not find a match for old_string in the file" + (
  338. GUTTER_MISS_SUFFIX if stripped is not None else "")
  339. if result[3] is None and correction_note and correction_notes is not None:
  340. correction_notes.append(correction_note)
  341. return result
  342. def _run_strategy_chain(content: str, old_string: str, new_string: str, replace_all: bool,
  343. strategies: list[tuple[str, Callable[[str, str], list[Span]]]]) -> Optional[tuple]:
  344. """Apply the first strategy in ``strategies`` that matches; None when none does."""
  345. for strategy_name, strategy_fn in strategies:
  346. matches = strategy_fn(content, old_string)
  347. if not matches:
  348. continue
  349. if len(matches) > 1 and not replace_all:
  350. _note_edit_match(None, "ambiguous")
  351. locations = _format_match_locations(content, matches)
  352. return content, 0, None, (
  353. f"Found {len(matches)} matches for old_string. "
  354. f"Provide more context to make it unique, or use replace_all=True. "
  355. f"Matches:\n{locations}")
  356. if replace_all and len(matches) > 1 and strategy_name in SIMILARITY_STRATEGIES:
  357. _note_edit_match(None, "ambiguous")
  358. return content, 0, None, (
  359. f"Found {len(matches)} approximate matches via the "
  360. f"'{strategy_name}' strategy; replace_all only applies to exact "
  361. f"matches. Provide the precise text (whitespace included) so an "
  362. f"exact/line-trimmed match can be made.")
  363. # Non-exact matches came through some normalization, so new_string may
  364. # carry serialization drift the file doesn't have.
  365. if strategy_name != "exact":
  366. drift_err = _detect_escape_drift(content, matches, old_string, new_string)
  367. if drift_err:
  368. return content, 0, None, drift_err
  369. effective_new = _maybe_unescape_new_string(new_string, content, matches)
  370. new_content = _apply_replacements(
  371. content, matches, effective_new,
  372. old_string=old_string if strategy_name != "exact" else None,
  373. unicode_plan=(_unicode_edit_plan(old_string, effective_new)
  374. if strategy_name == "unicode_normalized" else None))
  375. _note_edit_match(strategy_name)
  376. return new_content, len(matches), strategy_name, None
  377. return None
  378. # ── read_file gutter recovery ────────────────────────────────────────────
  379. _GUTTER_LINE = re.compile(r"^(\d+)\|", re.MULTILINE)
  380. GUTTER_STRIPPED_NOTE = (
  381. "old_string carried read_file's line-number prefixes (`N|`); they were stripped "
  382. "before matching. Send file text without the `N|` gutter next time.")
  383. GUTTER_NEW_STRING_ERROR = (
  384. "old_string looks like read_file output with its `N|` line-number prefixes, but "
  385. "new_string's `N|` prefixes are not a clean read_file gutter (missing on some non-blank "
  386. "lines, or not numbered consecutively), so the intended replacement text is ambiguous. "
  387. "Resend both strings without any `N|` prefixes.")
  388. GUTTER_MISS_SUFFIX = (
  389. " (its read_file `N|` line-number prefixes were stripped first; only an exact or "
  390. "whitespace-tolerant match of the remaining text is accepted)")
  391. def _strip_line_number_gutter(text: str, min_numbered: int = 2) -> Optional[str]:
  392. """``text`` minus a read_file ``N|`` gutter, or None when it is not a verbatim paste.
  393. Mirrors the write_file guard's signature but stricter: EVERY non-blank line carries
  394. the gutter, there are at least ``min_numbered``, and the numbers run strictly
  395. consecutively (blank lines may lose their prefix in a re-paste but still consume a number).
  396. """
  397. stripped: list[str] = []
  398. expected: Optional[int] = None
  399. numbered = 0
  400. for line in text.split("\n"):
  401. match = _GUTTER_LINE.match(line)
  402. if match is None and line.strip():
  403. return None
  404. if match is not None:
  405. if expected is not None and int(match.group(1)) != expected:
  406. return None
  407. expected, numbered = int(match.group(1)), numbered + 1
  408. line = line[match.end():]
  409. if expected is not None:
  410. expected += 1
  411. stripped.append(line)
  412. return "\n".join(stripped) if numbered >= min_numbered else None
  413. def _gutter_stripped_old(content: str, old_string: str) -> Optional[tuple[str, list]]:
  414. """``(old_string minus a read_file gutter, strategies allowed to match it)``; None when
  415. it has none, strips to whitespace (an anchor matching every line break), or the file
  416. itself has gutter-shaped lines (the pipes may be real content there).
  417. A single numbered line is only matched as a whole line: a bare `2|4` stripped to `4`
  418. must not land inside `a = 4`.
  419. """
  420. stripped_old = _strip_line_number_gutter(old_string, min_numbered=1)
  421. if stripped_old is None or not stripped_old.strip() or _GUTTER_LINE.search(content):
  422. return None
  423. if _strip_line_number_gutter(old_string) is None:
  424. return stripped_old, _WHOLE_LINE_STRATEGIES
  425. return stripped_old, _PRECISE_STRATEGIES
  426. def _gutter_recovery(content: str, stripped_old: str, strategies: list, new_string: str,
  427. replace_all: bool, correction_notes: Optional[list[str]]) -> Optional[tuple]:
  428. """Match a gutter-stripped old_string; None when no precise strategy matches.
  429. Only the exact/normalizing strategies may match the stripped text: a similarity
  430. match of a guessed anchor is how an edit lands on the wrong region.
  431. """
  432. # old_string already qualified, so one numbered line is enough for new_string
  433. # (deleting all but one line of the pasted block is an ordinary edit).
  434. stripped_new = _strip_line_number_gutter(new_string, min_numbered=1)
  435. if stripped_new is None:
  436. if _GUTTER_LINE.search(new_string):
  437. _note_edit_match(None, "no_match")
  438. return content, 0, None, GUTTER_NEW_STRING_ERROR
  439. stripped_new = new_string
  440. if stripped_old == stripped_new:
  441. return content, 0, None, IDENTICAL_STRINGS_ERROR
  442. result = _run_strategy_chain(content, stripped_old, stripped_new, replace_all, strategies)
  443. if result and result[3] is None and correction_notes is not None:
  444. correction_notes.append(GUTTER_STRIPPED_NOTE)
  445. return result
  446. def _note_edit_match(strategy: Optional[str], miss: Optional[str] = None) -> None:
  447. """Report to shared metrics which strategy landed (or why none did); a no-op unless a
  448. metered patch tool call is in progress."""
  449. try:
  450. from hermes_cli.observability.shared_metrics_harness import note_edit_match
  451. except Exception:
  452. return
  453. note_edit_match(strategy, miss)
  454. # ── Escape-drift guards ──────────────────────────────────────────────────
  455. def _detect_newline_literal_drift(content: str, matches: list[Span],
  456. old_string: str, new_string: str) -> Optional[str]:
  457. """Error string when a literal two-character ``\\n`` in the arguments stands in
  458. for a real line break in the file (arguments JSON-escaped one extra time), else None.
  459. Fires when some matched region contains a real newline and old_string holds MORE
  460. literal ``\\n`` than that region. old_string is copied from the file, so a genuine
  461. edit has equal counts even when the code legitimately contains ``"\\n"``; only the
  462. surplus is drift. Regions are compared one by one because joining them would
  463. multiply the file-side count under replace_all. new_string must carry a literal
  464. ``\\n`` too: that is what gets written in place of a line break, since
  465. _maybe_unescape_new_string deliberately never rewrites ``\\n``. ``\\r`` needs no
  466. guard here -- that helper converts it whenever the region has a real CR. Drift in
  467. new_string alone is indistinguishable from an edit that adds a ``\\n`` literal.
  468. """
  469. if "\\n" not in new_string:
  470. return None
  471. old_literals = old_string.count("\\n")
  472. for start, end in matches:
  473. region = content[start:end]
  474. if "\n" in region and old_literals > region.count("\\n"):
  475. return (
  476. "Escape-drift detected: old_string contains more literal "
  477. "'\\\\n' sequences than the matched region of the file, which "
  478. "has real line breaks there instead. This is almost always a "
  479. "tool-call serialization artifact where a line break got escaped "
  480. "one extra time; new_string would write it as backslash + n. "
  481. "Re-read the file with read_file and pass old_string/new_string "
  482. "with actual line breaks, keeping only the '\\\\n' sequences "
  483. "that appear literally in the file.")
  484. return None
  485. def _detect_escape_drift(content: str, matches: list[Span],
  486. old_string: str, new_string: str) -> Optional[str]:
  487. """Error string when new_string carries tool-call escape artifacts, else None:
  488. ``\\'``/``\\"`` in both strings but not the matched region, doubled backslash
  489. runs, or a literal ``\\n`` standing in for a real line break."""
  490. has_quote_suspects = "\\'" in new_string or '\\"' in new_string
  491. if not has_quote_suspects and "\\" not in old_string:
  492. return None
  493. matched_regions = _matched_regions(content, matches)
  494. if has_quote_suspects:
  495. for suspect in ("\\'", '\\"'):
  496. if suspect in new_string and suspect in old_string and suspect not in matched_regions:
  497. plain = suspect[1]
  498. return (
  499. f"Escape-drift detected: old_string and new_string contain "
  500. f"the literal sequence {suspect!r} but the matched region of "
  501. f"the file does not. This is almost always a tool-call "
  502. f"serialization artifact where an apostrophe or quote got "
  503. f"prefixed with a spurious backslash. Re-read the file with "
  504. f"read_file and pass old_string/new_string without "
  505. f"backslash-escaping {plain!r} characters.")
  506. newline_drift = _detect_newline_literal_drift(content, matches, old_string, new_string)
  507. if newline_drift:
  508. return newline_drift
  509. return _detect_backslash_doubling(matched_regions, old_string, new_string)
  510. def _backslash_runs(s: str) -> list[int]:
  511. """Lengths of maximal backslash runs in ``s``, in order."""
  512. return [len(run) for run in re.findall(r"\\+", s)]
  513. def _detect_backslash_doubling(matched_regions: str, old_string: str,
  514. new_string: str) -> Optional[str]:
  515. """Detect old_string whose every backslash run is exactly 2x the file's (arguments
  516. JSON-escaped one extra time). Requires the same run count, a non-trivial signal
  517. (a run >= 2 or 2+ runs), and new_string not already matching the file's counts."""
  518. old_runs = _backslash_runs(old_string)
  519. file_runs = _backslash_runs(matched_regions)
  520. if (not old_runs or not file_runs or len(old_runs) != len(file_runs)
  521. or old_runs == file_runs
  522. or any(o != f * 2 for o, f in zip(old_runs, file_runs))
  523. or not (any(f >= 2 for f in file_runs) or len(file_runs) >= 2)
  524. or _backslash_runs(new_string) == file_runs):
  525. return None
  526. return (
  527. "Escape-drift detected: every backslash run in old_string is exactly "
  528. "twice as long as in the matched region of the file (e.g. the file "
  529. "has `\\\\` where old_string has `\\\\\\\\`). The tool-call arguments "
  530. "were JSON-escaped one extra time; applying new_string verbatim would "
  531. "double every backslash in the file. Re-read the file with read_file "
  532. "and resend old_string/new_string with the backslash counts exactly "
  533. "as they appear in the file.")
  534. def _maybe_unescape_new_string(new_string: str, content: str, matches: list[Span]) -> str:
  535. """Convert literal ``\\t``/``\\r`` in new_string to control chars, per sequence, only
  536. when the matched region already contains the real control char (so ``sep = "\\t"`` files
  537. are left alone). ``\\n`` is excluded: rewriting it would mangle source escape literals."""
  538. if "\\t" not in new_string and "\\r" not in new_string:
  539. return new_string
  540. matched_regions = _matched_regions(content, matches)
  541. for literal, control in (("\\t", "\t"), ("\\r", "\r")):
  542. if literal in new_string and control in matched_regions:
  543. new_string = new_string.replace(literal, control)
  544. return new_string
  545. # ── Replacement shaping ──────────────────────────────────────────────────
  546. def _leading_whitespace(line: str) -> str:
  547. return line[:len(line) - len(line.lstrip(" \t"))]
  548. def _first_meaningful_line(text: str) -> Optional[str]:
  549. return next((line for line in text.split("\n") if line.strip()), None)
  550. def _match_starts_mid_line(content: str, start: int, end: int) -> bool:
  551. """Whether text outside the match precedes its first non-blank line.
  552. Leading newlines and blank lines do not make an anchor partial-line: the first
  553. code line can still be captured in full and need indentation adjustment.
  554. """
  555. first_line_start = start
  556. for line in content[start:end].split("\n"):
  557. if line.strip():
  558. line_start = content.rfind("\n", 0, first_line_start) + 1
  559. return bool(content[line_start:first_line_start].strip(" \t\r"))
  560. first_line_start += len(line) + 1
  561. return False
  562. def _reindent_replacement(file_region: str, old_string: str, new_string: str, *,
  563. match_starts_mid_line: bool) -> str:
  564. """Re-anchor ``new_string``'s indentation onto the file's actual base indent after a
  565. non-exact match: swap the LLM base prefix (first non-blank old_string line) for the
  566. file's, preserving relative nesting; shallower lines anchor to the file base.
  567. Preserve the supplied indentation when non-whitespace text precedes the match's
  568. first non-blank line: a partial-line expression has no reliable base indent.
  569. Leading line breaks and blank lines still allow whole-line re-anchoring.
  570. """
  571. if not new_string or match_starts_mid_line:
  572. return new_string
  573. old_first = _first_meaningful_line(old_string)
  574. file_first = _first_meaningful_line(file_region)
  575. if old_first is None or file_first is None:
  576. return new_string
  577. old_indent = _leading_whitespace(old_first)
  578. file_indent = _leading_whitespace(file_first)
  579. if old_indent == file_indent:
  580. return new_string
  581. out_lines: list[str] = []
  582. for line in new_string.split("\n"):
  583. if not line.strip():
  584. out_lines.append(line)
  585. elif _leading_whitespace(line).startswith(old_indent):
  586. out_lines.append(file_indent + line[len(old_indent):])
  587. else:
  588. out_lines.append(file_indent + line.lstrip(" \t"))
  589. return "\n".join(out_lines)
  590. def _unicode_edit_plan(old_string: str, new_string: str) -> tuple[str, list]:
  591. """``(normalized old, old->new opcodes)``: independent of the file region, so
  592. a replace_all computes it once for every match."""
  593. norm_old = _unicode_normalize(old_string)
  594. return norm_old, SequenceMatcher(None, norm_old, new_string).get_opcodes()
  595. def _preserve_unicode_in_replacement(file_region: str, new_string: str,
  596. plan: tuple[str, list]) -> str:
  597. """Apply only the old->new edits onto ``file_region``'s original (Unicode) text,
  598. so a unicode_normalized match doesn't flatten the file's em-dashes/smart quotes.
  599. ``plan`` is ``_unicode_edit_plan(old_string, new_string)``."""
  600. norm_old, opcodes = plan
  601. if norm_old != _unicode_normalize(file_region):
  602. return new_string # strategy shouldn't have fired; fall back
  603. file_orig_to_norm = _build_orig_to_norm_map(file_region)
  604. result_parts: list[str] = []
  605. for tag, i1, i2, j1, j2 in opcodes:
  606. if tag == "equal":
  607. # The original char owning norm index i1, even one inside a multi-char expansion (em-dash -> '--').
  608. orig_start = bisect.bisect_right(file_orig_to_norm, i1) - 1
  609. orig_end = _norm_end_to_orig(file_orig_to_norm, orig_start, i2)
  610. result_parts.append(file_region[orig_start:orig_end])
  611. elif tag != "delete":
  612. result_parts.append(new_string[j1:j2])
  613. return "".join(result_parts)
  614. def _apply_replacements(content: str, matches: list[Span],
  615. new_string: str, old_string: Optional[str] = None,
  616. unicode_plan: Optional[tuple[str, list]] = None) -> str:
  617. """Splice ``new_string`` over each span (end-to-start so offsets stay valid);
  618. ``old_string`` non-None (non-exact match) re-indents it per region, and
  619. ``unicode_plan`` (unicode_normalized match) keeps each region's typography."""
  620. result = content
  621. for start, end in sorted(matches, key=lambda x: x[0], reverse=True):
  622. adjusted = new_string
  623. if old_string is not None:
  624. region = content[start:end]
  625. if unicode_plan is not None:
  626. # Each occurrence may use different typographic characters even
  627. # though all normalize to the same old_string.
  628. adjusted = _preserve_unicode_in_replacement(region, adjusted, unicode_plan)
  629. adjusted = _reindent_replacement(
  630. region, old_string, adjusted,
  631. match_starts_mid_line=_match_starts_mid_line(content, start, end),
  632. )
  633. result = result[:start] + adjusted + result[end:]
  634. return result
  635. # ── "Did you mean?" diagnostics ──────────────────────────────────────────
  636. def _visualize_whitespace(line: str) -> str:
  637. """Render the leading whitespace run visibly (→ = tab, · = space)."""
  638. stripped = line.lstrip(" \t")
  639. prefix = line[:len(line) - len(stripped)]
  640. return prefix.replace("\t", "→").replace(" ", "·") + stripped
  641. def find_closest_lines(old_string: str, content: str, context_lines: int = 2, max_results: int = 3) -> str:
  642. """Numbered snippets of the lines most similar to old_string's anchor line, or ''."""
  643. if not old_string or not content:
  644. return ""
  645. old_lines = old_string.splitlines()
  646. content_lines = content.splitlines()
  647. if not old_lines or not content_lines:
  648. return ""
  649. anchor = old_lines[0].strip() or next((l.strip() for l in old_lines if l.strip()), "")
  650. if not anchor:
  651. return ""
  652. scored = sorted(((SequenceMatcher(None, anchor, line.strip()).ratio(), i)
  653. for i, line in enumerate(content_lines) if line.strip()), key=lambda x: -x[0])
  654. top = [s for s in scored if s[0] > 0.3][:max_results]
  655. if not top:
  656. return ""
  657. parts = []
  658. seen_ranges = set()
  659. for _, line_idx in top:
  660. start = max(0, line_idx - context_lines)
  661. end = min(len(content_lines), line_idx + len(old_lines) + context_lines)
  662. if (start, end) in seen_ranges:
  663. continue
  664. seen_ranges.add((start, end))
  665. parts.append("\n".join(
  666. f"{start + j + 1:4d}| {content_lines[start + j]}" for j in range(end - start)))
  667. result = "\n---\n".join(parts)
  668. # Whitespace-shaped miss: best line equals the anchor once stripped. Show
  669. # both with visible leading whitespace so the model copies the file's.
  670. best_line = content_lines[top[0][1]]
  671. if best_line.strip() == anchor and best_line != old_lines[0]:
  672. result += (
  673. "\n\nWhitespace difference detected (→ = tab, · = space):\n"
  674. f" file has: {_visualize_whitespace(best_line)}\n"
  675. f" you sent: {_visualize_whitespace(old_lines[0])}\n"
  676. "Use the exact whitespace shown in 'file has'.")
  677. return result
  678. def format_no_match_hint(error: Optional[str], match_count: int,
  679. old_string: str, content: str) -> str:
  680. """'\\n\\nDid you mean...' snippet for plain no-match errors only, else '' (ambiguous /
  681. escape-drift / identical errors also have ``match_count == 0`` but a hint would mislead)."""
  682. if match_count != 0 or not error or not error.startswith("Could not find"):
  683. return ""
  684. hint = find_closest_lines(old_string, content)
  685. return "\n\nDid you mean one of these sections?\n" + hint if hint else ""