← Back to branch summary

~ubuntu-branches/ubuntu/precise/graphviz/precise-security

« back to all changes in this revision

Viewing changes to lib/dotgen/compound.c

  • Committer: Bazaar Package Importer
  • Author(s): David Claughton
  • Date: 2010-03-24 22:45:18 UTC
  • mfrom: (1.2.7 upstream) (6.1.7 sid)
  • Revision ID: james.westby@ubuntu.com-20100324224518-do441tthbqjaqjzd
Tags: 2.26.3-4
http://bugs.debian.org/575255
Add patch to fix segfault in circo. Backported from upstream snapshot
release.  Thanks to Francis Russell for his work on this.
(Closes: #575255)

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/dotgen/compound.c
1
 
/* $Id: compound.c,v 1.3 2005/06/22 19:20:51 erg Exp $ $Revision: 1.3 $ */
 
1
/* $Id: compound.c,v 1.11 2009/06/03 01:10:52 ellson Exp $ $Revision: 1.11 $ */
2
2
/* vim:set shiftwidth=4 ts=8: */
3
3
 
4
4
/**********************************************************
20
20
 
21
21
#include        "dot.h"
22
22
 
23
 
 
24
 
/* midPt:
25
 
 * Return midpoint between two given points.
26
 
 */
27
 
static point midPt(point p, point q)
28
 
{
29
 
    point v;
30
 
 
31
 
    v.x = (p.x + q.x) / 2;
32
 
    v.y = (p.y + q.y) / 2;
33
 
    return v;
34
 
}
35
 
 
36
 
/* p2s:
37
 
 * Convert a point to its string representation.
38
 
 */
39
 
static char *p2s(point p, char *buf)
40
 
{
41
 
    sprintf(buf, "(%d,%d)", p.x, p.y);
 
23
/* pf2s:
 
24
 * Convert a pointf to its string representation.
 
25
 */
 
26
static char *pf2s(pointf p, char *buf)
 
27
{
 
28
    sprintf(buf, "(%.5g,%.5g)", p.x, p.y);
42
29
    return buf;
43
30
}
44
31
 
46
33
 * the box bp. Assume cp is outside the box, and pp is
47
34
 * on or in the box. 
48
35
 */
49
 
static point boxIntersect(point pp, point cp, box * bp)
 
36
static pointf boxIntersectf(pointf pp, pointf cp, boxf * bp)
50
37
{
51
 
    point ipp;
 
38
    pointf ipp;
52
39
    double ppx = pp.x;
53
40
    double ppy = pp.y;
54
41
    double cpx = cp.x;
55
42
    double cpy = cp.y;
56
 
    point ll = bp->LL;
57
 
    point ur = bp->UR;
 
43
    pointf ll;
 
44
    pointf ur;
58
45
 
 
46
    ll = bp->LL;
 
47
    ur = bp->UR;
59
48
    if (cp.x < ll.x) {
60
49
        ipp.x = ll.x;
61
50
        ipp.y = pp.y + (int) ((ipp.x - ppx) * (ppy - cpy) / (ppx - cpx));
86
75
        char ppbuf[100], cpbuf[100], llbuf[100], urbuf[100];
87
76
 
88
77
        agerr(AGERR,
89
 
              "segment [%s,%s] does not intersect box ll=%s,ur=%s\n",
90
 
              p2s(pp, ppbuf), p2s(cp, cpbuf), p2s(ll, llbuf), p2s(ur,
91
 
                                                                  urbuf));
 
78
                "segment [%s,%s] does not intersect box ll=%s,ur=%s\n",
 
79
                pf2s(pp, ppbuf), pf2s(cp, cpbuf),
 
80
                pf2s(ll, llbuf), pf2s(ur, urbuf));
92
81
        assert(0);
93
82
    }
94
83
    return ipp;
95
84
}
96
85
 
97
 
/* inBox:
 
86
/* inBoxf:
98
87
 * Returns true if p is on or in box bb
99
88
 */
100
 
static int inBox(point p, box * bb)
 
89
static int inBoxf(pointf p, boxf * bb)
101
90
{
102
 
    return ((p.x >= bb->LL.x) && (p.x <= bb->UR.x) &&
103
 
            (p.y >= bb->LL.y) && (p.y <= bb->UR.y));
 
91
    return INSIDE(p, *bb);
104
92
}
105
93
 
106
94
/* getCluster:
114
102
 
115
103
    if (!cluster_name || (*cluster_name == '\0'))
116
104
        return NULL;
 
105
#ifndef WITH_CGRAPH
117
106
    sg = agfindsubg(g, cluster_name);
 
107
#else
 
108
    sg = agsubg(g, cluster_name, 0);
 
109
#endif
118
110
    if (sg == NULL)
119
111
        agerr(AGWARN, "cluster named %s not found\n", cluster_name);
120
112
    return sg;
123
115
/* The following functions are derived from pp. 411-415 (pp. 791-795)
124
116
 * of Graphics Gems. In the code there, they use a SGN function to
125
117
 * count crossings. This doesn't seem to handle certain special cases,
126
 
 * as when the last point is on the line. It certainly doesn't work
127
 
 * for use; see bug 145. We need to use ZSGN instead.
 
118
 * as when the last point is on the line. It certainly didn't work
 
119
 * for us when we used int values; see bug 145. We needed to use CMP instead.
 
120
 *
 
121
 * Possibly unnecessary with double values, but harmless.
128
122
 */
129
 
#define SGN(a,b)          (((a)<(b)) ? -1 : 1)
130
 
#define ZSGN(a,b)         (((a)<(b)) ? -1 : (a)>(b) ? 1 : 0)
131
123
 
132
124
/* countVertCross:
133
125
 * Return the number of times the Bezier control polygon crosses
134
126
 * the vertical line x = xcoord.
135
127
 */
136
 
static int countVertCross(pointf * pts, int xcoord)
 
128
static int countVertCross(pointf * pts, double xcoord)
137
129
{
138
130
    int i;
139
131
    int sign, old_sign;
140
132
    int num_crossings = 0;
141
133
 
142
 
    sign = old_sign = ZSGN(pts[0].x, xcoord);
 
134
    sign = CMP(pts[0].x, xcoord);
143
135
    if (sign == 0)
144
136
        num_crossings++;
145
137
    for (i = 1; i <= 3; i++) {
146
 
        sign = ZSGN(pts[i].x, xcoord);
 
138
        old_sign = sign;
 
139
        sign = CMP(pts[i].x, xcoord);
147
140
        if ((sign != old_sign) && (old_sign != 0))
148
141
            num_crossings++;
149
 
        old_sign = sign;
150
142
    }
151
 
 
152
143
    return num_crossings;
153
 
 
154
144
}
155
145
 
156
146
/* countHorzCross:
157
147
 * Return the number of times the Bezier control polygon crosses
158
148
 * the horizontal line y = ycoord.
159
149
 */
160
 
static int countHorzCross(pointf * pts, int ycoord)
 
150
static int countHorzCross(pointf * pts, double ycoord)
161
151
{
162
152
    int i;
163
153
    int sign, old_sign;
164
154
    int num_crossings = 0;
165
155
 
166
 
    sign = old_sign = ZSGN(pts[0].y, ycoord);
 
156
    sign = CMP(pts[0].y, ycoord);
167
157
    if (sign == 0)
168
158
        num_crossings++;
169
159
    for (i = 1; i <= 3; i++) {
170
 
        sign = ZSGN(pts[i].y, ycoord);
 
160
        old_sign = sign;
 
161
        sign = CMP(pts[i].y, ycoord);
171
162
        if ((sign != old_sign) && (old_sign != 0))
172
163
            num_crossings++;
173
 
        old_sign = sign;
174
164
    }
175
 
 
176
165
    return num_crossings;
177
 
 
178
166
}
179
167
 
180
168
/* findVertical:
187
175
 */
188
176
static double
189
177
findVertical(pointf * pts, double tmin, double tmax,
190
 
             int xcoord, int ymin, int ymax)
 
178
             double xcoord, double ymin, double ymax)
191
179
{
192
180
    pointf Left[4];
193
181
    pointf Right[4];
197
185
    if (no_cross == 0)
198
186
        return -1.0;
199
187
 
200
 
    /* if 1 crossing and on the line x = xcoord */
201
 
    if ((no_cross == 1) && (ROUND(pts[3].x) == xcoord)) {
 
188
    /* if 1 crossing and on the line x == xcoord (within 1 point) */
 
189
    if ((no_cross == 1) && (ROUND(pts[3].x) == ROUND(xcoord))) {
202
190
        if ((ymin <= pts[3].y) && (pts[3].y <= ymax)) {
203
191
            return tmax;
204
192
        } else
225
213
 */
226
214
static double
227
215
findHorizontal(pointf * pts, double tmin, double tmax,
228
 
               int ycoord, int xmin, int xmax)
 
216
               double ycoord, double xmin, double xmax)
229
217
{
230
218
    pointf Left[4];
231
219
    pointf Right[4];
235
223
    if (no_cross == 0)
236
224
        return -1.0;
237
225
 
238
 
    /* if 1 crossing and on the line y = ycoord */
239
 
    if ((no_cross == 1) && (ROUND(pts[3].y) == ycoord)) {
 
226
    /* if 1 crossing and on the line y == ycoord (within 1 point) */
 
227
    if ((no_cross == 1) && (ROUND(pts[3].y) == ROUND(ycoord))) {
240
228
        if ((xmin <= pts[3].x) && (pts[3].x <= xmax)) {
241
229
            return tmax;
242
230
        } else
251
239
        return t;
252
240
    return findHorizontal(Right, (tmin + tmax) / 2.0, tmax, ycoord, xmin,
253
241
                          xmax);
254
 
 
255
242
}
256
243
 
257
 
#define P2PF(p, pf) (pf.x = p.x, pf.y = p.y)
258
 
#define PF2P(pf, p) (p.x = ROUND (pf.x), p.y = ROUND (pf.y))
259
 
 
260
 
/* splineIntersect:
 
244
/* splineIntersectf:
261
245
 * Given four spline control points and a box,
262
246
 * find the shortest portion of the spline from
263
 
 * ipts[0] to the intersection with the box, if any.
264
 
 * If an intersection is found, the four points are stored in ipts[0..3]
265
 
 * with ipts[3] being on the box, and 1 is returned. Otherwise, ipts
 
247
 * pts[0] to the intersection with the box, if any.
 
248
 * If an intersection is found, the four points are stored in pts[0..3]
 
249
 * with pts[3] being on the box, and 1 is returned. Otherwise, pts
266
250
 * is left unchanged and 0 is returned.
267
251
 */
268
 
static int splineIntersect(point * ipts, box * bb)
 
252
static int splineIntersectf(pointf * pts, boxf * bb)
269
253
{
270
254
    double tmin = 2.0;
271
255
    double t;
272
 
    pointf pts[4];
273
256
    pointf origpts[4];
274
257
    int i;
275
258
 
276
259
    for (i = 0; i < 4; i++) {
277
 
        P2PF(ipts[i], origpts[i]);
278
 
        pts[i] = origpts[i];
 
260
        origpts[i] = pts[i];
279
261
    }
280
262
 
281
263
    t = findVertical(pts, 0.0, 1.0, bb->LL.x, bb->LL.y, bb->UR.y);
303
285
    }
304
286
 
305
287
    if (tmin < 2.0) {
306
 
        for (i = 0; i < 4; i++) {
307
 
            PF2P(pts[i], ipts[i]);
308
 
        }
309
288
        return 1;
310
289
    } else
311
290
        return 0;
312
 
 
313
291
}
314
292
 
315
293
/* makeCompoundEdge:
328
306
    int starti = 0, endi = 0;   /* index of first and last control point */
329
307
    node_t *head;
330
308
    node_t *tail;
331
 
    box *bb;
 
309
    boxf *bb;
332
310
    int i, j;
333
311
    int size;
334
 
    point pts[4];
335
 
    point p;
 
312
    pointf pts[4];
 
313
    pointf p;
336
314
    int fixed;
337
315
 
338
316
    /* find head and tail target clusters, if defined */
345
323
    /* at present, we only handle single spline case */
346
324
    if (ED_spl(e)->size > 1) {
347
325
        agerr(AGWARN, "%s -> %s: spline size > 1 not supported\n",
348
 
              e->tail->name, e->head->name);
 
326
              agnameof(agtail(e)), agnameof(aghead(e)));
349
327
        return;
350
328
    }
351
329
    bez = ED_spl(e)->list;
352
330
    size = bez->size;
353
331
 
354
 
    head = e->head;
355
 
    tail = e->tail;
 
332
    head = aghead(e);
 
333
    tail = agtail(e);
356
334
 
357
335
    /* allocate new Bezier */
358
336
    nbez = GNEW(bezier);
371
349
    fixed = 0;
372
350
    if (lh) {
373
351
        bb = &(GD_bb(lh));
374
 
        if (!inBox(ND_coord_i(head), bb)) {
 
352
        if (!inBoxf(ND_coord(head), bb)) {
375
353
            agerr(AGWARN, "%s -> %s: head not inside head cluster %s\n",
376
 
                  e->tail->name, e->head->name, agget(e, "lhead"));
 
354
                  agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "lhead"));
377
355
        } else {
378
356
            /* If first control point is in bb, degenerate case. Spline
379
357
             * reduces to four points between the arrow head and the point 
380
358
             * where the segment between the first control point and arrow head 
381
359
             * crosses box.
382
360
             */
383
 
            if (inBox(bez->list[0], bb)) {
384
 
                if (inBox(ND_coord_i(tail), bb)) {
 
361
            if (inBoxf(bez->list[0], bb)) {
 
362
                if (inBoxf(ND_coord(tail), bb)) {
385
363
                    agerr(AGWARN,
386
364
                          "%s -> %s: tail is inside head cluster %s\n",
387
 
                          e->tail->name, e->head->name, agget(e, "lhead"));
 
365
                          agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "lhead"));
388
366
                } else {
389
367
                    assert(bez->sflag); /* must be arrowhead on tail */
390
 
                    p = boxIntersect(bez->list[0], bez->sp, bb);
 
368
                    p = boxIntersectf(bez->list[0], bez->sp, bb);
391
369
                    bez->list[3] = p;
392
 
                    bez->list[1] = midPt(p, bez->sp);
393
 
                    bez->list[0] = midPt(bez->list[1], bez->sp);
394
 
                    bez->list[2] = midPt(bez->list[1], p);
 
370
                    bez->list[1] = mid_pointf(p, bez->sp);
 
371
                    bez->list[0] = mid_pointf(bez->list[1], bez->sp);
 
372
                    bez->list[2] = mid_pointf(bez->list[1], p);
395
373
                    if (bez->eflag)
396
 
                        endi =
397
 
                            arrowEndClip(e, bez->list,
 
374
                        endi = arrowEndClip(e, bez->list,
398
375
                                         starti, 0, nbez, bez->eflag);
399
376
                    endi += 3;
400
377
                    fixed = 1;
401
378
                }
402
379
            } else {
403
380
                for (endi = 0; endi < size - 1; endi += 3) {
404
 
                    if (splineIntersect(&(bez->list[endi]), bb))
 
381
                    if (splineIntersectf(&(bez->list[endi]), bb))
405
382
                        break;
406
383
                }
407
384
                if (endi == size - 1) { /* no intersection */
408
385
                    assert(bez->eflag);
409
 
                    nbez->ep = boxIntersect(bez->ep, bez->list[endi], bb);
 
386
                    nbez->ep = boxIntersectf(bez->ep, bez->list[endi], bb);
410
387
                } else {
411
388
                    if (bez->eflag)
412
389
                        endi =
432
409
    fixed = 0;
433
410
    if (lt) {
434
411
        bb = &(GD_bb(lt));
435
 
        if (!inBox(ND_coord_i(tail), bb)) {
 
412
        if (!inBoxf(ND_coord(tail), bb)) {
436
413
            agerr(AGWARN, "%s -> %s: tail not inside tail cluster %s\n",
437
 
                  e->tail->name, head->name, agget(e, "ltail"));
 
414
                agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "ltail"));
438
415
        } else {
439
416
            /* If last control point is in bb, degenerate case. Spline
440
417
             * reduces to four points between arrow head, and the point
441
418
             * where the segment between the last control point and the 
442
419
             * arrow head crosses box.
443
420
             */
444
 
            if (inBox(bez->list[endi], bb)) {
445
 
                if (inBox(ND_coord_i(head), bb)) {
 
421
            if (inBoxf(bez->list[endi], bb)) {
 
422
                if (inBoxf(ND_coord(head), bb)) {
446
423
                    agerr(AGWARN,
447
 
                          "%s -> %s: head is inside tail cluster %s\n",
448
 
                          e->tail->name, e->head->name, agget(e, "ltail"));
 
424
                        "%s -> %s: head is inside tail cluster %s\n",
 
425
                        agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "ltail"));
449
426
                } else {
450
427
                    assert(bez->eflag); /* must be arrowhead on head */
451
 
                    p = boxIntersect(bez->list[endi], nbez->ep, bb);
 
428
                    p = boxIntersectf(bez->list[endi], nbez->ep, bb);
452
429
                    starti = endi - 3;
453
430
                    bez->list[starti] = p;
454
 
                    bez->list[starti + 2] = midPt(p, nbez->ep);
455
 
                    bez->list[starti + 3] =
456
 
                        midPt(bez->list[starti + 2], nbez->ep);
457
 
                    bez->list[starti + 1] =
458
 
                        midPt(bez->list[starti + 2], p);
 
431
                    bez->list[starti + 2] = mid_pointf(p, nbez->ep);
 
432
                    bez->list[starti + 3] = mid_pointf(bez->list[starti + 2], nbez->ep);
 
433
                    bez->list[starti + 1] = mid_pointf(bez->list[starti + 2], p);
459
434
                    if (bez->sflag)
460
 
                        starti =
461
 
                            arrowStartClip(e, bez->list,
462
 
                                           starti, endi - 3, nbez,
463
 
                                           bez->sflag);
 
435
                        starti = arrowStartClip(e, bez->list, starti,
 
436
                                endi - 3, nbez, bez->sflag);
464
437
                    fixed = 1;
465
438
                }
466
439
            } else {
467
440
                for (starti = endi; starti > 0; starti -= 3) {
468
441
                    for (i = 0; i < 4; i++)
469
442
                        pts[i] = bez->list[starti - i];
470
 
                    if (splineIntersect(pts, bb)) {
 
443
                    if (splineIntersectf(pts, bb)) {
471
444
                        for (i = 0; i < 4; i++)
472
445
                            bez->list[starti - i] = pts[i];
473
446
                        break;
476
449
                if (starti == 0) {
477
450
                    assert(bez->sflag);
478
451
                    nbez->sp =
479
 
                        boxIntersect(bez->sp, bez->list[starti], bb);
 
452
                        boxIntersectf(bez->sp, bez->list[starti], bb);
480
453
                } else {
481
454
                    starti -= 3;
482
455
                    if (bez->sflag)
483
 
                        starti =
484
 
                            arrowStartClip(e, bez->list,
485
 
                                           starti, endi - 3, nbez,
486
 
                                           bez->sflag);
 
456
                        starti = arrowStartClip(e, bez->list, starti,
 
457
                                endi - 3, nbez, bez->sflag);
487
458
                }
488
459
                fixed = 1;
489
460
            }
498
469
    /* complete Bezier, free garbage and attach new Bezier to edge 
499
470
     */
500
471
    nbez->size = endi - starti + 1;
501
 
    nbez->list = N_GNEW(nbez->size, point);
 
472
    nbez->list = N_GNEW(nbez->size, pointf);
502
473
    for (i = 0, j = starti; i < nbez->size; i++, j++)
503
474
        nbez->list[i] = bez->list[j];
504
475
    free(bez->list);
505
476
    free(bez);
506
477
    ED_spl(e)->list = nbez;
507
 
 
508
478
}
509
479
 
510
480
/* dot_compoundEdges: