Lightweight collections. ImmutableArray and MutableArray.freeze()
implementation.
Review at http://gwt-code-reviews.appspot.com/291801
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@7845 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/bikeshed/src/com/google/gwt/collections/Array.java b/bikeshed/src/com/google/gwt/collections/Array.java
index f6cded1..96a5cfe 100644
--- a/bikeshed/src/com/google/gwt/collections/Array.java
+++ b/bikeshed/src/com/google/gwt/collections/Array.java
@@ -31,4 +31,5 @@
@ConstantTime
public abstract int size();
+
}
diff --git a/bikeshed/src/com/google/gwt/collections/Assertions.java b/bikeshed/src/com/google/gwt/collections/Assertions.java
index 1a34e8d..282249c 100644
--- a/bikeshed/src/com/google/gwt/collections/Assertions.java
+++ b/bikeshed/src/com/google/gwt/collections/Assertions.java
@@ -20,13 +20,27 @@
*/
class Assertions {
+ static void assertGetFromImmutableEmpty() {
+ assert false : "Attempt to get an element from an immutable empty array";
+ }
+
static void assertIndexInRange(int index, int minInclusive, int maxExclusive) {
assert (index >= minInclusive && index < maxExclusive) : "Index " + index
+ " was not in the acceptable range [" + minInclusive + ", " + maxExclusive + ")";
}
+ static <E> void assertNotFrozen(MutableArray<E> a) {
+ assert !a.isFrozen() : "This operation is illegal on a frozen collection";
+ }
+
static void assertNotNull(Object ref) {
assert (ref != null) : "A null reference is not allowed here";
}
+
+ static <E> void markFrozen(MutableArray<E> a) {
+ if (Assertions.class.desiredAssertionStatus()) {
+ a.markFrozen();
+ }
+ }
}
diff --git a/bikeshed/src/com/google/gwt/collections/ImmutableArray.java b/bikeshed/src/com/google/gwt/collections/ImmutableArray.java
new file mode 100644
index 0000000..41d55ff
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/ImmutableArray.java
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2009 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.collections;
+
+/**
+ * An array that is guaranteed not to change, thus making it safe for disparate
+ * portions of code to maintain references to a shared instance, rather than
+ * feeling the need to make defensive copies.
+ *
+ * @param <E> The type stored in the array elements
+ */
+public abstract class ImmutableArray<E> extends Array<E> {
+
+ @SuppressWarnings("unchecked")
+ private static final ImmutableArray EMPTY = new ImmutableArrayEmptyImpl();
+
+ @SuppressWarnings("unchecked")
+ static <E> ImmutableArray<E> getEmptyInstance() {
+ return EMPTY;
+ }
+
+ ImmutableArray() {
+ }
+
+}
diff --git a/bikeshed/src/com/google/gwt/collections/ImmutableArrayEmptyImpl.java b/bikeshed/src/com/google/gwt/collections/ImmutableArrayEmptyImpl.java
new file mode 100644
index 0000000..bd0809c
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/ImmutableArrayEmptyImpl.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright 2009 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.collections;
+
+/**
+ * The standard byte code implementation of an immutable array.
+ *
+ * @param <E> The type stored in the array elements
+ */
+class ImmutableArrayEmptyImpl<E> extends ImmutableArray<E> {
+
+ @Override
+ public E get(int index) {
+ Assertions.assertGetFromImmutableEmpty();
+ return null;
+ }
+
+ @Override
+ public int size() {
+ return 0;
+ }
+
+}
diff --git a/bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java b/bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java
new file mode 100644
index 0000000..6fee8c0
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/ImmutableArrayImpl.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2009 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.collections;
+
+/**
+ * The standard byte code implementation of an immutable array.
+ *
+ * @param <E> The type stored in the array elements
+ */
+public class ImmutableArrayImpl<E> extends ImmutableArray<E> {
+
+ final E[] elems;
+
+ ImmutableArrayImpl(E[] elems) {
+ Assertions.assertNotNull(elems);
+ this.elems = elems;
+ }
+
+ @Override
+ public E get(int index) {
+ Assertions.assertIndexInRange(index, 0, elems.length);
+ return elems[index];
+ }
+
+ @Override
+ public int size() {
+ return elems.length;
+ }
+
+}
diff --git a/bikeshed/src/com/google/gwt/collections/MutableArray.java b/bikeshed/src/com/google/gwt/collections/MutableArray.java
index 3201458..444594e 100644
--- a/bikeshed/src/com/google/gwt/collections/MutableArray.java
+++ b/bikeshed/src/com/google/gwt/collections/MutableArray.java
@@ -23,7 +23,7 @@
public class MutableArray<E> extends Array<E> {
// The elements in the array
- private E[] elems;
+ E[] elems;
// Tracks when this array is frozen (for assertion enforcement only)
private boolean frozen;
@@ -41,8 +41,28 @@
@ConstantTime
public void clear() {
+ Assertions.assertNotFrozen(this);
elems = null;
}
+
+ /**
+ * Creates an immutable array based on this one. Also marks this object as read-only.
+ * After calling {@code freeze()}, only use methods from {@link Array} or the returned
+ * {@link ImmutableArray} should be to access the elements
+ * of the array is preferred.
+ */
+ public ImmutableArray<E> freeze() {
+ Assertions.markFrozen(this);
+
+ ImmutableArray<E> r;
+ if (elems != null) {
+ r = new ImmutableArrayImpl<E>(elems);
+ } else {
+ r = ImmutableArray.getEmptyInstance();
+ }
+
+ return r;
+ }
@Override
@ConstantTime
@@ -66,6 +86,7 @@
@SuppressWarnings("unchecked")
@LinearTime
public void insert(int index, E elem) {
+ Assertions.assertNotFrozen(this);
Assertions.assertIndexInRange(index, 0, size() + 1);
// TODO benchmark to see if we need to grow smartly (2x size?)
@@ -88,6 +109,7 @@
@SuppressWarnings("unchecked")
@LinearTime
public void remove(int index) {
+ Assertions.assertNotFrozen(this);
Assertions.assertIndexInRange(index, 0, size());
if (elems != null && elems.length >= 1) {
// TODO: replace with splice using JSNI
@@ -111,6 +133,7 @@
*/
@ConstantTime
public void set(int index, E elem) {
+ Assertions.assertNotFrozen(this);
Assertions.assertIndexInRange(index, 0, size());
if (elems != null) {
elems[index] = elem;
diff --git a/bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java b/bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java
new file mode 100644
index 0000000..dbc123c
--- /dev/null
+++ b/bikeshed/test/com/google/gwt/collections/ImmutableArrayTest.java
@@ -0,0 +1,161 @@
+/*
+ * Copyright 2009 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.collections;
+
+import com.google.gwt.junit.client.GWTTestCase;
+
+/**
+ * Tests immutable arrays.
+ */
+public class ImmutableArrayTest extends GWTTestCase {
+
+ private boolean assertionsEnabled;
+
+ @Override
+ public String getModuleName() {
+ return null;
+ }
+
+ public void gwtSetUp() {
+ assertionsEnabled = this.getClass().desiredAssertionStatus();
+ }
+
+ public void testAccessOutOfBounds() {
+ // Do not test undefined behavior with assertions disabled
+ if (!assertionsEnabled) {
+ return;
+ }
+
+ MutableArray<Integer> ma;
+ ImmutableArray<Integer> ia;
+
+ ma = CollectionFactory.createMutableArray();
+ ma.add(1);
+ ma.add(2);
+
+ ia = ma.freeze();
+
+ try {
+ ia.get(ia.size());
+ fail("Expected an assertion failure");
+ } catch (AssertionError e) {
+ assertEquals(("Index " + ia.size() + " was not in the acceptable range [" + 0 + ", " + ia.size()
+ + ")"), e.getMessage());
+ }
+
+ assertEquals(2, ma.size());
+
+ ma = CollectionFactory.createMutableArray();
+ // No elements added
+ ia = ma.freeze();
+
+ try {
+ ia.get(ia.size());
+ fail("Expected an assertion failure");
+ } catch (AssertionError e) {
+ assertEquals("Attempt to get an element from an immutable empty array", e.getMessage());
+ }
+ }
+
+ public void testFreezeEmptyArray() {
+ MutableArray<String> ma = CollectionFactory.createMutableArray();
+ // No elements added
+ ImmutableArray<String> ia = ma.freeze();
+
+ assertEquals(0, ia.size());
+ }
+
+ public void testFreezeMutable() {
+ MutableArray<String> ma = CollectionFactory.createMutableArray();
+ ma.add("pear");
+ ma.add("apple");
+ ImmutableArray<String> ia = ma.freeze();
+
+ assertEquals(2, ia.size());
+ assertEquals("pear", ia.get(0));
+ assertEquals("apple", ia.get(1));
+ }
+
+ public void testFreezeSingleElement() {
+ MutableArray<String> ma = CollectionFactory.createMutableArray();
+ ma.add("pear");
+ ImmutableArray<String> ia = ma.freeze();
+
+ assertEquals(1, ia.size());
+ assertEquals("pear", ia.get(0));
+ }
+
+ public void testModifyFrozenMutable() {
+ // Do not test undefined behavior with assertions disabled
+ if (!assertionsEnabled) {
+ return;
+ }
+
+ MutableArray<String> ma = CollectionFactory.createMutableArray();
+ ma.add("pear");
+ ma.add("apple");
+ ma.freeze();
+
+ try {
+ ma.add("orange");
+ fail("Expected an assertion failure");
+ } catch (AssertionError e) {
+ assertEquals(("This operation is illegal on a frozen collection"), e.getMessage());
+ }
+
+ try {
+ ma.clear();
+ fail("Expected an assertion failure");
+ } catch (AssertionError e) {
+ assertEquals(("This operation is illegal on a frozen collection"), e.getMessage());
+ }
+
+ try {
+ ma.insert(0, "orange");
+ fail("Expected an assertion failure");
+ } catch (AssertionError e) {
+ assertEquals(("This operation is illegal on a frozen collection"), e.getMessage());
+ }
+
+ try {
+ ma.remove(0);
+ fail("Expected an assertion failure");
+ } catch (AssertionError e) {
+ assertEquals(("This operation is illegal on a frozen collection"), e.getMessage());
+ }
+
+ try {
+ ma.set(0, "orange");
+ fail("Expected an assertion failure");
+ } catch (AssertionError e) {
+ assertEquals(("This operation is illegal on a frozen collection"), e.getMessage());
+ }
+ }
+
+ public void testImmutableNoCopy() {
+ MutableArray<String> ma = CollectionFactory.createMutableArray();
+ ma.add("pear");
+ ma.add("apple");
+ ImmutableArrayImpl<String> ia1 = (ImmutableArrayImpl<String>) ma.freeze();
+
+ assertTrue(ma.elems == ia1.elems);
+
+ ImmutableArrayImpl<String> ia2 = (ImmutableArrayImpl<String>) ma.freeze();
+
+ assertTrue(ia1.elems == ia2.elems);
+ }
+
+}
diff --git a/bikeshed/test/com/google/gwt/collections/ObjectArrayTest.java b/bikeshed/test/com/google/gwt/collections/ObjectArrayTest.java
index 312de31..ed63876 100644
--- a/bikeshed/test/com/google/gwt/collections/ObjectArrayTest.java
+++ b/bikeshed/test/com/google/gwt/collections/ObjectArrayTest.java
@@ -20,7 +20,7 @@
import com.google.gwt.junit.client.GWTTestCase;
/**
- * Tests immutable and mutable arrays.
+ * Tests mutable arrays.
*/
public class ObjectArrayTest extends GWTTestCase {
