From d565f5901b5744fed571d9f7c33cea6220169743 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Tue, 27 Sep 2022 21:04:52 -0600 Subject: [PATCH] milestone marker for surgery --- build/instructions_template.rs | 2 + src/arithmetic.rs | 4 +- src/iterators.rs | 105 ++++++++++------- src/lib.rs | 1 + src/machine/dispatch.rs | 2 +- src/machine/loader.rs | 210 +++++++++++++++++---------------- src/parser/ast.rs | 27 +++++ 7 files changed, 204 insertions(+), 147 deletions(-) diff --git a/build/instructions_template.rs b/build/instructions_template.rs index bec70e7e..a7ea3d21 100644 --- a/build/instructions_template.rs +++ b/build/instructions_template.rs @@ -1644,6 +1644,7 @@ fn generate_instruction_preface() -> TokenStream { &Instruction::CallDeleteAllAttributesFromVar(_) | &Instruction::CallUnattributedVar(_) | &Instruction::CallGetDBRefs(_) | + &Instruction::CallEnqueueAttributedVar(_) | &Instruction::CallFetchGlobalVar(_) | &Instruction::CallFirstStream(_) | &Instruction::CallFlushOutput(_) | @@ -1866,6 +1867,7 @@ fn generate_instruction_preface() -> TokenStream { &Instruction::ExecuteDeleteAllAttributesFromVar(_) | &Instruction::ExecuteUnattributedVar(_) | &Instruction::ExecuteGetDBRefs(_) | + &Instruction::ExecuteEnqueueAttributedVar(_) | &Instruction::ExecuteFetchGlobalVar(_) | &Instruction::ExecuteFirstStream(_) | &Instruction::ExecuteFlushOutput(_) | diff --git a/src/arithmetic.rs b/src/arithmetic.rs index 0cbb1eab..fcfd9599 100644 --- a/src/arithmetic.rs +++ b/src/arithmetic.rs @@ -74,7 +74,7 @@ impl<'a> ArithInstructionIterator<'a> { 2, )) } - Term::Var(cell, var) => TermIterState::Var(Level::Shallow, cell, var.clone()), + Term::Var(cell, var) => TermIterState::Var(Level::Shallow, cell, RcMutPtr::new(var)), }; Ok(ArithInstructionIterator { @@ -116,7 +116,7 @@ impl<'a> Iterator for ArithInstructionIterator<'a> { } TermIterState::Literal(_, _, c) => return Some(Ok(ArithTermRef::Literal(c))), TermIterState::Var(lvl, cell, var) => { - return Some(Ok(ArithTermRef::Var(lvl, cell, var.clone()))); + return Some(Ok(ArithTermRef::Var(lvl, cell, var.owned()))); } _ => { return Some(Err(ArithmeticError::NonEvaluableFunctor( diff --git a/src/iterators.rs b/src/iterators.rs index de091d4a..6bf92a5f 100644 --- a/src/iterators.rs +++ b/src/iterators.rs @@ -6,6 +6,8 @@ use crate::parser::ast::*; use std::cell::Cell; use std::collections::VecDeque; use std::fmt; +use std::fmt::Debug; +use std::hash::{Hash, Hasher}; use std::iter::*; use std::rc::Rc; use std::vec::Vec; @@ -35,6 +37,58 @@ impl<'a> TermRef<'a> { } } +#[derive(Clone, Debug)] +pub(crate) struct RcMutPtr { + owned: Rc, + ptr: *mut Rc, +} + +impl RcMutPtr { + #[inline] + pub(crate) fn new(rc: &Rc) -> Self { + Self { owned: rc.clone(), ptr: rc as *const _ as *mut _ } + } + + #[inline] + pub(crate) fn owned(&self) -> Rc { + self.owned.clone() + } + + #[inline] + pub(crate) fn set(&mut self, var_b_marker: &Rc) { + self.owned = var_b_marker.clone(); + + unsafe { + if !self.ptr.is_null() { + *self.ptr = self.owned.clone(); + } + } + } +} + +impl From for RcMutPtr { + #[inline] + fn from(value: T) -> RcMutPtr { + let owned = Rc::new(value); + RcMutPtr { owned, ptr: std::ptr::null_mut() } + } +} + +impl PartialEq for RcMutPtr { + fn eq(&self, rhs: &Self) -> bool { + &self.owned == &rhs.owned + } +} + +impl Eq for RcMutPtr {} + +impl Hash for RcMutPtr { + #[inline(always)] + fn hash(&self, hasher: &mut H) { + self.owned.hash(hasher) + } +} + #[derive(Debug)] pub(crate) enum TermIterState<'a> { AnonVar(Level), @@ -45,7 +99,7 @@ pub(crate) enum TermIterState<'a> { InitialPartialString(Level, &'a Cell, &'a String, &'a Box), FinalPartialString(Level, &'a Cell, &'a String, &'a Box), CompleteString(Level, &'a Cell, Atom), - Var(Level, &'a Cell, Rc), + Var(Level, &'a Cell, RcMutPtr), } impl<'a> TermIterState<'a> { @@ -65,7 +119,7 @@ impl<'a> TermIterState<'a> { Term::CompleteString(cell, atom) => { TermIterState::CompleteString(lvl, cell, *atom) } - Term::Var(cell, var) => TermIterState::Var(lvl, cell, var.clone()), + Term::Var(cell, var) => TermIterState::Var(lvl, cell, RcMutPtr::new(var)), } } } @@ -106,7 +160,7 @@ impl<'a> QueryIterator<'a> { *name, terms, ), - Term::Var(cell, var) => TermIterState::Var(Level::Root, cell, var.clone()), + Term::Var(cell, var) => TermIterState::Var(Level::Root, cell, RcMutPtr::new(var)), }; QueryIterator { @@ -129,13 +183,13 @@ impl<'a> QueryIterator<'a> { } } &QueryTerm::UnblockedCut(ref cell) => { - let state = TermIterState::Var(Level::Root, cell, Rc::new("!".to_string())); + let state = TermIterState::Var(Level::Root, cell, RcMutPtr::from("!".to_string())); QueryIterator { state_stack: vec![state], } } &QueryTerm::GetLevelAndUnify(ref cell, ref var) => { - let state = TermIterState::Var(Level::Root, cell, var.clone()); + let state = TermIterState::Var(Level::Root, cell, RcMutPtr::new(var)); QueryIterator { state_stack: vec![state], } @@ -213,7 +267,7 @@ impl<'a> Iterator for QueryIterator<'a> { return Some(TermRef::Literal(lvl, cell, constant)); } TermIterState::Var(lvl, cell, var) => { - return Some(TermRef::Var(lvl, cell, var)); + return Some(TermRef::Var(lvl, cell, var.owned())); } }; } @@ -279,7 +333,7 @@ impl<'a> FactIterator<'a> { vec![TermIterState::Literal(Level::Root, cell, constant)] } Term::Var(cell, var) => { - vec![TermIterState::Var(Level::Root, cell, var.clone())] + vec![TermIterState::Var(Level::Root, cell, RcMutPtr::new(var))] } }; @@ -326,7 +380,7 @@ impl<'a> Iterator for FactIterator<'a> { return Some(TermRef::Literal(lvl, cell, constant)) } TermIterState::Var(lvl, cell, var) => { - return Some(TermRef::Var(lvl, cell, var)); + return Some(TermRef::Var(lvl, cell, var.owned())); } _ => {} } @@ -530,38 +584,3 @@ impl<'a> Iterator for ChunkedIterator<'a> { self.iter.next().map(|term| self.take_chunk(term)) } } - -/* -================================================================================ - -This is a disjunction compilation experiment attempting to -adapt the paper "Compiling Large Disjunctions" to Scryer Prolog. - -================================================================================ -*/ - -enum VarInfo { - Perm, - Temp, - Void -} - -pub struct ChunkInfo { - chunk_num: usize, - vars: Vec<(Rc, VarInfo)>, -} - -pub struct BranchInfo { - branch_num: usize, // TODO: Rational?? or own type? - delta: usize, // TODO: Rational?? - chunks: Vec, -} - -pub struct ControlIterator<'a> { - current_branch_num: usize, // TODO: same as above - state_stack: Vec>, - branch_map: IndexMap, Vec>, -} - -impl ControlIterator { -} diff --git a/src/lib.rs b/src/lib.rs index 45dc2385..b117ab16 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -27,6 +27,7 @@ pub mod instructions { include!(concat!(env!("OUT_DIR"), "/instructions.rs")); } mod iterators; +mod disjuncts; pub mod machine; mod raw_block; pub mod read; diff --git a/src/machine/dispatch.rs b/src/machine/dispatch.rs index 3067ecb9..04f39428 100644 --- a/src/machine/dispatch.rs +++ b/src/machine/dispatch.rs @@ -5253,7 +5253,7 @@ impl Machine { } &Instruction::ExecuteUnattributedVar(_) => { self.machine_st.unattributed_var(); - step_or_fail!(self, self.machine_st.p = self.machine_st.cp); + self.machine_st.p = self.machine_st.cp; } &Instruction::CallGetDBRefs(_) => { self.get_db_refs(); diff --git a/src/machine/loader.rs b/src/machine/loader.rs index 616fe7ee..f268c0f7 100644 --- a/src/machine/loader.rs +++ b/src/machine/loader.rs @@ -465,6 +465,11 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { } } + pub(crate) fn read_term_from_heap(&mut self, r: RegType) -> Result { + let machine_st = LS::machine_st(&mut self.payload); + machine_st.read_term_from_heap(r) + } + pub(crate) fn load(mut self) -> Result { while let Some(decl) = self.dequeue_terms()? { self.load_decl(decl)?; @@ -531,106 +536,6 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { Ok(()) } - pub(super) fn read_term_from_heap(&mut self, heap_term_loc: RegType) -> Result { - let machine_st = LS::machine_st(&mut self.payload); - let term_addr = machine_st[heap_term_loc]; - - let mut term_stack = vec![]; - let mut iter = stackful_post_order_iter(&mut machine_st.heap, term_addr); - - while let Some(addr) = iter.next() { - let addr = unmark_cell_bits!(addr); - - read_heap_cell!(addr, - (HeapCellValueTag::Lis) => { - use crate::parser::parser::as_partial_string; - - let tail = term_stack.pop().unwrap(); - let head = term_stack.pop().unwrap(); - - match as_partial_string(head, tail) { - Ok((string, Some(tail))) => { - term_stack.push(Term::PartialString(Cell::default(), string, tail)); - } - Ok((string, None)) => { - let atom = machine_st.atom_tbl.build_with(&string); - term_stack.push(Term::CompleteString(Cell::default(), atom)); - } - Err(cons_term) => term_stack.push(cons_term), - } - } - (HeapCellValueTag::Var | HeapCellValueTag::AttrVar | HeapCellValueTag::StackVar, h) => { - let offset_string = format!("_{}", h); - term_stack.push(Term::Var(Cell::default(), Rc::new(offset_string))); - } - (HeapCellValueTag::Cons | HeapCellValueTag::CStr | HeapCellValueTag::Fixnum | - HeapCellValueTag::Char | HeapCellValueTag::F64) => { - term_stack.push(Term::Literal(Cell::default(), Literal::try_from(addr).unwrap())); - } - (HeapCellValueTag::Atom, (name, arity)) => { - let h = iter.focus(); - let mut arity = arity; - - if iter.heap.len() > h + arity + 1 { - let value = iter.heap[h + arity + 1]; - - if let Some(idx) = get_structure_index(value) { - // in the second condition, arity == 0, - // meaning idx cannot pertain to this atom - // if it is the direct subterm of a larger - // structure. - if arity > 0 || !iter.direct_subterm_of_str(h) { - term_stack.push( - Term::Literal(Cell::default(), Literal::CodeIndex(idx)) - ); - - arity += 1; - } - } - } - - if arity == 0 { - term_stack.push(Term::Literal(Cell::default(), Literal::Atom(name))); - } else { - let subterms = term_stack - .drain(term_stack.len() - arity ..) - .collect(); - - term_stack.push(Term::Clause(Cell::default(), name, subterms)); - } - } - (HeapCellValueTag::PStr, atom) => { - let tail = term_stack.pop().unwrap(); - - if let Term::Literal(_, Literal::Atom(atom!("[]"))) = &tail { - term_stack.push(Term::CompleteString(Cell::default(), atom)); - } else { - term_stack.push(Term::PartialString( - Cell::default(), - atom.as_str().to_owned(), - Box::new(tail), - )); - } - } - (HeapCellValueTag::PStrLoc, h) => { - let atom = cell_as_atom_cell!(iter.heap[h]).get_name(); - let tail = term_stack.pop().unwrap(); - - term_stack.push(Term::PartialString( - Cell::default(), - atom.as_str().to_owned(), - Box::new(tail), - )); - } - _ => { - } - ); - } - - debug_assert!(term_stack.len() == 1); - Ok(term_stack.pop().unwrap()) - } - fn reset_machine(&mut self) { while let Some(record) = self.payload.retraction_info.records.pop() { match record { @@ -1143,7 +1048,9 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { &mut self, r: RegType, ) -> Result, SessionError> { - let export_list = self.read_term_from_heap(r)?; + let machine_st = LS::machine_st(&mut self.payload); + + let export_list = machine_st.read_term_from_heap(r)?; let atom_tbl = &mut LS::machine_st(&mut self.payload).atom_tbl; let export_list = setup_module_export_list(export_list, atom_tbl)?; @@ -1493,6 +1400,107 @@ impl<'a> MachinePreludeView<'a> { } } +impl MachineState { + pub(super) fn read_term_from_heap(&mut self, r: RegType) -> Result { + let term_addr = self[r]; + + let mut term_stack = vec![]; + let mut iter = stackful_post_order_iter(&mut self.heap, term_addr); + + while let Some(addr) = iter.next() { + let addr = unmark_cell_bits!(addr); + + read_heap_cell!(addr, + (HeapCellValueTag::Lis) => { + use crate::parser::parser::as_partial_string; + + let tail = term_stack.pop().unwrap(); + let head = term_stack.pop().unwrap(); + + match as_partial_string(head, tail) { + Ok((string, Some(tail))) => { + term_stack.push(Term::PartialString(Cell::default(), string, tail)); + } + Ok((string, None)) => { + let atom = self.atom_tbl.build_with(&string); + term_stack.push(Term::CompleteString(Cell::default(), atom)); + } + Err(cons_term) => term_stack.push(cons_term), + } + } + (HeapCellValueTag::Var | HeapCellValueTag::AttrVar | HeapCellValueTag::StackVar, h) => { + let offset_string = format!("_{}", h); + term_stack.push(Term::Var(Cell::default(), Rc::new(offset_string))); + } + (HeapCellValueTag::Cons | HeapCellValueTag::CStr | HeapCellValueTag::Fixnum | + HeapCellValueTag::Char | HeapCellValueTag::F64) => { + term_stack.push(Term::Literal(Cell::default(), Literal::try_from(addr).unwrap())); + } + (HeapCellValueTag::Atom, (name, arity)) => { + let h = iter.focus(); + let mut arity = arity; + + if iter.heap.len() > h + arity + 1 { + let value = iter.heap[h + arity + 1]; + + if let Some(idx) = get_structure_index(value) { + // in the second condition, arity == 0, + // meaning idx cannot pertain to this atom + // if it is the direct subterm of a larger + // structure. + if arity > 0 || !iter.direct_subterm_of_str(h) { + term_stack.push( + Term::Literal(Cell::default(), Literal::CodeIndex(idx)) + ); + + arity += 1; + } + } + } + + if arity == 0 { + term_stack.push(Term::Literal(Cell::default(), Literal::Atom(name))); + } else { + let subterms = term_stack + .drain(term_stack.len() - arity ..) + .collect(); + + term_stack.push(Term::Clause(Cell::default(), name, subterms)); + } + } + (HeapCellValueTag::PStr, atom) => { + let tail = term_stack.pop().unwrap(); + + if let Term::Literal(_, Literal::Atom(atom!("[]"))) = &tail { + term_stack.push(Term::CompleteString(Cell::default(), atom)); + } else { + term_stack.push(Term::PartialString( + Cell::default(), + atom.as_str().to_owned(), + Box::new(tail), + )); + } + } + (HeapCellValueTag::PStrLoc, h) => { + let atom = cell_as_atom_cell!(iter.heap[h]).get_name(); + let tail = term_stack.pop().unwrap(); + + term_stack.push(Term::PartialString( + Cell::default(), + atom.as_str().to_owned(), + Box::new(tail), + )); + } + _ => { + } + ); + } + + debug_assert!(term_stack.len() == 1); + Ok(term_stack.pop().unwrap()) + } +} + impl Machine { pub(crate) fn use_module(&mut self) -> CallResult { let subevacuable_addr = self diff --git a/src/parser/ast.rs b/src/parser/ast.rs index 0933b11c..cf7bf946 100644 --- a/src/parser/ast.rs +++ b/src/parser/ast.rs @@ -667,3 +667,30 @@ pub fn unfold_by_str(mut term: Term, s: Atom) -> Vec { terms.push(term); terms } + +fn unfold_by_str_ref_once(term: &Term, s: Atom) -> Option<(&Term, &Term)> { + if let Term::Clause(_, ref name, ref subterms) = term { + if name == &s && subterms.len() == 2 { + let fst = &subterms[0]; + let snd = &subterms[1]; + + return Some((fst, snd)); + } + } + + None +} + +pub fn unfold_by_str_ref(mut term: &Term, s: Atom) -> Vec<&Term> { + let mut terms = vec![]; + + while let Some((fst, snd)) = unfold_by_str_ref_once(&term, s) { + terms.push(fst); + term = snd; + } + + terms.push(term); + terms +} + + -- 2.54.0