zeta/ast.c

   1 // Abstract syntax trees
   2
   3 #include "a.h"
   4 #include "type.h"
   5 #include "runtime.h"
   6 #include "grammar.h"
   7 #include "listimpl.h"
   8
   9 int nmkast;
  10 int nfreeast;
  11 int nleakast;
  12
  13 enum {
  14         Leaked = 255,
  15         AstFreelist = 1,
  16 };
  17
  18 static Ast *astfreed;
  19
  20 Ast*
  21 mkAst(AstOp op, CfgSym *sym)
  22 {
  23         Ast *a;
  24         static Ast *ma;
  25         static int nma;
  26
  27         a = astfreed;
  28         if(a){
  29                 astfreed = (Ast*)a->right;
  30                 a->right = nil;
  31         }else{
  32                 if(nma == 0){
  33                         if(AstFreelist)
  34                                 nma = 4096;
  35                         else
  36                                 nma = 1;
  37                         ma = emallocnz(nma*sizeof *a);
  38                 }
  39                 a = ma++;
  40                 nma--;
  41         }
  42         a->ref = 1;
  43         a->canonical = nil;
  44         a->copiedfrom = nil;
  45         a->op = op;
  46         a->tag = nil;
  47         a->line.file = nil;
  48         a->line.line = 0;
  49         a->sym = sym;
  50         a->rule = nil;
  51         a->right = nil;
  52         a->nright = 0;
  53         a->slotnum = 0;
  54         a->text = nil;
  55         a->parent = NoParentYet;
  56         a->attrmap.root = nil;
  57         a->attrmap.cmp = nil;
  58         nmkast++;
  59         return a;
  60 }
  61
  62 void
  63 astfree(Ast *a)
  64 {
  65         int i;
  66
  67         if(a == nil || a->ref == Leaked || --a->ref > 0)
  68                 return;
  69         assert(a->ref == 0);
  70
  71         for(i=0; i<a->nright; i++)
  72                 astfree(a->right[i]);
  73         free(a->right);
  74         if(AstFreelist){
  75                 a->right = (void*)astfreed;
  76                 astfreed = a;
  77         }else
  78                 free(a);
  79         nfreeast++;
  80 }
  81
  82 // Swap the AST's data but not their ref counts or tree position.
  83 void
  84 astswap(Ast *a, Ast *b)
  85 {
  86         Ast t;
  87
  88         t = *a;
  89         *a = *b;
  90         *b = t;
  91
  92         b->ref = a->ref;
  93         a->ref = t.ref;
  94
  95         b->parent = a->parent;
  96         a->parent = t.parent;
  97 }
  98
  99 Ast*
 100 astdup(Ast *a)
 101 {
 102         if(a && a->ref != Leaked)
 103                 a->ref++;
 104         return a;
 105 }
 106
 107 Ast*
 108 astleak(Ast *ast)
 109 {
 110         int i;
 111
 112         if(ast == nil || ast->ref == Leaked)
 113                 return ast;
 114         ast->ref = Leaked;
 115         nleakast++;
 116         for(i=0; i<ast->nright; i++)
 117                 astleak(ast->right[i]);
 118         return ast;
 119 }
 120
 121 #if 0
 122 void
 123 astrefcheck(Ast *ast, int pass)
 124 {
 125         int i;
 126
 127         switch(pass){
 128         case 0:
 129                 ast->refcheck = 0;
 130                 break;
 131         case 1:
 132                 if(ast->refcheck++ == 0)
 133                         for(i=0; i<ast->nright; i++)
 134                                 astrefcheck(ast->right[i], pass);
 135                 break;
 136         case 2:
 137                 if(ast->refcheck != -1){
 138                         if(ast->ref < ast->refcheck){
 139                                 fprint(2, "%d < %d | %s | %#A\n", ast->ref, ast->refcheck, ast->sym->name, ast);
 140                                 abort();
 141                         }
 142                         for(i=0; i<ast->nright; i++)
 143                                 astrefcheck(ast->right[i], pass);
 144                         ast->refcheck = -1;
 145                 }
 146                 break;
 147         }
 148 }
 149 #endif
 150
 151 Ast*
 152 mkaststring(CfgSym *sym, Name name)
 153 {
 154         Ast *a;
 155
 156         a = mkAst(AstString, sym);
 157         a->text = name;
 158         a->tag = typegramsym(typegram1(sym->ggram->name, nil), sym->name, nil);
 159         assert(a->tag->sym == sym);
 160         return a;
 161 }
 162
 163 Ast*
 164 mkastmerge(Ast *a, Ast *b)
 165 {
 166         int i, n;
 167         Ast *m;
 168
 169         n = 0;
 170         if(a->op == AstMerge)
 171                 n += a->nright;
 172         else
 173                 n++;
 174         if(b->op == AstMerge)
 175                 n += b->nright;
 176         else
 177                 n++;
 178
 179         m = mkAst(AstMerge, a->sym);
 180         m->right = emalloc(n*sizeof m->right[0]);
 181         m->nright = n;
 182         n = 0;
 183         if(a->op == AstMerge)
 184                 for(i=0; i<a->nright; i++)
 185                         m->right[n++] = astdup(a->right[i]);
 186         else
 187                 m->right[n++] = astdup(a);
 188         if(b->op == AstMerge)
 189                 for(i=0; i<b->nright; i++)
 190                         m->right[n++] = astdup(b->right[i]);
 191         else
 192                 m->right[n++] = astdup(b);
 193         assert(n == m->nright);
 194         if(typemax(a->tag, b->tag, &m->tag) < 0)
 195                 panic("typemax %T %T in mkastmerge", a->tag, b->tag);
 196         assert(m->tag->sym == m->sym);
 197         m->line = m->right[0]->line;
 198         return m;
 199 }
 200
 201 Ast*
 202 mkastmerge1(Ast **right, int nright)
 203 {
 204         Ast *m;
 205         Type *t;
 206         int i;
 207
 208         if(nright <= 0)
 209                 panic("mkastmerge %d", nright);
 210
 211         if(nright == 1)
 212                 return right[0];
 213
 214         m = mkAst(AstMerge, right[0]->sym);
 215         m->right = right;
 216         m->nright = nright;
 217         t = right[0]->tag;
 218         for(i=1; i<nright; i++){
 219                 if(typemax(t, right[i]->tag, &t) < 0)
 220                         panic("typemax %T %T in mkastmerge1", t, right[i]->tag);
 221         }
 222         m->tag = t;
 223         assert(m->tag->sym = m->sym);
 224         m->line = m->right[0]->line;
 225         return m;
 226 }
 227
 228 Ast*
 229 mkastrule(CfgRule *r, Ast **right)
 230 {
 231         Ast *a;
 232         Type *t, *tt;
 233         int i, j;
 234
 235         a = mkAst(AstRule, r->left);
 236         a->rule = r;
 237         a->right = right;
 238         a->nright = r->nsavedright;
 239         for(i=j=0; i<a->nright; i++, j++){
 240                 while(nametostr(r->right[j]->name)[0] == '"')
 241                         j++;
 242         //      assert(right[i]->sym == r->right[j]);
 243         }
 244         t = r->tgram;
 245         if(t == nil)
 246                 panic("nil r->tgram in mkastrule %s", r->name);
 247         for(i=0; i<a->nright; i++){
 248                 if(typemax(t, right[i]->tag, &tt) < 0)
 249                         panic("typemax %T %T in mkastrule", t, right[i]->tag);
 250                 t = tt;
 251                 astdup(right[i]);
 252         }
 253         for(i=0; i<a->nright; i++){
 254                 if(right[i]->line.file){
 255                         a->line = right[i]->line;
 256                         break;
 257                 }
 258         }
 259         a->tag = typegramsym(t, r->left->name, nil);
 260         assert(a->tag->sym == a->sym);
 261         return a;
 262 }
 263
 264 Ast*
 265 mkastslot(Type *t, CfgSym *sym, int slotnum)
 266 {
 267         Ast *a;
 268
 269         a = mkAst(AstSlot, sym);
 270         a->slotnum = slotnum;
 271         a->tag = typegramsym(t, sym->name, sym);
 272         assert(a->tag->sym == a->sym);
 273         return a;
 274 }
 275
 276
 277 //============================================================
 278 // Printing
 279
 280 static void astfmtsexpr(Fmt*, Ast*, int, int);
 281 static void astfmttext(Fmt*, Ast*);
 282
 283 // %A - format Ast as infix string (leaves separated by spaces)
 284 // %#A - format Ast as one-line S-expression.
 285 // %#lA - format Ast as multi-line S-expression.
 286 int
 287 astfmt(Fmt *fmt)
 288 {
 289         Ast *ast;
 290
 291         ast = va_arg(fmt->args, Ast*);
 292         if(ast == nil)
 293                 fmtprint(fmt, "<nil ast>");
 294         else if(fmt->flags&FmtSharp)
 295                 astfmtsexpr(fmt, ast, fmt->flags&FmtLong, 0);
 296         else
 297                 astfmttext(fmt, ast);
 298         return 0;
 299 }
 300
 301 static char*
 302 dots(int n)
 303 {
 304         int i;
 305         static int m = -1;
 306         static char *dots;
 307
 308         if(n > m) {
 309                 m = n + 128;
 310                 free(dots);
 311                 dots = emalloc(m+1);
 312                 char *p = dots;
 313                 for(i = 0; i < m; i++)
 314                         *p++ = ". "[i%2];
 315                 *p = 0;
 316         }
 317         return dots;
 318 }
 319
 320 static void
 321 astfmtsexpr(Fmt *fmt, Ast *ast, int newlines, int indent)
 322 {
 323         int i;
 324
 325         switch(ast->op){
 326         case AstSlot:
 327                 fmtprint(fmt, " ?slot.%s", ast->sym->name);
 328                 break;
 329         case AstString:
 330                 fmtprint(fmt, " '%s", ast->text);
 331                 break;
 332         case AstMerge:
 333                 fmtprint(fmt, " (%s.merge", ast->sym->name);
 334                 goto right;
 335         case AstRule:
 336                 fmtprint(fmt, " (%R", ast->rule);
 337         right:
 338                 for(i=0; i<ast->nright; i++){
 339                         if(newlines)
 340                                 fmtprint(fmt, "\n%.*s", indent*2, dots(indent*2));
 341                         astfmtsexpr(fmt, ast->right[i], newlines, indent+1);
 342                 }
 343                 fmtprint(fmt, ")");
 344                 break;
 345         }
 346 }
 347
 348 static void
 349 astfmttext(Fmt *fmt, Ast *ast)
 350 {
 351         int i, j;
 352         CfgSym *sym;
 353         char *s;
 354
 355         switch(ast->op){
 356         case AstSlot:
 357                 fmtprint(fmt, "\\%d ", ast->slotnum);
 358                 break;
 359         case AstString:
 360                 fmtprint(fmt, "%s ", ast->text);
 361                 break;
 362         case AstRule:
 363                 j = 0;
 364                 for(i=0; i<ast->rule->nright; i++){
 365                         sym = ast->rule->right[i];
 366                         s = nametostr(sym->name);
 367                         if(s[0] == '"')
 368                                 fmtprint(fmt, "%.*s ", utfnlen(s+1, strlen(s+1)-1), s+1);
 369                         else
 370                                 astfmttext(fmt, ast->right[j++]);
 371                 }
 372                 assert(j == ast->nright);
 373                 break;
 374         case AstMerge:
 375                 fmtprint(fmt, "{M: %A}", ast->right[0]);
 376                 break;
 377         }
 378 }
 379
 380 //============================================================
 381 // Zeta interface
 382 // Must use astright, not ast->right, to preserve parent pointers.
 383
 384 Ast*
 385 astparent(Ast *ast, Type *t)
 386 {
 387         if(ast->parent == NoParentYet)
 388                 ast->parent = nil;
 389         for(ast=ast->parent; ast; ast=ast->parent){
 390                 if(t == nil || issubtype(ast->tag, t))
 391                         return ast;
 392                 if(ast->parent == NoParentYet)
 393                         ast->parent = nil;
 394         }
 395         return nil;
 396 }
 397
 398 Ast*
 399 astprev_attr(Ast *ast)
 400 {
 401         int i;
 402         Ast *p;
 403
 404         p = astparent(ast, nil);
 405         if(p == nil)
 406                 return nil;
 407         for(i=0; i<p->nright; i++){
 408                 if(p->right[i] == ast){
 409                         for(i--; i>=0; i--)
 410                                 if(!p->right[i]->sym->nocopy)
 411                                         return astright(p, i);
 412                         return nil;
 413                 }
 414         }
 415         fprint(2, "cannot find self in parent!");
 416         abort();
 417         return nil;
 418 }
 419
 420 Ast*
 421 astnext_attr(Ast *ast)
 422 {
 423         int i;
 424         Ast *p;
 425
 426         p = astparent(ast, nil);
 427         if(p == nil)
 428                 return nil;
 429         for(i=0; i<p->nright; i++){
 430                 if(p->right[i] == ast){
 431                         for(i++; i<p->nright; i++)
 432                                 if(!p->right[i]->sym->nocopy)
 433                                         return astright(p, i);
 434                         return nil;
 435                 }
 436         }
 437         fprint(2, "cannot find self in parent!");
 438         abort();
 439         return nil;
 440 }
 441
 442 Ast*
 443 astcopiedfrom_attr(Ast *ast)
 444 {
 445         if(ast == nil || ast->copiedfrom == nil)
 446                 return nil;
 447         return ast->copiedfrom;
 448 }
 449
 450 Ast*
 451 astcvtslot(Ast *ast, Type *t)
 452 {
 453         Ast *a;
 454
 455         if(ast->op != AstSlot)
 456                 abort();
 457         a = mkastslot(t, t->sym, ast->slotnum);
 458         return a;
 459 }
 460
 461 Ast*
 462 astright(Ast *ast, int i)
 463 {
 464         Ast *a;
 465
 466         assert(i >= 0 && i < ast->nright);
 467         a = ast->right[i];
 468         if(a->sym->nocopy)
 469                 return a;
 470         if(a->parent == ast)
 471                 return a;
 472         if(a->parent == NoParentYet){
 473                 a->parent = ast;
 474                 return a;
 475         }
 476         ast->right[i] = a = astcopy(a);
 477         a->parent = ast;
 478         return a;
 479 }
 480
 481 Ast*
 482 asttoquestion(Ast *ast, CfgSym *sym)
 483 {
 484         Ast **right;
 485
 486         // name?:
 487         // name?: name
 488         assert(sym);
 489         assert(sym->nrule == 2);
 490         assert(sym->rule[0]->nright == 0);
 491         assert(sym->rule[1]->nright == 1);
 492         assert(sym->rule[1]->nsavedright == 1);
 493
 494         if(ast == nil)
 495                 return mkastrule(sym->rule[0], nil);
 496
 497         assert(ast->sym == sym->rule[1]->right[0]);
 498         right = emalloc(1*sizeof right[0]);
 499         right[0] = ast;
 500         return mkastrule(sym->rule[1], right);
 501 }
 502
 503 Ast*
 504 astfromquestion(Ast *ast, CfgSym *sym)
 505 {
 506         // name?:
 507         // name?: name
 508         assert(sym);
 509         assert(sym->nrule == 2);
 510         assert(sym->rule[0]->nright == 0);
 511         assert(sym->rule[1]->nright == 1);
 512         assert(sym->rule[1]->nsavedright == 1);
 513
 514         assert(ast->sym == sym);
 515
 516         if(ast->nright == 0)
 517                 return nil;
 518         return astright(ast, 0);
 519 }
 520
 521 Ast*
 522 astlisttostar(Zlist *zl, CfgSym *sym)
 523 {
 524         Ast **right;
 525
 526         // name*:
 527         // name*: name+
 528         assert(sym);
 529         assert(sym->nrule == 2);
 530         assert(sym->rule[0]->nright == 0);
 531         assert(sym->rule[1]->nright == 1);
 532         assert(sym->rule[1]->nsavedright == 1);
 533
 534         if(zl == nil)
 535                 return mkastrule(sym->rule[0], nil);
 536
 537         right = emalloc(1*sizeof right[0]);
 538         right[0] = astlisttoplus(zl, sym->rule[1]->right[0]);
 539         if(right[0] == nil)
 540                 return nil;
 541         return mkastrule(sym->rule[1], right);
 542 }
 543
 544 int
 545 aststartolist(Ast *ast, CfgSym *sym, Zlist **l)
 546 {
 547         // name*:
 548         // name*: name+
 549         assert(sym);
 550         assert(sym->nrule == 2);
 551         assert(sym->rule[0]->nright == 0);
 552         assert(sym->rule[1]->nright == 1);
 553         assert(sym->rule[1]->nsavedright == 1);
 554
 555         assert(ast->sym == sym);
 556
 557         if(ast->op == AstSlot)
 558                 return -1;
 559
 560         if(ast->nright == 0){
 561                 *l = nil;
 562                 return 0;
 563         }
 564         return astplustolist(astright(ast, 0), sym->rule[1]->right[0], l);
 565 }
 566
 567 Ast*
 568 _astlisttoplus(Zlist *zl, CfgSym *sym)
 569 {
 570         Ast **right;
 571
 572         // name+: name
 573         // name+: name+ sep name
 574         assert(sym);
 575         assert(sym->nrule == 2);
 576         assert(sym->rule[0]->nright == 1);
 577         assert(sym->rule[1]->nright == 2 || sym->rule[1]->nright == 3);
 578         assert(sym->rule[1]->nsavedright == 2);
 579         if(LeftRecursive)
 580                 assert(sym->rule[1]->right[0] == sym);
 581         else
 582                 assert(sym->rule[1]->right[sym->rule[1]->nright-1] == sym);
 583
 584         if(zl == nil){
 585                 fprint(2, "convert nil list to %s", sym->name);
 586                 abort();
 587         }
 588
 589         assert(zl->hd);
 590         assert(((Ast*)zl->hd)->sym == sym->rule[0]->right[0]);
 591
 592         if(zl->tl == nil){
 593                 right = emalloc(1*sizeof right[0]);
 594                 right[0] = zl->hd;
 595                 return mkastrule(sym->rule[0], right);
 596         }
 597
 598         right = emalloc(2*sizeof right[0]);
 599         if(LeftRecursive){
 600                 right[0] = _astlisttoplus(zl->tl, sym);
 601                 right[1] = zl->hd;
 602         }else{
 603                 right[0] = zl->hd;
 604                 right[1] = _astlisttoplus(zl->tl, sym);
 605         }
 606         return mkastrule(sym->rule[1], right);
 607 }
 608
 609 Ast*
 610 astlisttoplus(Zlist *zl, CfgSym *sym)
 611 {
 612         if(LeftRecursive)
 613                 zl = revZlist(zl);
 614         return _astlisttoplus(zl, sym);
 615 }
 616
 617 int
 618 astplustolist(Ast *ast, CfgSym *sym, Zlist **l)
 619 {
 620         Zlist *zl;
 621
 622         // name+: name
 623         // name+: name+ sep name
 624         assert(sym);
 625         assert(sym->nrule == 2);
 626         assert(sym->rule[0]->nright == 1);
 627         assert(sym->rule[1]->nright == 2 || sym->rule[1]->nright == 3);
 628         assert(sym->rule[1]->nsavedright == 2);
 629         if(LeftRecursive)
 630                 assert(sym->rule[1]->right[0] == sym);
 631         else
 632                 assert(sym->rule[1]->right[sym->rule[1]->nright-1] == sym);
 633         assert(ast->sym == sym);
 634
 635         zl = nil;
 636         for(;;){
 637                 assert(ast->sym == sym);
 638                 if(ast->op == AstSlot)
 639                         return -1;
 640                 switch(ast->nright){
 641                 default:
 642                         panic("astplustolist");
 643                 case 1:
 644                         ast = astright(ast, 0);
 645                         zl = mkZlist(ast, zl);
 646                         goto out;
 647                 case 2:
 648                         if(LeftRecursive){
 649                                 Ast *last, *prefix;
 650                                 last = astright(ast, ast->nright-1);
 651                                 prefix = astright(ast, 0);
 652                                 zl = mkZlist(last, zl);
 653                                 ast = prefix;
 654                         }else{
 655                                 Ast *first, *suffix;
 656                                 first = astright(ast, 0);
 657                                 suffix = astright(ast, ast->nright-1);
 658                                 zl = mkZlist(first, zl);
 659                                 ast = suffix;
 660                         }
 661                         break;
 662                 }
 663         }
 664 out:
 665         if(!LeftRecursive)
 666                 zl = revZlist(zl);
 667         *l = zl;
 668         return 0;
 669 }
 670
 671 Zlist*
 672 asttolist(Ast *ast)
 673 {
 674         char *s;
 675         Zlist *l;
 676
 677         if(ast == nil)
 678                 return nil;
 679         s = nametostr(ast->sym->name);
 680         switch(s[strlen(s)-1]){
 681         case '*':
 682                 if(aststartolist(ast, ast->sym, &l) < 0)
 683                         return nil;
 684                 return l;
 685         case '+':
 686                 if(astplustolist(ast, ast->sym, &l) < 0)
 687                         return nil;
 688                 return l;
 689         default:
 690                 return nil;
 691         }
 692 }
 693
 694 Zarray*
 695 astsplit(Ast *ast)
 696 {
 697         int i, n;
 698         Zarray *za;
 699
 700         n = 0;
 701         for(i=0; i<ast->nright; i++)
 702                 if(!ast->right[i]->sym->nocopy)
 703                         n++;
 704         za = mkZarray(n);
 705         n = 0;
 706         for(i=0; i<ast->nright; i++)
 707                 if(!ast->right[i]->sym->nocopy)
 708                         za->a[n++] = astright(ast, i);
 709         assert(n == za->n);
 710         return za;
 711 }
 712
 713 Ast*
 714 astjoin(Ast *ast, Zarray *za)
 715 {
 716         Ast **right;
 717         Ast *a;
 718         int i, n;
 719
 720         right = emalloc(ast->nright*sizeof right[0]);
 721         n = 0;
 722         for(i=0; i<ast->nright; i++){
 723                 if(ast->right[i]->sym->nocopy)
 724                         right[i] = ast->right[i];
 725                 else
 726                         right[i] = za->a[n++];
 727         }
 728         assert(n == za->n);
 729
 730         if(ast->op == AstMerge)
 731                 a = mkastmerge1(right, za->n);
 732         else if(ast->op == AstRule){
 733                 n = 0;
 734                 for(i=0; i<ast->rule->nright; i++){
 735                         if(nametostr(ast->rule->right[i]->name)[0] == '"')
 736                                 continue;
 737                         if(right[n]->sym != ast->rule->right[i]){
 738                                 fprint(2, "bad right %d / %R: %s %s\n", i, ast->rule, right[i]->sym->name, ast->rule->right[i]->name);
 739                                 assert(right[n]->sym == ast->rule->right[i]);
 740                         }
 741                         n++;
 742                 }
 743                 assert(n == ast->nright);
 744                 a = mkastrule(ast->rule, right);
 745         }
 746         else{
 747                 panic("astjoin: %#A\n", ast);
 748                 return nil;
 749         }
 750
 751         a = astleak(a);
 752         a->copiedfrom = ast;    // XXX is this correct?
 753         a->line = ast->line;
 754         return a;
 755 }
 756
 757 Ast*
 758 astcopy(Ast *ast)
 759 {
 760         int i;
 761         Ast *a;
 762
 763         if(ast == nil)
 764                 return nil;
 765         if(sys_astchatty > 0)
 766                 fprint(2, "astcopy: %s\n", ast->sym->name);
 767         a = mkAst(ast->op, ast->sym);
 768         a->slotnum = ast->slotnum;
 769         a->tag = ast->tag;
 770         a->text = ast->text;
 771         a->rule = ast->rule;
 772         if(ast->nright > 0){
 773                 a->right = emalloc(ast->nright*sizeof a->right[0]);
 774                 for(i=0; i<ast->nright; i++)
 775                         a->right[i] = astdup(ast->right[i]);
 776                 a->nright = ast->nright;
 777         }
 778         a->copiedfrom = ast;
 779         a->line = ast->line;
 780 //fprint(2, "astcopy: %p/%p -> %p\n", ast, ast->parent, a);
 781         return astleak(a);
 782 }
 783
 784 Ast*
 785 astlastkid(Ast *ast)
 786 {
 787         int i;
 788
 789         if(ast == nil)
 790                 return nil;
 791         for(i=ast->nright-1; i>=0; i--)
 792                 if(!ast->right[i]->sym->nocopy)
 793                         return astright(ast, i);
 794         return nil;
 795 }
 796
 797 int
 798 astmerged(Ast *ast)
 799 {
 800         return ast && ast->op == AstMerge;
 801 }
 802
 803 int
 804 astslotted(Ast *ast)
 805 {
 806         return ast && ast->op == AstSlot;
 807 }
 808
 809 Name
 810 asttostring(Ast *ast)
 811 {
 812         char *s, *t, *e;
 813         Name x;
 814
 815         if(ast == nil)
 816                 return nameof("");
 817         s = smprint("%A", ast);
 818         t = s;
 819         while(*t == ' ')
 820                 t++;
 821         e = t+strlen(t);
 822         while(e > t && e[-1] == ' ')
 823                 e--;
 824         x = nameofn(t, e-t);
 825         free(s);
 826         return x;
 827
 828 }
 829
 830 Name
 831 astlisp(Ast *ast)
 832 {
 833         char *s, *t, *e;
 834         Name x;
 835
 836         if(ast == nil)
 837                 return nameof("(nil)");
 838         s = smprint("%#A", ast);
 839         t = s;
 840         while(*t == ' ')
 841                 t++;
 842         e = t+strlen(t);
 843         while(e > t && e[-1] == ' ')
 844                 e--;
 845         x = nameofn(t, e-t);
 846         free(s);
 847         return x;
 848
 849 }
 850
 851 Name
 852 astlong(Ast *ast)
 853 {
 854         char *s, *t, *e;
 855         Name x;
 856
 857         if(ast == nil)
 858                 return nameof("(nil)");
 859         s = smprint("%#lA", ast);
 860         t = s;
 861         while(*t == ' ')
 862                 t++;
 863         e = t+strlen(t);
 864         while(e > t && e[-1] == ' ')
 865                 e--;
 866         x = nameofn(t, e-t);
 867         free(s);
 868         return x;
 869
 870 }
 871
 872 AttrLink *attrlinks;
 873 int nattrinfo;
 874 AttrInfo **attrinfo;
 875
 876 int
 877 attrinfocmp(const void *va, const void *vb)
 878 {
 879         AttrInfo *a, *b;
 880
 881         a = *(AttrInfo**)va;
 882         b = *(AttrInfo**)vb;
 883         return b->ncompute - a->ncompute;
 884 }
 885
 886 void
 887 regattr(AttrInfo *info)
 888 {
 889         if(info->registered)
 890                 return;
 891         attrinfo = erealloc(attrinfo, (nattrinfo+1)*sizeof attrinfo[0]);
 892         attrinfo[nattrinfo++] = info;
 893         info->registered = 1;
 894 }
 895
 896 void
 897 attrstats(void)
 898 {
 899         int i;
 900         AttrInfo *info;
 901
 902         qsort(attrinfo, nattrinfo, sizeof attrinfo[0], attrinfocmp);
 903         for(i=0; i<nattrinfo; i++){
 904                 info = attrinfo[i];
 905                 print("%10d %s %T\n", info->ncompute, info->name, info->type);
 906         }
 907 }
 908
 909 Attr*
 910 get_attribute(Ast *ast, AttrInfo *info)
 911 {
 912         Attr *a;
 913         static Attr *ma;
 914         static int nma;
 915
 916         if(ast == nil){
 917                 fprint(2, "%s called on nil\n", info->name);
 918                 abort();
 919                 // XXX maybe return 0?
 920         }
 921         if(!info->registered)
 922                 regattr(info);
 923         if((a = mapget(&ast->attrmap, info)) == nil){
 924                 if(nma == 0){
 925                         nma = 100;
 926                         ma = emallocnz(nma*sizeof ma[0]);
 927                 }
 928                 a = ma++;
 929                 nma--;
 930                 a->state = 0;
 931                 a->data = nil;
 932                 mapputelem(&ast->attrmap, info, a, &a->me);
 933         }
 934         return a;
 935 }
 936
 937 void
 938 set_attribute(Ast *ast, AttrInfo *info, Zpoly data)
 939 {
 940         Attr *a;
 941
 942         a = get_attribute(ast, info);
 943         if(a->state == AttrComputing)
 944                 fprint(2, "warning: changing attribute %s during its computation\n",
 945                         info->name);
 946         else if(a->state == AttrInit){
 947                 fprint(2, "warning: changing attribute %s after its computation\n",
 948                         info->name);
 949                 abort();
 950         }
 951         a->state = AttrInit;
 952         a->data = data;
 953 }
 954
 955 void
 956 attrloop(AttrInfo *info)
 957 {
 958         AttrLink *l;
 959
 960         fprint(2, "attribute loop:\n");
 961         fprint(2, "\t%s: %s\n", info->pos, info->name);
 962         for(l=attrlinks; l; l=l->next)
 963                 fprint(2, "\t%s: %s : %T\n", l->info->pos, l->info->name, l->ast->tag);
 964 }
 965
 966
 967 Zpoly*
 968 astline(Ast *ast)
 969 {
 970         Zpoly *p;
 971
 972         p = emalloc(2*sizeof p[0]);
 973         p[0] = ast->line.file;
 974         p[1] = (Zpoly)ast->line.line;
 975         return p;
 976 }
 977
 978 Ast*
 979 astcanonicalize(Ast *ast)
 980 {
 981         int i, changed;
 982         Ast **right, **oldright;
 983         Ast *a, *c;
 984         Zfn *f;
 985
 986         if(ast->canonical)
 987                 return ast->canonical;
 988
 989         if(ast->op == AstSlot)
 990                 return ast;
 991
 992         right = emalloc(ast->nright*sizeof ast->right[0]);
 993         changed = 0;
 994         for(i=0; i<ast->nright; i++){
 995                 right[i] = astcanonicalize(ast->right[i]);
 996                 if(right[i] != ast->right[i])
 997                         changed = 1;
 998         }
 999
1000         if(changed){
1001                 // Have to make a new AST to pass to the canonicalize function.
1002                 // Easier to reuse astcopy, temporarily editing ast.
1003                 oldright = ast->right;
1004                 ast->right = right;
1005                 a = astcopy(ast);
1006                 ast->right = oldright;
1007         }else
1008                 a = ast;
1009
1010         if(ast->sym != ast->tag->sym)
1011                 fprint(2, "oops: %s vs %s\n", ast->sym->name, ast->tag->sym->name);
1012
1013         assert(ast->sym == ast->tag->sym);
1014         if(ast->op == AstRule){
1015                 f = ast->sym->canonical;
1016                 ast->sym->used_canonical = 1;
1017 //extern Zfn nop_canonical;
1018 //      if(f == &nop_canonical)
1019 //              fprint(2, "no canonical for %T\n", ast->tag);
1020 //      else
1021 //              fprint(2, "canonical for %T\n", ast->tag);
1022
1023                 c = ((Ast*(*)(void*, Ast*))f->fn)(f->escf, astleak(a));
1024
1025                 if(c == nil){
1026                         fprint(2, "astcanonicalize(%T) returned nil for %A\n",
1027                                 ast->tag, a);
1028                         abort();
1029                 }
1030         }else
1031                 c = ast;
1032
1033         ast->canonical = c;
1034         a->canonical = c;
1035         c->canonical = c;
1036         return c;
1037 }
1038
1039 int
1040 astsame(Ast *a, Ast *b)
1041 {
1042         int i;
1043
1044         if(a == nil && b == nil)
1045                 return 1;
1046         if(a == nil || b == nil)
1047                 return 0;
1048         if(a->op != b->op
1049         || a->sym != b->sym
1050         || a->rule != b->rule
1051         || a->text != b->text)
1052                 return 0;
1053         for(i=0; i<a->nright; i++)
1054                 if(!astsame(a->right[i], b->right[i]))
1055                         return 0;
1056         return 1;
1057 }
1058
1059 void
1060 astremovecopiedfrom(Ast *ast)
1061 {
1062         int i;
1063
1064         ast->copiedfrom = nil;
1065         ast->parent = NoParentYet;
1066         for(i=0; i<ast->nright; i++)
1067                 astremovecopiedfrom(ast->right[i]);
1068 }
1069
1070
1071 LISTIMPL(Ast)