/* aux-type.cc: Type-related implementations.			*/

/* Copyright (C) 1996, Paul N. Hilfinger.  All Rights Reserved.		*/


#include <fstream>
#include <iomanip>
#include <map>
#include <string>
#include "AST.h"
#include "compiler.h"
#include "template.h"
#include "CfHeader.h"
#include "CfSource.h"
#include "IncludeOnce.h"
#include "Substitution.h"
#include "decls.h"
#include "errors.h"
#include "code.h"
#include "code-grid.h"
#include "code-point.h"
#include "code-util.h"
#include "decimalString.h"
#include "pseudocode.h"
#include "sharing.h"
#include "string-erase.h"
#include "string-utils.h"

typedef Common::Modifiers Modifiers;

extern bool javaDefinedType(const TreeNode *);


TypeNode* arithPromoteType (TypeNode* type)
{
  switch (type->kind()) {
  case TypeNode::CharKind:
  case TypeNode::ShortKind:
  case TypeNode::ByteKind:
  case TypeNode::IntKind:
    return theIntType;
  default:
    return type;
  }
}

TypeNode* arithPromoteType (TypeNode* type0, TypeNode* type1)
{
  if (type0->kind() == TypeNode::DoubleKind ||
      type1->kind() == TypeNode::DoubleKind)
    return theDoubleType;
  if (type0->kind() == TypeNode::FloatKind ||
      type1->kind() == TypeNode::FloatKind)
    return theFloatType;
  if (type0->kind() == TypeNode::LongKind ||
      type1->kind() == TypeNode::LongKind)
    return theLongType;
  if (type0->kind() == TypeNode::BoolKind ||
      type1->kind() == TypeNode::BoolKind)
    return theBoolType;
  return theIntType;
}

string TreeNode::unqualifiedTypeName() const
{
  return *decl()->name();
}

string TypeNameNode::unqualifiedTypeName() const
{
  if (decl() != NULL) return *decl()->name();
  else { /* PR584: decl may be NULL inside a template basis */
    TreeNode *n = name();
    string res = *n->ident();
    n = n->qualifier();
                                                                                                       
    while (! n->absent()) {                                                                            
      if (n->ident()->size() > 0)                                                                      
        res = *n->ident() + '.' + res;                                                                 
      n = n->qualifier();                                                                              
    }                                                                                                  
    return res;                                                                                  
  }
}

string TreeNode::typeName() const
{
  return unqualifiedTypeName();
}

string TreeNode::signature() const
{
  undefined("signature");
  return "";
}

string TreeNode::formalSignature() const
{
  undefined("formalSignature");
  return "";
}

bool TreeNode::hasFormalSignature() const
{
  return false;
}

				/* TypeNode members */

bool TypeNode::isCallableWith (Modifiers, const TreeNode* ) const
{
  undefined("isCallableWith");
  return false;
}

Common::Kind TypeNode::kind() const
{
  undefined("kind");
  return (Kind) 0;
}


TypeNode *TypeNode::indexType() const
{
  undefined("indexType");
  return NULL;
}

int TypeNode::tiArity() const
{
  undefined("tiArity");
  return 0;
}

TypeDecl *TypeNode::decl() const
{
  undefined("decl");
  return 0;
}

void TypeNode::print (ostream& os, unsigned depth) const
{
  indent(os, depth);
  os << '(' << oper_name();
  os << ':' << typeName() << ':';
  for (int i = 0; i < arity(); i += 1) {
    os << '\n';
    children[i]->print (os, depth + 1);
  }
  os << ')';
  
}

bool TreeNode::isTypeNode() const
{
  return false;
}

bool TypeNode::isTypeNode() const
{
  return true;
}

bool TypeNode::isPrimitive() const
{
  return (kind() & (CharKind | ByteKind | ShortKind | IntKind | LongKind |
		    FloatKind | DoubleKind | BoolKind)) != 0;
}

bool TypeNode::isReference() const
{
  /* HACK: avoid calling kind() on TemplateInstanceTypeNodes, since it may
   * fail early in compilation (PR 444, 520, 535)
   * PR576: note the hack below is a white-lie - we don't actually know
   * we have a reference type until after name resolution because the 
   * template may bind to an immutable. Hopefully we should always
   * have complete information by the time the difference matters, 
   */
  if (isTemplateInstanceTypeNode(this) && decl() == NULL) return true;
  return (kind() & (NullKind | ClassKind | InterfaceKind)) != 0;
}

bool TypeNode::hasReference() const
{
  return isReference();
}

bool TypeNode::isImmutable() const
{
  return kind() == ImmutableKind;
}

bool TypeNode::isArithType() const
{
  return (kind() & (CharKind | ByteKind | ShortKind | IntKind | LongKind |
		    FloatKind | DoubleKind)) != 0;
}

bool TypeNode::isFloatType() const
{
  return (kind() & (FloatKind | DoubleKind)) != 0;
}

bool TypeNode::isIntegralType() const
{
  return (kind() & (CharKind | ByteKind | ShortKind | IntKind | LongKind)) != 0;
}

bool TypeNode::isStringType() const
{
  return typeIdentNM(StringDecl->asType());
}

bool TypeNode::isAssignableFromExpr(TreeNode *with) const
{
  return isAssignableFromType(with->declaredType()) ||
    isAssignableFromConstant(with);
}

static bool isLocalWidening(const TypeNode *T0, const TypeNode *T1)
// Return: true if T0 is "at least as global" as T1
//   single is ignored here because it has rather special rules
//   (see st-single.cc)
{
  assert( T0->hasReference() == T1->hasReference() );
  if (T0->hasReference())
    return conformsTo( T1->modifiers(), T0->modifiers() );
  else
    return conformsTo( T1->sharing(), T0->sharing() );
}

static bool sameQualifiersNS(const TypeNode *T0, const TypeNode *T1)
// Return: true if T0 and T1 have equivalent type qualifiers,
// excluding "single"
{
  if (T0->sharing() != T1->sharing())
    return false;
  else if (T0->hasReference() || T1->hasReference())
    return T0->isLocal() == T1->isLocal();
  else
    return true;
}

static bool sameQualifiers(const TypeNode *T0, const TypeNode *T1)
// Return: true if T0 and T1 have equivalent type qualifiers,
// including "single"
{
  return sameQualifiersNS( T0, T1 )
    && T0->isSingle() == T1->isSingle();
}

bool TypeNode::isAssignableFromType (const TypeNode* T1) const
{
  // This function dispatches on the kind of both arguments. What is more,
  // the kinds don't match the classes. So its all done with switches...
  if (isPrimitive())
    // table driven for primitive types
    return (kind() & T1->kindsAssignableTo()) != 0;
 
  /*
   * Assignments from rectangular domains to domains are allowed if
   * they have the same arity.  This is more clearly expressed as a
   * special case instead of threading it into the big switch
   * statement below.
   */
  if (isDomainOrRectDomainType() && T1->isRectDomainType()
      && tiArity() == T1->tiArity())
    return true;

  // Grids can have null assigned to them.
  if (isTitaniumArrayType() && (T1->kind() == Common::NullKind))
    return true;

  switch (kind())
    {
    case Common::ClassKind:
      switch (T1->kind())
	{
	case Common::NullKind: return isReference(); // not immutable
	case Common::InterfaceKind:
	  return decl() == ObjectDecl && isLocalWidening(this, T1);
	case Common::ClassKind:
	  // We have to avoid calling decl() on Java array types, since it may
	  // be too early to instantiate them.
	  if (isJavaArrayType())
	    return isLocalWidening(this, T1) && T1->isJavaArrayType() &&
	      (elementType()->isReference() ? 
	       // only arrays of references are element convertible
	       elementType()->isAssignableFromType(T1->elementType()) :
	       elementType()->typeIdentNM(T1->elementType())) &&
	      sameQualifiers(elementType(), T1->elementType());
	  else if (T1->isJavaArrayType())
	    return isLocalWidening(this, T1) && isSubClass(JavaArrayDecl, decl());
	  else
	    return isLocalWidening(this, T1) && isSubClass(T1->decl(), decl());
	case Common::ArrayInitializerKind: return isArrayType();
	default: return false;
	}
    case Common::InterfaceKind:
      switch (T1->kind())
	{
	case Common::NullKind: return true;
	case Common::ClassKind:
	  return implements(T1->isJavaArrayType() ? JavaArrayDecl : 
			    T1->decl(), decl()) && isLocalWidening(this, T1);
	case Common::InterfaceKind:
	  return isSuperInterface(decl(), T1->decl()) && isLocalWidening(this, T1);
	default: return false;
	}
    case Common::NullKind:
      return false;
    case Common::ImmutableKind:
      // special stuff to support the special case of local titanium arrays
      return typeIdentNM(T1) && isLocalWidening(this, T1);
    default:
      fatal_error("");
      return false;
    }
}

Decision TypeNode::isCastableFromWithoutSharing (const TypeNode* T1) const
{
  // This function dispatches on the kind of both arguments. What is more,
  // the kinds don't match the classes. So its all done with switches...

  if (isPrimitive())
    // table driven for primitive types
    return ((kind() & T1->kindsCastableTo()) != 0) ? Yes : No;

  /*
   * Conversions between domains and rectangular domains are allowed
   * if they have the same arity.  This is more clearly expressed as a
   * special case instead of threading it into the big switch
   * statement below.
   */
  if (isDomainOrRectDomainType() && T1->isDomainOrRectDomainType()
      && tiArity() == T1->tiArity())
      return Yes;

  // null can be cast to grid types and vice versa.
  if (isTitaniumArrayType() && (T1->kind() == Common::NullKind) ||
      T1->isTitaniumArrayType() && (kind() == Common::NullKind))
    return Yes;

  switch (kind())
    {
    case Common::NullKind:
      return T1->isReference() ? Yes : No;
    case Common::ClassKind:
      switch (T1->kind())
	{
	case Common::NullKind:
	  // not immutable
	  return isReference() ? Yes : No;
	case Common::InterfaceKind:
	  return (!(decl()->modifiers() & Final) ||
		  implements(decl(), T1->decl()))
	    ? Maybe : No;
	case Common::ClassKind:
	  return (isSubClass(T1->decl(), decl()) ||
		  isSubClass(decl(), T1->decl()) ||
		  isJavaArrayType() && T1->isJavaArrayType() &&
		  elementType()->isCastableFrom(T1->elementType()) &&
		  sameQualifiers(elementType(), T1->elementType()))
	    ? Maybe : No;
	default: return No;
	}
    case Common::InterfaceKind:
      switch (T1->kind()) {
      case Common::NullKind: return Yes;
      case Common::ClassKind: {
	Decl* decl1 = T1->decl();
	bool isFinal1 = (decl1->modifiers() & Final) != 0;

	return (!isFinal1 || implements (decl1, decl())) ? Maybe : No;
      }
      case Common::InterfaceKind:
	/* ?? should check:  j5.5:
	   If T is an interface type and if T and S contain methods with
	   the same signature (j8.4.2) but different return types, then a
	   compile-time error occurs. */
	return Maybe;
      default: return No;
      }
    case Common::ImmutableKind:
      // Ignore qualifiers because of titanium arrays
      // (and, for that matter, cases like T -> T single)
      if (typeIdentNM(T1))
	if (isTitaniumArrayType())
	  return Maybe;
	else
	  return Yes;
      else
	return No;
    default:
      fatal_error("");
      return No;
    }
}

bool TypeNode::isCastableFrom (const TypeNode* T1) const
{
  switch (isCastableFromWithoutSharing( T1 ))
    {
    case No:
      return false;
    case Yes:
      return true;
    case Maybe:
      return conformsTo( T1->sharing(), sharing() );
    }
  
  assert( 0 );
  return false;
}

bool TypeNode::isComparableTo (const TypeNode* T1) const
{
  switch (isCastableFromWithoutSharing( T1 ))
    {
    case No:
      return false;
    case Yes:
      return true;
    case Maybe:
      return T1->sharing() == sharing()
	|| T1->sharing() == Polyshared
	|| sharing() == Polyshared;
    }
  
  assert( 0 );
  return false;
}

bool TypeNode::isAssignableFromConstant(const TreeNode *) const
{
  return false;
}

Modifiers TypeNode::modifiers() const
{
  return _modifiers;
}

void TypeNode::modifiers (Modifiers v)
{
  // We are rather trusting here; it is only during type checking that
  // TypeNode::checkQualifiers() will be called to see if the
  // modifiers actually make any sense.

  _modifiers = v;
  _cType = 0;
}
  
TypeNode *TypeNode::newModifiers(Modifiers v) const
// Returns: a copy of this type with modifiers 'v'
{
  TypeNode *t = clone();
  t->modifiers(v);
  return t;
}

TypeNode *TypeNode::withModifiers(Modifiers desired)
{
  return (desired == modifiers())
    ? this : newModifiers(desired);
}

TypeNode const *TypeNode::withModifiers(Modifiers desired) const
{
  return (desired == modifiers())
    ? this : newModifiers(desired);
}

