PsychoPathXPathProcessor/Design

Draft Content
This page is currently under construction. Community members are encouraged to maintain the page, and make sure the information is accurate.

About this Document
Information here is based on the original design document at the original sourceforge project. It is here for reference purposes and future updating by the current maintainers.

Introduction

The XPath specification proposes a processing model as shown in figure 1 .

Figure 1: Processing model taken from the XPath 2.0 specification.

This model was the base for PsychoPath’s design.

By following the diagram, the parsing of an XPath expression yields an Op-Tree. The variety of nodes this tree may contain is reflected by the different types of XPath expressions which exist. For example nodes representing expressions such as and, or, plus, etc. need to be implemented. Having a grammar of 80 production rules, and almost each one of them representing a different type of expression, it became clear that a separate package should be dedicated entirely to this Op-Tree. This lead to the definition of the ast package which contained the Abstract Syntax Tree nodes representing the various XPath expressions.

The next interesting component in the processing model is the execution engine. Much of the detail is hidden for clarity in the diagram. After some research on what exactly is needed for a complete execution of an expression, two main components were revealed: types and functions. Currently, over 90 functions are defined and we realized an extensible design for functions needed to be devised. They were all grouped in the function package.

A large number of types is also defined. Also, each type implicitly defines a constructor function and has specific interactions with operators defined on it. All matters regarding types and the type system are grouped in the types package.

The link between all these components is the main xpath package. Here the main interface to the client is defined, where components such as the execution engine are present.

Finally an additional package containing all the test code, called xpathtest, was created. The primary reason for separating the main code from the tests was to facilitate the distribution of the product in case some users were merely interested in the actual processor implementation without the accompanying test suite. Also we believe there is more order in the code’s structure this way, possibly aiding development.

Figure 2 summarizes the packages present in PsychoPath and their relationships. The design and rational for each package will now be presented in turn.

Figure 2: Packages present in PsychoPath.

The main xpath package makes extensive use of its function, types and ast sub packages.

1 AST Package

The ast package represents the Op-Tree defined in figure 1 . From the diagram, it is evident that various operations need to be performed on the ast such as resolving names, normalizing, executing and so on. These operations will lead to a definition of a base class for a node in the ast.

A first attempt in defining such a base class may be as shown in figure 3 .

Figure 3: A way of defining the base class for all ast nodes. All operations are supported directly by the nodes themselves.

There are several reasons why this design did not seem suitable. Firstly, if a new operation had to be added, all the nodes in the ast would have to be modified (currently over 60 classes). By by examining the details more closely, it is not yet clear what should the parameters and results be of these operations. For example, what arguments should the evaluate method take? What is necessary for full evaluation of an XPath? Another problem of this approach is that it gives more functionality to the ast than desired. The ast should represent expressions and not the way in which they are evaluated or statically checked, since the xpath package should deal with that responsibility. Furthermore, the code for these operations would be spread across all the ast classes instead of being present in one single location reflecting the single logical operation. Various implementations of the same operation would be impossible to be present in an effective manner using this design, which defeats one of our main requirements.

The solution to these problems was to implement the visitor pattern. One of the disadvantages of the visitor pattern is that if the ast changes, all the visitors would need to be updated. This is not at all a limitation for two main reasons. Firstly, a change in the ast would mean a change in the XPath language, which is not likely unless version 3 of XPath will be developed. Secondly, in the case of a change, if the previously described design was used new code would have to be implemented to support each novel expression. The amount of effort to update the visitors will be the same. The real downside of the visitor approach is performance. Instead of performing a single virtual call, the overhead of double dispatch will incur—the ast node will invoke the visitor, and then the operation will be executed.

The current design of the ast base class is shown in figure 4 .

Figure 4: Current design of the base class for all ast nodes with support for the visitor pattern.

No longer there is a question what each operation should return and what arguments it needs for performing correctly. All this information is defined by the specific implementation of the XPathVisitor. Also, all code for an operation will be contained in a single location. Implementing a different version for an operation is achievable by writing a new visitor—no changes to the ast are necessary.

In order to write a visitor the interface in figure 5 must be implemented. The visitor is then used by passing itself as the argument to the accept method of an XPathNode. The result will be whatever the visitor defines it to be. A wrapper to the visitor may be implemented which returns a specific type rather than Object.

Figure 5: XPathVisitor interface. Only two three ast nodes are shown for clarity—all of the nodes must be implemented.

The following fragment of code depicts how a visitor may be developed:

public class Printer implements XPathVisitor {
  public Object visit(XPath xp) {
     System.out.println("Node is XPath");
     return null;
  }

  public Object visit(IfExpr ifexpr) {
     System.out.println("Node is IfExpr");
     return null;
  }
  ...
} 

Finally, the visitor may be used in the following way:

XPathNode node; XPathVisitor visitor;
 ...
Object result = visitor.accept(node); 

Now visitors performing name resolving, normalization and evaluation may be implemented without any changes to the ast.

2 Types Package

