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.arity = lf.arity;
  50         setNames(lf.names);
  51         int result = lf.result;
  52         if (result == LAST_RESULT)  result = length - 1;
  53         if (result >= 0 && lf.names[result].type != V_TYPE)
  54             resultName = lf.names[result];
  55         debugName = lf.debugName;
  56         assert(lf.nameRefsAreLegal());
  57     }
  58 
  59     private LambdaForm lambdaForm() {
  60         assert(!inTrans());  // need endEdit call to tidy things up
  61         return new LambdaForm(debugName, arity, nameArray(), resultIndex());
  62     }
  63 
  64     Name name(int i) {
  65         assert(i < length);
  66         return names[i];
  67     }
  68 
  69     Name[] nameArray() {
  70         return Arrays.copyOf(names, length);
  71     }
  72 
  73     int resultIndex() {
  74         if (resultName == null)  return VOID_RESULT;
  75         int index = indexOf(resultName, names);
  76         assert(index >= 0);
  77         return index;
  78     }
  79 
  80     void setNames(Name[] names2) {
  81         names = originalNames = names2;  // keep a record of where everything was to start with
  82         length = names2.length;
  83         flags = 0;
  84     }
  85 
  86     private boolean verifyArity() {
  87         for (int i = 0; i < arity && i < firstChange; i++) {
  88             assert(names[i].isParam()) : "#" + i + "=" + names[i];
  89         }
  90         for (int i = arity; i < length; i++) {
  91             assert(!names[i].isParam()) : "#" + i + "=" + names[i];
  92         }
  93         for (int i = length; i < names.length; i++) {
  94             assert(names[i] == null) : "#" + i + "=" + names[i];
  95         }
  96         // check resultName also
  97         if (resultName != null) {
  98             int resultIndex = indexOf(resultName, names);
  99             assert(resultIndex >= 0) : "not found: " + resultName.exprString() + Arrays.asList(names);
 100             assert(names[resultIndex] == resultName);
 101         }
 102         return true;
 103     }
 104 
 105     private boolean verifyFirstChange() {
 106         assert(inTrans());
 107         for (int i = 0; i < length; i++) {
 108             if (names[i] != originalNames[i]) {
 109                 assert(firstChange == i) : Arrays.asList(firstChange, i, originalNames[i].exprString(), Arrays.asList(names));
 110                 return true;
 111             }
 112         }
 113         assert(firstChange == length) : Arrays.asList(firstChange, Arrays.asList(names));
 114         return true;
 115     }
 116 
 117     private static int indexOf(NamedFunction fn, NamedFunction[] fns) {
 118         for (int i = 0; i < fns.length; i++) {
 119             if (fns[i] == fn)  return i;
 120         }
 121         return -1;
 122     }
 123 
 124     private static int indexOf(Name n, Name[] ns) {
 125         for (int i = 0; i < ns.length; i++) {
 126             if (ns[i] == n)  return i;
 127         }
 128         return -1;
 129     }
 130 
 131     boolean inTrans() {
 132         return (flags & F_TRANS) != 0;
 133     }
 134 
 135     int ownedCount() {
 136         return flags & F_OWNED;
 137     }
 138 
 139     void growNames(int insertPos, int growLength) {
 140         int oldLength = length;
 141         int newLength = oldLength + growLength;
 142         int oc = ownedCount();
 143         if (oc == 0 || newLength > names.length) {
 144             names = Arrays.copyOf(names, (names.length + growLength) * 5 / 4);
 145             if (oc == 0) {
 146                 flags++;
 147                 oc++;
 148                 assert(ownedCount() == oc);
 149             }
 150         }
 151         if (originalNames != null && originalNames.length < names.length) {
 152             originalNames = Arrays.copyOf(originalNames, names.length);
 153             if (oc == 1) {
 154                 flags++;
 155                 oc++;
 156                 assert(ownedCount() == oc);
 157             }
 158         }
 159         if (growLength == 0)  return;
 160         int insertEnd = insertPos + growLength;
 161         int tailLength = oldLength - insertPos;
 162         System.arraycopy(names, insertPos, names, insertEnd, tailLength);
 163         Arrays.fill(names, insertPos, insertEnd, null);
 164         if (originalNames != null) {
 165             System.arraycopy(originalNames, insertPos, originalNames, insertEnd, tailLength);
 166             Arrays.fill(originalNames, insertPos, insertEnd, null);
 167         }
 168         length = newLength;
 169         if (firstChange >= insertPos) {
 170             firstChange += growLength;
 171         }
 172     }
 173 
 174     int lastIndexOf(Name n) {
 175         int result = -1;
 176         for (int i = 0; i < length; i++) {
 177             if (names[i] == n)  result = i;
 178         }
 179         return result;
 180     }
 181 
 182     /** We have just overwritten the name at pos1 with the name at pos2.
 183      *  This means that there are two copies of the name, which we will have to fix later.
 184      */
 185     private void noteDuplicate(int pos1, int pos2) {
 186         Name n = names[pos1];
 187         assert(n == names[pos2]);
 188         assert(originalNames[pos1] != null);  // something was replaced at pos1
 189         assert(originalNames[pos2] == null || originalNames[pos2] == n);
 190         if (dups == null) {
 191             dups = new ArrayList<>();
 192         }
 193         dups.add(n);
 194     }
 195 
 196     /** Replace duplicate names by nulls, and remove all nulls. */
 197     private void clearDuplicatesAndNulls() {
 198         if (dups != null) {
 199             // Remove duplicates.
 200             assert(ownedCount() >= 1);
 201             for (Name dup : dups) {
 202                 for (int i = firstChange; i < length; i++) {
 203                     if (names[i] == dup && originalNames[i] != dup) {
 204                         names[i] = null;
 205                         assert(Arrays.asList(names).contains(dup));
 206                         break;  // kill only one dup
 207                     }
 208                 }
 209             }
 210             dups.clear();
 211         }
 212         // Now that we are done with originalNames, remove "killed" names.
 213         int oldLength = length;
 214         for (int i = firstChange; i < length; i++) {
 215             if (names[i] == null) {
 216                 System.arraycopy(names, i + 1, names, i, (--length - i));
 217                 --i;  // restart loop at this position
 218             }
 219         }
 220         if (length < oldLength) {
 221             Arrays.fill(names, length, oldLength, null);
 222         }
 223         assert(!Arrays.asList(names).subList(0, length).contains(null));
 224     }
 225 
 226     /** Create a private, writable copy of names.
 227      *  Preserve the original copy, for reference.
 228      */
 229     void startEdit() {
 230         assert(verifyArity());
 231         int oc = ownedCount();
 232         assert(!inTrans());  // no nested transactions
 233         flags |= F_TRANS;
 234         Name[] oldNames = names;
 235         Name[] ownBuffer = (oc == 2 ? originalNames : null);
 236         assert(ownBuffer != oldNames);
 237         if (ownBuffer != null && ownBuffer.length >= length) {
 238             names = copyNamesInto(ownBuffer);
 239         } else {
 240             // make a new buffer to hold the names
 241             final int SLOP = 2;
 242             names = Arrays.copyOf(oldNames, Math.max(length + SLOP, oldNames.length));
 243             if (oc < 2)  ++flags;
 244             assert(ownedCount() == oc + 1);
 245         }
 246         originalNames = oldNames;
 247         assert(originalNames != names);
 248         firstChange = length;
 249         assert(inTrans());
 250     }
 251 
 252     private void changeName(int i, Name name) {
 253         assert(inTrans());
 254         assert(i < length);
 255         Name oldName = names[i];
 256         assert(oldName == originalNames[i]);  // no multiple changes
 257         assert(verifyFirstChange());
 258         if (ownedCount() == 0)
 259             growNames(0, 0);
 260         names[i] = name;
 261         if (firstChange > i) {
 262             firstChange = i;
 263         }
 264         if (resultName != null && resultName == oldName) {
 265             resultName = name;
 266         }
 267     }
 268 
 269     /** Change the result name.  Null means a void result. */
 270     void setResult(Name name) {
 271         assert(name == null || lastIndexOf(name) >= 0);
 272         resultName = name;
 273     }
 274 
 275     /** Finish a transaction. */
 276     LambdaForm endEdit() {
 277         assert(verifyFirstChange());
 278         // Assuming names have been changed pairwise from originalNames[i] to names[i],
 279         // update arguments to ensure referential integrity.
 280         for (int i = Math.max(firstChange, arity); i < length; i++) {
 281             Name name = names[i];
 282             if (name == null)  continue;  // space for removed duplicate
 283             Name newName = name.replaceNames(originalNames, names, firstChange, i);
 284             if (newName != name) {
 285                 names[i] = newName;
 286                 if (resultName == name) {
 287                     resultName = newName;
 288                 }
 289             }
 290         }
 291         assert(inTrans());
 292         flags &= ~F_TRANS;
 293         clearDuplicatesAndNulls();
 294         originalNames = null;
 295         // If any parameters have been changed, then reorder them as needed.
 296         // This is a "sheep-and-goats" stable sort, pushing all non-parameters
 297         // to the right of all parameters.
 298         if (firstChange < arity) {
 299             Name[] exprs = new Name[arity - firstChange];
 300             int argp = firstChange, exprp = 0;
 301             for (int i = firstChange; i < arity; i++) {
 302                 Name name = names[i];
 303                 if (name.isParam()) {
 304                     names[argp++] = name;
 305                 } else {
 306                     exprs[exprp++] = name;
 307                 }
 308             }
 309             assert(exprp == (arity - argp));
 310             // copy the exprs just after the last remaining param
 311             System.arraycopy(exprs, 0, names, argp, exprp);
 312             // adjust arity
 313             arity -= exprp;
 314         }
 315         assert(verifyArity());
 316         return lambdaForm();
 317     }
 318 
 319     private Name[] copyNamesInto(Name[] buffer) {
 320         System.arraycopy(names, 0, buffer, 0, length);
 321         Arrays.fill(buffer, length, buffer.length, null);
 322         return buffer;
 323     }
 324 
 325     /** Replace any Name whose function is in oldFns with a copy
 326      *  whose function is in the corresponding position in newFns.
 327      *  Only do this if the arguments are exactly equal to the given.
 328      */
 329     LambdaFormBuffer replaceFunctions(NamedFunction[] oldFns, NamedFunction[] newFns,
 330                                       Object... forArguments) {
 331         assert(inTrans());
 332         if (oldFns.length == 0)  return this;
 333         for (int i = arity; i < length; i++) {
 334             Name n = names[i];
 335             int nfi = indexOf(n.function, oldFns);
 336             if (nfi >= 0 && Arrays.equals(n.arguments, forArguments)) {
 337                 changeName(i, new Name(newFns[nfi], n.arguments));
 338             }
 339         }
 340         return this;
 341     }
 342 
 343     private void replaceName(int pos, Name binding) {
 344         assert(inTrans());
 345         assert(verifyArity());
 346         assert(pos < arity);
 347         Name param = names[pos];
 348         assert(param.isParam());
 349         assert(param.type == binding.type);
 350         changeName(pos, binding);
 351     }
 352 
 353     /** Replace a parameter by a fresh parameter. */
 354     LambdaFormBuffer renameParameter(int pos, Name newParam) {
 355         assert(newParam.isParam());
 356         replaceName(pos, newParam);
 357         return this;
 358     }
 359 
 360     /** Replace a parameter by a fresh expression. */
 361     LambdaFormBuffer replaceParameterByNewExpression(int pos, Name binding) {
 362         assert(!binding.isParam());
 363         assert(lastIndexOf(binding) < 0);  // else use replaceParameterByCopy
 364         replaceName(pos, binding);
 365         return this;
 366     }
 367 
 368     /** Replace a parameter by another parameter or expression already in the form. */
 369     LambdaFormBuffer replaceParameterByCopy(int pos, int valuePos) {
 370         assert(pos != valuePos);
 371         replaceName(pos, names[valuePos]);
 372         noteDuplicate(pos, valuePos);  // temporarily, will occur twice in the names array
 373         return this;
 374     }
 375 
 376     private void insertName(int pos, Name expr, boolean isParameter) {
 377         assert(inTrans());
 378         assert(verifyArity());
 379         assert(isParameter ? pos <= arity : pos >= arity);
 380         growNames(pos, 1);
 381         if (isParameter)  arity += 1;
 382         changeName(pos, expr);
 383     }
 384 
 385     /** Insert a fresh expression. */
 386     LambdaFormBuffer insertExpression(int pos, Name expr) {
 387         assert(!expr.isParam());
 388         insertName(pos, expr, false);
 389         return this;
 390     }
 391 
 392     /** Insert a fresh parameter. */
 393     LambdaFormBuffer insertParameter(int pos, Name param) {
 394         assert(param.isParam());
 395         insertName(pos, param, true);
 396         return this;
 397     }
 398 }