Rewrite dirtree so we don't need readdir, scandir, and fts.h. Rewrite ls (from scratch) to use new dirtree infrastructure. (This breaks everything else that currently uses dirtree.)

6 files changed, 449 insertions, 251 deletions

diff --git a/lib/dirtree.c b/lib/dirtree.c
index 1993d007..fb74f8d8 100644
--- a/lib/dirtree.c
+++ b/lib/dirtree.c
@@ -6,85 +6,150 @@
 
 #include "toys.h"
 
-// NOTE: This uses toybuf.  Possibly it shouldn't do that.
+// Create a dirtree node from a path, with stat and symlink info.
 
-// Create a dirtree node from a path.
+struct dirtree *dirtree_add_node(int dirfd, char *name)
+{
+	struct dirtree *dt = NULL;
+	struct stat st;
+	char buf[4096];
+	int len = 0, linklen = 0;
+
+	if (name) {
+		if (fstatat(dirfd, name, &st, AT_SYMLINK_NOFOLLOW)) goto error;
+		if (S_ISLNK(st.st_mode)) {
+			if (0>(linklen = readlinkat(dirfd, name, buf, 4095))) goto error;
+			buf[linklen++]=0;
+		}
+		len = strlen(name);
+	}
+   	dt = xzalloc((len = sizeof(struct dirtree)+len+1)+linklen);
+	if (name) {
+		memcpy(&(dt->st), &st, sizeof(struct stat));
+		strcpy(dt->name, name);
+
+		if (linklen) {
+			dt->symlink = memcpy(len+(char *)dt, buf, linklen);
+			dt->data = --linklen;
+		}
+	}
+
+	return dt;
+
+error:
+	perror_msg("%s",name);
+	free(dt);
+	return 0;
+}
 
-struct dirtree *dirtree_add_node(char *path)
+// Return path to this node.
+
+char *dirtree_path(struct dirtree *node, int *plen)
 {
-	struct dirtree *dt;
-	char *name;
+	char *path;
+	int len;
 
-	// Find last chunk of name.
+	if (!node || !node->name) return xmalloc(*plen);
 
-	for (;;) {
-		name = strrchr(path, '/');
+	len = (plen ? *plen : 0) + strlen(node->name)+1;
+	path = dirtree_path(node->parent, &len);
+	len = plen ? *plen : 0;
+	if (len) path[len++]='/';
+	strcpy(path+len, node->name);
 
-		if (!name) name = path;
-		else {
-			if (*(name+1)) name++;
-			else {
-				*name=0;
-				continue;
-			}
-		}
-		break;
-	}
+	return path;
+}
 
-   	dt = xzalloc(sizeof(struct dirtree)+strlen(name)+1);
-	if (lstat(path, &(dt->st))) {
-		error_msg("Skipped '%s'",name);
-		free(dt);
-		return 0;
-	}
-	strcpy(dt->name, name);
+// Default callback, filters out "." and "..".
 
-	return dt;
+int dirtree_isdotdot(struct dirtree *catch)
+{
+	// Should we skip "." and ".."?
+	if (catch->name[0]=='.' && (!catch->name[1] ||
+			(catch->name[1]=='.' && !catch->name[2])))
+				return DIRTREE_NOSAVE|DIRTREE_NORECURSE;
+
+	return 0;
 }
 
-// Given a directory (in a writeable PATH_MAX buffer), recursively read in a
-// directory tree.
+// Handle callback for a node in the tree. Returns saved node(s) or NULL.
 //
-// If callback==NULL, allocate tree of struct dirtree and
-// return root of tree.  Otherwise call callback(node) on each hit, free
+// By default, allocates a tree of struct dirtree, not following symlinks
+// If callback==NULL, or callback always returns 0, allocate tree of struct
+// dirtree and return root of tree.  Otherwise call callback(node) on each hit, free
 // structures after use, and return NULL.
+//
 
