/[CvsGraph]/cvsgraph/cvsgraph.c
ViewVC logotype

Diff of /cvsgraph/cvsgraph.c

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph | View Patch Patch

revision 1.2, Tue Feb 20 22:36:38 2001 UTC revision 1.47, Sun Aug 29 12:20:03 2004 UTC
# Line 2  Line 2 
2   * CvsGraph graphical representation generator of brances and revisions   * CvsGraph graphical representation generator of brances and revisions
3   * of a file in cvs/rcs.   * of a file in cvs/rcs.
4   *   *
5   * Copyright (C) 2001  B. Stultiens   * Copyright (C) 2001,2002,2003,2004  B. Stultiens
6   *   *
7   * This program is free software; you can redistribute it and/or modify   * This program is free software; you can redistribute it and/or modify
8   * it under the terms of the GNU General Public License as published by   * it under the terms of the GNU General Public License as published by
# Line 19  Line 19 
19   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20   */   */
21    
22  /*  #include "config.h"
  * Approx. layout of a cvs/rcs log:  
  *  
  * ws           ::= "[ \t]*"  
  * rev_nr       ::= "[:digit:]+(\.[:digit:]+)*"  
  * path_name    ::= "/?(([^\n/]*)/)+"  
  * file_name    ::= "[^\n]+"  
  * file_path    ::= "{file_path}{file_name}"  
  * tag          ::= "[^,.$@:;\0-\037]+"  
  * number       ::= "[:digit:]+"  
  * separator    ::= "(-{28})|(={78)\n"  
  *  
  * The header is identified with this snippet until  
  * a {separator} is encountered:  
  *      "RCS file:{ws}{file_path}"  
  *      "Working file:{ws}{file_name}"  
  *      "head:{ws}{rev_nr}"  
  *      "branch:{ws}{rev_nr}?"  
  *      "locks:{ws}[^\n]*"  
  *      "access list:{ws}[^\n]*"  
  *      "symbolic names:"  
  *      "(\t{tag}:{rev_nr}\n)*"  
  *      "keyword substitution:{ws}[^\n]*"  
  *      "total revisions:{ws}{number};{ws}selected revisions:{ws}{number}"  
  *      "description:"  
  *      "<any text you can imagine until a separator>"  
  *  
  * Each revision is identiefied with:  
  *      "{separator}"  
  *      "revision{ws}{rev_nr}"  
  *      "date: 2001/02/15 20:17:37;  author: bertho;  state: Exp;  lines: +2 -0  
  *      "any text as a comment until a separator>"  
  *  
  * The last revision has the "={78}" separator. Eventually, a next file may be  
  * appended.  
  */  
23    
24  #include <stdio.h>  #include <stdio.h>
25  #include <stdlib.h>  #include <stdlib.h>
26    #include <stdarg.h>
27  #include <unistd.h>  #include <unistd.h>
28  #include <string.h>  #include <string.h>
29  #include <assert.h>  #include <assert.h>
30  #include <sys/types.h>  #include <sys/types.h>
31  #include <sys/stat.h>  #include <sys/stat.h>
32  #include <sys/wait.h>  #ifdef HAVE_SYS_WAIT_H
33    # include <sys/wait.h>
34    #endif
35  #include <fcntl.h>  #include <fcntl.h>
36  #include <regex.h>  #include <regex.h>
37  #include <errno.h>  #include <errno.h>
38  #include <getopt.h>  #include <ctype.h>
39    #include <time.h>
40    #include <limits.h>
41    #include <regex.h>
42    #include <math.h>
43    
44    #ifdef HAVE_GETOPT_H
45    # include <getopt.h>
46    #endif
47    
48  #include <gd.h>  #include <gd.h>
49  #include <gdfontt.h>  #include <gdfontt.h>
50    
51  #include "cvsgraph.h"  #include "cvsgraph.h"
52  #include "utils.h"  #include "utils.h"
53  #include "readconf.h"  #include "readconf.h"
54    #include "rcs.h"
55    
56  /*#define DEBUG         1*/  #if !defined(HAVE_IMAGE_GIF) && !defined(HAVE_IMAGE_PNG) && !defined(HAVE_IMAGE_JPEG)
57    # error No image output format available. Check libgd
58    #endif
59    
 #define RLOGCMD         "/usr/bin/rlog"  
 #define DEVNULL         "/dev/null"  
 #define CONFFILENAME    "cvsgraph.conf"  
60    
61  #ifndef ETCDIR  /*#define DEBUG         1*/
62  # define ETCDIR         "/usr/local/etc"  /*#define NOGDFILL      1*/
63  #endif  /*#define DEBUG_IMAGEMAP        1*/
64    
65    #define LOOPSAFEGUARD   10000   /* Max itterations in possible infinite loops */
66    
67  #ifndef MAX  #ifndef MAX
68  # define MAX(a,b)       ((a) > (b) ? (a) : (b))  # define MAX(a,b)       ((a) > (b) ? (a) : (b))
# Line 97  Line 75 
75  #define ALIGN_HL        0x00  #define ALIGN_HL        0x00
76  #define ALIGN_HC        0x01  #define ALIGN_HC        0x01
77  #define ALIGN_HR        0x02  #define ALIGN_HR        0x02
78  #define ALIGN_HX        0x0f  #define ALIGN_HX        0x0f
79  #define ALIGN_VT        0x00  #define ALIGN_VT        0x00
80  #define ALIGN_VC        0x10  #define ALIGN_VC        0x10
81  #define ALIGN_VB        0x20  #define ALIGN_VB        0x20
82  #define ALIGN_VX        0xf0  #define ALIGN_VX        0xf0
83    
84  typedef struct __revid_t  #ifndef M_PI    /* math.h should have defined this */
85  {  # define M_PI 3.14159265358979323846
86          char    *branch;  #endif
87          char    *rev;  #define ROUND(f)        ((f >= 0.0)?((int)(f + 0.5)):((int)(f - 0.5)))
88          int     isbranch;  
89  } revid_t;  #define ARROW_LENGTH    12      /* Default arrow dimensions */
90    #define ARROW_WIDTH     3
 typedef struct __tag_t  
 {  
         char    *tag;  
         revid_t *rev;  
 } tag_t;  
   
 struct __branch_t;  
   
 typedef struct __revision_t  
 {  
         revid_t         *rev;  
         char            *info;  
         char            *comment;  
         tag_t           **tags;  
         int             ntags;  
         struct __branch_t       **branches;  
         int             nbranches;  
         int             w, h;  
         int             x, y;  
 } revision_t;  
   
 typedef struct __branch_t  
 {  
         char            *branch;  
         revision_t      *branchpoint;  
         tag_t           *tag;  
         revision_t      **revs;  
         int             nrevs;  
         int             tw, th;  
         int             w, h;  
         int             x, y;  
 } branch_t;  
   
 typedef struct __rcsfilelog_t  
 {  
         char            *path;  
         char            *name;  
         revid_t         *head;  
         char            *branch;  
         char            *locks;  
         char            *access;  
         char            *keyword;  
         char            *totalrevs;  
         char            *comment;  
         tag_t           **tags;  
         int             ntags;  
         revision_t      **revs;  
         int             nrevs;  
         branch_t        **branches;  
         int             nbranches;  
         int             tw, th;  
 } rcsfilelog_t;  
91    
92  /*  /*
93   **************************************************************************   **************************************************************************
# Line 169  Line 95 
95   **************************************************************************   **************************************************************************
96   */   */
97    
 char *rlogcmd = RLOGCMD;  
 char *devnull = DEVNULL;  
   
98  config_t conf;  config_t conf;
99    int debuglevel;
100    
101    static color_t white_color = {255, 255, 255, 0};
102    static color_t black_color = {0, 0, 0, 0};
103    
104    static branch_t *subtree_branch = NULL;         /* Set to the (first) subtree branch that we want to show */
105    static revision_t *subtree_rev = NULL;          /* Set to the subtree revision which branches we want to show */
106    
107    static msg_stack_t *msg_stack = NULL;           /* Messages that would otherwise be sent to stderr goto the image */
108    static int nmsg_stack = 0;
109    
110    /*
111     **************************************************************************
112     * Forwards
113     **************************************************************************
114     */
115    static void zap_string(void);
116    static char *dup_string(void);
117    static void add_string_str(const char *s);
118    static void add_string_ch(int ch);
119    static void add_string_date(const char *d);
120    static void add_string_str_html(const char *s, int maxlen);
121    static void add_string_str_len(const char *s, int maxlen);
122    
123    static void calc_subtree_size(branch_t *b, int *x, int *y, int *w, int *h);
124    
125  /*  /*
126   **************************************************************************   **************************************************************************
127   * Debug routines   * Debug routines
128   **************************************************************************   **************************************************************************
129   */   */
130  #ifdef DEBUG  static void dump_rev(char *p, rev_t *r)
131  void dump_revid(const char *s, revid_t *r)  {
132            printf("%s", p);
133            if(r)
134                    printf("'%s', '%s', %d\n", r->rev, r->branch, r->isbranch);
135            else
136                    printf("<null>\n");
137    }
138    
139    static void dump_id(char *p, char *d)
140  {  {
141          fprintf(stderr, "%s.branch  : '%s'\n", s, r->branch);          printf("%s", p);
142          fprintf(stderr, "%s.rev     : '%s'\n", s, r->rev);          if(d)
143          fprintf(stderr, "%s.isbranch: %d\n", s, r->isbranch);                  printf("'%s'\n", d);
144            else
145                    printf("<null>\n");
146  }  }
147    
148  void dump_tag(const char *s, tag_t *t)  static void dump_idrev(char *p, idrev_t *t)
149  {  {
150          fprintf(stderr, "%s", s);          printf("%s", p);
151          dump_revid(t->tag, t->rev);          if(t)
152            {
153                    printf("'%s' -> ", t->id);
154                    dump_rev("", t->rev);
155            }
156            else
157                    printf("<null>\n");
158  }  }
159    
160  void dump_rev(revision_t *r)  static void dump_tag(char *p, tag_t *t)
161  {  {
162          int i;          printf("%s", p);
163          dump_revid("Revision", r->rev);          if(t)
164          fprintf(stderr, "Revision.Info   : '%s'\n", r->info);          {
165          fprintf(stderr, "Revision.Comment: '%s'\n", r->comment);                  printf("'%s' -> ", t->tag);
166          for(i = 0; i < r->ntags; i++)                  dump_rev("", t->rev);
167                  dump_tag("Revision.Tag: ", r->tags[i]);          }
168            else
169                    printf("<null>\n");
170  }  }
171    
172  void dump_branch(branch_t *b)  static void dump_delta(char *p, delta_t *d)
173  {  {
174          int i;          int i;
175          fprintf(stderr, "Branch: '%s'\n", b->branch);          printf("%sdelta.rev   : ", p);
176          if(b->tag)          dump_rev("", d->rev);
177                  dump_tag("branchtag:", b->tag);          printf("%sdelta.date  : %s\n", p, d->date);
178          for(i = 0; i < b->nrevs; i++)          printf("%sdelta.author: %s\n", p, d->author);
179                  fprintf(stderr, "Branch.Rev: '%s'\n", b->revs[i]->rev->rev);          printf("%sdelta.state : %s\n", p, d->state);
180            for(i = 0; d->branches && i < d->branches->nrevs; i++)
181            {
182                    printf("%sdelta.branch: ", p);
183                    dump_rev("", d->branches->revs[i]);
184            }
185            printf("%sdelta.next  : ", p);
186            dump_rev("", d->next);
187            printf("\n");
188  }  }
189    
190  void dump_log(rcsfilelog_t *r)  static void dump_dtext(char *p, dtext_t *d)
191    {
192            printf("%sdtext.rev  : ", p);
193            dump_rev("", d->rev);
194            printf("%sdtext.log  : %d bytes\n", p, d->log ? strlen(d->log) : -1);
195            printf("%sdtext.text : %d bytes\n", p, d->text ? strlen(d->text) : -1);
196            printf("\n");
197    }
198    
199    static void dump_rcsfile(rcsfile_t *rcs)
200  {  {
201          int i;          int i;
202            printf("root   : '%s'\n", rcs->root);
203            printf("module : '%s'\n", rcs->module);
204            printf("file   : '%s'\n", rcs->file);
205            dump_rev("head   : ", rcs->head);
206            dump_rev("branch : ", rcs->branch);
207            printf("access :\n");
208            for(i = 0; rcs->access && i < rcs->access->nids; i++)
209                    dump_id("\t", rcs->access->ids[i]);
210            printf("tags   :\n");
211            for(i = 0; rcs->tags && i < rcs->tags->ntags; i++)
212                    dump_tag("\t", rcs->tags->tags[i]);
213            printf("locks  :%s\n", rcs->strict ? " (strict)" : "");
214            for(i = 0; rcs->locks && i < rcs->locks->nidrevs; i++)
215                    dump_idrev("\t", rcs->locks->idrevs[i]);
216            printf("comment: '%s'\n", rcs->comment);
217            printf("expand : '%s'\n", rcs->expand ? rcs->expand : "(default -kv)");
218            printf("deltas :\n");
219            for(i = 0; rcs->deltas && i < rcs->deltas->ndeltas; i++)
220                    dump_delta("\t", rcs->deltas->deltas[i]);
221            printf("desc   : '%s'\n", rcs->desc);
222            printf("dtexts :\n");
223            for(i = 0; rcs->dtexts && i < rcs->dtexts->ndtexts; i++)
224                    dump_dtext("\t", rcs->dtexts->dtexts[i]);
225    
226          fprintf(stderr, "Path   : '%s'\n", r->path);          fflush(stdout);
         fprintf(stderr, "Name   : '%s'\n", r->name);  
         dump_revid("Head", r->head);  
         fprintf(stderr, "Branch : '%s'\n", r->branch);  
         fprintf(stderr, "Locks  : '%s'\n", r->locks);  
         fprintf(stderr, "Access : '%s'\n", r->access);  
         fprintf(stderr, "Keyword: '%s'\n", r->keyword);  
         fprintf(stderr, "Total  : '%s'\n", r->totalrevs);  
         fprintf(stderr, "Comment: '%s'\n", r->comment);  
         for(i = 0; i < r->ntags; i++)  
                 dump_tag("", r->tags[i]);  
         for(i = 0; i < r->nrevs; i++)  
                 dump_rev(r->revs[i]);  
         for(i = 0; i < r->nbranches; i++)  
                 dump_branch(r->branches[i]);  
227  }  }
 #endif  
