300131 - need to refactor nsIFrame::PeekOffset

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Eyal Rozenberg]

Instead of being a deep-recursive, normal member function of nsFrame and its
inheritor classes, the following should happen:

- There should be an independent, or a static member of nsFrame, function called
'GetNext' or 'GetNextItem'.
- This function shouldn't get an entire PeekOffsetStruct but just those
parameters it needs (direction,frame,what kind of item, etc.)
- This function should be do a visit of the frames tree, i.e. "does the current
frame have the next item? no; maybe its next (or prev, depending) sibling? no,
and it's the last sibling; ok, maybe the next sibling of its parent has it?" etc.
- nsIFrame should have a 'HasItem' or 'HasPosition' or whatever which checks
whether it or a subframe of qualifies as having a position, or a word, or an end
of a line or whatever, and returning the proper information which up until now
was returned in PeekOffsetStruct.
- The 'HasItem' function will be implemented differently for nsTextFrame,
nsFrame, nsBRFrame just like the way it happens now with PeekOffset

BTW, One notes that PeekOffset gets called from very few places:
http://lxr.mozilla.org/seamonkey/search?string=PeekOffset%28
most calls are internal to the inheritor-of-nsFrame classes, and the rest are
from the selection/movement code in nsSelection.cpp - so one would expect a
relatively regression-free transition
that PeekOffset is called

Comment 1

[Eyal Rozenberg]

This change is of course related to the incorrect BiDi-related behavior of the
current implementation of the PeekOffset()'s. But the BiDi issues are not the
reason for this refactoring, they're just additional motivation.

Comment 2

[Eyal Rozenberg]

A couple more ideas after reading the code for a little while more:

- since the function is visual-order based, it would be helpful if the confusing
next/prev, prefer-left/prefer-right enums are resolved outside of the
PeekOffset() replacement - perhaps in the relevant nsSelection methods - so that
PeekOffset() is given strictly visual directions and hints.
- it may be beneficial splitting the function for the various values of mAmount
(get the right edge of the line, get one char to the left etc.) - despite the
code duplication.
- there are a host of unexplained choices and behaviors of the code which must
be documented somehow.

Comment 3

[Eyal Rozenberg]

