toHash => pure, nothrow, const, @safe

[Andrei Alexandrescu]

On 3/13/12 10:47 AM, deadalnix wrote:
> This problem is pretty close to garbage collection. Let's use pure as
> example, but it work with other qualifier too.
>
> function are marked pure, impure, or pure given all function called are
> pure (possibly pure). Then you go throw all possibly pure function and
> if it call an impure function, they mark it impure. When you don't mark
> any function as impure on a loop, you can mark all remaining possibly
> pure functions as pure.

Certain analyses can be done using the so-called worklist approach. The 
analysis can be pessimistic (initially marking all functions as not 
carrying the property analyzed and gradually proving some do carry it) 
or optimistic (the other way around). The algorithm ends when the 
worklist is empty. This approach is well-studied and probably ought more 
coverage in compiler books. I learned about it in a graduate compiler class.

However, the discussion was about availability of the body. A 
worklist-based approach would need all functions that call one another 
regardless of module. That makes the analysis interprocedural, i.e. 
difficult on large codebases.


Andrei