Mon, 10 Dec 2012 16:21:26 +0000
8003967: detect and remove all mutable implicit static enum fields in langtools
Reviewed-by: jjg
1 /*
2 * Copyright (c) 1999, 2012, 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 */
26 package com.sun.tools.javac.util;
28 import java.lang.reflect.Array;
29 import java.util.ArrayList;
30 import java.util.Collection;
31 import java.util.Collections;
32 import java.util.Iterator;
33 import java.util.AbstractCollection;
34 import java.util.ListIterator;
35 import java.util.NoSuchElementException;
37 /** A class for generic linked lists. Links are supposed to be
38 * immutable, the only exception being the incremental construction of
39 * lists via ListBuffers. List is the main container class in
40 * GJC. Most data structures and algorthms in GJC use lists rather
41 * than arrays.
42 *
43 * <p>Lists are always trailed by a sentinel element, whose head and tail
44 * are both null.
45 *
46 * <p><b>This is NOT part of any supported API.
47 * If you write code that depends on this, you do so at your own risk.
48 * This code and its internal interfaces are subject to change or
49 * deletion without notice.</b>
50 */
51 public class List<A> extends AbstractCollection<A> implements java.util.List<A> {
53 /** The first element of the list, supposed to be immutable.
54 */
55 public A head;
57 /** The remainder of the list except for its first element, supposed
58 * to be immutable.
59 */
60 //@Deprecated
61 public List<A> tail;
63 /** Construct a list given its head and tail.
64 */
65 List(A head, List<A> tail) {
66 this.tail = tail;
67 this.head = head;
68 }
70 /** Construct an empty list.
71 */
72 @SuppressWarnings("unchecked")
73 public static <A> List<A> nil() {
74 return (List<A>)EMPTY_LIST;
75 }
77 private static final List<?> EMPTY_LIST = new List<Object>(null,null) {
78 public List<Object> setTail(List<Object> tail) {
79 throw new UnsupportedOperationException();
80 }
81 public boolean isEmpty() {
82 return true;
83 }
84 };
86 /** Returns the list obtained from 'l' after removing all elements 'elem'
87 */
88 public static <A> List<A> filter(List<A> l, A elem) {
89 Assert.checkNonNull(elem);
90 List<A> res = List.nil();
91 for (A a : l) {
92 if (a != null && !a.equals(elem)) {
93 res = res.prepend(a);
94 }
95 }
96 return res.reverse();
97 }
99 /** Construct a list consisting of given element.
100 */
101 public static <A> List<A> of(A x1) {
102 return new List<A>(x1, List.<A>nil());
103 }
105 /** Construct a list consisting of given elements.
106 */
107 public static <A> List<A> of(A x1, A x2) {
108 return new List<A>(x1, of(x2));
109 }
111 /** Construct a list consisting of given elements.
112 */
113 public static <A> List<A> of(A x1, A x2, A x3) {
114 return new List<A>(x1, of(x2, x3));
115 }
117 /** Construct a list consisting of given elements.
118 */
119 @SuppressWarnings({"varargs", "unchecked"})
120 public static <A> List<A> of(A x1, A x2, A x3, A... rest) {
121 return new List<A>(x1, new List<A>(x2, new List<A>(x3, from(rest))));
122 }
124 /**
125 * Construct a list consisting all elements of given array.
126 * @param array an array; if {@code null} return an empty list
127 */
128 public static <A> List<A> from(A[] array) {
129 List<A> xs = nil();
130 if (array != null)
131 for (int i = array.length - 1; i >= 0; i--)
132 xs = new List<A>(array[i], xs);
133 return xs;
134 }
136 public static <A> List<A> from(Iterable<? extends A> coll) {
137 List<A> xs = nil();
138 for (A a : coll) {
139 xs = new List<A>(a, xs);
140 }
141 return xs;
142 }
144 /** Construct a list consisting of a given number of identical elements.
145 * @param len The number of elements in the list.
146 * @param init The value of each element.
147 */
148 @Deprecated
149 public static <A> List<A> fill(int len, A init) {
150 List<A> l = nil();
151 for (int i = 0; i < len; i++) l = new List<A>(init, l);
152 return l;
153 }
155 /** Does list have no elements?
156 */
157 @Override
158 public boolean isEmpty() {
159 return tail == null;
160 }
162 /** Does list have elements?
163 */
164 //@Deprecated
165 public boolean nonEmpty() {
166 return tail != null;
167 }
169 /** Return the number of elements in this list.
170 */
171 //@Deprecated
172 public int length() {
173 List<A> l = this;
174 int len = 0;
175 while (l.tail != null) {
176 l = l.tail;
177 len++;
178 }
179 return len;
180 }
181 @Override
182 public int size() {
183 return length();
184 }
186 public List<A> setTail(List<A> tail) {
187 this.tail = tail;
188 return tail;
189 }
191 /** Prepend given element to front of list, forming and returning
192 * a new list.
193 */
194 public List<A> prepend(A x) {
195 return new List<A>(x, this);
196 }
198 /** Prepend given list of elements to front of list, forming and returning
199 * a new list.
200 */
201 public List<A> prependList(List<A> xs) {
202 if (this.isEmpty()) return xs;
203 if (xs.isEmpty()) return this;
204 if (xs.tail.isEmpty()) return prepend(xs.head);
205 // return this.prependList(xs.tail).prepend(xs.head);
206 List<A> result = this;
207 List<A> rev = xs.reverse();
208 Assert.check(rev != xs);
209 // since xs.reverse() returned a new list, we can reuse the
210 // individual List objects, instead of allocating new ones.
211 while (rev.nonEmpty()) {
212 List<A> h = rev;
213 rev = rev.tail;
214 h.setTail(result);
215 result = h;
216 }
217 return result;
218 }
220 /** Reverse list.
221 * If the list is empty or a singleton, then the same list is returned.
222 * Otherwise a new list is formed.
223 */
224 public List<A> reverse() {
225 // if it is empty or a singleton, return itself
226 if (isEmpty() || tail.isEmpty())
227 return this;
229 List<A> rev = nil();
230 for (List<A> l = this; l.nonEmpty(); l = l.tail)
231 rev = new List<A>(l.head, rev);
232 return rev;
233 }
235 /** Append given element at length, forming and returning
236 * a new list.
237 */
238 public List<A> append(A x) {
239 return of(x).prependList(this);
240 }
242 /** Append given list at length, forming and returning
243 * a new list.
244 */
245 public List<A> appendList(List<A> x) {
246 return x.prependList(this);
247 }
249 /**
250 * Append given list buffer at length, forming and returning a new
251 * list.
252 */
253 public List<A> appendList(ListBuffer<A> x) {
254 return appendList(x.toList());
255 }
257 /** Copy successive elements of this list into given vector until
258 * list is exhausted or end of vector is reached.
259 */
260 @Override @SuppressWarnings("unchecked")
261 public <T> T[] toArray(T[] vec) {
262 int i = 0;
263 List<A> l = this;
264 Object[] dest = vec;
265 while (l.nonEmpty() && i < vec.length) {
266 dest[i] = l.head;
267 l = l.tail;
268 i++;
269 }
270 if (l.isEmpty()) {
271 if (i < vec.length)
272 vec[i] = null;
273 return vec;
274 }
276 vec = (T[])Array.newInstance(vec.getClass().getComponentType(), size());
277 return toArray(vec);
278 }
280 public Object[] toArray() {
281 return toArray(new Object[size()]);
282 }
284 /** Form a string listing all elements with given separator character.
285 */
286 public String toString(String sep) {
287 if (isEmpty()) {
288 return "";
289 } else {
290 StringBuilder buf = new StringBuilder();
291 buf.append(head);
292 for (List<A> l = tail; l.nonEmpty(); l = l.tail) {
293 buf.append(sep);
294 buf.append(l.head);
295 }
296 return buf.toString();
297 }
298 }
300 /** Form a string listing all elements with comma as the separator character.
301 */
302 @Override
303 public String toString() {
304 return toString(",");
305 }
307 /** Compute a hash code, overrides Object
308 * @see java.util.List#hashCode
309 */
310 @Override
311 public int hashCode() {
312 List<A> l = this;
313 int h = 1;
314 while (l.tail != null) {
315 h = h * 31 + (l.head == null ? 0 : l.head.hashCode());
316 l = l.tail;
317 }
318 return h;
319 }
321 /** Is this list the same as other list?
322 * @see java.util.List#equals
323 */
324 @Override
325 public boolean equals(Object other) {
326 if (other instanceof List<?>)
327 return equals(this, (List<?>)other);
328 if (other instanceof java.util.List<?>) {
329 List<A> t = this;
330 Iterator<?> oIter = ((java.util.List<?>) other).iterator();
331 while (t.tail != null && oIter.hasNext()) {
332 Object o = oIter.next();
333 if ( !(t.head == null ? o == null : t.head.equals(o)))
334 return false;
335 t = t.tail;
336 }
337 return (t.isEmpty() && !oIter.hasNext());
338 }
339 return false;
340 }
342 /** Are the two lists the same?
343 */
344 public static boolean equals(List<?> xs, List<?> ys) {
345 while (xs.tail != null && ys.tail != null) {
346 if (xs.head == null) {
347 if (ys.head != null) return false;
348 } else {
349 if (!xs.head.equals(ys.head)) return false;
350 }
351 xs = xs.tail;
352 ys = ys.tail;
353 }
354 return xs.tail == null && ys.tail == null;
355 }
357 /** Does the list contain the specified element?
358 */
359 @Override
360 public boolean contains(Object x) {
361 List<A> l = this;
362 while (l.tail != null) {
363 if (x == null) {
364 if (l.head == null) return true;
365 } else {
366 if (l.head.equals(x)) return true;
367 }
368 l = l.tail;
369 }
370 return false;
371 }
373 /** The last element in the list, if any, or null.
374 */
375 public A last() {
376 A last = null;
377 List<A> t = this;
378 while (t.tail != null) {
379 last = t.head;
380 t = t.tail;
381 }
382 return last;
383 }
385 @SuppressWarnings("unchecked")
386 public static <T> List<T> convert(Class<T> klass, List<?> list) {
387 if (list == null)
388 return null;
389 for (Object o : list)
390 klass.cast(o);
391 return (List<T>)list;
392 }
394 private static final Iterator<?> EMPTYITERATOR = new Iterator<Object>() {
395 public boolean hasNext() {
396 return false;
397 }
398 public Object next() {
399 throw new java.util.NoSuchElementException();
400 }
401 public void remove() {
402 throw new UnsupportedOperationException();
403 }
404 };
406 @SuppressWarnings("unchecked")
407 private static <A> Iterator<A> emptyIterator() {
408 return (Iterator<A>)EMPTYITERATOR;
409 }
411 @Override
412 public Iterator<A> iterator() {
413 if (tail == null)
414 return emptyIterator();
415 return new Iterator<A>() {
416 List<A> elems = List.this;
417 public boolean hasNext() {
418 return elems.tail != null;
419 }
420 public A next() {
421 if (elems.tail == null)
422 throw new NoSuchElementException();
423 A result = elems.head;
424 elems = elems.tail;
425 return result;
426 }
427 public void remove() {
428 throw new UnsupportedOperationException();
429 }
430 };
431 }
433 public A get(int index) {
434 if (index < 0)
435 throw new IndexOutOfBoundsException(String.valueOf(index));
437 List<A> l = this;
438 for (int i = index; i-- > 0 && !l.isEmpty(); l = l.tail)
439 ;
441 if (l.isEmpty())
442 throw new IndexOutOfBoundsException("Index: " + index + ", " +
443 "Size: " + size());
444 return l.head;
445 }
447 public boolean addAll(int index, Collection<? extends A> c) {
448 if (c.isEmpty())
449 return false;
450 throw new UnsupportedOperationException();
451 }
453 public A set(int index, A element) {
454 throw new UnsupportedOperationException();
455 }
457 public void add(int index, A element) {
458 throw new UnsupportedOperationException();
459 }
461 public A remove(int index) {
462 throw new UnsupportedOperationException();
463 }
465 public int indexOf(Object o) {
466 int i = 0;
467 for (List<A> l = this; l.tail != null; l = l.tail, i++) {
468 if (l.head == null ? o == null : l.head.equals(o))
469 return i;
470 }
471 return -1;
472 }
474 public int lastIndexOf(Object o) {
475 int last = -1;
476 int i = 0;
477 for (List<A> l = this; l.tail != null; l = l.tail, i++) {
478 if (l.head == null ? o == null : l.head.equals(o))
479 last = i;
480 }
481 return last;
482 }
484 public ListIterator<A> listIterator() {
485 return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator();
486 }
488 public ListIterator<A> listIterator(int index) {
489 return Collections.unmodifiableList(new ArrayList<A>(this)).listIterator(index);
490 }
492 public java.util.List<A> subList(int fromIndex, int toIndex) {
493 if (fromIndex < 0 || toIndex > size() || fromIndex > toIndex)
494 throw new IllegalArgumentException();
496 ArrayList<A> a = new ArrayList<A>(toIndex - fromIndex);
497 int i = 0;
498 for (List<A> l = this; l.tail != null; l = l.tail, i++) {
499 if (i == toIndex)
500 break;
501 if (i >= fromIndex)
502 a.add(l.head);
503 }
505 return Collections.unmodifiableList(a);
506 }
507 }