kernel.core.feature-model
Feature Model, FM for short. Implements a feature model representation and mutation operators.
This is the interface to the actual application. Every operation on the feature model is encapsulated and may be replaced with a more efficient / more suitable implementation (i.e., an existing implementation).
Here we implement a feature model as a hash table that contains a feature tree and constraints. This is the trivial implementation that directly corresponds to our concept. The feature tree is essentially a hash table from feature identifiers to attribute-value pairs with the following attributes:
- parent-ID: identifier of the parent feature (or :graveyard for removed features, nil for the root). children are not saved explicitly (but implicitly) and may be stored by the implementation for performance reasons. In this implementation, a children cache is maintained.
- optional?: boolean, whether a feature is optional or mandatory
- group-type: :and, :or or :alternative
- additional custom properties, such as name or abstract.
The constraints are a hash table from constraint identifiers to attribute-value pairs with the following attributes:
- formula: a propositional formula (represented as vectors of feature IDs and operators, including :not, :disj, :conj, :eq, and :imp)
- graveyarded?: boolean, whether the constraint is removed or not
All interactions with the feature model happen through a defined API, so the implementation may be changed (as long as the API is correctly implemented). The efficiency of the implementation is critical and O(1) is desired (and possible for most functions). Our concept is tailored towards not-extended, no-cardinalities feature models with arbitrary cross-tree constraints and group types/optional flags. The approach is certainly adaptable to other FM types, but this requires touching the conflict relation. This implementation is assumed to be mutation-free, i.e. mutating functions always return a mutated (structurally sharing) copy of the original. Also this API defines certain data types (i.e., sets) to be returned. This should be respected for efficiency reasons.
Before mutation, the parameters have to be checked (does the feature actually exist etc.) to detect mistakes and manipulation attempts. **TODO*: Right now, the implementation assumes that does not happen. The passed feature model, however, does not have to be checked. The implementation may assume that the passed feature model is valid and free of any inconsistencies. Provided that all other parameters are then valid, the implementation is expected to again return a consistent modified feature model.
_=
(_= FM-a FM-b)Determines whether two feature models are the same (deep equality). OPTIMIZE: This is only needed for testing purposes.
attribute=
(attribute= attribute-a attribute-b)Determines whether two attribute values (including custom properties) are the same. Should be a value-based equality. When only primitive values are used, Clojure equality is sufficient (not necessarily when complex custom properties are included).
create-constraint
(create-constraint FM ID)Creates a new constraint with the given new identifier. Returns the new feature model or, in case the identifier already exists, the unchanged feature model. Uses the default attribute values defined above. (The ID should be a globally new identifier for each created feature, so this function is not usually expected to be called twice with the same identifier.)
create-feature
(create-feature FM ID)Creates a new feature with the given new identifier. Returns the new feature model or, in case the identifier already exists, the unchanged feature model. Uses the default attribute values defined above. (The ID should be a globally new identifier for each created feature, so this function is not usually expected to be called twice with the same identifier.)
default-constraint-formula
(default-constraint-formula)Returns the default formula attribute for a newly created constraint. We start with no formula at all.
default-constraint-graveyarded?
(default-constraint-graveyarded?)Returns the default graveyarded attribute for a newly created constraint. Newly created constraints are graveyarded until explicitly shown.
default-feature-group-type
(default-feature-group-type)Returns the default group type attribute for a newly created feature. By convention, newly created features form an and group.
default-feature-name
(default-feature-name)Returns the default name attribute for a newly created feature.
default-feature-optional?
(default-feature-optional?)Returns the default optional attribute for a newly created feature. By convention, newly created features are optional.
default-feature-parent
(default-feature-parent)Returns the default parent for a newly created feature. Newly created features are not part of the feature tree until explicitly inserted and therefore graveyarded.
get-constraint-graveyarded?
(get-constraint-graveyarded? FM ID)Returns the boolean graveyarded flag of a constraint.
get-constraint-referenced-feature-IDs
(get-constraint-referenced-feature-IDs FM ID)Returns a set of all identifiers of features referenced in a constraint’s propositional formula.
get-feature-children-IDs
(get-feature-children-IDs FM ID)Returns a set of all immediate children identifiers for a given feature.
get-feature-group-type
(get-feature-group-type FM ID)Returns the group type of a feature. This includes :and, :or and :alternative.
get-feature-optional?
(get-feature-optional? FM ID)Returns the boolean optional flag of a feature.
get-feature-parent-ID
(get-feature-parent-ID FM ID)Returns the identifier of the given feature’s parent. Returns nil for the root feature. Returns :graveyard for explicitly removed features. A return value other than :graveyard may still mean that the feature is graveyarded implicitly.
get-feature-property
(get-feature-property FM ID property)Returns the value of a custom property of the given feature. The implementation may define which properties are allowed here (the same as in the setter). Additional property validation has to be done locally at generation time and in the conflict relation.
get-path-to-root
(get-path-to-root FM _ID)Computes a feature’s path to the root feature. Assumes that no cycles are in the graph.
graveyarded-constraint?
(graveyarded-constraint? FM ID)Returns whether the given constraint is im- or explicitly graveyarded.
graveyarded-feature?
(graveyarded-feature? FM _ID)Returns whether the given feature is im- or explicitly graveyarded.
initialize
(initialize FM)For a given initial representation of a feature model, initializes the feature model (if necessary) for other implementation functions to use.
In this specific implementation, the feature model is expected as a hash table with the following keys:
- :features is a feature tree as described above
- :constraints is a constraint map as described above
A cache with the key :children-cache is created for saving children identifiers so that the tree can be efficiently traversed in both directions. The graveyard is initially expected to be empty. OPTIMIZE: Instead of transferring the initialized feature model over the wire, we could just transfer the uninitialized feature model and build the children cache at the client (to save bandwidth).
part-of-and-group?
(part-of-and-group? FM ID)Returns whether the given feature is included in an and group. The root feature is, by convention, not considered as part of an and group (this avoids a special case in the conflict relation to guarantee that the root is always mandatory).
semantic-rules
(semantic-rules)A sequence of additional semantic rules to validate in conflict detection. A semantic rule is a function taking a feature model that returns true when a conflict is present.
Here, this sequence is hard-coded. More effort is needed to dynamically en- or disable semantic rules because this has to be synchronized across all sites.
set-constraint-formula
(set-constraint-formula FM ID formula)Sets the given constraint’s formula.
set-constraint-graveyarded?
(set-constraint-graveyarded? FM ID graveyarded?)Sets the given constraint’s graveyarded flag.
set-feature-group-type
(set-feature-group-type FM ID group-type)Sets the given feature’s group type.
set-feature-optional?
(set-feature-optional? FM ID optional?)Sets the given feature’s optional flag.
set-feature-parent-ID
(set-feature-parent-ID FM ID parent-ID)Sets the identifier of the given feature’s parent. For the value nil, sets the root feature. For the value :graveyard, removes the given feature and its subtree (while keeping all metadata).
set-feature-property
(set-feature-property FM ID property value)Sets the value of a custom property of the given feature. See get-feature-property.