Eigenstate: myrddin-dev mailing list

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Fixing The Implementation of Traits.


I'm pretty sure a butnch of people have been complaining about traits
being flaky with certain types a number of times. It turned out to be
a pretty deep problem with the implementation, and I finally took a
crack at fixing it.

Currently, the code is living in the `fixtraits` branch, and hasn't
been merged to master, becuase it's a fairly intrusive change. I'm
going to be testing it out in the next few days, and trying to break
it more, as well as deleting some dead code and doing some cleanup.

If you've got some trait heavy code, throw it at this and see if you
can break it!

So, for a summary of what's changed:

The bad old days:

	Because the traits were tracked in a bitset in the type itself,
	unification would lead to some type instances not having the trait
	itself. For example, before these changes:

		impl comparable int[:] = ... ;;

	would create an int[:], and insert the trait into its trait bitset,
	giving:

		int[:]::comparable

	That's fine, now whenever you use int[:], it satisfies the trait.
	Except:

		var x
		frob(x[:])	/* now x has $t[:] */
		x[0] = 123

	In this case, because we only unified $t with int, the bitset on the
	slice did *not* track the trait.

Now, after fixing it:

	The traits are no longer stored inside the types, but instead are in
	their own trie-like table:

		struct Traitmap {
			Bitset *traits;
			Traitmap *sub[Ntypes];

			Htab *name;	/* name => bitset(traits) */
			Type **filter;
			size_t nfilter;
			Trait **filtertr;
			size_t nfiltertr;
		};

	Each node on the trie contains all the traits that the type can have.
	For most types, this means simply walking down the trie based on the
	type id, looking up the name nodes as we go.

	For example:

		impl foo @a#
		impl bar int#
		impl baz int#
		impl quux byte#
		impl glarp int
		impl glorp @a::numeric#
		impl blart nametype

	would have:

		Typtr:
			traits: {foo}
			filter: {@a::numeric# => glorp}
			Tyint:
				traits: {bar,baz}
			Tybyte:
				traits: {quux}
		Tyint:
			glarp
		Tyname:
			name[nametype] => {blart}


	Looking up the traits for ain int#, one would start at the root, and
	walk down the Typtr node, adding 'foo' to the implemented type. Then,
	down to the Tyint node, adding {foo} to the type, and checking if all
	the filtered types satisfy it. In this case, int satisfies
	@a::numeric, so it is added to the set as well. Then, on to the int
	node, which implements {bar, baz}. Therefore, the final set of types
	here is {foo,glorp,bar,baz}.

	For names, there's a final lookup in the name table to get the set
	of implemented types, but the idea is generally the same.

	This is a fairly efficient set of operations, so in the end there's
	no measurable difference to compile time when building libstd.



-- 
    Ori Bernstein

Follow-Ups:
Re: Fixing The Implementation of Traits.Ori Bernstein <ori@xxxxxxxxxxxxxx>