changeset 9994:914aea3f4893

8057042: LambdaFormEditor: derive new LFs from a base LF Reviewed-by: vlivanov, psandoz Contributed-by: john.r.rose@oracle.com
author vlivanov
date Wed, 10 Sep 2014 18:34:40 +0400
parents 4a505ea8cc0a
children 24ac0f2fad86
files src/share/classes/java/lang/invoke/BoundMethodHandle.java src/share/classes/java/lang/invoke/LambdaForm.java src/share/classes/java/lang/invoke/LambdaFormBuffer.java src/share/classes/java/lang/invoke/LambdaFormEditor.java src/share/classes/java/lang/invoke/MethodHandleImpl.java
diffstat 5 files changed, 881 insertions(+), 100 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/lang/invoke/BoundMethodHandle.java	Wed Sep 10 18:34:03 2014 +0400
+++ b/src/share/classes/java/lang/invoke/BoundMethodHandle.java	Wed Sep 10 18:34:40 2014 +0400
@@ -54,6 +54,7 @@
 
     /*non-public*/ BoundMethodHandle(MethodType type, LambdaForm form) {
         super(type, form);
+        assert(speciesData() == speciesData(form));
     }
 
     //
@@ -81,6 +82,11 @@
         }
     }
 
+    /*non-public*/
+    LambdaFormEditor editor() {
+        return form.editor();
+    }
+
     static BoundMethodHandle bindSingle(MethodType type, LambdaForm form, Object x) {
         return Species_L.make(type, form, x);
     }
@@ -88,33 +94,23 @@
     @Override // there is a default binder in the super class, for 'L' types only
     /*non-public*/
     BoundMethodHandle bindArgumentL(int pos, Object value) {
-        MethodType type = type().dropParameterTypes(pos, pos+1);
-        LambdaForm form = internalForm().bind(1+pos, speciesData());
-        return copyWithExtendL(type, form, value);
+        return editor().bindArgumentL(this, pos, value);
     }
     /*non-public*/
     BoundMethodHandle bindArgumentI(int pos, int value) {
-        MethodType type = type().dropParameterTypes(pos, pos+1);
-        LambdaForm form = internalForm().bind(1+pos, speciesData());
-        return copyWithExtendI(type, form, value);
+        return editor().bindArgumentI(this, pos, value);
     }
     /*non-public*/
     BoundMethodHandle bindArgumentJ(int pos, long value) {
-        MethodType type = type().dropParameterTypes(pos, pos+1);
-        LambdaForm form = internalForm().bind(1+pos, speciesData());
-        return copyWithExtendJ(type, form, value);
+        return editor().bindArgumentJ(this, pos, value);
     }
     /*non-public*/
     BoundMethodHandle bindArgumentF(int pos, float value) {
-        MethodType type = type().dropParameterTypes(pos, pos+1);
-        LambdaForm form = internalForm().bind(1+pos, speciesData());
-        return copyWithExtendF(type, form, value);
+        return editor().bindArgumentF(this, pos, value);
     }
     /*non-public*/
     BoundMethodHandle bindArgumentD(int pos, double value) {
-        MethodType type = type().dropParameterTypes(pos, pos + 1);
-        LambdaForm form = internalForm().bind(1+pos, speciesData());
-        return copyWithExtendD(type, form, value);
+        return editor().bindArgumentD(this, pos, value);
     }
 
     @Override
@@ -149,6 +145,14 @@
      */
     /*non-public*/ abstract SpeciesData speciesData();
 
+    /*non-public*/ static SpeciesData speciesData(LambdaForm form) {
+        Object c = form.names[0].constraint;
+        if (c instanceof SpeciesData)
+            return (SpeciesData) c;
+        // if there is no BMH constraint, then use the null constraint
+        return SpeciesData.EMPTY;
+    }
+
     /**
      * Return the number of fields in this BMH.  Equivalent to speciesData().fieldCount().
      */
--- a/src/share/classes/java/lang/invoke/LambdaForm.java	Wed Sep 10 18:34:03 2014 +0400
+++ b/src/share/classes/java/lang/invoke/LambdaForm.java	Wed Sep 10 18:34:40 2014 +0400
@@ -124,8 +124,7 @@
     MemberName vmentry;   // low-level behavior, or null if not yet prepared
     private boolean isCompiled;
 
-    // Caches for common structural transforms:
-    LambdaForm[] bindCache;
+    Object transformCache;  // managed by LambdaFormEditor
 
     public static final int VOID_RESULT = -1, LAST_RESULT = -2;
 
@@ -213,6 +212,13 @@
             }
             return btypes;
         }
+        static byte[] basicTypesOrd(BasicType[] btypes) {
+            byte[] ords = new byte[btypes.length];
+            for (int i = 0; i < btypes.length; i++) {
+                ords[i] = (byte)btypes[i].ordinal();
+            }
+            return ords;
+        }
         static boolean isBasicTypeChar(char c) {
             return "LIJFDV".indexOf(c) >= 0;
         }
@@ -408,7 +414,7 @@
      * This allows Name references to be freely reused to construct
      * fresh lambdas, without confusion.
      */
