Unresolved (but typed) expressions in generics

[metagn]

The compiler may be unable to resolve an expression when it is being compiled in a generic (or template?) context because it depends on a context parameter (generic or static parameter). The unresolved expression can also propagate upward, i.e.:

when sizeof(T) == 4:
  ...

We don't know what T is, so sizeof(T) cannot be resolved as a constant expression, so neither can sizeof(T) == 4, so we cannot evaluate the when yet, so its branches need the untyped prepass (yet to be specified). However:

let x = sizeof(T)
echo x

sizeof(T) has a type, so it is still valid as a runtime expression, so x has the type int. When sizeof is replaced with a non-magic proc, we also need to prevent it from being instantiated, so an unresolved expression with a type can include calls with a non-instantiated callee. Unsure if this will cause problems.

The type of the unresolved expression does not have to be concrete either, we can give them generic types in the same way that routine parameters can have generic types.

proc foo[T](x: T): T = x

...
let x = foo(y) # y has type T, then x has type T, foo remains uninstantiated

For the cases where an expression depends on an unresolved parameter, I think Item should track it as unresolved: bool or maybe a more powerful usesTypevars: set[SymId] or something like that if needed. Then this can be ignored or propagated similar to the type. This is a divergence from the old compiler which generates tyFromExpr here even though the expression is not a type.

Edit: There is also this case:

const foo = sizeof(T)
when foo == 4:
  ...

So maybe there could also be an internal pragma specifically for consts that marks that their value is unresolved, maybe also storing the typevars it depends on.

---

The tricky part is when an unresolved expression is meant to become a type.

template foo(T: typedesc): typedesc =
  when T is int:
    int64
  else:
    float64

...
var x: foo(T)

foo(T) is an unresolved expression with a type that we know only satisfies typedesc. We need to give x a type but (call) nodes do not satisfy type AST, so we need something like tyFromExpr in the old compiler. This would also be used in sigmatch.

If we just have something like (unresolved (call foo T)) same as tyFromExpr, then every time we encounter it in sigmatch, we would need to try to instantiate it in case T has been resolved. To make this more efficient, we could also store a list of the type parameters used by the expression inside the (unresolved) type i.e. (unresolved (params T) (call foo T)). But it's unclear if the used type parameters would be reliably tracked and it might not be that much of a problem in comparison to just try to instantiate it.

We could also store the type that the original unresolved expression had before being converted into a type as the "base type" of the unresolved type, becoming (unresolved (typedesc) (params T) (call foo T)). This would store concept information etc. without having to semcheck the expression again to get its type, again minimizing the work sigmatch has to do.

I'm not sure if these additions are just redunancies for efficiency/simplicity or if they are needed for correctness. Maybe they are wrong too. We should probably start with them to make the implementation in sigmatch simpler.

The final case that comes to mind is unresolved expressions as static types. The direction we've been going is that expressions that are types always have the type typedesc, but values as types should always be wrapped in static (currently array violates this by just storing an integer but it should probably use range anyway). So it would be enough that:

type Bar[T: static int] =
  x: array[T, int]

var x: Bar[sizeof(T)]

gives (invoke Bar (unresolved (int) (params T) (sizeof T))). Then when the unresolved type is finally instantiated, if the expression has the type typedesc then it is skipped, otherwise it is wrapped in static. In any case this would just mirror what semLocalTypeImpl does for arbitrary expressions.

[metagn]

More generally:

An expression being unresolved means it has an indeterminate constant value. This includes type values. So, the expression sizeof(T) is unresolved, but the type of the expression sizeof(T) is not. Attempting to turn sizeof(T) into a type, a static type in this case, would create an unresolved type.

A type being unresolved also means it has an indeterminate value, as in it is meant to become another type. Concrete types cannot become other types, but type classes do. foo(T): typedesc is both unresolved and has an unresolved type. Any unresolved expression is wrapped in an (unresolved) type.

If I had a guess at the spec:

A type is unresolved if one of the following is true:

• it is a generic parameter
• it is an (unresolved) type
• it is a typeclass - specifically typeclasses that are allowed as return types as in foo(T) above, could be just typed/untyped
• it is a generic invocation or a structural type i.e. ref/array/tuple/maybe even proc where one of its children is unresolved

An expression is unresolved if:

• it is a symbol with an unresolved type. This sounds like an expensive check, but we are only concerned with expressions that have constant values, so instead we can check for:
  • generic parameter symbols
  • routine parameters with static/typedesc type
  • uninstantiated routine symbols, although these should be properly constructed
• it is a const symbol with an unresolved value
• it is a call where any of the arguments are unresolved
  • exception: typeof is only unresolved if the type of the argument is unresolved, not the argument itself
• it is a subscript, dot field, constructor etc where any of the participating expressions are unresolved
• edit: also probably if it's an type expression of an unresolved type, but this is probably covered by the above + type expressions are only really valid as typedesc arguments

Generic invocations and calls to generic routines where any of their generic arguments are unresolved are uninstantiated. In the case of calls, this probably means: overload resolution happens, if any of the routine parameters are inferred to be an unresolved type, the call still matches but is not instantiated. Maybe this should be marked in some way because this is one of the only contexts where uninstantiated symbols are valid.

[Araq]

Attempting to turn sizeof(T) into a type, a static type in this case, would create an unresolved type.

But why do we need to turn it into a type?

[metagn]

Bad wording, maybe a better way of saying it is "interpreting it as a type", i.e. encountering the expression in a type context. Interpreting a value as a type would create a static type, but sizeof(T) is not a concrete value.

[Araq]

We need to be careful that static T doesn't again infect the whole type system with more junk one usually has to "skip". Almost all usages I encountered would all work fine without a static annotation if the compiler allows values for types within at (and indeed it does).

[metagn]

I guess it's not needed, I thought maybe the information of the type of the value would need to be stored. Should be fine in sigmatch which sems the arguments and matches Items but invocations don't check constraint matches yet, in Foo[T: static int] = ...; Foo[123] we would have to check that 123 is an int.