Behavior of Many parser decumulator

[kamcma]

Hello.

I was recently working on a parser for some binary. In particular, there's a section near the beginning of the binary, eight octets, that are for encoding the whole length of the binary.

In some sample binary, I see the following, indicating the binary is 28,225 bytes long:

0x00 0x00 0x00 0x00 0x00 0x00 0x6E 0x41

So I wrote the following ParserPrinter to parse this section. I readily admit I am not an expert in bitwise math, so I relied a lot on web search to get that part implemented.

struct BytesToIntegerParser: ParserPrinter {
  var body: some ParserPrinter<ArraySlice<UInt8>, UInt64> {
    Many(8, into: 0) { (acc: inout UInt64, el: UInt8) in
      acc <<= 8
      acc |= UInt64(el)
    } decumulator: { (int: UInt64) in
      sequence(state: int) { value in
        defer { value >>= 8 }
        return UInt8(truncatingIfNeeded: value)
      }
    } element: {
      First()
    }
  }
}

The parsing test passes:

func testBytesToIntegerParser() throws {
  var input: ArraySlice<UInt8> = [
    0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x6E, 0x41
  ]
  let output = try BytesToIntegerParser().parse(&input)
  let rest = input

  XCTAssertEqual(28225, output) // ✅
  XCTAssertTrue(rest.isEmpty) // ✅
}

But the printing test fails:

func testBytesToIntegerPrinter() throws {
  let expected: ArraySlice<UInt8> = [
    0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x6E, 0x41
  ]
  let output = try BytesToIntegerParser().print(28225) // ❌
  XCTAssertEqual(expected, output)
}

In particular, the Many parser throws

round-trip expectation failed

A "Many" parser that parses at most 8 values of UInt8 was given more values than it could have parsed."

Very clear error message, and I understand what happened. I provided Many's decumulator with an infinite sequence, which it would have kept calling next() on, and printing more than the length of 8 I specified.

I guess I was just a little surprised by the behavior. In some sense, it is correct for my decumulator iterator, in a vacuum, to be infinite: it would just keep preprending the output with zeros, which is a valid way to print the number. I could imagine alternative Many behavior, in that, if a length is provided, it will only call the decumulator iterator that many times, and no more. Would that behavior be incorrect in some way? I'm not sure, but I guess it's the behavior I was expecting as I wrote the parser and before I tested it.

This is how I see to fix my parser implementation. It feels a little janky manually calling makeIterator(), since PrefixSequence does not conform to Iterator, I guess? I feel like there's probably a better way to do this.

struct BytesToIntegerParser: ParserPrinter {
  var body: some ParserPrinter<ArraySlice<UInt8>, UInt64> {
    Many(8, into: 0) { (acc: inout UInt64, el: UInt8) in
      acc <<= 8
      acc |= UInt64(el)
    } decumulator: { (int: UInt64) in
      sequence(state: int) { value in
        defer { value >>= 8 }
        return UInt8(truncatingIfNeeded: value)
      }
+      .prefix(8).makeIterator()
    } element: {
      First()
    }
  }
}

And then the printing test passes.

Anyway, I'm not necessarily asking for the Many behavior to change, I just thought it was interesting and am interested in others' thoughts. Maybe the existing behavior is necessary for some reason I don't see.

Also interested if anyone sees any ways to make my whole parser more idiomatic. Maybe the whole thing should really be a conversion, because it's not incremental?

[kamcma]

Actually, yeah, for this case, I'm coming to the conclusion this makes more sense as a conversion than a parser. Something like the following:

extension Conversions {
  struct BytesToBinaryInteger<Input: PrependableCollection, Output: BinaryInteger>: Conversion where Input.Element == UInt8 {

    func apply(_ bytes: Input) throws -> Output {
      precondition(bytes.count <= MemoryLayout<Output>.size)
      var value: Output = 0
      for byte in bytes {
        value <<= 8
        value |= Output(byte)
      }
      return value
    }
    
    func unapply(_ output: Output) throws -> Input {
      var result = Input()
      var copy = output
      for _ in 0..<MemoryLayout<Output>.size {
        result.prepend(UInt8(truncatingIfNeeded: copy))
        copy >>= 8
      }
      return result
    }
  }
}

This allows re-use across integer sizes.

Well, I think this makes my question about the Many decumulator academic almost to the point of irrelevance.

[kamcma]

Just in case anyone comes across this via search, I was able to radically simplify the above:

extension FixedWidthInteger {
  static func unsafeBytesParser() -> Parsers.UnsafeBytesIntParser<Self> {
    .init()
  }
}

extension Parsers {
  struct UnsafeBytesIntParser<Output: FixedWidthInteger>: ParserPrinter {
    var body: some ParserPrinter<ArraySlice<UInt8>, Output> {
      Prefix(MemoryLayout<Output>.size)
        .map(Conversions.UnsafeBytesToFixedWidthInteger<Output>())
    }
  }
}

extension Conversions {
  public struct UnsafeBytesToFixedWidthInteger<Output: FixedWidthInteger>: Conversion {
    public func apply(_ input: ArraySlice<UInt8>) throws -> Output {
      input.reversed().withUnsafeBytes { $0.load(as: Output.self) }
    }

    public func unapply(_ output: Output) throws -> ArraySlice<UInt8> {
      withUnsafeBytes(of: output.bigEndian, ArraySlice.init)
    }
  }
}

Which lets me do the following:

func testFixedWidthIntegerUnsafeBytesParse() throws {
  var input: ArraySlice<UInt8> = [
    0x00, 0x00, 0x6E, 0x41
  ]

  let output = try UInt32.unsafeBytesParser().parse(&input)
  XCTAssertEqual(28225, output) // ✅
}

func testFixedWidthIntegerUnsafeBytesPrint() throws {
  let expected: ArraySlice<UInt8> = [
    0x00, 0x00, 0x6E, 0x41
  ]
  let output = try UInt32.unsafeBytesParser().print(28225)
  XCTAssertEqual(expected, output) // ✅
}