src/edu/berkeley/sbp/StateNode.java

   1 // Copyright 2006-2007 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.Pos;
   8 import edu.berkeley.sbp.Sequence.Pos;
   9 import java.io.*;
  10 import java.util.*;
  11 import java.lang.reflect.*;
  12
  13 /** a node in the GSS */
  14 final class StateNode
  15     extends Node<ResultNode>
  16     implements Invokable<Pos, ResultNode, Object> {
  17
  18     private final Parser.Table.State state;
  19     private  boolean fromEmptyReduction;
  20
  21     /** which GSS.Phase this StateNode belongs to */
  22     public Iterator<ResultNode> iterator() { return predecessors.iterator(); }
  23     public Parser.Table.State state() { return state; }
  24     public boolean isDoomedState() { return state.doomed; }
  25
  26     public void check() {
  27         if (destroyed) return;
  28         boolean dead = true;
  29         // - all nodes must have a predecessor
  30         // - non-doomed nodes must either:
  31         //      - be on the frontier or
  32         //      - have a non-doomed node closer to the frontier than themself
  33         if (phase().isFrontier()) dead = false;
  34         else for(ResultNode r : successors)
  35                  if (state.doomed) { if (r.hasSuccessors()) { dead = false; break; } }
  36                  else              { if (r.hasNonDoomedSuccessors()) { dead = false; break; } }
  37         dead |= predecessors.size()==0;
  38         if (!dead) return;
  39         if (phase() != null && phase().hash != null)
  40             phase().hash.remove(state, predecessorPhase());
  41         destroy();
  42     }
  43
  44     public final void invoke(Pos r, ResultNode only, Object o) {
  45         boolean emptyProductions = only==null;
  46         if (emptyProductions != (r.numPops()==0)) return;
  47         if (r.numPops()!=0)  reduce(r, r.numPops()-1, phase(), only);
  48         else {
  49             Input.Region region = phase().getLocation().createRegion(phase().getLocation());
  50             phase().newNodeFromReduction(r.rewrite(region), r, this);
  51         }
  52     }
  53
  54     private void reduce(Pos r, int pos, GSS.Phase target, ResultNode only) {
  55         for(ResultNode res : predecessors)
  56             if (only == null || res == only)
  57                 for(StateNode pred : res)
  58                     reduce2(r, pos, target, pred, res.getForest());
  59     }
  60
  61     void reduce2(Pos r, int pos, GSS.Phase target, StateNode pred, Forest f) {
  62         Forest[] holder = r.holder;
  63         Forest old = pos >= holder.length ? null : holder[pos];
  64         if (pos < holder.length) holder[pos] = f;
  65         if (pos>0)  pred.reduce(r, pos-1, target, null);
  66         else {
  67             Input.Region region = pred.phase().getLocation().createRegion(target.getLocation());
  68             new Reduction(pred, r, r.rewrite(region), target);
  69         }
  70         if (pos < holder.length) holder[pos] = old;
  71     }
  72
  73     StateNode(GSS.Phase phase, Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
  74         this(phase, new ResultNode(f, reduction, pred), state, fromEmptyReduction);
  75     }
  76     StateNode(GSS.Phase phase, ResultNode pred, State state, boolean fromEmptyReduction) {
  77         super(phase, pred.phase());
  78         this.state = state;
  79         this.fromEmptyReduction = fromEmptyReduction;
  80         if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!");
  81         phase.hash.put(state, pred.phase(), this);
  82         addPred(pred);
  83         state.invokeEpsilonReductions(phase().token, this);
  84     }
  85
  86     // Add/Remove Successors/Predecessors //////////////////////////////////////////////////////////////////////////////
  87
  88     public void addPred(Forest f, Pos reduction, StateNode pred) {
  89         for(ResultNode r : predecessors)
  90             if (r.predecessorsContains(pred)) {
  91                 r.merge(f);
  92                 return;
  93             }
  94         addPred(new ResultNode(f, reduction, pred));
  95     }
  96     protected void addPred(ResultNode result) {
  97         super.addPred(result);
  98         if (!this.fromEmptyReduction)
  99             state.invokeReductions(phase().getToken(), this, result);
 100     }
 101 }