cmd/INIT/mamake.c

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1990-2011 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                 Eclipse Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*          http://www.eclipse.org/org/documents/epl-v10.html           *
*         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                 Glenn Fowler <gsf@research.att.com>                  *
*                                                                      *
***********************************************************************/
#pragma prototyped

/*
 * mamake -- MAM make
 *
 * coded for portability
 */

static char id[] = "\n@(#)$Id: mamake (AT&T Research) 2011-08-31 $\0\n";

#if _PACKAGE_ast

#include <ast.h>
#include <error.h>

static const char usage[] =
"[-?\n@(#)$Id: mamake (AT&T Research) 2011-08-31 $\n]"
USAGE_LICENSE
"[+NAME?mamake - make abstract machine make]"
"[+DESCRIPTION?\bmamake\b reads \amake abstract machine\a target and"
"   prerequisite file descriptions from a mamfile (see \b-f\b) and executes"
"   actions to update targets that are older than their prerequisites."
"   Mamfiles are generated by the \b--mam\b option of \bnmake\b(1) and"
"   \bgmake\b(1) and are portable to environments that only have"
"   \bsh\b(1) and \bcc\b(1).]"
"[+?In practice \bmamake\b is used to bootstrap build \bnmake\b(1) and"
"   \bksh\b(1) in new environments. Mamfiles are used rather than"
"   old-\bmake\b makefiles because some features are not reliably supported"
"   across all \bmake\b variants:]{"
"       [+action execution?Multi-line actions are executed as a"
"           unit by \b$SHELL\b. There are some shell constructs"
"           that cannot be expressed in an old-\bmake\b makefile.]"
"       [+viewpathing?\bVPATH\b is properly interpreted. This allows"
"           source to be separate from generated files.]"
"       [+recursion?Ordered subdirectory recursion over unrelated"
"           makefiles.]"
"   }"
"[+?\bmamprobe\b(1) is called to probe and generate system specific variable"
"   definitions. The probe information is regenerated when it is older"
"   than the \bmamprobe\b command.]"
"[+?For compatibility with \bnmake\b(1) the \b-K\b option and the"
"   \brecurse\b and \bcc-*\b command line targets are ignored.]"
"[e:?Explain reason for triggering action. Ignored if -F is on.]"
"[f:?Read \afile\a instead of the default.]:[file:=Mamfile]"
"[i:?Ignore action errors.]"
"[k:?Continue after error with sibling prerequisites.]"
"[n:?Print actions but do not execute. Recursion actions (see \b-r\b) are still"
"   executed. Use \b-N\b to disable recursion actions too.]"
"[r:?Recursively make leaf directories matching \apattern\a. Only leaf"
"   directories containing a makefile named \bNmakefile\b, \bnmakefile\b,"
"   \bMakefile\b or \bmakefile\b are considered. The first makefile"
"   found in each leaf directory is scanned for leaf directory"
"   prerequisites; the recusion order is determined by a topological sort"
"   of these prerequisites.]:[pattern]"
"[C:?Do all work in \adirectory\a. All messages will mention"
"   \adirectory\a.]:[directory]"
"[D:?Set the debug trace level to \alevel\a. Higher levels produce more"
"   output.]#[level]"
"[F:?Force all targets to be out of date.]"
"[K:?Ignored.]"
"[N:?Like \b-n\b but recursion actions (see \b-r\b) are also disabled.]"
"[V:?Print the program version and exit.]"
"[G:debug-symbols?Compile and link with debugging symbol options enabled.]"
"[S:strip-symbols?Strip link-time static symbols from executables.]"

"\n"
"\n[ target ... ] [ name=value ... ]\n"
"\n"

"[+SEE ALSO?\bgmake\b(1), \bmake\b(1), \bmamprobe\b(1),"
"   \bnmake\b(1), \bsh\b(1)]"
;

#else

#define elementsof(x)   (sizeof(x)/sizeof(x[0]))
#define newof(p,t,n,x)  ((p)?(t*)realloc((char*)(p),sizeof(t)*(n)+(x)):(t*)calloc(1,sizeof(t)*(n)+(x)))

#define NiL     ((char*)0)

#endif

#include <stdio.h>
#include <unistd.h>
#include <ctype.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <time.h>

#if !_PACKAGE_ast && defined(__STDC__)
#include <stdlib.h>
#include <string.h>
#endif

#define delimiter(c)    ((c)==' '||(c)=='\t'||(c)=='\n'||(c)==';'||(c)=='('||(c)==')'||(c)=='`'||(c)=='|'||(c)=='&'||(c)=='=')

#define add(b,c)    (((b)->nxt >= (b)->end) ? append(b, "") : NiL, *(b)->nxt++ = (c))
#define get(b)      ((b)->nxt-(b)->buf)
#define set(b,o)    ((b)->nxt=(b)->buf+(o))
#define use(b)      (*(b)->nxt=0,(b)->nxt=(b)->buf)

#define CHUNK       1024
#define KEY(a,b,c,d)    ((((unsigned long)(a))<<15)|(((unsigned long)(b))<<10)|(((unsigned long)(c))<<5)|(((unsigned long)(d))))
#define NOW     ((unsigned long)time((time_t*)0))
#define ROTATE(p,l,r,t) ((t)=(p)->l,(p)->l=(t)->r,(t)->r=(p),(p)=(t))

#define RULE_active 0x0001      /* active target        */
#define RULE_dontcare   0x0002      /* ok if not found      */
#define RULE_error  0x0004      /* not found or not generated   */
#define RULE_exists 0x0008      /* target file exists       */
#define RULE_generated  0x0010      /* generated target     */
#define RULE_ignore 0x0020      /* ignore time          */
#define RULE_implicit   0x0040      /* implicit prerequisite    */
#define RULE_made   0x0080      /* already made         */
#define RULE_virtual    0x0100      /* not a file           */

#define STREAM_KEEP 0x0001      /* don't fclose() on pop()  */
#define STREAM_MUST 0x0002      /* push() file must exist   */
#define STREAM_PIPE 0x0004      /* pclose() on pop()        */

#ifndef S_IXUSR
#define S_IXUSR     0100        /* owner execute permission */
#endif
#ifndef S_IXGRP
#define S_IXGRP     0010        /* group execute permission */
#endif
#ifndef S_IXOTH
#define S_IXOTH     0001        /* other execute permission */
#endif

struct Rule_s;

typedef struct stat Stat_t;
typedef FILE Stdio_t;

typedef struct Buf_s            /* buffer stream        */
{
    struct Buf_s*   old;        /* next dropped buffer      */
    char*       end;        /* 1 past end of buffer     */
    char*       nxt;        /* next char to add     */
    char*       buf;        /* buffer space         */
} Buf_t;

typedef struct Dict_item_s      /* dictionary item      */
{
    struct Dict_item_s* left;   /* left child           */
    struct Dict_item_s* right;  /* right child          */
    void*           value;  /* user defined value       */
    char            name[1];/* 0 terminated name        */
} Dict_item_t;

typedef struct Dict_s           /* dictionary handle        */
{
    Dict_item_t*    root;       /* root item            */
} Dict_t;

typedef struct List_s           /* Rule_t list          */
{
    struct List_s*  next;       /* next in list         */
    struct Rule_s*  rule;       /* list item            */
} List_t;

typedef struct Rule_s           /* rule item            */
{
    char*       name;       /* unbound name         */
    char*       path;       /* bound path           */
    List_t*     prereqs;    /* prerequisites        */
    struct Rule_s*  leaf;       /* recursion leaf alias     */
    int     flags;      /* RULE_* flags         */
    int     making;     /* currently make()ing      */
    unsigned long   time;       /* modification time        */
} Rule_t;

