/[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.51, Thu Oct 21 21:22:47 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_cvsnt(rcsfile_t *rcs)
744    {
745            int i;
746    
747            if(!conf.merge_cvsnt)
748                    return;
749    
750            for(i = 0; i < rcs->nsrev; i++)
751            {
752                    revision_t **r;
753    
754                    if(!rcs->srev[i]->delta->mergepoint)
755                            continue;
756    
757                    r = bsearch(rcs->srev[i]->delta->mergepoint->rev, rcs->srev, rcs->nsrev, sizeof(rcs->srev[0]), search_revision);
758                    if(!r)
759                            continue;
760                    rcs->merges = xrealloc(rcs->merges, sizeof(rcs->merges[0]) * (rcs->nmerges+1));
761                    rcs->merges[rcs->nmerges].type = TR_REVISION;
762                    rcs->merges[rcs->nmerges].from.rev = *r;
763                    rcs->merges[rcs->nmerges].to.rev = rcs->srev[i];
764                    rcs->nmerges++;
765            }
766    }
767    
768    static void find_merges(rcsfile_t *rcs)
769    {
770            int i;
771            int err;
772            int rcflags = REG_EXTENDED | (conf.merge_nocase ? REG_ICASE : 0);
773            regex_t *refrom = NULL;
774            regex_t *reto = NULL;
775            regmatch_t *matchfrom = NULL;
776    
777            if(!conf.merge_from || !conf.merge_from[0] || !conf.merge_to || !conf.merge_to[0])
778                    return;
779    
780            refrom = xmalloc(sizeof(*refrom));
781            reto = xmalloc(sizeof(*reto));
782    
783            /* Compile the 'from' regex match for merge identification */
784            err = regcomp(refrom, conf.merge_from, rcflags);
785            if(err)
786            {
787                    char *msg;
788                    i = regerror(err, refrom, NULL, 0);
789                    msg = xmalloc(i+1);
790                    regerror(err, refrom, msg, i+1);
791                    stack_msg(MSG_WARN, "%s", msg);
792                    xfree(msg);
793                    xfree(refrom);
794                    xfree(reto);
795                    return;
796            }
797            else
798                    matchfrom = xmalloc((refrom->re_nsub+1) * sizeof(*matchfrom));
799    
800            for(i = 0; i < rcs->tags->ntags; i++)
801            {
802                    tag_t *t = rcs->tags->tags[i];
803    
804                    /* Must be revision tags and not detached */
805                    if(t->rev->isbranch || !t->logrev)
806                            continue;
807    
808                    /* Try to find merge tag matches */
809                    if(!regexec(refrom, t->tag, refrom->re_nsub+1, matchfrom, 0))
810                    {
811                            int n;
812                            char *to;
813    
814                            to = build_regex(refrom->re_nsub+1, matchfrom, t->tag);
815                            if(to)
816                            {
817                                    err = regcomp(reto, to, rcflags);
818                                    if(err)
819                                    {
820                                            char *msg;
821                                            i = regerror(err, reto, NULL, 0);
822                                            msg = xmalloc(i+1);
823                                            regerror(err, reto, msg, i+1);
824                                            stack_msg(MSG_WARN, "%s", msg);
825                                            xfree(msg);
826                                    }
827                                    else if(!err)
828                                    {
829                                            for(n = 0; n < rcs->tags->ntags; n++)
830                                            {
831                                                    tag_t *nt = rcs->tags->tags[n];
832                                                    /* From and To never should match the same tag or belong to a branch */
833                                                    if(n == i || nt->rev->isbranch || !nt->logrev)
834                                                            continue;
835    
836                                                    if(!regexec(reto, nt->tag, 0, NULL, 0))
837                                                    {
838                                                            /* Tag matches */
839                                                            rcs->merges = xrealloc(rcs->merges,
840                                                                            sizeof(rcs->merges[0]) * (rcs->nmerges+1));
841                                                            rcs->merges[rcs->nmerges].type = TR_TAG;
842                                                            rcs->merges[rcs->nmerges].to.tag = nt;
843                                                            rcs->merges[rcs->nmerges].from.tag = t;
844                                                            rcs->nmerges++;
845                                                            if(!conf.tag_ignore_merge)
846                                                            {
847                                                                    nt->ignore = 0;
848                                                                    t->ignore = 0;
849                                                            }
850                                                            /* We cannot (should not) match multiple times */
851                                                            if(!conf.merge_findall)
852                                                                    break;
853                                                    }
854                                            }
855                                            regfree(reto);
856                                    }
857                                    xfree(to);
858                            }
859                    }
860            }
861            if(matchfrom)   xfree(matchfrom);
862            if(refrom)      { regfree(refrom); xfree(refrom); }
863            if(reto)        xfree(reto);
864    }
865    
866    static void assign_tags(rcsfile_t *rcs)
867    {
868            int i;
869            int nr;
870            regex_t *regextag = NULL;
871    
872            if(conf.tag_ignore && conf.tag_ignore[0])
873            {
874                    int err;
875                    regextag = xmalloc(sizeof(*regextag));
876                    err = regcomp(regextag, conf.tag_ignore, REG_EXTENDED | REG_NOSUB | (conf.tag_nocase ? REG_ICASE : 0));
877                    if(err)
878                    {
879                            char *msg;
880                            i = regerror(err, regextag, NULL, 0);
881                            msg = xmalloc(i+1);
882                            regerror(err, regextag, msg, i+1);
883                            stack_msg(MSG_WARN, "%s", msg);
884                            xfree(msg);
885                            xfree(regextag);
886                            regextag = NULL;
887                    }
888            }
889    
890            for(i = nr = 0; i < rcs->nbranches; i++)
891                    nr += rcs->branches[i]->nrevs;
892    
893            rcs->srev = xmalloc(nr * sizeof(rcs->srev[0]));
894            rcs->nsrev = nr;
895            for(i = nr = 0; i < rcs->nbranches; i++)
896            {
897                    memcpy(&rcs->srev[nr], rcs->branches[i]->revs, rcs->branches[i]->nrevs * sizeof(rcs->branches[i]->revs[0]));
898                    nr += rcs->branches[i]->nrevs;
899            }
900    
901            qsort(rcs->srev, rcs->nsrev, sizeof(rcs->srev[0]), sort_revision);
902            qsort(rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), sort_branch);
903    
904            if(!rcs->branch)
905            {
906                    /* The main trunk is the active trunk */
907                    rcs->tags->tags = xrealloc(rcs->tags->tags, (rcs->tags->ntags+1)*sizeof(rcs->tags->tags[0]));
908                    rcs->tags->tags[rcs->tags->ntags] = xmalloc(sizeof(tag_t));
909                    rcs->tags->tags[rcs->tags->ntags]->tag = xstrdup("MAIN");
910                    rcs->tags->tags[rcs->tags->ntags]->rev = xmalloc(sizeof(rev_t));
911                    rcs->tags->tags[rcs->tags->ntags]->rev->rev = xstrdup(rcs->active->branch->rev);
912                    rcs->tags->tags[rcs->tags->ntags]->rev->branch = xstrdup(rcs->active->branch->branch);
913                    rcs->tags->tags[rcs->tags->ntags]->rev->isbranch = 1;
914                    rcs->tags->ntags++;
915            }
916    
917            /* We should have at least two tags (HEAD and MAIN) */
918            assert(rcs->tags != NULL);
919    
920            for(i = 0; i < rcs->tags->ntags; i++)
921            {
922                    tag_t *t = rcs->tags->tags[i];
923                    if(t->rev->isbranch)
924                    {
925                            branch_t **b;
926    add_btag:
927                            b = bsearch(t->rev, rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), search_branch);
928                            if(!b)
929                            {
930                                    rev_t rev;
931                                    revision_t **r;
932                                    /* This happens for the magic branch numbers if there are
933                                     * no commits within the new branch yet. So, we add the
934                                     * branch and try to continue.
935                                     */
936                                    rev.rev = previous_rev(t->rev->branch);
937                                    rev.branch = NULL;
938                                    rev.isbranch = 0;
939                                    r = bsearch(&rev, rcs->srev, rcs->nsrev, sizeof(rcs->srev[0]), search_revision);
940                                    xfree(rev.rev);
941                                    if(!r)
942                                    {
943                                            stack_msg(MSG_WARN, "No branch found for tag '%s:%s'", t->tag, t->rev->branch);
944                                    }
945                                    else
946                                    {
947                                            rcs->branches = xrealloc(rcs->branches, (rcs->nbranches+1)*sizeof(rcs->branches[0]));
948                                            rcs->branches[rcs->nbranches] = xmalloc(sizeof(branch_t));
949                                            rcs->branches[rcs->nbranches]->branch = dup_rev(t->rev);
950                                            rcs->branches[rcs->nbranches]->branchpoint = *r;
951                                            (*r)->branches = xrealloc((*r)->branches, ((*r)->nbranches+1)*sizeof((*r)->branches[0]));
952                                            (*r)->branches[(*r)->nbranches] = rcs->branches[rcs->nbranches];
953                                            (*r)->nbranches++;
954                                            rcs->nbranches++;
955                                            /* Resort the branches */
956                                            qsort(rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), sort_branch);
957                                            goto add_btag;
958                                    }
959                            }
960                            else
961                            {
962                                    branch_t *bb = *b;
963                                    bb->tags = xrealloc(bb->tags, (bb->ntags+1)*sizeof(bb->tags[0]));
964                                    bb->tags[bb->ntags] = t;
965                                    bb->ntags++;
966                            }
967                    }
968                    else
969                    {
970                            revision_t **r = bsearch(t->rev, rcs->srev, rcs->nsrev, sizeof(rcs->srev[0]), search_revision);
971                            if(!r)
972                            {
973                                    stack_msg(MSG_WARN, "No revision found for tag '%s:%s'\n", t->tag, t->rev->rev);
974                            }
975                            else
976                            {
977                                    revision_t *rr = *r;
978                                    t->logrev = rr;
979                                    if(!conf.rev_maxtags || rr->ntags <= conf.rev_maxtags)
980                                    {
981                                            rr->tags = xrealloc(rr->tags, (rr->ntags+1)*sizeof(rr->tags[0]));
982                                            if(conf.rev_maxtags && rr->ntags == conf.rev_maxtags)
983                                            {
984                                                    rr->tags[rr->ntags] = xmalloc(sizeof(tag_t));
985                                                    rr->tags[rr->ntags]->tag = xstrdup("...");
986                                                    rr->tags[rr->ntags]->rev = t->rev;
987                                            }
988                                            else
989                                                    rr->tags[rr->ntags] = t;
990                                            rr->ntags++;
991                                    }
992                            }
993    
994                            if(conf.tag_negate)
995                                    t->ignore++;
996                            /* Mark the tag ignored if it matches the configuration */
997                            if(regextag && !regexec(regextag, t->tag, 0, NULL, 0))
998                            {
999                                    if(conf.tag_negate)
1000                                            t->ignore--;
1001                                    else
1002                                            t->ignore++;
1003                            }
1004                    }
1005            }
1006    
1007            /* We need to reset the first in the list of branches to the
1008             * active branch to ensure the drawing of all
1009             */
1010            if(rcs->active != rcs->branches[0])
1011            {
1012                    branch_t **b = bsearch(rcs->active->branch, rcs->branches, rcs->nbranches, sizeof(rcs->branches[0]), search_branch);
1013                    branch_t *t;
1014                    assert(b != NULL);
1015                    t = *b;
1016                    *b = rcs->branches[0];
1017                    rcs->branches[0] = t;
1018            }
1019    
1020            if(regextag)
1021            {
1022                    regfree(regextag);
1023                    xfree(regextag);
1024            }
1025    }
1026    
1027    /*
1028     **************************************************************************
1029     * String expansion
1030     **************************************************************************
1031     */
1032    static char *_string;
1033    static int _nstring;
1034    static int _nastring;
1035    
1036    static void zap_string(void)
1037    {
1038            _nstring = 0;
1039            if(_string)
1040                    _string[0] = '\0';
1041    }
1042    
1043    static char *dup_string(void)
1044    {
1045            if(_string)
1046                    return xstrdup(_string);
1047            else
1048                    return "";
1049    }
1050    
1051    static void add_string_str(const char *s)
1052    {
1053            int l = strlen(s) + 1;
1054            if(_nstring + l > _nastring)
1055            {
1056                    _nastring += MAX(128, l);
1057                    _string = xrealloc(_string, _nastring * sizeof(_string[0]));
1058            }
1059            memcpy(_string+_nstring, s, l);
1060            _nstring += l-1;
1061    }
1062    
1063    static void add_string_ch(int ch)
1064    {
1065            char buf[2];
1066            buf[0] = ch;
1067            buf[1] = '\0';
1068            add_string_str(buf);
1069    }
1070    
1071    static void add_string_date(const char *d)
1072    {
1073            struct tm tm, *tmp;
1074            int n;
1075            time_t t;
1076            char *buf;
1077            int nbuf;
1078            char *env;
1079    
1080            memset(&tm, 0, sizeof(tm));
1081            n = sscanf(d, "%d.%d.%d.%d.%d.%d",
1082                            &tm.tm_year, &tm.tm_mon, &tm.tm_mday,
1083                            &tm.tm_hour, &tm.tm_min, &tm.tm_sec);
1084            tm.tm_mon--;
1085            if(tm.tm_year > 1900)
1086                    tm.tm_year -= 1900;
1087    
1088            env = getenv("TZ");
1089            putenv("TZ=UTC0");
1090            t = mktime(&tm);
1091            if(env)
1092                    setenv("TZ", env, 1);
1093            else
1094                    unsetenv("TZ");
1095    
1096            if(n != 6 || t == (time_t)(-1))
1097            {
1098                    add_string_str("<invalid date>");
1099                    return;
1100            }
1101    
1102            tmp = localtime(&t);
1103            nbuf = (strlen(conf.date_format)+1) * 16;       /* Should be enough to hold all types of expansions */
1104            buf = xmalloc(nbuf);
1105            strftime(buf, nbuf, conf.date_format, tmp);
1106            add_string_str(buf);
1107            xfree(buf);
1108    }
1109    
1110    static void add_string_str_html(const char *s, int maxlen)
1111    {
1112            int l = 0;
1113            char *str = xmalloc(6 * strlen(s) + 1); /* Should hold all char entity-expand */
1114            char *cptr = str;
1115            for(; *s; s++)
1116            {
1117                    if(maxlen && l > abs(maxlen))
1118                    {
1119                            cptr += sprintf(cptr, "...");
1120                            break;
1121                    }
1122                    if(*s < 0x20)
1123                    {
1124                            if(*s == '\n')
1125                            {
1126                                    if(maxlen < 0)
1127                                            *cptr++ = ' ';
1128                                    else
1129                                            cptr += sprintf(cptr, "<br%s>", conf.html_level == HTMLLEVEL_X ? " /" : "");
1130                            }
1131                    }
1132                    else if(*s >= 0x7f || *s == '"')
1133                            cptr += sprintf(cptr, "&#%d;", (int)(unsigned char)*s);
1134                    else if(*s == '<')
1135                            cptr += sprintf(cptr, "&lt;");
1136                    else if(*s == '>')
1137                            cptr += sprintf(cptr, "&gt;");
1138                    else if(*s == '&')
1139                            cptr += sprintf(cptr, "&amp;");
1140                    else if(*s == '"')
1141                            cptr += sprintf(cptr, "&quot;");
1142                    else
1143                            *cptr++ = *s;
1144                    l++;
1145            }
1146            *cptr = '\0';
1147            add_string_str(str);
1148            xfree(str);
1149    }
1150    
1151    static void add_string_str_len(const char *s, int maxlen)
1152    {
1153            int l = strlen(s);
1154            char *str = xmalloc(l + 1 + 3);
1155            strcpy(str, s);
1156            if(maxlen < l)
1157                    sprintf(&str[maxlen], "...");
1158            add_string_str(str);
1159            xfree(str);
1160    }
1161    
1162    static char *expand_string(const char *s, rcsfile_t *rcs, revision_t *r, rev_t *rev, rev_t *prev, tag_t *tag)
1163    {
1164            char nb[32];
1165            char nr[32];
1166            char *base;
1167            char *exp;
1168            int l;
1169            char ch;
1170    
1171            if(!s)
1172                    return xstrdup("");
1173    
1174            zap_string();
1175    
1176            sprintf(nb, "%d", rcs->nbranches);
1177            sprintf(nr, "%d", rcs->nsrev);
1178            for(; *s; s++)
1179            {
1180                    if(*s == '%')
1181                    {
1182                            switch(*++s)
1183                            {
1184                            case 'c':
1185                            case 'C':
1186                                    add_string_str(conf.cvsroot);
1187                                    if(*s == 'C' && conf.cvsroot[0] && conf.cvsroot[strlen(conf.cvsroot)-1] == '/')
1188                                    {
1189                                            /* Strip the trailing '/' */
1190                                            _nstring--;
1191                                            _string[_nstring] = '\0';
1192                                    }
1193                                    break;
1194                            case 'f':
1195                            case 'F':
1196                                    base = strrchr(rcs->file, '/');
1197                                    if(!base)
1198                                            add_string_str(rcs->file);
1199                                    else
1200                                            add_string_str(base+1);
1201                                    if(*s == 'F' && _string[_nstring-1] == 'v' && _string[_nstring-2] == ',')
1202                                    {
1203                                            _nstring -= 2;
1204                                            _string[_nstring] = '\0';
1205                                    }
1206                                    break;
1207                            case 'p':
1208                                    base = strrchr(rcs->file, '/');
1209                                    if(base)
1210                                    {
1211                                            char *c = xstrdup(rcs->file);
1212                                            base = strrchr(c, '/');
1213                                            assert(base != NULL);
1214                                            base[1] = '\0';
1215                                            add_string_str(c);
1216                                            xfree(c);
1217                                    }
1218                                    /*
1219                                     * We should not add anything here because we can encounter
1220                                     * a completely empty path, in which case we do not want
1221                                     * to add any slash. This prevents an inadvertent root redirect.
1222                                     *
1223                                     * else
1224                                     *      add_string_str("/");
1225                                     */
1226                                    break;
1227                            case 'm':
1228                            case 'M':
1229                                    add_string_str(conf.cvsmodule);
1230                                    if(*s == 'M' && conf.cvsmodule[0] && conf.cvsmodule[strlen(conf.cvsmodule)-1] == '/')
1231                                    {
1232                                            /* Strip the trailing '/' */
1233                                            _nstring--;
1234                                            _string[_nstring] = '\0';
1235                                    }
1236                                    break;
1237                            case 'r': add_string_str(nr); break;
1238                            case 'b': add_string_str(nb); break;
1239                            case '%': add_string_ch('%'); break;
1240                            case '0': if(conf.expand[0]) add_string_str(conf.expand[0]); break;
1241                            case '1': if(conf.expand[1]) add_string_str(conf.expand[1]); break;
1242                            case '2': if(conf.expand[2]) add_string_str(conf.expand[2]); break;
1243                            case '3': if(conf.expand[3]) add_string_str(conf.expand[3]); break;
1244                            case '4': if(conf.expand[4]) add_string_str(conf.expand[4]); break;
1245                            case '5': if(conf.expand[5]) add_string_str(conf.expand[5]); break;
1246                            case '6': if(conf.expand[6]) add_string_str(conf.expand[6]); break;
1247                            case '7': if(conf.expand[7]) add_string_str(conf.expand[7]); break;
1248                            case '8': if(conf.expand[8]) add_string_str(conf.expand[8]); break;
1249                            case '9': if(conf.expand[9]) add_string_str(conf.expand[9]); break;
1250                            case 'R': if(rev && rev->rev) add_string_str(rev->rev); break;
1251                            case 'P': if(prev && prev->rev) add_string_str(prev->rev); break;
1252                            case 'B': if(rev && rev->branch) add_string_str(rev->branch); break;
1253                            case 't': if(tag && tag->tag) add_string_str(tag->tag); break;
1254                            case 'd': if(r && r->delta && r->delta->date) add_string_date(r->delta->date); break;
1255                            case 's': if(r && r->delta && r->delta->state) add_string_str(r->delta->state); break;
1256                            case 'a': if(r && r->delta && r->delta->author) add_string_str(r->delta->author); break;
1257                            case 'L':
1258                            case 'l':
1259                                    ch = *s;
1260                                    l = 0;
1261                                    if(s[1] == '[')
1262                                    {
1263                                            char *cptr = strchr(s, ']');
1264                                            char *eptr;
1265                                            if(cptr)
1266                                            {
1267                                                    l = strtol(&s[2], &eptr, 10);
1268                                                    if(eptr != cptr)
1269                                                            l = 0;
1270                                                    else
1271                                                            s = cptr;
1272                                            }
1273                                    }
1274                                    if(!conf.parse_logs)
1275                                            add_string_str("N/A");
1276                                    else if(r && r->dtext && r->dtext->log)
1277                                    {
1278                                            if(ch == 'l')
1279                                                    add_string_str_html(r->dtext->log, l);
1280                                            else
1281                                                    add_string_str_len(r->dtext->log, abs(l));
1282                                    }
1283                                    break;
1284                            case '(':
1285                                    base = dup_string();
1286                                    exp = expand_string(s+1, rcs, r, rev, prev, tag);
1287                                    zap_string();
1288                                    add_string_str(base);
1289                                    add_string_str_html(exp, 0);
1290                                    xfree(base);
1291                                    xfree(exp);
1292                                    /* Find the %) in this recursion level */
1293                                    for(; *s; s++)
1294                                    {
1295                                            if(*s == '%' && s[1] == ')')
1296                                            {
1297                                                    s++;
1298                                                    break;
1299                                            }
1300                                    }
1301                                    if(!*s)
1302                                    {
1303                                            s--;    /* To end outer loop */
1304                                            stack_msg(MSG_WARN, "string expand: Missing %%) in expansion");
1305                                    }
1306                                    break;
1307                            case ')':
1308                                    return dup_string();
1309                            default:
1310                                    add_string_ch('%');
1311                                    add_string_ch(*s);
1312                                    break;
1313                            }
1314                    }
1315                    else
1316                            add_string_ch(*s);
1317            }
1318            return dup_string();
1319    }
1320    
1321    /*
1322     **************************************************************************
1323     * Drawing routines
1324     **************************************************************************
1325     */
1326    static int get_swidth(const char *s, font_t *f)
1327    {
1328            int n;
1329            int m;
1330            if(!s || !*s)
1331                    return 0;
1332    
1333    #if defined(HAVE_GDIMAGESTRINGFT) || defined(HAVE_GDIMAGESTRINGTTF)
1334            if(conf.use_ttf && f->ttfont)
1335            {
1336                    int bb[8];
1337                    char *e;
1338    #ifdef HAVE_GDIMAGESTRINGFT
1339                    e = gdImageStringFT(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1340    #else
1341                    e = gdImageStringTTF(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1342    #endif
1343                    if(!e)
1344                            return bb[2] - bb[6];
1345            }
1346    #endif
1347            for(n = m = 0; *s; n++, s++)
1348            {
1349                    if(*s == '\n')
1350                    {
1351                            if(n > m)
1352                                    m = n;
1353                            n = 0;
1354                    }
1355            }
1356            if(n > m)
1357                    m = n;
1358            return f->gdfont ? m * f->gdfont->w : m;
1359    }
1360    
1361    static int get_sheight(const char *s, font_t *f)
1362    {
1363            int nl;
1364            if(!s || !*s)
1365                    return 0;
1366    
1367    #if defined(HAVE_GDIMAGESTRINGFT) || defined(HAVE_GDIMAGESTRINGTTF)
1368            if(conf.use_ttf && f->ttfont)
1369            {
1370                    int bb[8];
1371                    char *e;
1372    #ifdef HAVE_GDIMAGESTRINGFT
1373                    e = gdImageStringFT(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1374    #else
1375                    e = gdImageStringTTF(NULL, bb, 0, f->ttfont, f->ttsize, 0.0, 0, 0, (char *)s);
1376    #endif
1377                    if(!e)
1378                            return bb[3] - bb[7] + 4;
1379            }
1380    #endif
1381            for(nl = 1; *s; s++)
1382            {
1383                    if(*s == '\n' && s[1])
1384                            nl++;
1385            }
1386            return nl * f->gdfont->h;
1387    }
1388    
1389    static void draw_rbox(gdImagePtr im, int x1, int y1, int x2, int y2, int r, color_t *color, color_t *bgcolor)
1390    {
1391            int r2 = 2*r;
1392            if(!r)
1393                    gdImageFilledRectangle(im, x1, y1, x2, y2, bgcolor->id);
1394    #ifdef HAVE_GDIMAGEFILLEDARC
1395            else
1396            {
1397                    gdImageFilledArc(im, x1+r, y1+r, r2, r2, 180, 270, bgcolor->id, gdArc);
1398                    gdImageFilledArc(im, x2-r, y1+r, r2, r2, 270, 360, bgcolor->id, gdArc);
1399                    gdImageFilledArc(im, x1+r, y2-r, r2, r2,  90, 180, bgcolor->id, gdArc);
1400                    gdImageFilledArc(im, x2-r, y2-r, r2, r2,   0,  90, bgcolor->id, gdArc);
1401                    gdImageFilledRectangle(im, x1+r, y1, x2-r, y1+r, bgcolor->id);
1402                    gdImageFilledRectangle(im, x1, y1+r, x2, y2-r, bgcolor->id);
1403                    gdImageFilledRectangle(im, x1+r, y2-r, x2-r, y2, bgcolor->id);
1404            }
1405    #endif
1406            gdImageLine(im, x1+r, y1, x2-r, y1, color->id);
1407            gdImageLine(im, x1+r, y2, x2-r, y2, color->id);
1408            gdImageLine(im, x1, y1+r, x1, y2-r, color->id);
1409            gdImageLine(im, x2, y1+r, x2, y2-r, color->id);
1410            if(conf.box_shadow)
1411            {
1412                    gdImageLine(im, x1+r+1, y2+1, x2-r, y2+1, black_color.id);
1413                    gdImageLine(im, x2+1, y1+r+1, x2+1, y2-r, black_color.id);
1414            }
1415            if(r)
1416            {
1417                    /* FIXME: Pixelization is not perfect */
1418                    gdImageArc(im, x1+r, y1+r, r2, r2, 180, 270, color->id);
1419                    gdImageArc(im, x2-r, y1+r, r2, r2, 270, 360, color->id);
1420                    gdImageArc(im, x1+r, y2-r, r2, r2,  90, 180, color->id);
1421                    if(conf.box_shadow)
1422                    {
1423                            gdImageArc(im, x2-r+1, y2-r+1, r2, r2,   0,  90, black_color.id);
1424                            gdImageArc(im, x2-r+1, y2-r, r2, r2,   0,  90, black_color.id);
1425                            gdImageArc(im, x2-r, y2-r+1, r2, r2,   0,  90, black_color.id);
1426                    }
1427                    gdImageArc(im, x2-r, y2-r, r2, r2,   0,  90, color->id);
1428    #if !defined(NOGDFILL) && !defined(HAVE_GDIMAGEFILLEDARC)
1429                    /* BUG: We clip manually because libgd segfaults on out of bound values */
1430                    if((x1+x2)/2 >= 0 && (x1+x2)/2 < gdImageSX(im) && (y1+y2)/2 >= 0 && (y1+y2)/2 < gdImageSY(im))
1431                            gdImageFillToBorder(im, (x1+x2)/2, (y1+y2)/2, color->id, bgcolor->id);
1432    #endif
1433            }
1434    }
1435    
1436    static void draw_string(gdImagePtr im, char *s, font_t *f, int x, int y, int align, color_t *c)
1437    {
1438            int h = get_sheight(s, f);
1439            int xx, yy;
1440            switch(align & ALIGN_HX)
1441            {
1442            default:
1443            case ALIGN_HL: xx = 0; break;
1444            case ALIGN_HC: xx = -get_swidth(s, f)/2; break;
1445            case ALIGN_HR: xx = -get_swidth(s, f); break;
1446            }
1447            switch(align & ALIGN_VX)
1448            {
1449            default:
1450            case ALIGN_VT: yy = 0; break;
1451            case ALIGN_VC: yy = h/2; break;
1452            case ALIGN_VB: yy = h; break;
1453            }
1454    #if defined(HAVE_GDIMAGESTRINGFT) || defined(HAVE_GDIMAGESTRINGTTF)
1455            if(conf.use_ttf && f->ttfont)
1456            {
1457                    int bb[8];
1458                    char *e;
1459                    int cid = conf.anti_alias ? c->id : -c->id;
1460    #ifdef HAVE_GDIMAGESTRINGFT
1461                    e = gdImageStringFT(im, bb, cid, f->ttfont, f->ttsize, 0.0, x+xx, y+yy+h-2, (char *)s);
1462    #else
1463                    e = gdImageStringTTF(im, bb, cid, f->ttfont, f->ttsize, 0.0, x+xx, y+yy+h-2, (char *)s);
1464    #endif
1465                    if(!e)
1466                            return;
1467            }
1468    #endif
1469            yy = -yy;
1470            gdImageString(im, f->gdfont, x+xx+1, y+yy, s, c->id);
1471    }
1472    
1473    static void draw_stringnl(gdImagePtr im, char *s, font_t *f, int x, int y, int align, color_t *c)
1474    {
1475            char *t;
1476            char *d;
1477            d = s = xstrdup(s);
1478            do
1479            {
1480                    t = strchr(s, '\n');
1481                    if(t)
1482                            *t = '\0';
1483                    draw_string(im, s, f, x, y, align, c);
1484                    y += get_sheight(s, f);
1485                    s = t+1;
1486            } while(t);
1487            xfree(d);
1488    }
1489    
1490    static void draw_rev(gdImagePtr im, revision_t *r)
1491    {
1492            int lx;
1493            int rx;
1494            int x2;
1495            int i;
1496            int ty;
1497    
1498            if(conf.left_right)
1499            {
1500                    lx = r->cx;
1501                    rx = r->cx + r->w;
1502                    ty = r->y - r->h/2;
1503                    x2 = r->cx + r->w/2;
1504            }
1505            else
1506            {
1507                    lx = r->cx - r->w/2;
1508                    rx = lx + r->w;
1509                    ty = r->y;
1510                    x2 = r->cx;
1511            }
1512            draw_rbox(im, lx, ty, rx, ty+r->h, 0, &conf.rev_color, &conf.rev_bgcolor);
1513            ty += conf.rev_tspace;
1514            if(!conf.rev_hidenumber)
1515            {
1516                    draw_string(im, r->rev->rev, &conf.rev_font, x2, ty, ALIGN_HC, &conf.rev_color);
1517                    ty += get_sheight(r->rev->rev, &conf.rev_font);
1518            }
1519            draw_stringnl(im, r->revtext, &conf.rev_text_font, x2, ty, ALIGN_HC, &conf.rev_text_color);
1520            ty += get_sheight(r->revtext, &conf.rev_text_font);
1521            for(i = 0; i < r->ntags; i++)
1522            {
1523                    draw_string(im, r->tags[i]->tag, &conf.tag_font, x2, ty, ALIGN_HC, &conf.tag_color);
1524                    ty += get_sheight(r->tags[i]->tag, &conf.tag_font) + conf.rev_separator;
1525            }
1526    }
1527    
1528    static void draw_branch_box(gdImagePtr im, branch_t *b, int xp, int yp)
1529    {
1530            int lx;
1531            int rx;
1532            int i;
1533            int yy;
1534            int x2;
1535    
1536            if(conf.left_right)
1537            {
1538                    lx = b->cx;
1539                    rx = lx + b->w;
1540                    x2 = b->cx + b->w/2;
1541            }
1542            else
1543            {
1544                    lx = b->cx - b->w/2;
1545                    rx = lx + b->w;
1546                    x2 = b->cx;
1547            }
1548            draw_rbox(im, lx+xp, yp, rx+xp, yp+b->h, 5, &conf.branch_color, &conf.branch_bgcolor);
1549            yy = conf.branch_tspace;
1550            if(!b->nfolds)
1551            {
1552                    if(!conf.rev_hidenumber)
1553                    {
1554                            draw_string(im, b->branch->branch, &conf.branch_font, x2+xp, yp+yy, ALIGN_HC, &conf.branch_color);
1555                            yy += get_sheight(b->branch->branch, &conf.branch_font);
1556                    }
1557                    for(i = 0; i < b->ntags; i++)
1558                    {
1559                            draw_string(im, b->tags[i]->tag, &conf.branch_tag_font, x2+xp, yp+yy, ALIGN_HC, &conf.branch_tag_color);
1560                            yy += get_sheight(b->tags[i]->tag, &conf.branch_tag_font);
1561                    }
1562            }
1563            else
1564            {
1565                    int y1, y2;
1566                    int tx = lx + b->fw + conf.branch_lspace;
1567                    int nx = tx - get_swidth(" ", &conf.branch_font);
1568                    draw_string(im, b->branch->branch, &conf.branch_font, nx+xp, yp+yy, ALIGN_HR, &conf.branch_color);
1569                    y1 = get_sheight(b->branch->branch, &conf.branch_font);
1570                    draw_string(im, b->tags[0]->tag, &conf.branch_tag_font, tx+xp, yp+yy, ALIGN_HL, &conf.branch_tag_color);
1571                    y2 = get_sheight(b->tags[0]->tag, &conf.branch_font);
1572                    yy += MAX(y1, y2);
1573                    for(i = 0; i < b->nfolds; i++)
1574                    {
1575                            draw_string(im, b->folds[i]->branch->branch, &conf.branch_font, nx+xp, yp+yy, ALIGN_HR, &conf.branch_color);
1576                            y1 = get_sheight(b->folds[i]->branch->branch, &conf.branch_font);
1577                            draw_string(im, b->folds[i]->tags[0]->tag, &conf.branch_tag_font, tx+xp, yp+yy, ALIGN_HL, &conf.branch_tag_color);
1578                            y2 = get_sheight(b->folds[i]->tags[0]->tag, &conf.branch_tag_font);
1579                            yy += MAX(y1, y2);
1580                    }
1581            }
1582    }
1583    
1584    static void draw_branch(gdImagePtr im, branch_t *b)
1585    {
1586            int yy, xx;
1587            int i;
1588            int line[4];
1589            int l;
1590            int sign;
1591    
1592            line[0] = conf.rev_color.id;
1593            line[1] = gdTransparent;
1594            line[1] = gdTransparent;
1595            line[3] = conf.rev_color.id;
1596    
1597            /* Trivial clip the branch */
1598            if(conf.left_right)
1599            {
1600                    if(b->cx > gdImageSX(im) || b->cx+b->tw < 0 || b->y-b->th/2 > gdImageSY(im) || b->y+b->th/2 < 0)
1601                            return;
1602            }
1603            else
1604            {
1605                    if(b->cx-b->tw/2 > gdImageSX(im) || b->cx+b->tw/2 < 0 || b->y > gdImageSY(im) || b->y+b->th < 0)
1606                            return;
1607            }
1608    
1609            draw_branch_box(im, b, 0, conf.left_right ? b->y - b->h/2 : b->y);
1610    
1611            if(conf.left_right)
1612            {
1613                    if(conf.upside_down)
1614                    {
1615                            xx = b->cx;
1616                            for(i = 0; i < b->nrevs; i++)
1617                            {
1618                                    revision_t *r = b->revs[i];
1619                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1620                                    gdImageLine(im, xx, r->y, r->cx+r->w, r->y, gdStyled);
1621                                    for(sign = l = 1; l < conf.thick_lines; l++)
1622                                    {
1623                                            int pp = (l+1)/2*sign;
1624                                            gdImageLine(im, xx, r->y+pp, r->cx+r->w, r->y+pp, gdStyled);
1625                                            sign *= -1;
1626                                    }
1627                                    draw_rev(im, r);
1628                                    xx = r->cx;
1629                            }
1630                            if(conf.branch_dupbox && b->nrevs)
1631                            {
1632                                    i = b->cx - b->tw + b->w;
1633                                    gdImageLine(im, xx, b->y, i+b->w, b->y, conf.rev_color.id);
1634                                    for(sign = l = 1; l < conf.thick_lines; l++)
1635                                    {
1636                                            int pp = (l+1)/2*sign;
1637                                            gdImageLine(im, xx, b->y+pp, i+b->w, b->y+pp, conf.rev_color.id);
1638                                            sign *= -1;
1639                                    }
1640                                    draw_branch_box(im, b, i - b->cx, b->y - b->h/2);
1641                            }
1642                    }
1643                    else
1644                    {
1645                            xx = b->cx + b->w;
1646                            for(i = 0; i < b->nrevs; i++)
1647                            {
1648                                    revision_t *r = b->revs[i];
1649                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1650                                    gdImageLine(im, xx, r->y, r->cx, r->y, gdStyled);
1651                                    for(sign = l = 1; l < conf.thick_lines; l++)
1652                                    {
1653                                            int pp = (l+1)/2*sign;
1654                                            gdImageLine(im, xx, r->y+pp, r->cx, r->y+pp, gdStyled);
1655                                            sign *= -1;
1656                                    }
1657                                    draw_rev(im, r);
1658                                    xx = r->cx + r->w;
1659                            }
1660                            if(conf.branch_dupbox && b->nrevs)
1661                            {
1662                                    i = b->cx + b->tw - b->w;
1663                                    gdImageLine(im, xx, b->y, i, b->y, conf.rev_color.id);
1664                                    for(sign = l = 1; l < conf.thick_lines; l++)
1665                                    {
1666                                            int pp = (l+1)/2*sign;
1667                                            gdImageLine(im, xx, b->y+pp, i, b->y+pp, conf.rev_color.id);
1668                                            sign *= -1;
1669                                    }
1670                                    draw_branch_box(im, b, i - b->cx, b->y - b->h/2);
1671                            }
1672                    }
1673            }
1674            else
1675            {
1676                    if(conf.upside_down)
1677                    {
1678                            yy = b->y;
1679                            for(i = 0; i < b->nrevs; i++)
1680                            {
1681                                    revision_t *r = b->revs[i];
1682                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1683                                    gdImageLine(im, r->cx, yy, r->cx, r->y+r->h, gdStyled);
1684                                    for(sign = l = 1; l < conf.thick_lines; l++)
1685                                    {
1686                                            int pp = (l+1)/2*sign;
1687                                            gdImageLine(im, r->cx+pp, yy, r->cx+pp, r->y+r->h, gdStyled);
1688                                            sign *= -1;
1689                                    }
1690                                    draw_rev(im, r);
1691                                    yy = r->y;
1692                            }
1693                            if(conf.branch_dupbox && b->nrevs)
1694                            {
1695                                    i = b->y - b->th + b->h;
1696                                    gdImageLine(im, b->cx, yy, b->cx, i, conf.rev_color.id);
1697                                    for(sign = l = 1; l < conf.thick_lines; l++)
1698                                    {
1699                                            int pp = (l+1)/2*sign;
1700                                            gdImageLine(im, b->cx+pp, yy, b->cx+pp, i, conf.rev_color.id);
1701                                            sign *= -1;
1702                                    }
1703                                    draw_branch_box(im, b, 0, i);
1704                            }
1705                    }
1706                    else
1707                    {
1708                            yy = b->y + b->h;
1709                            for(i = 0; i < b->nrevs; i++)
1710                            {
1711                                    revision_t *r = b->revs[i];
1712                                    gdImageSetStyle(im, line, r->stripped ? 4 : 1);
1713                                    gdImageLine(im, r->cx, yy, r->cx, r->y, gdStyled);
1714                                    for(sign = l = 1; l < conf.thick_lines; l++)
1715                                    {
1716                                            int pp = (l+1)/2*sign;
1717                                            gdImageLine(im, r->cx+pp, yy, r->cx+pp, r->y, gdStyled);
1718                                            sign *= -1;
1719                                    }
1720                                    draw_rev(im, r);
1721                                    yy = r->y + r->h;
1722                            }
1723                            if(conf.branch_dupbox && b->nrevs)
1724                            {
1725                                    i = b->y + b->th - b->h;
1726                                    gdImageLine(im, b->cx, yy, b->cx, i, conf.rev_color.id);
1727                                    for(sign = l = 1; l < conf.thick_lines; l++)
1728                                    {
1729                                            int pp = (l+1)/2*sign;
1730                                            gdImageLine(im, b->cx+pp, yy, b->cx+pp, i, conf.rev_color.id);
1731                                            sign *= -1;
1732                                    }
1733                                    draw_branch_box(im, b, 0, i);
1734                            }
1735                    }
1736            }
1737    }
1738    
1739    static void draw_connector(gdImagePtr im, branch_t *b)
1740    {
1741            int l;
1742            int sign;
1743            revision_t *r = b->branchpoint;
1744            int x1 = r->cx + r->w/2 + 2;
1745            int y1 = r->y + r->h/2;
1746            int x2 = b->cx;
1747            int y2 = b->y;
1748    
1749            if(conf.left_right)
1750            {
1751                    x2 = r->cx + r->w/2;
1752                    y2 = r->y + r->h/2 + 3;
1753                    x1 = b->cx;
1754                    y1 = b->y;
1755                    if(conf.upside_down)
1756                            x1 += b->w;
1757            }
1758            else
1759            {
1760                    x1 = r->cx + r->w/2 + 2;
1761                    y1 = r->y + r->h/2;
1762                    x2 = b->cx;
1763                    y2 = b->y;
1764                    if(conf.upside_down)
1765                            y2 += b->h;
1766            }
1767            gdImageLine(im, x1, y1, x2, y1, conf.branch_color.id);
1768            gdImageLine(im, x2, y1, x2, y2, conf.branch_color.id);
1769            for(sign = l = 1; l < conf.thick_lines; l++)
1770            {
1771                    int pp = (l+1)/2*sign;
1772                    gdImageLine(im, x1, y1+pp, x2, y1+pp, conf.branch_color.id);
1773                    gdImageLine(im, x2+pp, y1, x2+pp, y2, conf.branch_color.id);
1774                    sign *= -1;
1775            }
1776    }
1777    
1778    static void draw_merges(gdImagePtr im, rcsfile_t *rcs, int dot)
1779    {
1780            int i;
1781            for(i = 0; i < rcs->nmerges; i++)
1782            {
1783                    revision_t *fr;
1784                    revision_t *tr;
1785                    int colorid;
1786                    int x1, x2, y1, y2;
1787                    switch(rcs->merges[i].type)
1788                    {
1789                    case TR_TAG:
1790                            fr = rcs->merges[i].from.tag->logrev;
1791                            tr = rcs->merges[i].to.tag->logrev;
1792                            colorid = conf.merge_color.id;
1793                            break;
1794                    case TR_REVISION:
1795                            fr = rcs->merges[i].from.rev;
1796                            tr = rcs->merges[i].to.rev;
1797                            colorid = conf.merge_cvsnt_color.id;
1798                            break;
1799                    default:
1800                            continue;
1801                    }
1802                    if(!fr || !tr || fr == tr)
1803                            continue;       /* This can happen with detached tags and self-references */
1804                    if(conf.left_right)
1805                    {
1806                            if(fr->branch == tr->branch)
1807                            {
1808                                    y1 = fr->y - fr->h/2;
1809                                    y2 = tr->y - tr->h/2;
1810                            }
1811                            else
1812                            {
1813                                    if(fr->y < tr->y)
1814                                    {
1815                                            y1 = fr->y + fr->h/2;
1816                                            y2 = tr->y - tr->h/2;
1817                                    }
1818                                    else
1819                                    {
1820                                            y1 = fr->y - fr->h/2;
1821                                            y2 = tr->y + tr->h/2;
1822                                    }
1823                            }
1824                            x1 = fr->cx + fr->w/2;
1825                            x2 = tr->cx + tr->w/2;
1826                    }
1827                    else
1828                    {
1829                            if(fr->branch == tr->branch)
1830                            {
1831                                    x1 = fr->cx - fr->w/2;
1832                                    x2 = tr->cx - tr->w/2;
1833                            }
1834                            else
1835                            {
1836                                    if(fr->cx < tr->cx)
1837                                    {
1838                                            x1 = fr->cx + fr->w/2;
1839                                            x2 = tr->cx - tr->w/2;
1840                                    }
1841                                    else
1842                                    {
1843                                            x1 = fr->cx - fr->w/2;
1844                                            x2 = tr->cx + tr->w/2;
1845                                    }
1846                            }
1847                            if(rcs->merges[i].type == TR_TAG)
1848                            {
1849                                    y1 = fr->y + rcs->merges[i].from.tag->yofs;
1850                                    y2 = tr->y + rcs->merges[i].to.tag->yofs;
1851                            }
1852                            else
1853                            {
1854                                    y1 = fr->y + fr->h/2;
1855                                    y2 = tr->y + tr->h/2;
1856                            }
1857                    }
1858                    if(dot && !conf.merge_arrows)
1859                    {
1860                            int o = conf.left_right ? 1 : 0;
1861                            gdImageArc(im, x2, y2+o, 8, 8, 0, 360, colorid);
1862                            /* BUG: We clip manually because libgd segfaults on out of bound values */
1863                            if(x2+1 >= 0 && x2+1 < gdImageSX(im) && y2+o+1 >= 0 && y2+o+1 < gdImageSY(im))
1864                                    gdImageFillToBorder(im, x2+1, y2+o+1, colorid, colorid);
1865                    }
1866                    else if(dot && conf.merge_arrows)
1867                    {
1868                            /*
1869                             * Arrow patch from Haroon Rafique <haroon.rafique@utoronto.ca>
1870                             * Slightly adapted to be more configurable.
1871                             */
1872                            int sx, sy;     /* start point coordinates */
1873                            int ex, ey;     /* end point coordinates */
1874                            double theta;
1875                            double u1, v1, u2, v2;
1876                            gdPoint p[3];
1877    
1878                            sx = x1; sy = y1;
1879                            ex = x2; ey = y2;
1880                            if(conf.left_right)
1881                            {
1882                                    if(fr->branch == tr->branch)
1883                                    {
1884                                            int yy = (y1 < y2 ? y1 : y2) - 5;
1885                                            /* line from (x1,yy) to (x2,yy) */
1886                                            sy = ey = yy;
1887                                    }
1888                                    else
1889                                    {
1890                                            if(y1 > y2)
1891                                            {
1892                                                    /* line from (x1,y1-3) to (x2,y2+3+1) */
1893                                                    sy = y1-3;
1894                                                    ey = y2+3+1;
1895                                            }
1896                                            else
1897                                            {
1898                                                    /* line from (x1,y1+3+1) to (x2,y2-3) */
1899                                                    sy = y1+3+1;
1900                                                    ey = y2-3;
1901                                            }
1902                                    }
1903                            }
1904                            else
1905                            {
1906                                    if(fr->branch == tr->branch)
1907                                    {
1908                                            int xx = (x1 < x2 ? x1 : x2) - 5;
1909                                            /* line from (xx,y1) to (xx,y2) */
1910                                            sx = ex = xx;
1911                                    }
1912                                    else
1913                                    {
1914                                            if(x1 > x2)
1915                                            {
1916                                                    /* line from (x1-3,y1) to (x2+3,y2) */
1917                                                    sx = x1-3;
1918                                                    ex = x2+3;
1919                                            }
1920                                            else
1921                                            {
1922                                                    /* line from (x1+3,y1) to (x2-3,y2) */
1923                                                    sx = x1+3;
1924                                                    ex = x2-3;
1925                                            }
1926                                    }
1927                            }
1928                            /*
1929                             * inspiration for arrow code comes from arrows.c in the
1930                             * graphviz package. Thank you, AT&T
1931                             */
1932                            /* theta in radians */
1933                            theta = atan2((double)(sy-ey), (double)(sx-ex));
1934                            u1 = (double)conf.arrow_length * cos(theta);
1935                            v1 = (double)conf.arrow_length * sin(theta);
1936                            u2 = (double)conf.arrow_width  * cos(theta + M_PI/2.0);
1937                            v2 = (double)conf.arrow_width  * sin(theta + M_PI/2.0);
1938                            /* points of polygon (triangle) */
1939                            p[0].x = ROUND(ex + u1 - u2);
1940                            p[0].y = ROUND(ey + v1 - v2);
1941                            p[1].x = ex;
1942                            p[1].y = ey;
1943                            p[2].x = ROUND(ex + u1 + u2);
1944                            p[2].y = ROUND(ey + v1 + v2);
1945                            /* draw the polygon (triangle) */
1946                            gdImageFilledPolygon(im, p, 3, colorid);
1947                    }
1948                    else
1949                    {
1950                            if(conf.left_right)
1951                            {
1952                                    if(fr->branch == tr->branch)
1953                                    {
1954                                            int yy = (y1 < y2 ? y1 : y2) - 5;
1955                                            gdImageLine(im, x1, y1, x1, yy, colorid);
1956                                            gdImageLine(im, x2, y2, x2, yy, colorid);
1957                                            gdImageLine(im, x1, yy, x2, yy, colorid);
1958                                    }
1959                                    else
1960                                    {
1961                                            if(y1 > y2)
1962                                            {
1963                                                    gdImageLine(im, x1, y1, x1, y1-3, colorid);
1964                                                    gdImageLine(im, x2, y2+1, x2, y2+3+1, colorid);
1965                                                    gdImageLine(im, x1, y1-3, x2, y2+3+1, colorid);
1966                                            }
1967                                            else
1968                                            {
1969                                                    gdImageLine(im, x1, y1+1, x1, y1+3+1, colorid);
1970                                                    gdImageLine(im, x2, y2, x2, y2-3, colorid);
1971                                                    gdImageLine(im, x1, y1+3+1, x2, y2-3, colorid);
1972                                            }
1973                                    }
1974                            }
1975                            else
1976                            {
1977                                    if(fr->branch == tr->branch)
1978                                    {
1979                                            int xx = (x1 < x2 ? x1 : x2) - 5;
1980                                            gdImageLine(im, xx, y1, x1, y1, colorid);
1981                                            gdImageLine(im, xx, y2, x2, y2, colorid);
1982                                            gdImageLine(im, xx, y1, xx, y2, colorid);
1983                                    }
1984                                    else
1985                                    {
1986                                            if(x1 > x2)
1987                                            {
1988                                                    gdImageLine(im, x1, y1, x1-3, y1, colorid);
1989                                                    gdImageLine(im, x2, y2, x2+3, y2, colorid);
1990                                                    gdImageLine(im, x1-3, y1, x2+3, y2, colorid);
1991                                            }
1992                                            else
1993                                            {
1994                                                    gdImageLine(im, x1, y1, x1+3, y1, colorid);
1995                                                    gdImageLine(im, x2, y2, x2-3, y2, colorid);
1996                                                    gdImageLine(im, x1+3, y1, x2-3, y2, colorid);
1997                                            }
1998                                    }
1999                            }
2000                    }
2001          }          }
2002          switch(align & ALIGN_VX)  }
2003    
2004    static void draw_messages(gdImagePtr im, int offset)
2005    {
2006            int i;
2007    
2008            for(i = 0; i < nmsg_stack; i++)
2009            {
2010                    draw_stringnl(im, msg_stack[i].msg, &conf.msg_font, conf.margin_left, offset, ALIGN_HL|ALIGN_VT, &conf.msg_color);
2011                    offset += msg_stack[i].h;
2012            }
2013    }
2014    
2015    static void alloc_color(gdImagePtr im, color_t *c)
2016    {
2017            c->id = gdImageColorAllocate(im, c->r, c->g, c->b);
2018    }
2019    
2020    static gdImagePtr make_image(rcsfile_t *rcs)
2021    {
2022            gdImagePtr im;
2023            int i;
2024            char *cptr;
2025            int w, h;
2026            int subx = 0, suby = 0;
2027            int subw, subh;
2028            int msgh = 0;
2029    
2030            if(subtree_branch)
2031            {
2032                    subw = 0;
2033                    subh = 0;
2034                    if(subtree_rev)
2035                    {
2036                            for(i = 0; i < subtree_rev->nbranches; i++)
2037                                    calc_subtree_size(subtree_rev->branches[i], &subx, &suby, &subw, &subh);
2038                    }
2039                    else
2040                            calc_subtree_size(subtree_branch, &subx, &suby, &subw, &subh);
2041            }
2042            else
2043            {
2044                    subw = rcs->tw;
2045                    subh = rcs->th;
2046            }
2047    
2048            cptr = expand_string(conf.title, rcs, NULL, NULL, NULL, NULL);
2049            w = subw + conf.margin_left + conf.margin_right;
2050            h = subh + conf.margin_top + conf.margin_bottom;
2051            i = get_swidth(cptr, &conf.title_font);
2052            if(i > w)
2053                    w = i;
2054    
2055            if(!quiet && nmsg_stack)
2056            {
2057                    int msgw = 0;
2058                    for(i = 0; i < nmsg_stack; i++)
2059                    {
2060                            int ww = msg_stack[i].w = get_swidth(msg_stack[i].msg, &conf.msg_font);
2061                            int hh = msg_stack[i].h = get_sheight(msg_stack[i].msg, &conf.msg_font);
2062                            msgh += hh;
2063                            h += hh;
2064                            if(ww > msgw)
2065                                    msgw = ww;
2066                    }
2067                    if(msgw > w)
2068                            w = msgw;
2069            }
2070    
2071            im = gdImageCreate(w, h);
2072            alloc_color(im, &conf.color_bg);
2073            alloc_color(im, &conf.tag_color);
2074            alloc_color(im, &conf.rev_color);
2075            alloc_color(im, &conf.rev_bgcolor);
2076            alloc_color(im, &conf.rev_text_color);
2077            alloc_color(im, &conf.branch_color);
2078            alloc_color(im, &conf.branch_tag_color);
2079            alloc_color(im, &conf.branch_bgcolor);
2080            alloc_color(im, &conf.title_color);
2081            alloc_color(im, &conf.merge_color);
2082            alloc_color(im, &conf.merge_cvsnt_color);
2083            alloc_color(im, &conf.msg_color);
2084            alloc_color(im, &black_color);
2085            alloc_color(im, &white_color);
2086    
2087            if(conf.transparent_bg)
2088                    gdImageColorTransparent(im, conf.color_bg.id);
2089    
2090            if(!conf.merge_front)
2091                    draw_merges(im, rcs, 0);
2092    
2093            for(i = 0; i < rcs->nbranches; i++)
2094            {
2095                    if(!rcs->branches[i]->folded && !(subtree_branch && !rcs->branches[i]->subtree_draw))
2096                            draw_branch(im, rcs->branches[i]);
2097            }
2098    
2099            draw_merges(im, rcs, 1);        /* The dots of the merge dest */
2100    
2101            for(i = 0; i < rcs->nbranches; i++)
2102            {
2103                    if(rcs->branches[i]->branchpoint)
2104                            draw_connector(im, rcs->branches[i]);
2105            }
2106    
2107            /* Clear the margins if we have a partial tree */
2108            if(subtree_branch)
2109            {
2110                    gdImageFilledRectangle(im, 0, 0, w-1, conf.margin_top-1, conf.color_bg.id);
2111                    gdImageFilledRectangle(im, 0, 0, conf.margin_left-1, h-1, conf.color_bg.id);
2112                    gdImageFilledRectangle(im, 0, h-conf.margin_bottom, w-1, h-1, conf.color_bg.id);
2113                    gdImageFilledRectangle(im, w-conf.margin_right, 0, w-1, h-1, conf.color_bg.id);
2114            }
2115    
2116            draw_stringnl(im, cptr, &conf.title_font, conf.title_x, conf.title_y, conf.title_align, &conf.title_color);
2117            xfree(cptr);
2118    
2119            if(conf.merge_front)
2120                    draw_merges(im, rcs, 0);
2121    
2122            if(!quiet)
2123                    draw_messages(im, h - conf.margin_bottom/2 - msgh);
2124    
2125            return im;
2126    }
2127    
2128    /*
2129     **************************************************************************
2130     * Layout routines
2131     *
2132     * Branch BBox:
2133     *      left   = center_x - total_width / 2     (cx-tw)/2
2134     *      right  = center_x + total_width / 2     (cx+tw)/2
2135     *      top    = y_pos                          (y)
2136     *      bottom = y_pos + total_height           (y+th)
2137     *
2138     * Margins of branches:
2139     *
2140     *         .              .
2141     *         .              .
2142     *         +--------------+
2143     *            ^
2144     *            | branch_margin           .
2145     *            v                         .
2146     * ----------------+                    .
2147     *                 | ^                  |
2148     *                 | | branch_connect   |
2149     *                 | v                  |
2150     *..-+      +t-----+------+      +------+------+
2151     *   |      l             |      |             |
2152     *   | <--> | branch bbox | <--> | branch bbox |
2153     *   |   |  |             r   |  |             |
2154     *..-+   |  +------------b+   |  +-------------+
2155     *       |    ^               branch_margin
2156     *       |    | branch_margin
2157     *       |    v
2158     *       |  +-------------+
2159     *       |  .             .
2160     *       |  .             .
2161     *       |
2162     *       branch_margin
2163     *
2164     * FIXME: There are probable som +/-1 errors in the code...
2165     *        (notably shadows are not calculated in the margins)
2166     **************************************************************************
2167     */
2168    static void move_branch(branch_t *b, int x, int y)
2169    {
2170            int i;
2171            b->cx += x;
2172            b->y += y;
2173            for(i = 0; i < b->nrevs; i++)
2174            {
2175                    b->revs[i]->cx += x;
2176                    b->revs[i]->y += y;
2177            }
2178    }
2179    
2180    static void initial_reposition_branch(revision_t *r, int *x, int *w)
2181    {
2182            int i, j;
2183            for(j = 0; j < r->nbranches; j++)
2184            {
2185                    branch_t *b = r->branches[j];
2186                    *x += *w + conf.rev_minline + b->tw/2 - b->cx;
2187                    *w = b->tw/2;
2188                    move_branch(b, *x, r->y + r->h/2 + conf.branch_connect);
2189                    *x = b->cx;
2190                    /* Recurse to move branches of branched revisions */
2191                    for(i = b->nrevs-1; i >= 0; i--)
2192                    {
2193                            initial_reposition_branch(b->revs[i], x, w);
2194                    }
2195            }
2196    }
2197    
2198    static void initial_reposition_branch_lr(revision_t *r, int *y, int *h)
2199    {
2200            int i, j;
2201            for(j = 0; j < r->nbranches; j++)
2202            {
2203                    branch_t *b = r->branches[j];
2204                    *y += *h + conf.rev_minline + b->th/2 - b->y;
2205                    *h = b->th/2;
2206                    move_branch(b, r->cx + r->w/2 + conf.branch_connect, *y);
2207                    *y = b->y;
2208                    /* Recurse to move branches of branched revisions */
2209                    for(i = b->nrevs-1; i >= 0; i--)
2210                    {
2211                            initial_reposition_branch_lr(b->revs[i], y, h);
2212                    }
2213            }
2214    }
2215    
2216    static void rect_union(int *x, int *y, int *w, int *h, branch_t *b)
2217    {
2218            int x1 = *x;
2219            int x2 = x1 + *w;
2220            int y1 = *y;
2221            int y2 = y1 + *h;
2222            int xx1;
2223            int xx2;
2224            int yy1;
2225            int yy2;
2226    
2227            if(conf.left_right)
2228            {
2229                    xx1 = b->cx;
2230                    yy1 = b->y - b->th/2;
2231            }
2232            else
2233            {
2234                    xx1 = b->cx - b->tw/2;
2235                    yy1 = b->y;
2236            }
2237            xx2 = xx1 + b->tw;
2238            yy2 = yy1 + b->th;
2239    
2240            x1 = MIN(x1, xx1);
2241            x2 = MAX(x2, xx2);
2242            y1 = MIN(y1, yy1);
2243            y2 = MAX(y2, yy2);
2244            *x = x1;
2245            *y = y1;
2246            *w = x2 - x1;
2247            *h = y2 - y1;
2248    }
2249    
2250    static void calc_subtree_size(branch_t *b, int *x, int *y, int *w, int *h)
2251    {
2252            int i, j;
2253    
2254            rect_union(x, y, w, h, b);
2255    
2256            for(i = 0; i < b->nrevs; i++)
2257            {
2258                    for(j = 0; j < b->revs[i]->nbranches; j++)
2259                            calc_subtree_size(b->revs[i]->branches[j], x, y, w, h);
2260            }
2261    }
2262    
2263    static int branch_intersects(int top, int bottom, int left, branch_t *b)
2264    {
2265            int br = b->cx + b->tw/2;
2266            int bt = b->y - conf.branch_connect - conf.branch_margin/2;
2267            int bb = b->y + b->th + conf.branch_margin/2;
2268            return !(bt > bottom || bb < top || br >= left);
2269    }
2270    
2271    static int branch_intersects_lr(int left, int right, int top, branch_t *b)
2272    {
2273            int bt = b->y + b->th/2;
2274            int bl = b->cx - conf.branch_connect - conf.branch_margin/2;
2275            int br = b->cx + b->tw + conf.branch_margin/2;
2276            return !(bl > right || br < left || bt >= top);
2277    }
2278    
2279    static int kern_branch(rcsfile_t *rcs, branch_t *b)
2280    {
2281            int left = b->cx - b->tw/2;
2282            int top = b->y - conf.branch_connect - conf.branch_margin/2;
2283            int bottom = b->y + b->th + conf.branch_margin/2;
2284            int i;
2285            int xpos = 0;
2286    
2287            for(i = 0; i < rcs->nbranches; i++)
2288            {
2289                    branch_t *bp = rcs->branches[i];
2290                    if(bp == b)
2291                            continue;
2292                    if(branch_intersects(top, bottom, left, bp))
2293                    {
2294                            int m = bp->cx + bp->tw/2 + conf.branch_margin;
2295                            if(m > xpos)
2296                                    xpos = m;
2297                    }
2298            }
2299            if(xpos && (b->cx - b->tw/2) - xpos > 0)
2300            {
2301                    move_branch(b, xpos - (b->cx - b->tw/2), 0);
2302                    return 1;
2303            }
2304            return 0;
2305    }
2306    
2307    static int kern_branch_lr(rcsfile_t *rcs, branch_t *b)
2308    {
2309            int top = b->y - b->th/2;
2310            int left = b->cx - conf.branch_connect - conf.branch_margin/2;
2311            int right = b->cx + b->tw + conf.branch_margin/2;
2312            int i;
2313            int ypos = 0;
2314    
2315            for(i = 0; i < rcs->nbranches; i++)
2316            {
2317                    branch_t *bp = rcs->branches[i];
2318                    if(bp == b)
2319                            continue;
2320                    if(branch_intersects_lr(left, right, top, bp))
2321                    {
2322                            int m = bp->y + bp->th/2 + conf.branch_margin;
2323                            if(m > ypos)
2324                                    ypos = m;
2325                    }
2326            }
2327            if(ypos && (b->y - b->th/2) - ypos > 0)
2328            {
2329                    move_branch(b, 0, ypos - (b->y - b->th/2));
2330                    return 1;
2331            }
2332            return 0;
2333    }
2334    
2335    static int kern_tree(rcsfile_t *rcs)
2336    {
2337            int i;
2338            int moved;
2339            int safeguard;
2340            int totalmoved = 0;
2341            for(moved = 1, safeguard = LOOPSAFEGUARD; moved && safeguard; safeguard--)
2342            {
2343                    moved = 0;
2344                    for(i = 1; i < rcs->nbranches; i++)
2345                    {
2346                            if(conf.left_right)
2347                                    moved += kern_branch_lr(rcs, rcs->branches[i]);
2348                            else
2349                                    moved += kern_branch(rcs, rcs->branches[i]);
2350                    }
2351                    totalmoved += moved;
2352    #ifdef DEBUG
2353                    fprintf(stderr, "kern_tree: moved=%d\n", moved);
2354    #endif
2355            }
2356            if(!safeguard)
2357                    stack_msg(MSG_WARN, "kern_tree: safeguard terminated possible infinite loop; please report.");
2358            return totalmoved;
2359    }
2360    
2361    static int index_of_revision(revision_t *r)
2362    {
2363            branch_t *b = r->branch;
2364            int i;
2365            for(i = 0; i < b->nrevs; i++)
2366            {
2367                    if(r == b->revs[i])
2368                            return i;
2369            }
2370            stack_msg(MSG_ERR, "index_of_revision: Cannot find revision in branch\n");
2371            return 0;
2372    }
2373    
2374    static void branch_bbox(branch_t *br, int *l, int *r, int *t, int *b)
2375    {
2376            if(l)   *l = br->cx - br->tw/2;
2377            if(r)   *r = br->cx + br->tw/2;
2378            if(t)   *t = br->y;
2379            if(b)   *b = br->y + br->th + ((conf.branch_dupbox && br->nrevs) ? conf.rev_minline + br->h : 0);
2380    }
2381    
2382    static void branch_ext_bbox(branch_t *br, int *l, int *r, int *t, int *b)
2383    {
2384            int extra = conf.branch_margin & 1;     /* Correct +/-1 error on div 2 */
2385            branch_bbox(br, l, r, t, b);
2386            if(l)   *l -= conf.branch_margin/2;
2387            if(r)   *r += conf.branch_margin/2 + extra;
2388            if(t)   *t -= conf.branch_connect + conf.branch_margin/2;
2389            if(b)   *b += conf.branch_margin/2 + extra;
2390    }
2391    
2392    static int branch_distance(branch_t *br1, branch_t *br2)
2393    {
2394            int l1, r1, t1, b1;
2395            int l2, r2, t2, b2;
2396            assert(br1 != NULL);
2397            assert(br2 != NULL);
2398            branch_bbox(br1, &l1, &r1, NULL, NULL);
2399            branch_bbox(br2, &l2, &r2, NULL, NULL);
2400            branch_ext_bbox(br1, NULL, NULL, &t1, &b1);
2401            branch_ext_bbox(br2, NULL, NULL, &t2, &b2);
2402            /* Return:
2403             * - 0 if branches have no horizontal overlap
2404             * - positive if b1 is left of b2
2405             * - negative if b2 is left of b1
2406             */
2407            if((t1 > t2 && t1 < b2) || (b1 > t2 && b1 < b2))
2408                    return l1 < l2 ? l2 - r1 : -(l1 - r2);
2409            else
2410                    return 0;
2411    }
2412    
2413    static int space_needed(branch_t *br1, branch_t *br2)
2414    {
2415            int t1, b1;
2416            int t2, b2;
2417            assert(br1 != NULL);
2418            assert(br2 != NULL);
2419            assert(br1->cx < br2->cx);      /* br1 must be left of br2 */
2420            branch_ext_bbox(br1, NULL, NULL, &t1, &b1);
2421            branch_ext_bbox(br2, NULL, NULL, &t2, &b2);
2422            /* Return:
2423             * - positive if top br1 is located lower than br2
2424             * - negatve is top br2 is located lower than br1
2425             */
2426            if(t1 > t2)
2427                    return -(t1 - b2);
2428            else
2429                    return t2 - b1;
2430    }
2431    
2432    static void move_yr_branch(branch_t *b, int dy)
2433    {
2434            int i, j;
2435    #ifdef DEBUG
2436    /*      fprintf(stderr, "move_yr_branch: b=%s, dy=%d\n", b->branch->branch, dy);*/
2437    #endif
2438            b->y += dy;
2439            for(i = 0; i < b->nrevs; i++)
2440          {          {
2441          default:                  b->revs[i]->y += dy;
2442          case ALIGN_VT: yy = 0; break;                  for(j = 0; j < b->revs[i]->nbranches; j++)
2443          case ALIGN_VC: yy = -get_sheight(s, f)/2; break;                  {
2444          case ALIGN_VB: yy = -get_sheight(s, f); break;  #ifdef DEBUG
2445    /*                      fprintf(stderr, ".");*/
2446    #endif
2447                            move_yr_branch(b->revs[i]->branches[j], dy);
2448                    }
2449          }          }
         gdImageString(im, *f, x+xx+1, y+yy, s, c->id);  
2450  }  }
2451    
2452  void draw_rev(gdImagePtr im, int cx, int ty, revision_t *r)  static void move_trunk(revision_t *r, int dy)
2453  {  {
2454          int lx = cx - r->w/2;          int i, j;
2455          int rx = lx + r->w;          branch_t *b = r->branch;
2456          int i;          b->th += dy;
2457          draw_rbox(im, lx, ty, rx, ty+r->h, 0, &conf.rev_color);          for(i = index_of_revision(r); i < b->nrevs; i++)
         ty += conf.rev_tspace;  
         draw_string(im, r->rev->rev, &conf.rev_font, cx, ty, ALIGN_HC, &conf.rev_color);  
         ty += get_sheight(r->rev->rev, &conf.rev_font);  
         for(i = 0; i < r->ntags; i++)  
2458          {          {
2459                  draw_string(im, r->tags[i]->tag, &conf.tag_font, cx, ty, ALIGN_HC, &conf.tag_color);  #ifdef DEBUG
2460                  ty += get_sheight(r->tags[i]->tag, &conf.tag_font);                  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);
2461    #endif
2462                    b->revs[i]->y += dy;
2463                    for(j = 0; j < b->revs[i]->nbranches; j++)
2464                    {
2465                            move_yr_branch(b->revs[i]->branches[j], dy);
2466                    }
2467          }          }
2468  }  }
2469    
2470  void draw_branch(gdImagePtr im, int cx, int ty, branch_t *b)  static int space_below(rcsfile_t *rcs, revision_t *r)
2471  {  {
2472          int lx = cx - b->w/2;          int i, j;
2473          int rx = lx + b->w;          int bl, br, bb;
2474          int yy;          int space = INT_MAX;
2475          int i;          branch_t *b = r->branch;
2476          draw_rbox(im, lx, ty, rx, ty+b->h, 5, &conf.branch_color);          branch_t *minb = NULL;
2477          yy = conf.branch_tspace;  
2478          draw_string(im, b->branch, &conf.branch_font, cx, ty+yy, ALIGN_HC, &conf.branch_color);          branch_ext_bbox(b, &bl, &br, NULL, &bb);
2479          yy += get_sheight(b->branch, &conf.branch_font);          for(i = 0; i < rcs->nbranches; i++)
         if(b->tag)  
2480          {          {
2481                  draw_string(im, b->tag->tag, &conf.branch_font, cx, ty+yy, ALIGN_HC, &conf.branch_color);                  int tbl, tbr, tbt;
2482                    branch_t *tb = rcs->branches[i];
2483                    branch_ext_bbox(tb, &tbl, &tbr, &tbt, NULL);
2484                    if(tb == b)
2485                            continue;
2486                    if(tbt > bb)    /* Must be below our branch */
2487                    {
2488                            if(tb->branchpoint)     /* Take account for the horiz connector */
2489                                    tbl = tb->branchpoint->cx + tb->branchpoint->branch->tw/2;
2490                            if((bl >= tbl && bl <= tbr) || (br <= tbr && br >= tbl))
2491                            {
2492                                    int s = tbt - bb - conf.branch_connect;
2493                                    if(s < space)
2494                                    {
2495                                            space = s;
2496                                            minb = tb;
2497                                    }
2498                            }
2499                    }
2500          }          }
2501            if(b->branchpoint)
         ty += b->h;  
         for(i = 0; i < b->nrevs; i++)  
2502          {          {
2503                  gdImageLine(im, cx, ty, cx, ty+conf.rev_minline, conf.rev_color.id);                  for(i = index_of_revision(r); i < b->nrevs; i++)
2504                  ty += conf.rev_minline;                  {
2505                  draw_rev(im, cx, ty, b->revs[i]);                          for(j = 0; j < b->revs[i]->nbranches; j++)
2506                  ty += b->revs[i]->h;                          {
2507                                    int s = space_below(rcs, b->revs[i]->branches[j]->revs[0]);
2508                                    if(s < space)
2509                                            space = s;
2510                            }
2511                    }
2512          }          }
2513    #ifdef DEBUG
2514            fprintf(stderr, "space_below: from %s have %d to %s\n", b->branch->branch, space, minb ? minb->branch->branch : "<recursed>");
2515    #endif
2516            return space;
2517  }  }
2518    
2519  static char *_title;  static int space_available(rcsfile_t *rcs, branch_t *colbr, branch_t *tagbr, int *nl, revision_t **bpcommon)
 static int _ntitle;  
 static int _natitle;  
   
 void add_title_str(const char *s)  
