use lang;
use lang:bs:macro;
use core:lang;
use core:asm;

/**
 * Class that allows asking PatchState for package equivalence.
 */
class PatchEquivalence on Compiler {
	// Patch state to use for queries.
	private PatchState state;

	// Create.
	package init(PatchState state) {
		init { state = state; }
	}

	// See if 'named' has the parent 'parent', considers the fact that 'named' may reside inside a
	// copy of the name tree.
	Bool namedHasParent(Named named, NameLookup parent) {
		state.namedHasParent(named, parent);
	}
}

/**
 * State when patching an entire program.
 *
 * Bundles some common parameters, and keeps track of what needs to be done.
 */
private class PatchState on Compiler {
	// Program instance we're patching for.
	Program program;

	// Hints available.
	Hints[] hints;

	// Package where our code is located.
	Package pkg;

	// Remember which functions we have patched.
	private Function->RefSource patched;

	// Queue of functions to patch.
	private Queue<Function> toPatch;

	// Create.
	init(Program program, Hints[] hints, Package pkg) {
		init {
			program = program;
			hints = hints;
			pkg = pkg;
		}
	}

	// Replace a reference to an instance in a temporary package with the corresponding one in the
	// real package.
	Ref replaceRef(Ref r) {
		unless (namedSrc = r.source as NamedSource)
			return r;

		Named res = replaceNamed(namedSrc.named);
		if (res as Function) {
			if (namedSrc.type == Char()) {
				return res.ref;
			} else if (namedSrc.type == 't') {
				return res.thunkRef;
			} else if (namedSrc.type == 'd') {
				return res.directRef;
			} else {
				throw InternalError("Unknown subtype of function reference.");
			}
		} else if (res as Type) {
			return res.typeRef;
		} else {
			return r;
		}
	}

	// Replace a named object.
	Named replaceNamed(Named n) {
		unless (temp = findTemp(n)) {
			return n;
		}

		SimpleName relative = n.path.from(temp.path.count);
		if (found = findPrivate(temporary.get(temp), relative)) {
			return found;
		}

		n;
	}

	// Check if we should patch a function?
	Bool needsPatch(Function fn) {
		// Note: We ask *all* hint objects if we should patch the function. That way they
		// collectively create a "union" of things to patch, which is more sensible than only asking
		// the hints for the language that is currently being compiled (otherwise, certain refactors
		// of the C++ runtime implementation would make this break).
		PatchEquivalence eq(this);
		for (hint in hints)
			if (hint.code.patchExternal(eq, fn))
				return true;
		return false;
	}

	// Get a new reference for a function that needs patching. Make sure the function is patched
	// eventually if that has not been done already.
	Ref patchFn(Function fn) {
		if (f = patched.at(fn))
			return Ref(f);

		NamedSource src(fn);
		patched.put(fn, src);
		toPatch.push(fn);

		return Ref(src);
	}

	// Patch all remaining functions in the queue.
	void patchRemaining() {
		while (toPatch.any) {
			var fn = toPatch.top;
			toPatch.pop();

			var into = patched.get(fn);
			if (source = findSource(fn)) {
				// print("Patching ${fn}...");
				Listing l = patchListing(this, findHints(hints, fn), source, fn, true);
				into.set(Binary(arena, l));
			} else {
				// Fallback, to avoid crashes.
				print("Failed to patch ${fn}.");
				into.set(DelegatedContent(fn.ref));
			}
		}
	}

	// Loaded packages.
	private Str->Package loaded;

	// Keep track of loaded packages so that we may quickly see if a reference is inside it.
	// Maps 'temporary'->'original'
	private Package->Package temporary;

	// Attempts to find the code of a function. This might involve loading the contained package again.
	private Listing? findSource(Function fn) {
		fn = traverseDelegated(fn);

		unless (code = fn.getCode() as GeneratedCode)
			return null;

		if (source = code.source)
			return source;

		// Try to re-load the package if possible.
		Package contained = findPkg(fn);
		unless (url = contained.url)
			return null;

		SimpleName pkgName = contained.path;
		Str pkgKey = pkgName.toS;
		Package pkg = if (p = loaded.at(pkgKey)) {
			p;
		} else {
			Package p(url);
			p.retainSource();
			p.parentLookup = contained.parent;
			loaded.put(pkgKey, p);
			temporary.put(p, contained);
			p;
		};

		SimpleName relative = fn.path.from(pkgName.count);

		if (fn = findPrivate(pkg, relative) as Function) {
			unless (code = fn.getCode() as GeneratedCode)
				return null;
			if (source = code.source)
				return source;
		}

		return null;
	}

