X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=6d5f8abaa6d238ec72fc4f1f1ae082df727fdbbe;hp=dcc8f3353d89663922812885b8973dc46fefa4ba;hb=4989eef7b4c4ff06e54f89ffd78b1483da088d6e;hpb=7fbee73b4dd985cb5b217ed297710c00fd9d7004 diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index dcc8f33..6d5f8ab 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -115,17 +115,17 @@ class GSS { if (!fromEmptyReduction) n.queueReductions(); } + + boolean reducing = false; /** perform all reduction operations */ public void reduce() { + reducing = true; HashSet s = new HashSet(); s.addAll(hash.values()); - for(Phase.Node n : s) { - n.queueEmptyReductions(); - n.queueReductions(); - } - while(pendingReduct.size()>0) - //pendingReduct.iterator().next().go(); - pendingReduct.removeFirst().go(); + //while(pendingReduct.size()>0) + //pendingReduct.removeFirst().go(); + for(Phase.Node n : s) n.queueEmptyReductions(); + for(Phase.Node n : s) n.queueReductions(); } /** perform all shift operations, adding promoted nodes to next */ @@ -134,6 +134,7 @@ class GSS { Forest res = null; boolean ok = false; for(Phase.Node n : hash.values()) { + if (n.holder==null) continue; n.holder.resolve(); if (token == null && n.state.isAccepting()) { ok = true; @@ -154,10 +155,10 @@ class GSS { error.append("error: unable to shift token \"" + token + "\"\n"); error.append(" before: " +pendingReductions+ "\n"); error.append(" before: " +totalReductions+ "\n"); - for(Phase.Node n : hash.values()) { - n.queueReductions(); - n.queueEmptyReductions(); - } + //for(Phase.Node n : hash.values()) { + //n.queueReductions(); + //n.queueEmptyReductions(); + //} error.append(" after: " +pendingReductions+ "\n"); error.append(" candidate states:\n"); for(Phase.Node n : hash.values()) { @@ -205,18 +206,21 @@ class GSS { queueReductions(n2); } + private HashSet queued = new HashSet(); /** FIXME */ public void queueReductions(Node n2) { - newReduct(this, n2, null); + if (queued.contains(n2)) return; + queued.add(n2); + new Reduct(this, n2, null).go(); } /** FIXME */ public void queueEmptyReductions() { - for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token)) { - if (r.numPop==0) - newReduct(this, null, r); /* ALLOC */ - } + if (reducing) + for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token)) + if (r.numPop==0) + r.reduce(this, null, this.phase, r.zero()); } private Node(Node parent, Forest pending, Parser.Table.State state, Phase start) { @@ -230,10 +234,6 @@ class GSS { } } - public void newReduct(Node n, Node n2, Parser.Table.Reduction r) { - new Reduct(n, n2, r)/*.go()*/; - } - // Forest / Completed Reductions ////////////////////////////////////////////////////////////////////////////// /** a pending or completed reduction */ @@ -259,10 +259,11 @@ class GSS { this.n = n; this.n2 = n2; this.r = r; - if (reductions.contains(this)) { done = true; return; } + //if (reductions.contains(this)) { done = true; return; } reductions.add(this); pendingReduct.addFirst(this); pendingReductions++; + go(); } /** perform the reduction */ @@ -272,44 +273,36 @@ class GSS { pendingReduct.remove(this); pendingReductions--; - if (r==null) + 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 == 1) new Reduct(n, n2, r).go(); - } - - - // FIXME: explain this - if (r==null) { - for(Parser.Table.Reduction r : token==null ? n.state.getEofReductions() : n.state.getReductions(token)) { - if (r.numPop <= 1) continue; - r.reduce(n, n2, Phase.this, null); + 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==0) { r.reduce(n, n2, n.phase, r.zero()); - } else if (r.numPop==1) { - // UGLY HACK - // The problem here is that a "reduction of length 0/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. - - 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 { + } else if (r.numPop != 1) { r.reduce(n, n2, Phase.this, null); } } @@ -338,5 +331,5 @@ class GSS { private static long code(Parser.Table.State state, Phase start) { return (((long)state.idx) << 32) | (start==null ? 0 : start.pos); } - + public boolean yak = false; }