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