//! returns: 0
//! 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;
}