Bug 46905

That is a real shame that you will not have time to finish this, certainly looks like really good useful work :).  It will not be easy, but I really hope someone will be able to pick it up where you left off.

In the meantime, applied the patch locally, and started to look into the failing tests.

First observations:
- Very good starting point: refactoring the keep-logic based on a Keep object in the layoutengine that correlates to the KeepProperty in the FO tree definitely makes things a lot easier to read. The only thing that does not look entirely right IMO, is the addition of the methods to the BlockLevelLM interface. I think we can safely push it up to the LayoutManager interface, since it may prove handy in the longer term to fully implement inline-keeps as well. It is not yet possible, IIC, to keep two fo:inlines together on the same line. I'd make it an 'optional' method, so add an UnsupportedOperationException to the method signature for cases like BlockStackingLayoutManager (using IllegalStateException in the patch)
- I see only 9 failed tests here at first glance... Could be missing one (?)
- Re: the remark about the hacky nature of using the break-class of KnuthPenalty: 
How about creating a set of dedicated subclasses of KnuthPenalty (PageBreakPenalty, ColumnBreakPenalty...), rather than play with the base class member? That way, the parts of the code that use the base class can probably remain largely unaffected by the changes for now. Obviously, where necessary, we will then have to take care to instantiate the correct types of penalty, but it could ultimately lead to code that is easier to read
The class hierarchy could reflect the real relationship between the different break-opportunities: 
a PageBreakPenalty is a ColumnBreakPenalty, which is a LineBreakPenalty, which is a special type of KnuthPenalty?

OK, enough ranting, back to investigating the failing testcases.

