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         if (fromEmptyReduction) return false;
  30         state.invokeReductions(phase().getToken(), this, false, r);
  31         return false;
  32     }
  33
  34     //////////////////////////////////////////////////////////////////////
  35
  36     private static int node_idx = 0;
  37     private final int idx = node_idx++;
  38
  39     private final GSS.Phase phase;
  40     private final Parser.Table.State state;
  41     private final boolean fromEmptyReduction;
  42     //private       FastSet<Result> results = new FastSet<Result>();
  43     private       HashSet<Result> results = new HashSet<Result>();
  44
  45     public final void invoke(Position r, Boolean emptyProductions, Result only) {
  46         if (emptyProductions != (r.pos==0)) return;
  47         if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase());
  48         else          reduce(r, r.pos-1, phase(), only);
  49     }
  50
  51     private void reduce(Position r, int pos, GSS.Phase target, Result only) {
  52         Forest[] holder = r.holder;
  53         Forest old = holder[pos];
  54         for(Result res : results)
  55             if (only == null || res == only) {
  56                 Node child = res.parent();
  57                 holder[pos] = res.getForest();
  58                 if (pos>0)  child.reduce(r, pos-1, target, null);
  59                 else {
  60                     Reduction reduction =
  61                         new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
  62                     target.reductionQueue.add(reduction);
  63                 }
  64             }
  65
  66         holder[pos] = old;
  67     }
  68
  69     void finish(Position r, Forest forest, GSS.Phase target) {
  70         Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner());
  71         Result result = new Result(forest, this, r);
  72         target.newNodeFromReduction(result, state0, r.pos<=0, r);
  73     }
  74
  75     Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) {
  76         this.phase = phase;
  77         this.state = state;
  78         this.fromEmptyReduction = fromEmptyReduction;
  79         results.add(result);
  80         if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
  81         phase.hash.put(state, result.phase(), this);
  82
  83         for(Object s : state.also)
  84             phase.newNode(result, (State)s, fromEmptyReduction);
  85
  86         state.invokeReductions(phase().token, this, true, null);
  87         if (!fromEmptyReduction)
  88             state.invokeReductions(phase().getToken(), this, false, null);
  89     }
  90
  91     // GraphViz //////////////////////////////////////////////////////////////////////////////
  92
  93     public GraphViz.Node toGraphViz(GraphViz gv) {
  94         if (gv.hasNode(this)) return gv.createNode(this);
  95         GraphViz.Node n = gv.createNode(this);
  96         n.label = ""+state.toStringx();
  97         n.shape = "rectangle";
  98         boolean hasparents = false;
  99         //for(Node parent : parents()) { hasparents = true; n.edge(parent, ""); }
 100         //for(Forest result : resultMap) n.edge(result, "");
 101         n.color = !hasparents ? "blue" : /*state.evil ? "red" :*/ "green";
 102         ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
 103         return n;
 104     }
 105     public boolean isTransparent() { return false; }
 106     public boolean isHidden() { return false; }
 107
 108 }