Skip to content

Dignostic code for RedBlackTree#107

Closed
retronym wants to merge 13 commits into2.12.xfrom
review/9326
Closed

Dignostic code for RedBlackTree#107
retronym wants to merge 13 commits into2.12.xfrom
review/9326

Conversation

@retronym
Copy link
Owner

@retronym retronym commented Nov 20, 2020

Build atop scala#9326

TreeMapTest.randomTree:

/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/bin/java -ea -Didea.test.cyclic.buffer.size=1048576 -javaagent:/Users/jz/Library/Application Support/JetBrains/Toolbox/apps/IDEA-U/ch-0/203.5784.10/IntelliJ IDEA 2020.3 EAP.app/Contents/lib/idea_rt.jar=55222:/Users/jz/Library/Application Support/JetBrains/Toolbox/apps/IDEA-U/ch-0/203.5784.10/IntelliJ IDEA 2020.3 EAP.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/jz/Library/Application Support/JetBrains/Toolbox/apps/IDEA-U/ch-0/203.5784.10/IntelliJ IDEA 2020.3 EAP.app/Contents/lib/idea_rt.jar:/Users/jz/Library/Application Support/JetBrains/Toolbox/apps/IDEA-U/ch-0/203.5784.10/IntelliJ IDEA 2020.3 EAP.app/Contents/plugins/junit/lib/junit5-rt.jar:/Users/jz/Library/Application Support/JetBrains/Toolbox/apps/IDEA-U/ch-0/203.5784.10/IntelliJ IDEA 2020.3 EAP.app/Contents/plugins/junit/lib/junit-rt.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/charsets.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/cldrdata.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/dnsns.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/jaccess.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/localedata.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/nashorn.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/sunec.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/ext/zipfs.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/jce.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/jfr.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/jsse.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/management-agent.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/resources.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/jre/lib/rt.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/lib/dt.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/lib/jconsole.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/lib/sa-jdi.jar:/Users/jz/.jabba/jdk/adopt@1.8.0-272/Contents/Home/lib/tools.jar:/Users/jz/code/scala/target/junit/test-classes:/Users/jz/code/scala/build/quick/classes/library:/Users/jz/code/scala/build/quick/classes/reflect:/Users/jz/code/scala/build/quick/classes/compiler:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/apache/ant/ant/1.9.4/ant-1.9.4.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/jline/jline/2.14.6/jline-2.14.6.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/modules/scala-xml_2.12/1.0.6/scala-xml_2.12-1.0.6.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/fusesource/jansi/jansi/1.12/jansi-1.12.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/apache/ant/ant-launcher/1.9.4/ant-launcher-1.9.4.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/modules/scala-asm/7.3.1-scala-1/scala-asm-7.3.1-scala-1.jar:/Users/jz/code/scala/build/quick/classes/repl:/Users/jz/code/scala/build/quick/classes/interactive:/Users/jz/code/scala/build/quick/classes/scaladoc:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/webjars/jquery/3.5.1/jquery-3.5.1.jar:/Users/jz/code/scala/build/quick/classes/partest:/Users/jz/code/scala/build/quick/classes/scalap:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/scala-sbt/test-interface/1.0/test-interface-1.0.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/com/googlecode/java-diff-utils/diffutils/1.3.0/diffutils-1.3.0.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/junit/junit/4.12/junit-4.12.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar:/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/openjdk/jol/jol-core/0.13/jol-core-0.13.jar com.intellij.rt.junit.JUnitStarter -ideVersion5 -junit4 scala.collection.immutable.TreeMapTest,randomTree

java.lang.IllegalStateException: bad tree:
 BlackTree(49, ())#1633
  BlackTree(32, ())#1278
    BlackTree(13, ())#1274
      RedTree(1, ())#1172
        Empty
        Empty
      Empty
    BlackTree(39, ())#1275
      Empty
      Empty
  RedTree(271, ())#1631
    BlackTree(125, ())#1629
      BlackTree(112, ())#387
        Empty
        Empty
      BlackTree(159, ())#1107
        RedTree(149, ())#1106
          Empty
          Empty
        RedTree(254, ())#905
          Empty
          Empty
    BlackTree(387, ())#1630
      BlackTree(360, ())#1219
        RedTree(307, ())#1218
          Empty
          Empty
        Empty
      RedTree(441, ())#1626 !! Red contains Red
        BlackTree(438, ())#420
          Empty
          Empty
        RedTree(469, ())#1625
          BlackTree(457, ())#1623
            Empty
            Empty
          BlackTree(473, ())#1624
            Empty
            Empty


