Implementing Set<T>

Question

I'm trying to wrap my head around abstract by implementing a Set data-type, like so:

abstract Set<T>(Map<T, Bool>) {
  public inline function new() {
    this = new Map<T, Bool>();
  }

  public inline function has(item:T):Bool {
    return this.exists(item);
  }

  public inline function add(item:T):Set<T> {
    this.set(item, true);
    return null;
  }

  public inline function remove(item:T):Set<T> {
    this.remove(item);
    return null;
  }

  public inline function iterator():Iterator<T> {
    return this.keys();
  }
}

The compiler doesn't like this, though. It tells me Set.hx:8: characters 11-29 : Abstract Map has no @:to function that accepts IMap<util.Set.T, Bool>

I don't really understand this at all, since if I change the constructor to

public inline function new(val:Map<T, Bool>) {
  this = val;
}

and then instantiate with var set = new Set(new Map());, it works.

That's pretty gross, though. I'd like the ability to instantiate Sets without exposing the underlying implementation. Ultimately, I'd prefer a constructor with the signature new(?initial:Iterable<T>). Is this possible? Am I misunderstanding something?

Mayfield

Answer 1

The problem is that currently it's impossible to instantiate Map without they key type being known (and since Set.T is a free type parameter, this doesn't work). However since the constructor is inline, T may well be known at the call site. The problem is that the compiler still tries to generate Set.new. You can avoid this by prefixing it with @:extern. Working example: https://try.haxe.org/#1D06C

Resupine

Thanks! That totally works, but I'm not sure I grasp what @:extern is doing. If I switch to the "classic" this = val; abstract constructor (so that it will compile without @:extern), and compile with and without @:extern, I don't see any differences in the generated javascript. Is there more in-depth documentation on abstract somewhere that covers this stuff? – Mayfield

This is not really related to abstracts. If you add inline to a function it tells the compiler to try to inline it at the call site (but it doesn't always do that). In any case, the function is still generated (unless the dead code elimination purges it, but that is just an optimization). If you run haxe --help-metas it will include the following line: @:extern : Marks the field as extern so it is not generated. This tells the compiler that Set.new does not actually exist, so it doesn't have to worry about the generic case. You can set DCE to no/std in the option to see the difference. – Resupine

Interesting... I thought that all functions marked inline were treated that way, especially since abstracts aren't actually generated classes. Where would the compiled generate an inline function on an abstract that wasn't marked @:extern? – Mayfield

The compiler may not inline a function because for example it generates too much code, or because you compile with --no-inline or what not. The only way to truly force it is to add @:extern or if the inline function is defined on an extern class. That will mean for example that structural subtyping with an anonymous type that expects the function no longer is possible (because the function is not actually there). – Resupine