[BACK]Return to make.c CVS log [TXT][DIR] Up to [local] / src / usr.bin / make

Annotation of src/usr.bin/make/make.c, Revision 1.64

1.64    ! espie       1: /*     $OpenBSD: make.c,v 1.63 2012/04/21 04:35:32 guenther Exp $      */
1.6       millert     2: /*     $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $       */
1.1       deraadt     3:
                      4: /*
1.4       millert     5:  * Copyright (c) 1988, 1989, 1990, 1993
                      6:  *     The Regents of the University of California.  All rights reserved.
1.1       deraadt     7:  * Copyright (c) 1989 by Berkeley Softworks
                      8:  * All rights reserved.
                      9:  *
                     10:  * This code is derived from software contributed to Berkeley by
                     11:  * Adam de Boor.
                     12:  *
                     13:  * Redistribution and use in source and binary forms, with or without
                     14:  * modification, are permitted provided that the following conditions
                     15:  * are met:
                     16:  * 1. Redistributions of source code must retain the above copyright
                     17:  *    notice, this list of conditions and the following disclaimer.
                     18:  * 2. Redistributions in binary form must reproduce the above copyright
                     19:  *    notice, this list of conditions and the following disclaimer in the
                     20:  *    documentation and/or other materials provided with the distribution.
1.33      millert    21:  * 3. Neither the name of the University nor the names of its contributors
1.1       deraadt    22:  *    may be used to endorse or promote products derived from this software
                     23:  *    without specific prior written permission.
                     24:  *
                     25:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     26:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     27:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     28:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     29:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     30:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     31:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     32:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     33:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     34:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     35:  * SUCH DAMAGE.
                     36:  */
                     37:
                     38: /*-
                     39:  * make.c --
                     40:  *     The functions which perform the examination of targets and
                     41:  *     their suitability for creation
                     42:  *
                     43:  * Interface:
1.25      espie      44:  *     Make_Run                Initialize things for the module and recreate
1.26      espie      45:  *                             whatever needs recreating. Returns true if
                     46:  *                             work was (or would have been) done and
                     47:  *                             false
1.25      espie      48:  *                             otherwise.
                     49:  *
                     50:  *     Make_Update             Update all parents of a given child. Performs
                     51:  *                             various bookkeeping chores like the updating
                     52:  *                             of the cmtime field of the parent, filling
                     53:  *                             of the IMPSRC context variable, etc. It will
                     54:  *                             place the parent on the toBeMade queue if it
                     55:  *                             should be.
                     56:  *
1.1       deraadt    57:  */
                     58:
1.27      espie      59: #include <limits.h>
1.26      espie      60: #include <stdio.h>
1.43      espie      61: #include <signal.h>
1.52      espie      62: #include <stddef.h>
1.54      espie      63: #include <stdlib.h>
1.52      espie      64: #include <string.h>
                     65: #include <ohash.h>
1.26      espie      66: #include "config.h"
                     67: #include "defines.h"
                     68: #include "dir.h"
                     69: #include "job.h"
                     70: #include "suff.h"
                     71: #include "var.h"
                     72: #include "error.h"
                     73: #include "make.h"
                     74: #include "gnode.h"
                     75: #include "extern.h"
                     76: #include "timestamp.h"
1.37      espie      77: #include "engine.h"
1.26      espie      78: #include "lst.h"
1.43      espie      79: #include "targ.h"
1.58      espie      80: #include "targequiv.h"
1.56      espie      81: #include "garray.h"
                     82: #include "memory.h"
                     83:
                     84: /* what gets added each time. Kept as one static array so that it doesn't
                     85:  * get resized every time.
                     86:  */
                     87: static struct growableArray examine;
                     88: /* The current fringe of the graph. These are nodes which await examination by
                     89:  * MakeOODate. It is added to by Make_Update and subtracted from by
                     90:  * MakeStartJobs */
                     91: static struct growableArray toBeMade;
1.25      espie      92:
1.64    ! espie      93: /* Hold back on nodes where equivalent stuff is already building... */
        !            94: static struct growableArray heldBack;
        !            95:
