While working on Vy’s rendering, I checked different rendering examples with Vim. And I found a bug. Incredible. It is the first time of my life that I find a bug in vim, which is deemed super super stable.

The bug happens on gvim on windows, I haven’t tested on other versions of vim. To reproduce :

• Open an empty file
• Fill the file with more lines than vim can display (force it to scroll a bit)
• Scroll up, there should be some non visible lines below your current vim window
• Go to the last line of your screen
• Fill the line with the exact number of character that fit on screen
• Return to normal mode, stay on that last line
• Press A : your cursor is no longer visible.

What happens is that the cursor is no the next line, but vim forgot to scroll the view so that you see your cursor. Interestingly, when you filled the line, the cursor was visible all the time and vim scrolled the window correctly. This means that what happens when you press A is different from what happens when you are in the middle of the insert mode.

Because I am working on rendering, I have a good idea of why there is bug there. Vim editing mode has the particularity that the cursor is standing on a non-existing character, which is past the last character of the line. When editing in the middle of a window line, this is not a problem. When you are at the end of a line, this becomes interesting. At one point, the last character of the line is at the last character of the window line; so the cursor is displayed on the first character of the next line. That line does not exist in the buffer, and that character does not exist in the buffer.

That creates a big rendering question : should we create an empty rendering line on screen, to display the cursor on a line that does not exist ? That means that the rendering code must do more than take existing lines and split them into window lines: it must take existing lines, check for the cursor location, if the cursor is past the last character of the window line, extend the length of the line to render to create a new empty rendering line.

This also means that the rendering must be updated each time the cursor moves, instead of just when a character is added or modified.

This is a bit cumbersome and more importantly, it would trigger a rendering check each time the cursor moves. That’s a bit too often and is likely to cause flickers. Instead, the simple solution is not to update the rendering each time the cursor moves and handle the very specific case of when the cursor is sitting on a line that is not part of the buffer, just put the cursor on the next displayed line, which is actually the next buffer line. The simplification is reasonable. It also avoids a rendering in the case we fill up a window line with character. With correct rendering, there would be an scroll-down to display the cursor on the next empty window line, and then a scroll-up if the user presses ESC. With this simplified approach, no rendering is necessary in this case. The only drawback is that in some situations, the cursor disappears from screen during the typing of one character.

Vi and a few old-style editors have the characteristics that they wrap long lines, so that all parts of the lines are visible on screen. This is different from most modern or IDE editors, that let part of the line be hidden, and you have to scroll to the right to see the hidden part. For programming, I believe it is a saner choice to see the whole line on screen. When reading code, you want to grab the content of the line.

So, I am working on the line wrapping code of Vy. There is no syntax highlighting and I am using a fixed pitch font. So, the situation is quite simple, I need to break lines so that they fit on screen. I know the number of characters that fit on a screen line, I know how many characters a line have. Initially, I thought it would be quite simple. Actually, the first implementation is super simple. But then comes the small details that make it tricky.

Insert Cursor

In vi, in insert mode, the cursor can be on a non-existing character (when you press A for example). So, I have to look where the cursor is and add an extra character to some lines in a few specific situations. No big deal.

Tabs

Tabs depending on a config, can be 4 characters or 8 characters wide. But more importantly, a char is a single character that is rendered to multiple characters. I can have a line composed of 4 characters, which renders to 4×8 = 32 characters on screen. This makes the line-breaking really more complicated. It means that I can not compute the length of the screen line based on its character count. This has a big impact on the performance of the line breaking algorithm. With one character in the buffer equal one character on screen, rendering code is simple. For example, for a screen width of 80 characters, and a line of 100 characters, I can split the line at 80 and have a second line of 20 characters. But not with variable width characters such as tab.

One suboptimal algorithm for variable width characters is to start from an empty line, then add characters one by one, until the screen width of the line exceeds the width of the screen. However, this is really unefficient. For a reasonable editing window of 80 columns x 50 lines, filled by a lot of characters, it could mean up to 400 operations to display the lines on screen. That’s too much, especially if you consider that there are other possibilities.

The algorithm that I consider is to use a dichotomy: split the line at a good estimate of the length, check the number of tabs, calculate the width of the rendered split line, check if the line fits exactly in the screen and if not, look for another position. A dichotomy will work in every case, but I believe that for regular case of screen, where lines are mostly between 80 and 160 character wide, a little optimisation in finding the next point can diminish the number of operations to break the line correctly. In any case, pure dichotomy will find the length of the screen line in log(number of line characters) iterations, where naive algorithm would need (number of screen characters) iterations.

Cursor moving

Something is that I really underestimated is the work necessary to handle cursor moving. Cursor moves all the time, so this algorithm is called frequently. And cursor moving is trickier than line-breaking, because when the cursor moves, the screen window needs to scroll to follow the cursor. But it needs to scroll on the right screen line, which can be tricky to compute. For example, if I have a screen size of 10 columns x 5 lines (that’s small but who knows ?) and I display a text with lines of 35 characters each, moving the cursor around triggers many recalculation of which portions of which lines to display. Calculating that is not really difficult. What is difficult is calculating it in an efficient manner, so that there is a minimum of recalculations.

Special Case

Something that looks trivial but creates complication : how to represent an emtpy file ? And an empty line of a file ? Those are special cases which need special handling. My buffer is implemented as a list of line, each line containing the buffer line content excluding the \n . Now, an empty buffer is an empty list, or a list with an empty line ? When the cursor is on an empty line, it is actually on a character that does not exist in the buffer. Small details like this create lot of special cases.

Conclusion

We will see how I cope with all this. I am happy that I will have tests to help me, and python to code quickly. It will sure make my life easier.

I am working on the rendering engine of a Vy, a vi engine written in python.

