kernel.core.compound-operation
Compound Operation, CO for short. Compound operations are sequences of primitive operations (kernel.core.primitive-operation). They correspond to feature modeling operations.
They are considered atomic as they have to be sent and received together (so that no other operations interleave). Compound operations also serve as input to the MOVIC algorithm (kernel.core.movic) to determine conflicts.
We provide an initial set of compound operations which may be extended. Below we give some guidance when designing new compound operations.
Compound operations have preconditions which should hold when the operation is generated (which is easy), but also whenever it is applied on another site’s feature model - this has to be ensured by the conflict detection (kernel.core.conflict-relation). For example, create-feature-above requires the supplied features to be siblings.
Some compound operations (e.g., create-feature-above) use information from the current feature model at generation time. This is legitimate, but may result in additional preconditions (e.g., supplied features must be siblings).
We always send compound operations over the wire, which in turn always consist of primitive operations. This makes it easy to compose compound operations, by just flattening their respective primitive operation sequences.
Compound operations should avoid setting the same feature attribute multiple times as this may raise false positives. For example, if a compound operation sets an attribute from A to B and later back to A, this operation has no net impact on said attribute. Nevertheless, this will cause a conflict with any other concurrent operation that targets the same attribute.
If a compound operation has to set the same feature attribute twice nonetheless, it is recommended to simplify them locally at generation time. For example, two updates targeting the same attribute can be merged into one. In this initial set of compound operations, we use local simplification to filter nop primitive operations from compound operations, as they have no effect to the feature model (kernel.core.primitive-operation/remove-nop).
Some of the compound operations’ preconditions introduce false-positives. For example, concurrent create-feature-above root and remove-feature root is considered a conflict, but may not be perceived as one. We argue that this is useful behaviour, as these cases may still be perceived conflicts, at least they target closely related features. Further, these preconditions help guaranteeing basic consistency properties like the single-root rule (remove-feature) and are simple to check and implement.
TODO: We currently do not consider the order of feature siblings or constraints. This means it is impossible to reorder feature siblings or constraints, or to create sibling features. We could introduce a reordering operation that treats concurrent writes to the same group of children as conflicts.
_apply
(_apply FM CO)Applies a given compound operation to a feature model. Does so by subsequently applying the compound operation’s primitive operations in order.
apply*
(apply* FM COs)Applies a sequence of compound operations in order to a feature model.
compose-PO-sequences
(compose-PO-sequences & PO-sequences)Composes multiple compound operations into one compound operation.
concurrent?
(concurrent? CO-a CO-b)Returns whether two compound operations are concurrent, i.e., no one causally precedes the other.
create-constraint
(create-constraint _FM formula)Creates a constraint and initializes it with a given propositional formula.
create-feature-above
(create-feature-above FM & IDs)Creates a feature above a set of sibling features. The set must not be empty and all contained features must be valid and siblings. Their parent must be the same as in the operation’s generation context. This is guaranteed automatically by the fact that competing concurrent updates on any parent cause conflicts (because both operations set the parent).
create-feature-below
(create-feature-below FM parent-ID)Creates a feature below another feature. The parent feature must be valid.
get-description
(get-description CO)Returns the human-readable description of a compound operation. Concatenates descriptions for composed COs.
get-icon
(get-icon CO)Returns the icon of a compound operation. For composed COs, returns the first icon.
get-PO-sequence
(get-PO-sequence CO)Returns the sequence of primitive operations of a compound operation.
get-site-ID
(get-site-ID CO)Returns the generating site of a compound operation. This is the site that issued the compound operation, or a site that has left.
get-timestamp
(get-timestamp CO)Returns the timestamp of a compound operation (only for UI purposes).
invert-PO-sequence
(invert-PO-sequence PO-sequence)Inverts a compound operation by inverting and reversing its primitive operations (socks-shoes property).
make
(make PO-sequence ID VC site-ID)For a sequence of primitive operations, creates a compound operation. Every compound operation has an identifier to distinguish it from other compound operations with the same PO sequence and to allow for undo/redo. Every CO carries a vector clock to relate it causally to other operations. Every CO also stores the generating site, but this is just informational and a site identifier can easily be invalidated when a site leaves.
make-PO-sequence
(make-PO-sequence & POs)Simplifies a sequence of primitive operations by removing any nop POs.
move-feature-subtree
(move-feature-subtree FM ID parent-ID)Moves an entire feature subtree rooted at a feature below another feature. Both must be valid features. The targeted feature subtree must not lie below the moved feature subtree.
preceding?
(preceding? CO-a CO-b)Returns whether a compound operation causally precedes another compound operation. OPTIMIZE: Possibly, we could also check whether CO-a is in CP(CO-b), this would be O(1).
remove-feature
(remove-feature FM ID)Removes a single feature. The feature must be valid. The feature’s children must be the same as in the operation’s generation context, otherwise concurrently added or removed child features may not be handled as expected. Removing child features provokes a conflict with the updates in the children’s parents. Adding child features, however, does not conflict with this operation by default, this is forced by an assert operation (kernel.core.primitive-operation/assert-no-child-added). Also, the feature’s parent must be the same as in the generation context. This is guaranteed because remove-feature also sets the feature’s parent to :graveyard and this conflicts with any other updates on the feature’s parent.
Special care has to be taken when removing the root feature, as the feature tree is required to have a single root at all times. In particular, the root may only be removed if it has exactly one child feature. Any other competing concurrent operations that add or remove child features below the root must then be considered conflicting. Both cases are covered by the same rules as above: Competing removes conflict as they set the feature’s parent, while the remove-root operation sets the child’s parent to nil. Competing additions conflict per the assertion operation. In other words, no more precautions are necessary to guarantee the single-root rule.
As for said assert operation, we insert it somewhere into the compound operation. It only serves as a conflict generator with update operations that add a child to the removed feature. When inverting this operation for undo/redo, it is kept unchanged. For undo, it could be a nop because the inverse of this operation un-removes the feature and moves the children (and as a concurrent inverse, it assumes that in the meanwhile the feature was not un-removed because that would generate a conflicting update, provoking a new version) and therefore, the children list was not manipulated, which guarantees the precondition automatically. But for redo, the assert operation needs to be preserved (and because of the above guarantee, it does not impact undo at all). Where the assert operation is placed is irrelevant, so order is also irrelevant for undo/redo.
remove-feature-subtree
(remove-feature-subtree FM ID)Removes an entire feature subtree rooted at a feature. The feature must be valid.
set-constraint
(set-constraint FM ID formula)Sets the propositional formula of a constraint.
set-feature-group-type
(set-feature-group-type FM ID group-type)Sets the group type attribute of a feature. The feature must be valid.
set-feature-optional?
(set-feature-optional? FM ID optional?)Sets the optional attribute of a feature. The feature must be valid.
set-feature-property
(set-feature-property FM ID property value)Sets some additional property of a feature. These may be arbitrary properties such as name, hidden, abstract or description. The feature must be valid.