From 80b59bae83169ec8a84e12c81d59a4b756f96e54 Mon Sep 17 00:00:00 2001
From: Mark Thom <markjordanthom@gmail.com>
Date: Wed, 28 Mar 2018 21:17:46 -0600
Subject: [PATCH] add acyclic term

---
 README.md                           |  1 +
 src/prolog/ast.rs                   |  5 ++++-
 src/prolog/heap_iter.rs             | 22 +++++++++++----------
 src/prolog/machine/machine_state.rs | 30 ++++++++++++++++++++++++++++-
 4 files changed, 46 insertions(+), 12 deletions(-)

diff --git a/README.md b/README.md
index 35621da2..be81b7c7 100644
--- a/README.md
+++ b/README.md
@@ -122,6 +122,7 @@ The following predicates are built-in to rusty-wam.
 * `(=..)/2`
 * `(->)/2`
 * `(;)/2`
+* `acyclic_term/2`
 * `append/3`
 * `arg/3`
 * `atom/1`
diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs
index d8385283..a43fb454 100644
--- a/src/prolog/ast.rs
+++ b/src/prolog/ast.rs
@@ -673,6 +673,7 @@ pub struct Rule {
 
 #[derive(Clone)]
 pub enum ClauseType {
+    AcyclicTerm,
     Arg,
     CallN,
     CallWithInferenceLimit,
@@ -773,7 +774,8 @@ impl ClauseType {
 
     pub fn name(&self) -> ClauseName {
         match self {
-            &ClauseType::Arg => clause_name!("arg"),
+            &ClauseType::AcyclicTerm => clause_name!("acyclic_term"),
+            &ClauseType::Arg => clause_name!("arg"),            
             &ClauseType::CallN => clause_name!("call"),
             &ClauseType::CallWithInferenceLimit => clause_name!("call_with_inference_limit"),
             &ClauseType::Catch => clause_name!("catch"),
@@ -798,6 +800,7 @@ impl ClauseType {
 
     pub fn from(name: ClauseName, arity: usize, fixity: Option<Fixity>) -> Self {
         match (name.as_str(), arity) {
+            ("acyclic_term", 1) => ClauseType::AcyclicTerm,
             ("arg", 3)   => ClauseType::Arg,
             ("call", _)  => ClauseType::CallN,
             ("call_with_inference_limit", 3) => ClauseType::CallWithInferenceLimit,
diff --git a/src/prolog/heap_iter.rs b/src/prolog/heap_iter.rs
index 909442fa..a070dfdf 100644
--- a/src/prolog/heap_iter.rs
+++ b/src/prolog/heap_iter.rs
@@ -59,18 +59,16 @@ impl<'a> Iterator for HeapCellPreOrderIterator<'a> {
     type Item = HeapCellValue;
 
     fn next(&mut self) -> Option<Self::Item> {
-        if let Some(a) = self.state_stack.pop() {
+        self.state_stack.pop().map(|a| {
             match self.follow(a) {
-                Addr::HeapCell(h) => Some(self.machine_st.heap[h].clone()),
-                Addr::StackCell(fr, sc) => {
-                    let heap_val = HeapCellValue::Addr(self.machine_st.and_stack[fr][sc].clone());
-                    Some(heap_val)
-                },
-                da => Some(HeapCellValue::Addr(da))
+                Addr::HeapCell(h) =>
+                    self.machine_st.heap[h].clone(),
+                Addr::StackCell(fr, sc) =>
+                    HeapCellValue::Addr(self.machine_st.and_stack[fr][sc].clone()),
+                da =>
+                    HeapCellValue::Addr(da)
             }
-        } else {
-            None
-        }
+        })
     }
 }
 
@@ -119,6 +117,10 @@ impl<'a> Iterator for HeapCellPostOrderIterator<'a> {
 }
 
 impl MachineState {
+    pub fn pre_order_iter<'a>(&'a self, a: Addr) -> HeapCellPreOrderIterator<'a> {
+        HeapCellPreOrderIterator::new(self, a)
+    }
+    
     pub fn post_order_iter<'a>(&'a self, a: Addr) -> HeapCellPostOrderIterator<'a> {
         HeapCellPostOrderIterator::new(HeapCellPreOrderIterator::new(self, a))
     }
diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs
index 87a35947..1a31351f 100644
--- a/src/prolog/machine/machine_state.rs
+++ b/src/prolog/machine/machine_state.rs
@@ -1,6 +1,7 @@
 use prolog::and_stack::*;
 use prolog::ast::*;
 use prolog::copier::*;
+use prolog::heap_iter::*;
 use prolog::num::{BigInt, BigUint, Zero, One};
 use prolog::or_stack::*;
 use prolog::heap_print::*;
@@ -9,7 +10,7 @@ use prolog::tabled_rc::*;
 use downcast::Any;
 
 use std::cmp::Ordering;
-use std::collections::HashMap;
+use std::collections::{HashMap, HashSet};
 use std::mem::swap;
 use std::ops::{Index, IndexMut};
 use std::rc::Rc;
@@ -395,6 +396,33 @@ pub(crate) trait CallPolicy: Any {
                            -> CallResult
     {
         match ct {
+            &ClauseType::AcyclicTerm => {
+                let addr = machine_st[temp_v!(1)].clone();
+                let mut seen = HashSet::new();
+                let mut fail = false;
+                
+                {
+                    let mut iter = machine_st.pre_order_iter(addr);
+
+                    loop {
+                        if let Some(addr) = iter.stack().last() {
+                            if !seen.contains(addr) {                            
+                                seen.insert(addr.clone());
+                            } else {
+                                fail = true;
+                                break;
+                            }                            
+                        }
+
+                        if iter.next().is_none() {
+                            break;
+                        }
+                    }
+                }
+
+                machine_st.fail = fail;
+                return_from_clause!(lco, machine_st)
+            },
             &ClauseType::Arg => {
                 if !lco {
                     machine_st.cp = machine_st.p.clone() + 1;
-- 
2.54.0