Generics
========

Generics are Nim's means to parametrize procs, iterators or types with
`type parameters`:idx:. Depending on context, the brackets are used either to
introduce type parameters or to instantiate a generic proc, iterator or type.

The following example shows a generic binary tree can be modelled:

.. code-block:: nim
  type
    BinaryTreeObj[T] = object    # BinaryTreeObj is a generic type with
                                 # with generic param ``T``
      le, ri: BinaryTree[T]      # left and right subtrees; may be nil
      data: T                    # the data stored in a node
    BinaryTree[T] = ref BinaryTreeObj[T] # a shorthand for notational convenience

  proc newNode[T](data: T): BinaryTree[T] = # constructor for a node
    new(result)
    result.data = data

  proc add[T](root: var BinaryTree[T], n: BinaryTree[T]) =
    if root == nil:
      root = n
    else:
      var it = root
      while it != nil:
        var c = cmp(it.data, n.data) # compare the data items; uses
                                     # the generic ``cmp`` proc that works for
                                     # any type that has a ``==`` and ``<``
                                     # operator
        if c < 0:
          if it.le == nil:
            it.le = n
            return
          it = it.le
        else:
          if it.ri == nil:
            it.ri = n
            return
          it = it.ri

  iterator inorder[T](root: BinaryTree[T]): T =
    # inorder traversal of a binary tree
    # recursive iterators are not yet implemented, so this does not work in
    # the current compiler!
    if root.le != nil: yield inorder(root.le)
    yield root.data
    if root.ri != nil: yield inorder(root.ri)

  var
    root: BinaryTree[string]  # instantiate a BinaryTree with the type string
  add(root, newNode("hallo")) # instantiates generic procs ``newNode`` and
  add(root, newNode("world")) # ``add``
  for str in inorder(root):
    writeln(stdout, str)


Is operator
-----------

The ``is`` operator checks for type equivalence at compile time. It is
therefore very useful for type specialization within generic code:

.. code-block:: nim
  type
    Table[Key, Value] = object
      keys: seq[Key]
      values: seq[Value]
      when not (Key is string): # nil value for strings used for optimization
        deletedKeys: seq[bool]


Type operator
-------------

The ``type`` (in many other languages called `typeof`:idx:) operator can
be used to get the type of an expression:

.. code-block:: nim
  var x = 0
  var y: type(x) # y has type int

If ``type`` is used to determine the result type of a proc/iterator/converter
call ``c(X)`` (where ``X`` stands for a possibly empty list of arguments), the
interpretation where ``c`` is an iterator is preferred over the
other interpretations:

.. code-block:: nim
  import strutils

  # strutils contains both a ``split`` proc and iterator, but since an
  # an iterator is the preferred interpretation, `y` has the type ``string``:
  var y: type("a b c".split)


Type Classes
------------

A type class is a special pseudo-type that can be used to match against
types in the context of overload resolution or the ``is`` operator.
Nim supports the following built-in type classes:

==================   ===================================================
type class           matches
==================   ===================================================
``object``           any object type
``tuple``            any tuple type

``enum``             any enumeration
``proc``             any proc type
``ref``              any ``ref`` type
``ptr``              any ``ptr`` type
``var``              any ``var`` type
``distinct``         any distinct type
``array``            any array type
``set``              any set type
``seq``              any seq type
``auto``             any type
==================   ===================================================

Furthermore, every generic type automatically creates a type class of the same
name that will match any instantiation of the generic type.

Type classes can be combined using the standard boolean operators to form
more complex type classes:

.. code-block:: nim
  # create a type class that will match all tuple and object types
  type RecordType = tuple or object

  proc printFields(rec: RecordType) =
    for key, value in fieldPairs(rec):
      echo key, " = ", value

Procedures utilizing type classes in such manner are considered to be
`implicitly generic`:idx:. They will be instantiated once for each unique
combination of param types used within the program.

Nim also allows for type classes and regular types to be specified
as `type constraints`:idx: of the generic type parameter:

.. code-block:: nim
  proc onlyIntOrString[T: int|string](x, y: T) = discard

  onlyIntOrString(450, 616) # valid
  onlyIntOrString(5.0, 0.0) # type mismatch
  onlyIntOrString("xy", 50) # invalid as 'T' cannot be both at the same time

By default, during overload resolution each named type class will bind to
exactly one concrete type. Here is an example taken directly from the system
module to illustrate this:

