Adam posted this in beerconf, as an alternative to std.meta.NoDuplicates:

template NoDuplicates(T...) {
        import std.meta;
        string getIndexesCode() {
                size_t[string] things;
                foreach(idx, t; T)
                        things[t.mangleof] = idx;
                string code;
                foreach(k, v; things) {
                        if(code.length) code ~= ", ";
                        code ~= "T[" ~ cast(char) (v + '0') ~ "]";
                }
                return "AliasSeq!(" ~ code ~ ")";
        }
        alias NoDuplicates = mixin(getIndexesCode());
}

Now, this works only on types, because of t.mangleof. So for instance if you do 3.manglof, it gives "i", the mangle for int. But I figured out, if I combine both the mangleof and stringof, you get something that is bound to be unique for each value AND type.

Here's an alternate:

template NoDuplicates(T...)
{
    import std.meta : AliasSeq;

    string getIndexesCode()
    {
        size_t[string] things;
        static foreach (idx, alias t; T)
            things[t.mangleof ~ t.stringof] = idx;
        string code;
        foreach (k, v; things)
        {
            code ~= "/*" ~ k ~ "*/ T[" ~ cast(char)(v + '0') ~ "],";
        }
        return code;
    }

    // pragma(msg, getIndexesCode()); // uncomment to see the keys and indexes
    mixin("alias NoDuplicates = AliasSeq!(" ~ getIndexesCode() ~ ");");
}

I tested this a bit, and it works pretty well.

I think the only thing that doesn't work with this is a lambda, which __traits(isSame) treats specially. Any other problems with this?

Another way to solve this is just to use CTFE brute force:

template NoDuplicates(T...)
{
    import std.meta : AliasSeq;

    string getIndexesCode()
    {
        string code;
        static foreach(i; 0 .. T.length)
        {{
            bool includeit = true;
            static foreach(j; i + 1 .. T.length)
                static if(__traits(isSame, T[i], T[j]))
                   includeit = false;
            if(includeit)
                code ~= "T[" ~ i.stringof ~ "],";
        }}
        return code;
    }

    //pragma(msg, getIndexesCode());
    mixin("alias NoDuplicates = AliasSeq!(" ~ getIndexesCode() ~ ");");
}

I'm not sure which one would perform better. One has better complexity, but the other is more correct (you could possibly split out lambdas or other problematic things into their own sub-function). But both I think might be a step up over the current NoDuplicates, which is horrendously complicated.

-Steve

On 9/26/20 11:15 PM, Steven Schveighoffer wrote:
> But I figured out, if I combine both the mangleof and stringof, you get something that is bound to be unique for each value AND type.

That's a pretty awesome hack. Currently the reification code keeps a separate enum to distinguish between values and types. This trick could help with getting rid of that.

One disadvantage is that once you concatenate you lose the interning (mangled types are interned so you only need to compare pointers to decide whether two types are equal). But, in the words of Steven Wright, you can't have everything; where would you put it?

> I'm not sure which one would perform better. One has better complexity, but the other is more correct (you could possibly split out lambdas or other problematic things into their own sub-function). But both I think might be a step up over the current NoDuplicates, which is horrendously complicated. 

For reference this is the reification-based code:

alias NoDuplicates(Args...) = dereify!({
    auto ids = reifyArray!Args;
    size_t newLength = ids.length;
    for (size_t i = 0; i < newLength; ++i) {
        newLength = 1 + i + ids[i + 1 .. $].remove!(x => x == ids[i]).length;
    }
    return ids[0 .. newLength];
}());

It calls into std.remove to (inefficiently) get rid of duplicates of the ith element from the array from the remainder of the array, thus compacting the array as it goes. At the end the result will be on the left end of the array.

Measuring the speed of each of these would be quite interesting.