	// Traverse layers of 'generatedCode' if needed.
	private Function traverseDelegated(Function fn) : static {
		if (delegated = fn.getCode() as DelegatedCode) {
			if (target = delegated.to.source as NamedSource) {
				if (f = target.named as Function) {
					return traverseDelegated(f);
				}
			}
		}
		fn;
	}

	// Find a temporary package.
	private Package? findTemp(Named named) {
		NameLookup? at = named;
		while (here = at) {
			if (here as Package) {
				if (temporary.has(here))
					return here;
			}

			at = here.parent;
		}
		null;
	}

	// See if a named has a specific parent, considering our mapping in 'temporary'.
	Bool namedHasParent(Named named, NameLookup parent) {
		NameLookup current = named;
		while (next = current.parent) {
			if (next is parent)
				return true;

			if (next as Package) {
				if (real = temporary.at(next)) {
					if (real is parent)
						return true;
				}
			}
			current = next;
		}
		return false;
	}

	// Find the closest package to a function.
	private Package findPkg(Named named) : static {
		NameLookup? at = named;
		while (here = at) {
			if (here as Package)
				return here;

			at = here.parent;
		}
		throw InternalError("No package found for ${named}");
	}

	// Find a named entity, but allowed to access private members.
	private Named? findPrivate(NameSet root, SimpleName name) : static {
		Scope scope = rootScope;
		Named? at = root;
		for (Nat i = 0; i < name.count; i++) {
			if (ns = at as NameSet)
				// Compare with a looser equality in the parameters.
				at = ns.find(Part(name[i]), scope.child(ns));
			else
				return null;
		}
		at;
	}

	// Custom name part that compares the path rather than objects for object identity since we have
	// multiple versions of the same thing.
	private class Part extends SimplePart {
		init(SimplePart s) {
			init(s) {}
		}

		Bool visible(Named candidate, Scope source) : override {
			// Just ignore visibility.
			true;
		}

		Int matches(Named candidate, Scope source) : override {
			if (candidate.params.count != params.count)
				return -1;

			for (Nat i = 0; i < params.count; i++) {
				Value a = candidate.params[i];
				Value b = params[i];

				if (a.ref != b.ref)
					return -1;
				if (a != b)
					if (a.toS != b.toS)
						return -1;
			}

			// It is a perfect match, we only get one of them.
			0;
		}
	}

}

// Patch all functions in the specified NameSet recursively.
// TODO: We don't really support threads at the moment, perhaps we should
// explicitly disallow that somehow?
package void patchFunctions(Program program, Hints[] hints, Package pkg) on Compiler {
	PatchState state(program, hints, pkg);
	patchFunctions(state, pkg);

	// Patch any functions outside 'pkg' here.
	state.patchRemaining();
}

// Recursively patch all functions in a name set.
private void patchFunctions(PatchState state, NameSet inside) on Compiler {
	inside.forceLoad();

	for (named in inside) {
		if (named as Function) {
			patchFunction(state, named);
		} else if (named as NameSet) {
			patchFunctions(state, named);
		}
	}
}

// Patch a single function, adding code for instrumentation at each "location" statement in the
// listing. This makes it possible for us to "single step" the program, since we get called
// at each relevant location.
private void patchFunction(PatchState state, Function fn) on Compiler {
	unless (code = fn.getCode() as GeneratedCode)
		return;

	unless (source = code.source) {
		print("Warning: Unable to patch ${fn}, no code!");
		return;
	}

	// If it does not have any "source" instructions, ignore stepping through it. Only track memory.
	Bool onlyMemory = !anyLocation(source);

	// print("Source: ${source}");

	// Find the hint object responsible for this function.
	var hint = findHints(state.hints, fn);

	Listing patched = patchListing(state, hint, source, fn, onlyMemory);
	fn.setCode(DynamicCode(patched));
}

// Find the hint responsible for this function.
private Hints findHints(Hints[] hints, Function fn) on Compiler {
	for (h in hints)
		if (h.code.handlesFunction(fn))
			return h;

	// Default if none is found (will more or less never happen, as the last element in 'hints' is 'defHints()'.
	return defaultHints();
}

// Common parameters to the code generation functions.
class PatchParams on Compiler {
	Package pkg;
	CodeHints codeHints;
	progvis:data:ViewHints viewHints;
	Listing to;
	Block block;
	Set<Nat> inactive;

	// Saved registers.
	Var saveA;
	Var saveB;
	Var saveC;

	// Contains the memory tracker instance returned by 'onFunctionEntered'.
	Var memTracker;
	Var tmpAddr;

	init(Package pkg, Hints hints, Listing to) {
		init() {
			pkg = pkg;
			codeHints = hints.code;
			viewHints = if (v = hints.view) { v; } else { progvis:data:DefaultViewHints(); };
			to = to;
			saveA = to.createVar(to.root, sLong);
			saveB = to.createVar(to.root, sLong);
			saveC = to.createVar(to.root, sLong);

			memTracker = to.createVar(to.root, sPtr);
			tmpAddr = to.createVar(to.root, sPtr);
		}
	}

	// Save registers.
	void saveRegs() {
		to << mov(saveA, rax);
		to << mov(saveB, rbx);
		to << mov(saveC, rcx);
	}

	// Restore registers.
	void restoreRegs() {
		to << mov(rax, saveA);
		to << mov(rbx, saveB);
		to << mov(rcx, saveC);
	}

	// Record that we read from memory. 'op' should be something we can use with 'lea'.
	void recordRead(Operand op) {
		to << lea(tmpAddr, op);
		to << fnParam(ptrDesc, memTracker);
		to << fnParam(ptrDesc, tmpAddr);
		to << fnCall(named{MemTracker:addRead<MemTracker, lang:unknown:PTR_NOGC>}.ref, true);
	}
	void recordReadRef(Operand op) {
		to << mov(tmpAddr, op);
		to << fnParam(ptrDesc, memTracker);
		to << fnParam(ptrDesc, tmpAddr);
		to << fnCall(named{MemTracker:addRead<MemTracker, lang:unknown:PTR_NOGC>}.ref, true);
	}

	// Record that we wrote to a register. 'op' should be something we can use with 'lea'.
	void recordWrite(Operand op) {
		to << lea(tmpAddr, op);
		to << fnParam(ptrDesc, memTracker);
		to << fnParam(ptrDesc, tmpAddr);
		to << fnCall(named{MemTracker:addWrite<MemTracker, lang:unknown:PTR_NOGC>}.ref, true);
	}
	void recordWriteRef(Operand op) {
		to << mov(tmpAddr, op);
		to << fnParam(ptrDesc, memTracker);
		to << fnParam(ptrDesc, tmpAddr);
		to << fnCall(named{MemTracker:addWrite<MemTracker, lang:unknown:PTR_NOGC>}.ref, true);
	}
}

// Patch a source listing. If 'onlyMemory' is true, we will only inject code for tracking memory
// accesses, not for stepping.
private Listing patchListing(PatchState state, Hints hints, Listing source, Function fn, Bool onlyMemory) on Compiler {
	Listing dest = source.createShell();
	PatchParams params(state.pkg, hints, dest);

	for (var in source.allVars()) {
		if (source.freeOpt(var).has(FreeOpt:inactive))
			params.inactive.put(var.key());
	}

	// Labels we have seen so far. This is so that we can detect back edges.
	Set<Nat> seenLabels;

	for (Nat i = 0; i < source.count; i++) {
		if (labels = source.labels(i)) {
			dest << labels;
			for (x in labels)
				seenLabels.put(x.key);
		}
		Instr instr = replaceRefs(state, source[i]);

		if (instr.op == OpCode:fnRet) {
			// Check parameters now.
			checkMemAccess(params, instr);
			if (!onlyMemory)
				generateReturnCall(state.program, params, fn, false, instr.src);
		} else if (instr.op == OpCode:fnRetRef) {
			// Trigger a read from the parameter. This won't be done unless we do it now.
			params.saveRegs();
			params.recordReadRef(instr.src);
			params.restoreRegs();
			if (!onlyMemory)
				generateReturnCall(state.program, params, fn, true, instr.src);
		} else if (instr.op == OpCode:fnCall | instr.op == OpCode:fnCallRef) {
			// Note: This path should not hit the 'else' branch below, even though it
			// might seem that way.
			instr = patchCall(state, instr);
		} else if (instr.op == OpCode:fnParam | instr.op == OpCode:fnParamRef) {
			// For paramerers, we must make sure that we handle all of them at once, so that we
			// don't insert a call between fnParam instructions. That is very bad.
			if (!lastFnParam(source, i)) {
				checkParamAccess(params, source, i);
				if (!checkCallBarrier(state, params, source, i)) {
					// Don't confuse the call tracking by calling 'beforeCall' if we only track memory.
					if (!onlyMemory)
						generateNotifyNewCall(state.program, params, i);
				}
			}
		} else {
			checkMemAccess(params, instr);
		}

		dest << instr;

		if (instr.op == OpCode:location) {
			if (!onlyMemory)
				generateCall(state.program, params, instr.src.srcPos, i);
		} else if (b = barrier(instr)) {
			generateBarrier(state.program, params, b.pos, b.type, source, i);
		} else if (l = leakable(instr)) {
			generateLeakable(state.program, params, l.alloc);
		} else if (instr.op == OpCode:prolog) {
			params.block = source.root;
			if (onlyMemory)
				generateInit(state.program, params, fn);
			else
				generateCallTracking(state.program, params, fn);
		} else if (instr.op == OpCode:beginBlock) {
			params.block = instr.src.block;
		} else if (instr.op == OpCode:endBlock) {
			params.block = source.parent(instr.src.block);
		} else if (instr.op == OpCode:activate) {
			params.inactive.remove(instr.src.var.key);
		} else if (instr.op == OpCode:fnCall) {
			// In case of function calls, the access operations must be after the call is finished.
			checkMemAccess(params, instr);
		} else if (instr.op == OpCode:fnCallRef) {
			params.saveRegs();
			params.recordWriteRef(instr.dest);
			params.restoreRegs();
		}

	}

	dest << source.labels(source.count);

	// print("Patched ${fn.name}: ${dest}");
	dest;
}

// Is the last one a function parameter?
private Bool lastFnParam(Listing l, Nat pos) on Compiler {
	if (pos == 0)
		return false;
	Instr i = l[pos - 1];
	i.op == OpCode:fnParam | i.op == OpCode:fnParamRef;
}

// Find a barrier in an instruction.
private SrcBarrier? barrier(Instr i) on Compiler {
	if (i.op == OpCode:meta)
		if (barrier = i.src.obj as SrcBarrier)
			return barrier;
	return null;
}

// Find a leakable allocation in an instruction.
private LeakableAlloc? leakable(Instr i) on Compiler {
	if (i.op == OpCode:meta)
		if (leakable = i.src.obj as LeakableAlloc)
			return leakable;
	return null;
}

// Find the function of a fnCall instruction.
private Function? calledFunction(Instr i) on Compiler {
	if (src = i.src.ref.source as NamedSource) {
		if (fn = src.named as Function) {
			return fn;
		}
	}
	return null;
}

// Replace references in an instruction. Since we re-load packages, we might have references into
// the temporary instances of a function for example. This function replaces these with their
// original corresponding reference.
private Instr replaceRefs(PatchState s, Instr i) on Compiler {
	Operand src = replaceRef(s, i.src);
	Operand dst = replaceRef(s, i.dest);
	i.alter(dst, src);
}

// Alter a single operand, as above.
private Operand replaceRef(PatchState s, Operand op) on Compiler {
	if (op.type == OpType:reference) {
		return Operand(s.replaceRef(op.ref));
	} else if (op.type == OpType:objReference) {
		if (n = op.tObj as Named)
			return objPtr(s.replaceNamed(n));
	}

	op;
}

// Patch a call operation if needed.
// We might need to call an alternate version of the function, if we need to add instrumentation to it.
private Instr patchCall(PatchState state, Instr src) on Compiler {
	unless (fn = calledFunction(src))
		return src;

	// Anything inside 'pkg' does not need to be altered. We will patch all of those functions anyway.
	if (fn.hasParent(state.pkg))
		return src;

	// See if it needs to be patched.
	if (!state.needsPatch(fn))
		return src;

	// We need to patch it, ask the state object to do that for us.
	src.alterSrc(state.patchFn(fn));
}


