176251 - Problems with nsContentIterator PRE traversal

Status: VERIFIED FIXED

(Core :: DOM: Editor, defect, P3)

Description

[kinmoz]

1. The |mFirst| and |mLast| calculated during the |Init()| calls are
   incorrect for PRE traversal. Currently they are calculated for POST
   traversal which is the default traversal mode for the iterator.

2. Need to decide whether we want to support dynamic switching between
   PRE and POST traversal modes. After working on problem #1 above I'm
   thinking this would be really difficult for some ranges given the
   fact that PRE and POST modes could iterate over nothing in one mode
   and something in the other, or over an entirely different set of nodes.

   A. Support dynamic switching.

      1. During |Init()| calculate |mPreFirst|, |mPreLast|, |mPostFirst|,
         and |mPostLast|, and set |mCurNode| based on the current traversal
         mode . Keeping |mFirst| and |mLast|, and setting them to one of the
         pairs mentioned above for the current mode is optional, but if we
         got rid of them, we would have to replace their usage in the current
         set of traversal methods.

      2. Modify |First()| and |Last()| to init |mCurNode| based on the
         current traversal method.

      3. Modify |MakePre()| and |MakePost()| so that it can tell if
         |mCurNode| is actually in the list nodes the mode would traverse.
         Note that we can't simply call |IsNodeIntersectsRange()| because we
         currently don't keep track of the init range, and besides asking
         if |mCurNode| intersected the init range would always return true,
         even if it wouldn't be visited in that mode. |mIsDone| would have
         to be set appropriately based on what we figure out about |mCurNode|
         above, and finally the index stack will have to rebuilt.
         
   B. No dynamic switching.

      1. Get rid of the |MakePre()| and |MakePost()| methods and
         provide some way for the caller to communicate which iterator
         traversal they wanted to use at creation or |Init()| time.
         Specifying at creation time would probably mean we have a
         separate iterator class for each traversal.


Here are some example ranges that illustrate some of the issues that need to be
dealt with. Note that these examples do not illustrate the special casing done
for text nodes.


            [A]
             |
       +-----+-----+
       |           |
      [B]         [C]
       |           |
   +---+---+   +---+---+
  [D]     [E] [F]     [G]
           |   |
           |   |
          [H] [I]


== Range where PRE mode is empty but POST isn't:

   (H,0)(B,2)

   POST: H-E
   PRE:  <EMPTY>

== Range where POST mode is empty but PRE isn't:

   (C,0)(I,0)

   POST: <EMPTY>
   PRE:  F-I

== Example1 where nodes not in one mode are in the other:

   (E,0)(F,1)

   POST: H-E-B-I-F-C
   PRE:  H-C-F-I

== Example2 where nodes not in one mode are in the other:

   (E,1)(F,0)

   POST: E-B
   PRE:  C-F

== Example3 where nodes not in one mode are in the other:

   (B,0)(c,2)

   POST: D-H-E-B-I-F-G
   PRE:  D-E-H-C-F-I-G

Comment 1

[kinmoz]

Attachment: Patch rev 0.1 (Work In Progress)

This patch attempts to calculate the correct mFirst and mLast values for both
PRE and POST traversal.

Comment 2

[Joe Francis]

As I discussed with Kin earlier, I prefer plan B) No dynamic switching.  This is
because if you switch from pre to post iteration for an iterator that was
initialized with a range, there is no guarantee that the current node (current
iterator position) is within the traversal of the other-directioned iterator. 
The right thing to do in that case is not well defined.  It really depends on
what the caller expected.

With plan B) the caller would create an iterator over the same range, and
attempt to set the current node to the one they had from the prior iterator.  If
that node was out of bounds they would get an error back.  Then the caller can
decide what to do, instead of the iterator code having to make the (possibly
wrong) decision.

Comment 3

[Joe Francis]

Comment on attachment 103889 [details] [diff] [review]
Patch rev 0.1 (Work In Progress)

in MakePre() and MakePost(), the mIsDone = !mFirst; looks wrong to me.	Don't
you mean mLast?

Comment 4

[Joe Francis]

what i'm trying to say is:
mIsDone = (mCurNode == mLast);
if (mFirst) mIsDone = PR_TRUE;

