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

mutable.IndexedSeq.view.map returns collection.SeqView #4190

Closed
scabug opened this Issue Jan 27, 2011 · 18 comments

Comments

Projects
None yet
6 participants
@scabug
Copy link

scabug commented Jan 27, 2011

=== What steps will reproduce the problem (please be specific and use wikiformatting)? ===

import collection.mutable._

val x: ArrayBuffer[String] = ArrayBuffer("a", "b", "c")
val y: IndexedSeq[String] = x.view map (_ + "0")

This code compiles but produces a ClassCastException in the last line:

java.lang.ClassCastException: scala.collection.SeqViewLike$$$$anon$$3 cannot be cast to scala.collection.mutable.IndexedSeq

=== What is the expected behavior? ===
A compiler error or working code.

=== What versions of the following are you using? ===

  • Scala: 2.8.1
@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jan 27, 2011

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 8, 2012

@jsuereth said:
Looks like this has been fixed.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 9, 2012

@soc said:
Still crashes for me on Scala version 2.10.0-20120507-163905-843ac9520c (OpenJDK 64-Bit Server VM, Java 1.7.0_03).

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 9, 2012

@jrudolph said:
Yep, seems like the essential part which is the expected type is missing in the test.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 9, 2012

@jrudolph said:
A bit of more info: this is specific to mutable.IndexedSeq which returns a mutable.IndexedSeqView if .view is called.

For some reason for this line

val y: IndexedSeq[String] = collection.mutable.ArrayBuffer(1,2,3).view.map[String, IndexedSeq[String]](_ + "0")

this is inferred in typer:

 val y: IndexedSeq[String] = scala.collection.mutable.ArrayBuffer.apply[Int](1, 2, 3).view.map[String, IndexedSeq[String]](((x$1: Int) => x$1.+("0")))(mutable.this.IndexedSeq.canBuildFrom[String]);

so it is using a CanBuildFrom from IndexedSeq which isn't what usually happens with views where a call like this would fail because of a missing CBF.

I don't really understand what's going on in the collections </embarassing confession> but is it possible that mutable.IndexedSeqView is just missing the usual boilerplate for map et al.?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 9, 2012

@jsuereth said:
Ok, so it's a different bug now, really. No longer class cast exception, but the CanBuildFrom's are all off.

Here's a relevant snippet with the types inferred:

scala> val x = collection.mutable.ArrayBuffer(1,2,3)
x: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)

scala> x.view
res1: scala.collection.mutable.IndexedSeqView[Int,scala.collection.mutable.ArrayBuffer[Int]] = SeqView(...)

scala> res1 map (_ + "0")
res2: scala.collection.SeqView[String,scala.collection.mutable.Seq[_]] = SeqViewM(...)

We loose the IndexedSeqView after a map, which tells me either (a) it's not overridden (likely) or (b) it's missing an appropriate CanBuildFrom. If the answer is (a), I'll have to dig further. This may be a limitation on IndexedSeqView that after a transformation operation, you shouldn't treat it as an IndexedSeq anymore.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 9, 2012

@jsuereth said (edited on May 9, 2012 12:57:50 PM UTC):
Ok, a bit more information. We're running a fowl of variance restrictions (and correctness) here.

(1) mutable.IndexedViewSeq will actually manipulate the underlying collection at the view given.
(2) Any mapping operation drops from mutable.IndexedSeqView to SeqView. This in inherent in the fact that any mapping operation returns a new collection for mutable collections. This is actually expected and 'ok'. Otherwise what should the following do?

val x = collection.mutable.ArrayBuffer(1,2,3)
val y = x.view map (_ + "0")
val z = y.update(0, "O NOES")

(3) the "indexed" part of the type implies fast indexed lookup. That's not the case for views that have transformations.

It may be confusing to drop from an mutable.IndexSeqView to SeqView, but given the three points above, I'm thinking we have "correct" behavior here.

I'll try to flush out all the ClassCastExceptions and make sure you can't accidentally assign to IndexedSeq once you loose the "Indexed"-ness.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 9, 2012

