[Monodevelop-devel] Adding tracking spans in the MD text editor

[nikhil sarda]

On Tue, Apr 6, 2010 at 11:20 PM, Mike Krüger <mkrueger at novell.com> wrote:
> Hi
>
> *I want to move the discussion to the developer mailing list*
>
>> I had a talk with Michael Hutchinson on IRC regarding the new VS 2010
>> text editor features, such as the text markers, tracking spans and the
>> ITagger interface. I guess currently book keeping in the text editor,
>> like region folding, bookmarks and breakpoints are done using markers.
>> In VS 2010, changes in the text are exposed to tracking spans.
>> Basically you create a span over some text, and after the text has
>> changed, you can query the span for its status. They key difference is
>> that, unlike markers that are checked at each text change event, spans
>> are checked only when you require their status, ie lazy evaluation.
>
> Don't believe all of the ms marketing :)

I generally assume they know what they are talking about, but I'll be
careful next time :)

> Monodevelop doesn't update all 'markers' on on text change events ...
> Currently the stuff is stored in the line segments and the line segments
> are stored in a red-black tree. And on text change only a small part of
> the tree changes. The monodevelop text editor is the same in this regard

I did know about the line segment data structure, its used to
calculate the LOC in the code metrics.
I just had a vague recollection of it being stored in the RB tree.
Thing is I don't know how to keep a track
of changes in the line segment. Maybe theres a onLineSegmentChange
event, I don't know. The problem is
how do I narrow down to that *part* of the line segment that changed,
ie a word or phrase.

> (I don't know why you think it's not).

Ignorance? I'm still new to Mono, and I never claimed to know the text
editor internals :)

> And for any kind of markers a red-black tree could be used as well. I
> don't know what's so difficult in 'not updatating all markers' ... this
> is more or less 3rd semester computer science stuff what they're
> describing. 'Use a tree instead of an array.' I wonder if they stored
> their lines as an 'array' as well :).

> (Before you kill me - the region folding isn't stored in a red-black
> tree this one is currently stored as a 'folding tree' ... has to do with
> the way I get the data from the parser. This is something like a hybrid
> tree ... it contains links in the line segment red-black tree -
> therefore updating it is faster as the domino update effect the MS
> developers are fearing).

So would you suggest I create my own hybrid tree to keep track of text in the
text editor? For example, I wanted to keep track of text that violate
certain rules
so that I could add little squiggly lines under them. I could probably
create a tree
that stores the links to the line segments that I know violate the
rules. Thing is,
is there a way to highlight only that part of the line segment which
has the error?
AFAIK, whenever theres a parse error, the entire line gets highlighted
by a red squiggly.

>> This is being done by using snapshots of the text editor, which allow
>> you to go get the status of the span at each write. The way its being
>> done suggests that the underlying data structure is persistent.
>> Also of interest is the ITagger interface, which provides metadata for
>> text in a buffer. The tagger interface will make writing of spell
>> checkers and the quick-fixes part of my proposal very easy. Also as
>> the spans are immutable, you could probably use PLINQ on them to do
>> some awesome stuff. I would like to point your attention to two
>> articles
>>
>> http://blogs.msdn.com/noahric/archive/2010/01/28/new-extension-spell-checker.aspx
>> http://blogs.msdn.com/noahric/archive/2009/06/06/editor-perf-markers-vs-tracking-spans.aspx
>>
>> Do let me know of your plans with the text editor.
>
> This one is *much* more interresting - I do want to do it as well :).
> Snapshots are the way to go (I've too many 'background' thread problems
> and I too think that this is the best solution).
>
> The snapshot stuff I call 'piece table'. I've started to implement it to
> replace the buffer. The idea is that the current buffer state is always
> valid - even if the buffer changes. (But for multi threading you need a
> copy of the 'snapshot' in the other thread - but it's always valid). I
> want the snapshot system for the whole document.
> (this will make the undo/redo more easier to implement as well ... but
> it's only a side effect).
>
> It's something like:
> [DATA] <- [TABLE]
> And [DATA] only grows and [TABLE] contains the information how the
> [DATA] is puzzled together as text. [DATA] contains something like 2
> char arrays: one of the original file and one growing change buffer.
> Background threads now can use the current valid [TABLE] in their thread
> and it's always valid against the [DATA] - even if it changes.
>
> (Before anybody throws in 'memory hole' I want to throw in 'unlimited
> undo')
>
> Markers/Highlighting:
>
> And I want to do an own red-black tree for segments (aka. 'markers') for
> the highlighting. Currently the highlighting spans are a bit hacky.
> Doing this as an own tree would be much easier. And a tree for semantic
> highlighting tags as well. I think here something like the ITagger
> interface would work. Currently the highlighting is state less more or
> less ... the line segments contain the begin span stack. But I want to
> get rid of this hack and have an own span red-black tree instead.

I guess this answers my questions above?
Btw does this mean an RB Tree within an RB Tree?

> Overall I want to use more red-black trees in the text editor. Maybe
> even put all markers into an own one (but for many markers the line
> tagging works well and the line segments also aren't updated on each
> text change). Currently the piece table has some bugs (but it uses the
> same red-black tree than the current line segments, I haven't had the
> time/patience to track this yet).
>
> It's interresting that the vs.net developers and we are doing almost the
> same evolution - it's always good to know what the competitors are up
> to :)
>
> If anyone wants to help with the text editor data structures (or maybe
> have more proposals on doing things) - all input/help is welcome.

Um, make the text editor extensible through scripting? *ducks shoes*

> Regards
> Mike
>
>
Cheers
Nikhil Sarda