Add expand command as described in POSIX-2008.

Erratum: Do not handle backspace.

5 files changed, 207 insertions, 3 deletions

diff --git a/configure b/configure
index bf2561b7..4aafb660 100644
--- a/configure
+++ b/configure
@@ -4,11 +4,11 @@
 
 # A synonym.
 [ -z "$CROSS_COMPILE" ] && CROSS_COMPILE="$CROSS"
-[ -z "$CFLAGS" ] && CFLAGS="-Wall -Wundef -Wno-char-subscripts"
+[ -z "$CFLAGS" ] && CFLAGS="-g -Wall -Wundef -Wno-char-subscripts"
 # Required for our expected ABI. we're 8-bit clean thus "char" must be unsigned.
 CFLAGS="$CFLAGS -funsigned-char"
 
-[ -z "$OPTIMIZE" ] && OPTIMIZE="-Os -ffunction-sections -fdata-sections -Wl,--gc-sections"
+[ -z "$OPTIMIZE" ] && OPTIMIZE="-O0 -ffunction-sections -fdata-sections -Wl,--gc-sections"
 [ -z "$CC" ] && CC=cc
 [ -z "$STRIP" ] && STRIP=strip
 
diff --git a/lib/lib.c b/lib/lib.c
index 57000ac7..36f78ceb 100644
--- a/lib/lib.c
+++ b/lib/lib.c
@@ -1182,6 +1182,17 @@ char* make_human_readable(unsigned long long size, unsigned long unit)
   return NULL; //not reached
 }
 
+// strtoul with exit on error
+unsigned long xstrtoul(const char *nptr, char **endptr, int base)
+{
+    unsigned long l;
+    errno = 0;
+    l = strtoul(nptr, endptr, base);
+    if (errno)
+        perror_exit("xstrtoul");
+    return l;
+}
+
 /*
  * used to get the interger value.
  */
diff --git a/lib/lib.h b/lib/lib.h
index 5c4cc46f..f8627149 100644
--- a/lib/lib.h
+++ b/lib/lib.h
@@ -29,6 +29,11 @@ struct arg_list {
   char *arg;
 };
 
+struct offset_list {
+  struct offset_list *next;
+  off_t off;
+};
+
 struct double_list {
   struct double_list *next, *prev;
   char *data;
@@ -145,7 +150,7 @@ void crc_init(unsigned int *crc_table, int little_endian);
 void terminal_size(unsigned *x, unsigned *y);
 int yesno(char *prompt, int def);
 void for_each_pid_with_name_in(char **names, void (*callback)(pid_t pid));
-
+unsigned long xstrtoul(const char *nptr, char **endptr, int base);
 
 // getmountlist.c
 struct mtab_list {
@@ -176,5 +181,9 @@ int update_password(char *filename, char* username, char* encrypted);
 // du helper functions
 char* make_human_readable(unsigned long long size, unsigned long unit);
 
+// useful tools
+#define min(a,b) (a)<(b) ? (a) : (b)
+#define max(a,b) (a)>(b) ? (a) : (b)
+
 // cut helper functions
 unsigned long get_int_value(const char *numstr, unsigned lowrange, unsigned highrange);
diff --git a/scripts/test/expand.test b/scripts/test/expand.test
new file mode 100644
index 00000000..73374562
--- /dev/null
+++ b/scripts/test/expand.test
@@ -0,0 +1,43 @@
+#!/bin/bash
+
+# POSIX 2008 compliant expand tests.
+# Copyright 2012 by Jonathan Clairembault <jonathan@clairembault.fr>
+
+[ -f testing.sh ] && . testing.sh
+
+# some basic tests
+
+testing "expand default" "expand input" "        foo     bar\n" "\tfoo\tbar\n" ""
+testing "expand default stdin" "expand"  "        foo     bar\n" "" "\tfoo\tbar\n"
+testing "expand single" "expand -t 2 input" "  foo bar\n" "\tfoo\tbar\n" ""
+testing "expand tablist" "expand -t 5,10,12 input" "     foo  bar foo\n" "\tfoo\tbar\tfoo\n" ""
+
+# advanced tests
+
+POW=15
+TABSTOP=1
+BIGTAB=" "
+for i in $(seq $POW); do
+    BIGTAB=$BIGTAB$BIGTAB
+    TABSTOP=$[$TABSTOP*2]
+done
+testing "expand long tab single" "expand -t $TABSTOP input" "${BIGTAB}foo\n" "\tfoo\n" ""
+testing "expand long tab tablist" "expand -t $TABSTOP,$[TABSTOP+5] input" \
+        "${BIGTAB}foo  bar\n" "\tfoo\tbar\n" ""
+
+testing "expand multiline single" "expand -t 4 input" "foo \n    bar\n" "foo\t\n\tbar\n" ""
+testing "expand multiline tablist" "expand -t 4,8 input" \
+        "foo     bar\n    bar foo\n" "foo\t\tbar\n\tbar\tfoo\n" ""
+POW=15
+BIGLINE="foo "
+for i in $(seq $POW); do
+    BIGLINE=$BIGLINE$BIGLINE
+done
+if [ $POW -gt 0 ]; then
+    EXPANDLINE="${BIGLINE}        foo\n"
+else
+    EXPANDLINE="${BIGLINE}    foo\n"
+fi
+BIGLINE="${BIGLINE}\tfoo\n"
+testing "expand long line single" "expand input" \
+        "${EXPANDLINE}" "$BIGLINE" ""
diff --git a/toys/posix/expand.c b/toys/posix/expand.c
new file mode 100644
index 00000000..739c326d
--- /dev/null
+++ b/toys/posix/expand.c
@@ -0,0 +1,141 @@
+/* expand.c - expands tabs to space
+ *
+ * FIXME: handle backspace.
+ *
+ * Copyright 2012 Jonathan Clairembault <jonathan at clairembault dot fr>
+ *
+ * See http://http://pubs.opengroup.org/onlinepubs/9699919799/nframe.html
+
+USE_EXPAND(NEWTOY(expand, "t:", TOYFLAG_USR|TOYFLAG_BIN))
+
+config EXPAND
+  bool "expand"
+  default n
+  help
+    usage: expand [-t tablist] [file...]
+
+    Command expand. Expands tabs to space according to tabstops.
+
+    -t  tablist
+    Specify the tab stops.  The argument tablist consists of either a single 
+    strictly positive decimal integer or a list of tabstops. If a single number 
+    is given, tabs are set that number of column positions apart instead of the 
+    default 8.
+
+    If a list of tabstops is given, the list is made of two or more strictly 
+    positive decimal integers, separated by <blank> or <comma> characters, in 
+    strictly ascending order. The <tab> characters are set at those specific 
+    column positions.
+
+    In the event of expand having to process a <tab> at a position beyond the 
+    last of those specified in a multiple tab-stop list, the <tab> is replaced 
+    by a single <space> in the output.
+
+    Any <backspace> characters shall be copied to the output and cause the 
+    column position count for tab stop calculations to be decremented; the 
+    column position count shall not be decremented below zero.
+*/
+
+#define FOR_expand
+#include "toys.h"
+
+GLOBALS(
+  char *t_flags;
+  struct offset_list tablist;
+)
+
+static void build_tablist(char *tabstops)
+{
+  char *ctx;
+  struct offset_list *tablist = &TT.tablist;
+  char *s, *ref;
+  off_t stop, last_stop;
+
+  /* for every tabstop decode and add to list */
+  for (stop = last_stop = 0, s = ref = xstrdup(tabstops); ;
+       last_stop = stop, s = NULL) {
+    char *tabstop = strtok_r(s, " ,", &ctx);
+
+    if (!tabstop) return;
+
+    stop = xstrtoul(tabstop, NULL, 0);
+    if (stop <= last_stop) {
+      free(ref);
+      toys.exithelp = 1;
+      error_exit("tablist ascending order");
+    }
+    tablist->next = xzalloc(sizeof(*tablist));
+    tablist->next->off = stop;
+    tablist = tablist->next;
+  }
+
+  free(ref);
+}
+
+static void expand_file(int fd, char *name)
+{
+  ssize_t rdn;
+  char *rdbuf, *wrbuf;
+  size_t wrbuflen, rdbuflen;
+  ssize_t rdbufi = 0, wrbufi = 0;
+  ssize_t wrlinei;
+  int hastablist = !!TT.tablist.next->next;
+  struct offset_list *tablist = TT.tablist.next;
+  ssize_t stop = tablist->off;
+
+  wrbuflen = rdbuflen = ARRAY_LEN(toybuf)/2;
+  rdbuf = toybuf;
+  wrbuf = toybuf + rdbuflen;
+  do {
+    rdn = readall(fd, rdbuf, rdbuflen);
+    if (rdn < 0) perror_exit("%s", name);
+    for (rdbufi=0, wrbufi=0; rdbufi<rdn; rdbufi++) {
+      if (wrbufi == wrbuflen) { /* flush expand buffer when full */
+        writeall(STDOUT_FILENO, wrbuf, wrbuflen);
+        wrbufi = 0;
+      }
+      if (rdbuf[rdbufi] == '\t') { /* expand tab */
+        size_t count;
+        size_t tabsize;
+
+        /* search next tab stop */
+        while(tablist && (stop <= wrlinei)) {
+          stop = hastablist ? tablist->off : stop + tablist->off;
+          tablist = hastablist ? tablist->next : tablist;
+        }
+        tabsize = ((stop - wrlinei < 2)) ? 1 : stop - wrlinei;
+        while (tabsize) { /* long expand */
+          count = min(tabsize, wrbuflen - wrbufi);
+          memset(wrbuf + wrbufi, ' ', count);
+          tabsize -= count;
+          if (tabsize) { /* flush expand buffer when full */
+            writeall(STDOUT_FILENO, wrbuf, wrbuflen);
+            wrbufi = 0;
+          } else wrbufi += count;
+        }
+        wrlinei += count;
+      } else { /* copy input to output */
+        wrbuf[wrbufi++] = rdbuf[rdbufi];
+        wrlinei += 1;
+        /* flush expand buffer and reset tablist at newline */
+        if (rdbuf[rdbufi] == '\n') {
+          writeall(STDOUT_FILENO, wrbuf, wrbufi);
+          tablist = TT.tablist.next;
+          stop = tablist->off;
+          wrbufi = wrlinei = 0;
+        }
+      }
+    }
+  } while (rdn == rdbuflen);
+  /* flush last expand buffer */
+  writeall(STDOUT_FILENO, wrbuf, wrbufi);
+}
+
+void expand_main(void)
+{
+  build_tablist((toys.optflags & FLAG_t) ? TT.t_flags : "8");
+  /* expand every file */
+  loopfiles(toys.optargs, expand_file);
+  /* free tablist */
+  llist_traverse(TT.tablist.next, free);
+}