revlist.c

   1 /*
   2  *  Copyright © 2006 Keith Packard <keithp@keithp.com>
   3  *
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 2 of the License, or (at
   7  *  your option) any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful, but
  10  *  WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License along
  15  *  with this program; if not, write to the Free Software Foundation, Inc.,
  16  *  59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
  17  */
  18
  19 #include "cvs.h"
  20
  21 /*
  22  * Add head refs
  23  */
  24
  25 rev_ref *
  26 rev_list_add_head (rev_list *rl, rev_commit *commit, char *name, int degree)
  27 {
  28     rev_ref     *r;
  29     rev_ref     **list = &rl->heads;
  30
  31     while (*list)
  32         list = &(*list)->next;
  33     r = calloc (1, sizeof (rev_ref));
  34     r->commit = commit;
  35     r->name = name;
  36     r->next = *list;
  37     r->degree = degree;
  38     *list = r;
  39     return r;
  40 }
  41
  42 static rev_ref *
  43 rev_find_head (rev_list *rl, char *name)
  44 {
  45     rev_ref     *h;
  46
  47     for (h = rl->heads; h; h = h->next)
  48         if (h->name == name)
  49             return h;
  50     return NULL;
  51 }
  52
  53 /*
  54  * We keep all file lists in a canonical sorted order,
  55  * first by latest date and then by the address of the rev_file object
  56  * (which are always unique)
  57  */
  58
  59 int
  60 rev_file_later (rev_file *af, rev_file *bf)
  61 {
  62     long        t;
  63
  64     /*
  65      * When merging file lists, we should never see the same
  66      * object in both trees
  67      */
  68     assert (af != bf);
  69
  70     t = time_compare (af->date, bf->date);
  71
  72     if (t > 0)
  73         return 1;
  74     if (t < 0)
  75         return 0;
  76     if ((uintptr_t) af > (uintptr_t) bf)
  77         return 1;
  78     return 0;
  79 }
  80
  81 int
  82 rev_commit_later (rev_commit *a, rev_commit *b)
  83 {
  84     long        t;
  85
  86     assert (a != b);
  87     t = time_compare (a->date, b->date);
  88     if (t > 0)
  89         return 1;
  90     if (t < 0)
  91         return 0;
  92     if ((uintptr_t) a > (uintptr_t) b)
  93         return 1;
  94     return 0;
  95 }
  96
  97 /*
  98  * Commits further than 60 minutes apart are assume to be different
  99  */
 100 static int
 101 commit_time_close (time_t a, time_t b)
 102 {
 103     long        diff = a - b;
 104     if (diff < 0) diff = -diff;
 105     if (diff < commit_time_window * 60)
 106         return 1;
 107     return 0;
 108 }
 109
 110 /*
 111  * The heart of the merge operation; detect when two
 112  * commits are "the same"
 113  */
 114 static int
 115 rev_commit_match (rev_commit *a, rev_commit *b)
 116 {
 117     /*
 118      * Very recent versions of CVS place a commitid in
 119      * each commit to track patch sets. Use it if present
 120      */
 121     if (a->commitid && b->commitid)
 122         return a->commitid == b->commitid;
 123     if (a->commitid || b->commitid)
 124         return 0;
 125     if (!commit_time_close (a->date, b->date))
 126         return 0;
 127     if (a->log != b->log)
 128         return 0;
 129     if (a->author != b->author)
 130         return 0;
 131     return 1;
 132 }
 133
 134 #if UNUSED
 135 static void
 136 rev_commit_dump (FILE *f, char *title, rev_commit *c, rev_commit *m)
 137 {
 138     fprintf (f, "\n%s\n", title);
 139     while (c) {
 140         int     i;
 141
 142         fprintf (f, "%c0x%x %s\n", c == m ? '>' : ' ',
 143                 (int) c, ctime_nonl (&c->date));
 144         for (i = 0; i < c->nfiles; i++) {
 145             fprintf (f, "\t%s", ctime_nonl (&c->files[i]->date));
 146             dump_number_file (f, c->files[i]->name, &c->files[i]->number);
 147             fprintf (f, "\n");
 148         }
 149         fprintf (f, "\n");
 150         c = c->parent;
 151     }
 152 }
 153 #endif
 154
 155 void
 156 rev_list_set_tail (rev_list *rl)
 157 {
 158     rev_ref     *head;
 159     rev_commit  *c;
 160     int         tail;
 161
 162     for (head = rl->heads; head; head = head->next) {
 163         tail = 1;
 164         if (head->commit && head->commit->seen) {
 165             head->tail = tail;
 166             tail = 0;
 167         }
 168         for (c = head->commit; c; c = c->parent) {
 169             if (tail && c->parent && c->seen < c->parent->seen) {
 170                 c->tail = 1;
 171                 tail = 0;
 172             }
 173             c->seen++;
 174         }
 175         head->commit->tagged = 1;
 176     }
 177 }
 178
 179 #if 0
 180 static int
 181 rev_ref_len (rev_ref *r)
 182 {
 183     int l = 0;
 184     while (r) {
 185         l++;
 186         r = r->next;
 187     }
 188     return l;
 189 }
 190
 191 static rev_ref *
 192 rev_ref_sel (rev_ref *r, int len)
 193 {
 194     rev_ref     *head, **tail;
 195     rev_ref     *a = r;
 196     rev_ref     *b;
 197     int         alen = len / 2;
 198     int         blen = len - alen;
 199     int         i;
 200
 201     if (len <= 1)
 202         return r;
 203
 204     /*
 205      * split
 206      */
 207     for (i = 0; i < alen - 1; i++)
 208         r = r->next;
 209     b = r->next;
 210     r->next = 0;
 211     /*
 212      * recurse
 213      */
 214     a = rev_ref_sel (a, alen);
 215     b = rev_ref_sel (b, blen);
 216     /*
 217      * merge
 218      */
 219     tail = &head;
 220     while (a && b) {
 221         if (a->degree < b->degree) {
 222             *tail = a;
 223             a = a->next;
 224         } else {
 225             *tail = b;
 226             b = b->next;
 227         }
 228         tail = &(*tail)->next;
 229     }
 230     /*
 231      * paste
 232      */
 233     if (a)
 234         *tail = a;
 235     else
 236         *tail = b;
 237     /*
 238      * done
 239      */
 240     return head;
 241 }
 242
 243 static rev_ref *
 244 rev_ref_sel_sort (rev_ref *r)
 245 {
 246     rev_ref     *s;
 247
 248     r = rev_ref_sel (r, rev_ref_len (r));
 249     for (s = r; s && s->next; s = s->next) {
 250         assert (s->degree <= s->next->degree);
 251     }
 252     return r;
 253 }
 254 #endif
 255
 256 static rev_ref *
 257 rev_ref_find_name (rev_ref *h, char *name)
 258 {
 259     for (; h; h = h->next)
 260         if (h->name == name)
 261             return h;
 262     return NULL;
 263 }
 264
 265 static int
 266 rev_ref_is_ready (char *name, rev_list *source, rev_ref *ready)
 267 {
 268     for (; source; source = source->next) {
 269         rev_ref *head = rev_find_head(source, name);
 270         if (head) {
 271             if (head->parent && !rev_ref_find_name(ready, head->parent->name))
 272                     return 0;
 273         }
 274     }
 275     return 1;
 276 }
 277
 278 static rev_ref *
 279 rev_ref_tsort (rev_ref *refs, rev_list *head)
 280 {
 281     rev_ref *done = NULL;
 282     rev_ref **done_tail = &done;
 283     rev_ref *r, **prev;
 284
 285 //    fprintf (stderr, "Tsort refs:\n");
 286     while (refs) {
 287         for (prev = &refs; (r = *prev); prev = &(*prev)->next) {
 288             if (rev_ref_is_ready (r->name, head, done)) {
 289                 break;
 290             }
 291         }
 292         if (!r) {
 293             fprintf (stderr, "Error: branch cycle\n");
 294             return NULL;
 295         }
 296         *prev = r->next;
 297         *done_tail = r;
 298 //      fprintf (stderr, "\t%s\n", r->name);
 299         r->next = NULL;
 300         done_tail = &r->next;
 301     }
 302     return done;
 303 }
 304
 305 static int
 306 rev_list_count (rev_list *head)
 307 {
 308     int count = 0;
 309     while (head) {
 310         count++;
 311         head = head->next;
 312     }
 313     return count;
 314 }
 315
 316 static int
 317 rev_commit_date_compare (const void *av, const void *bv)
 318 {
 319     const rev_commit    *a = *(const rev_commit **) av;
 320     const rev_commit    *b = *(const rev_commit **) bv;
 321     int                 t;
 322
 323     /*
 324      * NULL entries sort last
 325      */
 326     if (!a && !b)
 327         return 0;
 328     else if (!a)
 329         return 1;
 330     else if (!b)
 331         return -1;
 332 #if 0
 333     /*
 334      * Entries with no files sort next
 335      */
 336     if (a->nfiles != b->nfiles)
 337         return b->nfiles - a->nfiles;
 338 #endif
 339     /*
 340      * tailed entries sort next
 341      */
 342     if (a->tailed != b->tailed)
 343         return a->tailed - b->tailed;
 344     /*
 345      * Newest entries sort first
 346      */
 347     t = -time_compare (a->date, b->date);
 348     if (t)
 349         return t;
 350     /*
 351      * Ensure total order by ordering based on file address
 352      */
 353     if ((uintptr_t) a->file > (uintptr_t) b->file)
 354         return -1;
 355     if ((uintptr_t) a->file < (uintptr_t) b->file)
 356         return 1;
 357     return 0;
 358 }
 359
 360 static int
 361 rev_commit_date_sort (rev_commit **commits, int ncommit)
 362 {
 363     qsort (commits, ncommit, sizeof (rev_commit *),
 364            rev_commit_date_compare);
 365     /*
 366      * Trim off NULL entries
 367      */
 368     while (ncommit && !commits[ncommit-1])
 369         ncommit--;
 370     return ncommit;
 371 }
 372
 373 int
 374 rev_commit_has_file (rev_commit *c, rev_file *f)
 375 {
 376     int i, j;
 377
 378     if (!c)
 379         return 0;
 380     for (i = 0; i < c->ndirs; i++) {
 381         rev_dir *dir = c->dirs[i];
 382         for (j = 0; j < dir->nfiles; j++)
 383             if (dir->files[j] == f)
 384                 return 1;
 385     }
 386     return 0;
 387 }
 388
 389 #if UNUSED
 390 static rev_file *
 391 rev_commit_find_file (rev_commit *c, char *name)
 392 {
 393     int n;
 394
 395     for (n = 0; n < c->nfiles; n++)
 396         if (c->files[n]->name == name)
 397             return c->files[n];
 398     return NULL;
 399 }
 400 #endif
 401
 402 static rev_file **files = NULL;
 403 static int          sfiles = 0;
 404
 405 void
 406 rev_commit_cleanup (void)
 407 {
 408     if (files) {
 409         free (files);
 410         files = NULL;
 411         sfiles = 0;
 412     }
 413 }
 414
 415 static rev_commit *
 416 rev_commit_build (rev_commit **commits, rev_commit *leader, int ncommit)
 417 {
 418     int         n, nfile;
 419     rev_commit  *commit;
 420     int         nds;
 421     rev_dir     **rds;
 422     rev_file    *first;
 423
 424     if (rev_mode == ExecuteGit) {
 425         reset_commits(commits, ncommit);
 426         commit = create_tree(leader);
 427         for (n = 0; n < ncommit; n++) {
 428                 if (commits[n] && commits[n]->file) {
 429                         commit->file = commits[n]->file;
 430                         break;
 431                 }
 432         }
 433         return commit;
 434     }
 435     if (ncommit > sfiles) {
 436         free (files);
 437         files = 0;
 438     }
 439     if (!files)
 440         files = malloc ((sfiles = ncommit) * sizeof (rev_file *));
 441
 442     nfile = 0;
 443     for (n = 0; n < ncommit; n++)
 444         if (commits[n] && commits[n]->file)
 445             files[nfile++] = commits[n]->file;
 446
 447     if (nfile)
 448         first = files[0];
 449     else
 450         first = NULL;
 451
 452     rds = rev_pack_files (files, nfile, &nds);
 453
 454     commit = calloc (1, sizeof (rev_commit) +
 455                      nds * sizeof (rev_dir *));
 456
 457     commit->date = leader->date;
 458     commit->commitid = leader->commitid;
 459     commit->log = leader->log;
 460     commit->author = leader->author;
 461
 462     commit->file = first;
 463     commit->nfiles = nfile;
 464
 465     memcpy (commit->dirs, rds, (commit->ndirs = nds) * sizeof (rev_dir *));
 466
 467     return commit;
 468 }
 469
 470 #if UNUSED
 471 static rev_commit *
 472 rev_ref_find_commit_file (rev_ref *branch, rev_file *file)
 473 {
 474     rev_commit  *c;
 475
 476     for (c = branch->commit; c; c = c->parent)
 477         if (rev_commit_has_file (c, file))
 478             return c;
 479     return NULL;
 480 }
 481
 482 static int
 483 rev_commit_is_ancestor (rev_commit *old, rev_commit *young)
 484 {
 485     while (young) {
 486         if (young == old)
 487             return 1;
 488         young = young->parent;
 489     }
 490     return 0;
 491 }
 492 #endif
 493
 494 static rev_commit *
 495 rev_commit_locate_date (rev_ref *branch, time_t date)
 496 {
 497     rev_commit  *commit;
 498
 499     for (commit = branch->commit; commit; commit = commit->parent)
 500     {
 501         if (time_compare (commit->date, date) <= 0)
 502             return commit;
 503     }
 504     return NULL;
 505 }
 506
 507 static rev_commit *
 508 rev_commit_locate_one (rev_ref *branch, rev_commit *file)
 509 {
 510     rev_commit  *commit;
 511
 512     if (!branch)
 513         return NULL;
 514
 515     for (commit = branch->commit;
 516          commit;
 517          commit = commit->parent)
 518     {
 519         if (rev_commit_match (commit, file))
 520             return commit;
 521     }
 522     return NULL;
 523 }
 524
 525 static rev_commit *
 526 rev_commit_locate_any (rev_ref *branch, rev_commit *file)
 527 {
 528     rev_commit  *commit;
 529
 530     if (!branch)
 531         return NULL;
 532     commit = rev_commit_locate_any (branch->next, file);
 533     if (commit)
 534         return commit;
 535     return rev_commit_locate_one (branch, file);
 536 }
 537
 538 static rev_commit *
 539 rev_commit_locate (rev_ref *branch, rev_commit *file)
 540 {
 541     rev_commit  *commit;
 542
 543     /*
 544      * Check the presumed trunk first
 545      */
 546     commit = rev_commit_locate_one (branch, file);
 547     if (commit)
 548         return commit;
 549     /*
 550      * Now look through all branches
 551      */
 552     while (branch->parent)
 553         branch = branch->parent;
 554     return rev_commit_locate_any (branch, file);
 555 }
 556
 557 rev_ref *
 558 rev_branch_of_commit (rev_list *rl, rev_commit *commit)
 559 {
 560     rev_ref     *h;
 561     rev_commit  *c;
 562
 563     for (h = rl->heads; h; h = h->next)
 564     {
 565         if (h->tail)
 566             continue;
 567         for (c = h->commit; c; c = c->parent) {
 568             if (rev_commit_match (c, commit))
 569                 return h;
 570             if (c->tail)
 571                 break;
 572         }
 573     }
 574     return NULL;
 575 }
 576
 577 /*
 578  * Time of first commit along entire history
 579  */
 580 static time_t
 581 rev_commit_first_date (rev_commit *commit)
 582 {
 583     while (commit->parent)
 584         commit = commit->parent;
 585     return commit->date;
 586 }
 587
 588 /*
 589  * Merge a set of per-file branches into a global branch
 590  */
 591 static void
 592 rev_branch_merge (rev_ref **branches, int nbranch,
 593                   rev_ref *branch, rev_list *rl)
 594 {
 595         int nlive;
 596         int n;
 597         rev_commit *prev = NULL;
 598         rev_commit *head = NULL, **tail = &head;
 599         rev_commit **commits = calloc (nbranch, sizeof (rev_commit *));
 600         rev_commit *commit;
 601         rev_commit *latest;
 602         rev_commit **p;
 603         int lazy = 0;
 604         time_t start = 0;
 605
 606         nlive = 0;
 607         for (n = 0; n < nbranch; n++) {
 608                 rev_commit *c;
 609                 /*
 610                  * Initialize commits to head of each branch
 611                  */
 612                 c = commits[n] = branches[n]->commit;
 613                 /*
 614                 * Compute number of branches with remaining entries
 615                 */
 616                 if (!c)
 617                         continue;
 618                 if (branches[n]->tail) {
 619                         c->tailed = 1;
 620                         continue;
 621                 }
 622                 nlive++;
 623                 while (c && !c->tail) {
 624                         if (!start || time_compare(c->date, start) < 0)
 625                                 start = c->date;
 626                         c = c->parent;
 627                 }
 628                 if (c && (c->file || c->date != c->parent->date)) {
 629                         if (!start || time_compare(c->date, start) < 0)
 630                                 start = c->date;
 631                 }
 632         }
 633
 634         for (n = 0; n < nbranch; n++) {
 635                 rev_commit *c = commits[n];
 636                 if (!c->tailed)
 637                         continue;
 638                 if (!start || time_compare(start, c->date) >= 0)
 639                         continue;
 640                 if (c->file)
 641                         fprintf(stderr,
 642                                 "Warning: %s too late date through branch %s\n",
 643                                         c->file->name, branch->name);
 644                 commits[n] = NULL;
 645         }
 646         /*
 647          * Walk down branches until each one has merged with the
 648          * parent branch
 649          */
 650         while (nlive > 0 && nbranch > 0) {
 651                 for (n = 0, p = commits, latest = NULL; n < nbranch; n++) {
 652                         rev_commit *c = commits[n];
 653                         if (!c)
 654                                 continue;
 655                         *p++ = c;
 656                         if (c->tailed)
 657                                 continue;
 658                         if (!latest || time_compare(latest->date, c->date) < 0)
 659                                 latest = c;
 660                 }
 661                 nbranch = p - commits;
 662
 663                 /*
 664                  * Construct current commit
 665                  */
 666                 if (!lazy) {
 667                         commit = rev_commit_build (commits, latest, nbranch);
 668                         if (rev_mode == ExecuteGit)
 669                                 lazy = 1;
 670                 } else {
 671                         commit = create_tree(latest);
 672                 }
 673
 674                 /*
 675                  * Step each branch
 676                  */
 677                 nlive = 0;
 678                 for (n = 0; n < nbranch; n++) {
 679                         rev_commit *c = commits[n];
 680                         rev_commit *to;
 681                         /* already got to parent branch? */
 682                         if (c->tailed)
 683                                 continue;
 684                         /* not affected? */
 685                         if (c != latest && !rev_commit_match(c, latest)) {
 686                                 if (c->parent || c->file)
 687                                         nlive++;
 688                                 continue;
 689                         }
 690                         to = c->parent;
 691                         /* starts here? */
 692                         if (!to)
 693                                 goto Kill;
 694
 695                         if (c->tail) {
 696                                 /*
 697                                  * Adding file independently added on another
 698                                  * non-trunk branch.
 699                                  */
 700                                 if (!to->parent && !to->file)
 701                                         goto Kill;
 702                                 /*
 703                                  * If the parent is at the beginning of trunk
 704                                  * and it is younger than some events on our
 705                                  * branch, we have old CVS adding file
 706                                  * independently
 707                                  * added on another branch.
 708                                  */
 709                                 if (start && time_compare(start, to->date) < 0)
 710                                         goto Kill;
 711                                 /*
 712                                  * XXX: we still can't be sure that it's
 713                                  * not a file added on trunk after parent
 714                                  * branch had forked off it but before
 715                                  * our branch's creation.
 716                                  */
 717                                 to->tailed = 1;
 718                         } else if (to->file) {
 719                                 nlive++;
 720                         } else {
 721                                 /*
 722                                  * See if it's recent CVS adding a file
 723                                  * independently added on another branch.
 724                                  */
 725                                 if (!to->parent)
 726                                         goto Kill;
 727                                 if (to->tail && to->date == to->parent->date)
 728                                         goto Kill;
 729                                 nlive++;
 730                         }
 731                         if (to->file)
 732                                 set_commit(to);
 733                         else
 734                                 delete_commit(c);
 735                         commits[n] = to;
 736                         continue;
 737 Kill:
 738                         delete_commit(c);
 739                         commits[n] = NULL;
 740                 }
 741
 742                 *tail = commit;
 743                 tail = &commit->parent;
 744                 prev = commit;
 745         }
 746     /*
 747      * Connect to parent branch
 748      */
 749     nbranch = rev_commit_date_sort (commits, nbranch);
 750     if (nbranch && branch->parent )
 751     {
 752         rev_ref *lost;
 753         int     present;
 754
 755 //      present = 0;
 756         for (present = 0; present < nbranch; present++)
 757             if (commits[present]->file) {
 758                 /*
 759                  * Skip files which appear in the repository after
 760                  * the first commit along the branch
 761                  */
 762                 if (prev && commits[present]->date > prev->date &&
 763                     commits[present]->date == rev_commit_first_date (commits[present]))
 764                 {
 765                     fprintf (stderr, "Warning: file %s appears after branch %s date\n",
 766                              commits[present]->file->name, branch->name);
 767                     continue;
 768                 }
 769                 break;
 770             }
 771         if (present == nbranch)
 772             *tail = NULL;
 773         else if ((*tail = rev_commit_locate_one (branch->parent,
 774                                                  commits[present])))
 775         {
 776             if (prev && time_compare ((*tail)->date, prev->date) > 0) {
 777                 fprintf (stderr, "Warning: branch point %s -> %s later than branch\n",
 778                          branch->name, branch->parent->name);
 779                 fprintf (stderr, "\ttrunk(%3d):  %s %s", n,
 780                          ctime_nonl (&commits[present]->date),
 781                          commits[present]->file ? " " : "D" );
 782                 if (commits[present]->file)
 783                     dump_number_file (stderr,
 784                                       commits[present]->file->name,
 785                                       &commits[present]->file->number);
 786                 fprintf (stderr, "\n");
 787                 fprintf (stderr, "\tbranch(%3d): %s  ", n,
 788                          ctime_nonl (&prev->file->date));
 789                 dump_number_file (stderr,
 790                                   prev->file->name,
 791                                   &prev->file->number);
 792                 fprintf (stderr, "\n");
 793             }
 794         } else if ((*tail = rev_commit_locate_date (branch->parent,
 795                                                   commits[present]->date)))
 796             fprintf (stderr, "Warning: branch point %s -> %s matched by date\n",
 797                      branch->name, branch->parent->name);
 798         else {
 799             fprintf (stderr, "Error: branch point %s -> %s not found.",
 800                      branch->name, branch->parent->name);
 801
 802             if ((lost = rev_branch_of_commit (rl, commits[present])))
 803                 fprintf (stderr, " Possible match on %s.", lost->name);
 804             fprintf (stderr, "\n");
 805         }
 806         if (*tail) {
 807             if (prev)
 808                 prev->tail = 1;
 809         } else
 810             *tail = rev_commit_build (commits, commits[0], nbranch);
 811     }
 812     for (n = 0; n < nbranch; n++)
 813         if (commits[n])
 814             commits[n]->tailed = 0;
 815     free (commits);
 816     branch->commit = head;
 817 }
 818
 819 /*
 820  * Locate position in tree cooresponding to specific tag
 821  */
 822 static void
 823 rev_tag_search(Tag *tag, rev_commit **commits, rev_list *rl)
 824 {
 825         rev_commit_date_sort(commits, tag->count);
 826         tag->parent = rev_branch_of_commit(rl, commits[0]);
 827         if (tag->parent)
 828                 tag->commit = rev_commit_locate (tag->parent, commits[0]);
 829         if (!tag->commit) {
 830                 fprintf (stderr, "unmatched tag %s\n", tag->name);
 831                 /* AV: shouldn't we put it on some branch? */
 832                 tag->commit = rev_commit_build(commits, commits[0], tag->count);
 833         }
 834         tag->commit->tagged = 1;
 835 }
 836
 837 static void
 838 rev_ref_set_parent (rev_list *rl, rev_ref *dest, rev_list *source)
 839 {
 840     rev_ref     *sh;
 841     rev_list    *s;
 842     rev_ref     *p;
 843     rev_ref     *max;
 844
 845     if (dest->depth)
 846         return;
 847
 848     max = NULL;
 849     for (s = source; s; s = s->next) {
 850         sh = rev_find_head (s, dest->name);
 851         if (!sh)
 852             continue;
 853         if (!sh->parent)
 854             continue;
 855         p = rev_find_head (rl, sh->parent->name);
 856         assert (p);
 857         rev_ref_set_parent (rl, p, source);
 858         if (!max || p->depth > max->depth)
 859             max = p;
 860     }
 861     dest->parent = max;
 862     if (max)
 863         dest->depth = max->depth + 1;
 864     else
 865         dest->depth = 1;
 866 }
 867
 868
 869 #if UNUSED
 870 static void
 871 rev_head_find_parent (rev_list *rl, rev_ref *h, rev_list *lhead)
 872 {
 873     rev_list    *l;
 874     rev_ref     *lh;
 875
 876     for (l = lhead; l; l = l->next) {
 877         lh = rev_find_head (l, h->name);
 878         if (!lh)
 879             continue;
 880
 881     }
 882 }
 883 #endif
 884
 885 #if UNUSED
 886 static int
 887 rev_branch_name_is_ancestor (rev_ref *old, rev_ref *young)
 888 {
 889     while (young) {
 890         if (young->name == old->name)
 891             return 1;
 892         young = young->parent;
 893     }
 894     return 0;
 895 }
 896 #endif
 897
 898 #if UNUSED
 899 static rev_ref *
 900 rev_ref_parent (rev_ref **refs, int nref, rev_list *rl)
 901 {
 902     rev_ref     *parent = NULL;
 903     rev_ref     *branch = NULL;
 904     int         n;
 905     rev_ref     *h;
 906
 907     for (n = 0; n < nref; n++)
 908     {
 909         if (refs[n]->parent) {
 910             if (!parent) {
 911                 parent = refs[n]->parent;
 912                 branch = refs[n];
 913             } else if (parent->name != refs[n]->parent->name) {
 914                 if (rev_branch_name_is_ancestor (refs[n]->parent, parent))
 915                     ;
 916                 else if (rev_branch_name_is_ancestor (parent, refs[n]->parent)) {
 917                     parent = refs[n]->parent;
 918                     branch = refs[n];
 919                 } else {
 920                     fprintf (stderr, "Branch name collision:\n");
 921                     fprintf (stderr, "\tfirst branch: ");
 922                     dump_ref_name (stderr, branch);
 923                     fprintf (stderr, "\n");
 924                     fprintf (stderr, "\tsecond branch: ");
 925                     dump_ref_name (stderr, refs[n]);
 926                     fprintf (stderr, "\n");
 927                 }
 928             }
 929         }
 930     }
 931     if (!parent)
 932         return NULL;
 933     for (h = rl->heads; h; h = h->next)
 934         if (parent->name == h->name)
 935             return h;
 936     fprintf (stderr, "Reference missing in merge: %s\n", parent->name);
 937     return NULL;
 938 }
 939 #endif
 940
 941 rev_list *
 942 rev_list_merge (rev_list *head)
 943 {
 944     int         count = rev_list_count (head);
 945     rev_list    *rl = calloc (1, sizeof (rev_list));
 946     rev_list    *l;
 947     rev_ref     *lh, *h;
 948     Tag         *t;
 949     rev_ref     **refs = calloc (count, sizeof (rev_ref *));
 950     int         nref;
 951
 952     /*
 953      * Find all of the heads across all of the incoming trees
 954      * Yes, this is currently very inefficient
 955      */
 956     for (l = head; l; l = l->next) {
 957         for (lh = l->heads; lh; lh = lh->next) {
 958             h = rev_find_head (rl, lh->name);
 959             if (!h)
 960                 rev_list_add_head (rl, NULL, lh->name, lh->degree);
 961             else if (lh->degree > h->degree)
 962                 h->degree = lh->degree;
 963         }
 964     }
 965     /*
 966      * Sort by degree so that finding branch points always works
 967      */
 968 //    rl->heads = rev_ref_sel_sort (rl->heads);
 969     rl->heads = rev_ref_tsort (rl->heads, head);
 970     if (!rl->heads)
 971         return NULL;
 972 //    for (h = rl->heads; h; h = h->next)
 973 //      fprintf (stderr, "head %s (%d)\n",
 974 //               h->name, h->degree);
 975     /*
 976      * Find branch parent relationships
 977      */
 978     for (h = rl->heads; h; h = h->next) {
 979         rev_ref_set_parent (rl, h, head);
 980 //      dump_ref_name (stderr, h);
 981 //      fprintf (stderr, "\n");
 982     }
 983     /*
 984      * Merge common branches
 985      */
 986     for (h = rl->heads; h; h = h->next) {
 987         /*
 988          * Locate branch in every tree
 989          */
 990         nref = 0;
 991         for (l = head; l; l = l->next) {
 992             lh = rev_find_head (l, h->name);
 993             if (lh)
 994                 refs[nref++] = lh;
 995         }
 996         if (nref)
 997             rev_branch_merge (refs, nref, h, rl);
 998     }
 999     /*
1000      * Compute 'tail' values
1001      */
1002     rev_list_set_tail (rl);
1003
1004     free(refs);
1005     /*
1006      * Find tag locations
1007      */
1008     for (t = all_tags; t; t = t->next) {
1009         rev_commit **commits = tagged(t);
1010         if (commits)
1011             rev_tag_search(t, commits, rl);
1012         else
1013             fprintf (stderr, "lost tag %s\n", t->name);
1014         free(commits);
1015     }
1016     rev_list_validate (rl);
1017     return rl;
1018 }
1019
1020 /*
1021  * Icky. each file revision may be referenced many times in a single
1022  * tree. When freeing the tree, queue the file objects to be deleted
1023  * and clean them up afterwards
1024  */
1025
1026 static rev_file *rev_files;
1027
1028 static void
1029 rev_file_mark_for_free (rev_file *f)
1030 {
1031     if (f->name) {
1032         f->name = NULL;
1033         f->link = rev_files;
1034         rev_files = f;
1035     }
1036 }
1037
1038 static void
1039 rev_file_free_marked (void)
1040 {
1041     rev_file    *f, *n;
1042
1043     for (f = rev_files; f; f = n)
1044     {
1045         n = f->link;
1046         free (f);
1047     }
1048     rev_files = NULL;
1049 }
1050
1051 rev_file *
1052 rev_file_rev (char *name, cvs_number *n, time_t date)
1053 {
1054     rev_file    *f = calloc (1, sizeof (rev_file));
1055
1056     f->name = name;
1057     f->number = *n;
1058     f->date = date;
1059     return f;
1060 }
1061
1062 void
1063 rev_file_free (rev_file *f)
1064 {
1065     free (f);
1066 }
1067
1068 static void
1069 rev_commit_free (rev_commit *commit, int free_files)
1070 {
1071     rev_commit  *c;
1072
1073     while ((c = commit)) {
1074         commit = c->parent;
1075         if (--c->seen == 0)
1076         {
1077             if (free_files && c->file)
1078                 rev_file_mark_for_free (c->file);
1079             free (c);
1080         }
1081     }
1082 }
1083
1084 void
1085 rev_head_free (rev_ref *head, int free_files)
1086 {
1087     rev_ref     *h;
1088
1089     while ((h = head)) {
1090         head = h->next;
1091         rev_commit_free (h->commit, free_files);
1092         free (h);
1093     }
1094 }
1095
1096 void
1097 rev_list_free (rev_list *rl, int free_files)
1098 {
1099     rev_head_free (rl->heads, free_files);
1100     if (free_files)
1101         rev_file_free_marked ();
1102     free (rl);
1103 }
1104
1105 void
1106 rev_list_validate (rev_list *rl)
1107 {
1108     rev_ref     *h;
1109     rev_commit  *c;
1110     for (h = rl->heads; h; h = h->next) {
1111         if (h->tail)
1112             continue;
1113         for (c = h->commit; c && c->parent; c = c->parent) {
1114             if (c->tail)
1115                 break;
1116 //          assert (time_compare (c->date, c->parent->date) >= 0);
1117         }
1118     }
1119 }
1120
1121 /*
1122  * Generate a list of files in uniq that aren't in common
1123  */
1124
1125 static rev_file_list *
1126 rev_uniq_file (rev_commit *uniq, rev_commit *common, int *nuniqp)
1127 {
1128     int i, j;
1129     int nuniq = 0;
1130     rev_file_list   *head = NULL, **tail = &head, *fl;
1131
1132     if (!uniq)
1133         return NULL;
1134     for (i = 0; i < uniq->ndirs; i++) {
1135         rev_dir *dir = uniq->dirs[i];
1136         for (j = 0; j < dir->nfiles; j++)
1137             if (!rev_commit_has_file (common, dir->files[j])) {
1138                 fl = calloc (1, sizeof (rev_file_list));
1139                 fl->file = dir->files[j];
1140                 *tail = fl;
1141                 tail = &fl->next;
1142                 ++nuniq;
1143             }
1144     }
1145     *nuniqp = nuniq;
1146     return head;
1147 }
1148
1149 int
1150 rev_file_list_has_filename (rev_file_list *fl, char *name)
1151 {
1152     for (; fl; fl = fl->next)
1153         if (fl->file->name == name)
1154             return 1;
1155     return 0;
1156 }
1157
1158 /*
1159  * Generate a diff between two commits. Either may be NULL
1160  */
1161
1162 rev_diff *
1163 rev_commit_diff (rev_commit *old, rev_commit *new)
1164 {
1165     rev_diff    *diff = calloc (1, sizeof (rev_diff));
1166
1167     diff->del = rev_uniq_file (old, new, &diff->ndel);
1168     diff->add = rev_uniq_file (new, old, &diff->nadd);
1169     return diff;
1170 }
1171
1172 static void
1173 rev_file_list_free (rev_file_list *fl)
1174 {
1175     rev_file_list   *next;
1176
1177     while (fl) {
1178         next = fl->next;
1179         free (fl);
1180         fl = next;
1181     }
1182 }
1183
1184 void
1185 rev_diff_free (rev_diff *d)
1186 {
1187     rev_file_list_free (d->del);
1188     rev_file_list_free (d->add);
1189     free (d);
1190 }
1191