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