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