8000 Merge pull request #5162 from tanishiking/arraylist-wasm · scala-js/scala-js@008c33a · GitHub
[go: up one dir, main page]
Skip to content

Commit 008c33a

Browse files
sjrdsjrd
authored
Merge pull request #5162 from tanishiking/arraylist-wasm
Wasm: Implement ju.ArrayList without js.Array for Wasm backend
2 parents 3ad65c7 + a088ec4 commit 008c33a

File tree

4 files changed

+241
-23
lines changed

4 files changed

+241
-23
lines changed

‎javalib/src/main/scala/java/util/ArrayList.scala

Lines changed: 123 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -14,80 +14,181 @@ package java.util
1414

1515
import java.lang.Cloneable
1616
import java.lang.Utils._
17+
import java.util.ScalaOps._
1718

1819
import scala.scalajs._
20+
import scala.scalajs.LinkingInfo.isWebAssembly
1921

20-
class ArrayList[E] private (private[ArrayList] val inner: js.Array[E])
22+
class ArrayList[E] private (innerInit: AnyRef, private var _size: Int)
2123
extends AbstractList[E] with RandomAccess with Cloneable with Serializable {
2224
self =>
2325

26+
/* This class has two different implementations for handling the
27+
* internal data storage, depending on whether we are on Wasm or JS.
28+
* On JS, we utilize `js.Array`. On Wasm, for performance reasons,
29+
* we avoid JS interop and use a scala.Array.
30+
* The `_size` field (unused in JS) keeps track of the effective size
31+
* of the underlying Array for the Wasm implementation.
32+
*/
33+
34+
private val innerJS: js.Array[E] =
35+
if (isWebAssembly) null
36+
else innerInit.asInstanceOf[js.Array[E]]
37+
38+
private var innerWasm: Array[AnyRef] =
39+
if (!isWebAssembly) null
40+
else innerInit.asInstanceOf[Array[AnyRef]]
41+
2442
def this(initialCapacity: Int) = {
25-
this(new js.Array[E])
26-
if (initialCapacity < 0)
27-
throw new IllegalArgumentException
43+
this(
44+
{
45+
if (initialCapacity < 0)
46+
throw new IllegalArgumentException
47+
if (isWebAssembly) new Array[AnyRef](initialCapacity)
48+
else new js.Array[E]
49+
},
50+
0
51+
)
2852
}
2953

30-
def this() =
31-
this(new js.Array[E])
54+
def this() = this(16)
3255

3356
def this(c: Collection[_ <: E]) = {
34-
this()
57+
this(c.size())
3558
addAll(c)
3659
}
3760

3861
def trimToSize(): Unit = {
39-
// We ignore this as js.Array doesn't support explicit pre-allocation
62+
if (isWebAssembly)
63+
resizeTo(size())
64+
// We ignore this in JS as js.Array doesn't support explicit pre-allocation
4065
}
4166

4267
def ensureCapacity(minCapacity: Int): Unit = {
43-
// We ignore this as js.Array doesn't support explicit pre-allocation
68+
if (isWebAssembly) {
69+
if (innerWasm.length < minCapacity) {
70+
if (minCapacity > (1 << 30))
71+
resizeTo(minCapacity)
72+
else
73+
resizeTo(((1 << 31) >>> (Integer.numberOfLeadingZeros(minCapacity - 1)) - 1))
74+
}
75+
}
76+
// We ignore this in JS as js.Array doesn't support explicit pre-allocation
4477
}
4578

4679
def size(): Int =
47-
inner.length
48-
49-
override def clone(): AnyRef =
50-
new ArrayList(inner.jsSlice(0))
80+
if (isWebAssembly) _size
81+
else innerJS.length
82+
83+
override def clone(): AnyRef = {
84+
if (isWebAssembly)
85+
new ArrayList(innerWasm.clone(), size())
86+
else
87+
new ArrayList(innerJS.jsSlice(0), 0)
88+
}
5189

5290
def get(index: Int): E = {
5391
checkIndexInBounds(index)
54-
inner(index)
92+
if (isWebAssembly)
93+
innerWasm(index).asInstanceOf[E]
94+
else
95+
innerJS(index)
5596
}
5697

5798
override def set(index: Int, element: E): E = {
5899
val e = get(index)
59-
inner(index) = element
100+
if (isWebAssembly)
101+
innerWasm(index) = element.asInstanceOf[AnyRef]
102+
else
103+
innerJS(index) = element
60104
e
61105
}
62106

63107
override def add(e: E): Boolean = {
64-
inner.push(e)
108+
if (isWebAssembly) {
109+
if (size() >= innerWasm.length)
110+
expand()
111+
innerWasm(size()) = e.asInstanceOf[AnyRef]
112+
_size += 1
113+
} else {
114+
innerJS.push(e)
115+
}
65116
true
66117
}
67118

68119
override def add(index: Int, element: E): Unit = {
69120
checkIndexOnBounds(index)
70-
inner.splice(index, 0, element)
121+
if (isWebAssembly) {
122+
if (size() >= innerWasm.length)
123+
expand()
124+
System.arraycopy(innerWasm, index, innerWasm, index + 1, size() - index)
125+
innerWasm(index) = element.asInstanceOf[AnyRef]
126+
_size += 1
127+
} else {
128+
innerJS.splice(index, 0, element)
129+
}
71130
}
72131

73132
override def remove(index: Int): E = {
74133
checkIndexInBounds(index)
75-
arrayRemoveAndGet(inner, index)
134+
if (isWebAssembly) {
135+
val removed = innerWasm(index).asInstanceOf[E]
136+
System.arraycopy(innerWasm, index + 1, innerWasm, index, size() - index - 1)
137+
innerWasm(size - 1) = null // free reference for GC
138+
_size -= 1
139+
removed
140+
} else {
141+
arrayRemoveAndGet(innerJS, index)
142+
}
76143
}
77144

78145
override def clear(): Unit =
79-
inner.length = 0
146+
if (isWebAssembly) {
147+
Arrays.fill(innerWasm, null) // free references for GC
148+
_size = 0
149+
} else {
150+
innerJS.length = 0
151+
}
80152

81153
override def addAll(index: Int, c: Collection[_ <: E]): Boolean = {
82154
c match {
83155
case other: ArrayList[_] =>
84-
inner.splice(index, 0, other.inner.toSeq: _*)
156+
checkIndexOnBounds(index)
157+
if (isWebAssembly) {
158+
ensureCapacity(size() + other.size())
159+
System.arraycopy(innerWasm, index, innerWasm, index + other.size(), size() - index)
160+
System.arraycopy(other.innerWasm, 0, innerWasm, index, other.size())
161+
_size += c.size()
162+
} else {
163+
innerJS.splice(index, 0, other.innerJS.toSeq: _*)
164+
}
85165
other.size() > 0
86166
case _ => super.addAll(index, c)
87167
}
88168
}
89169

90-
override protected def removeRange(fromIndex: Int, toIndex: Int): Unit =
91-
inner.splice(fromIndex, toIndex - fromIndex)
170+
override protected def removeRange(fromIndex: Int, toIndex: Int): Unit = {
171+
if (fromIndex < 0 || toIndex > size() || toIndex < fromIndex)
172+
throw new IndexOutOfBoundsException()
173+
if (isWebAssembly) {
174+
if (fromIndex != toIndex) {
175+
System.arraycopy(innerWasm, toIndex, innerWasm, fromIndex, size() - toIndex)
176+
val newSize = size() - toIndex + fromIndex
177+
Arrays.fill(innerWasm, newSize, size(), null) // free references for GC
178+
_size = newSize
179+
}
180+
} else {
181+
innerJS.splice(fromIndex, toIndex - fromIndex)
182+
}
183+
}
92184

185+
// Wasm only
186+
private def expand(): Unit = {
187+
resizeTo(Math.max(innerWasm.length * 2, 16))
188+
}
189+
190+
// Wasm only
191+
private def resizeTo(newCapacity: Int): Unit = {
192+
innerWasm = Arrays.copyOf(innerWasm, newCapacity)
193+
}
93194
}

