Using Span<T> in F#: Why is this not OK?

Question

I am trying to implement a binary parser combinator library using Span. I am not sure if this is actually a good idea I just want to learn more about both.

I have already written a small binary parser a while ago using parser combinators which works perfectly.

The code looks like this:

type ByteRange =
    { Bytes : byte array
      BeginIndex : int
      EndIndex : int }

type ParserError<'err> =
    | EndOfStream
    | FormatError of 'err

type Parser<'T, 'err> = Parser of (ByteRange -> Result<'T * ByteRange, ParserError<'err>>)

let succeed value = Parser <| fun bytes -> Ok(value, bytes)
let fail error = Parser <| fun _ -> Error error

let internal fromResult result =
    Parser <| fun bytes ->
        match result with
        | Ok value -> Ok(value, bytes)
        | Error error -> Error(FormatError error)

let internal map f (Parser parse) =
    Parser <| fun byteRange ->
        match parse byteRange with
        | Ok(value', state') -> Ok(f value', state')
        | Error error -> Error error
...

I tried implemented it using Span instead of ByteRange and I just cannot do it.

Here is what I tried:

module BinaryParser

open System
open System.Runtime.CompilerServices

type ParserError<'err> =
    | EndOfStream
    | FormatError of 'err

[<Struct; IsByRefLike>]
type Success<'a> = {
    Value: 'a
    Bytes: Span<byte>
}

[<Struct; IsByRefLike>]
type ParsingResult<'a, 'err> =
| Success of success:Success<'a>
| Failure of failure:ParserError<'err>

type Parser<'T, 'err> =
    Span<byte> -> ParsingResult<'T, ParserError<'err>>

let succeed (value: 'a) =
    fun (bytes: Span<byte>) ->
        Success { Value = value; Bytes = bytes }

let fail error =
    fun _ ->
        Failure error

let internal fromResult result =
    fun bytes ->
        match result with
        | Ok value -> Success { Value = value; Bytes = bytes }
        | Error error -> Failure (FormatError error)

let internal map f (parse: Parser<_, _>) =
    fun bytes ->
        match parse bytes with
        | Success { Value = value'; Bytes = bytes' } -> Success { Value = f value'; Bytes = bytes' }
        | Failure error -> Failure error

I get following error in the map function in the line match parser bytes with: error FS0418: The byref typed value 'bytes' cannot be used at this point

What does this mean? Why can't I use Span here? Has somebody tried to implement parser combinator with Span? How would you try to solve this?

Thanks in advance.

Answer 1

This pattern (Span or other byref-like structs as a higher-order function parameter) is not supported:

let internal map f (parse: Parser<_, _>) =
    fun bytes ->
        match parse bytes with
        | Success { Value = value'; Bytes = bytes' } -> Success { Value = f value'; Bytes = bytes' }
        | Failure error -> Failure error

A simpler form:

let foo (f: Span<int> -> int) (x: Span<int>) = f x

Gives an error on f as well. There are some slight quirks with byref-like types and type abbreviations that are hiding the error on parse but you'll see it if you give it an explicit signature.

The reason is that a byref-like struct is only allocated on the stack. However, higher-order functions in F# use heap allocation. This would be a contradiction, so it's not supported.