path: root/usr.bin/make/make.c

/*	$OpenBSD: make.c,v 1.70 2015/08/21 02:19:49 jsg Exp $	*/
/*	$NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $	*/

/*
 * Copyright (c) 1988, 1989, 1990, 1993
 *	The Regents of the University of California.  All rights reserved.
 * Copyright (c) 1989 by Berkeley Softworks
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Adam de Boor.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*-
 * make.c --
 *	The functions which perform the examination of targets and
 *	their suitability for creation
 *
 * Interface:
 *	Make_Run		Initialize things for the module and recreate
 *				whatever needs recreating. Returns true if
 *				work was (or would have been) done and
 *				false
 *				otherwise.
 *
 *	Make_Update		Update all parents of a given child. Performs
 *				various bookkeeping chores like finding the
 *				youngest child of the parent, filling
 *				the IMPSRC context variable, etc. It will
 *				place the parent on the toBeMade queue if it
 *				should be.
 *
 */

#include <limits.h>
#include <signal.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ohash.h>
#include "config.h"
#include "defines.h"
#include "dir.h"
#include "job.h"
#include "suff.h"
#include "var.h"
#include "error.h"
#include "make.h"
#include "gnode.h"
#include "extern.h"
#include "timestamp.h"
#include "engine.h"
#include "lst.h"
#include "targ.h"
#include "targequiv.h"
#include "garray.h"
#include "memory.h"

/* what gets added each time. Kept as one static array so that it doesn't
 * get resized every time.
 */
static struct growableArray examine;
/* The current fringe of the graph. These are nodes which await examination by
 * MakeOODate. It is added to by Make_Update and subtracted from by
 * MakeStartJobs */
static struct growableArray toBeMade;	

/* Hold back on nodes where equivalent stuff is already building... */
static struct growableArray heldBack;

static struct ohash targets;	/* stuff we must build */

static void MakeAddChild(void *, void *);
static void MakeHandleUse(void *, void *);
static bool MakeStartJobs(void);
static void MakePrintStatus(void *, void *);
static bool try_to_make_node(GNode *);
static void add_targets_to_make(Lst);

static bool has_unmade_predecessor(GNode *);
static void requeue_successors(GNode *);
static void random_setup(void);

static bool randomize_queue;
long random_delay = 0;

bool 
no_jobs_left()
{
	return Array_IsEmpty(&toBeMade);
}

static void
random_setup()
{
	randomize_queue = Var_Definedi("RANDOM_ORDER", NULL);

/* no random delay in the new engine for now */
#if 0
	if (Var_Definedi("RANDOM_DELAY", NULL))
		random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000, 
		    NULL) * 1000000;
#endif

}

static void
randomize_garray(struct growableArray *g)
{
	/* This is a fairly standard algorithm to randomize an array. */
	unsigned int i, v;
	GNode *e;

	for (i = g->n; i > 0; i--) {
		v = arc4random_uniform(i);
		if (v == i-1)
			continue;
		else {
			e = g->a[i-1];
			g->a[i-1] = g->a[v];
			g->a[v] = e;
		}
	}
}

static bool
has_unmade_predecessor(GNode *gn)
{
	LstNode ln;

	if (Lst_IsEmpty(&gn->preds))
		return false;


	for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)) {
		GNode	*pgn = (GNode *)Lst_Datum(ln);

		if (pgn->must_make && pgn->built_status == UNKNOWN) {
			if (DEBUG(MAKE))
				printf("predecessor %s not made yet.\n", 
				    pgn->name);
			return true;
		}
	}
	return false;
}

static void
requeue_successors(GNode *gn)
{
	LstNode ln;
	/* Deal with successor nodes. If any is marked for making and has an
	 * unmade count of 0, has not been made and isn't in the examination
	 * queue, it means we need to place it in the queue as it restrained
	 * itself before.	*/
	for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) {
		GNode	*succ = (GNode *)Lst_Datum(ln);

		if (succ->must_make && succ->unmade == 0 
		    && succ->built_status == UNKNOWN)
			Array_PushNew(&toBeMade, succ);
	}
}

static void
requeue(GNode *gn)
{
	/* this is where we go inside the array and move things around */
	unsigned int i, j;

	for (i = 0, j = 0; i < heldBack.n; i++, j++) {
		if (heldBack.a[i]->watched == gn) {
			j--;
			heldBack.a[i]->built_status = UNKNOWN;
			if (DEBUG(HELDJOBS))
				printf("%s finished, releasing: %s\n", 
				    gn->name, heldBack.a[i]->name);
			Array_Push(&toBeMade, heldBack.a[i]);
			continue;
		}
		heldBack.a[j] = heldBack.a[i];
	}
	heldBack.n = j;
}

/*-
 *-----------------------------------------------------------------------
 * Make_Update	--
 *	Perform update on the parents of a node. Used by JobFinish once
 *	a node has been dealt with and by MakeStartJobs if it finds an
 *	up-to-date node.
 *
 * Results:
 *	Always returns 0
 *
 * Side Effects:
 *	The unmade field of pgn is decremented and pgn may be placed on
 *	the toBeMade queue if this field becomes 0.
 *
 *	If the child was made, the parent's childMade field will be set to
 *	true
 *-----------------------------------------------------------------------
 */
void
Make_Update(GNode *cgn)	/* the child node */
{
	GNode	*pgn;	/* the parent node */
	LstNode	ln;	/* Element in parents list */

	/*
	 * If the child was actually made, see what its modification time is
	 * now -- some rules won't actually update the file. If the file still
	 * doesn't exist, make its mtime now.
	 */
	if (cgn->built_status != UPTODATE) {
		/*
		 * This is what Make does and it's actually a good thing, as it
		 * allows rules like
		 *
		 *	cmp -s y.tab.h parse.h || cp y.tab.h parse.h
		 *
		 * to function as intended. Unfortunately, thanks to the
		 * stateless nature of NFS, there are times when the
		 * modification time of a file created on a remote machine
		 * will not be modified before the local stat() implied by
		 * the Dir_MTime occurs, thus leading us to believe that the
		 * file is unchanged, wreaking havoc with files that depend
		 * on this one.
		 */
		if (noExecute || is_out_of_date(Dir_MTime(cgn)))
			clock_gettime(CLOCK_REALTIME, &cgn->mtime);
		if (DEBUG(MAKE))
			printf("update time: %s\n", 
			    time_to_string(&cgn->mtime));
	}

	requeue(cgn);
	/* SIB: this is where I should mark the build as finished */
	for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
		pgn = (GNode *)Lst_Datum(ln);
		/* SIB: there should be a siblings loop there */
		pgn->unmade--;
		if (pgn->must_make) {
			if (DEBUG(MAKE))
				printf("%s--=%d ", 
				    pgn->name, pgn->unmade);

			if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
				if (cgn->built_status == MADE)
					pgn->childMade = true;
				(void)Make_TimeStamp(pgn, cgn);
			}
			if (pgn->unmade == 0) {
				/*
				 * Queue the node up -- any unmade
				 * predecessors will be dealt with in
				 * MakeStartJobs.
				 */
				if (DEBUG(MAKE))
					printf("QUEUING ");
				Array_Push(&toBeMade, pgn);
			} else if (pgn->unmade < 0) {
				Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
			}
		}
	}
	if (DEBUG(MAKE))
		printf("\n");
	requeue_successors(cgn);
}

static bool
try_to_make_node(GNode *gn)
{
	if (DEBUG(MAKE))
		printf("Examining %s...", gn->name);
		
	if (gn->built_status == HELDBACK) {
		if (DEBUG(HELDJOBS))
			printf("%s already held back ???\n", gn->name);
		return false;
	}

	if (gn->unmade != 0) {
		if (DEBUG(MAKE))
			printf(" Requeuing (%d)\n", gn->unmade);
		add_targets_to_make(&gn->children);
		Array_Push(&toBeMade, gn);
		return false;
	}
	if (has_been_built(gn)) {
		if (DEBUG(MAKE))
			printf(" already made\n");
		return false;
	}
	if (has_unmade_predecessor(gn)) {
		if (DEBUG(MAKE))
			printf(" Dropping for now\n");
		return false;
	}

	/* SIB: this is where there should be a siblings loop */
	if (gn->unmade != 0) {
		if (DEBUG(MAKE))
			printf(" Requeuing (after deps: %d)\n", gn->unmade);
		add_targets_to_make(&gn->children);
		return false;
	}
	/* this is where we hold back nodes */
	if (gn->groupling != NULL) {
		GNode *gn2;
		for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling)
			if (gn2->built_status == BUILDING) {
				gn->watched = gn2;
				gn->built_status = HELDBACK;
				if (DEBUG(HELDJOBS))
					printf("Holding back job %s, "
					    "groupling to %s\n", 
					    gn->name, gn2->name);
				Array_Push(&heldBack, gn);
				return false;
			}
	}
	if (gn->sibling != gn) {
		GNode *gn2;
		for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling)
			if (gn2->built_status == BUILDING) {
				gn->watched = gn2;
				gn->built_status = HELDBACK;
				if (DEBUG(HELDJOBS))
					printf("Holding back job %s, "
					    "sibling to %s\n", 
					    gn->name, gn2->name);
				Array_Push(&heldBack, gn);
				return false;
			}
	}
	if (Make_OODate(gn)) {
		if (DEBUG(MAKE))
			printf("out-of-date\n");
		if (queryFlag)
			return true;
		/* SIB: this is where commands should get prepared */
		Make_DoAllVar(gn);
		Job_Make(gn);
	} else {
		if (DEBUG(MAKE))
			printf("up-to-date\n");
		gn->built_status = UPTODATE;
		if (gn->type & OP_JOIN) {
			/*
			 * Even for an up-to-date .JOIN node, we need it
			 * to have its context variables so references
			 * to it get the correct value for .TARGET when
			 * building up the context variables of its
			 * parent(s)...
			 */
			Make_DoAllVar(gn);
		}

		Make_Update(gn);
	}
	return false;
}

/*
 *-----------------------------------------------------------------------
 * MakeStartJobs --
 *	Start as many jobs as possible.
 *
 * Results:
 *	If the query flag was given to pmake, no job will be started,
 *	but as soon as an out-of-date target is found, this function
 *	returns true. At all other times, this function returns false.
 *
 * Side Effects:
 *	Nodes are removed from the toBeMade queue and job table slots
 *	are filled.
 *-----------------------------------------------------------------------
 */
static bool
MakeStartJobs(void)
{
	GNode	*gn;

	while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) {
		if (try_to_make_node(gn))
			return true;
	}
	return false;
}

/*-
 *-----------------------------------------------------------------------
 * MakePrintStatus --
 *	Print the status of a top-level node, viz. it being up-to-date
 *	already or not created due to an error in a lower level.
 *	Callback function for Make_Run via Lst_ForEach.
 *
 * Side Effects:
 *	A message may be printed.
 *-----------------------------------------------------------------------
 */
static void
MakePrintStatus(
    void *gnp,		    /* Node to examine */
    void *cyclep)	    /* True if gn->unmade being non-zero implies
			     * a cycle in the graph, not an error in an
			     * inferior */
{
	GNode	*gn = gnp;
	bool 	*cp = cyclep;
	bool	cycle = *cp;
	if (gn->built_status == UPTODATE) {
		printf("`%s' is up to date.\n", gn->name);
	} else if (gn->unmade != 0) {
		if (cycle) {
			bool t = true;
			/*
			 * If printing cycles and came to one that has unmade
			 * children, print out the cycle by recursing on its
			 * children. Note a cycle like:
			 *	a : b
			 *	b : c
			 *	c : b
			 * will cause this to erroneously complain about a
			 * being in the cycle, but this is a good approximation.
			 */
			if (gn->built_status == CYCLE) {
				Error("Graph cycles through `%s'", gn->name);
				gn->built_status = ENDCYCLE;
				Lst_ForEach(&gn->children, MakePrintStatus, &t);
				gn->built_status = UNKNOWN;
			} else if (gn->built_status != ENDCYCLE) {
				gn->built_status = CYCLE;
				Lst_ForEach(&gn->children, MakePrintStatus, &t);
			}
		} else {
			printf("`%s' not remade because of errors.\n",
			    gn->name);
		}
	}
}


static void
MakeAddChild(void *to_addp, void *ap)
{
	GNode *gn = to_addp;
	struct growableArray *a = ap;

	if (!gn->must_make && !(gn->type & OP_USE))
		Array_Push(a, gn);
}

static void
MakeHandleUse(void *cgnp, void *pgnp)
{
	GNode *cgn = cgnp;
	GNode *pgn = pgnp;

	if (cgn->type & OP_USE)
		Make_HandleUse(cgn, pgn);
}

/* Add stuff to the toBeMade queue. we try to sort things so that stuff 
 * that can be done directly is done right away.  This won't be perfect,
 * since some dependencies are only discovered later (e.g., SuffFindDeps).
 */
static void
add_targets_to_make(Lst todo)
{
	GNode *gn;

	unsigned int slot;

	AppendList2Array(todo, &examine);

	while ((gn = Array_Pop(&examine)) != NULL) {
		if (gn->must_make) 	/* already known */
			continue;
		gn->must_make = true;

		slot = ohash_qlookup(&targets, gn->name);
		if (!ohash_find(&targets, slot))
			ohash_insert(&targets, slot, gn);


		look_harder_for_target(gn);
		kludge_look_harder_for_target(gn);
		/*
		 * Apply any .USE rules before looking for implicit
		 * dependencies to make sure everything that should have
		 * commands has commands ...
		 */
		Lst_ForEach(&gn->children, MakeHandleUse, gn);
		Suff_FindDeps(gn);
		expand_all_children(gn);

		if (gn->unmade != 0) {
			if (DEBUG(MAKE))
				printf("%s: not queuing (%d unmade children)\n",
				    gn->name, gn->unmade);
			Lst_ForEach(&gn->children, MakeAddChild,
			    &examine);
		} else {
			if (DEBUG(MAKE))
				printf("%s: queuing\n", gn->name);
			Array_Push(&toBeMade, gn);
		}
	}
	if (randomize_queue)
		randomize_garray(&toBeMade);
}

/*-
 *-----------------------------------------------------------------------
 * Make_Run --
 *	Initialize the nodes to remake and the list of nodes which are
 *	ready to be made by doing a breadth-first traversal of the graph
 *	starting from the nodes in the given list. Once this traversal
 *	is finished, all the 'leaves' of the graph are in the toBeMade
 *	queue.
 *	Using this queue and the Job module, work back up the graph,
 *	calling on MakeStartJobs to keep the job table as full as
 *	possible.
 *
 * Results:
 *	true if work was done. false otherwise.
 *
 * Side Effects:
 *	The must_make field of all nodes involved in the creation of the given
 *	targets is set to 1. The toBeMade list is set to contain all the
 *	'leaves' of these subgraphs.
 *-----------------------------------------------------------------------
 */
bool
Make_Run(Lst targs)		/* the initial list of targets */
{
	bool problem;	/* errors occurred */
	GNode *gn;
	unsigned int i;
	bool cycle;

	/* wild guess at initial sizes */
	Array_Init(&toBeMade, 500);
	Array_Init(&examine, 150);
	Array_Init(&heldBack, 100);
	ohash_init(&targets, 10, &gnode_info);
	if (DEBUG(PARALLEL))
		random_setup();

	add_targets_to_make(targs);
	if (queryFlag) {
		/*
		 * We wouldn't do any work unless we could start some jobs in
		 * the next loop... (we won't actually start any, of course,
		 * this is just to see if any of the targets was out of date)
		 */
		return MakeStartJobs();
	} else {
		/*
		 * Initialization. At the moment, no jobs are running and until
		 * some get started, nothing will happen since the remaining
		 * upward traversal of the graph is performed by the routines
		 * in job.c upon the finishing of a job. So we fill the Job
		 * table as much as we can before going into our loop.
		 */
		(void)MakeStartJobs();
	}

	/*
	 * Main Loop: The idea here is that the ending of jobs will take
	 * care of the maintenance of data structures and the waiting for output
	 * will cause us to be idle most of the time while our children run as
	 * much as possible. Because the job table is kept as full as possible,
	 * the only time when it will be empty is when all the jobs which need
	 * running have been run, so that is the end condition of this loop.
	 * Note that the Job module will exit if there were any errors unless
	 * the keepgoing flag was given.
	 */
	while (!Job_Empty()) {
		handle_running_jobs();
		(void)MakeStartJobs();
	}

	problem = Job_Finish();
	cycle = false;

	for (gn = ohash_first(&targets, &i); gn != NULL; 
	    gn = ohash_next(&targets, &i)) {
	    	if (has_been_built(gn))
			continue;
		cycle = true;
		problem = true;
	    	printf("Error: target %s unaccounted for (%s)\n", 
		    gn->name, status_to_string(gn));
	}
	/*
	 * Print the final status of each target. E.g. if it wasn't made
	 * because some inferior reported an error.
	 */
	Lst_ForEach(targs, MakePrintStatus, &cycle);
	if (problem)
		Fatal("Errors while building");

	return true;
}