Tree Traversal and Integration Testing

Unit tests prove that individual functions work. Integration tests prove that the system works. There is a vast gap between "each piece works in isolation" and "the pieces work together to solve a real problem." FlinDB crossed that gap through a deliberate testing strategy: every feature was validated not just with unit tests, but with integration tests that mimic real applications.

This article covers two interconnected topics. First, how FlinDB handles hierarchical data -- trees, recursive structures, and self-referencing entities. Second, how we tested the entire database engine through integration tests that simulate blog platforms, e-commerce systems, and todo applications.

Hierarchical Data in FlinDB

Trees are everywhere in application data. Category hierarchies in e-commerce. Organizational charts in HR systems. Comment threads in social platforms. File systems. Menu structures. Nested navigation. Any data that has a parent-child relationship forms a tree.

In the relational world, hierarchical data is notoriously difficult. The standard approaches all have significant drawbacks:

Adjacency list (each row has a parent_id column) is simple to write but expensive to query. Finding all descendants of a node requires recursive CTEs or multiple queries.

Nested sets (each row has left and right values) makes subtree queries fast but inserts and updates are expensive because they require renumbering.

Materialized path (each row stores its full path like "/1/3/7/") makes path queries fast but path strings are fragile and hard to maintain.

FlinDB takes the adjacency list approach but pairs it with graph traversal algorithms that make the expensive operations fast.

Self-Referencing Entities

In FLIN, a self-referencing entity is declared naturally:

flinentity Category {
    name: text
    parent: Category?         // Optional self-reference
}

// Build a tree
electronics = Category { name: "Electronics" }
save electronics

phones = Category { name: "Phones", parent: electronics }
save phones

smartphones = Category { name: "Smartphones", parent: phones }
save smartphones

iphones = Category { name: "iPhones", parent: smartphones }
save iphones

The parent: Category? field creates a nullable reference to the same entity type. ZeroCore stores this as an entity ID, just like any other reference. The ? makes it optional, because root nodes have no parent.

Finding Ancestors

To find all ancestors of a node (the path from a leaf to the root), you traverse the parent reference upward:

flin// Starting from "iPhones", find the path to the root
node = Category.find(iphones.id)
path = []

while node.parent != none {
    path.push(node)
    node = node.parent
}
path.push(node)  // Add the root

// path = [iPhones, Smartphones, Phones, Electronics]

In ZeroCore, this traversal uses resolve_reference() at each step:

rustlet mut path = Vec::new();
let mut current_id = start_id;

loop {
    let entity = db.find_by_id("Category", current_id)?;
    path.push(entity.clone());

    match entity.fields.get("parent") {
        Some(Value::EntityRef(_, parent_id)) => {
            current_id = *parent_id;
        }
        _ => break,  // Reached the root
    }
}

Because reference fields are automatically indexed, each find_by_id() call is O(1). The total traversal is O(d) where d is the tree depth -- typically very small (5-10 levels for most hierarchies).

Finding Descendants

Finding all descendants of a node -- all subcategories of "Electronics" -- uses the graph traversal methods from Session 166:

rustlet descendants = db.traverse("Category", electronics_id, "parent", 10)?;

The traverse() method performs a breadth-first search starting from the given node, following the parent reference in reverse (finding entities that reference the given node). The depth parameter (10) limits how deep the traversal goes, preventing infinite loops in case of accidental circular references.

Detecting Cycles

Circular references in a tree are a bug. If Category A's parent is B, B's parent is C, and C's parent is A, the hierarchy is invalid. FlinDB's cycle detection catches this:

rustlet cycles = db.find_cycles("Category", "parent")?;
if !cycles.is_empty() {
    // Report circular references
    for cycle in cycles {
        log("Circular reference detected: {:?}", cycle);
    }
}

The cycle detection uses depth-first search with a "visited" set. If DFS encounters a node that is already in the current traversal path, a cycle has been found. The complete cycle is extracted by tracing back through the path.

