1use std::collections::{HashMap, HashSet};
2use std::fmt;
3use std::ops::Range;
4
5use crate::compile::{Atom, CompiledRule, Matcher, Pattern, Quantifier, ReplacementPart};
6use crate::{Application, Direction};
7
8#[derive(Debug, Clone)]
10pub struct Program {
11 rules: Vec<CompiledRule>,
12}
13
14impl Program {
15 pub(crate) fn new(rules: Vec<CompiledRule>) -> Self {
16 Self { rules }
17 }
18
19 pub fn rule_count(&self) -> usize {
21 self.rules.len()
22 }
23
24 pub fn rule_names(&self) -> impl ExactSizeIterator<Item = &str> {
26 self.rules.iter().map(|rule| rule.name.as_str())
27 }
28
29 pub fn then(&self, next: &Program) -> Result<Program, ProgramCompositionError> {
34 let mut names: HashSet<&str> = self.rule_names().collect();
35 if let Some(duplicate) = next.rule_names().find(|name| !names.insert(name)) {
36 return Err(ProgramCompositionError {
37 duplicate_rule: duplicate.to_owned(),
38 });
39 }
40 let mut rules = Vec::with_capacity(self.rules.len() + next.rules.len());
41 rules.extend(self.rules.iter().cloned());
42 rules.extend(next.rules.iter().cloned());
43 Ok(Program::new(rules))
44 }
45
46 pub fn apply(&self, input: &str) -> String {
48 apply_rules(&self.rules, input)
49 }
50
51 pub fn apply_with_limit(
57 &self,
58 input: &str,
59 max_steps: usize,
60 ) -> Result<String, MatchLimitError> {
61 let mut budget = WorkBudget::limited(max_steps);
62 apply_rules_with_budget(&self.rules, input, &mut budget)
63 }
64
65 pub fn apply_range(&self, input: &str, range: Range<usize>) -> Result<String, RuleRangeError> {
67 if range.start > range.end || range.end > self.rules.len() {
68 return Err(RuleRangeError::OutOfBounds {
69 start: range.start,
70 end: range.end,
71 rule_count: self.rules.len(),
72 });
73 }
74 Ok(apply_rules(&self.rules[range], input))
75 }
76
77 pub fn apply_named_range(
79 &self,
80 input: &str,
81 first: &str,
82 last: &str,
83 ) -> Result<String, RuleRangeError> {
84 let start = self.rule_index(first)?;
85 let end = self.rule_index(last)?;
86 if start > end {
87 return Err(RuleRangeError::Reversed {
88 first: first.to_owned(),
89 last: last.to_owned(),
90 });
91 }
92 Ok(apply_rules(&self.rules[start..=end], input))
93 }
94
95 pub fn apply_through(&self, input: &str, last: &str) -> Result<String, RuleRangeError> {
97 let end = self.rule_index(last)?;
98 Ok(apply_rules(&self.rules[..=end], input))
99 }
100
101 pub fn apply_from(&self, input: &str, first: &str) -> Result<String, RuleRangeError> {
103 let start = self.rule_index(first)?;
104 Ok(apply_rules(&self.rules[start..], input))
105 }
106
107 pub fn apply_with_trace(&self, input: &str) -> (String, Vec<TraceStep>) {
109 let mut word = input.to_owned();
110 let mut trace = Vec::new();
111 let mut budget = WorkBudget::unlimited();
112
113 for rule in &self.rules {
114 let next = apply_rule(rule, &word, &mut budget);
115 if next != word {
116 trace.push(TraceStep {
117 rule: rule.name.clone(),
118 before: word,
119 after: next.clone(),
120 });
121 word = next;
122 }
123 }
124
125 (word, trace)
126 }
127
128 pub fn apply_until_stable(
133 &self,
134 input: &str,
135 max_passes: usize,
136 ) -> Result<String, IterationError> {
137 let mut seen = HashMap::new();
138 let mut word = input.to_owned();
139 seen.insert(word.clone(), 0usize);
140
141 for pass in 1..=max_passes {
142 let next = self.apply(&word);
143 if next == word {
144 return Ok(word);
145 }
146 if let Some(first_seen) = seen.insert(next.clone(), pass) {
147 return Err(IterationError::Cycle {
148 form: next,
149 first_seen,
150 repeated_at: pass,
151 });
152 }
153 word = next;
154 }
155
156 Err(IterationError::Limit {
157 max_passes,
158 last_form: word,
159 })
160 }
161
162 fn rule_index(&self, name: &str) -> Result<usize, RuleRangeError> {
163 self.rules
164 .iter()
165 .position(|rule| rule.name == name)
166 .ok_or_else(|| RuleRangeError::UnknownRule(name.to_owned()))
167 }
168}
169
170fn apply_rules(rules: &[CompiledRule], input: &str) -> String {
171 let mut budget = WorkBudget::unlimited();
172 apply_rules_with_budget(rules, input, &mut budget)
173 .expect("an unlimited matcher budget cannot be exhausted")
174}
175
176fn apply_rules_with_budget(
177 rules: &[CompiledRule],
178 input: &str,
179 budget: &mut WorkBudget,
180) -> Result<String, MatchLimitError> {
181 let mut word = input.to_owned();
182 for rule in rules {
183 word = apply_rule(rule, &word, budget);
184 if budget.exhausted {
185 return Err(MatchLimitError {
186 max_steps: budget.max_steps,
187 rule: rule.name.clone(),
188 });
189 }
190 }
191 Ok(word)
192}
193
194#[derive(Debug, Clone, PartialEq, Eq)]
196pub struct TraceStep {
197 pub rule: String,
199 pub before: String,
201 pub after: String,
203}
204
205#[derive(Debug, Clone, PartialEq, Eq)]
207pub enum IterationError {
208 Cycle {
210 form: String,
212 first_seen: usize,
214 repeated_at: usize,
216 },
217 Limit {
219 max_passes: usize,
221 last_form: String,
223 },
224}
225
226impl fmt::Display for IterationError {
227 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
228 match self {
229 Self::Cycle {
230 form,
231 first_seen,
232 repeated_at,
233 } => write!(
234 f,
235 "sound-law iteration cycled on `{form}` (passes {first_seen} and {repeated_at})"
236 ),
237 Self::Limit {
238 max_passes,
239 last_form,
240 } => write!(
241 f,
242 "sound-law iteration did not stabilize in {max_passes} passes; last form was `{last_form}`"
243 ),
244 }
245 }
246}
247
248impl std::error::Error for IterationError {}
249
250#[derive(Debug, Clone, PartialEq, Eq)]
252pub enum RuleRangeError {
253 UnknownRule(String),
255 Reversed {
257 first: String,
259 last: String,
261 },
262 OutOfBounds {
264 start: usize,
266 end: usize,
268 rule_count: usize,
270 },
271}
272
273impl fmt::Display for RuleRangeError {
274 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
275 match self {
276 Self::UnknownRule(rule) => write!(f, "unknown sound-law rule `{rule}`"),
277 Self::Reversed { first, last } => write!(
278 f,
279 "sound-law rule range is reversed: `{first}` occurs after `{last}`"
280 ),
281 Self::OutOfBounds {
282 start,
283 end,
284 rule_count,
285 } => write!(
286 f,
287 "sound-law rule range {start}..{end} is invalid for {rule_count} rules"
288 ),
289 }
290 }
291}
292
293impl std::error::Error for RuleRangeError {}
294
295#[derive(Debug, Clone, PartialEq, Eq)]
297pub struct ProgramCompositionError {
298 duplicate_rule: String,
299}
300
301impl ProgramCompositionError {
302 pub fn duplicate_rule(&self) -> &str {
304 &self.duplicate_rule
305 }
306}
307
308impl fmt::Display for ProgramCompositionError {
309 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
310 write!(
311 f,
312 "cannot compose sound-law programs with duplicate rule `{}`",
313 self.duplicate_rule
314 )
315 }
316}
317
318impl std::error::Error for ProgramCompositionError {}
319
320#[derive(Debug, Clone, PartialEq, Eq)]
322pub struct MatchLimitError {
323 max_steps: usize,
324 rule: String,
325}
326
327impl MatchLimitError {
328 pub fn max_steps(&self) -> usize {
330 self.max_steps
331 }
332
333 pub fn rule(&self) -> &str {
335 &self.rule
336 }
337}
338
339impl fmt::Display for MatchLimitError {
340 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
341 write!(
342 f,
343 "sound law `{}` exceeded its matcher work limit of {} steps",
344 self.rule, self.max_steps
345 )
346 }
347}
348
349impl std::error::Error for MatchLimitError {}
350
351#[derive(Debug)]
352struct WorkBudget {
353 remaining: Option<usize>,
354 max_steps: usize,
355 exhausted: bool,
356}
357
358impl WorkBudget {
359 fn unlimited() -> Self {
360 Self {
361 remaining: None,
362 max_steps: usize::MAX,
363 exhausted: false,
364 }
365 }
366
367 fn limited(max_steps: usize) -> Self {
368 Self {
369 remaining: Some(max_steps),
370 max_steps,
371 exhausted: false,
372 }
373 }
374
375 fn spend(&mut self) -> bool {
376 match self.remaining {
377 None => true,
378 Some(0) => {
379 self.exhausted = true;
380 false
381 }
382 Some(remaining) => {
383 self.remaining = Some(remaining - 1);
384 true
385 }
386 }
387 }
388}
389
390#[derive(Debug, Clone, Copy, PartialEq, Eq)]
391struct Span {
392 start: usize,
393 end: usize,
394}
395
396#[derive(Debug, Clone)]
397struct MatchState {
398 position: usize,
399 captures: Vec<Option<Span>>,
400}
401
402#[derive(Debug, Clone)]
403struct FoundMatch {
404 start: usize,
405 end: usize,
406 captures: Vec<Option<Span>>,
407}
408
409fn apply_rule(rule: &CompiledRule, input: &str, budget: &mut WorkBudget) -> String {
410 if rule.target.atoms.is_empty() {
411 return apply_insertion_rule(rule, input, budget);
412 }
413
414 let matches = select_matches(rule, input, budget);
415 if matches.is_empty() {
416 return input.to_owned();
417 }
418
419 let mut output = String::with_capacity(input.len());
420 let mut cursor = 0;
421 for found in matches {
422 output.push_str(&input[cursor..found.start]);
423 render_replacement(rule, input, &found.captures, &mut output);
424 cursor = found.end;
425 }
426 output.push_str(&input[cursor..]);
427 output
428}
429
430fn apply_insertion_rule(rule: &CompiledRule, input: &str, budget: &mut WorkBudget) -> String {
431 let mut insertions = Vec::new();
432 let mut boundaries = boundaries_from(input, 0);
433 if rule.direction == Direction::RightToLeft {
434 boundaries.reverse();
435 }
436 for boundary in boundaries {
437 if budget.exhausted {
438 break;
439 }
440 if let Some(captures) = insertion_captures(rule, input, boundary, budget) {
441 insertions.push((boundary, captures));
442 if rule.application == Application::Once {
443 break;
444 }
445 }
446 }
447 if insertions.is_empty() {
448 return input.to_owned();
449 }
450 insertions.sort_by_key(|(boundary, _)| *boundary);
451
452 let mut output = String::with_capacity(input.len());
453 let mut cursor = 0;
454 let mut changed = false;
455
456 for (boundary, captures) in insertions {
460 output.push_str(&input[cursor..boundary]);
461 let before_replacement = output.len();
462 render_replacement(rule, input, &captures, &mut output);
463 changed |= output.len() != before_replacement;
464 cursor = boundary;
465 }
466
467 if !changed {
468 return input.to_owned();
469 }
470 output.push_str(&input[cursor..]);
471 output
472}
473
474fn insertion_captures(
475 rule: &CompiledRule,
476 input: &str,
477 boundary: usize,
478 budget: &mut WorkBudget,
479) -> Option<Vec<Option<Span>>> {
480 if rule.target.anchored_at_start && boundary != 0 {
481 return None;
482 }
483 if rule.target.anchored_at_end && boundary != input.len() {
484 return None;
485 }
486
487 let empty_captures = vec![None; rule.capture_count];
488 for left_state in left_context_matches(&rule.left, input, boundary, &empty_captures, budget) {
489 for right_state in
490 match_pattern_from(&rule.right, input, boundary, &left_state.captures, budget)
491 {
492 if !is_excluded(
493 rule,
494 input,
495 boundary,
496 boundary,
497 &right_state.captures,
498 budget,
499 ) {
500 return Some(right_state.captures);
501 }
502 }
503 }
504 None
505}
506
507fn select_matches(rule: &CompiledRule, input: &str, budget: &mut WorkBudget) -> Vec<FoundMatch> {
508 let mut selected = Vec::new();
509 match rule.direction {
510 Direction::LeftToRight => {
511 let mut cursor = 0;
512 while let Some(found) = find_next_match(rule, input, cursor, budget) {
513 cursor = found.end;
514 selected.push(found);
515 if rule.application == Application::Once {
516 break;
517 }
518 }
519 }
520 Direction::RightToLeft => {
521 let mut edge = input.len();
522 while let Some(found) = find_previous_match(rule, input, edge, budget) {
523 edge = found.start;
524 selected.push(found);
525 if rule.application == Application::Once {
526 break;
527 }
528 }
529 selected.sort_by_key(|found| found.start);
530 }
531 }
532 selected
533}
534
535fn find_next_match(
536 rule: &CompiledRule,
537 input: &str,
538 search_from: usize,
539 budget: &mut WorkBudget,
540) -> Option<FoundMatch> {
541 for start in boundaries_from(input, search_from) {
542 if budget.exhausted {
543 break;
544 }
545 if rule.target.anchored_at_start && start != 0 {
546 break;
547 }
548 if let Some(found) = match_at(rule, input, start, None, budget) {
549 return Some(found);
550 }
551 }
552 None
553}
554
555fn find_previous_match(
556 rule: &CompiledRule,
557 input: &str,
558 through: usize,
559 budget: &mut WorkBudget,
560) -> Option<FoundMatch> {
561 for start in boundaries_through(input, through).into_iter().rev() {
562 if budget.exhausted {
563 break;
564 }
565 if rule.target.anchored_at_start && start != 0 {
566 continue;
567 }
568 if let Some(found) = match_at(rule, input, start, Some(through), budget) {
569 return Some(found);
570 }
571 }
572 None
573}
574
575fn match_at(
576 rule: &CompiledRule,
577 input: &str,
578 start: usize,
579 must_end_by: Option<usize>,
580 budget: &mut WorkBudget,
581) -> Option<FoundMatch> {
582 let empty_captures = vec![None; rule.capture_count];
583 for left_state in left_context_matches(&rule.left, input, start, &empty_captures, budget) {
584 if budget.exhausted {
585 break;
586 }
587 for target_state in
588 match_pattern_from(&rule.target, input, start, &left_state.captures, budget)
589 {
590 if target_state.position == start
593 || must_end_by.is_some_and(|edge| target_state.position > edge)
594 {
595 continue;
596 }
597 for right_state in match_pattern_from(
598 &rule.right,
599 input,
600 target_state.position,
601 &target_state.captures,
602 budget,
603 ) {
604 if !is_excluded(
605 rule,
606 input,
607 start,
608 target_state.position,
609 &right_state.captures,
610 budget,
611 ) {
612 return Some(FoundMatch {
613 start,
614 end: target_state.position,
615 captures: right_state.captures,
616 });
617 }
618 }
619 }
620 }
621 None
622}
623
624fn is_excluded(
625 rule: &CompiledRule,
626 input: &str,
627 target_start: usize,
628 target_end: usize,
629 captures: &[Option<Span>],
630 budget: &mut WorkBudget,
631) -> bool {
632 let (Some(left), Some(right)) = (&rule.excluded_left, &rule.excluded_right) else {
633 return false;
634 };
635
636 left_context_matches(left, input, target_start, captures, budget)
637 .into_iter()
638 .any(|left_state| {
639 !match_pattern_from(right, input, target_end, &left_state.captures, budget).is_empty()
640 })
641}
642
643fn left_context_matches(
644 pattern: &Pattern,
645 input: &str,
646 target_start: usize,
647 captures: &[Option<Span>],
648 budget: &mut WorkBudget,
649) -> Vec<MatchState> {
650 if pattern.atoms.is_empty() && !pattern.anchored_at_start && !pattern.anchored_at_end {
651 return vec![MatchState {
652 position: target_start,
653 captures: captures.to_vec(),
654 }];
655 }
656
657 let starts: Vec<usize> = if pattern.anchored_at_start {
658 vec![0]
659 } else {
660 boundaries_through(input, target_start)
661 };
662 let mut matches = Vec::new();
663 for start in starts {
664 if budget.exhausted {
665 break;
666 }
667 matches.extend(
668 match_pattern_from(pattern, input, start, captures, budget)
669 .into_iter()
670 .filter(|state| state.position == target_start),
671 );
672 }
673 matches
674}
675
676fn match_pattern_from(
677 pattern: &Pattern,
678 input: &str,
679 start: usize,
680 captures: &[Option<Span>],
681 budget: &mut WorkBudget,
682) -> Vec<MatchState> {
683 if pattern.anchored_at_start && start != 0 {
684 return Vec::new();
685 }
686 let mut matches = Vec::new();
687 match_atoms(pattern, 0, input, start, captures, &mut matches, budget);
688 matches
689}
690
691fn match_atoms(
692 pattern: &Pattern,
693 atom_index: usize,
694 input: &str,
695 position: usize,
696 captures: &[Option<Span>],
697 matches: &mut Vec<MatchState>,
698 budget: &mut WorkBudget,
699) {
700 if !budget.spend() {
701 return;
702 }
703 if atom_index == pattern.atoms.len() {
704 if !pattern.anchored_at_end || position == input.len() {
705 matches.push(MatchState {
706 position,
707 captures: captures.to_vec(),
708 });
709 }
710 return;
711 }
712
713 let atom = &pattern.atoms[atom_index];
714 for end in repetition_ends(atom, input, position, captures, budget) {
715 let mut next_captures = captures.to_vec();
716 if let Some(capture) = atom.capture {
717 next_captures[capture] = Some(Span {
718 start: position,
719 end,
720 });
721 }
722 match_atoms(
723 pattern,
724 atom_index + 1,
725 input,
726 end,
727 &next_captures,
728 matches,
729 budget,
730 );
731 }
732}
733
734fn repetition_ends(
735 atom: &Atom,
736 input: &str,
737 start: usize,
738 captures: &[Option<Span>],
739 budget: &mut WorkBudget,
740) -> Vec<usize> {
741 let (minimum, maximum) = match atom.quantifier {
742 Quantifier::One => (1, Some(1)),
743 Quantifier::Optional => (0, Some(1)),
744 Quantifier::ZeroOrMore => (0, None),
745 Quantifier::OneOrMore => (1, None),
746 };
747
748 let mut candidates = Vec::new();
749 let mut frontier = vec![(0usize, start)];
750 let mut visited = HashSet::from([(0usize, start)]);
751
752 while let Some((count, position)) = frontier.pop() {
753 if !budget.spend() {
754 break;
755 }
756 if count >= minimum && maximum.is_none_or(|limit| count <= limit) {
757 candidates.push((count, position));
758 }
759 if maximum.is_some_and(|limit| count >= limit) {
760 continue;
761 }
762
763 for end in unit_ends(&atom.matcher, input, position, captures) {
764 if end == position && maximum.is_none() {
767 continue;
768 }
769 let next = (count + 1, end);
770 if visited.insert(next) {
771 frontier.push(next);
772 }
773 }
774 }
775
776 candidates.sort_by(|(left_count, left_end), (right_count, right_end)| {
779 right_end
780 .cmp(left_end)
781 .then_with(|| right_count.cmp(left_count))
782 });
783 candidates.into_iter().map(|(_, end)| end).collect()
784}
785
786fn unit_ends(
787 matcher: &Matcher,
788 input: &str,
789 position: usize,
790 captures: &[Option<Span>],
791) -> Vec<usize> {
792 let rest = &input[position..];
793 match matcher {
794 Matcher::Literal(literal) => rest
795 .starts_with(literal)
796 .then_some(vec![position + literal.len()])
797 .unwrap_or_default(),
798 Matcher::Class(members) => members
799 .iter()
800 .filter(|member| rest.starts_with(member.as_str()))
801 .map(|member| position + member.len())
802 .collect(),
803 Matcher::NotClass(members) => {
804 if members
805 .iter()
806 .any(|member| rest.starts_with(member.as_str()))
807 {
808 Vec::new()
809 } else {
810 rest.chars()
811 .next()
812 .map(|ch| vec![position + ch.len_utf8()])
813 .unwrap_or_default()
814 }
815 }
816 Matcher::Any => rest
817 .chars()
818 .next()
819 .map(|ch| vec![position + ch.len_utf8()])
820 .unwrap_or_default(),
821 Matcher::WordBoundary => is_word_boundary(input, position)
822 .then_some(vec![position])
823 .unwrap_or_default(),
824 Matcher::Backreference(capture) => {
825 let Some(span) = captures[*capture] else {
826 return Vec::new();
827 };
828 let captured = &input[span.start..span.end];
829 rest.starts_with(captured)
830 .then_some(vec![position + captured.len()])
831 .unwrap_or_default()
832 }
833 }
834}
835
836fn is_word_boundary(input: &str, position: usize) -> bool {
837 let previous = input[..position].chars().next_back();
838 let next = input[position..].chars().next();
839 match (previous, next) {
840 (None, _) | (_, None) => true,
841 (Some(previous), Some(next)) => previous.is_whitespace() != next.is_whitespace(),
842 }
843}
844
845fn render_replacement(
846 rule: &CompiledRule,
847 input: &str,
848 captures: &[Option<Span>],
849 output: &mut String,
850) {
851 for part in &rule.replacement {
852 match part {
853 ReplacementPart::Literal(literal) => output.push_str(literal),
854 ReplacementPart::Capture(capture) => {
855 let span = captures[*capture]
856 .expect("compiled replacement captures are set by every successful match");
857 output.push_str(&input[span.start..span.end]);
858 }
859 ReplacementPart::MappedCapture { capture, entries } => {
860 let span = captures[*capture]
861 .expect("compiled replacement captures are set by every successful match");
862 let captured = &input[span.start..span.end];
863 let (_, mapped) = entries
864 .iter()
865 .find(|(source, _)| source == captured)
866 .expect("map coverage is checked while compiling the capture");
867 output.push_str(mapped);
868 }
869 }
870 }
871}
872
873fn boundaries_from(input: &str, from: usize) -> Vec<usize> {
874 input
875 .char_indices()
876 .map(|(index, _)| index)
877 .chain(std::iter::once(input.len()))
878 .filter(|index| *index >= from)
879 .collect()
880}
881
882fn boundaries_through(input: &str, through: usize) -> Vec<usize> {
883 input
884 .char_indices()
885 .map(|(index, _)| index)
886 .chain(std::iter::once(input.len()))
887 .take_while(|index| *index <= through)
888 .collect()
889}