using Programming;

A Blog about some of the intrinsics related to programming and how one can get the best out of various languages.

F# Gotcha: Giraffe Task "FS0708"

F# / .NET: Gotcha's

If you are a user of Giraffe with ASP.NET Core and F#, you might have come across the following error:

FS0708: This control construct may only be used if the computation expression builder defines a 'Bind' method

This happens if you try to use a let! expression inside a task computation expression:

task {
    let! x = ...Async()

The problem here is that task as a computation expression doesn't define a "Bind" method, from what I can tell. There is, however, a quick workaround:

open FSharp.Control.Tasks.V2.ContextInsensitive

For some reason, this open fixes it. I assume that it allows the async computation-expression version of the Bind to be used, so that the code above works.

There's been discussion around this, from what I can tell, but it hasn't really resolved this issue, not sure if it's a version thing, or entirely unrelated: Q: remove async await bind from task {}?.

The Giraffe folks do a great job, so I want to make sure you can work around this particular issue if and when you encounter it.

F# / .NET: "Gotcha's"

Recently I've been digging more-and-more into F#, so I want to start putting together a list of things that I occasionally (or regularly) run into that new users of the language (or even those who are substantially experienced) might not have a great time with.

I'll be notating if it's a general .NET "gotcha", or an F#-specific "gotcha."

F#:

.NET:

If you have something you want to see in the list, please let me know either via Twitter or as a comment. I'll try to check back here regularly to keep this list as up-to-date as possible.

Importing F# to the SQLCLR (T-SQL)

Bringing F# into the SQLCLR

It's been some-time since my last post, and don't worry, we're still going to continue the IMAP server. I've been swamped at work, and as a result, haven't had the time to properly dedicate to writing these posts (especially that series, which is a complex topic).

Excuses aside, today we're going to talk about something I recently did for work, which is integrating F# into the SQLCLR (part of Microsoft SQL Server).

For those who don't know, the SQLCLR is a feature of SQL Server that allows one to import .NET assemblies as user-defined functions, or stored procedures. On it's own it doesn't sound impressive, but the SQLCLR allows us to significantly improve performance in some cases, and moderately improve it in others.

I won't go into detail explaining the SQLCLR, a gentleman by the name of Soloman Rutzky does that quite well. I'll let his "Stairway to SQLCLR" give you the introduction.

No, what I'll do today is show you how to import F# into the SQLCLR, instead of just C# or VB.NET. The process is about as straightforward as Soloman describes, but there are a few "gotcha's", so I'm going to include those in our discussion here today.

Without further ado, let's get started.

First: create the project and add the System.Data reference

The first step is obviously to create a project to hold our SQL code. The project should be an F# Class Library, in .NET Framework (I'm using 4.7.1 and F# Core 4.4.3.0). You'll want a module for the functions, and in that module you'll want to open Microsoft.SqlServer.Server, and System.Data.SqlTypes.

Once we've done that, we'll build a function. There are a few rules to creating a function in .NET that can be seen by SQL Server:

  1. The function must have the SqlFunction attribute;
  2. All inputs must be tupled;
  3. All input and output types must be a Sql[Something] type (SqlDouble, SqlInt, etc.);

So, for our example we're going to use a real-world example from my work: distance calculation from two geo-coded points.

To do this, we'll build a function that takes 4 double values: two Latitude/Longitude value sets.

let calculateDistance (fromLat : SqlDouble, fromLon : SqlDouble, toLat : SqlDouble, toLon : SqlDouble) : SqlDouble

That's the signature we'll use, next, we want to define how SQL should treat the function:

[<SqlFunction(
    IsDeterministic = true,
    IsPrecise = false,
    SystemDataAccess = SystemDataAccessKind.None,
    DataAccess = DataAccessKind.None)>]

This is where life gets special, so let me explain them piece-by-piece:

  • SqlFunction: this is just the attribute we use, there is also SqlProcedure for stored procedures;
  • IsDeterministic = true: this value should ONLY be set to true if the function is deterministic, that is, given any input value, it returns one and exactly one output, and that two calls to the function with the same input will result in the same output;
  • IsPrecise = false: this value should ONLY be set to true if the function uses the DECIMAL or NUMERIC types, and does precise mathematical calculations;
  • SystemDataAccess = SystemDataAccessKind.None: I'll be completely honest with you, I don't know what the difference between this and DataAccess are, but if you do any reading/writing to/from SQL, you should set it to Read, otherwise, probably use None (there's a small performance cost to setting this to Read, I leave it to you to decide whether or not to do so);
  • DataAccess = DataAccessKind.None: see above;

So basically, what we did here is define a function and tell SQL what it should expect the function to do. One of the most impotant parts is the IsDeterministic flag: this tells SQL that if it called the function for a set of values, it can reuse that result for any subsequent calls with the same set of values. This means it can memoize the results. If your function has side-effects, do not set this flag to true, or you will get weird results. Basically, if your function is truly "pure" (no side-effects), mark it with IsDeterministic = true.

Next: write the code

Alright, so we've covered the hard parts, next, we write the function.

My version of this function used some logic that was specific to my workplace, so I'm going to remove it and we'll write a vanilla function:

let constMod = 1.852 / 1.61 * 60.
let divPi180 = Math.PI / 180.
let div180Pi = 180. / Math.PI

[<SqlFunction(
    IsDeterministic = true,
    IsPrecise = false,
    SystemDataAccess = SystemDataAccessKind.None,
    DataAccess = DataAccessKind.None)>]
let calculateDistance (fromLat : SqlDouble, fromLon : SqlDouble, toLat : SqlDouble, toLon : SqlDouble) : SqlDouble =
    let fromLat = fromLat.Value
    let fromLon = fromLon.Value
    let toLat = toLat.Value
    let toLon = toLon.Value

    let fromLat = fromLat * divPi180
    let toLat = toLat * divPi180
    let fromLon = fromLon * divPi180
    let toLon = toLon * divPi180

    constMod *
    (Math.Acos
        ((Math.Sin toLon) * (Math.Sin fromLon) +
         (Math.Cos toLon) * (Math.Cos fromLon) * (Math.Cos (toLat - fromLat))))
    |> SqlDouble

This should be self-explanatory: we basically convert the data and do some simple math on it.

Third: enable SQLCLR

Alright, so that's that entirety of our .NET code.

Now, we need to enable the SQLCLR, because it's disabled by default.

The SQLCLR can be enabled through GUI or T-SQL, I prefer to do it through GUI because I typo a lot.

To enable it:

  1. Right click your server in SSMS;
  2. Click "Facets";
  3. In the "Facet" dropdown select "Surface Area Configuration";
  4. Change "ClrIntegrationEnabled" to "True";
  5. Click "OK";

Easy enough.

Fourth: trust the assembly, and import it

This is one spot where things aren't completely awesome: the FSharp.Core library isn't built to natively support a "SAFE" import to SQLCLR, so we have to trust it first.

To trust the assemblies, we'll want to get a SHA2_512 hash of them, and optionally, a description.

I, personally, don't care so much about the description at the moment, so I'll leave that out and let you locate it if you like. Instead, I'm just going to demonstrate how to hash it and trust it.

We need to trust FSharp.Core, and then our assembly:

DECLARE @hash AS BINARY(64) = (SELECT HASHBYTES('SHA2_512', (SELECT * FROM OPENROWSET (BULK 'C:\path\to\bin\dir\FSharp.Core.dll', SINGLE_BLOB) AS [Data])))
EXEC sp_add_trusted_assembly @hash

Then, our assembly:

DECLARE @hash AS BINARY(64) = (SELECT HASHBYTES('SHA2_512', (SELECT * FROM OPENROWSET (BULK 'C:\path\to\bin\dir\MyAssembly.dll', SINGLE_BLOB) AS [Data])))
EXEC sp_add_trusted_assembly @hash

Easy enough.

Because FSharp.Core isn't built for native SQL Server support (which, if anyone want's to fix, I've included the error at the end of this article), we have to add it with PERMISSION_SET = UNSAFE, which is, well...unsafe.

So, to load our assembly, we need a name, and the path:

CREATE ASSEMBLY [MyAssembly]
AUTHORIZATION dbo
FROM 'C:\path\to\bin\dir\MyAssembly.dll'
WITH PERMISSION_SET = SAFE

Not particularly hard. The name ([MyAssembly]) is not restricted to anything other than the regular NVARCHAR(128) for sysname, it does not need to match anything from the DLL, but probably easier if it does.

Finally: create the function

Alright, so our assembly is imported, we have it available, the last part is creating the function.

To create the function, we start it off like a normal T-SQL UDF:

CREATE FUNCTION CalculateDistance
(
    @fromLat FLOAT,
    @fromLon FLOAT,
    @toLat FLOAT,
    @toLon FLOAT
)
RETURNS FLOAT

If you've ever written a T-SQL Scalar-Valued UDF, this should look familiar. We build the signature exactly as we defined it in F#, and that part is super important: the signature cannot vary at all.

Next, we write the UDF:

AS EXTERNAL NAME [MyAssembly].[MyAssembly.Namespace.ModuleName].calculateDistance

The EXTERNAL NAME is a three part name:

  1. The assembly name as specified in CREATE ASSEMBLY;
  2. The assembly namespace and module name, the fully-qualified name of the first outer-container of the function we need;
  3. The function name itself;

Once you've created the function, we're literally all done. You can now call directly into your CLR code:

SELECT dbo.CalculateDistance(@fromLat, @fromLon, @toLat, @toLon)

Demonstrations!

For those who want to see the performance difference, the original T-SQL function is:

CREATE FUNCTION CalculateDistanceUdf
(
    @fromLat FLOAT,
    @fromLon FLOAT,
    @toLat FLOAT,
    @toLon FLOAT
)
RETURNS FLOAT
WITH SCHEMABINDING
AS 
BEGIN
    RETURN (1.852 / 1.61) *
        60 *
        DEGREES(
            ACOS(
                SIN(RADIANS(@toLon)) *
                SIN(RADIANS(@fromLon)) +
                COS(RADIANS(@toLon)) *
                COS(RADIANS(@fromLon)) *
                COS(RADIANS(@toLat) - RADIANS(@fromLat))))
END

The WITH SCHEMABINDING is a hint to try to tell SQL Server to mark the function deterministic, and it is as verified with SELECT OBJECTPROPERTY(OBJECT_ID('[dbo].[CalculateDistanceUdf]'), 'IsDeterministic'), but it still performs significantly slower than the SQLCLR alternative.

I borrowed the test from this article to run mine, and wrote them as follows:

CREATE TABLE Numbers (
    Num INT NOT NULL,
    CONSTRAINT PK_Numbers PRIMARY KEY CLUSTERED (Num)
)
GO

WITH N1(C) AS (SELECT 0 UNION ALL SELECT 0),
N2(C) AS (SELECT 0 FROM N1 AS T1 CROSS JOIN N1 AS T2),
N3(C) AS (SELECT 0 FROM N2 AS T1 CROSS JOIN N2 AS T2),
N4(C) AS (SELECT 0 FROM N3 AS T1 CROSS JOIN N3 AS T2),
N5(C) AS (SELECT 0 FROM N4 AS T1 CROSS JOIN N4 AS T2),
N6(C) AS (SELECT 0 FROM N4 AS T1 CROSS JOIN N4 AS T2 CROSS JOIN N3 AS T3),
Nums(Num) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM N6)
INSERT INTO Numbers(Num) SELECT Num FROM Nums
GO

This inserts 1048576 rows to the Numbers table, so it's a good-sized test.

Then we can run each of the following three tests:

DECLARE @fromLat AS FLOAT = 100
DECLARE @fromLon AS FLOAT = 100
DECLARE @toLat AS FLOAT = 120
DECLARE @toLon AS FLOAT = 120

SELECT MAX(dbo.CalculateDistance(Num / @fromLat, Num / @fromLon, Num / @toLat, Num / @toLon)) FROM Numbers
GO

DECLARE @fromLat AS FLOAT = 100
DECLARE @fromLon AS FLOAT = 100
DECLARE @toLat AS FLOAT = 120
DECLARE @toLon AS FLOAT = 120

SELECT MAX(dbo.CalculateDistanceUdf(Num / @fromLat, Num / @fromLon, Num / @toLat, Num / @toLon)) FROM Numbers
GO

DECLARE @fromLat AS FLOAT = 100
DECLARE @fromLon AS FLOAT = 100
DECLARE @toLat AS FLOAT = 120
DECLARE @toLon AS FLOAT = 120

SELECT MAX
    (
        (1.852 / 1.61) *
        60 *
        DEGREES(
            ACOS(
                SIN(RADIANS(Num / @toLon)) *
                SIN(RADIANS(Num / @fromLon)) +
                COS(RADIANS(Num / @toLon)) *
                COS(RADIANS(Num / @fromLon)) *
                COS(RADIANS(Num / @toLat) - RADIANS(Num / @fromLat)))))
FROM Numbers
GO

You can run these each individually to time them. My times were roughly 645ms for the SQLCLR, 3369ms for the T-SQL UDF, and 703ms for the inline T-SQL. As you can see, the SQLCLR function is faster than the inline T-SQL, and let's us encapsulate the logic in a single function. (This actually came about as an issue because we have the calculation there copied-and-pasted over several dozen queries, often 3-8x per query.)

So, that said, in this type of situation (raw math) there's no reason to use T-SQL for the task, and for something reasonably complex like this, no reason not to abstract it. Dump the code in .NET, write your unit tests, and then deploy the assembly to the SQL server.

Now, that said, there are times I wouldn't use a SQLCLR function, such as when the math is ultra simple: i.e. * 3, and there are times when a table-valued UDF would be far superior, so I don't want to make the suggestion that this will always help, just that it's another thing you can try, and it might actually surprise you.


For anyone curious, attempting to create an assembly in F# throws the following warning:

Warning: The Microsoft .NET Framework assembly 'fsharp.core, version=4.4.3.0, culture=neutral, publickeytoken=b03f5f7f11d50a3a, processorarchitecture=msil.' you are registering is not fully tested in the SQL Server hosted environment and is not supported. In the future, if you upgrade or service this assembly or the .NET Framework, your CLR integration routine may stop working. Please refer SQL Server Books Online for more details.

And using a PERMISSION_SET of EXTERNAL_ACCESS or SAFE throws the following error:

CREATE ASSEMBLY failed because type 'Microsoft.FSharp.Collections.FSharpMap`2' in safe assembly 'FSharp.Core' has a static field 'empty'. Attributes of static fields in safe assemblies must be marked readonly in Visual C#, ReadOnly in Visual Basic, or initonly in Visual C++ and intermediate language.

Constructing an IMAP Server from Scratch - Part 2

Implementing Server-Side RFC 3501 (IMAP) in F# (Part 2)

Previous: Implementing Server-Side RFC 3501 (IMAP) in F# (Part 1)

Alright, so the previous blog post got us introducded to our RFC 3501 (IMAP) implementation. We looked at the basic TCP/IP stack of the architecture. Today, we're going to actually start building part of the IMAP server itself.

To start building the IMAP server, we need to start building a mock file-system. Now me, personally, I'm about keeping things as simple as possible. As a result, the mock file-server I'm building is not going to do anything fancy. We'll use a DemoFiles folder in the IMAP server for all the data, then within that folder we'll have a Configuration file, then a Message_{Id} file for each message. The Configuration file will have some basic stuff:

  • Password: to verify the user against on authentication;
  • UIDVALIDITY: that value that RFC 3501 says can never change;
  • NextUniqueIdentifier: the value that RFC 3501 dictates must change only when a message is received;

Next, each Message_{Id} file needs to have a few of it's own pieces:

  • Attributes: at least all of the following attributes:
    • \Seen
    • \Answered
    • \Flagged
    • \Deleted
    • \Draft
  • Date/Time Received: the date and time that the message was received by the server (typically via SMTP);
  • Message Size: the number of 8-bit octets in the message;
  • Envelope Structure: the parsed header of the message;
  • Body Structure: the parsed body (MIME-IME) of the message;
  • Message Text: the text(s) in the message;

We'll worry about messages later, for now I just want to concern ourselves with the configuration, as that's the first part of implementing IMAP.

Building a Configuration File

Now we have several methods for building the configuration file: XML, JSON, INI, CSV, etc. Because I'm lazy, and because this is a sample storage system, I'm going to build it as a line-delimited file. I.e.: each line is a value in the config. (Easy to write by hand, easy to ready by hand, easy to parse with code, all-in-all, pretty easy.)

Our config file will look like:

Plaintext Password (For easy troubleshooting)
The UIDVALIDITY value (Constant)
The Next Unique Identifier value (Changes when a message comes in)

My sample configuration:

Password123
307110933
1

Building Storage Events

Using this basic configuration, we can start to modify our server to take note of file read/write. We can start modifying the IMAP server to start using some storage events.

type StorageEvents =
    { Authenticate : string * string -> User option
      GetUidValidity : User -> int
      GetNextUniqueId : User -> int }

So we can start developing some basic events here. We want to be able to tell if a user can be authenticated (take a username and password and output a Some User if it's valid, or None if not). We want to get the UIDVALIDITY value (take a User and return an int), and we want to get the next unique ID (take a User and output an int).

Now we don't really take commands from the server yet, but we can shoehorn a test or two in:

let objectToStr o = o.ToString()
let rec runClient (socket : Socket) =
    let printfn = printfn "Socket %s: %s" (socket.RemoteEndPoint.ToString())
    let user = Some { Id = "ebrown@example.com" }
    async {
        let! buffer = () |> socket.AsyncReceiveAll
        let str = buffer |> Encoding.ASCII.GetString
        sprintf "Received (%i bytes): %s" buffer.Length str |> printfn
        if str.Length = 3 && str = "BYE" then printfn "Disconnected"
        else
            let! bytesSent = [| "Hello, other world!"B |> Some; user |> Option.map (storageEvents.GetUidValidity >> objectToStr >> Seq.map byte >> Seq.toArray) |] |> Array.choose id |> Array.concat |> socket.AsyncSend
            bytesSent |> sprintf "Sent response (%i bytes)" |> printfn
            return! socket |> runClient }

We'll send back the UIDVALIDITY value every time we get a packet from a client, that should be a good proof-of-concept.

Our server itself needs to change (ever-so-slightly): type Server (storageEvents) =, this will allow us to pass the storageEvents in, and the server has no idea what or how the underlying storage mechanism works (nor does it care).

Defining the entire storage system to work is really, really trivial:

type Configuration =
    { Password : string
      UidValididty : int
      NextUniqueId : int }
let getConfig (f : string) =
    let lines = System.IO.Path.Combine(@"DemoFiles", f, @"Configuration.txt") |> System.IO.File.ReadAllLines
    { Password = lines.[0]; UidValididty = lines.[1] |> int; NextUniqueId = lines.[2] |> int }
let serverEvents = 
    { Authenticate = (fun (u, p) -> if (u |> getConfig).Password = p then Some { Id = u } else None)
      GetUidValidity = (fun u -> (u.Id |> getConfig).UidValididty)
      GetNextUniqueId = (fun u -> (u.Id |> getConfig).NextUniqueId) }

We defined a Configuration type, a function to parse it, and then created a serverEvents object to hold all the functions for working with the storage system. Our main function changes little:

use server = Server(serverEvents).Start()
Console.ReadLine() |> ignore
printfn "Closing..."
0

We just put serverEvents in now.

If we put it all together to start testing it, we'll get Received 28 bytes: Hello, other world!307110933 on the client, which proves that our storage works.

We can push this off to a Storage module, to get it out of our work-area:

module EBrown.Imap.Server.Storage
open EBrown.Imap.Core

type Configuration =
    { Password : string
      UidValididty : int
      NextUniqueId : int }
let getConfig (f : string) =
    let lines = System.IO.Path.Combine(@"DemoFiles", f, @"Configuration.txt") |> System.IO.File.ReadAllLines
    { Password = lines.[0]; UidValididty = lines.[1] |> int; NextUniqueId = lines.[2] |> int }
let getStorageEvents () = 
    { Authenticate = (fun (u, p) -> if (u |> getConfig).Password = p then Some { Id = u } else None)
      GetUidValidity = (fun u -> (u.Id |> getConfig).UidValididty)
      GetNextUniqueId = (fun u -> (u.Id |> getConfig).NextUniqueId) }

Implementing IMAP Commands

Alright, so now that we have a storage mechanism, we want to start implementing some IMAP commands and state and such.

IMAP commands are either tagged or untagged, and comprise of a command name, and possibly arguments. Thus a command would look like <TAG> <COMMANDNAME> <ARGUMENTS>, where <TAG> is either a client-generated string, or a * if the command is untagged. There are a few, basic commands, that can be implemented regardless of the state of the IMAP connection:

  • CAPABILITY: the capability command is tagged and has no arguments. The response should be one untagged response with a list of what capabilities are currently supported by the server, and the server should send one tagged OK response (or a tagged BAD response if the command is badly formed).
  • NOOP: the noop command is tagged and has no arguments. There is no specific response, but it can be used as a polling command as any command can return a status update. The server should send one tagged OK (or BAD) response after sending status update data, if appropriate.
  • LOGOUT: the logout command is tagged and has no arguments. The response should be one untagged BYE, and one OK or BAD.

The format of an OK response to a command is <TAG> OK <COMMANDNAME> completed.

Thus, if a client sends a a002 NOOP, the server OK response would be a002 OK NOOP completed.

With all this in mind, we can start building a command parser and generator.

The first part we need is a Tag. This is honestly quite trivial:

type Tag = | Untagged | Tagged of string
let getTag = function | Untagged -> "*" | Tagged s -> s

As commands are either tagged or untagged, this makes life really easy.

Next, we need a general generateLine, which can be used to generate any given command or response:

let joinStrings (sep : string) (sarr : string array) = System.String.Join(sep, sarr)
let generateLine tag largs name rargs =
    [|[|tag |> getTag |> Some|]; largs; [|name |> Some|]; rargs|]
    |> Array.concat
    |> Array.choose id
    |> joinStrings " "

We generalize this enough so that we can use it for any command, which makes life extremely trivial to build a generateCommand:

let generateCommand tag name args = generateLine (Tagged tag) [||] name (args |> Array.map Some)

Now we can generalize command generation, let's build a capability command:

let capability tag = generateCommand tag "CAPABILITY" [||]
let capabilityResponse tag args = [|generateLine Untagged [||] "CAPABILITY" (args |> Array.map Some); generateLine (Tagged tag) [|"OK" |> Some|] "CAPABILITY" [|"completed" |> Some|]|]

Again, we're keeping it mostly simple.

The next step is to parse a command. This will be just as easy as generation, we'll define new types and a function to handle the input.

type Command = | Capability
type InputCommand = { Tag : Tag; Command : Command }
let parseCommand (command : string) =
    let parseTag = function | "*" -> Untagged | s -> Tagged s
    let parseCommandName =
        function
        | [|"CAPABILITY"|] -> Capability |> Some
        | _ -> None
    let parts = command.Split(' ')
    parts.[1..] |> parseCommandName |> Option.map (fun c -> { Tag = parts.[0] |> parseTag; Command = c })

Again, quite simple. We parse the tag out, then we parse the command out, and return the result.

So with this, extending to add a NOOP command is really easy:

type Command = | Capability | Noop
....
let noop tag = generateCommand tag "NOOP" [||]
let noopResponse tag = [|generateLine (Tagged tag) [||] "NOOP" [|"completed" |> Some|]|]
....
let parseCommand (command : string) =
    let parseTag = function | "*" -> Untagged | s -> Tagged s
    let parseCommandName =
        function
        | [|"CAPABILITY"|] -> Capability |> Some
        | [|"NOOP"|] -> Noop |> Some
        | _ -> None
    let parts = command.Split(' ')
    parts.[1..] |> parseCommandName |> Option.map (fun c -> { Tag = parts.[0] |> parseTag; Command = c })

And now we have NOOP support.

Lastly, LOGOUT command support:

let logout tag = generateCommand tag "LOGOUT" [||]
let logoutResponse tag = [|generateLine Untagged [||] "BYE" ([|"IMAP4rev1"; "Server"; "logging"; "out"|] |> Array.map Some); generateLine (Tagged tag) [||] "LOGOUT" [|"completed" |> Some|]|]
let parseCommand (command : string) =
    let parseTag = function | "*" -> Untagged | s -> Tagged s
    let parseCommandName =
        function
        | [|"CAPABILITY"|] -> Capability |> Some
        | [|"NOOP"|] -> Noop |> Some
        | [|"LOGOUT"|] -> Logout |> Some
        | _ -> None
    let parts = command.Split(' ')
    parts.[1..] |> parseCommandName |> Option.map (fun c -> { Tag = parts.[0] |> parseTag; Command = c })

Now as we work with this, we should realize that we can actually remove most of the specific functions, and use the InputCommand for the capability, noop, and logout functions we built:

type ClientCommandName = | Capability | Noop | Logout
type ClientCommand = { Tag : Tag; Command : ClientCommandName }
let generateClientCommandName =
    function
    | Capability -> ("CAPABILITY", [||])
    | Noop -> ("NOOP", [||])
    | Logout -> ("LOGOUT", [||])
let generateClientCommand (command : ClientCommand) = command.Command |> generateClientCommandName ||> generateLine command.Tag [||]
let parseClientCommand (command : string) =
    let parseTag = function | "*" -> Untagged | s -> Tagged s
    let parseCommandName =
        function
        | [|"CAPABILITY"|] -> Capability |> Some
        | [|"NOOP"|] -> Noop |> Some
        | [|"LOGOUT"|] -> Logout |> Some
        | _ -> None
    let parts = command.Split(' ')
    parts.[1..] |> parseCommandName |> Option.map (fun c -> { ClientCommand.Tag = parts.[0] |> parseTag; Command = c })

type OkBadResult = | Ok | Bad
let getOkBad = function | Ok -> ("OK", "completed") | Bad -> ("BAD", "")
type ServerCommandName = | Capability of OkBadResult * string array | Noop of OkBadResult | Logout of OkBadResult
type ServerCommand = { Tag : Tag; Command : ServerCommandName }
let generateServerCommandName (command : ServerCommand) =
    match command.Command with 
    | Capability (res, options) ->
        let lRes, rRes = res |> getOkBad
        [|(Untagged, [||], "CAPABILITY", options); (command.Tag, [|lRes|], "CAPABILITY", [|rRes|])|]
    | Noop res ->
        let lRes, rRes = res |> getOkBad
        [|command.Tag, [|lRes|], "NOOP", [|rRes|]|]
    | Logout res ->
        let lRes, rRes = res |> getOkBad
        [|(Untagged, [||], "BYE", [|"IMAP4rev1 Server logging out"|]); command.Tag, [|lRes|], "LOGOUT", [|rRes|]|]
let generateServerCommand (command : ServerCommand) = command |> generateServerCommandName |> Array.map (fun (t, l, n, r) -> generateLine t (l |> Array.map Some) n (r |> Array.map Some))

So now we have a manner of building commands, somewhat dynamically. We can construct a command from what it needs, which means we can continue on with the next step: authentication / authorization. That will be the subject of the next blog post, as I want to allow a lot of this to sink in, so that we can hit the ground running in the next situation. We have a whole hell-of-a-lot to do yet, so we'll take it in shorter, more manageable bits.


As a reminder, the code for this is on GitHub. The version for this specific blog post is tree 8d7b3f15777d0be7cd78903bb5f0c94d8175230d.


Due to time constraints, I didn't make it as far as I would have liked with this post. But never fear, consistent, slow progress is better than inconsistent progress.

Constructing an IMAP Server from Scratch - Part 1

Implementing Server-Side RFC 3501 (IMAP) in F# (Part 1)

So it's been a while, I've had little free time over the last couple months (December through February are my extrememly busy period), but I want to start a new project today, inspired by a complete failure of my existing mail provider to work properly.

Start with RTFM (or RFC's, in this case)

Now IMAP, as a protocol, is extraordinarily complicated. It is primarily detailed by RFC 3501, but many other RFC's have come in over the years to update it. As a result, we have 23 RFC's that relate to IMAP directly, and several more indirectly. I'm going to list the most important ones (in numeric order) first, then the extraneious ones.

Primarily, we have 18 RFC's to work with: 1730, 2060, 2061, 2088, 2342, 3501, 3502, 3516, 4466, 4469, 4551, 5032, 5182, 5738, 6237, 6855, 7162, and 7377.

We also have 5 additional RFC's for MIME that are extremely important: 2045. 2046, 2047, 2048, and 2049.

Additionally, there are 7 other RFC's that are directly relevant, though we can ignore for now: 2595, 5068, 5550, 6186, 6858, 7817, and 8314.

Finally, we have 6 other RFC's we'll need to think about: 2822, 5322, 5335, 5336, 6531, and 6854.


I don't expect you to read all of these, but you should know where to find them. We'll actually deal with most of the 36 RFC's detailed here tangentially, and I won't go into much detail on what parts of which RFC's we've implemented. (Though I haven't decided on that, yet.) The RFC rabbit-hole on IMAP is deep, and as a result we will need to be aware of issues we might run into that aren't detailed here. (We may discover new RFC's pertaining to what we're doing, for example.)

What is IMAP?

So let's back our complicated story up a little bit. First, let's talk about what is and isn't IMAP.

IMAP is the Internet Message Access Protocol, a protocol designed to allow a client (such as Outlook, Thunderbird, etc.) to retreive and update Internet Messages (Email's) associated with an account. This means you specify the account and credentials, the client uses those to perform IMAP interactions, and then displays those results to you.

This protocol does not specify how or where those messages must be stored (server or client side), nor how one can send messages to another Email box (which is typically SMTP / relays), it only specifies how a client system should access, modify, and remove Emails that it owns.

The short and simple: this means we can build a generic IMAP access protocol, which can then be used to interact with another service (or .NET library) for storage of the physical message.

Getting Started: Understanding Requirements

We'll begin our adventure down this IMAP server path by reading some of the RFC information. Fortunately, we won't read all of it, but we do have quite a bit of information to digest.

One of the more basic requirements we'll want to facilitate with our design is the transport-layer protocol and port, which happens to be TCP Port 143. This is found in RFC 3501 §2.1.

Another interesting note is the definition of a command / line, in RFC 3501 §2.2. By definition, a line ends in CRLF, and data is either a line, or a known length of octets (8-bit bytes) followed by a line.

Further in this same section, we are told that transferring data from Server to Client can happen on request, or be initiated by the server. We also learn that a client should generate an alpha-numeric "tag" which indicates which command the server is responding to. (There is no fixed syntax for a tag, just that it may only be alpha-numeric.)

Further reading tells us that there are a couple other items and states we'll need to keep. Particularly:

  • For each mailbox we must have a UIDVALIDITY value that is unique to that mailbox;
  • For each message, we must have a UID value that is unique to that message;

The combination of the mailbox name, UIDVALIDITY, and UID must describe a single message in the mail server. Each of these values is a 32-bit integer.


While there are many, many more requirements, I have set a goal to write code in every blog-post in this new series. As a result, I want to dive into writing, at the very least, a single-threading server for clients to connect to.

There are many examples out there of doing OpenSendReceiveClose, but that's not what we want. With IMAP, we need to do an OpenLoop (SendReceive) → Close. This obviously complicates things, especially once we get into mutliple concurrent connections.

So, to start this, we're going to build a demo client/server to get our infrastructure together. We're going to build one that allows us to send messages to the server, and pipe other messages back to the client. (Similar to a chat, but without message sharing.) This will allow us to build and demonstrate all the pieces of the IMAP infrastructure. (Many concurrent, connected clients, etc.) We're going to use F# Async-Computations to do so, which are actually really fun.

Let's start building a server!

Raw TCP/IP is a very difficult task to set out to implement without an understanding of how TCP/IP works. I'm not going to go into any of that detail, as I want to get right into writing some code, but the basics are that a TCP/IP connection is a "Socket", the socket is opened, and remains open until closed by the client or server. TCP/IP sockets are also bidirectional, meaning that at any given point the client and the server both reserve the right to unilaterally send data or close the connection.

We'll start with the TCP Server. This is an easy enough build, and can be abstracted to a pretty simple API. But before we do that, I want to make a few extensions to .NET.

Boilerplate

One of the pain-points (for me) with .NET is that there is no way to read an entire response from a raw TCP socket. For some reason (probably a good one), the designers left that part out. As a result, I always write some modifications to System.Net.Sockets.NetworkStream and System.Net.Sockets.Socket to make them more friendly:

module EBrown.Tcp.NetworkStream
open System.Net.Sockets

/// Add definitions to the `System.Net.Sockets.NetworkStream`
type NetworkStream with
    member stream.AsyncReceive (buffer : byte array, ?offset, ?count) =
        Async.FromBeginEnd(
            buffer, 
            defaultArg offset 0, 
            defaultArg count buffer.Length, 
            stream.BeginRead, 
            stream.EndRead)
    member stream.AsyncReceiveAll () =
        let rec receive buffer =
            async {
                let tempBuffer = 1024 |> Array.zeroCreate
                let! bytesReceived = tempBuffer |> stream.AsyncReceive
                let buffer = [|buffer; tempBuffer.[0..bytesReceived - 1]|] |> Array.concat
                if bytesReceived < tempBuffer.Length then return buffer else return! buffer |> receive }
        [||] |> receive
    member stream.ReadAll () =
        let rec receive buffer =
            let tempBuffer = 1024 |> Array.zeroCreate
            let bytes = (tempBuffer, 0, tempBuffer.Length) |> stream.Read
            let buffer = [|buffer; tempBuffer.[0..bytes - 1]|] |> Array.concat
            if bytes < tempBuffer.Length then buffer else buffer |> receive
        [||] |> receive
    member stream.Write (buffer : byte array) = stream.Write(buffer, 0, buffer.Length)

The first thing you see is AsyncRead, which performs an asynchronous call to BeginRead and EndRead, to do the entire thing in one go. This seems to be the most preferred way of doing .NET async operations at this level. The next line starts some interesting syntax: we define an AsyncReadAll function which will do an AsyncRead call until it has no more data. You might not have seen async { ... } before, or let! or return!, but they're F# Asynchronous Computation Expressions. I won't go into detail (because I don't really understand how they work, just how to use them) but we'll use them all over the place here.

The basics you need to know are that in an async block, you can make calls to other async code, and bind that. The let! (let bang) keyword will call to an async function, and bind the result, ONCE the result is ready. If the result isn't ready, then this function execution is paused and the thread is used elsewhere. The return! (return bang) will return the result of the async expression, after it's ready.

This is important to know because the following two lines are not the same:

let bytesReceived = tempBuffer |> stream.AsyncReceive
let! bytesReceived = tempBuffer |> stream.AsyncReceive

The first line binds an Async<int> to bytesReceived, whereas the second binds an int to bytesReceived. The first value is just a function call, that has not yet been started. The second calls the function and then yields the thread until the result is ready.

You then see that the NetworkStream has a ReadAll, which does a Read until no more data, and a Write, which does a stream.Write with a buffer.

Next we want to extend Socket to make life easier:

module EBrown.Tcp.Socket
open System.Net.Sockets

/// Add definitions to the `System.Net.Sockets.Socket`
type Socket with
    member socket.AsyncAccept () = Async.FromBeginEnd(socket.BeginAccept, socket.EndAccept)
    member socket.AsyncReceive (buffer : byte array, ?offset, ?count) =
        Async.FromBeginEnd(
            buffer, 
            defaultArg offset 0, 
            defaultArg count buffer.Length, 
            (fun (buffer, offset, size, callback, state) -> socket.BeginReceive(buffer, offset, size, SocketFlags.None, callback, state)), 
            socket.EndReceive)
    member socket.AsyncSend (buffer : byte array, ?offset, ?count) =
        Async.FromBeginEnd(
            buffer,
            defaultArg offset 0,
            defaultArg count buffer.Length,
            (fun (buffer, offset, size, callback, state) -> socket.BeginSend(buffer, offset, size, SocketFlags.None, callback, state)),
            socket.EndSend)
    member socket.AsyncReceiveAll () =
        let rec receive buffer =
            async {
                let tempBuffer = 1024 |> Array.zeroCreate
                let! bytesReceived = tempBuffer |> socket.AsyncReceive
                let buffer = [|buffer; tempBuffer.[0..bytesReceived - 1]|] |> Array.concat
                if bytesReceived < tempBuffer.Length then return buffer else return! buffer |> receive }
        [||] |> receive

This is the same as the NetworkStream for the most part, so I won't explain it.

Build a TCP Server

We're going to build two servers here, we'll build a TCP/IP server, and then an IMAP server. We'll do this because the raw TCP/IP server is pretty simple, and can be used for other servers as well.

A TCP/IP server needs two data-points to bind to: an IP Address, and a Port. These two values, when concatenated with a colon (:) make up a "socket". The server has a socket, and the client has a socket.

So one of the first things we need is the server endpoint: let endpoint = (ipAddress, port) |> IPEndPoint

So that's easy. The next thing we need is a server. In .NET we can accomplish a low-level TCP/IP server by using the Socket class (which we extended above), and binding. To start, we define our Socket:

let server = new Socket (AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp)

This builds a TCP/IP socket (which we named the server) to the InterNetwork address family (IP), the Stream socket type (raw bytes to and from), and the Tcp protocol (the TCP part of TCP/IP). Thus, we can use a stream to send and receive data.

Next, we bind:

(ipAddress, port) |> IPEndPoint |> server.Bind

Because I'm lazy, I bound and created the endpoint in the same line. This tells the server that it will be dealing specifically on the IP Address and Port we provided.

After binding, we listen:

SocketOptionName.MaxConnections |> int |> server.Listen

This builds a server with the MaxConnections configuration (allowing the maximum number of connections in the backlog) and then starts listening on the socket we asked for.

Once we've done that, we need to do the hard part. We need to do something with inbound connections, because by default the server doesn't actually do anything.

Listening for a new connection can be done with the socket.AsyncAccept function we built earlier, and because it's async we can ignore the threading issues (for the most part) and bind directly to it:

let! socket = () |> server.AsyncAccept

Now we won't get anything into socket until someone tries to connect, so we can then start working with that connection:

try Async.Start(socket |> events.Connect, cancellationToken = cts.Token)
with e -> ()

Now, what I did here is attempt to spawn a new asynchronous computation expression to handle the connection, it's not the job of the TCP/IP server to track that. We also passed a cancellation token in case we want to stop that expression later.

We'll then wrap that in an async { } block, and bind it to a function. If we include some basic logging, we have:

let cts = new CancellationTokenSource ()
let server = new Socket (AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp)
(ipAddress, port) |> IPEndPoint |> server.Bind
SocketOptionName.MaxConnections |> int |> server.Listen
(() |> ipAddress.ToString, port) ||> printfn "Started listening on %s:%d"

let rec waitForConnection () = 
    async {
        printfn "Waiting for connection..."
        let! socket = () |> server.AsyncAccept
        () |> socket.RemoteEndPoint.ToString |> printfn "Socket connected: %s"
        try Async.Start(socket |> events.Connect, cancellationToken = cts.Token)
        with e -> e.ToString() |> printfn "An error occurred: %s"
        return! () |> waitForConnection }

Good good, progress. Next, we want to unconditionally start the waitForConnection loop:

Async.Start(() |> waitForConnection, cancellationToken = cts.Token)

And finally, we'll build an IDisposable to properly handle closing the server:

{ new IDisposable with
    member this.Dispose () =
        () |> events.Close
        () |> cts.Cancel
        () |> server.Close
        () |> cts.Dispose
        () |> server.Dispose }

One of the things not defined here is events. I built a custom record for events the server can perform, which is extremely simple:

type ServerEvents =
    { Connect : Socket -> Async<unit>
      Close : unit -> unit }

Basically, we have a Connect and Close event.

All-in-all, if we put everything together and build a couple functions in a type, we have:

type Server () =
    static member StartI events port (ipAddress : IPAddress) =
        let cts = new CancellationTokenSource ()
        let server = new Socket (AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp)
        (ipAddress, port) |> IPEndPoint |> server.Bind
        SocketOptionName.MaxConnections |> int |> server.Listen
        (() |> ipAddress.ToString, port) ||> printfn "Started listening on %s:%d"

        let rec waitForConnection () = 
            async {
                printfn "Waiting for connection..."
                let! socket = () |> server.AsyncAccept
                () |> socket.RemoteEndPoint.ToString |> printfn "Socket connected: %s"
                try Async.Start(socket |> events.Connect, cancellationToken = cts.Token)
                with e -> e.ToString() |> printfn "An error occurred: %s"
                return! () |> waitForConnection }
        Async.Start(() |> waitForConnection, cancellationToken = cts.Token)

        { new IDisposable with
            member this.Dispose () =
                () |> events.Close
                () |> cts.Cancel
                () |> server.Close
                () |> cts.Dispose
                () |> server.Dispose }
    static member Start events port = (events, port, IPAddress.Any) |||> Server.StartI 

Which is a fully-functional TCP/IP server that does nothing, as of yet.

Building the basic IMAP Server

Our basic IMAP server won't comply with any parts of the protocol, but it will function as an end-to-end test of TCP/IP and the server we created. The IMAP server will use a TCP/IP server instance from the previous class to handle the raw TCP/IP portions, then will use a mutable list of connected sockets (including a basic User ID) to manage the connections. It will also send a BYE on close of the server to all connected sockets, thus allowing us to tell clients we're not there anymore, cleanly.

To start this process, we'll actually define the Start function of the server:

member this.Start () = EBrown.Tcp.Server.Start { Connect = this.OnConnect; Close = this.OnClose } 143

This helps push us to the right direction of where to go next. We need to define OnConnect and OnClose, which will be called by the TCP/IP server.

The OnConnect function really only has one job: accept a connected client, spawn the async computation for it, and add it to the list of all sockets. So for that, we'll define a pretty brief function:

member this.OnConnect (socket : Socket) =
    async {
        try
            lock sockets (fun () -> sockets <- (socket, None)::sockets)
            sockets |> List.length |> printfn "Sockets open: %i"
            return! socket |> runClient
        finally
            lock sockets (fun () -> sockets <- sockets |> List.filter (fst >> (<>) socket))
            SocketShutdown.Both |> socket.Shutdown |> socket.Close
            sockets |> List.length |> printfn "Sockets open: %i" }

This function just takes a socket, indicates that it's open, and then runs the async computation for it. When it closes, it removes the socket from the open pool. Pretty simple and basic. What we see here, that we haven't yet written, is runClient.

The runClient function is a little more complex, as it will actually do some things in our IMAP server. For now, all we want it to do is echo back what the user sent over the socket, when the user sends data. For this, we'll use AsyncReceiveAll, and send back with AsyncSend:

let rec runClient (socket : Socket) =
    let printfn = printfn "Socket %s: %s" (socket.RemoteEndPoint.ToString())
    async {
        let! buffer = () |> socket.AsyncReceiveAll
        let str = buffer |> Encoding.ASCII.GetString
        sprintf "Received (%i bytes): %s" buffer.Length str |> printfn
        if str.Length = 3 && str = "BYE" then printfn "Disconnected"
        else
            let! bytesSent = [| "Hello, other world!"B |] |> Array.concat |> socket.AsyncSend
            bytesSent |> sprintf "Sent response (%i bytes)" |> printfn
            return! socket |> runClient }

The goal here, is to loop until we have to kill the socket (for any reason). Currently, the only valid reason is a BYE, but there may be others at some point. (Such as errors, authentication failures, etc.)

Finally, we need the OnClose function, which should kill the server and tell all clients it's gone. This is actually really simple:

member this.OnClose () =
    lock sockets (fun () ->
        sockets
        |> List.toArray
        |> Array.filter (fun (sock, _) -> sock.Connected)
        |> Array.map (fun (sock, user) -> [| "BYE"B |] |> Array.concat |> sock.AsyncSend)
        |> Async.Parallel
        |> Async.RunSynchronously
        |> ignore)

If we put it all together, and add our mutable sockets, we get:

type User = { Id : string }

type Server () =
    let mutable sockets : (Socket * User option) list = []
    let rec runClient (socket : Socket) =
        let printfn = printfn "Socket %s: %s" (socket.RemoteEndPoint.ToString())
        async {
            let! buffer = () |> socket.AsyncReceiveAll
            let str = buffer |> Encoding.ASCII.GetString
            sprintf "Received (%i bytes): %s" buffer.Length str |> printfn
            if str.Length = 3 && str = "BYE" then printfn "Disconnected"
            else
                let! bytesSent = [| "Hello, other world!"B |] |> Array.concat |> socket.AsyncSend
                bytesSent |> sprintf "Sent response (%i bytes)" |> printfn
                return! socket |> runClient }
    member this.OnConnect (socket : Socket) =
        async {
            try
                lock sockets (fun () -> sockets <- (socket, None)::sockets)
                sockets |> List.length |> printfn "Sockets open: %i"
                return! socket |> runClient
            finally
                lock sockets (fun () -> sockets <- sockets |> List.filter (fst >> (<>) socket))
                SocketShutdown.Both |> socket.Shutdown |> socket.Close
                sockets |> List.length |> printfn "Sockets open: %i" }
    member this.OnClose () =
        lock sockets (fun () ->
            sockets
            |> List.toArray
            |> Array.filter (fun (sock, _) -> sock.Connected)
            |> Array.map (fun (sock, user) -> [| "BYE"B |] |> Array.concat |> sock.AsyncSend)
            |> Async.Parallel
            |> Async.RunSynchronously
            |> ignore)
    member this.Start () = EBrown.Tcp.Server.Start { Connect = this.OnConnect; Close = this.OnClose } 143

So now we want to test it.

Testing our Server

To test our server we need to start it, and build a client to connect to it. Both are trivial:

use server = Server().Start()
Console.ReadLine() |> ignore
printfn "Closing..."

This runs the server, forever. It will stay online until the user presses "Enter".

The client is much simpler than the server, and is just a few lines of code:

printfn "Press [Enter] / [Return] to quit, any other character to send data."
let cts = new CancellationTokenSource ()
use client = new TcpClient("127.0.0.1", 143)
printfn "Connected to %s" (client.Client.RemoteEndPoint.ToString())
use stream = client.GetStream()

let sendData = 
    async {
        while (Console.ReadKey().Key <> ConsoleKey.Enter) do
            if not cts.IsCancellationRequested then
                printfn ""
                [| "Hello world!"B |] |> Array.concat |> stream.Write
        [| "BYE"B |] |> Array.concat |> stream.Write
        printfn "Disconnected" }
let receiveData = 
    async {
        let rec loop () =
            async {
                let! bytes = () |> stream.AsyncReadAll
                let str = bytes |> Encoding.ASCII.GetString
                printfn "Received %i bytes: %s" bytes.Length str
                if str.Length = 3 && str = "BYE" then printfn "Disconnected, press any key to exit."; cts.Cancel() else return! () |> loop }
        return! () |> loop }
Async.Start(receiveData, cancellationToken = cts.Token)
try Async.RunSynchronously(sendData, cancellationToken = cts.Token)
with | :? OperationCanceledException -> () | e -> printfn "%s" (e.ToString()); printfn "Press enter to exit..."; Console.ReadLine() |> ignore

We're not going to do client-side work at all, so I won't detail anything about it, but it's really quite trivial.

If we build out two console applications, throw this code in and make it work, we can test it and see the result:

Client:

Press [Enter] / [Return] to quit, any other character to send data.
Connected to 127.0.0.1:143
a
Received 19 bytes: Hello, other world!
Disconnected

Server:

Started listening on 0.0.0.0:143
Waiting for connection...
Socket connected: 127.0.0.1:57309
Waiting for connection...
Sockets open: 1
Socket 127.0.0.1:57309: Received (12 bytes): Hello world!
Socket 127.0.0.1:57309: Sent response (19 bytes)
Socket 127.0.0.1:57309: Received (3 bytes): BYE
Socket 127.0.0.1:57309: Disconnected
Sockets open: 0

And there we have it. We've built bi-directional TCP/IP in a small amount of F# code, and can now begin the adventure of building the actual IMAP server.


If you are lazy, like me, and want this project for free, the entire thing will be available on GitHub. The version for this specific blog post is tree 8d269692ab169806e87b59700d69853b1d2eb1ff.


The blog post today is brought to you buy a significant amount of Coca-Cola and Fritos. I do not recommend either of these products unless you hate yourself (like me) and are trying to gain a lot of unnecessary weight. What I do recommend, however, is that you try to enjoy yourself as much as possible, and ignore what anyone else says about that. (You do you, basically.)

It's been a short while, as I took a longer-than-expected hiatus after the F# Advent of Code, but I'm back and we're going to work on a fun little project that involves a lot of detail and such.