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