Skip to content

2.8 "no-symbol does not have owner" in lambdalift phase #2316

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.

Sign up for GitHub

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

Jump to bottom
Closed
scabug opened this issue Sep 1, 2009 · 25 comments
Closed

2.8 "no-symbol does not have owner" in lambdalift phase #2316

scabug opened this issue Sep 1, 2009 · 25 comments
Assignees
@adriaanm

Comments

@scabug
Copy link

scabug commented Sep 1, 2009

See also #710 and #805. I've attached the full console output. It dies in the lambdalift phase

How can I find out what the compiler was doing when this error arose? Its a bit hard to produce a minimal test case without this.

A decidedly un-minimal test case is here: http://scalaz.googlecode.com/svn/branches/scala-2.8, SVN revision 825.

I'm on version 2.8.0.r18583-b20090827020153
@scabug
Copy link
Author

scabug commented Sep 1, 2009

Imported From: https://issues.scala-lang.org/browse/SI-2316?orig=1
Reporter: @retronym
Attachments:

@scabug
Copy link
Author

scabug commented Sep 1, 2009

@retronym said:
console output of compilation

@scabug
Copy link
Author

scabug commented Sep 2, 2009

@paulp said:
It sounds like #2201, which I have a patch for but do not want to commit without it being approved (or more likely, improved) by martin or adriaan. That was the bug that needed to be fixed for scalacheck to compile and it's very believable that scalaz and scalacheck would induce the same bugs.

If you want you can build the repo with the patch and see if it works - or hopefully it'll be in trunk soon. http://github.com/paulp/scala/tree/scalacheck

@scabug
Copy link
Author

scabug commented Sep 5, 2009

@retronym said:
I've just tried the patched compiler. It gets past the first instance of this error -- encountered compiling the scalacheck sources, which are svn:external-ed into the Scalaz build -- but there is another case in triggered by the Scalaz sources proper.

I've got it pinned down in the debugger, so I'll narrow it down and post a test case soon.

-jason

@scabug
Copy link
Author

scabug commented Sep 5, 2009

@retronym said:
Analysis of the failure during lambda lift phase

@scabug
Copy link
Author

scabug commented Sep 5, 2009

@retronym said:
I took a look at this in the debugger, and attached an analysis. Still can't pare it down to a small example, unfortunately :(

      Transforming unit Pointed.scala. Inspection of the AST here shows that 's' in PromisePure(s) already has the wrong symbol. I expect it to
      be the parameter 's' from PromisePointed, instead it is bound to the parameter 's' from another file.
      
        // Pointed.scala
        trait Pointed[P[_]] extends Functor[P] with Pure[P]

        object Pointed {
           import concurrent._
           implicit def PromisePointed(implicit s: Strategy[Unit]) = pointed[Promise]
   // = Pointed.this.pointed(
   //         scalaz.this.Functor.PromiseFunctor(),
   //   scalaz.this.Pure.PromisePure(s).$$asInstanceOf[scalaz.Pure]())
   //                                |__ 's' bound to out-of-scope implicit
   //                                     param of Applicative.PromiseApplicative()!
        }
      
        //Applicative.scala:
        trait Applicative[Z[_]] extends Pointed[Z] with Apply[Z] {
          override def fmap[A, B](fa: Z[A], f: A => B): Z[B] = apply(pure(f), fa)
        }

        object Applicative {
           implicit def PromiseApplicative(implicit s: Strategy[Unit]) = applicative[Promise]           
        }

@scabug
Copy link
Author

scabug commented Sep 8, 2009

@cunei said:
Adriaan, could you please review Paul's patch? Thanks!

@scabug
Copy link
Author

scabug commented Sep 11, 2009

@adriaanm said:
Patch committed as fix for #2201 in r18692

@scabug
Copy link
Author

scabug commented Sep 12, 2009

@retronym said:
small test case

@scabug
Copy link
Author

scabug commented Sep 12, 2009

@retronym said:

usr$$ ~/usr/scala-2.8.0.r18697/bin/scala ~/Desktop/implicit-cache-error.scala 
java.lang.Error: no-symbol does not have owner
	at scala.tools.nsc.symtab.Symbols$$NoSymbol$$.owner(Symbols.scala:1869)
        ...

