regex_syntax/hir/
print.rs

1/*!
2This module provides a regular expression printer for `Hir`.
3*/
4
5use core::fmt;
6
7use crate::{
8    hir::{
9        self,
10        visitor::{self, Visitor},
11        Hir, HirKind,
12    },
13    is_meta_character,
14};
15
16/// A builder for constructing a printer.
17///
18/// Note that since a printer doesn't have any configuration knobs, this type
19/// remains unexported.
20#[derive(Clone, Debug)]
21struct PrinterBuilder {
22    _priv: (),
23}
24
25impl Default for PrinterBuilder {
26    fn default() -> PrinterBuilder {
27        PrinterBuilder::new()
28    }
29}
30
31impl PrinterBuilder {
32    fn new() -> PrinterBuilder {
33        PrinterBuilder { _priv: () }
34    }
35
36    fn build(&self) -> Printer {
37        Printer { _priv: () }
38    }
39}
40
41/// A printer for a regular expression's high-level intermediate
42/// representation.
43///
44/// A printer converts a high-level intermediate representation (HIR) to a
45/// regular expression pattern string. This particular printer uses constant
46/// stack space and heap space proportional to the size of the HIR.
47///
48/// Since this printer is only using the HIR, the pattern it prints will likely
49/// not resemble the original pattern at all. For example, a pattern like
50/// `\pL` will have its entire class written out.
51///
52/// The purpose of this printer is to provide a means to mutate an HIR and then
53/// build a regular expression from the result of that mutation. (A regex
54/// library could provide a constructor from this HIR explicitly, but that
55/// creates an unnecessary public coupling between the regex library and this
56/// specific HIR representation.)
57#[derive(Debug)]
58pub struct Printer {
59    _priv: (),
60}
61
62impl Printer {
63    /// Create a new printer.
64    pub fn new() -> Printer {
65        PrinterBuilder::new().build()
66    }
67
68    /// Print the given `Ast` to the given writer. The writer must implement
69    /// `fmt::Write`. Typical implementations of `fmt::Write` that can be used
70    /// here are a `fmt::Formatter` (which is available in `fmt::Display`
71    /// implementations) or a `&mut String`.
72    pub fn print<W: fmt::Write>(&mut self, hir: &Hir, wtr: W) -> fmt::Result {
73        visitor::visit(hir, Writer { wtr })
74    }
75}
76
77#[derive(Debug)]
78struct Writer<W> {
79    wtr: W,
80}
81
82impl<W: fmt::Write> Visitor for Writer<W> {
83    type Output = ();
84    type Err = fmt::Error;
85
86    fn finish(self) -> fmt::Result {
87        Ok(())
88    }
89
90    fn visit_pre(&mut self, hir: &Hir) -> fmt::Result {
91        match *hir.kind() {
92            HirKind::Empty => {
93                // Technically an empty sub-expression could be "printed" by
94                // just ignoring it, but in practice, you could have a
95                // repetition operator attached to an empty expression, and you
96                // really need something in the concrete syntax to make that
97                // work as you'd expect.
98                self.wtr.write_str(r"(?:)")?;
99            }
100            // Repetition operators are strictly suffix oriented.
101            HirKind::Repetition(_) => {}
102            HirKind::Literal(hir::Literal(ref bytes)) => {
103                // See the comment on the 'Concat' and 'Alternation' case below
104                // for why we put parens here. Literals are, conceptually,
105                // a special case of concatenation where each element is a
106                // character. The HIR flattens this into a Box<[u8]>, but we
107                // still need to treat it like a concatenation for correct
108                // printing. As a special case, we don't write parens if there
109                // is only one character. One character means there is no
110                // concat so we don't need parens. Adding parens would still be
111                // correct, but we drop them here because it tends to create
112                // rather noisy regexes even in simple cases.
113                let result = core::str::from_utf8(bytes);
114                let len = result.map_or(bytes.len(), |s| s.chars().count());
115                if len > 1 {
116                    self.wtr.write_str(r"(?:")?;
117                }
118                match result {
119                    Ok(string) => {
120                        for c in string.chars() {
121                            self.write_literal_char(c)?;
122                        }
123                    }
124                    Err(_) => {
125                        for &b in bytes.iter() {
126                            self.write_literal_byte(b)?;
127                        }
128                    }
129                }
130                if len > 1 {
131                    self.wtr.write_str(r")")?;
132                }
133            }
134            HirKind::Class(hir::Class::Unicode(ref cls)) => {
135                if cls.ranges().is_empty() {
136                    return self.wtr.write_str("[a&&b]");
137                }
138                self.wtr.write_str("[")?;
139                for range in cls.iter() {
140                    if range.start() == range.end() {
141                        self.write_literal_char(range.start())?;
142                    } else if u32::from(range.start()) + 1
143                        == u32::from(range.end())
144                    {
145                        self.write_literal_char(range.start())?;
146                        self.write_literal_char(range.end())?;
147                    } else {
148                        self.write_literal_char(range.start())?;
149                        self.wtr.write_str("-")?;
150                        self.write_literal_char(range.end())?;
151                    }
152                }
153                self.wtr.write_str("]")?;
154            }
155            HirKind::Class(hir::Class::Bytes(ref cls)) => {
156                if cls.ranges().is_empty() {
157                    return self.wtr.write_str("[a&&b]");
158                }
159                self.wtr.write_str("(?-u:[")?;
160                for range in cls.iter() {
161                    if range.start() == range.end() {
162                        self.write_literal_class_byte(range.start())?;
163                    } else if range.start() + 1 == range.end() {
164                        self.write_literal_class_byte(range.start())?;
165                        self.write_literal_class_byte(range.end())?;
166                    } else {
167                        self.write_literal_class_byte(range.start())?;
168                        self.wtr.write_str("-")?;
169                        self.write_literal_class_byte(range.end())?;
170                    }
171                }
172                self.wtr.write_str("])")?;
173            }
174            HirKind::Look(ref look) => match *look {
175                hir::Look::Start => {
176                    self.wtr.write_str(r"\A")?;
177                }
178                hir::Look::End => {
179                    self.wtr.write_str(r"\z")?;
180                }
181                hir::Look::StartLF => {
182                    self.wtr.write_str("(?m:^)")?;
183                }
184                hir::Look::EndLF => {
185                    self.wtr.write_str("(?m:$)")?;
186                }
187                hir::Look::StartCRLF => {
188                    self.wtr.write_str("(?mR:^)")?;
189                }
190                hir::Look::EndCRLF => {
191                    self.wtr.write_str("(?mR:$)")?;
192                }
193                hir::Look::WordAscii => {
194                    self.wtr.write_str(r"(?-u:\b)")?;
195                }
196                hir::Look::WordAsciiNegate => {
197                    self.wtr.write_str(r"(?-u:\B)")?;
198                }
199                hir::Look::WordUnicode => {
200                    self.wtr.write_str(r"\b")?;
201                }
202                hir::Look::WordUnicodeNegate => {
203                    self.wtr.write_str(r"\B")?;
204                }
205                hir::Look::WordStartAscii => {
206                    self.wtr.write_str(r"(?-u:\b{start})")?;
207                }
208                hir::Look::WordEndAscii => {
209                    self.wtr.write_str(r"(?-u:\b{end})")?;
210                }
211                hir::Look::WordStartUnicode => {
212                    self.wtr.write_str(r"\b{start}")?;
213                }
214                hir::Look::WordEndUnicode => {
215                    self.wtr.write_str(r"\b{end}")?;
216                }
217                hir::Look::WordStartHalfAscii => {
218                    self.wtr.write_str(r"(?-u:\b{start-half})")?;
219                }
220                hir::Look::WordEndHalfAscii => {
221                    self.wtr.write_str(r"(?-u:\b{end-half})")?;
222                }
223                hir::Look::WordStartHalfUnicode => {
224                    self.wtr.write_str(r"\b{start-half}")?;
225                }
226                hir::Look::WordEndHalfUnicode => {
227                    self.wtr.write_str(r"\b{end-half}")?;
228                }
229            },
230            HirKind::Capture(hir::Capture { ref name, .. }) => {
231                self.wtr.write_str("(")?;
232                if let Some(ref name) = *name {
233                    write!(self.wtr, "?P<{}>", name)?;
234                }
235            }
236            // Why do this? Wrapping concats and alts in non-capturing groups
237            // is not *always* necessary, but is sometimes necessary. For
238            // example, 'concat(a, alt(b, c))' should be written as 'a(?:b|c)'
239            // and not 'ab|c'. The former is clearly the intended meaning, but
240            // the latter is actually 'alt(concat(a, b), c)'.
241            //
242            // It would be possible to only group these things in cases where
243            // it's strictly necessary, but it requires knowing the parent
244            // expression. And since this technique is simpler and always
245            // correct, we take this route. More to the point, it is a non-goal
246            // of an HIR printer to show a nice easy-to-read regex. Indeed,
247            // its construction forbids it from doing so. Therefore, inserting
248            // extra groups where they aren't necessary is perfectly okay.
249            HirKind::Concat(_) | HirKind::Alternation(_) => {
250                self.wtr.write_str(r"(?:")?;
251            }
252        }
253        Ok(())
254    }
255
256    fn visit_post(&mut self, hir: &Hir) -> fmt::Result {
257        match *hir.kind() {
258            // Handled during visit_pre
259            HirKind::Empty
260            | HirKind::Literal(_)
261            | HirKind::Class(_)
262            | HirKind::Look(_) => {}
263            HirKind::Repetition(ref x) => {
264                match (x.min, x.max) {
265                    (0, Some(1)) => {
266                        self.wtr.write_str("?")?;
267                    }
268                    (0, None) => {
269                        self.wtr.write_str("*")?;
270                    }
271                    (1, None) => {
272                        self.wtr.write_str("+")?;
273                    }
274                    (1, Some(1)) => {
275                        // 'a{1}' and 'a{1}?' are exactly equivalent to 'a'.
276                        return Ok(());
277                    }
278                    (m, None) => {
279                        write!(self.wtr, "{{{},}}", m)?;
280                    }
281                    (m, Some(n)) if m == n => {
282                        write!(self.wtr, "{{{}}}", m)?;
283                        // a{m} and a{m}? are always exactly equivalent.
284                        return Ok(());
285                    }
286                    (m, Some(n)) => {
287                        write!(self.wtr, "{{{},{}}}", m, n)?;
288                    }
289                }
290                if !x.greedy {
291                    self.wtr.write_str("?")?;
292                }
293            }
294            HirKind::Capture(_)
295            | HirKind::Concat(_)
296            | HirKind::Alternation(_) => {
297                self.wtr.write_str(r")")?;
298            }
299        }
300        Ok(())
301    }
302
303    fn visit_alternation_in(&mut self) -> fmt::Result {
304        self.wtr.write_str("|")
305    }
306}
307
308impl<W: fmt::Write> Writer<W> {
309    fn write_literal_char(&mut self, c: char) -> fmt::Result {
310        if is_meta_character(c) {
311            self.wtr.write_str("\\")?;
312        }
313        self.wtr.write_char(c)
314    }
315
316    fn write_literal_byte(&mut self, b: u8) -> fmt::Result {
317        if b <= 0x7F && !b.is_ascii_control() && !b.is_ascii_whitespace() {
318            self.write_literal_char(char::try_from(b).unwrap())
319        } else {
320            write!(self.wtr, "(?-u:\\x{:02X})", b)
321        }
322    }
323
324    fn write_literal_class_byte(&mut self, b: u8) -> fmt::Result {
325        if b <= 0x7F && !b.is_ascii_control() && !b.is_ascii_whitespace() {
326            self.write_literal_char(char::try_from(b).unwrap())
327        } else {
328            write!(self.wtr, "\\x{:02X}", b)
329        }
330    }
331}
332
333#[cfg(test)]
334mod tests {
335    use alloc::{
336        boxed::Box,
337        string::{String, ToString},
338    };
339
340    use crate::ParserBuilder;
341
342    use super::*;
343
344    fn roundtrip(given: &str, expected: &str) {
345        roundtrip_with(|b| b, given, expected);
346    }
347
348    fn roundtrip_bytes(given: &str, expected: &str) {
349        roundtrip_with(|b| b.utf8(false), given, expected);
350    }
351
352    fn roundtrip_with<F>(mut f: F, given: &str, expected: &str)
353    where
354        F: FnMut(&mut ParserBuilder) -> &mut ParserBuilder,
355    {
356        let mut builder = ParserBuilder::new();
357        f(&mut builder);
358        let hir = builder.build().parse(given).unwrap();
359
360        let mut printer = Printer::new();
361        let mut dst = String::new();
362        printer.print(&hir, &mut dst).unwrap();
363
364        // Check that the result is actually valid.
365        builder.build().parse(&dst).unwrap();
366
367        assert_eq!(expected, dst);
368    }
369
370    #[test]
371    fn print_literal() {
372        roundtrip("a", "a");
373        roundtrip(r"\xff", "\u{FF}");
374        roundtrip_bytes(r"\xff", "\u{FF}");
375        roundtrip_bytes(r"(?-u)\xff", r"(?-u:\xFF)");
376        roundtrip("☃", "☃");
377    }
378
379    #[test]
380    fn print_class() {
381        roundtrip(r"[a]", r"a");
382        roundtrip(r"[ab]", r"[ab]");
383        roundtrip(r"[a-z]", r"[a-z]");
384        roundtrip(r"[a-z--b-c--x-y]", r"[ad-wz]");
385        roundtrip(r"[^\x01-\u{10FFFF}]", "\u{0}");
386        roundtrip(r"[-]", r"\-");
387        roundtrip(r"[☃-⛄]", r"[☃-⛄]");
388
389        roundtrip(r"(?-u)[a]", r"a");
390        roundtrip(r"(?-u)[ab]", r"(?-u:[ab])");
391        roundtrip(r"(?-u)[a-z]", r"(?-u:[a-z])");
392        roundtrip_bytes(r"(?-u)[a-\xFF]", r"(?-u:[a-\xFF])");
393
394        // The following test that the printer escapes meta characters
395        // in character classes.
396        roundtrip(r"[\[]", r"\[");
397        roundtrip(r"[Z-_]", r"[Z-_]");
398        roundtrip(r"[Z-_--Z]", r"[\[-_]");
399
400        // The following test that the printer escapes meta characters
401        // in byte oriented character classes.
402        roundtrip_bytes(r"(?-u)[\[]", r"\[");
403        roundtrip_bytes(r"(?-u)[Z-_]", r"(?-u:[Z-_])");
404        roundtrip_bytes(r"(?-u)[Z-_--Z]", r"(?-u:[\[-_])");
405
406        // This tests that an empty character class is correctly roundtripped.
407        #[cfg(feature = "unicode-gencat")]
408        roundtrip(r"\P{any}", r"[a&&b]");
409        roundtrip_bytes(r"(?-u)[^\x00-\xFF]", r"[a&&b]");
410    }
411
412    #[test]
413    fn print_anchor() {
414        roundtrip(r"^", r"\A");
415        roundtrip(r"$", r"\z");
416        roundtrip(r"(?m)^", r"(?m:^)");
417        roundtrip(r"(?m)$", r"(?m:$)");
418    }
419
420    #[test]
421    fn print_word_boundary() {
422        roundtrip(r"\b", r"\b");
423        roundtrip(r"\B", r"\B");
424        roundtrip(r"(?-u)\b", r"(?-u:\b)");
425        roundtrip_bytes(r"(?-u)\B", r"(?-u:\B)");
426    }
427
428    #[test]
429    fn print_repetition() {
430        roundtrip("a?", "a?");
431        roundtrip("a??", "a??");
432        roundtrip("(?U)a?", "a??");
433
434        roundtrip("a*", "a*");
435        roundtrip("a*?", "a*?");
436        roundtrip("(?U)a*", "a*?");
437
438        roundtrip("a+", "a+");
439        roundtrip("a+?", "a+?");
440        roundtrip("(?U)a+", "a+?");
441
442        roundtrip("a{1}", "a");
443        roundtrip("a{2}", "a{2}");
444        roundtrip("a{1,}", "a+");
445        roundtrip("a{1,5}", "a{1,5}");
446        roundtrip("a{1}?", "a");
447        roundtrip("a{2}?", "a{2}");
448        roundtrip("a{1,}?", "a+?");
449        roundtrip("a{1,5}?", "a{1,5}?");
450        roundtrip("(?U)a{1}", "a");
451        roundtrip("(?U)a{2}", "a{2}");
452        roundtrip("(?U)a{1,}", "a+?");
453        roundtrip("(?U)a{1,5}", "a{1,5}?");
454
455        // Test that various zero-length repetitions always translate to an
456        // empty regex. This is more a property of HIR's smart constructors
457        // than the printer though.
458        roundtrip("a{0}", "(?:)");
459        roundtrip("(?:ab){0}", "(?:)");
460        #[cfg(feature = "unicode-gencat")]
461        {
462            roundtrip(r"\p{any}{0}", "(?:)");
463            roundtrip(r"\P{any}{0}", "(?:)");
464        }
465    }
466
467    #[test]
468    fn print_group() {
469        roundtrip("()", "((?:))");
470        roundtrip("(?P<foo>)", "(?P<foo>(?:))");
471        roundtrip("(?:)", "(?:)");
472
473        roundtrip("(a)", "(a)");
474        roundtrip("(?P<foo>a)", "(?P<foo>a)");
475        roundtrip("(?:a)", "a");
476
477        roundtrip("((((a))))", "((((a))))");
478    }
479
480    #[test]
481    fn print_alternation() {
482        roundtrip("|", "(?:(?:)|(?:))");
483        roundtrip("||", "(?:(?:)|(?:)|(?:))");
484
485        roundtrip("a|b", "[ab]");
486        roundtrip("ab|cd", "(?:(?:ab)|(?:cd))");
487        roundtrip("a|b|c", "[a-c]");
488        roundtrip("ab|cd|ef", "(?:(?:ab)|(?:cd)|(?:ef))");
489        roundtrip("foo|bar|quux", "(?:(?:foo)|(?:bar)|(?:quux))");
490    }
491
492    // This is a regression test that stresses a peculiarity of how the HIR
493    // is both constructed and printed. Namely, it is legal for a repetition
494    // to directly contain a concatenation. This particular construct isn't
495    // really possible to build from the concrete syntax directly, since you'd
496    // be forced to put the concatenation into (at least) a non-capturing
497    // group. Concurrently, the printer doesn't consider this case and just
498    // kind of naively prints the child expression and tacks on the repetition
499    // operator.
500    //
501    // As a result, if you attached '+' to a 'concat(a, b)', the printer gives
502    // you 'ab+', but clearly it really should be '(?:ab)+'.
503    //
504    // This bug isn't easy to surface because most ways of building an HIR
505    // come directly from the concrete syntax, and as mentioned above, it just
506    // isn't possible to build this kind of HIR from the concrete syntax.
507    // Nevertheless, this is definitely a bug.
508    //
509    // See: https://github.com/rust-lang/regex/issues/731
510    #[test]
511    fn regression_repetition_concat() {
512        let expr = Hir::concat(alloc::vec![
513            Hir::literal("x".as_bytes()),
514            Hir::repetition(hir::Repetition {
515                min: 1,
516                max: None,
517                greedy: true,
518                sub: Box::new(Hir::literal("ab".as_bytes())),
519            }),
520            Hir::literal("y".as_bytes()),
521        ]);
522        assert_eq!(r"(?:x(?:ab)+y)", expr.to_string());
523
524        let expr = Hir::concat(alloc::vec![
525            Hir::look(hir::Look::Start),
526            Hir::repetition(hir::Repetition {
527                min: 1,
528                max: None,
529                greedy: true,
530                sub: Box::new(Hir::concat(alloc::vec![
531                    Hir::look(hir::Look::Start),
532                    Hir::look(hir::Look::End),
533                ])),
534            }),
535            Hir::look(hir::Look::End),
536        ]);
537        assert_eq!(r"(?:\A\A\z\z)", expr.to_string());
538    }
539
540    // Just like regression_repetition_concat, but with the repetition using
541    // an alternation as a child expression instead.
542    //
543    // See: https://github.com/rust-lang/regex/issues/731
544    #[test]
545    fn regression_repetition_alternation() {
546        let expr = Hir::concat(alloc::vec![
547            Hir::literal("ab".as_bytes()),
548            Hir::repetition(hir::Repetition {
549                min: 1,
550                max: None,
551                greedy: true,
552                sub: Box::new(Hir::alternation(alloc::vec![
553                    Hir::literal("cd".as_bytes()),
554                    Hir::literal("ef".as_bytes()),
555                ])),
556            }),
557            Hir::literal("gh".as_bytes()),
558        ]);
559        assert_eq!(r"(?:(?:ab)(?:(?:cd)|(?:ef))+(?:gh))", expr.to_string());
560
561        let expr = Hir::concat(alloc::vec![
562            Hir::look(hir::Look::Start),
563            Hir::repetition(hir::Repetition {
564                min: 1,
565                max: None,
566                greedy: true,
567                sub: Box::new(Hir::alternation(alloc::vec![
568                    Hir::look(hir::Look::Start),
569                    Hir::look(hir::Look::End),
570                ])),
571            }),
572            Hir::look(hir::Look::End),
573        ]);
574        assert_eq!(r"(?:\A(?:\A|\z)\z)", expr.to_string());
575    }
576
577    // This regression test is very similar in flavor to
578    // regression_repetition_concat in that the root of the issue lies in a
579    // peculiarity of how the HIR is represented and how the printer writes it
580    // out. Like the other regression, this one is also rooted in the fact that
581    // you can't produce the peculiar HIR from the concrete syntax. Namely, you
582    // just can't have a 'concat(a, alt(b, c))' because the 'alt' will normally
583    // be in (at least) a non-capturing group. Why? Because the '|' has very
584    // low precedence (lower that concatenation), and so something like 'ab|c'
585    // is actually 'alt(ab, c)'.
586    //
587    // See: https://github.com/rust-lang/regex/issues/516
588    #[test]
589    fn regression_alternation_concat() {
590        let expr = Hir::concat(alloc::vec![
591            Hir::literal("ab".as_bytes()),
592            Hir::alternation(alloc::vec![
593                Hir::literal("mn".as_bytes()),
594                Hir::literal("xy".as_bytes()),
595            ]),
596        ]);
597        assert_eq!(r"(?:(?:ab)(?:(?:mn)|(?:xy)))", expr.to_string());
598
599        let expr = Hir::concat(alloc::vec![
600            Hir::look(hir::Look::Start),
601            Hir::alternation(alloc::vec![
602                Hir::look(hir::Look::Start),
603                Hir::look(hir::Look::End),
604            ]),
605        ]);
606        assert_eq!(r"(?:\A(?:\A|\z))", expr.to_string());
607    }
608}
regex_syntax/hir/print.rs

regex_syntax/hir/
print.rs
