EMMA Coverage Report (generated Mon Nov 01 16:48:29 PDT 2010)
[all classes][com.google.caja.lexer]

COVERAGE SUMMARY FOR SOURCE FILE [PositionInferer.java]

nameclass, %method, %block, %line, %
PositionInferer.java100% (6/6)87%  (20/23)85%  (642/754)91%  (126.5/139)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class PositionInferer100% (1/1)100% (8/8)100% (318/318)100% (63/63)
<static initializer> 100% (1/1)100% (5/5)100% (1/1)
PositionInferer (FilePosition): void 100% (1/1)100% (16/16)100% (6/6)
access$000 (): int 100% (1/1)100% (2/2)100% (1/1)
adjacent (Object, Object): void 100% (1/1)100% (25/25)100% (5/5)
boundsForNode (Object): PositionInferer$Region 100% (1/1)100% (87/87)100% (13/13)
contains (Object, Object): void 100% (1/1)100% (41/41)100% (7/7)
precedes (Object, Object): void 100% (1/1)100% (25/25)100% (5/5)
solve (): void 100% (1/1)100% (117/117)100% (25/25)
     
class PositionInferer$Boundary100% (1/1)75%  (3/4)41%  (50/122)60%  (15/25)
PositionInferer$Boundary (boolean, Object): void 100% (1/1)100% (18/18)100% (7/7)
isSpecified (): boolean 100% (1/1)100% (9/9)100% (1/1)
schedule (List): void 100% (1/1)100% (23/23)100% (7/7)
toString (): String 0%   (0/1)0%   (0/72)0%   (0/10)
     
class PositionInferer$EqualRelation100% (1/1)75%  (3/4)89%  (131/148)95%  (18/19)
PositionInferer$EqualRelation (PositionInferer$Boundary, PositionInferer$Boun... 100% (1/1)100% (5/5)100% (1/1)
isSatisfied (): boolean 100% (1/1)100% (26/26)100% (1/1)
satisfy (List): boolean 100% (1/1)100% (100/100)100% (16/16)
toString (): String 0%   (0/1)0%   (0/17)0%   (0/1)
     
class PositionInferer$LessThanRelation100% (1/1)75%  (3/4)85%  (95/112)95%  (18/19)
PositionInferer$LessThanRelation (PositionInferer$Boundary, PositionInferer$B... 100% (1/1)100% (5/5)100% (2/2)
isSatisfied (): boolean 100% (1/1)100% (19/19)100% (1/1)
satisfy (List): boolean 100% (1/1)100% (71/71)100% (15/15)
toString (): String 0%   (0/1)0%   (0/17)0%   (0/1)
     
class PositionInferer$Region100% (1/1)100% (2/2)79%  (23/29)91%  (5.5/6)
<static initializer> 100% (1/1)75%  (6/8)75%  (0.8/1)
PositionInferer$Region (PositionInferer$Boundary, PositionInferer$Boundary): ... 100% (1/1)81%  (17/21)94%  (4.7/5)
     
class PositionInferer$Relation100% (1/1)100% (1/1)100% (25/25)100% (7/7)
PositionInferer$Relation (PositionInferer$Boundary, PositionInferer$Boundary)... 100% (1/1)100% (25/25)100% (7/7)

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 
15package com.google.caja.lexer;
16 
17import com.google.caja.util.Lists;
18import com.google.caja.util.Maps;
19 
20import java.util.Iterator;
21import java.util.List;
22import 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 */
50public 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}

[all classes][com.google.caja.lexer]
EMMA 2.0.5312 (C) Vladimir Roubtsov