riddle/
env.rs

1use crate::{
2    RiddleError,
3    core::Core,
4    scope::{Class, Predicate, Scope, Type},
5};
6use core::fmt;
7use std::{
8    any::Any,
9    cell::RefCell,
10    collections::HashMap,
11    ops::Deref,
12    rc::{Rc, Weak},
13};
14
15#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
16pub struct ObjectId(pub(super) usize);
17
18impl From<usize> for ObjectId {
19    fn from(val: usize) -> Self {
20        ObjectId(val)
21    }
22}
23
24impl Deref for ObjectId {
25    type Target = usize;
26
27    fn deref(&self) -> &Self::Target {
28        &self.0
29    }
30}
31
32impl fmt::Display for ObjectId {
33    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
34        write!(f, "obj-{}", self.0)
35    }
36}
37
38#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
39pub struct AtomId(pub(super) usize);
40
41impl Deref for AtomId {
42    type Target = usize;
43
44    fn deref(&self) -> &Self::Target {
45        &self.0
46    }
47}
48
49impl From<usize> for AtomId {
50    fn from(val: usize) -> Self {
51        AtomId(val)
52    }
53}
54
55impl fmt::Display for AtomId {
56    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
57        write!(f, "atm-{}", self.0)
58    }
59}
60
61#[derive(Clone)]
62pub enum Slot {
63    Primitive(Rc<dyn Var>),
64    ObjectRef(ObjectId),
65    AtomRef(AtomId),
66}
67
68impl fmt::Display for Slot {
69    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
70        match self {
71            Slot::Primitive(var) => write!(f, "{}", var.var_type().name()),
72            Slot::ObjectRef(obj_id) => write!(f, "Object({})", *obj_id),
73            Slot::AtomRef(atom_id) => write!(f, "Atom({})", *atom_id),
74        }
75    }
76}
77
78pub trait Var {
79    /// Returns the type of this variable.
80    fn var_type(&self) -> Rc<dyn Type>;
81    /// Returns a reference to this variable as a `dyn Any` for downcasting.
82    fn as_any(self: Rc<Self>) -> Rc<dyn Any>;
83    /// Returns a reference to this variable as a `dyn Env` if it is an environment.
84    fn as_env(self: Rc<Self>) -> Option<Rc<dyn Env>> {
85        None
86    }
87}
88
89pub trait Env {
90    /// Returns the parent environment of this environment, if any.
91    fn parent(&self) -> Option<Rc<dyn Env>>;
92    /// Returns a map of all variable names to their corresponding slots in this environment.
93    fn get_slots(&self) -> HashMap<String, Slot>;
94    /// Returns the slot corresponding to the given variable name in this environment, if it exists.
95    fn get(&self, name: &str) -> Option<Slot>;
96    /// Sets the slot corresponding to the given variable name in this environment.
97    fn set(&self, name: String, value: Slot);
98}
99
100pub struct CommonEnv {
101    parent: Option<Rc<dyn Env>>,
102    variables: RefCell<HashMap<String, Slot>>,
103}
104
105impl CommonEnv {
106    pub fn new(parent: Option<Rc<dyn Env>>) -> Self {
107        Self { parent, variables: RefCell::new(HashMap::new()) }
108    }
109}
110
111impl Env for CommonEnv {
112    fn parent(&self) -> Option<Rc<dyn Env>> {
113        self.parent.clone()
114    }
115
116    fn get_slots(&self) -> HashMap<String, Slot> {
117        self.variables.borrow().clone()
118    }
119
120    fn get(&self, name: &str) -> Option<Slot> {
121        self.variables.borrow().get(name).cloned().or_else(|| self.parent.as_ref()?.get(name))
122    }
123
124    fn set(&self, name: String, value: Slot) {
125        self.variables.borrow_mut().insert(name, value);
126    }
127}
128
129pub enum BoolExpr {
130    Term { var_type: Weak<dyn Type>, term: Slot },
131    Not { var_type: Weak<dyn Type>, term: Rc<BoolExpr> },
132    Eq { var_type: Weak<dyn Type>, left: Slot, right: Slot },
133    Lt { var_type: Weak<dyn Type>, left: Slot, right: Slot },
134    Leq { var_type: Weak<dyn Type>, left: Slot, right: Slot },
135    Or { var_type: Weak<dyn Type>, terms: Vec<Rc<BoolExpr>> },
136    And { var_type: Weak<dyn Type>, terms: Vec<Rc<BoolExpr>> },
137}
138
139impl Var for BoolExpr {
140    fn var_type(&self) -> Rc<dyn Type> {
141        match self {
142            BoolExpr::Term { var_type: var_tp, .. } | BoolExpr::Not { var_type: var_tp, .. } | BoolExpr::Eq { var_type: var_tp, .. } | BoolExpr::Lt { var_type: var_tp, .. } | BoolExpr::Leq { var_type: var_tp, .. } | BoolExpr::Or { var_type: var_tp, .. } | BoolExpr::And { var_type: var_tp, .. } => var_tp.upgrade().unwrap(),
143        }
144    }
145
146    fn as_any(self: Rc<Self>) -> Rc<dyn Any> {
147        self
148    }
149}
150
151pub struct Object {
152    id: ObjectId,
153    class: Weak<dyn Class>,
154    env: CommonEnv,
155}
156
157impl Object {
158    pub(super) fn new(id: ObjectId, class: Rc<dyn Class>) -> Self {
159        Self { id, class: Rc::downgrade(&class), env: CommonEnv::new(Some(class.core())) }
160    }
161
162    pub fn id(&self) -> ObjectId {
163        self.id
164    }
165
166    pub fn class(&self) -> Rc<dyn Class> {
167        self.class.upgrade().unwrap()
168    }
169}
170
171impl Var for Object {
172    fn var_type(&self) -> Rc<dyn Type> {
173        self.class.upgrade().unwrap()
174    }
175
176    fn as_any(self: Rc<Self>) -> Rc<dyn Any> {
177        self
178    }
179
180    fn as_env(self: Rc<Self>) -> Option<Rc<dyn Env>> {
181        Some(self.clone())
182    }
183}
184
185impl Env for Object {
186    fn parent(&self) -> Option<Rc<dyn Env>> {
187        self.env.parent.clone()
188    }
189
190    fn get_slots(&self) -> HashMap<String, Slot> {
191        self.env.get_slots()
192    }
193
194    fn get(&self, name: &str) -> Option<Slot> {
195        self.env.get(name)
196    }
197
198    fn set(&self, name: String, value: Slot) {
199        self.env.set(name, value);
200    }
201}
202
203pub struct Atom {
204    id: AtomId,
205    predicate: Weak<Predicate>,
206    fact: bool,
207    env: CommonEnv,
208}
209
210impl Atom {
211    pub fn new(id: AtomId, predicate: Rc<Predicate>, fact: bool, args: HashMap<String, Slot>) -> Self {
212        // Determine the environment for this atom based on the "tau" argument, if present.
213        let env = match args.get("tau") {
214            Some(tau) => match tau {
215                Slot::Primitive(var) => var.clone().as_env().expect("Tau variable does not have an environment").clone(),
216                Slot::ObjectRef(obj_id) => predicate.clone().core().get_object(*obj_id).expect("Object ID in tau does not exist").as_env().expect("Object in tau does not have an environment").clone(),
217                Slot::AtomRef(atom_id) => predicate.clone().core().get_atom(*atom_id).expect("Atom ID in tau does not exist").as_env().expect("Atom in tau does not have an environment").clone(),
218            },
219            None => predicate.core(),
220        };
221        // Create a new CommonEnv for this atom, with the determined environment as its parent.
222        let env = CommonEnv::new(Some(env));
223        for (name, value) in args {
224            env.set(name, value);
225        }
226        Self { id, predicate: Rc::downgrade(&predicate), fact, env }
227    }
228
229    pub fn id(&self) -> AtomId {
230        self.id
231    }
232
233    pub fn predicate(&self) -> Rc<Predicate> {
234        self.predicate.upgrade().unwrap()
235    }
236
237    pub fn is_fact(&self) -> bool {
238        self.fact
239    }
240}
241
242impl Var for Atom {
243    fn var_type(&self) -> Rc<dyn Type> {
244        self.predicate.upgrade().unwrap()
245    }
246
247    fn as_any(self: Rc<Self>) -> Rc<dyn Any> {
248        self
249    }
250
251    fn as_env(self: Rc<Self>) -> Option<Rc<dyn Env>> {
252        Some(self.clone())
253    }
254}
255
256impl Env for Atom {
257    fn parent(&self) -> Option<Rc<dyn Env>> {
258        self.env.parent.clone()
259    }
260
261    fn get_slots(&self) -> HashMap<String, Slot> {
262        self.env.get_slots()
263    }
264
265    fn get(&self, name: &str) -> Option<Slot> {
266        self.env.get(name)
267    }
268
269    fn set(&self, name: String, value: Slot) {
270        self.env.set(name, value);
271    }
272}
273
274fn push_negations(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
275    match expr.as_ref() {
276        BoolExpr::Not { term, .. } => push_inverted(term.clone()),
277        BoolExpr::And { var_type, terms } => Rc::new(BoolExpr::And {
278            var_type: var_type.clone(),
279            terms: terms.iter().map(|t| push_negations(t.clone())).collect(),
280        }),
281        BoolExpr::Or { var_type, terms } => Rc::new(BoolExpr::Or {
282            var_type: var_type.clone(),
283            terms: terms.iter().map(|t| push_negations(t.clone())).collect(),
284        }),
285        _ => expr,
286    }
287}
288
289/// Processes an expression as if a `Not` wrapper were applied to it.
290fn push_inverted(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
291    match expr.as_ref() {
292        // Double Negation: Not(Not(term)) => term
293        BoolExpr::Not { term, .. } => push_negations(term.clone()),
294
295        // De Morgan: Not(And(A, B)) => Or(Not(A), Not(B))
296        BoolExpr::And { var_type, terms } => Rc::new(BoolExpr::Or {
297            var_type: var_type.clone(),
298            terms: terms.iter().map(|t| push_inverted(t.clone())).collect(),
299        }),
300
301        // De Morgan: Not(Or(A, B)) => And(Not(A), Not(B))
302        BoolExpr::Or { var_type, terms } => Rc::new(BoolExpr::And {
303            var_type: var_type.clone(),
304            terms: terms.iter().map(|t| push_inverted(t.clone())).collect(),
305        }),
306
307        BoolExpr::Leq { var_type, left, right } => Rc::new(BoolExpr::Lt { var_type: var_type.clone(), left: right.clone(), right: left.clone() }),
308        BoolExpr::Lt { var_type, left, right } => Rc::new(BoolExpr::Leq { var_type: var_type.clone(), left: right.clone(), right: left.clone() }),
309
310        BoolExpr::Term { var_type: var_tp, .. } | BoolExpr::Eq { var_type: var_tp, .. } => Rc::new(BoolExpr::Not { var_type: var_tp.clone(), term: expr }),
311    }
312}
313
314fn distribute(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
315    match expr.as_ref() {
316        BoolExpr::Or { var_type, terms } => {
317            // Step 1: Recursively distribute child nodes and flatten any nested Ors
318            let mut distributed_terms = Vec::new();
319            for t in terms {
320                let dist = distribute(t.clone());
321                if let BoolExpr::Or { terms: inner_terms, .. } = dist.as_ref() {
322                    distributed_terms.extend(inner_terms.clone());
323                } else {
324                    distributed_terms.push(dist);
325                }
326            }
327
328            // Step 2: Build the Cartesian product of terms over And boundaries
329            // Start with a pool containing a single empty clause
330            let mut result_ands: Vec<Vec<Rc<BoolExpr>>> = vec![vec![]];
331
332            for term in distributed_terms {
333                if let BoolExpr::And { terms: and_terms, .. } = term.as_ref() {
334                    // Split all existing combinations across the newly encountered And choices
335                    let mut next_ands = Vec::new();
336                    for existing_and in &result_ands {
337                        for and_term in and_terms {
338                            let mut combo = existing_and.clone();
339                            combo.push(and_term.clone());
340                            next_ands.push(combo);
341                        }
342                    }
343                    result_ands = next_ands;
344                } else {
345                    // Leaf nodes or Or nodes get appended to all current paths
346                    for existing_and in &mut result_ands {
347                        existing_and.push(term.clone());
348                    }
349                }
350            }
351
352            // Step 3: Map our combinations back into Or nodes inside a master And node
353            let cnf_or_nodes: Vec<Rc<BoolExpr>> = result_ands.into_iter().map(|sub_terms| Rc::new(BoolExpr::Or { var_type: var_type.clone(), terms: sub_terms })).collect();
354
355            // Optimization: If no distribution happened, don't wrap in a redundant And
356            if cnf_or_nodes.len() == 1 { cnf_or_nodes[0].clone() } else { Rc::new(BoolExpr::And { var_type: var_type.clone(), terms: cnf_or_nodes }) }
357        }
358
359        BoolExpr::And { var_type, terms } => {
360            // Flatten nested Ands to keep the AST compact
361            let mut distributed_terms = Vec::new();
362            for t in terms {
363                let dist = distribute(t.clone());
364                if let BoolExpr::And { terms: inner_terms, .. } = dist.as_ref() {
365                    distributed_terms.extend(inner_terms.clone());
366                } else {
367                    distributed_terms.push(dist);
368                }
369            }
370            Rc::new(BoolExpr::And { var_type: var_type.clone(), terms: distributed_terms })
371        }
372
373        _ => expr,
374    }
375}
376
377pub fn to_cnf(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
378    distribute(push_negations(expr))
379}
380
381/// Resolves a nested variable path starting from the given environment.
382///
383/// The first segment is read from the initial environment and each subsequent
384/// segment is resolved against the environment exposed by the current value.
385/// This supports walking through primitive variables, object references, and
386/// atom references while returning a `RiddleError` if any segment is missing or
387/// the current value is not an environment.
388pub fn get_var_by_path(core: &dyn Core, env: &dyn Env, path: &[String]) -> Result<Slot, RiddleError> {
389    let (first, rest) = path.split_first().ok_or_else(|| RiddleError::RuntimeError("Empty variable path".into()))?;
390    rest.iter().try_fold(env.get(first).ok_or_else(|| RiddleError::NotFound(first.to_string()))?, |acc, id| match acc {
391        Slot::Primitive(var) => var.clone().as_env().ok_or_else(|| RiddleError::NotAnEnvironment(format!("Variable '{}' in path does not have an environment", first)))?.get(id).ok_or_else(|| RiddleError::NotFound(format!("Variable '{}' in path not found in variable '{}'", id, first))),
392        Slot::ObjectRef(obj_id) => {
393            let obj = core.get_object(obj_id).ok_or_else(|| RiddleError::NotFound(format!("Object {} not found", *obj_id)))?;
394            obj.as_env().ok_or_else(|| RiddleError::NotAnEnvironment(format!("Object {} does not have an environment", *obj_id)))?.get(id).ok_or_else(|| RiddleError::NotFound(format!("Variable '{}' in path not found in object {}", id, *obj_id)))
395        }
396        Slot::AtomRef(atom_id) => {
397            let atom = core.get_atom(atom_id).ok_or_else(|| RiddleError::NotFound(format!("Atom {} not found", *atom_id)))?;
398            atom.as_env().ok_or_else(|| RiddleError::NotAnEnvironment(format!("Atom {} does not have an environment", *atom_id)))?.get(id).ok_or_else(|| RiddleError::NotFound(format!("Variable '{}' in path not found in atom {}", id, *atom_id)))
399        }
400    })
401}
riddle/env.rs

riddle/
env.rs
