Next: 4. Resulting Requirements Up: Großer Beleg XML Query Previous: 2. Foundations and State-of-the-Art Contents

Subsections

3.1 Analysis
3.2 Design
- 3.2.1 Type Information Component
- 3.2.2 XMI Parser
3.3 Implementation
- 3.3.1 Requirements
- 3.3.2 Operations with Side Effects
3.4 Tests
- 3.4.1 Tests Using the Royloy Example Model
  - 3.4.1.0.1 Testing the Type Information Component.
  - 3.4.1.0.2 Testing the XMI Parser.
- 3.4.2 Stress Test for the Type Information Component.
  - 3.4.2.0.1 Attribute Ambiguities.
  - 3.4.2.0.2 Method Ambiguities.

3. Type Information Component for OCL

This chapter describes the problem I solved for verification of XML-QL. It describes the problem in detail, so the reader can understand the difficulties I found during implementation.

3.1 Analysis

The type information component is a part of the OCL compiler developed by Frank Finger. The compiler does some type checking on OCL constraints. Therefore it needs information from the model. The compiler supplies a java interface, which the type information component has to implement. Up to this point, there was only an implementation featuring a hard-wired example model. The component developed here enables the OCL compiler to process OCL constraints on arbitrary models given in XMI.

3.1.1 Interface

This is the interface, as given by the OCL compiler. For further details see [FF] package tudresden.ocl.check.types.

ModelFacade

represents a whole model, with all its classes, datatypes and relationships. The information is extracted from a XMI file.

interface ModelFacade
{
Any getClassifier(String name);
}
getClassifier: retrieves an object from the model, representing a class/datatype with the given name. This object is subject to further queries, covering the details of this class. By implementing the interface Any, the object makes these queries available.

Any

specializes Type, that it is a non-collection type. All methods of this interface are inherited from Type.

interface Any extends Type
{
}

Collections use Any as their element type, since this must be a non-collection type. (Nested collections are automatically flattened in OCL.)

Type

represents a arbitrary type of the type information model. It may be a class, a basic datatype or a collection of those.

interface Type
{
  boolean conformsTo(Type type);
  Type navigateQualified(String name, Type[] qualifiers);
  Type navigateParameterized(String name, Type[] params);
}
conformsTo: checks, whether the type can be an instance of a formal parameter of the given type. For classes this is the transitive closure of the generalization relation being extended to be reflexive.
navigateQualified: queries the class for a structural feature (an attribute or an association partner by its rolename). It returns the object representing the type of this feature. According to [OCL] section 5.4.1. missing rolenames are generated automatically (the class name starting with a lowercase letter). For association partners with multiplicities greater the one, a collection of the partners type is returned. The parameter qualifiers is used for qualified associations. This method cannot be used for operations, even operations without parameters. See section 3.1.4 about potential ambiguities .
navigateParameterized: queries the class for a behavioral feature (an operation). The second parameter specifies the parameter sequence of the requested method. This request is valid only for methods having the isQuery flag set. Methods with return type void are unavailable for OCL. See section 3.1.5 about potential ambiguities.

All queries have to care about inherited features and polymorphism of parameters. This is explained below by example.

Methods navigateQualified, navigateParameterized and getClassifier never return null. Instead they throw an exception, if the queried feature/classifier is not available.

3.1.2 Example

This section explains the interface introduced above in detail using an example model. For the example see figure 3.1.

**Figure 3.1:** Example Model for the Type Interface

3.1.2.0.1 Creating the model.

At first the model has to be created. Using the XMI parser this is achieved by

ModelFacade model=XmiParser.getModel("example.xmi");

3.1.2.0.2 Querying classifiers.

The model is used to get objects representing classes of the model. These objects are subject to further queries.

Type person=model.getClassifier("Person");
Type lecture=model.getClassifier("Lecture");

I suppose similar procedure for all classes of the model to be used below.

3.1.2.0.3 Checking generalizations.

Generalizations beetween classes of the given model are checked with conformsTo.

student.conformsTo(person);
!person.conformsTo(student);
foreignstudent.conformsTo(person); // yes its transitive
student.conformsTo(student); // and reflexive too!

3.1.2.0.4 Querying features.

At first some obvious examples.

lecture.navigateQualified("name", null) ==^3.1
  Basic.STRING^3.2;
