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`_.