xtc.type
Class AST

java.lang.Object
  xtc.type.AST

Direct Known Subclasses:

JavaAST

public abstract class AST
extends Object

Common type operations for Rats! ASTs.

This class supports two views on a grammar's generic AST. The first view is dynamically typed, with all generic AST nodes represented by the canonical node type. The second view is statically typed, with all generic AST nodes represented by tuples organized into variants. Either way, this class supports the following types:

• The void type represented by VoidT.
• The unit type represented by UnitT.
• Characters represented by an InternalT with name "char".
• Strings represented by an InternalT with name "string".
• Tokens represented by an InternalT with name "token".
• Dynamically typed nodes represented by an InternalT with name "node".
• Statically typed nodes represented by a VariantT with TupleT elements.
• Parse tree annotations represented by an InternalT with name "formatting".
• Lists represented by an InternalT with name "list".
• Actions represented by an InternalT with name "action".

All node types have the Constants.ATT_NODE attribute; the dynamically typed node representing generic productions also has the Constants.ATT_GENERIC attribute.

In addition to generic ASTs, this class also supports user-defined types, which must be represented by types that are not listed above.

Concrete subclasses specify the mapping between strings and types. For mapping internal representations back to strings, the void type has name "void", the unit type has name "unit", and the wildcard has name "?".

Version:

$Revision: 1.39 $

Nested Class Summary

static class

AST.MetaData The metadata for a grammar's statically typed nodes.

Field Summary

static Type	ACTION The canonical parameterized action type.
static Type	ANY The canonical any type.
static Type	CHAR The canonical character reference type.
protected Map<String,Type>	externToIntern The map from strings to type representations.
static Type	FORMATTING The canonical formatting node type.
static Type	GENERIC The canonical dynamically typed generic node type.
protected List<String>	importedModules The list of imported module names.
protected Map<String,String>	importedTypes The map from simple type names to fully qualified type names.
static Set<String>	INTERNAL The set of internal type names.
protected Map<String,String>	internToExtern The map from internal type names to external types.
static Type	LIST The canonical parameterized list type.
static Type	NODE The canonical dynamically typed node type.
static Type	NULL_NODE The canonical null node type.
protected Map<String,String>	originalNames The map from unqualified variant names to original names.
static Type	STRING The canonical string type.
static Type	TOKEN The canonical token type.
protected Map<String,TupleT>	tuples The map from tuple names to tuple types.
protected Map<String,List<VariantT>>	tupleVariants The map from tuple names to variants containing the tuples.
protected Map<String,Set<String>>	variantNodes The map from variant names to nodes.
protected Map<String,VariantT>	variants The map from variant names to variant types.
static Type	VOID The canonical void type, which is VoidT.TYPE.
static Type	WILD_ACTION The canonical action instantiated with a wildcard element type.
static Type	WILD_LIST The canonical list instantiated with a wildcard element type.

Constructor Summary

AST()
Create a new instance.

Method Summary