Topological Ordering

For dependency trees (task A depends on task B, which depends on task C), topological sort provides an execution order that respects dependencies:

flinentity Task {
    name: text
    depends_on: Task?
}

// Tasks with dependencies
deploy = Task { name: "Deploy" }
build = Task { name: "Build" }
test = Task { name: "Test", depends_on: build }
deploy_task = Task { name: "Deploy to prod", depends_on: test }

rustlet order = db.topological_sort("Task", "depends_on")?;
// Returns: [Build, Test, Deploy to prod]
// Each task appears after its dependency

Topological sort fails if cycles exist (you cannot order circular dependencies). FlinDB's implementation detects this and returns an error with the cycle path.

Integration Testing Strategy

FlinDB's integration tests are not traditional "call an API and check the response" tests. They simulate complete application scenarios, exercising the full stack from entity definition through querying and deletion.

The Blog Application Test

The blog test creates Users and Posts, verifying that the entire relationship model works end-to-end:

rust#[test]
fn test_flindb_blog_example() {
    let mut db = ZeroCore::new();

    // Register schemas
    let user_schema = EntitySchema::new("User")
        .field("name", FieldType::String)
        .field("email", FieldType::String);
    db.register_schema("User", user_schema);

    let post_schema = EntitySchema::new("Post")
        .field("title", FieldType::String)
        .field("body", FieldType::String)
        .field("author", FieldType::EntityRef("User".to_string()));
    db.register_schema("Post", post_schema);

    // Create users
    let user1 = db.save("User", None, hashmap!{
        "name" => Value::Text("Thales".into()),
        "email" => Value::Text("[email protected]".into()),
    }).unwrap();

    let user2 = db.save("User", None, hashmap!{
        "name" => Value::Text("Claude".into()),
        "email" => Value::Text("[email protected]".into()),
    }).unwrap();

    // Create posts
    let post1 = db.save("Post", None, hashmap!{
        "title" => Value::Text("Hello World".into()),
        "body" => Value::Text("First post!".into()),
        "author" => Value::EntityRef("User".to_string(), user1.id),
    }).unwrap();

    // Query posts by author
    let thales_posts = db.query("Post")
        .where_ref("author", user1.id)
        .execute()
        .unwrap();
    assert_eq!(thales_posts.len(), 1);
    assert_eq!(thales_posts[0].fields.get("title"),
        Some(&Value::Text("Hello World".into())));

    // Eager load author
    let posts_with_authors = db.query("Post")
        .with("author")
        .execute()
        .unwrap();
    // Verify author was resolved
}

This test exercises schema registration, entity creation, reference storage, reference querying, and eager loading -- five different subsystems in a single test. If any of them is broken, the test fails. If all of them work individually but fail to interoperate, the test fails. This is the value of integration testing.

The E-Commerce Test

The e-commerce test adds constraints and aggregations to the mix:

rust#[test]
fn test_flindb_ecommerce_example() {
    let mut db = ZeroCore::new();

    let product_schema = EntitySchema::new("Product")
        .field("name", FieldType::String)
        .field("category", FieldType::String)
        .field("price", FieldType::Number)
        .field("stock", FieldType::Integer)
        .check("price", "price > 0")
        .check("stock", "stock >= 0");
    db.register_schema("Product", product_schema);

    // Create products
    db.save("Product", None, hashmap!{
        "name" => Value::Text("Laptop".into()),
        "category" => Value::Text("electronics".into()),
        "price" => Value::Number(999.99),
        "stock" => Value::Int(50),
    }).unwrap();

    db.save("Product", None, hashmap!{
        "name" => Value::Text("Mouse".into()),
        "category" => Value::Text("electronics".into()),
        "price" => Value::Number(29.99),
        "stock" => Value::Int(200),
    }).unwrap();

    // Test aggregations
    let total = db.sum("Product", "price").unwrap();
    assert!((total - 1029.98).abs() < 0.01);

    let avg = db.avg("Product", "price").unwrap();
    assert!((avg - 514.99).abs() < 0.01);

    // Test group aggregation
    let by_category = db.group_sum("Product", "category", "stock").unwrap();
    assert_eq!(by_category.get("electronics"), Some(&250.0));

    // Test constraint enforcement
    let result = db.save("Product", None, hashmap!{
        "name" => Value::Text("Bad Product".into()),
        "category" => Value::Text("test".into()),
        "price" => Value::Number(-10.0),  // Violates check constraint
        "stock" => Value::Int(0),
    });
    assert!(result.is_err());
}

This test verifies that constraints, aggregations, and group operations work correctly in a realistic scenario. The negative price test at the end confirms that the constraint system actively prevents invalid data -- not just in isolation, but in the context of a multi-entity database.

The Todo Application Test

The simplest integration test is also the most important. It simulates the exact use case of FlinDB's embedded demo:

rust#[test]
fn test_flindb_todo_app() {
    let mut db = ZeroCore::new();

    let schema = EntitySchema::new("Todo")
        .field("title", FieldType::String)
        .field("done", FieldType::Boolean);
    db.register_schema("Todo", schema);

    // Create todos
    db.save("Todo", None, hashmap!{
        "title" => Value::Text("Buy milk".into()),
        "done" => Value::Bool(false),
    }).unwrap();

    db.save("Todo", None, hashmap!{
        "title" => Value::Text("Write article".into()),
        "done" => Value::Bool(true),
    }).unwrap();

    // Filter by done status
    let pending = db.query("Todo")
        .where_eq("done", Value::Bool(false))
        .execute()
        .unwrap();
    assert_eq!(pending.len(), 1);

    let completed = db.query("Todo")
        .where_eq("done", Value::Bool(true))
        .execute()
        .unwrap();
    assert_eq!(completed.len(), 1);

    // Count
    assert_eq!(db.count("Todo").unwrap(), 2);
    assert_eq!(db.count_where("Todo", |e| {
        e.fields.get("done") == Some(&Value::Bool(false))
    }).unwrap(), 1);
}

Why Integration Tests Catch What Unit Tests Miss

Unit tests verify that check_unique_constraints() returns an error for duplicate values. Integration tests verify that a duplicate email in a blog application is correctly rejected when the user tries to register, that the error message makes sense, and that the database state is unchanged after the rejection.

The difference is subtle but critical. A unit test for save() might pass even if check_unique_constraints() is never called during save() -- because the unit test calls check_unique_constraints() directly, not through save(). An integration test that creates two users with the same email will fail if the constraint check is not wired into the save path.

FlinDB's test strategy was: unit tests for algorithmic correctness (sorting, comparison, index key generation), integration tests for behavioral correctness (does the system do the right thing in a realistic scenario?). Both are necessary. Neither is sufficient alone.

The Testing Numbers

Across all FlinDB sessions, the test counts grew steadily:

Over 340 tests added for FlinDB alone. The total test suite for the FLIN project exceeded 2,400 tests -- and every one passed before any session ended.

The discipline was absolute: no feature was considered complete without tests. No session ended with failing tests. No test was skipped or ignored without a documented reason. When you are two people building a database engine -- one human, one AI -- the test suite is your safety net. It catches regressions before they reach users. It documents expected behavior better than any specification. And it gives confidence to make aggressive changes, because if the tests pass, the system works.

This is Part 12 of the "How We Built FlinDB" series, documenting how we built a complete embedded database engine for the FLIN programming language.

Series Navigation: - [065] The EAVT Storage Model - [066] Database Encryption and Configuration - [067] Tree Traversal and Integration Testing (you are here) - [068] FlinDB Hardening for Production - [069] FlinDB vs SQLite: Why We Built Our Own