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 26package java.lang.invoke; 27 28import java.util.ArrayList; 29import java.util.Arrays; 30import static java.lang.invoke.LambdaForm.*; 31import 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 */ 36final 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 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} 399