static Type	actionOf(Type element) Create a new action type.
void	add(TupleT tuple, VariantT variant) Add the specified tuple type to the specified variant type.
Type	combine(TupleT tuple1, TupleT tuple2, boolean flatten, boolean strict) Combine the specified tuple types into a consistent type.
Type	concretize(Type type, Type concrete) Ensure that the specified type is concrete.
void	concretizeTuples(VariantT variant, Type concrete) Concretize the specified variant type's tuples.
String	extern(Type type) Convert the specified type to a string.
protected abstract String	externAction(Type type) Convert the specified action type to a string.
protected abstract String	externList(Type type) Convert the specified list type to a string.
protected abstract String	externUser(Type type) Convert the specified user-defined type to a string.
Type	flatten(TupleT tuple, boolean strict) Flatten the specified tuple type.
static Type	getArgument(Type type) Get the specified instantiated type's only argument.
AST.MetaData	getMetaData(VariantT variant) Determine the metadata for the specified variant.
Constants.FuzzyBoolean	hasLocation(Type type) Determine whether instances of the specified type have a source location.
protected abstract Constants.FuzzyBoolean	hasLocationUser(Type type) Determine whether instances of the specified user-defined type have a source location.
boolean	hasTuple(String name) Determine whether a tuple type with the specified name has been created before.
boolean	hasVariant(String name) Determine whether a variant type with the specified name has been created before.
void	importModule(String module) Import the specified module.
void	importType(String qualified, String simple) Import the specified type.
abstract void	initialize(boolean hasNode, boolean hasToken, boolean hasFormatting, boolean hasAction) Initialize the mapping between external and internal representations.
Type	intern(String s) Convert the specified string representation of a type into the type.
protected abstract Type	internAction(String s) Convert the specified string representation of an action type into the type.
protected abstract Type	internList(String s) Convert the specified string representation of a list type into the type.
protected abstract Type	internUser(String s) Convert the specified string representation of a user-defined type into its internal representation.
static boolean	isAction(Type type) Determine whether the specified type is an action.
static boolean	isAny(Type type) Determine whether the specified type is the any type.
static boolean	isChar(Type type) Determine whether the specified type is a character.
static boolean	isDynamicNode(Type type) Determine whether the specified type is a dynamically typed node.
static boolean	isFormatting(Type type) Determine whether the specified type is a formatting node.
abstract boolean	isGenericNode(String s) Determine whether the specified string represents the generic node type.
static boolean	isGenericNode(Type type) Determine whether the specified type is a generic node.
static boolean	isList(Type type) Determine whether the specified type is a list.
boolean	isMonomorphic(String name) Determine whether the tuple type with the specified name has been created before and is monomorphic.
static boolean	isNode(Type type) Determine whether the specified type is a node.
static boolean	isNullNode(Type type) Determine whether the specified type is a null node.
static boolean	isOptional(Type type) Determine whether the specified type is optional.
static boolean	isStaticNode(Type type) Determine whether the specified type is a statically typed node.
static boolean	isString(Type type) Determine whether the specified type is a string.
static boolean	isToken(Type type) Determine whether the specified type is a token.
static boolean	isUser(Type type) Determine whether the specified type is user-defined.
static boolean	isVariable(Type type) Determine whether the specified type is variable.
abstract boolean	isVoid(String s) Determine whether the specified string represents the void type.
static boolean	isVoid(Type type) Determine whether the specified type is the void type.
static Type	listOf(Type element) Create a new list type.
static Type	markOptional(Type type) Mark the specified type as optional.
static Type	markVariable(Type type) Mark the specified type as variable.
boolean	overlap(VariantT v1, VariantT v2) Determine whether the specified variants overlap.
void	print(Type type, Printer printer, boolean refIsDecl, boolean qualified, String module) Print the specified type.
String	toOriginal(VariantT variant) Get the original name for the specified variant.
TupleT	toTuple(String name) Get the tuple type with the specified name.
TupleT	toTuple(VariantT variant) Get the polymorphic tuple for the specified variant.
VariantT	toVariant(String name, boolean poly) Get the variant type with the specified name.
String	toVariantName(String name) Convert the specified production's name into a variant name.
List<VariantT>	toVariants(TupleT tuple) Get the specified tuple's variants.
Type	unify(Type t1, Type t2, boolean strict) Unify the specified types.
protected Type	unify(VariantT v1, VariantT v2) Unify the specified statically typed nodes.
protected abstract Type	unifyUser(Type t1, Type t2, boolean strict) Unify the specified user-defined types.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

INTERNAL

public static final Set<String> INTERNAL

The set of internal type names.

VOID

public static final Type VOID

The canonical void type, which is VoidT.TYPE.

ANY

public static final Type ANY

The canonical any type.

CHAR

public static final Type CHAR

The canonical character reference type.

STRING

public static final Type STRING

The canonical string type.

TOKEN

public static final Type TOKEN

The canonical token type.

NODE

public static final Type NODE

The canonical dynamically typed node type.

NULL_NODE

public static final Type NULL_NODE

The canonical null node type.

GENERIC

public static final Type GENERIC

The canonical dynamically typed generic node type.

FORMATTING

public static final Type FORMATTING

The canonical formatting node type.

LIST

public static final Type LIST

The canonical parameterized list type.

WILD_LIST

public static final Type WILD_LIST

The canonical list instantiated with a wildcard element type.

ACTION

public static final Type ACTION

The canonical parameterized action type.

WILD_ACTION

public static final Type WILD_ACTION

The canonical action instantiated with a wildcard element type.

externToIntern

protected final Map<String,Type> externToIntern

The map from strings to type representations.

internToExtern

protected final Map<String,String> internToExtern

The map from internal type names to external types. Valid type names are void, unit, any, char, string, token, node, formatting, list, and action as well as ? for wildcards.

importedModules

protected final List<String> importedModules

The list of imported module names. Each module name should end with the separator necessary for creating a fully qualified type name by appending a simple name.

importedTypes

protected final Map<String,String> importedTypes

The map from simple type names to fully qualified type names.

variants

protected final Map<String,VariantT> variants

The map from variant names to variant types.

variantNodes

protected final Map<String,Set<String>> variantNodes

