Removing lookahead algorithm in nsTextFrame

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Removing lookahead algorithm in nsTextFrame

Robert O'Callahan-3
Context: https://bugzilla.mozilla.org/show_bug.cgi?id=317278#c4

The issue is how to handle content like
<span>Hello Kit</span>ty
where a word spans multiple frames and we need to break before the word.
The problem is that the span's text frame doesn't know to break at the
space if "Kit" fits but "Kitty" doesn't.

Currently the text frame calls nsTextFrame::ComputeTotalWordDimensions
to look ahead in the frame tree and try to compute the width required
for the word that starts at the end of this frame. This code is really
nasty. It also doesn't work in many cases ... for example, we don't know
how to measure non-text-frame widths (these frames have not been
reflowed yet, in general), so we give up on measuring those frames and
allow breaks to happen before them. See the comment at
http://lxr.mozilla.org/mozilla/source/layout/generic/nsImageFrame.cpp#1614,
for example.

I think a better way would be to simply allow the text frame to finish
reflow with status 'complete', but record in nsLineLayout (or elsewhere)
that there's a potential line break before the last word. When line
layout eventually runs out of available space, we notice that we had a
potential line break earlier, and reflow the line again, forcing the
text frame to break at the last saved line break position. I think this
case is not common so the cost should not be significant (and we may be
able to optimize by only reflowing frames at or after the forced line
break). In fact we may improve performance because the current lookahead
approach requires us to measure the same text multiple times any time a
word spans frames. Anyway it would simplify text frames a lot because
the process of transforming and measuring text in a text frame could
only happen in its Reflow. We also wouldn't have to do scary crawling
around in a not-yet-reflowed frame tree.

This general approach would also be useful in vertical situations.
Currently we have problems with vertically-constrained text (pages,
columns) where a frame with a thick border where the border ends up on a
page boundary. We really need to move the last child to the next page,
if possible, but we've already placed the child on the current page
because it fitted. We need to redo the reflow, forcing the child to move
to the next page. This becomes really acute when we want to handle CSS
widows, orphans and page-break control.

Rob
_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout
Reply | Threaded
Open this post in threaded view
|

Re: Removing lookahead algorithm in nsTextFrame

L. David Baron
On Friday 2006-04-28 12:31 +1200, Robert O'Callahan wrote:
> I think a better way would be to simply allow the text frame to finish
> reflow with status 'complete', but record in nsLineLayout (or elsewhere)
> that there's a potential line break before the last word. When line
> layout eventually runs out of available space, we notice that we had a
> potential line break earlier, and reflow the line again, forcing the
> text frame to break at the last saved line break position. I think this

Why do we need to reflow the line again?  Why can't we just break the
frames at the earlier position and *not* reflow the line again -- just
do vertical/horizontal alignment of the line.

-David

--
L. David Baron                                <URL: http://dbaron.org/ >
           Technical Lead, Layout & CSS, Mozilla Corporation

_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Removing lookahead algorithm in nsTextFrame

L. David Baron
On Friday 2006-04-28 15:24 -0700, L. David Baron wrote:

> On Friday 2006-04-28 12:31 +1200, Robert O'Callahan wrote:
> > I think a better way would be to simply allow the text frame to finish
> > reflow with status 'complete', but record in nsLineLayout (or elsewhere)
> > that there's a potential line break before the last word. When line
> > layout eventually runs out of available space, we notice that we had a
> > potential line break earlier, and reflow the line again, forcing the
> > text frame to break at the last saved line break position. I think this
>
> Why do we need to reflow the line again?  Why can't we just break the
> frames at the earlier position and *not* reflow the line again -- just
> do vertical/horizontal alignment of the line.
That said, I think we could do much better still if we abandoned the
idea that reflow of inline frames had to be done using a member function
on the frames.  Then we could do splitting and just keep going.  Much of
the work (vertical alignment, horizontal alignment and justification)
already happens outside of reflow anyway.

-David

--
L. David Baron                                <URL: http://dbaron.org/ >
           Technical Lead, Layout & CSS, Mozilla Corporation

_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Removing lookahead algorithm in nsTextFrame

L. David Baron
On Friday 2006-04-28 15:26 -0700, L. David Baron wrote:
> That said, I think we could do much better still if we abandoned the
> idea that reflow of inline frames had to be done using a member function
> on the frames.  Then we could do splitting and just keep going.  Much of
> the work (vertical alignment, horizontal alignment and justification)
> already happens outside of reflow anyway.