1.52      espie      96: static struct ohash targets;   /* stuff we must build */
1.1       deraadt    97:
1.25      espie      98: static void MakeAddChild(void *, void *);
                     99: static void MakeHandleUse(void *, void *);
1.26      espie     100: static bool MakeStartJobs(void);
1.25      espie     101: static void MakePrintStatus(void *, void *);
1.46      espie     102: static bool try_to_make_node(GNode *);
                    103: static void add_targets_to_make(Lst);
1.40      espie     104:
1.52      espie     105: static bool has_unmade_predecessor(GNode *);
                    106: static void requeue_successors(GNode *);
1.54      espie     107: static void random_setup(void);
                    108:
                    109: static bool randomize_queue;
                    110: long random_delay = 0;
                    111:
1.56      espie     112: bool
                    113: no_jobs_left()
                    114: {
                    115:        return Array_IsEmpty(&toBeMade);
                    116: }
                    117:
1.54      espie     118: static void
                    119: random_setup()
                    120: {
                    121:        randomize_queue = Var_Definedi("RANDOM_ORDER", NULL);
                    122:
                    123:        if (Var_Definedi("RANDOM_DELAY", NULL))
                    124:                random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000,
                    125:                    NULL) * 1000000;
                    126:
                    127:        if (randomize_queue || random_delay) {
                    128:                unsigned int random_seed;
                    129:                char *t;
                    130:
                    131:                t = Var_Value("RANDOM_SEED");
                    132:                if (t != NULL)
                    133:                        random_seed = strtonum(t, 0, UINT_MAX, NULL);
                    134:                else
                    135:                        random_seed = time(NULL);
                    136:                fprintf(stderr, "RANDOM_SEED=%u\n", random_seed);
                    137:                srandom(random_seed);
                    138:        }
                    139: }
1.52      espie     140:
1.56      espie     141: static void
                    142: randomize_garray(struct growableArray *g)
                    143: {
                    144:        /* This is a fairly standard algorithm to randomize an array. */
                    145:        unsigned int i, v;
                    146:        GNode *e;
                    147:
                    148:        for (i = g->n; i > 0; i--) {
                    149:                v = random() % i;
                    150:                if (v == i-1)
                    151:                        continue;
                    152:                else {
                    153:                        e = g->a[i-1];
                    154:                        g->a[i-1] = g->a[v];
                    155:                        g->a[v] = e;
                    156:                }
                    157:        }
                    158: }
                    159:
1.52      espie     160: static bool
                    161: has_unmade_predecessor(GNode *gn)
1.1       deraadt   162: {
1.52      espie     163:        LstNode ln;
                    164:
                    165:        if (Lst_IsEmpty(&gn->preds))
                    166:                return false;
1.5       millert   167:
1.52      espie     168:
                    169:        for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)) {
                    170:                GNode   *pgn = (GNode *)Lst_Datum(ln);
                    171:
                    172:                if (pgn->must_make && pgn->built_status == UNKNOWN) {
                    173:                        if (DEBUG(MAKE))
                    174:                                printf("predecessor %s not made yet.\n",
                    175:                                    pgn->name);
                    176:                        return true;
                    177:                }
                    178:        }
                    179:        return false;
1.1       deraadt   180: }
1.25      espie     181:
1.15      espie     182: static void
1.52      espie     183: requeue_successors(GNode *gn)
1.1       deraadt   184: {
1.52      espie     185:        LstNode ln;
                    186:        /* Deal with successor nodes. If any is marked for making and has an
                    187:         * unmade count of 0, has not been made and isn't in the examination
                    188:         * queue, it means we need to place it in the queue as it restrained
                    189:         * itself before.       */
                    190:        for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) {
                    191:                GNode   *succ = (GNode *)Lst_Datum(ln);
                    192:
                    193:                if (succ->must_make && succ->unmade == 0
                    194:                    && succ->built_status == UNKNOWN)
1.56      espie     195:                        Array_PushNew(&toBeMade, succ);
1.52      espie     196:        }
1.1       deraadt   197: }
1.25      espie     198:
1.64    ! espie     199: static void
        !           200: requeue(GNode *gn)
        !           201: {
        !           202:        /* this is where we go inside the array and move things around */
        !           203:        unsigned int i, j;
        !           204:
        !           205:        for (i = 0, j = 0; i < heldBack.n; i++, j++) {
        !           206:                if (heldBack.a[i]->watched == gn) {
        !           207:                        j--;
        !           208:                        heldBack.a[i]->built_status = UNKNOWN;
        !           209:                        if (DEBUG(HELDJOBS))
        !           210:                                printf("%s finished, releasing: %s\n",
        !           211:                                    gn->name, heldBack.a[i]->name);
        !           212:                        Array_Push(&toBeMade, heldBack.a[i]);
        !           213:                        continue;
        !           214:                }
        !           215:                heldBack.a[j] = heldBack.a[i];
        !           216:        }
        !           217:        heldBack.n = j;
        !           218: }
        !           219:
1.1       deraadt   220: /*-
                    221:  *-----------------------------------------------------------------------
1.25      espie     222:  * Make_Update --
1.1       deraadt   223:  *     Perform update on the parents of a node. Used by JobFinish once
                    224:  *     a node has been dealt with and by MakeStartJobs if it finds an
1.4       millert   225:  *     up-to-date node.
1.1       deraadt   226:  *
                    227:  * Results:
                    228:  *     Always returns 0
                    229:  *
                    230:  * Side Effects:
                    231:  *     The unmade field of pgn is decremented and pgn may be placed on
                    232:  *     the toBeMade queue if this field becomes 0.
                    233:  *
1.25      espie     234:  *     If the child was made, the parent's childMade field will be set true
1.1       deraadt   235:  *     and its cmtime set to now.
                    236:  *
                    237:  *     If the child wasn't made, the cmtime field of the parent will be
                    238:  *     altered if the child's mtime is big enough.
                    239:  *
                    240:  *-----------------------------------------------------------------------
                    241:  */
                    242: void
1.35      espie     243: Make_Update(GNode *cgn)        /* the child node */
1.1       deraadt   244: {
1.40      espie     245:        GNode   *pgn;   /* the parent node */
1.47      espie     246:        LstNode ln;     /* Element in parents list */
1.40      espie     247:
1.1       deraadt   248:        /*
1.40      espie     249:         * If the child was actually made, see what its modification time is
                    250:         * now -- some rules won't actually update the file. If the file still
                    251:         * doesn't exist, make its mtime now.
1.1       deraadt   252:         */
1.48      espie     253:        if (cgn->built_status != UPTODATE) {
1.40      espie     254:                /*
                    255:                 * This is what Make does and it's actually a good thing, as it
                    256:                 * allows rules like
                    257:                 *
                    258:                 *      cmp -s y.tab.h parse.h || cp y.tab.h parse.h
                    259:                 *
1.41      espie     260:                 * to function as intended. Unfortunately, thanks to the
                    261:                 * stateless nature of NFS, there are times when the
                    262:                 * modification time of a file created on a remote machine
1.40      espie     263:                 * will not be modified before the local stat() implied by
1.41      espie     264:                 * the Dir_MTime occurs, thus leading us to believe that the
                    265:                 * file is unchanged, wreaking havoc with files that depend
1.40      espie     266:                 * on this one.
                    267:                 */
1.43      espie     268:                if (noExecute || is_out_of_date(Dir_MTime(cgn)))
1.60      espie     269:                        ts_set_from_now(cgn->mtime);
1.40      espie     270:                if (DEBUG(MAKE))
                    271:                        printf("update time: %s\n", time_to_string(cgn->mtime));
                    272:        }
                    273:
1.64    ! espie     274:        requeue(cgn);
1.58      espie     275:        /* SIB: this is where I should mark the build as finished */
1.40      espie     276:        for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
                    277:                pgn = (GNode *)Lst_Datum(ln);
1.58      espie     278:                /* SIB: there should be a siblings loop there */
1.55      espie     279:                pgn->unmade--;
1.48      espie     280:                if (pgn->must_make) {
1.52      espie     281:                        if (DEBUG(MAKE))
                    282:                                printf("%s--=%d ",
                    283:                                    pgn->name, pgn->unmade);
1.40      espie     284:
                    285:                        if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
1.63      guenther  286:                                if (cgn->built_status == MADE)
1.40      espie     287:                                        pgn->childMade = true;
1.63      guenther  288:                                (void)Make_TimeStamp(pgn, cgn);
1.40      espie     289:                        }
                    290:                        if (pgn->unmade == 0) {
                    291:                                /*
1.41      espie     292:                                 * Queue the node up -- any unmade
                    293:                                 * predecessors will be dealt with in
1.40      espie     294:                                 * MakeStartJobs.
                    295:                                 */
1.52      espie     296:                                if (DEBUG(MAKE))
                    297:                                        printf("QUEUING ");
1.56      espie     298:                                Array_Push(&toBeMade, pgn);
1.40      espie     299:                        } else if (pgn->unmade < 0) {
1.52      espie     300:                                Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
1.40      espie     301:                        }
                    302:                }
