Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Issues with Collection Builder capability #5001

Closed
scabug opened this issue Sep 17, 2011 · 3 comments
Closed

Issues with Collection Builder capability #5001

scabug opened this issue Sep 17, 2011 · 3 comments

Comments

@scabug
Copy link

scabug commented Sep 17, 2011

The issues are specifically with the methods in TraversableLike that
use the newBuilder method and those that use the CanBuildFrom implicit.

The Collection Builder is elegant but it has a flaw that
limits one's ability to count on its results.
Specifically, when a Traversable is extended with with one
or more traits, the object returned from the methods that
rely on the Builder is a Traversable of the wrong type.

First a "newBuilder" method, "filter":

Consider the code:

import scala.collection.mutable.ArrayBuffer
val a = new ArrayBuffer[Int]
a += 1
a += 2
a += 3
a filter {_ > 2}
res4: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(3)

Now consider the class:

import scala.collection.mutable.SynchronizedBuffer
class SyncArrayBuffer[T]  extends ArrayBuffer[T] with SynchronizedBuffer[T]

val s = new SyncArrayBuffer[Int]
s += 1
s += 2
s += 3
s filter {_ > 2}
res11: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(3)

This does not work. It returns an ArrayBuffer NOT a SyncArrayBuffer.

How to fix this?
Try the class:

import scala.collection.mutable.Builder
class SyncArrayBuffer[T]  extends ArrayBuffer[T] with SynchronizedBuffer[T]
    with Builder[T, SyncArrayBuffer[T]] {
  override def result: SyncArrayBuffer[T] = this
  override def stringPrefix: String = "SyncArrayBuffer"
  override def newBuilder: Builder[T, SyncArrayBuffer[T]] =
    new SyncArrayBuffer[T]
}

val s = new SyncArrayBuffer[Int]
s += 1
s += 2
s += 3
val x = s filter {_ > 2}
res: scala.collection.mutable.ArrayBuffer[Int] = SyncArrayBuffer(3)
x.getClass.getName
res5: java.lang.String = SyncArrayBuffer

So, this version of SyncArrayBuffer works.
But, note all of the extra boiler-plate stuff that had to be added to:

class SyncArrayBuffer[T] extends ArrayBuffer[T] with SynchronizedBuffer[T]

to get it to work. How many Scala users will go that that effort?

Now consider a "CanBuildFrom" method, "map", specifically the case
where the "map" function simply returns the original collection:

map { v => v}

Consider the code:

val a = new ArrayBuffer[Int]
a += 1
a += 2
a += 3
a map {v => v}
res: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)

This works as expected, it returns an ArrayBuffer as it should.

Now consider the class:

class SyncArrayBuffer[T]  extends ArrayBuffer[T] with SynchronizedBuffer[T]

val s = new SyncArrayBuffer[Int]
s += 1
s += 2
s += 3
s map {v => v}
res: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)

This does not work. It returns an ArrayBuffer NOT a SyncArrayBuffer.

How to fix this?
Try the class take worked for "newBuilder" "filter" example above:

import scala.collection.mutable.Builder
class SyncArrayBuffer[T]  extends ArrayBuffer[T] with SynchronizedBuffer[T]
    with Builder[T, SyncArrayBuffer[T]] {
  override def result: SyncArrayBuffer[T] = this
  override def stringPrefix: String = "SyncArrayBuffer"
  override def newBuilder: Builder[T, SyncArrayBuffer[T]] =
    new SyncArrayBuffer[T]
}

val s = new SyncArrayBuffer[Int]
s += 1
s += 2
s += 3
s map {v => v}
res: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)

Nope, does not fix the problem, still returns an ArrayBuffer.

Now consider the following "simple" ArrayBuffer extension with a trait:

class SyncArrayBuffer[T] extends ArrayBuffer[T]
    with SynchronizedBuffer[T]
    with GenericTraversableTemplate[T, SyncArrayBuffer]
    with BufferLike[T, SyncArrayBuffer[T]]
    with IndexedSeqOptimized[T, SyncArrayBuffer[T]]
    with Builder[T, SyncArrayBuffer[T]] {
  override def companion: GenericCompanion[SyncArrayBuffer] = SyncArrayBuffer
  override def result: SyncArrayBuffer[T] = this
  override def stringPrefix: String = "SyncArrayBuffer"
  override def newBuilder: Builder[T, SyncArrayBuffer[T]] =
    new SyncArrayBuffer[T]
}
object SyncArrayBuffer extends SeqFactory[SyncArrayBuffer] {
  /** $genericCanBuildFromInfo */
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, SyncArrayBuffer[A]] =
      ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]
  def newBuilder[A]: Builder[A, SyncArrayBuffer[A]] = new SyncArrayBuffer[A]
}

val s = new SyncArrayBuffer[Int]
s += 1
s += 2
s += 3
s map {v => v}
res: SyncArrayBuffer[Int] = SyncArrayBuffer(1, 2, 3)

