Config Include Resolver (C)
Topics: graphs, DFS, recursion, cycle detection
Problem
Flatten a config file that can pull in others with include <file> lines, like
nginx/Apache includes. Walk includes depth-first, expanding each in place and
emitting every other line as-is — while detecting include cycles and bounding the
nesting depth.
typedef enum { CFG_OK, CFG_MISSING_FILE, CFG_MAX_DEPTH, CFG_CYCLE } CfgStatus;
typedef struct { const char *name; const char *const *lines; int nlines; } CfgFile;
CfgStatus cfg_resolve(const CfgFile *files, int n, const char *root, int max_depth,
const char **out, int *out_len, const char **chain, int *chain_len);
- A line is an include iff it starts with
"include "; the child file name is the
rest of the line. Any other line is a literal directive, emitted verbatim.
CFG_OK — out[0..*out_len) is the expanded directive stream.CFG_CYCLE — chain[0..*chain_len) is the include path that closed the loop
(e.g. {"a","b","a"}).CFG_MISSING_FILE — the root, or an included file, doesn't exist.CFG_MAX_DEPTH — recursion went deeper than max_depth (root is depth 0).
Key concepts
- On-path set, not global visited: a cycle is an include that's currently on
the recursion stack. A file reached on two sibling branches (a diamond) is not
a cycle — it legitimately expands twice. Track the path and pop on the way out.
- Self-include is a cycle:
a including a closes a loop of length one
(chain {"a","a"}).
- Depth is a separate guard from cycle detection — a deep but acyclic chain
still fails once it passes
max_depth.
The output stream, the path stack, and the cycle chain are all fixed-size arrays —
no allocation.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/config && /tmp/config
Sign in to submit your solution.