1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
//! SQLite-backed graph database implementation.
//!
//! This module provides the core graph database implementation with SQLite storage,
//! entity and edge management, pattern matching, and MVCC-lite snapshot isolation.
//!
//! # Module Architecture
//!
//! The graph module is organized into focused submodules:
//!
//! - **core**: [`SqliteGraph`] - Main graph database implementation
//! - **types**: [`GraphEntity`], [`GraphEdge`] - Core graph data structures
//! - **adjacency**: Adjacency list management with caching
//! - **entity_ops**: Node/entity CRUD operations
//! - **edge_ops**: Edge/relationship CRUD operations
//! - **pattern_matching**: Triple pattern matching engine
//! - **snapshot**: MVCC-lite snapshot system for read isolation
//! - **metrics**: Performance monitoring and instrumentation
//!
//! # Core Types
//!
//! - [`SqliteGraph`] - Main graph database struct with dual backend support
//! - [`GraphEntity`] - Graph node/vertex representation with labels and properties
//! - [`GraphEdge`] - Graph edge/relationship representation with metadata
//!
//! # Invariants and Guarantees
//
//! ## Thread Safety
//!
//! **NOT thread-safe for concurrent writes.** `SqliteGraph` uses interior mutability
//! (`RefCell`) and is not `Sync`. Do not share across threads for write operations.
//!
//! For concurrent read access, use [`GraphSnapshot`] from the `mvcc` module:
//!
//! ```rust,ignore
//! use sqlitegraph::{GraphSnapshot, SqliteGraph};
//!
//! let graph = SqliteGraph::open("my_graph.db")?;
//!
//! // Create snapshots for concurrent reads
//! let snapshot1 = graph.snapshot()?;
//! let snapshot2 = graph.snapshot()?;
//!
//! // Both snapshots can be used concurrently (thread-safe)
//! std::thread::spawn(move || {
//! let neighbors = snapshot1.neighbors(node_id)?;
//! });
//! ```
//!
//! ## Transaction Isolation
//!
//! This graph provides **MVCC-lite** snapshot isolation:
//!
//! - **Readers** see consistent snapshot at creation time
//! - **Writers** are serialized (one write transaction at a time)
//! - **No phantom reads** - snapshots are immutable after creation
//! - **Write skew** possible - snapshots don't prevent concurrent write conflicts
//!
//! MVCC-lite guarantees:
//! - Readers never block writers
//! - Writers never block readers
//! - Each snapshot sees a consistent view
//! - No dirty reads within a snapshot
//!
//! ## Edge Case Behavior
//!
//! ### Empty Graph
//! - Queries on empty graph return empty results (not errors)
//! - `all_entity_ids()` returns empty `Vec`
//! - Pattern matching returns empty iterator
//!
//! ### Deleted Nodes
//! - Deleted nodes are removed from all adjacency lists
//! - Edges to/from deleted nodes are automatically removed
//! - Subsequent queries return `SqliteGraphError::EntityNotFound`
//!
//! ### Self-Loops
//! - Self-loops (edges where source == target) are supported
//! - Stored in both incoming and outgoing adjacency lists
//! - Returned by both `fetch_outgoing` and `fetch_incoming`
//!
//! # Performance Characteristics
//!
//! ## Insert Operations
//! - **Node insert**: O(1) amortized (single SQLite INSERT)
//! - **Edge insert**: O(1) amortized (two SQLite INSERTs + cache update)
//! - **Bulk insert**: O(N) for batch operations (transaction overhead amortized)
//!
//! ## Query Operations
//! - **Neighbor lookup**: O(degree) for cached adjacency, O(log V) for database query
//! - **Pattern match**: O(matched triples) with cache acceleration
//! - **BFS traversal**: O(V + E) worst case, typically O(branching_factor × depth)
//! - **Shortest path**: O(V + E) for unweighted BFS-based algorithm
//!
//! ## Memory Usage
//! - **Base graph**: O(V + E) for adjacency lists
//! - **Cache overhead**: O(cached_nodes × avg_degree) for LRU cache
//! - **Snapshot**: O(1) per snapshot (shares graph data, isolated transaction)
//!
//! # Usage Examples
//!
//! ## Basic Graph Operations
//!
//! ```rust,ignore
//! use sqlitegraph::{SqliteGraph, GraphEntityCreate};
//!
//! let graph = SqliteGraph::open_in_memory()?;
//!
//! // Insert nodes
//! let node1 = graph.insert_node(GraphEntityCreate {
//! labels: vec!["Person".into()],
//! properties: vec![],
//! })?;
//!
//! let node2 = graph.insert_node(GraphEntityCreate {
//! labels: vec!["Person".into()],
//! properties: vec![],
//! })?;
//!
//! // Insert edge
//! graph.insert_edge(node1, "KNOWS".into(), node2, vec![])?;
//!
//! // Query neighbors
//! let neighbors = graph.fetch_outgoing(node1)?;
//! assert_eq!(neighbors, vec![node2]);
//! ```
//!
//! ## Pattern Matching
//!
//! ```rust,ignore
//! use sqlitegraph::{PatternTriple, match_triples};
//!
//! let pattern = PatternTriple {
//! subject: Some(node1),
//! predicate: Some("KNOWS".into()),
//! object: None, // Wildcard
//! };
//!
//! let matches = match_triples(&graph, pattern)?;
//! for triple in matches {
//! println!("{:?} KNOWS {:?}", triple.subject, triple.object);
//! }
//! ```
//!
//! # Backend Selection
//!
//! This module provides the SQLite backend implementation. For the native backend
//! (optimized for performance without SQLite dependencies), see `backend::NativeGraphBackend`.
//!
//! Both backends implement the `GraphBackend` trait, providing a unified API for
//! graph operations regardless of storage engine.
pub use ;
pub use ;
pub use ;
pub use ;