Re: Data structures for efficient overload resolution

Steve Horne <stephenhorne100@aol.com> wrote in news:08-03-063@comp.compilers:
> When my naive approach resolves one particular call, it checks every
> single candidate. It looks linear at a glance, but it's not. An
> apparent ambiguity can arise early in the search only to be resolved
> later. For example, given a hierarchy with parent class p and child
> class c, consider the following sequence of candidates...
>
> 1 (p, c)
> 2 (c, p)
> 3 (c, c)
>
> When resolving for the call (c, c), candidates 1 and 2 will both
> appear valid with neither being more specific than the other.
> Therefore, when assessing candidate 3, it must be compared with both
> of these two earlier candidates. Only then can these candidates be
> eliminated. Comparisons must be done both with the call being resolved
> and with those previously identified candidates that have yet to be
> eliminated. Since the number of previously identified candidates can
> grow linearly with the number of candidates checked so far, the
> overall worst-case complexity is quadratic.


The usual way to do this is to compare each function against the list
of best matches for each argument irrespective of which function they
came from. That way you get O(nm) complexity in the number of
candidates and number of arguments. So after looking at #2, you'll
have (c, c) as your best match argument types and no function that
matches it. #3 will then match.


Chris Dodd
cdodd@acm.org

Return to the comp.compilers page.
Search the comp.compilers archives again.