/*      $OpenBSD: make.c,v 1.85 2024/06/18 02:11:03 millert 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(void)
{
        return Array_IsEmpty(&to_build);
}

static void
random_setup(void)
{
        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(void)
{
        /* 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;
}