TypeNode *TypeNode::addModifiers(Modifiers delta)
{
  return withModifiers( (Modifiers) (modifiers() | delta) );
}

TypeNode const *TypeNode::addModifiers(Modifiers delta) const
{
  return withModifiers( (Modifiers) (modifiers() | delta) );
}

TypeNode *TypeNode::removeModifiers(Modifiers delta)
{
  return withModifiers( (Modifiers) (modifiers() & ~delta) );
}

TypeNode const *TypeNode::removeModifiers(Modifiers delta) const
{
  return withModifiers( (Modifiers) (modifiers() & ~delta) );
}

string TypeNode::typeName() const
{
  return singleName(unqualifiedTypeName());
}

string TypeNode::singleName(string s) const
{
  if (modifiers() & Single)
    s += " single";
  if (modifiers() & Local && hasReference())
    s += " local";
  if (sharing() != Shared)
    {
      s += ' ';
      s += sharing();
    }

  return s;
}


/* TypeListNode members */

string TypeListNode::signature() const
{
  string res;
  for (int i = 0; i < arity(); i += 1)
    res += child (i)->signature();
  return res;
}

string TypeListNode::typeName() const
{
  return '(' + TypeListToString( this ) + ')';
}

/* BoolTypeNode members */

string BoolTypeNode::unqualifiedTypeName() const
{
  return "boolean";
}

TypeNode::Kind BoolTypeNode::kind() const
{
  return Common::BoolKind;
}

TypeNode::Kind BoolTypeNode::kindsAssignableTo() const
{
  return Common::BoolKind;
}

TypeNode::Kind BoolTypeNode::kindsCastableTo() const
{
  return Common::BoolKind;
}

string BoolTypeNode::signature() const
{
  static string sig = "Z";
  return sig;
}

string BoolTypeNode::formalSignature() const
{
  return signature();
}

bool BoolTypeNode::hasFormalSignature() const
{
  return true;
}

/* CharTypeNode members */

string CharTypeNode::unqualifiedTypeName() const
{
  return "char";
}

TypeNode::Kind CharTypeNode::kind() const
{
  return Common::CharKind;
}

TypeNode::Kind CharTypeNode::kindsAssignableTo() const
{
  return (Kind) (Common::CharKind | Common::IntKind | Common::LongKind | Common::FloatKind | Common::DoubleKind);
}

TypeNode::Kind CharTypeNode::kindsCastableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::CharKind | Common::IntKind | Common::LongKind |
		 Common::FloatKind | Common::DoubleKind);
}

string CharTypeNode::signature() const
{
  static string sig = "C";
  return sig;
}

string CharTypeNode::formalSignature() const
{
  return signature();
}

bool CharTypeNode::hasFormalSignature() const
{
  return true;
}

bool CharTypeNode::isAssignableFromConstant(const TreeNode *with) const
{
  return with->isIntConstant(0, 65535);
}

/* ByteTypeNode members */

string ByteTypeNode::unqualifiedTypeName() const
{
  return "byte";
}

TypeNode::Kind ByteTypeNode::kind() const
{
  return Common::ByteKind;
}

TypeNode::Kind ByteTypeNode::kindsAssignableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::IntKind | Common::LongKind 
		 | Common::FloatKind | Common::DoubleKind);
}

TypeNode::Kind ByteTypeNode::kindsCastableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::CharKind | Common::IntKind | Common::LongKind |
		 Common::FloatKind | Common::DoubleKind);
}

string ByteTypeNode::signature() const
{
  static string sig = "B";
  return sig;
}

string ByteTypeNode::formalSignature() const
{
  return signature();
}

bool ByteTypeNode::hasFormalSignature() const
{
  return true;
}

bool ByteTypeNode::isAssignableFromConstant(const TreeNode *with) const
{
  return with->isIntConstant(-128, 127);
}

/* ShortTypeNode members */

string ShortTypeNode::unqualifiedTypeName() const
{
  return "short";
}

TypeNode::Kind ShortTypeNode::kind() const
{
  return Common::ShortKind;
}

TypeNode::Kind ShortTypeNode::kindsAssignableTo() const
{
  return (Kind) (Common::ShortKind | Common::IntKind | Common::LongKind | Common::FloatKind | Common::DoubleKind);
}

TypeNode::Kind ShortTypeNode::kindsCastableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::CharKind | Common::IntKind | Common::LongKind |
		 Common::FloatKind | Common::DoubleKind);
}

string ShortTypeNode::signature() const
{
  static string sig = "S";
  return sig;
}

string ShortTypeNode::formalSignature() const
{
  return signature();
}

bool ShortTypeNode::hasFormalSignature() const
{
  return true;
}

bool ShortTypeNode::isAssignableFromConstant(const TreeNode *with) const
{
  return with->isIntConstant(-32768, 32767);
}

/* IntTypeNode members */

string IntTypeNode::unqualifiedTypeName() const
{
  return "int";
}

TypeNode::Kind IntTypeNode::kind() const
{
  return Common::IntKind;
}

TypeNode::Kind IntTypeNode::kindsAssignableTo() const
{
  return (Kind) (Common::IntKind | Common::LongKind | Common::FloatKind | Common::DoubleKind);
}

TypeNode::Kind IntTypeNode::kindsCastableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::CharKind | Common::IntKind | Common::LongKind |
		 Common::FloatKind | Common::DoubleKind);
}

string IntTypeNode::signature() const
{
  static string sig = "I";
  return sig;
}

string IntTypeNode::formalSignature() const
{
  return signature();
}

bool IntTypeNode::hasFormalSignature() const
{
  return true;
}

/* FloatTypeNode members */

string FloatTypeNode::unqualifiedTypeName() const
{
  return "float";
}

TypeNode::Kind FloatTypeNode::kind() const
{
  return Common::FloatKind;
}

TypeNode::Kind FloatTypeNode::kindsAssignableTo() const
{
  return (Kind) (Common::FloatKind | Common::DoubleKind);
}

TypeNode::Kind FloatTypeNode::kindsCastableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::CharKind | Common::IntKind | Common::LongKind |
		 Common::FloatKind | Common::DoubleKind);
}

string FloatTypeNode::signature() const
{
  static string sig = "F";
  return sig;
}

string FloatTypeNode::formalSignature() const
{
  return signature();
}

bool FloatTypeNode::hasFormalSignature() const
{
  return true;
}

/* DoubleTypeNode members */

string DoubleTypeNode::unqualifiedTypeName() const
{
  return "double";
}

