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