From 12aaae5fc0b8b82fe7514808f8769c20935dfc63 Mon Sep 17 00:00:00 2001 From: bakaq Date: Thu, 15 Aug 2024 04:55:20 -0300 Subject: [PATCH] Differentiate anonymous variables --- src/machine/lib_machine.rs | 38 +++++++++++++++--- src/machine/parsed_results.rs | 75 +++++++++++++++++++++++++++++------ 2 files changed, 95 insertions(+), 18 deletions(-) diff --git a/src/machine/lib_machine.rs b/src/machine/lib_machine.rs index c42bcae0..ec264ed4 100644 --- a/src/machine/lib_machine.rs +++ b/src/machine/lib_machine.rs @@ -34,7 +34,7 @@ impl Iterator for QueryState<'_> { type Item = Result; fn next(&mut self) -> Option { - let var_names = &self.var_names; + let var_names = &mut self.var_names; let term_write_result = &self.term; let machine = &mut self.machine; @@ -91,11 +91,18 @@ impl Iterator for QueryState<'_> { let mut bindings: BTreeMap = BTreeMap::new(); for (var_key, term_to_be_printed) in &term_write_result.var_dict { - if var_key.to_string().starts_with('_') { - continue; + let var_name = var_key.to_string(); + if var_name.starts_with('_') { + let should_print = var_names.values().any(|x| match x.borrow().clone() { + Var::Named(v) => v == var_name, + _ => false, + }); + if !should_print { + continue; + } } - let term = Value::from_heapcell(machine, *term_to_be_printed, var_names); + let term = Value::from_heapcell(machine, *term_to_be_printed, &mut var_names.clone()); if let Value::Var(ref term_str) = term { if *term_str == var_key.to_string() { @@ -682,7 +689,7 @@ mod tests { ".".into(), vec![ Value::Atom("b".into()), - Value::AnonVar, // Anonymous variable + Value::Var("_A".into()), // Anonymous variable ], ), ], @@ -764,4 +771,25 @@ mod tests { assert_eq!(iterator.next(), Some(Ok(QueryResolutionLine::False))); assert_eq!(iterator.next(), None); } + + #[test] + #[cfg_attr(miri, ignore)] + fn differentiate_anonymous_variables() { + let mut machine = Machine::new_lib(); + + let result = machine.run_query("A = [_,_], _B = 1 ; B = [_,_].".into()); + + assert_eq!( + result, + Ok(QueryResolution::Matches(vec![ + QueryMatch::from(btreemap! { + "A" => Value::List(vec![Value::Var("_A".into()), Value::Var("_C".into())]), + "_B" => Value::Integer(1.into()), + }), + QueryMatch::from(btreemap! { + "B" => Value::List(vec![Value::Var("_A".into()), Value::Var("_C".into())]), + }), + ])) + ); + } } diff --git a/src/machine/parsed_results.rs b/src/machine/parsed_results.rs index 94dd5d98..06a8873b 100644 --- a/src/machine/parsed_results.rs +++ b/src/machine/parsed_results.rs @@ -1,10 +1,11 @@ use crate::atom_table::*; use crate::heap_iter::{stackful_post_order_iter, NonListElider}; use crate::machine::{F64Offset, F64Ptr, Fixnum, HeapCellValueTag}; -use crate::parser::ast; +use crate::parser::ast::{Var, VarPtr}; use dashu::*; use indexmap::IndexMap; use ordered_float::OrderedFloat; +use std::cmp::Ordering; use std::collections::BTreeMap; use std::collections::HashMap; use std::fmt::Display; @@ -138,14 +139,31 @@ pub enum Value { List(Vec), Structure(String, Vec), Var(String), - AnonVar, +} + +/// This is an auxiliary function to turn a count into names of anonymous variables like _A, _B, +/// _AB, etc... +fn count_to_letter_code(mut count: usize) -> String { + let mut letters = Vec::new(); + + loop { + let letter_idx = (count % 26) as u32; + letters.push(char::from_u32('A' as u32 + letter_idx).unwrap()); + count /= 26; + + if count == 0 { + break; + } + } + + letters.into_iter().chain("_".chars()).rev().collect() } impl Value { pub(crate) fn from_heapcell( machine: &mut Machine, heap_cell: HeapCellValue, - var_names: &IndexMap, + var_names: &mut IndexMap, ) -> Self { // Adapted from MachineState::read_term_from_heap let mut term_stack = vec![]; @@ -155,6 +173,18 @@ impl Value { heap_cell, ); + let mut anon_count: usize = 0; + let var_ptr_cmp = |a, b| match a { + Var::Named(name_a) => match b { + Var::Named(name_b) => name_a.cmp(&name_b), + _ => Ordering::Less, + }, + _ => match b { + Var::Named(_) => Ordering::Greater, + _ => Ordering::Equal, + }, + }; + for addr in iter { let addr = unmark_cell_bits!(addr); @@ -195,18 +225,37 @@ impl Value { term_stack.push(list); } (HeapCellValueTag::Var | HeapCellValueTag::AttrVar | HeapCellValueTag::StackVar) => { - if let Some(ast::Var::Named(name)) = var_names.get(&addr).map(|x| x.borrow().clone()) { - term_stack.push(Value::Var(name)); - } else { - // TODO: These variables aren't actually anonymous, they just aren't in the - // query. Give names to them to differentiate distinct variables. - term_stack.push(Value::AnonVar); + let var = var_names.get(&addr).map(|x| x.borrow().clone()); + match var { + Some(Var::Named(name)) => term_stack.push(Value::Var(name)), + _ => { + let anon_name = loop { + // Generate a name for the anonymous variable + let anon_name = count_to_letter_code(anon_count); + + // Find if this name is already being used + var_names.sort_by(|_, a, _, b| { + var_ptr_cmp(a.borrow().clone(), b.borrow().clone()) + }); + let binary_result = var_names.binary_search_by(|_,a| { + let var_ptr = Var::Named(anon_name.clone()); + var_ptr_cmp(a.borrow().clone(), var_ptr.clone()) + }); + + match binary_result { + Ok(_) => anon_count += 1, // Name already used + Err(_) => { + // Name not used, assign it to this variable + let var_ptr = VarPtr::from(Var::Named(anon_name.clone())); + var_names.insert(addr, var_ptr); + break anon_name; + }, + } + }; + term_stack.push(Value::Var(anon_name)); + }, } } - //(HeapCellValueTag::Cons | HeapCellValueTag::CStr | HeapCellValueTag::Fixnum | - // HeapCellValueTag::Char | HeapCellValueTag::F64) => { - // term_stack.push(Term::Literal(Cell::default(), Literal::try_from(addr).unwrap())); - //} (HeapCellValueTag::F64, f) => { term_stack.push(Value::Float(*f)); } -- 2.54.0