[qvtd-dev] To One Regions in Practice

[Ed Willink <ed@xxxxxxxxxxxxx>]

Hi

I have made sufficient progress on exploiting to-one regions to report progress so far:

Adolfo's entire example2 schedule is below. I will explain the details piecemeal.



Small Inner rectangles are Class/PropertyDatums.
Larger rectangles potentially correspond to mappings with inner mapping calls nested.

Small rectangles
- blue - predicated, loaded from input, pre-assigned
- green - realized by the mapping
- cyan - predicated, realized somewhere else
- very thick borders, a distinct head from which other nodes are to-one navigable
- thick borders, ClassDatums
- thin borders, PropertyDatums

Edges
- blue - predicated, loaded from input, pre-assigned
- green - assigned by the mapping
- cyan - predicated, assigned somewhere
- orange - binding (one to one copy)
- magenta - iteration

Property edges are labelled with the name and multiplicity. (Opposites are drawn separately - none in this example).

Each mapping is analyzed to identify its distinct inputs (heads).



is derived from

map cClassCS_2_Class in classescs2as_qvtp_qvtias
{
    check leftCS(classCS : ClassCS) {}
    enforce rightAS() {
        realize class : Class
    }
    where () {
        classCS.ast := class;
    }
}

and has the trivial ClassCS head from which the realized variable is to-one navigable.

Slightly more interesting



is derived from

map uClass_name in classescs2as_qvtp_qvtias
{
    check leftCS(classCS : ClassCS) {}
    enforce rightAS() {}
    where () {
        classCS.ast.oclAsType(classes::Class).name := classCS.name;
    }
}

This again has a ClassCS head from which ast and name are navigable. The ast node is doubly typed as a consequence of the oclAsType(). The ast node is cyan since the Class must be realized before its name can be assigned. The String is shared since it is used unmodified. The name edge is green since this is the mutation.

More interesting is


derived from

map uClass_superClass in classescs2as_qvtp_qvtias
{
    check leftCS(classCS : ClassCS) {}
    enforce rightAS() {}
    where () {
        classCS.ast.oclAsType(classes::Class).superClass := classCS.ast.oclAsType(classes::Class).lookupClass(classCS);
    }
}

One head is again a ClassCS, from which classCS.ast.oclAsType(classes::Class) is navigable once the ast has been realized. The further superclass edge is assigned.

However lookupClass is an unknown operation that returns a Class from a Class, but we do not know whether it is the same Class, so we have to be pessimitic and make the Class another head. This mapping is therefore double headed and so requires both heads to be valid for invocation. This is not trivial to achieve as for a single headed mapping.

Also interesting is



derived from

map uPackage_ownedClasses in classescs2as_qvtp_qvtias
{
    check leftCS(packageCS : PackageCS) {}
    enforce rightAS() {}
    where () {
        packageCS.ast.oclAsType(classes::Package).ownedClasses :=
        packageCS.ownedClasses.ast.oclAsType(classes::Class)->asOrderedSet();
    }
}

Expanding packageCS.ownedClasses.ast.oclAsType(classes::Class)->asOrderedSet(), we get
packageCS.ownedClasses->collect(«internal» : ClassCS : ast.oclAsType(classes::Class))->asOrderedSet()

packagesCS.ownedClasses is to-one navigable to give us one OrderedSet, but the collect iteration dismantles it to give us something that we don't necessarily fully understand. The iterator therefore becomes another head to reflect the need to know many Classes. However we do know that it is internal, the value is navigable, so we don't need a total model search.

The bottom up scheduling starts by sharing guard conditions amongst all mappings to-one reachable from a shared single head. In this example this finds that


can share a ClassCS head (and classCS.name). the realized Class satisfies the predicated Class, so we can successfully merge behind the shared guard. More generally there can be guard trees.

Two trivial merges is all that bottom up sharing gives us. All the other shared heads are multi-headed.

Further progress requires that we have some source data (introduced as opposed to produced).

A class instance can be introduced in three ways:
- at the root of a model (unless it has an exactly to-one containment relationship)
- as a contained child of a known model element
- as a contained child of a unknown model element (unless it has an exactly to-one containment relationship)

Contained by an unknown model element occurs if the source model uses an extended metamodel with additional containment relationships that were not known at compile-time.

The normal containment case for e.g. PackageCS::ownedClasses : ClassCS can be shown graphically as:


using a blue rather than green border. This has a single PackageCS from which some ClassCS children are introduced.

One of these containment introductions is required for every class used by the head of any region.

The abnormal containment case can be shown graphically as:



with a child class for each class used by any head.

The «root» is the Ecore Resource providing root content as Resource.getContents().

The «others» derives from containment relationships not known at compile time.

The diagram simplifies significantly if classes have a precisely one containment relationship that prohibits their appearance at the root or in unknown containments. It also simplifies if we can make a closed world assumption prohibiting extended metamodels.

Since processing of unknown metamodels requires reflection, the Root Containment is best implemented by dedicated Java code.

The above introduction diagram enables us to start joining the loose ends up, prioritizing all single headed regions into a First Pass region at the left of the original picture. This picks up the simple mappings and allows a nested containment descent. Showing just part of it:



«all» RootCS elements are gathered together from the sole possible source, the model root, or unknown places.

«all» PackageCS elements are gathered together from the additional sources of RootCS.ownedPackages or recursive PackageCS.ownedPackages.

«all» RootCS elements are consumed one at a time by the cRootCS_2_Root mapping and RootCS.ownedPackages containment, and another use off to the right.

The residual multi-headed mappings appear to the right. Three are almost single headed since the iterator is internally navigable. The fourth for superClasses is again single headed since the additional head just ensured that all Class instances were computed in an earlier pass.

More work is needed to generalize the FirstPass and Residue into a sequence of passes.

---

Conclusion.

Consideration of to-one restrictions indeed leaves few genuine scheduling options.

Use of containment regions completely eliminates allInstances, at least in this example.

There are minor choices as to whether to gather «all» elements together before servicing them uniformly, or whether to service each possible source individually.

Bottom up merging should perform aggregation of closely related mappings and so avoid redundant scheduling overheads.

Sharing guards allows the predicate to be evaluated just once.

Internal bindings allows predicates to be satisfied by construction rather than re-evaluated redundantly.

Anyway, the pictures are beginning to look credible. Maybe its time for the guided QVTp to QVTi conversion.

A first attempt at the HSV2HLS recursion looked promising finding an arguably better schedule than our manual one. But I had to change example because a QVTc2QVTu bug lost a dependency. Horacio has now fixed this; thabks.

    Regards

        Ed