1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
//! Select one condition necessary for every successful match. Emission is done,
//! so AST slots can be reused without growing caller scratch or the program.
use super::*;
use core::cmp::Ordering;
/// Marks a candidate reached through a positive assertion. A lookbehind body
/// can satisfy its condition before the match start, so such a condition
/// proves presence somewhere but never a bound on where a match may begin.
/// Node indices are bounded by caller scratch, so the top bit is free.
const ASSERTED: u32 = 1 << 31;
impl Prepared<'_> {
fn compare_admission(
&mut self,
p: Program<'_>,
a: u32,
b: u32,
) -> Result<Ordering, CompileError> {
let (a, b) = (a & !ASSERTED, b & !ASSERTED);
let (left, right) = (self.nodes[a as usize - 1], self.nodes[b as usize - 1]);
let score = left.end.cmp(&right.end);
if score != Ordering::Equal {
return Ok(score);
}
let (lpc, rpc) = (left.start as usize, right.start as usize);
let (li, ri) = (p.instruction(lpc), p.instruction(rpc));
let kind = li[0].cmp(&ri[0]);
if kind != Ordering::Equal {
return Ok(kind);
}
if matches!(li[0], CHAR | CHAR_I) {
let len = ADMISSION_MAX - left.end as usize;
for i in 0..len {
self.step()?;
let l = p.instruction(lpc + if left.reverse { len - 1 - i } else { i })[1];
let r = p.instruction(rpc + if right.reverse { len - 1 - i } else { i })[1];
let order = l.cmp(&r);
if order != Ordering::Equal {
return Ok(order);
}
}
} else {
let shape = li[2].cmp(&ri[2]);
if shape != Ordering::Equal {
return Ok(shape);
}
for i in 0..li[2] as usize {
self.step()?;
let order = p
.range(li[1] as usize + i)
.cmp(&p.range(ri[1] as usize + i));
if order != Ordering::Equal {
return Ok(order);
}
}
}
Ok(Ordering::Equal)
}
pub(super) fn admission(&mut self, p: Program<'_>, root: u32) -> Result<u32, CompileError> {
let (mut literal_start, mut literal_end) = (0, 0);
for i in 0..self.used {
self.step()?;
let n = self.nodes[i];
let candidate = match n.kind {
CHAR => {
let pc = n.start as usize;
let op = p.instruction(pc)[0];
if pc < literal_start || pc >= literal_end {
// Cache the entire instruction run, including reverse
// bodies. Rescanning up to 32 successors for every
// literal made long-pattern compilation unnecessarily
// expensive. AST literal leaves visit each run together.
literal_start = pc;
literal_end = pc + 1;
while literal_start > 0 && p.instruction(literal_start - 1)[0] == op {
self.step()?;
literal_start -= 1;
}
while literal_end < p.instructions() && p.instruction(literal_end)[0] == op
{
self.step()?;
literal_end += 1;
}
}
let len = (literal_end - pc).min(ADMISSION_MAX);
self.nodes[i].end = (ADMISSION_MAX - len) as u32;
i as u32 + 1
}
CLASS if n.b & NEGATED == 0 => {
let mut cardinality = 0u32;
for r in n.a..n.a + n.b {
self.step()?;
let [lo, hi] = p.range(r as usize);
if lo & PROPERTY != 0 {
cardinality = 257;
break;
}
cardinality = cardinality.saturating_add(hi - lo + 1);
if cardinality > 256 {
break;
}
}
if cardinality <= 256 {
// A heuristic rank only; actual membership reuses VM
// semantics. Overlapping ranges need not be normalized.
self.nodes[i].end = ADMISSION_MAX as u32 + cardinality;
i as u32 + 1
} else {
0
}
}
GROUP | WRAP => self.nodes[n.a as usize].c,
REPEAT if n.b > 0 => self.nodes[n.a as usize].c,
ASSERT if n.flags & 1 == 0 => match self.nodes[n.a as usize].c {
0 => 0,
inner => inner | ASSERTED,
},
SEQ | ALT => {
let (a, b) = (self.nodes[n.a as usize].c, self.nodes[n.b as usize].c);
if n.kind == ALT {
if a != 0 && b != 0 && self.compare_admission(p, a, b)? == Ordering::Equal {
// Both paths must bound the start for the claim to hold.
a | (b & ASSERTED)
} else {
0
}
} else if a == 0 {
b
} else if b == 0 {
a
} else {
let (left, right) = (
self.nodes[(a & !ASSERTED) as usize - 1],
self.nodes[(b & !ASSERTED) as usize - 1],
);
// A sequence does not need lexical equality: either
// condition is necessary. Prefer the later literal on
// a rank tie (a+z should check z). Keep canonical class
// ranking so reordered alternatives share conditions.
let order = if left.kind == CHAR && right.kind == CHAR {
left.end.cmp(&right.end).then(Ordering::Greater)
} else {
self.compare_admission(p, a, b)?
};
if order == Ordering::Greater { b } else { a }
}
}
_ => 0,
};
// c/end no longer hold repeat maxima/capture ends after emission.
self.nodes[i].c = candidate;
}
let id = self.nodes[root as usize].c;
if id == 0 {
return Ok(0);
}
let n = self.nodes[(id & !ASSERTED) as usize - 1];
// The bound resumes a literal byte search, so only a literal condition
// carries the claim; a class condition still proves presence only.
self.forward = id & ASSERTED == 0
&& n.start < 1 << 24
&& matches!(p.instruction(n.start as usize)[0], CHAR | CHAR_I);
if n.start >= 1 << 24 {
return Ok(0);
} // Omit the optimization, not the pattern.
Ok(ADMISSION | (n.start << 8) | if n.reverse { ADMISSION_REVERSE } else { 0 })
}
}