This refactoring may, in the case of selecting words or lines, allow us to first
look at the entire content of a line of text, decide where we want to get to,
and then just determining which frame in the line holds that position (with ties
broken according to 'prefer left' or whatever it is we'll have).

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

This sounds good.

Comment 5

[Eyal Rozenberg]

Attachment: suggested header change

I'm not sure about the 'prefer left' as an argument - its presence or absence
is currently just my best guess. Also, it is possible to use the enum instead
of having multiple functions, with these methods becoming static functions in
nsFrame.cpp and the main method being just a dispatcher (this won't save code
but will make the interface slimmer).

Comment 6

[Eyal Rozenberg]

Umm, that GetPositionVisualInNextPrevLine should be
GetPositionInVisualNextPrevLine of course.

Comment 7

[Eyal Rozenberg]

Comment on attachment 188924 [details] [diff] [review]
suggested header change

Hmm, I forgot I won't be able to delete this... should have learned my lesson
by now. I'll try to set up some directory with code and point the URL at it.

Comment 8

[Eyal Rozenberg]

At

http://tx.technion.ac.il/~eyalroz/mozilla/ 

You can find initial suggested changes to nsFrame.h and nsFrame.cpp , both
plainly as 2 files and as a patch against the trunk. This code has not yet been
compiled, plus I'm not sure whether I'm going to have the time to work on this
further. In the code you'll find some 'Eyal says:' near places which need more
work (mostly wrapping calls to functions which get nsPeekOffsetStruct's; later
on it might be a good idea to get rid of the nsPeekOffsetStruct's there as
well), plus of course there's the code in nsTextFrame.cpp a lot of which needs
to be partially rewritten , and the code in nsBRFrame.cpp .

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

*** Bug 304656 has been marked as a duplicate of this bug. ***

Comment 10

[Robert O'Callahan (:roc) (email my personal email if necessary)]

> No, I don't agree. The functions do quite different things, they don't just do
> the same thing for different content units, and they don't just cover
> different combinations of parameters. Trying to force it all into a single
> function would just mean a big switch. Also, some functions require only some
> parameters and one of the big problems with nsPeekOffsetStruct is the
> uncertainty of which fields are in actual use, when. Finally, it seemed to me
> that using more meaningful, less generic and less cryptic function names helps
> to understand what exactly is being done. PeekOffset() is a bit like having a
> DoAnyFunction() function which takes an "ePossibleFunction aWhichFunction"
> parameter and an "struct nsLotsOfParamsForEverythingStruct" parameter.

You're absolutely right, but there's a tension between having too many
specialized functions and a few over-general ones. We'll have to figure out
exactly the functionality we need and then make the best tradeoff. Anyway the
latest version of your patch (sorry I didn't look before) only has two functions
so it doesn't worry me right now.

> We currently support only visual caret movement (for characters/words).
> There's bug 167288 for supporting logical movement on platforms where that's
> the system behaviour (Windows, and also Linux, IIRC).

That's something we should fix here, now --- at least the infrastructure, if not
the actual UI behaviour.

> The visual/logical ambiguity is *the* problem at the base of bidirectional
> caret movement. It exists (in different forms) for both the logical and visual
> approaches. Note that we are internally keeping track only of the logical
> position of the caret. Since one visual position can map to two different
> logical positions, we are potentially in the "wrong" logical place half the
> time (that's assuming we manage to do the visual movement correctly!)

I think keeping the logical position is the right thing to do because it is
never ambiguous. It can also be preserved during style and content changes much
more robustly. As you point out below, ambiguity only arises during visual
movement and it's simply up to us to resolve it in a sensible way.

> I once had the radical idea that since we're doing visual caret movement we
> should actually keep track of the caret's visual position, and decide on the
> logical position only when we must (i.e. when the user types a letter, or hits
> "delete" - but not when they're just moving around using arrow keys). I can
> elaborate on that if anybody's interested (I'm already digressing).

I don't think this will really help. Whenever we move visually we simply need to
choose a content position that maps to the desired visual position. It doesn't
matter which content position we choose until the user does something that
depends on the content position, at which point visual caret positioning hits
the same problem.

> If we were to switch to logical caret movement (at least for some platforms),
> things would actually be a bit easier. You can usually know where the caret is
> logically if you know how you got there (the left/right arrows traverse the
> content in logical order, so as long as you're just using them you always know
> where you are, logically). The only case when you have to make a decision is
> if you get to an ambiguous location using a mouse-click.

That's pretty unlikely, right? The user would have click exactly on a pixel
boundary which doesn't really happen. In reality they always click inside some
character so we then know which character the caret should be associated with.

> You also have the "reverse" problem of where to display the caret when it is
> logically in a place that can map to two visual places. This can probably be
> "guessed" pretty well based on where we came from.

We can get around this by tracking in the caret position whether the caret is
associated with the content logically before it or logically after it. So a
caret position would be something like
struct nsCaretPosition {
  nsIContent*  mContent;
  PRUInt32     mOffset;
  /** If mAssociateLeft is true then the caret is *after* the character
   * at mOffset - 1; if mAssociateLeft is false then the caret is *before* the
   * character at mOffset. If mOffset is zero then mAssociateLeft must
   * false; if mContent is text and mOffset is the text length then
   * mAssociateLeft must be true. */
  PRPackedBool mAssociateLeft;
};

Comment 11

[Eyal Rozenberg]

(In reply to comment #10)
Anyway the
> latest version of your patch (sorry I didn't look before) only has two functions
> so it doesn't worry me right now.

The latest version wasn't the patch. See

http://tx.technion.ac.il/~eyalroz/mozilla/nsFrame.cpp

line 3590 - that's the big function with the switch. It calls one of five
different functions (one I hadn't begun to implement and one is a simple wrapper
for GetContentAndOffsetsFromPoint which can probably be removed).


> struct nsCaretPosition {
>   nsIContent*  mContent;
>   PRUInt32     mOffset;
>   PRPackedBool mAssociateLeft;
> };

I sort of thought of that in my code already, except for the mAssociateLeft. But
why is this is supposed to be working for both visual and logical positions? In
all the code I've seen offsets into mContent were visual. And if the offset is
logical, wouldn't you want 'AssociatePrev' rather than 'AssociateLeft'?

Comment 12

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #11)
> > struct nsCaretPosition {
> >   nsIContent*  mContent;
> >   PRUInt32     mOffset;
> >   PRPackedBool mAssociateLeft;
> > };
> 
> I sort of thought of that in my code already, except for the mAssociateLeft.
> But why is this is supposed to be working for both visual and logical
> positions?

I think that maintaining logical caret positions makes the most sense, but we
want to support visual *and* logical movement.

> In all the code I've seen offsets into mContent were visual.

Really? That makes no sense. Content is the DOM which is logical unless it's a
visual character encoding (which I *hope* means we just treat everything as a
LTR language).

> And if the offset
> is logical, wouldn't you want 'AssociatePrev' rather than 'AssociateLeft'?

Indeed, my mistake.

Comment 13

[Eyal Rozenberg]

*** Bug 263305 has been marked as a duplicate of this bug. ***

Comment 14

[Eyal Rozenberg]

(In reply to comment #2)
> so that PeekOffset() is given strictly visual directions and hints.

I'm retracting this statement... it seems PeekOffset is only _setting_
aPos->mPreferLeft; I don't think it's using it for anything.

Comment 15

[Uri Bernstein]

I've spent the last couple of days trying to get rid of nsPeekOffset, instead
passing its members explicitly, thus exposing the true nature of each of the
parameters (input, output, or i/o). Eventually, I came to the conclusion that
this is not the first thing that needs to be done. I now strongly agree with
Eyal (and with bug 202306) that the first thing to be done is to split
PeekOffset() into methods by amount. There's really very little in common
between the functionality of "moving one line up" and that of "moving to the end
of the current word, or to the next word if we're already at the end of a word".
There's no reason that, e.g., word-specific parameters such as mEatingWS should
be carried around for all the other cases. 
On a side note, I actually prefer the function names suggested in bug 202306 to
Eyal's ("PrevNext" is good for when you get both the previous and the next
something - such as in GetPrevNextBidiLevels(). But here we're only going in one
direction).

Anyway, so that my work won't be totally in vain, here's what I found about
nsPeekOffsetStruct. Nine of its members are (basically) input parameters:
  nsIPresShell *mShell;
  nscoord mDesiredX;
  nsSelectionAmount mAmount;
  nsDirection mDirection;
  PRInt32 mStartOffset;
  PRBool mEatingWS;
  PRBool mJumpLines;
  PRBool mScrollViewStop;
  PRBool mIsKeyboardSelect;

Note that some of these are used only in specific cases: mDesiredX for
eSelectLine; mEatingWS and mIsKeyboardSelect for eSelectWord; and I'm not sure
in which cases mJumpLines is used. 

Of these input parameters - two are, at least technically, i/o parameters:
- mAmount
- mStartOffset
These two are, at some point, assigned a value, either by PeekOffset() itself or
by a method called by PeekOffset (GetFrameFromDirection,
GetNextPrevLineFromBlockFrame). It is not clear that in all cases the "out"
value is actually used by the calling function - it's possible that some of the
assignments are just because the same POS is used in inner calls to methods, and
needs to be adjusted for these calls.
This i/o-ness is bad - and getting rid of it should be one of our goals.

Then there's
  PRBool aPreferLeft
Which we all love so much. Apparently it started its life as an input parameter,
and then morphed into an i/o parameter. It's output value certainly is used.
Sorting it out should be one of our main goals.

The remaining four members are output parameters:
  nsCOMPtr<nsIContent> mResultContent;
  PRInt32 mContentOffset;
  PRInt32 mContentOffsetEnd;
  nsIFrame *mResultFrame; 
although I'm not sure mContentOffsetEnd is actually used anywhere. Also,
mResultFrame is apparently ignored , at least by nsSelection::MoveCaret (for a
reason which I don't believe is true!).

So the strategy I propose is:
- Split PeekOffset() to methods per amount
- Go over these methods one by one and if necessary rewrite them from the ground
up, eliminating uses of nsPeekOffsetStruct, perhaps replacing it by smaller
structs which are entirely either input (with const members) or output parameters.

------------------------------------

Roc - only today I noticed your responses to me in comment #10. Regarding my
"using visual positions" idea, I expanded it in
http://wiki.mozilla.org/User:Uri/Bidi_editing, which you might be interested in
reading. (Eyal already commented on it, so you can read his comments on the talk
page as well. Hopefully I'll have some answers for him soon). I suggest we
continue the discussion of these ideas there, rather than on this bug. It's
really a discussion of functionality, whereas this bug focuses on code refactoring.

Comment 16

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #15)
> I now strongly agree with
> Eyal (and with bug 202306) that the first thing to be done is to split
> PeekOffset() into methods by amount.

Fine, but it's still important to define very precisely what each of these
functions does.

> Roc - only today I noticed your responses to me in comment #10. Regarding my
> "using visual positions" idea, I expanded it in
> http://wiki.mozilla.org/User:Uri/Bidi_editing, which you might be interested
> in reading. (Eyal already commented on it, so you can read his comments on the
> talk page as well. Hopefully I'll have some answers for him soon). I suggest
> we continue the discussion of these ideas there, rather than on this bug. It's
> really a discussion of functionality, whereas this bug focuses on code
> refactoring.

That is a great discussion. I'll comment there. I do suggest that we resolve
what the behaviour should be before we worry about the code.

Comment 17

[Uri Bernstein]

Attachment: Caret operations (functional spec, draft)

Here I tried to specify what types of functionality we want. This does not go
into how to implement the requested operations, or into code design.

Read carefully the "word" rows - you might not agree with what I put there.
Also, the exact definitions of "beginning/end/left/right" of word, under the
various platforms, are still missing.

Also, if someone can clarify what the current eSelectNoAmount really means,
that would be great.

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

The "used internally" functions are not really part of a functional spec. We may
or may not even need them internally.

The set of operations looks good but you need to define what each of these
operations actually does in more detail.

Comment 19

[Eyal Rozenberg]

(In reply to comment #15)
> Then there's
>   PRBool aPreferLeft
> Which we all love so much. Apparently it started its life as an input parameter,
> and then morphed into an i/o parameter.

Are you sure? Can you name a piece of code that gets called with an
nsPeekOffsetStruct as a parameter and actually _uses_ mPreferLeft, for something
other than deciding on how to reset its value?

Comment 20

[Uri Bernstein]

> Are you sure? Can you name a piece of code that gets called with an
> nsPeekOffsetStruct as a parameter and actually _uses_ mPreferLeft, for something
> other than deciding on how to reset its value?

Well, I *thought* I could, but upon further examination - you're right.
mPreferLeft is, and always was, an output parameter. its input value, as you
say, is only used for determining its output value. Sorry for the confusion.

Comment 21

[Uri Bernstein]

We also need to define how replaced elements (e.g. inline images) are treated,
both in the "by character" case and in the "by word" case. Currently they seem
to be just ignored, which, IMO, is not the correct behavior (see bug 306683).

Comment 22

[Uri Bernstein]

Attachment: phase 1, v1 (diff -w)

This patch does the following:

* Replace recursion in PeekOffset with iteration. This is done by splitting PeekOffset into a top level, non-virtual, nsIFrame::PeekOffset, which does the iterating over frames, and to PeekOffset[Character|Word|NoAmount] methods, which operate on one frame at a time, and return a value indicating whether the requested position was found within the frame, or whether iteration should continue to the next frame. 

* Remove nsPeekOffsetStruct::mEatingWS, thus hiding this implementation detail from the API, per bug 304656 comment 0.

* Change the offsets within PeekOffset[Character|Word|NoAmount] to be relative to the frame's content offset, also per the same comment.

* Tighten the interface to GetFrameFromDirection() so that it doesn't have to know about mAmount and mEatingWS. Also, the arguments are now explicit, instead of using PeekOffsetStruct. (This was my original goal when I started working on this. The others just followed).

* Add some comments (mostly to nsIFrame::PeekOffset) attempting to clarify the meaning of things like "wordSelectEatSpace" and "eatingWS".

* Fix some bugs, namely: bug 139402, bug 346445, and bug 347143.

* Fix a bug in nsSelection::MoveCaret, which caused incorrect behavior when PeekOffset() failed. See bug 299371.

This patch does not change the interface to PeekOffset itself (other than removing nsPeekOffsetStruct::mEatingWS and dropping eSelectNoAmount as a valid value of mAmount). Such changes could be done in subsequent phases.

I did my best to test this in various plaintext and HTML cases, with both settings of layout.word_select.eat_space_to_next_word.

There's obviously a lot more to do, but I think this can serve as a first step in the right direction.

Comment 23

[Uri Bernstein]

(In reply to comment #22)
> * Fix some bugs, namely: [...] bug 347143.

That should have read: bug 347173.

Comment 24

[Uri Bernstein]

Attachment: phase 1, v1.1 (diff -w)

- Updated to tip.
- I realized that the current behavior for character movement is that the movement is canceled if, after jumping a line, we find no renderable content to land on. This patch preserves this behavior.
- Restored the comment about the meaning of "direction" for visual bidi movement, which used to be in nsTextFrame::PeekOffset, into the documentation of nsPeekOffsetStruct, in nsFrameSelection.h.

Comment 25

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+   *  @param aScrollViewStop [in] whether to stop when reaching a scroll view boundary

Say scroll frame boundary.

+   *  @param aOutOffset [out] set to 0 or -1 to indicate which edge of the result frame
+   *                          is closer to "this" frame

Why -1? At least from this comment it's not clear what this means.

+   * @return PR_TRUE: An appropreate offset was found within this frame,

"appropriate"

+   * @param  aForward [in] Are we moving forward (or backward), relative to this frame

forward in content order or visual order?

+   * @param  aWordSelectEatSpace [in] PR_TRUE: look for a boundary between whitespace
+   *         and non-whitespace (in the direction of movement).

I think it's clearer to say "look for non-whitespace following whitespace"

   *         PR_FALSE: look for a boundary between non-whitespace and whitespace
+   *         (in the direction of movement).

"look for whitespace following non-whitespace"

+   * @param  IsKeyboardSelect [in] Was the action initiated by a keyboard operation?

Make it "aIsKeyboardSelect".

I'd prefer a better description here. In text, it seems that the difference is that when aIsKeyboardSelect is true, we break at text following punctuation, but when it's false we break at punctuation following text as well as text following punctuation. Is that it?

Can we eliminate prescontext parameters here? We can always get it from the frame.

+  PRBool movingInFrameDirection = 
+    ((aDirection == eDirNext) && !isReverseDirection) ||
+    ((aDirection == eDirPrevious) && isReverseDirection);

PRBool movingInFrameDirection = aDirection ==
  (isReverseDirection ? eDirPrevious : eDirNext);

+      // 1. If we're moving forward, looking for a word beginning (i.e. a boundary
+      //    between whitespace and non-whitespace), then eatingWS==PR_TRUE means
+      //    "we already saw some whitespace".
+      // 2. If we're moving backward, looking for a word beginning (i.e. a boundary
+      //    between non-whitespace and whitespace), then eatingWS==PR_TRUE means
+      //    "we already saw some non-whitespace".
+      PRBool eatingWS = PR_FALSE;

Can't we use a better name here?

+nsFrame::PeekOffsetCharacter(PRBool aForward, PRInt32* aOffset)
+{
+  NS_ASSERTION (aOffset && *aOffset <= 1, "aOffset out of range");
+  PRInt32 startOffset = *aOffset;
+  if (startOffset < 0)
+    startOffset = 1;

Why are negative offsets treated as 1?

Otherwise looks pretty good.

Comment 26

[Uri Bernstein]

Attachment: [backed out] phase 1, v1.2 (diff -w)

Addressed all the comments (I hope).

What you said about IsKeyboardSelect is basically true, but I tried to explain it in simpler terms.

I'm not sure sawBeforeType means anything, but at least it's not lying (like eatingWS). If you have a better idea, I'll be happy to hear it.

I explained the "negative offset" issue in comments. I hope it's clear now.

Comment 27

[Uri Bernstein]

Checked in:
Checking in layout/generic/nsIFrame.h;
/cvsroot/mozilla/layout/generic/nsIFrame.h,v  <--  nsIFrame.h
new revision: 3.329; previous revision: 3.328
done
Checking in layout/generic/nsFrame.h;
/cvsroot/mozilla/layout/generic/nsFrame.h,v  <--  nsFrame.h
new revision: 3.251; previous revision: 3.250
done
Checking in layout/generic/nsFrame.cpp;
/cvsroot/mozilla/layout/generic/nsFrame.cpp,v  <--  nsFrame.cpp
new revision: 3.670; previous revision: 3.669
done
Checking in layout/generic/nsBRFrame.cpp;
/cvsroot/mozilla/layout/generic/nsBRFrame.cpp,v  <--  nsBRFrame.cpp
new revision: 1.62; previous revision: 1.61
done
Checking in layout/generic/nsTextFrame.cpp;
/cvsroot/mozilla/layout/generic/nsTextFrame.cpp,v  <--  nsTextFrame.cpp
new revision: 1.589; previous revision: 1.588
done
Checking in layout/generic/nsInlineFrame.h;
/cvsroot/mozilla/layout/generic/nsInlineFrame.h,v  <--  nsInlineFrame.h
new revision: 1.55; previous revision: 1.54
done
Checking in layout/generic/nsInlineFrame.cpp;
/cvsroot/mozilla/layout/generic/nsInlineFrame.cpp,v  <--  nsInlineFrame.cpp
new revision: 3.261; previous revision: 3.260
done
Checking in layout/generic/nsSelection.cpp;
/cvsroot/mozilla/layout/generic/nsSelection.cpp,v  <--  nsSelection.cpp
new revision: 3.262; previous revision: 3.261
done
Checking in layout/generic/nsFrameSelection.h;
/cvsroot/mozilla/layout/generic/nsFrameSelection.h,v  <--  nsFrameSelection.h
new revision: 1.9; previous revision: 1.8
done
Checking in layout/base/nsCaret.cpp;
/cvsroot/mozilla/layout/base/nsCaret.cpp,v  <--  nsCaret.cpp
new revision: 1.164; previous revision: 1.163
done
Checking in accessible/src/html/nsHyperTextAccessible.cpp;
/cvsroot/mozilla/accessible/src/html/nsHyperTextAccessible.cpp,v  <--  nsHyperTextAccessible.cpp
new revision: 1.23; previous revision: 1.22
done

Comment 28

[Uri Bernstein]

Sorry - I didn't mean to resolve this as FIXED.

Comment 29

[Uri Bernstein]

Comment on attachment 237511 [details] [diff] [review]
[backed out] phase 1, v1.2 (diff -w)

Changing nsIFrame::PeekOffset() from NS_IMETHOD to nsresult hid it form the Accessability module, causing bustage (on some of the build machines), and when I tried to fix it, I screwed up. I'll try again tomorrow.

Comment 30

[Uri Bernstein]

Attachment: [checked in] phase 1, v1.3

This just changes back the signature of nsIFrame::PekOffset to NS_IMETHOD.
The reason I changed it in the first place was that I didn't want it to be virtual. But evidently, doing so wasn't a good idea.

roc - can you please just confirm this is OK? If so, I'll check it in whenever I have time to watch the tree.

Sorry for this whole mess.

Comment 31

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 237712 [details] [diff] [review]
[checked in] phase 1, v1.3

sigh

yes, this should work

Comment 32

[Uri Bernstein]

Comment on attachment 237712 [details] [diff] [review]
[checked in] phase 1, v1.3

Checked in. Hopefully this time there won't be any major disasters.

Comment 33

[Aaron Leventhal]

If it's checked in, why is this still open?

Comment 34

[David Bolter [:davidb] (NeedInfo me for attention)]

Roc, do you know what should happen next with this bug?

Comment 35

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Let's just close it.