1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
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;
10 import java.lang.reflect.*;
12 /** a node in the GSS */
13 final class Node implements Invokable<Position, Node, Node>, IntegerMappable, GraphViz.ToGraphViz {
15 public static int node_idx = 0;
17 private final GSS.Phase phase;
19 public FastSet<Node> setx = new FastSet<Node>();
20 public FastSet<Node> childs = new FastSet<Node>();
22 private boolean allqueued = false;
24 /** what state this node is in */
25 public final Parser.Table.State state;
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; }
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) {
36 n.childs.add(this, true);
38 //System.out.println("************ evilstate: " + this);
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) {
48 Forest.Many f = new Forest.Many();
49 f.parents.add(parent);
52 addParent(parent, true);
56 public void performReductions() {
57 if (allqueued) return;
59 state.invokeReductions(phase().token(), this, this, null);
62 public void performReductions(Node n2) {
63 if (!allqueued) phase().reductionQueue.add(this);//performReductions();
64 else state.invokeReductions(phase().token(), this, this, n2);
67 public Parser.Table.State state() { return state; }
69 public void performEmptyReductions() { state.invokeReductions(phase().token, this, null, null); }
70 public final void invoke(Position r, Node n, Node n2) {
72 //if (r.pos==1) single_newnode++;
73 //if (r.pos>1) multi_newnode++;
74 if (n==null || n2==null || r.pos==0) {
76 if (n==null) n = this;
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);
84 if (r.pos<=0) throw new Error("called wrong form of reduce()");
86 n.reduce(r, pos, n.phase(), n2);
90 public void reduce(Position r, int pos, GSS.Phase target, Node only) {
91 Forest[] holder = r.holder;
92 Forest old = holder[pos];
94 //toplevel_reductions++;
95 HashSet<Forest> rr = new HashSet<Forest>();
96 for(Forest result : results()) {
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);
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();
115 target.newNode(this, result, state0, r.pos<=0, r);
118 Node(GSS.Phase phase, Node parent, Forest pending, 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);
127 public int toInt() { return idx; }
128 private final int idx = node_idx++;
130 // GraphViz //////////////////////////////////////////////////////////////////////////////
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);
144 public boolean isTransparent() { return false; }
145 public boolean isHidden() { return false; }