To clarify this a little:  inline reflow is fundamentally an operation
on lists, not trees.  (Inline frames, which are containers, just put two
items in the list:  one before their children and one after.)  If we do
this algorithm by walking the list, without recursion into methods, then
we can split things more easily and just keep going without having to go
out of the recursion and then back into it on the new continuation
objects.

-David

--
L. David Baron                                <URL: http://dbaron.org/ >
           Technical Lead, Layout & CSS, Mozilla Corporation

_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Removing lookahead algorithm in nsTextFrame

Robert O'Callahan-3
In reply to this post by Robert O'Callahan-3
L. David Baron wrote:

> On Friday 2006-04-28 12:31 +1200, Robert O'Callahan wrote:
>> I think a better way would be to simply allow the text frame to finish
>> reflow with status 'complete', but record in nsLineLayout (or elsewhere)
>> that there's a potential line break before the last word. When line
>> layout eventually runs out of available space, we notice that we had a
>> potential line break earlier, and reflow the line again, forcing the
>> text frame to break at the last saved line break position. I think this
>
> Why do we need to reflow the line again?  Why can't we just break the
> frames at the earlier position and *not* reflow the line again -- just
> do vertical/horizontal alignment of the line.

That would require going back and splitting the textframe and its inline
containers and putting the continuations in the right places,
recalculating the metrics for the modified frames, and also undoing
float placement if any. It's a lot simpler just to reflow the line
again. It's not a full line reflow because we don't do horizontal and
vertical alignment etc, and it only happens when a multi-frame word
crosses the line end boundary after the first frame, so I don't think
it'll be a performance issue.

Rob
_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout
Reply | Threaded
Open this post in threaded view
|

Re: Removing lookahead algorithm in nsTextFrame

Robert O'Callahan-3
In reply to this post by L. David Baron
L. David Baron wrote:
> To clarify this a little:  inline reflow is fundamentally an operation
> on lists, not trees.  (Inline frames, which are containers, just put two
> items in the list:  one before their children and one after.)  If we do
> this algorithm by walking the list, without recursion into methods, then
> we can split things more easily and just keep going without having to go
> out of the recursion and then back into it on the new continuation
> objects.

This sounds like something that would be post 1.9 if we did it ... I
don't see a driving need to do it for 1.9.

Do you intend this method to eventually construct the same sort of
inline frame tree that we do today?

Rob
_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout
Reply | Threaded
Open this post in threaded view
|

Re: Removing lookahead algorithm in nsTextFrame

L. David Baron
On Monday 2006-05-01 09:05 +1200, Robert O'Callahan wrote:

> L. David Baron wrote:
> > To clarify this a little:  inline reflow is fundamentally an operation
> > on lists, not trees.  (Inline frames, which are containers, just put two
> > items in the list:  one before their children and one after.)  If we do
> > this algorithm by walking the list, without recursion into methods, then
> > we can split things more easily and just keep going without having to go
> > out of the recursion and then back into it on the new continuation
> > objects.
>
> This sounds like something that would be post 1.9 if we did it ... I
> don't see a driving need to do it for 1.9.
That's fine, although I fear significant work on the current code may be
somewhat painful.

> Do you intend this method to eventually construct the same sort of
> inline frame tree that we do today?

Yes.

-David

--
L. David Baron                                <URL: http://dbaron.org/ >
           Technical Lead, Layout & CSS, Mozilla Corporation

_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Removing lookahead algorithm in nsTextFrame

Robert O'Callahan-3
In reply to this post by Robert O'Callahan-3
L. David Baron wrote:

> On Monday 2006-05-01 09:05 +1200, Robert O'Callahan wrote:
>> L. David Baron wrote:
>>> To clarify this a little:  inline reflow is fundamentally an operation
>>> on lists, not trees.  (Inline frames, which are containers, just put two
>>> items in the list:  one before their children and one after.)  If we do
>>> this algorithm by walking the list, without recursion into methods, then
>>> we can split things more easily and just keep going without having to go
>>> out of the recursion and then back into it on the new continuation
>>> objects.
>> This sounds like something that would be post 1.9 if we did it ... I
>> don't see a driving need to do it for 1.9.
>
> That's fine, although I fear significant work on the current code may be
> somewhat painful.

The redo stuff that I've already implemented and the stuff that I just
proposed don't feel too painful to me. I think the main reason to do
what you're proposing would be performance.

Rob
_______________________________________________
dev-tech-layout mailing list
[hidden email]
https://lists.mozilla.org/listinfo/dev-tech-layout