Mutually recurses with uncached-conflicting*? to cache conflict detection results.

The CDAG, HB, base-FM and CC& arguments are passed down as context. This function only uses (and modifies) the conflict cache.

For each primitive operation from one compound operation CO-x, checks whether applying it would compromise feature model consistency assuming that another compound operation CO-y has already been applied.

Some rules access to the feature model (e.g., children implicitly targeted by an operation), which has to be obtained by actually applying the operations to intermediate feature models. This is potentially slow, although this is only required if operations are eligible for conflict, i.e. concurrent, which is not the most common case.

Multiple rules are checked to guarantee basic feature model consistency (called syntactic consistency):

• The no-overwrites rule flags two updates that target the same feature/constraint attribute as conflict.
• The no-cycles rule flags any two updates as conflict that introduce a cycle to the feature tree.
• The no-graveyarded rule flags an update and a remove (which is in turn a special update) as conflict when the update targets the removed feature/constraint or an implicit child of the removed feature. A special case must be considered, namely un-removing a removed or created feature/constraint (setting the parent from :graveyard to something else).
• The group-children rule flags two updates as conflict if one changes a feature group to :or or :alternative, and the other sets a child of said feature to mandatory or optional.
• The assert-no-child-added rule flags two updates as conflict if one asserts that no feature children may be added by the other, but the other adds feature children nonetheless (see kernel.core.compound-operation/remove-feature).

All rules included here are checked in a short-circuiting way, so they may build upon each other, and they should return true if a conflict is present. These rules assume that CO-y has been applied and everything up to, but excluding PO-x.

Determines whether two compound operations are in conflict, assuming that no causally preceding operations were in conflict.

First, it is checked whether subsequently applying CO-a (assuming CO-b has already been applied) yields a conflict. The same is then checked the other way by subsequently applying CO-b (assuming CO-a has already been applied). Finally, any additional semantic rules are checked.

The CDAG, HB and base-FM arguments are passed down as context for CO-syntactically-conflicting?.

OPTIMIZE: Remove the assertion.

Determines whether two compound operations are in semantic conflict, according to the rules defined in kernel.core.feature-model/semantic-rules.

Determines whether two compound operations are in syntactic conflict, according to the rules defined in CO-conflict-reducer.

For that, produces a feature model suitable for subsequently applying CO-x. The feature models are well-defined, because the CDAG has all information regarding CP-x and CP-y across all sites (due to causality preservation), and we may simply assume base-FM to represent the CDAG garbage collected up to this point (so the base-FM can be seen as an implementation detail of the CDAG, i.e., if there was no base-FM, we would just use the entire CDAG on an empty initial feature model, which is clearly correct).

First applies (set/intersection CP-x CP-y) to base-FM, then (set/difference CP-y (set/intersection CP-x CP-y)). Because the intermediate result is not needed, their union can directly be applied, which is CP-y, yielding base-FM+preceding-CO-y.

Next, CO-y is applied, yielding base-FM+preceding-CO-y+CO-y. Both of these are required to ensure CO-conflict-reducer’s assert-no-child-added rule.

Next, (set/difference CP-x (set/intersection CP-x CP-y)) is applied, which simplifies to (set/difference CP-x CP-y), yielding base-FM+preceding-CO-y+CO-y+preceding-CO-x.

This feature model is fed into CO-conflict-reducer which subsequently applies all primitive operations contained in CO-x to produce a final base-FM+preceding-CO-y+CO-y+preceding-CO-x+CO-x.

Determines whether two operations are compatible with each other. As it is derived from the conflict relation, it is reflexive and symmetric, but not transitive. This kind of relation is also known as compatibility relation. This guarantees convergence, but it is only a necessary, not sufficient condition for intention preservation (Xue et al., 2003).

Determines whether two compound operations are in conflict with each other. This may only be the case for concurrent operations, as causally ordered operations can be guaranteed compatible at generation time. This relation should be irreflexive and symmetric. It is not generally transitive. When called with a newly arrived operation, it should be the second one to allow for optimization.

Determines whether two compound operations are in conflict. If they are, causally succeeding operations are also in conflict (a transitivity of sorts).

As this relation is only used by MOVIC when a new operation arrives, we may assume that if one of CO-a or CO-b is the new operation, it is CO-b (this does not impact the result, it is only an optimization).

The CDAG, HB, base-FM and CC& arguments are passed down as context. This function only uses CDAG to obtain CIPs of CO-a and CO-b.

Algorithm pseudocode (CACHE is only a performance optimization and not essential):

conflicting?(CO-a, CO-b): (assuming that if a new operation is supplied, it is CO-b)
CACHE: if CO-a, CO-b are known, return whether #{CO-a, CO-b} is in the cache; else continue
if CO-a not concurrent CO-b, or CO-a == CO-b: return false (respect causal order and irreflexivity)
foreach CIP(CO-a) and CIP(CO-b), if (conflicting? CIP(CO-a) CIP(CO-b)), goto return_true
foreach CIP(CO-b), if (conflicting? CO-a CIP(CO-b)), goto return_true (this one goes first, as we may hit the cache)
foreach CIP(CO-a), if (conflicting? CIP(CO-a) CO-b), goto return_true (from here on, the cache is not hittable)
if (CO-conflicting? CO-a CO-b), goto return_true
else return false
return_true:
CACHE: add #{CO-a, CO-b} to the cache
return true

For better separation of concerns, conflicting? is split up over two functions, uncached-conflicting*? and cached-conflicting*?.