==================================
Nim Destructors and Move Semantics
==================================

:Authors: Andreas Rumpf
:Version: |nimversion|

.. default-role:: code
.. include:: rstcommon.rst
.. contents::


About this document
===================

This document describes the upcoming Nim runtime which does
not use classical GC algorithms anymore but is based on destructors and
move semantics. The new runtime's advantages are that Nim programs become
oblivious to the involved heap sizes and programs are easier to write to make
effective use of multi-core machines. As a nice bonus, files and sockets and
the like will not require manual `close` calls anymore.

This document aims to be a precise specification about how
move semantics and destructors work in Nim.


Motivating example
==================

With the language mechanisms described here, a custom seq could be
written as:

  ```nim
  type
    myseq*[T] = object
      len, cap: int
      data: ptr UncheckedArray[T]

  proc `=destroy`*[T](x: var myseq[T]) =
    if x.data != nil:
      for i in 0..<x.len: `=destroy`(x.data[i])
      dealloc(x.data)

  proc `=trace`[T](x: var myseq[T]; env: pointer) =
    # `=trace` allows the cycle collector `--mm:orc`
    # to understand how to trace the object graph.
    if x.data != nil:
      for i in 0..<x.len: `=trace`(x.data[i], env)

  proc `=copy`*[T](a: var myseq[T]; b: myseq[T]) =
    # do nothing for self-assignments:
    if a.data == b.data: return
    `=destroy`(a)
    wasMoved(a)
    a.len = b.len
    a.cap = b.cap
    if b.data != nil:
      a.data = cast[typeof(a.data)](alloc(a.cap * sizeof(T)))
      for i in 0..<a.len:
        a.data[i] = b.data[i]

  proc `=sink`*[T](a: var myseq[T]; b: myseq[T]) =
    # move assignment, optional.
    # Compiler is using `=destroy` and `copyMem` when not provided
    `=destroy`(a)
    wasMoved(a)
    a.len = b.len
    a.cap = b.cap
    a.data = b.data

  proc add*[T](x: var myseq[T]; y: sink T) =
    if x.len >= x.cap:
      x.cap = max(x.len + 1, x.cap * 2)
      x.data = cast[typeof(x.data)](realloc(x.data, x.cap * sizeof(T)))
    x.data[x.len] = y
    inc x.len

  proc `[]`*[T](x: myseq[T]; i: Natural): lent T =
    assert i < x.len
    x.data[i]

  proc `[]=`*[T](x: var myseq[T]; i: Natural; y: sink T) =
    assert i < x.len
    x.data[i] = y

  proc createSeq*[T](elems: varargs[T]): myseq[T] =
    result.cap = elems.len
    result.len = elems.len
    result.data = cast[typeof(result.data)](alloc(result.cap * sizeof(T)))
    for i in 0..<result.len: result.data[i] = elems[i]

  proc len*[T](x: myseq[T]): int {.inline.} = x.len
  ```


Lifetime-tracking hooks
=======================

