diff --git a/CLAUDE.md b/CLAUDE.md index 63d61ed0b..916976657 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -4,34 +4,50 @@ This file provides guidance to Claude Code (claude.ai/code) when working with co ## Project Overview -Minigraf is a tiny, portable GQL (Graph Query Language) engine written in Rust. It's a work-in-progress project designed to run as a standalone binary, library, or WebAssembly module. +Minigraf is a tiny, portable **bi-temporal graph database with Datalog queries** written in Rust. It's designed to be the "SQLite of graph databases" - embedded, single-file, reliable, with time travel capabilities. -**Current Status: Phase 2 Complete** - Fully embeddable graph database with persistent storage: -- Property graph data model (nodes, edges, properties) -- **Persistent storage engine** (`.graph` file format) - NEW! -- **Embedded database API** (`Minigraf::open()`) - NEW! -- Storage backend abstraction (File, Memory, future IndexedDB) -- Custom GQL query parser -- Query executor with persistence integration -- Interactive REPL console -- 35+ tests, all passing +**Current Status: Phase 2 Complete → Phase 3 Starting** - Pivoting from GQL to Datalog: +- ✅ Phase 1: Property graph PoC (in-memory) +- ✅ Phase 2: Persistent storage (`.graph` file format, embedded API) +- 🎯 Phase 3: Datalog core (EAV model, recursive rules) - **NEXT** +- 🎯 Phase 4: Bi-temporal support (transaction time + valid time) +- 🎯 Phase 5: ACID + WAL (crash safety, transactions) +- 🎯 Phase 6: Performance (indexes, query optimization) +- 🎯 v1.0.0: 12-15 months -**Important**: This is a GQL-inspired implementation (~2-5% of ISO/IEC 39075:2024 spec). It is NOT fully spec-compliant and prioritizes usability over conformance. See README.md's "GQL Spec Compliance" section for detailed feature coverage and roadmap. +**Important Strategic Pivot** (January 2026): After completing Phase 2 with a GQL-inspired implementation, we pivoted to Datalog for: +1. Simpler implementation (proven patterns vs. novel GQL spec) +2. Better temporal semantics (bi-temporal is natural in Datalog) +3. Faster time-to-production (12-15 months vs. 24-30 months) +4. Unique market positioning (single-file bi-temporal Datalog doesn't exist) + +**GQL Archive**: Previous GQL implementation preserved at `archive/gql-phase-2` branch and `gql-phase-2-complete` tag. ## Core Philosophy - CRITICAL **Before implementing ANY feature or change, you MUST assess it against the design philosophy in PHILOSOPHY.md.** -Minigraf follows the "SQLite for graph databases" philosophy: +Minigraf follows the "SQLite for bi-temporal graph databases" philosophy: - **Zero-configuration** - No setup, no config files, just works - **Embedded-first** - Library not server, in-process execution - **Single-file database** - One portable `.graph` file - **Self-contained** - Minimal dependencies, small binary (<1MB goal) - **Cross-platform** - Native, WASM, mobile, embedded - **Reliability over features** - Do less, do it perfectly +- **Bi-temporal first-class** - Time travel is a core feature, not addon +- **Datalog queries** - Simpler, more powerful for graphs than SQL/GQL - **Stability** - Backwards compatibility, stable file format - **Long-term support** - Decades-long commitment +### Why Datalog? + +**Critical Context**: We chose Datalog over GQL because: +1. **Simpler** - 50 pages vs. 600-page spec +2. **Proven** - 40+ years, Datomic/XTDB production use +3. **Better for temporal** - Time is just another dimension +4. **Recursive rules** - First-class graph traversal +5. **Faster to production** - 12-15 months vs. 24-30 months + ### Philosophy Compliance Check **CRITICAL INSTRUCTION**: When the user requests a feature or change, you MUST: @@ -51,6 +67,7 @@ Minigraf follows the "SQLite for graph databases" philosophy: - Features only useful for distributed systems (violates target use cases) - Breaking changes to API or file format (violates stability) - Complex features before basics are reliable (violates reliability-first) +- Multi-file storage (violates single-file philosophy) **Your response format when detecting a violation**: ``` @@ -80,14 +97,20 @@ cargo build # Build release version (with panic=abort optimization) cargo build --release -# Run the REPL +# Run the REPL (currently GQL, will become Datalog in Phase 3) cargo run # Run tests cargo test -# Run integration tests with output +# Run specific test suite cargo test --test integration_test -- --nocapture +cargo test --test concurrency_test +cargo test --test edge_cases_test + +# Run examples +cargo run --example embedded +cargo run --example file_storage ``` ## Architecture @@ -96,142 +119,370 @@ cargo test --test integration_test -- --nocapture The codebase is organized into the following modules: -1. **Graph Module (`src/graph/`)**: - - `types.rs`: Core property graph types - - `Node`: Vertices with UUID IDs, multiple labels, and typed properties - - `Edge`: Directed edges with UUID IDs, source/target nodes, label, and properties - - `PropertyValue`: Enum supporting String, Integer, Float, Boolean, and Null types - - `storage.rs`: Thread-safe in-memory storage using `Arc>` - - CRUD operations for nodes and edges - - Query helpers: filter by labels, properties, get edges from/to nodes - -2. **Storage Module (`src/storage/`)**: Backend abstraction layer (Phase 2) - - `mod.rs`: StorageBackend trait and file format definitions +1. **Graph Module (`src/graph/`)** - Phase 1-2 (will evolve in Phase 3): + - `types.rs`: Core graph types (will become EAV model) + - Current: `Node`, `Edge`, `PropertyValue` (property graph) + - Future: `Fact`, `Entity`, `Attribute`, `Value` (EAV model) + - `storage.rs`: Thread-safe in-memory storage (Phase 1) + - Uses `Arc>` for nodes/edges + - Will migrate to fact-based storage in Phase 3 + +2. **Storage Module (`src/storage/`)** - Phase 2 (stable foundation) ✅: + - `mod.rs`: StorageBackend trait and file format - `StorageBackend` trait: Platform-agnostic storage interface - - `FileHeader`: Metadata structure for .graph files + - `FileHeader`: Metadata for `.graph` files - Page size: 4KB, Magic number: "MGRF" - - `backend/file.rs`: File-based backend for native platforms - - Single `.graph` file with page-based storage + - `backend/file.rs`: File-based backend (single `.graph` file) + - Page-based storage, cross-platform format - Supports Linux, macOS, Windows, iOS, Android - - Cross-platform format (endian-safe) - - `backend/memory.rs`: In-memory backend - - Fast, non-persistent storage for testing/embedded - - `backend/indexeddb.rs`: Future WASM browser backend - -3. **Query Module (`src/query/`)**: - - `parser.rs`: Text-based query parser supporting: - - `CREATE NODE (:Label1:Label2) {prop: value}` - Create nodes - - `CREATE EDGE (id1)-[LABEL]->(id2) {prop: value}` - Create edges - - `MATCH (:Label) [WHERE prop = value]` - Find nodes - - `MATCH -[:LABEL]->` - Find edges - - `SHOW NODES` / `SHOW EDGES` - List all entities - - `HELP` / `EXIT` - Console commands + - `backend/memory.rs`: In-memory backend for testing + - `backend/indexeddb.rs`: Future WASM browser backend (Phase 7) + - `persistent.rs`: Persistent graph storage layer + - Serialization/deserialization of property graph + - Will evolve to support EAV facts in Phase 3 + +3. **Query Module (`src/query/`)** - Phase 1-2 (will be rewritten in Phase 3): + - `parser.rs`: Query parser + - Current: GQL-inspired syntax (Phase 1-2, archived) + - Future: Datalog EDN syntax (Phase 3) - `executor.rs`: Query execution engine - - Executes parsed queries against storage - - Validates edge creation (source/target existence) - - Returns formatted results + - Current: Property graph executor + - Future: Datalog pattern matcher with recursive rules -4. **REPL Module (`src/repl.rs`)**: Interactive console +4. **REPL Module (`src/repl.rs`)** - Phase 1-2 (will be updated in Phase 3): + - Interactive console - Prompt-based interface (`minigraf>`) - - Reads user input, parses queries, executes, and displays results - - Handles EOF gracefully (src/repl.rs:27-30) for piped input - - Error handling for parse/execution errors - -5. **Library (`src/lib.rs`)**: Public API - - Exports all core types: `Node`, `Edge`, `PropertyValue`, `GraphStorage` - - Exports query functions: `parse_query`, `QueryExecutor`, `QueryResult` - - Exports storage: `StorageBackend`, `FileHeader`, `PAGE_SIZE` - - Exports REPL: `Repl` - -6. **Binary (`src/main.rs`)**: Standalone executable - - Creates in-memory storage - - Launches interactive REPL + - Handles EOF gracefully (src/repl.rs:27-30) + - Will support Datalog syntax in Phase 3 -### Storage Implementation +5. **Minigraf Module (`src/minigraf.rs`)** - Phase 2 (stable) ✅: + - Public embedded database API + - `Minigraf::open()` - Opens or creates database + - `Minigraf::execute()` - Executes queries + - `Minigraf::save()` - Explicit save + - Auto-save on drop -Minigraf uses a **layered storage architecture**: - -**High-level** (`src/graph/storage.rs`): -- `GraphStorage`: In-memory graph operations (Phase 1 PoC) -- `Arc>>` for nodes -- `Arc>>` for edges -- Thread-safe concurrent access via read/write locks -- UUIDs for automatic ID generation - -**Low-level** (`src/storage/`): Backend abstraction (Phase 2) -- `StorageBackend` trait: Platform-agnostic storage interface -- `FileBackend`: Single `.graph` file with page-based storage - - 4KB pages, cross-platform format - - Magic number "MGRF", versioned header -- `MemoryBackend`: In-memory page storage for testing -- Future: `IndexedDbBackend` for WASM +6. **Library (`src/lib.rs`)**: Public API + - Exports core types and functions + - Stable foundation for Phase 3 evolution -**Philosophy**: Following SQLite's VFS model, enabling cross-platform support (native, mobile, WASM) with the same API. +7. **Binary (`src/main.rs`)**: Standalone executable + - Launches interactive REPL + - Uses in-memory storage currently + +### Current Data Model (Phase 1-2) + +**Property Graph** (will be replaced with EAV in Phase 3): +```rust +struct Node { + id: Uuid, + labels: Vec, + properties: HashMap, +} + +struct Edge { + id: Uuid, + source: Uuid, + target: Uuid, + label: String, + properties: HashMap, +} +``` -Note: RocksDB was considered but rejected in favor of a custom implementation that aligns with the "SQLite for graphs" philosophy (single-file, self-contained, cross-platform). +### Future Data Model (Phase 3+) + +**Entity-Attribute-Value (Datalog Triple Store)**: +```rust +struct Fact { + entity: Uuid, + attribute: String, // e.g., ":person/name", ":friend" + value: Value, + tx_id: TxId, // Transaction that asserted this + asserted: bool, // true = assert, false = retract +} + +enum Value { + String(String), + Integer(i64), + Float(f64), + Boolean(bool), + Ref(Uuid), // Reference to another entity + Keyword(String), // e.g., ":person", ":status/active" + Null, +} +``` -### Query Language Syntax +**Bi-temporal Extension (Phase 4)**: +```rust +struct Fact { + entity: Uuid, + attribute: String, + value: Value, + valid_from: DateTime, // When fact became valid in real world + valid_to: DateTime, // When fact stopped being valid + tx_id: TxId, // Transaction ID + tx_time: SystemTime, // When fact was recorded + asserted: bool, +} +``` -The query language is inspired by GQL (ISO/IEC 39075:2024) but simplified for the PoC: +### Storage Implementation -``` -# Create nodes with labels and properties -CREATE NODE (:Person) {name: "Alice", age: 30} -CREATE NODE (:Person:Employee) {name: "Bob", age: 25} +**Layered Architecture**: -# Create edges between existing nodes (use node IDs) -CREATE EDGE (node-id-1)-[KNOWS]->(node-id-2) {since: 2020} +**High-level** (Phase 1-2, will evolve): +- `GraphStorage`: In-memory property graph operations +- `PersistentGraphStorage`: Serialization layer +- Will become fact-based storage in Phase 3 -# Match nodes by label -MATCH (:Person) +**Low-level** (Phase 2, stable foundation) ✅: +- `StorageBackend` trait: Platform-agnostic interface +- `FileBackend`: Single `.graph` file (4KB pages) +- `MemoryBackend`: In-memory for testing +- Future: `IndexedDbBackend` for WASM -# Match nodes with property filter -MATCH (:Person) WHERE name = "Alice" +**File Format**: +``` +Page 0: Header + - Magic: "MGRF" + - Version: u32 + - Page count: u64 + - Node count: u64 (Phase 1-2) + - Edge count: u64 (Phase 1-2) + - Fact count: u64 (Phase 3+) + - Tx counter: u64 (Phase 4+) + +Page 1+: Data + - Current: Serialized nodes/edges + - Future: EAV facts with temporal dimensions +``` -# Match edges by label -MATCH -[:KNOWS]-> +### Query Language -# Show all nodes or edges +**Current (Phase 1-2, GQL-inspired)** - Archived: +```gql +CREATE NODE (:Person) {name: "Alice", age: 30} +CREATE EDGE (id1)-[KNOWS]->(id2) {since: 2020} +MATCH (:Person) WHERE name = "Alice" SHOW NODES -SHOW EDGES +``` + +**Future (Phase 3+, Datalog)** - Target syntax: +```datalog +;; Transact facts +(transact [[:alice :person/name "Alice"] + [:alice :person/age 30] + [:alice :friend :bob]]) + +;; Simple query +(query [:find ?name + :where [?e :person/name ?name]]) + +;; Recursive rule +(rule [(reachable ?from ?to) + [?from :connected ?to]]) + +(rule [(reachable ?from ?to) + [?from :connected ?intermediate] + (reachable ?intermediate ?to)]) + +;; Bi-temporal query (Phase 4) +(query [:find ?status + :valid-at "2023-06-01" + :as-of tx-100 + :where [:alice :employment/status ?status]]) ``` ### Error Handling -- Parse errors: Reported with descriptive messages, REPL continues -- Execution errors: Validated before execution (e.g., edge endpoints must exist) -- EOF handling: REPL exits gracefully when stdin closes (for piped input/scripts) +- Parse errors: Descriptive messages, REPL continues +- Execution errors: Validated before execution +- EOF handling: REPL exits gracefully (for piped input) +- Storage errors: Result with context ## Test Coverage -The project has comprehensive test coverage: - -- **Unit tests** (19 tests): - - `src/graph/types.rs`: Node/Edge creation, PropertyValue accessors - - `src/graph/storage.rs`: CRUD operations, queries, edge relationships - - `src/query/parser.rs`: All query syntax variations +**Current Tests (Phase 1-2)**: 54 tests passing ✅ +- Unit tests: + - `src/graph/types.rs`: Node/Edge creation, PropertyValue + - `src/graph/storage.rs`: CRUD, queries, edge relationships + - `src/query/parser.rs`: GQL syntax parsing - `src/query/executor.rs`: Query execution, validation - -- **Integration tests** (`tests/integration_test.rs`): - - Complete workflow: create nodes, create edges, query, filter + - `src/storage/`: Backend operations, persistence + - `src/minigraf.rs`: Embedded API +- Integration tests: + - `tests/integration_test.rs`: Complete workflow + - `tests/concurrency_test.rs`: Thread safety + - `tests/edge_cases_test.rs`: Edge cases, dirty flags + +**Future Tests (Phase 3+)**: +- Datalog parser (EDN syntax) +- Pattern matching and unification +- Recursive rule evaluation +- Transitive closure +- Bi-temporal queries (Phase 4) +- WAL and crash recovery (Phase 5) +- Index performance (Phase 6) Run tests with: `cargo test` ## Development Notes -- **No schema file required**: The engine uses in-memory storage and doesn't require a schema on startup -- **UUID-based IDs**: All nodes and edges get automatic UUID identifiers -- **Thread-safe**: Storage can be safely shared across threads -- **Property types**: Supports String, Integer, Float, Boolean, and Null values -- **EOF handling**: REPL properly exits when stdin closes (fixed in src/repl.rs:27-30) - -## Future Work - -- Persistent storage (RocksDB integration) -- Indexes for fast property lookups -- Complex graph traversals (multi-hop paths) -- Aggregations and analytics -- Library embedding support -- WebAssembly compilation -- Transaction support -- Schema validation +### Phase 2 (Current) - Foundation Complete ✅ + +- **Storage backend abstraction** - Solid foundation for Phase 3+ +- **Single `.graph` file** - Philosophy-aligned persistent storage +- **Embedded API** - `Minigraf::open()` works like SQLite +- **UUID-based IDs** - Will continue in EAV model +- **Thread-safe** - Concurrent read/write via RwLock +- **Property types** - Will map to Value enum in Phase 3 +- **Auto-save** - On drop, works reliably +- **Cross-platform** - Endian-safe file format + +### Phase 3 (Next) - Datalog Core 🎯 + +**Migration Strategy**: +1. Add EAV types alongside existing property graph types +2. Implement Datalog parser (new module) +3. Build query executor with pattern matching +4. Add recursive rule evaluation +5. Update REPL to support both syntaxes temporarily +6. Gradually migrate tests +7. Eventually deprecate property graph types + +**Key Implementation Tasks**: +- EDN parser for Datalog syntax +- Pattern matching engine +- Variable unification +- Semi-naive evaluation for recursion +- Stratification for safe recursion + +### Philosophy-Aligned Development + +When implementing features, always ask: +1. Does this keep the single-file philosophy? +2. Does this maintain zero-configuration? +3. Does this add unnecessary complexity? +4. Is this needed for embedded use cases? +5. Does this compromise reliability? + +## Future Work (Roadmap) + +**Phase 3** (3-4 months): Datalog Core +- EAV data model +- Datalog parser (EDN syntax) +- Pattern matching and unification +- Recursive rules (semi-naive evaluation) +- Updated REPL + +**Phase 4** (3-4 months): Bi-temporal Support +- Transaction time (tx_id, tx_time) +- Valid time (valid_from, valid_to) +- Time travel queries (:as-of, :valid-at) +- History queries + +**Phase 5** (2-3 months): ACID + WAL +- Write-ahead logging (embedded in .graph file) +- Transaction API (BEGIN, COMMIT, ROLLBACK) +- Crash recovery +- ACID compliance + +**Phase 6** (2-3 months): Performance +- Indexes (EAVT, AEVT, AVET, VAET) +- Query optimization +- Benchmarking + +**Phase 7** (3-4 months): Cross-platform +- WASM (IndexedDB backend) +- Mobile bindings (iOS, Android) +- Language bindings (Python, JavaScript) + +**v1.0.0** (12-15 months): Production Ready +- Stable API +- Stable file format +- Comprehensive docs +- Backwards compatibility promise + +## Comparison to Similar Projects + +**XTDB** (formerly Crux): +- ✅ Bi-temporal Datalog database (inspiration) +- ✅ Production-ready +- ❌ Clojure, multi-file storage (directories) +- Minigraf: Single file, Rust, simpler scope + +**Cozo**: +- ✅ Embedded Datalog, Rust +- ✅ Graph algorithms, vector search +- ❌ Multi-file storage (RocksDB/Sled) +- Minigraf: Single file, bi-temporal first-class + +**Datomic**: +- ✅ Temporal Datalog database (major inspiration) +- ✅ Production-proven since 2012 +- ❌ Client-server, Clojure, proprietary +- Minigraf: Embedded, single file, open source + +**GraphLite**: +- ✅ Full GQL spec compliance +- ✅ Embedded, ACID, mature +- ❌ Multi-file storage (Sled), no bi-temporal +- Minigraf: Datalog (not GQL), single file, bi-temporal + +**Positioning**: Minigraf = SQLite + Datomic + single file + +## Contributing Guidelines + +This is a hobby project with a decades-long vision. When contributing: + +1. **Read PHILOSOPHY.md first** - Understand the core principles +2. **Check ROADMAP.md** - See where we are and where we're going +3. **Align with philosophy** - Simplicity, reliability, embedded-first +4. **Write tests** - All features must be tested +5. **Keep it simple** - Prefer boring, proven solutions +6. **Think long-term** - We're building for decades, not months + +**Say NO to**: +- Features that break single-file philosophy +- Client-server architecture +- Complex configuration +- Features only for distributed systems +- Breaking changes without overwhelming justification + +**Say YES to**: +- Crash safety and data integrity +- Query performance improvements +- Better error messages +- Documentation improvements +- Cross-platform support + +## Key Files to Understand + +**For Phase 3 work (Datalog implementation)**: +1. `PHILOSOPHY.md` - Why Datalog, why bi-temporal +2. `ROADMAP.md` - Detailed Phase 3 plan +3. `src/storage/mod.rs` - Storage abstraction (stable foundation) +4. `src/graph/types.rs` - Current types (will evolve to EAV) +5. `src/query/parser.rs` - Current parser (will be rewritten) +6. `src/query/executor.rs` - Current executor (will be rewritten) + +**For understanding storage (stable)**: +1. `src/storage/backend/file.rs` - File format implementation +2. `src/storage/persistent.rs` - Persistence layer +3. `src/minigraf.rs` - Public API + +## Important Reminders + +1. **We pivoted to Datalog** - Don't implement GQL features +2. **Bi-temporal is first-class** - Not an afterthought +3. **Single file is sacred** - Never break this +4. **Simplicity over features** - Do less, do it perfectly +5. **Test everything** - No untested code +6. **Think SQLite** - Would SQLite do this? +7. **Long-term vision** - Building for decades + +--- + +*When in doubt, refer to PHILOSOPHY.md and ROADMAP.md. The goal is not to be the most feature-complete graph database. The goal is to be the one that's always there when you need it, works reliably, and never gets in your way.* + +*Be boring. Be reliable. Be Minigraf.* diff --git a/Cargo.toml b/Cargo.toml index 7ef8f867b..93dab5192 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -9,7 +9,7 @@ serde = { version = "1.0", features = ["derive"] } serde_json = "1.0" bincode = "1.3" anyhow = "1.0" -uuid = { version = "1.0", features = ["v4", "serde"] } +uuid = { version = "1.0", features = ["v4", "v5", "serde"] } [profile.release] panic = "abort" diff --git a/PHILOSOPHY.md b/PHILOSOPHY.md index 46d0c9ad5..1e4750715 100644 --- a/PHILOSOPHY.md +++ b/PHILOSOPHY.md @@ -2,7 +2,62 @@ > "Minigraf is not trying to replace Neo4j. It's trying to replace `serde_json` for graph data." -Minigraf aims to be **the SQLite of graph databases** - a small, fast, reliable, embedded graph database engine that runs in-process with your application. +Minigraf aims to be **the SQLite of bi-temporal graph databases** - a small, fast, reliable, embedded graph database with Datalog queries and time travel capabilities. + +## Why Datalog? + +**Strategic Decision** (January 2026): After completing Phase 2 with a GQL-inspired implementation, we pivoted to Datalog. Here's why: + +### 1. Better Philosophy Alignment + +**Datalog is simpler** → Aligns with "do less, do it perfectly": +- Datalog spec: ~50 pages of core concepts +- GQL spec: 600+ pages (ISO/IEC 39075:2024) +- Smaller surface area = fewer bugs, faster to production + +**Datalog is proven** → 40+ years of production use (Datomic since 2012, XTDB, LogicBlox) +**Datalog is reliable** → Well-understood semantics, extensive research + +### 2. Natural Fit for Temporal Databases + +**Bi-temporal support was always the plan.** Datalog makes it natural: +- Facts are tuples: `(Entity, Attribute, Value, ValidFrom, ValidTo, TxTime)` +- Time is just another dimension in relations +- Temporal queries use simple predicates: `[(<= ?valid-from ?query-time)]` +- No special temporal syntax needed - it's just data + +**With GQL**: Bi-temporal would be 12+ months of novel implementation (unclear semantics) +**With Datalog**: Bi-temporal is 3-4 months of proven patterns (Datomic/XTDB model) + +### 3. Graph Traversal is MORE Powerful + +**Recursive rules are first-class in Datalog:** +```datalog +[(reachable ?from ?to) + [?from :connected ?to]] + +[(reachable ?from ?to) + [?from :connected ?intermediate] + (reachable ?intermediate ?to)] +``` + +This is cleaner and more powerful than GQL's path patterns. Transitive closure is native, not bolted on. + +### 4. Faster Path to Production + +**GQL roadmap**: 24-30 months to production (catch up to GraphLite) +**Datalog roadmap**: 12-15 months to production (proven implementation patterns) + +We can ship a useful, reliable database faster with Datalog. + +### 5. Unique Market Position + +**GQL space**: GraphLite already won (full spec, ACID, mature) +**Datalog space**: Gap exists for single-file embedded bi-temporal DB + +Minigraf = SQLite + Datomic + single file (no one else offers this) + +--- ## Core Inspiration: SQLite @@ -177,6 +232,18 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s - Direct function calls, no network overhead - Runs in-process with your app +✅ **A bi-temporal database** +- Track when facts were recorded (transaction time) +- Track when facts were valid in the real world (valid time) +- Time travel queries: see any point in history +- Audit trails and compliance built-in + +✅ **A Datalog query engine** +- Recursive rules for graph traversal +- Logic programming paradigm +- Simpler than SQL, more powerful for graphs +- Proven semantics (40+ years of research) + ✅ **A local-first storage solution** - Perfect for desktop applications - Ideal for mobile apps @@ -188,7 +255,7 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s - Portable across platforms - Simple backup and versioning -✅ **A reliable, ACID-compliant database** +✅ **A reliable, ACID-compliant database** (Phase 5) - Transactions with rollback support - Crash recovery via WAL - Data integrity guarantees @@ -226,27 +293,32 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s - Different scale (millions vs. billions of nodes) - Different philosophy (library vs. service) -❌ **Not chasing full GQL spec compliance** -- Implement what's useful, not what's in the spec -- Pragmatic subset of GQL -- Extensions for common patterns +❌ **Not chasing feature parity with XTDB/Datomic** +- Simpler scope: single-file only +- No distributed features +- No vector search (separate crate if needed) +- Focus on reliability over features ## Target Use Cases **Primary use cases** (optimize for these): -1. **Mobile applications** - Local graph storage on phones/tablets -2. **Desktop applications** - Apps that need relationship data (IDEs, note-taking, etc.) -3. **Web applications (WASM)** - Client-side graph storage in browsers -4. **Embedded devices** - IoT, edge computing with graph data -5. **Development/testing** - Local graph database for testing -6. **Small to medium production apps** - Where embedded DB is sufficient +1. **Audit-heavy applications** - Finance, healthcare, legal (bi-temporal = compliance) +2. **Event sourcing** - Full history, time travel debugging +3. **Personal knowledge bases** - Obsidian, Logseq, Roam-like apps with provenance +4. **Mobile applications** - Local graph storage on phones/tablets +5. **Desktop applications** - Apps that need relationship data (IDEs, note-taking, etc.) +6. **Web applications (WASM)** - Client-side graph storage in browsers +7. **AI/RAG systems** - Knowledge graphs with temporal provenance +8. **Embedded devices** - IoT, edge computing with graph data +9. **Development/testing** - Local graph database for testing +10. **Small to medium production apps** - Where embedded DB is sufficient **Secondary use cases** (should work, but not optimized for): -7. **Server applications** - Using Minigraf as an embedded component -8. **Data analysis** - Exploring graph datasets locally -9. **Education** - Learning graph databases and algorithms +11. **Server applications** - Using Minigraf as an embedded component +12. **Data analysis** - Exploring graph datasets locally +13. **Education** - Learning Datalog and temporal databases **Non-use cases** (explicitly out of scope): @@ -305,7 +377,6 @@ To maintain focus, these are explicitly NOT goals: - ❌ Distributed consensus algorithms - ❌ Multi-master replication - ❌ Built-in authentication/authorization -- ❌ Full GQL standard compliance (implement useful subset) - ❌ Competing with Neo4j/TigerGraph on their turf - ❌ Real-time analytics (OLAP workloads) - ❌ Graph visualization (provide data, let others visualize) @@ -359,19 +430,28 @@ The `.graph` file format must be: **Phase 2**: ✅ Embeddability (COMPLETE) - Single-file storage, persistent graph database, embedded API +- GQL-inspired PoC (archived at `archive/gql-phase-2`) + +**Phase 3**: 🎯 Datalog Core (NEXT - 3-4 months) +- EAV data model, basic facts and queries, recursive rules -**Phase 3**: ⏳ Establish reliability (NEXT) -- WAL, ACID transactions, crash recovery, indexes, query optimization +**Phase 4**: 🎯 Bi-temporal Support (3-4 months) +- Transaction time + valid time, time travel queries, history -**Phase 4**: ⏳ Expand reach -- WASM support, mobile bindings, multiple backends +**Phase 5**: 🎯 ACID + WAL (2-3 months) +- Write-ahead logging, transactions, crash recovery -**Phase 5**: ⏳ Mature the ecosystem -- Full documentation, tooling, ecosystem libraries +**Phase 6**: 🎯 Performance (2-3 months) +- Indexes (EAVT, AEVT, AVET, VAET), query optimization -**Phase 6+**: ⏳ Long-term maintenance +**Phase 7**: 🎯 Cross-platform (3-4 months) +- WASM support, mobile bindings, language bindings + +**Phase 8+**: 🎯 Long-term maintenance - Bug fixes, security patches, conservative improvements +**v1.0.0**: 12-15 months (vs. 24-30 months with GQL) + See ROADMAP.md for detailed feature breakdown. ## When to Say "No" @@ -381,6 +461,7 @@ It's important to say "no" to preserve the project's focus: - Features that only serve enterprise/distributed use cases - Complexity that compromises reliability - Dependencies that increase binary size significantly + - Breaking changes without overwhelming justification - Features that should be separate libraries - Premature optimization @@ -391,9 +472,10 @@ It's important to say "no" to preserve the project's focus: Beyond SQLite, we draw inspiration from: -- **SQLite**: Embedded database philosophy +- **Datomic**: Immutable facts, temporal queries, Datalog +- **XTDB**: Bi-temporal database, time travel +- **Cozo**: Embedded Datalog, graph algorithms - **Redis**: Simple, focused, well-documented -- **Rust**: Memory safety, zero-cost abstractions - **Git**: Single-file stores (packfiles), content-addressed storage - **DuckDB**: Modern analytics, SQLite-style - **Local-first software**: Offline-capable, user-owned data diff --git a/README.md b/README.md index 1bac2051b..4549db709 100644 --- a/README.md +++ b/README.md @@ -6,26 +6,47 @@ [![Rust Edition](https://img.shields.io/badge/rust-2024-orange.svg)](https://blog.rust-lang.org/2024/10/17/Rust-1.82.0.html) [![Phase](https://img.shields.io/badge/phase-2%20complete-blue.svg)](https://github.com/adityamukho/minigraf/blob/main/ROADMAP.md) -A tiny, portable GQL (Graph Query Language) engine written in Rust. **W.I.P.** +> **The SQLite of bi-temporal graph databases** - Embedded Datalog engine written in Rust -GQL stands for Graph Query Language, which has been standardized in [ISO/IEC 39075:2024](https://www.iso.org/standard/76120.html). +A tiny, self-contained graph database with **Datalog queries** and **bi-temporal time travel**. Think SQLite, but for connected data with full history. + +## Vision + +Minigraf is a **single-file embedded graph database** that lets you: +- ✅ **Query relationships with Datalog** - Recursive rules, natural graph traversal +- 🎯 **Time travel through history** - Bi-temporal queries (transaction time + valid time) +- ✅ **Embed anywhere** - Native, WASM, mobile, IoT - one `.graph` file +- ✅ **Zero configuration** - Just `Minigraf::open("data.graph")` and you're done + +**Status**: Early development. Phase 2 complete (persistent storage). Now pivoting from GQL to Datalog for better temporal semantics. + +## Why Datalog? + +**Datalog is fundamentally better for graphs than SQL-like languages:** + +1. **Recursive by design** - Multi-hop traversals are natural, not an afterthought +2. **Simpler to implement** - Smaller spec = more reliable, faster to production +3. **Perfect for temporal** - Time is just another dimension in relations +4. **Proven at scale** - 40+ years of research, production use (Datomic, XTDB) +5. **Graph-native** - Facts (Entity-Attribute-Value) are literally edges ## Current Status - Phase 2 -Minigraf is now a **fully embeddable graph database** with persistent storage: +Minigraf has **persistent storage foundation** ready for Datalog: -- ✅ **Property graph model** - Nodes and edges with typed properties -- ✅ **Persistent storage** - Single `.graph` file format (Phase 2 NEW!) -- ✅ **Embedded database API** - Use like SQLite (Phase 2 NEW!) +- ✅ **Single `.graph` file** - Page-based storage (4KB pages) +- ✅ **Embedded database API** - Use like SQLite (`Minigraf::open()`) - ✅ **Cross-platform** - Works on Linux, macOS, Windows, iOS, Android - ✅ **Auto-persistence** - Changes auto-save when database is dropped -- ✅ **Interactive REPL** - Query console for exploration -- ✅ **Query language** - GQL-inspired syntax -- ✅ **Test coverage** - 35+ tests, all passing +- ✅ **Storage abstraction** - File, Memory backends (IndexedDB future) +- ✅ **54 tests passing** - Comprehensive test coverage +- 🎯 **Query language** - Transitioning from GQL to Datalog (Phase 3) -## Quick Start +**GQL Archive**: Previous GQL implementation preserved at `archive/gql-phase-2` branch and `gql-phase-2-complete` tag. -### As an Embedded Database +## Quick Start (Future API) + +### Embedded Datalog Database ```rust use minigraf::Minigraf; @@ -33,27 +54,33 @@ use minigraf::Minigraf; // Open or create a database let mut db = Minigraf::open("myapp.graph")?; -// Execute queries -db.execute("CREATE NODE (:Person) {name: \"Alice\", age: 30}")?; -db.execute("MATCH (:Person)")?; - -// Auto-saves on drop -drop(db); - -// Later - data is still there! -let db = Minigraf::open("myapp.graph")?; +// Add facts (Entity-Attribute-Value triples) +db.transact(vec![ + [:alice, :person/name, "Alice"], + [:alice, :person/age, 30], + [:alice, :friend, :bob], + [:bob, :person/name, "Bob"], +])?; + +// Query with Datalog +let results = db.query(" + [:find ?friend-name + :where + [:alice :friend ?friend] + [?friend :person/name ?friend-name]] +")?; + +// Time travel - query as of past transaction +let past_db = db.as_of(tx_100); +let old_results = past_db.query(...)?; ``` -### As an Interactive Console +### Interactive Console (Current - In-memory) ```bash -# Build and run the REPL +# Build and run the REPL (currently supports basic graph operations) cargo run -# Or build release version -cargo build --release -./target/release/minigraf - # Run tests cargo test @@ -61,301 +88,279 @@ cargo test cargo run --example embedded ``` -## Query Language +## Datalog Query Language (Planned - Phase 3) -The PoC implements a simple GQL-like query language: +### Basic Facts -### Create a Node - -```gql -CREATE NODE (:Person) {name: "Alice", age: 30} -CREATE NODE (:Person:Employee) {name: "Bob"} -CREATE NODE (:Company) +```datalog +;; Add facts about entities +[:alice :person/name "Alice"] +[:alice :person/age 30] +[:alice :friend :bob] +[:bob :person/name "Bob"] ``` -### Create an Edge - -```gql -CREATE EDGE (node-id-1)-[KNOWS]->(node-id-2) {since: 2020} -CREATE EDGE (alice-id)-[WORKS_AT]->(company-id) -``` +### Simple Queries -### Match/Query Nodes +```datalog +;; Find all friends of Alice +[:find ?friend + :where + [:alice :friend ?friend]] -```gql -MATCH (:Person) -MATCH (:Person) WHERE name = "Alice" -MATCH (:Employee) +;; Find names of Alice's friends +[:find ?name + :where + [:alice :friend ?friend] + [?friend :person/name ?name]] ``` -### Match/Query Edges +### Recursive Rules (The Power of Datalog) -```gql -MATCH -[:KNOWS]-> -MATCH -[:WORKS_AT]-> -``` +```datalog +;; Define transitive friendship +[(friends-network ?person ?reachable) + [?person :friend ?reachable]] -### Show All Data +[(friends-network ?person ?reachable) + [?person :friend ?intermediate] + (friends-network ?intermediate ?reachable)] -```gql -SHOW NODES -SHOW EDGES +;; Find everyone in Alice's network +[:find ?person + :where + (friends-network :alice ?person)] ``` -### Help and Exit - -```gql -HELP # Show available commands -EXIT # Exit the console (or use QUIT) +### Bi-temporal Queries (Phase 4) + +```datalog +;; Query valid at a specific time +[:find ?name + :valid-at "2023-06-01" + :where + [:alice :person/name ?name]] + +;; Query as of past transaction +[:find ?friend + :as-of tx-100 + :where + [:alice :friend ?friend]] + +;; Full bi-temporal query +[:find ?status + :valid-at "2023-06-01" + :as-of tx-100 + :where + [:alice :employment/status ?status]] ``` -## Example Session - -``` -$ cargo run -Minigraf v0.1.0 - Graph Query Language Engine -Using in-memory storage +## Architecture -Minigraf v0.1.0 - Interactive Graph Query Console -Type HELP for available commands, EXIT to quit. +### Module Structure -minigraf> CREATE NODE (:Person) {name: "Alice", age: 30} -Node created: (labels: Person, properties: {age: 30, name: "Alice"}) +- **`src/graph/types.rs`**: Core graph data structures (will evolve to EAV model) +- **`src/graph/storage.rs`**: In-memory storage layer (Phase 1) +- **`src/storage/`**: Storage backend abstraction (Phase 2) ✅ + - **`mod.rs`**: StorageBackend trait, file format + - **`backend/file.rs`**: Single-file persistent backend + - **`backend/memory.rs`**: In-memory backend for testing + - **`backend/indexeddb.rs`**: Future WASM backend +- **`src/query/parser.rs`**: Query parser (will become Datalog parser in Phase 3) +- **`src/query/executor.rs`**: Query executor (will become Datalog engine) +- **`src/repl.rs`**: Interactive REPL console +- **`src/lib.rs`**: Public API +- **`src/main.rs`**: Binary entry point -minigraf> CREATE NODE (:Person) {name: "Bob", age: 25} -Node created: (labels: Person, properties: {age: 25, name: "Bob"}) +### Data Model -minigraf> CREATE EDGE ()-[KNOWS]->() {since: 2020} -Edge created: ( -[KNOWS]-> , properties: {since: 2020}) +**Current** (Property Graph - Phase 1-2): +- Nodes with labels and properties +- Edges with source, target, label, properties -minigraf> MATCH (:Person) -Found 2 node(s): - - (labels: Person, properties: {age: 30, name: "Alice"}) - - (labels: Person, properties: {age: 25, name: "Bob"}) +**Future** (Datalog Triple Store - Phase 3+): +- Facts: `(Entity, Attribute, Value, ValidFrom, ValidTo, TxTime)` +- Entities are just UUIDs +- Attributes are keywords (`:person/name`, `:friend`) +- Values can be primitives or entity references +- Time dimensions for bi-temporal support -minigraf> MATCH (:Person) WHERE name = "Alice" -Found 1 node(s): - - (labels: Person, properties: {age: 30, name: "Alice"}) +### Storage Format -minigraf> SHOW EDGES -Found 1 edge(s): - - ( -[KNOWS]-> , properties: {since: 2020}) +The `.graph` file uses a page-based format (like SQLite): -minigraf> EXIT -Goodbye! +``` ++----------------+ +| Page 0: Header | <- Magic "MGRF", version, page count ++----------------+ +| Page 1: Facts | <- (E, A, V, ValidFrom, ValidTo, TxTime) ++----------------+ +| Page 2: Indexes| <- EAVT, AEVT, AVET, VAET indexes ++----------------+ +| Page 3+: Data | ++----------------+ ``` -## Architecture +- **Page size**: 4KB (like SQLite) +- **Endian-safe**: Works across all platforms +- **Single file**: Easy to backup, share, version control +- **Stable format**: Backwards compatible once v1.0 ships -### Module Structure +## Roadmap -- **`src/graph/types.rs`**: Core property graph data structures (Node, Edge, Property, PropertyValue) -- **`src/graph/storage.rs`**: In-memory storage layer with thread-safe operations -- **`src/storage/`**: Storage backend abstraction (NEW in Phase 2) - - **`mod.rs`**: StorageBackend trait and file format definitions - - **`backend/file.rs`**: File-based backend for native platforms (.graph files) - - **`backend/memory.rs`**: In-memory backend for testing/embedded - - **`backend/indexeddb.rs`**: Browser backend (future, WASM only) -- **`src/query/parser.rs`**: Query language parser -- **`src/query/executor.rs`**: Query execution engine -- **`src/repl.rs`**: Interactive REPL console -- **`src/lib.rs`**: Library exports -- **`src/main.rs`**: Binary entry point +**Phase 1**: ✅ Property graph PoC (Complete) +**Phase 2**: ✅ Persistent storage (Complete) +**Phase 3**: 🎯 Datalog core (3-4 months) +- Basic facts and queries +- Recursive rules +- Pattern matching -### Property Graph Model +**Phase 4**: 🎯 Bi-temporal support (3-4 months) +- Valid time + transaction time +- Time travel queries +- Historical analysis -**Nodes**: -- Unique UUID identifier -- Multiple labels (e.g., `Person`, `Employee`) -- Properties as key-value pairs +**Phase 5**: 🎯 ACID + WAL (2-3 months) +- Write-ahead logging +- Transactions +- Crash recovery -**Edges**: -- Unique UUID identifier -- Source and target node IDs -- Single label/type (e.g., `KNOWS`, `WORKS_AT`) -- Properties as key-value pairs +**Phase 6**: 🎯 Performance (2-3 months) +- Indexes (EAVT, AEVT, AVET, VAET) +- Query optimization +- Benchmarking -**Property Values**: -- String -- Integer (i64) -- Float (f64) -- Boolean -- Null +**Phase 7**: 🎯 Cross-platform (3-4 months) +- WASM (IndexedDB backend) +- Mobile bindings +- Language bindings -## Scope +**v1.0.0**: 12-15 months (vs. 24-30 months with GQL) -Minigraf will be designed to run in multiple environments, including: -- As a standalone binary ✅ (PoC done) -- As a library ✅ (PoC done) -- As a WebAssembly module (for browsers) ⏳ (future) +See [ROADMAP.md](ROADMAP.md) for detailed breakdown. -## Unscope +## Why Minigraf? -Minigraf will **NOT** be designed to be (for now): -- Distributed, -- Fault-tolerant, -- ACID-compliant. +### Unique Positioning -## Storage Backends +No other database offers this combination: -Minigraf uses a **platform-abstraction layer** inspired by SQLite's VFS architecture. Different storage backends enable cross-platform support: +| Feature | Minigraf | XTDB | Cozo | Neo4j | SQLite | +|---------|----------|------|------|-------|--------| +| **Query Language** | Datalog | Datalog | Datalog | Cypher | SQL | +| **Single File** | ✅ Yes | ❌ No | ❌ No | ❌ No | ✅ Yes | +| **Bi-temporal** | 🎯 Goal | ✅ Yes | ⚠️ Time travel | ❌ No | ❌ No | +| **Embedded** | ✅ Yes | ✅ Yes | ✅ Yes | ❌ No | ✅ Yes | +| **Graph Native** | ✅ Yes | ✅ Yes | ✅ Yes | ✅ Yes | ❌ No | +| **Rust** | ✅ Yes | ❌ Clojure | ✅ Yes | ❌ Java | ❌ C | +| **WASM Ready** | 🎯 Goal | ❌ No | ⚠️ Limited | ❌ No | ✅ Yes | -### Available Backends +**Minigraf = SQLite + Datomic + single file** -- **In-memory** ✅ - Fast, non-persistent storage (Phase 1 PoC) - - Perfect for testing and embedded systems - - Currently used by the REPL +### Target Use Cases -- **File-based (`.graph` files)** ✅ - Single-file persistent storage (Phase 2) - - Page-based storage with 4KB pages - - Cross-platform file format (endian-safe) - - Supports native platforms: Linux, macOS, Windows, iOS, Android - - See `examples/file_storage.rs` for usage +1. **Audit-heavy applications** - Finance, healthcare, legal (bi-temporal = compliance) +2. **Event sourcing** - Full history, time travel debugging +3. **Personal knowledge bases** - Obsidian, Logseq, Roam-like apps +4. **Local-first applications** - Offline-capable, user-owned data +5. **AI/RAG systems** - Knowledge graphs with provenance +6. **Mobile apps** - Embedded graph database on devices +7. **WASM applications** - Graph database in the browser +8. **Development/testing** - Local graph DB like SQLite -### Future Backends +### Philosophy: The SQLite of Graph Databases -- **IndexedDB** ⏳ - Browser storage for WASM (Phase 5) - - Same API, different implementation - - Enables Minigraf in web applications +- **Zero-configuration** - No setup, just works +- **Embedded-first** - Library, not server +- **Single-file database** - Easy backup, share, version control +- **Self-contained** - <1MB binary, minimal dependencies +- **Cross-platform** - Native, WASM, mobile, embedded +- **Reliability over features** - Do less, do it perfectly +- **Long-term support** - Decades-long commitment -- **Optional: Custom implementations** ⏳ - - Users can implement `StorageBackend` trait for custom needs - - Example: SQLite, RocksDB (via feature flags) +See [PHILOSOPHY.md](PHILOSOPHY.md) for complete design principles. -### `.graph` File Format +## Scope -The file-based backend uses a simple, stable page-based format: +Minigraf is designed to run in multiple environments: +- ✅ As a standalone binary (PoC done) +- ✅ As an embedded library (PoC done) +- 🎯 As a WebAssembly module (future - Phase 7) -``` -+----------------+ -| Page 0: Header | <- Magic "MGRF", version, page count, node/edge counts -+----------------+ -| Page 1: Data | <- Future: Nodes, edges, indexes -+----------------+ -| Page 2: Data | -+----------------+ -| ... | -+----------------+ -``` +## Unscope -- **Page size**: 4KB (like SQLite) -- **Endian-safe**: Works across all platforms -- **Single file**: Easy to backup, share, version control -- **Stable format**: Once v1.0 ships, backwards compatible forever - -## GQL Spec Compliance - -**Current Status: ~2-5% of ISO/IEC 39075:2024** - -This is a hobby project implementing a GQL-inspired query language. It is **not fully compliant** with the GQL standard and does not aim for complete compliance in the near term. - -### ✅ Implemented (PoC Level) - -**Basic Graph Model:** -- ✅ Nodes with multiple labels -- ✅ Directed edges with single label -- ✅ Properties on nodes and edges -- ✅ Property types: String, Integer, Float, Boolean, Null - -**Basic Query Operations:** -- ✅ CREATE NODE with labels and properties -- ✅ CREATE EDGE between existing nodes -- ✅ Simple MATCH by label: `MATCH (:Label)` -- ✅ Single property equality filter: `WHERE prop = value` -- ✅ SHOW NODES / SHOW EDGES (non-standard convenience commands) - -### ❌ Not Yet Implemented (Majority of GQL Spec) - -**Graph Pattern Matching:** -- ❌ Complex path patterns: `(a)-[:REL]->(b)-[:REL2]->(c)` -- ❌ Variable-length paths: `(a)-[:REL*1..5]->(b)` -- ❌ Shortest path queries -- ❌ Optional patterns (OPTIONAL MATCH) -- ❌ Pattern alternatives/disjunction -- ❌ Quantified path patterns - -**Query Clauses:** -- ❌ RETURN clause (projections, expressions) -- ❌ WITH clause (intermediate results) -- ❌ ORDER BY, LIMIT, SKIP -- ❌ DISTINCT -- ❌ OPTIONAL MATCH -- ❌ UNION, INTERSECT, EXCEPT - -**Data Manipulation:** -- ❌ INSERT (vs. CREATE) -- ❌ SET (update properties/labels) -- ❌ REMOVE (remove properties/labels) -- ❌ DELETE (delete nodes/edges) -- ❌ MERGE (upsert semantics) - -**Expressions & Operators:** -- ❌ Arithmetic operations (+, -, *, /, %) -- ❌ Comparison operators (<, >, <=, >=, <>) -- ❌ Logical operators (AND, OR, NOT) in WHERE -- ❌ String operations (CONTAINS, STARTS WITH, ENDS WITH) -- ❌ List operations -- ❌ Map/record operations -- ❌ CASE expressions -- ❌ NULL handling (IS NULL, COALESCE) - -**Aggregations & Grouping:** -- ❌ Aggregation functions (COUNT, SUM, AVG, MIN, MAX) -- ❌ GROUP BY -- ❌ HAVING - -**Advanced Data Types:** -- ❌ Lists/Arrays -- ❌ Maps/Records -- ❌ Path type -- ❌ Temporal types (Date, Time, DateTime, Duration) -- ❌ Spatial types (Point, Geography) - -**Advanced Features:** -- ❌ Multiple named graphs -- ❌ Graph constructors -- ❌ Schema definitions and validation -- ❌ Constraints and indexes -- ❌ Functions (string, math, temporal, etc.) -- ❌ Subqueries -- ❌ Transactions - -**Conformance:** -- ❌ No formal conformance testing -- ❌ Not validated against official GQL test suite -- ❌ Syntax may differ from official spec - -### Roadmap to Compliance - -This project prioritizes usability over spec compliance. See [ROADMAP.md](ROADMAP.md) for the complete development roadmap. - -**GQL Spec Feature Milestones**: - -1. ✅ **Basic PoC**: Simple CRUD and queries -2. ⏳ **Complex patterns**: Multi-hop paths, variable-length -3. ⏳ **RETURN clause**: Projections, ORDER BY/LIMIT -4. ⏳ **Data manipulation**: UPDATE/DELETE operations -5. ⏳ **Aggregations**: COUNT, SUM, AVG, GROUP BY -6. ⏳ **Advanced expressions**: Operators, functions -7. ⏳ **Schema**: Constraints, indexes -8. ⏳ **Full compliance**: Advanced types, multiple graphs - -For official GQL resources, see: [ISO/IEC 39075:2024](https://www.iso.org/standard/76120.html) +Minigraf will **NOT** be (by design): +- **Distributed** - No clustering, no sharding, no replication +- **Client-server** - No network protocol in core +- **Enterprise-focused** - No RBAC, no HA, no multi-datacenter +- **Billion-node scale** - Optimized for <1M nodes (like SQLite) + +If you need these, use Neo4j, TigerGraph, or similar. ## Testing -The project includes comprehensive test coverage: +Comprehensive test coverage: ```bash cargo test ``` -Tests cover: -- Property graph data structures -- Storage operations (CRUD for nodes and edges) -- Query parser -- Query executor -- Edge traversal operations +Current tests (54 total): +- Property graph operations (Phase 1-2 foundation) +- Storage backend operations +- Persistence and recovery +- Concurrency and edge cases + +Future tests (Phase 3+): +- Datalog parser +- Recursive rule evaluation +- Bi-temporal queries +- Transaction isolation + +## Comparison to Similar Projects + +### vs. XTDB (formerly Crux) +- ✅ **Minigraf**: Single `.graph` file, simpler scope +- ✅ **XTDB**: More mature, production-ready, but Clojure + multi-file storage + +### vs. Cozo +- ✅ **Minigraf**: Single file, bi-temporal first-class +- ✅ **Cozo**: More features (vector search, time travel), but multi-file storage + +### vs. GraphLite +- ✅ **Minigraf**: Datalog (recursive rules), bi-temporal +- ✅ **GraphLite**: Full GQL compliance, but multi-file (Sled directories) + +### vs. Datomic +- ✅ **Minigraf**: Single file, embedded, Rust +- ✅ **Datomic**: Production-proven, but client-server, Clojure, proprietary + +**Minigraf aims to be the simplest, most portable option: SQLite's simplicity + Datomic's temporal model.** + +## Contributing + +This is a hobby project with a long-term vision. Contributions welcome, but we prioritize: +1. Reliability over features +2. Simplicity over flexibility +3. Philosophy alignment + +See [ROADMAP.md](ROADMAP.md) and [PHILOSOPHY.md](PHILOSOPHY.md) before proposing features. + +## Learning Resources + +### Datalog +- [Learn Datalog Today](http://www.learndatalogtoday.org/) +- [Datomic Query Tutorial](https://docs.datomic.com/query/query-tutorial.html) +- [XTDB Datalog Queries](https://xtdb.com/docs/) + +### Temporal Databases +- [Temporal Database Wikipedia](https://en.wikipedia.org/wiki/Temporal_database) +- [XTDB Bitemporality](https://v1-docs.xtdb.com/concepts/bitemporality/) +- [Datomic Time Model](https://docs.datomic.com/time/time-model.html) + +### SQLite's VFS +- [SQLite OS Interface](https://www.sqlite.org/vfs.html) +- [SQLite File Format](https://www.sqlite.org/fileformat.html) ## License diff --git a/ROADMAP.md b/ROADMAP.md index fff303643..59eb9cfaa 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -1,16 +1,18 @@ # Minigraf Roadmap -> The path from PoC to production-ready embedded graph database +> The path from property graph PoC to production-ready bi-temporal Datalog database -**Philosophy**: "SQLite for graph databases" - Be boring, be reliable, be embeddable. +**Philosophy**: "SQLite for bi-temporal graph databases" - Be boring, be reliable, be embeddable. + +**Strategic Pivot** (January 2026): After completing Phase 2, we pivoted from GQL to Datalog for better temporal semantics, simpler implementation, and faster time-to-production. --- -## Phase 1: Proof of Concept ✅ COMPLETE +## Phase 1: Property Graph PoC ✅ COMPLETE **Goal**: Prove the concept works -**Status**: ✅ Completed +**Status**: ✅ Completed (December 2025) **What Was Built**: - ✅ Property graph model (nodes, edges, properties) @@ -22,13 +24,15 @@ **Deliverable**: Working in-memory graph database with REPL +**Learnings**: Property graphs work well, but GQL spec is too large. Need simpler query language. + --- ## Phase 2: Embeddability ✅ COMPLETE **Goal**: Make it truly embeddable with persistence -**Status**: ✅ Completed (Current) +**Status**: ✅ Completed (January 2026) **What Was Built**: - ✅ Storage backend abstraction (FileBackend, MemoryBackend) @@ -45,265 +49,535 @@ **Philosophy Alignment**: ✅ Single-file, self-contained, embedded-first +**Archive**: GQL implementation preserved at `archive/gql-phase-2` branch + +**Learnings**: Storage layer is solid. Pivot to Datalog for better temporal support. + --- -## Phase 3: Reliability & Performance 🔄 NEXT +## Phase 3: Datalog Core 🎯 NEXT -**Goal**: Add crash safety, transactions, and query optimization +**Goal**: Implement core Datalog query engine -**Status**: ⏳ Planned +**Status**: 🎯 In Progress (Expected: 3-4 months) -### 3.1 Write-Ahead Logging (WAL) & Crash Safety +**Priority**: 🔴 Critical - Foundation for everything else -**Priority**: 🔴 Critical +### 3.1 EAV Data Model **Features**: -- ⏳ Embedded WAL (in same `.graph` file) -- ⏳ Transaction support (BEGIN, COMMIT, ROLLBACK) -- ⏳ Crash recovery (replay WAL on open) -- ⏳ Checkpoint mechanism (merge WAL to main pages) -- ⏳ ACID compliance: - - Atomicity: All-or-nothing transactions - - Consistency: Enforce constraints - - Isolation: Transaction isolation levels - - Durability: WAL ensures persistence +- 🎯 Migrate from property graph to Entity-Attribute-Value model +- 🎯 Fact representation: `(Entity, Attribute, Value)` +- 🎯 Entities as UUIDs (keep existing ID system) +- 🎯 Attributes as keywords (`:person/name`, `:friend`) +- 🎯 Values: primitives or entity references +- 🎯 Update storage format to support EAV tuples **Technical Approach**: -``` -File Structure: -Page 0: Header (includes wal_offset) -Page 1: Index -Page 2+: Data -WAL: Append-only log at end of file +```rust +struct Fact { + entity: Uuid, + attribute: String, // Will become typed Keyword later + value: Value, + tx_id: TxId, // Transaction that asserted this fact + asserted: bool, // true = assert, false = retract +} + +enum Value { + String(String), + Integer(i64), + Float(f64), + Boolean(bool), + Ref(Uuid), // Reference to another entity + Keyword(String), + Null, +} ``` -**Why Embedded WAL**: -- ✅ Maintains single-file philosophy -- ✅ Easy to backup/share (one file) -- ✅ Simpler user experience -- ⚠️ Slightly more complex than separate file -- ✅ Acceptable trade-off for our use cases +**Migration Path**: +- Keep existing node/edge types for backward compat +- Add EAV layer on top +- Gradually migrate tests +- Eventually deprecate property graph types -**Tests Needed**: -- Crash during transaction (unclean shutdown) -- Multiple transactions before checkpoint -- Recovery from partial writes -- Transaction rollback +### 3.2 Datalog Parser -### 3.2 Indexes for Query Performance +**Features**: +- 🎯 Parse basic Datalog queries (EDN syntax) +- 🎯 Query structure: `[:find ?vars :where [clauses]]` +- 🎯 Pattern matching: `[?e :attr ?v]` +- 🎯 Variable binding +- 🎯 Constants and entity references + +**Example Queries**: +```datalog +;; Find all entities with a name +[:find ?e + :where [?e :person/name _]] + +;; Find friends of Alice +[:find ?friend + :where + [?alice :person/name "Alice"] + [?alice :friend ?friend]] + +;; Find names of Alice's friends +[:find ?name + :where + [?alice :person/name "Alice"] + [?alice :friend ?friend] + [?friend :person/name ?name]] +``` -**Priority**: 🟡 High +**Parser Components**: +- EDN reader (simple S-expression parser) +- Query validation +- Variable extraction +- Pattern recognition -**Features**: -- ⏳ B-tree indexes for properties -- ⏳ Label indexes for fast MATCH -- ⏳ Composite indexes (multi-property) -- ⏳ Index maintenance (auto-update on changes) -- ⏳ Query planner (choose index vs. scan) +### 3.3 Query Executor (Basic) -**Performance Targets**: -- Indexed property lookup: <1ms -- MATCH with filter: <10ms for 100K nodes -- Bulk insert: 10K nodes/sec +**Features**: +- 🎯 Pattern matching against fact database +- 🎯 Variable unification +- 🎯 Join multiple patterns +- 🎯 Return results as tuples -### 3.3 Query Optimization +**Implementation**: +- Naive evaluation initially (optimize in Phase 6) +- Iterate through facts, unify variables +- Cartesian product + filter (like nested loops) +- Return binding sets -**Priority**: 🟡 High +### 3.4 Recursive Rules **Features**: -- ⏳ Query plan generation -- ⏳ Cost-based optimization -- ⏳ Index selection -- ⏳ JOIN optimization (for multi-hop paths) +- 🎯 Define rules: `[(rule-name ?args) [body]]` +- 🎯 Stratified recursion (safe subset) +- 🎯 Rule evaluation via semi-naive evaluation +- 🎯 Transitive closure queries + +**Example Rules**: +```datalog +;; Define reachability +[(reachable ?from ?to) + [?from :connected ?to]] + +[(reachable ?from ?to) + [?from :connected ?intermediate] + (reachable ?intermediate ?to)] + +;; Use in query +[:find ?person + :where + (reachable :alice ?person)] +``` -### 3.4 Incremental Persistence +**Technical Approach**: +- Fixed-point iteration +- Track delta (new facts) each round +- Stop when no new facts produced +- Detect cycles, prevent infinite loops -**Priority**: 🟢 Medium +### 3.5 REPL for Datalog **Features**: -- ⏳ Only save changed pages (not full "load all, save all") -- ⏳ Page-level dirty tracking -- ⏳ Efficient diff detection +- 🎯 Interactive Datalog console +- 🎯 Transact facts +- 🎯 Query with Datalog +- 🎯 Pretty-print results + +**Commands**: +```clojure +;; Transact facts +(transact [[:alice :person/name "Alice"] + [:alice :person/age 30]]) + +;; Query +(query [:find ?name :where [?e :person/name ?name]]) + +;; Define rule +(rule [(friends ?a ?b) [?a :friend ?b] [?b :friend ?a]]) + +;; Help +(help) + +;; Exit +(exit) +``` -**Why After WAL**: -- WAL provides atomic updates -- Safer to do incremental with WAL +### 3.6 Tests -**Deliverable**: ACID-compliant database with fast queries +**Test Coverage**: +- EAV data model CRUD +- Datalog parser (all query forms) +- Pattern matching +- Variable unification +- Multi-pattern joins +- Recursive rule evaluation +- Transitive closure queries -**Timeline**: 2-3 months of focused development +**Deliverable**: Working Datalog query engine with recursion + +**Timeline**: 3-4 months --- -## Phase 4: Advanced Graph Features +## Phase 4: Bi-temporal Support 🎯 FUTURE + +**Goal**: Add transaction time and valid time -**Goal**: Multi-hop queries, advanced patterns +**Status**: 🎯 Planned (After Phase 3) -**Status**: ⏳ Future +**Priority**: 🔴 Critical - Core differentiator -### 4.1 Complex Path Patterns +### 4.1 Transaction Time **Features**: -- ⏳ Variable-length paths: `(a)-[:REL*1..5]->(b)` -- ⏳ Shortest path queries -- ⏳ Multi-hop traversals -- ⏳ Path finding algorithms +- 🎯 Every fact records when it was added (`tx_id`, `tx_time`) +- 🎯 Facts are never deleted, only retracted +- 🎯 Query as of past transaction: `[:as-of tx-100]` +- 🎯 History of an entity/attribute + +**Data Model**: +```rust +struct Fact { + entity: Uuid, + attribute: String, + value: Value, + tx_id: TxId, // NEW: Transaction ID + tx_time: SystemTime, // NEW: Wall-clock time + asserted: bool, // true = assert, false = retract +} +``` + +**Queries**: +```datalog +;; Current state (default) +[:find ?name :where [?e :person/name ?name]] + +;; State as of transaction 100 +[:find ?name + :as-of 100 + :where [?e :person/name ?name]] + +;; History of Alice's name +[:find ?name ?tx + :where + [?alice :person/name "Alice"] + [?alice :person/name ?name ?tx]] +``` -### 4.2 Advanced Query Language +### 4.2 Valid Time **Features**: -- ⏳ RETURN clause (projections, expressions) -- ⏳ WITH clause (intermediate results) -- ⏳ ORDER BY, LIMIT, SKIP -- ⏳ DISTINCT -- ⏳ Aggregations (COUNT, SUM, AVG, MIN, MAX) -- ⏳ GROUP BY, HAVING +- 🎯 Facts can have validity period (when true in real world) +- 🎯 `valid_from` and `valid_to` timestamps +- 🎯 Query valid at specific time: `[:valid-at "2023-06-01"]` +- 🎯 Separate from transaction time + +**Data Model**: +```rust +struct Fact { + entity: Uuid, + attribute: String, + value: Value, + valid_from: DateTime, // NEW: When valid starts + valid_to: DateTime, // NEW: When valid ends (MAX for open) + tx_id: TxId, + tx_time: SystemTime, + asserted: bool, +} +``` + +**Queries**: +```datalog +;; Valid on specific date +[:find ?status + :valid-at "2023-06-01" + :where + [:alice :employment/status ?status]] + +;; Valid during range +[:find ?status + :valid-from "2023-01-01" + :valid-to "2023-12-31" + :where + [:alice :employment/status ?status]] +``` -### 4.3 Data Manipulation +### 4.3 Bi-temporal Queries **Features**: -- ⏳ UPDATE nodes/edges -- ⏳ DELETE nodes/edges (with cascade options) -- ⏳ MERGE (upsert semantics) -- ⏳ SET/REMOVE properties +- 🎯 Combine both time dimensions +- 🎯 "What did we believe on date X about facts valid on date Y?" +- 🎯 Audit trails and compliance queries + +**Queries**: +```datalog +;; Full bi-temporal query +[:find ?status + :valid-at "2023-06-01" ;; Valid time + :as-of tx-100 ;; Transaction time + :where + [:alice :employment/status ?status]] + +;; History of corrections +[:find ?value ?tx ?valid-at + :where + [:alice :account/balance ?value ?tx ?valid-at]] +``` + +### 4.4 Storage Format + +**File Structure**: +``` +Page 0: Header (includes tx counter) +Page 1+: Facts with (E, A, V, ValidFrom, ValidTo, TxTime, Asserted) +``` + +**Indexes for Temporal Queries**: +- EAVT: Entity, Attribute, Value, Transaction +- AEVT: Attribute, Entity, Value, Transaction +- AVET: Attribute, Value, Entity, Transaction +- VAET: Value, Attribute, Entity, Transaction +- ValidTime index: (ValidFrom, ValidTo) for range queries + +### 4.5 Tests + +**Test Coverage**: +- Transaction time recording +- As-of queries +- Valid time periods +- Valid-at queries +- Bi-temporal queries +- History queries +- Time travel edge cases -**Deliverable**: Feature-rich query language +**Deliverable**: Full bi-temporal Datalog database + +**Timeline**: 3-4 months --- -## Phase 5: Cross-Platform Expansion +## Phase 5: ACID + WAL 🎯 FUTURE + +**Goal**: Add crash safety and transactions -**Goal**: WASM, mobile, multiple backends +**Status**: 🎯 Planned -**Status**: ⏳ Future +**Priority**: 🟡 High -### 5.1 WebAssembly Support +### 5.1 Write-Ahead Logging (WAL) **Features**: -- ⏳ IndexedDB backend for browsers -- ⏳ WASM compilation target -- ⏳ Browser-compatible API -- ⏳ Import/export between native and WASM +- 🎯 Embedded WAL (in same `.graph` file) +- 🎯 Append-only transaction log +- 🎯 Crash recovery (replay WAL on open) +- 🎯 Checkpoint mechanism (merge WAL to main pages) + +**Technical Approach**: +``` +File Structure: +Page 0: Header (includes wal_offset, last_checkpoint) +Page 1: EAVT index +Page 2+: Fact pages +WAL: Append-only log at end of file +``` + +**Why Embedded WAL**: +- ✅ Maintains single-file philosophy +- ✅ Easy to backup/share (one file) +- ✅ Simpler user experience -### 5.2 Mobile Optimization +### 5.2 Transactions **Features**: -- ⏳ iOS bindings (Swift FFI) -- ⏳ Android bindings (JNI/Kotlin) -- ⏳ Mobile-specific optimizations (battery, storage) -- ⏳ Background sync support +- 🎯 Transaction API: `BEGIN`, `COMMIT`, `ROLLBACK` +- 🎯 ACID compliance: + - Atomicity: All-or-nothing transactions + - Consistency: Enforce constraints + - Isolation: Serializable isolation + - Durability: WAL ensures persistence + +**API**: +```rust +let mut tx = db.begin_transaction()?; +tx.transact(vec![ + [:alice, :person/name, "Alice"], + [:alice, :friend, :bob], +])?; +tx.commit()?; // or tx.rollback()? +``` -### 5.3 Backend Flexibility +### 5.3 Crash Recovery **Features**: -- ⏳ Pluggable backends (users can implement `StorageBackend`) -- ⏳ Optional SQLite backend (feature flag) -- ⏳ Optional RocksDB backend (for advanced users, feature flag) +- 🎯 Detect unclean shutdown (incomplete checkpoint) +- 🎯 Replay WAL to reconstruct state +- 🎯 Validate checksums +- 🎯 Verify transaction completeness -**Deliverable**: Run anywhere - desktop, mobile, web, embedded +### 5.4 Tests + +**Test Coverage**: +- WAL write and read +- Transaction commit/rollback +- Crash during transaction (kill -9) +- Recovery from partial writes +- Checkpoint correctness +- Multiple transactions before checkpoint + +**Deliverable**: ACID-compliant database with crash safety + +**Timeline**: 2-3 months --- -## Phase 6: Ecosystem & Tooling +## Phase 6: Performance & Indexes 🎯 FUTURE -**Goal**: Developer experience and ecosystem +**Goal**: Make queries fast -**Status**: ⏳ Future +**Status**: 🎯 Planned + +**Priority**: 🟡 High -### 6.1 Developer Tools +### 6.1 Indexes **Features**: -- ⏳ Visual query builder -- ⏳ Database inspector/debugger -- ⏳ Schema designer -- ⏳ Query profiler -- ⏳ Migration tools +- 🎯 EAVT, AEVT, AVET, VAET covering indexes +- 🎯 B-tree or sorted page indexes +- 🎯 Index maintenance (auto-update on changes) +- 🎯 Temporal index (ValidFrom, ValidTo ranges) -### 6.2 Language Bindings +**Performance Targets**: +- Indexed fact lookup: <1ms +- Pattern match with index: <10ms for 100K facts +- Transitive closure: <100ms for typical graphs + +### 6.2 Query Optimization **Features**: -- ⏳ Python bindings -- ⏳ JavaScript/TypeScript bindings -- ⏳ C FFI for other languages +- 🎯 Query plan generation +- 🎯 Cost-based optimization +- 🎯 Index selection +- 🎯 Join order optimization +- 🎯 Rule evaluation optimization -### 6.3 Documentation & Examples +**Optimizer**: +- Choose best index for each pattern +- Reorder patterns by selectivity +- Push filters down +- Eliminate redundant patterns + +### 6.3 Caching **Features**: -- ⏳ Complete API reference -- ⏳ Query language specification -- ⏳ Cookbook (common patterns) -- ⏳ Performance tuning guide -- ⏳ Real-world examples +- 🎯 Query result caching +- 🎯 Rule evaluation caching +- 🎯 Page cache (LRU) -**Deliverable**: Production-ready ecosystem +### 6.4 Benchmarks + +**Benchmark Suite**: +- Insert throughput (facts/sec) +- Query latency (indexed, unindexed) +- Memory usage (various dataset sizes) +- File size growth +- Transaction throughput +- Time travel query performance + +**Target Scales**: +- Small: 10K facts (personal knowledge base) +- Medium: 100K facts (small business app) +- Large: 1M facts (production single-machine) + +**Deliverable**: Fast, indexed query engine + +**Timeline**: 2-3 months --- -## Phase 7: Enterprise Features (Optional) +## Phase 7: Cross-Platform Expansion 🎯 FUTURE -**Goal**: Features for larger deployments +**Goal**: WASM, mobile, language bindings -**Status**: ⏳ Future (Maybe) +**Status**: 🎯 Planned -**Features** (if needed): -- ⏳ Backup/restore utilities -- ⏳ Replication (read replicas) -- ⏳ Encryption at rest -- ⏳ Audit logging -- ⏳ Schema validation/enforcement +**Priority**: 🟢 Medium -**Note**: These might be better as separate crates, not in core. +### 7.1 WebAssembly Support ---- +**Features**: +- 🎯 IndexedDB backend for browsers +- 🎯 WASM compilation target +- 🎯 JavaScript API +- 🎯 Import/export between native and WASM -## GQL Spec Compliance Roadmap +### 7.2 Mobile Optimization -**Note**: Separate from architecture phases above. These are **feature milestones** for GQL spec coverage, not project phases. +**Features**: +- 🎯 iOS bindings (Swift FFI) +- 🎯 Android bindings (JNI/Kotlin) +- 🎯 Mobile-specific optimizations + +### 7.3 Language Bindings -**Current**: ~2-5% of ISO/IEC 39075:2024 +**Features**: +- 🎯 Python bindings +- 🎯 JavaScript/TypeScript bindings +- 🎯 C FFI for other languages -1. ✅ **Milestone 1**: Basic PoC - simple CRUD and queries -2. ⏳ **Milestone 2**: Complex patterns - multi-hop paths, variable-length -3. ⏳ **Milestone 3**: RETURN clause, projections, ORDER BY/LIMIT -4. ⏳ **Milestone 4**: UPDATE/DELETE operations -5. ⏳ **Milestone 5**: Aggregations and GROUP BY -6. ⏳ **Milestone 6**: Advanced expressions and operators -7. ⏳ **Milestone 7**: Schema, constraints, indexes -8. ⏳ **Milestone 8+**: Advanced types, multiple graphs, full spec compliance +**Deliverable**: Run anywhere - desktop, mobile, web, embedded -**Important**: We prioritize practical usefulness over spec compliance. A 20% compliant implementation that's reliable is better than 100% compliance that's buggy. +**Timeline**: 3-4 months --- -## Performance Benchmarking +## Phase 8: Ecosystem & Tooling 🎯 FUTURE -**Start After**: Phase 3.2 (indexes implemented) +**Goal**: Developer experience and ecosystem -**Benchmark Suite**: -- Insert throughput (nodes/sec, edges/sec) -- Query latency (indexed, unindexed) -- Memory usage (various dataset sizes) -- File size growth patterns -- Cache hit rates -- Transaction throughput +**Status**: 🎯 Planned -**Target Scales**: -- Small: 1K nodes, 5K edges (use case: personal notes) -- Medium: 100K nodes, 500K edges (use case: small business) -- Large: 1M nodes, 5M edges (use case: enterprise single-machine) +**Priority**: 🟢 Medium + +### 8.1 Developer Tools + +**Features**: +- 🎯 Database inspector/debugger +- 🎯 Query profiler +- 🎯 Time travel visualizer +- 🎯 Migration tools + +### 8.2 Documentation + +**Features**: +- 🎯 Complete API reference +- 🎯 Datalog language specification +- 🎯 Cookbook (common patterns) +- 🎯 Performance tuning guide +- 🎯 Real-world examples + +### 8.3 Ecosystem Libraries + +**Features**: +- 🎯 Graph algorithms (as separate crate) +- 🎯 Schema validation (optional) +- 🎯 Import/export tools +- 🎯 Backup utilities -**Not Targeting**: -- Billions of nodes (use Neo4j, TigerGraph) -- Distributed systems (not our use case) -- Real-time analytics at scale (not our use case) +**Deliverable**: Production-ready ecosystem + +**Timeline**: Ongoing --- ## Release Strategy ### v0.1.0 - ✅ Phase 1 Complete (PoC) -- In-memory graph database -- Basic query language +- In-memory property graph +- GQL-inspired queries - REPL console ### v0.2.0 - ✅ Phase 2 Complete (Embeddable) @@ -312,23 +586,37 @@ WAL: Append-only log at end of file - Cross-platform file format - Auto-save -### v0.3.0 - ⏳ Phase 3.1 (WAL & ACID) +**GQL Archive**: `archive/gql-phase-2` branch, `gql-phase-2-complete` tag + +### v0.3.0 - 🎯 Phase 3 (Datalog Core) +- EAV data model +- Datalog queries +- Recursive rules +- Pattern matching + +### v0.4.0 - 🎯 Phase 4 (Bi-temporal) +- Transaction time +- Valid time +- Time travel queries +- History queries + +### v0.5.0 - 🎯 Phase 5 (ACID) - Write-ahead logging -- Transactions (BEGIN/COMMIT/ROLLBACK) +- Transactions - Crash recovery - ACID compliance -### v0.4.0 - ⏳ Phase 3.2 (Performance) -- B-tree indexes +### v0.6.0 - 🎯 Phase 6 (Performance) +- Indexes (EAVT, AEVT, AVET, VAET) - Query optimization - Performance benchmarks -### v0.5.0 - ⏳ Phase 4 (Advanced Queries) -- Multi-hop paths -- RETURN clause -- Aggregations +### v0.7.0 - 🎯 Phase 7 (Cross-platform) +- WASM support +- Mobile bindings +- Language bindings -### v1.0.0 - ⏳ Production Ready +### v1.0.0 - 🎯 Production Ready (12-15 months) - Stable API - Stable file format - Comprehensive tests @@ -337,10 +625,10 @@ WAL: Append-only log at end of file - Backwards compatibility promise **Stability Promise**: After v1.0.0, we commit to: -- Backwards-compatible file format +- Backwards-compatible file format (decades) - Stable public API (semantic versioning) - Migration tools for any format changes -- Long-term support (decades) +- Long-term support --- @@ -348,8 +636,8 @@ WAL: Append-only log at end of file When evaluating features, ask: -1. **Does it align with philosophy?** (embedded, reliable, simple) -2. **Is it needed for target use cases?** (not enterprise distributed) +1. **Does it align with philosophy?** (embedded, reliable, simple, bi-temporal) +2. **Is it needed for target use cases?** (audit, event sourcing, knowledge graphs) 3. **Does it compromise reliability?** (stability over features) 4. **Can it be a separate crate?** (keep core small) @@ -359,66 +647,83 @@ When evaluating features, ask: - Built-in ML/AI - Features only useful at massive scale - Complex configuration +- Breaking the single-file philosophy **Say YES to**: - Crash safety - Data integrity +- Temporal queries - Query performance - Developer experience - Cross-platform support --- -## How to Contribute - -See each phase for specific tasks. Good starting points: +## Timeline (Rough Estimates) -**Easy**: -- Documentation improvements -- Example applications -- Test coverage -- Error message improvements +- ✅ Phase 1: Complete (December 2025) +- ✅ Phase 2: Complete (January 2026) +- 🎯 Phase 3: 3-4 months (Datalog core) +- 🎯 Phase 4: 3-4 months (Bi-temporal) +- 🎯 Phase 5: 2-3 months (ACID + WAL) +- 🎯 Phase 6: 2-3 months (Performance) +- 🎯 Phase 7: 3-4 months (Cross-platform) +- 🎯 Phase 8: Ongoing (Ecosystem) +- 🎯 **v1.0.0: 12-15 months** from now (vs. 24-30 months with GQL) -**Medium**: -- Additional query types -- Performance optimizations -- Platform-specific backends +**Note**: This is a hobby project. Timeline is flexible but realistic. -**Hard**: -- WAL implementation -- B-tree indexes -- Query optimizer -- WASM backend +**Comparison**: +- **GQL path**: 24-30 months to v1.0 (catching up to GraphLite) +- **Datalog path**: 12-15 months to v1.0 (proven patterns from Datomic/XTDB) --- -## Timeline (Rough Estimates) +## Current Focus + +**Right Now**: Planning Phase 3 - Datalog Core -- ✅ Phase 1: Complete -- ✅ Phase 2: Complete -- ⏳ Phase 3: 3-6 months -- ⏳ Phase 4: 4-6 months -- ⏳ Phase 5: 6-12 months -- ⏳ Phase 6: Ongoing -- ⏳ v1.0.0: 12-18 months from now +**Immediate Next Steps**: +1. Design EAV data model +2. Implement Datalog parser (EDN syntax) +3. Build basic query executor +4. Add recursive rules +5. Update REPL for Datalog +6. Migrate tests -**Note**: This is a hobby project. Timeline is flexible. +**Key Decisions Made**: +- ✅ Pivot to Datalog (simpler, better for temporal) +- ✅ Bi-temporal as first-class feature (not afterthought) +- ✅ Keep single-file philosophy +- ✅ Target 12-15 months to v1.0 + +See [GitHub Issues](https://github.com/adityamukho/minigraf/issues) for specific tasks. --- -## Current Focus +## Why This Roadmap is Better -**Right Now**: Phase 3.1 - Write-Ahead Logging +**Compared to GQL roadmap:** -**Next Steps**: -1. Design embedded WAL structure -2. Implement transaction API -3. Add crash recovery -4. Test unclean shutdowns -5. Benchmark transaction throughput +1. **Faster**: 12-15 months vs. 24-30 months +2. **Simpler**: Proven Datalog patterns vs. novel GQL implementation +3. **More unique**: Single-file bi-temporal Datalog (no competitor) +4. **Better fit**: Temporal semantics natural in Datalog +5. **More reliable**: 40+ years of Datalog research vs. new GQL spec -See [GitHub Issues](https://github.com/adityamukho/minigraf/issues) for specific tasks. +**Trade-offs accepted:** +- ❌ Lose familiarity of SQL-like syntax +- ❌ Smaller developer audience (fewer know Datalog) +- ✅ Gain simplicity and power of logic programming +- ✅ Gain natural temporal queries +- ✅ Gain recursive rules without pain + +**Market positioning:** +- **GQL space**: GraphLite won (full spec, mature, ACID) +- **Datalog space**: Gap for single-file embedded bi-temporal DB + +We're not competing with GraphLite anymore. We're creating a new category. --- -Last Updated: Phase 2 Complete (January 2026) +Last Updated: Phase 2 Complete, Datalog Pivot (January 2026) diff --git a/src/graph/mod.rs b/src/graph/mod.rs index 4b7a27633..653ff39bf 100644 --- a/src/graph/mod.rs +++ b/src/graph/mod.rs @@ -2,4 +2,4 @@ pub mod types; pub mod storage; pub use types::{Node, Edge, Property, PropertyValue, NodeId, EdgeId}; -pub use storage::GraphStorage; +pub use storage::{GraphStorage, FactStorage}; diff --git a/src/graph/storage.rs b/src/graph/storage.rs index d7816672a..5719cf821 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -1,4 +1,5 @@ use crate::graph::types::{Edge, EdgeId, Node, NodeId}; +use crate::graph::types::{Fact, Value, EntityId, Attribute, TxId, tx_id_now}; use anyhow::Result; use std::collections::HashMap; use std::sync::{Arc, RwLock}; @@ -94,6 +95,232 @@ impl GraphStorage { } } +// ============================================================================ +// Datalog Fact Storage (Phase 3+) +// ============================================================================ + +/// In-memory storage for Datalog facts with transaction support +/// +/// FactStorage maintains an append-only log of facts. Facts are never deleted, +/// only retracted (with asserted=false). This enables: +/// - Full history tracking +/// - Time travel queries (Phase 4) +/// - Audit trails +/// +/// # Examples +/// ``` +/// use minigraf::{FactStorage, Value}; +/// use uuid::Uuid; +/// +/// let storage = FactStorage::new(); +/// +/// // Add facts (automatic timestamping) +/// let alice = Uuid::new_v4(); +/// storage.transact(vec![ +/// (alice, ":person/name".to_string(), Value::String("Alice".to_string())), +/// (alice, ":person/age".to_string(), Value::Integer(30)), +/// ]).unwrap(); +/// +/// // Query facts +/// let facts = storage.get_facts_by_entity(&alice).unwrap(); +/// assert_eq!(facts.len(), 2); +/// ``` +#[derive(Clone)] +pub struct FactStorage { + /// Append-only log of all facts (assertions and retractions) + facts: Arc>>, +} + +impl Default for FactStorage { + fn default() -> Self { + Self::new() + } +} + +impl FactStorage { + /// Create a new empty fact storage + pub fn new() -> Self { + FactStorage { + facts: Arc::new(RwLock::new(Vec::new())), + } + } + + /// Transact a batch of facts with automatic timestamping + /// + /// All facts in a single transaction get the same timestamp (TxId). + /// This groups related facts together for atomicity. + /// + /// # Arguments + /// * `fact_tuples` - Vec of (EntityId, Attribute, Value) tuples to assert + /// + /// # Returns + /// The TxId (timestamp) assigned to these facts + pub fn transact(&self, fact_tuples: Vec<(EntityId, Attribute, Value)>) -> Result { + let tx_id = tx_id_now(); + + let facts: Vec = fact_tuples + .into_iter() + .map(|(entity, attribute, value)| Fact::new(entity, attribute, value, tx_id)) + .collect(); + + let mut storage = self.facts.write().unwrap(); + storage.extend(facts); + + Ok(tx_id) + } + + /// Retract a batch of facts with automatic timestamping + /// + /// Retractions are new facts with asserted=false. The original facts remain + /// in the log for history tracking. + /// + /// # Arguments + /// * `fact_tuples` - Vec of (EntityId, Attribute, Value) tuples to retract + /// + /// # Returns + /// The TxId (timestamp) assigned to these retractions + pub fn retract(&self, fact_tuples: Vec<(EntityId, Attribute, Value)>) -> Result { + let tx_id = tx_id_now(); + + let retractions: Vec = fact_tuples + .into_iter() + .map(|(entity, attribute, value)| Fact::retract(entity, attribute, value, tx_id)) + .collect(); + + let mut storage = self.facts.write().unwrap(); + storage.extend(retractions); + + Ok(tx_id) + } + + /// Get all facts (including retractions) + /// + /// Returns the complete append-only log. For current state, filter by + /// asserted=true and take the most recent fact for each (E, A) pair. + pub fn get_all_facts(&self) -> Result> { + let storage = self.facts.read().unwrap(); + Ok(storage.clone()) + } + + /// Get all asserted facts (filters out retractions) + /// + /// Returns only facts where asserted=true. This gives you the currently + /// valid facts, but includes all historical versions. + pub fn get_asserted_facts(&self) -> Result> { + let storage = self.facts.read().unwrap(); + Ok(storage + .iter() + .filter(|f| f.is_asserted()) + .cloned() + .collect()) + } + + /// Get all facts for a specific entity + /// + /// # Arguments + /// * `entity_id` - The entity to query + /// + /// # Returns + /// All facts (assertions and retractions) about this entity + pub fn get_facts_by_entity(&self, entity_id: &EntityId) -> Result> { + let storage = self.facts.read().unwrap(); + Ok(storage + .iter() + .filter(|f| &f.entity == entity_id) + .cloned() + .collect()) + } + + /// Get all facts for a specific attribute + /// + /// # Arguments + /// * `attribute` - The attribute to query (e.g., ":person/name") + /// + /// # Returns + /// All facts with this attribute + pub fn get_facts_by_attribute(&self, attribute: &Attribute) -> Result> { + let storage = self.facts.read().unwrap(); + Ok(storage + .iter() + .filter(|f| &f.attribute == attribute) + .cloned() + .collect()) + } + + /// Get all facts for a specific entity and attribute + /// + /// # Arguments + /// * `entity_id` - The entity to query + /// * `attribute` - The attribute to query + /// + /// # Returns + /// All facts (including history) for this entity-attribute pair + pub fn get_facts_by_entity_attribute( + &self, + entity_id: &EntityId, + attribute: &Attribute, + ) -> Result> { + let storage = self.facts.read().unwrap(); + Ok(storage + .iter() + .filter(|f| &f.entity == entity_id && &f.attribute == attribute) + .cloned() + .collect()) + } + + /// Get the current value for an entity-attribute pair + /// + /// Returns the most recent asserted (non-retracted) value, or None if + /// the attribute was retracted or never existed. + /// + /// # Arguments + /// * `entity_id` - The entity to query + /// * `attribute` - The attribute to query + /// + /// # Returns + /// The current value, or None if retracted or not found + pub fn get_current_value( + &self, + entity_id: &EntityId, + attribute: &Attribute, + ) -> Result> { + let storage = self.facts.read().unwrap(); + + // Find the most recent fact for this (entity, attribute) pair + let mut relevant_facts: Vec<&Fact> = storage + .iter() + .filter(|f| &f.entity == entity_id && &f.attribute == attribute) + .collect(); + + // Sort by transaction ID (timestamp) descending + relevant_facts.sort_by(|a, b| b.tx_id.cmp(&a.tx_id)); + + // Return the value if the most recent fact is an assertion + Ok(relevant_facts + .first() + .and_then(|f| if f.is_asserted() { Some(f.value.clone()) } else { None })) + } + + /// Get the count of all facts in storage + pub fn fact_count(&self) -> usize { + let storage = self.facts.read().unwrap(); + storage.len() + } + + /// Get the count of currently asserted facts + pub fn asserted_fact_count(&self) -> usize { + let storage = self.facts.read().unwrap(); + storage.iter().filter(|f| f.is_asserted()).count() + } + + /// Clear all facts (for testing) + pub fn clear(&self) -> Result<()> { + let mut storage = self.facts.write().unwrap(); + storage.clear(); + Ok(()) + } +} + #[cfg(test)] mod tests { use super::*; @@ -204,4 +431,302 @@ mod tests { let all_nodes = storage.get_all_nodes().unwrap(); assert_eq!(all_nodes.len(), 2); } + + // ======================================================================== + // FactStorage Tests (Phase 3+) + // ======================================================================== + + #[test] + fn test_fact_storage_transact() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + + // Transact facts + let tx_id = storage + .transact(vec![ + ( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice, ":person/age".to_string(), Value::Integer(30)), + ]) + .unwrap(); + + // Verify facts were stored + assert_eq!(storage.fact_count(), 2); + assert_eq!(storage.asserted_fact_count(), 2); + + // Verify all facts have same tx_id + let facts = storage.get_facts_by_entity(&alice).unwrap(); + assert_eq!(facts.len(), 2); + assert!(facts.iter().all(|f| f.tx_id == tx_id)); + assert!(facts.iter().all(|f| f.is_asserted())); + } + + #[test] + fn test_fact_storage_retract() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + + // Assert a fact + let _tx1 = storage + .transact(vec![( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )]) + .unwrap(); + + std::thread::sleep(std::time::Duration::from_millis(2)); + + // Retract the fact + let tx2 = storage + .retract(vec![( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )]) + .unwrap(); + + // Both facts exist in storage (assertion + retraction) + assert_eq!(storage.fact_count(), 2); + // But only 1 is asserted + assert_eq!(storage.asserted_fact_count(), 1); + + let facts = storage.get_facts_by_entity(&alice).unwrap(); + assert_eq!(facts.len(), 2); + + // Find the retraction + let retraction = facts.iter().find(|f| f.tx_id == tx2).unwrap(); + assert!(retraction.is_retracted()); + } + + #[test] + fn test_fact_storage_get_by_entity() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + let bob = Uuid::new_v4(); + + storage + .transact(vec![ + ( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + ( + bob, + ":person/name".to_string(), + Value::String("Bob".to_string()), + ), + ]) + .unwrap(); + + let alice_facts = storage.get_facts_by_entity(&alice).unwrap(); + assert_eq!(alice_facts.len(), 1); + assert_eq!(alice_facts[0].value, Value::String("Alice".to_string())); + + let bob_facts = storage.get_facts_by_entity(&bob).unwrap(); + assert_eq!(bob_facts.len(), 1); + assert_eq!(bob_facts[0].value, Value::String("Bob".to_string())); + } + + #[test] + fn test_fact_storage_get_by_attribute() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + let bob = Uuid::new_v4(); + + storage + .transact(vec![ + ( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice, ":person/age".to_string(), Value::Integer(30)), + ( + bob, + ":person/name".to_string(), + Value::String("Bob".to_string()), + ), + ]) + .unwrap(); + + // Get all :person/name facts + let name_facts = storage + .get_facts_by_attribute(&":person/name".to_string()) + .unwrap(); + assert_eq!(name_facts.len(), 2); + + // Get all :person/age facts + let age_facts = storage + .get_facts_by_attribute(&":person/age".to_string()) + .unwrap(); + assert_eq!(age_facts.len(), 1); + } + + #[test] + fn test_fact_storage_get_current_value() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + + // Set initial value + storage + .transact(vec![( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )]) + .unwrap(); + + std::thread::sleep(std::time::Duration::from_millis(2)); + + // Update value + storage + .transact(vec![( + alice, + ":person/name".to_string(), + Value::String("Alice Smith".to_string()), + )]) + .unwrap(); + + // Current value should be the most recent + let current = storage + .get_current_value(&alice, &":person/name".to_string()) + .unwrap(); + assert_eq!(current, Some(Value::String("Alice Smith".to_string()))); + + std::thread::sleep(std::time::Duration::from_millis(2)); + + // Retract the value + storage + .retract(vec![( + alice, + ":person/name".to_string(), + Value::String("Alice Smith".to_string()), + )]) + .unwrap(); + + // Current value should now be None (retracted) + let current = storage + .get_current_value(&alice, &":person/name".to_string()) + .unwrap(); + assert_eq!(current, None); + } + + #[test] + fn test_fact_storage_entity_references() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + let bob = Uuid::new_v4(); + + // Alice is friends with Bob (using Ref) + storage + .transact(vec![ + ( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice, ":friend".to_string(), Value::Ref(bob)), + ( + bob, + ":person/name".to_string(), + Value::String("Bob".to_string()), + ), + ]) + .unwrap(); + + // Get friendship + let friendship_facts = storage + .get_facts_by_entity_attribute(&alice, &":friend".to_string()) + .unwrap(); + assert_eq!(friendship_facts.len(), 1); + assert_eq!(friendship_facts[0].value.as_ref(), Some(bob)); + } + + #[test] + fn test_fact_storage_history_tracking() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + + // Create multiple versions over time + let tx1 = storage + .transact(vec![(alice, ":person/age".to_string(), Value::Integer(30))]) + .unwrap(); + + std::thread::sleep(std::time::Duration::from_millis(2)); + + let tx2 = storage + .transact(vec![(alice, ":person/age".to_string(), Value::Integer(31))]) + .unwrap(); + + std::thread::sleep(std::time::Duration::from_millis(2)); + + let tx3 = storage + .transact(vec![(alice, ":person/age".to_string(), Value::Integer(32))]) + .unwrap(); + + // All versions are in history + let history = storage + .get_facts_by_entity_attribute(&alice, &":person/age".to_string()) + .unwrap(); + assert_eq!(history.len(), 3); + + // TxIds should be increasing (chronological) + assert!(tx1 < tx2); + assert!(tx2 < tx3); + + // Current value should be most recent + let current = storage + .get_current_value(&alice, &":person/age".to_string()) + .unwrap(); + assert_eq!(current, Some(Value::Integer(32))); + } + + #[test] + fn test_fact_storage_batch_transact() { + use uuid::Uuid; + + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + + // Transact multiple facts at once + let tx_id = storage + .transact(vec![ + ( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice, ":person/age".to_string(), Value::Integer(30)), + ( + alice, + ":person/email".to_string(), + Value::String("alice@example.com".to_string()), + ), + ]) + .unwrap(); + + // All facts should have same tx_id (atomic batch) + let facts = storage.get_facts_by_entity(&alice).unwrap(); + assert_eq!(facts.len(), 3); + assert!(facts.iter().all(|f| f.tx_id == tx_id)); + } } diff --git a/src/graph/types.rs b/src/graph/types.rs index ac71cd0c4..8aaf701c7 100644 --- a/src/graph/types.rs +++ b/src/graph/types.rs @@ -108,6 +108,214 @@ impl Edge { } } +// ============================================================================ +// Datalog EAV Model (Phase 3+) +// ============================================================================ + +use std::time::{SystemTime, UNIX_EPOCH}; + +/// Transaction ID type - milliseconds since UNIX epoch +/// +/// We use timestamps as transaction IDs for natural chronological ordering +/// and consistency with bi-temporal valid_time (Phase 4). Millisecond precision +/// is sufficient for Phase 3's single-threaded usage. +pub type TxId = u64; + +/// Get current timestamp as transaction ID (milliseconds since UNIX epoch) +pub fn tx_id_now() -> TxId { + SystemTime::now() + .duration_since(UNIX_EPOCH) + .expect("System time before UNIX epoch") + .as_millis() as u64 +} + +/// Create a TxId from a SystemTime +pub fn tx_id_from_system_time(time: SystemTime) -> TxId { + time.duration_since(UNIX_EPOCH) + .expect("System time before UNIX epoch") + .as_millis() as u64 +} + +/// Convert a TxId back to a SystemTime +pub fn tx_id_to_system_time(tx_id: TxId) -> SystemTime { + UNIX_EPOCH + std::time::Duration::from_millis(tx_id) +} + +/// Entity ID type - using UUID for consistency with existing Node/Edge IDs +pub type EntityId = Uuid; + +/// Attribute name - namespace-qualified keywords like ":person/name" or ":friend" +pub type Attribute = String; + +/// Value types for Datalog facts +/// Extends PropertyValue with Ref (entity reference) and Keyword support +#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)] +pub enum Value { + /// String value + String(String), + /// 64-bit integer + Integer(i64), + /// 64-bit floating point + Float(f64), + /// Boolean value + Boolean(bool), + /// Reference to another entity (for relationships) + Ref(EntityId), + /// Keyword (e.g., ":status/active", ":person") + Keyword(String), + /// Null/None value + Null, +} + +impl Value { + /// Extract string value if this is a String variant + pub fn as_string(&self) -> Option<&str> { + match self { + Value::String(s) => Some(s), + _ => None, + } + } + + /// Extract integer value if this is an Integer variant + pub fn as_integer(&self) -> Option { + match self { + Value::Integer(i) => Some(*i), + _ => None, + } + } + + /// Extract float value if this is a Float variant + pub fn as_float(&self) -> Option { + match self { + Value::Float(f) => Some(*f), + _ => None, + } + } + + /// Extract boolean value if this is a Boolean variant + pub fn as_boolean(&self) -> Option { + match self { + Value::Boolean(b) => Some(*b), + _ => None, + } + } + + /// Extract entity reference if this is a Ref variant + pub fn as_ref(&self) -> Option { + match self { + Value::Ref(id) => Some(*id), + _ => None, + } + } + + /// Extract keyword if this is a Keyword variant + pub fn as_keyword(&self) -> Option<&str> { + match self { + Value::Keyword(k) => Some(k), + _ => None, + } + } + + /// Check if this value is Null + pub fn is_null(&self) -> bool { + matches!(self, Value::Null) + } +} + +/// A Datalog fact: (Entity, Attribute, Value) triple with transaction metadata +/// +/// This is the core data structure for Phase 3+. Facts are immutable and versioned +/// by transaction ID. Facts are never deleted, only retracted (asserted=false). +/// +/// # Examples +/// ``` +/// use minigraf::{Fact, Value}; +/// use uuid::Uuid; +/// +/// // Fact: Alice's name is "Alice" +/// let alice_id = Uuid::new_v4(); +/// let fact = Fact::new( +/// alice_id, +/// ":person/name".to_string(), +/// Value::String("Alice".to_string()), +/// 1, // transaction ID +/// ); +/// +/// // Fact: Alice is friends with Bob (reference) +/// let bob_id = Uuid::new_v4(); +/// let friendship = Fact::new( +/// alice_id, +/// ":friend".to_string(), +/// Value::Ref(bob_id), +/// 2, +/// ); +/// ``` +#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)] +pub struct Fact { + /// The entity this fact is about + pub entity: EntityId, + /// The attribute/property name (namespace-qualified, e.g., ":person/name") + pub attribute: Attribute, + /// The value of this attribute + pub value: Value, + /// Transaction ID that asserted or retracted this fact + pub tx_id: TxId, + /// True if this fact is asserted, false if retracted + /// Retractions are used instead of deletions to maintain history + pub asserted: bool, +} + +impl Fact { + /// Create a new asserted fact + pub fn new(entity: EntityId, attribute: Attribute, value: Value, tx_id: TxId) -> Self { + Fact { + entity, + attribute, + value, + tx_id, + asserted: true, + } + } + + /// Create a retraction of a fact + pub fn retract(entity: EntityId, attribute: Attribute, value: Value, tx_id: TxId) -> Self { + Fact { + entity, + attribute, + value, + tx_id, + asserted: false, + } + } + + /// Create a fact with explicit asserted flag + pub fn with_asserted( + entity: EntityId, + attribute: Attribute, + value: Value, + tx_id: TxId, + asserted: bool, + ) -> Self { + Fact { + entity, + attribute, + value, + tx_id, + asserted, + } + } + + /// Check if this is an assertion (not a retraction) + pub fn is_asserted(&self) -> bool { + self.asserted + } + + /// Check if this is a retraction + pub fn is_retracted(&self) -> bool { + !self.asserted + } +} + #[cfg(test)] mod tests { use super::*; @@ -171,4 +379,188 @@ mod tests { let bool_val = PropertyValue::Boolean(true); assert_eq!(bool_val.as_boolean(), Some(true)); } + + // ======================================================================== + // EAV Model Tests (Phase 3+) + // ======================================================================== + + #[test] + fn test_tx_id_timestamp() { + use std::time::SystemTime; + + // Test tx_id_now() returns a reasonable timestamp + let tx1 = tx_id_now(); + std::thread::sleep(std::time::Duration::from_millis(5)); + let tx2 = tx_id_now(); + + // tx2 should be after tx1 + assert!(tx2 > tx1, "Transaction IDs should be chronologically ordered"); + + // Difference should be at least 5ms (we slept for 5ms) + assert!(tx2 - tx1 >= 5, "Expected at least 5ms difference"); + + // Test round-trip conversion + let now = SystemTime::now(); + let tx_id = tx_id_from_system_time(now); + let recovered = tx_id_to_system_time(tx_id); + + // Should be within 1ms (we lose precision converting to millis) + let diff = recovered.duration_since(now).unwrap_or_else(|e| e.duration()); + assert!(diff.as_millis() < 1, "Round-trip conversion should preserve timestamp within 1ms"); + } + + #[test] + fn test_tx_id_ordering() { + // TxIds created sequentially should be ordered + let mut tx_ids = vec![]; + for _ in 0..5 { + tx_ids.push(tx_id_now()); + std::thread::sleep(std::time::Duration::from_millis(2)); + } + + // Verify chronological order + for i in 1..tx_ids.len() { + assert!( + tx_ids[i] > tx_ids[i - 1], + "TxIds should be strictly increasing" + ); + } + } + + #[test] + fn test_value_creation_and_accessors() { + // String value + let string_val = Value::String("Alice".to_string()); + assert_eq!(string_val.as_string(), Some("Alice")); + assert_eq!(string_val.as_integer(), None); + assert!(!string_val.is_null()); + + // Integer value + let int_val = Value::Integer(42); + assert_eq!(int_val.as_integer(), Some(42)); + assert_eq!(int_val.as_string(), None); + + // Float value + let float_val = Value::Float(3.14); + assert_eq!(float_val.as_float(), Some(3.14)); + + // Boolean value + let bool_val = Value::Boolean(true); + assert_eq!(bool_val.as_boolean(), Some(true)); + + // Reference value + let ref_id = Uuid::new_v4(); + let ref_val = Value::Ref(ref_id); + assert_eq!(ref_val.as_ref(), Some(ref_id)); + assert_eq!(ref_val.as_string(), None); + + // Keyword value + let keyword_val = Value::Keyword(":person".to_string()); + assert_eq!(keyword_val.as_keyword(), Some(":person")); + + // Null value + let null_val = Value::Null; + assert!(null_val.is_null()); + assert_eq!(null_val.as_string(), None); + } + + #[test] + fn test_fact_creation() { + let entity = Uuid::new_v4(); + let fact = Fact::new( + entity, + ":person/name".to_string(), + Value::String("Alice".to_string()), + 1, + ); + + assert_eq!(fact.entity, entity); + assert_eq!(fact.attribute, ":person/name"); + assert_eq!(fact.value, Value::String("Alice".to_string())); + assert_eq!(fact.tx_id, 1); + assert!(fact.is_asserted()); + assert!(!fact.is_retracted()); + } + + #[test] + fn test_fact_retraction() { + let entity = Uuid::new_v4(); + let fact = Fact::retract( + entity, + ":person/name".to_string(), + Value::String("Alice".to_string()), + 2, + ); + + assert_eq!(fact.entity, entity); + assert_eq!(fact.attribute, ":person/name"); + assert_eq!(fact.tx_id, 2); + assert!(!fact.is_asserted()); + assert!(fact.is_retracted()); + } + + #[test] + fn test_fact_with_ref_value() { + let alice = Uuid::new_v4(); + let bob = Uuid::new_v4(); + + // Fact: Alice is friends with Bob + let friendship = Fact::new(alice, ":friend".to_string(), Value::Ref(bob), 1); + + assert_eq!(friendship.entity, alice); + assert_eq!(friendship.attribute, ":friend"); + assert_eq!(friendship.value.as_ref(), Some(bob)); + assert!(friendship.is_asserted()); + } + + #[test] + fn test_fact_equality() { + let entity = Uuid::new_v4(); + + let fact1 = Fact::new( + entity, + ":person/name".to_string(), + Value::String("Alice".to_string()), + 1, + ); + + let fact2 = Fact::new( + entity, + ":person/name".to_string(), + Value::String("Alice".to_string()), + 1, + ); + + assert_eq!(fact1, fact2); + + // Different transaction ID = different fact + let fact3 = Fact::new( + entity, + ":person/name".to_string(), + Value::String("Alice".to_string()), + 2, + ); + + assert_ne!(fact1, fact3); + } + + #[test] + fn test_value_types() { + let values = vec![ + Value::String("test".to_string()), + Value::Integer(42), + Value::Float(3.14), + Value::Boolean(true), + Value::Ref(Uuid::new_v4()), + Value::Keyword(":status/active".to_string()), + Value::Null, + ]; + + // All values should serialize/deserialize correctly + for value in values { + let serialized = serde_json::to_string(&value).unwrap(); + let deserialized: Value = serde_json::from_str(&serialized).unwrap(); + assert_eq!(value, deserialized); + } + } } diff --git a/src/lib.rs b/src/lib.rs index b2bfd87c4..b6ac43046 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -4,8 +4,25 @@ pub mod query; pub mod repl; pub mod storage; +// Property Graph exports (Phase 1-2) pub use graph::{GraphStorage, Node, Edge, Property, PropertyValue}; + +// Datalog EAV storage (Phase 3) +pub use graph::FactStorage; + +// Datalog EAV exports (Phase 3+) +pub use graph::types::{ + Fact, Value, EntityId, TxId, Attribute, + tx_id_now, tx_id_from_system_time, tx_id_to_system_time, +}; + pub use minigraf::Minigraf; pub use query::{parse_query, Query, QueryExecutor}; pub use repl::Repl; pub use storage::{StorageBackend, FileHeader, PAGE_SIZE}; + +// Datalog query API (Phase 3+) +pub use query::datalog::{ + parse_datalog_command, parse_edn, DatalogCommand, DatalogExecutor, DatalogQuery, EdnValue, + Pattern, PatternMatcher, QueryResult as DatalogQueryResult, Transaction, +}; diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs new file mode 100644 index 000000000..e4c974c81 --- /dev/null +++ b/src/query/datalog/executor.rs @@ -0,0 +1,344 @@ +use super::matcher::{edn_to_entity_id, edn_to_value, PatternMatcher}; +use super::types::{DatalogCommand, DatalogQuery, EdnValue, Transaction}; +use crate::graph::types::{TxId, Value}; +use crate::graph::FactStorage; +use anyhow::{anyhow, Result}; + +/// Result of executing a Datalog query +#[derive(Debug, Clone, PartialEq)] +pub enum QueryResult { + /// Transaction completed successfully with TX ID + Transacted(TxId), + /// Retraction completed successfully with TX ID + Retracted(TxId), + /// Query results: list of variable bindings + QueryResults { + vars: Vec, + results: Vec>, + }, + /// Empty result (e.g., for future rule definitions) + Ok, +} + +/// Executor for Datalog commands +pub struct DatalogExecutor { + storage: FactStorage, +} + +impl DatalogExecutor { + pub fn new(storage: FactStorage) -> Self { + DatalogExecutor { storage } + } + + /// Execute a Datalog command + pub fn execute(&self, command: DatalogCommand) -> Result { + match command { + DatalogCommand::Transact(tx) => self.execute_transact(tx), + DatalogCommand::Retract(tx) => self.execute_retract(tx), + DatalogCommand::Query(query) => self.execute_query(query), + DatalogCommand::Rule(_rule) => { + // TODO: Implement rule execution in later phase + Err(anyhow!("Rule execution not yet implemented")) + } + } + } + + /// Execute a transact command: add facts to storage + fn execute_transact(&self, tx: Transaction) -> Result { + let mut fact_tuples = Vec::new(); + + for pattern in tx.facts { + let entity_id = edn_to_entity_id(&pattern.entity) + .map_err(|e| anyhow!("Invalid entity: {}", e))?; + + let attribute = match &pattern.attribute { + EdnValue::Keyword(k) => k.clone(), + _ => return Err(anyhow!("Attribute must be a keyword")), + }; + + let value = + edn_to_value(&pattern.value).map_err(|e| anyhow!("Invalid value: {}", e))?; + + fact_tuples.push((entity_id, attribute, value)); + } + + let tx_id = self + .storage + .transact(fact_tuples) + .map_err(|e| anyhow!("Transaction failed: {}", e))?; + + Ok(QueryResult::Transacted(tx_id)) + } + + /// Execute a retract command: retract facts from storage + fn execute_retract(&self, tx: Transaction) -> Result { + let mut fact_tuples = Vec::new(); + + for pattern in tx.facts { + let entity_id = edn_to_entity_id(&pattern.entity) + .map_err(|e| anyhow!("Invalid entity: {}", e))?; + + let attribute = match &pattern.attribute { + EdnValue::Keyword(k) => k.clone(), + _ => return Err(anyhow!("Attribute must be a keyword")), + }; + + let value = + edn_to_value(&pattern.value).map_err(|e| anyhow!("Invalid value: {}", e))?; + + fact_tuples.push((entity_id, attribute, value)); + } + + let tx_id = self + .storage + .retract(fact_tuples) + .map_err(|e| anyhow!("Retraction failed: {}", e))?; + + Ok(QueryResult::Retracted(tx_id)) + } + + /// Execute a query: find matching facts and return specified variables + fn execute_query(&self, query: DatalogQuery) -> Result { + let matcher = PatternMatcher::new(self.storage.clone()); + + // Match all patterns and get bindings + let bindings = matcher.match_patterns(&query.patterns); + + // Extract requested variables from bindings + let mut results = Vec::new(); + for binding in bindings { + let mut row = Vec::new(); + for var in &query.find { + if let Some(value) = binding.get(var) { + row.push(value.clone()); + } else { + // Variable not bound in this result - skip this result + // (This can happen if the variable wasn't mentioned in patterns) + continue; + } + } + if row.len() == query.find.len() { + results.push(row); + } + } + + Ok(QueryResult::QueryResults { + vars: query.find, + results, + }) + } + + /// Get the underlying storage (for testing) + pub fn storage(&self) -> &FactStorage { + &self.storage + } +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::query::datalog::parser::parse_datalog_command; + use uuid::Uuid; + + #[test] + fn test_execute_transact() { + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage); + + let cmd = parse_datalog_command( + r#"(transact [[:alice :person/name "Alice"] + [:alice :person/age 30]])"#, + ) + .unwrap(); + + let result = executor.execute(cmd).unwrap(); + match result { + QueryResult::Transacted(tx_id) => { + assert!(tx_id > 0); + } + _ => panic!("Expected Transacted result"), + } + + // Verify facts were added + let facts = executor.storage().get_asserted_facts().unwrap(); + assert_eq!(facts.len(), 2); + } + + #[test] + fn test_execute_simple_query() { + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage.clone()); + + // Add some facts + let alice_id = Uuid::new_v4(); + storage + .transact(vec![ + ( + alice_id, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice_id, ":person/age".to_string(), Value::Integer(30)), + ]) + .unwrap(); + + // Query for name + let cmd = + parse_datalog_command(r#"(query [:find ?name :where [?e :person/name ?name]])"#) + .unwrap(); + + let result = executor.execute(cmd).unwrap(); + match result { + QueryResult::QueryResults { vars, results } => { + assert_eq!(vars, vec!["?name"]); + assert_eq!(results.len(), 1); + assert_eq!(results[0][0], Value::String("Alice".to_string())); + } + _ => panic!("Expected QueryResults"), + } + } + + #[test] + fn test_execute_multi_pattern_query() { + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage.clone()); + + // Add some facts + let alice_id = Uuid::new_v4(); + storage + .transact(vec![ + ( + alice_id, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice_id, ":person/age".to_string(), Value::Integer(30)), + ]) + .unwrap(); + + // Query for both name and age + let cmd = parse_datalog_command( + r#"(query [:find ?name ?age + :where [?e :person/name ?name] + [?e :person/age ?age]])"#, + ) + .unwrap(); + + let result = executor.execute(cmd).unwrap(); + match result { + QueryResult::QueryResults { vars, results } => { + assert_eq!(vars, vec!["?name", "?age"]); + assert_eq!(results.len(), 1); + assert_eq!(results[0][0], Value::String("Alice".to_string())); + assert_eq!(results[0][1], Value::Integer(30)); + } + _ => panic!("Expected QueryResults"), + } + } + + #[test] + fn test_execute_query_no_results() { + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage); + + // Query with no matching facts + let cmd = + parse_datalog_command(r#"(query [:find ?name :where [?e :person/name ?name]])"#) + .unwrap(); + + let result = executor.execute(cmd).unwrap(); + match result { + QueryResult::QueryResults { vars, results } => { + assert_eq!(vars, vec!["?name"]); + assert_eq!(results.len(), 0); + } + _ => panic!("Expected QueryResults"), + } + } + + #[test] + fn test_execute_retract() { + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage.clone()); + + // Add a fact + let alice_id = Uuid::new_v4(); + storage + .transact(vec![( + alice_id, + ":person/age".to_string(), + Value::Integer(30), + )]) + .unwrap(); + + // Verify it exists + let current_value = storage + .get_current_value(&alice_id, &":person/age".to_string()) + .unwrap(); + assert_eq!(current_value, Some(Value::Integer(30))); + + // Small delay to ensure different timestamp + std::thread::sleep(std::time::Duration::from_millis(2)); + + // Retract it using UUID-based entity reference + let cmd = parse_datalog_command( + format!( + r#"(retract [[#uuid "{}" :person/age 30]])"#, + alice_id.to_string() + ) + .as_str(), + ) + .unwrap(); + + let result = executor.execute(cmd).unwrap(); + match result { + QueryResult::Retracted(tx_id) => { + assert!(tx_id > 0); + } + _ => panic!("Expected Retracted result"), + } + + // Verify it's retracted (current value should be None) + let current_value = storage + .get_current_value(&alice_id, &":person/age".to_string()) + .unwrap(); + assert_eq!(current_value, None); + } + + #[test] + fn test_transact_with_keyword_entity() { + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage.clone()); + + // Transact with keyword-based entity (will be converted to deterministic UUID) + let cmd = parse_datalog_command( + r#"(transact [[:alice :person/name "Alice"] + [:alice :person/age 30]])"#, + ) + .unwrap(); + + let result = executor.execute(cmd).unwrap(); + match result { + QueryResult::Transacted(_) => {} + _ => panic!("Expected Transacted result"), + } + + // Query to verify both facts share the same entity + let query_cmd = parse_datalog_command( + r#"(query [:find ?name ?age + :where [?e :person/name ?name] + [?e :person/age ?age]])"#, + ) + .unwrap(); + + let result = executor.execute(query_cmd).unwrap(); + match result { + QueryResult::QueryResults { results, .. } => { + assert_eq!(results.len(), 1); + assert_eq!(results[0][0], Value::String("Alice".to_string())); + assert_eq!(results[0][1], Value::Integer(30)); + } + _ => panic!("Expected QueryResults"), + } + } +} diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs new file mode 100644 index 000000000..43f61e7a8 --- /dev/null +++ b/src/query/datalog/matcher.rs @@ -0,0 +1,468 @@ +use super::types::{EdnValue, Pattern}; +use crate::graph::types::{EntityId, Fact, Value}; +use crate::graph::FactStorage; +use std::collections::HashMap; +use uuid::Uuid; + +/// Variable bindings for query execution +/// Maps variable names (e.g., "?name") to their bound values +pub type Bindings = HashMap; + +/// Pattern matcher that finds facts matching a pattern and produces bindings +pub struct PatternMatcher { + storage: FactStorage, +} + +impl PatternMatcher { + pub fn new(storage: FactStorage) -> Self { + PatternMatcher { storage } + } + + /// Match a single pattern against all facts in storage + /// Returns a list of bindings, one for each matching fact + pub fn match_pattern(&self, pattern: &Pattern) -> Vec { + let mut results = Vec::new(); + + // Get all currently asserted facts + let facts = self.storage.get_asserted_facts().unwrap_or_default(); + + for fact in facts { + if let Some(bindings) = self.match_fact_against_pattern(&fact, pattern) { + results.push(bindings); + } + } + + results + } + + /// Try to match a single fact against a pattern + /// Returns Some(bindings) if successful, None otherwise + fn match_fact_against_pattern(&self, fact: &Fact, pattern: &Pattern) -> Option { + let mut bindings = HashMap::new(); + + // Match entity + if !self.match_component(&pattern.entity, &Value::Ref(fact.entity), &mut bindings) { + return None; + } + + // Match attribute + if !self.match_component( + &pattern.attribute, + &Value::Keyword(fact.attribute.clone()), + &mut bindings, + ) { + return None; + } + + // Match value + if !self.match_component(&pattern.value, &fact.value, &mut bindings) { + return None; + } + + Some(bindings) + } + + /// Match a pattern component (entity, attribute, or value) against a fact value + /// Returns true if match succeeds, updating bindings for variables + fn match_component( + &self, + pattern_component: &EdnValue, + fact_value: &Value, + bindings: &mut Bindings, + ) -> bool { + match pattern_component { + // Variable: bind it or check consistency + EdnValue::Symbol(var) if var.starts_with('?') => { + if let Some(existing) = bindings.get(var) { + // Variable already bound, check consistency + existing == fact_value + } else { + // Bind the variable + bindings.insert(var.clone(), fact_value.clone()); + true + } + } + + // Constant: must match exactly + EdnValue::Keyword(k) => { + if let Value::Keyword(fk) = fact_value { + k == fk + } else { + false + } + } + + EdnValue::String(s) => { + if let Value::String(fs) = fact_value { + s == fs + } else { + false + } + } + + EdnValue::Integer(i) => { + if let Value::Integer(fi) = fact_value { + i == fi + } else { + false + } + } + + EdnValue::Float(f) => { + if let Value::Float(ff) = fact_value { + (f - ff).abs() < f64::EPSILON + } else { + false + } + } + + EdnValue::Boolean(b) => { + if let Value::Boolean(fb) = fact_value { + b == fb + } else { + false + } + } + + EdnValue::Uuid(u) => { + if let Value::Ref(entity_id) = fact_value { + u == entity_id + } else { + false + } + } + + EdnValue::Nil => matches!(fact_value, Value::Null), + + // Symbols (non-variables) or other types are not supported in patterns + _ => false, + } + } + + /// Match multiple patterns with variable unification + /// Returns bindings that satisfy all patterns simultaneously + pub fn match_patterns(&self, patterns: &[Pattern]) -> Vec { + if patterns.is_empty() { + return vec![HashMap::new()]; + } + + // Start with the first pattern + let mut results = self.match_pattern(&patterns[0]); + + // Join with each subsequent pattern + for pattern in &patterns[1..] { + results = self.join_with_pattern(results, pattern); + } + + results + } + + /// Join existing bindings with a new pattern + /// Only keeps bindings that are consistent with the new pattern + fn join_with_pattern( + &self, + existing_bindings: Vec, + pattern: &Pattern, + ) -> Vec { + let mut results = Vec::new(); + + for existing in existing_bindings { + // Try to match the pattern with existing bindings + let new_matches = self.match_pattern_with_bindings(pattern, &existing); + results.extend(new_matches); + } + + results + } + + /// Match a pattern given existing variable bindings + /// Returns new bindings that extend the existing ones + fn match_pattern_with_bindings( + &self, + pattern: &Pattern, + existing: &Bindings, + ) -> Vec { + let mut results = Vec::new(); + + let facts = self.storage.get_asserted_facts().unwrap_or_default(); + + for fact in facts { + // Try to match with existing bindings + let mut new_bindings = existing.clone(); + + // Apply existing bindings to pattern before matching + let resolved_pattern = self.apply_bindings_to_pattern(pattern, existing); + + if let Some(additional_bindings) = + self.match_fact_against_pattern(&fact, &resolved_pattern) + { + // Check that additional bindings are consistent with existing + let mut consistent = true; + for (var, val) in &additional_bindings { + if matches!(existing.get(var), Some(existing_val) if existing_val != val) { + consistent = false; + break; + } + } + + if consistent { + // Merge bindings + new_bindings.extend(additional_bindings); + results.push(new_bindings); + } + } + } + + results + } + + /// Apply existing bindings to a pattern, replacing bound variables with their values + fn apply_bindings_to_pattern(&self, pattern: &Pattern, bindings: &Bindings) -> Pattern { + Pattern { + entity: self.apply_binding_to_component(&pattern.entity, bindings), + attribute: self.apply_binding_to_component(&pattern.attribute, bindings), + value: self.apply_binding_to_component(&pattern.value, bindings), + } + } + + /// Apply bindings to a single pattern component + fn apply_binding_to_component( + &self, + component: &EdnValue, + bindings: &Bindings, + ) -> EdnValue { + match component { + EdnValue::Symbol(var) if var.starts_with('?') => { + if let Some(value) = bindings.get(var) { + // Convert Value to EdnValue + self.value_to_edn(value) + } else { + component.clone() + } + } + _ => component.clone(), + } + } + + /// Convert a Value to EdnValue for pattern matching + fn value_to_edn(&self, value: &Value) -> EdnValue { + match value { + Value::String(s) => EdnValue::String(s.clone()), + Value::Integer(i) => EdnValue::Integer(*i), + Value::Float(f) => EdnValue::Float(*f), + Value::Boolean(b) => EdnValue::Boolean(*b), + Value::Ref(entity_id) => EdnValue::Uuid(*entity_id), + Value::Keyword(k) => EdnValue::Keyword(k.clone()), + Value::Null => EdnValue::Nil, + } + } +} + +/// Convert EdnValue to Value for storage +pub fn edn_to_value(edn: &EdnValue) -> Result { + match edn { + EdnValue::String(s) => Ok(Value::String(s.clone())), + EdnValue::Integer(i) => Ok(Value::Integer(*i)), + EdnValue::Float(f) => Ok(Value::Float(*f)), + EdnValue::Boolean(b) => Ok(Value::Boolean(*b)), + EdnValue::Keyword(k) => Ok(Value::Keyword(k.clone())), + EdnValue::Uuid(u) => Ok(Value::Ref(*u)), + EdnValue::Nil => Ok(Value::Null), + EdnValue::Symbol(s) if s.starts_with('?') => { + Err(format!("Cannot convert unbound variable {} to value", s)) + } + _ => Err(format!("Cannot convert {:?} to Value", edn)), + } +} + +/// Convert EdnValue to EntityId (must be a keyword or UUID) +pub fn edn_to_entity_id(edn: &EdnValue) -> Result { + match edn { + EdnValue::Keyword(k) => { + // Convert keyword to deterministic UUID + // For now, we'll use a simple hash-based approach + // In production, you might want a more sophisticated method + let hash = k.as_bytes(); + // Create a UUID from the keyword string + // This is deterministic: same keyword always gives same UUID + if let Ok(uuid) = Uuid::parse_str(k.trim_start_matches(':')) { + Ok(uuid) + } else { + // Generate UUID from keyword name + Ok(Uuid::new_v5(&Uuid::NAMESPACE_OID, hash)) + } + } + EdnValue::Uuid(u) => Ok(*u), + _ => Err(format!("Expected keyword or UUID for entity, got {:?}", edn)), + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_match_simple_pattern() { + let storage = FactStorage::new(); + let alice_id = Uuid::new_v4(); + + // Add some facts + storage + .transact(vec![ + ( + alice_id, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice_id, ":person/age".to_string(), Value::Integer(30)), + ]) + .unwrap(); + + let matcher = PatternMatcher::new(storage); + + // Pattern: [?e :person/name "Alice"] + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + + let results = matcher.match_pattern(&pattern); + assert_eq!(results.len(), 1); + assert_eq!( + results[0].get("?e"), + Some(&Value::Ref(alice_id)) + ); + } + + #[test] + fn test_match_pattern_with_variable_value() { + let storage = FactStorage::new(); + let alice_id = Uuid::new_v4(); + + storage + .transact(vec![( + alice_id, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )]) + .unwrap(); + + let matcher = PatternMatcher::new(storage); + + // Pattern: [?e :person/name ?name] + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::Symbol("?name".to_string()), + ); + + let results = matcher.match_pattern(&pattern); + assert_eq!(results.len(), 1); + assert_eq!( + results[0].get("?name"), + Some(&Value::String("Alice".to_string())) + ); + } + + #[test] + fn test_match_multiple_patterns() { + let storage = FactStorage::new(); + let alice_id = Uuid::new_v4(); + + storage + .transact(vec![ + ( + alice_id, + ":person/name".to_string(), + Value::String("Alice".to_string()), + ), + (alice_id, ":person/age".to_string(), Value::Integer(30)), + ]) + .unwrap(); + + let matcher = PatternMatcher::new(storage); + + // Patterns: [?e :person/name ?name] [?e :person/age ?age] + let patterns = vec![ + Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::Symbol("?name".to_string()), + ), + Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/age".to_string()), + EdnValue::Symbol("?age".to_string()), + ), + ]; + + let results = matcher.match_patterns(&patterns); + assert_eq!(results.len(), 1); + assert_eq!( + results[0].get("?name"), + Some(&Value::String("Alice".to_string())) + ); + assert_eq!(results[0].get("?age"), Some(&Value::Integer(30))); + } + + #[test] + fn test_match_patterns_no_match() { + let storage = FactStorage::new(); + let alice_id = Uuid::new_v4(); + + storage + .transact(vec![( + alice_id, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )]) + .unwrap(); + + let matcher = PatternMatcher::new(storage); + + // Pattern asks for Bob, but we only have Alice + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Bob".to_string()), + ); + + let results = matcher.match_pattern(&pattern); + assert_eq!(results.len(), 0); + } + + #[test] + fn test_edn_to_value() { + assert_eq!( + edn_to_value(&EdnValue::String("test".to_string())).unwrap(), + Value::String("test".to_string()) + ); + assert_eq!( + edn_to_value(&EdnValue::Integer(42)).unwrap(), + Value::Integer(42) + ); + assert_eq!( + edn_to_value(&EdnValue::Boolean(true)).unwrap(), + Value::Boolean(true) + ); + + // Variables should fail + let result = edn_to_value(&EdnValue::Symbol("?x".to_string())); + assert!(result.is_err()); + } + + #[test] + fn test_edn_to_entity_id() { + let uuid = Uuid::new_v4(); + assert_eq!( + edn_to_entity_id(&EdnValue::Uuid(uuid)).unwrap(), + uuid + ); + + // Keywords should generate deterministic UUIDs + let result1 = edn_to_entity_id(&EdnValue::Keyword(":alice".to_string())).unwrap(); + let result2 = edn_to_entity_id(&EdnValue::Keyword(":alice".to_string())).unwrap(); + assert_eq!(result1, result2); // Same keyword = same UUID + } +} diff --git a/src/query/datalog/mod.rs b/src/query/datalog/mod.rs new file mode 100644 index 000000000..8b5cddba6 --- /dev/null +++ b/src/query/datalog/mod.rs @@ -0,0 +1,9 @@ +pub mod executor; +pub mod matcher; +pub mod parser; +pub mod types; + +pub use executor::{DatalogExecutor, QueryResult}; +pub use matcher::{edn_to_entity_id, edn_to_value, Bindings, PatternMatcher}; +pub use parser::{parse_datalog_command, parse_edn}; +pub use types::{DatalogCommand, DatalogQuery, EdnValue, Pattern, Rule, Transaction}; diff --git a/src/query/datalog/parser.rs b/src/query/datalog/parser.rs new file mode 100644 index 000000000..c01667720 --- /dev/null +++ b/src/query/datalog/parser.rs @@ -0,0 +1,619 @@ +use super::types::*; +use uuid::Uuid; + +/// Tokenizer for EDN syntax +#[derive(Debug, Clone, PartialEq)] +enum Token { + LeftParen, + RightParen, + LeftBracket, + RightBracket, + Keyword(String), + Symbol(String), + String(String), + Integer(i64), + Float(f64), + Boolean(bool), + TaggedLiteral(String), // e.g., "#uuid" + Nil, +} + +/// Tokenize EDN input +fn tokenize(input: &str) -> Result, String> { + let mut tokens = Vec::new(); + let mut chars = input.chars().peekable(); + + while let Some(&ch) = chars.peek() { + match ch { + // Whitespace + ' ' | '\t' | '\n' | '\r' | ',' => { + chars.next(); + } + // Parens and brackets + '(' => { + tokens.push(Token::LeftParen); + chars.next(); + } + ')' => { + tokens.push(Token::RightParen); + chars.next(); + } + '[' => { + tokens.push(Token::LeftBracket); + chars.next(); + } + ']' => { + tokens.push(Token::RightBracket); + chars.next(); + } + // String literals + '"' => { + chars.next(); // consume opening quote + let mut string = String::new(); + while let Some(&ch) = chars.peek() { + if ch == '"' { + chars.next(); // consume closing quote + break; + } else if ch == '\\' { + chars.next(); + // Handle escape sequences + if let Some(&escaped) = chars.peek() { + chars.next(); + match escaped { + 'n' => string.push('\n'), + 't' => string.push('\t'), + 'r' => string.push('\r'), + '"' => string.push('"'), + '\\' => string.push('\\'), + _ => string.push(escaped), + } + } + } else { + string.push(ch); + chars.next(); + } + } + tokens.push(Token::String(string)); + } + // Keywords (start with :) + ':' => { + chars.next(); + let mut keyword = String::from(":"); + while let Some(&ch) = chars.peek() { + if ch.is_alphanumeric() || ch == '/' || ch == '-' || ch == '_' { + keyword.push(ch); + chars.next(); + } else { + break; + } + } + tokens.push(Token::Keyword(keyword)); + } + // Tagged literals (start with #) + '#' => { + chars.next(); + let mut tag = String::new(); + while let Some(&ch) = chars.peek() { + if ch.is_alphanumeric() || ch == '-' { + tag.push(ch); + chars.next(); + } else { + break; + } + } + tokens.push(Token::TaggedLiteral(tag)); + } + // Numbers or symbols starting with - + '-' => { + let start_pos = chars.clone(); + chars.next(); + if let Some(&next_ch) = chars.peek() { + if next_ch.is_numeric() { + // It's a negative number + let mut num_str = String::from("-"); + let (is_float, num) = parse_number(&mut chars, &mut num_str)?; + if is_float { + tokens.push(Token::Float(num.parse().unwrap())); + } else { + tokens.push(Token::Integer(num.parse().unwrap())); + } + } else { + // It's a symbol starting with - + chars = start_pos; + chars.next(); + let symbol = parse_symbol(&mut chars, '-'); + tokens.push(Token::Symbol(symbol)); + } + } else { + // Just a - symbol + tokens.push(Token::Symbol("-".to_string())); + } + } + // Numbers + '0'..='9' => { + let mut num_str = String::new(); + let (is_float, num) = parse_number(&mut chars, &mut num_str)?; + if is_float { + tokens.push(Token::Float(num.parse().unwrap())); + } else { + tokens.push(Token::Integer(num.parse().unwrap())); + } + } + // Symbols (including variables starting with ?) + _ if ch.is_alphabetic() || ch == '?' || ch == '_' => { + let mut symbol = String::new(); + while let Some(&ch) = chars.peek() { + if ch.is_alphanumeric() || ch == '?' || ch == '_' || ch == '-' || ch == '/' { + symbol.push(ch); + chars.next(); + } else { + break; + } + } + + // Check for special symbols + match symbol.as_str() { + "true" => tokens.push(Token::Boolean(true)), + "false" => tokens.push(Token::Boolean(false)), + "nil" => tokens.push(Token::Nil), + _ => tokens.push(Token::Symbol(symbol)), + } + } + _ => { + return Err(format!("Unexpected character: {}", ch)); + } + } + } + + Ok(tokens) +} + +fn parse_number( + chars: &mut std::iter::Peekable, + num_str: &mut String, +) -> Result<(bool, String), String> { + let mut is_float = false; + + while let Some(&ch) = chars.peek() { + if ch.is_numeric() { + num_str.push(ch); + chars.next(); + } else if ch == '.' && !is_float { + is_float = true; + num_str.push(ch); + chars.next(); + } else { + break; + } + } + + Ok((is_float, num_str.clone())) +} + +fn parse_symbol(chars: &mut std::iter::Peekable, first: char) -> String { + let mut symbol = String::from(first); + while let Some(&ch) = chars.peek() { + if ch.is_alphanumeric() || ch == '?' || ch == '_' || ch == '-' || ch == '/' { + symbol.push(ch); + chars.next(); + } else { + break; + } + } + symbol +} + +/// Parser for EDN values +struct Parser { + tokens: Vec, + pos: usize, +} + +impl Parser { + fn new(tokens: Vec) -> Self { + Parser { tokens, pos: 0 } + } + + fn peek(&self) -> Option<&Token> { + self.tokens.get(self.pos) + } + + fn advance(&mut self) -> Option { + if self.pos < self.tokens.len() { + let token = self.tokens[self.pos].clone(); + self.pos += 1; + Some(token) + } else { + None + } + } + + fn parse_value(&mut self) -> Result { + match self.peek() { + Some(Token::LeftParen) => self.parse_list(), + Some(Token::LeftBracket) => self.parse_vector(), + Some(Token::Keyword(_)) => { + if let Some(Token::Keyword(k)) = self.advance() { + Ok(EdnValue::Keyword(k)) + } else { + unreachable!() + } + } + Some(Token::Symbol(_)) => { + if let Some(Token::Symbol(s)) = self.advance() { + Ok(EdnValue::Symbol(s)) + } else { + unreachable!() + } + } + Some(Token::String(_)) => { + if let Some(Token::String(s)) = self.advance() { + Ok(EdnValue::String(s)) + } else { + unreachable!() + } + } + Some(Token::Integer(_)) => { + if let Some(Token::Integer(i)) = self.advance() { + Ok(EdnValue::Integer(i)) + } else { + unreachable!() + } + } + Some(Token::Float(_)) => { + if let Some(Token::Float(f)) = self.advance() { + Ok(EdnValue::Float(f)) + } else { + unreachable!() + } + } + Some(Token::Boolean(_)) => { + if let Some(Token::Boolean(b)) = self.advance() { + Ok(EdnValue::Boolean(b)) + } else { + unreachable!() + } + } + Some(Token::TaggedLiteral(_)) => { + if let Some(Token::TaggedLiteral(tag)) = self.advance() { + if tag == "uuid" { + // Next token should be a string containing the UUID + if let Some(Token::String(uuid_str)) = self.advance() { + match Uuid::parse_str(&uuid_str) { + Ok(uuid) => Ok(EdnValue::Uuid(uuid)), + Err(_) => Err(format!("Invalid UUID: {}", uuid_str)), + } + } else { + Err("Expected UUID string after #uuid tag".to_string()) + } + } else { + Err(format!("Unknown tagged literal: #{}", tag)) + } + } else { + unreachable!() + } + } + Some(Token::Nil) => { + self.advance(); + Ok(EdnValue::Nil) + } + Some(token) => Err(format!("Unexpected token: {:?}", token)), + None => Err("Unexpected end of input".to_string()), + } + } + + fn parse_vector(&mut self) -> Result { + self.advance(); // consume [ + let mut elements = Vec::new(); + + while let Some(token) = self.peek() { + if token == &Token::RightBracket { + self.advance(); // consume ] + return Ok(EdnValue::Vector(elements)); + } + elements.push(self.parse_value()?); + } + + Err("Unclosed vector".to_string()) + } + + fn parse_list(&mut self) -> Result { + self.advance(); // consume ( + let mut elements = Vec::new(); + + while let Some(token) = self.peek() { + if token == &Token::RightParen { + self.advance(); // consume ) + return Ok(EdnValue::List(elements)); + } + elements.push(self.parse_value()?); + } + + Err("Unclosed list".to_string()) + } +} + +/// Parse EDN input into EdnValue +pub fn parse_edn(input: &str) -> Result { + let tokens = tokenize(input)?; + let mut parser = Parser::new(tokens); + parser.parse_value() +} + +/// Parse a Datalog command from EDN +pub fn parse_datalog_command(input: &str) -> Result { + let edn = parse_edn(input)?; + + match edn { + EdnValue::List(elements) if !elements.is_empty() => { + // Command is a symbol (e.g., "query", "transact") + let command = match &elements[0] { + EdnValue::Symbol(s) => s.as_str(), + EdnValue::Keyword(k) => k.as_str(), + _ => return Err("Expected command symbol".to_string()), + }; + + match command { + "query" => parse_query(&elements[1..]), + "transact" => parse_transact(&elements[1..]), + "retract" => parse_retract(&elements[1..]), + "rule" => parse_rule(&elements[1..]), + _ => Err(format!("Unknown command: {}", command)), + } + } + _ => Err("Expected a list starting with a command symbol".to_string()), + } +} + +fn parse_query(elements: &[EdnValue]) -> Result { + // Parse (query [:find ?x ?y :where [patterns...]]) + if elements.is_empty() { + return Err("Query requires a map argument".to_string()); + } + + let query_vector = elements[0] + .as_vector() + .ok_or("Query argument must be a vector")?; + + let mut find_vars = Vec::new(); + let mut patterns = Vec::new(); + let mut current_clause = None; + + let mut i = 0; + while i < query_vector.len() { + if let Some(keyword) = query_vector[i].as_keyword() { + current_clause = Some(keyword); + i += 1; + continue; + } + + match current_clause { + Some(":find") => { + // Collect find variables + if let Some(var) = query_vector[i].as_variable() { + find_vars.push(var.to_string()); + } else { + return Err(format!( + "Expected variable in :find clause, got {:?}", + query_vector[i] + )); + } + } + Some(":where") => { + // Parse patterns + if let Some(pattern_vec) = query_vector[i].as_vector() { + patterns.push(Pattern::from_edn(pattern_vec)?); + } else { + return Err(format!( + "Expected pattern vector in :where clause, got {:?}", + query_vector[i] + )); + } + } + _ => { + return Err(format!("Unexpected element in query: {:?}", query_vector[i])); + } + } + + i += 1; + } + + Ok(DatalogCommand::Query(DatalogQuery::new( + find_vars, patterns, + ))) +} + +fn parse_transact(elements: &[EdnValue]) -> Result { + // Parse (transact [[e a v] [e a v] ...]) + if elements.is_empty() { + return Err("Transact requires a vector of facts".to_string()); + } + + let facts_vector = elements[0] + .as_vector() + .ok_or("Transact argument must be a vector")?; + + let mut patterns = Vec::new(); + for fact in facts_vector { + let fact_vec = fact + .as_vector() + .ok_or("Each fact must be a vector [e a v]")?; + patterns.push(Pattern::from_edn(fact_vec)?); + } + + Ok(DatalogCommand::Transact(Transaction::new(patterns))) +} + +fn parse_retract(elements: &[EdnValue]) -> Result { + // Same structure as transact + if elements.is_empty() { + return Err("Retract requires a vector of facts".to_string()); + } + + let facts_vector = elements[0] + .as_vector() + .ok_or("Retract argument must be a vector")?; + + let mut patterns = Vec::new(); + for fact in facts_vector { + let fact_vec = fact + .as_vector() + .ok_or("Each fact must be a vector [e a v]")?; + patterns.push(Pattern::from_edn(fact_vec)?); + } + + Ok(DatalogCommand::Retract(Transaction::new(patterns))) +} + +fn parse_rule(_elements: &[EdnValue]) -> Result { + // TODO: Implement rule parsing in later phase + Err("Rule parsing not yet implemented".to_string()) +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_tokenize_basic() { + let input = "(query [:find ?x])"; + let tokens = tokenize(input).unwrap(); + assert_eq!(tokens[0], Token::LeftParen); + assert_eq!(tokens[1], Token::Symbol("query".to_string())); + assert_eq!(tokens[2], Token::LeftBracket); + assert_eq!(tokens[3], Token::Keyword(":find".to_string())); + assert_eq!(tokens[4], Token::Symbol("?x".to_string())); + assert_eq!(tokens[5], Token::RightBracket); + assert_eq!(tokens[6], Token::RightParen); + } + + #[test] + fn test_tokenize_numbers() { + let tokens = tokenize("42 3.14 -5 -2.5").unwrap(); + assert_eq!(tokens[0], Token::Integer(42)); + assert_eq!(tokens[1], Token::Float(3.14)); + assert_eq!(tokens[2], Token::Integer(-5)); + assert_eq!(tokens[3], Token::Float(-2.5)); + } + + #[test] + fn test_tokenize_strings() { + let tokens = tokenize(r#""hello" "world\"test""#).unwrap(); + assert_eq!(tokens[0], Token::String("hello".to_string())); + assert_eq!(tokens[1], Token::String("world\"test".to_string())); + } + + #[test] + fn test_tokenize_booleans() { + let tokens = tokenize("true false nil").unwrap(); + assert_eq!(tokens[0], Token::Boolean(true)); + assert_eq!(tokens[1], Token::Boolean(false)); + assert_eq!(tokens[2], Token::Nil); + } + + #[test] + fn test_parse_edn_vector() { + let result = parse_edn("[1 2 3]").unwrap(); + match result { + EdnValue::Vector(v) => { + assert_eq!(v.len(), 3); + assert_eq!(v[0], EdnValue::Integer(1)); + } + _ => panic!("Expected vector"), + } + } + + #[test] + fn test_parse_edn_list() { + let result = parse_edn("(query :find ?x)").unwrap(); + match result { + EdnValue::List(l) => { + assert_eq!(l.len(), 3); + assert_eq!(l[0], EdnValue::Symbol("query".to_string())); + assert_eq!(l[1], EdnValue::Keyword(":find".to_string())); + } + _ => panic!("Expected list"), + } + } + + #[test] + fn test_parse_simple_query() { + let input = r#"(query [:find ?name :where [?e :person/name ?name]])"#; + let cmd = parse_datalog_command(input).unwrap(); + + match cmd { + DatalogCommand::Query(q) => { + assert_eq!(q.find, vec!["?name"]); + assert_eq!(q.patterns.len(), 1); + assert_eq!( + q.patterns[0].attribute, + EdnValue::Keyword(":person/name".to_string()) + ); + } + _ => panic!("Expected Query command"), + } + } + + #[test] + fn test_parse_transact() { + let input = r#"(transact [[:alice :person/name "Alice"] [:alice :person/age 30]])"#; + let cmd = parse_datalog_command(input).unwrap(); + + match cmd { + DatalogCommand::Transact(tx) => { + assert_eq!(tx.facts.len(), 2); + assert_eq!( + tx.facts[0].entity, + EdnValue::Keyword(":alice".to_string()) + ); + assert_eq!( + tx.facts[0].value, + EdnValue::String("Alice".to_string()) + ); + assert_eq!(tx.facts[1].value, EdnValue::Integer(30)); + } + _ => panic!("Expected Transact command"), + } + } + + #[test] + fn test_parse_uuid() { + let uuid_str = "550e8400-e29b-41d4-a716-446655440000"; + let input = format!(r#"#uuid "{}""#, uuid_str); + let result = parse_edn(&input).unwrap(); + + match result { + EdnValue::Uuid(uuid) => { + assert_eq!(uuid.to_string(), uuid_str); + } + _ => panic!("Expected UUID"), + } + } + + #[test] + fn test_parse_complex_query() { + let input = r#"(query [:find ?name ?age :where [?e :person/name ?name] [?e :person/age ?age]])"#; + let cmd = parse_datalog_command(input).unwrap(); + + match cmd { + DatalogCommand::Query(q) => { + assert_eq!(q.find, vec!["?name", "?age"]); + assert_eq!(q.patterns.len(), 2); + } + _ => panic!("Expected Query command"), + } + } + + #[test] + fn test_parse_retract() { + let input = r#"(retract [[:alice :person/age 30]])"#; + let cmd = parse_datalog_command(input).unwrap(); + + match cmd { + DatalogCommand::Retract(tx) => { + assert_eq!(tx.facts.len(), 1); + } + _ => panic!("Expected Retract command"), + } + } +} diff --git a/src/query/datalog/types.rs b/src/query/datalog/types.rs new file mode 100644 index 000000000..b06d18f19 --- /dev/null +++ b/src/query/datalog/types.rs @@ -0,0 +1,308 @@ +use uuid::Uuid; + +/// EDN (Extensible Data Notation) value types +/// This represents the core data types in EDN/Datalog syntax +#[derive(Debug, Clone, PartialEq)] +pub enum EdnValue { + /// Keyword: :person/name, :find, :where + Keyword(String), + /// Symbol: ?name, ?e (logic variables) + Symbol(String), + /// String literal: "Alice" + String(String), + /// Integer: 42 + Integer(i64), + /// Float: 3.14 + Float(f64), + /// Boolean: true, false + Boolean(bool), + /// UUID: #uuid "550e8400-e29b-41d4-a716-446655440000" + Uuid(Uuid), + /// Vector: [...] + Vector(Vec), + /// List: (...) + List(Vec), + /// Null/nil + Nil, +} + +impl EdnValue { + /// Check if this is a logic variable (symbol starting with ?) + pub fn is_variable(&self) -> bool { + matches!(self, EdnValue::Symbol(s) if s.starts_with('?')) + } + + /// Get the variable name if this is a variable + pub fn as_variable(&self) -> Option<&str> { + match self { + EdnValue::Symbol(s) if s.starts_with('?') => Some(s), + _ => None, + } + } + + /// Check if this is a keyword + pub fn is_keyword(&self) -> bool { + matches!(self, EdnValue::Keyword(_)) + } + + /// Get the keyword value if this is a keyword + pub fn as_keyword(&self) -> Option<&str> { + match self { + EdnValue::Keyword(k) => Some(k), + _ => None, + } + } + + /// Check if this is a vector + pub fn is_vector(&self) -> bool { + matches!(self, EdnValue::Vector(_)) + } + + /// Get the vector contents if this is a vector + pub fn as_vector(&self) -> Option<&Vec> { + match self { + EdnValue::Vector(v) => Some(v), + _ => None, + } + } + + /// Check if this is a list + pub fn is_list(&self) -> bool { + matches!(self, EdnValue::List(_)) + } + + /// Get the list contents if this is a list + pub fn as_list(&self) -> Option<&Vec> { + match self { + EdnValue::List(l) => Some(l), + _ => None, + } + } +} + +/// A Datalog pattern: [Entity Attribute Value] +/// Variables start with ?, constants are literal values +/// +/// Examples: +/// - [?e :person/name "Alice"] - Find entity with name "Alice" +/// - [?e :person/name ?name] - Find all entity-name pairs +/// - [:alice :friend ?friend] - Find all friends of Alice +#[derive(Debug, Clone, PartialEq)] +pub struct Pattern { + pub entity: EdnValue, + pub attribute: EdnValue, + pub value: EdnValue, +} + +impl Pattern { + pub fn new(entity: EdnValue, attribute: EdnValue, value: EdnValue) -> Self { + Pattern { + entity, + attribute, + value, + } + } + + /// Parse a pattern from an EDN vector + pub fn from_edn(vector: &[EdnValue]) -> Result { + if vector.len() != 3 { + return Err(format!( + "Pattern must have exactly 3 elements (E A V), got {}", + vector.len() + )); + } + + Ok(Pattern { + entity: vector[0].clone(), + attribute: vector[1].clone(), + value: vector[2].clone(), + }) + } +} + +/// A Datalog query with :find and :where clauses +/// +/// Example: +/// ```datalog +/// (query [:find ?name ?age +/// :where [?e :person/name ?name] +/// [?e :person/age ?age]]) +/// ``` +#[derive(Debug, Clone, PartialEq)] +pub struct DatalogQuery { + /// Variables to return (from :find clause) + pub find: Vec, + /// Patterns to match (from :where clause) + pub patterns: Vec, +} + +impl DatalogQuery { + pub fn new(find: Vec, patterns: Vec) -> Self { + DatalogQuery { find, patterns } + } +} + +/// A Datalog rule definition +/// +/// Example: +/// ```datalog +/// (rule [(reachable ?from ?to) +/// [?from :connected ?to]]) +/// +/// (rule [(reachable ?from ?to) +/// [?from :connected ?intermediate] +/// (reachable ?intermediate ?to)]) +/// ``` +#[derive(Debug, Clone, PartialEq)] +pub struct Rule { + /// The rule head: (predicate ?var1 ?var2) + pub head: Vec, + /// The rule body: list of patterns and rule invocations + pub body: Vec, +} + +impl Rule { + pub fn new(head: Vec, body: Vec) -> Self { + Rule { head, body } + } +} + +/// A transaction: list of facts to assert or retract +/// +/// Example: +/// ```datalog +/// (transact [[:alice :person/name "Alice"] +/// [:alice :person/age 30] +/// [:alice :friend :bob]]) +/// ``` +#[derive(Debug, Clone, PartialEq)] +pub struct Transaction { + /// List of fact triples to assert + pub facts: Vec, +} + +impl Transaction { + pub fn new(facts: Vec) -> Self { + Transaction { facts } + } +} + +/// A Datalog command (top-level form) +#[derive(Debug, Clone, PartialEq)] +pub enum DatalogCommand { + /// Execute a query + Query(DatalogQuery), + /// Define a rule + Rule(Rule), + /// Transact facts + Transact(Transaction), + /// Retract facts + Retract(Transaction), +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_edn_value_variable() { + let var = EdnValue::Symbol("?name".to_string()); + assert!(var.is_variable()); + assert_eq!(var.as_variable(), Some("?name")); + + let not_var = EdnValue::Symbol("name".to_string()); + assert!(!not_var.is_variable()); + assert_eq!(not_var.as_variable(), None); + } + + #[test] + fn test_edn_value_keyword() { + let keyword = EdnValue::Keyword(":person/name".to_string()); + assert!(keyword.is_keyword()); + assert_eq!(keyword.as_keyword(), Some(":person/name")); + + let not_keyword = EdnValue::String(":not-a-keyword".to_string()); + assert!(!not_keyword.is_keyword()); + } + + #[test] + fn test_pattern_creation() { + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + + assert!(pattern.entity.is_variable()); + assert!(pattern.attribute.is_keyword()); + } + + #[test] + fn test_pattern_from_edn() { + let vector = vec![ + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ]; + + let pattern = Pattern::from_edn(&vector).unwrap(); + assert_eq!(pattern.entity, EdnValue::Symbol("?e".to_string())); + assert_eq!( + pattern.attribute, + EdnValue::Keyword(":person/name".to_string()) + ); + assert_eq!(pattern.value, EdnValue::String("Alice".to_string())); + } + + #[test] + fn test_pattern_from_edn_invalid_length() { + let vector = vec![ + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + ]; + + let result = Pattern::from_edn(&vector); + assert!(result.is_err()); + assert!(result.unwrap_err().contains("must have exactly 3 elements")); + } + + #[test] + fn test_datalog_query_creation() { + let query = DatalogQuery::new( + vec!["?name".to_string(), "?age".to_string()], + vec![ + Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::Symbol("?name".to_string()), + ), + Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/age".to_string()), + EdnValue::Symbol("?age".to_string()), + ), + ], + ); + + assert_eq!(query.find.len(), 2); + assert_eq!(query.patterns.len(), 2); + } + + #[test] + fn test_transaction_creation() { + let tx = Transaction::new(vec![ + Pattern::new( + EdnValue::Keyword(":alice".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ), + Pattern::new( + EdnValue::Keyword(":alice".to_string()), + EdnValue::Keyword(":person/age".to_string()), + EdnValue::Integer(30), + ), + ]); + + assert_eq!(tx.facts.len(), 2); + } +} diff --git a/src/query/mod.rs b/src/query/mod.rs index 9e0b8263e..351d4f4a4 100644 --- a/src/query/mod.rs +++ b/src/query/mod.rs @@ -1,5 +1,7 @@ pub mod parser; pub mod executor; +pub mod datalog; pub use parser::{parse_query, Query}; pub use executor::QueryExecutor; +pub use datalog::{parse_datalog_command, parse_edn, DatalogCommand, DatalogQuery, EdnValue, Pattern, Transaction}; diff --git a/src/repl.rs b/src/repl.rs index 28cc6f46b..5db26e12c 100644 --- a/src/repl.rs +++ b/src/repl.rs @@ -1,22 +1,30 @@ use crate::graph::storage::GraphStorage; +use crate::graph::FactStorage; +use crate::query::datalog::{parse_datalog_command, DatalogExecutor}; use crate::query::executor::{QueryExecutor, QueryResult}; use crate::query::parser::parse_query; use std::io::{self, Write}; pub struct Repl { - storage: GraphStorage, + graph_storage: GraphStorage, + fact_storage: FactStorage, } impl Repl { - pub fn new(storage: GraphStorage) -> Self { - Repl { storage } + pub fn new(graph_storage: GraphStorage) -> Self { + Repl { + graph_storage, + fact_storage: FactStorage::new(), + } } pub fn run(&self) { - println!("Minigraf v0.1.0 - Interactive Graph Query Console"); - println!("Type HELP for available commands, EXIT to quit.\n"); + println!("Minigraf v0.1.0 - Interactive Datalog Console"); + println!("Datalog commands: (transact [...]), (query [...]), (retract [...])"); + println!("Type EXIT to quit.\n"); - let executor = QueryExecutor::new(&self.storage); + let gql_executor = QueryExecutor::new(&self.graph_storage); + let datalog_executor = DatalogExecutor::new(self.fact_storage.clone()); loop { print!("minigraf> "); @@ -36,9 +44,30 @@ impl Repl { continue; } - match parse_query(input) { - Ok(query) => { - match executor.execute(query) { + // Check for EXIT command + if input.to_uppercase() == "EXIT" { + break; + } + + // Try Datalog syntax first (starts with parenthesis) + if input.starts_with('(') { + match parse_datalog_command(input) { + Ok(command) => match datalog_executor.execute(command) { + Ok(result) => { + self.print_datalog_result(result); + } + Err(e) => { + eprintln!("Execution error: {}", e); + } + }, + Err(e) => { + eprintln!("Parse error: {}", e); + } + } + } else { + // Fall back to GQL syntax (backward compatibility) + match parse_query(input) { + Ok(query) => match gql_executor.execute(query) { Ok(result) => { let formatted = result.format(); println!("{}", formatted); @@ -50,11 +79,11 @@ impl Repl { Err(e) => { eprintln!("Execution error: {}", e); } + }, + Err(e) => { + eprintln!("Parse error: {}", e); } } - Err(e) => { - eprintln!("Parse error: {}", e); - } } println!(); @@ -66,4 +95,54 @@ impl Repl { } } } + + fn print_datalog_result(&self, result: crate::query::datalog::QueryResult) { + use crate::query::datalog::QueryResult as DResult; + + match result { + DResult::Transacted(tx_id) => { + println!("✓ Transacted successfully (tx: {})", tx_id); + } + DResult::Retracted(tx_id) => { + println!("✓ Retracted successfully (tx: {})", tx_id); + } + DResult::QueryResults { vars, results } => { + if results.is_empty() { + println!("No results found."); + } else { + // Print header + println!("{}", vars.join("\t")); + println!("{}", "-".repeat(vars.len() * 20)); + + // Print rows + for row in &results { + let formatted_row: Vec = row + .iter() + .map(|v| self.format_value(v)) + .collect(); + println!("{}", formatted_row.join("\t")); + } + + println!("\n{} result(s) found.", results.len()); + } + } + DResult::Ok => { + println!("✓ OK"); + } + } + } + + fn format_value(&self, value: &crate::graph::types::Value) -> String { + use crate::graph::types::Value; + + match value { + Value::String(s) => format!("\"{}\"", s), + Value::Integer(i) => i.to_string(), + Value::Float(f) => f.to_string(), + Value::Boolean(b) => b.to_string(), + Value::Ref(uuid) => format!("#uuid {}", uuid), + Value::Keyword(k) => k.clone(), + Value::Null => "nil".to_string(), + } + } }