Skip to content

PatternTypeInference

Jump to bottom Edit New page
scottwis edited this page Mar 3, 2012 · 111 revisions

Pattern Type Inference

Notes

This document defines the rules used by the compiler for validating patterns used in switch statements, and for inferring types for pattern variables. It is intended to serve as a formal specification, and is mainly of interest to compiler hackers. For a user-level overview of the language, please see LanguageIntroduction.

Pattern Context

Patterns are always interpreted within the confines of a pattern context. A pattern context is a type used to constrain the set of types that can be inferred for a given variable. A pattern type is said to be incompatible with a given pattern if there is no value that can both:

  1. Exist in a storage location with a static type equal to the context type
  2. Sucessfully match the pattern.

If the compiler can determine that a pattern is incompatible with the associated pattern context it will report a compiler error.

Default Context

The default pattern context is always the static type of the containing switch statement's operand. Given this code:

function Foo<T>(xs :: IEnumerable<T>)
{
    switch (xs) {
        //...
    }
}

The default pattern context for the switch statement would be IEnumerable<T>.

Cons Patterns (x :: xs)

  1. If the pattern context is a type T , such that

    then the pattern context is not compatible with a cons pattern and an error will be reported. This is true when the pattern context is any of the following:

    • A value type not implicitly convertible to a list type. All value types are implicitly sealed.
    • A sealed reference type not implicitly convertible to a list type.
    • A generic parameter constrained to a specific value type or to a sealed reference type that is not implicitly convertible to a list type.
    • A case class, constructor class, or a generic parameter constrained to such a type.

  2. If the pattern context is a list type [T] then the head pattern should be interpreted using a context of T and the tail pattern should be interpreted using a context of [T].

  3. If the pattern context is implicitly convertible to a type [T] for some type T, then the head pattern should be interpreted using a context of T and the tail pattern should be interpreted using a context of [T]. If the pattern context is implicitly convertible to multiple list types then the most encompassing of such types should be selected. If no unique most encompassing type exists then the pattern context is incompatible with a cons-pattern and an error will be reported.

  4. If the pattern context is one of:

    • IEnumerable<T> for some type T.
    • A generic parameter constrained to only IEnumerable<T> (this excludes class and new constraints).
Then the head pattern should be interpreted using a context of `T` and the tail pattern should be 
interpreted using a context of `[T]`.

  1. Otherwise the head pattern should be interpreted using a context of object and the tail pattern should be interpreted using a context of [object].

  2. If pattern inference succeeds and the pattern context is a tuple type then a compile time warning will be reported.

List Patterns ([a, b, c])

The rules for list patterns are similar to cons patterns, except that each sub-pattern is interpreted with a scalar context (with cons patterns the tail is interpreted with a list context).

More formally:

  1. If the pattern context is a type T , such that

    then the pattern context is not compatible with a list pattern and an error will be reported. This is true when the pattern context is any of the following:

    • A value type not implicitly convertible to a list type. All value types are implicitly sealed.
    • A sealed reference type not implicitly convertible to a list type.
    • A generic parameter constrained to a specific value type or to a sealed reference type that is not
      implicitly convertible to a list type.
    • A case class, constructor class, or a generic parameter constrained to such a type.

  2. If the pattern context is a list type [T] then all sub-patterns should be interpreted using a type of T'.

  3. If the pattern context is implicitly convertible to a type [T] for some type T, then all sub- patterns should be interpreted using a context of T. If the pattern context is implicitly convertible to multiple list types then the most encompassing of such types should be selected. If no unique most encompassing type exists then the pattern context is incompatible with a list pattern and an error will be reported.

  4. If the pattern context is one of:

    • IEnumerable<T> for some type T.
    • A generic parameter constrained to only IEnumerable<T> (this excludes class and new constraints).
Then all sub-patterns should be interpreted using a context of `T`.

  1. Otherwise all sub-patterns should be interpreted using a context of object.

  2. If the pattern inference succeeds and the pattern context is a tuple type then a compile-time warning will be reported.

Anonymous Patterns (_)

An anonymous pattern does not introduce any variables, infer any types, nor have any restrictions. It's type inference step always succeeds.

Named Patterns (x)