The map from variant names to nodes.

originalNames

protected final Map<String,String> originalNames

The map from unqualified variant names to original names.

tuples

protected final Map<String,TupleT> tuples

The map from tuple names to tuple types.

tupleVariants

protected final Map<String,List<VariantT>> tupleVariants

The map from tuple names to variants containing the tuples.

Constructor Detail

AST

public AST()

Create a new instance. This constructor allocates the internal data structures for mapping between external and internal types but does not initialize them.

See Also:

initialize(boolean,boolean,boolean,boolean)

Method Detail

initialize

public abstract void initialize(boolean hasNode,
                                boolean hasToken,
                                boolean hasFormatting,
                                boolean hasAction)

Initialize the mapping between external and internal representations. This method fills the externToIntern and internToExtern data structures.

Parameters:

hasNode - Flag to indicate use of built-in nodes.

hasToken - Flag to indicate use of tokens.

hasFormatting - Flag to indicate use of formatting.

hasAction - Flag to indicate use of actions.

importModule

public void importModule(String module)

Import the specified module. This method adds the module to the list of imported modules importedModules. The specified module name must end with the appropriate separator.

Parameters:

module - The module name.

importType

public void importType(String qualified,
                       String simple)

Import the specified type. This method adds a mapping from the specified simple type name to the specified qualified type name to the imported types importedTypes.

Parameters:

qualified - The fully qualified name.

simple - The simple name.

isVoid

public abstract boolean isVoid(String s)

Determine whether the specified string represents the void type.

Parameters:

s - The type as a string.

Returns:

true if the string represents the void type.

isGenericNode

public abstract boolean isGenericNode(String s)

Determine whether the specified string represents the generic node type.

Parameters:

s - The type as a string.

Returns:

true if the string represents the generic node type.

intern

public Type intern(String s)

Convert the specified string representation of a type into the type. This method defers to internList(String), internAction(String), and internUser(String) for list, action, and user-defined types, respectively.

Parameters:

s - The type as a string.

Returns:

The type.

Throws:

IllegalArgumentException - Signals that the string representation is not a valid type.

internList

protected abstract Type internList(String s)

Convert the specified string representation of a list type into the type.

Parameters:

s - The list type as a string.

Returns:

The type or ErrorT.TYPE if the string does not represent a list.

internAction

protected abstract Type internAction(String s)

Convert the specified string representation of an action type into the type.

Parameters:

s - The action type as a string.

Returns:

The type or ErrorT.TYPE if the string does not represent an action.

internUser

protected abstract Type internUser(String s)

Convert the specified string representation of a user-defined type into its internal representation.

Parameters:

s - The user-defined type as a string.

Returns:

The type.

Throws:

IllegalArgumentException - Signals that the string representation is not a valid type.

extern

public String extern(Type type)

Convert the specified type to a string. This method defers to externList(Type), externAction(Type), and externUser(Type) for list, action, and user-defined types, respectively.

Parameters:

type - The type.

Returns:

The type as a string.

externList

protected abstract String externList(Type type)

Convert the specified list type to a string.

Parameters:

type - The list type.

Returns:

The type as a string.

externAction

protected abstract String externAction(Type type)

Convert the specified action type to a string.

Parameters:

type - The action type.

Returns:

The type as a string.

externUser

protected abstract String externUser(Type type)

Convert the specified user-defined type to a string.

Parameters:

type - The user-defined type.

Returns:

The type as a string.

hasLocation

public Constants.FuzzyBoolean hasLocation(Type type)

Determine whether instances of the specified type have a source location. This method defers to hasLocationUser(Type) for user-defined types.

Parameters:

type - The type.

Returns:

The inexact answer.

hasLocationUser

protected abstract Constants.FuzzyBoolean hasLocationUser(Type type)

Determine whether instances of the specified user-defined type have a source location.

Parameters:

type - The type.

Returns:

The inexact answer.

isOptional

public static boolean isOptional(Type type)

Determine whether the specified type is optional.

Parameters:

type - The type.

Returns:

true if the specified type is optional.

isVariable

public static boolean isVariable(Type type)

Determine whether the specified type is variable.

Parameters:

type - The type.

Returns:

true if the specified type is variable.

isVoid

public static boolean isVoid(Type type)

Determine whether the specified type is the void type.

Parameters:

type - The type.

Returns:

true if the type is the void type.

isAny

public static boolean isAny(Type type)

Determine whether the specified type is the any type.

Parameters:

type - The type.

Returns:

true if the type is the any type.

isChar

public static boolean isChar(Type type)

Determine whether the specified type is a character.

Parameters:

