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 LambdaFormBuffer(LambdaForm lf)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 lambdaForm()60 private LambdaForm lambdaForm() { 61 assert(!inTrans()); // need endEdit call to tidy things up 62 return new LambdaForm(arity, nameArray(), resultIndex()); 63 } 64 name(int i)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 setNames(Name[] names2)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 verifyArity()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 verifyFirstChange()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 indexOf(NamedFunction fn, List<NamedFunction> fns)118 private static int indexOf(NamedFunction fn, List<NamedFunction> fns) { 119 for (int i = 0; i < fns.size(); i++) { 120 if (fns.get(i) == fn) return i; 121 } 122 return -1; 123 } 124 indexOf(Name n, Name[] ns)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 inTrans()132 boolean inTrans() { 133 return (flags & F_TRANS) != 0; 134 } 135 ownedCount()136 int ownedCount() { 137 return flags & F_OWNED; 138 } 139 growNames(int insertPos, int growLength)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 lastIndexOf(Name n)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 */ noteDuplicate(int pos1, int pos2)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. */ clearDuplicatesAndNulls()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 */ startEdit()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 changeName(int i, Name name)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. */ setResult(Name name)271 void setResult(Name name) { 272 assert(name == null || lastIndexOf(name) >= 0); 273 resultName = name; 274 } 275 276 /** Finish a transaction. */ endEdit()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 copyNamesInto(Name[] buffer)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 */ replaceFunctions(List<NamedFunction> oldFns, List<NamedFunction> newFns, Object... forArguments)330 LambdaFormBuffer replaceFunctions(List<NamedFunction> oldFns, List<NamedFunction> newFns, 331 Object... forArguments) { 332 assert(inTrans()); 333 if (oldFns.isEmpty()) return this; 334 for (int i = arity; i < length; i++) { 335 Name n = names[i]; 336 int nfi = indexOf(n.function, oldFns); 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 replaceName(int pos, Name binding)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 } 400