use fmt;
use strings;
use bufio;
use os;
use io;
use strconv;

// A node in the file system tree is either a dir or a file
type inode = (*dir | *file);
type dir = struct {
	name: str,
	parent: (*dir | void),
	children: []inode,
	sz: size,
};
type file = struct {
	name: str,
	sz: size,
};

fn freeinode(root: inode) void = {
	match (root) {
	case let f: *file =>
		free(f.name);
		free(f);
	case let d: *dir =>
		for (let i = 0z; i < len(d.children); i += 1)
			freeinode(d.children[i]);
		free(d.children);
		free(d.name);
		free(d);
	};
};

fn printinode(root: inode, indent: size) void = {
	for (let i = 0z; i < indent; i += 1)
		fmt::print(" ")!;
	match (root) {
	case let f: *file =>
		fmt::printfln("- {} ({})", f.name, f.sz)!;
	case let d: *dir =>
		fmt::printfln("{} ({} entr{})", d.name, len(d.children), if (len(d.children) == 1) "y" else "ies")!;
		for (let i = 0z; i < len(d.children); i += 1)
			printinode(d.children[i], indent + 1);
	};
};

// Do we have an entry with the given name?
fn finddir(d: *dir, name: str) (void | *dir) = {
	for (let i = 0z; i < len(d.children); i += 1) {
		match (d.children[i]) {
		case let d0: *dir =>
			if (d0.name == name)
				return d0;
		case => void;
		};
	};
};

fn dirsize(d: *dir, tally: *size) size = {
	let total = 0z;
	for (let i = 0z; i < len(d.children); i += 1) match (d.children[i]) {
	case let f: *file =>
		total += f.sz;
	case let d0: *dir =>
		total += dirsize(d0, tally);
	};
	if (total <= 100000)
		*tally += total;
	d.sz = total;
	return total;
};

// Find a candidate for deletion of at least threshold in size
//
// Returns void if none is found, otherwise the smallest candidate identified
// (recursively).
fn find_delcandidates(d: *dir, threshold: size, candidates: *[]*dir) void = {

	for (let i = 0z; i < len(d.children); i += 1) match (d.children[i]) {
	case let d0: *dir =>
		if (d0.sz >= threshold) {
			append(candidates, d0);
		};
		find_delcandidates(d0, threshold, candidates);
	case => void;
	};
	if (d.sz >= threshold) {
		append(candidates, d);
	};
};

export fn main() void = {
	let root: *dir = alloc(dir {
		name = strings::dup("/"),
		parent = void,
		children = [],
		sz = 0,
	});
	defer freeinode(root);

	let cwd = root;

	for (true) match (bufio::read_line(os::stdin)) {
	case let buf: []u8 =>
		defer free(buf);
		if (buf[0] == '$') {
			// running command
			let cmd = strings::fromutf8(buf[2..4])!;
			switch (cmd) {
			case "cd" =>
				// get destination dir
				let to = strings::fromutf8(buf[5..])!;
				if (to == "/" && root == cwd) {
					void;
				} else if (to == "..") {
					assert(cwd != root);
					cwd = cwd.parent as *dir;
				} else {
					// check if we already know the
					// subfolder
					let subfolder = match (finddir(cwd, to)) {
					case let d: *dir=> yield d;
					case void =>
						let subfolder = alloc(dir {
							name = strings::dup(to),
							parent = cwd,
							children = [],
							sz = 0,
						});
						append(cwd.children, subfolder);
						yield subfolder;
					};
					cwd = subfolder;
				};
			case "ls" => void;
			case => abort();
			};
		} else {
			// processing ls output
			let line = strings::fromutf8(buf)!;
			let (what, name) = strings::cut(line, " ");

			if (what == "dir") {
				if (finddir(cwd, name) is void) {
					let subfolder = alloc(dir {
						name = strings::dup(name),
						parent = cwd,
						children = [],
						sz = 0,
					});
					append(cwd.children, subfolder);
				};
			} else {
				let sz = strconv::stoz(what)!;
				let file = alloc(file {
					name = strings::dup(name),
					sz = sz,
				});

				append(cwd.children, file);
			};
		};
	case io::EOF =>
		break;
	case let err: io::error =>
		fmt::fatalf("error: {}", io::strerror(err));
	};

	printinode(root, 0);
	let tally = 0z;
	let rootsz = dirsize(root, &tally);
	fmt::printfln("total size of /: {}", rootsz)!;
	fmt::printfln("tally = {}", tally)!;

	// find smallest candidate that could be deleted to make room
	let unused = 70000000z - rootsz;
	let threshold = 30000000 - unused;
	fmt::printfln("unused space = {} (missing {})", unused, threshold)!;

	let candidates: []*dir = [];
	defer free(candidates);
	find_delcandidates(root, threshold, &candidates);
	fmt::printfln("found {} deletion candidates", len(candidates))!;
	let min = candidates[0];
	for (let i = 1z; i < len(candidates); i += 1) {
		let d = candidates[i];
		if (d.sz < min.sz)
			min = d;
		fmt::printfln("'{}' ({})", d.name, d.sz)!;
	};
	fmt::printfln("let's delete {} ({})", min.name, min.sz)!;
};