2520  {  {
2521          int l = strlen(s) + 1;          int i;
2522          if(_ntitle + l > _natitle)          int space = 0;
2523            int nlinks = 0;
2524            revision_t *r;
2525            branch_t *b;
2526            branch_t *ancestor;
2527            revision_t *branchpoint;
2528    
2529            if(!tagbr->branchpoint || !colbr->branchpoint)
2530          {          {
2531                  _natitle += 128;                  stack_msg(MSG_WARN, "space_available: Trying to stretch the top?");
2532                  _title = xrealloc(_title, _natitle * sizeof(_title[0]));                  return 0;
2533          }          }
         memcpy(_title+_ntitle, s, l);  
         _ntitle += l-1;  
 }  
2534    
2535  void add_title_ch(int ch)          r = colbr->branchpoint;
2536  {          b = r->branch;
2537          char buf[2];          branchpoint = tagbr->branchpoint;
2538          buf[0] = ch;          ancestor = branchpoint->branch;
2539          buf[1] = '\0';          assert(b != NULL);
2540          add_title_str(buf);          assert(ancestor != NULL);
2541    
2542            while(1)
2543            {
2544                    int s;
2545                    int rtag = b == ancestor ? index_of_revision(branchpoint)+1 : 0;
2546                    for(i = index_of_revision(r); i >= rtag; i--)
2547                    {
2548                            if(i > 0)
2549                                    s = b->revs[i]->y - (b->revs[i-1]->y + b->revs[i-1]->h);
2550                            else
2551                                    s = b->revs[i]->y - (b->y + b->h);
2552                            if(s < conf.rev_maxline)
2553                            {
2554                                    space += conf.rev_maxline - s;
2555                                    nlinks++;
2556                            }
2557                    }
2558                    s = space_below(rcs, r);
2559                    if(s < space)
2560                            space = s;
2561    #ifdef DEBUG
2562                    if(space < 0)
2563                            return -1;
2564    #endif
2565                    if(b == ancestor)
2566                            break;
2567                    r = b->branchpoint;
2568                    if(!r)
2569                    {
2570                            /* Not a common ancestor */
2571                            r = colbr->branchpoint;
2572                            b = r->branch;
2573                            branchpoint = ancestor->branchpoint;
2574                            if(!branchpoint)
2575                            {
2576                                    stack_msg(MSG_WARN, "space_available: No common ancestor?");
2577                                    return 0;
2578                            }
2579                            ancestor = branchpoint->branch;
2580                            assert(ancestor != NULL);
2581                            nlinks = 0;
2582                            space = 0;
2583                            continue;       /* Restart with a new ancestor */
2584                    }
2585                    b = r->branch;
2586            }
2587            if(nl)
2588                    *nl = nlinks;           /* Return the number of links that can stretch */
2589            if(bpcommon)
2590                    *bpcommon = branchpoint;        /* Return the ancestral branchpoint on the common branch */
2591            return space;
2592  }  }
2593    
2594  char *expand_title(rcsfilelog_t *rcs)  static int stretch_branches(rcsfile_t *rcs, branch_t *br1, branch_t *br2, int totalstretch)
2595  {  {
2596          char nb[32];          revision_t *r;
2597          char nr[32];          revision_t *bpcommon = NULL;
2598          char *cptr;          branch_t *ancestor = NULL;
2599            branch_t *b;
2600            int i;
2601            int space;
2602            int nlinks;
2603            int dy;
2604            int rest;
2605    
2606            space = space_available(rcs, br1, br2, &nlinks, &bpcommon);
2607            if(bpcommon)
2608                    ancestor = bpcommon->branch;
2609    
2610          sprintf(nb, "%d", rcs->nbranches);  #ifdef DEBUG
2611          sprintf(nr, "%d", rcs->nrevs);          if(space == -1)
2612          for(cptr = conf.title; *cptr; cptr++)                  return 0;
2613            fprintf(stderr, "stretch_branches: space available %d over %d links common %s\n", space, nlinks, ancestor->branch->branch);
2614    #endif
2615            if(space < totalstretch)
2616                    return 0;
2617    
2618            dy = totalstretch / nlinks;
2619            rest = totalstretch - dy * nlinks;
2620    
2621            r = br1->branchpoint;
2622            b = r->branch;
2623            while(1)
2624          {          {
2625                  if(*cptr == '%')                  int rtag = b == ancestor ? index_of_revision(bpcommon)+1 : 0;
2626                    for(i = index_of_revision(r); i >= rtag; i--)
2627                  {                  {
2628                          switch(*++cptr)                          int s, q;
2629                            if(i > 0)
2630                                    s = b->revs[i]->y - (b->revs[i-1]->y + b->revs[i-1]->h);
2631                            else
2632                                    s = b->revs[i]->y - (b->y + b->h);
2633                            q = conf.rev_maxline - s;
2634                            if(q > 0)
2635                          {                          {
2636                          case 'c': add_title_str(conf.cvsroot); break;                                  int d = rest ? rest/nlinks+1 : 0;
2637                          case 'f': add_title_str(rcs->name); break;                                  if(q >= dy+d)
2638                          case 'm': add_title_str(conf.cvsmodule); break;                                  {
2639                          case 'r': add_title_str(nr); break;                                          move_trunk(b->revs[i], dy+d);
2640                          case 'b': add_title_str(nb); break;                                  }
2641                          case '%': add_title_ch('%'); break;                                  else
2642                          default:                                  {
2643                                  add_title_ch('%');                                          move_trunk(b->revs[i], q);
2644                                  add_title_ch(*cptr);                                          rest += dy+d - q;
2645                                  break;                                  }
2646                                    rest -= d;
2647                                    nlinks--;
2648                          }                          }
2649                  }                  }
2650                  else                  if(b == ancestor)
2651                          add_title_ch(*cptr);                          break;
2652                    r = b->branchpoint;
2653                    assert(r != NULL);      /* else 'space_available' wouldn't have returned positively */
2654                    b = r->branch;
2655          }          }
2656          return _title;          return 1;
2657  }  }
2658    
2659  void draw_title(gdImagePtr im, char *title)  static branch_t *find_collision_branch(rcsfile_t *rcs, branch_t *b)
2660  {  {
2661          char *t;          int i;
2662          char *s = title;          int dist = INT_MAX;
2663          int x = conf.title_x;          branch_t *col = NULL;
         int y = conf.title_y;  
         do  
         {  
                 t = strchr(s, '\n');  
                 if(t)  
                         *t = '\0';  
                 draw_string(im, s, &conf.title_font, x, y, conf.title_align, &conf.title_color);  
                 y += get_sheight(s, &conf.title_font);  
                 s = t+1;  
         } while(t);  
 }  
2664    
2665  void draw_connector(gdImagePtr im, branch_t *b)          for(i = 0; i < rcs->nbranches; i++)
2666  {          {
2667          revision_t *r = b->branchpoint;                  int t = branch_distance(rcs->branches[i], b);
2668          int x1 = r->x + r->w/2 + 2;                  if(t > 0 && t < dist)
2669          int y1 = r->y + r->h/2;                  {
2670          int x2 = b->x;                          dist = t;
2671          int y2 = b->y;                          col = rcs->branches[i];
2672          gdImageLine(im, x1, y1, x2, y1, conf.branch_color.id);                  }
2673          gdImageLine(im, x2, y1, x2, y2, conf.branch_color.id);          }
2674            return col;
2675  }  }
2676    
2677  gdImagePtr make_image(rcsfilelog_t *rcs)  static void auto_stretch(rcsfile_t *rcs)
2678  {  {
         gdImagePtr im;  
2679          int i;          int i;
2680            int safeguard;
2681    
2682          im = gdImageCreate(rcs->tw+conf.margin_left+conf.margin_right, rcs->th+conf.margin_top+conf.margin_bottom);          for(i = 0, safeguard = LOOPSAFEGUARD; i < rcs->nbranches && safeguard; i++)
         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);  
   
         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++)  
