Consider the following program:

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.?

On Friday, 1 April 2022 at 22:22:21 UTC, Vijay Nayar wrote:

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.

On Friday, 1 April 2022 at 22:22:21 UTC, Vijay Nayar wrote:

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:

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

On Saturday, 2 April 2022 at 14:23:31 UTC, Salih Dincer wrote:

I am using rbTree, the problem is when I try to use it with Variant, at which point it blows up.

On Saturday, 2 April 2022 at 10:04:49 UTC, vit wrote:

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:

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:

/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.

On Saturday, 2 April 2022 at 14:35:10 UTC, Vijay Nayar wrote:

/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.

On Saturday, 2 April 2022 at 14:49:15 UTC, Vijay Nayar wrote:

/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"

Try this:

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.
}

On 4/1/22 6:22 PM, Vijay Nayar wrote:

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);
   }
}

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