1
//! Representation of Bézier paths.
2
//!
3
//! Path data can consume a significant amount of memory in complex SVG documents.  This
4
//! module deals with this as follows:
5
//!
6
//! * The path parser pushes commands into a [`PathBuilder`].  This is a mutable,
7
//! temporary storage for path data.
8
//!
9
//! * Then, the [`PathBuilder`] gets turned into a long-term, immutable [`Path`] that has
10
//! a more compact representation.
11
//!
12
//! The code tries to reduce work in the allocator, by using a [`TinyVec`] with space for at
13
//! least 32 commands on the stack for `PathBuilder`; most paths in SVGs in the wild have
14
//! fewer than 32 commands, and larger ones will spill to the heap.
15
//!
16
//! See these blog posts for details and profiles:
17
//!
18
//! * [Compact representation for path data](https://people.gnome.org/~federico/blog/reducing-memory-consumption-in-librsvg-4.html)
19
//! * [Reducing slack space and allocator work](https://people.gnome.org/~federico/blog/reducing-memory-consumption-in-librsvg-3.html)
20

            
21
use tinyvec::TinyVec;
22

            
23
use std::f64;
24
use std::f64::consts::*;
25
use std::slice;
26

            
27
use crate::float_eq_cairo::ApproxEqCairo;
28
use crate::path_parser::{ParseError, PathParser};
29
use crate::util::clamp;
30

            
31
/// Whether an arc's sweep should be >= 180 degrees, or smaller.
32
18
#[derive(Debug, Copy, Clone, PartialEq)]
33
9
pub struct LargeArc(pub bool);
34

            
35
/// Angular direction in which an arc is drawn.
36
2601
#[derive(Debug, Copy, Clone, PartialEq)]
37
pub enum Sweep {
38
    Negative,
39
    Positive,
40
}
41

            
42
/// "c" command for paths; describes a cubic Bézier segment.
43
58
#[derive(Debug, Clone, PartialEq, Default)]
44
pub struct CubicBezierCurve {
45
    /// The (x, y) coordinates of the first control point.
46
29
    pub pt1: (f64, f64),
47
    /// The (x, y) coordinates of the second control point.
48
29
    pub pt2: (f64, f64),
49
    /// The (x, y) coordinates of the end point of this path segment.
50
29
    pub to: (f64, f64),
51
}
52

            
53
impl CubicBezierCurve {
54
    /// Consumes 6 coordinates and creates a curve segment.
55
290449
    fn from_coords(coords: &mut slice::Iter<'_, f64>) -> CubicBezierCurve {
56
290449
        let pt1 = take_two(coords);
57
290449
        let pt2 = take_two(coords);
58
290449
        let to = take_two(coords);
59

            
60
290449
        CubicBezierCurve { pt1, pt2, to }
61
290449
    }
62

            
63
    /// Pushes 6 coordinates to `coords` and returns `PackedCommand::CurveTo`.
64
147456
    fn to_packed_and_coords(&self, coords: &mut Vec<f64>) -> PackedCommand {
65
147456
        coords.push(self.pt1.0);
66
147456
        coords.push(self.pt1.1);
67
147456
        coords.push(self.pt2.0);
68
147456
        coords.push(self.pt2.1);
69
147456
        coords.push(self.to.0);
70
147456
        coords.push(self.to.1);
71
147456
        PackedCommand::CurveTo
72
147456
    }
73
}
74

            
75
/// Conversion from endpoint parameterization to center parameterization.
76
///
77
/// SVG path data specifies elliptical arcs in terms of their endpoints, but
78
/// they are easier to process if they are converted to a center parameterization.
79
///
80
/// When attempting to compute the center parameterization of the arc,
81
/// out of range parameters may see an arc omitted or treated as a line.
82
pub enum ArcParameterization {
83
    /// Center parameterization of the arc.
84
    CenterParameters {
85
        /// Center of the ellipse.
86
        center: (f64, f64),
87
        /// Radii of the ellipse (corrected).
88
        radii: (f64, f64),
89
        /// Angle of the start point.
90
        theta1: f64,
91
        /// Delta angle to the end point.
92
        delta_theta: f64,
93
    },
94
    /// Treat the arc as a line to the end point.
95
    LineTo,
96
    /// Omit the arc.
97
    Omit,
98
}
99

            
100
/// "a" command for paths; describes  an elliptical arc in terms of its endpoints.
101
18
#[derive(Debug, Clone, PartialEq)]
102
pub struct EllipticalArc {
103
    /// The (x-axis, y-axis) radii for the ellipse.
104
9
    pub r: (f64, f64),
105
    /// The rotation angle in degrees for the ellipse's x-axis
106
    /// relative to the x-axis of the user coordinate system.
107
9
    pub x_axis_rotation: f64,
108
    /// Flag indicating whether the arc sweep should be
109
    /// greater than or equal to 180 degrees, or smaller than 180 degrees.
110
9
    pub large_arc: LargeArc,
111
    /// Flag indicating the angular direction in which the arc is drawn.
112
9
    pub sweep: Sweep,
113
    /// The (x, y) coordinates for the start point of this path segment.
114
9
    pub from: (f64, f64),
115
    /// The (x, y) coordinates for the end point of this path segment.
116
9
    pub to: (f64, f64),
117
}
118

            
119
impl EllipticalArc {
120
    /// Calculates a center parameterization from the endpoint parameterization.
121
    ///
122
    /// Radii may be adjusted if there is no solution.
123
    ///
124
    /// See section [B.2.4. Conversion from endpoint to center
125
    /// parameterization](https://www.w3.org/TR/SVG2/implnote.html#ArcConversionEndpointToCenter)
126
2594
    pub(crate) fn center_parameterization(&self) -> ArcParameterization {
127
        let Self {
128
2594
            r: (mut rx, mut ry),
129
2594
            x_axis_rotation,
130
2594
            large_arc,
131
2594
            sweep,
132
2594
            from: (x1, y1),
133
2594
            to: (x2, y2),
134
        } = *self;
135

            
136
        // Ensure radii are non-zero.
137
        // Otherwise this arc is treated as a line segment joining the end points.
138
        //
139
        // A bit further down we divide by the square of the radii.
140
        // Check that we won't divide by zero.
141
        // See http://bugs.debian.org/508443
142
2594
        if rx * rx < f64::EPSILON || ry * ry < f64::EPSILON {
143
            return ArcParameterization::LineTo;
144
        }
145

            
146
2590
        let is_large_arc = large_arc.0;
147
2590
        let is_positive_sweep = sweep == Sweep::Positive;
148

            
149
2590
        let phi = x_axis_rotation * PI / 180.0;
150
2590
        let (sin_phi, cos_phi) = phi.sin_cos();
151

            
152
        // Ensure radii are positive.
153
2590
        rx = rx.abs();
154
2590
        ry = ry.abs();
155

            
156
        // The equations simplify after a translation which places
157
        // the origin at the midpoint of the line joining (x1, y1) to (x2, y2),
158
        // followed by a rotation to line up the coordinate axes
159
        // with the axes of the ellipse.
160
        // All transformed coordinates will be written with primes.
161
        //
162
        // Compute (x1', y1').
163
2590
        let mid_x = (x1 - x2) / 2.0;
164
2590
        let mid_y = (y1 - y2) / 2.0;
165
2590
        let x1_ = cos_phi * mid_x + sin_phi * mid_y;
166
2590
        let y1_ = -sin_phi * mid_x + cos_phi * mid_y;
167

            
168
        // Ensure radii are large enough.
169
2590
        let lambda = (x1_ / rx).powi(2) + (y1_ / ry).powi(2);
170
2590
        if lambda > 1.0 {
171
            // If not, scale up the ellipse uniformly
172
            // until there is exactly one solution.
173
86
            rx *= lambda.sqrt();
174
86
            ry *= lambda.sqrt();
175
        }
176

            
177
        // Compute the transformed center (cx', cy').
178
2590
        let d = (rx * y1_).powi(2) + (ry * x1_).powi(2);
179
2590
        if d == 0.0 {
180
            return ArcParameterization::Omit;
181
        }
182
        let k = {
183
2590
            let mut k = ((rx * ry).powi(2) / d - 1.0).abs().sqrt();
184
2590
            if is_positive_sweep == is_large_arc {
185
1214
                k = -k;
186
            }
187
2590
            k
188
        };
189
2590
        let cx_ = k * rx * y1_ / ry;
190
2590
        let cy_ = -k * ry * x1_ / rx;
191

            
192
        // Compute the center (cx, cy).
193
2590
        let cx = cos_phi * cx_ - sin_phi * cy_ + (x1 + x2) / 2.0;
194
2590
        let cy = sin_phi * cx_ + cos_phi * cy_ + (y1 + y2) / 2.0;
195

            
196
        // Compute the start angle θ1.
197
2590
        let ux = (x1_ - cx_) / rx;
198
2590
        let uy = (y1_ - cy_) / ry;
199
2590
        let u_len = (ux * ux + uy * uy).abs().sqrt();
200
2590
        if u_len == 0.0 {
201
            return ArcParameterization::Omit;
202
        }
203
2590
        let cos_theta1 = clamp(ux / u_len, -1.0, 1.0);
204
        let theta1 = {
205
2590
            let mut theta1 = cos_theta1.acos();
206
2590
            if uy < 0.0 {
207
1014
                theta1 = -theta1;
208
            }
209
2590
            theta1
210
        };
211

            
212
        // Compute the total delta angle Δθ.
213
2590
        let vx = (-x1_ - cx_) / rx;
214
2590
        let vy = (-y1_ - cy_) / ry;
215
2590
        let v_len = (vx * vx + vy * vy).abs().sqrt();
216
2590
        if v_len == 0.0 {
217
            return ArcParameterization::Omit;
218
        }
219
2590
        let dp_uv = ux * vx + uy * vy;
220
2590
        let cos_delta_theta = clamp(dp_uv / (u_len * v_len), -1.0, 1.0);
221
        let delta_theta = {
222
2590
            let mut delta_theta = cos_delta_theta.acos();
223
2590
            if ux * vy - uy * vx < 0.0 {
224
870
                delta_theta = -delta_theta;
225
            }
226
2590
            if is_positive_sweep && delta_theta < 0.0 {
227
124
                delta_theta += PI * 2.0;
228
2466
            } else if !is_positive_sweep && delta_theta > 0.0 {
229
392
                delta_theta -= PI * 2.0;
230
            }
231
2590
            delta_theta
232
        };
233

            
234
2590
        ArcParameterization::CenterParameters {
235
2590
            center: (cx, cy),
236
2590
            radii: (rx, ry),
237
            theta1,
238
            delta_theta,
239
        }
240
2590
    }
241

            
242
    /// Consumes 7 coordinates and creates an arc segment.
243
2606
    fn from_coords(
244
        large_arc: LargeArc,
245
        sweep: Sweep,
246
        coords: &mut slice::Iter<'_, f64>,
247
    ) -> EllipticalArc {
248
2606
        let r = take_two(coords);
249
2606
        let x_axis_rotation = take_one(coords);
250
2606
        let from = take_two(coords);
251
2606
        let to = take_two(coords);
252

            
253
2606
        EllipticalArc {
254
            r,
255
            x_axis_rotation,
256
            large_arc,
257
            sweep,
258
            from,
259
            to,
260
        }
261
2606
    }
262

            
263
    /// Pushes 7 coordinates to `coords` and returns one of `PackedCommand::Arc*`.
264
1413
    fn to_packed_and_coords(&self, coords: &mut Vec<f64>) -> PackedCommand {
265
1413
        coords.push(self.r.0);
266
1413
        coords.push(self.r.1);
267
1413
        coords.push(self.x_axis_rotation);
268
1413
        coords.push(self.from.0);
269
1413
        coords.push(self.from.1);
270
1413
        coords.push(self.to.0);
271
1413
        coords.push(self.to.1);
272

            
273
1413
        match (self.large_arc, self.sweep) {
274
377
            (LargeArc(false), Sweep::Negative) => PackedCommand::ArcSmallNegative,
275
626
            (LargeArc(false), Sweep::Positive) => PackedCommand::ArcSmallPositive,
276
195
            (LargeArc(true), Sweep::Negative) => PackedCommand::ArcLargeNegative,
277
215
            (LargeArc(true), Sweep::Positive) => PackedCommand::ArcLargePositive,
278
        }
279
1413
    }
280
}
281

            
282
/// Turns an arc segment into a cubic bezier curve.
283
///
284
/// Takes the center, the radii and the x-axis rotation of the ellipse,
285
/// the angles of the start and end points,
286
/// and returns cubic bezier curve parameters.
287
4022
pub(crate) fn arc_segment(
288
    c: (f64, f64),
289
    r: (f64, f64),
290
    x_axis_rotation: f64,
291
    th0: f64,
292
    th1: f64,
293
) -> CubicBezierCurve {
294
4022
    let (cx, cy) = c;
295
4022
    let (rx, ry) = r;
296
4022
    let phi = x_axis_rotation * PI / 180.0;
297
4022
    let (sin_phi, cos_phi) = phi.sin_cos();
298
4022
    let (sin_th0, cos_th0) = th0.sin_cos();
299
4022
    let (sin_th1, cos_th1) = th1.sin_cos();
300

            
301
4022
    let th_half = 0.5 * (th1 - th0);
302
4022
    let t = (8.0 / 3.0) * (th_half * 0.5).sin().powi(2) / th_half.sin();
303
4022
    let x1 = rx * (cos_th0 - t * sin_th0);
304
4022
    let y1 = ry * (sin_th0 + t * cos_th0);
305
4022
    let x3 = rx * cos_th1;
306
4022
    let y3 = ry * sin_th1;
307
4022
    let x2 = x3 + rx * (t * sin_th1);
308
4022
    let y2 = y3 + ry * (-t * cos_th1);
309

            
310
4022
    CubicBezierCurve {
311
4022
        pt1: (
312
4022
            cx + cos_phi * x1 - sin_phi * y1,
313
4022
            cy + sin_phi * x1 + cos_phi * y1,
314
        ),
315
4022
        pt2: (
316
4022
            cx + cos_phi * x2 - sin_phi * y2,
317
4022
            cy + sin_phi * x2 + cos_phi * y2,
318
        ),
319
4022
        to: (
320
4022
            cx + cos_phi * x3 - sin_phi * y3,
321
4022
            cy + sin_phi * x3 + cos_phi * y3,
322
        ),
323
    }
324
4022
}
325

            
326
/// Long-form version of a single path command.
327
///
328
/// This is returned from iterators on paths and subpaths.
329
60657803
#[derive(Clone, Default, Debug, PartialEq)]
330
pub enum PathCommand {
331
141
    MoveTo(f64, f64),
332
49
    LineTo(f64, f64),
333
29
    CurveTo(CubicBezierCurve),
334
9
    Arc(EllipticalArc),
335

            
336
    // The #[default] is just so we can use TinyVec, whose type
337
    // parameter requires T: Default.  There is no actual default for
338
    // path commands in the SVG spec; this is just our implementation
339
    // detail.
340
    #[default]
341
30328670
    ClosePath,
342
}
343

            
344
impl PathCommand {
345
    /// Returns the number of coordinate values that this command will generate in a `Path`.
346
5955908
    fn num_coordinates(&self) -> usize {
347
5955908
        match *self {
348
969399
            PathCommand::MoveTo(..) => 2,
349
3870225
            PathCommand::LineTo(..) => 2,
350
147471
            PathCommand::CurveTo(_) => 6,
351
1411
            PathCommand::Arc(_) => 7,
352
967402
            PathCommand::ClosePath => 0,
353
        }
354
5955908
    }
355

            
356
    /// Pushes a command's coordinates to `coords` and returns the corresponding `PackedCommand`.
357
5954825
    fn to_packed(&self, coords: &mut Vec<f64>) -> PackedCommand {
358
5954825
        match *self {
359
969654
            PathCommand::MoveTo(x, y) => {
360
969654
                coords.push(x);
361
969654
                coords.push(y);
362
969654
                PackedCommand::MoveTo
363
969654
            }
364

            
365
3869122
            PathCommand::LineTo(x, y) => {
366
3869122
                coords.push(x);
367
3869122
                coords.push(y);
368
3869122
                PackedCommand::LineTo
369
3869122
            }
370

            
371
147458
            PathCommand::CurveTo(ref c) => c.to_packed_and_coords(coords),
372

            
373
1414
            PathCommand::Arc(ref a) => a.to_packed_and_coords(coords),
374

            
375
967177
            PathCommand::ClosePath => PackedCommand::ClosePath,
376
        }
377
5954825
    }
378

            
379
    /// Consumes a packed command's coordinates from the `coords` iterator and returns the rehydrated `PathCommand`.
380
11891453
    fn from_packed(packed: PackedCommand, coords: &mut slice::Iter<'_, f64>) -> PathCommand {
381
11891453
        match packed {
382
            PackedCommand::MoveTo => {
383
1934813
                let x = take_one(coords);
384
1934813
                let y = take_one(coords);
385
1934813
                PathCommand::MoveTo(x, y)
386
1934813
            }
387

            
388
            PackedCommand::LineTo => {
389
7729363
                let x = take_one(coords);
390
7729363
                let y = take_one(coords);
391
7729363
                PathCommand::LineTo(x, y)
392
7729363
            }
393

            
394
290456
            PackedCommand::CurveTo => PathCommand::CurveTo(CubicBezierCurve::from_coords(coords)),
395

            
396
1934215
            PackedCommand::ClosePath => PathCommand::ClosePath,
397

            
398
752
            PackedCommand::ArcSmallNegative => PathCommand::Arc(EllipticalArc::from_coords(
399
752
                LargeArc(false),
400
752
                Sweep::Negative,
401
                coords,
402
752
            )),
403

            
404
995
            PackedCommand::ArcSmallPositive => PathCommand::Arc(EllipticalArc::from_coords(
405
995
                LargeArc(false),
406
995
                Sweep::Positive,
407
                coords,
408
995
            )),
409

            
410
389
            PackedCommand::ArcLargeNegative => PathCommand::Arc(EllipticalArc::from_coords(
411
389
                LargeArc(true),
412
389
                Sweep::Negative,
413
                coords,
414
389
            )),
415

            
416
470
            PackedCommand::ArcLargePositive => PathCommand::Arc(EllipticalArc::from_coords(
417
470
                LargeArc(true),
418
470
                Sweep::Positive,
419
                coords,
420
470
            )),
421
        }
422
11891453
    }
423
}
424

            
425
/// Constructs a path out of commands.
426
///
427
/// Create this with `PathBuilder::default`; you can then add commands to it or call the
428
/// `parse` method.  When you are finished constructing a path builder, turn it into a
429
/// `Path` with `into_path`.  You can then iterate on that `Path`'s commands with its
430
/// methods.
431
1898256
#[derive(Default)]
432
pub struct PathBuilder {
433
949128
    path_commands: TinyVec<[PathCommand; 32]>,
434
}
435

            
436
/// An immutable path with a compact representation.
437
///
438
/// This is constructed from a `PathBuilder` once it is finished.  You
439
/// can get an iterator for the path's commands with the `iter`
440
/// method, or an iterator for its subpaths (subsequences of commands that
441
/// start with a MoveTo) with the `iter_subpath` method.
442
///
443
/// The variants in `PathCommand` have different sizes, so a simple array of `PathCommand`
444
/// would have a lot of slack space.  We reduce this to a minimum by separating the
445
/// commands from their coordinates.  Then, we can have two dense arrays: one with a compact
446
/// representation of commands, and another with a linear list of the coordinates for each
447
/// command.
448
///
449
/// Both `PathCommand` and `PackedCommand` know how many coordinates they ought to
450
/// produce, with their `num_coordinates` methods.
451
///
452
/// This struct implements `Default`, and it yields an empty path.
453
1788
#[derive(Default)]
454
pub struct Path {
455
1788
    commands: Box<[PackedCommand]>,
456
1788
    coords: Box<[f64]>,
457
}
458

            
459
/// Packed version of a `PathCommand`, used in `Path`.
460
///
461
/// MoveTo/LineTo/CurveTo have only pairs of coordinates, while ClosePath has no coordinates,
462
/// and EllipticalArc has a bunch of coordinates plus two flags.  Here we represent the flags
463
/// as four variants.
464
///
465
/// This is `repr(u8)` to keep it as small as possible.
466
#[repr(u8)]
467
#[derive(Debug, Clone, Copy)]
468
enum PackedCommand {
469
    MoveTo,
470
    LineTo,
471
    CurveTo,
472
    ArcSmallNegative,
473
    ArcSmallPositive,
474
    ArcLargeNegative,
475
    ArcLargePositive,
476
    ClosePath,
477
}
478

            
479
impl PackedCommand {
480
    // Returns the number of coordinate values that this command will generate in a `Path`.
481
11870376
    fn num_coordinates(&self) -> usize {
482
11870376
        match *self {
483
1936253
            PackedCommand::MoveTo => 2,
484
7710641
            PackedCommand::LineTo => 2,
485
290383
            PackedCommand::CurveTo => 6,
486
            PackedCommand::ArcSmallNegative
487
            | PackedCommand::ArcSmallPositive
488
            | PackedCommand::ArcLargeNegative
489
2583
            | PackedCommand::ArcLargePositive => 7,
490
1930516
            PackedCommand::ClosePath => 0,
491
        }
492
11870376
    }
493
}
494

            
495
impl PathBuilder {
496
1937
    pub fn parse(&mut self, path_str: &str) -> Result<(), ParseError> {
497
1937
        let mut parser = PathParser::new(self, path_str);
498
1937
        parser.parse()
499
1937
    }
500

            
501
    /// Consumes the `PathBuilder` and returns a compact, immutable representation as a `Path`.
502
950137
    pub fn into_path(self) -> Path {
503
950137
        let num_coords = self
504
            .path_commands
505
            .iter()
506
            .map(PathCommand::num_coordinates)
507
            .sum();
508

            
509
949717
        let mut coords = Vec::with_capacity(num_coords);
510
949295
        let packed_commands: Vec<_> = self
511
            .path_commands
512
            .iter()
513
6902318
            .map(|cmd| cmd.to_packed(&mut coords))
514
            .collect();
515

            
516
948573
        Path {
517
949457
            commands: packed_commands.into_boxed_slice(),
518
948573
            coords: coords.into_boxed_slice(),
519
        }
520
948573
    }
521

            
522
    /// Adds a MoveTo command to the path.
523
969528
    pub fn move_to(&mut self, x: f64, y: f64) {
524
969528
        self.path_commands.push(PathCommand::MoveTo(x, y));
525
969528
    }
526

            
527
    /// Adds a LineTo command to the path.
528
3871369
    pub fn line_to(&mut self, x: f64, y: f64) {
529
3871369
        self.path_commands.push(PathCommand::LineTo(x, y));
530
3871369
    }
531

            
532
    /// Adds a CurveTo command to the path.
533
147456
    pub fn curve_to(&mut self, x2: f64, y2: f64, x3: f64, y3: f64, x4: f64, y4: f64) {
534
147456
        let curve = CubicBezierCurve {
535
147456
            pt1: (x2, y2),
536
147456
            pt2: (x3, y3),
537
147456
            to: (x4, y4),
538
        };
539
147456
        self.path_commands.push(PathCommand::CurveTo(curve));
540
147456
    }
541

            
542
    /// Adds an EllipticalArc command to the path.
543
1415
    pub fn arc(
544
        &mut self,
545
        x1: f64,
546
        y1: f64,
547
        rx: f64,
548
        ry: f64,
549
        x_axis_rotation: f64,
550
        large_arc: LargeArc,
551
        sweep: Sweep,
552
        x2: f64,
553
        y2: f64,
554
    ) {
555
1415
        let arc = EllipticalArc {
556
1415
            r: (rx, ry),
557
            x_axis_rotation,
558
            large_arc,
559
            sweep,
560
1415
            from: (x1, y1),
561
1415
            to: (x2, y2),
562
        };
563
1415
        self.path_commands.push(PathCommand::Arc(arc));
564
1415
    }
565

            
566
    /// Adds a ClosePath command to the path.
567
967772
    pub fn close_path(&mut self) {
568
967772
        self.path_commands.push(PathCommand::ClosePath);
569
967772
    }
570
}
571

            
572
/// An iterator over the subpaths of a `Path`.
573
pub struct SubPathIter<'a> {
574
    path: &'a Path,