1.1       deraadt   303:        }
1.52      espie     304:        if (DEBUG(MAKE))
                    305:                printf("\n");
                    306:        requeue_successors(cgn);
1.1       deraadt   307: }
1.25      espie     308:
1.46      espie     309: static bool
                    310: try_to_make_node(GNode *gn)
                    311: {
                    312:        if (DEBUG(MAKE))
                    313:                printf("Examining %s...", gn->name);
1.52      espie     314:
1.64    ! espie     315:        if (gn->built_status == HELDBACK) {
        !           316:                if (DEBUG(HELDJOBS))
        !           317:                        printf("%s already held back ???\n", gn->name);
        !           318:                return false;
        !           319:        }
        !           320:
1.52      espie     321:        if (gn->unmade != 0) {
                    322:                if (DEBUG(MAKE))
                    323:                        printf(" Requeuing (%d)\n", gn->unmade);
                    324:                add_targets_to_make(&gn->children);
1.56      espie     325:                Array_Push(&toBeMade, gn);
1.52      espie     326:                return false;
                    327:        }
                    328:        if (has_been_built(gn)) {
                    329:                if (DEBUG(MAKE))
                    330:                        printf(" already made\n");
                    331:                        return false;
                    332:        }
                    333:        if (has_unmade_predecessor(gn)) {
                    334:                if (DEBUG(MAKE))
                    335:                        printf(" Dropping for now\n");
                    336:                return false;
                    337:        }
1.46      espie     338:
1.58      espie     339:        /* SIB: this is where there should be a siblings loop */
1.52      espie     340:        Suff_FindDeps(gn);
                    341:        if (gn->unmade != 0) {
                    342:                if (DEBUG(MAKE))
                    343:                        printf(" Requeuing (after deps: %d)\n", gn->unmade);
                    344:                add_targets_to_make(&gn->children);
                    345:                return false;
1.46      espie     346:        }
1.64    ! espie     347:        /* this is where we hold back nodes */
        !           348:        if (gn->groupling != NULL) {
        !           349:                GNode *gn2;
        !           350:                for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling)
        !           351:                        if (gn2->built_status == BUILDING) {
        !           352:                                gn->watched = gn2;
        !           353:                                gn->built_status = HELDBACK;
        !           354:                                if (DEBUG(HELDJOBS))
        !           355:                                        printf("Holding back job %s, "
        !           356:                                            "groupling to %s\n",
        !           357:                                            gn->name, gn2->name);
        !           358:                                Array_Push(&heldBack, gn);
        !           359:                                return false;
        !           360:                        }
        !           361:        }
        !           362:        if (gn->sibling != gn) {
        !           363:                GNode *gn2;
        !           364:                for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling)
        !           365:                        if (gn2->built_status == BUILDING) {
        !           366:                                gn->watched = gn2;
        !           367:                                gn->built_status = HELDBACK;
        !           368:                                if (DEBUG(HELDJOBS))
        !           369:                                        printf("Holding back job %s, "
        !           370:                                            "sibling to %s\n",
        !           371:                                            gn->name, gn2->name);
        !           372:                                Array_Push(&heldBack, gn);
        !           373:                                return false;
        !           374:                        }
        !           375:        }
