How does the scala compiler locate the positions for variance annotation

Question

I am trying to understand how the compiler checks whether the position for a type parameter is covariant or contravariant.

As far as I know, if the type parameter is annotated with the +, which is the covariant annotation, then any method cannot have a input parameter typed with that class/trait's type parameter.

For example, bar cannot have a parameter of type T.

class Foo[+T] {
  def bar(param: T): Unit = 
    println("Hello foo bar")
}

Because the position for the parameter of bar() is considered to be negative, which means any type parameter in that position is in a contravariant position.

I am curious how the Scala compiler can find if every location in the class/trait is positive, negative, or neutral. It seems that there exist some rules like flipping its position in some condition but couldn't understand it clearly.

Also, if possible, I would like to know how these rules are defined. For example, it seems that parameters for methods defined in a class that has covariant annotation, like bar() method in Foo class, should have contravariant class type. Why?

Answer 1

I am curious how the Scala compiler can find if every location in the class/trait is positive, negative, or neutral. It seems that there exist some rules like flipping its position in some condition but couldn't understand it clearly.

The Scala compiler has a phase called parser (like most compilers), which goes over the text and parses out tokens. One of these tokens is called variance. If we dive into the detail, there's a method called Parsers.typeParamClauseOpt which is responsible for parsing out the type parameter clause. The part relevant to your question is this:

def typeParam(ms: Modifiers): TypeDef = {
  var mods = ms | Flags.PARAM
  val start = in.offset
  if (owner.isTypeName && isIdent) {
    if (in.name == raw.PLUS) {
      in.nextToken()
      mods |= Flags.COVARIANT
    } else if (in.name == raw.MINUS) {
      in.nextToken()
      mods |= Flags.CONTRAVARIANT
    }
  }

The parser looks for the + and - signs in the type parameter signature, and creates a class called TypeDef which describes the type and states that it is covariant, contravariant or invariant.

Also, if possible, I would like to know how these rules are defined.

Variance rules are universal, and they stem from a branch of mathematics called Category Theory. More specifically, they're derived from Covariant and Contravariant Functors and the composition between the two. If you want to learn more on these rules, that would be the path I'd take.

Additionally, there is a class called Variance in the Scala compiler which looks like a helper class in regards to variance rules, if you want to take a deeper look.

Answer 2

To verify the correctness of variance annotation, the compiler classifies all positions in a class or trait body as positive (+), negative (-) or neutral. A "position" is any location in the class or trait (but from now on I'll just write "class") body where a type parameter may be used.

The compiler checks each use of each of the class's type parameters:

• +T type parameters (covariant/flexible) may only be used in positive positions.
• -T type parameters (contravariant) may only be used in negative positions.
• T type parameters (invariant/rigid) may be used in any position, and is therefore, the only kind of type parameter that can be used in neutral positions.

To classify the positions, the compiler starts from the given class declaration of a type parameter and moves inward through deeper nesting levels. Positions at the top level of the declaring class are classified as positive. By default, positions at deeper nesting levels are classified the same as that at enclosing levels, but there are three exceptions where the classification changes:

1. Method value parameter positions are classified to the flipped classification relative to positions outside the method, where:

   • the flip of a positive classification is negative
   • the flip of a negative classification is positive
   • the flip of a neutral classification remains neutral.

2. Besides method value parameter positions, the current classification is also flipped at the type parameters of methods.

3. A classification is sometimes flipped at the type argument position of a type, such as the Arg in C[Arg], depending on the variance of the corresponding type parameter. If C's type parameter is:

   • +T then the classification stays the same.
   • -T then the current classification is flipped
   • T then the current classification is changed to neutral

To understand better, here's a contrived example, where all positions are annotated with their classifications, given by the compiler:

abstract class Cat[-T, +U] {
    def meow[W-](volume: T-, listener: Cat[U+, T-]-): Cat[Cat[U+, T-]-, U+]+
}

• The type parameter W is in a negative (contravariant) position because of rule number 2 stated above. (So it is flipped relative to positions outside the method - which are stated to be positive by default, so the compiler flips it and that is why it becomes negative.).
• The value parameter volume is in a negative position (contravariant) because of rule number 1. (So it is flipped in the same manner as W)
• The value parameter listener, is in a negative position for the same reason as volume. Looking at the positions of its type arguments U and T inside the type Cat, they are flipped because Cat is in a negative position, and according to rule number 3 it must be flipped.
• The result type of the method is positive because it's considered outside the method. Looking inside the result type of meow: the position of the first Cat[U, T] is negative because Cat's first type parameter, T is annotated with a -; while the second type argument, U is positive since Cat's second type parameter, U is annotated with a +. The two positions remain unchanged (are not flipped) because the flipping rule does not apply here (rule number 3), since Cat is in a positive position. But the types U and T inside the first argument of Cat are flipped because the flipping rule does apply here - that Cat is in a negative position.

As you can see it's quite hard to keep track of variance positions. That's why is a welcome relief that the Scala compiler does this job for you.

Once the classification is computed, the compiler checks that each type parameter is only used in positions that are classified appropriately. In this case, T is only used in negative positions, while U is only used in positive positions. So class Cat is type correct.

The rules and example are taken directly from the Programming in Scala book by M. Odersky, B. Venners and L. Spoon.

This also answers your second question: based on these rules we can infer that method value arguments will always be in contravariant positions, while method result types will always be in covariant positions. This is why you can't have a covariant type in a method value parameter position in your example.