const char CMSRC_SEP[] = "#"

const byte F_RECURSE_POINT = 128

data TRCheck {
	DanaType type
	DanaTypeField field
	TRCheck prev
}

component provides TypeShaper requires io.Output out, data.adt.List, data.StringUtil stringUtil, data.IntUtil iu, data.ByteUtil bu, data.query.Search search, DNCUtil dncUtil {

	DanaType getDeclareType(DanaToken fnx, DanaType types[])
		{
		DanaType ftype = null
		
		if (fnx.subType == TokSubTypes.DECLARE)
			{
			ftype = dncUtil.findType(types, fnx.subTokens.token)
			}
			else if (fnx.subType == TokSubTypes.DECLARE_ARRAY)
			{
			DanaType atype
			ftype = dncUtil.findType(types, fnx.subTokens.token)

			char typeStart[] = fnx.subTokens.token
			//out.println("typestart: $typeStart")
			if (fnx.subTokens.next != null)
				{
				char arraySize[] = null
				DanaToken dts = fnx.subTokens.next
				while (dts != null)
					{
					arraySize = null
					
					if (dts.subTokens != null && dts.subTokens.token != null)
						{
						arraySize = dts.subTokens.token
						}
						else if (dts.token != null)
						{
						arraySize = dts.token
						}
					

					if (arraySize == null)
						{
						atype = types.findFirst(DanaType.[name], new DanaType(name = "$(typeStart)[]"))
						if (dts.next != null) typeStart = "$(typeStart)[]"
						}
						else
						{
						atype = types.findFirst(DanaType.[name], new DanaType(name = "$(typeStart)[$arraySize]"))
						if (dts.next != null) typeStart = "$(typeStart)[$arraySize]"
						}
					
					dts = dts.next
					}
				
				//out.println("ts: $(typeStart) / as: $(arraySize)")
				
				if (arraySize == null)
					ftype = types.findFirst(DanaType.[name], new DanaType(name = "$(typeStart)[]"))
					else
					ftype = types.findFirst(DanaType.[name], new DanaType(name = "$(typeStart)[$arraySize]"))
				}
				else
				{
				ftype = types.findFirst(DanaType.[name], new DanaType(name = "$(typeStart)[]"))
				}
			}
		
		return ftype
		}
	
	void setRecursionFlags(TRCheck checker, DanaType type)
		{
		checker = checker.prev

		while (checker != null)
			{
			if (checker.type === type)
				{
				//out.println("marking TRP for $(type.name):$(checker.type.name) via field $(checker.field.name)")
				checker.field.flags |= F_RECURSE_POINT
				}
			
			checker = checker.prev
			}
		}
	
	void locateRecursionPoints(DanaType types[], DanaType type, TRCheck checker, int level)
		{
		TRCheck ntrc = new TRCheck()
		ntrc.prev = checker

		setRecursionFlags(checker, type)

		//out.println(" -> LRP @ lv $level for $(type.name)")

		if (type.class == DanaType.DATA)
			{
			for (int i = 0; i < type.fields.arrayLength; i++)
				{
				if ((type.fields[i].flags & F_RECURSE_POINT) != F_RECURSE_POINT)
					{
					//DanaType fieldType = types.findFirst(DanaType.[name], new DanaType(name = type.fields[i].type))
					DanaType fieldType = dncUtil.findType(types, type.fields[i].type)

					ntrc.field = type.fields[i]
					ntrc.type = fieldType

					locateRecursionPoints(types, fieldType, ntrc, level + 1)
					}
				}
			}
			else if (type.class == DanaType.INTERFACE || type.class == DanaType.FUNCTION)
			{
			for (int i = 0; i < type.fields.arrayLength; i++)
				{
				byte q = type.fields[i].flags & F_RECURSE_POINT
				if ((type.fields[i].flags & F_RECURSE_POINT) != F_RECURSE_POINT)
					{
					//DanaType fieldType = types.findFirst(DanaType.[name], new DanaType(name = type.fields[i].type))
					DanaType fieldType = dncUtil.findType(types, type.fields[i].type)

					ntrc.field = type.fields[i]
					ntrc.type = fieldType

					locateRecursionPoints(types, fieldType, ntrc, level + 1)
					}
				}
			}
			else if (type.class == DanaType.ARRAY)
			{
			for (int i = 0; i < type.fields.arrayLength; i++)
				{
				if ((type.fields[i].flags & F_RECURSE_POINT) != F_RECURSE_POINT)
					{
					//DanaType fieldType = types.findFirst(DanaType.[name], new DanaType(name = type.fields[i].type))
					DanaType fieldType = dncUtil.findType(types, type.fields[i].type)

					ntrc.field = type.fields[i]
					ntrc.type = fieldType

					locateRecursionPoints(types, fieldType, ntrc, level + 1)
					}
				}
			}
		}
	
	void setTypeRecursionPoints(DanaType types[])
		{
		for (int i = 0; i < types.arrayLength; i++)
			{
			//out.println("-- set recursion for type $(types[i].name) --")
			TRCheck trc = new TRCheck(types[i], new DanaTypeField())
			locateRecursionPoints(types, types[i], trc, 0)
			}
		}
	
	void markNoCycle(DanaType t, DanaType types[])
		{
		// for now we need to be *very* conservative about this, so start with only data types that have primitive / array-primitive fields
		// - later we can try to upgrade things, but we need to be aware not just of the "same type", but fields that you *could* assign the same type in to and so create a cycle...
		
		if (t.class == DanaType.DATA)
			{
			for (int i = 0; i < t.fields.arrayLength; i++)
				{
				DanaType fieldType = dncUtil.findType(types, t.fields[i].type)

				if (fieldType.class == DanaType.DATA || fieldType.class == DanaType.INTERFACE)
					{
					return
					}
				
				if (fieldType.class == DanaType.ARRAY)
					{
					fieldType = dncUtil.findType(types, fieldType.fields[0].type)
					if (fieldType.class == DanaType.DATA || fieldType.class == DanaType.INTERFACE)
						{
						return
						}
					}
				}
			}
		
		t.flags = DanaType.F_NO_CYCLE
		}
	
	void setTypeNoCycle(DanaType types[])
		{
		for (int i = 0; i < types.arrayLength; i++)
			{
			if (types[i].class == DanaType.DATA)
				{
				markNoCycle(types[i], types)
				}
			}
		
		for (int i = 0; i < types.arrayLength; i++)
			{
			if (types[i].class == DanaType.ARRAY)
				{
				DanaType fieldType = dncUtil.findType(types, types[i].fields[0].type)

				if (fieldType.flags == DanaType.F_NO_CYCLE)
					{
					types[i].flags = DanaType.F_NO_CYCLE
					}
				}
			}
		}
	
	char[] getMakeArrayType(DanaToken tok)
		{
		char result[] = null

		if (tok.subTokens.next == null)
			{
			//one-dimensional array
			result = "$(tok.exStr1)[]"
			}
			else
			{
			//multi-dimensional array
			result = tok.exStr1

			DanaToken stw = tok.subTokens
			while (stw != null)
				{
				result = "$(result)[]"
				stw = stw.next
				}
			}
		
		return result
		}
	
	char[] getMakeArrayConstructType(DanaToken tok)
		{
		char result[] = null

		if (tok.subTokens.next.type == DanaToken.PARAM)
			{
			result = "$(tok.exStr1)[]"
			}
			else
			{
			//multi-dimensional array
			result = tok.exStr1
			DanaToken stw = tok.subTokens
			while (stw != null && stw.type != DanaToken.PARAM)
				{
				result = "$(result)[]"
				stw = stw.next
				}
			}

		return result
		}
	
	int countCharacters(char str[], char c)
		{
		int result = 0
		for (int i = 0; i < str.arrayLength; i++)
			{
			if (str[i] == c) result ++
			}
		
		return result
		}
	
	DanaType[] makeNewArrayTypes(DanaType types[], DanaToken tree)
		{
		DanaType result[]
		DanaToken tw = tree
		while (tw != null)
			{
			result = new DanaType[](result, makeNewArrayTypes(types, tw.subTokens))

			if (tw.type == DanaToken.OPERATION && tw.subType == TokSubTypes.NEW_ARRAY)
				{
				char typeName[] = getMakeArrayType(tw)

				char plainType[] = typeName.lsplit("[")[0].string
				int levels = countCharacters(typeName, "[")

				while (levels > 0)
					{
					if (dncUtil.findType(types, "$(plainType)[]") == null)
						{
						DanaType nt = new DanaType(DanaType.ARRAY, "$(plainType)[]", "$(plainType)[]", null, new DanaTypeField(type = plainType))
						result = new DanaType[](result, nt)
						}
					
					plainType = "$(plainType)[]"

					levels --
					}
				}
				else if (tw.type == DanaToken.OPERATION && tw.subType == TokSubTypes.NEW_ARRAY_CONSTRUCT)
				{
				char typeName[] = getMakeArrayConstructType(tw)

				char plainType[] = typeName.lsplit("[")[0].string
				int levels = countCharacters(typeName, "[")

				while (levels > 0)
					{
					if (dncUtil.findType(types, "$(plainType)[]") == null)
						{
						DanaType nt = new DanaType(DanaType.ARRAY, "$(plainType)[]", "$(plainType)[]", null, new DanaTypeField(type = plainType))
						result = new DanaType[](result, nt)
						}
					
					plainType = "$(plainType)[]"

					levels --
					}
				}

			tw = tw.next
			}
		
		return result
		}
	
	DanaType[] TypeShaper:shapeTypes(DanaType types[], DanaToken tree)
		{
		//here we flatten all types by including their inherited members, and we ensure that "lang.Object" is the base type of all objects
		// - we also do cycle analysis and mark type fields as recursion-points
		types = clone types

		//auto-inherit from lang.Object
		for (int i = 0; i < types.arrayLength; i++)
			{
			if (types[i].class == DanaType.INTERFACE && types[i].name != "lang.Object" && types[i].extendsType == null)
				{
				types[i] = clone types[i]
				types[i].extendsType = "lang.Object"
				}
				else if (types[i].class == DanaType.DATA && types[i].name != "Data" && types[i].name != "Mutex" && types[i].extendsType == null)
				{
				types[i] = clone types[i]
				types[i].extendsType = "Data"
				}
			}
		
		//flatten types
		// - note which ones are already flattened
		DanaType flattened[] = null
		for (int i = 0; i < types.arrayLength; i++)
			{
			DanaType frq = null

			if (types[i].class == DanaType.INTERFACE && types[i].extendsType == null)
				{
				frq = clone types[i]
				flattened = new DanaType[](flattened, frq)
				}
				else if (types[i].class == DanaType.DATA && types[i].extendsType == null)
				{
				frq = clone types[i]
				flattened = new DanaType[](flattened, frq)
				}
				else if (types[i].class != DanaType.INTERFACE && types[i].class != DanaType.DATA)
				{
				frq = clone types[i]
				flattened = new DanaType[](flattened, frq)
				}
			
			if (frq != null)
				{
				frq.fields = clone frq.fields
				for (int j = 0; j < frq.fields.arrayLength; j++)
					{
					frq.fields[j] = clone frq.fields[j]
					}
				}
			}
		
		// - flatten any types which extend an already-flattened type
		bool expansion = true
		while (expansion)
			{
			expansion = false

			for (int i = 0; i < types.arrayLength; i++)
				{
				//out.println("TSHAP: considering $(types[i].name)")
				//if (flattened.findFirst(DanaType.[name], types[i]) == null)
				if (dncUtil.findType(flattened, types[i].name) == null)
					{
					//out.println(" - TSHAP: not in flat-list, class $(types[i].class) ET $(types[i].extendsType)")
					DanaType flt = null
					if (types[i].class == DanaType.INTERFACE && (flt = dncUtil.findType(flattened, types[i].extendsType)) != null)
						{
						char compositeSourceName[] = flt.fromFile

						int countFunction = 0

						DanaType nt = new DanaType(DanaType.INTERFACE, types[i].name, types[i].simpleName, extendsType = types[i].extendsType, deprecated = types[i].deprecated, deprecatedBy = types[i].deprecatedBy)

						//merge transfer fields, events, and functions
						for (int j = 0; j < flt.fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, flt.fields[j].type)
							if (fieldType.class != DanaType.EVENT && fieldType.class != DanaType.FUNCTION && flt.fields[j].qualifier == "constant")
								{
								DanaTypeField flfield = clone flt.fields[j]
								flfield.flags = DanaTypeField.INHERITED
								nt.fields = new DanaTypeField[](nt.fields, flfield)
								}
							}
						
						for (int j = 0; j < types[i].fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, types[i].fields[j].type)
							if (fieldType.class != DanaType.EVENT && fieldType.class != DanaType.FUNCTION && types[i].fields[j].qualifier == "constant")
								{
								nt.fields = new DanaTypeField[](nt.fields, clone types[i].fields[j])
								}
							}

						for (int j = 0; j < flt.fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, flt.fields[j].type)
							if (fieldType.class != DanaType.EVENT && fieldType.class != DanaType.FUNCTION && flt.fields[j].qualifier == "transfer")
								{
								nt.fields = new DanaTypeField[](nt.fields, clone flt.fields[j])
								}
							}
						
						for (int j = 0; j < types[i].fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, types[i].fields[j].type)
							if (fieldType.class != DanaType.EVENT && fieldType.class != DanaType.FUNCTION && types[i].fields[j].qualifier == "transfer")
								{
								nt.fields = new DanaTypeField[](nt.fields, clone types[i].fields[j])
								}
							}
						
						for (int j = 0; j < flt.fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, flt.fields[j].type)
							if (fieldType.class == DanaType.EVENT)
								{
								DanaTypeField flfield = clone flt.fields[j]
								flfield.flags = DanaTypeField.INHERITED
								nt.fields = new DanaTypeField[](nt.fields, flfield)
								}
							}
						
						for (int j = 0; j < types[i].fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, types[i].fields[j].type)
							if (fieldType.class == DanaType.EVENT)
								{
								nt.fields = new DanaTypeField[](nt.fields, clone types[i].fields[j])
								}
							}
						
						for (int j = 0; j < flt.fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, flt.fields[j].type)
							if (fieldType.class == DanaType.FUNCTION)
								{
								DanaTypeField flfield = clone flt.fields[j]
								flfield.flags = DanaTypeField.INHERITED
								nt.fields = new DanaTypeField[](nt.fields, flfield)
								countFunction ++
								}
							}
						
						for (int j = 0; j < types[i].fields.arrayLength; j ++)
							{
							DanaType fieldType = dncUtil.findType(types, types[i].fields[j].type)
							if (fieldType.class == DanaType.FUNCTION)
								{
								nt.fields = new DanaTypeField[](nt.fields, clone types[i].fields[j])
								}
							}
						
						compositeSourceName = new char[](compositeSourceName, "$(CMSRC_SEP)$(types[i].fromFile)[$(countFunction)]")
						
						nt.fromFile = compositeSourceName

						flattened = new DanaType[](flattened, nt)
						expansion = true
						}
						else if (types[i].class == DanaType.DATA && (flt = dncUtil.findType(flattened, types[i].extendsType)) != null)
						{
						DanaType nt = clone types[i]
						
						nt.fields = null

						//merge regular fields (not constants)
						for (int j = 0; j < flt.fields.arrayLength; j ++)
							{
							if (flt.fields[j].qualifier.arrayLength == 0)
								{
								nt.fields = new DanaTypeField[](nt.fields, clone flt.fields[j])
								}
							}
						
						for (int j = 0; j < types[i].fields.arrayLength; j ++)
							{
							nt.fields = new DanaTypeField[](nt.fields, clone types[i].fields[j])
							}
						
						flattened = new DanaType[](flattened, nt)
						expansion = true
						}
					}
				}
			}
		
		//invent array types for every new_array instruction, since these can be present without a variable declaration of that type (reflection)
		DanaType newArrays[] = makeNewArrayTypes(flattened, tree)
		for (int i = 0; i < newArrays.arrayLength; i++)
			{
			if (dncUtil.findType(flattened, newArrays[i].name) == null)
				{
				flattened = new DanaType[](flattened, newArrays[i])
				}
			}
		
		setTypeRecursionPoints(flattened)

		setTypeNoCycle(flattened)

		//invent fixed-size char[]-array types for every object type name, in case they're needed for dynamic instantiation instructions
		
		for (int i = 0; i < types.arrayLength; i++)
			{
			if (types[i].class == DanaType.INTERFACE)
				{
				if (dncUtil.findType(flattened, "char[$(types[i].name.arrayLength)]") == null)
					{
					DanaType nt = new DanaType(DanaType.ARRAY, "char[$(types[i].name.arrayLength)]", "char[$(types[i].name.arrayLength)]", null, new DanaTypeField(type = "char"), types[i].name.arrayLength)
					flattened = new DanaType[](flattened, nt)
					}
				}
			}
		
		//invent fixed-size primitive-type arrays for every array constant
		DanaToken pw = tree.subTokens

		while (pw != null)
			{
			if (pw.type == DanaToken.OUTER_SCOPE)
				{
				//all constants should be here

				DanaToken sw = pw.subTokens

				while (sw != null)
					{
					if (sw.type == DanaToken.OPERATION && sw.subType == TokSubTypes.ASSIGN && (sw.subTokens.type == DanaToken.OPERATION && (sw.subTokens.subType == TokSubTypes.DECLARE || sw.subTokens.subType == TokSubTypes.DECLARE_ARRAY)))
						{
						//parse the RHS using the normal parse function...
						if (sw.subTokens.exStr2 == "constant")
							{
							DanaType declareType = getDeclareType(sw.subTokens, types)

							if (declareType.class == DanaType.ARRAY && declareType.storageSize == 0 && sw.subTokens.next.subType == TokSubTypes.NEW_ARRAY_CONSTRUCT)
								{
								//count the number of cells
								DanaToken cw = sw.subTokens.next.subTokens.next.subTokens
								DanaType fieldType = dncUtil.findType(types, declareType.fields[0].type)
								char pTypeName[] = fieldType.name

								int count = 0

								while (cw != null)
									{
									count ++
									cw = cw.next
									}
								
								//out.println("found $count params of array construct for $(pTypeName)[]")

								if (flattened.findFirst(DanaType.[name], new DanaType(name = "$(pTypeName)[$count]")) == null)
									{
									DanaType nt = new DanaType(DanaType.ARRAY, "$(pTypeName)[$count]", "$(pTypeName)[$count]", null, new DanaTypeField(type = "$(pTypeName)"), count)
									flattened = new DanaType[](flattened, nt)
									}
								}
							}
						}
					
					sw = sw.next
					}
				}
			
			pw = pw.next
			}

		return flattened
		}
}