Index: /reasoner/reasoner.tex =================================================================== --- /reasoner/reasoner.tex (revision 104) +++ /reasoner/reasoner.tex (revision 105) @@ -73,7 +73,14 @@ Besides traditional variability modeling approaches, such as feature modeling~\cite{CzarneckiHelsenEisenecker05, KangCohenHess+90} or decision modeling~\cite{CzarneckiGruenbacherRabiser+12, SchmidJohn04}, in recent time several approaches to textual variability modeling have been proposed~\cite{EichelbergerSchmid15a}. Moreover, there seems to be a trend that more recent variability modeling support more powerful modeling concepts~\cite{EichelbergerSchmid15a}, which then require more powerful analysis and reasoning mechanisms. As stated above, typically these mechanisms then imply limitations of the analysis capabilities, e.g., non-Boolean decisions typically prevent determining the actual number of possible configurations (of course not the number of configuration options that remain to be configured to achieve a complete configuration). -The \emph{Integrated Variability Modeling Language (IVML)}~\cite{IVML-LS} is a textual variability modeling language providing rather powerful modeling concepts, among them a type system, multiple-inheritance, container types, configuration references, imports, orthogonal annotations (for binding times), quantification constraints, or user-defined constraint functions. This even allows for topological variability, i.e., configuring and reasoning over graph structures~\cite{EichelbergerQinSizonenko+16}. In this document, we discuss the approach and recent state of the reasoning mechanism for IVML and its realization in EASy-Producer~\cite{EichelbergerEl-SharkawyKroeher+14, El-SharkawyKroeherEichelbergerSchmid15}. Currently, the reasoning mechanism focuses on translating / creating specifically instantiated constraints for the various IVML concepts and on forward-reasoning, i.e., evaluating the constraints and performing value propagation as much as possible. So far, this allows performing typical validation and propagation tasks. However, we are aware of the fact that more advanced tasks like configuration completion are not supported by the current approach. This is subject to future work, for which this document shall provide a solid foundation. - -This document is structured as follows: Section \ref{sectApproach} introduces the overall approach to reasoning for IVML. Section \ref{sectNotation} introduces the notation that we use to describe the reasoning algorithm, in particular the notation to access (derived) properties of the various IVML concepts. In Section \ref{sectReasoning}, we discuss the top-level algorithms for transforming constraints, reasoning and reacting to value changes / propagation. In Section \ref{sectTranslation}, we detail the instantiation and translation of constraints for individual configuration settings. In Section \ref{sectCompleteness}, we analyze the effect translations in order to assess the actual state for completeness with respect to IVML concepts. In Section \ref{}, we summarize the findings made during the revision of the reasoner with regard to performance, in particular that further modifications don't apply modify the implementation against already known performance anti-patterns. In Section \ref{sectEvaluation}, we present an evaluation of the actual evaluation with respect to performance incuding different kinds of IVML models. Finally, in Section \ref{sectConclusion} we conclude and provide an outlook to future work. +The \emph{Integrated Variability Modeling Language (IVML)}~\cite{IVML-LS} is a textual variability modeling language providing rather powerful modeling concepts, among them a type system, multiple-inheritance, container types, configuration references, imports, orthogonal annotations (for binding times), quantification constraints, or user-defined constraint functions. This even allows for topological variability, i.e., configuring and reasoning over graph structures~\cite{EichelbergerQinSizonenko+16}. In this document, we discuss the approach and recent state of the reasoning mechanism for IVML and its realization in EASy-Producer~\cite{EichelbergerEl-SharkawyKroeher+14, El-SharkawyKroeherEichelbergerSchmid15}. At its core, the reasoner focuses on translating / creating specifically instantiated constraints for the various IVML concepts and on forward-reasoning, i.e., evaluating the constraints and performing value propagation as much as possible. This allows for performing typical validation and propagation tasks. In summary, the main constributions of this document are: + +\begin{itemize} + \item An IVML-complete reasoning mechanism, i.e., translation and reasoning for a complex, rich and typed variability modeling language. + \item Support for IVML type refinements, i.e., types and polymorphism as known from object-orientation. IVML allows introducing a type hierarchy within a (meta-)model, and so the potential types for a variable can change along the type hierarchy. As types can introduce constraints, the actual constraint set during reasoning may change, i.e., constraints may be added or removed as an effect of a value change. + \item Support for IVML constraint variables, i.e., variables that hold constraints (including sets or sequences) and also can change during reasoning. Likewise, this must be reflected correctly by adjusting the constraint set at runtime. + \item Instantiation of type-based constraints to variable-based constraints as a basis for a subsequent reasoning chain. For such subsequent reasoners, the IVML reasoner provides a solid basis, detailed error messages including the failed instantiated constraints so that a chained reasoner can directly continue with these constraints. We envision for future work, that further reasoning steps may add complementing reasoning functionalities such as identifying a value from narrowing constraints. +\end{itemize} + +This document is structured as follows: Section \ref{sectApproach} introduces the overall approach to reasoning for IVML. Section \ref{sectNotation} introduces the notation that we use to describe the reasoning algorithm, in particular the notation to access (derived) properties of the various IVML concepts. In Section \ref{sectReasoning}, we discuss the top-level algorithms for transforming constraints, reasoning and reacting to value changes / propagation. In Section \ref{sectTranslation}, we detail the instantiation and translation of constraints for individual configuration settings. The re-scheduling of constraints due to changing value types or constraints is discussed in Section \ref{sectTopLevelConstraintsRescheduling} as the respective algorithm relies on the constraint translation algoithms introduced before. In Section \ref{sectCompleteness}, we analyze the effect translations in order to assess the actual state for completeness with respect to IVML concepts. In Section \ref{sectEvaluation}, we present an evaluation of the actual evaluation with respect to performance incuding different kinds of IVML models. In Section \ref{sectPerformance}, we summarize the findings made during the revision of the reasoner with regard to performance, in particular that further modifications don't apply modify the implementation against already known performance anti-patterns. Finally, in Section \ref{sectConclusion} we conclude and provide an outlook to future work. %----------------------------------------------------------------------------------------------------------------- @@ -126,5 +133,5 @@ \subsubsection{Variable Declarations} -An IVML \emph{variable declaration} $d$ specifies a variable with $name(d)$ and $type(d)$.~$default(d)$ is an expression specifying the default value of $d$, whereby $default(d)$ must evaluate to a type compatible with $type(d)$. Further, $parent(d)$ is the model element the declaration $d$ is nested within, typically, a compound or a project. Moreover, $annotations(d)$ denotes the set of (orthogonal) IVML annotation (variable) declarations for $d$. +An IVML \emph{variable declaration} $d$ specifies a variable with $name(d)$ and $type(d)$.~$default(d)$ is an expression specifying the default value of $d$, whereby $default(d)$ must evaluate to a type compatible with $type(d)$. Further, $parent(d)$ is the model element the declaration $d$ is nested within, typically, a compound or a project. Moreover, $annotations(d)$ denotes the set of (orthogonal) IVML annotation (variable) declarations for $d$ and $isAnnotation(d)$ returns whether a variable declaration is an annotation. For an arbitrary model element $e$ (including type definitions, projects and variable declarations), $parent(e)$ returns the parent model element and $isAssngBlock(e)$ returns whether $e$ is an assignment block. \subsubsection{Configuration Variables}\label{sectNotationConfigVars} @@ -349,9 +356,9 @@ The reasoner performs forward reasoning, i.e., it identifies relevant constraints (according to the reasoning mode), translates the constraints, evaluates them in a loop until all constraints are processed and adjusts/extends the constraint set upon variable value changes. Figure \ref{figStructure} shows the call graph of the reasoner algorithms and the sections where we will discuss them in more detail. Some algorithms call others recursively due to the potentially recursive structure of some IVML types, in particular compounds and containers. Algorithm \ref{algAddConstraint} and \ref{algComposeExpression} appear disconnected, but are called by most of the translation algorithms to populate the constraint base and to compose complex constraints from recursive nesting of containers and compounds. -This section introduces the top-level reasoning algorithms, in particular the main reasoning loop in Section \ref{sectTopLevelMainReasoningLoop}, the global variable mapping structure used during the translation in Section \ref{sectVarMapping}, the top-level constraint translation in Section \ref{sectTopLevelConstraintsTranslation}, the top-level constraint evaluation in Section \ref{sectTopLevelConstraintsEvaluation} and the re-scheduling of constraints while evaluation in Section \ref{sectTopLevelConstraintsRescheduling}. The algorithms for constraint translation will be discussed in detailed in Section \ref{sectTranslation}. +This section introduces the top-level reasoning algorithms, in particular the main reasoning loop in Section \ref{sectTopLevelMainReasoningLoop}, the global variable mapping structure used during the translation in Section \ref{sectVarMapping}, the top-level constraint translation in Section \ref{sectTopLevelConstraintsTranslation}, the top-level constraint evaluation in Section \ref{sectTopLevelConstraintsEvaluation}. The algorithms for constraint translation will be discussed in detailed in Section \ref{sectTranslation} and the algorithms forrRe-scheduling of constraints during evaluation in Section \ref{sectTopLevelConstraintsRescheduling}. \begin{figure}[ht] \center -\includegraphics[scale=0.40]{figures/structure.eps} +\includegraphics[scale=0.80]{figures/structure.eps} \caption{Structuring blocks, algorithms and sections.} \label{figStructure} @@ -360,5 +367,5 @@ \subsection{Main Reasoning Loop}\label{sectTopLevelMainReasoningLoop} -The main reasoning loop implements the overall control for the IVML reasoning process. First, Algorithm \ref{algMainLoop} sets up\footnote{In the implementation, also the re-scheduling of changed variables (Algorithm \ref{algVarChange} in Section \ref{sectTopLevelConstraintsRescheduling}) and recording assigned variables are registered with the expression evaluator, but this is not shown here.} the expression evaluator in line \ref{algMainLoopSetupEval} for use with the configuration $cfg$ and the scope assignments $\scopeAssignments$. The remainder of the algorithm is separated into two parts, 1) the full execution (lines \ref{algMainLoopFullStart}-\ref{algMainLoopFullEnd}), and 2) the incremental part (lines \ref{algMainLoopIncStart}-\ref{algMainLoopIncEnd}) utilizing a constraint base prepared and stored while running the first part. +The main reasoning loop implements the overall control for the IVML reasoning process. First, Algorithm \ref{algMainLoop} sets up\footnote{In the implementation, the listener for changed variables triggering constraint re-scheduling (Algorithm \ref{algVarChange} in Section \ref{sectTopLevelConstraintsRescheduling}) as well as recording of assigned variables are registered with the expression evaluator. These details are omitted here.} the expression evaluator in line \ref{algMainLoopSetupEval} for use with the configuration $cfg$ and the scope assignments $\scopeAssignments$. The remainder of the algorithm is separated into two parts, 1) the full execution (lines \ref{algMainLoopFullStart}-\ref{algMainLoopFullEnd}), and 2) the incremental part (lines \ref{algMainLoopIncStart}-\ref{algMainLoopIncEnd}) utilizing a constraint base prepared and stored while running the first part. \begin{algorithm}[H] @@ -519,24 +526,4 @@ Finally, Algorithm \ref{algEvalLoop} checks for a potential timeout in line \ref{algEvalLoopTimeout} comparing the global $startTime$ set in Algorithm \ref{algMainLoop} with a configured reasoning timeout. If a timeout occurred (not further detailed in this document), the global $hasTimeout$ flag is set to $true$. This information is particularly relevant for creating the overall reasoning report as explained for Algorithm \ref{algMainLoop}. -\subsection{Constraint Re-scheduling}\label{sectTopLevelConstraintsRescheduling} - -When variable $v$ is changed as side effect of a constraint evaluation during reasoning, Algorithm \ref{algVarChange} is called. If the changed variable is not local, i.e., neither a parameter of a user-defined function, an iterator of a container operation nor a local variable defined in a let-expression, the variable is relevant for re-scheduling. First, Algorithm \ref{algVarChange} registers in lines \ref{algVarChangeScopeStart}-\ref{algVarChangeScopeEnd} the change of $v$ within the actual project scope (\TBD{correct? also \IVML{DEFAULT}? Test case needed!}) if the value of $v$ actually has been affected by reasoning. This scope information is used by the evaluator prior to a variable assignment to check for illegal duplicate assignments within the same scope. Then all known constraints (\MISSING{dynamic value type changes}) for a variable are identified and become subject to re-scheduling. The identification includes both, parent (line \ref{algVarChangeRescheduleParents}) and nested (line \ref{algVarChangeRescheduleNested}) variables, which is in particular relevant to capture all relevant constraints for variables in compound and container values. These constraints are appended to the constraint $base$, not adding an individual constraint if it is already scheduled in the constraint $base$. - -\begin{algorithm}[H] - \SetAlgoLined - \KwIn{decision variable $v$, old value $val$} - \KwData{scope assignments $\scopeAssignments$, relevant constraints $\relevantConstraints$} - - \If{$\neg isLocal(v)$}{ - \If{$state(v) == \IVML{DERIVED}$}{\label{algVarChangeScopeStart} %addScopeAssignment - $\scopeAssignments \assng \scopeAssignments \cup \set{v}$\; - }\label{algVarChangeScopeEnd} - \MISSING{change constraints if dynamic value type changes}\; - $base \assng base \addSeqNoDupl \seqWith{\relevantConstraints[p]}{p\in allParents(v)}$\; \label{algVarChangeRescheduleParents}%constraintsForParent - $base \assng base \addSeqNoDupl \seqWith{\relevantConstraints[n]}{n\in allNested(v)}$\; \label{algVarChangeRescheduleNested}%constraintsForParent -% $base \assng base \addSeqNoDupl \bigcup_{c\in alNested(v)}\relevantConstraints[c]$\; \label{algVarChangeRescheduleNested}%constraintsForChilds, nested geht für alle variablen - } - \caption{Adjusting the constraint base (\IVML{notifyChanged}).}\label{algVarChange} -\end{algorithm} \section{Constraint translation}\label{sectTranslation} @@ -569,5 +556,5 @@ For a $v$ of compound or container type, Algorithm \ref{algTranslateDeclaration} dispatches to the other algorithms constituting the reasoner as we will discus in the following sections. Then the patterns can also be applied for initializing compound slots. As a consequence, Algorithm \ref{algTranslateDeclaration} may be called recursively with an incrementally constructed access expression $ca$ that is prefixed before the right side, e.g., let $c$ be the top-level variable of compound type, then $ca=c$ and the pattern $\patternDerivation{v}{ca.v = deflt}$ becomes $c.v=deflt$. In particular in such recursive calls, occurrences of other variables in $deflt$ recorded in $\variableMapping$, e.g., other slots as well as \IVML{self} denoting the actual compound must be substituted properly, i.e., the result is at least $c.v=\varSubstitution{deflt}{\IVML{self}, \variableMapping}$. -In more detail, Algorithm \ref{algTranslateDeclaration} first declares some local variables in line \ref{algTranslateDeclarationDecl}, including the actual type $t$ (to be overridden by the type of the default value expression if needed), the default value expression $dflt$, the actual set of default constraints ($\defaultConstraints$ or $\deferredDefaultConstraints$) to be utilized for adding the final constraint and the actual value of self $s$ (for compound types only). Then, if $t$ is a derived data type, constraints are translated and collected through Algorithm \ref{algTranslateDerivedDatatypeConstraints}. In non-incremental mode, i.e., we translate default value expressions to assignment constraints as well as the default constraints for annotations can then be translated using \ref{algTranslateAnnotationDeclarations}. Due to potential type interferences with derived types, we determine then the actual type through the type of the default value expression if defined. %parasplit +In more detail, Algorithm \ref{algTranslateDeclaration} first declares some local variables in line \ref{algTranslateDeclarationDecl}, including the actual type $t$ (to be overridden by the type of the default value expression if needed), the default value expression $dflt$, the actual set of default constraints ($\defaultConstraints$ or $\deferredDefaultConstraints$) to be utilized for adding the final constraint and the actual value of self $s$ (for compound types only). Then, if $t$ is a derived data type, constraints are translated and collected through Algorithm \ref{algTranslateDerivedDatatypeConstraints}. In incremental mode, we can skip all default value expressions as they are already assigned except for constraint variables that must be taken over into the constraint base (line \ref{algTranslateDeclarationDefltUndef}). In non-incremental mode, we translate default value expressions to assignment constraints as well as the default constraints for annotations can then be translated using \ref{algTranslateAnnotationDeclarations} (line \ref{algTranslateDeclarationAnnotationDefault}). Due to potential type interferences with derived types, we determine then the actual type through the type of the default value expression if defined. %parasplit \begin{algorithm}[H] @@ -578,5 +565,7 @@ $t \assng type(d)$; $dflt \assng default(d)$; $f \assng \undef$\; \label{algTranslateDeclarationDecl} $translateDerivedDatatypeConstraints(d, t)$\; \label{algTranslateDeclarationDerivedDatatype} - \lIf{$\neg inc$} { + \uIf{$inc$} { + \lIf{$\neg isConstraint(type(d))$}{$dflt \assng \undef$} \label{algTranslateDeclarationDefltUndef} + }\uElse{ $translateAnnotationDeclarations(d, v, \undef)$ \label{algTranslateDeclarationAnnotationDefault} } @@ -585,5 +574,5 @@ \uIf{$isCompound(t)$}{ $f \assng d$\; \label{algTranslateDeclarationTranslateSelf1} - $translateCompoundDeclaration(d, v, ca, t)$\; \label{algTranslateDeclarationTranslateCompound} + $dflt = translateCompoundDeclaration(d, v, ca, t, dflt)$\; \label{algTranslateDeclarationTranslateCompound} } \uElseIf{$ isContainer(type(d)) $}{ \label{algTranslateDeclarationHasDefault} $translateContainerDeclaration(d, v, ca, t)$\; \label{algTranslateDeclarationTranslateContainer} @@ -591,5 +580,5 @@ \lIf{$ca \neq \undef$}{$s \assng ca$} \label{algTranslateDeclarationTranslateInCompound} }\lElseIf{$inc$}{$ dflt \assng \undef $} - \If{$ deflt \neq \undef $}{ + \If{$ deflt \neq \undef \wedge \neg(isAttribute(d) \wedge isAssngBlock(parent(d)))$}{ \uIf{$isConstraint(type(d))$}{ \label{algTranslateDeclarationTranslateConstraintDefaultStart} $createConstraintVariableConstraint(dflt, s, v)$\; \label{algTranslateDeclarationConstraintVariableConstraint} @@ -609,5 +598,5 @@ If $t$ is a compound type, we set the value of self $v$ to the actual variable declaration $d$ and execute the specific translations for compound types using Algorithm \ref{algTranslateCompoundDeclaration}. If $t$ is a container type, we call \ref{algTranslateContainerDeclaration} instead. Otherwise, if there is a default value expression and reasoning is not in incremental mode, i.e., we shall translate default value expressions to assignment constraints, and if there is a compound accessor, we just have to schedule a replacement of \IVML{self} by the compound accessor. Remaining default constraints are taken over as defined as long as the reasoner is not operating incremental mode as there no default value assignments are needed. -If there is finally a default value expression to be recorded in the constraint base, we have to distinguish whether the actual variable is a constraint variable or an usual variable. In the first case, we apply Algorithm \ref{algCreateConstraintVariableConstraint} (cf. Section \ref{sectConstraintVariables}). In the second case, we turn the default value expression into an assignment expression. However, the accessor creation depends on whether $d$ is an annotation or an usual variable. Then, we substitute \IVML{self} and the actual variable mapping on the complete constraint expression and turn the result into a default constraint. We either either it to $\deferredDefaultConstraints$ if the constraint may override a complete value assignment (\IVML{self} is used referring to another variable in the same compound or $d$ is an overridden slot that may accidentally be overriden by a complex compound value) or in all other cases to the usual default constraints set $\defaultConstraints$. +If there is finally a default value expression to be recorded in the constraint base and $d$ is not an attribute used within an assignment block(\MISSING{explain}), we have to distinguish whether the actual variable is a constraint variable or an usual variable. In the first case, we apply Algorithm \ref{algCreateConstraintVariableConstraint} (cf. Section \ref{sectConstraintVariables}). In the second case, we turn the default value expression into an assignment expression. However, the accessor creation depends on whether $d$ is an annotation or an usual variable. Then, we substitute \IVML{self} and the actual variable mapping on the complete constraint expression and turn the result into a default constraint. We either either it to $\deferredDefaultConstraints$ if the constraint may override a complete value assignment (\IVML{self} is used referring to another variable in the same compound or $d$ is an overridden slot that may accidentally be overriden by a complex compound value) or in all other cases to the usual default constraints set $\defaultConstraints$. \subsection{Derived types}\label{sectDerivedTypes} @@ -660,9 +649,9 @@ Algorithm \ref{algTranslateCompoundDeclaration} collects and translates the constraints for a compound variable $v$ with declaration $d$, potential compound accessor $ca$ and (default value) type (or $type(d)$ if no default expression is defined for $d$). No translation happens if type $t$ was already processed, e.g., in case of recursive compound types. The types are related by $type(d) = type(v) \in allRefines^+(t)$. Algorithm \ref{algTranslateCompoundDeclaration} creates a context frame and pushes it onto the variable mapping stack $\variableMapping$. Used types are registered only if there is no variable $v$ given, e.g., we process constraints according to a potentially recursive type structure. If a variable $v$ is given, the nested variables are initialized correctly, in particular recursively nested variables terminate correctly based on configured values, i.e., we do not have to take care of recursion in this case. -The main two steps are detailed in Algorithms \ref{algRegisterCompoundMapping} and \ref{algTranslateCompoundContent} as both Algorithms are reused with different arguments during the translation of compounds in Section \ref{sectCompoundDefaults}. Algorithms \ref{algRegisterCompoundMapping} registers all compound slots and annotations in the variable mapping, using $ca$ or $d$ as basis for access expressions for slots and annotations and casts to the type of the actual value in $v$ if available (else $\undef$ is passed in as argument). Now Algorithm \ref{algTranslateCompoundContent} can translate the entire compound content including slots, annotations, constraints, annotation-blocks and eval-blocks. Finally, Algorithm \ref{algTranslateCompoundDeclaration} pops the context frame for this compound from $\variableMapping$. +The main two steps are detailed in Algorithm \ref{algRegisterCompoundMapping} and \ref{algTranslateCompoundContent} as both Algorithms are reused with different arguments during the translation of compounds in Section \ref{sectCompoundDefaults}. Algorithm \ref{algRegisterCompoundMapping} registers all compound slots and annotations in the variable mapping, using $ca$ or $d$ as basis for access expressions for slots and annotations and casts to the type of the actual value in $v$ if available (else $\undef$ is passed in as argument). Now Algorithm \ref{algTranslateCompoundContent} can translate the entire compound content including slots, annotations, constraints, annotation-blocks and eval-blocks. As the context with the compound mapping is only valid during Algorithm \ref{algRegisterCompoundMapping}, default value expressions must be translated within the actual context, i.e., if $deflt$ has been passed in, lines \ref{algTranslateCompoundSubstStart}-\ref{algTranslateCompoundSubstEnd} perform the respective substitution, which will be returned as result of Algorithm \ref{algRegisterCompoundMapping}. Finally, Algorithm \ref{algTranslateCompoundDeclaration} removes the actual context frame for this compound from $\variableMapping$. \begin{algorithm}[H] \SetAlgoLined - \KwIn{declaration $d$, variable $v$, compound access $ca$, default value type $t$} + \KwIn{declaration $d$, variable $v$, compound access $ca$, default value type $t$, constraint $dflt$} \KwData{constraints $\otherConstraints$, variable mapping $\variableMapping$} @@ -673,6 +662,10 @@ $registerCompoundMapping(t, ca, e, type(value(v)))$\; $translateCompoundContent(d, v, t, ca)$\; + \If{$dflt \neq \undef$} { \label{algTranslateCompoundSubstStart} + $dflt \assng \varSubstitutionSelfVarMapping{dflt}{d}$ + }\label{algTranslateCompoundSubstEnd} $popContext(\variableMapping)$; } + \Return{$dflt$} \caption{Translating compound declarations (\IVML{translateCompoundDeclaration}).}\label{algTranslateCompoundDeclaration} \end{algorithm} @@ -1034,4 +1027,25 @@ %\end{algorithm} +\section{Constraint Re-scheduling}\label{sectTopLevelConstraintsRescheduling} + +When variable $v$ is changed as side effect of a constraint evaluation during reasoning, Algorithm \ref{algVarChange} is called. If the changed variable is not local, i.e., neither a parameter of a user-defined function, an iterator of a container operation nor a local variable defined in a let-expression, the variable is relevant for re-scheduling. First, Algorithm \ref{algVarChange} registers in lines \ref{algVarChangeScopeStart}-\ref{algVarChangeScopeEnd} the change of $v$ within the actual project scope (\TBD{correct? also \IVML{DEFAULT}? Test case needed!}) if the value of $v$ actually has been affected by reasoning. This scope information is used by the evaluator prior to a variable assignment to check for illegal duplicate assignments within the same scope. Then all known constraints (\MISSING{dynamic value type changes}) for a variable are identified and become subject to re-scheduling. The identification includes both, parent (line \ref{algVarChangeRescheduleParents}) and nested (line \ref{algVarChangeRescheduleNested}) variables, which is in particular relevant to capture all relevant constraints for variables in compound and container values. These constraints are appended to the constraint $base$, not adding an individual constraint if it is already scheduled in the constraint $base$. + +\begin{algorithm}[H] + \SetAlgoLined + \KwIn{decision variable $v$, old value $val$} + \KwData{scope assignments $\scopeAssignments$, relevant constraints $\relevantConstraints$} + + \If{$\neg isLocal(v)$}{ + \If{$state(v) == \IVML{DERIVED}$}{\label{algVarChangeScopeStart} %addScopeAssignment + $\scopeAssignments \assng \scopeAssignments \cup \set{v}$\; + }\label{algVarChangeScopeEnd} + \MISSING{change constraints if dynamic value type changes}\; + $base \assng base \addSeqNoDupl \seqWith{\relevantConstraints[p]}{p\in allParents(v)}$\; \label{algVarChangeRescheduleParents}%constraintsForParent + $base \assng base \addSeqNoDupl \seqWith{\relevantConstraints[n]}{n\in allNested(v)}$\; \label{algVarChangeRescheduleNested}%constraintsForParent +% $base \assng base \addSeqNoDupl \bigcup_{c\in alNested(v)}\relevantConstraints[c]$\; \label{algVarChangeRescheduleNested}%constraintsForChilds, nested geht für alle variablen + } + \caption{Adjusting the constraint base (\IVML{notifyChanged}).}\label{algVarChange} +\end{algorithm} + \section{IVML-Completeness}\label{sectCompleteness} @@ -1247,4 +1261,19 @@ \pagebreak + +%----------------------------------------------------------------------------------------------------------------- + +\section{Evaluation}\label{sectEvaluation} + +\TBD{Keep or remove that section. However, some basic performance evaluations should not be so difficult. All executions need multiple runs, in particular to even out JIT compilation. It seems that this is done during/after the second reasoning run. Potential topics: + +\begin{itemize} + \item Artificial models of some size/variable/constraint ratio. Christian had a generator for that and Roman typically did some evaluations using these models. Compare to known results where available. + \item QualiMaster full, incremental, runtime reasoning (full, no defaults, no frozen, reuse constraint base). Runtime vs. full reasoning seems to behave rather linearly, at around 23 constraints evaluated per ms. Compare to known results where available. + \item All test cases involving reasoning as an overview map. + \item Eclipse 4.7/Java9 runs tests with asserts!!! +\end{itemize} + +} %----------------------------------------------------------------------------------------------------------------- @@ -1271,16 +1300,4 @@ There are still opportunities for further speeding up the reasoning operations. On an Intel core i7, the reasoner reaches around 15-43 constraint evaluations in average per millisecond - runtime vs. full reasoning on the latest QualiMasster test model, currently reasoning time includes translation and evaluation time \TBD{Sepearte timing}. This is already an improvement over the initial version, which operated at around 10 evaluations per millisecond in average (also with a higher number of constraint evaluations due to unneeded and uneffective constraints). The constraint evaluation time probably suffers from the immutable structured values in EASy-Producer, which are created for each assignment. Knowing that most of the assignments in this model are done for basic IVML datatypes, a fast track for setting integer, double, boolean and String values could increase the number of evaluations, but requires careful extension, as changing values shall only be allowed via decision variables, which take care of the current assignment state, e.g., \IVML{FROZEN}. -\section{Evaluation}\label{sectEvaluation} - -\TBD{Keep or remove that section. However, some basic performance evaluations should not be so difficult. All executions need multiple runs, in particular to even out JIT compilation. It seems that this is done during/after the second reasoning run. Potential topics: - -\begin{itemize} - \item Artificial models of some size/variable/constraint ratio. Christian had a generator for that and Roman typically did some evaluations using these models. Compare to known results where available. - \item QualiMaster full, incremental, runtime reasoning (full, no defaults, no frozen, reuse constraint base). Runtime vs. full reasoning seems to behave rather linearly, at around 23 constraints evaluated per ms. Compare to known results where available. - \item All test cases involving reasoning as an overview map. - \item Eclipse 4.7/Java9 runs tests with asserts!!! -\end{itemize} - -} %-----------------------------------------------------------------------------------------------------------------