Currently, we have a query that returns a list of the
DefIds for all associated items, as well as a query that finds the
ty::AssocItem for the associated item with the given
DefId using a linear search. Finally, we have an
associated_items query which returns a list of
ty::AssocItem, but which only works in the local crate. This query is implemented by calling
associated_item on each
DefId returned by
associated_item_def_ids, meaning it takes O(n²) time where
n is the number of associated items. The result is cached so we only ever pay this cost once.
I want to do away with the
associated_item_def_ids query and cache the results of
ty::AssocItem is a small,
Copy header that already contains the
DefId for that item. This would avoid the quadratic behavior.