1use core::cmp::Ordering;
2
3#[derive(Debug, Clone, PartialEq, Eq)]
4pub struct TextPatch {
5 start: usize,
6 end: usize,
7 replacement: String,
8}
9
10impl TextPatch {
11 pub fn new(
12 start: usize,
13 end: usize,
14 replacement: impl Into<String>,
15 ) -> Result<Self, TextPatchError> {
16 if start > end {
17 return Err(TextPatchError::InvalidRange { start, end });
18 }
19 Ok(Self {
20 start,
21 end,
22 replacement: replacement.into(),
23 })
24 }
25
26 pub fn insert(offset: usize, replacement: impl Into<String>) -> Self {
27 Self {
28 start: offset,
29 end: offset,
30 replacement: replacement.into(),
31 }
32 }
33
34 pub fn delete(start: usize, end: usize) -> Result<Self, TextPatchError> {
35 Self::new(start, end, "")
36 }
37
38 pub fn replace(
39 start: usize,
40 end: usize,
41 replacement: impl Into<String>,
42 ) -> Result<Self, TextPatchError> {
43 Self::new(start, end, replacement)
44 }
45
46 pub fn start(&self) -> usize {
47 self.start
48 }
49
50 pub fn end(&self) -> usize {
51 self.end
52 }
53
54 pub fn replacement(&self) -> &str {
55 &self.replacement
56 }
57}
58
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct PatchConflict {
61 pub first_index: usize,
62 pub second_index: usize,
63 pub first_start: usize,
64 pub first_end: usize,
65 pub second_start: usize,
66 pub second_end: usize,
67}
68
69#[derive(Debug, Clone, PartialEq, Eq)]
70pub enum TextPatchError {
71 InvalidRange { start: usize, end: usize },
72 OffsetOutOfBounds { offset: usize, len: usize },
73 InvalidUtf8Boundary { offset: usize },
74 Conflict(PatchConflict),
75 BlockNotFound { block_name: String },
76 UnclosedBlock { block_name: String },
77 AmbiguousEntry { block_name: String, key: String },
78}
79
80#[derive(Debug, Clone, Copy, PartialEq, Eq)]
81pub struct BlockRange {
82 pub start: usize,
83 pub content_start: usize,
84 pub end: usize,
85}
86
87#[derive(Debug, Clone, Copy, PartialEq, Eq)]
88pub struct KnownEntry<'a> {
89 pub key: &'a str,
90 pub replacement: &'a str,
91}
92
93pub fn validate_patches(source: &str, patches: &[TextPatch]) -> Result<(), TextPatchError> {
94 let sorted = sorted_patches(patches);
95 let mut previous_non_empty: Option<SortedPatch<'_>> = None;
96
97 for current in sorted {
98 validate_patch_bounds(source, current.patch)?;
99 if current.patch.start == current.patch.end {
100 if let Some(previous) = previous_non_empty {
101 if current.patch.start < previous.patch.end {
102 return Err(TextPatchError::Conflict(PatchConflict {
103 first_index: previous.index,
104 second_index: current.index,
105 first_start: previous.patch.start,
106 first_end: previous.patch.end,
107 second_start: current.patch.start,
108 second_end: current.patch.end,
109 }));
110 }
111 }
112 continue;
113 }
114
115 if let Some(previous) = previous_non_empty {
116 if current.patch.start < previous.patch.end {
117 return Err(TextPatchError::Conflict(PatchConflict {
118 first_index: previous.index,
119 second_index: current.index,
120 first_start: previous.patch.start,
121 first_end: previous.patch.end,
122 second_start: current.patch.start,
123 second_end: current.patch.end,
124 }));
125 }
126 }
127 previous_non_empty = Some(current);
128 }
129
130 Ok(())
131}
132
133pub fn apply_patch(source: &str, patch: &TextPatch) -> Result<String, TextPatchError> {
134 apply_patches(source, core::slice::from_ref(patch))
135}
136
137pub fn apply_patches(source: &str, patches: &[TextPatch]) -> Result<String, TextPatchError> {
138 validate_patches(source, patches)?;
139
140 let mut ordered = sorted_patches(patches);
141 ordered.sort_by(|left, right| {
142 left.patch
143 .start
144 .cmp(&right.patch.start)
145 .then_with(|| left.patch.end.cmp(&right.patch.end))
146 .then_with(|| left.index.cmp(&right.index))
147 });
148
149 let mut output = source.to_string();
150 for current in ordered.into_iter().rev() {
151 output.replace_range(
152 current.patch.start..current.patch.end,
153 current.patch.replacement(),
154 );
155 }
156 Ok(output)
157}
158
159pub fn inverse_patches(original_text: &str, patches: &[TextPatch]) -> Vec<TextPatch> {
162 let ordered = sorted_patches(patches);
163
164 let mut cumulative_offset = 0isize;
165 let mut inverse = Vec::with_capacity(ordered.len());
166
167 for sp in &ordered {
168 let patch = &sp.patch;
169 let replaced = original_text[patch.start..patch.end].to_string();
170 let inverse_start = patch
171 .start
172 .checked_add_signed(cumulative_offset)
173 .expect("validated patch offset should stay within bounds");
174 let inverse_end = inverse_start + patch.replacement.len();
175 let inverse_patch = TextPatch::new(inverse_start, inverse_end, replaced)
176 .expect("inverse patch range is derived from validated patches");
177
178 inverse.push(inverse_patch);
179 cumulative_offset += patch.replacement.len() as isize - (patch.end - patch.start) as isize;
180 }
181
182 inverse
183}
184
185pub fn find_block_range(source: &str, block_name: &str) -> Result<BlockRange, TextPatchError> {
186 let Some((block_start, open_brace)) = find_named_block_start(source, block_name) else {
187 return Err(TextPatchError::BlockNotFound {
188 block_name: block_name.to_string(),
189 });
190 };
191
192 let mut depth = 0usize;
193 for (offset, ch) in source[open_brace..].char_indices() {
194 match ch {
195 '{' => depth += 1,
196 '}' => {
197 depth -= 1;
198 if depth == 0 {
199 let end = open_brace + offset + ch.len_utf8();
200 return Ok(BlockRange {
201 start: block_start,
202 content_start: open_brace + 1,
203 end,
204 });
205 }
206 }
207 _ => {}
208 }
209 }
210
211 Err(TextPatchError::UnclosedBlock {
212 block_name: block_name.to_string(),
213 })
214}
215
216pub fn replace_block(
217 source: &str,
218 block_name: &str,
219 replacement: &str,
220) -> Result<TextPatch, TextPatchError> {
221 let range = find_block_range(source, block_name)?;
222 TextPatch::replace(range.content_start, range.end - 1, replacement)
223}
224
225pub fn merge_known_entries(
226 source: &str,
227 block_name: &str,
228 entries: &[KnownEntry<'_>],
229) -> Result<TextPatch, TextPatchError> {
230 let range = find_block_range(source, block_name)?;
231 let block_content = &source[range.content_start..range.end - 1];
232
233 for (index, entry) in entries.iter().enumerate() {
234 if entries[..index]
235 .iter()
236 .any(|earlier| earlier.key == entry.key)
237 {
238 return Err(TextPatchError::AmbiguousEntry {
239 block_name: block_name.to_string(),
240 key: entry.key.to_string(),
241 });
242 }
243 }
244
245 let segments = split_top_level_entries(block_content);
246 for entry in entries {
247 let matches = segments
248 .iter()
249 .filter(|segment| identify_entry_key(segment) == Some(entry.key))
250 .count();
251 if matches > 1 {
252 return Err(TextPatchError::AmbiguousEntry {
253 block_name: block_name.to_string(),
254 key: entry.key.to_string(),
255 });
256 }
257 }
258
259 let mut merged: Vec<String> = Vec::with_capacity(segments.len() + entries.len());
260 let mut seen: Vec<&str> = Vec::with_capacity(entries.len());
261
262 for segment in &segments {
263 if let Some(key) = identify_entry_key(segment) {
264 if let Some(entry) = entries.iter().find(|candidate| candidate.key == key) {
265 if !seen.contains(&key) {
266 merged.push(entry.replacement.to_string());
267 seen.push(key);
268 continue;
269 }
270 }
271 }
272 merged.push((*segment).to_string());
273 }
274
275 let mut merged = trim_trailing_blank_segments(merged);
276 merged = compact_blank_segment_runs(merged);
277 for entry in entries {
278 if seen.contains(&entry.key) {
279 continue;
280 }
281 merged.push(entry.replacement.to_string());
282 }
283
284 let replacement = if merged.is_empty() {
285 String::new()
286 } else {
287 let mut text = merged.concat();
288 if !text.starts_with('\n') {
289 text.insert(0, '\n');
290 }
291 if !text.ends_with('\n') {
292 text.push('\n');
293 }
294 text
295 };
296 TextPatch::replace(range.content_start, range.end - 1, replacement)
297}
298
299#[derive(Clone, Copy)]
300struct SortedPatch<'a> {
301 index: usize,
302 patch: &'a TextPatch,
303}
304
305fn sorted_patches(patches: &[TextPatch]) -> Vec<SortedPatch<'_>> {
306 let mut sorted: Vec<_> = patches
307 .iter()
308 .enumerate()
309 .map(|(index, patch)| SortedPatch { index, patch })
310 .collect();
311 sorted.sort_by(|left, right| compare_for_validation(*left, *right));
312 sorted
313}
314
315fn compare_for_validation(left: SortedPatch<'_>, right: SortedPatch<'_>) -> Ordering {
316 left.patch
317 .start
318 .cmp(&right.patch.start)
319 .then_with(|| left.patch.is_insert().cmp(&right.patch.is_insert()))
320 .then_with(|| left.patch.end.cmp(&right.patch.end))
321 .then_with(|| left.index.cmp(&right.index))
322}
323
324fn validate_patch_bounds(source: &str, patch: &TextPatch) -> Result<(), TextPatchError> {
325 let len = source.len();
326 if patch.start > len {
327 return Err(TextPatchError::OffsetOutOfBounds {
328 offset: patch.start,
329 len,
330 });
331 }
332 if patch.end > len {
333 return Err(TextPatchError::OffsetOutOfBounds {
334 offset: patch.end,
335 len,
336 });
337 }
338 if !source.is_char_boundary(patch.start) {
339 return Err(TextPatchError::InvalidUtf8Boundary {
340 offset: patch.start,
341 });
342 }
343 if !source.is_char_boundary(patch.end) {
344 return Err(TextPatchError::InvalidUtf8Boundary { offset: patch.end });
345 }
346 Ok(())
347}
348
349fn find_named_block_start(source: &str, block_name: &str) -> Option<(usize, usize)> {
350 let mut search_from = 0usize;
351 while search_from <= source.len() {
352 let offset = source[search_from..].find(block_name)?;
353 let name_start = search_from + offset;
354 let name_end = name_start + block_name.len();
355 if !is_identifier_boundary(source, name_start, name_end) {
356 search_from = name_end;
357 continue;
358 }
359
360 let mut cursor = name_end;
361 while let Some(ch) = source[cursor..].chars().next() {
362 if ch.is_whitespace() {
363 cursor += ch.len_utf8();
364 continue;
365 }
366 if ch == '{' {
367 return Some((name_start, cursor));
368 }
369 break;
370 }
371 search_from = name_end;
372 }
373 None
374}
375
376fn is_identifier_boundary(source: &str, start: usize, end: usize) -> bool {
377 let previous_ok = if start == 0 {
378 true
379 } else {
380 source[..start]
381 .chars()
382 .next_back()
383 .map(|ch| !is_identifier_char(ch))
384 .unwrap_or(true)
385 };
386 let next_ok = if end == source.len() {
387 true
388 } else {
389 source[end..]
390 .chars()
391 .next()
392 .map(|ch| !is_identifier_char(ch))
393 .unwrap_or(true)
394 };
395 previous_ok && next_ok
396}
397
398fn split_top_level_entries(source: &str) -> Vec<&str> {
399 let mut segments = Vec::new();
400 let mut depth = 0usize;
401 let mut segment_start = 0usize;
402
403 for (index, ch) in source.char_indices() {
404 match ch {
405 '{' => depth += 1,
406 '}' => depth = depth.saturating_sub(1),
407 '\n' if depth == 0 => {
408 segments.push(&source[segment_start..index + 1]);
409 segment_start = index + 1;
410 }
411 _ => {}
412 }
413 }
414
415 if segment_start < source.len() {
416 segments.push(&source[segment_start..]);
417 }
418
419 segments
420}
421
422fn identify_entry_key(entry: &str) -> Option<&str> {
423 let trimmed = entry.trim_start();
424 if trimmed.is_empty() {
425 return None;
426 }
427
428 let end = trimmed
429 .char_indices()
430 .find_map(|(index, ch)| (!is_identifier_char(ch)).then_some(index))
431 .unwrap_or(trimmed.len());
432 (end > 0).then_some(&trimmed[..end])
433}
434
435fn is_identifier_char(ch: char) -> bool {
436 ch.is_ascii_alphanumeric() || ch == '_' || ch == '-'
437}
438
439fn trim_trailing_blank_segments(mut segments: Vec<String>) -> Vec<String> {
440 while segments
441 .last()
442 .is_some_and(|segment| segment.trim().is_empty())
443 {
444 segments.pop();
445 }
446 segments
447}
448
449fn compact_blank_segment_runs(segments: Vec<String>) -> Vec<String> {
450 let mut compacted = Vec::with_capacity(segments.len());
451 let mut previous_blank = false;
452 for segment in segments {
453 let is_blank = segment.trim().is_empty();
454 if is_blank && previous_blank {
455 continue;
456 }
457 previous_blank = is_blank;
458 compacted.push(segment);
459 }
460 compacted
461}
462
463impl TextPatch {
464 fn is_insert(&self) -> bool {
465 self.start == self.end
466 }
467}
468
469#[cfg(test)]
470mod tests {
471 use super::{
472 apply_patch, apply_patches, find_block_range, inverse_patches, merge_known_entries,
473 replace_block, validate_patches, BlockRange, KnownEntry, PatchConflict, TextPatch,
474 TextPatchError,
475 };
476
477 #[test]
478 fn apply_patch_replaces_single_range() {
479 let patch = TextPatch::replace(6, 11, "there").expect("valid patch");
480 let updated = apply_patch("hello world", &patch).expect("patch should apply");
481 assert_eq!(updated, "hello there");
482 }
483
484 #[test]
485 fn text_patch_rejects_reversed_range() {
486 let err = TextPatch::replace(4, 2, "x").expect_err("reversed range must fail");
487 assert_eq!(err, TextPatchError::InvalidRange { start: 4, end: 2 });
488 }
489
490 #[test]
491 fn apply_patch_rejects_non_utf8_boundary_offsets() {
492 let patch = TextPatch::replace(1, 3, "A").expect("range ordering is valid");
493 let err = apply_patch("あい", &patch).expect_err("middle of code point must fail");
494 assert_eq!(err, TextPatchError::InvalidUtf8Boundary { offset: 1 });
495 }
496
497 #[test]
498 fn apply_patches_uses_deterministic_original_offsets() {
499 let patches = vec![
500 TextPatch::replace(0, 1, "A").expect("valid patch"),
501 TextPatch::insert(3, "!"),
502 ];
503 let updated = apply_patches("abc", &patches).expect("patches should apply");
504 assert_eq!(updated, "Abc!");
505 }
506
507 #[test]
508 fn validate_patches_rejects_overlapping_ranges() {
509 let patches = vec![
510 TextPatch::replace(1, 3, "XX").expect("valid patch"),
511 TextPatch::replace(2, 4, "YY").expect("valid patch"),
512 ];
513 let err = validate_patches("abcdef", &patches).expect_err("overlap must fail");
514 assert_eq!(
515 err,
516 TextPatchError::Conflict(PatchConflict {
517 first_index: 0,
518 second_index: 1,
519 first_start: 1,
520 first_end: 3,
521 second_start: 2,
522 second_end: 4,
523 })
524 );
525 }
526
527 #[test]
528 fn validate_patches_allows_multiple_inserts_at_same_offset() {
529 let patches = vec![TextPatch::insert(1, "X"), TextPatch::insert(1, "Y")];
530 validate_patches("ab", &patches).expect("same-offset inserts should be allowed");
531 let updated = apply_patches("ab", &patches).expect("patches should apply");
532 assert_eq!(updated, "aXYb");
533 }
534
535 #[test]
536 fn validate_patches_allows_insert_at_range_end() {
537 let patches = vec![
538 TextPatch::replace(1, 3, "BC").expect("valid patch"),
539 TextPatch::insert(3, "!"),
540 ];
541 validate_patches("abcd", &patches).expect("insert at end boundary is allowed");
542 let updated = apply_patches("abcd", &patches).expect("patches should apply");
543 assert_eq!(updated, "aBC!d");
544 }
545
546 #[test]
547 fn validate_patches_rejects_insert_at_range_start() {
548 let patches = vec![
549 TextPatch::replace(1, 3, "BC").expect("valid patch"),
550 TextPatch::insert(1, "!"),
551 ];
552 let err =
553 validate_patches("abcd", &patches).expect_err("insert at range start must conflict");
554 assert_eq!(
555 err,
556 TextPatchError::Conflict(PatchConflict {
557 first_index: 0,
558 second_index: 1,
559 first_start: 1,
560 first_end: 3,
561 second_start: 1,
562 second_end: 1,
563 })
564 );
565 }
566
567 #[test]
568 fn test_inverse_single_insert() {
569 let patches = vec![TextPatch::insert(3, "!")];
570 let inverse = inverse_patches("abc", &patches);
571 assert_eq!(
572 inverse,
573 vec![TextPatch::delete(3, 4).expect("valid delete")]
574 );
575 }
576
577 #[test]
578 fn test_inverse_single_delete() {
579 let patches = vec![TextPatch::delete(1, 3).expect("valid delete")];
580 let inverse = inverse_patches("abcd", &patches);
581 assert_eq!(inverse, vec![TextPatch::insert(1, "bc")]);
582 }
583
584 #[test]
585 fn test_inverse_single_replace() {
586 let patches = vec![TextPatch::replace(1, 4, "XYZ").expect("valid patch")];
587 let inverse = inverse_patches("abcde", &patches);
588 assert_eq!(
589 inverse,
590 vec![TextPatch::replace(1, 4, "bcd").expect("valid patch")]
591 );
592 }
593
594 #[test]
595 fn test_inverse_multiple_patches() {
596 let patches = vec![
597 TextPatch::replace(1, 3, "XYZ").expect("valid patch"),
598 TextPatch::insert(5, "!"),
599 TextPatch::delete(6, 8).expect("valid patch"),
600 ];
601 let inverse = inverse_patches("abcdefgh", &patches);
602 assert_eq!(
603 inverse,
604 vec![
605 TextPatch::replace(1, 4, "bc").expect("valid patch"),
606 TextPatch::delete(6, 7).expect("valid patch"),
607 TextPatch::insert(8, "gh"),
608 ]
609 );
610 }
611
612 #[test]
613 fn test_inverse_round_trip() {
614 let original = "abcdefghij";
615 let forward = vec![
616 TextPatch::replace(1, 3, "XYZ").expect("valid patch"),
617 TextPatch::insert(5, "!"),
618 TextPatch::delete(8, 10).expect("valid patch"),
619 ];
620 let modified = apply_patches(original, &forward).expect("forward patch should apply");
621 let inverse = inverse_patches(original, &forward);
622 let restored = apply_patches(&modified, &inverse).expect("inverse patch should apply");
623 assert_eq!(restored, original);
624 }
625
626 #[test]
627 fn find_block_range_returns_named_brace_block() {
628 let source = "settings {\n theme \"dark\"\n}\n";
629 let range = find_block_range(source, "settings").expect("settings block should exist");
630 assert_eq!(
631 range,
632 BlockRange {
633 start: 0,
634 content_start: 10,
635 end: source.len() - 1,
636 }
637 );
638 assert_eq!(
639 &source[range.content_start..range.end - 1],
640 "\n theme \"dark\"\n"
641 );
642 }
643
644 #[test]
645 fn replace_block_returns_patch_for_block_content() {
646 let source = "settings {\n theme \"dark\"\n}\n";
647 let patch = replace_block(source, "settings", "\n theme \"light\"\n")
648 .expect("replace should succeed");
649 let updated = apply_patch(source, &patch).expect("patch should apply");
650 assert_eq!(updated, "settings {\n theme \"light\"\n}\n");
651 }
652
653 #[test]
654 fn find_block_range_errors_when_block_is_missing() {
655 let err = find_block_range("root {\n}\n", "settings").expect_err("missing block must fail");
656 assert_eq!(
657 err,
658 TextPatchError::BlockNotFound {
659 block_name: "settings".to_string(),
660 }
661 );
662 }
663
664 #[test]
665 fn find_block_range_errors_when_block_is_unclosed() {
666 let err = find_block_range("settings {\n theme \"dark\"\n", "settings")
667 .expect_err("unclosed block must fail");
668 assert_eq!(
669 err,
670 TextPatchError::UnclosedBlock {
671 block_name: "settings".to_string(),
672 }
673 );
674 }
675
676 #[test]
677 fn merge_known_entries_replaces_existing_and_appends_missing_keys() {
678 let source = "settings {\n theme \"dark\"\n shell \"/bin/zsh\"\n extra 1\n}\n";
679 let entries = [
680 KnownEntry {
681 key: "theme",
682 replacement: " theme \"light\"\n",
683 },
684 KnownEntry {
685 key: "font",
686 replacement: " font {\n size 12\n }\n",
687 },
688 ];
689 let patch =
690 merge_known_entries(source, "settings", &entries).expect("merge should succeed");
691 let updated = apply_patch(source, &patch).expect("patch should apply");
692 assert_eq!(
693 updated,
694 "settings {\n theme \"light\"\n shell \"/bin/zsh\"\n extra 1\n font {\n size 12\n }\n}\n"
695 );
696 }
697
698 #[test]
699 fn merge_known_entries_rejects_ambiguous_known_key() {
700 let source = "settings {\n theme \"dark\"\n theme \"light\"\n}\n";
701 let entries = [KnownEntry {
702 key: "theme",
703 replacement: " theme \"paper\"\n",
704 }];
705 let err = merge_known_entries(source, "settings", &entries)
706 .expect_err("duplicate keys must fail");
707 assert_eq!(
708 err,
709 TextPatchError::AmbiguousEntry {
710 block_name: "settings".to_string(),
711 key: "theme".to_string(),
712 }
713 );
714 }
715}