/*
 * TYPEQ.C
 *
 * (c)Copyright 1993-2014, Matthew Dillon, All Rights Reserved.  See the  
 *    COPYRIGHT file at the base of the distribution.
 *
 * WARNING: This needs to be almost standalone because it is also compiled
 *	    into libruntime.
 */

#include "defs.h"

/*
 * MatchType() -	Match two types
 *
 *	Match two types as if we wanted to cast type to super or use
 *	type as super.
 *
 *	SG_COMPAT_FULL		Type is a subclass, methods and storage are
 *				compatible (storage may be extended).
 *
 *	SG_COMPAT_PART		Type is a subclass, methods are compatible
 *				but storage is not.
 *
 *	SG_COMPAT_SUBCLASS	Type is a subclass, but the methods are
 *				not directly compatible (the methods that
 *				propogate down must be regenerated).
 *
 *	SG_COMPAT_FAIL		Type is not even a subclass
 *
 *	XXX we are skipping qualifiers
 */
int
MatchType(Type *super, Type *type)
{
	int r = SG_COMPAT_FULL;
	int loop = 0;

	while (super && type) {
		SemGroup *sg1 = NULL;
		SemGroup *sg2 = NULL;

		++loop;

		if (type->ty_Op != super->ty_Op) {
			if (super->ty_Op == TY_REFTO &&
			    type->ty_Op == TY_PTRTO) {
				super = super->ty_RefType.et_Type;
				type = type->ty_PtrType.et_Type;
				r = MatchType(super, type);
			} else {
				r = SG_COMPAT_FAIL;
			}
			break;
		}

		/*
		 * Relaxed storage qualifiers.  We are effectively casting
		 * to 'super'.  We can remove SF_CONST from super but not from
		 * type.
		 *
		 * NOTE: Actual casts may do more stringent tests.
		 */
		if (super->ty_SQFlags != type->ty_SQFlags) {
			if (loop > 1 &&
			    (type->ty_SQFlags & ~SF_IGNORE_MASK) !=
			    (super->ty_SQFlags & ~SF_RELAXING_MASK)) {
				r = SG_COMPAT_FAIL;
				break;
			}
		}

		switch(super->ty_Op) {
		case TY_CLASS:
			/*
			 * type can be a subclass of super
			 */
			if (type->ty_ClassType.et_SemGroup ==
			    super->ty_ClassType.et_SemGroup) {
				return(r);
			}
			r = type->ty_ClassType.et_SemGroup->sg_Compat;
#if 0
			if (r < SG_COMPAT_PART)
				r = SG_COMPAT_PART;
#endif
			while ((type = type->ty_ClassType.et_Super) != NULL) {
				if (type->ty_ClassType.et_SemGroup ==
				    super->ty_ClassType.et_SemGroup) {
					break;
				}
				if (r < type->ty_ClassType.et_SemGroup->sg_Compat)
					r = type->ty_ClassType.et_SemGroup->sg_Compat;
			}
			if (type == NULL)	/* not even a subclass */
				r = SG_COMPAT_FAIL;
			break;
		case TY_IMPORT:
			/*
			 * type can be a subclass of super
			 */
			if (type != super)
				r = SG_COMPAT_FAIL;
			break;
		case TY_CPTRTO:
			type = type->ty_CPtrType.et_Type;
			super = super->ty_CPtrType.et_Type;
			continue;
		case TY_PTRTO:
			type = type->ty_PtrType.et_Type;
			super = super->ty_PtrType.et_Type;
			continue;
		case TY_REFTO:
			type = type->ty_RefType.et_Type;
			super = super->ty_RefType.et_Type;
			continue;
		case TY_ARYOF:
			type = type->ty_AryType.et_Type;
			super = super->ty_AryType.et_Type;
			/* XXX */
			continue;
		case TY_COMPOUND:
			sg1 = super->ty_CompType.et_SemGroup;
			sg2 = type->ty_CompType.et_SemGroup;
			break;
		case TY_ARGS:
			sg1 = super->ty_ArgsType.et_SemGroup;
			sg2 = type->ty_ArgsType.et_SemGroup;
			break;
		case TY_VAR:
			r = MatchType(super->ty_VarType.et_Type,
				      type->ty_VarType.et_Type);
			break;
		case TY_PROC:
			{
				int v;

				r = MatchType(super->ty_ProcType.et_ArgsType, 
					      type->ty_ProcType.et_ArgsType);
				v = MatchType(super->ty_ProcType.et_RetType,
					      type->ty_ProcType.et_RetType);
				if (r < v)
					r = v;
			}
			break;
		case TY_DYNAMIC:
			break;
		case TY_STORAGE:
			if (type->ty_StorType.et_Bytes !=
			    super->ty_StorType.et_Bytes) {
				r = SG_COMPAT_SUBCLASS;
			}
			break;
		case TY_UNRESOLVED:
		default:
			dassert_type(super, 0);	/* can't happen */
			break;
		}
		if (sg1) {
			Declaration *sd = RUNE_FIRST(&sg1->sg_DeclList);
			Declaration *rd = RUNE_FIRST(&sg2->sg_DeclList);
			while (sd && rd) {
				int v = MatchDeclTypes(sd, rd);
				if (r < v)
					r = v;
				if (r == SG_COMPAT_FAIL)
					break;
				sd = RUNE_NEXT(sd, d_Node);
				rd = RUNE_NEXT(rd, d_Node);
			}
			if (sd || rd)
				r = SG_COMPAT_FAIL;
		}
		break;
	}
	return(r);
}

