Borrow Checking in Nim 3.0

57 minutes ago 1

Introduction

Nimony provides memory safety through a simple borrow checking system combined with field-level ownership annotations. Unlike Rust's complex lifetime system, Nimony uses straightforward path-based rules that leverage Nim's existing semantics.

Key principles:

  • Safety by default for value types
  • Simple, teachable rules without lifetime annotations
  • Field-level ownership clarity (.unique and .cursor)
  • Graceful degradation when analysis is uncertain
  • Leverages Nim's value semantics and var keyword

Core Concepts

Borrowing

When you iterate over a collection or take a reference to part of a data structure, you're borrowing from it:

type Data = object items: seq[Item] metadata: Metadata var data: Data for item in mitems(data.items): # You're borrowing from 'data.items' item.value = 10

During the borrow, certain operations on the borrowed path are restricted to ensure safety.

The Witness Path

When you borrow, you establish a witness path - a path expression that must remain stable for the borrow's duration:

for item in mitems(data.items): # Witness path: 'data.items' # This path witnesses that the structure stays valid

Simple Path Expressions

Nimony only allows borrowing from simple paths - expressions that are locally analyzable:

# ✅ Simple paths (borrowable): data data.items data.nested.field data.items[i] ptr[] # Pointer with dereference at the end # ❌ Complex paths (not directly borrowable): ptr[].items # Dereference in the middle getPtr()[].field # Function call in path table[key].items # Dynamic lookup

Why? Simple paths let the compiler verify safety locally without global analysis.

Ownership Annotations

Before diving into borrow checking rules, let's understand how Nimony tracks ownership through field-level annotations.

unique Fields - Exclusive Ownership

A unique field indicates exclusive ownership of a ref:

type Tree = ref object left {.unique.}: Node # This field exclusively owns the left subtree right {.unique.}: Node # This field exclusively owns the right subtree Node = ref object next {.unique.}: Node # Exclusively owns the next node data: int

Semantics:

  • Assignment moves ownership (old value is destroyed)
  • No other field or variable can alias this ref
  • Participates in destruction (destructor recursively destroys unique fields)

Creating unique refs:

let node = new(Node) # new() produces a unique ref node.next = new(Node) # Assigning unique to unique field proc createTree(): Tree {.unique.} = # {.unique.} pragma indicates function returns unique ownership result = new(Tree) result.left = new(Node) result.right = new(Node)

.cursor Fields - Non-Owning References

A .cursor field is a non-owning reference (borrowed view):

type List = ref object head {.unique.}: Node Node = ref object next {.unique.}: Node prev {.cursor.}: Node # Back pointer - does NOT own data: int

Semantics:

  • Does not participate in destruction
  • No RC operations (not an owner)
  • Must point into a structure kept alive elsewhere
  • Used for back-references, cached views, etc.

Regular ref Fields - Shared Ownership

A regular ref field without annotations means shared ownership:

type Cache = ref object fallback: Node # Shared reference (might be aliased)

Semantics:

  • RC increment on assignment
  • RC decrement on destruction
  • Can be aliased
  • May participate in cycles (cycle collector handles this)

Acyclicity Benefits

When all ref fields in a type are unique or .cursor, the structure is provably acyclic:

type Tree = ref object left {.unique.}: Node right {.unique.}: Node Node = ref object left {.unique.}: Node right {.unique.}: Node parent {.cursor.}: Node # Non-owning back reference

Benefits:

  • Simple, fast destruction (no cycle collector)
  • Guaranteed no memory cycles
  • Borrow checking is sound through all paths

Any regular ref field means potentially cyclic:

type Graph = ref object nodes: seq[Node] # Shared refs - might have cycles Node = ref object neighbors: seq[Node] # Cycles possible

Composition Summary

Field Type Ownership RC Cycles Use Case
{.unique.}: ref T Exclusive Yes (might be optimized later) No Trees, owned children
{.cursor.}: ref T None No No* Back pointers, views
ref T Shared Yes Yes Graphs, shared structures

*cursor fields don't create ownership cycles

Borrow Checking Rules

Rule 1: Prefix Exclusion

During a borrow, you cannot mutate the borrowed path or any of its prefixes:

for item in mitems(data.items): # ❌ Forbidden: data = newData # Prefix of 'data.items' data.items = @[] # The borrowed path itself # ✅ Allowed: data.metadata = x # Disjoint sibling item.value = 10 # Mutation through the borrow (the point!)