typedef struct Stream_s         /* input file stream stack  */
{
    Stdio_t*    fp;     /* read stream          */
    char*       file;       /* stream path          */
    unsigned long   line;       /* stream line          */
    int     flags;      /* stream flags         */
} Stream_t;

typedef struct View_s           /* viewpath level       */
{
    struct View_s*  next;       /* next level in viewpath   */
    int     node;       /* viewpath node path length    */
    char        dir[1];     /* viewpath level dir prefix    */
} View_t;

static struct               /* program state        */
{
    Buf_t*      buf;        /* work buffer          */
    Buf_t*      old;        /* dropped buffers      */
    Buf_t*      opt;        /* option buffer        */

    Dict_t*     leaf;       /* recursion leaf dictionary    */
    Dict_t*     libs;       /* library dictionary       */
    Dict_t*     rules;      /* rule dictionary      */
    Dict_t*     vars;       /* variable dictionary      */

    View_t*     view;       /* viewpath levels      */

    char*       directory;  /* work in this directory   */
    char*       id;     /* command name         */
    char*       file;       /* first input file     */
    char*       pwd;        /* current directory        */
    char*       recurse;    /* recursion pattern        */
    char*       shell;      /* ${SHELL}         */

    int     active;     /* targets currently active */
    int     debug;      /* negative of debug level  */
    int     errors;     /* some error(s) occurred   */
    int     exec;       /* execute actions      */
    int     explain;    /* explain actions      */
    int     force;      /* all targets out of date  */
    int     ignore;     /* ignore command errors    */
    int     indent;     /* debug indent         */
    int     keepgoing;  /* do siblings on error     */
    int     never;      /* never execute        */
    int     peek;       /* next line already in input   */
    int     probed;     /* probe already done       */
    int     verified;   /* don't bother with verify()   */

    Stream_t    streams[4]; /* input file stream stack  */
    Stream_t*   sp;     /* input stream stack pointer   */

    char        input[8*CHUNK]; /* input buffer         */
} state;

static unsigned long    make(Rule_t*);

static char     mamfile[] = "Mamfile";
static char     sh[] = "/bin/sh";

extern char**       environ;

#if !_PACKAGE_ast

#if defined(NeXT) || defined(__NeXT)
#define getcwd(a,b) getwd(a)
#endif

/*
 * emit usage message and exit
 */

static void
usage()
{
    fprintf(stderr, "Usage: %s [-iknFKNV] [-f mamfile] [-r pattern] [-C directory] [-D level] [target ...] [name=value ...]\n", state.id);
    exit(2);
}

#endif

/*
 * output error message identification
 */

static void
identify(Stdio_t* sp)
{
    if (state.directory)
        fprintf(sp, "%s [%s]: ", state.id, state.directory);
    else
        fprintf(sp, "%s: ", state.id);
}

/*
 * emit error message
 * level:
 *  <0  debug
 *   0  info
 *   1  warning
 *   2  error
 *  >2  exit(level-2)
 */

static void
report(int level, char* text, char* item, unsigned long stamp)
{
    int i;

    if (level >= state.debug)
    {
        if (level)
            identify(stderr);
        if (level < 0)
        {
            fprintf(stderr, "debug%d: ", level);
            for (i = 1; i < state.indent; i++)
                fprintf(stderr, "  ");
        }
        else
        {
            if (state.sp && state.sp->line)
            {
                if (state.sp->file)
                    fprintf(stderr, "%s: ", state.sp->file);
                fprintf(stderr, "%ld: ", state.sp->line);
            }
            if (level == 1)
                fprintf(stderr, "warning: ");
            else if (level > 1)
                state.errors = 1;
        }
        if (item)
            fprintf(stderr, "%s: ", item);
        fprintf(stderr, "%s", text);
        if (stamp && state.debug <= -2)
            fprintf(stderr, " %10lu", stamp);
        fprintf(stderr, "\n");
        if (level > 2)
            exit(level - 2);
    }
}

/*
 * don't know how to make or exit code making
 */

static void
dont(Rule_t* r, int code, int keepgoing)
{
    identify(stderr);
    if (!code)
        fprintf(stderr, "don't know how to make %s\n", r->name);
    else
    {
        fprintf(stderr, "*** exit code %d making %s%s\n", code, r->name, state.ignore ? " ignored" : "");
        unlink(r->name);
        if (state.ignore)
            return;
    }
    if (!keepgoing)
        exit(1);
    state.errors++;
    r->flags |= RULE_error;
}

/*
 * local strrchr()
 */

static char*
last(register char* s, register int c)
{
    register char*  r = 0;

    for (r = 0; *s; s++)
        if (*s == c)
            r = s;
    return r;
}

/*
 * open a buffer stream
 */

static Buf_t*
buffer(void)
{
    register Buf_t* buf;

    if (buf = state.old)
        state.old = state.old->old;
    else if (!(buf = newof(0, Buf_t, 1, 0)) || !(buf->buf = newof(0, char, CHUNK, 0)))
        report(3, "out of space [buffer]", NiL, (unsigned long)0);
    buf->end = buf->buf + CHUNK;
    buf->nxt = buf->buf;
    return buf;
}

/*
 * close a buffer stream
 */

static void
drop(Buf_t* buf)
{
    buf->old = state.old;
    state.old = buf;
}

/*
 * append str length n to buffer and return the buffer base
 */

static char*
appendn(Buf_t* buf, char* str, int n)
{
    int m;
    int i;

    if ((n + 1) >= (buf->end - buf->nxt))
    {
        i = buf->nxt - buf->buf;
        m = (((buf->end - buf->buf) + n + CHUNK + 1) / CHUNK) * CHUNK;
        if (!(buf->buf = newof(buf->buf, char, m, 0)))
            report(3, "out of space [buffer resize]", NiL, (unsigned long)0);
        buf->end = buf->buf + m;
        buf->nxt = buf->buf + i;
    }
    memcpy(buf->nxt, str, n + 1);
    buf->nxt += n;
    return buf->buf;
}

/*
 * append str to buffer and return the buffer base
 * if str==0 then next pointer reset to base
 */

static char*
append(Buf_t* buf, char* str)
{
    if (str)
        return appendn(buf, str, strlen(str));
    buf->nxt = buf->buf;
    return buf->buf;
}

/*
 * allocate space for s and return the copy
 */

static char*
duplicate(char* s)
{
    char*   t;
    int n;

    n = strlen(s);
    if (!(t = newof(0, char, n, 1)))
        report(3, "out of space [duplicate]", s, (unsigned long)0);
    strcpy(t, s);
    return t;
}

/*
 * open a new dictionary
 */

static Dict_t*
dictionary(void)
{
    Dict_t* dict;

    if (!(dict = newof(0, Dict_t, 1, 0)))
        report(3, "out of space [dictionary]", NiL, (unsigned long)0);
    return dict;
}

/*
 * return the value for item name in dictionary dict
 * if value!=0 then name entry value is created if necessary and set
 * uses top-down splaying (ala Tarjan and Sleator)
 */

static void*
search(register Dict_t* dict, char* name, void* value)
{
    register int        cmp;
    register Dict_item_t*   root;
    register Dict_item_t*   t;
    register Dict_item_t*   left;
    register Dict_item_t*   right;
    register Dict_item_t*   lroot;
    register Dict_item_t*   rroot;

    root = dict->root;
    left = right = lroot = rroot = 0;
    while (root)
    {
        if (!(cmp = strcmp(name, root->name)))
            break;
        else if (cmp < 0)
        {
            if (root->left && (cmp = strcmp(name, root->left->name)) <= 0)
            {
                ROTATE(root, left, right, t);
                if (!cmp)
                    break;
            }
            if (right)
                right->left = root;
            else
                rroot = root;
            right = root;
            root = root->left;
            right->left = 0;
        }
        else
        {
            if (root->right && (cmp = strcmp(name, root->right->name)) >= 0)
            {
                ROTATE(root, right, left, t);
                if (!cmp)
                    break;
            }
            if (left)
                left->right = root;
            else
                lroot = root;
            left = root;
            root = root->right;
            left->right = 0;
        }
    }
    if (root)
    {
        if (right)
            right->left = root->right;
        else
            rroot = root->right;
        if (left)
            left->right = root->left;
        else
            lroot = root->left;
    }
    else if (value)
    {
        if (!(root = newof(0, Dict_item_t, 1, strlen(name))))
            report(3, "out of space [dictionary]", name, (unsigned long)0);
        strcpy(root->name, name);
    }
    if (root)
    {
        if (value)
            root->value = value;
        root->left = lroot;
        root->right = rroot;
        dict->root = root;
        return value ? (void*)root->name : root->value;
    }
    if (left)
    {
        left->right = rroot;
        dict->root = lroot;
    }
    else if (right)
    {
        right->left = lroot;
        dict->root = rroot;
    }
    return 0;
}

/*
 * low level for walk()
 */

static int
apply(Dict_t* dict, Dict_item_t* item, int (*func)(Dict_item_t*, void*), void* handle)
{
    register Dict_item_t*   right;

    do
    {
        right = item->right;
        if (item->left && apply(dict, item->left, func, handle))
            return -1;
        if ((*func)(item, handle))
            return -1;
    } while (item = right);
    return 0;
}

/*
 * apply func to each dictionary item
 */

static int
walk(Dict_t* dict, int (*func)(Dict_item_t*, void*), void* handle)
{
    return dict->root ? apply(dict, dict->root, func, handle) : 0;
}

/*
 * return a rule pointer for name
 */

static Rule_t*
rule(char* name)
{
    Rule_t* r;

    if (!(r = (Rule_t*)search(state.rules, name, NiL)))
    {
        if (!(r = newof(0, Rule_t, 1, 0)))
            report(3, "out of space [rule]", name, (unsigned long)0);
        r->name = (char*)search(state.rules, name, (void*)r);
    }
    return r;
}

/*
 * prepend p onto rule r prereqs
 */

static void
cons(Rule_t* r, Rule_t* p)
{
    register List_t*    x;

    for (x = r->prereqs; x && x->rule != p; x = x->next);
    if (!x)
    {
        if (!(x = newof(0, List_t, 1, 0)))
            report(3, "out of space [list]", r->name, (unsigned long)0);
        x->rule = p;
        x->next = r->prereqs;
        r->prereqs = x;
    }
}

/*
 * initialize the viewpath
 */

static void
view(void)
{
    register char*      s;
    register char*      t;
    register char*      p;
    register View_t*    vp;

    View_t*         zp;
    int         c;
    int         n;

    Stat_t          st;
    Stat_t          ts;

    char            buf[CHUNK];

    if (stat(".", &st))
        report(3, "cannot stat", ".", (unsigned long)0);
    if ((s = (char*)search(state.vars, "PWD", NiL)) && !stat(s, &ts) &&
        ts.st_dev == st.st_dev && ts.st_ino == st.st_ino)
        state.pwd = s;
    if (!state.pwd)
    {
        if (!getcwd(buf, sizeof(buf) - 1))
            report(3, "cannot determine PWD", NiL, (unsigned long)0);
        state.pwd = duplicate(buf);
        search(state.vars, "PWD", state.pwd);
    }
    if ((s = (char*)search(state.vars, "VPATH", NiL)) && *s)
    {
        zp = 0;
        for (;;)
        {
            for (t = s; *t && *t != ':'; t++);
            if (c = *t)
                *t = 0;
            if (!state.view)
            {
                /*
                 * determine the viewpath offset
                 */

                if (stat(s, &st))
                    report(3, "cannot stat top view", s, (unsigned long)0);
                if (stat(state.pwd, &ts))
                    report(3, "cannot stat", state.pwd, (unsigned long)0);
                if (ts.st_dev == st.st_dev && ts.st_ino == st.st_ino)
                    p = ".";
                else
                {
                    p = state.pwd + strlen(state.pwd);
                    while (p > state.pwd)
                        if (*--p == '/')
                        {
                            if (p == state.pwd)
                                report(3, ". not under VPATH", s, (unsigned long)0);
                            *p = 0;
                            if (stat(state.pwd, &ts))
                                report(3, "cannot stat", state.pwd, (unsigned long)0);
                            *p = '/';
                            if (ts.st_dev == st.st_dev && ts.st_ino == st.st_ino)
                            {
                                p++;
                                break;
                            }
                        }
                    if (p <= state.pwd)
                        report(3, "cannot determine viewpath offset", s, (unsigned long)0);
                }
            }
            n = strlen(s);
            if (!(vp = newof(0, View_t, 1, strlen(p) + n + 1)))
                report(3, "out of space [view]", s, (unsigned long)0);
            vp->node = n + 1;
            strcpy(vp->dir, s);
            *(vp->dir + n) = '/';
            strcpy(vp->dir + n + 1, p);
            report(-4, vp->dir, "view", (unsigned long)0);
            if (!state.view)
                state.view = zp = vp;
            else
                zp = zp->next = vp;
            if (!c)
                break;
            *t++ = c;
            s = t;
        }
    }
}

/*
 * return next '?' or '}' in nested '}'
 */

static char*
cond(register char* s)
{
    register int    n;

    if (*s == '?')
        s++;
    n = 0;
    for (;;)
    {
        switch (*s++)
        {
        case 0:
            break;
        case '{':
            n++;
            continue;
        case '}':
            if (!n--)
                break;
            continue;
        case '?':
            if (!n)
                break;
            continue;
        default:
            continue;
        }
        break;
    }
    return s - 1;
}

/*
 * expand var refs from s into buf
 */

static void
substitute(Buf_t* buf, register char* s)
{
    register char*  t;
    register char*  v;
    register char*  q;
    register char*  b;
    register int    c;
    register int    n;
    int     a = 0;
    int     i;

    while (c = *s++)
    {
        if (c == '$' && *s == '{')
        {
            b = s - 1;
            i = 1;
            for (n = *(t = ++s) == '-' ? 0 : '-'; (c = *s) && c != '?' && c != '+' && c != n && c != ':' && c != '=' && c != '[' && c != '}'; s++)
                if (!isalnum(c) && c != '_')
                    i = 0;
            *s = 0;
            if (c == '[')
            {
                append(buf, b);
                *s = c;
                continue;
            }
            v = (char*)search(state.vars, t, NiL);
            if ((c == ':' || c == '=') && (!v || c == ':' && !*v))
            {
                append(buf, b);
                *s = c;
                continue;
            }
            if (t[0] == 'A' && t[1] == 'R' && t[2] == 0)
                a = 1;
            *s = c;
            if (c && c != '}')
            {
                n = 1;
                for (t = ++s; *s; s++)
                    if (*s == '{')
                        n++;
                    else if (*s == '}' && !--n)
                        break;
            }
            switch (c)
            {
            case '?':
                q = cond(t - 1);
                if (v)
                {
                    if (((q - t) != 1 || *t != '*') && strncmp(v, t, q - t))
                        v = 0;
                }
                else if (q == t)
                    v = s;
                t = cond(q);
                if (v)
                {
                    if (t > q)
                    {
                        c = *t;
                        *t = 0;
                        substitute(buf, q + 1);
                        *t = c;
                    }
                }
                else
                {
                    q = cond(t);
                    if (q > t)
                    {
                        c = *q;
                        *q = 0;
                        substitute(buf, t + 1);
                        *q = c;
                    }
                }
                break;
            case '+':
            case '-':
                if ((v == 0 || *v == 0) == (c == '-'))
                {
                    c = *s;
                    *s = 0;
                    substitute(buf, t);
                    *s = c;
                    break;
                }
                if (c != '-')
                    break;
                /*FALLTHROUGH*/
            case 0:
            case '=':
            case '}':
                if (v)
                {
                    if (a && t[0] == 'm' && t[1] == 'a' && t[2] == 'm' && t[3] == '_' && t[4] == 'l' && t[5] == 'i' && t[6] == 'b')
                    {
                        for (t = v; *t == ' '; t++);
                        for (; *t && *t != ' '; t++);
                        if (*t)
                            *t = 0;
                        else
                            t = 0;
                        substitute(buf, v);
                        if (t)
                            *t = ' ';
                    }
                    else
                        substitute(buf, v);
                }
                else if (i)
                {
                    c = *s;
                    *s = 0;
                    append(buf, b);
                    *s = c;
                    continue;
                }
                break;
            }
            if (*s)
                s++;
        }
        else
            add(buf, c);
    }
}

/*
 * expand var refs from s into buf and return buf base
 */

static char*
expand(Buf_t* buf, char* s)
{
    substitute(buf, s);
    return use(buf);
}

/*
 * stat() with .exe check
 */

static char*
status(Buf_t* buf, int off, char* path, struct stat* st)
{
    int     r;
    char*       s;
    Buf_t*      tmp;

    if (!stat(path, st))
        return path;
    if (!(tmp = buf))
    {
        tmp = buffer();
        off = 0;
    }
    if (off)
        set(tmp, off);
    else
        append(tmp, path);
    append(tmp, ".exe");
    s = use(tmp);
    r = stat(s, st);
    if (!buf)
    {
        drop(tmp);
        s = path;
    }
    if (r)
    {
        if (off)
            s[off] = 0;
        s = 0;
    }
    return s;
}

/*
 * return path to file
 */

static char*
find(Buf_t* buf, char* file, struct stat* st)
{
    char*       s;
    View_t*     vp;
    int     node;
    int     c;
    int     o;

    if (s = status(buf, 0, file, st))
    {
        report(-3, s, "find", (unsigned long)0);
        return s;
    }
    if (vp = state.view)
    {
        node = 0;
        if (*file == '/')
        {
            do
            {
                if (!strncmp(file, vp->dir, vp->node))
                {
                    file += vp->node;
                    node = 2;
                    break;
                }
            } while (vp = vp->next);
        }
        else
            vp = vp->next;
        if (vp)
            do
            {
                if (node)
                {
                    c = vp->dir[vp->node];
                    vp->dir[vp->node] = 0;
                    append(buf, vp->dir);
                    vp->dir[vp->node] = c;
                }
                else
                {
                    append(buf, vp->dir);
                    append(buf, "/");
                }
                append(buf, file);
                o = get(buf);
                s = use(buf);
                if (s = status(buf, o, s, st))
                {
                    report(-3, s, "find", (unsigned long)0);
                    return s;
                }
            } while (vp = vp->next);
    }
    return 0;
}

/*
 * bind r to a file and return the modify time
 */

static unsigned long
bind(Rule_t* r)
{
    char*       s;
    Buf_t*      buf;
    struct stat st;

    buf = buffer();
    if (s = find(buf, r->name, &st))
    {
        if (s != r->name)
            r->path = duplicate(s);
        r->time = st.st_mtime;
        r->flags |= RULE_exists;
    }
    drop(buf);
    return r->time;
}

/*
 * pop the current input file
 */

static int
pop(void)
{
    int r;

    if (!state.sp)
        report(3, "input stack underflow", NiL, (unsigned long)0);
    if (!state.sp->fp || (state.sp->flags & STREAM_KEEP))
        r = 0;
    else if (state.sp->flags & STREAM_PIPE)
        r = pclose(state.sp->fp);
    else
        r = fclose(state.sp->fp);
    if (state.sp == state.streams)
        state.sp = 0;
    else
        state.sp--;
    return r;
}

/*
 * push file onto the input stack
 */

static int
push(char* file, Stdio_t* fp, int flags)
{
    char*       path;
    Buf_t*      buf;
    struct stat st;

    if (!state.sp)
        state.sp = state.streams;
    else if (++state.sp >= &state.streams[elementsof(state.streams)])
        report(3, "input stream stack overflow", NiL, (unsigned long)0);
    if (state.sp->fp = fp)
        state.sp->file = "pipeline";
    else if (flags & STREAM_PIPE)
        report(3, "pipe error", file, (unsigned long)0);
    else if (!file || !strcmp(file, "-") || !strcmp(file, "/dev/stdin"))
    {
        flags |= STREAM_KEEP;
        state.sp->file = "/dev/stdin";
        state.sp->fp = stdin;
    }
    else
    {
        buf = buffer();
        if (path = find(buf, file, &st))
        {
            if (!(state.sp->fp = fopen(path, "r")))
                report(3, "cannot read", path, (unsigned long)0);
            state.sp->file = duplicate(path);
            drop(buf);
        }
        else
        {
            drop(buf);
            pop();
            if (flags & STREAM_MUST)
                report(3, "not found", file, (unsigned long)0);
            return 0;
        }
    }
    state.sp->flags = flags;
    state.sp->line = 0;
    return 1;
}

/*
 * return the next input line
 */

static char*
input(void)
{
    char*   e;

    if (!state.sp)
        report(3, "no input file stream", NiL, (unsigned long)0);
    if (state.peek)
        state.peek = 0;
    else if (!fgets(state.input, sizeof(state.input), state.sp->fp))
        return 0;
    else if (*state.input && *(e = state.input + strlen(state.input) - 1) == '\n')
        *e = 0;
    state.sp->line++;
    return state.input;
}

/*
 * pass shell action s to ${SHELL:-/bin/sh}
 * the -c wrapper ensures that scripts are run in the selected shell
 * even on systems that otherwise demand #! magic (can you say cygwin)
 */

static int
execute(register char* s)
{
    register int    c;
    Buf_t*      buf;

    if (!state.shell && (!(state.shell = (char*)search(state.vars, "SHELL", NiL)) || !strcmp(state.shell, sh)))
        state.shell = sh;
    buf = buffer();
    append(buf, state.shell);
    append(buf, " -c '");
    while (c = *s++)
    {
        if (c == '\'')
        {
            add(buf, c);
            for (s--; *s == c; s++)
            {
                add(buf, '\\');
                add(buf, c);
            }
        }
        add(buf, c);
    }
    add(buf, '\'');
    s = use(buf);
    report(-5, s, "exec", (unsigned long)0);
    if ((c = system(s)) > 255)
        c >>= 8;
    drop(buf);
    return c;
}

/*
 * run action s to update r
 */

static unsigned long
run(Rule_t* r, register char* s)
{
    register Rule_t*    q;
    register char*      t;
    register int        c;
    register View_t*    v;
    int         i;
    int         j;
    int         x;
    Stat_t          st;
    Buf_t*          buf;

    if (r->flags & RULE_error)
        return r->time;
    buf = buffer();
    if (!strncmp(s, "mamake -r ", 10))
    {
        state.verified = 1;
        x = !state.never;
    }
    else
        x = state.exec;
    if (x)
        append(buf, "trap - 1 2 3 15\nPATH=.:$PATH\nset -x\n");
    if (state.view)
    {
        do
        {
            for (; delimiter(*s); s++)
                add(buf, *s);
            for (t = s; *s && !delimiter(*s); s++);
            c = *s;
            *s = 0;
            if (c == '=')
            {
                append(buf, t);
                continue;
            }
            if ((q = (Rule_t*)search(state.rules, t, NiL)) && q->path && !(q->flags & RULE_generated))
                append(buf, q->path);
            else
            {
                append(buf, t);
                if (*t == '-' && *(t + 1) == 'I' && (*(t + 2) || c))
                {
                    if (*(t + 2))
                        i = 2;
                    else
                    {
                        for (i = 3; *(t + i) == ' ' || *(t + i) == '\t'; i++);
                        *s = c;
                        for (s = t + i; *s && *s != ' ' && *s != '\t' && *s != '\n'; s++);
                        c = *s;
                        *s = 0;
                        append(buf, t + 2);
                    }
                    if (*(t + i) && *(t + i) != '/')
                    {
                        v = state.view;
                        while (v = v->next)
                        {
                            add(buf, ' ');
                            for (j = 0; j < i; j++)
                                add(buf, *(t + j));
                            append(buf, v->dir);
                            if (*(t + i) != '.' || *(t + i + 1))
                            {
                                add(buf, '/');
                                append(buf, t + i);
                            }
                        }
                    }
                }
            }
        } while (*s = c);
        s = use(buf);
    }
    else if (x)
    {
        append(buf, s);
        s = use(buf);
    }
    if (x)
    {
        if (c = execute(s))
            dont(r, c, state.keepgoing);
        if (status((Buf_t*)0, 0, r->name, &st))
        {
            r->time = st.st_mtime;
            r->flags |= RULE_exists;
        }
        else
            r->time = NOW;
    }
    else
    {
        fprintf(stdout, "%s\n", s);
        if (state.debug)
            fflush(stdout);
        r->time = NOW;
        r->flags |= RULE_exists;
    }
    drop(buf);
    return r->time;
}

/*
 * return the full path for s using buf workspace
 */

static char*
path(Buf_t* buf, char* s, int must)
{
    register char*  p;
    register char*  d;
    register char*  x;
    char*       e;
    register int    c;
    int     t;
    int     o;
    Stat_t      st;

    for (e = s; *e && *e != ' ' && *e != '\t'; e++);
    t = *e;
    if ((x = status(buf, 0, s, &st)) && (st.st_mode & (S_IXUSR|S_IXGRP|S_IXOTH)))
        return x;
    if (!(p = (char*)search(state.vars, "PATH", NiL)))
        report(3, "variable not defined", "PATH", (unsigned long)0);
    do
    {
        for (d = p; *p && *p != ':'; p++);
        c = *p;
        *p = 0;
        if (*d && (*d != '.' || *(d + 1)))
        {
            append(buf, d);
            add(buf, '/');
        }
        *p = c;
        if (t)
            *e = 0;
        append(buf, s);
        if (t)
            *e = t;
        o = get(buf);
        x = use(buf);
        if ((x = status(buf, o, x, &st)) && (st.st_mode & (S_IXUSR|S_IXGRP|S_IXOTH)))
            return x;
    } while (*p++);
    if (must)
        report(3, "command not found", s, (unsigned long)0);
    return 0;
}

/*
 * generate (if necessary) and read the MAM probe information
 * done on the first `setv CC ...'
 */

static void
probe(void)
{
    register char*  cc;
    register char*  s;
    unsigned long   h;
    unsigned long   q;
    Buf_t*      buf;
    Buf_t*      pro;
    Buf_t*      tmp;
    struct stat st;

    static char let[] = "ABCDEFGHIJKLMNOP";
    static char cmd[] = "mamprobe";

    if (!(cc = (char*)search(state.vars, "CC", NiL)))
        cc = "cc";
    buf = buffer();
    s = path(buf, cmd, 1);
    q = stat(s, &st) ? (unsigned long)0 : (unsigned long)st.st_mtime;
    pro = buffer();
    s = cc = path(pro, cc, 1);
    for (h = 0; *s; s++)
        h = h * 0x63c63cd9L + *s + 0x9c39c33dL;
    if (!(s = (char*)search(state.vars, "INSTALLROOT", NiL)))
        report(3, "variable must be defined", "INSTALLROOT", (unsigned long)0);
    append(buf, s);
    append(buf, "/lib/probe/C/mam/");
    for (h &= 0xffffffffL; h; h >>= 4)
        add(buf, let[h & 0xf]);
    s = use(buf);
    h = stat(s, &st) ? (unsigned long)0 : (unsigned long)st.st_mtime;
    if (h < q || !push(s, (Stdio_t*)0, 0))
    {
        tmp = buffer();
        append(tmp, cmd);
        add(tmp, ' ');
        append(tmp, s);
        add(tmp, ' ');
        append(tmp, cc);
        if (execute(use(tmp)))
            report(3, "cannot generate probe info", s, (unsigned long)0);
        drop(tmp);
        if (!push(s, (Stdio_t*)0, 0))
            report(3, "cannot read probe info", s, (unsigned long)0);
    }
    drop(pro);
    drop(buf);
    make(rule(""));
    pop();
}

/*
 * add attributes in s to r
 */

static void
attributes(register Rule_t* r, register char* s)
{
    register char*  t;
    register int    n;

    for (;;)
    {
        for (; *s == ' '; s++);
        for (t = s; *s && *s != ' '; s++);
        if (!(n = s - t))
            break;
        switch (*t)
        {
        case 'd':
            if (n == 8 && !strncmp(t, "dontcare", n))
                r->flags |= RULE_dontcare;
            break;
        case 'g':
            if (n == 9 && !strncmp(t, "generated", n))
                r->flags |= RULE_generated;
            break;
        case 'i':
            if (n == 6 && !strncmp(t, "ignore", n))
                r->flags |= RULE_ignore;
            else if (n == 8 && !strncmp(t, "implicit", n))
                r->flags |= RULE_implicit;
            break;
        case 'v':
            if (n == 7 && !strncmp(t, "virtual", n))
                r->flags |= RULE_virtual;
            break;
        }
    }
}

/*
 * define ${mam_libX} for library reference lib
 */

static char*
require(char* lib, int dontcare)
{
    register int    c;
    char*       s;
    char*       r;
    FILE*       f;
    Buf_t*      buf;
    Buf_t*      tmp;
    struct stat st;

    static int  dynamic = -1;

    if (dynamic < 0)
        dynamic = (s = search(state.vars, "mam_cc_L", NiL)) ? atoi(s) : 0;
    if (!(r = search(state.vars, lib, NiL)))
    {
        buf = buffer();
        tmp = buffer();
        s = 0;
        for (;;)
        {
            if (s)
                append(buf, s);
            if (r = search(state.vars, "mam_cc_PREFIX_ARCHIVE", NiL))
                append(buf, r);
            append(buf, lib + 2);
            if (r = search(state.vars, "mam_cc_SUFFIX_ARCHIVE", NiL))
                append(buf, r);
            r = expand(tmp, use(buf));
            if (!stat(r, &st))
                break;
            if (s)
            {
                r = lib;
                break;
            }
            s = "${INSTALLROOT}/lib/";
            if (dynamic)
            {
                append(buf, s);
                if (r = search(state.vars, "mam_cc_PREFIX_SHARED", NiL))
                    append(buf, r);
                append(buf, lib + 2);
                if (r = search(state.vars, "mam_cc_SUFFIX_SHARED", NiL))
                    append(buf, r);
                r = expand(tmp, use(buf));
                if (!stat(r, &st))
                {
                    r = lib;
                    break;
                }
            }
        }
        if (r != lib)
            r = duplicate(r);
        search(state.vars, lib, r);
        append(tmp, lib + 2);
        append(tmp, ".req");
        if (!(f = fopen(use(tmp), "r")))
        {
            append(tmp, "${INSTALLROOT}/lib/lib/");
            append(tmp, lib + 2);
            f = fopen(expand(buf, use(tmp)), "r");
        }
        if (f)
        {
            for (;;)
            {
                while ((c = fgetc(f)) == ' ' || c == '\t' || c == '\n');
                if (c == EOF)
                    break;
                do
                {
                    add(tmp, c);
                } while ((c = fgetc(f)) != EOF && c != ' ' && c != '\t' && c != '\n');
                s = use(tmp);
                if (s[0] && (s[0] != '-' || s[1]))
                {
                    add(buf, ' ');
                    append(buf, require(s, 0));
                }
            }
            fclose(f);
            r = use(buf);
        }
        else if (dontcare)
        {
            append(tmp, "set -\n");
            append(tmp, "cd /tmp\n");
            append(tmp, "echo 'int main(){return 0;}' > x.${!-$$}.c\n");
            append(tmp, "${CC} ${CCFLAGS} -o x.${!-$$}.x x.${!-$$}.c ");
            append(tmp, r);
            append(tmp, " >/dev/null 2>&1\n");
            append(tmp, "c=$?\n");
            append(tmp, "rm -f x.${!-$$}.[cox]\n");
            append(tmp, "exit $c\n");
            if (execute(expand(buf, use(tmp))))
                r = "";
        }
        r = duplicate(r);
        search(state.vars, lib, r);
        append(tmp, "mam_lib");
        append(tmp, lib + 2);
        search(state.vars, use(tmp), r);
        drop(tmp);
        drop(buf);
    }
    return r;
}

/*
 * input() until `done r'
 */

static unsigned long
make(Rule_t* r)
{
    register char*      s;
    register char*      t;
    register char*      u;
    register char*      v;
    register Rule_t*    q;
    unsigned long       z;
    unsigned long       x;
    Buf_t*          buf;
    Buf_t*          cmd;

    r->making++;
    if (r->flags & RULE_active)
        state.active++;
    if (*r->name)
    {
        z = bind(r);
        state.indent++;
        report(-1, r->name, "make", r->time);
    }
    else
        z = 0;
    buf = buffer();
    cmd = 0;
    while (s = input())
    {
        for (; *s == ' '; s++);
        for (; isdigit(*s); s++);
        for (; *s == ' '; s++);
        for (u = s; *s && *s != ' '; s++);
        if (*s)
        {
            for (*s++ = 0; *s == ' '; s++);
            for (t = s; *s && *s != ' '; s++);
            if (*s)
                for (*s++ = 0; *s == ' '; s++);
            v = s;
        }
        else
            t = v = s;
        switch (KEY(u[0], u[1], u[2], u[3]))
        {
        case KEY('b','i','n','d'):
            if ((t[0] == '-' || t[0] == '+') && t[1] == 'l' && (s = require(t, !strcmp(v, "dontcare"))) && strncmp(r->name, "FEATURE/", 8) && strcmp(r->name, "configure.h"))
                for (;;)
                {
                    for (t = s; *s && *s != ' '; s++);
                    if (*s)
                        *s = 0;
                    else
                        s = 0;
                    if (*t)
                    {
                        q = rule(expand(buf, t));
                        attributes(q, v);
                        x = bind(q);
                        if (z < x)
                            z = x;
                        if (q->flags & RULE_error)
                            r->flags |= RULE_error;
                    }
                    if (!s)
                        break;
                    for (*s++ = ' '; *s == ' '; s++);
                }
            continue;
        case KEY('d','o','n','e'):
            q = rule(expand(buf, t));
            if (q != r)
                report(2, "improper done statement", t, (unsigned long)0);
            attributes(r, v);
            if (cmd && state.active && (state.force || r->time < z || !r->time && !z))
            {
                if (state.explain && !state.force)
                {
                    if (!r->time)
                        fprintf(stderr, "%s [not found]\n", r->name);
                    else
                        fprintf(stderr, "%s [%lu] older than prerequisites [%lu]\n", r->name, r->time, z);
                }
                substitute(buf, use(cmd));
                x = run(r, use(buf));
                if (z < x)
                    z = x;
            }
            r->flags |= RULE_made;
            if (!(r->flags & (RULE_dontcare|RULE_error|RULE_exists|RULE_generated|RULE_implicit|RULE_virtual)))
                dont(r, 0, state.keepgoing);
            break;
        case KEY('e','x','e','c'):
            r->flags |= RULE_generated;
            if (r->path)
            {
                free(r->path);
                r->path = 0;
                r->time = 0;
            }
            if (state.active)
            {
                if (cmd)
                    add(cmd, '\n');
                else
                    cmd = buffer();
                append(cmd, v);
            }
            continue;
        case KEY('m','a','k','e'):
            q = rule(expand(buf, t));
            if (!q->making)
            {
                attributes(q, v);
                x = make(q);
                if (!(q->flags & RULE_ignore) && z < x)
                    z = x;
                if (q->flags & RULE_error)
                    r->flags |= RULE_error;
            }
            continue;
        case KEY('p','r','e','v'):
            q = rule(expand(buf, t));
            if (!q->making)
            {
                if (!(q->flags & RULE_ignore) && z < q->time)
                    z = q->time;
                if (q->flags & RULE_error)
                    r->flags |= RULE_error;
                state.indent++;
                report(-2, q->name, "prev", q->time);
                state.indent--;
            }
            continue;
        case KEY('s','e','t','v'):
            if (!search(state.vars, t, NiL))
            {
                if (*v == '"')
                {
                    s = v + strlen(v) - 1;
                    if (*s == '"')
                    {
                        *s = 0;
                        v++;
                    }
                }
                search(state.vars, t, duplicate(expand(buf, v)));
            }
            if (!state.probed && t[0] == 'C' && t[1] == 'C' && !t[2])
            {
                state.probed = 1;
                probe();
            }
            continue;
        default:
            continue;
        }
        break;
    }
    drop(buf);
    if (cmd)
        drop(cmd);
    if (*r->name)
    {
        report(-1, r->name, "done", z);
        state.indent--;
    }
    if (r->flags & RULE_active)
        state.active--;
    r->making--;
    return r->time = z;
}

/*
 * verify that active targets were made
 */

static int
verify(Dict_item_t* item, void* handle)
{
    Rule_t* r = (Rule_t*)item->value;

    if ((r->flags & (RULE_active|RULE_error|RULE_made)) == RULE_active)
        dont(r, 0, 1);
    return 0;
}

/*
 * return 1 if name is an initializer
 */

static int
initializer(char* name)
{
    register char*  s;

    if (s = last(name, '/'))
        s++;
    else
        s = name;
    return s[0] == 'I' && s[1] == 'N' && s[2] == 'I' && s[3] == 'T';
}