.. code-block:: nim
  proc `==`*(x, y: tuple): bool =
    ## requires `x` and `y` to be of the same tuple type
    ## generic ``==`` operator for tuples that is lifted from the components
    ## of `x` and `y`.
    result = true
    for a, b in fields(x, y):
      if a != b: result = false

Alternatively, the ``distinct`` type modifier can be applied to the type class
to allow each param matching the type class to bind to a different type.

If a proc param doesn't have a type specified, Nim will use the
``distinct auto`` type class (also known as ``any``):

.. code-block:: nim
  # allow any combination of param types
  proc concat(a, b): string = $a & $b

Procs written with the implicitly generic style will often need to refer to the
type parameters of the matched generic type. They can be easily accessed using
the dot syntax:

.. code-block:: nim
  type Matrix[T, Rows, Columns] = object
    ...

  proc `[]`(m: Matrix, row, col: int): Matrix.T =
    m.data[col * high(Matrix.Columns) + row]

Alternatively, the `type` operator can be used over the proc params for similar
effect when anonymous or distinct type classes are used.

When a generic type is instantiated with a type class instead of a concrete
type, this results in another more specific type class:

.. code-block:: nim
  seq[ref object]  # Any sequence storing references to any object type

  type T1 = auto
  proc foo(s: seq[T1], e: T1)
    # seq[T1] is the same as just `seq`, but T1 will be allowed to bind
    # to a single type, while the signature is being matched

  Matrix[Ordinal] # Any Matrix instantiation using integer values

As seen in the previous example, in such instantiations, it's not necessary to
supply all type parameters of the generic type, because any missing ones will
be inferred to have the equivalent of the `any` type class and thus they will
match anything without discrimination.


Concepts
--------

**Note**: Concepts are still in development.

Concepts, also known as "user-defined type classes", are used to specify an
arbitrary set of requirements that the matched type must satisfy.

Concepts are written in the following form:

.. code-block:: nim
  type
    Comparable = concept x, y
      (x < y) is bool

    Container[T] = concept c
      c.len is Ordinal
      items(c) is iterator
      for value in c:
        type(value) is T

The concept is a match if:

a) all of the expressions within the body can be compiled for the tested type
b) all statically evaluatable boolean expressions in the body must be true

The identifiers following the ``concept`` keyword represent instances of the
currently matched type. These instances can act both as variables of the type,
when used in contexts where a value is expected, and as the type itself when
used in contexts where a type is expected.

Please note that the ``is`` operator allows one to easily verify the precise
type signatures of the required operations, but since type inference and
default parameters are still applied in the provided block, it's also possible
to encode usage protocols that do not reveal implementation details.

As a special rule providing further convenience when writing concepts, any
type value appearing in a callable expression will be treated as a variable of
the designated type for overload resolution purposes, unless the type value was
passed in its explicit ``typedesc[T]`` form:

.. code-block:: nim
  type
    OutputStream = concept s
      write(var s, string)

Much like generics, concepts are instantiated exactly
once for each tested type and any static code included within them is also
executed once.


Symbol lookup in generics
-------------------------

The symbol binding rules in generics are slightly subtle: There are "open" and
"closed" symbols. A "closed" symbol cannot be re-bound in the instantiation
context, an "open" symbol can. Per default overloaded symbols are open
and every other symbol is closed.

Open symbols are looked up in two different contexts: Both the context
at definition and the context at instantiation are considered:

.. code-block:: nim
  type
    Index = distinct int

  proc `==` (a, b: Index): bool {.borrow.}

  var a = (0, 0.Index)
  var b = (0, 0.Index)

  echo a == b # works!

In the example the generic ``==`` for tuples (as defined in the system module)
uses the ``==`` operators of the tuple's components. However, the ``==`` for
the ``Index`` type is defined *after* the ``==`` for tuples; yet the example
compiles as the instantiation takes the currently defined symbols into account
too.

A symbol can be forced to be open by a `mixin`:idx: declaration:

.. code-block:: nim
  proc create*[T](): ref T =
    # there is no overloaded 'init' here, so we need to state that it's an
    # open symbol explicitly:
    mixin init
    new result
    init result


Bind statement
--------------

The ``bind`` statement is the counterpart to the ``mixin`` statement. It
can be used to explicitly declare identifiers that should be bound early (i.e.
the identifiers should be looked up in the scope of the template/generic
definition):

.. code-block:: nim
  # Module A
  var
    lastId = 0

  template genId*: expr =
    bind lastId
    inc(lastId)
    lastId

.. code-block:: nim
  # Module B
  import A

  echo genId()

But a ``bind`` is rarely useful because symbol binding from the definition
scope is the default.