575
    commands_start: usize,
576
    coords_start: usize,
577
}
578

            
579
/// A slice of commands and coordinates with a single `MoveTo` at the beginning.
580
pub struct SubPath<'a> {
581
    commands: &'a [PackedCommand],
582
    coords: &'a [f64],
583
}
584

            
585
/// An iterator over the commands/coordinates of a subpath.
586
pub struct SubPathCommandsIter<'a> {
587
    commands_iter: slice::Iter<'a, PackedCommand>,
588
    coords_iter: slice::Iter<'a, f64>,
589
}
590

            
591
impl<'a> SubPath<'a> {
592
    /// Returns an iterator over the subpath's commands.
593
1933481
    pub fn iter_commands(&self) -> SubPathCommandsIter<'_> {
594
1933481
        SubPathCommandsIter {
595
1933481
            commands_iter: self.commands.iter(),
596
1933481
            coords_iter: self.coords.iter(),
597
        }
598
1933481
    }
599

            
600
    /// Each subpath starts with a MoveTo; this returns its `(x, y)` coordinates.
601
77
    pub fn origin(&self) -> (f64, f64) {
602
77
        let first = *self.commands.first().unwrap();
603
77
        assert!(matches!(first, PackedCommand::MoveTo));
604
77
        let command = PathCommand::from_packed(first, &mut self.coords.iter());
605

            
606
77
        match command {
607
77
            PathCommand::MoveTo(x, y) => (x, y),
608
            _ => unreachable!(),
609
        }
610
77
    }