This package faces a similar problem as the ast one. In both cases there is a relatively complex class hierarchy and the single base class is used throughout the code at most times. The developer does not know the concrete types of the objects being manipulated although the semantics of the operations highly depend on them. Polymorphism is the main tool which needs to be used effectively to solve this problem.

Types not only need to represent values, but in most cases they must also support operators. Unary operators may be implemented very effectively with standard polymorphism by simply applying a method representing the operation to the type such as:

AnyType t; ... t.negate(); // unary negation 

The problem is more complex with binary operations. In this case, the semantics of the operation depends on two types and not only a single one. Consider the following example which attempts to solve the problem using standard polymorphism:

AnyType left, right; ... left.plus(right); 

Although the problem of the plus operator may seem solved, it is not. How is will the plus method actually be implemented? Using the solution described above, only the type of the left argument will be revealed but not the right one. A naive implementation would be:

public Object plus(AnyType right) {
   if(right instanceof AnyNumber) {
      ...
   } else if(right instanceof AnyString) {
      ...
   }  ...
   else 
     return null;
} 

An interesting solution to this problem are multi methods. Briefly, it consists in registering all permutations of operations and arguments to a hash table. When an operation needs to be performed on two unknown types, a key consisting of the operation and concrete types (obtainable via standard polymorphism) is computed. The key is then used to lookup the hash table and retrieve a function pointer to the specific operation required.

PsychoPath’s implementation adopts the standard polymorphism mechanism. The main reason for not using multi methods was that we were not confident enough on how to implement it with Java (no direct support for function pointers). It also turns out that many operators require specific right arguments for specific left arguments, i.e. the types of the left and right arguments need to be always the same. Thus the previous implementation described for plus would simply be, in pseudo code:

if(right instanceof typeof(this))
  // do operation
else 
  // error 

2.1 Type hierarchy

XPath defines a large type hierarchy. Figure 6 summarizes a portion of the current implementation of the type hierarchy. Classes of special interest are the base AnyType and CtrType. Their definition is illustrated in figure 7 .

Figure 6: Part of the type hierarchy currently implemented.

Figure 7: The design of the base class for all types AnyType. CtrType represents the base class for all types which may be created using constructors in XPath.

The AnyType class will define the requirements for implementing a new type. Currently these are to provide a string representation of the value which they hold. This is a requirement in the XPath specification. Additionally, types must provide a string representation of the type name. This requirement is purely for PsychoPath and its main reason is for testing. It makes it much easier to write test cases by specifying the expected type as a string rather than having to use some Java operators or other mechanisms to determine the type of the result. Also, these two methods are very useful for debugging.

The methods to be implemented for a CtrType are both required by the XPath specification. The obvious method is constructor which will construct the type from the argument supplied. The implementor is required to sanity check the arguments and must not alter them. The type_name method will return the name of the implicit constructor function defined in order to create this type. An example would be the type name of “string” which will define a function available in XPath to construct string elements by invoking an expression such as string("w00t"). The developer of a type will not need to create the code for a function constructing the type but rather, as later explained, he/she simply needs to add the newly developed type to a special function library.

2.2 Operators on Types

The way operators are treated in the main implementation is purely syntactic. If a type is to support a certain operator, a specific interface needs to be implemented. It is up to the implementation of the type to provide the semantics of the operator. There is a interface to be implemented for each symbol representing an operator. For example if a type requires support for the plus and minus symbol a class such as this may be defined:

public class MyType extends AnyType implements MathPlus, MathMinus {
   ...
   public ResultSequence plus(ResultSequence arg) throws DynamicError {
        ...
   }
   public ResultSequence minus(ResultSequence arg) throws DynamicError { 
        ...
   }
} 

The implementor is responsible for sanity checking arguments. Since the result is a sequence, the implementor has total control over what the result is, and thus the semantics of the operator is. For example, the plus may be used for string concatenation and not necessarily addition.

This flexibility has been reduced toward the end of the project, mainly due to performance issues. Comparison operators no longer use sequences as arguments and return values, but rather they are restricted in returning a primitive boolean and taking in a single type for an argument. This is always the case in XPath so it is not a limitation. However it shows that design rational and generality sometimes needs to be given up for the benefit of performance. Figure 8 shows a subset of the operator interfaces some of which use the original style and others the revised design.

Figure 8: The MathPlus interface shows the original design where the implementor had total control over the semantics of the operator. The CmpEq interface resembles the new design where less power is given to the implementor but efficiency is gained by not having to (un)wrap arguments and results from sequences.

3 Function Package

The XPath specification contains many functions, thus the ease with which a single function may be implemented had to be maximized. Another problem is locating the relevant function and dispatching it in an effective way. A function is uniquely identified by its signature consisting of its name and arity (number of parameters). These requirements already define a minimal interface a function needs to implement as depicted by the summarized version of the current Function base class in figure 9 .

Figure 9: Simplified diagram of the current Function base class. A developer is only required to implement the evaluate method and provide the function’s name and arity in the constructor.

