scala3 Track type variable dependencies to guide instantiation decisions

We now keep track of reverse type variable dependencies in constraints. E.g. if a constraint contains a clause like

A >: List[B]

We associate with B info that A depends co-variantly on it. Or, if

A <: B => C

we associate with B that A depends co-variantly on it and with C that A depends contra-variantly on it. Here, co-variant means that the allowable range of A narrows if the referred-to variable B grows, and contra-variant means that the allowable range of A narrows if the referred-to variable C shrinks. If there's an invariant reference such as

A <: Array[B]

Then A depends both co- and contra-variantly on B.

These dependencies are then used to guide type variable instantiation. If an eligible type variable does not appear in the type of a typed expression, we interpolate it to one of its bounds. Previously this was done in an ad-hoc manner where we minimized the type variable if it had a lower bound and maximized it otherwise. We now take reverse dependencies into account. If maximizing a type variable would narrow the remaining constraint we minimize, and if minimizing a type variable would narrow the remaining constraint we maximize. Only if the type variable is not referred to from the remaining constraint we resort to the old heuristic based on the lower bound.

Fixes #15864

Todo: This could be generalized in several directions:

We could base the dependency tracking on type param refs instead of type variables. That could make the replace operation in a constraint more efficient.
We could base more interpolation decisions on dependencies. E.g. we could interpolate a type variable only if both the type of an expression and the enclosing constraint agree in which direction this should be done.

Sep 15 '22 09:09 odersky

test performance please

Sep 15 '22 19:09 odersky

@mbovel @anatoliykmetyuk Benchmark bot seems to be down?

Sep 16 '22 07:09 odersky

test performance please

Sep 17 '22 10:09 mbovel

performance test scheduled: 355 job(s) in queue, 1 running.

Sep 17 '22 11:09 dottybot

performance test scheduled: 355 job(s) in queue, 1 running.

Sep 17 '22 11:09 dottybot

performance test scheduled: 355 job(s) in queue, 1 running.

Sep 17 '22 11:09 dottybot

performance test scheduled: 355 job(s) in queue, 1 running.

Sep 17 '22 11:09 dottybot

performance test scheduled: 355 job(s) in queue, 1 running.

Sep 17 '22 11:09 dottybot

Performance test finished successfully:

Visit https://dotty-bench.epfl.ch/16042/ to see the changes.

Benchmarks is based on merging with main (afc6ce4d21)

Sep 17 '22 13:09 dottybot

Some info on the parboiled2 test. It seems to be a hygiene violation caused somewhere in typedQuotePattern. The test failed when adding a new polytype to the constraint as follows (with -uniqid on, to disambiguate)

