1 | // Copyright (C) 2009 Google Inc. |
2 | // |
3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | // you may not use this file except in compliance with the License. |
5 | // You may obtain a copy of the License at |
6 | // |
7 | // http://www.apache.org/licenses/LICENSE-2.0 |
8 | // |
9 | // Unless required by applicable law or agreed to in writing, software |
10 | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | // See the License for the specific language governing permissions and |
13 | // limitations under the License. |
14 | |
15 | package com.google.caja.lexer; |
16 | |
17 | import com.google.caja.util.Lists; |
18 | import com.google.caja.util.Maps; |
19 | |
20 | import java.util.Iterator; |
21 | import java.util.List; |
22 | import java.util.Map; |
23 | |
24 | /** |
25 | * Does some simple constraint solving to assign reasonable position values |
26 | * to generated parse tree nodes. |
27 | * |
28 | * <h3>Usage</h3> |
29 | * <ol> |
30 | * <li>Create a {@code PositionInferer}, and implement the abstract methods. |
31 | * Pass to the constructor a file position from the same |
32 | * {@link InputSource source} as nodes with known file positions. |
33 | * <li>Add constraints by calling {@link #contains}, {@link #precedes} and |
34 | * friends. This class is meant to be agnostic to the classes used to |
35 | * implement the parse tree, but a node descriptor should typically be a |
36 | * {@code ParseTreeNode} or {@code org.w3c.dom.Node}. Object descriptors |
37 | * are compared by reference identity, not {@link Object#equals}. |
38 | * Any node descriptor not mentioned in a constraint will not have a |
39 | * position inferred. If there are contradictory constraints, then |
40 | * solve will behave as if some non-contradictory subset of constraints |
41 | * were added, though this subset is unpredictable. |
42 | * <li>Call {@link #solve} to solve constraints. This will cause a flurry of |
43 | * calls to {@link #setPosForNode}. Consider the file positions as advisory |
44 | * and ignore as you like. Ignoring a set will not affect the quality of |
45 | * later inferences. |
46 | * </ol> |
47 | * |
48 | * @author mikesamuel@gmail.com |
49 | */ |
50 | public abstract class PositionInferer { |
51 | private final List<Boundary> boundaries = Lists.newLinkedList(); |
52 | private final List<Relation> relations = Lists.newLinkedList(); |
53 | private final Map<Object, Region> boundsByNode |
54 | = Maps.newIdentityHashMap(); |
55 | /** |
56 | * Used to construct inferred file positions. |
57 | */ |
58 | private final SourceBreaks breaks; |
59 | |
60 | private static final int UNSPECIFIED_MAX = Integer.MAX_VALUE; |
61 | private static final int UNSPECIFIED_MIN |
62 | = FilePosition.startOfFile(InputSource.UNKNOWN).startCharInFile(); |
63 | |
64 | public PositionInferer(FilePosition spanningPos) { |
65 | this.breaks = spanningPos.getBreaks(); |
66 | } |
67 | |
68 | /** |
69 | * Adds a constraint that requires that contained's start and end falls |
70 | * (inclusively) between container's start and end. |
71 | * @param container a valid node descriptor. |
72 | * @param contained a valid node descriptor. |
73 | */ |
74 | public void contains(Object container, Object contained) { |
75 | Region aBounds = boundsForNode(container); |
76 | Region bBounds = boundsForNode(contained); |
77 | Relation left = new LessThanRelation(aBounds.start, bBounds.start); |
78 | Relation right = new LessThanRelation(bBounds.end, aBounds.end); |
79 | if (!left.isSatisfied()) { relations.add(left); } |
80 | if (!right.isSatisfied()) { relations.add(right); } |
81 | } |
82 | |
83 | /** |
84 | * Adds a constraint that requires that the end of before is at or before the |
85 | * start of after. |
86 | * @param before a valid node descriptor. |
87 | * @param after a valid node descriptor. |
88 | */ |
89 | public void precedes(Object before, Object after) { |
90 | Region beforeBounds = boundsForNode(before); |
91 | Region afterBounds = boundsForNode(after); |
92 | Relation r = new LessThanRelation(beforeBounds.end, afterBounds.start); |
93 | if (!r.isSatisfied()) { relations.add(r); } |
94 | } |
95 | |
96 | /** |
97 | * Adds a constraint that requires that the end of before is the same as the |
98 | * start of after. Similar to, but more constraining than {@link #precedes}. |
99 | * @param before a valid node descriptor. |
100 | * @param after a valid node descriptor. |
101 | */ |
102 | public void adjacent(Object before, Object after) { |
103 | Region beforeBounds = boundsForNode(before); |
104 | Region afterBounds = boundsForNode(after); |
105 | Relation r = new EqualRelation(beforeBounds.end, afterBounds.start); |
106 | if (!r.isSatisfied()) { relations.add(r); } |
107 | } |
108 | |
109 | /** |
110 | * Attempts to satisfy all constraints added thus far, and then invokes |
111 | * {@link #setPosForNode} for each node descriptor for which it could conclude |
112 | * a position. |
113 | */ |
114 | public void solve() { |
115 | boolean workDone; |
116 | List<Relation> toCheck = Lists.newLinkedList(); |
117 | do { |
118 | workDone = false; |
119 | for (Iterator<Relation> it = relations.iterator(); it.hasNext();) { |
120 | Relation r = it.next(); |
121 | if (!r.isSatisfied()) { |
122 | toCheck.add(r); |
123 | do { |
124 | Relation head = toCheck.remove(0); |
125 | if (head.satisfy(toCheck)) { workDone = true; } |
126 | } while (!toCheck.isEmpty()); |
127 | } |
128 | if (r.isSatisfied()) { it.remove(); } |
129 | } |
130 | } while (workDone); |
131 | |
132 | // Make guesses for any half-specified bounds. |
133 | for (Boundary b : boundaries) { |
134 | if (!b.isSpecified()) { |
135 | if (b.min > UNSPECIFIED_MIN) { |
136 | b.max = b.min; |
137 | } else if (b.max < UNSPECIFIED_MAX) { |
138 | b.min = b.max; |
139 | } |
140 | } |
141 | } |
142 | |
143 | // Propagate positions back to nodes. |
144 | for (Map.Entry<Object, Region> e : boundsByNode.entrySet()) { |
145 | Object node = e.getKey(); |
146 | Region r = e.getValue(); |
147 | if (r.start.isSpecified() && r.end.isSpecified()) { |
148 | this.setPosForNode(node, breaks.toFilePosition(r.start.min, r.end.max)); |
149 | } |
150 | } |
151 | } |
152 | |
153 | /** |
154 | * Returns the file position for the given node descriptor or an unknown |
155 | * position if the position needs to be inferred. |
156 | * |
157 | * @param o a node descriptor. |
158 | * @return non null. |
159 | * Should return a position whose {@link FilePosition#source source} is |
160 | * {@link InputSource#UNKNOWN unknown} if the node does not have accurate |
161 | * position info. |
162 | */ |
163 | protected abstract FilePosition getPosForNode(Object o); |
164 | |
165 | /** |
166 | * Informs the client that it has inferred a position for the given node. |
167 | * The client may ignore this, and probably should if the given node already |
168 | * has accurate position data from a {@link InputSource source} different than |
169 | * that of the position passed to the |
170 | * {@link #PositionInferer(FilePosition) constructor}. |
171 | * |
172 | * @param o a node descriptor. |
173 | * @param pos non null. |
174 | */ |
175 | protected abstract void setPosForNode(Object o, FilePosition pos); |
176 | |
177 | private Region boundsForNode(Object o) { |
178 | Region r = boundsByNode.get(o); |
179 | if (r == null) { |
180 | r = new Region(new Boundary(true, o), new Boundary(false, o)); |
181 | boundsByNode.put(o, r); |
182 | FilePosition pos = getPosForNode(o); |
183 | if (breaks.source().equals(pos.source())) { |
184 | r.start.min = r.start.max = pos.startCharInFile(); |
185 | r.end.min = r.end.max = pos.endCharInFile(); |
186 | } |
187 | boundaries.add(r.start); |
188 | boundaries.add(r.end); |
189 | Relation rel = new LessThanRelation(r.start, r.end); |
190 | if (!rel.isSatisfied()) { relations.add(rel); } |
191 | } |
192 | return r; |
193 | } |
194 | |
195 | /** An edge of a node descriptor's position. */ |
196 | private static class Boundary { |
197 | /** True if this is the start edge. */ |
198 | final boolean isStart; |
199 | /** A node descriptor. */ |
200 | final Object target; |
201 | /** |
202 | * Possibly unsatisfied relations that have this as one of their clauses. |
203 | */ |
204 | final List<Relation> relations = Lists.newLinkedList(); |
205 | /** Lower bound on the edge's position. */ |
206 | int min = UNSPECIFIED_MIN; |
207 | /** Upper bound on the edge's position. */ |
208 | int max = UNSPECIFIED_MAX; |
209 | |
210 | Boundary(boolean isStart, Object target) { |
211 | this.isStart = isStart; |
212 | this.target = target; |
213 | } |
214 | |
215 | boolean isSpecified() { return min == max; } |
216 | |
217 | /** |
218 | * Adds any unsatisfied relations to the given list, clearing out any |
219 | * satisfied relations. |
220 | */ |
221 | void schedule(List<? super Relation> out) { |
222 | for (Iterator<Relation> deps = relations.iterator(); deps.hasNext();) { |
223 | Relation dep = deps.next(); |
224 | if (dep.isSatisfied()) { |
225 | deps.remove(); |
226 | } else { |
227 | out.add(dep); |
228 | } |
229 | } |
230 | } |
231 | |
232 | /** For debugging. */ |
233 | @Override |
234 | public String toString() { |
235 | StringBuilder sb = new StringBuilder(); |
236 | String targetStr; |
237 | if (target != null) { |
238 | targetStr = target.toString().replace("\n", "\\n").replace("\r", "\\r"); |
239 | } else { |
240 | targetStr = "<null>"; |
241 | } |
242 | sb.append("(").append((isStart ? "start" : "end")).append(" ") |
243 | .append(targetStr); |
244 | if (min != UNSPECIFIED_MIN || max != UNSPECIFIED_MAX) { |
245 | if (min != UNSPECIFIED_MIN) { sb.append(" min=").append(min); } |
246 | if (max != UNSPECIFIED_MAX) { sb.append(" max=").append(max); } |
247 | } |
248 | sb.append(")"); |
249 | return sb.toString(); |
250 | } |
251 | } |
252 | |
253 | /** A start boundary and an end boundary. */ |
254 | private static class Region { |
255 | final Boundary start; |
256 | final Boundary end; |
257 | |
258 | Region(Boundary start, Boundary end) { |
259 | assert start.isStart && !end.isStart; |
260 | this.start = start; |
261 | this.end = end; |
262 | } |
263 | } |
264 | |
265 | /** |
266 | * A relationship between two boundaries that constrains the positions of the |
267 | * set of boundaries. |
268 | */ |
269 | private static abstract class Relation { |
270 | final Boundary a; |
271 | final Boundary b; |
272 | |
273 | Relation(Boundary a, Boundary b) { |
274 | this.a = a; |
275 | this.b = b; |
276 | if (!(a.isSpecified() && b.isSpecified())) { |
277 | a.relations.add(this); |
278 | b.relations.add(this); |
279 | } |
280 | } |
281 | |
282 | /** |
283 | * True if the upper and lower bounds of the positions of a and b are |
284 | * such that no choice of actual positions within those bounds would make |
285 | * this relation inconsistent. |
286 | */ |
287 | abstract boolean isSatisfied(); |
288 | |
289 | /** |
290 | * Attempts to narrow the bounds on this relation's boundaries. |
291 | * @param toCheck a list to append any relations that should be rechecked |
292 | * in light of changes to this relation's boundaries. |
293 | * @return true if it managed to narrow bounds. |
294 | */ |
295 | abstract boolean satisfy(List<? super Relation> toCheck); |
296 | } |
297 | |
298 | /** |
299 | * A relation between a boundary that appears at or before another boundary. |
300 | */ |
301 | private static class LessThanRelation extends Relation { |
302 | LessThanRelation(Boundary lesser, Boundary greater) { |
303 | super(lesser, greater); |
304 | } |
305 | |
306 | @Override |
307 | boolean satisfy(List<? super Relation> toCheck) { |
308 | // Consider six cases for (A <= B): |
309 | // 1. A |----| Inconsistent. |
310 | // B |----| |
311 | |
312 | // 2. A |----| Consistent and satisfied. |
313 | // B |----| |
314 | |
315 | // 3. A |----| Consistent but cannot narrow. |
316 | // B |----| |
317 | |
318 | // 4. A |----| => |-| Narrow lesser's max |
319 | // B |----| |-| and greater's min. |
320 | |
321 | // 5. A |-----------| => |--------| Narrow lesser's max. |
322 | // B |-----| |-----| |
323 | |
324 | // 6. A |-----| => |-----| Narrow greater's min. |
325 | // B |-----------| |--------| |
326 | |
327 | boolean narrowed = false; |
328 | if (a.min <= b.max) { |
329 | // Eliminated case 1 and a special case of case 3 where both are equal. |
330 | if (a.min > b.min) { // Cases 4 and 6 above. |
331 | int newMin = Math.min(a.min, b.max); |
332 | if (b.min != newMin) { |
333 | b.min = newMin; |
334 | b.schedule(toCheck); |
335 | narrowed = true; |
336 | } |
337 | } |
338 | if (a.max > b.max) { // Cases 4 and 5 above |
339 | int newMax = Math.max(b.max, a.min); |
340 | if (a.max != newMax) { |
341 | a.max = newMax; |
342 | a.schedule(toCheck); |
343 | narrowed = true; |
344 | } |
345 | } |
346 | } |
347 | return narrowed; |
348 | } |
349 | |
350 | @Override |
351 | boolean isSatisfied() { |
352 | return (a.isSpecified() && b.isSpecified()) || a.max <= b.min; |
353 | } |
354 | |
355 | @Override |
356 | public String toString() { |
357 | return "(" + a + " <= " + b + ")"; |
358 | } |
359 | } |
360 | |
361 | /** |
362 | * A relation between two boundaries that should be at the same actual |
363 | * position. |
364 | */ |
365 | private static class EqualRelation extends Relation { |
366 | EqualRelation(Boundary a, Boundary b) { super(a, b); } |
367 | |
368 | @Override |
369 | boolean satisfy(List<? super Relation> toCheck) { |
370 | int newAMin = Math.min(a.max, Math.max(a.min, b.min)); |
371 | int newAMax = Math.max(a.min, Math.min(a.max, b.max)); |
372 | int newBMin = Math.min(b.max, Math.max(a.min, b.min)); |
373 | int newBMax = Math.max(b.min, Math.min(a.max, b.max)); |
374 | boolean narrowed = false; |
375 | if (a.min != newAMin || a.max != newAMax) { |
376 | a.min = newAMin; |
377 | a.max = newAMax; |
378 | a.schedule(toCheck); |
379 | narrowed = true; |
380 | } |
381 | if (b.min != newBMin || b.max != newBMax) { |
382 | b.min = newBMin; |
383 | b.max = newBMax; |
384 | b.schedule(toCheck); |
385 | narrowed = true; |
386 | } |
387 | return narrowed; |
388 | } |
389 | |
390 | @Override |
391 | boolean isSatisfied() { |
392 | return (a.isSpecified() && b.isSpecified()) |
393 | || (a.min == b.min && a.max == b.max); |
394 | } |
395 | |
396 | @Override |
397 | public String toString() { |
398 | return "(" + a + " == " + b + ")"; |
399 | } |
400 | } |
401 | } |