//! Symbol table.

//! Implement a multi-scope symbol table with hash-based lookup, scope

//! push/pop, and symbol resolution. Exercises: optionals, if-let,

//! while-let, let-else, for-in with indexing, records with pointer

//! fields, and complex interactions between data structures.

const MAX_SYMBOLS: u32 = 256;

const MAX_SCOPES: u32 = 16;

const HASH_SIZE: u32 = 64;

const NIL: u32 = 0xFFFFFFFF;

/// A symbol entry in the table.

record Symbol {

    /// Name of the symbol (hash for comparison).

    nameHash: u32,

    /// The value associated with this symbol.

    value: i32,

    /// Scope depth at which this symbol was defined.

    depth: u32,

    /// Next symbol in hash chain.

    next: u32,

    /// Previous symbol with the same name (for shadowing).

    shadow: u32,

}

/// A scope boundary marker.

record ScopeMarker {

    /// Number of symbols when scope was entered.

    symbolCount: u32,

}

/// The symbol table.

record SymTab {

    symbols: *mut [Symbol],

    symbolCount: u32,

    scopes: *mut [ScopeMarker],

    scopeDepth: u32,

    buckets: *mut [u32],

}

/// Simple string hash function.

fn hashName(name: *[u8]) -> u32 {

    let mut h: u32 = 5381;

    for ch in name {

        h = ((h << 5) + h) + ch as u32;

    }

    return h;

}

/// Initialize the symbol table.

fn init(tab: *mut SymTab) {

    tab.symbolCount = 0;

    tab.scopeDepth = 0;

    for i in 0..HASH_SIZE {

        tab.buckets[i] = NIL;

    }

}

/// Push a new scope.

fn pushScope(tab: *mut SymTab) {

    tab.scopes[tab.scopeDepth] = ScopeMarker { symbolCount: tab.symbolCount };

    tab.scopeDepth += 1;

}

/// Pop the current scope, removing all symbols defined in it.

fn popScope(tab: *mut SymTab) {

    if tab.scopeDepth == 0 {

        return;

    }

    tab.scopeDepth -= 1;

    let marker = tab.scopes[tab.scopeDepth];

    // Remove symbols added in this scope (in reverse order).

    while tab.symbolCount > marker.symbolCount {

        tab.symbolCount -= 1;

        let sym = tab.symbols[tab.symbolCount];

        let bucket = sym.nameHash % HASH_SIZE;

        // Remove from hash chain.

        tab.buckets[bucket] = sym.next;

        // Restore shadowed symbol if any.

        if sym.shadow != NIL {

            // The shadowed symbol is still in the symbols array;

            // re-link it into the hash chain.

            let shadowIdx = sym.shadow;

            tab.symbols[shadowIdx].next = tab.buckets[bucket];

            tab.buckets[bucket] = shadowIdx;

        }

    }

}

/// Define a symbol in the current scope.

fn define(tab: *mut SymTab, name: *[u8], value: i32) -> u32 {

    let h = hashName(name);

    let bucket = h % HASH_SIZE;

    // Check for shadowed symbol with same name.

    let mut shadowIdx: u32 = NIL;

    let mut cur = tab.buckets[bucket];

    while cur != NIL {

        if tab.symbols[cur].nameHash == h {

            // Found existing symbol with same hash - shadow it.

            // Remove it from hash chain first.

            shadowIdx = cur;

            // Remove the shadowed symbol from the bucket chain.

            if tab.buckets[bucket] == cur {

                tab.buckets[bucket] = tab.symbols[cur].next;

            }

            break;

        }

        cur = tab.symbols[cur].next;

    }

    let idx = tab.symbolCount;

    tab.symbols[idx] = Symbol {

        nameHash: h,

        value,

        depth: tab.scopeDepth,

        next: tab.buckets[bucket],

        shadow: shadowIdx,

    };

    tab.buckets[bucket] = idx;

    tab.symbolCount += 1;

    return idx;

}

/// Look up a symbol by name. Returns the value if found.

fn lookup(tab: *SymTab, name: *[u8]) -> ?i32 {

    let h = hashName(name);

    let bucket = h % HASH_SIZE;

    let mut cur = tab.buckets[bucket];

    while cur != NIL {

        if tab.symbols[cur].nameHash == h {

            return tab.symbols[cur].value;

        }

        cur = tab.symbols[cur].next;

    }

    return nil;

}

/// Update a symbol's value. Returns true if the symbol was found.

fn update(tab: *mut SymTab, name: *[u8], newValue: i32) -> bool {

    let h = hashName(name);

    let bucket = h % HASH_SIZE;

    let mut cur = tab.buckets[bucket];

    while cur != NIL {

        if tab.symbols[cur].nameHash == h {

            tab.symbols[cur].value = newValue;

            return true;

        }

        cur = tab.symbols[cur].next;

    }

    return false;

}

/// Test basic define and lookup.

fn testBasic(tab: *mut SymTab) -> i32 {

    init(tab);

    pushScope(tab);

    define(tab, "x", 10);

    define(tab, "y", 20);

    define(tab, "z", 30);

    let x = lookup(tab, "x") else {

        return 1;

    };

    assert x == 10;

    let y = lookup(tab, "y") else {

        return 3;

    };

    assert y == 20;

    let z = lookup(tab, "z") else {

        return 5;

    };

    assert z == 30;

    // Lookup nonexistent symbol.

    if let val = lookup(tab, "w") {

        return 7;

    }

    popScope(tab);

    return 0;

}

/// Test scope shadowing.