lecture.navigateQualified("professor", null) ==
  professor;
lecture.navigateParameterized(
  "isInvolved", { person } ) == Basic.BOOLEAN;

Note that ``professor'' is an implicit rolename as described in [OCL] section 5.4.1. Implicit role names may cause ambiguities. For details see section 3.1.4.

3.1.2.0.5 Multiplicities.

Association ends featuring multiplicities of more than one result in collections.

professor.navigate("lectures")==
new Collection(SET, lecture);

3.1.2.0.6 Inherited features.

The model must find all features of a class. This includes features inherited from super classes.

student.navigate("bornOn")==date;
student.navigate("husband")==person;
student.navigate("getAge", {} )==
Basic.INTEGER;
lecture.navigate("isInvolved", { person } )==
Basic.BOOLEAN;

3.1.2.0.7 Polymorphism.

The model must find operations, even if parameter types are not exactly the same as in the operation definition. For demonstration, the last statement of the paragraph above is slightly modified.

lecture.navigate("isInvolved", { student } )==
Basic.BOOLEAN;
lecture.navigate("isInvolved", { professor } )==
Basic.BOOLEAN;

Note that this may result in ambiguities in method matching. For details see section 3.1.5.

3.1.3 Dissolving Associations

Associations in UML are entities of their own. The type information component dissolves associations into a set of structural features for each class of the association. This section describes the algorithm used to dissolve an association formally. The algorithm closely follows [OCL].

Association.: An association is a tupel of a set of association ends and an association class. The association class is optional.^3.3 The set of association ends must contain at least two members. The associations name is not of interest.
Association End.: An association end is a tupel of the following components: the rolename, the class connected to the association end, the flag isMultiple describing whether multiplicities above one are allowed and the flag isOrdered provided by the model.
Name of an Association End.: The association ends name is the rolename, if provided by the model. Otherwise it is the name of the class, starting with a lowercase letter.

3.1.3.1 Navigation beetween Association Ends.

In a first step, we don't care about association classes.

Type of an Association End.: The association ends type is determined by the following table.

isMultiple	isOrdered	Type
false	-	class
true	false	set of class
true	true	sequence of class

Bags are never generated by the type information model.

Structural Feature of an Association End.: Each association end is represented by a structural feature. The name of the feature is the name of the association end. The type of the feature is the type of the association end.

3.1.3.1.1 Creating features.

For each pair (A,B) of association ends with $A\neq B$ the structural feature representing B is added to the class connected to association end A.

3.1.3.2 Navigation to Association Classes.

The second step makes the association class reachable from the classes connected to association ends.

othersAreMultiple.: For each association end E of an association A, there is a flag othersAreMultiple, which is true, if at least one of the other association ends has the isMultiple flag set:
$othersAreMultiple(E)=\exists e\in A:e\neq E\wedge isMultiple(e)$

3.1.3.2.1 Creating features.

To each class connected to an association end a structural feature is added. The name of the feature is the name of the association class (which is the name of the association) starting with a lower-case letter. The type of the feature is determined by the following table.

othersAreMultiple	Type
false	association class
true	set of association class

3.1.3.3 Navigation from Association Classes.

The third step makes the association ends reachable from the association class.

3.1.3.3.1 Creating features.

For each association end a structural feature is added to the association class. The name of the feature is the name of the association end. The type of the feature is the class connected to the association end.

Note that when navigating from the association class to association ends the model never returns collections, regardless of the association ends multiplicity.

3.1.4 Attribute Ambiguities

An attribute ambiguity occurs, if a classifier has more than one feature of the same name. Consider the following example.

SomeClass has two features called ``anotherClass'':

The attribute ``anotherClass''
The association partner ``AnotherClass'', which is accessible by an implicit rolename ``anotherClass'', as described in section 3.1.3.

According to [OCL], this ambiguity causes both features ``anotherClass'' to be unavailable for OCL.

The same applies to ``AnotherClass''. It has two features ``anotherClass''. Both are implicit rolenames of the reflexive association. Again, this causes both features ``anotherClass'' to be unavailable for OCL.

