src/edu/berkeley/sbp/Cache.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.Sequence.Position;
   7 import java.io.*;
   8 import java.util.*;
   9 import java.lang.reflect.*;
  10 import java.lang.ref.*;
  11
  12 class Cache {
  13     private Union root;
  14     private Topology top;
  15
  16     public HashMap<Sequence, Topology> follow = new HashMap<Sequence, Topology>();
  17     public HashSet<Sequence> followEof = new HashSet<Sequence>();
  18     public final HashMap<SequenceOrElement,Boolean> possiblyEpsilon = new HashMap<SequenceOrElement,Boolean>();
  19     public HashSet<SequenceOrElement> all = new HashSet<SequenceOrElement>();
  20
  21     public Cache(Union root, Topology top) {
  22         this.root = root;
  23         this.top = top;
  24     }
  25
  26     // Follow //////////////////////////////////////////////////////////////////////////////
  27
  28     public Topology follow(Sequence s) { return follow.get(s); }
  29
  30     public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof)  {
  31         all.add(seq);
  32         Topology old = follow.get(seq);
  33         if (old==null) old = followTopology;
  34         else           old = old.union(followTopology);
  35         if (seq.follow != null) old = old.intersect(seq.follow.getTokenTopology());
  36         if (follow.get(seq) != null && follow.get(seq).containsAll(old) && (!eof || followEof.contains(seq)))
  37             return;
  38         follow.put(seq, old);
  39         if (eof) followEof.add(seq);
  40
  41         for(Position p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
  42             all.add(p.element());
  43             if (p.element() instanceof Union)
  44                 for(Sequence s2 : ((Union)p.element())) {
  45                     buildFollowSet(s2, followTopology, eof);
  46                     for(Sequence ss : s2.needs()) buildFollowSet(ss, followTopology, eof);
  47                     for(Sequence ss : s2.hates()) buildFollowSet(ss, followTopology, eof);
  48                 }
  49             if (!possiblyEpsilon(p.element())) {
  50                 followTopology = followTopology.empty();
  51                 eof = false;
  52             }
  53             followTopology = followTopology.union(first(p.element(), new HashSet<Sequence>()));
  54         }
  55     }
  56
  57     public Topology epsilonFollowSet(Union u) {
  58         Topology ret = top.empty();
  59         for(Sequence s : u)
  60             ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
  61         return ret;
  62     }
  63     public Topology epsilonFollowSet(Sequence seq, HashSet<Sequence> seen) {
  64         Topology ret = seq.follow==null ? top.empty().complement() : seq.follow.getTokenTopology();
  65         if (seen.contains(seq)) return ret;
  66         seen.add(seq);
  67         for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
  68             if (!(p.element() instanceof Union)) continue;
  69             Topology t = top.empty();
  70             for(Sequence s : ((Union)p.element()))
  71                 if (possiblyEpsilon(s))
  72                     t = t.union(epsilonFollowSet(s, seen));
  73             ret = ret.intersect(t);
  74         }
  75         return ret;
  76     }
  77
  78     public Topology first(SequenceOrElement e, HashSet<Sequence> seen) {
  79         if (e instanceof Atom) return ((Atom)e).getTokenTopology();
  80         Topology ret = top.empty();
  81         if (e instanceof Union) {
  82             for(Sequence s : ((Union)e)) ret = ret.union(first(s, seen));
  83         } else {
  84             Sequence seq = (Sequence)e;
  85             if (seen.contains(seq)) return top.empty();
  86             seen.add(seq);
  87             for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
  88                 ret = ret.union(first(p.element(), seen));
  89                 if (!possiblyEpsilon(p.element())) break;
  90             }
  91         }
  92         return ret;
  93     }
  94
  95     // Epsilon-Ness //////////////////////////////////////////////////////////////////////////////
  96
  97     final boolean possiblyEpsilon(SequenceOrElement e) {
  98         Boolean ret = possiblyEpsilon.get(e);
  99         if (ret != null) return ret.booleanValue();
 100         ret = possiblyEpsilon(e, new HashMap<SequenceOrElement,Boolean>());
 101         possiblyEpsilon.put(e, ret);
 102         return ret;
 103     }
 104
 105     private boolean possiblyEpsilon(SequenceOrElement e, HashMap<SequenceOrElement,Boolean> hm) {
 106         if (hm.get(e) != null) return hm.get(e);
 107         hm.put(e, false);
 108         boolean ret = false;
 109         if      (e instanceof Atom)     ret = false;
 110         else if (e instanceof Union)    { for(Sequence s : (Union)e) ret |= possiblyEpsilon(s, hm); }
 111         else if (e instanceof Sequence) {
 112             ret = true;
 113             Sequence s = (Sequence)e;
 114             for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
 115                 ret &= possiblyEpsilon(p.element(), hm);
 116         }
 117         hm.put(e, ret);
 118         return ret;
 119     }
 120
 121     public boolean isRightNullable(Position p) {
 122         if (p.isLast()) return true;
 123         if (!possiblyEpsilon(p.element())) return false;
 124         return isRightNullable(p.next());
 125     }
 126
 127     public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
 128         HashSet<Sequence> eq = new HashSet<Sequence>();
 129         gatherNulledSubsequences(parent, eq);
 130         return eq.contains(potentialSubSequence);
 131     }
 132     private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
 133         if (eq.contains(seq)) return;
 134         eq.add(seq);
 135         Position p = seq.firstp();
 136         for(; !p.isLast(); p = p.next()) {
 137             if (!p.isLast() && isRightNullable(p.next()) && p.element() instanceof Union)
 138                 for(Sequence s : ((Union)p.element()))
 139                     gatherNulledSubsequences(s, eq);
 140             if (!possiblyEpsilon(p.element())) break;
 141         }
 142     }
 143
 144     // Position Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
 145
 146     public boolean canKill(Position mep, Position himp) {
 147         if (!isRightNullable(mep))  return false;
 148         if (!isRightNullable(himp)) return false;
 149         Sequence me  = mep.owner();
 150         Sequence him = himp.owner();
 151         Boolean b = me.canKill.get(him);
 152         if (b!=null) return b;
 153         for(Sequence killer : him.hates())
 154             if (isNulledSubsequence(killer, me))
 155                 { me.canKill.put(him, true); return true; }
 156         me.canKill.put(him, false);
 157         return false;
 158     }
 159
 160     public boolean canNeed(Position mep, Position himp) {
 161         if (!isRightNullable(mep))  return false;
 162         if (!isRightNullable(himp)) return false;
 163         Sequence me  = mep.owner();
 164         Sequence him = himp.owner();
 165         Boolean b = me.canNeed.get(him);
 166         if (b!=null) return b;
 167         for(Sequence needer : him.needs())
 168             if (isNulledSubsequence(needer, me))
 169                 { me.canNeed.put(him, true); return true; }
 170         me.canNeed.put(him, false);
 171         return false;
 172     }
 173
 174     public int comparePositions(Position position, Position rposition) {
 175         int ret = 0;
 176         if (canKill(position, rposition) && canKill(rposition, position)) throw new Error();
 177         if      (canKill(position,  rposition))  ret = -1;
 178         else if (canKill(rposition, position))   ret =  1;
 179         else if (canNeed(position,  rposition))  ret = -1;
 180         else if (canNeed(rposition, position))   ret =  1;
 181         /*
 182         else if (isNulledSubsequence(position.owner(),  rposition.owner()) && isNulledSubsequence(rposition.owner(),  position.owner())) ret = 0;
 183         else if (isNulledSubsequence(position.owner(),  rposition.owner())) ret =  1;
 184         else if (isNulledSubsequence(rposition.owner(), position.owner()))  ret = -1;
 185         */
 186         return ret;
 187     }
 188
 189 }
 190