> ## Documentation Index
> Fetch the complete documentation index at: https://docs.chameleondb.dev/llms.txt
> Use this file to discover all available pages before exploring further.

# Type Checker

> Static analysis and validation for schema ASTs

# Type Checker

The type checker validates the parsed AST before runtime, catching errors like invalid relations, missing primary keys, and annotation misuse. It runs after parsing and before schema registration in the vault.

## Overview

Validation is organized into three specialized modules:

1. **Relations** (`relations.rs`) - Entity references and foreign key consistency
2. **Constraints** (`constraints.rs`) - Primary keys and annotation rules
3. **Orchestration** (`mod.rs`) - Pipeline coordination and error reporting

## Architecture

```
Parsed AST
    ↓
Type Check Pipeline
    ├── Check duplicate entities
    ├── Check duplicate fields
    ├── Check relations (relations.rs)
    │   ├── Target entity exists?
    │   ├── Foreign key exists?
    │   └── HasMany requires 'via'?
    ├── Check circular dependencies (relations.rs)
    │   └── DFS cycle detection
    ├── Check primary keys (constraints.rs)
    │   ├── Exactly one per entity?
    │   └── No composite keys?
    └── Check annotations (constraints.rs)
        ├── @vector only on vector(N)?
        └── No annotations on primary/unique?
    ↓
TypeCheckResult { errors: Vec<TypeCheckError> }
    ↓
Valid: errors.is_empty() == true
```

## Entry Point

Location: `chameleon-core/src/typechecker/mod.rs:36`

```rust theme={null}
pub fn type_check(schema: &Schema) -> TypeCheckResult {
    let mut errors: Vec<TypeCheckError> = Vec::new();
    
    // 1. Check for duplicate entities
    // 2. Check for duplicate fields
    // 3. Check relations
    errors.extend(relations::check_relations(schema));
    errors.extend(relations::check_circular_dependencies(schema));
    
    // 4. Check constraints
    errors.extend(constraints::check_primary_keys(schema));
    errors.extend(constraints::check_annotations(schema));
    
    TypeCheckResult { errors }
}
```

**Key characteristics:**

* **Non-short-circuiting**: Collects all errors, not just the first
* **Zero allocation** (where possible): Borrows schema, doesn't modify
* **Deterministic**: Same schema always produces same errors in same order

## TypeCheckResult

Location: `chameleon-core/src/typechecker/mod.rs:9`

```rust theme={null}
#[derive(Debug, Clone)]
pub struct TypeCheckResult {
    pub errors: Vec<TypeCheckError>,
}

impl TypeCheckResult {
    pub fn is_valid(&self) -> bool {
        self.errors.is_empty()
    }
    
    pub fn error_report(&self) -> String {
        if self.is_valid() {
            return "✅ Schema is valid".to_string();
        }
        
        let mut report = format!("❌ Found {} error(s):\n\n", self.errors.len());
        for (i, error) in self.errors.iter().enumerate() {
            report.push_str(&format!("  {}. {}\n", i + 1, error));
        }
        report
    }
}
```

**Example report:**

```
❌ Found 3 error(s):

  1. Entity 'User' has no primary key
  2. Entity 'Post' references unknown entity 'Comment' in relation 'comments'
  3. Field 'embedding' in 'Product' uses @vector but type is 'String', expected vector(N)
```

## Relations Validation

Location: `chameleon-core/src/typechecker/relations.rs`

### Check Relations

```rust theme={null}
pub fn check_relations(schema: &Schema) -> Vec<TypeCheckError> {
    let mut errors = Vec::new();
    
    for entity in &schema.entities {
        for (_, relation) in &entity.relations {
            // 1. Target entity exists?
            if schema.get_entity(&relation.target_entity).is_none() {
                errors.push(TypeCheckError::UnknownRelationTarget {
                    entity: entity.name.clone(),
                    relation: relation.name.clone(),
                    target: relation.target_entity.clone(),
                });
                continue;
            }
            
            // 2. Foreign key exists in target entity?
            if let Some(fk) = &relation.foreign_key {
                let target_entity = schema.get_entity(&relation.target_entity).unwrap();
                if !target_entity.fields.contains_key(fk) {
                    errors.push(TypeCheckError::InvalidForeignKey { ... });
                }
            }
            
            // 3. HasMany relations MUST have a foreign key
            if relation.kind == RelationKind::HasMany && relation.foreign_key.is_none() {
                errors.push(TypeCheckError::MissingForeignKey { ... });
            }
        }
    }
    
    errors
}
```

