zero/internal/tools/edit_replacers.go

package tools

// Fuzzy fallback matching for edit_file. When the model's old_string fails to
// match byte-for-byte (drifted indentation, collapsed whitespace, escaped
// characters, a slightly-misremembered middle line), these replacers propose
// candidate spans that plausibly correspond to what the model intended. Only a
// candidate that occurs literally in the file is accepted, so the replacement
// itself is always exact even when the match was tolerant.
//
// Strategy cascade ported from opencode's edit tool, whose replacers were in
// turn distilled from Cline's diff-apply evals and gemini-cli's edit corrector.

import (
	"errors"
	"regexp"
	"strings"
)

// editReplacer proposes candidate spans for find inside content. Candidates
// are re-validated by fuzzyEditMatch before use.
type editReplacer func(content, find string) []string

var (
	errEditFuzzyNotFound  = errors.New("no fuzzy match for old_string")
	errEditFuzzyAmbiguous = errors.New("fuzzy match for old_string is ambiguous")
)

// Minimum average middle-line similarity for block-anchor matches.
const editAnchorSimilarityThreshold = 0.65

// fuzzyEditMatch runs the replacer cascade and returns the exact span of
// content to replace. When replaceAll is false the span must be unique in
// content; an ambiguous candidate is skipped in favor of later candidates and
// only reported if nothing unique is found. A span wildly larger than
// old_string is refused outright rather than risking a destructive edit.
func fuzzyEditMatch(content, find string, replaceAll bool) (string, error) {
	replacers := []editReplacer{
		lineTrimmedReplacer,
		blockAnchorReplacer,
		whitespaceNormalizedReplacer,
		indentationFlexibleReplacer,
		escapeNormalizedReplacer,
		trimmedBoundaryReplacer,
		contextAwareReplacer,
	}
	found := false
	for _, replacer := range replacers {
		for _, search := range replacer(content, find) {
			if search == "" {
				continue
			}
			index := strings.Index(content, search)
			if index < 0 {
				continue
			}
			found = true
			if isDisproportionateEditMatch(search, find) {
				return "", errors.New("refusing replacement because the matched span is much larger than old_string; re-read the file and provide the full exact old_string for the intended replacement")
			}
			if replaceAll {
				return search, nil
			}
			if strings.LastIndex(content, search) != index {
				continue
			}
			return search, nil
		}
	}
	if !found {
		return "", errEditFuzzyNotFound
	}
	return "", errEditFuzzyAmbiguous
}

// isDisproportionateEditMatch guards against anchor-style replacers matching a
// span far larger than the text the model asked to replace (e.g. first/last
// line anchors bridging hundreds of unrelated lines).
func isDisproportionateEditMatch(search, find string) bool {
	findLines := strings.Count(find, "\n") + 1
	searchLines := strings.Count(search, "\n") + 1
	limit := findLines + 3
	if findLines*2 > limit {
		limit = findLines * 2
	}
	if searchLines >= limit {
		return true
	}
	if findLines == 1 {
		return false
	}
	searchTrimmed := len(strings.TrimSpace(search))
	findTrimmed := len(strings.TrimSpace(find))
	byteLimit := findTrimmed + 500
	if findTrimmed*4 > byteLimit {
		byteLimit = findTrimmed * 4
	}
	return searchTrimmed > byteLimit
}

// splitFindLines splits find into lines, dropping the trailing empty line a
// trailing newline produces so windows align with real content lines.
func splitFindLines(find string) []string {
	lines := strings.Split(find, "\n")
	if len(lines) > 0 && lines[len(lines)-1] == "" {
		lines = lines[:len(lines)-1]
	}
	return lines
}

// lineTrimmedReplacer matches when every line equals the corresponding
// old_string line after trimming surrounding whitespace.
func lineTrimmedReplacer(content, find string) []string {
	contentLines := strings.Split(content, "\n")
	findLines := splitFindLines(find)
	if len(findLines) == 0 {
		return nil
	}
	var candidates []string
	for i := 0; i+len(findLines) <= len(contentLines); i++ {
		matches := true
		for j := range findLines {
			if strings.TrimSpace(contentLines[i+j]) != strings.TrimSpace(findLines[j]) {
				matches = false
				break
			}
		}
		if matches {
			candidates = append(candidates, strings.Join(contentLines[i:i+len(findLines)], "\n"))
		}
	}
	return candidates
}

