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(None) }
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        let env = match args.get("tau") {
213            Some(tau) => match tau {
214                Slot::Primitive(var) => var.clone().as_env().expect("Tau variable does not have an environment").clone(),
215                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(),
216                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(),
217            },
218            None => predicate.clone().core(),
219        };
220        let env = CommonEnv::new(Some(env));
221        for (name, value) in args {
222            env.set(name, value);
223        }
224        Self { id, predicate: Rc::downgrade(&predicate), fact, env }
225    }
226
227    pub fn id(&self) -> AtomId {
228        self.id
229    }
230
231    pub fn predicate(&self) -> Rc<Predicate> {
232        self.predicate.upgrade().unwrap()
233    }
234
235    pub fn is_fact(&self) -> bool {
236        self.fact
237    }
238}
239
240impl Var for Atom {
241    fn var_type(&self) -> Rc<dyn Type> {
242        self.predicate.upgrade().unwrap()
243    }
244
245    fn as_any(self: Rc<Self>) -> Rc<dyn Any> {
246        self
247    }
248
249    fn as_env(self: Rc<Self>) -> Option<Rc<dyn Env>> {
250        Some(self.clone())
251    }
252}
253
254impl Env for Atom {
255    fn parent(&self) -> Option<Rc<dyn Env>> {
256        self.env.parent.clone()
257    }
258
259    fn get_slots(&self) -> HashMap<String, Slot> {
260        self.env.get_slots()
261    }
262
263    fn get(&self, name: &str) -> Option<Slot> {
264        self.env.get(name)
265    }
266
267    fn set(&self, name: String, value: Slot) {
268        self.env.set(name, value);
269    }
270}
271
272fn push_negations(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
273    match expr.as_ref() {
274        BoolExpr::Not { term, .. } => push_inverted(term.clone()),
275        BoolExpr::And { var_type, terms } => Rc::new(BoolExpr::And {
276            var_type: var_type.clone(),
277            terms: terms.iter().map(|t| push_negations(t.clone())).collect(),
278        }),
279        BoolExpr::Or { var_type, terms } => Rc::new(BoolExpr::Or {
280            var_type: var_type.clone(),
281            terms: terms.iter().map(|t| push_negations(t.clone())).collect(),
282        }),
283        _ => expr,
284    }
285}
286
287/// Processes an expression as if a `Not` wrapper were applied to it.
288fn push_inverted(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
289    match expr.as_ref() {
290        // Double Negation: Not(Not(term)) => term
291        BoolExpr::Not { term, .. } => push_negations(term.clone()),
292
293        // De Morgan: Not(And(A, B)) => Or(Not(A), Not(B))
294        BoolExpr::And { var_type, terms } => Rc::new(BoolExpr::Or {
295            var_type: var_type.clone(),
296            terms: terms.iter().map(|t| push_inverted(t.clone())).collect(),
297        }),
298
299        // De Morgan: Not(Or(A, B)) => And(Not(A), Not(B))
300        BoolExpr::Or { var_type, terms } => Rc::new(BoolExpr::And {
301            var_type: var_type.clone(),
302            terms: terms.iter().map(|t| push_inverted(t.clone())).collect(),
303        }),
304
305        BoolExpr::Leq { var_type, left, right } => Rc::new(BoolExpr::Lt { var_type: var_type.clone(), left: right.clone(), right: left.clone() }),
306        BoolExpr::Lt { var_type, left, right } => Rc::new(BoolExpr::Leq { var_type: var_type.clone(), left: right.clone(), right: left.clone() }),
307
308        BoolExpr::Term { var_type: var_tp, .. } | BoolExpr::Eq { var_type: var_tp, .. } => Rc::new(BoolExpr::Not { var_type: var_tp.clone(), term: expr }),
309    }
310}
311
312fn distribute(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
313    match expr.as_ref() {
314        BoolExpr::Or { var_type, terms } => {
315            // Step 1: Recursively distribute child nodes and flatten any nested Ors
316            let mut distributed_terms = Vec::new();
317            for t in terms {
318                let dist = distribute(t.clone());
319                if let BoolExpr::Or { terms: inner_terms, .. } = dist.as_ref() {
320                    distributed_terms.extend(inner_terms.clone());
321                } else {
322                    distributed_terms.push(dist);
323                }
324            }
325
326            // Step 2: Build the Cartesian product of terms over And boundaries
327            // Start with a pool containing a single empty clause
328            let mut result_ands: Vec<Vec<Rc<BoolExpr>>> = vec![vec![]];
329
330            for term in distributed_terms {
331                if let BoolExpr::And { terms: and_terms, .. } = term.as_ref() {
332                    // Split all existing combinations across the newly encountered And choices
333                    let mut next_ands = Vec::new();
334                    for existing_and in &result_ands {
335                        for and_term in and_terms {
336                            let mut combo = existing_and.clone();
337                            combo.push(and_term.clone());
338                            next_ands.push(combo);
339                        }
340                    }
341                    result_ands = next_ands;
342                } else {
343                    // Leaf nodes or Or nodes get appended to all current paths
344                    for existing_and in &mut result_ands {
345                        existing_and.push(term.clone());
346                    }
347                }
348            }
349
350            // Step 3: Map our combinations back into Or nodes inside a master And node
351            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();
352
353            // Optimization: If no distribution happened, don't wrap in a redundant And
354            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 }) }
355        }
356
357        BoolExpr::And { var_type, terms } => {
358            // Flatten nested Ands to keep the AST compact
359            let mut distributed_terms = Vec::new();
360            for t in terms {
361                let dist = distribute(t.clone());
362                if let BoolExpr::And { terms: inner_terms, .. } = dist.as_ref() {
363                    distributed_terms.extend(inner_terms.clone());
364                } else {
365                    distributed_terms.push(dist);
366                }
367            }
368            Rc::new(BoolExpr::And { var_type: var_type.clone(), terms: distributed_terms })
369        }
370
371        _ => expr,
372    }
373}
374
375pub fn to_cnf(expr: Rc<BoolExpr>) -> Rc<BoolExpr> {
376    distribute(push_negations(expr))
377}
378
379/// Resolves a nested variable path starting from the given environment.
380///
381/// The first segment is read from the initial environment and each subsequent
382/// segment is resolved against the environment exposed by the current value.
383/// This supports walking through primitive variables, object references, and
384/// atom references while returning a `RiddleError` if any segment is missing or
385/// the current value is not an environment.
386pub fn get_var_by_path(core: &dyn Core, env: &dyn Env, path: &[String]) -> Result<Slot, RiddleError> {
387    let (first, rest) = path.split_first().ok_or_else(|| RiddleError::RuntimeError("Empty variable path".into()))?;
388    rest.iter().try_fold(env.get(first).ok_or_else(|| RiddleError::NotFound(first.to_string()))?, |acc, id| match acc {
389        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))),
390        Slot::ObjectRef(obj_id) => {
391            let obj = core.get_object(obj_id).ok_or_else(|| RiddleError::NotFound(format!("Object {} not found", *obj_id)))?;
392            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)))
393        }
394        Slot::AtomRef(atom_id) => {
395            let atom = core.get_atom(atom_id).ok_or_else(|| RiddleError::NotFound(format!("Atom {} not found", *atom_id)))?;
396            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)))
397        }
398    })
399}
riddle/env.rs

riddle/
env.rs
