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 implements Invokable<Position, Node, Node>, IntegerMappable, GraphViz.ToGraphViz {
  14
  15     public static int node_idx = 0;
  16
  17     private final GSS.Phase phase;
  18
  19     public FastSet<Node> setx = new FastSet<Node>();
  20     public FastSet<Node> childs = new FastSet<Node>();
  21
  22     private boolean allqueued = false;
  23
  24     /** what state this node is in */
  25     public final Parser.Table.State state;
  26
  27     /** which GSS.Phase this Node belongs to (node that Node is also a non-static inner class of GSS.Phase) */
  28     public  GSS.Phase phase() { return phase; }
  29
  30     private HashSet<Forest.Many> resultMap = new HashSet<Forest.Many>();
  31     public Iterable<Forest.Many> results() { return resultMap; }
  32     public Iterable<Node> parents() { return setx; }
  33     public void addParent(Node n, boolean b) {
  34         if (n==null) return;
  35         setx.add(n, b);
  36         n.childs.add(this, true);
  37         //else
  38         //System.out.println("************ evilstate: " + this);
  39     }
  40     public boolean merge(Node parent, Forest result) {
  41         // FIXME: inefficient!
  42         for(Forest.Many f : results()) {
  43             if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) {
  44                 f.merge(result);
  45                 return true;
  46             }
  47         }
  48         Forest.Many f = new Forest.Many();
  49         f.parents.add(parent);
  50         f.merge(result);
  51         resultMap.add(f);
  52         addParent(parent, true);
  53         return false;
  54     }
  55
  56     public void performReductions() {
  57         if (allqueued) return;
  58         allqueued = true;
  59         state.invokeReductions(phase().token(), this, this, null);
  60     }
  61
  62     public void performReductions(Node n2) {
  63         if (!allqueued) phase().reductionQueue.add(this);//performReductions();
  64         else            state.invokeReductions(phase().token(), this, this, n2);
  65     }
  66
  67     public Parser.Table.State state() { return state; }
  68
  69     public void performEmptyReductions() { state.invokeReductions(phase().token, this, null, null); }
  70     public final void invoke(Position r, Node n, Node n2) {
  71         //reductions++;
  72         //if (r.pos==1) single_newnode++;
  73         //if (r.pos>1) multi_newnode++;
  74         if (n==null || n2==null || r.pos==0) {
  75             if (r.pos==0) {
  76                 if (n==null) n = this;
  77                 else return;
  78             }
  79             if (n==null) return;
  80             Forest[] holder = new Forest[r.pos];
  81             if (r.pos==0) n.finish(r, r.zero(n.phase().getLocation().createRegion(n.phase().getLocation())), n.phase());
  82             else          n.reduce(r, r.pos-1,  n.phase(), null);
  83         } else {
  84             if (r.pos<=0) throw new Error("called wrong form of reduce()");
  85             int pos = r.pos-1;
  86             n.reduce(r, pos, n.phase(), n2);
  87         }
  88     }
  89
  90     public void reduce(Position r, int pos, GSS.Phase target, Node only) {
  91         Forest[] holder = r.holder;
  92         Forest old = holder[pos];
  93
  94         //toplevel_reductions++;
  95         HashSet<Forest> rr = new HashSet<Forest>();
  96         for(Forest result : results()) {
  97             rr.add(result);
  98         }
  99         //System.out.println(r);
 100         for(Forest result : rr) {
 101             for(Node child : ((Forest.Many<?>)result).parents) {
 102                 if (only != null && child!=only) continue;
 103                 holder[pos] = result;
 104                 if (pos==0) child.finish(r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
 105                 else        child.reduce(r, pos-1, target, null);
 106             }
 107         }
 108         holder[pos] = old;
 109     }
 110
 111     public void finish(Position r, Forest result, GSS.Phase target) {
 112         Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner());
 113         if (result==null) throw new Error();
 114         if (state0!=null)
 115             target.newNode(this, result, state0, r.pos<=0, r);
 116     }
 117
 118     Node(GSS.Phase phase, Node parent, Forest pending, State state) {
 119         this.phase = phase;
 120         this.state = state;
 121         this.merge(parent, pending);
 122         GSS.Phase start = parent==null ? null : parent.phase();
 123         if (parent != null) addParent(parent, true);
 124         if (phase.hash.get(state, start) != null) throw new Error("severe problem!");
 125         phase.hash.put(state, start, this);
 126     }
 127     public int toInt() { return idx; }
 128     private final int idx = node_idx++;
 129
 130     // GraphViz //////////////////////////////////////////////////////////////////////////////
 131
 132     public GraphViz.Node toGraphViz(GraphViz gv) {
 133         if (gv.hasNode(this)) return gv.createNode(this);
 134         GraphViz.Node n = gv.createNode(this);
 135         n.label = ""+state.toStringx();
 136         n.shape = "rectangle";
 137         boolean hasparents = false;
 138         for(Node parent : parents()) { hasparents = true; n.edge(parent, ""); }
 139         for(Forest result : results()) n.edge(result, "");
 140         n.color = !hasparents ? "blue" : /*state.evil ? "red" :*/ "green";
 141         ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
 142         return n;
 143     }
 144     public boolean isTransparent() { return false; }
 145     public boolean isHidden() { return false; }
 146
 147 }