Oddly, scalac doesn't produce the error, but you can see the reference to an out-of-scope symbol from test.A.B2 with -uniqid -print:

def thisSI-11202(): object test$$A$$B1SI-11193 = {
      test$$A$$B1SI-11193.super.thisSI-3699();
      test$$A$$B1SI-11193.this.t2_b1SI-11204 = {
        new test$$A$$B1$$$$anon$$2SI-11206()
      };
      test$$ASI-7966.this.requireT1SI-11191(test$$T1SI-7962.T1FromT2SI-11170(test$$A$$B1SI-11193.this.t2_b1SI-11203().$$asInstanceOfSI-6888[test$$T2SI-7964]()).$$asInstanceOfSI-6888[test$$T1SI-7961]());
      ()
    }
    ...
    
    def thisSI-11564(): object test$$A$$B2SI-11195 = {
      test$$A$$B2SI-11195.super.thisSI-3699();
      test$$A$$B2SI-11195.this.t2_b2SI-11566 = {
        new test$$A$$B2$$$$anon$$3SI-11568()
      };
      test$$ASI-7966.this.requireT1SI-11191(test$$T1SI-7962.T1FromT2SI-11170(test$$A$$B1SI-11193.this.t2_b1SI-11203().$$asInstanceOfSI-6888[test$$T2SI-7964]()).$$asInstanceOfSI-6888[test$$T1SI-7961]());
      ()
    }

Implicits are being cached too aggressively. The patch recently applied for #2201 should be reviewed in light of this test case.

Implicits.cacheResult returns T1.T1FromT2(t2_b1) here, which is bogus. Even though T1.T1FromT2 was found outside of the scope of A.B1, this implicit expression should not be cached, as it includes the bound variable t2_b1 from this scope.

SearchResult could be augmented with an attribute cacheable. In Implicits.bestImplicits(), if the first search in the local context succeeds, return SearchResult(tree, subst, cacheable = false). This would need to be propagated for SearchResults that themselves depend on implicits.

Implicits.cacheResult would then ensure that only cacheable SearchResult-s are cached.

@scabug
Copy link
Author

scabug commented Sep 13, 2009

@retronym said:
Another example of seemingly innocent implicit caching going wrong.

@scabug
Copy link
Author

scabug commented Sep 13, 2009

@retronym said:
Added another test case that invalidates my suggested algorithm for determining 'cacheability' of implicits. This is something of a can of worms. May I suggest -Xdisable-implicit-caching in the meantime?

@scabug
Copy link
Author

scabug commented Sep 13, 2009

@retronym said:
Patch to only cache non-local implicits if safe to do so.

@scabug
Copy link
Author

scabug commented Sep 13, 2009

@retronym said:
I've implemented a simpler solution, whereby only the results of implicitsOfExpectedType() are cached.

http://github.com/retronym/scala/commits/implicit-caching

@scabug
Copy link
Author

scabug commented Sep 22, 2009

@retronym said:
Patch from http://github.com/retronym/scala/tree/implicit-cache

@scabug
Copy link
Author

scabug commented Sep 22, 2009

@retronym said:
Could you consider the attached patch? It is based on my 'implicit-caching' tree on github, mentioned above. Two new test cases are included, it simplifies implicit caching, and is ready to integrate.

@scabug
Copy link
Author

scabug commented Sep 22, 2009

@paulp said:
Replying to [comment:10 retronym]:

Could you consider the attached patch? It is based on my 'implicit-caching' tree on github, mentioned above. Two new test cases are included, it simplifies implicit caching, and is ready to integrate.

Very sorry nobody has responded to you on this; the problem is that martin is almost the only person who can properly assess a patch in this area, and he is buried. I am promoting myself to basically-capable-of-assessing and will take a look at all this right now.

On a separate note, thank you very much for your work on #2337, which is definitely #1697. I already had that fairly specifically diagnosed, but fixing it has been far more elusive than it ought to be because of the opaque way the pattern matcher constructs its automaton. Regardless, another pair of eyes on these bugs is tremendously useful, and test cases and actual patches puts you in a seriously elite group -- so please don't be discouraged by the difficulty (unusually high right now with 2.8 around the corner) of getting the attention of committers.

@scabug
Copy link
Author