The rule: If you borrow from a.b.c, you cannot mutate a, a.b, or a.b.c.

Rule 2: Read-Only Access is Allowed

Read-only access to borrowed paths is fine:

for item in mitems(data.items): echo data.name # ✅ Read-only process(data) # ✅ Non-var parameter (gets copy) let n = data.items.len # ✅ Reading # ❌ Still forbidden: mutate(var data) # var parameter data.items = @[] # Direct mutation

Rule 3: Disjoint Siblings Don't Conflict

Fields at the same level can be independently borrowed:

for row in mitems(data.rows): for col in mitems(data.cols): # Both borrows active simultaneously - they're disjoint! row.value = compute(col)

Rule 4: Nested Borrowing Works Naturally

for item in mitems(data.items): # Borrow: data.items for part in mitems(item.parts): # Borrow: item.parts (from loop variable) # Works! Prefix exclusion prevents issues part.active = true

The borrow from item.parts makes item immutable (prefix exclusion), which is exactly what we need for safety.

Paths with Dereferences

The Problem with Ref Derefs

Paths that dereference through ref types in the middle create aliasing concerns:

type App = ref object users: seq[User] var app: App # This path has a deref: app -> app[] -> app[].users for user in mitems(app.users): # ❌ Error: path contains ref deref user.process()

Why is this problematic? The compiler can't prove that app won't be reassigned or aliased during the borrow. Even though app.users can't be mutated (borrow checking prevents it), app itself could change.

The unchecked Template

For simple ref derefs where you know the ref is stable, use unchecked:

template unchecked(path: typed): untyped = (addr path)[] # Usage: for user in mitems(unchecked app.users): # You assert: app won't change during iteration user.process()

What unchecked means:

  • You bypass borrow checking for the ref deref
  • Uses the addr escape hatch explicitly
  • Your responsibility to ensure safety
  • One word to add - minor inconvenience for ref-heavy code

Safe paths don't need unchecked:

type Data = object # Value type items: seq[Item] var data: Data for item in mitems(data.items): # ✅ No deref, fully checked item.process() # Paths through unique fields are also safe: type Tree = ref object nodes: unique NodeList var tree = new(Tree) for node in mitems(tree.nodes.items): # ✅ unique prevents aliasing node.process()

The with Statement

For truly complex paths or when you need to mutate the parent during iteration, use with to safely move the data temporarily:

# Template (user-level code): template with(path: typed, name: untyped, body: untyped) = block: var name = move(path) defer: path = move(name) body # Usage for complex paths: with table[key].items as items: for item in mitems(items): complexOperation() # items automatically moved back # Usage when mutating parent: with data.items as items: for item in mitems(items): data.reconfigure() # OK: items was moved out

Cost: Two pointer swaps (O(1)), not a full copy!

Compare to other languages:

  • Rust: Must clone the entire collection (O(n))
  • C++: Easy but unsafe (iterator invalidation)
  • Nimony: Move temporarily (O(1) and safe)

When to Use Which

# Value types - just works: var data: Data for x in mitems(data.items): process(x) # Unique ref fields - just works: var tree: Tree for x in mitems(tree.nodes.items): process(x) # Shared ref - use unchecked: var app: App for x in mitems(unchecked app.users): process(x) # Complex path - use with: with table[key].items as items: for x in mitems(items): process(x) # Need to mutate parent - use with: with data.items as items: for x in mitems(items): data = reconfigure() # Safe: items was moved

Complete Examples

Example 1: Value Type Iteration (Always Safe)

type Config = object users: seq[User] settings: Settings var config: Config for user in mitems(config.users): user.active = true # ✅ Mutating through borrow echo config.settings.timeout # ✅ Reading disjoint field config.settings.updated = now() # ✅ Mutating disjoint field

Example 2: Tree with Unique Fields

type Tree = ref object root {.unique.}: Node Node = ref object left {.unique.}: Node right {.unique.}: Node parent: Node {.cursor.} data: int proc buildTree(): Tree {.unique.} = result = new(Tree) result.root = new(Node) result.root.data = 1 result.root.left = new(Node) result.root.left.parent = result.root # Cursor back-ref result.root.right = new(Node) result.root.right.parent = result.root # Safe iteration through unique path: var tree = buildTree() for node in mitems(tree.root.children): node.data = compute(node.parent.data) # ✅ All safe!

Example 3: Ref-Heavy Code with unchecked

