The Orthogonality Validation Tool


Multidimensional models rely on the property of orthogonality for consistency. The term orthogonality describes also an oppositional relationship: two abstractions influencing each other, such that composition of either abstraction is identical to the composition of other.

Multidimensional AHEAD models allow us to simultaneously decompose a problem along multiple abstractions (dimensions). One of the tenets of this approach is the ability to synthesize software modules that capture different design viewpoints or perspectives. This rests on a fundamental assumption: different projections of the code-base should be consistent. If they are inconsistent, then the abstractions are not defined to be balanced, and we may obtain decompositions that represent different programs. Likewise, any edits that we perform on a view may not correspond to correct functionality in another view. Stated differently, to produce consistent views of a multidimensional code-base and allow programmers to edit these views, the underlying multidimensional model implementation must satisfy the orthogonality property: the same program will be produced when matrix dimensions are summed in any order.

The orthotest tool was created in response for automated tool support to ensure orthogonality of product-lines.

Orthogonality Validator reports any implementation level dependencies between features located at diagonals on the MDM model matrix. (See Sahil’s Master Thesis on AHEAD publications webpage for more details.)

The following tool is a stand-alone command line utility for invoking Orthogonality Validator. Programmatic invocation is also possible with some minor modifications (look at what the main method does in the source code).


         Overview

         PLM File Format

         Bytecode Compilation

         Command-Line Invocation

         Failure Details

 

Overview

This stand alone version of Orthogonality Validator requires the product line matrix file (.plm), a model grammar file for the multidimensional model (.m), and a compiled directory structure of all layers (see compilation instructions). It supports only multidimensional models (so don’t complain on any errors with single-dimensional models). Multidimensional models are defined in a Product Line Matrix (.plm) file (see its format below).

The most basic scenario of usage is by designing a multidimensional model:

  1. Write the product-line model file (foo/foo.m) such that terminals in the grammar refer to units of dimensions (not layer directories themselves)
  2. Write the PLM file (foo.plm) describing dimensions, units, and layers that each coordinate maps to.
  3. Generate layer directory structure (foo/*)
  4. Implement all layers in foo/*
  5. Compile all layers into class files
  6. Run orthotest on foo.plm

 

PLM File Format

Note: PLM files are only for multi-dimensional models (MDMs).

A Product Line Matrix file defines an n-dimensional matrix. It is needed only if dimensional model is being verified for safe composition.

The first line contains path to the model file. If a relative path is used, it must be relative to the orthotest execution directory. The remainder of the file is split into three sections, separated by %%. Comments are denoted by starting a line with '

The first section specified path to the project root directory. This layer names are appended to this path. The second section defines the axis and units along each axis. Each unit is separated by space. The final section defines layers within each cell of the matrix. For example, if it is a 2-dimensional matrix, a line will be of the form: "x-coodinateValue y-coordinateValue : layer1 layer2"

projects\GPL2D.m
' First line should always pointing to the model file (relative paths are ok)

' Path to project root directory. Relative paths are ok, so . represents current directory – I tend to place the plm file also in the project directory.
projects\GPL

%%

' Each line represents an axis of the multidimensional cube
' Tokens before : mark the axis name, and tokens after : specify the units along that axis
COLUMN : Base WithDriver
ROW : Directed Undirected Weighted UnWeighted BFS DFS Number Connected StrongC Cycle MSTPrim MSTKruskal Shortest Extra

%%

' This section specifies the cell and layers of the matrix
' Each line represents cell of the cube, and is preceded by its coordinates in n-dimensions
' Tuple-format: axis0 axis1 ... axis(n-1) : layers separated by space

Base Directed : Directed
Base Undirected : Undirected
Base Weighted : Weighted
Base UnWeighted : UnWeighted
Base BFS : BFS
Base DFS : DFS
Base Number : Number
Base Connected : Connected
Base StrongC : StronglyConnected Transpose
Base Cycle : Cycle
Base MSTPrim : MSTPrim
Base MSTKruskal : MSTKruskal
Base Shortest : Shortest

WithDriver Directed : DirectedRun
WithDriver Undirected : UnDirectedRun

WithDriver Number : NumberRun
WithDriver Connected : ConnectedRun

WithDriver Cycle : CycleRun
WithDriver MSTPrim : MSTPrimRun
WithDriver MSTKruskal : MSTKruskalRun
WithDriver Shortest : ShortestRun
WithDriver Extra : Benchmark Prog

 

Bytecode Compilation

The orthotest tool requires references from the bytecode to verify compilation dependencies. There are two ways AHEAD model source can be compiled into a program: 1) compose the jak source, convert it to java, and compile the java classes 2) Convert individual jak files within layers into java, compile the java files into bytecode and compose bytecode. This tool requires the later approach.

Example:
cd to the parent of GPL directory
run in bash:
rm -r gpl\$\$
bcj2j gpl
bccompiler gpl

This procedure will produce "gpl$$" directory containing all layers and class files representing jak source within each layer. Use this directory as the Project Root for this tool. It needs uncomposed compiled classes. For more information on using bytecode compilation tools look into ByteCodeTools.html in AHEAD documentation.

Note: Some jar files (bcjak2java.jar, bcmixin.jar, bcstubgenerator.jar, bctostub.jar, jrename.jar) needs to be added to the class path (typically in setpath.bat or setpath.sh). If your AHEAD build cant find jrename copy jrename files from lib directory of orthotest package to AHEAD's bin and lib directories.

Note: Bytecode compilation can be quite painful at first, so keep the following points in mind:

Command-Line Invocation

To call orthotest from the command line, type:

>./orthotest -s "bali_matrix.plm"

Usage: OrthogonalityValidator [-s] "Path to PLM file"

The optional –s flag outputs any statistics. Currently the only supported statistic is execution time.

Example: java -cp "orthotest.jar;classreader.jar;jdom.jar;guidsl.jar;bcel-5.1.jar" ProgramCube.Validation.Orthogonality.OrthogonalityValidator -s "path to..bali_matrix.plm"

 
 

Failure Details

Orthogonality test outputs any errors or warnings to std err. Errors can be viewed on command line with regular output, or you can pipe errors to a file using:

shell> orthotest “path” 2> errors.txt

which instructs stream 2 (error stream) to be sent to the file. Any other message is sent to the standard out. If there are no errors (i.e. the product line passes orthogonality validation) or warnings, the program terminates without any output.

Right-diagonal dependencies are marked as errors, and left-diagonal dependencies as warnings.

Example of an error:

Orthogonality failure (method referencing method): (withRequireFeature and base) with (core and baliComposer) java.lang.Object driver (java.lang.String[]) references Main$$::java.lang.Object driver (java.lang.String[])

require references composer

In this example, the error resulted because a method is referencing another method at right-diagonal. The two layers are located at coordinate (withRequireFeature, base) and (core, baliComposer). To be precise, the layer require has a method driver(..) referencing method driver(..), which is defined within the layer composer.

Example of a warning:

LEFT DIAGONAL Warning (Same method refined by layers at diagonal): (core and base) with (withRequireFeature and baliComposer)

In the above example two layers located at left-diagonal are referencing the same method. These two layers are placed at coordinates (core, base) and (withRequireFeature, baliComposer). Such interference occurring from layers at left-diagonals are not errors - it never changes the semantics of the program under different order of dimensional aggregation, however it may be useful for debugging and understanding how refinements interact in the product line.

 


ATS Home Page

Copyright Software Systems Generator Research Group. All rights reserved.
Revised:  February 12, 2006 .