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 }