sunder icon indicating copy to clipboard operation
sunder copied to clipboard

Cannot use `std::hash_map` and `std::hash_set` with recursive types

Open ashn-dot-dev opened this issue 1 year ago • 1 comments

std::hash_map

import "std";

struct foo {
    var map: std::hash_map[[ssize, foo]];
}

func main() void {
    var x: foo = uninit;
}
$ sunder-compile test.sunder
[std/std.sunder:3100] error: struct `struct { var state: usize; var index: usize; var key: ssize; var value: foo; }` contains a member variable of incomplete struct type `foo`
        var value: V;
        ^
[test.sunder:4] info: ...encountered during template instantiation of `std::hash_map[[ssize, foo]]`
    var map: std::hash_map[[ssize, foo]];
                  ^

std::hash_set

import "std";

struct foo {
    var set: std::set[[foo]];
}

func main() void {
    var x: foo = uninit;
}
$ sunder-compile test.sunder
[std/std.sunder:3096] error: struct `struct { var state: usize; var index: usize; var key: foo; var value: void; }` contains a member variable of incomplete struct type `foo`
        var key: K;
        ^
[std/std.sunder:3408] info: ...encountered during template instantiation of `std::hash_map[[foo, void]]`
    var _hash_map: std::hash_map[[T, void]];
                        ^
[test.sunder:4] info: ...encountered during template instantiation of `std::hash_set[[foo]]`
    var set: std::hash_set[[foo]];
                  ^

Additional Notes

Attempting to box the templated type using a pointer also does not work:

import "std";

struct foo {
    var map: *std::hash_map[[ssize, foo]];
}

func main() void {
    var x: foo = uninit;
}
$ sunder-compile test.sunder
[std/std.sunder:3100] error: struct `struct { var state: usize; var index: usize; var key: ssize; var value: foo; }` contains a member variable of incomplete struct type `foo`
        var value: V;
        ^
[test.sunder:4] info: ...encountered during template instantiation of `std::hash_map[[ssize, foo]]`
    var map: *std::hash_map[[ssize, foo]];
                   ^

In order to hold the data, a boxed any must be used to "smuggle" the heap allocated struct:

import "std";
import "sys";

struct foo {
    var _map: *any; # std::hash_map[[ssize, foo]];

    func map(self: *foo) *std::hash_map[[ssize, foo]] {
        return (:*std::hash_map[[ssize, foo]])self.*._map;
    }
}

func main() void {
    var x: foo = uninit;
    sys::dump[[typeof(x.map())]](x.map());
}
$ sunder-run test.sunder
00 00 00 00 00 00 00 00

The discovery of this issue, and an example of this smuggling in action, comes from an initial draft of a data interchange format library called bubby: https://github.com/ashn-dot-dev/bubby/blob/4f1f6f0f605b8ba7f6d18fa1c0945460576fabab/bubby.sunder#L22C1-L23C50

ashn-dot-dev avatar Dec 08 '23 21:12 ashn-dot-dev