1use rustc_hash::FxHashMap;
2use std::fmt::Debug;
3
4#[derive(Clone, Copy, PartialEq, Hash, Eq, PartialOrd, Ord)]
5#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
6pub struct Nullability(pub u8);
7
8impl Debug for Nullability {
9 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
10 let num = &self.0;
11 f.write_str(format!("{num}").as_str())
12 }
13}
14impl Nullability {
15 pub const NEVER: Nullability = Nullability(0b000);
16 pub const CENTER: Nullability = Nullability(0b001);
17 pub const ALWAYS: Nullability = Nullability(0b111);
18 pub const BEGIN: Nullability = Nullability(0b010);
19 pub const END: Nullability = Nullability(0b100);
20 pub const NONBEGIN: Nullability = Nullability(0b011);
21 pub const EMPTYSTRING: Nullability = Nullability(0b110);
22 #[inline]
23 pub fn has(self, flag: Nullability) -> bool {
24 self.0 & flag.0 != 0
25 }
26 #[inline]
27 pub fn and(self, other: Nullability) -> Nullability {
28 Nullability(self.0 & other.0)
29 }
30 #[inline]
31 pub fn or(self, other: Nullability) -> Nullability {
32 Nullability(self.0 | other.0)
33 }
34 #[inline]
35 pub fn not(self) -> Nullability {
36 Nullability(!self.0)
37 }
38}
39
40#[derive(PartialEq, Eq, Clone, Hash)]
41#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
42pub struct NullState {
43 pub mask: Nullability,
44 pub rel: u32,
45}
46impl NullState {
47 pub fn new(mask: Nullability, rel: u32) -> NullState {
48 NullState { mask, rel }
49 }
50 pub fn new0(mask: Nullability) -> NullState {
51 NullState { mask, rel: 0 }
52 }
53
54 pub fn is_center_nullable(&self) -> bool {
55 self.mask.and(Nullability::CENTER) != Nullability::NEVER
56 }
57 pub fn is_mask_nullable(&self, mask: Nullability) -> bool {
58 self.mask.and(mask) != Nullability::NEVER
59 }
60}
61impl Ord for NullState {
62 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
63 other
64 .rel
65 .cmp(&self.rel)
66 .then_with(|| self.mask.cmp(&other.mask))
67 }
68}
69impl PartialOrd for NullState {
70 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
71 Some(self.cmp(other))
72 }
73}
74
75impl Debug for NullState {
76 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
77 f.debug_set().entry(&self.mask).entry(&self.rel).finish()
78 }
79}
80
81type Nulls = BTreeSet<NullState>;
82
83#[derive(Clone, Copy, PartialEq, Hash, Eq, Debug, PartialOrd, Ord)]
84pub struct NullsId(pub u32);
85impl NullsId {
86 pub const EMPTY: NullsId = NullsId(0);
87 pub const CENTER0: NullsId = NullsId(1);
88 pub const ALWAYS0: NullsId = NullsId(2);
89 pub const BEGIN0: NullsId = NullsId(3);
90 pub const END0: NullsId = NullsId(4);
91}
92
93pub const EID_NONE: u32 = NullsId::EMPTY.0;
94pub const EID_CENTER0: u32 = NullsId::CENTER0.0;
95pub const EID_ALWAYS0: u32 = NullsId::ALWAYS0.0;
96pub const EID_BEGIN0: u32 = NullsId::BEGIN0.0;
97pub const EID_END0: u32 = NullsId::END0.0;
98
99pub fn has_any_null(
100 effects_id: &[u16],
101 effects: &[Vec<NullState>],
102 state: u32,
103 mask: Nullability,
104) -> bool {
105 let eid = effects_id[state as usize] as u32;
106 if eid == 0 {
107 return false;
108 }
109 if eid == EID_ALWAYS0 {
110 return mask.has(Nullability::ALWAYS);
111 }
112 if eid == EID_CENTER0 {
113 return mask.has(Nullability::CENTER);
114 }
115 effects[eid as usize].iter().any(|n| n.mask.has(mask))
116}
117
118#[inline]
119pub fn push_null_desc(nulls: &mut Vec<usize>, v: usize) {
120 let mut j = nulls.len();
121 nulls.push(v);
122 while j > 0 && nulls[j - 1] < v {
123 nulls.swap(j - 1, j);
124 j -= 1;
125 }
126}
127
128#[inline(always)]
129pub fn collect_nulls(
130 effects_id: &[u16],
131 effects: &[Vec<NullState>],
132 state: u32,
133 pos: usize,
134 mask: Nullability,
135 nulls: &mut Vec<usize>,
136) {
137 let eid = effects_id[state as usize] as u32;
138 if eid != 0 {
139 match eid {
140 EID_ALWAYS0 => {
141 if mask.has(Nullability::ALWAYS) {
142 nulls.push(pos);
143 }
144 }
145 EID_CENTER0 => {
146 if mask.has(Nullability::CENTER) {
147 nulls.push(pos);
148 }
149 }
150 EID_BEGIN0 => {
151 if mask.has(Nullability::BEGIN) {
152 nulls.push(pos);
153 }
154 }
155 EID_END0 => {
156 if mask.has(Nullability::END) {
157 nulls.push(pos);
158 }
159 }
160 _ => {
161 for n in &effects[eid as usize] {
162 if n.mask.has(mask) {
163 let resolved = pos + n.rel as usize;
164 push_null_desc(nulls, resolved);
165 }
166 }
167 }
168 }
169 }
170}
171
172use std::{collections::BTreeSet, hash::Hash};
173
174#[repr(u8)]
175#[derive(Hash, PartialEq, Eq)]
176enum Operation {
177 Or,
178 Inter,
179}
180
181#[derive(Hash, PartialEq, Eq)]
182struct Key {
183 op: Operation,
184 left: NullsId,
185 right: NullsId,
186}
187
188pub struct NullsBuilder {
189 cache: FxHashMap<Nulls, NullsId>,
190 created: FxHashMap<Key, NullsId>,
191 add_rel_cache: FxHashMap<(NullsId, u32), NullsId>,
192 pub array: Vec<Nulls>,
193}
194
195impl Default for NullsBuilder {
196 fn default() -> Self {
197 Self::new()
198 }
199}
200
201impl NullsBuilder {
202 pub fn new() -> NullsBuilder {
203 let mut inst = Self {
204 cache: FxHashMap::default(),
205 array: Vec::new(),
206 created: FxHashMap::default(),
207 add_rel_cache: FxHashMap::default(),
208 };
209 let _ = inst.init(BTreeSet::new());
210 let _center = inst.init1(NullState::new0(Nullability::CENTER));
211 let _always = inst.init1(NullState::new0(Nullability::ALWAYS));
212 let _begin = inst.init1(NullState::new0(Nullability::BEGIN));
213 let _end = inst.init1(NullState::new0(Nullability::END));
214 debug_assert!(_center == NullsId::CENTER0);
215 debug_assert!(_always == NullsId::ALWAYS0);
216 debug_assert!(_begin == NullsId::BEGIN0);
217 debug_assert!(_end == NullsId::END0);
218 inst
219 }
220
221 fn init(&mut self, inst: Nulls) -> NullsId {
222 let new_id = NullsId(self.cache.len() as u32);
223 self.cache.insert(inst.clone(), new_id);
224 self.array.push(inst);
225 new_id
226 }
227
228 fn init1(&mut self, inst: NullState) -> NullsId {
229 let mut b = BTreeSet::new();
230 b.insert(inst);
231 let new_id = NullsId(self.cache.len() as u32);
232 self.cache.insert(b.clone(), new_id);
233 self.array.push(b);
234 new_id
235 }
236
237 pub fn get_set_ref(&self, set_id: NullsId) -> &Nulls {
238 &self.array[set_id.0 as usize]
239 }
240
241 pub fn get_id(&mut self, inst: Nulls) -> NullsId {
242 match self.cache.get(&inst) {
243 Some(&id) => id,
244 None => self.init(inst),
245 }
246 }
247}
248
249impl NullsBuilder {
250 #[inline]
251 fn is_created(&self, inst: &Key) -> Option<&NullsId> {
252 self.created.get(inst)
253 }
254
255 #[inline]
256 pub fn or_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
257 if set1 > set2 {
258 return self.or_id(set2, set1);
259 }
260 let key = Key {
261 op: Operation::Or,
262 left: set1,
263 right: set2,
264 };
265 if let Some(v) = self.is_created(&key) {
266 return *v;
267 }
268 if set1 == set2 {
269 return set1;
270 }
271 if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
272 return NullsId::ALWAYS0;
273 }
274 if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
275 return NullsId::ALWAYS0;
276 }
277
278 let all = self.get_set_ref(set1) | self.get_set_ref(set2);
279 let mut result: BTreeSet<&NullState> = BTreeSet::new();
280 for m in all.iter().rev() {
281 let dominated = result
282 .iter()
283 .any(|v| v.rel == m.rel && (v.mask.0 & m.mask.0) == m.mask.0);
284 if !dominated {
285 result.insert(m);
286 }
287 }
288
289 let result = result.into_iter().cloned().collect::<BTreeSet<_>>();
290
291 let new_id = self.get_id(result);
292 self.created.insert(key, new_id);
293 new_id
294 }
295
296 #[inline]
297 pub fn and_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
298 if NullsId::EMPTY == set1 {
299 return NullsId::EMPTY;
300 }
301 if NullsId::EMPTY == set2 {
302 return NullsId::EMPTY;
303 }
304 if set1 > set2 {
305 return self.and_id(set2, set1);
306 }
307 let key = Key {
308 op: Operation::Inter,
309 left: set1,
310 right: set2,
311 };
312 if let Some(v) = self.is_created(&key) {
313 return *v;
314 }
315 if set1 == set2 {
316 return set1;
317 }
318 let s1 = self.get_set_ref(set1).clone();
319 let s2 = self.get_set_ref(set2).clone();
320 let mut result: BTreeSet<NullState> = BTreeSet::new();
321 for ns1 in &s1 {
322 for ns2 in &s2 {
323 if ns1.rel == ns2.rel {
324 let mask = ns1.mask.and(ns2.mask);
325 if mask != Nullability::NEVER {
326 result.insert(NullState::new(mask, ns1.rel));
327 }
328 }
329 }
330 }
331 let result = self.get_id(result);
332 self.created.insert(key, result);
333 result
334 }
335
336 #[inline]
337 pub fn and_mask(&mut self, set1: NullsId, mask: Nullability) -> NullsId {
338 if NullsId::EMPTY == set1 || mask == Nullability::NEVER {
339 return NullsId::EMPTY;
340 }
341 if mask == Nullability::ALWAYS {
342 return set1;
343 }
344 let remaining = self
345 .get_set_ref(set1)
346 .iter()
347 .filter_map(|v| {
348 let newmask = v.mask.and(mask);
349 if newmask == Nullability::NEVER {
350 None
351 } else {
352 Some(NullState::new(newmask, v.rel))
353 }
354 })
355 .collect::<BTreeSet<_>>();
356
357 self.get_id(remaining)
358 }
359
360 #[inline]
361 pub fn not_id(&mut self, set_id: NullsId) -> NullsId {
362 if set_id == NullsId::EMPTY {
363 return NullsId::ALWAYS0;
364 }
365 if set_id == NullsId::ALWAYS0 {
366 return NullsId::EMPTY;
367 }
368 if set_id == NullsId::BEGIN0 {
369 return self.or_id(NullsId::CENTER0, NullsId::END0);
370 }
371 if set_id == NullsId::END0 {
372 return self.or_id(NullsId::CENTER0, NullsId::BEGIN0);
373 }
374 NullsId::EMPTY
375 }
376
377 pub fn max_rel(&self, set_id: NullsId) -> u32 {
378 self.get_set_ref(set_id).iter().next().map_or(0, |ns| ns.rel)
379 }
380
381 pub fn min_rel(&self, set_id: NullsId) -> u32 {
382 self.get_set_ref(set_id).iter().next_back().map_or(0, |ns| ns.rel)
383 }
384
385 #[inline]
386 pub fn add_rel(&mut self, set_id: NullsId, rel: u32) -> NullsId {
387 if rel == 0 || rel == u32::MAX {
388 return set_id;
389 }
390 if let Some(&cached) = self.add_rel_cache.get(&(set_id, rel)) {
391 return cached;
392 }
393 let res = self.get_set_ref(set_id).clone();
394 let with_rel = res
395 .iter()
396 .map(|v| NullState::new(v.mask, v.rel + rel))
397 .collect();
398 let result = self.get_id(with_rel);
399 self.add_rel_cache.insert((set_id, rel), result);
400 result
401 }
402}