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.*;
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>();
21 public Cache(Union root, Topology top) {
26 // Follow //////////////////////////////////////////////////////////////////////////////
28 public Topology follow(Sequence s) { return follow.get(s); }
30 public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof) {
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)))
39 if (eof) followEof.add(seq);
41 for(Position p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
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);
49 if (!possiblyEpsilon(p.element())) {
50 followTopology = followTopology.empty();
53 followTopology = followTopology.union(first(p.element(), new HashSet<Sequence>()));
57 public Topology epsilonFollowSet(Union u) {
58 Topology ret = top.empty();
60 ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
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;
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);
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));
84 Sequence seq = (Sequence)e;
85 if (seen.contains(seq)) return top.empty();
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;
95 // Epsilon-Ness //////////////////////////////////////////////////////////////////////////////
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);
105 private boolean possiblyEpsilon(SequenceOrElement e, HashMap<SequenceOrElement,Boolean> hm) {
106 if (hm.get(e) != null) return hm.get(e);
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) {
113 Sequence s = (Sequence)e;
114 for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
115 ret &= possiblyEpsilon(p.element(), hm);
121 public boolean isRightNullable(Position p) {
122 if (p.isLast()) return true;
123 if (!possiblyEpsilon(p.element())) return false;
124 return isRightNullable(p.next());
127 public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
128 HashSet<Sequence> eq = new HashSet<Sequence>();
129 gatherNulledSubsequences(parent, eq);
130 return eq.contains(potentialSubSequence);
132 private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
133 if (eq.contains(seq)) return;
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;
144 // Position Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
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);
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);
174 public int comparePositions(Position position, Position rposition) {
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;
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;