<commit_before>// arrays.cpp
// Copyright (c) 2014 - 2017, <EMAIL>
// Licensed under the Apache License Version 2.0.

#include "codegen.h"

#define BUILTIN_ARRAY_BOUNDS_CHECK_FUNC_NAME		"__array_boundscheck"
#define BUILTIN_ARRAY_DECOMP_BOUNDS_CHECK_FUNC_NAME	"__array_boundscheckdecomp"

#define BUILTIN_ARRAY_CMP_FUNC_NAME					"__array_compare"

#define BUILTIN_DYNARRAY_CLONE_FUNC_NAME			"__darray_clone"
#define BUILTIN_DYNARRAY_APPEND_FUNC_NAME			"__darray_append"
#define BUILTIN_DYNARRAY_APPEND_ELEMENT_FUNC_NAME	"__darray_appendelement"
#define BUILTIN_DYNARRAY_POP_BACK_FUNC_NAME			"__darray_popback"
#define BUILTIN_DYNARRAY_MAKE_FROM_TWO_FUNC_NAME	"__darray_combinetwo"

#define BUILTIN_SLICE_CLONE_FUNC_NAME				"__slice_clone"
#define BUILTIN_SLICE_APPEND_FUNC_NAME				"__slice_append"
#define BUILTIN_SLICE_APPEND_ELEMENT_FUNC_NAME		"__slice_appendelement"

#define BUILTIN_LOOP_INCR_REFCOUNT_FUNC_NAME		"__loop_incr_refcount"
#define BUILTIN_LOOP_DECR_REFCOUNT_FUNC_NAME		"__loop_decr_refcount"


namespace cgn {
namespace glue {
namespace array
{
	fir::Function* getBoundsCheckFunction(CodegenState* cs, bool isPerformingDecomposition)
	{
		fir::Function* fn = cs->module->getFunction(Identifier(isPerformingDecomposition
			? BUILTIN_ARRAY_DECOMP_BOUNDS_CHECK_FUNC_NAME : BUILTIN_ARRAY_BOUNDS_CHECK_FUNC_NAME, IdKind::Name));

		if(!fn)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(isPerformingDecomposition ? BUILTIN_ARRAY_DECOMP_BOUNDS_CHECK_FUNC_NAME : BUILTIN_ARRAY_BOUNDS_CHECK_FUNC_NAME, IdKind::Name),
				fir::FunctionType::get({ fir::Type::getInt64(), fir::Type::getInt64(), fir::Type::getString() },
					fir::Type::getVoid()), fir::LinkageType::Internal);

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			fir::IRBlock* failb = cs->irb.addNewBlockInFunction("fail", func);
			fir::IRBlock* checkneg = cs->irb.addNewBlockInFunction("checkneg", func);
			fir::IRBlock* merge = cs->irb.addNewBlockInFunction("merge", func);

			cs->irb.setCurrentBlock(entry);

			fir::Value* max = func->getArguments()[0];
			fir::Value* ind = func->getArguments()[1];

			fir::Value* res = 0;

			// if we're decomposing, it's length vs length, so compare strictly greater.
			if(isPerformingDecomposition)
				res = cs->irb.CreateICmpGT(ind, max);

			else
				res = cs->irb.CreateICmpGEQ(ind, max);

			iceAssert(res);

			cs->irb.CreateCondBranch(res, failb, checkneg);
			cs->irb.setCurrentBlock(failb);
			{
				fir::Function* fprintfn = cs->module->getOrCreateFunction(Identifier("fprintf", IdKind::Name),
					fir::FunctionType::getCVariadicFunc({ fir::Type::getVoidPtr(), fir::Type::getInt8Ptr() },
					fir::Type::getInt32()), fir::LinkageType::External);

				fir::Function* fdopenf = cs->module->getOrCreateFunction(Identifier("fdopen", IdKind::Name),
					fir::FunctionType::get({ fir::Type::getInt32(), fir::Type::getInt8Ptr() }, fir::Type::getVoidPtr()),
					fir::LinkageType::External);

				// basically:
				// void* stderr = fdopen(2, "w")
				// fprintf(stderr, "", bla bla)

				fir::ConstantValue* tmpstr = cs->module->createGlobalString("w");
				fir::ConstantValue* fmtstr = 0;

				if(isPerformingDecomposition)
					fmtstr = cs->module->createGlobalString("%s: Tried to decompose array into '%zd' elements; length is only '%zd'\n");

				else
					fmtstr = cs->module->createGlobalString("%s: Tried to index array at index '%zd'; length is only '%zd'\n");

				iceAssert(fmtstr);

				fir::Value* posstr = cs->irb.CreateGetStringData(func->getArguments()[2]);
				fir::Value* err = cs->irb.CreateCall2(fdopenf, fir::ConstantInt::getInt32(2), tmpstr);

				cs->irb.CreateCall(fprintfn, { err, fmtstr, posstr, ind, max });

				cs->irb.CreateCall0(cs->getOrDeclareLibCFunction("abort"));
				cs->irb.CreateUnreachable();
			}

			cs->irb.setCurrentBlock(checkneg);
			{
				fir::Value* res2 = cs->irb.CreateICmpLT(ind, fir::ConstantInt::getInt64(0));
				cs->irb.CreateCondBranch(res2, failb, merge);
			}

			cs->irb.setCurrentBlock(merge);
			{
				cs->irb.CreateReturnVoid();
			}

			fn = func;

			cs->irb.setCurrentBlock(restore);
		}

		iceAssert(fn);
		return fn;
	}





	static void _callCloneFunctionInLoop(CodegenState* cs, fir::Function* curfunc, fir::Function* fn,
		fir::Value* ptr, fir::Value* len, fir::Value* newptr, fir::Value* startIndex)
	{
		fir::IRBlock* loopcond = cs->irb.addNewBlockInFunction("loopcond", curfunc);
		fir::IRBlock* loopbody = cs->irb.addNewBlockInFunction("loopbody", curfunc);
		fir::IRBlock* merge = cs->irb.addNewBlockInFunction("merge", curfunc);

		fir::Value* counter = cs->irb.CreateStackAlloc(fir::Type::getInt64());
		cs->irb.CreateStore(startIndex, counter);

		cs->irb.CreateUnCondBranch(loopcond);
		cs->irb.setCurrentBlock(loopcond);
		{
			fir::Value* res = cs->irb.CreateICmpEQ(cs->irb.CreateLoad(counter), len);
			cs->irb.CreateCondBranch(res, merge, loopbody);
		}

		cs->irb.setCurrentBlock(loopbody);
		{
			// make clone
			fir::Value* origElm = cs->irb.CreatePointerAdd(ptr, cs->irb.CreateLoad(counter));
			fir::Value* clone = 0;

			if(fn->getArgumentCount() == 1)
				clone = cs->irb.CreateCall1(fn, cs->irb.CreateLoad(origElm));
			else
				clone = cs->irb.CreateCall2(fn, cs->irb.CreateLoad(origElm), fir::ConstantInt::getInt64(0));

			// store clone
			fir::Value* newElm = cs->irb.CreatePointerAdd(newptr, cs->irb.CreateLoad(counter));
			cs->irb.CreateStore(clone, newElm);

			// increment counter
			cs->irb.CreateStore(cs->irb.CreateAdd(cs->irb.CreateLoad(counter), fir::ConstantInt::getInt64(1)), counter);
			cs->irb.CreateUnCondBranch(loopcond);
		}

		cs->irb.setCurrentBlock(merge);
	}


	static void _handleCallingAppropriateCloneFunction(CodegenState* cs, fir::Function* func, fir::Type* elmType, fir::Value* origptr,
		fir::Value* newptr, fir::Value* origlen, fir::Value* actuallen, fir::Value* startIndex)
	{
		if(elmType->isPrimitiveType() || elmType->isCharType() || elmType->isEnumType())
		{
			fir::Function* memcpyf = cs->module->getIntrinsicFunction("memmove");

			cs->irb.CreateCall(memcpyf, { newptr, cs->irb.CreatePointerTypeCast(cs->irb.CreatePointerAdd(origptr,
				startIndex), fir::Type::getInt8Ptr()), actuallen, fir::ConstantInt::getInt32(0), fir::ConstantBool::get(false) });
		}
		else if(elmType->isDynamicArrayType())
		{
			// yo dawg i heard you like arrays...
			fir::Function* clonef = getCloneFunction(cs, elmType->toDynamicArrayType());
			iceAssert(clonef);

			// loop
			fir::Value* cloneptr = cs->irb.CreatePointerTypeCast(newptr, elmType->getPointerTo());
			_callCloneFunctionInLoop(cs, func, clonef, origptr, origlen, cloneptr, startIndex);
		}
		else if(elmType->isArraySliceType())
		{
			// yo dawg i heard you like arrays...
			fir::Function* clonef = getCloneFunction(cs, elmType->toArraySliceType());
			iceAssert(clonef);

			// loop
			fir::Value* cloneptr = cs->irb.CreatePointerTypeCast(newptr, elmType->getPointerTo());
			_callCloneFunctionInLoop(cs, func, clonef, origptr, origlen, cloneptr, startIndex);
		}
		else if(elmType->isStringType())
		{
			fir::Function* clonef = glue::string::getCloneFunction(cs);
			iceAssert(clonef);

			// loop
			fir::Value* cloneptr = cs->irb.CreatePointerTypeCast(newptr, elmType->getPointerTo());
			_callCloneFunctionInLoop(cs, func, clonef, origptr, origlen, cloneptr, startIndex);
		}
		else if(elmType->isStructType() || elmType->isClassType() || elmType->isTupleType() || elmType->isArrayType())
		{
			// todo: call copy constructors and stuff

			fir::Function* memcpyf = cs->module->getIntrinsicFunction("memmove");

			cs->irb.CreateCall(memcpyf, { newptr, cs->irb.CreatePointerTypeCast(cs->irb.CreatePointerAdd(origptr,
				startIndex), fir::Type::getInt8Ptr()), actuallen, fir::ConstantInt::getInt32(0), fir::ConstantBool::get(false) });
		}
		else
		{
			error("unsupported element type '%s' for array clone", elmType->str());
		}
	}








	fir::Function* getCloneFunction(CodegenState* cs, fir::Type* arrtype)
	{
		if(arrtype->isDynamicArrayType())		return getCloneFunction(cs, arrtype->toDynamicArrayType());
		else if(arrtype->isArraySliceType())	return getCloneFunction(cs, arrtype->toArraySliceType());
		else									error("unsupported type '%s'", arrtype->str());
	}

	// takes ptr, start index
	fir::Function* getCloneFunction(CodegenState* cs, fir::DynamicArrayType* arrtype)
	{
		auto name = BUILTIN_DYNARRAY_CLONE_FUNC_NAME + std::string("_") + arrtype->encodedStr();

		fir::Function* fn = cs->module->getFunction(Identifier(name, IdKind::Name));

		if(!fn)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(name, IdKind::Name),
				fir::FunctionType::get({ arrtype, fir::Type::getInt64() }, arrtype),
				fir::LinkageType::Internal);

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			fir::IRBlock* insane = cs->irb.addNewBlockInFunction("insane", func);
			fir::IRBlock* merge1 = cs->irb.addNewBlockInFunction("merge1", func);

			cs->irb.setCurrentBlock(entry);

			fir::Value* orig = func->getArguments()[0];
			fir::Value* startIndex = func->getArguments()[1];

			iceAssert(orig);
			iceAssert(startIndex);



			fir::Value* origptr = cs->irb.CreateGetDynamicArrayData(orig, "origptr");
			fir::Value* origlen = cs->irb.CreateGetDynamicArrayLength(orig, "origlen");

			// fir::Value* cap = cs->irb.CreateStackAlloc(fir::Type::getInt64(), "cap");

			fir::Value* origcap = cs->irb.CreateGetDynamicArrayCapacity(orig);
			// cs->irb.CreateStore(origcap, cap);


			// note: sanity check that len <= cap
			fir::Value* sane = cs->irb.CreateICmpLEQ(origlen, origcap);
			cs->irb.CreateCondBranch(sane, merge1, insane);


			cs->irb.setCurrentBlock(insane);
			{
				// sanity check failed
				// *but* since we're using dyn arrays as vararg arrays,
				// then we just treat capacity = length.

				cs->irb.CreateUnCondBranch(merge1);
			}


			// ok, back to normal
			cs->irb.setCurrentBlock(merge1);
			auto cap = cs->irb.CreatePHINode(fir::Type::getInt64());
			cap->addIncoming(origcap, entry);
			cap->addIncoming(origlen, insane);


			// ok, alloc a buffer with the original capacity
			// get size in bytes, since cap is in elements
			fir::Value* actuallen = cs->irb.CreateMul(cap, cs->irb.CreateSizeof(arrtype->getElementType()));


			fir::Function* mallocf = cs->getOrDeclareLibCFunction(ALLOCATE_MEMORY_FUNC);
			iceAssert(mallocf);

			fir::Value* newptr = cs->irb.CreateCall1(mallocf, actuallen);

			fir::Type* elmType = arrtype->getElementType();
			_handleCallingAppropriateCloneFunction(cs, func, elmType, origptr, newptr, origlen, actuallen, startIndex);

			fir::Value* newarr = cs->irb.CreateValue(arrtype);
			newarr = cs->irb.CreateSetDynamicArrayData(newarr, cs->irb.CreatePointerTypeCast(newptr, arrtype->getElementType()->getPointerTo()));
			newarr = cs->irb.CreateSetDynamicArrayLength(newarr, cs->irb.CreateSub(origlen, startIndex));
			newarr = cs->irb.CreateSetDynamicArrayCapacity(newarr, cap);
			cs->irb.CreateSetDynamicArrayRefCount(newarr, fir::ConstantInt::getInt64(1));

			cs->irb.CreateReturn(newarr);

			fn = func;
			cs->irb.setCurrentBlock(restore);
		}

		iceAssert(fn);
		return fn;
	}









	// takes a slice, but returns a dynamic array
	fir::Function* getCloneFunction(CodegenState* cs, fir::ArraySliceType* arrtype)
	{
		auto name = BUILTIN_SLICE_CLONE_FUNC_NAME + std::string("_") + arrtype->encodedStr();

		fir::Function* fn = cs->module->getFunction(Identifier(name, IdKind::Name));

		if(!fn)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(name, IdKind::Name),
				fir::FunctionType::get({ arrtype, fir::Type::getInt64() },
					fir::DynamicArrayType::get(arrtype->getElementType())), fir::LinkageType::Internal);

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			fir::IRBlock* merge1 = cs->irb.addNewBlockInFunction("merge1", func);

			cs->irb.setCurrentBlock(entry);

			fir::Value* orig = func->getArguments()[0];
			fir::Value* startIndex = func->getArguments()[1];

			iceAssert(orig);
			iceAssert(startIndex);

			fir::Value* origptr = cs->irb.CreateGetArraySliceData(orig);
			fir::Value* origlen = cs->irb.CreateGetArraySliceLength(orig);

			cs->irb.CreateUnCondBranch(merge1);

			// ok, back to normal
			cs->irb.setCurrentBlock(merge1);

			// ok, alloc a buffer with the original capacity
			// get size in bytes, since cap is in elements
			fir::Value* actuallen = cs->irb.CreateMul(origlen, cs->irb.CreateSizeof(arrtype->getElementType()));

			fir::Function* mallocf = cs->getOrDeclareLibCFunction(ALLOCATE_MEMORY_FUNC);
			iceAssert(mallocf);

			fir::Value* newptr = cs->irb.CreateCall1(mallocf, actuallen);

			fir::Type* elmType = arrtype->getElementType();
			_handleCallingAppropriateCloneFunction(cs, func, elmType, origptr, newptr, origlen, actuallen, startIndex);

			fir::Value* newarr = cs->irb.CreateValue(fir::DynamicArrayType::get(arrtype->getElementType()));
			newarr = cs->irb.CreateSetDynamicArrayData(newarr, cs->irb.CreatePointerTypeCast(newptr, arrtype->getElementType()->getPointerTo()));
			newarr = cs->irb.CreateSetDynamicArrayLength(newarr, cs->irb.CreateSub(origlen, startIndex));
			newarr = cs->irb.CreateSetDynamicArrayCapacity(newarr, cs->irb.CreateSub(origlen, startIndex));

			cs->irb.CreateReturn(newarr);

			fn = func;
			cs->irb.setCurrentBlock(restore);
		}

		iceAssert(fn);
		return fn;
	}






	// static void _growCapacityBy(CodegenState* cs, fir::Function* func, fir::Value* arr, fir::Value* amt)
	// {
	// 	iceAssert(arr->getType()->isPointerType());
	// 	iceAssert(arr->getType()->getPointerElementType()->isDynamicArrayType());
	// 	iceAssert(amt->getType() == fir::Type::getInt64());
	// }


	// required is how much *EXTRA* space we need.
	static fir::Value* _checkCapacityAndGrowIfNeeded(CodegenState* cs, fir::Function* func, fir::Value* arr, fir::Value* required)
	{
		iceAssert(arr->getType()->isDynamicArrayType());
		iceAssert(required->getType() == fir::Type::getInt64());

		auto elmtype = arr->getType()->getArrayElementType();

		fir::Value* ptr = cs->irb.CreateGetDynamicArrayData(arr, "ptr");
		fir::Value* len = cs->irb.CreateGetDynamicArrayLength(arr, "len");
		fir::Value* cap = cs->irb.CreateGetDynamicArrayCapacity(arr, "cap");

		// check if len + required > cap
		fir::Value* needed = cs->irb.CreateAdd(len, required, "needed");
		fir::Value* cond = cs->irb.CreateICmpGT(needed, cap);



		fir::IRBlock* cb = cs->irb.getCurrentBlock();

		fir::IRBlock* trampoline = cs->irb.addNewBlockInFunction("trampoline", func);
		fir::IRBlock* growblk = cs->irb.addNewBlockInFunction("grow", func);

		// for when the 'dynamic' array came from a literal. same as the usual stuff
		// capacity will be -1, in this case.
		fir::IRBlock* growNewblk = cs->irb.addNewBlockInFunction("growFromScratch", func);

		fir::IRBlock* mergeblk = cs->irb.addNewBlockInFunction("merge", func);
		cs->irb.CreateCondBranch(cond, trampoline, mergeblk);

		cs->irb.setCurrentBlock(trampoline);
		{
			auto cond = cs->irb.CreateICmpEQ(cap, fir::ConstantInt::getInt64(-1));
			cs->irb.CreateCondBranch(cond, growNewblk, growblk);
		}

		// return a phi node.
		fir::Value* growPhi = 0;
		fir::Value* growNewPhi = 0;


		// grows to the nearest power of two from (len + required)
		cs->irb.setCurrentBlock(growblk);
		{
			fir::Function* p2func = cs->module->getIntrinsicFunction("roundup_pow2");
			iceAssert(p2func);

			fir::Value* nextpow2 = cs->irb.CreateCall1(p2func, needed, "nextpow2");

			fir::Function* refunc = cs->getOrDeclareLibCFunction(REALLOCATE_MEMORY_FUNC);
			iceAssert(refunc);

			fir::Value* actuallen = cs->irb.CreateMul(nextpow2, cs->irb.CreateSizeof(elmtype));
			fir::Value* newptr = cs->irb.CreateCall2(refunc, cs->irb.CreatePointerTypeCast(ptr, fir::Type::getInt8Ptr()), actuallen);

			fir::Value* ret = cs->irb.CreateSetDynamicArrayData(arr, cs->irb.CreatePointerTypeCast(newptr, ptr->getType()));
			ret = cs->irb.CreateSetDynamicArrayCapacity(ret, nextpow2);

			cs->irb.CreateUnCondBranch(mergeblk);

			growPhi = ret;
		}


		// makes a new memory piece, to the nearest power of two from (len + required)
		cs->irb.setCurrentBlock(growNewblk);
		{
			fir::Function* p2func = cs->module->getIntrinsicFunction("roundup_pow2");
			iceAssert(p2func);

			fir::Value* nextpow2 = cs->irb.CreateCall1(p2func, needed, "nextpow2");

			fir::Function* mallocf = cs->getOrDeclareLibCFunction(ALLOCATE_MEMORY_FUNC);
			iceAssert(mallocf);

			fir::Value* actuallen = cs->irb.CreateMul(nextpow2, cs->irb.CreateSizeof(elmtype));
			fir::Value* newptr = cs->irb.CreateCall1(mallocf, actuallen);


			// memcpy
			fir::Function* memcpyf = cs->module->getIntrinsicFunction("memmove");

			cs->irb.CreateCall(memcpyf, { cs->irb.CreatePointerTypeCast(newptr, fir::Type::getInt8Ptr()),
				cs->irb.CreatePointerTypeCast(ptr, fir::Type::getInt8Ptr()), actuallen, fir::ConstantInt::getInt32(0),
				fir::ConstantBool::get(false) });


			fir::Value* ret = cs->irb.CreateSetDynamicArrayData(arr, cs->irb.CreatePointerTypeCast(newptr, ptr->getType()));
			ret = cs->irb.CreateSetDynamicArrayCapacity(ret, nextpow2);

			cs->irb.CreateUnCondBranch(mergeblk);

			growNewPhi = ret;
		}



		cs->irb.setCurrentBlock(mergeblk);
		{
			auto phi = cs->irb.CreatePHINode(arr->getType());
			phi->addIncoming(arr, cb);
			phi->addIncoming(growPhi, growblk);
			phi->addIncoming(growNewPhi, growNewblk);

			return phi;
		}
	}



	fir::Function* getAppendFunction(CodegenState* cs, fir::DynamicArrayType* arrtype)
	{
		iceAssert(arrtype);

		auto name = BUILTIN_DYNARRAY_APPEND_FUNC_NAME + std::string("_") + arrtype->encodedStr();
		fir::Function* appendf = cs->module->getFunction(Identifier(name, IdKind::Name));

		if(!appendf)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(name, IdKind::Name),
				fir::FunctionType::get({ arrtype, arrtype }, arrtype), fir::LinkageType::Internal);

			func->setAlwaysInline();

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			cs->irb.setCurrentBlock(entry);

			fir::Value* s1 = func->getArguments()[0];
			fir::Value* s2 = func->getArguments()[1];

			auto elmType = arrtype->getElementType();


			// get the second one
			{
				fir::Value* origlen = cs->irb.CreateGetDynamicArrayLength(s1);
				fir::Value* applen = cs->irb.CreateGetDynamicArrayLength(s2);

				// grow if needed
				s1 = _checkCapacityAndGrowIfNeeded(cs, func, s1, applen);

				// // we should be ok, now copy.<commit_msg>hopefully fix some refcounting issues with arrays<commit_after>// arrays.cpp
// Copyright (c) 2014 - 2017, <EMAIL>
// Licensed under the Apache License Version 2.0.

#include "codegen.h"

#define BUILTIN_ARRAY_BOUNDS_CHECK_FUNC_NAME		"__array_boundscheck"
#define BUILTIN_ARRAY_DECOMP_BOUNDS_CHECK_FUNC_NAME	"__array_boundscheckdecomp"

#define BUILTIN_ARRAY_CMP_FUNC_NAME					"__array_compare"

#define BUILTIN_DYNARRAY_CLONE_FUNC_NAME			"__darray_clone"
#define BUILTIN_DYNARRAY_APPEND_FUNC_NAME			"__darray_append"
#define BUILTIN_DYNARRAY_APPEND_ELEMENT_FUNC_NAME	"__darray_appendelement"
#define BUILTIN_DYNARRAY_POP_BACK_FUNC_NAME			"__darray_popback"
#define BUILTIN_DYNARRAY_MAKE_FROM_TWO_FUNC_NAME	"__darray_combinetwo"

#define BUILTIN_SLICE_CLONE_FUNC_NAME				"__slice_clone"
#define BUILTIN_SLICE_APPEND_FUNC_NAME				"__slice_append"
#define BUILTIN_SLICE_APPEND_ELEMENT_FUNC_NAME		"__slice_appendelement"

#define BUILTIN_LOOP_INCR_REFCOUNT_FUNC_NAME		"__loop_incr_refcount"
#define BUILTIN_LOOP_DECR_REFCOUNT_FUNC_NAME		"__loop_decr_refcount"


namespace cgn {
namespace glue {
namespace array
{
	fir::Function* getBoundsCheckFunction(CodegenState* cs, bool isPerformingDecomposition)
	{
		fir::Function* fn = cs->module->getFunction(Identifier(isPerformingDecomposition
			? BUILTIN_ARRAY_DECOMP_BOUNDS_CHECK_FUNC_NAME : BUILTIN_ARRAY_BOUNDS_CHECK_FUNC_NAME, IdKind::Name));

		if(!fn)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(isPerformingDecomposition ? BUILTIN_ARRAY_DECOMP_BOUNDS_CHECK_FUNC_NAME : BUILTIN_ARRAY_BOUNDS_CHECK_FUNC_NAME, IdKind::Name),
				fir::FunctionType::get({ fir::Type::getInt64(), fir::Type::getInt64(), fir::Type::getString() },
					fir::Type::getVoid()), fir::LinkageType::Internal);

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			fir::IRBlock* failb = cs->irb.addNewBlockInFunction("fail", func);
			fir::IRBlock* checkneg = cs->irb.addNewBlockInFunction("checkneg", func);
			fir::IRBlock* merge = cs->irb.addNewBlockInFunction("merge", func);

			cs->irb.setCurrentBlock(entry);

			fir::Value* max = func->getArguments()[0];
			fir::Value* ind = func->getArguments()[1];

			fir::Value* res = 0;

			// if we're decomposing, it's length vs length, so compare strictly greater.
			if(isPerformingDecomposition)
				res = cs->irb.CreateICmpGT(ind, max);

			else
				res = cs->irb.CreateICmpGEQ(ind, max);

			iceAssert(res);

			cs->irb.CreateCondBranch(res, failb, checkneg);
			cs->irb.setCurrentBlock(failb);
			{
				fir::Function* fprintfn = cs->module->getOrCreateFunction(Identifier("fprintf", IdKind::Name),
					fir::FunctionType::getCVariadicFunc({ fir::Type::getVoidPtr(), fir::Type::getInt8Ptr() },
					fir::Type::getInt32()), fir::LinkageType::External);

				fir::Function* fdopenf = cs->module->getOrCreateFunction(Identifier("fdopen", IdKind::Name),
					fir::FunctionType::get({ fir::Type::getInt32(), fir::Type::getInt8Ptr() }, fir::Type::getVoidPtr()),
					fir::LinkageType::External);

				// basically:
				// void* stderr = fdopen(2, "w")
				// fprintf(stderr, "", bla bla)

				fir::ConstantValue* tmpstr = cs->module->createGlobalString("w");
				fir::ConstantValue* fmtstr = 0;

				if(isPerformingDecomposition)
					fmtstr = cs->module->createGlobalString("%s: Tried to decompose array into '%zd' elements; length is only '%zd'\n");

				else
					fmtstr = cs->module->createGlobalString("%s: Tried to index array at index '%zd'; length is only '%zd'\n");

				iceAssert(fmtstr);

				fir::Value* posstr = cs->irb.CreateGetStringData(func->getArguments()[2]);
				fir::Value* err = cs->irb.CreateCall2(fdopenf, fir::ConstantInt::getInt32(2), tmpstr);

				cs->irb.CreateCall(fprintfn, { err, fmtstr, posstr, ind, max });

				cs->irb.CreateCall0(cs->getOrDeclareLibCFunction("abort"));
				cs->irb.CreateUnreachable();
			}

			cs->irb.setCurrentBlock(checkneg);
			{
				fir::Value* res2 = cs->irb.CreateICmpLT(ind, fir::ConstantInt::getInt64(0));
				cs->irb.CreateCondBranch(res2, failb, merge);
			}

			cs->irb.setCurrentBlock(merge);
			{
				cs->irb.CreateReturnVoid();
			}

			fn = func;

			cs->irb.setCurrentBlock(restore);
		}

		iceAssert(fn);
		return fn;
	}





	static void _callCloneFunctionInLoop(CodegenState* cs, fir::Function* curfunc, fir::Function* fn,
		fir::Value* ptr, fir::Value* len, fir::Value* newptr, fir::Value* startIndex)
	{
		fir::IRBlock* loopcond = cs->irb.addNewBlockInFunction("loopcond", curfunc);
		fir::IRBlock* loopbody = cs->irb.addNewBlockInFunction("loopbody", curfunc);
		fir::IRBlock* merge = cs->irb.addNewBlockInFunction("merge", curfunc);

		fir::Value* counter = cs->irb.CreateStackAlloc(fir::Type::getInt64());
		cs->irb.CreateStore(startIndex, counter);

		cs->irb.CreateUnCondBranch(loopcond);
		cs->irb.setCurrentBlock(loopcond);
		{
			fir::Value* res = cs->irb.CreateICmpEQ(cs->irb.CreateLoad(counter), len);
			cs->irb.CreateCondBranch(res, merge, loopbody);
		}

		cs->irb.setCurrentBlock(loopbody);
		{
			// make clone
			fir::Value* origElm = cs->irb.CreatePointerAdd(ptr, cs->irb.CreateLoad(counter));
			fir::Value* clone = 0;

			if(fn->getArgumentCount() == 1)
				clone = cs->irb.CreateCall1(fn, cs->irb.CreateLoad(origElm));
			else
				clone = cs->irb.CreateCall2(fn, cs->irb.CreateLoad(origElm), fir::ConstantInt::getInt64(0));

			// store clone
			fir::Value* newElm = cs->irb.CreatePointerAdd(newptr, cs->irb.CreateLoad(counter));
			cs->irb.CreateStore(clone, newElm);

			// increment counter
			cs->irb.CreateStore(cs->irb.CreateAdd(cs->irb.CreateLoad(counter), fir::ConstantInt::getInt64(1)), counter);
			cs->irb.CreateUnCondBranch(loopcond);
		}

		cs->irb.setCurrentBlock(merge);
	}


	static void _handleCallingAppropriateCloneFunction(CodegenState* cs, fir::Function* func, fir::Type* elmType, fir::Value* origptr,
		fir::Value* newptr, fir::Value* origlen, fir::Value* actuallen, fir::Value* startIndex)
	{
		if(elmType->isPrimitiveType() || elmType->isCharType() || elmType->isEnumType())
		{
			fir::Function* memcpyf = cs->module->getIntrinsicFunction("memmove");

			cs->irb.CreateCall(memcpyf, { newptr, cs->irb.CreatePointerTypeCast(cs->irb.CreatePointerAdd(origptr,
				startIndex), fir::Type::getInt8Ptr()), actuallen, fir::ConstantInt::getInt32(0), fir::ConstantBool::get(false) });
		}
		else if(elmType->isDynamicArrayType())
		{
			// yo dawg i heard you like arrays...
			fir::Function* clonef = getCloneFunction(cs, elmType->toDynamicArrayType());
			iceAssert(clonef);

			// loop
			fir::Value* cloneptr = cs->irb.CreatePointerTypeCast(newptr, elmType->getPointerTo());
			_callCloneFunctionInLoop(cs, func, clonef, origptr, origlen, cloneptr, startIndex);
		}
		else if(elmType->isArraySliceType())
		{
			// yo dawg i heard you like arrays...
			fir::Function* clonef = getCloneFunction(cs, elmType->toArraySliceType());
			iceAssert(clonef);

			// loop
			fir::Value* cloneptr = cs->irb.CreatePointerTypeCast(newptr, elmType->getPointerTo());
			_callCloneFunctionInLoop(cs, func, clonef, origptr, origlen, cloneptr, startIndex);
		}
		else if(elmType->isStringType())
		{
			fir::Function* clonef = glue::string::getCloneFunction(cs);
			iceAssert(clonef);

			// loop
			fir::Value* cloneptr = cs->irb.CreatePointerTypeCast(newptr, elmType->getPointerTo());
			_callCloneFunctionInLoop(cs, func, clonef, origptr, origlen, cloneptr, startIndex);
		}
		else if(elmType->isStructType() || elmType->isClassType() || elmType->isTupleType() || elmType->isArrayType())
		{
			// todo: call copy constructors and stuff

			fir::Function* memcpyf = cs->module->getIntrinsicFunction("memmove");

			cs->irb.CreateCall(memcpyf, { newptr, cs->irb.CreatePointerTypeCast(cs->irb.CreatePointerAdd(origptr,
				startIndex), fir::Type::getInt8Ptr()), actuallen, fir::ConstantInt::getInt32(0), fir::ConstantBool::get(false) });
		}
		else
		{
			error("unsupported element type '%s' for array clone", elmType->str());
		}
	}








	fir::Function* getCloneFunction(CodegenState* cs, fir::Type* arrtype)
	{
		if(arrtype->isDynamicArrayType())		return getCloneFunction(cs, arrtype->toDynamicArrayType());
		else if(arrtype->isArraySliceType())	return getCloneFunction(cs, arrtype->toArraySliceType());
		else									error("unsupported type '%s'", arrtype->str());
	}

	// takes ptr, start index
	fir::Function* getCloneFunction(CodegenState* cs, fir::DynamicArrayType* arrtype)
	{
		auto name = BUILTIN_DYNARRAY_CLONE_FUNC_NAME + std::string("_") + arrtype->encodedStr();

		fir::Function* fn = cs->module->getFunction(Identifier(name, IdKind::Name));

		if(!fn)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(name, IdKind::Name),
				fir::FunctionType::get({ arrtype, fir::Type::getInt64() }, arrtype),
				fir::LinkageType::Internal);

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			fir::IRBlock* insane = cs->irb.addNewBlockInFunction("insane", func);
			fir::IRBlock* merge1 = cs->irb.addNewBlockInFunction("merge1", func);

			cs->irb.setCurrentBlock(entry);

			fir::Value* orig = func->getArguments()[0];
			fir::Value* startIndex = func->getArguments()[1];

			iceAssert(orig);
			iceAssert(startIndex);



			fir::Value* origptr = cs->irb.CreateGetDynamicArrayData(orig, "origptr");
			fir::Value* origlen = cs->irb.CreateGetDynamicArrayLength(orig, "origlen");

			fir::Value* origcap = cs->irb.CreateGetDynamicArrayCapacity(orig);
			// cs->irb.CreateStore(origcap, cap);


			// note: sanity check that len <= cap
			fir::Value* sane = cs->irb.CreateICmpLEQ(origlen, origcap);
			cs->irb.CreateCondBranch(sane, merge1, insane);


			cs->irb.setCurrentBlock(insane);
			{
				// sanity check failed
				// *but* since we're using dyn arrays as vararg arrays,
				// then we just treat capacity = length.

				cs->irb.CreateUnCondBranch(merge1);
			}


			// ok, back to normal
			cs->irb.setCurrentBlock(merge1);
			auto cap = cs->irb.CreatePHINode(fir::Type::getInt64());
			cap->addIncoming(origcap, entry);
			cap->addIncoming(origlen, insane);


			// ok, alloc a buffer with the original capacity
			// get size in bytes, since cap is in elements
			fir::Value* actuallen = cs->irb.CreateMul(cap, cs->irb.CreateSizeof(arrtype->getElementType()));

			// space for refcount
			auto i64size = fir::ConstantInt::getInt64(8);
			actuallen = cs->irb.CreateAdd(actuallen, i64size);


			fir::Function* mallocf = cs->getOrDeclareLibCFunction(ALLOCATE_MEMORY_FUNC);
			iceAssert(mallocf);

			fir::Value* newptr = cs->irb.CreateCall1(mallocf, actuallen);
			newptr = cs->irb.CreatePointerAdd(newptr, i64size);

			fir::Type* elmType = arrtype->getElementType();
			_handleCallingAppropriateCloneFunction(cs, func, elmType, origptr, newptr, origlen, actuallen, startIndex);

			fir::Value* newarr = cs->irb.CreateValue(arrtype);
			newarr = cs->irb.CreateSetDynamicArrayData(newarr, cs->irb.CreatePointerTypeCast(newptr, arrtype->getElementType()->getPointerTo()));
			newarr = cs->irb.CreateSetDynamicArrayLength(newarr, cs->irb.CreateSub(origlen, startIndex));
			newarr = cs->irb.CreateSetDynamicArrayCapacity(newarr, cap);
			cs->irb.CreateSetDynamicArrayRefCount(newarr, fir::ConstantInt::getInt64(1));

			cs->irb.CreateReturn(newarr);

			fn = func;
			cs->irb.setCurrentBlock(restore);
		}

		iceAssert(fn);
		return fn;
	}









	// takes a slice, but returns a dynamic array
	fir::Function* getCloneFunction(CodegenState* cs, fir::ArraySliceType* arrtype)
	{
		auto name = BUILTIN_SLICE_CLONE_FUNC_NAME + std::string("_") + arrtype->encodedStr();

		fir::Function* fn = cs->module->getFunction(Identifier(name, IdKind::Name));

		if(!fn)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(name, IdKind::Name),
				fir::FunctionType::get({ arrtype, fir::Type::getInt64() },
					fir::DynamicArrayType::get(arrtype->getElementType())), fir::LinkageType::Internal);

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			fir::IRBlock* merge1 = cs->irb.addNewBlockInFunction("merge1", func);

			cs->irb.setCurrentBlock(entry);

			fir::Value* orig = func->getArguments()[0];
			fir::Value* startIndex = func->getArguments()[1];

			iceAssert(orig);
			iceAssert(startIndex);

			fir::Value* origptr = cs->irb.CreateGetArraySliceData(orig);
			fir::Value* origlen = cs->irb.CreateGetArraySliceLength(orig);

			cs->irb.CreateUnCondBranch(merge1);

			// ok, back to normal
			cs->irb.setCurrentBlock(merge1);

			// ok, alloc a buffer with the original capacity
			// get size in bytes, since cap is in elements
			fir::Value* actuallen = cs->irb.CreateMul(origlen, cs->irb.CreateSizeof(arrtype->getElementType()));

			// refcount space
			auto i64size = fir::ConstantInt::getInt64(8);
			actuallen = cs->irb.CreateAdd(actuallen, i64size);


			fir::Function* mallocf = cs->getOrDeclareLibCFunction(ALLOCATE_MEMORY_FUNC);
			iceAssert(mallocf);

			fir::Value* newptr = cs->irb.CreateCall1(mallocf, actuallen);
			newptr = cs->irb.CreatePointerAdd(newptr, i64size);

			fir::Type* elmType = arrtype->getElementType();
			_handleCallingAppropriateCloneFunction(cs, func, elmType, origptr, newptr, origlen, actuallen, startIndex);

			fir::Value* newarr = cs->irb.CreateValue(fir::DynamicArrayType::get(arrtype->getElementType()));
			newarr = cs->irb.CreateSetDynamicArrayData(newarr, cs->irb.CreatePointerTypeCast(newptr, arrtype->getElementType()->getPointerTo()));
			newarr = cs->irb.CreateSetDynamicArrayLength(newarr, cs->irb.CreateSub(origlen, startIndex));
			newarr = cs->irb.CreateSetDynamicArrayCapacity(newarr, cs->irb.CreateSub(origlen, startIndex));
			cs->irb.CreateSetDynamicArrayRefCount(newarr, fir::ConstantInt::getInt64(1));

			cs->irb.CreateReturn(newarr);

			fn = func;
			cs->irb.setCurrentBlock(restore);
		}

		iceAssert(fn);
		return fn;
	}






	// static void _growCapacityBy(CodegenState* cs, fir::Function* func, fir::Value* arr, fir::Value* amt)
	// {
	// 	iceAssert(arr->getType()->isPointerType());
	// 	iceAssert(arr->getType()->getPointerElementType()->isDynamicArrayType());
	// 	iceAssert(amt->getType() == fir::Type::getInt64());
	// }


	// required is how much *EXTRA* space we need.
	static fir::Value* _checkCapacityAndGrowIfNeeded(CodegenState* cs, fir::Function* func, fir::Value* arr, fir::Value* required)
	{
		iceAssert(arr->getType()->isDynamicArrayType());
		iceAssert(required->getType() == fir::Type::getInt64());

		auto elmtype = arr->getType()->getArrayElementType();

		fir::Value* ptr = cs->irb.CreateGetDynamicArrayData(arr, "ptr");
		fir::Value* len = cs->irb.CreateGetDynamicArrayLength(arr, "len");
		fir::Value* cap = cs->irb.CreateGetDynamicArrayCapacity(arr, "cap");
		fir::Value* refcnt = cs->irb.CreateGetDynamicArrayRefCount(arr, "refcount");

		// check if len + required > cap
		fir::Value* needed = cs->irb.CreateAdd(len, required, "needed");
		fir::Value* cond = cs->irb.CreateICmpGT(needed, cap);



		fir::IRBlock* cb = cs->irb.getCurrentBlock();

		fir::IRBlock* trampoline = cs->irb.addNewBlockInFunction("trampoline", func);
		fir::IRBlock* growblk = cs->irb.addNewBlockInFunction("grow", func);

		// for when the 'dynamic' array came from a literal. same as the usual stuff
		// capacity will be -1, in this case.
		fir::IRBlock* growNewblk = cs->irb.addNewBlockInFunction("growFromScratch", func);

		fir::IRBlock* mergeblk = cs->irb.addNewBlockInFunction("merge", func);
		cs->irb.CreateCondBranch(cond, trampoline, mergeblk);

		cs->irb.setCurrentBlock(trampoline);
		{
			auto cond = cs->irb.CreateICmpEQ(cap, fir::ConstantInt::getInt64(-1));
			cs->irb.CreateCondBranch(cond, growNewblk, growblk);
		}

		// return a phi node.
		fir::Value* growPhi = 0;
		fir::Value* growNewPhi = 0;


		// grows to the nearest power of two from (len + required)
		cs->irb.setCurrentBlock(growblk);
		{
			fir::Function* p2func = cs->module->getIntrinsicFunction("roundup_pow2");
			iceAssert(p2func);

			fir::Value* nextpow2 = cs->irb.CreateCall1(p2func, needed, "nextpow2");

			fir::Function* refunc = cs->getOrDeclareLibCFunction(REALLOCATE_MEMORY_FUNC);
			iceAssert(refunc);

			auto dataptr = cs->irb.CreatePointerTypeCast(ptr, fir::Type::getInt8Ptr());
			dataptr = cs->irb.CreatePointerSub(dataptr, fir::ConstantInt::getInt64(8));

			fir::Value* actuallen = cs->irb.CreateMul(nextpow2, cs->irb.CreateSizeof(elmtype));
			fir::Value* newptr = cs->irb.CreateCall2(refunc, dataptr, actuallen);
			newptr = cs->irb.CreatePointerAdd(newptr, fir::ConstantInt::getInt64(8));


			fir::Value* ret = cs->irb.CreateSetDynamicArrayData(arr, cs->irb.CreatePointerTypeCast(newptr, ptr->getType()));
			ret = cs->irb.CreateSetDynamicArrayCapacity(ret, nextpow2);
			cs->irb.CreateSetDynamicArrayRefCount(ret, refcnt);

			cs->irb.CreateUnCondBranch(mergeblk);

			growPhi = ret;
		}


		// makes a new memory piece, to the nearest power of two from (len + required)
		cs->irb.setCurrentBlock(growNewblk);
		{
			fir::Function* p2func = cs->module->getIntrinsicFunction("roundup_pow2");
			iceAssert(p2func);

			fir::Value* nextpow2 = cs->irb.CreateCall1(p2func, needed, "nextpow2");

			fir::Function* mallocf = cs->getOrDeclareLibCFunction(ALLOCATE_MEMORY_FUNC);
			iceAssert(mallocf);

			fir::Value* actuallen = cs->irb.CreateMul(nextpow2, cs->irb.CreateSizeof(elmtype));

			// refcount space
			actuallen = cs->irb.CreateAdd(actuallen, fir::ConstantInt::getInt64(8));

			fir::Value* newptr = cs->irb.CreateCall1(mallocf, actuallen);
			newptr = cs->irb.CreatePointerAdd(newptr, fir::ConstantInt::getInt64(8));


			// memcpy
			fir::Function* memcpyf = cs->module->getIntrinsicFunction("memmove");

			cs->irb.CreateCall(memcpyf, { cs->irb.CreatePointerTypeCast(newptr, fir::Type::getInt8Ptr()),
				cs->irb.CreatePointerTypeCast(ptr, fir::Type::getInt8Ptr()), actuallen, fir::ConstantInt::getInt32(0),
				fir::ConstantBool::get(false) });


			fir::Value* ret = cs->irb.CreateSetDynamicArrayData(arr, cs->irb.CreatePointerTypeCast(newptr, ptr->getType()));
			ret = cs->irb.CreateSetDynamicArrayCapacity(ret, nextpow2);
			cs->irb.CreateSetDynamicArrayRefCount(ret, refcnt);

			cs->irb.CreateUnCondBranch(mergeblk);

			growNewPhi = ret;
		}



		cs->irb.setCurrentBlock(mergeblk);
		{
			auto phi = cs->irb.CreatePHINode(arr->getType());
			phi->addIncoming(arr, cb);
			phi->addIncoming(growPhi, growblk);
			phi->addIncoming(growNewPhi, growNewblk);

			return phi;
		}
	}



	fir::Function* getAppendFunction(CodegenState* cs, fir::DynamicArrayType* arrtype)
	{
		iceAssert(arrtype);

		auto name = BUILTIN_DYNARRAY_APPEND_FUNC_NAME + std::string("_") + arrtype->encodedStr();
		fir::Function* appendf = cs->module->getFunction(Identifier(name, IdKind::Name));

		if(!appendf)
		{
			auto restore = cs->irb.getCurrentBlock();

			fir::Function* func = cs->module->getOrCreateFunction(Identifier(name, IdKind::Name),
				fir::FunctionType::get({ arrtype, arrtype }, arrtype), fir::LinkageType::Internal);

			func->setAlwaysInline();

			fir::IRBlock* entry = cs->irb.addNewBlockInFunction("entry", func);
			cs->irb.setCurrentBlock(entry);

			fir::Value* s1 = func->getArguments()[0];
			fir::Value* s2 = func->getArguments()[1];

			auto elmType = arrtype->getElementType();


			// get the second one
			{
				fir::Value* origlen = cs->irb.CreateGetDynamicArrayLength(s1);
				fir::Value* applen = cs->irb.CreateGetDynamicArrayLength(s2);

				// grow if needed
				s1 = _checkCapacityAndGrowIfNeeded(cs, func, s1, applen);

				// we should be ok, now copy.
{'fraction_non_alphanumeric': 0.15829762775629638, 'fraction_numerical': 0.007393667049848469, 'mean_word_length': 5.19669742593492, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 522, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '338173', 'n_tokens_mistral': 15023, 'n_tokens_neox': 13516, 'n_words': 2193}