type - The type.

Returns:

true if the type is a character.

isString

public static boolean isString(Type type)

Determine whether the specified type is a string.

Parameters:

type - The type.

Returns:

true if the type is a string.

isToken

public static boolean isToken(Type type)

Determine whether the specified type is a token.

Parameters:

type - The type.

Returns:

true if the type is a token.

isNode

public static boolean isNode(Type type)

Determine whether the specified type is a node.

Parameters:

type - The type.

Returns:

true if the type is a node.

isDynamicNode

public static boolean isDynamicNode(Type type)

Determine whether the specified type is a dynamically typed node.

Parameters:

type - The type.

Returns:

true if the type is a dynamically typed node.

isNullNode

public static boolean isNullNode(Type type)

Determine whether the specified type is a null node.

Parameters:

type - The type.

Returns:

true if the type is a null node.

isStaticNode

public static boolean isStaticNode(Type type)

Determine whether the specified type is a statically typed node.

Parameters:

type - The type.

Returns:

true if the type is a statically typed node.

isGenericNode

public static boolean isGenericNode(Type type)

Determine whether the specified type is a generic node.

Parameters:

type - The type.

Returns:

true if the type is a generic node.

isFormatting

public static boolean isFormatting(Type type)

Determine whether the specified type is a formatting node.

Parameters:

type - The type.

Returns:

true if the type is a formatting node.

isList

public static boolean isList(Type type)

Determine whether the specified type is a list.

Parameters:

type - The type.

Returns:

true if the type is a list.

isAction

public static boolean isAction(Type type)

Determine whether the specified type is an action.

Parameters:

type - The type.

Returns:

true if the type is an action.

getArgument

public static Type getArgument(Type type)

Get the specified instantiated type's only argument.

Parameters:

type - The instantiated type.

Returns:

The argument type.

isUser

public static boolean isUser(Type type)

Determine whether the specified type is user-defined.

Parameters:

type - The type.

Returns:

true if the type is a user-defined type.

markOptional

public static Type markOptional(Type type)

Mark the specified type as optional.

Parameters:

type - The type.

Returns:

The optional type.

markVariable

public static Type markVariable(Type type)

Mark the specified type as variable.

Parameters:

type - The type.

Returns:

The variable type.

toVariantName

public String toVariantName(String name)

Convert the specified production's name into a variant name. This method converts the name from Rats!' camel case naming convention into ML's lower case with underscores naming convention. It preserves any qualifier.

Parameters:

name - The production's name.

Returns:

The corresponding variant name.

hasVariant

public boolean hasVariant(String name)

Determine whether a variant type with the specified name has been created before. This method first converts the name from Rats!' camel case naming convention into ML's lower case with underscores naming convention. It then checks whether a variant type with that name has been returned by toVariant(String,boolean) before.

Parameters:

name - The name in camel case.

Returns:

true if a variant type with the name exists.

See Also:

toVariantName(String)

toVariant

public VariantT toVariant(String name,
                          boolean poly)

Get the variant type with the specified name. This method first converts the name from Rats!' camel case naming convention into ML's lower case with underscores naming convention. Then, if this method has not been invoked on the specified name before, it returns a new variant type with an empty list of tuples. Otherwise, it simply returns the previously created variant type. The returned variant type has the Constants.ATT_NODE attribute.

Parameters:

name - The name in camel case.

poly - The flag for whether the variant is polymorphic.

Returns:

The corresponding variant type.

See Also:

toVariantName(String)

toOriginal

public String toOriginal(VariantT variant)

Get the original name for the specified variant.

The specified variant must have been created with toVariant(String,boolean).

Parameters:

variant - The variant.

Returns:

The original name in Rats!' camel case.

hasTuple

public boolean hasTuple(String name)

Determine whether a tuple type with the specified name has been created before.

Parameters:

name - The name.

Returns:

true if a tuple type with the name exists.

isMonomorphic

public boolean isMonomorphic(String name)

Determine whether the tuple type with the specified name has been created before and is monomorphic.

Parameters:

name - The name.

Returns:

true if a tuple type with the name exists and is monomorphic.

toTuple

public TupleT toTuple(String name)

Get the tuple type with the specified name. If this method has not been invoked on the specified name before, it returns a new tuple type, which is incomplete. Otherwise, it simply returns the previoulsy created tuple type.

Parameters:

name - The name.

Returns:

The corresponding tuple type.

add

public void add(TupleT tuple,
                VariantT variant)

Add the specified tuple type to the specified variant type. If the tuple is not a member of the specified variant, this method adds it, while also updating its internal state.

