shifty_opt/
deps.rs

1//! Polarity-aware shape dependency graph (Layer 4).
2//!
3//! An edge `A → B` means shape `A`'s satisfaction depends on shape `B`'s. The
4//! polarity is the *semantic* monotonicity of that dependency, not the surface
5//! `¬`: because our IR encodes `∀π.φ` as `∃≤0 π.¬φ`, a positive SHACL constraint
6//! looks syntactically negative, and two anti-monotone operators compose back to
7//! monotone (see `docs/03-recursion-semantics.md`).
8//!
9//! Per-node polarity:
10//! - `And` / `Or`        → children **positive** (monotone)
11//! - `Not`               → child **negative**
12//! - `Count` lower bound → qualifier **positive** (monotone in the qualifier)
13//! - `Count` upper bound → qualifier **negative** (anti-monotone)
14//!
15//! A `Count{min,max}` with both bounds emits both a positive and a negative edge
16//! to its qualifier (un-fusing), so a genuinely two-sided qualified count reads
17//! as non-monotone.
18
19use serde::{Deserialize, Serialize};
20use shifty_algebra::{Shape, ShapeArena, ShapeId};
21
22#[derive(Clone, Copy, PartialEq, Eq, Debug, Serialize, Deserialize)]
23pub enum Polarity {
24    Positive,
25    Negative,
26}
27
28impl Polarity {
29    /// `+1` / `-1`, so a cycle's net polarity is the product of its edges'.
30    pub fn sign(self) -> i8 {
31        match self {
32            Polarity::Positive => 1,
33            Polarity::Negative => -1,
34        }
35    }
36}
37
38#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
39pub struct DepEdge {
40    pub from: ShapeId,
41    pub to: ShapeId,
42    pub polarity: Polarity,
43}
44
45/// All polarity-annotated dependency edges of an arena.
46pub fn dependency_edges(arena: &ShapeArena) -> Vec<DepEdge> {
47    let mut edges = Vec::new();
48    for i in 0..arena.len() {
49        let from = ShapeId(i as u32);
50        match arena.get(from) {
51            Shape::Annotated { shape, .. } => edges.push(DepEdge {
52                from,
53                to: *shape,
54                polarity: Polarity::Positive,
55            }),
56            Shape::Not(c) => edges.push(DepEdge {
57                from,
58                to: *c,
59                polarity: Polarity::Negative,
60            }),
61            Shape::And(cs) | Shape::Or(cs) => {
62                for c in cs {
63                    edges.push(DepEdge {
64                        from,
65                        to: *c,
66                        polarity: Polarity::Positive,
67                    });
68                }
69            }
70            Shape::Count {
71                min,
72                max,
73                qualifier,
74                ..
75            } => {
76                if min.is_some() {
77                    edges.push(DepEdge {
78                        from,
79                        to: *qualifier,
80                        polarity: Polarity::Positive,
81                    });
82                }
83                if max.is_some() {
84                    edges.push(DepEdge {
85                        from,
86                        to: *qualifier,
87                        polarity: Polarity::Negative,
88                    });
89                }
90            }
91            Shape::Expression(e) => {
92                // A `Filter` inside the expression keeps inputs satisfying its
93                // shape — monotone, so the edge is positive.
94                let mut refs = Vec::new();
95                e.referenced_shapes(&mut refs);
96                for to in refs {
97                    edges.push(DepEdge {
98                        from,
99                        to,
100                        polarity: Polarity::Positive,
101                    });
102                }
103            }
104            _ => {}
105        }
106    }
107    edges
108}
shifty_opt/deps.rs

shifty_opt/
deps.rs
