Config Include Resolver (Rust)
Topics: graphs, DFS, cycle detection, gateway configuration
Problem
Gateway/proxy configs (nginx, Envoy, …) are split across files that include one another. Booting
the gateway means flattening the include graph into one ordered directive list — while refusing
configs that loop forever or nest pathologically deep.
pub const INCLUDE_PREFIX: &str = "include ";
pub enum ResolveError { MissingFile, MaxDepth, Cycle(Vec<String>) }
pub fn resolve(files: &HashMap<String, Vec<String>>, root: &str, max_depth: usize)
-> Result<Vec<String>, ResolveError>;
files maps a filename to its lines. A line include <name> pulls in that file's directives in
place; every other line is a literal directive. Resolution starts at root and is depth-first.
- Expand includes in order, in place — a file's directives appear exactly where its
include
line sat.
- The same file may be included on different branches and expands each time — that is not a
cycle. A cycle is revisiting a file already on the current path; return
Cycle(chain) where
chain is the path that closed the loop (e.g. ["a","b","a"]).
root is depth 0; each include is one level deeper. Visiting a file at depth > max_depth
returns MaxDepth.- A missing
root, or an include of an absent file, returns MissingFile.
main:[listen 80, include common, gzip on], common:[timeout 30, include security], security:[tls on]
→ [listen 80, timeout 30, tls on, gzip on]
main:[include a, include b], a:[include shared, x], b:[include shared, y], shared:[s]
→ [s, x, s, y] // shared expands on both branches — not a cycle
a:[include b], b:[include a] → Err(Cycle(["a","b","a"]))
A DFS that tracks the set of files on the current path (not a global visited set) makes the
cycle-vs-diamond distinction fall out; carry the recursion depth to enforce max_depth.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.