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
nested extractors generate exponential-space bytecode #1133
Comments
Imported From: https://issues.scala-lang.org/browse/SI-1133?orig=1
|
@DRMacIver said: |
@rjolly said: import scala.xml.Elem
def f(expr: Elem) = expr match {
case <apply><plus/><apply><plus/>{x: Elem}{y: Elem}</apply>{z: Elem}</apply> => <apply><plus/>{x}<apply><plus/>{y}{z}</apply></apply>
case <apply><plus/><apply><minus/>{x: Elem}{y: Elem}</apply>{z: Elem}</apply> => <apply><minus/>{x}<apply><minus/>{y}{z}</apply></apply>
case <apply><plus/>{x: Elem}<apply><plus/>{y: Elem}{z: Elem}</apply></apply> if (x == y) => <apply><plus/><apply><times/><cn>2</cn>{x}</apply>{z}</apply>
case <apply><plus/>{x: Elem}<apply><minus/>{y: Elem}{z: Elem}</apply></apply> if (x == y) => <apply><minus/><apply><times/><cn>2</cn>{x}</apply>{z}</apply>
case <apply><plus/>{x: Elem}{y: Elem}</apply> if (x == y) => <apply><times/><cn>2</cn>{x}</apply>
case <apply><minus/><apply><plus/>{x: Elem}{y: Elem}</apply>{z: Elem}</apply> => <apply><plus/>{x}<apply><minus/>{y}{z}</apply></apply>
case <apply><minus/><apply><minus/>{x: Elem}{y: Elem}</apply>{z: Elem}</apply> => <apply><minus/>{x}<apply><plus/>{y}{z}</apply></apply>
case <apply><minus/>{x: Elem}<apply><plus/>{y: Elem}{z: Elem}</apply></apply> if (x == y) => <apply><minus/>{z}</apply>
case <apply><minus/>{x: Elem}<apply><minus/>{y: Elem}{z: Elem}</apply></apply> if (x == y) => z
case <apply><minus/>{x: Elem}{y: Elem}</apply> if (x == y) => <cn>0</cn>
case x => x
} I get the same error: java.lang.Error: ch.epfl.lamp.fjbg.JCode$$OffsetTooBigException: offset too big to fit in 16 bits: 33190 This is more or less the minimal set of case statements that triggers the error. If I remove one or two arbitrary ones, it compiles again. Of course I need many more to achieve what I intend, so this defect is very blocking to me. |
@paulp said: This should not fundamentally be a blocker though, because you can work around it simply by breaking up the pattern matches into more units. For instance you could follow however many cases with a default case which passes the scrutinee a new method that continues the pattern match. I realize this is annoying, but at least it's straightforward. |
@rjolly said: |
@DRMacIver said: |
Kieron Wilkinson (kieron) said: import scala.util.matching.Regex
object Tokeniser {
val prefix = """[0-9a-f]{8}:[\s]+"""
val StatusRegex = new Regex(prefix + """status=0""")
val ResetRegex = new Regex(prefix + """reset=0""")
val DensityRegex = new Regex(prefix + """density=(\d)""")
val MinTrackRegex = new Regex(prefix + """min_track=(\d+)""")
val MaxTrackRegex = new Regex(prefix + """max_track=(\d+)""")
val MotorRegex = new Regex(prefix + """motor=([0-1])""")
val TrackRegex = new Regex(prefix + """track=(\d+)""")
val SideRegex = new Regex(prefix + """side=([0-1])""")
val StreamRegex = new Regex(prefix + """stream=([0-1])""")
def go(text: String): String = text.trim match {
case StatusRegex() => ""
case ResetRegex() => ""
case DensityRegex(density) => ""
case MinTrackRegex(track) => ""
case MaxTrackRegex(track) => ""
case MotorRegex(on) => ""
case TrackRegex(track) => ""
case SideRegex(side) => ""
case StreamRegex(on) => ""
}
} And the exception I get is: Exception in thread "main" java.lang.Error: ch.epfl.lamp.fjbg.JCode$$OffsetTooBigException: offset to
o big to fit in 16 bits: 55087
at ch.epfl.lamp.fjbg.JFieldOrMethod.writeTo(JFieldOrMethod.java:114)
at ch.epfl.lamp.fjbg.JClass.writeTo(JClass.java:315)
at scala.tools.nsc.backend.jvm.GenJVM$$BytecodeGenerator.emitClass(GenJVM.scala:150)
at scala.tools.nsc.backend.jvm.GenJVM$$BytecodeGenerator.genClass(GenJVM.scala:241)
at scala.tools.nsc.backend.jvm.GenJVM$$JvmPhase.apply(GenJVM.scala:57)
at scala.tools.nsc.backend.jvm.GenJVM$$JvmPhase$$$$anonfun$$run$$3.apply(GenJVM.scala:53)
at scala.tools.nsc.backend.jvm.GenJVM$$JvmPhase$$$$anonfun$$run$$3.apply(GenJVM.scala:53)
at scala.collection.Iterator$$class.foreach(Iterator.scala:582)
at scala.collection.mutable.HashMap$$$$anon$$4.foreach(HashMap.scala:82)
at scala.tools.nsc.backend.jvm.GenJVM$$JvmPhase.run(GenJVM.scala:53)
at scala.tools.nsc.Global$$Run.compileSources(Global.scala:749)
at scala.tools.nsc.Global$$Run.compile(Global.scala:839)
at scala.tools.nsc.Main$$.process(Main.scala:110)
at scala.tools.nsc.Main$$.main(Main.scala:124)
at scala.tools.nsc.Main.main(Main.scala)
Caused by: ch.epfl.lamp.fjbg.JCode$$OffsetTooBigException: offset too big to fit in 16 bits: 55087
at ch.epfl.lamp.fjbg.JCode.checkOffset16(JCode.java:896)
at ch.epfl.lamp.fjbg.JCode.patchAllOffset(JCode.java:975)
at ch.epfl.lamp.fjbg.JCode.freeze(JCode.java:95)
at ch.epfl.lamp.fjbg.JMethod.freeze(JMethod.java:81)
at ch.epfl.lamp.fjbg.JFieldOrMethod.writeTo(JFieldOrMethod.java:111)
... 14 more If I remove any of the cases, it works fine, so I will try to break it up as suggested. I did have a lot more cases to add too :) |
Alex Black (alexblack) said: java.lang.Error: ch.epfl.lamp.fjbg.JCode$$OffsetTooBigException: offset too big to fit in 16 bits: 36197 |
tomer.doron said: |
Willis Blackburn (willisblackburn) said: |
@paulp said:
What is missing are not ideas, but implementations. |
Willis Blackburn (willisblackburn) said:
That's good to hear. What would happen if the compiler silently translated any code of the form x match {
case p1 => r1;
case p2 => r2;
...
} into {code} ? Would that destroy the performance of the match operation? Maybe it would create lots of new function objects? |
@paulp said:
You can try it out if you like, I implemented that a year ago. It's under -Ypmat-naive. It's not viable for general usage, but I don't remember every reason. Here's what the source comment says. /** For debugging only. Desugar a match statement like so:
* val x = scrutinee
* x match {
* case case1 => ...
* case _ => x match {
* case case2 => ...
* case _ => x match ...
* }
* }
*
* This way there are never transitions between nontrivial casedefs.
* Of course many things break: exhaustiveness and unreachable checking
* do not work, no switches will be generated, etc.
*/ |
Dustin Whitney (dwhitney) said: def intent = { That code is not in need of refactoring or ugly at all. In fact this issue makes me take things that are otherwise understandable and break them apart into things that are less understandable. |
Toni Menzel (tonit) said: |
Toni Menzel (tonit) said: |
@dcsobral said (edited on Nov 1, 2011 11:43:46 AM UTC): dcs@ayanami:~/tmp$ scalac -Yvirtpatmat Tokeniser.scala
dcs@ayanami:~/tmp$ Yay! |
@dcsobral said: object TokeniserTest extends Properties("Tokeniser") {
val hexDigit = Gen oneOf (('0' to '9') ++ ('a' to 'f'))
val identifier = Gen listOfN (8, hexDigit) map (_.mkString)
val command0 = Gen oneOf ("status", "reset") map (_ + "=0")
val command01 = for {
cmd <- Gen oneOf ("motor", "side", "stream")
digit <- Gen oneOf ("0", "1")
} yield cmd + "=" + digit
val commandX = Gen oneOf ('0' to '9') map ("density="+_)
val commandN = for {
cmd <- Gen oneOf ("min_track", "max_track", "track")
number <- Gen.numStr suchThat (_.size > 0)
} yield cmd + "=" + number
val textGen = for {
i <- id
cmd <- Gen oneOf (command0, command01, commandX, commandN)
} yield i + ": " + cmd
property("Parsing") = forAllNoShrink(textGen) ( text => Tokeniser.go(text)
matches """(status|reset|density \d+|(min |max )?track \d+|(motor|stream) (on|off)|side \d+)""" )
} |
Matic Potočnik (hairyfotr) said: The code I had trouble with is way too messy to post, but I also confirm it works with Kierons case. |
@retronym said: |
Pattern matching multiple cases against extractors triggers a combination explosion that quickly overwhelms the maximum method size. This has bitten me quite hard on my in-progress java to scala translator, as I use extractors against the JDT for parsing java source. I have attached a demonstration. You can make a minor tweak to the attached source and see the size of the bytecode drop in half (or double again, if FJBG wouldn't choke.)
leaf:dfascala paulp$$ scalac *.scala
Exception in thread "main" java.lang.Error: ch.epfl.lamp.fjbg.JCode$$OffsetTooBigException: offset too big to fit in 16 bits: 36580
at ch.epfl.lamp.fjbg.JFieldOrMethod.writeTo(JFieldOrMethod.java:114)
[...]
The disassembled bytecode reveals enormous nested if-else statements with massive duplicated code.
The text was updated successfully, but these errors were encountered: