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
93use std::{collections::BTreeSet, hash::Hash};
94
95#[repr(u8)]
96#[derive(Hash, PartialEq, Eq)]
97enum Operation {
98 Or,
99 Inter,
100}
101
102#[derive(Hash, PartialEq, Eq)]
103struct Key {
104 op: Operation,
105 left: NullsId,
106 right: NullsId,
107}
108
109pub struct NullsBuilder {
110 cache: FxHashMap<Nulls, NullsId>,
111 created: FxHashMap<Key, NullsId>,
112 pub array: Vec<Nulls>,
113}
114
115impl Default for NullsBuilder {
116 fn default() -> Self {
117 Self::new()
118 }
119}
120
121impl NullsBuilder {
122 pub fn new() -> NullsBuilder {
123 let mut inst = Self {
124 cache: FxHashMap::default(),
125 array: Vec::new(),
126 created: FxHashMap::default(),
127 };
128 let _ = inst.init(BTreeSet::new());
129 let _center = inst.init1(NullState::new0(Nullability::CENTER));
130 let _always = inst.init1(NullState::new0(Nullability::ALWAYS));
131 let _begin = inst.init1(NullState::new0(Nullability::BEGIN));
132 let _end = inst.init1(NullState::new0(Nullability::END));
133 debug_assert!(_center == NullsId::CENTER0);
134 debug_assert!(_always == NullsId::ALWAYS0);
135 debug_assert!(_begin == NullsId::BEGIN0);
136 debug_assert!(_end == NullsId::END0);
137 inst
138 }
139
140 fn init(&mut self, inst: Nulls) -> NullsId {
141 let new_id = NullsId(self.cache.len() as u32);
142 self.cache.insert(inst.clone(), new_id);
143 self.array.push(inst);
144 new_id
145 }
146
147 fn init1(&mut self, inst: NullState) -> NullsId {
148 let mut b = BTreeSet::new();
149 b.insert(inst);
150 let new_id = NullsId(self.cache.len() as u32);
151 self.cache.insert(b.clone(), new_id);
152 self.array.push(b);
153 new_id
154 }
155
156 pub fn get_set_ref(&self, set_id: NullsId) -> &Nulls {
157 &self.array[set_id.0 as usize]
158 }
159
160 pub fn get_id(&mut self, inst: Nulls) -> NullsId {
161 match self.cache.get(&inst) {
162 Some(&id) => id,
163 None => self.init(inst),
164 }
165 }
166}
167
168impl NullsBuilder {
169 #[inline]
170 fn is_created(&self, inst: &Key) -> Option<&NullsId> {
171 self.created.get(inst)
172 }
173
174 #[inline]
175 pub fn or_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
176 if set1 > set2 {
177 return self.or_id(set2, set1);
178 }
179 let key = Key {
180 op: Operation::Or,
181 left: set1,
182 right: set2,
183 };
184 if let Some(v) = self.is_created(&key) {
185 return *v;
186 }
187 if set1 == set2 {
188 return set1;
189 }
190 if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
191 return NullsId::ALWAYS0;
192 }
193 if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
194 return NullsId::ALWAYS0;
195 }
196
197 let all = self.get_set_ref(set1) | self.get_set_ref(set2);
198 let mut result: BTreeSet<&NullState> = BTreeSet::new();
199 for m in all.iter().rev() {
200 let found = result.iter().find(|v| v.mask == m.mask && v.rel == m.rel);
201 if found.is_none() {
202 result.insert(m);
203 }
204 }
205
206 let result = result.into_iter().cloned().collect::<BTreeSet<_>>();
207
208 let new_id = self.get_id(result);
209 self.created.insert(key, new_id);
210 new_id
211 }
212
213 #[inline]
214 pub fn and_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
215 if NullsId::EMPTY == set1 {
216 return NullsId::EMPTY;
217 }
218 if NullsId::EMPTY == set2 {
219 return NullsId::EMPTY;
220 }
221 if set1 > set2 {
222 return self.and_id(set2, set1);
223 }
224 let key = Key {
225 op: Operation::Inter,
226 left: set1,
227 right: set2,
228 };
229 if let Some(v) = self.is_created(&key) {
230 return *v;
231 }
232 if set1 == set2 {
233 return set1;
234 }
235 if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
236 return NullsId::END0;
237 }
238 if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
239 return NullsId::END0;
240 }
241
242 let result = self.get_id(self.get_set_ref(set1) | self.get_set_ref(set2));
243 self.created.insert(key, result);
244 result
245 }
246
247 #[inline]
248 pub fn and_mask(&mut self, set1: NullsId, mask: Nullability) -> NullsId {
249 if NullsId::EMPTY == set1 || mask == Nullability::NEVER {
250 return NullsId::EMPTY;
251 }
252 if mask == Nullability::ALWAYS {
253 return set1;
254 }
255 let remaining = self
256 .get_set_ref(set1)
257 .iter()
258 .filter_map(|v| {
259 let newmask = v.mask.and(mask);
260 if newmask == Nullability::NEVER {
261 None
262 } else {
263 Some(NullState::new(newmask, v.rel))
264 }
265 })
266 .collect::<BTreeSet<_>>();
267
268 self.get_id(remaining)
269 }
270
271 #[inline]
272 pub fn not_id(&mut self, set_id: NullsId) -> NullsId {
273 if set_id == NullsId::EMPTY {
274 return NullsId::ALWAYS0;
275 }
276 if set_id == NullsId::ALWAYS0 {
277 return NullsId::EMPTY;
278 }
279 if set_id == NullsId::BEGIN0 {
280 return self.or_id(NullsId::CENTER0, NullsId::END0);
281 }
282 if set_id == NullsId::END0 {
283 return self.or_id(NullsId::CENTER0, NullsId::BEGIN0);
284 }
285 NullsId::EMPTY
286 }
287
288 #[inline]
289 pub fn add_rel(&mut self, set_id: NullsId, rel: u32) -> NullsId {
290 if rel == 0 || rel == u32::MAX {
291 return set_id;
292 }
293 let res = self.get_set_ref(set_id).clone();
294 let with_rel = res
295 .iter()
296 .map(|v| NullState::new(v.mask, v.rel + rel))
297 .collect();
298
299 self.get_id(with_rel)
300 }
301}