[OCL] does not specify, whether a subclass may override an ambiguous feature, thus making the feature available again. For example, suppose a subclass ``SubSomeClass'' of ``SomeClass'' having an attribute ``anotherClass''. One could argue about, whether this feature is available for OCL or not. Current implementation of the type information component makes the feature available again, however this could be changed easily.

3.1.5 Operation Matching Ambiguities

Operation matching is a problem to be solved by any compiler. There is a operation call and given set of operations with the same name. The question is, which operation actually gets called.

Suppose a generalizationship of two classes

class ClassA {};
class ClassB extends ClassA {};

and the following model.

class SomeClass
{
operation(ClassA a);
operation(ClassB b);
}

Now lets query for operation(ClassB).

someClass.navigateParameterized("operation", { ClassB } );

According to the interface definition, navigate must care about parameter polymorphism. Thus, there are two operations matching the query: operation(ClassA) and operation(ClassB). Of course the second one matches ``better''.

But its not as easy, as it looks. To explain, the model above is extended.

class SomeClass
{
operation(ClassA a, ClassB b);
operation(ClassB b, ClassA a);
}

The new query

someClass.navigateParameterized("operation",
{ ClassA, ClassA} );

will get the type checker into serious problems. Both operations match to the query, and both match equally well. There is no way to decide, which operation is meant.

The current implementation of the type information component cannot handle either of the queries. Instead, it will generate an exception due to ambiguous operations. More formally:

Operation matching.

An operation definition $(dn,dp_{1},dp_{2},..,dp_{dl})$ matches an operation query $(qn,qp_{1},qp_{2},..,qp_{ql})$ if and only if all subsequent conditions hold:

The operations name matches: $dn=qn$ .
The parameter sequence length matches: $dl=ql$ .
The parameters match: $\forall i\in \left[ 1..dl\right] :qp_{i}.conformsTo(dp_{i})$

Operation ambiguity.

An operation query is ambiguous, if and only if there is more than one operation definition matching the operation query as defined above.

A more sophisticated algorithm could handle at least some of the queries, which are rejected by the current implementation. For an idea see [Java] section 15.11.2.2: CHOOSING THE MOST SPECIFIC METHOD. This has not been implemented for simplicity. Up to now the OCL specification does not specify operation matching in detail.

3.2 Design

This section explains the design of the component I developed. It consists of two parts:

Type Information Component.: The model itself, storing all information needed to handle the queries from the OCL compiler.
XMI Parser.: Creates the model from the information provided by the XMI file.

See figure 3.2 how both parts fit into the architecture of the whole system.

**Figure 3.2:** Architecture of the Type Checking Subsystem

3.2.1 Type Information Component

See the figure 3.3 for an static UML structure of the type information component.

**Figure 3.3:** Design of the Type Information Component

3.2.1.0.1 Model Facade.

At the right there is the interface provided by the OCL compiler. This has been discussed in detail in section 3.1.1.

3.2.1.0.2 Type Information Component.

The classes at the left store the type information and implement the interface ModelFacade to answer the queries from the compiler.

Model: represents a whole Model. It aggregates all classes of the model. It implements the getClassifier() method inherited from ModelFacade by looking up the class with the given name.
ModelClass: represents a class of the model. It knows about its supertypes and aggregates all attributes and operations. ModelClass implements Any, so it is directly responsible for all queries about the class.
ModelAttribute: represents an attribute of a class. It stores the attributes name and its type.
ModelOperation: represents an operation of a class. It stores the operations name, its parameter sequence and its return type. Note that parameters is an ordered association.

3.2.1.0.3 Associations.

It is not possible to store associations explicitly. Instead, associations are dissolved into a set of structural features (attributes) according to section 3.1.3. Dissolving associations is implemented by the method ModelAssociation.dissolve(Model).

3.2.1.0.4 Flattening.

After creating the model structure, there is a final step of flattening the model. This means, that for each class

The set of supertypes is extended to include all indirect supertypes.
The set of attributes is extended to include all inherited attributes, which are not overridden in this class. However, overriding an attribute is considered to be suspect and causes a warning to standard out.
The set of operations is extended to include all inherited operations, which are not overridden in this class. Overriding an operation with a different return type is considered to be suspect and causes a warning to standard out.

After flattening the model, it cannot be modified any longer. The Type Information Component is designed to be created at once, and then used without any further modifications. This simplifies the design significantly and makes better performance possible.