**Checks performed:**

* `UnknownRelationTarget` - Target entity doesn't exist
* `InvalidForeignKey` - Foreign key field doesn't exist in target
* `MissingForeignKey` - HasMany without `via` clause

### Circular Dependency Detection

```rust theme={null}
pub fn check_circular_dependencies(schema: &Schema) -> Vec<TypeCheckError> {
    let mut errors = Vec::new();
    let mut visited: Vec<String> = Vec::new();
    let mut in_stack: Vec<String> = Vec::new();
    
    for entity in &schema.entities {
        if !visited.contains(&entity.name) {
            if let Some(cycle) = dfs(schema, &entity.name, &mut visited, &mut in_stack) {
                errors.push(TypeCheckError::CircularDependency { cycle });
            }
        }
    }
    
    errors
}
```

**Algorithm: Depth-First Search (DFS)**

Location: `chameleon-core/src/typechecker/relations.rs:64`

```rust theme={null}
fn dfs(
    schema: &Schema,
    current: &str,
    visited: &mut Vec<String>,
    in_stack: &mut Vec<String>,
) -> Option<Vec<String>> {
    visited.push(current.to_string());
    in_stack.push(current.to_string());
    
    if let Some(entity) = schema.get_entity(current) {
        for (_, relation) in &entity.relations {
            // Skip BelongsTo (inverse side of relation)
            if relation.kind == RelationKind::BelongsTo {
                continue;
            }
            
            let target = &relation.target_entity;
            
            if !visited.contains(target) {
                // Recurse into unvisited target
                if let Some(cycle) = dfs(schema, target, visited, in_stack) {
                    return Some(cycle);
                }
            } else if in_stack.contains(target) {
                // Cycle detected! Build cycle path
                let start = in_stack.iter().position(|n| n == target).unwrap();
                let mut cycle: Vec<String> = in_stack[start..].to_vec();
                cycle.push(target.clone());
                return Some(cycle);
            }
        }
    }
    
    in_stack.pop();
    None
}
```

**Example cycle:**

```
A → B → C → A

Error: Circular dependency detected: ["A", "B", "C", "A"]
```

**Why skip BelongsTo?**

* `BelongsTo` is the inverse of `HasOne`/`HasMany`
* It doesn't create a new dependency, just references the parent
* Example: `Post.user (BelongsTo User)` doesn't add `Post → User` edge

## Constraints Validation

Location: `chameleon-core/src/typechecker/constraints.rs`

### Primary Key Validation

```rust theme={null}
pub fn check_primary_keys(schema: &Schema) -> Vec<TypeCheckError> {
    let mut errors = Vec::new();
    
    for entity in &schema.entities {
        let primary_keys: Vec<String> = entity.fields.iter()
            .filter(|(_, field)| field.primary_key)
            .map(|(name, _)| name.clone())
            .collect();
        
        match primary_keys.len() {
            0 => errors.push(TypeCheckError::MissingPrimaryKey {
                entity: entity.name.clone(),
            }),
            1 => {} // Valid
            _ => errors.push(TypeCheckError::MultiplePrimaryKeys {
                entity: entity.name.clone(),
                fields: primary_keys,
            }),
        }
    }
    
    errors
}
```

**Rules:**

* Every entity must have **exactly one** primary key
* Composite primary keys are **not supported** in v1.0
* Primary key must be a field (not a relation)

### Annotation Validation

```rust theme={null}
pub fn check_annotations(schema: &Schema) -> Vec<TypeCheckError> {
    let mut errors = Vec::new();
    
    for entity in &schema.entities {
        for (_, field) in &entity.fields {
            if let Some(annotation) = &field.backend {
                // Rule 1: @vector only on vector(N) types
                if *annotation == BackendAnnotation::Vector {
                    if !matches!(field.field_type, FieldType::Vector(_)) {
                        errors.push(TypeCheckError::InvalidVectorAnnotation {
                            entity: entity.name.clone(),
                            field: field.name.clone(),
                            actual_type: format!("{:?}", field.field_type),
                        });
                    }
                }
                
                // Rule 2: Primary keys cannot have annotations
                if field.primary_key {
                    errors.push(TypeCheckError::AnnotationOnConstrainedField {
                        entity: entity.name.clone(),
                        field: field.name.clone(),
                        constraint: "primary".to_string(),
                        annotation: format!("{:?}", annotation).to_lowercase(),
                    });
                }
                
                // Rule 3: Unique fields cannot have annotations
                if field.unique {
                    errors.push(TypeCheckError::AnnotationOnConstrainedField {
                        entity: entity.name.clone(),
                        field: field.name.clone(),
                        constraint: "unique".to_string(),
                        annotation: format!("{:?}", annotation).to_lowercase(),
                    });
                }
            }
        }
    }
    
    errors
}
```

