Am 30.09.2010 um 19:03 schrieb Richard Heck: > > The attached patch is an attempt to get a real start on fixing problems with > recursive includes. As you'll note, there are a couple places I know still > crash, but I wanted to see if anyone had a better idea. On this approach, we > basically have to make sure we NEVER try to recurse via Buffer::parent() or > even Buffer::masterBuffer(). Rather, what you do is call > Buffer::getAncestors() to get the list [parent, grandparent, etc] and then > call some routine on each of those. getAncestors() makes sure we don't run > into an infinite loop [A, B, A, B, etc], but if we have: A -> B -> A, then A > still thinks its ancestors are [B] and B thinks its are [A]. So even if > you've called getAncestors() to get that list, you must not call some routine > on each of them that itself tries to recurse via getAncestors(). Rather, that > must be a simple, one-buffer routine. > > This seems fragile, but I'm not sure what else to try. I had the idea that > somehow somewhere there might be a "global" record of Buffer inheritance, so > that e.g. we would not try to find the masterBuffer() each time by following > parent() but rather by looking at this global structure. But I don't know how > or where to implement that. In a way, maybe it isn't very hard. You'd only > need to update that structure when an InsetInclude is created or destroyed, > or---better---when a Buffer's parent is modified. I think. And of course the > structure itself could be created in much the way we find this information > now (we'd just have to do it for everything in the BufferList). > > Then again, clones will cause problems for that.... > > Thoughts?
There is a cool algorithm to detect infinite loops without global state: Use two pointers, start both somewhere at the same point. Increment the first by one, the second by two (if not hitting the end), until one of the conditions is true: 1. Stop if one of the pointers reach the end -> no infinite loop. 2. Stop if the second pointer meets the first -> loop detected! It's easy and fast. Stephan
