JavaParser/com/github/javaparser/ast/Node.java

1	/*
2	* Copyright (C) 2007-2010 Júlio Vilmar Gesser.
3	* Copyright (C) 2011, 2013-2020 The JavaParser Team.
4	*
5	* This file is part of JavaParser.
6	*
7	* JavaParser can be used either under the terms of
8	* a) the GNU Lesser General Public License as published by
9	* the Free Software Foundation, either version 3 of the License, or
10	* (at your option) any later version.
11	* b) the terms of the Apache License
12	*
13	* You should have received a copy of both licenses in LICENCE.LGPL and
14	* LICENCE.APACHE. Please refer to those files for details.
15	*
16	* JavaParser is distributed in the hope that it will be useful,
17	* but WITHOUT ANY WARRANTY; without even the implied warranty of
18	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19	* GNU Lesser General Public License for more details.
20	*/
21	package com.github.javaparser.ast;
22
23	import com.github.javaparser.HasParentNode;
24	import com.github.javaparser.Position;
25	import com.github.javaparser.Range;
26	import com.github.javaparser.TokenRange;
27	import com.github.javaparser.ast.comments.BlockComment;
28	import com.github.javaparser.ast.comments.Comment;
29	import com.github.javaparser.ast.comments.LineComment;
30	import com.github.javaparser.ast.nodeTypes.NodeWithRange;
31	import com.github.javaparser.ast.nodeTypes.NodeWithTokenRange;
32	import com.github.javaparser.ast.observer.AstObserver;
33	import com.github.javaparser.ast.observer.ObservableProperty;
34	import com.github.javaparser.ast.observer.PropagatingAstObserver;
35	import com.github.javaparser.ast.visitor.CloneVisitor;
36	import com.github.javaparser.ast.visitor.EqualsVisitor;
37	import com.github.javaparser.ast.visitor.HashCodeVisitor;
38	import com.github.javaparser.ast.visitor.Visitable;
39	import com.github.javaparser.metamodel.InternalProperty;
40	import com.github.javaparser.metamodel.JavaParserMetaModel;
41	import com.github.javaparser.metamodel.NodeMetaModel;
42	import com.github.javaparser.metamodel.OptionalProperty;
43	import com.github.javaparser.metamodel.PropertyMetaModel;
44	import com.github.javaparser.printer.PrettyPrinter;
45	import com.github.javaparser.printer.PrettyPrinterConfiguration;
46	import com.github.javaparser.resolution.SymbolResolver;
47	import com.github.javaparser.utils.LineSeparator;
48
49	import java.util.*;
50	import java.util.function.Consumer;
51	import java.util.function.Function;
52	import java.util.function.Predicate;
53	import java.util.stream.Stream;
54	import java.util.stream.StreamSupport;
55
56	import static com.github.javaparser.ast.Node.Parsedness.PARSED;
57	import static com.github.javaparser.ast.Node.TreeTraversal.PREORDER;
58	import static java.util.Collections.emptySet;
59	import static java.util.Collections.unmodifiableList;
60	import static java.util.Spliterator.DISTINCT;
61	import static java.util.Spliterator.NONNULL;
62
63	/**
64	* Base class for all nodes of the abstract syntax tree.
65	* <h2>Construction</h2>
66	* <p>The tree is built by instantiating the required nodes, then adding them to other nodes.
67	* If it is the parser who is building the tree, it will use the largest constructor,
68	* the one with "range" as the first parameter.
69	* If you want to manually instantiate nodes, we suggest to...
70	* <ul>
71	* <li>use a convenience method, like "addStatement(...)", or if none are available...</li>
72	* <li>use a convenient constructor, like ClassOrInterfaceType(String name), or if none are available...</li>
73	* <li>use the default constructor.</li>
74	* <li>Alternatively, use one of the JavaParser.parse(snippet) methods.</li>
75	* </ul>
76	* ... and use the various methods on the node to initialize it further, if needed.
77	* <h2>Parent/child</h2>
78	* <p>The parent node field is managed automatically and can be seen as read only.
79	* Note that there is only one parent,
80	* and trying to use the same node in two places will lead to unexpected behaviour.
81	* It is advised to clone() a node before moving it around.
82	* <h2>Comments</h2>
83	* <p>Each Node can have one associated comment which describes it and
84	* a number of "orphan comments" which it contains but are not specifically
85	* associated to any child.
86	* <h2>Positions</h2>
87	* <p>When the parser creates nodes, it sets their source code position in the "range" field.
88	* When you manually instantiate nodes, their range is not set.
89	* The top left character is position 1, 1.
90	* Note that since this is an <i>abstract</i> syntax tree,
91	* it leaves out a lot of text from the original source file,
92	* like where braces or comma's are exactly.
93	* Therefore there is no position information on everything in the original source file.
94	* <h2>Observers</h2>
95	* <p>It is possible to add observers to the the tree.
96	* Any change in the tree is sent as an event to any observers watching.
97	* <h2>Visitors</h2>
98	* <p>The most comfortable way of working with an abstract syntax tree is using visitors.
99	* You can use one of the visitors in the visitor package, or extend one of them.
100	* A visitor can be "run" by calling accept on a node:
101	* <pre>node.accept(visitor, argument);</pre>
102	* where argument is an object of your choice (often simply null.)
103	*
104	* @author Julio Vilmar Gesser
105	*/
106	public abstract class Node implements Cloneable, HasParentNode<Node>, Visitable, NodeWithRange<Node>, NodeWithTokenRange<Node> {
107
108	/**
109	* Different registration mode for observers on nodes.
110	*/
111	public enum ObserverRegistrationMode {
112
113	/**
114	* Notify exclusively for changes happening on this node alone.
115	*/
116	JUST_THIS_NODE,
117	/**
118	* Notify for changes happening on this node and all its descendants existing at the moment in
119	* which the observer was registered. Nodes attached later will not be observed.
120	*/
121	THIS_NODE_AND_EXISTING_DESCENDANTS,
122	/**
123	* Notify for changes happening on this node and all its descendants. The descendants existing at the moment in
124	* which the observer was registered will be observed immediately. As new nodes are attached later they are
125	* automatically registered to be observed.
126	*/
127	SELF_PROPAGATING
128	}
129
130	public enum Parsedness {
131
132	PARSED, UNPARSABLE
133	}
134
135	/**
136	* This can be used to sort nodes on position.
137	*/
138	public static Comparator<NodeWithRange<?>> NODE_BY_BEGIN_POSITION = (a, b) -> {
139	if (a.getRange().isPresent() && b.getRange().isPresent()) {
140	return a.getRange().get().begin.compareTo(b.getRange().get().begin);
141	}
142	if (a.getRange().isPresent() \|\| b.getRange().isPresent()) {
143	if (a.getRange().isPresent()) {
144	return 1;
145	}
146	return -1;
147	}
148	return 0;
149	};
150
151	private static PrettyPrinterConfiguration toStringPrettyPrinterConfiguration = new PrettyPrinterConfiguration();
152
153	protected static final PrettyPrinterConfiguration prettyPrinterNoCommentsConfiguration = new PrettyPrinterConfiguration().setPrintComments(false);
154
155	@InternalProperty
156	private Range range;
157
158	@InternalProperty
159	private TokenRange tokenRange;
160
161	@InternalProperty
162	private Node parentNode;
163
164	@InternalProperty
165	private List<Node> childNodes = new LinkedList<>();
166
167	@InternalProperty
168	private List<Comment> orphanComments = new LinkedList<>();
169
170	@InternalProperty
171	private IdentityHashMap<DataKey<?>, Object> data = null;
172
173	@OptionalProperty
174	private Comment comment;
175
176	@InternalProperty
177	private Set<AstObserver> observers = new HashSet<>();
178
179	@InternalProperty
180	private Parsedness parsed = PARSED;
181
182	protected Node(TokenRange tokenRange) {
183	setTokenRange(tokenRange);
184	}
185
186	/**
187	* Called in every constructor for node specific code.
188	* It can't be written in the constructor itself because it will
189	* be overwritten during code generation.
190	*/
191	protected void customInitialization() {
192	}
193
194	/**
195	* This is a comment associated with this node.
196	*
197	* @return comment property
198	*/
199	@Generated("com.github.javaparser.generator.core.node.PropertyGenerator")
200	public Optional<Comment> getComment() {
201	return Optional.ofNullable(comment);
202	}
203
204	/**
205	* @return the range of characters in the source code that this node covers.
206	*/
207	public Optional<Range> getRange() {
208	return Optional.ofNullable(range);
209	}
210
211	/**
212	* @return the range of tokens that this node covers.
213	*/
214	public Optional<TokenRange> getTokenRange() {
215	return Optional.ofNullable(tokenRange);
216	}
217
218	public Node setTokenRange(TokenRange tokenRange) {
219	this.tokenRange = tokenRange;
220	if (tokenRange == null \|\| !(tokenRange.getBegin().getRange().isPresent() && tokenRange.getEnd().getRange().isPresent())) {
221	range = null;
222	} else {
223	range = new Range(tokenRange.getBegin().getRange().get().begin, tokenRange.getEnd().getRange().get().end);
224	}
225	return this;
226	}
227
228	/**
229	* @param range the range of characters in the source code that this node covers. null can be used to indicate that
230	* no range information is known, or that it is not of interest.
231	*/
232	public Node setRange(Range range) {
233	if (this.range == range) {
234	return this;
235	}
236	notifyPropertyChange(ObservableProperty.RANGE, this.range, range);
237	this.range = range;
238	return this;
239	}
240
241	/**
242	* Use this to store additional information to this node.
243	*
244	* @param comment to be set
245	*/
246	public Node setComment(final Comment comment) {
247	if (this.comment == comment) {
248	return this;
249	}
250	notifyPropertyChange(ObservableProperty.COMMENT, this.comment, comment);
251	if (this.comment != null) {
252	this.comment.setCommentedNode(null);
253	}
254	this.comment = comment;
255	if (comment != null) {
256	this.comment.setCommentedNode(this);
257	}
258	return this;
259	}
260
261	/**
262	* Use this to store additional information to this node.
263	*
264	* @param comment to be set
265	*/
266	public final Node setLineComment(String comment) {
267	return setComment(new LineComment(comment));
268	}
269
270	/**
271	* Use this to store additional information to this node.
272	*
273	* @param comment to be set
274	*/
275	public final Node setBlockComment(String comment) {
276	return setComment(new BlockComment(comment));
277	}
278
279	/**
280	* @return pretty printed source code for this node and its children.
281	* Formatting can be configured with Node.setToStringPrettyPrinterConfiguration.
282	*/
283	@Override
284	public final String toString() {
285	if (containsData(LINE_SEPARATOR_KEY)) {
286	LineSeparator lineSeparator = getLineEndingStyleOrDefault(LineSeparator.SYSTEM);
287	toStringPrettyPrinterConfiguration.setEndOfLineCharacter(lineSeparator.asRawString());
288	}
289	return new PrettyPrinter(toStringPrettyPrinterConfiguration).print(this);
290	}
291
292	/**
293	* @return pretty printed source code for this node and its children.
294	* Formatting can be configured with parameter prettyPrinterConfiguration.
295	*/
296	public final String toString(PrettyPrinterConfiguration prettyPrinterConfiguration) {
297	return new PrettyPrinter(prettyPrinterConfiguration).print(this);
298	}
299
300	@Override
301	public final int hashCode() {
302	return HashCodeVisitor.hashCode(this);
303	}
304
305	@Override
306	public boolean equals(final Object obj) {
307	if (obj == null \|\| !(obj instanceof Node)) {
308	return false;
309	}
310	return EqualsVisitor.equals(this, (Node) obj);
311	}
312
313	@Override
314	public Optional<Node> getParentNode() {
315	return Optional.ofNullable(parentNode);
316	}
317
318	/**
319	* Contains all nodes that have this node set as their parent.
320	* You can add and remove nodes from this list by adding or removing nodes from the fields of this node.
321	*
322	* @return all nodes that have this node as their parent.
323	*/
324	public List<Node> getChildNodes() {
325	return unmodifiableList(childNodes);
326	}
327
328	public void addOrphanComment(Comment comment) {
329	orphanComments.add(comment);
330	comment.setParentNode(this);
331	}
332
333	public boolean removeOrphanComment(Comment comment) {
334	boolean removed = orphanComments.remove(comment);
335	if (removed) {
336	notifyPropertyChange(ObservableProperty.COMMENT, comment, null);
337	comment.setParentNode(null);
338	}
339	return removed;
340	}
341
342	/**
343	* This is a list of Comment which are inside the node and are not associated
344	* with any meaningful AST Node.
345	* <p>
346	* For example, comments at the end of methods (immediately before the parenthesis)
347	* or at the end of CompilationUnit are orphan comments.
348	* <p>
349	* When more than one comment preceeds a statement, the one immediately preceding it
350	* it is associated with the statements, while the others are orphans.
351	* <p>
352	* Changes to this list are not persisted.
353	*
354	* @return all comments that cannot be attributed to a concept
355	*/
356	public List<Comment> getOrphanComments() {
357	return new LinkedList<>(orphanComments);
358	}
359
360	/**
361	* This is the list of Comment which are contained in the Node either because
362	* they are properly associated to one of its children or because they are floating
363	* around inside the Node
364	*
365	* @return all Comments within the node as a list
366	*/
367	public List<Comment> getAllContainedComments() {
368	List<Comment> comments = new LinkedList<>();
369	comments.addAll(getOrphanComments());
370	for (Node child : getChildNodes()) {
371	child.getComment().ifPresent(comments::add);
372	comments.addAll(child.getAllContainedComments());
373	}
374	return comments;
375	}
376
377	/**
378	* Assign a new parent to this node, removing it
379	* from the list of children of the previous parent, if any.
380	*
381	* @param newParentNode node to be set as parent
382	*/
383	@Override
384	public Node setParentNode(Node newParentNode) {
385	if (newParentNode == parentNode) {
386	return this;
387	}
388	observers.forEach(o -> o.parentChange(this, parentNode, newParentNode));
389	// remove from old parent, if any
390	if (parentNode != null) {
391	final List<Node> parentChildNodes = parentNode.childNodes;
392	for (int i = 0; i < parentChildNodes.size(); i++) {
393	if (parentChildNodes.get(i) == this) {
394	parentChildNodes.remove(i);
395	}
396	}
397	}
398	parentNode = newParentNode;
399	// add to new parent, if any
400	if (parentNode != null) {
401	parentNode.childNodes.add(this);
402	}
403	return this;
404	}
405
406	protected void setAsParentNodeOf(Node childNode) {
407	if (childNode != null) {
408	childNode.setParentNode(getParentNodeForChildren());
409	}
410	}
411
412	/**
413	* @deprecated Use {@link Position#ABSOLUTE_BEGIN_LINE}
414	*/
415	@Deprecated
416	public static final int ABSOLUTE_BEGIN_LINE = Position.ABSOLUTE_BEGIN_LINE;
417
418	/**
419	* @deprecated Use {@link Position#ABSOLUTE_END_LINE}
420	*/
421	@Deprecated
422	public static final int ABSOLUTE_END_LINE = Position.ABSOLUTE_END_LINE;
423
424	public void tryAddImportToParentCompilationUnit(Class<?> clazz) {
425	findAncestor(CompilationUnit.class).ifPresent(p -> p.addImport(clazz));
426	}
427
428	/**
429	* Recursively finds all nodes of a certain type.
430	*
431	* @param clazz the type of node to find.
432	* @deprecated use {@link Node#findAll(Class)} but be aware that findAll also considers the initial node.
433	*/
434	@Deprecated
435	public <N extends Node> List<N> getChildNodesByType(Class<N> clazz) {
436	List<N> nodes = new ArrayList<>();
437	for (Node child : getChildNodes()) {
438	if (clazz.isInstance(child)) {
439	nodes.add(clazz.cast(child));
440	}
441	nodes.addAll(child.getChildNodesByType(clazz));
442	}
443	return nodes;
444	}
445
446	/**
447	* @deprecated use {@link Node#findAll(Class)} but be aware that findAll also considers the initial node.
448	*/
449	@Deprecated
450	public <N extends Node> List<N> getNodesByType(Class<N> clazz) {
451	return getChildNodesByType(clazz);
452	}
453
454	/**
455	* Gets data for this node using the given key.
456	*
457	* @param <M> The type of the data.
458	* @param key The key for the data
459	* @return The data.
460	* @throws IllegalStateException if the key was not set in this node.
461	* @see Node#containsData(DataKey)
462	* @see DataKey
463	*/
464	@SuppressWarnings("unchecked")
465	public <M> M getData(final DataKey<M> key) {
466	if (data == null) {
467	throw new IllegalStateException("No data of this type found. Use containsData to check for this first.");
468	}
469	M value = (M) data.get(key);
470	if (value == null) {
471	throw new IllegalStateException("No data of this type found. Use containsData to check for this first.");
472	}
473	return value;
474	}
475
476	/**
477	* This method was added to support the clone method.
478	*
479	* @return all known data keys.
480	*/
481	public Set<DataKey<?>> getDataKeys() {
482	if (data == null) {
483	return emptySet();
484	}
485	return data.keySet();
486	}
487
488	/**
489	* Sets data for this node using the given key.
490	* For information on creating DataKey, see {@link DataKey}.
491	*
492	* @param <M> The type of data
493	* @param key The singleton key for the data
494	* @param object The data object
495	* @see DataKey
496	*/
497	public <M> void setData(DataKey<M> key, M object) {
498	if (data == null) {
499	data = new IdentityHashMap<>();
500	}
501	data.put(key, object);
502	}
503
504	/**
505	* @return does this node have data for this key?
506	* @see DataKey
507	*/
508	public boolean containsData(DataKey<?> key) {
509	if (data == null) {
510	return false;
511	}
512	return data.containsKey(key);
513	}
514
515	/**
516	* Remove data by key.
517	*
518	* @see DataKey
519	*/
520	public void removeData(DataKey<?> key) {
521	if (data != null) {
522	data.remove(key);
523	}
524	}
525
526	/**
527	* Try to remove this node from the parent
528	*
529	* @return true if removed, false if it is a required property of the parent, or if the parent isn't set.
530	* @throws RuntimeException if it fails in an unexpected way
531	*/
532	public boolean remove() {
533	if (parentNode == null) {
534	return false;
535	}
536	return parentNode.remove(this);
537	}
538
539	/**
540	* Try to replace this node in the parent with the supplied node.
541	*
542	* @return true if removed, or if the parent isn't set.
543	* @throws RuntimeException if it fails in an unexpected way
544	*/
545	public boolean replace(Node node) {
546	if (parentNode == null) {
547	return false;
548	}
549	return parentNode.replace(this, node);
550	}
551
552	/**
553	* Forcibly removes this node from the AST.
554	* If it cannot be removed from the parent with remove(),
555	* it will try to remove its parent instead,
556	* until it finds a node that can be removed,
557	* or no parent can be found.
558	* <p>
559	* Since everything at CompilationUnit level is removable,
560	* this method will only (silently) fail when the node is in a detached AST fragment.
561	*/
562	public void removeForced() {
563	if (!remove()) {
564	getParentNode().ifPresent(Node::remove);
565	}
566	}
567
568	@Override
569	public Node getParentNodeForChildren() {
570	return this;
571	}
572
573	protected void setAsParentNodeOf(NodeList<? extends Node> list) {
574	if (list != null) {
575	list.setParentNode(getParentNodeForChildren());
576	}
577	}
578
579	public <P> void notifyPropertyChange(ObservableProperty property, P oldValue, P newValue) {
580	this.observers.forEach(o -> o.propertyChange(this, property, oldValue, newValue));
581	}
582
583	@Override
584	public void unregister(AstObserver observer) {
585	this.observers.remove(observer);
586	}
587
588	@Override
589	public void register(AstObserver observer) {
590	this.observers.add(observer);
591	}
592
593	/**
594	* Register a new observer for the given node. Depending on the mode specified also descendants, existing
595	* and new, could be observed. For more details see <i>ObserverRegistrationMode</i>.
596	*/
597	public void register(AstObserver observer, ObserverRegistrationMode mode) {
598	if (mode == null) {
599	throw new IllegalArgumentException("Mode should be not null");
600	}
601	switch(mode) {
602	case JUST_THIS_NODE:
603	register(observer);
604	break;
605	case THIS_NODE_AND_EXISTING_DESCENDANTS:
606	registerForSubtree(observer);
607	break;
608	case SELF_PROPAGATING:
609	registerForSubtree(PropagatingAstObserver.transformInPropagatingObserver(observer));
610	break;
611	default:
612	throw new UnsupportedOperationException("This mode is not supported: " + mode);
613	}
614	}
615
616	/**
617	* Register the observer for the current node and all the contained node and nodelists, recursively.
618	*/
619	public void registerForSubtree(AstObserver observer) {
620	register(observer);
621	this.getChildNodes().forEach(c -> c.registerForSubtree(observer));
622	for (PropertyMetaModel property : getMetaModel().getAllPropertyMetaModels()) {
623	if (property.isNodeList()) {
624	NodeList<?> nodeList = (NodeList<?>) property.getValue(this);
625	if (nodeList != null)
626	nodeList.register(observer);
627	}
628	}
629	}
630
631	@Override
632	public boolean isRegistered(AstObserver observer) {
633	return this.observers.contains(observer);
634	}
635
636	@Generated("com.github.javaparser.generator.core.node.RemoveMethodGenerator")
637	public boolean remove(Node node) {
638	if (node == null)
639	return false;
640	if (comment != null) {
641	if (node == comment) {
642	removeComment();
643	return true;
644	}
645	}
646	return false;
647	}
648
649	@Generated("com.github.javaparser.generator.core.node.RemoveMethodGenerator")
650	public Node removeComment() {
651	return setComment((Comment) null);
652	}
653
654	@Override
655	@Generated("com.github.javaparser.generator.core.node.CloneGenerator")
656	public Node clone() {
657	return (Node) accept(new CloneVisitor(), null);
658	}
659
660	/**
661	* @return get JavaParser specific node introspection information.
662	*/
663	@Generated("com.github.javaparser.generator.core.node.GetMetaModelGenerator")
664	public NodeMetaModel getMetaModel() {
665	return JavaParserMetaModel.nodeMetaModel;
666	}
667
668	/**
669	* @return whether this node was successfully parsed or not.
670	* If it was not, only the range and tokenRange fields will be valid.
671	*/
672	public Parsedness getParsed() {
673	return parsed;
674	}
675
676	/**
677	* Used by the parser to flag unparsable nodes.
678	*/
679	public Node setParsed(Parsedness parsed) {
680	this.parsed = parsed;
681	return this;
682	}
683
684	public static PrettyPrinterConfiguration getToStringPrettyPrinterConfiguration() {
685	return toStringPrettyPrinterConfiguration;
686	}
687
688	public static void setToStringPrettyPrinterConfiguration(PrettyPrinterConfiguration toStringPrettyPrinterConfiguration) {
689	Node.toStringPrettyPrinterConfiguration = toStringPrettyPrinterConfiguration;
690	}
691
692	@Generated("com.github.javaparser.generator.core.node.ReplaceMethodGenerator")
693	public boolean replace(Node node, Node replacementNode) {
694	if (node == null)
695	return false;
696	if (comment != null) {
697	if (node == comment) {
698	setComment((Comment) replacementNode);
699	return true;
700	}
701	}
702	return false;
703	}
704
705	/**
706	* Finds the root node of this AST by finding the topmost parent.
707	*/
708	public Node findRootNode() {
709	Node n = this;
710	while (n.getParentNode().isPresent()) {
711	n = n.getParentNode().get();
712	}
713	return n;
714	}
715
716	/**
717	* @return the containing CompilationUnit, or empty if this node is not inside a compilation unit.
718	*/
719	public Optional<CompilationUnit> findCompilationUnit() {
720	Node rootNode = findRootNode();
721	if (rootNode instanceof CompilationUnit) {
722	return Optional.of((CompilationUnit) rootNode);
723	}
724	return Optional.empty();
725	}
726
727	public LineSeparator getLineEndingStyleOrDefault(LineSeparator defaultLineSeparator) {
728	if (getLineEndingStyle().isStandardEol()) {
729	return getLineEndingStyle();
730	}
731	return defaultLineSeparator;
732	}
733
734	public LineSeparator getLineEndingStyle() {
735	Node current = this;
736
737	// First check this node
738	if(current.containsData(Node.LINE_SEPARATOR_KEY)) {
739	LineSeparator lineSeparator = current.getData(Node.LINE_SEPARATOR_KEY);
740	return lineSeparator;
741	}
742
743	// Then check parent/ancestor nodes
744	while(current.getParentNode().isPresent()) {
745	current = current.getParentNode().get();
746	if(current.containsData(Node.LINE_SEPARATOR_KEY)) {
747	return current.getData(Node.LINE_SEPARATOR_KEY);
748	}
749	}
750
751	// Default to the system line separator if it's not already set within the parsed node/code.
752	return LineSeparator.SYSTEM;
753	}
754
755	protected SymbolResolver getSymbolResolver() {
756	return findCompilationUnit().map(cu -> {
757	if (cu.containsData(SYMBOL_RESOLVER_KEY)) {
758	return cu.getData(SYMBOL_RESOLVER_KEY);
759	} else {
760	throw new IllegalStateException("Symbol resolution not configured: to configure consider setting a SymbolResolver in the ParserConfiguration");
761	}
762	}).orElseThrow(() -> new IllegalStateException("The node is not inserted in a CompilationUnit"));
763	}
764
765	// We need to expose it because we will need to use it to inject the SymbolSolver
766	public static final DataKey<SymbolResolver> SYMBOL_RESOLVER_KEY = new DataKey<SymbolResolver>() {
767	};
768
769	public static final DataKey<LineSeparator> LINE_SEPARATOR_KEY = new DataKey<LineSeparator>() {
770	};
771
772	public enum TreeTraversal {
773
774	PREORDER, BREADTHFIRST, POSTORDER, PARENTS, DIRECT_CHILDREN
775	}
776
777	private Iterator<Node> treeIterator(TreeTraversal traversal) {
778	switch(traversal) {
779	case BREADTHFIRST:
780	return new BreadthFirstIterator(this);
781	case POSTORDER:
782	return new PostOrderIterator(this);
783	case PREORDER:
784	return new PreOrderIterator(this);
785	case DIRECT_CHILDREN:
786	return new DirectChildrenIterator(this);
787	case PARENTS:
788	return new ParentsVisitor(this);
789	default:
790	throw new IllegalArgumentException("Unknown traversal choice.");
791	}
792	}
793
794	private Iterable<Node> treeIterable(TreeTraversal traversal) {
795	return () -> treeIterator(traversal);
796	}
797
798	/**
799	* Make a stream of nodes using traversal algorithm "traversal".
800	*/
801	public Stream<Node> stream(TreeTraversal traversal) {
802	return StreamSupport.stream(Spliterators.spliteratorUnknownSize(treeIterator(traversal), NONNULL \| DISTINCT), false);
803	}
804
805	/**
806	* Make a stream of nodes using pre-order traversal.
807	*/
808	public Stream<Node> stream() {
809	return StreamSupport.stream(Spliterators.spliteratorUnknownSize(treeIterator(PREORDER), NONNULL \| DISTINCT), false);
810	}
811
812	/**
813	* Walks the AST, calling the consumer for every node, with traversal algorithm "traversal".
814	* <br>This is the most general walk method. All other walk and findAll methods are based on this.
815	*/
816	public void walk(TreeTraversal traversal, Consumer<Node> consumer) {
817	// Could be implemented as a call to the above walk method, but this is a little more efficient.
818	for (Node node : treeIterable(traversal)) {
819	consumer.accept(node);
820	}
821	}
822
823	/**
824	* Walks the AST, calling the consumer for every node with pre-order traversal.
825	*/
826	public void walk(Consumer<Node> consumer) {
827	walk(PREORDER, consumer);
828	}
829
830	/**
831	* Walks the AST with pre-order traversal, calling the consumer for every node of type "nodeType".
832	*/
833	public <T extends Node> void walk(Class<T> nodeType, Consumer<T> consumer) {
834	walk(TreeTraversal.PREORDER, node -> {
835	if (nodeType.isAssignableFrom(node.getClass())) {
836	consumer.accept(nodeType.cast(node));
837	}
838	});
839	}
840
841	/**
842	* Walks the AST with pre-order traversal, returning all nodes of type "nodeType".
843	*/
844	public <T extends Node> List<T> findAll(Class<T> nodeType) {
845	final List<T> found = new ArrayList<>();
846	walk(nodeType, found::add);
847	return found;
848	}
849
850	/**
851	* Walks the AST with pre-order traversal, returning all nodes of type "nodeType" that match the predicate.
852	*/
853	public <T extends Node> List<T> findAll(Class<T> nodeType, Predicate<T> predicate) {
854	final List<T> found = new ArrayList<>();
855	walk(nodeType, n -> {
856	if (predicate.test(n))
857	found.add(n);
858	});
859	return found;
860	}
861
862	/**
863	* Walks the AST, applying the function for every node, with traversal algorithm "traversal". If the function
864	* returns something else than null, the traversal is stopped and the function result is returned. <br>This is the
865	* most general findFirst method. All other findFirst methods are based on this.
866	*/
867	public <T> Optional<T> findFirst(TreeTraversal traversal, Function<Node, Optional<T>> consumer) {
868	for (Node node : treeIterable(traversal)) {
869	final Optional<T> result = consumer.apply(node);
870	if (result.isPresent()) {
871	return result;
872	}
873	}
874	return Optional.empty();
875	}
876
877	/**
878	* Walks the AST with pre-order traversal, returning the first node of type "nodeType" or empty() if none is found.
879	*/
880	public <N extends Node> Optional<N> findFirst(Class<N> nodeType) {
881	return findFirst(TreeTraversal.PREORDER, node -> {
882	if (nodeType.isAssignableFrom(node.getClass())) {
883	return Optional.of(nodeType.cast(node));
884	}
885	return Optional.empty();
886	});
887	}
888
889	/**
890	* Walks the AST with pre-order traversal, returning the first node of type "nodeType" that matches "predicate" or empty() if none is
891	* found.
892	*/
893	public <N extends Node> Optional<N> findFirst(Class<N> nodeType, Predicate<N> predicate) {
894	return findFirst(TreeTraversal.PREORDER, node -> {
895	if (nodeType.isAssignableFrom(node.getClass())) {
896	final N castNode = nodeType.cast(node);
897	if (predicate.test(castNode)) {
898	return Optional.of(castNode);
899	}
900	}
901	return Optional.empty();
902	});
903	}
904
905	/**
906	* Determines whether this node is an ancestor of the given node. A node is <i>not</i> an ancestor of itself.
907	*
908	* @param descendant the node for which to determine whether it has this node as an ancestor.
909	* @return {@code true} if this node is an ancestor of the given node, and {@code false} otherwise.
910	* @see HasParentNode#isDescendantOf(Node)
911	*/
912	public boolean isAncestorOf(Node descendant) {
913	return this != descendant && findFirst(Node.class, n -> n == descendant).isPresent();
914	}
915
916	/**
917	* Performs a breadth-first node traversal starting with a given node.
918	*
919	* @see <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Breadth-first traversal</a>
920	*/
921	public static class BreadthFirstIterator implements Iterator<Node> {
922
923	private final Queue<Node> queue = new LinkedList<>();
924
925	public BreadthFirstIterator(Node node) {
926	queue.add(node);
927	}
928
929	@Override
930	public boolean hasNext() {
931	return !queue.isEmpty();
932	}
933
934	@Override
935	public Node next() {
936	Node next = queue.remove();
937	queue.addAll(next.getChildNodes());
938	return next;
939	}
940	}
941
942	/**
943	* Performs a simple traversal over all nodes that have the passed node as their parent.
944	*/
945	public static class DirectChildrenIterator implements Iterator<Node> {
946
947	private final Iterator<Node> childrenIterator;
948
949	public DirectChildrenIterator(Node node) {
950	childrenIterator = new ArrayList<>(node.getChildNodes()).iterator();
951	}
952
953	@Override
954	public boolean hasNext() {
955	return childrenIterator.hasNext();
956	}
957
958	@Override
959	public Node next() {
960	return childrenIterator.next();
961	}
962	}
963
964	/**
965	* Iterates over the parent of the node, then the parent's parent, then the parent's parent's parent, until running
966	* out of parents.
967	*/
968	public static class ParentsVisitor implements Iterator<Node> {
969
970	private Node node;
971
972	public ParentsVisitor(Node node) {
973	this.node = node;
974	}
975
976	@Override
977	public boolean hasNext() {
978	return node.getParentNode().isPresent();
979	}
980
981	@Override
982	public Node next() {
983	node = node.getParentNode().orElse(null);
984	return node;
985	}
986	}
987
988	/**
989	* Performs a pre-order (or depth-first) node traversal starting with a given node.
990	*
991	* @see <a href="https://en.wikipedia.org/wiki/Pre-order">Pre-order traversal</a>
992	*/
993	public static class PreOrderIterator implements Iterator<Node> {
994
995	private final Stack<Node> stack = new Stack<>();
996
997	public PreOrderIterator(Node node) {
998	stack.add(node);
999	}
1000
1001	@Override
1002	public boolean hasNext() {
1003	return !stack.isEmpty();
1004	}
1005
1006	@Override
1007	public Node next() {
1008	Node next = stack.pop();
1009	List<Node> children = next.getChildNodes();
1010	for (int i = children.size() - 1; i >= 0; i--) {
1011	stack.add(children.get(i));
1012	}
1013	return next;
1014	}
1015	}
1016
1017	/**
1018	* Performs a post-order (or leaves-first) node traversal starting with a given node.
1019	*
1020	* @see <a href="https://en.wikipedia.org/wiki/Post-order">Post-order traversal</a>
1021	*/
1022	public static class PostOrderIterator implements Iterator<Node> {
1023
1024	private final Stack<List<Node>> nodesStack = new Stack<>();
1025
1026	private final Stack<Integer> cursorStack = new Stack<>();
1027
1028	private final Node root;
1029
1030	private boolean hasNext = true;
1031
1032	public PostOrderIterator(Node root) {
1033	this.root = root;
1034	fillStackToLeaf(root);
1035	}
1036
1037	private void fillStackToLeaf(Node node) {
1038	while (true) {
1039	List<Node> childNodes = new ArrayList<>(node.getChildNodes());
1040	if (childNodes.isEmpty()) {
1041	break;
1042	}
1043	nodesStack.push(childNodes);
1044	cursorStack.push(0);
1045	node = childNodes.get(0);
1046	}
1047	}
1048
1049	@Override
1050	public boolean hasNext() {
1051	return hasNext;
1052	}
1053
1054	@Override
1055	public Node next() {
1056	final List<Node> nodes = nodesStack.peek();
1057	final int cursor = cursorStack.peek();
1058	final boolean levelHasNext = cursor < nodes.size();
1059	if (levelHasNext) {
1060	Node node = nodes.get(cursor);
1061	fillStackToLeaf(node);
1062	return nextFromLevel();
1063	} else {
1064	nodesStack.pop();
1065	cursorStack.pop();
1066	hasNext = !nodesStack.empty();
1067	if (hasNext) {
1068	return nextFromLevel();
1069	}
1070	return root;
1071	}
1072	}
1073
1074	private Node nextFromLevel() {
1075	final List<Node> nodes = nodesStack.peek();
1076	final int cursor = cursorStack.pop();
1077	cursorStack.push(cursor + 1);
1078	return nodes.get(cursor);
1079	}
1080	}
1081	}
1082