# compiler/varpartitions

Dark Mode

- Index

Search:
Group by:
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.

# Imports

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

# Types

    Goal = enum
      constParameters, borrowChecking, cursorInference

  Source Edit

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

  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
      g: ModuleGraph

  Source Edit

# Procs

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

  Source Edit

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

  Source Edit

    proc computeCursors(s: PSym; n: PNode; g: ModuleGraph) {....raises: [Exception,
        ValueError, KeyError, OSError, IOError, ERecoverableError], tags: [
        RootEffect, ReadDirEffect, WriteIOEffect, ReadIOEffect, ReadEnvEffect].}

  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].}

  Source Edit

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

  Source Edit