// Insert a barrier before all parameters to a function call if necessary. Returns 'true' if this
// call was captured.
private Bool checkCallBarrier(PatchState state, PatchParams params, Listing source, Nat start) on Compiler {
	Nat i = start;
	while (i < source.count) {
		Instr instr = source[i];
		if (instr.op == OpCode:fnParam | instr.op == OpCode:fnParamRef) {
			// Continue.
		} else if (instr.op == OpCode:fnCall | instr.op == OpCode:fnCallRef) {
			// The call itself. Check if we need a barrier!
			if (fn = calledFunction(instr)) {
				return addCallBarrier(state, params, fn, source, start);
			}

			// We're done!
			break;
		} else {
			// Something is wrong, bail.
			break;
		}

		i++;
	}
	return false;
}

private Bool addCallBarrier(PatchState state, PatchParams params, Function fn, Listing src, Nat parId) on Compiler {
	// Don't insert barriers for functions where all code is visible to us.
	if (fn.hasParent(state.pkg))
		return false;

	var barrier = params.codeHints.functionBarrier(fn);
	return generateBarrier(state.program, params, SrcPos(), barrier, src, parId);
}

// Generate code that tracks reads that happen during fnCall instructions.
private void checkParamAccess(PatchParams params, Listing source, Nat i) on Compiler {
	Bool saved = false;
	while (i < source.count) {
		Instr instr = source[i];
		if (instr.op == OpCode:fnParam) {
			if (checkMemAccess(instr.src)) {
				if (!saved)
					params.saveRegs();
				saved = true;

				params.recordRead(instr.src);
				params.restoreRegs();
			}
		} else if (instr.op == OpCode:fnParamRef) {
			if (!saved)
				params.saveRegs();
			saved = true;

			params.recordReadRef(instr.src);
			params.restoreRegs();
		} else {
			break;
		}

		i++;
	}
}

// Generate code that tracks any memory accesses made by the instruction.
private void checkMemAccess(PatchParams params, Instr instr) on Compiler {
	Bool saved = false;
	if (checkMemAccess(instr.src)) {
		if (!saved)
			params.saveRegs();
		saved = true;

		params.recordRead(instr.src);
		params.restoreRegs();
	}

	if (checkMemAccess(instr.dest)) {
		if (instr.mode.has(DestMode:read)) {
			if (!saved)
				params.saveRegs();
			saved = true;

			params.recordRead(instr.dest);
			params.restoreRegs();
		}
		if (instr.mode.has(DestMode:write)) {
			if (!saved)
				params.saveRegs();
			saved = true;

			params.recordWrite(instr.dest);
			params.restoreRegs();
		}
	}
}

// Check if this operand is a memory reference through a register.
private Bool checkMemAccess(Operand op) on Compiler {
	return op.type == OpType:relative;
}

// Generate the a call to the class to track execution, adding a copy of the return value.
private void generateReturnCall(Program program, PatchParams to, Function fn, Bool ref, Operand src) on Compiler {
	// Don't attempt to handle references.
	if (fn.result.ref)
		return;

	// Don't show the result from constructors or destructors.
	if (fn.name == "__init" | fn.name == "__destroy")
		return;

	// Don't add 'void'.
	unless (type = fn.result.type)
		return;

	to.saveRegs();
	Listing l = to.to;
	Block subBlock = l.createBlock(to.block);

	l << begin(subBlock);

	Var array = saveVariables(to, subBlock);

	// Create a 'stackVar' container for the result.
	Var stackVar = l.createVar(subBlock, sPtr);
	l << fnParam(ptrDesc, objPtr("↲"));
	l << fnCall(named{createStackVar<Str>}.ref, false, ptrDesc, stackVar);

	Var dest = l.createVar(subBlock, sPtr);
	if (fn.result.isValue())
		generateReturnSaveVal(l, type, ref, src, dest);
	else
		generateReturnSaveClass(l, type, ref, src, dest);

	l << mov(ptrB, stackVar);
	l << mov(ptrRel(ptrB, named{StackVar:value<StackVar>}.offset), dest);

	// Add it to the array.
	l << fnParam(ptrDesc, array);
	l << fnParam(ptrDesc, stackVar);
	l << fnCall(named{Array<StackVar>:push<StackVar[], StackVar>}.ref, true);

	// Call the tracking.
	l << fnParam(ptrDesc, objPtr(program));
	l << fnParam(ptrDesc, array);
	l << fnCall(named{Program:functionReturn<Program, StackVar[]>}.ref, true);

	l << end(subBlock);
	to.restoreRegs();
}

private void generateReturnSaveVal(Listing l, Type type, Bool ref, Operand src, Operand dest) on Compiler {
	// We will make a memcpy of the variable that we don't destroy in order to not confuse constructors/destructors.

	// Allocate memory and save the variable.
	l << fnParam(ptrDesc, type.typeRef);
	l << fnParam(ptrDesc, ptrConst(1));
	l << fnCall(ref(BuiltIn:allocArray), false, ptrDesc, ptrA);
	l << mov(dest, ptrA);

	// Copy the value.
	var start = l.label();
	l << add(ptrA, ptrConst(sPtr * 2));
	if (ref)
		l << mov(ptrB, src);
	else
		l << lea(ptrB, src);
	l << mov(ptrC, ptrConst(0));
	l << start;
	// Copying whole pointers is OK, heap allocation sizes are always word-aligned anyway, and
	// we just created the allocation we're copying to.
	l << mov(ptrRel(ptrA), ptrRel(ptrB));
	l << add(ptrA, ptrConst(sPtr));
	l << add(ptrB, ptrConst(sPtr));
	l << add(ptrC, ptrConst(sPtr));
	l << cmp(ptrC, ptrConst(type.size));
	l << jmp(start, CondFlag:ifBelow);
}

private void generateReturnSaveClass(Listing l, Type type, Bool ref, Operand src, Operand dest) on Compiler {
	// It is a pointer, we can just store that inside a Variant without any issues.
	if (ref) {
		l << mov(ptrA, src);
		l << mov(dest, ptrRel(ptrA));
	} else {
		l << mov(dest, src);
	}
}

// Generate a call to this class in order to keep track of the execution.
private void generateCall(Program program, PatchParams to, SrcPos pos, Nat id) on Compiler {
	var fn = named{Program:newLocation<Program, SrcPosWrap, StackVar[], Nat>};

	to.saveRegs();
	Listing l = to.to;

	Block subBlock = l.createBlock(to.block);

	l << begin(subBlock);

	Var array = saveVariables(to, subBlock);

	l << fnParam(ptrDesc, objPtr(program));
	l << fnParam(ptrDesc, objPtr(SrcPosWrap(pos)));
	l << fnParam(ptrDesc, array);
	l << fnParam(intDesc, natConst(id));
	l << fnCall(fn.ref, true);

	l << end(subBlock);
	to.restoreRegs();
}

// Generate a call to track barriers.
private Bool generateBarrier(Program program, PatchParams to, SrcPos pos, Barrier type, Listing src, Nat id) on Compiler {
	if (type == Barrier:none)
		return false;
	if (type & Barrier:showCall)
		return generateFnBarrier(program, to, pos, type, src, id);

	var fn = named{Program:newBarrier<Program, SrcPosWrap, Barrier, Nat>};

	to.saveRegs();
	Listing l = to.to;

	l << fnParam(ptrDesc, objPtr(program));
	l << fnParam(ptrDesc, objPtr(SrcPosWrap(pos)));
	l << fnParam(intDesc, natConst(type.v));
	l << fnParam(intDesc, natConst(id));
	l << fnCall(fn.ref, true);

	to.restoreRegs();

	return true;
}

// Like below, but figures out the call-site and the function first.
private Bool generateFnBarrier(Program program, PatchParams to, SrcPos pos, Barrier type, Listing src, Nat id) on Compiler {
	Nat firstParam = 0;
	for (Nat i = id; i < src.count; i++) {
		Instr instr = src[i];
		if (instr.op == OpCode:fnParam | instr.op == OpCode:fnParamRef) {
			if (firstParam == 0)
				firstParam = i;
		} else if (instr.op == OpCode:fnCall | instr.op == OpCode:fnCallRef) {
			if (fn = calledFunction(instr)) {
				return generateFnBarrier(program, to, pos, type, fn, src, firstParam);
			} else {
				return false;
			}
		}
	}
	return false;
}

// Generate a call to track function barriers, where we should show the call as a separate stack frame.
private Bool generateFnBarrier(Program program, PatchParams to, SrcPos pos,	Barrier type, Function fn,
							Listing src, Nat paramStart) on Compiler {
	if (type == Barrier:none)
		return false;

	var barrierFn = named{Program:newFnBarrier<Program, SrcPosWrap, Str, Barrier, StackVar[], Nat>};

	to.saveRegs();
	Listing l = to.to;

	Block sub = l.createBlock(to.block);
	l << begin(sub);

	Var params = l.createVar(sub, sPtr);
	Type arrayType = named{StackVar[]};
	l << fnParam(ptrDesc, arrayType.typeRef);
	l << fnCall(ref(BuiltIn:alloc), false, ptrDesc, params);
	if (ctor = arrayType.defaultCtor) {
		l << fnParam(ptrDesc, params);
		l << fnCall(ctor.ref, true);
	}

	Var tmpVariant = l.createVar(sub, named{Variant}.size);
	for (i, type in fn.params) {
		Str name;
		if (nDoc = fn.documentation) {
			var doc = nDoc.get;
			if (i < doc.params.count) {
				name = doc.params[i].name;
			}
		}
		if (name.empty)
			name = (i + 1).toS;

		// Store the parameter in 'tmpVariant'.
		Type variant = named{Variant};
		SimplePart ctorName("__init", [Value(variant, true), type]);
		unless (ctor = variant.find(ctorName, Scope()) as Function)
			continue;

		Instr instr = src[paramStart + i];
		to.restoreRegs(); // Would be nice to not restore all of them...
		if (instr.op == OpCode:fnParamRef) {
			l << mov(ptrB, instr.src);
		} else if (instr.op == OpCode:fnParam) {
			l << lea(ptrB, instr.src);
		} else {
			continue;
		}
		l << lea(ptrA, tmpVariant);
		l << fnParam(ptrDesc, ptrA);
		l << fnParam(ptrDesc, ptrB);
		l << fnCall(ctor.ref(), true);

		// Create a StackVar element.
		l << fnParam(ptrDesc, objPtr(name));
		l << fnCall(named{createStackVar<Str>}.ref, false, ptrDesc, ptrA);

		// Set the pointers.
		var offset = named{StackVar:value<StackVar>}.offset;
		var offset2 = named{StackVar:destroy<StackVar>}.offset;
		l << mov(ptrRel(ptrA, offset), tmpVariant);
		l << mov(ptrRel(ptrA, offset2), tmpVariant);

		// Push to the array.
		Function push = named{Array<StackVar>:push<StackVar[], StackVar>};
		l << fnParam(ptrDesc, params);
		l << fnParam(ptrDesc, ptrA);
		l << fnCall(push.ref, true);
	}

	Str fnName = to.codeHints.cleanName(fn, to.pkg);

	l << fnParam(ptrDesc, objPtr(program));
	l << fnParam(ptrDesc, objPtr(SrcPosWrap(pos)));
	l << fnParam(ptrDesc, objPtr(fnName));
	l << fnParam(intDesc, natConst(type.v));
	l << fnParam(ptrDesc, params);
	l << fnParam(intDesc, natConst(paramStart));
	l << fnCall(barrierFn.ref, true);

	l << end(sub);
	to.restoreRegs();

	return true;
}

// Generate a call to track leakable allocations.
private void generateLeakable(Program program, PatchParams to, Operand leakable) on Compiler {
	Listing l = to.to;
	l << fnParam(ptrDesc, objPtr(program));
	l << fnParam(ptrDesc, leakable);
	l << fnCall(named{Program:leakableAllocation<Program, unsafe:RawPtr>}.ref(), true);
}

// Generate a call to notify about that we're about to perform a function call.
private void generateNotifyNewCall(Program program, PatchParams to, Nat offset) on Compiler {
	var fn = named{Program:beforeCall<Program, Nat>};
	Listing l = to.to;
	to.saveRegs();
	l << fnParam(ptrDesc, objPtr(program));
	l << fnParam(intDesc, natConst(offset));
	l << fnCall(fn.ref, true);
	to.restoreRegs();
}

// Save all variables to a data structure in the current block.
private Var saveVariables(PatchParams to, Block current) on Compiler {
	Listing l = to.to;

	Var array = l.createVar(current, sPtr);
	Var variant = l.createVar(current, named{Variant}.size);
	Type arrayType = named{StackVar[]};
	l << fnParam(ptrDesc, named{StackVar[]}.typeRef);
	l << fnCall(ref(BuiltIn:alloc), false, ptrDesc, array);

	if (ctor = arrayType.defaultCtor) {
		l << fnParam(ptrDesc, array);
		l << fnCall(ctor.ref, true);
	}

	saveVariables(to, to.block, array, variant);

	array;
}

// Save all variables to a data structure.
private void saveVariables(PatchParams to, Block block, Var array, Var variant) on Compiler {
	Block parent = to.to.parent(block);
	if (parent != Block()) {
		saveVariables(to, parent, array, variant);
	}

	saveVariables(to, to.to.allVars(block), array, variant);
}

private void saveVariables(PatchParams to, Var[] vars, Var array, Var variant) on Compiler {
	Listing l = to.to;

	for (var in vars) {
		if (info = to.to.varInfo(var)) {
			// Don't output variables that are not yet activated.
			if (!to.inactive.has(var.key)) {
				// Ask if and how to save this variable.
				var save = to.codeHints.saveVariable(l, var, info, variant);
				if (save != CodeHints:Save:none) {
					// Create a StackVar element.
					l << fnParam(ptrDesc, objPtr(info.name));
					l << fnCall(named{createStackVar<Str>}.ref, false, ptrDesc, ptrA);

					// Set the pointer.
					var offset = named{StackVar:value<StackVar>}.offset;
					l << mov(ptrRel(ptrA, offset), variant);

					if (save == CodeHints:Save:copy) {
						// If we need destruction, set the variant as well. We know that it is currently
						// empty, so we don't have to bother destroying it. The one saved in 'variant'
						// is moved, so we don't have to bother with that either.
						offset = named{StackVar:destroy<StackVar>}.offset;
						l << mov(ptrRel(ptrA, offset), variant);
					}

					// Push it to the array!
					Function push = named{Array<StackVar>:push<StackVar[], StackVar>};
					l << fnParam(ptrDesc, array);
					l << fnParam(ptrDesc, ptrA);
					l << fnCall(push.ref, true);
				}
			}
		}
	}
}

// Create a StackVar instance. Called from ASM.
private StackVar createStackVar(Str name) {
	StackVar(name);
}

// Generate the call to 'functionEntered' and make sure 'functionExited' is called on function exit (last).
private void generateCallTracking(Program program, PatchParams to, Function fn) on Compiler {
	var enterFn = named{Program:functionEntered<Program, Str, SrcPosWrap, progvis:data:ViewHints, StackVar[]>};
	// TODO: It is not always safe to do this... The destructor is expected to be a free function,
	// but in almost all cases, it does not matter.
	var exitFn = named{Program:functionExited<Program>};

	// Find a clean function name.
	var fnName = to.codeHints.cleanName(fn, to.pkg);

	Listing l = to.to;

	Var v = l.createVar(l.root, sPtr, exitFn.ref);
	l.moveFirst(v);
	l << mov(v, objPtr(program));

	Block subBlock = l.createBlock(l.root);
	l << begin(subBlock);
	Var array = saveVariables(to, subBlock);

	l << fnParam(ptrDesc, objPtr(program));
	l << fnParam(ptrDesc, objPtr(fnName));
	l << fnParam(ptrDesc, objPtr(SrcPosWrap(fn.pos)));
	l << fnParam(ptrDesc, objPtr(to.viewHints));
	l << fnParam(ptrDesc, array);
	l << fnCall(enterFn.ref, true, ptrDesc, to.memTracker);

	l << end(subBlock);
}

// Generate a simpler version of call tracking that only initializes things needed for the memory tracking.
private void generateInit(Program program, PatchParams to, Function fn) on Compiler {
	var enterFn = named{Program:anonFunctionEntered<Program>};
	// TODO: It is not always safe to do this... The destructor is expected to be a free function,
	// but in almost all cases, it does not matter.
	var exitFn = named{Program:anonFunctionExited<Program>};

	Listing l = to.to;

	Var v = l.createVar(l.root, sPtr, exitFn.ref);
	l.moveFirst(v);
	l << mov(v, objPtr(program));

	l << fnParam(ptrDesc, objPtr(program));
	l << fnCall(enterFn.ref, true, ptrDesc, to.memTracker);
}

// Check if the listing contains any location information at all.
private Bool anyLocation(Listing l) on Compiler {
	for (Nat i = 0; i < l.count; i++) {
		if (l[i].op == OpCode:location)
			if (l[i].src.srcPos != SrcPos())
				return true;
	}
	return false;
}