Index: /reasoner/consRescheduling.tex =================================================================== --- /reasoner/consRescheduling.tex (revision 222) +++ /reasoner/consRescheduling.tex (revision 223) @@ -1,5 +1,18 @@ \section{Constraint Re-scheduling}\label{sectTopLevelConstraintsRescheduling} -When configuration variable $v$ is changed as side effect of a constraint evaluation, modifications of the constraint base may be required, e.g., when the value of a constraint variable or the type of a compound value changes. Upon a value change, Algorithm \ref{algVarChange} is called\footnote{In the implementation, Algorithm \ref{algVarChange} is realized as a combination of a visitor and a listener in \class{RescheduleValueChangeVisitor.java}.}. +When configuration variable $v$ is changed as side effect of a constraint evaluation, modifications of the constraint base may be required if the value of a constraint variable or the type of a compound value changes. In particular, dependent constraints affected by the changed variables must be re-scheduled for constraint evaluation (forward-chaining). + +Moreover, as discussed above, we must distinguish between +\begin{itemize} +\item compound variables, as the value may change along the compound refinement hierarchy and different types may imply different constraints. +\item constraint variables, as the old constraint in the variable must be replaced in the constraint base by the new value. +\item local variables, which must be tracked to assign values of constraint variables correctly (cf. Section \ref{sectConstraintVariables}). +\end{itemize} + +We structure this section into general value changes (Section \ref{sectReSchedGeneral}), which is called for any value change including local variables, configuration variable value changes (Section \ref{sectReSchedComp}), constraint value changes (Section \ref{sectReSchedConstr}), and value type changes (Section \ref{sectReSchedType}). + +\subsection{General Value Changes}\label{sectReSchedGeneral} + +When the value of a any variable is changed, Algorithm \ref{algVarChange} is called\footnote{In the implementation, Algorithm \ref{algVarChange} is realized as a combination of a visitor and a listener in \class{RescheduleValueChangeVisitor.java}.}. \begin{algorithm}[H] @@ -29,8 +42,8 @@ Algorithm \ref{algVarChange} receives information about a value change in terms of the changed variable $v$ (already holding the new value) and the old value $val_o$ before the value change. If a configuration variable was changed, the algorithm determines the kind of the change and either creates new constraints using the constraint translation introduced in Section \ref{sectTranslation}, adds dependent constraints for re-evaluation to the constraint base, or removes superfluous constraints. If a local variable was changed, e.g., an iterator variable, Algorithm \ref{algVarChange} adjusts the variable mapping as discussed in Section \ref{sectConstraintVariables}. -If a (non-local) configuration was changed (line \ref{algVarChangeIsLocal}), the value change is relevant for re-scheduling related or dependent constraints. Algorithm \ref{algVarChange} registers in line \ref{algVarChangeScope} the change of $v$ within the actual project scope. This information is used by the expression evaluator to avoid illegal duplicate assignments within the same scope. If the value changed (lines \ref{algVarChangeRescheduleConstraintVariables}-\ref{algVarChangeRescheduleValueTypeChange}), this may involve a constraint variable or imply a value type change. If the value of a (nested) constraint variable was changed, we call Algorithm \ref{algRescheduleConstraintValue} in line \ref{algVarChangeRescheduleConstraintVariables} to exchange the involved constraints. - -If the type of the value changed, we call Algorithm \ref{algTranslateValueTypeChange} to add or to remove related constraints (line \ref{algVarChangeRescheduleValueTypeChange}). Function $isValueTypeChange$ determines a value type change if $v$ is a compound variable, old and new value are given and their types differ: - +If a (non-local) configuration was changed (line \ref{algVarChangeIsLocal}), the value change is relevant for re-scheduling related or dependent constraints. Algorithm \ref{algVarChange} registers in line \ref{algVarChangeScope} the change of $v$ within the actual project scope. This information is used by the expression evaluator to avoid illegal duplicate assignments within the same scope. If the value changed (lines \ref{algVarChangeRescheduleConstraintVariables}-\ref{algVarChangeRescheduleValueTypeChange}), this may involve a constraint variable or imply a value type change. + +Algorithm \ref{algVarChange} dispatches to the further cases: If the value of a (nested) constraint variable was changed, we call in line \ref{algVarChangeRescheduleConstraintVariables} Algorithm \ref{algRescheduleConstraintValue} (cf. Section \ref{sectReSchedComp}) to exchange the involved constraints. If the type of the value changed, we call in line \ref{algVarChangeRescheduleValueTypeChange} Algorithm \ref{algTranslateValueTypeChange} (cf. Section \ref{sectReSchedConstr}) to add or to remove type-related constraints. Function $isValueTypeChange$ determines a value type change if $v$ is a compound variable, old and new value are given and their types differ: +% \begin{align*} is&ValueTypeChange(v, val_n, val_o) = \\&\begin{cases} val_o \neq \undef \wedge~val_n \neq \undef \wedge~type(val_o) \neq type(val_n) & isCompound(type(v))\\ false & \text{else}\end{cases} @@ -40,4 +53,10 @@ In any case of a value change of $v$, the reasoner shall perform forward reasoning, i.e., check whether constraints using $v$ are still valid. Therefore, Algorithm \ref{algVarChange} consults the relevant constraints per declaration $\relevantConstraintsPerDeclaration$ and adds all registered constraints for all parent and nested variables to the constraint base (lines \ref{algVarChangeRescheduleParents}-\ref{algVarChangeRescheduleNested}), but only if the respective constraints are not already in the constraint base. + +If the changed variable is local and there is a mapping in $\variableMapping$, e.g., as the variable is used as iterator in the evaluation of a quantor expression, we adjust the variable mapping\footnote{A local decision variable wraps either a value (if the evaluation runs over constants) or a decision variable. To allow for (call-by-reference) evaluation of nested slots and attributes, this part actually refers to the wrapped decision variable (not detailed here).}. If the subsequent evaluation of the quantor expression causes a change of a variable, Algorithm \ref{algVarChange} will be called for that variable. If then either Algorithm \ref{algRescheduleConstraintValue} or Algorithm \ref{algTranslateValueTypeChange} is called, the involved constraint translations will consider the changed $\variableMapping$ in their variable substitutions and replace unbound iterator variables. + +\subsection{Configuration Variable Value Changes}\label{sectReSchedComp} + +Algorithm \ref{algRescheduleValueChange} is responsible for re-scheduling constraint values contained in a given IVML value. The idea is to follow nested value structures recursively, to extract constraint values and to add them after variable substitution to the constraint base. \begin{algorithm}[H] @@ -65,10 +84,10 @@ \end{algorithm} -If the changed variable is local and there is a mapping in $\variableMapping$, e.g., as the variable is used as iterator in the evaluation of a quantor expression, we adjust the variable mapping\footnote{A local decision variable wraps either a value (if the evaluation runs over constants) or a decision variable. To allow for (call-by-reference) evaluation on nested slots and attributes, this part actually refers to the wrapped decision variable (not detailed here).}. If the subsequent evaluation of the quantor expression causes a change of a variable, Algorithm \ref{algVarChange} will be called for that variable. If then either Algorithm \ref{algRescheduleConstraintValue} or Algorithm \ref{algTranslateValueTypeChange} is called, the involved constraint translations will consider the changed $\variableMapping$ in their variable substitutions and replace unbound iterator variables. - - -Algorithm \ref{algRescheduleValueChange} is responsible for re-scheduling constraint values from a given IVML value. The idea is to follow nested value structures recursively, to extract constraint values and to add them after variable substitution to the constraint base. Upon the first changed constraint value for the given variable, existing constraints shall be cleared from the reasoning data structures. - -For this purpose, Algorithm \ref{algRescheduleValueChange} receives the changed variable $v$, its optional parent variable $v_p$ (if $v$ is nested into $p$), the old value $val_o$ and a flag that indicates whether existing constraints shall be cleared within this call. If $val_n$ is a constraint, the algorithm calls Algorithm \ref{algRescheduleConstraintValue} (lines \ref{algRescheduleValueChangeConsStart}-\ref{algRescheduleValueChangeConsEnd}). If $val_n$ is a compound, the algorithm calls itself recursively for all slots that have a value assigned (lines \ref{algRescheduleValueChangeCompStart}-\ref{algRescheduleValueChangeCompEnd}). Finally, if $val_n$ is a container, the algorithm iterates over the elements in the new and the old value (assuming that at least all elements in $val_n$ are considered, eventually $val_o$ is $\undef$ then) and calls itself recursively for each pair (lines \ref{algRescheduleValueChangeContStart}-\ref{algRescheduleValueChangeContEnd}). Existing constraints are cleared only for the first element pair ($first$). + +Algorithm \ref{algRescheduleValueChange} receives the changed variable $v$, its optional parent variable $v_p$ (if $v$ is nested into $p$), the old value $val_o$ and the flag $clear$ that indicates whether existing constraints shall be cleared within this call. For container variables, $clear$ shall only be true for the first element to avoid clearing again constraints for elements that already have been processed for the same container. + +If $val_n$ is a constraint, the algorithm calls in lines \ref{algRescheduleValueChangeConsStart}-\ref{algRescheduleValueChangeConsEnd} the algorithm for constraint value changes, i.e., Algorithm \ref{algRescheduleConstraintValue} (cf. Section \ref{sectReSchedConstr}). If $val_n$ is a compound, the algorithm calls itself recursively for all slots that have a value assigned (lines \ref{algRescheduleValueChangeCompStart}-\ref{algRescheduleValueChangeCompEnd}). Finally, if $val_n$ is a container, the algorithm iterates over the elements in the new and the old value (assuming that at least all elements in $val_n$ are considered, eventually $val_o$ is $\undef$ then) and calls itself recursively for each pair (lines \ref{algRescheduleValueChangeContStart}-\ref{algRescheduleValueChangeContEnd}). Existing constraints are cleared only for the first element ($first$). + +\subsection{Constraint Value Changes}\label{sectReSchedConstr} Algorithm \ref{algRescheduleConstraintValue} targets re-scheduling a constraint value. This involves replacing existing constraints for a given variable $v$ by a new constraint instantiated using variable substitution. In more details, Algorithm \ref{algRescheduleConstraintValue} receives the changed variable $v$, its optional parent variable $v_p$ and a flag whether existing constraints shall be cleared (if this function is called repeatedly on the same $v_p$, e.g., for all slots of a compound). @@ -143,5 +162,7 @@ %\end{algorithm} -When the value of variable $v$ changes, also its actual type may change, in particular if $v$ is a compound variable. If the differing types also specify different constraints, the reasoner must adjust the constraint set accordingly. Moreover, a type change may also be caused when the value is changed from or to the IVML value \IVMLnull{} (different from $\undef$ / null of the implementing programming language). In these cases, a configed value is explicitly replaced by nothing (no configuration) or \IVMLnull{} is replaced by a certain value. Algorithm \ref{algTranslateValueTypeChange} handles these four cases\footnote{\label{fnVisibilityResolver}Due to technical reasons, in particular the visibility of involved attributes, this algorithm is realized in \class{Resolver.java} rather than \class{RescheduleValueChangeVisitor}.}, i.e., changing from / to \IVMLnull{} or changing the actual type up- or down the type hierarchy. Generally, all cases could be handled by first removing all existing constraints and then executing the constraint translation from Section \ref{sectTranslation}. However, this can lead to unnecessary creation of already scheduled or even successfully evaluated constraints, i.e., inefficient or even wrong reasoning situations. To avoid such transformations, Algorithm \ref{algTranslateValueTypeChange} operates on the difference among the involved types, i.e., in particular if the type changes along the refinement hierarchy, it identifies the types in between the old and the new type in the type hierarchy and either creates constraints or removes constraints according to the differnce. +\subsection{Value Type Changes}\label{sectReSchedType} + +If the value of variable $v$ changes, also its actual type may change, in particular if $v$ is a compound variable. If the differing types also specify different constraints, the reasoner must adjust the constraint set accordingly. Moreover, a type change may also be caused when the value is changed from or to the IVML value \IVMLnull{} (different from $\undef$ / null of the implementing programming language). In these cases, a configed value is explicitly replaced by nothing (no configuration) or \IVMLnull{} is replaced by a certain value. Algorithm \ref{algTranslateValueTypeChange} handles these four cases\footnote{\label{fnVisibilityResolver}Due to technical reasons, in particular the visibility of involved attributes, this algorithm is realized in \class{Resolver.java} rather than \class{RescheduleValueChangeVisitor}.}, i.e., changing from / to \IVMLnull{} or changing the actual type up- or down the type hierarchy. Generally, all cases could be handled by first removing all existing constraints and then executing the constraint translation from Section \ref{sectTranslation}. However, this can lead to unnecessary creation of already scheduled or even successfully evaluated constraints, i.e., inefficient or even wrong reasoning situations. To avoid such transformations, Algorithm \ref{algTranslateValueTypeChange} operates on the difference among the involved types, i.e., in particular if the type changes along the refinement hierarchy, it identifies the types in between the old and the new type in the type hierarchy and either creates constraints or removes constraints according to the differnce. In details, Algorithm \ref{algTranslateValueTypeChange} receives the changed variable $v$, and, as already available in the caller, the new value $val_n$ and the old value $val_o$ of $v$. Algorithm \ref{algTranslateValueTypeChange} is only called (by Algorithm \ref{algVarChange} in line \ref{algVarChangeRescheduleValueTypeChange}) if the types of $val_o$ and $val_n$ differ, i.e., in particular not if the types are equal. As mentioned above, Algorithm \ref{algTranslateValueTypeChange} distinguishes four cases: