fob-graph
Pure graph data structures for module dependency graphs.
This crate provides the core graph primitives and ModuleGraph implementation without any I/O or analysis logic. It's designed to be lightweight and WASM-compatible.
Features
- Pure Data Structures: No I/O, no file system dependencies
- WASM-Compatible: Can run in browser environments
- Thread-Safe: Uses
Arcfor efficient shared ownership - Memory Efficient: Arena-based allocation where possible
- Type-Safe: Strong typing for modules, imports, exports, and dependencies
- Extensible: Extension trait pattern for adding custom functionality
Architecture
┌─────────────────────────────────────────────────────────────┐
│ ModuleGraph │
│ (Arc-based, thread-safe, WASM-compatible) │
└────────────────────┬────────────────────────────────────────┘
│
┌────────────┼────────────┐
│ │ │
▼ ▼ ▼
┌───────────┐ ┌───────────┐ ┌───────────┐
│ Module │ │ Import │ │ Export │
│ (Node) │ │ (Edge) │ │ (Edge) │
└───────────┘ └───────────┘ └───────────┘
│ │ │
└────────────┼────────────┘
│
▼
┌──────────────────────┐
│ SymbolTable │
│ (Intra-file │
│ analysis) │
└──────────────────────┘
Installation
Add to your Cargo.toml:
[]
= { = "../fob-graph" }
Quick Start
Building a Module Graph
use ;
use PathBuf;
// Create a new graph
let graph = new?;
// Add a module
let module_id = new?;
let module = builder
.entry
.build;
graph.add_module?;
// Add dependencies
let utils_id = new?;
graph.add_dependency?;
// Query the graph
let dependencies = graph.dependencies?;
println!;
Symbol Analysis
use analyze_symbols;
use ;
let source = r#"
const used = 42;
const unused = 100;
console.log(used);
"#;
let table: SymbolTable = analyze_symbols?;
// Find unused symbols
let unused = table.unused_symbols;
println!;
Finding Circular Dependencies
use ModuleGraph;
let graph: ModuleGraph = /* ... */;
// Find all circular dependency chains
let circular = graph.dependency_chains_to?;
for chain in circular
Core Types
ModuleGraph
The main graph structure. Provides methods for:
- Adding/removing modules
- Querying dependencies and dependents
- Finding circular dependencies
- Computing statistics
- Symbol-level analysis
Module
Represents a single module in the graph:
- ModuleId: Unique identifier (path-based or virtual)
- Imports: List of imports from this module
- Exports: List of exports from this module
- SymbolTable: Intra-file symbol analysis results
SymbolTable
Tracks symbols within a single module:
- Variable declarations
- Function declarations
- Class declarations
- Usage counts (reads/writes)
- Scope information
Extension Trait Pattern
The crate uses extension traits to add functionality without modifying core types:
use ModuleGraph;
// Extension traits are automatically available
let unused_exports = graph.unused_exports?;
let statistics = graph.statistics?;
let circular = graph.find_circular_dependencies?;
Thread Safety
ModuleGraph uses Arc internally for efficient shared ownership. Multiple threads can safely:
- Read from the graph concurrently
- Query dependencies/dependents
- Compute statistics
For modifications, use appropriate synchronization (e.g., Mutex or RwLock).
Performance Characteristics
- Graph Construction: O(n) where n is the number of modules
- Dependency Queries: O(1) average case
- Transitive Dependencies: O(n) worst case
- Circular Detection: O(n + e) where e is the number of edges
WASM Compatibility
The crate is designed to work in WASM environments:
- No file system dependencies
- No network dependencies
- Pure Rust data structures
- Compatible with
wasm-bindgenandwasm-pack
Examples
See the examples/ directory for more detailed usage:
basic_graph.rs- Simple graph constructionsymbol_analysis.rs- Symbol table usagedependency_analysis.rs- Finding dependenciesconcurrent_access.rs- Thread-safe operations
Module Organization
- Core Types:
module.rs,import.rs,export.rs,module_id.rs - Graph Implementation:
memory/directory - Semantic Analysis:
semantic/directory (symbol extraction) - Symbol Tracking:
symbol/directory (intra-file analysis) - Code Quality:
quality/directory (metrics calculation) - Collection:
collection.rs(parsing and collection)
License
See the workspace root for license information.
Contributing
Contributions are welcome! Please see the workspace contributing guidelines.