(In reply to comment #0)

> * the deferring mechanism may also conflict with regular node recovery
> (restarting from the last deactivated/too short/too long node when the number
> of active nodes falls to zero). See commented out code in BreakingAlgorithm.
> It's not clear yet what may happen when.

Not sure if I interpret it entirely correctly, but the effects seemed to show in the (alphabetically) first failing testcase, where the algorithm chooses a layout with less lines, in spite of the fact that the last line is too long.
So, I naively tried uncommenting that bit, and that brings the number of failures down to 7. Is that expected?

(In reply to comment #0)
> * keeps have been implemented such that a keep.within-line implies a
> keep.within-column, which implies a keep.within-page. This is almost always
> true except if, for example, keep.within-page is set to always and
> keep.within-column to an integer value. The integer value from the column
> component will override the always value from the page component, possibly
> leading to an 'illegal' page break.

Are you referring to case block_keep-with-next_integers_1 here?

If so, the most straightforward solution seems to be a change in the implementation of Keep.compare(). First check whether either keep is forced before doing the rest. 
In the patch, BlockStackingLM.getKeepTogether() will return the parent's keep-together if it has a lower priority. That is definitely incorrect if the child's keep is forced.

Roughly:

        /* check forced keep first, regardless of priority */
        if (strength == STRENGTH_ALWAYS) {
            return this;
        } else if (other.strength == STRENGTH_ALWAYS) {
            return other;
        }
        
        int pThis = getKeepContextPriority(this.context);
        int pOther = getKeepContextPriority(other.context);

        /* equal priority: strongest wins */
        if (pThis == pOther) {
            return (strength >= other.strength) ? this : other;
        }

        /* different priority: lowest priority wins 
          * (line wins over column wins over page)
          */
        return (pThis < pOther) ? this : other;

would make only 6 failing tests here (provided the two fixed by the uncommenting weren't a fluke)

(In reply to comment #4)

Previous remark was not entirely correct, yet...

Fact remains: if the child's keep has a higher strength than the parent keep, it should win. If we have a keep.within-line="5" and a nested keep.within-column="10", the inner keep should 'win'. Following the changes in the patch, we would always get the line-context keep, and won't even consider the other. This is still so after the additional changes I proposed earlier.

If a line-context keep is specified on a node, a page-context keep, no matter how deeply nested, should still be honored if it is stronger. This is especially the case for forced keeps, but also for integers (see above). I read: keep the inline content together in a line, if possible. If it isn't possible, we may break into multiple lines (since the keep is not absolute), but still there is a higher preference for keeping at least part of the content together within a column. If we insert a line-break somewhere within that part, the break should preferably not be considered as a column-break.

Next batch of 3 failing tests concerns the impact of the changes on the footnote-splitting mechanism. 
The PageBreakingAlgorithm (PBA) no longer includes the first part on the first page. That is: the break after the line containing the footnote-citation for the footnote that should be split, is no longer considered to be a feasible break. 

Taking the first test footnote_changing-page-bpd-2.xml as reference case.

In the initial pass over the footnote list in PBA.computeDifference(), both PBA.checkCanDeferOldFootnotes() and PBA.newFootnotes evaluate to false, so we do not even try PBA.getFootnoteSplit() to see how many lines of the footnote fit on the first page.
The reason for newFootnotes being false (even though there are definitely footnotes):
BreakingAlgorithm.findBreakingPoints() (line 463) will trigger handleBox() for the last line-box, which will trigger handleFootnotes(), which will set newFootnotes to true. Following that, we have a penalty, which will be considered as a legal break, but elementCanEndLine() returns false. PBA.considerLegalBreak() returns, sets newFootnotes to false, so that when we consider the next, finishing penalty, it will be as if there are no footnotes.
Since the total of the body content and the entire footnote does not fit into one page, considerLegalBreak() deactivates the node, and the algorithm restarts from that position further on.

(In reply to comment #3)
> (In reply to comment #0)
> 
> > * the deferring mechanism may also conflict with regular node recovery
> > (restarting from the last deactivated/too short/too long node when the number
> > of active nodes falls to zero). See commented out code in BreakingAlgorithm.
> > It's not clear yet what may happen when.
> 
> Not sure if I interpret it entirely correctly, but the effects seemed to show
> in the (alphabetically) first failing testcase, where the algorithm chooses a
> layout with less lines, in spite of the fact that the last line is too long.
> So, I naively tried uncommenting that bit, and that brings the number of
> failures down to 7. Is that expected?

(Sorry for the delay.)

I had to comment that part because it was preventing the PageBreakingAlgorithm.recoverFromTooLong method from properly working. Instead of taking as lastTooLong the node that overflows the second column because of page-unbreakable content, it would take the node that overflowed the first column, and that was deactivated following the normal process of the algorithm. That doesn't mean that the first column can't be laid out, just that starting from that node no content could be squeezed into the first column any more. That piece of code needs to be re-enabled and collaborate nicely with recoverFromTooLong.

(In reply to comment #7)
> (Sorry for the delay.)

(Me too ;-))

> 
> I had to comment that part because it was preventing the
> PageBreakingAlgorithm.recoverFromTooLong method from properly working. Instead
> of taking as lastTooLong the node that overflows the second column because of
> page-unbreakable content, it would take the node that overflowed the first
> column, and that was deactivated following the normal process of the algorithm.
> That doesn't mean that the first column can't be laid out, just that starting
> from that node no content could be squeezed into the first column any more.
> That piece of code needs to be re-enabled and collaborate nicely with
> recoverFromTooLong.

So.. the implementation, without comments, uses the last deactivated node as lastTooLong, but since the (Page)BreakingAlgorithm is actually not breaking pages but columns, this turns out to be the last deactivated column-break node, instead of a page-break node.

Maybe it's a matter of checking the node, before deactivating. IOW: never deactivate column-breaks, so the algorithm always restarts from the last page-break (?)
Then again, this could get messy, given that changes in BreakingAlgorithm also influence line-breaking, where the distinction is irrelevant. 
The cleanest solution is probably to override compareNodes() in PageBreakingAlgorithm, so it always returns the last true page-break, rather than the last (plain) break. The default implementation in BreakingAlgorithm simply returns the break with the last position (or the one yielding the best demerits in case of equal position). If overridden, the later break can then be deactivated, but not stored as lastDeactivatedNode.

(OK, finally back in shape to continue working on this, and some progress in the meantime...)

Re: the issue with the failing footnote tests

I have found the cause for those failures. There seems to be a logic error in the subtle change in BreakingAlgorithm.findBreakingPoints(), where penalties are handled: after the change, a penalty is considered as a legal break if the penalty value is lower than INFINITE or it is not of class EN_LINE. 
This is wrong. Regardless of the break class, a penalty with that value is *never* to be considered as a legal break.

Removing that part of the condition makes the failing footnote tests pass. I'm just a bit uncertain what the precise motivation was to add that one... so I hope I'm not missing anything here.

(OK, finally back in shape to continue working on this, and some progress in the meantime...)

Re: the issue with the failing footnote tests

I have found the cause for those failures. There seems to be a logic error in the subtle change in BreakingAlgorithm.findBreakingPoints(), where penalties are handled: after the change, a penalty is considered as a legal break if the penalty value is lower than INFINITE or it is not of class EN_LINE. 
This is wrong. Regardless of the break class, a penalty with that value is *never* to be considered as a legal break.

Removing that part of the condition makes the failing footnote tests pass. I'm just a bit uncertain what the precise motivation was to add that one... so I hope I'm not missing anything here.

Next failing test was inline_block_nested_6. I have investigated that closer, and after the changes the global element list on the one hand contains more elements than before. On the other hand, the penalties appear earlier in the list. I still have to check whether this has undesired consequences, but it seems like the produced output is identical. This may be a case of having to adapt the testcase, and change the expected results.

Remaining failing testcases are related to tables. 
For table-row_keep-together.xml, the reason is that, before the changes in the patch, we generated one consolidated box for 2 lines (due to the keep). After the changes, we generate two boxes, plus a penalty with break-class EN_PAGE to allow the row to break over multiple columns.

Similar thing happens for table_keep-together.xml.

Still two hyphenation testcases to look at...

Hi Andreas,

(In reply to comment #10)
> (OK, finally back in shape to continue working on this, and some progress in
> the meantime...)
> 
> Re: the issue with the failing footnote tests
> 
> I have found the cause for those failures. There seems to be a logic error in
> the subtle change in BreakingAlgorithm.findBreakingPoints(), where penalties
> are handled: after the change, a penalty is considered as a legal break if the
> penalty value is lower than INFINITE or it is not of class EN_LINE. 
> This is wrong. Regardless of the break class, a penalty with that value is
> *never* to be considered as a legal break.
> 
> Removing that part of the condition makes the failing footnote tests pass. I'm
> just a bit uncertain what the precise motivation was to add that one... so I
> hope I'm not missing anything here.

The idea was that a penalty of value infinite and class EN_PAGE become a penalty of value 0 when considering a column break. Like I said in my first comment this is very hacky and needs to be improved. All the more than the actual value may not always be zero (e.g. when breaking the column at a hyphenated word).

Vincent

(In reply to comment #13)

Hi Vincent,

> The idea was that a penalty of value infinite and class EN_PAGE become a
> penalty of value 0 when considering a column break.

Aaah... of course, now I get it.

The general idea is obviously:
keep-*.within-line => infinite penalty of class EN_LINE, should result in the break never being considered as a legal break.
keep-*.within-column => infinite penalty of class EN_COLUMN, should result in the break being considered as a legal line-break, but not a page- or column-break
keep-*.within-page => infinite penalty of class EN_PAGE, should result in the break being considered as line- or column-break, but not as a page-break

> Like I said in my first comment this is very hacky and needs to be improved. 
> All the more than the actual value may not always be zero (e.g. when breaking the 
> column at a hyphenated word).

Indeed. On top of that, there are the 'terminating' sequences of penalty-glue-penalty that we use for the filler space after the last break. Since the breakClass for the first penalty in that sequence remains unset (= -1), it is also considered as a legal break (getBreakClass() != EN_LINE), while it is precisely meant to prevent any break before the filler glue.

(In reply to comment #12)
> Still two hyphenation testcases to look at...

Spent quite some time today trying to figure out what was causing those to fail. Turned out to have nothing to do with the patch, but with other unrelated changes I had made locally... :/

I have addressed the change mentioned in comment #10 by adding a check for a break-class of -1 to the condition, so such penalties are no more considered as a legal break.

Now that all tests pass, all that's left is to start some improvements and add the testcases. For the moment, the improvements can be kept down to a minimum, since with some minor modifications, it seems to be working nicely already. The only case that is still not correctly processed is the one mentioned in the beginning (see description mentioned by Vincent): if we have a block with keep-together.within-column="5" and a nested block with keep-together.within-page="10", the inner block is still split over multiple pages. Maybe, this situation is solvable by adding 'hinting' penalties (with negative values) before the inner block, which would make a page-break before or after better than a break inside that block. Remains to be seen whether this will work as expected, as I remember a test Luca Furini did once, where he demonstrated that the effect of the penalties' values is marginal on the total demerits, unless the difference is big enough (?)

More later.

(In reply to comment #15)
> (In reply to comment #12)
> > Still two hyphenation testcases to look at...
> 
> Spent quite some time today trying to figure out what was causing those to
> fail. Turned out to have nothing to do with the patch, but with other unrelated
> changes I had made locally... :/
> 
> I have addressed the change mentioned in comment #10 by adding a check for a
> break-class of -1 to the condition, so such penalties are no more considered as
> a legal break.
> 
> Now that all tests pass, all that's left is to start some improvements and add
> the testcases. For the moment, the improvements can be kept down to a minimum,
> since with some minor modifications, it seems to be working nicely already. The
> only case that is still not correctly processed is the one mentioned in the
> beginning (see description mentioned by Vincent): if we have a block with
> keep-together.within-column="5" and a nested block with
> keep-together.within-page="10", the inner block is still split over multiple
> pages. Maybe, this situation is solvable by adding 'hinting' penalties (with
> negative values) before the inner block, which would make a page-break before
> or after better than a break inside that block. Remains to be seen whether this
> will work as expected, as I remember a test Luca Furini did once, where he
> demonstrated that the effect of the penalties' values is marginal on the total
> demerits, unless the difference is big enough (?)

This won't work. If keep-together.within-column="1" and keep-together.within-page="always" then a break must be completely forbidden at a page. Hinting penalties won't prevent that in every case, for example if the only feasible page break is at such a place. In that situation the node recovery mechanism must be launched, and an earlier too-short/long node selected.

Vincent

(In reply to comment #16)
> This won't work. If keep-together.within-column="1" and
> keep-together.within-page="always" then a break must be completely forbidden at
> a page. Hinting penalties won't prevent that in every case, for example if the
> only feasible page break is at such a place.

OK, I thought so...

I had this working for strength "always", with the modified implementation for Keep.compare() I suggested earlier (comment #4). Anyway, that case is easy. The more complicated case is keep-together.within-column="1" and on a nested block .within-page="10". Both column-breaks and page-breaks are allowed, but the page-breaks should preferably be made before/after the nested block. A page-break in the nested block would be permitted only if its content does not fit into one page.

> In that situation the node recovery mechanism must be launched, 
> and an earlier too-short/long node selected.

As far as I can tell, we currently only remember the last deactivated node. As soon as we deactivate another node, either it will replace that one (if it produces better demerits) or it is just disregarded completely (after my modifications: if the deactivated node does not end a page, PBA.compareNodes() will return the preceding page-break, so that the column-break node is deactivated but not used as the point from which to restart later on).

If I interpret that remark correctly, then either we have to remember more deactivated nodes in order to be able to select an earlier one, or we should make sure (somehow?) that the nodes for the breaks before/after the nested block produce better demerits than those corresponding to page-breaks within that block...

Another question-mark: if the keep-constraints would lead to a break mid-column, would end-users expect column-balancing to be applied to the part before the page-break...? Currently not trivial to implement, if I judge correctly. I'll first see if I can get it working without column-balancing, and add this later.

(In reply to comment #17)
> (In reply to comment #16)
> > This won't work. If keep-together.within-column="1" and
> > keep-together.within-page="always" then a break must be completely forbidden at
> > a page. Hinting penalties won't prevent that in every case, for example if the
> > only feasible page break is at such a place.
> OK, I thought so...
> I had this working for strength "always", with the modified implementation for
> Keep.compare() I suggested earlier (comment #4). Anyway, that case is easy. The
> more complicated case is keep-together.within-column="1" and on a nested block
> .within-page="10". Both column-breaks and page-breaks are allowed, but the
> page-breaks should preferably be made before/after the nested block. A
> page-break in the nested block would be permitted only if its content does not
> fit into one page.

I think it is an acceptable limitation that keep-*.within-column works only for "always" It is already a big improvement on the current situation where this is treated as keep-*.within-page.

<snip/>

Created attachment 23799 [details]
sample file; basis for a simple testcase

I have been running some more tests with the attached sample file, relatively simple.

So far, all seems to work as expected --as long as there are only 2 columns.
As soon as I increase it to 3 or more, the algorithm picks the wrong node somehow... currently looking into that.

I will post the changed patch, and attach PDF results for reference shortly.

(In reply to comment #19)
> Created an attachment (id=23799) [details]
> So far, all seems to work as expected --as long as there are only 2 columns.
> As soon as I increase it to 3 or more, the algorithm picks the wrong node
> somehow... currently looking into that.

A hunch right after posting this, checked PageBreakingAlgorithm.recoverFromTooLong(), and thought I'd change the first while-loop to:

while (!pageProvider.startPage(lastTooLong.line))

i.e. do not subtract 1 from the line-number

Now, it already works for three columns, but crashes on four... :-(

Seems to be pointing to an issue when having to restart from the first node (whose previous node is null)

Created attachment 23800 [details]
Result w/ 2columns

Created attachment 23801 [details]
Result w/ 3 columns

Created attachment 23802 [details]
Result w/ 4 columns

Comparing this to the 3-column version, I shortened block-2 in the example to fit in one column, and then there's no interference/confusion with the normal recovery mechanism.

(In reply to comment #20)
> A hunch right after posting this, checked
> PageBreakingAlgorithm.recoverFromTooLong(), and thought I'd change the first
> while-loop to:
> 
> while (!pageProvider.startPage(lastTooLong.line))
> 
> i.e. do not subtract 1 from the line-number

Undid this change, for the moment, since it causes more trouble than it solves.

While debugging further, I notice it is indeed a problem when the algorithm 5-restarts from the first node.
Apparently, restarting from that first node (way too-short) triggers area-addition for the first line on the first page, then we get an effective page-break, and the rest is rendered as it would otherwise be rendered.

Still looking closer at the trace-logs to try and make sense of it...

Maybe a somewhat exceptional case, but I'd still like to see if I can fix that one before publishing the patch.

Some more progress: the undesired behavior is also eliminated in case all of the columns of the first page are occupied.
Trying to explain this a bit better, if you look at the sample result with 3 columns, the behavior is triggered because the block with id 'block-1' occupies only 1 column and a part. If we make it 2 columns plus some more, the following block is correctly moved to the next page, where it overflows the first column. In the current state, the column-break nodes will be deactivated, but priority will be given to the first page-break, which is the one that is remembered as the restart point. Strictly speaking not incorrect, but PBA.recoverFromTooLong() creates a node that turns an illegal break (in between two boxes, always to be kept together due to widows/orphans) into a feasible one. Then it appends a few more for the column-break nodes. Commenting out the specialized recoverFromTooLong(), it works neatly for the first case, but still produces incorrect results for the third case (integer keep.within-column with nested forced keep.within-page).

Closing in on completing this one. A real challenge, I must say... Just writing out some observations, as it generally helps me get closer to the solution (even if nobody replies ;-))

Diving deeper and deeper into the layout-loop: from the point of view of the page-breaking, the code in BreakingAlgorithm is really, really misleading. considerLegalBreak() contains a loop, but in practice, the body of the outer for-loop is always executed only once. There's a number of those hidden throughout the codebase, IIRC: judging purely from the code, you can hardly keep track of the nesting. When debugging the same code, you suddenly realize that those are all pseudo loops...
The difference between startLine and endLine is always exactly one. 
The basic process seems to be: 
- try adding another line, 
- compute adjustment ratio/difference/demerits, and 
- if the line does not fit, recover by considering the lastTooShort node as the definitive break.

Does not really sound so 'total-fit' to me. Earlier breaks are never revisited. For the duration of the main loop in findBreakingPoints(), there is always at most one node active. If the last node is too long, it is removed and the recovery mechanism comes into play.

What it means in terms of page-keeps nested in column-keeps, is that the node corresponding to the break before the keep-context switch will have been discarded, since it was too-short. There is no way to get that node back, apart from going back to the first preceding penalty in a different keep-context and recreating it. Either that or...
Using some additional overrides in PageBreakingAlgorithm to keep track of the keep-context and remember that node brought me very close to a solution, but it still causes unwanted side-effects in other cases.

Created attachment 23863 [details]
sample testcase


Modified the sample file into a full testcase, checking the simplest cases and some combinations of keep-together with keep-with-previous or -with-next.

Currently, in my sandbox, the test passes, but the changes still break a few other tests, so first have to find out why exactly...

Together with this change, I also did quite a bit of restructuring in BreakingAlgorithm, with the benefit of giving subclasses multiple hooks to insert overrides and reducing the 'main loop' in findBreakingPoints() to fit on one screen...

Created attachment 23864 [details]
sample PDF result for the testcase (5 columns)

Created attachment 23865 [details]
diff of the changes, so far...

As indicated earlier, the changes in the patch still cause some issues with around 20 testcases. Just thought I'd post it for review to see if everyone is OK with some of the refactoring.

Basically, the most important changes in that respect are localized in BreakingAlgorithm, where I extracted some of the code blocks in the main loop in findBreakingPoints() into protected methods, offering hooks for subclasses to inject custom behavior. An implementation may choose to treat penalties differently than the basic algorithm does; the implementation of handlePenaltyAt() in PageBreakingAlgorithm can serve as an example.

Change with respect to the previous patch: PageBreakingAlgorithm keeps track of the current keep-context, and the last too-short node before the context changed. If the keep-context is not AUTO, then PBA will restart from that too-short node, instead of using the superclass' implementation of recoverFromTooLong(). Then we add nodes after that node, until all the columns in that page are occupied. Since we do not yet implement changing IPD (hence no change in column-count), I have explicitly chosen to defer only the overflowing part to the next page, for the sake of simplicity. The silent assumption is that the next page will have the same number of columns, so deferring the first part as well is pointless... Best case showing that effect is block-4 in the sample: we only defer the content of the block that must be kept within one-page (starting with "[BOB-4a] ...").

Created attachment 23886 [details]
sample PDF result showing a remaining issue

Further testing and digging revealed that the last attached FO/PDF sample contains a fluke... 
If I lengthen the nested block-4a so that it causes a page-level overflow, none of the breaks in the last column will be considered/registered as feasible (page-)breaks. As a consequence, the next restart is triggered from the last column-break. An additional node is inserted to fill the last column, and the remainder is pushed to the next page, while it should actually just overflow the column/page. Since the last part is also run through the column-balancing algorithm, I end up with suboptimal break-decisions...

For the rest, in the meantime, I have made a few more modifications to the last patch, so am now down to four failing testcases (five, when including the above). Will post an updated patch later today.

Hi Andreas,

(In reply to comment #29)
> Created an attachment (id=23865) [details]
> diff of the changes, so far...
> 
> As indicated earlier, the changes in the patch still cause some issues with
> around 20 testcases. Just thought I'd post it for review to see if everyone is
> OK with some of the refactoring.
> 
> Basically, the most important changes in that respect are localized in
> BreakingAlgorithm, where I extracted some of the code blocks in the main loop
> in findBreakingPoints() into protected methods, offering hooks for subclasses
> to inject custom behavior. An implementation may choose to treat penalties
> differently than the basic algorithm does; the implementation of
> handlePenaltyAt() in PageBreakingAlgorithm can serve as an example.
> 
> Change with respect to the previous patch: PageBreakingAlgorithm keeps track of
> the current keep-context, and the last too-short node before the context
> changed. If the keep-context is not AUTO, then PBA will restart from that
> too-short node, instead of using the superclass' implementation of
> recoverFromTooLong(). Then we add nodes after that node, until all the columns
> in that page are occupied. Since we do not yet implement changing IPD (hence no
> change in column-count), I have explicitly chosen to defer only the overflowing
> part to the next page, for the sake of simplicity. The silent assumption is
> that the next page will have the same number of columns, so deferring the first
> part as well is pointless... Best case showing that effect is block-4 in the
> sample: we only defer the content of the block that must be kept within
> one-page (starting with "[BOB-4a] ...").

I've had a quick look at your patch. I have 2 small comments:
- there are two compilation errors: one in KnuthPenalty about an unknown PENALTY_TYPE constant, one in PageBreaker, l.421, trying to convert a List into a LinkedList (that one is easily fixed).
- I think you can commit the changes that are clean-up 'only' right now. They are improving the code readability quite a bit.

And a bit of nit-picking:
- in BlockStackingLM: in the getKeep*Property methods, I chose to throw IllegalStateExceptions because the only LMs that don't override those methods are LMs to which keeps don't apply. So calling those methods on such LMs is a genuine programming mistake, and not a TODONotYetImplementedException.
- there's no reason to make the PageBreakingAlgorithm class public
- in PageBreakingAlgorithm.createFootnotePages: tmpLength can be declared inside the while loop
- I see you changed the 'while (iter.hasNext())' loops into 'for (Iterator iter = list.iterator(); iter.hasNext();)' and... I just wanted to say that it's great ;-)

I'll try to have a look at the bigger changes in [Page]BreakingAlgorithm later on.

Thanks,
Vincent

(In reply to comment #31)

Hi Vincent,

> I've had a quick look at your patch. I have 2 small comments:
> - there are two compilation errors: one in KnuthPenalty about an unknown
> PENALTY_TYPE constant, one in PageBreaker, l.421, trying to convert a List into
> a LinkedList (that one is easily fixed).

Hmm, sorry about those... The missing constant was an experiment of mine, to see if we could follow a similar approach as for FONode here. Instead of the fixed isBox(), isGlue() and isPenalty(), we would get something like getElementType() and isElementType(int). Undid this change for the moment, but it seems I forgot to clean up after that. The change would only make sense if we would consider adding new types of elements. In that case, we probably won't want to change KnuthElement every time to add yet another isXXX() method.
The latter one I noticed earlier today, too. It was a more general change: if we do not need the LinkedList functionality, we can just as well use the List interface.

> - I think you can commit the changes that are clean-up 'only' right now. They
> are improving the code readability quite a bit.

Good! That's the intention. Just making sure that future contributors will spend less time trying to understand the code. The goal is to make it (almost) readable by a child. ;-)

> And a bit of nit-picking:
> - in BlockStackingLM: in the getKeep*Property methods, I chose to throw
> IllegalStateExceptions because the only LMs that don't override those methods
> are LMs to which keeps don't apply. So calling those methods on such LMs is a
> genuine programming mistake, and not a TODONotYetImplementedException.

Initially, I had pushed the getKeep*Property() method up to the LayoutManager interface, and wanted to use a similar pattern as some standard Java interfaces. The subclass can choose to implement it, but if it does not, it is allowed to signal this with an UnsupportedOperationException. It would indeed be a mistake, just like it is a mistake to call remove() on an arbitrary Iterator, because remove() is an optional operation. A concrete iterator is not obliged to implement it, and if it doesn't, it should throw an exception. Whether it's an IllegalStateException or an UnsupportedOperationException is really all the same to me. Both are unchecked runtime exceptions. Just found the latter more appropriate...

> - there's no reason to make the PageBreakingAlgorithm class public

Good catch! A reminder for me to try to get around to finishing the fo:inline-container implementation. The origin of that change is that an InlineContainerBreaker would need to have access to the PBA, from within the layoutmgr.inline package.

> - in PageBreakingAlgorithm.createFootnotePages: tmpLength can be declared
> inside the while loop

No idea whether it's still relevant, but I always tend to avoid stuff like:

while (someCondition) {
  int intVar = intValue;
  ...
}

Instead, use:

int intVar = -1;
while (someCondition) {
  intVar = intValue;
  ...
}

which, I guess, is almost equivalent to:

while (someCondition) {
  final int intVar = intValue;
  ...
}

apart from the fact that the variable is available outside of the loop.
IOW: loop only the assignment, not the declaration. There really is no reason to declare (=allocate space for) a new variable on every iteration. Maybe using the final modifier would work here too, since we don't need the variable scoped outside of the loop...

> - I see you changed the 'while (iter.hasNext())' loops into 'for (Iterator iter
> = list.iterator(); iter.hasNext();)' and... I just wanted to say that it's
> great ;-)

Cool! :-)

> 
> I'll try to have a look at the bigger changes in [Page]BreakingAlgorithm later
> on.

OK, thanks for the feedback so far!

Andreas

Created attachment 23916 [details]
updated patch (minus the already committed cleanups)

Updated patch, as mentioned, without the cleanups already committed in r790142 and r790166.

Currently, down to one failing testcase (but that's actually two, when taking into account that the added testcase keep_within-column_basic.xml will fail if we make the nested block 4-a overflow the page).

OK, /almost/ there. All existing testcases pass now. The cause of the last failed testcase (region-body_column-count_3.xml), had something to do with PageBreaker.handleBreakTrait(). 
Since the keep-implementation causes generation of KnuthPenalty elements with a break-class "auto", it is now possible for the condition at line 474 to evaluate to true, but then further on, on line 483 the breakVal is not -1 as it used to be, so the check returns false and we generate a new flow for the second column, instead of a whole new page.

Will post the updated patch asap.

Afterwards, I think we may just as well go ahead and commit. After all, the failing added test is not a very common use-case, and could, for the moment, be noted as a known limitation.

Hi Andreas,

(In reply to comment #32)
> (In reply to comment #31)
> 
> Hi Vincent,
> 
<snip/>
> > And a bit of nit-picking:
> > - in BlockStackingLM: in the getKeep*Property methods, I chose to throw
> > IllegalStateExceptions because the only LMs that don't override those methods
> > are LMs to which keeps don't apply. So calling those methods on such LMs is a
> > genuine programming mistake, and not a TODONotYetImplementedException.
> 
> Initially, I had pushed the getKeep*Property() method up to the LayoutManager
> interface, and wanted to use a similar pattern as some standard Java
> interfaces. The subclass can choose to implement it, but if it does not, it is
> allowed to signal this with an UnsupportedOperationException. It would indeed
> be a mistake, just like it is a mistake to call remove() on an arbitrary
> Iterator, because remove() is an optional operation. A concrete iterator is not
> obliged to implement it, and if it doesn't, it should throw an exception.
> Whether it's an IllegalStateException or an UnsupportedOperationException is
> really all the same to me. Both are unchecked runtime exceptions. Just found
> the latter more appropriate...

That's two different things. remove() is semantically correct on an Iterator; the fact that some iterators don't support it really is an implementation limitation, and UnsupportedOperationException is applicable here. In the case of LayoutManager, getKeep*Property shouldn't even be defined in that interface, since not all descendants accept keep properties. For example, keeps make no sense on an fo:static-content element. Calling the keep methods on its corresponding StaticContentLayoutManager therefore is an error in the logic, not an implementation limitation issue.

Actually, those methods shouldn't even be declared on those layout managers for which they are not applicable. That way it wouldn't even be possible to make a logic error. Unfortunately that implies changes in the class hierarchy that are beyond the scope of this patch.


<snip/>
> > - in PageBreakingAlgorithm.createFootnotePages: tmpLength can be declared
> > inside the while loop
> 
> No idea whether it's still relevant, but I always tend to avoid stuff like:
> 
> while (someCondition) {
>   int intVar = intValue;
>   ...
> }
> 
> Instead, use:
> 
> int intVar = -1;
> while (someCondition) {
>   intVar = intValue;
>   ...
> }
> 
> which, I guess, is almost equivalent to:
> 
> while (someCondition) {
>   final int intVar = intValue;
>   ...
> }
> 
> apart from the fact that the variable is available outside of the loop.
> IOW: loop only the assignment, not the declaration. There really is no reason
> to declare (=allocate space for) a new variable on every iteration. Maybe using
> the final modifier would work here too, since we don't need the variable scoped
> outside of the loop...

The 'declaration' only applies at compilation time, and is used to perform type checking. At runtime there is no space allocated whatsoever. A value is simply pushed onto the operand stack [1]. Actually, declaring the variable outside the loop results into more boilerplate bytecode, so technically is less efficient (although very probably unnoticeable). OTOH, declaring the variable inside the loop is cleaner and safer (no risk to mistakenly use it outside the loop).

[1] http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.html#28851


<snip/>

Vincent

(In reply to comment #35)
> <snip/>
> > Whether it's an IllegalStateException or an UnsupportedOperationException is
> > really all the same to me. Both are unchecked runtime exceptions. Just found
> > the latter more appropriate...
> 
> That's two different things. remove() is semantically correct on an Iterator;
> the fact that some iterators don't support it really is an implementation
> limitation, and UnsupportedOperationException is applicable here. 

I don't see the difference. Seems to be in your head... :-)

> 
> The 'declaration' only applies at compilation time, and is used to perform type
> checking. At runtime there is no space allocated whatsoever. 

OK, good to know. I'll go for the declaration inside the loop, with the final modifier.

(In reply to comment #36)
> > <snip/>
> > > Whether it's an IllegalStateException or an UnsupportedOperationException is
> > > really all the same to me. Both are unchecked runtime exceptions. Just found
> > > the latter more appropriate...
> > 
> > That's two different things. remove() is semantically correct on an Iterator;
> > the fact that some iterators don't support it really is an implementation
> > limitation, and UnsupportedOperationException is applicable here. 
> 
> I don't see the difference. Seems to be in your head... :-)

Thought about it some more, and the above argument is moot. An UnsupportedOperationException does not necessarily mean that it is a limitation, in the sense that the implementation is not complete. For some iterators, for example one over a list returned by Collections.unmodifiableList(), it is an error if it implements the remove() operation.

Created attachment 23990 [details]
Yet another update


Had hoped to get to this sooner, but it seems that at some point when getting the existing testcases to succeed, I made a change that, again screwed up the nested column/page keep test in the attachment. Took me a while to track it down.

The way the algorithm operates, after the changes in the previous patch, is that in block-4 in the sample, we get the effect that the overflow condition for the first page will be detected at the first break after the nested block-4a (mentioned in comment #1 as something to watch out for). This means that my devised strategy of keeping track of the keep-context would not work. The keep context would switch again before we detect the overflow.
So I had the idea of making the skip dependent on one more factor: first compute the difference. If that is negative, then we know that there will be an unavoidable column-break somewhere before the current node, so we can already trigger the overflow handling. Seems to work nicely, so far. Still have to complete the testcases: the additional one present in the patch still needs decent checks, and additional tests checking the behavior in tables and lists would also be nice. Maybe it can be done by extending some of the existing testcases. Getting into that right now.

Created attachment 24015 [details]
updated patch

Added decent checks to the testcase, which uncovered one remaining issue that has also been addressed in the meantime. Still problematic: the fact that block-4a in the testcase renders correctly only if it fits in one page. If not, we will still consider the first too-long page-break (negative difference) within the block, and recover from there, leading to unexpected results.
Still lacking testcases for tables and lists...

Created attachment 24152 [details]
small FO demonstrating the remaining problem


Added this attachment to demonstrate the one remaining issue I was looking into. It is not restricted to the page-keep being nested, but is a general problem with keep-within.page in multi-column flows.

The changes break no testcases, since our current tests only check for behavior in single column documents, where the issue does not exist. So, it could be argued that the changes are ready to be committed to Trunk, since it does offer increased functionality. 

I propose to add the newly attached file as a disabled testcase to remind us of what does not work, but apart from that...? Anyone against?

Patch (finally) applied to FOP Trunk with rev807014, with the additional disabled-testcase.

batch transition pre-FOP1.0 resolved+fixed bugs to closed+fixed