Skip to content

Failing tests for type comparisons.#6080

Closed
TomasMikula wants to merge 2 commits intoscala:2.12.xfrom
TomasMikula:type-comparison-tests
Closed

Failing tests for type comparisons.#6080
TomasMikula wants to merge 2 commits intoscala:2.12.xfrom
TomasMikula:type-comparison-tests

Conversation

@TomasMikula
Copy link
Contributor

These tests show that for types Foo[A], Bar[A, B] and type variables F[_], G[_, _]:

  1. It is possible to unify the type variable ?G with [A]Bar[A, A], which is incorrect because of the different number of type parameters (2 vs 1).
  2. Both Foo <:< ?F and ?F <:< [A]Bar[Int, A] simultaneously, which by transitivity means Foo <:< [A]Bar[Int, A], which is not true.

I don't know if these are reproducible through compilation, but they hinder my progress on correctly implementing and testing #6069.

For starters, is there agreement that these are bugs that need to be addressed?

@retronym
Copy link
Member

Thanks for surveying the foundations before building another storey.

The inconsistency in arity checks in TypeVar for <:< vs =:= certainly looks suspicious.

Let's see how we arrive at TypeVar.registerTypeEquality while compiling actual sources.


During typechecking of this pattern:

private[scala] def unlifted[A, B](f: _root_.scala.Function1[A, Option[B]]): PartialFunction[A,B] = f match {
  case (lf @ (_: Lifted[A, B])) => lf.pf
  case (ff @ _) => new Unlifted(ff)
}

We ask: is the scrutinee type of A => Option[B] inhabited by values that might conform to scala.PartialFunction.Lifted[A,B] (via CheckabilityChecker and propagateKnownTypes). I believe that by construction the arities should align here, but it could stand some closer inspection.


A similar check is made in populated

        else {
          tvars = tpparams map freshVar
          tp    = pattp.instantiateTypeParams(tpparams, tvars)

          debuglog("free type params (2) = " + ptparams)

          val ptvars = ptparams map freshVar
          val pt1    = pt.instantiateTypeParams(ptparams, ptvars)

          // See ticket #2486 for an example of code which would incorrectly
          // fail if we didn't allow for pattpMatchesPt.
          if (isPopulated(tp, pt1) && isInstantiatable(tvars ++ ptvars) || pattpMatchesPt)
             ptvars foreach instantiateTypeVar
          else {
            PatternTypeIncompatibleWithPtError1(tree0, pattp, pt)
            return ErrorType
          }
....
  /** Is intersection of given types populated? That is,
   *  for all types tp1, tp2 in intersection
   *    for all common base classes bc of tp1 and tp2
   *      let bt1, bt2 be the base types of tp1, tp2 relative to class bc
   *      Then:
   *        bt1 and bt2 have the same prefix, and
   *        any corresponding non-variant type arguments of bt1 and bt2 are the same
   */
  def isPopulated(tp1: Type, tp2: Type): Boolean = {
    def isConsistent(tp1: Type, tp2: Type): Boolean = (tp1.dealias, tp2.dealias) match {
      case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) =>
        assert(sym1 == sym2, (sym1, sym2))
        (    pre1 =:= pre2
          && forall3(args1, args2, sym1.typeParams) { (arg1, arg2, tparam) =>
               // if left-hand argument is a typevar, make it compatible with variance
               // this is for more precise pattern matching
               // todo: work this in the spec of this method
               // also: think what happens if there are embedded typevars?
               if (tparam.variance.isInvariant)
                 arg1 =:= arg2
               else !arg1.isInstanceOf[TypeVar] || {
                 if (tparam.variance.isContravariant) arg1 <:< arg2
                 else arg2 <:< arg1
               }
             }
        )
      case (et: ExistentialType, _) =>
        et.withTypeVars(isConsistent(_, tp2))
      case (_, et: ExistentialType) =>
        et.withTypeVars(isConsistent(tp1, _))
      case (_, _) =>
        throw new MatchError((tp1, tp2))
    }

    def check(tp1: Type, tp2: Type) = (
      if (tp1.typeSymbol.isClass && tp1.typeSymbol.hasFlag(FINAL))
        tp1 <:< tp2 || isNumericValueClass(tp1.typeSymbol) && isNumericValueClass(tp2.typeSymbol)
      else tp1.baseClasses forall (bc =>
        tp2.baseTypeIndex(bc) < 0 || isConsistent(tp1.baseType(bc), tp2.baseType(bc)))
    )

    check(tp1, tp2) && check(tp2, tp1)
  }

Again, it seems likely that the arities will line up by construction.


As an experiment, add an assertion into registerTypeEquality that the arities to line up, and then we can see if we can trip it by compiling some code. We can run the community build on that commit.

@retronym
Copy link
Member

As to question 2, TypeVars are only supposed to appear on one side of type comparisons as they accumulate constraints. All (or some) bets are off if they appear on the LHS and RHS.

However (IIRC) it can happen with the way that typechecking of existential types creates type variables.

@TomasMikula
Copy link
Contributor Author

Added the assertion to registerTypeEquality in the first commit. It is not triggered by tests.

I brought this up because in #6069, you asked for tests to "explore whether the change preserves transitivity of subtyping and consistency with =:=". But these tests demonstrate that when it comes to TypeVars, subtyping is neither transitive nor consistent with =:= to start with.

@adriaanm adriaanm modified the milestones: 2.12.4, WIP Sep 27, 2017
@joroKr21
Copy link
Member

Type vars also cause inconsistency between =:= and <:< wrt refined types (causing scala/bug#10506). E.g. we have:

type Struct = { def i: Int }
// these are true
(?A with Serializable) =:= (Struct with Serializable)
(Struct with Serializable) <:< (?A with Serializable)
// but this is false
(?A with Serializable) <:< (Struct with Serializable)

@milessabin
Copy link
Contributor

You might want to take a look at my WIP on the solver ... it addresses some ill-kinding issues.

@SethTisue
Copy link
Member

closing for inactivity. we can reopen if activity resumes

@SethTisue SethTisue closed this Feb 24, 2018
@SethTisue SethTisue removed this from the WIP milestone Mar 6, 2018
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.

7 participants