/*
 *  DMAKE.C
 *
 *  (c)Copyright 1989 by Matthew Dillon, All Rights Reserved.
 *
 *	ONLY AN APPROPRIATE AMIGA EXECUTABLE MAY BE DISTRIBUTED.  DO
 *	NOT DISTRIBUTE SOURCE!
 *
 *  This is a new try at makefiles ...	read the documentation.
 */

#include "defs.h"


MLIST	DepList;    /*	Dependancies	*/

short Verbose;
short Silent;
short LineNo;
short XDebug;
short ForceAll;
short ListOnly;
short Order;
long  SaveLock;
char MakeFile[128];

main(ac, av)
char *av[];
{
    short dofirst = 1;
    short error = 0;


    NewList(&DepList);
    strcpy(MakeFile, "DMakefile");

    SaveLock = CurrentDir(Lock("", SHARED_LOCK));
    {
	register short i;
	short notenoughargs = 0;
	for (i = 1; i < ac; ++i) {
	    register char *ptr = av[i];
	    if (*ptr != '-')
		continue;
	    while (*++ptr) {
		switch(*ptr) {
		case 's':
		    ++Silent;
		    break;
		case 'v':
		    ++Verbose;
		    break;
		case 'd':
		    ++XDebug;
		    break;
		case 'n':
		    ListOnly = 1;
		    break;
		case 'a':
		    ForceAll = 1;
		    break;
		case 'f':
		    if (i + 1 < ac) {
			strcpy(MakeFile, av[++i]);
			av[i][0] = '-'; /* kill it */
		    } else {
			notenoughargs = 1;
		    }
		    break;
		}
	    }
	}
	if (notenoughargs) {
	    puts("Not enough args for option!");
	    xexit(20);
	}
    }
    if (!Silent) {
	puts("DMake Beta V0.6 26-Jan-89");
	puts("(c)Copyright 1989 by Matthew Dillon, All Rights Reserved");
    }
    {
	FILE *fi;
	if (fi = fopen(MakeFile, "r")) {
	    ScanFile(fi);
	    fclose(fi);
	} else {
	    printf("Unable to open %s\n", MakeFile);
	    xexit(25);
	}
    }
    {
	register short i;
	for (i = 1; i < ac; ++i) {
	    register char *ptr = av[i];
	    register DEPEND *dep;
	    if (*ptr == '-')
		continue;
	    dofirst = 0;
	    for (dep = GetHead(&DepList); dep; dep = GetSucc(dep)) {
		if (strcmp(ptr, dep->Left) == 0) {
		    /* XXX ? */
		    Order = FindBeginPoint(dep, Order, 1);
		    break;
		}
	    }
	    if (dep == NULL) {
		printf("Could not find %s dependancy\n", ptr);
		error = 10;
	    }
	}
    }
    if (dofirst) {
	register DEPEND *dep = GetHead(&DepList);
	if (dep)
	    Order = FindBeginPoint(dep, Order, 1);
    }
    CombineRefCnts(NULL);
    if (XDebug)
	PrintDepList(&DepList);
    ExecuteDepList();
    xexit(error);
}

xexit(error)
{
    UnLock(CurrentDir(SaveLock));
    exit(error);
}

ScanFile(fi)
FILE *fi;
{
    char *ptr;

    LineNo = 0;
    while (ptr = getline(fi, NULL)) {
	MLIST	*cmdlist = malloc(sizeof(MLIST));
	NewList(cmdlist);

	++LineNo;
	if (*ptr == 0) {
	    free(cmdlist);
	    continue;
	}
	{
	    register char *str = ptr;
	    while ((*str >= 'a' && *str <= 'z') || (*str >= 'A' && *str <= 'Z') ||
		    (*str >= '0' && *str <= '9') ||
		    *str == '_' || *str == ' ' || *str == '\t')
		++str;
	    if (*str == '=') {      /* macro assignment */
		MacroAssign(ptr, str);
		continue;
	    }
	}
	{
	    short ac;
	    register char **av;
	    register short i;

	    av = parseline(ptr, &ac);
	    for (i = 0; i < ac; ++i) {
		if (av[i][0] == ':' && av[i][1] == 0)
		    break;
	    }
	    if (i == ac) {  /*  could be blah:  */
		register char *str = av[0];
		register short len = strlen(str);
		if (len && str[len-1] == ':') {     /*  blah:   */
		    str[len-1] = 0;
		    CreateDependancies(cmdlist, av, 0, 1, 1, ac);
		} else {
		    short cmmnt;
		    printf("Badly formed command line %ld\n", LineNo);
		    while (ptr = getline(fi, &cmmnt)) {
			if (ptr[0] == 0 && !cmmnt)
			    break;
		    }
		}
	    } else {
		CreateDependancies(cmdlist, av, 0, i, i + 1, ac);
	    }
	}
	{
	    register NODE *node;
	    short cmmnt;
	    while (ptr = getline(fi, &cmmnt)) {
		if (ptr[0] == 0 && !cmmnt)
		    break;
		if (ptr[0]) {
		    node = malloc(sizeof(NODE) + strlen(ptr) + 1);
		    node->ln_Name = (char *)(node + 1);
		    strcpy(node->ln_Name, ptr);
		    AddTail(cmdlist, node);
		}
	    }
	}
    }
    if (XDebug)
	PrintDepList(&DepList);
}

