ValueType.java

package edu.udel.cis.vsl.tass.dynamic.impl.type;

import java.util.Collection;
import java.util.LinkedList;

import edu.udel.cis.vsl.tass.dynamic.IF.type.PrimitiveValueTypeIF;
import edu.udel.cis.vsl.tass.dynamic.IF.type.ValueTypeIF;
import edu.udel.cis.vsl.tass.dynamic.IF.value.ValueIF;
import edu.udel.cis.vsl.tass.model.IF.type.TypeIF.TypeKind;
import edu.udel.cis.vsl.tass.morph.Morphic;
import edu.udel.cis.vsl.tass.morph.MorphicObject;
import edu.udel.cis.vsl.tass.symbolic.IF.type.SymbolicTypeIF;

/**
 * The value type may be considered a node in a directed graph. The edges in the
 * directed graph come from the "child" relation. What makes things complicated
 * is there may be cycles in this graph, to allow for types like linked lists.
 * 
 * @author siegel
 * 
 */
public abstract class ValueType extends MorphicObject implements ValueTypeIF {

	final static Collection<ValueType> EMPTY_SET = new LinkedList<ValueType>();

	/**
	 * Is this a (locally) complete type, i.e., are all componetns of this type
	 * defined? An example of an incomplete type is a pointer type in which the
	 * base type has not yet been defined.
	 * 
	 * This is a local concept: it is not a recursive definition on the
	 * children.
	 */
	private boolean isComplete;

	/**
	 * For a compound type (e.g., array, record), the value types which are
	 * components of this one. Note that the child relation may contain cycles,
	 * because of data structures such as linked lists.
	 */

	private Morphic[] children;

	/**
	 * Extrinsic data: the cached symbolic type corresponding to this value
	 * type. It can be cached as long as this value type is committed, because
	 * after that point the state cannot change in any way which would change
	 * the symType.
	 */
	private SymbolicTypeIF symType = null;

	/** An idea number unique among all instances of ValueType. */
	private int instanceId;

	/**
	 * For a canonic ValueType object, an ID number unique among all canonic
	 * ValueType objects.
	 */
	private int canonicalId = -1;

	/**
	 * Extrinsic data: the cached undefined value corresponding to this type.
	 * Like hashCode, it will only be cached if this type is committed. It will
	 * also be canonicalized if this type is canonicalized.
	 * 
	 * */
	private ValueIF undefinedValue = null;

	/**
	 * Is this type or any type reachable from it a reference type? This is
	 * extrinsic data, initialized at instantiation and never changed.
	 */
	protected boolean containsReferences;

	/**
	 * Used in various recursive procedures to prevent infinite recursion due to
	 * cycles in children graph.
	 */
	private boolean flag = false;

	protected int classHashCode = getClass().hashCode();

	ValueType(int instanceId, boolean isComplete, Morphic[] children) {
		this.isComplete = isComplete;
		this.instanceId = instanceId;
		assert children != null;
		this.children = children;
		if (this instanceof ReferenceValueType) {
			containsReferences = true;
		} else {
			containsReferences = false;
			for (Morphic child : children) {
				if (child != null && child instanceof ValueType
						&& ((ValueType) child).containsReferences) {
					containsReferences = true;
					break;
				}
			}
		}
	}

	@Override
	protected void commitChildren() {
		int numChildren = numChildren();

		for (int i = 0; i < numChildren; i++) {
			Morphic child = getChild(i);

			if (child != null)
				child.commit();
		}
	}

	boolean getFlag() {
		return flag;
	}

	void setFlag(boolean value) {
		flag = value;
	}

	@Override
	public int instanceId() {
		return instanceId;
	}

	@Override
	public int canonicalId() {
		return canonicalId;
	}

	public int numChildren() {
		return children.length;
	}

	public Morphic getChild(int i) {
		return children[i];
	}

	public void setChild(int index, Morphic component) {
		children[index] = component;
		if (component instanceof ReferenceValueType)
			containsReferences = true;
	}

	boolean isComplete() {
		return isComplete;
	}

	void makeComplete() {
		isComplete = true;
	}

	void setSymbolicType(SymbolicTypeIF symType) {
		this.symType = symType;
	}

	SymbolicTypeIF getSymbolicType() {
		assert isCommitted();
		return symType;
	}

	public void setCanonicalId(int id) {
		assert isCanonic();
		this.canonicalId = id;
	}

