spb/khaelor Public
KHAELOR — a terminal-native autonomous engineering agent powered by Anthropic.
TypeScript 82.9%
HTML 14.9%
CSS 1.1%
JavaScript 0.7%
1/**2 * KHAELOR3 * File: src/tools/replacers.ts4 * Description: The nine-strategy edit replacer cascade with uniqueness and disproportion guards (TOOL_PROTOCOL §4.3–4.4).5 *6 * Author: Simon-Pierre Boucher7 * Contact: contact@spboucher.ai8 */910/** Strategy names, in cascade order (TOOL_PROTOCOL §4.3). */11export type ReplacerStrategy =12 | "exact"13 | "line-trimmed"14 | "whitespace-normalized"15 | "indentation-flexible"16 | "escape-normalized"17 | "trimmed-boundary"18 | "block-anchor"19 | "context-aware"20 | "multi-occurrence";2122/** Model-facing phrase for the success parenthetical (§4.6). */23export const STRATEGY_PHRASES: Record<ReplacerStrategy, string> = {24 exact: "matched exactly",25 "line-trimmed": "matched with line-trimmed whitespace",26 "whitespace-normalized": "matched with whitespace normalization",27 "indentation-flexible": "matched with indentation flexibility",28 "escape-normalized": "matched with escape normalization",29 "trimmed-boundary": "matched at trimmed boundaries",30 "block-anchor": "matched with block anchors",31 "context-aware": "matched with context anchors",32 "multi-occurrence": "matched exactly",33};3435/** One replacement site: [start, end) character span and the text to insert. */36export interface MatchSpan {37 start: number;38 end: number;39 replacement: string;40}4142export interface NearMiss {43 /** 1-based line range of the closest candidate block. */44 startLine: number;45 endLine: number;46 /** 1-based line number of the first differing line. */47 diffLine: number;48 kind: "whitespace" | "content";49 expected: string;50 actual: string;51}5253export type CascadeResult =54 | { kind: "match"; strategy: ReplacerStrategy; matches: MatchSpan[] }55 | { kind: "disproportionate"; candidateLength: number; oldLength: number }56 | { kind: "not-found"; nearMiss?: NearMiss };5758// ─────────────────────────── line indexing ───────────────────────────5960interface LineIndex {61 lines: string[];62 /** Character offset of each line start. */63 starts: number[];64}6566function indexLines(text: string): LineIndex {67 const lines = text.split("\n");68 const starts: number[] = new Array<number>(lines.length);69 let offset = 0;70 for (let i = 0; i < lines.length; i++) {71 starts[i] = offset;72 offset += (lines[i] as string).length + 1;73 }74 return { lines, starts };75}7677/** Character span covering lines [i, i+count) without the trailing newline. */78function spanOf(index: LineIndex, i: number, count: number): { start: number; end: number } {79 const lastLine = i + count - 1;80 return {81 start: index.starts[i] as number,82 end: (index.starts[lastLine] as number) + (index.lines[lastLine] as string).length,83 };84}8586/**87 * For line-based strategies: a single trailing newline on old_string is88 * stripped (with the symmetric strip on new_string) so window spans replace89 * whole lines without duplicating the file's own newline.90 */91function stripTrailingNewline(oldString: string, newString: string): [string, string] {92 if (!oldString.endsWith("\n")) return [oldString, newString];93 return [94 oldString.slice(0, -1),95 newString.endsWith("\n") ? newString.slice(0, -1) : newString,96 ];97}9899// ─────────────────────────── small helpers ───────────────────────────100101function exactScan(text: string, needle: string, replacement: string): MatchSpan[] {102 const matches: MatchSpan[] = [];103 if (needle.length === 0) return matches;104 let from = 0;105 for (;;) {106 const at = text.indexOf(needle, from);107 if (at === -1) break;108 matches.push({ start: at, end: at + needle.length, replacement });109 from = at + needle.length;110 }111 return matches;112}113114function normalizeWhitespace(s: string): string {115 return s.replace(/\s+/g, " ").trim();116}117118function leadingWhitespace(line: string): string {119 return (/^[ \t]*/.exec(line) as RegExpExecArray)[0];120}121122function commonIndentLength(lines: string[]): number {123 let min = Number.POSITIVE_INFINITY;124 for (const line of lines) {125 if (line.trim().length === 0) continue;126 min = Math.min(min, leadingWhitespace(line).length);127 }128 return Number.isFinite(min) ? min : 0;129}130131function unescapeLiterals(s: string): string {132 return s.replace(/\\(n|t|r|'|"|`|\\)/g, (_all, ch: string) => {133 switch (ch) {134 case "n":135 return "\n";136 case "t":137 return "\t";138 case "r":139 return "\r";140 default:141 return ch;142 }143 });144}145146const MAX_LEVENSHTEIN_CHARS = 10_000;147148/** Similarity ratio in [0, 1] — 1 means identical. */149function levenshteinRatio(a: string, b: string): number {150 if (a === b) return 1;151 const maxLen = Math.max(a.length, b.length);152 if (maxLen === 0) return 1;153 if (maxLen > MAX_LEVENSHTEIN_CHARS) return 0;154 let previous = new Uint32Array(b.length + 1);155 let current = new Uint32Array(b.length + 1);156 for (let j = 0; j <= b.length; j++) previous[j] = j;157 for (let i = 1; i <= a.length; i++) {158 current[0] = i;159 for (let j = 1; j <= b.length; j++) {160 const cost = a[i - 1] === b[j - 1] ? 0 : 1;161 current[j] = Math.min(162 (previous[j] as number) + 1,163 (current[j - 1] as number) + 1,164 (previous[j - 1] as number) + cost,165 );166 }167 [previous, current] = [current, previous];168 }169 return 1 - (previous[b.length] as number) / maxLen;170}171172/** Disproportionate-match guard threshold (TOOL_PROTOCOL §4.4). */173function disproportionLimit(oldLength: number): number {174 return Math.max(3 * oldLength, oldLength + 1000);175}176177// ─────────────────────────── strategies ───────────────────────────178179/**180 * Strategy 2 — line-trimmed. Tolerates per-line trailing-whitespace drift181 * (each line's leading whitespace must still match). Leading-indent drift is182 * deliberately left to strategies 3/4 so that indentation-flexible matching183 * (and its re-indentation of new_string) stays reachable — with full-trim184 * comparison here, §4.3 strategy 4 would be dead code.185 */186function lineTrimmed(index: LineIndex, oldBody: string, newBody: string): MatchSpan[] {187 const oldLines = oldBody.split("\n");188 const count = oldLines.length;189 const matches: MatchSpan[] = [];190 if (count === 0 || oldBody.trim().length === 0) return matches;191 for (let i = 0; i + count <= index.lines.length; i++) {192 let all = true;193 for (let k = 0; k < count; k++) {194 const fileLine = index.lines[i + k] as string;195 const oldLine = oldLines[k] as string;196 if (197 fileLine.trim() !== oldLine.trim() ||198 leadingWhitespace(fileLine) !== leadingWhitespace(oldLine)199 ) {200 all = false;201 break;202 }203 }204 if (all) matches.push({ ...spanOf(index, i, count), replacement: newBody });205 }206 return matches;207}208209/**210 * Strategy 3 — whitespace-normalized. Single-line old_strings only: all runs211 * of whitespace collapsed to single spaces on both sides. Multi-line212 * whitespace drift belongs to strategy 4 (which preserves file indentation).213 */214function whitespaceNormalized(index: LineIndex, oldBody: string, newBody: string): MatchSpan[] {215 const matches: MatchSpan[] = [];216 if (oldBody.includes("\n")) return matches;217 const target = normalizeWhitespace(oldBody);218 if (target.length === 0) return matches; // needs ≥1 non-whitespace token219 for (let i = 0; i < index.lines.length; i++) {220 const fileLine = index.lines[i] as string;221 if (normalizeWhitespace(fileLine) !== target) continue;222 // Preserve the file's own leading whitespace when the replacement is single-line.223 const replacement = newBody.includes("\n")224 ? newBody225 : leadingWhitespace(fileLine) + newBody.trimStart();226 matches.push({ ...spanOf(index, i, 1), replacement });227 }228 return matches;229}230231function indentationFlexible(index: LineIndex, oldBody: string, newBody: string): MatchSpan[] {232 const oldLines = oldBody.split("\n");233 const count = oldLines.length;234 const matches: MatchSpan[] = [];235 if (oldBody.trim().length === 0) return matches;236 const oldIndent = commonIndentLength(oldLines);237 const oldStripped = oldLines.map((l) => (l.trim().length === 0 ? "" : l.slice(oldIndent).trimEnd()));238239 for (let i = 0; i + count <= index.lines.length; i++) {240 const window = index.lines.slice(i, i + count);241 const fileIndentLen = commonIndentLength(window);242 let all = true;243 for (let k = 0; k < count; k++) {244 const fileLine = window[k] as string;245 const stripped = fileLine.trim().length === 0 ? "" : fileLine.slice(fileIndentLen).trimEnd();246 if (stripped !== oldStripped[k]) {247 all = false;248 break;249 }250 }251 if (!all) continue;252 // Re-apply the FILE's indentation to new_string (indentation preservation).253 const firstContent = window.find((l) => l.trim().length > 0) ?? "";254 const fileIndent = leadingWhitespace(firstContent).slice(0, fileIndentLen);255 const newLines = newBody.split("\n");256 const newIndentLen = commonIndentLength(newLines);257 const reindented = newLines258 .map((l) => (l.trim().length === 0 ? l : fileIndent + l.slice(newIndentLen)))259 .join("\n");260 matches.push({ ...spanOf(index, i, count), replacement: reindented });261 }262 return matches;263}264265interface AnchorScan {266 matches: MatchSpan[];267 guardHit?: { candidateLength: number };268}269270function blockAnchor(271 index: LineIndex,272 oldBody: string,273 newBody: string,274 oldRawLength: number,275): AnchorScan {276 const oldLines = oldBody.split("\n");277 const count = oldLines.length;278 if (count < 3) return { matches: [] };279 const first = (oldLines[0] as string).trim();280 const last = (oldLines[count - 1] as string).trim();281 const oldMiddle = oldLines282 .slice(1, -1)283 .map((l) => l.trim())284 .join("\n");285 const minLines = Math.max(3, Math.floor(count * 0.75));286 const maxLines = Math.ceil(count * 1.25);287 const limit = disproportionLimit(oldRawLength);288289 let guardHit: { candidateLength: number } | undefined;290 const scored: Array<{ span: { start: number; end: number }; score: number }> = [];291292 for (let i = 0; i < index.lines.length; i++) {293 if ((index.lines[i] as string).trim() !== first) continue;294 for (let size = minLines; size <= maxLines; size++) {295 const j = i + size - 1;296 if (j >= index.lines.length) break;297 if ((index.lines[j] as string).trim() !== last) continue;298 const span = spanOf(index, i, size);299 const candidateLength = span.end - span.start;300 if (candidateLength > limit) {301 guardHit = { candidateLength };302 continue;303 }304 const candidateMiddle = index.lines305 .slice(i + 1, j)306 .map((l) => l.trim())307 .join("\n");308 const score = levenshteinRatio(oldMiddle, candidateMiddle);309 if (score >= 0.65) scored.push({ span, score });310 }311 }312313 if (scored.length === 0) return guardHit !== undefined ? { matches: [], guardHit } : { matches: [] };314 const best = Math.max(...scored.map((c) => c.score));315 const winners = scored.filter((c) => c.score === best);316 const result: AnchorScan = {317 matches: winners.map((c) => ({ ...c.span, replacement: newBody })),318 };319 if (guardHit !== undefined) result.guardHit = guardHit;320 return result;321}322323function contextAware(324 index: LineIndex,325 oldBody: string,326 newBody: string,327 oldRawLength: number,328): AnchorScan {329 const oldLines = oldBody.split("\n");330 const count = oldLines.length;331 if (count < 3) return { matches: [] };332 const first = (oldLines[0] as string).trim();333 const last = (oldLines[count - 1] as string).trim();334 const middle = oldLines.slice(1, -1).map((l) => l.trim());335 const limit = disproportionLimit(oldRawLength);336337 let guardHit: { candidateLength: number } | undefined;338 const matches: MatchSpan[] = [];339 for (let i = 0; i + count <= index.lines.length; i++) {340 if ((index.lines[i] as string).trim() !== first) continue;341 if ((index.lines[i + count - 1] as string).trim() !== last) continue;342 let equal = 0;343 for (let k = 0; k < middle.length; k++) {344 if ((index.lines[i + 1 + k] as string).trim() === middle[k]) equal += 1;345 }346 if (middle.length > 0 && equal / middle.length < 0.5) continue;347 const span = spanOf(index, i, count);348 if (span.end - span.start > limit) {349 guardHit = { candidateLength: span.end - span.start };350 continue;351 }352 matches.push({ ...span, replacement: newBody });353 }354 const result: AnchorScan = { matches };355 if (guardHit !== undefined) result.guardHit = guardHit;356 return result;357}358359// ─────────────────────────── near-miss search ───────────────────────────360361/** Best same-length window by fraction of trimmed-equal lines (for the not-found message). */362export function findNearMiss(text: string, oldString: string): NearMiss | undefined {363 const [oldBody] = stripTrailingNewline(oldString, "");364 const index = indexLines(text);365 const oldLines = oldBody.split("\n");366 const count = oldLines.length;367 if (count === 0 || oldBody.trim().length === 0 || count > index.lines.length) return undefined;368369 let bestScore = 0;370 let bestAt = -1;371 for (let i = 0; i + count <= index.lines.length; i++) {372 let equal = 0;373 for (let k = 0; k < count; k++) {374 if ((index.lines[i + k] as string).trim() === (oldLines[k] as string).trim()) equal += 1;375 }376 const score = equal / count;377 if (score > bestScore) {378 bestScore = score;379 bestAt = i;380 }381 }382 if (bestAt === -1 || bestScore === 0) return undefined;383384 for (let k = 0; k < count; k++) {385 const expected = oldLines[k] as string;386 const actual = index.lines[bestAt + k] as string;387 if (expected !== actual) {388 return {389 startLine: bestAt + 1,390 endLine: bestAt + count,391 diffLine: bestAt + k + 1,392 kind: expected.trim() === actual.trim() ? "whitespace" : "content",393 expected,394 actual,395 };396 }397 }398 return undefined;399}400401// ─────────────────────────── the cascade ───────────────────────────402403/**404 * Run strategies 1–8 in order; the first strategy producing at least one405 * match wins and later strategies never run (TOOL_PROTOCOL §4.3). Guard406 * violations from fuzzy strategies surface as "disproportionate" only when407 * no strategy produced a trustworthy match.408 */409export function runCascade(text: string, oldString: string, newString: string): CascadeResult {410 // 1. Exact.411 const exact = exactScan(text, oldString, newString);412 if (exact.length > 0) return { kind: "match", strategy: "exact", matches: exact };413414 const [oldBody, newBody] = stripTrailingNewline(oldString, newString);415 const index = indexLines(text);416417 // 2. Line-trimmed.418 const trimmedLines = lineTrimmed(index, oldBody, newBody);419 if (trimmedLines.length > 0) {420 return { kind: "match", strategy: "line-trimmed", matches: trimmedLines };421 }422423 // 3. Whitespace-normalized.424 const wsNormalized = whitespaceNormalized(index, oldBody, newBody);425 if (wsNormalized.length > 0) {426 return { kind: "match", strategy: "whitespace-normalized", matches: wsNormalized };427 }428429 // 4. Indentation-flexible.430 const indentFlex = indentationFlexible(index, oldBody, newBody);431 if (indentFlex.length > 0) {432 return { kind: "match", strategy: "indentation-flexible", matches: indentFlex };433 }434435 // 5. Escape-normalized.436 const unescapedOld = unescapeLiterals(oldString);437 if (unescapedOld !== oldString) {438 const escaped = exactScan(text, unescapedOld, unescapeLiterals(newString));439 if (escaped.length > 0) {440 return { kind: "match", strategy: "escape-normalized", matches: escaped };441 }442 }443444 // 6. Trimmed-boundary.445 const trimmed = oldString.trim();446 if (trimmed !== oldString && trimmed.length > 0) {447 const boundary = exactScan(text, trimmed, newString.trim());448 if (boundary.length > 0) {449 return { kind: "match", strategy: "trimmed-boundary", matches: boundary };450 }451 }452453 // 7. Block-anchor (fuzzy, guarded).454 const anchor = blockAnchor(index, oldBody, newBody, oldString.length);455 if (anchor.matches.length > 0) {456 return { kind: "match", strategy: "block-anchor", matches: anchor.matches };457 }458459 // 8. Context-aware (fuzzy, guarded).460 const context = contextAware(index, oldBody, newBody, oldString.length);461 if (context.matches.length > 0) {462 return { kind: "match", strategy: "context-aware", matches: context.matches };463 }464465 const guardHit = anchor.guardHit ?? context.guardHit;466 if (guardHit !== undefined) {467 return {468 kind: "disproportionate",469 candidateLength: guardHit.candidateLength,470 oldLength: oldString.length,471 };472 }473474 const nearMiss = findNearMiss(text, oldString);475 return nearMiss !== undefined ? { kind: "not-found", nearMiss } : { kind: "not-found" };476}477478/** Strategy 9 — replace_all: all EXACT occurrences only (never fuzzy, §4.4). */479export function runMultiOccurrence(480 text: string,481 oldString: string,482 newString: string,483): CascadeResult {484 const matches = exactScan(text, oldString, newString);485 if (matches.length > 0) return { kind: "match", strategy: "multi-occurrence", matches };486 const nearMiss = findNearMiss(text, oldString);487 return nearMiss !== undefined ? { kind: "not-found", nearMiss } : { kind: "not-found" };488}489490/** Apply match spans (non-overlapping, in order) to the text. */491export function applyMatches(text: string, matches: MatchSpan[]): string {492 let out = "";493 let cursor = 0;494 for (const match of matches) {495 out += text.slice(cursor, match.start) + match.replacement;496 cursor = match.end;497 }498 return out + text.slice(cursor);499}500501/** 1-based line number of a character offset. */502export function lineNumberAt(text: string, offset: number): number {503 let line = 1;504 for (let i = 0; i < offset && i < text.length; i++) {505 if (text[i] === "\n") line += 1;506 }507 return line;508}509