TreeDL: Tree Description Language

Each entity in a tree description can be linked with additional declarative information. It expands capabilities of tree description without change of tree description language. Declarative information is available during tree description analysis and can be used by a tool that process tree description. Keeping declarative information directly in tree description allows to do without additional configuration files. But it is recommended to keep in tree description only information that is immutable for tree description.

Declarative information is specified as a set of named properties:

Property name qid is qualified identifier. Property value - boolean <BOOL_LITERAL>, integer <INT_LITERAL> or string <STRING_LITERAL>.

Example:

[
  treedl.language = "java";
  has.key = true;
  max.length = 8;
]

Here three properties are declared with string, boolean and integer values.

For each entity in a tree description can be defined documentation comment. Documentation comments are available during tree description analysis. Format of documentation comment depends on target language and processing tool. For example, when translating to Java programming language, documentation comments can be used as javadoc comments.

Documentation comments <DOCOMMENT> can be only in certain places described in syntax grammar of TreeDL language. Lexical structure of documentation comments are described in Appendix 1, Lexical grammar.

Example:

/**
 * Documentation comment
 */

TreeDL language allows to declare node types and enumeration types. A type has name <type:ID> that is specified when type is referenced. If type is used in module differrent from module where it was declared, type name should be qualified by synonym of module <module:ID> where type was declared.

Qualified type name is type name <type:ID> qualified by synonym of module <module:ID> if needed.

Used type can be defined using one of the following constructs:

where type can be:

with modifier defining cardinality of type:

Example:

There are two kinds of modules - structure description modules and operation modules.

Structure description module declares a set of node types that can be used in a tree, and may be operations on them. This module kind specified by keyword tree in module header.

Operation module defines operations on nodes whose types are declared in referenced structure description modules. This module kind specified by keyword module in module header.

Full name of module is qualified identifier used to reference module from other modules.

Example:

tree com.unitesk.atp.treedl.TDL;

...

Structure description module with full name com.unitesk.atp.treedl.TDL.

module com.unitesk.atp.treedl.Checker;

...

Operation module com.unitesk.atp.treedl.Checker.

A module can use types declared in other modules. For that full names of referenced modules should be specified.

To use type declared in referenced module its name should be qualified by synonym of module. By default synonym of module is the last identifier of full name. In case of conflicts or other reasons, synonym of module can be defined explicitly using <synonym:ID>. Full name of module itself also defines synonym. Scope of visibility of synonyms is module where they are declared.

Example:

module com.unitesk.atp.treedl.Checker : TreeDL = com.unitesk.atp.treedl.TDL;

...

Operation module com.unitesk.atp.treedl.Checker uses referenced structure description module com.unitesk.atp.treedl.TDL defining TreeDL synonym.

Result of module translation to programming language can be modified using customization code. It is possible to specify base types <TYPE>, insert code <CODE> from header construct before and code from body construct into result of module translation. Detailed description of processing of these constructs is in description of translation scheme for specific programming language.

Example:

[ treedl.language = "java"; ]
module com.unitesk.atp.treedl.TDL;

header
{
    import java.util.Map;
}

body
{
    public static Map getTypes() { ... }
}

Code from header и body constructs is inserted before and into generated class that is the result of module translation to Java programming language:

package com.unitesk.atp.treedl;

// header code
import java.util.Map;

public class TDL
{
    // body code
    public static Map getTypes() { ... }

    ...
}

Node type name is identifier <name:ID> used to reference node type from any node type declaration or operation definition in the same module.

From other modules node type can be referenced by qualified type name.

If node type marked with abstract modifier, it is abstract. Abstract node type can not be instantiated and can be used as base type for other node types. Abstract node types correspond to abstract classes in programming languages.

If node type marked with root modifier, it is a type of root node of a tree.

Example:

abstract node Statement { ... }

Abstract base node type Statement.

root node CompilationUnit { ... }

Root node type.

A node type declaration can be based on other - base node type declaration. All members of base node type with qualified type name type_ref are inherited and can be used in inherited node type. By default a node type is inherited from abstract base node type Node:

abstract node Node
{
    attribute late Node? parent;
}

This node type defines attribute parent containing link to parent node or null for root node.

Example:

node IfStatement : Statement { ... }

Node type IfStatement inherited from Statement.

A result of node type translation to programming language can be modified using customization code. It is possible to specify base types <TYPE> of node type. Detailed description of this construct is in scheme of translation for specific programming language.

Also a code from constructor and body members is inserted in result of node type translation..

The are the following kinds of node type members:

attribute string fullName;

attribute custom string name
get
{
    name = fullName.substring( fullName.lastIndexOf( '.' ) + 1 );
}
set { ... };

abstract node NamedNode
{
    abstract attribute string name;
}

node DefaultNamedNode : NamedNode
{
    attribute string name;
}

node CustomNamedNode : NamedNode
{
    attribute custom string name
    get { ... }
    set { ... };
}