2683          {          {
2684                  if(rcs->branches[i]->branchpoint)                  int bl, pr;
2685                          draw_connector(im, rcs->branches[i]);                  branch_t *b = rcs->branches[i];
2686                    if(!b->branchpoint)
2687                            continue;
2688                    branch_bbox(b, &bl, NULL, NULL, NULL);
2689                    branch_bbox(b->branchpoint->branch, NULL, &pr, NULL, NULL);
2690                    if(bl - conf.branch_margin - pr > 0)
2691                    {
2692                            branch_t *col;
2693                            int spaceneeded;
2694                            /* There is a potential to move branch b further left.
2695                             * All branches obstructing this one from moving further
2696                             * left must be originating from revisions below
2697                             * b->branchpoint until a common ancester.
2698                             * So, we search all branches for a branch that lies left
2699                             * of b and is closest to b. This is then the collission
2700                             * branch that needs to be moved.
2701                             */
2702                            col = find_collision_branch(rcs, b);
2703                            if(!col)
2704                                    continue;
2705                            spaceneeded = space_needed(col, b);
2706                            if(spaceneeded < 0)
2707                                    continue;
2708    #ifdef DEBUG
2709                            fprintf(stderr, "auto_stretch: %s collides %s need %d\n", b->branch->branch, col->branch->branch, spaceneeded);
2710    #endif
2711                            /* Trace the collision branch back to find the common ancester
2712                             * of both col and b. All revisions encountered while traversing
2713                             * backwards must be stretched, including all revisions on the
2714                             * common ancester from where the branches sprout.
2715                             */
2716                            if(stretch_branches(rcs, col, b, spaceneeded))
2717                            {
2718                                    if(kern_tree(rcs))
2719                                    {
2720                                            /* Restart the process because movement can
2721                                             * cause more movement.
2722                                             */
2723                                            i = 0 - 1;      /* -1 for the i++ of the loop */
2724                                            safeguard--;    /* Prevent infinite loop, just in case */
2725                                    }
2726                                    /*return;*/
2727                            }
2728                    }
2729          }          }
2730          draw_title(im, expand_title(rcs));          if(!safeguard)
2731                    stack_msg(MSG_ERR, "auto_stretch: safeguard terminated possible infinite loop; please report.");
         return im;  
2732  }  }
2733    
2734  void move_branch(branch_t *b, int x, int y)  static void fold_branch(rcsfile_t *rcs, revision_t *r)
2735  {  {
2736          int i;          int i, j;
2737          b->x += x;          branch_t *btag = NULL;
2738          b->y += y;  
2739          for(i = 0; i < b->nrevs; i++)          for(i = 0; i < r->nbranches; i++)
2740          {          {
2741                  b->revs[i]->x += x;                  branch_t *b = r->branches[i];
2742                  b->revs[i]->y += y;                  if(!b->nrevs && b->ntags < 2)
2743                    {
2744                            /* No commits in this branch and no duplicate tags */
2745                            if(!btag)
2746                                    btag = b;
2747                            else
2748                            {
2749                                    /* We have consecutive empty branches, fold */
2750                                    b->folded = 1;
2751                                    b->folded_to = btag;
2752                                    for(j = 0; j < rcs->nbranches; j++)
2753                                    {
2754                                            if(b == rcs->branches[j])
2755                                            {
2756                                                    /* Zap the branch from the admin */
2757                                                    memmove(&rcs->branches[j],
2758                                                            &rcs->branches[j+1],
2759                                                            (rcs->nbranches - j - 1)*sizeof(rcs->branches[0]));
2760                                                    rcs->nbranches--;
2761                                                    break;
2762                                            }
2763    
2764                                    }
2765                                    memmove(&r->branches[i], &r->branches[i+1], (r->nbranches - i - 1)*sizeof(r->branches[0]));
2766                                    r->nbranches--;
2767                                    i--;    /* We have one less now */
2768    
2769                                    /* Add to the fold-list */
2770                                    btag->folds = xrealloc(btag->folds, (btag->nfolds+1) * sizeof(btag->folds[0]));
2771                                    btag->folds[btag->nfolds] = b;
2772                                    btag->nfolds++;
2773                            }
2774                    }
2775                    else
2776                    {
2777                            if(!conf.branch_foldall)
2778                                    btag = NULL;    /* Start a new box */
2779                            /* Recursively fold sub-branches */
2780                            for(j = 0; j < b->nrevs; j++)
2781                                    fold_branch(rcs, b->revs[j]);