# ax-sym

High-performance **scoped symbol table** for compiler front-ends, linters, and LSP servers — backed by [`axhash-map`](https://crates.io/crates/axhash-map) (AES-NI accelerated hashing).

[![Crates.io](https://img.shields.io/crates/v/ax-sym.svg)](https://crates.io/crates/ax-sym)
[![Docs.rs](https://docs.rs/ax-sym/badge.svg)](https://docs.rs/ax-sym)
[![License: MIT](https://img.shields.io/badge/License-MIT-blue.svg)](LICENSE)

---

## Why ax-sym?

Name resolution in a compiler repeatedly hashes and looks up identifiers — thousands of times per source file.  `ax-sym` replaces the naive `Vec<HashMap<String, _>>` pattern with a stack of **`AxHashMap`** scopes, shaving off hashing overhead per lookup via AES-NI acceleration.

```text
┌──────────────────────────────────────┐
│  ScopedSymbolTable                   │
│  ┌──────────────────────────────┐    │
│  │ scope[2]  (innermost block)  │ ← push_scope / pop_scope
│  │  "x" → SymbolData { id, … } │    │
│  ├──────────────────────────────┤    │
│  │ scope[1]  (function body)    │    │
│  │  "n" → SymbolData { … }     │    │
│  ├──────────────────────────────┤    │
│  │ scope[0]  (global / module)  │    │
│  │  "println" → SymbolData {…}  │    │
│  └──────────────────────────────┘    │
│  Each scope = AxHashMap<String, SymbolData>  │
└──────────────────────────────────────┘
```

## Ecosystem

| Crate | Description |
|---|---|
| `axhash` | High-performance hashing engine (AES-NI) |
| `axhash-map` | Fast HashMap/HashSet backed by `hashbrown` |
| `axhash-indexmap` | Ordered maps with AxHash |
| `axhash-dashmap` | Concurrent DashMap powered by AxHash |
| **`ax-sym`** | **Scoped symbol table for compilers** |

---

## Performance characteristics

| Operation | Complexity | Notes |
|---|---|---|
| `define` | O(1) amortised | Single `AxHashMap::insert` |
| `resolve` (depth 0) | O(1) | Symbol in innermost scope — one hash probe |
| `resolve` (depth d) | O(d) | Walk d scopes; each probe is AES-NI fast |
| `push_scope` | O(1) amortised | Append pre-allocated scope to stack |
| `pop_scope` | O(n) | Drop n symbols in the popped scope |

`resolve` on a scope stack of depth 8 with 50 symbols per scope outperforms an equivalent naïve `Vec<std::collections::HashMap<String, _>>` stack, because every hash computation uses ~1 AES round trip instead of a full SipHash pipeline.

---

## Installation

```toml
[dependencies]
ax-sym = "0.1"
```

---

## Quick start

```rust
use ax_sym::{ScopedSymbolTable, SymbolData, SymbolKind, SourceLocation};

let mut table = ScopedSymbolTable::new();

let loc = SourceLocation::new(0, 1, 1);

// Define in the global scope
table.define("println".to_string(),
    SymbolData::new(0, SymbolKind::Function, loc).public());

// Enter a function body scope
table.push_scope();
table.define("n".to_string(), SymbolData::new(1, SymbolKind::Variable, loc));

// Enter an inner block scope
table.push_scope();
table.define("x".to_string(), SymbolData::new(2, SymbolKind::Variable, loc));

// resolve() searches innermost → outermost
assert!(table.resolve("x").is_some());
assert!(table.resolve("n").is_some());
assert!(table.resolve("println").is_some());
assert!(table.resolve("undefined").is_none());

// Leave the inner block
table.pop_scope();
assert!(table.resolve("x").is_none());   // x no longer in scope
assert!(table.resolve("n").is_some());   // n still visible
```

---

## API reference

### Constructors

| Method | Description |
|---|---|
| `ScopedSymbolTable::new()` | Single global scope, 64-symbol capacity per scope |
| `ScopedSymbolTable::with_scope_capacity(n)` | Global scope pre-allocated for `n` symbols |
| `ScopedSymbolTable::with_capacity(depth, n)` | Pre-allocate for `depth` scopes of `n` symbols each |

### Scope management

| Method | Returns | Description |
|---|---|---|
| `push_scope()` | `()` | Enter a new lexical scope |
| `pop_scope()` | `bool` | Leave current scope; `false` if already at global |
| `depth()` | `usize` | 0 = global scope only |
| `scope_count()` | `usize` | Total active scope count |

### Symbol operations

| Method | Returns | Description |
|---|---|---|
| `define(name, data)` | `Option<SymbolData>` | Insert in innermost scope; returns previous binding if re-declared |
| `define_symbol(name, kind, loc)` | `u32` | Shorthand — auto-assigns id, returns it |
| `resolve(name)` | `Option<&SymbolData>` | Innermost → outermost search (hot path) |
| `resolve_with_depth(name)` | `Option<ResolveResult>` | Like `resolve`, also returns depth at which found |
| `resolve_mut(name)` | `Option<&mut SymbolData>` | Mutable lookup — update `is_used`, etc. |
| `is_defined_locally(name)` | `bool` | Only checks the innermost scope |
| `total_symbols()` | `usize` | Sum of symbols across all active scopes |

### Diagnostics

```rust,ignore
// Emit "unused variable" warnings.
let unused = table.unused_symbols();
for (depth, name, data) in unused {
    eprintln!("warning: unused `{}` at {}:{} (depth {})",
              name, data.location.line, data.location.column, depth);
}
```

---

## Symbol metadata

```rust,ignore
pub struct SymbolData {
    pub id: u32,                    // unique monotonic id — safe to use as arena index
    pub kind: SymbolKind,           // Variable | Function | Type | Constant | Module | Other
    pub location: SourceLocation,   // { file_id, line, column } — 1-based, LSP-compatible
    pub is_used: bool,              // set via resolve_mut().mark_used()
    pub is_public: bool,            // set at construction via .public()
}
```

### `SymbolKind`

```rust,ignore
pub enum SymbolKind {
    Variable,
    Function,
    Type,
    Constant,
    Module,
    Other(String),  // extend for domain-specific categories
}
```

---

## Depth-aware resolution

`resolve_with_depth` returns the symbol and the number of scope levels walked — useful for closure capture analysis and de-Bruijn index generation:

```rust
use ax_sym::{ScopedSymbolTable, SymbolData, SymbolKind, SourceLocation};

let mut table = ScopedSymbolTable::new();
let loc = SourceLocation::new(0, 1, 1);

table.define("outer".to_string(), SymbolData::new(0, SymbolKind::Variable, loc));
table.push_scope();
table.push_scope();

let result = table.resolve_with_depth("outer").unwrap();
assert_eq!(result.depth, 2);   // found 2 scopes up from innermost
```

---

## Compiler pattern: mark-as-used

```rust
use ax_sym::{ScopedSymbolTable, SymbolData, SymbolKind, SourceLocation};

let mut table = ScopedSymbolTable::new();
let loc = SourceLocation::new(0, 1, 1);

table.define("x".to_string(), SymbolData::new(0, SymbolKind::Variable, loc));

// At each reference site: mark the symbol as used.
if let Some(sym) = table.resolve_mut("x") {
    sym.mark_used();
}

// After type-checking: warn about anything still unused.
for (_depth, name, _data) in table.unused_symbols() {
    eprintln!("warning: unused variable `{}`", name);
}
```

---

## Pre-allocation for large files

Tune the initial capacity to your language's typical nesting characteristics:

```rust
use ax_sym::ScopedSymbolTable;

// Typical Rust function: up to 8 levels of block nesting,
// ~50 locals per scope — no reallocations during a normal function.
let mut table = ScopedSymbolTable::with_capacity(8, 50);
```

---

## Benchmarks

Run the full benchmark suite:

```sh
cargo bench --bench symbol_table
# HTML reports → target/criterion/
```

Five scenarios, each comparing `ScopedSymbolTable` against a naïve
`Vec<std::collections::HashMap<String, SymbolData>>` baseline:

| Benchmark | Description |
|---|---|
| `define` | Fill N symbols across a realistic scope stack |
| `resolve_hit` | Resolve N times — every name exists (hot path) |
| `resolve_miss` | Resolve N times — name never found (cold path) |
| `resolve_deep_outer` | Name lives in global scope; must walk all scopes |
| `mixed_workload` | Interleaved define + resolve (simulates a type-checker loop) |

---

## License

MIT — see [LICENSE](LICENSE).
