Highlighting matching brackets in code

Question

I've wanted to write my own portable IDE for CLisp for a while now and have recently started with it, using C#.

I have implemented bracket highlighting by checking if the current character is a bracket and then moving backwards/forwards throughout the text, whilst keeping track of the following opening/closing brackets until the number of opening and closing brackets are equal.

I have done this using simple for loops (also "break"-ing the for loop as soon as the matching bracket is found), but the method is slow on larger blocks of code. The method of highlighting text in the RichTextBox also seems a bit inefficient, i.e. selecting the characters by programmatically moving the cursor and applying a highlight, then deselecting and moving back to the cursor's original position. Moving away from the brackets requires the highlighting to be cleared, so I simply select all the text and then remove the formatting on it.

Occasionally the application can't keep track of where the cursor is supposed to be if the user moves the cursor too fast (using the arrow keys on the keyboard) and the application might erroneously move it back to a previous position. Simply put, the highlighting function I wrote can't keep up if the user scrolls through large blocks of code using the keyboard.

Is there a more efficient way of going about this other than for loops? Am I simply using inefficient methods to highlight and un-highlight the brackets? Could Regex offer a solution here?

While I wrote my piece of code myself, in essence I have done exactly what Bill The Lizard has done here: How do I find the position of matching parentheses or braces in a given piece of text?

Answer 1

I believe Regex will not help you here - in this case, it will probably be slower, since it still has to go through the code char by char.

However, there is a "simple" solution - create a tree of all the code blocks in the code, and update it as needed when the user changes the code (ideally, not on every keypress, but if done well, even that is an option). Then you no longer have to find the next bracket every time you move the cursor - you know in which code block you are (simple lookup by index), and you know immediately where the starting and ending bracket of the code is.

The approach assumes that updating the block indices is easy - and really, it kind of is; if the block is before the cursor as it updates, don't change it. If it's after the cursor, add numberOfCharsInserted to all the indices. Simple and fast. It becomes tricky as you add and remove new blocks of code, but that gives Visual Studio trouble as well :))

Another interesting solution might be a variant of "space partitioning". Split the code into sections you can easily index (for example, a binary tree or a hash table). If you remember the number of opening and closing brackets in each of these sections, you can quite quickly determine where the bracket you're looking for is located, and based on the section granularity, you can significantly reduce the are you have to search.

There's a lot of ways to optimize searching, but at some point, you simply have to go through the file from start to end. Based on typical use-cases, you have to choose the proper way. In this case, I believe simply remembering the indices of all brackets in the file will be by far the easiest solution, and it's pretty fast (How many characters are brackets out of the code? Adding 1 to a hundred indices is a lot faster than searching through a thousand chars. And you only have to do it while changing the code!). Although you did say LISP, didn't you? That could be a lot of brackets! :D