use crate::api::Match;
use crate::bytesearch;
use crate::cursor;
use crate::cursor::{Backward, Direction, Forward};
use crate::exec;
use crate::indexing::{AsciiInput, ElementType, InputIndexer, Utf8Input};
use crate::insn::{CompiledRegex, Insn, LoopFields, StartPredicate};
use crate::matchers;
use crate::matchers::CharProperties;
use crate::position::PositionType;
use crate::scm;
use crate::scm::SingleCharMatcher;
use crate::types::{CaptureGroupID, GroupData, LoopData, IP, MAX_CAPTURE_GROUPS};
use crate::util::DebugCheckIndex;
use std::ops::Range;
#[derive(Clone, Debug)]
enum BacktrackInsn<Input: InputIndexer> {
Exhausted,
SetPosition { ip: IP, pos: Input::Position },
SetLoopData {
id: u32,
data: LoopData<Input::Position>,
},
SetCaptureGroup {
id: CaptureGroupID,
data: GroupData<Input::Position>,
},
EnterNonGreedyLoop {
ip: IP,
data: LoopData<Input::Position>,
},
GreedyLoop1Char {
continuation: IP,
min: Input::Position,
max: Input::Position,
},
NonGreedyLoop1Char {
continuation: IP,
min: Input::Position,
max: Input::Position,
},
}
#[derive(Debug, Default)]
struct State<Position: PositionType> {
loops: Vec<LoopData<Position>>,
groups: Vec<GroupData<Position>>,
}
#[derive(Debug)]
struct MatchAttempter<'a, Input: InputIndexer> {
re: &'a CompiledRegex,
bts: Vec<BacktrackInsn<Input>>,
s: State<Input::Position>,
}
impl<'a, Input: InputIndexer> MatchAttempter<'a, Input> {
fn new(re: &'a CompiledRegex, entry: Input::Position) -> Self {
Self {
re,
bts: vec![BacktrackInsn::Exhausted],
s: State {
loops: vec![LoopData::new(entry); re.loops as usize],
groups: vec![GroupData::new(); re.groups as usize],
},
}
}
#[inline(always)]
fn push_backtrack(&mut self, bt: BacktrackInsn<Input>) {
self.bts.push(bt)
}
#[inline(always)]
fn pop_backtrack(&mut self) {
debug_assert!(!self.bts.is_empty());
if cfg!(feature = "prohibit-unsafe") {
self.bts.pop();
} else {
unsafe { self.bts.set_len(self.bts.len() - 1) }
}
}
fn prepare_to_enter_loop(
bts: &mut Vec<BacktrackInsn<Input>>,
pos: Input::Position,
loop_fields: &LoopFields,
loop_data: &mut LoopData<Input::Position>,
) {
bts.push(BacktrackInsn::SetLoopData {
id: loop_fields.loop_id,
data: *loop_data,
});
loop_data.iters += 1;
loop_data.entry = pos;
}
fn run_loop(
&mut self,
loop_fields: &'a LoopFields,
pos: Input::Position,
ip: IP,
) -> Option<IP> {
let loop_data = &mut self.s.loops[loop_fields.loop_id as usize];
let iteration = loop_data.iters;
let do_taken = iteration < loop_fields.max_iters;
let do_not_taken = iteration >= loop_fields.min_iters;
let loop_taken_ip = ip + 1;
let loop_not_taken_ip = loop_fields.exit as IP;
if loop_data.entry == pos && iteration > loop_fields.min_iters {
return None;
}
match (do_taken, do_not_taken) {
(false, false) => {
None
}
(false, true) => {
Some(loop_not_taken_ip)
}
(true, false) => {
MatchAttempter::prepare_to_enter_loop(&mut self.bts, pos, loop_fields, loop_data);
Some(loop_taken_ip)
}
(true, true) if !loop_fields.greedy => {
loop_data.entry = pos;
self.bts.push(BacktrackInsn::EnterNonGreedyLoop {
ip,
data: *loop_data,
});
Some(loop_not_taken_ip)
}
(true, true) => {
debug_assert!(loop_fields.greedy, "Should be greedy");
self.bts.push(BacktrackInsn::SetPosition {
ip: loop_not_taken_ip,
pos,
});
MatchAttempter::prepare_to_enter_loop(&mut self.bts, pos, loop_fields, loop_data);
Some(loop_taken_ip)
}
}
}
#[inline(always)]
fn run_scm_loop_impl<Dir: Direction, Scm: SingleCharMatcher<Input, Dir>>(
input: &Input,
mut pos: Input::Position,
min: usize,
max: usize,
dir: Dir,
matcher: Scm,
) -> Option<(Input::Position, Input::Position)> {
debug_assert!(min <= max, "min should be <= max");
for _ in 0..min {
if !matcher.matches(input, dir, &mut pos) {
return None;
}
}
let min_pos = pos;
for _ in 0..(max - min) {
let saved = pos;
if !matcher.matches(input, dir, &mut pos) {
pos = saved;
break;
}
}
let max_pos = pos;
Some((min_pos, max_pos))
}
#[allow(clippy::too_many_arguments)]
fn run_scm_loop<Dir: Direction>(
&mut self,
input: &Input,
dir: Dir,
pos: &mut Input::Position,
min: usize,
max: usize,
ip: IP,
greedy: bool,
) -> Option<IP> {
let loop_res = match self.re.insns.iat(ip + 1) {
&Insn::Char(c) => {
let c = Input::Element::try_from(c)?;
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::Char { c })
}
&Insn::CharICase(c) => {
let c = Input::Element::try_from(c)?;
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::CharICase { c })
}
Insn::Bracket(bc) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::Bracket { bc })
}
Insn::AsciiBracket(bitmap) => Self::run_scm_loop_impl(
input,
*pos,
min,
max,
dir,
scm::MatchByteSet { bytes: bitmap },
),
Insn::MatchAny => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::MatchAny::new())
}
Insn::MatchAnyExceptLineTerminator => Self::run_scm_loop_impl(
input,
*pos,
min,
max,
dir,
scm::MatchAnyExceptLineTerminator::new(),
),
Insn::CharSet(chars) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::CharSet { chars })
}
&Insn::ByteSet2(bytes) => Self::run_scm_loop_impl(
input,
*pos,
min,
max,
dir,
scm::MatchByteArraySet { bytes },
),
&Insn::ByteSet3(bytes) => Self::run_scm_loop_impl(
input,
*pos,
min,
max,
dir,
scm::MatchByteArraySet { bytes },
),
&Insn::ByteSet4(bytes) => Self::run_scm_loop_impl(
input,
*pos,
min,
max,
dir,
scm::MatchByteArraySet { bytes },
),
Insn::ByteSeq1(bytes) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::MatchByteSeq { bytes })
}
Insn::ByteSeq2(bytes) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::MatchByteSeq { bytes })
}
Insn::ByteSeq3(bytes) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::MatchByteSeq { bytes })
}
Insn::ByteSeq4(bytes) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::MatchByteSeq { bytes })
}
Insn::ByteSeq5(bytes) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::MatchByteSeq { bytes })
}
Insn::ByteSeq6(bytes) => {
Self::run_scm_loop_impl(input, *pos, min, max, dir, scm::MatchByteSeq { bytes })
}
_ => {
unreachable!("Missing SCM: {:?}", self.re.insns.iat(ip + 1));
}
};
let (min_pos, max_pos) = loop_res?;
debug_assert!(
if Dir::FORWARD {
min_pos <= max_pos
} else {
min_pos >= max_pos
},
"min should be <= (>=) max if cursor is tracking forwards (backwards)"
);
let continuation = ip + 2;
if min_pos != max_pos {
let bti = if greedy {
BacktrackInsn::GreedyLoop1Char {
continuation,
min: min_pos,
max: max_pos,
}
} else {
BacktrackInsn::NonGreedyLoop1Char {
continuation,
min: min_pos,
max: max_pos,
}
};
self.bts.push(bti);
}
*pos = if greedy { max_pos } else { min_pos };
Some(continuation)
}
fn run_lookaround<Dir: Direction>(
&mut self,
input: &Input,
ip: IP,
pos: Input::Position,
start_group: CaptureGroupID,
end_group: CaptureGroupID,
negate: bool,
) -> bool {
let range = (start_group as usize)..(end_group as usize);
let saved_groups = self.s.groups.iat(range.clone()).to_vec();
let mut saved_bts = vec![BacktrackInsn::Exhausted];
std::mem::swap(&mut self.bts, &mut saved_bts);
let matched = self.try_at_pos(*input, ip, pos, Dir::new()).is_some();
std::mem::swap(&mut self.bts, &mut saved_bts);
if matched && !negate {
for (idx, cg) in saved_groups.iter().enumerate() {
debug_assert!(idx + (start_group as usize) < MAX_CAPTURE_GROUPS);
self.push_backtrack(BacktrackInsn::SetCaptureGroup {
id: (idx as CaptureGroupID) + start_group,
data: *cg,
});
}
} else {
self.s.groups.splice(range, saved_groups);
}
matched != negate
}
fn try_backtrack<Dir: Direction>(
&mut self,
input: &Input,
ip: &mut IP,
pos: &mut Input::Position,
_dir: Dir,
) -> bool {
loop {
debug_assert!(!self.bts.is_empty(), "Backtrack stack should not be empty");
let bt = match self.bts.last_mut() {
Some(bt) => bt,
None => rs_unreachable!("BT stack should never be empty"),
};
match bt {
BacktrackInsn::Exhausted => return false,
BacktrackInsn::SetPosition {
ip: saved_ip,
pos: saved_pos,
} => {
*ip = *saved_ip;
*pos = *saved_pos;
self.pop_backtrack();
return true;
}
BacktrackInsn::SetLoopData { id, data } => {
*self.s.loops.mat(*id as usize) = *data;
self.pop_backtrack();
}
BacktrackInsn::SetCaptureGroup { id, data } => {
*self.s.groups.mat(*id as usize) = *data;
self.pop_backtrack();
}
&mut BacktrackInsn::EnterNonGreedyLoop { ip: loop_ip, data } => {
self.pop_backtrack();
*ip = loop_ip + 1;
*pos = data.entry;
let loop_fields = match &self.re.insns.iat(loop_ip) {
Insn::EnterLoop(loop_fields) => loop_fields,
_ => rs_unreachable!("EnterNonGreedyLoop must point at a loop instruction"),
};
let loop_data = self.s.loops.mat(loop_fields.loop_id as usize);
*loop_data = data;
MatchAttempter::prepare_to_enter_loop(
&mut self.bts,
*pos,
loop_fields,
loop_data,
);
return true;
}
BacktrackInsn::GreedyLoop1Char {
continuation,
min,
max,
} => {
debug_assert!(
if Dir::FORWARD { max >= min } else { max <= min },
"max should be >= min (or <= if tracking backwards)"
);
if *max == *min {
self.bts.pop();
continue;
}
let newmax = if Dir::FORWARD {
input.next_left_pos(*max)
} else {
input.next_right_pos(*max)
};
if let Some(newmax) = newmax {
*pos = newmax;
*max = newmax;
} else {
rs_unreachable!("Should always be able to advance since min != max")
}
*ip = *continuation;
return true;
}
BacktrackInsn::NonGreedyLoop1Char {
continuation,
min,
max,
} => {
debug_assert!(
if Dir::FORWARD { max >= min } else { max <= min },
"max should be >= min (or <= if tracking backwards)"
);
if *max == *min {
self.bts.pop();
continue;
}
let newmin = if Dir::FORWARD {
input.next_right_pos(*min)
} else {
input.next_left_pos(*min)
};
if let Some(newmin) = newmin {
*pos = newmin;
*min = newmin;
} else {
rs_unreachable!("Should always be able to advance since min != max")
}
*ip = *continuation;
return true;
}
}
}
}
fn try_at_pos<Dir: Direction>(
&mut self,
inp: Input,
mut ip: IP,
mut pos: Input::Position,
dir: Dir,
) -> Option<Input::Position> {
debug_assert!(
self.bts.len() == 1,
"Should be only initial exhausted backtrack insn"
);
let input = &inp;
let re = self.re;
#[allow(clippy::never_loop)]
'nextinsn: loop {
'backtrack: loop {
macro_rules! next_or_bt {
($e:expr) => {
if $e {
ip += 1;
continue 'nextinsn;
} else {
break 'backtrack;
}
};
}
match re.insns.iat(ip) {
&Insn::Char(c) => {
let m = match Input::Element::try_from(c) {
Some(c) => scm::Char { c }.matches(input, dir, &mut pos),
None => false,
};
next_or_bt!(m);
}
Insn::CharSet(chars) => {
let m = scm::CharSet { chars }.matches(input, dir, &mut pos);
next_or_bt!(m);
}
&Insn::ByteSet2(bytes) => {
next_or_bt!(scm::MatchByteArraySet { bytes }.matches(input, dir, &mut pos))
}
&Insn::ByteSet3(bytes) => {
next_or_bt!(scm::MatchByteArraySet { bytes }.matches(input, dir, &mut pos))
}
&Insn::ByteSet4(bytes) => {
next_or_bt!(scm::MatchByteArraySet { bytes }.matches(input, dir, &mut pos))
}
Insn::ByteSeq1(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq2(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq3(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq4(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq5(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq6(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq7(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq8(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq9(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq10(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq11(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq12(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq13(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq14(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq15(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
Insn::ByteSeq16(v) => {
next_or_bt!(cursor::try_match_lit(input, dir, &mut pos, v))
}
&Insn::CharICase(c) => {
let m = match Input::Element::try_from(c) {
Some(c) => scm::CharICase { c }.matches(input, dir, &mut pos),
None => false,
};
next_or_bt!(m)
}
Insn::AsciiBracket(bitmap) => next_or_bt!(
scm::MatchByteSet { bytes: bitmap }.matches(input, dir, &mut pos)
),
Insn::Bracket(bc) => {
next_or_bt!(scm::Bracket { bc }.matches(input, dir, &mut pos))
}
Insn::MatchAny => {
next_or_bt!(scm::MatchAny::new().matches(input, dir, &mut pos))
}
Insn::MatchAnyExceptLineTerminator => next_or_bt!(
scm::MatchAnyExceptLineTerminator::new().matches(input, dir, &mut pos)
),
&Insn::WordBoundary { invert } => {
let prev_wordchar = input
.peek_left(pos)
.map_or(false, Input::CharProps::is_word_char);
let curr_wordchar = input
.peek_right(pos)
.map_or(false, Input::CharProps::is_word_char);
let is_boundary = prev_wordchar != curr_wordchar;
next_or_bt!(is_boundary != invert)
}
Insn::StartOfLine => {
let matches = match input.peek_left(pos) {
None => true,
Some(c)
if re.flags.multiline
&& Input::CharProps::is_line_terminator(c) =>
{
true
}
_ => false,
};
next_or_bt!(matches)
}
Insn::EndOfLine => {
let matches = match input.peek_right(pos) {
None => true, Some(c)
if re.flags.multiline
&& Input::CharProps::is_line_terminator(c) =>
{
true
}
_ => false,
};
next_or_bt!(matches)
}
&Insn::Jump { target } => {
ip = target as usize;
continue 'nextinsn;
}
&Insn::BeginCaptureGroup(cg_idx) => {
let cg = self.s.groups.mat(cg_idx as usize);
self.bts.push(BacktrackInsn::SetCaptureGroup {
id: cg_idx,
data: *cg,
});
if Dir::FORWARD {
cg.start = Some(pos);
debug_assert!(
cg.end.is_none(),
"Should not have already exited capture group we are entering"
)
} else {
cg.end = Some(pos);
debug_assert!(
cg.start.is_none(),
"Should not have already exited capture group we are entering"
)
}
next_or_bt!(true)
}
&Insn::EndCaptureGroup(cg_idx) => {
let cg = self.s.groups.mat(cg_idx as usize);
if Dir::FORWARD {
debug_assert!(
cg.start_matched(),
"Capture group should have been entered"
);
cg.end = Some(pos);
} else {
debug_assert!(
cg.end_matched(),
"Capture group should have been entered"
);
cg.start = Some(pos)
}
next_or_bt!(true)
}
&Insn::ResetCaptureGroup(cg_idx) => {
let cg = self.s.groups.mat(cg_idx as usize);
self.bts.push(BacktrackInsn::SetCaptureGroup {
id: cg_idx,
data: *cg,
});
cg.reset();
next_or_bt!(true)
}
&Insn::BackRef(cg_idx) => {
let cg = self.s.groups.mat(cg_idx as usize);
let matched;
if let Some(orig_range) = cg.as_range() {
if re.flags.icase {
matched = matchers::backref_icase(input, dir, orig_range, &mut pos);
} else {
matched = matchers::backref(input, dir, orig_range, &mut pos);
}
} else {
matched = true;
}
next_or_bt!(matched)
}
&Insn::LookaheadInsn {
negate,
start_group,
end_group,
continuation,
} => {
if self.run_lookaround::<Forward>(
input,
ip + 1,
pos,
start_group,
end_group,
negate,
) {
ip = continuation as IP;
continue 'nextinsn;
} else {
break 'backtrack;
}
}
&Insn::LookbehindInsn {
negate,
start_group,
end_group,
continuation,
} => {
if self.run_lookaround::<Backward>(
input,
ip + 1,
pos,
start_group,
end_group,
negate,
) {
ip = continuation as IP;
continue 'nextinsn;
} else {
break 'backtrack;
}
}
&Insn::Alt { secondary } => {
self.push_backtrack(BacktrackInsn::SetPosition {
ip: secondary as IP,
pos,
});
next_or_bt!(true);
}
Insn::EnterLoop(fields) => {
self.s.loops.mat(fields.loop_id as usize).iters = 0;
match self.run_loop(&fields, pos, ip) {
Some(next_ip) => {
ip = next_ip;
continue 'nextinsn;
}
None => {
break 'backtrack;
}
}
}
&Insn::LoopAgain { begin } => {
let act = match re.insns.iat(begin as IP) {
Insn::EnterLoop(fields) => self.run_loop(fields, pos, begin as IP),
_ => rs_unreachable!("EnterLoop should always refer to loop field"),
};
match act {
Some(next_ip) => {
ip = next_ip;
continue 'nextinsn;
}
None => break 'backtrack,
}
}
&Insn::Loop1CharBody {
min_iters,
max_iters,
greedy,
} => {
if let Some(next_ip) = self
.run_scm_loop(input, dir, &mut pos, min_iters, max_iters, ip, greedy)
{
ip = next_ip;
continue 'nextinsn;
} else {
break 'backtrack;
}
}
Insn::Goal => {
self.bts.truncate(1);
return Some(pos);
}
Insn::JustFail => {
break 'backtrack;
}
}
}
if self.try_backtrack(input, &mut ip, &mut pos, dir) {
continue 'nextinsn;
} else {
debug_assert!(self.bts.len() == 1, "Should have exhausted backtrack stack");
return None;
}
}
{
#![allow(unreachable_code)]
rs_unreachable!("Should not fall to end of nextinsn loop")
}
}
}
#[derive(Debug)]
pub struct BacktrackExecutor<'r, Input: InputIndexer> {
input: Input,
matcher: MatchAttempter<'r, Input>,
}
impl<'r, Input: InputIndexer> BacktrackExecutor<'r, Input> {
fn successful_match(&mut self, start: Input::Position, end: Input::Position) -> Match {
let mut captures = Vec::new();
captures.reserve_exact(self.matcher.s.groups.len());
for gd in self.matcher.s.groups.iter_mut() {
captures.push(match gd.as_range() {
Some(r) => Some(Range {
start: self.input.pos_to_offset(r.start),
end: self.input.pos_to_offset(r.end),
}),
None => None,
});
gd.start = None;
gd.end = None;
}
Match {
range: self.input.pos_to_offset(start)..self.input.pos_to_offset(end),
captures,
named_captures: self.matcher.re.named_group_indices.clone(),
}
}
fn next_match_with_prefix_search<PrefixSearch: bytesearch::ByteSearcher>(
&mut self,
mut pos: Input::Position,
next_start: &mut Option<Input::Position>,
prefix_search: &PrefixSearch,
) -> Option<Match> {
let inp = self.input;
loop {
pos = inp.find_bytes(pos, prefix_search)?;
if let Some(end) = self.matcher.try_at_pos(inp, 0, pos, Forward::new()) {
if end != pos {
*next_start = Some(end)
} else {
*next_start = inp.next_right_pos(end);
}
return Some(self.successful_match(pos, end));
}
pos = inp.next_right_pos(pos)?;
}
}
}
impl<'a, Input: InputIndexer> exec::MatchProducer for BacktrackExecutor<'a, Input> {
type Position = Input::Position;
fn initial_position(&self, offset: usize) -> Option<Self::Position> {
self.input.try_move_right(self.input.left_end(), offset)
}
fn next_match(
&mut self,
pos: Input::Position,
next_start: &mut Option<Input::Position>,
) -> Option<Match> {
match &self.matcher.re.start_pred {
StartPredicate::Arbitrary => {
self.next_match_with_prefix_search(pos, next_start, &bytesearch::EmptyString {})
}
StartPredicate::ByteSeq1(bytes) => {
self.next_match_with_prefix_search(pos, next_start, bytes)
}
StartPredicate::ByteSeq2(bytes) => {
self.next_match_with_prefix_search(pos, next_start, bytes)
}
StartPredicate::ByteSeq3(bytes) => {
self.next_match_with_prefix_search(pos, next_start, bytes)
}
StartPredicate::ByteSeq4(bytes) => {
self.next_match_with_prefix_search(pos, next_start, bytes)
}
&StartPredicate::ByteSet2(bytes) => self.next_match_with_prefix_search(
pos,
next_start,
&bytesearch::ByteArraySet(bytes),
),
StartPredicate::ByteBracket(bitmap) => {
self.next_match_with_prefix_search(pos, next_start, bitmap)
}
}
}
}
impl<'r, 't> exec::Executor<'r, 't> for BacktrackExecutor<'r, Utf8Input<'t>> {
type AsAscii = BacktrackExecutor<'r, AsciiInput<'t>>;
fn new(re: &'r CompiledRegex, text: &'t str) -> Self {
let input = Utf8Input::new(text);
Self {
input,
matcher: MatchAttempter::new(re, input.left_end()),
}
}
}
impl<'r, 't> exec::Executor<'r, 't> for BacktrackExecutor<'r, AsciiInput<'t>> {
type AsAscii = BacktrackExecutor<'r, AsciiInput<'t>>;
fn new(re: &'r CompiledRegex, text: &'t str) -> Self {
let input = AsciiInput::new(text);
Self {
input,
matcher: MatchAttempter::new(re, input.left_end()),
}
}
}