// blockAnchorReplacer anchors on the first and last lines (trimmed) and
// accepts the block when the middle lines average >= the similarity threshold
// (Levenshtein-based), tolerating a slightly misremembered interior.
func blockAnchorReplacer(content, find string) []string {
	findLines := splitFindLines(find)
	if len(findLines) < 3 {
		return nil
	}
	contentLines := strings.Split(content, "\n")
	firstAnchor := strings.TrimSpace(findLines[0])
	lastAnchor := strings.TrimSpace(findLines[len(findLines)-1])
	searchBlockSize := len(findLines)
	maxLineDelta := searchBlockSize / 4
	if maxLineDelta < 1 {
		maxLineDelta = 1
	}

	type span struct{ start, end int }
	var candidates []span
	for i := 0; i < len(contentLines); i++ {
		if strings.TrimSpace(contentLines[i]) != firstAnchor {
			continue
		}
		// Only the first occurrence of the last anchor after this start counts,
		// mirroring the reference implementation: a farther-away closing line is
		// assumed to close a different block.
		for j := i + 2; j < len(contentLines); j++ {
			if strings.TrimSpace(contentLines[j]) != lastAnchor {
				continue
			}
			actualBlockSize := j - i + 1
			delta := actualBlockSize - searchBlockSize
			if delta < 0 {
				delta = -delta
			}
			if delta <= maxLineDelta {
				candidates = append(candidates, span{start: i, end: j})
			}
			break
		}
	}
	if len(candidates) == 0 {
		return nil
	}

	middleSimilarity := func(candidate span) float64 {
		actualBlockSize := candidate.end - candidate.start + 1
		linesToCheck := searchBlockSize - 2
		if actualBlockSize-2 < linesToCheck {
			linesToCheck = actualBlockSize - 2
		}
		if linesToCheck <= 0 {
			return 1.0
		}
		similarity := 0.0
		for j := 1; j < searchBlockSize-1 && j < actualBlockSize-1; j++ {
			contentLine := strings.TrimSpace(contentLines[candidate.start+j])
			findLine := strings.TrimSpace(findLines[j])
			maxLen := len(contentLine)
			if len(findLine) > maxLen {
				maxLen = len(findLine)
			}
			if maxLen == 0 {
				continue
			}
			distance := levenshtein(contentLine, findLine)
			similarity += 1 - float64(distance)/float64(maxLen)
		}
		return similarity / float64(linesToCheck)
	}

	best := candidates[0]
	if len(candidates) > 1 {
		bestSimilarity := -1.0
		for _, candidate := range candidates {
			if s := middleSimilarity(candidate); s > bestSimilarity {
				bestSimilarity = s
				best = candidate
			}
		}
		if bestSimilarity < editAnchorSimilarityThreshold {
			return nil
		}
	} else if middleSimilarity(best) < editAnchorSimilarityThreshold {
		return nil
	}
	return []string{strings.Join(contentLines[best.start:best.end+1], "\n")}
}

var editWhitespaceRun = regexp.MustCompile(`\s+`)

func normalizeEditWhitespace(text string) string {
	return strings.TrimSpace(editWhitespaceRun.ReplaceAllString(text, " "))
}

// whitespaceNormalizedReplacer matches after collapsing all whitespace runs to
// a single space: full lines, sub-line spans (via a word-boundary regex), and
// multi-line windows.
func whitespaceNormalizedReplacer(content, find string) []string {
	normalizedFind := normalizeEditWhitespace(find)
	if normalizedFind == "" {
		return nil
	}
	contentLines := strings.Split(content, "\n")
	var candidates []string
	var subLinePattern *regexp.Regexp
	for _, line := range contentLines {
		normalizedLine := normalizeEditWhitespace(line)
		if normalizedLine == normalizedFind {
			candidates = append(candidates, line)
			continue
		}
		if !strings.Contains(normalizedLine, normalizedFind) {
			continue
		}
		if subLinePattern == nil {
			words := strings.Fields(find)
			quoted := make([]string, len(words))
			for i, word := range words {
				quoted[i] = regexp.QuoteMeta(word)
			}
			pattern, err := regexp.Compile(strings.Join(quoted, `\s+`))
			if err != nil {
				continue
			}
			subLinePattern = pattern
		}
		if match := subLinePattern.FindString(line); match != "" {
			candidates = append(candidates, match)
		}
	}

	findLines := strings.Split(find, "\n")
	if len(findLines) > 1 {
		for i := 0; i+len(findLines) <= len(contentLines); i++ {
			block := strings.Join(contentLines[i:i+len(findLines)], "\n")
			if normalizeEditWhitespace(block) == normalizedFind {
				candidates = append(candidates, block)
			}
		}
	}
	return candidates
}

// stripCommonIndentation removes the minimum leading-whitespace width shared
// by all non-empty lines, so blocks match regardless of their nesting depth.
func stripCommonIndentation(text string) string {
	lines := strings.Split(text, "\n")
	minIndent := -1
	for _, line := range lines {
		if strings.TrimSpace(line) == "" {
			continue
		}
		indent := len(line) - len(strings.TrimLeft(line, " \t"))
		if minIndent < 0 || indent < minIndent {
			minIndent = indent
		}
	}
	if minIndent <= 0 {
		return text
	}
	stripped := make([]string, len(lines))
	for i, line := range lines {
		if strings.TrimSpace(line) == "" {
			stripped[i] = line
			continue
		}
		stripped[i] = line[minIndent:]
	}
	return strings.Join(stripped, "\n")
}

func indentationFlexibleReplacer(content, find string) []string {
	normalizedFind := stripCommonIndentation(find)
	contentLines := strings.Split(content, "\n")
	findLines := strings.Split(find, "\n")
	var candidates []string
	for i := 0; i+len(findLines) <= len(contentLines); i++ {
		block := strings.Join(contentLines[i:i+len(findLines)], "\n")
		if stripCommonIndentation(block) == normalizedFind {
			candidates = append(candidates, block)
		}
	}
	return candidates
}

var editEscapeSequence = regexp.MustCompile("\\\\(n|t|r|'|\"|`|\\\\|\\n|\\$)")

// unescapeEditString undoes one level of string escaping (\n, \t, \", \\, a
// backslash-newline continuation, \$) — the model sometimes reproduces file
// content as it appeared inside a quoted string literal.
func unescapeEditString(text string) string {
	return editEscapeSequence.ReplaceAllStringFunc(text, func(match string) string {
		switch match[1:] {
		case "n":
			return "\n"
		case "t":
			return "\t"
		case "r":
			return "\r"
		case "\n":
			return "\n"
		default:
			// ', ", `, \, $ all unescape to themselves.
			return match[1:]
		}
	})
}

func escapeNormalizedReplacer(content, find string) []string {
	unescapedFind := unescapeEditString(find)
	var candidates []string
	if strings.Contains(content, unescapedFind) {
		candidates = append(candidates, unescapedFind)
	}
	contentLines := strings.Split(content, "\n")
	findLines := strings.Split(unescapedFind, "\n")
	for i := 0; i+len(findLines) <= len(contentLines); i++ {
		block := strings.Join(contentLines[i:i+len(findLines)], "\n")
		if unescapeEditString(block) == unescapedFind {
			candidates = append(candidates, block)
		}
	}
	return candidates
}

// trimmedBoundaryReplacer tolerates stray leading/trailing whitespace (often
// blank lines) around an otherwise-exact old_string.
func trimmedBoundaryReplacer(content, find string) []string {
	trimmedFind := strings.TrimSpace(find)
	if trimmedFind == find || trimmedFind == "" {
		return nil
	}
	var candidates []string
	if strings.Contains(content, trimmedFind) {
		candidates = append(candidates, trimmedFind)
	}
	contentLines := strings.Split(content, "\n")
	findLines := strings.Split(find, "\n")
	for i := 0; i+len(findLines) <= len(contentLines); i++ {
		block := strings.Join(contentLines[i:i+len(findLines)], "\n")
		if strings.TrimSpace(block) == trimmedFind {
			candidates = append(candidates, block)
		}
	}
	return candidates
}

// contextAwareReplacer anchors on the first and last lines and accepts an
// equal-length block when at least half of its non-empty middle lines match
// after trimming — a cheaper, stricter cousin of blockAnchorReplacer.
func contextAwareReplacer(content, find string) []string {
	findLines := splitFindLines(find)
	if len(findLines) < 3 {
		return nil
	}
	contentLines := strings.Split(content, "\n")
	firstAnchor := strings.TrimSpace(findLines[0])
	lastAnchor := strings.TrimSpace(findLines[len(findLines)-1])
	var candidates []string
	for i := 0; i < len(contentLines); i++ {
		if strings.TrimSpace(contentLines[i]) != firstAnchor {
			continue
		}
		for j := i + 2; j < len(contentLines); j++ {
			if strings.TrimSpace(contentLines[j]) != lastAnchor {
				continue
			}
			if j-i+1 == len(findLines) {
				matching, nonEmpty := 0, 0
				for k := 1; k < len(findLines)-1; k++ {
					blockLine := strings.TrimSpace(contentLines[i+k])
					findLine := strings.TrimSpace(findLines[k])
					if blockLine == "" && findLine == "" {
						continue
					}
					nonEmpty++
					if blockLine == findLine {
						matching++
					}
				}
				if nonEmpty == 0 || float64(matching)/float64(nonEmpty) >= 0.5 {
					candidates = append(candidates, strings.Join(contentLines[i:j+1], "\n"))
				}
			}
			break
		}
	}
	return candidates
}

// levenshtein computes edit distance with a two-row rolling matrix.
func levenshtein(a, b string) int {
	if a == "" {
		return len(b)
	}
	if b == "" {
		return len(a)
	}
	previous := make([]int, len(b)+1)
	current := make([]int, len(b)+1)
	for j := range previous {
		previous[j] = j
	}
	for i := 1; i <= len(a); i++ {
		current[0] = i
		for j := 1; j <= len(b); j++ {
			cost := 1
			if a[i-1] == b[j-1] {
				cost = 0
			}
			minimum := previous[j] + 1
			if current[j-1]+1 < minimum {
				minimum = current[j-1] + 1
			}
			if previous[j-1]+cost < minimum {
				minimum = previous[j-1] + cost
			}
			current[j] = minimum
		}
		previous, current = current, previous
	}
	return previous[len(b)]
}