Write forward declarations for all types and functions for mutual and/or nested recursion.

git-svn-id: http://svn.drobilla.net/resp/trunk@440 ad02d1e2-f140-0410-9f75-f8b11f17cedd

7 files changed, 89 insertions, 16 deletions

diff --git a/src/c.cpp b/src/c.cpp
index b2d17d1..934100c 100644
--- a/src/c.cpp
+++ b/src/c.cpp
@@ -41,6 +41,7 @@ struct CEngine : public Engine {
 	{
 	}
 
+	CFunc compileProt(CEnv& cenv, const string& name, const ATuple* args, const ATuple* type);
 	CFunc startFn(CEnv& cenv, const string& name, const ATuple* args, const ATuple* type);
 	void  finishFn(CEnv& cenv, CFunc f, CVal ret, const AST* retT);
 	void  eraseFn(CEnv& cenv, CFunc f);
@@ -175,6 +176,12 @@ CEngine::compileType(CEnv& cenv, const std::string& name, const AST* expr)
 }
 
 CFunc
+CEngine::compileProt(CEnv& cenv, const std::string& name, const ATuple* args, const ATuple* type)
+{
+	return NULL;
+}
+
+CFunc
 CEngine::startFn(CEnv& cenv, const std::string& name, const ATuple* args, const ATuple* type)
 {
 	const ATuple* argsT = type->prot();
diff --git a/src/compile.cpp b/src/compile.cpp
index 917944a..64dee08 100644
--- a/src/compile.cpp
+++ b/src/compile.cpp
@@ -111,8 +111,12 @@ compile_def_type(CEnv& cenv, const ATuple* def) throw()
 {
 	const ASymbol* name = def->frst()->to_symbol();
 	if (name) {
-		cenv.engine()->compileType(cenv, name->str(), def->frrst());
-		cenv.tenv.def(name, def->frrst());
+		if (def->rrst()) {  // Definition
+			cenv.engine()->compileType(cenv, name->str(), def->frrst());
+			cenv.tenv.def(name, def->frrst());
+		} else {  // Forward declaration
+			cenv.engine()->compileType(cenv, name->str(), NULL);
+		}
 	} else {
 		name = def->frst()->as_tuple()->fst()->as_symbol();
 		cenv.engine()->compileType(cenv, name->str(), def->frst());
@@ -154,7 +158,19 @@ compile_call(CEnv& cenv, const ATuple* call) throw()
 		}
 	}
 
-	return cenv.engine()->compileCall(cenv, f, cenv.type(call->fst())->as_tuple(), args);
+	return cenv.engine()->compileCall(cenv, f, cenv.type(call->frst())->as_tuple(), args);
+}
+
+static CVal
+compile_prot(CEnv& cenv, const ATuple* call) throw()
+{
+	const ASymbol* name = call->list_ref(1)->as_symbol();
+	const ATuple*  type = cenv.type(name)->as_tuple();
+	const ATuple*  args = call->frrst()->as_tuple()->frst()->as_tuple();
+
+	cenv.engine()->compileProt(cenv, name->sym(), args, type);
+
+	return NULL;
 }
 
 static CVal
@@ -220,6 +236,8 @@ resp_compile(CEnv& cenv, const AST* ast) throw()
 			return compile_def_type(cenv, call);
 		else if (form == "quote")
 			return compile_quote(cenv, call);
+		else if (form == "prot")
+			return compile_prot(cenv, call);
 		else if (form == "fn-start")
 			return compile_fn_start(cenv, call);
 		else if (form == "fn-end")
diff --git a/src/flatten.cpp b/src/flatten.cpp
index 8d92ff9..424e5a6 100644
--- a/src/flatten.cpp
+++ b/src/flatten.cpp
@@ -65,6 +65,10 @@ static const AST*
 flatten_def_type(CEnv& cenv, Code& code, const ATuple* def) throw()
 {
 	const ASymbol* name = def->frst()->to_symbol();
+	if (!def->rrst()) {  // Forward declaration
+		code.push_back(def);
+		return NULL;
+	}
 	if (name) {
 		cenv.tenv.def(name, def->frrst());
 	} else {
diff --git a/src/lift.cpp b/src/lift.cpp
index 802130d..c6bcee9 100644
--- a/src/lift.cpp
+++ b/src/lift.cpp
@@ -82,7 +82,7 @@ lift_def(CEnv& cenv, Code& code, const ATuple* def) throw()
 	assert(def->list_ref(1)->to_symbol());
 	List copy;
 	copy.push_back(def->fst());
-	copy.push_back(resp_lift(cenv, code, def->list_ref(1)));
+	copy.push_back(sym);
 	for (ATuple::const_iterator t = def->iter_at(2); t != def->end(); ++t)
 		copy.push_back(resp_lift(cenv, code, *t));
 
@@ -135,6 +135,14 @@ lift_fn(CEnv& cenv, Code& code, const ATuple* fn) throw()
 		implProtT.push_back(paramType);
 	}
 
+	// Write function prototype first for mutual and/or nested recursion
+	List declProt(fn->loc, cenv.penv.sym("fn"), 0);
+	declProt.push_back(implProt);
+	List decl(fn->loc, cenv.penv.sym("prot"), cenv.penv.sym(implNameStr), 0);
+	decl.push_back(declProt);
+	code.push_back(decl);
+	cenv.setType(decl, cenv.penv.sym("Nothing"));
+
 	impl.push_back(implProt);
 
 	// Lift body
@@ -159,13 +167,13 @@ lift_fn(CEnv& cenv, Code& code, const ATuple* fn) throw()
 	List consT;
 	List cons(fn->loc, cenv.penv.sym("Closure"), implName, NULL);
 
-	const CEnv::FreeVars& freeVars = cenv.liftStack.top();
+	const CEnv::FreeVars freeVars = cenv.liftStack.top();
+	cenv.liftStack.pop();
 	for (CEnv::FreeVars::const_iterator i = freeVars.begin(); i != freeVars.end(); ++i) {
-		cons.push_back(*i);
+		cons.push_back(resp_lift(cenv, code, *i));
 		tupT.push_back(cenv.type(*i));
 		consT.push_back(cenv.type(*i));
 	}
-	cenv.liftStack.pop();
 
 	// Prepend closure parameter type
 	implProtT.push_front(tsym);
@@ -183,6 +191,9 @@ lift_fn(CEnv& cenv, Code& code, const ATuple* fn) throw()
 	code.push_back(tdef);
 	cenv.tenv.def(tsym, consT);
 
+	List tdecl(Cursor(), cenv.penv.sym("def-type"), tsym, 0);
+	code.push_front(tdecl);
+
 	code.push_back(def);
 
 	// Set type of closure to type symbol
@@ -192,7 +203,6 @@ lift_fn(CEnv& cenv, Code& code, const ATuple* fn) throw()
 	if (cenv.name(fn) != "")
 		cenv.def(cenv.penv.sym(cenv.name(fn)), fn, consT, NULL);
 
-
 	return cons;
 }
 
diff --git a/src/llvm.cpp b/src/llvm.cpp
index 795cd8c..93bf066 100644
--- a/src/llvm.cpp
+++ b/src/llvm.cpp
@@ -82,6 +82,7 @@ struct LLVMEngine : public Engine {
 	LLVMEngine();
 	virtual ~LLVMEngine();
 
+	CFunc compileProt(CEnv& cenv, const string& name, const ATuple* args, const ATuple* type);
 	CFunc startFn(CEnv& cenv, const string& name, const ATuple* args, const ATuple* type);
 	void  finishFn(CEnv& cenv, CVal ret, const AST* retT);
 	CFunc getFn(CEnv& cenv, const std::string& name);
@@ -229,10 +230,9 @@ LLVMEngine::llType(const AST* t, const char* name)
 	}
 
 	// Struct type
-	Type*         ret = NULL;
+	StructType*   ret = NULL;
 	vector<Type*> ctypes;
 
-	
 	if (!name) {
 		const ASymbol* tag = t->as_tuple()->fst()->as_symbol();
 		if (tag->str() != "Tup" && tag->str() != "Closure") {
@@ -243,14 +243,18 @@ LLVMEngine::llType(const AST* t, const char* name)
 	if (name) {
 		CTypes::const_iterator i = compiledTypes.find(name);
 		if (i != compiledTypes.end()) {
-			return i->second;
+			ret = (StructType*)((PointerType*)i->second)->getContainedType(0);
 		}
 	}
 
+	if (ret && !ret->isOpaque()) {
+		return PointerType::getUnqual(ret);
+	}
+
 	// Define opaque type to stand for name in recursive type body
 	if (name) {
 		THROW_IF(opaqueT, t->loc, "Nested recursive types");
-		opaqueT    = StructType::create(context, name);
+		opaqueT    = (ret) ? ret : StructType::create(context, name);
 		opaqueName = name;
 	}
 
@@ -383,11 +387,16 @@ LLVMEngine::compileType(CEnv& cenv, const std::string& name, const AST* expr)
 	if (!name.empty()) {
 		CTypes::const_iterator i = compiledTypes.find(name);
 		if (i != compiledTypes.end()) {
-			return i->second;
+			if (!i->second->isPointerTy() ||
+			    !((StructType*)(((PointerType*)i->second)->getContainedType(0)))->isOpaque()) {
+				return i->second;
+			}
 		}
 	}
 
-	Type* const type = llType(expr, name.c_str());
+	Type* const type = (expr)
+		? llType(expr, name.c_str())  // Definition
+		: PointerType::getUnqual(StructType::create(context, name));  // Forward declaration
 
 	if (!name.empty())
 		compiledTypes.insert(make_pair(name, type));
@@ -396,7 +405,7 @@ LLVMEngine::compileType(CEnv& cenv, const std::string& name, const AST* expr)
 }
 
 CFunc
-LLVMEngine::startFn(
+LLVMEngine::compileProt(
 	CEnv& cenv, const std::string& name, const ATuple* args, const ATuple* type)
 {
 	const ATuple* argsT = type->prot();
@@ -431,6 +440,24 @@ LLVMEngine::startFn(
 			a->setName((*i)->as_symbol()->sym());
 	}
 
+	// Define function in the environment so any calls that get compiled before
+	// the definition will resolve correctly (e.g. parent calls from a child fn)
+	cenv.def(cenv.penv.sym(name), NULL, type, f);
+
+	return f;
+}
+
+CFunc
+LLVMEngine::startFn(
+	CEnv& cenv, const std::string& name, const ATuple* args, const ATuple* type)
+{
+	// Use forward declaration if it exists
+	Function* f = module->getFunction(name);
+	if (!f) {
+		f = (Function*)compileProt(cenv, name, args, type);
+	}
+
+	// Start the function body
 	BasicBlock* bb = BasicBlock::Create(context, "entry", f);
 	builder.SetInsertPoint(bb);
 
diff --git a/src/repl.cpp b/src/repl.cpp
index d4eed09..25da08a 100644
--- a/src/repl.cpp
+++ b/src/repl.cpp
@@ -103,7 +103,7 @@ compile(CEnv& cenv, const Code& parsed, Code& defs, bool& hasMain, const char* m
 	const Pass passes[] = {
 		{ resp_simplify, "-R" },
 		{ resp_lift, "-L" },
-		{ resp_depoly, "-D" },
+		//{ resp_depoly, "-D" },
 		{ NULL, NULL }
 	};
 
@@ -136,6 +136,8 @@ compile(CEnv& cenv, const Code& parsed, Code& defs, bool& hasMain, const char* m
 		if (call && (is_form(*i, "def-type")
 		             || (is_form(*i, "def") && is_form(call->frrst(), "fn")))) {
 			resp_flatten(cenv, defs, call);
+		} else if (call && is_form(*i, "prot")) {
+			defs.push_back(*i);
 		} else {
 			const ATuple* tup = (*i)->to_tuple();
 			if (!tup || !tup->empty()) {
diff --git a/src/resp.hpp b/src/resp.hpp
index d56b5ae..494241b 100644
--- a/src/resp.hpp
+++ b/src/resp.hpp
@@ -679,6 +679,11 @@ struct Engine {
 
 	typedef const vector<CVal> CVals;
 
+	virtual CFunc compileProt(CEnv&              cenv,
+	                          const std::string& name,
+	                          const ATuple*      args,
+	                          const ATuple*      type) = 0;
+
 	virtual CFunc startFn(CEnv&              cenv,
 	                      const std::string& name,
 	                      const ATuple*      args,