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