Skip to content
This repository was archived by the owner on Dec 11, 2021. It is now read-only.
This repository was archived by the owner on Dec 11, 2021. It is now read-only.

Idea: use "packed ASTs" #8

@Araq

Description

@Araq

Have you tried this design:

type
  Node = distinct int32

template kind*(n: Node): JsonKind = JsonKind(n and KindMask)
template operand*(n: Node): int32 = n shr KindShift

type
  JsonTree = object
    kids: seq[Node]
    atoms: BiTable[string] # store numbers as strings too and parse them to numbers in the accessor procs

The crucial idea here is that atoms use 'operand' bits to index into the 'atoms' BiTable while compound nodes use it to store the total number of children. Via some clever arithmetic operations you can easily compute the ith-child anyway. See my PackedAST code in compiler/ic.

This should be close to the optimum design. The API on top should encourage efficient operations (don't use random access, iterate over the tree instead).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions