home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume12 / cake / part02 / chase.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-14  |  13.3 KB  |  580 lines
  1. /*
  2. **    Module to chase Cake dependencies.
  3. */
  4.  
  5. static    char
  6. rcs_id[] = "$Header: /mip/zs/src/sys/cake/RCS/chase.c,v 1.14 86/07/19 12:22:39 zs Exp $";
  7.  
  8. #include    "cake.h"
  9.  
  10. /*
  11. **    The main chasing function. It checks all entries to see
  12. **    if they describe a dependency of the name. If the second arg
  13. **    is not NULL, it is taken as a fixed choice (by another do_chase)
  14. **    as to which entry will actually be used to generate the name.
  15. **
  16. **    The kinds of nodes returned by do_chase are as follows.
  17. **    OK means that no action is needed to update the name.
  18. **    CANDO means that the action is known and there is no reason
  19. **    why it shouldn't succeed. NOWAY is set when neither of those
  20. **    conditions is satisfied. nf_ERR means that some error has
  21. **    occurred; nf_ERR nodes are never touched again; except for
  22. **    printing the error messages themselves. (NOWAY nodes *are*
  23. **    touched by act.c to update as many ancestors as possible.)
  24. **
  25. **    Whenever nf_ERR is not set, do_chase sets the utime field,
  26. **    and the rtime field as well if the file exists.
  27. */
  28.  
  29. do_chase(node, picked)
  30. reg    Node    *node;
  31. reg    Entry    *picked;
  32. {
  33.     extern        get_utime();
  34.     extern    time_t    cake_gettime();
  35.     extern    Node    *chase();
  36.     extern    Node    *chase_node();
  37.     extern    time_t    pick_time();
  38.     extern    bool    match();
  39.     extern    bool    eval();
  40.     extern    Entry    *ground_entry();
  41.     extern    Test    *deref_test();
  42.     extern        deref_entry();
  43.     extern    List    *entries;
  44.     extern    char    *list_names();
  45.     Env        env;
  46.     reg    List    *ptr, *ptr1, *ptr2;
  47.     reg    Node    *newnode, *onode;
  48.     reg    Entry    *entry, *newentry;
  49.     reg    Pat    *pat;
  50.     reg    List    *entry_anay, *entry_ayea;    /* of Entry    */
  51.     reg    List    *miss_anay, *miss_ayea;        /* of Node    */
  52.     reg    List    *pot_entry;        /* of Entry    */
  53.     reg    List    *pot_pat;        /* of Pat    */
  54.     reg    List    *probe_old;        /* of Node    */
  55.     reg    bool    found, missing;
  56.     reg    bool    singleton, orphan;
  57.  
  58.     put_trail("do_chase", "start");
  59.     cdebug("chasing %s\n", node->n_name);
  60.  
  61.     if (off_node(node, nf_EXIST))
  62.         set_node(node, nf_NEWFILE);
  63.  
  64.     /* find all entries which could generate this name */
  65.     pot_entry = makelist0();
  66.     pot_pat   = makelist0();
  67.     for_list (ptr, entries)
  68.     {
  69.         entry = (Entry *) ldata(ptr);
  70.         /* try everything on the left side of the entry */
  71.         for_list (ptr1, entry->e_new)
  72.         {
  73.             pat = (Pat *) ldata(ptr1);
  74.             if (match(env, node->n_name, pat))
  75.             {
  76.                 if ((newentry = ground_entry(env, entry)) == (Entry *) NULL)
  77.                 {
  78.                     sprintf(scratchbuf, "cannot perform substitutions on entry for %s",
  79.                         node->n_name);
  80.                     add_error(node, new_name(scratchbuf), LNULL, TRUE);
  81.                     goto end;
  82.                 }
  83.  
  84. #ifdef    CAKEDEBUG
  85.                 if (entrydebug)
  86.                 {
  87.                     printf("Applicable entry\n");
  88.                     print_entry(newentry);
  89.                 }
  90. #endif
  91.  
  92.                 addtail(pot_entry, newentry);    /* na */
  93.                 addtail(pot_pat, pat);        /* na */
  94.                 break;
  95.             }
  96.         }
  97.     }
  98.  
  99.     cdebug("%s: %d potentials\n", node->n_name, length(pot_entry));
  100.  
  101.     /* find out which tests are satisfied */
  102.     entry_anay = makelist0();
  103.     entry_ayea = makelist0();
  104.     for_2list (ptr1, ptr2, pot_entry, pot_pat)
  105.     {
  106.         entry = (Entry *) ldata(ptr1);
  107.         pat = (Pat *) ldata(ptr2);
  108.  
  109.         for_list (ptr, entry->e_when)
  110.         {
  111.             reg    Node    *whennode;
  112.             reg    Pat    *whenpat;
  113.  
  114.             whenpat  = (Pat *) ldata(ptr);
  115.             whennode = chase(whenpat->p_str, whenpat->p_flag, (Entry *) NULL);
  116.             if (off_node(whennode, nf_ERR))
  117.             {
  118.                 if (is_ok(whennode))
  119.                     continue;
  120.  
  121.                 if (nflag && off_node(whennode, nf_WARNED))
  122.                 {
  123.                     printf("cake -n: warning, need to make %s to find dependencies\n",
  124.                         whenpat->p_str);
  125.                     set_node(whennode, nf_WARNED);
  126.                 }
  127.  
  128.                 update(whennode, 100, TRUE);
  129.             }
  130.  
  131.             if (on_node(whennode, nf_ERR) || ! is_ok(whennode))
  132.             {
  133.                 sprintf(scratchbuf, "cannot find out if entry applies to %s",
  134.                     node->n_name);
  135.                 add_error(node, new_name(scratchbuf), makelist(whennode), TRUE);
  136.                 return;
  137.             }
  138.         }
  139.  
  140. #ifdef    CAKEDEBUG
  141.         if (entrydebug)
  142.         {
  143.             printf("about to test condition\n");
  144.             print_entry(entry);
  145.         }
  146. #endif
  147.  
  148.         entry->e_cond = deref_test(entry->e_cond);
  149.         if (! eval(node, entry->e_cond, env))
  150.         {
  151.             cdebug("condition FALSE\n");
  152.             continue;
  153.         }
  154.  
  155.         /* here we know that this entry applies */
  156.         deref_entry(env, entry);
  157.  
  158.         if (Lflag)
  159.         {
  160.             for_list (ptr, entry->e_old)
  161.             {
  162.                 reg    Pat    *opat;
  163.  
  164.                 opat = (Pat *) ldata(ptr);
  165.                 if (streq(node->n_name, opat->p_str))
  166.                 {
  167.                     cdebug("found loop in entry at %s\n", node->n_name);
  168.                     continue;
  169.                 }
  170.             }
  171.         }
  172.  
  173.         node->n_flag |= pat->p_flag;
  174.         if (length(entry->e_act) == 0)
  175.             addtail(entry_anay, entry);    /* no assigment */
  176.         else
  177.             addtail(entry_ayea, entry);    /* no assigment */
  178.     }
  179.  
  180.     if (on_node(node, nf_ERR))
  181.         return;
  182.  
  183.     cdebug("%s: no action: %d, with actions: %d\n",
  184.         node->n_name, length(entry_anay), length(entry_ayea));
  185.  
  186.     /* All entries considered from now on are ground */
  187.  
  188.     /* see if the file is an original */
  189.     if (length(entry_anay) == 0 && length(entry_ayea) == 0)
  190.     {
  191.         if (off_node(node, nf_EXIST))
  192.         {
  193.             cdebug("%s: noway\n", node->n_name);
  194.             node->n_kind  = n_NOWAY;
  195.             node->n_utime = GENESIS;
  196.             sprintf(scratchbuf, "base file %s does not exist", node->n_name);
  197.             add_error(node, new_name(scratchbuf), LNULL, FALSE);
  198.             goto end;
  199.         }
  200.  
  201.         set_node(node, nf_ORIG);
  202.         cdebug("%s: orig ok\n", node->n_name);
  203.         node->n_kind  = n_OK;
  204.         node->n_utime = node->n_rtime;
  205.         goto end;
  206.     }
  207.  
  208.     /* see to actionless dependencies */
  209.     missing = FALSE;
  210.     miss_anay = NULL;
  211.     for_list (ptr, entry_anay)
  212.     {
  213.         entry = (Entry *) ldata(ptr);
  214.         for_list (ptr1, entry->e_old)
  215.         {
  216.             pat = (Pat *) ldata(ptr1);
  217.             newnode = chase(pat->p_str, pat->p_flag, (Entry *) NULL);
  218.             if (on_node(newnode, nf_ERR) || is_noway(newnode))
  219.             {
  220.                 missing = TRUE;
  221.                 miss_anay = addtail(miss_anay, newnode);
  222.             }
  223.  
  224.             addtail(node->n_old, newnode);    /* na */
  225.         }
  226.     }
  227.  
  228.     cdebug("%s: unconditional dependencies, %s\n",
  229.         node->n_name, missing? "some missing": "all there");
  230.  
  231.     /*
  232.     **    If necessary, choose a feasible action dependency.
  233.     **    However, if there is only one, select it even if
  234.     **    it is not feasible.
  235.     */
  236.  
  237.     found = FALSE;
  238.     miss_ayea = NULL;
  239.     if (picked == (Entry *) NULL)
  240.     {
  241.         singleton = (length(entry_ayea) == 1);
  242.         orphan    = (length(entry_ayea) == 0);
  243.  
  244.         for_list (ptr, entry_ayea)
  245.         {
  246.             entry = (Entry *) ldata(ptr);
  247.             /* first copy of this code, with chase */
  248.             found = TRUE; /* assume it for the moment */
  249.             probe_old = makelist0();
  250.             for_list (ptr1, entry->e_old)
  251.             {
  252.                 pat = (Pat *) ldata(ptr1);
  253.                 newnode = chase(pat->p_str, pat->p_flag, (Entry *) NULL);
  254.                 if (on_node(newnode, nf_ERR) || is_noway(newnode))
  255.                 {
  256.                     found = FALSE;
  257.                     miss_ayea = addtail(miss_ayea, newnode);
  258.                     if (! singleton)
  259.                         break;
  260.                 }
  261.  
  262.                 addtail(probe_old, newnode);    /* na */
  263.             }
  264.  
  265.             if (found)
  266.                 break;
  267.         }
  268.     }
  269.     else
  270.     {
  271.         singleton = TRUE;
  272.         orphan    = FALSE;
  273.  
  274.         cdebug("%s: was given generator\n", node->n_name);
  275.         entry = picked;
  276.  
  277.         /* second copy of this code, with chase_node */
  278.         found = TRUE; /* assume it for the moment */
  279.         probe_old = makelist0();
  280.         for_list (ptr1, entry->e_old)
  281.         {
  282.             pat = (Pat *) ldata(ptr1);
  283.             newnode = chase_node(pat->p_str);
  284.             if (on_node(newnode, nf_ERR) || is_noway(newnode))
  285.             {
  286.                 found = FALSE;
  287.                 miss_ayea = addtail(miss_ayea, newnode);
  288.                 if (! singleton)
  289.                     break;
  290.             }
  291.  
  292.             addtail(probe_old, newnode);    /* na */
  293.         }
  294.     }
  295.  
  296.     if (found)
  297.     {
  298.         /* we have found an applicable entry */
  299.         cdebug("%s: found feasible generator\n", node->n_name);
  300.         addlist(node->n_old, probe_old);    /* na */
  301.         node->n_act = entry->e_act;
  302.         if (picked == (Entry *) NULL)
  303.             set_buddies(node, entry);
  304.         picked = entry;
  305.     }
  306.     or (singleton)
  307.     {
  308.         /* we have only one (inapplicable) entry */
  309.         /* so we shall make do as best we can */
  310.         cdebug("%s: found single infeasible generator\n", node->n_name);
  311.         addlist(node->n_old, probe_old);    /* na */
  312.         node->n_act = entry->e_act;
  313.         if (picked == (Entry *) NULL)
  314.             set_buddies(node, entry);
  315.         picked = entry;
  316.     }
  317.     or (orphan && on_node(node, nf_PSEUDO))
  318.     {
  319.         /* no entry is needed, act as we had one */
  320.         found = TRUE;
  321.         cdebug("%s: no generator, no problem\n", node->n_name);
  322.         node->n_act = makelist0();
  323.     }
  324.     else
  325.     {
  326.         cdebug("%s: no feasible generator\n", node->n_name);
  327.         node->n_act = makelist0();
  328.     }
  329.  
  330.     if (length(node->n_act) > 0 && length(picked->e_old) == 0)
  331.         node->n_utime = cake_gettime();
  332.     else
  333.         get_utime(node, TRUE);
  334.  
  335.     for_list (ptr, node->n_old)
  336.     {
  337.         newnode = (Node *) ldata(ptr);
  338.         if (on_node(newnode, nf_NONVOL))
  339.             set_node(node, nf_DEPNONVOL);
  340.     }
  341.  
  342.     if (missing)
  343.     {
  344.         node->n_kind = n_NOWAY;
  345.         sprintf(scratchbuf, "%s is missing the prerequisite%s %s",
  346.             node->n_name, length(miss_anay)==1? "": "s", list_names(miss_anay));
  347.         add_error(node, new_name(scratchbuf), miss_anay, FALSE);
  348.     }
  349.     or (! found)
  350.     {
  351.         node->n_kind = n_NOWAY;
  352.         if (miss_ayea == (List *) NULL)
  353.             sprintf(scratchbuf, "%s has no applicable entries with actions\n",
  354.                 node->n_name);
  355.         else
  356.             sprintf(scratchbuf, "%s is missing the ancestor%s %s",
  357.                 node->n_name, length(miss_ayea)==1? "": "s", list_names(miss_ayea));
  358.  
  359.         add_error(node, new_name(scratchbuf), miss_ayea, FALSE);
  360.     }
  361.     or (on_node(node, nf_EXIST) && node->n_utime <= node->n_rtime)
  362.         node->n_kind = n_OK;
  363.     or (on_node(node, nf_PSEUDO) && length(node->n_act) == 0)
  364.     {
  365.         node->n_kind = n_OK;
  366.         for_list (ptr, node->n_old)
  367.         {
  368.             onode = (Node *) ldata(ptr);
  369.             if (is_cando(onode))
  370.                 node->n_kind = n_CANDO;
  371.         }
  372.     }
  373.     else
  374.         node->n_kind = n_CANDO;
  375.     
  376. end:
  377. #ifdef    CAKEDEBUG
  378.     if (cakedebug)
  379.     {
  380.         printf("chase exit\n");
  381.         print_node(node);
  382.     }
  383. #endif
  384.  
  385.     put_trail("do_chase", "finish");
  386. }
  387.  
  388. /*
  389. **    Calculate the "update time" of the given node. The second arg
  390. **    tells us whether we should set a flag for nonvolatile ancestors.
  391. */
  392.  
  393. get_utime(node, planning)
  394. reg    Node    *node;
  395. reg    bool    planning;
  396. {
  397.     extern    time_t    get_youngest(), cake_gettime();
  398.     reg    time_t    youngest;
  399.  
  400.     if ((youngest = get_youngest(node, planning)) == GENESIS)
  401.         node->n_utime = cake_gettime();
  402.     else
  403.         node->n_utime = youngest;
  404. }
  405.  
  406. /*
  407. **    Return the time of update of the youngest dependent.
  408. */
  409.  
  410. time_t
  411. get_youngest(node, planning)
  412. reg    Node    *node;
  413. reg    bool    planning;
  414. {
  415.     reg    List    *ptr;
  416.     reg    Node    *onode;
  417.     reg    time_t    youngest, picked_time;
  418.     reg    List    *errnodes;
  419.  
  420.     youngest = GENESIS;
  421.     errnodes = NULL;
  422.     for_list (ptr, node->n_old)
  423.     {
  424.         onode = (Node *) ldata(ptr);
  425.         if (on_node(onode, nf_ERR))
  426.             errnodes = addtail(errnodes, onode);
  427.         else
  428.         {
  429.             if ((picked_time = pick_time(onode, planning)) > youngest)
  430.                 youngest = picked_time;
  431.         }
  432.     }
  433.  
  434.     if (errnodes != (List *) NULL)
  435.     {
  436.         sprintf(scratchbuf, "don't know what to do with %s because of problems with %s",
  437.             node->n_name, list_names(errnodes));
  438.         add_error(node, new_name(scratchbuf), errnodes, TRUE);
  439.     }
  440.  
  441.     return youngest;
  442. }
  443.  
  444. /*
  445. **    Take care of the names mentioned alongside node's
  446. **    on the left hand side of the given ground entry.
  447. **
  448. **    If a node exists for one of these names we know that
  449. **    a producer must have been chosen for it, and we know that
  450. **    it is not this rule (if it were, then the caller would not
  451. **    have done anything about buddies). This is an inconsistency.
  452. */
  453.  
  454. set_buddies(node, entry)
  455. reg    Node    *node;
  456. reg    Entry    *entry;
  457. {
  458.     extern    Node    *chase_node();
  459.     reg    List    *list;
  460.     reg    List    *ptr;
  461.     reg    Node    *newnode;
  462.     reg    Pat    *pat;
  463.     reg    List    *errnodes;
  464.  
  465.     put_trail("set_buddies", "start");
  466.     list = makelist(node);
  467.     errnodes = NULL;
  468.     for_list (ptr, entry->e_new)
  469.     {
  470.         pat = (Pat *) ldata(ptr);
  471.         if (streq(pat->p_str, node->n_name))
  472.             continue;
  473.         
  474.         if ((newnode = chase_node(pat->p_str)) != (Node *) NULL)
  475.             errnodes = addtail(errnodes, newnode);
  476.         else
  477.         {
  478.             newnode = chase(pat->p_str, pat->p_flag, entry);
  479.             addtail(list, newnode);    /* no assigment */
  480.         }
  481.     }
  482.  
  483.     for_list (ptr, list)
  484.     {
  485.         newnode = (Node *) ldata(ptr);
  486.         newnode->n_new = list;
  487.  
  488.         if (errnodes != (List *) NULL)
  489.         {
  490.             sprintf(scratchbuf, "cannot update %s because of interference with %s %s",
  491.                 newnode->n_name, (length(errnodes) == 1)? "buddy": "buddies",
  492.                 list_names(errnodes));
  493.             add_error(node, new_name(scratchbuf), errnodes, TRUE);
  494.         }
  495.     }
  496.  
  497.     put_trail("set_buddies", "finish");
  498. }
  499.  
  500. /*
  501. **    Pick the appropriate time to use in decisions
  502. **    about dependencies. The algorithms differ in the
  503. **    twp phases: in the execution phase real times
  504. **    override any calculated times.
  505. */
  506.  
  507. time_t
  508. pick_time(node, planning)
  509. reg    Node    *node;
  510. reg    bool    planning;
  511. {
  512.     if (off_node(node, nf_EXIST))
  513.         return node->n_utime;
  514.     
  515.     if (planning)
  516.         return max(node->n_rtime, node->n_utime);
  517.  
  518.     return node->n_rtime;
  519. }
  520.  
  521. /*
  522. **    Chase down the ancestors of the given name.
  523. **    Return the node describing the dependency graph.
  524. **
  525. **    Note that this is merely an interface function,
  526. **    serving to cache previous results and to detect cycles.
  527. */
  528.  
  529. char    *goal_stack[MAXGSTACK];
  530. int    goal_stackp = 0;
  531.  
  532. Node *
  533. chase(name, flag, picked)
  534. reg    char    *name;
  535. reg    bool    flag;
  536. reg    Entry    *picked;
  537. {
  538.     extern    Table    node_tab;
  539.     extern        do_chase();
  540.     extern    char    *find_circle();
  541.     reg    Node    *node;
  542.  
  543.     if ((node = (Node *) lookup_table(node_tab, name)) == NULL)
  544.     {
  545.         node = make_node(name);
  546.         if (goal_stackp >= MAXGSTACK)
  547.         {
  548.             printf("cake: dependency nesting level %d too deep\n", goal_stackp);
  549.             exit_cake(FALSE);
  550.         }
  551.  
  552.         goal_stack[goal_stackp++] = name;
  553. #ifdef    CAKEDEBUG
  554.         cdebug("stack[%d] = %s\n", goal_stackp-1, goal_stack[goal_stackp-1]);
  555. #endif
  556.         set_node(node, nf_BUSY);
  557.         insert_table(node_tab, node);
  558.         do_chase(node, picked);
  559.         --goal_stackp;
  560.         reset_node(node, nf_BUSY);
  561.     }
  562.     else
  563.     {
  564.         cdebug("Using cache for %s\n", name);
  565.         if (on_node(node, nf_BUSY))
  566.         {
  567.             node->n_flag |= flag;
  568.             sprintf(scratchbuf, "%s depends upon itself %s", node->n_name,
  569.                 find_circle(node->n_name));
  570.             add_error(node, new_name(scratchbuf), LNULL, TRUE);
  571.             put_trail("chase", "finish");
  572.             return node;
  573.         }
  574.     }
  575.  
  576.     node->n_flag |= flag;
  577.     put_trail("chase", "finish");
  578.     return node;
  579. }
  580.