1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "render.h"
15#include "agxbuf.h"
16#include "htmltable.h"
17#include "entities.h"
18#include "logic.h"
19#include "gvc.h"
20
21#ifdef _WIN32
22#define R_OK 4
23#endif
24
25#ifdef HAVE_UNISTD_H
26# include <unistd.h>
27#endif // HAVE_UNISTD_H
28
29#include <ctype.h>
30
31/*
32 * a queue of nodes
33 */
34nodequeue *new_queue(int sz)
35{
36 nodequeue *q = NEW(nodequeue);
37
38 if (sz <= 1)
39 sz = 2;
40 q->head = q->tail = q->store = N_NEW(sz, node_t *);
41 q->limit = q->store + sz;
42 return q;
43}
44
45void free_queue(nodequeue * q)
46{
47 free(q->store);
48 free(q);
49}
50
51void enqueue(nodequeue * q, node_t * n)
52{
53 *(q->tail++) = n;
54 if (q->tail >= q->limit)
55 q->tail = q->store;
56}
57
58node_t *dequeue(nodequeue * q)
59{
60 node_t *n;
61 if (q->head == q->tail)
62 n = NULL;
63 else {
64 n = *(q->head++);
65 if (q->head >= q->limit)
66 q->head = q->store;
67 }
68 return n;
69}
70
71int late_int(void *obj, attrsym_t * attr, int def, int low)
72{
73 char *p;
74 char *endp;
75 int rv;
76 if (attr == NULL)
77 return def;
78 p = ag_xget(obj, attr);
79 if (!p || p[0] == '\0')
80 return def;
81 rv = strtol (p, &endp, 10);
82 if (p == endp) return def; /* invalid int format */
83 if (rv < low) return low;
84 else return rv;
85}
86
87double late_double(void *obj, attrsym_t * attr, double def, double low)
88{
89 char *p;
90 char *endp;
91 double rv;
92
93 if (!attr || !obj)
94 return def;
95 p = ag_xget(obj, attr);
96 if (!p || p[0] == '\0')
97 return def;
98 rv = strtod (p, &endp);
99 if (p == endp) return def; /* invalid double format */
100 if (rv < low) return low;
101 else return rv;
102}
103
104/* get_inputscale:
105 * Return value for PSinputscale. If this is > 0, it has been set on the
106 * command line and this value is used.
107 * Otherwise, we check the graph's inputscale attribute. If this is not set
108 * or has a bad value, we return -1.
109 * If the value is 0, we return the default. Otherwise, we return the value.
110 * Set but negative values are treated like 0.
111 */
112double get_inputscale (graph_t* g)
113{
114 double d;
115
116 if (PSinputscale > 0) return PSinputscale; /* command line flag prevails */
117 d = late_double(g, agfindgraphattr(g, "inputscale"), -1, 0);
118 if (d == 0) return POINTS_PER_INCH;
119 else return d;
120}
121
122char *late_string(void *obj, attrsym_t * attr, char *def)
123{
124 if (!attr || !obj)
125 return def;
126 return agxget(obj, attr);
127}
128
129char *late_nnstring(void *obj, attrsym_t * attr, char *def)
130{
131 char *rv = late_string(obj, attr, def);
132 if (!rv || (rv[0] == '\0'))
133 rv = def;
134 return rv;
135}
136
137boolean late_bool(void *obj, attrsym_t * attr, int def)
138{
139 if (attr == NULL)
140 return def;
141
142 return mapbool(agxget(obj, attr));
143}
144
145/* union-find */
146node_t *UF_find(node_t * n)
147{
148 while (ND_UF_parent(n) && (ND_UF_parent(n) != n)) {
149 if (ND_UF_parent(ND_UF_parent(n)))
150 ND_UF_parent(n) = ND_UF_parent(ND_UF_parent(n));
151 n = ND_UF_parent(n);
152 }
153 return n;
154}
155
156node_t *UF_union(node_t * u, node_t * v)
157{
158 if (u == v)
159 return u;
160 if (ND_UF_parent(u) == NULL) {
161 ND_UF_parent(u) = u;
162 ND_UF_size(u) = 1;
163 } else
164 u = UF_find(u);
165 if (ND_UF_parent(v) == NULL) {
166 ND_UF_parent(v) = v;
167 ND_UF_size(v) = 1;
168 } else
169 v = UF_find(v);
170 if (ND_id(u) > ND_id(v)) {
171 ND_UF_parent(u) = v;
172 ND_UF_size(v) += ND_UF_size(u);
173 } else {
174 ND_UF_parent(v) = u;
175 ND_UF_size(u) += ND_UF_size(v);
176 v = u;
177 }
178 return v;
179}
180
181void UF_remove(node_t * u, node_t * v)
182{
183 assert(ND_UF_size(u) == 1);
184 ND_UF_parent(u) = u;
185 ND_UF_size(v) -= ND_UF_size(u);
186}
187
188void UF_singleton(node_t * u)
189{
190 ND_UF_size(u) = 1;
191 ND_UF_parent(u) = NULL;
192 ND_ranktype(u) = NORMAL;
193}
194
195void UF_setname(node_t * u, node_t * v)
196{
197 assert(u == UF_find(u));
198 ND_UF_parent(u) = v;
199 ND_UF_size(v) += ND_UF_size(u);
200}
201
202pointf coord(node_t * n)
203{
204 pointf r;
205
206 r.x = POINTS_PER_INCH * ND_pos(n)[0];
207 r.y = POINTS_PER_INCH * ND_pos(n)[1];
208 return r;
209}
210
211/* from Glassner's Graphics Gems */
212#define W_DEGREE 5
213
214/*
215 * Bezier :
216 * Evaluate a Bezier curve at a particular parameter value
217 * Fill in control points for resulting sub-curves if "Left" and
218 * "Right" are non-null.
219 *
220 */
221pointf Bezier(pointf * V, int degree, double t, pointf * Left, pointf * Right)
222{
223 int i, j; /* Index variables */
224 pointf Vtemp[W_DEGREE + 1][W_DEGREE + 1];
225
226 /* Copy control points */
227 for (j = 0; j <= degree; j++) {
228 Vtemp[0][j] = V[j];
229 }
230
231 /* Triangle computation */
232 for (i = 1; i <= degree; i++) {
233 for (j = 0; j <= degree - i; j++) {
234 Vtemp[i][j].x =
235 (1.0 - t) * Vtemp[i - 1][j].x + t * Vtemp[i - 1][j + 1].x;
236 Vtemp[i][j].y =
237 (1.0 - t) * Vtemp[i - 1][j].y + t * Vtemp[i - 1][j + 1].y;
238 }
239 }
240
241 if (Left != NULL)
242 for (j = 0; j <= degree; j++)
243 Left[j] = Vtemp[j][0];
244 if (Right != NULL)
245 for (j = 0; j <= degree; j++)
246 Right[j] = Vtemp[degree - j][j];
247
248 return (Vtemp[degree][0]);
249}
250
251#ifdef DEBUG
252edge_t *debug_getedge(graph_t * g, char *s0, char *s1)
253{
254 node_t *n0, *n1;
255 n0 = agfindnode(g, s0);
256 n1 = agfindnode(g, s1);
257 if (n0 && n1)
258 return agfindedge(g, n0, n1);
259 else
260 return NULL;
261}
262Agraphinfo_t* GD_info(graph_t * g) { return ((Agraphinfo_t*)AGDATA(g));}
263Agnodeinfo_t* ND_info(node_t * n) { return ((Agnodeinfo_t*)AGDATA(n));}
264#endif
265
266#if !defined(_WIN32)
267#include <pwd.h>
268
269#if 0
270static void cleanup(void)
271{
272 agxbfree(&xb);
273}
274#endif
275#endif
276
277/* Fgets:
278 * Read a complete line.
279 * Return pointer to line,
280 * or 0 on EOF
281 */
282char *Fgets(FILE * fp)
283{
284 static int bsize = 0;
285 static char *buf;
286 char *lp;
287 int len;
288
289 len = 0;
290 do {
291 if (bsize - len < BUFSIZ) {
292 bsize += BUFSIZ;
293 buf = grealloc(buf, bsize);
294 }
295 lp = fgets(buf + len, bsize - len, fp);
296 if (lp == 0)
297 break;
298 len += strlen(lp); /* since lp != NULL, len > 0 */
299 } while (buf[len - 1] != '\n');
300
301 if (len > 0)
302 return buf;
303 else
304 return 0;
305}
306
307/* safefile:
308 * Check to make sure it is okay to read in files.
309 * It returns NULL if the filename is trivial.
310 *
311 * If the application has set the SERVER_NAME environment variable,
312 * this indicates it is web-active. In this case, it requires that the GV_FILE_PATH
313 * environment variable be set. This gives the legal directories
314 * from which files may be read. safefile then derives the rightmost component
315 * of filename, where components are separated by a slash, backslash or colon,
316 * It then checks for the existence of a file consisting of a directory from
317 * GV_FILE_PATH followed by the rightmost component of filename. It returns the
318 * first such found, or NULL otherwise.
319 * The filename returned is thus
320 * Gvfilepath concatenated with the last component of filename,
321 * where a component is determined by a slash, backslash or colon
322 * character.
323 *
324 * If filename contains multiple components, the user is
325 * warned, once, that everything to the left is ignored.
326 *
327 * For non-server applications, we use the path list in Gvimagepath to
328 * resolve relative pathnames.
329 *
330 * N.B. safefile uses a fixed buffer, so functions using it should use the
331 * value immediately or make a copy.
332 */
333#ifdef _WIN32
334#define PATHSEP ";"
335#else
336#define PATHSEP ":"
337#endif
338
339static char** mkDirlist (const char* list, int* maxdirlen)
340{
341 int cnt = 0;
342 char* s = strdup (list);
343 char* dir;
344 char** dirs = NULL;
345 int maxlen = 0;
346
347 for (dir = strtok (s, PATHSEP); dir; dir = strtok (NULL, PATHSEP)) {
348 dirs = ALLOC (cnt+2,dirs,char*);
349 dirs[cnt++] = dir;
350 maxlen = MAX(maxlen, strlen (dir));
351 }
352 dirs[cnt] = NULL;
353 *maxdirlen = maxlen;
354 return dirs;
355}
356
357static char* findPath (char** dirs, int maxdirlen, const char* str)
358{
359 static char *safefilename = NULL;
360 char** dp;
361
362 /* allocate a buffer that we are sure is big enough
363 * +1 for null character.
364 * +1 for directory separator character.
365 */
366 safefilename = realloc(safefilename, (maxdirlen + strlen(str) + 2));
367
368 for (dp = dirs; *dp; dp++) {
369 sprintf (safefilename, "%s%s%s", *dp, DIRSEP, str);
370 if (access (safefilename, R_OK) == 0)
371 return safefilename;
372 }
373 return NULL;
374}
375
376const char *safefile(const char *filename)
377{
378 static boolean onetime = TRUE;
379 static char *pathlist = NULL;
380 static int maxdirlen;
381 static char** dirs;
382 const char *str, *p;
383
384 if (!filename || !filename[0])
385 return NULL;
386
387 if (HTTPServerEnVar) { /* If used as a server */
388 /*
389 * If we are running in an http server we allow
390 * files only from the directory specified in
391 * the GV_FILE_PATH environment variable.
392 */
393 if (!Gvfilepath || (*Gvfilepath == '\0')) {
394 if (onetime) {
395 agerr(AGWARN,
396 "file loading is disabled because the environment contains SERVER_NAME=\"%s\"\n"
397 "and the GV_FILE_PATH variable is unset or empty.\n",
398 HTTPServerEnVar);
399 onetime = FALSE;
400 }
401 return NULL;
402 }
403 if (!pathlist) {
404 dirs = mkDirlist (Gvfilepath, &maxdirlen);
405 pathlist = Gvfilepath;
406 }
407
408 str = filename;
409 if ((p = strrchr(str, '/')))
410 str = ++p;
411 if ((p = strrchr(str, '\\')))
412 str = ++p;
413 if ((p = strrchr(str, ':')))
414 str = ++p;
415
416 if (onetime && str != filename) {
417 agerr(AGWARN, "Path provided to file: \"%s\" has been ignored"
418 " because files are only permitted to be loaded from the directories in \"%s\""
419 " when running in an http server.\n", filename, Gvfilepath);
420 onetime = FALSE;
421 }
422
423 return findPath (dirs, maxdirlen, str);
424 }
425
426 if (pathlist != Gvimagepath) {
427 if (dirs) {
428 free (dirs[0]);
429 free (dirs);
430 dirs = NULL;
431 }
432 pathlist = Gvimagepath;
433 if (pathlist && *pathlist)
434 dirs = mkDirlist (pathlist, &maxdirlen);
435 }
436
437 if ((*filename == DIRSEP[0]) || !dirs)
438 return filename;
439
440 return findPath (dirs, maxdirlen, filename);
441}
442
443int maptoken(char *p, char **name, int *val)
444{
445 int i;
446 char *q;
447
448 for (i = 0; (q = name[i]) != 0; i++)
449 if (p && streq(p, q))
450 break;
451 return val[i];
452}
453
454boolean mapBool(char *p, boolean dflt)
455{
456 if (!p || (*p == '\0'))
457 return dflt;
458 if (!strcasecmp(p, "false"))
459 return FALSE;
460 if (!strcasecmp(p, "no"))
461 return FALSE;
462 if (!strcasecmp(p, "true"))
463 return TRUE;
464 if (!strcasecmp(p, "yes"))
465 return TRUE;
466 if (isdigit(*p))
467 return atoi(p);
468 else
469 return dflt;
470}
471
472boolean mapbool(char *p)
473{
474 return mapBool (p, FALSE);
475}
476
477pointf dotneato_closest(splines * spl, pointf pt)
478{
479 int i, j, k, besti, bestj;
480 double bestdist2, d2, dlow2, dhigh2; /* squares of distances */
481 double low, high, t;
482 pointf c[4], pt2;
483 bezier bz;
484
485 besti = bestj = -1;
486 bestdist2 = 1e+38;
487 for (i = 0; i < spl->size; i++) {
488 bz = spl->list[i];
489 for (j = 0; j < bz.size; j++) {
490 pointf b;
491
492 b.x = bz.list[j].x;
493 b.y = bz.list[j].y;
494 d2 = DIST2(b, pt);
495 if ((bestj == -1) || (d2 < bestdist2)) {
496 besti = i;
497 bestj = j;
498 bestdist2 = d2;
499 }
500 }
501 }
502
503 bz = spl->list[besti];
504 /* Pick best Bezier. If bestj is the last point in the B-spline, decrement.
505 * Then set j to be the first point in the corresponding Bezier by dividing
506 * then multiplying be 3. Thus, 0,1,2 => 0; 3,4,5 => 3, etc.
507 */
508 if (bestj == bz.size-1)
509 bestj--;
510 j = 3*(bestj / 3);
511 for (k = 0; k < 4; k++) {
512 c[k].x = bz.list[j + k].x;
513 c[k].y = bz.list[j + k].y;
514 }
515 low = 0.0;
516 high = 1.0;
517 dlow2 = DIST2(c[0], pt);
518 dhigh2 = DIST2(c[3], pt);
519 do {
520 t = (low + high) / 2.0;
521 pt2 = Bezier(c, 3, t, NULL, NULL);
522 if (fabs(dlow2 - dhigh2) < 1.0)
523 break;
524 if (fabs(high - low) < .00001)
525 break;
526 if (dlow2 < dhigh2) {
527 high = t;
528 dhigh2 = DIST2(pt2, pt);
529 } else {
530 low = t;
531 dlow2 = DIST2(pt2, pt);
532 }
533 } while (1);
534 return pt2;
535}
536
537pointf spline_at_y(splines * spl, double y)
538{
539 int i, j;
540 double low, high, d, t;
541 pointf c[4], p;
542 static bezier bz;
543
544/* this caching seems to prevent p.x from getting set from bz.list[0].x
545 - optimizer problem ? */
546
547#if 0
548 static splines *mem = NULL;
549
550 if (mem != spl) {
551 mem = spl;
552#endif
553 for (i = 0; i < spl->size; i++) {
554 bz = spl->list[i];
555 if (BETWEEN(bz.list[bz.size - 1].y, y, bz.list[0].y))
556 break;
557 }
558#if 0
559 }
560#endif
561 if (y > bz.list[0].y)
562 p = bz.list[0];
563 else if (y < bz.list[bz.size - 1].y)
564 p = bz.list[bz.size - 1];
565 else {
566 for (i = 0; i < bz.size; i += 3) {
567 for (j = 0; j < 3; j++) {
568 if ((bz.list[i + j].y <= y) && (y <= bz.list[i + j + 1].y))
569 break;
570 if ((bz.list[i + j].y >= y) && (y >= bz.list[i + j + 1].y))
571 break;
572 }
573 if (j < 3)
574 break;
575 }
576 assert(i < bz.size);
577 for (j = 0; j < 4; j++) {
578 c[j].x = bz.list[i + j].x;
579 c[j].y = bz.list[i + j].y;
580 /* make the spline be monotonic in Y, awful but it works for now */
581 if ((j > 0) && (c[j].y > c[j - 1].y))
582 c[j].y = c[j - 1].y;
583 }
584 low = 0.0;
585 high = 1.0;
586 do {
587 t = (low + high) / 2.0;
588 p = Bezier(c, 3, t, NULL, NULL);
589 d = p.y - y;
590 if (ABS(d) <= 1)
591 break;
592 if (d < 0)
593 high = t;
594 else
595 low = t;
596 } while (1);
597 }
598 p.y = y;
599 return p;
600}
601
602pointf neato_closest(splines * spl, pointf p)
603{
604/* this is a stub so that we can share a common emit.c between dot and neato */
605
606 return spline_at_y(spl, p.y);
607}
608
609static int Tflag;
610void gvToggle(int s)
611{
612 Tflag = !Tflag;
613#if !defined(_WIN32)
614 signal(SIGUSR1, gvToggle);
615#endif
616}
617
618int test_toggle()
619{
620 return Tflag;
621}
622
623struct fontinfo {
624 double fontsize;
625 char *fontname;
626 char *fontcolor;
627};
628
629void common_init_node(node_t * n)
630{
631 struct fontinfo fi;
632 char *str;
633 ND_width(n) =
634 late_double(n, N_width, DEFAULT_NODEWIDTH, MIN_NODEWIDTH);
635 ND_height(n) =
636 late_double(n, N_height, DEFAULT_NODEHEIGHT, MIN_NODEHEIGHT);
637 ND_shape(n) =
638 bind_shape(late_nnstring(n, N_shape, DEFAULT_NODESHAPE), n);
639 str = agxget(n, N_label);
640 fi.fontsize = late_double(n, N_fontsize, DEFAULT_FONTSIZE, MIN_FONTSIZE);
641 fi.fontname = late_nnstring(n, N_fontname, DEFAULT_FONTNAME);
642 fi.fontcolor = late_nnstring(n, N_fontcolor, DEFAULT_COLOR);
643 ND_label(n) = make_label((void*)n, str,
644 ((aghtmlstr(str) ? LT_HTML : LT_NONE) | ( (shapeOf(n) == SH_RECORD) ? LT_RECD : LT_NONE)),
645 fi.fontsize, fi.fontname, fi.fontcolor);
646 if (N_xlabel && (str = agxget(n, N_xlabel)) && (str[0])) {
647 ND_xlabel(n) = make_label((void*)n, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
648 fi.fontsize, fi.fontname, fi.fontcolor);
649 GD_has_labels(agraphof(n)) |= NODE_XLABEL;
650 }
651
652 ND_showboxes(n) = late_int(n, N_showboxes, 0, 0);
653 ND_shape(n)->fns->initfn(n);
654}
655
656static void initFontEdgeAttr(edge_t * e, struct fontinfo *fi)
657{
658 fi->fontsize = late_double(e, E_fontsize, DEFAULT_FONTSIZE, MIN_FONTSIZE);
659 fi->fontname = late_nnstring(e, E_fontname, DEFAULT_FONTNAME);
660 fi->fontcolor = late_nnstring(e, E_fontcolor, DEFAULT_COLOR);
661}
662
663static void
664initFontLabelEdgeAttr(edge_t * e, struct fontinfo *fi,
665 struct fontinfo *lfi)
666{
667 if (!fi->fontname) initFontEdgeAttr(e, fi);
668 lfi->fontsize = late_double(e, E_labelfontsize, fi->fontsize, MIN_FONTSIZE);
669 lfi->fontname = late_nnstring(e, E_labelfontname, fi->fontname);
670 lfi->fontcolor = late_nnstring(e, E_labelfontcolor, fi->fontcolor);
671}
672
673/* noClip:
674 * Return true if head/tail end of edge should not be clipped
675 * to node.
676 */
677static boolean
678noClip(edge_t *e, attrsym_t* sym)
679{
680 char *str;
681 boolean rv = FALSE;
682
683 if (sym) { /* mapbool isn't a good fit, because we want "" to mean true */
684 str = agxget(e,sym);
685 if (str && str[0]) rv = !mapbool(str);
686 else rv = FALSE;
687 }
688 return rv;
689}
690
691/*chkPort:
692 */
693static port
694chkPort (port (*pf)(node_t*, char*, char*), node_t* n, char* s)
695{
696 port pt;
697 char* cp=NULL;
698 if(s)
699 cp= strchr(s,':');
700 if (cp) {
701 *cp = '\0';
702 pt = pf(n, s, cp+1);
703 *cp = ':';
704 pt.name = cp+1;
705 }
706 else {
707 pt = pf(n, s, NULL);
708 pt.name = s;
709 }
710 return pt;
711}
712
713/* return true if edge has label */
714int common_init_edge(edge_t * e)
715{
716 char *str;
717 int r = 0;
718 struct fontinfo fi;
719 struct fontinfo lfi;
720 graph_t *sg = agraphof(agtail(e));
721
722 fi.fontname = NULL;
723 lfi.fontname = NULL;
724 if (E_label && (str = agxget(e, E_label)) && (str[0])) {
725 r = 1;
726 initFontEdgeAttr(e, &fi);
727 ED_label(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
728 fi.fontsize, fi.fontname, fi.fontcolor);
729 GD_has_labels(sg) |= EDGE_LABEL;
730 ED_label_ontop(e) =
731 mapbool(late_string(e, E_label_float, "false"));
732 }
733
734 if (E_xlabel && (str = agxget(e, E_xlabel)) && (str[0])) {
735 if (!fi.fontname)
736 initFontEdgeAttr(e, &fi);
737 ED_xlabel(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
738 fi.fontsize, fi.fontname, fi.fontcolor);
739 GD_has_labels(sg) |= EDGE_XLABEL;
740 }
741
742
743 /* vladimir */
744 if (E_headlabel && (str = agxget(e, E_headlabel)) && (str[0])) {
745 initFontLabelEdgeAttr(e, &fi, &lfi);
746 ED_head_label(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
747 lfi.fontsize, lfi.fontname, lfi.fontcolor);
748 GD_has_labels(sg) |= HEAD_LABEL;
749 }
750 if (E_taillabel && (str = agxget(e, E_taillabel)) && (str[0])) {
751 if (!lfi.fontname)
752 initFontLabelEdgeAttr(e, &fi, &lfi);
753 ED_tail_label(e) = make_label((void*)e, str, (aghtmlstr(str) ? LT_HTML : LT_NONE),
754 lfi.fontsize, lfi.fontname, lfi.fontcolor);
755 GD_has_labels(sg) |= TAIL_LABEL;
756 }
757 /* end vladimir */
758
759 /* We still accept ports beginning with colons but this is deprecated
760 * That is, we allow tailport = ":abc" as well as the preferred
761 * tailport = "abc".
762 */
763 str = agget(e, TAIL_ID);
764 /* libgraph always defines tailport/headport; libcgraph doesn't */
765 if (!str) str = "";
766 if (str && str[0])
767 ND_has_port(agtail(e)) = TRUE;
768 ED_tail_port(e) = chkPort (ND_shape(agtail(e))->fns->portfn, agtail(e), str);
769 if (noClip(e, E_tailclip))
770 ED_tail_port(e).clip = FALSE;
771 str = agget(e, HEAD_ID);
772 /* libgraph always defines tailport/headport; libcgraph doesn't */
773 if (!str) str = "";
774 if (str && str[0])
775 ND_has_port(aghead(e)) = TRUE;
776 ED_head_port(e) = chkPort(ND_shape(aghead(e))->fns->portfn, aghead(e), str);
777 if (noClip(e, E_headclip))
778 ED_head_port(e).clip = FALSE;
779
780 return r;
781}
782
783/* addLabelBB:
784 */
785static boxf addLabelBB(boxf bb, textlabel_t * lp, boolean flipxy)
786{
787 double width, height;
788 pointf p = lp->pos;
789 double min, max;
790
791 if (flipxy) {
792 height = lp->dimen.x;
793 width = lp->dimen.y;
794 }
795 else {
796 width = lp->dimen.x;
797 height = lp->dimen.y;
798 }
799 min = p.x - width / 2.;
800 max = p.x + width / 2.;
801 if (min < bb.LL.x)
802 bb.LL.x = min;
803 if (max > bb.UR.x)
804 bb.UR.x = max;
805
806 min = p.y - height / 2.;
807 max = p.y + height / 2.;
808 if (min < bb.LL.y)
809 bb.LL.y = min;
810 if (max > bb.UR.y)
811 bb.UR.y = max;
812
813 return bb;
814}
815
816/* polyBB:
817 * Compute the bounding box of a polygon.
818 * We only need to use the outer periphery.
819 */
820boxf
821polyBB (polygon_t* poly)
822{
823 int i, sides = poly->sides;
824 int peris = MAX(poly->peripheries,1);
825 pointf* verts = poly->vertices + (peris-1)*sides;
826 boxf bb;
827
828 bb.LL = bb.UR = verts[0];
829 for (i = 1; i < sides; i++) {
830 bb.LL.x = MIN(bb.LL.x,verts[i].x);
831 bb.LL.y = MIN(bb.LL.y,verts[i].y);
832 bb.UR.x = MAX(bb.UR.x,verts[i].x);
833 bb.UR.y = MAX(bb.UR.y,verts[i].y);
834 }
835 return bb;
836}
837
838/* updateBB:
839 * Reset graph's bounding box to include bounding box of the given label.
840 * Assume the label's position has been set.
841 */
842void updateBB(graph_t * g, textlabel_t * lp)
843{
844 GD_bb(g) = addLabelBB(GD_bb(g), lp, GD_flip(g));
845}
846
847/* compute_bb:
848 * Compute bounding box of g using nodes, splines, and clusters.
849 * Assumes bb of clusters already computed.
850 * store in GD_bb.
851 */
852void compute_bb(graph_t * g)
853{
854 node_t *n;
855 edge_t *e;
856 boxf b, bb;
857 boxf BF;
858 pointf ptf, s2;
859 int i, j;
860
861 if ((agnnodes(g) == 0) && (GD_n_cluster(g) ==0)) {
862 bb.LL = pointfof(0, 0);
863 bb.UR = pointfof(0, 0);
864 return;
865 }
866
867 bb.LL = pointfof(INT_MAX, INT_MAX);
868 bb.UR = pointfof(-INT_MAX, -INT_MAX);
869 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
870 ptf = coord(n);
871 s2.x = ND_xsize(n) / 2.0;
872 s2.y = ND_ysize(n) / 2.0;
873 b.LL = sub_pointf(ptf, s2);
874 b.UR = add_pointf(ptf, s2);
875
876 EXPANDBB(bb,b);
877 if (ND_xlabel(n) && ND_xlabel(n)->set) {
878 bb = addLabelBB(bb, ND_xlabel(n), GD_flip(g));
879 }
880 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
881 if (ED_spl(e) == 0)
882 continue;
883 for (i = 0; i < ED_spl(e)->size; i++) {
884 for (j = 0; j < (((Agedgeinfo_t*)AGDATA(e))->spl)->list[i].size; j++) {
885 ptf = ED_spl(e)->list[i].list[j];
886 EXPANDBP(bb,ptf);
887 }
888 }
889 if (ED_label(e) && ED_label(e)->set) {
890 bb = addLabelBB(bb, ED_label(e), GD_flip(g));
891 }
892 if (ED_head_label(e) && ED_head_label(e)->set) {
893 bb = addLabelBB(bb, ED_head_label(e), GD_flip(g));
894 }
895 if (ED_tail_label(e) && ED_tail_label(e)->set) {
896 bb = addLabelBB(bb, ED_tail_label(e), GD_flip(g));
897 }
898 if (ED_xlabel(e) && ED_xlabel(e)->set) {
899 bb = addLabelBB(bb, ED_xlabel(e), GD_flip(g));
900 }
901 }
902 }
903
904 for (i = 1; i <= GD_n_cluster(g); i++) {
905 B2BF(GD_bb(GD_clust(g)[i]), BF);
906 EXPANDBB(bb,BF);
907 }
908 if (GD_label(g) && GD_label(g)->set) {
909 bb = addLabelBB(bb, GD_label(g), GD_flip(g));
910 }
911
912 GD_bb(g) = bb;
913}
914
915int is_a_cluster (Agraph_t* g)
916{
917 return ((g == g->root) || (!strncasecmp(agnameof(g), "cluster", 7)) || mapBool(agget(g,"cluster"),FALSE));
918}
919
920/* setAttr:
921 * Sets object's name attribute to the given value.
922 * Creates the attribute if not already set.
923 */
924Agsym_t *setAttr(graph_t * g, void *obj, char *name, char *value,
925 Agsym_t * ap)
926{
927 if (ap == NULL) {
928 switch (agobjkind(obj)) {
929 case AGRAPH:
930 ap = agattr(g, AGRAPH,name, "");
931 break;
932 case AGNODE:
933 ap = agattr(g,AGNODE, name, "");
934 break;
935 case AGEDGE:
936 ap = agattr(g,AGEDGE, name, "");
937 break;
938 }
939 }
940 agxset(obj, ap, value);
941 return ap;
942}
943
944/* clustNode:
945 * Generate a special cluster node representing the end node
946 * of an edge to the cluster cg. n is a node whose name is the same
947 * as the cluster cg. clg is the subgraph of all of
948 * the original nodes, which will be deleted later.
949 */
950static node_t *clustNode(node_t * n, graph_t * cg, agxbuf * xb,
951 graph_t * clg)
952{
953 node_t *cn;
954 static int idx = 0;
955 char num[100];
956
957 agxbput(xb, "__");
958 sprintf(num, "%d", idx++);
959 agxbput(xb, num);
960 agxbputc(xb, ':');
961 agxbput(xb, agnameof(cg));
962
963 cn = agnode(agroot(cg), agxbuse(xb), 1);
964 agbindrec(cn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);
965
966 SET_CLUST_NODE(cn);
967 agsubnode(cg,cn,1);
968 //aginsert(cg, cn);
969 agsubnode(clg,n,1);
970 //aginsert(clg, n);
971
972 /* set attributes */
973 N_label = setAttr(agraphof(cn), cn, "label", "", N_label);
974 N_style = setAttr(agraphof(cn), cn, "style", "invis", N_style);
975 N_shape = setAttr(agraphof(cn), cn, "shape", "box", N_shape);
976 /* N_width = setAttr (cn->graph, cn, "width", "0.0001", N_width); */
977
978 return cn;
979}
980
981typedef struct {
982 Dtlink_t link; /* cdt data */
983 void *p[2]; /* key */
984 node_t *t;
985 node_t *h;
986} item;
987
988static int cmpItem(Dt_t * d, void *p1[], void *p2[], Dtdisc_t * disc)
989{
990 NOTUSED(d);
991 NOTUSED(disc);
992
993 if (p1[0] < p2[0])
994 return -1;
995 else if (p1[0] > p2[0])
996 return 1;
997 else if (p1[1] < p2[1])
998 return -1;
999 else if (p1[1] > p2[1])
1000 return 1;
1001 else
1002 return 0;
1003}
1004
1005/* newItem:
1006 */
1007static void *newItem(Dt_t * d, item * objp, Dtdisc_t * disc)
1008{
1009 item *newp = NEW(item);
1010
1011 NOTUSED(disc);
1012 newp->p[0] = objp->p[0];
1013 newp->p[1] = objp->p[1];
1014 newp->t = objp->t;
1015 newp->h = objp->h;
1016
1017 return newp;
1018}
1019
1020/* freeItem:
1021 */
1022static void freeItem(Dt_t * d, item * obj, Dtdisc_t * disc)
1023{
1024 free(obj);
1025}
1026
1027static Dtdisc_t mapDisc = {
1028 offsetof(item, p),
1029 sizeof(2 * sizeof(void *)),
1030 offsetof(item, link),
1031 (Dtmake_f) newItem,
1032 (Dtfree_f) freeItem,
1033 (Dtcompar_f) cmpItem,
1034 NIL(Dthash_f),
1035 NIL(Dtmemory_f),
1036 NIL(Dtevent_f)
1037};
1038
1039/* cloneEdge:
1040 * Make a copy of e in e's graph but using ct and ch as nodes
1041 */
1042static edge_t *cloneEdge(edge_t * e, node_t * ct, node_t * ch)
1043{
1044 graph_t *g = agraphof(ct);
1045 edge_t *ce = agedge(g, ct, ch,NULL,1);
1046 agbindrec(ce, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);
1047 agcopyattr(e, ce);
1048 ED_compound(ce) = TRUE;
1049
1050 return ce;
1051}
1052
1053/* insertEdge:
1054 */
1055static void insertEdge(Dt_t * map, void *t, void *h, edge_t * e)
1056{
1057 item dummy;
1058
1059 dummy.p[0] = t;
1060 dummy.p[1] = h;
1061 dummy.t = agtail(e);
1062 dummy.h = aghead(e);
1063 dtinsert(map, &dummy);
1064
1065 dummy.p[0] = h;
1066 dummy.p[1] = t;
1067 dummy.t = aghead(e);
1068 dummy.h = agtail(e);
1069 dtinsert(map, &dummy);
1070}
1071
1072/* mapEdge:
1073 * Check if we already have cluster edge corresponding to t->h,
1074 * and return it.
1075 */
1076static item *mapEdge(Dt_t * map, edge_t * e)
1077{
1078 void *key[2];
1079
1080 key[0] = agtail(e);
1081 key[1] = aghead(e);
1082 return (item *) dtmatch(map, &key);
1083}
1084
1085/* checkCompound:
1086 * If endpoint names a cluster, mark for temporary deletion and create
1087 * special node and insert into cluster. Then clone the edge. Real edge
1088 * will be deleted when we delete the original node.
1089 * Invariant: new edge has same sense as old. That is, given t->h with
1090 * t and h mapped to ct and ch, the new edge is ct->ch.
1091 *
1092 * In the current model, we create a cluster node for each cluster edge
1093 * between the cluster and some other node or cluster, treating the
1094 * cluster node as a port on the cluster. This should help with better
1095 * routing to avoid edge crossings. At present, this is not implemented,
1096 * so we could use a simpler model in which we create a single cluster
1097 * node for each cluster used in a cluster edge.
1098 *
1099 * Return 1 if cluster edge is created.
1100 */
1101#define MAPC(n) (strncmp(agnameof(n),"cluster",7)?NULL:findCluster(cmap,agnameof(n)))
1102
1103static int
1104checkCompound(edge_t * e, graph_t * clg, agxbuf * xb, Dt_t * map, Dt_t* cmap)
1105{
1106 graph_t *tg;
1107 graph_t *hg;
1108 node_t *cn;
1109 node_t *cn1;
1110 node_t *t = agtail(e);
1111 node_t *h = aghead(e);
1112 edge_t *ce;
1113 item *ip;
1114
1115 if (IS_CLUST_NODE(h)) return 0;
1116 tg = MAPC(t);
1117 hg = MAPC(h);
1118 if (!tg && !hg)
1119 return 0;
1120 if (tg == hg) {
1121 agerr(AGWARN, "cluster cycle %s -- %s not supported\n", agnameof(t),
1122 agnameof(t));
1123 return 0;
1124 }
1125 ip = mapEdge(map, e);
1126 if (ip) {
1127 cloneEdge(e, ip->t, ip->h);
1128 return 1;
1129 }
1130
1131 if (hg) {
1132 if (tg) {
1133 if (agcontains(hg, tg)) {
1134 agerr(AGWARN, "tail cluster %s inside head cluster %s\n",
1135 agnameof(tg), agnameof(hg));
1136 return 0;
1137 }
1138 if (agcontains(tg, hg)) {
1139 agerr(AGWARN, "head cluster %s inside tail cluster %s\n",
1140 agnameof(hg),agnameof(tg));
1141 return 0;
1142 }
1143 cn = clustNode(t, tg, xb, clg);
1144 cn1 = clustNode(h, hg, xb, clg);
1145 ce = cloneEdge(e, cn, cn1);
1146 insertEdge(map, t, h, ce);
1147 } else {
1148 if (agcontains(hg, t)) {
1149 agerr(AGWARN, "tail node %s inside head cluster %s\n",
1150 agnameof(t), agnameof(hg));
1151 return 0;
1152 }
1153 cn = clustNode(h, hg, xb, clg);
1154 ce = cloneEdge(e, t, cn);
1155 insertEdge(map, t, h, ce);
1156 }
1157 } else {
1158 if (agcontains(tg, h)) {
1159 agerr(AGWARN, "head node %s inside tail cluster %s\n", agnameof(h),
1160 agnameof(tg));
1161 return 0;
1162 }
1163 cn = clustNode(t, tg, xb, clg);
1164 ce = cloneEdge(e, cn, h);
1165 insertEdge(map, t, h, ce);
1166 }
1167 return 1;
1168}
1169
1170typedef struct {
1171 Agrec_t hdr;
1172 int n_cluster_edges;
1173} cl_edge_t;
1174
1175static int
1176num_clust_edges(graph_t * g)
1177{
1178 cl_edge_t* cl_info = (cl_edge_t*)HAS_CLUST_EDGE(g);
1179 if (cl_info)
1180 return cl_info->n_cluster_edges;
1181 else
1182 return 0;
1183}
1184
1185/* processClusterEdges:
1186 * Look for cluster edges. Replace cluster edge endpoints
1187 * corresponding to a cluster with special cluster nodes.
1188 * Delete original nodes.
1189 * If cluster edges are found, a cl_edge_t record will be
1190 * attached to the graph, containing the count of such edges.
1191 */
1192void processClusterEdges(graph_t * g)
1193{
1194 int num_cl_edges = 0;
1195 node_t *n;
1196 node_t *nxt;
1197 edge_t *e;
1198 graph_t *clg;
1199 agxbuf xb;
1200 Dt_t *map;
1201 Dt_t *cmap = mkClustMap (g);
1202 unsigned char buf[SMALLBUF];
1203
1204 map = dtopen(&mapDisc, Dtoset);
1205 clg = agsubg(g, "__clusternodes",1);
1206 agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
1207 agxbinit(&xb, SMALLBUF, buf);
1208 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1209 if (IS_CLUST_NODE(n)) continue;
1210 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1211 num_cl_edges += checkCompound(e, clg, &xb, map, cmap);
1212 }
1213 }
1214 agxbfree(&xb);
1215 dtclose(map);
1216 for (n = agfstnode(clg); n; n = nxt) {
1217 nxt = agnxtnode(clg, n);
1218 agdelete(g, n);
1219 }
1220 agclose(clg);
1221 if (num_cl_edges) {
1222 cl_edge_t* cl_info;
1223 cl_info = agbindrec(g, CL_EDGE_TAG, sizeof(cl_edge_t), FALSE);
1224 cl_info->n_cluster_edges = num_cl_edges;
1225 }
1226 dtclose(cmap);
1227}
1228
1229/* mapN:
1230 * Convert cluster nodes back to ordinary nodes
1231 * If n is already ordinary, return it.
1232 * Otherwise, we know node's name is "__i:xxx"
1233 * where i is some number and xxx is the nodes's original name.
1234 * Create new node of name xxx if it doesn't exist and add n to clg
1235 * for later deletion.
1236 */
1237static node_t *mapN(node_t * n, graph_t * clg)
1238{
1239 node_t *nn;
1240 char *name;
1241 graph_t *g = agraphof(n);
1242 Agsym_t *sym;
1243
1244 if (!(IS_CLUST_NODE(n)))
1245 return n;
1246 agsubnode(clg, n, 1);
1247 name = strchr(agnameof(n), ':');
1248 assert(name);
1249 name++;
1250 if ((nn = agfindnode(g, name)))
1251 return nn;
1252 nn = agnode(g, name, 1);
1253 agbindrec(nn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);
1254 SET_CLUST_NODE(nn);
1255
1256 /* Set all attributes to default */
1257 for (sym = agnxtattr(g, AGNODE, NULL); sym; (sym = agnxtattr(g, AGNODE, sym))) {
1258 if (agxget(nn, sym) != sym->defval)
1259 agxset(nn, sym, sym->defval);
1260 }
1261 return nn;
1262}
1263
1264static void undoCompound(edge_t * e, graph_t * clg)
1265{
1266 node_t *t = agtail(e);
1267 node_t *h = aghead(e);
1268 node_t *ntail;
1269 node_t *nhead;
1270 edge_t* ce;
1271
1272 ntail = mapN(t, clg);
1273 nhead = mapN(h, clg);
1274 ce = cloneEdge(e, ntail, nhead);
1275
1276 /* transfer drawing information */
1277 ED_spl(ce) = ED_spl(e);
1278 ED_spl(e) = NULL;
1279 ED_label(ce) = ED_label(e);
1280 ED_label(e) = NULL;
1281 ED_xlabel(ce) = ED_xlabel(e);
1282 ED_xlabel(e) = NULL;
1283 ED_head_label(ce) = ED_head_label(e);
1284 ED_head_label(e) = NULL;
1285 ED_tail_label(ce) = ED_tail_label(e);
1286 ED_tail_label(e) = NULL;
1287 gv_cleanup_edge(e);
1288}
1289
1290/* undoClusterEdges:
1291 * Replace cluster nodes with originals. Make sure original has
1292 * no attributes. Replace original edges. Delete cluster nodes,
1293 * which will also delete cluster edges.
1294 */
1295void undoClusterEdges(graph_t * g)
1296{
1297 node_t *n;
1298 node_t *nextn;
1299 edge_t *e;
1300 graph_t *clg;
1301 edge_t **elist;
1302 int ecnt = num_clust_edges(g);
1303 int i = 0;
1304
1305 if (!ecnt) return;
1306 clg = agsubg(g, "__clusternodes",1);
1307 agbindrec(clg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
1308 elist = N_NEW(ecnt, edge_t*);
1309 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1310 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1311 if (ED_compound(e))
1312 elist[i++] = e;
1313 }
1314 }
1315 assert(i == ecnt);
1316 for (i = 0; i < ecnt; i++)
1317 undoCompound(elist[i], clg);
1318 free (elist);
1319 for (n = agfstnode(clg); n; n = nextn) {
1320 nextn = agnxtnode(clg, n);
1321 gv_cleanup_node(n);
1322 agdelete(g, n);
1323 }
1324 agclose(clg);
1325}
1326
1327/* safe_dcl:
1328 * Find the attribute belonging to graph g for objects like obj
1329 * with given name. If one does not exist, create it with the
1330 * default value def.
1331 */
1332attrsym_t*
1333safe_dcl(graph_t * g, int obj_kind, char *name, char *def)
1334{
1335 attrsym_t *a = agattr(g,obj_kind,name, NULL);
1336 if (!a) /* attribute does not exist */
1337 a = agattr(g,obj_kind,name,def);
1338 return a;
1339}
1340
1341static int comp_entities(const void *e1, const void *e2) {
1342 return strcmp(((struct entities_s *)e1)->name, ((struct entities_s *)e2)->name);
1343}
1344
1345#define MAXENTLEN 8
1346
1347/* scanEntity:
1348 * Scan non-numeric entity, convert to &#...; form and store in xbuf.
1349 * t points to first char after '&'. Return after final semicolon.
1350 * If unknown, we return t and let libexpat flag the error.
1351 * */
1352char* scanEntity (char* t, agxbuf* xb)
1353{
1354 char* endp = strchr (t, ';');
1355 struct entities_s key, *res;
1356 int len;
1357 char buf[MAXENTLEN+1];
1358
1359 agxbputc(xb, '&');
1360 if (!endp) return t;
1361 if (((len = endp-t) > MAXENTLEN) || (len < 2)) return t;
1362 strncpy (buf, t, len);
1363 buf[len] = '\0';
1364 key.name = buf;
1365 res = bsearch(&key, entities, NR_OF_ENTITIES,
1366 sizeof(entities[0]), comp_entities);
1367 if (!res) return t;
1368 sprintf (buf, "%d", res->value);
1369 agxbputc(xb, '#');
1370 agxbput(xb, buf);
1371 agxbputc(xb, ';');
1372 return (endp+1);
1373}
1374
1375
1376/* htmlEntity:
1377 * Check for an HTML entity for a special character.
1378 * Assume *s points to first byte after '&'.
1379 * If successful, return the corresponding value and update s to
1380 * point after the terminating ';'.
1381 * On failure, return 0 and leave s unchanged.
1382 */
1383static int
1384htmlEntity (char** s)
1385{
1386 char *p;
1387 struct entities_s key, *res;
1388 char entity_name_buf[ENTITY_NAME_LENGTH_MAX+1];
1389 unsigned char* str = *(unsigned char**)s;
1390 unsigned int byte;
1391 int i, n = 0;
1392
1393 byte = *str;
1394 if (byte == '#') {
1395 byte = *(str + 1);
1396 if (byte == 'x' || byte == 'X') {
1397 for (i = 2; i < 8; i++) {
1398 byte = *(str + i);
1399 if (byte >= 'A' && byte <= 'F')
1400 byte = byte - 'A' + 10;
1401 else if (byte >= 'a' && byte <= 'f')
1402 byte = byte - 'a' + 10;
1403 else if (byte >= '0' && byte <= '9')
1404 byte = byte - '0';
1405 else
1406 break;
1407 n = (n * 16) + byte;
1408 }
1409 }
1410 else {
1411 for (i = 1; i < 8; i++) {
1412 byte = *(str + i);
1413 if (byte >= '0' && byte <= '9')
1414 n = (n * 10) + (byte - '0');
1415 else
1416 break;
1417 }
1418 }
1419 if (byte == ';') {
1420 str += i+1;
1421 }
1422 else {
1423 n = 0;
1424 }
1425 }
1426 else {
1427 key.name = p = entity_name_buf;
1428 for (i = 0; i < ENTITY_NAME_LENGTH_MAX; i++) {
1429 byte = *(str + i);
1430 if (byte == '\0') break;
1431 if (byte == ';') {
1432 *p++ = '\0';
1433 res = bsearch(&key, entities, NR_OF_ENTITIES,
1434 sizeof(entities[0]), *comp_entities);
1435 if (res) {
1436 n = res->value;
1437 str += i+1;
1438 }
1439 break;
1440 }
1441 *p++ = byte;
1442 }
1443 }
1444 *s = (char*)str;
1445 return n;
1446}
1447
1448static unsigned char
1449cvtAndAppend (unsigned char c, agxbuf* xb)
1450{
1451 char buf[2];
1452 char* s;
1453 char* p;
1454 int len;
1455
1456 buf[0] = c;
1457 buf[1] = '\0';
1458
1459 p = s = latin1ToUTF8 (buf);
1460 len = strlen(s);
1461 while (len-- > 1)
1462 agxbputc(xb, *p++);
1463 c = *p;
1464 free (s);
1465 return c;
1466}
1467
1468/* htmlEntityUTF8:
1469 * substitute html entities like: &#123; and: &amp; with the UTF8 equivalents
1470 * check for invalid utf8. If found, treat a single byte as Latin-1, convert it to
1471 * utf8 and warn the user.
1472 */
1473char* htmlEntityUTF8 (char* s, graph_t* g)
1474{
1475 static graph_t* lastg;
1476 static boolean warned;
1477 char* ns;
1478 agxbuf xb;
1479 unsigned char buf[BUFSIZ];
1480 unsigned char c;
1481 unsigned int v;
1482
1483 int uc;
1484 int ui;
1485
1486 if (lastg != g) {
1487 lastg = g;
1488 warned = 0;
1489 }
1490
1491 agxbinit(&xb, BUFSIZ, buf);
1492
1493 while ((c = *(unsigned char*)s++)) {
1494 if (c < 0xC0)
1495 /*
1496 * Handles properly formed UTF-8 characters between
1497 * 0x01 and 0x7F. Also treats \0 and naked trail
1498 * bytes 0x80 to 0xBF as valid characters representing
1499 * themselves.
1500 */
1501 uc = 0;
1502 else if (c < 0xE0)
1503 uc = 1;
1504 else if (c < 0xF0)
1505 uc = 2;
1506 else if (c < 0xF8)
1507 uc = 3;
1508 else {
1509 uc = -1;
1510 if (!warned) {
1511 agerr(AGWARN, "UTF8 codes > 4 bytes are not currently supported (graph %s) - treated as Latin-1. Perhaps \"-Gcharset=latin1\" is needed?\n", agnameof(g));
1512 warned = 1;
1513 }
1514 c = cvtAndAppend (c, &xb);
1515 }
1516
1517 if (uc == 0 && c == '&') {
1518 /* replace html entity sequences like: &amp;
1519 * and: &#123; with their UTF8 equivalents */
1520 v = htmlEntity (&s);
1521 if (v) {
1522 if (v < 0x7F) /* entity needs 1 byte in UTF8 */
1523 c = v;
1524 else if (v < 0x07FF) { /* entity needs 2 bytes in UTF8 */
1525 agxbputc(&xb, (v >> 6) | 0xC0);
1526 c = (v & 0x3F) | 0x80;
1527 }
1528 else { /* entity needs 3 bytes in UTF8 */
1529 agxbputc(&xb, (v >> 12) | 0xE0);
1530 agxbputc(&xb, ((v >> 6) & 0x3F) | 0x80);
1531 c = (v & 0x3F) | 0x80;
1532 }
1533 }
1534 }
1535 else /* copy n byte UTF8 characters */
1536 for (ui = 0; ui < uc; ++ui)
1537 if ((*s & 0xC0) == 0x80) {
1538 agxbputc(&xb, c);
1539 c = *(unsigned char*)s++;
1540 }
1541 else {
1542 if (!warned) {
1543 agerr(AGWARN, "Invalid %d-byte UTF8 found in input of graph %s - treated as Latin-1. Perhaps \"-Gcharset=latin1\" is needed?\n", uc + 1, agnameof(g));
1544 warned = 1;
1545 }
1546 c = cvtAndAppend (c, &xb);
1547 break;
1548 }
1549 agxbputc(&xb, c);
1550 }
1551 ns = strdup (agxbuse(&xb));
1552 agxbfree(&xb);
1553 return ns;
1554}
1555
1556/* latin1ToUTF8:
1557 * Converts string from Latin1 encoding to utf8
1558 * Also translates HTML entities.
1559 *
1560 */
1561char* latin1ToUTF8 (char* s)
1562{
1563 char* ns;
1564 agxbuf xb;
1565 unsigned char buf[BUFSIZ];
1566 unsigned int v;
1567
1568 agxbinit(&xb, BUFSIZ, buf);
1569
1570 /* Values are either a byte (<= 256) or come from htmlEntity, whose
1571 * values are all less than 0x07FF, so we need at most 3 bytes.
1572 */
1573 while ((v = *(unsigned char*)s++)) {
1574 if (v == '&') {
1575 v = htmlEntity (&s);
1576 if (!v) v = '&';
1577 }
1578 if (v < 0x7F)
1579 agxbputc(&xb, v);
1580 else if (v < 0x07FF) {
1581 agxbputc(&xb, (v >> 6) | 0xC0);
1582 agxbputc(&xb, (v & 0x3F) | 0x80);
1583 }
1584 else {
1585 agxbputc(&xb, (v >> 12) | 0xE0);
1586 agxbputc(&xb, ((v >> 6) & 0x3F) | 0x80);
1587 agxbputc(&xb, (v & 0x3F) | 0x80);
1588 }
1589 }
1590 ns = strdup (agxbuse(&xb));
1591 agxbfree(&xb);
1592 return ns;
1593}
1594
1595/* utf8ToLatin1:
1596 * Converts string from utf8 encoding to Latin1
1597 * Note that it does not attempt to reproduce HTML entities.
1598 * We assume the input string comes from latin1ToUTF8.
1599 */
1600char*
1601utf8ToLatin1 (char* s)
1602{
1603 char* ns;
1604 agxbuf xb;
1605 unsigned char buf[BUFSIZ];
1606 unsigned char c;
1607 unsigned char outc;
1608
1609 agxbinit(&xb, BUFSIZ, buf);
1610
1611 while ((c = *(unsigned char*)s++)) {
1612 if (c < 0x7F)
1613 agxbputc(&xb, c);
1614 else {
1615 outc = (c & 0x03) << 6;
1616 c = *(unsigned char*)s++;
1617 outc = outc | (c & 0x3F);
1618 agxbputc(&xb, outc);
1619 }
1620 }
1621 ns = strdup (agxbuse(&xb));
1622 agxbfree(&xb);
1623 return ns;
1624}
1625
1626boolean overlap_node(node_t *n, boxf b)
1627{
1628 inside_t ictxt;
1629 pointf p;
1630
1631 if (! OVERLAP(b, ND_bb(n)))
1632 return FALSE;
1633
1634/* FIXME - need to do something better about CLOSEENOUGH */
1635 p = sub_pointf(ND_coord(n), mid_pointf(b.UR, b.LL));
1636
1637 ictxt.s.n = n;
1638 ictxt.s.bp = NULL;
1639
1640 return ND_shape(n)->fns->insidefn(&ictxt, p);
1641}
1642
1643boolean overlap_label(textlabel_t *lp, boxf b)
1644{
1645 pointf s;
1646 boxf bb;
1647
1648 s.x = lp->dimen.x / 2.;
1649 s.y = lp->dimen.y / 2.;
1650 bb.LL = sub_pointf(lp->pos, s);
1651 bb.UR = add_pointf(lp->pos, s);
1652 return OVERLAP(b, bb);
1653}
1654
1655static boolean overlap_arrow(pointf p, pointf u, double scale, int flag, boxf b)
1656{
1657 if (OVERLAP(b, arrow_bb(p, u, scale, flag))) {
1658 /* FIXME - check inside arrow shape */
1659 return TRUE;
1660 }
1661 return FALSE;
1662}
1663
1664static boolean overlap_bezier(bezier bz, boxf b)
1665{
1666 int i;
1667 pointf p, u;
1668
1669 assert(bz.size);
1670 u = bz.list[0];
1671 for (i = 1; i < bz.size; i++) {
1672 p = bz.list[i];
1673 if (lineToBox(p, u, b) != -1)
1674 return TRUE;
1675 u = p;
1676 }
1677
1678 /* check arrows */
1679 if (bz.sflag) {
1680 if (overlap_arrow(bz.sp, bz.list[0], 1, bz.sflag, b))
1681 return TRUE;
1682 }
1683 if (bz.eflag) {
1684 if (overlap_arrow(bz.ep, bz.list[bz.size - 1], 1, bz.eflag, b))
1685 return TRUE;
1686 }
1687 return FALSE;
1688}
1689
1690boolean overlap_edge(edge_t *e, boxf b)
1691{
1692 int i;
1693 splines *spl;
1694 textlabel_t *lp;
1695
1696 spl = ED_spl(e);
1697 if (spl && boxf_overlap(spl->bb, b))
1698 for (i = 0; i < spl->size; i++)
1699 if (overlap_bezier(spl->list[i], b))
1700 return TRUE;
1701
1702 lp = ED_label(e);
1703 if (lp && overlap_label(lp, b))
1704 return TRUE;
1705
1706 return FALSE;
1707}
1708
1709/* edgeType:
1710 * Convert string to edge type.
1711 */
1712int edgeType (char* s, int dflt)
1713{
1714 int et;
1715
1716 if (!s || (*s == '\0')) return dflt;
1717
1718 et = ET_NONE;
1719 switch (*s) {
1720 case '0' : /* false */
1721 et = ET_LINE;
1722 break;
1723 case '1' : /* true */
1724 case '2' :
1725 case '3' :
1726 case '4' :
1727 case '5' :
1728 case '6' :
1729 case '7' :
1730 case '8' :
1731 case '9' :
1732 et = ET_SPLINE;
1733 break;
1734 case 'c' :
1735 case 'C' :
1736 if (!strcasecmp (s+1, "urved"))
1737 et = ET_CURVED;
1738 else if (!strcasecmp (s+1, "ompound"))
1739 et = ET_COMPOUND;
1740 break;
1741 case 'f' :
1742 case 'F' :
1743 if (!strcasecmp (s+1, "alse"))
1744 et = ET_LINE;
1745 break;
1746 case 'l' :
1747 case 'L' :
1748 if (!strcasecmp (s+1, "ine"))
1749 et = ET_LINE;
1750 break;
1751 case 'n' :
1752 case 'N' :
1753 if (!strcasecmp (s+1, "one")) return et;
1754 if (!strcasecmp (s+1, "o")) return ET_LINE;
1755 break;
1756 case 'o' :
1757 case 'O' :
1758 if (!strcasecmp (s+1, "rtho"))
1759 et = ET_ORTHO;
1760 break;
1761 case 'p' :
1762 case 'P' :
1763 if (!strcasecmp (s+1, "olyline"))
1764 et = ET_PLINE;
1765 break;
1766 case 's' :
1767 case 'S' :
1768 if (!strcasecmp (s+1, "pline"))
1769 et = ET_SPLINE;
1770 break;
1771 case 't' :
1772 case 'T' :
1773 if (!strcasecmp (s+1, "rue"))
1774 et = ET_SPLINE;
1775 break;
1776 case 'y' :
1777 case 'Y' :
1778 if (!strcasecmp (s+1, "es"))
1779 et = ET_SPLINE;
1780 break;
1781 }
1782 if (!et) {
1783 agerr(AGWARN, "Unknown \"splines\" value: \"%s\" - ignored\n", s);
1784 et = dflt;
1785 }
1786 return et;
1787}
1788
1789/* setEdgeType:
1790 * Sets graph's edge type based on the "splines" attribute.
1791 * If the attribute is not defined, use default.
1792 * If the attribute is "", use NONE.
1793 * If attribute value matches (case indepedent), use match.
1794 * ortho => ET_ORTHO
1795 * none => ET_NONE
1796 * line => ET_LINE
1797 * polyline => ET_PLINE
1798 * spline => ET_SPLINE
1799 * If attribute is boolean, true means ET_SPLINE, false means ET_LINE.
1800 * Else warn and use default.
1801 */
1802void setEdgeType (graph_t* g, int dflt)
1803{
1804 char* s = agget(g, "splines");
1805 int et;
1806
1807 if (!s) {
1808 et = dflt;
1809 }
1810 else if (*s == '\0') {
1811 et = ET_NONE;
1812 }
1813 else et = edgeType (s, dflt);
1814 GD_flags(g) |= et;
1815}
1816
1817
1818/* get_gradient_points
1819 * Evaluates the extreme points of an ellipse or polygon
1820 * Determines the point at the center of the extreme points
1821 * If isRadial is true,sets the inner radius to half the distance to the min point;
1822 * else uses the angle parameter to identify two points on a line that defines the
1823 * gradient direction
1824 * By default, this assumes a left-hand coordinate system (for svg); if RHS = 2 flag
1825 * is set, use standard coordinate system.
1826 */
1827void get_gradient_points(pointf * A, pointf * G, int n, float angle, int flags)
1828{
1829 int i;
1830 double rx, ry;
1831 pointf min,max,center;
1832 int isRadial = flags & 1;
1833 int isRHS = flags & 2;
1834
1835 if (n == 2) {
1836 rx = A[1].x - A[0].x;
1837 ry = A[1].y - A[0].y;
1838 min.x = A[0].x - rx;
1839 max.x = A[0].x + rx;
1840 min.y = A[0].y - ry;
1841 max.y = A[0].y + ry;
1842 }
1843 else {
1844 min.x = max.x = A[0].x;
1845 min.y = max.y = A[0].y;
1846 for (i = 0; i < n; i++){
1847 min.x = MIN(A[i].x,min.x);
1848 min.y = MIN(A[i].y,min.y);
1849 max.x = MAX(A[i].x,max.x);
1850 max.y = MAX(A[i].y,max.y);
1851 }
1852 }
1853 center.x = min.x + (max.x - min.x)/2;
1854 center.y = min.y + (max.y - min.y)/2;
1855 if (isRadial) {
1856 double inner_r, outer_r;
1857 outer_r = sqrt((center.x - min.x)*(center.x - min.x) +
1858 (center.y - min.y)*(center.y - min.y));
1859 inner_r = outer_r /4.;
1860 if (isRHS) {
1861 G[0].y = center.y;
1862 }
1863 else {
1864 G[0].y = -center.y;
1865 }
1866 G[0].x = center.x;
1867 G[1].x = inner_r;
1868 G[1].y = outer_r;
1869 }
1870 else {
1871 double half_x = max.x - center.x;
1872 double half_y = max.y - center.y;
1873 double sina = sin(angle);
1874 double cosa = cos(angle);
1875 if (isRHS) {
1876 G[0].y = center.y - half_y * sina;
1877 G[1].y = center.y + half_y * sina;
1878 }
1879 else {
1880 G[0].y = -center.y + (max.y - center.y) * sin(angle);
1881 G[1].y = -center.y - (center.y - min.y) * sin(angle);
1882 }
1883 G[0].x = center.x - half_x * cosa;
1884 G[1].x = center.x + half_x * cosa;
1885 }
1886}
1887
1888#ifndef WIN32_STATIC
1889#ifndef HAVE_STRCASECMP
1890
1891
1892#include <string.h>
1893//#include <ctype.h>
1894
1895
1896int strcasecmp(const char *s1, const char *s2)
1897{
1898 while ((*s1 != '\0')
1899 && (tolower(*(unsigned char *) s1) ==
1900 tolower(*(unsigned char *) s2))) {
1901 s1++;
1902 s2++;
1903 }
1904
1905 return tolower(*(unsigned char *) s1) - tolower(*(unsigned char *) s2);
1906}
1907
1908#endif /* HAVE_STRCASECMP */
1909#endif /* WIN32_STATIC */
1910
1911#ifndef WIN32_STATIC
1912#ifndef HAVE_STRNCASECMP
1913#include <string.h>
1914//#include <ctype.h>
1915
1916int strncasecmp(const char *s1, const char *s2, unsigned int n)
1917{
1918 if (n == 0)
1919 return 0;
1920
1921 while ((n-- != 0)
1922 && (tolower(*(unsigned char *) s1) ==
1923 tolower(*(unsigned char *) s2))) {
1924 if (n == 0 || *s1 == '\0' || *s2 == '\0')
1925 return 0;
1926 s1++;
1927 s2++;
1928 }
1929
1930 return tolower(*(unsigned char *) s1) - tolower(*(unsigned char *) s2);
1931}
1932
1933#endif /* HAVE_STRNCASECMP */
1934#endif /* WIN32_STATIC */
1935void gv_free_splines(edge_t * e)
1936{
1937 int i;
1938 if (ED_spl(e)) {
1939 for (i = 0; i < ED_spl(e)->size; i++)
1940 free(ED_spl(e)->list[i].list);
1941 free(ED_spl(e)->list);
1942 free(ED_spl(e));
1943 }
1944 ED_spl(e) = NULL;
1945}
1946
1947void gv_cleanup_edge(edge_t * e)
1948{
1949 free (ED_path(e).ps);
1950 gv_free_splines(e);
1951 free_label(ED_label(e));
1952 free_label(ED_xlabel(e));
1953 free_label(ED_head_label(e));
1954 free_label(ED_tail_label(e));
1955 /*FIX HERE , shallow cleaning may not be enough here */
1956 agdelrec(e, "Agedgeinfo_t");
1957}
1958
1959void gv_cleanup_node(node_t * n)
1960{
1961 if (ND_pos(n)) free(ND_pos(n));
1962 if (ND_shape(n))
1963 ND_shape(n)->fns->freefn(n);
1964 free_label(ND_label(n));
1965 free_label(ND_xlabel(n));
1966 /*FIX HERE , shallow cleaning may not be enough here */
1967 agdelrec(n, "Agnodeinfo_t");
1968}
1969
1970void gv_nodesize(node_t * n, boolean flip)
1971{
1972 double w;
1973
1974 if (flip) {
1975 w = INCH2PS(ND_height(n));
1976 ND_lw(n) = ND_rw(n) = w / 2;
1977 ND_ht(n) = INCH2PS(ND_width(n));
1978 }
1979 else {
1980 w = INCH2PS(ND_width(n));
1981 ND_lw(n) = ND_rw(n) = w / 2;
1982 ND_ht(n) = INCH2PS(ND_height(n));
1983 }
1984}
1985
1986#ifdef _WIN32
1987void fix_fc(void)
1988{
1989 char buf[28192];
1990 char buf2[28192];
1991 int cur=0;
1992 FILE* fp;
1993
1994 if((fp = fopen("fix-fc.exe", "r")) == NULL)
1995 return ;
1996 fclose (fp);
1997 if (!system ("fix-fc.exe")) {
1998 system ("del fix-fc.exe");
1999 system ("dot -c"); //run dot -c once too since we already run things :)
2000 }
2001}
2002#endif
2003
2004#ifndef HAVE_DRAND48
2005double drand48(void)
2006{
2007 double d;
2008 d = rand();
2009 d = d / RAND_MAX;
2010 return d;
2011}
2012#endif
2013typedef struct {
2014 Dtlink_t link;
2015 char* name;
2016 Agraph_t* clp;
2017} clust_t;
2018
2019static void free_clust (Dt_t* dt, clust_t* clp, Dtdisc_t* disc)
2020{
2021 free (clp);
2022}
2023
2024static Dtdisc_t strDisc = {
2025 offsetof(clust_t,name),
2026 -1,
2027 offsetof(clust_t,link),
2028 NIL(Dtmake_f),
2029 (Dtfree_f)free_clust,
2030 NIL(Dtcompar_f),
2031 NIL(Dthash_f),
2032 NIL(Dtmemory_f),
2033 NIL(Dtevent_f)
2034};
2035
2036static void fillMap (Agraph_t* g, Dt_t* map)
2037{
2038 Agraph_t* cl;
2039 int c;
2040 char* s;
2041 clust_t* ip;
2042
2043 for (c = 1; c <= GD_n_cluster(g); c++) {
2044 cl = GD_clust(g)[c];
2045 s = agnameof(cl);
2046 if (dtmatch (map, s)) {
2047 agerr(AGWARN, "Two clusters named %s - the second will be ignored\n", s);
2048 }
2049 else {
2050 ip = NEW(clust_t);
2051 ip->name = s;
2052 ip->clp = cl;
2053 dtinsert (map, ip);
2054 }
2055 fillMap (cl, map);
2056 }
2057}
2058
2059/* mkClustMap:
2060 * Generates a dictionary mapping cluster names to corresponding cluster.
2061 * Used with cgraph as the latter does not support a flat namespace of clusters.
2062 * Assumes G has already built a cluster tree using GD_n_cluster and GD_clust.
2063 */
2064Dt_t* mkClustMap (Agraph_t* g)
2065{
2066 Dt_t* map = dtopen (&strDisc, Dtoset);
2067
2068 fillMap (g, map);
2069
2070 return map;
2071}
2072
2073Agraph_t*
2074findCluster (Dt_t* map, char* name)
2075{
2076 clust_t* clp = dtmatch (map, name);
2077 if (clp)
2078 return clp->clp;
2079 else
2080 return NULL;
2081}
2082
2083Agnodeinfo_t* ninf(Agnode_t* n) {return (Agnodeinfo_t*)AGDATA(n);}
2084Agraphinfo_t* ginf(Agraph_t* g) {return (Agraphinfo_t*)AGDATA(g);}
2085Agedgeinfo_t* einf(Agedge_t* e) {return (Agedgeinfo_t*)AGDATA(e);}
2086/* void dumpG(Agraph_t* g) { agwrite(g, stderr); } */
2087