/*
 * SameType() - return 1 if the types are exactly the same, 0 if they are not.
 *
 *	The sqFlags for t2 may be overriden.  If you do not wish to override
 *	the sqFlags for t2, pass t2->ty_SQFlags for sqFlags.  The override
 *	only applies to the top level of the type.
 *
 *	Types can be aliased - for example, two different type structures
 *	may point to the same class data.
 *
 *	XXX this needs a lot of work.  We really need to guarentee
 *	some level of uniqueness for non-qualified type elements.
 */
int
SameType(Type *t1, Type *t2, int sqFlags2)
{
	for (;;) {
		if (t1 == t2)
			return(1);
		if (t1->ty_Op != t2->ty_Op)
			break;
		if (t1->ty_SQFlags != sqFlags2)
			break;
		switch(t1->ty_Op) {
		case TY_IMPORT:
			if (t1->ty_ImportType.et_SemGroup ==
			    t2->ty_ImportType.et_SemGroup)
			{
				return(1);
			}
			return(0);
		case TY_CLASS:
			if (t1->ty_ClassType.et_SemGroup ==
			     t2->ty_ClassType.et_SemGroup &&
			    SameType(t1->ty_ClassType.et_Super,
				     t2->ty_ClassType.et_Super, 0))
			{
				return(1);
			}
			return(0);
		case TY_CPTRTO:
			t1 = t1->ty_CPtrType.et_Type;
			t2 = t2->ty_CPtrType.et_Type;
			break;
		case TY_PTRTO:
			t1 = t1->ty_PtrType.et_Type;
			t2 = t2->ty_PtrType.et_Type;
			break;
		case TY_REFTO:
			t1 = t1->ty_RefType.et_Type;
			t2 = t2->ty_RefType.et_Type;
			break;
		case TY_ARYOF:
		case TY_VAR:
		case TY_COMPOUND:
		case TY_PROC:
			/* XXX */
			return(0);
		case TY_STORAGE:
		case TY_ARGS:
		case TY_UNRESOLVED:
		case TY_DYNAMIC:
			/* XXX */
			return(0);
		default:
			dassert_type(t1, 0);
			return(0);
		}
		sqFlags2 = t2->ty_SQFlags;
	}
	return(0);
}

/*
 * SimilarType() - like SameType(), but ignores storage qualifiers (except
 *		   SF_CONST) and if t2 is varargs, compares the original
 *		   version.
 *
 * Used when casting t2 (rhs) to t1 (lhs).
 */
int
SimilarType(Type *t1, Type *t2)
{
	int check_const = 0;


	if (t2->ty_Op == TY_VAR)
		t2 = t2->ty_VarType.et_Type;

	for (;;) {
		if (t1 == t2)
			return(1);

		/*
		 * Check for an incompatible constant conversion if we loop
		 * through a pointer or ref.  Allow compatibility for e.g.
		 * rvalues (const int)1 == (int)1
		 */
		if (check_const &&
		    (t2->ty_SQFlags & SF_CONST) &&
		    (t1->ty_SQFlags & SF_CONST) == 0) {
			return(0);
		}
#if 0
		/*
		 * Normally we fail if the ops do not match, but it is legal to
		 * cast a pointer (t2) to a reference type (t1) if the ref type
		 * is its superclass.  It is also legal to cast an array to a
		 * pointer or C pointer.
		 */
		if (t2->ty_Op != t1->ty_Op) {
			/*
			 * pointer->ref
			 */
			if (t2->ty_Op == TY_PTRTO && t1->ty_Op == TY_REFTO) {
				t1 = t1->ty_RefType.et_Type;
				t2 = t2->ty_PtrType.et_Type;
				if (MatchType(t1, t2) <= SG_COMPAT_PART) {
					return(1);
				}
				return(0);
			}
			/*
			 * array->pointer
			 */
			if (t2->ty_Op == TY_ARYOF && t1->ty_Op == TY_PTRTO) {
				t1 = t1->ty_PtrType.et_Type;
				t2 = t2->ty_AryType.et_Type;
				if (MatchType(t1, t2) <= SG_COMPAT_PART) {
					return(1);
				}
				return(0);
			}
			/*
			 * array->cpointer
			 */
			if (t2->ty_Op == TY_ARYOF && t1->ty_Op == TY_CPTRTO) {
				t1 = t1->ty_PtrType.et_Type;
				t2 = t2->ty_AryType.et_Type;
				if (MatchType(t1, t2) <= SG_COMPAT_PART) {
					return(1);
				}
				return(0);
			}
			break;
		}
#endif
		if (t2->ty_Op != t1->ty_Op)
			break;
		switch(t1->ty_Op) {
		case TY_IMPORT:
			if (t1->ty_ImportType.et_SemGroup ==
			    t2->ty_ImportType.et_SemGroup) {
				return(1);
			}
			return(0);
		case TY_CLASS:
			if (t1->ty_ClassType.et_SemGroup ==
			     t2->ty_ClassType.et_SemGroup &&
			    SameType(t1->ty_ClassType.et_Super,
			             t2->ty_ClassType.et_Super, 0))
			{
				return(1);
			}
			return(0);
		case TY_CPTRTO:
			t1 = t1->ty_CPtrType.et_Type;
			t2 = t2->ty_CPtrType.et_Type;
			break;
		case TY_PTRTO:
			t1 = t1->ty_PtrType.et_Type;
			t2 = t2->ty_PtrType.et_Type;
			break;
		case TY_REFTO:
			/*
			 * Reference types are similar if the lhs is a
			 * superclass of the rhs and partially compatible
			 * (only method call changes and extensions).
			 */
			t1 = t1->ty_RefType.et_Type;
			t2 = t2->ty_RefType.et_Type;
			if (MatchType(t1, t2) <= SG_COMPAT_PART) {
				return(1);
			}
			return(0);
			break;
		case TY_COMPOUND:
			/*
			 * Compare the elements making up the compound type.
			 * XXX
			 */
			return(SimilarSemGroup(t1->ty_CompType.et_SemGroup,
					       t2->ty_CompType.et_SemGroup));
			break;
		case TY_ARYOF:
		case TY_VAR:
		case TY_PROC:
			/* XXX */
			return(0);
		case TY_STORAGE:
		case TY_ARGS:
		case TY_UNRESOLVED:
		case TY_DYNAMIC:
			/* XXX */
			return(0);
		default:
			dassert_type(t1, 0);
			return(0);
		}
		check_const = 1;
	}
	return(0);
}

/*
 * SimilarSemGroup() - check to see if the storage underlying the two
 *			semantic groups is compatible.
 */
int
SimilarSemGroup(SemGroup *s1, SemGroup *s2)
{
	Declaration *d1;
	Declaration *d2;

	if (s1->sg_Bytes != s2->sg_Bytes)
		return(0);
	d1 = RUNE_FIRST(&s1->sg_DeclList);
	d2 = RUNE_FIRST(&s2->sg_DeclList);
	for (;;) {
		while (d1 && 
		       ((d1->d_Op & DOPF_STORAGE) == 0 ||
			 d1->d_Op == DOP_GLOBAL_STORAGE)
		) {
			d1 = RUNE_NEXT(d1, d_Node);
		}
		while (d2 && 
		       ((d2->d_Op & DOPF_STORAGE) == 0 ||
			 d2->d_Op == DOP_GLOBAL_STORAGE)
		) {
			d2 = RUNE_NEXT(d2, d_Node);
		}
		if (d1 == NULL || d2 == NULL)
			break;
		if (SimilarType(d1->d_StorDecl.ed_Type,
				d2->d_StorDecl.ed_Type) == 0) {
			break;
		}
		d1 = RUNE_NEXT(d1, d_Node);
		d2 = RUNE_NEXT(d2, d_Node);
	}
	if (d1 || d2)
		return(0);	/* compare bad */
	return(1);		/* compare good */
}

static char *SaveStr[8];
static int SaveIndex;

static
char *
typeToStr(Type *type, char **pstr, int simple)
{
	char *str = NULL;
	char *s1 = NULL;
	char *s2 = NULL;
	Stmt *st;
	SemGroup *sg;
	Declaration *d;
	int count;
	int flags;

	if (type == NULL) {
		safe_asprintf(&str, "(null)");
	} else {
		switch(type->ty_Op) {
		case TY_CLASS:
			st = type->ty_ClassType.et_SemGroup->sg_Stmt;
			if (st) {
				dassert(st->st_Op == ST_Class);
#if 1
				safe_asprintf(&str, "%s",
					      st->st_ClassStmt.es_Decl->d_Id);
#else
				LexPrintRef(&st->st_LexRef, 0);
				safe_asprintf(&str, "%s(",
					      st->st_ClassStmt.es_Decl->d_Id);
				if (type->ty_Flags & (TF_ISINTEGER | TF_ISFLOAT |
						      TF_ISBOOL)) {
					break;
				}

				count = 0;
				for (;;) {
					while (st && st->st_Op != ST_Import)
						st = st->st_Parent;
					if (st == NULL)
						break;
					safe_replacef(&str, "%s%s%s",
						      str,
						      (count ? "," : ""),
						      /* st->st_ImportStmt.es_Path, */
						      st->st_ImportStmt.es_File);
					st = st->st_Parent;
					++count;
				}
				safe_replacef(&str, "%s)", str);
#endif
			} else {
				safe_asprintf(&str, "(class_sg=%p)",
					      type->ty_ClassType.et_SemGroup);
			}
			break;
		case TY_IMPORT:
			st = type->ty_ImportType.et_SemGroup->sg_Stmt;
			if (st) {
				dassert(st->st_Op == ST_Module);
				safe_asprintf(&str, "IMPORT(%s)",
					      st->st_LexRef.lr_Lex->l_Path);
			} else {
				safe_asprintf(&str, "IMPORT(sg=%p)",
					      type->ty_ImportType.et_SemGroup);
			}
			break;
		case TY_CPTRTO:
			typeToStr(type->ty_CPtrType.et_Type, &s1, simple);
			safe_replacef(&str, "(CLANG)*%s", s1);
			break;
		case TY_PTRTO:
			typeToStr(type->ty_PtrType.et_Type, &s1, simple);
			safe_replacef(&str, "*%s", s1);
			break;
		case TY_REFTO:
			typeToStr(type->ty_RefType.et_Type, &s1, simple);
			safe_replacef(&str, "@%s", s1);
			break;
		case TY_ARYOF:
			typeToStr(type->ty_AryType.et_Type, &s1, simple);
			safe_replacef(&str, "%s[%jd]",
				      s1, (intmax_t)type->ty_AryType.et_Count);
			break;
		case TY_COMPOUND:
			sg = type->ty_CompType.et_SemGroup;
			safe_asprintf(&str, "COMP(");
			count = 0;

			RUNE_FOREACH(d, &sg->sg_DeclList, d_Node) {
				if (d->d_Op & DOPF_STORAGE) {
					Type *dtype = d->d_StorDecl.ed_Type;
					typeToStr(dtype, &s1, 1);
					if (count)
						safe_replacef(&str, "%s,%s",
							      str, s1);
					else
						safe_replacef(&str, "%s%s",
							      str, s1);
					++count;
					safe_free(&s1);
				}
			}
			safe_replacef(&str, "%s)", str);
			break;
		case TY_VAR:
			safe_replacef(&str, "VAR");
			break;
		case TY_ARGS:
			sg = type->ty_ArgsType.et_SemGroup;
			safe_asprintf(&str, "ARGS(");
			count = 0;
			RUNE_FOREACH(d, &sg->sg_DeclList, d_Node) {
				if (d->d_Op & DOPF_STORAGE) {
					Type *dtype = d->d_StorDecl.ed_Type;
					typeToStr(dtype, &s1, 1);
					if (count)
						safe_replacef(&str, "%s,%s",
							      str, s1);
					else
						safe_replacef(&str, "%s%s",
							      str, s1);
					safe_free(&s1);
					++count;
				}
			}
			safe_replacef(&str, "%s)", str);
			break;
		case TY_PROC:
			{
				Type *rtype = type->ty_ProcType.et_RetType;
				Type *atype = type->ty_ProcType.et_ArgsType;
				typeToStr(rtype, &s1, 1);
				typeToStr(atype, &s2, 1);
				safe_asprintf(&str, "%s %s", s1, s2);
			}
			break;
		case TY_STORAGE:
			safe_asprintf(&str, "STORAGE(%d)",
				      type->ty_StorType.et_Bytes);
			break;
		case TY_DYNAMIC:
			safe_asprintf(&str, "DYNAMIC");
			break;
		case TY_UNRESOLVED:
			safe_asprintf(&str, "UNRES(");
			for (count = 0; type->ty_UnresType.et_DottedId[count]; ++count) {
				safe_replacef(&str, "%s%s",
					      str, type->ty_UnresType.et_DottedId[count]);
				if (count) {
					safe_replacef(&str, "%s,%s",
						      str, type->ty_UnresType.et_DottedId[count]);
				}
			}
			safe_replacef(&str, "%s)", str);
			break;
		default:
			safe_asprintf(&str, "?");
			break;
		}
		flags = type->ty_SQFlags;
		count = 0;
		while (flags) {
			const char *sqflag;

			if (flags & SF_CONST) {
				sqflag = "const";
				flags &= ~SF_CONST;
			} else if (flags & SF_VOLATILE) {
				sqflag = "volatile";
				flags &= ~SF_VOLATILE;
			} else if (flags & SF_VARARGS) {
				sqflag = "varargs";
				flags &= ~SF_VARARGS;
			} else if (flags & SF_LVALUE) {
				sqflag = "lvalue";
				flags &= ~SF_LVALUE;
			} else if (flags & SF_NOZERO) {
				sqflag = "__nozero";
				flags &= ~SF_NOZERO;
			} else if (flags & SF_METHOD) {
				sqflag = "method";
				flags &= ~SF_METHOD;
			} else if (flags & SF_GMETHOD) {
				sqflag = "gmethod";
				flags &= ~SF_GMETHOD;
			} else {
				sqflag = "bad";
				flags = 0;
			}
			safe_replacef(&str, "%s%s%s",
				      sqflag, " ", str);
			++count;
		}
	}
	safe_free(&s1);
	safe_free(&s2);
	if (pstr) {
		safe_free(pstr);
		*pstr = str;
	} else {
		safe_free(&SaveStr[SaveIndex]);
		SaveStr[SaveIndex] = str;
		SaveIndex = (SaveIndex + 1) % arysize(SaveStr);
	}
	return(str);
}

char *
TypeToStr(Type *type, char **pstr)
{
	char *str = NULL;
	char *res;

	res = typeToStr(type, pstr, 0);
	safe_asprintf(&str, "<TYPE_%p %s>", type, res);
	if (pstr) {
		safe_free(pstr);
		*pstr = str;
	} else {
		safe_free(&SaveStr[SaveIndex]);
		SaveStr[SaveIndex] = str;
		SaveIndex = (SaveIndex + 1) % arysize(SaveStr);
	}
	return(str);
}