[dmd-internals] Fixing forward ref bugs for good

[Benjamin Shropshire]

On 09/14/2011 11:29 PM, Rainer Schuetze wrote:
> On 15.09.2011 05:58, Benjamin Shropshire wrote:
>> On 09/14/2011 12:06 AM, Rainer Schuetze wrote:
>>>
>>> On 14.09.2011 00:04, Walter Bright wrote:
>>>> Don, just so you know, I've been thinking for a while about 
>>>> transitioning from doing the semantic pass in order to doing it 
>>>> completely "on demand". In other words, try to semantic a 
>>>> declaration. In the process, any declarations it depends on are 
>>>> semantic'd if not already, recursively.
>>>
>>> I've been trying something similar for Visual D in its yet to 
>>> integrate semantic analysis for intellisense. Still, static if and 
>>> mixins get in the way of complete "on demand" handling. When a 
>>> symbol is searched in a scope (e.g. a module, class, struct), some 
>>> preparational work has to be done before the member list can be 
>>> searched:
>>>
>>> 1. all "simple" non-scoping members are expanded (version/debug 
>>> conditions, attributed declaration blocks). the branch inserted to 
>>> the scopes' member list is also searched for "simple" non-scoping 
>>> members (this step could also be done non-lazily, but doing it 
>>> lazily slightly changes the interaction of version statements and 
>>> conditionals with "static if" conditionals - good or bad, I don't know)
>>>
>>> 2. "complex" non-scoping members are expanded in lexical order 
>>> (static if, mixins). When inserting the expanded branch into the 
>>> scopes member list, the expansion restarts at 1.
>>>
>>> This works out better than the current dmd implementation, e.g. when 
>>> forward referencing symbols in a mixin. There are still situations 
>>> that depend on interpretation order, but that is to be expected when 
>>> "static if" is used.
>>>
>>
>> Every time I've puzzled over the problem, the solution I've 
>> gravitated to is to have the symbol table logic result be tri-state: 
>> symbol-found, no-symbol, unknown/incomplete (for when a lookup 
>> includes an unprocessed scope). From there, you greedily evaluate all 
>> symbol that you can and proceed with whatever processing can be done, 
>> bailing when an "incomplete" results is found and keeping a list of 
>> where to come back and try again later. The only question then is how 
>> to handle the case where you dead lock. I suspect that if you make 
>> that illegal, a lot of legacy code will break. I'm going to guess we 
>> will want to have a small set of well thought out deadlock escape rules.
>
> I guess, Walter also wants to get rid of the "try again later" part. 
> Especially is-expressions and trait(compiles) are getting rather 
> indeterministic and might depend on other symbols being looked up 
> before. If the evaluation is lazy, there is some hope that 
> dependencies will be cyclic only in cases that are actual errors. I'm 
> not sure about a good cycle-detection, though. (Is that what you meant 
> by "deadlock escape"?)

Not exactly, what I'm thinking of wouldn't come into play until after a 
cycle has been detected. Breaking or escaping a deadlock would require 
ignoring an "unknown" lookup result by assuming the related scope(s) 
won't have any more relevant symbols. The issue is choosing where to 
make the guess. The simplest case would be a static if where you can 
look at both sides and see all the symbols (no complex mixins) and can 
show that regardless of which side is used the injected symbol won't 
effect it self.

>
> What happens, if the evaluation of "static if" turns out to require 
> symbols from the same scope? (Something I did not mention above: 
> unconditionally existing or expanded members of a scope should be 
> added to the symbol lookup as soon as possible.) My current suggestion 
> is: do not recurse into the expansion of "complex" members, just use 
> the currently available symbols.
>
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals