Tabela de Simbolos

Tabela de símbolos para:
  def calcular(taxa: float, bonus: float) -> float:
      resultado = taxa * 100 + bonus
      return resultado

Nome         | Tipo     | Escopo     | Categoria  | Offset | Linha
-------------|----------|------------|------------|--------|------
calcular     | function | global     | função     | —      | 1
taxa         | float    | calcular   | parâmetro  | 0      | 1
bonus        | float    | calcular   | parâmetro  | 8      | 1
resultado    | float    | calcular   | local      | 16     | 2

Fases que consultam a tabela:
  Léxica:    insere identificadores encontrados
  Sintática: associa declarações a entradas
  Semântica: verifica tipos, escopos, uso antes de declaração
  Código:    resolve offsets para endereços de memória

1. Lista Linear (simples, lenta)
   insert: O(1)  |  lookup: O(n)
   Adequada apenas para programas muito pequenos.

2. Hash Table (padrão industrial)
   insert: O(1) amortizado  |  lookup: O(1) amortizado
   Usada em GCC, Clang, javac, CPython.
   Cada escopo mantém sua própria hash table.

3. Árvore Binária de Busca (BST)
   insert: O(log n)  |  lookup: O(log n)
   Preserva ordem lexicográfica — útil para geração
   de listagens de símbolos ordenadas.

Comparação prática (programa com ~10.000 identificadores):
  Lista:    ~50.000.000 comparações (lookup médio = n/2)
  Hash:     ~10.000 comparações (lookup médio = 1)
  BST:      ~130.000 comparações (lookup médio = log₂n)

/* Tabela de Símbolos — implementação com hash table */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 211  /* primo — reduz colisões */

typedef enum { CAT_VAR, CAT_PARAM, CAT_FUNC, CAT_TYPE } Category;

typedef struct Symbol {
    char *name;
    char *type;
    Category category;
    int scope_level;
    int offset;
    int line;
    struct Symbol *next;  /* encadeamento para colisões */
} Symbol;

static Symbol *table[TABLE_SIZE];
static int current_scope = 0;

/* Função hash de Daniel J. Bernstein (djb2) */
unsigned int hash(const char *s) {
    unsigned int h = 5381;
    while (*s)
        h = ((h << 5) + h) + *s++;
    return h % TABLE_SIZE;
}

void sym_insert(const char *name, const char *type,
                Category cat, int offset, int line) {
    unsigned int idx = hash(name);
    Symbol *sym = malloc(sizeof(Symbol));
    sym->name = strdup(name);
    sym->type = strdup(type);
    sym->category = cat;
    sym->scope_level = current_scope;
    sym->offset = offset;
    sym->line = line;
    sym->next = table[idx];  /* insere no início da lista */
    table[idx] = sym;
}

Symbol* sym_lookup(const char *name) {
    unsigned int idx = hash(name);
    Symbol *sym = table[idx];
    while (sym) {
        if (strcmp(sym->name, name) == 0)
            return sym;  /* mais recente primeiro = escopo correto */
        sym = sym->next;
    }
    return NULL;
}

void sym_enter_scope(void) { current_scope++; }

void sym_exit_scope(void) {
    /* Remove todos os símbolos do escopo atual */
    for (int i = 0; i < TABLE_SIZE; i++) {
        while (table[i] && table[i]->scope_level == current_scope) {
            Symbol *old = table[i];
            table[i] = old->next;
            free(old->name);
            free(old->type);
            free(old);
        }
    }
    current_scope--;
}

Cadeia de escopos para o programa:

  int x = 10;                    ← escopo global
  void foo() {                   ← escopo foo (nível 1)
      float x = 3.14;            ← shadowing: x local esconde x global
      if (x > 0) {               ← escopo if (nível 2)
          int y = x + 1;         ← x resolve para float (nível 1)
          {                      ← escopo bloco (nível 3)
              char x = 'A';      ← shadowing novamente
              print(x);          ← resolve para char (nível 3)
          }
          print(x);              ← resolve para float (nível 1)
      }
  }

  Representação da cadeia:
  [bloco 3] → [if 2] → [foo 1] → [global 0]
     char x      int y     float x     int x

  lookup("x") no bloco 3: encontra char x (nível 3) — para
  lookup("y") no bloco 3: não acha → sobe → encontra int y (nível 2)
  lookup("x") após sair do bloco 3: encontra float x (nível 1)

from dataclasses import dataclass, field
from typing import Optional, Dict, List

@dataclass
class SymbolInfo:
    """Atributos de um símbolo na tabela."""
    name: str
    type: str
    category: str    # 'var', 'param', 'func', 'type'
    offset: int = 0
    line: int = 0
    is_initialized: bool = False

class SymbolTable:
    """Tabela de símbolos com escopos aninhados."""

    def __init__(self, parent=None, scope_name="global", level=0):
        self.symbols: Dict[str, SymbolInfo] = {}
        self.parent: Optional[SymbolTable] = parent
        self.scope_name = scope_name
        self.level = level
        self.children: List[SymbolTable] = []
        self._next_offset = 0

    def define(self, name, type_name, category='var', line=0):
        """Define um símbolo no escopo atual."""
        if name in self.symbols:
            raise NameError(
                f"Linha {line}: '{name}' já definido em '{self.scope_name}' "
                f"(declaração anterior na linha {self.symbols[name].line})"
            )
        info = SymbolInfo(
            name=name, type=type_name, category=category,
            offset=self._next_offset, line=line
        )
        self.symbols[name] = info
        self._next_offset += 8  # alinhamento de 8 bytes
        return info

    def lookup(self, name):
        """Busca um símbolo: escopo atual → pai → avô → ..."""
        if name in self.symbols:
            return self.symbols[name]
        if self.parent:
            return self.parent.lookup(name)
        raise NameError(f"'{name}' não definido em nenhum escopo")

    def lookup_local(self, name):
        """Busca apenas no escopo atual (sem subir)."""
        return self.symbols.get(name)

    def enter_scope(self, name):
        """Cria e retorna um escopo filho."""
        child = SymbolTable(
            parent=self, scope_name=name, level=self.level + 1
        )
        self.children.append(child)
        return child

    def dump(self, indent=0):
        """Imprime a tabela para depuração."""
        prefix = "  " * indent
        print(f"{prefix}Escopo: {self.scope_name} (nível {self.level})")
        for name, info in self.symbols.items():
            print(f"{prefix}  {name}: {info.type} ({info.category}, offset={info.offset})")
        for child in self.children:
            child.dump(indent + 1)

# Demonstração completa
global_scope = SymbolTable()
global_scope.define('PI', 'float', 'const', line=1)
global_scope.define('calcular', '(float,float)->float', 'func', line=3)

func_scope = global_scope.enter_scope('calcular')
func_scope.define('taxa', 'float', 'param', line=3)
func_scope.define('bonus', 'float', 'param', line=3)
func_scope.define('resultado', 'float', 'var', line=4)

# Resolver 'PI' de dentro de func_scope — sobe a cadeia
print(func_scope.lookup('PI'))       # encontra no escopo pai
print(func_scope.lookup('taxa'))     # encontra no escopo atual
global_scope.dump()
# Escopo: global (nível 0)
#   PI: float (const, offset=0)
#   calcular: (float,float)->float (func, offset=8)
#   Escopo: calcular (nível 1)
#     taxa: float (param, offset=0)
#     bonus: float (param, offset=8)
#     resultado: float (var, offset=16)

Erros detectados pela tabela de símbolos:

1. Variável não declarada (lookup falha em todos os escopos)
   int y = x + 1;    ← erro: 'x' não definido

2. Declaração duplicada (insert encontra nome já existente)
   int x = 5;
   float x = 3.14;   ← erro: 'x' já definido neste escopo

3. Uso antes de declaração (em linguagens como C)
   y = x + 1;
   int x = 5;        ← erro: 'x' usado antes de ser declarado

4. Tipo incompatível (lookup retorna tipo diferente do esperado)
   int x = "hello";  ← erro: não pode atribuir string a int

5. Shadowing não intencional (aviso — não erro)
   int x = 10;
   void f() {
     float x = 3.14; ← aviso: 'x' sombra declaração na linha 1
   }

class SemanticChecker:
    """Verificador semântico usando a tabela de símbolos."""

    def __init__(self, symtab):
        self.symtab = symtab
        self.errors = []
        self.warnings = []

    def check_declaration(self, name, type_name, line):
        """Verifica e registra uma declaração."""
        # Checar shadowing (aviso)
        if self.symtab.parent:
            try:
                outer = self.symtab.parent.lookup(name)
                self.warnings.append(
                    f"Linha {line}: '{name}' oculta declaração da linha {outer.line}"
                )
            except NameError:
                pass

        # Registrar no escopo atual
        try:
            self.symtab.define(name, type_name, line=line)
        except NameError as e:
            self.errors.append(str(e))

    def check_use(self, name, line):
        """Verifica o uso de um identificador."""
        try:
            info = self.symtab.lookup(name)
            if not info.is_initialized:
                self.warnings.append(
                    f"Linha {line}: '{name}' pode não estar inicializado"
                )
            return info
        except NameError:
            self.errors.append(f"Linha {line}: '{name}' não declarado")
            return None

class HarnessSymbolTable:
    """Tabela de símbolos para o namespace do harness.os.

    Hierarquia de resolução:
      project → domain → concern → knowledge

    Exemplo de resolução:
      "harness-os/build/governance/commit-hygiene"
       ^project   ^domain ^concern   ^knowledge
    """

    def __init__(self):
        self.projects = {}  # slug → project info
        self.tools = {}     # tool_name → tool info (MCP)

    def register_project(self, slug, info):
        self.projects[slug] = {
            'info': info,
            'domains': {},
        }

    def register_domain(self, project_slug, domain_name, info):
        proj = self.projects[project_slug]
        proj['domains'][domain_name] = {
            'info': info,
            'concerns': {},
        }

    def resolve(self, path):
        """Resolve um caminho como 'harness-os/build/governance'."""
        parts = path.split('/')
        current = self.projects.get(parts[0])
        if not current:
            raise NameError(f"Projeto '{parts[0]}' não encontrado")
        if len(parts) > 1:
            current = current['domains'].get(parts[1])
            if not current:
                raise NameError(f"Domain '{parts[1]}' não encontrado")
        if len(parts) > 2:
            current = current['concerns'].get(parts[2])
            if not current:
                raise NameError(f"Concern '{parts[2]}' não encontrado")
        return current

    def register_tool(self, name, schema):
        """Registra uma tool MCP (análogo a declaração de função)."""
        self.tools[name] = schema

    def resolve_tool(self, name):
        """Resolve uma tool MCP por nome."""
        if name not in self.tools:
            raise NameError(f"Tool '{name}' não registrada")
        return self.tools[name]