/*
 *  COMBINEREFCNTS()
 *
 *  All dependancies with the same left hand side are supposed to have
 *  the same (shared) common structure.  This ensures they do and is
 *  called after operations which might invalidate the rule.
 */

CombineRefCnts(newlist)
MLIST *newlist;
{
    register DEPEND *d1, *d2;

    /*
     *	First combine references within a new list, then combine references
     *	from the new list to the master list, then combine references in
     *	the master list.
     */

    if (newlist) {
	for (d1 = GetHead(newlist); d1; d1 = GetSucc(d1)) {
	    for (d2 = GetSucc(d1); d2; d2 = GetSucc(d2)) {
		if (strcmp(d1->Left, d2->Left) == 0 && d1->Common != d2->Common)
		    Combine(d1, d2);
	    }
	}
	for (d1 = GetHead(newlist); d1; d1 = GetSucc(d1)) {
	    for (d2 = GetHead(&DepList); d2; d2 = GetSucc(d2)) {
		if (strcmp(d1->Left, d2->Left) == 0 && d1->Common != d2->Common)
		    Combine(d1, d2);    /*  deplist's gets it   */
	    }
	}
    }
    for (d1 = GetHead(&DepList); d1; d1 = GetSucc(d1)) {
	for (d2 = GetSucc(d1); d2; d2 = GetSucc(d2)) {
	    if (strcmp(d1->Left, d2->Left) == 0 && d1->Common != d2->Common)
		Combine(d1, d2);
	}
    }
}

Combine(d1, d2)
DEPEND *d1, *d2;
{
    register COMMON *c1 = d1->Common;
    register COMMON *c2 = d2->Common;

    if (XDebug) {
	printf("Combine (%s : %s -> %s : %s) com %08lx %08lx (%ld+%ld) %02lx|%02lx\n",
	    d1->Left, d1->Right, d2->Left, d2->Right, c1, c2,
	    c1->RefCnt, c2->RefCnt,
	    c1->Flags, c2->Flags
	);
    }
    c2->RefCnt += c1->RefCnt;
    c2->Flags  |= c1->Flags;
    c1->RefCnt = 0;
    c1->Flags  = 0;
    d1->Common = c2;
}

/*
 *  FINDBEGINPOINT()
 *
 *  The specified left side was requested to execute.  Search the list for
 *  common points (left side the same)
 *
 *  Find those entries whos left sides match this entry's right side
 *  (depth first, recursively) and assign an ordering number.  The ordering
 *  number is essential to guarentee proper execution order of dependancies
 *  since their list positions are random.
 */

FindBeginPoint(db, order, add)
register DEPEND *db;
{
    register DEPEND *dep;

    db->Flags |= DF_ALLOWED;
    db->Order = order;
    order += add;

    for (dep = GetHead(&DepList); dep; dep = GetSucc(dep)) {
	if (dep->Flags & DF_ALLOWED)
	    continue;
	if (strcmp(dep->Left, db->Right) == 0)
	    order = FindBeginPoint(dep, order, add);  /*  DEPTH FIRST    */
    }
    for (dep = GetHead(&DepList); dep; dep = GetSucc(dep)) {
	if (dep->Flags & DF_ALLOWED)
	    continue;
	if (dep->Common == db->Common)                /*  BREADTH SECOND */
	    order = FindBeginPoint(dep, order, add);
    }
    return(order);
}

/*
 *  EXECUTEDEPLIST()
 *				MAIN EXECUTION LOOP
 *
 *  This is the main execution loop for DMake.	It scans the dependancy
 *  list calling appropriate functions, determining associations, and
 *  doing timestamp comparisons if necessary.
 *
 *  (1) For all dependancies which have yet to be handled by this loop
 *	(DF_DIDTHIS is NOT set).
 *
 *	(i) does the right side exist as the left side of some other
 *	    dependancy?  If not
 *
 *	(ii) unless forced or a wildcard, check the file timestamps
 *	     on the left vs right side and set appropriate flags.
 *
 *  (2) Execution phase.  Take the highest priority (lowest Ordered)
 *	dependancy and attempt to execute it.	Collect all dependancies
 *	with a common left side.  At this time any dependancies marked
 *	DF_EXPANDRIGHT must be expanded (this may result in the reference
 *	count becomming non-zero in which case we must abort the execution
 *	phase until the new dependancies have been resolved).
 *
 *	If all non-special (the 'meat', not the exhausted wildcarded
 *	dependancies) timestamp flag checks out, execute the command
 *	list.
 *
 *
 */