TypeNode::Kind DoubleTypeNode::kind() const
{
  return Common::DoubleKind;
}

TypeNode::Kind DoubleTypeNode::kindsAssignableTo() const
{
  return Common::DoubleKind;
}

TypeNode::Kind DoubleTypeNode::kindsCastableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::CharKind | Common::IntKind | Common::LongKind |
		 Common::FloatKind | Common::DoubleKind);
}

string DoubleTypeNode::signature() const
{
  static string sig = "D";
  return sig;
}

string DoubleTypeNode::formalSignature() const
{
  return signature();
}

bool DoubleTypeNode::hasFormalSignature() const
{
  return true;
}

/* LongTypeNode members */

string LongTypeNode::unqualifiedTypeName() const
{
  return "long";
}

TypeNode::Kind LongTypeNode::kind() const
{
  return Common::LongKind;
}

TypeNode::Kind LongTypeNode::kindsAssignableTo() const
{
  return (Kind) (Common::LongKind | Common::FloatKind | Common::DoubleKind);
}

TypeNode::Kind LongTypeNode::kindsCastableTo() const
{
  return (Kind) (Common::ByteKind | Common::ShortKind | Common::CharKind | Common::IntKind | Common::LongKind |
		 Common::FloatKind | Common::DoubleKind);
}

string LongTypeNode::signature() const
{
  static string sig = "J";
  return sig;
}

string LongTypeNode::formalSignature() const
{
  return signature();
}

bool LongTypeNode::hasFormalSignature() const
{
  return true;
}

/* TypeNameNode members */

TypeNode::Kind TypeNameNode::kind() const
{
  ClassDecl *d = decl();

  if (d)
    return d->kind();
  else
    return ClassKind;
}

bool TypeNameNode::hasReference() const
{
  return TypeNode::hasReference()
    || decl() == TiArrayDecl
    || decl() == TiArrayLDecl;
}

string TypeNameNode::signature() const
{
  return name()->signature();
}

string TemplateInstanceTypeNode::signature() const
{
  // BUG: this gives all template instantiations the same signature (that of the basis)
  // we probably want signatures to differ across instantiations by somehow including
  // the actuals, but Java lacks templates so it's not clear what this should look like
  // (especially for value-typed template actuals)
  return dtype()->signature();
}

bool TypeNameNode::isAssignableFromConstant(const TreeNode *with) const
{
  return decl() == StringDecl && isStringLitNode(with);
}

string NameNode::signature() const
{
  if (decl() != NULL)
    return decl()->signature();
  else {  /* Punt. */
    TreeNode* t;
    string res;

    res = *ident() + ';';
    t = qualifier();
	
    while (! t->absent()) {
      if (t->ident()->size() > 0)
	res = *t->ident() + '/' + res;
      t = t->qualifier();
    }
    return 'L' + res;
  }
}


/* ArrayTypeNode members */

bool ArrayTypeNode::isArrayType() const 
{
  return true;
}

bool ArrayTypeNode::hasReference() const
{
  return true;
}

Modifiers ArrayTypeNode::modifiers() const
{
  // Single is contagious in arrays
  if (elementType()->isSingle())
    return (Modifiers)(_modifiers | Single);
  else
    return _modifiers;
}


/* JavaArrayTypeNode members */

bool JavaArrayTypeNode::isJavaArrayType() const 
{
  return true;
}

TypeNode *JavaArrayTypeNode::indexType() const
{
  return theIntType;
}

TypeNode::Kind JavaArrayTypeNode::kind() const
{
  assert(!(JavaArrayDecl->modifiers() & Immutable));
  return Common::ClassKind;
}

string JavaArrayTypeNode::signature() const
{
  static string sig = "Q";
  return sig + elementType()->signature();
}

/* MethodTypeNode members */

TypeNode::Kind MethodTypeNode::kind() const
{
  return Common::MethodKind;
}

bool MethodTypeNode::hasReference() const
{
  return true;
}

bool MethodTypeNode::isCallableWith(Modifiers actualModifiers, const TreeNode* T1) const
{
  const TreeNode* formalTypes = paramTypes();
  
  if (T1->arity() != formalTypes->arity())
    return false;
  if (!conformsTo( actualModifiers, modifiers() ))
    return false;
  foriter2 (formal0, formalTypes->allTypes(),
	    formal1, T1->allTypes(), ConstTypeIter) {
    if (! (*formal0)->isAssignableFromType(*formal1))
      return false;
  }
  return true;
}

string MethodTypeNode::signature() const
{
  return '(' + paramTypes()->signature() + ')'
    + returnType()->signature();
}

Modifiers MethodTypeNode::modifiers() const
{
  // Method types are always "single"
  return (Modifiers)(_modifiers | Single);
}

string MethodTypeNode::unqualifiedTypeName() const
{
  return returnType()->typeName()
    + ' '
    + paramTypes()->typeName();
}

string MethodTypeNode::typeName() const
{
  string prefix;
  if (isLocal()) prefix += "local ";
  if (sharing() != Shared)
    {
      prefix += sharing();
      prefix += ' ';
    }

  return prefix + unqualifiedTypeName();
}

/* VoidTypeNode members */

string VoidTypeNode::unqualifiedTypeName() const
{
  return "void";
}

string VoidTypeNode::typeName() const
{
  return unqualifiedTypeName();
}

TypeNode::Kind VoidTypeNode::kind() const
{
  return Common::VoidKind;
}

TypeNode::Kind VoidTypeNode::kindsAssignableTo() const
{
  return (Kind) 0;
}

TypeNode::Kind VoidTypeNode::kindsCastableTo() const
{
  return (Kind) 0;
}

string VoidTypeNode::signature() const
{
  static string sig = "V";
  return sig;
}

string VoidTypeNode::formalSignature() const
{
  return signature();
}

bool VoidTypeNode::hasFormalSignature() const
{
  return true;
}

Modifiers VoidTypeNode::modifiers() const
{
  // Void types are always "single"
  return (Modifiers)(_modifiers | Single);
}

/* NullTypeNode members */

bool NullTypeNode::isNullType() const { return true; }

string NullTypeNode::unqualifiedTypeName() const
{
  return "null";
}

string NullTypeNode::typeName() const
{
  return "null";
}

TypeNode::Kind NullTypeNode::kind() const
{
  return Common::NullKind;
}

Modifiers NullTypeNode::modifiers() const
{
  // null is local
  return (Modifiers)(_modifiers | Local);
}

/* ArrayInitializerTypeNode members */

string ArrayInitializerTypeNode::unqualifiedTypeName() const
{
  return "arrayinitializer";
}

