Doxense/foundationdb-dotnet-client — pull request #42 by KrzysFR (2014-11-15 18:17:37+00:00)
Title: Tuples and Subspaces API refactoring

The goal of this PR is to introduce support for embedded Tuples, and fix several issues with the current Tuple and Subspace APIs.

__Tuple API overload resolution ambiguity__

Currently, the Tuple Encoding only supports flat tuples, meaning tuples composed of simple values such as string, integers, GUIDs, and so on. The Tuple API itself allows users to construct Tuples that contain other Tuples, but they will be flattened once packed, and will become flat tuples once unpacked. This issue, combined with some undefined behavior in the current API, means that most code out there is relying on an undefined behavior (embedded tuples that get flattened after a roundtrip to the db) will break in weird ways once the support for embedded tuples is introduced.

The typical problematic code:
```CSharp
// source transaction
tr.Set(subspace.Pack(FdbTuple.Create(42, "abc", 123)), Slice.FromString("hello"));

// in a different transaction
Slice key = await tr.GetRange(/* range that includes the above key).FirstOrDefaultAsync();
var t = subspace.Unpack(key);
// expected result
// t[0] = 42
// t[1] = "abc"
// t[2] = 123
```

Most people will think that they are creating the tuple `(42, "abc", 123)`, passing it to the subspace by calling `FdbSubpsace.Pack(IFdbTuple)` which packs the tuple, and appends it to the subspace prefix.

The problem is that `FdbTuple.Create(42, "abc", 123)` actually returns a instance of the struct `FdbTuple`(which implements `IFdbTuple`), but its return value is not IFdbTuple itself. This means that the actual code is:
```CSharp
FdbTuple tuple = FdbTuple.Create(42, "abc", 123);
Slice key = subspace.Pack>(tuple); // calls the generic subspace.Pack(T) mehtod!
tr.Set(key, ....);
```

The C# compiler has an instance of type `FdbTuple` and sees to candidate overrides `Pack(IFdbTuple)` and `Pack(T)`. For some reason, it chooses to resolve the call to the generic version, instead of the non-generic one. If the variable `tuple` is declared as an `IFdbTuple` than the compiler picks the non-generic version of the Pack method:
```CSharp
IFdbTuple tuple = FdbTuple.Create(42, "abc", 123);
Slice key = subspace.Pack(tuple); // calls the non-generic subspace.Pack(IFdbTuple) method!
tr.Set(key, ....);
```

The main difference is that the non-generic packs the 3-tuple `(42, "abc", 123)` while the generic version creates the singleton `( (42, "abc", 123), )` which contains the original tuple as it single element. But due to the undefined behavior of the Tuple Encoding, it gets flatten before encoding, and both code produce the same result.

With the new support for embedded tuples, the generic version would now produce a different binary key, one that would return the expected singleton tuple when unpacked. This will break any code that was reyling on the (undefined) flattening behavior.

Unfortunately, there are not much easy solutions to force the compiler to choose the "correct" overload, appart from always returning instances of tuples by their interface. But this would kill the performance benefit of being able to create short lived tuples as structs, which don't need to be garbage collected as long as they stay on the stack.

Only choice currently, is to change the name of all the generic Pack methods, so that there would be no overload resolution ambiguity. And while we are breaking the API, we should take this opportunity to also fix all the other small mistakes that were made.

__Decoupling Subspaces and Tuples__

The current `FdbSubspace` class comes from the initial Subspace python prototype (before 2.0) which was promoted into a first class API in FoundationDB 2.0. The main issue with it, is that it does two things at the same time: key subspaces, and key packing using the Tuple Encoding. This makes it very difficult for newcomers to understand what is actually going on (hence why most people fell into the trap of doing `subspace.Pack(FdbTuple.Create(1, 2, 3))` while they could have used `subspace.Pack(1, 2, 3)`. This also pollutes the API of classes that uses KeyEncoders, such as `FdbEncoderSubspace` which wraps a subspace and a custom key encoder (one that use any data encoding format), but it still exposes methods like "Pack()" or "Unpack()" which are Tuple-only.

The aim of this PR is also to decouple the notion of Tuple Encoding from subspaces, while still allowing people to use them if they don't want to deal with custom encoders.

The proposed solution is to move most key encoding methods from the IFdbSubspace interface (or extension methods), and move them to specific helper structs, that would be connected to the subspace via properties like `subspace.Keys`, `subspaces.Tuples`, or subpsace.Partition`.

For example, all theses will produce the same key (from less optimized to fastest)
```CSharp
tr.Set(subspace.Partition.By(123, "abc").Key, Slice.Empty);
tr.Set(subspace.Keys[FdbTuple.Pack(123, "abc")], Slice.Empty);
tr.Set(subspace.Tuples.Pack(FdbTuple.Create(123, "abc")), Slice.Empty);
tr.Set(subspace.Tuples.EncodeKey(123, "abc"), Slice.Empty);
```

The `subspace.Keys` helper struct deals only with binary keys, like Slice, or classes that implement `IFdbKey` which return a binary key. There will be everything to add and remove the subspace prefix to keys, deal with a single key or many keys at once (optimized).

The `subspace.Partition` helper struct deals with splitting the subspace into smaller subspaces. Since historically it was using the tuple encoding to create the suffixes, this is still supported via any of the `subspace.Partition.By` overloads.

The `subspace.Tuples` helper struct deals with tuples. The `Pack()` and `Unpack()` methods are non-generic, and deal with tuples as a whole. The `EncodeKey<>()` and `DecodeKey<>()` methods deals with items and are faster ways to create keys from tuple (without having to construct the tuple itself in the process). There are also variants that can encode or decode multiple tuples and keys at once.

Most of these helper structs support some shortcuts via indexers, like `subspace.Keys[Slice]` or subspace.Tuples[IFdbTuple]` which are shorter than calling the actual methods. The indexer method on a subspace itself as been removed, because there was no real good candidate to fill this role, and the current one (returns a new Subspace) was abused into creating sub-partitions just to get there Key, which was the slowest method.

__Parsing and Serializing embedded tuples__

Once the API is in good shape, we can now (without any ambiguity), create keys like `(1, (2, 3), "abc")`, which need to be encoded into bytes, and decoded back into there original shape.

The `NewType` encoding proposal did provision type headers `0x03` and `0x04` for tuple Start and End. Meaning that it would produce the following keys:
- `(1, 2)` => `<15><01> <15><02>`
- `( (1, 2), )` => `<03> <15><01> <15><02> <04>`
- `(1, (2, 3, 4), 5)` => `<15><01> <03> <15><02> <15><03> <15><04> <04> <15><05>`

This has several issues:
- It uses byte `0x04` to mark the end of a tuple, which can be found in other tokens, like integer 4 (`<15><04>`) or a byte string that would contain 4. This means that the parser cannot just scan until the next `0x04` to find the end of a tuple. It has to parse the content, to know which `0x04` are tokens and which are tuple end markers.
- Also, byte `0x04` (which represents the closing parenthesis) would be sorted _after_ byte[] or string items, as well as embedded tuples. Meaning that `(1, (2), "abc")` would be sorted _after_ `(1, (2, "abc"))` but _before_ `(1, (2, 42))` which is not what one would expect.

The only way to solve this issue would be to use `0x00` as the end marker of a tuple, but it conflicts with the already existing usage of `0x00` which is to define NIL entries in tuples. So `(1, (2, null))` and `(1, (2,), null)` would produce the same result. The proposed solution for ordering issues would be to change the encoding of NILs inside embedded tuples to `<00>`, while keeping a single `<00>` for NILs outside embedded tuples, in order to be compatible with the previous encoding.

The change would then allow things like:
- `(1, 2) => `<15><01> <15><02>`
- `((1, 2), ) => `<03> <15><01> <15><02> <00>`
- `(1, (2, 3, 4), 5)` => `<15><01> <03> <15><02> <15><03> <15><04> <00> <15><05>`
- `(1, (2, null))` => `<15><01> <03> <15><02> <00> <00>`
- `(1, (2,) null)` => `<15><01> <03> <15><02> <00> <00>`