The line rendering is a fundamental piece of text editor. The result of the rendering is the one thing that the user sees. If it is broken, or it looks ugly, the editor is not worth its line count: a programmer will spend hours, days and nights in front of its editor. He wants good rendering.

Another aspect is that rendering needs to be quick. Rendering occurs every time the programmer enters few characters, every time he adds or remove a line, every time he scroll his window. So basically, that’s all the time. If that’s slow, that’s impeding the programmer’s productivity, which is the opposite goal of an editor.

What is the proper way of dealing with a piece of code that must be good and quick, and that is the core of a functionality ? For me, the answer is simple. I need to isolate that piece of code from the rest of my code. And I need to test it! And test it again; as much as possible; from every possible angle.

Rendering can be complicated. There are lot of corner cases. So I need one test for every corner case, because I want to be sure that I handle all of them properly. And each time I see a bug for a corner case that I did not think of, I’ll write a new test.

Isolating rendering code is very important. In Yzis, the rendering is done inside paint events, so it is quite difficult to test and validate it. Wrong! The good approach that I am taking is to isolate the rendering code in a class. The rendering consists in taking a few inputs, the buffer content, the screen size, a few rendering options, and producing a representation of the final text with information on how to paint it on screen. In my case, that representation is a list of rendering lines, and a rendering line is a list of references to some text (the initial text) and attributes on how to draw this text. With such isolation, I can fully test my rendering. And painting it will be also simpler.

Optimizing the rendering is important. But optimization can not start before code isolation and testing. Once I have a piece of code that is isolated from the rest of my application, with a full test suite, I can start tweaking the code for optimization. Actually, I will never start by tweaking the code. My internal rules for optimization are:

1. Measure. I can not optimize anything if I don’t know how much time it takes. So, first step is to measure the operation I want to work on.

2. Build a usage scenario. I want to optimize for real use case, not for hypothetical use case. For example, a user can not type more than 20 characters in one second, but he can past 100 characters at once. That’s an important information to measure rendering performance. I will handle typing and pasting with a different algorithm.

3. Analyze. I want to analyze my code flow, I understand it. Why is action X done at step A and action Y done at step B ? Profiling can be a part of the analysis. But don’t reduce code optimization to profiling. Profiling is useless if you don’t know why you are doing some operation. In many cases, optimization is about changing the global code flow, not changing how a small part of it behaves.

4. Finally, Optimize. Work a new algorithm. Try out new stuff. I have my use cases, my analysis data, my test suite, I can try all the stuff I want. Computer science is a nice area where common sense and a few heuristics can perform better than the mathematically optimized solution. So I am checking my use cases to see if you can grab an extra trick where things will speed up in a often encountered situation, that is simpler to handle than the general situation.

In my case, the rendering is done in python. And python may be slow. So rendering code is the number one candidate for rewrite in C++. But before that, I will try many different algorithm, and I will measure, measure, measure. Because my rendering code is isolated in a class, at any time, I can substitute my python class with a C++ class and measure again. I will develop all my rendering algorithm in python. Python is easy to code and slow to execute. That’s the perfect environment for trying new optimization, and evaluate the impact of their results. When I know that an algorithm is working, I will probably recode it in C++. But not before I have the working and tested python version.

A very technical post as first post on my blog. I publish the solution to a problem that we encountered yesterday, in the hope that it will help others.

Windres is an utility part of mingw or cygwin, that one uses on Windows to compile and add resources to an executable. An example of resources are the application icon, or the version information. There are more types but this is usually the one we are concerned about.

Our windres generation line part of our cmake build process is here:

   ADD_CUSTOM_COMMAND( OUTPUT ${CMAKE_CURRENT_BINARY_DIR}/qyzis_ico.obj
                        COMMAND windres.exe
                            -I${CMAKE_CURRENT_SOURCE_DIR}
                            -o ${CMAKE_CURRENT_BINARY_DIR}/qyzis_ico.obj
                            -i${CMAKE_CURRENT_SOURCE_DIR}/qyzis_ico.rc
                        )
 

The problem we had was with path containing spaces. On windows, those are common beast. If you do a checkout on the desktop, the actual path of your checkout is C:\Document and vSettings\[User Name]\Desktop which contain spaces. If you run windres on a file in such a path, you get an error about gcc not finding the file. Why gcc while we are talking windres. The man page of windres gives the hint:

      --preprocessor program
          When  windres  reads  an  rc  file,  it  runs  it  through  the   C
          preprocessor  first.   This  option  may  be  used  to  specify the
          preprocessor to use, including any leading arguments.  The  default
          preprocessor argument is gcc -E -xc-header -DRC_INVOKED.

Oh, windres runs the rc files through the gcc preprocessor. But it does not quote them properly so gcc gets confused. We tried several combination of adding quotes and backslash to solve the problem, but it did not work. windres expects the filename unquoted and pass it like that to gcc.

Luckily, there is a way out of this. Two ways actually.

First solution :

There is a bug reported in the mingw bug tracker (I can find the reference now though) about this problem and a proposed fix. The bug has been closed and a fix is included in the mingw CVS. So, for the brave, you can recompile mingw and probably get rid or the problem.

Second solution :

The fix was quite trivial:

   ADD_CUSTOM_COMMAND( OUTPUT ${CMAKE_CURRENT_BINARY_DIR}/qyzis_ico.obj
                        COMMAND windres.exe
                            -I${CMAKE_CURRENT_SOURCE_DIR}
                            -o ${CMAKE_CURRENT_BINARY_DIR}/qyzis_ico.obj
                            < ${CMAKE_CURRENT_SOURCE_DIR}/qyzis_ico.rc
                        )
 

Instead of specifying a file path to windres, we just pipe the file through its standard input. Works like a charm. You can thank orzel for that solution.