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
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 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