ExecuteDepList()
{
    register DEPEND *dep, *dp;
    register short changed = 1;
    DEPEND *lowdep;

    if (Verbose == 1) {
	puts("\nINITIAL DEPLIST");
	PrintDepList(&DepList);
	puts("");
    }

    if (XDebug)
	puts("ExecuteDepList");
    while (changed) {
	char identchanged = 1;

	/*
	 *  (1) Determine highest priority ready dependancy to execute and
	 *	handle datestamp checking.
	 */

	changed = 0;
	if (XDebug)
	    puts("while-changed-loop");
	while (identchanged) {
	    if (XDebug)
		puts("while-ident-changed-loop");
	    identchanged = 0;
	    lowdep = NULL;
	    for (dep = GetHead(&DepList); dep; dep = GetSucc(dep)) {
		if (dep->Common->RefCnt < 0 || !(dep->Flags & DF_ALLOWED))
		    continue;
		if (!(dep->Flags & DF_DIDTHIS)) {
		    /*
		     *	(i) does the right side exist as the left side of
		     *	    some other dependancy?  If not, decrement the
		     *	    reference count and if a wildcard handle
		     *	    expansion.
		     */

		    for (dp = GetHead(&DepList); dp; dp = GetSucc(dp)) {
			if (strcmp(dep->Right, dp->Left) == 0)
			    break;	/* valid references exist   */
		    }


		    if (dp == NULL) { /* don't exist, dec. ref cnt*/
			identchanged = 1;

			--dep->Common->RefCnt;
			dep->Flags |= DF_DIDTHIS;
			if (XDebug)
			    printf("EDL1: DECREMENT REF: %s : %s (%08lx) -> %ld\n",
				dep->Left, dep->Right, dep->Common, dep->Common->RefCnt
			    );

			/*
			 *  handling expansion.  If the right side is a wild
			 *  card defer expansion until the execution phase
			 *  (2).  This is in case files have yet to be
			 *  created that will effect the expansion.  If not
			 *  a wildcard, and not APPLYALL, then we must
			 *  expand the left side (a rare occurance but what
			 *  if somebody does this?:  *.c : charlie)
			 */

			if (IsWildCard(dep->Right))   /* defer expansion unless a-a */
			    dep->Flags |= DF_EXPANDRIGHT;
			else if (dep->Common->RefCnt == 0) {
			    if (IsWildCard(dep->Left) && !(dep->Flags & DF_APPLYALL))
				DirectoryWildScan(dep, NULL, 1);
			    else
				;/*AddCollect(dep, dep);*/
			}
		    }

		   /*
		    *	(ii)
		    *  Unless forced or a wildcard, we do a time-date comparison
		    *  on the left and right side.  If the right side does not
		    *  exist as a file, nothing changes.  If the right side
		    *  DOES exist as a file, the time-date comparison overides
		    *  anything propogated from below.	This allows:
		    *
		    *  $(OBJS) : $(SRCS)
		    *	   cc ..
		    *
		    *  $(SRCS) : ram:symbols.m
		    */

		    if (!(dep->Flags & DF_OUTDATED) && !ForceAll && IsWildCard(dep->Left) == 0) {
			short validright;
			short od = OutDated(dep->Left, dep->Right, &validright);

			if (Verbose == 2)
			    printf("COMPARE %s : %s, od = %ld  vr = %ld\n", dep->Left, dep->Right, od, validright);
			if (validright && !(dep->Flags & DF_OUTDATED)) {
			    if (od)
				dep->Flags |= DF_OUTDATED;
			    else
				dep->Flags |= DF_DATEDOK;
			}
		    }
		}
		if (dep->Common->RefCnt != 0)
		    continue;
		if (lowdep == NULL || dep->Order < lowdep->Order)
		    lowdep = dep;
	    }
	}
	if (Verbose == 1) {
	    puts("\nSTABLE DEPLIST:");
	    PrintDepList(&DepList);
	    puts("");
	}

	/*
	 *  (2) Execution phase.                    **************
	 *
	 */

	dep = lowdep;
	if (dep == NULL || dep->Common->RefCnt != 0)
	    continue;
	changed = 1;

	if (Verbose)
	    printf("PICKED: %s : %s (seq# %d)\n", dep->Left, dep->Right, dep->Order);

	/*
	 *  References have fallen to zero.  We must scan the dependancies
	 *  for all common nodes (common to left hand side), combine
	 *  various collected variables (i.e. *.c etc..) and do a single
	 *  execution run.
	 *
	 *  But, if a right hand side is a wildcard and therefore has
	 *  not been determined yet, we must do a DirectoryWildScan()
	 *  and if the refcnt is no longer 0 abort the execution.
	 */

	if (XDebug) {
	    printf("\nEDL: Refs have fallen to 0 %s : %s (%08lx)\n",
		dep->Left, dep->Right, dep->Common
	    );
	    PrintDepList(&DepList);
	}

	{
	    MLIST exelist;
	    DEPEND *nextdp;
	    char numdatedok = 0;
	    char numdeps    = 0;

	    NewList(&exelist);
	    for (dp = GetHead(&DepList); dp; dp = nextdp) {
		nextdp = GetSucc(dp);

		/*
		 *  Gather the common entries together into a list.
		 *  Look at the time stamp information and handle that.
		 *  Collect all non-wildcarded entries into a separate list
		 *  in preparation for execution.
		 */

		if (dep->Common == dp->Common && (dp->Flags & DF_DIDTHIS)) {
		    if (XDebug)
			printf("ready exe date: %s : %s  %02lx\n", dp->Left, dp->Right, dp->Flags & DF_DATEDOK);
		    if (dp->Flags & DF_EXPANDRIGHT) {
			dp->Flags &= ~DF_EXPANDRIGHT;
			DirectoryWildScan(dp, NULL, 0);
		    }

		    if (IsWildCard(dp->Right)) {
			if (XDebug)
			    printf("Warn: IsWildCard! %s : %s\n", dp->Left, dp->Right);
		    } else {	/*  remove into separate list */
			++numdeps;
			if ((dp->Flags & DF_DATEDOK) && !(dp->Flags & DF_OUTDATED))
			    ++numdatedok;
			Remove(dp);
			AddTail(&exelist, dp);
		    }
		}
	    }

	    /*
	     *	If there are any dependancies in the list, the reference
	     *	count is still 0, the left side is not a wildcard, and the
	     *	date doesn't checkout, execute the list.    Set the common
	     *	flags according to whether the list was executed or not
	     *	(propogation upwards of the timestamp comparison results).
	     */

	    if (dep->Common->RefCnt == 0 && GetHead(&exelist) && !IsWildCard(dep->Left)) {
		if (numdeps != numdatedok || numdeps == 0) {
		    ExecuteCmdCollection(&exelist);
		    dep->Common->Flags |= DF_OUTDATED;
		} else {
		    dep->Common->Flags |= DF_DATEDOK;
		}
	    }
	    while (dp = RemHead(&exelist))
		AddTail(&DepList, dp);
	}

	/*
	 *  RefCnt != 0, abort cleanup
	 */

	if (dep->Common->RefCnt != 0)
	    continue;

	dep->Common->RefCnt = -1;   /*	RAN!	*/

	/*
	 *  After execution has completed, decrement any occurances
	 *  of our left side (now complete) on the right of other
	 *  dependancies.
	 */

	for (dp = GetHead(&DepList); dp; dp = GetSucc(dp)) {
	    if (strcmp(dep->Left, dp->Right) == 0 && !(dp->Flags & DF_DIDTHIS)) {
		--dp->Common->RefCnt;
		dp->Flags |= DF_DIDTHIS;
		if (XDebug)
		    printf("EDL2: DECREMENT REF (RHR): %s : %s (%08lx) -> %ld\n",
			dp->Left, dp->Right, dp->Common, dp->Common->RefCnt
		    );
		/*
		 *  If all of the dependancies for dep->Left had a valid
		 *  time (nothing needed to be executed), propogate the
		 *  information upwards.
		 */

		dp->Flags |= dep->Common->Flags & (DF_DATEDOK | DF_OUTDATED);
		if (Verbose == 2) {
		    if (dep->Common->Flags & DF_OUTDATED)
			printf("Propogate outdated (%s:%s) -> (%s:%s)\n", dep->Left, dep->Right, dp->Left, dp->Right);
		    else if (dep->Common->Flags & DF_DATEDOK)
			printf("Propogate date ok (%s:%s) -> (%s:%s)\n", dep->Left, dep->Right, dp->Left, dp->Right);
		}
		if (IsWildCard(dp->Right))    /* defer expansion ??APPLYALL */
		    dp->Flags |= DF_EXPANDRIGHT;
		if (dp->Common->RefCnt == 0) {
		    if (IsWildCard(dp->Left) && !(dp->Flags & DF_APPLYALL))
			DirectoryWildScan(dp, NULL, 1);
		}
	    }

	    if (XDebug)
		PrintDepList(&DepList);
	}
    }
    if (XDebug) {
	puts("ExecuteDepList End");
	PrintDepList(&DepList);
    }
}

/*
 *  ExecuteCmdCollect()
 *
 *	Given a list of dependancies (all with the same left side), add
 *	their right sides into the %(variable) table under the name
 *	specified by their collection entry.  This is how all those object
 *	modules in all : *.o get combined to so the programmer can
 *	specify %(*.o) in the command list.
 *
 */

ExecuteCmdCollection(list)
MLIST *list;
{
    register DEPEND *dep = GetHead(list);

    if (XDebug) {
	printf("EXECUTE %s :", dep->Left);
	for (; dep; dep = GetSucc(dep))
	    printf("<%s> ", dep->Right);
	puts("");
    }
    ResetVarCollector();
    for (dep = GetHead(list); dep; dep = GetSucc(dep)) {
	if (dep->ColDep)
	    AddVarCollector(dep->Right, dep->ColDep->Right, 1);
	else
	    AddVarCollector(dep->Right, dep->Right, 1);
	AddVarCollector(dep->Right, "right", 0);
    }
    dep = GetHead(list);
    AddVarCollector(dep->Left, "left", 0);
    ExecuteCmdList(dep->CmdList);
}

/*
 *  Test if a file contains a wildcard or not.
 */

IsWildCard(str)
register char *str;
{
    while (*str) {
	if (*str == '*' || *str == '?')
	    return(1);
	++str;
    }
    return(0);
}

/*
 *  DirectoryWildScan(dep, autolist, scanleft)
 *
 *  This is the major wildcard dependancy handling call.
 *
 *  (1) If we have *.o : <any>  which is flagged DF_APPLYALL (any must
 *	depend on each derived .o file), we cannot handle the dependancy
 *	at this point so we undo the DF_DIDTHIS flag and return.
 *
 *  (2) Either the right side is expanded and the left side derived or
 *	the left side is expanded and the right side derived.  When one
 *	side is expanded, if the other side is NOT a wildcard it is left
 *	alone ( all:*.c -> all:a.c, all:b.c, all:c.c etc.. ).
 *
 *  (3)
 *
 */

DirectoryWildScan(dep, autolist, scanleft)
DEPEND *dep;
MLIST *autolist;
{
    MLIST DList;
    register DEPEND *dp;
    short iswcleft = IsWildCard(dep->Left);

    if (XDebug)
	printf("DirectoryWildScan: %s : %s  (%ld)\n", dep->Left, dep->Right, scanleft);
    NewList(&DList);

    /*
     *	(1) Unless scanleft is set (set when we must expand ONE side because
     *	    it *IS* DF_APPLYALL, i.e. *.c : *.h -> a.c : *.h, b.c : *.h),
     *	    we defer DF_APPLYALL operation until all other associated
     *	    dependancies have been resolved.  Otherwise we would be forced
     *	    to evaluate the left-side wildcard too early .. perhaps before
     *	    the files have been created.
     */

    if (!scanleft && iswcleft && (dep->Flags & DF_APPLYALL)) {
	++dep->Common->RefCnt;
	dep->Flags &= ~DF_DIDTHIS;
	return(0);
    }

    /*
     *	(2) Expand either the left side or the right side.  Do either
     *	    a directory scan or use a predetermined list.  Handle the
     *	    three cases: <wild>:<wild>, <norm>:<wild>, <wild:norm>
     *
     *	    The only time <wild>:<wild> will occur is with the DF_APPLYALL
     *	    case.
     */

    {
	char *left = (iswcleft) ? dep->Left : dep->Right;
	char *right= (scanleft) ? dep->Left : dep->Right;

	if (autolist)
	    AutoExpandRightSide(&DList, left, right, autolist);
	else
	    ExpandRightSide(&DList, left, right);

	/*
	 *  if not wc must set left side all the same (cause we did a hack
	 *  above so we could call the Virtuo routine).  Also, assign the
	 *
	 *  if scanleft (left side guarenteed to be a wildcard), we need
	 *  to set the right side all the same (cause... )
	 */

	for (dp = GetHead(&DList); dp; dp = GetSucc(dp)) {
	    dp->Flags |= DF_ALLOWED;
	    dp->Order = dep->Order;
	    if (iswcleft == 0)
		dp->Left = dep->Left;
	    else if (scanleft)
		dp->Right= dep->Right;
	    AddCollect(dp, dep);
	}

	CombineRefCnts(&DList);    /*  combine reference counts for new left sides */

    }

    /*
     *	(3) If the left side is not a wildcard we are done for now.
     */

    if (XDebug)
	puts("Main Combinational complete");

    if (iswcleft == 0) {
	if (XDebug)
	    puts("Left side not wc, end");
	while (dp = RemHead(&DList)) {
	    dp->CmdList = dep->CmdList;
	    Order = FindBeginPoint(dp, Order, 1);
	    AddTail(&DepList, dp);
	}
	return(1);
    }

    /*
     *	(3) If the left side IS a wildcard, then scan the list for two cases
     *	    (a) if the left wildcard appears on the LEFT side of any other
     *		dependancy in which DF_APPLYALL is set, we must break up
     *		those dependancies.
     *
     *		    *.o : *.c *.h -> *.o : *.c and *.o : *.h (APPLYALL),
     *		    when *.o : *.c is resolved in (1)&(2), we must break up
     *		    the apply all case *.o : *.h -> a.o : *.h, b.o : *.h
     *		    etc...
     *
     *	    (b) if the left wildcard appears on the RIGHT side of any
     *		other dependancy we must expand them as well:
     *
     *		    all : *.o
     *		    *.o : *.c	when *.o : *.c is resolved, we must also
     *		    resolve all : *.o -> all : a.o, all : b.o
     *
     *		NOTE:	all : *.o is allowed to DF_DIDTHIS since several
     *		dependancies might reference it:
     *
     *		    *.o : *.c
     *		    *.o : *.asm
     *
     *		There are THREE cases in this expansion.  (i) the left side
     *		of the found dep (i.e. all : *.o in the example above) is
     *		NOT a wildcard (simple).  (ii) the left side IS a wildcard
     *		and DF_APPLYALL is set, (iii) the left side IS a wildcard
     *		and DF_APPLYALL is not set.
     *
     *		    (i) all : *.o   -> all : a.o, all : b.o
     *		   (ii) *.x : *.h   -> *.x : mike.h, *.x : ben.h
     *			     ^DF_APPLYALL (ii)
     *		  (iii) *.x : *.o   -> a.x : a.o, b.x : b.o
     */

    for (dp = GetHead(&DepList); dp; dp = GetSucc(dp)) {
	/*
	 *  (3a)
	 */
	if (strcmp(dep->Left, dp->Left) == 0 && (dp->Flags & DF_APPLYALL)) {
	    DEPEND *dp2, *newdep;

	    if (!(dp->Flags & DF_DIDTHIS)) {
		--dp->Common->RefCnt;
		dp->Flags |= DF_DIDTHIS;
	    }
	    dp->Flags &= ~(DF_APPLYALL | DF_EXPANDRIGHT);

	    if (XDebug)
		printf("DidThis FLAG SET (DWS1) for %s : %s (%ld)\n",
		    dp->Left, dp->Right, dp->Common->RefCnt
		);

	    /*
	     *	For each expanded left side, generate left : wildright
	     */

	    for (dp2 = GetHead(&DList); dp2; dp2 = GetSucc(dp2)) {
		newdep = MakeOneDepend(dp2->Common, &DepList, dp2->Left, dp->Right);
		newdep->Order = dp2->Order;
		newdep->Flags |= DF_ALLOWED;
		newdep->CmdList = dp->CmdList;
		AddCollect(newdep, dp);
		if (XDebug)
		    printf("*** Created APPLYALL dep: %s : %s\n", newdep->Left, newdep->Right);
	    }
	}

	/*
	 *  If our wild left side appears on the right side of anybody
	 *  else, we must expand them.	How we expand them depends whether
	 *  they are wildcarded &| APPLYALL.
	 *
	 *  (3b.i,ii,iii)
	 */

	if (strcmp(dep->Left, dp->Right) == 0 && (dp->Flags & DF_ALLOWED)) {
	    if (XDebug)
		printf("DidThis FLAG SET (DWS2) for %s : %s (%ld)(%08lx)\n",
		    dp->Left, dp->Right, dp->Common->RefCnt, dp
		);
	    if (!(dp->Flags & DF_DIDTHIS)) {
		if (XDebug)
		    printf("SET %08lx ref %08lx\n", dp, dp->Common);
		--dp->Common->RefCnt;
		dp->Flags |= DF_DIDTHIS;
	    } else {
		if (XDebug)
		    printf("NOTSET %08lx ref %08lx\n", dp, dp->Common);
	    }
	    if (dp->Common->RefCnt < 0) {
		puts("INTERNAL ERROR #Directory-1");
		xexit(30);
	    }

	    /*
	     *	(3b. i, ii, iii).  Here (i) is taken care of by checking
	     *	if the left side is a wildcard... we skip the if. Inside
	     *	the if (ii) and (iii) are handled.
	     */

	    if (IsWildCard(dp->Left)) {     /* create mult refs to mult objects   */
		/*
		 * (ii) APPLYALL flagged
		 */
		if (dp->Flags & DF_APPLYALL) {
		    DEPEND *dp2, *newdep;

		    if (!(dp->Flags & DF_DIDTHIS)) {
			dp->Flags |= DF_DIDTHIS;
			--dp->Common->RefCnt;
			for (dp2 = GetHead(&DList); dp2; dp2 = GetSucc(dp2)) {
			    newdep = MakeOneDepend(dp->Common, &DepList, dp->Left, dp2->Left);
			    newdep->Order = dp->Order;
			    if (XDebug)
				printf("Common: %s : %s  now %d\n", dp->Left, dp->Right, dp->Common->RefCnt);
			    newdep->Flags |= DF_ALLOWED | DF_APPLYALL;
			    newdep->CmdList = dp->CmdList;
			    AddCollect(newdep, dp);     /* RefCnt must be stable */
			}
		    }
		} else {
		    /*
		     *	(iii) *.o : *.c -> a.o : a.c, b.o : b.c etc...
		     *		Simple recurse.
		     */

		    DirectoryWildScan(dp, &DList, 0);
		}
	    } else {			    /* create multiple refs to one object */
		/*
		 *  (i) left side is not a wildcard, all : *.o
		 */

		DEPEND *dp2, *newdep;

		for (dp2 = GetHead(&DList); dp2; dp2 = GetSucc(dp2)) {
		    newdep = MakeOneDepend(dp->Common, &DepList, dp->Left, dp2->Left);
		    newdep->Order = dp->Order;
		    if (XDebug)
			printf("Common: %s : %s  now %d\n", dp->Left, dp->Right, dp->Common->RefCnt);
		    newdep->Flags |= DF_ALLOWED;
		    newdep->CmdList = dp->CmdList;
		    AddCollect(newdep, dp);     /* RefCnt must be stable */
		}
	    }
	}
    }

    /*
     *	For each of the new dependancies, FindBeginPoint() them (to handle
     *	special cases for wildcarded objects) and add them to the main list.
     *	Also note that we must CombineRefCnts() to combine the common
     *	structures (all dependancies with the same left side must point
     *	to the same shared common structure).
     *
     *	(4) i.e. you have   *.o : *.c  and also have a special case like
     *	    charlie.o : cook_takes_the_cake
     *
     */

    CombineRefCnts(&DList);

    while (dp = RemHead(&DList)) {
	dp->CmdList = dep->CmdList;
	FindBeginPoint(dp, dep->Order, 0);
	AddTail(&DepList, dp);
    }
    return(1);
}

/*
 *  AutoExpandRightSide()
 *
 *  This routine works like ExpandRightSide(), but instead of scanning a
 *  directory it derives the results from a passed list of dependancies.
 *  The reasoning behind this follows:	 ram:*.o : *.c , DMake will
 *  scan the directory for *.c and derive ram:*.o without scaning ram:.
 *  After all, there might be additional .o files in ram: that we do NOT
 *  want to include.
 *
 *  The previously found file's left side matches the new right side.
 */

AutoExpandRightSide(newlist, left, right, oldlist)
MLIST *newlist;
char *left;
char *right;
MLIST *oldlist;
{
    register DEPEND *dp;

    if (XDebug)
	printf("AutoExpandRightSide %s : %s\n", left, right);
    for (dp = GetHead(oldlist); dp; dp = GetSucc(dp)) {
	MakeOneDepend(NULL, newlist, VirtuoExpand(left, right, dp->Left), dp->Left);
    }
    if (XDebug)
	puts("AutoExpandRightSide done");
}

/*
 *  ExpandRightSide()
 *
 *  This routine does a directory scan of the right side and creates
 *  a set of dependancies, placing them in the specified list.
 */

ExpandRightSide(newlist, left, right)
MLIST *newlist;
char *left;
char *right;
{
    char *ptr;
    int ac;
    register char **av;
    register short i;
    char **expand();

    if (XDebug)
	printf("ExpandRightSide <%s> : <%s>\n", left, right);
    av = expand(right, &ac);
    if (XDebug) {
	for (i = 0; i < ac; ++i)
	    printf("(%s)", av[i]);
	puts("");
    }

    for (i = 0; i < ac; ++i)
	MakeOneDepend(NULL, newlist, VirtuoExpand(left, right, av[i]), av[i]);
    if (XDebug)
	puts("ExpandRightSide done");
}

/*
 *  VirtuoExpand("x*.poof", "*.o", "charlie.o") -> xcharlie.poof
 *
 *  This converts a filename from one name to another using the two
 *  provided wildcards (old and new).
 */

char *
VirtuoExpand(newwc, oldwc, filename)
register char *newwc, *oldwc, *filename;
{
    char *newbase = newwc;

    if (XDebug)
	printf("VEIN: <%s> <%s> <%s>\n", newwc, oldwc, filename);
    {					/*  skip non-wildcards	*/
	register char *old = oldwc;
	register char *name = filename;

	while (*old && *old != '*' && *old != '?') {
	    if (*name != *old)      /*  failure!    */
		return(NULL);
	    ++name;
	    ++old;
	}
	oldwc = old;
	filename = name;
    }
    {					/* skip non wildcards in new */
	register char *new = newwc;
	while (*new && *new != '*' && *new != '?')
	    ++new;
	newwc = new;
    }
    if (*newwc != *oldwc)           /*  new pattern must match old */
	return(NULL);
    if (*oldwc == 0 && *filename == 0)
	return(newbase);            /*  success!                   */
    /*
     *	at this point, *oldwc == *newwc == '*' or '?'
     */

    if (*oldwc == '?') {            /*  match a single char in *filename   */
	char *last = VirtuoExpand(newwc + 1, oldwc + 1, filename + 1);
	char *str;
	short i;

	if (!last)
	    return(NULL);
	/*
	 *  combine (newbase..newwc) with *filename with last
	 */
	i = newwc - newbase;
	str = malloc(i + strlen(last) + 2);
	movmem(newbase, str, i);
	str[i] = *filename;
	strcpy(str+i+1, last);
	return(str);
    }

    /*
     *	*oldwc == *newwc == '*', we must try to match all or part of
     *	the remaining filename.
     */

    {
	char *fi = filename + strlen(filename);

	while (fi >= filename) {
	    char *last;
	    char *str;
	    short i, j;

	    if (last = VirtuoExpand(newwc + 1, oldwc + 1, fi)) {
		/*
		 *  combine (newbase..newwc with filename..fi with last
		 */
		i = newwc - newbase;
		j = fi - filename;
		str = malloc(i + j + strlen(last) + 1);
		movmem(newbase, str, i);
		movmem(filename, str + i, j);
		strcpy(str + i + j, last);
		return(str);
	    }
	    --fi;
	}
    }
    return(NULL);
}

/*
 *  CreateDependancies()
 *
 *  Given a just-parsed line from the initial file scan, this routine
 *  breaks it up into individual dependancies with a left and right side.
 *
 *  It is pretty straight forward (see the dmake rules).  Note that the
 *  APPLYALL flag must be set for dependancies like this:
 *	    *.o : *.c *.h	(set APPLYALL for *.o : *.h to prevent
 *				it from being misinterpreted later)
 *
 *  each .c files depends on its .o file, but each .o files depends on
 *  ALL the .h files.
 */

CreateDependancies(cmdlist, av, ls, le, rs, re)
MLIST *cmdlist;
char **av;
short ls, le, rs, re;
{
    register short i;
    MLIST deplist;

    NewList(&deplist);

    if (Verbose == 4) {
	printf("CreateDependancies %08lx %08lx %ld %ld %ld %ld\n",
	    cmdlist, av, ls, le, rs, re
	);
	for (i = 0; i + ls < le; ++i)
	    printf("left: %08lx <%s>\n", av[ls+i], av[ls+i]);
	for (i = 0; i + rs < re; ++i)
	    printf("rght: %08lx <%s>\n", av[rs+i], av[rs+i]);
    }

    for (i = 0; ls + i < le && rs + i < re; ++i) {
	MakeOneDepend(NULL, &deplist, av[ls+i], av[rs+i]);
    }
    while (ls + i < le) {   /*  only left guys remain               */
	if (rs == re) {     /*  special case, right side was empty  */
	    MakeOneDepend(NULL, &deplist, av[ls + i], NULL);
	} else if (rs + 1 == re) {
	    MakeOneDepend(NULL, &deplist, av[ls + i], av[rs]);
	} else {
	    printf("Error line %ld.  Under normal conditions one has the\n", LineNo);
	    puts("same number of dependancies on the left as on the right,");
	    puts("or more on the right.  The only two cases allowed for more");
	    puts("on the left is when the right has 0 or 1 arguments");
	    xexit(25);
	}
	++i;
    }

    {	/*  only right guys remain.  Make all left's dep. on them.  */
	/*  note: operation must be defered for wildcards on left   */

	register DEPEND *dbase = GetTail(&deplist);
	if (dbase) {
	    while (rs + i < re) {
		register DEPEND *dep, *new;
		for (dep = dbase; dep; dep = GetPred(dep)) {
		    new = MakeOneDepend(dep->Common, &deplist, dep->Left, av[rs + i]);
		    if (IsWildCard(new->Left) /*&& !IsWildCard(new->Right)*/)
			new->Flags |= DF_APPLYALL;
		}
		++i;
	    }
	}
    }

    {
	register DEPEND *dep;
	while (dep = RemHead(&deplist)) {
	    dep->CmdList = cmdlist;
	    AddTail(&DepList, dep);
	}
    }
}

/*
 *  MakeOneDepend()
 *
 *  Note: the fact that it adds to the tail of the list is counted on in
 *  an earlier routine.  This creates a new dependancy.  Note, however,
 *  that the common node might be allocated thus invalidating the rule
 *  that all dependancies with the same dep->Left have the same common
 *  structure.	This is dealt with by calling CombineRefCnts().
 */

DEPEND *
MakeOneDepend(common, list, left, right)
register COMMON *common;
MLIST *list;
char *left;
char *right;
{
    register DEPEND *dep = malloc(sizeof(DEPEND));
    if (!common) {
	common = malloc(sizeof(COMMON));
	clrmem(common, sizeof(COMMON));
    }
    clrmem(dep, sizeof(DEPEND));

    ++common->RefCnt;
    dep->Common = common;
    dep->Left = left;
    dep->Right= (right) ? right : "";
    AddTail(list, dep);
    if (XDebug)
	printf("MakeOneDepend dep %08lx com %08lx %d %s : %s\n", dep, common, common->RefCnt, left, right);
    return(dep);
}

/*
 *  ADDCOLLECT()
 *
 *  Set dep's collection to dp (always dp->Right).  I.E. when you have
 *  something like:  *.o : *.c *.h, cc %(*.c) -o %(left).  The individual
 *  C files get placed in the *.c collection one at a time so they can be
 *  referenced by a % variable
 */

AddCollect(dep, dp)
register DEPEND *dep;
DEPEND *dp;
{
    dep->Flags |= DF_COLLECT;
    dep->Common->Flags |= DF_COLLECT;
    dep->ColDep = dp;
}

/*
 *  low level routines
 */

char LineBuf[4096];

char *
getline(fi, pcmmnt)
FILE *fi;
short *pcmmnt;
{
    register short i = 0;
    if (pcmmnt)
	*pcmmnt = 0;
    while (fgets(LineBuf + i, sizeof(LineBuf) - i, fi)) {
	if (i == 0 && LineBuf[i] == '#') {
	    LineBuf[i] = 0;
	    if (pcmmnt)
		*pcmmnt = 1;
	}
	i += MacroReplace(0, LineBuf + i, strlen(LineBuf + i));
	while (i-- && (LineBuf[i] == '\n' || LineBuf[i] == '\t' || LineBuf[i] == ' '))
	    LineBuf[i] = 0;
	if (LineBuf[i] == '\\')     /*  line continuance    */
	    continue;
	if (XDebug)
	    printf("LINE: %s\n", LineBuf);
	return(LineBuf);
    }
    return(NULL);
}

char **
parseline(ptr, pac)
register char *ptr;
short *pac;
{
    char *pbuf = malloc(strlen(ptr)+1);
    static char *av[1024];
    register short ac = 0;

    strcpy(pbuf, ptr);
    ptr = pbuf;
    while (*ptr) {
	while (*ptr == ' ' || *ptr == '\t')
	    ++ptr;
	av[ac++] = ptr;
	while (*ptr && *ptr != ' ' && *ptr != '\t')
	    ++ptr;
	if (*ptr)
	    *ptr++ = 0;
    }
    *pac = ac;
    return(av);
}

PrintDepList(list)
MLIST *list;
{
    register DEPEND *dep;

    puts("(DEP LIST)");
    for (dep = GetHead(list); dep; dep = GetSucc(dep)) {
	printf("dep: %02lx %2ld (#%2ld)(%08lx) %s : %s",
	    dep->Flags,
	    dep->Common->RefCnt,
	    dep->Order,
	    dep->Common,
	    dep->Left,
	    dep->Right
	);
	if (dep->Flags & DF_COLLECT) {
	    printf("  (collect to %s)", dep->ColDep->Right);
	}
	puts("");
    }
    puts("(END OF DEP LIST)");
}