From: adam Date: Wed, 4 Jan 2006 09:19:04 +0000 (-0500) Subject: checkpoint X-Git-Tag: tag_for_25-Mar~455 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=6c2a17e674b32389d281261796e9e962e9d9380c;hp=db08cd7213a2dbaa5146448d4d6f96b3f12e09b5;ds=sidebyside checkpoint darcs-hash:20060104091904-5007d-e59f6d5cdcc32808044286d3c5676974950e1041.gz --- diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 7dbb29c..8165ccd 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -21,10 +21,6 @@ import java.lang.reflect.*; // class is meant to remain simple and easy to understand; // optimizations which obscure that do not belong here (they // should go into the compiled version instead) -// -// - most of our time is now spent creating and storing Reduct instances -// - we should be able to perform Reduct's immediately after creating them... -// /** implements Tomita's Graph Structured Stack */ class GSS { @@ -43,18 +39,9 @@ class GSS { /** FIXME */ public Forest.Ref finalResult = null; - /** all reductions (pending and completed) */ - private HashSet reductions = new HashSet(); /* ALLOC */ - /** all nodes, keyed by the value returned by code() */ private HashMap hash = new HashMap(); /* ALLOC */ - /** the number of pending reductions */ - private int pendingReductions = 0; - private int totalReductions = 0; - //private HashSet pendingReduct = new HashSet(); - private LinkedList pendingReduct = new LinkedList(); - /** the number of nodes in this phase */ private int numNodes = 0; @@ -112,7 +99,7 @@ class GSS { Node n = new Node(parent, pending, state, start); // ALLOC n.queueEmptyReductions(); - if (!fromEmptyReduction) n.queueReductions(); + if (!fromEmptyReduction) n.queueReductions(parent); } @@ -122,8 +109,6 @@ class GSS { reducing = true; HashSet s = new HashSet(); s.addAll(hash.values()); - //while(pendingReduct.size()>0) - //pendingReduct.removeFirst().go(); for(Phase.Node n : s) n.queueEmptyReductions(); for(Phase.Node n : s) n.queueReductions(); } @@ -153,13 +138,13 @@ class GSS { if (!ok && token != null) { StringBuffer error = new StringBuffer(); error.append("error: unable to shift token \"" + token + "\"\n"); - error.append(" before: " +pendingReductions+ "\n"); - error.append(" before: " +totalReductions+ "\n"); + //error.append(" before: " +pendingReductions+ "\n"); + //error.append(" before: " +totalReductions+ "\n"); //for(Phase.Node n : hash.values()) { //n.queueReductions(); //n.queueEmptyReductions(); //} - error.append(" after: " +pendingReductions+ "\n"); + //error.append(" after: " +pendingReductions+ "\n"); error.append(" candidate states:\n"); for(Phase.Node n : hash.values()) { //for(Sequence.Position p : n.state) error.append(" " + p + "\n"); @@ -171,14 +156,12 @@ class GSS { } // this massively improves GC performance - reductions = null; hash = null; } // GSS Nodes ////////////////////////////////////////////////////////////////////////////// - //private HashMap pcache = new HashMap(); /** a node in the GSS */ public final class Node { @@ -202,13 +185,18 @@ class GSS { /** FIXME */ public void queueReductions() { - for(Node n2 : parents) - queueReductions(n2); + if (allqueued) return; + allqueued = true; + FastSet h = new FastSet(); + for(Node n : parents) h.add(n); + for(Node n : h) queueReductions(n); } + private boolean allqueued = false; private HashSet queued = new HashSet(); /** FIXME */ public void queueReductions(Node n2) { + if (!allqueued) { queueReductions(); return; } if (queued.contains(n2)) return; queued.add(n2); Node n = this; @@ -262,90 +250,6 @@ class GSS { } } - // Forest / Completed Reductions ////////////////////////////////////////////////////////////////////////////// - - /** a pending or completed reduction */ - class Reduct { - - /** the node from which the reduction should begin */ - public Node n = null; - - /** the node on the other end of the edge to be reduced along (either: null, the second node of the reduction, - * or the parent of the result of a length-one reduction) - */ - public Node n2 = null; - - /** true iff the reduction has already been performed */ - private boolean done = false; - - /** the reduction to be applied */ - public Parser.Table.Reduction r; - - public Tree result = null; - - public Reduct(Node n, Node n2, Parser.Table.Reduction r) { - this.n = n; - this.n2 = n2; - this.r = r; - //if (reductions.contains(this)) { done = true; return; } - //reductions.add(this); - //pendingReduct.addFirst(this); - //pendingReductions++; - go(); - } - - /** perform the reduction */ - public void go() { - if (done) return; - done = true; - //pendingReduct.remove(this); - //pendingReductions--; - - if (r==null) { - for(Parser.Table.Reduction r : token==null ? n.state.getEofReductions() : n.state.getReductions(token)) { - - // UGLY HACK - // The problem here is that a "reduction of length 1" - // performed twice with different values of n2 needs - // to only create a *single* new result, but must add - // multiple parents to the node holding that result. - // The current reducer doesn't differentiate between - // the next node of an n-pop reduction and the - // ultimate parent of the last pop, so we need to - // cache instances here as a way of avoiding - // recreating them. - - // currently we have this weird problem where we - // have to do an individual reduct for each child - // when the reduction length is one (ie the - // children wind up being children of the newly - // created node rather than part of the popped - // sequence - if (r.numPop <= 0) continue; - if (r.numPop == 1) { - Forest ret = n.cache().get(r); - if (ret != null) r.reduce(n, n2, n.phase, ret); - else n.cache().put(r, r.reduce(n, n2, n.phase, null)); - } else { - r.reduce(n, n2, Phase.this, null); - } - } - } else if (r.numPop != 1) { - r.reduce(n, n2, Phase.this, null); - } - } - - // FIXME: this is a PITA - public int hashCode() { return n.hashCode() ^ (r==null ? 0 : r.hashCode()) ^ (n2==null ? 0 : n2.hashCode()); } - public boolean equals(Object o) { - if (o==null) return false; - if (o==this) return true; - if (!(o instanceof Reduct)) return false; - Reduct other = (Reduct)o; - return equal(r, other.r) && equal(n, other.n) && equal(n2, other.n2); - } - } - } /** helper method */ diff --git a/tests/regression.tc b/tests/regression.tc index a713405..c2206ee 100644 --- a/tests/regression.tc +++ b/tests/regression.tc @@ -263,62 +263,62 @@ testcase { idl ::= [a-d] } -testcase { - - input " - - - while x>0 - while y>0 - foo() - bar() - - while x>0 - while y>0 - foo() - bar() - - -"; - output "smt:{while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}}}"; - output "smt:{while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}"; - -indent !::= ww -outdent !::= " " outdent " " - | " " (~[]*) "\n" - -any !::= ~[]* -s ::= any "\n\n" ww statement ww "\n\n" any => smt -ww !::= sp* -ws !::= sp** -sp ::= " " - -block ::= "\n" indent blockBody - &~ "\n" outdent ~[\ ] ~[]* - -blockBody ::= statement - > statement blockBody /ws => "sbb" - -statement ::= call - | ^"while" expr block /ws - -expr ::= ident - | call - | expr ^">" expr /ws - | num - -call ::= expr "()" /ws - -num ::= [0-9]++ - -ident ::= [a-z]++ &~ keyword -keyword ::= "if" | "then" | "else" | "while" - -w ::= " " | "\n" | "\r" -ws ::= w* - - -} +//testcase { +// +// input " +// +// +// while x>0 +// while y>0 +// foo() +// bar() +// +// while x>0 +// while y>0 +// foo() +// bar() +// +// +//"; +// output "smt:{while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}}}"; +// output "smt:{while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}"; +// +//indent !::= ww +//outdent !::= " " outdent " " +// | " " (~[]*) "\n" +// +//any !::= ~[]* +//s ::= any "\n\n" ww statement ww "\n\n" any => smt +//ww !::= sp* +//ws !::= sp** +//sp ::= " " +// +//block ::= "\n" indent blockBody +// &~ "\n" outdent ~[\ ] ~[]* +// +//blockBody ::= statement +// > statement blockBody /ws => "sbb" +// +//statement ::= call +// | ^"while" expr block /ws +// +//expr ::= ident +// | call +// | expr ^">" expr /ws +// | num +// +//call ::= expr "()" /ws +// +//num ::= [0-9]++ +// +//ident ::= [a-z]++ &~ keyword +//keyword ::= "if" | "then" | "else" | "while" +// +//w ::= " " | "\n" | "\r" +//ws ::= w* +// +// +//} testcase { input "aa bb";