1use std::collections::BTreeSet;
2
3use crate::automaton::{
4 concatenate_automaton_class_values, finite_language_values, join_automaton_class_values,
5};
6use crate::domain::{meaningful_longest_common_prefix, meaningful_longest_common_suffix};
7use crate::reduced_product::{
8 concatenate_reduced_product_class_values, intersect_reduced_product_class_values,
9 join_reduced_product_class_values, reduced_product_class_value_is_subset,
10};
11use crate::selector_projection::abstract_value_matches_string;
12use crate::{
13 AbstractClassValueProvenanceV0, AbstractClassValueV0, bottom_class_value,
14 finite_set_class_value, prefix_class_value, prefix_suffix_class_value, suffix_class_value,
15 top_class_value_with_provenance,
16};
17
18pub fn intersect_abstract_class_values(
19 left: &AbstractClassValueV0,
20 right: &AbstractClassValueV0,
21) -> AbstractClassValueV0 {
22 match (left, right) {
23 (AbstractClassValueV0::Bottom, _) | (_, AbstractClassValueV0::Bottom) => {
24 bottom_class_value()
25 }
26 (AbstractClassValueV0::Top { .. }, value) | (value, AbstractClassValueV0::Top { .. }) => {
27 value.clone()
28 }
29 _ => intersect_non_top_class_values(left, right),
30 }
31}
32
33pub fn join_abstract_class_values(
34 left: &AbstractClassValueV0,
35 right: &AbstractClassValueV0,
36) -> AbstractClassValueV0 {
37 if abstract_class_value_is_subset(left, right) {
38 return right.clone();
39 }
40 if abstract_class_value_is_subset(right, left) {
41 return left.clone();
42 }
43
44 if let Some(joined) = join_automaton_class_values(left, right) {
45 return joined;
46 }
47
48 match (finite_language_values(left), finite_language_values(right)) {
49 (Some(values), None)
50 if values
51 .iter()
52 .all(|value| abstract_value_matches_string(right, value)) =>
53 {
54 return right.clone();
55 }
56 (None, Some(values))
57 if values
58 .iter()
59 .all(|value| abstract_value_matches_string(left, value)) =>
60 {
61 return left.clone();
62 }
63 _ => {}
64 }
65
66 match (left, right) {
67 (
68 AbstractClassValueV0::Prefix {
69 prefix: left_prefix,
70 ..
71 },
72 AbstractClassValueV0::Prefix {
73 prefix: right_prefix,
74 ..
75 },
76 ) => {
77 let prefix =
78 meaningful_longest_common_prefix(&[left_prefix.clone(), right_prefix.clone()]);
79 if !prefix.is_empty() {
80 return prefix_class_value(
81 prefix,
82 Some(AbstractClassValueProvenanceV0::PrefixJoinLcp),
83 );
84 }
85 }
86 (
87 AbstractClassValueV0::Suffix {
88 suffix: left_suffix,
89 ..
90 },
91 AbstractClassValueV0::Suffix {
92 suffix: right_suffix,
93 ..
94 },
95 ) => {
96 let suffix =
97 meaningful_longest_common_suffix(&[left_suffix.clone(), right_suffix.clone()]);
98 if !suffix.is_empty() {
99 return suffix_class_value(
100 suffix,
101 Some(AbstractClassValueProvenanceV0::SuffixJoinLcs),
102 );
103 }
104 }
105 _ => {}
106 }
107
108 join_reduced_product_class_values(left, right).unwrap_or_else(|| {
109 top_class_value_with_provenance(AbstractClassValueProvenanceV0::JoinUnrepresentable)
110 })
111}
112
113pub fn concatenate_abstract_class_values(
114 left: &AbstractClassValueV0,
115 right: &AbstractClassValueV0,
116) -> AbstractClassValueV0 {
117 match (left, right) {
118 (AbstractClassValueV0::Bottom, _) | (_, AbstractClassValueV0::Bottom) => {
119 return bottom_class_value();
120 }
121 (AbstractClassValueV0::Top { .. }, _) => {
122 return left.clone();
123 }
124 (_, AbstractClassValueV0::Top { .. }) => {
125 return right.clone();
126 }
127 _ => {}
128 }
129
130 if let Some(concatenated) = concatenate_automaton_class_values(left, right) {
131 return concatenated;
132 }
133
134 match (left, right) {
135 (AbstractClassValueV0::Exact { value }, AbstractClassValueV0::Prefix { prefix, .. }) => {
136 prefix_class_value(format!("{value}{prefix}"), None)
137 }
138 (AbstractClassValueV0::Exact { value }, AbstractClassValueV0::Suffix { suffix, .. }) => {
139 prefix_suffix_class_value(value, suffix, Some(value.len() + suffix.len()), None)
140 }
141 (
142 AbstractClassValueV0::Exact { value },
143 AbstractClassValueV0::PrefixSuffix {
144 prefix,
145 suffix,
146 min_length,
147 ..
148 },
149 ) => prefix_suffix_class_value(
150 format!("{value}{prefix}"),
151 suffix,
152 Some(value.len() + min_length),
153 None,
154 ),
155 (AbstractClassValueV0::Prefix { prefix, .. }, AbstractClassValueV0::Exact { value }) => {
156 prefix_suffix_class_value(prefix, value, Some(prefix.len() + value.len()), None)
157 }
158 (
159 AbstractClassValueV0::Prefix { prefix, .. },
160 AbstractClassValueV0::FiniteSet { values },
161 ) => {
162 let suffix = meaningful_longest_common_suffix(values);
163 if suffix.is_empty() {
164 prefix_class_value(prefix, None)
165 } else {
166 prefix_suffix_class_value(
167 prefix,
168 suffix.clone(),
169 Some(prefix.len() + suffix.len()),
170 None,
171 )
172 }
173 }
174 (AbstractClassValueV0::Prefix { prefix, .. }, AbstractClassValueV0::Prefix { .. }) => {
175 prefix_class_value(prefix, None)
176 }
177 (
178 AbstractClassValueV0::Prefix { prefix, .. },
179 AbstractClassValueV0::Suffix { suffix, .. },
180 )
181 | (
182 AbstractClassValueV0::Prefix { prefix, .. },
183 AbstractClassValueV0::PrefixSuffix { suffix, .. },
184 ) => prefix_suffix_class_value(prefix, suffix, Some(prefix.len() + suffix.len()), None),
185 (
186 AbstractClassValueV0::FiniteSet { values },
187 AbstractClassValueV0::Prefix { prefix, .. },
188 ) => {
189 let values = values
190 .iter()
191 .map(|value| format!("{value}{prefix}"))
192 .collect::<Vec<_>>();
193 let prefix = meaningful_longest_common_prefix(&values);
194 if prefix.is_empty() {
195 top_class_value_with_provenance(
196 AbstractClassValueProvenanceV0::ConcatenationUnrepresentable,
197 )
198 } else {
199 prefix_class_value(prefix, None)
200 }
201 }
202 (
203 AbstractClassValueV0::FiniteSet { values },
204 AbstractClassValueV0::Suffix { suffix, .. },
205 ) => {
206 let prefix = meaningful_longest_common_prefix(values);
207 if prefix.is_empty() {
208 suffix_class_value(suffix, None)
209 } else {
210 prefix_suffix_class_value(prefix, suffix, Some(suffix.len()), None)
211 }
212 }
213 (AbstractClassValueV0::Suffix { .. }, AbstractClassValueV0::FiniteSet { values }) => {
214 let suffix = meaningful_longest_common_suffix(values);
215 if suffix.is_empty() {
216 top_class_value_with_provenance(
217 AbstractClassValueProvenanceV0::ConcatenationUnrepresentable,
218 )
219 } else {
220 suffix_class_value(suffix, None)
221 }
222 }
223 (AbstractClassValueV0::Suffix { .. }, AbstractClassValueV0::Suffix { suffix, .. }) => {
224 suffix_class_value(suffix, None)
225 }
226 (
227 AbstractClassValueV0::Suffix { .. },
228 AbstractClassValueV0::PrefixSuffix { suffix, .. },
229 ) => suffix_class_value(suffix, None),
230 (
231 AbstractClassValueV0::PrefixSuffix { prefix, .. },
232 AbstractClassValueV0::Prefix { .. },
233 ) => prefix_class_value(prefix, None),
234 (
235 AbstractClassValueV0::PrefixSuffix {
236 prefix,
237 suffix,
238 min_length,
239 ..
240 },
241 AbstractClassValueV0::Exact { value },
242 ) => prefix_suffix_class_value(
243 prefix,
244 format!("{suffix}{value}"),
245 Some(min_length + value.len()),
246 None,
247 ),
248 (
249 AbstractClassValueV0::PrefixSuffix {
250 prefix,
251 suffix,
252 min_length,
253 ..
254 },
255 AbstractClassValueV0::FiniteSet { values },
256 ) => {
257 let shared_suffix = meaningful_longest_common_suffix(values);
258 if shared_suffix.is_empty() {
259 prefix_class_value(prefix, None)
260 } else {
261 prefix_suffix_class_value(
262 prefix,
263 format!("{suffix}{shared_suffix}"),
264 Some(min_length + shared_suffix.len()),
265 None,
266 )
267 }
268 }
269 (
270 AbstractClassValueV0::PrefixSuffix { prefix, .. },
271 AbstractClassValueV0::Suffix { suffix, .. },
272 ) => prefix_suffix_class_value(prefix, suffix, Some(prefix.len() + suffix.len()), None),
273 (
274 AbstractClassValueV0::PrefixSuffix { prefix, .. },
275 AbstractClassValueV0::PrefixSuffix {
276 suffix, min_length, ..
277 },
278 ) => prefix_suffix_class_value(prefix, suffix, Some(prefix.len() + min_length), None),
279 _ => concatenate_reduced_product_class_values(left, right).unwrap_or_else(|| {
280 top_class_value_with_provenance(
281 AbstractClassValueProvenanceV0::ConcatenationUnrepresentable,
282 )
283 }),
284 }
285}
286
287fn intersect_non_top_class_values(
288 left: &AbstractClassValueV0,
289 right: &AbstractClassValueV0,
290) -> AbstractClassValueV0 {
291 match (finite_language_values(left), finite_language_values(right)) {
292 (Some(left_values), Some(right_values)) => {
293 let right_values = right_values.into_iter().collect::<BTreeSet<_>>();
294 return finite_set_class_value(
295 left_values
296 .into_iter()
297 .filter(|value| right_values.contains(value)),
298 );
299 }
300 (Some(values), None) => {
301 return finite_set_class_value(
302 values
303 .into_iter()
304 .filter(|value| abstract_value_matches_string(right, value)),
305 );
306 }
307 (None, Some(values)) => {
308 return finite_set_class_value(
309 values
310 .into_iter()
311 .filter(|value| abstract_value_matches_string(left, value)),
312 );
313 }
314 (None, None) => {}
315 }
316
317 intersect_reduced_product_class_values(left, right).unwrap_or_else(bottom_class_value)
318}
319
320pub fn abstract_class_value_is_subset(
321 left: &AbstractClassValueV0,
322 right: &AbstractClassValueV0,
323) -> bool {
324 if left == right {
325 return true;
326 }
327
328 match (left, right) {
329 (AbstractClassValueV0::Bottom, _) | (_, AbstractClassValueV0::Top { .. }) => true,
330 (AbstractClassValueV0::Top { .. }, _) => false,
331 _ => {
332 finite_language_values(left).is_some_and(|values| {
333 values
334 .iter()
335 .all(|value| abstract_value_matches_string(right, value))
336 }) || constrained_value_is_subset(left, right)
337 || reduced_product_class_value_is_subset(left, right).unwrap_or(false)
338 }
339 }
340}
341
342fn constrained_value_is_subset(left: &AbstractClassValueV0, right: &AbstractClassValueV0) -> bool {
343 match (left, right) {
344 (
345 AbstractClassValueV0::Prefix {
346 prefix: left_prefix,
347 ..
348 },
349 AbstractClassValueV0::Prefix {
350 prefix: right_prefix,
351 ..
352 },
353 ) => left_prefix.starts_with(right_prefix),
354 (
355 AbstractClassValueV0::Suffix {
356 suffix: left_suffix,
357 ..
358 },
359 AbstractClassValueV0::Suffix {
360 suffix: right_suffix,
361 ..
362 },
363 ) => left_suffix.ends_with(right_suffix),
364 (
365 AbstractClassValueV0::PrefixSuffix {
366 prefix: left_prefix,
367 suffix: _,
368 ..
369 },
370 AbstractClassValueV0::Prefix {
371 prefix: right_prefix,
372 ..
373 },
374 ) => left_prefix.starts_with(right_prefix),
375 (
376 AbstractClassValueV0::PrefixSuffix {
377 prefix: left_prefix,
378 suffix: left_suffix,
379 min_length: left_min_length,
380 ..
381 },
382 AbstractClassValueV0::PrefixSuffix {
383 prefix: right_prefix,
384 suffix: right_suffix,
385 min_length: right_min_length,
386 ..
387 },
388 ) => {
389 left_prefix.starts_with(right_prefix)
390 && left_suffix.ends_with(right_suffix)
391 && left_min_length >= right_min_length
392 }
393 (
394 AbstractClassValueV0::PrefixSuffix {
395 suffix: left_suffix,
396 ..
397 },
398 AbstractClassValueV0::Suffix {
399 suffix: right_suffix,
400 ..
401 },
402 ) => left_suffix.ends_with(right_suffix),
403 _ => false,
404 }
405}