1.46      espie     376:        if (Make_OODate(gn)) {
                    377:                if (DEBUG(MAKE))
                    378:                        printf("out-of-date\n");
                    379:                if (queryFlag)
                    380:                        return true;
1.58      espie     381:                /* SIB: this is where commands should get prepared */
1.46      espie     382:                Make_DoAllVar(gn);
                    383:                Job_Make(gn);
                    384:        } else {
                    385:                if (DEBUG(MAKE))
                    386:                        printf("up-to-date\n");
1.48      espie     387:                gn->built_status = UPTODATE;
1.46      espie     388:                if (gn->type & OP_JOIN) {
                    389:                        /*
                    390:                         * Even for an up-to-date .JOIN node, we need it
                    391:                         * to have its context variables so references
                    392:                         * to it get the correct value for .TARGET when
                    393:                         * building up the context variables of its
                    394:                         * parent(s)...
                    395:                         */
                    396:                        Make_DoAllVar(gn);
                    397:                }
                    398:
                    399:                Make_Update(gn);
                    400:        }
                    401:        return false;
                    402: }
                    403:
1.40      espie     404: /*
1.1       deraadt   405:  *-----------------------------------------------------------------------
                    406:  * MakeStartJobs --
                    407:  *     Start as many jobs as possible.
                    408:  *
                    409:  * Results:
                    410:  *     If the query flag was given to pmake, no job will be started,
                    411:  *     but as soon as an out-of-date target is found, this function
1.26      espie     412:  *     returns true. At all other times, this function returns false.
1.1       deraadt   413:  *
                    414:  * Side Effects:
                    415:  *     Nodes are removed from the toBeMade queue and job table slots
                    416:  *     are filled.
                    417:  *-----------------------------------------------------------------------
                    418:  */
1.26      espie     419: static bool
1.35      espie     420: MakeStartJobs(void)
1.1       deraadt   421: {
1.40      espie     422:        GNode   *gn;
1.4       millert   423:
1.59      espie     424:        while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) {
1.46      espie     425:                if (try_to_make_node(gn))
                    426:                        return true;
1.1       deraadt   427:        }
1.40      espie     428:        return false;
1.1       deraadt   429: }
1.25      espie     430:
1.1       deraadt   431: /*-
                    432:  *-----------------------------------------------------------------------
                    433:  * MakePrintStatus --
                    434:  *     Print the status of a top-level node, viz. it being up-to-date
                    435:  *     already or not created due to an error in a lower level.
                    436:  *     Callback function for Make_Run via Lst_ForEach.
1.25      espie     437:  *
                    438:  * Side Effects:
                    439:  *     A message may be printed.
1.1       deraadt   440:  *-----------------------------------------------------------------------
                    441:  */
1.15      espie     442: static void
1.35      espie     443: MakePrintStatus(
                    444:     void *gnp,             /* Node to examine */
                    445:     void *cyclep)          /* True if gn->unmade being non-zero implies
1.1       deraadt   446:                             * a cycle in the graph, not an error in an
                    447:                             * inferior */
                    448: {
1.40      espie     449:        GNode   *gn = (GNode *)gnp;
                    450:        bool    cycle = *(bool *)cyclep;
1.48      espie     451:        if (gn->built_status == UPTODATE) {
1.40      espie     452:                printf("`%s' is up to date.\n", gn->name);
                    453:        } else if (gn->unmade != 0) {
                    454:                if (cycle) {
                    455:                        bool t = true;
                    456:                        /*
1.41      espie     457:                         * If printing cycles and came to one that has unmade
                    458:                         * children, print out the cycle by recursing on its
1.40      espie     459:                         * children. Note a cycle like:
                    460:                         *      a : b
                    461:                         *      b : c
                    462:                         *      c : b
1.41      espie     463:                         * will cause this to erroneously complain about a
1.40      espie     464:                         * being in the cycle, but this is a good approximation.
                    465:                         */
1.48      espie     466:                        if (gn->built_status == CYCLE) {
1.40      espie     467:                                Error("Graph cycles through `%s'", gn->name);
1.48      espie     468:                                gn->built_status = ENDCYCLE;
1.40      espie     469:                                Lst_ForEach(&gn->children, MakePrintStatus, &t);
1.49      espie     470:                                gn->built_status = UNKNOWN;
1.48      espie     471:                        } else if (gn->built_status != ENDCYCLE) {
                    472:                                gn->built_status = CYCLE;
1.40      espie     473:                                Lst_ForEach(&gn->children, MakePrintStatus, &t);
                    474:                        }
                    475:                } else {
1.41      espie     476:                        printf("`%s' not remade because of errors.\n",
1.40      espie     477:                            gn->name);
                    478:                }
1.1       deraadt   479:        }
                    480: }
