QVTd Relation Overriding

The QVT specification has a relatively clear specification that QVTr relation may override, but no clues as to how this is mapped to QVTc that has no overrides concrete syntax, even though it inherits an overrides capability from QVTb.

The eventual solution was easy and unsound so this document is active again:

• QVTr overrides are eliminated by a QVTr2QVTr transformation
  • each no longer overridden relation has a not-when-predicate on each transitively overriding relation
• QVTc, QVTs no change
• run-time Connections support smart dispatching

The remainder of this working document is now obsolete. It considered how overriding might be supported. It takes over from

• https://bugs.eclipse.org/bugs/show_bug.cgi?id=508267 [qvts] Introduce MicroMapping Alternator/Switch
• https://bugs.eclipse.org/bugs/show_bug.cgi?id=515327 [qvtc] Support overrides / refines

Overrides principles

A relation does not execute for a given set of object bindings if a transitively overriding relation executed.

Execution prohibition can be localized:

• each relation has a not when predicate on each overriding possibility
• each top override invoker uses logic to aggregate the statuses of all possible overrides
• non-top relations are converted to top by an additional invocation request instance
• each non-top override invoker requests invocation then uses logic to aggregate the statuses of all possible overrides
• logic is comparatively easy but quadratic
• there is no trace of the dispatch
• needs a contravariant hierarchy of invocation classes and covariant trace classes

Execution prohibition can be centralized (in a dispatcher):

• all override/overridden relations have a request instance which is the externally created trace
• top relations are sequenced by requests from a top dispatcher
• non top relations are sequence by requests from a non-top dispatcher
• relation calls/guards are easy dispatcher is painful
• dispatcher has its own trace
• no invocation classes needed, no trace class inheritance needed
• common predicates can be hoisted into the dispatcher eliminating multi-step synchronous evaluation

Memory/Execution costs

Considering execution of C in A overrides B overrides C with TA, TB, TC trace classes.

Localized

Execution of top C creates a failed TA and a failed TB before a success TC is available for the caller to test TA.success or TB.success or TC.success.

Execution of non-top C additionally creates an AorBorC request before it creates a failed TA and a failed TB before a success TC is available for the caller to test TA.success or TB.success or TC.success.

Centralized

Execution of top C by a top dispatcher D, creates a TD and then a failed TA and a failed TB before a success TC is available for the caller to test as TD.success.

Execution of non-top C by a non-top dispatcher D, creates a TD and then a failed TA and a failed TB before a success TC is available for the caller to test as TD.success.

Summary

The centralized execution incurs an additional mapping execution for the dispatcher . The centralized top execution incurs an additional dispatcher trace.

The centralized execution avoids quadratic code size costs.

The centralized dispatcher provides an opportunity for optimization that can often avoid invoking/tracing bad mappings altogether.

Conclusion

The centralized dispatcher could be a little worse, but offers opportunities to be significantly better.

Once reified into the QVTi Connection, the centralized dispatcher may incur no overheads.

QVTc exposition

The QVTr=>QVTc=>...=>QVTs=>QVTi=>... requires an exposition of the overrides in QVTc.

Using A overrides B overrides C as a working example...

localized

Multiple not-overridden guards are easy. Multiple each override tests are easy. Just quadratically bloated.

mapping A { ... where()
   {... realize ta:TA; realize taorborc:TAorBorC; taorborc.result := ...; ...}}
mapping B { ... where(ta:TA | not ta.success)
   {... realize tb:TB; realize taorborc:TAorBorC; taorborc.result := ...; ...}}
mapping C { ... where(ta:TA, tb:TB | not ta.success and not tb.success)
   {... realize tc:TC; realize taorborc:TAorBorC; taorborc.result := ...; ...}}
mapping NoneOfAorBorC { ... where(ta:TA, tb:TB, tc:TC | not ta.success and not tb.success and not tc.success)
   {... realize tnotaorborc:TNotAorBorC; realize taorborc:TAorBorC; taorborc.result := null; ...}}

--example caller...
   ... where(taorborc:TAorBorC | taorborc.result <> null) ... taorborc.result ...
-- the above assumes that t*.success := true/false is part of the run-time support

Introducing the pseudo-trace TAorBorC result aggregator allows the mappings to contribute to a result avoiding the caller needing to aggregate them.

For more complex cases such as A1 overrides B overrides C, A2 overrides B overrides C an additional aggegator is needed for each or-something-else in the inheritance tree.

centralized

