Return to graph.c CVS log

Up to [Research Unix] / researchv10no / cmd / mk / src

Annotation of researchv10no/cmd/mk/src/graph.c, revision 1.1

1.1     ! root        1: #include       "mk.h"
        !             2: 
        !             3: static Node *newnode(), *applyrules();
        !             4: static cyclechk(), vacuous(), ambiguous(), attribute();
        !             5: 
        !             6: Node *
        !             7: graph(target)
        !             8:        char *target;
        !             9: {
        !            10:        Node *node;
        !            11:        char *cnt;
        !            12: 
        !            13:        node = applyrules(target, cnt = rulecnt());
        !            14:        free(cnt);
        !            15:        cyclechk(node);
        !            16:        node->flags |= PROBABLE;        /* make sure it doesn't get deleted */
        !            17:        (void)vacuous(node);
        !            18:        (void)ambiguous(node);
        !            19:        (void)attribute(node);
        !            20:        return(node);
        !            21: }
        !            22: 
        !            23: static Node *
        !            24: applyrules(target, cnt)
        !            25:        char *target, *cnt;
        !            26: {
        !            27:        Symtab *sym;
        !            28:        Node *node;
        !            29:        Rule *r;
        !            30:        Arc head, *a = &head;
        !            31:        Word *w;
        !            32:        char stem[NAMEBLOCK], buf[NAMEBLOCK];
        !            33:        regsubexp rmatch[NREGEXP];
        !            34: 
        !            35: /*     print("appplyrules(%ld='%s')\n", target, target);/**/
        !            36:        if(sym = symlook(target, S_NODE, (char *)0)){
        !            37:                node = (Node *)(sym->value);
        !            38:                return(node);
        !            39:        }
        !            40:        target = strdup(target);
        !            41:        node = newnode(target);
        !            42:        head.n = 0;
        !            43:        head.next = 0;
        !            44:        sym = symlook(target, S_TARGET, (char *)0);
        !            45:        for(r = sym? (Rule *)(sym->value):0; r; r = r->chain){
        !            46:                if(r->attr&META) continue;
        !            47:                if(strcmp(target, r->target)) continue;
        !            48:                if(cnt[r->rule] >= nreps) continue;
        !            49:                cnt[r->rule]++;
        !            50:                node->flags |= PROBABLE;
        !            51:                if(r->attr&VIR)
        !            52:                        node->flags |= VIRTUAL;
        !            53:                if(r->attr&NOREC)
        !            54:                        node->flags |= NORECIPE;
        !            55:                if(r->attr&DEL)
        !            56:                        node->flags |= DELETE;
        !            57:                if(r->tail == 0)
        !            58:                        a = a->next = newarc((Node *)0, r, "", rmatch);
        !            59:                else
        !            60:                        for(w = r->tail; w; w = w->next){
        !            61:                                a = a->next = newarc(applyrules(w->s, cnt), r, "", rmatch);
        !            62:                }
        !            63:                cnt[r->rule]--;
        !            64:                head.n = node;
        !            65:        }
        !            66:        for(r = metarules; r; r = r->next){
        !            67:                if(r->attr&REGEXP){
        !            68:                        stem[0] = 0;
        !            69:                        patrule = r;
        !            70:                        if(regexec(r->pat, node->name, rmatch, NREGEXP) == 0)
        !            71:                                continue;
        !            72:                } else {
        !            73:                        if(!match(node->name, r->target, stem)) continue;
        !            74:                }
        !            75:                if(cnt[r->rule] >= nreps) continue;
        !            76:                cnt[r->rule]++;
        !            77:                if(r->attr&VIR)
        !            78:                        node->flags |= VIRTUAL;
        !            79:                if(r->attr&NOREC)
        !            80:                        node->flags |= NORECIPE;
        !            81:                if(r->attr&DEL)
        !            82:                        node->flags |= DELETE;
        !            83:                if(r->tail == 0)
        !            84:                        a = a->next = newarc((Node *)0, r, strdup(stem), rmatch);
        !            85:                else
        !            86:                        for(w = r->tail; w; w = w->next){
        !            87:                                if(r->attr&REGEXP)
        !            88:                                        regsub(w->s, buf, rmatch, NREGEXP);
        !            89:                                else
        !            90:                                        subst(stem, w->s, buf);
        !            91:                                a = a->next = newarc(applyrules(buf, cnt), r, strdup(stem), rmatch);
        !            92:                        }
        !            93:                cnt[r->rule]--;
        !            94:        }
        !            95:        a->next = node->prereqs;
        !            96:        node->prereqs = head.next;
        !            97:        return(node);
        !            98: }
        !            99: 
        !           100: static
        !           101: togo(node)
        !           102:        register Node *node;
        !           103: {
        !           104:        register Arc *la, *a;
        !           105: 
        !           106:        /* delete them now */
        !           107:        for(a = node->prereqs; a; la = a, a = a->next)
        !           108:                if(a->flag&TOGO){
        !           109:                        if(a == node->prereqs)
        !           110:                                node->prereqs = a->next;
        !           111:                        else
        !           112:                                la->next = a->next, a = la;
        !           113:                }
        !           114: }
        !           115: 
        !           116: static
        !           117: vacuous(node)
        !           118:        register Node *node;
        !           119: {
        !           120:        register Arc *la, *a;
        !           121:        int vac = !(node->flags&PROBABLE);
        !           122: 
        !           123:        if(node->flags&READY)
        !           124:                return(node->flags&VACUOUS);
        !           125:        node->flags |= READY;
        !           126:        for(a = node->prereqs; a; a = a->next)
        !           127:                if(a->n && vacuous(a->n) && (a->r->attr&META))
        !           128:                        a->flag |= TOGO;
        !           129:                else
        !           130:                        vac = 0;
        !           131:        /* if a rule generated arcs that DON'T go; no others from that rule go */
        !           132:        for(a = node->prereqs; a; a = a->next)
        !           133:                if((a->flag&TOGO) == 0)
        !           134:                        for(la = node->prereqs; la; la = la->next)
        !           135:                                if((la->flag&TOGO) && (la->r == a->r)){
        !           136:                                        la->flag &= ~TOGO;
        !           137:                                }
        !           138:        togo(node);
        !           139:        if(vac)
        !           140:                node->flags |= VACUOUS;
        !           141:        return(vac);
        !           142: }
        !           143: 
        !           144: static Node *
        !           145: newnode(name)
        !           146:        char *name;
        !           147: {
        !           148:        register Node *node;
        !           149: 
        !           150:        node = (Node *)Malloc(sizeof(Node));
        !           151:        symlook(name, S_NODE, (char *)node);
        !           152:        node->name = name;
        !           153:        node->time = timeof(name, 0);
        !           154:        node->prereqs = 0;
        !           155:        node->flags = node->time? PROBABLE : 0;
        !           156:        node->next = 0;
        !           157:        return(node);
        !           158: }
        !           159: 
        !           160: dumpn(s, n)
        !           161:        char *s;
        !           162:        register Node *n;
        !           163: {
        !           164:        char buf[1024];
        !           165:        register Arc *a;
        !           166: 
        !           167:        sprint(buf, "%s   ", (*s == ' ')? s:"");
        !           168:        Fprint(1, "%s%s@%ld: time=%ld flags=0x%x next=%ld\n",
        !           169:                s, n->name, n, n->time, n->flags, n->next);
        !           170:        for(a = n->prereqs; a; a = a->next)
        !           171:                dumpa(buf, a);
        !           172: }
        !           173: 
        !           174: static
        !           175: trace(s, a)
        !           176:        char *s;
        !           177:        register Arc *a;
        !           178: {
        !           179:        Fprint(2, "\t%s", s);
        !           180:        while(a){
        !           181:                Fprint(2, " <-(%s:%d)- %s", a->r->file, a->r->line,
        !           182:                        a->n? a->n->name:"");
        !           183:                if(a->n){
        !           184:                        for(a = a->n->prereqs; a; a = a->next)
        !           185:                                if(*a->r->recipe) break;
        !           186:                } else
        !           187:                        a = 0;
        !           188:        }
        !           189:        Fputc(2, '\n');
        !           190: }
        !           191: 
        !           192: static
        !           193: cyclechk(n)
        !           194:        register Node *n;
        !           195: {
        !           196:        register Arc *a;
        !           197: 
        !           198:        if((n->flags&CYCLE) && n->prereqs){
        !           199:                Fprint(2, "mk: cycle in graph detected at target %s\n", n->name);
        !           200:                Exit();
        !           201:        }
        !           202:        n->flags |= CYCLE;
        !           203:        for(a = n->prereqs; a; a = a->next)
        !           204:                if(a->n)
        !           205:                        cyclechk(a->n);
        !           206:        n->flags &= ~CYCLE;
        !           207: }
        !           208: 
        !           209: static
        !           210: ambiguous(n)
        !           211:        register Node *n;
        !           212: {
        !           213:        register Arc *a;
        !           214:        register Rule *r = 0;
        !           215:        Arc *la;
        !           216:        int bad = 0;
        !           217: 
        !           218:        for(a = n->prereqs; a; a = a->next){
        !           219:                if(a->n)
        !           220:                        ambiguous(a->n);
        !           221:                if(*a->r->recipe == 0) continue;
        !           222:                if(r == 0)
        !           223:                        r = a->r, la = a;
        !           224:                else{
        !           225:                        if(r->recipe != a->r->recipe){
        !           226:                                if((r->attr&META) && !(a->r->attr&META)){
        !           227:                                        la->flag |= TOGO;
        !           228:                                        r = a->r, la = a;
        !           229:                                } else if(!(r->attr&META) && (a->r->attr&META)){
        !           230:                                        a->flag |= TOGO;
        !           231:                                        continue;
        !           232:                                }
        !           233:                        }
        !           234:                        if(r->recipe != a->r->recipe){
        !           235:                                if(bad == 0){
        !           236:                                        Fprint(2, "mk: ambiguous recipes for %s:\n", n->name);
        !           237:                                        bad = 1;
        !           238:                                        trace(n->name, la);
        !           239:                                }
        !           240:                                trace(n->name, a);
        !           241:                        }
        !           242:                }
        !           243:        }
        !           244:        if(bad)
        !           245:                Exit();
        !           246:        togo(n);
        !           247: }
        !           248: 
        !           249: static
        !           250: attribute(n)
        !           251:        register Node *n;
        !           252: {
        !           253:        register Arc *a;
        !           254: 
        !           255:        for(a = n->prereqs; a; a = a->next){
        !           256:                if(a->r->attr&VIR)
        !           257:                        n->flags |= VIRTUAL;
        !           258:                if(a->r->attr&NOREC)
        !           259:                        n->flags |= NORECIPE;
        !           260:                if(a->r->attr&DEL)
        !           261:                        n->flags |= DELETE;
        !           262:                if(a->n)
        !           263:                        attribute(a->n);
        !           264:        }
        !           265:        if(n->flags&VIRTUAL)
        !           266:                n->time = 0;
        !           267: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.