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 <a href="Body.Builder.html#body-building-observability">unobservable</a> block
82 * is encountered
83 */
84 CodeElement<?, E> parent();
85
86 // Nearest ancestors
87
88 /**
89 * Finds the nearest ancestor operation, otherwise {@code null} if there is no nearest ancestor.
90 *
91 * @return the nearest ancestor operation.
92 * @throws IllegalStateException if an <a href="Body.Builder.html#body-building-observability">unobservable</a> block
93 * is encountered
94 */
95 default Op ancestorOp() {
96 return switch (this) {
97 // block -> body -> op~
98 case Block block -> block.parent().parent();
99 // body -> op~
100 case Body body -> body.parent();
101 // op -> block? -> body -> op~
102 case Op op -> {
103 // Throws ISE if an unobservable block is encountered
104 Block parent = op.parent();
105 yield parent == null ? null : parent.parent().parent();
106 }
107 };
108 }
109
110 /**
111 * Finds the nearest ancestor body, otherwise {@code null} if there is no nearest ancestor.
112 *
113 * @return the nearest ancestor body.
114 * @throws IllegalStateException if an <a href="Body.Builder.html#body-building-observability">unobservable</a> block
115 * is encountered
116 */
117 default Body ancestorBody() {
118 return switch (this) {
119 // block -> body
120 case Block block -> block.parent();
121 // body -> op~ -> block? -> body
122 case Body body -> {
123 // Throws ISE if an unobservable block is encountered
124 Block ancestor = body.parent().parent();
125 yield ancestor == null ? null : ancestor.parent();
126 }
127 // op~ -> block? -> body
128 case Op op -> {
129 // Throws ISE if an unobservable block is encountered
130 Block parent = op.parent();
131 yield parent == null ? null : parent.parent();
132 }
133 };
134 }
135
136 /**
137 * Finds the nearest ancestor block, otherwise {@code null} if there is no nearest ancestor.
138 *
139 * @return the nearest ancestor block.
140 * @throws IllegalStateException if an <a href="Body.Builder.html#body-building-observability">unobservable</a> block
141 * is encountered
142 */
143 default Block ancestorBlock() {
144 return switch (this) {
145 // block -> body -> op~ -> block?
146 // Throws ISE if an unobservable block is encountered
147 case Block block -> block.parent().parent().parent();
148 // body -> op~ -> block?
149 // Throws ISE if an unobservable block is encountered
150 case Body body -> body.parent().parent();
151 // op~ -> block?
152 // Throws ISE if an unobservable block is encountered
153 case Op op -> op.parent();
154 };
155 }
156
157 /**
158 * Returns true if this element is an ancestor of the descendant element.
159 *
160 * @param descendant the descendant element.
161 * @return true if this element is an ancestor of the descendant element.
162 * @see #isDescendantOf
163 */
164 default boolean isAncestorOf(CodeElement<?, ?> descendant) {
165 Objects.requireNonNull(descendant);
166
167 CodeElement<?, ?> e = descendant.parent();
168 while (e != null && e != this) {
169 e = e.parent();
170 }
171 return e != null;
172 }
173
174 /**
175 * Returns true if this element is a descendant of the ancestor element.
176 *
177 * @param ancestor the ancestor element.
178 * @return true if this element is a descendant of the ancestor element.
179 * @see #isAncestorOf
180 */
181 default boolean isDescendantOf(CodeElement<?, ?> ancestor) {
182 Objects.requireNonNull(ancestor);
183 return ancestor.isAncestorOf(this);
184 }
185
186 /**
187 * Returns the child code elements, as an unmodifiable list.
188 *
189 * @return the child code elements
190 */
191 List<C> children();
192
193 /**
194 * Compares two code elements by comparing their pre-order traversal positions in the code model.
195 * <p>
196 * The pre-order traversal position of a code element, {@code e} say, is equivalent to result of
197 * the expression {@code root.elements().toList().indexOf(e)}, where {@code root} is the root
198 * code element of the code model containing {@code e}.
199 *
200 * @param a the first code element to compare
201 * @param b the second code element to compare
202 * @return the value {@code 0} if {@code a == b}; {@code -1} if {@code a}'s pre-order traversal position
203 * is less than {@code b}'s position; and {@code 1} if {@code a}'s pre-order traversal position
204 * is greater than {@code b}'s position
205 * @throws IllegalArgumentException if {@code a} and {@code b} are not present in the same code model
206 */
207 static int compare(CodeElement<?, ?> a, CodeElement<?, ?> b) {
208 if (a == b) {
209 return 0;
210 }
211
212 // Find the common ancestor of a and b and the respective children
213 int depthA = getDepth(a);
214 int depthB = getDepth(b);
215
216 CodeElement<?, ?> childA = a;
217 CodeElement<?, ?> childB = b;
218 while (depthA > depthB) {
219 childA = a;
220 a = a.parent();
221 depthA--;
222 }
223
224 while (depthB > depthA) {
225 childB = b;
226 b = b.parent();
227 depthB--;
228 }
229
230 while (a != b) {
231 childA = a;
232 a = a.parent();
233 childB = b;
234 b = b.parent();
235 }
236
237 if (a == null) {
238 // No common ancestor, a and b are not in the same code model
239 throw new IllegalArgumentException("Comparing code elements in different code models");
240 } else if (a == childA) {
241 // a is an ancestor of b
242 return -1;
243 } else if (a == childB) {
244 // b is an ancestor of a
245 return 1;
246 } else {
247 // a and b share a common ancestor
248 List<?> children = a.children();
249 return Integer.compare(children.indexOf(childA), children.indexOf(childB));
250 }
251 }
252
253 private static int getDepth(CodeElement<?, ?> a) {
254 int depth = 0;
255 while (a.parent() != null) {
256 a = a.parent();
257 depth++;
258 }
259 return depth;
260 }
261 }