1 use std::cell::RefCell;
2 use std::collections::BTreeMap;
3 use std::collections::{HashMap, HashSet};
4 use std::fmt::Write;
5 use std::rc::Rc;
6 use std::string::ToString;
7 use std::sync::{Arc, RwLock};
8
9 #[cfg(target_arch = "wasm32")]
10 use wasm_bindgen::prelude::*;
11
12 use super::visitor::{walk_term, Visitor};
13 use crate::bindings::{BindingManager, BindingStack, Bindings, Bsp, FollowerId, VariableState};
14 use crate::counter::Counter;
15 use crate::debugger::{DebugEvent, Debugger};
16 use crate::error::{self, PolarResult};
17 use crate::events::*;
18 use crate::folder::Folder;
19 use crate::formatting::ToPolarString;
20 use crate::inverter::Inverter;
21 use crate::kb::*;
22 use crate::lexer::loc_to_pos;
23 use crate::messages::*;
24 use crate::numerics::*;
25 use crate::partial::{simplify_bindings, simplify_partial, sub_this, IsaConstraintCheck};
26 use crate::rewrites::Renamer;
27 use crate::rules::*;
28 use crate::runnable::Runnable;
29 use crate::sources::*;
30 use crate::terms::*;
31 use crate::traces::*;
32
33 pub const MAX_STACK_SIZE: usize = 10_000;
34 #[cfg(not(target_arch = "wasm32"))]
35 pub const QUERY_TIMEOUT_S: std::time::Duration = std::time::Duration::from_secs(30);
36 #[cfg(target_arch = "wasm32")]
37 pub const QUERY_TIMEOUT_S: f64 = 30_000.0;
38
39 #[derive(Debug, Clone)]
40 #[must_use = "ignored goals are never accomplished"]
41 #[allow(clippy::large_enum_variant)]
42 pub enum Goal {
43 Backtrack,
44 Cut {
45 choice_index: usize, // cuts all choices in range [choice_index..]
46 },
47 Debug {
48 message: String,
49 },
50 Halt,
51 Isa {
52 left: Term,
53 right: Term,
54 },
55 IsMoreSpecific {
56 left: Arc<Rule>,
57 right: Arc<Rule>,
58 args: TermList,
59 },
60 IsSubspecializer {
61 answer: Symbol,
62 left: Term,
63 right: Term,
64 arg: Term,
65 },
66 Lookup {
67 dict: Dictionary,
68 field: Term,
69 value: Term,
70 },
71 LookupExternal {
72 call_id: u64,
73 instance: Term,
74 field: Term,
75 },
76 IsaExternal {
77 instance: Term,
78 literal: InstanceLiteral,
79 },
80 MakeExternal {
81 constructor: Term,
82 instance_id: u64,
83 },
84 NextExternal {
85 call_id: u64,
86 iterable: Term,
87 },
88 UnifyExternal {
89 left_instance_id: u64,
90 right_instance_id: u64,
91 },
92 CheckError,
93 Noop,
94 Query {
95 term: Term,
96 },
97 PopQuery {
98 term: Term,
99 },
100 FilterRules {
101 args: TermList,
102 applicable_rules: Rules,
103 unfiltered_rules: Rules,
104 },
105 SortRules {
106 args: TermList,
107 rules: Rules,
108 outer: usize,
109 inner: usize,
110 },
111 TraceRule {
112 trace: Rc<Trace>,
113 },
114 TraceStackPush,
115 TraceStackPop,
116 Unify {
117 left: Term,
118 right: Term,
119 },
120
121 /// Run the `runnable`.
122 Run {
123 runnable: Box<dyn Runnable>,
124 },
125
126 /// Add a new constraint
127 AddConstraint {
128 term: Term,
129 },
130
131 /// TODO hack.
132 /// Add a new constraint
133 AddConstraintsBatch {
134 add_constraints: Rc<RefCell<Bindings>>,
135 },
136 }
137
138 #[derive(Clone, Debug)]
139 pub struct Choice {
140 pub alternatives: Vec<GoalStack>,
141 bsp: Bsp, // binding stack pointer
142 pub goals: GoalStack, // goal stack snapshot
143 queries: Queries, // query stack snapshot
144 trace: Vec<Rc<Trace>>, // trace snapshot
145 trace_stack: TraceStack,
146 }
147
148 pub type Choices = Vec<Choice>;
149 /// Shortcut type alias for a list of goals
150 pub type Goals = Vec<Goal>;
151 pub type TraceStack = Vec<Rc<Vec<Rc<Trace>>>>;
152
153 #[derive(Clone, Debug, Default)]
154 pub struct GoalStack(Vec<Rc<Goal>>);
155
156 impl GoalStack {
new_reversed(goals: Goals) -> Self157 fn new_reversed(goals: Goals) -> Self {
158 Self(goals.into_iter().rev().map(Rc::new).collect())
159 }
160 }
161
162 impl std::ops::Deref for GoalStack {
163 type Target = Vec<Rc<Goal>>;
164
deref(&self) -> &Self::Target165 fn deref(&self) -> &Self::Target {
166 &self.0
167 }
168 }
169
170 impl std::ops::DerefMut for GoalStack {
deref_mut(&mut self) -> &mut Self::Target171 fn deref_mut(&mut self) -> &mut Self::Target {
172 &mut self.0
173 }
174 }
175
176 pub type Queries = TermList;
177
178 // TODO(ap): don't panic.
compare(op: Operator, left: &Term, right: &Term) -> PolarResult<bool>179 pub fn compare(op: Operator, left: &Term, right: &Term) -> PolarResult<bool> {
180 // Coerce booleans to integers.
181 fn to_int(x: bool) -> Numeric {
182 if x {
183 Numeric::Integer(1)
184 } else {
185 Numeric::Integer(0)
186 }
187 }
188
189 fn compare<T: PartialOrd>(op: Operator, left: T, right: T) -> bool {
190 match op {
191 Operator::Lt => left < right,
192 Operator::Leq => left <= right,
193 Operator::Gt => left > right,
194 Operator::Geq => left >= right,
195 Operator::Eq => left == right,
196 Operator::Neq => left != right,
197 _ => panic!("`{}` is not a comparison operator", op.to_polar()),
198 }
199 }
200
201 match (left.value(), right.value()) {
202 (Value::Boolean(l), Value::Boolean(r)) => Ok(compare(op, &to_int(*l), &to_int(*r))),
203 (Value::Boolean(l), Value::Number(r)) => Ok(compare(op, &to_int(*l), r)),
204 (Value::Number(l), Value::Boolean(r)) => Ok(compare(op, l, &to_int(*r))),
205 (Value::Number(l), Value::Number(r)) => Ok(compare(op, l, r)),
206 (Value::String(l), Value::String(r)) => Ok(compare(op, l, r)),
207 _ => Err(error::RuntimeError::Unsupported {
208 msg: format!("{} {} {}", left.to_polar(), op.to_polar(), right.to_polar()),
209 }
210 .into()),
211 }
212 }
213
214 #[derive(Clone)]
215 pub struct PolarVirtualMachine {
216 /// Stacks.
217 pub goals: GoalStack,
218 binding_manager: BindingManager,
219 choices: Choices,
220 pub queries: Queries,
221
222 pub tracing: bool,
223 pub trace_stack: TraceStack, // Stack of traces higher up the tree.
224 pub trace: Vec<Rc<Trace>>, // Traces for the current level of the trace tree.
225
226 // Errors from outside the vm.
227 pub external_error: Option<String>,
228
229 #[cfg(not(target_arch = "wasm32"))]
230 query_start_time: Option<std::time::Instant>,
231 #[cfg(target_arch = "wasm32")]
232 query_start_time: Option<f64>,
233 #[cfg(not(target_arch = "wasm32"))]
234 query_timeout: std::time::Duration,
235 #[cfg(target_arch = "wasm32")]
236 query_timeout: f64,
237
238 /// Maximum size of goal stack
239 stack_limit: usize,
240
241 /// Binding stack constant below here.
242 csp: Bsp,
243
244 /// Interactive debugger.
245 pub debugger: Debugger,
246
247 /// Rules and types.
248 pub kb: Arc<RwLock<KnowledgeBase>>,
249
250 /// Call ID -> result variable name table.
251 call_id_symbols: HashMap<u64, Symbol>,
252
253 /// Logging flag.
254 log: bool,
255 polar_log: bool,
256 polar_log_stderr: bool,
257 polar_log_mute: bool,
258
259 // Other flags.
260 pub query_contains_partial: bool,
261 pub inverting: bool,
262
263 /// Output messages.
264 pub messages: MessageQueue,
265 }
266
267 impl Default for PolarVirtualMachine {
default() -> Self268 fn default() -> Self {
269 PolarVirtualMachine::new(
270 Arc::new(RwLock::new(KnowledgeBase::default())),
271 false,
272 vec![],
273 // Messages will not be exposed, only use default() for testing.
274 MessageQueue::new(),
275 )
276 }
277 }
278
279 #[cfg(target_arch = "wasm32")]
280 #[wasm_bindgen]
281 extern "C" {
282 #[wasm_bindgen(js_namespace = console, js_name = error)]
console_error(a: &str)283 fn console_error(a: &str);
284 }
285
286 // Methods which aren't goals/instructions.
287 impl PolarVirtualMachine {
288 /// Make a new virtual machine with an initial list of goals.
289 /// Reverse the goal list for the sanity of callers.
new( kb: Arc<RwLock<KnowledgeBase>>, tracing: bool, goals: Goals, messages: MessageQueue, ) -> Self290 pub fn new(
291 kb: Arc<RwLock<KnowledgeBase>>,
292 tracing: bool,
293 goals: Goals,
294 messages: MessageQueue,
295 ) -> Self {
296 let constants = kb
297 .read()
298 .expect("cannot acquire KB read lock")
299 .constants
300 .clone();
301 let mut vm = Self {
302 goals: GoalStack::new_reversed(goals),
303 binding_manager: BindingManager::new(),
304 query_start_time: None,
305 query_timeout: QUERY_TIMEOUT_S,
306 stack_limit: MAX_STACK_SIZE,
307 csp: Bsp::default(),
308 choices: vec![],
309 queries: vec![],
310 tracing,
311 trace_stack: vec![],
312 trace: vec![],
313 external_error: None,
314 debugger: Debugger::default(),
315 kb,
316 call_id_symbols: HashMap::new(),
317 log: std::env::var("RUST_LOG").is_ok(),
318 polar_log: std::env::var("POLAR_LOG").is_ok(),
319 polar_log_stderr: std::env::var("POLAR_LOG")
320 .map(|pl| pl == "now")
321 .unwrap_or(false),
322 polar_log_mute: false,
323 query_contains_partial: false,
324 inverting: false,
325 messages,
326 };
327 vm.bind_constants(constants);
328 vm.query_contains_partial();
329 vm
330 }
331
332 #[cfg(target_arch = "wasm32")]
set_logging_options(&mut self, rust_log: Option<String>, polar_log: Option<String>)333 pub fn set_logging_options(&mut self, rust_log: Option<String>, polar_log: Option<String>) {
334 self.log = rust_log.is_some();
335 if let Some(pl) = polar_log {
336 if &pl == "now" {
337 self.polar_log_stderr = true;
338 }
339 self.polar_log = true;
340 }
341 }
342
query_contains_partial(&mut self)343 fn query_contains_partial(&mut self) {
344 struct VarVisitor<'vm> {
345 has_partial: bool,
346 vm: &'vm PolarVirtualMachine,
347 }
348
349 impl<'vm> Visitor for VarVisitor<'vm> {
350 fn visit_variable(&mut self, v: &Symbol) {
351 if matches!(self.vm.variable_state(v), VariableState::Partial) {
352 self.has_partial = true;
353 }
354 }
355 }
356
357 let mut visitor = VarVisitor {
358 has_partial: false,
359 vm: &self,
360 };
361 self.query_contains_partial = self.goals.iter().any(|goal| {
362 if let Goal::Query { term } = goal.as_ref() {
363 walk_term(&mut visitor, term);
364 visitor.has_partial
365 } else {
366 false
367 }
368 });
369 }
370
371 #[cfg(test)]
new_test(kb: Arc<RwLock<KnowledgeBase>>, tracing: bool, goals: Goals) -> Self372 pub fn new_test(kb: Arc<RwLock<KnowledgeBase>>, tracing: bool, goals: Goals) -> Self {
373 PolarVirtualMachine::new(kb, tracing, goals, MessageQueue::new())
374 }
375
376 /// Clone self, replacing the goal stack and retaining only the current bindings.
clone_with_goals(&self, goals: Goals) -> Self377 pub fn clone_with_goals(&self, goals: Goals) -> Self {
378 let mut vm = Self::new(self.kb.clone(), self.tracing, goals, self.messages.clone());
379 vm.binding_manager.clone_from(&self.binding_manager);
380 vm.query_contains_partial = self.query_contains_partial;
381 vm.debugger = self.debugger.clone();
382 vm
383 }
384
385 #[cfg(test)]
set_stack_limit(&mut self, limit: usize)386 fn set_stack_limit(&mut self, limit: usize) {
387 self.stack_limit = limit;
388 }
389
390 #[cfg(test)]
set_query_timeout(&mut self, timeout_s: u64)391 fn set_query_timeout(&mut self, timeout_s: u64) {
392 self.query_timeout = std::time::Duration::from_secs(timeout_s);
393 }
394
new_id(&self) -> u64395 pub fn new_id(&self) -> u64 {
396 self.kb
397 .read()
398 .expect("cannot acquire KB read lock")
399 .new_id()
400 }
401
id_counter(&self) -> Counter402 pub fn id_counter(&self) -> Counter {
403 self.kb
404 .read()
405 .expect("cannot acquire KB read lock")
406 .id_counter()
407 }
408
new_call_id(&mut self, symbol: &Symbol) -> u64409 fn new_call_id(&mut self, symbol: &Symbol) -> u64 {
410 let call_id = self.new_id();
411 self.call_id_symbols.insert(call_id, symbol.clone());
412 call_id
413 }
414
new_call_var(&mut self, var_prefix: &str, initial_value: Value) -> (u64, Term)415 fn new_call_var(&mut self, var_prefix: &str, initial_value: Value) -> (u64, Term) {
416 let sym = self.kb.read().unwrap().gensym(var_prefix);
417 self.bind(&sym, Term::new_temporary(initial_value)).unwrap();
418 let call_id = self.new_call_id(&sym);
419 (call_id, Term::new_temporary(Value::Variable(sym)))
420 }
421
get_call_sym(&self, call_id: u64) -> &Symbol422 fn get_call_sym(&self, call_id: u64) -> &Symbol {
423 self.call_id_symbols
424 .get(&call_id)
425 .expect("unregistered external call ID")
426 }
427
428 /// Try to achieve one goal. Return `Some(QueryEvent)` if an external
429 /// result is needed to achieve it, or `None` if it can run internally.
next(&mut self, goal: Rc<Goal>) -> PolarResult<QueryEvent>430 fn next(&mut self, goal: Rc<Goal>) -> PolarResult<QueryEvent> {
431 if self.log {
432 self.print(&format!("{}", goal));
433 }
434
435 self.check_timeout()?;
436
437 match goal.as_ref() {
438 Goal::Backtrack => self.backtrack()?,
439 Goal::Cut { choice_index } => self.cut(*choice_index),
440 Goal::Debug { message } => return Ok(self.debug(&message)),
441 Goal::Halt => return Ok(self.halt()),
442 Goal::Isa { left, right } => self.isa(&left, &right)?,
443 Goal::IsMoreSpecific { left, right, args } => {
444 self.is_more_specific(left, right, args)?
445 }
446 Goal::IsSubspecializer {
447 answer,
448 left,
449 right,
450 arg,
451 } => return self.is_subspecializer(answer, left, right, arg),
452 Goal::Lookup { dict, field, value } => self.lookup(dict, field, value)?,
453 Goal::LookupExternal {
454 call_id,
455 instance,
456 field,
457 } => return self.lookup_external(*call_id, instance, field),
458 Goal::IsaExternal { instance, literal } => return self.isa_external(instance, literal),
459 Goal::UnifyExternal {
460 left_instance_id,
461 right_instance_id,
462 } => return self.unify_external(*left_instance_id, *right_instance_id),
463 Goal::MakeExternal {
464 constructor,
465 instance_id,
466 } => return Ok(self.make_external(constructor, *instance_id)),
467 Goal::NextExternal { call_id, iterable } => {
468 return self.next_external(*call_id, iterable)
469 }
470 Goal::CheckError => return self.check_error(),
471 Goal::Noop => {}
472 Goal::Query { term } => {
473 let result = self.query(term);
474 self.maybe_break(DebugEvent::Query)?;
475 return result;
476 }
477 Goal::PopQuery { .. } => self.pop_query(),
478 Goal::FilterRules {
479 applicable_rules,
480 unfiltered_rules,
481 args,
482 } => self.filter_rules(applicable_rules, unfiltered_rules, args)?,
483 Goal::SortRules {
484 rules,
485 outer,
486 inner,
487 args,
488 } => self.sort_rules(rules, args, *outer, *inner)?,
489 Goal::TraceStackPush => {
490 self.trace_stack.push(Rc::new(self.trace.clone()));
491 self.trace = vec![];
492 }
493 Goal::TraceStackPop => {
494 let mut children = self.trace.clone();
495 self.trace = self.trace_stack.pop().unwrap().as_ref().clone();
496 let mut trace = self.trace.pop().unwrap();
497 let trace = Rc::make_mut(&mut trace);
498 trace.children.append(&mut children);
499 self.trace.push(Rc::new(trace.clone()));
500 self.maybe_break(DebugEvent::Pop)?;
501 }
502 Goal::TraceRule { trace } => {
503 if let Node::Rule(rule) = &trace.node {
504 self.log_with(
505 || {
506 let source_str = self.rule_source(&rule);
507 format!("RULE: {}", source_str)
508 },
509 &[],
510 );
511 }
512 self.trace.push(trace.clone());
513 }
514 Goal::Unify { left, right } => self.unify(&left, &right)?,
515 Goal::AddConstraint { term } => self.add_constraint(&term)?,
516 Goal::AddConstraintsBatch { add_constraints } => {
517 add_constraints.borrow_mut().drain().try_for_each(
518 |(_, constraint)| -> PolarResult<()> { self.add_constraint(&constraint) },
519 )?
520 }
521 Goal::Run { runnable } => return self.run_runnable(runnable.clone_runnable()),
522 }
523 Ok(QueryEvent::None)
524 }
525
526 /// Return true if there is nothing left to do.
is_halted(&self) -> bool527 pub fn is_halted(&self) -> bool {
528 self.goals.is_empty() && self.choices.is_empty()
529 }
530
531 /// Push a goal onto the goal stack.
push_goal(&mut self, goal: Goal) -> PolarResult<()>532 pub fn push_goal(&mut self, goal: Goal) -> PolarResult<()> {
533 if self.goals.len() >= self.stack_limit {
534 return Err(error::RuntimeError::StackOverflow {
535 msg: format!("Goal stack overflow! MAX_GOALS = {}", self.stack_limit),
536 }
537 .into());
538 }
539 match goal {
540 Goal::LookupExternal { call_id, .. } | Goal::NextExternal { call_id, .. } => {
541 assert!(matches!(
542 self.variable_state(self.get_call_sym(call_id)),
543 VariableState::Unbound
544 ), "The call_id result variables for LookupExternal and NextExternal goals must be unbound.");
545 }
546 _ => (),
547 }
548
549 self.goals.push(Rc::new(goal));
550 Ok(())
551 }
552
553 /// Push a non-trivial choice onto the choice stack.
554 ///
555 /// Params:
556 ///
557 /// - `alternatives`: an ordered list of alternatives to try in the choice.
558 /// The first element is the first alternative to try.
559 ///
560 /// Do not modify the goals stack. This function defers execution of the
561 /// choice until a backtrack occurs. To immediately execute the choice on
562 /// top of the current stack, use `choose`.
push_choice<I>(&mut self, alternatives: I) where I: IntoIterator<Item = Goals>, I::IntoIter: std::iter::DoubleEndedIterator,563 fn push_choice<I>(&mut self, alternatives: I)
564 where
565 I: IntoIterator<Item = Goals>,
566 I::IntoIter: std::iter::DoubleEndedIterator,
567 {
568 // Make sure that alternatives are executed in order of first to last.
569 let alternatives = alternatives
570 .into_iter()
571 .rev()
572 .map(GoalStack::new_reversed)
573 .collect();
574 assert!(self.choices.len() < self.stack_limit, "too many choices");
575 self.choices.push(Choice {
576 alternatives,
577 bsp: self.bsp(),
578 goals: self.goals.clone(),
579 queries: self.queries.clone(),
580 trace: self.trace.clone(),
581 trace_stack: self.trace_stack.clone(),
582 });
583 }
584
585 /// Push a choice onto the choice stack, and execute immediately by
586 /// pushing the first alternative onto the goals stack
587 ///
588 /// Params:
589 ///
590 /// - `alternatives`: an ordered list of alternatives to try in the choice.
591 /// The first element is the first alternative to try.
choose<I>(&mut self, alternatives: I) -> PolarResult<()> where I: IntoIterator<Item = Goals>, I::IntoIter: std::iter::DoubleEndedIterator,592 fn choose<I>(&mut self, alternatives: I) -> PolarResult<()>
593 where
594 I: IntoIterator<Item = Goals>,
595 I::IntoIter: std::iter::DoubleEndedIterator,
596 {
597 let mut alternatives_iter = alternatives.into_iter();
598 if let Some(alternative) = alternatives_iter.next() {
599 self.push_choice(alternatives_iter);
600 self.append_goals(alternative)?;
601 Ok(())
602 } else {
603 self.backtrack()
604 }
605 }
606
607 /// If each goal of `conditional` succeeds, execute `consequent`;
608 /// otherwise, execute `alternative`. The branches are entered only
609 /// by backtracking so that bindings established during the execution
610 /// of `conditional` are always unwound.
choose_conditional( &mut self, mut conditional: Goals, consequent: Goals, mut alternative: Goals, ) -> PolarResult<()>611 fn choose_conditional(
612 &mut self,
613 mut conditional: Goals,
614 consequent: Goals,
615 mut alternative: Goals,
616 ) -> PolarResult<()> {
617 // If the conditional fails, cut the consequent.
618 let cut_consequent = Goal::Cut {
619 choice_index: self.choices.len(),
620 };
621 alternative.insert(0, cut_consequent);
622
623 // If the conditional succeeds, cut the alternative and backtrack to this choice point.
624 self.push_choice(vec![consequent]);
625 let cut_alternative = Goal::Cut {
626 choice_index: self.choices.len(),
627 };
628 conditional.push(cut_alternative);
629 conditional.push(Goal::Backtrack);
630
631 self.choose(vec![conditional, alternative])?;
632 Ok(())
633 }
634
635 /// Push multiple goals onto the stack in reverse order.
append_goals<I>(&mut self, goals: I) -> PolarResult<()> where I: IntoIterator<Item = Goal>, I::IntoIter: std::iter::DoubleEndedIterator,636 fn append_goals<I>(&mut self, goals: I) -> PolarResult<()>
637 where
638 I: IntoIterator<Item = Goal>,
639 I::IntoIter: std::iter::DoubleEndedIterator,
640 {
641 goals.into_iter().rev().try_for_each(|g| self.push_goal(g))
642 }
643
644 /// Rebind an external answer variable.
645 ///
646 /// DO NOT USE THIS TO REBIND ANOTHER VARIABLE (see unsafe_rebind doc string).
rebind_external_answer(&mut self, var: &Symbol, val: Term)647 fn rebind_external_answer(&mut self, var: &Symbol, val: Term) {
648 self.binding_manager.unsafe_rebind(var, val);
649 }
650
651 /// Push a binding onto the binding stack.
bind(&mut self, var: &Symbol, val: Term) -> PolarResult<()>652 pub fn bind(&mut self, var: &Symbol, val: Term) -> PolarResult<()> {
653 if self.log {
654 self.print(&format!("⇒ bind: {} ← {}", var.to_polar(), val.to_polar()));
655 }
656
657 self.binding_manager.bind(var, val)
658 }
659
add_binding_follower(&mut self) -> FollowerId660 pub fn add_binding_follower(&mut self) -> FollowerId {
661 self.binding_manager.add_follower(BindingManager::new())
662 }
663
remove_binding_follower(&mut self, follower_id: &FollowerId) -> Option<BindingManager>664 pub fn remove_binding_follower(&mut self, follower_id: &FollowerId) -> Option<BindingManager> {
665 self.binding_manager.remove_follower(&follower_id)
666 }
667
668 /// Add a single constraint operation to the variables referenced in it.
669 /// Precondition: Operation is either binary or ternary (binary + result var),
670 /// and at least one of the first two arguments is an unbound variable.
add_constraint(&mut self, term: &Term) -> PolarResult<()>671 fn add_constraint(&mut self, term: &Term) -> PolarResult<()> {
672 if self.log {
673 self.print(&format!("⇒ add_constraint: {}", term.to_polar()));
674 }
675
676 self.binding_manager.add_constraint(term)
677 }
678
679 /// Augment the bindings stack with constants from a hash map.
680 /// There must be no temporaries bound yet.
bind_constants(&mut self, bindings: Bindings)681 pub fn bind_constants(&mut self, bindings: Bindings) {
682 assert_eq!(self.bsp(), self.csp);
683 for (var, value) in bindings.iter() {
684 self.bind(var, value.clone()).unwrap();
685 }
686 self.csp = self.bsp();
687 }
688
689 /// Retrieve the current non-constant bindings as a hash map.
bindings(&self, include_temps: bool) -> Bindings690 pub fn bindings(&self, include_temps: bool) -> Bindings {
691 self.binding_manager
692 .bindings_after(include_temps, &self.csp)
693 }
694
695 /// Retrive internal binding stack for debugger.
bindings_debug(&self) -> &BindingStack696 pub fn bindings_debug(&self) -> &BindingStack {
697 self.binding_manager.bindings_debug()
698 }
699
700 /// Returns bindings for all vars used by terms in terms.
relevant_bindings(&self, terms: &[&Term]) -> Bindings701 pub fn relevant_bindings(&self, terms: &[&Term]) -> Bindings {
702 let mut variables = HashSet::new();
703 for t in terms {
704 t.variables(&mut variables);
705 }
706 self.binding_manager.variable_bindings(&variables)
707 }
708
709 /// Return the current binding stack pointer.
bsp(&self) -> Bsp710 fn bsp(&self) -> Bsp {
711 self.binding_manager.bsp()
712 }
713
714 /// Investigate the state of a variable at some point and return a variable state variant.
variable_state_at_point(&self, variable: &Symbol, bsp: &Bsp) -> VariableState715 pub fn variable_state_at_point(&self, variable: &Symbol, bsp: &Bsp) -> VariableState {
716 self.binding_manager.variable_state_at_point(variable, bsp)
717 }
718
719 /// Investigate the current state of a variable and return a variable state variant.
variable_state(&self, variable: &Symbol) -> VariableState720 pub fn variable_state(&self, variable: &Symbol) -> VariableState {
721 self.binding_manager.variable_state(variable)
722 }
723
724 /// Recursively dereference variables in a term, including subterms, except operations.
deep_deref(&self, term: &Term) -> Term725 fn deep_deref(&self, term: &Term) -> Term {
726 self.binding_manager.deep_deref(term)
727 }
728
729 /// Recursively dereference variables, but do not descend into (most) subterms.
730 /// The exception is for lists, so that we can correctly handle rest variables.
731 /// We also support cycle detection, in which case we return the original term.
deref(&self, term: &Term) -> Term732 fn deref(&self, term: &Term) -> Term {
733 self.binding_manager.deref(term)
734 }
735
736 /// Generate a fresh set of variables for a rule.
rename_rule_vars(&self, rule: &Rule) -> Rule737 fn rename_rule_vars(&self, rule: &Rule) -> Rule {
738 let kb = &*self.kb.read().unwrap();
739 let mut renamer = Renamer::new(&kb);
740 renamer.fold_rule(rule.clone())
741 }
742
743 /// Push or print a message to the output stream.
744 #[cfg(not(target_arch = "wasm32"))]
print<S: Into<String>>(&self, message: S)745 fn print<S: Into<String>>(&self, message: S) {
746 let message = message.into();
747 if self.polar_log_stderr {
748 eprintln!("{}", message);
749 } else {
750 self.messages.push(MessageKind::Print, message);
751 }
752 }
753
754 /// Push or print a message to the WASM output stream.
755 #[cfg(target_arch = "wasm32")]
print<S: Into<String>>(&self, message: S)756 fn print<S: Into<String>>(&self, message: S) {
757 let message = message.into();
758 if self.polar_log_stderr {
759 console_error(&message);
760 } else {
761 self.messages.push(MessageKind::Print, message);
762 }
763 }
764
log(&self, message: &str, terms: &[&Term])765 fn log(&self, message: &str, terms: &[&Term]) {
766 self.log_with(|| message, terms)
767 }
768
log_with<F, R>(&self, message_fn: F, terms: &[&Term]) where F: FnOnce() -> R, R: AsRef<str>,769 fn log_with<F, R>(&self, message_fn: F, terms: &[&Term])
770 where
771 F: FnOnce() -> R,
772 R: AsRef<str>,
773 {
774 if self.polar_log && !self.polar_log_mute {
775 let mut indent = String::new();
776 for _ in 0..=self.queries.len() {
777 indent.push_str(" ");
778 }
779 let message = message_fn();
780 let lines = message.as_ref().split('\n').collect::<Vec<&str>>();
781 if let Some(line) = lines.first() {
782 let mut msg = format!("[debug] {}{}", &indent, line);
783 if !terms.is_empty() {
784 let relevant_bindings = self.relevant_bindings(terms);
785 msg.push_str(&format!(
786 ", BINDINGS: {{{}}}",
787 relevant_bindings
788 .iter()
789 .map(|(var, val)| format!("{} = {}", var.0, val.to_polar()))
790 .collect::<Vec<String>>()
791 .join(", ")
792 ));
793 }
794 self.print(msg);
795 for line in &lines[1..] {
796 self.print(format!("[debug] {}{}", &indent, line));
797 }
798 }
799 }
800 }
801
source(&self, term: &Term) -> Option<Source>802 pub fn source(&self, term: &Term) -> Option<Source> {
803 term.get_source_id()
804 .and_then(|id| self.kb.read().unwrap().sources.get_source(id))
805 }
806
807 /// Get the query stack as a string for printing in error messages.
stack_trace(&self) -> String808 pub fn stack_trace(&self) -> String {
809 let mut trace_stack = self.trace_stack.clone();
810 let mut trace = self.trace.clone();
811
812 // Build linear stack from trace tree. Not just using query stack because it doesn't
813 // know about rules, query stack should really use this too.
814 let mut stack = vec![];
815 while let Some(t) = trace.last() {
816 stack.push(t.clone());
817 trace = trace_stack
818 .pop()
819 .map(|ts| ts.as_ref().clone())
820 .unwrap_or_else(Vec::new);
821 }
822
823 stack.reverse();
824
825 let mut st = String::new();
826 let _ = write!(st, "trace (most recent evaluation last):");
827
828 let mut rule = None;
829 for t in stack {
830 match &t.node {
831 Node::Rule(r) => {
832 rule = Some(r.clone());
833 }
834 Node::Term(t) => {
835 if matches!(t.value(), Value::Expression(Operation { operator: Operator::And, args}) if args.len() == 1)
836 {
837 continue;
838 }
839 let _ = write!(st, "\n ");
840
841 if let Some(source) = self.source(t) {
842 if let Some(rule) = &rule {
843 let _ = write!(st, "in rule {} ", rule.name.to_polar());
844 } else {
845 let _ = write!(st, "in query ");
846 }
847 let (row, column) = loc_to_pos(&source.src, t.offset());
848 let _ = write!(st, "at line {}, column {}", row + 1, column + 1);
849 if let Some(filename) = source.filename {
850 let _ = write!(st, " in file {}", filename);
851 }
852 let _ = writeln!(st);
853 };
854 let _ = write!(st, " {}", self.term_source(t, false));
855 }
856 }
857 }
858 st
859 }
860
861 #[cfg(not(target_arch = "wasm32"))]
check_timeout(&self) -> PolarResult<()>862 fn check_timeout(&self) -> PolarResult<()> {
863 // TODO (dhatch): How do we reliably not do this when debugging.
864
865 let now = std::time::Instant::now();
866 let start_time = self
867 .query_start_time
868 .expect("Query start time not recorded");
869
870 if now - start_time > self.query_timeout {
871 return Err(error::RuntimeError::QueryTimeout {
872 msg: format!(
873 "Query running for {}. Exceeded query timeout of {} seconds",
874 (now - start_time).as_secs(),
875 self.query_timeout.as_secs()
876 ),
877 }
878 .into());
879 }
880
881 Ok(())
882 }
883
884 #[cfg(target_arch = "wasm32")]
check_timeout(&self) -> PolarResult<()>885 fn check_timeout(&self) -> PolarResult<()> {
886 let now = js_sys::Date::now();
887 let start_time = self
888 .query_start_time
889 .expect("Query start time not recorded");
890
891 if now - start_time > self.query_timeout {
892 return Err(error::RuntimeError::QueryTimeout {
893 msg: format!(
894 "Query running for {}. Exceeded query timeout of {} seconds",
895 (now - start_time) / 1_000.0,
896 self.query_timeout / 1_000.0
897 ),
898 }
899 .into());
900 }
901
902 Ok(())
903 }
904 }
905
906 /// Implementations of instructions.
907 impl PolarVirtualMachine {
908 /// Remove all bindings after the last choice point, and try the
909 /// next available alternative. If no choice is possible, halt.
backtrack(&mut self) -> PolarResult<()>910 fn backtrack(&mut self) -> PolarResult<()> {
911 if self.log {
912 self.print("⇒ backtrack");
913 }
914 self.log("BACKTRACK", &[]);
915
916 loop {
917 match self.choices.pop() {
918 None => return self.push_goal(Goal::Halt),
919 Some(Choice {
920 mut alternatives,
921 bsp,
922 goals,
923 queries,
924 trace,
925 trace_stack,
926 }) => {
927 self.binding_manager.backtrack(&bsp);
928 if let Some(mut alternative) = alternatives.pop() {
929 if alternatives.is_empty() {
930 self.goals = goals;
931 self.queries = queries;
932 self.trace = trace;
933 self.trace_stack = trace_stack;
934 } else {
935 self.goals.clone_from(&goals);
936 self.queries.clone_from(&queries);
937 self.trace.clone_from(&trace);
938 self.trace_stack.clone_from(&trace_stack);
939 self.choices.push(Choice {
940 alternatives,
941 bsp,
942 goals,
943 queries,
944 trace,
945 trace_stack,
946 })
947 }
948 self.goals.append(&mut alternative);
949 break;
950 }
951 }
952 }
953 }
954 Ok(())
955 }
956
957 /// Commit to the current choice.
cut(&mut self, index: usize)958 fn cut(&mut self, index: usize) {
959 let _ = self.choices.truncate(index);
960 }
961
962 /// Clean up the query stack after completing a query.
pop_query(&mut self)963 fn pop_query(&mut self) {
964 self.queries.pop();
965 }
966
967 /// Interact with the debugger.
debug(&mut self, message: &str) -> QueryEvent968 fn debug(&mut self, message: &str) -> QueryEvent {
969 // Query start time is reset when a debug event occurs.
970 self.query_start_time.take();
971
972 QueryEvent::Debug {
973 message: message.to_string(),
974 }
975 }
976
977 /// Halt the VM by clearing all goals and choices.
halt(&mut self) -> QueryEvent978 pub fn halt(&mut self) -> QueryEvent {
979 self.log("HALT", &[]);
980 self.goals.clear();
981 self.choices.clear();
982 assert!(self.is_halted());
983 QueryEvent::Done { result: true }
984 }
985
986 /// Comparison operator that essentially performs partial unification.
987 #[allow(clippy::many_single_char_names)]
isa(&mut self, left: &Term, right: &Term) -> PolarResult<()>988 pub fn isa(&mut self, left: &Term, right: &Term) -> PolarResult<()> {
989 self.log_with(
990 || format!("MATCHES: {} matches {}", left.to_polar(), right.to_polar()),
991 &[left, right],
992 );
993
994 match (left.value(), right.value()) {
995 (_, Value::Dictionary(_)) => unreachable!("parsed as pattern"),
996 (Value::Expression(_), _) | (_, Value::Expression(_)) => {
997 unreachable!("encountered bare expression")
998 }
999
1000 // TODO(gj): (Var, Rest) + (Rest, Var) cases might be unreachable.
1001 (Value::Variable(l), Value::Variable(r))
1002 | (Value::Variable(l), Value::RestVariable(r))
1003 | (Value::RestVariable(l), Value::Variable(r))
1004 | (Value::RestVariable(l), Value::RestVariable(r)) => {
1005 // Two variables.
1006 match (self.variable_state(l), self.variable_state(r)) {
1007 (VariableState::Bound(x), _) => self.push_goal(Goal::Isa {
1008 left: x,
1009 right: right.clone(),
1010 })?,
1011 (_, VariableState::Bound(y)) => self.push_goal(Goal::Isa {
1012 left: left.clone(),
1013 right: y,
1014 })?,
1015 (_, _) => self.add_constraint(&term!(op!(Isa, left.clone(), right.clone())))?,
1016 }
1017 }
1018 (Value::Variable(l), _) | (Value::RestVariable(l), _) => match self.variable_state(l) {
1019 VariableState::Unbound => self.push_goal(Goal::Unify {
1020 left: left.clone(),
1021 right: right.clone(),
1022 })?,
1023 VariableState::Bound(x) => self.push_goal(Goal::Isa {
1024 left: x,
1025 right: right.clone(),
1026 })?,
1027 _ => self.isa_expr(left, right)?,
1028 },
1029 (_, Value::Variable(r)) | (_, Value::RestVariable(r)) => match self.variable_state(r) {
1030 VariableState::Unbound => self.push_goal(Goal::Unify {
1031 left: left.clone(),
1032 right: right.clone(),
1033 })?,
1034 VariableState::Bound(y) => self.push_goal(Goal::Isa {
1035 left: left.clone(),
1036 right: y,
1037 })?,
1038 _ => self.isa_expr(left, right)?,
1039 },
1040
1041 (Value::List(left), Value::List(right)) => {
1042 self.unify_lists(left, right, |(left, right)| Goal::Isa {
1043 left: left.clone(),
1044 right: right.clone(),
1045 })?;
1046 }
1047
1048 (Value::Dictionary(left), Value::Pattern(Pattern::Dictionary(right))) => {
1049 // Check that the left is more specific than the right.
1050 let left_fields: HashSet<&Symbol> = left.fields.keys().collect();
1051 let right_fields: HashSet<&Symbol> = right.fields.keys().collect();
1052 if !right_fields.is_subset(&left_fields) {
1053 return self.push_goal(Goal::Backtrack);
1054 }
1055
1056 // For each field on the right, isa its value against the corresponding value on
1057 // the left.
1058 for (k, v) in right.fields.iter() {
1059 let left = left
1060 .fields
1061 .get(&k)
1062 .expect("left fields should be a superset of right fields")
1063 .clone();
1064 self.push_goal(Goal::Isa {
1065 left,
1066 right: v.clone(),
1067 })?
1068 }
1069 }
1070
1071 (_, Value::Pattern(Pattern::Dictionary(right))) => {
1072 // For each field in the dict, look up the corresponding field on the instance and
1073 // then isa them.
1074 for (field, right_value) in right.fields.iter() {
1075 // Generate symbol for the lookup result and leave the variable unbound, so that unification with the result does not fail.
1076 // Unification with the lookup result happens in `fn external_call_result()`.
1077 let answer = self.kb.read().unwrap().gensym("isa_value");
1078 let call_id = self.new_call_id(&answer);
1079
1080 let lookup = Goal::LookupExternal {
1081 instance: left.clone(),
1082 call_id,
1083 field: right_value.clone_with_value(Value::String(field.0.clone())),
1084 };
1085 let isa = Goal::Isa {
1086 left: Term::new_temporary(Value::Variable(answer)),
1087 right: right_value.clone(),
1088 };
1089 self.append_goals(vec![lookup, isa])?;
1090 }
1091 }
1092
1093 (_, Value::Pattern(Pattern::Instance(right_literal))) => {
1094 // Check fields
1095 self.push_goal(Goal::Isa {
1096 left: left.clone(),
1097 right: right.clone_with_value(Value::Pattern(Pattern::Dictionary(
1098 right_literal.fields.clone(),
1099 ))),
1100 })?;
1101 // Check class
1102 self.push_goal(Goal::IsaExternal {
1103 instance: left.clone(),
1104 literal: right_literal.clone(),
1105 })?;
1106 }
1107
1108 // Default case: x isa y if x = y.
1109 _ => self.push_goal(Goal::Unify {
1110 left: left.clone(),
1111 right: right.clone(),
1112 })?,
1113 }
1114 Ok(())
1115 }
1116
isa_expr(&mut self, left: &Term, right: &Term) -> PolarResult<()>1117 fn isa_expr(&mut self, left: &Term, right: &Term) -> PolarResult<()> {
1118 match right.value() {
1119 Value::Pattern(Pattern::Dictionary(fields)) => {
1120 // Produce a constraint like left.field = value
1121 let to_unify = |(field, value): (&Symbol, &Term)| -> Term {
1122 let value = self.deref(value);
1123 let field = right.clone_with_value(value!(field.0.as_ref()));
1124 let left = left.clone_with_value(value!(op!(Dot, left.clone(), field)));
1125 let unify = op!(Unify, left, value);
1126 term!(unify)
1127 };
1128
1129 let constraints = fields.fields.iter().rev().map(to_unify).collect::<Vec<_>>();
1130 for op in constraints {
1131 self.add_constraint(&op)?;
1132 }
1133 }
1134 Value::Pattern(Pattern::Instance(InstanceLiteral { fields, tag })) => {
1135 // TODO(gj): assert that a simplified expression contains at most 1 unification
1136 // involving a particular variable.
1137 // TODO(gj): Ensure `op!(And) matches X{}` doesn't die after these changes.
1138 let var = left.value().as_symbol()?;
1139
1140 // Get the existing partial on the LHS variable.
1141 let partial = self.binding_manager.get_constraints(var);
1142
1143 let mut hs = HashSet::with_capacity(1);
1144 hs.insert(var.clone());
1145
1146 let (simplified, _) = simplify_partial(var, partial.into_term(), hs, false);
1147 let simplified = simplified.value().as_expression()?;
1148
1149 // TODO (dhatch): what if there is more than one var = dot_op constraint?
1150 // What if the one there is is in a not, or an or, or something
1151 let lhs_of_matches = simplified
1152 .constraints()
1153 .into_iter()
1154 .find_map(|c| {
1155 // If the simplified partial includes a `var = dot_op` constraint, use the
1156 // dot op as the LHS of the matches.
1157 if c.operator != Operator::Unify {
1158 None
1159 } else if &c.args[0] == left &&
1160 matches!(c.args[1].value().as_expression(), Ok(o) if o.operator == Operator::Dot) {
1161 Some(c.args[1].clone())
1162 } else if &c.args[1] == left &&
1163 matches!(c.args[0].value().as_expression(), Ok(o) if o.operator == Operator::Dot) {
1164 Some(c.args[0].clone())
1165 } else {
1166 None
1167 }
1168 })
1169 .unwrap_or_else(|| left.clone());
1170
1171 // Construct field-less matches operation.
1172 let tag_pattern = right.clone_with_value(value!(pattern!(instance!(tag.clone()))));
1173 let type_constraint = op!(Isa, left.clone(), tag_pattern);
1174
1175 let new_matches = op!(Isa, lhs_of_matches, right.clone());
1176 let runnable = Box::new(IsaConstraintCheck::new(
1177 simplified.constraints(),
1178 new_matches,
1179 ));
1180
1181 // Construct field constraints.
1182 let field_constraints = fields.fields.iter().rev().map(|(f, v)| {
1183 let v = self.deref(v);
1184 let field = right.clone_with_value(value!(f.0.as_ref()));
1185 let left = left.clone_with_value(value!(op!(Dot, left.clone(), field)));
1186 op!(Unify, left, v)
1187 });
1188
1189 let mut add_constraints = vec![type_constraint];
1190 add_constraints.extend(field_constraints.into_iter());
1191
1192 // Run compatibility check.
1193 self.choose_conditional(
1194 vec![Goal::Run { runnable }],
1195 add_constraints
1196 .into_iter()
1197 .map(|op| Goal::AddConstraint {
1198 term: op.into_term(),
1199 })
1200 .collect(),
1201 vec![Goal::CheckError, Goal::Backtrack],
1202 )?;
1203 }
1204 _ => self.add_constraint(&op!(Unify, left.clone(), right.clone()).into_term())?,
1205 }
1206 Ok(())
1207 }
1208
lookup(&mut self, dict: &Dictionary, field: &Term, value: &Term) -> PolarResult<()>1209 pub fn lookup(&mut self, dict: &Dictionary, field: &Term, value: &Term) -> PolarResult<()> {
1210 let field = self.deref(field);
1211 match field.value() {
1212 Value::Variable(_) => {
1213 let mut alternatives = vec![];
1214 for (k, v) in &dict.fields {
1215 let mut goals: Goals = vec![];
1216 // attempt to unify dict key with field
1217 // if `field` is bound, unification will only succeed for the matching key
1218 // if `field` is unbound, unification will succeed for all keys
1219 goals.push(Goal::Unify {
1220 left: field.clone_with_value(Value::String(k.clone().0)),
1221 right: field.clone(),
1222 });
1223 // attempt to unify dict value with result
1224 goals.push(Goal::Unify {
1225 left: v.clone(),
1226 right: value.clone(),
1227 });
1228 alternatives.push(goals);
1229 }
1230 self.choose(alternatives)?;
1231 }
1232 Value::String(field) => {
1233 if let Some(retrieved) = dict.fields.get(&Symbol(field.clone())) {
1234 self.push_goal(Goal::Unify {
1235 left: retrieved.clone(),
1236 right: value.clone(),
1237 })?;
1238 } else {
1239 self.push_goal(Goal::Backtrack)?;
1240 }
1241 }
1242 v => {
1243 return Err(self.type_error(
1244 &field,
1245 format!("cannot look up field {:?} on a dictionary", v),
1246 ))
1247 }
1248 };
1249 Ok(())
1250 }
1251
1252 /// Return an external call event to look up a field's value
1253 /// in an external instance. Push a `Goal::LookupExternal` as
1254 /// an alternative on the last choice point to poll for results.
lookup_external( &mut self, call_id: u64, instance: &Term, field: &Term, ) -> PolarResult<QueryEvent>1255 pub fn lookup_external(
1256 &mut self,
1257 call_id: u64,
1258 instance: &Term,
1259 field: &Term,
1260 ) -> PolarResult<QueryEvent> {
1261 let (field_name, args, kwargs): (
1262 Symbol,
1263 Option<Vec<Term>>,
1264 Option<BTreeMap<Symbol, Term>>,
1265 ) = match self.deref(field).value() {
1266 Value::Call(Call { name, args, kwargs }) => (
1267 name.clone(),
1268 Some(args.iter().map(|arg| self.deep_deref(arg)).collect()),
1269 kwargs.as_ref().map(|unwrapped| {
1270 unwrapped
1271 .iter()
1272 .map(|(k, v)| (k.to_owned(), self.deep_deref(v)))
1273 .collect()
1274 }),
1275 ),
1276 Value::String(field) => (Symbol(field.clone()), None, None),
1277 v => {
1278 return Err(self.type_error(
1279 &field,
1280 format!("cannot look up field {:?} on an external instance", v),
1281 ))
1282 }
1283 };
1284
1285 // add an empty choice point; lookups return only one value
1286 // but we'll want to cut if we get back nothing
1287 self.push_choice(vec![]);
1288
1289 self.log_with(
1290 || {
1291 let mut msg = format!("LOOKUP: {}.{}", instance.to_string(), field_name);
1292 msg.push('(');
1293 let args = args
1294 .clone()
1295 .unwrap_or_else(Vec::new)
1296 .into_iter()
1297 .map(|a| a.to_polar());
1298 let kwargs = kwargs
1299 .clone()
1300 .unwrap_or_else(BTreeMap::new)
1301 .into_iter()
1302 .map(|(k, v)| format!("{}: {}", k, v.to_polar()));
1303 msg.push_str(&args.chain(kwargs).collect::<Vec<String>>().join(", "));
1304 msg.push(')');
1305 msg
1306 },
1307 &[],
1308 );
1309
1310 Ok(QueryEvent::ExternalCall {
1311 call_id,
1312 instance: self.deep_deref(instance),
1313 attribute: field_name,
1314 args,
1315 kwargs,
1316 })
1317 }
1318
isa_external( &mut self, instance: &Term, literal: &InstanceLiteral, ) -> PolarResult<QueryEvent>1319 pub fn isa_external(
1320 &mut self,
1321 instance: &Term,
1322 literal: &InstanceLiteral,
1323 ) -> PolarResult<QueryEvent> {
1324 let (call_id, answer) = self.new_call_var("isa", Value::Boolean(false));
1325 self.push_goal(Goal::Unify {
1326 left: answer,
1327 right: Term::new_temporary(Value::Boolean(true)),
1328 })?;
1329
1330 Ok(QueryEvent::ExternalIsa {
1331 call_id,
1332 instance: self.deep_deref(instance),
1333 class_tag: literal.tag.clone(),
1334 })
1335 }
1336
next_external(&mut self, call_id: u64, iterable: &Term) -> PolarResult<QueryEvent>1337 pub fn next_external(&mut self, call_id: u64, iterable: &Term) -> PolarResult<QueryEvent> {
1338 // add another choice point for the next result
1339 self.push_choice(vec![vec![Goal::NextExternal {
1340 call_id,
1341 iterable: iterable.clone(),
1342 }]]);
1343
1344 Ok(QueryEvent::NextExternal {
1345 call_id,
1346 iterable: iterable.clone(),
1347 })
1348 }
1349
unify_external( &mut self, left_instance_id: u64, right_instance_id: u64, ) -> PolarResult<QueryEvent>1350 pub fn unify_external(
1351 &mut self,
1352 left_instance_id: u64,
1353 right_instance_id: u64,
1354 ) -> PolarResult<QueryEvent> {
1355 let (call_id, answer) = self.new_call_var("unify", Value::Boolean(false));
1356 self.push_goal(Goal::Unify {
1357 left: answer,
1358 right: Term::new_temporary(Value::Boolean(true)),
1359 })?;
1360
1361 Ok(QueryEvent::ExternalUnify {
1362 call_id,
1363 left_instance_id,
1364 right_instance_id,
1365 })
1366 }
1367
make_external(&self, constructor: &Term, instance_id: u64) -> QueryEvent1368 pub fn make_external(&self, constructor: &Term, instance_id: u64) -> QueryEvent {
1369 QueryEvent::MakeExternal {
1370 instance_id,
1371 constructor: self.deep_deref(&constructor),
1372 }
1373 }
1374
check_error(&self) -> PolarResult<QueryEvent>1375 pub fn check_error(&self) -> PolarResult<QueryEvent> {
1376 if let Some(error) = &self.external_error {
1377 let term = match self.trace.last().map(|t| t.node.clone()) {
1378 Some(Node::Term(t)) => Some(t),
1379 _ => None,
1380 };
1381 let stack_trace = self.stack_trace();
1382 let error = error::RuntimeError::Application {
1383 msg: error.clone(),
1384 stack_trace: Some(stack_trace),
1385 };
1386 if let Some(term) = term {
1387 Err(self.set_error_context(&term, error))
1388 } else {
1389 Err(error.into())
1390 }
1391 } else {
1392 Ok(QueryEvent::None)
1393 }
1394 }
1395
1396 /// Query for the provided term.
1397 ///
1398 /// Uses the knowledge base to get an ordered list of rules.
1399 /// Creates a choice point over each rule, where each alternative
1400 /// consists of unifying the rule head with the arguments, then
1401 /// querying for each body clause.
query(&mut self, term: &Term) -> PolarResult<QueryEvent>1402 fn query(&mut self, term: &Term) -> PolarResult<QueryEvent> {
1403 // Don't log if it's just a single element AND like lots of rule bodies tend to be.
1404 match &term.value() {
1405 Value::Expression(Operation {
1406 operator: Operator::And,
1407 args,
1408 }) if args.len() < 2 => (),
1409 _ => {
1410 self.log_with(|| format!("QUERY: {}", term.to_polar()), &[term]);
1411 }
1412 };
1413
1414 self.queries.push(term.clone());
1415 self.push_goal(Goal::PopQuery { term: term.clone() })?;
1416 self.trace.push(Rc::new(Trace {
1417 node: Node::Term(term.clone()),
1418 children: vec![],
1419 }));
1420
1421 match &term.value() {
1422 Value::Call(predicate) => {
1423 self.query_for_predicate(predicate.clone())?;
1424 }
1425 Value::Expression(_) => {
1426 return self.query_for_operation(&term);
1427 }
1428 Value::Variable(_a_symbol) => {
1429 let val = self.deref(term);
1430
1431 if val == *term {
1432 // variable was unbound
1433 // apply a constraint to variable that it must be truthy
1434 self.push_goal(Goal::Unify {
1435 left: term.clone(),
1436 right: term!(true),
1437 })?;
1438 } else {
1439 self.push_goal(Goal::Query { term: val })?;
1440 }
1441 }
1442 Value::Boolean(value) => {
1443 if !value {
1444 // Backtrack if the boolean is false.
1445 self.push_goal(Goal::Backtrack)?;
1446 }
1447
1448 return Ok(QueryEvent::None);
1449 }
1450 _ => {
1451 // everything else dies horribly and in pain
1452 return Err(self.type_error(
1453 &term,
1454 format!(
1455 "{} isn't something that is true or false so can't be a condition",
1456 term.value().to_polar()
1457 ),
1458 ));
1459 }
1460 }
1461 Ok(QueryEvent::None)
1462 }
1463
1464 /// Select applicable rules for predicate.
1465 /// Sort applicable rules by specificity.
1466 /// Create a choice over the applicable rules.
query_for_predicate(&mut self, predicate: Call) -> PolarResult<()>1467 fn query_for_predicate(&mut self, predicate: Call) -> PolarResult<()> {
1468 assert!(predicate.kwargs.is_none());
1469 let goals = match self.kb.read().unwrap().rules.get(&predicate.name) {
1470 None => vec![Goal::Backtrack],
1471 Some(generic_rule) => {
1472 assert_eq!(generic_rule.name, predicate.name);
1473
1474 // Pre-filter rules.
1475 let args = predicate.args.iter().map(|t| self.deep_deref(t)).collect();
1476 let pre_filter = generic_rule.get_applicable_rules(&args);
1477
1478 self.polar_log_mute = true;
1479
1480 // Filter rules by applicability.
1481 vec![
1482 Goal::TraceStackPush,
1483 Goal::FilterRules {
1484 applicable_rules: vec![],
1485 unfiltered_rules: pre_filter,
1486 args: predicate.args,
1487 },
1488 Goal::TraceStackPop,
1489 ]
1490 }
1491 };
1492 self.append_goals(goals)
1493 }
1494
query_for_operation(&mut self, term: &Term) -> PolarResult<QueryEvent>1495 fn query_for_operation(&mut self, term: &Term) -> PolarResult<QueryEvent> {
1496 let operation = term.value().as_expression().unwrap();
1497 let mut args = operation.args.clone();
1498 match operation.operator {
1499 Operator::And => {
1500 // Query for each conjunct.
1501 self.push_goal(Goal::TraceStackPop)?;
1502 self.append_goals(args.into_iter().map(|term| Goal::Query { term }))?;
1503 self.push_goal(Goal::TraceStackPush)?;
1504 }
1505 Operator::Or => {
1506 // Make an alternative Query for each disjunct.
1507 self.choose(args.into_iter().map(|term| vec![Goal::Query { term }]))?;
1508 }
1509 Operator::Not => {
1510 // Query in a sub-VM and invert the results.
1511 assert_eq!(args.len(), 1);
1512 let term = args.pop().unwrap();
1513 let add_constraints = Rc::new(RefCell::new(Bindings::new()));
1514 let inverter = Box::new(Inverter::new(
1515 self,
1516 vec![Goal::Query { term }],
1517 add_constraints.clone(),
1518 self.bsp(),
1519 ));
1520 self.choose_conditional(
1521 vec![Goal::Run { runnable: inverter }],
1522 vec![Goal::AddConstraintsBatch { add_constraints }],
1523 vec![Goal::Backtrack],
1524 )?;
1525 }
1526 Operator::Assign => {
1527 assert_eq!(args.len(), 2);
1528 let right = args.pop().unwrap();
1529 let left = args.pop().unwrap();
1530 match (left.value(), right.value()) {
1531 (Value::Variable(var), _) => match self.variable_state(var) {
1532 VariableState::Unbound => {
1533 self.push_goal(Goal::Unify { left, right })?;
1534 }
1535 _ => {
1536 return Err(self.type_error(
1537 &left,
1538 format!(
1539 "Can only assign to unbound variables, {} is not unbound.",
1540 var.to_polar()
1541 ),
1542 ));
1543 }
1544 },
1545 _ => {
1546 return Err(self.type_error(
1547 &left,
1548 format!("Cannot assign to type {}.", left.to_polar()),
1549 ))
1550 }
1551 }
1552 }
1553
1554 Operator::Unify => {
1555 // Push a `Unify` goal
1556 assert_eq!(args.len(), 2);
1557 let right = args.pop().unwrap();
1558 let left = args.pop().unwrap();
1559 self.push_goal(Goal::Unify { left, right })?
1560 }
1561 Operator::Dot => {
1562 return self.query_op_helper(term, Self::dot_op_helper, false, false);
1563 }
1564
1565 Operator::Lt
1566 | Operator::Gt
1567 | Operator::Leq
1568 | Operator::Geq
1569 | Operator::Eq
1570 | Operator::Neq => {
1571 return self.query_op_helper(term, Self::comparison_op_helper, true, true);
1572 }
1573
1574 Operator::Add
1575 | Operator::Sub
1576 | Operator::Mul
1577 | Operator::Div
1578 | Operator::Mod
1579 | Operator::Rem => {
1580 return self.query_op_helper(term, Self::arithmetic_op_helper, true, true);
1581 }
1582
1583 Operator::In => {
1584 return self.query_op_helper(term, Self::in_op_helper, false, true);
1585 }
1586
1587 Operator::Debug => {
1588 let mut message = "".to_string();
1589 if !args.is_empty() {
1590 message += &format!(
1591 "debug({})",
1592 args.iter()
1593 .map(|arg| self.deref(arg).to_polar())
1594 .collect::<Vec<String>>()
1595 .join(", ")
1596 );
1597 }
1598 if let Some(debug_goal) = self.debugger.break_query(&self) {
1599 self.goals.push(debug_goal);
1600 } else {
1601 self.push_goal(Goal::Debug {
1602 message: "".to_owned(),
1603 })?
1604 }
1605 }
1606 Operator::Print => {
1607 self.print(
1608 &args
1609 .iter()
1610 .map(|arg| self.deref(arg).to_polar())
1611 .collect::<Vec<String>>()
1612 .join(", "),
1613 );
1614 }
1615 Operator::New => {
1616 assert_eq!(args.len(), 2);
1617 let result = args.pop().unwrap();
1618 assert!(
1619 matches!(result.value(), Value::Variable(_)),
1620 "Must have result variable as second arg."
1621 );
1622 let constructor = args.pop().unwrap();
1623
1624 let instance_id = self.new_id();
1625 let instance =
1626 constructor.clone_with_value(Value::ExternalInstance(ExternalInstance {
1627 instance_id,
1628 constructor: Some(constructor.clone()),
1629 repr: Some(constructor.to_polar()),
1630 }));
1631
1632 // A goal is used here in case the result is already bound to some external
1633 // instance.
1634 self.append_goals(vec![
1635 Goal::Unify {
1636 left: result,
1637 right: instance,
1638 },
1639 Goal::MakeExternal {
1640 instance_id,
1641 constructor,
1642 },
1643 ])?;
1644 }
1645 Operator::Cut => {
1646 if self.query_contains_partial {
1647 return Err(self.set_error_context(
1648 &term,
1649 error::RuntimeError::Unsupported {
1650 msg: "cannot use cut with partial evaluation".to_string(),
1651 },
1652 ));
1653 }
1654
1655 // Remove all choices created before this cut that are in the
1656 // current rule body.
1657 let mut choice_index = self.choices.len();
1658 for choice in self.choices.iter().rev() {
1659 // Comparison excludes the rule body & cut operator (the last two elements of self.queries)
1660 let prefix = &self.queries[..(self.queries.len() - 2)];
1661 if choice.queries.starts_with(prefix) {
1662 // If the choice has the same query stack as the current
1663 // query stack, remove it.
1664 choice_index -= 1;
1665 } else {
1666 break;
1667 }
1668 }
1669
1670 self.push_goal(Goal::Cut { choice_index })?;
1671 }
1672 Operator::Isa => {
1673 // TODO (dhatch): Use query op helper.
1674 assert_eq!(args.len(), 2);
1675 let right = args.pop().unwrap();
1676 let left = args.pop().unwrap();
1677 self.push_goal(Goal::Isa { left, right })?
1678 }
1679 Operator::ForAll => {
1680 assert_eq!(args.len(), 2);
1681 let action = args.pop().unwrap();
1682 let condition = args.pop().unwrap();
1683 // For all is implemented as !(condition, !action).
1684 let op = Operation {
1685 operator: Operator::Not,
1686 args: vec![term.clone_with_value(Value::Expression(Operation {
1687 operator: Operator::And,
1688 args: vec![
1689 condition,
1690 term.clone_with_value(Value::Expression(Operation {
1691 operator: Operator::Not,
1692 args: vec![action],
1693 })),
1694 ],
1695 }))],
1696 };
1697 let double_negation = term.clone_with_value(Value::Expression(op));
1698 self.push_goal(Goal::Query {
1699 term: double_negation,
1700 })?;
1701 }
1702 }
1703 Ok(QueryEvent::None)
1704 }
1705
1706 /// Handle variables & constraints as arguments to various operations.
1707 /// Calls the `eval` method to handle ground terms.
1708 ///
1709 /// Arguments:
1710 ///
1711 /// - handle_unbound_left_var: If set to `false`, allow `eval` to handle
1712 /// operations with an unbound left variable, instead of adding a constraint.
1713 /// Some operations, like `In`, emit new goals or choice points when the left
1714 /// operand is a variable.
1715 /// - handle_unbound_right_var: Same as above but for the RHS. `Dot` uses this.
1716 #[allow(clippy::many_single_char_names)]
query_op_helper<F>( &mut self, term: &Term, eval: F, handle_unbound_left_var: bool, handle_unbound_right_var: bool, ) -> PolarResult<QueryEvent> where F: Fn(&mut Self, &Term) -> PolarResult<QueryEvent>,1717 fn query_op_helper<F>(
1718 &mut self,
1719 term: &Term,
1720 eval: F,
1721 handle_unbound_left_var: bool,
1722 handle_unbound_right_var: bool,
1723 ) -> PolarResult<QueryEvent>
1724 where
1725 F: Fn(&mut Self, &Term) -> PolarResult<QueryEvent>,
1726 {
1727 let Operation { operator: op, args } = term.value().as_expression().unwrap();
1728
1729 let mut args = args.clone();
1730 assert!(args.len() >= 2);
1731 let left = &args[0];
1732 let right = &args[1];
1733
1734 match (left.value(), right.value()) {
1735 (Value::Expression(_), _)
1736 | (_, Value::Expression(_))
1737 | (Value::RestVariable(_), _)
1738 | (_, Value::RestVariable(_)) => {
1739 panic!("invalid query");
1740 }
1741 _ => {}
1742 };
1743
1744 if let Value::Variable(r) = right.value() {
1745 if let VariableState::Bound(x) = self.variable_state(r) {
1746 args[1] = x;
1747 self.push_goal(Goal::Query {
1748 term: term.clone_with_value(Value::Expression(Operation {
1749 operator: *op,
1750 args,
1751 })),
1752 })?;
1753 return Ok(QueryEvent::None);
1754 } else if !handle_unbound_right_var && left.value().as_symbol().is_err() {
1755 return eval(self, term);
1756 }
1757 }
1758
1759 if let Value::Variable(l) = left.value() {
1760 if let VariableState::Bound(x) = self.variable_state(l) {
1761 args[0] = x;
1762 self.push_goal(Goal::Query {
1763 term: term.clone_with_value(Value::Expression(Operation {
1764 operator: *op,
1765 args,
1766 })),
1767 })?;
1768 return Ok(QueryEvent::None);
1769 } else if !handle_unbound_left_var && right.value().as_symbol().is_err() {
1770 return eval(self, term);
1771 }
1772 }
1773
1774 if left.value().as_symbol().is_ok() || right.value().as_symbol().is_ok() {
1775 self.add_constraint(term)?;
1776 return Ok(QueryEvent::None);
1777 }
1778
1779 eval(self, term)
1780 }
1781
1782 /// Evaluate comparison operations.
comparison_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent>1783 fn comparison_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent> {
1784 let Operation { operator: op, args } = term.value().as_expression().unwrap();
1785
1786 assert_eq!(args.len(), 2);
1787 let left = &args[0];
1788 let right = &args[1];
1789
1790 match (left.value(), right.value()) {
1791 (Value::ExternalInstance(_), _) | (_, Value::ExternalInstance(_)) => {
1792 // Generate a symbol for the external result and bind to `false` (default).
1793 let (call_id, answer) =
1794 self.new_call_var("external_op_result", Value::Boolean(false));
1795
1796 // Check that the external result is `true` when we return.
1797 self.push_goal(Goal::Unify {
1798 left: answer,
1799 right: Term::new_temporary(Value::Boolean(true)),
1800 })?;
1801
1802 // Emit an event for the external operation.
1803 Ok(QueryEvent::ExternalOp {
1804 call_id,
1805 operator: *op,
1806 args: vec![left.clone(), right.clone()],
1807 })
1808 }
1809 _ => {
1810 if !compare(*op, left, right)? {
1811 self.push_goal(Goal::Backtrack)?;
1812 }
1813 Ok(QueryEvent::None)
1814 }
1815 }
1816 }
1817
1818 // TODO(ap, dhatch): Rewrite 3-arg arithmetic ops as 2-arg + unify,
1819 // like we do for dots; e.g., `+(a, b, c)` → `c = +(a, b)`.
1820 /// Evaluate arithmetic operations.
arithmetic_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent>1821 fn arithmetic_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent> {
1822 let Operation { operator: op, args } = term.value().as_expression().unwrap();
1823
1824 assert_eq!(args.len(), 3);
1825 let left = &args[0];
1826 let right = &args[1];
1827 let result = &args[2];
1828 assert!(matches!(result.value(), Value::Variable(_)));
1829
1830 match (left.value(), right.value()) {
1831 (Value::Number(left), Value::Number(right)) => {
1832 if let Some(answer) = match op {
1833 Operator::Add => *left + *right,
1834 Operator::Sub => *left - *right,
1835 Operator::Mul => *left * *right,
1836 Operator::Div => *left / *right,
1837 Operator::Mod => (*left).modulo(*right),
1838 Operator::Rem => *left % *right,
1839 _ => {
1840 return Err(self.set_error_context(
1841 &term,
1842 error::RuntimeError::Unsupported {
1843 msg: format!("numeric operation {}", op.to_polar()),
1844 },
1845 ));
1846 }
1847 } {
1848 self.push_goal(Goal::Unify {
1849 left: term.clone_with_value(Value::Number(answer)),
1850 right: result.clone(),
1851 })?;
1852 Ok(QueryEvent::None)
1853 } else {
1854 Err(self.set_error_context(
1855 &term,
1856 error::RuntimeError::ArithmeticError {
1857 msg: term.to_polar(),
1858 },
1859 ))
1860 }
1861 }
1862 (_, _) => Err(self.set_error_context(
1863 &term,
1864 error::RuntimeError::Unsupported {
1865 msg: format!("unsupported arithmetic operands: {}", term.to_polar()),
1866 },
1867 )),
1868 }
1869 }
1870
1871 /// Push appropriate goals for lookups on dictionaries and instances.
dot_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent>1872 fn dot_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent> {
1873 let Operation { operator: op, args } = term.value().as_expression().unwrap();
1874 assert_eq!(*op, Operator::Dot, "expected a dot operation");
1875
1876 let mut args = args.clone();
1877 assert_eq!(args.len(), 3);
1878 let object = &args[0];
1879 let field = &args[1];
1880 let value = &args[2];
1881
1882 match object.value() {
1883 // Push a `Lookup` goal for simple field lookups on dictionaries.
1884 Value::Dictionary(dict)
1885 if matches!(field.value(), Value::String(_) | Value::Variable(_)) =>
1886 {
1887 self.push_goal(Goal::Lookup {
1888 dict: dict.clone(),
1889 field: field.clone(),
1890 value: args.remove(2),
1891 })?
1892 }
1893 // Push an `ExternalLookup` goal for external instances and built-ins.
1894 Value::Dictionary(_)
1895 | Value::ExternalInstance(_)
1896 | Value::List(_)
1897 | Value::Number(_)
1898 | Value::String(_) => {
1899 // handle partial arguments to an external call
1900 if let Some(constraint_term) = self.check_partial_args(object, field, value)? {
1901 // if there is a valid partial argument, it means we have a special case handler, so don't call out to the method
1902 self.add_constraint(&constraint_term)?;
1903 return Ok(QueryEvent::None);
1904 }
1905 let answer = self.kb.read().unwrap().gensym("lookup_value");
1906 let call_id = self.new_call_id(&answer);
1907 self.append_goals(vec![
1908 Goal::Unify {
1909 left: Term::new_temporary(Value::Variable(answer)),
1910 right: value.clone(),
1911 },
1912 Goal::LookupExternal {
1913 call_id,
1914 field: field.clone(),
1915 instance: object.clone(),
1916 },
1917 Goal::CheckError,
1918 ])?;
1919 }
1920 Value::Variable(v) => {
1921 if matches!(field.value(), Value::Call(_)) {
1922 return Err(self.set_error_context(
1923 object,
1924 error::RuntimeError::Unsupported {
1925 msg: format!("cannot call method on unbound variable {}", v),
1926 },
1927 ));
1928 }
1929
1930 // Translate `.(object, field, value)` → `value = .(object, field)`.
1931 let dot2 = op!(Dot, object.clone(), field.clone());
1932 self.add_constraint(&op!(Unify, value.clone(), dot2.into_term()).into_term())?;
1933 }
1934 _ => {
1935 return Err(self.type_error(
1936 &object,
1937 format!(
1938 "can only perform lookups on dicts and instances, this is {}",
1939 object.to_polar()
1940 ),
1941 ))
1942 }
1943 }
1944 Ok(QueryEvent::None)
1945 }
1946
1947 /// Check for partially bound or unbound variable arguments to an external call.
1948 /// If any arguments are partially bound or unbound, return an error.
1949 /// The only exception is the method `OsoRoles.role_allows()`, which expects a partially bound resource argument.
1950 /// If the call is `OsoRoles.role_allows()`, return a term representing a special constraint for the method call.
check_partial_args( &self, object: &Term, field: &Term, value: &Term, ) -> PolarResult<Option<Term>>1951 fn check_partial_args(
1952 &self,
1953 object: &Term,
1954 field: &Term,
1955 value: &Term,
1956 ) -> PolarResult<Option<Term>> {
1957 // If the lookup is a `Value::Call`, then we need to check for partial args
1958 let (name, args, maybe_kwargs): (Symbol, Vec<Term>, Option<BTreeMap<Symbol, Term>>) =
1959 match self.deref(field).value() {
1960 Value::Call(Call { name, args, kwargs }) => (
1961 name.clone(),
1962 args.iter().map(|arg| self.deep_deref(arg)).collect(),
1963 kwargs.as_ref().map(|unwrapped| {
1964 unwrapped
1965 .iter()
1966 .map(|(k, v)| (k.to_owned(), self.deep_deref(v)))
1967 .collect()
1968 }),
1969 ),
1970 _ => return Ok(None),
1971 };
1972
1973 // get all partially-bound args
1974 let partial_args = args
1975 .iter()
1976 .enumerate()
1977 .filter_map(|(i, arg)| {
1978 if let Value::Variable(v) = arg.value() {
1979 match self.binding_manager.variable_state(v) {
1980 // bound variables are fine, continue
1981 VariableState::Bound(_) => None,
1982 // TODO: temporary fix so that partial variables are only fine if being passed into "role_allows"
1983 VariableState::Partial => Some(Ok((i, arg))),
1984 VariableState::Unbound => Some(Err(self.set_error_context(
1985 field,
1986 error::RuntimeError::Unsupported {
1987 msg: format!(
1988 "cannot call method {} with unbound variable argument {}",
1989 name, v
1990 ),
1991 },
1992 ))),
1993 }
1994 } else {
1995 None
1996 }
1997 })
1998 .collect::<Result<Vec<_>, _>>()?;
1999
2000 // get all partially-bound kwargs
2001 let partial_kwargs = maybe_kwargs
2002 .clone()
2003 .map(|kwargs| {
2004 kwargs
2005 .iter()
2006 .filter_map(|(key, arg)| {
2007 if let Value::Variable(v) = arg.value() {
2008 match self.binding_manager.variable_state(v) {
2009 // bound variables are fine, continue
2010 VariableState::Bound(_) => None,
2011 // TODO: temporary fix so that partial variables are only fine if being passed into "role_allows"
2012 VariableState::Partial => Some(Ok((key.clone(), arg.clone()))),
2013 VariableState::Unbound => Some(Err(self.set_error_context(
2014 field,
2015 error::RuntimeError::Unsupported {
2016 msg: format!(
2017 "cannot call method {} with unbound variable argument {}", name, v
2018 ),
2019 },
2020 ))),
2021 }
2022 } else {
2023 None
2024 }
2025 })
2026 .collect::<Result<Vec<_>, _>>()
2027 })
2028 .transpose()?.unwrap_or_else(Vec::new);
2029
2030 // If there are no partial args or kwargs, return
2031 if partial_args.len() + partial_kwargs.len() == 0 {
2032 return Ok(None);
2033 }
2034
2035 // TODO: temprorary fix--If there are partial args, they must be called on `role_allows` or `user_in_role`
2036 if let Value::ExternalInstance(external) = self.deep_deref(&object).value() {
2037 if let Some(repr) = external.repr.clone() {
2038 if repr.contains("sqlalchemy_oso.roles.OsoRoles")
2039 && (name.0 == "role_allows" || name.0 == "user_in_role")
2040 {
2041 if partial_args.len() + partial_kwargs.len() > 1 {
2042 // More than 1 partial arg results in error
2043 return Err(self.set_error_context(
2044 field,
2045 error::RuntimeError::Unsupported {
2046 msg: format!("Cannot call method {} with more than 1 partially bound argument.", name.0
2047 ),
2048 }));
2049 } else if partial_args.len() == 1 && partial_args[0].0 != 2 {
2050 // Non-resource partial arg results in error
2051 return Err(self.set_error_context(
2052 field,
2053 error::RuntimeError::Unsupported {
2054 msg: format!("Cannot call method {} with partially bound argument at index {}.", name.0, partial_args[0].0
2055 ),
2056 }));
2057 } else if partial_kwargs.len() == 1 && partial_kwargs[0].0 != sym!("resource") {
2058 return Err(self.set_error_context(
2059 field,
2060 error::RuntimeError::Unsupported {
2061 msg: format!("Cannot call method {} with partially bound argument with keyword {}.", name.0, partial_kwargs[0].0
2062 ),
2063 }));
2064 }
2065 let dot = op!(
2066 Dot,
2067 object.clone(),
2068 term!(value!(Call {
2069 name,
2070 args,
2071 kwargs: maybe_kwargs
2072 }))
2073 );
2074 let constraint_term = op!(Unify, value.clone(), dot.into_term()).into_term();
2075 return Ok(Some(constraint_term));
2076 }
2077 }
2078 }
2079 // If the call wasn't to one of the specially-allowed methods, throw an error
2080 Err(self.set_error_context(
2081 field,
2082 error::RuntimeError::Unsupported {
2083 msg: format!(
2084 "cannot call method {} with partially-bound arguments.",
2085 name,
2086 ),
2087 },
2088 ))
2089 }
2090
in_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent>2091 fn in_op_helper(&mut self, term: &Term) -> PolarResult<QueryEvent> {
2092 let Operation { args, .. } = term.value().as_expression().unwrap();
2093
2094 assert_eq!(args.len(), 2);
2095 let item = &args[0];
2096 let iterable = &args[1];
2097
2098 match (item.value(), iterable.value()) {
2099 (_, Value::List(list)) if list.is_empty() => {
2100 // Nothing is in an empty list.
2101 self.backtrack()?;
2102 }
2103 (_, Value::String(s)) if s.is_empty() => {
2104 // Nothing is in an empty string.
2105 self.backtrack()?;
2106 }
2107 (_, Value::Dictionary(d)) if d.is_empty() => {
2108 // Nothing is in an empty dict.
2109 self.backtrack()?;
2110 }
2111
2112 (_, Value::List(terms)) => {
2113 // Unify item with each element of the list, skipping non-matching ground terms.
2114 let item_is_ground = item.is_ground();
2115 self.choose(
2116 terms
2117 .iter()
2118 .filter(|term| {
2119 !item_is_ground || !term.is_ground() || term.value() == item.value()
2120 })
2121 .map(|term| {
2122 vec![Goal::Unify {
2123 left: item.clone(),
2124 right: term.clone(),
2125 }]
2126 })
2127 .collect::<Vec<Goals>>(),
2128 )?;
2129 }
2130 (_, Value::Dictionary(dict)) => {
2131 // Unify item with each (k, v) pair of the dict, skipping non-matching ground terms.
2132 let item_is_ground = item.is_ground();
2133 self.choose(
2134 dict.fields
2135 .iter()
2136 .map(|(k, v)| {
2137 iterable.clone_with_value(Value::List(vec![
2138 v.clone_with_value(Value::String(k.0.clone())),
2139 v.clone(),
2140 ]))
2141 })
2142 .filter(|term| {
2143 !item_is_ground || !term.is_ground() || term.value() == item.value()
2144 })
2145 .map(|term| {
2146 vec![Goal::Unify {
2147 left: item.clone(),
2148 right: term,
2149 }]
2150 })
2151 .collect::<Vec<Goals>>(),
2152 )?;
2153 }
2154 (_, Value::String(s)) => {
2155 // Unify item with each element of the string
2156 let item_is_ground = item.is_ground();
2157 self.choose(
2158 s.chars()
2159 .map(|c| c.to_string())
2160 .map(Value::String)
2161 .filter(|c| !item_is_ground || c == item.value())
2162 .map(|c| {
2163 vec![Goal::Unify {
2164 left: item.clone(),
2165 right: iterable.clone_with_value(c),
2166 }]
2167 })
2168 .collect::<Vec<Goals>>(),
2169 )?;
2170 }
2171 // Push an `ExternalLookup` goal for external instances
2172 (_, Value::ExternalInstance(_)) => {
2173 // Generate symbol for next result and leave the variable unbound, so that unification with the result does not fail
2174 // Unification of the `next_sym` variable with the result of `NextExternal` happens in `fn external_call_result()`
2175 // `external_call_result` is the handler for results from both `LookupExternal` and `NextExternal`, so neither can bind the
2176 // call ID variable to `false`.
2177 let next_sym = self.kb.read().unwrap().gensym("next_value");
2178 let call_id = self.new_call_id(&next_sym);
2179
2180 // append unify goal to be evaluated after
2181 // next result is fetched
2182 self.append_goals(vec![
2183 Goal::NextExternal {
2184 call_id,
2185 iterable: self.deep_deref(&iterable),
2186 },
2187 Goal::Unify {
2188 left: item.clone(),
2189 right: Term::new_temporary(Value::Variable(next_sym)),
2190 },
2191 ])?;
2192 }
2193 _ => {
2194 return Err(self.type_error(
2195 &iterable,
2196 format!(
2197 "can only use `in` on an iterable value, this is {:?}",
2198 iterable.value()
2199 ),
2200 ));
2201 }
2202 }
2203 Ok(QueryEvent::None)
2204 }
2205
2206 /// Unify `left` and `right` terms.
2207 ///
2208 /// Outcomes of a unification are:
2209 /// - Successful unification => bind zero or more variables to values
2210 /// - Recursive unification => more `Unify` goals are pushed onto the stack
2211 /// - Failure => backtrack
unify(&mut self, left: &Term, right: &Term) -> PolarResult<()>2212 fn unify(&mut self, left: &Term, right: &Term) -> PolarResult<()> {
2213 match (left.value(), right.value()) {
2214 (Value::Expression(_), _) | (_, Value::Expression(_)) => {
2215 return Err(self.type_error(
2216 &left,
2217 format!(
2218 "cannot unify expressions directly `{}` = `{}`",
2219 left.to_polar(),
2220 right.to_polar()
2221 ),
2222 ));
2223 }
2224 (Value::Pattern(_), _) | (_, Value::Pattern(_)) => {
2225 return Err(self.type_error(
2226 &left,
2227 format!(
2228 "cannot unify patterns directly `{}` = `{}`",
2229 left.to_polar(),
2230 right.to_polar()
2231 ),
2232 ));
2233 }
2234
2235 // Unify two variables.
2236 // TODO(gj): (Var, Rest) + (Rest, Var) cases might be unreachable.
2237 (Value::Variable(l), Value::Variable(r))
2238 | (Value::Variable(l), Value::RestVariable(r))
2239 | (Value::RestVariable(l), Value::Variable(r))
2240 | (Value::RestVariable(l), Value::RestVariable(r)) => {
2241 match (self.variable_state(l), self.variable_state(r)) {
2242 (VariableState::Bound(x), VariableState::Bound(y)) => {
2243 // Both variables are bound. Unify their values.
2244 self.push_goal(Goal::Unify { left: x, right: y })?;
2245 }
2246 (_, _) => {
2247 // At least one variable is unbound. Bind it.
2248 if self.bind(l, right.clone()).is_err() {
2249 self.push_goal(Goal::Backtrack)?;
2250 }
2251 }
2252 }
2253 }
2254
2255 // Unify/bind a variable on the left with/to the term on the right.
2256 (Value::Variable(var), _) | (Value::RestVariable(var), _) => {
2257 let right = right.clone();
2258 match self.variable_state(var) {
2259 VariableState::Bound(value) => {
2260 self.push_goal(Goal::Unify { left: value, right })?;
2261 }
2262 _ => {
2263 if self.bind(var, right).is_err() {
2264 self.push_goal(Goal::Backtrack)?;
2265 }
2266 }
2267 }
2268 }
2269
2270 // Unify/bind a variable on the right with/to the term on the left.
2271 (_, Value::Variable(var)) | (_, Value::RestVariable(var)) => {
2272 let left = left.clone();
2273 match self.variable_state(var) {
2274 VariableState::Bound(value) => {
2275 self.push_goal(Goal::Unify { left, right: value })?;
2276 }
2277 _ => {
2278 if self.bind(var, left).is_err() {
2279 self.push_goal(Goal::Backtrack)?;
2280 }
2281 }
2282 }
2283 }
2284
2285 // Unify lists by recursively unifying their elements.
2286 (Value::List(l), Value::List(r)) => self.unify_lists(l, r, |(l, r)| Goal::Unify {
2287 left: l.clone(),
2288 right: r.clone(),
2289 })?,
2290
2291 (Value::Dictionary(left), Value::Dictionary(right)) => {
2292 // Check that the set of keys are the same.
2293 let left_fields: HashSet<&Symbol> = left.fields.keys().collect();
2294 let right_fields: HashSet<&Symbol> = right.fields.keys().collect();
2295 if left_fields != right_fields {
2296 self.push_goal(Goal::Backtrack)?;
2297 return Ok(());
2298 }
2299
2300 // For each value, push a unify goal.
2301 for (k, v) in left.fields.iter() {
2302 let right = right
2303 .fields
2304 .get(&k)
2305 .expect("fields should be equal")
2306 .clone();
2307 self.push_goal(Goal::Unify {
2308 left: v.clone(),
2309 right,
2310 })?
2311 }
2312 }
2313
2314 // Unify integers by value.
2315 (Value::Number(left), Value::Number(right)) => {
2316 if left != right {
2317 self.push_goal(Goal::Backtrack)?;
2318 }
2319 }
2320
2321 // Unify strings by value.
2322 (Value::String(left), Value::String(right)) => {
2323 if left != right {
2324 self.push_goal(Goal::Backtrack)?;
2325 }
2326 }
2327
2328 // Unify bools by value.
2329 (Value::Boolean(left), Value::Boolean(right)) => {
2330 if left != right {
2331 self.push_goal(Goal::Backtrack)?;
2332 }
2333 }
2334
2335 // Unify predicates like unifying heads
2336 (Value::Call(left), Value::Call(right)) => {
2337 // Handled in the parser.
2338 assert!(left.kwargs.is_none());
2339 assert!(right.kwargs.is_none());
2340 if left.name == right.name && left.args.len() == right.args.len() {
2341 self.append_goals(left.args.iter().zip(right.args.iter()).map(
2342 |(left, right)| Goal::Unify {
2343 left: left.clone(),
2344 right: right.clone(),
2345 },
2346 ))?;
2347 } else {
2348 self.push_goal(Goal::Backtrack)?
2349 }
2350 }
2351
2352 // External instances can unify if they are the same instance, i.e., have the same
2353 // instance ID. This is necessary for the case where an instance appears multiple times
2354 // in the same rule head. For example, `f(foo, foo) if ...` or `isa(x, y, x: y) if ...`
2355 // or `max(x, y, x) if x > y;`.
2356 (
2357 Value::ExternalInstance(ExternalInstance {
2358 instance_id: left_instance,
2359 ..
2360 }),
2361 Value::ExternalInstance(ExternalInstance {
2362 instance_id: right_instance,
2363 ..
2364 }),
2365 ) => {
2366 // If IDs match, they're the same _instance_ (not just the same _value_), so unify.
2367 if left_instance != right_instance {
2368 self.push_goal(Goal::UnifyExternal {
2369 left_instance_id: *left_instance,
2370 right_instance_id: *right_instance,
2371 })?;
2372 }
2373 }
2374
2375 // Anything else fails.
2376 (_, _) => self.push_goal(Goal::Backtrack)?,
2377 }
2378
2379 Ok(())
2380 }
2381
2382 /// "Unify" two lists element-wise, respecting rest-variables.
2383 /// Used by both `unify` and `isa`; hence the third argument,
2384 /// a closure that builds sub-goals.
2385 #[allow(clippy::ptr_arg)]
unify_lists<F>(&mut self, left: &TermList, right: &TermList, unify: F) -> PolarResult<()> where F: FnMut((&Term, &Term)) -> Goal,2386 fn unify_lists<F>(&mut self, left: &TermList, right: &TermList, unify: F) -> PolarResult<()>
2387 where
2388 F: FnMut((&Term, &Term)) -> Goal,
2389 {
2390 if has_rest_var(left) && has_rest_var(right) {
2391 self.unify_two_lists_with_rest(left, right, unify)
2392 } else if has_rest_var(left) {
2393 self.unify_rest_list_with_list(left, right, unify)
2394 } else if has_rest_var(right) {
2395 self.unify_rest_list_with_list(right, left, unify)
2396 } else if left.len() == right.len() {
2397 // No rest-variables; unify element-wise.
2398 self.append_goals(left.iter().zip(right).map(unify))
2399 } else {
2400 self.push_goal(Goal::Backtrack)
2401 }
2402 }
2403
2404 /// Unify two list that end with a rest-variable with eachother.
2405 /// A helper method for `unify_lists`.
2406 #[allow(clippy::ptr_arg)]
unify_two_lists_with_rest<F>( &mut self, rest_list_a: &TermList, rest_list_b: &TermList, mut unify: F, ) -> PolarResult<()> where F: FnMut((&Term, &Term)) -> Goal,2407 fn unify_two_lists_with_rest<F>(
2408 &mut self,
2409 rest_list_a: &TermList,
2410 rest_list_b: &TermList,
2411 mut unify: F,
2412 ) -> PolarResult<()>
2413 where
2414 F: FnMut((&Term, &Term)) -> Goal,
2415 {
2416 if rest_list_a.len() == rest_list_b.len() {
2417 let n = rest_list_b.len() - 1;
2418 let rest = unify((&rest_list_b[n].clone(), &rest_list_a[n].clone()));
2419 self.append_goals(
2420 rest_list_b
2421 .iter()
2422 .take(n)
2423 .zip(rest_list_a)
2424 .map(unify)
2425 .chain(vec![rest]),
2426 )
2427 } else {
2428 let (shorter, longer) = {
2429 if rest_list_a.len() < rest_list_b.len() {
2430 (rest_list_a, rest_list_b)
2431 } else {
2432 (rest_list_b, rest_list_a)
2433 }
2434 };
2435 let n = shorter.len() - 1;
2436 let rest = unify((
2437 &shorter[n].clone(),
2438 &Term::new_temporary(Value::List(longer[n..].to_vec())),
2439 ));
2440 self.append_goals(
2441 shorter
2442 .iter()
2443 .take(n)
2444 .zip(longer)
2445 .map(unify)
2446 .chain(vec![rest]),
2447 )
2448 }
2449 }
2450
2451 /// Unify a list that ends with a rest-variable with another that doesn't.
2452 /// A helper method for `unify_lists`.
2453 #[allow(clippy::ptr_arg)]
unify_rest_list_with_list<F>( &mut self, rest_list: &TermList, list: &TermList, mut unify: F, ) -> PolarResult<()> where F: FnMut((&Term, &Term)) -> Goal,2454 fn unify_rest_list_with_list<F>(
2455 &mut self,
2456 rest_list: &TermList,
2457 list: &TermList,
2458 mut unify: F,
2459 ) -> PolarResult<()>
2460 where
2461 F: FnMut((&Term, &Term)) -> Goal,
2462 {
2463 let n = rest_list.len() - 1;
2464 if list.len() >= n {
2465 let rest = unify((
2466 &rest_list[n].clone(),
2467 &Term::new_temporary(Value::List(list[n..].to_vec())),
2468 ));
2469 self.append_goals(
2470 rest_list
2471 .iter()
2472 .take(n)
2473 .zip(list)
2474 .map(unify)
2475 .chain(vec![rest]),
2476 )
2477 } else {
2478 self.push_goal(Goal::Backtrack)
2479 }
2480 }
2481
2482 /// Filter rules to just those applicable to a list of arguments,
2483 /// then sort them by specificity.
2484 #[allow(clippy::ptr_arg)]
filter_rules( &mut self, applicable_rules: &Rules, unfiltered_rules: &Rules, args: &TermList, ) -> PolarResult<()>2485 fn filter_rules(
2486 &mut self,
2487 applicable_rules: &Rules,
2488 unfiltered_rules: &Rules,
2489 args: &TermList,
2490 ) -> PolarResult<()> {
2491 if unfiltered_rules.is_empty() {
2492 // The rules have been filtered. Sort them.
2493
2494 self.push_goal(Goal::SortRules {
2495 rules: applicable_rules.iter().rev().cloned().collect(),
2496 args: args.clone(),
2497 outer: 1,
2498 inner: 1,
2499 })
2500 } else {
2501 // Check one rule for applicability.
2502 let mut unfiltered_rules = unfiltered_rules.clone();
2503 let rule = unfiltered_rules.pop().unwrap();
2504
2505 let inapplicable = Goal::FilterRules {
2506 args: args.clone(),
2507 applicable_rules: applicable_rules.clone(),
2508 unfiltered_rules: unfiltered_rules.clone(),
2509 };
2510 if rule.params.len() != args.len() {
2511 return self.push_goal(inapplicable); // wrong arity
2512 }
2513
2514 let mut applicable_rules = applicable_rules.clone();
2515 applicable_rules.push(rule.clone());
2516 let applicable = Goal::FilterRules {
2517 args: args.clone(),
2518 applicable_rules,
2519 unfiltered_rules,
2520 };
2521
2522 // The prefilter already checks applicability for ground rules.
2523 if rule.is_ground() {
2524 return self.push_goal(applicable);
2525 }
2526
2527 // Rename the variables in the rule (but not the args).
2528 // This avoids clashes between arg vars and rule vars.
2529 let Rule { params, .. } = self.rename_rule_vars(&rule);
2530 let mut check_applicability = vec![];
2531 for (arg, param) in args.iter().zip(params.iter()) {
2532 check_applicability.push(Goal::Unify {
2533 left: arg.clone(),
2534 right: param.parameter.clone(),
2535 });
2536 if let Some(specializer) = ¶m.specializer {
2537 check_applicability.push(Goal::Isa {
2538 left: arg.clone(),
2539 right: specializer.clone(),
2540 });
2541 }
2542 }
2543 self.choose_conditional(check_applicability, vec![applicable], vec![inapplicable])?;
2544 Ok(())
2545 }
2546 }
2547
2548 /// Sort a list of rules with respect to a list of arguments
2549 /// using an explicit-state insertion sort.
2550 ///
2551 /// We maintain two indices for the sort, `outer` and `inner`. The `outer` index tracks our
2552 /// sorting progress. Every rule at or below `outer` is sorted; every rule above it is
2553 /// unsorted. The `inner` index tracks our search through the sorted sublist for the correct
2554 /// position of the candidate rule (the rule at the head of the unsorted portion of the
2555 /// list).
2556 #[allow(clippy::ptr_arg)]
sort_rules( &mut self, rules: &Rules, args: &TermList, outer: usize, inner: usize, ) -> PolarResult<()>2557 fn sort_rules(
2558 &mut self,
2559 rules: &Rules,
2560 args: &TermList,
2561 outer: usize,
2562 inner: usize,
2563 ) -> PolarResult<()> {
2564 if rules.is_empty() {
2565 return self.push_goal(Goal::Backtrack);
2566 }
2567
2568 assert!(outer <= rules.len(), "bad outer index");
2569 assert!(inner <= rules.len(), "bad inner index");
2570 assert!(inner <= outer, "bad insertion sort state");
2571
2572 let next_outer = Goal::SortRules {
2573 rules: rules.clone(),
2574 args: args.clone(),
2575 outer: outer + 1,
2576 inner: outer + 1,
2577 };
2578 // Because `outer` starts as `1`, if there is only one rule in the `Rules`, this check
2579 // fails and we jump down to the evaluation of that lone rule.
2580 if outer < rules.len() {
2581 if inner > 0 {
2582 let compare = Goal::IsMoreSpecific {
2583 left: rules[inner].clone(),
2584 right: rules[inner - 1].clone(),
2585 args: args.clone(),
2586 };
2587
2588 let mut rules = rules.clone();
2589 rules.swap(inner - 1, inner);
2590 let next_inner = Goal::SortRules {
2591 rules,
2592 outer,
2593 inner: inner - 1,
2594 args: args.clone(),
2595 };
2596
2597 // If the comparison fails, break out of the inner loop.
2598 // If the comparison succeeds, continue the inner loop with the swapped rules.
2599 self.choose_conditional(vec![compare], vec![next_inner], vec![next_outer])?;
2600 } else {
2601 assert_eq!(inner, 0);
2602 self.push_goal(next_outer)?;
2603 }
2604 } else {
2605 // We're done; the rules are sorted.
2606 // Make alternatives for calling them.
2607
2608 self.polar_log_mute = false;
2609 self.log_with(
2610 || {
2611 let mut rule_strs = "APPLICABLE_RULES:".to_owned();
2612 for rule in rules {
2613 rule_strs.push_str(&format!("\n {}", self.rule_source(&rule)));
2614 }
2615 rule_strs
2616 },
2617 &[],
2618 );
2619
2620 let mut alternatives = Vec::with_capacity(rules.len());
2621 for rule in rules.iter() {
2622 let mut goals = Vec::with_capacity(2 * args.len() + 4);
2623 goals.push(Goal::TraceRule {
2624 trace: Rc::new(Trace {
2625 node: Node::Rule(rule.clone()),
2626 children: vec![],
2627 }),
2628 });
2629 goals.push(Goal::TraceStackPush);
2630 let Rule { body, params, .. } = self.rename_rule_vars(rule);
2631
2632 // Unify the arguments with the formal parameters.
2633 for (arg, param) in args.iter().zip(params.iter()) {
2634 goals.push(Goal::Unify {
2635 left: arg.clone(),
2636 right: param.parameter.clone(),
2637 });
2638 if let Some(specializer) = ¶m.specializer {
2639 goals.push(Goal::Isa {
2640 left: param.parameter.clone(),
2641 right: specializer.clone(),
2642 });
2643 }
2644 }
2645
2646 // Query for the body clauses.
2647 goals.push(Goal::Query { term: body.clone() });
2648 goals.push(Goal::TraceStackPop);
2649
2650 alternatives.push(goals)
2651 }
2652
2653 // Choose the first alternative, and push a choice for the rest.
2654 self.choose(alternatives)?;
2655 }
2656 Ok(())
2657 }
2658
2659 /// Succeed if `left` is more specific than `right` with respect to `args`.
2660 #[allow(clippy::ptr_arg)]
is_more_specific(&mut self, left: &Rule, right: &Rule, args: &TermList) -> PolarResult<()>2661 fn is_more_specific(&mut self, left: &Rule, right: &Rule, args: &TermList) -> PolarResult<()> {
2662 let zipped = left.params.iter().zip(right.params.iter()).zip(args.iter());
2663 for ((left_param, right_param), arg) in zipped {
2664 match (&left_param.specializer, &right_param.specializer) {
2665 (Some(left_spec), Some(right_spec)) => {
2666 // If you find two non-equal specializers, that comparison determines the relative
2667 // specificity of the two rules completely. As soon as you have two specializers
2668 // that aren't the same and you can compare them and ask which one is more specific
2669 // to the relevant argument, you're done.
2670 if left_spec != right_spec {
2671 let answer = self.kb.read().unwrap().gensym("is_subspecializer");
2672 // Bind answer to false as a starting point in case is subspecializer doesn't
2673 // bind any result.
2674 // This is done here for safety to avoid a bug where `answer` is unbound by
2675 // `IsSubspecializer` and the `Unify` Goal just assigns it to `true` instead
2676 // of checking that is is equal to `true`.
2677 self.bind(&answer, Term::new_temporary(Value::Boolean(false)))
2678 .unwrap();
2679
2680 return self.append_goals(vec![
2681 Goal::IsSubspecializer {
2682 answer: answer.clone(),
2683 left: left_spec.clone(),
2684 right: right_spec.clone(),
2685 arg: arg.clone(),
2686 },
2687 Goal::Unify {
2688 left: Term::new_temporary(Value::Variable(answer)),
2689 right: Term::new_temporary(Value::Boolean(true)),
2690 },
2691 ]);
2692 }
2693 }
2694 // If the left rule has no specializer and the right does, it is NOT more specific,
2695 // so we Backtrack (fail)
2696 (None, Some(_)) => return self.push_goal(Goal::Backtrack),
2697 // If the left rule has a specializer and the right does not, the left IS more specific,
2698 // so we return
2699 (Some(_), None) => return Ok(()),
2700 // If neither has a specializer, neither is more specific, so we continue to the next argument.
2701 (None, None) => (),
2702 }
2703 }
2704 // Fail on any of the above branches that do not return
2705 self.push_goal(Goal::Backtrack)
2706 }
2707
2708 /// Determine if `left` is a more specific specializer ("subspecializer") than `right`
is_subspecializer( &mut self, answer: &Symbol, left: &Term, right: &Term, arg: &Term, ) -> PolarResult<QueryEvent>2709 fn is_subspecializer(
2710 &mut self,
2711 answer: &Symbol,
2712 left: &Term,
2713 right: &Term,
2714 arg: &Term,
2715 ) -> PolarResult<QueryEvent> {
2716 let arg = self.deref(&arg);
2717 match (arg.value(), left.value(), right.value()) {
2718 (
2719 Value::ExternalInstance(instance),
2720 Value::Pattern(Pattern::Instance(left_lit)),
2721 Value::Pattern(Pattern::Instance(right_lit)),
2722 ) => {
2723 let call_id = self.new_call_id(&answer);
2724 let instance_id = instance.instance_id;
2725 if left_lit.tag == right_lit.tag
2726 && !(left_lit.fields.fields.is_empty() && right_lit.fields.fields.is_empty())
2727 {
2728 self.push_goal(Goal::IsSubspecializer {
2729 answer: answer.clone(),
2730 left: left.clone_with_value(Value::Pattern(Pattern::Dictionary(
2731 left_lit.fields.clone(),
2732 ))),
2733 right: right.clone_with_value(Value::Pattern(Pattern::Dictionary(
2734 right_lit.fields.clone(),
2735 ))),
2736 arg,
2737 })?;
2738 }
2739 // check ordering based on the classes
2740 Ok(QueryEvent::ExternalIsSubSpecializer {
2741 call_id,
2742 instance_id,
2743 left_class_tag: left_lit.tag.clone(),
2744 right_class_tag: right_lit.tag.clone(),
2745 })
2746 }
2747 (
2748 _,
2749 Value::Pattern(Pattern::Dictionary(left)),
2750 Value::Pattern(Pattern::Dictionary(right)),
2751 ) => {
2752 let left_fields: HashSet<&Symbol> = left.fields.keys().collect();
2753 let right_fields: HashSet<&Symbol> = right.fields.keys().collect();
2754
2755 // The dictionary with more fields is taken as more specific.
2756 // The assumption here is that rules have already been filtered
2757 // for applicability.
2758 if left_fields.len() != right_fields.len() {
2759 self.rebind_external_answer(
2760 &answer,
2761 Term::new_temporary(Value::Boolean(right_fields.len() < left.fields.len())),
2762 );
2763 }
2764 Ok(QueryEvent::None)
2765 }
2766 (_, Value::Pattern(Pattern::Instance(_)), Value::Pattern(Pattern::Dictionary(_))) => {
2767 self.rebind_external_answer(&answer, Term::new_temporary(Value::Boolean(true)));
2768 Ok(QueryEvent::None)
2769 }
2770 _ => {
2771 self.rebind_external_answer(&answer, Term::new_temporary(Value::Boolean(false)));
2772 Ok(QueryEvent::None)
2773 }
2774 }
2775 }
2776
term_source(&self, term: &Term, include_info: bool) -> String2777 pub fn term_source(&self, term: &Term, include_info: bool) -> String {
2778 let source = self.source(term);
2779 let span = term.span();
2780
2781 let mut source_string = match (&source, &span) {
2782 (Some(source), Some((left, right))) => {
2783 source.src.chars().take(*right).skip(*left).collect()
2784 }
2785 _ => term.to_polar(),
2786 };
2787
2788 if include_info {
2789 if let Some(source) = source {
2790 let offset = term.offset();
2791 let (row, column) = crate::lexer::loc_to_pos(&source.src, offset);
2792 source_string.push_str(&format!(" at line {}, column {}", row + 1, column));
2793 if let Some(filename) = source.filename {
2794 source_string.push_str(&format!(" in file {}", filename));
2795 }
2796 }
2797 }
2798
2799 source_string
2800 }
2801
rule_source(&self, rule: &Rule) -> String2802 pub fn rule_source(&self, rule: &Rule) -> String {
2803 let head = format!(
2804 "{}({})",
2805 rule.name,
2806 rule.params.iter().fold(String::new(), |mut acc, p| {
2807 if !acc.is_empty() {
2808 acc += ", ";
2809 }
2810 acc += &self.term_source(&p.parameter, false);
2811 if let Some(spec) = &p.specializer {
2812 acc += ": ";
2813 acc += &self.term_source(&spec, false);
2814 }
2815 acc
2816 })
2817 );
2818 match rule.body.value() {
2819 Value::Expression(Operation {
2820 operator: Operator::And,
2821 args,
2822 }) if !args.is_empty() => head + " if " + &self.term_source(&rule.body, false) + ";",
2823 _ => head + ";",
2824 }
2825 }
2826
set_error_context( &self, term: &Term, error: impl Into<error::PolarError>, ) -> error::PolarError2827 fn set_error_context(
2828 &self,
2829 term: &Term,
2830 error: impl Into<error::PolarError>,
2831 ) -> error::PolarError {
2832 let source = self.source(term);
2833 let error: error::PolarError = error.into();
2834 error.set_context(source.as_ref(), Some(term))
2835 }
2836
type_error(&self, term: &Term, msg: String) -> error::PolarError2837 fn type_error(&self, term: &Term, msg: String) -> error::PolarError {
2838 let stack_trace = self.stack_trace();
2839 let error = error::RuntimeError::TypeError {
2840 msg,
2841 stack_trace: Some(stack_trace),
2842 };
2843 self.set_error_context(term, error)
2844 }
2845
run_runnable(&mut self, runnable: Box<dyn Runnable>) -> PolarResult<QueryEvent>2846 fn run_runnable(&mut self, runnable: Box<dyn Runnable>) -> PolarResult<QueryEvent> {
2847 let (call_id, answer) = self.new_call_var("runnable_result", Value::Boolean(false));
2848 self.push_goal(Goal::Unify {
2849 left: answer,
2850 right: Term::new_temporary(Value::Boolean(true)),
2851 })?;
2852
2853 Ok(QueryEvent::Run { runnable, call_id })
2854 }
2855
2856 /// Handle an error coming from outside the vm.
external_error(&mut self, message: String) -> PolarResult<()>2857 pub fn external_error(&mut self, message: String) -> PolarResult<()> {
2858 self.external_error = Some(message);
2859 Ok(())
2860 }
2861 }
2862
2863 impl Runnable for PolarVirtualMachine {
2864 /// Run the virtual machine. While there are goals on the stack,
2865 /// pop them off and execute them one at a time until we have a
2866 /// `QueryEvent` to return. May be called multiple times to restart
2867 /// the machine.
run(&mut self, _: Option<&mut Counter>) -> PolarResult<QueryEvent>2868 fn run(&mut self, _: Option<&mut Counter>) -> PolarResult<QueryEvent> {
2869 if self.query_start_time.is_none() {
2870 #[cfg(not(target_arch = "wasm32"))]
2871 let query_start_time = Some(std::time::Instant::now());
2872 #[cfg(target_arch = "wasm32")]
2873 let query_start_time = Some(js_sys::Date::now());
2874 self.query_start_time = query_start_time;
2875 }
2876
2877 if self.goals.is_empty() {
2878 if self.choices.is_empty() {
2879 return Ok(QueryEvent::Done { result: true });
2880 } else {
2881 self.backtrack()?;
2882 }
2883 }
2884
2885 while let Some(goal) = self.goals.pop() {
2886 match self.next(goal.clone())? {
2887 QueryEvent::None => (),
2888 event => {
2889 self.external_error = None;
2890 return Ok(event);
2891 }
2892 }
2893 self.maybe_break(DebugEvent::Goal(goal.clone()))?;
2894 }
2895
2896 if self.log {
2897 self.print("⇒ result");
2898 if self.tracing {
2899 for t in &self.trace {
2900 self.print(&format!("trace\n{}", t.draw(&self)));
2901 }
2902 }
2903 }
2904
2905 let trace = if self.tracing {
2906 let trace = self.trace.first().cloned();
2907 trace.map(|trace| TraceResult {
2908 formatted: trace.draw(&self),
2909 trace,
2910 })
2911 } else {
2912 None
2913 };
2914
2915 let mut bindings = self.bindings(true);
2916 if !self.inverting {
2917 if let Some(bs) = simplify_bindings(bindings, false) {
2918 bindings = bs;
2919 } else {
2920 return Ok(QueryEvent::None);
2921 }
2922
2923 bindings = bindings
2924 .clone()
2925 .into_iter()
2926 .filter(|(var, _)| !var.is_temporary_var())
2927 .map(|(var, value)| (var.clone(), sub_this(var, value)))
2928 .collect();
2929 }
2930
2931 Ok(QueryEvent::Result { bindings, trace })
2932 }
2933
2934 /// Handle response to a predicate posed to the application, e.g., `ExternalIsa`.
external_question_result(&mut self, call_id: u64, answer: bool) -> PolarResult<()>2935 fn external_question_result(&mut self, call_id: u64, answer: bool) -> PolarResult<()> {
2936 let var = self.call_id_symbols.remove(&call_id).expect("bad call id");
2937 self.rebind_external_answer(&var, Term::new_temporary(Value::Boolean(answer)));
2938 Ok(())
2939 }
2940
2941 /// Handle an external result provided by the application.
2942 ///
2943 /// If the value is `Some(_)` then we have a result, and unify the
2944 /// symbol associated with the call ID to the result value. If the
2945 /// value is `None` then the external has no (more) results, so we
2946 /// backtrack to the choice point left by `Goal::LookupExternal`.
external_call_result(&mut self, call_id: u64, term: Option<Term>) -> PolarResult<()>2947 fn external_call_result(&mut self, call_id: u64, term: Option<Term>) -> PolarResult<()> {
2948 // TODO: Open question if we need to pass errors back down to rust.
2949 // For example what happens if the call asked for a field that doesn't exist?
2950
2951 if let Some(value) = term {
2952 self.log_with(|| format!("=> {}", value.to_string()), &[]);
2953
2954 // Fetch variable to unify with call result.
2955 let sym = self.get_call_sym(call_id).to_owned();
2956
2957 self.push_goal(Goal::Unify {
2958 left: Term::new_temporary(Value::Variable(sym)),
2959 right: value,
2960 })?;
2961 } else {
2962 self.log("=> No more results.", &[]);
2963
2964 // No more results. Clean up, cut out the retry alternative,
2965 // and backtrack.
2966 self.call_id_symbols.remove(&call_id).expect("bad call ID");
2967
2968 let check_error = if let Some(goal) = self.goals.last() {
2969 matches!(*(*goal), Goal::CheckError)
2970 } else {
2971 false
2972 };
2973
2974 self.push_goal(Goal::Backtrack)?;
2975 self.push_goal(Goal::Cut {
2976 choice_index: self.choices.len() - 1,
2977 })?;
2978
2979 if check_error {
2980 self.push_goal(Goal::CheckError)?;
2981 }
2982 }
2983 Ok(())
2984 }
2985
2986 /// Drive debugger.
debug_command(&mut self, command: &str) -> PolarResult<()>2987 fn debug_command(&mut self, command: &str) -> PolarResult<()> {
2988 let mut debugger = self.debugger.clone();
2989 let maybe_goal = debugger.debug_command(command, self);
2990 if let Some(goal) = maybe_goal {
2991 self.push_goal(goal)?;
2992 }
2993 self.debugger = debugger;
2994 Ok(())
2995 }
2996
clone_runnable(&self) -> Box<dyn Runnable>2997 fn clone_runnable(&self) -> Box<dyn Runnable> {
2998 Box::new(self.clone())
2999 }
3000 }
3001
3002 #[cfg(test)]
3003 mod tests {
3004 use permute::permute;
3005
3006 use super::*;
3007 use crate::rewrites::unwrap_and;
3008
3009 /// Shorthand for constructing Goal::Query.
3010 ///
3011 /// A one argument invocation assumes the 1st argument is the same
3012 /// parameters that can be passed to the term! macro. In this invocation,
3013 /// typically the form `query!(op!(And, term!(TERM)))` will be used. The
3014 /// one argument form allows for queries with a top level operator other
3015 /// than AND.
3016 ///
3017 /// Multiple arguments `query!(f1, f2, f3)` result in a query with a root
3018 /// AND operator term.
3019 macro_rules! query {
3020 ($term:expr) => {
3021 Goal::Query {
3022 term: term!($term)
3023 }
3024 };
3025 ($($term:expr),+) => {
3026 Goal::Query {
3027 term: term!(op!(And, $($term),+))
3028 }
3029 };
3030 }
3031
3032 /// Macro takes two arguments, the vm and a list-like structure of
3033 /// QueryEvents to expect. It will call run() for each event in the second
3034 /// argument and pattern match to check that the event matches what is
3035 /// expected. Then `vm.is_halted()` is checked.
3036 ///
3037 /// The QueryEvent list elements can either be:
3038 /// - QueryEvent::Result{EXPR} where EXPR is a HashMap<Symbol, Term>.
3039 /// This is shorthand for QueryEvent::Result{bindings} if bindings == EXPR.
3040 /// Use btreemap! for EXPR from the maplit package to write inline hashmaps
3041 /// to assert on.
3042 /// - A pattern with optional guard accepted by matches!. (QueryEvent::Result
3043 /// cannot be matched on due to the above rule.)
3044 macro_rules! assert_query_events {
3045 ($vm:ident, []) => {
3046 assert!($vm.is_halted());
3047 };
3048 ($vm:ident, [QueryEvent::Result{$result:expr}]) => {
3049 assert!(matches!($vm.run(None).unwrap(), QueryEvent::Result{bindings, ..} if bindings == $result));
3050 assert_query_events!($vm, []);
3051 };
3052 ($vm:ident, [QueryEvent::Result{$result:expr}, $($tail:tt)*]) => {
3053 assert!(matches!($vm.run(None).unwrap(), QueryEvent::Result{bindings, ..} if bindings == $result));
3054 assert_query_events!($vm, [$($tail)*]);
3055 };
3056 ($vm:ident, [$( $pattern:pat )|+ $( if $guard: expr )?]) => {
3057 assert!(matches!($vm.run(None).unwrap(), $($pattern)|+ $(if $guard)?));
3058 assert_query_events!($vm, []);
3059 };
3060 ($vm:ident, [$( $pattern:pat )|+ $( if $guard: expr )?, $($tail:tt)*]) => {
3061 assert!(matches!($vm.run(None).unwrap(), $($pattern)|+ $(if $guard)?));
3062 assert_query_events!($vm, [$($tail)*]);
3063 };
3064 // TODO (dhatch) Be able to use btreemap! to match on specific bindings.
3065 }
3066
3067 #[test]
3068 #[allow(clippy::cognitive_complexity)]
and_expression()3069 fn and_expression() {
3070 let f1 = rule!("f", [1]);
3071 let f2 = rule!("f", [2]);
3072
3073 let rule = GenericRule::new(sym!("f"), vec![Arc::new(f1), Arc::new(f2)]);
3074
3075 let mut kb = KnowledgeBase::new();
3076 kb.rules.insert(rule.name.clone(), rule);
3077
3078 let goal = query!(op!(And));
3079
3080 let mut vm = PolarVirtualMachine::new_test(Arc::new(RwLock::new(kb)), false, vec![goal]);
3081 assert_query_events!(vm, [
3082 QueryEvent::Result{hashmap!()},
3083 QueryEvent::Done { result: true }
3084 ]);
3085
3086 assert!(vm.is_halted());
3087
3088 let f1 = term!(call!("f", [1]));
3089 let f2 = term!(call!("f", [2]));
3090 let f3 = term!(call!("f", [3]));
3091
3092 // Querying for f(1)
3093 vm.push_goal(query!(op!(And, f1.clone()))).unwrap();
3094
3095 assert_query_events!(vm, [
3096 QueryEvent::Result{hashmap!{}},
3097 QueryEvent::Done { result: true }
3098 ]);
3099
3100 // Querying for f(1), f(2)
3101 vm.push_goal(query!(f1.clone(), f2.clone())).unwrap();
3102 assert_query_events!(vm, [
3103 QueryEvent::Result{hashmap!{}},
3104 QueryEvent::Done { result: true }
3105 ]);
3106
3107 // Querying for f(3)
3108 vm.push_goal(query!(op!(And, f3.clone()))).unwrap();
3109 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3110
3111 // Querying for f(1), f(2), f(3)
3112 let parts = vec![f1, f2, f3];
3113 for permutation in permute(parts) {
3114 vm.push_goal(Goal::Query {
3115 term: Term::new_from_test(Value::Expression(Operation {
3116 operator: Operator::And,
3117 args: permutation,
3118 })),
3119 })
3120 .unwrap();
3121 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3122 }
3123 }
3124
3125 #[test]
unify_expression()3126 fn unify_expression() {
3127 let mut vm = PolarVirtualMachine::default();
3128 vm.push_goal(query!(op!(Unify, term!(1), term!(1))))
3129 .unwrap();
3130
3131 assert_query_events!(vm, [
3132 QueryEvent::Result{hashmap!{}},
3133 QueryEvent::Done { result: true }
3134 ]);
3135
3136 let q = op!(Unify, term!(1), term!(2));
3137 vm.push_goal(query!(q)).unwrap();
3138
3139 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3140 }
3141
3142 #[test]
3143 #[allow(clippy::cognitive_complexity)]
isa_on_lists()3144 fn isa_on_lists() {
3145 let mut vm = PolarVirtualMachine::default();
3146 let one = term!(1);
3147 let one_list = term!([1]);
3148 let one_two_list = term!([1, 2]);
3149 let two_one_list = term!([2, 1]);
3150 let empty_list = term!([]);
3151
3152 // [] isa []
3153 vm.push_goal(Goal::Isa {
3154 left: empty_list.clone(),
3155 right: empty_list.clone(),
3156 })
3157 .unwrap();
3158 assert!(
3159 matches!(vm.run(None).unwrap(), QueryEvent::Result{bindings, ..} if bindings.is_empty())
3160 );
3161 assert!(matches!(
3162 vm.run(None).unwrap(),
3163 QueryEvent::Done { result: true }
3164 ));
3165 assert!(vm.is_halted());
3166
3167 // [1,2] isa [1,2]
3168 vm.push_goal(Goal::Isa {
3169 left: one_two_list.clone(),
3170 right: one_two_list.clone(),
3171 })
3172 .unwrap();
3173 assert!(
3174 matches!(vm.run(None).unwrap(), QueryEvent::Result{bindings, ..} if bindings.is_empty())
3175 );
3176 assert!(matches!(
3177 vm.run(None).unwrap(),
3178 QueryEvent::Done { result: true }
3179 ));
3180 assert!(vm.is_halted());
3181
3182 // [1,2] isNOTa [2,1]
3183 vm.push_goal(Goal::Isa {
3184 left: one_two_list.clone(),
3185 right: two_one_list,
3186 })
3187 .unwrap();
3188 assert!(matches!(
3189 vm.run(None).unwrap(),
3190 QueryEvent::Done { result: true }
3191 ));
3192 assert!(vm.is_halted());
3193
3194 // [1] isNOTa [1,2]
3195 vm.push_goal(Goal::Isa {
3196 left: one_list.clone(),
3197 right: one_two_list.clone(),
3198 })
3199 .unwrap();
3200 assert!(matches!(
3201 vm.run(None).unwrap(),
3202 QueryEvent::Done { result: true }
3203 ));
3204 assert!(vm.is_halted());
3205
3206 // [1,2] isNOTa [1]
3207 vm.push_goal(Goal::Isa {
3208 left: one_two_list.clone(),
3209 right: one_list.clone(),
3210 })
3211 .unwrap();
3212 assert!(matches!(
3213 vm.run(None).unwrap(),
3214 QueryEvent::Done { result: true }
3215 ));
3216 assert!(vm.is_halted());
3217
3218 // [1] isNOTa []
3219 vm.push_goal(Goal::Isa {
3220 left: one_list.clone(),
3221 right: empty_list.clone(),
3222 })
3223 .unwrap();
3224 assert!(matches!(
3225 vm.run(None).unwrap(),
3226 QueryEvent::Done { result: true }
3227 ));
3228 assert!(vm.is_halted());
3229
3230 // [] isNOTa [1]
3231 vm.push_goal(Goal::Isa {
3232 left: empty_list,
3233 right: one_list.clone(),
3234 })
3235 .unwrap();
3236 assert!(matches!(
3237 vm.run(None).unwrap(),
3238 QueryEvent::Done { result: true }
3239 ));
3240 assert!(vm.is_halted());
3241
3242 // [1] isNOTa 1
3243 vm.push_goal(Goal::Isa {
3244 left: one_list.clone(),
3245 right: one.clone(),
3246 })
3247 .unwrap();
3248 assert!(matches!(
3249 vm.run(None).unwrap(),
3250 QueryEvent::Done { result: true }
3251 ));
3252 assert!(vm.is_halted());
3253
3254 // 1 isNOTa [1]
3255 vm.push_goal(Goal::Isa {
3256 left: one,
3257 right: one_list,
3258 })
3259 .unwrap();
3260 assert!(matches!(
3261 vm.run(None).unwrap(),
3262 QueryEvent::Done { result: true }
3263 ));
3264 assert!(vm.is_halted());
3265
3266 // [1,2] isa [1, *rest]
3267 vm.push_goal(Goal::Isa {
3268 left: one_two_list,
3269 right: term!([1, Value::RestVariable(sym!("rest"))]),
3270 })
3271 .unwrap();
3272 assert_query_events!(vm, [
3273 QueryEvent::Result{hashmap!{sym!("rest") => term!([2])}},
3274 QueryEvent::Done { result: true }
3275 ]);
3276 }
3277
3278 #[test]
3279 #[allow(clippy::cognitive_complexity)]
isa_on_dicts()3280 fn isa_on_dicts() {
3281 let mut vm = PolarVirtualMachine::default();
3282 let dict = term!(btreemap! {
3283 sym!("x") => term!(1),
3284 sym!("y") => term!(2),
3285 });
3286 let dict_pattern = term!(pattern!(btreemap! {
3287 sym!("x") => term!(1),
3288 sym!("y") => term!(2),
3289 }));
3290 vm.push_goal(Goal::Isa {
3291 left: dict.clone(),
3292 right: dict_pattern.clone(),
3293 })
3294 .unwrap();
3295 assert_query_events!(vm, [QueryEvent::Result { hashmap!() }, QueryEvent::Done { result: true }]);
3296
3297 // Dicts with identical keys and different values DO NOT isa.
3298 let different_dict_pattern = term!(pattern!(btreemap! {
3299 sym!("x") => term!(2),
3300 sym!("y") => term!(1),
3301 }));
3302 vm.push_goal(Goal::Isa {
3303 left: dict.clone(),
3304 right: different_dict_pattern,
3305 })
3306 .unwrap();
3307 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3308
3309 let empty_dict = term!(btreemap! {});
3310 let empty_dict_pattern = term!(pattern!(btreemap! {}));
3311 // {} isa {}.
3312 vm.push_goal(Goal::Isa {
3313 left: empty_dict.clone(),
3314 right: empty_dict_pattern.clone(),
3315 })
3316 .unwrap();
3317 assert_query_events!(vm, [QueryEvent::Result { hashmap!() }, QueryEvent::Done { result: true }]);
3318
3319 // Non-empty dicts should isa against an empty dict.
3320 vm.push_goal(Goal::Isa {
3321 left: dict.clone(),
3322 right: empty_dict_pattern,
3323 })
3324 .unwrap();
3325 assert_query_events!(vm, [QueryEvent::Result { hashmap!() }, QueryEvent::Done { result: true }]);
3326
3327 // Empty dicts should NOT isa against a non-empty dict.
3328 vm.push_goal(Goal::Isa {
3329 left: empty_dict,
3330 right: dict_pattern.clone(),
3331 })
3332 .unwrap();
3333 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3334
3335 let subset_dict_pattern = term!(pattern!(btreemap! {sym!("x") => term!(1)}));
3336 // Superset dict isa subset dict.
3337 vm.push_goal(Goal::Isa {
3338 left: dict,
3339 right: subset_dict_pattern,
3340 })
3341 .unwrap();
3342 assert_query_events!(vm, [QueryEvent::Result { hashmap!() }, QueryEvent::Done { result: true }]);
3343
3344 // Subset dict isNOTa superset dict.
3345 let subset_dict = term!(btreemap! {sym!("x") => term!(1)});
3346 vm.push_goal(Goal::Isa {
3347 left: subset_dict,
3348 right: dict_pattern,
3349 })
3350 .unwrap();
3351 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3352 }
3353
3354 #[test]
unify_dicts()3355 fn unify_dicts() {
3356 let mut vm = PolarVirtualMachine::default();
3357 // Dicts with identical keys and values unify.
3358 let left = term!(btreemap! {
3359 sym!("x") => term!(1),
3360 sym!("y") => term!(2),
3361 });
3362 let right = term!(btreemap! {
3363 sym!("x") => term!(1),
3364 sym!("y") => term!(2),
3365 });
3366 vm.push_goal(Goal::Unify {
3367 left: left.clone(),
3368 right,
3369 })
3370 .unwrap();
3371 assert_query_events!(vm, [QueryEvent::Result { hashmap!() }, QueryEvent::Done { result: true }]);
3372
3373 // Dicts with identical keys and different values DO NOT unify.
3374 let right = term!(btreemap! {
3375 sym!("x") => term!(2),
3376 sym!("y") => term!(1),
3377 });
3378 vm.push_goal(Goal::Unify {
3379 left: left.clone(),
3380 right,
3381 })
3382 .unwrap();
3383 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3384
3385 // Empty dicts unify.
3386 vm.push_goal(Goal::Unify {
3387 left: term!(btreemap! {}),
3388 right: term!(btreemap! {}),
3389 })
3390 .unwrap();
3391 assert_query_events!(vm, [QueryEvent::Result { hashmap!() }, QueryEvent::Done { result: true }]);
3392
3393 // Empty dict should not unify against a non-empty dict.
3394 vm.push_goal(Goal::Unify {
3395 left: left.clone(),
3396 right: term!(btreemap! {}),
3397 })
3398 .unwrap();
3399 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3400
3401 // Subset match should fail.
3402 let right = term!(btreemap! {
3403 sym!("x") => term!(1),
3404 });
3405 vm.push_goal(Goal::Unify { left, right }).unwrap();
3406 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3407 }
3408
3409 #[test]
unify_nested_dicts()3410 fn unify_nested_dicts() {
3411 let mut vm = PolarVirtualMachine::default();
3412
3413 let left = term!(btreemap! {
3414 sym!("x") => term!(btreemap!{
3415 sym!("y") => term!(1)
3416 })
3417 });
3418 let right = term!(btreemap! {
3419 sym!("x") => term!(btreemap!{
3420 sym!("y") => term!(sym!("result"))
3421 })
3422 });
3423 vm.push_goal(Goal::Unify { left, right }).unwrap();
3424 assert_query_events!(vm, [QueryEvent::Result { hashmap!{sym!("result") => term!(1)} }, QueryEvent::Done { result: true }]);
3425 }
3426
3427 #[test]
lookup()3428 fn lookup() {
3429 let mut vm = PolarVirtualMachine::default();
3430
3431 let fields = btreemap! {
3432 sym!("x") => term!(1),
3433 };
3434 let dict = Dictionary { fields };
3435 vm.push_goal(Goal::Lookup {
3436 dict: dict.clone(),
3437 field: term!(string!("x")),
3438 value: term!(1),
3439 })
3440 .unwrap();
3441
3442 assert_query_events!(vm, [
3443 QueryEvent::Result{hashmap!{}}
3444 ]);
3445
3446 // Lookup with incorrect value
3447 vm.push_goal(Goal::Lookup {
3448 dict: dict.clone(),
3449 field: term!(string!("x")),
3450 value: term!(2),
3451 })
3452 .unwrap();
3453
3454 assert_query_events!(vm, [QueryEvent::Done { result: true }]);
3455
3456 // Lookup with unbound value
3457 vm.push_goal(Goal::Lookup {
3458 dict,
3459 field: term!(string!("x")),
3460 value: term!(sym!("y")),
3461 })
3462 .unwrap();
3463 assert_query_events!(vm, [
3464 QueryEvent::Result{hashmap!{sym!("y") => term!(1)}}
3465 ]);
3466 }
3467
3468 #[test]
debug()3469 fn debug() {
3470 let mut vm = PolarVirtualMachine::new_test(
3471 Arc::new(RwLock::new(KnowledgeBase::new())),
3472 false,
3473 vec![Goal::Debug {
3474 message: "Hello".to_string(),
3475 }],
3476 );
3477 assert!(matches!(
3478 vm.run(None).unwrap(),
3479 QueryEvent::Debug { message } if &message[..] == "Hello"
3480 ));
3481 }
3482
3483 #[test]
halt()3484 fn halt() {
3485 let mut vm = PolarVirtualMachine::new_test(
3486 Arc::new(RwLock::new(KnowledgeBase::new())),
3487 false,
3488 vec![Goal::Halt],
3489 );
3490 let _ = vm.run(None).unwrap();
3491 assert_eq!(vm.goals.len(), 0);
3492 assert_eq!(vm.bindings(true).len(), 0);
3493 }
3494
3495 #[test]
unify()3496 fn unify() {
3497 let x = sym!("x");
3498 let y = sym!("y");
3499 let vars = term!([x.clone(), y.clone()]);
3500 let zero = value!(0);
3501 let one = value!(1);
3502 let vals = term!([zero.clone(), one.clone()]);
3503 let mut vm = PolarVirtualMachine::new_test(
3504 Arc::new(RwLock::new(KnowledgeBase::new())),
3505 false,
3506 vec![Goal::Unify {
3507 left: vars,
3508 right: vals,
3509 }],
3510 );
3511 let _ = vm.run(None).unwrap();
3512 assert_eq!(vm.variable_state(&x), VariableState::Bound(term!(zero)));
3513 assert_eq!(vm.variable_state(&y), VariableState::Bound(term!(one)));
3514 }
3515
3516 #[test]
unify_var()3517 fn unify_var() {
3518 let x = sym!("x");
3519 let y = sym!("y");
3520 let z = sym!("z");
3521 let one = term!(1);
3522 let two = term!(2);
3523
3524 let mut vm = PolarVirtualMachine::default();
3525
3526 // Left variable bound to bound right variable.
3527 vm.bind(&y, one.clone()).unwrap();
3528 vm.append_goals(vec![Goal::Unify {
3529 left: term!(x.clone()),
3530 right: term!(y),
3531 }])
3532 .unwrap();
3533 let _ = vm.run(None).unwrap();
3534 assert_eq!(vm.deref(&term!(x)), one);
3535 vm.backtrack().unwrap();
3536
3537 // Left variable bound to value.
3538 vm.bind(&z, one.clone()).unwrap();
3539 vm.append_goals(vec![Goal::Unify {
3540 left: term!(z.clone()),
3541 right: one.clone(),
3542 }])
3543 .unwrap();
3544 let _ = vm.run(None).unwrap();
3545 assert_eq!(vm.deref(&term!(z.clone())), one);
3546
3547 // Left variable bound to value, unify with something else, backtrack.
3548 vm.append_goals(vec![Goal::Unify {
3549 left: term!(z.clone()),
3550 right: two,
3551 }])
3552 .unwrap();
3553 let _ = vm.run(None).unwrap();
3554 assert_eq!(vm.deref(&term!(z)), one);
3555 }
3556
3557 #[test]
test_gen_var()3558 fn test_gen_var() {
3559 let vm = PolarVirtualMachine::default();
3560
3561 let rule = Rule {
3562 name: Symbol::new("foo"),
3563 params: vec![],
3564 body: Term::new_from_test(Value::Expression(Operation {
3565 operator: Operator::And,
3566 args: vec![
3567 term!(1),
3568 Term::new_from_test(Value::Variable(Symbol("x".to_string()))),
3569 Term::new_from_test(Value::Variable(Symbol("x".to_string()))),
3570 Term::new_from_test(Value::List(vec![Term::new_from_test(Value::Variable(
3571 Symbol("y".to_string()),
3572 ))])),
3573 ],
3574 })),
3575 };
3576
3577 let renamed_rule = vm.rename_rule_vars(&rule);
3578 let renamed_terms = unwrap_and(&renamed_rule.body);
3579 assert_eq!(renamed_terms[1].value(), renamed_terms[2].value());
3580 let x_value = match &renamed_terms[1].value() {
3581 Value::Variable(sym) => Some(sym.0.clone()),
3582 _ => None,
3583 };
3584 assert_eq!(x_value.unwrap(), "_x_1");
3585
3586 let y_value = match &renamed_terms[3].value() {
3587 Value::List(terms) => match &terms[0].value() {
3588 Value::Variable(sym) => Some(sym.0.clone()),
3589 _ => None,
3590 },
3591 _ => None,
3592 };
3593 assert_eq!(y_value.unwrap(), "_y_2");
3594 }
3595
3596 #[test]
test_filter_rules()3597 fn test_filter_rules() {
3598 let rule_a = Arc::new(rule!("bar", ["_"; instance!("a")]));
3599 let rule_b = Arc::new(rule!("bar", ["_"; instance!("b")]));
3600 let rule_1a = Arc::new(rule!("bar", [value!(1)]));
3601 let rule_1b = Arc::new(rule!("bar", ["_"; value!(1)]));
3602
3603 let gen_rule = GenericRule::new(sym!("bar"), vec![rule_a, rule_b, rule_1a, rule_1b]);
3604 let mut kb = KnowledgeBase::new();
3605 kb.add_generic_rule(gen_rule);
3606
3607 let kb = Arc::new(RwLock::new(kb));
3608
3609 let external_instance = Value::ExternalInstance(ExternalInstance {
3610 instance_id: 1,
3611 constructor: None,
3612 repr: None,
3613 });
3614 let query = query!(call!("bar", [sym!("x")]));
3615 let mut vm = PolarVirtualMachine::new_test(kb.clone(), false, vec![query]);
3616 vm.bind(&sym!("x"), Term::new_from_test(external_instance))
3617 .unwrap();
3618
3619 let mut external_isas = vec![];
3620
3621 loop {
3622 match vm.run(None).unwrap() {
3623 QueryEvent::Done { .. } => break,
3624 QueryEvent::ExternalIsa {
3625 call_id, class_tag, ..
3626 } => {
3627 external_isas.push(class_tag.clone());
3628 // Return `true` if the specified `class_tag` is `"a"`.
3629 vm.external_question_result(call_id, class_tag.0 == "a")
3630 .unwrap()
3631 }
3632 QueryEvent::ExternalIsSubSpecializer { .. } | QueryEvent::Result { .. } => (),
3633 e => panic!("Unexpected event: {:?}", e),
3634 }
3635 }
3636
3637 let expected = vec![sym!("b"), sym!("a"), sym!("a")];
3638 assert_eq!(external_isas, expected);
3639
3640 let query = query!(call!("bar", [sym!("x")]));
3641 let mut vm = PolarVirtualMachine::new_test(kb, false, vec![query]);
3642 vm.bind(&sym!("x"), Term::new_from_test(value!(1))).unwrap();
3643
3644 let mut results = vec![];
3645 loop {
3646 match vm.run(None).unwrap() {
3647 QueryEvent::Done { .. } => break,
3648 QueryEvent::ExternalIsa { .. } => (),
3649 QueryEvent::Result { bindings, .. } => results.push(bindings),
3650 _ => panic!("Unexpected event"),
3651 }
3652 }
3653
3654 assert_eq!(results.len(), 2);
3655 assert_eq!(
3656 results,
3657 vec![
3658 hashmap! {sym!("x") => term!(1)},
3659 hashmap! {sym!("x") => term!(1)},
3660 ]
3661 );
3662 }
3663
3664 #[test]
test_sort_rules()3665 fn test_sort_rules() {
3666 // Test sort rule by mocking ExternalIsSubSpecializer and ExternalIsa.
3667 let bar_rule = GenericRule::new(
3668 sym!("bar"),
3669 vec![
3670 Arc::new(rule!("bar", ["_"; instance!("b"), "_"; instance!("a"), value!(3)])),
3671 Arc::new(rule!("bar", ["_"; instance!("a"), "_"; instance!("a"), value!(1)])),
3672 Arc::new(rule!("bar", ["_"; instance!("a"), "_"; instance!("b"), value!(2)])),
3673 Arc::new(rule!("bar", ["_"; instance!("b"), "_"; instance!("b"), value!(4)])),
3674 ],
3675 );
3676
3677 let mut kb = KnowledgeBase::new();
3678 kb.add_generic_rule(bar_rule);
3679
3680 let external_instance = Value::ExternalInstance(ExternalInstance {
3681 instance_id: 1,
3682 constructor: None,
3683 repr: None,
3684 });
3685
3686 let mut vm = PolarVirtualMachine::new_test(
3687 Arc::new(RwLock::new(kb)),
3688 false,
3689 vec![query!(call!(
3690 "bar",
3691 [external_instance.clone(), external_instance, sym!("z")]
3692 ))],
3693 );
3694
3695 let mut results = Vec::new();
3696 loop {
3697 match vm.run(None).unwrap() {
3698 QueryEvent::Done { .. } => break,
3699 QueryEvent::Result { bindings, .. } => results.push(bindings),
3700 QueryEvent::ExternalIsSubSpecializer {
3701 call_id,
3702 left_class_tag,
3703 right_class_tag,
3704 ..
3705 } => {
3706 // For this test we sort classes lexically.
3707 vm.external_question_result(call_id, left_class_tag < right_class_tag)
3708 .unwrap()
3709 }
3710 QueryEvent::MakeExternal { .. } => (),
3711 QueryEvent::ExternalIsa { call_id, .. } => {
3712 // For this test, anything is anything.
3713 vm.external_question_result(call_id, true).unwrap()
3714 }
3715 _ => panic!("Unexpected event"),
3716 }
3717 }
3718
3719 assert_eq!(results.len(), 4);
3720 assert_eq!(
3721 results,
3722 vec![
3723 hashmap! {sym!("z") => term!(1)},
3724 hashmap! {sym!("z") => term!(2)},
3725 hashmap! {sym!("z") => term!(3)},
3726 hashmap! {sym!("z") => term!(4)},
3727 ]
3728 );
3729 }
3730
3731 #[test]
test_is_subspecializer()3732 fn test_is_subspecializer() {
3733 let mut vm = PolarVirtualMachine::default();
3734
3735 // Test `is_subspecializer` case where:
3736 // - arg: `ExternalInstance`
3737 // - left: `InstanceLiteral`
3738 // - right: `Dictionary`
3739 let arg = term!(Value::ExternalInstance(ExternalInstance {
3740 instance_id: 1,
3741 constructor: None,
3742 repr: None,
3743 }));
3744 let left = term!(value!(Pattern::Instance(InstanceLiteral {
3745 tag: sym!("Any"),
3746 fields: Dictionary {
3747 fields: btreemap! {}
3748 }
3749 })));
3750 let right = term!(Value::Pattern(Pattern::Dictionary(Dictionary {
3751 fields: btreemap! {sym!("a") => term!("a")},
3752 })));
3753
3754 let answer = vm.kb.read().unwrap().gensym("is_subspecializer");
3755
3756 match vm.is_subspecializer(&answer, &left, &right, &arg).unwrap() {
3757 QueryEvent::None => (),
3758 event => panic!("Expected None, got {:?}", event),
3759 }
3760
3761 assert_eq!(
3762 vm.deref(&term!(Value::Variable(answer))),
3763 term!(value!(true))
3764 );
3765 }
3766
3767 #[test]
test_timeout()3768 fn test_timeout() {
3769 let mut vm = PolarVirtualMachine::default();
3770 vm.set_query_timeout(1);
3771 // Turn this off so we don't hit it.
3772 vm.set_stack_limit(std::usize::MAX);
3773
3774 loop {
3775 vm.push_goal(Goal::Noop).unwrap();
3776 vm.push_goal(Goal::UnifyExternal {
3777 left_instance_id: 1,
3778 right_instance_id: 1,
3779 })
3780 .unwrap();
3781 let result = vm.run(None);
3782 match result {
3783 Ok(event) => assert!(matches!(event, QueryEvent::ExternalUnify { .. })),
3784 Err(err) => {
3785 assert!(matches!(
3786 err,
3787 error::PolarError {
3788 kind: error::ErrorKind::Runtime(
3789 error::RuntimeError::QueryTimeout { .. }
3790 ),
3791 ..
3792 }
3793 ));
3794
3795 // End test.
3796 break;
3797 }
3798 }
3799 }
3800 }
3801
3802 #[test]
test_prefiltering()3803 fn test_prefiltering() {
3804 let bar_rule = GenericRule::new(
3805 sym!("bar"),
3806 vec![
3807 Arc::new(rule!("bar", [value!([1])])),
3808 Arc::new(rule!("bar", [value!([2])])),
3809 ],
3810 );
3811
3812 let mut kb = KnowledgeBase::new();
3813 kb.add_generic_rule(bar_rule);
3814
3815 let mut vm = PolarVirtualMachine::new_test(Arc::new(RwLock::new(kb)), false, vec![]);
3816 vm.bind(&sym!("x"), term!(1)).unwrap();
3817 let _ = vm.run(None);
3818 let _ = vm.next(Rc::new(query!(call!("bar", [value!([sym!("x")])]))));
3819 // After calling the query goal we should be left with the
3820 // prefiltered rules
3821 let next_goal = vm
3822 .goals
3823 .iter()
3824 .find(|g| matches!(g.as_ref(), Goal::FilterRules { .. }))
3825 .unwrap();
3826 let goal_debug = format!("{:#?}", next_goal);
3827 assert!(
3828 matches!(next_goal.as_ref(), Goal::FilterRules {
3829 ref applicable_rules, ref unfiltered_rules, ..
3830 } if unfiltered_rules.len() == 1 && applicable_rules.is_empty()),
3831 "Goal should contain just one prefiltered rule: {}",
3832 goal_debug
3833 );
3834 }
3835
3836 #[test]
choose_conditional()3837 fn choose_conditional() {
3838 let mut vm = PolarVirtualMachine::new_test(
3839 Arc::new(RwLock::new(KnowledgeBase::new())),
3840 false,
3841 vec![],
3842 );
3843 let consequent = Goal::Debug {
3844 message: "consequent".to_string(),
3845 };
3846 let alternative = Goal::Debug {
3847 message: "alternative".to_string(),
3848 };
3849
3850 // Check consequent path when conditional succeeds.
3851 vm.choose_conditional(
3852 vec![Goal::Noop],
3853 vec![consequent.clone()],
3854 vec![alternative.clone()],
3855 )
3856 .unwrap();
3857 assert_query_events!(vm, [
3858 QueryEvent::Debug { message } if &message[..] == "consequent" && vm.is_halted(),
3859 QueryEvent::Done { result: true }
3860 ]);
3861
3862 // Check alternative path when conditional fails.
3863 vm.choose_conditional(
3864 vec![Goal::Backtrack],
3865 vec![consequent.clone()],
3866 vec![alternative.clone()],
3867 )
3868 .unwrap();
3869 assert_query_events!(vm, [
3870 QueryEvent::Debug { message } if &message[..] == "alternative" && vm.is_halted(),
3871 QueryEvent::Done { result: true }
3872 ]);
3873
3874 // Ensure bindings are cleaned up after conditional.
3875 vm.choose_conditional(
3876 vec![
3877 Goal::Unify {
3878 left: term!(sym!("x")),
3879 right: term!(true),
3880 },
3881 query!(sym!("x")),
3882 ],
3883 vec![consequent],
3884 vec![alternative],
3885 )
3886 .unwrap();
3887 assert_query_events!(vm, [
3888 QueryEvent::Debug { message } if &message[..] == "consequent" && vm.bindings(true).is_empty() && vm.is_halted(),
3889 QueryEvent::Done { result: true }
3890 ]);
3891 }
3892
3893 #[test]
test_check_partial_args()3894 fn test_check_partial_args() {
3895 let mut vm = PolarVirtualMachine::new_test(
3896 Arc::new(RwLock::new(KnowledgeBase::new())),
3897 false,
3898 vec![],
3899 );
3900
3901 // Test with valid args
3902 let object = term!(Value::ExternalInstance(ExternalInstance {
3903 instance_id: 1,
3904 constructor: None,
3905 repr: Some(String::from("sqlalchemy_oso.roles.OsoRoles"))
3906 }));
3907 let value = term!(sym!("result"));
3908 let resource_var = term!(sym!("resource"));
3909 vm.add_constraint(&term!(op!(
3910 Isa,
3911 resource_var.clone(),
3912 term!(pattern!(instance!("Repository")))
3913 )))
3914 .unwrap();
3915 let actor_var = sym!("actor");
3916 vm.bind(&actor_var, term!(value!("Leina"))).unwrap();
3917 let action_var = sym!("action");
3918 vm.bind(&action_var, term!(value!("read"))).unwrap();
3919 let args = vec![
3920 term!(actor_var.clone()),
3921 term!(action_var.clone()),
3922 resource_var.clone(),
3923 ];
3924 let role_allows_call = term!(Call {
3925 name: sym!("role_allows"),
3926 args: args.clone(),
3927 kwargs: None
3928 });
3929 let user_in_role_call = term!(Call {
3930 name: sym!("user_in_role"),
3931 args: args.clone(),
3932 kwargs: None
3933 });
3934 let role_allows_constraint_term = term!(op!(
3935 Unify,
3936 value.clone(),
3937 term!(op!(
3938 Dot,
3939 object.clone(),
3940 term!(Call {
3941 name: sym!("role_allows"),
3942 args: vec![
3943 term!(value!("Leina")),
3944 term!(value!("read")),
3945 resource_var.clone()
3946 ],
3947 kwargs: None
3948 })
3949 ))
3950 ));
3951 let user_in_role_constraint_term = term!(op!(
3952 Unify,
3953 value.clone(),
3954 term!(op!(
3955 Dot,
3956 object.clone(),
3957 term!(Call {
3958 name: sym!("user_in_role"),
3959 args: vec![
3960 term!(value!("Leina")),
3961 term!(value!("read")),
3962 resource_var.clone()
3963 ],
3964 kwargs: None
3965 })
3966 ))
3967 ));
3968
3969 // Test role_allows
3970 let res_val = vm
3971 .check_partial_args(&object, &role_allows_call, &value)
3972 .unwrap()
3973 .unwrap();
3974 assert_eq!(res_val, role_allows_constraint_term);
3975 // Test adding the actual constraint
3976 vm.add_constraint(&res_val).unwrap();
3977
3978 // Test user_in_role
3979 let res_val = vm
3980 .check_partial_args(&object, &user_in_role_call, &value)
3981 .unwrap()
3982 .unwrap();
3983 assert_eq!(res_val, user_in_role_constraint_term);
3984 // Test adding the actual constraint
3985 vm.add_constraint(&res_val).unwrap();
3986
3987 // Test on invalid instance
3988 let bad_object = term!(Value::ExternalInstance(ExternalInstance {
3989 instance_id: 1,
3990 constructor: None,
3991 repr: Some(String::from("sqlalchemy_oso.roles.FakeRoles"))
3992 }));
3993 assert!(vm
3994 .check_partial_args(&bad_object, &role_allows_call, &value)
3995 .is_err());
3996
3997 // Test with invalid method name
3998 let bad_method_name = term!(Call {
3999 name: sym!("bad_method"),
4000 args,
4001 kwargs: None
4002 });
4003 // TODO: check error messages are correct
4004 assert!(vm
4005 .check_partial_args(&object, &bad_method_name, &value)
4006 .is_err());
4007
4008 // Test with invalid arg position
4009 let bad_args = vec![term!(actor_var), resource_var, term!(action_var)];
4010 let wrong_arg_order = term!(Call {
4011 name: sym!("role_allows"),
4012 args: bad_args,
4013 kwargs: None
4014 });
4015 // TODO: check error messages are correct
4016 assert!(vm
4017 .check_partial_args(&object, &wrong_arg_order, &value)
4018 .is_err());
4019 // TODO: Test with kwargs
4020 }
4021 }
4022