digitalmars.D.learn - Can std.variant be used with std.container.rbtree?
- Vijay Nayar (44/44) Apr 01 2022 Consider the following program:
- JG (9/17) Apr 02 2022 You need an order on the elements in a red black tree. Am I
- Vijay Nayar (24/33) Apr 02 2022 This is correct, although it seems that Variant is not suitable
- vit (6/14) Apr 02 2022 Variant can contain any type => variant cannot assume attributes
- Vijay Nayar (39/40) Apr 02 2022 I'm playing with SumType to see how it works, and I must be doing
- Vijay Nayar (12/20) Apr 02 2022 Through sheer trial and error, I discovered that changing the
- vit (28/48) Apr 02 2022 Try this:
- Paul Backus (29/49) Apr 02 2022 The reason `const` is required is that the arguments to your
- Salih Dincer (26/39) Apr 02 2022 If your type includes opCmp() there is no reason not to use
- Vijay Nayar (3/5) Apr 02 2022 I am using rbTree, the problem is when I try to use it with
- Steven Schveighoffer (9/55) Apr 02 2022 The issue is that for some reason redblacktree declares a `@safe nothrow...
Consider the following program:
```d
void main()
{
import std.stdio;
import std.container.rbtree;
import std.variant;
// alias Type = int; // Works with no problem.
alias Type = Variant; // Produces error.
auto rbTree = new RedBlackTree!(Type);
rbTree.stableInsert(Type(3));
rbTree.stableInsert(Type(2));
rbTree.stableInsert(Type(4));
foreach (v; rbTree.upperBound(Type(2))) {
writeln(v);
}
}
```
A `RedBlackTree` constructs and runs perfectly fine using "int"
as the data type, but it seems to blow up as soon as I use
`std.variant : Variant`.
```
Compilation output (1: )
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1116): Error:
` safe` function `std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b",
false).RedBlackTree.toHash` cannot call ` system` function
`std.container.rbtree.RBRange!(RBNode!(VariantN!32LU)*).RBRange.front`
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(682):
`std.container.rbtree.RBRange!(RBNode!(VariantN!32LU)*).RBRange.front` is
declared here
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1116): Error:
destructor `std.variant.VariantN!32LU.VariantN.~this` is not `nothrow`
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1113): Error:
function `std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b",
false).RedBlackTree.toHash` may throw but is marked as `nothrow`
onlineapp.d(10): Error: template instance
`std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b",
false)` error instantiating
```
This may seem like a strange thing to do, but it is useful when
trying to have set of indexes, each of which is used on a
different data field. The set of indexes can share a common
data-type using Variant, which allows one to do things like have
associative arrays of indexes which you can look up by field name.
However, it looks like `Variant` doesn't have the various
attributes desired by `RedBlackTree`. Is there a way to make them
compatible? Do I need to avoid std.container.rbtree and make my
own which doesn't require these attributes, or do I need to
implement my own version of Variant using a union and try to make
it safe/nothrow/etc.?
Apr 01 2022
On Friday, 1 April 2022 at 22:22:21 UTC, Vijay Nayar wrote:
Consider the following program:
```d
void main()
{
import std.stdio;
import std.container.rbtree;
import std.variant;
[...]
You need an order on the elements in a red black tree. Am I
correct in thinking you want a container of the form given a key
(a string) recover some data (of different types). If so make the
elements you store in the red black tree tuples (k,d) where k is
a string and d is a variant. Define the order (k1,d1)<(k2,d2) if
k1<k2. Make sure to allo duplicates. The when you search for a
key you get the pair and take the second part. I hope this makes
sense.
Apr 02 2022
Vijay Nayar <madric gmail.com> On Saturday, 2 April 2022 at 10:03:19 UTC, JG wrote:You need an order on the elements in a red black tree. Am I correct in thinking you want a container of the form given a key (a string) recover some data (of different types). If so make the elements you store in the red black tree tuples (k,d) where k is a string and d is a variant. Define the order (k1,d1)<(k2,d2) if k1<k2. Make sure to allo duplicates. The when you search for a key you get the pair and take the second part. I hope this makes sense.This is correct, although it seems that Variant is not suitable for this purpose. The data structure roughly looks like this: - FieldName (string) => Index - Index has PrimaryKey (Variant) and a Value (also Variant) - Index Entries are a tuple of the form (PrimaryKey, Value) Each index is roughly used by passing in a value, and it spits out a range of PrimaryKeys that are equal, lessThan, or greaterThan that value depending on what's needed. The special Entry data type (rather than just the raw value) was added because I still need the IDs when I look up values, and I think using the Entry is every so slightly more efficient than maintaining a separate data structure keeping a set of Ids per Value. Variant itself works well for comparison, because it simply passes down the compare operation to the underlying type, but it's major flaw seems to be the lack of support for noThrow, safe, etc. On Saturday, 2 April 2022 at 10:04:49 UTC, vit wrote:Try use ```std.sumtype```.Very good suggestion, I haven't tried this before. I'll do some digging to see if I can make it work. Because it requires one to list the data types in advance, it can work for primary keys, however, it may not work in my particular use case because the values too that I'm organizing are also Variants. I hope it works.
Apr 02 2022
On Friday, 1 April 2022 at 22:22:21 UTC, Vijay Nayar wrote:
Consider the following program:
```d
void main()
{
import std.stdio;
import std.container.rbtree;
import std.variant;
[...]
Variant can contain any type => variant cannot assume attributes
like pure nothrow safe nogc on its methods. RedBlackTree has
nothrow dtor => Element type must have nothrow dtor => Variand
need nothrow dtor... Similar for other methods.
Try use ```std.sumtype```.
Apr 02 2022
On Saturday, 2 April 2022 at 10:04:49 UTC, vit wrote:Try use ```std.sumtype```.I'm playing with SumType to see how it works, and I must be doing something silly, because it fails to compile with the first example type I attempted. Consider the following: ```d import std.sumtype; import std.algorithm : cmp; alias VarType = SumType!(double, ubyte[]); int opCmp(const ref VarType v1, const ref VarType v2) { alias doMatch = tryMatch!( (ref ubyte[] _1, ref ubyte[] _2) => cmp(_1, _2), (_1, _2) => _1 < _2 ? -1 : (_2 < _1 ? 1 : 0)); return doMatch(v1, v2); } void main() { VarType b1 = cast(ubyte[]) [0x01, 0x02, 0x03]; VarType b2 = cast(ubyte[]) [0x01, 0x02, 0x04]; b1 > b2; } ``` The `tryMatch` method fails to compile, and instead I get the following error: ```d /dlang/dmd/linux/bin64/../../src/phobos/std/sumtype.d(2004): Error: static assert: "`handlers[0]` of type `int function(ref ubyte[] _1, ref ubyte[] _2) pure nothrow nogc safe` never matches" /dlang/dmd/linux/bin64/../../src/phobos/std/sumtype.d(1739): instantiated from here: `matchImpl!(const(SumType!(double, ubyte[])), const(SumType!(double, ubyte[])))` onlineapp.d(10): instantiated from here: `tryMatch!(const(SumType!(double, ubyte[])), const(SumType!(double, ubyte[])))` ``` I'm not super sure why this handler would not match. If I do simple types like `double` or `int` it works, it even works with `string`, but the moment I include `ubyte[]`, it no longer compiles. In this example, I eliminated all other array types aside from `ubyte[]`, so there should be no conflicts in theory.
Apr 02 2022
On Saturday, 2 April 2022 at 14:35:10 UTC, Vijay Nayar wrote:The `tryMatch` method fails to compile, and instead I get the following error: ```d /dlang/dmd/linux/bin64/../../src/phobos/std/sumtype.d(2004): Error: static assert: "`handlers[0]` of type `int function(ref ubyte[] _1, ref ubyte[] _2) pure nothrow nogc safe` never matches" ```Through sheer trial and error, I discovered that changing the handler arguments from `ref ubyte[]` to `const ref ubyte[]` the error goes away. However, I did not find any information in the documentation or code that made this requirement clear. It was basically a guess based on the fact that `string` has no trouble but `ubyte[]` did, and string is basically just `immutable(char[])`. So far, I'm finding that learning to use `SumType` is significantly more cryptic than `Variant`, by a large margin. I'll still give it a shot of course, because I want to get past this problem.
Apr 02 2022
On Saturday, 2 April 2022 at 14:49:15 UTC, Vijay Nayar wrote:On Saturday, 2 April 2022 at 14:35:10 UTC, Vijay Nayar wrote:Try this: ```d import std.sumtype; import std.algorithm : cmp; alias VarType = SumType!(double, ubyte[]); int opCmp(const ref VarType v1, const ref VarType v2) { //you need all combinations of types: static int impl(A, B)(auto ref A a, auto ref B b){ // (double, ubyte[]) or (ubyte[], double): static if(!is(immutable A == immutable B)) assert(0, "type missmatch"); // (ubyte[], ubyte[]): else static if(is(immutable A == immutable ubyte[])) return cmp(a, b); // (double, double): else return (a < b) ? (-1) : (a < b ? 1 : 0); } return tryMatch!impl(v1, v2); } void main(){ VarType b1 = cast(ubyte[]) [0x01, 0x02, 0x03]; VarType b2 = cast(ubyte[]) [0x01, 0x02, 0x04]; assert(opCmp(b1, b2) == -1); //operator overloading work only if opCmp is method. } ```The `tryMatch` method fails to compile, and instead I get the following error: ```d /dlang/dmd/linux/bin64/../../src/phobos/std/sumtype.d(2004): Error: static assert: "`handlers[0]` of type `int function(ref ubyte[] _1, ref ubyte[] _2) pure nothrow nogc safe` never matches" ```Through sheer trial and error, I discovered that changing the handler arguments from `ref ubyte[]` to `const ref ubyte[]` the error goes away. However, I did not find any information in the documentation or code that made this requirement clear. It was basically a guess based on the fact that `string` has no trouble but `ubyte[]` did, and string is basically just `immutable(char[])`. So far, I'm finding that learning to use `SumType` is significantly more cryptic than `Variant`, by a large margin. I'll still give it a shot of course, because I want to get past this problem.
Apr 02 2022
On Saturday, 2 April 2022 at 14:49:15 UTC, Vijay Nayar wrote:On Saturday, 2 April 2022 at 14:35:10 UTC, Vijay Nayar wrote:The reason `const` is required is that the arguments to your function, `v1` and `v2`, are `const`. In D, the `const` qualifier is transitive, so if you have a `const VarType`, whatever value it contains will also be qualified with `const`.The `tryMatch` method fails to compile, and instead I get the following error: ```d /dlang/dmd/linux/bin64/../../src/phobos/std/sumtype.d(2004): Error: static assert: "`handlers[0]` of type `int function(ref ubyte[] _1, ref ubyte[] _2) pure nothrow nogc safe` never matches" ```Through sheer trial and error, I discovered that changing the handler arguments from `ref ubyte[]` to `const ref ubyte[]` the error goes away. However, I did not find any information in the documentation or code that made this requirement clear. It was basically a guess based on the fact that `string` has no trouble but `ubyte[]` did, and string is basically just `immutable(char[])`.So far, I'm finding that learning to use `SumType` is significantly more cryptic than `Variant`, by a large margin. I'll still give it a shot of course, because I want to get past this problem.It's possible to get more informative error messages using the `-verrors=spec` compiler flag, although it's a bit of a hassle. The basic process is 1. Recompile the module that the error occurs in with `-verrors=spec` and redirect output to a file. ``` dmd -verrors=spec -c source/mymodule.d >verrors.txt 2>&1 ``` 2. Use `grep` or your text editor's search function to find errors that occurred in that source file or in `sumtype.d`. ``` grep -e 'source/mymodule.d' -e 'std/sumtype.d' verrors.txt ``` Following these steps on your example code yields around 20 lines of output, which includes the "real" error message: ``` (spec:1) /usr/include/dmd/phobos/std/sumtype.d(1768): Error: function literal `__lambda3(ref ubyte[] _1, ref ubyte[] _2)` is not callable using argument types `(const(ubyte[]), const(ubyte[]))` (spec:1) /usr/include/dmd/phobos/std/sumtype.d(1768): cannot pass argument `_param_0` of type `const(ubyte[])` to parameter `ref ubyte[] _1` ```
Apr 02 2022
On Friday, 1 April 2022 at 22:22:21 UTC, Vijay Nayar wrote:A `RedBlackTree` constructs and runs perfectly fine using "int" as the data type, but it seems to blow up as soon as I use `std.variant : Variant`. ``` Compilation output (1: ) /dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1116): Error: ` safe` function `std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b", false).RedBlackTree.toHash` cannot call ` system` function `std.container.rbtree.RBRange!(RBNode!(VariantN!32LU)*).RBRange.front` /dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(682): `std.container.rbtree.RBRange!(RBNode!(VariantN!32LU)*).RBRange.front` is declared here /dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1116): Error: destructor `std.variant.VariantN!32LU.VariantN.~this` is not `nothrow` /dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1113): Error: function `std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b", false).RedBlackTree.toHash` may throw but is marked as `nothrow` onlineapp.d(10): Error: template instance `std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b", false)` error instantiating ```If your type includes opCmp() there is no reason not to use rbTree. Let me give a simple example: ```d struct Char { char c; auto opCmp(Char rhs) const { return c == rhs.c ? 0: c - rhs.c; } } import std.container.rbtree; import std.stdio; void main() { alias Type = Char; with(new RedBlackTree!(Type)) { stableInsert(Type('B')); stableInsert(Type('A')); stableInsert(Type('C')); foreach (v; upperBound(Type('A'))) v.c.write(", "); writeln; // "B, C, " } } ``` SDB 79
Apr 02 2022
On Saturday, 2 April 2022 at 14:23:31 UTC, Salih Dincer wrote:If your type includes opCmp() there is no reason not to use rbTree.I am using rbTree, the problem is when I try to use it with Variant, at which point it blows up.
Apr 02 2022
On 4/1/22 6:22 PM, Vijay Nayar wrote:
Consider the following program:
```d
void main()
{
import std.stdio;
import std.container.rbtree;
import std.variant;
// alias Type = int; // Works with no problem.
alias Type = Variant; // Produces error.
auto rbTree = new RedBlackTree!(Type);
rbTree.stableInsert(Type(3));
rbTree.stableInsert(Type(2));
rbTree.stableInsert(Type(4));
foreach (v; rbTree.upperBound(Type(2))) {
writeln(v);
}
}
```
A `RedBlackTree` constructs and runs perfectly fine using "int" as the
data type, but it seems to blow up as soon as I use `std.variant :
Variant`.
```
Compilation output (1: )
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1116):
Error: ` safe` function
`std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b",
false).RedBlackTree.toHash` cannot call ` system` function
`std.container.rbtree.RBRange!(RBNode!(VariantN!32LU)*).RBRange.front`
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(682):
`std.container.rbtree.RBRange!(RBNode!(VariantN!32LU)*).RBRange.front`
is declared here
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1116):
Error: destructor `std.variant.VariantN!32LU.VariantN.~this` is not
`nothrow`
/dlang/dmd/linux/bin64/../../src/phobos/std/container/rbtree.d(1113):
Error: function `std.container.rbtree.RedBlackTree!(VariantN!32LU, "a <
b", false).RedBlackTree.toHash` may throw but is marked as `nothrow`
onlineapp.d(10): Error: template instance
`std.container.rbtree.RedBlackTree!(VariantN!32LU, "a < b", false)`
error instantiating
```
The issue is that for some reason redblacktree declares a ` safe nothrow
toHash` function.
https://github.com/dlang/phobos/blob/99e9c1b7741e0f4e6f2a8c14883c4828d092701d/std/container/rbtree.d#L1113
I'm not sure why that is. But just copying a Variant is not ` safe
nothrow`. So this explains why it's not working.
RBT should detect whether it can call the toHash with the appropriate
attributes and declare it based on that.
-Steve
Apr 02 2022