1 package org.apache.torque.generator.source;
2
3 /*
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
19 * under the License.
20 */
21
22 import java.util.ArrayList;
23 import java.util.HashSet;
24 import java.util.List;
25 import java.util.ListIterator;
26 import java.util.Set;
27 import java.util.StringTokenizer;
28
29 import org.apache.torque.generator.GeneratorException;
30
31 /**
32 * Methods for traversing a source tree.
33 */
34 public final class SourcePath
35 {
36 /**
37 * The separator between different levels in the path.
38 */
39 private static final String PATH_LEVEL_SEPARATOR = "/";
40
41 /**
42 * The token denoting the current element.
43 */
44 private static final String THIS_TOKEN = ".";
45
46 /**
47 * The token denoting the parent element.
48 */
49 private static final String PARENT_TOKEN = "..";
50
51 /**
52 * The token denoting the parent element.
53 */
54 private static final String ANY_ELEMENT_TOKEN = "*";
55
56 /**
57 * Private constructor for utility class.
58 */
59 private SourcePath()
60 {
61 }
62
63 /**
64 * Returns whether children with the given name exist.
65 *
66 * @param sourceElement the start element, not null.
67 * @param name the name of the child element, not null.
68 *
69 * @return true if children with the given name exist, false otherwise.
70 *
71 * @throws NullPointerException if name is null.
72 */
73 public static boolean hasChild(SourceElement sourceElement, String name)
74 {
75 if (name == null)
76 {
77 throw new NullPointerException("name must not be null");
78 }
79 if (sourceElement == null)
80 {
81 throw new NullPointerException("sourceElement must not be null");
82 }
83 for (SourceElement child : sourceElement.getChildren())
84 {
85 if (name.equals(child.getName()))
86 {
87 return true;
88 }
89 }
90 return false;
91 }
92
93 /**
94 * Returns whether a following element exists as a child of the parent of
95 * this element.
96 *
97 * @param sourceElement the start element, not null.
98 *
99 * @return true if a following element exists, false if not.
100 */
101 public static boolean hasFollowing(SourceElement sourceElement)
102 {
103 return !getFollowing(sourceElement, null).isEmpty();
104 }
105
106 /**
107 * Returns whether an preceding exists as a child of the parent of
108 * this element.
109 *
110 * @param sourceElement the start element, not null.
111 *
112 * @return true if a preceding element exists, false if not.
113 */
114 public static boolean hasPreceding(SourceElement sourceElement)
115 {
116 return !getPreceding(sourceElement, sourceElement.getName()).isEmpty();
117 }
118
119 /**
120 * Returns whether a following element exists as a child of the parent of
121 * this element, which has the same name as this source element.
122 *
123 * @param sourceElement the start element, not null.
124 *
125 * @return true if a following sibling exists, false if not.
126 */
127 public static boolean hasFollowingSibling(SourceElement sourceElement)
128 {
129 return !getFollowing(sourceElement, sourceElement.getName()).isEmpty();
130 }
131
132 /**
133 * Returns whether an preceding exists as a child of the parent of
134 * this element, which has the same name as this source element.
135 *
136 * @param sourceElement the start element, not null.
137 *
138 * @return true if a preceding sibling exists, false if not.
139 */
140 public static boolean hasPrecedingSibling(SourceElement sourceElement)
141 {
142 return !getPreceding(sourceElement, sourceElement.getName()).isEmpty();
143 }
144
145 /**
146 * Returns all the preceding elements before this element
147 * with the given name.
148 * If name is null, all preceding elements are returned.
149 * If this element has no parent, an empty list is returned.
150 *
151 * @param sourceElement the start element, not null.
152 * @param name the name of the preceding elements to select,
153 * or null to select all preceding elements.
154 *
155 * @return a list containing the preceding elements with the given name,
156 * never null.
157 *
158 * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
159 */
160 public static List<SourceElement> getPreceding(
161 SourceElement sourceElement,
162 String name)
163 {
164 if (sourceElement == null)
165 {
166 throw new NullPointerException("sourceElement must not be null");
167 }
168
169 List<SourceElement> result = new ArrayList<SourceElement>();
170 ListIterator<SourceElement> sameLevelIt
171 = getSiblingIteratorPositionedOnSelf(sourceElement);
172 if (sameLevelIt == null)
173 {
174 return result;
175 }
176 boolean first = true;
177 while (sameLevelIt.hasPrevious())
178 {
179 SourceElement sameLevelElement = sameLevelIt.previous();
180 // skip first iterated element because it is input element,
181 // but we want to begin before the input element.
182 if (first)
183 {
184 first = false;
185 continue;
186 }
187 if (name == null || name.equals(sameLevelElement.getName()))
188 {
189 result.add(sameLevelElement);
190 }
191 }
192 return result;
193
194 }
195
196 /**
197 * Returns all the following elements after this element
198 * with the given name.
199 * If name is null, all following elements are returned.
200 * If this element has no parent, an empty list is returned.
201 *
202 * @param sourceElement the start element, not null.
203 * @param name the name of the following elements to select,
204 * or null to select all following elements.
205 *
206 * @return a list containing the following elements with the given name,
207 * never null.
208 *
209 * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
210 */
211 public static List<SourceElement> getFollowing(
212 SourceElement sourceElement,
213 String name)
214 {
215 if (sourceElement == null)
216 {
217 throw new NullPointerException("sourceElement must not be null");
218 }
219 List<SourceElement> result = new ArrayList<SourceElement>();
220
221 ListIterator<SourceElement> sameLevelIt
222 = getSiblingIteratorPositionedOnSelf(sourceElement);
223 if (sameLevelIt == null)
224 {
225 return result;
226 }
227 while (sameLevelIt.hasNext())
228 {
229 SourceElement sameLevelElement = sameLevelIt.next();
230 if (name == null || name.equals(sameLevelElement.getName()))
231 {
232 result.add(sameLevelElement);
233 }
234 }
235 return result;
236 }
237
238 /**
239 * Returns a ListIterator of the siblings of the input source element.
240 * The iterator is positioned such that the next method returns
241 * the element after the input element, and the previous method returns
242 * the input element.
243 *
244 * @param sourceElement the source element for which the sibling iterator
245 * should be created, not null.
246 *
247 * @return the sibling iterator, or null if the input source element has
248 * no parent.
249 *
250 * @throws IllegalArgumentException if the element cannot be found in the
251 * list of children of its parent.
252 */
253 private static ListIterator<SourceElement> getSiblingIteratorPositionedOnSelf(
254 SourceElement sourceElement)
255 {
256 SourceElement parent = sourceElement.getParent();
257 if (parent == null)
258 {
259 return null;
260 }
261 ListIterator<SourceElement> sameLevelIt
262 = parent.getChildren().listIterator();
263
264 boolean found = false;
265 while (sameLevelIt.hasNext())
266 {
267 SourceElement sameLevelElement = sameLevelIt.next();
268 if (sameLevelElement == sourceElement)
269 {
270 found = true;
271 break;
272 }
273 }
274 if (!found)
275 {
276 throw new IllegalArgumentException("Inconsistent source tree: "
277 + "Source element " + sourceElement.getName()
278 + " not found in the list of the children of its parent");
279 }
280 return sameLevelIt;
281 }
282
283 /**
284 * Gets the elements which can be reached from the start element by a given
285 * path.
286 *
287 * @param sourceElement the start element, not null.
288 * @param path the path to use, not null.
289 *
290 * @return the list of matching source elements, not null, may be empty.
291 *
292 * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
293 */
294 public static List<SourceElement> getElements(
295 SourceElement sourceElement,
296 String path)
297 {
298 if (sourceElement == null)
299 {
300 throw new NullPointerException("sourceElement must not be null");
301 }
302
303 if (path.equals(THIS_TOKEN))
304 {
305 List<SourceElement> result = new ArrayList<SourceElement>(1);
306 result.add(sourceElement);
307 return result;
308 }
309 StringTokenizer selectionPathTokenizer
310 = new StringTokenizer(path, PATH_LEVEL_SEPARATOR);
311 List<SourceElement> currentSelection = new ArrayList<SourceElement>();
312 currentSelection.add(sourceElement);
313 while (selectionPathTokenizer.hasMoreTokens())
314 {
315 String childName = selectionPathTokenizer.nextToken();
316 List<SourceElement> nextSelection = new ArrayList<SourceElement>();
317 for (SourceElement currentElement : currentSelection)
318 {
319 if (childName.equals(PARENT_TOKEN))
320 {
321 SourceElement parent = currentElement.getParent();
322 if (parent != null && !nextSelection.contains(parent))
323 {
324 nextSelection.add(parent);
325 }
326 }
327 else if (ANY_ELEMENT_TOKEN.equals(childName))
328 {
329 for (SourceElement child
330 : currentElement.getChildren())
331 {
332 nextSelection.add(child);
333 }
334 }
335 {
336 for (SourceElement child
337 : currentElement.getChildren(childName))
338 {
339 nextSelection.add(child);
340 }
341 }
342 }
343 currentSelection = nextSelection;
344 }
345 return currentSelection;
346 }
347
348 /**
349 * Gets the elements which can be reached from the root element by a given
350 * path. The name of the root element must appear first in the path,
351 * otherwise nothing is selected.
352 *
353 * @param rootElement the root element of the source tree, not null.
354 * @param path the path to use, null selects the root element.
355 *
356 * @return the list of matching source elements, not null, may be empty.
357 *
358 * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
359 */
360 public static List<SourceElement> getElementsFromRoot(
361 SourceElement rootElement,
362 String path)
363 {
364 if (rootElement == null)
365 {
366 throw new NullPointerException("rootElement must not be null");
367 }
368
369 if (path == null
370 || "".equals(path.trim())
371 || PATH_LEVEL_SEPARATOR.equals(path.trim()))
372 {
373 // use root element
374 List<SourceElement> result = new ArrayList<SourceElement>(1);
375 result.add(rootElement);
376 return result;
377 }
378
379 path = path.trim();
380 // remove leading slash
381 if (path.startsWith(PATH_LEVEL_SEPARATOR))
382 {
383 path = path.substring(1);
384 }
385 int firstSeparatorPos = path.indexOf(PATH_LEVEL_SEPARATOR);
386 String firstElementName;
387 if (firstSeparatorPos == -1)
388 {
389 firstElementName = path;
390 path = THIS_TOKEN;
391 }
392 else
393 {
394 firstElementName = path.substring(0, firstSeparatorPos);
395 path = path.substring(firstSeparatorPos + 1);
396 }
397 if (!ANY_ELEMENT_TOKEN.equals(firstElementName)
398 && !rootElement.getName().equals(firstElementName))
399 {
400 return new ArrayList<SourceElement>();
401 }
402 return SourcePath.getElements(rootElement, path);
403 }
404
405
406 /**
407 * Gets a single source element which can be reached from the start element
408 * by a given path.
409 *
410 * @param sourceElement the start element, not null.
411 * @param path the path to use, not null.
412 * @param acceptEmpty whether no match is an error(acceptEmpty=false)
413 * or not (acceptEmpty=true)
414 *
415 * @return the single matching source elements, may be null only if
416 * acceptEmpty=true.
417 *
418 * @throws GeneratorException if more than one source element matches,
419 * or if no source element matches and acceptEmpty=false
420 * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
421 */
422 public static SourceElement getElement(
423 SourceElement sourceElement,
424 String path,
425 boolean acceptEmpty)
426 throws GeneratorException
427 {
428 List<SourceElement> sourceElements
429 = SourcePath.getElements(sourceElement, path);
430 if (sourceElements.isEmpty())
431 {
432 if (acceptEmpty)
433 {
434 return null;
435 }
436 else
437 {
438 throw new GeneratorException(
439 "Source element path "
440 + path
441 + " selects no element on source element "
442 + sourceElement.getName());
443 }
444 }
445 if (sourceElements.size() > 1)
446 {
447 throw new GeneratorException(
448 "Source element path "
449 + path
450 + " selects more than a single element on source element "
451 + sourceElement.getName());
452 }
453 return sourceElements.get(0);
454 }
455
456 /**
457 * Returns the path from the root element to the source element.
458 * The element names are separated by slashes.
459 * Example: root/firstLevelElement/secondLevelElement/currentNode
460 *
461 * @param sourceElement the element to output, not null.
462 *
463 * @return the path from root, not null.
464 *
465 * @throws GeneratorException if the parent chain contains a closed loop.
466 */
467 public static String getPathAsString(SourceElement sourceElement)
468 throws GeneratorException
469 {
470 StringBuilder result = new StringBuilder();
471 getParentPath(sourceElement, new HashSet<SourceElement>(), result);
472 result.append(sourceElement.getName());
473 return result.toString();
474 }
475
476 /**
477 * Gets the path to the parent of a source element.
478 * @param toProcess the source element for which parent the path should be
479 * calculated.
480 * @param alreadyProcessed the elements which are already processed
481 * by this method.
482 * @param result the path to the parent, ends with a slash if any parents
483 * are present.
484 *
485 * @throws GeneratorException if the parent is contained in alreadyProcessed
486 * or if the parent chain contains a closed loop.
487 */
488 private static void getParentPath(
489 SourceElement toProcess,
490 Set<SourceElement> alreadyProcessed,
491 StringBuilder result)
492 throws GeneratorException
493 {
494 SourceElement parent = toProcess.getParent();
495 if (alreadyProcessed.contains(parent))
496 {
497 throw new GeneratorException(
498 "getParentPath(): invoked on a closed loop");
499 }
500 if (parent == null)
501 {
502 return;
503 }
504 result.insert(0, parent.getName() + "/");
505 alreadyProcessed.add(parent);
506 getParentPath(parent, alreadyProcessed, result);
507 }
508 }