Fixing The Implementation of Traits.
[Thread Prev] | [Thread Next]
- Subject: Fixing The Implementation of Traits.
- From: Ori Bernstein <ori@xxxxxxxxxxxxxx>
- Reply-to: myrddin-dev@xxxxxxxxxxxxxx
- Date: Sun, 20 Aug 2017 20:32:00 -0700
- To: myrddin-dev@xxxxxxxxxxxxxx
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
Re: Fixing The Implementation of Traits. | Ori Bernstein <ori@xxxxxxxxxxxxxx> |
- Prev by Date: Re: Full Syscall Support: Linux + OpenBSD 6.1
- Next by Date: Re: Fixing The Implementation of Traits.
- Previous by thread: Re: Full Syscall Support: Linux + OpenBSD 6.1
- Next by thread: Re: Fixing The Implementation of Traits.
- Index(es):