**Annotation rules:**

| Annotation | Allowed Types    | Constraints             |
| ---------- | ---------------- | ----------------------- |
| `@cache`   | Any              | ❌ Not on primary/unique |
| `@olap`    | Any              | ❌ Not on primary/unique |
| `@vector`  | `vector(N)` only | ❌ Not on primary/unique |
| `@ml`      | Any              | ❌ Not on primary/unique |

**Rationale:**

* Primary/unique fields must reside in the main OLTP database
* They're used for joins, indexes, and integrity constraints
* Splitting them across backends breaks referential integrity

## Error Types

Location: `chameleon-core/src/typechecker/errors.rs`

```rust theme={null}
use thiserror::Error;

#[derive(Error, Debug, Clone, PartialEq)]
pub enum TypeCheckError {
    #[error("Entity '{entity}' references unknown entity '{target}' in relation '{relation}'")]
    UnknownRelationTarget {
        entity: String,
        relation: String,
        target: String,
    },
    
    #[error("Relation '{relation}' in '{entity}' references foreign key '{foreign_key}', but '{target}' has no such field")]
    InvalidForeignKey {
        entity: String,
        relation: String,
        target: String,
        foreign_key: String,
    },
    
    #[error("HasMany relation '{relation}' in '{entity}' requires a 'via' foreign key")]
    MissingForeignKey {
        entity: String,
        relation: String,
    },
    
    #[error("Entity '{entity}' has no primary key")]
    MissingPrimaryKey {
        entity: String,
    },
    
    #[error("Entity '{entity}' has multiple primary keys: {fields:?}")]
    MultiplePrimaryKeys {
        entity: String,
        fields: Vec<String>,
    },
    
    #[error("Field '{field}' in '{entity}' uses @vector but type is '{actual_type}', expected vector(N)")]
    InvalidVectorAnnotation {
        entity: String,
        field: String,
        actual_type: String,
    },
    
    #[error("Field '{field}' in '{entity}' is {constraint} and cannot have @{annotation} annotation")]
    AnnotationOnConstrainedField {
        entity: String,
        field: String,
        constraint: String,  // "primary" or "unique"
        annotation: String,
    },
    
    #[error("Circular dependency detected: {cycle:?}")]
    CircularDependency {
        cycle: Vec<String>,
    },
    
    #[error("Duplicate entity name '{entity}' (first defined at #{first}, redefined at #{second})")]
    DuplicateEntity {
        entity: String,
        first: usize,
        second: usize,
    },
    
    #[error("Duplicate field name '{field}' in entity '{entity}'")]
    DuplicateField {
        entity: String,
        field: String,
    },
}
```

**Error design:**

* Uses `thiserror` for automatic `Display` implementation
* Structured fields for programmatic access (e.g., CI tooling)
* Human-readable messages with context

## Performance Characteristics

| Operation       | Time Complexity | Space Complexity | Notes                                    |
| --------------- | --------------- | ---------------- | ---------------------------------------- |
| Relations check | O(E × R × F)    | O(1)             | E=entities, R=relations/entity, F=fields |
| Cycle detection | O(E + R)        | O(E)             | DFS graph traversal                      |
| Primary keys    | O(E × F)        | O(1)             | Linear scan per entity                   |
| Annotations     | O(E × F)        | O(1)             | Linear scan per entity                   |
| **Total**       | **O(E × F)**    | **O(E)**         | Dominated by field scans                 |

**Benchmarks (typical schema: 20 entities, 10 fields each):**

* Type check: \~5ms
* Error report generation: \~0.5ms
* Memory overhead: \~2KB (visited sets)

## Example Usage

### Valid Schema

