diff options
Diffstat (limited to 'compiler/ic/packed_ast.nim')
| -rw-r--r-- | compiler/ic/packed_ast.nim | 408 |
1 files changed, 157 insertions, 251 deletions
diff --git a/compiler/ic/packed_ast.nim b/compiler/ic/packed_ast.nim index ef609e8c8..a39bb7adf 100644 --- a/compiler/ic/packed_ast.nim +++ b/compiler/ic/packed_ast.nim @@ -12,205 +12,149 @@ ## use this representation directly in all the transformations, ## it is superior. -import std / [hashes, tables] -import bitabs -import ".." / [ast, lineinfos, options, pathutils] +import std/[hashes, tables, strtabs] +import bitabs, rodfiles +import ".." / [ast, options] -const - localNamePos* = 0 - localExportMarkerPos* = 1 - localPragmaPos* = 2 - localTypePos* = 3 - localValuePos* = 4 - - typeNamePos* = 0 - typeExportMarkerPos* = 1 - typeGenericParamsPos* = 2 - typePragmaPos* = 3 - typeBodyPos* = 4 - - routineNamePos* = 0 - routineExportMarkerPos* = 1 - routinePatternPos* = 2 - routineGenericParamsPos* = 3 - routineParamsPos* = 4 - routineResultPos* = 5 - routinePragmasPos* = 6 - routineBodyPos* = 7 +import iclineinfos -const - nkModuleRef = nkNone # pair of (ModuleId, SymId) +when defined(nimPreviewSlimSystem): + import std/assertions type SymId* = distinct int32 - TypeId* = distinct int32 ModuleId* = distinct int32 NodePos* = distinct int NodeId* = distinct int32 - PackedLineInfo* = object - line*: uint16 - col*: int16 - file*: LitId + PackedItemId* = object + module*: LitId # 0 if it's this module + item*: int32 # same as the in-memory representation + +const + nilItemId* = PackedItemId(module: LitId(0), item: 0.int32) + +const + emptyNodeId* = NodeId(-1) +type PackedLib* = object kind*: TLibKind generated*: bool - isOverriden*: bool + isOverridden*: bool name*: LitId path*: NodeId PackedSym* = object + id*: int32 kind*: TSymKind name*: LitId - typeId*: TypeId + typ*: PackedItemId flags*: TSymFlags magic*: TMagic info*: PackedLineInfo - ast*: NodePos - owner*: ItemId - guard*: ItemId + ast*: NodeId + owner*: PackedItemId + guard*: PackedItemId bitsize*: int alignment*: int # for alignment options*: TOptions position*: int - offset*: int + offset*: int32 + disamb*: int32 externalName*: LitId # instead of TLoc + locFlags*: TLocFlags annex*: PackedLib when hasFFI: cname*: LitId constraint*: NodeId + instantiatedFrom*: PackedItemId PackedType* = object + id*: int32 kind*: TTypeKind - nodekind*: TNodeKind + callConv*: TCallingConvention + #nodekind*: TNodeKind flags*: TTypeFlags - types*: int32 - nodes*: int32 - methods*: int32 - nodeflags*: TNodeFlags - info*: PackedLineInfo - sym*: ItemId - owner*: ItemId - attachedOps*: array[TTypeAttachedOp, ItemId] + types*: seq[PackedItemId] + n*: NodeId + #nodeflags*: TNodeFlags + sym*: PackedItemId + owner*: PackedItemId size*: BiggestInt align*: int16 paddingAtEnd*: int16 - lockLevel*: TLockLevel # lock level as required for deadlock checking # not serialized: loc*: TLoc because it is backend-specific - typeInst*: TypeId - nonUniqueId*: ItemId - - Node* = object # 20 bytes - kind*: TNodeKind - flags*: TNodeFlags - operand*: int32 # for kind in {nkSym, nkSymDef}: SymId - # for kind in {nkStrLit, nkIdent, nkNumberLit}: LitId - # for kind in nkInt32Lit: direct value - # for non-atom kinds: the number of nodes (for easy skipping) - typeId*: TypeId - info*: PackedLineInfo + typeInst*: PackedItemId + nonUniqueId*: int32 - ModulePhase* = enum - preLookup, lookedUpTopLevelStmts - - Module* = object - name*: string - file*: AbsoluteFile - ast*: PackedTree - phase*: ModulePhase - iface*: Table[string, seq[SymId]] # 'seq' because of overloading - - Program* = ref object - modules*: seq[Module] - - Shared* = ref object # shared between different versions of 'Module'. - # (though there is always exactly one valid - # version of a module) - syms*: seq[PackedSym] - types*: seq[seq[Node]] - strings*: BiTable[string] # we could share these between modules. - integers*: BiTable[BiggestInt] - floats*: BiTable[BiggestFloat] - config*: ConfigRef - #thisModule*: ModuleId - #program*: Program + PackedNode* = object # 8 bytes + x: uint32 + info*: PackedLineInfo PackedTree* = object ## usually represents a full Nim module - nodes*: seq[Node] - toPosition*: Table[SymId, NodePos] - sh*: Shared + nodes: seq[PackedNode] + withFlags: seq[(int32, TNodeFlags)] + withTypes: seq[(int32, PackedItemId)] -proc `==`*(a, b: SymId): bool {.borrow.} -proc hash*(a: SymId): Hash {.borrow.} + PackedInstantiation* = object + key*, sym*: PackedItemId + concreteTypes*: seq[PackedItemId] -proc `==`*(a, b: NodePos): bool {.borrow.} -proc `==`*(a, b: TypeId): bool {.borrow.} -proc `==`*(a, b: ModuleId): bool {.borrow.} +const + NodeKindBits = 8'u32 + NodeKindMask = (1'u32 shl NodeKindBits) - 1'u32 -proc declareSym*(tree: var PackedTree; kind: TSymKind; - name: LitId; info: PackedLineInfo): SymId = - result = SymId(tree.sh.syms.len) - tree.sh.syms.add PackedSym(kind: kind, name: name, flags: {}, magic: mNone, info: info) +template kind*(n: PackedNode): TNodeKind = TNodeKind(n.x and NodeKindMask) +template uoperand*(n: PackedNode): uint32 = (n.x shr NodeKindBits) +template soperand*(n: PackedNode): int32 = int32(uoperand(n)) -proc newTreeFrom*(old: PackedTree): PackedTree = - result.nodes = @[] - result.sh = old.sh +template toX(k: TNodeKind; operand: uint32): uint32 = + uint32(k) or (operand shl NodeKindBits) + +template toX(k: TNodeKind; operand: LitId): uint32 = + uint32(k) or (operand.uint32 shl NodeKindBits) -proc litIdFromName*(tree: PackedTree; name: string): LitId = - result = tree.sh.strings.getOrIncl(name) +template typeId*(n: PackedNode): PackedItemId = n.typ -proc add*(tree: var PackedTree; kind: TNodeKind; token: string; info: PackedLineInfo) = - tree.nodes.add Node(kind: kind, operand: int32 getOrIncl(tree.sh.strings, token), info: info) +proc `==`*(a, b: SymId): bool {.borrow.} +proc hash*(a: SymId): Hash {.borrow.} -proc add*(tree: var PackedTree; kind: TNodeKind; info: PackedLineInfo) = - tree.nodes.add Node(kind: kind, operand: 0, info: info) +proc `==`*(a, b: NodePos): bool {.borrow.} +#proc `==`*(a, b: PackedItemId): bool {.borrow.} +proc `==`*(a, b: NodeId): bool {.borrow.} -proc throwAwayLastNode*(tree: var PackedTree) = - tree.nodes.setLen(tree.nodes.len-1) +proc newTreeFrom*(old: PackedTree): PackedTree = + result = PackedTree(nodes: @[]) + when false: result.sh = old.sh proc addIdent*(tree: var PackedTree; s: LitId; info: PackedLineInfo) = - tree.nodes.add Node(kind: nkIdent, operand: int32(s), info: info) - -proc addSym*(tree: var PackedTree; s: SymId; info: PackedLineInfo) = - tree.nodes.add Node(kind: nkSym, operand: int32(s), info: info) + tree.nodes.add PackedNode(x: toX(nkIdent, uint32(s)), info: info) -proc addModuleId*(tree: var PackedTree; s: ModuleId; info: PackedLineInfo) = - tree.nodes.add Node(kind: nkInt32Lit, operand: int32(s), info: info) +proc addSym*(tree: var PackedTree; s: int32; info: PackedLineInfo) = + tree.nodes.add PackedNode(x: toX(nkSym, cast[uint32](s)), info: info) proc addSymDef*(tree: var PackedTree; s: SymId; info: PackedLineInfo) = - tree.nodes.add Node(kind: nkSym, operand: int32(s), info: info) + tree.nodes.add PackedNode(x: toX(nkSym, cast[uint32](s)), info: info) proc isAtom*(tree: PackedTree; pos: int): bool {.inline.} = tree.nodes[pos].kind <= nkNilLit -proc copyTree*(dest: var PackedTree; tree: PackedTree; n: NodePos) = - # and this is why the IR is superior. We can copy subtrees - # via a linear scan. - let pos = n.int - let L = if isAtom(tree, pos): 1 else: tree.nodes[pos].operand - let d = dest.nodes.len - dest.nodes.setLen(d + L) - for i in 0..<L: - dest.nodes[d+i] = tree.nodes[pos+i] - -proc copySym*(dest: var PackedTree; tree: PackedTree; s: SymId): SymId = - result = SymId(dest.sh.syms.len) - assert int(s) < tree.sh.syms.len - let oldSym = tree.sh.syms[s.int] - dest.sh.syms.add oldSym - type PatchPos = distinct int -when false: - proc prepare*(tree: var PackedTree; kind: TNodeKind; info: PackedLineInfo): PatchPos = - result = PatchPos tree.nodes.len - tree.nodes.add Node(kind: kind, operand: 0, info: info) +proc addNode*(t: var PackedTree; kind: TNodeKind; operand: int32; + typeId: PackedItemId = nilItemId; info: PackedLineInfo; + flags: TNodeFlags = {}) = + t.nodes.add PackedNode(x: toX(kind, cast[uint32](operand)), info: info) + if flags != {}: + t.withFlags.add (t.nodes.len.int32 - 1, flags) + if typeId != nilItemId: + t.withTypes.add (t.nodes.len.int32 - 1, typeId) -proc prepare*(tree: var PackedTree; kind: TNodeKind; flags: TNodeFlags; typeId: TypeId; info: PackedLineInfo): PatchPos = +proc prepare*(tree: var PackedTree; kind: TNodeKind; flags: TNodeFlags; typeId: PackedItemId; info: PackedLineInfo): PatchPos = result = PatchPos tree.nodes.len - tree.nodes.add Node(kind: kind, flags: flags, operand: 0, typeId: typeId, info: info) + tree.addNode(kind = kind, flags = flags, operand = 0, info = info, typeId = typeId) proc prepare*(dest: var PackedTree; source: PackedTree; sourcePos: NodePos): PatchPos = result = PatchPos dest.nodes.len @@ -218,25 +162,30 @@ proc prepare*(dest: var PackedTree; source: PackedTree; sourcePos: NodePos): Pat proc patch*(tree: var PackedTree; pos: PatchPos) = let pos = pos.int - assert tree.nodes[pos].kind > nkNilLit + let k = tree.nodes[pos].kind + assert k > nkNilLit let distance = int32(tree.nodes.len - pos) - tree.nodes[pos].operand = distance + assert distance > 0 + tree.nodes[pos].x = toX(k, cast[uint32](distance)) proc len*(tree: PackedTree): int {.inline.} = tree.nodes.len -proc `[]`*(tree: PackedTree; i: int): lent Node {.inline.} = tree.nodes[i] +proc `[]`*(tree: PackedTree; i: NodePos): lent PackedNode {.inline.} = + tree.nodes[i.int] + +template rawSpan(n: PackedNode): int = int(uoperand(n)) proc nextChild(tree: PackedTree; pos: var int) {.inline.} = if tree.nodes[pos].kind > nkNilLit: - assert tree.nodes[pos].operand > 0 - inc pos, tree.nodes[pos].operand + assert tree.nodes[pos].uoperand > 0 + inc pos, tree.nodes[pos].rawSpan else: inc pos iterator sonsReadonly*(tree: PackedTree; n: NodePos): NodePos = var pos = n.int assert tree.nodes[pos].kind > nkNilLit - let last = pos + tree.nodes[pos].operand + let last = pos + tree.nodes[pos].rawSpan inc pos while pos < last: yield NodePos pos @@ -247,7 +196,8 @@ iterator sons*(dest: var PackedTree; tree: PackedTree; n: NodePos): NodePos = for x in sonsReadonly(tree, n): yield x patch dest, patchPos -iterator isons*(dest: var PackedTree; tree: PackedTree; n: NodePos): (int, NodePos) = +iterator isons*(dest: var PackedTree; tree: PackedTree; + n: NodePos): (int, NodePos) = var i = 0 for ch0 in sons(dest, tree, n): yield (i, ch0) @@ -256,7 +206,7 @@ iterator isons*(dest: var PackedTree; tree: PackedTree; n: NodePos): (int, NodeP iterator sonsFrom1*(tree: PackedTree; n: NodePos): NodePos = var pos = n.int assert tree.nodes[pos].kind > nkNilLit - let last = pos + tree.nodes[pos].operand + let last = pos + tree.nodes[pos].rawSpan inc pos if pos < last: nextChild tree, pos @@ -270,7 +220,7 @@ iterator sonsWithoutLast2*(tree: PackedTree; n: NodePos): NodePos = inc count var pos = n.int assert tree.nodes[pos].kind > nkNilLit - let last = pos + tree.nodes[pos].operand + let last = pos + tree.nodes[pos].rawSpan inc pos while pos < last and count > 2: yield NodePos pos @@ -280,9 +230,9 @@ iterator sonsWithoutLast2*(tree: PackedTree; n: NodePos): NodePos = proc parentImpl(tree: PackedTree; n: NodePos): NodePos = # finding the parent of a node is rather easy: var pos = n.int - 1 - while pos >= 0 and isAtom(tree, pos) or (pos + tree.nodes[pos].operand - 1 < n.int): + while pos >= 0 and (isAtom(tree, pos) or (pos + tree.nodes[pos].rawSpan - 1 < n.int)): dec pos - assert pos >= 0, "node has no parent" + #assert pos >= 0, "node has no parent" result = NodePos(pos) template parent*(n: NodePos): NodePos = parentImpl(tree, n) @@ -301,13 +251,37 @@ proc hasAtLeastXsons*(tree: PackedTree; n: NodePos; x: int): bool = if count >= x: return true return false -proc firstSon*(tree: PackedTree; n: NodePos): NodePos {.inline.} = NodePos(n.int+1) -proc kind*(tree: PackedTree; n: NodePos): TNodeKind {.inline.} = tree.nodes[n.int].kind -proc litId*(tree: PackedTree; n: NodePos): LitId {.inline.} = LitId tree.nodes[n.int].operand -proc info*(tree: PackedTree; n: NodePos): PackedLineInfo {.inline.} = tree.nodes[n.int].info - -proc span(tree: PackedTree; pos: int): int {.inline.} = - if isAtom(tree, pos): 1 else: tree.nodes[pos].operand +proc firstSon*(tree: PackedTree; n: NodePos): NodePos {.inline.} = + NodePos(n.int+1) +proc kind*(tree: PackedTree; n: NodePos): TNodeKind {.inline.} = + tree.nodes[n.int].kind +proc litId*(tree: PackedTree; n: NodePos): LitId {.inline.} = + LitId tree.nodes[n.int].uoperand +proc info*(tree: PackedTree; n: NodePos): PackedLineInfo {.inline.} = + tree.nodes[n.int].info + +proc findType*(tree: PackedTree; n: NodePos): PackedItemId = + for x in tree.withTypes: + if x[0] == int32(n): return x[1] + if x[0] > int32(n): return nilItemId + return nilItemId + +proc findFlags*(tree: PackedTree; n: NodePos): TNodeFlags = + for x in tree.withFlags: + if x[0] == int32(n): return x[1] + if x[0] > int32(n): return {} + return {} + +template typ*(n: NodePos): PackedItemId = + tree.findType(n) +template flags*(n: NodePos): TNodeFlags = + tree.findFlags(n) + +template uoperand*(n: NodePos): uint32 = + tree.nodes[n.int].uoperand + +proc span*(tree: PackedTree; pos: int): int {.inline.} = + if isAtom(tree, pos): 1 else: tree.nodes[pos].rawSpan proc sons2*(tree: PackedTree; n: NodePos): (NodePos, NodePos) = assert(not isAtom(tree, n.int)) @@ -323,6 +297,7 @@ proc sons3*(tree: PackedTree; n: NodePos): (NodePos, NodePos, NodePos) = result = (NodePos a, NodePos b, NodePos c) proc ithSon*(tree: PackedTree; n: NodePos; i: int): NodePos = + result = default(NodePos) if tree.nodes[n.int].kind > nkNilLit: var count = 0 for child in sonsReadonly(tree, n): @@ -330,106 +305,34 @@ proc ithSon*(tree: PackedTree; n: NodePos; i: int): NodePos = inc count assert false, "node has no i-th child" -proc `@`*(tree: PackedTree; lit: LitId): lent string {.inline.} = tree.sh.strings[lit] +when false: + proc `@`*(tree: PackedTree; lit: LitId): lent string {.inline.} = + tree.sh.strings[lit] template kind*(n: NodePos): TNodeKind = tree.nodes[n.int].kind template info*(n: NodePos): PackedLineInfo = tree.nodes[n.int].info -template litId*(n: NodePos): LitId = LitId tree.nodes[n.int].operand +template litId*(n: NodePos): LitId = LitId tree.nodes[n.int].uoperand -template symId*(n: NodePos): SymId = SymId tree.nodes[n.int].operand +template symId*(n: NodePos): SymId = SymId tree.nodes[n.int].soperand proc firstSon*(n: NodePos): NodePos {.inline.} = NodePos(n.int+1) -proc strLit*(tree: PackedTree; n: NodePos): lent string = - assert n.kind == nkStrLit - result = tree.sh.strings[LitId tree.nodes[n.int].operand] - -proc strVal*(tree: PackedTree; n: NodePos): string = - assert n.kind == nkStrLit - result = tree.sh.strings[LitId tree.nodes[n.int].operand] - #result = cookedStrLit(raw) - -proc filenameVal*(tree: PackedTree; n: NodePos): string = - case n.kind - of nkStrLit: - result = strVal(tree, n) - of nkIdent: - result = tree.sh.strings[n.litId] - of nkSym: - result = tree.sh.strings[tree.sh.syms[int n.symId].name] - else: - result = "" - -proc identAsStr*(tree: PackedTree; n: NodePos): lent string = - assert n.kind == nkIdent - result = tree.sh.strings[LitId tree.nodes[n.int].operand] - const externIntLit* = {nkCharLit, nkIntLit, nkInt8Lit, nkInt16Lit, + nkInt32Lit, nkInt64Lit, nkUIntLit, nkUInt8Lit, nkUInt16Lit, nkUInt32Lit, - nkUInt64Lit} # nkInt32Lit is missing by design! + nkUInt64Lit} - externSIntLit* = {nkIntLit, nkInt8Lit, nkInt16Lit, nkInt64Lit} + externSIntLit* = {nkIntLit, nkInt8Lit, nkInt16Lit, nkInt32Lit, nkInt64Lit} externUIntLit* = {nkUIntLit, nkUInt8Lit, nkUInt16Lit, nkUInt32Lit, nkUInt64Lit} - directIntLit* = nkInt32Lit - -proc toString*(tree: PackedTree; n: NodePos; nesting: int; result: var string) = - let pos = n.int - if result.len > 0 and result[^1] notin {' ', '\n'}: - result.add ' ' - - result.add $tree[pos].kind - case tree.nodes[pos].kind - of nkNone, nkEmpty, nkNilLit, nkType: discard - of nkIdent, nkStrLit..nkTripleStrLit: - result.add " " - result.add tree.sh.strings[LitId tree.nodes[pos].operand] - of nkSym: - result.add " " - result.add tree.sh.strings[tree.sh.syms[tree.nodes[pos].operand].name] - of directIntLit: - result.add " " - result.addInt tree.nodes[pos].operand - of externSIntLit: - result.add " " - result.addInt tree.sh.integers[LitId tree.nodes[pos].operand] - of externUIntLit: - result.add " " - result.add $cast[uint64](tree.sh.integers[LitId tree.nodes[pos].operand]) - else: - result.add "(\n" - for i in 1..(nesting+1)*2: result.add ' ' - for child in sonsReadonly(tree, n): - toString(tree, child, nesting + 1, result) - result.add "\n" - for i in 1..nesting*2: result.add ' ' - result.add ")" - #for i in 1..nesting*2: result.add ' ' - - -proc toString*(tree: PackedTree; n: NodePos): string = - result = "" - toString(tree, n, 0, result) - -proc debug*(tree: PackedTree) = - stdout.write toString(tree, NodePos 0) - -proc identIdImpl(tree: PackedTree; n: NodePos): LitId = - if n.kind == nkIdent: - result = n.litId - elif n.kind == nkSym: - result = tree.sh.syms[int n.symId].name - else: - result = LitId(0) - -template identId*(n: NodePos): LitId = identIdImpl(tree, n) + directIntLit* = nkNone template copyInto*(dest, n, body) = let patchPos = prepare(dest, tree, n) @@ -441,21 +344,24 @@ template copyIntoKind*(dest, kind, info, body) = body patch dest, patchPos -proc hasPragma*(tree: PackedTree; n: NodePos; pragma: string): bool = - let litId = tree.sh.strings.getKeyId(pragma) - if litId == LitId(0): - return false - assert n.kind == nkPragma - for ch0 in sonsReadonly(tree, n): - if ch0.kind == nkExprColonExpr: - if ch0.firstSon.identId == litId: - return true - elif ch0.identId == litId: - return true +proc getNodeId*(tree: PackedTree): NodeId {.inline.} = NodeId tree.nodes.len -when false: - proc produceError*(dest: var PackedTree; tree: PackedTree; n: NodePos; msg: string) = - let patchPos = prepare(dest, nkError, n.info) - dest.add nkStrLit, msg, n.info - copyTree(dest, tree, n) - patch dest, patchPos +iterator allNodes*(tree: PackedTree): NodePos = + var p = 0 + while p < tree.len: + yield NodePos(p) + let s = span(tree, p) + inc p, s + +proc toPackedItemId*(item: int32): PackedItemId {.inline.} = + PackedItemId(module: LitId(0), item: item) + +proc load*(f: var RodFile; t: var PackedTree) = + loadSeq f, t.nodes + loadSeq f, t.withFlags + loadSeq f, t.withTypes + +proc store*(f: var RodFile; t: PackedTree) = + storeSeq f, t.nodes + storeSeq f, t.withFlags + storeSeq f, t.withTypes |