That does it, the correct collection type is generated by the map method.

But how many Scala user when they extend a
Traversable with one or more traits are going to add all that
extra stuff just to get the correct Traversable result type
when using the thirty or forty TraversableLike methods that rely
of on a Builder? I bet no one does this and, secondly, I would
bet that most of them don't know there is a problem until it
runs over them.

Using code that relies on Builder with an Anonymous collection class
is worse, its just plain broken; there is NO way to fix it by flushing
out the class with methods and additional traits. Why? How does on
construct a companion object for an anonymous class?

val a = new SyncArrayBuffer[T] extends ArrayBuffer[T] with SynchronizedBuffer[T]
a filter {_ > 2} // returns ArrayBuffer
a map {v => v} // returns ArrayBuffer

These will return ArrayBuffers and with an anonymous class there is no where
to put the companion object. And, besides, the appeal of the
anonymous class is its simplicity.

So, how to deal with this hole in the collection Builder framework?

As I see it there are 4 options:

Option 1: Declare that its not a Bug but rather its a Feature.

Or another way to say this is: When programming in Scala and one takes
a sub-set of a collection, then there should be no expectation that
the type of the sub-set bears any relation to the type of the
original collection; the programmer should not have any notion
of "behaves as expected" because it does not.

Option 2: Declare that it is a Bug and it will Not be fixed.

While Scala should not have nooks and crannies where unexpected
behaviors can arise, the collection Builder has such traps
but it just not worth fixing.

Option 3: Implement https://issues.scala-lang.org/browse/SUGGEST-3

In the case of the "filter" method and the other methods that
rely on "newBuilder", rather than simply return the result of
the Builder, the code should call the "expandTo" operator as
described in Suggest-3:

  def filter(p: A => Boolean): Repr = {
    val b = newBuilder
    for (x <- this)
    if (p(x)) b += x
    b.result.expandTo[getClass]
  }

The "expandTo" operator is analogous to the "asInstanceOf" operator.
It takes an instance and expands it, explicitly pimps it, into a
derived type if possible (otherwise an Exception is thrown).

In the case of a SyncArrayBuffer instance, the above "filter" method code
is analogous to the following explicit pimped code:

  def filter(p: A => Boolean): Repr = {
    val b = newBuilder
    for (x <- this)
    if (p(x)) b += x
    b.result with SynchronizedBuffer[A]
  }

except that the type returned is actually "SyncArrayBuffer[A]" and not
just "ArrayBuffer[A] with SynchronizedBuffer[A]"

"optionalExpandTo" is used, for example for the "map" function:

  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b.sizeHint(this)
    for (x <- this) b += f(x)
    b.result.optionalExpandTo[getClass]
  }

Here, if the result type is a base-class of the type returned
by the call to getClass, then the result is converted into an
instance of the getClass type, otherwise, the result is returned
unchanged. This covers the corner case where the "map" function
simply returns a copy or sup-set of the original collection type.

The up-side of using Suggest-3 is that Scala would then support
explicit pimping and explicit pimping is vastly easier to use
and understand than implicit pimping (their domain of usage
do partially overlap). I would imagine that there would be a
whole lot of explicit pimping going on once it was realized that
one could (for better or worse) pimp objects return by
third-party libraries.

If this approach is taken, then this bug is not only a collection
issue but also effect the language specification.

Of course, I will admit that is faster to yield the incorrect
collection type than using explicit pimping to produce the
correct collection type, but I guess thats the trade-off isn't it.

Option 4: You are a bunch of smart folks, find a different solution.

A number of times I've run across the unexpected behavior
represented by this bug. I always struck me that its something
that ought to be fixed.

Thanks.

@scabug
Copy link
Author

scabug commented Sep 17, 2011

Imported From: https://issues.scala-lang.org/browse/SI-5001?orig=1
Reporter: Richard Emberson (rmemberson)
Affected Versions: 2.9.2

@scabug
Copy link
Author

scabug commented Dec 12, 2012

@retronym said:
I'm reclassifying as an improvement: you're proposing that we make it easier to make a fully-fledged member of the collection hierarchy.

We're unlikely to be able to tinker with the collections design within the bounds of backwards compatibility for the next one or two major releases. But these perspectives will be useful when the time comes.

@scabug scabug added this to the Backlog milestone Apr 7, 2017
@scala scala deleted a comment from scabug Jan 18, 2024
@SethTisue SethTisue removed this from the Backlog milestone Jan 18, 2024
@SethTisue
Copy link
Member

closing since the collections got redesigned in 2.13, and since the contributors forum is the place for these sorts of design discussions; we've refocused scala/bug as just a bug tracker

I'll mention @scala/collections in case anyone wants to sort through this and see if anything here remains actionable or of interest

@SethTisue SethTisue closed this as not planned Won't fix, can't repro, duplicate, stale Jan 18, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants