Overriding Operations on Types

The last section illustrates how semantic changes can be implemented by overriding operations on ASTs. While most semantic changes are handled this ways, certain semantic changes are solely based on types. Type classes define many operations on types so that the type system needs not depend on the AST for this kind of semantic checks. These type operations should be overridden to accommodate semantic changes on types.

For example, in the CArray extension, we cannot assign a constant array to a nonconstant array. Moreover, constant arrays are covariant, i.e., for constant arrays ca1 and ca2, the assignment ca2 = ca1 is legal only if the type of ca1 is a subtype of the type of ca2. Let t1 be the type of ca1 and similarly for t2 as the type of ca2. It follows that both t1 and t2 are instances of ConstArrayType. Then, t1 is a subtype of t2 if the base type of t1 is a subtype of the base type of t2.

The semantic enforcement above requires an appropriate answer to the question: Can something of type t1 be assigned to something of type t2? This question is a query on types. First, let us take a look at how type checking for assignments is performed. The following is an excerpt from method typeCheck in class Assign_c that issues this type query, where s is the same as t1 above, and t is the same as t2 above:

There are three subformulas in the conditional expression:

ts.isImplicitCastValid(s, t), which returns true if a value of type s can be assigned to a variable of type t.
ts.typeEquals(s, t), which returns true if type s is equivalent to type t. Usually, this is the same as ts.isImplicitCastValid(s, t) because a value can always be assigned to a variable of the same type, but the assignment could still be legal even if two types are not structurally equal. This method handles that case.
ts.numericConversionValid(t, ...), which returns true if the value in the second argument can be cast to primitive type t.

Failures to satisfy any of these predicates mean that an expression of type s cannot be assigned to an expression of type t, so a compile-time error is issued. For our CArray extension, we only have to modify the definition of the first predicate, isImplicitCastValid.

The type system forwards the query isImplicitCastValid(from, to) to instance method isImplicitCastValidImpl of from type. In this way, the implementations of operations on types are defined in type classes without cluttering the implementation of the type system, and also maintain modularity between type classes.

To implement the semantic enforcement on constant-array types, we will override isImplicitCastValidImpl in ConstArrayType_c. Here is the implementation in ArrayType_c to be overridden:

    @Override
    public boolean isImplicitCastValidImpl(Type toType) {
        if (toType.isArray()) {
            if (base().isPrimitive() || toType.toArray().base().isPrimitive()) {
                return ts.typeEquals(base(), toType.toArray().base());
            }
            else {
                return ts.isImplicitCastValid(base(), toType.toArray().base());
            }
        }

        // toType is not an array, but this is.  Check if the array
        // is a subtype of the toType.  This happens when toType
        // is java.lang.Object.
        return ts.isSubtype(this, toType);
    }

Given toType, the type to be assigned to, if toType is an array type, there are two cases:

If the base types of the two array types are primitive, then these two base types must be equivalent.
Otherwise, the base type of the source array must be assignable to the base type of the target array.

Otherwise, toType is not an array type. In this case, the array type must be a subtype of toType to make the assignment legal. This happens when toType is the primordial class Object.

First, let us begin with a skeleton of the overriding method in ConstArrayType_c:

    @Override
    public boolean isImplicitCastValidImpl(Type toType) {
        // TODO: Implement this method.
    }

Given a type to be assigned to (toType), when is it legal to assign a value of constant-array type to toType? There are three cases to consider:

toType is not an array type. Then, toType must be the primordial class Object for the assignment to be legal. Since the superclass handles this case properly, we simply invoke the superclass implementation:

        if (!toType.isArray()) {
            // ?1 = ?2 const[]
            // This const array type is assignable to ?1 only if ?1 is Object.
            // Let the base language check this fact.
            return super.isImplicitCastValidImpl(toType);
        }

Otherwise, toType must be an array type. If toType is a constant-array type, then the source array type must be assignable to the target array type. That is, covariance must hold. Since the superclass also handles this case properly, we also invoke the superclass implementation:
```
        if (toType instanceof ConstArrayType) {
            // ?1 const[] = ?2 const[]
            // Let the base language check whether ?2 is assignable to ?1.
            return super.isImplicitCastValidImpl(toType);
        }
		
```
Otherwise, toType must be a nonconstant-array type. Since we cannot assign a constant array to a nonconstant array, the result of the type query is always false:
```
        // ?1[] = ?2 const[]
        // We cannot assign a const array to a non-const array.
        return false;
		
```

Here is the full implementation of isImplicitCastValidImpl:

    @Override
    public boolean isImplicitCastValidImpl(Type toType) {
        if (!toType.isArray()) {
            // ?1 = ?2 const[]
            // This const array type is assignable to ?1 only if ?1 is Object.
            // Let the base language check this fact.
            return super.isImplicitCastValidImpl(toType);
        }

        // From this point, toType is an array.
        if (toType instanceof ConstArrayType) {
            // ?1 const[] = ?2 const[]
            // Let the base language check whether ?2 is assignable to ?1.
            return super.isImplicitCastValidImpl(toType);
        }

        // From this point, toType is a non-const array.
        // ?1[] = ?2 const[]
        // We cannot assign a const array to a non-const array.
        return false;
    }

In addition to isImplicitCastValidImpl, more operations on type objects for constant-array types need to be redefined:

equalsImpl, which returns true if and only if this type object is the same as the given type. Here is the implementation in ArrayType_c:

    @Override
    public boolean equalsImpl(TypeObject t) {
        if (t instanceof ArrayType) {
            ArrayType a = (ArrayType) t;
            return ts.equals(base(), a.base());
        }
        return false;
    }

The given type t can be the same as the receiver type object, which is an array type, iff t is also an array type and their base types are also equal. The only change we need to make for constant-array types is that t must be a constant-array type:

    @Override
    public boolean equalsImpl(TypeObject t) {
        if (t instanceof ConstArrayType) {
            ConstArrayType ca = (ConstArrayType) t;
            // Two ConstArrayType objects are equal if their bases are equal.
            return ts.equals(base(), ca.base());
        }
        return false;
    }

typeEqualsImpl, which returns true if this type is equivalent to the given type. This is usually the same as equalsImpl, but equalsImpl should return true only if the two types are structurally equal. That is, there could be two types that are not structurally equal, but they are still equivalent. typeEqualsImpl handles this case. Here is the implementation in ArrayType_c:
```
    @Override
    public boolean typeEqualsImpl(Type t) {
        if (t instanceof ArrayType) {
            ArrayType a = (ArrayType) t;
            return ts.typeEquals(base(), a.base());
        }
        return false;
    }
		
```
The only difference from equalsImpl is that this method invokes typeEquals on the base types instead of equals. Again, the only change we need to make for constant-array types is that t must be a constant-array type:
```
    @Override
    public boolean typeEqualsImpl(Type t) {
        if (t instanceof ConstArrayType) {
            ConstArrayType a = (ConstArrayType) t;
            // Two ConstArrayType objects are equal if their bases are equal.
            return ts.typeEquals(base(), a.base());
        }
        return false;
    }
		
```

Exercise

Implement the semantic change in CArray related to casting from constant-array types. That is, constant arrays can be cast to other constant arrays as long as casts are valid between base types. That is, the validity of casts between constant-array types are the same as that of traditional array types in Java. The method of interest is isCastValidImpl, which returns true if this type can be cast to the given type.

Solution: + Reveal...

    @Override
    public boolean isCastValidImpl(Type toType) {
        if (!toType.isArray()) {
            // (?1) ?2 const[]
            // This const array type can be cast to ?1 only if ?1 is Object.
            // Let the base language check this fact.
            return super.isCastValidImpl(toType);
        }

        // From this point, toType is an array.
        if (toType instanceof ConstArrayType) {
            // (?1 const[]) ?2 const[]
            // Let the base language check whether ?2 can be cast to ?1.
            return super.isCastValidImpl(toType);
        }

        // From this point, toType is a non-const array.
        // (?1[]) ?2 const[]
        // We cannot cast a const array to a non-const array.
        return false;
    }

Here is the implementation of ConstArrayType_c so far: + Reveal...

package carray.types;

import polyglot.types.ArrayType_c;
import polyglot.types.Resolver;
import polyglot.types.Type;
import polyglot.types.TypeObject;
import polyglot.types.TypeSystem;
import polyglot.util.Position;
import polyglot.util.SerialVersionUID;

/**
 * A {@code ConstArrayType} represents an array of base java types,
 * whose elements cannot change after initialization.
 */
public class ConstArrayType_c extends ArrayType_c implements ConstArrayType {
    private static final long serialVersionUID = SerialVersionUID.generate();

    /** Used for deserializing types. */
    protected ConstArrayType_c() {
    }

    public ConstArrayType_c(TypeSystem ts, Position pos, Type base) {
        super(ts, pos, base);
    }

    @Override
    public boolean equalsImpl(TypeObject t) {
        if (t instanceof ConstArrayType) {
            ConstArrayType ca = (ConstArrayType) t;
            // Two ConstArrayType objects are equal if their bases are equal.
            return ts.equals(base(), ca.base());
        }
        return false;
    }

    @Override
    public boolean typeEqualsImpl(Type t) {
        if (t instanceof ConstArrayType) {
            ConstArrayType a = (ConstArrayType) t;
            // Two ConstArrayType objects are equal if their bases are equal.
            return ts.typeEquals(base(), a.base());
        }
        return false;
    }

    @Override
    public boolean isImplicitCastValidImpl(Type toType) {
        if (!toType.isArray()) {
            // ?1 = ?2 const[]
            // This const array type is assignable to ?1 only if ?1 is Object.
            // Let the base language check this fact.
            return super.isImplicitCastValidImpl(toType);
        }

        // From this point, toType is an array.
        if (toType instanceof ConstArrayType) {
            // ?1 const[] = ?2 const[]
            // Let the base language check whether ?2 is assignable to ?1.
            return super.isImplicitCastValidImpl(toType);
        }

        // From this point, toType is a non-const array.
        // ?1[] = ?2 const[]
        // We cannot assign a const array to a non-const array.
        return false;
    }

    @Override
    public boolean isCastValidImpl(Type toType) {
        if (!toType.isArray()) {
            // ?1 = ?2 const[]
            // This const array type can be cast to ?1 only if ?1 is Object.
            // Let the base language check this fact.
            return super.isCastValidImpl(toType);
        }

        // From this point, toType is an array.
        if (toType instanceof ConstArrayType) {
            // ?1 const[] = ?2 const[]
            // Let the base language check whether ?2 can be cast to ?1.
            return super.isCastValidImpl(toType);
        }

        // From this point, toType is a non-const array.
        // ?1[] = ?2 const[]
        // We cannot cast a const array to a non-const array.
        return false;
    }

    @Override
    public String toString() {
        String result = base.toString();
        if (base instanceof ConstArrayType) {
            // If base is also a ConstArrayType, the keyword "const" would
            // have been displayed, so just add additional dimension here.
            result += "[]";
        }
        else result += " const[]";
        return result;
    }
}

Exercise

Not all semantic changes have been implemented. Specifically, the following checks must be implemented:

Nonconstant arrays are invariant.
A nonconstant array can be assigned to a constant array if the base type of the nonconstant array is a subtype of the base type of the constant array.
Nonconstant arrays cannot be cast to nonconstant arrays of different types.

Therefore, ArrayType_c must be extended to handle these changes. Implement these changes in class CArrayArrayType_c.

Hint: + Reveal...

Remember to complete all the equality predicates as shown in ConstArrayType_c. Don't forget to let the type system know about this new type. Method createArrayType in TypeSystem_c should be of interest here.

Solution: + Reveal...

First, define the following interface:

CArrayArrayType.java

Next, implement the interface:

CArrayArrayType_c.java

Finally, add this method override in CArrayTypeSystem_c:

    @Override
    public ArrayType createArrayType(Position pos, Type base) {
        // Use carray's version of ArrayType to distinguish between const and
        // non-const array types.
        return new CArrayArrayType_c(this, pos, base);
    }

Now, all test cases should pass. That means our implementation of CArray respects our designed semantics. Congratulations on building a working language extension in Polyglot!

Next, we will explore the language dispatcher, which ensures that the correct implementation of AST operations gets chosen, which in turn ensures the correctness of the language extension. We will also learn that language dispatchers can be extended to add new operations on ASTs, thereby supporting new compiler passes, which are useful if we would like to perform an analysis that does not exist in the base language, or if we would like to prepare the AST for later phases of the compiler, such as translation to other languages.