use std::collections::HashMap;
use std::fmt;
use std::iter;
use std::result;
use std::sync::Arc;
use regex_syntax::hir::{self, Hir};
use regex_syntax::is_word_byte;
use regex_syntax::utf8::{Utf8Range, Utf8Sequence, Utf8Sequences};
use crate::prog::{
EmptyLook, Inst, InstBytes, InstChar, InstEmptyLook, InstPtr, InstRanges,
InstSave, InstSplit, Program,
};
use crate::Error;
type Result = result::Result<Patch, Error>;
type ResultOrEmpty = result::Result<Option<Patch>, Error>;
#[derive(Debug)]
struct Patch {
hole: Hole,
entry: InstPtr,
}
#[allow(missing_debug_implementations)]
pub struct Compiler {
insts: Vec<MaybeInst>,
compiled: Program,
capture_name_idx: HashMap<String, usize>,
num_exprs: usize,
size_limit: usize,
suffix_cache: SuffixCache,
utf8_seqs: Option<Utf8Sequences>,
byte_classes: ByteClassSet,
extra_inst_bytes: usize,
}
impl Compiler {
pub fn new() -> Self {
Compiler {
insts: vec![],
compiled: Program::new(),
capture_name_idx: HashMap::new(),
num_exprs: 0,
size_limit: 10 * (1 << 20),
suffix_cache: SuffixCache::new(1000),
utf8_seqs: Some(Utf8Sequences::new('\x00', '\x00')),
byte_classes: ByteClassSet::new(),
extra_inst_bytes: 0,
}
}
pub fn size_limit(mut self, size_limit: usize) -> Self {
self.size_limit = size_limit;
self
}
pub fn bytes(mut self, yes: bool) -> Self {
self.compiled.is_bytes = yes;
self
}
pub fn only_utf8(mut self, yes: bool) -> Self {
self.compiled.only_utf8 = yes;
self
}
pub fn dfa(mut self, yes: bool) -> Self {
self.compiled.is_dfa = yes;
self
}
pub fn reverse(mut self, yes: bool) -> Self {
self.compiled.is_reverse = yes;
self
}
pub fn compile(mut self, exprs: &[Hir]) -> result::Result<Program, Error> {
debug_assert!(!exprs.is_empty());
self.num_exprs = exprs.len();
if exprs.len() == 1 {
self.compile_one(&exprs[0])
} else {
self.compile_many(exprs)
}
}
fn compile_one(mut self, expr: &Hir) -> result::Result<Program, Error> {
let mut dotstar_patch = Patch { hole: Hole::None, entry: 0 };
self.compiled.is_anchored_start = expr.is_anchored_start();
self.compiled.is_anchored_end = expr.is_anchored_end();
if self.compiled.needs_dotstar() {
dotstar_patch = self.c_dotstar()?;
self.compiled.start = dotstar_patch.entry;
}
self.compiled.captures = vec![None];
let patch =
self.c_capture(0, expr)?.unwrap_or_else(|| self.next_inst());
if self.compiled.needs_dotstar() {
self.fill(dotstar_patch.hole, patch.entry);
} else {
self.compiled.start = patch.entry;
}
self.fill_to_next(patch.hole);
self.compiled.matches = vec![self.insts.len()];
self.push_compiled(Inst::Match(0));
self.compile_finish()
}
fn compile_many(
mut self,
exprs: &[Hir],
) -> result::Result<Program, Error> {
debug_assert!(exprs.len() > 1);
self.compiled.is_anchored_start =
exprs.iter().all(|e| e.is_anchored_start());
self.compiled.is_anchored_end =
exprs.iter().all(|e| e.is_anchored_end());
let mut dotstar_patch = Patch { hole: Hole::None, entry: 0 };
if self.compiled.needs_dotstar() {
dotstar_patch = self.c_dotstar()?;
self.compiled.start = dotstar_patch.entry;
} else {
self.compiled.start = 0; }
self.fill_to_next(dotstar_patch.hole);
let mut prev_hole = Hole::None;
for (i, expr) in exprs[0..exprs.len() - 1].iter().enumerate() {
self.fill_to_next(prev_hole);
let split = self.push_split_hole();
let Patch { hole, entry } =
self.c_capture(0, expr)?.unwrap_or_else(|| self.next_inst());
self.fill_to_next(hole);
self.compiled.matches.push(self.insts.len());
self.push_compiled(Inst::Match(i));
prev_hole = self.fill_split(split, Some(entry), None);
}
let i = exprs.len() - 1;
let Patch { hole, entry } =
self.c_capture(0, &exprs[i])?.unwrap_or_else(|| self.next_inst());
self.fill(prev_hole, entry);
self.fill_to_next(hole);
self.compiled.matches.push(self.insts.len());
self.push_compiled(Inst::Match(i));
self.compile_finish()
}
fn compile_finish(mut self) -> result::Result<Program, Error> {
self.compiled.insts =
self.insts.into_iter().map(|inst| inst.unwrap()).collect();
self.compiled.byte_classes = self.byte_classes.byte_classes();
self.compiled.capture_name_idx = Arc::new(self.capture_name_idx);
Ok(self.compiled)
}
fn c(&mut self, expr: &Hir) -> ResultOrEmpty {
use crate::prog;
use regex_syntax::hir::HirKind::*;
self.check_size()?;
match *expr.kind() {
Empty => self.c_empty(),
Literal(hir::Literal::Unicode(c)) => self.c_char(c),
Literal(hir::Literal::Byte(b)) => {
assert!(self.compiled.uses_bytes());
self.c_byte(b)
}
Class(hir::Class::Unicode(ref cls)) => self.c_class(cls.ranges()),
Class(hir::Class::Bytes(ref cls)) => {
if self.compiled.uses_bytes() {
self.c_class_bytes(cls.ranges())
} else {
assert!(cls.is_all_ascii());
let mut char_ranges = vec![];
for r in cls.iter() {
let (s, e) = (r.start() as char, r.end() as char);
char_ranges.push(hir::ClassUnicodeRange::new(s, e));
}
self.c_class(&char_ranges)
}
}
Anchor(hir::Anchor::StartLine) if self.compiled.is_reverse => {
self.byte_classes.set_range(b'\n', b'\n');
self.c_empty_look(prog::EmptyLook::EndLine)
}
Anchor(hir::Anchor::StartLine) => {
self.byte_classes.set_range(b'\n', b'\n');
self.c_empty_look(prog::EmptyLook::StartLine)
}
Anchor(hir::Anchor::EndLine) if self.compiled.is_reverse => {
self.byte_classes.set_range(b'\n', b'\n');
self.c_empty_look(prog::EmptyLook::StartLine)
}
Anchor(hir::Anchor::EndLine) => {
self.byte_classes.set_range(b'\n', b'\n');
self.c_empty_look(prog::EmptyLook::EndLine)
}
Anchor(hir::Anchor::StartText) if self.compiled.is_reverse => {
self.c_empty_look(prog::EmptyLook::EndText)
}
Anchor(hir::Anchor::StartText) => {
self.c_empty_look(prog::EmptyLook::StartText)
}
Anchor(hir::Anchor::EndText) if self.compiled.is_reverse => {
self.c_empty_look(prog::EmptyLook::StartText)
}
Anchor(hir::Anchor::EndText) => {
self.c_empty_look(prog::EmptyLook::EndText)
}
WordBoundary(hir::WordBoundary::Unicode) => {
if !cfg!(feature = "unicode-perl") {
return Err(Error::Syntax(
"Unicode word boundaries are unavailable when \
the unicode-perl feature is disabled"
.to_string(),
));
}
self.compiled.has_unicode_word_boundary = true;
self.byte_classes.set_word_boundary();
self.byte_classes.set_range(0, 0x7F);
self.c_empty_look(prog::EmptyLook::WordBoundary)
}
WordBoundary(hir::WordBoundary::UnicodeNegate) => {
if !cfg!(feature = "unicode-perl") {
return Err(Error::Syntax(
"Unicode word boundaries are unavailable when \
the unicode-perl feature is disabled"
.to_string(),
));
}
self.compiled.has_unicode_word_boundary = true;
self.byte_classes.set_word_boundary();
self.byte_classes.set_range(0, 0x7F);
self.c_empty_look(prog::EmptyLook::NotWordBoundary)
}
WordBoundary(hir::WordBoundary::Ascii) => {
self.byte_classes.set_word_boundary();
self.c_empty_look(prog::EmptyLook::WordBoundaryAscii)
}
WordBoundary(hir::WordBoundary::AsciiNegate) => {
self.byte_classes.set_word_boundary();
self.c_empty_look(prog::EmptyLook::NotWordBoundaryAscii)
}
Group(ref g) => match g.kind {
hir::GroupKind::NonCapturing => self.c(&g.hir),
hir::GroupKind::CaptureIndex(index) => {
if index as usize >= self.compiled.captures.len() {
self.compiled.captures.push(None);
}
self.c_capture(2 * index as usize, &g.hir)
}
hir::GroupKind::CaptureName { index, ref name } => {
if index as usize >= self.compiled.captures.len() {
let n = name.to_string();
self.compiled.captures.push(Some(n.clone()));
self.capture_name_idx.insert(n, index as usize);
}
self.c_capture(2 * index as usize, &g.hir)
}
},
Concat(ref es) => {
if self.compiled.is_reverse {
self.c_concat(es.iter().rev())
} else {
self.c_concat(es)
}
}
Alternation(ref es) => self.c_alternate(&**es),
Repetition(ref rep) => self.c_repeat(rep),
}
}
fn c_empty(&mut self) -> ResultOrEmpty {
self.extra_inst_bytes += std::mem::size_of::<Inst>();
Ok(None)
}
fn c_capture(&mut self, first_slot: usize, expr: &Hir) -> ResultOrEmpty {
if self.num_exprs > 1 || self.compiled.is_dfa {
self.c(expr)
} else {
let entry = self.insts.len();
let hole = self.push_hole(InstHole::Save { slot: first_slot });
let patch = self.c(expr)?.unwrap_or_else(|| self.next_inst());
self.fill(hole, patch.entry);
self.fill_to_next(patch.hole);
let hole = self.push_hole(InstHole::Save { slot: first_slot + 1 });
Ok(Some(Patch { hole, entry }))
}
}
fn c_dotstar(&mut self) -> Result {
Ok(if !self.compiled.only_utf8() {
self.c(&Hir::repetition(hir::Repetition {
kind: hir::RepetitionKind::ZeroOrMore,
greedy: false,
hir: Box::new(Hir::any(true)),
}))?
.unwrap()
} else {
self.c(&Hir::repetition(hir::Repetition {
kind: hir::RepetitionKind::ZeroOrMore,
greedy: false,
hir: Box::new(Hir::any(false)),
}))?
.unwrap()
})
}
fn c_char(&mut self, c: char) -> ResultOrEmpty {
if self.compiled.uses_bytes() {
if c.is_ascii() {
let b = c as u8;
let hole =
self.push_hole(InstHole::Bytes { start: b, end: b });
self.byte_classes.set_range(b, b);
Ok(Some(Patch { hole, entry: self.insts.len() - 1 }))
} else {
self.c_class(&[hir::ClassUnicodeRange::new(c, c)])
}
} else {
let hole = self.push_hole(InstHole::Char { c });
Ok(Some(Patch { hole, entry: self.insts.len() - 1 }))
}
}
fn c_class(&mut self, ranges: &[hir::ClassUnicodeRange]) -> ResultOrEmpty {
use std::mem::size_of;
assert!(!ranges.is_empty());
if self.compiled.uses_bytes() {
Ok(Some(CompileClass { c: self, ranges }.compile()?))
} else {
let ranges: Vec<(char, char)> =
ranges.iter().map(|r| (r.start(), r.end())).collect();
let hole = if ranges.len() == 1 && ranges[0].0 == ranges[0].1 {
self.push_hole(InstHole::Char { c: ranges[0].0 })
} else {
self.extra_inst_bytes +=
ranges.len() * (size_of::<char>() * 2);
self.push_hole(InstHole::Ranges { ranges })
};
Ok(Some(Patch { hole, entry: self.insts.len() - 1 }))
}
}
fn c_byte(&mut self, b: u8) -> ResultOrEmpty {
self.c_class_bytes(&[hir::ClassBytesRange::new(b, b)])
}
fn c_class_bytes(
&mut self,
ranges: &[hir::ClassBytesRange],
) -> ResultOrEmpty {
debug_assert!(!ranges.is_empty());
let first_split_entry = self.insts.len();
let mut holes = vec![];
let mut prev_hole = Hole::None;
for r in &ranges[0..ranges.len() - 1] {
self.fill_to_next(prev_hole);
let split = self.push_split_hole();
let next = self.insts.len();
self.byte_classes.set_range(r.start(), r.end());
holes.push(self.push_hole(InstHole::Bytes {
start: r.start(),
end: r.end(),
}));
prev_hole = self.fill_split(split, Some(next), None);
}
let next = self.insts.len();
let r = &ranges[ranges.len() - 1];
self.byte_classes.set_range(r.start(), r.end());
holes.push(
self.push_hole(InstHole::Bytes { start: r.start(), end: r.end() }),
);
self.fill(prev_hole, next);
Ok(Some(Patch { hole: Hole::Many(holes), entry: first_split_entry }))
}
fn c_empty_look(&mut self, look: EmptyLook) -> ResultOrEmpty {
let hole = self.push_hole(InstHole::EmptyLook { look });
Ok(Some(Patch { hole, entry: self.insts.len() - 1 }))
}
fn c_concat<'a, I>(&mut self, exprs: I) -> ResultOrEmpty
where
I: IntoIterator<Item = &'a Hir>,
{
let mut exprs = exprs.into_iter();
let Patch { mut hole, entry } = loop {
match exprs.next() {
None => return self.c_empty(),
Some(e) => {
if let Some(p) = self.c(e)? {
break p;
}
}
}
};
for e in exprs {
if let Some(p) = self.c(e)? {
self.fill(hole, p.entry);
hole = p.hole;
}
}
Ok(Some(Patch { hole, entry }))
}
fn c_alternate(&mut self, exprs: &[Hir]) -> ResultOrEmpty {
debug_assert!(
exprs.len() >= 2,
"alternates must have at least 2 exprs"
);
let first_split_entry = self.insts.len();
let mut holes = vec![];
let mut prev_hole = (Hole::None, false);
for e in &exprs[0..exprs.len() - 1] {
if prev_hole.1 {
let next = self.insts.len();
self.fill_split(prev_hole.0, None, Some(next));
} else {
self.fill_to_next(prev_hole.0);
}
let split = self.push_split_hole();
if let Some(Patch { hole, entry }) = self.c(e)? {
holes.push(hole);
prev_hole = (self.fill_split(split, Some(entry), None), false);
} else {
let (split1, split2) = split.dup_one();
holes.push(split1);
prev_hole = (split2, true);
}
}
if let Some(Patch { hole, entry }) = self.c(&exprs[exprs.len() - 1])? {
holes.push(hole);
if prev_hole.1 {
self.fill_split(prev_hole.0, None, Some(entry));
} else {
self.fill(prev_hole.0, entry);
}
} else {
holes.push(prev_hole.0);
}
Ok(Some(Patch { hole: Hole::Many(holes), entry: first_split_entry }))
}
fn c_repeat(&mut self, rep: &hir::Repetition) -> ResultOrEmpty {
use regex_syntax::hir::RepetitionKind::*;
match rep.kind {
ZeroOrOne => self.c_repeat_zero_or_one(&rep.hir, rep.greedy),
ZeroOrMore => self.c_repeat_zero_or_more(&rep.hir, rep.greedy),
OneOrMore => self.c_repeat_one_or_more(&rep.hir, rep.greedy),
Range(hir::RepetitionRange::Exactly(min_max)) => {
self.c_repeat_range(&rep.hir, rep.greedy, min_max, min_max)
}
Range(hir::RepetitionRange::AtLeast(min)) => {
self.c_repeat_range_min_or_more(&rep.hir, rep.greedy, min)
}
Range(hir::RepetitionRange::Bounded(min, max)) => {
self.c_repeat_range(&rep.hir, rep.greedy, min, max)
}
}
}
fn c_repeat_zero_or_one(
&mut self,
expr: &Hir,
greedy: bool,
) -> ResultOrEmpty {
let split_entry = self.insts.len();
let split = self.push_split_hole();
let Patch { hole: hole_rep, entry: entry_rep } = match self.c(expr)? {
Some(p) => p,
None => return self.pop_split_hole(),
};
let split_hole = if greedy {
self.fill_split(split, Some(entry_rep), None)
} else {
self.fill_split(split, None, Some(entry_rep))
};
let holes = vec![hole_rep, split_hole];
Ok(Some(Patch { hole: Hole::Many(holes), entry: split_entry }))
}
fn c_repeat_zero_or_more(
&mut self,
expr: &Hir,
greedy: bool,
) -> ResultOrEmpty {
let split_entry = self.insts.len();
let split = self.push_split_hole();
let Patch { hole: hole_rep, entry: entry_rep } = match self.c(expr)? {
Some(p) => p,
None => return self.pop_split_hole(),
};
self.fill(hole_rep, split_entry);
let split_hole = if greedy {
self.fill_split(split, Some(entry_rep), None)
} else {
self.fill_split(split, None, Some(entry_rep))
};
Ok(Some(Patch { hole: split_hole, entry: split_entry }))
}
fn c_repeat_one_or_more(
&mut self,
expr: &Hir,
greedy: bool,
) -> ResultOrEmpty {
let Patch { hole: hole_rep, entry: entry_rep } = match self.c(expr)? {
Some(p) => p,
None => return Ok(None),
};
self.fill_to_next(hole_rep);
let split = self.push_split_hole();
let split_hole = if greedy {
self.fill_split(split, Some(entry_rep), None)
} else {
self.fill_split(split, None, Some(entry_rep))
};
Ok(Some(Patch { hole: split_hole, entry: entry_rep }))
}
fn c_repeat_range_min_or_more(
&mut self,
expr: &Hir,
greedy: bool,
min: u32,
) -> ResultOrEmpty {
let min = u32_to_usize(min);
let patch_concat = self
.c_concat(iter::repeat(expr).take(min))?
.unwrap_or_else(|| self.next_inst());
if let Some(patch_rep) = self.c_repeat_zero_or_more(expr, greedy)? {
self.fill(patch_concat.hole, patch_rep.entry);
Ok(Some(Patch { hole: patch_rep.hole, entry: patch_concat.entry }))
} else {
Ok(None)
}
}
fn c_repeat_range(
&mut self,
expr: &Hir,
greedy: bool,
min: u32,
max: u32,
) -> ResultOrEmpty {
let (min, max) = (u32_to_usize(min), u32_to_usize(max));
debug_assert!(min <= max);
let patch_concat = self.c_concat(iter::repeat(expr).take(min))?;
if min == max {
return Ok(patch_concat);
}
let patch_concat = patch_concat.unwrap_or_else(|| self.next_inst());
let initial_entry = patch_concat.entry;
let mut holes = vec![];
let mut prev_hole = patch_concat.hole;
for _ in min..max {
self.fill_to_next(prev_hole);
let split = self.push_split_hole();
let Patch { hole, entry } = match self.c(expr)? {
Some(p) => p,
None => return self.pop_split_hole(),
};
prev_hole = hole;
if greedy {
holes.push(self.fill_split(split, Some(entry), None));
} else {
holes.push(self.fill_split(split, None, Some(entry)));
}
}
holes.push(prev_hole);
Ok(Some(Patch { hole: Hole::Many(holes), entry: initial_entry }))
}
fn next_inst(&self) -> Patch {
Patch { hole: Hole::None, entry: self.insts.len() }
}
fn fill(&mut self, hole: Hole, goto: InstPtr) {
match hole {
Hole::None => {}
Hole::One(pc) => {
self.insts[pc].fill(goto);
}
Hole::Many(holes) => {
for hole in holes {
self.fill(hole, goto);
}
}
}
}
fn fill_to_next(&mut self, hole: Hole) {
let next = self.insts.len();
self.fill(hole, next);
}
fn fill_split(
&mut self,
hole: Hole,
goto1: Option<InstPtr>,
goto2: Option<InstPtr>,
) -> Hole {
match hole {
Hole::None => Hole::None,
Hole::One(pc) => match (goto1, goto2) {
(Some(goto1), Some(goto2)) => {
self.insts[pc].fill_split(goto1, goto2);
Hole::None
}
(Some(goto1), None) => {
self.insts[pc].half_fill_split_goto1(goto1);
Hole::One(pc)
}
(None, Some(goto2)) => {
self.insts[pc].half_fill_split_goto2(goto2);
Hole::One(pc)
}
(None, None) => unreachable!(
"at least one of the split \
holes must be filled"
),
},
Hole::Many(holes) => {
let mut new_holes = vec![];
for hole in holes {
new_holes.push(self.fill_split(hole, goto1, goto2));
}
if new_holes.is_empty() {
Hole::None
} else if new_holes.len() == 1 {
new_holes.pop().unwrap()
} else {
Hole::Many(new_holes)
}
}
}
}
fn push_compiled(&mut self, inst: Inst) {
self.insts.push(MaybeInst::Compiled(inst));
}
fn push_hole(&mut self, inst: InstHole) -> Hole {
let hole = self.insts.len();
self.insts.push(MaybeInst::Uncompiled(inst));
Hole::One(hole)
}
fn push_split_hole(&mut self) -> Hole {
let hole = self.insts.len();
self.insts.push(MaybeInst::Split);
Hole::One(hole)
}
fn pop_split_hole(&mut self) -> ResultOrEmpty {
self.insts.pop();
Ok(None)
}
fn check_size(&self) -> result::Result<(), Error> {
use std::mem::size_of;
let size =
self.extra_inst_bytes + (self.insts.len() * size_of::<Inst>());
if size > self.size_limit {
Err(Error::CompiledTooBig(self.size_limit))
} else {
Ok(())
}
}
}
#[derive(Debug)]
enum Hole {
None,
One(InstPtr),
Many(Vec<Hole>),
}
impl Hole {
fn dup_one(self) -> (Self, Self) {
match self {
Hole::One(pc) => (Hole::One(pc), Hole::One(pc)),
Hole::None | Hole::Many(_) => {
unreachable!("must be called on single hole")
}
}
}
}
#[derive(Clone, Debug)]
enum MaybeInst {
Compiled(Inst),
Uncompiled(InstHole),
Split,
Split1(InstPtr),
Split2(InstPtr),
}
impl MaybeInst {
fn fill(&mut self, goto: InstPtr) {
let maybeinst = match *self {
MaybeInst::Split => MaybeInst::Split1(goto),
MaybeInst::Uncompiled(ref inst) => {
MaybeInst::Compiled(inst.fill(goto))
}
MaybeInst::Split1(goto1) => {
MaybeInst::Compiled(Inst::Split(InstSplit {
goto1,
goto2: goto,
}))
}
MaybeInst::Split2(goto2) => {
MaybeInst::Compiled(Inst::Split(InstSplit {
goto1: goto,
goto2,
}))
}
_ => unreachable!(
"not all instructions were compiled! \
found uncompiled instruction: {:?}",
self
),
};
*self = maybeinst;
}
fn fill_split(&mut self, goto1: InstPtr, goto2: InstPtr) {
let filled = match *self {
MaybeInst::Split => Inst::Split(InstSplit { goto1, goto2 }),
_ => unreachable!(
"must be called on Split instruction, \
instead it was called on: {:?}",
self
),
};
*self = MaybeInst::Compiled(filled);
}
fn half_fill_split_goto1(&mut self, goto1: InstPtr) {
let half_filled = match *self {
MaybeInst::Split => goto1,
_ => unreachable!(
"must be called on Split instruction, \
instead it was called on: {:?}",
self
),
};
*self = MaybeInst::Split1(half_filled);
}
fn half_fill_split_goto2(&mut self, goto2: InstPtr) {
let half_filled = match *self {
MaybeInst::Split => goto2,
_ => unreachable!(
"must be called on Split instruction, \
instead it was called on: {:?}",
self
),
};
*self = MaybeInst::Split2(half_filled);
}
fn unwrap(self) -> Inst {
match self {
MaybeInst::Compiled(inst) => inst,
_ => unreachable!(
"must be called on a compiled instruction, \
instead it was called on: {:?}",
self
),
}
}
}
#[derive(Clone, Debug)]
enum InstHole {
Save { slot: usize },
EmptyLook { look: EmptyLook },
Char { c: char },
Ranges { ranges: Vec<(char, char)> },
Bytes { start: u8, end: u8 },
}
impl InstHole {
fn fill(&self, goto: InstPtr) -> Inst {
match *self {
InstHole::Save { slot } => Inst::Save(InstSave { goto, slot }),
InstHole::EmptyLook { look } => {
Inst::EmptyLook(InstEmptyLook { goto, look })
}
InstHole::Char { c } => Inst::Char(InstChar { goto, c }),
InstHole::Ranges { ref ranges } => Inst::Ranges(InstRanges {
goto,
ranges: ranges.clone().into_boxed_slice(),
}),
InstHole::Bytes { start, end } => {
Inst::Bytes(InstBytes { goto, start, end })
}
}
}
}
struct CompileClass<'a, 'b> {
c: &'a mut Compiler,
ranges: &'b [hir::ClassUnicodeRange],
}
impl<'a, 'b> CompileClass<'a, 'b> {
fn compile(mut self) -> Result {
let mut holes = vec![];
let mut initial_entry = None;
let mut last_split = Hole::None;
let mut utf8_seqs = self.c.utf8_seqs.take().unwrap();
self.c.suffix_cache.clear();
for (i, range) in self.ranges.iter().enumerate() {
let is_last_range = i + 1 == self.ranges.len();
utf8_seqs.reset(range.start(), range.end());
let mut it = (&mut utf8_seqs).peekable();
loop {
let utf8_seq = match it.next() {
None => break,
Some(utf8_seq) => utf8_seq,
};
if is_last_range && it.peek().is_none() {
let Patch { hole, entry } = self.c_utf8_seq(&utf8_seq)?;
holes.push(hole);
self.c.fill(last_split, entry);
last_split = Hole::None;
if initial_entry.is_none() {
initial_entry = Some(entry);
}
} else {
if initial_entry.is_none() {
initial_entry = Some(self.c.insts.len());
}
self.c.fill_to_next(last_split);
last_split = self.c.push_split_hole();
let Patch { hole, entry } = self.c_utf8_seq(&utf8_seq)?;
holes.push(hole);
last_split =
self.c.fill_split(last_split, Some(entry), None);
}
}
}
self.c.utf8_seqs = Some(utf8_seqs);
Ok(Patch { hole: Hole::Many(holes), entry: initial_entry.unwrap() })
}
fn c_utf8_seq(&mut self, seq: &Utf8Sequence) -> Result {
if self.c.compiled.is_reverse {
self.c_utf8_seq_(seq)
} else {
self.c_utf8_seq_(seq.into_iter().rev())
}
}
fn c_utf8_seq_<'r, I>(&mut self, seq: I) -> Result
where
I: IntoIterator<Item = &'r Utf8Range>,
{
let mut from_inst = ::std::usize::MAX;
let mut last_hole = Hole::None;
for byte_range in seq {
let key = SuffixCacheKey {
from_inst,
start: byte_range.start,
end: byte_range.end,
};
{
let pc = self.c.insts.len();
if let Some(cached_pc) = self.c.suffix_cache.get(key, pc) {
from_inst = cached_pc;
continue;
}
}
self.c.byte_classes.set_range(byte_range.start, byte_range.end);
if from_inst == ::std::usize::MAX {
last_hole = self.c.push_hole(InstHole::Bytes {
start: byte_range.start,
end: byte_range.end,
});
} else {
self.c.push_compiled(Inst::Bytes(InstBytes {
goto: from_inst,
start: byte_range.start,
end: byte_range.end,
}));
}
from_inst = self.c.insts.len().checked_sub(1).unwrap();
debug_assert!(from_inst < ::std::usize::MAX);
}
debug_assert!(from_inst < ::std::usize::MAX);
Ok(Patch { hole: last_hole, entry: from_inst })
}
}
#[derive(Debug)]
struct SuffixCache {
sparse: Box<[usize]>,
dense: Vec<SuffixCacheEntry>,
}
#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
struct SuffixCacheEntry {
key: SuffixCacheKey,
pc: InstPtr,
}
#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
struct SuffixCacheKey {
from_inst: InstPtr,
start: u8,
end: u8,
}
impl SuffixCache {
fn new(size: usize) -> Self {
SuffixCache {
sparse: vec![0usize; size].into(),
dense: Vec::with_capacity(size),
}
}
fn get(&mut self, key: SuffixCacheKey, pc: InstPtr) -> Option<InstPtr> {
let hash = self.hash(&key);
let pos = &mut self.sparse[hash];
if let Some(entry) = self.dense.get(*pos) {
if entry.key == key {
return Some(entry.pc);
}
}
*pos = self.dense.len();
self.dense.push(SuffixCacheEntry { key, pc });
None
}
fn clear(&mut self) {
self.dense.clear();
}
fn hash(&self, suffix: &SuffixCacheKey) -> usize {
const FNV_PRIME: u64 = 1_099_511_628_211;
let mut h = 14_695_981_039_346_656_037;
h = (h ^ (suffix.from_inst as u64)).wrapping_mul(FNV_PRIME);
h = (h ^ (suffix.start as u64)).wrapping_mul(FNV_PRIME);
h = (h ^ (suffix.end as u64)).wrapping_mul(FNV_PRIME);
(h as usize) % self.sparse.len()
}
}
struct ByteClassSet([bool; 256]);
impl ByteClassSet {
fn new() -> Self {
ByteClassSet([false; 256])
}
fn set_range(&mut self, start: u8, end: u8) {
debug_assert!(start <= end);
if start > 0 {
self.0[start as usize - 1] = true;
}
self.0[end as usize] = true;
}
fn set_word_boundary(&mut self) {
let iswb = is_word_byte;
let mut b1: u16 = 0;
let mut b2: u16;
while b1 <= 255 {
b2 = b1 + 1;
while b2 <= 255 && iswb(b1 as u8) == iswb(b2 as u8) {
b2 += 1;
}
self.set_range(b1 as u8, (b2 - 1) as u8);
b1 = b2;
}
}
fn byte_classes(&self) -> Vec<u8> {
let mut byte_classes = vec![0; 256];
let mut class = 0u8;
let mut i = 0;
loop {
byte_classes[i] = class as u8;
if i >= 255 {
break;
}
if self.0[i] {
class = class.checked_add(1).unwrap();
}
i += 1;
}
byte_classes
}
}
impl fmt::Debug for ByteClassSet {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("ByteClassSet").field(&&self.0[..]).finish()
}
}
fn u32_to_usize(n: u32) -> usize {
if (n as u64) > (::std::usize::MAX as u64) {
panic!("BUG: {} is too big to be pointer sized", n)
}
n as usize
}
#[cfg(test)]
mod tests {
use super::ByteClassSet;
#[test]
fn byte_classes() {
let mut set = ByteClassSet::new();
set.set_range(b'a', b'z');
let classes = set.byte_classes();
assert_eq!(classes[0], 0);
assert_eq!(classes[1], 0);
assert_eq!(classes[2], 0);
assert_eq!(classes[b'a' as usize - 1], 0);
assert_eq!(classes[b'a' as usize], 1);
assert_eq!(classes[b'm' as usize], 1);
assert_eq!(classes[b'z' as usize], 1);
assert_eq!(classes[b'z' as usize + 1], 2);
assert_eq!(classes[254], 2);
assert_eq!(classes[255], 2);
let mut set = ByteClassSet::new();
set.set_range(0, 2);
set.set_range(4, 6);
let classes = set.byte_classes();
assert_eq!(classes[0], 0);
assert_eq!(classes[1], 0);
assert_eq!(classes[2], 0);
assert_eq!(classes[3], 1);
assert_eq!(classes[4], 2);
assert_eq!(classes[5], 2);
assert_eq!(classes[6], 2);
assert_eq!(classes[7], 3);
assert_eq!(classes[255], 3);
}
#[test]
fn full_byte_classes() {
let mut set = ByteClassSet::new();
for i in 0..256u16 {
set.set_range(i as u8, i as u8);
}
assert_eq!(set.byte_classes().len(), 256);
}
}