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.
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 *
44 * @param <E> the code element type
45 * @param <C> the child code element type.
46 * @sealedGraph
47 */
48 // @@@ E may not be needed
49 public sealed interface CodeElement<
50 E extends CodeElement<E, C>,
51 C extends CodeElement<C, ?>>
52 extends CodeItem
53 permits Body, Block, Op {
54
55 /**
56 * {@return a stream of code elements sorted topologically in pre-order traversal.}
57 */
58 default Stream<CodeElement<?, ?>> elements() {
59 return Stream.of(this).gather(() -> (_, e, downstream) -> traversePreOrder(e, downstream));
60 }
61
62 private static boolean traversePreOrder(CodeElement<?, ?> e, Gatherer.Downstream<? super CodeElement<?, ?>> d) {
63 if (!d.push(e)) {
64 return false;
65 }
66 for (CodeElement<?, ?> c : e.children()) {
67 if (!traversePreOrder(c, d)) {
68 return false;
69 }
70 }
71 return true;
72 }
73
74 /**
75 * Returns the parent element, otherwise {@code null} if this element is an operation that has no parent block.
76 *
77 * @return the parent code element.
78 * @throws IllegalStateException if an unbuilt block is encountered.
79 */
80 CodeElement<?, E> parent();
81
82 // Nearest ancestors
83
84 /**
85 * Finds the nearest ancestor operation, otherwise {@code null} if there is no nearest ancestor.
86 *
87 * @return the nearest ancestor operation.
88 * @throws IllegalStateException if an unbuilt block is encountered.
89 */
90 default Op ancestorOp() {
91 return switch (this) {
92 // block -> body -> op~
93 case Block block -> block.parent().parent();
94 // body -> op~
95 case Body body -> body.parent();
96 // op -> block? -> body -> op~
97 case Op op -> {
98 // Throws ISE if op is not bound
99 Block parent = op.parent();
100 yield parent == null ? null : parent.parent().parent();
101 }
102 };
103 }
104
105 /**
106 * Finds the nearest ancestor body, otherwise {@code null} if there is no nearest ancestor.
107 *
108 * @return the nearest ancestor body.
109 * @throws IllegalStateException if an unbuilt block is encountered.
110 */
111 default Body ancestorBody() {
112 return switch (this) {
113 // block -> body
114 case Block block -> block.parent();
115 // body -> op~ -> block? -> body
116 case Body body -> {
117 // Throws ISE if block is not built
118 Block ancestor = body.parent().parent();
119 yield ancestor == null ? null : ancestor.parent();
120 }
121 // op~ -> block? -> body
122 case Op op -> {
123 // Throws ISE if op is not bound
124 Block parent = op.parent();
125 yield parent == null ? null : parent.parent();
126 }
127 };
128 }
129
130 /**
131 * Finds the nearest ancestor block, otherwise {@code null} if there is no nearest ancestor.
132 *
133 * @return the nearest ancestor block.
134 * @throws IllegalStateException if an unbuilt block is encountered.
135 */
136 default Block ancestorBlock() {
137 return switch (this) {
138 // block -> body -> op~ -> block?
139 // Throws ISE if op is not bound
140 case Block block -> block.parent().parent().parent();
141 // body -> op~ -> block?
142 // Throws ISE if op is not bound
143 case Body body -> body.parent().parent();
144 // op~ -> block?
145 // Throws ISE if op is not bound
146 case Op op -> op.parent();
147 };
148 }
149
150 /**
151 * Returns true if this element is an ancestor of the descendant element.
152 *
153 * @param descendant the descendant element.
154 * @return true if this element is an ancestor of the descendant element.
155 * @throws IllegalStateException if an unbuilt block is encountered.
156 */
157 default boolean isAncestorOf(CodeElement<?, ?> descendant) {
158 Objects.requireNonNull(descendant);
159
160 CodeElement<?, ?> e = descendant.parent();
161 while (e != null && e != this) {
162 e = e.parent();
163 }
164 return e != null;
165 }
166
167 /**
168 * Returns the child code elements, as an unmodifiable list.
169 *
170 * @return the child code elements
171 */
172 List<C> children();
173
174 /**
175 * Compares two code elements by comparing their pre-order traversal positions in the code model.
176 * <p>
177 * The pre-order traversal position of a code element, {@code e} say, is equivalent to result of
178 * the expression {@code root.elements().toList().indexOf(e)}, where {@code root} is the root
179 * code element of the code model containing {@code e}.
180 *
181 * @param a the first code element to compare
182 * @param b the second code element to compare
183 * @return the value {@code 0} if {@code a == b}; {@code -1} if {@code a}'s pre-order traversal position
184 * is less than {@code b}'s position; and {@code 1} if {@code a}'s pre-order traversal position
185 * is greater than {@code b}'s position
186 * @throws IllegalArgumentException if {@code a} and {@code b} are not present in the same code model
187 * @throws IllegalStateException if an unbuilt block is encountered.
188 */
189 static int compare(CodeElement<?, ?> a, CodeElement<?, ?> b) {
190 if (a == b) {
191 return 0;
192 }
193
194 // Find the common ancestor of a and b and the respective children
195 int depthA = getDepth(a);
196 int depthB = getDepth(b);
197
198 CodeElement<?, ?> childA = a;
199 CodeElement<?, ?> childB = b;
200 while (depthA > depthB) {
201 childA = a;
202 a = a.parent();
203 depthA--;
204 }
205
206 while (depthB > depthA) {
207 childB = b;
208 b = b.parent();
209 depthB--;
210 }
211
212 while (a != b) {
213 childA = a;
214 a = a.parent();
215 childB = b;
216 b = b.parent();
217 }
218
219 if (a == null) {
220 // No common ancestor, a and b are not in the same code model
221 throw new IllegalArgumentException("Comparing code elements in different code models");
222 } else if (a == childA) {
223 // a is an ancestor of b
224 return -1;
225 } else if (a == childB) {
226 // b is an ancestor of a
227 return 1;
228 } else {
229 // a and b share a common ancestor
230 List<?> children = a.children();
231 return Integer.compare(children.indexOf(childA), children.indexOf(childB));
232 }
233 }
234
235 private static int getDepth(CodeElement<?, ?> a) {
236 int depth = 0;
237 while (a.parent() != null) {
238 a = a.parent();
239 depth++;
240 }
241 return depth;
242 }
243 }