node BaseNode
{
    attribute late int+ intList;
}

node MyNode : BaseNode
{
    attribute override int+ intList
    set { ... };
}

node IfStatement : Statement
{
    child Expression condition;
    child Statement thenStatement;
    child Statement elseStatement;
}

node TryStatement
{
    child Block block;
    child CatchClause* optCatchClauseList;
    child Block? optFinallyBlock;

    constructor
    {
        if( sizeOptCatchClauseList() == 0 && getOptFinallyBlock() == null )
        {
            throw new IllegalArgumentException("There is neither catch clause nor finally block");
        }
    }
}

Name of enumeration type is identifier <name:ID> used to reference this type from any other declaration in the same module.

From other modules enumeration type can be referenced by qualified type name.

A range of enumeration type depends on given constants. A set of these constants is union of a set of base enumeration type type_ref (if specified) and set of constants <const:ID> specified in declaration of this enumeration type.

There are two kinds of enumeration types: enumeration and set of flags. A kind of enumeration type is specified by keywords enum and flags respectively. Range of enumeration is a set of all enumeration type constants. Range of set of flags is a set of all subsets (including empty subset) of a set of all enumeration type constants.

Example:

enum Color { RED, GREEN, BLUE }

Range of enumeration Color consists of three values: RED, GREEN, BLUE.

enum ExtendedColor : Color { WHITE, BLACK }

Range of set of enumeration ExtendedColor consists of five values: three values of base enumeration type Color and two additional values WHITE and BLACK.

flags Modifiers { ABSTRACT, CUSTOM, LATE, OVERRIDE, NOSET, SETONCE }

Range of set of flags Modifiers constsis of 64 combinations of 6 flags.

Signature of operation declares:

A formal parameter of operation has name and type. Parameter of node type or enumeration type can be marked by modifier virtual. Virtual parameters define set of operation cases.

Operation case case_signature

consists of:

A list of parameters of operation case is defined by set of virtual parameters of operation. In operation case for each virtual parameter of operation one of variants of this parameter is specified. Variants of parameter of enumeration type are constants of this type. Variants of parameter of node type are parameters with the same name and its type is non-abstract inherited node type declared in one of modules directly or indirectly referenced by module where operation is declared. If abstract base node type Node is specified as a type of virtual parameter, operation is defined on all node types in all referenced modules.

Exactly one operation case should be defined for each combination of variants of virtual parameters. When operation is called, code <CODE> of operation case corresponding to set of actual parameters will be executed. Operation case can be defined either in body of operation either in one of referenced operations.

Operation is defined on all combinations of virtual parameters, whose node types are declared in modules directly or indirectly referenced by module where operation is declared. Operation can use one or more operations declared in these modules. Qualified (by synonym of module) names of referenced operations are specified after signature of operation. Inherited operations should have the same types of parameters. Referenced operations should be consistent, that is two referenced operations for each common combination of virtual parameters should use the same case, defined in one of these operations or in operation referenced by both of them.

Example:

tree P;

node A {}

tree Q : P;

abstract node X {}

node B {}

operation string F( virtual Node n )
{
    case( P.A n ): { return "A"; }
    case( B   n ): { return "B"; }
}

Operation F is defined for all node types declared in module Q and referenced module P. Operation case is defined for each of non-abstract node types.

tree R : Q;

node C {}

operation string G( virtual Node n )
  : Q.F
{
    case ( C node ): { return "C"; }
}

Operation G is defined for all node types, defined in module R and referenced modules P and Q. For all node types from modules P and Q operation Q.F is used. So, operation cases are defined only for node types from module R.

If there is another module S that also use module P, and operation H defined on these modules:

tree S : P;

node D {}

operation string H( virtual Node n )
{
    case( P.A n ): { return "P.A"; }
    case( D   n ): { return "S.D"; }
}

when trying to extend the definition of operation R.G on module S using operation H:

tree R : Q, S;

operation string G( virtual Node n )
 : Q.F, S.H
{
    case ( C node ): { return "C"; }
}

there will be conflict because operations Q.F and S.H use different cases for node type P.A: the result of operation Q.F is "A", but the result of operation S.H - "P.A". To resolve this conflict, either remove reference to one of this operations and redefine its cases, either extract implementation of operation for module P to separate operation and use it by both operations:

tree P;

node A {}

operation string E( virtual Node n )
{
    case( A n ): { return "P.A"; }
}

tree Q : P;

abstract node X {}

node B {}

operation string F( virtual Node n ) : P.E
{
    case( B n ): { return "B"; }
}

tree S : P;

node D {}

operation string H( virtual Node n ) : P.E
{
    case( D n ): { return "S.D"; }
}

tree R : Q, S;

operation string G( virtual Node n )
 : Q.F, S.H
{
    case ( C node ): { return "C"; }
}

This definition of operation R.G is correct because both referenced operations on module P use the same implementation of operation P.E.