	public ValueIF getUndefinedValue() {
		return undefinedValue;
	}

	public void setUndefinedValue(ValueIF value) {
		assert isCommitted();
		undefinedValue = value;
	}

	/**
	 * Returns a hash code which is a function of this value type and the set of
	 * value types that are reachable from this one but not in stack. This is a
	 * value which is invariant under value type graph isomorphism.
	 * 
	 * This method should only be called if this ValueType is "reach complete",
	 * i.e., no value type reachable from this one (including this itself) is an
	 * incomplete type.
	 * 
	 * @param stack
	 * @return
	 */
	protected int isomorphismHashCode() {
		if (getFlag()) {
			return 0;
		} else {
			int result = classHashCode;

			setFlag(true);
			for (Morphic child : children)
				if (child != null) {
					if (child instanceof ValueType) {
						result += 2 * ((ValueType) child).isomorphismHashCode();
					} else {
						result += child.hashCode();
					}
				}
			return result;
		}
	}

	/**
	 * Returns a hash code which is a function of this value type and the set of
	 * value types that are reachable from this one. This is a value which is
	 * invariant under value type graph isomorphism: if
	 * this.isIsomorphicTo(that) then this.isomorphismHashCode() will equal
	 * that.isomorphismHashCode().
	 * 
	 * This method should only be called if this ValueType is "complete", i.e.,
	 * no value type reachable from this one (including this itself) is an
	 * instance of IncompleteReferenceValueTypeIF.
	 */
	@Override
	protected int computeHashCode() {
		assert isComplete();

		int result = isomorphismHashCode();

		turnOffFlags();
		return result;
	}

	/**
	 * Sets flag to false for all nodes reachable from this one, assuming the
	 * set of off nodes is closed. (If a node's flag is false, then all of its
	 * children's flags are false.)
	 */
	private void turnOffFlags() {
		if (!getFlag())
			return;
		setFlag(false);

		for (Morphic child : children) {
			if (child != null && child instanceof ValueType)
				((ValueType) child).turnOffFlags();
		}
	}

	/**
	 * Determines whether this value type object is isormophic to the given one.
	 * 
	 * Uses the flags. Hopefully no one else will be using them while this is
	 * execution.
	 */
	boolean isIsomorphicTo(ValueType that) {
		assert isComplete();
		assert that.isComplete();

		if (this == that || getFlag())
			return true;
		if (this.isCanonic() && that.isCanonic())
			return this == that;
		setFlag(true);
		if (classHashCode != that.classHashCode)
			return false;

		int numChildren = numChildren();

		if (numChildren != that.numChildren())
			return false;
		for (int i = 0; i < numChildren; i++) {
			Morphic thisChild = getChild(i);
			Morphic thatChild = that.getChild(i);

			if (thisChild == null) {
				if (thatChild != null)
					return false;
			} else {
				if (thatChild == null)
					return false;
				if (thisChild instanceof ValueType) {
					if (!(thatChild instanceof ValueType && ((ValueType) thisChild)
							.isIsomorphicTo((ValueType) thatChild)))
						return false;
				} else {
					if (!thisChild.equals(thatChild))
						return false;
				}
			}
		}
		return true;
	}

	/**
	 * Returns true iff the value type graph consisting of all value types
	 * reachable from this one is isomorphic to the value type graph consisting
	 * of all value types reachable from that one.
	 * 
	 * @param that
	 * @return
	 */
	@Override
	protected boolean computeEquals(Morphic component) {
		if (this == component)
			return true;
		if (component instanceof ValueType) {
			ValueType that = (ValueType) component;
			boolean result = isIsomorphicTo(that);

			turnOffFlags();
			return result;
		}
		return false;
	}

	abstract String stringRecursive();

	@Override
	public String toString() {
		String result = stringRecursive();

		turnOffFlags();
		return result;
	}

	/**
	 * Does this value type contain (in any of its components, transitively
	 * closed) any reference types?
	 */
	@Override
	public boolean containsReferences() {
		return containsReferences;
	}

	@Override
	public boolean isInteger() {
		return this instanceof PrimitiveValueTypeIF
				&& (((PrimitiveValueTypeIF) this).type().kind() == TypeKind.INTEGER);
	}

	@Override
	public boolean isChar() {
		return this instanceof PrimitiveValueTypeIF
				&& (((PrimitiveValueTypeIF) this).type().kind() == TypeKind.CHAR);

	}
}