Rudder

So, this is how I think we can solve it.

We already have a function which, given a query, is able to tell which nodes match it.
Any dyngroup can be decompose in a simple, fully computable query and the dependance towards other groups, i.e towards other queries (and that, recursively).

The composition between the simple part and the group is either an AND (intersection of nodeids set) or an OR (union of nodeids).

So now, we can build a simple algo with 3 queues: TODO, BLOCKED, DONE. All dyn groups start in TODO. Then, we proceed the TODO queue iteratively. When a node has N dep (N > 0), it goes into BLOCKED.
Then, each time a group is fully computable (no dep), the set of nodeid matching it is evaluated, and it goes into DONE.
At that point, we put back each group in BLOCKED which were only blocked by the newly finished group at the end of TODO queue, and for each, we intersect or union the set of nodes matching.

We are sure to progress by at least one element in TODO (even when we put back some from BLOCKED, and BLOCKED never get refilled), so at some point TODO is empty. If some groups remain in BLOCKED, it means their dependencies can't be computed (mutual dependencies of dep towards static groups). We set these dependencies to nodeids == empty set, and we do the final TODO processing (after union/intersec).

And done!

An imagine to illustrate the process (it misses the last step where we zeroïze dependencies of group in the BLOCKED queue at the end)

PR https://github.com/Normation/rudder/pull/1882

Applied in changeset rudder|c26ba5cf2bce52d443e41a1cc0d1865685724355.

This bug has been fixed in Rudder 4.3.0~rc2 which was released today.

• 4.3.0~rc2: Announce Changelog
• Download: https://www.rudder-project.org/site/get-rudder/downloads/