Problem

At AcmeCI, a pipeline consists of named gates with directed dependencies and additional OR-rules. You must compute the smallest set of gates (and an execution order) needed to reach a given milestone.

Specification

Implement plan_devsecops_gates(gates, deps, milestone, rules) -> list[str].

• gates: list of unique gate names.
• deps: list of pairs [a, b] meaning gate a must run before gate b.
• rules: list of rules [[opt1, opt2, ...], before_gate] meaning at least one option must run before before_gate.
• Output: a list of gate names in execution order.

The plan must:

1. Include milestone.
2. Be closed under dependencies: if a gate is included, all its prerequisites (dependency ancestors) must be included.
3. Satisfy every rule whose before_gate is included (including milestone if it appears as a before_gate).
4. Be a valid topological order of included gates.
5. Minimize the number of included gates; break ties by returning the lexicographically smallest valid order. Return [] if impossible.

Examples

1. gates=[checkout,build,sast,sca,container_scan,deploy_prod], deps=[[checkout,build],[build,container_scan],[container_scan,deploy_prod]], rules=[[[sast,sca],deploy_prod],[[container_scan],deploy_prod]], milestone=deploy_prod → [checkout, build, sca, container_scan, deploy_prod] (pick sca to satisfy the OR-rule).

2. gates=[a,b,c,deploy], deps=[[a,deploy],[b,deploy],[c,deploy]], rules=[[[b,a],deploy]], milestone=deploy → [a, deploy] (only one option is needed; minimal picks a).

Constraints

• 1 <= len(gates) <= 60
• 0 <= len(deps) <= 200
• 0 <= len(rules) <= 12
• 1 <= len(options) <= 12 for each rule
• Return [] if no valid plan exists.