SpineFM is a tooled approach which aims to describe a SPL with a domain model related to multiple interrelated feature models. It uses a propagation algorithm of configuration actions in order to provide a free-order process for product derivation.

The propagation algorithm consists of two main steps. Given a processing configuration and the associated context, it first computes the restrictions to be applied on the neighbor configurations. Doing so implies to navigate in the domain model and to get the restriction functions and rules. But it also uses the contexts in order to retrieve the right configurations to impact. Then the second step consists in applying the propagation on the configurations which have been impacted.

All functions presented below have been implemented in Java and uses classes generated from the EMF metamodel described above.

public void propagate(ConfigurationProcessStep CPS, Context context) throws FMEngineException {
	Collection<ConfigurationProcessStep> CPSSet;
	CPSSet = this.immediateRestriction(CPS, context);
	this.recursePropagation(CPSSet, context);
}

The propagate function is the entry point of the propagation. It takes as inputs the context in which user actions that triggered the propagation have been done and the altered ConfigurationProcessStep (CPS): actions made by users to configure a product are directly applied on CPSs. This function realizes two actions: first, it computes actions to be done on neighbor CPSs; then from the list of resulting impacted CPSs, the propagation is launched recursively.

private Collection<ConfigurationProcessStep> immediateRestriction(ConfigurationProcessStep CPSSource, Context ContextSource) throws FMEngineException {
	Set<ConfigurationProcessStep> result = new HashSet<ConfigurationProcessStep>();
	DomainElement deSource = CPSSource.getDomainElement();
        Context gc = this.getContextManager().getGlobalContext();
	for (DEAssociation asso : deSource.getBelongs_to()) {
		DomainElement deTarget = asso.getOppositeExtremity(deSource).getApply_on();
		ConfigurationProcessStep CPSTarget;
		if (deTarget.getMultiplicityElement().isExactlyOne()) {
			CPSTarget = gc.getCPSOfDE(deTarget);
		} else {
			CPSTarget = ContextSource.getCPSOfDE(deTarget);
		}
		EList<ActionOnFM> actionsToDo = asso.computeActionsToDo(CPSSource, CPSTarget);
                for (ActionOnFM as : actionsToDo) {
                        if (!CPSTarget.alreadyHaveAction(aof)) {
                                ActionOnFM action = aof.cloneAction();
                                action.setCPS(CPSTarget);
                                action.apply();
                                result.add(CPSTarget);
                        }
                }
	}
	return result;
}

The function immediateRestriction defines the way actions on the neighbor CPSs are computed. The function takes as inputs the CPS that is responsible for the propagation and its associated context. To ease reading in the following, we call this context the propagation context. The function loops on associations whom the DE related to the CPS is the source. Then it computes the list of actions to apply on targeted DEs regarding the associations. Finally it builds the list of impacted CPSs. It gets the right CPS regarding the multiplicity of the DE: if a DE is local then the CPS is taken from propagation context; otherwise, the CPS is taken directly from the GlobalContext. The function computeActionsTodo, to get the actions to be done, is detailed in the class DEAssociation.

private void recursePropagation(Collection<ConfigurationProcessStep> CPSSet, Context context) throws FMEngineException {
        Context gc = this.getContextManager().getGlobalContext();
	for (ConfigurationProcessStep cps : CPSSet) {
		DomainElement deSource = cps.getDomainElement();
		if (deSource.getMultiplicityElement().isExactlyOne() || context.equals(gc)) {
			this.propagate(cps, gc);
			if (!deSource.getMultiplicityElement().isExactlyOne()) {
				for (Context c : this.getContextManager().getLocalContexts()) {
					ConfigurationProcessStep cpsLocal = c.getCPSOfDE(deSource);
					c.mergeExternalCPS(cps);
					propagate(cpsLocal, c);
				}
			}
		} else {
			propagate(cps, context);
		}
	}
}

The function recursePropagation performs the recursion during propagation. It takes as inputs the set of CPS which have been impacted by restrictions and the propagation context. Then the function iterates on each CPS. There are two possibilities: either the CPS refers to a local DE and the context given as input is local, then the propagation is just launched with this CPS; or one of the previous condition is not met, i.e., the CPS refers to a global DE or the changing context corresponds to the global context. Then the propagation must be global. However, if a CPS is changed directly in the global context, all CPSs referring the same DE in all local contexts must belong to the same impacts and the propagation must be replayed from these local contexts. The function mergeExternalCPS (presented in Class Context) retrieves the CPSs with the same DE than the input CPS and performs a merge of actions lists.

