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 new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
  60             }
  61         holder[pos] = old;
  62     }
  63
  64     void finish(Position r, Forest forest, GSS.Phase target) {
  65         Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner());
  66         Result result = new Result(forest, this, r);
  67         target.newNodeFromReduction(result, state0, r.pos<=0, r);
  68     }
  69
  70     Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) {
  71         this.phase = phase;
  72         this.state = state;
  73         this.fromEmptyReduction = fromEmptyReduction;
  74         results.add(result);
  75         if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
  76         phase.hash.put(state, result.phase(), this);
  77
  78         for(Object s : state.also)
  79             phase.newNode(new Result(null, this, null), (State)s, fromEmptyReduction);
  80
  81         state.invokeReductions(phase().token, this, true, null);
  82         if (!fromEmptyReduction)
  83             state.invokeReductions(phase().getToken(), this, false, null);
  84     }
  85
  86     // GraphViz //////////////////////////////////////////////////////////////////////////////
  87
  88     public GraphViz.Node toGraphViz(GraphViz gv) {
  89         if (results.size()==0) return null;
  90         if (gv.hasNode(this)) return gv.createNode(this);
  91         GraphViz.Node n = gv.createNode(this);
  92         n.label = ""+state.toStringx();
  93         n.shape = "rectangle";
  94         boolean hasparents = false;
  95         for(Result r : results) n.edge(r, "");
  96         n.color = state.doomed ? "red" : "green";
  97         ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
  98         return n;
  99     }
 100     public boolean isTransparent() { return false; }
 101     public boolean isHidden() { return false; }
 102
 103 }