revcvs.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 #define DEBUG 0
  22
  23 /*
  24  * Given a single-file tree, locate the specific version number
  25  */
  26
  27 static rev_commit *
  28 rev_find_cvs_commit (rev_list *rl, cvs_number *number)
  29 {
  30     rev_ref     *h;
  31     rev_commit  *c;
  32     rev_file    *f;
  33
  34     for (h = rl->heads; h; h = h->next) {
  35         if (h->tail)
  36             continue;
  37         for (c = h->commit; c; c = c->parent)
  38         {
  39              f = c->file;
  40              if (cvs_number_compare (&f->number, number) == 0)
  41                     return c;
  42              if (c->tail)
  43                  break;
  44         }
  45     }
  46     return NULL;
  47 }
  48
  49 /*
  50  * Construct a branch using CVS revision numbers
  51  */
  52 static rev_commit *
  53 rev_branch_cvs (cvs_file *cvs, cvs_number *branch)
  54 {
  55     cvs_number  n;
  56     rev_commit  *head = NULL;
  57     rev_commit  *c, *p;
  58     Node        *node;
  59
  60     n = *branch;
  61     n.n[n.c-1] = -1;
  62     for (node = cvs_find_version (cvs, &n); node; node = node->next) {
  63         cvs_version *v = node->v;
  64         cvs_patch *p = node->p;
  65         rev_commit *c;
  66         if (!v)
  67              continue;
  68         c = calloc (1, sizeof (rev_commit));
  69         c->date = v->date;
  70         c->commitid = v->commitid;
  71         c->author = v->author;
  72         if (p)
  73             c->log = p->log;
  74         if (v->dead)
  75             c->nfiles = 0;
  76         else
  77             c->nfiles = 1;
  78         /* leave this around so the branch merging stuff can find numbers */
  79         c->file = rev_file_rev (cvs->name, &v->number, v->date);
  80         if (!v->dead) {
  81             node->file = c->file;
  82             c->file->mode = cvs->mode;
  83         }
  84         c->parent = head;
  85         head = c;
  86     }
  87     /*
  88      * Make sure the dates along the branch are well ordered. As we
  89      * want to preserve current data, push previous versions back to
  90      * align with newer revisions.
  91      */
  92     for (c = head; (p = c->parent); c = p) {
  93         if (time_compare (p->file->date, c->file->date) > 0)
  94         {
  95             fprintf (stderr, "Warning: %s:", cvs->name);
  96             dump_number_file (stderr, " ", &p->file->number);
  97             dump_number_file (stderr, " is newer than", &c->file->number);
  98             fprintf (stderr, ", adjusting\n");
  99             p->file->date = c->file->date;
 100         }
 101     }
 102     return head;
 103 }
 104
 105 /*
 106  * "Vendor branches" (1.1.x) are created by importing sources from
 107  * an external source. In X.org, this was from XFree86 and DRI. When
 108  * these trees are imported, cvs sets the 'default' branch in each ,v file
 109  * to point along this branch. This means that tags made between
 110  * the time the vendor branch is imported and when a new revision
 111  * is committed to the head branch are placed on the vendor branch
 112  * In addition, any files without such a commit appear to adopt
 113  * the vendor branch as 'head'. We fix this by merging these two
 114  * branches together as if they were the same
 115  */
 116 static void
 117 rev_list_patch_vendor_branch (rev_list *rl, cvs_file *cvs)
 118 {
 119     rev_ref     *trunk = NULL;
 120     rev_ref     *vendor = NULL, **vendor_p = NULL;
 121     rev_ref     *h;
 122     rev_commit  *t, **tp, *v, **vp;
 123     rev_commit  *vlast;
 124     rev_commit  *tc;
 125     rev_ref     **h_p;
 126     int         delete_head;
 127
 128     trunk = rl->heads;
 129     for (h_p = &rl->heads; (h = *h_p);) {
 130         delete_head = 0;
 131         if (h->commit && cvs_is_vendor (&h->commit->file->number))
 132         {
 133             /*
 134              * Find version 1.2 on the trunk.
 135              * This will reset the default branch set
 136              * when the initial import was done.
 137              * Subsequent imports will *not* set the default
 138              * branch, and should be on their own branch
 139              */
 140             vendor = h;
 141             vendor_p = h_p;
 142             t = trunk->commit;
 143             v = vendor->commit;
 144             for (vlast = vendor->commit; vlast; vlast = vlast->parent)
 145                 if (!vlast->parent)
 146                     break;
 147             tc = NULL;
 148             tp = &trunk->commit;
 149             /*
 150              * Find the latest trunk revision older than
 151              * the entire vendor branch
 152              */
 153             while ((t = *tp))
 154             {
 155                 if (!t->parent ||
 156                     time_compare (vlast->file->date,
 157                                   t->parent->file->date) >= 0)
 158                 {
 159                     break;
 160                 }
 161                 tp = &t->parent;
 162             }
 163             if (t)
 164             {
 165                 /*
 166                  * If the first commit is older than the last element
 167                  * of the vendor branch, paste them together and
 168                  * nuke the vendor branch
 169                  */
 170                 if (time_compare (vlast->file->date,
 171                                   t->file->date) >= 0)
 172                 {
 173                     delete_head = 1;
 174                 }
 175                 else
 176                 {
 177                     /*
 178                      * Splice out any portion of the vendor branch
 179                      * newer than a the next trunk commit after
 180                      * the oldest branch commit.
 181                      */
 182                     for (vp = &vendor->commit; (v = *vp); vp = &v->parent)
 183                         if (time_compare (v->date, t->date) <= 0)
 184                             break;
 185                     if (vp == &vendor->commit)
 186                     {
 187                         /*
 188                          * Nothing newer, nuke vendor branch
 189                          */
 190                         delete_head = 1;
 191                     }
 192                     else
 193                     {
 194                         /*
 195                          * Some newer stuff, patch parent
 196                          */
 197                         *vp = NULL;
 198                     }
 199                 }
 200             }
 201             else
 202                 delete_head = 1;
 203             /*
 204              * Patch up the remaining vendor branch pieces
 205              */
 206             if (!delete_head) {
 207                 rev_commit  *vr;
 208                 if (!vendor->name) {
 209                     char        rev[CVS_MAX_REV_LEN];
 210                     char        name[MAXPATHLEN];
 211                     cvs_number  branch;
 212
 213                     branch = vlast->file->number;
 214                     branch.c--;
 215                     cvs_number_string (&branch, rev);
 216                     snprintf (name, sizeof (name),
 217                               "import-%s", rev);
 218                     vendor->name = atom (name);
 219                     vendor->parent = trunk;
 220                     vendor->degree = vlast->file->number.c;
 221                 }
 222                 for (vr = vendor->commit; vr; vr = vr->parent)
 223                 {
 224                     if (!vr->parent) {
 225                         vr->tail = 1;
 226                         vr->parent = v;
 227                         break;
 228                     }
 229                 }
 230             }
 231
 232             /*
 233              * Merge two branches based on dates
 234              */
 235             while (t && v)
 236             {
 237                 if (time_compare (v->file->date,
 238                                   t->file->date) >= 0)
 239                 {
 240                     *tp = v;
 241                     tp = &v->parent;
 242                     v = v->parent;
 243                 }
 244                 else
 245                 {
 246                     *tp = t;
 247                     tp = &t->parent;
 248                     t = t->parent;
 249                 }
 250             }
 251             if (t)
 252                 *tp = t;
 253             else
 254                 *tp = v;
 255         }
 256         if (delete_head) {
 257             *h_p = h->next;
 258             free (h);
 259         } else {
 260             h_p = &(h->next);
 261         }
 262     }
 263 #if DEBUG
 264     fprintf (stderr, "%s spliced:\n", cvs->name);
 265     for (t = trunk->commit; t; t = t->parent) {
 266         dump_number_file (stderr, "\t", &t->file->number);
 267         fprintf (stderr, "\n");
 268     }
 269 #endif
 270 }
 271
 272 /*
 273  * Given a disconnected set of branches, graft the bottom
 274  * of each branch where it belongs on the parent branch
 275  */
 276
 277 static void
 278 rev_list_graft_branches (rev_list *rl, cvs_file *cvs)
 279 {
 280     rev_ref     *h;
 281     rev_commit  *c;
 282     cvs_version *cv;
 283     cvs_branch  *cb;
 284
 285     /*
 286      * Glue branches together
 287      */
 288     for (h = rl->heads; h; h = h->next) {
 289         /*
 290          * skip master branch; it "can't" join
 291          * any other branches and it may well end with a vendor
 292          * branch revision of the file, which will then create
 293          * a loop back to the recorded branch point
 294          */
 295         if (h == rl->heads)
 296             continue;
 297         if (h->tail)
 298             continue;
 299         /*
 300          * Find last commit on branch
 301          */
 302         for (c = h->commit; c && c->parent; c = c->parent)
 303             if (c->tail) {
 304                 c = NULL;       /* already been done, skip */
 305                 break;
 306             }
 307         if (c) {
 308             /*
 309              * Walk the version tree, looking for the branch location.
 310              * Note that in the presense of vendor branches, the
 311              * branch location may actually be out on that vendor branch
 312              */
 313             for (cv = cvs->versions; cv; cv = cv->next) {
 314                 for (cb = cv->branches; cb; cb = cb->next) {
 315                     if (cvs_number_compare (&cb->number,
 316                                             &c->file->number) == 0)
 317                     {
 318                         c->parent = rev_find_cvs_commit (rl, &cv->number);
 319                         c->tail = 1;
 320                         break;
 321                     }
 322                 }
 323                 if (c->parent)
 324                 {
 325 #if 0
 326                     /*
 327                      * check for a parallel vendor branch
 328                      */
 329                     for (cb = cv->branches; cb; cb = cb->next) {
 330                         if (cvs_is_vendor (&cb->number)) {
 331                             cvs_number  v_n;
 332                             rev_commit  *v_c, *n_v_c;
 333                             fprintf (stderr, "Found merge into vendor branch\n");
 334                             v_n = cb->number;
 335                             v_c = NULL;
 336                             /*
 337                              * Walk to head of vendor branch
 338                              */
 339                             while ((n_v_c = rev_find_cvs_commit (rl, &v_n)))
 340                             {
 341                                 /*
 342                                  * Stop if we reach a date after the
 343                                  * branch version date
 344                                  */
 345                                 if (time_compare (n_v_c->date, c->date) > 0)
 346                                     break;
 347                                 v_c = n_v_c;
 348                                 v_n.n[v_n.c - 1]++;
 349                             }
 350                             if (v_c)
 351                             {
 352                                 fprintf (stderr, "%s: rewrite branch", cvs->name);
 353                                 dump_number_file (stderr, " branch point",
 354                                                   &v_c->file->number);
 355                                 dump_number_file (stderr, " branch version",
 356                                                   &c->file->number);
 357                                 fprintf (stderr, "\n");
 358                                 c->parent = v_c;
 359                             }
 360                         }
 361                     }
 362 #endif
 363                     break;
 364                 }
 365             }
 366         }
 367     }
 368 }
 369
 370 /*
 371  * For each symbol, locate the appropriate commit
 372  */
 373
 374 static rev_ref *
 375 rev_list_find_branch (rev_list *rl, cvs_number *number)
 376 {
 377     cvs_number  n;
 378     rev_ref     *h;
 379
 380     if (number->c < 2)
 381         return NULL;
 382     n = *number;
 383     h = NULL;
 384     while (n.c >= 2)
 385     {
 386         for (h = rl->heads; h; h = h->next) {
 387             if (cvs_same_branch (&h->number, &n)) {
 388                 break;
 389             }
 390         }
 391         if (h)
 392             break;
 393         n.c -= 2;
 394     }
 395     return h;
 396 }
 397
 398 static void
 399 rev_list_set_refs (rev_list *rl, cvs_file *cvs)
 400 {
 401     rev_ref     *h;
 402     cvs_symbol  *s;
 403     rev_commit  *c;
 404
 405     /*
 406      * Locate a symbolic name for this head
 407      */
 408     for (s = cvs->symbols; s; s = s->next) {
 409         c = NULL;
 410         if (cvs_is_head (&s->number)) {
 411             for (h = rl->heads; h; h = h->next) {
 412                 if (cvs_same_branch (&h->commit->file->number, &s->number))
 413                     break;
 414             }
 415             if (h) {
 416                 if (!h->name) {
 417                     h->name = s->name;
 418                     h->degree = cvs_number_degree (&s->number);
 419                 } else
 420                     h = rev_list_add_head (rl, h->commit, s->name,
 421                                            cvs_number_degree (&s->number));
 422             } else {
 423                 cvs_number      n;
 424
 425                 n = s->number;
 426                 while (n.c >= 4) {
 427                     n.c -= 2;
 428                     c = rev_find_cvs_commit (rl, &n);
 429                     if (c)
 430                         break;
 431                 }
 432                 if (c)
 433                     h = rev_list_add_head (rl, c, s->name,
 434                                            cvs_number_degree (&s->number));
 435             }
 436             if (h)
 437                 h->number = s->number;
 438         } else {
 439             c = rev_find_cvs_commit (rl, &s->number);
 440             if (c)
 441                 tag_commit(c, s->name);
 442         }
 443     }
 444     /*
 445      * Fix up unnamed heads
 446      */
 447     for (h = rl->heads; h; h = h->next) {
 448         cvs_number      n;
 449         rev_commit      *c;
 450
 451         if (h->name)
 452             continue;
 453         for (c = h->commit; c; c = c->parent) {
 454             if (c->nfiles)
 455                 break;
 456         }
 457         if (!c)
 458             continue;
 459         n = c->file->number;
 460         /* convert to branch form */
 461         n.n[n.c-1] = n.n[n.c-2];
 462         n.n[n.c-2] = 0;
 463         h->number = n;
 464         h->degree = cvs_number_degree (&n);
 465         /* compute name after patching parents */
 466     }
 467     /*
 468      * Link heads together in a tree
 469      */
 470     for (h = rl->heads; h; h = h->next) {
 471         cvs_number      n;
 472
 473         if (h->number.c >= 4) {
 474             n = h->number;
 475             n.c -= 2;
 476             h->parent = rev_list_find_branch (rl, &n);
 477             if (!h->parent && ! cvs_is_vendor (&h->number))
 478                 fprintf (stderr, "Warning: %s: branch %s has no parent\n",
 479                          cvs->name, h->name);
 480         }
 481         if (h->parent && !h->name) {
 482             char        name[1024];
 483             char        rev[CVS_MAX_REV_LEN];
 484
 485             cvs_number_string (&h->number, rev);
 486             fprintf (stderr, "Warning: %s: unnamed branch %s from %s\n",
 487                      cvs->name, rev, h->parent->name);
 488             sprintf (name, "%s-UNNAMED-BRANCH", h->parent->name);
 489             h->name = atom (name);
 490         }
 491     }
 492 }
 493
 494 /*
 495  * Dead file revisions get an extra rev_file object which may be
 496  * needed during branch merging. Clean those up before returning
 497  * the resulting rev_list
 498  */
 499
 500 static void
 501 rev_list_free_dead_files (rev_list *rl)
 502 {
 503     rev_ref     *h;
 504     rev_commit  *c;
 505
 506     for (h = rl->heads; h; h = h->next) {
 507         if (h->tail)
 508             continue;
 509         for (c = h->commit; c; c = c->parent) {
 510             if (c->nfiles == 0) {
 511                 rev_file_free (c->file);
 512                 c->file = 0;
 513             }
 514             if (c->tail)
 515                 break;
 516         }
 517     }
 518 }
 519
 520 #if UNUSED
 521 static int
 522 rev_order_compare (cvs_number *a, cvs_number *b)
 523 {
 524     if (a->c != b->c)
 525         return a->c - b->c;
 526     return cvs_number_compare (b, a);
 527 }
 528 #endif
 529
 530 static cvs_symbol *
 531 cvs_find_symbol (cvs_file *cvs, char *name)
 532 {
 533     cvs_symbol  *s;
 534
 535     for (s = cvs->symbols; s; s = s->next)
 536         if (s->name == name)
 537             return s;
 538     return NULL;
 539 }
 540
 541 static int
 542 cvs_symbol_compare (cvs_symbol *a, cvs_symbol *b)
 543 {
 544     if (!a) {
 545         if (!b) return 0;
 546         return -1;
 547     }
 548     if (!b)
 549         return 1;
 550     return cvs_number_compare (&a->number, &b->number);
 551 }
 552
 553 static void
 554 rev_list_dump_ref_parents (FILE *f, rev_ref *h)
 555 {
 556     if (h) {
 557         rev_list_dump_ref_parents (f, h->parent);
 558         fprintf (f, "%s > ", h->name);
 559     }
 560 }
 561
 562 static void
 563 rev_list_sort_heads (rev_list *rl, cvs_file *cvs)
 564 {
 565     rev_ref     *h, **hp;
 566     cvs_symbol  *hs, *hns;
 567
 568     for (hp = &rl->heads; (h = *hp);) {
 569         if (!h->next)
 570             break;
 571         hs = cvs_find_symbol (cvs, h->name);
 572         hns = cvs_find_symbol (cvs, h->next->name);
 573         if (cvs_symbol_compare (hs, hns) > 0) {
 574             *hp = h->next;
 575             h->next = h->next->next;
 576             (*hp)->next = h;
 577             hp = &rl->heads;
 578         } else {
 579             hp = &h->next;
 580         }
 581     }
 582 #if DEBUG
 583     fprintf (stderr, "Sorted heads for %s\n", cvs->name);
 584     for (h = rl->heads; h;) {
 585         fprintf (stderr, "\t");
 586         rev_list_dump_ref_parents (stderr, h->parent);
 587         dump_number_file (stderr, h->name, &h->number);
 588         fprintf (stderr, "\n");
 589         h = h->next;
 590     }
 591 #endif
 592 }
 593
 594 rev_list *
 595 rev_list_cvs (cvs_file *cvs)
 596 {
 597     rev_list    *rl = calloc (1, sizeof (rev_list));
 598     cvs_number  trunk_number;
 599     rev_commit  *trunk;
 600     rev_commit  *branch;
 601     cvs_version *cv;
 602     cvs_branch  *cb;
 603     rev_ref     *t;
 604     cvs_version *ctrunk = NULL;
 605
 606     build_branches();
 607     /*
 608      * Locate first revision on trunk branch
 609      */
 610     for (cv = cvs->versions; cv; cv = cv->next) {
 611         if (cvs_is_trunk (&cv->number) &&
 612             (!ctrunk || cvs_number_compare (&cv->number,
 613                                             &ctrunk->number) < 0))
 614         {
 615             ctrunk = cv;
 616         }
 617     }
 618     /*
 619      * Generate trunk branch
 620      */
 621     if (ctrunk)
 622         trunk_number = ctrunk->number;
 623     else
 624         trunk_number = lex_number ("1.1");
 625     trunk = rev_branch_cvs (cvs, &trunk_number);
 626     if (trunk) {
 627         t = rev_list_add_head (rl, trunk, atom ("master"), 2);
 628         t->number = trunk_number;
 629     }
 630     /*
 631      * Search for other branches
 632      */
 633 #if DEBUG
 634     printf ("building branches for %s\n", cvs->name);
 635 #endif
 636
 637     for (cv = cvs->versions; cv; cv = cv->next) {
 638         for (cb = cv->branches; cb; cb = cb->next)
 639         {
 640             branch = rev_branch_cvs (cvs, &cb->number);
 641             rev_list_add_head (rl, branch, NULL, 0);
 642         }
 643     }
 644     generate_files(cvs);
 645     rev_list_patch_vendor_branch (rl, cvs);
 646     rev_list_graft_branches (rl, cvs);
 647     rev_list_set_refs (rl, cvs);
 648     rev_list_sort_heads (rl, cvs);
 649     rev_list_set_tail (rl);
 650     rev_list_free_dead_files (rl);
 651     rev_list_validate (rl);
 652     return rl;
 653 }