tools/leaky/leaky.cpp

   1 /* ***** BEGIN LICENSE BLOCK *****
   2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   3  *
   4  * The contents of this file are subject to the Mozilla Public License Version
   5  * 1.1 (the "License"); you may not use this file except in compliance with
   6  * the License. You may obtain a copy of the License at
   7  * http://www.mozilla.org/MPL/
   8  *
   9  * Software distributed under the License is distributed on an "AS IS" basis,
  10  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  11  * for the specific language governing rights and limitations under the
  12  * License.
  13  *
  14  * The Original Code is mozilla.org code.
  15  *
  16  * The Initial Developer of the Original Code is Kipp E.B. Hickman.
  17  * Portions created by the Initial Developer are Copyright (C) 1999
  18  * the Initial Developer. All Rights Reserved.
  19  *
  20  * Contributor(s):
  21  *
  22  * Alternatively, the contents of this file may be used under the terms of
  23  * either the GNU General Public License Version 2 or later (the "GPL"), or
  24  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  25  * in which case the provisions of the GPL or the LGPL are applicable instead
  26  * of those above. If you wish to allow use of your version of this file only
  27  * under the terms of either the GPL or the LGPL, and not to allow others to
  28  * use your version of this file under the terms of the MPL, indicate your
  29  * decision by deleting the provisions above and replace them with the notice
  30  * and other provisions required by the GPL or the LGPL. If you do not delete
  31  * the provisions above, a recipient may use your version of this file under
  32  * the terms of any one of the MPL, the GPL or the LGPL.
  33  *
  34  * ***** END LICENSE BLOCK ***** */
  35
  36 #include "leaky.h"
  37 #include "dict.h"
  38
  39 #include <sys/types.h>
  40 #include <sys/mman.h>
  41 #include <sys/stat.h>
  42 #include <fcntl.h>
  43 #include <unistd.h>
  44 #include <string.h>
  45 #ifndef NTO
  46 #include <getopt.h>
  47 #endif
  48 #include <assert.h>
  49 #include <stdlib.h>
  50 #include <stdio.h>
  51
  52 #ifdef NTO
  53 #include <mem.h>
  54 #endif
  55
  56 #ifndef FALSE
  57 #define FALSE 0
  58 #endif
  59 #ifndef TRUE
  60 #define TRUE 1
  61 #endif
  62
  63 static const u_int DefaultBuckets = 10007;      // arbitrary, but prime
  64 static const u_int MaxBuckets = 1000003;        // arbitrary, but prime
  65
  66 //----------------------------------------------------------------------
  67
  68 int main(int argc, char** argv)
  69 {
  70   leaky* l = new leaky;
  71
  72   l->initialize(argc, argv);
  73   l->open();
  74   return 0;
  75 }
  76
  77 leaky::leaky()
  78 {
  79   applicationName = NULL;
  80   logFile = NULL;
  81   progFile = NULL;
  82
  83   dumpLeaks = FALSE;
  84   dumpGraph = FALSE;
  85   dumpHTML = FALSE;
  86   quiet = FALSE;
  87   dumpEntireLog = FALSE;
  88   showAddress = FALSE;
  89   stackDepth = 100000;
  90   dumpRefcnts = false;
  91
  92   mappedLogFile = -1;
  93   firstLogEntry = lastLogEntry = 0;
  94   buckets = DefaultBuckets;
  95   dict = NULL;
  96   refcntDict = NULL;
  97
  98   mallocs = 0;
  99   reallocs = 0;
 100   frees = 0;
 101   totalMalloced = 0;
 102   errors = 0;
 103   totalLeaked = 0;
 104
 105   sfd = -1;
 106   externalSymbols = 0;
 107   usefulSymbols = 0;
 108   numExternalSymbols = 0;
 109   lowestSymbolAddr = 0;
 110   highestSymbolAddr = 0;
 111
 112   loadMap = NULL;
 113 }
 114
 115 leaky::~leaky()
 116 {
 117   delete dict;
 118 }
 119
 120 void leaky::usageError()
 121 {
 122   fprintf(stderr,
 123           "Usage: %s [-aAEdfgqxR] [-e name] [-s depth] [-h hash-buckets] [-r root|-i symbol] prog log\n",
 124           (char*) applicationName);
 125   exit(-1);
 126 }
 127
 128 void leaky::initialize(int argc, char** argv)
 129 {
 130   applicationName = argv[0];
 131   applicationName = strrchr(applicationName, '/');
 132   if (!applicationName) {
 133     applicationName = argv[0];
 134   } else {
 135     applicationName++;
 136   }
 137
 138   int arg;
 139   int errflg = 0;
 140   while ((arg = getopt(argc, argv, "adEe:gh:i:r:Rs:tqx")) != -1) {
 141     switch (arg) {
 142       case '?':
 143         errflg++;
 144         break;
 145       case 'a':
 146         dumpEntireLog = TRUE;
 147         break;
 148       case 'A':
 149         showAddress = TRUE;
 150         break;
 151       case 'd':
 152         dumpLeaks = TRUE;
 153         if (dumpGraph) errflg++;
 154         break;
 155       case 'R':
 156         dumpRefcnts = true;
 157         break;
 158       case 'e':
 159         exclusions.add(optarg);
 160         break;
 161       case 'g':
 162         dumpGraph = TRUE;
 163         if (dumpLeaks) errflg++;
 164         break;
 165       case 'r':
 166         roots.add(optarg);
 167         if (!includes.IsEmpty()) {
 168           errflg++;
 169         }
 170         break;
 171       case 'i':
 172         includes.add(optarg);
 173         if (!roots.IsEmpty()) {
 174           errflg++;
 175         }
 176         break;
 177       case 'h':
 178         buckets = atoi(optarg);
 179         if ((buckets < 0) || (buckets > MaxBuckets)) {
 180           buckets = MaxBuckets;
 181           fprintf(stderr, "%s: buckets is invalid, using %d\n",
 182                   (char*) applicationName,
 183                   buckets);
 184         }
 185         break;
 186       case 's':
 187         stackDepth = atoi(optarg);
 188         if (stackDepth < 2) {
 189           stackDepth = 2;
 190         }
 191         break;
 192       case 'x':
 193         dumpHTML = TRUE;
 194         break;
 195       case 'q':
 196         quiet = TRUE;
 197         break;
 198     }
 199   }
 200   if (errflg || ((argc - optind) < 2)) {
 201     usageError();
 202   }
 203   progFile = argv[optind++];
 204   logFile = argv[optind];
 205
 206   dict = new MallocDict(buckets);
 207   if (dumpRefcnts) {
 208     refcntDict = new MallocDict(buckets);
 209   }
 210 }
 211
 212 static void* mapFile(int fd, u_int flags, off_t* sz)
 213 {
 214   struct stat sb;
 215   if (fstat(fd, &sb) < 0) {
 216     perror("fstat");
 217     exit(-1);
 218   }
 219   void* base = mmap(0, (int)sb.st_size, flags, MAP_PRIVATE, fd, 0);
 220   if (!base) {
 221     perror("mmap");
 222     exit(-1);
 223   }
 224   *sz = sb.st_size;
 225   return base;
 226 }
 227
 228 void leaky::LoadMap()
 229 {
 230   malloc_map_entry mme;
 231   char name[1000];
 232
 233   int fd = ::open("malloc-map", O_RDONLY);
 234   if (fd < 0) {
 235     perror("open: malloc-map");
 236     exit(-1);
 237   }
 238   for (;;) {
 239     int nb = read(fd, &mme, sizeof(mme));
 240     if (nb != sizeof(mme)) break;
 241     nb = read(fd, name, mme.nameLen);
 242     if (nb != (int)mme.nameLen) break;
 243     name[mme.nameLen] = 0;
 244     if (!quiet) {
 245       printf("%s @ %lx\n", name, mme.address);
 246     }
 247
 248     LoadMapEntry* lme = new LoadMapEntry;
 249     lme->address = mme.address;
 250     lme->name = strdup(name);
 251     lme->next = loadMap;
 252     loadMap = lme;
 253   }
 254   close(fd);
 255 }
 256
 257 void leaky::open()
 258 {
 259   LoadMap();
 260
 261   setupSymbols(progFile);
 262
 263   // open up the log file
 264   mappedLogFile = ::open(logFile, O_RDONLY);
 265   if (mappedLogFile < 0) {
 266     perror("open");
 267     exit(-1);
 268   }
 269   off_t size;
 270   firstLogEntry = (malloc_log_entry*) mapFile(mappedLogFile, PROT_READ, &size);
 271   lastLogEntry = (malloc_log_entry*)((char*)firstLogEntry + size);
 272
 273   analyze();
 274
 275   if (dumpLeaks || dumpEntireLog || dumpRefcnts) {
 276     dumpLog();
 277   }
 278   else if (dumpGraph) {
 279     buildLeakGraph();
 280     dumpLeakGraph();
 281   }
 282   exit(0);
 283 }
 284
 285 //----------------------------------------------------------------------
 286
 287
 288 static ptrdiff_t symbolOrder(void const* a, void const* b)
 289 {
 290   Symbol const* ap = (Symbol const *)a;
 291   Symbol const* bp = (Symbol const *)b;
 292   return ap->address - bp->address;
 293 }
 294
 295 void leaky::ReadSharedLibrarySymbols()
 296 {
 297   LoadMapEntry* lme = loadMap;
 298   while (NULL != lme) {
 299     ReadSymbols(lme->name, lme->address);
 300     lme = lme->next;
 301   }
 302 }
 303
 304 void leaky::setupSymbols(const char *fileName)
 305 {
 306   // Read in symbols from the program
 307   ReadSymbols(fileName, 0);
 308
 309   // Read in symbols from the .so's
 310   ReadSharedLibrarySymbols();
 311
 312   if (!quiet) {
 313     printf("A total of %d symbols were loaded\n", usefulSymbols);
 314   }
 315
 316   // Now sort them
 317   qsort(externalSymbols, usefulSymbols, sizeof(Symbol), symbolOrder);
 318   lowestSymbolAddr = externalSymbols[0].address;
 319   highestSymbolAddr = externalSymbols[usefulSymbols-1].address;
 320 }
 321
 322 // Binary search the table, looking for a symbol that covers this
 323 // address.
 324 Symbol* leaky::findSymbol(u_long addr)
 325 {
 326   u_int base = 0;
 327   u_int limit = usefulSymbols - 1;
 328   Symbol* end = &externalSymbols[limit];
 329   while (base <= limit) {
 330     u_int midPoint = (base + limit)>>1;
 331     Symbol* sp = &externalSymbols[midPoint];
 332     if (addr < sp->address) {
 333       if (midPoint == 0) {
 334         return NULL;
 335       }
 336       limit = midPoint - 1;
 337     } else {
 338       if (sp+1 < end) {
 339         if (addr < (sp+1)->address) {
 340           return sp;
 341         }
 342       } else {
 343         return sp;
 344       }
 345       base = midPoint + 1;
 346     }
 347   }
 348   return NULL;
 349 }
 350
 351 //----------------------------------------------------------------------
 352
 353 bool leaky::excluded(malloc_log_entry* lep)
 354 {
 355   if (exclusions.IsEmpty()) {
 356     return false;
 357   }
 358
 359   char** pcp = &lep->pcs[0];
 360   u_int n = lep->numpcs;
 361   for (u_int i = 0; i < n; i++, pcp++) {
 362     Symbol* sp = findSymbol((u_long) *pcp);
 363     if (sp && exclusions.contains(sp->name)) {
 364       return true;
 365     }
 366   }
 367   return false;
 368 }
 369
 370 bool leaky::included(malloc_log_entry* lep)
 371 {
 372   if (includes.IsEmpty()) {
 373     return true;
 374   }
 375
 376   char** pcp = &lep->pcs[0];
 377   u_int n = lep->numpcs;
 378   for (u_int i = 0; i < n; i++, pcp++) {
 379     Symbol* sp = findSymbol((u_long) *pcp);
 380     if (sp && includes.contains(sp->name)) {
 381       return true;
 382     }
 383   }
 384   return false;
 385 }
 386
 387 //----------------------------------------------------------------------
 388
 389 void leaky::displayStackTrace(FILE* out, malloc_log_entry* lep)
 390 {
 391   char** pcp = &lep->pcs[0];
 392   u_int n = (lep->numpcs < stackDepth) ? lep->numpcs : stackDepth;
 393   for (u_int i = 0; i < n; i++, pcp++) {
 394     u_long addr = (u_long) *pcp;
 395     Symbol* sp = findSymbol(addr);
 396     if (sp) {
 397       fputs(sp->name, out);
 398       if (showAddress) {
 399         fprintf(out, "[%p]", (char*)addr);
 400       }
 401     }
 402     else {
 403       fprintf(out, "<%p>", (char*)addr);
 404     }
 405     fputc(' ', out);
 406   }
 407   fputc('\n', out);
 408 }
 409
 410 char* typeFromLog[] = {
 411     "malloc",
 412     "realloc",
 413     "free",
 414     "new",
 415     "delete",
 416     "addref",
 417     "release"
 418 };
 419
 420 void leaky::dumpEntryToLog(malloc_log_entry* lep)
 421 {
 422   printf("%-10s %08lx %5ld ",
 423          typeFromLog[lep->type],
 424          lep->address, lep->size);
 425   if (IsRefcnt(lep)) {
 426     printf("%08ld", lep->oldaddress);
 427   }
 428   else {
 429     printf("%08lx", lep->oldaddress);
 430   }
 431   printf(" --> ");
 432   displayStackTrace(stdout, lep);
 433 }
 434
 435 bool leaky::ShowThisEntry(malloc_log_entry* lep)
 436 {
 437   if ((!dumpRefcnts || IsRefcnt(lep)) && !excluded(lep) && included(lep)) {
 438     return true;
 439   }
 440   return false;
 441 }
 442
 443 void leaky::dumpLog()
 444 {
 445   if (dumpRefcnts) {
 446       malloc_log_entry* lep;
 447       refcntDict->rewind();
 448       while (NULL != (lep = refcntDict->next())) {
 449         if (ShowThisEntry(lep)) {
 450           // Now we get slow...
 451           u_long addr = lep->address;
 452           malloc_log_entry* lep2 = firstLogEntry;
 453           while (lep2 < lastLogEntry) {
 454             if (lep2->address == addr) {
 455               dumpEntryToLog(lep2);
 456             }
 457             lep2 = (malloc_log_entry*) &lep2->pcs[lep2->numpcs];
 458           }
 459         }
 460       }
 461   }
 462   else {
 463     if (dumpEntireLog) {
 464       malloc_log_entry* lep = firstLogEntry;
 465       while (lep < lastLogEntry) {
 466         if (ShowThisEntry(lep)) {
 467           dumpEntryToLog(lep);
 468         }
 469         lep = (malloc_log_entry*) &lep->pcs[lep->numpcs];
 470       }
 471     } else {
 472       malloc_log_entry* lep;
 473       dict->rewind();
 474       while (NULL != (lep = dict->next())) {
 475         if (ShowThisEntry(lep)) {
 476           dumpEntryToLog(lep);
 477         }
 478       }
 479     }
 480   }
 481 }
 482
 483 //----------------------------------------------------------------------
 484
 485 void leaky::insertAddress(u_long address, malloc_log_entry* lep)
 486 {
 487   malloc_log_entry** lepp = dict->find(address);
 488   if (lepp) {
 489     assert(*lepp);
 490     if (!quiet) {
 491       printf("Address %lx allocated twice\n", address);
 492       displayStackTrace(stdout, lep);
 493     }
 494     errors++;
 495   } else {
 496     dict->add(address, lep);
 497   }
 498 }
 499
 500 void leaky::removeAddress(u_long address, malloc_log_entry* lep)
 501 {
 502   malloc_log_entry** lepp = dict->find(address);
 503   if (!lepp) {
 504     if (!quiet) {
 505       printf("Free of unallocated %lx\n", address);
 506       displayStackTrace(stdout, lep);
 507     }
 508     errors++;
 509   } else {
 510     dict->remove(address);
 511   }
 512 }
 513
 514 void leaky::analyze()
 515 {
 516   malloc_log_entry* lep = firstLogEntry;
 517   while (lep < lastLogEntry) {
 518     switch (lep->type) {
 519       case malloc_log_malloc:
 520       case malloc_log_new:
 521         mallocs++;
 522         if (lep->address) {
 523           totalMalloced += lep->size;
 524           insertAddress((u_long) lep->address, lep);
 525         }
 526         break;
 527
 528       case malloc_log_realloc:
 529         if (lep->oldaddress) {
 530           removeAddress((u_long) lep->oldaddress, lep);
 531         }
 532         if (lep->address) {
 533           insertAddress((u_long) lep->address, lep);
 534         }
 535         reallocs++;
 536         break;
 537
 538       case malloc_log_free:
 539       case malloc_log_delete:
 540         if (lep->address) {
 541           removeAddress((u_long) lep->address, lep);
 542         }
 543         frees++;
 544         break;
 545       case malloc_log_addref:
 546         if (dumpRefcnts) {
 547           if (lep->size == 0) {
 548             // Initial addref
 549             u_long addr = (u_long) lep->address;
 550             malloc_log_entry** lepp = refcntDict->find(addr);
 551             if (!lepp) {
 552               refcntDict->add(addr, lep);
 553             }
 554           }
 555         }
 556         break;
 557       case malloc_log_release:
 558         if (dumpRefcnts) {
 559           if (lep->oldaddress == 0) {
 560             // Final release
 561             u_long addr = (u_long) lep->address;
 562             malloc_log_entry** lepp = refcntDict->find(addr);
 563             if (lepp) {
 564               refcntDict->remove(addr);
 565             }
 566           }
 567         }
 568         break;
 569     }
 570     lep = (malloc_log_entry*) &lep->pcs[lep->numpcs];
 571   }
 572
 573   dict->rewind();
 574   while (NULL != (lep = dict->next())) {
 575     totalLeaked += lep->size;
 576   }
 577
 578   if (!quiet) {
 579     printf("# of mallocs = %ld\n", mallocs);
 580     printf("# of reallocs = %ld\n", reallocs);
 581     printf("# of frees = %ld\n", frees);
 582     printf("# of errors = %ld\n", errors);
 583     printf("Total bytes allocated = %ld\n", totalMalloced);
 584     printf("Total bytes leaked = %ld\n", totalLeaked);
 585     printf("Average bytes per malloc = %g\n",
 586            float(totalMalloced)/mallocs);
 587   }
 588 }
 589
 590 void leaky::buildLeakGraph()
 591 {
 592   // For each leak
 593   malloc_log_entry* lep;
 594   dict->rewind();
 595   while (NULL != (lep = dict->next())) {
 596     if (ShowThisEntry(lep)) {
 597       char** basepcp = &lep->pcs[0];
 598       char** pcp = &lep->pcs[lep->numpcs - 1];
 599
 600       // Find root for this allocation
 601       Symbol* sym = findSymbol((u_long) *pcp);
 602       TreeNode* node = sym->root;
 603       if (!node) {
 604         sym->root = node = new TreeNode(sym);
 605
 606         // Add root to list of roots
 607         if (roots.IsEmpty()) {
 608           node->nextRoot = rootList;
 609           rootList = node;
 610         }
 611       }
 612       pcp--;
 613
 614       // Build tree underneath the root
 615       for (; pcp >= basepcp; pcp--) {
 616         // Share nodes in the tree until there is a divergence
 617         sym = findSymbol((u_long) *pcp);
 618         if (!sym) {
 619           break;
 620         }
 621         TreeNode* nextNode = node->GetDirectDescendant(sym);
 622         if (!nextNode) {
 623           // Make a new node at the point of divergence
 624           nextNode = node->AddDescendant(sym);
 625         }
 626
 627         // See if the symbol is to be a user specified root. If it is,
 628         // and we haven't already stuck it on the root-list do so now.
 629         if (!sym->root && !roots.IsEmpty() && roots.contains(sym->name)) {
 630           sym->root = nextNode;
 631           nextNode->nextRoot = rootList;
 632           rootList = nextNode;
 633         }
 634
 635         if (pcp == basepcp) {
 636           nextNode->bytesLeaked += lep->size;
 637         }
 638         else {
 639           node->descendantBytesLeaked += lep->size;
 640         }
 641
 642         node = nextNode;
 643       }
 644     }
 645   }
 646 }
 647
 648 Symbol* leaky::findLeakGraphRoot(Symbol* aStart, Symbol* aEnd)
 649 {
 650   while (aStart < aEnd) {
 651     if (aStart->root) {
 652       return aStart;
 653     }
 654     aStart++;
 655   }
 656   return NULL;
 657 }
 658
 659 void leaky::dumpLeakGraph()
 660 {
 661   if (dumpHTML) {
 662     printf("<html><head><title>Leaky Graph</title>\n");
 663     printf("<style src=\"resource:/res/leaky/leaky.css\"></style>\n");
 664     printf("<script src=\"resource:/res/leaky/leaky.js\"></script>\n");
 665     printf("</head><body><div class=\"key\">\n");
 666     printf("Key:<br>\n");
 667     printf("<span class=b>Bytes directly leaked</span><br>\n");
 668     printf("<span class=d>Bytes leaked by descendants</span></div>\n");
 669   }
 670
 671 #if 0
 672   Symbol* base = externalSymbols;
 673   Symbol* end = externalSymbols + usefulSymbols;
 674   while (base < end) {
 675     Symbol* sym = findLeakGraphRoot(base, end);
 676     if (!sym) break;
 677     dumpLeakTree(sym->root, 0);
 678     base = sym + 1;
 679   }
 680 #else
 681   TreeNode* root = rootList;
 682   while (root) {
 683     dumpLeakTree(root, 0);
 684     root = root->nextRoot;
 685   }
 686 #endif
 687   if (dumpHTML) {
 688     printf("</body></html>\n");
 689   }
 690 }
 691
 692 void leaky::dumpLeakTree(TreeNode* aNode, int aIndent)
 693 {
 694   Symbol* sym = aNode->symbol;
 695   if (dumpHTML) {
 696     printf("<div class=\"n\">\n");
 697     if (aNode->HasDescendants()) {
 698       printf("<img onmouseout=\"O(event);\" onmouseover=\"I(event);\" ");
 699       printf("onclick=\"C(event);\" src=\"resource:/res/leaky/%s.gif\">",
 700              aIndent > 1 ? "close" : "open");
 701     }
 702     printf("<span class=s>%s</span><span class=b>%ld</span>",
 703            sym->name,
 704            aNode->bytesLeaked);
 705     printf("<span class=d>%ld</span>\n",
 706            aNode->descendantBytesLeaked);
 707   }
 708   else {
 709     indentBy(aIndent);
 710     printf("%s bytesLeaked=%ld (%ld from kids)\n",
 711            sym->name,
 712            aNode->bytesLeaked,
 713            aNode->descendantBytesLeaked);
 714   }
 715
 716   TreeNode* node = aNode->descendants;
 717   int kidNum = 0;
 718   while (node) {
 719     sym = node->symbol;
 720     dumpLeakTree(node, aIndent + 1);
 721     kidNum++;
 722     node = node->nextSibling;
 723   }
 724
 725   if (dumpHTML) {
 726     printf("</div>");
 727   }
 728 }
 729
 730 //----------------------------------------------------------------------
 731
 732 TreeNode* TreeNode::freeList;
 733
 734 void* TreeNode::operator new(size_t size) CPP_THROW_NEW
 735 {
 736   if (!freeList) {
 737     TreeNode* newNodes = (TreeNode*) new char[sizeof(TreeNode) * 5000];
 738     if (!newNodes) {
 739       return NULL;
 740     }
 741     TreeNode* n = newNodes;
 742     TreeNode* end = newNodes + 5000 - 1;
 743     while (n < end) {
 744       n->nextSibling = n + 1;
 745       n++;
 746     }
 747     n->nextSibling = NULL;
 748     freeList = newNodes;
 749   }
 750
 751   TreeNode* rv = freeList;
 752   freeList = rv->nextSibling;
 753
 754   return (void*) rv;
 755 }
 756
 757 void TreeNode::operator delete(void* ptr)
 758 {
 759   TreeNode* node = (TreeNode*) ptr;
 760   if (node) {
 761     node->nextSibling = freeList;
 762     freeList = node;
 763   }
 764 }
 765
 766 TreeNode* TreeNode::GetDirectDescendant(Symbol* aSymbol)
 767 {
 768   TreeNode* node = descendants;
 769   while (node) {
 770     if (node->symbol == aSymbol) {
 771       return node;
 772     }
 773     node = node->nextSibling;
 774   }
 775   return NULL;
 776 }
 777
 778 TreeNode* TreeNode::AddDescendant(Symbol* aSymbol)
 779 {
 780   TreeNode* node = new TreeNode(aSymbol);
 781   node->nextSibling = descendants;
 782   descendants = node;
 783   return node;
 784 }