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.function.BiFunction;
31 import java.util.function.Predicate;
32 import java.util.stream.Gatherer;
33 import java.util.stream.Stream;
34
35 /**
36 * A code element, one of {@link Body body}, {@link Block block}, or {@link Op operation}.
37 * <p>
38 * A code may have a parent code element. An unbound code element is an operation, an unbound operation, that has no
39 * parent block. An unbound operation may also be considered a root operation if never bound. A code element and all its
40 * ancestors can be traversed, up to and including the unbound or root operation.
41 * <p>
42 * A code element may have child code elements, and so on. An unbound or root operation and all its descendants can be
43 * traversed, down to and including operations with no children. Bodies and blocks have at least one child element.
44 *
45 * @param <E> the code element type
46 * @param <C> the child code element type.
47 * @sealedGraph
48 */
49 // @@@ E may not be needed
50 public sealed interface CodeElement<
51 E extends CodeElement<E, C>,
52 C extends CodeElement<C, ?>>
53 extends CodeItem
54 permits Body, Block, Op {
55
56 /**
57 * {@return a stream of code elements sorted topologically in pre-order traversal.}
58 */
59 default Stream<CodeElement<?, ?>> elements() {
60 return Stream.of(Void.class).gather(() -> (_, _, downstream) -> traversePreOrder(downstream));
61 }
62
63 private boolean traversePreOrder(Gatherer.Downstream<? super CodeElement<?, ?>> v) {
64 if (!v.push(this)) {
65 return false;
66 }
67 for (C c : children()) {
68 if (!((CodeElement<?, ?>) c).traversePreOrder(v)) {
69 return false;
70 }
71 }
72 return true;
73 }
74
75 /**
76 * Traverses this code element and any descendant code elements.
77 * <p>
78 * Traversal is performed in pre-order, reporting each code element to the visitor.
79 *
80 * @param t the traversing accumulator
81 * @param v the code element visitor
82 * @param <T> accumulator type
83 * @return the traversing accumulator
84 */
85 default <T> T traverse(T t, BiFunction<T, CodeElement<?, ?>, T> v) {
86 t = v.apply(t, this);
87 for (C r : children()) {
88 t = r.traverse(t, v);
89 }
90
91 return t;
92 }
93
94 /**
95 * Creates a visiting function for bodies.
96 *
97 * @param v the body visitor
98 * @param <T> accumulator type
99 * @return the visiting function for bodies
100 */
101 static <T> BiFunction<T, CodeElement<?, ?>, T> bodyVisitor(BiFunction<T, Body, T> v) {
102 return (t, e) -> e instanceof Body f
103 ? v.apply(t, f)
104 : t;
105 }
106
107 /**
108 * Creates a visiting function for blocks.
109 *
110 * @param v the block visitor
111 * @param <T> accumulator type
112 * @return the visiting function for blocks
113 */
114 static <T> BiFunction<T, CodeElement<?, ?>, T> blockVisitor(BiFunction<T, Block, T> v) {
115 return (t, e) -> e instanceof Block f
116 ? v.apply(t, f)
117 : t;
118 }
119
120 /**
121 * Creates a visiting function for operations.
122 *
123 * @param v the operation visitor
124 * @param <T> accumulator type
125 * @return the visiting function for operations
126 */
127 static <T> BiFunction<T, CodeElement<?, ?>, T> opVisitor(BiFunction<T, Op, T> v) {
128 return (t, e) -> e instanceof Op f
129 ? v.apply(t, f)
130 : t;
131 }
132
133 /**
134 * Returns the parent element, otherwise {@code null}
135 * if there is no parent.
136 *
137 * @return the parent code element.
138 * @throws IllegalStateException if this element is an operation whose parent block is unbuilt.
139 */
140 CodeElement<?, E> parent();
141
142 // Nearest ancestors
143
144 /**
145 * Finds the nearest ancestor operation, otherwise {@code null}
146 * if there is no nearest ancestor.
147 *
148 * @return the nearest ancestor operation.
149 * @throws IllegalStateException if an operation with unbuilt parent block is encountered.
150 */
151 default Op ancestorOp() {
152 return switch (this) {
153 // block -> body -> op~
154 case Block block -> block.parent().parent();
155 // body -> op~
156 case Body body -> body.parent();
157 // op -> block? -> body -> op~
158 case Op op -> {
159 // Throws ISE if op is not bound
160 Block parent = op.parent();
161 yield parent == null ? null : parent.parent().parent();
162 }
163 };
164 }
165
166 /**
167 * Finds the nearest ancestor body, otherwise {@code null}
168 * if there is no nearest ancestor.
169 *
170 * @return the nearest ancestor body.
171 * @throws IllegalStateException if an operation with unbuilt parent block is encountered.
172 */
173 default Body ancestorBody() {
174 return switch (this) {
175 // block -> body
176 case Block block -> block.parent();
177 // body -> op~ -> block? -> body
178 case Body body -> {
179 // Throws ISE if block is partially constructed
180 Block ancestor = body.parent().parent();
181 yield ancestor == null ? null : ancestor.parent();
182 }
183 // op~ -> block? -> body
184 case Op op -> {
185 // Throws ISE if op is not bound
186 Block parent = op.parent();
187 yield parent == null ? null : parent.parent();
188 }
189 };
190 }
191
192 /**
193 * Finds the nearest ancestor block, otherwise {@code null}
194 * if there is no nearest ancestor.
195 *
196 * @return the nearest ancestor block.
197 * @throws IllegalStateException if an operation with unbuilt parent block is encountered.
198 */
199 default Block ancestorBlock() {
200 return switch (this) {
201 // block -> body -> op~ -> block?
202 // Throws ISE if op is not bound
203 case Block block -> block.parent().parent().parent();
204 // body -> op~ -> block?
205 // Throws ISE if op is not bound
206 case Body body -> body.parent().parent();
207 // op~ -> block?
208 // Throws ISE if op is not bound
209 case Op op -> op.parent();
210 };
211 }
212
213 /**
214 * Returns true if this element is an ancestor of the descendant element.
215 *
216 * @param descendant the descendant element.
217 * @return true if this element is an ancestor of the descendant element.
218 */
219 default boolean isAncestorOf(CodeElement<?, ?> descendant) {
220 Objects.requireNonNull(descendant);
221
222 CodeElement<?, ?> e = descendant.parent();
223 while (e != null && e != this) {
224 e = e.parent();
225 }
226 return e != null;
227 }
228
229 /**
230 * Returns the child code elements, as an unmodifiable list.
231 *
232 * @return the child code elements
233 */
234 List<C> children();
235
236 // Siblings
237 // Left, right
238
239 // Des
240 }