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 find_block_range(source: &str, block_name: &str) -> Result<BlockRange, TextPatchError> {
160 let Some((block_start, open_brace)) = find_named_block_start(source, block_name) else {
161 return Err(TextPatchError::BlockNotFound {
162 block_name: block_name.to_string(),
163 });
164 };
165
166 let mut depth = 0usize;
167 for (offset, ch) in source[open_brace..].char_indices() {
168 match ch {
169 '{' => depth += 1,
170 '}' => {
171 depth -= 1;
172 if depth == 0 {
173 let end = open_brace + offset + ch.len_utf8();
174 return Ok(BlockRange {
175 start: block_start,
176 content_start: open_brace + 1,
177 end,
178 });
179 }
180 }
181 _ => {}
182 }
183 }
184
185 Err(TextPatchError::UnclosedBlock {
186 block_name: block_name.to_string(),
187 })
188}
189
190pub fn replace_block(
191 source: &str,
192 block_name: &str,
193 replacement: &str,
194) -> Result<TextPatch, TextPatchError> {
195 let range = find_block_range(source, block_name)?;
196 TextPatch::replace(range.content_start, range.end - 1, replacement)
197}
198
199pub fn merge_known_entries(
200 source: &str,
201 block_name: &str,
202 entries: &[KnownEntry<'_>],
203) -> Result<TextPatch, TextPatchError> {
204 let range = find_block_range(source, block_name)?;
205 let block_content = &source[range.content_start..range.end - 1];
206
207 for (index, entry) in entries.iter().enumerate() {
208 if entries[..index]
209 .iter()
210 .any(|earlier| earlier.key == entry.key)
211 {
212 return Err(TextPatchError::AmbiguousEntry {
213 block_name: block_name.to_string(),
214 key: entry.key.to_string(),
215 });
216 }
217 }
218
219 let segments = split_top_level_entries(block_content);
220 for entry in entries {
221 let matches = segments
222 .iter()
223 .filter(|segment| identify_entry_key(segment) == Some(entry.key))
224 .count();
225 if matches > 1 {
226 return Err(TextPatchError::AmbiguousEntry {
227 block_name: block_name.to_string(),
228 key: entry.key.to_string(),
229 });
230 }
231 }
232
233 let mut merged: Vec<String> = Vec::with_capacity(segments.len() + entries.len());
234 let mut seen: Vec<&str> = Vec::with_capacity(entries.len());
235
236 for segment in &segments {
237 if let Some(key) = identify_entry_key(segment) {
238 if let Some(entry) = entries.iter().find(|candidate| candidate.key == key) {
239 if !seen.contains(&key) {
240 merged.push(entry.replacement.to_string());
241 seen.push(key);
242 continue;
243 }
244 }
245 }
246 merged.push((*segment).to_string());
247 }
248
249 let mut merged = trim_trailing_blank_segments(merged);
250 merged = compact_blank_segment_runs(merged);
251 for entry in entries {
252 if seen.contains(&entry.key) {
253 continue;
254 }
255 merged.push(entry.replacement.to_string());
256 }
257
258 let replacement = if merged.is_empty() {
259 String::new()
260 } else {
261 let mut text = merged.concat();
262 if !text.starts_with('\n') {
263 text.insert(0, '\n');
264 }
265 if !text.ends_with('\n') {
266 text.push('\n');
267 }
268 text
269 };
270 TextPatch::replace(range.content_start, range.end - 1, replacement)
271}
272
273#[derive(Clone, Copy)]
274struct SortedPatch<'a> {
275 index: usize,
276 patch: &'a TextPatch,
277}
278
279fn sorted_patches(patches: &[TextPatch]) -> Vec<SortedPatch<'_>> {
280 let mut sorted: Vec<_> = patches
281 .iter()
282 .enumerate()
283 .map(|(index, patch)| SortedPatch { index, patch })
284 .collect();
285 sorted.sort_by(|left, right| compare_for_validation(*left, *right));
286 sorted
287}
288
289fn compare_for_validation(left: SortedPatch<'_>, right: SortedPatch<'_>) -> Ordering {
290 left.patch
291 .start
292 .cmp(&right.patch.start)
293 .then_with(|| left.patch.is_insert().cmp(&right.patch.is_insert()))
294 .then_with(|| left.patch.end.cmp(&right.patch.end))
295 .then_with(|| left.index.cmp(&right.index))
296}
297
298fn validate_patch_bounds(source: &str, patch: &TextPatch) -> Result<(), TextPatchError> {
299 let len = source.len();
300 if patch.start > len {
301 return Err(TextPatchError::OffsetOutOfBounds {
302 offset: patch.start,
303 len,
304 });
305 }
306 if patch.end > len {
307 return Err(TextPatchError::OffsetOutOfBounds {
308 offset: patch.end,
309 len,
310 });
311 }
312 if !source.is_char_boundary(patch.start) {
313 return Err(TextPatchError::InvalidUtf8Boundary {
314 offset: patch.start,
315 });
316 }
317 if !source.is_char_boundary(patch.end) {
318 return Err(TextPatchError::InvalidUtf8Boundary { offset: patch.end });
319 }
320 Ok(())
321}
322
323fn find_named_block_start(source: &str, block_name: &str) -> Option<(usize, usize)> {
324 let mut search_from = 0usize;
325 while search_from <= source.len() {
326 let offset = source[search_from..].find(block_name)?;
327 let name_start = search_from + offset;
328 let name_end = name_start + block_name.len();
329 if !is_identifier_boundary(source, name_start, name_end) {
330 search_from = name_end;
331 continue;
332 }
333
334 let mut cursor = name_end;
335 while let Some(ch) = source[cursor..].chars().next() {
336 if ch.is_whitespace() {
337 cursor += ch.len_utf8();
338 continue;
339 }
340 if ch == '{' {
341 return Some((name_start, cursor));
342 }
343 break;
344 }
345 search_from = name_end;
346 }
347 None
348}
349
350fn is_identifier_boundary(source: &str, start: usize, end: usize) -> bool {
351 let previous_ok = if start == 0 {
352 true
353 } else {
354 source[..start]
355 .chars()
356 .next_back()
357 .map(|ch| !is_identifier_char(ch))
358 .unwrap_or(true)
359 };
360 let next_ok = if end == source.len() {
361 true
362 } else {
363 source[end..]
364 .chars()
365 .next()
366 .map(|ch| !is_identifier_char(ch))
367 .unwrap_or(true)
368 };
369 previous_ok && next_ok
370}
371
372fn split_top_level_entries(source: &str) -> Vec<&str> {
373 let mut segments = Vec::new();
374 let mut depth = 0usize;
375 let mut segment_start = 0usize;
376
377 for (index, ch) in source.char_indices() {
378 match ch {
379 '{' => depth += 1,
380 '}' => depth = depth.saturating_sub(1),
381 '\n' if depth == 0 => {
382 segments.push(&source[segment_start..index + 1]);
383 segment_start = index + 1;
384 }
385 _ => {}
386 }
387 }
388
389 if segment_start < source.len() {
390 segments.push(&source[segment_start..]);
391 }
392
393 segments
394}
395
396fn identify_entry_key(entry: &str) -> Option<&str> {
397 let trimmed = entry.trim_start();
398 if trimmed.is_empty() {
399 return None;
400 }
401
402 let end = trimmed
403 .char_indices()
404 .find_map(|(index, ch)| (!is_identifier_char(ch)).then_some(index))
405 .unwrap_or(trimmed.len());
406 (end > 0).then_some(&trimmed[..end])
407}
408
409fn is_identifier_char(ch: char) -> bool {
410 ch.is_ascii_alphanumeric() || ch == '_' || ch == '-'
411}
412
413fn trim_trailing_blank_segments(mut segments: Vec<String>) -> Vec<String> {
414 while segments
415 .last()
416 .is_some_and(|segment| segment.trim().is_empty())
417 {
418 segments.pop();
419 }
420 segments
421}
422
423fn compact_blank_segment_runs(segments: Vec<String>) -> Vec<String> {
424 let mut compacted = Vec::with_capacity(segments.len());
425 let mut previous_blank = false;
426 for segment in segments {
427 let is_blank = segment.trim().is_empty();
428 if is_blank && previous_blank {
429 continue;
430 }
431 previous_blank = is_blank;
432 compacted.push(segment);
433 }
434 compacted
435}
436
437impl TextPatch {
438 fn is_insert(&self) -> bool {
439 self.start == self.end
440 }
441}
442
443#[cfg(test)]
444mod tests {
445 use super::{
446 apply_patch, apply_patches, find_block_range, merge_known_entries, replace_block,
447 validate_patches, BlockRange, KnownEntry, PatchConflict, TextPatch, TextPatchError,
448 };
449
450 #[test]
451 fn apply_patch_replaces_single_range() {
452 let patch = TextPatch::replace(6, 11, "there").expect("valid patch");
453 let updated = apply_patch("hello world", &patch).expect("patch should apply");
454 assert_eq!(updated, "hello there");
455 }
456
457 #[test]
458 fn text_patch_rejects_reversed_range() {
459 let err = TextPatch::replace(4, 2, "x").expect_err("reversed range must fail");
460 assert_eq!(err, TextPatchError::InvalidRange { start: 4, end: 2 });
461 }
462
463 #[test]
464 fn apply_patch_rejects_non_utf8_boundary_offsets() {
465 let patch = TextPatch::replace(1, 3, "A").expect("range ordering is valid");
466 let err = apply_patch("あい", &patch).expect_err("middle of code point must fail");
467 assert_eq!(err, TextPatchError::InvalidUtf8Boundary { offset: 1 });
468 }
469
470 #[test]
471 fn apply_patches_uses_deterministic_original_offsets() {
472 let patches = vec![
473 TextPatch::replace(0, 1, "A").expect("valid patch"),
474 TextPatch::insert(3, "!"),
475 ];
476 let updated = apply_patches("abc", &patches).expect("patches should apply");
477 assert_eq!(updated, "Abc!");
478 }
479
480 #[test]
481 fn validate_patches_rejects_overlapping_ranges() {
482 let patches = vec![
483 TextPatch::replace(1, 3, "XX").expect("valid patch"),
484 TextPatch::replace(2, 4, "YY").expect("valid patch"),
485 ];
486 let err = validate_patches("abcdef", &patches).expect_err("overlap must fail");
487 assert_eq!(
488 err,
489 TextPatchError::Conflict(PatchConflict {
490 first_index: 0,
491 second_index: 1,
492 first_start: 1,
493 first_end: 3,
494 second_start: 2,
495 second_end: 4,
496 })
497 );
498 }
499
500 #[test]
501 fn validate_patches_allows_multiple_inserts_at_same_offset() {
502 let patches = vec![TextPatch::insert(1, "X"), TextPatch::insert(1, "Y")];
503 validate_patches("ab", &patches).expect("same-offset inserts should be allowed");
504 let updated = apply_patches("ab", &patches).expect("patches should apply");
505 assert_eq!(updated, "aXYb");
506 }
507
508 #[test]
509 fn validate_patches_allows_insert_at_range_end() {
510 let patches = vec![
511 TextPatch::replace(1, 3, "BC").expect("valid patch"),
512 TextPatch::insert(3, "!"),
513 ];
514 validate_patches("abcd", &patches).expect("insert at end boundary is allowed");
515 let updated = apply_patches("abcd", &patches).expect("patches should apply");
516 assert_eq!(updated, "aBC!d");
517 }
518
519 #[test]
520 fn validate_patches_rejects_insert_at_range_start() {
521 let patches = vec![
522 TextPatch::replace(1, 3, "BC").expect("valid patch"),
523 TextPatch::insert(1, "!"),
524 ];
525 let err =
526 validate_patches("abcd", &patches).expect_err("insert at range start must conflict");
527 assert_eq!(
528 err,
529 TextPatchError::Conflict(PatchConflict {
530 first_index: 0,
531 second_index: 1,
532 first_start: 1,
533 first_end: 3,
534 second_start: 1,
535 second_end: 1,
536 })
537 );
538 }
539
540 #[test]
541 fn find_block_range_returns_named_brace_block() {
542 let source = "settings {\n theme \"dark\"\n}\n";
543 let range = find_block_range(source, "settings").expect("settings block should exist");
544 assert_eq!(
545 range,
546 BlockRange {
547 start: 0,
548 content_start: 10,
549 end: source.len() - 1,
550 }
551 );
552 assert_eq!(
553 &source[range.content_start..range.end - 1],
554 "\n theme \"dark\"\n"
555 );
556 }
557
558 #[test]
559 fn replace_block_returns_patch_for_block_content() {
560 let source = "settings {\n theme \"dark\"\n}\n";
561 let patch = replace_block(source, "settings", "\n theme \"light\"\n")
562 .expect("replace should succeed");
563 let updated = apply_patch(source, &patch).expect("patch should apply");
564 assert_eq!(updated, "settings {\n theme \"light\"\n}\n");
565 }
566
567 #[test]
568 fn find_block_range_errors_when_block_is_missing() {
569 let err = find_block_range("root {\n}\n", "settings").expect_err("missing block must fail");
570 assert_eq!(
571 err,
572 TextPatchError::BlockNotFound {
573 block_name: "settings".to_string(),
574 }
575 );
576 }
577
578 #[test]
579 fn find_block_range_errors_when_block_is_unclosed() {
580 let err = find_block_range("settings {\n theme \"dark\"\n", "settings")
581 .expect_err("unclosed block must fail");
582 assert_eq!(
583 err,
584 TextPatchError::UnclosedBlock {
585 block_name: "settings".to_string(),
586 }
587 );
588 }
589
590 #[test]
591 fn merge_known_entries_replaces_existing_and_appends_missing_keys() {
592 let source = "settings {\n theme \"dark\"\n shell \"/bin/zsh\"\n extra 1\n}\n";
593 let entries = [
594 KnownEntry {
595 key: "theme",
596 replacement: " theme \"light\"\n",
597 },
598 KnownEntry {
599 key: "font",
600 replacement: " font {\n size 12\n }\n",
601 },
602 ];
603 let patch =
604 merge_known_entries(source, "settings", &entries).expect("merge should succeed");
605 let updated = apply_patch(source, &patch).expect("patch should apply");
606 assert_eq!(
607 updated,
608 "settings {\n theme \"light\"\n shell \"/bin/zsh\"\n extra 1\n font {\n size 12\n }\n}\n"
609 );
610 }
611
612 #[test]
613 fn merge_known_entries_rejects_ambiguous_known_key() {
614 let source = "settings {\n theme \"dark\"\n theme \"light\"\n}\n";
615 let entries = [KnownEntry {
616 key: "theme",
617 replacement: " theme \"paper\"\n",
618 }];
619 let err = merge_known_entries(source, "settings", &entries)
620 .expect_err("duplicate keys must fail");
621 assert_eq!(
622 err,
623 TextPatchError::AmbiguousEntry {
624 block_name: "settings".to_string(),
625 key: "theme".to_string(),
626 }
627 );
628 }
629}