1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code;
27
28 import java.util.List;
29 import java.util.Objects;
30 import java.util.stream.Gatherer;
31 import java.util.stream.Stream;
32
33 /**
34 * A code element, one of {@link Body body}, {@link Block block}, or {@link Op operation}, is an element in a code
35 * model tree.
36 * <p>
37 * Code elements form a tree. A code element may have a parent code element. A root code element is an operation,
38 * a root operation, that has no parent element (a block). A code element and all its ancestors can be traversed,
39 * up to and including the root operation.
40 * <p>
41 * A code element may have child code elements. A root code element and all its descendants can be
42 * traversed, down to and including elements with no children. Bodies and blocks have at least one child element.
43 * <p>
44 * Operations contain child bodies, bodies contain child blocks, and blocks contain child operations, to form
45 * a tree of arbitrary depth.
46 *
47 * @param <E> the code element type
48 * @param <C> the child code element type.
49 * @sealedGraph
50 */
51 // @@@ E may not be needed
52 public sealed interface CodeElement<
53 E extends CodeElement<E, C>,
54 C extends CodeElement<C, ?>>
55 extends CodeItem
56 permits Body, Block, Op {
57
58 /**
59 * {@return a stream of code elements sorted topologically in pre-order traversal.}
60 */
61 default Stream<CodeElement<?, ?>> elements() {
62 return Stream.of(this).gather(() -> (_, e, downstream) -> traversePreOrder(e, downstream));
63 }
64
65 private static boolean traversePreOrder(CodeElement<?, ?> e, Gatherer.Downstream<? super CodeElement<?, ?>> d) {
66 if (!d.push(e)) {
67 return false;
68 }
69 for (CodeElement<?, ?> c : e.children()) {
70 if (!traversePreOrder(c, d)) {
71 return false;
72 }
73 }
74 return true;
75 }
76
77 /**
78 * Returns the parent element, otherwise {@code null} if this element is an operation that has no parent block.
79 *
80 * @return the parent code element.
81 * @throws IllegalStateException if an encountered block is being built and is not observable.
82 */
83 CodeElement<?, E> parent();
84
85 // Nearest ancestors
86
87 /**
88 * Finds the nearest ancestor operation, otherwise {@code null} if there is no nearest ancestor.
89 *
90 * @return the nearest ancestor operation.
91 * @throws IllegalStateException if an encountered block is being built and is not observable.
92 */
93 default Op ancestorOp() {
94 return switch (this) {
95 // block -> body -> op~
96 case Block block -> block.parent().parent();
97 // body -> op~
98 case Body body -> body.parent();
99 // op -> block? -> body -> op~
100 case Op op -> {
101 // Throws ISE if encountering block being built
102 Block parent = op.parent();
103 yield parent == null ? null : parent.parent().parent();
104 }
105 };
106 }
107
108 /**
109 * Finds the nearest ancestor body, otherwise {@code null} if there is no nearest ancestor.
110 *
111 * @return the nearest ancestor body.
112 * @throws IllegalStateException if an encountered block is being built and is not observable.
113 */
114 default Body ancestorBody() {
115 return switch (this) {
116 // block -> body
117 case Block block -> block.parent();
118 // body -> op~ -> block? -> body
119 case Body body -> {
120 // Throws ISE if block is not built
121 Block ancestor = body.parent().parent();
122 yield ancestor == null ? null : ancestor.parent();
123 }
124 // op~ -> block? -> body
125 case Op op -> {
126 // Throws ISE if encountering block being built
127 Block parent = op.parent();
128 yield parent == null ? null : parent.parent();
129 }
130 };
131 }
132
133 /**
134 * Finds the nearest ancestor block, otherwise {@code null} if there is no nearest ancestor.
135 *
136 * @return the nearest ancestor block.
137 * @throws IllegalStateException if an encountered block is being built and is not observable.
138 */
139 default Block ancestorBlock() {
140 return switch (this) {
141 // block -> body -> op~ -> block?
142 // Throws ISE if encountering block being built
143 case Block block -> block.parent().parent().parent();
144 // body -> op~ -> block?
145 // Throws ISE if encountering block being built
146 case Body body -> body.parent().parent();
147 // op~ -> block?
148 // Throws ISE if encountering block being built
149 case Op op -> op.parent();
150 };
151 }
152
153 /**
154 * Returns true if this element is an ancestor of the descendant element.
155 *
156 * @param descendant the descendant element.
157 * @return true if this element is an ancestor of the descendant element.
158 * @throws IllegalStateException if an encountered block is being built and is not observable.
159 * @see #isDescendantOf
160 */
161 default boolean isAncestorOf(CodeElement<?, ?> descendant) {
162 Objects.requireNonNull(descendant);
163
164 CodeElement<?, ?> e = descendant.parent();
165 while (e != null && e != this) {
166 e = e.parent();
167 }
168 return e != null;
169 }
170
171 /**
172 * Returns true if this element is a descendant of the ancestor element.
173 *
174 * @param ancestor the ancestor element.
175 * @return true if this element is a descendant of the ancestor element.
176 * @throws IllegalStateException if an encountered block is being built and is not observable.
177 * @see #isAncestorOf
178 */
179 default boolean isDescendantOf(CodeElement<?, ?> ancestor) {
180 Objects.requireNonNull(ancestor);
181 return ancestor.isAncestorOf(this);
182 }
183
184 /**
185 * Returns the child code elements, as an unmodifiable list.
186 *
187 * @return the child code elements
188 */
189 List<C> children();
190
191 /**
192 * Compares two code elements by comparing their pre-order traversal positions in the code model.
193 * <p>
194 * The pre-order traversal position of a code element, {@code e} say, is equivalent to result of
195 * the expression {@code root.elements().toList().indexOf(e)}, where {@code root} is the root
196 * code element of the code model containing {@code e}.
197 *
198 * @param a the first code element to compare
199 * @param b the second code element to compare
200 * @return the value {@code 0} if {@code a == b}; {@code -1} if {@code a}'s pre-order traversal position
201 * is less than {@code b}'s position; and {@code 1} if {@code a}'s pre-order traversal position
202 * is greater than {@code b}'s position
203 * @throws IllegalArgumentException if {@code a} and {@code b} are not present in the same code model
204 * @throws IllegalStateException if an encountered block is being built and is not observable.
205 */
206 static int compare(CodeElement<?, ?> a, CodeElement<?, ?> b) {
207 if (a == b) {
208 return 0;
209 }
210
211 // Find the common ancestor of a and b and the respective children
212 int depthA = getDepth(a);
213 int depthB = getDepth(b);
214
215 CodeElement<?, ?> childA = a;
216 CodeElement<?, ?> childB = b;
217 while (depthA > depthB) {
218 childA = a;
219 a = a.parent();
220 depthA--;
221 }
222
223 while (depthB > depthA) {
224 childB = b;
225 b = b.parent();
226 depthB--;
227 }
228
229 while (a != b) {
230 childA = a;
231 a = a.parent();
232 childB = b;
233 b = b.parent();
234 }
235
236 if (a == null) {
237 // No common ancestor, a and b are not in the same code model
238 throw new IllegalArgumentException("Comparing code elements in different code models");
239 } else if (a == childA) {
240 // a is an ancestor of b
241 return -1;
242 } else if (a == childB) {
243 // b is an ancestor of a
244 return 1;
245 } else {
246 // a and b share a common ancestor
247 List<?> children = a.children();
248 return Integer.compare(children.indexOf(childA), children.indexOf(childB));
249 }
250 }
251
252 private static int getDepth(CodeElement<?, ?> a) {
253 int depth = 0;
254 while (a.parent() != null) {
255 a = a.parent();
256 depth++;
257 }
258 return depth;
259 }
260 }