Skip to main content

sound_law/
engine.rs

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/// A validated, executable sequence of sound laws.
9#[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    /// The number of ordered rules in this program.
20    pub fn rule_count(&self) -> usize {
21        self.rules.len()
22    }
23
24    /// Iterate over stable rule names in declaration order.
25    pub fn rule_names(&self) -> impl ExactSizeIterator<Item = &str> {
26        self.rules.iter().map(|rule| rule.name.as_str())
27    }
28
29    /// Compose two compiled programs, applying `self` before `next`.
30    ///
31    /// Stable rule names must remain unique so traces and named ranges are
32    /// unambiguous.
33    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    /// Apply every rule once, in declaration order.
47    pub fn apply(&self, input: &str) -> String {
48        apply_rules(&self.rules, input)
49    }
50
51    /// Apply every rule with a deterministic limit on matcher search work.
52    ///
53    /// One work unit is charged for each recursive pattern state and repeated
54    /// matcher state examined. This is an algorithmic guard, not wall-clock
55    /// timing, so a given program and input fail reproducibly.
56    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    /// Apply an end-exclusive range of rules by declaration index.
66    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    /// Apply the inclusive range from `first` through `last` by rule name.
78    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    /// Apply rules from the beginning through `last`, inclusively.
96    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    /// Apply rules from `first` through the end of the program.
102    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    /// Apply every rule while recording only the rules that changed the word.
108    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    /// Reapply the complete ordered program until it stops changing the word.
129    ///
130    /// Cycles are detected, and `max_passes` is a hard guard against programs
131    /// that keep producing novel forms forever.
132    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/// One changed intermediate form from [`Program::apply_with_trace`].
195#[derive(Debug, Clone, PartialEq, Eq)]
196pub struct TraceStep {
197    /// The declarative rule name.
198    pub rule: String,
199    /// The word immediately before this rule.
200    pub before: String,
201    /// The word immediately after this rule.
202    pub after: String,
203}
204
205/// Failure to reach a fixed point in [`Program::apply_until_stable`].
206#[derive(Debug, Clone, PartialEq, Eq)]
207pub enum IterationError {
208    /// A form already seen during this run appeared again.
209    Cycle {
210        /// The repeated form.
211        form: String,
212        /// The zero-based pass where the form first appeared.
213        first_seen: usize,
214        /// The pass where it appeared again.
215        repeated_at: usize,
216    },
217    /// The program was still changing after the requested number of passes.
218    Limit {
219        /// The configured pass limit.
220        max_passes: usize,
221        /// The last form produced before stopping.
222        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/// An invalid index or name passed to a partial-execution API.
251#[derive(Debug, Clone, PartialEq, Eq)]
252pub enum RuleRangeError {
253    /// No compiled rule has this name.
254    UnknownRule(String),
255    /// The named first rule occurs after the named last rule.
256    Reversed {
257        /// Requested first rule.
258        first: String,
259        /// Requested last rule.
260        last: String,
261    },
262    /// An index range was reversed or extended beyond the program.
263    OutOfBounds {
264        /// Inclusive start index.
265        start: usize,
266        /// Exclusive end index.
267        end: usize,
268        /// Number of compiled rules.
269        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/// Two compiled programs cannot be composed without ambiguous rule names.
296#[derive(Debug, Clone, PartialEq, Eq)]
297pub struct ProgramCompositionError {
298    duplicate_rule: String,
299}
300
301impl ProgramCompositionError {
302    /// The rule name present in both programs.
303    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/// Matcher search exceeded the caller's deterministic work budget.
321#[derive(Debug, Clone, PartialEq, Eq)]
322pub struct MatchLimitError {
323    max_steps: usize,
324    rule: String,
325}
326
327impl MatchLimitError {
328    /// The configured maximum number of matcher work units.
329    pub fn max_steps(&self) -> usize {
330        self.max_steps
331    }
332
333    /// The rule being evaluated when the budget was exhausted.
334    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    // Unlike consuming matches, an insertion has no natural "next byte".
457    // Enumerating the original boundaries exactly once gives it simultaneous
458    // semantics and prevents emitted text from matching this rule recursively.
459    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            // Nullable pieces are useful inside real patterns, but consuming
591            // rules must make progress. Pure insertion has a separate path.
592            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            // Quantified matchers must make progress. A one-shot empty
765            // backreference remains valid, but cannot make `*` loop forever.
766            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    // Greedy means greatest consumed span first. Count breaks ties for class
777    // inventories whose members admit more than one segmentation.
778    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}