geometry_io_wkt/
lexer.rs

1//! The WKT tokenizer and its error type.
2//!
3//! Mirrors the `tokenizer` block in `boost/geometry/io/wkt/read.hpp`
4//! (Boost drives the read with `boost::tokenizer` over a small set of
5//! separators). This port hand-rolls the scan so it can classify each
6//! lexeme into a [`Token`] up front — identifiers (uppercased keywords
7//! such as `POINT`, `LINESTRING`, the OGC `Z`/`M`/`ZM` dimension
8//! suffixes, and `EMPTY`), signed decimal / E-notation numbers, and the
9//! `(`, `)`, `,` punctuation the grammar uses.
10//!
11//! Reference: OGC Simple Feature Access Part 1 §7 for the WKT grammar,
12//! and `boost/geometry/io/wkt/read.hpp` for the C++ tokenizer.
13
14use alloc::string::{String, ToString};
15#[cfg(test)]
16use alloc::vec::Vec;
17
18/// One lexeme of a WKT string.
19///
20/// Mirrors the token classes the `boost::tokenizer` in
21/// `boost/geometry/io/wkt/read.hpp` separates on: a keyword/identifier,
22/// a number, the three punctuation marks, and end-of-input. `EMPTY` is
23/// broken out as its own token (rather than folded into `Ident`) so the
24/// parser can branch on `<TYPE> EMPTY` without re-comparing strings.
25#[derive(Debug, Clone, PartialEq)]
26pub enum Token {
27    /// An uppercased keyword — a geometry type (`POINT`, `LINESTRING`,
28    /// …) or an OGC dimension suffix (`Z`, `M`, `ZM`).
29    Ident(String),
30    /// A numeric literal, already parsed to `f64` (signed, decimal,
31    /// E-notation).
32    Number(f64),
33    /// `(`
34    LeftParen,
35    /// `)`
36    RightParen,
37    /// `,`
38    Comma,
39    /// The `EMPTY` keyword.
40    Empty,
41    /// End of input.
42    Eof,
43}
44
45/// Everything that can go wrong reading WKT.
46///
47/// Covers the lexer's character-level failures plus the parser's
48/// token-level and type-level failures, so a single error type flows
49/// through the whole read path (mirroring how
50/// `boost/geometry/io/wkt/read.hpp` throws a single
51/// `read_wkt_exception`).
52#[derive(Debug, Clone, PartialEq)]
53pub enum WktError {
54    /// A character that cannot begin any lexeme, at byte offset `pos`.
55    UnexpectedChar {
56        /// Byte offset of the offending character in the input.
57        pos: usize,
58        /// The offending character.
59        ch: char,
60    },
61    /// A token that does not fit the grammar at this point.
62    UnexpectedToken {
63        /// A human-readable description of what the parser wanted.
64        expected: &'static str,
65        /// A `Debug`-style rendering of the token actually found.
66        found: String,
67    },
68    /// Input ended while the parser still needed more tokens.
69    UnexpectedEof,
70    /// A numeric lexeme that failed to parse as `f64`.
71    InvalidNumber(String),
72    /// A leading keyword that is not a known OGC geometry type.
73    UnknownGeometryType(String),
74    /// A typed-parse convenience function was handed WKT of the wrong
75    /// kind (e.g. [`crate::parse_point`] on a `LINESTRING`).
76    TypeMismatch {
77        /// The kind the caller asked for.
78        expected: &'static str,
79        /// The kind actually present in the input.
80        found: &'static str,
81    },
82    /// Nested `GEOMETRYCOLLECTION`s exceeded the reader's recursion limit.
83    /// Rejecting deep nesting keeps a hostile string from overflowing the
84    /// native stack (an uncatchable process abort).
85    NestingTooDeep,
86}
87
88impl core::fmt::Display for WktError {
89    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
90        match self {
91            WktError::UnexpectedChar { pos, ch } => {
92                write!(f, "unexpected character {ch:?} at byte {pos}")
93            }
94            WktError::UnexpectedToken { expected, found } => {
95                write!(f, "expected {expected}, found {found}")
96            }
97            WktError::UnexpectedEof => f.write_str("unexpected end of input"),
98            WktError::InvalidNumber(s) => write!(f, "invalid number {s:?}"),
99            WktError::UnknownGeometryType(s) => write!(f, "unknown geometry type {s:?}"),
100            WktError::TypeMismatch { expected, found } => {
101                write!(f, "type mismatch: expected {expected}, found {found}")
102            }
103            WktError::NestingTooDeep => {
104                f.write_str("WKT nesting too deep; exceeded the reader's recursion limit")
105            }
106        }
107    }
108}
109
110#[cfg(feature = "std")]
111impl std::error::Error for WktError {}
112
113/// Split a WKT string into its token stream.
114///
115/// Whitespace separates tokens and is otherwise discarded. Identifiers
116/// (ASCII letters) are uppercased so `Point`, `POINT`, and `point` all
117/// lex to the same keyword — matching the case-insensitivity Boost gets
118/// from comparing against upper-cased keyword tables in
119/// `boost/geometry/io/wkt/read.hpp`. Numbers accept an optional sign, a
120/// decimal point, and an `e`/`E` exponent (e.g. `1.5e-3`). The stream
121/// always ends with a single [`Token::Eof`].
122///
123/// # Errors
124///
125/// Returns [`WktError::UnexpectedChar`] for a character that cannot
126/// start any lexeme, and [`WktError::InvalidNumber`] for a numeric
127/// lexeme that fails to parse as `f64`.
128pub(crate) struct Lexer<'a> {
129    input: &'a str,
130    pos: usize,
131}
132
133impl<'a> Lexer<'a> {
134    pub(crate) fn new(input: &'a str) -> Self {
135        Self { input, pos: 0 }
136    }
137
138    /// Scan and return one token, leaving the rest of the input untouched.
139    /// The parser asks for the next token only after consuming the current
140    /// one, avoiding an allocated copy of the complete token stream.
141    pub(crate) fn next_token(&mut self) -> Result<Token, WktError> {
142        let bytes = self.input.as_bytes();
143        while let Some(&byte) = bytes.get(self.pos) {
144            if byte.is_ascii_whitespace() {
145                self.pos += 1;
146            } else if !byte.is_ascii() {
147                let ch = self.input[self.pos..]
148                    .chars()
149                    .next()
150                    .expect("position is inside the input");
151                if ch.is_whitespace() {
152                    self.pos += ch.len_utf8();
153                } else {
154                    break;
155                }
156            } else {
157                break;
158            }
159        }
160
161        let Some(&byte) = bytes.get(self.pos) else {
162            return Ok(Token::Eof);
163        };
164        let start = self.pos;
165        if byte == b'(' {
166            self.pos += 1;
167            Ok(Token::LeftParen)
168        } else if byte == b')' {
169            self.pos += 1;
170            Ok(Token::RightParen)
171        } else if byte == b',' {
172            self.pos += 1;
173            Ok(Token::Comma)
174        } else if byte.is_ascii_alphabetic() {
175            self.pos += 1;
176            while bytes.get(self.pos).is_some_and(u8::is_ascii_alphabetic) {
177                self.pos += 1;
178            }
179            let word = self.input[start..self.pos].to_ascii_uppercase();
180            if word == "EMPTY" {
181                Ok(Token::Empty)
182            } else {
183                Ok(Token::Ident(word))
184            }
185        } else if byte == b'+' || byte == b'-' || byte == b'.' || byte.is_ascii_digit() {
186            let negative = byte == b'-';
187            let mut all_digits = byte == b'+' || byte == b'-' || byte.is_ascii_digit();
188            let mut saw_digit = byte.is_ascii_digit();
189            let mut integer = if saw_digit { u64::from(byte - b'0') } else { 0 };
190            self.pos += 1;
191            while let Some(&byte) = bytes.get(self.pos) {
192                if byte.is_ascii_digit()
193                    || byte == b'.'
194                    || byte == b'+'
195                    || byte == b'-'
196                    || byte == b'e'
197                    || byte == b'E'
198                {
199                    if all_digits {
200                        if byte.is_ascii_digit() {
201                            saw_digit = true;
202                            match integer
203                                .checked_mul(10)
204                                .and_then(|value| value.checked_add(u64::from(byte - b'0')))
205                            {
206                                Some(next) => integer = next,
207                                None => all_digits = false,
208                            }
209                        } else {
210                            all_digits = false;
211                        }
212                    }
213                    self.pos += 1;
214                } else {
215                    break;
216                }
217            }
218            let slice = &self.input[start..self.pos];
219            let value = if all_digits && saw_digit {
220                #[allow(
221                    clippy::cast_precision_loss,
222                    reason = "integer-to-f64 uses the same IEEE-754 rounding as parsing its decimal spelling"
223                )]
224                let value = integer as f64;
225                if negative { -value } else { value }
226            } else {
227                let parsed: f64 = slice
228                    .parse()
229                    .map_err(|_| WktError::InvalidNumber(slice.to_string()))?;
230                // `str::parse` maps an out-of-range exponent to an infinity
231                // rather than failing, so `1e400` would otherwise enter the
232                // model as `+inf` — a value WKT cannot spell on the way back
233                // out. The integer fast path above cannot reach here
234                // non-finite: it falls through to this branch on overflow.
235                if !parsed.is_finite() {
236                    return Err(WktError::InvalidNumber(slice.to_string()));
237                }
238                parsed
239            };
240            Ok(Token::Number(value))
241        } else {
242            let ch = self.input[self.pos..]
243                .chars()
244                .next()
245                .expect("position is inside the input");
246            Err(WktError::UnexpectedChar { pos: self.pos, ch })
247        }
248    }
249}
250
251#[cfg(test)]
252pub(crate) fn tokenize(input: &str) -> Result<Vec<Token>, WktError> {
253    let mut lexer = Lexer::new(input);
254    let mut tokens = Vec::new();
255    loop {
256        let token = lexer.next_token()?;
257        let done = token == Token::Eof;
258        tokens.push(token);
259        if done {
260            return Ok(tokens);
261        }
262    }
263}
264
265#[cfg(test)]
266mod tests {
267    //! One case per token kind plus a malformed-input fixture per lexer
268    //! error category. Mirrors the tokenizer coverage in
269    //! `boost/geometry/test/io/wkt/wkt.cpp`.
270    #![allow(
271        clippy::float_cmp,
272        reason = "number tokens come from exact integer / short-decimal WKT literals"
273    )]
274
275    use super::{Token, WktError, tokenize};
276    use alloc::vec;
277
278    #[test]
279    fn each_token_kind() {
280        let toks = tokenize("POINT ( 1 , 2 )").unwrap();
281        assert_eq!(
282            toks,
283            vec![
284                Token::Ident("POINT".into()),
285                Token::LeftParen,
286                Token::Number(1.0),
287                Token::Comma,
288                Token::Number(2.0),
289                Token::RightParen,
290                Token::Eof,
291            ]
292        );
293    }
294
295    #[test]
296    fn identifiers_are_uppercased() {
297        let toks = tokenize("LineString").unwrap();
298        assert_eq!(toks, vec![Token::Ident("LINESTRING".into()), Token::Eof]);
299    }
300
301    #[test]
302    fn empty_is_its_own_token() {
303        let toks = tokenize("POINT EMPTY").unwrap();
304        assert_eq!(
305            toks,
306            vec![Token::Ident("POINT".into()), Token::Empty, Token::Eof]
307        );
308    }
309
310    #[test]
311    fn dimension_suffix_lexes_as_ident() {
312        let toks = tokenize("POINT ZM").unwrap();
313        assert_eq!(
314            toks,
315            vec![
316                Token::Ident("POINT".into()),
317                Token::Ident("ZM".into()),
318                Token::Eof,
319            ]
320        );
321    }
322
323    #[test]
324    fn number_e_notation() {
325        let toks = tokenize("1.5e-3").unwrap();
326        assert_eq!(toks, vec![Token::Number(0.0015), Token::Eof]);
327    }
328
329    #[test]
330    fn number_signed_and_decimal() {
331        let toks = tokenize("-10 20.5 +3").unwrap();
332        assert_eq!(
333            toks,
334            vec![
335                Token::Number(-10.0),
336                Token::Number(20.5),
337                Token::Number(3.0),
338                Token::Eof,
339            ]
340        );
341    }
342
343    #[test]
344    fn integral_fast_path_matches_standard_float_rounding() {
345        for literal in [
346            "0",
347            "-0",
348            "9007199254740993",
349            "18446744073709551615",
350            "-18446744073709551615",
351        ] {
352            let expected = literal.parse::<f64>().unwrap();
353            let tokens = tokenize(literal).unwrap();
354            assert!(
355                matches!(&tokens[0], Token::Number(actual) if actual.to_bits() == expected.to_bits()),
356                "literal {literal}: expected number token {expected:?}"
357            );
358        }
359    }
360
361    #[test]
362    fn malformed_char_reports_position() {
363        let err = tokenize("POINT (1 @)").unwrap_err();
364        assert_eq!(err, WktError::UnexpectedChar { pos: 9, ch: '@' });
365    }
366
367    #[test]
368    fn malformed_number_reports_slice() {
369        let err = tokenize("1.2.3").unwrap_err();
370        assert_eq!(err, WktError::InvalidNumber("1.2.3".into()));
371    }
372
373    /// An exponent too large for `f64` is rejected rather than silently
374    /// becoming an infinity. `str::parse` returns `Ok(inf)` for these, so
375    /// without the finiteness check `POINT(1e400 1)` would enter the
376    /// model as `+inf` and come back out as the unparseable
377    /// `POINT(inf 1)`.
378    #[test]
379    fn overflowing_exponent_is_rejected_not_infinity() {
380        for literal in ["1e400", "-1e400", "1.5e309"] {
381            assert_eq!(
382                tokenize(literal).unwrap_err(),
383                WktError::InvalidNumber(literal.into()),
384                "literal {literal}"
385            );
386        }
387    }
388
389    /// Underflow is not an error: it rounds to a finite zero, which WKT
390    /// can spell and which round-trips.
391    #[test]
392    fn underflowing_exponent_is_a_finite_zero() {
393        let tokens = tokenize("1e-400").unwrap();
394        assert!(matches!(tokens[0], Token::Number(v) if v == 0.0));
395    }
396
397    /// Every `WktError` variant renders a distinct message through its
398    /// `Display` impl, embedding its payload.
399    #[test]
400    fn every_error_variant_displays_descriptively() {
401        use alloc::format;
402
403        assert_eq!(
404            format!("{}", WktError::UnexpectedChar { pos: 9, ch: '@' }),
405            "unexpected character '@' at byte 9"
406        );
407        assert_eq!(
408            format!(
409                "{}",
410                WktError::UnexpectedToken {
411                    expected: "'('",
412                    found: "Comma".into()
413                }
414            ),
415            "expected '(', found Comma"
416        );
417        assert_eq!(
418            format!("{}", WktError::UnexpectedEof),
419            "unexpected end of input"
420        );
421        assert_eq!(
422            format!("{}", WktError::InvalidNumber("1.2.3".into())),
423            "invalid number \"1.2.3\""
424        );
425        assert_eq!(
426            format!("{}", WktError::UnknownGeometryType("TRIANGLE".into())),
427            "unknown geometry type \"TRIANGLE\""
428        );
429        assert_eq!(
430            format!(
431                "{}",
432                WktError::TypeMismatch {
433                    expected: "POINT",
434                    found: "LINESTRING"
435                }
436            ),
437            "type mismatch: expected POINT, found LINESTRING"
438        );
439        assert!(
440            format!("{}", WktError::NestingTooDeep).contains("nesting too deep"),
441            "nesting message"
442        );
443    }
444}
geometry_io_wkt/lexer.rs

geometry_io_wkt/
lexer.rs
