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

[Mike Krüger]

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 :)

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 don't know why you think it's not).

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).

> 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.

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. 

Regards
Mike