There is a major sequencing challenge for overrides. Considering execution of C in A overrides B overrides C, no attempt to execute the action parts C may occur until A and B have failed. This forces top invocations to be behave s non-top invocations relying on explicit invocation by the dispatcher, which must have an ability to perform multiple waits. A single mapping can wait repeatedly but for only a single complex guard condition.

An earlier consideration of partial relations used multiple partial relations for multiple sequenced waits.

If QVTc had a "if" statement it could be used to provide alternative guards for each outgoing request realize; a language change.

QVTc has composed mappings. Perhaps these can orchestrate the multiple waits. A significant stress to a little used QVTc2QVTm functionality. No, composed mappings are unnamed so they cannot wait for each other. However there could be a child mapping for each node in the inheritance tree guarded by its ancestors then dispatching to the target. Child mappings would therefore wait for each other in so far as one child waits for something that can only happen after another child.

mapping AorBorC {
   mapping /*A*/ { ... where()
       {... realize ta:TA; realize taorborc:TAorBorC; taorborc.success := true; ...}}
   mapping /*B*/ { ... where(ta:TA | not ta.success)
       {... realize tb:TB; realize taorborc:TAorBorC; taorborc.success := true; ...}}
   mapping /*C*/ { ... where(ta:TA, tb:TB | not ta.success and not tb.success)
       {... realize tc:TC; realize taorborc:TAorBorC; taorborc.success := true; ...}}
   mapping /*default*/ { ... where(ta:TA, tb:TB, tc:TC | not ta.success and not tb.success and not tc.success)
       {... realize taorborc:TAorBorC; taorborc.success := false; ...}}
}
mapping B { ... where(tb:TB | ...)
       { ... tb.success := true; ... }}
-- the above assumes that t*.success := false for a guard failure is part of run-time support

QVTc Choices

QVTc refinement syntax is an additive capability and therefore not suitable for implementing the QVTr replacement semantics of QVTr overrides.

We could add overrides syntax and semantics to QVTc, which then passes the buck to QVTi. But since we already need an 'alternator' to dispatch multiple similar but differently predicated mappings efficiently, we may be able to kill two birds with one stone.

QVTc is relatively simple. It solves the mapping sequencing problem by inter-trace class references/dependencies. Can it solve the overrides problem as-is? Let's go with this.

Consideration here led to QVT14-51 advocating the addition of overrides to the QVTc concrete syntax.

QVTr2QVTc Overrides 'Rewrite'

There is a simple rewrite that reifies overrides in QVTc without requiring any new capabilities, although it may stress some existing ones.

Given a transformation comprising Mx mappings/relations, Gx guard functions, and Bx bottom actions:

MA: when { GA(); } BA();
MB overrides MA: when { GB(); } BB();
MC overrides MB: when { GC(); } BC();
MD overrides MA: when { GD(); } BD();

we can rewrite the polymorphs (relations that participate in an overrides hierarchy) as siblings (relations that share a similar structural interface), refined guard functions and dispatchers:

MAsibling: when { GAsibling(); } BA();
MBsibling: when { GBsibling(); } BB();
MCsibling: when { GCsibling(); } BC();
MDsibling: when { GDsibling(); } BD();

GAsibling() = !GBsibling() && !GDsibling() && GA();
GBsibling() = !GCsibling() && GB();
GCsibling() = GC();
GDsibling() = GD();

MAdispatcher: when { GAdispatcher(); } where { MAsibling(); MBsibling(); MCsibling(); MDsibling(); }
MBdispatcher: when { GBdispatcher(); } where { MBsibling(); MCsibling(); }
MCdispatcher: when { GCdispatcher(); } where { MCsibling(); }
MDdispatcher: when { GDdispatcher); } where { MDsibling(); }

GAdispatcher() = GAsibling() || GBsibling() || GCsibling() || GDsibling();
GBdispatcher() = GBsibling() || GCsibling();
GCdispatcher() = GCsibling();
GDdispatcher() = GDsibling();

• introduce Gxsibling() equal to Gx() anded with the Gxsibling()es of all directly overriding relations.
• introduce Mxsibling() equal to Mx() using Gxsibling() to replace the override.
• replace Mx by an Mxdispatcher to all the new siblings

Mxdispatcher and Gxdispatcher can be omitted if there is no direct invocation of Mx.

(The aggregating Gxdispatcher() operations are required to ensure that Mxdispatcher dispatch fails if no override matches.)

Rewrite reification in QVTr2QVTc