error while adding [T#1874900402]#1874900402
  (m#569565916: Map[String#6487, T#1874900402])
    (implicit h#1341031137: 
      org#15.parboiled2#2768.support#2770.HListable#2786[T#1874900402]
    ): org#15.parboiled2#2768.RuleN#2986[h#1341031137.Out#15632]/[T#1874900402] to #66778 with uninstantiated variables: T#1986710687, (param)1#489820775, 
  (param)2#1856085236
 constrained types: 
  [T#1986710687]#1986710687
    (m#620022507: Map[String#6487, T#1986710687], ignoreCase#620022507: 
      Boolean#88
    )
      (implicit h#1277453506: 
        org#15.parboiled2#2768.support#2770.HListable#2786[T#1986710687]
      ): org#15.parboiled2#2768.RuleN#2986[h#1277453506.Out#15632]
, 
  [(param)1#489820775 <: 
    org#15.parboiled2#2768.support#2770.HListable#2786[T#1986710687]
   & Singleton#1670]#489820775: h#1277453506.type
, 
  [(param)2#1856085236 <: 
    org#15.parboiled2#2768.support#2770.HListable#2786[T#1874900402]
   & Singleton#1670]#1856085236: h#1341031137.type
 bounds: 
     T#1986710687
     (param)1#489820775
     <: org#15.parboiled2#2768.support#2770.HListable#2786[T#1986710687] & 
      Singleton#1670
     (param)2#1856085236
     <: org#15.parboiled2#2768.support#2770.HListable#2786[T#1874900402] & 
      Singleton#1670
 ordering: 
 co-deps:
     T#1986710687 --> (param)1#489820775
 contra-deps:
     T#1986710687 --> (param)1#489820775

T#1874900402 gets added as bound parameter to the constraint, but it is already referenced in the constraint. We then get:

java.lang.AssertionError: assertion failed: missing contra backwards reference T#1874900402 -> (param)2#1856085236 in #66779 with uninstantiated variables: T#1986710687, (param)1#489820775, 
  (param)2#1856085236
, T#1874900402
 constrained types: 
  [T#1986710687]#1986710687
    (m#620022507: Map[String#6487, T#1986710687], ignoreCase#620022507: 
      Boolean#88
    )
      (implicit h#1277453506: 
        org#15.parboiled2#2768.support#2770.HListable#2786[T#1986710687]
      ): org#15.parboiled2#2768.RuleN#2986[h#1277453506.Out#15632]
, 
  [(param)1#489820775 <: 
    org#15.parboiled2#2768.support#2770.HListable#2786[T#1986710687]
   & Singleton#1670]#489820775: h#1277453506.type
, 
  [(param)2#1856085236 <: 
    org#15.parboiled2#2768.support#2770.HListable#2786[T#1874900402]
   & Singleton#1670]#1856085236: h#1341031137.type
, 
  [T#1874900402]#1874900402
    (m#569565916: Map[String#6487, T#1874900402])
      (implicit h#1341031137: 
        org#15.parboiled2#2768.support#2770.HListable#2786[T#1874900402]
      ): org#15.parboiled2#2768.RuleN#2986[h#1341031137.Out#15632]
 bounds: 
     T#1986710687
     (param)1#489820775
     <: org#15.parboiled2#2768.support#2770.HListable#2786[T#1986710687] & 
      Singleton#1670
     (param)2#1856085236
     <: org#15.parboiled2#2768.support#2770.HListable#2786[T#1874900402] & 
      Singleton#1670
     T#1874900402
 ordering: 
 co-deps:
     T#1986710687 --> (param)1#489820775
 contra-deps:
     T#1986710687 --> (param)1#489820775
 while typechecking /Users/odersky/workspace/dotty/community-build/community-projects/parboiled2/parboiled-core/src/main/scala-3/org/parboiled2/support/OpTreeContext.scala

Sep 23 '22 08:09 odersky

The perspective failure is also a hygiene violation (both added parameters are already referred to in the constraint). This time it's called from TypeComparer#matchCase.

error while adding [h#1295220417, t#1295220417 <: Tuple#52]#1295220417 =>> 
  scala#23.runtime#430.MatchCase#5264[h#1295220417 *: t#1295220417, h#1295220417
     
  | 
    scala#23.Tuple#53.Fold#23132[t#1295220417, Nothing#1128, 
      [x#-1965483054, y#-1965483054]#-1965483054 =>> x#-1965483054 | 
        y#-1965483054
    ]
  ]/[] to #23870 with uninstantiated variables: (param)1#673691532, (param)2#392956106, 
  (param)3#666882910
, B#1367453971, X0#1173905467
 constrained types: 
  [(param)1#673691532 <: 
    perspective#25.derivation#2791.HKDProductGeneric#11888[
      perspective#25.examples#2907.Cat#2932
    ]
   & Singleton#1676]#673691532: gen#1729214832.type
, 
  [(param)2#392956106 <: 
    perspective#25.derivation#2791.HKDProductGeneric#11888[
      perspective#25.examples#2907.Cat#2932
    ]
   & Singleton#1676]#392956106: gen#1729214832.type
, 
  [(param)3#666882910 <: 
    deriving#436.Mirror#11941.ProductOf#23108[
      perspective#25.examples#2907.Cat#2932
    ]{
      MirroredElemTypes = m$proxy1#40129.MirroredElemTypes; 
        MirroredLabel = m$proxy1#40129.MirroredLabel#23214
    }
   & Singleton#1676]#666882910: m#223342788.type
, 
  [B#1367453971 >: 
    m$proxy1#40129.MirroredElemLabels#23215 match {
      case EmptyTuple#12278 => Nothing#1128
      case h#1134074693 *: t#1134074693 => h#1134074693 | 
        scala#23.Tuple#53.Fold#23132[t#1134074693, Nothing#1128, 
          [x#-1965483054, y#-1965483054]#-1965483054 =>> x#-1965483054 | 
            y#-1965483054
        ]
    }
  ]#1367453971: Set[B#1367453971]
, [X0#1173905467]#1173905467: X0#1173905467
 bounds: 
     (param)1#673691532
     <: 
      perspective#25.derivation#2791.HKDProductGeneric#11888[
        perspective#25.examples#2907.Cat#2932
      ]
     & Singleton#1676
     (param)2#392956106
     <: 
      perspective#25.derivation#2791.HKDProductGeneric#11888[
        perspective#25.examples#2907.Cat#2932
      ]
     & Singleton#1676
     (param)3#666882910
     <: 
      deriving#436.Mirror#11941.ProductOf#23108[
        perspective#25.examples#2907.Cat#2932
      ]{
        MirroredElemTypes = m$proxy1#40129.MirroredElemTypes; 
          MirroredLabel = m$proxy1#40129.MirroredLabel#23214
      }
     & Singleton#1676
     B#1367453971
     >: 
      m$proxy1#40129.MirroredElemLabels#23215 match {
        case EmptyTuple#12278 => Nothing#1128
        case h#1295220417 *: t#1295220417 => h#1295220417 | 
          scala#23.Tuple#53.Fold#23132[t#1295220417, Nothing#1128, 
            [x#-1965483054, y#-1965483054]#-1965483054 =>> x#-1965483054 | 
              y#-1965483054
          ]
      }
     X0#1173905467
 ordering: 
 co-deps:
 contra-deps:

Sep 23 '22 08:09 odersky

So, the question to decide is this:

We have evidence that reverse dependencies work except that there can be rare hygiene violations (2 cases in CB, none in test suite).
replace was not affected by these violations on the tests or the CB. It works either based on dependencies or doing a brute force search of all parameters (which was the state before the last commit).
It's debatable what replace should do when faced with a hygiene problem. I.e say we have the constraint
```
 A >: C[B]
```
then we add the binder [B] yielding
```
A >: C[B]
B
```
and then we replace the bound B by B1. Should the pre-existing C[B] be replaced as well? Previously the answer was yes, with the replace optimization the answer is no.

So in the end the question is: Do we prefer to keep the behavior stable wrt replace or do we choose to optimize, with potentially big gains for large constraints?

Sep 23 '22 19:09 odersky

test performance please

Sep 25 '22 07:09 odersky

performance test scheduled: 355 job(s) in queue, 1 running.

Sep 25 '22 07:09 dottybot

Performance test finished successfully:

Visit https://dotty-bench.epfl.ch/16042/ to see the changes.

Benchmarks is based on merging with main (b1b1dfdac8)

Sep 25 '22 10:09 dottybot

test performance please

Sep 25 '22 11:09 odersky

performance test scheduled: 355 job(s) in queue, 1 running.

Sep 25 '22 11:09 dottybot

Performance test finished successfully:

Visit https://dotty-bench.epfl.ch/16042/ to see the changes.

Benchmarks is based on merging with main (b1b1dfdac8)

Sep 25 '22 13:09 dottybot

test performance please

Sep 26 '22 14:09 mbovel

performance test scheduled: 1 job(s) in queue, 2 running.

Sep 26 '22 14:09 dottybot

Performance test finished successfully:

Visit https://dotty-bench.epfl.ch/16042/ to see the changes.

Benchmarks is based on merging with main (9d574ce1fc)

Sep 26 '22 15:09 dottybot

test performance please

Sep 28 '22 13:09 mbovel

test performance please

Sep 28 '22 14:09 mbovel

performance test scheduled: 2 job(s) in queue, 1 running.

Sep 28 '22 14:09 dottybot

performance test scheduled: 2 job(s) in queue, 1 running.

Sep 28 '22 15:09 dottybot

Performance test finished successfully:

Visit https://dotty-bench.epfl.ch/16042/ to see the changes.

Benchmarks is based on merging with main (731522a283)

Sep 28 '22 16:09 dottybot

Performance test finished successfully:

Visit https://dotty-bench.epfl.ch/16042/ to see the changes.

Benchmarks is based on merging with main (731522a283)

Sep 28 '22 17:09 dottybot

@smarter ping for review

Sep 30 '22 18:09 odersky

@smarter The two occurrences were replaced following your suggestions.

Oct 31 '22 09:10 odersky

scala3 scala3 copied to clipboard

Track type variable dependencies to guide instantiation decisions

scala3
scala3 copied to clipboard