1 /*
  2  *  Copyright (c) 2019, 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.internal.foreign;
 27 
 28 import jdk.incubator.foreign.MemoryHandles;
 29 import jdk.incubator.foreign.MemoryLayout;
 30 import jdk.incubator.foreign.MemorySegment;
 31 import jdk.internal.access.foreign.MemorySegmentProxy;
 32 
 33 import jdk.incubator.foreign.GroupLayout;
 34 import jdk.incubator.foreign.SequenceLayout;
 35 import jdk.incubator.foreign.ValueLayout;
 36 
 37 import java.lang.invoke.MethodHandle;
 38 import java.lang.invoke.MethodHandles;
 39 import java.lang.invoke.MethodType;
 40 import java.lang.invoke.VarHandle;
 41 import java.util.ArrayDeque;
 42 import java.util.ArrayList;
 43 import java.util.Deque;
 44 import java.util.List;
 45 import java.util.function.ToLongFunction;
 46 import java.util.function.UnaryOperator;
 47 
 48 /**
 49  * This class provide support for constructing layout paths; that is, starting from a root path (see {@link #rootPath(MemoryLayout, ToLongFunction)},
 50  * a path can be constructed by selecting layout elements using the selector methods provided by this class
 51  * (see {@link #sequenceElement()}, {@link #sequenceElement(long)}, {@link #sequenceElement(long, long)}, {@link #groupElement(String)}).
 52  * Once a path has been fully constructed, clients can ask for the offset associated with the layout element selected
 53  * by the path (see {@link #offset}), or obtain a memory access var handle to access the selected layout element
 54  * given an address pointing to a segment associated with the root layout (see {@link #dereferenceHandle()}).
 55  */
 56 public class LayoutPath {
 57 
 58     private static final MethodHandle ADD_STRIDE;
 59     private static final MethodHandle MH_ADD_SCALED_OFFSET;
 60     private static final MethodHandle MH_SLICE;
 61 
 62     private static final int UNSPECIFIED_ELEM_INDEX = -1;
 63 
 64     static {
 65         try {
 66             MethodHandles.Lookup lookup = MethodHandles.lookup();
 67             ADD_STRIDE = lookup.findStatic(LayoutPath.class, "addStride",
 68                     MethodType.methodType(long.class, MemorySegment.class, long.class, long.class, long.class));
 69             MH_ADD_SCALED_OFFSET = lookup.findStatic(LayoutPath.class, "addScaledOffset",
 70                     MethodType.methodType(long.class, long.class, long.class, long.class));
 71             MH_SLICE = lookup.findVirtual(MemorySegment.class, "asSlice",
 72                     MethodType.methodType(MemorySegment.class, long.class, long.class));
 73         } catch (Throwable ex) {
 74             throw new ExceptionInInitializerError(ex);
 75         }
 76     }
 77 
 78     private final MemoryLayout layout;
 79     private final long offset;
 80     private final LayoutPath enclosing;
 81     private final long[] strides;
 82     private final long elementIndex;
 83     private final ToLongFunction<MemoryLayout> sizeFunc;
 84 
 85     private LayoutPath(MemoryLayout layout, long offset, long[] strides, long elementIndex, LayoutPath enclosing, ToLongFunction<MemoryLayout> sizeFunc) {
 86         this.layout = layout;
 87         this.offset = offset;
 88         this.strides = strides;
 89         this.enclosing = enclosing;
 90         this.elementIndex = elementIndex;
 91         this.sizeFunc = sizeFunc;
 92     }
 93 
 94     // Layout path selector methods
 95 
 96     public LayoutPath sequenceElement() {
 97         check(SequenceLayout.class, "attempting to select a sequence element from a non-sequence layout");
 98         SequenceLayout seq = (SequenceLayout)layout;
 99         MemoryLayout elem = seq.elementLayout();
100         return LayoutPath.nestedPath(elem, offset, addStride(sizeFunc.applyAsLong(elem)), UNSPECIFIED_ELEM_INDEX, this);
101     }
102 
103     public LayoutPath sequenceElement(long start, long step) {
104         check(SequenceLayout.class, "attempting to select a sequence element from a non-sequence layout");
105         SequenceLayout seq = (SequenceLayout)layout;
106         checkSequenceBounds(seq, start);
107         MemoryLayout elem = seq.elementLayout();
108         long elemSize = sizeFunc.applyAsLong(elem);
109         return LayoutPath.nestedPath(elem, offset + (start * elemSize), addStride(elemSize * step),
110                 UNSPECIFIED_ELEM_INDEX, this);
111     }
112 
113     public LayoutPath sequenceElement(long index) {
114         check(SequenceLayout.class, "attempting to select a sequence element from a non-sequence layout");
115         SequenceLayout seq = (SequenceLayout)layout;
116         checkSequenceBounds(seq, index);
117         long elemOffset = 0;
118         if (index > 0) {
119             //if index == 0, we do not depend on sequence element size, so skip
120             long elemSize = sizeFunc.applyAsLong(seq.elementLayout());
121             elemOffset = elemSize * index;
122         }
123         return LayoutPath.nestedPath(seq.elementLayout(), offset + elemOffset, strides, index, this);
124     }
125 
126     public LayoutPath groupElement(String name) {
127         check(GroupLayout.class, "attempting to select a group element from a non-group layout");
128         GroupLayout g = (GroupLayout)layout;
129         long offset = 0;
130         MemoryLayout elem = null;
131         int index = -1;
132         for (int i = 0; i < g.memberLayouts().size(); i++) {
133             MemoryLayout l = g.memberLayouts().get(i);
134             if (l.name().isPresent() &&
135                 l.name().get().equals(name)) {
136                 elem = l;
137                 index = i;
138                 break;
139             } else if (g.isStruct()) {
140                 offset += sizeFunc.applyAsLong(l);
141             }
142         }
143         if (elem == null) {
144             throw badLayoutPath("cannot resolve '" + name + "' in layout " + layout);
145         }
146         return LayoutPath.nestedPath(elem, this.offset + offset, strides, index, this);
147     }
148 
149     // Layout path projections
150 
151     public long offset() {
152         return offset;
153     }
154 
155     public VarHandle dereferenceHandle() {
156         if (!(layout instanceof ValueLayout)) {
157             throw new IllegalArgumentException("Path does not select a value layout");
158         }
159         checkAlignment(this);
160 
161         Class<?> carrier = ((ValueLayout)layout).carrier();
162 
163         List<Class<?>> expectedCoordinates = new ArrayList<>();
164         Deque<Integer> perms = new ArrayDeque<>();
165         perms.addFirst(0);
166         expectedCoordinates.add(MemorySegment.class);
167 
168         VarHandle handle = Utils.makeMemoryAccessVarHandle(carrier, true, layout.byteAlignment() - 1,
169                 ((ValueLayout)layout).order());
170 
171         for (int i = 0 ; i < strides.length ; i++) {
172             expectedCoordinates.add(long.class);
173             perms.addFirst(0);
174             perms.addLast(i + 1);
175             //add stride
176             handle = MemoryHandles.collectCoordinates(handle, 1 + i,
177                     MethodHandles.insertArguments(ADD_STRIDE, 1, Utils.bitsToBytesOrThrow(strides[strides.length - 1 - i], IllegalStateException::new))); // MS, long, MS_n, long_n, long
178         }
179         //add offset
180         handle = MemoryHandles.insertCoordinates(handle, 1 + strides.length, Utils.bitsToBytesOrThrow(offset, IllegalStateException::new));
181 
182         if (strides.length > 0) {
183             // remove duplicate MS args
184             handle = MemoryHandles.permuteCoordinates(handle, expectedCoordinates, perms.stream().mapToInt(i -> i).toArray());
185         }
186         return handle;
187     }
188 
189     private static long addScaledOffset(long base, long index, long stride) {
190         return base + (stride * index);
191     }
192 
193     public MethodHandle offsetHandle() {
194         MethodHandle mh = MethodHandles.identity(long.class);
195         for (int i = strides.length - 1; i >=0; i--) {
196             MethodHandle collector = MethodHandles.insertArguments(MH_ADD_SCALED_OFFSET, 2, strides[i]);
197             // (J, ...) -> J to (J, J, ...) -> J
198             // i.e. new coord is prefixed. Last coord will correspond to innermost layout
199             mh = MethodHandles.collectArguments(mh, 0, collector);
200         }
201         mh = MethodHandles.insertArguments(mh, 0, offset);
202         return mh;
203     }
204 
205     public MethodHandle sliceHandle() {
206         if (strides.length == 0) {
207             // trigger checks eagerly
208             Utils.bitsToBytesOrThrow(offset, Utils.bitsToBytesThrowOffset);
209         }
210 
211         MethodHandle offsetHandle = offsetHandle(); // bit offset
212         offsetHandle = MethodHandles.filterReturnValue(offsetHandle, Utils.MH_bitsToBytesOrThrowForOffset); // byte offset
213 
214         MethodHandle sliceHandle = MH_SLICE; // (MS, long, long) -> MS
215         sliceHandle = MethodHandles.insertArguments(sliceHandle, 2, layout.byteSize()); // (MS, long) -> MS
216         sliceHandle = MethodHandles.collectArguments(sliceHandle, 1, offsetHandle); // (MS, ...) -> MS
217 
218         return sliceHandle;
219     }
220 
221     public MemoryLayout layout() {
222         return layout;
223     }
224 
225     public MemoryLayout map(UnaryOperator<MemoryLayout> op) {
226         MemoryLayout newLayout = op.apply(layout);
227         if (enclosing == null) {
228             return newLayout;
229         } else if (enclosing.layout instanceof SequenceLayout seq) {
230             if (seq.elementCount().isPresent()) {
231                 return enclosing.map(l -> dup(l, MemoryLayout.sequenceLayout(seq.elementCount().getAsLong(), newLayout)));
232             } else {
233                 return enclosing.map(l -> dup(l, MemoryLayout.sequenceLayout(newLayout)));
234             }
235         } else if (enclosing.layout instanceof GroupLayout g) {
236             List<MemoryLayout> newElements = new ArrayList<>(g.memberLayouts());
237             //if we selected a layout in a group we must have a valid index
238             newElements.set((int)elementIndex, newLayout);
239             if (g.isUnion()) {
240                 return enclosing.map(l -> dup(l, MemoryLayout.unionLayout(newElements.toArray(new MemoryLayout[0]))));
241             } else {
242                 return enclosing.map(l -> dup(l, MemoryLayout.structLayout(newElements.toArray(new MemoryLayout[0]))));
243             }
244         } else {
245             return newLayout;
246         }
247     }
248 
249     private MemoryLayout dup(MemoryLayout oldLayout, MemoryLayout newLayout) {
250         newLayout = newLayout.withBitAlignment(oldLayout.bitAlignment());
251         if (oldLayout.name().isPresent()) {
252             newLayout.withName(oldLayout.name().get());
253         }
254         return newLayout;
255     }
256 
257     // Layout path construction
258 
259     public static LayoutPath rootPath(MemoryLayout layout, ToLongFunction<MemoryLayout> sizeFunc) {
260         return new LayoutPath(layout, 0L, EMPTY_STRIDES, -1, null, sizeFunc);
261     }
262 
263     private static LayoutPath nestedPath(MemoryLayout layout, long offset, long[] strides, long elementIndex, LayoutPath encl) {
264         return new LayoutPath(layout, offset, strides, elementIndex, encl, encl.sizeFunc);
265     }
266 
267     // Helper methods
268 
269     private void check(Class<?> layoutClass, String msg) {
270         if (!layoutClass.isAssignableFrom(layout.getClass())) {
271             throw badLayoutPath(msg);
272         }
273     }
274 
275     private void checkSequenceBounds(SequenceLayout seq, long index) {
276         if (seq.elementCount().isPresent() && index >= seq.elementCount().getAsLong()) {
277             throw badLayoutPath(String.format("Sequence index out of bound; found: %d, size: %d", index, seq.elementCount().getAsLong()));
278         }
279     }
280 
281     private static IllegalArgumentException badLayoutPath(String cause) {
282         return new IllegalArgumentException("Bad layout path: " + cause);
283     }
284 
285     private static void checkAlignment(LayoutPath path) {
286         MemoryLayout layout = path.layout;
287         long alignment = layout.bitAlignment();
288         if (path.offset % alignment != 0) {
289             throw new UnsupportedOperationException("Invalid alignment requirements for layout " + layout);
290         }
291         for (long stride : path.strides) {
292             if (stride % alignment != 0) {
293                 throw new UnsupportedOperationException("Alignment requirements for layout " + layout + " do not match stride " + stride);
294             }
295         }
296         LayoutPath encl = path.enclosing;
297         if (encl != null) {
298             if (encl.layout.bitAlignment() < alignment) {
299                 throw new UnsupportedOperationException("Alignment requirements for layout " + layout + " do not match those for enclosing layout " + encl.layout);
300             }
301             checkAlignment(encl);
302         }
303     }
304 
305     private long[] addStride(long stride) {
306         long[] newStrides = new long[strides.length + 1];
307         System.arraycopy(strides, 0, newStrides, 0, strides.length);
308         newStrides[strides.length] = stride;
309         return newStrides;
310     }
311 
312     private static final long[] EMPTY_STRIDES = new long[0];
313 
314     /**
315      * This class provides an immutable implementation for the {@code PathElement} interface. A path element implementation
316      * is simply a pointer to one of the selector methods provided by the {@code LayoutPath} class.
317      */
318     public static final class PathElementImpl implements MemoryLayout.PathElement, UnaryOperator<LayoutPath> {
319 
320         public enum PathKind {
321             SEQUENCE_ELEMENT("unbound sequence element"),
322             SEQUENCE_ELEMENT_INDEX("bound sequence element"),
323             SEQUENCE_RANGE("sequence range"),
324             GROUP_ELEMENT("group element");
325 
326             final String description;
327 
328             PathKind(String description) {
329                 this.description = description;
330             }
331 
332             public String description() {
333                 return description;
334             }
335         }
336 
337         final PathKind kind;
338         final UnaryOperator<LayoutPath> pathOp;
339 
340         public PathElementImpl(PathKind kind, UnaryOperator<LayoutPath> pathOp) {
341             this.kind = kind;
342             this.pathOp = pathOp;
343         }
344 
345         @Override
346         public LayoutPath apply(LayoutPath layoutPath) {
347             return pathOp.apply(layoutPath);
348         }
349 
350         public PathKind kind() {
351             return kind;
352         }
353     }
354 
355     private static long addStride(MemorySegment segment, long stride, long base, long index) {
356         return MemorySegmentProxy.addOffsets(base,
357                     MemorySegmentProxy.multiplyOffsets(stride, index, ((MemorySegmentProxy)segment)), (MemorySegmentProxy)segment);
358     }
359 }