/*
 * update recursion leaf r and its prerequisites
 */

static int
update(register Rule_t* r)
{
    register List_t*    x;
    Buf_t*          buf;

    static char     cmd[] = "${MAMAKE} -C ";
    static char     arg[] = " ${MAMAKEARGS}";

    r->flags |= RULE_made;
    if (r->leaf)
        r->leaf->flags |= RULE_made;
    for (x = r->prereqs; x; x = x->next)
        if (x->rule->leaf && !(x->rule->flags & RULE_made))
            update(x->rule);
    buf = buffer();
    substitute(buf, cmd);
    append(buf, r->name);
    substitute(buf, arg);
    run(r, use(buf));
    drop(buf);
    return 0;
}

/*
 * scan makefile prereqs
 */

static int
scan(Dict_item_t* item, void* handle)
{
    register Rule_t*    r = (Rule_t*)item->value;
    register char*      s;
    register char*      t;
    register char*      u;
    register char*      w;
    Rule_t*         q;
    int         i;
    int         j;
    int         k;
    int         p;
    Buf_t*          buf;

    static char*        files[] =
                {
                    "Nmakefile",
                    "nmakefile",
                    "Makefile",
                    "makefile"
                };

    /*
     * drop non-leaf rules
     */

    if (!r->leaf)
        return 0;

    /*
     * always make initializers
     */

    if (initializer(r->name))
    {
        if (!(r->flags & RULE_made))
            update(r);
        return 0;
    }
    buf = buffer();
    for (i = 0; i < elementsof(files); i++)
    {
        append(buf, r->name);
        add(buf, '/');
        append(buf, files[i]);
        if (push(use(buf), (Stdio_t*)0, 0))
        {
            while (s = input())
            {
                j = p = 0;
                while (*s)
                {
                    for (k = 1; (i = *s) == ' ' || i == '\t' || i == '"' || i == '\''; s++);
                    for (t = s; (i = *s) && i != ' ' && i != '\t' && i != '"' && i != '\'' && i != '\\' && i != ':'; s++)
                        if (i == '/')
                            t = s + 1;
                        else if (i == '.' && *(s + 1) != 'c' && *(s + 1) != 'C' && *(s + 1) != 'h' && *(s + 1) != 'H' && t[0] == 'l' && t[1] == 'i' && t[2] == 'b')
                            *s = 0;
                    if (*s)
                        *s++ = 0;
                    if (!t[0])
                        k = 0;
                    else if ((t[0] == '-' || t[0] == '+') && t[1] == 'l' && t[2])
                    {
                        append(buf, "lib");
                        append(buf, t + 2);
                        t = use(buf);
                    }
                    else if (p)
                    {
                        if (t[0] == '+' && !t[1])
                            p = 2;
                        else if (p == 1)
                        {
                            if (i != ':' || strncmp(s, "command", 7))
                            {
                                append(buf, "lib");
                                append(buf, t);
                                t = use(buf);
                            }
                            if (i == ':')
                                while (*s && (*s == ' ' || *s == '\t'))
                                    s++;
                        }
                    }
                    else if (i == ':')
                    {
                        if (j != ':' || !isupper(*t))
                            k = 0;
                        else if (!strcmp(t, "PACKAGE"))
                        {
                            p = 1;
                            k = 0;
                        }
                        else
                            for (u = t; *u; u++)
                                if (isupper(*u))
                                    *u = tolower(*u);
                                else if (!isalnum(*u))
                                {
                                    k = 0;
                                    break;
                                }
                    }
                    else if (t[0] != 'l' || t[1] != 'i' || t[2] != 'b')
                        k = 0;
                    else
                        for (u = t + 3; *u; u++)
                            if (!isalnum(*u))
                            {
                                k = 0;
                                break;
                            }
                    if (k && ((q = (Rule_t*)search(state.leaf, t, NiL)) && q != r || *t++ == 'l' && *t++ == 'i' && *t++ == 'b' && *t && (q = (Rule_t*)search(state.leaf, t, NiL)) && q != r))
                    {
                        for (t = w = r->name; *w; w++)
                            if (*w == '/')
                                t = w + 1;
                        if (t[0] == 'l' && t[1] == 'i' && t[2] == 'b')
                            t += 3;
                        for (u = w = q->name; *w; w++)
                            if (*w == '/')
                                u = w + 1;
                        if (strcmp(t, u))
                            cons(r, q);
                    }
                    j = i;
                }
            }
            pop();
            for (s = 0, w = r->name; *w; w++)
                if (*w == '/')
                    s = w;
            if (s)
            {
                if ((s - r->name) > 3 && *(s - 1) == 'b' && *(s - 2) == 'i' && *(s - 3) == 'l' && *(s - 4) != '/')
                {
                    /*
                     * foolib : foo : libfoo
                     */

                    *(s - 3) = 0;
                    q = (Rule_t*)search(state.leaf, r->name, NiL);
                    if (q && q != r)
                        cons(r, q);
                    for (t = w = r->name; *w; w++)
                        if (*w == '/')
                            t = w + 1;
                    append(buf, "lib");
                    append(buf, t);
                    q = (Rule_t*)search(state.leaf, use(buf), NiL);
                    if (q && q != r)
                        cons(r, q);
                    *(s - 3) = 'l';
                }
                else if (((s - r->name) != 3 || *(s - 1) != 'b' || *(s - 2) != 'i' || *(s - 3) != 'l') && (*(s + 1) != 'l' || *(s + 2) != 'i' || *(s + 3) != 'b'))
                {
                    /*
                     * huh/foobar : lib/libfoo
                     */

                    s++;
                    t = s + strlen(s);
                    while (--t > s)
                    {
                        append(buf, "lib/lib");
                        appendn(buf, s, t - s);
                        q = (Rule_t*)search(state.leaf, use(buf), NiL);
                        if (q && q != r)
                            cons(r, q);
                    }
                }
            }
            break;
        }
    }
    drop(buf);
    return 0;
}

/*
 * descend into op and its prereqs
 */

static int
descend(Dict_item_t* item, void* handle)
{
    Rule_t* r = (Rule_t*)item->value;

    if (!state.active && (!(r->flags & RULE_active) || !(r = (Rule_t*)search(state.leaf, r->name, NiL))))
        return 0;
    return r->leaf && !(r->flags & RULE_made) ? update(r) : 0;
}

/*
 * append the non-leaf active targets to state.opt
 */

static int
active(Dict_item_t* item, void* handle)
{
    Rule_t* r = (Rule_t*)item->value;

    if (r->flags & RULE_active)
    {
        if (r->leaf || search(state.leaf, r->name, NiL))
            state.active = 0;
        else
        {
            add(state.opt, ' ');
            append(state.opt, r->name);
        }
    }
    return 0;
}

/*
 * recurse on mamfiles in subdirs matching pattern
 */

