1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.*;
5 import edu.berkeley.sbp.util.*;
6 import edu.berkeley.sbp.Sequence.Position;
9 import java.lang.reflect.*;
10 import java.lang.ref.*;
12 abstract class Cache<Token> {
13 protected Union rootUnion;
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>();
20 abstract Topology<Token> emptyTopology();
21 public Cache(Union root) {
22 this.rootUnion = root;
24 for(Sequence s : root)
25 buildFollowSet(s, emptyTopology(), true);
28 // Follow //////////////////////////////////////////////////////////////////////////////
30 public Topology follow(Sequence s) { return follow.get(s); }
32 public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof) {
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)))
41 if (eof) followEof.add(seq);
43 for(Position p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
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);
51 if (!possiblyEpsilon(p.element())) {
52 followTopology = followTopology.empty();
55 followTopology = followTopology.union(first(p.element(), new HashSet<Sequence>()));
59 public Topology epsilonFollowSet(Union u) {
60 Topology ret = emptyTopology();
62 ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
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;
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);
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));
86 Sequence seq = (Sequence)e;
87 if (seen.contains(seq)) return emptyTopology();
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;
97 // Epsilon-Ness //////////////////////////////////////////////////////////////////////////////
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);
107 private boolean possiblyEpsilon(SequenceOrElement e, HashMap<SequenceOrElement,Boolean> hm) {
108 if (hm.get(e) != null) return hm.get(e);
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) {
115 Sequence s = (Sequence)e;
116 for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
117 ret &= possiblyEpsilon(p.element(), hm);
123 public boolean isRightNullable(Position p) {
124 if (p.isLast()) return true;
125 if (!possiblyEpsilon(p.element())) return false;
126 return isRightNullable(p.next());
129 public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
130 HashSet<Sequence> eq = new HashSet<Sequence>();
131 gatherNulledSubsequences(parent, eq);
132 return eq.contains(potentialSubSequence);
134 private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
135 if (eq.contains(seq)) return;
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;
146 // Position Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
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);
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);
176 public int comparePositions(Position position, Position rposition) {
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;
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;