shithub: mc

Download patch

ref: c05e4d021a24645c06092dda39c6befdf77ec813
parent: 97f03b720b5d8656a316ce1ca14b89d4a411c59f
author: Ori Bernstein <[email protected]>
date: Fri Apr 17 07:43:11 EDT 2015 

Topologically sort targets.

    This avoids tons of ugly, spurious chdir calls, as well as
    detecting cycles in library dependencies.


--- a/mbld/bld.sub
+++ b/mbld/bld.sub
@@ -10,7 +10,6 @@
 	main.myr
 	opts.myr
 	parse.myr
-	subdir.myr
 	test.myr
         types.myr
 	util.myr
--- a/mbld/build.myr
+++ b/mbld/build.myr
@@ -17,6 +17,10 @@
 
 const buildall = {b
 	for tn in b.all
+		if std.hthas(b.built, tn)
+			continue
+		;;
+		std.htput(b.built, tn, true)
 		match gettarg(b.targs, tn)
 		| `Bin bt:	buildbin(b, bt, false)
 		| `Lib lt:	buildlib(b, lt)
@@ -54,12 +58,8 @@
 const buildbin = {b, targ, addsrc
 	var dg, src
 
-	if targ.built
-		->
-	;;
-	pushdir(b, targ.dir)
+	setdir(b, targ.dir)
 	addincludes(b, targ)
-	buildlibdeps(b, targ)
 	std.put("%s...\n", targ.name)
 	if !myrdeps(b, targ, false, false, addsrc, &dg)
 		std.fatal(1, "Could not load dependencies for %s\n", targ.name)
@@ -72,8 +72,6 @@
 		linkbin(&dg, targ.name, src, targ.ldscript, targ.runtime, targ.incpath, targ.libdeps)
 		std.slfree(src)
 	;;
-	targ.built = true
-	popdir(b)
 }
 
 const buildlib = {b, targ
@@ -82,12 +80,8 @@
 	var dg
 	var lib, src
 
-	if targ.built
-		->
-	;;
-	pushdir(b, targ.dir)
+	setdir(b, targ.dir)
 	addincludes(b, targ)
-	buildlibdeps(b, targ)
 	lib = targ.name
 	std.put("lib%s.a...\n", lib)
 	archive = std.fmt("lib%s.a", lib)
@@ -106,12 +100,10 @@
 		std.slfree(src)
 	;;
 	std.slfree(archive)
-	targ.built = true
-	popdir(b)
 }
 
 const genfiles = {b, gt
-	pushdir(b, gt.dir)
+	setdir(b, gt.dir)
 	for f in gt.out
 		if !std.fexists(f)
 			run(gt.cmd)
@@ -118,7 +110,6 @@
 			break
 		;;
 	;;
-	popdir(b)
 }
 
 const addincludes = {b, targ
@@ -126,12 +117,6 @@
 		if !hasinc(targ.incpath, inc)
 			targ.incpath = std.slpush(targ.incpath, inc)
 		;;
-	;;
-}
-
-const buildlibdeps = {b, targ
-	for (inc, lib, subtarg) in targ.libdeps
-		build(b, subtarg)
 	;;
 }
 
--- a/mbld/clean.myr
+++ b/mbld/clean.myr
@@ -4,7 +4,6 @@
 use "deps.use"
 use "opts.use"
 use "parse.use"
-use "subdir.use"
 use "types.use"
 use "util.use"
 
@@ -70,7 +69,7 @@
 	we want to automatically add 'clean' sources since otherwise,
 	mbld won't be able to clean code after changing a build file.
 	*/
-	pushdir(b, targ.dir)
+	setdir(b, targ.dir)
 	if !myrdeps(b, targ, islib, true, true, &dg)
 		std.fatal(1, "Could not load dependencies for %s\n", targ.name)
 	;;
@@ -85,6 +84,5 @@
 			std.put("\tclean %s\n", k)
 		;;
 	;;
-	popdir(b)
 }
 
--- a/mbld/install.myr
+++ b/mbld/install.myr
@@ -4,7 +4,6 @@
 use "deps.use"
 use "opts.use"
 use "parse.use"
-use "subdir.use"
 use "types.use"
 use "util.use"
 use "build.use"
@@ -52,7 +51,7 @@
 const movefile = {b, delete, dir, file, instdir, destdir, prefix, perm
 	var path
 
-	pushdir(b, dir)
+	setdir(b, dir)
 	path = std.pathjoin([destdir, instdir, prefix, file][:])
 	if delete
 		std.put("\tdelete %s\n", path)
@@ -72,7 +71,6 @@
 		;;
 	;;
 	std.slfree(path)
-	popdir(b)
 }
 
 const moveman = {b, delete, dir, man
--- a/mbld/main.myr
+++ b/mbld/main.myr
@@ -105,10 +105,11 @@
 	b = std.zalloc()
 	b.targs = std.mkht(std.strhash, std.streq)
 	b.gensrc = std.mkht(std.strhash, std.streq)
+	b.built = std.mkht(std.strhash, std.streq)
 	if !findbase(b, bldfile) || !std.chdir(b.basedir)
 		std.fatal(1, "could not find %s\n", bldfile)
 	;;
-	bld.pushdir(b, "")
+	bld.setdir(b, "")
 	-> b
 }
 
--- a/mbld/parse.myr
+++ b/mbld/parse.myr
@@ -23,10 +23,14 @@
 ;;
 
 const load = {b
-	-> loadall(b, b.bldfile, "")
+	var ok
+	ok = loadall(b, b.bldfile, "")
+	if ok
+		ok = sortdeps(b)
+	;;
+	-> ok
 }
 
-
 const loadall = {b, path, dir
 	var p : parser#
 	var subpath, subbld, subproj, ok
@@ -65,6 +69,50 @@
 	-> ok
 }
 
+const sortdeps = {b
+	var looped
+	var marked
+	var all
+
+	all = [][:]
+	looped = std.mkht(std.strhash, std.streq)
+	marked = std.mkht(std.strhash, std.streq)
+	for dep in b.all
+		match gettarg(b.targs, dep)
+		| `Bin _:	all = visit(all, b, dep, looped, marked)
+		| `Lib _:	all = visit(all, b, dep, looped, marked)
+		| targ:		all = std.slpush(all, dep)
+		;;
+	;;
+	std.slfree(b.all)
+	b.all = all
+	-> true
+}
+
+const visit = {all, b, targ, looped, marked
+	if std.hthas(looped, targ)
+		std.fatal(1, "cycle in build depgraph involving %s\n", targ)
+	elif std.hthas(marked, targ)
+		-> all
+	;;
+
+	std.htput(looped, targ, true)
+	for (dir, lib, dep) in getdeps(gettarg(b.targs, targ))
+		all = visit(all, b, dep, looped, marked)
+	;;
+	std.htdel(looped, targ)
+	std.htput(marked, targ, true)
+	-> std.slpush(all, targ)
+}
+
+const getdeps = {targ
+	match targ
+	| `Bin t:	-> t.libdeps
+	| `Lib t:	-> t.libdeps
+	| _:	std.fatal(1, "depending on non-library target")
+	;;
+}
+
 const mkparser = {path, dir, basedir
 	var p
 
@@ -306,7 +354,6 @@
 		.ldscript=ldscript,
 		.runtime=runtime,
 		.incpath=incpath,
-		.built=false
 	])
 }
 
--- a/mbld/subdir.myr
+++ /dev/null
@@ -1,23 +1,0 @@
-use std
-
-use "types.use"
-use "util.use"
-
-pkg bld =
-	const subdirs	: (p : build#, subs : byte[:][:], targ : std.option(byte[:]) -> void)
-;;
-
-const subdirs = {p, subs, targ
-	for s in subs
-		std.put("Entering directory '%s'\n", s)
-		if !std.chdir(s)
-			std.fatal(1, "unable to enter directory %s\n", s)
-		;;
-		run(p.cmd)
-		std.put("Leaving directory '%s'\n", s)
-		if !std.chdir("..")
-			std.fatal(1, "unable to leave directory %s\n", s)
-		;;
-	;;
-}
-
--- a/mbld/test.myr
+++ b/mbld/test.myr
@@ -7,7 +7,6 @@
 use "parse.use"
 use "types.use"
 use "util.use"
-use "subdir.use"
 
 use "config.use"
 
@@ -68,7 +67,7 @@
 	var tt, bin ,path, tests
 
 	tests = [][:]
-	pushdir(b, targ.dir)
+	setdir(b, targ.dir)
 	for s in targ.inputs
 		path = std.pathcat("./test", s)
 		if std.fexists(path)
@@ -80,7 +79,6 @@
 				.install = false,
 				.libdeps = targ.libdeps,
 				.incpath = targ.incpath,
-				.built = false,
 			]
 
 			cleantest(b, path)
@@ -98,7 +96,6 @@
 		std.slfree(t)
 	;;
 	std.slfree(tests)
-	popdir(b)
 	-> ok
 }
 
--- a/mbld/types.myr
+++ b/mbld/types.myr
@@ -2,14 +2,14 @@
 
 pkg bld =
 	type build = struct
-		cmd	: byte[:][:]	/* command that we ran */
 		/* build state */
 		basedir	: byte[:]
 		bldfile	: byte[:]
-		dirstk	: byte[:][:]
 		curdir	: byte[:]
+		built	: std.htab(byte[:], bool)#	/* set of targets built in this run */
+
 		/* build params */
-		all	: byte[:][:]
+		all	: byte[:][:]			/* all targets, in reverse topological order */
 		targs	: std.htab(byte[:], targ)#	/* dir => target mapping */
 		tdeps	: std.htab(byte[:], byte[:][:])	/* targname => depname[:] mapping */
 		gensrc	: std.htab(byte[:], gentarg#)#	/* generated src => generating target mapping */
@@ -30,8 +30,7 @@
 		dir	: byte[:]
 		name	: byte[:]
 		inputs	: byte[:][:]
-		libdeps	: (byte[:], byte[:], byte[:])[:]	/* dir, lib pairs */
-		built	: bool
+		libdeps	: (byte[:], byte[:], byte[:])[:]	/* dir, lib, targname */
 		install	: bool
 		runtime	: byte[:]
 		incpath	: byte[:][:]
--- a/mbld/util.myr
+++ b/mbld/util.myr
@@ -11,8 +11,7 @@
 	const srcswapsuffix	: (f : byte[:], newsuff : byte[:] -> byte[:])
 	const strlistfree	: (sl : byte[:][:] -> void)
 	const gettarg	: (tab : std.htab(byte[:], targ)#, n : byte[:] -> targ)
-	const pushdir	: (b : build#, dir : byte[:] -> void)
-	const popdir	: (b : build# -> void)
+	const setdir	: (b : build#, dir : byte[:] -> void)
 ;;
 
 const run = {cmd
@@ -102,16 +101,6 @@
 	| `std.None:	std.fatal(1, "internal: nonexistent %s\n", n)
 	| `std.Some t:	-> t
 	;;
-}
-
-const pushdir = {b, dir
-	b.dirstk = std.slpush(b.dirstk, dir)
-	setdir(b, dir)
-}
-
-const popdir = {b
-	b.dirstk = b.dirstk[:b.dirstk.len-1]
-	setdir(b, b.dirstk[b.dirstk.len-1])
 }
 
 const setdir = {b, dir