scabug commented Sep 22, 2009

@adriaanm said:
Thanks, Paul, for taking the time to thank Jason on our behalf ;-)
I did have a look earlier, but am also quite busy as I'm moving country in a couple days.
The patch looks okay on the surface, except I couldn't convince myself in the timeframe that I had that the issue with reusing symbols for different bound variables won't occur.

Martin recently changed implicit caching to be more coarse-grained. Can you give us some numbers on how much your patch (applied to trunk) speeds up worst/average/best case? Could you motivate how the duplicate bound variables issue with the previous cache is avoided now?

Thanks for contributing!

@scabug
Copy link
Author

scabug commented Sep 22, 2009

@paulp said:
Replying to [comment:12 moors]:

Thanks, Paul, for taking the time to thank Jason on our behalf ;-)

Thank you for taking the time to acknowledge my valuable role as a proxy for gratitude expression. (No thanks necessary for this beautiful almost hand-written thank-you note.)

@scabug
Copy link
Author

scabug commented Sep 23, 2009

@retronym said:
Okay -- leaving gratitude aside for a moment -- back to to bits.

To be clear, the latest patch I propose is http://lampsvn.epfl.ch/trac/scala/attachment/ticket/2316/no-owner.patch . It is based on: http://github.com/retronym/scala/commits/implicit-caching (not implicit-cache as I wrote above.)

The key change is

-  val implicitsCache = new LinkedHashMap[AnyRef, SearchResult]
+  val implicitsCache = new LinkedHashMap[Type, List[List[ImplicitInfo]]]

This cache is interrogated when looking for implicits from the implicit import scope, that is, to look for an implicit of type T in the companion object of T and the companion objects of its super-types.

Previously, the entire !SearchResult was cached, which could contain symbols local to the scope of the search that were used as implicit parameters, and hence not safely cacheable. These tests demonstrate best the problems with this approach. r1

With the patch, the cache only stores information gleaned from the implicit import scope r2. When no in-scope implicit is found, the current context and cached implicitInfoss are used to find a search result r3, which may contain bound variables used as implicit parameters. As such, it is not cached.

I tried a more complex version that detected SearchResults that contained no bound variables and cached them, but this was complex, not driven by performance measurements and as such probably wrongheaded.

r1 http://github.com/retronym/scala/commit/f0bfbfc3234bd9c7349e740b6dff50aac5f7ca4b
r2 http://github.com/retronym/scala/blob/implicit-caching/src/compiler/scala/tools/nsc/typechecker/Implicits.scala#L578
r3 http://github.com/retronym/scala/blob/implicit-caching/src/compiler/scala/tools/nsc/typechecker/Implicits.scala#L695
Every time an implicit search occurs, this information is combined with the

I haven't done any performance testing, but to paraphrase Joe Armstrong, an incorrect implementation can be made arbitrarily fast.

@scabug
Copy link
Author

scabug commented Sep 28, 2009

@retronym said:
I timed the compilation of Scalaz, patched to workaround this bug, using scalac r18697 nightly, and r18701 + the patch. The time in implicits, and total compile time were almost identical over a few repeats.

r18697

