From 0fb64f412ea3ff4fca62ba2a0f25bb7ee21131c4 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sat, 13 Jan 2018 21:50:47 -0700 Subject: [PATCH] refactor heapview --- src/prolog/ast.rs | 4 +- src/prolog/heap_iter.rs | 88 +++++++++++++ src/prolog/heap_print.rs | 135 +++++++++++++++++++ src/prolog/heapview.rs | 196 ---------------------------- src/prolog/machine/machine_state.rs | 2 +- src/prolog/machine/mod.rs | 33 ++++- src/prolog/mod.rs | 3 +- 7 files changed, 257 insertions(+), 204 deletions(-) create mode 100644 src/prolog/heap_iter.rs create mode 100644 src/prolog/heap_print.rs delete mode 100644 src/prolog/heapview.rs diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 474bfc72..a385843a 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -15,12 +15,12 @@ use std::rc::Rc; use std::str::Utf8Error; use std::vec::Vec; +pub const LEXER_BUF_SIZE: usize = 4096; + pub type Atom = String; pub type Var = String; -pub const LEXER_BUF_SIZE: usize = 4096; - #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)] pub enum GenContext { Head, Mid(usize), Last(usize) // Mid & Last: chunk_num diff --git a/src/prolog/heap_iter.rs b/src/prolog/heap_iter.rs new file mode 100644 index 00000000..ec830e0c --- /dev/null +++ b/src/prolog/heap_iter.rs @@ -0,0 +1,88 @@ +use prolog::ast::*; +use prolog::machine::machine_state::MachineState; + +use std::vec::Vec; + +pub struct HeapCellIterator<'a> { + machine_st : &'a MachineState, + state_stack : Vec +} + +impl<'a> HeapCellIterator<'a> { + pub fn new(machine_st: &'a MachineState, r: Ref) -> Self + { + let mut iter = HeapCellIterator { + machine_st, + state_stack: vec![] + }; + + iter.state_stack.push(r); + iter + } + + // called under the assumption that the location at r is about to + // be visited, and so any follow up states need to be added to + // state_stack. returns the dereferenced Addr from Ref. + fn follow(&mut self, r: Ref) -> Addr + { + match r { + Ref::HeapCell(hc) => self.follow_heap(hc), + Ref::StackCell(fr, sc) => self.follow_addr(Addr::StackCell(fr, sc)) + } + } + + fn follow_heap(&mut self, h: usize) -> Addr + { + match &self.machine_st.heap[h] { + &HeapCellValue::NamedStr(arity, _) => { + for idx in (1 .. arity + 1).rev() { + self.state_stack.push(Ref::HeapCell(h + idx)); + } + + Addr::HeapCell(h) + }, + &HeapCellValue::Addr(ref a) => + self.follow_addr(a.clone()) + } + } + + fn follow_addr(&mut self, addr: Addr) -> Addr + { + let da = self.machine_st.store(self.machine_st.deref(addr)); + + match &da { + &Addr::Con(_) => da, + &Addr::Lis(a) => { + self.state_stack.push(Ref::HeapCell(a + 1)); + self.state_stack.push(Ref::HeapCell(a)); + + da + }, + &Addr::HeapCell(_) | &Addr::StackCell(_, _) => + da, + &Addr::Str(s) => { + self.follow_heap(s); // record terms of structure. + Addr::HeapCell(s) + } + } + } +} + +impl<'a> Iterator for HeapCellIterator<'a> { + type Item = HeapCellValue; + + fn next(&mut self) -> Option { + if let Some(r) = self.state_stack.pop() { + match self.follow(r) { + 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)) + } + } else { + None + } + } +} diff --git a/src/prolog/heap_print.rs b/src/prolog/heap_print.rs new file mode 100644 index 00000000..ddfdc17e --- /dev/null +++ b/src/prolog/heap_print.rs @@ -0,0 +1,135 @@ +use prolog::ast::*; +use prolog::heap_iter::*; + +use std::cell::Cell; +use std::rc::Rc; + +#[derive(Clone)] +pub enum TokenOrRedirect { + Atom(Rc), + Redirect, + Open, + Close, + Comma, + OpenList(Rc>), + CloseList(Rc>), + HeadTailSeparator +} + +pub trait HeapCellValueFormatter { + // this function belongs to the display predicate formatter. + fn format_clause(&self, arity: usize, name: Rc, state_stack: &mut Vec) + { + state_stack.push(TokenOrRedirect::Close); + + for _ in 0 .. arity { + state_stack.push(TokenOrRedirect::Redirect); + state_stack.push(TokenOrRedirect::Comma); + } + + state_stack.pop(); + state_stack.push(TokenOrRedirect::Open); + + state_stack.push(TokenOrRedirect::Atom(name)); + } +} + +// the 'classic' display corresponding to the display predicate. +pub struct DisplayFormatter {} + +impl HeapCellValueFormatter for DisplayFormatter {} + +pub struct HeapCellPrinter<'a, Formatter> { + formatter: Formatter, + iter: HeapCellIterator<'a>, + state_stack: Vec +} + +impl<'a, Formatter: HeapCellValueFormatter> HeapCellPrinter<'a, Formatter> +{ + pub fn new(iter: HeapCellIterator<'a>, formatter: Formatter) -> Self { + HeapCellPrinter { formatter, iter, state_stack: vec![] } + } + + fn handle_heap_term(&mut self, heap_val: HeapCellValue, result: &mut String) { + match heap_val { + HeapCellValue::NamedStr(arity, name) => + self.formatter.format_clause(arity, name, &mut self.state_stack), + HeapCellValue::Addr(Addr::Con(Constant::EmptyList)) => + if !Self::at_cdr(result, "") { + *result += "[]"; + }, + HeapCellValue::Addr(Addr::Con(c)) => + *result += format!("{}", c).as_str(), + HeapCellValue::Addr(Addr::Lis(_)) => { + let cell = Rc::new(Cell::new(true)); + + self.state_stack.push(TokenOrRedirect::CloseList(cell.clone())); + + self.state_stack.push(TokenOrRedirect::Redirect); + self.state_stack.push(TokenOrRedirect::HeadTailSeparator); // bar + self.state_stack.push(TokenOrRedirect::Redirect); + + self.state_stack.push(TokenOrRedirect::OpenList(cell)); + }, + HeapCellValue::Addr(Addr::HeapCell(h)) => + *result += format!("_{}", h).as_str(), + HeapCellValue::Addr(Addr::StackCell(fr, sc)) => + *result += format!("s_{}_{}", fr, sc).as_str(), + HeapCellValue::Addr(Addr::Str(_)) => {} + } + } + + fn at_cdr(result: &mut String, tr: &str) -> bool { + let len = result.len(); + + if result.ends_with(" | ") { + result.truncate(len - 3); + *result += tr; + true + } else { + false + } + } + + pub fn print(&mut self) -> String { + let mut result = String::new(); + + loop { + if let Some(loc_data) = self.state_stack.pop() { + match loc_data { + TokenOrRedirect::Atom(atom) => + result += atom.as_str(), + TokenOrRedirect::Redirect => { + let heap_val = self.iter.next().unwrap(); + self.handle_heap_term(heap_val, &mut result); + }, + TokenOrRedirect::Close => + result += ")", + TokenOrRedirect::Open => + result += "(", + TokenOrRedirect::OpenList(delimit) => + if !Self::at_cdr(&mut result, ", ") { + result += "["; + } else { + delimit.set(false); + }, + TokenOrRedirect::CloseList(delimit) => + if delimit.get() == true { + result += "]"; + }, + TokenOrRedirect::HeadTailSeparator => + result += " | ", + TokenOrRedirect::Comma => + result += ", " + } + } else if let Some(heap_val) = self.iter.next() { + self.handle_heap_term(heap_val, &mut result); + } else { + break; + } + } + + result + } +} diff --git a/src/prolog/heapview.rs b/src/prolog/heapview.rs deleted file mode 100644 index f46fe65c..00000000 --- a/src/prolog/heapview.rs +++ /dev/null @@ -1,196 +0,0 @@ -use prolog::and_stack::*; -use prolog::ast::*; - -use std::vec::Vec; - -#[derive(Clone, Copy)] -pub enum TToken { - Bar, - Comma, - LRBracket, - LSBracket(usize), - Nothing, - RRBracket, - RSBracket -} - -impl TToken { - pub fn as_str(self) -> &'static str { - match self { - TToken::Bar => " | ", - TToken::Comma => ", ", - TToken::LRBracket => "(", - TToken::LSBracket(_) => "[", - TToken::Nothing => "", - TToken::RRBracket => ")", - TToken::RSBracket => "]" - } - } -} - -#[derive(Clone, Copy)] -enum CellRef<'a> { - Lis(usize), - View(CellView<'a>), - Redirect(usize), - TToken(TToken) -} - -#[derive(Clone, Copy)] -pub enum CellView<'a> { - Con(&'a Constant), - HeapVar(usize), - StackVar(usize, usize), - Str(usize, &'a Atom), - TToken(TToken), -} - -pub struct HeapCellViewer<'a> { - and_stack: &'a AndStack, - heap: &'a Heap, - state_stack: Vec> -} - -impl<'a> HeapCellViewer<'a> -{ - pub fn new(heap: &'a Heap, and_stack: &'a AndStack, addr: &'a Addr) -> Self - { - let mut viewer = HeapCellViewer { - heap: heap, - and_stack: and_stack, - state_stack: vec![] - }; - - let cell_ref = viewer.deref_cell(addr); - let view = viewer.follow(cell_ref); - - viewer.state_stack.push(CellRef::View(view)); - - viewer - } - - fn deref_cell(&self, mut focus: &'a Addr) -> CellRef<'a> - { - loop { - match focus { - &Addr::Con(ref c) => - return CellRef::View(CellView::Con(c)), - &Addr::Lis(hc) => - return CellRef::Lis(hc), - &Addr::HeapCell(hc) | &Addr::Str(hc) => - return CellRef::Redirect(hc), - &Addr::StackCell(fr, sc) => { - match &self.and_stack[fr][sc] { - &Addr::StackCell(fr1, sc1) => { - if fr1 == fr && sc1 == sc { - return CellRef::View(CellView::StackVar(fr, sc)); - } - }, - _ => focus = &self.and_stack[fr][sc] - } - } - } - } - } - - pub fn remove_token(&mut self, loc: usize) { - self.state_stack[loc] = CellRef::TToken(TToken::Nothing); - } - - pub fn peek(&mut self) -> Option> { - let len = self.state_stack.len(); - - if len > 0 { - let last_elt = self.state_stack.pop().unwrap(); - let cell_view = self.follow(last_elt); - - self.state_stack.truncate(len - 1); - self.state_stack.push(last_elt); - - Some(cell_view) - } else { - None - } - } - - fn handle_list(&mut self, focus: usize) -> CellView<'a> { - self.state_stack.push(CellRef::TToken(TToken::RSBracket)); - - self.state_stack.push(CellRef::Redirect(focus + 1)); - self.state_stack.push(CellRef::TToken(TToken::Bar)); - self.state_stack.push(CellRef::Redirect(focus)); - - let len = self.state_stack.len() - 4; - - return CellView::TToken(TToken::LSBracket(len)); - } - - fn from_heap(&mut self, mut focus: usize) -> CellView<'a> { - loop { - match &self.heap[focus] { - &HeapCellValue::NamedStr(arity, ref name) => { - self.state_stack.push(CellRef::TToken(TToken::RRBracket)); - - for i in (2 .. arity + 1).rev() { - self.state_stack.push(CellRef::Redirect(focus + i)); - self.state_stack.push(CellRef::TToken(TToken::Comma)); - } - - self.state_stack.push(CellRef::Redirect(focus + 1)); - self.state_stack.push(CellRef::TToken(TToken::LRBracket)); - - return CellView::Str(arity, name); - }, - &HeapCellValue::Addr(ref a) => - match a { - &Addr::Con(ref c) => - return CellView::Con(c), - &Addr::Lis(a) => - return self.handle_list(a), - &Addr::HeapCell(hc) => - if focus == hc { - return CellView::HeapVar(hc); - } else { - focus = hc; - }, - &Addr::StackCell(fr, sc) => - match self.deref_cell(&self.and_stack[fr][sc]) { - CellRef::Lis(hc) => return self.handle_list(hc), - CellRef::View(cell_view) => return cell_view, - CellRef::Redirect(hc) => focus = hc, - CellRef::TToken(token) => return CellView::TToken(token) - }, - &Addr::Str(cell_num) => - focus = cell_num, - }, - - } - } - } - - fn follow(&mut self, cell_ref: CellRef<'a>) -> CellView<'a> - { - match cell_ref { - CellRef::Lis(hc) => - self.handle_list(hc), - CellRef::Redirect(hc) => - self.from_heap(hc), - CellRef::View(cell_view) => - cell_view, - CellRef::TToken(term_token) => - CellView::TToken(term_token) - } - } -} - -impl<'a> Iterator for HeapCellViewer<'a> { - type Item = CellView<'a>; - - fn next(&mut self) -> Option { - if let Some(cell_ref) = self.state_stack.pop() { - Some(self.follow(cell_ref)) - } else { - None - } - } -} diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index b1e08e87..fe28879e 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -221,7 +221,7 @@ impl MachineState { if self.b > 0 { self.or_stack[self.b - 1].global_index } else { 0 }) + 1 } - pub(super) fn store(&self, a: Addr) -> Addr { + pub(crate) fn store(&self, a: Addr) -> Addr { match a { Addr::HeapCell(r) => self.heap[r].as_addr(r), Addr::StackCell(fr, sc) => self.and_stack[fr][sc].clone(), diff --git a/src/prolog/machine/mod.rs b/src/prolog/machine/mod.rs index 259c06d9..7aa20bf7 100644 --- a/src/prolog/machine/mod.rs +++ b/src/prolog/machine/mod.rs @@ -1,7 +1,8 @@ use prolog::ast::*; use prolog::builtins::*; use prolog::codegen::*; -use prolog::heapview::*; +use prolog::heap_iter::*; +use prolog::heap_print::*; use prolog::fixtures::*; pub(crate) mod machine_state; @@ -321,7 +322,7 @@ impl Machine { } } - pub fn continue_query<'a>(&mut self, alloc_locs: &AllocVarDict<'a>, heap_locs: &mut HeapVarDict<'a>) + pub fn continue_query<'a>(&mut self, alloc_l: &AllocVarDict<'a>, heap_l: &mut HeapVarDict<'a>) -> EvalSession<'a> { if !self.or_stack_is_empty() { @@ -332,7 +333,7 @@ impl Machine { return EvalSession::QueryFailure; } - self.run_query(alloc_locs, heap_locs); + self.run_query(alloc_l, heap_l); if self.failed() { self.fail() @@ -344,6 +345,30 @@ impl Machine { } } + fn print_var(&self, r: Ref) -> String + { + let disp = DisplayFormatter {}; + let iter = HeapCellIterator::new(&self.ms, r); + + let mut printer = HeapCellPrinter::new(iter, disp); + + printer.print() + } + + // NEW --- + fn print_term(&self, addr: &Addr) -> String + { + match addr { + &Addr::Con(ref c) => + format!("{}", c), + &Addr::Lis(h) | &Addr::HeapCell(h) | &Addr::Str(h) => + self.print_var(Ref::HeapCell(h)), + &Addr::StackCell(fr, sc) => + self.print_var(Ref::StackCell(fr, sc)) + } + } + +/* fn print_term(&self, addr: &Addr) -> String { let mut viewer = HeapCellViewer::new(&self.ms.heap, @@ -387,7 +412,7 @@ impl Machine { result } - +*/ pub fn heap_view(&self, var_dir: &HeapVarDict) -> String { let mut result = String::new(); diff --git a/src/prolog/mod.rs b/src/prolog/mod.rs index 533c3c1b..ad5c1b82 100644 --- a/src/prolog/mod.rs +++ b/src/prolog/mod.rs @@ -13,7 +13,8 @@ pub mod codegen; pub mod copier; pub mod debray_allocator; pub mod fixtures; -pub mod heapview; +pub mod heap_iter; +pub mod heap_print; pub mod indexing; pub mod io; pub mod iterators; -- 2.54.0