Lightweight directed graph implementation for cycle detection in macro expansion This module provides a compact, allocation-efficient directed graph (digraph) specifically designed for detecting circular dependencies during macro expansion in the fpx preprocessor.
Features:
- Fixed-size adjacency list using a dense 2D integer array (fast access, no pointers)
- Dynamic edge insertion with automatic per-vertex size tracking
- Depth-first search (DFS) based) cycle detection starting from any vertex
- Automatic cleanup via finalizer
- No dynamic memory fragmentation – ideal for frequent creation/destruction during preprocessing
Used internally by fpx_macro to prevent infinite recursion when a macro expands (directly or indirectly) to itself (e.g., #define A B, #define B A).
- Detect circular macro dependency:
type(digraph) :: g
logical :: cycle
g = digraph(3)
call g%add_edge(1, 2)
call g%add_edge(2, 3)
call g%add_edge(3, 1)
cycle = g%is_circular(1)
print *, 'Circular macro chain detected:', cycle
...
- Safe expansion (used inside fpx_macro):
type(digraph) :: expansion_graph
expansion_graph = digraph(size(macros))
call expansion_graph%add_edge(current_macro_idx, referenced_macro_idx)
if (expansion_graph%is_circular(referenced_macro_idx)) then
end if
...
|
| type | digraph |
| | Directed graph with fixed vertex count and efficient cycle detection Stores edges in a dense adjacency matrix slice per vertex. Only the actually used portion of each row is tracked via list_sizes. More...
|
| |
◆ dfs_recursive()
| recursive logical function dfs_recursive |
( |
class(digraph), intent(in) | this, |
|
|
integer, intent(in) | vertex, |
|
|
logical, dimension(:), intent(inout) | visited, |
|
|
logical, dimension(:), intent(inout) | recursion_stack ) |
|
private |
Internal recursive DFS worker for cycle detection.
Definition at line 168 of file graph.f90.
