Feature Flag Compatibility Solver (C)
Topics: constraint satisfaction, backtracking, recursion
Problem
Search for a compatible set of feature flags to enable for a rollout, given
mutual-exclusion and "requires" constraints — a small CSP solved by backtracking.
typedef struct { const char *const *opts; int n; } Group;
typedef struct {
const char *name;
const char *const *excludes; int nexcludes;
const Group *requires; int nrequires;
} Flag;
bool ff_enable(const Flag *flags, int nflags, const char *const *want, int nwant, bool *enabled_out);
ff_enable finds a set of flags that includes every name in want and satisfies
every enabled flag's constraints. On success, write the enabled set into
enabled_out[i] (per flag index) and return true; otherwise return false.
- excludes is symmetric: if A excludes B, then B may not be enabled
alongside A either — even if B doesn't list A. Check both directions.
- requires is a list of groups: for each group, at least one of the
named flags must also be enabled. A 1-element group is a plain "must also
enable"; a multi-element group is a choice.
Key concepts
- A work queue of obligations: "enable this flag (then queue its requires
groups)" and "satisfy this choice group." Process them recursively; on a dead
end, undo what you enabled so a choice point higher up can try another
option.
- Choices need real backtracking: in
new-ui requires {fast-path, legacy-path}, picking fast-path first can conflict with another wanted flag —
the solver must retreat and try legacy-path.
- Skip an already-satisfied choice: if some option in a group is already
enabled, don't pull in another.
No allocation needed — a fixed-size work array and a bool enabled-set suffice.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/flags && /tmp/flags
Sign in to submit your solution.