```rust theme={null}
use chameleon::typechecker::type_check;

let schema = build_schema(vec![
    ("User", vec![
        ("id", FieldType::UUID, true, false, None),
        ("email", FieldType::String, false, true, None),
    ], vec![
        ("posts", RelationKind::HasMany, "Post", Some("user_id")),
    ]),
    ("Post", vec![
        ("id", FieldType::UUID, true, false, None),
        ("user_id", FieldType::UUID, false, false, None),
    ], vec![
        ("user", RelationKind::BelongsTo, "User", None),
    ]),
]);

let result = type_check(&schema);
assert!(result.is_valid());
```

### Invalid Schema

```rust theme={null}
let schema = build_schema(vec![
    ("User", vec![
        ("email", FieldType::String, false, false, None), // No primary key!
    ], vec![
        ("posts", RelationKind::HasMany, "NonExistent", Some("user_id")), // Unknown target!
    ]),
]);

let result = type_check(&schema);
assert!(!result.is_valid());
assert_eq!(result.errors.len(), 2);

println!("{}", result.error_report());
// Output:
// ❌ Found 2 error(s):
//
//   1. Entity 'User' has no primary key
//   2. Entity 'User' references unknown entity 'NonExistent' in relation 'posts'
```

### Annotation Errors

```rust theme={null}
let schema = build_schema(vec![
    ("Product", vec![
        ("id", FieldType::UUID, true, false, Some(BackendAnnotation::Cache)), // Invalid!
        ("embedding", FieldType::String, false, false, Some(BackendAnnotation::Vector)), // Invalid!
    ], vec![]),
]);

let result = type_check(&schema);
assert_eq!(result.errors.len(), 2);

match &result.errors[0] {
    TypeCheckError::AnnotationOnConstrainedField { field, constraint, .. } => {
        assert_eq!(field, "id");
        assert_eq!(constraint, "primary");
    }
    _ => panic!("Unexpected error type"),
}
```

## Testing

Location: `chameleon-core/src/typechecker/mod.rs:98`

**Test coverage:**

* ✅ Valid simple schemas
* ✅ Valid schemas with relations
* ✅ Valid backend annotations
* ✅ Unknown relation targets
* ✅ Invalid foreign keys
* ✅ Missing foreign keys (HasMany)
* ✅ Missing primary keys
* ✅ Multiple primary keys
* ✅ Invalid vector annotations
* ✅ Annotations on primary keys
* ✅ Annotations on unique fields
* ✅ Circular dependencies
* ✅ Error report formatting

**Example test:**

```rust theme={null}
#[test]
fn test_circular_dependency() {
    let schema = build_schema(vec![
        ("A", vec![("id", FieldType::UUID, true, false, None)], 
              vec![("b", RelationKind::HasOne, "B", None)]),
        ("B", vec![("id", FieldType::UUID, true, false, None)], 
              vec![("c", RelationKind::HasOne, "C", None)]),
        ("C", vec![("id", FieldType::UUID, true, false, None)], 
              vec![("a", RelationKind::HasOne, "A", None)]),
    ]);
    
    let result = type_check(&schema);
    assert!(!result.is_valid());
    assert!(result.errors.iter().any(|e| matches!(e, TypeCheckError::CircularDependency { .. })));
}
```

## Integration with FFI

The type checker is exposed to Go via FFI (see [FFI Interface](/api/ffi-interface)):

Location: `chameleon-core/src/ffi/mod.rs:106`

```rust theme={null}
#[no_mangle]
pub unsafe extern "C" fn chameleon_validate_schema(
    input: *const c_char,
    error_out: *mut *mut c_char,
) -> ChameleonResult {
    let schema = parse_schema(input_str)?;
    let result = type_check(&schema);
    
    if result.is_valid() {
        return ChameleonResult::Ok;
    } else {
        // Serialize errors to JSON
        let json = serde_json::to_string(&result.errors)?;
        *error_out = CString::new(json)?.into_raw();
        return ChameleonResult::ValidationError;
    }
}
```

**JSON error format:**

```json theme={null}
{
  "valid": false,
  "errors": [
    {
      "kind": "ValidationError",
      "message": "Entity 'User' has no primary key",
      "line": null,
      "column": null
    }
  ]
}
```

## See Also

* [Parser and AST](/api/parser) - AST construction before type checking
* [FFI Interface](/api/ffi-interface) - Exposing validation to Go