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.
src/context/context.go
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.
src/context/context.go set and get value
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.
how context value allows overriding
The children key overriding is achieved that the Value
enquiries the value by comparable key from the tail and stops as long as it finds one. By this way, overriding DOES NOT change the previous key but appends a new key which will end up querying key there.
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 |
+---------+------+----+------+----+------+
hints
The hint is you might see multiple keys with different values if you print a context recursively with its internal states. However, Go doesn't export such APIs.
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.