1use std::collections::{BTreeMap, BTreeSet};
4
5use serde::Serialize;
6
7use crate::{
8 CascadeKey, CascadeLevel, FirstWitnessErrorV0, FirstWitnessManagerConfigV0,
9 FirstWitnessManagerV0, GuardedCascadeCandidateV0, GuardedCascadeFragmentV0,
10 GuardedCascadeSpecificityExactnessV0, LayerOrdinal, Specificity,
11 at_rule_nesting_order_for_fragment_v0, build_guarded_cascade_winner_v0,
12 evaluate_guarded_cascade_winner_v0, normalized_layer_rank,
13};
14
15pub const GUARDED_CASCADE_ROBUSTNESS_PRODUCT_V0: &str =
16 "omena-cascade.guarded-winner-robustness-radius";
17pub const GUARDED_CASCADE_ROBUSTNESS_CALIBRATION_STAGE_V0: &str = "schemaOnlyUncalibrated";
18pub const GUARDED_CASCADE_ROBUSTNESS_MIN_PLUS_DUPLICATION_REASON_V0: &str = "the decision diagram lives in omena-cascade while the reusable tropical semiring lives downstream in omena-abstract-value, so this finite min-plus fold avoids a dependency cycle";
19pub const MAX_GUARDED_CASCADE_PERTURBATIONS_V0: usize = 20;
20
21#[non_exhaustive]
22#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize)]
23#[serde(rename_all = "camelCase")]
24pub enum GuardedCascadePerturbationKindV0 {
25 AddClass,
26 RemoveClass,
27 ToggleImportant,
28 IncreaseSpecificity,
29 MoveLayer,
30 MoveSourceOrder,
31 ToggleCondition,
32}
33
34#[non_exhaustive]
35#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
36#[serde(
37 tag = "kind",
38 rename_all = "camelCase",
39 rename_all_fields = "camelCase"
40)]
41pub enum GuardedCascadePerturbationV0 {
42 AddClass { declaration_id: u32 },
43 RemoveClass { declaration_id: u32 },
44 ToggleImportant { declaration_id: u32 },
45 IncreaseSpecificity { declaration_id: u32 },
46 MoveLayer { declaration_id: u32 },
47 MoveSourceOrder { declaration_id: u32 },
48 ToggleCondition { atom: String },
49}
50
51impl GuardedCascadePerturbationV0 {
52 pub const fn kind(&self) -> GuardedCascadePerturbationKindV0 {
53 match self {
54 Self::AddClass { .. } => GuardedCascadePerturbationKindV0::AddClass,
55 Self::RemoveClass { .. } => GuardedCascadePerturbationKindV0::RemoveClass,
56 Self::ToggleImportant { .. } => GuardedCascadePerturbationKindV0::ToggleImportant,
57 Self::IncreaseSpecificity { .. } => {
58 GuardedCascadePerturbationKindV0::IncreaseSpecificity
59 }
60 Self::MoveLayer { .. } => GuardedCascadePerturbationKindV0::MoveLayer,
61 Self::MoveSourceOrder { .. } => GuardedCascadePerturbationKindV0::MoveSourceOrder,
62 Self::ToggleCondition { .. } => GuardedCascadePerturbationKindV0::ToggleCondition,
63 }
64 }
65}
66
67#[non_exhaustive]
68#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
69#[serde(rename_all = "camelCase")]
70pub struct GuardedCascadePerturbationCostModelV0 {
71 pub add_class: u32,
72 pub remove_class: u32,
73 pub toggle_important: u32,
74 pub increase_specificity: u32,
75 pub move_layer: u32,
76 pub move_source_order: u32,
77 pub toggle_condition: u32,
78 pub calibration_stage: &'static str,
79 pub public_safety_claim_ready: bool,
80}
81
82impl GuardedCascadePerturbationCostModelV0 {
83 pub const fn unit_cost_v0() -> Self {
84 Self {
85 add_class: 1,
86 remove_class: 1,
87 toggle_important: 1,
88 increase_specificity: 1,
89 move_layer: 1,
90 move_source_order: 1,
91 toggle_condition: 1,
92 calibration_stage: GUARDED_CASCADE_ROBUSTNESS_CALIBRATION_STAGE_V0,
93 public_safety_claim_ready: false,
94 }
95 }
96
97 pub const fn cost(&self, kind: GuardedCascadePerturbationKindV0) -> u32 {
98 match kind {
99 GuardedCascadePerturbationKindV0::AddClass => self.add_class,
100 GuardedCascadePerturbationKindV0::RemoveClass => self.remove_class,
101 GuardedCascadePerturbationKindV0::ToggleImportant => self.toggle_important,
102 GuardedCascadePerturbationKindV0::IncreaseSpecificity => self.increase_specificity,
103 GuardedCascadePerturbationKindV0::MoveLayer => self.move_layer,
104 GuardedCascadePerturbationKindV0::MoveSourceOrder => self.move_source_order,
105 GuardedCascadePerturbationKindV0::ToggleCondition => self.toggle_condition,
106 }
107 }
108}
109
110pub const fn guarded_cascade_perturbation_cost_model_v0() -> GuardedCascadePerturbationCostModelV0 {
111 GuardedCascadePerturbationCostModelV0::unit_cost_v0()
112}
113
114#[non_exhaustive]
115#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
116#[serde(tag = "kind", content = "cost", rename_all = "camelCase")]
117pub enum GuardedCascadeRobustnessRadiusValueV0 {
118 Finite(u32),
119 Infinity,
120}
121
122#[non_exhaustive]
123#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
124#[serde(rename_all = "camelCase")]
125pub struct GuardedCascadeConditionImplicationV0 {
126 pub antecedent_atom: String,
127 pub consequent_atom: String,
128}
129
130#[non_exhaustive]
131#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
132#[serde(rename_all = "camelCase")]
133pub struct GuardedCascadeRealisabilityModelV0 {
134 pub derivation: &'static str,
135 pub always_false_atoms: Vec<String>,
136 pub implications: Vec<GuardedCascadeConditionImplicationV0>,
137}
138
139#[non_exhaustive]
140#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
141#[serde(rename_all = "camelCase")]
142pub struct GuardedCascadeRobustnessRadiusV0 {
143 pub schema_version: &'static str,
144 pub product: &'static str,
145 pub baseline_winner_declaration_id: u32,
146 pub radius: GuardedCascadeRobustnessRadiusValueV0,
147 pub witness: Vec<GuardedCascadePerturbationV0>,
148 pub evaluated_perturbation_set_count: usize,
149 pub verified_below_radius_perturbation_set_count: usize,
150 pub excluded_unrealisable_assignment_count: usize,
151 pub realisability: GuardedCascadeRealisabilityModelV0,
152 pub calibration_stage: &'static str,
153 pub public_safety_claim_ready: bool,
154 pub min_plus_duplication_reason: &'static str,
155}
156
157#[non_exhaustive]
158#[derive(Debug)]
159pub enum GuardedCascadeRobustnessErrorV0 {
160 FirstWitness(FirstWitnessErrorV0),
161 MissingBaselineWinner,
162 AssignmentCardinalityMismatch {
163 expected: usize,
164 observed: usize,
165 },
166 PerturbationCapacityExceeded {
167 observed: usize,
168 capacity: usize,
169 },
170 ZeroPerturbationCost {
171 kind: GuardedCascadePerturbationKindV0,
172 },
173}
174
175impl From<FirstWitnessErrorV0> for GuardedCascadeRobustnessErrorV0 {
176 fn from(value: FirstWitnessErrorV0) -> Self {
177 Self::FirstWitness(value)
178 }
179}
180
181impl std::fmt::Display for GuardedCascadeRobustnessErrorV0 {
182 fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
183 match self {
184 Self::FirstWitness(error) => error.fmt(formatter),
185 Self::MissingBaselineWinner => formatter
186 .write_str("guarded cascade robustness requires a baseline winner declaration"),
187 Self::AssignmentCardinalityMismatch { expected, observed } => write!(
188 formatter,
189 "guarded cascade assignment cardinality mismatch: expected {expected}, observed {observed}"
190 ),
191 Self::PerturbationCapacityExceeded { observed, capacity } => write!(
192 formatter,
193 "guarded cascade perturbation capacity exceeded: observed {observed}, capacity {capacity}"
194 ),
195 Self::ZeroPerturbationCost { kind } => {
196 write!(
197 formatter,
198 "guarded cascade perturbation {kind:?} has zero cost"
199 )
200 }
201 }
202 }
203}
204
205impl std::error::Error for GuardedCascadeRobustnessErrorV0 {}
206
207#[derive(Clone)]
208struct EnumeratedPerturbationV0 {
209 perturbation: GuardedCascadePerturbationV0,
210 candidate_index: Option<usize>,
211 variable_index: Option<usize>,
212 cost: u32,
213}
214
215pub fn compute_guarded_cascade_robustness_radius_v0(
216 fragment: &GuardedCascadeFragmentV0<CascadeKey>,
217 assignment: &[bool],
218 cost_model: &GuardedCascadePerturbationCostModelV0,
219) -> Result<GuardedCascadeRobustnessRadiusV0, GuardedCascadeRobustnessErrorV0> {
220 let order = at_rule_nesting_order_for_fragment_v0(fragment)?;
221 if assignment.len() != order.atoms().len() {
222 return Err(
223 GuardedCascadeRobustnessErrorV0::AssignmentCardinalityMismatch {
224 expected: order.atoms().len(),
225 observed: assignment.len(),
226 },
227 );
228 }
229 let baseline_winner = evaluate_fragment_winner(fragment, order.clone(), assignment)?
230 .ok_or(GuardedCascadeRobustnessErrorV0::MissingBaselineWinner)?;
231 let realisability = derive_guarded_cascade_realisability_v0(order.atoms());
232 #[cfg(test)]
233 let realisability = if std::env::var_os("OMENA_G122_INJECT_IGNORE_REALISABILITY").is_some() {
234 GuardedCascadeRealisabilityModelV0 {
235 derivation: realisability.derivation,
236 always_false_atoms: Vec::new(),
237 implications: Vec::new(),
238 }
239 } else {
240 realisability
241 };
242 let perturbations = enumerate_perturbations(fragment, &order, cost_model)?;
243 if perturbations.len() > MAX_GUARDED_CASCADE_PERTURBATIONS_V0 {
244 return Err(
245 GuardedCascadeRobustnessErrorV0::PerturbationCapacityExceeded {
246 observed: perturbations.len(),
247 capacity: MAX_GUARDED_CASCADE_PERTURBATIONS_V0,
248 },
249 );
250 }
251
252 let mut best: Option<(u32, Vec<GuardedCascadePerturbationV0>)> = None;
253 let mut evaluated_perturbation_set_count = 0usize;
254 let mut preserving_costs = Vec::new();
255 let mut excluded_unrealisable_assignment_count = 0usize;
256 let upper = 1u64 << perturbations.len();
257 for mask in 1..upper {
258 let cost = perturbations
259 .iter()
260 .enumerate()
261 .filter(|(index, _)| mask & (1u64 << index) != 0)
262 .map(|(_, perturbation)| perturbation.cost)
263 .sum::<u32>();
264 if best.as_ref().is_some_and(|(best, _)| cost > *best) {
265 continue;
266 }
267 let (candidate_keys, candidate_assignment, witness) =
268 apply_perturbation_set(fragment, assignment, perturbations.as_slice(), mask);
269 if !assignment_is_realisable(
270 order.atoms(),
271 candidate_assignment.as_slice(),
272 &realisability,
273 ) {
274 excluded_unrealisable_assignment_count += 1;
275 continue;
276 }
277 let Some(candidate_fragment) = fragment_with_keys(fragment, candidate_keys) else {
278 continue;
279 };
280 evaluated_perturbation_set_count += 1;
281 let winner = evaluate_fragment_winner(
282 &candidate_fragment,
283 order.clone(),
284 candidate_assignment.as_slice(),
285 )?;
286 if winner != Some(baseline_winner) {
287 if best.as_ref().is_none_or(|(best, _)| cost < *best) {
288 best = Some((cost, witness));
289 }
290 } else {
291 preserving_costs.push(cost);
292 }
293 }
294
295 let (radius, witness) = best.map_or(
296 (GuardedCascadeRobustnessRadiusValueV0::Infinity, Vec::new()),
297 |(cost, witness)| (GuardedCascadeRobustnessRadiusValueV0::Finite(cost), witness),
298 );
299 let verified_below_radius_perturbation_set_count = preserving_costs
300 .into_iter()
301 .filter(|cost| match radius {
302 GuardedCascadeRobustnessRadiusValueV0::Finite(radius) => *cost < radius,
303 GuardedCascadeRobustnessRadiusValueV0::Infinity => true,
304 })
305 .count();
306 Ok(GuardedCascadeRobustnessRadiusV0 {
307 schema_version: "0",
308 product: GUARDED_CASCADE_ROBUSTNESS_PRODUCT_V0,
309 baseline_winner_declaration_id: baseline_winner,
310 radius,
311 witness,
312 evaluated_perturbation_set_count,
313 verified_below_radius_perturbation_set_count,
314 excluded_unrealisable_assignment_count,
315 realisability,
316 calibration_stage: cost_model.calibration_stage,
317 public_safety_claim_ready: cost_model.public_safety_claim_ready,
318 min_plus_duplication_reason: GUARDED_CASCADE_ROBUSTNESS_MIN_PLUS_DUPLICATION_REASON_V0,
319 })
320}
321
322fn evaluate_fragment_winner(
323 fragment: &GuardedCascadeFragmentV0<CascadeKey>,
324 order: crate::VariableOrderRegistrationV0,
325 assignment: &[bool],
326) -> Result<Option<u32>, GuardedCascadeRobustnessErrorV0> {
327 let mut manager = FirstWitnessManagerV0::new(order, FirstWitnessManagerConfigV0::default());
328 let root = build_guarded_cascade_winner_v0(&mut manager, fragment)?;
329 Ok(evaluate_guarded_cascade_winner_v0(
330 &manager, root, assignment,
331 )?)
332}
333
334fn enumerate_perturbations(
335 fragment: &GuardedCascadeFragmentV0<CascadeKey>,
336 order: &crate::VariableOrderRegistrationV0,
337 cost_model: &GuardedCascadePerturbationCostModelV0,
338) -> Result<Vec<EnumeratedPerturbationV0>, GuardedCascadeRobustnessErrorV0> {
339 let mut result = Vec::new();
340 for (candidate_index, candidate) in fragment.candidates().iter().enumerate() {
341 let declaration_id = candidate.declaration_id();
342 let key = *candidate.cascade_key();
343 for perturbation in [
344 GuardedCascadePerturbationV0::AddClass { declaration_id },
345 GuardedCascadePerturbationV0::IncreaseSpecificity { declaration_id },
346 GuardedCascadePerturbationV0::MoveSourceOrder { declaration_id },
347 ] {
348 push_enumerated(
349 &mut result,
350 perturbation,
351 Some(candidate_index),
352 None,
353 cost_model,
354 )?;
355 }
356 if key.specificity.classes > 0 {
357 push_enumerated(
358 &mut result,
359 GuardedCascadePerturbationV0::RemoveClass { declaration_id },
360 Some(candidate_index),
361 None,
362 cost_model,
363 )?;
364 }
365 if toggle_important_level(key.level).is_some() {
366 push_enumerated(
367 &mut result,
368 GuardedCascadePerturbationV0::ToggleImportant { declaration_id },
369 Some(candidate_index),
370 None,
371 cost_model,
372 )?;
373 }
374 if moved_layer_rank(key).is_some() {
375 push_enumerated(
376 &mut result,
377 GuardedCascadePerturbationV0::MoveLayer { declaration_id },
378 Some(candidate_index),
379 None,
380 cost_model,
381 )?;
382 }
383 }
384 for (variable_index, atom) in order.atoms().iter().enumerate() {
385 push_enumerated(
386 &mut result,
387 GuardedCascadePerturbationV0::ToggleCondition { atom: atom.clone() },
388 None,
389 Some(variable_index),
390 cost_model,
391 )?;
392 }
393 Ok(result)
394}
395
396fn push_enumerated(
397 result: &mut Vec<EnumeratedPerturbationV0>,
398 perturbation: GuardedCascadePerturbationV0,
399 candidate_index: Option<usize>,
400 variable_index: Option<usize>,
401 cost_model: &GuardedCascadePerturbationCostModelV0,
402) -> Result<(), GuardedCascadeRobustnessErrorV0> {
403 let cost = cost_model.cost(perturbation.kind());
404 #[cfg(test)]
405 let cost = if std::env::var_os("OMENA_G122_INJECT_IGNORE_RADIUS_COST_MODEL").is_some() {
406 1
407 } else {
408 cost
409 };
410 if cost == 0 {
411 return Err(GuardedCascadeRobustnessErrorV0::ZeroPerturbationCost {
412 kind: perturbation.kind(),
413 });
414 }
415 result.push(EnumeratedPerturbationV0 {
416 perturbation,
417 candidate_index,
418 variable_index,
419 cost,
420 });
421 Ok(())
422}
423
424fn apply_perturbation_set(
425 fragment: &GuardedCascadeFragmentV0<CascadeKey>,
426 assignment: &[bool],
427 perturbations: &[EnumeratedPerturbationV0],
428 mask: u64,
429) -> (
430 Vec<CascadeKey>,
431 Vec<bool>,
432 Vec<GuardedCascadePerturbationV0>,
433) {
434 let mut keys = fragment
435 .candidates()
436 .iter()
437 .map(|candidate| *candidate.cascade_key())
438 .collect::<Vec<_>>();
439 let mut assignment = assignment.to_vec();
440 let mut witness = Vec::new();
441 for (index, perturbation) in perturbations.iter().enumerate() {
442 if mask & (1u64 << index) == 0 {
443 continue;
444 }
445 if let Some(candidate_index) = perturbation.candidate_index {
446 apply_key_perturbation(&mut keys[candidate_index], &perturbation.perturbation);
447 }
448 if let Some(variable_index) = perturbation.variable_index {
449 assignment[variable_index] = !assignment[variable_index];
450 }
451 witness.push(perturbation.perturbation.clone());
452 }
453 (keys, assignment, witness)
454}
455
456fn apply_key_perturbation(key: &mut CascadeKey, perturbation: &GuardedCascadePerturbationV0) {
457 #[cfg(test)]
458 if std::env::var_os("OMENA_G122_INJECT_DISABLE_KEY_PERTURBATIONS").is_some() {
459 return;
460 }
461 match perturbation {
462 GuardedCascadePerturbationV0::AddClass { .. }
463 | GuardedCascadePerturbationV0::IncreaseSpecificity { .. } => {
464 key.specificity = Specificity::new(
465 key.specificity.ids,
466 key.specificity.classes.saturating_add(1),
467 key.specificity.elements,
468 );
469 }
470 GuardedCascadePerturbationV0::RemoveClass { .. } => {
471 key.specificity = Specificity::new(
472 key.specificity.ids,
473 key.specificity.classes.saturating_sub(1),
474 key.specificity.elements,
475 );
476 }
477 GuardedCascadePerturbationV0::ToggleImportant { .. } => {
478 if let Some(level) = toggle_important_level(key.level) {
479 key.level = level;
480 }
481 }
482 GuardedCascadePerturbationV0::MoveLayer { .. } => {
483 if let Some(layer_rank) = moved_layer_rank(*key) {
484 key.layer_rank = layer_rank;
485 }
486 }
487 GuardedCascadePerturbationV0::MoveSourceOrder { .. } => {
488 key.source_order = if key.source_order == u32::MAX {
489 0
490 } else {
491 u32::MAX
492 };
493 }
494 GuardedCascadePerturbationV0::ToggleCondition { .. } => {}
495 }
496}
497
498fn toggle_important_level(level: CascadeLevel) -> Option<CascadeLevel> {
499 match level {
500 CascadeLevel::UserAgentNormal => Some(CascadeLevel::UserAgentImportant),
501 CascadeLevel::UserNormal => Some(CascadeLevel::UserImportant),
502 CascadeLevel::AuthorNormal => Some(CascadeLevel::AuthorImportant),
503 CascadeLevel::InlineNormal => Some(CascadeLevel::InlineImportant),
504 CascadeLevel::AuthorImportant => Some(CascadeLevel::AuthorNormal),
505 CascadeLevel::InlineImportant => Some(CascadeLevel::InlineNormal),
506 CascadeLevel::UserImportant => Some(CascadeLevel::UserNormal),
507 CascadeLevel::UserAgentImportant => Some(CascadeLevel::UserAgentNormal),
508 CascadeLevel::Animation | CascadeLevel::Transition => None,
509 }
510}
511
512fn moved_layer_rank(key: CascadeKey) -> Option<crate::LayerRank> {
513 let important = matches!(
514 key.level,
515 CascadeLevel::AuthorImportant
516 | CascadeLevel::InlineImportant
517 | CascadeLevel::UserImportant
518 | CascadeLevel::UserAgentImportant
519 );
520 let rank = key.layer_rank.get();
521 let ordinal = if important {
522 if rank == i32::MIN {
523 0
524 } else {
525 rank.checked_neg()?.saturating_add(1)
526 }
527 } else if rank == i32::MAX {
528 0
529 } else {
530 rank.saturating_add(1)
531 };
532 LayerOrdinal::new(ordinal).map(|ordinal| normalized_layer_rank(important, Some(ordinal)))
533}
534
535fn fragment_with_keys(
536 fragment: &GuardedCascadeFragmentV0<CascadeKey>,
537 keys: Vec<CascadeKey>,
538) -> Option<GuardedCascadeFragmentV0<CascadeKey>> {
539 let candidates = fragment
540 .candidates()
541 .iter()
542 .zip(keys)
543 .map(|(candidate, key)| {
544 GuardedCascadeCandidateV0::new(
545 candidate.declaration_id(),
546 candidate.element_signature(),
547 candidate.property(),
548 key,
549 GuardedCascadeSpecificityExactnessV0::Exact,
550 candidate.scope_proximity(),
551 candidate.conditions().to_vec(),
552 )
553 });
554 GuardedCascadeFragmentV0::admit(fragment.condition_alphabet().iter().cloned(), candidates).ok()
555}
556
557fn derive_guarded_cascade_realisability_v0(atoms: &[String]) -> GuardedCascadeRealisabilityModelV0 {
558 let parsed = atoms
559 .iter()
560 .filter_map(|atom| parse_width_bounds(atom).map(|bounds| (atom, bounds)))
561 .collect::<Vec<_>>();
562 let always_false_atoms = parsed
563 .iter()
564 .filter(|(_, bounds)| {
565 bounds.min.is_some()
566 && bounds.max.is_some()
567 && bounds.min_unit == bounds.max_unit
568 && bounds.min > bounds.max
569 })
570 .map(|(atom, _)| (*atom).clone())
571 .collect::<Vec<_>>();
572 let mut implications = BTreeSet::new();
573 for (antecedent_atom, antecedent) in &parsed {
574 let (Some(antecedent_min), Some(antecedent_unit)) =
575 (antecedent.min, antecedent.min_unit.as_deref())
576 else {
577 continue;
578 };
579 for (consequent_atom, consequent) in &parsed {
580 let (Some(consequent_min), Some(consequent_unit)) =
581 (consequent.min, consequent.min_unit.as_deref())
582 else {
583 continue;
584 };
585 if antecedent_atom != consequent_atom
586 && antecedent_unit == consequent_unit
587 && antecedent_min >= consequent_min
588 {
589 implications.insert(((*antecedent_atom).clone(), (*consequent_atom).clone()));
590 }
591 }
592 }
593 GuardedCascadeRealisabilityModelV0 {
594 derivation: "sameUnitWidthBoundaryMonotonicity",
595 always_false_atoms,
596 implications: implications
597 .into_iter()
598 .map(
599 |(antecedent_atom, consequent_atom)| GuardedCascadeConditionImplicationV0 {
600 antecedent_atom,
601 consequent_atom,
602 },
603 )
604 .collect(),
605 }
606}
607
608fn assignment_is_realisable(
609 atoms: &[String],
610 assignment: &[bool],
611 model: &GuardedCascadeRealisabilityModelV0,
612) -> bool {
613 let values = atoms
614 .iter()
615 .cloned()
616 .zip(assignment.iter().copied())
617 .collect::<BTreeMap<_, _>>();
618 if model
619 .always_false_atoms
620 .iter()
621 .any(|atom| values.get(atom).copied().unwrap_or(false))
622 {
623 return false;
624 }
625 model.implications.iter().all(|implication| {
626 !values
627 .get(implication.antecedent_atom.as_str())
628 .copied()
629 .unwrap_or(false)
630 || values
631 .get(implication.consequent_atom.as_str())
632 .copied()
633 .unwrap_or(false)
634 })
635}
636
637#[derive(Default)]
638struct WidthBoundsV0 {
639 min: Option<u32>,
640 min_unit: Option<String>,
641 max: Option<u32>,
642 max_unit: Option<String>,
643}
644
645fn parse_width_bounds(atom: &str) -> Option<WidthBoundsV0> {
646 let lower = atom.to_ascii_lowercase();
647 let mut bounds = WidthBoundsV0::default();
648 if let Some((value, unit)) = numeric_boundary(&lower, "min-width") {
649 bounds.min = Some(value);
650 bounds.min_unit = Some(unit);
651 }
652 if let Some((value, unit)) = numeric_boundary(&lower, "max-width") {
653 bounds.max = Some(value);
654 bounds.max_unit = Some(unit);
655 }
656 (bounds.min.is_some() || bounds.max.is_some()).then_some(bounds)
657}
658
659fn numeric_boundary(source: &str, name: &str) -> Option<(u32, String)> {
660 let start = source.find(name)? + name.len();
661 let tail = source.get(start..)?.trim_start_matches([' ', ':']);
662 let digits = tail
663 .chars()
664 .take_while(|character| character.is_ascii_digit())
665 .collect::<String>();
666 let value = digits.parse().ok()?;
667 let unit = tail
668 .get(digits.len()..)?
669 .chars()
670 .take_while(|character| character.is_ascii_alphabetic() || *character == '%')
671 .collect::<String>();
672 (!unit.is_empty()).then_some((value, unit))
673}
674
675#[cfg(test)]
676mod tests {
677 use crate::{GuardedCascadeConditionAtomV0, GuardedCascadeSpecificityExactnessV0};
678
679 use super::*;
680
681 fn candidate(
682 declaration_id: u32,
683 source_order: u32,
684 condition: Option<&str>,
685 ) -> GuardedCascadeCandidateV0<CascadeKey> {
686 GuardedCascadeCandidateV0::new(
687 declaration_id,
688 ".a",
689 "color",
690 CascadeKey::new(
691 CascadeLevel::AuthorNormal,
692 normalized_layer_rank(false, LayerOrdinal::new(0)),
693 0,
694 Specificity::new(0, 1, 0),
695 source_order,
696 ),
697 GuardedCascadeSpecificityExactnessV0::Exact,
698 0,
699 condition
700 .map(|condition| vec![GuardedCascadeConditionAtomV0::media(condition, [0], true)])
701 .unwrap_or_default(),
702 )
703 }
704
705 fn candidate_with_key(
706 declaration_id: u32,
707 key: CascadeKey,
708 ) -> GuardedCascadeCandidateV0<CascadeKey> {
709 GuardedCascadeCandidateV0::new(
710 declaration_id,
711 ".a",
712 "color",
713 key,
714 GuardedCascadeSpecificityExactnessV0::Exact,
715 0,
716 Vec::new(),
717 )
718 }
719
720 fn key(
721 level: CascadeLevel,
722 layer_ordinal: Option<i32>,
723 classes: u32,
724 source_order: u32,
725 ) -> CascadeKey {
726 CascadeKey::new(
727 level,
728 normalized_layer_rank(false, layer_ordinal.and_then(LayerOrdinal::new)),
729 0,
730 Specificity::new(0, classes, 0),
731 source_order,
732 )
733 }
734
735 fn isolated_cost_model(
736 kind: GuardedCascadePerturbationKindV0,
737 ) -> GuardedCascadePerturbationCostModelV0 {
738 let mut model = GuardedCascadePerturbationCostModelV0 {
739 add_class: 11,
740 remove_class: 11,
741 toggle_important: 11,
742 increase_specificity: 11,
743 move_layer: 11,
744 move_source_order: 11,
745 toggle_condition: 11,
746 calibration_stage: GUARDED_CASCADE_ROBUSTNESS_CALIBRATION_STAGE_V0,
747 public_safety_claim_ready: false,
748 };
749 match kind {
750 GuardedCascadePerturbationKindV0::AddClass => model.add_class = 1,
751 GuardedCascadePerturbationKindV0::RemoveClass => model.remove_class = 1,
752 GuardedCascadePerturbationKindV0::ToggleImportant => model.toggle_important = 1,
753 GuardedCascadePerturbationKindV0::IncreaseSpecificity => {
754 model.increase_specificity = 1;
755 }
756 GuardedCascadePerturbationKindV0::MoveLayer => model.move_layer = 1,
757 GuardedCascadePerturbationKindV0::MoveSourceOrder => model.move_source_order = 1,
758 GuardedCascadePerturbationKindV0::ToggleCondition => model.toggle_condition = 1,
759 }
760 model
761 }
762
763 fn perturbation(
764 kind: GuardedCascadePerturbationKindV0,
765 declaration_id: u32,
766 ) -> GuardedCascadePerturbationV0 {
767 match kind {
768 GuardedCascadePerturbationKindV0::AddClass => {
769 GuardedCascadePerturbationV0::AddClass { declaration_id }
770 }
771 GuardedCascadePerturbationKindV0::RemoveClass => {
772 GuardedCascadePerturbationV0::RemoveClass { declaration_id }
773 }
774 GuardedCascadePerturbationKindV0::ToggleImportant => {
775 GuardedCascadePerturbationV0::ToggleImportant { declaration_id }
776 }
777 GuardedCascadePerturbationKindV0::IncreaseSpecificity => {
778 GuardedCascadePerturbationV0::IncreaseSpecificity { declaration_id }
779 }
780 GuardedCascadePerturbationKindV0::MoveLayer => {
781 GuardedCascadePerturbationV0::MoveLayer { declaration_id }
782 }
783 GuardedCascadePerturbationKindV0::MoveSourceOrder => {
784 GuardedCascadePerturbationV0::MoveSourceOrder { declaration_id }
785 }
786 GuardedCascadePerturbationKindV0::ToggleCondition => {
787 GuardedCascadePerturbationV0::ToggleCondition {
788 atom: String::new(),
789 }
790 }
791 }
792 }
793
794 fn fragment(
795 condition: &str,
796 ) -> Result<GuardedCascadeFragmentV0<CascadeKey>, crate::GuardedCascadeFragmentRefusalV0> {
797 GuardedCascadeFragmentV0::admit(
798 [condition],
799 [candidate(0, 0, None), candidate(1, 1, Some(condition))],
800 )
801 }
802
803 #[test]
804 fn radius_computes_named_cheapest_flip_and_moves_with_the_cost_table()
805 -> Result<(), Box<dyn std::error::Error>> {
806 let condition = "@media (min-width: 1px)";
807 let fragment = fragment(condition)?;
808 let unit = compute_guarded_cascade_robustness_radius_v0(
809 &fragment,
810 &[false],
811 &guarded_cascade_perturbation_cost_model_v0(),
812 )?;
813 assert_eq!(
814 unit.radius,
815 GuardedCascadeRobustnessRadiusValueV0::Finite(1)
816 );
817 assert_eq!(
818 unit.witness,
819 vec![GuardedCascadePerturbationV0::ToggleCondition {
820 atom: condition.to_string(),
821 }]
822 );
823 assert_eq!(unit.calibration_stage, "schemaOnlyUncalibrated");
824 assert!(!unit.public_safety_claim_ready);
825
826 let mut changed_cost = guarded_cascade_perturbation_cost_model_v0();
827 changed_cost.toggle_condition = 7;
828 let changed =
829 compute_guarded_cascade_robustness_radius_v0(&fragment, &[false], &changed_cost)?;
830 assert_eq!(
831 changed.radius,
832 GuardedCascadeRobustnessRadiusValueV0::Finite(7)
833 );
834 Ok(())
835 }
836
837 #[test]
838 fn every_key_perturbation_kind_has_a_cheapest_winner_flip()
839 -> Result<(), Box<dyn std::error::Error>> {
840 let ordinary_winner = key(CascadeLevel::AuthorNormal, Some(0), 2, 0);
841 let ordinary_challenger = key(CascadeLevel::AuthorNormal, Some(0), 1, 1);
842 let cases = [
843 (
844 GuardedCascadePerturbationKindV0::AddClass,
845 ordinary_winner,
846 ordinary_challenger,
847 1,
848 ),
849 (
850 GuardedCascadePerturbationKindV0::RemoveClass,
851 ordinary_winner,
852 ordinary_challenger,
853 0,
854 ),
855 (
856 GuardedCascadePerturbationKindV0::ToggleImportant,
857 ordinary_winner,
858 ordinary_challenger,
859 1,
860 ),
861 (
862 GuardedCascadePerturbationKindV0::IncreaseSpecificity,
863 ordinary_winner,
864 ordinary_challenger,
865 1,
866 ),
867 (
868 GuardedCascadePerturbationKindV0::MoveLayer,
869 key(CascadeLevel::AuthorNormal, None, 1, 0),
870 key(CascadeLevel::AuthorNormal, Some(0), 1, 1),
871 0,
872 ),
873 (
874 GuardedCascadePerturbationKindV0::MoveSourceOrder,
875 key(CascadeLevel::AuthorNormal, Some(0), 1, 1),
876 key(CascadeLevel::AuthorNormal, Some(0), 1, 0),
877 1,
878 ),
879 ];
880 let mut observations = Vec::new();
881 for (kind, winner, challenger, target_declaration_id) in cases {
882 let fragment = GuardedCascadeFragmentV0::admit(
883 std::iter::empty::<&str>(),
884 [
885 candidate_with_key(0, winner),
886 candidate_with_key(1, challenger),
887 ],
888 )?;
889 let result = compute_guarded_cascade_robustness_radius_v0(
890 &fragment,
891 &[],
892 &isolated_cost_model(kind),
893 )?;
894 assert_eq!(
895 result.radius,
896 GuardedCascadeRobustnessRadiusValueV0::Finite(1),
897 "{kind:?} must provide a real cheapest winner flip"
898 );
899 assert_eq!(
900 result.witness,
901 vec![perturbation(kind, target_declaration_id)],
902 "{kind:?} must name the declaration whose key crosses the winner boundary"
903 );
904 observations.push((kind, result.baseline_winner_declaration_id, result.witness));
905 }
906 eprintln!("S6_KEY_PERTURBATION_OBSERVATIONS={observations:?}");
907 Ok(())
908 }
909
910 #[test]
911 fn unrealisable_only_flip_has_infinite_radius() -> Result<(), Box<dyn std::error::Error>> {
912 let contradictory = "@media (min-width: 1200px) and (max-width: 768px)";
913 let fragment = fragment(contradictory)?;
914 let radius = compute_guarded_cascade_robustness_radius_v0(
915 &fragment,
916 &[false],
917 &guarded_cascade_perturbation_cost_model_v0(),
918 )?;
919 assert_eq!(
920 radius.radius,
921 GuardedCascadeRobustnessRadiusValueV0::Infinity
922 );
923 assert!(radius.witness.is_empty());
924 assert!(radius.excluded_unrealisable_assignment_count > 0);
925 assert!(radius.verified_below_radius_perturbation_set_count > 0);
926 assert_eq!(
927 radius.verified_below_radius_perturbation_set_count,
928 radius.evaluated_perturbation_set_count,
929 "every evaluated finite perturbation is below an infinite radius"
930 );
931 assert_eq!(
932 radius.realisability.always_false_atoms,
933 vec![contradictory.to_string()]
934 );
935 Ok(())
936 }
937
938 #[test]
939 fn every_realisable_perturbation_below_radius_preserves_the_winner()
940 -> Result<(), Box<dyn std::error::Error>> {
941 let condition = "@media (min-width: 1px)";
942 let fragment = fragment(condition)?;
943 let mut costs = guarded_cascade_perturbation_cost_model_v0();
944 costs.toggle_condition = 3;
945 let radius = compute_guarded_cascade_robustness_radius_v0(&fragment, &[false], &costs)?;
946 assert_eq!(
947 radius.radius,
948 GuardedCascadeRobustnessRadiusValueV0::Finite(3)
949 );
950 let order = at_rule_nesting_order_for_fragment_v0(&fragment)?;
951 let perturbations = enumerate_perturbations(&fragment, &order, &costs)?;
952 let baseline = independently_rederive_winner(&fragment, order.atoms(), &[false]);
953 let mut independently_verified = 0usize;
954 for mask in 1..(1u64 << perturbations.len()) {
955 let cost = perturbations
956 .iter()
957 .enumerate()
958 .filter(|(index, _)| mask & (1u64 << index) != 0)
959 .map(|(_, perturbation)| perturbation.cost)
960 .sum::<u32>();
961 if cost >= 3 {
962 continue;
963 }
964 let (keys, assignment, _) =
965 apply_perturbation_set(&fragment, &[false], &perturbations, mask);
966 if !assignment_is_realisable(order.atoms(), &assignment, &radius.realisability) {
967 continue;
968 }
969 let Some(candidate_fragment) = fragment_with_keys(&fragment, keys) else {
970 continue;
971 };
972 assert_eq!(
973 independently_rederive_winner(&candidate_fragment, order.atoms(), &assignment),
974 baseline,
975 "an independently rederived sub-radius path changed the winner"
976 );
977 independently_verified += 1;
978 }
979 assert!(independently_verified > 0);
980 assert_eq!(
981 radius.verified_below_radius_perturbation_set_count, independently_verified,
982 "the theorem-7 receipt must equal the independent sub-radius rederivation"
983 );
984 Ok(())
985 }
986
987 fn independently_rederive_winner(
988 fragment: &GuardedCascadeFragmentV0<CascadeKey>,
989 atoms: &[String],
990 assignment: &[bool],
991 ) -> Option<u32> {
992 let values = atoms
993 .iter()
994 .map(String::as_str)
995 .zip(assignment.iter().copied())
996 .collect::<BTreeMap<_, _>>();
997 fragment
998 .candidates()
999 .iter()
1000 .filter(|candidate| {
1001 candidate
1002 .conditions()
1003 .iter()
1004 .all(|condition| values.get(condition.atom()).copied().unwrap_or(false))
1005 })
1006 .max_by_key(|candidate| *candidate.cascade_key())
1007 .map(GuardedCascadeCandidateV0::declaration_id)
1008 }
1009}