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 }