src/edu/berkeley/sbp/Node.java

   1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp;
   4 import edu.berkeley.sbp.*;
   5 import edu.berkeley.sbp.util.*;
   6 import edu.berkeley.sbp.Parser.Table.*;
   7 import edu.berkeley.sbp.Sequence.Position;
   8 import java.io.*;
   9 import java.util.*;
  10 import java.lang.reflect.*;
  11
  12 /** a node in the GSS */
  13 final class Node
  14     implements Invokable<Position, Boolean, Result>,
  15                IntegerMappable,
  16                GraphViz.ToGraphViz,
  17                Iterable<Result> {
  18
  19     /** which GSS.Phase this Node belongs to */
  20     public  GSS.Phase phase() { return phase; }
  21     public Iterator<Result> iterator() { return results.iterator(); }
  22     public Parser.Table.State state() { return state; }
  23
  24     public int toInt() { return idx; }
  25
  26     public boolean merge(Result r) {
  27         if (results.contains(r)) return true;
  28         results.add(r);
  29         r.addChild(this);
  30         if (fromEmptyReduction) return false;
  31         state.invokeReductions(phase().getToken(), this, false, r);
  32         return false;
  33     }
  34
  35     private boolean destroyed = false;
  36     public boolean check() {
  37         boolean dead = true;
  38         // - all nodes must have a parent
  39         // - non-doomed nodes must either:
  40         //      - be on the frontier or
  41         //      - have a non-doomed node closer to the frontier than themself
  42
  43         if (phase.isFrontier()) dead = false;
  44         for(Result r : children)
  45             if (state.doomed) { if (r.usedByAnyNode()) dead = false; }
  46             else              { if (r.usedByNonDoomedNode()) dead = false; }
  47         dead |= results.size()==0;
  48         if (!dead || destroyed) return dead;
  49         destroyed = true;
  50         while(children.size()>0)
  51             for(Result r : children) {
  52                 children.remove(r);
  53                 r.destroy();
  54                 break;
  55             }
  56         while(results.size()>0)
  57             for(Result r : results) {
  58                 results.remove(r);
  59                 r.removeChild(this);
  60                 r.check();
  61                 break;
  62             }
  63         return dead;
  64     }
  65
  66     //////////////////////////////////////////////////////////////////////
  67
  68     private static int node_idx = 0;
  69     private final int idx = node_idx++;
  70
  71     private final GSS.Phase phase;
  72     private final Parser.Table.State state;
  73     private final boolean fromEmptyReduction;
  74     //private       FastSet<Result> results = new FastSet<Result>();
  75     private       HashSet<Result> results = new HashSet<Result>();
  76     private       HashSet<Result> children = new HashSet<Result>();
  77     public void removeChild(Result child) { children.remove(child); }
  78     public void removeResult(Result result) { results.remove(result); }
  79     public void addChild(Result child) { children.add(child); }
  80
  81     public final void invoke(Position r, Boolean emptyProductions, Result only) {
  82         if (emptyProductions != (r.pos==0)) return;
  83         if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase());
  84         else          reduce(r, r.pos-1, phase(), only);
  85     }
  86
  87     private void reduce(Position r, int pos, GSS.Phase target, Result only) {
  88         Forest[] holder = r.holder;
  89         Forest old = holder[pos];
  90         for(Result res : results)
  91             if (only == null || res == only) {
  92                 Node child = res.parent();
  93                 holder[pos] = res.getForest();
  94                 if (pos>0)  child.reduce(r, pos-1, target, null);
  95                 else new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
  96             }
  97         holder[pos] = old;
  98     }
  99
 100     void finish(Position r, Forest forest, GSS.Phase target) {
 101         Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner());
 102         Result result = new Result(forest, this, r);
 103         target.newNodeFromReduction(result, state0, r.pos<=0, r);
 104     }
 105
 106     Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) {
 107         this.phase = phase;
 108         this.state = state;
 109         this.fromEmptyReduction = fromEmptyReduction;
 110         results.add(result);
 111         result.addChild(this);
 112         if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
 113         phase.hash.put(state, result.phase(), this);
 114
 115         for(Object s : state.also)
 116             phase.newNode(new Result(null, this, null), (State)s, fromEmptyReduction);
 117
 118         state.invokeReductions(phase().token, this, true, null);
 119         if (!fromEmptyReduction)
 120             state.invokeReductions(phase().getToken(), this, false, null);
 121     }
 122
 123     // GraphViz //////////////////////////////////////////////////////////////////////////////
 124
 125     public GraphViz.Node toGraphViz(GraphViz gv) {
 126         if (results.size()==0) return null;
 127         if (gv.hasNode(this)) return gv.createNode(this);
 128         GraphViz.Node n = gv.createNode(this);
 129         n.label = ""+state.toStringx();
 130         n.shape = "rectangle";
 131         boolean hasparents = false;
 132         for(Result r : results) n.edge(r, "");
 133         n.color = state.doomed ? "red" : "green";
 134         ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
 135         return n;
 136     }
 137     public boolean isTransparent() { return false; }
 138     public boolean isHidden() { return false; }
 139
 140 }