public EList<ActionOnFM> computeActionsToDo(ConfigurationProcessStep CPSSource, ConfigurationProcessStep CPSTarget) throws IllegalCallException {
	EList<ActionOnFM> result = new BasicEList<ActionOnFM>();
	ConfigurationState sourceState;
	sourceState = CPSSource.getState();
	for (RestrictionFunction rf : this.getRestrictionFunction()) {
	     for (Rule r : rf.getRules()) {
	          if (r.getState().isIncludedIn(sourceState)) {
		       result.add(r.getActions());
		  }
	     }
	}
 
	return result;
}

This function aims at comparing a list of rules with a configuration state and at selecting which actions to apply on a CPS. Then it takes as inputs two CPSs: the source and the target of the impacts. In order to compute the actions to apply, the function starts by getting the ConfigurationState (CS) corresponding to the CPS source. This operation triggers the application of all actions of the CPS on its associated feature model and gets the list of selected and deselected features to build the CS. Then the function iterates on each rule of each restriction functions of the association and checks whether a CS of a rule matches with the CS returned from the CPS: a match means that a rule can be fired. Moreover, as actions on a feature model are idempotent, a check is done before adding an action in the resulting list to avoid redundancy.

Here is the prolog code, used to prototype the generation of inverse rules.

%%%%
%% Reverse a Rule
%%%%
 
 
%% reverse_rule(+OneRule,-RuleList): reverse one rule returning a set of rules.
%Reverse Conditions
%Second reverse selection part
%Third distribute selection parts
reverse_rule(rule(Selected, Deselected,ActionSet), Rules) :-
	reverse_conditions(Selected, Deselected,ActionList),
        reverse_actions(ActionSet,[],[],Res_Selected,Res_Deselected),
        distributesConditions(Res_Selected,Res_Deselected, ActionList,Rules).
 
 
%% reverse_conditions(+SelectedFeatures,+DeselectedFeatures, -ActionList) : Reverse the conditions of a rule as a set of actions
reverse_conditions( [Selected], [], SelectActionList) :- !,
            reverse_conditions_Selected([Selected],SelectActionList).           
reverse_conditions( [], [Deselected], DeselectActionList) :- !,
            reverse_conditions_Deselected([Deselected],DeselectActionList).
reverse_conditions( Selected, Deselected, [addConstraintOr(Deselected, Selected)] ).
 
reverse_conditions_Selected([S|Selected],[deselect(S)|SelectActionList]) :-
      reverse_conditions_Selected(Selected,SelectActionList).
reverse_conditions_Selected([],[]).
reverse_conditions_Deselected([S|Selected],[select(S)|SelectActionList]) :-
      reverse_conditions_Deselected(Selected,SelectActionList).
reverse_conditions_Deselected([],[]).
 
 
%% Warning : we don't reverse "addConstraintOr" action; this action can be used by end-user 
%% reverse_actions(+ActionList,+SelectedFeatures, +DeselectedFeatures, -FeaturesToSelect, -FeaturesToDeselected) : Reverse the actions of a rule as a condition
reverse_actions([],Selected,Deselected,Selected,Deselected).
reverse_actions([select(B)|ActionList],Selected,Deselected,Res_Selected,Res_Deselected) :-
    reverse_actions(ActionList,Selected,[B|Deselected],Res_Selected,Res_Deselected).
reverse_actions([deselect(B)|ActionList],Selected,Deselected,Res_Selected,Res_Deselected) :-
    reverse_actions(ActionList,[B|Selected],Deselected,Res_Selected,Res_Deselected).
 
 
%% distributesConditions(+SelectedFeatures, +DeselectedFeatures,+ActionList, -RuleList) : distribute the conditions to create a set of rules
distributesConditions([S|Res_Selected],Res_Deselected, ActionList,[rule([S],[],ActionList)|Rules]) :-
            distributesConditions(Res_Selected,Res_Deselected, ActionList,Rules).
distributesConditions([],[D|Res_Deselected], ActionList,[rule([],[D],ActionList)|Rules]) :-
            distributesConditions([],Res_Deselected, ActionList,Rules).
distributesConditions([],[],_,[]).