We need to synthesize Gx() as a Function/Operation invoked from the Mapping Guard rather than being inlined in the Mapping Guard. All type checks must use explicit oclIsKindOf's since we cannot exploit 'mismatch is predicate fail' semantics within Function/Operations.

Whether Function/Operation should be used to exploit/bypass uniqueness optimizations is unclear. Probably doesn't matter. If QVTi understands what's happening, QVTi can optimize merged invocations behind the uniqueness of the polymorphic dispatcher.

Should relations that are not overridden also have their predicates structured as guard functions?

• pro: a simplification reducing QVTr2QVTc complexity
• pro: sibling mappings are also exposed to QVTi dispatch optimization
• con: increases stress on QVTs deep operation analysis - needs to work anyway
• con: further deviation from RelToCore

2 strong pro's, 2 weak con's => always create guard functions.

A distinct guard function may allow a failed guard to have a distinct and more optimum trace class for incremental update.

In order to avoid recomputing all the intermediate guard/bottom pattern variables the Mxdispatcher's trace class must provide properties to pass context between Gxsibling, Mxdispatcher and Mxsibling. For the degenerate case of no dispatcher the sibling's trace class should serve the same function.

Rewrite reification in QVTc, QVTu, QVTm, QVTs

There should be no change, but deep operation dependency analysis will need to work for QVTs.

But, what about partitioning? Is it necessary to partition guard functions?

Rewrite reification in QVTi / run-time

Nothing necessary, but significant optimizations available.

The dispatch of one or Micromappings from a Connection currently invokes each relevant Micromapping. No change since each synthetic override has full exclusions in its own predicate. However there may be many available Micromappings each with a guard function. These can be hoisted into a dispatcher and CSE applied to dramatically reduce recomputation. Since the failed guard functions are invoked by the dispatcher, the failures do not need to be traced, incremental redispatch from the Connection will redetermine what needs to be done correctly. These optimizations apply to siblings as well as polymorphs.

If we add a QVTi syntax to support the decision tree, the optimized dispatch can work in interpreted as well as code generated execution.

The CSE will need to work on the OCL expressions and so we need to generalize CSE support from CG-only. [1]

It may be helpful to structure the guard functions in disjunctive normal form within a let-variable CSE hierarchy to facilitate partitioning.

Add QVTc Overrides

The alternative to a QVTr2QVTc synthesis is to just propagate the 'overrides' semantic till much later.

Rather than worry about how to partition functions, perhaps the Partitioner could partition the Gx() of each Mx() without ever needing to create the artificial Gx(). We have the flexibility to introduce QVTs/QVTi constructs to directly support the reified semantic rather than contort into standard QVTc whose idioms must be dismantled later.

Both approaches have the same semantic to resolve:

'QVTr2QVTc rewrite' adds unpleasant complexity to the QVTr2QVTc to express predicates overtly as functions so that another layer of functions defines the overrides. QVTs then has to struggle to make sense of the functions.

'Overrides partitioning' just passes 'overrides' through QVTc, then uses the Partitioner to perform the rewrites where rewrites are already performed. The predicates are partitioned as preliminary micromappings and not-success dependencies lock-out the unwanted executions.

In both cases QVTi/Connection synthesis optimizes the treatment of siblings. For the 'QVTr2QVTc rewrite' idiomatic functions need recognition, for the 'partitioner' shared state is possible.

QVTr2QVTc synthesis

The QVTc synthesis is still not easy.

For a polymorphic invocation of the Mxx with a Txx trace, we require a calling signature Sxx containing the RelationCallExp arguments and a Txx for each polymorph. Each Txx is potentially independent since it may have properties with distinct types. Sxx is similarly independent.

The caller creates an Sxx which non-top Txxes depend on. The QVTs partitioner reifies the inter Txx dependencies.

This is fairly easy for a polymorphic where call, since the realized caller can realize an Sxx in addition to realizing its own trace. It might be beneficial to aggregate each Sxx into the caller's trace. Perhaps slightly awkward/bloated for multiple calls of the same relation; but probably an implementation detail that will become clear.

This is not easy for a polymorphic when call, since the caller's trace has yet to be realized and no additional Sxx can be realized either. Promoting a nest of when calls to the root caller solves the nested calls, but the root caller might be a top relation, so again no one can create the Sxx to initiate the dependency. A solution is to split the the caller

MC : when (GC()) BC()

as

MC1 : when (GC1()) where{ MC2() }
MC2 : when (GC2()) BC()

MC1, GC1() verifies all the non-top-when-call predicates and realizes the Sxx for each non-top-when-call. MC2, GC2() use the Sxx created by MC1 to provide the non-top-when-call objects to correctly guard BC().