static int
recurse(char* pattern)
{
    register char*  s;
    register char*  t;
    Rule_t*     r;
    Buf_t*      buf;
    Buf_t*      tmp;
    struct stat st;

    /*
     * first determine the MAM subdirs
     */

    tmp = buffer();
    buf = buffer();
    state.exec = !state.never;
    state.leaf = dictionary();
    append(buf, "ls -d ");
    append(buf, pattern);
    s = use(buf);
    push("recurse", popen(s, "r"), STREAM_PIPE);
    while (s = input())
    {
        append(buf, s);
        add(buf, '/');
        append(buf, mamfile);
        if (find(tmp, use(buf), &st))
        {
            r = rule(s);
            if (t = last(r->name, '/'))
                t++;
            else
                t = r->name;
            r->leaf = rule(t);
            search(state.leaf, t, r);
        }
    }
    pop();
    drop(buf);
    drop(tmp);

    /*
     * grab the non-leaf active targets
     */

    if (!state.active)
    {
        state.active = 1;
        walk(state.rules, active, NiL);
    }
    search(state.vars, "MAMAKEARGS", duplicate(use(state.opt) + 1));

    /*
     * scan the makefile and descend
     */

    walk(state.rules, scan, NiL);
    state.view = 0;
    walk(state.rules, descend, NiL);
    return 0;
}

int
main(int argc, char** argv)
{
    register char**     e;
    register char*      s;
    register char*      t;
    register char*      v;
    Buf_t*          tmp;
    int         c;

    /*
     * initialize the state
     */

    state.id = "mamake";
    state.active = 1;
    state.exec = 1;
    state.file = mamfile;
    state.opt = buffer();
    state.rules = dictionary();
    state.vars = dictionary();
    search(state.vars, "MAMAKE", *argv);

    /*
     * parse the options
     */

#if _PACKAGE_ast
    error_info.id = state.id;
    for (;;)
    {
        switch (optget(argv, usage))
        {
        case 'e':
            append(state.opt, " -e");
            state.explain = 1;
            continue;
        case 'i':
            append(state.opt, " -i");
            state.ignore = 1;
            continue;
        case 'k':
            append(state.opt, " -k");
            state.keepgoing = 1;
            continue;
        case 'N':
            state.never = 1;
            /*FALLTHROUGH*/
        case 'n':
            append(state.opt, " -n");
            state.exec = 0;
            continue;
        case 'F':
            append(state.opt, " -F");
            state.force = 1;
            continue;
        case 'K':
            continue;
        case 'V':
            fprintf(stdout, "%s\n", id + 10);
            exit(0);
        case 'f':
            append(state.opt, " -f ");
            append(state.opt, opt_info.arg);
            state.file = opt_info.arg;
            continue;
        case 'r':
            state.recurse = opt_info.arg;
            continue;
        case 'C':
            state.directory = opt_info.arg;
            continue;
        case 'D':
            append(state.opt, " -D");
            append(state.opt, opt_info.arg);
            state.debug = -opt_info.num;
            continue;
        case 'G':
            append(state.opt, " -G");
            search(state.vars, "-debug-symbols", "1");
            continue;
        case 'S':
            append(state.opt, " -S");
            search(state.vars, "-strip-symbols", "1");
            continue;
        case '?':
            error(ERROR_USAGE|4, "%s", opt_info.arg);
            continue;
        case ':':
            error(2, "%s", opt_info.arg);
            continue;
        }
        break;
    }
    if (error_info.errors)
        error(ERROR_USAGE|4, "%s", optusage(NiL));
    argv += opt_info.index;
#else
    while ((s = *++argv) && *s == '-')
    {
        if (*(s + 1) == '-')
        {
            if (!*(s + 2))
            {
                append(state.opt, " --");
                argv++;
                break;
            }
            for (t = s += 2; *t && *t != '='; t++);
            if (!strncmp(s, "debug-symbols", t - s) && append(state.opt, " -G") || !strncmp(s, "strip-symbols", t - s) && append(state.opt, " -S"))
            {
                if (*t)
                {
                    v = t + 1;
                    if (t > s && *(t - 1) == '+')
                        t--;
                    c = *t;
                    *t = 0;
                }
                else
                {
                    c = 0;
                    v = "1";
                }
                search(state.vars, s - 1, v);
                if (c)
                    *t = c;
                continue;
            }
            usage();
            break;
        }
        for (;;)
        {
            switch (*++s)
            {
            case 0:
                break;
            case 'e':
                append(state.opt, " -e");
                state.explain = 1;
                continue;
            case 'i':
                append(state.opt, " -i");
                state.ignore = 1;
                continue;
            case 'k':
                append(state.opt, " -k");
                state.keepgoing = 1;
                continue;
            case 'N':
                state.never = 1;
                /*FALLTHROUGH*/
            case 'n':
                append(state.opt, " -n");
                state.exec = 0;
                continue;
            case 'F':
                append(state.opt, " -F");
                state.force = 1;
                continue;
            case 'G':
                append(state.opt, " -G");
                search(state.vars, "-debug-symbols", "1");
                continue;
            case 'K':
                continue;
            case 'S':
                append(state.opt, " -S");
                search(state.vars, "-strip-symbols", "1");
                continue;
            case 'V':
                fprintf(stdout, "%s\n", id + 10);
                exit(0);
            case 'f':
            case 'r':
            case 'C':
            case 'D':
                t = s;
                if (!*++s && !(s = *++argv))
                {
                    report(2, "option value expected", t, (unsigned long)0);
                    usage();
                }
                else
                    switch (*t)
                    {
                    case 'f':
                        append(state.opt, " -f ");
                        append(state.opt, s);
                        state.file = s;
                        break;
                    case 'r':
                        state.recurse = s;
                        break;
                    case 'C':
                        state.directory = s;
                        break;
                    case 'D':
                        append(state.opt, " -D");
                        append(state.opt, s);
                        state.debug = -atoi(s);
                        break;
                    }
                break;
            default:
                report(2, "unknown option", s, (unsigned long)0);
            case '?':
                usage();
                break;
            }
            break;
        }
    }
#endif

    /*
     * load the environment
     */

    for (e = environ; s = *e; e++)
        for (t = s; *t; t++)
            if (*t == '=')
            {
                *t = 0;
                search(state.vars, s, t + 1);
                *t = '=';
                break;
            }

    /*
     * grab the command line targets and variable definitions
     */

    while (s = *argv++)
    {
        for (t = s; *t; t++)
            if (*t == '=')
            {
                v = t + 1;
                if (t > s && *(t - 1) == '+')
                    t--;
                c = *t;
                *t = 0;
                search(state.vars, s, v);
                tmp = buffer();
                append(tmp, s);
                append(tmp, ".FORCE");
                search(state.vars, use(tmp), v);
                drop(tmp);
                *t = c;
                break;
            }
        if (!*t)
        {
            /*
             * handle a few targets for nmake compatibility
             */

            if (*s == 'e' && !strncmp(s, "error 0 $(MAKEVERSION:", 22))
                exit(1);
            if (*s == 'r' && !strcmp(s, "recurse") || *s == 'c' && !strncmp(s, "cc-", 3))
                continue;
            rule(s)->flags |= RULE_active;
            state.active = 0;
            if (state.recurse)
                continue;
        }
        add(state.opt, ' ');
        add(state.opt, '\'');
        append(state.opt, s);
        add(state.opt, '\'');
    }

    /*
     * initialize the views
     */

    if (state.directory && chdir(state.directory))
        report(3, "cannot change working directory", NiL, (unsigned long)0);
    view();

    /*
     * recursion drops out here
     */

    if (state.recurse)
        return recurse(state.recurse);

    /*
     * read the mamfile(s) and bring the targets up to date
     */

    search(state.vars, "MAMAKEARGS", duplicate(use(state.opt) + 1));
    push(state.file, (Stdio_t*)0, STREAM_MUST);
    make(rule(""));
    pop();

    /*
     * verify that active targets were made
     */

    if (!state.active && !state.verified)
        walk(state.rules, verify, NiL);

    /*
     * done
     */

    return state.errors != 0;
}