Skip to content

RedBlackTree backport review#85

Closed
retronym wants to merge 63 commits into2.12.xfrom
review/8749
Closed

RedBlackTree backport review#85
retronym wants to merge 63 commits into2.12.xfrom
review/8749

Conversation

@retronym
Copy link
Owner

Review of: scala#8749

These optimizations still need to pulled up into type-cases of the inherited methods:

[error]  * method --(scala.collection.GenTraversableOnce)scala.collection.immutable.TreeMap in class scala.collection.immutable.TreeMap does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeMap.--")
[error]  * method keySet()scala.collection.immutable.TreeSet in class scala.collection.immutable.TreeMap does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeMap.keySet")
[error]  * method filter(scala.Function1)scala.collection.immutable.TreeMap in class scala.collection.immutable.TreeMap does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeMap.filter")
[error]  * the type hierarchy of class scala.collection.immutable.RedBlackTree#KeysIterator is different in other version. Missing types {scala.collection.AbstractIterator}
[error]    filter with: ProblemFilters.exclude[MissingTypesProblem]("scala.collection.immutable.RedBlackTree$KeysIterator")
[error]  * method tree()scala.collection.immutable.RedBlackTree#Tree in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeSet.tree")
[error]  * method ++(scala.collection.GenTraversableOnce)scala.collection.immutable.TreeSet in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeSet.++")
[error]  * method --(scala.collection.GenTraversableOnce)scala.collection.immutable.TreeSet in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeSet.--")
[error]  * method intersect(scala.collection.GenSet)scala.collection.immutable.TreeSet in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeSet.intersect")
[error]  * method diff(scala.collection.GenSet)scala.collection.immutable.TreeSet in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeSet.diff")
[error]  * method filter(scala.Function1)scala.collection.immutable.TreeSet in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("scala.collection.immutable.TreeSet.filter")

mkeskells and others added 30 commits February 2, 2020 21:01
I removed `generatePropertiesFileSettings` from commonSettings
leaving projects that really need to use it to directly add it
to the settings. This was already being done (redundatly in some
cases) in `library`, `reflect`, `compiler`, `partestExtras`
and `partestJavaAgent`.

Before this PR (but after the SBT upgrade on 2.12.x branch):

```
➜  sbt 'show compiler/Compile/packageBin/mappings' | egrep 'repl-jline\.properties'
[info] * (/Users/jz/code/scala-2.12.x-reference/build/quick/classes/repl-jline/repl-jline.properties,repl-jline.properties)
[info] * (/Users/jz/code/scala-2.12.x-reference/build/quick/classes/repl-jline-embedded/repl-jline.properties,repl-jline.properties)

➜  sbt scala
[info] Loading global plugins from /Users/jz/.sbt/1.0/plugins
[info] Loading settings for project scala-2-12-x-reference-build-build from plugins.sbt ...
[info] Loading project definition from /Users/jz/code/scala-2.12.x-reference/project/project
[info] Loading settings for project scala-2-12-x-reference-build from plugins.sbt,build.sbt ...
[info] Loading project definition from /Users/jz/code/scala-2.12.x-reference/project
[info] Loading settings for project root from build.sbt ...
[info] Resolving key references (18230 settings) ...
[error] Could not determine commit date + SHA: org.eclipse.jgit.errors.MissingObjectException: Missing unknown b8c33ad
[info] *** Welcome to the sbt build definition for Scala! ***
[info] Check README.md for more information.
[error] java.util.zip.ZipException: duplicate entry: repl-jline.properties
```

After this PR:

