/*	$OpenBSD: make.c,v 1.73 2017/06/22 17:09:10 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 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 *);

/* 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_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()

{

}

static void

random_setup()

{

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

			continue;

		else {

		}

	}

}

static bool

has_unmade_predecessor(GNode *gn)

{

	LstNode ln;

		}

	}

}

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.	*/

	}

static void

requeue(GNode *gn)

{

	/* this is where we go inside the array and move things around */

	unsigned int i, j;

		}

		heldBack.a[j] = heldBack.a[i];

	}

/*-

 *-----------------------------------------------------------------------

 * 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.

	 */

		/*

		 * 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.

		 */

	}

	/* SIB: this is where I should mark the build as finished */

		/* SIB: there should be a siblings loop there */

			}

				/*

				 * Queue the node up -- any unmade

				 * predecessors will be dealt with in

				 * MakeStartJobs.

				 */

			}

		}

	}

static bool

try_to_make_node(GNode *gn)

{

	}

	}

	}

	}

	/* SIB: this is where there should be a siblings loop */

	}

	/* this is where we hold back nodes */

		GNode *gn2;

					    "groupling to %s\n",

			}

	}

		GNode *gn2;

					    "sibling to %s\n",

			}

	}

		/* SIB: this is where commands should get prepared */

			/*

			 * 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)...

			 */

		}

	}

}

/*

 *-----------------------------------------------------------------------

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

	}

}

static void

MakePrintStatus(void *gnp)

{

	}

}

static void

MakeAddChild(void *to_addp, void *ap)

{

}

static void

MakeHandleUse(void *cgnp, void *pgnp)

{

}

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

		/*

		 * Apply any .USE rules before looking for implicit

		 * dependencies to make sure everything that should have

		 * commands has commands ...

		 */

				    gn->name, gn->unmade);

			    &examine);

		}

	}

}

/*-

 *-----------------------------------------------------------------------

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

	/* wild guess at initial sizes */

		/*

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

		 */

	} 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.

	 */

	}

	/*

	 * Print the final status of each target. E.g. if it wasn't made

	 * because some inferior reported an error.

	 */

		problem = true;

	}

}

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

	bool cycle = false;

	bool first = true;

			continue;

		cycle = true;

		first = false;

	}

}

static void

print_unlink_cycle(struct growableArray *l, GNode *c)

{

	LstNode ln;

	GNode *gn = NULL;

	unsigned int i;

	}

	/* So the first element is tied to our node, find and kill the link */

		}

	}

	/* this shouldn't happen ever */

}

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

{

		GNode *c;

		else

	}

}

static GNode *

find_cycle(Lst l, struct growableArray *cycle)

{

	LstNode ln;

			/* we should print the cycle and not do more */

		}

			GNode *c;

		}

	}

}