‎test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/ArrayListTest.scala

Lines changed: 95 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,14 +13,19 @@
1313
package org.scalajs.testsuite.javalib.util
1414

1515
import org.junit.Test
16+
import org.junit.Assert._
17+
import org.junit.Assume._
18+
19+
import org.scalajs.testsuite.utils.AssertThrows.assertThrows
20+
import org.scalajs.testsuite.utils.Platform
1621

1722
import java.{util => ju}
1823

1924
import scala.reflect.ClassTag
2025

2126
class ArrayListTest extends AbstractListTest {
2227

23-
override def factory: AbstractListFactory = new ArrayListFactory
28+
override def factory: ArrayListFactory = new ArrayListFactory
2429

2530
@Test def ensureCapacity(): Unit = {
2631
// note that these methods become no ops in js
@@ -29,6 +34,86 @@ class ArrayListTest extends AbstractListTest {
2934
al.ensureCapacity(34)
3035
al.trimToSize()
3136
}
37+
38+
@Test def constructorInitialCapacity(): Unit = {
39+
val al1 = new ju.ArrayList(0)
40+
assertTrue(al1.size() == 0)
41+
assertTrue(al1.isEmpty())
42+
43+
val al2 = new ju.ArrayList(2)
44+
assertTrue(al2.size() == 0)
45+
assertTrue(al2.isEmpty())
46+
47+
assertThrows(classOf[IllegalArgumentException], new ju.ArrayList(-1))
48+
}
49+
50+
@Test def constructorNullThrowsNullPointerException(): Unit = {
51+
assumeTrue("assumed compliant NPEs", Platform.hasCompliantNullPointers)
52+
assertThrows(classOf[NullPointerException], new ju.ArrayList(null))
53+
}
54+
55+
@Test def testClone(): Unit = {
56+
val al1 = factory.fromElements[Int](1, 2)
57+
val al2 = al1.clone().asInstanceOf[ju.ArrayList[Int]]
58+
al1.add(100)
59+
al2.add(200)
60+
assertTrue(Array[Int](1, 2, 100).sameElements(al1.toArray()))
61+
assertTrue(Array[Int](1, 2, 200).sameElements(al2.toArray()))
62+
}
63+
64+
@Test def removeRangeFromIdenticalIndices(): Unit = {
65+
val al = new ArrayListRangeRemovable[Int](
66+
TrivialImmutableCollection(-175, 24, 7, 44))
67+
val expected = Array[Int](-175, 24, 7, 44)
68+
al.removeRangeList(0, 0)
69+
assertTrue(al.toArray().sameElements(expected))
70+
al.removeRangeList(1, 1)
71+
assertTrue(al.toArray().sameElements(expected))
72+
al.removeRangeList(al.size, al.size) // no op
73+
assertTrue(al.toArray().sameElements(expected))
74+
}
75+
76+
@Test def removeRangeFromToInvalidIndices(): Unit = {
77+
val al = new ArrayListRangeRemovable[Int](
78+
TrivialImmutableCollection(175, -24, -7, -44))
79+
80+
assertThrows(
81+
classOf[java.lang.IndexOutOfBoundsException],
82+
al.removeRangeList(-1, 2)
83+
) // fromIndex < 0
84+
assertThrows(
85+
classOf[java.lang.IndexOutOfBoundsException],
86+
al.removeRangeList(0, al.size + 1)
87+
) // toIndex > size
88+
assertThrows(
89+
classOf[java.lang.IndexOutOfBoundsException],
90+
al.removeRangeList(2, -1)
91+
) // toIndex < f 10000 romIndex
92+
}
93+
94+
@Test def removeRangeFromToFirstTwoElements(): Unit = {
95+
val al = new ArrayListRangeRemovable[Int](
96+
TrivialImmutableCollection(284, -27, 995, 500, 267, 904))
97+
val expected = Array[Int](995, 500, 267, 904)
98+
al.removeRangeList(0, 2)
99+
assertTrue(al.toArray().sameElements(expected))
100+
}
101+
102+
@Test def removeRangeFromToTwoElementsFromMiddle(): Unit = {
103+
val al = new ArrayListRangeRemovable[Int](
104+
TrivialImmutableCollection(7, 9, -1, 20))
105+
val expected = Array[Int](7, 20)
106+
al.removeRangeList(1, 3)
107+
assertTrue(al.toArray().sameElements(expected))
108+
}
109+
110+
@Test def removeRangeFromToLastTwoElementsAtTail(): Unit = {
111+
val al = new ArrayListRangeRemovable[Int](
112+
TrivialImmutableCollection(50, 72, 650, 12, 7, 28, 3))
113+
val expected = Array[Int](50, 72, 650, 12, 7)
114+
al.removeRangeList(al.size - 2, al.size)
115+
assertTrue(al.toArray().sameElements(expected))
116+
}
32117
}
33118

34119
class ArrayListFactory extends AbstractListFactory {
@@ -37,4 +122,13 @@ class ArrayListFactory extends AbstractListFactory {
37122

38123
override def empty[E: ClassTag]: ju.ArrayList[E] =
39124
new ju.ArrayList[E]
125+
126+
override def fromElements[E: ClassTag](coll: E*): ju.ArrayList[E] =
127+
new ju.ArrayList[E](TrivialImmutableCollection(coll: _*))
128+
}
129+
130+
class ArrayListRangeRemovable[E](c: ju.Collection[_ <: E]) extends ju.ArrayList[E](c) {
131+
def removeRangeList(fromIndex: Int, toIndex: Int): Unit = {
132+
removeRange(fromIndex, toIndex)
133+
}
40134
}

‎test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/CollectionTest.scala

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,16 @@ trait CollectionTest extends IterableTest {
117117
assertFalse(coll.contains(TestObj(200)))
118118
}
119119

120+
@Test def isEmpty(): Unit = {
121+
val coll = factory.empty[Int]
122+
assertTrue(coll.size() == 0)
123+
assertTrue(coll.isEmpty())
124+
125+
val nonEmpty = factory.fromElements[Int](1)
126+
assertTrue(nonEmpty.size() == 1)
127+
assertFalse(nonEmpty.isEmpty())
128+
}
129+
120130
@Test def removeString(): Unit = {
121131
val coll = factory.empty[String]
122132

‎test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/ListTest.scala

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -96,6 +96,19 @@ trait ListTest extends CollectionTest with CollectionsTestBase {
9696
assertThrows(classOf[IndexOutOfBoundsException], lst.get(lst.size))
9797
}
9898

99+
@Test def addAllIndexBounds(): Unit = {
100+
val al = factory.fromElements[String]("one", "two", "three")
101+
102+
val coll = factory.fromElements[String]("foo")
103+
assertThrows(classOf[IndexOutOfBoundsException], al.addAll(-1, coll))
104+
assertThrows(classOf[IndexOutOfBoundsException], al.addAll(al.size + 1, coll))
105+
106+
assertThrows(classOf[IndexOutOfBoundsException],
107+
al.addAll(-1, TrivialImmutableCollection("foo")))
108+
assertThrows(classOf[IndexOutOfBoundsException],
109+
al.addAll(al.size + 1, TrivialImmutableCollection("foo")))
110+
}
111+
99112
@Test def removeStringRemoveIndex(): Unit = {
100113
val lst = factory.empty[String]
101114

0 commit comments

Comments
 (0)
0