flatMap alternatives when printing

[lukeredpath]

Currently, flatMap is not a printer parser so you can't use it if you need to print. I'm wondering what the alternative is and how you could achieve similar functionality - where the output of one parser needs to feed into the next parser in some way - using conversions.

To take a trivial example, imagine a string "key:value" - the value of key determines how we should parse value, e.g.:

foo:something_foo - the foo key would tell us that what follows the ":" needs to be parsed in a particular way.

With flat map, you could parse off the "key:" part and then switch over the value of "key", returning an appropriate parser for "value" e.g. FooParser or BarParser which parses of the remainder.

What would be the correct approach here?

[mbrandonw]

Unfortunately I don't think there is a general correct approach. It might depend heavily on use case.

In your example this could be done by parsing 3 things, the stuff before the ":", then the stuff before the "_" and then everything to the end of the line, and then use filter and map with conversions to layer on additional logic (pseudo code using a theoretical throwing splitOnce function):

let p = ParsePrint { 
  Prefix { $0 != ":" }
  ":"
  Prefix { $0 != "_" }
  "_"
  Prefix { $0 != "\n" }
}
.filter { key, value1, value2 in 
  key == value2
}
.map(.convert { key, value1, value2 in 
  (key, value1 + "_" + value2)
} unapply: { key, value
  let (value1, value2) = try value.splitOnce("_")
  return (key, value1, value2)
})

p.parse("foo:something_foo")    // ✅ ("foo", "something_foo")
p.parse("foo:something_bar")    // ❌
p.print("foo", "something_foo") // ✅ "foo:something_foo"
p.print("foo", "something_bar") // ❌

I think the real problem here is that flatMap is an incredibly general tool for performing context-sensitive parsing, and parser-printers simply cannot do general context-dependent parsing. So we are forced to do things on a case-by-case basis to see how we can recover context-sensitivity.

[gohanlon]

Prefixed-length fields simplify parsing logic and support binary strings (e.g. "5:hello"), and are a specific and somewhat common case of what Luke's describing. I recently came across them to parse the "Bulk String" format from the Redis Serialization Protocol (RESP), which looks like this:

"$11\r\nhello world\r\n"

where the "$" indicates that the record is a Bulk String, "11" is the field length of the binary-safe string, and the two "\r\n" are delimiters. I resorted to a custom ParserPrinter:

public struct RespBulkStringBody: ParserPrinter {
  public func parse(_ input: inout Substring) throws -> Substring {
    let length = try Int.parser().parse(&input)
    return try self.fixedFieldParser(length).parse(&input)
  }

  public func print(_ output: Substring, into input: inout Substring) throws {
    let length = output.lengthOfBytes(using: .utf8)

    try self.fixedFieldParser(length).print(output, into: &input)
    try Int.parser().print(length, into: &input)
  }

  private func fixedFieldParser(_ length: Int)
  -> ParsePrint<
    ParserBuilder.ZipVOV<String, Prefix<Substring>, String>
  > {
    ParsePrint {
      "\r\n"
      Prefix(length)
      "\r\n"
    }
  }
}

let respBulkString = Parse {
  "$"
  RespBulkStringBody()
}

var input = "$11\r\nhello world\r\n"
let bulkStringValue = try respBulkString.parse(input)   // → "hello world"
let printed = try respBulkString.print(bulkStringValue) // → "$11\r\nhello world\r\n"
printed == input                                        // → true

Note: For simplicity, my parser is using String values instead of a binary-safe type (like Data).

This is a relatively simple custom parser, but custom parsers feel like a fairly sharp tool that are easy to get wrong (hint: this one's probably not right!), and don't necessarily compose nicely. Of course, I'm not sure how this kind of dependency between parsers could be expressed in a general way, and even if it could, whether it'd be worth doing.

Aside: RESP might make for an interesting case study. RESP also uses a prefixed length to represent arrays of (potentially deeply nested) RESP types.

[mbrandonw]

Interesting, thanks for this example!

It seems like my ParsePrint+filter+map solution may work in this case too. You could parse one character, then some digits, then the new lines, and then everything up until the next newlines, and do filter+map to validate and massage that data how you want.

Might be worth a shot!

[gohanlon]

Almost, I think. The tricky part is that the prefixed length isn't just for validation. I can't parse until the newlines because the value of the Bulk String is a binary string — it could include newlines.

What I need to do: read one character (specifically "$" for a Bulk String), then some digits representing the length, then consume exactly length-bytes, then the final newlines.

[mbrandonw]

Very interesting. I'll have to think a bit more on it. It does feel like there is some general tool we could make to help with this, but it is alluding me right now.

[gohanlon]

A general tool would be ideal (and probably super interesting!). I also appreciate that it's not at all trivial.

Even if a general tool remained elusive, I think a specific tool for prefixed-length fields could be beneficial. Not just beneficial for parsing existing formats, either, but to also encourage the use of prefixed-length fields in new work: They're simple to parse in every language/toolset I can think of, support binary strings without onerous escaping rules, and are maximally performant to parse.

DataParser, maybe?

[JaapWijnen]

Working on a similar problem. Trying to make my XMLParser printing as well.

<tag>
  tagContent
</tag>

I currently have:

let openingTagParser = ParsePrint {
    "<".utf8
    tagHeadParser // returns tagName (String) and attributes ([String: String])
    ">".utf8
}

let containerTagParser = openingTagParser.flatMap { tagName, attributes in // this flatmap is hard to replace, since I need the tag name to search for the closing tag
    let tag = "</\(tagName)>".utf8
    Whitespace()
    PrefixUpTo(tag).pipe {
        Lazy { xmlBodyParser } // parses the content nested in this xml tag
        End()
    }.map { xml in
        return (tagName, attributes, xml) // some mappings that are easily replaceable by a conversion
    }.map {
        XML.element($0.0, $0.1, $0.2) // other mapping that's replacable by a conversion
    }
    tag
}

Any idea how to approach this? Maybe what kind of restrictions would we need on a flatMap in order for it to be reversible?

[stephencelis]

@JaapWijnen I think you can do the same as @mbrandonw's suggestion above, by capturing both values and using filter to compare them and then a custom conversion to discard the closing tag.

Here's a quick simplified sketch:

indirect enum Node {
  case element(String, [Node])
}

var tag: AnyParserPrinter<Substring, Node> {
  ParsePrint {
    "<"
    Not { "/" }
    Prefix(1...) { $0 != ">" }.map(.string)
    ">"
    Many {
      Lazy { tag }
    } terminator: {
      "</"
    }
    Prefix { $0 != ">" }.map(.string)
    ">"
  }
  .filter { open, _, close in open == close }
  .map(
    .convert(
      apply: { name, children, _ in Node.element(name, children) },
      unapply: { node in
        switch node {
        case let .element(name, children):
          return (name, children, name)
        }
      }
    )
  )
  .eraseToAnyParserPrinter()
}

[JaapWijnen]

Ah that's great thanks! Really helps. I thought this would be inefficient at first but of course it just runs through once and just fails all filter predicates before finding the right tag instead of directly looking for that specific tag.