Return to make.c CVS log

Up to [local] / src / usr.bin / make

GC old code that was originally implemented to facilitate adoption by
other BSDs, which never happened, so make things simpler for further
development.

Ditches config.h entirely since it gets reduced to 2 defines.

okay tb@

/*	$OpenBSD: make.c,v 1.84 2023/09/04 11:35:11 espie 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 local variable, etc. It will
 *				place the parent on the to_build 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 "defines.h"
#include "dir.h"
#include "job.h"
#include "suff.h"
#include "var.h"
#include "error.h"
#include "expandchildren.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 to_build;	

/* 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 *);

/* Cycle detection functions */
static bool targets_contain_cycles(void);
static void print_unlink_cycle(struct growableArray *, GNode *);
static void break_and_print_cycles(Lst);
static GNode *find_cycle(Lst, struct growableArray *);

static bool try_to_make_node(GNode *);
static void add_targets_to_make(Lst);

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

static bool randomize_queue;
long random_delay = 0;

bool
nothing_left_to_build()
{
	return Array_IsEmpty(&to_build);
}

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_predecessor_left_to_build(GNode *gn)
{
	LstNode ln;

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


	for (ln = Lst_First(&gn->predecessors); ln != NULL; ln = Lst_Adv(ln)) {
		GNode	*pgn = 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
	 * children_left 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 = Lst_Datum(ln);

		if (succ->must_make && succ->children_left == 0
		    && succ->built_status == UNKNOWN)
			Array_PushNew(&to_build, 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(&to_build, 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 children_left field of pgn is decremented and pgn may be placed on
 *	the to_build queue if this field becomes 0.
 *
 *	If the child got built, the parent's child_rebuilt 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 = Lst_Datum(ln);
		/* SIB: there should be a siblings loop there */
		pgn->children_left--;
		if (pgn->must_make) {
			if (DEBUG(MAKE))
				printf("%s--=%d ",
				    pgn->name, pgn->children_left);

			if ( ! (cgn->type & OP_USE)) {
				if (cgn->built_status == REBUILT)
					pgn->child_rebuilt = true;
				(void)Make_TimeStamp(pgn, cgn);
			}
			if (pgn->children_left == 0) {
				/*
				 * Queue the node up -- any yet-to-build
				 * predecessors will be dealt with in
				 * MakeStartJobs.
				 */
				if (DEBUG(MAKE))
					printf("QUEUING ");
				Array_Push(&to_build, pgn);
			} else if (pgn->children_left < 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->children_left != 0) {
		if (DEBUG(MAKE))
			printf(" Requeuing (%d)\n", gn->children_left);
		add_targets_to_make(&gn->children);
		Array_Push(&to_build, gn);
		return false;
	}
	if (has_been_built(gn)) {
		if (DEBUG(MAKE))
			printf(" already made\n");
		return false;
	}
	if (has_predecessor_left_to_build(gn)) {
		if (DEBUG(MAKE))
			printf(" Dropping for now\n");
		return false;
	}

	/* SIB: this is where there should be a siblings loop */
	if (gn->children_left != 0) {
		if (DEBUG(MAKE))
			printf(" Requeuing (after deps: %d)\n", 
			    gn->children_left);
		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);
		if (node_find_valid_commands(gn)) {
			if (touchFlag)
				Job_Touch(gn);
			else 
				Job_Make(gn);
		} else
			node_failure(gn);
	} else {
		if (DEBUG(MAKE))
			printf("up-to-date\n");
		gn->built_status = UPTODATE;

		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 to_build queue and job table slots
 *	are filled.
 *-----------------------------------------------------------------------
 */
static bool
MakeStartJobs(void)
{
	GNode	*gn;

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

static void
MakePrintStatus(void *gnp)
{
	GNode	*gn = gnp;
	if (gn->built_status == UPTODATE) {
		printf("`%s' is up to date.\n", gn->name);
	} else if (gn->children_left != 0) {
		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 to_build 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->children_left != 0) {
			if (DEBUG(MAKE))
				printf("%s: not queuing (%d child%s left to build)\n",
				    gn->name, gn->children_left, 
				    gn->children_left > 1 ? "ren" : "");
			Lst_ForEach(&gn->children, MakeAddChild,
			    &examine);
		} else {
			if (DEBUG(MAKE))
				printf("%s: queuing\n", gn->name);
			Array_Push(&to_build, gn);
		}
	}
	if (randomize_queue)
		randomize_garray(&to_build);
}

void
Make_Init()
{
	/* wild guess at initial sizes */
	Array_Init(&to_build, 500);
	Array_Init(&examine, 150);
	Array_Init(&heldBack, 100);
	ohash_init(&targets, 10, &gnode_info);
}

/*-
 *-----------------------------------------------------------------------
 * 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 to_build
 *	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.
 *
 * Side Effects:
 *	The must_make field of all nodes involved in the creation of the given
 *	targets is set to 1. The to_build list is set to contain all the
 *	'leaves' of these subgraphs.
 *-----------------------------------------------------------------------
 */
void
Make_Run(Lst targs, bool *has_errors, bool *out_of_date)
{
	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)
		 */
		if (MakeStartJobs())
			*out_of_date = true;
	} 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();
	}

	if (errorJobs != NULL)
		*has_errors = true;

	/*
	 * Print the final status of each target. E.g. if it wasn't made
	 * because some inferior reported an error.
	 */
	if (targets_contain_cycles()) {
		break_and_print_cycles(targs);
		*has_errors = true;
	}
	Lst_Every(targs, MakePrintStatus);
}

/* round-about detection: assume make is bug-free, if there are targets
 * that have not been touched, it means they never were reached, so we can
 * look for a cycle
 */
static bool
targets_contain_cycles(void)
{
	GNode *gn;
	unsigned int i;
	bool cycle = false;
	bool first = true;

	for (gn = ohash_first(&targets, &i); gn != NULL;
	    gn = ohash_next(&targets, &i)) {
	    	if (has_been_built(gn))
			continue;
		cycle = true;
		if (first)
			printf("Error target(s) unaccounted for: ");
		printf("%s ", gn->name);
		first = false;
	}
	if (!first)
		printf("\n");
	return cycle;
}

static void
print_unlink_cycle(struct growableArray *l, GNode *c)
{
	LstNode ln;
	GNode *gn = NULL;
	unsigned int i;
	
	printf("Cycle found: ");

	for (i = 0; i != l->n; i++) {
		gn = l->a[i];
		if (gn == c)
			printf("(");
		printf("%s -> ", gn->name);
	}
	printf("%s)\n", c->name);
	assert(gn);

	/* So the first element is tied to our node, find and kill the link */
	for (ln = Lst_First(&gn->children); ln != NULL; ln = Lst_Adv(ln)) {
		GNode *gn2 = Lst_Datum(ln);
		if (gn2 == c) {
			Lst_Remove(&gn->children, ln);
			return;
		}
	}
	/* this shouldn't happen ever */
	assert(0);
}

/* each call to find_cycle records a cycle in cycle, to break at node c.
 * this will stop eventually.
 */
static void
break_and_print_cycles(Lst t)
{
	struct growableArray cycle;

	Array_Init(&cycle, 16); /* cycles are generally shorter */
	while (1) {
		GNode *c;

		Array_Reset(&cycle);
		c = find_cycle(t, &cycle);
		if (c)
			print_unlink_cycle(&cycle, c);
		else
			break;
	}
	free(cycle.a);
}


static GNode *
find_cycle(Lst l, struct growableArray *cycle)
{
	LstNode ln;

	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
		GNode *gn = Lst_Datum(ln);
		if (gn->in_cycle) {
			/* we should print the cycle and not do more */
			return gn;
		}
		
		if (gn->built_status == UPTODATE)
			continue;
		if (gn->children_left != 0) {
			GNode *c;

			gn->in_cycle = true;
			Array_Push(cycle, gn);
			c = find_cycle(&gn->children, cycle);
			gn->in_cycle = false;
			if (c)
				return c;
			Array_Pop(cycle);
		}
	}
	return NULL;
}