611

            
612
    /// Returns whether the length of a subpath is approximately zero.
613
37
    pub fn is_zero_length(&self) -> bool {
614
37
        let (cur_x, cur_y) = self.origin();
615

            
616
38
        for cmd in self.iter_commands().skip(1) {
617
71
            let (end_x, end_y) = match cmd {
618
                PathCommand::MoveTo(_, _) => unreachable!(
619
                    "A MoveTo cannot appear in a subpath if it's not the first element"
620
                ),
621
33
                PathCommand::LineTo(x, y) => (x, y),
622
1
                PathCommand::CurveTo(curve) => curve.to,
623
1
                PathCommand::Arc(arc) => arc.to,
624
                // If we get a `ClosePath and haven't returned yet then we haven't moved at all making
625
                // it an empty subpath`
626
1
                PathCommand::ClosePath => return true,
627
            };
628

            
629
35
            if !end_x.approx_eq_cairo(cur_x) || !end_y.approx_eq_cairo(cur_y) {
630
34
                return false;
631
            }
632
        }
633

            
634
2
        true
635
37
    }
636
}
637

            
638
impl<'a> Iterator for SubPathIter<'a> {
639
    type Item = SubPath<'a>;
640

            
641
3831157
    fn next(&mut self) -> Option<Self::Item> {
642
        // If we ended on our last command in the previous iteration, we're done here
643
3831157
        if self.commands_start >= self.path.commands.len() {
644
1897680
            return None;
645
        }
646

            
647
        // Otherwise we have at least one command left, we setup the slice to be all the remaining
648
        // commands.
649
1933477
        let commands = &self.path.commands[self.commands_start..];
650

            
651
1933477
        assert!(matches!(commands.first().unwrap(), PackedCommand::MoveTo));
652
1933477
        let mut num_coords = PackedCommand::MoveTo.num_coordinates();
653

            
654
        // Skip over the initial MoveTo
655
11859741
        for (i, cmd) in commands.iter().enumerate().skip(1) {
656
            // If we encounter a MoveTo , we ended our current subpath, we
657
            // return the commands until this command and set commands_start to be the index of the
658
            // next command
659
9965173
            if let PackedCommand::MoveTo = cmd {
660
38909
                let subpath_coords_start = self.coords_start;
661

            
662
38909
                self.commands_start += i;
663
38909
                self.coords_start += num_coords;
664

            
665
38909
                return Some(SubPath {
666
38909
                    commands: &commands[..i],
667
38909
                    coords: &self.path.coords
668
38909
                        [subpath_coords_start..subpath_coords_start + num_coords],
669
                });
670
            } else {
671
9926264
                num_coords += cmd.num_coordinates();
672
            }
673
        }
674

            
675
        // If we didn't find any MoveTo, we're done here. We return the rest of the path
676
        // and set commands_start so next iteration will return None.
677

            
678
1894568
        self.commands_start = self.path.commands.len();
679

            
680
1894568
        let subpath_coords_start = self.coords_start;
681
1894568
        assert!(subpath_coords_start + num_coords == self.path.coords.len());
682
1894568
        self.coords_start = self.path.coords.len();
683

            
684
1894568
        Some(SubPath {
685
            commands,
686
1894568
            coords: &self.path.coords[subpath_coords_start..],
687
        })
688
3831157
    }
689
}
690

            
691
impl<'a> Iterator for SubPathCommandsIter<'a> {
692
    type Item = PathCommand;
693

            
694
13833352
    fn next(&mut self) -> Option<Self::Item> {
695
27666704
        self.commands_iter
696
            .next()
697
25718541
            .map(|packed| PathCommand::from_packed(*packed, &mut self.coords_iter))
698
13833352
    }
699
}
700

            
701
impl Path {
702
    /// Get an iterator over a path `Subpath`s.
703
1897923
    pub fn iter_subpath(&self) -> SubPathIter<'_> {
704
1897923
        SubPathIter {
705
            path: self,
706
            commands_start: 0,
707
            coords_start: 0,
708
        }
709
1897923
    }