-struct dirtree *dirtree_read(char *path, struct dirtree *parent,
-					int (*callback)(char *path, struct dirtree *node))
+struct dirtree *handle_callback(struct dirtree *new,
+					int (*callback)(struct dirtree *node))
 {
-	struct dirtree *dtroot = NULL, *this, **ddt = &dtroot;
-	DIR *dir;
-	int len = strlen(path);
-
-	if (!(dir = opendir(path))) perror_msg("No %s", path);
-	else for (;;) {
-		int norecurse = 0;
-		struct dirent *entry = readdir(dir);
-		if (!entry) {
-			closedir(dir);
-			break;
-		}
+	int flags;
 
-		// Skip "." and ".."
-		if (entry->d_name[0]=='.') {
-			if (!entry->d_name[1]) continue;
-			if (entry->d_name[1]=='.' && !entry->d_name[2]) continue;
+	if (!callback) callback = dirtree_isdotdot;
+
+	flags = callback(new);
+	if (S_ISDIR(new->st.st_mode)) {
+		if (!(flags & DIRTREE_NORECURSE)) {
+			new->data = openat(new->data, new->name, 0);
+			dirtree_recurse(new, callback);
 		}
+		new->data = -1;
+		if (flags & DIRTREE_COMEAGAIN) flags = callback(new);
+	}
+	// If this had children, it was callback's job to free them already.
+	if (flags & DIRTREE_NOSAVE) {
+		free(new);
+		new = NULL;
+	}
+
+	return (flags & DIRTREE_ABORT)==DIRTREE_ABORT ? DIRTREE_ABORTVAL : new;
+}
+
+// Recursively read/process children of directory node (with dirfd in data),
+// filtering through callback().
 
-		snprintf(path+len, sizeof(toybuf)-len, "/%s", entry->d_name);
-		*ddt = this = dirtree_add_node(path);
-		if (!this) continue;
-		this->parent = parent;
-		this->depth = parent ? parent->depth + 1 : 1;
-		if (callback) norecurse = callback(path, this);
-		if (!norecurse && S_ISDIR(this->st.st_mode))
-			this->child = dirtree_read(path, this, callback);
-		if (callback) free(this);
-		else ddt = &(this->next);
-		path[len]=0;
+void dirtree_recurse(struct dirtree *node,
+					int (*callback)(struct dirtree *node))
+{
+	struct dirtree *new, **ddt = &(node->child);
+	struct dirent *entry;
+	DIR *dir;
+	int dirfd;
+
+	if (!(dir = fdopendir(node->data))) {
+		char *path = dirtree_path(node, 0);
+		perror_msg("No %s", path);
+		free(path);
+		close(node->data);
+	}
+	// Dunno if I really need to do this, but the fdopendir man page insists
+	dirfd = xdup(node->data);
+
+	// The extra parentheses are to shut the stupid compiler up.
+	while ((entry = readdir(dir))) {
+		if (!(new = dirtree_add_node(dirfd, entry->d_name))) continue;
+		new->parent = node;
+		new = handle_callback(new, callback);
+		if (new == DIRTREE_ABORTVAL) break;
+		if (new) {
+			*ddt = new;
+			ddt = &((*ddt)->next);
+		}
 	}
 
-	return dtroot;
+	closedir(dir);
+	close(dirfd);
 }
 
+// Create dirtree from path, using callback to filter nodes.
+// If callback == NULL allocate a tree of struct dirtree nodes and return
+// pointer to root node.
+
+struct dirtree *dirtree_read(char *path, int (*callback)(struct dirtree *node))
+{
+	int fd = open(".", 0);
+	struct dirtree *root = dirtree_add_node(fd, path);
+	root->data = fd;
 
+	return handle_callback(root, callback);
+}
diff --git a/lib/lib.c b/lib/lib.c
index 4190b065..a7eb65a6 100644
--- a/lib/lib.c
+++ b/lib/lib.c
@@ -208,6 +208,13 @@ void xclose(int fd)
 	if (close(fd)) perror_exit("xclose");
 }
 
+int xdup(int fd)
+{
+	fd = dup(fd);
+	if (fd == -1) perror_exit("xdup");
+	return fd;
+}
+
 // Die unless we can open/create a file, returning FILE *.
 FILE *xfopen(char *path, char *mode)
 {
@@ -497,6 +504,16 @@ long atolx(char *numstr)
 	return val;
 }
 
+int numlen(long l)
+{
+    int len = 0;
+    while (l) {
+       l /= 10;
+       len++;
+    }
+    return len;
+}
+
 // Return how long the file at fd is, if there's any way to determine it.
 off_t fdlength(int fd)
 {
diff --git a/lib/lib.h b/lib/lib.h
index 2f33236a..812908af 100644
--- a/lib/lib.h
+++ b/lib/lib.h
@@ -17,6 +17,9 @@ ssize_t getline(char **lineptr, size_t *n, FILE *stream);
 
 // llist.c
 
+// All these list types can be handled by the same code because first element
+// is always next pointer, so next = (mytype *)&struct.
+
 struct string_list {
 	struct string_list *next;
 	char str[0];
@@ -28,8 +31,7 @@ struct arg_list {
 };
 
 struct double_list {
-	struct double_list *next;
-	struct double_list *prev;
+	struct double_list *next, *prev;
 	char *data;
 };
 
@@ -42,16 +44,40 @@ struct double_list *dlist_add(struct double_list **list, char *data);
 void get_optflags(void);
 
 // dirtree.c
+
+// Values returnable from callback function (bitfield, or them together)
+// Default with no callback is 0
+
+// Do not add this node to the tree
+#define DIRTREE_NOSAVE       1
+// Do not recurse into children
+#define DIRTREE_NORECURSE    2
+// Call again after handling all children (Directories only. Sets linklen = -1)
+#define DIRTREE_COMEAGAIN    4
+// Follow symlinks to directories
+#define DIRTREE_SYMFOLLOW    8
+// Abort recursive dirtree.  (Forces NOSAVE and NORECURSE on this entry.)
+#define DIRTREE_ABORT      (256|DIRTREE_NOSAVE|DIRTREE_NORECURSE)
+
+#define DIRTREE_ABORTVAL ((struct dirtree *)1)
+
 struct dirtree {
-	struct dirtree *next, *child, *parent;
+	struct dirtree *next, *parent, *child;
+	long extra; // place for user to store their stuff (can be pointer)
+	long data;  // dirfd for directory, linklen for symlink
 	struct stat st;
-	int depth;
+	char *symlink;
 	char name[];
 };
 
-struct dirtree *dirtree_add_node(char *path);
-struct dirtree *dirtree_read(char *path, struct dirtree *parent,
-                    int (*callback)(char *path, struct dirtree *node));
+struct dirtree *dirtree_add_node(int dirfd, char *name);
+char *dirtree_path(struct dirtree *node, int *plen);
+int dirtree_isdotdot(struct dirtree *catch);
+struct dirtree *handle_callback(struct dirtree *new,
+	int (*callback)(struct dirtree *node));
+void dirtree_recurse(struct dirtree *node,
+	int (*callback)(struct dirtree *node));
+struct dirtree *dirtree_read(char *path, int (*callback)(struct dirtree *node));
 
 // lib.c
 void xstrcpy(char *dest, char *src, size_t size);
@@ -76,6 +102,7 @@ void xunlink(char *path);
 int xcreate(char *path, int flags, int mode);
 int xopen(char *path, int flags);
 void xclose(int fd);
+int xdup(int fd);
 FILE *xfopen(char *path, char *mode);
 ssize_t readall(int fd, void *buf, size_t len);
 ssize_t writeall(int fd, void *buf, size_t len);
@@ -97,6 +124,7 @@ void itoa_to_buf(int n, char *buf, unsigned buflen);
 char *utoa(unsigned n);
 char *itoa(int n);
 long atolx(char *c);
+int numlen(long l);
 off_t fdlength(int fd);
 char *xreadlink(char *name);
 void loopfiles_rw(char **argv, int flags, int permissions, int failok,
diff --git a/toys/cp.c b/toys/cp.c
index c3153e0a..a53d5fe0 100644
--- a/toys/cp.c
+++ b/toys/cp.c
@@ -10,8 +10,8 @@
 USE_CP(NEWTOY(cp, "<2vslrR+rdpa+d+p+rHLPif", TOYFLAG_BIN))
 
 config CP
-	bool "cp"
-	default y
+	bool "cp (broken by dirtree changes)"
+	default n
 	help
 	  usage: cp -fiprdal SOURCE... DEST
 
@@ -128,8 +128,9 @@ void cp_file(char *src, char *dst, struct stat *srcst)
 
 // Callback from dirtree_read() for each file/directory under a source dir.
 
-int cp_node(char *path, struct dirtree *node)
+int cp_node(struct dirtree *node)
 {
+	char *path = dirtree_path(node, 0); // TODO: use openat() instead
 	char *s = path+strlen(path);
 	struct dirtree *n;
 
@@ -148,6 +149,7 @@ int cp_node(char *path, struct dirtree *node)
 	s = xmsprintf("%s/%s", TT.destname, s);
 	cp_file(path, s, &(node->st));
 	free(s);
+	free(path); // redo this whole darn function.
 
 	return 0;
 }
@@ -209,7 +211,7 @@ void cp_main(void)
 				TT.keep_symlinks++;
 				strncpy(toybuf, src, sizeof(toybuf)-1);
 				toybuf[sizeof(toybuf)-1]=0;
-				dirtree_read(toybuf, NULL, cp_node);
+				dirtree_read(toybuf, cp_node);
 			} else error_msg("Skipped dir '%s'", src);
 		} else cp_file(src, dst, &st);
 		if (TT.destisdir) free(dst);
diff --git a/toys/ls.c b/toys/ls.c
index ec5606f5..fd316b64 100644
--- a/toys/ls.c
+++ b/toys/ls.c
@@ -3,16 +3,17 @@
  * ls.c - list files
  *
  * Copyright 2012 Andre Renaud <andre@bluewatersys.com>
+ * Copyright 2012 Rob Landley <rob@landley.net>
  *
  * See http://pubs.opengroup.org/onlinepubs/9699919799/utilities/ls.html
 
-USE_LS(NEWTOY(ls, "AnRlF1a", TOYFLAG_BIN))
+USE_LS(NEWTOY(ls, "ACFHLRSacdfiklmnpqrstux1", TOYFLAG_BIN))
 
 config LS
 	bool "ls"
-	default n
+	default y
 	help
-	  usage: ls [-lFaA1] [directory...]
+	  usage: ls [-ACFHLRSacdfiklmnpqrstux1] [directory...]
 	  list files
 
           -1    list one file per line
@@ -24,209 +25,294 @@ config LS
 
 #include "toys.h"
 
-#define FLAG_a 1
-#define FLAG_1 2
-#define FLAG_F 4
-#define FLAG_l 8
-#define FLAG_R 16
-#define FLAG_n 32
-#define FLAG_A 64
+#define FLAG_1 (1<<0)
+//#define FLAG_x (1<<1)
+//#define FLAG_u (1<<2)
+//#define FLAG_t (1<<3)
+//#define FLAG_s (1<<4)
+//#define FLAG_r (1<<5)
+//#define FLAG_q (1<<6)
+#define FLAG_p (1<<7)
+//#define FLAG_n (1<<8)
+#define FLAG_m (1<<9)
+#define FLAG_l (1<<10)
+//#define FLAG_k (1<<11)
+#define FLAG_i (1<<12)
+#define FLAG_f (1<<13)
+#define FLAG_d (1<<14)
+//#define FLAG_c (1<<15)
+#define FLAG_a (1<<16)
+//#define FLAG_S (1<<17)
+#define FLAG_R (1<<18)
+//#define FLAG_L (1<<19)
+//#define FLAG_H (1<<20)
+#define FLAG_F (1<<21)
+//#define FLAG_C (1<<21)
+#define FLAG_A (1<<22)
 
-static int dir_filter(const struct dirent *d)
+// test sst output (suid/sticky in ls flaglist)
+
+// ls -lR starts .: then ./subdir:
+
+DEFINE_GLOBALS(
+  struct dirtree *files;
+
+  unsigned width;
+  int again;
+)
+
+#define TT this.ls
+
+void dlist_to_dirtree(struct dirtree *parent)
+{
+    // Turn double_list into dirtree
+    struct dirtree *dt = parent->child;
+    if (dt) {
+        dt->parent->next = NULL;
+        while (dt) {
+            dt->parent = parent;
+            dt = dt->next;
+        }
+    }
+}
+
+static char endtype(struct stat *st)
 {
-    /* Skip over all '.*' entries, unless -a is given */
-    if (!(toys.optflags & FLAG_a)) {
-        /* -A means show everything except the . & .. entries */
-        if (toys.optflags & FLAG_A) {
-            if (strcmp(d->d_name, ".") == 0 ||
-                strcmp(d->d_name, "..") == 0)
-                return 0;
-        } else if (d->d_name[0] == '.')
-            return 0;
+    mode_t mode = st->st_mode;
+    if ((toys.optflags&(FLAG_F|FLAG_p)) && S_ISDIR(mode)) return '/';
+    if (toys.optflags & FLAG_F) {
+        if (S_ISLNK(mode) && !(toys.optflags & FLAG_F)) return '@';
+        if (S_ISREG(mode) && (mode&0111)) return '*';
+        if (S_ISFIFO(mode)) return '|';
+        if (S_ISSOCK(mode)) return '=';
     }
-    return 1;
+    return 0;
+}
+
+static char *getusername(uid_t uid)
+{
+  struct passwd *pw = getpwuid(uid);
+  return pw ? pw->pw_name : utoa(uid);
+}
+
+static char *getgroupname(gid_t gid)
+{
+  struct group *gr = getgrgid(gid);
+  return gr ? gr->gr_name : utoa(gid);
 }
 
-static void do_ls(int fd, char *name)
+// Figure out size of printable entry fields for display indent/wrap
+
+static void entrylen(struct dirtree *dt, unsigned *len)
 {
-    struct dirent **entries;
-    int nentries;
-    int i;
-    int maxwidth = -1;
-    int ncolumns = 1;
-    struct dirent file_dirent;
-    struct dirent *file_direntp;
-
-    if (!name || strcmp(name, "-") == 0)
-        name = ".";
-
-    if (toys.optflags & FLAG_R)
-        xprintf("\n%s:\n", name);
-
-    /* Get all the files in this directory */
-    nentries = scandir(name, &entries, dir_filter, alphasort);
-    if (nentries < 0) {
-        /* We've just selected a single file, so create a single-length list */
-        /* FIXME: This means that ls *.x results in a whole bunch of single
-         * listings, not one combined listing.
-         */
-        if (errno == ENOTDIR) {
-            nentries = 1;
-            strcpy(file_dirent.d_name, name);
-            file_direntp = &file_dirent;
-            entries = &file_direntp;
-        } else 
-            perror_exit("ls: cannot access %s'", name);
+    struct stat *st = &(dt->st);
+    unsigned flags = toys.optflags;
+
+    *len = strlen(dt->name);
+    if (endtype(st)) ++*len;
+    if (flags & FLAG_m) ++*len;
+
+    if (flags & FLAG_i) *len += (len[1] = numlen(st->st_ino));
+    if (flags & FLAG_l) {
+        len[2] = numlen(st->st_nlink);
+        len[3] = strlen(getusername(st->st_uid));
+        len[4] = strlen(getgroupname(st->st_gid));
+        len[5] = numlen(st->st_size);
     }
+}
+
+static int compare(void *a, void *b)
+{
+    struct dirtree *dta = *(struct dirtree **)a;
+    struct dirtree *dtb = *(struct dirtree **)b;
+
+// TODO handle flags
+    return strcmp(dta->name, dtb->name);
+}
 
+static int filter(struct dirtree *new)
+{
+    int ret = DIRTREE_NORECURSE;
+
+// TODO -1f should print here to handle enormous dirs without runing out of mem.
+
+    if (!(toys.optflags & (FLAG_a|FLAG_A)) && new->name[0]=='.')
+        ret |= DIRTREE_NOSAVE;
+    else if (!(toys.optflags & FLAG_a)) ret |= dirtree_isdotdot(new);
+
+    return ret;
+}
+
+// Display a list of dirtree entries, according to current format
+// Output types -1, -l, -C, or stream
 
-    /* Determine the widest entry so we can flow them properly */
-    if (!(toys.optflags & FLAG_1)) {
-        int columns;
-        char *columns_str;
+static void listfiles(struct dirtree *indir)
+{
+    struct dirtree *dt, **sort = 0;
+    unsigned long dtlen = 0, ul = 0;
+    unsigned width, flags = toys.optflags, totals[6], len[6];
+    int showdirs = 1;
 
-        for (i = 0; i < nentries; i++) {
-            struct dirent *ent = entries[i];
-            int width;
+    // Figure out if we should show directories and current directory name
+    if (indir == TT.files) showdirs = (flags & (FLAG_d|FLAG_R));
+    else if (indir->parent == TT.files && toys.optc <= 1 && !(flags&FLAG_R));
+    else {
+        char *path = dirtree_path(indir, 0);
+        if (TT.again++) xputc('\n');
+        xprintf("%s:\n", path);
+        free(path);
+    }
 
-            width = strlen(ent->d_name);
-            if (width > maxwidth)
-                maxwidth = width;
+
+    // Copy linked list to array and sort it. Directories go in array because
+    // we visit them in sorted order.
+
+    for (;;) {
+        for (dt = indir->child; dt; dt = dt->next) {
+            if (sort) sort[dtlen] = dt;
+            dtlen++;
         }
-        /* We always want at least a single space for each entry */
-        maxwidth++;
-        if (toys.optflags & FLAG_F)
-            maxwidth++;
-
-        columns_str = getenv("COLUMNS");
-        columns = columns_str ? atoi(columns_str) : 80;
-        ncolumns = maxwidth ? columns / maxwidth : 1;
+        if (sort) break;
+        sort = xmalloc(dtlen * sizeof(void *));
+        dtlen = 0;
+        continue;
     }
 
-    for (i = 0; i < nentries; i++) {
-        struct dirent *ent = entries[i];
-        int len = strlen(ent->d_name);
-        struct stat st;
-        int stat_valid = 0;
-
-        sprintf(toybuf, "%s/%s", name, ent->d_name);
-
-        /* Provide the ls -l long output */
-        if (toys.optflags & FLAG_l) {
-            char type;
-            char timestamp[64];
-            struct tm mtime;
-
-            if (lstat(toybuf, &st))
-                perror_exit("Can't stat %s", toybuf);
-            stat_valid = 1;
-            if (S_ISDIR(st.st_mode))
-                type = 'd';
-            else if (S_ISCHR(st.st_mode))
-                type = 'c';
-            else if (S_ISBLK(st.st_mode))
-                type = 'b';
-            else if (S_ISLNK(st.st_mode))
-                type = 'l';
-            else
-                type = '-';
-
-            xprintf("%c%c%c%c%c%c%c%c%c%c ", type,
-                (st.st_mode & S_IRUSR) ? 'r' : '-',
-                (st.st_mode & S_IWUSR) ? 'w' : '-',
-                (st.st_mode & S_IXUSR) ? 'x' : '-',
-                (st.st_mode & S_IRGRP) ? 'r' : '-',
-                (st.st_mode & S_IWGRP) ? 'w' : '-',
-                (st.st_mode & S_IXGRP) ? 'x' : '-',
-                (st.st_mode & S_IROTH) ? 'r' : '-',
-                (st.st_mode & S_IWOTH) ? 'w' : '-',
-                (st.st_mode & S_IXOTH) ? 'x' : '-');
-
-            xprintf("%2d ", st.st_nlink);
-            if (toys.optflags & FLAG_n) {
-                xprintf("%4d ", st.st_uid);
-                xprintf("%4d ", st.st_gid);
-            } else {
-                struct passwd *pwd = getpwuid(st.st_uid);
-                struct group *grp = getgrgid(st.st_gid);
-                if (!pwd)
-                    xprintf("%4d ", st.st_uid);
-                else
-                    xprintf("%-10s ", pwd->pw_name);
-                if (!grp)
-                    xprintf("%4d ", st.st_gid);
-                else
-                    xprintf("%-10s ", grp->gr_name);
-            }
-            if (S_ISCHR(st.st_mode) || S_ISBLK(st.st_mode))
-                xprintf("%3d, %3d ", major(st.st_rdev), minor(st.st_rdev));
-            else
-                xprintf("%12lld ", st.st_size);
+    if (flags & FLAG_l) xprintf("total %lu\n", dtlen);
 
-            localtime_r(&st.st_mtime, &mtime);
+    if (!(flags & FLAG_f)) qsort(sort, dtlen, sizeof(void *), (void *)compare);
 
-            strftime(timestamp, sizeof(timestamp), "%b %e %H:%M", &mtime);
-            xprintf("%s ", timestamp);
+    // Find largest entry in each field for everything but -1
+
+    memset(totals, 0, 6*sizeof(unsigned));
+    if ((flags & (FLAG_1|FLAG_l)) != FLAG_1) {
+        for (ul = 0; ul<dtlen; ul++) {
+            if (!showdirs && S_ISDIR(sort[ul]->st.st_mode)) continue;
+            entrylen(sort[ul], len);
+            if (flags & FLAG_l) {
+                for (width=0; width<6; width++)
+                    if (len[width] > totals[width]) totals[width] = len[width];
+//TODO            } else if (flags & FLAG_C) {
+            } else if (*len > *totals) *totals = *len;
         }
+    }
 
-        xprintf("%s", ent->d_name);
+    // Loop through again to produce output.
+    width = 0;
+    memset(toybuf, ' ', 256);
+    for (ul = 0; ul<dtlen; ul++) {
+        struct stat *st = &(sort[ul]->st);
+        mode_t mode = st->st_mode;
+        char et = endtype(st);
 
-        /* Append the file-type indicator character */
-        if (toys.optflags & FLAG_F) {
-            if (!stat_valid) {
-                if (lstat(toybuf, &st))
-                    perror_exit("Can't stat %s", toybuf);
-                stat_valid = 1;
-            }
-            if (S_ISDIR(st.st_mode)) {
-                xprintf("/");
-                len++;
-            } else if (S_ISREG(st.st_mode) &&
-                (st.st_mode & (S_IXUSR | S_IXGRP | S_IXOTH))) {
-                xprintf("*");
-                len++;
-            } else if (S_ISLNK(st.st_mode)) {
-                xprintf("@");
-                len++;
+        if (S_ISDIR(mode) && !showdirs) continue;
+        entrylen(sort[ul], len);
+
+        if (ul) {
+            if (toys.optflags & FLAG_m) xputc(',');
+            if ((flags & FLAG_1) || width+1+*len > TT.width) {
+                xputc('\n');
+                width = 0;
+            } else {
+                xputc(' ');
+                width++;
             }
         }
-        if (toys.optflags & FLAG_1) {
-            xprintf("\n");
-        } else {
-            if (i % ncolumns == ncolumns - 1)
-                xprintf("\n");
-            else
-                xprintf("%*s", maxwidth - len, "");
+        width += *len;
+
+        if (flags & FLAG_i)
+            xprintf("% *lu ", len[1], (unsigned long)st->st_ino);
+
+        if (flags & FLAG_l) {
+            struct tm *tm;
+            char perm[11], thyme[64], c, d;
+            int i, bit;
+
+            perm[10]=0;
+            for (i=0; i<9; i++) {
+                bit = mode & (1<<i);
+                c = i%3;
+                if (!c && (mode & (1<<((d=i/3)+9)))) {
+                    c = "tss"[d];
+                    if (!bit) c &= 0x20;
+                } else c = bit ? "xwr"[c] : '-';
+                perm[9-i] = c;
+            }
+
+            if (S_ISDIR(mode)) c = 'd';
+            else if (S_ISBLK(mode)) c = 'b';
+            else if (S_ISCHR(mode)) c = 'c';
+            else if (S_ISLNK(mode)) c = 'l';
+            else if (S_ISFIFO(mode)) c = 'p';
+            else if (S_ISSOCK(mode)) c = 's';
+            else c = '-';
+            *perm = c;
+
+            tm = localtime(&(st->st_mtime));
+            strftime(thyme, sizeof(thyme), "%F %H:%M", tm);
+
+            xprintf("%s% *d %s%s%s%s% *d %s ", perm, totals[2]+1, st->st_nlink,
+                    getusername(st->st_uid), toybuf+255-(totals[3]-len[3]),
+                    getgroupname(st->st_gid), toybuf+256-(totals[4]-len[4]),
+                    totals[5]+1, st->st_size, thyme);
         }
+
+        xprintf("%s", sort[ul]->name);
+        if ((flags & FLAG_l) && S_ISLNK(mode))
+            xprintf(" -> %s", sort[ul]->symlink);
+
+        if (et) xputc(et);
     }
-    /* Make sure we put at a trailing new line in */
-    if (!(toys.optflags & FLAG_1) && (i % ncolumns))
-        xprintf("\n");
-
-    if (toys.optflags & FLAG_R) {
-        for (i = 0; i < nentries; i++) {
-            struct dirent *ent = entries[i];
-            struct stat st;
-            char dirname[PATH_MAX];
-
-            sprintf(dirname, "%s/%s", name, ent->d_name);
-            if (lstat(dirname, &st))
-                perror_exit("Can't stat %s", dirname);
-            if (S_ISDIR(st.st_mode))
-                do_ls(0, dirname);
+
+    if (width) xputc('\n');
+
+    for (ul = 0; ul<dtlen; free(sort[ul++])) {
+// TODO follow symlinks when?
+        if (!S_ISDIR(sort[ul]->st.st_mode) || dirtree_isdotdot(sort[ul]))
+            continue;
+        if (indir == TT.files || (flags & FLAG_R)) {
+            sort[ul]->data = openat(indir->data, sort[ul]->name, 0);
+            dirtree_recurse(sort[ul], filter);
+            listfiles(sort[ul]);
         }
     }
+    free(sort);
+    close(indir->data);
+
+
 }
 
 void ls_main(void)
 {
-    /* If the output is not a TTY, then just do one-file per line
-     * This makes ls easier to use with other command line tools (grep/awk etc...)
-     */
-    if (!isatty(fileno(stdout)))
-        toys.optflags |= FLAG_1;
-    /* Long output must be one-file per line */
-    if (toys.optflags & FLAG_l)
-        toys.optflags |= FLAG_1;
-    loopfiles(toys.optargs, do_ls);
+    char **s, *noargs[] = {".", 0};
+
+    // Do we have an implied -1
+    if (!isatty(1) || (toys.optflags&FLAG_l)) toys.optflags |= FLAG_1;
+    else {
+        TT.width = 80;
+        terminal_size(&TT.width, NULL);
+    }
+
+    // Iterate through command line arguments, collecting directories and files.
+    // Non-absolute paths are relative to current directory.
+    TT.files = dirtree_add_node(0, 0);
+    TT.files->data =open(".", 0);
+    for (s = toys.optargs ? toys.optargs : noargs; *s; s++) {
+        struct dirtree *dt = dirtree_add_node(TT.files->data, *s);
+
+        if (!dt) {
+            toys.exitval = 1;
+            continue;
+        }
+
+        // Typecast means double_list->prev temporarirly goes in dirtree->parent
+        dlist_add_nomalloc((struct double_list **)&TT.files->child,
+                           (struct double_list *)dt);
+    }
+
+    // Turn double_list into dirtree
+    dlist_to_dirtree(TT.files);
+
+    // Display the files we collected
+    listfiles(TT.files);
 }
diff --git a/toys/mke2fs.c b/toys/mke2fs.c
index cf313424..47f31f2d 100644
--- a/toys/mke2fs.c
+++ b/toys/mke2fs.c
@@ -10,7 +10,7 @@
 USE_MKE2FS(NEWTOY(mke2fs, "<1>2g:Fnqm#N#i#b#", TOYFLAG_SBIN))
 
 config MKE2FS
-	bool "mke2fs"
+	bool "mke2fs (unfinished and broken by dirtree changes)"
 	default n
 	help
 	  usage: mke2fs [-Fnq] [-b ###] [-N|i ###] [-m ###] device