```
fg: no current job
➜  sbt 'show compiler/Compile/packageBin/mappings' | egrep 'repl-jline\.properties'
[info] * (/Users/jz/code/scala-2.12.x-reference/build/quick/classes/repl-jline-embedded/repl-jline.properties,repl-jline.properties)

➜  sbt scala
[info] Loading global plugins from /Users/jz/.sbt/1.0/plugins
[info] Loading settings for project scala-2-12-x-reference-build-build from plugins.sbt ...
[info] Loading project definition from /Users/jz/code/scala-2.12.x-reference/project/project
[info] Loading settings for project scala-2-12-x-reference-build from plugins.sbt,build.sbt ...
[info] Loading project definition from /Users/jz/code/scala-2.12.x-reference/project
[info] Loading settings for project root from build.sbt ...
[info] Resolving key references (18194 settings) ...
[info] *** Welcome to the sbt build definition for Scala! ***
[info] Check README.md for more information.
[info] running (fork) scala.tools.nsc.MainGenericRunner -usejavacp
Welcome to Scala 2.12.11-20200203-035143-5bdfd31 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_221).
Type in expressions for evaluation. Or try :help.
```

Prior to the SBT upgrade, we also had the duplicate mapping:

```
sbt 'show compiler/compile:packageBin::mappings' | egrep 'repl-jline\.properties'
[info] * (/Users/jz/code/scala-2.12.x-reference/build/quick/classes/repl-jline/repl-jline.properties,repl-jline.properties)
[info] * (/Users/jz/code/scala-2.12.x-reference/build/quick/classes/repl-jline-embedded/repl-jline.properties,repl-jline.properties)
```
Avoid duplicate repl-jline.properties entries in compiler/packageBin
The List.intersect method creates a new list of elements,
which in this case was discarded (only the length matters).
Since typeParams is to be a list without repetitions, for
(A intersect B) to be the same length as B, it needs be that
all elements of B are contained in A.
create less objects for zipWithIndex
EmptySet and SetBuilder adjusted to take advantage of ++ optimisation for simple and common cases

eliminate unneeded allocations for HashSets where the result is already built for -
   subSet ++ superSet
   subSet union superSet
   superSet union subSet
   superSet ++ subSet

make a fast path when there is structural sharing in the HashSet
for union, guarantee internal operations will only return a new HashSet if one of the existing HashSet parameters or internal values cant be used

use System.arraycopy rather than Array.copy as it avoid JVM nulling the array

add missing `eq` fast path to intersect0 and diff0

minor improvements to + to reduce allocations

reduce calls to HashSet.size which can be a bottleneck

reduce allocations in ListSet ++, + and -
no allocations in ++ or + if the data is contained in the original sets

HashSetCollision1 stores its length so as to avoid calls to ListSet.size which is O(n)
take advantage of ListSet guarantees on identity for return or + or - where we can
avoid calling ListSet.size where we can avoid it
The keys in the resulting map are the same, so the internal structure
will also be the same, and that can be used to avoid allocating tuples
and going through `MapBuilder` and other such convolutions.
I thought som-snytt had recently gone on some sort of warning-cleanup
mission, but nowadays I can't compile 2.12.x without seeing scala tell
me off for these. Well, now I can.
Unlike .scala files, .java files are named and typed lazily: they will
only be analyzed when necessary to typecheck a Scala source. However,
under -Ypickle-java, pickler runs over them after typechecking, and can
force infos that otherwise wouldn't be forced. If typing the Java source
fails, the tree can contain erroneous types and symbols which will then
crash pickler as it attempts to write out the pickle.

This patch makes -Ypickle-java eagerly typecheck Java sources during
typer, so any errors will be emitted alongside Scala typer errors.

The enclosed test case previously crashed the compiler with a MatchError
on ErrorType.
Thoroughly typecheck Java sources for pickling
[nomerge] Update to sbt 1.3.8, remove workarounds
[nomerge] HashMap#transform reuses structure
fix our Windows Jenkins job (sbt 1.3 upgrade broke it)
…ores some imports

Co-authored-by: Dale Wijnand <dale.wijnand@gmail.com>
Always generate a `val INSTANCE` field, whether it's for class-based or
object-based, so that the access code branches needn't branch on
isClassBased.

This greatly simplifies the next commit, for handling value classes.
... by making any code snippet that defines (or seems to define) a value
class use the original "object-based" wrappers instead.
Co-authored-by: Dale Wijnand <dale.wijnand@gmail.com>
This avoids problems like

    private value read escapes its defining scope as part of type u.Type

when running `test/files/run/class-symbol-contravariant.scala` (and a
few others) with -Yrepl-class-based.

