X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FCache.java;fp=src%2Fedu%2Fberkeley%2Fsbp%2FCache.java;h=454f584d4f3c32b1c8def991f064a6537f1dd1d2;hp=0000000000000000000000000000000000000000;hb=a82ff8c049dd265ecf1d115d60e1be8ecb81a4c1;hpb=01f461b42d1ea2cdfcbc1750e00a2fd8338146ba

diff --git a/src/edu/berkeley/sbp/Cache.java b/src/edu/berkeley/sbp/Cache.java
new file mode 100644
index 0000000..454f584
--- /dev/null
+++ b/src/edu/berkeley/sbp/Cache.java
@@ -0,0 +1,190 @@
+// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
+
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.Sequence.Position;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+class Cache {
+    private Union root;
+    private Topology top;
+
+    public HashMap<Sequence, Topology> follow = new HashMap<Sequence, Topology>();
+    public HashSet<Sequence> followEof = new HashSet<Sequence>();
+    public final HashMap<SequenceOrElement,Boolean> possiblyEpsilon = new HashMap<SequenceOrElement,Boolean>();
+    public HashSet<SequenceOrElement> all = new HashSet<SequenceOrElement>();
+
+    public Cache(Union root, Topology top) {
+        this.root = root;
+        this.top = top;
+    }
+
+    // Follow //////////////////////////////////////////////////////////////////////////////
+
+    public Topology follow(Sequence s) { return follow.get(s); }
+
+    public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof)  {
+        all.add(seq);
+        Topology old = follow.get(seq);
+        if (old==null) old = followTopology;
+        else           old = old.union(followTopology);
+        if (seq.follow != null) old = old.intersect(seq.follow.getTokenTopology());
+        if (follow.get(seq) != null && follow.get(seq).containsAll(old) && (!eof || followEof.contains(seq)))
+            return;
+        follow.put(seq, old);
+        if (eof) followEof.add(seq);
+
+        for(Position p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
+            all.add(p.element());
+            if (p.element() instanceof Union)
+                for(Sequence s2 : ((Union)p.element())) {
+                    buildFollowSet(s2, followTopology, eof);
+                    for(Sequence ss : s2.needs()) buildFollowSet(ss, followTopology, eof);
+                    for(Sequence ss : s2.hates()) buildFollowSet(ss, followTopology, eof);
+                }
+            if (!possiblyEpsilon(p.element())) {
+                followTopology = followTopology.empty();
+                eof = false;
+            }
+            followTopology = followTopology.union(first(p.element(), new HashSet<Sequence>()));
+        }
+    }
+
+    public Topology epsilonFollowSet(Union u) {
+        Topology ret = top.empty();
+        for(Sequence s : u)
+            ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
+        return ret;
+    }
+    public Topology epsilonFollowSet(Sequence seq, HashSet<Sequence> seen) {
+        Topology ret = seq.follow==null ? top.empty().complement() : seq.follow.getTokenTopology();
+        if (seen.contains(seq)) return ret;
+        seen.add(seq);
+        for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
+            if (!(p.element() instanceof Union)) continue;
+            Topology t = top.empty();
+            for(Sequence s : ((Union)p.element()))
+                if (possiblyEpsilon(s))
+                    t = t.union(epsilonFollowSet(s, seen));
+            ret = ret.intersect(t);
+        }
+        return ret;
+    }
+
+    public Topology first(SequenceOrElement e, HashSet<Sequence> seen) {
+        if (e instanceof Atom) return ((Atom)e).getTokenTopology();
+        Topology ret = top.empty();
+        if (e instanceof Union) {
+            for(Sequence s : ((Union)e)) ret = ret.union(first(s, seen));
+        } else {
+            Sequence seq = (Sequence)e;
+            if (seen.contains(seq)) return top.empty();
+            seen.add(seq);
+            for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
+                ret = ret.union(first(p.element(), seen));
+                if (!possiblyEpsilon(p.element())) break;
+            }
+        }
+        return ret;
+    }
+
+    // Epsilon-Ness //////////////////////////////////////////////////////////////////////////////
+
+    final boolean possiblyEpsilon(SequenceOrElement e) {
+        Boolean ret = possiblyEpsilon.get(e);
+        if (ret != null) return ret.booleanValue();
+        ret = possiblyEpsilon(e, new HashMap<SequenceOrElement,Boolean>());
+        possiblyEpsilon.put(e, ret);
+        return ret;
+    }
+
+    private boolean possiblyEpsilon(SequenceOrElement e, HashMap<SequenceOrElement,Boolean> hm) {
+        if (hm.get(e) != null) return hm.get(e);
+        hm.put(e, false);
+        boolean ret = false;
+        if      (e instanceof Atom)     ret = false;
+        else if (e instanceof Union)    { for(Sequence s : (Union)e) ret |= possiblyEpsilon(s, hm); }
+        else if (e instanceof Sequence) {
+            ret = true;
+            Sequence s = (Sequence)e;
+            for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
+                ret &= possiblyEpsilon(p.element(), hm);
+        }
+        hm.put(e, ret);
+        return ret;
+    }
+
+    public boolean isRightNullable(Position p) {
+        if (p.isLast()) return true;
+        if (!possiblyEpsilon(p.element())) return false;
+        return isRightNullable(p.next());
+    }
+
+    public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
+        HashSet<Sequence> eq = new HashSet<Sequence>();
+        gatherNulledSubsequences(parent, eq);
+        return eq.contains(potentialSubSequence);
+    }
+    private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
+        if (eq.contains(seq)) return;
+        eq.add(seq);
+        Position p = seq.firstp();
+        for(; !p.isLast(); p = p.next()) {
+            if (!p.isLast() && isRightNullable(p.next()) && p.element() instanceof Union)
+                for(Sequence s : ((Union)p.element()))
+                    gatherNulledSubsequences(s, eq);
+            if (!possiblyEpsilon(p.element())) break;
+        }
+    }
+
+    // Position Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
+
+    public boolean canKill(Position mep, Position himp) {
+        if (!isRightNullable(mep))  return false;
+        if (!isRightNullable(himp)) return false;
+        Sequence me  = mep.owner();
+        Sequence him = himp.owner();
+        Boolean b = me.canKill.get(him);
+        if (b!=null) return b;
+        for(Sequence killer : him.hates())
+            if (isNulledSubsequence(killer, me))
+                { me.canKill.put(him, true); return true; }
+        me.canKill.put(him, false);
+        return false;
+    }
+
+    public boolean canNeed(Position mep, Position himp) {
+        if (!isRightNullable(mep))  return false;
+        if (!isRightNullable(himp)) return false;
+        Sequence me  = mep.owner();
+        Sequence him = himp.owner();
+        Boolean b = me.canNeed.get(him);
+        if (b!=null) return b;
+        for(Sequence needer : him.needs())
+            if (isNulledSubsequence(needer, me))
+                { me.canNeed.put(him, true); return true; }
+        me.canNeed.put(him, false);
+        return false;
+    }
+
+    public int comparePositions(Position position, Position rposition) {
+        int ret = 0;
+        if (canKill(position, rposition) && canKill(rposition, position)) throw new Error();
+        if      (canKill(position,  rposition))  ret = -1;
+        else if (canKill(rposition, position))   ret =  1;
+        else if (canNeed(position,  rposition))  ret = -1;
+        else if (canNeed(rposition, position))   ret =  1;
+        /*
+        else if (isNulledSubsequence(position.owner(),  rposition.owner()) && isNulledSubsequence(rposition.owner(),  position.owner())) ret = 0;
+        else if (isNulledSubsequence(position.owner(),  rposition.owner())) ret =  1;
+        else if (isNulledSubsequence(rposition.owner(), position.owner()))  ret = -1;
+        */
+        return ret;
+    }
+
+}
+