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