DCT: D compiler as a collection of libraries

[Ary Manzana]

On 5/11/12 10:14 PM, Roman D. Boiko wrote:
> On Friday, 11 May 2012 at 15:05:19 UTC, deadalnix wrote:
>> Le 11/05/2012 16:02, Roman D. Boiko a écrit :
>>> Technically, I'm trading N*0(1) operations needed to track line and
>>> column while consuming each character to M*0(log(n)) operations when
>>> calculating them on demand. N = number of characters, n is number of
>>> lines and M is number of actual usages of Location. My assumption is
>>> that M << N (M is much smaller than N).
>>
>> N can easily be number of tokens.
> Yes, if you are looking for the token by its index, not for location.
> E.g., for autocompletion it is needed to find the last token before
> cursor location. But that is not related to location search.
>
> Also please note that I oversimplified formula for complexity. It also
> has other components. My reply was just an additional minor comment.
> Motivation is design, not performance.
>
> One additional reason for such separation: with my approach it is
> possible to calculate Location both taking into account infromation from
> special token sequences, or ignoring it. How would you do that for eager
> calculation? Calculate only one category? Or track and store both?
>
> Unnecessary complexity will eventually find a way to shoot your leg :)
> Real-world usage (at least, anticipated scenarios) should be the basis
> for designing. Sometimes this contradicts intuition and requires you to
> look at the problem from a different side.

As deadalnix says, I think you are over-complicating things.

I mean, to store the column and line information it's just:

if (isNewLine(c)) {
   line++;
   column = 0;
} else {
   column++;
}

(I think you need to add that to the SourceRange class. Then copy line 
and column to token on the Lexer#lex() method)

Do you really think it's that costly in terms of performance?

I think you are wasting much more memory and performance by storing all 
the tokens in the lexer.

Imagine I want to implement a simple syntax highlighter: just highlight 
keywords. How can I tell DCT to *not* store all tokens because I need 
each one in turn? And since I'll be highlighting in the editor I will 
need column and line information. That means I'll have to do that 
O(log(n)) operation for every token.

So you see, for the simplest use case of a lexer the performance of DCT 
is awful.

Now imagine I want to build an AST. Again, I consume the tokens one by 
one, probably peeking in some cases. If I want to store line and column 
information I just copy them to the AST. You say the tokens are 
discarded but their data is not, and that's why their data is usually 
copied.