1.25      espie     481:
1.5       millert   482:
1.52      espie     483: static void
1.56      espie     484: MakeAddChild(void *to_addp, void *ap)
1.52      espie     485: {
                    486:        GNode *gn = (GNode *)to_addp;
                    487:
                    488:        if (!gn->must_make && !(gn->type & OP_USE))
1.56      espie     489:                Array_Push((struct growableArray *)ap, gn);
1.52      espie     490: }
                    491:
                    492: static void
1.58      espie     493: MakeHandleUse(void *cgnp, void *pgnp)
1.52      espie     494: {
1.58      espie     495:        GNode *cgn = (GNode *)cgnp;
                    496:        GNode *pgn = (GNode *)pgnp;
                    497:
                    498:        if (cgn->type & OP_USE)
                    499:                Make_HandleUse(cgn, pgn);
1.52      espie     500: }
                    501:
                    502: /* Add stuff to the toBeMade queue. we try to sort things so that stuff
                    503:  * that can be done directly is done right away.  This won't be perfect,
                    504:  * since some dependencies are only discovered later (e.g., SuffFindDeps).
1.46      espie     505:  */
                    506: static void
1.52      espie     507: add_targets_to_make(Lst todo)
1.46      espie     508: {
                    509:        GNode *gn;
1.56      espie     510:
1.52      espie     511:        unsigned int slot;
                    512:
1.56      espie     513:        AppendList2Array(todo, &examine);
1.46      espie     514:
1.56      espie     515:        while ((gn = Array_Pop(&examine)) != NULL) {
1.52      espie     516:                if (gn->must_make)      /* already known */
                    517:                        continue;
                    518:                gn->must_make = true;
1.46      espie     519:
1.52      espie     520:                slot = ohash_qlookup(&targets, gn->name);
                    521:                if (!ohash_find(&targets, slot))
                    522:                        ohash_insert(&targets, slot, gn);
                    523:
                    524:
                    525:                look_harder_for_target(gn);
1.58      espie     526:                kludge_look_harder_for_target(gn);
1.52      espie     527:                /*
                    528:                 * Apply any .USE rules before looking for implicit
                    529:                 * dependencies to make sure everything that should have
                    530:                 * commands has commands ...
                    531:                 */
                    532:                Lst_ForEach(&gn->children, MakeHandleUse, gn);
                    533:                expand_all_children(gn);
1.46      espie     534:
1.52      espie     535:                if (gn->unmade != 0) {
                    536:                        if (DEBUG(MAKE))
                    537:                                printf("%s: not queuing (%d unmade children)\n",
                    538:                                    gn->name, gn->unmade);
                    539:                        Lst_ForEach(&gn->children, MakeAddChild,
                    540:                            &examine);
                    541:                } else {
                    542:                        if (DEBUG(MAKE))
                    543:                                printf("%s: queuing\n", gn->name);
1.56      espie     544:                        Array_Push(&toBeMade, gn);
1.46      espie     545:                }
                    546:        }
1.56      espie     547:        if (randomize_queue)
                    548:                randomize_garray(&toBeMade);
1.46      espie     549: }
                    550:
1.1       deraadt   551: /*-
                    552:  *-----------------------------------------------------------------------
1.6       millert   553:  * Make_Run --
                    554:  *     Initialize the nodes to remake and the list of nodes which are
                    555:  *     ready to be made by doing a breadth-first traversal of the graph
                    556:  *     starting from the nodes in the given list. Once this traversal
                    557:  *     is finished, all the 'leaves' of the graph are in the toBeMade
                    558:  *     queue.
                    559:  *     Using this queue and the Job module, work back up the graph,
                    560:  *     calling on MakeStartJobs to keep the job table as full as
                    561:  *     possible.
                    562:  *
1.1       deraadt   563:  * Results:
1.26      espie     564:  *     true if work was done. false otherwise.
1.1       deraadt   565:  *
                    566:  * Side Effects:
1.48      espie     567:  *     The must_make field of all nodes involved in the creation of the given
1.6       millert   568:  *     targets is set to 1. The toBeMade list is set to contain all the
                    569:  *     'leaves' of these subgraphs.
1.1       deraadt   570:  *-----------------------------------------------------------------------
                    571:  */
1.26      espie     572: bool
1.35      espie     573: Make_Run(Lst targs)            /* the initial list of targets */
1.1       deraadt   574: {
1.52      espie     575:        int errors;     /* Number of errors the Job module reports */
                    576:        GNode *gn;
                    577:        unsigned int i;
                    578:        bool cycle;
1.40      espie     579:
1.54      espie     580:        /* wild guess at initial sizes */
1.56      espie     581:        Array_Init(&toBeMade, 500);
                    582:        Array_Init(&examine, 150);
1.64    ! espie     583:        Array_Init(&heldBack, 100);
1.52      espie     584:        ohash_init(&targets, 10, &gnode_info);
1.54      espie     585:        if (DEBUG(PARALLEL))
                    586:                random_setup();
1.40      espie     587:
1.46      espie     588:        add_targets_to_make(targs);
1.40      espie     589:        if (queryFlag) {
                    590:                /*
1.41      espie     591:                 * We wouldn't do any work unless we could start some jobs in
                    592:                 * the next loop... (we won't actually start any, of course,
1.40      espie     593:                 * this is just to see if any of the targets was out of date)
                    594:                 */
                    595:                return MakeStartJobs();
                    596:        } else {
                    597:                /*
                    598:                 * Initialization. At the moment, no jobs are running and until
                    599:                 * some get started, nothing will happen since the remaining
1.41      espie     600:                 * upward traversal of the graph is performed by the routines
                    601:                 * in job.c upon the finishing of a job. So we fill the Job
1.40      espie     602:                 * table as much as we can before going into our loop.
                    603:                 */
                    604:                (void)MakeStartJobs();
1.1       deraadt   605:        }
1.4       millert   606:
1.1       deraadt   607:        /*
1.40      espie     608:         * Main Loop: The idea here is that the ending of jobs will take
                    609:         * care of the maintenance of data structures and the waiting for output
                    610:         * will cause us to be idle most of the time while our children run as
                    611:         * much as possible. Because the job table is kept as full as possible,
                    612:         * the only time when it will be empty is when all the jobs which need
                    613:         * running have been run, so that is the end condition of this loop.
1.41      espie     614:         * Note that the Job module will exit if there were any errors unless
1.40      espie     615:         * the keepgoing flag was given.
1.1       deraadt   616:         */
1.40      espie     617:        while (!Job_Empty()) {
1.57      espie     618:                handle_running_jobs();
1.40      espie     619:                (void)MakeStartJobs();
                    620:        }
                    621:
                    622:        errors = Job_Finish();
1.52      espie     623:        cycle = false;
1.40      espie     624:
1.52      espie     625:        for (gn = ohash_first(&targets, &i); gn != NULL;
                    626:            gn = ohash_next(&targets, &i)) {
                    627:                if (has_been_built(gn))
                    628:                        continue;
                    629:                cycle = true;
                    630:                errors++;
                    631:                printf("Error: target %s unaccounted for (%s)\n",
                    632:                    gn->name, status_to_string(gn));
                    633:        }
1.1       deraadt   634:        /*
1.40      espie     635:         * Print the final status of each target. E.g. if it wasn't made
                    636:         * because some inferior reported an error.
1.1       deraadt   637:         */
1.52      espie     638:        Lst_ForEach(targs, MakePrintStatus, &cycle);
                    639:        if (errors)
                    640:                Fatal("Errors while building");
1.4       millert   641:
1.40      espie     642:        return true;
1.1       deraadt   643: }