3.2.2 XMI Parser

The parser is essentially a collection of methods, creating the Type Information Component. So there is not much to be designed.

3.2.2.0.1 The XML Parser used.

The XMI parser uses XML4J to parse the XML file. XML4J is provided by IBM for free. XML4J implements the DOM model provided by the W3C. This standardizes the way, a java application accesses a XML file. Thus, the XMI parser does not depend on an interface proprietary to IBM.

3.2.2.0.2 XMI Adapters.

A XMI adapter adapts the parser to different versions of XMI. For the XMI Parser there are two different versions to be distinguished. Both differ in naming of tags and attributes. See the table for details.

Version	OMG	IBM
	Rational Rose XMI Plugin	Argo/UML 0.7
attribute name	xmi.id	XMI.id
attribute name	xmi.value	XMI.value
attribute name	xmi.idref	target
element name	Foundation.Core.Class	Class
element name	Foundation.Core.ModelElement.name	name
element name	Foundation.Core.Generalization	Generalization
element name	Foundation.Core.Generalization.subtype	subtype
... and so on.

Originally, XMI has been developed by IBM. The OMG adopted XMI as a standard representation of UML. Unfortunately, the OMG has prefixed all element names with their packages of the UML specification. This makes XMI documents less readable by humans, more tedious to parse and noticeably larger in size.

3.2.2.0.3 Element Nesting.

There are further differences of the XMI generated by the tools mentioned above. One example is illustrated here.

This is an extract of the XMI structure generated by Argo/UML:

The XMI generated by Rational Rose is different: The two lines put in italics are missing.^3.4

In other words: Argo puts each <Class> element into its own <ownedElement> element, while Rose put all <Class> elements into a single <ownedElement> element.

This problem is solved by defensive programming. The parser simply accepts multiple <ownedElement> elements, each having multiple <Class> elements nested inside.

The table below list all similar cases of different nesting, the author found during implementation. Probably, this list is not complete.

Class	Rolename	Associated Classes
Model	ownedElement	Class, Association, Generalization
Association	connection	AssociationEnd
Class	feature	Attribute, Operation
Operation	parameter	Parameter

3.3 Implementation

This section discusses selected issues of the implementation.

3.3.1 Requirements

The type information component with the XMI parser requires the Java Collections API. Since the OCL compiler does depend on Java Collections too, this is no problem.

Additionally XML4J is needed. It is available at the IBM website. Development and testing was done using version 2.0.15.

The parser was tested with Argo/UML 0.7 and Rational Rose 98sp1 with the Unisys XMI Plugin.

3.3.2 Operations with Side Effects

[OCL] specifies, that OCL expressions may not use operations with side effects. XMI makes this information available by the isQuery element. However, neither Rose or Argo do support setting the isQuery information by the user. Instead, it is set to false for all operations. Therefore the XMI parser ignores it.

3.4 Tests

This section describes the test cases performed on the type information subsystem. There are several tests, some replacing some of the components with test drivers. For understanding, please refer to the type checking subsystem architecture figure 3.2 on page .

3.4.1 Tests Using the Royloy Example Model

The following tests use a model featuring the ``Royalties and Loyalties'' example model. The OCL compiler processes some OCL expressions written by Frank Finger for the example model.

3.4.1.0.1 Testing the Type Information Component.

In this test case the XMI Parser component replaced by a test driver. The test driver directly creates the example model.

3.4.1.0.2 Testing the XMI Parser.

This test case runs the entire system. The XMI Parser creates the example model twice from two XMI documents. The first one was created using Argo/UML 0.7. The second document has been exported from Rational Rose using the Unisys Plugin.

3.4.2 Stress Test for the Type Information Component.

The example model of the tests above does not cover the more subtle problems of the type information component. The model lacks

overriding features
indirect generalizations
attribute ambiguities (see section 3.1.4)
method ambiguities (see section 3.1.5)
different package names.

The stress test features a model covering all these issues. See figure 3.4.

**Figure 3.4:** Stress Test Model

The test case replaces the OCL compiler (see figure 3.2 again) by a test driver querying the Model Facade. This makes more precise testing possible. For failing queries it is additionally checked, whether they fail for the intended reason. Possible reasons for failure are attribute ambiguity, method ambiguity and the simple absence of the feature queried.