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