> get forked.compiler.jar
/Users/jason/usr/scala-2.8.0.r18697/lib/scala-compiler.jar
> clean                  
[info] 
[info] == clean ==
[info] Deleting directory /Users/jason/code/scalaz-2.8/target
[info] == clean ==
[success] Successful.
[info] 
[info] Total time: 2 s
> compile                
[info] 
[info] == compile ==
[info] Compiling main sources...
[error] *** Cumulative statistics at phase typer
[error] #tree nodes  : 500454
[error] #identifiers : 36475
[error] #selections  : 31258
[error] #applications: 9059
[error] #implicits   : 3737
[error] #uniquetypes : 544544
[error] #symbols     : 417366
[error] #type symbols: 83027
[error] #class symbols: 49628
[error] #singleton closures: 0
[error] #compound closures : 4775
[error] #typeref closures  : 13220
[error] #findMember     : 957382
[error] #notfound member: 145749
[error] #multiple member: 5194
[error] time findMember: 0
[error] #norm meth   : 47285
[error] #norm poly   : 45
[error] #norm other  : 274481
[error] #subtype     : 0
[error] ns subtype   : 0
[error] #sametype    : 124926
[error] #unique types: 544544
[error] ms type-flow-analysis: 0
[error] time spent typechecking: 100.0 / 43651216000ns
[error] time spent in implicits: 106.8 / 46608085000ns
[error]     successful in scope: 33.4 / 14581283000ns
[error]         failed in scope: 25.6 / 11155622000ns
[error]      successful of type: 41.7 / 18210703000ns
[error]          failed of type: 6.0 / 2613996000ns
[error]     successful manifest: 0.0 / 18806000ns
[error]         failed manifest: 0.0 / 10825000ns
[error] implicit cache hitratio: 32.3
[error] implicit cache coverage: 100.0
[error] time spent in failed   : 0.3 / 146208000ns
[error]        failed op=      : 0.3 / 146262000ns
[error]        failed apply    : 0.0 / 0ns
[error] *** Cumulative statistics at phase erasure
[error] #tree nodes  : 1067694
[error] #identifiers : 36737
[error] #selections  : 36292
[error] #applications: 19020
[error] #implicits   : 3737
[error] #uniquetypes : 557779
[error] #symbols     : 525311
[error] #type symbols: 88792
[error] #class symbols: 55036
[error] #singleton closures: 0
[error] #compound closures : 10480
[error] #typeref closures  : 14985
[error] #findMember     : 1056851
[error] #notfound member: 151184
[error] #multiple member: 30685
[error] time findMember: 0
[error] #norm meth   : 47285
[error] #norm poly   : 45
[error] #norm other  : 277395
[error] #subtype     : 0
[error] ns subtype   : 0
[error] #sametype    : 187189
[error] #unique types: 557779
[error] ms type-flow-analysis: 0
[error] *** Cumulative statistics at phase cleanup
[error] #tree nodes  : 1358780
[error] #identifiers : 39335
[error] #selections  : 40912
[error] #applications: 20765
[error] #implicits   : 3737
[error] #uniquetypes : 562345
[error] #symbols     : 555738
[error] #type symbols: 88837
[error] #class symbols: 55042
[error] #singleton closures: 0
[error] #compound closures : 21096
[error] #typeref closures  : 19301
[error] #findMember     : 1094544
[error] #notfound member: 158122
[error] #multiple member: 43342
[error] time findMember: 0
[error] #norm meth   : 47285
[error] #norm poly   : 45
[error] #norm other  : 278648
[error] #subtype     : 0
[error] ns subtype   : 0
[error] #sametype    : 197127
[error] #unique types: 562345
[error] ms type-flow-analysis: 0
[info] Compilation successful.
[info] == compile ==
[success] Successful.
[info] 
[info] Total time: 105 s

r18701 with patch

