Fighting Infinite Loops in the Writer Layout Engine

Some of you might already have encountered this very nasty sort of bug in OpenOffice.org. A crash is bad, but an infinite loop is even worse: You have to kill the process to be able to continue working. So how can such an infinite loop occur? Imagine this situation:

The graphic is anchored to the second paragraph and its wrap attribute is set to page wrap. What happens, if we set the vertical position of the graphic to -1cm from top? Take the current y position y ₀ of the second paragraph and set the position of the graphic to y ₀ - 1. This will yield a position somewhere in the first paragraph. Since the wrap attribute is set to page wrap, the first paragraph has to be re-calculated and because of the graphic, it will change its size. This in turn will cause the second paragraph to move down a bit. Hey, but the graphic wants to be only 1cm from top of the second paragraph. So we adjust the position of the graphic again. Therefore the first paragraph has to be calculated again... You see the point: the anchor position has an influence on the object position and the object position has an influence on the anchor position.

This is only a simple example of how a loop can occur. There are others, most of them caused by two ore more layout objects influencing each other. So, how can this situation be resolved? One solution might be to introduce a mediating instance that resolves such conflicts e.g. by suppressing invalidations. This of course requires some massive changes to the Writer layout engine and takes its time. Meanwhile a much more simpler approach has been taken with cws loopcontrol which has been integrated in SRC680m230. We analyzed the code to identify a couple of ‘fragile’ algorithms which are likely to cause problems. Then we have taken some very simple measures that drastically reduce the number of infinite loops:

we have added counter variables to some of the layout algorithms and break a loop after a certain number of iterations
an algorithm ends prematurely when a reoccurrence of certain layout states has been detected
we have implemented some functions that force the validation of some of the involved layout objects once an infinite loop has been detected

So, does this mean that each and every Writer layout engine infinite loop has been eliminated? No, not yet, but they definitely will occur less likely.

tags: openoffice.org writer