fn testShadowing(tab: *mut SymTab) -> i32 {

    init(tab);

    pushScope(tab);

    define(tab, "x", 1);

    // Verify outer x.

    let x1 = lookup(tab, "x") else {

        return 1;

    };

    assert x1 == 1;

    // Push inner scope, shadow x.

    pushScope(tab);

    define(tab, "x", 2);

    let x2 = lookup(tab, "x") else {

        return 3;

    };

    assert x2 == 2;

    // Pop inner scope, x should revert.

    popScope(tab);

    let x3 = lookup(tab, "x") else {

        return 5;

    };

    assert x3 == 1;

    popScope(tab);

    return 0;

}

/// Test deep nesting with shadowing.

fn testDeepNesting(tab: *mut SymTab) -> i32 {

    init(tab);

    // Define x at each of 8 scope levels.

    let mut i: u32 = 0;

    while i < 8 {

        pushScope(tab);

        define(tab, "x", i as i32 * 10);

        i += 1;

    }

    // x should be the innermost value.

    let x = lookup(tab, "x") else {

        return 1;

    };

    assert x == 70;

    // Pop scopes one by one and check.

    i = 7;

    while i > 0 {

        popScope(tab);

        let val = lookup(tab, "x") else {

            return 3;

        };

        let expected = (i - 1) as i32 * 10;

        assert val == expected;

        i -= 1;

    }

    popScope(tab);

    return 0;

}

/// Test multiple symbols per scope.

fn testMultipleSymbols(tab: *mut SymTab) -> i32 {

    init(tab);

    pushScope(tab);

    // Define a bunch of symbols.

    let names: [*[u8]; 8] = ["a", "bb", "ccc", "dddd", "eeeee", "ff", "ggg", "h"];

    let values: [i32; 8] = [1, 2, 3, 4, 5, 6, 7, 8];

    for name, i in names {

        define(tab, name, values[i]);

    }

    // Verify all of them.

    let mut sum: i32 = 0;

    for name, i in names {

        if let val = lookup(tab, name) {

            sum += val;

        } else {

            return 1;

        }

    }

    // 1+2+3+4+5+6+7+8 = 36

    assert sum == 36;

    popScope(tab);

    return 0;

}

/// Test update functionality.

fn testUpdate(tab: *mut SymTab) -> i32 {

    init(tab);

    pushScope(tab);

    define(tab, "counter", 0);

    // Increment counter 10 times.

    let mut i: u32 = 0;

    while i < 10 {

        let cur = lookup(tab, "counter") else {

            return 1;

        };

        assert update(tab, "counter", cur + 1);

        i += 1;

    }

    let finalVal = lookup(tab, "counter") else {

        return 3;

    };

    assert finalVal == 10;

    // Update nonexistent symbol should fail.

    if update(tab, "nonexistent", 99) {

        return 5;

    }

    popScope(tab);

    return 0;

}

/// Test scope isolation: symbols in popped scopes are gone.

fn testScopeIsolation(tab: *mut SymTab) -> i32 {

    init(tab);

    pushScope(tab);

    define(tab, "outer", 1);

    pushScope(tab);

    define(tab, "inner", 2);

    // Both visible.

    if let val = lookup(tab, "outer") {

        assert val == 1;

    } else {

        return 2;

    }

    if let val = lookup(tab, "inner") {

        assert val == 2;

    } else {

        return 4;

    }

    popScope(tab);

    // outer still visible, inner gone.

    if let val = lookup(tab, "outer") {

        assert val == 1;

    } else {

        return 6;

    }

    if let val = lookup(tab, "inner") {

        return 7;

    }

    popScope(tab);

    return 0;

}

/// Test interleaved defines and lookups across scopes using while-let.

fn testInterleaved(tab: *mut SymTab) -> i32 {

    init(tab);

    pushScope(tab);

    define(tab, "a", 100);

    define(tab, "b", 200);

    pushScope(tab);

    define(tab, "a", 111);

    define(tab, "c", 300);

    // Verify values with expected lookup results.

    let queries: [*[u8]; 4] = ["a", "b", "c", "d"];

    let expected: [?i32; 4] = [111, 200, 300, nil];

    let mut failures: u32 = 0;

    for name, i in queries {

        let result = lookup(tab, name);

        if let exp = expected[i] {

            // We expect a value.

            if let r = result {

                if r != exp {

                    failures += 1;

                }

            } else {

                failures += 1;

            }

        } else {

            // We expect nil.

            if let _ = result {

                failures += 1;

            }

        }

    }

    if failures != 0 {

        return failures as i32;

    }

    popScope(tab);

    popScope(tab);

    return 0;

}

@default fn main() -> i32 {

    let mut symbols: [Symbol; 256] = [Symbol { nameHash: 0, value: 0, depth: 0, next: NIL, shadow: NIL }; 256];

    let mut scopes: [ScopeMarker; 16] = [ScopeMarker { symbolCount: 0 }; 16];

    let mut buckets: [u32; 64] = [NIL; 64];

    let mut tab = SymTab {

        symbols: &mut symbols[..],

        symbolCount: 0,

        scopes: &mut scopes[..],

        scopeDepth: 0,

        buckets: &mut buckets[..],

    };

    let r1 = testBasic(&mut tab);

    if r1 != 0 {

        return 10 + r1;

    }

    let r2 = testShadowing(&mut tab);

    if r2 != 0 {

        return 20 + r2;

    }

    let r3 = testDeepNesting(&mut tab);

    if r3 != 0 {

        return 30 + r3;

    }

    let r4 = testMultipleSymbols(&mut tab);

    if r4 != 0 {

        return 40 + r4;

    }

    let r5 = testUpdate(&mut tab);

    if r5 != 0 {

        return 50 + r5;

    }

    let r6 = testScopeIsolation(&mut tab);

    if r6 != 0 {

        return 60 + r6;

    }

    let r7 = testInterleaved(&mut tab);

    if r7 != 0 {

        return 70 + r7;

    }

    return 0;

}