TypeNode::Kind ArrayInitializerTypeNode::kind() const
{
  return Common::ArrayInitializerKind;
}

				/* Titanium type-related  */

static int getArity(const TypeNode *type)
{
  TreeNode *expr = type->expr();

  if (expr->isIntConstant(1, INT_MAX))
    return (int)expr->literal().intValue();
  else
    return 0;
}

/* TitaniumArrayTypeNode */

bool TitaniumArrayTypeNode::isTitaniumArrayType() const 
{
  return true;
}

TypeNode *TitaniumArrayTypeNode::indexType() const
{
  return makePointType(tiArity());
}

TypeNode::Kind TitaniumArrayTypeNode::kind() const
{
  assert(TiArrayDecl->modifiers() & Immutable);
  assert(TiArrayLDecl->modifiers() & Immutable);
  return Common::ImmutableKind;
}

string TitaniumArrayTypeNode::signature() const
{
  static string sig = "T"; 
  return sig + elementType()->signature() + '_' + int2string(tiArity());
}

int TitaniumArrayTypeNode::tiArity() const
{
  return getArity(this);
}


/* PointTypeNode */

bool PointTypeNode::isArrayType() const 
{
  return true;
}

bool PointTypeNode::isWriteableArrayType() const 
{
  return false;
}

TypeNode *PointTypeNode::indexType() const
{
  return theIntType;
}

TypeNode *PointTypeNode::elementType() const
{
  return isSingle()
    ? theIntType->addModifiers( Single )
    : theIntType;
}

TypeNode::Kind PointTypeNode::kind() const
{
  assert(PointDecl->modifiers() & Immutable);
  return Common::ImmutableKind;
}

bool PointTypeNode::isPointType() const { return true; }

string PointTypeNode::signature() const
{
  return string(MANGLE_TYPE_MARKER) + MANGLE_TI_POINT_TYPE_MARKER +
    int2string(tiArity());
}

string PointTypeNode::formalSignature() const
{
  return signature();
}

bool PointTypeNode::hasFormalSignature() const
{
  return false;
}

int PointTypeNode::tiArity() const
{
  return getArity(this);
}

/* RectDomainTypeNode */

bool RectDomainTypeNode::isRectDomainType() const { return true; }

TypeNode::Kind RectDomainTypeNode::kind() const
{
  assert(RectDomainDecl->modifiers() & Immutable);
  return ImmutableKind;
}

string RectDomainTypeNode::signature() const
{
  return string(MANGLE_TYPE_MARKER) + MANGLE_TI_RECTDOMAIN_TYPE_MARKER +
    int2string(tiArity());  /* FIX ME */
}

string RectDomainTypeNode::formalSignature() const
{
  return signature();
}

bool RectDomainTypeNode::hasFormalSignature() const
{
  return false;
}

int RectDomainTypeNode::tiArity() const
{
  return getArity(this);
}

/* DomainTypeNode */

bool DomainTypeNode::isDomainType() const { return true; }

TypeNode::Kind DomainTypeNode::kind() const
{
  assert(!(DomainDecl->modifiers() & Immutable));
  return ClassKind;
}

string DomainTypeNode::signature() const
{
  return string(MANGLE_TYPE_MARKER) + MANGLE_TI_DOMAIN_TYPE_MARKER +
    int2string(tiArity()); /* FIX ME */
}

string DomainTypeNode::formalSignature() const
{
  return signature();
}

bool DomainTypeNode::hasFormalSignature() const
{
  return false;
}

int DomainTypeNode::tiArity() const
{
  return getArity(this);
}

/* Template instances */

string TemplateInstanceTypeNode::unqualifiedTypeName() const
{
  return TreeNode::unqualifiedTypeName()
    + "< " + TypeListToString( args() ) + " >";
}


Common::Kind TemplateInstanceTypeNode::kind() const
{
  return decl()->kind();
}


bool TemplateInstanceTypeNode::isPrimitive() const
{
  // Cannot call kind() if we don't have a decl yet.  But that's OK,
  // because even without a decl we know we can't be a primitive type.
  return false;
}

				/* Type comparison */

bool TreeNode::typeIdent(const TreeNode* T1) const
{
  return typeIdentNM(T1);
}

bool TypeNode::typeIdent(const TreeNode* T1) const
{
#if 0
  bool tINM = typeIdentNM(T1), sQ = sameQualifiers(this, (TypeNode *)T1);
  cout << "typeIdent(" << pseudocode(this) << ", " <<
    pseudocode(T1) << ") " << (tINM ? "1" : "0") << (sQ ? "1" : "0") << endl;
#endif
  return typeIdentNM(T1) && sameQualifiers(this, (TypeNode *)T1);
}

bool TreeNode::typeIdentNS(const TreeNode* T1) const
{
  return typeIdentNM(T1);
}

bool TypeNode::typeIdentNS(const TreeNode* T1) const
{
  return typeIdentNM(T1) && sameQualifiersNS(this, (TypeNode *)T1);
}

bool TreeNode::typeIdentNM(const TreeNode*) const
{
  undefined("typeIdentNM");
  return false;
}

bool TypeNode::typeIdentNM(const TreeNode* T1) const
{
  if (oper_name() != T1->oper_name())
    return false;

  foriter2 (child0, allChildren(), child1, T1->allChildren(),
	    ConstChildIter)
    if (! (*child0)->typeIdent(*child1))
      return false;

  return true;
}

bool TypeListNode::typeIdentNM(const TreeNode* T1) const
{
  if (oper_name() != T1->oper_name()
      || arity() != T1->arity())
    return false;

  foriter2 (child0, allChildren(), child1, T1->allChildren(),
	    ConstChildIter)
    if (!(*child0)->typeIdentNS(*child1))
      return false;

  return true;
}

bool TypeNameNode::typeIdentNM(const TreeNode* T1) const
{
  if (T1->oper_name() != oper_name())
    return false;
  else 
    return decl() == T1->decl();
}

bool TemplateInstanceTypeNode::typeIdentNM( const TreeNode *other ) const
{
  return oper_name() == other->oper_name()
    && dtype()->typeIdentNM(other->dtype()) /* HACK: redundant condition that helps with PR535 */
    && decl() == other->decl();
}

bool ExprNode::typeIdentNM(const TreeNode* T1) const
{
  // The only legal expressions in template arguments are literals
  // However, we want to continue compiling templates with bad
  // arguments, so we do need some imprecise approximation of 
  // expression equality (it should return false when comparing
  // with any literal)
  return T1->oper_name() == oper_name();
}

bool PrimitiveLitNode::typeIdentNM(const TreeNode* T1) const
{
  if (T1->oper_name() != oper_name())
    return false;
  else
    return literal().eq(T1->literal()).boolValue();
}

bool TreeNode::singleArgsIdent(const TreeNode* T1) const
{
  unimplemented("singleArgsIdent");
  return false;
}

bool TypeListNode::singleArgsIdent(const TreeNode* T1) const
{
  foriter2 (child0, allTypes(), child1, T1->allTypes(),
	    ConstTypeIter)
    if (!sameQualifiers(*child0, *child1))
      return false;

  return true;
}

				/* Inheritance-related */


bool implements (Decl* aClass, Decl* interface)
{
  foreach (intr, llist<Decl*>, *(aClass->interfaces())) {
    if (isSuperInterface (interface, *intr))
      return true;
  }
  if (aClass == ObjectDecl)
    return false;
  else
    return implements (aClass->superClass(), interface);
}

bool isSuperInterface (Decl* decl0, Decl* decl1)
{
  if (decl0 == decl1)
    return true;
  foreach (intr, llist<Decl*>, *(decl1->interfaces())) {
    if (isSuperInterface (decl0, *intr))
      return true;
  }
  return false;
}

bool isSubClass(Decl *decl0, Decl *decl1)
{
  if (decl0->category() != Decl::Class || decl1->category() != Decl::Class)
    return false;

  while (true) {
    if (decl1 == decl0)
      return true;
    if (decl0 == ObjectDecl || !decl0)
      return false;
    decl0 = decl0->superClass();
  }
}

/* Assuming that M0 and M1 are MethodDecls, true iff M0 is more specific */
/* (in the sense of 15.11.2.2) than M1.  Actually, the right term */
/* should be "no less specific than", but the Reference Manual is the */
/* Reference Manual. */
bool isMoreSpecific (const Decl* M0, const Decl* M1)
{
  TypeNode *t0 = M0->type(), *t1 = M1->type();
  TreeNode* params0 = t0->paramTypes();
  TreeNode* params1 = t1->paramTypes();
    
  if (params0->arity() != params1->arity())
    return false;

  if (!(M1->container()->asType()->isAssignableFromType(M0->container()->asType()) &&
	isLocalWidening(t1, t0)))
    return false;

  for (int i = params0->arity() - 1; i >= 0; i -= 1)
    if (!((TypeNode *)params1->child(i))->isAssignableFromType((TypeNode *)params0->child(i)))
      return false;

  return true;
}



/* For nodes that represent field accesses (ObjectFieldAccessNode, */
/* ThisFieldAccessNode, SuperFieldAccessNode) the type of the */
/* object that is accessed (e.g., for a node representing FOO.BAR, */
/* the type of FOO. */
TypeNode *TreeNode::accessedObjectType() const
{
  undefined("accessedObjectType");
  return NULL;
}


TypeNode *TypeFieldAccessNode::accessedObjectType() const
{
  return ftype()->decl()->asType();
}

TypeNode *ObjectFieldAccessNode::accessedObjectType() const
{
  if (isRewrittenQSFAN()) {
    Decl *sclass = object()->type()->decl()->superClass();
    if (!sclass) return object()->decl()->asType(); // as good as anything

    TypeNode *t = dynamic_cast<TypeNode *>(sclass->asType())->deepClone();
    t->modifiers( (Modifiers) (object()->type()->modifiers() & (Local | NonsharedQ | PolysharedQ)) );
    return t;
  } else {
    return object()->type();
  }
}

TypeNode *ThisFieldAccessNode::accessedObjectType() const
{
  // TBD: should cache this
  TypeNode *t = dynamic_cast<TypeNode *>(theClass())->deepClone();
  t->modifiers( (Modifiers) (flags() & (Local | NonsharedQ | PolysharedQ)) );
  return t;
}

TypeNode *SuperFieldAccessNode::accessedObjectType() const
{
  // Should cache this, but it gets rewritten half-way through the frontend, so not crucial
  Decl *sclass = theClass()->decl()->superClass();
  if (!sclass) return theClass()->decl()->asType(); // as good as anything

  TypeNode *t = dynamic_cast<TypeNode *>(sclass->asType())->deepClone();
  t->modifiers( (Modifiers) (flags() & (Local | NonsharedQ | PolysharedQ)) );
  return t;
}

TypeNode* ConstructorDeclNode::returnType() const
{
  return theVoidType;
}


// Assignability

static void finalError(TreeNode *field)
{
  field->error() << "attempt to assign to final field "
		 << *field->simpName()->ident() << endl;
}

static void typeError(TreeNode *dest, TreeNode *src)
{
  dest->error() << "bad type in assignment (" << dest->declaredType()->typeName()
		<< '=' << src->declaredType()->typeName() << ')' << endl;
}

void TreeNode::checkAssignable(TreeNode *, bool, bool, Decl*)
{
  error() << "target is not assignable" << endl;
}

void ArrayAccessNode::checkAssignable(TreeNode *with, bool, bool, Decl*)
{
  TypeNode *aType = array()->type();

  if (!aType->isWriteableArrayType())
    error() << "elements of type " << aType->typeName()
	    << " are not assignable" << endl;

  if (aType->isArrayType() && !aType->isLocal())
    {
      if (aType->elementType()->isLocal())
	error() <<
	  "arrays of local references cannot be assigned"
	  " when accessed by a global array reference" << endl;

      aType->checkShared( *this, "array", "modify" );
    }

  if (!type()->isAssignableFromExpr(with))
    typeError(this, with);
}

void ObjectNode::checkAssignable(TreeNode *with, bool, bool, Decl*)
{
  // ObjectNode is for locals and formals

  if (!decl()->assignable())
    error() << decl()->errorName() << " is not assignable" << endl;

  if (!type()->isAssignableFromExpr(with))
    typeError(this, with);
}

void FieldAccessNode::checkFieldAssignment(TreeNode &with)
{
  Decl &fieldDecl = *decl();
  const TypeNode &fieldType = *fieldDecl.type();
  const TypeNode &accessedType = *accessedObjectType();

  if (!(fieldDecl.modifiers() & Static)
      && accessedType.isReference()
      && !accessedType.isLocal())
    {
      if (fieldType.isLocal())
	error() << "local field " << *simpName()->ident()
		<< " cannot be assigned when accessed by a global reference" << endl;

      accessedType.checkShared( *this, "object", "modify" );
    }
	
  if (!type()->isAssignableFromExpr(&with))
    typeError(this, &with);
}

