10000 LazyList.force returns LazyList. (#454) · szeiger/scala@0a00062 · GitHub
[go: up one dir, main page]
Skip to content

Commit 0a00062

Browse files
opticianjulienrf
optician
authored and
julienrf
committed
LazyList.force returns LazyList. (scala#454)
* * Add tests of `force` for LazyList and Stream. * Test string representations of LazyList and Stream after `force` call. * Add tests of `sameElements` for LazyList and Stream. * Change `force` result type from `Option[(head, tail)]` to `CC[A]`. * Force `force` to evaluate whole LazyList and Stream. * Update methods depended on `force`: `unapply` and `sameElements`. * Reimplement `sameElements`. ** Remove Tuple allocation. ** Check reference equality on every step. * * Code style. * * Remove redundant override of `sameElements` method. * * Set more strict type of `force` method. * * Stack safe `force` with cyclic references detection. * * Update LazyListForceBenchmark * * Fix method name. * Test `sameElements` with cyclic collections. * Reduce allocation in `force` method.
1 parent 01d3f3a commit 0a00062

File tree

4 files changed

+140
-50
lines changed

4 files changed

+140
-50
lines changed

‎collections/src/main/scala/strawman/collection/LinearSeq.scala

Lines changed: 13 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -129,20 +129,21 @@ trait LinearSeqOps[+A, +CC[X] <: LinearSeq[X], +C <: LinearSeq[A]] extends Any w
129129
acc
130130
}
131131

132-
override def sameElements[B >: A](that: IterableOnce[B]): Boolean = that match {
133-
case that1: LinearSeq[B] =>
134-
// Probably immutable, so check reference identity first (it's quick anyway)
135-
(coll eq that1) || {
136-
var these: LinearSeq[A] = coll
137-
var those: LinearSeq[B] = that1
138-
while (!these.isEmpty && !those.isEmpty && these.head == those.head) {
139-
these = these.tail
140-
those = those.tail
132+
override def sameElements[B >: A](that: IterableOnce[B]): Boolean = {
133+
@tailrec def linearSeqEq(a: LinearSeq[B], b: LinearSeq[B]): Boolean =
134+
(a eq b) || {
135+
if (a.nonEmpty && b.nonEmpty && a.head == b.head) {
136+
linearSeqEq(a.tail, b.tail)
137+
}
138+
else {
139+
a.isEmpty && b.isEmpty
141140
}
142-
these.isEmpty && those.isEmpty
143141
}
144-
case _ =>
145-
super.sameElements(that)
142+
143+
that match {
144+
case that: LinearSeq[B] => linearSeqEq(coll, that)
145+
case _ => super.sameElements(that)
146+
}
146147
}
147148

148149

‎collections/src/main/scala/strawman/collection/immutable/LazyList.scala

Lines changed: 76 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ package immutable
44

55
import strawman.collection.mutable.{ArrayBuffer, Builder}
66

7-
import scala.{Any, AnyRef, Boolean, Int, None, NoSuchElementException, noinline, Nothing, Option, PartialFunction, Some, StringContext, Unit, UnsupportedOperationException, deprecated}
7+
import scala.{Any, AnyRef, Boolean, Int, NoSuchElementException, None, Nothing, Option, PartialFunction, Some, StringContext, Unit, UnsupportedOperationException, deprecated, noinline}
88
import scala.Predef.String
99
import scala.annotation.tailrec
1010
import scala.annotation.unchecked.uncheckedVariance
@@ -230,37 +230,30 @@ sealed private[immutable] trait LazyListOps[+A, +CC[+X] <: LinearSeq[X] with Laz
230230

231231
protected[this] def cons[T](hd: => T, tl: => CC[T]): CC[T]
232232

233-
/** Force the evaluation of both the head and the tail of this `LazyList` */
234-
def force: Option[(A, CC[A])]
233+
/** Forces evaluation of the whole `LazyList` and returns it.
234+
*
235+
* @note Often we use `LazyList`s to represent an infinite set or series. If
236+
* that's the case for your particular `LazyList` then this function will never
237+
* return and will probably crash the VM with an `OutOfMemory` exception.
238+
* This function will not hang on a finite cycle, however.
239+
*
240+
* @return The fully realized `LazyList`.
241+
*/
242+
def force: this.type
235243

236244
/** The stream resulting from the concatenation of this stream with the argument stream.
237245
*
238246
* @param suffix The collection that gets appended to this lazy list
239247
* @return The lazy list containing elements of this lazy list and the iterable object.
240248
*/
241249
def lazyAppendAll[B >: A](suffix: => collection.IterableOnce[B]): CC[B] =
242-
if (isEmpty) iterableFactory.from(suffix.iterator()) else cons[B](head, tail.lazyAppendAll(suffix))
250+
if (isEmpty) iterableFactory.from(suffix) else cons[B](head, tail.lazyAppendAll(suffix))
243251

244252
override def className = "LazyList"
245253

246254
override def equals(that: Any): Boolean =
247255
if (this eq that.asInstanceOf[AnyRef]) true else super.equals(that)
248256

249-
override def sameElements[B >: A](that: IterableOnce[B]): Boolean = {
250-
@tailrec def lazyListEq(a: CC[_], b: CC[_]): Boolean =
251-
if (a eq b) true else {
252-
(a.force, b.force) match {
253-
case (Some((ah, at)), Some((bh, bt))) => (ah == bh) && lazyListEq(at, bt)
254-
case (None, None) => true
255-
case _ => false
256-
}
257-
}
258-
that match {
259-
case that: LazyListOps[_, _, _] => lazyListEq(coll, that.asInstanceOf[CC[_]])
260-
case _ => super.sameElements(that)
261-
}
262-
}
263-
264257
override def scanLeft[B](z: B)(op: (B, A) => B): CC[B] =
265258
if (isEmpty) z +: iterableFactory.empty
266259
else cons(z, tail.scanLeft(op(z, head))(op))
@@ -337,11 +330,11 @@ sealed private[immutable] trait LazyListOps[+A, +CC[+X] <: LinearSeq[X] with Laz
337330
else {
338331
// establish !prefix.isEmpty || nonEmptyPrefix.isEmpty
339332
var nonEmptyPrefix: CC[A] = coll
340-
var prefix = iterableFactory.from(f(nonEmptyPrefix.head).iterator())
333+
var prefix = iterableFactory.from(f(nonEmptyPrefix.head))
341334
while (!nonEmptyPrefix.isEmpty && prefix.isEmpty) {
342335
nonEmptyPrefix = nonEmptyPrefix.tail
343336
if(!nonEmptyPrefix.isEmpty)
344-
prefix = iterableFactory.from(f(nonEmptyPrefix.head).iterator())
337+
prefix = iterableFactory.from(f(nonEmptyPrefix.head))
345338
}
346339

347340
if (nonEmptyPrefix.isEmpty) iterableFactory.empty
@@ -434,7 +427,6 @@ sealed private[immutable] trait LazyListFactory[+CC[+X] <: LinearSeq[X] with Laz
434427
newCons(head, stream.tail.collect(pf))
435428
}
436429

437-
type Evaluated[+A] <: Option[(A, CC[A])]
438430
}
439431

440432
/**
@@ -446,14 +438,12 @@ object LazyList extends LazyListFactory[LazyList] {
446438

447439
protected[this] def newCons[T](hd: => T, tl: => LazyList[T]): LazyList[T] = new LazyList.Cons(hd, tl)
448440

449-
type Evaluated[+A] = Option[(A, LazyList[A])]
450-
451441
object Empty extends LazyList[Nothing] {
452442
override def isEmpty: Boolean = true
453443
override def head: Nothing = throw new NoSuchElementException("head of empty lazy list")
454444
override def tail: LazyList[Nothing] = throw new UnsupportedOperationException("tail of empty lazy list")
455-
def force: Evaluated[Nothing] = None
456-
override def toString: String = "Empty"
445+
def force: this.type = this
446+
override def toString(): String = "Empty"
457447
}
458448

459449
final class Cons[A](hd: => A, tl: => LazyList[A]) extends LazyList[A] {
@@ -468,8 +458,26 @@ object LazyList extends LazyListFactory[LazyList] {
468458
tlEvaluated = true
469459
tl
470460
}
471-
def force: Evaluated[A] = Some((head, tail))
472-
override def toString: String =
461+
def force: this.type = {
462+
// Use standard 2x 1x iterator trick for cycle detection ("those" is slow one)
463+
var these, those: LazyList[A] = this
464+
if (!these.isEmpty) {
465+
these.head
466+
these = these.tail
467+
}
468+
while (those ne these) {
469+
if (these.isEmpty) return this
470+
these.head
471+
these = these.tail
472+
if (these.isEmpty) return this
473+
these.head
474+
these = these.tail
475+
if (these eq those) return this
476+
those = those.tail
477+
}
478+
this
479+
}
480+
override def toString(): String =
473481
if (hdEvaluated) s"$head #:: ${if (tlEvaluated) tail.toString else "?"}"
474482
else "LazyList(?)"
475483
}
@@ -499,7 +507,8 @@ object LazyList extends LazyListFactory[LazyList] {
499507
}
500508

501509
object #:: {
502-
def unapply[A](s: LazyList[A]): Evaluated[A] = s.force
510+
def unapply[A](s: LazyList[A]): Option[(A, LazyList[A])] =
511+
if (s.nonEmpty) Some((s.head, s.tail)) else None
503512
}
504513

505514
def from[A](coll: collection.IterableOnce[A]): LazyList[A] = coll match {
@@ -571,14 +580,21 @@ object Stream extends LazyListFactory[Stream] {
571580

572581
protected[this] def newCons[T](hd: => T, tl: => Stream[T]): Stream[T] = new Stream.Cons(hd, tl)
573582

574-
type Evaluated[+A] = Option[(A, Stream[A])]
575-
576583
object Empty extends Stream[Nothing] {
577584
override def isEmpty: Boolean = true
578585
override def head: Nothing = throw new NoSuchElementException("head of empty lazy list")
579586
override def tail: Stream[Nothing] = throw new UnsupportedOperationException("tail of empty lazy list")
580-
def force: Evaluated[Nothing] = None
581-
override def toString: String = "Empty"
587+
/** Forces evaluation of the whole `Stream` and returns it.
588+
*
589+
* @note Often we use `Stream`s to represent an infinite set or series. If
590+
* that's the case for your particular `Stream` then this function will never
591+
* return and will probably crash the VM with an `OutOfMemory` exception.
592+
* This function will not hang on a finite cycle, however.
593+
*
594+
* @return The fully realized `Stream`.
595+
*/
596+
def force: this.type = this
597+
override def toString(): String = "Empty"
582598
}
583599

584600
final class Cons[A](override val head: A, tl: => Stream[A]) extends Stream[A] {
@@ -588,9 +604,32 @@ object Stream extends LazyListFactory[Stream] {
588604
tlEvaluated = true
589605
tl
590606
}
591-
def force: Evaluated[A] = Some((head, tail))
592-
override def toString: String =
607+
/** Forces evaluation of the whole `Stream` and returns it.
608+
*
609+
* @note Often we use `Stream`s to represent an infinite set or series. If
610+
* that's the case for your particular `Stream` then this function will never
611+
* return and will probably crash the VM with an `OutOfMemory` exception.
612+
* This function will not hang on a finite cycle, however.
613+
*
614+
* @return The fully realized `Stream`.
615+
*/
616+
def force: this.type = {
617+
// Use standard 2x 1x iterator trick for cycle detection ("those" is slow one)
618+
var these, those: Stream[A] = this
619+
if (!these.isEmpty) these = these.tail
620+
while (those ne these) {
621+
if (these.isEmpty) return this
622+
these = these.tail
623+
if (these.isEmpty) return this
624+
these = these.tail
625+
if (these eq those) return this
626+
those = those.tail
627+
}
628+
this
629+
}
630+
override def toString(): String =
593631
s"$head #:: ${if (tlEvaluated) tail.toString else "?"}"
632+
594633
}
595634

596635
/** An alternative way of building and matching Streams using Stream.cons(hd, tl).
@@ -618,7 +657,8 @@ object Stream extends LazyListFactory[Stream] {
618657
}
619658

620659
object #:: {
621-
def unapply[A](s: Stream[A]): Evaluated[A] = s.force
660+
def unapply[A](s: Stream[A]): Option[(A, Stream[A])] =
661+
if (s.nonEmpty) Some((s.head, s.tail)) else None
622662
}
623663

624664
def from[A](coll: collection.IterableOnce[A]): Stream[A] = coll match {

‎test/junit/src/test/scala/strawman/collection/immutable/LazyListTest.scala

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
package strawman.collection.immutable
22

3+
import strawman.collection.Iterator
34
import org.junit.runner.RunWith
45
import org.junit.runners.JUnit4
56
import org.junit.{Test, Ignore}
@@ -139,4 +140,33 @@ class LazyListTest {
139140
assertEquals(LazyList(3), LazyList(1, 2, 3).drop(2))
140141
assertEquals(LazyList(3, 4), LazyList(1, 2, 3, 4).drop(2))
141142
}
143+
144+
@Test
145+
def testForceReturnsEvaluatedLazyList() : Unit = {
146+
var i = 0
147+
def f: Int = { i += 1; i }
148+
val xs = LazyList.from(Iterator.fill(3)(f))
149+
assertEquals(0, i)
150+
xs.force
151+
assertEquals(3, i)
152+
// it's possible to implement `force` with incorrect string representation
153+
// (to forget about `tlEvaluated` update)
154+
assertEquals( "1 #:: 2 #:: 3 #:: Empty", xs.toString())
155+
}
156+
157+
val cycle1: LazyList[Int] = 1 #:: 2 #:: cycle1
158+
val cycle2: LazyList[Int] = 1 #:: 2 #:: 3 #:: cycle2
159+
@Test(timeout=10000)
160+
def testSameElements(): Unit = {
161+
assert(LazyList().sameElements(LazyList()))
162+
assert(!LazyList().sameElements(LazyList(1)))
163+
assert(LazyList(1,2).sameElements(LazyList(1,2)))
164+
assert(!LazyList(1,2).sameElements(LazyList(1)))
165+
assert(!LazyList(1).sameElements(LazyList(1,2)))
166+
assert(!LazyList(1).sameElements(LazyList(2)))
167+
assert(cycle1.sameElements(cycle1))
168+
assert(!cycle1.sameElements(cycle2))
169+
assert(!cycle1.sameElements(cycle2))
170+
}
171+
142172
}

‎test/junit/src/test/scala/strawman/collection/immutable/StreamTest.scala

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -125,10 +125,29 @@ class StreamTest {
125125
}
126126

127127
@Test
128-
def testStreamForcesHead: Unit = {
128+
def testForceReturnsEvaluatedStream() : Unit = {
129129
var i = 0
130130
def f: Int = { i += 1; i }
131-
val s = f #:: f #:: f #:: Stream.empty
131+
val xs = f #:: f #:: f #:: Stream.empty
132132
assertEquals(1, i)
133+
xs.force
134+
assertEquals(3, i)
135+
// it's possible to implement `force` with incorrect string representation
136+
// (to forget about `tlEvaluated` update)
137+
assertEquals( "1 #:: 2 #:: 3 #:: Empty", xs.toString())
138+
}
139+
140+
val cycle1: Stream[Int] = 1 #:: 2 #:: cycle1
141+
val cycle2: Stream[Int] = 1 #:: 2 #:: 3 #:: cycle2
142+
@Test(timeout=10000)
143+
def testSameElements(): Unit = {
144+
assert(Stream().sameElements(Stream()))
145+
assert(!Stream().sameElements(Stream(1)))
146+
assert(Stream(1,2).sameElements(Stream(1,2)))
147+
assert(!Stream(1,2).sameElements(Stream(1)))
148+
assert(!Stream(1).sameElements(Stream(1,2)))
149+
assert(!Stream(1).sameElements(Stream(2)))
150+
assert(!cycle1.sameElements(cycle2))
151+
assert(!cycle1.sameElements(cycle2))
133152
}
134153
}

0 commit comments

Comments
 (0)
0