Added a description for my extensions (README-my-extensions.html).
[parsecvs/imz-RCS2git-use-cases.git] / revcvs.c
blob8b733493270dd93103d3ace3dfb119ba62284954
1 /*
2 * Copyright © 2006 Keith Packard <keithp@keithp.com>
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.
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.
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.
19 #include "cvs.h"
21 #define DEBUG 0
24 * Given a single-file tree, locate the specific version number
27 static rev_commit *
28 rev_find_cvs_commit (rev_list *rl, cvs_number *number)
30 rev_ref *h;
31 rev_commit *c;
32 rev_file *f;
34 for (h = rl->heads; h; h = h->next) {
35 if (h->tail)
36 continue;
37 for (c = h->commit; c; c = c->parent)
39 f = c->file;
40 if (cvs_number_compare (&f->number, number) == 0)
41 return c;
42 if (c->tail)
43 break;
46 return NULL;
50 * Construct a branch using CVS revision numbers
52 static rev_commit *
53 rev_branch_cvs (cvs_file *cvs, cvs_number *branch)
55 cvs_number n;
56 rev_commit *head = NULL;
57 rev_commit *c, *p;
58 Node *node;
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;
84 c->parent = head;
85 head = c;
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.
92 for (c = head; (p = c->parent); c = p) {
93 if (time_compare (p->file->date, c->file->date) > 0)
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;
102 return head;
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
116 static void
117 rev_list_patch_vendor_branch (rev_list *rl, cvs_file *cvs)
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;
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))
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
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;
150 * Find the latest trunk revision older than
151 * the entire vendor branch
153 while ((t = *tp))
155 if (!t->parent ||
156 time_compare (vlast->file->date,
157 t->parent->file->date) >= 0)
159 break;
161 tp = &t->parent;
163 if (t)
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
170 if (time_compare (vlast->file->date,
171 t->file->date) >= 0)
173 delete_head = 1;
175 else
178 * Splice out any portion of the vendor branch
179 * newer than a the next trunk commit after
180 * the oldest branch commit.
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)
188 * Nothing newer, nuke vendor branch
190 delete_head = 1;
192 else
195 * Some newer stuff, patch parent
197 *vp = NULL;
201 else
202 delete_head = 1;
204 * Patch up the remaining vendor branch pieces
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;
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;
222 for (vr = vendor->commit; vr; vr = vr->parent)
224 if (!vr->parent) {
225 vr->tail = 1;
226 vr->parent = v;
227 break;
233 * Merge two branches based on dates
235 while (t && v)
237 if (time_compare (v->file->date,
238 t->file->date) >= 0)
240 *tp = v;
241 tp = &v->parent;
242 v = v->parent;
244 else
246 *tp = t;
247 tp = &t->parent;
248 t = t->parent;
251 if (t)
252 *tp = t;
253 else
254 *tp = v;
256 if (delete_head) {
257 *h_p = h->next;
258 free (h);
259 } else {
260 h_p = &(h->next);
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");
269 #endif
273 * Given a disconnected set of branches, graft the bottom
274 * of each branch where it belongs on the parent branch
277 static void
278 rev_list_graft_branches (rev_list *rl, cvs_file *cvs)
280 rev_ref *h;
281 rev_commit *c;
282 cvs_version *cv;
283 cvs_branch *cb;
286 * Glue branches together
288 for (h = rl->heads; h; h = h->next) {
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
295 if (h == rl->heads)
296 continue;
297 if (h->tail)
298 continue;
300 * Find last commit on branch
302 for (c = h->commit; c && c->parent; c = c->parent)
303 if (c->tail) {
304 c = NULL; /* already been done, skip */
305 break;
307 if (c) {
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
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)
318 c->parent = rev_find_cvs_commit (rl, &cv->number);
319 c->tail = 1;
320 break;
323 if (c->parent)
325 #if 0
327 * check for a parallel vendor branch
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;
337 * Walk to head of vendor branch
339 while ((n_v_c = rev_find_cvs_commit (rl, &v_n)))
342 * Stop if we reach a date after the
343 * branch version date
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]++;
350 if (v_c)
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;
362 #endif
363 break;
371 * For each symbol, locate the appropriate commit
374 static rev_ref *
375 rev_list_find_branch (rev_list *rl, cvs_number *number)
377 cvs_number n;
378 rev_ref *h;
380 if (number->c < 2)
381 return NULL;
382 n = *number;
383 h = NULL;
384 while (n.c >= 2)
386 for (h = rl->heads; h; h = h->next) {
387 if (cvs_same_branch (&h->number, &n)) {
388 break;
391 if (h)
392 break;
393 n.c -= 2;
395 return h;
398 static void
399 rev_list_set_refs (rev_list *rl, cvs_file *cvs)
401 rev_ref *h;
402 cvs_symbol *s;
403 rev_commit *c;
406 * Locate a symbolic name for this head
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;
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;
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;
432 if (c)
433 h = rev_list_add_head (rl, c, s->name,
434 cvs_number_degree (&s->number));
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);
445 * Fix up unnamed heads
447 for (h = rl->heads; h; h = h->next) {
448 cvs_number n;
449 rev_commit *c;
451 if (h->name)
452 continue;
453 for (c = h->commit; c; c = c->parent) {
454 if (c->nfiles)
455 break;
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 */
468 * Link heads together in a tree
470 for (h = rl->heads; h; h = h->next) {
471 cvs_number n;
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);
481 if (h->parent && !h->name) {
482 char name[1024];
483 char rev[CVS_MAX_REV_LEN];
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);
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
500 static void
501 rev_list_free_dead_files (rev_list *rl)
503 rev_ref *h;
504 rev_commit *c;
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;
514 if (c->tail)
515 break;
520 #if UNUSED
521 static int
522 rev_order_compare (cvs_number *a, cvs_number *b)
524 if (a->c != b->c)
525 return a->c - b->c;
526 return cvs_number_compare (b, a);
528 #endif
530 static cvs_symbol *
531 cvs_find_symbol (cvs_file *cvs, char *name)
533 cvs_symbol *s;
535 for (s = cvs->symbols; s; s = s->next)
536 if (s->name == name)
537 return s;
538 return NULL;
541 static int
542 cvs_symbol_compare (cvs_symbol *a, cvs_symbol *b)
544 if (!a) {
545 if (!b) return 0;
546 return -1;
548 if (!b)
549 return 1;
550 return cvs_number_compare (&a->number, &b->number);
553 static void
554 rev_list_dump_ref_parents (FILE *f, rev_ref *h)
556 if (h) {
557 rev_list_dump_ref_parents (f, h->parent);
558 fprintf (f, "%s > ", h->name);
562 static void
563 rev_list_sort_heads (rev_list *rl, cvs_file *cvs)
565 rev_ref *h, **hp;
566 cvs_symbol *hs, *hns;
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;
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;
591 #endif
594 rev_list *
595 rev_list_cvs (cvs_file *cvs)
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;
606 build_branches();
608 * Locate first revision on trunk branch
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))
615 ctrunk = cv;
619 * Generate trunk branch
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;
631 * Search for other branches
633 #if DEBUG
634 printf ("building branches for %s\n", cvs->name);
635 #endif
637 for (cv = cvs->versions; cv; cv = cv->next) {
638 for (cb = cv->branches; cb; cb = cb->next)
640 branch = rev_branch_cvs (cvs, &cb->number);
641 rev_list_add_head (rl, branch, NULL, 0);
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;