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.isEmpty()) 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 }