1 /*
2  * Copyright (c) 2014, 2017, 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 java.lang.invoke;
27
28 import sun.invoke.util.Wrapper;
29
30 import java.lang.ref.SoftReference;
31 import java.util.Arrays;
32 import java.util.Collections;
33 import java.util.concurrent.ConcurrentHashMap;
34
35 import static java.lang.invoke.LambdaForm.*;
36 import static java.lang.invoke.LambdaForm.BasicType.*;
37 import static java.lang.invoke.MethodHandleImpl.Intrinsic;
38 import static java.lang.invoke.MethodHandleImpl.NF_loop;
39
40 /** Transforms on LFs.
41  *  A lambda-form editor can derive new LFs from its base LF.
42  *  The editor can cache derived LFs, which simplifies the reuse of their underlying bytecodes.
43  *  To support this caching, a LF has an optional pointer to its editor.
44  */
45 class LambdaFormEditor {
46     final LambdaForm lambdaForm;
47
48     private LambdaFormEditor(LambdaForm lambdaForm) {
49         this.lambdaForm = lambdaForm;
50     }
51
52     // Factory method.
53     static LambdaFormEditor lambdaFormEditor(LambdaForm lambdaForm) {
54         // TO DO:  Consider placing intern logic here, to cut down on duplication.
55         // lambdaForm = findPreexistingEquivalent(lambdaForm)
56
57         // Always use uncustomized version for editing.
58         // It helps caching and customized LambdaForms reuse transformCache field to keep a link to uncustomized version.
59         return new LambdaFormEditor(lambdaForm.uncustomize());
60     }
61
62     /** A description of a cached transform, possibly associated with the result of the transform.
63      *  The logical content is a sequence of byte values, starting with a kind value.
64      *  The sequence is unterminated, ending with an indefinite number of zero bytes.
65      *  Sequences that are simple (short enough and with small enough values) pack into a 64-bit long.
66      */
67     private static final class Transform extends SoftReference<LambdaForm> {
68         final long packedBytes;
69         final byte[] fullBytes;
70
71         // maybe add more for guard with test, catch exception, pointwise type conversions
72         private static final byte
73                 BIND_ARG = 1,
74                 ADD_ARG = 2,
75                 DUP_ARG = 3,
76                 SPREAD_ARGS = 4,
77                 FILTER_ARG = 5,
78                 FILTER_RETURN = 6,
79                 FILTER_RETURN_TO_ZERO = 7,
80                 COLLECT_ARGS = 8,
81                 COLLECT_ARGS_TO_VOID = 9,
82                 COLLECT_ARGS_TO_ARRAY = 10,
83                 FOLD_ARGS = 11,
84                 FOLD_ARGS_TO_VOID = 12,
85                 PERMUTE_ARGS = 13,
86                 LOCAL_TYPES = 14,
87                 FOLD_SELECT_ARGS = 15,
88                 FOLD_SELECT_ARGS_TO_VOID = 16;
89
90         private static final boolean STRESS_TEST = false; // turn on to disable most packing
91         private static final int
92                 PACKED_BYTE_SIZE = (STRESS_TEST ? 2 : 4),
93                 PACKED_BYTE_MASK = (1 << PACKED_BYTE_SIZE) - 1,
94                 PACKED_BYTE_MAX_LENGTH = (STRESS_TEST ? 3 : 64 / PACKED_BYTE_SIZE);
95
96         private static long packedBytes(byte[] bytes) {
97             if (bytes.length > PACKED_BYTE_MAX_LENGTH)  return 0;
98             long pb = 0;
99             int bitset = 0;
100             for (int i = 0; i < bytes.length; i++) {
101                 int b = bytes[i] & 0xFF;
102                 bitset |= b;
103                 pb |= (long)b << (i * PACKED_BYTE_SIZE);
104             }
105             if (!inRange(bitset))
106                 return 0;
107             return pb;
108         }
109         private static long packedBytes(int b0, int b1) {
110             assert(inRange(b0 | b1));
111             return (  (b0 << 0*PACKED_BYTE_SIZE)
112                     | (b1 << 1*PACKED_BYTE_SIZE));
113         }
114         private static long packedBytes(int b0, int b1, int b2) {
115             assert(inRange(b0 | b1 | b2));
116             return (  (b0 << 0*PACKED_BYTE_SIZE)
117                     | (b1 << 1*PACKED_BYTE_SIZE)
118                     | (b2 << 2*PACKED_BYTE_SIZE));
119         }
120         private static long packedBytes(int b0, int b1, int b2, int b3) {
121             assert(inRange(b0 | b1 | b2 | b3));
122             return (  (b0 << 0*PACKED_BYTE_SIZE)
123                     | (b1 << 1*PACKED_BYTE_SIZE)
124                     | (b2 << 2*PACKED_BYTE_SIZE)
125                     | (b3 << 3*PACKED_BYTE_SIZE));
126         }
127         private static boolean inRange(int bitset) {
128             assert((bitset & 0xFF) == bitset);  // incoming values must fit in *unsigned* byte
129             return ((bitset & ~PACKED_BYTE_MASK) == 0);
130         }
131         private static byte[] fullBytes(int... byteValues) {
132             byte[] bytes = new byte[byteValues.length];
133             int i = 0;
134             for (int bv : byteValues) {
135                 bytes[i++] = bval(bv);
136             }
137             assert(packedBytes(bytes) == 0);
138             return bytes;
139         }
140
141         private Transform(long packedBytes, byte[] fullBytes, LambdaForm result) {
142             super(result);
143             this.packedBytes = packedBytes;
144             this.fullBytes = fullBytes;
145         }
146         private Transform(long packedBytes) {
147             this(packedBytes, null, null);
148             assert(packedBytes != 0);
149         }
150         private Transform(byte[] fullBytes) {
151             this(0, fullBytes, null);
152         }
153
154         private static byte bval(int b) {
155             assert((b & 0xFF) == b);  // incoming value must fit in *unsigned* byte
156             return (byte)b;
157         }
158         static Transform of(byte k, int b1) {
159             byte b0 = bval(k);
160             if (inRange(b0 | b1))
161                 return new Transform(packedBytes(b0, b1));
162             else
163                 return new Transform(fullBytes(b0, b1));
164         }
165         static Transform of(byte b0, int b1, int b2) {
166             if (inRange(b0 | b1 | b2))
167                 return new Transform(packedBytes(b0, b1, b2));
168             else
169                 return new Transform(fullBytes(b0, b1, b2));
170         }
171         static Transform of(byte b0, int b1, int b2, int b3) {
172             if (inRange(b0 | b1 | b2 | b3))
173                 return new Transform(packedBytes(b0, b1, b2, b3));
174             else
175                 return new Transform(fullBytes(b0, b1, b2, b3));
176         }
177         private static final byte[] NO_BYTES = {};
178         static Transform of(byte kind, int... b123) {
179             return ofBothArrays(kind, b123, NO_BYTES);
180         }
181         static Transform of(byte kind, int b1, byte[] b234) {
182             return ofBothArrays(kind, new int[]{ b1 }, b234);
183         }
184         static Transform of(byte kind, int b1, int b2, byte[] b345) {
185             return ofBothArrays(kind, new int[]{ b1, b2 }, b345);
186         }
187         private static Transform ofBothArrays(byte kind, int[] b123, byte[] b456) {
188             byte[] fullBytes = new byte[1 + b123.length + b456.length];
189             int i = 0;
190             fullBytes[i++] = bval(kind);
191             for (int bv : b123) {
192                 fullBytes[i++] = bval(bv);
193             }
194             for (byte bv : b456) {
195                 fullBytes[i++] = bv;
196             }
197             long packedBytes = packedBytes(fullBytes);
198             if (packedBytes != 0)
199                 return new Transform(packedBytes);
200             else
201                 return new Transform(fullBytes);
202         }
203
204         Transform withResult(LambdaForm result) {
205             return new Transform(this.packedBytes, this.fullBytes, result);
206         }
207
208         @Override
209         public boolean equals(Object obj) {
210             return obj instanceof Transform && equals((Transform)obj);
211         }
212         public boolean equals(Transform that) {
213             return this.packedBytes == that.packedBytes && Arrays.equals(this.fullBytes, that.fullBytes);
214         }
215         @Override
216         public int hashCode() {
217             if (packedBytes != 0) {
218                 assert(fullBytes == null);
219                 return Long.hashCode(packedBytes);
220             }
221             return Arrays.hashCode(fullBytes);
222         }
223         @Override
224         public String toString() {
225             StringBuilder buf = new StringBuilder();
226             long bits = packedBytes;
227             if (bits != 0) {
228                 buf.append("(");
229                 while (bits != 0) {
230                     buf.append(bits & PACKED_BYTE_MASK);
231                     bits >>>= PACKED_BYTE_SIZE;
232                     if (bits != 0)  buf.append(",");
233                 }
234                 buf.append(")");
235             }
236             if (fullBytes != null) {
237                 buf.append("unpacked");
238                 buf.append(Arrays.toString(fullBytes));
239             }
240             LambdaForm result = get();
241             if (result != null) {
242                 buf.append(" result=");
243                 buf.append(result);
244             }
245             return buf.toString();
246         }
247     }
248
249     /** Find a previously cached transform equivalent to the given one, and return its result. */
250     private LambdaForm getInCache(Transform key) {
251         assert(key.get() == null);
252         // The transformCache is one of null, Transform, Transform[], or ConcurrentHashMap.
253         Object c = lambdaForm.transformCache;
254         Transform k = null;
255         if (c instanceof ConcurrentHashMap) {
256             @SuppressWarnings("unchecked")
257             ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c;
258             k = m.get(key);
259         } else if (c == null) {
260             return null;
261         } else if (c instanceof Transform) {
262             // one-element cache avoids overhead of an array
263             Transform t = (Transform)c;
264             if (t.equals(key))  k = t;
265         } else {
266             Transform[] ta = (Transform[])c;
267             for (int i = 0; i < ta.length; i++) {
268                 Transform t = ta[i];
269                 if (t == null)  break;
270                 if (t.equals(key)) { k = t; break; }
271             }
272         }
273         assert(k == null || key.equals(k));
274         return (k != null) ? k.get() : null;
275     }
276
277     /** Arbitrary but reasonable limits on Transform[] size for cache. */
278     private static final int MIN_CACHE_ARRAY_SIZE = 4, MAX_CACHE_ARRAY_SIZE = 16;
279
280     /** Cache a transform with its result, and return that result.
281      *  But if an equivalent transform has already been cached, return its result instead.
282      */
283     private LambdaForm putInCache(Transform key, LambdaForm form) {
284         key = key.withResult(form);
285         for (int pass = 0; ; pass++) {
286             Object c = lambdaForm.transformCache;
287             if (c instanceof ConcurrentHashMap) {
288                 @SuppressWarnings("unchecked")
289                 ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c;
290                 Transform k = m.putIfAbsent(key, key);
291                 if (k == null) return form;
292                 LambdaForm result = k.get();
293                 if (result != null) {
294                     return result;
295                 } else {
296                     if (m.replace(key, k, key)) {
297                         return form;
298                     } else {
299                         continue;
300                     }
301                 }
302             }
303             assert(pass == 0);
304             synchronized (lambdaForm) {
305                 c = lambdaForm.transformCache;
306                 if (c instanceof ConcurrentHashMap)
307                     continue;
308                 if (c == null) {
309                     lambdaForm.transformCache = key;
310                     return form;
311                 }
312                 Transform[] ta;
313                 if (c instanceof Transform) {
314                     Transform k = (Transform)c;
315                     if (k.equals(key)) {
316                         LambdaForm result = k.get();
317                         if (result == null) {
318                             lambdaForm.transformCache = key;
319                             return form;
320                         } else {
321                             return result;
322                         }
323                     } else if (k.get() == null) { // overwrite stale entry
324                         lambdaForm.transformCache = key;
325                         return form;
326                     }
327                     // expand one-element cache to small array
328                     ta = new Transform[MIN_CACHE_ARRAY_SIZE];
329                     ta[0] = k;
330                     lambdaForm.transformCache = ta;
331                 } else {
332                     // it is already expanded
333                     ta = (Transform[])c;
334                 }
335                 int len = ta.length;
336                 int stale = -1;
337                 int i;
338                 for (i = 0; i < len; i++) {
339                     Transform k = ta[i];
340                     if (k == null) {
341                         break;
342                     }
343                     if (k.equals(key)) {
344                         LambdaForm result = k.get();
345                         if (result == null) {
346                             ta[i] = key;
347                             return form;
348                         } else {
349                             return result;
350                         }
351                     } else if (stale < 0 && k.get() == null) {
352                         stale = i; // remember 1st stale entry index
353                     }
354                 }
355                 if (i < len || stale >= 0) {
356                     // just fall through to cache update
357                 } else if (len < MAX_CACHE_ARRAY_SIZE) {
358                     len = Math.min(len * 2, MAX_CACHE_ARRAY_SIZE);
359                     ta = Arrays.copyOf(ta, len);
360                     lambdaForm.transformCache = ta;
361                 } else {
362                     ConcurrentHashMap<Transform, Transform> m = new ConcurrentHashMap<>(MAX_CACHE_ARRAY_SIZE * 2);
363                     for (Transform k : ta) {
364                         m.put(k, k);
365                     }
366                     lambdaForm.transformCache = m;
367                     // The second iteration will update for this query, concurrently.
368                     continue;
369                 }
370                 int idx = (stale >= 0) ? stale : i;
371                 ta[idx] = key;
372                 return form;
373             }
374         }
375     }
376
377     private LambdaFormBuffer buffer() {
378         return new LambdaFormBuffer(lambdaForm);
379     }
380
381     /// Editing methods for method handles.  These need to have fast paths.
382
383     private BoundMethodHandle.SpeciesData oldSpeciesData() {
384         return BoundMethodHandle.speciesDataFor(lambdaForm);
385     }
386
387     private BoundMethodHandle.SpeciesData newSpeciesData(BasicType type) {
388         return oldSpeciesData().extendWith((byte) type.ordinal());
389     }
390
391     BoundMethodHandle bindArgumentL(BoundMethodHandle mh, int pos, Object value) {
392         assert(mh.speciesData() == oldSpeciesData());
393         BasicType bt = L_TYPE;
394         MethodType type2 = bindArgumentType(mh, pos, bt);
395         LambdaForm form2 = bindArgumentForm(1+pos);
396         return mh.copyWithExtendL(type2, form2, value);
397     }
398     BoundMethodHandle bindArgumentI(BoundMethodHandle mh, int pos, int value) {
399         assert(mh.speciesData() == oldSpeciesData());
400         BasicType bt = I_TYPE;
401         MethodType type2 = bindArgumentType(mh, pos, bt);
402         LambdaForm form2 = bindArgumentForm(1+pos);
403         return mh.copyWithExtendI(type2, form2, value);
404     }
405
406     BoundMethodHandle bindArgumentJ(BoundMethodHandle mh, int pos, long value) {
407         assert(mh.speciesData() == oldSpeciesData());
408         BasicType bt = J_TYPE;
409         MethodType type2 = bindArgumentType(mh, pos, bt);
410         LambdaForm form2 = bindArgumentForm(1+pos);
411         return mh.copyWithExtendJ(type2, form2, value);
412     }
413
414     BoundMethodHandle bindArgumentF(BoundMethodHandle mh, int pos, float value) {
415         assert(mh.speciesData() == oldSpeciesData());
416         BasicType bt = F_TYPE;
417         MethodType type2 = bindArgumentType(mh, pos, bt);
418         LambdaForm form2 = bindArgumentForm(1+pos);
419         return mh.copyWithExtendF(type2, form2, value);
420     }
421
422     BoundMethodHandle bindArgumentD(BoundMethodHandle mh, int pos, double value) {
423         assert(mh.speciesData() == oldSpeciesData());
424         BasicType bt = D_TYPE;
425         MethodType type2 = bindArgumentType(mh, pos, bt);
426         LambdaForm form2 = bindArgumentForm(1+pos);
427         return mh.copyWithExtendD(type2, form2, value);
428     }
429
430     private MethodType bindArgumentType(BoundMethodHandle mh, int pos, BasicType bt) {
431         assert(mh.form.uncustomize() == lambdaForm);
432         assert(mh.form.names[1+pos].type == bt);
433         assert(BasicType.basicType(mh.type().parameterType(pos)) == bt);
434         return mh.type().dropParameterTypes(pos, pos+1);
435     }
436
437     /// Editing methods for lambda forms.
438     // Each editing method can (potentially) cache the edited LF so that it can be reused later.
439
440     LambdaForm bindArgumentForm(int pos) {
441         Transform key = Transform.of(Transform.BIND_ARG, pos);
442         LambdaForm form = getInCache(key);
443         if (form != null) {
444             assert(form.parameterConstraint(0) == newSpeciesData(lambdaForm.parameterType(pos)));
445             return form;
446         }
447         LambdaFormBuffer buf = buffer();
448         buf.startEdit();
449
450         BoundMethodHandle.SpeciesData oldData = oldSpeciesData();
451         BoundMethodHandle.SpeciesData newData = newSpeciesData(lambdaForm.parameterType(pos));
452         Name oldBaseAddress = lambdaForm.parameter(0);  // BMH holding the values
453         Name newBaseAddress;
454         NamedFunction getter = newData.getterFunction(oldData.fieldCount());
455
456         if (pos != 0) {
457             // The newly created LF will run with a different BMH.
458             // Switch over any pre-existing BMH field references to the new BMH class.
459             buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress);
460             newBaseAddress = oldBaseAddress.withConstraint(newData);
461             buf.renameParameter(0, newBaseAddress);
462             buf.replaceParameterByNewExpression(pos, new Name(getter, newBaseAddress));
463         } else {
464             // cannot bind the MH arg itself, unless oldData is empty
465             assert(oldData == BoundMethodHandle.SPECIALIZER.topSpecies());
466             newBaseAddress = new Name(L_TYPE).withConstraint(newData);
467             buf.replaceParameterByNewExpression(0, new Name(getter, newBaseAddress));
468             buf.insertParameter(0, newBaseAddress);
469         }
470
471         form = buf.endEdit();
472         return putInCache(key, form);
473     }
474
475     LambdaForm addArgumentForm(int pos, BasicType type) {
476         Transform key = Transform.of(Transform.ADD_ARG, pos, type.ordinal());
477         LambdaForm form = getInCache(key);
478         if (form != null) {
479             assert(form.arity == lambdaForm.arity+1);
480             assert(form.parameterType(pos) == type);
481             return form;
482         }
483         LambdaFormBuffer buf = buffer();
484         buf.startEdit();
485
486         buf.insertParameter(pos, new Name(type));
487
488         form = buf.endEdit();
489         return putInCache(key, form);
490     }
491
492     LambdaForm dupArgumentForm(int srcPos, int dstPos) {
493         Transform key = Transform.of(Transform.DUP_ARG, srcPos, dstPos);
494         LambdaForm form = getInCache(key);
495         if (form != null) {
496             assert(form.arity == lambdaForm.arity-1);
497             return form;
498         }
499         LambdaFormBuffer buf = buffer();
500         buf.startEdit();
501
502         assert(lambdaForm.parameter(srcPos).constraint == null);
503         assert(lambdaForm.parameter(dstPos).constraint == null);
504         buf.replaceParameterByCopy(dstPos, srcPos);
505
506         form = buf.endEdit();
507         return putInCache(key, form);
508     }
509
510     LambdaForm spreadArgumentsForm(int pos, Class<?> arrayType, int arrayLength) {
511         Class<?> elementType = arrayType.getComponentType();
512         Class<?> erasedArrayType = arrayType;
513         if (!elementType.isPrimitive())
514             erasedArrayType = Object[].class;
515         BasicType bt = basicType(elementType);
516         int elementTypeKey = bt.ordinal();
517         if (bt.basicTypeClass() != elementType) {
518             if (elementType.isPrimitive()) {
519                 elementTypeKey = TYPE_LIMIT + Wrapper.forPrimitiveType(elementType).ordinal();
520             }
521         }
522         Transform key = Transform.of(Transform.SPREAD_ARGS, pos, elementTypeKey, arrayLength);
523         LambdaForm form = getInCache(key);
524         if (form != null) {
525             assert(form.arity == lambdaForm.arity - arrayLength + 1);
526             return form;
527         }
528         LambdaFormBuffer buf = buffer();
529         buf.startEdit();
530
531         assert(pos <= MethodType.MAX_JVM_ARITY);
532         assert(pos + arrayLength <= lambdaForm.arity);
533         assert(pos > 0);  // cannot spread the MH arg itself
534
535         Name spreadParam = new Name(L_TYPE);
536         Name checkSpread = new Name(MethodHandleImpl.getFunction(MethodHandleImpl.NF_checkSpreadArgument),
537                 spreadParam, arrayLength);
538
539         // insert the new expressions
540         int exprPos = lambdaForm.arity();
541         buf.insertExpression(exprPos++, checkSpread);
542         // adjust the arguments
543         MethodHandle aload = MethodHandles.arrayElementGetter(erasedArrayType);
544         for (int i = 0; i < arrayLength; i++) {
545             Name loadArgument = new Name(new NamedFunction(aload, Intrinsic.ARRAY_LOAD), spreadParam, i);
546             buf.insertExpression(exprPos + i, loadArgument);
547             buf.replaceParameterByCopy(pos + i, exprPos + i);
548         }
549         buf.insertParameter(pos, spreadParam);
550
551         form = buf.endEdit();
552         return putInCache(key, form);
553     }
554
555     LambdaForm collectArgumentsForm(int pos, MethodType collectorType) {
556         int collectorArity = collectorType.parameterCount();
557         boolean dropResult = (collectorType.returnType() == void.class);
558         if (collectorArity == 1 && !dropResult) {
559             return filterArgumentForm(pos, basicType(collectorType.parameterType(0)));
560         }
561         byte[] newTypes = BasicType.basicTypesOrd(collectorType.parameterArray());
562         byte kind = (dropResult
563                 ? Transform.COLLECT_ARGS_TO_VOID
564                 : Transform.COLLECT_ARGS);
565         if (dropResult && collectorArity == 0)  pos = 1;  // pure side effect
566         Transform key = Transform.of(kind, pos, collectorArity, newTypes);
567         LambdaForm form = getInCache(key);
568         if (form != null) {
569             assert(form.arity == lambdaForm.arity - (dropResult ? 0 : 1) + collectorArity);
570             return form;
571         }
572         form = makeArgumentCombinationForm(pos, collectorType, false, dropResult);
573         return putInCache(key, form);
574     }
575
576     LambdaForm collectArgumentArrayForm(int pos, MethodHandle arrayCollector) {
577         MethodType collectorType = arrayCollector.type();
578         int collectorArity = collectorType.parameterCount();
579         assert(arrayCollector.intrinsicName() == Intrinsic.NEW_ARRAY);
580         Class<?> arrayType = collectorType.returnType();
581         Class<?> elementType = arrayType.getComponentType();
582         BasicType argType = basicType(elementType);
583         int argTypeKey = argType.ordinal();
584         if (argType.basicTypeClass() != elementType) {
585             // return null if it requires more metadata (like String[].class)
586             if (!elementType.isPrimitive())
587                 return null;
588             argTypeKey = TYPE_LIMIT + Wrapper.forPrimitiveType(elementType).ordinal();
589         }
590         assert(collectorType.parameterList().equals(Collections.nCopies(collectorArity, elementType)));
591         byte kind = Transform.COLLECT_ARGS_TO_ARRAY;
592         Transform key = Transform.of(kind, pos, collectorArity, argTypeKey);
593         LambdaForm form = getInCache(key);
594         if (form != null) {
595             assert(form.arity == lambdaForm.arity - 1 + collectorArity);
596             return form;
597         }
598         LambdaFormBuffer buf = buffer();
599         buf.startEdit();
600
601         assert(pos + 1 <= lambdaForm.arity);
602         assert(pos > 0);  // cannot filter the MH arg itself
603
604         Name[] newParams = new Name[collectorArity];
605         for (int i = 0; i < collectorArity; i++) {
606             newParams[i] = new Name(pos + i, argType);
607         }
608         Name callCombiner = new Name(new NamedFunction(arrayCollector, Intrinsic.NEW_ARRAY),
609                                         (Object[]) /*...*/ newParams);
610
611         // insert the new expression
612         int exprPos = lambdaForm.arity();
613         buf.insertExpression(exprPos, callCombiner);
614
615         // insert new arguments
616         int argPos = pos + 1;  // skip result parameter
617         for (Name newParam : newParams) {
618             buf.insertParameter(argPos++, newParam);
619         }
620         assert(buf.lastIndexOf(callCombiner) == exprPos+newParams.length);
621         buf.replaceParameterByCopy(pos, exprPos+newParams.length);
622
623         form = buf.endEdit();
624         return putInCache(key, form);
625     }
626
627     LambdaForm filterArgumentForm(int pos, BasicType newType) {
628         Transform key = Transform.of(Transform.FILTER_ARG, pos, newType.ordinal());
629         LambdaForm form = getInCache(key);
630         if (form != null) {
631             assert(form.arity == lambdaForm.arity);
632             assert(form.parameterType(pos) == newType);
633             return form;
634         }
635
636         BasicType oldType = lambdaForm.parameterType(pos);
637         MethodType filterType = MethodType.methodType(oldType.basicTypeClass(),
638                 newType.basicTypeClass());
639         form = makeArgumentCombinationForm(pos, filterType, false, false);
640         return putInCache(key, form);
641     }
642
643     private LambdaForm makeArgumentCombinationForm(int pos,
644                                                    MethodType combinerType,
645                                                    boolean keepArguments, boolean dropResult) {
646         LambdaFormBuffer buf = buffer();
647         buf.startEdit();
648         int combinerArity = combinerType.parameterCount();
649         int resultArity = (dropResult ? 0 : 1);
650
651         assert(pos <= MethodType.MAX_JVM_ARITY);
652         assert(pos + resultArity + (keepArguments ? combinerArity : 0) <= lambdaForm.arity);
653         assert(pos > 0);  // cannot filter the MH arg itself
654         assert(combinerType == combinerType.basicType());
655         assert(combinerType.returnType() != void.class || dropResult);
656
657         BoundMethodHandle.SpeciesData oldData = oldSpeciesData();
658         BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE);
659
660         // The newly created LF will run with a different BMH.
661         // Switch over any pre-existing BMH field references to the new BMH class.
662         Name oldBaseAddress = lambdaForm.parameter(0);  // BMH holding the values
663         buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress);
664         Name newBaseAddress = oldBaseAddress.withConstraint(newData);
665         buf.renameParameter(0, newBaseAddress);
666
667         Name getCombiner = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress);
668         Object[] combinerArgs = new Object[1 + combinerArity];
669         combinerArgs[0] = getCombiner;
670         Name[] newParams;
671         if (keepArguments) {
672             newParams = new Name[0];
673             System.arraycopy(lambdaForm.names, pos + resultArity,
674                              combinerArgs, 1, combinerArity);
675         } else {
676             newParams = new Name[combinerArity];
677             for (int i = 0; i < newParams.length; i++) {
678                 newParams[i] = new Name(pos + i, basicType(combinerType.parameterType(i)));
679             }
680             System.arraycopy(newParams, 0,
681                              combinerArgs, 1, combinerArity);
682         }
683         Name callCombiner = new Name(combinerType, combinerArgs);
684
685         // insert the two new expressions
686         int exprPos = lambdaForm.arity();
687         buf.insertExpression(exprPos+0, getCombiner);
688         buf.insertExpression(exprPos+1, callCombiner);
689
690         // insert new arguments, if needed
691         int argPos = pos + resultArity;  // skip result parameter
692         for (Name newParam : newParams) {
693             buf.insertParameter(argPos++, newParam);
694         }
695         assert(buf.lastIndexOf(callCombiner) == exprPos+1+newParams.length);
696         if (!dropResult) {
697             buf.replaceParameterByCopy(pos, exprPos+1+newParams.length);
698         }
699
700         return buf.endEdit();
701     }
702
703     private LambdaForm makeArgumentCombinationForm(int pos,
704                                                    MethodType combinerType,
705                                                    int[] argPositions,
706                                                    boolean keepArguments,
707                                                    boolean dropResult) {
708         LambdaFormBuffer buf = buffer();
709         buf.startEdit();
710         int combinerArity = combinerType.parameterCount();
711         assert(combinerArity == argPositions.length);
712
713         int resultArity = (dropResult ? 0 : 1);
714
715         assert(pos <= lambdaForm.arity);
716         assert(pos > 0);  // cannot filter the MH arg itself
717         assert(combinerType == combinerType.basicType());
718         assert(combinerType.returnType() != void.class || dropResult);
719
720         BoundMethodHandle.SpeciesData oldData = oldSpeciesData();
721         BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE);
722
723         // The newly created LF will run with a different BMH.
724         // Switch over any pre-existing BMH field references to the new BMH class.
725         Name oldBaseAddress = lambdaForm.parameter(0);  // BMH holding the values
726         buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress);
727         Name newBaseAddress = oldBaseAddress.withConstraint(newData);
728         buf.renameParameter(0, newBaseAddress);
729
730         Name getCombiner = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress);
731         Object[] combinerArgs = new Object[1 + combinerArity];
732         combinerArgs[0] = getCombiner;
733         Name[] newParams;
734         if (keepArguments) {
735             newParams = new Name[0];
736             for (int i = 0; i < combinerArity; i++) {
737                 combinerArgs[i + 1] = lambdaForm.parameter(1 + argPositions[i]);
738                 assert (basicType(combinerType.parameterType(i)) == lambdaForm.parameterType(1 + argPositions[i]));
739             }
740         } else {
741             newParams = new Name[combinerArity];
742             for (int i = 0; i < newParams.length; i++) {
743                 newParams[i] = lambdaForm.parameter(1 + argPositions[i]);
744                 assert (basicType(combinerType.parameterType(i)) == lambdaForm.parameterType(1 + argPositions[i]));
745             }
746             System.arraycopy(newParams, 0,
747                              combinerArgs, 1, combinerArity);
748         }
749         Name callCombiner = new Name(combinerType, combinerArgs);
750
751         // insert the two new expressions
752         int exprPos = lambdaForm.arity();
753         buf.insertExpression(exprPos+0, getCombiner);
754         buf.insertExpression(exprPos+1, callCombiner);
755
756         // insert new arguments, if needed
757         int argPos = pos + resultArity;  // skip result parameter
758         for (Name newParam : newParams) {
759             buf.insertParameter(argPos++, newParam);
760         }
761         assert(buf.lastIndexOf(callCombiner) == exprPos+1+newParams.length);
762         if (!dropResult) {
763             buf.replaceParameterByCopy(pos, exprPos+1+newParams.length);
764         }
765
766         return buf.endEdit();
767     }
768
769     LambdaForm filterReturnForm(BasicType newType, boolean constantZero) {
770         byte kind = (constantZero ? Transform.FILTER_RETURN_TO_ZERO : Transform.FILTER_RETURN);
771         Transform key = Transform.of(kind, newType.ordinal());
772         LambdaForm form = getInCache(key);
773         if (form != null) {
774             assert(form.arity == lambdaForm.arity);
775             assert(form.returnType() == newType);
776             return form;
777         }
778         LambdaFormBuffer buf = buffer();
779         buf.startEdit();
780
781         int insPos = lambdaForm.names.length;
782         Name callFilter;
783         if (constantZero) {
784             // Synthesize a constant zero value for the given type.
785             if (newType == V_TYPE)
786                 callFilter = null;
787             else
788                 callFilter = new Name(constantZero(newType));
789         } else {
790             BoundMethodHandle.SpeciesData oldData = oldSpeciesData();
791             BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE);
792
793             // The newly created LF will run with a different BMH.
794             // Switch over any pre-existing BMH field references to the new BMH class.
795             Name oldBaseAddress = lambdaForm.parameter(0);  // BMH holding the values
796             buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress);
797             Name newBaseAddress = oldBaseAddress.withConstraint(newData);
798             buf.renameParameter(0, newBaseAddress);
799
800             Name getFilter = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress);
801             buf.insertExpression(insPos++, getFilter);
802             BasicType oldType = lambdaForm.returnType();
803             if (oldType == V_TYPE) {
804                 MethodType filterType = MethodType.methodType(newType.basicTypeClass());
805                 callFilter = new Name(filterType, getFilter);
806             } else {
807                 MethodType filterType = MethodType.methodType(newType.basicTypeClass(), oldType.basicTypeClass());
808                 callFilter = new Name(filterType, getFilter, lambdaForm.names[lambdaForm.result]);
809             }
810         }
811
812         if (callFilter != null)
813             buf.insertExpression(insPos++, callFilter);
814         buf.setResult(callFilter);
815
816         form = buf.endEdit();
817         return putInCache(key, form);
818     }
819
820     LambdaForm foldArgumentsForm(int foldPos, boolean dropResult, MethodType combinerType) {
821         int combinerArity = combinerType.parameterCount();
822         byte kind = (dropResult ? Transform.FOLD_ARGS_TO_VOID : Transform.FOLD_ARGS);
823         Transform key = Transform.of(kind, foldPos, combinerArity);
824         LambdaForm form = getInCache(key);
825         if (form != null) {
826             assert(form.arity == lambdaForm.arity - (kind == Transform.FOLD_ARGS ? 1 : 0));
827             return form;
828         }
829         form = makeArgumentCombinationForm(foldPos, combinerType, true, dropResult);
830         return putInCache(key, form);
831     }
832
833     LambdaForm foldArgumentsForm(int foldPos, boolean dropResult, MethodType combinerType, int ... argPositions) {
834         byte kind = (dropResult ? Transform.FOLD_SELECT_ARGS_TO_VOID
835                                 : Transform.FOLD_SELECT_ARGS);
836         int[] keyArgs = Arrays.copyOf(argPositions, argPositions.length + 1);
837         keyArgs[argPositions.length] = foldPos;
838         Transform key = Transform.of(kind, keyArgs);
839         LambdaForm form = getInCache(key);
840         if (form != null) {
841             assert(form.arity == lambdaForm.arity - (kind == Transform.FOLD_SELECT_ARGS ? 1 : 0));
842             return form;
843         }
844         form = makeArgumentCombinationForm(foldPos, combinerType, argPositions, true, dropResult);
845         return putInCache(key, form);
846     }
847
848     LambdaForm permuteArgumentsForm(int skip, int[] reorder) {
849         assert(skip == 1);  // skip only the leading MH argument, names[0]
850         int length = lambdaForm.names.length;
851         int outArgs = reorder.length;
852         int inTypes = 0;
853         boolean nullPerm = true;
854         for (int i = 0; i < reorder.length; i++) {
855             int inArg = reorder[i];
856             if (inArg != i)  nullPerm = false;
857             inTypes = Math.max(inTypes, inArg+1);
858         }
859         assert(skip + reorder.length == lambdaForm.arity);
860         if (nullPerm)  return lambdaForm;  // do not bother to cache
861         Transform key = Transform.of(Transform.PERMUTE_ARGS, reorder);
862         LambdaForm form = getInCache(key);
863         if (form != null) {
864             assert(form.arity == skip+inTypes) : form;
865             return form;
866         }
867
868         BasicType[] types = new BasicType[inTypes];
869         for (int i = 0; i < outArgs; i++) {
870             int inArg = reorder[i];
871             types[inArg] = lambdaForm.names[skip + i].type;
872         }
873         assert (skip + outArgs == lambdaForm.arity);
874         assert (permutedTypesMatch(reorder, types, lambdaForm.names, skip));
875         int pos = 0;
876         while (pos < outArgs && reorder[pos] == pos) {
877             pos += 1;
878         }
879         Name[] names2 = new Name[length - outArgs + inTypes];
880         System.arraycopy(lambdaForm.names, 0, names2, 0, skip + pos);
881         int bodyLength = length - lambdaForm.arity;
882         System.arraycopy(lambdaForm.names, skip + outArgs, names2, skip + inTypes, bodyLength);
883         int arity2 = names2.length - bodyLength;
884         int result2 = lambdaForm.result;
885         if (result2 >= skip) {
886             if (result2 < skip + outArgs) {
887                 result2 = reorder[result2 - skip] + skip;
888             } else {
889                 result2 = result2 - outArgs + inTypes;
890             }
891         }
892         for (int j = pos; j < outArgs; j++) {
893             Name n = lambdaForm.names[skip + j];
894             int i = reorder[j];
895             Name n2 = names2[skip + i];
896             if (n2 == null) {
897                 names2[skip + i] = n2 = new Name(types[i]);
898             } else {
899                 assert (n2.type == types[i]);
900             }
901             for (int k = arity2; k < names2.length; k++) {
902                 names2[k] = names2[k].replaceName(n, n2);
903             }
904         }
905         for (int i = skip + pos; i < arity2; i++) {
906             if (names2[i] == null) {
907                 names2[i] = argument(i, types[i - skip]);
908             }
909         }
910         for (int j = lambdaForm.arity; j < lambdaForm.names.length; j++) {
911             int i = j - lambdaForm.arity + arity2;
912             Name n = lambdaForm.names[j];
913             Name n2 = names2[i];
914             if (n != n2) {
915                 for (int k = i + 1; k < names2.length; k++) {
916                     names2[k] = names2[k].replaceName(n, n2);
917                 }
918             }
919         }
920
921         form = new LambdaForm(arity2, names2, result2);
922         return putInCache(key, form);
923     }
924
925     LambdaForm noteLoopLocalTypesForm(int pos, BasicType[] localTypes) {
926         assert(lambdaForm.isLoop(pos));
927         int[] desc = BasicType.basicTypeOrds(localTypes);
928         desc = Arrays.copyOf(desc, desc.length + 1);
929         desc[desc.length - 1] = pos;
930         Transform key = Transform.of(Transform.LOCAL_TYPES, desc);
931         LambdaForm form = getInCache(key);
932         if (form != null) {
933             return form;
934         }
935
936         // replace the null entry in the MHImpl.loop invocation with localTypes
937         Name invokeLoop = lambdaForm.names[pos + 1];
938         assert(invokeLoop.function.equals(MethodHandleImpl.getFunction(NF_loop)));
939         Object[] args = Arrays.copyOf(invokeLoop.arguments, invokeLoop.arguments.length);
940         assert(args[0] == null);
941         args[0] = localTypes;
942
943         LambdaFormBuffer buf = buffer();
944         buf.startEdit();
945         buf.changeName(pos + 1, new Name(MethodHandleImpl.getFunction(NF_loop), args));
946         form = buf.endEdit();
947
948         return putInCache(key, form);
949     }
950
951     static boolean permutedTypesMatch(int[] reorder, BasicType[] types, Name[] names, int skip) {
952         for (int i = 0; i < reorder.length; i++) {
953             assert (names[skip + i].isParam());
954             assert (names[skip + i].type == types[reorder[i]]);
955         }
956         return true;
957     }
958 }
959