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