# Template generics

<!--
Part of the Carbon Language project, under the Apache License v2.0 with LLVM
Exceptions. See /LICENSE for license information.
SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-->

[Pull request](https://github.com/carbon-language/carbon-lang/pull/2200)

<!-- toc -->

## Table of contents

-   [Abstract](#abstract)
-   [Problem](#problem)
-   [Background](#background)
-   [Terminology](#terminology)
-   [Proposal](#proposal)
-   [Details](#details)
    -   [Syntax](#syntax)
        -   [Branching on type identity](#branching-on-type-identity)
    -   [Value phases](#value-phases)
    -   [`auto`](#auto)
    -   [Template constraints](#template-constraints)
    -   [Name lookup](#name-lookup)
    -   [Transition from C++ templates to Carbon checked generics](#transition-from-c-templates-to-carbon-checked-generics)
        -   [To template Carbon with structural constraints](#to-template-carbon-with-structural-constraints)
        -   [To interface constraints](#to-interface-constraints)
        -   [To checked generic](#to-checked-generic)
    -   [Validity can depend on value](#validity-can-depend-on-value)
    -   [Template dependent](#template-dependent)
        -   [Simple member access](#simple-member-access)
        -   [Compound member access](#compound-member-access)
        -   [Impl lookup](#impl-lookup)
        -   [Use of dependent value is dependent](#use-of-dependent-value-is-dependent)
-   [Rationale](#rationale)
-   [Alternatives considered](#alternatives-considered)
    -   [Only checked generics](#only-checked-generics)
    -   [SFINAE](#sfinae)
    -   [Ad hoc API specialization](#ad-hoc-api-specialization)
    -   [Value phase of bindings determined by initializer](#value-phase-of-bindings-determined-by-initializer)
    -   [Simpler template dependent rules that delayed more checking](#simpler-template-dependent-rules-that-delayed-more-checking)
-   [Future work](#future-work)
    -   [Expanded template constraints](#expanded-template-constraints)
    -   [Predicates: constraints on values](#predicates-constraints-on-values)
    -   [Checked generics calling templates](#checked-generics-calling-templates)
    -   [Which expressions will be evaluated at compile time](#which-expressions-will-be-evaluated-at-compile-time)

<!-- tocstop -->

## Abstract

Add template generics, with optional constraints but no
[SFINAE](https://en.cppreference.com/w/cpp/language/sfinae), to Carbon. Template
generics allows the compiler to postpone type checking of expressions dependent
on a template parameter until the function is called and the value of that
parameter is known.

Example usage:

```carbon
fn Identity[template T:! Type](x: T) -> T {
  return x;
}
```

## Problem

Starting with
[#24: Generics goals](https://github.com/carbon-language/carbon-lang/pull/24),
we have assumed templates (also known as "template generics" in Carbon) will be
a feature of Carbon, but it has not been an accepted part of the design. We now
understand enough about how they should fit into the language to decide that we
are including the feature in the language, and what form they should take.

Template generics will address these use cases:

-   They provide a step in the transition from C++ templates to Carbon checked
    generics.
-   They provide a generics programming model familiar to C++ developers.
-   They allow Carbon to separate features that we don't want to expose by
    default in checked generics. These are features that pierce abstraction
    boundaries that we want to discourage for software engineering reasons or at
    least mark when they are in use. Examples in this category include:
    -   Compile-time duck typing features that use the structural properties of
        types, like having a method with a particular name, rather than semantic
        properties like implementing an interface.
    -   Branching in code based on type identity.

Out of scope for this proposal are any questions about passing a checked generic
argument value to a template parameter. See question-for-leads issue
[#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153).

## Background

Templates are the mechanism for performing
[generic programming](https://en.wikipedia.org/wiki/Generic_programming) in C++,
see [cppreference.com](https://en.cppreference.com/w/cpp/language/templates).

There have been a number of prior proposals and questions-for-leads issues on
template generics on which this proposal builds:

-   Proposal
    [#24: Generics goals](https://github.com/carbon-language/carbon-lang/pull/24)
    talked about the reasons for templates, without committing Carbon to
    including them. These reasons include making it easier to transition C++
    template code to Carbon and providing functionality outside of what we want
    to support with checked generics.
-   Proposal
    [#447: Generics terminology](https://github.com/carbon-language/carbon-lang/pull/447)
    defined terminology. This included some of the differences between checked
    and template generics, and definitions for terms like _instantiation_.
-   Proposal
    [#553: Generic details part 1](https://github.com/carbon-language/carbon-lang/pull/553)
    defined `auto` as a template construct, and described how templates do not
    require constraints to find member names.
-   Question-for-leads issue
    [#565: Generic syntax to replace provisional `$`s](https://github.com/carbon-language/carbon-lang/issues/565)
    implemented in proposal
    [#676: `:!` generic syntax](https://github.com/carbon-language/carbon-lang/pull/676)
    defined the syntax for template bindings.
-   Proposal
    [#731: Generics details 2: adapters, associated types, parameterized interfaces](https://github.com/carbon-language/carbon-lang/pull/731)
    included that template values may be passed to generic parameters.
-   Proposal
    [#818: Constraints for generics](https://github.com/carbon-language/carbon-lang/pull/818)
    included `template constraint` to defined named constraints with fewer
    restrictions for use with template parameters.
-   Proposal
    [#875: Principle: information accumulation](https://github.com/carbon-language/carbon-lang/pull/875)
    considered how the principle benefited and was impacted by templates.
-   Question-for-leads issue
    [#949: Constrained template name lookup](https://github.com/carbon-language/carbon-lang/issues/949)
    implemented in proposal
    [#989: Member access expressions](https://github.com/carbon-language/carbon-lang/pull/989)
    defined how name lookup works for template parameters. It provided a path to
    incrementally adopt constraints on template parameters, a stepping stone to
    transitioning to checked generics.
-   Proposal
    [#950: Generics details 6: remove facets](https://github.com/carbon-language/carbon-lang/pull/950)
    included the impact on the semantics of templates in its rationale.
-   Proposal
    [#1146: Generic details 12: parameterized types](https://github.com/carbon-language/carbon-lang/pull/1146)
    allowed template type parameters.
-   Proposal
    [#1270: Update and expand README content and motivation for Carbon](https://github.com/carbon-language/carbon-lang/pull/1270)
    advertised that Carbon would support templates for "seamless C++ interop."
-   Terminology was updated in proposal
    [#2138: Checked and template generic terminology](https://github.com/carbon-language/carbon-lang/pull/2138).

TODO: Update if proposal
[#2188: Pattern matching syntax and semantics](https://github.com/carbon-language/carbon-lang/pull/2188)
is accepted first.

## Terminology

-   A _template dependent_ name or expression is one whose meaning depends on,
    that is varies with, some template generic parameter. Specifically this
    refers to an expression that can not be fully checked until the value of the
    parameter is known. This is consistent with the meaning of this term in
    [C++](https://en.cppreference.com/w/cpp/language/dependent_name), but is
    different from
    ["dependent types"](https://en.wikipedia.org/wiki/Dependent_type). The
    specifics of how this works in Carbon are being proposed in
    [a later section](#template-dependent).
-   [_Instantiation_](/docs/design/generics/terminology.md#instantiation),
    _substitution_, or
    [_monomorphizaton_](https://en.wikipedia.org/wiki/Monomorphization) is the
    process of duplicating the implementation of a function and then
    substituting in the values of any (checked or template) generic arguments.
-   Errors that are only detected once the argument value from the call site is
    known are called _monomorphization errors_. These mostly occur in
    expressions dependent on some template parameter, but can also occur for
    other reasons like hitting an implementation limit.
-   _SFINAE_ stands for "Substitution failure is not an error", which is the
    policy in C++, see
    [cppreference](https://en.cppreference.com/w/cpp/language/sfinae),
    [wikipedia](https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error).
    It means that functions from an overload set with monorphization errors, or
    "substitution failure," within their signatures are simply ignored instead
    of causing compilation to fail.

## Proposal

We propose that template generics are included as an official feature of Carbon.

In many ways, template generic parameters work like checked generic parameters.
The following are true for any kind of generic parameter:

-   The value passed to a generic parameter must be able to be evaluated at
    compile time.
-   Generic parameters may have constraints that will be enforced by the
    compiler on the value supplied by the caller.
-   The compiler may choose to generate multiple copies of a generic function
    for different values of the generic parameters.

The main differences between checked and templated generics are:

-   Member lookup into a templated type looks in the actual type value provided
    by the caller in addition to in any constraints on that type; see
    [proposal #989](https://github.com/carbon-language/carbon-lang/pull/989).
-   A templated parameter may be used in ways where the validity of the result
    depends on the value of the parameter, not just its type.
-   Impl lookup is delayed until all templated types, interfaces, and parameters
    are known.

As a consequence of these differences, type checking of any expression dependent
on a templated parameter may not be completed until its value is known. In
addition, templated generics support branching on the value of a templated type.

In contrast with C++ templates, with Carbon template generics:

-   Substitution failure is an error. In C++, [the SFINAE rule](#terminology)
    will skip functions in overload resolution that fail to instantiate.
    Instead, Carbon template parameters use constraints to control when the
    function is available.
-   Carbon template specialization does not allow ad hoc changes to the API of
    the function or type being specialized, only its implementation. This is in
    contrast to C++, where
    [C++'s `std::vector<bool>`](https://en.cppreference.com/w/cpp/container/vector_bool)
    has different return types for certain methods. Anything that can vary in an
    API must be explicitly marked using associated types of an interface, as is
    described in the
    ["parameterized type specialization" design](/docs/design/generics/details.md#specialization).
-   Constraints on a Carbon template type affect how lookup is done into that
    type, as described in
    [proposal #989](https://github.com/carbon-language/carbon-lang/pull/989).

## Details

### Syntax

Template generic bindings are declared using the `template` keyword in addition
to the `:!` of all generic bindings. This includes `let` declarations, as in:

```carbon
// `N` is a constant that may be used in types.
let template N:! i64 = 4;
var my_array: [u8; N] = (255, 128, 64, 255);
```

Function parameters also default to a `let` context and may use `template`:

```carbon
// `U` is a templated type parameter that must be specified
// explicitly by the caller.
fn Cast[template T:! Type](x: T, template U:! Type) -> U {
  // OK, check for `T is As(U)` delayed until values of `T` and `U` are known.
  return x as U;
}

let x: i32 = 7;
// Calls `Cast` with `T` set to `i32` and `U` set to `i64`.
let y: auto = Cast(x, i64);
// Type of `y` is `i64`.
```

Note that generic bindings, checked or template, can only be used in `let`
context to produce r-values, not in a `var` context to produce l-values.

```carbon
// ❌ Error: Can't use `:!` with `var`. Can't be both a
//           compile-time constant and a variable.
var N:! i64 = 4;
// ❌ Error: Can't use `template :!` with `var` for the
//           same reason.
var template M:! i64 = 5;
```

#### Branching on type identity

Branching on the value of a templated type will be done using a `match`
statement, but is outside the scope of this proposal. See instead pending
proposal
[#2188: Pattern matching syntax and semantics](https://github.com/carbon-language/carbon-lang/pull/2188).

### Value phases

R-values are divided into three different _value phases_:

-   A _constant_ has a value known at compile time, and that value is available
    during type checking, for example to use as the size of an array. These
    include literals (integer, floating-point, string), concrete type values
    (like `f64` or `Optional(i32*)`), expressions in terms of constants, and
    values of `template` parameters.
-   A _symbolic value_ has a value that will be known at the code generation
    stage of compilation when monomorphization happens, but is not known during
    type checking. This includes checked-generic parameters, and type
    expressions with checked-generic arguments, like `Optional(T*)`.
-   A _runtime value_ has a dynamic value only known at runtime.

So:

-   A `let template T:! ...` or `fn F(template T:! ...)` declaration binds `T`
    with constant value phase,
-   A `let T:! ...` or `fn F(T:! ...)` declaration binds `T` with symbolic value
    phase,
-   A `let x: ...` or `fn F(x: ...)` declaration binds `x` with runtime value
    phase.

**Note:** The naming of value phases is the subject of open question-for-leads
issue
[#1391: New name for "constant" value phase](https://github.com/carbon-language/carbon-lang/issues/1391).
This terminology comes from
[a discussion in #typesystem on Discord](https://discord.com/channels/655572317891461132/708431657849585705/992817321074774098),
in particular
[this message](https://discord.com/channels/655572317891461132/708431657849585705/994396535561408623).

**Note:** This reflects the resolution of question-for-leads issue
[#1371: Is `let` referentially transparent?](https://github.com/carbon-language/carbon-lang/issues/1371)
that the value phase of a binding is determined by the kind of binding, and not
anything about the initializer.

**Note:** The situations in which a value with one phase can be used to
initialize a binding with a different value phase is future work, partially
considered in question-for-leads issue
[#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153)
in addition to
[#1371: Is `let` referentially transparent?](https://github.com/carbon-language/carbon-lang/issues/1371).

**Note:** Exactly which expressions in terms of constants result in constants is
an open question that is not resolved by this proposal. In particular, which
function calls will be evaluated at compile time is not yet specified. See
[future work](#which-expressions-will-be-evaluated-at-compile-time).

### `auto`

The `auto` keyword is a shortcut for an unnamed templated type, as in:

```carbon
// Type of `x` is the same as the return type of function `F`.
let x: auto = F();
```

This was first added to Carbon in proposal
[#553: Generic details part 1](https://github.com/carbon-language/carbon-lang/pull/553)
and further specified by open proposal
[#2188: Pattern matching syntax and semantics](https://github.com/carbon-language/carbon-lang/pull/2188).

The `auto` keyword may also be used to omit the return type, as specified in
[#826: Function return type inference](https://github.com/carbon-language/carbon-lang/pull/826).

The semantics of `let x:! auto = ...` is the subject of open question-for-leads
issue
[#996: Generic `let` with `auto`?](https://github.com/carbon-language/carbon-lang/issues/996).

### Template constraints

Template constraints have already been introduced in proposal
[#818: Constraints for generics](https://github.com/carbon-language/carbon-lang/pull/818).
In brief, a `template constraint` declaration is like a `constraint`
declaration, except that it may also contain function and field declarations,
called _structural constraints_. Only types with matching declarations will
satisfy the template constraint. Note that the declarations matching the
structural constraints must be found by member lookups in the type. It is not
sufficient for them to be declared only in an external impl.

```carbon
interface A { fn F[me: Self](); }
interface B { fn F[me: Self](); }
class C { }
external impl C as A;
external impl C as B;
template constraint HasF {
  fn F[me: Self]();
}
fn G[template T:! HasF](x: T);
var y: C = {};
// Can't call `G` with with `y` since it doesn't have any internal
// implementation of a method `F` satisfying `HasF`, even though `C`
// externally implements both `A` and `B` with such an `F`. May
// define an adapter for `C` to get a type that implements `HasF`,
// with `A.F`, `B.F`, or some other definition.
```

This was discussed in
[#generics-and-templates on 2022-09-20](https://discord.com/channels/655572317891461132/941071822756143115/1021903925613449316).

Structural constraints do not affect [name lookup](#name-lookup) into template
type parameters. They guarantee that a name will be available in the type, but
don't change the outcome.

```carbon
template constraint HasF {
  fn F[me: Self]();
}
class C {
  fn F[me: Self]();
}
fn G[template T:! HasF](x: T) {
  x.F();
}
var y: C = {};
// Call to `F` inside `G` is not ambiguous since
// `C.F` and `HasF.F` refer to the same function.
G(y);
class D extends C {
  alias F = C.(A.F);
}
// OK, `z.(HasF.F)` will resolve to `z.(C.(A.F))`.
fn Run(z: D) { G(z); }
```

Whether template constraints may be used as constraints on checked-generic
parameters is being considered in question-for-leads issue
[#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153).
Even if we allow a checked-generic parameter to use a template constraint, we
want to focus checked generics on semantic properties encapsulated in
interfaces, not structural properties tested by template constraints. So we
would not allow lookup into a checked-generic type to find type members outside
of an interface:

```carbon
template constraint HasF {
  fn F[me: Self]();
}
// ❓ If we allow a checked generic to use a template
// constraint, as in:
fn H[T:! HasF](x: T) {
  // We still will not support calling `F` on `x`:
  // ❌ x.F();
}
```

These members would only be found using a template type parameter.

[Expanding the kinds of template constraints](#expanded-template-constraints)
and
[defining a way to put constraints on values](#predicates-constraints-on-values)
are both [future work](#future-work).

### Name lookup

Name lookup for templates has already been decided in question-for-leads issue
[#949: Constrained template name lookup](https://github.com/carbon-language/carbon-lang/issues/949)
and proposal
[#989: Member access expressions](https://github.com/carbon-language/carbon-lang/pull/989).
Briefly, name lookup is done both in the actual type value supplied at the call
site and the interface constraints on the parameter. If the name is found in
both, it is an error if they resolve to different entities.

Look up into the calling type gives _compile-time duck typing_ behavior, much
like C++ templates, as in:

```carbon
fn F[template T:! Type](x: T) {
  // Calls whatever `M` is declared in `T`, and will
  // fail if `T` does not have a matching member `M`.
  x.M();
}

class C1 { fn M[me: Self](); }
var x1: C1 = {};
// Calls `F` with `T` equal to `C1`, which succeeds.
F(x1);

class C2 { fn M[addr me: Self*](); }
var x2: C2 = {};
// Calls `F` with `T` equal to `C2`, which fails,
// since `x` is an r-value in `F` and `C2.M` requires
// an l-value.
F(x2);

class C3 { fn M[me: Self](p: i32); }
var x3: C3 = {};
// Calls `F` with `T` equal to `C3`, which fails,
// since `C3.M` must be passed an argument value.
F(x3);

class C4 { fn M[me: Self](p: i32 = 4); }
var x4: C4 = {};
// Calls `F` with `T` equal to `C4`, which succeeds,
// using the default value of `4` for `p` when
// calling `C4.M`.
F(x4);

class C5 { var v: i32; }
var x5: C5 = {.v = 5};
// Calls `F` with `T` equal to `C5`, which fails,
// since `T` has no member `M`.
F(x5);
```

Note that in some cases of looking up a qualified name, lookup will not depend
on the value of the template parameter and can be checked before instantiation,
as in:

```carbon
interface A {
  fn F[me: Self]();
}

fn G[template T:! A](x: T) {
  // No question what this resolves to, can be checked
  // when `G` is defined:
  x.(A.F)();

  // Will generate a monomorphization error if
  // `T.F` means something different than `T.(A.F)`,
  // can only be checked when `G` is called:
  x.F();
}
```

### Transition from C++ templates to Carbon checked generics

We have a specific
[goal for generics](/docs/design/generics/goals.md#upgrade-path-from-templates)
that we have a smooth story for transitioning from C++ templates to Carbon
checked generics. Adding template generics to Carbon allows this to be done in
steps. These steps serve two purposes. One is to allow any updates needed for
callers and types used as parameters to be done incrementally. The second is to
avoid any silent changes in semantics that would occur from jumping directly to
Carbon checked generics. Each step will either preserve the meaning of the code
or result in compile failures.

#### To template Carbon with structural constraints

The first step is to convert the C++ function with one or more template
parameters to a Carbon function with template generic parameters. Any
[non-type template parameters](https://en.cppreference.com/w/cpp/language/template_parameters#Non-type_template_parameter)
can be converted to template generic parameters with the equivalent type, as in:

```
// This C++ function:
void F_CPlusPlus<int N>();

// gets converted to Carbon:
fn F_Carbon(template N:! i32);
```

Other template parameters can either be declared without constraints, using
`template T:! Type`, or using [structural constraints](#template-constraints).

To see if this transition can cause silent changes in meaning, consider how this
new Carbon function will be different from the old C++ one:

-   The conversion of the body of the code in the function could introduce
    differences, but only template concerns are in scope for this proposal.
-   The C++ code could use ad hoc API specialization. The only way to translate
    that to Carbon is through
    [explicit parameterization of the API](/docs/design/generics/details.md#specialization),
    which is not expected to introduce silent changes in meaning.
-   The C++ code could rely on [SFINAE](#terminology). C++ uses of
    `std::enable_if` should be translated to equivalent
    [template constraints](#template-constraints). Generally making substitution
    failure an error is expected to make less code compile, not introduce silent
    changes in meaning.
-   As long as the constraints on template type parameters are
    [structural](#template-constraints) and not interface constraints, the name
    lookup rules into those type parameters will consistently look in the type
    for both C++ and Carbon.

#### To interface constraints

The next step is to switch from structural constraints to interface constraints.
The interfaces that are providing the functionality that the function relies on
must be identified or created. In some cases this could be done automatically
when names are resolved consistently to interface methods in the types currently
being used to instantiate the function. Once that is done, there are two
approaches:

-   Implement the interface for every instantiating type. Once that is done, the
    function's constraint can be updated.
-   Alternatively, a blanket implementation of the interface could be defined
    for any type implementing the structural constraints so that the function's
    constraint can be updated first. After that, the interface can be
    implemented for types individually, overriding the blanket implementation
    until the blanket implementation is no longer needed. This second choice
    requires changes to the library defining the interface, and is most
    appropriate when it is a new interface specifically created for this
    function.

In either case, the compiler will give an error if the interface is not
implemented for some types before the step is finished.

An example of the second approach, starting with a templated function with a
structural constraint:

```carbon
template constraint HasF {
  fn F[me: Self]();
}

fn G[template T:! HasF](x: T) {
  x.F();
}

class C {
  fn F[me: Self]();
}
var y: C = {};
G(y);
```

First, a new interface is created with a blanket implementation and the
function's constraints are updated to use it instead. Calls in the function body
should be qualified to avoid ambiguity errors.

```carbon
template constraint HasF {
  fn F[me: Self]();
}

// New interface
interface NewF {
  fn DoF[me: Self]();
}

// Blanket implementation
external impl forall [template T:! HasF] T as NewF {
  // If the functions are identical, can instead do:
  //    alias DoF = T.F;
  fn DoF[me: Self]() {
    me.F();
    // Or: me.(T.F)();
  }
}

// Changed constraint
fn G[template T:! NewF](x: T) {
  // Call function from interface
  x.(NewF.DoF)();
  // Could use `x.DoF();` instead, but that will
  // give a compile error if `T` has a definition
  // for `DoF` in addition to the one in `NewF`.
}

class C {
  fn F[me: Self]();
}
var y: C = {};
// Still works since `C` implements `NewF`
// from blanket implementation.
G(y);
```

Then the interface is implemented for types used as parameters:

```carbon
// ...
class C {
  impl as NewF {
    // `NewF.DoF` will be called by `G`, not `C.F`.
    fn DoF[me: Self]();
  }
  // No longer needed: fn F[me: Self]();
}
// ...
```

Once all types have implemented the new interface, the blanket implementation
can be removed:

```carbon
// Template constraint `HasF` no longer needed.

// New interface
interface NewF {
  fn DoF[me: Self]();
}

// Blanket implementation no longer needed.

fn G[template T:! NewF](x: T) {
  x.(NewF.DoF)();
}

class C {
  impl as NewF {
    fn DoF[me: Self]();
  }
}
var y: C = {};
// `C` implements `NewF` directly.
G(y);
```

The [name lookup rules](#name-lookup) ensure that unqualified names will only
have one possible meaning, or the compiler will report an error. This error may
be resolved by adding qualifications, which is done with the context of an
ambiguity for a specific type. This avoids silent changes in the meaning of the
code. Once the disambiguating qualifications have been added, the transition to
checked generic becomes safe.

#### To checked generic

Once all needed qualifications are in place, the `template` keyword can be
removed. After this, names will only be looked up in the interface constraints,
not the type. If this does not cover the names used by the function, the
compiler will report an error and this step can be rolled back and the previous
step can be repeated to cover what was missed.

Qualifications in the body of the function can be removed at this point, if
desired, since the compiler will complain if this introduces an ambiguity from
two different interfaces using that name. It would be reasonable to leave the
qualifications in if the type parameter has multiple interface constraints, both
as documentation for readers and to protect against future name collisions if
the interfaces are changed.

### Validity can depend on value

A templated parameter may be used in ways where the validity of the result
depends on the value of the parameter, not just its type. As an example, whether
two array types are compatible depends on whether they have the same size. With
a symbolic constant sizes, they will only be considered equal if the compiler
can show that the two sizes are always equal symbolically. If the size is a
template parameter, the checking will be delayed until the value of the template
parameter is known.

### Template dependent

Expressions fall under three categories:

-   Expressions that are valid and have meaning determined without knowing the
    value of any template parameter are _not template dependent_.
-   Expressions whose meaning and validity requires knowing the value of a
    template parameter are _template dependent_. Template dependent expressions
    are not fully type checked until the template is instantiated, which can
    result in monomorphization errors. Further, template dependent
    subexpressions commonly cause a containing expression to also be dependent,
    as described in the
    ["use of dependent value is dependent" section](#use-of-dependent-value-is-dependent).
-   Expressions that have a meaning without knowing the value of any template
    parameter, assuming it is valid, but whose validity requires knowing the
    value of a template parameter are _template validity dependent_. These
    expressions can trigger a monomorphization error, but are not considered
    template dependent for purposes of a containing expression.

The compiler will type check expressions that are not template dependent when
the function is defined, and they won't trigger monomorphization errors.

Note that an expression may not be template dependent even though it has a
template-dependent sub-expression. For example, a function may have a value that
is function dependent, but calling that function only needs the type of the
function (meaning the function's signature) to not be template dependent.

#### Simple member access

There are three cases when performing unqualified member-name lookup into a
templated type:

```carbon
fn F[template T:! I](x: T) {
  x.G();
}
```

-   If generic name lookup would succeed, in this example it would be because
    `G` is a member of `I`, then the result of name lookup is template validity
    dependent. This means that template instantiation may fail if `T` has a
    member `G` different than `T.(I.G)`. Assuming it succeeds, though, it will
    definitely have meaning determined by `I.G`. There may still be ambiguity
    making the result dependent if it is not known whether `x` is a type and
    `I.G` is a method and so has an implicit `me` parameter.
-   If the member name is not found in the constraint, lookup may still succeed
    once the type is known, so the result is template dependent.
-   If the lookup is ambiguous prior to knowing the value of the type, for
    example if `G` has two distinct meanings in `I`, then the code is invalid.

The value of the expression will be dependent. For example, if `U` is an
associated type of `I`, then `T.U` as an expression is template validity
dependent, but the value of that expression is dependent. The value is not
always needed to perform checking, for example `x.G()` can be checked without
ever determining the value of `x.G` as long as its signature can be determined,
if it is valid.

#### Compound member access

Adding qualifier to the member name, as in `x.(U.V)`, can make the lookup less
dependent on the template parameter:

-   If `x` is dependent, and `U` is an interface, the value of the expression is
    dependent, but the type of the expression is not dependent unless the type
    of `U.V` involves `Self`. The lookup itself follows proposal
    [#2360](https://github.com/carbon-language/carbon-lang/pull/2360):

    -   If `U.V` is an _instance_ member, and the type of `x` is known to
        implement `U`, then the lookup is not dependent. For example, there
        could be a requirement on `x` or a sufficiently general implementation
        of `U` that includes all possible types of `x`. The resulting value is
        dependent unless the implementation of `U` is `final`, see
        [the impl lookup section](#impl-lookup).
    -   Otherwise, the lookup is template validity dependent.

    ```carbon
    interface Serializable {
      fn Serialize[me: Self]();
    }

    interface Printable {
      fn Print[me: Self]();
    }

    interface Hashable {
      let HashType:! Type;
      fn Hash[me: Self]() -> HashType;
    }

    external impl forall [T:! Serializable] T as Hashable;

    fn F[template T:! Serializable](x: T) {
      // `T` is required to implement `Serializable` and
      // `Serialize` is an instance member, so this is not
      // dependent.
      x.(Serializable.Serialize)();

      // Any `T` implementing `Serializable` also implements
      // `Hashable`, since there is a blanket implementation,
      // so this is not dependent. Note: there may be a
      // specialization of this impl, so we can't rely on
      // knowing how `T` implements `Hashable`.
      x.(Hashable.Hash)();

      // Unclear whether `T` implements `Printable`, but if
      // does, clear what this means, so this is template
      // validity dependent
      x.(Printable.Print)();

      match (x.(Hashable.Hash)()) {
        // Uses the value of the associated type
        // `Hashable.HashType` that is template dependent.
        case _: u64 => { ... }
        default => { ... }
      }
    }
    ```

-   If `U.V` is dependent, then the entire expression is dependent.

#### Impl lookup

If the validity of an expression requires that an impl exist for a type, and
that can't be determined until the value of a template parameter is known, then
the expression is template validity dependent. For example, in the example from
the previous section, `x.(Printable.Print)()` is valid if `T` implements
`Printable`. This can also occur without a qualified lookup, for example:

```carbon
fn F[T:! Printable](x: T);
fn G[template T:! Type](x: T) {
  // Valid if `T` implements `Printable`, so this
  // expression is template validity dependent.
  F(x);
}
```

The values of members of an impl for a template-dependent type are template
dependent, unless they can be resolved to a not template-dependent expression
using checked-generic impl resolution.

```
final external impl [T:! Type] T* as D
    where .Result = T and .Index = i32;
fn F[T:! Type](p: T*) {
  // `(T*).(D.Index)` uses the final impl of `D` for `T*`,
  // and so equals `i32`, which is not dependent.
  // `(T*).(D.Result)` is recognized as equal to `T`, which
  // is template dependent.
}
```

#### Use of dependent value is dependent

To match the expectations of C++ templates, uses of dependent values are also
template dependent, propagating dependence from subexpressions to enclosing
expressions. For example, if `expr` is a dependent expression, each of these is
dependent:

-   `(expr)`
-   `F(expr)`
-   `expr + 1`
-   `if a then expr else b`
-   `a as expr`

In some cases, an expression's type and value category can be determined even
when a subexpression is dependent. This makes the expression template validity
dependent, rather than dependent. For example, the types of these expressions
are not dependent, even when `expr` is a dependent subexpression:

-   `if expr then a else b`
-   `expr as T`

For `match`, which `case` body is executed may be dependent on the type of the
match expression. For example:

```
fn TypeName[template T:! Type](x: T) -> String {
  match (x) {
    // Each entire case body is dependent
    case _: i32 => { return "int"; }
    case _: bool => { return "bool"; }
    case _: auto* => { return "pointer"; }
    // Allowed even though body of case is invalid for
    // `T != Vector(String)`
    case _: Vector(String) => { return x.front(); }
    default => { return "unknown"; }
  }
}
```

## Rationale

This proposal advances these Carbon goals:

-   [Performance-critical software](/docs/project/goals.md#performance-critical-software),
    by providing an alternative to checked generics that has greater access to
    the specific value of the parameter.
-   [Code that is easy to read, understand, and write](/docs/project/goals.md#code-that-is-easy-to-read-understand-and-write)
    by specifically marking code that is using features that should receive
    greater scruitiny.
-   [Interoperability with and migration from existing C++ code](/docs/project/goals.md#interoperability-with-and-migration-from-existing-c-code),
    specifically migrating C++ code using templates, as detailed in the
    ["transition from C++ templates to Carbon checked generics" section](#transition-from-c-templates-to-carbon-checked-generics).

## Alternatives considered

### Only checked generics

Like Rust, Carbon could use only checked generics and not support templates. The
reasons for this approach are detailed in the ["problem" section](#problem).

### SFINAE

We could use the [SFINAE rule](#terminology), to match C++. While familiar, it
prevents the compiler from being able to distinguish between "this code is not
meant for this case" from "this code has an error." The goal of eliminating
SFINAE is to get away from the verbose and unclear errors that templates are
infamous for. C++ itself, with
[concepts](https://en.cppreference.com/w/cpp/language/constraints), is moving
toward stating requirements up front to improve the quality of error
diagnostics.

### Ad hoc API specialization

Consider a type with a template type parameter:

```carbon
class Vector(template T:! Type) {
  fn GetPointer[addr me: Self*](index: i32) -> T*;
  // ...
}
```

To be able to type check a checked generic function using that type:

```carbon
fn SetFirst[T:! Type](vec: Vector(T)*, val: T) {
  let p: T* = vec->GetPointer(0);
  *p = val;
}
```

we need a guarantee that the function signature used to type check the function
is correct. This won't in general be true if ad hoc specialization is allowed:

```carbon
// ❌ Not legal Carbon, no ad hoc specialization
class Vector(bool) {
  // `let p: T* = vec->GetPointer(0)` won't type check
  // in `SetFirst` with `T == bool`.
  fn GetPointer[addr me: Self*](index: i32) -> BitProxy;
  // ...
}
```

Specialization is still important for performance, but Carbon's
[existing approach to specialization of parameterized types](/docs/design/generics/details.md#specialization)
makes it clear what parts of the signature can vary, and what properties all
specializations will have. In this example, `Vector` would have to be declared
alongside an interface, and implementations of that interface, as in:

```carbon
class Vector(template T:! Type);

interface VectorSpecialization {
  let PointerType: Deref(Self);
  fn GetPointer(p: Vector(Self)*, index: i32) -> PointerType;
}

// Blanket implementation provides default when there is
// no specialization.
impl forall [T:! Type] T as VectorSpecialization
    where .PointerType = T* { ... }

// Specialization for `bool`.
impl bool as VectorSpecialization
    where .PointerType = BitProxy { ... }

class Vector(template T:! Type) {
  // Return type of `GetPointer` varies with `T`, but must
  // implement `Deref(T)`.
  fn GetPointer[addr me: Self*](index: i32)
      -> T.(VectorSpecialization.PointerType) {
    return T.(VectorSpecialization.GetPointer)(me, index);
  }
  // ...
}
```

### Value phase of bindings determined by initializer

We considered allowing a `let` binding to result in a name with
[constant value phase](#value-phases) if the initializer was a constant, even if
it was not declared using the `template` keyword. That would mean that
`let x: i32 = 5;` would declare `x` as constant, rather than a runtime value.

For non-type values, this would be a strict improvement in usability. With the
proposal, there is a choice between writing the concise form `let x: i32 = 5;`
and `let template x:! i32 = 5;` that lets the compiler use the value of `x`
directly. The `let template` form is both longer and uses `template` which in
other contexts might merit closer scrutiny, but is generally either desirable or
harmless in this context. The problem is that for type values, changing from a
symbolic value to a constant results in a change to the
[name lookup](#name-lookup) rules, which is not going to always be desired.

This decision was the result of a discussion in open discussions on
[2022-09-09](https://docs.google.com/document/d/1tEt4iM6vfcY0O0DG0uOEMIbaXcZXlNREc2ChNiEtn_w/edit#heading=h.g1xcokypbstm).

### Simpler template dependent rules that delayed more checking

We considered simpler rules for which expressions were considered
[template dependent](#template-dependent), like that any expression involving a
template parameter was template dependent. This had the downside that it would
have delayed checking of more expressions, and would have resulted in greater
differences between template and checked generic semantics. Ultimately we
thought that the developer experience would be better if errors were delivered
earlier.

This was discussed in
[open discussion on 2022-10-10](https://discord.com/channels/655572317891461132/941071822756143115/1029411854277165137)
and on
[Discord #generics-and-templates starting 2022-10-11](https://discord.com/channels/655572317891461132/941071822756143115/1029411854277165137).

## Future work

### Expanded template constraints

[Template constraints](#template-constraints) will need to support other kinds
of structural constraints. In particular, the kinds of constraints that can be
expressed in C++20 Concepts:

-   [Constraints and concepts (since C++20)](https://en.cppreference.com/w/cpp/language/constraints)
-   [Requires expression (since C++20)](https://en.cppreference.com/w/cpp/language/requires)

This is both to allow the constraints of existing C++ code to be migrated, and
because we expect constraints that were found to be useful in C++ will also be
useful for Carbon.

### Predicates: constraints on values

We will need some mechanism to express that the value of a non-type template
parameter meets some criteria. For example, the size parameter of an array must
not be less than 0. We are considering a construct called _predicates_ to
represent these kinds of constraints, see the question-for-leads issue
[#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153).

### Checked generics calling templates

For checked generics interoperation with existing templates, and to allow
templates to be migrated to checked generics in any order, we want Carbon to
support supplying a symbolic constant argument value, such as from a checked
generic function, to a function taking a template parameter. One approach that
already works is using a template implementation of an interface, as in this
example:

```carbon
fn TemplateFunction[template T:! Type](x: T) -> T;

// `Wrapper` is an interface wrapper around
// `TemplateFunction`.

interface Wrapper {
  fn F[me: Self]() -> Self;
}

external impl forall [template T:! Type] T as Wrapper {
  fn F[me: Self]() -> Self {
    TemplateFunction(me);
  }
}

// ✅ Allowed:
fn CheckedGeneric[T:! Wrapper](z: T) -> T {
  return z.(Wrapper.F)();
}

// ⚠️ Future work, see #2153:
fn CheckedGenericDirect[T:! Type](z: T) -> T {
  return TemplateFunction(z);
}
```

More direct interoperation is being considered in question-for-leads issue
[#2153: Generics calling templates](https://github.com/carbon-language/carbon-lang/issues/2153).

### Which expressions will be evaluated at compile time

The section on [value phases](#value-phases) and the
["value phase of bindings determined by initializer" alternative](#value-phase-of-bindings-determined-by-initializer)
still leave open some questions about how value phases interact, and what gets
evaluated at compile time. For example, what happens when there is a function
call in the initializer of a `let template`, as in:

```carbon
let x: i32 = 5;
let template Y:! i32 = F(x);
```

Is the function call evaluated at compile time in order to determine a value for
`Y`, or is this an error? Does it depend on something about `F`, such as its
definition being visible to the caller and being free of side effects? Is this
only allowed since the value of `x` can be determined at compile time, even
though it is a runtime value, or would the declaration of `x` have to change? If
we allow this construction, observe that the parameter to `F` has different
value phases when called at compile time compared to run time, which might
affect the interpretation of the body of `F`.