-    private boolean nameRefsAreLegal() {
+    boolean nameRefsAreLegal() {
         assert(arity >= 0 && arity <= names.length);
         assert(result >= -1 && result < names.length);
         // Do all names possess an index consistent with their local definition order?
@@ -887,87 +893,8 @@
     public int hashCode() {
         return result + 31 * Arrays.hashCode(names);
     }
-
-    LambdaForm bind(int namePos, BoundMethodHandle.SpeciesData oldData) {
-        Name name = names[namePos];
-        BoundMethodHandle.SpeciesData newData = oldData.extendWith(name.type);
-        return bind(name, new Name(newData.getterFunction(oldData.fieldCount()), names[0]), oldData, newData);
-    }
-    LambdaForm bind(Name name, Name binding,
-                    BoundMethodHandle.SpeciesData oldData,
-                    BoundMethodHandle.SpeciesData newData) {
-        int pos = name.index;
-        assert(name.isParam());
-        assert(!binding.isParam());
-        assert(name.type == binding.type);
-        assert(0 <= pos && pos < arity && names[pos] == name);
-        assert(binding.function.memberDeclaringClassOrNull() == newData.fieldHolder());
-        assert(oldData.getterFunctions().length == newData.getterFunctions().length-1);
-        if (bindCache != null) {
-            LambdaForm form = bindCache[pos];
-            if (form != null) {
-                assert(form.contains(binding)) : "form << " + form + " >> does not contain binding << " + binding + " >>";
-                return form;
-            }
-        } else {
-            bindCache = new LambdaForm[arity];
-        }
-        assert(nameRefsAreLegal());
-        int arity2 = arity-1;
-        Name[] names2 = names.clone();
-        names2[pos] = binding;  // we might move this in a moment
-
-        // The newly created LF will run with a different BMH.
-        // Switch over any pre-existing BMH field references to the new BMH class.
-        int firstOldRef = -1;
-        for (int i = 0; i < names2.length; i++) {
-            Name n = names[i];
-            if (n.function != null &&
-                n.function.memberDeclaringClassOrNull() == oldData.fieldHolder()) {
-                MethodHandle oldGetter = n.function.resolvedHandle;
-                MethodHandle newGetter = null;
-                for (int j = 0; j < oldData.getterHandles().length; j++) {
-                    if (oldGetter == oldData.getterHandles()[j])
-                        newGetter =  newData.getterHandles()[j];
-                }
-                if (newGetter != null) {
-                    if (firstOldRef < 0)  firstOldRef = i;
-                    Name n2 = new Name(newGetter, n.arguments);
-                    names2[i] = n2;
-                }
-            }
-        }
-
-        // Walk over the new list of names once, in forward order.
-        // Replace references to 'name' with 'binding'.
-        // Replace data structure references to the old BMH species with the new.
-        // This might cause a ripple effect, but it will settle in one pass.
-        assert(firstOldRef < 0 || firstOldRef > pos);
-        for (int i = pos+1; i < names2.length; i++) {
-            if (i <= arity2)  continue;
-            names2[i] = names2[i].replaceNames(names, names2, pos, i);
-        }
-
-        //  (a0, a1, name=a2, a3, a4)  =>  (a0, a1, a3, a4, binding)
-        int insPos = pos;
-        for (; insPos+1 < names2.length; insPos++) {
-            Name n = names2[insPos+1];
-            if (n.isParam()) {
-                names2[insPos] = n;
-            } else {
-                break;
-            }
-        }
-        names2[insPos] = binding;
-
-        // Since we moved some stuff, maybe update the result reference:
-        int result2 = result;
-        if (result2 == pos)
-            result2 = insPos;
-        else if (result2 > pos && result2 <= insPos)
-            result2 -= 1;
-
-        return bindCache[pos] = new LambdaForm(debugName, arity2, names2, result2);
+    LambdaFormEditor editor() {
+        return LambdaFormEditor.lambdaFormEditor(this);
     }
 
     boolean contains(Name name) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/lang/invoke/LambdaFormBuffer.java	Wed Sep 10 18:34:40 2014 +0400
@@ -0,0 +1,400 @@
+/*
+ * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package java.lang.invoke;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import static java.lang.invoke.LambdaForm.*;
+import static java.lang.invoke.LambdaForm.BasicType.*;
+
+/** Working storage for an LF that is being transformed.
+ *  Similarly to a StringBuffer, the editing can take place in multiple steps.
+ */
+final class LambdaFormBuffer {
+    private int arity, length;
+    private Name[] names;
+    private Name[] originalNames;  // snapshot of pre-transaction names
+    private byte flags;
+    private int firstChange;
+    private Name resultName;
+    private String debugName;
+    private ArrayList<Name> dups;
+
+    private static final int F_TRANS = 0x10, F_OWNED = 0x03;
+
+    LambdaFormBuffer(LambdaForm lf) {
+        this(lf.arity, lf.names, lf.result);
+        debugName = lf.debugName;
+        assert(lf.nameRefsAreLegal());
+    }
+
+    private LambdaFormBuffer(int arity, Name[] names, int result) {
+        this.arity = arity;
+        setNames(names);
+        if (result == LAST_RESULT)  result = length - 1;
+        if (result >= 0 && names[result].type != V_TYPE)
+            resultName = names[result];
+    }
+
+    LambdaForm lambdaForm() {
+        assert(!inTrans());  // need endEdit call to tidy things up
+        return new LambdaForm(debugName, arity, nameArray(), resultIndex());
+    }
+
+    Name name(int i) {
+        assert(i < length);
+        return names[i];
+    }
+
+    Name[] nameArray() {
+        return Arrays.copyOf(names, length);
+    }
+
+    int resultIndex() {
+        if (resultName == null)  return VOID_RESULT;
+        int index = indexOf(resultName, names);
+        assert(index >= 0);
+        return index;
+    }
+
+    void setNames(Name[] names2) {
+        names = originalNames = names2;  // keep a record of where everything was to start with
+        length = names2.length;
+        flags = 0;
+    }
+
+    private boolean verifyArity() {
+        for (int i = 0; i < arity && i < firstChange; i++) {
+            assert(names[i].isParam()) : "#" + i + "=" + names[i];
+        }
+        for (int i = arity; i < length; i++) {
+            assert(!names[i].isParam()) : "#" + i + "=" + names[i];
+        }
+        for (int i = length; i < names.length; i++) {
+            assert(names[i] == null) : "#" + i + "=" + names[i];
+        }
+        // check resultName also
+        if (resultName != null) {
+            int resultIndex = indexOf(resultName, names);
+            assert(resultIndex >= 0) : "not found: " + resultName.exprString() + Arrays.asList(names);
+            assert(names[resultIndex] == resultName);
+        }
+        return true;
+    }
+
+    private boolean verifyFirstChange() {
+        assert(inTrans());
+        for (int i = 0; i < length; i++) {
+            if (names[i] != originalNames[i]) {
+                assert(firstChange == i) : Arrays.asList(firstChange, i, originalNames[i].exprString(), Arrays.asList(names));
+                return true;
+            }
+        }
+        assert(firstChange == length) : Arrays.asList(firstChange, Arrays.asList(names));
+        return true;
+    }
+
+    private static int indexOf(NamedFunction fn, NamedFunction[] fns) {
+        for (int i = 0; i < fns.length; i++) {
+            if (fns[i] == fn)  return i;
+        }
+        return -1;
+    }
+
+    private static int indexOf(Name n, Name[] ns) {
+        for (int i = 0; i < ns.length; i++) {
+            if (ns[i] == n)  return i;
+        }
+        return -1;
+    }
+
+    boolean inTrans() {
+        return (flags & F_TRANS) != 0;
+    }
+
+    int ownedCount() {
+        return flags & F_OWNED;
+    }
+
+    void growNames(int insertPos, int growLength) {
+        int oldLength = length;
+        int newLength = oldLength + growLength;
+        int oc = ownedCount();
+        if (oc == 0 || newLength > names.length) {
+            names = Arrays.copyOf(names, (names.length + growLength) * 5 / 4);
+            if (oc == 0) {
+                flags++;
+                oc++;
+                assert(ownedCount() == oc);
+            }
+        }
+        if (originalNames != null && originalNames.length < names.length) {
+            originalNames = Arrays.copyOf(originalNames, names.length);
+            if (oc == 1) {
+                flags++;
+                oc++;
+                assert(ownedCount() == oc);
+            }
+        }
+        if (growLength == 0)  return;
+        int insertEnd = insertPos + growLength;
+        int tailLength = oldLength - insertPos;
+        System.arraycopy(names, insertPos, names, insertEnd, tailLength);
+        Arrays.fill(names, insertPos, insertEnd, null);
+        if (originalNames != null) {
+            System.arraycopy(originalNames, insertPos, originalNames, insertEnd, tailLength);
+            Arrays.fill(originalNames, insertPos, insertEnd, null);
+        }
+        length = newLength;
+        if (firstChange >= insertPos) {
+            firstChange += growLength;
+        }
+    }
+
+    int lastIndexOf(Name n) {
+        int result = -1;
+        for (int i = 0; i < length; i++) {
+            if (names[i] == n)  result = i;
+        }
+        return result;
+    }
+
+    /** We have just overwritten the name at pos1 with the name at pos2.
+     *  This means that there are two copies of the name, which we will have to fix later.
+     */
+    private void noteDuplicate(int pos1, int pos2) {
+        Name n = names[pos1];
+        assert(n == names[pos2]);
+        assert(originalNames[pos1] != null);  // something was replaced at pos1
+        assert(originalNames[pos2] == null || originalNames[pos2] == n);
+        if (dups == null) {
+            dups = new ArrayList<>();
+        }
+        dups.add(n);
+    }
+
+    /** Replace duplicate names by nulls, and remove all nulls. */
+    private void clearDuplicatesAndNulls() {
+        if (dups != null) {
+            // Remove duplicates.
+            assert(ownedCount() >= 1);
+            for (Name dup : dups) {
+                for (int i = firstChange; i < length; i++) {
+                    if (names[i] == dup && originalNames[i] != dup) {
+                        names[i] = null;
+                        assert(Arrays.asList(names).contains(dup));
+                        break;  // kill only one dup
+                    }
+                }
+            }
+            dups.clear();
+        }
+        // Now that we are done with originalNames, remove "killed" names.
+        int oldLength = length;
+        for (int i = firstChange; i < length; i++) {
+            if (names[i] == null) {
+                System.arraycopy(names, i + 1, names, i, (--length - i));
+                --i;  // restart loop at this position
+            }
+        }
+        if (length < oldLength) {
+            Arrays.fill(names, length, oldLength, null);
+        }
+        assert(!Arrays.asList(names).subList(0, length).contains(null));
+    }
+
+    /** Create a private, writable copy of names.
+     *  Preserve the original copy, for reference.
+     */
+    void startEdit() {
+        assert(verifyArity());
+        int oc = ownedCount();
+        assert(!inTrans());  // no nested transactions
+        flags |= F_TRANS;
+        Name[] oldNames = names;
+        Name[] ownBuffer = (oc == 2 ? originalNames : null);
+        assert(ownBuffer != oldNames);
+        if (ownBuffer != null && ownBuffer.length >= length) {
+            names = copyNamesInto(ownBuffer);
+        } else {
+            // make a new buffer to hold the names
+            final int SLOP = 2;
+            names = Arrays.copyOf(oldNames, Math.max(length + SLOP, oldNames.length));
+            if (oc < 2)  ++flags;
+            assert(ownedCount() == oc + 1);
+        }
+        originalNames = oldNames;
+        assert(originalNames != names);
+        firstChange = length;
+        assert(inTrans());
+    }
+
+    private void changeName(int i, Name name) {
+        assert(inTrans());
+        assert(i < length);
+        Name oldName = names[i];
+        assert(oldName == originalNames[i]);  // no multiple changes
+        assert(verifyFirstChange());
+        if (ownedCount() == 0)
+            growNames(0, 0);
+        names[i] = name;
+        if (firstChange > i) {
+            firstChange = i;
+        }
+        if (resultName != null && resultName == oldName) {
+            resultName = name;
+        }
+    }
+
+    /** Change the result name.  Null means a void result. */
+    void setResult(Name name) {
+        assert(name == null || lastIndexOf(name) >= 0);
+        resultName = name;
+    }
+
+    /** Finish a transaction. */
+    void endEdit() {
+        assert(verifyFirstChange());
+        // Assuming names have been changed pairwise from originalNames[i] to names[i],
+        // update arguments to ensure referential integrity.
+        for (int i = Math.max(firstChange, arity); i < length; i++) {
+            Name name = names[i];
+            if (name == null)  continue;  // space for removed duplicate
+            Name newName = name.replaceNames(originalNames, names, firstChange, i);
+            if (newName != name) {
+                names[i] = newName;
+                if (resultName == name) {
+                    resultName = newName;
+                }
+            }
+        }
+        assert(inTrans());
+        flags &= ~F_TRANS;
+        clearDuplicatesAndNulls();
+        originalNames = null;
+        // If any parameters have been changed, then reorder them as needed.
+        // This is a "sheep-and-goats" stable sort, pushing all non-parameters
+        // to the right of all parameters.
+        if (firstChange < arity) {
+            Name[] exprs = new Name[arity - firstChange];
+            int argp = firstChange, exprp = 0;
+            for (int i = firstChange; i < arity; i++) {
+                Name name = names[i];
+                if (name.isParam()) {
+                    names[argp++] = name;
+                } else {
+                    exprs[exprp++] = name;
+                }
+            }
+            assert(exprp == (arity - argp));
+            // copy the exprs just after the last remaining param
+            System.arraycopy(exprs, 0, names, argp, exprp);
+            // adjust arity
+            arity -= exprp;
+        }
+        assert(verifyArity());
+    }
+
+    private Name[] copyNamesInto(Name[] buffer) {
+        System.arraycopy(names, 0, buffer, 0, length);
+        Arrays.fill(buffer, length, buffer.length, null);
+        return buffer;
+    }
+
+    /** Replace any Name whose function is in oldFns with a copy
+     *  whose function is in the corresponding position in newFns.
+     *  Only do this if the arguments are exactly equal to the given.
+     */
+    LambdaFormBuffer replaceFunctions(NamedFunction[] oldFns, NamedFunction[] newFns,
+                                      Object... forArguments) {
+        assert(inTrans());
+        if (oldFns.length == 0)  return this;
+        for (int i = arity; i < length; i++) {
+            Name n = names[i];
+            int nfi = indexOf(n.function, oldFns);
+            if (nfi >= 0 && Arrays.equals(n.arguments, forArguments)) {
+                changeName(i, new Name(newFns[nfi], n.arguments));
+            }
+        }
+        return this;
+    }
+
+    private void replaceName(int pos, Name binding) {
+        assert(inTrans());
+        assert(verifyArity());
+        assert(pos < arity);
+        Name param = names[pos];
+        assert(param.isParam());
+        assert(param.type == binding.type);
+        changeName(pos, binding);
+    }
+
+    /** Replace a parameter by a fresh parameter. */
+    LambdaFormBuffer renameParameter(int pos, Name newParam) {
+        assert(newParam.isParam());
+        replaceName(pos, newParam);
+        return this;
+    }
+
+    /** Replace a parameter by a fresh expression. */
+    LambdaFormBuffer replaceParameterByNewExpression(int pos, Name binding) {
+        assert(!binding.isParam());
+        assert(lastIndexOf(binding) < 0);  // else use replaceParameterByCopy
+        replaceName(pos, binding);
+        return this;
+    }
+
+    /** Replace a parameter by another parameter or expression already in the form. */
+    LambdaFormBuffer replaceParameterByCopy(int pos, int valuePos) {
+        assert(pos != valuePos);
+        replaceName(pos, names[valuePos]);
+        noteDuplicate(pos, valuePos);  // temporarily, will occur twice in the names array
+        return this;
+    }
+
+    private void insertName(int pos, Name expr, boolean isParameter) {
+        assert(inTrans());
+        assert(verifyArity());
+        assert(isParameter ? pos <= arity : pos >= arity);
+        growNames(pos, 1);
+        if (isParameter)  arity += 1;
+        changeName(pos, expr);
+    }
+
+    /** Insert a fresh expression. */
+    LambdaFormBuffer insertExpression(int pos, Name expr) {
+        assert(!expr.isParam());
+        insertName(pos, expr, false);
+        return this;
+    }
+
+    /** Insert a fresh parameter. */
+    LambdaFormBuffer insertParameter(int pos, Name param) {
+        assert(param.isParam());
+        insertName(pos, param, true);
+        return this;
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/lang/invoke/LambdaFormEditor.java	Wed Sep 10 18:34:40 2014 +0400
@@ -0,0 +1,450 @@
+/*
+ * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package java.lang.invoke;
+
+import java.util.Arrays;
+import static java.lang.invoke.LambdaForm.*;
+import static java.lang.invoke.LambdaForm.BasicType.*;
+import static java.lang.invoke.MethodHandleImpl.Intrinsic;
+import java.util.Collections;
+import java.util.concurrent.ConcurrentHashMap;
+
+import sun.invoke.util.Wrapper;
+
+/** Transforms on LFs.
+ *  A lambda-form editor can derive new LFs from its base LF.
+ *  The editor can cache derived LFs, which simplifies the reuse of their underlying bytecodes.
+ *  To support this caching, a LF has an optional pointer to its editor.
+ */
+class LambdaFormEditor {
+    final LambdaForm lambdaForm;
+
+    private LambdaFormEditor(LambdaForm lambdaForm) {
+        this.lambdaForm = lambdaForm;
+    }
+
+    // Factory method.
+    static LambdaFormEditor lambdaFormEditor(LambdaForm lambdaForm) {
+        // TO DO:  Consider placing intern logic here, to cut down on duplication.
+        // lambdaForm = findPreexistingEquivalent(lambdaForm)
+        return new LambdaFormEditor(lambdaForm);
+    }
+
+    /** A description of a cached transform, possibly associated with the result of the transform.
+     *  The logical content is a sequence of byte values, starting with a Kind.ordinal value.
+     *  The sequence is unterminated, ending with an indefinite number of zero bytes.
+     *  Sequences that are simple (short enough and with small enough values) pack into a 64-bit long.
+     */
+    private static final class Transform {
+        final long packedBytes;
+        final byte[] fullBytes;
+        final LambdaForm result;  // result of transform, or null, if there is none available
+
+        private enum Kind {
+            NO_KIND,  // necessary because ordinal must be greater than zero
+            BIND_ARG, ADD_ARG, DUP_ARG,
+            SPREAD_ARGS,
+            FILTER_ARG, FILTER_RETURN, FILTER_RETURN_TO_ZERO,
+            COLLECT_ARGS, COLLECT_ARGS_TO_VOID, COLLECT_ARGS_TO_ARRAY,
+            FOLD_ARGS, FOLD_ARGS_TO_VOID,
+            PERMUTE_ARGS
+            //maybe add more for guard with test, catch exception, pointwise type conversions
+        }
+
+        private static final boolean STRESS_TEST = false; // turn on to disable most packing
+        private static final int
+                PACKED_BYTE_SIZE = (STRESS_TEST ? 2 : 4),
+                PACKED_BYTE_MASK = (1 << PACKED_BYTE_SIZE) - 1,
+                PACKED_BYTE_MAX_LENGTH = (STRESS_TEST ? 3 : 64 / PACKED_BYTE_SIZE);
+
+        private static long packedBytes(byte[] bytes) {
+            if (bytes.length > PACKED_BYTE_MAX_LENGTH)  return 0;
+            long pb = 0;
+            int bitset = 0;
+            for (int i = 0; i < bytes.length; i++) {
+                int b = bytes[i] & 0xFF;
+                bitset |= b;
+                pb |= (long)b << (i * PACKED_BYTE_SIZE);
+            }
+            if (!inRange(bitset))
+                return 0;
+            return pb;
+        }
+        private static long packedBytes(int b0, int b1) {
+            assert(inRange(b0 | b1));
+            return (  (b0 << 0*PACKED_BYTE_SIZE)
+                    | (b1 << 1*PACKED_BYTE_SIZE));
+        }
+        private static long packedBytes(int b0, int b1, int b2) {
+            assert(inRange(b0 | b1 | b2));
+            return (  (b0 << 0*PACKED_BYTE_SIZE)
+                    | (b1 << 1*PACKED_BYTE_SIZE)
+                    | (b2 << 2*PACKED_BYTE_SIZE));
+        }
+        private static long packedBytes(int b0, int b1, int b2, int b3) {
+            assert(inRange(b0 | b1 | b2 | b3));
+            return (  (b0 << 0*PACKED_BYTE_SIZE)
+                    | (b1 << 1*PACKED_BYTE_SIZE)
+                    | (b2 << 2*PACKED_BYTE_SIZE)
+                    | (b3 << 3*PACKED_BYTE_SIZE));
+        }
+        private static boolean inRange(int bitset) {
+            assert((bitset & 0xFF) == bitset);  // incoming values must fit in *unsigned* byte
+            return ((bitset & ~PACKED_BYTE_MASK) == 0);
+        }
+        private static byte[] fullBytes(int... byteValues) {
+            byte[] bytes = new byte[byteValues.length];
+            int i = 0;
+            for (int bv : byteValues) {
+                bytes[i++] = bval(bv);
+            }
+            assert(packedBytes(bytes) == 0);
+            return bytes;
+        }
+
+        private byte byteAt(int i) {
+            long pb = packedBytes;
+            if (pb == 0) {
+                if (i >= fullBytes.length)  return 0;
+                return fullBytes[i];
+            }
+            assert(fullBytes == null);
+            if (i > PACKED_BYTE_MAX_LENGTH)  return 0;
+            int pos = (i * PACKED_BYTE_SIZE);
+            return (byte)((pb >>> pos) & PACKED_BYTE_MASK);
+        }
+
+        Kind kind() { return Kind.values()[byteAt(0)]; }
+
+        private Transform(long packedBytes, byte[] fullBytes, LambdaForm result) {
+            this.packedBytes = packedBytes;
+            this.fullBytes = fullBytes;
+            this.result = result;
+        }
+        private Transform(long packedBytes) {
+            this(packedBytes, null, null);
+            assert(packedBytes != 0);
+        }
+        private Transform(byte[] fullBytes) {
+            this(0, fullBytes, null);
+        }
+
+        private static byte bval(int b) {
+            assert((b & 0xFF) == b);  // incoming value must fit in *unsigned* byte
+            return (byte)b;
+        }
+        private static byte bval(Kind k) {
+            return bval(k.ordinal());
+        }
+        static Transform of(Kind k, int b1) {
+            byte b0 = bval(k);
+            if (inRange(b0 | b1))
+                return new Transform(packedBytes(b0, b1));
+            else
+                return new Transform(fullBytes(b0, b1));
+        }
+        static Transform of(Kind k, int b1, int b2) {
+            byte b0 = (byte) k.ordinal();
+            if (inRange(b0 | b1 | b2))
+                return new Transform(packedBytes(b0, b1, b2));
+            else
+                return new Transform(fullBytes(b0, b1, b2));
+        }
+        static Transform of(Kind k, int b1, int b2, int b3) {
+            byte b0 = (byte) k.ordinal();
+            if (inRange(b0 | b1 | b2 | b3))
+                return new Transform(packedBytes(b0, b1, b2, b3));
+            else
+                return new Transform(fullBytes(b0, b1, b2, b3));
+        }
+        private static final byte[] NO_BYTES = {};
+        static Transform of(Kind k, int... b123) {
+            return ofBothArrays(k, b123, NO_BYTES);
+        }
+        static Transform of(Kind k, int b1, byte[] b234) {
+            return ofBothArrays(k, new int[]{ b1 }, b234);
+        }
+        static Transform of(Kind k, int b1, int b2, byte[] b345) {
+            return ofBothArrays(k, new int[]{ b1, b2 }, b345);
+        }
+        private static Transform ofBothArrays(Kind k, int[] b123, byte[] b456) {
+            byte[] fullBytes = new byte[1 + b123.length + b456.length];
+            int i = 0;
+            fullBytes[i++] = bval(k);
+            for (int bv : b123) {
+                fullBytes[i++] = bval(bv);
+            }
+            for (byte bv : b456) {
+                fullBytes[i++] = bv;
+            }
+            long packedBytes = packedBytes(fullBytes);
+            if (packedBytes != 0)
+                return new Transform(packedBytes);
+            else
+                return new Transform(fullBytes);
+        }
+
+        Transform withResult(LambdaForm result) {
+            return new Transform(this.packedBytes, this.fullBytes, result);
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            return obj instanceof Transform && equals((Transform)obj);
+        }
+        public boolean equals(Transform that) {
+            return this.packedBytes == that.packedBytes && Arrays.equals(this.fullBytes, that.fullBytes);
+        }
+        @Override
+        public int hashCode() {
+            if (packedBytes != 0) {
+                assert(fullBytes == null);
+                return Long.hashCode(packedBytes);
+            }
+            return Arrays.hashCode(fullBytes);
+        }
+        @Override
+        public String toString() {
+            StringBuilder buf = new StringBuilder();
+            long bits = packedBytes;
+            if (bits != 0) {
+                buf.append("(");
+                while (bits != 0) {
+                    buf.append(bits & PACKED_BYTE_MASK);
+                    bits >>>= PACKED_BYTE_SIZE;
+                    if (bits != 0)  buf.append(",");
+                }
+                buf.append(")");
+            }
+            if (fullBytes != null) {
+                buf.append("unpacked");
+                buf.append(Arrays.toString(fullBytes));
+            }
+            if (result != null) {
+                buf.append(" result=");
+                buf.append(result);
+            }
+            return buf.toString();
+        }
+    }
+
+    /** Find a previously cached transform equivalent to the given one, and return its result. */
+    private LambdaForm getInCache(Transform key) {
+        assert(key.result == null);
+        // The transformCache is one of null, Transform, Transform[], or ConcurrentHashMap.
+        Object c = lambdaForm.transformCache;
+        Transform k = null;
+        if (c instanceof ConcurrentHashMap) {
+            @SuppressWarnings("unchecked")
+            ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c;
+            k = m.get(key);
+        } else if (c == null) {
+            return null;
+        } else if (c instanceof Transform) {
+            // one-element cache avoids overhead of an array
+            Transform t = (Transform)c;
+            if (t.equals(key))  k = t;
+        } else {
+            Transform[] ta = (Transform[])c;
+            for (int i = 0; i < ta.length; i++) {
+                Transform t = ta[i];
+                if (t == null)  break;
+                if (t.equals(key)) { k = t; break; }
+            }
+        }
+        assert(k == null || key.equals(k));
+        return k == null ? null : k.result;
+    }
+
+    /** Arbitrary but reasonable limits on Transform[] size for cache. */
+    private static final int MIN_CACHE_ARRAY_SIZE = 4, MAX_CACHE_ARRAY_SIZE = 16;
+
+    /** Cache a transform with its result, and return that result.
+     *  But if an equivalent transform has already been cached, return its result instead.
+     */
+    private LambdaForm putInCache(Transform key, LambdaForm form) {
+        key = key.withResult(form);
+        for (int pass = 0; ; pass++) {
+            Object c = lambdaForm.transformCache;
+            if (c instanceof ConcurrentHashMap) {
+                @SuppressWarnings("unchecked")
+                ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c;
+                Transform k = m.putIfAbsent(key, key);
+                return k != null ? k.result : form;
+            }
+            assert(pass == 0);
+            synchronized (lambdaForm) {
+                c = lambdaForm.transformCache;
+                if (c instanceof ConcurrentHashMap)
+                    continue;
+                if (c == null) {
+                    lambdaForm.transformCache = key;
+                    return form;
+                }
+                Transform[] ta;
+                if (c instanceof Transform) {
+                    Transform k = (Transform)c;
+                    if (k.equals(key)) {
+                        return k.result;
+                    }
+                    // expand one-element cache to small array
+                    ta = new Transform[MIN_CACHE_ARRAY_SIZE];
+                    ta[0] = k;
+                    lambdaForm.transformCache = c = ta;
+                } else {
+                    // it is already expanded
+                    ta = (Transform[])c;
+                }
+                int len = ta.length;
+                int i;
+                for (i = 0; i < len; i++) {
+                    Transform k = ta[i];
+                    if (k == null) {
+                        break;
+                    }
+                    if (k.equals(key)) {
+                        return k.result;
+                    }
+                }
+                if (i < len) {
+                    // just fall through to cache update
+                } else if (len < MAX_CACHE_ARRAY_SIZE) {
+                    len = Math.min(len * 2, MAX_CACHE_ARRAY_SIZE);
+                    ta = Arrays.copyOf(ta, len);
+                    lambdaForm.transformCache = ta;
+                } else {
+                    ConcurrentHashMap<Transform, Transform> m = new ConcurrentHashMap<>(MAX_CACHE_ARRAY_SIZE * 2);
+                    for (Transform k : ta) {
+                        m.put(k, k);
+                    }
+                    lambdaForm.transformCache = m;
+                    // The second iteration will update for this query, concurrently.
+                    continue;
+                }
+                ta[i] = key;
+                return form;
+            }
+        }
+    }
+
+    private LambdaFormBuffer buffer() {
+        return new LambdaFormBuffer(lambdaForm);
+    }
+
+    /// Editing methods for method handles.  These need to have fast paths.
+
+    private BoundMethodHandle.SpeciesData oldSpeciesData() {
+        return BoundMethodHandle.speciesData(lambdaForm);
+    }
+    private BoundMethodHandle.SpeciesData newSpeciesData(BasicType type) {
+        return oldSpeciesData().extendWith(type);
+    }
+
+    BoundMethodHandle bindArgumentL(BoundMethodHandle mh, int pos, Object value) {
+        assert(mh.speciesData() == oldSpeciesData());
+        BasicType bt = L_TYPE;
+        MethodType type2 = bindArgumentType(mh, pos, bt);
+        LambdaForm form2 = bindArgumentForm(1+pos);
+        return mh.copyWithExtendL(type2, form2, value);
+    }
+    BoundMethodHandle bindArgumentI(BoundMethodHandle mh, int pos, int value) {
+        assert(mh.speciesData() == oldSpeciesData());
+        BasicType bt = I_TYPE;
+        MethodType type2 = bindArgumentType(mh, pos, bt);
+        LambdaForm form2 = bindArgumentForm(1+pos);
+        return mh.copyWithExtendI(type2, form2, value);
+    }
+
+    BoundMethodHandle bindArgumentJ(BoundMethodHandle mh, int pos, long value) {
+        assert(mh.speciesData() == oldSpeciesData());
+        BasicType bt = J_TYPE;
+        MethodType type2 = bindArgumentType(mh, pos, bt);
+        LambdaForm form2 = bindArgumentForm(1+pos);
+        return mh.copyWithExtendJ(type2, form2, value);
+    }
+
+    BoundMethodHandle bindArgumentF(BoundMethodHandle mh, int pos, float value) {
+        assert(mh.speciesData() == oldSpeciesData());
+        BasicType bt = F_TYPE;
+        MethodType type2 = bindArgumentType(mh, pos, bt);
+        LambdaForm form2 = bindArgumentForm(1+pos);
+        return mh.copyWithExtendF(type2, form2, value);
+    }
+
+    BoundMethodHandle bindArgumentD(BoundMethodHandle mh, int pos, double value) {
+        assert(mh.speciesData() == oldSpeciesData());
+        BasicType bt = D_TYPE;
+        MethodType type2 = bindArgumentType(mh, pos, bt);
+        LambdaForm form2 = bindArgumentForm(1+pos);
+        return mh.copyWithExtendD(type2, form2, value);
+    }
+
+    private MethodType bindArgumentType(BoundMethodHandle mh, int pos, BasicType bt) {
+        assert(mh.form == lambdaForm);
+        assert(mh.form.names[1+pos].type == bt);
+        assert(BasicType.basicType(mh.type().parameterType(pos)) == bt);
+        return mh.type().dropParameterTypes(pos, pos+1);
+    }
+
+    /// Editing methods for lambda forms.
+    // Each editing method can (potentially) cache the edited LF so that it can be reused later.
+
+    LambdaForm bindArgumentForm(int pos) {
+        Transform key = Transform.of(Transform.Kind.BIND_ARG, pos);
+        LambdaForm form = getInCache(key);
+        if (form != null) {
+            assert(form.parameterConstraint(0) == newSpeciesData(lambdaForm.parameterType(pos)));
+            return form;
+        }
+        LambdaFormBuffer buf = buffer();
+        buf.startEdit();
+
+        BoundMethodHandle.SpeciesData oldData = oldSpeciesData();
+        BoundMethodHandle.SpeciesData newData = newSpeciesData(lambdaForm.parameterType(pos));
+        Name oldBaseAddress = lambdaForm.parameter(0);  // BMH holding the values
+        Name newBaseAddress;
+        NamedFunction getter = newData.getterFunction(oldData.fieldCount());
+
+        if (pos != 0) {
+            // The newly created LF will run with a different BMH.
+            // Switch over any pre-existing BMH field references to the new BMH class.
+            buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress);
+            newBaseAddress = oldBaseAddress.withConstraint(newData);
+            buf.renameParameter(0, newBaseAddress);
+            buf.replaceParameterByNewExpression(pos, new Name(getter, newBaseAddress));
+        } else {
+            // cannot bind the MH arg itself, unless oldData is empty
+            assert(oldData == BoundMethodHandle.SpeciesData.EMPTY);
+            newBaseAddress = new Name(L_TYPE).withConstraint(newData);
+            buf.replaceParameterByNewExpression(0, new Name(getter, newBaseAddress));
+            buf.insertParameter(0, newBaseAddress);
+        }
+
+        buf.endEdit();
+        form = buf.lambdaForm();
+        return putInCache(key, form);
+    }
+}
--- a/src/share/classes/java/lang/invoke/MethodHandleImpl.java	Wed Sep 10 18:34:03 2014 +0400
+++ b/src/share/classes/java/lang/invoke/MethodHandleImpl.java	Wed Sep 10 18:34:40 2014 +0400
@@ -530,7 +530,7 @@
      * Pre-initialized NamedFunctions for bootstrapping purposes.
      * Factored in an inner class to delay initialization until first usage.
      */
-    private static class Lazy {
+    static class Lazy {
         private static final Class<?> MHI = MethodHandleImpl.class;
 
         static final NamedFunction NF_checkSpreadArgument;