Symbol Table and Context Value Implementation¶

After learning briefly about compiler, with the motivation of walker inside astjson, it's a bit compulsory to master some knowledge about symbol table as it helps to understand management of variables/states in a large different scales.

This blog talks first about the symbol table itself, and then check how Go language maintains the values among contexts in src/context. Note that it doesn't talk anything else rather than values in context.

Summary of Symbol Table¶

The compiler has some stages to get the final binary:

• tokenization(lexical analysis)
• parsing(syntax analysis)
• semantic analysis
• code generation.

The symbol table is constructed in semantic analysis stage which compiler traverses the AST to construct symbol tables.

While traversing AST, the compiler proceeds the nodes and manipulate the tables. Basically, the implementation of symbol tables can be ordered array, map ,binary search tree and so forth. During parsing AST, compiler maintains scopes between symbol tables and nodes. Note that Go itself doesn't use symbol table during semantic analysis.

Context Value Implementation¶

For now, I'm intrigue on the management of different scopes of symbol table. Hence, the context is a super nice example as it's easy and common and fits the different symbol table case here.

Context allows you to put data inside it.

• Parent(outside scope) cannot read values inside children(inside scope),
• Children enables to read and override without affecting parents.

From this view, it's more likely similar to a symbol table, which enables override variables inside an inside scope.

valueCtx Definition¶

Generally, context provides different implementations and composites them for different purposes. When it comes to value storing, we can focus on the valueCtx in golang.

package context

// A Context carries a deadline, a cancellation signal, and other values across
// API boundaries.
//
// Context's methods may be called by multiple goroutines simultaneously.
type Context interface {
    Deadline() (deadline time.Time, ok bool)
    Done() <-chan struct{}
    Err() error
    Value(key any) any
}

// A valueCtx carries a key-value pair. It implements Value for that key and
// delegates all other calls to the embedded Context.
type valueCtx struct {
    Context
    key, val any
}

You can quickly find that the values in a valueCtx is a linked list. It wraps new value inside valueCtx and returns the new context.

Here is a visual view of how value context looks like:

+---------+------+----+------+----+------+
| Context | ctx1 | -> | ctx2 | -> | ctx3 |
+---------+------+----+------+----+------+
| Value   | a:1  |    | ctx1 |    | ctx2 |
|         |      |    | b:2  |    | c:3  |
+---------+------+----+------+----+------+

valueCtx Set and Get Value¶

The Context maintains values simply by wrapping them.

func WithValue(parent Context, key, val any) Context {
    if parent == nil {
        panic("cannot create context from nil parent")
    }
    if key == nil {
        panic("nil key")
    }
    if !reflectlite.TypeOf(key).Comparable() {
        panic("key is not comparable")
    }
    return &valueCtx{parent, key, val}
}

func (c *valueCtx) Value(key any) any {
    if c.key == key {
        return c.val
    }
    return value(c.Context, key)
}

When querying, it keeps looking recursively up in the parents until end or found as the following source code reveals.

As a result, each context have some visual values, and it finds a key from bottom to top. For example, when finding key b in ctx4, it will find b:3 and end up there. The parent value b:2 seems to be changed but indeed it's hidden by the code implementation.

+---------+------+----+------+----+------+
| Context | ctx1 | -> | ctx2 | -> | ctx4 |
+---------+------+----+------+----+------+
| Value   | a:1  |    | a:1  |    | a:1  |
|         |      |    | b:2  |    | b:2  |
|         |      |    |      |    | b:3  |
+---------+------+----+------+----+------+
| Context |      | -> | ctx3 | -> | ctx5 |
+---------+------+----+------+----+------+
| Value   |      |    | a:1  |    | a:1  |
|         |      |    | c:2  |    | c:2  |
|         |      |    |      |    | a:3  |
+---------+------+----+------+----+------+

It's a smart and cunning way to maintain values for different scopes, simply adding and getting keys inside a children context is easy to implement without considering preserving value in parents.