varpartitions

Source   Edit  

Partition variables into different graphs. Used for Nim's write tracking, borrow checking and also for the cursor inference. The algorithm is a reinvention / variation of Steensgaard's algorithm. The used data structure is "union find" with path compression.We perform two passes over the AST:

  • Pass one (computeLiveRanges): collect livetimes of local variables and whether they are potentially re-assigned.
  • Pass two (traverse): combine local variables to abstract "graphs". Strict func checking: Ensure that graphs that are connected to const parameters are not mutated. Cursor inference: Ensure that potential cursors are not borrowed from locations that are connected to a graph that is mutated during the liveness of the cursor. (We track all possible mutations of a graph.)

See https://nim-lang.github.io/Nim/manual_experimental.html#view-types-algorithm for a high-level description of how borrow checking works.

Types

Goal = enum
  constParameters, borrowChecking, cursorInference
Source   Edit  
MutationInfo = object
  
Source   Edit  
Partitions = object
  
Source   Edit  

Procs

proc `$`(config: ConfigRef; g: MutationInfo): string {.
    ...raises: [Exception, KeyError, OSError], tags: [RootEffect, ReadDirEffect],
    forbids: [].}
Source   Edit  
proc checkBorrowedLocations(par: var Partitions; body: PNode; config: ConfigRef) {....raises: [
    Exception, KeyError, OSError, ValueError, IOError, ERecoverableError], tags: [
    RootEffect, ReadDirEffect, WriteIOEffect, ReadIOEffect, ReadEnvEffect],
    forbids: [].}
Source   Edit  
proc computeCursors(s: PSym; n: PNode; g: ModuleGraph) {....raises: [Exception,
    ValueError, KeyError, OSError, IOError, ERecoverableError], tags: [
    RootEffect, ReadDirEffect, WriteIOEffect, ReadIOEffect, ReadEnvEffect],
    forbids: [].}
Source   Edit  
proc computeGraphPartitions(s: PSym; n: PNode; g: ModuleGraph; goals: set[Goal]): Partitions {....raises: [
    Exception, ValueError, KeyError, OSError, IOError, ERecoverableError], tags: [
    RootEffect, ReadDirEffect, WriteIOEffect, ReadIOEffect, ReadEnvEffect],
    forbids: [].}
Source   Edit  
proc hasSideEffect(c: var Partitions; info: var MutationInfo): bool {.
    ...raises: [], tags: [], forbids: [].}
Source   Edit