The memory management for Nim's standard `string` and `seq` types as
well as other standard collections is performed via so-called
"Lifetime-tracking hooks", which are particular [type bound operators](
manual.html#procedures-type-bound-operators).

There are 4 different hooks for each (generic or concrete) object type `T` (`T` can also be a
`distinct` type) that are called implicitly by the compiler.

(Note: The word "hook" here does not imply any kind of dynamic binding
or runtime indirections, the implicit calls are statically bound and
potentially inlined.)


`=destroy` hook
---------------

A `=destroy` hook frees the object's associated memory and releases
other associated resources. Variables are destroyed via this hook when
they go out of scope or when the routine they were declared in is about
to return.

The prototype of this hook for a type `T` needs to be:

  ```nim
  proc `=destroy`(x: var T)
  ```

The general pattern in `=destroy` looks like:

  ```nim
  proc `=destroy`(x: var T) =
    # first check if 'x' was moved to somewhere else:
    if x.field != nil:
      freeResourc<style>pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */</style><div class="highlight"><pre><span></span><span class="k">discard</span><span class="w"> </span><span class="s2">&quot;&quot;&quot;</span>
<span class="s">  targets: &quot;c cpp js&quot;</span>
<span class="s">  ccodecheck: &quot;&#39;HELLO&#39;&quot;</span>
<span class="s">  action: compile</span>
<span class="s2">&quot;&quot;&quot;</span>

<span class="k">when</span><span class="w"> </span><span class="n">defined</span><span class="p">(</span><span class="n">js</span><span class="p">):</span>
<span class="w">  </span><span class="kd">var</span><span class="w"> </span><span class="n">foo</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">proc</span><span class="p">():</span><span class="w"> </span><span class="n">void</span><span class="sx">{.codegenDecl</span>:<span class="w"> </span><span class="sx">&quot;/*HELLO*/function</span><span class="w"> </span><span class="sx">$2($3)&quot;.} =</span>
<span class="sx">    echo</span><span class="w"> </span><span class="sx">&quot;baa&quot;</span>
<span class="sx">else</span>:
<span class="w">  </span><span class="sx">var</span><span class="w"> </span><span class="sx">foo</span><span class="w"> </span><span class="sx">= proc(): void{.codegenDecl</span>:<span class="w"> </span><span class="sx">&quot;/*HELLO*/$1</span><span class="w"> </span><span class="sx">$2</span><span class="w"> </span><span class="sx">$3&quot;.} =</span>
<span class="sx">    echo</span><span class="w"> </span><span class="sx">&quot;baa&quot;</span>

<span class="sx">foo()</span>
</pre></div>
</code></pre></td></tr></table>
</div> <!-- class=content -->
<div class='footer'>generated by <a href='https://git.causal.agency/cgit-pink/about/'>cgit-pink 1.4.1-2-gfad0</a> (<a href='https://git-scm.com/'>git 2.36.2.497.gbbea4dcf42</a>) at 2025-02-13 23:36:49 +0000</div>
</div> <!-- id=cgit -->
</body>
</html>
nce algorithm are currently undocumented.


Rewrite rules
=============

**Note**: There are two different allowed implementation strategies:

1. The produced `finally` section can be a single section that is wrapped
   around the complete routine body.
2. The produced `finally` section is wrapped around the enclosing scope.

The current implementation follows strategy (2). This means that resources are
destroyed at the scope exit.

::

  var x: T; stmts
  ---------------             (destroy-var)
  var x: T; try stmts
  finally: `=destroy`(x)


  g(f(...))
  ------------------------    (nested-function-call)
  g(let tmp;
  bitwiseCopy tmp, f(...);
  tmp)
  finally: `=destroy`(tmp)


  x = f(...)
  ------------------------    (function-sink)
  `=sink`(x, f(...))


  x = lastReadOf z
  ------------------          (move-optimization)
  `=sink`(x, z)
  wasMoved(z)


  v = v
  ------------------   (self-assignment-removal)
  discard "nop"


  x = y
  ------------------          (copy)
  `=copy`(x, y)


  f_sink(g())
  -----------------------     (call-to-sink)
  f_sink(g())


  f_sink(notLastReadOf y)
  --------------------------     (copy-to-sink)
  (let tmp; `=copy`(tmp, y);
  f_sink(tmp))


  f_sink(lastReadOf y)
  -----------------------     (move-to-sink)
  f_sink(y)
  wasMoved(y)


Object and array construction
=============================

Object and array construction is treated as a function call where the
function has `sink` parameters.


Destructor removal
==================

`wasMoved(x);` followed by a `=destroy(x)` operation cancel each other
out. An implementation is encouraged to exploit this in order to improve
efficiency and code sizes. The current implementation does perform this
optimization.


Self assignments
================

`=sink` in combination with `wasMoved` can handle self-assignments but
it's subtle.

The simple case of `x = x` cannot be turned
into `=sink(x, x); wasMoved(x)` because that would lose `x`'s value.
The solution is that simple self-assignments that consist of

- Symbols: `x = x`
- Field access: `x.f = x.f`
- Array, sequence or string access with indices known at compile-time: `x[0] = x[0]`

are transformed into an empty statement that does nothing.
The compiler is free to optimize further cases.

The complex case looks like a variant of `x = f(x)`, we consider
`x = select(rand() < 0.5, x, y)` here:


  ```nim
  proc select(cond: bool; a, b: sink string): string =
    if cond:
      result = a # moves a into result
    else:
      result = b # moves b into result

  proc main =
    var x = "abc"
    var y = "xyz"
    # possible self-assignment:
    x = select(true, x, y)
  ```

Is transformed into:

  ```nim
  proc select(cond: bool; a, b: sink string): string =
    try:
      if cond:
        `=sink`(result, a)
        wasMoved(a)
      else:
        `=sink`(result, b)
        wasMoved(b)
    finally:
      `=destroy`(b)
      `=destroy`(a)

  proc main =
    var
      x: string
      y: string
    try:
      `=sink`(x, "abc")
      `=sink`(y, "xyz")
      `=sink`(x, select(true,
        let blitTmp = x
        wasMoved(x)
        blitTmp,
        let blitTmp = y
        wasMoved(y)
        blitTmp))
      echo [x]
    finally:
      `=destroy`(y)
      `=destroy`(x)
  ```

As can be manually verified, this transformation is correct for
self-assignments.


Lent type
=========

`proc p(x: sink T)` means that the proc `p` takes ownership of `x`.
To eliminate even more creation/copy <-> destruction pairs, a proc's return
type can be annotated as `lent T`. This is useful for "getter" accessors
that seek to allow an immutable view into a container.

The `sink` and `lent` annotations allow us to remove most (if not all)
superfluous copies and destructions.

`lent T` is like `var T` a hidden pointer. It is proven by the compiler
that the pointer does not outlive its origin. No destructor call is injected
for expressions of type `lent T` or of type `var T`.


  ```nim
  type
    Tree = object
      kids: seq[Tree]

  proc construct(kids: sink seq[Tree]): Tree =
    result = Tree(kids: kids)
    # converted into:
    `=sink`(result.kids, kids); wasMoved(kids)
    `=destroy`(kids)

  proc `[]`*(x: Tree; i: int): lent Tree =
    result = x.kids[i]
    # borrows from 'x', this is transformed into:
    result = addr x.kids[i]
    # This means 'lent' is like 'var T' a hidden pointer.
    # Unlike 'var' this hidden pointer cannot be used to mutate the object.

  iterator children*(t: Tree): lent Tree =
    for x in t.kids: yield x

  proc main =
    # everything turned into moves:
    let t = construct(@[construct(@[]), construct(@[])])
    echo t[0] # accessor does not copy the element!
  ```


The cursor pragma
=================

Under the `--mm:arc|orc`:option: modes Nim's `ref` type is implemented
via the same runtime "hooks" and thus via reference counting.
This means that cyclic structures cannot be freed
immediately (`--mm:orc`:option: ships with a cycle collector).
With the `cursor` pragma one can break up cycles declaratively:

  ```nim
  type
    Node = ref object
      left: Node # owning ref
      right {.cursor.}: Node # non-owning ref
  ```

But please notice that this is not C++'s weak_ptr, it means the right field is not
involved in the reference counting, it is a raw pointer without runtime checks.

Automatic reference counting also has the disadvantage that it introduces overhead
when iterating over linked structures. The `cursor` pragma can also be used
to avoid this overhead:

  ```nim
  var it {.cursor.} = listRoot
  while it != nil:
    use(it)
    it = it.next
  ```

In fact, `cursor` more generally prevents object construction/destruction pairs
and so can also be useful in other contexts. The alternative solution would be to
use raw pointers (`ptr`) instead which is more cumbersome and also more dangerous
for Nim's evolution: Later on, the compiler can try to prove `cursor` pragmas
to be safe, but for `ptr` the compiler has to remain silent about possible
problems.


Cursor inference / copy elision
===============================

The current implementation also performs `cursor` inference. Cursor inference is
a form of copy elision.

To see how and when we can do that, think about this question: In `dest = src` when
do we really have to *materialize* the full copy? - Only if `dest` or `src` are mutated
afterward. If `dest` is a local variable that is simple to analyze. And if `src` is a
location derived from a formal parameter, we also know it is not mutated! In other
words, we do a compile-time copy-on-write analysis.

This means that "borrowed" views can be written naturally and without explicit pointer
indirections:

  ```nim
  proc main(tab: Table[string, string]) =
    let v = tab["key"] # inferred as cursor because 'tab' is not mutated.
    # no copy into 'v', no destruction of 'v'.
    use(v)
    useItAgain(v)
  ```


Hook lifting
============

The hooks of a tuple type `(A, B, ...)` are generated by lifting the
hooks of the involved types `A`, `B`, ... to the tuple type. In
other words, a copy `x = y` is implemented
as `x[0] = y[0]; x[1] = y[1]; ...`, likewise for `=sink` and `=destroy`.

Other value-based compound types like `object` and `array` are handled
correspondingly. For `object` however, the compiler-generated hooks
can be overridden. This can also be important to use an alternative traversal
of the involved data structure that is more efficient or in order to avoid
deep recursions.



Hook generation
===============

The ability to override a hook leads to a phase ordering problem:

  ```nim
  type
    Foo[T] = object

  proc main =
    var f: Foo[int]
    # error: destructor for 'f' called here before
    # it was seen in this module.

  proc `=destroy`[T](f: var Foo[T]) =
    discard
  ```

The solution is to define ``proc `=destroy`[T](f: var Foo[T])`` before
it is used. The compiler generates implicit
hooks for all types in *strategic places* so that an explicitly provided
hook that comes too "late" can be detected reliably. These *strategic places*
have been derived from the rewrite rules and are as follows:

- In the construct `let/var x = ...` (var/let binding)
  hooks are generated for `typeof(x)`.
- In `x = ...` (assignment) hooks are generated for `typeof(x)`.
- In `f(...)` (function call) hooks are generated for `typeof(f(...))`.
- For every sink parameter `x: sink T` the hooks are generated
  for `typeof(x)`.


nodestroy pragma
================

The experimental `nodestroy`:idx: pragma inhibits hook injections. This can be
used to specialize the object traversal in order to avoid deep recursions:


  ```nim
  type Node = ref object
    x, y: int32
    left, right: Node

  type Tree = object
    root: Node

  proc `=destroy`(t: var Tree) {.nodestroy.} =
    # use an explicit stack so that we do not get stack overflows:
    var s: seq[Node] = @[t.root]
    while s.len > 0:
      let x = s.pop
      if x.left != nil: s.add(x.left)
      if x.right != nil: s.add(x.right)
      # free the memory explicit:
      dispose(x)
    # notice how even the destructor for 's' is not called implicitly
    # anymore thanks to .nodestroy, so we have to call it on our own:
    `=destroy`(s)
  ```


As can be seen from the example, this solution is hardly sufficient and
should eventually be replaced by a better solution.


Copy on write
=============

String literals are implemented as "copy on write".
When assigning a string literal to a variable, a copy of the literal won't be created.
Instead the variable simply points to the literal.
The literal is shared between different variables which are pointing to it.
The copy operation is deferred until the first write.

For example:

  ```nim
  var x = "abc"  # no copy
  var y = x      # no copy
  y[0] = 'h'     # copy
  ```

The abstraction fails for `addr x` because whether the address is going to be used for mutations is unknown.
`prepareMutation` needs to be called before the "address of" operation. For example:

  ```nim
  var x = "abc"
  var y = x

  prepareMutation(y)
  moveMem(addr y[0], addr x[0], 3)
  assert y == "abc"
  ```