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.)

3 files changed, 272 insertions, 184 deletions

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