Any monomorphic or polymorphic non-top-when-call requires the invoking mapping to be two-part. For simplicity, let the first-part trace aggregate each non-top-when-call Sxx. The second-part depends on the Sxx success. An optimization for most cases: the first part trace can inherit each Sxx, more so if Sxx property names are long and so no clashing.

Any polymorphic top-when-call is a lookup so just predicates the Sxx result. A distinct Sxx result must be maintained by each polymorph for each possible top-when invocation. No. A single Sxx result for (each) root polymorphism is sufficient. The derived Sxx results can be deduced from the root. ? cycle hazard: if we wait for the full root polymorphism tree to resolve when we only needed a branch, do we introduce a deadlock hazard? Perhaps the wait for derived Sxx can accurately test for only the required branch.

Any monomorphic top-when-call is a lookup so just predicates the Txx result.

Refined QVTc realized semantics

The above is klunky. While most of the overrides complexity is deferred to the QVTs partitioning, one form of invocation still needs partitioning to be expressed in QVTc. Can we refine the QVTc overrides functionality to defer this too? The problem is that we cannot realize the overrides root early enough. Perhaps a realized overrides is created by the guard/is declared in the guard.

One option is to allow 'realized' variables in the guard to create temporaries need to evaluate the predicates. A bit of a stretch.

Another option is to recognize nested realized variables (composed by another realized variable, e.g. the trace) as speculative temporaries to be created and populated in time for use by the predicate evaluation. A bit cute but no actual change. The temporaries become non-orphans once the predicates have passed.

What if we completely ignore the inadequate polymorphism of the QVTc trace class, then we can completely ignore polymorphism in QVTc except for the 'overrides' clause. The partitioner now realizes all the semantics, including the synthesis of a polymorphism-friendly variant of the trace model. Moving the trace synthesis from QVTr2Trace to QVTs has many advantages. QVTs is much closer to where we might optimize away dead trace properties. For QVTr we defer GenModeling till after initial conversions have succeeded. For QVTc (and QVTr) the early trace is just an Ecore model, which the optional code greneration reifies as Java. For interpreted execution it might remain dynamic.

Too simple. A where call can happily create a signature class instance, fully populate it and leave it to sort itself out. A when call requires the caller to create the signature class instance, half populate, then wait for external progress, test the result and proceed. Not impossible but highly irregular. A relation with non-top when calls must map to a when caller mapping for each non-top when call followed by the real mapping that responds once all whens have behaved satisfactorily.

If the initial trace model that the QVTc references is just simplistic, perhaps there is a case for adding OCLinEcore package/class syntax to QVTc and/or QVTr. Success status/opposite roles etc might then be available automatically.

A residual complexity arises with the Sxx instance necessary to avoid quadratic complexity on non-top when/where calls. Having removed the need for overrides variants the quadratic is much less serious. Let's make it simpler. If it becomes embarrassing maybe QVTc can have a less obfuscated when/where syntax.

Calling mechanism

A relation Mx() comprises

• guard predicates GMx()
• bottom actions AMx()
• trace class TMx.

The guard predicates comprise

• conformance checks CMx()
• preconditions (when) PMx().

The bottom actions comprise

• realization and assignments RMx()
• sequel (where) invocations SMx()

Overall we might have in Java terms

boolean Mx() {
   Tx trace = new TMx();
   boolean status = CMx() && PMx(); // May be many CM, PM
   if (status) {
       RMx();  // May be many RM
       SMx();  // May be many SM
   }
   trace._success = status;
   return status;
}

QVTc has no support for mapping calls, just trace dependencies that use TMx._success.

where calls

If SMx() in Mx() calls My():

We can per-Mx variants of My with a reference to TMx._success as a Py. This incurs a potentially quadratic code size cost.

We can avoid the quadratic cost if Mx() creates a SMy signature as a TMx property. My() then has a Py referencing a SMy.

A where invocation of a top relation is an error; top relations are invoked by matching objects alone.

A where invocation of a non-top relation My() by Mx() requires

• an SMy signature class
• Mx() creates and populates an SMy as an Rx() bottom action
• My() depends on an SMy as a Py() guard predicate

when calls

If Px() in Mx() calls My() and Px() in Mx() calls Mz(), we must evaluate all Gy() and Gz() before any B(y) or Bz() executes.

A when invocation by Mx() of a top relation My() is lookup top relations are invoked by matching objects alone.

• the when invocation just references TMy._success as part of a Px.

