rupg_types/
geo.rs

1//! The geometric types of `src/backend/utils/adt/geo_ops.c`: `point`, `lseg`, `box`, `path`, `polygon`, `line` and `circle`. A value is the bytes of its binary form, so that the send function is a copy of the bytes.
2
3use rupg_common::SqlState;
4
5use crate::binary::Recv;
6use crate::error::TypeError;
7use crate::float::{float8_out, strtod};
8use crate::number::is_space;
9use crate::oid;
10
11/// `EPSILON`: two numbers that differ by no more than this are equal in the fuzzy comparisons of `geo_decls.h`.
12const EPSILON: f64 = 1.0e-6;
13
14/// A geometric type.
15#[derive(Clone, Copy, Debug, PartialEq, Eq)]
16pub enum GeoKind {
17    Point,
18    Lseg,
19    Box,
20    Path,
21    Polygon,
22    Line,
23    Circle,
24}
25
26impl GeoKind {
27    /// The geometric type with this OID, or `None` for another type.
28    #[must_use]
29    pub fn from_oid(ty: u32) -> Option<GeoKind> {
30        Some(match ty {
31            oid::POINT => GeoKind::Point,
32            oid::LSEG => GeoKind::Lseg,
33            oid::BOX => GeoKind::Box,
34            oid::PATH => GeoKind::Path,
35            oid::POLYGON => GeoKind::Polygon,
36            oid::LINE => GeoKind::Line,
37            oid::CIRCLE => GeoKind::Circle,
38            _ => return None,
39        })
40    }
41
42    /// The name of the type in an error.
43    fn name(self) -> &'static str {
44        match self {
45            GeoKind::Point => "point",
46            GeoKind::Lseg => "lseg",
47            GeoKind::Box => "box",
48            GeoKind::Path => "path",
49            GeoKind::Polygon => "polygon",
50            GeoKind::Line => "line",
51            GeoKind::Circle => "circle",
52        }
53    }
54}
55
56/// A point of a geometric value.
57#[derive(Clone, Copy, Debug)]
58struct Point {
59    x: f64,
60    y: f64,
61}
62
63/// `FPzero`.
64fn fp_zero(a: f64) -> bool {
65    a.abs() <= EPSILON
66}
67
68/// `FPeq`.
69fn fp_eq(a: f64, b: f64) -> bool {
70    a == b || (a - b).abs() <= EPSILON
71}
72
73/// `float8_lt`: NaN is above every other value.
74fn float8_lt(a: f64, b: f64) -> bool {
75    !a.is_nan() && (b.is_nan() || a < b)
76}
77
78/// `float8_eq`: NaN is equal to NaN.
79fn float8_eq(a: f64, b: f64) -> bool {
80    if a.is_nan() || b.is_nan() { a.is_nan() && b.is_nan() } else { a == b }
81}
82
83/// `point_eq_point`: the fuzzy equality, or the exact equality when a coordinate is NaN.
84fn point_eq(a: Point, b: Point) -> bool {
85    if a.x.is_nan() || a.y.is_nan() || b.x.is_nan() || b.y.is_nan() {
86        return float8_eq(a.x, b.x) && float8_eq(a.y, b.y);
87    }
88    fp_eq(a.x, b.x) && fp_eq(a.y, b.y)
89}
90
91/// `22003`, `value out of range: overflow` or `value out of range: underflow`.
92fn out_of_range(what: &str) -> TypeError {
93    TypeError::new(SqlState::NUMERIC_VALUE_OUT_OF_RANGE, format!("value out of range: {what}"))
94}
95
96/// `float8_mi`.
97fn float8_mi(a: f64, b: f64) -> Result<f64, TypeError> {
98    let r = a - b;
99    if r.is_infinite() && !a.is_infinite() && !b.is_infinite() {
100        return Err(out_of_range("overflow"));
101    }
102    Ok(r)
103}
104
105/// `float8_mul`.
106fn float8_mul(a: f64, b: f64) -> Result<f64, TypeError> {
107    let r = a * b;
108    if r.is_infinite() && !a.is_infinite() && !b.is_infinite() {
109        return Err(out_of_range("overflow"));
110    }
111    if r == 0.0 && a != 0.0 && b != 0.0 {
112        return Err(out_of_range("underflow"));
113    }
114    Ok(r)
115}
116
117/// `float8_div`.
118fn float8_div(a: f64, b: f64) -> Result<f64, TypeError> {
119    if b == 0.0 && !a.is_nan() {
120        return Err(TypeError::new(SqlState::DIVISION_BY_ZERO, "division by zero".to_string()));
121    }
122    let r = a / b;
123    if r.is_infinite() && !a.is_infinite() {
124        return Err(out_of_range("overflow"));
125    }
126    if r == 0.0 && a != 0.0 && !b.is_infinite() {
127        return Err(out_of_range("underflow"));
128    }
129    Ok(r)
130}
131
132/// `point_sl`: the slope of the line through two points, which is infinity for a vertical line.
133fn point_sl(a: Point, b: Point) -> Result<f64, TypeError> {
134    if fp_eq(a.x, b.x) {
135        return Ok(f64::INFINITY);
136    }
137    if fp_eq(a.y, b.y) {
138        return Ok(0.0);
139    }
140    float8_div(float8_mi(a.y, b.y)?, float8_mi(a.x, b.x)?)
141}
142
143/// `line_construct`: the coefficients `A`, `B` and `C` of `Ax + By + C = 0` for the line through a point with a slope.
144fn line_construct(pt: Point, m: f64) -> Result<[f64; 3], TypeError> {
145    if m.is_infinite() {
146        return Ok([-1.0, 0.0, pt.x]);
147    }
148    if m == 0.0 {
149        return Ok([0.0, -1.0, pt.y]);
150    }
151    let c = float8_mi(pt.y, float8_mul(m, pt.x)?)?;
152    // The subtraction can give -0, which PostgreSQL changes to 0.
153    Ok([m, -1.0, if c == 0.0 { 0.0 } else { c }])
154}
155
156/// The reader of the text form of a geometric value, with the functions of `geo_ops.c` that read the parts. Each function takes the index of a byte and gives the index after the part.
157struct Reader<'a> {
158    text: &'a str,
159    kind: GeoKind,
160}
161
162impl Reader<'_> {
163    /// The byte at `i`, or 0 at the end, as a C string has.
164    fn at(&self, i: usize) -> u8 {
165        self.text.as_bytes().get(i).copied().unwrap_or(0)
166    }
167
168    fn skip_space(&self, mut i: usize) -> usize {
169        while is_space(self.at(i)) {
170            i += 1;
171        }
172        i
173    }
174
175    /// `22P02`, `invalid input syntax for type point: "..."`.
176    fn syntax(&self) -> TypeError {
177        TypeError::syntax(self.kind.name(), self.text)
178    }
179
180    /// An error if `i` is not the end of the text.
181    fn end(&self, i: usize) -> Result<(), TypeError> {
182        if self.at(i) == 0 { Ok(()) } else { Err(self.syntax()) }
183    }
184
185    /// An error if the byte at `i` is not `c`, else the index after it.
186    fn expect(&self, i: usize, c: u8) -> Result<usize, TypeError> {
187        if self.at(i) == c { Ok(i + 1) } else { Err(self.syntax()) }
188    }
189
190    /// `single_decode` and `float8in_internal`: a number with the white space around it.
191    fn single(&self, i: usize) -> Result<(f64, usize), TypeError> {
192        let i = self.skip_space(i);
193        if self.at(i) == 0 {
194            return Err(self.syntax());
195        }
196        let Some((value, len, range)) = strtod::<f64>(&self.text.as_bytes()[i..]) else {
197            return Err(self.syntax());
198        };
199        if range {
200            return Err(TypeError::new(
201                SqlState::NUMERIC_VALUE_OUT_OF_RANGE,
202                format!("\"{}\" is out of range for type double precision", &self.text[i..i + len]),
203            ));
204        }
205        Ok((value, self.skip_space(i + len)))
206    }
207
208    /// `pair_decode`: `x,y` or `(x,y)`.
209    fn pair(&self, i: usize) -> Result<(Point, usize), TypeError> {
210        let mut i = self.skip_space(i);
211        let delim = self.at(i) == b'(';
212        i += usize::from(delim);
213        let (x, i) = self.single(i)?;
214        let i = self.expect(i, b',')?;
215        let (y, mut i) = self.single(i)?;
216        if delim {
217            i = self.skip_space(self.expect(i, b')')?);
218        }
219        Ok((Point { x, y }, i))
220    }
221
222    /// `path_decode`: `npts` points, in `[` and `]` for an open path when `open` allows it, or in parentheses. Gives the points, true for an open path, and the index after them.
223    fn path(
224        &self,
225        i: usize,
226        open: bool,
227        npts: usize,
228    ) -> Result<(Vec<Point>, bool, usize), TypeError> {
229        let mut i = self.skip_space(i);
230        let mut depth = 0;
231        let is_open = self.at(i) == b'[';
232        if is_open {
233            if !open {
234                return Err(self.syntax());
235            }
236            depth += 1;
237            i += 1;
238        } else if self.at(i) == b'(' {
239            let cp = self.skip_space(i + 1);
240            if self.at(cp) == b'(' || !self.text.as_bytes()[i + 1..].contains(&b'(') {
241                depth += 1;
242                i = cp;
243            }
244        }
245        let mut points = Vec::with_capacity(npts.min(self.text.len()));
246        for _ in 0..npts {
247            let (p, next) = self.pair(i)?;
248            points.push(p);
249            i = next + usize::from(self.at(next) == b',');
250        }
251        while depth > 0 {
252            if self.at(i) == b')' || self.at(i) == b']' && is_open && depth == 1 {
253                depth -= 1;
254                i = self.skip_space(i + 1);
255            } else {
256                return Err(self.syntax());
257            }
258        }
259        Ok((points, is_open, i))
260    }
261
262    /// `pair_count`: the number of points of a path or a polygon, from the number of commas, which must be odd.
263    fn pair_count(&self) -> Result<usize, TypeError> {
264        let commas = self.text.bytes().filter(|&c| c == b',').count();
265        if commas % 2 == 1 { Ok(commas.div_ceil(2)) } else { Err(self.syntax()) }
266    }
267}
268
269/// The bytes of the binary form of the points.
270fn put_points(points: &[Point], out: &mut Vec<u8>) {
271    for p in points {
272        out.extend_from_slice(&p.x.to_be_bytes());
273        out.extend_from_slice(&p.y.to_be_bytes());
274    }
275}
276
277/// The count of points of a path or a polygon as an `int4`.
278fn put_count(n: usize, out: &mut Vec<u8>) {
279    out.extend_from_slice(&i32::try_from(n).unwrap_or(i32::MAX).to_be_bytes());
280}
281
282/// The corners of a box with the high corner first, as `box_in` and `box_recv` order them.
283fn box_corners(mut high: Point, mut low: Point) -> [Point; 2] {
284    if float8_lt(high.x, low.x) {
285        std::mem::swap(&mut high.x, &mut low.x);
286    }
287    if float8_lt(high.y, low.y) {
288        std::mem::swap(&mut high.y, &mut low.y);
289    }
290    [high, low]
291}
292
293/// `22P02` or `22P03`, `invalid line specification: A and B cannot both be zero`.
294fn check_line(a: f64, b: f64, binary: bool) -> Result<(), TypeError> {
295    if fp_zero(a) && fp_zero(b) {
296        let state = if binary {
297            SqlState::INVALID_BINARY_REPRESENTATION
298        } else {
299            SqlState::INVALID_TEXT_REPRESENTATION
300        };
301        return Err(TypeError::new(
302            state,
303            "invalid line specification: A and B cannot both be zero".to_string(),
304        ));
305    }
306    Ok(())
307}
308
309/// The text input functions of the geometric types, from `point_in` to `circle_in`. The value is the bytes of the binary form.
310///
311/// # Errors
312///
313/// `22P02` for text that is not valid, `22003` for a number out of the range of `double precision`, and the errors of the slope of a `line` given by two points.
314pub fn geo_in(kind: GeoKind, text: &str) -> Result<Vec<u8>, TypeError> {
315    let r = Reader { text, kind };
316    let mut out = Vec::new();
317    match kind {
318        GeoKind::Point => {
319            let (p, i) = r.pair(0)?;
320            r.end(i)?;
321            put_points(&[p], &mut out);
322        }
323        GeoKind::Lseg => {
324            let (points, _, i) = r.path(0, true, 2)?;
325            r.end(i)?;
326            put_points(&points, &mut out);
327        }
328        GeoKind::Box => {
329            let (points, _, i) = r.path(0, false, 2)?;
330            r.end(i)?;
331            put_points(&box_corners(points[0], points[1]), &mut out);
332        }
333        GeoKind::Path => {
334            let npts = r.pair_count()?;
335            let mut i = r.skip_space(0);
336            // A single opening parenthesis, as in `(1,2,3,4)`, holds the points.
337            let single = r.at(i) == b'(' && !text.as_bytes()[i + 1..].contains(&b'(');
338            i += usize::from(single);
339            let (points, open, mut i) = r.path(i, true, npts)?;
340            if single {
341                i = r.skip_space(r.expect(i, b')')?);
342            }
343            r.end(i)?;
344            out.push(u8::from(!open));
345            put_count(points.len(), &mut out);
346            put_points(&points, &mut out);
347        }
348        GeoKind::Polygon => {
349            let npts = r.pair_count()?;
350            let (points, _, i) = r.path(0, false, npts)?;
351            r.end(i)?;
352            put_count(points.len(), &mut out);
353            put_points(&points, &mut out);
354        }
355        GeoKind::Line => {
356            let i = r.skip_space(0);
357            let coefficients = if r.at(i) == b'{' {
358                let (a, i) = r.single(i + 1)?;
359                let (b, i) = r.single(r.expect(i, b',')?)?;
360                let (c, i) = r.single(r.expect(i, b',')?)?;
361                r.end(r.skip_space(r.expect(i, b'}')?))?;
362                check_line(a, b, false)?;
363                [a, b, c]
364            } else {
365                let (points, _, i) = r.path(i, true, 2)?;
366                r.end(i)?;
367                if point_eq(points[0], points[1]) {
368                    return Err(TypeError::new(
369                        SqlState::INVALID_TEXT_REPRESENTATION,
370                        "invalid line specification: must be two distinct points".to_string(),
371                    ));
372                }
373                line_construct(points[0], point_sl(points[0], points[1])?)?
374            };
375            for v in coefficients {
376                out.extend_from_slice(&v.to_be_bytes());
377            }
378        }
379        GeoKind::Circle => {
380            let mut i = r.skip_space(0);
381            let mut depth = 0;
382            if r.at(i) == b'<' {
383                depth += 1;
384                i += 1;
385            } else if r.at(i) == b'(' {
386                // Of two opening parentheses, the first one holds the circle.
387                let cp = r.skip_space(i + 1);
388                if r.at(cp) == b'(' {
389                    depth += 1;
390                    i = cp;
391                }
392            }
393            let (center, i) = r.pair(i)?;
394            let i = i + usize::from(r.at(i) == b',');
395            let (radius, mut i) = r.single(i)?;
396            if radius < 0.0 {
397                return Err(r.syntax());
398            }
399            while depth > 0 {
400                if r.at(i) == b')' || r.at(i) == b'>' && depth == 1 {
401                    depth -= 1;
402                    i = r.skip_space(i + 1);
403                } else {
404                    return Err(r.syntax());
405                }
406            }
407            r.end(i)?;
408            put_points(&[center], &mut out);
409            out.extend_from_slice(&radius.to_be_bytes());
410        }
411    }
412    Ok(out)
413}
414
415/// The numbers of the binary form from byte `from`.
416fn numbers(bytes: &[u8], from: usize) -> impl Iterator<Item = f64> + '_ {
417    bytes.get(from..).unwrap_or_default().as_chunks::<8>().0.iter().map(|c| f64::from_be_bytes(*c))
418}
419
420/// `pair_encode` in parentheses.
421fn put_pair(x: f64, y: f64, digits: i32, out: &mut Vec<u8>) {
422    out.push(b'(');
423    float8_out(x, digits, out);
424    out.push(b',');
425    float8_out(y, digits, out);
426    out.push(b')');
427}
428
429/// `path_encode`: the points from byte `from`, with commas between them.
430fn put_path(bytes: &[u8], from: usize, digits: i32, out: &mut Vec<u8>) {
431    let values: Vec<f64> = numbers(bytes, from).collect();
432    for (n, p) in values.as_chunks::<2>().0.iter().enumerate() {
433        if n > 0 {
434            out.push(b',');
435        }
436        put_pair(p[0], p[1], digits, out);
437    }
438}
439
440/// The text output functions of the geometric types, from `point_out` to `circle_out`. `digits` is `extra_float_digits`.
441pub fn geo_out(kind: GeoKind, bytes: &[u8], digits: i32, out: &mut Vec<u8>) {
442    match kind {
443        GeoKind::Point | GeoKind::Box => put_path(bytes, 0, digits, out),
444        GeoKind::Lseg => {
445            out.push(b'[');
446            put_path(bytes, 0, digits, out);
447            out.push(b']');
448        }
449        GeoKind::Path => {
450            let closed = bytes.first().is_some_and(|&c| c != 0);
451            out.push(if closed { b'(' } else { b'[' });
452            put_path(bytes, 5, digits, out);
453            out.push(if closed { b')' } else { b']' });
454        }
455        GeoKind::Polygon => {
456            out.push(b'(');
457            put_path(bytes, 4, digits, out);
458            out.push(b')');
459        }
460        GeoKind::Line => {
461            out.push(b'{');
462            for (n, v) in numbers(bytes, 0).enumerate() {
463                if n > 0 {
464                    out.push(b',');
465                }
466                float8_out(v, digits, out);
467            }
468            out.push(b'}');
469        }
470        GeoKind::Circle => {
471            let v: Vec<f64> = numbers(bytes, 0).collect();
472            if let [x, y, r] = v[..] {
473                out.push(b'<');
474                put_pair(x, y, digits, out);
475                out.push(b',');
476                float8_out(r, digits, out);
477                out.push(b'>');
478            }
479        }
480    }
481}
482
483/// `n` points of the binary form.
484fn recv_points(recv: &mut Recv<'_>, n: usize) -> Result<Vec<Point>, TypeError> {
485    let mut points = Vec::with_capacity(n.min(recv.remaining() / 16));
486    for _ in 0..n {
487        let x = recv.f64()?;
488        points.push(Point { x, y: recv.f64()? });
489    }
490    Ok(points)
491}
492
493/// The count of points of a path or a polygon in the binary form, which must be more than 0 and fit in an `int` with the header.
494fn recv_count(recv: &mut Recv<'_>, header: usize, name: &str) -> Result<usize, TypeError> {
495    let n = recv.i32()?;
496    let limit = (0x7fff_ffff - header) / 16;
497    usize::try_from(n).ok().filter(|&n| n > 0 && n < limit).ok_or_else(|| {
498        TypeError::new(
499            SqlState::INVALID_BINARY_REPRESENTATION,
500            format!("invalid number of points in external \"{name}\" value"),
501        )
502    })
503}
504
505/// The receive functions of the geometric types, from `point_recv` to `circle_recv`. The corners of a box are put in order and the flag of a path is 0 or 1.
506///
507/// # Errors
508///
509/// `22P03` for a `line` whose `A` and `B` are zero, a `circle` with a negative radius, or a path or a polygon with a count of points that is not valid, and `08P01` for too few bytes.
510pub fn geo_recv(kind: GeoKind, recv: &mut Recv<'_>) -> Result<Vec<u8>, TypeError> {
511    let mut out = Vec::new();
512    match kind {
513        GeoKind::Point => put_points(&recv_points(recv, 1)?, &mut out),
514        GeoKind::Lseg => put_points(&recv_points(recv, 2)?, &mut out),
515        GeoKind::Box => {
516            let p = recv_points(recv, 2)?;
517            put_points(&box_corners(p[0], p[1]), &mut out);
518        }
519        GeoKind::Path => {
520            let closed = recv.byte()? != 0;
521            let n = recv_count(recv, 16, "path")?;
522            let points = recv_points(recv, n)?;
523            out.push(u8::from(closed));
524            put_count(n, &mut out);
525            put_points(&points, &mut out);
526        }
527        GeoKind::Polygon => {
528            let n = recv_count(recv, 40, "polygon")?;
529            let points = recv_points(recv, n)?;
530            put_count(n, &mut out);
531            put_points(&points, &mut out);
532        }
533        GeoKind::Line => {
534            let (a, b, c) = (recv.f64()?, recv.f64()?, recv.f64()?);
535            check_line(a, b, true)?;
536            for v in [a, b, c] {
537                out.extend_from_slice(&v.to_be_bytes());
538            }
539        }
540        GeoKind::Circle => {
541            let center = recv_points(recv, 1)?;
542            let radius = recv.f64()?;
543            if radius < 0.0 {
544                return Err(TypeError::new(
545                    SqlState::INVALID_BINARY_REPRESENTATION,
546                    "invalid radius in external \"circle\" value".to_string(),
547                ));
548            }
549            put_points(&center, &mut out);
550            out.extend_from_slice(&radius.to_be_bytes());
551        }
552    }
553    Ok(out)
554}
555
556#[cfg(test)]
557mod tests {
558    use super::*;
559
560    fn text(kind: GeoKind, s: &str) -> String {
561        let bytes = geo_in(kind, s).unwrap();
562        let mut out = Vec::new();
563        geo_out(kind, &bytes, 1, &mut out);
564        String::from_utf8(out).unwrap()
565    }
566
567    fn error(kind: GeoKind, s: &str) -> String {
568        geo_in(kind, s).unwrap_err().message
569    }
570
571    /// The values and the errors of PostgreSQL 19 for the same text.
572    #[test]
573    fn text_forms() {
574        assert_eq!(text(GeoKind::Point, " ( 1.5 , -2 ) "), "(1.5,-2)");
575        assert_eq!(text(GeoKind::Point, "(NaN,Infinity)"), "(NaN,Infinity)");
576        assert_eq!(error(GeoKind::Point, "(1,2"), "invalid input syntax for type point: \"(1,2\"");
577        assert_eq!(
578            error(GeoKind::Point, "(1e400,2)"),
579            "\"1e400\" is out of range for type double precision"
580        );
581        assert_eq!(text(GeoKind::Lseg, "(1,2,3,4)"), "[(1,2),(3,4)]");
582        assert_eq!(text(GeoKind::Box, "(NaN,1),(2,3)"), "(NaN,3),(2,1)");
583        assert!(geo_in(GeoKind::Box, "[(1,2),(3,4)]").is_err());
584        assert_eq!(text(GeoKind::Line, "(1,2),(3,7)"), "{2.5,-1,-0.5}");
585        assert_eq!(text(GeoKind::Line, "(0,0),(0,5)"), "{-1,0,0}");
586        assert_eq!(
587            error(GeoKind::Line, "{1e-7,0,1}"),
588            "invalid line specification: A and B cannot both be zero"
589        );
590        assert_eq!(text(GeoKind::Path, "(1,2,3,4)"), "((1,2),(3,4))");
591        assert_eq!(text(GeoKind::Path, "[(1,2)]"), "[(1,2)]");
592        assert!(geo_in(GeoKind::Path, "(1,2),(3,4)]").is_err());
593        assert_eq!(text(GeoKind::Polygon, "1,2,3,4,5,6"), "((1,2),(3,4),(5,6))");
594        assert_eq!(text(GeoKind::Circle, "((1,2),3>"), "<(1,2),3>");
595        assert!(geo_in(GeoKind::Circle, "(1,2,3)").is_err());
596        assert!(geo_in(GeoKind::Circle, "<(1,2),-1>").is_err());
597    }
598
599    #[test]
600    fn binary_forms() {
601        let bytes = geo_in(GeoKind::Path, "[(1,2),(3,4)]").unwrap();
602        assert_eq!(bytes.len(), 37);
603        assert_eq!(geo_recv(GeoKind::Path, &mut Recv::new(&bytes)).unwrap(), bytes);
604        let mut bad = bytes.clone();
605        bad[1..5].copy_from_slice(&0i32.to_be_bytes());
606        assert!(geo_recv(GeoKind::Path, &mut Recv::new(&bad)).is_err());
607        let line = [0.0f64, 0.0, 1.0].iter().flat_map(|v| v.to_be_bytes()).collect::<Vec<u8>>();
608        let e = geo_recv(GeoKind::Line, &mut Recv::new(&line)).unwrap_err();
609        assert_eq!(e.sqlstate.as_str(), "22P03");
610    }
611}
rupg_types/geo.rs

rupg_types/
geo.rs
