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