:expected: 
BlackTree(254, ())#1652
  BlackTree(49, ())#1642
    BlackTree(13, ())#1637
      BlackTree(1, ())#1634
        Empty
        Empty
      BlackTree(32, ())#1636
        Empty
        RedTree(39, ())#1635
          Empty
          Empty
    BlackTree(125, ())#1641
      BlackTree(112, ())#1638
        Empty
        Empty
      BlackTree(149, ())#1640
        Empty
        RedTree(159, ())#1639
          Empty
          Empty
  BlackTree(438, ())#1651
    BlackTree(307, ())#1646
      BlackTree(271, ())#1643
        Empty
        Empty
      BlackTree(360, ())#1645
        Empty
        RedTree(387, ())#1644
          Empty
          Empty
    BlackTree(457, ())#1650
      BlackTree(441, ())#1647
        Empty
        Empty
      BlackTree(469, ())#1649
        Empty
        RedTree(473, ())#1648
          Empty
          Empty
.

original input tree|b: BlackTree(616, ())#1595
  BlackTree(387, ())#1594
    RedTree(49, ())#1280
      BlackTree(32, ())#1278
        BlackTree(13, ())#1274
          RedTree(1, ())#1172
            Empty
            Empty
          Empty
        BlackTree(39, ())#1275
          Empty
          Empty
      BlackTree(125, ())#1279
        BlackTree(112, ())#387
          Empty
          Empty
        RedTree(271, ())#1220
          BlackTree(159, ())#1107
            RedTree(149, ())#1106
              Empty
              Empty
            RedTree(254, ())#905
              Empty
              Empty
          BlackTree(360, ())#1219
            RedTree(307, ())#1218
              Empty
              Empty
            Empty
    BlackTree(473, ())#1593
      RedTree(441, ())#1592
        BlackTree(438, ())#420
          Empty
          Empty
        BlackTree(457, ())#1591
          Empty
          RedTree(469, ())#1590
            Empty
            Empty
      RedTree(577, ())#1483
        BlackTree(546, ())#648
          Empty
          Empty
        BlackTree(584, ())#1482
          RedTree(580, ())#1481
            Empty
            Empty
          RedTree(615, ())#739
            Empty
            Empty
  BlackTree(794, ())#1552
    RedTree(721, ())#1441
      BlackTree(688, ())#1439
        BlackTree(643, ())#1384
          RedTree(640, ())#1383
            Empty
            Empty
          Empty
        BlackTree(693, ())#1435
          Empty
          Empty
      BlackTree(767, ())#1440
        BlackTree(758, ())#1436
          Empty
          Empty
        BlackTree(786, ())#946
          Empty
          Empty
    BlackTree(905, ())#1551
      RedTree(888, ())#1342
        BlackTree(814, ())#1340
          Empty
          Empty
        BlackTree(889, ())#1341
          Empty
          Empty
      RedTree(986, ())#1550
        BlackTree(957, ())#1549
          Empty
          RedTree(971, ())#1548
            Empty
            Empty
        BlackTree(999, ())#806
          Empty
          Empty


	at scala.collection.immutable.NewRedBlackTree$.scala$collection$immutable$NewRedBlackTree$$validate(RedBlackTree.scala:273)
	at scala.collection.immutable.NewRedBlackTree$.result(RedBlackTree.scala:232)
	at scala.collection.immutable.NewRedBlackTree$.to(RedBlackTree.scala:192)
	at scala.collection.immutable.TreeSet.to(TreeSet.scala:243)
	at scala.collection.immutable.TreeMapTest.$anonfun$randomTree$1(TreeMapTest.scala:117)
	at scala.collection.immutable.TreeMapTest.$anonfun$randomTree$1$adapted(TreeMapTest.scala:107)
	at scala.collection.immutable.Range.foreach(Range.scala:158)
	at scala.collection.immutable.TreeMapTest.randomTree(TreeMapTest.scala:107)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
	at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
	at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
	at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
	at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:69)
	at com.intellij.rt.junit.IdeaTestRunner$Repeater.startRunnerWithArgs(IdeaTestRunner.java:33)
	at com.intellij.rt.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:220)
	at com.intellij.rt.junit.JUnitStarter.main(JUnitStarter.java:53)
Caused by: java.lang.IllegalStateException: at RedTree#1626 (k=441) right is also red 469
	at scala.collection.immutable.NewRedBlackTree$.checkAdjacentRed$1(RedBlackTree.scala:247)
	at scala.collection.immutable.NewRedBlackTree$.scala$collection$immutable$NewRedBlackTree$$validate(RedBlackTree.scala:267)
	... 29 more
Caused by: java.lang.Throwable: tree created stack trace
	at scala.collection.immutable.NewRedBlackTree$Tree.<init>(RedBlackTree.scala:619)
	at scala.collection.immutable.NewRedBlackTree$Tree.withRight(RedBlackTree.scala:787)
	at scala.collection.immutable.NewRedBlackTree$.balanceRight(RedBlackTree.scala:445)
	at scala.collection.immutable.NewRedBlackTree$.upd(RedBlackTree.scala:467)
	at scala.collection.immutable.NewRedBlackTree$.doTo(RedBlackTree.scala:499)
	at scala.collection.immutable.NewRedBlackTree$.doTo(RedBlackTree.scala:497)
	at scala.collection.immutable.NewRedBlackTree$.doTo(RedBlackTree.scala:496)
	... 28 more

jtjeferreira and others added 11 commits October 24, 2020 16:25
This reverts commit 8662d4a.

It is a very important API, but the compiler's binary API isn't stable.

This got confused because scala-rewrites is special in the
community-build as it uses binary dependencies (for scalafix/scalameta
dependency graph problems).  Additionally I optimistically "fix"
semanticdb-scalac-core's cross version when consuming Scala nightlies...
…orter-Reporter

Revert "Restore Global.reporter()Reporter"
…ings

[nomerge] Emit warnings in the REPL
Now that `Typer.stabilize` ends up checking for `@uncheckedStable`
annotations to support defs's as stable paths, new opportunities
arise for cyclic errors.

This PR reduces the likelihood of cycles by typechecking the only core of
an annotation (_not_ the full application to the annotation arguments)
to determine its type symbol.

pos/unchecked-stable-cyclic-error.scala test case started to fail
since scala#8338 with:

```
|-- object Test BYVALmode-EXPRmode (site: package <empty>)
|    |-- super APPSELmode-EXPRmode-POLYmode-QUALmode (silent: <init> in Test)
|    |    |-- this EXPRmode (silent: <init> in Test)
|    |    |    \-> Test.type
|    |    \-> Test.type
|    |-- def foo BYVALmode-EXPRmode (site: object Test)
|    |    |-- attr EXPRmode (site: method foo in Test)
|    |    |    |-- Int TYPEmode (site: method attr in Test)
|    |    |    |    \-> Int
|    |    |    |-- new anno APPSELmode-BYVALmode-EXPRmode-FUNmode-POLYmode (site: object Test)
|    |    |    |    |-- new anno APPSELmode-EXPRmode-POLYmode-QUALmode (site: object Test)
|    |    |    |    |    |-- anno FUNmode-TYPEmode (site: object Test)
|    |    |    |    |    |    \-> anno
|    |    |    |    |    \-> anno
|    |    |    |    \-> (a: Any): anno
|    |    |    |-- (a: Any): anno : pt=anno EXPRmode (site: value <local Test> in Test)
|    |    |    |    |-- foo : pt=Any BYVALmode-EXPRmode (site: value <local Test> in Test)
|    |    |    |    |    caught scala.reflect.internal.Symbols$CyclicReference: illegal cyclic reference involving method foo: while typing foo
/Users/jz/code/scala/sandbox/test.scala:7: error: recursive method foo needs result type
  @anno(foo) def attr: Int = foo
        ^
|    |    |    |    \-> anno
```

Another variant, pos/annotation-cycle.scala, fails only on 2.12.x
(after the backport of scala#8338). Backporting this fix makes that test
start passing on 2.12.x.

Backports scala#9302
…ation-info

[backport] Make annotation typechecking lazier
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants