From ea1414e738cac70a66d9c3ffdadcc51dc3049154 Mon Sep 17 00:00:00 2001
From: Mark Thom <markjordanthom@gmail.com>
Date: Sun, 11 Mar 2018 19:51:25 -0600
Subject: [PATCH] correct sort, keysort

---
 src/prolog/builtins.rs                   | 11 +++++++++--
 src/prolog/machine/machine_state_impl.rs | 24 ++++++++++++++++++++++--
 src/prolog/macros.rs                     | 12 ++++++++++++
 3 files changed, 43 insertions(+), 4 deletions(-)

diff --git a/src/prolog/builtins.rs b/src/prolog/builtins.rs
index 5da93945..535db093 100644
--- a/src/prolog/builtins.rs
+++ b/src/prolog/builtins.rs
@@ -622,7 +622,9 @@ fn get_builtins() -> Code {
          fail!(),
          compare_execute!(), // compare/3, 464.
          is_atom!(temp_v!(1)), // atom/1, 465.
-         proceed!()
+         proceed!(),
+         sort_execute!(), // sort/2, 467.
+         keysort_execute!() // keysort/2, 468.
     ]
 }
 
@@ -736,6 +738,8 @@ pub fn build_code_and_op_dirs() -> (CodeDir, OpDir)
     code_dir.insert((clause_name!("\\=@="), 2), (392, builtin.clone()));
     code_dir.insert((clause_name!("compare"), 3), (464, builtin.clone()));
     code_dir.insert((clause_name!("atom"), 1), (465, builtin.clone()));
+    code_dir.insert((clause_name!("sort"), 2), (467, builtin.clone()));
+    code_dir.insert((clause_name!("keysort"), 2), (468, builtin.clone()));
     
     (code_dir, op_dir)
 }
@@ -794,7 +798,10 @@ pub fn builtin_module() -> Module
                                             (clause_name!("ground"), 1),
                                             (clause_name!("setup_call_cleanup"), 3),
                                             (clause_name!("call_with_inference_limit"), 3),
-                                            (clause_name!("compare"), 3)]);
+                                            (clause_name!("compare"), 3),
+                                            (clause_name!("atom"), 1),
+                                            (clause_name!("sort"), 2),
+                                            (clause_name!("keysort"), 2)]);
 
     for arity in 0 .. 63 {
         module_decl.exports.push((clause_name!("call"), arity));
diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs
index 892d8911..97adb11d 100644
--- a/src/prolog/machine/machine_state_impl.rs
+++ b/src/prolog/machine/machine_state_impl.rs
@@ -1633,6 +1633,22 @@ impl MachineState {
         Ok(())
     }
 
+    fn term_dedup(&self, list: &mut Vec<Addr>) {
+        let mut result = vec![];
+
+        for a2 in list.iter().cloned() {
+            if let Some(a1) = result.last().cloned() {
+                if self.compare_term_test(&a1, &a2) == Ordering::Equal {
+                    continue;
+                }
+            }
+
+            result.push(a2);
+        }
+        
+        *list = result;
+    }
+    
     fn to_list<Iter: Iterator<Item=Addr>>(&mut self, values: Iter) -> usize {
         let head_addr = self.heap.h;
 
@@ -2082,6 +2098,8 @@ impl MachineState {
                 });
                                 
                 list.sort_unstable_by(|a1, a2| self.compare_term_test(a1, a2));
+                self.term_dedup(&mut list);
+                
                 let heap_addr = Addr::HeapCell(self.to_list(list.into_iter()));
                 
                 let r2 = self[temp_v!(2)].clone();
@@ -2095,6 +2113,8 @@ impl MachineState {
                 });
                 
                 list.sort_unstable_by(|a1, a2| self.compare_term_test(a1, a2));
+                self.term_dedup(&mut list);
+                
                 let heap_addr = Addr::HeapCell(self.to_list(list.into_iter()));
                 
                 let r2 = self[temp_v!(2)].clone();
@@ -2114,7 +2134,7 @@ impl MachineState {
                     key_pairs.push((key, val.clone()));
                 }
                 
-                key_pairs.sort_unstable_by(|a1, a2| self.compare_term_test(&a1.0, &a2.0));
+                key_pairs.sort_by(|a1, a2| self.compare_term_test(&a1.0, &a2.0));
                 
                 let key_pairs = key_pairs.into_iter().map(|kp| kp.1);
                 let heap_addr = Addr::HeapCell(self.to_list(key_pairs));
@@ -2136,7 +2156,7 @@ impl MachineState {
                     key_pairs.push((key, val.clone()));
                 }
                 
-                key_pairs.sort_unstable_by(|a1, a2| self.compare_term_test(&a1.0, &a2.0));
+                key_pairs.sort_by(|a1, a2| self.compare_term_test(&a1.0, &a2.0));
                 
                 let key_pairs = key_pairs.into_iter().map(|kp| kp.1);
                 let heap_addr = Addr::HeapCell(self.to_list(key_pairs));
diff --git a/src/prolog/macros.rs b/src/prolog/macros.rs
index 83834000..c6fed893 100644
--- a/src/prolog/macros.rs
+++ b/src/prolog/macros.rs
@@ -719,3 +719,15 @@ macro_rules! keysort_call {
         Line::Control(ControlInstruction::KeySortCall)
     )
 }
+
+macro_rules! sort_execute {
+    () => (
+        Line::Control(ControlInstruction::SortExecute)
+    )
+}
+
+macro_rules! keysort_execute {
+    () => (
+        Line::Control(ControlInstruction::KeySortExecute)
+    )
+}
-- 
2.54.0