Comment 5

[Joe Francis]

dammit i cant type.  take 3:

// we are done if we are positioned at end
mIsDone = (mCurNode == mLast);
// we are done if there simply isn't a start node in this traversal order at all
if (!mFirst) mIsDone = PR_TRUE;

Comment 6

[kinmoz]

Right I made absolutely no effort to handle mCurNode in the MakePre()/MakePost()
methods.

Comment 7

[kinmoz]

Attachment: Patch rev 0.1.1 (Work In Progress with corrected expression)

This is the same as patch rev 0.1, but I added a missing '!':

-  if (cData || ContentHasChildren(endCon) || endIndx == 0)
+  if (cData || !ContentHasChildren(endCon) || endIndx == 0)

Comment 8

[kinmoz]

Attachment: Patch rev 0.2 (Removal of MakePre() and MakePost() with checks for intersection with traversal range)

Comment 9

[kinmoz]

Attachment: Patch rev 0.2.1 (Same as above with correct range point calcs in PositionAt())

This patch is pretty much the same as rev 0.2 except it takes into account the
iter direction when calculating the traversal range endpoints to handle some
cases that jfrancis correctly pointed out to me. :-) Thanks Joe.

Comment 10

[Joe Francis]

Comment on attachment 106296 [details] [diff] [review]
Patch rev 0.2.1 (Same as above with correct range point calcs in PositionAt())

cool beans

Comment 11

[kinmoz]

Cc akkana.

Akkana, I just wanted to make sure that the changes I made in nsFind.cpp are ok
with you.

Comment 12

[kinmoz]

Attachment: Patch rev 0.2.2 (Something that actually works.)

Ok here's a patch that actually works. Like a bonehead, I forgot to register
the CID for the pre-iterator, I also had to correct some of the logic in a
couple of places. I used |find| to test out the pre-iter, and it seems to be
working fine.

These are the changes between rev 0.2.1 and this rev of the patch ... a diff of
the diffs to make it easier to see what I tweaked:


==== diff -u nsContentIterator.cpp



 +static void
 +ContentToDOMPoint(nsIContent *aContent, nsIDOMNode **aParent, PRInt32
*aOffset)
 +{
++  if (!aParent || !aOffset)
++    return;
++
 +  *aParent = nsnull;
-+  aOffset  = 0;
++  *aOffset  = 0;
 +
 +  if (!aContent)
 +    return;
@@ -81,7 +82,7 @@
 +			    nsIDOMNode *aStartNode, PRInt32 aStartOffset,
 +			    nsIDOMNode *aEndNode,   PRInt32 aEndOffset)
 +{
-+  if (!aStartNode || !aEndNode || aContent)
++  if (!aStartNode || !aEndNode || !aContent)
 +    return PR_FALSE;
 +
 +  nsCOMPtr<nsIDOMNode> parentNode;
@@ -95,13 +96,13 @@
 +  if (!aIsPreMode)
 +    ++indx;
 +
-+  return (ComparePoints(aStartNode, aStartOffset, parentNode, indx) > 0) ||
-+	   (ComparePoints(aEndNode,   aEndOffset,   parentNode, indx) < 0);
++  return (ComparePoints(aStartNode, aStartOffset, parentNode, indx) <= 0) &&
++	   (ComparePoints(aEndNode,   aEndOffset,   parentNode, indx) >= 0);
 +}




==== diff -u nsGeneratedIterator.cpp


