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):
    writeLine(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
``any``              distinct auto (see below)
==================   ===================================================

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. We call such type classes `bind once`:idx: types.
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. Such
type classes are called `bind many`:idx: types.

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

    Stack[T] = concept s, var v
      s.pop() is T
      v.push(T)

      s.len is Ordinal

      for value in s:
        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 evaluable boolean expressions in the body must be true

The identifiers following the ``concept`` keyword represent instances of the
currently matched type. You can apply any of the standard type modifiers such
as ``var``, ``ref``, ``ptr`` and ``static`` to denote a more specific type of
instance. You can also apply the `type` modifier to create a named instance of
the type itself:

.. code-block:: nim
  type
    MyConcept = concept x, var v, ref r, ptr p, static s, type T
      ...

Within the concept body, types can appear in positions where ordinary values
and parameters are expected. This provides a more convenient way to check for
the presence of callable symbols with specific signatures:

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

In order to check for symbols accepting ``typedesc`` params, you must prefix
the type with an explicit ``type`` modifier. The named instance of the type,
following the ``concept`` keyword is also considered an explicit ``typedesc``
value that will be matched only as a type.

.. code-block:: nim
  type
    # Let's imagine a user-defined casting framework with operators
    # such as `val.to(string)` and `val.to(JSonValue)`. We can test
    # for these with the following concept:
    MyCastables = concept x
      x.to(type string)
      x.to(type JSonValue)

    # Let's define a couple of concepts, known from Algebra:
    AdditiveMonoid* = concept x, y, type T
      x + y is T
      T.zero is T # require a proc such as `int.zero` or 'Position.zero'

    AdditiveGroup* = concept x, y, type T
      x is AdditiveMonoid
      -x is T
      x - y is T

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 concept body, it's also possible
to describe usage protocols that do not reveal implementation details.

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


Concept diagnostics
-------------------

By default, the compiler will report the matching errors in concepts only when
no other overload can be selected and a normal compilation error is produced.
When you need to understand why the compiler is not matching a particular
concept and, as a result, a wrong overload is selected, you can apply the
``explain`` pragma to either the concept body or a particular call-site.

.. code-block:: nim
  type
    MyConcept {.explain.} = concept ...

  overloadedProc(x, y, z) {.explain.}

This will provide Hints in the compiler output either every time the concept is
not matched or only on the particular call-site.


Generic concepts and type binding rules
---------------------------------------

The concept types can be parametric just like the regular generic types:

.. code-block:: nim
  ### matrixalgo.nim
  
  import typetraits

  type
    AnyMatrix*[R, C: static[int]; T] = concept m, var mvar, type M
      M.ValueType is T
      M.Rows == R
      M.Cols == C

      m[int, int] is T
      mvar[int, int] = T

      type TransposedType = stripGenericParams(M)[C, R, T]

    AnySquareMatrix*[N: static[int], T] = AnyMatrix[N, N, T]

    AnyTransform3D* = AnyMatrix[4, 4, float]

  proc transposed*(m: AnyMatrix): m.TransposedType =
    for r in 0 .. <m.R:
      for c in 0 .. <m.C:
        result[r, c] = m[c, r]

  proc determinant*(m: AnySquareMatrix): int =
    ...

  proc setPerspectiveProjection*(m: AnyTransform3D) =
    ...

  --------------
  ### matrix.nim

  type
    Matrix*[M, N: static[int]; T] = object
      data: array[M*N, T]

  proc `[]`*(M: Matrix; m, n: int): M.T =
    M.data[m * M.N + n]

  proc `[]=`*(M: var Matrix; m, n: int; v: M.T) =
    M.data[m * M.N + n] = v

  # Adapt the Matrix type to the concept's requirements
  template Rows*(M: type Matrix): expr = M.M
  template Cols*(M: type Matrix): expr = M.N
  template ValueType*(M: type Matrix): typedesc = M.T
  
  -------------
  ### usage.nim

  import matrix, matrixalgo

  var
    m: Matrix[3, 3, int]
    projectionMatrix: Matrix[4, 4, float]

  echo m.transposed.determinant
  setPerspectiveProjection projectionMatrix

When the concept type is matched against a concrete type, the unbound type
parameters are inferred from the body of the concept in a way that closely
resembles the way generic parameters of callable symbols are inferred on
call sites.

Unbound types can appear both as params to calls such as `s.push(T)` and
on the right-hand side of the ``is`` operator in cases such as `x.pop is T`
and `x.data is seq[T]`.

Unbound static params will be inferred from expressions involving the `==`
operator and also when types dependent on them are being matched:

.. code-block:: nim
  type
    MatrixReducer[M, N: static[int]; T] = concept x
      x.reduce(SquareMatrix[N, T]) is array[M, int]

The Nim compiler includes a simple linear equation solver, allowing it to
infer static params in some situations where integer arithmetic is involved.

Just like in regular type classes, Nim discriminates between ``bind once``
and ``bind many`` types when matching the concept. You can add the ``distinct``
modifier to any of the otherwise inferable types to get a type that will be
matched without permanently inferring it. This may be useful when you need
to match several procs accepting the same wide class of types:

.. code-block:: nim
  type
    Enumerable[T] = concept e
      for v in e:
        v is T

  type
    MyConcept = concept o
      # this could be inferred to a type such as Enumerable[int]
      o.foo is distinct Enumerable

      # this could be inferred to a different type such as Enumerable[float]
      o.bar is distinct Enumerable

      # it's also possible to give an alias name to a `bind many` type class
      type Enum = distinct Enumerable
      o.baz is Enum

On the other hand, using ``bind once`` types allows you to test for equivalent
types used in multiple signatures, without actually requiring any concrete
types, thus allowing you to encode implementation-defined types:

.. code-block:: nim
  type
    MyConcept = concept x
      type T1 = auto
      x.foo(T1)
      x.bar(T1) # both procs must accept the same type

      type T2 = seq[SomeNumber]
      x.alpha(T2)
      x.omega(T2) # both procs must accept the same type
                  # and it must be a numeric sequence

As seen in the previous examples, you can refer to generic concepts such as
`Enumerable[T]` just by their short name. Much like the regular generic types,
the concept will be automatically instantiated with the bind once auto type
in the place of each missing generic param.

Please note that generic concepts such as `Enumerable[T]` can be matched
against concrete types such as `string`. Nim doesn't require the concept
type to have the same number of parameters as the type being matched.
If you wish to express a requirement towards the generic parameters of
the matched type, you can use a type mapping operator such as `genericHead`
or `stripGenericParams` within the body of the concept to obtain the
uninstantiated version of the type, which you can then try to instantiate
in any required way. For example, here is how one might define the classic
`Functor` concept from Haskell and then demonstrate that Nim's `Option[T]`
type is an instance of it:

.. code-block:: nim
  import future, typetraits

  type
    Functor[A] = concept f
      type MatchedGenericType = genericHead(f.type)
        # `f` will be a value of a type such as `Option[T]`
        # `MatchedGenericType` will become the `Option` type

      f.val is A
        # The Functor should provide a way to obtain
        # a value stored inside it

      type T = auto
      map(f, A -> T) is MatchedGenericType[T]
        # And it should provide a way to map one instance of
        # the Functor to a instance of a different type, given
        # a suitable `map` operation for the enclosed values

  import options
  echo Option[int] is Functor # prints true


Concept derived values
----------------------

All top level constants or types appearing within the concept body are
accessible through the dot operator in procs where the concept was successfully
matched to a concrete type:

.. code-block:: nim
  type
    DateTime = concept t1, t2, type T
      const Min = T.MinDate
      T.Now is T

      t1 < t2 is bool

      type TimeSpan = type(t1 - t2)
      TimeSpan * int is TimeSpan
      TimeSpan + TimeSpan is TimeSpan

      t1 + TimeSpan is T

  proc eventsJitter(events: Enumerable[DateTime]): float =
    var
      # this variable will have the inferred TimeSpan type for
      # the concrete Date-like value the proc was called with:
      averageInterval: DateTime.TimeSpan

      deviation: float
    ...


Concept refinement
------------------

When the matched type within a concept is directly tested against a different
concept, we say that the outer concept is a refinement of the inner concept and
thus it is more-specific. When both concepts are matched in a call during
overload resolution, Nim will assign a higher precedence to the most specific
one. As an alternative way of defining concept refinements, you can use the
object inheritance syntax involving the ``of`` keyword:

.. code-block:: nim
  type
    Graph = concept g, type G of EqualyComparable, Copyable
      type
        VertexType = G.VertexType
        EdgeType = G.EdgeType

      VertexType is Copyable
      EdgeType is Copyable

      var
        v: VertexType
        e: EdgeType

    IncidendeGraph = concept of Graph
      # symbols such as variables and types from the refined
      # concept are automatically in scope:

      g.source(e) is VertexType
      g.target(e) is VertexType

      g.outgoingEdges(v) is Enumerable[EdgeType]

    BidirectionalGraph = concept g, type G
      # The following will also turn the concept into a refinement when it
      # comes to overload resolution, but it doesn't provide the convenient
      # symbol inheritance
      g is IncidendeGraph

      g.incomingEdges(G.VertexType) is Enumerable[G.EdgeType]

  proc f(g: IncidendeGraph)
  proc f(g: BidirectionalGraph) # this one will be preferred if we pass a type
                                # matching the BidirectionalGraph concept


Converter type classes
----------------------

Concepts can also be used to convert a whole range of types to a single type or
a small set of simpler types. This is achieved with a `return` statement within
the concept body:

.. code-block:: nim
  type
    Stringable = concept x
      $x is string
      return $x

    StringRefValue[CharType] = object
      base: ptr CharType
      len: int

    StringRef = concept x
      # the following would be an overloaded proc for cstring, string, seq and
      # other user-defined types, returning either a StringRefValue[char] or
      # StringRefValue[wchar]
      return makeStringRefValue(x)

  # the varargs param will here be converted to an array of StringRefValues
  # the proc will have only two instantiations for the two character types
  proc log(format: static[string], varargs[StringRef])

  # this proc will allow char and wchar values to be mixed in
  # the same call at the cost of additional instantiations
  # the varargs param will be converted to a tuple
  proc log(format: static[string], varargs[distinct StringRef])


VTable types
------------

Concepts allow Nim to define a great number of algorithms, using only
static polymorphism and without erasing any type information or sacrificing
any execution speed. But when polymorphic collections of objects are required,
the user must use one of the provided type erasure techniques - either common
base types or VTable types.

VTable types are represented as "fat pointers" storing a reference to an
object together with a reference to a table of procs implementing a set of
required operations (the so called vtable).

In contrast to other programming languages, the vtable in Nim is stored
externally to the object, allowing you to create multiple different vtable
views for the same object. Thus, the polymorphism in Nim is unbounded -
any type can implement an unlimited number of protocols or interfaces not
originally envisioned by the type's author.

Any concept type can be turned into a VTable type by using the ``vtref``
or the ``vtptr`` compiler magics. Under the hood, these magics generate
a converter type class, which converts the regular instances of the matching
types to the corresponding VTable type.

.. code-block:: nim
  type
    IntEnumerable = vtref Enumerable[int]

    MyObject = object
      enumerables: seq[IntEnumerable]
      streams: seq[OutputStream.vtref]

  proc addEnumerable(o: var MyObject, e: IntEnumerable) =
    o.enumerables.add e

  proc addStream(o: var MyObject, e: OutputStream.vtref) =
    o.streams.add e

The procs that will be included in the vtable are derived from the concept
body and include all proc calls for which all param types were specified as
concrete types. All such calls should include exactly one param of the type
matched against the concept (not necessarily in the first position), which
will be considered the value bound to the vtable.

Overloads will be created for all captured procs, accepting the vtable type
in the position of the captured underlying object.

Under these rules, it's possible to obtain a vtable type for a concept with
unbound type parameters or one instantiated with metatypes (type classes),
but it will include a smaller number of captured procs. A completely empty
vtable will be reported as an error.

The ``vtref`` magic produces types which can be bound to ``ref`` types and
the ``vtptr`` magic produced types bound to ``ptr`` types.


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*: untyped =
    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.