void FieldAccessNode::checkFinalFieldAssignment(bool ignoreInstanceFinal,
						bool ignoreStaticFinal)
{
  Decl &d = *decl();

  /* Static final fields can be assigned to if ignoreStaticFinal is true,
     and instance final fields can be assigned to if ignoreInstanceFinal
     is true, as long as the final field did not have an initializer */
  if ((d.modifiers() & Common::Final) &&
      (!d.source()->initExpr()->absent() ||
       ((d.modifiers() & Common::Static) && !ignoreStaticFinal) ||
       (!(d.modifiers() & Common::Static) && !ignoreInstanceFinal)))
    finalError(this);
}

void FieldAccessNode::checkAssignable(TreeNode *with, bool, bool, Decl*)
{
  checkFinalFieldAssignment(false, false);
  checkFieldAssignment(*with);
}

void TypeFieldAccessNode::checkAssignable(TreeNode *with, bool, 
					  bool ignoreStaticFinal,
					  Decl *currentClass)
{
  ignoreStaticFinal &= (ftype()->decl() == currentClass);
  checkFinalFieldAssignment(false, ignoreStaticFinal);
  checkFieldAssignment(*with);
}

void ObjectFieldAccessNode::checkAssignable(TreeNode *with, 
					    bool ignoreInstanceFinal, bool,
					    Decl *)
{
  ignoreInstanceFinal &= !strcmp( object()->oper_name(), "ThisNode" );
  checkFinalFieldAssignment(ignoreInstanceFinal, false);
  checkFieldAssignment(*with);
}

void ThisFieldAccessNode::checkAssignable(TreeNode *with, 
					  bool ignoreInstanceFinal, bool,
					  Decl *)
{
  checkFinalFieldAssignment(ignoreInstanceFinal, false);
  checkFieldAssignment(*with);
}


// PrimitiveLitNode type-related methods

bool TreeNode::isIntConstant(int , int ) const
{
  return false;
}

bool PrimitiveLitNode::isIntConstant(int from, int to) const
{
  return (literal().kind() & (ByteKind | ShortKind | CharKind | IntKind)) &&
    literal().intValue() >= from && literal().intValue() <= to;
}

string ExprNode::unqualifiedTypeName() const
{
  return "(expression)";
}

string PrimitiveLitNode::unqualifiedTypeName() const
{
  return literal().asString();
}



/* The TypeNode corresponding to signature S. */
TypeNode* signatureToType (const char*& s, llist<TypeNode *> *throws)
{
  switch (s[0]) {
  case 'B':
    s += 1;
    return theByteType;
  case 'C':
    s += 1;
    return theCharType;
  case 'D':
    s += 1;
    return theDoubleType;
  case 'F':
    s += 1;
    return theFloatType;
  case 'I':
    s += 1;
    return theIntType;
  case 'J':
    s += 1;
    return theLongType;
  case 'S':
    s += 1;
    return theShortType;
  case 'Z':
    s += 1;
    return theBoolType;
  case 'V':
    s += 1;
    return theVoidType;
  case '[':
    s += 1;
    return makeArrayType (signatureToType (s, NULL), 1);
  case 'L': {
    const char* e = ::strchr (s, ';');
    if (e == NULL) {
      Error() << "bad class signature (" << s << ')' << endl;
      s += strlen (s);
      return theIntType;
    }
    TypeNode* type =
      declFromFullClassName (string (s+1, e-s-1))->asType();
    s = e+1;
    return type;
  }
  case '(': {
    s += 1;
    llist<TypeNode*>* argTypes;
    argTypes = NULL;
    while (s[0] != ')' && s[0] != '\000')
      argTypes = cons (signatureToType (s, NULL), argTypes);
    if (s[0] != ')') {
      Error() << "bad format for method signature" << endl;
      return new MethodTypeNode (NULL, theVoidType, theVoidType, NULL);
    }
    s += 1;
    TypeNode *ret = signatureToType(s, NULL);
    return
      new MethodTypeNode (dreverse (argTypes),
			  ret, ret, throws);
  }
  default:
    Error() << "bad format for signature" << endl;
    return theIntType;
  }
}
	 
/* The TypeNode corresponding to signature S. */
TypeNode* signatureToType (string s, llist<TypeNode *> *throws)
{
  const char* p = s.c_str();
  return signatureToType (p, throws);
}

/* Return the type of METHOD, assuming that its parameter list and */
/* return type have been resolved. */
TypeNode* typeFromMethodDeclNode (TreeNode* method)
{
  llist<TypeNode*>* formalTypes;
  TypeNode *type;

  formalTypes = NULL;
  foriter (param, method->params()->allChildren(), TreeNode::ChildIter)
    formalTypes = cons((*param)->dtype(), formalTypes);
  type = new MethodTypeNode(dreverse(formalTypes),
			    method->returnType(),
			    method->returnType(), NULL);

  type->modifiers((Common::Modifiers)(method->flags() & (Common::Local
							 | Common::Single
							 | Common::NonsharedQ
							 | Common::PolysharedQ)));
  type->throws(method->throws()); // constructor wants a llist<..>
  return type;
}
   
/* True if two method types conflict (same parameter types and
   'local' specification for 'this') */
bool TypeNode::methodsConflict(TypeNode *with)
{
  return paramTypes()->typeIdent(with->paramTypes()) &&
    sameQualifiersNS(this, with);
}

/* Some Titanium type stuff */

// Return a new Point<n> type
TypeNode *makePointType(int n)
{
  return new PointTypeNode(new PrimitiveLitNode(Literal((int32)n)));
}

// Return a new Domain<n> type
TypeNode *makeDomainType(int n)
{
  return new DomainTypeNode(new PrimitiveLitNode(Literal((int32)n)));
}

// Return a new RectDomain<n> type
TypeNode *makeRectDomainType(int n)
{
  return new RectDomainTypeNode(new PrimitiveLitNode(Literal((int32)n)));
}

// Return a new T array<n> type
TypeNode *makeTiArrayType(TypeNode *T, TreeNode *dims, int i)
{
  if (i == dims->arity())
    return T;
  else
    {
      TypeNode *elemType = makeTiArrayType(T, dims, i + 1);
      TreeNode *di = dims->child(i);
      TreeNode *expr = di->expr();
      TypeNode *etype = expr->type();
      TypeNode *t;
      if (etype->isRectDomainType())
	t = new TitaniumArrayTypeNode(elemType,
					 new PrimitiveLitNode(Literal((int32)etype->tiArity())));
      else 
	t = new JavaArrayTypeNode (elemType);
      t->modifiers(di->flags());

      return t;
    }
}


static void fixArity(Decl *tiDecl, TreeNode *expr)
{
  /* Evil hack to make constant folding work with the 'arity' field */
  Decl *arity = tiDecl->environ()->lookupProper(ArityString, Decl::Field);
  TreeNode *arityNode = arity->source();
  arity->source(new FieldDeclNode(arityNode->dtype(), arityNode->simpName(),
				  arityNode->flags(), expr));
}

// Return the Point<n> decl
ClassDecl *getPointDecl(const TypeNode *type)
{
  ClassDecl *d = static_cast< ClassDecl * >(templateEnv.lookup( type ));
  if (d) {
    assert(d->category() == Decl::Class);
    return d;
  }

  TreeNode *expr = type->expr();
  if (!isPrimitiveLitNode(expr)) return NULL; // dim may be a template actual
  d = instantiateClass(PointDecl, type, &templateEnv, 
		       cons(new Substitution(TiArityDecl, expr),
		       cons(new Substitution(PointDecl,
					     new PointTypeNode(expr)))),
		        new PointTypeNode(expr));
  fixArity(d, expr);

  return d;
}

// Return the Domain<n> decl
ClassDecl *getDomainDecl(const TypeNode *type)
{
  ClassDecl *d = static_cast< ClassDecl * >(templateEnv.lookup( type ));
  if (d) {
    assert(d->category() == Decl::Class);
    return d;
  }

  TreeNode *expr = type->expr();
  if (!isPrimitiveLitNode(expr)) return NULL; // dim may be a template actual
  d = instantiateClass(DomainDecl, type, &templateEnv, 
		       cons(new Substitution(TiArityDecl, expr),
		       cons(new Substitution(PointDecl, 
					     new PointTypeNode(expr)),
		       cons(new Substitution(RectDomainDecl, 
					     new RectDomainTypeNode(expr)),
		       cons(new Substitution(DomainDecl,  
					     new DomainTypeNode(expr)))))),
		       new DomainTypeNode(expr));
  fixArity(d, expr);

  return d;
}

// Return the RectDomain<n> decl
ClassDecl *getRectDomainDecl(const TypeNode *type)
{
  ClassDecl *d = static_cast< ClassDecl * >(templateEnv.lookup( type ));
  if (d) {
    assert(d->category() == Decl::Class);
    return d;
  }

  TreeNode *expr = type->expr();
  if (!isPrimitiveLitNode(expr)) return NULL; // dim may be a template actual
  // Decl* super_class = getDomainDecl(new DomainTypeNode(expr));

  TreeNode *exprm1 = 
    new MinusNode(type->expr()->instantiate(NULL), new PrimitiveLitNode(Literal((int32)1)));
  exprm1 = exprm1->foldConstants();
  d = instantiateClass(RectDomainDecl, type, &templateEnv,
		       cons(new Substitution(TiArityDecl, expr),
		       cons(new Substitution(PointDecl, 
					     new PointTypeNode(expr)),
		       cons(new Substitution(RectDomainDecl, 
					     new RectDomainTypeNode(expr)),
		       cons(new Substitution(RectDomainM1Decl, 
					     new RectDomainTypeNode(exprm1)),
		       cons(new Substitution(DomainDecl, 
					     new DomainTypeNode(expr))))))),
		       new RectDomainTypeNode(expr));
  fixArity(d, expr);
  // d->superClass(super_class);

  return d;
}

// Return the T Array<n> decl
ClassDecl *getTiArrayDecl(const TypeNode *type)
{
  ClassDecl *d = static_cast< ClassDecl * >(templateEnv.lookup( type ));
  if (d) {
    assert(d->category() == Decl::Class);
    return d;
  }

  TypeNode *etype = type->elementType();
  TypeDecl * const edecl = etype->decl();
  if (!edecl) return 0;

  ClassDecl * const arrayTemplate = etype->isLocal() || edecl->containsEmbeddedLocals() ? TiArrayLDecl : TiArrayDecl;
  
  TreeNode *expr = type->expr();
  if (!isPrimitiveLitNode(expr)) return NULL; // dim may be a template actual
  TreeNode *exprm1 = 
    new MinusNode(expr->instantiate(NULL), new PrimitiveLitNode(Literal((int32)1)));
  exprm1 = exprm1->foldConstants();

  d = instantiateClass
    (arrayTemplate, type, &templateEnv,
     cons(new Substitution(TiArityDecl, expr),
     cons(new Substitution(PointDecl, new PointTypeNode(expr)),
     cons(new Substitution(DomainDecl, new DomainTypeNode(expr)),
     cons(new Substitution(RectDomainDecl, new RectDomainTypeNode(expr)),
     cons(new Substitution(RectDomainM1Decl, 
			   new RectDomainTypeNode(exprm1)),
     cons(new Substitution(TemplateArgDecl, etype),
     cons(new Substitution(TiArrayM1Decl,
			   new TitaniumArrayTypeNode (etype, exprm1)),
     cons(new Substitution(arrayTemplate,
			   new TitaniumArrayTypeNode (etype, expr)))))))))),
     new TitaniumArrayTypeNode (etype, expr));

  fixArity(d, expr);
  return d;
}

ClassDecl *getJavaArrayDecl(const TypeNode *type)
{
  ClassDecl *d = static_cast< ClassDecl * >(templateEnv.lookup( type ));
  if (d) {
    assert(d->category() == Decl::Class);
    return d;
  }

  TypeNode *etype = type->elementType();
  if (etype->decl())
    return instantiateClass(JavaArrayDecl, type, &templateEnv,
			    cons(new Substitution(TemplateArgDecl, etype),
				 cons(new Substitution(JavaArrayDecl, makeArrayType(etype, 1)))),
			    makeArrayType(etype, 1));
  else
    // postponed; element type is uninstantiated template
    return 0;
}



// 'this' is an array of array of .. of array of void type. 
// Replace the 'void' by 'to'
void TypeNode::setElementType(TypeNode *to)
{
  TypeNode *last = this;

  while (last->elementType()->kind() != VoidKind)
    last = last->elementType();
  last->elementType(to);
}

void createDomains_h()
{
  CfHeader hFile( "domains" );
  
  IncludeOnce once(hFile, "TITANIUM_POINTS");

  for (int arity = 1; arity <= MAX_TIARITY; arity++) {
    createPointMethods(hFile, arity);
  }
}

string TypeListToString(const TreeNode *t)
{
  string s;
  bool first = true;
  foriter (f, t->allChildren(), TreeNode::ConstChildIter) {
    if (first) first = false;
    else s += ", ";
    s += (*f)->typeName();
  }
  return s;
}