type App = ref object users: seq[User] config: Config var app = new(App) app.users = @[User(name: "Alice"), User(name: "Bob")] # Need unchecked for ref deref: for user in mitems(unchecked app.users): user.active = true echo app.config.version # ✅ Disjoint field access OK

Example 4: Complex Path with with

proc processCache(table: Table[string, Data]) = with table["key"].entries as entries: for entry in mitems(entries): entry.lastAccess = now() callUnknownFunc() # OK: entries was moved out

Example 5: Nested Iteration

type Matrix = object rows: seq[Row] cols: seq[Col] var matrix: Matrix for row in mitems(matrix.rows): for col in mitems(matrix.cols): # Both borrows active, disjoint paths row.data[col.index] = compute(row, col)

Comparison to Rust

Aspect Rust Nimony
Ownership tracking Type-level (Box<T>, Rc<T>) Field-level (unique, .cursor)
Lifetime annotations Required in signatures None
Nested iteration Complex lifetime management Just works
Mental model Ownership + lifetimes Path prefix exclusion + field ownership
Function analysis Often needed Black box (signature sufficient)
Ref-heavy code Fight borrow checker unchecked when needed
Escape hatch .clone() (expensive O(n)) with (cheap O(1) move)
Acyclicity Manual (no cycles in safe code) Automatic (unique/.cursor fields)
Learning curve Steep Gentle

Teaching Guide

For Beginners

Step 1: Understand the basic borrow rule:

"When you borrow from a.b.c, you can't change a, a.b, or a.b.c. You can change other fields like a.other or a.b.other."

for x in mitems(data.items): # data.items is borrowed, so: data.items = @[] # ❌ Can't change it data = newData # ❌ Can't change its parent data.other = 5 # ✅ Can change siblings

Step 2: Value types just work:

type Data = object # Value type items: seq[Item] var data: Data for item in mitems(data.items): # ✅ Always safe item.process()

Step 3: Ref types need unchecked:

type App = ref object # Ref type users: seq[User] var app: App for user in mitems(unchecked app.users): # Need unchecked user.process()

For Intermediate Users

Introduce ownership annotations:

type Tree = ref object left {.unique.}: Node # I own this exclusively right {.unique.}: Node # I own this exclusively parent {.cursor.}: Node # Non-owning back reference
  • Use .unique for owned children (trees, lists)
  • Use .cursor for back-references
  • Regular ref for shared/aliased references

Introduce with for complex cases:

# When the path is too complex: with table[key].items as items: for x in mitems(items): process(x) # When you need to mutate the parent: with data.items as items: for x in mitems(items): data = reconfigure() # Safe: items was moved

For Advanced Users

Acyclicity and performance:

If all ref fields in your type are .unique or .cursor, the structure is provably acyclic:

  • No cycle collector overhead
  • Simple, fast destruction
  • Better performance

Using func for cursor optimization:

See cursor-optimization.md - func enables zero-cost iteration because the compiler knows the function can't mutate the structure.

Implementation Notes

This section is primarily for compiler implementers.

Ownership Tracking

Track field-level ownership annotations:

type FieldInfo = object name: string typ: Type ownership: OwnershipKind OwnershipKind = enum okUnique # unique field - exclusive ownership okCursor # .cursor field - non-owning okShared # regular field - shared ownership proc analyzeType(T: Type): TypeInfo = var info = TypeInfo() for field in T.fields: if field.typ.kind == tyRef: if field.isUnique or field.isCursor: info.acyclic = true else: info.acyclic = false break return info

Uniqueness sources:

  1. new(T) always produces unique refs
  2. Functions with {.unique.} pragma return unique ownership
  3. Moving from .unique fields preserves uniqueness

Uniqueness requirements:

  • Assigning to .unique field requires unique value
  • Can "downgrade" unique to shared (when assigning to regular field)
  • Cannot "upgrade" shared to unique

Path Analysis

Implement a grammar checker for borrowable paths:

borrowablePath ::= simplePath | uncheckedPath simplePath ::= symbol ('.' field | '[' index ']')* uncheckedPath ::= '(addr' path ')[' ']'

Check for each path component:

  1. No function calls in the path
  2. Track ref derefs through the path
  3. If path has ref deref in middle:
    • Check if deref is through .unique field → safe
    • Check if wrapped in addr(...)[] → unchecked (allowed)
    • Otherwise → error: "path requires unchecked"

Path safety rules:

  • Value types: always safe
  • .unique fields: safe (no aliasing possible)
  • .cursor fields: safe (treated like value access)
  • Regular ref fields: require unchecked or with

Paths inside addr(...) are not checked (unsafe escape hatch).

Borrow Tracking

Maintain a stack of active borrows during tree traversal:

type BorrowInfo = object path: Cursor # NIF expression being borrowed borrower: SymId # the local variable doing the borrowing # upon `(kill <borrower>)` we know the borrow is over isRef: bool # Ref vs value borrowing BorrowChecker = object activeBorrows: seq[BorrowInfo] errors: seq[BorrowError]

On entering a for/mitems loop or taking an addr:

  1. Parse the borrowed path
  2. Check it's analyzable
  3. Add to active borrows

On (kill ...) node: remove corresponding borrow

Conflict Detection

For each mutation during active borrows:

proc checkConflict(mutation: Cursor, borrows: seq[BorrowInfo]) = for borrow in borrows: if overlaps(mutation, borrow.path): if isPrefix(mutation, borrow.path) or isPrefix(borrow.path, mutation): error("mutation conflicts with borrow") # Check if disjoint siblings if areDisjoint(mutation, borrow.path): continue # OK error("mutation conflicts with borrow")

For value borrowing, check mutations (StoreJ, UnknownJ).

For ref borrowing (see cursor-optimization.md), check any use of the witness path (even reads).

Integration with NJVL

NJVL provides the infrastructure needed:

  • (kill x) - explicit end of lifetime for borrow tracking
  • (unknown x) - marks mutations for conflict detection
  • Structured control flow - simplifies lifetime computation

Loop Handling

Loops work naturally without special handling:

for x in mitems(data.rows): for y in mitems(data.cols): # Two simultaneous borrows - check disjointness

The prefix exclusion rule prevents problematic mutations:

for item in mitems(data.items): for part in mitems(item.parts): # Borrow from item.parts makes 'item' immutable (prefix) # This is exactly what we need!

Error Messages

Provide clear, actionable messages:

Borrow conflict:

error: cannot assign to 'data' because it is borrowed at line 5: for x in mitems(data.items) at line 7: data = newData note: 'data' is a prefix of the borrowed path 'data.items' hint: if you need to mutate, use 'with': with data.items as items: for x in mitems(items): data = newData # Now safe - items was moved

Ref deref in path:

error: cannot borrow from 'app.users' - path contains ref dereference at line 10: for user in mitems(app.users) note: 'app' is a ref type and might be aliased hint: use 'unchecked' if you know 'app' is stable: for user in mitems(unchecked app.users): hint: or use 'with' for guaranteed safety: with app.users as users: for user in mitems(users):

Unique field assignment:

error: cannot assign shared ref to unique field 'head' at line 15: list.head = someNode note: 'head' requires unique ownership hint: use new() or a function marked {.unique.}: list.head = new(Node) list.head = createNode() # if createNode is {.unique.}

Summary

Nimony's borrow checking achieves memory safety through:

  1. Simple path-based rules - no complex lifetime tracking
  2. Prefix exclusion - one rule handles most cases
  3. Field-level ownership - .unique and .cursor annotations clarify structure
  4. Acyclicity verification - types with only .unique/.cursor fields are provably acyclic
  5. Leveraging Nim's semantics - value types, var vs non-var
  6. Graceful degradation - unchecked for ref derefs, with for complex paths
  7. No function annotations - functions stay clean, analysis is local

The ownership model:

  • .unique fields: exclusive ownership (prevents aliasing)
  • .cursor fields: non-owning references (prevents cycles)
  • Regular ref fields: shared ownership (with RC and cycle collector)

Escape hatches:

  • unchecked template: for ref-heavy code where you know it's safe
  • with template: temporarily move data (O(1) cost)

Performance benefits:

  • Acyclic types: no cycle collector overhead
  • func enables cursor optimization (see cursor-optimization.md)
  • Zero-cost abstractions for safe iteration

For automatic performance optimizations with ref types, see Cursor Optimization.

Read Entire Article
  1. Homepage
  2. Technology
  3. Borrow Checking in Nim 3.0

Related

PDF-native extraction vs. vision models for document processing

PDF-native extraction vs. vision models for document process...

20 minutes ago 0
Tech company CTO and others indicted for exporting Nvidia chips to China

Tech company CTO and others indicted for exporting Nvidia ch...

21 minutes ago 0
Real-Time AI-Powered Texas Hold'em in Python and Flask – Play in the Browser

Real-Time AI-Powered Texas Hold'em in Python and Flask – Pla...

21 minutes ago 0
Hostinger Web Hosting