So far, calling Checkable::IsReachable() traversed all possible paths to it's
parents. In case a parent is reachable via multiple paths, all it's parents
were evaluated multiple times, result in a worst-case exponential complexity.
With this commit, the implementation keeps track of which checkables were
already visited and uses the already-computed reachability instead of repeating
the computation, ensuring a worst-case linear runtime within the graph size.
Checkable::IsReachable() and DependencyGroup::GetState() call each other
recursively. Moving them to a common helper class allows adding caching to them
in a later commit without having to pass a cache between the functions (through
a public interface) or resorting to thread_local variables.
This prevents the use of DependencyGroup for storing the dependencies during
the early registration (m_DependencyGroupsPushedToRegistry = false),
m_PendingDependencies is introduced as a replacement to store the dependencies
at that time.
Previously the dependency state was evaluated by picking the first
dependency object from the batched members. However, since the
dependency `disable_{checks,notifications` attributes aren't taken into
account when batching the members, the evaluated state may yield a wrong
result for some Checkables due to some random dependency from other
Checkable of that group that has the `disable_{checks,notifications`
attrs set. This commit forces the callers to always provide the child
Checkable the state is evaluated for and picks only the dependency
objects of that child Checkable.
The new implementation just counts reachable and available parents and
determines the overall result by comparing numbers, see inline comments for
more information.
This also fixes an issue in the previous implementation: if it didn't return
early from the loop, it would just return the state of the last parent
considered which may not actually represent the group state accurately.
This commit removes a distinction in how dependency objects are checked for
cycles in the resulting graph depending on whether they are part of the
initially loaded configuration during process startup or as part of a runtime
update.
The DependencyCycleChecker helper class is extended with a mechanism that
allows additional dependencies to be considered during the cycle search. This
allows using it to check for cycles before actually registering the
dependencies with the checkables.
The aforementioned case-distinction for initial/runtime-update config is
removed by making use of the newly added BeforeOnAllConfigLoaded signal to
perform the cycle check at once for each batch of dependencies inside
ConfigItem::CommitNewItems() for both cases now. During the initial config
loading, there can be multiple batches of dependencies as objects from apply
rules are created separately, so parts of the dependency graph might be visited
multiple times now, however that is limited to a minimum as only parts of the
graph that are reachable from the newly added dependencies are searched.
