varpartitions

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.

Imports

ast, types, lineinfos, options, msgs, renderer, typeallowed, trees, isolation_check

Types

MutationInfo = object
  param: PSym
  mutatedHere, connectedVia: TLineInfo
  flags: set[SubgraphFlag]
  maxMutation, minConnection: AbstractTime
  mutations: seq[AbstractTime]

Source Edit

Goal = enum
  constParameters, borrowChecking, cursorInference

Source Edit

Partitions = object
  abstractTime: AbstractTime
  s: seq[VarIndex]
  graphs: seq[MutationInfo]
  goals: set[Goal]
  unanalysableMutation: bool
  inAsgnSource, inConstructor, inNoSideEffectSection: int
  inConditional, inLoop: int
  owner: PSym
  config: ConfigRef

Source Edit

Procs

proc `$`(config: ConfigRef; g: MutationInfo): string {...}{.raises: [], tags: [].}

Source Edit

proc hasSideEffect(c: var Partitions; info: var MutationInfo): bool {...}{.
    raises: [], tags: [].}

Source Edit

proc computeGraphPartitions(s: PSym; n: PNode; config: ConfigRef;
                            goals: set[Goal]): Partitions {...}{.
    raises: [Exception, ValueError, IOError, ERecoverableError],
    tags: [RootEffect, WriteIOEffect, ReadIOEffect, ReadEnvEffect].}

Source Edit

proc checkBorrowedLocations(par: var Partitions; body: PNode; config: ConfigRef) {...}{.
    raises: [Exception, ValueError, IOError, ERecoverableError],
    tags: [RootEffect, WriteIOEffect, ReadIOEffect, ReadEnvEffect].}

Source Edit

proc computeCursors(s: PSym; n: PNode; config: ConfigRef) {...}{.
    raises: [Exception, ValueError, IOError, ERecoverableError],
    tags: [RootEffect, WriteIOEffect, ReadIOEffect, ReadEnvEffect].}

Source Edit