A named pattern introduces a variable with the given name and sets its static type equal to the current pattern context.

Tuple Patterns (a,b,c)

  1. If the pattern context is a tuple type with an arity that does not match the pattern's arity then the pattern is not compatible with the context and an error will be generated.

  2. If the pattern context is a tuple type with an arity that matches the pattern's arity, then each sub- pattern will be interpreted in the context of the associated tuple element type.

  3. If the pattern context is a type `T' such that

[[incompatible-tuple.gif|width=481px]]

Where _n_ is the arity of the tuple pattern, then the pattern is incompatible with the context and a 
compile-time error will be reported. This is true when the pattern context is any of the following:
  * A value type not implicitly convertible to a tuple with matching arity. All value types are 
  implicitly sealed.
  * A sealed reference type not implicitly convertible to a tuple with matching arity. 
  * A generic parameter constrained to a specific value type or a sealed reference type not 
  implicitly convertible to a tuple with matching arity.
  * A case class, constructor class, or a generic parameter constrained to such a type.

  1. If the pattern context is implicitly convertible to a tuple type with an arity that matches the pattern's arity, then each sub-pattern will be interpreted in the context of the corresponding tuple element-type. If the pattern context is implicitly convertible to multiple such tuple types then the most encompassing tuple type will be selected. If no unique most encompassing type exists then the context is incompatible with the pattern and a compile-time error will be reported.

  2. If pattern inference succeeds and the pattern context is a list type then a compile time warning will be reported.

Typed Patterns (x :: S)

  1. If the pattern context is a type T such that
[[incompatible-type.gif|width=188px]]

where `S` is the type declared in the pattern, then the pattern is incompatible with the context and a 
compile-time error will be reported. This is true when the pattern context is:

* A value type not implicitly convertible to `S`.
* A sealed reference type not implicitly convertible to `S`.
* A case class, none of whose constructor types are implicitly convertible to `S`.
* A virtual or abstract constructor class, none of whose derived constructor classes are implicitly 
convertible to `S` (these types are not sealed, but unlike most unsealed reference types, the set of 
implementing types is closed and always know by the compiler).
* A generic parameter constrained to a type matching any of the above cases.

  1. If the sub-pattern is a null pattern, then a compile-time error will be reported.

  2. Otherwise the sub-pattern is interpreted in the context of the type declared in the pattern.

Object Pattern `( S { F1 = x, F2 = y} )'

  1. If the pattern context is a type T such that
[[incompatible-type.gif|width=188px]]

Where _S_ is the type declared in the object pattern, then the context is incompatible with it and a compile-time error will be reported. This is true when the pattern context is:

  * A sealed reference type not convertible to the specified object type.
  * A value type not convertible to the specified object type.
  * A generic parameter constrained to a sealed reference type or a specific value type that is not
  convertible to the specified object type. 
  * A case class,or a generic parameter constrained to a case class, where neither the case class nor 
  any of it's derived constructor classes are implicitly convertible to the specified type.
  1. Otherwise the value of each Field Pattern is interpreted in the context of the type of the associated member.

Constructor Pattern (S.C (p1, ..., pn))

  1. If the pattern context is a type T such that
[[incompatible-constructor.gif|width=322px]]

Where C is the type corresponding to the provided constructor then the pattern context is incompatible with the constructor parameter and a compile time error will 
be reported. This is true when the pattern context is any of:

* A sealed reference type not convertible to the provided constructor class, nor any of it's base classes.
* A value type not convertible to the provided constructor class, nor any of it's base classes.
* A case class that is not related to the provided constructor class, or a generic parameter constrained to such a type.
* A  generic parameter constrained to a sealed reference type or a specific value type that is not 
convertible to the provided constructor class nor any of it's base classes.

  1. If the number of supplied sub-patterns is not equal to the arity of the given constructor, then the pattern is incompatible with the context and a compile-time error will be reported.

  2. If the pattern specifies generic parameters for the provided constructor, then each sub-pattern of the context is interpreted using the corresponding (substituted) constructor parameter type.

  3. If the pattern context is either a case class or a constructor class, then the compiler will attempt to infer types for the constructor's parameters using any generic type parameters of the pattern context. If that process is unable to infer closed types for each constructor parameter, and a closed type for the constructor, then a compile-time error will be reported. If it succeeds in inferring types for each constructor parameter (and the constructor type), then each sub-pattern will be interpreted using the corresponding constructor parameter type.

  4. If the pattern context is not a case class or a constructor, then an attempt will be made to infer types for the constructor's parameters by doing a bottom-up type inference pass on the provided sub- patterns. Those inferred types will then be used to perform generic-parameter inference in the same manner as at constructor invocation sites. If that process succeeds in inferring closed types for each sub- pattern and for the constructor class, then each sub pattern will be interpreted using the corresponding parameter type. If that process fails then a compile-time error will be reported. See BottomUpPatternInference for more info.

  5. If interpretation of the constructor pattern succeeds and the pattern context is a list type or tuple type then a compile-time warning will be reported.

Integer Literal Patterns (42)

  1. If the pattern context is a type T such that:
[[incompatible-int.gif|width=213px]]

Then the pattern context is incompatible with an integer pattern and a compile-time error will be 
reported. This is true if the pattern context is any of the following:

* A value type not implicitly convertible to `int`.
* A sealed reference type not implicitly convertible to `int`.
* A case class, or any type derived from a case class.
* A generic parameter constrained to any of the above types.

  1. Otherwise interpretation of the integer literal pattern will succeed.

  2. If pattern interpretation succeeds and the pattern context is a list or tuple type then a compile-time warning will be reported.

Float Literal Patterns (3.14)

  1. If the pattern context is a type T such that:
[[incompatible-float.gif|width=256px]]

Then the pattern is incompatible with a floating point literal pattern and a compile-time error will be reported. This is 
true if the pattern context is any of the following:

* A value type not implicitly convertible to `double`.
* A sealed reference type not implicitly convertible to `double`.
* A case class, or an type derived from a case class.
* A generic parameter constrained to any of the above types

  1. Otherwise interpretation of the floating point literal succeeds.

  2. If interpretation of the floating pointer literal succeeds and the pattern context is a list type or tuple type then a compile-time warning will be reported.

Char Literal Patterns ('x')

  1. If the pattern context is a type T such that:
[[incompatible-char.gif|width=225px]]

Then the pattern is incompatible with a character literal pattern and a compile-time error will be reported. This is 
true if the pattern context is any of the following:

* A value type not implicitly convertible to `char`.
* A sealed reference type not implicitly convertible to `char`.
* A case class, or an type derived from a case class.
* A generic parameter constrained to any of the above types

  1. Otherwise interpretation of the character literal succeeds.

  2. If interpretation of the character literal succeeds and the pattern context is a list type or tuple type then a compile-time warning will be reported.

String Literal Patterns

  1. If the pattern context is a type T such that:
[[incompatible-string.gif|width=257px]]

Then the pattern is incompatible with a string literal pattern and a compile-time error will be reported. This is 
true if the pattern context is any of the following:

* A value type not implicitly convertible to `[char]`.
* A sealed reference type not implicitly convertible to `[char]`.
* A case class, or an type derived from a case class.
* A generic parameter constrained to any of the above types

  1. Otherwise interpretation of the string literal succeeds.

  2. If interpretation of the string literal succeeds and the pattern context is a tuple type then a compile-time warning will be reported.

Bool Literal Patterns

  1. If the pattern context is a type T such that:
[[incompatible-bool.gif|width=518px]]

Then it is incompatible with a bool literal pattern and a compile-time error will be reported. This is true if the pattern 
context is any of:

* A value type not implicitly convertible to `bool` and not usable in a conditional context.
* A sealed reference type not implicitly convertible to `bool` and not usable in a conditional context.
* A case or constructor class.
* A generic parameter constrained to any of the above types.
  1. Otherwise inference of the boolean pattern succeeds.
  2. If the inference is successful, and the pattern context is a list type, tuple type, or function type, then a compile-time warning will be reported.

Formal Semantics

Below is a small-step operational semantics for switch statement pattern inference. See OperationalSemantics for an introduction to the notation.

Type Checking

Add a custom footer
Add a custom sidebar
Clone this wiki locally