On Tue Mar 12 12:49:25 2024 +0000, Giovanni Mascellani wrote:
I am not I understand the question. The point of this and the previous loop is to make sure that intervals remain properly nested after `[begin, successor->order_pos)` is added. For the nesting property to be broken one of these two situations must happen:
existing interval: ---[------)------ candidate interval: -------[-----)---or
existing interval: -------[-----)--- candidate interval: ---[------)------Broadly speaking, the first loop cares about the first problematic situation and the second loop cares about the second one. In the first case we basically bring the candidate begin backward:
existing interval: ---[------)------ candidate interval: -------[-----)--- BECOMES existing interval: ---[------)------ candidate interval: ---[---------)---so the candidate interval now includes the existing one and they are properly nested. In the second case we need to modify the existing interval:
existing interval: -------[-----)--- candidate interval: ---[------)------ BECOMES existing interval: ---[---------)--- candidate interval: ---[------)------and again they're properly nested. This is admittedly a bit more delicate, because extending the existing interval we might in turn create a bad situation with a third interval. However that cannot really happen, because if that were the case this third interval would already been not properly nested with either the candidate or the existing interval (I can go into detail, if that helps). Another potential problem might be that the existing interval is a natural one, so its begin point cannot be touched. But again this cannot happen (if the input CFG is reducible), because it would mean that there is a jump that lands inside it without going through the begin point (which is the header). Hopefully this helps understanding these two loops. They are quite probably the most cryptic point in my structurizer, which is why I tried to be generous with comments. If you think this comment does a better job than the comments, I can use it to expand those.
I understand now. I'm on the fence about whether we need something like the above in comments. It may be a bit too much, but does make it clearer.