Tabla de Símbolos y String Interning

Archivo: src/symbol_table.rs

En el diseño de lenguajes de programación, los identificadores (nombres de variables, funciones, clases, etc.) se repiten constantemente por todo el código fuente. Comparar nombres usando cadenas de caracteres tradicionales (con strcmp u operaciones similares) es lento ($O(n)$ en base al tamaño de la cadena) y consume mucha memoria debido a duplicaciones.

Para resolver esto de forma óptima, Forja implementa una Tabla de Símbolos global con String Interning. Esta técnica almacena únicamente una copia única de cada cadena en memoria y representa cada una mediante un identificador numérico liviano de 32 bits (SymId). Esto permite realizar comparaciones sintácticas y semánticas en tiempo constante ($O(1)$) mediante simples comparaciones de enteros.

Estructuras Clave

struct SymId

pub struct SymId(pub u32);

• ¿Por qué?: Actúa como un puntero conceptual seguro a la cadena real guardada en la tabla de símbolos.
• ¿Cómo?: Envuelve una variable numérica entera simple u32. Implementa rasgos como Copy, PartialEq, y Hash para posibilitar comparaciones rápidas en mapas hash y pilas.

struct SymbolTable

pub struct SymbolTable &brace;
    strings: Vec<Rc<str>>,
    lookup: HashMap<Rc<str>, SymId>,
}

• strings: Vector de punteros contados por referencia (Rc) que mapea un SymId (representado por el índice en el vector) a su correspondiente string original.
• lookup: Mapa hash inverso utilizado para verificar en tiempo mínimo si una cadena entrante ya ha sido internada en la tabla.

Desglose de Funciones de SymbolTable

pub fn new() -> Self

• ¿Por qué?: Constructor principal de la tabla de símbolos.
• ¿Cómo?: Inicializa colecciones vacías en memoria.

pub fn intern(&mut self, s: &str) -> SymId

• ¿Por qué?: Registrar una cadena de texto en la tabla y obtener su identificador numérico único. Si la cadena ya existía, devuelve el identificador anteriormente asignado sin consumir memoria adicional.
• ¿Cómo?:
  1. Crea temporalmente un Rc<str> a partir del string s.
  2. Busca en el mapa hash lookup. Si lo encuentra, retorna el SymId asociado.
  3. Si no existe, calcula el nuevo ID como el tamaño actual de strings (casteado a u32).
  4. Pushea el Rc<str> al vector strings y lo registra en el mapa lookup.
  5. Retorna el nuevo SymId.
• ¿Para qué?: Utilizado por el Lexer y el Parser para convertir identificadores de texto en tokens de SymId eficientes.

pub fn intern_rc(&mut self, s: &Rc<str>) -> SymId

• ¿Por qué?: Variante optimizada de intern() para cuando el llamador ya posee una cadena contada por referencia. Evita allocations innecesarias en el heap.
• ¿Cómo?: Realiza el mismo flujo de verificación de lookup mapeando el puntero Rc directamente.

pub fn get(&self, id: SymId) -> &str

• ¿Por qué?: Recuperar la cadena de caracteres original a partir de su identificador numérico (resolución inversa de símbolos).
• ¿Cómo?: Accede al vector strings utilizando el entero interno del SymId como índice. La operación es segura y ultrarrápida ($O(1)$).
• ¿Para qué?: Usado por el generador de código, desensamblador y sistema de reporte de errores para imprimir los nombres de variables o funciones reales de cara al usuario.

pub fn len(&self) -> usize

• ¿Por qué?: Conocer la cantidad total de símbolos únicos internados.
• ¿Cómo?: Retorna el número de elementos en el vector strings.