The specified tuple must have been created with toTuple(String) or toTuple(VariantT). The specified variant must have been created with toVariant(String,boolean).

Parameters:

tuple - The tuple.

variant - The variant.

toVariants

public List<VariantT> toVariants(TupleT tuple)

Get the specified tuple's variants.

The specified tuple must have been created with toTuple(String) or toTuple(VariantT). It must have been added to any variants with add(TupleT,VariantT).

Parameters:

tuple - The tuple.

Returns:

The tuple's variants.

toTuple

public TupleT toTuple(VariantT variant)

Get the polymorphic tuple for the specified variant.

The specified variant must have been created with toVariant(String,boolean).

Parameters:

variant - The variant.

Returns:

The corresponding polymorphic tuple.

overlap

public boolean overlap(VariantT v1,
                       VariantT v2)

Determine whether the specified variants overlap. Two variants overlap if they include tuples representing the same generic node.

The specified variants must have been created with toVariant(String,boolean).

Parameters:

v1 - The first variant.

v2 - The second variant.

Returns:

true if the two variants overlap.

getMetaData

public AST.MetaData getMetaData(VariantT variant)

Determine the metadata for the specified variant.

Parameters:

variant - The variant.

Returns:

The corresponding metadata.

listOf

public static Type listOf(Type element)

Create a new list type.

Parameters:

element - The element type.

Returns:

The corresponding list type.

actionOf

public static Type actionOf(Type element)

Create a new action type.

Parameters:

element - The element type.

Returns:

The corresponding action type.

unify

public Type unify(Type t1,
                  Type t2,
                  boolean strict)

Unify the specified types. If the strict flag is set, statically and dynamically typed nodes do not unify. If the flag is not set, they do unify and otherwise incompatible types unify to the any type. This method defers to unify(VariantT,VariantT) for statically typed nodes and to unifyUser(Type,Type,boolean) for user-defined types.

Parameters:

t1 - The first type.

t2 - The second type.

strict - The flag for strict unification.

Returns:

The unified type or ErrorT.TYPE if the two types do not unify.

unify

protected Type unify(VariantT v1,
                     VariantT v2)

Unify the specified statically typed nodes. Statically typed nodes unify through polymorphic variant types, unless they reference the same underlying AST node.

Parameters:

v1 - The first variant.

v2 - The second variant.

Returns:

The unified variant.

unifyUser

protected abstract Type unifyUser(Type t1,
                                  Type t2,
                                  boolean strict)

Unify the specified user-defined types. Note that this method need not handle instantiated types but must preserve parameterize types.

Parameters:

t1 - The first user-defined type.

t2 - The second user-defined type.

strict - The flag for strict unification.

Returns:

The unified type or ErrorT.TYPE if the two types do not unify.

flatten

public Type flatten(TupleT tuple,
                    boolean strict)

Flatten the specified tuple type. If the specified tuple has a list element, this method combines the first such list type with all succeeding element types into a single list type, modifying the specified tuple type.

Parameters:

tuple - The tuple type.

strict - The flag for strict unification.

Returns:

The updated tuple type or ErrorT.TYPE if types cannot be unified.

combine

public Type combine(TupleT tuple1,
                    TupleT tuple2,
                    boolean flatten,
                    boolean strict)

Combine the specified tuple types into a consistent type. The types must be tuples with the same name.

Parameters:

tuple1 - The first tuple.

tuple2 - The second tuple.

flatten - The flag for flattening lists.

strict - The flag for strict unification.

Returns:

The combined tuple type or ErrorT.TYPE if the two tuple types cannot be combined into a consistent type.

concretize

public Type concretize(Type type,
                       Type concrete)

Ensure that the specified type is concrete. This method replaces occurrences of the wildcard type with the specified replacement; though it does not process variant types to avoid infinite recursions. It assumes that list and action types are instantiated.

Parameters:

type - The type.

concrete - The concrete replacement for wildcards.

Returns:

The concrete type.

See Also:

concretizeTuples(VariantT,Type)

concretizeTuples

public void concretizeTuples(VariantT variant,
                             Type concrete)

Concretize the specified variant type's tuples. This method updates any tuples in place.

Parameters:

variant - The variant.

concrete - The concrete replacement for wildcards.

See Also:

concretize(Type,Type)

print

public void print(Type type,
                  Printer printer,
                  boolean refIsDecl,
                  boolean qualified,
                  String module)

Print the specified type.

Parameters:

printer - The printer.

type - The type.

refIsDecl - The flag for whether a variant type reference also is a declaration.

qualified - The flag for printing qualified names.

module - The current module name, which may be null.