Foundation Layer — Zusammenfassung¶
Alle Subsysteme des Jade Bootstrap-Compilers (CompilerDb, Parser, TypeEngine, NameResolver, DepGraph, QueryCache) brauchen dieselben Grundoperationen unter
@nogc nothrow pure. Diese gehören in eine gemeinsame Schicht unterhalb aller Subsysteme.
Einordnung im Projekt¶
jade/
foundation/ ← importiert KEIN anderes Jade-Modul
compiler_db/ ← importiert foundation
parser/ ← importiert foundation
type_engine/ ← importiert foundation
name_resolver/ ← importiert foundation
generator/ ← importiert foundation
foundation ist das Fundament — alle anderen Module bauen darauf auf,
es selbst hat keine Abhängigkeiten nach oben. Keine Zyklen möglich.
Nicht zu verwechseln mit der JME (Jade Memory Engine), die ein
Runtime-System für JDL-Programme ist. foundation ist D-Code
für den Bootstrap-Compiler.
Warum nicht std.experimental.allocator?¶
Handler müssen @nogc nothrow pure sein. pure verlangt, dass alle
aufgerufenen Methoden ebenfalls pure sind. Bei einer externen Dependency
kontrollierst du die Attribute nicht — wenn allocate() dort nicht pure
ist, bekommst du einen Buildfehler den du nicht fixen kannst. Eine Arena
ist ~20 Zeilen Code. Volle Kontrolle über alle Attribute wiegt mehr als
eine Dependency.
Die Bausteine¶
1. Arena — Chunk-basierter Bump-Allocator¶
Problem: Ein einzelner fixer Buffer läuft irgendwann voll.
Lösung: Kette von Chunks. Chunk voll → neuer Chunk dazu, weiter
allokieren. Kein Kopieren, kein Verschnitt. reset() gibt alle Chunks
auf einmal frei.
struct Chunk {
ubyte[] buffer;
Chunk* next;
}
struct Arena {
Chunk* current;
size_t offset;
size_t chunkSize;
ubyte[] allocate(size_t size) @nogc nothrow pure { ... }
void reset() @nogc nothrow { ... }
}
Kernmechanik: allocate = Offset vorschieben, fertig. O(1).
reset = Offset aller Chunks auf 0. Einzelne Freigabe gibt es nicht.
Chunks allokieren: Die Chunks selbst werden über malloc aus
core.stdc.stdlib geholt — das ist die einzige Stelle wo mit dem
OS-Allocator gesprochen wird. Alles darüber hinaus geht über
arena.allocate().
2. ArenaList(T) — Segmentierte Liste¶
Problem: Dynamische Arrays (arr ~= item) brauchen GC-Realloc.
Ein zusammenhängendes Array in der Arena erzeugt toten Ballast bei
jedem Wachstumsschritt (alter Block bleibt liegen, neuer wird allokiert).
Lösung: Kette von Segmenten fester Größe. Segment voll → neues Segment aus Arena allokieren, anhängen. Kein Kopieren, kein Verschnitt.
struct ArenaList(T) {
struct Segment {
T[64] items;
size_t len;
Segment* next;
}
Segment* first;
Segment* current;
Arena* arena;
void push(T val) @nogc nothrow pure { ... }
// Iteration: sequentiell über Segmente
}
Tradeoff: Kein O(1) Random Access per Index — dafür müsste man die
Segment-Kette entlanglaufen. Aber in der CompilerDb werden Listen fast
ausschließlich sequentiell iteriert (foreach über dependentsOf(key),
Cache-Traversal, Query-Stack). Dafür ist die Segment-Kette ideal.
3. ArenaMap(K, V) — Hash-Tabelle mit Open Addressing¶
Problem: Built-in Associative Arrays (V[K]) sind GC-verwaltet.
Lösung: Ein zusammenhängender Block von Buckets in der Arena. Open Addressing mit Linear Probing — kein Bucket belegt? Eins weiterrutschen bis ein freier gefunden wird.
struct ArenaMap(K, V) {
struct Bucket {
K key;
V value;
bool occupied;
}
Bucket[] buckets; // ein zusammenhängender Block in Arena
Arena* arena;
V* get(K key) @nogc nothrow pure { ... }
void put(K key, V value) @nogc nothrow pure { ... }
}
Warum zusammenhängend, nicht segmentiert? Hash → Index → direkter Zugriff auf den Bucket. Das ist Random Access, O(1). Bei einer Segment-Kette müsste man erst das richtige Segment suchen — das zerstört den Sinn einer Hash-Tabelle.
Wachstum: Wenn die Buckets voll werden: größeres Array allokieren, alles re-hashen, alter Block bleibt als Verschnitt. Deshalb initiale Größe großzügig schätzen. Bei der CompilerDb ist die Anzahl der Queries von der Projektgröße abhängig (Dateien × Typen × Symbole) und damit ungefähr abschätzbar.
4. hashOf(T) und equals(T) — Generische Identität¶
Problem: ArenaMap braucht für jeden Key-Typ Hash-Berechnung und
Gleichheitsvergleich. Manuell pro Typ schreiben skaliert nicht.
Lösung: static foreach über __traits(allMembers, T) — der
D-Compiler generiert zur Compile-Zeit typspezifischen Code.
bool equals(T)(const ref T a, const ref T b) @nogc nothrow pure {
static foreach (field; __traits(allMembers, T)) {
if (__traits(getMember, a, field) != __traits(getMember, b, field))
return false;
}
return true;
}
size_t hashOf(T)(const ref T value) @nogc nothrow pure {
size_t hash = 0;
static foreach (field; __traits(allMembers, T)) {
hash = hash * 31 + fieldHash(__traits(getMember, value, field));
}
return hash;
}
fieldHash für Primitives: Ein uint mit Wert 42 hat Hash 42.
Integers sind bereits Zahlen — sie sind ihr eigener Hash. Komplexe
Typen (verschachtelte Structs) werden rekursiv über ihre Felder gehasht.
Für ResolveType { TypeId id; ScopeId scope_; } entrollt der Compiler:
// equals:
if (a.id != b.id) return false;
if (a.scope_ != b.scope_) return false;
return true;
// hashOf:
hash = hash * 31 + fieldHash(value.id);
hash = hash * 31 + fieldHash(value.scope_);
Kein GC, kein Overhead, kein manueller Code pro Query-Typ.
5. serialize(T) und deserialize(T) — Deep Copy in Ziel-Arena¶
Problem: Query-Ergebnisse müssen im Cache (resultArena) überleben,
auch wenn die Quell-Arena zurückgesetzt wird. Ein Struct mit Pointern
oder Slices hat Referenzen die nach einem Arena-Reset ins Nichts zeigen
(Dangling Pointer). D hat keinen Borrow Checker der das erkennt.
Lösung: Deep Copy mit Pointer-Relokation.
- Das Struct selbst in die Ziel-Arena kopieren
- Alle referenzierten Daten (Slices, Pointer-Ziele) ebenfalls kopieren
- Die Pointer/Slices im kopierten Struct auf die neuen Adressen umbiegen
ubyte[] serialize(T)(T value, ref Arena arena) @nogc nothrow pure {
static if (isSimpleStruct!T) {
// Nur Primitives — memcpy reicht
auto buf = arena.allocate(T.sizeof);
memcpy(buf.ptr, &value, T.sizeof);
return buf;
} else {
// Struct in Arena kopieren
auto structBuf = arena.allocate(T.sizeof);
memcpy(structBuf.ptr, &value, T.sizeof);
auto result = cast(T*) structBuf.ptr;
// Für jedes Slice/Pointer-Feld: Daten kopieren + umbiegen
static foreach (field; __traits(allMembers, T)) {
static if (isSlice!(typeof(__traits(getMember, T, field)))) {
// Slice-Daten in Arena kopieren
// Slice-Pointer im kopierten Struct umbiegen
}
}
return structBuf;
}
}
isSimpleStruct: Ein Struct das nur Primitives enthält (keine Pointer,
keine Slices, keine Referenz-Typen). Dafür reicht memcpy. Alles andere
braucht den else-Branch mit Feld-für-Feld-Behandlung.
deserialize ist die Umkehrung: aus dem ubyte[]-Buffer ein typisiertes
Struct zurückholen. Für simple Structs ein cast, für komplexe Typen
müssen die Pointer auf die Positionen im Buffer zeigen.
Gesamtbild¶
┌─────────────────────────┐
│ Jade Compiler │
│ (CompilerDb, Parser, │
│ TypeEngine, ...) │
└────────────┬────────────┘
│ importiert
┌────────────▼────────────┐
│ foundation/ │
│ │
│ Arena │ Chunk-Kette, Bump-Alloc
│ ArenaList(T) │ Segment-Kette, push/iterate
│ ArenaMap(K, V) │ Open Addressing, ein Block
│ hashOf(T) / equals(T) │ static foreach + __traits
│ serialize / deserialize │ Deep Copy + Relokation
│ │
│ Alles @nogc nothrow pure│
└────────────┬────────────┘
│ nutzt
┌────────────▼────────────┐
│ core.stdc.stdlib │
│ (malloc/free nur für │
│ Arena-Chunks selbst) │
└─────────────────────────┘