@jrudolph said:
Are you really losing the "Indexed"-ness when mapping? If the function used with map is slow, accessing an element will be slow afterwards as well (because you are (re)calculating that entry) but that's the usual trade-off for using views. You may lose it for other transformations but in particular for map I don't necessarily think so.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 9, 2012

@jsuereth said:
You're not just loosing the IndexedSeq-ness (remember Seq has indexed operations for slower indexing), you're also losing mutability of the original collection. You can't allow the view to chain mutation back into the original.

SO yes. You're no longer a mutable.IndexedSeq after a map/flatMap/etc.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 10, 2012

@jrudolph said:
Oh yes, you are clearly right about mutability, I've forgot that. Maybe I could argue if it was about immutable.IndexedSeq but as you said since it has all the methods of Seq all of this discussion is only of theoretic relevance if at all. Sorry for the noise.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented May 20, 2013

@JamesIry said:
2.10.2 is about to be cut. Kicking down the road and un-assigning to foster work stealing.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Feb 10, 2014

@adriaanm said:
Since 2.11.0-RC1 is one week away, pushing all non-blockers without PR to 2.11.1-RC1. Please undo the change if I missed work in progress.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jun 27, 2014

@Ichoran said:
This can't be fixed without breaking binary compatibility. Changing fix version to 2.12.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Mar 20, 2015

@Ichoran said:
More related brokenness reported by Dima Golubets:

scala> Array(1, 2, 3, 4).view
res60: scala.collection.mutable.IndexedSeqView[Int,Array[Int]] = SeqView(...)
OK

scala> Array(1, 2, 3, 4).view.map{x => println(x); x}
res61: scala.collection.SeqView[Int,Array[Int]] = SeqViewM(...)
OK

scala> Array(1, 2, 3, 4).view.map{x => println(x); x}.map{x => println(x); x}
res62: Seq[Int] = SeqViewMM(...)
WTF? Why Seq?

After that point I can't call a force method. But I want to get some results so lets try:

scala> Array(1, 2, 3, 4).view.map{x => println(x); x}.map{x => println(x); x}.take(1).toList
1
1
res64: List[Int] = List(1)
OK..

scala> Array(1, 2, 3, 4).view.map{x => println(x); x}.map{x => println(x); x}.take(1).toArray
1
1
1
1
res65: Array[Int] = Array(1)
Double view evaluation!

Note that double view evaluation isn't forbidden by the contract, but views should perhaps be a little smarter about the choice of algorithm

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Oct 12, 2015

Iurii Gazin (archeg) said:
Not sure whether this is a separate bug or not, but it could be related:
I'm trying to work with a string as a view. From my perspective this should return SeqView:

"abc".view.updated(0, 'A')

But it returns Seq, the same as in previous comment. It looks like it's missing appropriate CanBuildFrom.

Seq('a', 'b', 'c').view.updated(0, 'A')

works fine.

It looks very similar to some of the code reported above, but this time it is about immutable structure.

Scala 2.11.2

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jun 23, 2016

@Ichoran said:
I am not sure there is a simple fix of the sort that should go in for RC1. To fix this (without exposing a bunch of other equivalent holes) I had to rewrite a lot of the views library to make it differently-consistent. The problem is that the function given to map is not invertible, so you can't very well change the original values. But it's also confusing that some methods detach you from the original collection while others do not.

I recommend punting until 2.13, @adriaanm @szeiger (at which point I may have time to get my tentative fixes in).

@scabug scabug added this to the 2.13.0-M1 milestone Apr 7, 2017

@adriaanm adriaanm modified the milestones: 2.13.0-M1, 2.13.0-M2 Apr 14, 2017

@szeiger szeiger modified the milestones: 2.13.0-M3, 2.13.0-M2 Jul 20, 2017

@adriaanm adriaanm modified the milestones: 2.13.0-M3, 2.13.0-M4 Jan 30, 2018

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Feb 17, 2018

likely fixed in strawman. leaving it on M4 milestone so we can check it once strawman lands

@lrytz

This comment has been minimized.

Copy link
Member

lrytz commented Apr 23, 2018

The view type herarchy is much more shallow in 2.13, which mean we lose some view functionality, but are no longer exposed to bugs like those in this ticket.

@lrytz lrytz closed this Apr 23, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment