1use super::*;
3
4#[derive(Clone, Copy, Debug, PartialEq, Eq)]
5pub(crate) enum CountingName {
6 Count(RelationMode),
7 AtLeast,
8 AtMost,
9 Among,
10 Nvalue,
11 Cardinality { closed: bool, bounded: bool },
12 Window { boolean: bool },
13 Coded { matches: bool },
14}
15
16impl CountingName {
17 pub fn from_name(name: &str) -> Option<Self> {
18 for base in [
20 name,
21 name.strip_prefix("gecode_").unwrap_or(""),
22 name.strip_prefix("fzn_").unwrap_or(""),
23 ] {
24 let found = match base {
25 "count" | "count_eq" => Self::Count(RelationMode::Plain),
26 "count_reif" | "count_eq_reif" => Self::Count(RelationMode::Reified),
27 "count_imp" | "count_eq_imp" => Self::Count(RelationMode::Implied),
28 "at_least_int" => Self::AtLeast,
29 "at_most_int" => Self::AtMost,
30 "among" => Self::Among,
31 "nvalue" => Self::Nvalue,
32 "gecode_global_cardinality" => Self::Cardinality {
33 closed: false,
34 bounded: false,
35 },
36 "gecode_global_cardinality_closed" => Self::Cardinality {
37 closed: true,
38 bounded: false,
39 },
40 "global_cardinality_low_up" => Self::Cardinality {
41 closed: false,
42 bounded: true,
43 },
44 "global_cardinality_low_up_closed" => Self::Cardinality {
45 closed: true,
46 bounded: true,
47 },
48 "gecode_among_seq_int" => Self::Window { boolean: false },
49 "gecode_among_seq_bool" => Self::Window { boolean: true },
50 "gecode_count_int_fzn" => Self::Coded { matches: false },
51 "gecode_count_matches_fzn" => Self::Coded { matches: true },
52 _ => continue,
53 };
54 return Some(found);
55 }
56 None
57 }
58
59 #[cfg(feature = "prepare")]
60 pub fn signature(self) -> Vec<prepare::ArgumentType> {
61 use ValueType::*;
62 let scalar = |kind, is_var| prepare::ArgumentType {
63 kind,
64 is_var,
65 is_array: false,
66 };
67 let array = |kind, is_var| prepare::ArgumentType {
68 kind,
69 is_var,
70 is_array: true,
71 };
72 let int = scalar(Integer, true);
73 let fixed = scalar(Integer, false);
74 let entries = array(Integer, true);
75 match self {
76 Self::Count(mode) => {
77 let mut args = vec![entries, int.clone(), int];
78 if mode != RelationMode::Plain {
79 args.push(scalar(Boolean, true));
80 }
81 args
82 }
83 Self::AtLeast | Self::AtMost => vec![fixed.clone(), entries, fixed],
84 Self::Among => vec![int, entries, scalar(IntegerSet, false)],
85 Self::Nvalue => vec![int, entries],
86 Self::Cardinality { bounded, .. } => {
87 let mut args = vec![entries, array(Integer, false), array(Integer, !bounded)];
88 if bounded {
89 args.push(array(Integer, false));
90 }
91 args
92 }
93 Self::Window { boolean } => vec![
94 array(if boolean { Boolean } else { Integer }, true),
95 scalar(if boolean { Boolean } else { IntegerSet }, false),
96 fixed.clone(),
97 fixed.clone(),
98 fixed,
99 ],
100 Self::Coded { matches } => vec![
101 entries,
102 if matches {
103 array(Integer, false)
104 } else {
105 int.clone()
106 },
107 fixed,
108 int,
109 ],
110 }
111 }
112}
113
114#[derive(Debug, Serialize, Deserialize)]
115pub(crate) enum CountSelector {
116 Needle(Operand),
117 Matches(
118 #[serde(
119 serialize_with = "serialize_integers",
120 deserialize_with = "deserialize_integers"
121 )]
122 Vec<i64>,
123 ),
124 Members(IntegerSet),
125 Distinct,
126}
127
128#[derive(Debug, Serialize, Deserialize)]
129pub(crate) enum CardinalityCounts {
130 Exact(Vec<Operand>),
131 Bounds {
132 #[serde(
133 serialize_with = "serialize_integers",
134 deserialize_with = "deserialize_integers"
135 )]
136 lower: Vec<i64>,
137 #[serde(
138 serialize_with = "serialize_integers",
139 deserialize_with = "deserialize_integers"
140 )]
141 upper: Vec<i64>,
142 },
143}
144
145#[derive(Debug, Serialize, Deserialize)]
146pub(crate) enum Counting {
147 Count {
148 entries: Vec<Operand>,
149 selector: CountSelector,
150 count: Operand,
151 relation: IntegerRelation,
152 condition: RelationCondition,
153 #[serde(
154 serialize_with = "serialize_optional_integer",
155 deserialize_with = "deserialize_optional_integer"
156 )]
157 code: Option<i64>,
158 },
159 Cardinality {
160 entries: Vec<Operand>,
161 #[serde(
162 serialize_with = "serialize_integers",
163 deserialize_with = "deserialize_integers"
164 )]
165 cover: Vec<i64>,
166 counts: CardinalityCounts,
167 closed: bool,
168 },
169 Window {
170 entries: Vec<Operand>,
171 membership: Value,
172 #[serde(
173 serialize_with = "serialize_integer",
174 deserialize_with = "deserialize_integer"
175 )]
176 length: i64,
177 #[serde(
178 serialize_with = "serialize_integer",
179 deserialize_with = "deserialize_integer"
180 )]
181 lower: i64,
182 #[serde(
183 serialize_with = "serialize_integer",
184 deserialize_with = "deserialize_integer"
185 )]
186 upper: i64,
187 },
188}
189
190#[derive(Clone, Debug, Serialize)]
191#[serde(tag = "kind", rename_all = "snake_case")]
192pub enum CountSelectorValue {
193 Needle {
194 value: Option<ArgumentValue>,
195 unresolved: Option<Box<VariableRef>>,
196 irrelevant: bool,
197 },
198 Matches {
199 #[serde(serialize_with = "serialize_integers")]
200 values: Vec<i64>,
201 },
202 Members {
203 set: IntegerSet,
204 },
205 Distinct,
206}
207
208#[derive(Clone, Debug, Serialize)]
209pub struct CountPosition {
210 pub position: usize,
211 #[serde(serialize_with = "serialize_integer")]
212 pub cover: i64,
213 #[serde(serialize_with = "serialize_integer")]
214 pub calculated: i64,
215 pub supplied: Option<ArgumentValue>,
216 #[serde(serialize_with = "serialize_optional_integer")]
217 pub lower: Option<i64>,
218 #[serde(serialize_with = "serialize_optional_integer")]
219 pub upper: Option<i64>,
220}
221
222#[derive(Clone, Debug, Serialize)]
223pub struct WindowCount {
224 pub position: usize,
225 #[serde(serialize_with = "serialize_integer")]
226 pub calculated: i64,
227}
228
229impl Counting {
230 pub fn operands(&self, required: bool) -> Vec<&Operand> {
231 match self {
232 Self::Count {
233 entries,
234 selector,
235 count,
236 condition,
237 ..
238 } => entries
239 .iter()
240 .chain(match selector {
241 CountSelector::Needle(needle) if !required || !entries.is_empty() => {
242 Some(needle)
243 }
244 _ => None,
245 })
246 .chain(std::iter::once(count))
247 .chain(condition.operand())
248 .collect(),
249 Self::Cardinality {
250 entries, counts, ..
251 } => entries
252 .iter()
253 .chain(match counts {
254 CardinalityCounts::Exact(counts) => counts.iter(),
255 _ => [].iter(),
256 })
257 .collect(),
258 Self::Window { entries, .. } => entries.iter().collect(),
259 }
260 }
261
262 pub fn validate_shape(&self) -> Result<(), &'static str> {
263 match self {
264 Self::Count {
265 entries,
266 selector: CountSelector::Matches(matches),
267 ..
268 } if entries.len() != matches.len() => {
269 Err("positional count arrays must have equal lengths")
270 }
271 Self::Cardinality { cover, counts, .. } => {
272 let valid = match counts {
273 CardinalityCounts::Exact(counts) => counts.len() == cover.len(),
274 CardinalityCounts::Bounds { lower, upper } => {
275 lower.len() == cover.len() && upper.len() == cover.len()
276 }
277 };
278 if valid {
279 Ok(())
280 } else {
281 Err("cardinality cover and count arrays must have equal lengths")
282 }
283 }
284 Self::Window {
285 entries, length, ..
286 } if entries.is_empty()
287 || *length < 1
288 || usize::try_from(*length)
289 .ok()
290 .is_none_or(|q| q > entries.len()) =>
291 {
292 Err("count windows require nonempty entries and length in 1..array length")
293 }
294 _ => Ok(()),
295 }
296 }
297
298 fn calculate(&self, values: &[Option<Value>]) -> Option<i64> {
299 let Self::Count {
300 entries, selector, ..
301 } = self
302 else {
303 unreachable!()
304 };
305 let concrete = integers(entries, values)?;
306 let count = match selector {
307 CountSelector::Needle(needle) => {
308 if concrete.is_empty() {
309 0
310 } else {
311 let needle = needle.value(values)?.integer();
312 concrete.iter().filter(|&&value| value == needle).count()
313 }
314 }
315 CountSelector::Matches(matches) => {
316 concrete.iter().zip(matches).filter(|(a, b)| a == b).count()
317 }
318 CountSelector::Members(set) => concrete
319 .iter()
320 .filter(|&&value| set.contains(value))
321 .count(),
322 CountSelector::Distinct => concrete.iter().collect::<HashSet<_>>().len(),
323 };
324 Some(i64::try_from(count).expect("addressable aggregate fits i64"))
326 }
327
328 pub fn can_define(&self, output: usize) -> bool {
329 let is_output =
330 |operand: &Operand| matches!(operand, Operand::Variable(slot) if *slot == output);
331 match self {
332 Self::Count {
333 entries,
334 selector,
335 count,
336 relation,
337 condition,
338 ..
339 } => {
340 let input = entries.iter().any(is_output)
341 || matches!(selector, CountSelector::Needle(needle) if is_output(needle) && !entries.is_empty());
342 if input {
343 return false;
344 }
345 match condition {
346 RelationCondition::Plain => {
347 *relation == IntegerRelation::Equal && is_output(count)
348 }
349 RelationCondition::Reified { result } => is_output(result) && !is_output(count),
350 _ => false,
351 }
352 }
353 Self::Cardinality {
354 entries,
355 counts: CardinalityCounts::Exact(counts),
356 ..
357 } => counts.iter().any(is_output) && !entries.iter().any(is_output),
358 _ => false,
359 }
360 }
361
362 pub fn derive(
363 &self,
364 output: usize,
365 values: &[Option<Value>],
366 constraint: &Constraint,
367 ) -> Result<Option<Value>, CheckError> {
368 match self {
369 Self::Count {
370 count,
371 relation,
372 condition,
373 ..
374 } => {
375 let Some(calculated) = self.calculate(values) else {
376 return Ok(None);
377 };
378 Ok(match condition {
379 RelationCondition::Plain => Some(Value::Integer(calculated)),
380 RelationCondition::Reified { .. } => count
381 .value(values)
382 .map(|count| Value::Boolean(relation.holds(calculated, count.integer()))),
383 _ => None,
384 })
385 }
386 Self::Cardinality {
387 entries,
388 cover,
389 counts: CardinalityCounts::Exact(counts),
390 ..
391 } => {
392 let Some(entries) = integers(entries, values) else {
393 return Ok(None);
394 };
395 let mut result = None;
396 for (&cover, count) in cover.iter().zip(counts) {
397 if matches!(count, Operand::Variable(slot) if *slot == output) {
398 let count = occurrence(&entries, cover)
399 .map_err(|message| constraint.execution_error(message))?;
400 if result.is_some_and(|prior| prior != count) {
401 return Ok(None);
402 }
403 result = Some(count);
404 }
405 }
406 Ok(result.map(Value::Integer))
407 }
408 _ => Ok(None),
409 }
410 }
411}
412
413fn integers(entries: &[Operand], values: &[Option<Value>]) -> Option<Vec<i64>> {
414 entries
415 .iter()
416 .map(|entry| entry.value(values).map(Value::integer))
417 .collect()
418}
419fn occurrence(entries: &[i64], value: i64) -> Result<i64, &'static str> {
420 i64::try_from(entries.iter().filter(|&&entry| entry == value).count())
421 .map_err(|_| "checked i64 overflow in counting aggregate")
422}
423
424impl PreparedModel {
425 pub(crate) fn evaluate_counting(
426 &self,
427 constraint: &Constraint,
428 counting: &Counting,
429 values: &[Option<Value>],
430 ) -> Result<Option<ViolationKind>, CheckError> {
431 let argument = |operand| {
432 self.argument(operand, values)
433 .expect("available counting operand")
434 };
435 Ok(match counting {
436 Counting::Count {
437 entries,
438 selector,
439 count,
440 relation,
441 condition,
442 code,
443 } => {
444 let calculated = counting
445 .calculate(values)
446 .expect("available counting inputs");
447 if condition.satisfied(
448 relation.holds(calculated, count.value(values).unwrap().integer()),
449 values,
450 ) {
451 return Ok(None);
452 }
453 let selector = match selector {
454 CountSelector::Needle(needle) => CountSelectorValue::Needle {
455 value: self.argument(needle, values),
456 unresolved: match needle {
457 Operand::Variable(slot) if values[*slot].is_none() => {
458 Some(Box::new(self.slots[*slot].reference.clone()))
459 }
460 _ => None,
461 },
462 irrelevant: entries.is_empty(),
463 },
464 CountSelector::Matches(values) => CountSelectorValue::Matches {
465 values: values.clone(),
466 },
467 CountSelector::Members(set) => CountSelectorValue::Members { set: set.clone() },
468 CountSelector::Distinct => CountSelectorValue::Distinct,
469 };
470 Some(ViolationKind::Count {
471 entries: entries.iter().map(argument).collect(),
472 selector,
473 calculated,
474 supplied: argument(count),
475 relation: *relation,
476 code: *code,
477 condition: self.condition_value(condition, values),
478 })
479 }
480 Counting::Cardinality {
481 entries,
482 cover,
483 counts,
484 closed,
485 } => {
486 let concrete = integers(entries, values).expect("available cardinality inputs");
487 let mut failures = Vec::new();
488 for (position, &value) in cover.iter().enumerate() {
489 let calculated = occurrence(&concrete, value)
490 .map_err(|message| constraint.execution_error(message))?;
491 let (supplied, lower, upper, valid) = match counts {
492 CardinalityCounts::Exact(counts) => {
493 let count = argument(&counts[position]);
494 let valid = count.value.integer() == calculated;
495 (Some(count), None, None, valid)
496 }
497 CardinalityCounts::Bounds { lower, upper } => (
498 None,
499 Some(lower[position]),
500 Some(upper[position]),
501 lower[position] <= calculated && calculated <= upper[position],
502 ),
503 };
504 if !valid {
505 failures.push(CountPosition {
506 position: position + 1,
507 cover: value,
508 calculated,
509 supplied,
510 lower,
511 upper,
512 });
513 }
514 }
515 let outside_cover: Vec<_> = concrete
516 .iter()
517 .enumerate()
518 .filter_map(|(index, value)| {
519 (*closed && !cover.contains(value)).then_some(index + 1)
520 })
521 .collect();
522 (!failures.is_empty() || !outside_cover.is_empty()).then(|| {
523 ViolationKind::Cardinality {
524 entries: entries.iter().map(argument).collect(),
525 counts: failures,
526 outside_cover,
527 closed: *closed,
528 }
529 })
530 }
531 Counting::Window {
532 entries,
533 membership,
534 length,
535 lower,
536 upper,
537 } => {
538 let matches: Vec<_> = entries
539 .iter()
540 .map(|entry| match membership {
541 Value::IntegerSet(set) => {
542 set.contains(entry.value(values).unwrap().integer())
543 }
544 Value::Boolean(member) => entry.value(values).unwrap().boolean() == *member,
545 _ => unreachable!("admitted window membership"),
546 })
547 .collect();
548 let mut windows = Vec::new();
549 for (position, window) in matches.windows(*length as usize).enumerate() {
550 let calculated = i64::try_from(window.iter().filter(|&&member| member).count())
551 .map_err(|_| {
552 constraint.execution_error("checked i64 overflow in counting aggregate")
553 })?;
554 if calculated < *lower || calculated > *upper {
555 windows.push(WindowCount {
556 position: position + 1,
557 calculated,
558 });
559 }
560 }
561 (!windows.is_empty()).then(|| ViolationKind::CountWindows {
562 entries: entries.iter().map(argument).collect(),
563 membership: membership.clone(),
564 length: *length,
565 lower: *lower,
566 upper: *upper,
567 windows,
568 })
569 }
570 })
571 }
572}