www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Can std.variant be used with std.container.rbtree?

reply Vijay Nayar <madric gmail.com> writes:
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
next sibling parent reply JG <someone simewhere.com> writes:
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
parent Vijay Nayar <madric gmail.com> writes:
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
prev sibling next sibling parent reply vit <vit vit.vit> writes:
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
parent reply Vijay Nayar <madric gmail.com> writes:
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
parent reply Vijay Nayar <madric gmail.com> writes:
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
next sibling parent vit <vit vit.vit> writes:
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 `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.
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. } ```
Apr 02 2022
prev sibling parent Paul Backus <snarwin gmail.com> writes:
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 `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[])`.
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`.
 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
prev sibling next sibling parent reply Salih Dincer <salihdb hotmail.com> writes:
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
parent Vijay Nayar <madric gmail.com> writes:
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
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
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