> get forked.compiler.jar
/Users/jason/code/scala-lang-retronym/scala/build/pack/lib/scala-compiler.jar
> clean                  
[info] 
[info] == clean ==
[info] Deleting directory /Users/jason/code/scalaz-2.8/target
[info] == clean ==
[success] Successful.
[info] 
[info] Total time: 2 s
> compile                
[info] 
[info] == compile ==
[info] Compiling main sources...
[error] *** Cumulative statistics at phase typer
[error] #tree nodes  : 499904
[error] #identifiers : 36506
[error] #selections  : 31499
[error] #applications: 9095
[error] #implicits   : 3749
[error] #uniquetypes : 552168
[error] #symbols     : 426764
[error] #type symbols: 87898
[error] #class symbols: 52204
[error] #singleton closures: 0
[error] #compound closures : 4771
[error] #typeref closures  : 13218
[error] #findMember     : 1005704
[error] #notfound member: 149318
[error] #multiple member: 5194
[error] time findMember: 0
[error] #norm meth   : 49235
[error] #norm poly   : 45
[error] #norm other  : 285112
[error] #subtype     : 0
[error] ns subtype   : 0
[error] #sametype    : 126318
[error] #unique types: 552168
[error] ms type-flow-analysis: 0
[error] time spent typechecking: 100.0 / 43569496000ns
[error] time spent in implicits: 107.0 / 46607210000ns
[error]     successful in scope: 32.7 / 14256010000ns
[error]         failed in scope: 26.1 / 11361695000ns
[error]      successful of type: 43.1 / 18774723000ns
[error]          failed of type: 5.0 / 2169973000ns
[error]     successful manifest: 0.0 / 10685000ns
[error]         failed manifest: 0.0 / 20858000ns
[error] implicit cache hitratio: 32.6
[error] implicit cache coverage: 100.0
[error] time spent in failed   : 0.4 / 159905000ns
[error]        failed op=      : 0.4 / 159953000ns
[error]        failed apply    : 0.0 / 0ns
[error] *** Cumulative statistics at phase erasure
[error] #tree nodes  : 1067144
[error] #identifiers : 36768
[error] #selections  : 36533
[error] #applications: 19056
[error] #implicits   : 3749
[error] #uniquetypes : 565401
[error] #symbols     : 534709
[error] #type symbols: 93663
[error] #class symbols: 57612
[error] #singleton closures: 0
[error] #compound closures : 10476
[error] #typeref closures  : 14983
[error] #findMember     : 1105173
[error] #notfound member: 154753
[error] #multiple member: 30685
[error] time findMember: 0
[error] #norm meth   : 49235
[error] #norm poly   : 45
[error] #norm other  : 288026
[error] #subtype     : 0
[error] ns subtype   : 0
[error] #sametype    : 188581
[error] #unique types: 565401
[error] ms type-flow-analysis: 0
[error] *** Cumulative statistics at phase cleanup
[error] #tree nodes  : 1358230
[error] #identifiers : 39366
[error] #selections  : 41153
[error] #applications: 20801
[error] #implicits   : 3749
[error] #uniquetypes : 569967
[error] #symbols     : 565136
[error] #type symbols: 93708
[error] #class symbols: 57618
[error] #singleton closures: 0
[error] #compound closures : 21092
[error] #typeref closures  : 19299
[error] #findMember     : 1142866
[error] #notfound member: 161691
[error] #multiple member: 43342
[error] time findMember: 0
[error] #norm meth   : 49235
[error] #norm poly   : 45
[error] #norm other  : 289279
[error] #subtype     : 0
[error] ns subtype   : 0
[error] #sametype    : 198519
[error] #unique types: 569967
[error] ms type-flow-analysis: 0
[info] Compilation successful.
[info] == compile ==
[success] Successful.
[info] 
[info] Total time: 103 s

@scabug
Copy link
Author

scabug commented Sep 29, 2009

@adriaanm said:
Thanks, I committed your fix as r18825.

@scabug
Copy link
Author

scabug commented Sep 29, 2009

@retronym said:
I just noticed two minor things to clean up:

scala/trunk/src/compiler/scala/tools/nsc/util/Statistics.scala:60

Delete this line logging of "implicit cache coverage", it is now always 100%

scala/trunk/src/compiler/scala/tools/nsc/ast/Trees.scala:1717

remove 'case' from 'case class !TreeTypeSubstituter'

@scabug
Copy link
Author

scabug commented Sep 30, 2009

@adriaanm said:
Martin says we need to do better, at least benchmark compiling against the collection libraries as, compiler performance depends crucially on caching in that case.
Clearly, the behaviour before this patch was erroneous, but we probably need a more refined caching strategy.
Can we come up with a safe fast-path that covers the typical case in the collections where the same implicit is found over and over again (typically a Manifest)

@scabug
Copy link
Author

scabug commented Oct 1, 2009

@adriaanm said:
It turns out that the safe caching scheme is actually better at compiling the compiler than the unsafe one -- leaving it in place for now.

On my macbook(*):

ant quick.comp (with locker that employs the specified implicit caching scheme, based on r18850):
NO CACHING AT ALL [quick.comp.timer: 3:42.670 sec]
ORIGINAL UNSAFE CACHING SCHEME [quick.comp.timer: 3:39.467 sec]
NEW SAFE CACHING SCHEME [quick.comp.timer: 3:33.377 sec]

(*) 10.5.8, C2D 2.4 GHz 4GB RAM, Java HotSpot(TM) 64-Bit Server VM (build 14.1-b02-92, mixed mode)

@scabug scabug closed this as completed May 18, 2011
This was referenced Apr 7, 2017
Closed
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@adriaanm adriaanm

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@adriaanm @scabug