Move some unfinished commands to the "pending" directory.

3 files changed, 1179 insertions, 0 deletions

diff --git a/toys/pending/mke2fs.c b/toys/pending/mke2fs.c
new file mode 100644
index 00000000..1a83e4f6
--- /dev/null
+++ b/toys/pending/mke2fs.c
@@ -0,0 +1,656 @@
+/* mke2fs.c - Create an ext2 filesystem image.
+ *
+ * Copyright 2006, 2007 Rob Landley <rob@landley.net>
+
+// Still to go: "E:jJ:L:m:O:"
+USE_MKE2FS(NEWTOY(mke2fs, "<1>2g:Fnqm#N#i#b#", TOYFLAG_SBIN))
+
+config MKE2FS
+  bool "mke2fs (unfinished and broken by dirtree changes)"
+  default n
+  help
+    usage: mke2fs [-Fnq] [-b ###] [-N|i ###] [-m ###] device
+
+    Create an ext2 filesystem on a block device or filesystem image.
+
+    -F         Force to run on a mounted device
+    -n         Don't write to device
+    -q         Quiet (no output)
+    -b size    Block size (1024, 2048, or 4096)
+    -N inodes  Allocate this many inodes
+    -i bytes   Allocate one inode for every XXX bytes of device
+    -m percent Reserve this percent of filesystem space for root user
+
+config MKE2FS_JOURNAL
+  bool "Journaling support (ext3)"
+  default n
+  depends on MKE2FS
+  help
+    usage: [-j] [-J size=###,device=XXX]
+
+    -j         Create journal (ext3)
+    -J         Journal options
+               size: Number of blocks (1024-102400)
+               device: Specify an external journal
+
+config MKE2FS_GEN
+  bool "Generate (gene2fs)"
+  default n
+  depends on MKE2FS
+  help
+    usage: gene2fs [options] device filename
+
+    The [options] are the same as mke2fs.
+
+config MKE2FS_LABEL
+  bool "Label support"
+  default n
+  depends on MKE2FS
+  help
+    usage: mke2fs [-L label] [-M path] [-o string]
+
+    -L         Volume label
+    -M         Path to mount point
+    -o         Created by
+
+config MKE2FS_EXTENDED
+  bool "Extended options"
+  default n
+  depends on MKE2FS
+  help
+    usage: mke2fs [-E stride=###] [-O option[,option]]
+
+    -E stride= Set RAID stripe size (in blocks)
+    -O [opts]  Specify fewer ext2 option flags (for old kernels)
+               All of these are on by default (as appropriate)
+       none         Clear default options (all but journaling)
+       dir_index    Use htree indexes for large directories
+       filetype     Store file type info in directory entry
+       has_journal  Set by -j
+       journal_dev  Set by -J device=XXX
+       sparse_super Don't allocate huge numbers of redundant superblocks
+*/
+
+#define FOR_mke2fs
+#include "toys.h"
+
+GLOBALS(
+  // Command line arguments.
+  long blocksize;
+  long bytes_per_inode;
+  long inodes;           // Total inodes in filesystem.
+  long reserved_percent; // Integer precent of space to reserve for root.
+  char *gendir;          // Where to read dirtree from.
+
+  // Internal data.
+  struct dirtree *dt;    // Tree of files to copy into the new filesystem.
+  unsigned treeblocks;   // Blocks used by dt
+  unsigned treeinodes;   // Inodes used by dt
+
+  unsigned blocks;       // Total blocks in the filesystem.
+  unsigned freeblocks;   // Free blocks in the filesystem.
+  unsigned inodespg;     // Inodes per group
+  unsigned groups;       // Total number of block groups.
+  unsigned blockbits;    // Bits per block.  (Also blocks per group.)
+
+  // For gene2fs
+  unsigned nextblock;    // Next data block to allocate
+  unsigned nextgroup;    // Next group we'll be allocating from
+  int fsfd;              // File descriptor of filesystem (to output to).
+
+  struct ext2_superblock sb;
+)
+
+#define INODES_RESERVED 10
+
+static uint32_t div_round_up(uint32_t a, uint32_t b)
+{
+  uint32_t c = a/b;
+
+  if (a%b) c++;
+  return c;
+}
+
+// Calculate data blocks plus index blocks needed to hold a file.
+
+static uint32_t file_blocks_used(uint64_t size, uint32_t *blocklist)
+{
+  uint32_t dblocks = (uint32_t)((size+(TT.blocksize-1))/TT.blocksize);
+  uint32_t idx=TT.blocksize/4, iblocks=0, diblocks=0, tiblocks=0;
+
+  // Fill out index blocks in inode.
+
+  if (blocklist) {
+    int i;
+
+    // Direct index blocks
+    for (i=0; i<13 && i<dblocks; i++) blocklist[i] = i;
+    // Singly indirect index blocks
+    if (dblocks > 13+idx) blocklist[13] = 13+idx;
+    // Doubly indirect index blocks
+    idx = 13 + idx + (idx*idx);
+    if (dblocks > idx) blocklist[14] = idx;
+
+    return 0;
+  }
+
+  // Account for direct, singly, doubly, and triply indirect index blocks
+
+  if (dblocks > 12) {
+    iblocks = ((dblocks-13)/idx)+1;
+    if (iblocks > 1) {
+      diblocks = ((iblocks-2)/idx)+1;
+      if (diblocks > 1)
+        tiblocks = ((diblocks-2)/idx)+1;
+    }
+  }
+
+  return dblocks + iblocks + diblocks + tiblocks;
+}
+
+// Use the parent pointer to iterate through the tree non-recursively.
+static struct dirtree *treenext(struct dirtree *this)
+{
+  while (this && !this->next) this = this->parent;
+  if (this) this = this->next;
+
+  return this;
+}
+
+// Recursively calculate the number of blocks used by each inode in the tree.
+// Returns blocks used by this directory, assigns bytes used to *size.
+// Writes total block count to TT.treeblocks and inode count to TT.treeinodes.
+
+static long check_treesize(struct dirtree *that, off_t *size)
+{
+  long blocks;
+
+  while (that) {
+    *size += sizeof(struct ext2_dentry) + strlen(that->name);
+
+    if (that->child)
+      that->st.st_blocks = check_treesize(that->child, &that->st.st_size);
+    else if (S_ISREG(that->st.st_mode)) {
+       that->st.st_blocks = file_blocks_used(that->st.st_size, 0);
+       TT.treeblocks += that->st.st_blocks;
+    }
+    that = that->next;
+  }
+  TT.treeblocks += blocks = file_blocks_used(*size, 0);
+  TT.treeinodes++;
+
+  return blocks;
+}
+
+// Calculate inode numbers and link counts.
+//
+// To do this right I need to copy the tree and sort it, but here's a really
+// ugly n^2 way of dealing with the problem that doesn't scale well to large
+// numbers of files (> 100,000) but can be done in very little code.
+// This rewrites inode numbers to their final values, allocating depth first.
+
+static void check_treelinks(struct dirtree *tree)
+{
+  struct dirtree *current=tree, *that;
+  long inode = INODES_RESERVED;
+
+  while (current) {
+    ++inode;
+    // Since we can't hardlink to directories, we know their link count.
+    if (S_ISDIR(current->st.st_mode)) current->st.st_nlink = 2;
+    else {
+      dev_t new = current->st.st_dev;
+
+      if (!new) continue;
+
+      // Look for other copies of current node
+      current->st.st_nlink = 0;
+      for (that = tree; that; that = treenext(that)) {
+        if (current->st.st_ino == that->st.st_ino &&
+          current->st.st_dev == that->st.st_dev)
+        {
+          current->st.st_nlink++;
+          current->st.st_ino = inode;
+        }
+      }
+    }
+    current->st.st_ino = inode;
+    current = treenext(current);
+  }
+}
+
+// According to http://www.opengroup.org/onlinepubs/9629399/apdxa.htm
+// we should generate a uuid structure by reading a clock with 100 nanosecond
+// precision, normalizing it to the start of the gregorian calendar in 1582,
+// and looking up our eth0 mac address.
+//
+// On the other hand, we have 128 bits to come up with a unique identifier, of
+// which 6 have a defined value.  /dev/urandom it is.
+
+static void create_uuid(char *uuid)
+{
+  // Read 128 random bits
+  int fd = xopen("/dev/urandom", O_RDONLY);
+  xreadall(fd, uuid, 16);
+  close(fd);
+
+  // Claim to be a DCE format UUID.
+  uuid[6] = (uuid[6] & 0x0F) | 0x40;
+  uuid[8] = (uuid[8] & 0x3F) | 0x80;
+
+  // rfc2518 section 6.4.1 suggests if we're not using a macaddr, we should
+  // set bit 1 of the node ID, which is the mac multicast bit.  This means we
+  // should never collide with anybody actually using a macaddr.
+  uuid[11] = uuid[11] | 128;
+}
+
+// Calculate inodes per group from total inodes.
+static uint32_t get_inodespg(uint32_t inodes)
+{
+  uint32_t temp;
+
+  // Round up to fill complete inode blocks.
+  temp = (inodes + TT.groups - 1) / TT.groups;
+  inodes = TT.blocksize/sizeof(struct ext2_inode);
+  return ((temp + inodes - 1)/inodes)*inodes;
+}
+
+// Fill out superblock and TT structures.
+
+static void init_superblock(struct ext2_superblock *sb)
+{
+  uint32_t temp;
+
+  // Set log_block_size and log_frag_size.
+
+  for (temp = 0; temp < 4; temp++) if (TT.blocksize == 1024<<temp) break;
+  if (temp==4) error_exit("bad blocksize");
+  sb->log_block_size = sb->log_frag_size = SWAP_LE32(temp);
+
+  // Fill out blocks_count, r_blocks_count, first_data_block
+
+  sb->blocks_count = SWAP_LE32(TT.blocks);
+  sb->free_blocks_count = SWAP_LE32(TT.freeblocks);
+  temp = (TT.blocks * (uint64_t)TT.reserved_percent) / 100;
+  sb->r_blocks_count = SWAP_LE32(temp);
+
+  sb->first_data_block = SWAP_LE32(TT.blocksize == 1024 ? 1 : 0);
+
+  // Set blocks_per_group and frags_per_group, which is the size of an
+  // allocation bitmap that fits in one block (I.E. how many bits per block)?
+
+  sb->blocks_per_group = sb->frags_per_group = SWAP_LE32(TT.blockbits);
+
+  // Set inodes_per_group and total inodes_count
+  sb->inodes_per_group = SWAP_LE32(TT.inodespg);
+  sb->inodes_count = SWAP_LE32(TT.inodespg * TT.groups);
+
+  // Determine free inodes.
+  temp = TT.inodespg*TT.groups - INODES_RESERVED;
+  if (temp < TT.treeinodes) error_exit("Not enough inodes.\n");
+  sb->free_inodes_count = SWAP_LE32(temp - TT.treeinodes);
+
+  // Fill out the rest of the superblock.
+  sb->max_mnt_count=0xFFFF;
+  sb->wtime = sb->lastcheck = sb->mkfs_time = SWAP_LE32(time(NULL));
+  sb->magic = SWAP_LE32(0xEF53);
+  sb->state = sb->errors = SWAP_LE16(1);
+
+  sb->rev_level = SWAP_LE32(1);
+  sb->first_ino = SWAP_LE32(INODES_RESERVED+1);
+  sb->inode_size = SWAP_LE16(sizeof(struct ext2_inode));
+  sb->feature_incompat = SWAP_LE32(EXT2_FEATURE_INCOMPAT_FILETYPE);
+  sb->feature_ro_compat = SWAP_LE32(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER);
+
+  create_uuid(sb->uuid);
+
+  // TODO If we're called as mke3fs or mkfs.ext3, do a journal.
+
+  //if (strchr(toys.which->name,'3'))
+  //	sb->feature_compat |= SWAP_LE32(EXT3_FEATURE_COMPAT_HAS_JOURNAL);
+}
+
+// Does this group contain a superblock backup (and group descriptor table)?
+static int is_sb_group(uint32_t group)
+{
+  int i;
+
+  // Superblock backups are on groups 0, 1, and powers of 3, 5, and 7.
+  if(!group || group==1) return 1;
+  for (i=3; i<9; i+=2) {
+    int j = i;
+    while (j<group) j*=i;
+    if (j==group) return 1;
+  }
+  return 0;
+}
+
+
+// Number of blocks used in group by optional superblock/group list backup.
+static int group_superblock_overhead(uint32_t group)
+{
+  int used;
+
+  if (!is_sb_group(group)) return 0;
+
+  // How many blocks does the group descriptor table take up?
+  used = TT.groups * sizeof(struct ext2_group);
+  used += TT.blocksize - 1;
+  used /= TT.blocksize;
+  // Plus the superblock itself.
+  used++;
+  // And a corner case.
+  if (!group && TT.blocksize == 1024) used++;
+
+  return used;
+}
+
+// Number of blocks used in group to store superblock/group/inode list
+static int group_overhead(uint32_t group)
+{
+  // Return superblock backup overhead (if any), plus block/inode
+  // allocation bitmaps, plus inode tables.
+  return group_superblock_overhead(group) + 2 + get_inodespg(TT.inodespg)
+        / (TT.blocksize/sizeof(struct ext2_inode));
+}
+
+// In bitmap "array" set "len" bits starting at position "start" (from 0).
+static void bits_set(char *array, int start, int len)
+{
+  while(len) {
+    if ((start&7) || len<8) {
+      array[start/8]|=(1<<(start&7));
+      start++;
+      len--;
+    } else {
+      array[start/8]=255;
+      start+=8;
+      len-=8;
+    }
+  }
+}
+
+// Seek past len bytes (to maintain sparse file), or write zeroes if output
+// not seekable
+static void put_zeroes(int len)
+{
+  if(-1 == lseek(TT.fsfd, len, SEEK_SET)) {
+    memset(toybuf, 0, sizeof(toybuf));
+    while (len) {
+      int out = len > sizeof(toybuf) ? sizeof(toybuf) : len;
+      xwrite(TT.fsfd, toybuf, out);
+      len -= out;
+    }
+  }
+}
+
+// Fill out an inode structure from struct stat info in dirtree.
+static void fill_inode(struct ext2_inode *in, struct dirtree *that)
+{
+  uint32_t fbu[15];
+  int temp;
+
+  file_blocks_used(that->st.st_size, fbu);
+
+  // If that inode needs data blocks allocated to it.
+  if (that->st.st_size) {
+    int i, group = TT.nextblock/TT.blockbits;
+
+    // TODO: teach this about indirect blocks.
+    for (i=0; i<15; i++) {
+      // If we just jumped into a new group, skip group overhead blocks.
+      while (group >= TT.nextgroup)
+        TT.nextblock += group_overhead(TT.nextgroup++);
+    }
+  }
+  // TODO :  S_ISREG/DIR/CHR/BLK/FIFO/LNK/SOCK(m)
+  in->mode = SWAP_LE32(that->st.st_mode);
+
+  in->uid = SWAP_LE16(that->st.st_uid & 0xFFFF);
+  in->uid_high = SWAP_LE16(that->st.st_uid >> 16);
+  in->gid = SWAP_LE16(that->st.st_gid & 0xFFFF);
+  in->gid_high = SWAP_LE16(that->st.st_gid >> 16);
+  in->size = SWAP_LE32(that->st.st_size & 0xFFFFFFFF);
+
+  // Contortions to make the compiler not generate a warning for x>>32
+  // when x is 32 bits.  The optimizer should clean this up.
+  if (sizeof(that->st.st_size) > 4) temp = 32;
+  else temp = 0;
+  if (temp) in->dir_acl = SWAP_LE32(that->st.st_size >> temp);
+
+  in->atime = SWAP_LE32(that->st.st_atime);
+  in->ctime = SWAP_LE32(that->st.st_ctime);
+  in->mtime = SWAP_LE32(that->st.st_mtime);
+
+  in->links_count = SWAP_LE16(that->st.st_nlink);
+  in->blocks = SWAP_LE32(that->st.st_blocks);
+  // in->faddr
+}
+
+// Works like an archiver.
+// The first argument is the name of the file to create.  If it already
+// exists, that size will be used.
+
+void mke2fs_main(void)
+{
+  int i, temp;
+  off_t length;
+  uint32_t usedblocks, usedinodes, dtiblk, dtbblk;
+  struct dirtree *dti, *dtb;
+
+  // Handle command line arguments.
+
+  if (toys.optargs[1]) {
+    sscanf(toys.optargs[1], "%u", &TT.blocks);
+    temp = O_RDWR|O_CREAT;
+  } else temp = O_RDWR;
+  if (!TT.reserved_percent) TT.reserved_percent = 5;
+
+  // TODO: Check if filesystem is mounted here
+
+  // For mke?fs, open file.  For gene?fs, create file.
+  TT.fsfd = xcreate(*toys.optargs, temp, 0777);
+
+  // Determine appropriate block size and block count from file length.
+  // (If no length, default to 4k.  They can override it on the cmdline.)
+
+  length = fdlength(TT.fsfd);
+  if (!TT.blocksize) TT.blocksize = (length && length < 1<<29) ? 1024 : 4096;
+  TT.blockbits = 8*TT.blocksize;
+  if (!TT.blocks) TT.blocks = length/TT.blocksize;
+
+  // Collect gene2fs list or lost+found, calculate requirements.
+
+  if (TT.gendir) {
+    strncpy(toybuf, TT.gendir, sizeof(toybuf));
+    dti = dirtree_read(toybuf, NULL, NULL);
+  } else {
+    dti = xzalloc(sizeof(struct dirtree)+11);
+    strcpy(dti->name, "lost+found");
+    dti->st.st_mode = S_IFDIR|0755;
+    dti->st.st_ctime = dti->st.st_mtime = time(NULL);
+  }
+
+  // Add root directory inode.  This is iterated through for when finding
+  // blocks, but not when finding inodes.  The tree's parent pointers don't
+  // point back into this.
+
+  dtb = xzalloc(sizeof(struct dirtree)+1);
+  dtb->st.st_mode = S_IFDIR|0755;
+  dtb->st.st_ctime = dtb->st.st_mtime = time(NULL);
+  dtb->child = dti;
+
+  // Figure out how much space is used by preset files
+  length = check_treesize(dtb, &(dtb->st.st_size));
+  check_treelinks(dtb);
+
+  // Figure out how many total inodes we need.
+
+  if (!TT.inodes) {
+    if (!TT.bytes_per_inode) TT.bytes_per_inode = 8192;
+    TT.inodes = (TT.blocks * (uint64_t)TT.blocksize) / TT.bytes_per_inode;
+  }
+
+  // If we're generating a filesystem and have no idea how many blocks it
+  // needs, start with a minimal guess, find the overhead of that many
+  // groups, and loop until this is enough groups to store this many blocks.
+  if (!TT.blocks) TT.groups = (TT.treeblocks/TT.blockbits)+1;
+  else TT.groups = div_round_up(TT.blocks, TT.blockbits);
+
+  for (;;) {
+    temp = TT.treeblocks;
+
+    for (i = 0; i<TT.groups; i++) temp += group_overhead(i);
+
+    if (TT.blocks) {
+      if (TT.blocks < temp) error_exit("Not enough space.\n");
+      break;
+    }
+    if (temp <= TT.groups * TT.blockbits) {
+      TT.blocks = temp;
+      break;
+    }
+    TT.groups++;
+  }
+  TT.freeblocks = TT.blocks - temp;
+
+  // Now we know all the TT data, initialize superblock structure.
+
+  init_superblock(&TT.sb);
+
+  // Start writing.  Skip the first 1k to avoid the boot sector (if any).
+  put_zeroes(1024);
+
+  // Loop through block groups, write out each one.
+  dtiblk = dtbblk = usedblocks = usedinodes = 0;
+  for (i=0; i<TT.groups; i++) {
+    struct ext2_inode *in = (struct ext2_inode *)toybuf;
+    uint32_t start, itable, used, end;
+    int j, slot;
+
+    // Where does this group end?
+    end = TT.blockbits;
+    if ((i+1)*TT.blockbits > TT.blocks) end = TT.blocks & (TT.blockbits-1);
+
+    // Blocks used by inode table
+    itable = (TT.inodespg*sizeof(struct ext2_inode))/TT.blocksize;
+
+    // If a superblock goes here, write it out.
+    start = group_superblock_overhead(i);
+    if (start) {
+      struct ext2_group *bg = (struct ext2_group *)toybuf;
+      int treeblocks = TT.treeblocks, treeinodes = TT.treeinodes;
+
+      TT.sb.block_group_nr = SWAP_LE16(i);
+
+      // Write superblock and pad it up to block size
+      xwrite(TT.fsfd, &TT.sb, sizeof(struct ext2_superblock));
+      temp = TT.blocksize - sizeof(struct ext2_superblock);
+      if (!i && TT.blocksize > 1024) temp -= 1024;
+      memset(toybuf, 0, TT.blocksize);
+      xwrite(TT.fsfd, toybuf, temp);
+
+      // Loop through groups to write group descriptor table.
+      for(j=0; j<TT.groups; j++) {
+
+        // Figure out what sector this group starts in.
+        used = group_superblock_overhead(j);
+
+        // Find next array slot in this block (flush block if full).
+        slot = j % (TT.blocksize/sizeof(struct ext2_group));
+        if (!slot) {
+          if (j) xwrite(TT.fsfd, bg, TT.blocksize);
+          memset(bg, 0, TT.blocksize);
+        }
+
+        // How many free inodes in this group?
+        temp = TT.inodespg;
+        if (!i) temp -= INODES_RESERVED;
+        if (temp > treeinodes) {
+          treeinodes -= temp;
+          temp = 0;
+        } else {
+          temp -= treeinodes;
+          treeinodes = 0;
+        }
+        bg[slot].free_inodes_count = SWAP_LE16(temp);
+
+        // How many free blocks in this group?
+        temp = TT.inodespg/(TT.blocksize/sizeof(struct ext2_inode)) + 2;
+        temp = end-used-temp;
+        if (temp > treeblocks) {
+          treeblocks -= temp;
+          temp = 0;
+        } else {
+          temp -= treeblocks;
+          treeblocks = 0;
+        }
+        bg[slot].free_blocks_count = SWAP_LE32(temp);
+
+        // Fill out rest of group structure
+        used += j*TT.blockbits;
+        bg[slot].block_bitmap = SWAP_LE32(used++);
+        bg[slot].inode_bitmap = SWAP_LE32(used++);
+        bg[slot].inode_table = SWAP_LE32(used);
+        bg[slot].used_dirs_count = 0;  // (TODO)
+      }
+      xwrite(TT.fsfd, bg, TT.blocksize);
+    }
+
+    // Now write out stuff that every block group has.
+
+    // Write block usage bitmap
+
+    start += 2 + itable;
+    memset(toybuf, 0, TT.blocksize);
+    bits_set(toybuf, 0, start);
+    bits_set(toybuf, end, TT.blockbits-end);
+    temp = TT.treeblocks - usedblocks;
+    if (temp) {
+      if (end-start > temp) temp = end-start;
+      bits_set(toybuf, start, temp);
+    }
+    xwrite(TT.fsfd, toybuf, TT.blocksize);
+
+    // Write inode bitmap
+    memset(toybuf, 0, TT.blocksize);
+    j = 0;
+    if (!i) bits_set(toybuf, 0, j = INODES_RESERVED);
+    bits_set(toybuf, TT.inodespg, slot = TT.blockbits-TT.inodespg);
+    temp = TT.treeinodes - usedinodes;
+    if (temp) {
+      if (slot-j > temp) temp = slot-j;
+      bits_set(toybuf, j, temp);
+    }
+    xwrite(TT.fsfd, toybuf, TT.blocksize);
+
+    // Write inode table for this group (TODO)
+    for (j = 0; j<TT.inodespg; j++) {
+      slot = j % (TT.blocksize/sizeof(struct ext2_inode));
+      if (!slot) {
+        if (j) xwrite(TT.fsfd, in, TT.blocksize);
+        memset(in, 0, TT.blocksize);
+      }
+      if (!i && j<INODES_RESERVED) {
+        // Write root inode
+        if (j == 2) fill_inode(in+slot, dtb);
+      } else if (dti) {
+        fill_inode(in+slot, dti);
+        dti = treenext(dti);
+      }
+    }
+    xwrite(TT.fsfd, in, TT.blocksize);
+
+    while (dtb) {
+      // TODO write index data block
+      // TODO write root directory data block
+      // TODO write directory data block
+      // TODO write file data block
+      put_zeroes(TT.blocksize);
+      start++;
+      if (start == end) break;
+    }
+    // Write data blocks (TODO)
+    put_zeroes((end-start) * TT.blocksize);
+  }
+}
diff --git a/toys/pending/sed.c b/toys/pending/sed.c
new file mode 100644
index 00000000..15099cc6
--- /dev/null
+++ b/toys/pending/sed.c
@@ -0,0 +1,131 @@
+/* sed.c - Stream editor.
+ *
+ * Copyright 2012 Rob Landley <rob@landley.net>
+ *
+ * See http://opengroup.org/onlinepubs/9699919799/utilities/sed.c
+
+USE_SED(NEWTOY(sed, "irne*", TOYFLAG_BIN))
+
+config SED
+  bool "sed"
+  default n
+  help
+    usage: sed [-irn] {command | [-e command]...} [FILE...]
+
+    Stream EDitor, transforms text by appling script of command to each line
+    of input.
+
+    -e  Add expression to the command script (if no -e, use first argument)
+    -i	Modify file in place
+    -n  No default output (p commands only)
+    -r  Use extended regular expression syntex
+*/
+
+#define FOR_sed
+#include "toys.h"
+#include "lib/xregcomp.h"
+
+GLOBALS(
+  struct arg_list *scripts;
+  struct double_list *commands;
+
+  void *parsed;
+)
+
+// Digested version of what sed commands can actually tell use to do.
+
+
+struct sed_command {
+  // double_list compatibility (easier to create in-order)
+  struct sed_command *next, *prev;
+
+  // data string for (saicytb)
+  char c, *data;
+  // Regexes for s/match/data/ and /begin/,/end/command
+  regex_t *match, *begin, *end;
+  // For numeric ranges ala 10,20command
+  long lstart, lstop;
+  // Which match to replace, 0 for all. s and w commands can write to a file
+  int which, outfd;
+};
+
+//  Space. Space. Gotta get past space. Spaaaaaaaace! (But not newline.)
+void spaceorb(char **s)
+{
+  while (**s == ' ' || **s == '\t') *s++;
+}
+
+void parse_scripts(void)
+{
+  struct sed_command *commands = 0;
+  struct arg_list *script;
+  int which = 0;
+  long l;
+
+  for (script = TT.scripts; *script; script = script->next) {
+    char *str = script->arg, *s;
+    struct sed_command *cmd;
+
+    which++;
+    for (i=1;;) {
+      if (!*str) break;
+
+      cmd = xzalloc(sizeof(struct sed_command));
+
+      // Identify prefix
+      for (;;) {
+        long l;
+
+        spaceorb(&str);
+        if (*str == '$') {
+          l = -1;
+          str++;
+        } else if (isdigit(*str)) l = strtol(str, &str, 10);
+        else if (!cmd->lstart) break;
+        else goto parse_fail;
+
+        spaceorb(&str);
+        if (!cmd->lstart) {
+          if (!l) goto parse_fail;
+          cmd->lstart = l;
+          if (*str != ',') break;
+          str++;
+          continue;
+        }
+        cmd->lstop = l;
+        break;
+      } else if (*str == '/') {
+        printf("regex\n");
+      }
+      l = stridx("{bcdDgGhHlnNpPstwxyrqia= \t#:}", *str);
+      if (l == -1) goto parse_fail;
+
+
+    }
+  }
+
+  return;
+
+parse_fail:
+  error_exit("bad expression %d@%d: %s", which, i, script->arg+i);
+}
+
+void sed_main(void)
+{
+  char **files=toys.optargs;
+
+  // If no -e, use first argument
+  if (!TT.scripts) {
+    if (!*files) error_exit("Need script");
+    (TT.scripts=xzalloc(sizeof(struct arg_list)))->arg=*(files++);
+  }
+
+
+  {
+    struct arg_list *test;
+
+    for (test = TT.commands; test; test = test->next)
+      dprintf(2,"command=%s\n",test->arg);
+    while (*files) dprintf(2,"file=%s\n", *(files++));
+  }
+}
diff --git a/toys/pending/sh.c b/toys/pending/sh.c
new file mode 100644
index 00000000..2f09f63b
--- /dev/null
+++ b/toys/pending/sh.c
@@ -0,0 +1,392 @@
+/* sh.c - toybox shell
+ *
+ * Copyright 2006 Rob Landley <rob@landley.net>
+ *
+ * The POSIX-2008/SUSv4 spec for this is at:
+ * http://opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html
+ * and http://opengroup.org/onlinepubs/9699919799/utilities/sh.html
+ *
+ * The first link describes the following shell builtins:
+ *
+ *   break colon continue dot eval exec exit export readonly return set shift
+ *   times trap unset
+ *
+ * The second link (the utilities directory) also contains specs for the
+ * following shell builtins:
+ *
+ *   alias bg cd command fc fg getopts hash jobs kill read type ulimit
+ *   umask unalias wait
+ *
+ * Things like the bash man page are good to read too.
+ *
+ * TODO: // Handle embedded NUL bytes in the command line.
+
+USE_SH(NEWTOY(cd, NULL, TOYFLAG_NOFORK))
+USE_SH(NEWTOY(exit, NULL, TOYFLAG_NOFORK))
+
+USE_SH(NEWTOY(sh, "c:i", TOYFLAG_BIN))
+USE_SH(OLDTOY(toysh, sh, "c:i", TOYFLAG_BIN))
+
+config SH
+  bool "sh (toysh)"
+  default n
+  help
+    usage: sh [-c command] [script]
+
+    Command shell.  Runs a shell script, or reads input interactively
+    and responds to it.
+
+    -c	command line to execute
+
+config SH_TTY
+  bool "Interactive shell (terminal control)"
+  default n
+  depends on SH
+  help
+    Add terminal control to toysh.  This is necessary for interactive use,
+    so the shell isn't killed by CTRL-C.
+
+config SH_PROFILE
+  bool "Profile support"
+  default n
+  depends on SH_TTY
+  help
+    Read /etc/profile and ~/.profile when running interactively.
+
+    Also enables the built-in command "source".
+
+config SH_JOBCTL
+  bool "Job Control (fg, bg, jobs)"
+  default n
+  depends on SH_TTY
+  help
+    Add job control to toysh.  This lets toysh handle CTRL-Z, and enables
+    the built-in commands "fg", "bg", and "jobs".
+
+    With pipe support, enable use of "&" to run background processes.
+
+config SH_FLOWCTL
+  bool "Flow control (if, while, for, functions)"
+  default n
+  depends on SH
+  help
+    Add flow control to toysh.  This enables the if/then/else/fi,
+    while/do/done, and for/do/done constructs.
+
+    With pipe support, this enables the ability to define functions
+    using the "function name" or "name()" syntax, plus curly brackets
+    "{ }" to group commands.
+
+config SH_QUOTES
+  bool "Smarter argument parsing (quotes)"
+  default n
+  depends on SH
+  help
+    Add support for parsing "" and '' style quotes to the toysh command
+    parser, with lets arguments have spaces in them.
+
+config SH_WILDCARDS
+  bool "Wildcards ( ?*{,} )"
+  default n
+  depends on SH_QUOTES
+  help
+    Expand wildcards in argument names, ala "ls -l *.t?z" and
+    "rm subdir/{one,two,three}.txt".
+
+config SH_PROCARGS
+  bool "Executable arguments ( `` and $() )"
+  default n
+  depends on SH_QUOTES
+  help
+    Add support for executing arguments contianing $() and ``, using
+    the output of the command as the new argument value(s).
+
+    (Bash calls this "command substitution".)
+
+config SH_ENVVARS
+  bool "Environment variable support"
+  default n
+  depends on SH_QUOTES
+  help
+    Substitute environment variable values for $VARNAME or ${VARNAME},
+    and enable the built-in command "export".
+
+config SH_LOCALS
+  bool "Local variables"
+  default n
+  depends on SH_ENVVARS
+  help
+    Support for local variables, fancy prompts ($PS1), the "set" command,
+    and $?.
+
+config SH_ARRAYS
+  bool "Array variables"
+  default n
+  depends on SH_LOCALS
+  help
+    Support for ${blah[blah]} style array variables.
+
+config SH_PIPES
+  bool "Pipes and redirects ( | > >> < << & && | || () ; )"
+  default n
+  depends on SH
+  help
+    Support multiple commands on the same command line.  This includes
+    | pipes, > >> < redirects, << here documents, || && conditional
+    execution, () subshells, ; sequential execution, and (with job
+    control) & background processes.
+
+config SH_BUILTINS
+  bool "Builtin commands"
+  default n
+  depends on SH
+  help
+    Adds the commands exec, fg, bg, help, jobs, pwd, export, source, set,
+    unset, read, alias.
+
+config EXIT
+  bool
+  default n
+  depends on SH
+  help
+    usage: exit [status]
+
+    Exit shell.  If no return value supplied on command line, use value
+    of most recent command, or 0 if none.
+
+config CD
+  bool
+  default n
+  depends on SH
+  help
+    usage: cd [path]
+
+    Change current directory.  With no arguments, go to $HOME.
+
+config CD_P
+  bool # "-P support for cd"
+  default n
+  depends on SH
+  help
+    usage: cd [-PL]
+
+    -P    Physical path: resolve symlinks in path.
+    -L    Cancel previous -P and restore default behavior.
+*/
+
+#define FOR_sh
+#include "toys.h"
+
+GLOBALS(
+  char *command;
+)
+
+// A single executable, its arguments, and other information we know about it.
+#define SH_FLAG_EXIT    1
+#define SH_FLAG_SUSPEND 2
+#define SH_FLAG_PIPE    4
+#define SH_FLAG_AND     8
+#define SH_FLAG_OR      16
+#define SH_FLAG_AMP     32
+#define SH_FLAG_SEMI    64
+#define SH_FLAG_PAREN   128
+
+// What we know about a single process.
+struct command {
+  struct command *next;
+  int flags;              // exit, suspend, && ||
+  int pid;                // pid (or exit code)
+  int argc;
+  char *argv[0];
+};
+
+// A collection of processes piped into/waiting on each other.
+struct pipeline {
+  struct pipeline *next;
+  int job_id;
+  struct command *cmd;
+  char *cmdline;         // Unparsed line for display purposes
+  int cmdlinelen;        // How long is cmdline?
+};
+
+// Parse one word from the command line, appending one or more argv[] entries
+// to struct command.  Handles environment variable substitution and
+// substrings.  Returns pointer to next used byte, or NULL if it
+// hit an ending token.
+static char *parse_word(char *start, struct command **cmd)
+{
+  char *end;
+
+  // Detect end of line (and truncate line at comment)
+  if (CFG_SH_PIPES && strchr("><&|(;", *start)) return 0;
+
+  // Grab next word.  (Add dequote and envvar logic here)
+  end = start;
+  while (*end && !isspace(*end)) end++;
+  (*cmd)->argv[(*cmd)->argc++] = xstrndup(start, end-start);
+
+  // Allocate more space if there's no room for NULL terminator.
+
+  if (!((*cmd)->argc & 7))
+    *cmd=xrealloc(*cmd,
+        sizeof(struct command) + ((*cmd)->argc+8)*sizeof(char *));
+  (*cmd)->argv[(*cmd)->argc] = 0;
+  return end;
+}
+
+// Parse a line of text into a pipeline.
+// Returns a pointer to the next line.
+
+static char *parse_pipeline(char *cmdline, struct pipeline *line)
+{
+  struct command **cmd = &(line->cmd);
+  char *start = line->cmdline = cmdline;
+
+  if (!cmdline) return 0;
+
+  if (CFG_SH_JOBCTL) line->cmdline = cmdline;
+
+  // Parse command into argv[]
+  for (;;) {
+    char *end;
+
+    // Skip leading whitespace and detect end of line.
+    while (isspace(*start)) start++;
+    if (!*start || *start=='#') {
+      if (CFG_SH_JOBCTL) line->cmdlinelen = start-cmdline;
+      return 0;
+    }
+
+    // Allocate next command structure if necessary
+    if (!*cmd) *cmd = xzalloc(sizeof(struct command)+8*sizeof(char *));
+
+    // Parse next argument and add the results to argv[]
+    end = parse_word(start, cmd);
+
+    // If we hit the end of this command, how did it end?
+    if (!end) {
+      if (CFG_SH_PIPES && *start) {
+        if (*start==';') {
+          start++;
+          break;
+        }
+        // handle | & < > >> << || &&
+      }
+      break;
+    }
+    start = end;
+  }
+
+  if (CFG_SH_JOBCTL) line->cmdlinelen = start-cmdline;
+
+  return start;
+}
+
+// Execute the commands in a pipeline
+static void run_pipeline(struct pipeline *line)
+{
+  struct toy_list *tl;
+  struct command *cmd = line->cmd;
+  if (!cmd || !cmd->argc) return;
+
+  tl = toy_find(cmd->argv[0]);
+  // Is this command a builtin that should run in this process?
+  if (tl && (tl->flags & TOYFLAG_NOFORK)) {
+    struct toy_context temp;
+    jmp_buf rebound;
+
+    // This fakes lots of what toybox_main() does.
+    memcpy(&temp, &toys, sizeof(struct toy_context));
+    memset(&toys, 0, sizeof(struct toy_context));
+
+    if (!setjmp(rebound)) {
+      toys.rebound = rebound;
+      toy_init(tl, cmd->argv);
+      tl->toy_main();
+    }
+    cmd->pid = toys.exitval;
+    if (toys.optargs != toys.argv+1) free(toys.optargs);
+    if (toys.old_umask) umask(toys.old_umask);
+    memcpy(&toys, &temp, sizeof(struct toy_context));
+  } else {
+    int status;
+
+    cmd->pid = vfork();
+    if (!cmd->pid) xexec(cmd->argv);
+    else waitpid(cmd->pid, &status, 0);
+
+    if (CFG_SH_FLOWCTL || CFG_SH_PIPES) {
+      if (WIFEXITED(status)) cmd->pid = WEXITSTATUS(status);
+      if (WIFSIGNALED(status)) cmd->pid = WTERMSIG(status);
+    }
+  }
+
+  return;
+}
+
+// Free the contents of a command structure
+static void free_cmd(void *data)
+{
+  struct command *cmd=(struct command *)data;
+
+  while(cmd->argc) free(cmd->argv[--cmd->argc]);
+}
+
+
+// Parse a command line and do what it says to do.
+static void handle(char *command)
+{
+  struct pipeline line;
+  char *start = command;
+
+  // Loop through commands in this line
+
+  for (;;) {
+
+    // Parse a group of connected commands
+
+    memset(&line,0,sizeof(struct pipeline));
+    start = parse_pipeline(start, &line);
+    if (!line.cmd) break;
+
+    // Run those commands
+
+    run_pipeline(&line);
+    llist_traverse(line.cmd, free_cmd);
+  }
+}
+
+void cd_main(void)
+{
+  char *dest = *toys.optargs ? *toys.optargs : getenv("HOME");
+  xchdir(dest);
+}
+
+void exit_main(void)
+{
+  exit(*toys.optargs ? atoi(*toys.optargs) : 0);
+}
+
+void sh_main(void)
+{
+  FILE *f;
+
+  // Set up signal handlers and grab control of this tty.
+  if (CFG_SH_TTY) {
+    if (isatty(0)) toys.optflags |= 1;
+  }
+  f = *toys.optargs ? xfopen(*toys.optargs, "r") : NULL;
+  if (TT.command) handle(TT.command);
+  else {
+    size_t cmdlen = 0;
+    for (;;) {
+      char *command = 0;
+      if (!f) xputc('$');
+      if (1 > getline(&command, &cmdlen, f ? f : stdin)) break;
+      handle(command);
+      free(command);
+    }
+  }
+
+  toys.exitval = 1;
+}