1
2
3
4 package net.sf.bddbddb.ir;
5
6 import java.util.ArrayList;
7 import java.util.HashMap;
8 import java.util.Iterator;
9 import java.util.List;
10 import java.util.Map;
11 import java.io.BufferedWriter;
12 import java.io.IOException;
13 import jwutil.collections.LinearMap;
14 import jwutil.collections.Pair;
15 import jwutil.collections.UnionFindWithConstraints;
16 import jwutil.util.Assert;
17 import net.sf.bddbddb.Attribute;
18 import net.sf.bddbddb.BDDRelation;
19 import net.sf.bddbddb.BDDSolver;
20 import net.sf.bddbddb.Domain;
21 import net.sf.bddbddb.Relation;
22 import net.sf.bddbddb.Solver;
23 import net.sf.bddbddb.dataflow.PartialOrder.Constraints;
24 import net.sf.bddbddb.ir.lowlevel.Replace;
25 import net.sf.javabdd.BDDDomain;
26
27 /***
28 * Performs domain assignment based on a union-find data structure.
29 * The general model is to introduce constraints in their order of importance.
30 * If a constraint cannot be satisfied, a replace operation is introduced at
31 * that point.
32 *
33 * This domain assignment works by keeping track of attributes that are the
34 * same in a union-find data structure, and keeping a set of not-equal
35 * constraints that must be obeyed. When a new constraint (equal or not-equal)
36 * is considered that does not obey the current constraints, it is not added
37 * and a replace operation is generated at that point.
38 *
39 * @author John Whaley
40 * @version $Id: UFDomainAssignment.java 622 2005-08-30 11:06:31Z joewhaley $
41 */
42 public class UFDomainAssignment extends DomainAssignment {
43
44 UnionFindWithConstraints uf;
45 Map physicalDomains;
46
47 public UFDomainAssignment(Solver s){
48 super(s);
49 uf = new UnionFindWithConstraints(65536);
50 this.initialize();
51 }
52 /***
53 * @param s
54 */
55 protected UFDomainAssignment(Solver s, Constraints[] constraintMap) {
56 super(s, constraintMap);
57 uf = new UnionFindWithConstraints(65536);
58 this.initialize();
59 }
60
61 void initialize() {
62 super.initialize();
63
64
65 BDDSolver s = (BDDSolver) solver;
66 for (Iterator i = s.getBDDDomains().keySet().iterator(); i.hasNext();) {
67 Domain d = (Domain) i.next();
68 for (Iterator j = s.getBDDDomains(d).iterator(); j.hasNext();) {
69 BDDDomain b1 = (BDDDomain) j.next();
70 for (Iterator k = s.getBDDDomains(d).iterator(); k.hasNext();) {
71 BDDDomain b2 = (BDDDomain) k.next();
72 if (b1 == b2) continue;
73 forceNotEqual(b1, b2);
74 }
75 }
76 }
77 }
78
79
80
81
82 public void doAssignment() {
83 for (Iterator j = inserted.iterator(); j.hasNext(); ) {
84 Replace op = (Replace) j.next();
85 if (TRACE) solver.out.println("Visiting inserted operation: "+op);
86 Relation r0 = op.getRelationDest();
87 Relation r1 = op.getSrc();
88 for (Iterator i = r1.getAttributes().iterator(); i.hasNext(); ) {
89 Attribute a1 = (Attribute) i.next();
90 if (r0.getAttributes().contains(a1)) {
91 if (!forceEqual(r1, a1, r0, a1, true)) {
92
93 if (TRACE) solver.out.println("Domain "+a1+" cannot be matched.");
94 } else {
95 if (TRACE) solver.out.println("Domain "+a1+" matched.");
96 }
97 }
98 }
99 }
100
101 BDDSolver s = (BDDSolver) solver;
102 physicalDomains = new HashMap();
103 for (Iterator i = s.getBDDDomains().keySet().iterator(); i.hasNext();) {
104 Domain d = (Domain) i.next();
105 for (Iterator j = s.getBDDDomains(d).iterator(); j.hasNext();) {
106 BDDDomain b = (BDDDomain) j.next();
107 Object rep = uf.find(b);
108 physicalDomains.put(rep, b);
109 if (TRACE) solver.out.println("Domain " + b + " rep: " + rep);
110 }
111 }
112 for (int i = 0; i < s.getNumberOfRelations(); ++i) {
113 BDDRelation r = (BDDRelation) s.getRelation(i);
114 if(TRACE) solver.out.print(i+": "+r+" ");
115 List domAssign = new ArrayList(r.getAttributes().size());
116 for (Iterator j = r.getAttributes().iterator(); j.hasNext();) {
117 Attribute a = (Attribute) j.next();
118 Pair p = new Pair(r, a);
119 Object assignment = uf.find(p);
120 if (TRACE) solver.out.println(p + " rep = " + assignment);
121 BDDDomain b = (BDDDomain) physicalDomains.get(assignment);
122 if (b != null) {
123
124 if (TRACE) solver.out.println(p + " already bound to " + b);
125 } else {
126
127 b = chooseBDDDomain(r, a);
128 uf.union(p, b);
129 if (TRACE) solver.out.println(p + ": binding to " + b);
130 Object rep = uf.find(b);
131 physicalDomains.put(rep, b);
132 if (TRACE) solver.out.println("Domain " + b + " rep: " + rep);
133 }
134 domAssign.add(b);
135 }
136 if (TRACE) solver.out.println("Relation " + r + " domains: " + domAssign);
137 if(TRACE) solver.out.print(domAssign+" \r");
138 r.setDomainAssignment(domAssign);
139 }
140 }
141
142
143 public void setVariableOrdering(){
144 ((BDDSolver) solver).setVariableOrdering();
145 }
146
147
148 /***
149 * Choose a BDD domain to allocate for the given attribute in the given relation.
150 * Allocates a new BDD domain if none of the existing ones would be legal.
151 *
152 * @param r relation
153 * @param a attribute
154 * @return BDD domain
155 */
156 BDDDomain chooseBDDDomain(BDDRelation r, Attribute a) {
157 BDDSolver s = (BDDSolver) solver;
158 Domain d = a.getDomain();
159 Pair p = new Pair(r, a);
160 List legal = new ArrayList();
161 for (Iterator i = s.getBDDDomains(d).iterator(); i.hasNext();) {
162 BDDDomain b = (BDDDomain) i.next();
163 if (TRACE) solver.out.println("assign " + p + " = " + b);
164 if (wouldBeLegal(p, b)) {
165 legal.add(b);
166 }
167 }
168 if (legal.isEmpty()) {
169 BDDDomain b = s.allocateBDDDomain(d);
170 if (TRACE) solver.out.println("Allocating new domain " + b);
171 return b;
172 }
173 if (legal.size() == 1) {
174 return (BDDDomain) legal.get(0);
175 }
176
177 if (TRACE) solver.out.println("Legal bindings for " + p +": "+legal);
178 return (BDDDomain) legal.get(0);
179 }
180
181
182
183
184
185
186 void forceDifferent(Relation r) {
187 if (TRACE) solver.out.println("Forcing attributes to be different for "+r);
188 for (Iterator j = r.getAttributes().iterator(); j.hasNext();) {
189 Attribute a1 = (Attribute) j.next();
190 Pair p1 = new Pair(r, a1);
191 Iterator k = r.getAttributes().iterator();
192 while (k.next() != a1) ;
193 while (k.hasNext()) {
194 Attribute a2 = (Attribute) k.next();
195 if (a1 == a2) continue;
196 if (a1.getDomain() != a2.getDomain()) continue;
197 Pair p2 = new Pair(r, a2);
198 if (!p1.equals(uf.find(p1))) {
199 solver.out.println("Warning: "+p1+" != "+uf.find(p1));
200 p1 = (Pair) uf.find(p1);
201 }
202 if (!p2.equals(uf.find(p2))) {
203 solver.out.println("Warning: "+p2+" != "+uf.find(p2));
204 p2 = (Pair) uf.find(p2);
205 }
206 boolean b = uf.disjoint(p1, p2);
207 Assert._assert(b);
208 }
209 }
210 }
211
212 boolean forceNotEqual(Object a1, Object a2) {
213 if (TRACE) solver.out.println("Forcing " + a1 + " != " + a2);
214 boolean b = uf.disjoint(a1, a2);
215 if (!b) {
216 if (TRACE) solver.out.println("Cannot force, " + a1 + " != " + a2);
217 }
218 return b;
219 }
220
221 boolean wouldBeLegal(Object a1, Object a2) {
222 return uf.union(a1, a2, false);
223 }
224
225 boolean forceEqual(Object a1, Object a2) {
226 if (TRACE) solver.out.println("Forcing " + a1 + " = " + a2);
227 boolean b = uf.union(a1, a2);
228 if (!b) {
229 if (TRACE) solver.out.println("Cannot force, " + a1 + " = " + a2);
230 }
231 return b;
232 }
233
234
235
236
237
238
239
240 boolean forceEqual(Relation r1, Attribute a1, int k) {
241 Domain dom = a1.getDomain();
242 BDDDomain d = ((BDDSolver) solver).getBDDDomain(dom, k);
243 return forceEqual(new Pair(r1, a1), d);
244 }
245
246
247
248
249
250
251
252
253 boolean forceEqual(Relation r1, Attribute a1, Relation r2, Attribute a2, boolean equal) {
254 Pair p1 = new Pair(r1, a1);
255 Pair p2 = new Pair(r2, a2);
256 if (equal) {
257 return forceEqual(p1, p2);
258 } else {
259 return forceNotEqual(p1, p2);
260 }
261 }
262
263 boolean forceBefore(Object o1, Object o2){return true;}
264 boolean forceBefore(Relation r1, Attribute a1, Relation r2, Attribute a2){return true;}
265 boolean forceInterleaved(Object o1, Object o2){ return true; }
266 boolean forceInterleaved(Relation r1, Attribute a1, Relation r2, Attribute a2){ return true; }
267
268
269
270
271
272 Relation allocNewRelation(Relation old_r) {
273 Relation r = old_r.copy();
274 Map m = new LinearMap();
275 for (Iterator j = r.getAttributes().iterator(); j.hasNext();) {
276 Attribute a = (Attribute) j.next();
277 domainToAttributes.add(a.getDomain(), a);
278 }
279 forceDifferent(r);
280 r.initialize();
281 return r;
282 }
283
284
285
286
287 public void saveDomainAssignment(BufferedWriter out) throws IOException {
288 BDDSolver s = (BDDSolver) solver;
289 for (int i = 0; i < s.getNumberOfRelations(); ++i) {
290 BDDRelation r = (BDDRelation) s.getRelation(i);
291 StringBuffer sb = new StringBuffer();
292 for (Iterator j = r.getAttributes().iterator(); j.hasNext();) {
293 Attribute a = (Attribute) j.next();
294 Pair p = new Pair(r, a);
295 Object assignment = uf.find(p);
296 BDDDomain b = (BDDDomain) physicalDomains.get(assignment);
297 if (b != null) {
298 out.write(r+" "+a+" = "+b+"\n");
299 } else {
300 solver.out.println(p+" not assigned a domain!");
301 }
302 }
303 }
304 }
305
306 }