Type relations
==============
The following section defines several relations on types that are needed to
describe the type checking done by the compiler.
Type equality
-------------
Nim uses structural type equivalence for most types. Only for objects,
enumerations and distinct types name equivalence is used. The following
algorithm, *in pseudo-code*, determines type equality:
.. code-block:: nim
proc typeEqualsAux(a, b: PType,
s: var HashSet[(PType, PType)]): bool =
if (a,b) in s: return true
incl(s, (a,b))
if a.kind == b.kind:
case a.kind
of int, intXX, float, floatXX, char, string, cstring, pointer,
bool, nil, void:
# leaf type: kinds identical; nothing more to check
result = true
of ref, ptr, var, set, seq, openarray:
result = typeEqualsAux(a.baseType, b.baseType, s)
of range:
result = typeEqualsAux(a.baseType, b.baseType, s) and
(a.rangeA == b.rangeA) and (a.rangeB == b.rangeB)
of array:
result = typeEqualsAux(a.baseType, b.baseType, s) and
typeEqualsAux(a.indexType, b.indexType, s)
of tuple:
if a.tupleLen == b.tupleLen:
for i in 0..a.tupleLen-1:
if not typeEqualsAux(a[i], b[i], s): return false
result = true
of object, enum, distinct:
result = a == b
of proc:
result = typeEqualsAux(a.parameterTuple, b.parameterTuple, s) and
typeEqualsAux(a.resultType, b.resultType, s) and
a.callingConvention == b.callingConvention
proc typeEquals(a, b: PType): bool =
var s: HashSet[(PType, PType)] = {}
result = typeEqualsAux(a, b, s)
Since types are graphs which can have cycles, the above algorithm needs an
auxiliary set ``s`` to detect this case.
Type equality modulo type distinction
-------------------------------------
The following algorithm (in pseudo-code) determines whether two types
are equal with no respect to ``distinct`` types. For brevity the cycle check
with an auxiliary set ``s`` is omitted:
.. code-block:: nim
proc typeEqualsOrDistinct(a, b: PType): bool =
if a.kind == b.kind:
case a.kind
of int, intXX, float, floatXX, char, string, cstring, pointer,
bool, nil, void:
# leaf type: kinds identical; nothing more to check
result = true
of ref, ptr, var, set, seq, openarray:
result = typeEqualsOrDistinct(a.baseType, b.baseType)
of range:
result = typeEqualsOrDistinct(a.baseType, b.baseType) and
(a.rangeA == b.rangeA) and (a.rangeB == b.rangeB)
of array:
result = typeEqualsOrDistinct(a.baseType, b.baseType) and
typeEqualsOrDistinct(a.indexType, b.indexType)
of tuple:
if a.tupleLen == b.tupleLen:
for i in 0..a.tupleLen-1:
if not typeEqualsOrDistinct(a[i], b[i]): return false
result = true
of distinct:
result = typeEqualsOrDistinct(a.baseType, b.baseType)
of object, enum:
result = a == b
of proc:
result = typeEqualsOrDistinct(a.parameterTuple, b.parameterTuple) and
typeEqualsOrDistinct(a.resultType, b.resultType) and
a.callingConvention == b.callingConvention
elif a.kind == distinct:
result = typeEqualsOrDistinct(a.baseType, b)
elif b.kind == distinct:
result = typeEqualsOrDistinct(a, b.baseType)
Subtype relation
----------------
If object ``a`` inherits from ``b``, ``a`` is a subtype of ``b``. This subtype
relation is extended to the types ``var``, ``ref``, ``ptr``:
.. code-block:: nim
proc isSubtype(a, b: PType): bool =
if a.kind == b.kind:
case a.kind
of object:
var aa = a.baseType
while aa != nil and aa != b: aa = aa.baseType
result = aa == b
of var, ref, ptr:
result = isSubtype(a.baseType, b.baseType)
.. XXX nil is a special value!
Convertible relation
--------------------
A type ``a`` is **implicitly** convertible to type ``b`` iff the following
algorithm returns true:
.. code-block:: nim
# XXX range types?
proc isImplicitlyConvertible(a, b: PType): bool =
case a.kind
of int: result = b in {int8, int16, int32, int64, uint, uint8, uint16,
uint32, uint64, float, float32, float64}
of int8: result = b in {int16, int32, int64, int}
of int16: result = b in {int32, int64, int}
of int32: result = b in {int64, int}
of uint: result = b in {uint32, uint64}
of uint8: result = b in {uint16, uint32, uint64}
of uint16: result = b in {uint32, uint64}
of uint32: result = b in {uint64}
of float: result = b in {float32, float64}
of float32: result = b in {float64, float}
of float64: result = b in {float32, float}
of seq:
result = b == openArray and typeEquals(a.baseType, b.baseType)
of array:
result = b == openArray and typeEquals(a.baseType, b.baseType)
if a.baseType == char and a.indexType.rangeA == 0:
result = b = cstring
of cstring, ptr:
result = b == pointer
of string:
result = b == cstring
A type ``a`` is **explicitly** convertible to type ``b`` iff the following
algorithm returns true:
.. code-block:: nim
proc isIntegralType(t: PType): bool =
result = isOrdinal(t) or t.kind in {float, float32, float64}
proc isExplicitlyConvertible(a, b: PType): bool =
result = false
if isImplicitlyConvertible(a, b): return true
if typeEqualsOrDistinct(a, b): return true
if isIntegralType(a) and isIntegralType(b): return true
if isSubtype(a, b) or isSubtype(b, a): return true
The convertible relation can be relaxed by a user-defined type
`converter`:idx:.
.. code-block:: nim
converter toInt(x: char): int = result = ord(x)
var
x: int
chr: char = 'a'
# implicit conversion magic happens here
x = chr
echo x # => 97
# you can use the explicit form too
x = chr.toInt
echo x # => 97
The type conversion ``T(a)`` is an L-value if ``a`` is an L-value and
``typeEqualsOrDistinct(T, type(a))`` holds.
Assignment compatibility
------------------------
An expression ``b`` can be assigned to an expression ``a`` iff ``a`` is an
`l-value` and ``isImplicitlyConvertible(b.typ, a.typ)`` holds.
Overloading resolution
======================
In a call ``p(args)`` the routine ``p`` that matches best is selected. If
multiple routines match equally well, the ambiguity is reported at compiletime.
Every arg in args needs to match. There are multiple different categories how an
argument can match. Let ``f`` be the formal parameter's type and ``a`` the type
of the argument.
1. Exact match: ``a`` and ``f`` are of the same type.
2. Literal match: ``a`` is an integer literal of value ``v``
and ``f`` is a signed or unsigned integer type and ``v`` is in ``f``'s
range. Or: ``a`` is a floating point literal of value ``v``
and ``f`` is a floating point type and ``v`` is in ``f``'s
range.
3. Generic match: ``f`` is a generic type and ``a`` matches, for
instance ``a`` is ``int`` and ``f`` is a generic (constrained) parameter
type (like in ``[T]`` or ``[T: int|char]``.
4. Subrange or subtype match: ``a`` is a ``range[T]`` and ``T``
matches ``f`` exactly. Or: ``a`` is a subtype of ``f``.
5. Integral conversion match: ``a`` is convertible to ``f`` and ``f`` and ``a``
is some integer or floating point type.
6. Conversion match: ``a`` is convertible to ``f``, possibly via a user
defined ``converter``.
These matching categories have a priority: An exact match is better than a
literal match and that is better than a generic match etc. In the following
``count(p, m)`` counts the number of matches of the matching category ``m``
for the routine ``p``.
A routine ``p`` matches better than a routine ``q`` if the following
algorithm returns true::
for each matching category m in ["exact match", "literal match",
"generic match", "subtype match",
"integral match", "conversion match"]:
if count(p, m) > count(q, m): return true
elif count(p, m) == count(q, m):
discard "continue with next category m"
else:
return false
return "ambiguous"
Some examples:
.. code-block:: nim
proc takesInt(x: int) = echo "int"
proc takesInt[T](x: T) = echo "T"
proc takesInt(x: int16) = echo "int16"
takesInt(4) # "int"
var x: int32
takesInt(x) # "T"
var y: int16
takesInt(y) # "int16"
var z: range[0..4] = 0
takesInt(z) # "T"
If this algorithm returns "ambiguous" further disambiguation is performed:
If the argument ``a`` matches both the parameter type ``f`` of ``p``
and ``g`` of ``q`` via a subtyping relation, the inheritance depth is taken
into account:
.. code-block:: nim
type
A = object of RootObj
B = object of A
C = object of B
proc p(obj: A) =
echo "A"
proc p(obj: B) =
echo "B"
var c = C()
# not ambiguous, calls 'B', not 'A' since B is a subtype of A
# but not vice versa:
p(c)
proc pp(obj: A, obj2: B) = echo "A B"
proc pp(obj: B, obj2: A) = echo "B A"
# but this is ambiguous:
pp(c, c)
Likewise for generic matches the most specialized generic type (that still
matches) is preferred:
.. code-block:: nim
proc gen[T](x: ref ref T) = echo "ref ref T"
proc gen[T](x: ref T) = echo "ref T"
proc gen[T](x: T) = echo "T"
var ri: ref int
gen(ri) # "ref T"
Overloading based on 'var T'
----------------------------
If the formal parameter ``f`` is of type ``var T`` in addition to the ordinary
type checking, the argument is checked to be an `l-value`:idx:. ``var T``
matches better than just ``T`` then.
.. code-block:: nim
proc sayHi(x: int): string =
# matches a non-var int
result = $x
proc sayHi(x: var int): string =
# matches a var int
result = $(x + 10)
proc sayHello(x: int) =
var m = x # a mutable version of x
echo sayHi(x) # matches the non-var version of sayHi
echo sayHi(m) # matches the var version of sayHi
sayHello(3) # 3
# 13
Automatic dereferencing
-----------------------
If the `experimental mode <#pragmas-experimental-pragma>`_ is active and no other match
is found, the first argument ``a`` is dereferenced automatically if it's a
pointer type and overloading resolution is tried with ``a[]`` instead.
Automatic self insertions
-------------------------
Starting with version 0.14 of the language, Nim supports ``field`` as a
shortcut for ``self.field`` comparable to the `this`:idx: keyword in Java
or C++. This feature has to be explicitly enabled via a ``{.this: self.}``
statement pragma. This pragma is active for the rest of the module:
.. code-block:: nim
type
Parent = object of RootObj
parentField: int
Child = object of Parent
childField: int
{.this: self.}
proc sumFields(self: Child): int =
result = parentField + childField
# is rewritten to:
# result = self.parentField + self.childField
Instead of ``self`` any other identifier can be used too, but
``{.this: self.}`` will become the default directive for the whole language
eventually.
In addition to fields, routine applications are also rewritten, but only
if no other interpretation of the call is possible:
.. code-block:: nim
proc test(self: Child) =
echo childField, " ", sumFields()
# is rewritten to:
echo self.childField, " ", sumFields(self)
# but NOT rewritten to:
echo self, self.childField, " ", sumFields(self)
Lazy type resolution for untyped
--------------------------------
**Note**: An `unresolved`:idx: expression is an expression for which no symbol
lookups and no type checking have been performed.
Since templates and macros that are not declared as ``immediate`` participate
in overloading resolution it's essential to have a way to pass unresolved
expressions to a template or macro. This is what the meta-type ``untyped``
accomplishes:
.. code-block:: nim
template rem(x: untyped) = discard
rem unresolvedExpression(undeclaredIdentifier)
A parameter of type ``untyped`` always matches any argument (as long as there is
any argument passed to it).
But one has to watch out because other overloads might trigger the
argument's resolution:
.. code-block:: nim
template rem(x: untyped) = discard
proc rem[T](x: T) = discard
# undeclared identifier: 'unresolvedExpression'
rem unresolvedExpression(undeclaredIdentifier)
``untyped`` and ``varargs[untyped]`` are the only metatype that are lazy in this sense, the other
metatypes ``typed`` and ``typedesc`` are not lazy.
Varargs matching
----------------
See `Varargs`_.