228    
229  /*  /*
230   **************************************************************************   **************************************************************************
231   * Retrieve the log entries   * Error/Warning Message helpers
232   **************************************************************************   **************************************************************************
233   */   */
234  FILE *get_log(const char *cvsroot, const char *module, const char *file)  #define MSGBUFSIZE      256
235    void stack_msg(int severity, const char *fmt, ...)
236  {  {
237          pid_t pid;          va_list va;
238          int nul;          int i;
239          FILE *tmp;          char *buf = xmalloc(MSGBUFSIZE);
240          char *cmd = NULL;          switch(severity)
         int status;  
         mode_t um;  
   
         if((nul = open(devnull, O_RDWR, S_IRUSR|S_IWUSR)) == -1)  
                 return NULL;  
   
         um = umask(0177);       /* Set tempfiles to max 0600 permissions */  
         if((tmp = tmpfile()) == NULL)  
         {  
                 close(nul);  
                 return NULL;  
         }  
         umask(um);  
   
         cmd = xmalloc(strlen(cvsroot) + + strlen(module) + strlen(file) + 2 + 1);  
         sprintf(cmd, "%s/%s/%s", cvsroot, module, file);  
   
         switch(pid = fork())  
241          {          {
242          case -1:        /* Error */          case MSG_WARN:  sprintf(buf, "Warning: "); break;
243                  close(nul);          case MSG_ERR:   sprintf(buf, "Error: "); break;
244                  fclose(tmp);          default:        sprintf(buf, "Unqualified error: "); break;
245                  xfree(cmd);          }
246                  return NULL;          i = strlen(buf);
247          case 0:         /* Child */          assert(i < MSGBUFSIZE);
248                  if((dup2(nul, STDIN_FILENO)) == -1)     exit(126);          va_start(va, fmt);
249                  if((dup2(fileno(tmp), STDOUT_FILENO)) == -1)    exit(126);          vsnprintf(buf+i, MSGBUFSIZE-i, fmt, va);
250                  if((dup2(nul, STDERR_FILENO)) == -1)    exit(126);          va_end(va);
251                  close(nul);          if(!msg_stack)
252                  fclose(tmp);                  msg_stack = xmalloc(sizeof(*msg_stack));
253                  execl(rlogcmd, rlogcmd, cmd, NULL);          else
                 exit(127);  
                 break;  
         default:        /* Parent */  
                 close(nul);  
                 xfree(cmd);  
                 while(1)  
                 {  
                         if(waitpid(pid, &status, 0) == -1)  
                         {  
                                 if(errno != EINTR)  
                                 {  
                                         fclose(tmp);  
                                         return NULL;  
                                 }  
                         }  
                         else  
                                 break;  
                 }  
                 break;  
         }  
   
         if(WIFEXITED(status) && WEXITSTATUS(status) == 0)  
254          {          {
255                  if(fseek(tmp, 0, SEEK_SET) != (off_t)-1)                  msg_stack = xrealloc(msg_stack, (nmsg_stack+1)*sizeof(*msg_stack));
                 {  
                         return tmp;  
                 }  
                 else  
                 {  
                         fclose(tmp);  
                         return NULL;  
                 }  
256          }          }
257          else          msg_stack[nmsg_stack].msg = buf;
258                  fclose(tmp);          msg_stack[nmsg_stack].severity = severity;
259          return NULL;          nmsg_stack++;
260  }  }
261    
262  /*  /*
263   **************************************************************************   **************************************************************************
264   * Parse the log entries   * Read the rcs file
265   **************************************************************************   **************************************************************************
266   */   */
267  char *strip_dup(const char *s)  static rcsfile_t *get_rcsfile(const char *cvsroot, const char *module, const char *file)
268  {  {
269          int l = strlen(s);          char *cmd = NULL;
270          char *c = xmalloc(l+1);          int rv;
   
         strcpy(c, s);  
         while(*c == ' ' || *c == '\t')  
         {  
                 memmove(c, c+1, l--);  
         }  
         while(l && strchr(" \t\r\n", c[l]))  
                 c[l--] = '\0';  
         return c;  
 }  
271    
272  revid_t *make_revid(const char *s)          if(file)
 {  
         char *c = strip_dup(s);  
         char *cptr;  
         int dots = 0;  
         revid_t *r = xmalloc(sizeof(*r));  
         for(cptr = c; *cptr; cptr++)  
273          {          {
274                  if(*cptr == '.')                  cmd = xmalloc(strlen(cvsroot) + strlen(module) + strlen(file) + 1);
275                          dots++;                  sprintf(cmd, "%s%s%s", cvsroot, module, file);
276                    if(!(rcsin = fopen(cmd, "rb")))
277                    {
278                            perror(cmd);
279                            return NULL;
280                    }
281                    input_file = cmd;
282          }          }
283          if(!dots)          else
284          {          {
285                  r->rev = xstrdup("");                  rcsin = stdin;
286                  r->branch = xstrdup(s);                  input_file = "<stdin>";
                 r->isbranch = 1;  
287          }          }
288          else if(!*c)          line_number = 1;
289            rv = rcsparse();
290            if(file)
291          {          {
292                  r->rev = xstrdup("?.?");                  fclose(rcsin);
293                  r->branch = xstrdup("?");                  xfree(cmd);
294          }          }
295          else if(dots & 1)          if(rv)
296                    return NULL;
297            input_file = NULL;
298            if(file)
299          {          {
300                  char *t;                  rcsfile->root = xstrdup(cvsroot);
301                  r->rev = c;                  rcsfile->module = xstrdup(module);
302                  r->branch = xstrdup(c);                  rcsfile->file = xstrdup(file);
                 cptr = strrchr(r->branch, '.');  
                 assert(cptr != NULL);  
                 *cptr = '\0';  
                 t = strrchr(r->branch, '.');  
                 if((t&& !strcmp(t+1, "0")) || (!t && !strcmp(r->branch, "0")))  
                 {  
                         /* Magic branch numbers "x.x.0.x" */  
                         r->isbranch = 1;  
                         if(t)  
                                 strcpy(t+1, cptr+1);  
                         else  
                                 strcpy(r->branch, cptr+1);  
                 }  
303          }          }
304          else          else
305          {          {
306                  r->isbranch = 1;                  rcsfile->root = xstrdup("");
307                  r->branch = c;                  rcsfile->module = xstrdup("");
308                  r->rev = xmalloc(strlen(c) + 3);                  rcsfile->file = xstrdup("<stdin>");
                 strcpy(r->rev, c);  
                 strcat(r->rev, ".?");  
309          }          }
310          return r;          return rcsfile;
311  }  }
312    
313  char *add_comment(char *c, const char *n)  /*
314     **************************************************************************
315     * Sort and find helpers
316     **************************************************************************
317     */
318    static int count_dots(const char *s)
319  {  {
320          int l;          int i;
321          char *r;          for(i = 0; *s; s++)
         assert(n != NULL);  
         l = strlen(n);  
         if(!c)  
         {  
                 r = xmalloc(l+1);  
                 strcpy(r, n);  
         }  
         else  
322          {          {
323                  r = xmalloc(l+strlen(c)+1+1);                  if(*s == '.')
324                  strcpy(r, c);                          i++;
                 strcat(r, "\n");  
                 strcat(r, n);  
325          }          }
326          return r;          return i;
327  }  }
328    
329  int get_line(FILE *fp, char *buf, int maxlen)  static int compare_rev(int bcmp, const rev_t *r1, const rev_t *r2)
330  {  {
331          int n;          int d1, d2;
332          int seennl;          char *c1, *c2;
333  retry:          char *v1, *v2;
334          seennl = 0;          char *s1, *s2;
335          if(!fgets(buf, maxlen, fp))          int retval = 0;
336                  return feof(fp) ? 0 : -1;          assert(r1 != NULL);
337          n = strlen(buf);          assert(r2 != NULL);
338          while(n && buf[n-1] == '\n')          if(bcmp)
339          {          {
340                  seennl = 1;                  assert(r1->branch != NULL);
341                  buf[--n] = '\0';                  assert(r2->branch != NULL);
342                    c1 = r1->branch;
343                    c2 = r2->branch;
344          }          }
345          if(!n)          else
                 goto retry;  
         if(!seennl)  
346          {          {
347                  while(fgetc(fp) != '\n')                  assert(r1->rev != NULL);
348                          ;                  assert(r2->rev != NULL);
349                    c1 = r1->rev;
350                    c2 = r2->rev;
351          }          }
         return n;  
 }  
352    
353  rcsfilelog_t *parse_log(FILE *fp)          d1 = count_dots(c1);
354  {          d2 = count_dots(c2);
355          rcsfilelog_t *p;          if(d1 != d2)
         int state = 0;  
         regex_t rerev;  
         regex_t reinfo;  
   
         if(regcomp(&rerev, "^revision[ \\t]*[0-9]+(\\.[0-9]+)*", REG_EXTENDED))  
                 return NULL;  
         if(regcomp(&reinfo, "^date:[^;]*;[ \\t]*author:[^;]*;[ \\t]+state:", REG_EXTENDED))  
356          {          {
357                  regfree(&rerev);                  return d1 - d2;
                 return NULL;  
358          }          }
359          p = xmalloc(sizeof(*p));  
360          while(state != 4)          s1 = v1 = xstrdup(c1);
361            s2 = v2 = xstrdup(c2);
362            while(1)
363          {          {
364                  char buf[256];                  char *vc1 = strchr(s1, '.');
365                  int n;                  char *vc2 = strchr(s2, '.');
366                  n = get_line(fp, buf, sizeof(buf));                  if(vc1 && vc2)
367                  if(!n)                          *vc1 = *vc2 = '\0';
368                          break;                  if(*s1 && *s2)
                 if(n == -1)  
                 {  
                         perror("tempfile read");  
                         xfree(p);  
                         regfree(&rerev);  
                         regfree(&reinfo);  
                         return NULL;  
                 }  
                 switch(state)  
369                  {                  {
370                  case 0: /* Prologue */                          d1 = atoi(s1);
371  more_prologue:                          d2 = atoi(s2);
372                          if(!strncmp(buf, "RCS file:", 9))                          if(d1 != d2)
                         {  
                                 p->path = strip_dup(buf+9);  
                         }  
                         else if(!strncmp(buf, "Working file:", 13))  
                         {  
                                 p->name = strip_dup(buf+13);  
                         }  
                         else if(!strncmp(buf, "head:", 5))  
                         {  
                                 p->head = make_revid(buf+5);  
                         }  
                         else if(!strncmp(buf, "branch:", 7))  
                         {  
                                 p->branch = strip_dup(buf+7);  
                         }  
                         else if(!strncmp(buf, "locks:", 6))  
                         {  
                                 p->locks = strip_dup(buf+6);  
                         }  
                         else if(!strncmp(buf, "access list:", 12))  
                         {  
                                 p->access = strip_dup(buf+12);  
                         }  
                         else if(!strncmp(buf, "keyword substitution:", 21))  
                         {  
                                 p->keyword = strip_dup(buf+21);  
                         }  
                         else if(!strncmp(buf, "total revisions:", 16))  
                         {  
                                 p->totalrevs = strip_dup(buf+16);  
                         }  
                         else if(!strncmp(buf, "description:", 12))  
                         {  
                                 state = 2;  
                         }  
                         else if(!strncmp(buf, "symbolic names:", 15))  
                         {  
                                 state = 1;  
                         }  
                         else  
                         {  
                                 fprintf(stderr, "Unknown keyword(s) in line '%s' (state=%d)\n", buf, state);  
                                 xfree(p);  
                                 return NULL;  
                         }  
                         break;  
                 case 1: /* Tags */  
                         if(*buf != '\t')  
                         {  
                                 state = 0;  
                                 goto more_prologue;  
                         }  
                         else  
                         {  
                                 char *rev = strrchr(buf, ':');  
                                 tag_t *t;  
                                 if(!rev)  
                                 {  
                                         state = 2;  
                                         goto more_prologue;  
                                 }  
                                 *rev = '\0';  
                                 t = xmalloc(sizeof(*t));  
                                 t->tag = strip_dup(buf);  
                                 t->rev = make_revid(rev+1);  
                                 p->tags = xrealloc(p->tags, (p->ntags+1) * sizeof(p->tags[0]));  
                                 p->tags[p->ntags] = t;  
                                 p->ntags++;  
                         }  
                         break;  
                 case 2: /* Description */  
 add_description:  
                         if(!strcmp(buf, "----------------------------"))  
                         {  
                                 /* End of description */  
                                 state = 3;  
                                 break;  
                         }  
                         else if(!strcmp(buf, "============================================================================="))  
373                          {                          {
374                                  /* End of log */                                  retval = d1 - d2;
                                 state = 4;  
375                                  break;                                  break;
376                          }                          }
                         if(!p->nrevs)  
                                 p->comment = add_comment(p->comment, buf);  
                         else  
                                 p->revs[p->nrevs-1]->comment = add_comment(p->revs[p->nrevs-1]->comment, buf);  
                         break;  
                 case 3:  
                         if(!regexec(&rerev, buf, 0, NULL, 0))  
                         {  
                                 revision_t *r = xmalloc(sizeof(*r));  
                                 p->revs = xrealloc(p->revs, (p->nrevs+1) * sizeof(p->revs[0]));  
                                 p->revs[p->nrevs] = r;  
                                 p->nrevs++;  
                                 r->rev = make_revid(buf+8);  
                         }  
                         else if(!regexec(&reinfo, buf, 0, NULL, 0))  
                         {  
                                 assert(p->nrevs > 0);  
                                 p->revs[p->nrevs-1]->info = strip_dup(buf);  
                         }  
                         else  
                         {  
                                 /* No match means the description/comment */  
                                 state = 2;  
                                 goto add_description;  
                         }  
                         break;  
                 default:  
                         fprintf(stderr, "Illegal state (%d) in parser\n", state);  
                         xfree(p);  
                         regfree(&rerev);  
                         regfree(&reinfo);  
                         return NULL;  
377                  }                  }
378                    if(!vc1 || !vc2)
379                            break;
380                    s1 = vc1 + 1;
381                    s2 = vc2 + 1;
382          }          }
383          regfree(&rerev);          xfree(v1);
384          regfree(&reinfo);          xfree(v2);
385          return p;          return retval;
386  }  }
387    
388  /*  /*
389   **************************************************************************   **************************************************************************
390   * Sort and find helpers   * Reorganise the rcsfile for the branches
391     *
392     * Basically, we have a list of deltas (i.e. administrative info on
393     * revisions) and a list of delta text (the actual logs and diffs).
394     * The deltas are linked through the 'next' and the 'branches' fields
395     * which describe the tree-structure of revisions.
396     * The reorganisation means that we put each delta and corresponding
397     * delta text in a revision structure and assign it to a specific
398     * branch. This is required because we want to be able to calculate
399     * the bounding boxes of each branch. The revisions expand vertically
400     * and the branches expand horizontally.
401     * The reorganisation is performed in these steps:
402     * 1 - sort deltas and delta text on revision number for quick lookup
403     * 2 - start at the denoted head revision:
404     *      * create a branch structure and add this revision
405     *      * for each 'branches' in the delta do:
406     *              - walk all 'branches' of the delta and recursively goto 2
407     *                with the denoted branch delta as new head
408     *              - backlink the newly create sub-branch to the head revision
409     *                so that we can draw them recursively
410     *      * set head to the 'next' field and goto 2 until no next is
411     *        available
412     * 3 - update the administration
413   **************************************************************************   **************************************************************************
414   */   */
415  int tag_sort(const void *t1, const void *t2)  static int sort_delta(const void *d1, const void *d2)
416    {
417            return compare_rev(0, (*(delta_t **)d1)->rev, (*(delta_t **)d2)->rev);
418    }
419    
420    static int search_delta(const void *r, const void *d)
421  {  {
422  #define TAGPTR(t)       (*((tag_t **)t))          return compare_rev(0, (rev_t *)r, (*(delta_t **)d)->rev);
         return strcmp(TAGPTR(t1)->rev->rev, TAGPTR(t2)->rev->rev);  
 #undef TAGPTR  
423  }  }
424    
425  int rev_sort(const void *v1, const void *v2)  static delta_t *find_delta(delta_t **dl, int n, rev_t *r)
426  {  {
427  #define REVPTR(t)       (*((revision_t **)t))          delta_t **d;
428          return strcmp(REVPTR(v1)->rev->rev, REVPTR(v2)->rev->rev);          if(!n)
429  #undef REVPTR                  return NULL;
430            d = bsearch(r, dl, n, sizeof(*dl), search_delta);
431            if(!d)
432                    return NULL;
433            return *d;
434  }  }
435    
436  int branch_sort(const void *b1, const void *b2)  static int sort_dtext(const void *d1, const void *d2)
437  {  {
438  #define BPTR(t) (*((branch_t **)t))          return compare_rev(0, (*(dtext_t **)d1)->rev, (*(dtext_t **)d2)->rev);
         return strcmp(BPTR(b1)->branch, BPTR(b2)->branch);  
 #undef BPTR  
439  }  }
440    
441  int rev_cmp(const void *id, const void *v)  static int search_dtext(const void *r, const void *d)
442  {  {
443  #define REVPTR(t)       (*((revision_t **)t))          return compare_rev(0, (rev_t *)r, (*(dtext_t **)d)->rev);
         return strcmp(((revid_t *)id)->rev, REVPTR(v)->rev->rev);  
 #undef REVPTR  
444  }  }
445    
446  revision_t *find_revision(rcsfilelog_t * rcs, revid_t *id)  static dtext_t *find_dtext(dtext_t **dl, int n, rev_t *r)
447  {  {
448          revision_t **r;          dtext_t **d;
449          if(id->isbranch)          if(!n)
450                  return NULL;                  return NULL;
451          r = bsearch(id, rcs->revs, rcs->nrevs, sizeof(rcs->revs[0]), rev_cmp);          d = bsearch(r, dl, n, sizeof(*dl), search_dtext);
452          if(!r)          if(!d)
453                  return NULL;                  return NULL;
454          else          return *d;
                 return *r;  
455  }  }
456    
457  int branch_cmp(const void *s, const void *b)  static rev_t *dup_rev(const rev_t *r)
458  {  {
459          return strcmp((const char *)s, (*((branch_t **)b))->branch);          rev_t *t = xmalloc(sizeof(*t));
460            t->rev = xstrdup(r->rev);
461            t->branch = xstrdup(r->branch);
462            t->isbranch = r->isbranch;
463            return t;
464    }
465    
466    static branch_t *new_branch(delta_t *d, dtext_t *t)
467    {
468            branch_t *b = xmalloc(sizeof(*b));
469            revision_t *r = xmalloc(sizeof(*r));
470            r->delta = d;
471            r->dtext = t;
472            r->rev = d->rev;
473            r->branch = b;
474            b->branch = dup_rev(d->rev);
475            b->branch->isbranch = 1;
476            b->nrevs = 1;
477            b->revs = xmalloc(sizeof(b->revs[0]));
478            b->revs[0] = r;
479            return b;
480    }
481    
482    static revision_t *add_to_branch(branch_t *b, delta_t *d, dtext_t *t)
483    {
484            revision_t *r = xmalloc(sizeof(*r));
485            r->delta = d;
486            r->dtext = t;
487            r->rev = d->rev;
488            r->branch = b;
489            b->revs = xrealloc(b->revs, (b->nrevs+1) * sizeof(b->revs[0]));
490            b->revs[b->nrevs] = r;
491            b->nrevs++;
492            return r;
493  }  }
494    
495  branch_t *find_branch(rcsfilelog_t *rcs, const char *id)  static int sort_branch_height(const void *b1, const void *b2)
496  {  {
497          branch_t **b;          return (*(branch_t **)b1)->nrevs - (*(branch_t **)b2)->nrevs;
498          b = bsearch(id, rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), branch_cmp);  }
499          if(!b)  
500                  return NULL;  static void build_branch(branch_t ***bl, int *nbl, delta_t **sdl, int nsdl, dtext_t **sdt, int nsdt, delta_t *head)
501          else  {
502                  return *b;          branch_t *b;
503            dtext_t *text;
504            revision_t *currev;
505    
506            assert(head != NULL);
507    
508            if(head->flag)
509            {
510                    stack_msg(MSG_ERR, "Circular reference on '%s' in branchpoint\n", head->rev->rev);
511                    return;
512            }
513            head->flag++;
514            text = find_dtext(sdt, nsdt, head->rev);
515    
516            /* Create a new branch for this head */
517            b = new_branch(head, text);
518            *bl = xrealloc(*bl, (*nbl+1)*sizeof((*bl)[0]));
519            (*bl)[*nbl] = b;
520            (*nbl)++;
521            currev = b->revs[0];
522            while(1)
523            {
524                    /* Process all sub-branches */
525                    if(head->branches)
526                    {
527                            int i;
528                            for(i = 0; i < head->branches->nrevs; i++)
529                            {
530                                    delta_t *d = find_delta(sdl, nsdl, head->branches->revs[i]);
531                                    int btag = *nbl;
532                                    if(!d)
533                                            continue;
534                                    build_branch(bl, nbl, sdl, nsdl, sdt, nsdt, d);
535    
536                                    /* Set the new branch's origin */
537                                    (*bl)[btag]->branchpoint = currev;
538    
539                                    /* Add branch to this revision */
540                                    currev->branches = xrealloc(currev->branches, (currev->nbranches+1)*sizeof(currev->branches[0]));
541                                    currev->branches[currev->nbranches] = (*bl)[btag];
542                                    currev->nbranches++;
543                            }
544                            if(conf.branch_resort)
545                                    qsort(currev->branches, currev->nbranches, sizeof(currev->branches[0]), sort_branch_height);
546                    }
547    
548                    /* Walk through the next list */
549                    if(!head->next)
550                            return;
551    
552                    head = find_delta(sdl, nsdl, head->next);
553                    if(!head)
554                    {
555                            stack_msg(MSG_ERR, "Next revision (%s) not found in deltalist\n", head->next->rev);
556                            return;
557                    }
558                    if(head->flag)
559                    {
560                            stack_msg(MSG_ERR, "Circular reference on '%s'\n", head->rev->rev);
561                            return;
562                    }
563                    head->flag++;
564                    text = find_dtext(sdt, nsdt, head->rev);
565                    currev = add_to_branch(b, head, text);
566            }
567  }  }
568    
569  tag_t *find_branchtag(rcsfilelog_t * rcs, const char *id)  int reorganise_branches(rcsfile_t *rcs)
570  {  {
571            delta_t **sdelta;
572            int nsdelta;
573            dtext_t **sdtext;
574            int nsdtext;
575            delta_t *head;
576            branch_t **bl;
577            int nbl;
578          int i;          int i;
579          for(i = 0; i < rcs->ntags; i++)  
580            assert(rcs->deltas != NULL);
581            assert(rcs->head != NULL);
582    
583            /* Make a new list for quick lookup */
584            nsdelta = rcs->deltas->ndeltas;
585            sdelta = xmalloc(nsdelta * sizeof(sdelta[0]));
586            memcpy(sdelta, rcs->deltas->deltas, nsdelta * sizeof(sdelta[0]));
587            qsort(sdelta, nsdelta, sizeof(sdelta[0]), sort_delta);
588    
589            /* Do the same for the delta text */
590            if(rcs->dtexts)
591            {
592                    nsdtext = rcs->dtexts->ndtexts;
593                    sdtext = xmalloc(nsdtext * sizeof(sdtext[0]));
594                    memcpy(sdtext, rcs->dtexts->dtexts, nsdtext * sizeof(sdtext[0]));
595                    qsort(sdtext, nsdtext, sizeof(sdtext[0]), sort_dtext);
596            }
597            else
598          {          {
599                  if(!rcs->tags[i]->rev->isbranch)                  nsdtext = 0;
600                          continue;                  sdtext = NULL;
601                  if(!strcmp(id, rcs->tags[i]->rev->branch))          }
602                          return rcs->tags[i];  
603            /* Start from the head of the trunk */
604            head = find_delta(sdelta, nsdelta, rcs->head);
605            if(!head)
606            {
607                    stack_msg(MSG_ERR, "Head revision (%s) not found in deltalist\n", rcs->head->rev);
608                    return 0;
609          }          }
610          return NULL;          bl = NULL;
611            nbl = 0;
612            build_branch(&bl, &nbl, sdelta, nsdelta, sdtext, nsdtext, head);
613    
614            /* Reverse the head branch */
615            for(i = 0; i < bl[0]->nrevs/2; i++)
616            {
617                    revision_t *r;
618                    r = bl[0]->revs[i];
619                    bl[0]->revs[i] = bl[0]->revs[bl[0]->nrevs-i-1];
620                    bl[0]->revs[bl[0]->nrevs-i-1] = r;
621            }
622    
623            /* Update the branch-number of the head because it was reversed */
624            xfree(bl[0]->branch->branch);
625            bl[0]->branch->branch = xstrdup(bl[0]->revs[0]->rev->branch);
626    
627            /* Keep the admin */
628            rcs->branches = bl;
629            rcs->nbranches = nbl;
630            rcs->sdelta = sdelta;
631            rcs->nsdelta = nsdelta;
632            rcs->sdtext = sdtext;
633            rcs->nsdtext = nsdtext;
634            rcs->active = bl[0];
635            return 1;
636  }  }
637    
638  /*  /*
639   **************************************************************************   **************************************************************************
640   * Drawing routines   * Assign the symbolic tags to the revisions and branches
641     *
642     * The tags point to revision numbers somewhere in the tree structure
643     * of branches and revisions. First we make a sorted list of all
644     * revisions and then we assign each tag to the proper revision.
645   **************************************************************************   **************************************************************************
646   */   */
647  int get_swidth(const char *s, font_t *f)  static int sort_revision(const void *r1, const void *r2)
648  {  {
649          if(!s)          return compare_rev(0, (*(revision_t **)r1)->delta->rev, (*(revision_t **)r2)->delta->rev);
                 return 0;  
         return strlen(s) * (*f)->w;  
650  }  }
651    
652  int get_sheight(const char *s, font_t *f)  static int search_revision(const void *t, const void *r)
653  {  {
654          int nl;          return compare_rev(0, (rev_t *)t, (*(revision_t **)r)->delta->rev);
         if(!s)  
                 return 0;  
         for(nl = 1; *s; s++)  
         {  
                 if(*s == '\n' && s[1])  
                         nl++;  
         }  
         return nl * (*f)->h;  
655  }  }
656    
657  void draw_rbox(gdImagePtr im, int x1, int y1, int x2, int y2, int r, color_t *color)  static int sort_branch(const void *b1, const void *b2)
658  {  {
659          int r2 = 2*r;          return compare_rev(1, (*(branch_t **)b1)->branch, (*(branch_t **)b2)->branch);
         gdImageLine(im, x1+r, y1, x2-r, y1, color->id);  
         gdImageLine(im, x1+r, y2, x2-r, y2, color->id);  
         gdImageLine(im, x1, y1+r, x1, y2-r, color->id);  
         gdImageLine(im, x2, y1+r, x2, y2-r, color->id);  
         if(r)  
         {  
                 gdImageArc(im, x1+r, y1+r, r2, r2, 180, 270, color->id);  
                 gdImageArc(im, x2-r, y1+r, r2, r2, 270, 360, color->id);  
                 gdImageArc(im, x1+r, y2-r, r2, r2,  90, 180, color->id);  
                 gdImageArc(im, x2-r, y2-r, r2, r2,   0,  90, color->id);  
         }  
660  }  }
661    
662  void draw_string(gdImagePtr im, char *s, font_t *f, int x, int y, int align, color_t *c)  static int search_branch(const void *t, const void *b)
663  {  {
664          int xx, yy;          return compare_rev(1, (rev_t *)t, (*(branch_t **)b)->branch);
665          switch(align & ALIGN_HX)  }
666          {  
667          default:  static char *previous_rev(const char *c)
668          case ALIGN_HL: xx = 0; break;  {
669          case ALIGN_HC: xx = -get_swidth(s, f)/2; break;          int dots = count_dots(c);
670          case ALIGN_HR: xx = -get_swidth(s, f); break;          char *cptr;
671            char *r;
672            if(!dots)
673            {
674                    stack_msg(MSG_ERR, "FIXME: previous_rev(\"%s\"): Cannot determine parent branch revision\n", c);
675                    return xstrdup("1.0");  /* FIXME: don't know what the parent is */
676            }
677            if(dots & 1)
678            {
679                    /* Is is a revision we want the parent of */
680                    r = xstrdup(c);
681                    cptr = strrchr(r, '.');
682                    assert(cptr != NULL);
683                    if(dots == 1)
684                    {
685                            stack_msg(MSG_ERR, "FIXME: previous_rev(\"%s\"): Going beyond top-level?\n", c);
686                            /* FIXME: What is the parent of 1.1? */
687                            cptr[1] = '\0';
688                            strcat(r, "0");
689                            return r;
690                    }
691                    /* Here we have a "x.x[.x.x]+" case */
692                    *cptr = '\0';
693                    cptr = strrchr(r, '.');
694                    assert(cptr != NULL);
695                    *cptr = '\0';
696                    return r;
697            }
698            /* It is a branch we want the parent of */
699            r = xstrdup(c);
700            cptr = strrchr(r, '.');
701            assert(cptr != NULL);
702            *cptr = '\0';
703            return r;
704    }
705    
706    static char *build_regex(size_t n, regmatch_t *m, const char *ms)
707    {
708            char *cptr;
709            int i;
710    
711            if(!conf.merge_to || !conf.merge_to[0])
712                    return NULL;
713    
714            zap_string();
715            for(cptr = conf.merge_to; *cptr; cptr++)
716            {
717                    if(*cptr == '%')
718                    {
719                            if(cptr[1] >= '1' && cptr[1] <= '9')
720                            {
721                                    int idx = cptr[1] - '0';
722                                    regmatch_t *p = &m[idx];
723                                    if(idx < n && !(p->rm_so == -1 || p->rm_so >= p->rm_eo))
724                                    {
725                                            for(i = p->rm_so; i < p->rm_eo; i++)
726                                            {
727                                                    if(strchr("^$.*+\\[{()", ms[i]))
728                                                            add_string_ch('\\');
729                                                    add_string_ch(ms[i]);
730                                            }
731                                    }
732                                    cptr++;
733                            }
734                            else
735                                    add_string_ch('%');
736                    }
737                    else
738                            add_string_ch(*cptr);
739            }
740            return dup_string();
741    }
742    
743    static void find_merges(rcsfile_t *rcs)
744    {
745            int i;
746            int err;
747            int rcflags = REG_EXTENDED | (conf.merge_nocase ? REG_ICASE : 0);
748            regex_t *refrom = NULL;
749            regex_t *reto = NULL;
750            regmatch_t *matchfrom = NULL;
751    
752            if(!conf.merge_from || !conf.merge_from[0] || !conf.merge_to || !conf.merge_to[0])
753                    return;
754    
755            refrom = xmalloc(sizeof(*refrom));
756            reto = xmalloc(sizeof(*reto));
757    
758            /* Compile the 'from' regex match for merge identification */
759            err = regcomp(refrom, conf.merge_from, rcflags);
760            if(err)
761            {
762                    char *msg;
763                    i = regerror(err, refrom, NULL, 0);
764                    msg = xmalloc(i+1);
765                    regerror(err, refrom, msg, i+1);
766                    stack_msg(MSG_WARN, "%s", msg);
767                    xfree(msg);
768                    xfree(refrom);
769                    xfree(reto);
770                    return;
771            }
772            else
773                    matchfrom = xmalloc((refrom->re_nsub+1) * sizeof(*matchfrom));
774    
775            for(i = 0; i < rcs->tags->ntags; i++)
776            {
777                    tag_t *t = rcs->tags->tags[i];
778    
779                    /* Must be revision tags and not detached */
780                    if(t->rev->isbranch || !t->logrev)
781                            continue;
782    
783                    /* Try to find merge tag matches */
784                    if(!regexec(refrom, t->tag, refrom->re_nsub+1, matchfrom, 0))
785                    {
786                            int n;
787                            char *to;
788    
789                            to = build_regex(refrom->re_nsub+1, matchfrom, t->tag);
790                            if(to)
791                            {
792                                    err = regcomp(reto, to, rcflags);
793                                    if(err)
794                                    {
795                                            char *msg;
796                                            i = regerror(err, reto, NULL, 0);
797                                            msg = xmalloc(i+1);
798                                            regerror(err, reto, msg, i+1);
799                                            stack_msg(MSG_WARN, "%s", msg);
800                                            xfree(msg);
801                                    }
802                                    else if(!err)
803                                    {
804                                            for(n = 0; n < rcs->tags->ntags; n++)
805                                            {
806                                                    tag_t *nt = rcs->tags->tags[n];
807                                                    /* From and To never should match the same tag or belong to a branch */
808                                                    if(n == i || nt->rev->isbranch || !nt->logrev)
809                                                            continue;
810    
811                                                    if(!regexec(reto, nt->tag, 0, NULL, 0))
812                                                    {
813                                                            /* Tag matches */
814                                                            rcs->merges = xrealloc(rcs->merges,
815                                                                            sizeof(rcs->merges[0]) * (rcs->nmerges+1));
816                                                            rcs->merges[rcs->nmerges].to = nt;
817                                                            rcs->merges[rcs->nmerges].from = t;
818                                                            rcs->nmerges++;
819                                                            if(!conf.tag_ignore_merge)
820                                                            {
821                                                                    nt->ignore = 0;
822                                                                    t->ignore = 0;
823                                                            }
824                                                            /* We cannot (should not) match multiple times */
825                                                            if(!conf.merge_findall)
826                                                                    break;
827                                                    }
828                                            }
829                                            regfree(reto);
830                                    }
831                                    xfree(to);
832                            }
833                    }
834            }
835            if(matchfrom)   xfree(matchfrom);
836            if(refrom)      { regfree(refrom); xfree(refrom); }
837            if(reto)        xfree(reto);
838    }
839    
840    static void assign_tags(rcsfile_t *rcs)
841    {
842            int i;
843            int nr;
844            regex_t *regextag = NULL;
845    
846            if(conf.tag_ignore && conf.tag_ignore[0])
847            {
848                    int err;
849                    regextag = xmalloc(sizeof(*regextag));
850                    err = regcomp(regextag, conf.tag_ignore, REG_EXTENDED | REG_NOSUB | (conf.tag_nocase ? REG_ICASE : 0));
851                    if(err)
852                    {
853                            char *msg;
854                            i = regerror(err, regextag, NULL, 0);
855                            msg = xmalloc(i+1);
856                            regerror(err, regextag, msg, i+1);
857                            stack_msg(MSG_WARN, "%s", msg);
858                            xfree(msg);
859                            xfree(regextag);
860                            regextag = NULL;
861                    }
862            }
863    
864            for(i = nr = 0; i < rcs->nbranches; i++)
865                    nr += rcs->branches[i]->nrevs;
866    
867            rcs->srev = xmalloc(nr * sizeof(rcs->srev[0]));
868            rcs->nsrev = nr;
869            for(i = nr = 0; i < rcs->nbranches; i++)
870            {
871                    memcpy(&rcs->srev[nr], rcs->branches[i]->revs, rcs->branches[i]->nrevs * sizeof(rcs->branches[i]->revs[0]));
872                    nr += rcs->branches[i]->nrevs;
873            }
874    
875            qsort(rcs->srev, rcs->nsrev, sizeof(rcs->srev[0]), sort_revision);
876            qsort(rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), sort_branch);
877    
878            if(!rcs->branch)
879            {
880                    /* The main trunk is the active trunk */
881                    rcs->tags->tags = xrealloc(rcs->tags->tags, (rcs->tags->ntags+1)*sizeof(rcs->tags->tags[0]));
882                    rcs->tags->tags[rcs->tags->ntags] = xmalloc(sizeof(tag_t));
883                    rcs->tags->tags[rcs->tags->ntags]->tag = xstrdup("MAIN");
884                    rcs->tags->tags[rcs->tags->ntags]->rev = xmalloc(sizeof(rev_t));
885                    rcs->tags->tags[rcs->tags->ntags]->rev->rev = xstrdup(rcs->active->branch->rev);
886                    rcs->tags->tags[rcs->tags->ntags]->rev->branch = xstrdup(rcs->active->branch->branch);
887                    rcs->tags->tags[rcs->tags->ntags]->rev->isbranch = 1;
888                    rcs->tags->ntags++;
889            }
890    
891            /* We should have at least two tags (HEAD and MAIN) */
892            assert(rcs->tags != NULL);
893    
894            for(i = 0; i < rcs->tags->ntags; i++)
895            {
896                    tag_t *t = rcs->tags->tags[i];
897                    if(t->rev->isbranch)
898                    {
899                            branch_t **b;
900    add_btag:
901                            b = bsearch(t->rev, rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), search_branch);
902                            if(!b)
903                            {
904                                    rev_t rev;
905                                    revision_t **r;
906                                    /* This happens for the magic branch numbers if there are
907                                     * no commits within the new branch yet. So, we add the
908                                     * branch and try to continue.
909                                     */
910                                    rev.rev = previous_rev(t->rev->branch);
911                                    rev.branch = NULL;
912                                    rev.isbranch = 0;
913                                    r = bsearch(&rev, rcs->srev, rcs->nsrev, sizeof(rcs->srev[0]), search_revision);
914                                    xfree(rev.rev);
915                                    if(!r)
916                                    {
917                                            stack_msg(MSG_WARN, "No branch found for tag '%s:%s'", t->tag, t->rev->branch);
918                                    }
919                                    else
920                                    {
921                                            rcs->branches = xrealloc(rcs->branches, (rcs->nbranches+1)*sizeof(rcs->branches[0]));
922                                            rcs->branches[rcs->nbranches] = xmalloc(sizeof(branch_t));
923                                            rcs->branches[rcs->nbranches]->branch = dup_rev(t->rev);
924                                            rcs->branches[rcs->nbranches]->branchpoint = *r;
925                                            (*r)->branches = xrealloc((*r)->branches, ((*r)->nbranches+1)*sizeof((*r)->branches[0]));
926                                            (*r)->branches[(*r)->nbranches] = rcs->branches[rcs->nbranches];
927                                            (*r)->nbranches++;
928                                            rcs->nbranches++;
929                                            /* Resort the branches */
930                                            qsort(rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), sort_branch);
931                                            goto add_btag;
932                                    }
933                            }
934                            else
935                            {
936                                    branch_t *bb = *b;
937                                    bb->tags = xrealloc(bb->tags, (bb->ntags+1)*sizeof(bb->tags[0]));
938                                    bb->tags[bb->ntags] = t;
939                                    bb->ntags++;
940                            }
941                    }
942                    else
943                    {
944                            revision_t **r = bsearch(t->rev, rcs->srev, rcs->nsrev, sizeof(rcs->srev[0]), search_revision);
945                            if(!r)
946                            {
947                                    stack_msg(MSG_WARN, "No revision found for tag '%s:%s'\n", t->tag, t->rev->rev);
948                            }
949                            else
950                            {
951                                    revision_t *rr = *r;
952                                    t->logrev = rr;
953                                    if(!conf.rev_maxtags || rr->ntags <= conf.rev_maxtags)
954                                    {
955                                            rr->tags = xrealloc(rr->tags, (rr->ntags+1)*sizeof(rr->tags[0]));
956                                            if(conf.rev_maxtags && rr->ntags == conf.rev_maxtags)
957                                            {
958                                                    rr->tags[rr->ntags] = xmalloc(sizeof(tag_t));
959                                                    rr->tags[rr->ntags]->tag = xstrdup("...");
960                                                    rr->tags[rr->ntags]->rev = t->rev;
961                                            }
962                                            else
963                                                    rr->tags[rr->ntags] = t;
964                                            rr->ntags++;
965                                    }
966                            }
967    
968                            if(conf.tag_negate)
969                                    t->ignore++;
970                            /* Mark the tag ignored if it matches the configuration */
971                            if(regextag && !regexec(regextag, t->tag, 0, NULL, 0))
972                            {
973                                    if(conf.tag_negate)
974                                            t->ignore--;
975                                    else
976                                            t->ignore++;
977                            }
978                    }
979            }
980    
981            /* We need to reset the first in the list of branches to the
982             * active branch to ensure the drawing of all
983             */
984            if(rcs->active != rcs->branches[0])
985            {
986                    branch_t **b = bsearch(rcs->active->branch, rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), search_branch);
987                    branch_t *t;
988                    assert(b != NULL);
989                    t = *b;
990                    *b = rcs->branches[0];
991                    rcs->branches[0] = t;
992            }
993    
994            if(regextag)
995            {
996                    regfree(regextag);
997                    xfree(regextag);
998            }
999    }
1000    
1001    /*
1002     **************************************************************************
1003     * String expansion
1004     **************************************************************************
1005     */
1006    static char *_string;
1007    static int _nstring;
1008    static int _nastring;
1009    
1010    static void zap_string(void)
1011    {
1012            _nstring = 0;
1013            if(_string)
1014                    _string[0] = '\0';
1015    }
1016    
1017    static char *dup_string(void)
1018    {
1019            if(_string)
1020                    return xstrdup(_string);
1021            else
1022                    return "";
1023    }
1024    
1025    static void add_string_str(const char *s)
1026    {
1027            int l = strlen(s) + 1;
1028            if(_nstring + l > _nastring)
1029            {
1030                    _nastring += MAX(128, l);
1031                    _string = xrealloc(_string, _nastring * sizeof(_string[0]));
1032            }
1033            memcpy(_string+_nstring, s, l);
1034            _nstring += l-1;
1035    }
1036    
1037    static void add_string_ch(int ch)
1038    {
1039            char buf[2];
1040            buf[0] = ch;
1041            buf[1] = '\0';
1042            add_string_str(buf);
1043    }
1044    
1045    static void add_string_date(const char *d)
1046    {
1047            struct tm tm, *tmp;
1048            int n;
1049            time_t t;
1050            char *buf;
1051            int nbuf;
1052    
1053            memset(&tm, 0, sizeof(tm));
1054            n = sscanf(d, "%d.%d.%d.%d.%d.%d",
1055                            &tm.tm_year, &tm.tm_mon, &tm.tm_mday,
1056                            &tm.tm_hour, &tm.tm_min, &tm.tm_sec);
1057            tm.tm_mon--;
1058            if(tm.tm_year > 1900)
1059                    tm.tm_year -= 1900;
1060            t = mktime(&tm) - timezone;
1061            if(n != 6 || t == (time_t)(-1))
1062            {
1063                    add_string_str("<invalid date>");
1064                    return;
1065            }
1066    
1067            tmp = localtime(&t);
1068            nbuf = strlen(conf.date_format) * 16;   /* Should be enough to hold all types of expansions */
1069            buf = xmalloc(nbuf);
1070            strftime(buf, nbuf, conf.date_format, tmp);
1071            add_string_str(buf);
1072            xfree(buf);
1073    }
1074    
1075    static void add_string_str_html(const char *s, int maxlen)
1076    {
1077            int l = 0;
1078            char *str = xmalloc(6 * strlen(s) + 1); /* Should hold all char entity-expand */
1079            char *cptr = str;
1080            for(; *s; s++)
1081            {
1082                    if(maxlen && l > abs(maxlen))
1083                    {
1084                            cptr += sprintf(cptr, "...");
1085                            break;
1086                    }
1087                    if(*s < 0x20)
1088                    {
1089                            if(*s == '\n')
1090                            {
1091                                    if(maxlen < 0)
1092                                            *cptr++ = ' ';
1093                                    else
1094                                            cptr += sprintf(cptr, "<br%s>", conf.html_level == HTMLLEVEL_X ? " /" : "");
1095                            }
1096                    }
1097                    else if(*s >= 0x7f || *s == '"')
1098                            cptr += sprintf(cptr, "&#%d;", (int)(unsigned char)*s);
1099                    else if(*s == '<')
1100                            cptr += sprintf(cptr, "&lt;");
1101                    else if(*s == '>')
1102                            cptr += sprintf(cptr, "&gt;");
1103                    else if(*s == '&')
1104                            cptr += sprintf(cptr, "&amp;");
1105                    else if(*s == '"')
1106                            cptr += sprintf(cptr, "&quot;");
1107                    else
1108                            *cptr++ = *s;
1109                    l++;
1110            }
1111            *cptr = '\0';
1112            add_string_str(str);
1113            xfree(str);
1114    }
1115    
1116    static void add_string_str_len(const char *s, int maxlen)
1117    {
1118            int l = strlen(s);
1119            char *str = xmalloc(l + 1 + 3);
1120            strcpy(str, s);
1121            if(maxlen < l)
1122                    sprintf(&str[maxlen], "...");
1123            add_string_str(str);
1124            xfree(str);
1125    }
1126    
1127    static char *expand_string(const char *s, rcsfile_t *rcs, revision_t *r, rev_t *rev, rev_t *prev, tag_t *tag)
1128    {
1129            char nb[32];
1130            char nr[32];
1131            char *base;
1132            char *exp;
1133            int l;
1134            char ch;
1135    
1136            if(!s)
1137                    return xstrdup("");
1138    
1139            zap_string();
1140    
1141            sprintf(nb, "%d", rcs->nbranches);
1142            sprintf(nr, "%d", rcs->nsrev);
1143            for(; *s; s++)
1144            {
1145                    if(*s == '%')
1146                    {
1147                            switch(*++s)
1148                            {
1149                            case 'c':
1150                            case 'C':
1151                                    add_string_str(conf.cvsroot);
1152                                    if(*s == 'C' && conf.cvsroot[0] && conf.cvsroot[strlen(conf.cvsroot)-1] == '/')
1153                                    {
1154                                            /* Strip the trailing '/' */
1155                                            _nstring--;
1156                                            _string[_nstring] = '\0';
1157                                    }
1158                                    break;
1159                            case 'f':
1160                            case 'F':
1161                                    base = strrchr(rcs->file, '/');
1162                                    if(!base)
1163                                            add_string_str(rcs->file);
1164                                    else
1165                                            add_string_str(base+1);
1166                                    if(*s == 'F' && _string[_nstring-1] == 'v' && _string[_nstring-2] == ',')
1167                                    {
1168                                            _nstring -= 2;
1169                                            _string[_nstring] = '\0';
1170                                    }
1171                                    break;
1172                            case 'p':
1173                                    base = strrchr(rcs->file, '/');
1174                                    if(base)
1175                                    {
1176                                            char *c = xstrdup(rcs->file);
1177                                            base = strrchr(c, '/');
1178                                            assert(base != NULL);
1179                                            base[1] = '\0';
1180                                            add_string_str(c);
1181                                            xfree(c);
1182                                    }
1183                                    /*
1184                                     * We should not add anything here because we can encounter
1185                                     * a completely empty path, in which case we do not want
1186                                     * to add any slash. This prevents an inadvertent root redirect.
1187                                     *
1188                                     * else
1189                                     *      add_string_str("/");
1190                                     */
1191                                    break;
1192                            case 'm':
1193                            case 'M':
1194                                    add_string_str(conf.cvsmodule);
1195                                    if(*s == 'M' && conf.cvsmodule[0] && conf.cvsmodule[strlen(conf.cvsmodule)-1] == '/')
1196                                    {
1197                                            /* Strip the trailing '/' */
1198                                            _nstring--;
1199                                            _string[_nstring] = '\0';
1200                                    }
1201                                    break;
1202                            case 'r': add_string_str(nr); break;
1203                            case 'b': add_string_str(nb); break;
1204                            case '%': add_string_ch('%'); break;
1205                            case '0': if(conf.expand[0]) add_string_str(conf.expand[0]); break;
1206                            case '1': if(conf.expand[1]) add_string_str(conf.expand[1]); break;
1207                            case '2': if(conf.expand[2]) add_string_str(conf.expand[2]); break;
1208                            case '3': if(conf.expand[3]) add_string_str(conf.expand[3]); break;
1209                            case '4': if(conf.expand[4]) add_string_str(conf.expand[4]); break;
1210                            case '5': if(conf.expand[5]) add_string_str(conf.expand[5]); break;
1211                            case '6': if(conf.expand[6]) add_string_str(conf.expand[6]); break;
1212                            case '7': if(conf.expand[7]) add_string_str(conf.expand[7]); break;
1213                            case '8': if(conf.expand[8]) add_string_str(conf.expand[8]); break;
1214                            case '9': if(conf.expand[9]) add_string_str(conf.expand[9]); break;
1215                            case 'R': if(rev && rev->rev) add_string_str(rev->rev); break;
1216                            case 'P': if(prev && prev->rev) add_string_str(prev->rev); break;
1217                            case 'B': if(rev && rev->branch) add_string_str(rev->branch); break;
1218                            case 't': if(tag && tag->tag) add_string_str(tag->tag); break;
1219                            case 'd': if(r && r->delta && r->delta->date) add_string_date(r->delta->date); break;
1220                            case 's': if(r && r->delta && r->delta->state) add_string_str(r->delta->state); break;
1221                            case 'a': if(r && r->delta && r->delta->author) add_string_str(r->delta->author); break;
1222                            case 'L':
1223                            case 'l':
1224                                    ch = *s;
1225                                    l = 0;
1226                                    if(s[1] == '[')
1227                                    {
1228                                            char *cptr = strchr(s, ']');
1229                                            char *eptr;
1230                                            if(cptr)
1231                                            {
1232                                                    l = strtol(&s[2], &eptr, 10);
1233                                                    if(eptr != cptr)
1234                                                            l = 0;
1235                                                    else
1236                                                            s = cptr;
1237                                            }
1238                                    }
1239                                    if(!conf.parse_logs)
1240                                            add_string_str("N/A");
1241                                    else if(r && r->dtext && r->dtext->log)
1242                                    {
1243                                            if(ch == 'l')
1244                                                    add_string_str_html(r->dtext->log, l);
1245                                            else
1246                                                    add_string_str_len(r->dtext->log, abs(l));
1247                                    }
1248                                    break;
1249                            case '(':
1250                                    base = dup_string();
1251                                    exp = expand_string(s+1, rcs, r, rev, prev, tag);
1252                                    zap_string();
1253                                    add_string_str(base);
1254                                    add_string_str_html(exp, 0);
1255                                    xfree(base);
1256                                    xfree(exp);
1257                                    /* Find the %) in this recursion level */
1258                                    for(; *s; s++)
1259                                    {
1260                                            if(*s == '%' && s[1] == ')')
1261                                            {
1262                                                    s++;
1263                                                    break;
1264                                            }
1265                                    }
1266                                    if(!*s)
1267                                    {
1268                                            s--;    /* To end outer loop */
1269                                            stack_msg(MSG_WARN, "string expand: Missing %%) in expansion");
1270                                    }
1271                                    break;
1272                            case ')':
1273                                    return dup_string();
1274                            default:
1275                                    add_string_ch('%');
1276                                    add_string_ch(*s);
1277                                    break;
1278                            }
1279                    }
1280                    else
1281                            add_string_ch(*s);
1282            }
1283            return dup_string();
1284    }
1285    
1286    /*
1287     **************************************************************************
1288     * Drawing routines
1289     **************************************************************************
1290     */
1291    static int get_swidth(const char *s, font_t *f)
1292    {
1293            int n;
1294            int m;
1295            if(!s || !*s)
1296                    return 0;
1297    
1298    #if defined(HAVE_GDIMAGESTRINGFT) || defined(HAVE_GDIMAGESTRINGTTF)
1299            if(conf.use_ttf && f->ttfont)
1300            {
1301                    int bb[8];
1302                    char *e;
1303    #ifdef HAVE_GDIMAGESTRINGFT
1304                    e = gdImageStringFT(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1305    #else
1306                    e = gdImageStringTTF(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1307    #endif
1308                    if(!e)
1309                            return bb[2] - bb[6];
1310            }
1311    #endif
1312            for(n = m = 0; *s; n++, s++)
1313            {
1314                    if(*s == '\n')
1315                    {
1316                            if(n > m)
1317                                    m = n;
1318                            n = 0;
1319                    }
1320            }
1321            if(n > m)
1322                    m = n;
1323            return f->gdfont ? m * f->gdfont->w : m;
1324    }
1325    
1326    static int get_sheight(const char *s, font_t *f)
1327    {
1328            int nl;
1329            if(!s || !*s)
1330                    return 0;
1331    
1332    #if defined(HAVE_GDIMAGESTRINGFT) || defined(HAVE_GDIMAGESTRINGTTF)
1333            if(conf.use_ttf && f->ttfont)
1334            {
1335                    int bb[8];
1336                    char *e;
1337    #ifdef HAVE_GDIMAGESTRINGFT
1338                    e = gdImageStringFT(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1339    #else
1340                    e = gdImageStringTTF(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1341    #endif
1342                    if(!e)
1343                            return bb[3] - bb[7] + 4;
1344            }
1345    #endif
1346            for(nl = 1; *s; s++)
1347            {
1348                    if(*s == '\n' && s[1])
1349                            nl++;
1350            }
1351            return nl * f->gdfont->h;
1352    }
1353    
1354    static void draw_rbox(gdImagePtr im, int x1, int y1, int x2, int y2, int r, color_t *color, color_t *bgcolor)
1355    {
1356            int r2 = 2*r;
1357            if(!r)
1358                    gdImageFilledRectangle(im, x1, y1, x2, y2, bgcolor->id);
1359    #ifdef HAVE_GDIMAGEFILLEDARC
1360            else
1361            {
1362                    gdImageFilledArc(im, x1+r, y1+r, r2, r2, 180, 270, bgcolor->id, gdArc);
1363                    gdImageFilledArc(im, x2-r, y1+r, r2, r2, 270, 360, bgcolor->id, gdArc);
1364                    gdImageFilledArc(im, x1+r, y2-r, r2, r2,  90, 180, bgcolor->id, gdArc);
1365                    gdImageFilledArc(im, x2-r, y2-r, r2, r2,   0,  90, bgcolor->id, gdArc);
1366                    gdImageFilledRectangle(im, x1+r, y1, x2-r, y1+r, bgcolor->id);
1367                    gdImageFilledRectangle(im, x1, y1+r, x2, y2-r, bgcolor->id);
1368                    gdImageFilledRectangle(im, x1+r, y2-r, x2-r, y2, bgcolor->id);
1369            }
1370    #endif
1371            gdImageLine(im, x1+r, y1, x2-r, y1, color->id);
1372            gdImageLine(im, x1+r, y2, x2-r, y2, color->id);
1373            gdImageLine(im, x1, y1+r, x1, y2-r, color->id);
1374            gdImageLine(im, x2, y1+r, x2, y2-r, color->id);
1375            if(conf.box_shadow)
1376            {
1377                    gdImageLine(im, x1+r+1, y2+1, x2-r, y2+1, black_color.id);
1378                    gdImageLine(im, x2+1, y1+r+1, x2+1, y2-r, black_color.id);
1379            }
1380            if(r)
1381            {
1382                    /* FIXME: Pixelization is not perfect */
1383                    gdImageArc(im, x1+r, y1+r, r2, r2, 180, 270, color->id);
1384                    gdImageArc(im, x2-r, y1+r, r2, r2, 270, 360, color->id);
1385                    gdImageArc(im, x1+r, y2-r, r2, r2,  90, 180, color->id);
1386                    if(conf.box_shadow)
1387                    {
1388                            gdImageArc(im, x2-r+1, y2-r+1, r2, r2,   0,  90, black_color.id);
1389                            gdImageArc(im, x2-r+1, y2-r, r2, r2,   0,  90, black_color.id);
1390                            gdImageArc(im, x2-r, y2-r+1, r2, r2,   0,  90, black_color.id);
1391                    }
1392                    gdImageArc(im, x2-r, y2-r, r2, r2,   0,  90, color->id);
1393    #if !defined(NOGDFILL) && !defined(HAVE_GDIMAGEFILLEDARC)
1394                    /* BUG: We clip manually because libgd segfaults on out of bound values */
1395                    if((x1+x2)/2 >= 0 && (x1+x2)/2 < gdImageSX(im) && (y1+y2)/2 >= 0 && (y1+y2)/2 < gdImageSY(im))
1396                            gdImageFillToBorder(im, (x1+x2)/2, (y1+y2)/2, color->id, bgcolor->id);
1397    #endif
1398            }
1399    }
1400    
1401    static void draw_string(gdImagePtr im, char *s, font_t *f, int x, int y, int align, color_t *c)
1402    {
1403            int h = get_sheight(s, f);
1404            int xx, yy;
1405            switch(align & ALIGN_HX)
1406            {
1407            default:
1408            case ALIGN_HL: xx = 0; break;
1409            case ALIGN_HC: xx = -get_swidth(s, f)/2; break;
1410            case ALIGN_HR: xx = -get_swidth(s, f); break;
1411            }
1412            switch(align & ALIGN_VX)
1413            {
1414            default:
1415            case ALIGN_VT: yy = 0; break;
1416            case ALIGN_VC: yy = h/2; break;
1417            case ALIGN_VB: yy = h; break;
1418            }
1419    #if defined(HAVE_GDIMAGESTRINGFT) || defined(HAVE_GDIMAGESTRINGTTF)
1420            if(conf.use_ttf && f->ttfont)
1421            {
1422                    int bb[8];
1423                    char *e;
1424                    int cid = conf.anti_alias ? c->id : -c->id;
1425    #ifdef HAVE_GDIMAGESTRINGFT
1426                    e = gdImageStringFT(im, bb, cid, f->ttfont, f->ttsize, 0.0, x+xx, y+yy+h-2, (char *)s);
1427    #else
1428                    e = gdImageStringTTF(im, bb, cid, f->ttfont, f->ttsize, 0.0, x+xx, y+yy+h-2, (char *)s);
1429    #endif
1430                    if(!e)
1431                            return;
1432            }
1433    #endif
1434            yy = -yy;
1435            gdImageString(im, f->gdfont, x+xx+1, y+yy, s, c->id);
1436    }
1437    
1438    static void draw_stringnl(gdImagePtr im, char *s, font_t *f, int x, int y, int align, color_t *c)
1439    {
1440            char *t;
1441            char *d;
1442            d = s = xstrdup(s);
1443            do
1444            {
1445                    t = strchr(s, '\n');
1446                    if(t)
1447                            *t = '\0';
1448                    draw_string(im, s, f, x, y, align, c);
1449                    y += get_sheight(s, f);
1450                    s = t+1;
1451            } while(t);
1452            xfree(d);
1453    }
1454    
1455    static void draw_rev(gdImagePtr im, revision_t *r)
1456    {
1457            int lx;
1458            int rx;
1459            int x2;
1460            int i;
1461            int ty;
1462    
1463            if(conf.left_right)
1464            {
1465                    lx = r->cx;
1466                    rx = r->cx + r->w;
1467                    ty = r->y - r->h/2;
1468                    x2 = r->cx + r->w/2;
1469            }
1470            else
1471            {
1472                    lx = r->cx - r->w/2;
1473                    rx = lx + r->w;
1474                    ty = r->y;
1475                    x2 = r->cx;
1476            }
1477            draw_rbox(im, lx, ty, rx, ty+r->h, 0, &conf.rev_color, &conf.rev_bgcolor);
1478            ty += conf.rev_tspace;
1479            if(!conf.rev_hidenumber)
1480            {
1481                    draw_string(im, r->rev->rev, &conf.rev_font, x2, ty, ALIGN_HC, &conf.rev_color);
1482                    ty += get_sheight(r->rev->rev, &conf.rev_font);
1483            }
1484            draw_stringnl(im, r->revtext, &conf.rev_text_font, x2, ty, ALIGN_HC, &conf.rev_text_color);
1485            ty += get_sheight(r->revtext, &conf.rev_text_font);
1486            for(i = 0; i < r->ntags; i++)
1487            {
1488                    draw_string(im, r->tags[i]->tag, &conf.tag_font, x2, ty, ALIGN_HC, &conf.tag_color);
1489                    ty += get_sheight(r->tags[i]->tag, &conf.tag_font) + conf.rev_separator;
1490            }
1491    }
1492    
1493    static void draw_branch_box(gdImagePtr im, branch_t *b, int xp, int yp)
1494    {
1495            int lx;
1496            int rx;
1497            int i;
1498            int yy;
1499            int x2;
1500    
1501            if(conf.left_right)
1502            {
1503                    lx = b->cx;
1504                    rx = lx + b->w;
1505                    x2 = b->cx + b->w/2;
1506            }
1507            else
1508            {
1509                    lx = b->cx - b->w/2;
1510                    rx = lx + b->w;
1511                    x2 = b->cx;
1512            }
1513            draw_rbox(im, lx+xp, yp, rx+xp, yp+b->h, 5, &conf.branch_color, &conf.branch_bgcolor);
1514            yy = conf.branch_tspace;
1515            if(!b->nfolds)
1516            {
1517                    if(!conf.rev_hidenumber)
1518                    {
1519                            draw_string(im, b->branch->branch, &conf.branch_font, x2+xp, yp+yy, ALIGN_HC, &conf.branch_color);
1520                            yy += get_sheight(b->branch->branch, &conf.branch_font);
1521                    }
1522                    for(i = 0; i < b->ntags; i++)
1523                    {
1524                            draw_string(im, b->tags[i]->tag, &conf.branch_tag_font, x2+xp, yp+yy, ALIGN_HC, &conf.branch_tag_color);
1525                            yy += get_sheight(b->tags[i]->tag, &conf.branch_tag_font);
1526                    }
1527            }
1528            else
1529            {
1530                    int y1, y2;
1531                    int tx = lx + b->fw + conf.branch_lspace;
1532                    int nx = tx - get_swidth(" ", &conf.branch_font);
1533                    draw_string(im, b->branch->branch, &conf.branch_font, nx+xp, yp+yy, ALIGN_HR, &conf.branch_color);
1534                    y1 = get_sheight(b->branch->branch, &conf.branch_font);
1535                    draw_string(im, b->tags[0]->tag, &conf.branch_tag_font, tx+xp, yp+yy, ALIGN_HL, &conf.branch_tag_color);
1536                    y2 = get_sheight(b->tags[0]->tag, &conf.branch_font);
1537                    yy += MAX(y1, y2);
1538                    for(i = 0; i < b->nfolds; i++)
1539                    {
1540                            draw_string(im, b->folds[i]->branch->branch, &conf.branch_font, nx+xp, yp+yy, ALIGN_HR, &conf.branch_color);
1541                            y1 = get_sheight(b->folds[i]->branch->branch, &conf.branch_font);
1542                            draw_string(im, b->folds[i]->tags[0]->tag, &conf.branch_tag_font, tx+xp, yp+yy, ALIGN_HL, &conf.branch_tag_color);
1543                            y2 = get_sheight(b->folds[i]->tags[0]->tag, &conf.branch_tag_font);
1544                            yy += MAX(y1, y2);
1545                    }
1546            }
1547    }
1548    
1549    static void draw_branch(gdImagePtr im, branch_t *b)
1550    {
1551            int yy, xx;
1552            int i;
1553            int line[4];
1554            int l;
1555            int sign;
1556    
1557            line[0] = conf.rev_color.id;
1558            line[1] = gdTransparent;
1559            line[1] = gdTransparent;
1560            line[3] = conf.rev_color.id;
1561    
1562            /* Trivial clip the branch */
1563            if(conf.left_right)
1564            {
1565                    if(b->cx > gdImageSX(im) || b->cx+b->tw < 0 || b->y-b->th/2 > gdImageSY(im) || b->y+b->th/2 < 0)
1566                            return;
1567            }
1568            else
1569            {
1570                    if(b->cx-b->tw/2 > gdImageSX(im) || b->cx+b->tw/2 < 0 || b->y > gdImageSY(im) || b->y+b->th < 0)
1571                            return;
1572            }
1573    
1574            draw_branch_box(im, b, 0, conf.left_right ? b->y - b->h/2 : b->y);
1575    
1576            if(conf.left_right)
1577            {
1578                    if(conf.upside_down)
1579                    {
1580                            xx = b->cx;
1581                            for(i = 0; i < b->nrevs; i++)
1582                            {
1583                                    revision_t *r = b->revs[i];
1584                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1585                                    gdImageLine(im, xx, r->y, r->cx+r->w, r->y, gdStyled);
1586                                    for(sign = l = 1; l < conf.thick_lines; l++)
1587                                    {
1588                                            int pp = (l+1)/2*sign;
1589                                            gdImageLine(im, xx, r->y+pp, r->cx+r->w, r->y+pp, gdStyled);
1590                                            sign *= -1;
1591                                    }
1592                                    draw_rev(im, r);
1593                                    xx = r->cx;
1594                            }
1595                            if(conf.branch_dupbox && b->nrevs)
1596                            {
1597                                    i = b->cx - b->tw + b->w;
1598                                    gdImageLine(im, xx, b->y, i+b->w, b->y, conf.rev_color.id);
1599                                    for(sign = l = 1; l < conf.thick_lines; l++)
1600                                    {
1601                                            int pp = (l+1)/2*sign;
1602                                            gdImageLine(im, xx, b->y+pp, i+b->w, b->y+pp, conf.rev_color.id);
1603                                            sign *= -1;
1604                                    }
1605                                    draw_branch_box(im, b, i - b->cx, b->y - b->h/2);
1606                            }
1607                    }
1608                    else
1609                    {
1610                            xx = b->cx + b->w;
1611                            for(i = 0; i < b->nrevs; i++)
1612                            {
1613                                    revision_t *r = b->revs[i];
1614                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1615                                    gdImageLine(im, xx, r->y, r->cx, r->y, gdStyled);
1616                                    for(sign = l = 1; l < conf.thick_lines; l++)
1617                                    {
1618                                            int pp = (l+1)/2*sign;
1619                                            gdImageLine(im, xx, r->y+pp, r->cx, r->y+pp, gdStyled);
1620                                            sign *= -1;
1621                                    }
1622                                    draw_rev(im, r);
1623                                    xx = r->cx + r->w;
1624                            }
1625                            if(conf.branch_dupbox && b->nrevs)
1626                            {
1627                                    i = b->cx + b->tw - b->w;
1628                                    gdImageLine(im, xx, b->y, i, b->y, conf.rev_color.id);
1629                                    for(sign = l = 1; l < conf.thick_lines; l++)
1630                                    {
1631                                            int pp = (l+1)/2*sign;
1632                                            gdImageLine(im, xx, b->y+pp, i, b->y+pp, conf.rev_color.id);
1633                                            sign *= -1;
1634                                    }
1635                                    draw_branch_box(im, b, i - b->cx, b->y - b->h/2);
1636                            }
1637                    }
1638            }
1639            else
1640            {
1641                    if(conf.upside_down)
1642                    {
1643                            yy = b->y;
1644                            for(i = 0; i < b->nrevs; i++)
1645                            {
1646                                    revision_t *r = b->revs[i];
1647                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1648                                    gdImageLine(im, r->cx, yy, r->cx, r->y+r->h, gdStyled);
1649                                    for(sign = l = 1; l < conf.thick_lines; l++)
1650                                    {
1651                                            int pp = (l+1)/2*sign;
1652                                            gdImageLine(im, r->cx+pp, yy, r->cx+pp, r->y+r->h, gdStyled);
1653                                            sign *= -1;
1654                                    }
1655                                    draw_rev(im, r);
1656                                    yy = r->y;
1657                            }
1658                            if(conf.branch_dupbox && b->nrevs)
1659                            {
1660                                    i = b->y - b->th + b->h;
1661                                    gdImageLine(im, b->cx, yy, b->cx, i, conf.rev_color.id);
1662                                    for(sign = l = 1; l < conf.thick_lines; l++)
1663                                    {
1664                                            int pp = (l+1)/2*sign;
1665                                            gdImageLine(im, b->cx+pp, yy, b->cx+pp, i, conf.rev_color.id);
1666                                            sign *= -1;
1667                                    }
1668                                    draw_branch_box(im, b, 0, i);
1669                            }
1670                    }
1671                    else
1672                    {
1673                            yy = b->y + b->h;
1674                            for(i = 0; i < b->nrevs; i++)
1675                            {
1676                                    revision_t *r = b->revs[i];
1677                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1678                                    gdImageLine(im, r->cx, yy, r->cx, r->y, gdStyled);
1679                                    for(sign = l = 1; l < conf.thick_lines; l++)
1680                                    {
1681                                            int pp = (l+1)/2*sign;
1682                                            gdImageLine(im, r->cx+pp, yy, r->cx+pp, r->y, gdStyled);
1683                                            sign *= -1;
1684                                    }
1685                                    draw_rev(im, r);
1686                                    yy = r->y + r->h;
1687                            }
1688                            if(conf.branch_dupbox && b->nrevs)
1689                            {
1690                                    i = b->y + b->th - b->h;
1691                                    gdImageLine(im, b->cx, yy, b->cx, i, conf.rev_color.id);
1692                                    for(sign = l = 1; l < conf.thick_lines; l++)
1693                                    {
1694                                            int pp = (l+1)/2*sign;
1695                                            gdImageLine(im, b->cx+pp, yy, b->cx+pp, i, conf.rev_color.id);
1696                                            sign *= -1;
1697                                    }
1698                                    draw_branch_box(im, b, 0, i);
1699                            }
1700                    }
1701            }
1702    }
1703    
1704    static void draw_connector(gdImagePtr im, branch_t *b)
1705    {
1706            int l;
1707            int sign;
1708            revision_t *r = b->branchpoint;
1709            int x1 = r->cx + r->w/2 + 2;
1710            int y1 = r->y + r->h/2;
1711            int x2 = b->cx;
1712            int y2 = b->y;
1713    
1714            if(conf.left_right)
1715            {
1716                    x2 = r->cx + r->w/2;
1717                    y2 = r->y + r->h/2 + 3;
1718                    x1 = b->cx;
1719                    y1 = b->y;
1720                    if(conf.upside_down)
1721                            x1 += b->w;
1722            }
1723            else
1724            {
1725                    x1 = r->cx + r->w/2 + 2;
1726                    y1 = r->y + r->h/2;
1727                    x2 = b->cx;
1728                    y2 = b->y;
1729                    if(conf.upside_down)
1730                            y2 += b->h;
1731            }
1732            gdImageLine(im, x1, y1, x2, y1, conf.branch_color.id);
1733            gdImageLine(im, x2, y1, x2, y2, conf.branch_color.id);
1734            for(sign = l = 1; l < conf.thick_lines; l++)
1735            {
1736                    int pp = (l+1)/2*sign;
1737                    gdImageLine(im, x1, y1+pp, x2, y1+pp, conf.branch_color.id);
1738                    gdImageLine(im, x2+pp, y1, x2+pp, y2, conf.branch_color.id);
1739                    sign *= -1;
1740            }
1741    }
1742    
1743    static void draw_merges(gdImagePtr im, rcsfile_t *rcs, int dot)
1744    {
1745            int i;
1746            for(i = 0; i < rcs->nmerges; i++)
1747            {
1748                    revision_t *fr = rcs->merges[i].from->logrev;
1749                    revision_t *tr = rcs->merges[i].to->logrev;
1750                    int x1, x2, y1, y2;
1751                    if(!fr || !tr || fr == tr)
1752                            continue;       /* This can happen with detached tags and self-references */
1753                    if(conf.left_right)
1754                    {
1755                            if(fr->branch == tr->branch)
1756                            {
1757                                    y1 = fr->y - fr->h/2;
1758                                    y2 = tr->y - tr->h/2;
1759                            }
1760                            else
1761                            {
1762                                    if(fr->y < tr->y)
1763                                    {
1764                                            y1 = fr->y + fr->h/2;
1765                                            y2 = tr->y - tr->h/2;
1766                                    }
1767                                    else
1768                                    {
1769                                            y1 = fr->y - fr->h/2;
1770                                            y2 = tr->y + tr->h/2;
1771                                    }
1772                            }
1773                            x1 = fr->cx + fr->w/2;
1774                            x2 = tr->cx + tr->w/2;
1775                    }
1776                    else
1777                    {
1778                            if(fr->branch == tr->branch)
1779                            {
1780                                    x1 = fr->cx - fr->w/2;
1781                                    x2 = tr->cx - tr->w/2;
1782                            }
1783                            else
1784                            {
1785                                    if(fr->cx < tr->cx)
1786                                    {
1787                                            x1 = fr->cx + fr->w/2;
1788                                            x2 = tr->cx - tr->w/2;
1789                                    }
1790                                    else
1791                                    {
1792                                            x1 = fr->cx - fr->w/2;
1793                                            x2 = tr->cx + tr->w/2;
1794                                    }
1795                            }
1796                            y1 = fr->y + rcs->merges[i].from->yofs;
1797                            y2 = tr->y + rcs->merges[i].to->yofs;
1798                    }
1799                    if(dot && !conf.merge_arrows)
1800                    {
1801                            int o = conf.left_right ? 1 : 0;
1802                            gdImageArc(im, x2, y2+o, 8, 8, 0, 360, conf.merge_color.id);
1803                            /* BUG: We clip manually because libgd segfaults on out of bound values */
1804                            if(x2+1 >= 0 && x2+1 < gdImageSX(im) && y2+o+1 >= 0 && y2+o+1 < gdImageSY(im))
1805                                    gdImageFillToBorder(im, x2+1, y2+o+1, conf.merge_color.id, conf.merge_color.id);
1806                    }
1807                    else if(dot && conf.merge_arrows)
1808                    {
1809                            /*
1810                             * Arrow patch from Haroon Rafique <haroon.rafique@utoronto.ca>
1811                             * Slightly adapted to be more configurable.
1812                             */
1813                            int sx, sy;     /* start point coordinates */
1814                            int ex, ey;     /* end point coordinates */
1815                            double theta;
1816                            double u1, v1, u2, v2;
1817                            gdPoint p[3];
1818    
1819                            sx = x1; sy = y1;
1820                            ex = x2; ey = y2;
1821                            if(conf.left_right)
1822                            {
1823                                    if(fr->branch == tr->branch)
1824                                    {
1825                                            int yy = (y1 < y2 ? y1 : y2) - 5;
1826                                            /* line from (x1,yy) to (x2,yy) */
1827                                            sy = ey = yy;
1828                                    }
1829                                    else
1830                                    {
1831                                            if(y1 > y2)
1832                                            {
1833                                                    /* line from (x1,y1-3) to (x2,y2+3+1) */
1834                                                    sy = y1-3;
1835                                                    ey = y2+3+1;
1836                                            }
1837                                            else
1838                                            {
1839                                                    /* line from (x1,y1+3+1) to (x2,y2-3) */
1840                                                    sy = y1+3+1;
1841                                                    ey = y2-3;
1842                                            }
1843                                    }
1844                            }
1845                            else
1846                            {
1847                                    if(fr->branch == tr->branch)
1848                                    {
1849                                            int xx = (x1 < x2 ? x1 : x2) - 5;
1850                                            /* line from (xx,y1) to (xx,y2) */
1851                                            sx = ex = xx;
1852                                    }
1853                                    else
1854                                    {
1855                                            if(x1 > x2)
1856                                            {
1857                                                    /* line from (x1-3,y1) to (x2+3,y2) */
1858                                                    sx = x1-3;
1859                                                    ex = x2+3;
1860                                            }
1861                                            else
1862                                            {
1863                                                    /* line from (x1+3,y1) to (x2-3,y2) */
1864                                                    sx = x1+3;
1865                                                    ex = x2-3;
1866                                            }
1867                                    }
1868                            }
1869                            /*
1870                             * inspiration for arrow code comes from arrows.c in the
1871                             * graphviz package. Thank you, AT&T
1872                             */
1873                            /* theta in radians */
1874                            theta = atan2((double)(sy-ey), (double)(sx-ex));
1875                            u1 = (double)conf.arrow_length * cos(theta);
1876                            v1 = (double)conf.arrow_length * sin(theta);
1877                            u2 = (double)conf.arrow_width  * cos(theta + M_PI/2.0);
1878                            v2 = (double)conf.arrow_width  * sin(theta + M_PI/2.0);
1879                            /* points of polygon (triangle) */
1880                            p[0].x = ROUND(ex + u1 - u2);
1881                            p[0].y = ROUND(ey + v1 - v2);
1882                            p[1].x = ex;
1883                            p[1].y = ey;
1884                            p[2].x = ROUND(ex + u1 + u2);
1885                            p[2].y = ROUND(ey + v1 + v2);
1886                            /* draw the polygon (triangle) */
1887                            gdImageFilledPolygon(im, p, 3, conf.merge_color.id);
1888                    }
1889                    else
1890                    {
1891                            if(conf.left_right)
1892                            {
1893                                    if(fr->branch == tr->branch)
1894                                    {
1895                                            int yy = (y1 < y2 ? y1 : y2) - 5;
1896                                            gdImageLine(im, x1, y1, x1, yy, conf.merge_color.id);
1897                                            gdImageLine(im, x2, y2, x2, yy, conf.merge_color.id);
1898                                            gdImageLine(im, x1, yy, x2, yy, conf.merge_color.id);
1899                                    }
1900                                    else
1901                                    {
1902                                            if(y1 > y2)
1903                                            {
1904                                                    gdImageLine(im, x1, y1, x1, y1-3, conf.merge_color.id);
1905                                                    gdImageLine(im, x2, y2+1, x2, y2+3+1, conf.merge_color.id);
1906                                                    gdImageLine(im, x1, y1-3, x2, y2+3+1, conf.merge_color.id);
1907                                            }
1908                                            else
1909                                            {
1910                                                    gdImageLine(im, x1, y1+1, x1, y1+3+1, conf.merge_color.id);
1911                                                    gdImageLine(im, x2, y2, x2, y2-3, conf.merge_color.id);
1912                                                    gdImageLine(im, x1, y1+3+1, x2, y2-3, conf.merge_color.id);
1913                                            }
1914                                    }
1915                            }
1916                            else
1917                            {
1918                                    if(fr->branch == tr->branch)
1919                                    {
1920                                            int xx = (x1 < x2 ? x1 : x2) - 5;
1921                                            gdImageLine(im, xx, y1, x1, y1, conf.merge_color.id);
1922                                            gdImageLine(im, xx, y2, x2, y2, conf.merge_color.id);
1923                                            gdImageLine(im, xx, y1, xx, y2, conf.merge_color.id);
1924                                    }
1925                                    else
1926                                    {
1927                                            if(x1 > x2)
1928                                            {
1929                                                    gdImageLine(im, x1, y1, x1-3, y1, conf.merge_color.id);
1930                                                    gdImageLine(im, x2, y2, x2+3, y2, conf.merge_color.id);
1931                                                    gdImageLine(im, x1-3, y1, x2+3, y2, conf.merge_color.id);
1932                                            }
1933                                            else
1934                                            {
1935                                                    gdImageLine(im, x1, y1, x1+3, y1, conf.merge_color.id);
1936                                                    gdImageLine(im, x2, y2, x2-3, y2, conf.merge_color.id);
1937                                                    gdImageLine(im, x1+3, y1, x2-3, y2, conf.merge_color.id);
1938                                            }
1939                                    }
1940                            }
1941                    }
1942            }
1943    }
1944    
1945    static void draw_messages(gdImagePtr im, int offset)
1946    {
1947            int i;
1948    
1949            for(i = 0; i < nmsg_stack; i++)
1950            {
1951                    draw_stringnl(im, msg_stack[i].msg, &conf.msg_font, conf.margin_left, offset, ALIGN_HL|ALIGN_VT, &conf.msg_color);
1952                    offset += msg_stack[i].h;
1953            }
1954    }
1955    
1956    static void alloc_color(gdImagePtr im, color_t *c)
1957    {
1958            c->id = gdImageColorAllocate(im, c->r, c->g, c->b);
1959    }
1960    
1961    static gdImagePtr make_image(rcsfile_t *rcs)
1962    {
1963            gdImagePtr im;
1964            int i;
1965            char *cptr;
1966            int w, h;
1967            int subx = 0, suby = 0;
1968            int subw, subh;
1969            int msgh = 0;
1970    
1971            if(subtree_branch)
1972            {
1973                    subw = 0;
1974                    subh = 0;
1975                    if(subtree_rev)
1976                    {
1977                            for(i = 0; i < subtree_rev->nbranches; i++)
1978                                    calc_subtree_size(subtree_rev->branches[i], &subx, &suby, &subw, &subh);
1979                    }
1980                    else
1981                            calc_subtree_size(subtree_branch, &subx, &suby, &subw, &subh);
1982            }
1983            else
1984            {
1985                    subw = rcs->tw;
1986                    subh = rcs->th;
1987            }
1988    
1989            cptr = expand_string(conf.title, rcs, NULL, NULL, NULL, NULL);
1990            w = subw + conf.margin_left + conf.margin_right;
1991            h = subh + conf.margin_top + conf.margin_bottom;
1992            i = get_swidth(cptr, &conf.title_font);
1993            if(i > w)
1994                    w = i;
1995    
1996            if(!quiet && nmsg_stack)
1997            {
1998                    int msgw = 0;
1999                    for(i = 0; i < nmsg_stack; i++)
2000                    {
2001                            int ww = msg_stack[i].w = get_swidth(msg_stack[i].msg, &conf.msg_font);
2002                            int hh = msg_stack[i].h = get_sheight(msg_stack[i].msg, &conf.msg_font);
2003                            msgh += hh;
2004                            h += hh;
2005                            if(ww > msgw)
2006                                    msgw = ww;
2007                    }
2008                    if(msgw > w)
2009                            w = msgw;
2010            }
2011    
2012            im = gdImageCreate(w, h);
2013            alloc_color(im, &conf.color_bg);
2014            alloc_color(im, &conf.tag_color);
2015            alloc_color(im, &conf.rev_color);
2016            alloc_color(im, &conf.rev_bgcolor);
2017            alloc_color(im, &conf.rev_text_color);
2018            alloc_color(im, &conf.branch_color);
2019            alloc_color(im, &conf.branch_tag_color);
2020            alloc_color(im, &conf.branch_bgcolor);
2021            alloc_color(im, &conf.title_color);
2022            alloc_color(im, &conf.merge_color);
2023            alloc_color(im, &conf.msg_color);
2024            alloc_color(im, &black_color);
2025            alloc_color(im, &white_color);
2026    
2027            if(conf.transparent_bg)
2028                    gdImageColorTransparent(im, conf.color_bg.id);
2029    
2030            if(!conf.merge_front)
2031                    draw_merges(im, rcs, 0);
2032    
2033            for(i = 0; i < rcs->nbranches; i++)
2034            {
2035                    if(!rcs->branches[i]->folded && !(subtree_branch && !rcs->branches[i]->subtree_draw))
2036                            draw_branch(im, rcs->branches[i]);
2037            }
2038    
2039            draw_merges(im, rcs, 1);        /* The dots of the merge dest */
2040    
2041            for(i = 0; i < rcs->nbranches; i++)
2042            {
2043                    if(rcs->branches[i]->branchpoint)
2044                            draw_connector(im, rcs->branches[i]);
2045            }
2046    
2047            /* Clear the margins if we have a partial tree */
2048            if(subtree_branch)
2049            {
2050                    gdImageFilledRectangle(im, 0, 0, w-1, conf.margin_top-1, conf.color_bg.id);
2051                    gdImageFilledRectangle(im, 0, 0, conf.margin_left-1, h-1, conf.color_bg.id);
2052                    gdImageFilledRectangle(im, 0, h-conf.margin_bottom, w-1, h-1, conf.color_bg.id);
2053                    gdImageFilledRectangle(im, w-conf.margin_right, 0, w-1, h-1, conf.color_bg.id);
2054            }
2055    
2056            draw_stringnl(im, cptr, &conf.title_font, conf.title_x, conf.title_y, conf.title_align, &conf.title_color);
2057            xfree(cptr);
2058    
2059            if(conf.merge_front)
2060                    draw_merges(im, rcs, 0);
2061    
2062            if(!quiet)
2063                    draw_messages(im, h - conf.margin_bottom/2 - msgh);
2064    
2065            return im;
2066    }
2067    
2068    /*
2069     **************************************************************************
2070     * Layout routines
2071     *
2072     * Branch BBox:
2073     *      left   = center_x - total_width / 2     (cx-tw)/2
2074     *      right  = center_x + total_width / 2     (cx+tw)/2
2075     *      top    = y_pos                          (y)
2076     *      bottom = y_pos + total_height           (y+th)
2077     *
2078     * Margins of branches:
2079     *
2080     *         .              .
2081     *         .              .
2082     *         +--------------+
2083     *            ^
2084     *            | branch_margin           .
2085     *            v                         .
2086     * ----------------+                    .
2087     *                 | ^                  |
2088     *                 | | branch_connect   |
2089     *                 | v                  |
2090     *..-+      +t-----+------+      +------+------+
2091     *   |      l             |      |             |
2092     *   | <--> | branch bbox | <--> | branch bbox |
2093     *   |   |  |             r   |  |             |
2094     *..-+   |  +------------b+   |  +-------------+
2095     *       |    ^               branch_margin
2096     *       |    | branch_margin
2097     *       |    v
2098     *       |  +-------------+
2099     *       |  .             .
2100     *       |  .             .
2101     *       |
2102     *       branch_margin
2103     *
2104     * FIXME: There are probable som +/-1 errors in the code...
2105     *        (notably shadows are not calculated in the margins)
2106     **************************************************************************
2107     */
2108    static void move_branch(branch_t *b, int x, int y)
2109    {
2110            int i;
2111            b->cx += x;
2112            b->y += y;
2113            for(i = 0; i < b->nrevs; i++)
2114            {
2115                    b->revs[i]->cx += x;
2116                    b->revs[i]->y += y;
2117            }
2118    }
2119    
2120    static void initial_reposition_branch(revision_t *r, int *x, int *w)
2121    {
2122            int i, j;
2123            for(j = 0; j < r->nbranches; j++)
2124            {
2125                    branch_t *b = r->branches[j];
2126                    *x += *w + conf.rev_minline + b->tw/2 - b->cx;
2127                    *w = b->tw/2;
2128                    move_branch(b, *x, r->y + r->h/2 + conf.branch_connect);
2129                    *x = b->cx;
2130                    /* Recurse to move branches of branched revisions */
2131                    for(i = b->nrevs-1; i >= 0; i--)
2132                    {
2133                            initial_reposition_branch(b->revs[i], x, w);
2134                    }
2135            }
2136    }
2137    
2138    static void initial_reposition_branch_lr(revision_t *r, int *y, int *h)
2139    {
2140            int i, j;
2141            for(j = 0; j < r->nbranches; j++)
2142            {
2143                    branch_t *b = r->branches[j];
2144                    *y += *h + conf.rev_minline + b->th/2 - b->y;
2145                    *h = b->th/2;
2146                    move_branch(b, r->cx + r->w/2 + conf.branch_connect, *y);
2147                    *y = b->y;
2148                    /* Recurse to move branches of branched revisions */
2149                    for(i = b->nrevs-1; i >= 0; i--)
2150                    {
2151                            initial_reposition_branch_lr(b->revs[i], y, h);
2152                    }
2153            }
2154    }
2155    
2156    static void rect_union(int *x, int *y, int *w, int *h, branch_t *b)
2157    {
2158            int x1 = *x;
2159            int x2 = x1 + *w;
2160            int y1 = *y;
2161            int y2 = y1 + *h;
2162            int xx1;
2163            int xx2;
2164            int yy1;
2165            int yy2;
2166    
2167            if(conf.left_right)
2168            {
2169                    xx1 = b->cx;
2170                    yy1 = b->y - b->th/2;
2171            }
2172            else
2173            {
2174                    xx1 = b->cx - b->tw/2;
2175                    yy1 = b->y;
2176            }
2177            xx2 = xx1 + b->tw;
2178            yy2 = yy1 + b->th;
2179    
2180            x1 = MIN(x1, xx1);
2181            x2 = MAX(x2, xx2);
2182            y1 = MIN(y1, yy1);
2183            y2 = MAX(y2, yy2);
2184            *x = x1;
2185            *y = y1;
2186            *w = x2 - x1;
2187            *h = y2 - y1;
2188    }
2189    
2190    static void calc_subtree_size(branch_t *b, int *x, int *y, int *w, int *h)
2191    {
2192            int i, j;
2193    
2194            rect_union(x, y, w, h, b);
2195    
2196            for(i = 0; i < b->nrevs; i++)
2197            {
2198                    for(j = 0; j < b->revs[i]->nbranches; j++)
2199                            calc_subtree_size(b->revs[i]->branches[j], x, y, w, h);
2200            }
2201    }
2202    
2203    static int branch_intersects(int top, int bottom, int left, branch_t *b)
2204    {
2205            int br = b->cx + b->tw/2;
2206            int bt = b->y - conf.branch_connect - conf.branch_margin/2;
2207            int bb = b->y + b->th + conf.branch_margin/2;
2208            return !(bt > bottom || bb < top || br >= left);
2209    }
2210    
2211    static int branch_intersects_lr(int left, int right, int top, branch_t *b)
2212    {
2213            int bt = b->y + b->th/2;
2214            int bl = b->cx - conf.branch_connect - conf.branch_margin/2;
2215            int br = b->cx + b->tw + conf.branch_margin/2;
2216            return !(bl > right || br < left || bt >= top);
2217    }
2218    
2219    static int kern_branch(rcsfile_t *rcs, branch_t *b)
2220    {
2221            int left = b->cx - b->tw/2;
2222            int top = b->y - conf.branch_connect - conf.branch_margin/2;
2223            int bottom = b->y + b->th + conf.branch_margin/2;
2224            int i;
2225            int xpos = 0;
2226    
2227            for(i = 0; i < rcs->nbranches; i++)
2228            {
2229                    branch_t *bp = rcs->branches[i];
2230                    if(bp == b)
2231                            continue;
2232                    if(branch_intersects(top, bottom, left, bp))
2233                    {
2234                            int m = bp->cx + bp->tw/2 + conf.branch_margin;
2235                            if(m > xpos)
2236                                    xpos = m;
2237                    }
2238            }
2239            if(xpos && (b->cx - b->tw/2) - xpos > 0)
2240            {
2241                    move_branch(b, xpos - (b->cx - b->tw/2), 0);
2242                    return 1;
2243            }
2244            return 0;
2245    }
2246    
2247    static int kern_branch_lr(rcsfile_t *rcs, branch_t *b)
2248    {
2249            int top = b->y - b->th/2;
2250            int left = b->cx - conf.branch_connect - conf.branch_margin/2;
2251            int right = b->cx + b->tw + conf.branch_margin/2;
2252            int i;
2253            int ypos = 0;
2254    
2255            for(i = 0; i < rcs->nbranches; i++)
2256            {
2257                    branch_t *bp = rcs->branches[i];
2258                    if(bp == b)
2259                            continue;
2260                    if(branch_intersects_lr(left, right, top, bp))
2261                    {
2262                            int m = bp->y + bp->th/2 + conf.branch_margin;
2263                            if(m > ypos)
2264                                    ypos = m;
2265                    }
2266          }          }
2267          switch(align & ALIGN_VX)          if(ypos && (b->y - b->th/2) - ypos > 0)
2268          {          {
2269          default:                  move_branch(b, 0, ypos - (b->y - b->th/2));
2270          case ALIGN_VT: yy = 0; break;                  return 1;
         case ALIGN_VC: yy = -get_sheight(s, f)/2; break;  
         case ALIGN_VB: yy = -get_sheight(s, f); break;  
2271          }          }
2272          gdImageString(im, *f, x+xx+1, y+yy, s, c->id);          return 0;
2273  }  }
2274    
2275  void draw_rev(gdImagePtr im, int cx, int ty, revision_t *r)  static int kern_tree(rcsfile_t *rcs)
2276  {  {
         int lx = cx - r->w/2;  
         int rx = lx + r->w;  
2277          int i;          int i;
2278          draw_rbox(im, lx, ty, rx, ty+r->h, 0, &conf.rev_color);          int moved;
2279          ty += conf.rev_tspace;          int safeguard;
2280          draw_string(im, r->rev->rev, &conf.rev_font, cx, ty, ALIGN_HC, &conf.rev_color);          int totalmoved = 0;
2281          ty += get_sheight(r->rev->rev, &conf.rev_font);          for(moved = 1, safeguard = LOOPSAFEGUARD; moved && safeguard; safeguard--)
         for(i = 0; i < r->ntags; i++)  
2282          {          {
2283                  draw_string(im, r->tags[i]->tag, &conf.tag_font, cx, ty, ALIGN_HC, &conf.tag_color);                  moved = 0;
2284                  ty += get_sheight(r->tags[i]->tag, &conf.tag_font);                  for(i = 1; i < rcs->nbranches; i++)
2285                    {
2286                            if(conf.left_right)
2287                                    moved += kern_branch_lr(rcs, rcs->branches[i]);
2288                            else
2289                                    moved += kern_branch(rcs, rcs->branches[i]);
2290                    }
2291                    totalmoved += moved;
2292    #ifdef DEBUG
2293                    fprintf(stderr, "kern_tree: moved=%d\n", moved);
2294    #endif
2295          }          }
2296            if(!safeguard)
2297                    stack_msg(MSG_WARN, "kern_tree: safeguard terminated possible infinite loop; please report.");
2298            return totalmoved;
2299  }  }
2300    
2301  void draw_branch(gdImagePtr im, int cx, int ty, branch_t *b)  static int index_of_revision(revision_t *r)
2302  {  {
2303          int lx = cx - b->w/2;          branch_t *b = r->branch;
         int rx = lx + b->w;  
         int yy;  
2304          int i;          int i;
         draw_rbox(im, lx, ty, rx, ty+b->h, 5, &conf.branch_color);  
         yy = conf.branch_tspace;  
         draw_string(im, b->branch, &conf.branch_font, cx, ty+yy, ALIGN_HC, &conf.branch_color);  
         yy += get_sheight(b->branch, &conf.branch_font);  
         if(b->tag)  
         {  
                 draw_string(im, b->tag->tag, &conf.branch_font, cx, ty+yy, ALIGN_HC, &conf.branch_color);  
         }  
   
         ty += b->h;  
2305          for(i = 0; i < b->nrevs; i++)          for(i = 0; i < b->nrevs; i++)
2306          {          {
2307                  gdImageLine(im, cx, ty, cx, ty+conf.rev_minline, conf.rev_color.id);                  if(r == b->revs[i])
2308                  ty += conf.rev_minline;                          return i;
                 draw_rev(im, cx, ty, b->revs[i]);  
                 ty += b->revs[i]->h;  
2309          }          }
2310            stack_msg(MSG_ERR, "index_of_revision: Cannot find revision in branch\n");
2311            return 0;
2312    }
2313    
2314    static void branch_bbox(branch_t *br, int *l, int *r, int *t, int *b)
2315    {
2316            if(l)   *l = br->cx - br->tw/2;
2317            if(r)   *r = br->cx + br->tw/2;
2318            if(t)   *t = br->y;
2319            if(b)   *b = br->y + br->th + ((conf.branch_dupbox && br->nrevs) ? conf.rev_minline + br->h : 0);
2320    }
2321    
2322    static void branch_ext_bbox(branch_t *br, int *l, int *r, int *t, int *b)
2323    {
2324            int extra = conf.branch_margin & 1;     /* Correct +/-1 error on div 2 */
2325            branch_bbox(br, l, r, t, b);
2326            if(l)   *l -= conf.branch_margin/2;
2327            if(r)   *r += conf.branch_margin/2 + extra;
2328            if(t)   *t -= conf.branch_connect + conf.branch_margin/2;
2329            if(b)   *b += conf.branch_margin/2 + extra;
2330    }
2331    
2332    static int branch_distance(branch_t *br1, branch_t *br2)
2333    {
2334            int l1, r1, t1, b1;
2335            int l2, r2, t2, b2;
2336            assert(br1 != NULL);
2337            assert(br2 != NULL);
2338            branch_bbox(br1, &l1, &r1, NULL, NULL);
2339            branch_bbox(br2, &l2, &r2, NULL, NULL);
2340            branch_ext_bbox(br1, NULL, NULL, &t1, &b1);
2341            branch_ext_bbox(br2, NULL, NULL, &t2, &b2);
2342            /* Return:
2343             * - 0 if branches have no horizontal overlap
2344             * - positive if b1 is left of b2
2345             * - negative if b2 is left of b1
2346             */
2347            if((t1 > t2 && t1 < b2) || (b1 > t2 && b1 < b2))
2348                    return l1 < l2 ? l2 - r1 : -(l1 - r2);
2349            else
2350                    return 0;
2351  }  }
2352    
2353  static char *_title;  static int space_needed(branch_t *br1, branch_t *br2)
2354  static int _ntitle;  {
2355  static int _natitle;          int t1, b1;
2356            int t2, b2;
2357            assert(br1 != NULL);
2358            assert(br2 != NULL);
2359            assert(br1->cx < br2->cx);      /* br1 must be left of br2 */
2360            branch_ext_bbox(br1, NULL, NULL, &t1, &b1);
2361            branch_ext_bbox(br2, NULL, NULL, &t2, &b2);
2362            /* Return:
2363             * - positive if top br1 is located lower than br2
2364             * - negatve is top br2 is located lower than br1
2365             */
2366            if(t1 > t2)
2367                    return -(t1 - b2);
2368            else
2369                    return t2 - b1;
2370    }
2371    
2372  void add_title_str(const char *s)  static void move_yr_branch(branch_t *b, int dy)
2373  {  {
2374          int l = strlen(s) + 1;          int i, j;
2375          if(_ntitle + l > _natitle)  #ifdef DEBUG
2376    /*      fprintf(stderr, "move_yr_branch: b=%s, dy=%d\n", b->branch->branch, dy);*/
2377    #endif
2378            b->y += dy;
2379            for(i = 0; i < b->nrevs; i++)
2380          {          {
2381                  _natitle += 128;                  b->revs[i]->y += dy;
2382                  _title = xrealloc(_title, _natitle * sizeof(_title[0]));                  for(j = 0; j < b->revs[i]->nbranches; j++)
2383                    {
2384    #ifdef DEBUG
2385    /*                      fprintf(stderr, ".");*/
2386    #endif
2387                            move_yr_branch(b->revs[i]->branches[j], dy);
2388                    }
2389          }          }
         memcpy(_title+_ntitle, s, l);  
         _ntitle += l-1;  
2390  }  }
2391    
2392  void add_title_ch(int ch)  static void move_trunk(revision_t *r, int dy)
2393  {  {
2394          char buf[2];          int i, j;
2395          buf[0] = ch;          branch_t *b = r->branch;
2396          buf[1] = '\0';          b->th += dy;
2397          add_title_str(buf);          for(i = index_of_revision(r); i < b->nrevs; i++)
2398            {
2399    #ifdef DEBUG
2400                    fprintf(stderr, "move_trunk: start %s, moving %s by %d (b's %d)\n", r->rev->rev, b->revs[i]->rev->rev, dy, b->revs[i]->nbranches);
2401    #endif
2402                    b->revs[i]->y += dy;
2403                    for(j = 0; j < b->revs[i]->nbranches; j++)
2404                    {
2405                            move_yr_branch(b->revs[i]->branches[j], dy);
2406                    }
2407            }
2408  }  }
2409    
2410  char *expand_title(rcsfilelog_t *rcs)  static int space_below(rcsfile_t *rcs, revision_t *r)
2411  {  {
2412          char nb[32];          int i, j;
2413          char nr[32];          int bl, br, bb;
2414          char *cptr;          int space = INT_MAX;
2415            branch_t *b = r->branch;
2416            branch_t *minb = NULL;
2417    
2418          sprintf(nb, "%d", rcs->nbranches);          branch_ext_bbox(b, &bl, &br, NULL, &bb);
2419          sprintf(nr, "%d", rcs->nrevs);          for(i = 0; i < rcs->nbranches; i++)
         for(cptr = conf.title; *cptr; cptr++)  
2420          {          {
2421                  if(*cptr == '%')                  int tbl, tbr, tbt;
2422                    branch_t *tb = rcs->branches[i];
2423                    branch_ext_bbox(tb, &tbl, &tbr, &tbt, NULL);
2424                    if(tb == b)
2425                            continue;
2426                    if(tbt > bb)    /* Must be below our branch */
2427                  {                  {
2428                          switch(*++cptr)                          if(tb->branchpoint)     /* Take account for the horiz connector */
2429                                    tbl = tb->branchpoint->cx + tb->branchpoint->branch->tw/2;
2430                            if((bl >= tbl && bl <= tbr) || (br <= tbr && br >= tbl))
2431                          {                          {
2432                          case 'c': add_title_str(conf.cvsroot); break;                                  int s = tbt - bb - conf.branch_connect;
2433                          case 'f': add_title_str(rcs->name); break;                                  if(s < space)
2434                          case 'm': add_title_str(conf.cvsmodule); break;                                  {
2435                          case 'r': add_title_str(nr); break;                                          space = s;
2436                          case 'b': add_title_str(nb); break;                                          minb = tb;
2437                          case '%': add_title_ch('%'); break;                                  }
2438                          default:                          }
2439                                  add_title_ch('%');                  }
2440                                  add_title_ch(*cptr);          }
2441                                  break;          if(b->branchpoint)
2442            {
2443                    for(i = index_of_revision(r); i < b->nrevs; i++)
2444                    {
2445                            for(j = 0; j < b->revs[i]->nbranches; j++)
2446                            {
2447                                    int s = space_below(rcs, b->revs[i]->branches[j]->revs[0]);
2448                                    if(s < space)
2449                                            space = s;
2450                          }                          }
2451                  }                  }
                 else  
                         add_title_ch(*cptr);  
2452          }          }
2453          return _title;  #ifdef DEBUG
2454            fprintf(stderr, "space_below: from %s have %d to %s\n", b->branch->branch, space, minb ? minb->branch->branch : "<recursed>");
2455    #endif
2456            return space;
2457  }  }
2458    
2459  void draw_title(gdImagePtr im, char *title)  static int space_available(rcsfile_t *rcs, branch_t *colbr, branch_t *tagbr, int *nl, revision_t **bpcommon)
2460  {  {
2461          char *t;          int i;
2462          char *s = title;          int space = 0;
2463          int x = conf.title_x;          int nlinks = 0;
2464          int y = conf.title_y;          revision_t *r;
2465          do          branch_t *b;
2466            branch_t *ancestor;
2467            revision_t *branchpoint;
2468    
2469            if(!tagbr->branchpoint || !colbr->branchpoint)
2470          {          {
2471                  t = strchr(s, '\n');                  stack_msg(MSG_WARN, "space_available: Trying to stretch the top?");
2472                  if(t)                  return 0;
2473                          *t = '\0';          }
2474                  draw_string(im, s, &conf.title_font, x, y, conf.title_align, &conf.title_color);  
2475                  y += get_sheight(s, &conf.title_font);          r = colbr->branchpoint;
2476                  s = t+1;          b = r->branch;
2477          } while(t);          branchpoint = tagbr->branchpoint;
2478            ancestor = branchpoint->branch;
2479            assert(b != NULL);
2480            assert(ancestor != NULL);
2481    
2482            while(1)
2483            {
2484                    int s;
2485                    int rtag = b == ancestor ? index_of_revision(branchpoint)+1 : 0;
2486                    for(i = index_of_revision(r); i >= rtag; i--)
2487                    {
2488                            if(i > 0)
2489                                    s = b->revs[i]->y - (b->revs[i-1]->y + b->revs[i-1]->h);
2490                            else
2491                                    s = b->revs[i]->y - (b->y + b->h);
2492                            if(s < conf.rev_maxline)
2493                            {
2494                                    space += conf.rev_maxline - s;
2495                                    nlinks++;
2496                            }
2497                    }
2498                    s = space_below(rcs, r);
2499                    if(s < space)
2500                            space = s;
2501    #ifdef DEBUG
2502                    if(space < 0)
2503                            return -1;
2504    #endif
2505                    if(b == ancestor)
2506                            break;
2507                    r = b->branchpoint;
2508                    if(!r)
2509                    {
2510                            /* Not a common ancestor */
2511                            r = colbr->branchpoint;
2512                            b = r->branch;
2513                            branchpoint = ancestor->branchpoint;
2514                            if(!branchpoint)
2515                            {
2516                                    stack_msg(MSG_WARN, "space_available: No common ancestor?");
2517                                    return 0;
2518                            }
2519                            ancestor = branchpoint->branch;
2520                            assert(ancestor != NULL);
2521                            nlinks = 0;
2522                            space = 0;
2523                            continue;       /* Restart with a new ancestor */
2524                    }
2525                    b = r->branch;
2526            }
2527            if(nl)
2528                    *nl = nlinks;           /* Return the number of links that can stretch */
2529            if(bpcommon)
2530                    *bpcommon = branchpoint;        /* Return the ancestral branchpoint on the common branch */
2531            return space;
2532  }  }
2533    
2534  void draw_connector(gdImagePtr im, branch_t *b)  static int stretch_branches(rcsfile_t *rcs, branch_t *br1, branch_t *br2, int totalstretch)
2535  {  {
2536          revision_t *r = b->branchpoint;          revision_t *r;
2537          int x1 = r->x + r->w/2 + 2;          revision_t *bpcommon = NULL;
2538          int y1 = r->y + r->h/2;          branch_t *ancestor = NULL;
2539          int x2 = b->x;          branch_t *b;
2540          int y2 = b->y;          int i;
2541          gdImageLine(im, x1, y1, x2, y1, conf.branch_color.id);          int space;
2542          gdImageLine(im, x2, y1, x2, y2, conf.branch_color.id);          int nlinks;
2543            int dy;
2544            int rest;
2545    
2546            space = space_available(rcs, br1, br2, &nlinks, &bpcommon);
2547            if(bpcommon)
2548                    ancestor = bpcommon->branch;
2549    
2550    #ifdef DEBUG
2551            if(space == -1)
2552                    return 0;
2553            fprintf(stderr, "stretch_branches: space available %d over %d links common %s\n", space, nlinks, ancestor->branch->branch);
2554    #endif
2555            if(space < totalstretch)
2556                    return 0;
2557    
2558            dy = totalstretch / nlinks;
2559            rest = totalstretch - dy * nlinks;
2560    
2561            r = br1->branchpoint;
2562            b = r->branch;
2563            while(1)
2564            {
2565                    int rtag = b == ancestor ? index_of_revision(bpcommon)+1 : 0;
2566                    for(i = index_of_revision(r); i >= rtag; i--)
2567                    {
2568                            int s, q;
2569                            if(i > 0)
2570                                    s = b->revs[i]->y - (b->revs[i-1]->y + b->revs[i-1]->h);
2571                            else
2572                                    s = b->revs[i]->y - (b->y + b->h);
2573                            q = conf.rev_maxline - s;
2574                            if(q > 0)
2575                            {
2576                                    int d = rest ? rest/nlinks+1 : 0;
2577                                    if(q >= dy+d)
2578                                    {
2579                                            move_trunk(b->revs[i], dy+d);
2580                                    }
2581                                    else
2582                                    {
2583                                            move_trunk(b->revs[i], q);
2584                                            rest += dy+d - q;
2585                                    }
2586                                    rest -= d;
2587                                    nlinks--;
2588                            }
2589                    }
2590                    if(b == ancestor)
2591                            break;
2592                    r = b->branchpoint;
2593                    assert(r != NULL);      /* else 'space_available' wouldn't have returned positively */
2594                    b = r->branch;
2595            }
2596            return 1;
2597  }  }
2598    
2599  gdImagePtr make_image(rcsfilelog_t *rcs)  static branch_t *find_collision_branch(rcsfile_t *rcs, branch_t *b)
2600  {  {
         gdImagePtr im;  
2601          int i;          int i;
2602            int dist = INT_MAX;
2603          im = gdImageCreate(rcs->tw+conf.margin_left+conf.margin_right, rcs->th+conf.margin_top+conf.margin_bottom);          branch_t *col = NULL;
         conf.color_bg.id = gdImageColorAllocate(im, conf.color_bg.r, conf.color_bg.g, conf.color_bg.b);  
         conf.tag_color.id = gdImageColorAllocate(im, conf.tag_color.r, conf.tag_color.g, conf.tag_color.b);  
         conf.rev_color.id = gdImageColorAllocate(im, conf.rev_color.r, conf.rev_color.g, conf.rev_color.b);  
         conf.branch_color.id = gdImageColorAllocate(im, conf.branch_color.r, conf.branch_color.g, conf.branch_color.b);  
         conf.branch_bgcolor.id = gdImageColorAllocate(im, conf.branch_bgcolor.r, conf.branch_bgcolor.g, conf.branch_bgcolor.b);  
         conf.title_color.id = gdImageColorAllocate(im, conf.title_color.r, conf.title_color.g, conf.title_color.b);  
2604    
2605          for(i = 0; i < rcs->nbranches; i++)          for(i = 0; i < rcs->nbranches; i++)
                 draw_branch(im, rcs->branches[i]->x, rcs->branches[i]->y, rcs->branches[i]);  
         for(i = 0; i < rcs->nbranches; i++)  
2606          {          {
2607                  if(rcs->branches[i]->branchpoint)                  int t = branch_distance(rcs->branches[i], b);
2608                          draw_connector(im, rcs->branches[i]);                  if(t > 0 && t < dist)
2609                    {
2610                            dist = t;
2611                            col = rcs->branches[i];
2612                    }
2613          }          }
2614          draw_title(im, expand_title(rcs));          return col;
   
         return im;  
2615  }  }
2616    
2617  void move_branch(branch_t *b, int x, int y)  static void auto_stretch(rcsfile_t *rcs)
2618  {  {
2619          int i;          int i;
2620          b->x += x;          int safeguard;
2621          b->y += y;  
2622          for(i = 0; i < b->nrevs; i++)          for(i = 0, safeguard = LOOPSAFEGUARD; i < rcs->nbranches && safeguard; i++)
2623          {          {
2624                  b->revs[i]->x += x;                  int bl, pr;
2625                  b->revs[i]->y += y;                  branch_t *b = rcs->branches[i];
2626                    if(!b->branchpoint)
2627                            continue;
2628                    branch_bbox(b, &bl, NULL, NULL, NULL);
2629                    branch_bbox(b->branchpoint->branch, NULL, &pr, NULL, NULL);
2630                    if(bl - conf.branch_margin - pr > 0)
2631                    {
2632                            branch_t *col;
2633                            int spaceneeded;
2634                            /* There is a potential to move branch b further left.
2635                             * All branches obstructing this one from moving further
2636                             * left must be originating from revisions below
2637                             * b->branchpoint until a common ancester.
2638                             * So, we search all branches for a branch that lies left
2639                             * of b and is closest to b. This is then the collission
2640                             * branch that needs to be moved.
2641                             */
2642                            col = find_collision_branch(rcs, b);
2643                            if(!col)
2644                                    continue;
2645                            spaceneeded = space_needed(col, b);
2646                            if(spaceneeded < 0)
2647                                    continue;
2648    #ifdef DEBUG
2649                            fprintf(stderr, "auto_stretch: %s collides %s need %d\n", b->branch->branch, col->branch->branch, spaceneeded);
2650    #endif
2651                            /* Trace the collision branch back to find the common ancester
2652                             * of both col and b. All revisions encountered while traversing
2653                             * backwards must be stretched, including all revisions on the
2654                             * common ancester from where the branches sprout.
2655                             */
2656                            if(stretch_branches(rcs, col, b, spaceneeded))
2657                            {
2658                                    if(kern_tree(rcs))
2659                                    {
2660                                            /* Restart the process because movement can
2661                                             * cause more movement.
2662                                             */
2663                                            i = 0 - 1;      /* -1 for the i++ of the loop */
2664                                            safeguard--;    /* Prevent infinite loop, just in case */
2665                                    }
2666                                    /*return;*/
2667                            }
2668                    }
2669          }          }
2670            if(!safeguard)
2671                    stack_msg(MSG_ERR, "auto_stretch: safeguard terminated possible infinite loop; please report.");
2672  }  }
2673    
2674  void rect_union(int *x, int *y, int *w, int *h, branch_t *b)  static void fold_branch(rcsfile_t *rcs, revision_t *r)
2675  {  {
2676          int x1 = *x;          int i, j;
2677          int x2 = x1 + *w;          branch_t *btag = NULL;
2678          int y1 = *y;  
2679          int y2 = y1 + *h;          for(i = 0; i < r->nbranches; i++)
2680          int xx1 = b->x - b->tw/2;          {
2681          int xx2 = xx1 + b->tw;                  branch_t *b = r->branches[i];
2682          int yy1 = b->y;                  if(!b->nrevs && b->ntags < 2)
2683          int yy2 = yy1 + b->th;                  {
2684          x1 = MIN(x1, xx1);                          /* No commits in this branch and no duplicate tags */
2685          x2 = MAX(x2, xx2);                          if(!btag)
2686          y1 = MIN(y1, yy1);                                  btag = b;
2687          y2 = MAX(y2, yy2);                          else
2688          *x = x1;                          {
2689          *y = y1;                                  /* We have consecutive empty branches, fold */
2690          *w = x2 - x1;                                  b->folded = 1;
2691          *h = y2 - y1;                                  b->folded_to = btag;
2692                                    for(j = 0; j < rcs->nbranches; j++)
2693                                    {
2694                                            if(b == rcs->branches[j])
2695                                            {
2696                                                    /* Zap the branch from the admin */
2697                                                    memmove(&rcs->branches[j],
2698                                                            &rcs->branches[j+1],
2699                                                            (rcs->nbranches - j - 1)*sizeof(rcs->branches[0]));
2700                                                    rcs->nbranches--;
2701                                                    break;
2702                                            }
2703    
2704                                    }
2705                                    memmove(&r->branches[i], &r->branches[i+1], (r->nbranches - i - 1)*sizeof(r->branches[0]));
2706                                    r->nbranches--;
2707                                    i--;    /* We have one less now */
2708    
2709                                    /* Add to the fold-list */
2710                                    btag->folds = xrealloc(btag->folds, (btag->nfolds+1) * sizeof(btag->folds[0]));
2711                                    btag->folds[btag->nfolds] = b;
2712                                    btag->nfolds++;
2713                            }
2714                    }
2715                    else
2716                    {
2717                            if(!conf.branch_foldall)
2718                                    btag = NULL;    /* Start a new box */
2719                            /* Recursively fold sub-branches */
2720                            for(j = 0; j < b->nrevs; j++)
2721                                    fold_branch(rcs, b->revs[j]);
2722                    }
2723            }
2724    }
2725    
2726    static void mark_subtree(branch_t *b)
2727    {
2728            int i, j;
2729            b->subtree_draw = 1;
2730            for(i = 0; i < b->nrevs; i++)
2731            {
2732                    for(j = 0; j < b->revs[i]->nbranches; j++)
2733                            mark_subtree(b->revs[i]->branches[j]);
2734            }
2735  }  }
2736    
2737  void make_layout(rcsfilelog_t *rcs)  static void make_layout(rcsfile_t *rcs)
2738  {  {
2739          int i, j;          int i, j;
2740          int x, y;          int x, y;
2741          int w, h;          int w, h;
2742          int w2;          int w2;
2743    
2744            /* Remove all unwanted revisions */
2745            if(conf.strip_untagged)
2746            {
2747                    int fr = conf.strip_first_rev ? 0 : 1;
2748                    for(i = 0; i < rcs->nbranches; i++)
2749                    {
2750                            branch_t *bp = rcs->branches[i];
2751                            for(j = fr; j < bp->nrevs-1; j++)
2752                            {
2753                                    if(!bp->revs[j]->ntags && !bp->revs[j]->nbranches)
2754                                    {
2755                                            memmove(&bp->revs[j], &bp->revs[j+1], (bp->nrevs-j-1) * sizeof(bp->revs[0]));
2756                                            bp->nrevs--;
2757                                            bp->revs[j]->stripped = 1;
2758                                            j--;
2759                                    }
2760                            }
2761                    }
2762            }
2763    
2764            /* Find the sub-tree(s) we want to see */
2765            if(conf.branch_subtree && conf.branch_subtree[0])
2766            {
2767                    branch_t **b;
2768                    revision_t **r;
2769                    rev_t rev;
2770                    int k;
2771                    char *tag = conf.branch_subtree;
2772    
2773                    /* First translate any symbolic tag to a real branch/revision number */
2774                    if(rcs->tags)
2775                    {
2776                            for(k = 0; k < rcs->tags->ntags; k++)
2777                            {
2778                                    if(!strcmp(conf.branch_subtree, rcs->tags->tags[k]->tag))
2779                                    {
2780                                            if(rcs->tags->tags[k]->rev->isbranch)
2781                                                    tag = rcs->tags->tags[k]->rev->branch;
2782                                            else
2783                                                    tag = rcs->tags->tags[k]->rev->rev;
2784