cst-tokens internal data stucture

index.md

  A range is represented as a [Token, Token] tuple.

  A range can only be iterated backwards, which creates the need to store tokens in an array!

  Each node must have its own tokens array to enable efficient editing.

  A context object often abbreviated `ctx` holds WeakMaps, including `paths` and `previousTokens`.

  Tokens reference their preceding token using the `previousTokens` WeakMap.
  This allows tokens double as iterator steps.


       ┌───────────────┐        ┌───────────────┐        ┌───────────────┐        ┌───────────────┐
       │     Token     │        │     Token     │        │     Token     │        │     Token     │
       │               │        │               │        │               │        │               │
◄──────┤               │ ◄──────┤   StartNode   │ ◄──────┤     (child)   │ ◄──────┤    EndNode    │
  prev └───────────────┘   prev └──────┬────────┘   prev └───────────────┘   prev └─────────┬─────┘
                                       │  ▲                                              ▲  │
                                       │  │                                              │  │
                                       │  │  This inner cycle can be used to skip        │  │
                                       │  │  child tokens. When an EndNode is found,     │  │
The `ctx.paths` WeakMap is responsible │  │  look up its path and swap it for StartNode. │  │
for linking tokens to paths.           │  │                                              │  │
e.g. `ctx.paths.get(startNodeToken)`   │  │                                              │  │
                                       ▼  │ range[0]                                     │  │
                                ┌─────────┴─────┐     range[1]                           │  │
                                │     Path      ├────────────────────────────────────────┘  │
                                │               │                                           │
                                │               │ ◄─────────────────────────────────────────┘
                                └───────┬───────┘
                                        │ parent
                                        │
                                        ▼
                                ┌───────────────┐
                                │     Path      │
                                └───────────────┘

                             To efficiently capture a node's own tokens into an array in
                             O(n) time you must skip tokens belonging to children.

                             This is done by swapping `path.range[0]` for `path.range[1]`