How to simplify argument templating in functions that return `nom` parsers?

Question

I am writing a small parser in Rust using nom and I wanted to implement a simple function that given a delimiting &str would return a delimited parser using my delimiting &str.

After fighting the compiler for half an hour, I ended up with this monstrosity that does not even compile:

use nom::{
    branch::alt,
    bytes::complete::{escaped, tag},
    character::complete::{multispace0, one_of, satisfy, space0},
    combinator::{map, not, recognize},
    error::ParseError,
    sequence::{delimited, pair, tuple},
    AsChar, Compare, FindToken, IResult, InputIter, InputTake, InputTakeAtPosition, Parser,
};

pub fn string_literal(input: &str) -> IResult<&str, &str> {
    fn parse_delimited_string<
        'a,
        I: Clone
            + InputTake
            + Compare<&'a str>
            + nom::Slice<std::ops::RangeFrom<usize>>
            + nom::InputIter
            + nom::Offset
            + nom::InputLength
            + nom::UnspecializedInput
            + 'a,
        O,
        E: ParseError<I> + 'a,
    >(
        delimited_by: &'a str,
    ) -> impl Parser<I, I, E> + 'a
    where
        <I as InputIter>::Item: std::marker::Copy,
        <I as InputIter>::Item: AsChar,
        for<'b> &'a str: FindToken<<I as InputIter>::Item>,
    {
        delimited(
            tag(delimited_by),
            escaped(
                not(tag("\\")),
                delimited_by.as_bytes()[0] as char,
                one_of(delimited_by),
            ),
            tag(delimited_by),
        )
    }

    alt((parse_delimited_string("\'"), parse_delimited_string("\"")))(input)
}

This gives me a compiler error:

error[E0277]: the trait bound `&str: UnspecializedInput` is not satisfied
   --> src/expression.rs:102:10
    |
102 |     alt((parse_delimited_string("\'"), parse_delimited_string("\"")))(input)
    |          ^^^^^^^^^^^^^^^^^^^^^^ the trait `UnspecializedInput` is not implemented for `&str`
    |
note: required by a bound in `parse_delimited_string`
   --> src/expression.rs:79:15
    |
70  |     fn parse_delimited_string<
    |        ---------------------- required by a bound in this function
...
79  |             + nom::UnspecializedInput
    |               ^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `parse_delimited_string`

It's clear that I want to parse strings that are delimited by either ' or " - my use case is pretty simple, so at this point I will just write the two parsers by hand and not use a generating function because just look at this thing.

Is there any way I can write this concisely without exploding in the size of the template? It seems like such a simple task, but it proved to be surprisingly difficult.

Answer 1

I think you can copy the example from here, which I've pasted below. You may have to adapt it slightly to handle both single and double quotes.

//! This example shows an example of how to parse an escaped string. The
//! rules for the string are similar to JSON and rust. A string is:
//!
//! - Enclosed by double quotes
//! - Can contain any raw unescaped code point besides \ and "
//! - Matches the following escape sequences: \b, \f, \n, \r, \t, \", \\, \/
//! - Matches code points like Rust: \u{XXXX}, where XXXX can be up to 6
//!   hex characters
//! - an escape followed by whitespace consumes all whitespace between the
//!   escape and the next non-whitespace character

#![cfg(feature = "alloc")]

use nom::branch::alt;
use nom::bytes::streaming::{is_not, take_while_m_n};
use nom::character::streaming::{char, multispace1};
use nom::combinator::{map, map_opt, map_res, value, verify};
use nom::error::{FromExternalError, ParseError};
use nom::multi::fold;
use nom::sequence::{delimited, preceded};
use nom::{IResult, Parser};

// parser combinators are constructed from the bottom up:
// first we write parsers for the smallest elements (escaped characters),
// then combine them into larger parsers.

/// Parse a unicode sequence, of the form u{XXXX}, where XXXX is 1 to 6
/// hexadecimal numerals. We will combine this later with parse_escaped_char
/// to parse sequences like \u{00AC}.
fn parse_unicode<'a, E>(input: &'a str) -> IResult<&'a str, char, E>
where
  E: ParseError<&'a str> + FromExternalError<&'a str, std::num::ParseIntError>,
{
  // `take_while_m_n` parses between `m` and `n` bytes (inclusive) that match
  // a predicate. `parse_hex` here parses between 1 and 6 hexadecimal numerals.
  let parse_hex = take_while_m_n(1, 6, |c: char| c.is_ascii_hexdigit());

  // `preceded` takes a prefix parser, and if it succeeds, returns the result
  // of the body parser. In this case, it parses u{XXXX}.
  let parse_delimited_hex = preceded(
    char('u'),
    // `delimited` is like `preceded`, but it parses both a prefix and a suffix.
    // It returns the result of the middle parser. In this case, it parses
    // {XXXX}, where XXXX is 1 to 6 hex numerals, and returns XXXX
    delimited(char('{'), parse_hex, char('}')),
  );

  // `map_res` takes the result of a parser and applies a function that returns
  // a Result. In this case we take the hex bytes from parse_hex and attempt to
  // convert them to a u32.
  let parse_u32 = map_res(parse_delimited_hex, move |hex| u32::from_str_radix(hex, 16));

  // map_opt is like map_res, but it takes an Option instead of a Result. If
  // the function returns None, map_opt returns an error. In this case, because
  // not all u32 values are valid unicode code points, we have to fallibly
  // convert to char with from_u32.
  map_opt(parse_u32, std::char::from_u32).parse(input)
}

/// Parse an escaped character: \n, \t, \r, \u{00AC}, etc.
fn parse_escaped_char<'a, E>(input: &'a str) -> IResult<&'a str, char, E>
where
  E: ParseError<&'a str> + FromExternalError<&'a str, std::num::ParseIntError>,
{
  preceded(
    char('\\'),
    // `alt` tries each parser in sequence, returning the result of
    // the first successful match
    alt((
      parse_unicode,
      // The `value` parser returns a fixed value (the first argument) if its
      // parser (the second argument) succeeds. In these cases, it looks for
      // the marker characters (n, r, t, etc) and returns the matching
      // character (\n, \r, \t, etc).
      value('\n', char('n')),
      value('\r', char('r')),
      value('\t', char('t')),
      value('\u{08}', char('b')),
      value('\u{0C}', char('f')),
      value('\\', char('\\')),
      value('/', char('/')),
      value('"', char('"')),
    )),
  )
  .parse(input)
}

/// Parse a backslash, followed by any amount of whitespace. This is used later
/// to discard any escaped whitespace.
fn parse_escaped_whitespace<'a, E: ParseError<&'a str>>(
  input: &'a str,
) -> IResult<&'a str, &'a str, E> {
  preceded(char('\\'), multispace1).parse(input)
}

/// Parse a non-empty block of text that doesn't include \ or "
fn parse_literal<'a, E: ParseError<&'a str>>(input: &'a str) -> IResult<&'a str, &'a str, E> {
  // `is_not` parses a string of 0 or more characters that aren't one of the
  // given characters.
  let not_quote_slash = is_not("\"\\");

  // `verify` runs a parser, then runs a verification function on the output of
  // the parser. The verification function accepts out output only if it
  // returns true. In this case, we want to ensure that the output of is_not
  // is non-empty.
  verify(not_quote_slash, |s: &str| !s.is_empty()).parse(input)
}

/// A string fragment contains a fragment of a string being parsed: either
/// a non-empty Literal (a series of non-escaped characters), a single
/// parsed escaped character, or a block of escaped whitespace.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum StringFragment<'a> {
  Literal(&'a str),
  EscapedChar(char),
  EscapedWS,
}

/// Combine parse_literal, parse_escaped_whitespace, and parse_escaped_char
/// into a StringFragment.
fn parse_fragment<'a, E>(input: &'a str) -> IResult<&'a str, StringFragment<'a>, E>
where
  E: ParseError<&'a str> + FromExternalError<&'a str, std::num::ParseIntError>,
{
  alt((
    // The `map` combinator runs a parser, then applies a function to the output
    // of that parser.
    map(parse_literal, StringFragment::Literal),
    map(parse_escaped_char, StringFragment::EscapedChar),
    value(StringFragment::EscapedWS, parse_escaped_whitespace),
  ))
  .parse(input)
}

/// Parse a string. Use a loop of parse_fragment and push all of the fragments
/// into an output string.
fn parse_string<'a, E>(input: &'a str) -> IResult<&'a str, String, E>
where
  E: ParseError<&'a str> + FromExternalError<&'a str, std::num::ParseIntError>,
{
  // fold is the equivalent of iterator::fold. It runs a parser in a loop,
  // and for each output value, calls a folding function on each output value.
  let build_string = fold(
    0..,
    // Our parser function– parses a single string fragment
    parse_fragment,
    // Our init value, an empty string
    String::new,
    // Our folding function. For each fragment, append the fragment to the
    // string.
    |mut string, fragment| {
      match fragment {
        StringFragment::Literal(s) => string.push_str(s),
        StringFragment::EscapedChar(c) => string.push(c),
        StringFragment::EscapedWS => {}
      }
      string
    },
  );

  // Finally, parse the string. Note that, if `build_string` could accept a raw
  // " character, the closing delimiter " would never match. When using
  // `delimited` with a looping parser (like fold), be sure that the
  // loop won't accidentally match your closing delimiter!
  delimited(char('"'), build_string, char('"')).parse(input)
}

fn main() {
  let data = "\"abc\"";
  println!("EXAMPLE 1:\nParsing a simple input string: {}", data);
  let result = parse_string::<()>(data);
  assert_eq!(result, Ok(("", String::from("abc"))));
  println!("Result: {}\n\n", result.unwrap().1);

  let data = "\"tab:\\tafter tab, newline:\\nnew line, quote: \\\", emoji: \\u{1F602}, newline:\\nescaped whitespace: \\    abc\"";
  println!(
    "EXAMPLE 2:\nParsing a string with escape sequences, newline literal, and escaped whitespace:\n\n{}\n",
    data
  );
  let result = parse_string::<()>(data);
  assert_eq!(
    result,
    Ok((
      "",
      String::from("tab:\tafter tab, newline:\nnew line, quote: \", emoji: , newline:\nescaped whitespace: abc")
    ))
  );
  println!("Result:\n\n{}", result.unwrap().1);
}

Answer 2

Thanks to @ColonelThirtyTwo for the suggestion. I should have limited the input and the parser output to &str from the beginning!

I ended with this, which was much less hectic than my initial proposition.

    fn string_example(input: &str) -> IResult<&str, &str> {
        fn parse_delimited_string<'a, E: ParseError<&'a str>>(
            delimited_by: &'a str,
        ) -> impl Parser<&str, &str, E> {
            delimited(
                tag(delimited_by),
                escaped(
                    not(tag("\\")),
                    delimited_by.chars().first().unwrap(),
                    one_of(delimited_by),
                ),
                tag(delimited_by),
            )
        }

        alt((parse_delimited_string("\'"), parse_delimited_string("\"")))(input)
    }