+@@ -626,6 +628,11 @@
+     NS_CONTENTITERATOR_CID,
+     nsnull,
+     CreateContentIterator },
++
++  { "Pre Content iterator",
++    NS_PRECONTENTITERATOR_CID,
++    nsnull,
++    CreatePreContentIterator },
+ 
+   { "Generated Content iterator",
+     NS_GENERATEDCONTENTITERATOR_CID,

Comment 13

[Joe Francis]

Comment on attachment 106412 [details] [diff] [review]
Patch rev 0.2.2 (Something that actually works.)

There is one problem I found in the patch which is pretty
serious but just a typo.

nsContentIterator.cpp
line 1114:
	ContentToDOMPoint(mFirst, getter_AddRefs(lastNode), &lastOffset);
should be:
	ContentToDOMPoint(mLast, getter_AddRefs(lastNode), &lastOffset);

My r= is contingent on that being fixed.

=============

There are several minor problems in the iter that predate Kin's patch.	
Nonetheless I think we should fix them now, since the patch is 
touching the very lines in question.

-------------
nsContentIterator.cpp
line 446:
    if (cData || !ContentHasChildren(startCon))
    {
      // No children, must be a text node or empty container.
should be:
    if (cData)
    {
      // It's a text node.

This is because we know that both the start and end container
are in startCon, and startOffset != endOffset.	The later
means startCon can't be empty.

-------------
line 466:
  if (!cChild) // no children, must be a text node
should be:
  if (!cChild) // no child at offset.  parent is a text node,
	       // or offset is past last child of container.

-------------
line 538:
    endCon->ChildAt(--indx,*getter_AddRefs(cChild));

    if (!cChild)  // offset after last child, last child is last node
    {
      endCon->ChildCount(indx);
      endCon->ChildAt(--indx,*getter_AddRefs(cChild)); 
      if (!cChild)
      {
	NS_NOTREACHED("nsContentIterator::nsContentIterator");
	return NS_ERROR_FAILURE; 
      }
    }

should be:
    endCon->ChildAt(--indx,*getter_AddRefs(cChild));

    if (!cChild)  // no child at offset!
    {
      NS_NOTREACHED("nsContentIterator::nsContentIterator");
      return NS_ERROR_FAILURE; 
    }

This is because we predecremented indx before calling ChildAt, 
so there must be a child there.  We already handled the case
where indx==0 up at line 513.  Kin, please double check me on this. 
It would be bad for me to be wrong about this.	:-)

Comment 14

[Akkana Peck]

The new Find code looks fine in theory, but when I test it, I see a difference.

The find test page is
http://www.mozilla.org/quality/browser/front-end/testcases/xpapps-gui/find-on-page/find-in-page.html
Go to the second set of tests, "Skipped nodes".
Note that when searching forward, it does not find the skipped link, but it also
doesn't find the word "nifty" in step two of the instructions (the occurrence
that's actually part of the instructions).  When searching backward, it does
find the word where it occurs in step 2 of the instructions.

When I test this on an older release build, the forward search finds the two
occurrences in the test pattern, then finds the invisible occurrence (sigh!  I
wonder if this is a regression?  It finds it both forward and backward), then
finds the occurrence in the instructions.

If you want, you could make nsFind.cpp use post order for both forward and
reverse cases (that's what it's doing now anyway) and file a bug to me to switch
it over to pre order (it may just be that the find algorithm needs tweaking to
take advantage of pre order; of course it was never tested with pre order since
that's never been available before).  Of course, if you get inspired to make it
all work, or if you think this is a problem in the iterator and not in the find
algorithm, your contribution is most welcome. :-)

(I should file a bug on it finding that invisible content anyway.)

Comment 15

[kinmoz]

Attachment: Patch rev 0.2.3 (Address comments from jfrancis)

> line 1114:
>	ContentToDOMPoint(mFirst, getter_AddRefs(lastNode), &lastOffset);
> should be:
>	ContentToDOMPoint(mLast, getter_AddRefs(lastNode), &lastOffset);


Ugh, thanks for catching that copy/paste error.


> This is because we predecremented indx before calling ChildAt, 
> so there must be a child there.  We already handled the case
> where indx==0 up at line 513.


Yeah, I was wondering why we had that fallback code ... it's gone now.

All other comments should be addressed by this patch.

I think the "nifty" problem akk saw, was due to the mLast typo jfrancis pointed
out. I hit that line several times while doing find through that doc.

FYI, the find code seems to find an invisible instance of "nifty" probably in
the noscript tag, but that was a bug prior to the iterator changes.

Comment 16

[Joe Francis]

Comment on attachment 106697 [details] [diff] [review]
Patch rev 0.2.3 (Address comments from jfrancis)

r=jfrancis
good job!

Comment 17

[Simon Fraser [no longer active]]

+ContentHasChildren(nsIContent *aContent)
+{
+  nsCOMPtr<nsIContent> child;
+  aContent->ChildAt(0,*getter_AddRefs(child));

Is it cheaper to get the child count?

+static void
+ContentToDOMPoint(nsIContent *aContent, nsIDOMNode **aParent, PRInt32 *aOffset)

"DOMPoint" infers visual coordinates to me. Maybe DOMOffset?

+ContentToDOMPoint(nsIContent *aContent, nsIDOMNode **aParent, PRInt32 *aOffset)
+{
+  if (!aParent || !aOffset)
+    return;
+
+  *aParent = nsnull;
+  *aOffset  = 0;
+
+  if (!aContent)
+    return;

Check aContent on the same line as aParent and aOffset?

+    endCon->ChildAt(--indx,*getter_AddRefs(cChild));
Space after comma. 


+#define NS_PRECONTENTITERATOR_CID \
+{/* {80D7E247-D4B8-45d7-BB59-6F1DD56F384C} */ \
+ 0x80d7e247, 0xd4b8, 0x45d7, { 0xbb, 0x59, 0x6f, 0x1d, 0xd5, 0x6f, 0x38, 0x4c } }

I noticed some content iterator CIDs in both nsContentCID.h and nsLayoutCID.h on
the branch. Might want to clean that up.

+  { "Pre Content iterator",
+    NS_PRECONTENTITERATOR_CID,
+    nsnull,
+    CreatePreContentIterator },

Contract IDs are always nice to have. Then you can avoid the #include and
static NS_DEFINE_CID stuff.

Comment 18

[Simon Fraser [no longer active]]

Comment on attachment 106697 [details] [diff] [review]
Patch rev 0.2.3 (Address comments from jfrancis)

sr=sfraser with comments.

Comment 19

[kinmoz]

Attachment: Patch rev 0.2.4 (Address comments from sfraser)

> Is it cheaper to get the child count?


Yes, thanks for pointing that out. I think the original code used |ChildAt()|
to avoid having to QI to a dom node to call |GetNumchildren()|.


> "DOMPoint" infers visual coordinates to me. Maybe DOMOffset?


Renamed to |ContentToParentOffset()|.


> Check aContent on the same line as aParent and aOffset?


The check is done at that point on purpose to allow |aParent| and |aOffset| to
be initialized.


> Space after comma.


Done.


> I noticed some content iterator CIDs in both nsContentCID.h
> and nsLayoutCID.h on the branch. Might want to clean that up.

> Contract IDs are always nice to have. Then you can avoid the
> #include and static NS_DEFINE_CID stuff.


I'd like to cleanup the 2 items mentioned above as a separate bug since it
affects lots of other files that aren't associated with fixing this bug.
I filed bug 181137 to address the 2 items as well as some other issues.

Comment 20

[kinmoz]

Attachment: Patch rev 0.2.5 (Add a call to RebuildIndex() in Init(node)))

I added a call to RebuildIndex() to explicitly build the indexes for both
traversal cases in the node version of Init().

The only change between rev 0.2.4 and 0.2.5 is this tidbit:


@@ -161,14 +161,17 @@
 +  }
 +  else
 +  {
-+    mFirst = GetDeepFirstChild(root, &mIndexes);
++    mFirst = GetDeepFirstChild(root, nsnull);
 +    mLast  = root;
 +  }
 +
    mCommonParent = root;
    mCurNode = mFirst;
++  RebuildIndexStack();
    return NS_OK;

Comment 21

[kinmoz]

Fix checked in to the TRUNK:

  content/base/public/nsIContentIterator.h          revision 1.10
  content/base/src/nsContentIterator.cpp            revision 1.53
  content/base/src/nsGeneratedIterator.cpp          revision 1.9
  content/build/nsContentCID.h                      revision 1.18
  content/build/nsContentModule.cpp                 revision 1.58
  embedding/components/find/src/nsFind.cpp          revision 1.16
  layout/html/style/src/nsFrameContentIterator.cpp  revision 3.3

Should appear in 11/21/02 8am TRUNK builds.

Comment 22

[sairuh (rarely reading bugmail)]

rs vrfy.