1 /*
   2  * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.lang.invoke;
  27 
  28 import java.util.ArrayList;
  29 import java.util.Arrays;
  30 import static java.lang.invoke.LambdaForm.*;
  31 import static java.lang.invoke.LambdaForm.BasicType.*;
  32 
  33 /** Working storage for an LF that is being transformed.
  34  *  Similarly to a StringBuffer, the editing can take place in multiple steps.
  35  */
  36 final class LambdaFormBuffer {
  37     private int arity, length;
  38     private Name[] names;
  39     private Name[] originalNames;  // snapshot of pre-transaction names
  40     private byte flags;
  41     private int firstChange;
  42     private Name resultName;
  43     private String debugName;
  44     private ArrayList<Name> dups;
  45 
  46     private static final int F_TRANS = 0x10, F_OWNED = 0x03;
  47 
  48     LambdaFormBuffer(LambdaForm lf) {
  49         this(lf.arity, lf.names, lf.result);
  50         debugName = lf.debugName;
  51         assert(lf.nameRefsAreLegal());
  52     }
  53 
  54     private LambdaFormBuffer(int arity, Name[] names, int result) {
  55         this.arity = arity;
  56         setNames(names);
  57         if (result == LAST_RESULT)  result = length - 1;
  58         if (result >= 0 && names[result].type != V_TYPE)
  59             resultName = names[result];
  60     }
  61 
  62     LambdaForm lambdaForm() {
  63         assert(!inTrans());  // need endEdit call to tidy things up
  64         return new LambdaForm(debugName, arity, nameArray(), resultIndex());
  65     }
  66 
  67     Name name(int i) {
  68         assert(i < length);
  69         return names[i];
  70     }
  71 
  72     Name[] nameArray() {
  73         return Arrays.copyOf(names, length);
  74     }
  75 
  76     int resultIndex() {
  77         if (resultName == null)  return VOID_RESULT;
  78         int index = indexOf(resultName, names);
  79         assert(index >= 0);
  80         return index;
  81     }
  82 
  83     void setNames(Name[] names2) {
  84         names = originalNames = names2;  // keep a record of where everything was to start with
  85         length = names2.length;
  86         flags = 0;
  87     }
  88 
  89     private boolean verifyArity() {
  90         for (int i = 0; i < arity && i < firstChange; i++) {
  91             assert(names[i].isParam()) : "#" + i + "=" + names[i];
  92         }
  93         for (int i = arity; i < length; i++) {
  94             assert(!names[i].isParam()) : "#" + i + "=" + names[i];
  95         }
  96         for (int i = length; i < names.length; i++) {
  97             assert(names[i] == null) : "#" + i + "=" + names[i];
  98         }
  99         // check resultName also
 100         if (resultName != null) {
 101             int resultIndex = indexOf(resultName, names);
 102             assert(resultIndex >= 0) : "not found: " + resultName.exprString() + Arrays.asList(names);
 103             assert(names[resultIndex] == resultName);
 104         }
 105         return true;
 106     }
 107 
 108     private boolean verifyFirstChange() {
 109         assert(inTrans());
 110         for (int i = 0; i < length; i++) {
 111             if (names[i] != originalNames[i]) {
 112                 assert(firstChange == i) : Arrays.asList(firstChange, i, originalNames[i].exprString(), Arrays.asList(names));
 113                 return true;
 114             }
 115         }
 116         assert(firstChange == length) : Arrays.asList(firstChange, Arrays.asList(names));
 117         return true;
 118     }
 119 
 120     private static int indexOf(NamedFunction fn, NamedFunction[] fns) {
 121         for (int i = 0; i < fns.length; i++) {
 122             if (fns[i] == fn)  return i;
 123         }
 124         return -1;
 125     }
 126 
 127     private static int indexOf(Name n, Name[] ns) {
 128         for (int i = 0; i < ns.length; i++) {
 129             if (ns[i] == n)  return i;
 130         }
 131         return -1;
 132     }
 133 
 134     boolean inTrans() {
 135         return (flags & F_TRANS) != 0;
 136     }
 137 
 138     int ownedCount() {
 139         return flags & F_OWNED;
 140     }
 141 
 142     void growNames(int insertPos, int growLength) {
 143         int oldLength = length;
 144         int newLength = oldLength + growLength;
 145         int oc = ownedCount();
 146         if (oc == 0 || newLength > names.length) {
 147             names = Arrays.copyOf(names, (names.length + growLength) * 5 / 4);
 148             if (oc == 0) {
 149                 flags++;
 150                 oc++;
 151                 assert(ownedCount() == oc);
 152             }
 153         }
 154         if (originalNames != null && originalNames.length < names.length) {
 155             originalNames = Arrays.copyOf(originalNames, names.length);
 156             if (oc == 1) {
 157                 flags++;
 158                 oc++;
 159                 assert(ownedCount() == oc);
 160             }
 161         }
 162         if (growLength == 0)  return;
 163         int insertEnd = insertPos + growLength;
 164         int tailLength = oldLength - insertPos;
 165         System.arraycopy(names, insertPos, names, insertEnd, tailLength);
 166         Arrays.fill(names, insertPos, insertEnd, null);
 167         if (originalNames != null) {
 168             System.arraycopy(originalNames, insertPos, originalNames, insertEnd, tailLength);
 169             Arrays.fill(originalNames, insertPos, insertEnd, null);
 170         }
 171         length = newLength;
 172         if (firstChange >= insertPos) {
 173             firstChange += growLength;
 174         }
 175     }
 176 
 177     int lastIndexOf(Name n) {
 178         int result = -1;
 179         for (int i = 0; i < length; i++) {
 180             if (names[i] == n)  result = i;
 181         }
 182         return result;
 183     }
 184 
 185     /** We have just overwritten the name at pos1 with the name at pos2.
 186      *  This means that there are two copies of the name, which we will have to fix later.
 187      */
 188     private void noteDuplicate(int pos1, int pos2) {
 189         Name n = names[pos1];
 190         assert(n == names[pos2]);
 191         assert(originalNames[pos1] != null);  // something was replaced at pos1
 192         assert(originalNames[pos2] == null || originalNames[pos2] == n);
 193         if (dups == null) {
 194             dups = new ArrayList<>();
 195         }
 196         dups.add(n);
 197     }
 198 
 199     /** Replace duplicate names by nulls, and remove all nulls. */
 200     private void clearDuplicatesAndNulls() {
 201         if (dups != null) {
 202             // Remove duplicates.
 203             assert(ownedCount() >= 1);
 204             for (Name dup : dups) {
 205                 for (int i = firstChange; i < length; i++) {
 206                     if (names[i] == dup && originalNames[i] != dup) {
 207                         names[i] = null;
 208                         assert(Arrays.asList(names).contains(dup));
 209                         break;  // kill only one dup
 210                     }
 211                 }
 212             }
 213             dups.clear();
 214         }
 215         // Now that we are done with originalNames, remove "killed" names.
 216         int oldLength = length;
 217         for (int i = firstChange; i < length; i++) {
 218             if (names[i] == null) {
 219                 System.arraycopy(names, i + 1, names, i, (--length - i));
 220                 --i;  // restart loop at this position
 221             }
 222         }
 223         if (length < oldLength) {
 224             Arrays.fill(names, length, oldLength, null);
 225         }
 226         assert(!Arrays.asList(names).subList(0, length).contains(null));
 227     }
 228 
 229     /** Create a private, writable copy of names.
 230      *  Preserve the original copy, for reference.
 231      */
 232     void startEdit() {
 233         assert(verifyArity());
 234         int oc = ownedCount();
 235         assert(!inTrans());  // no nested transactions
 236         flags |= F_TRANS;
 237         Name[] oldNames = names;
 238         Name[] ownBuffer = (oc == 2 ? originalNames : null);
 239         assert(ownBuffer != oldNames);
 240         if (ownBuffer != null && ownBuffer.length >= length) {
 241             names = copyNamesInto(ownBuffer);
 242         } else {
 243             // make a new buffer to hold the names
 244             final int SLOP = 2;
 245             names = Arrays.copyOf(oldNames, Math.max(length + SLOP, oldNames.length));
 246             if (oc < 2)  ++flags;
 247             assert(ownedCount() == oc + 1);
 248         }
 249         originalNames = oldNames;
 250         assert(originalNames != names);
 251         firstChange = length;
 252         assert(inTrans());
 253     }
 254 
 255     private void changeName(int i, Name name) {
 256         assert(inTrans());
 257         assert(i < length);
 258         Name oldName = names[i];
 259         assert(oldName == originalNames[i]);  // no multiple changes
 260         assert(verifyFirstChange());
 261         if (ownedCount() == 0)
 262             growNames(0, 0);
 263         names[i] = name;
 264         if (firstChange > i) {
 265             firstChange = i;
 266         }
 267         if (resultName != null && resultName == oldName) {
 268             resultName = name;
 269         }
 270     }
 271 
 272     /** Change the result name.  Null means a void result. */
 273     void setResult(Name name) {
 274         assert(name == null || lastIndexOf(name) >= 0);
 275         resultName = name;
 276     }
 277 
 278     /** Finish a transaction. */
 279     void endEdit() {
 280         assert(verifyFirstChange());
 281         // Assuming names have been changed pairwise from originalNames[i] to names[i],
 282         // update arguments to ensure referential integrity.
 283         for (int i = Math.max(firstChange, arity); i < length; i++) {
 284             Name name = names[i];
 285             if (name == null)  continue;  // space for removed duplicate
 286             Name newName = name.replaceNames(originalNames, names, firstChange, i);
 287             if (newName != name) {
 288                 names[i] = newName;
 289                 if (resultName == name) {
 290                     resultName = newName;
 291                 }
 292             }
 293         }
 294         assert(inTrans());
 295         flags &= ~F_TRANS;
 296         clearDuplicatesAndNulls();
 297         originalNames = null;
 298         // If any parameters have been changed, then reorder them as needed.
 299         // This is a "sheep-and-goats" stable sort, pushing all non-parameters
 300         // to the right of all parameters.
 301         if (firstChange < arity) {
 302             Name[] exprs = new Name[arity - firstChange];
 303             int argp = firstChange, exprp = 0;
 304             for (int i = firstChange; i < arity; i++) {
 305                 Name name = names[i];
 306                 if (name.isParam()) {
 307                     names[argp++] = name;
 308                 } else {
 309                     exprs[exprp++] = name;
 310                 }
 311             }
 312             assert(exprp == (arity - argp));
 313             // copy the exprs just after the last remaining param
 314             System.arraycopy(exprs, 0, names, argp, exprp);
 315             // adjust arity
 316             arity -= exprp;
 317         }
 318         assert(verifyArity());
 319     }
 320 
 321     private Name[] copyNamesInto(Name[] buffer) {
 322         System.arraycopy(names, 0, buffer, 0, length);
 323         Arrays.fill(buffer, length, buffer.length, null);
 324         return buffer;
 325     }
 326 
 327     /** Replace any Name whose function is in oldFns with a copy
 328      *  whose function is in the corresponding position in newFns.
 329      *  Only do this if the arguments are exactly equal to the given.
 330      */
 331     LambdaFormBuffer replaceFunctions(NamedFunction[] oldFns, NamedFunction[] newFns,
 332                                       Object... forArguments) {
 333         assert(inTrans());
 334         if (oldFns.length == 0)  return this;
 335         for (int i = arity; i < length; i++) {
 336             Name n = names[i];
 337             int nfi = indexOf(n.function, oldFns);
 338             if (nfi >= 0 && Arrays.equals(n.arguments, forArguments)) {
 339                 changeName(i, new Name(newFns[nfi], n.arguments));
 340             }
 341         }
 342         return this;
 343     }
 344 
 345     private void replaceName(int pos, Name binding) {
 346         assert(inTrans());
 347         assert(verifyArity());
 348         assert(pos < arity);
 349         Name param = names[pos];
 350         assert(param.isParam());
 351         assert(param.type == binding.type);
 352         changeName(pos, binding);
 353     }
 354 
 355     /** Replace a parameter by a fresh parameter. */
 356     LambdaFormBuffer renameParameter(int pos, Name newParam) {
 357         assert(newParam.isParam());
 358         replaceName(pos, newParam);
 359         return this;
 360     }
 361 
 362     /** Replace a parameter by a fresh expression. */
 363     LambdaFormBuffer replaceParameterByNewExpression(int pos, Name binding) {
 364         assert(!binding.isParam());
 365         assert(lastIndexOf(binding) < 0);  // else use replaceParameterByCopy
 366         replaceName(pos, binding);
 367         return this;
 368     }
 369 
 370     /** Replace a parameter by another parameter or expression already in the form. */
 371     LambdaFormBuffer replaceParameterByCopy(int pos, int valuePos) {
 372         assert(pos != valuePos);
 373         replaceName(pos, names[valuePos]);
 374         noteDuplicate(pos, valuePos);  // temporarily, will occur twice in the names array
 375         return this;
 376     }
 377 
 378     private void insertName(int pos, Name expr, boolean isParameter) {
 379         assert(inTrans());
 380         assert(verifyArity());
 381         assert(isParameter ? pos <= arity : pos >= arity);
 382         growNames(pos, 1);
 383         if (isParameter)  arity += 1;
 384         changeName(pos, expr);
 385     }
 386 
 387     /** Insert a fresh expression. */
 388     LambdaFormBuffer insertExpression(int pos, Name expr) {
 389         assert(!expr.isParam());
 390         insertName(pos, expr, false);
 391         return this;
 392     }
 393 
 394     /** Insert a fresh parameter. */
 395     LambdaFormBuffer insertParameter(int pos, Name param) {
 396         assert(param.isParam());
 397         insertName(pos, param, true);
 398         return this;
 399     }
 400 }