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