A when invocation by Mx() of a non-top relation My() is a conditional nested dependency.

• an SMy signature class
• the Mx() is partitioned into GMx() and BMx()
• the My() is partitioned into GMy() and BMy()
• CMx() is realized by CGx()
• The PMx() when calls are realized by creation of SMy instances in BGx()
• The PMx() when returns are realized by SMy._success testing in PBx()
• The AMx() actions are realized by ABx()
• Gx() create and populate an SMy as an Rx bottom action
• My() depends on an SMy as a Py() guard predicate
• My() returns to SMy as a Ry() bottom action

conclusion

The QVTr2QVTc synthesis must be prepared to split Mx() into Gx() and Bx(). Once a Gx() is available providing the overrides predicates is not much harder.

top when/where calls

top relations do not need invocation, so what does it mean to invoke them?

For top-when calls, the call is just a possibly polymorphic lookup.

Perhaps for fixed point execution a top-where call might provoke an execution on some internally created objects that would not otherwise occur. But the internally created objects must be in the input domain, so execution occurs. The option to declare that a domain uses another domain allows output into another domain to contribute to the input. top-where calls therefore seem to be a semantic error.

when/where call hierarchy

Each where is a then-do-this, which has no reverse influence on the caller, so can just dangle off as a dependency. Multiple where's may repeat arguments in difficult to predict fashion, so there is little point attempting any folding. If a where invokes a when, then that is a pre-requisite of the independent activity; no new problems.

Conclusion: where flattening is not necessary and could be bad.

However a hierarchy of when's may form a cycle. This is not a problem from the final truth perspective but it may be challenging to find an intermediate truth. Since all when's must be consistent (might be when {A() and not B()}) for the root call to be satisfied, flattening the when's might eliminate the loops, but flattening might obfuscate the uniqueness of each non-top when invocation.

Hypothesis: the when call outputs (other than the status) cannot be used within the when cycle.

Hypothesis: the invoking trace instance is part of the uniqueness of a non-top-when, therefore a non-top-when can only repeat for degenerate code such as when { A() and A() }.

Therefore non-top-when predicates should be flattened into the caller. But preserving their logic so that when { if A() then B() else C() endif; } does not spuriously depend on unguarded B() or C().

Hypothesis: a non-top when cannot invoke its caller to form a cycle.

Consider a Fibonnaci tx from Seq{1..N} to Seq(Fib(1)..Fin(N)}. Each relation has a guarded double when on predecessors, so Fib when-calls Fib with distinct arguments, but we need a simple symbolic analysis to prove it. A mis-coded Fib could easily loop forever; no surprise there is no panacea for rubbish code. The correctly coded recursion cannot be flattened, but is probably a top when call so not a problem anyway.

Conclusion: non-top when flattening is not necessary and could be bad.

But:

top MA : when (MB()) BA()
top MB : when (MA()) BB()

can only be executed if we flatten to

top MAB : when (true) BA(); BB();

or we rely on speculation to fix it as it should.

Conclusion: top when flattening might be good / might be bad. Speculation should work if not flattened.

Signature class

An Sxx signature class instance is required for every non-top when or where call. It provides the critical predicate that communicates the RelationCallExp arguments to the non-top relation.

An Sxx signature class instance is also required for each distinct polymorphic invocation of top when calls. (Top where calls are erroneous.)

The class comprises

• one property for each invoked Relation parameter. For when-calls the enforced domain properties may be 'output's.
• a status for each polymorph wrt the polymorphism root
• a caller, if the invoked Relation is non-top

The polymorphism root is the least overridden relation in the overrides hierarchy that is explicitly invoked. If this is not actu The status is three-valued

• true=success
• false=fail
• null=not-ready.

For when calls the status that may participate in trivial or complex predicates.

Distinct instances are required for when and where calls; rather unlikely but not necessarily invalid.

For invocations below the root of the polymorphism, the reduced polymorphic result may be deduced from a subset of the statuses.

A distinct failure status is required for each polymorph so that the chain of failures can eventually enable a partially overridden relation to succeed.

What about multiple successes? If a polymorphic when-call invokes multiple non-orthogonal overrides, there can be multiple results! The transformation is a statement of final truth, each of the multiple results is a truth, so we must treat a polymorphic when-call as an iteration over the potentially many results.

Optimization: the Sxx may be merged with the calling trace for the common case that the caller invokes at most one non-top when and all invoked when's/where's are invoked solely by the one caller.

Connection dispatching

Must accommodate an iteration over multiple polymorphic results.