710

            
711
    /// Get an iterator over a path's commands.
712
287
    pub fn iter(&self) -> impl Iterator<Item = PathCommand> + '_ {
713
287
        let commands = self.commands.iter();
714
287
        let mut coords = self.coords.iter();
715

            
716
1025
        commands.map(move |cmd| PathCommand::from_packed(*cmd, &mut coords))
717
287
    }
718

            
719
    /// Returns whether there are no commands in the path.
720
2845666
    pub fn is_empty(&self) -> bool {
721
2845666
        self.commands.is_empty()
722
2845666
    }
723
}
724

            
725
21016861
fn take_one(iter: &mut slice::Iter<'_, f64>) -> f64 {
726
21016861
    *iter.next().unwrap()
727
21016861
}
728

            
729
878828
fn take_two(iter: &mut slice::Iter<'_, f64>) -> (f64, f64) {
730
878828
    (take_one(iter), take_one(iter))
731
878828
}
732

            
733
#[cfg(test)]
734
mod tests {
735
    use super::*;
736

            
737
    #[test]
738
2
    fn empty_builder() {
739
1
        let builder = PathBuilder::default();
740
1
        let path = builder.into_path();
741
1
        assert!(path.is_empty());
742
1
        assert_eq!(path.iter().count(), 0);
743
2
    }
744

            
745
    #[test]
746
2
    fn empty_path() {
747
1
        let path = Path::default();
748
1
        assert!(path.is_empty());
749
1
        assert_eq!(path.iter().count(), 0);
750
2
    }
751

            
752
    #[test]
753
2
    fn all_commands() {
754
1
        let mut builder = PathBuilder::default();
755
1
        builder.move_to(42.0, 43.0);
756
1
        builder.line_to(42.0, 43.0);
757
1
        builder.curve_to(42.0, 43.0, 44.0, 45.0, 46.0, 47.0);
758
1
        builder.arc(
759
            42.0,
760
            43.0,
761
            44.0,
762
            45.0,
763
            46.0,
764
1
            LargeArc(true),
765
1
            Sweep::Positive,
766
            47.0,
767
            48.0,
768
        );
769
1
        builder.close_path();
770
1
        let path = builder.into_path();
771
1
        assert!(path.iter().eq(vec![
772
1
            PathCommand::MoveTo(42.0, 43.0),
773
1
            PathCommand::LineTo(42.0, 43.0),
774
1
            PathCommand::CurveTo(CubicBezierCurve {
775
1
                pt1: (42.0, 43.0),
776
1
                pt2: (44.0, 45.0),
777
1
                to: (46.0, 47.0),
778
            }),
779
1
            PathCommand::Arc(EllipticalArc {
780
1
                from: (42.0, 43.0),
781
1
                r: (44.0, 45.0),
782
1
                to: (47.0, 48.0),
783
                x_axis_rotation: 46.0,
784
1
                large_arc: LargeArc(true),
785
1
                sweep: Sweep::Positive,
786
            }),
787
1
            PathCommand::ClosePath,
788
        ]));
789
2
    }
790

            
791
    #[test]
792
2
    fn subpath_iter() {
793
1
        let mut builder = PathBuilder::default();
794
1
        builder.move_to(42.0, 43.0);
795
1
        builder.line_to(42.0, 43.0);
796
1
        builder.close_path();
797

            
798
1
        builder.move_to(22.0, 22.0);
799
1
        builder.curve_to(22.0, 22.0, 44.0, 45.0, 46.0, 47.0);
800

            
801
1
        builder.move_to(69.0, 69.0);
802
1
        builder.line_to(42.0, 43.0);
803
1
        let path = builder.into_path();
804

            
805
1
        let subpaths = path
806
            .iter_subpath()
807
3
            .map(|subpath| {
808
3
                (
809
3
                    subpath.origin(),
810
3
                    subpath.iter_commands().collect::<Vec<PathCommand>>(),
811
                )
812
3
            })
813
            .collect::<Vec<((f64, f64), Vec<PathCommand>)>>();
814

            
815
2
        assert_eq!(
816
            subpaths,
817
2
            vec![
818
1
                (
819
1
                    (42.0, 43.0),
820
1
                    vec![
821
1
                        PathCommand::MoveTo(42.0, 43.0),
822
1
                        PathCommand::LineTo(42.0, 43.0),
823
1
                        PathCommand::ClosePath
824
                    ]
825
                ),
826
1
                (
827
1
                    (22.0, 22.0),
828
1
                    vec![
829
1
                        PathCommand::MoveTo(22.0, 22.0),
830
1
                        PathCommand::CurveTo(CubicBezierCurve {
831
1
                            pt1: (22.0, 22.0),
832
1
                            pt2: (44.0, 45.0),
833
1
                            to: (46.0, 47.0)
834
                        })
835
                    ]
836
                ),
837
1
                (
838
1
                    (69.0, 69.0),
839
1
                    vec![
840
1
                        PathCommand::MoveTo(69.0, 69.0),
841
1
                        PathCommand::LineTo(42.0, 43.0)
842
                    ]
843
                )
844
            ]
845
        );
846
2
    }
847

            
848
    #[test]
849
2
    fn zero_length_subpaths() {
850
1
        let mut builder = PathBuilder::default();
851
1
        builder.move_to(42.0, 43.0);
852
1
        builder.move_to(44.0, 45.0);
853
1
        builder.close_path();
854
1
        builder.move_to(46.0, 47.0);
855
1
        builder.line_to(48.0, 49.0);
856

            
857
1
        let path = builder.into_path();
858

            
859
1
        let subpaths = path
860
            .iter_subpath()
861
3
            .map(|subpath| (subpath.is_zero_length(), subpath.origin()))
862
            .collect::<Vec<(bool, (f64, f64))>>();
863

            
864
2
        assert_eq!(
865
            subpaths,
866
1
            vec![
867
1
                (true, (42.0, 43.0)),
868
1
                (true, (44.0, 45.0)),
869
1
                (false, (46.0, 47.0)),
870
            ]
871
        );
872
2
    }
873
}