Also add a test specific for type aliases, extracted from
`test/files/jvm/interpreter.scala`, to run in class-based mode.
The Spark REPL uses -Yrepl-class-based and the change around
ImportHandler in interpreter/Imports (and that introduced the custom
wrapperCleanup phase for the REPL) requires -Yrepl-use-magic-imports be
set in order for the Spark REPL to continue to work correctly.  Rather
than affect all existing Spark releases that choose to upgrade Scala, we
preserve the functioning of the Spark REPL by enabling "magic imports"
when using the class-based wrappers.
... and thus -Yrepl-use-magic-imports too.
The intent is for these to be true, but we'll do that for 2.13.x,
not 2.12.x.
Warn use of a deprecated class' static method
The custom phase that does this needs to descend deeper than
the first `Template`.

It now works bottom up (from the innermost `$iw`) and runs the
unused analysis at each level, feeding the possibly simpilfied
trees into the analysis of the enclosing level.

I also needed to add a special case for the `lineXY$read`
variable names which should be considered private for the
purpose of this analysis.
dwijnand and others added 18 commits February 19, 2020 12:03
This should help ensure the order is as deterministic as possible.
Avoid IntRef and other overheads in `ScalaRuntime.{toArray, toObjectArray}`
[nomerge] optimise the addition of immutable HashMap
dont create a TreeMap if the underlying tree is unchanged
Dont create a new TreeSet if there is no change to the underlying tree
…sable

remove some refs in TraversableOnce
@mkeskells
Copy link

mkeskells commented Feb 29, 2020

[error] * method tree()scala.collection.immutable.RedBlackTree#Tree in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error] filter with: ProblemFilters.excludeDirectMissingMethodProblem

before it was
final class TreeMap[A, +B] private (_tree: RB.Tree[A, B])(... private[immutable] val tree: RB.Tree[A, B] = _tree

now it is
final class TreeSet[A] private[immutable] (private[immutable] val tree: RB.Tree[A, Any])(

I don't see what the issues is . Please confirm

@mkeskells
Copy link

mkeskells commented Feb 29, 2020

method filter(scala.Function1)scala.collection.immutable.TreeMap in class scala.collection.immutable.TreeMap does not have a correspondent in other version

method filter(scala.Function1)scala.collection.immutable.TreeSet in class scala.collection.immutable.TreeSet does not have a correspondent in other version
[error]  

It looks like 2.13 is overriding filter, when it should be filterImpl
I will adjust, but I thing this should be applied to 2.13 as well

in commits 634af15 and 5581dff

@dwijnand
Copy link

dwijnand commented Mar 1, 2020

does not have a correspondent in other version
[error] filter with: ProblemFilters.excludeDirectMissingMethodProblem

That's a bug. It's meant to be an IncompatibleResultTypeProblem. That was fixed in https://github.com/lightbend/mima/releases/tag/0.6.4 but 2.12.x is lagging.

@retronym retronym force-pushed the review/8749 branch 2 times, most recently from 5b8bb6b to 4a51c40 Compare March 2, 2020 00:37
  - Backports the new internal `RedBlackTree`.
  - In 2.12.x `Tree` must still extend `Serializable` as we don't
    use proxy based serialization for `TreeMap` / `TreeSet`.
  - Take advantage of the new implementation when the operand to
    `++`, `filter`, etc is the same collection type with the same
    `Ordering`. Many of these changes require us to modify the
    inherited implementation to add a type-case to be binary
    compatibile.
@szeiger
Copy link

szeiger commented Mar 2, 2020

before it was
final class TreeMap[A, +B] private (_tree: RB.Tree[A, B])(... private[immutable] val tree: RB.Tree[A, B] = _tree

I don't know where you're looking but I see this in 2.12.x:

final class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Ordering[A])

@szeiger
Copy link

szeiger commented Mar 2, 2020

It looks like 2.13 is overriding filter, when it should be filterImpl
I will adjust, but I thing this should be applied to 2.13 as well

I see a few lone filter overrides in 2.13. It should be either filterImpl, or filter plus filterNot.

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.

8 participants