1use crate::patch::matcher::{
7 normalize_indent, normalize_unicode, seek_sequence_tiered, SequenceMatch,
8};
9use crate::patch::parser::UpdateFileChunk;
10
11#[derive(Debug, Clone, Copy, PartialEq, Eq)]
12pub struct ClosestPartialMatch {
13 pub line_number: usize,
14 pub matched_lines: usize,
15 pub first_divergence: usize,
16}
17
18pub fn seek_sequence(
20 lines: &[&str],
21 pattern: &[&str],
22 start_index: usize,
23 eof: bool,
24) -> Option<usize> {
25 seek_sequence_tiered(lines, pattern, start_index, eof)
26 .map(|sequence_match| sequence_match.found)
27}
28
29fn line_refs(lines: &[String]) -> Vec<&str> {
30 lines.iter().map(String::as_str).collect()
31}
32
33fn compare_any(a: &str, b: &str) -> bool {
34 if a == b || a.trim_end() == b.trim_end() || a.trim() == b.trim() {
35 return true;
36 }
37
38 let normalized_a_indent = normalize_indent(a);
39 let normalized_b_indent = normalize_indent(b);
40 if normalized_a_indent.trim_end() == normalized_b_indent.trim_end() {
41 return true;
42 }
43
44 normalize_unicode(a.trim()) == normalize_unicode(b.trim())
45}
46
47pub fn find_closest_partial_match(lines: &[&str], pattern: &[&str]) -> Option<ClosestPartialMatch> {
49 if pattern.is_empty() || lines.is_empty() {
50 return None;
51 }
52
53 let mut candidates = Vec::new();
54 for (index, line) in lines.iter().enumerate() {
55 if compare_any(line, pattern[0]) {
56 candidates.push(index);
57 if candidates.len() >= 16 {
58 break;
59 }
60 }
61 }
62 if candidates.is_empty() {
63 return None;
64 }
65
66 let mut best: Option<ClosestPartialMatch> = None;
67 for start in candidates {
68 let mut matched = 0;
69 for (offset, expected) in pattern.iter().enumerate() {
70 let Some(actual) = lines.get(start + offset) else {
71 break;
72 };
73 if !compare_any(actual, expected) {
74 break;
75 }
76 matched += 1;
77 }
78
79 if best.is_none_or(|current| matched > current.matched_lines) {
80 best = Some(ClosestPartialMatch {
81 line_number: start + 1,
82 matched_lines: matched,
83 first_divergence: matched,
84 });
85 }
86 }
87
88 best
89}
90
91fn seek_sequence_tiered_strings(
92 lines: &[String],
93 pattern: &[String],
94 start_index: usize,
95 eof: bool,
96) -> Option<SequenceMatch> {
97 let line_refs = line_refs(lines);
98 let pattern_refs: Vec<&str> = pattern.iter().map(String::as_str).collect();
99 seek_sequence_tiered(&line_refs, &pattern_refs, start_index, eof)
100}
101
102fn seek_sequence_strings(
103 lines: &[String],
104 pattern: &[String],
105 start_index: usize,
106 eof: bool,
107) -> Option<usize> {
108 let line_refs = line_refs(lines);
109 let pattern_refs: Vec<&str> = pattern.iter().map(String::as_str).collect();
110 seek_sequence(&line_refs, &pattern_refs, start_index, eof)
111}
112
113fn json_string(value: &str) -> String {
114 serde_json::to_string(value).expect("serializing a string to JSON should not fail")
115}
116
117pub fn apply_update_chunks(
119 original_content: &str,
120 file_path: &str,
121 chunks: &[UpdateFileChunk],
122) -> Result<String, String> {
123 let mut original_lines: Vec<String> = original_content
124 .split('\n')
125 .map(ToOwned::to_owned)
126 .collect();
127
128 if original_lines.last().is_some_and(String::is_empty) {
129 original_lines.pop();
130 }
131
132 let mut replacements: Vec<(usize, usize, Vec<String>)> = Vec::new();
133 let mut line_index = 0;
134
135 for chunk in chunks {
136 let change_context = chunk
137 .change_context
138 .as_ref()
139 .filter(|context| !context.is_empty());
140 if let Some(context) = change_context {
141 let line_refs = line_refs(&original_lines);
142 let context_pattern = [context.as_str()];
143 let Some(context_match) =
144 seek_sequence_tiered(&line_refs, &context_pattern, line_index, false)
145 else {
146 return Err(format!("Failed to find context '{context}' in {file_path}"));
147 };
148 line_index = context_match.found + context_match.line_count;
149 }
150
151 if chunk.old_lines.is_empty() {
152 let insertion_idx = if change_context.is_some() {
153 line_index
154 } else if original_lines.last().is_some_and(String::is_empty) {
155 original_lines.len() - 1
156 } else {
157 original_lines.len()
158 };
159 replacements.push((insertion_idx, 0, chunk.new_lines.clone()));
160 continue;
161 }
162
163 let mut pattern = chunk.old_lines.clone();
164 let mut new_slice = chunk.new_lines.clone();
165 let mut matched = seek_sequence_tiered_strings(
166 &original_lines,
167 &pattern,
168 line_index,
169 chunk.is_end_of_file,
170 );
171
172 if matched.is_none() && pattern.last().is_some_and(String::is_empty) {
173 pattern.pop();
174 if new_slice.last().is_some_and(String::is_empty) {
175 new_slice.pop();
176 }
177 matched = seek_sequence_tiered_strings(
178 &original_lines,
179 &pattern,
180 line_index,
181 chunk.is_end_of_file,
182 );
183 }
184
185 if let Some(sequence_match) = matched {
186 replacements.push((sequence_match.found, sequence_match.line_count, new_slice));
187 line_index = sequence_match.found + sequence_match.line_count;
188 } else {
189 let new_slice_trimmed: Vec<String> = new_slice
190 .iter()
191 .filter(|line| !line.trim().is_empty())
192 .cloned()
193 .collect();
194 let already_applied = !new_slice_trimmed.is_empty()
195 && seek_sequence_strings(
196 &original_lines,
197 &new_slice_trimmed,
198 0,
199 chunk.is_end_of_file,
200 )
201 .is_some();
202
203 let line_refs = line_refs(&original_lines);
204 let pattern_refs: Vec<&str> = pattern.iter().map(String::as_str).collect();
205 let closest = find_closest_partial_match(&line_refs, &pattern_refs);
206 let mut closest_hint = String::new();
207 if let Some(closest) = closest.filter(|closest| closest.matched_lines > 0) {
208 let file_line_no = closest.line_number + closest.first_divergence;
209 let expected_line = pattern.get(closest.first_divergence).map(String::as_str);
210 let expected_json =
211 expected_line.map_or_else(|| "undefined".to_owned(), json_string);
212 let actual_line = original_lines
213 .get(file_line_no.saturating_sub(1))
214 .map(String::as_str)
215 .unwrap_or("<EOF>");
216 closest_hint = format!(
217 "\n\nClosest match starts at line {} ({} of {} lines matched).\n\
218 First divergence at line {file_line_no}:\n expected: {}\n actual: {}",
219 closest.line_number,
220 closest.matched_lines,
221 pattern.len(),
222 expected_json,
223 json_string(actual_line)
224 );
225 }
226
227 let tried_tiers =
228 "exact, trimEnd, trim, indent (tab/space), unicode, reflow (whitespace-normalized)";
229 let already_applied_hint = if already_applied {
230 "\n\nHint: the replacement content for this hunk already appears in the file. \
231 The patch may have been partially applied in a prior turn — re-read the file \
232 to confirm which hunks still need to apply."
233 } else {
234 ""
235 };
236
237 return Err(format!(
238 "Failed to find expected lines in {file_path}:\n{}\n\n\
239 Tried match tiers: {tried_tiers}.{closest_hint}{already_applied_hint}",
240 chunk.old_lines.join("\n")
241 ));
242 }
243 }
244
245 replacements.sort_by(|left, right| left.0.cmp(&right.0));
246
247 let mut result = original_lines;
248 for (start_idx, old_len, new_segment) in replacements.into_iter().rev() {
249 result.splice(start_idx..start_idx + old_len, new_segment);
250 }
251
252 if result.last().is_none_or(|line| !line.is_empty()) {
253 result.push(String::new());
254 }
255
256 Ok(result.join("\n"))
257}
258
259#[cfg(test)]
260mod tests {
261 use super::*;
262
263 fn chunk(old_lines: &[&str], new_lines: &[&str]) -> UpdateFileChunk {
264 UpdateFileChunk {
265 old_lines: old_lines.iter().map(|line| (*line).to_owned()).collect(),
266 new_lines: new_lines.iter().map(|line| (*line).to_owned()).collect(),
267 change_context: None,
268 is_end_of_file: false,
269 }
270 }
271
272 fn context_chunk(context: &str, old_lines: &[&str], new_lines: &[&str]) -> UpdateFileChunk {
273 UpdateFileChunk {
274 old_lines: old_lines.iter().map(|line| (*line).to_owned()).collect(),
275 new_lines: new_lines.iter().map(|line| (*line).to_owned()).collect(),
276 change_context: Some(context.to_owned()),
277 is_end_of_file: false,
278 }
279 }
280
281 fn eof_chunk(old_lines: &[&str], new_lines: &[&str]) -> UpdateFileChunk {
282 UpdateFileChunk {
283 old_lines: old_lines.iter().map(|line| (*line).to_owned()).collect(),
284 new_lines: new_lines.iter().map(|line| (*line).to_owned()).collect(),
285 change_context: None,
286 is_end_of_file: true,
287 }
288 }
289
290 fn assert_apply_error(original: &str, file_path: &str, chunks: &[UpdateFileChunk]) -> String {
291 apply_update_chunks(original, file_path, chunks).unwrap_err()
292 }
293
294 #[test]
295 fn missing_change_context_matches_patch_parser_test_60_72() {
296 let chunks = [context_chunk("missing line", &["beta"], &["updated beta"])];
297 assert_eq!(
298 assert_apply_error("alpha\nbeta\n", "src/example.ts", &chunks),
299 "Failed to find context 'missing line' in src/example.ts"
300 );
301 }
302
303 #[test]
304 fn missing_old_lines_error_format_matches_patch_parser_test_74_85() {
305 let chunks = [chunk(&["missing line"], &["replacement line"])];
306 assert_eq!(
307 assert_apply_error("alpha\nbeta\n", "src/example.ts", &chunks),
308 "Failed to find expected lines in src/example.ts:\nmissing line\n\n\
309 Tried match tiers: exact, trimEnd, trim, indent (tab/space), unicode, reflow (whitespace-normalized)."
310 );
311 }
312
313 #[test]
314 fn already_applied_hint_matches_patch_parser_test_87_103() {
315 let chunks = [chunk(
316 &["const mainQuota = await getFreshMainQuota(auth.access, storage)"],
317 &["const mainQuota = await getMainQuotaForRouting(auth.access, storage)"],
318 )];
319 let file_with_rewrite_already_applied =
320 "alpha\nconst mainQuota = await getMainQuotaForRouting(auth.access, storage)\nbeta\n";
321
322 assert!(
323 assert_apply_error(file_with_rewrite_already_applied, "src/example.ts", &chunks)
324 .contains("already appears in the file")
325 );
326 }
327
328 #[test]
329 fn absent_old_and_new_lines_have_no_already_applied_hint_matches_patch_parser_test_105_122() {
330 let chunks = [chunk(&["missing old line"], &["missing new line"])];
331 let message = assert_apply_error("unrelated content\n", "src/example.ts", &chunks);
332 assert!(message.contains("Failed to find expected lines"));
333 assert!(!message.contains("already appears in the file"));
334 }
335
336 #[test]
337 fn spaces_patch_matches_tab_file_matches_patch_parser_test_124_147() {
338 let file = "function foo() {\n\treturn 42;\n}\n";
339 let chunks = [chunk(&[" return 42;"], &[" return 43;"])];
340
341 assert_eq!(
342 apply_update_chunks(file, "src/foo.ts", &chunks).unwrap(),
343 "function foo() {\n return 43;\n}\n"
344 );
345 }
346
347 #[test]
348 fn tab_patch_matches_spaces_file_matches_patch_parser_test_149_162() {
349 let file = "function foo() {\n return 42;\n}\n";
350 let chunks = [chunk(&["\treturn 42;"], &["\treturn 43;"])];
351
352 assert_eq!(
353 apply_update_chunks(file, "src/foo.ts", &chunks).unwrap(),
354 "function foo() {\n\treturn 43;\n}\n"
355 );
356 }
357
358 #[test]
359 fn closest_match_diagnostic_matches_patch_parser_test_164_195() {
360 let file =
361 "function foo() {\n const x = 1;\n const y = 2;\n const z = 3;\n return x + y + z;\n}\n";
362 let chunks = [chunk(
363 &[" const x = 1;", " const y = 2;", " const Q = 99;"],
364 &[" const x = 1;", " const y = 2;", " const Q = 100;"],
365 )];
366
367 let message = assert_apply_error(file, "src/foo.ts", &chunks);
368 assert!(message.contains("Closest match starts at line 2"));
369 assert!(message.contains("2 of 3 lines matched"));
370 assert!(message.contains("First divergence at line 4"));
371 assert!(message.contains("expected: \" const Q = 99;\""));
372 assert!(message.contains("actual: \" const z = 3;\""));
373 }
374
375 #[test]
376 fn tried_tiers_diagnostic_matches_patch_parser_test_197_221() {
377 let chunks = [chunk(&["completely unrelated line"], &["replacement"])];
378 let message = assert_apply_error("alpha\nbeta\ngamma\n", "src/foo.ts", &chunks);
379
380 assert!(message.contains("Tried match tiers:"));
381 assert!(message.contains("exact"));
382 assert!(message.contains("trim"));
383 assert!(message.contains("indent"));
384 assert!(message.contains("unicode"));
385 }
386
387 #[test]
388 fn reflow_one_line_to_three_line_split_matches_patch_parser_test_225_240() {
389 let original =
390 "function demo() {\n const value = alpha +\n beta +\n gamma;\n return value;\n}\n";
391 let chunks = [chunk(
392 &[" const value = alpha + beta + gamma;"],
393 &[" const value = alpha + beta + delta;"],
394 )];
395
396 assert_eq!(
397 apply_update_chunks(original, "src/demo.ts", &chunks).unwrap(),
398 "function demo() {\n const value = alpha + beta + delta;\n return value;\n}\n"
399 );
400 }
401
402 #[test]
403 fn reflow_three_line_to_one_line_join_matches_patch_parser_test_242_254() {
404 let original = "function demo() {\n const value = alpha + beta + gamma;\n}\n";
405 let chunks = [chunk(
406 &[" const value = alpha +", " beta +", " gamma;"],
407 &[" const value = alpha +", " beta +", " delta;"],
408 )];
409
410 assert_eq!(
411 apply_update_chunks(original, "src/demo.ts", &chunks).unwrap(),
412 "function demo() {\n const value = alpha +\n beta +\n delta;\n}\n"
413 );
414 }
415
416 #[test]
417 fn ambiguous_reflow_rejects_matches_patch_parser_test_256_269() {
418 let original =
419 "const value = alpha +\n beta +\n gamma;\n\nconst value = alpha +\n beta +\n gamma;\n";
420 let chunks = [chunk(
421 &["const value = alpha + beta + gamma;"],
422 &["const value = alpha + beta + delta;"],
423 )];
424
425 assert!(assert_apply_error(original, "src/demo.ts", &chunks)
426 .contains("Failed to find expected lines in src/demo.ts"));
427 }
428
429 #[test]
430 fn reflow_near_miss_rejects_matches_patch_parser_test_271_282() {
431 let chunks = [chunk(
432 &["const value = alpha + beta + delta;"],
433 &["const value = alpha + beta + epsilon;"],
434 )];
435
436 assert!(assert_apply_error(
437 "const value = alpha +\n beta +\n gamma;\n",
438 "src/demo.ts",
439 &chunks,
440 )
441 .contains("Failed to find expected lines in src/demo.ts"));
442 }
443
444 #[test]
445 fn contiguous_match_wins_before_reflow_matches_patch_parser_test_284_299() {
446 let original =
447 "const value = alpha +\n beta +\n gamma;\nconst value = alpha + beta + gamma;\n";
448 let chunks = [chunk(
449 &["const value = alpha + beta + gamma;"],
450 &["const value = alpha + beta + delta;"],
451 )];
452
453 assert_eq!(
454 apply_update_chunks(original, "src/demo.ts", &chunks).unwrap(),
455 "const value = alpha +\n beta +\n gamma;\nconst value = alpha + beta + delta;\n"
456 );
457 }
458
459 #[test]
460 fn strict_tiers_stay_ahead_of_reflow_matches_patch_parser_test_301_342() {
461 let cases = [
462 (
463 "src/rstrip.ts",
464 "const value = alpha +\n beta +\n gamma;\nconst value = alpha + beta + gamma; \n",
465 vec!["const value = alpha + beta + gamma;"],
466 "const value = alpha +\n beta +\n gamma;\nconst value = alpha + beta + delta;\n",
467 ),
468 (
469 "src/trim.ts",
470 "const value = alpha +\n beta +\n gamma;\n const value = alpha + beta + gamma;\n",
471 vec!["const value = alpha + beta + gamma;"],
472 "const value = alpha +\n beta +\n gamma;\nconst value = alpha + beta + delta;\n",
473 ),
474 (
475 "src/unicode.ts",
476 "const label =\n \"alpha\";\nconst label = “alpha”;\n",
477 vec!["const label = \"alpha\";"],
478 "const label =\n \"alpha\";\nconst value = alpha + beta + delta;\n",
479 ),
480 ];
481
482 for (file_path, original, old_lines, expected) in cases {
483 let chunks = [chunk(&old_lines, &["const value = alpha + beta + delta;"])];
484 assert_eq!(
485 apply_update_chunks(original, file_path, &chunks).unwrap(),
486 expected
487 );
488 }
489 }
490
491 #[test]
492 fn pure_insertion_with_context_matches_patch_parser_test_345_367() {
493 let original = "function foo() {\n return 1;\n}\n\nfunction bar() {\n return 2;\n}\n";
494 let chunks = [context_chunk("function foo() {", &[], &[" const x = 42;"])];
495
496 let result = apply_update_chunks(original, "src/example.ts", &chunks).unwrap();
497 assert_eq!(
498 result,
499 "function foo() {\n const x = 42;\n return 1;\n}\n\nfunction bar() {\n return 2;\n}\n"
500 );
501 assert!(!result.contains(" return 2;\n const x = 42;"));
502 }
503
504 #[test]
505 fn pure_insertion_without_context_matches_patch_parser_test_369_380() {
506 let original = "alpha\nbeta\n";
507 let chunks = [chunk(&[], &["gamma"])];
508
509 assert_eq!(
510 apply_update_chunks(original, "src/example.ts", &chunks).unwrap(),
511 "alpha\nbeta\ngamma\n"
512 );
513 }
514
515 #[test]
516 fn pure_insertion_does_not_short_circuit_matches_patch_parser_test_382_397() {
517 let original = "import a;\nimport b;\n\nconst x = 1;\n";
518 let chunks = [context_chunk("import a;", &[], &["import inserted;"])];
519
520 assert_eq!(
521 apply_update_chunks(original, "src/example.ts", &chunks).unwrap(),
522 "import a;\nimport inserted;\nimport b;\n\nconst x = 1;\n"
523 );
524 }
525
526 #[test]
527 fn eof_hunk_applies_final_occurrence_matches_patch_parser_test_400_414() {
528 let original = "header\nmarker\nold\nmiddle\nmarker\nold\n";
529 let chunks = [eof_chunk(&["marker", "old"], &["marker", "new"])];
530
531 assert_eq!(
532 apply_update_chunks(original, "src/eof.ts", &chunks).unwrap(),
533 "header\nmarker\nold\nmiddle\nmarker\nnew\n"
534 );
535 }
536
537 #[test]
538 fn eof_hunk_rejects_forward_scan_matches_patch_parser_test_416_429() {
539 let original = "header\nmarker\nold\nmiddle\nmarker\nchanged\n";
540 let chunks = [eof_chunk(&["marker", "old"], &["marker", "new"])];
541
542 assert!(assert_apply_error(original, "src/eof.ts", &chunks)
543 .contains("Failed to find expected lines in src/eof.ts"));
544 }
545
546 #[test]
547 fn trailing_empty_line_retry_matches_patch_parser_source_514_519() {
548 let chunks = [chunk(&["alpha", ""], &["beta", ""])];
549
550 assert_eq!(
551 apply_update_chunks("alpha\n", "src/trailing.ts", &chunks).unwrap(),
552 "beta\n"
553 );
554 }
555}