The implementor is required to sanity check arguments and must not alter them. He/she also has total control over the semantics of the function. Some functions call other ones in order to aid their evaluation. Also, the main XPath execution engine maps operators to specific function calls to obtain a result. For these reasons, all of the functions have been implemented by using a static evaluate method. The non-static version will call the static method directly to perform the computation. This does add extra overhead. On the other hand however, if a function calls another one, it may do so via the static method directly rather than going through the overhead of locating the function (the same is true for operators in the evaluator). Another interesting aspect of this is that unit testing may be done on the individual functions directly without having to create the necessary environment for execution. An example of how a function may be implemented follows:

public class MyFunction extends Function {
    public MyFunction() {
      // provide function name and arity 
      super(new QName("MyFunction"), 2);
    }
    public ResultSequence evaluate(Collection args) throws DynamicError {
      // call static version
      return MyFunction(args);
    }
    public static ResultSequence MyFunction(Collection args) throws DynamicError {
       ...
    }
} 

In order to locate and dispatch functions, they are organized in libraries. It is important to note that the developer of new function does not need to know anything about how functions are located and dispatched. He/she only needs to implement the minimum required for a function to work fully.

3.1 Function Libraries

A function library contains a logical collection of functions. The obvious example is the “default” function library which contains all XPath function specified in Xpath and XQuery: Functions and Operators. Other examples include functions defined in XML Schema, which not directly available to the user, and constructor functions. Function libraries are responsible for adding, locating and retrieving functions within them.

The two main function libraries implemented are the FnFunctionLibrary and the ConstructorFL. These map respectively to the default library and constructor functions available to the user. If a developer desires to make a new function, the addition of it is necessary in the appropriate function library. For example to add MyFunction the the default function library, a developer would add a line resembling this in FnFunctionLibrary’s constructor:

 add_function(new MyFunction()). 

Constructible types are added in a similar way.

4 xpath Package

This package links together all of PsychoPath’s functionality and provides a portal to the user. The [[PsychoPathXPathProcessor/UserInterface | User Interface] and these sections will focus mainly on design decisions made throughout the development process rather than explaining how the user should interact with PsychoPath.

One of the main classes in this package is ResultSequence and is fully described in figure 10 .

Figure 10: Interface of the ResultSequence class. The class plays a major role as everything in XPath is treated as a sequence of items.

In XPath everything is a sequence—arguments to functions, results of expressions, etc. This class is highly used in functions and the evaluator visitor, and in several cases, many temporary instances of it are created. For this reason, sequences may be constructed via a factory and later released to try and minimize memory utilization.

This package also contains two fundamental classes to XPath processing: the static and dynamic context. These are used by various visitors in order to retrieve and insert state and other information into them. Their functionality is equivalent to the one explained in the XPath specification.

Other functionality in this package includes the parsing of an XPath expression to an AST. This is currently achieved via JFlex and CUP. Implementing a new, and possible more efficient, parser in the future will be simple as long as the result of the parse operation is an AST as described earlier. DOM Loading is also accomplished by this package with a well defined interface. Currently Xerces2-J  is used as the main DOM implementation.

The visitors which perform actual computations on an XPath will now be described.

4.1 XPath Visitors

There are two main phases in evaluating an XPath expression: the static and the dynamic phase. The static phase consists in name checking, possibly static type checking, and normalization. The dynamic phase relates to the actual execution of the expression. Currently two interfaces have been designed which reflect these two phases and are shown in figure 11 .

Figure 11: Interface for the two phases of execution. First the StaticCheck will perform all necessary static checks on the expression. Then, the Evaluator will execute the expression and return its result.

Both of these interfaces use the visitor pattern inside and are merely wrappers to hide implementation details to the user. Also, since they take a generic XPathNode as an argument, it should be possible to evaluate or check only a specific portion of the whole XPath expression. Both of the interfaces throw exceptions on errors.

The visitors currently implemented in PsychoPath are StaticNameResolver which will check names and expand all QNames, Normalizer which performs normalization and is not supported any longer and the DefaultEvaluator which will evaluate an XPath expression even if it is not normalized. No static type checking has been implemented, and the specification marks it as an option.

The main rational behind the visitors is that they should keep all their state internally. Also, they should not modify objects with which they are initialized. If they do, they must bring the object to its initial state at the end. In the current implementation this is not quite true. An example, although currently not supported, is the normalizer which will modify the AST it is provided. Each visitor may in turn decide its own rules regarding what should be result of a visit operation and how state should be maintained.

4.2 Exceptions and the Error Handling System

All exceptions in PsychoPath derive from a common base: XPathException. The only requirement for exceptions is to have a human readable error message. This facilitates error reporting and assures there is a specific reason to each error.

Furthermore, two other main classes of exceptions exist: StaticError and DynamicError. These relate to errors generated during a specific phase of evaluation. An additional requirement of providing an error code is enforced. These error codes match the ones in the XPath 2.0 specification. In the future, they may be used to check whether failures of a test occurred because of an expected reason or not.

Figure 12 summarizes the key portions of the current exception hierarchy in PsychoPath.

Figure 12: Part of the error hierarchy in PsychoPath.