Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1372153007:
[Editing] Speed up PositionIterator::computePosition from O(n) to O(1). (Closed)
Description[Editing] Speed up PositionIterator::computePosition
PositionIterator::computePosition is slow if position is before a node.
That is because |PositionTemplate<Strategy>::inParentBeforeNode(node)|
calculates index of |node| by counting siblings, which takes O(n) time.
To avoid that, this CL let PositionIterator to remember and count index within
increment() because the function usually moves position to next sibling.
Then, computePosition uses the index instead of inParentBeforeNode so it takes
O(1) time.
-- Implementation detail --
|Vector<int> m_offsetsInAnchorNode| stores indexes within each anchor node in
a path from root to position.
|m_depthToAnchorNode| is a current depth of anchor node.
To delay initialize each index(because we may not use all index value instantly),
we initialize |m_offsetsInAnchorNode| -1 and initialize if it needs in increment().
Since this implementation supposes DOM tree doesn't change in traversal, I
introduce |m_domTreeVersion| to check tree is not changed. This assumption works
because PositionIterator is used on stack and DOM mutaion must not happen in
traversal.
BUG=514193, 543779, 545170
Committed: https://crrev.com/b6d97fc86439a6a4d164ad8caf588d67d5f635e2
Cr-Commit-Position: refs/heads/master@{#355517}
Patch Set 1 #
Total comments: 20
Patch Set 2 : update #
Total comments: 33
Patch Set 3 : Update #
Total comments: 12
Patch Set 4 : Update #
Total comments: 2
Patch Set 5 : Update assert #
Messages
Total messages: 29 (7 generated)
yoichio@chromium.org changed reviewers: + hajimehoshi@chromium.org, yosin@chromium.org
https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:38: m_depthToAnchorNode = 0; m_depthToAnchorNode can be initialized the same way as the other member variables. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:41: // but let delay to calculate the index until it is needed. let's? https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:60: { m_depthToAnchorNode is not initialized in this case. Is this OK? https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:105: // We have following DOM tree: Assume that we have the following DOM tree: https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:115: // Let |anchor| as |m_anchorNode| and No breaking line here. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:120: // Let |anchor| is A and |child| is B, I prefer least breaking-lines, so in this case, I wouldn't break the line after the comma. WDYT? https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:172: // We have following DOM tree: ditto https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/PositionIterator.h (right): https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.h:54: // increment() takes O(1) other than increment into new parent. I don't understand this sentence. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.h:55: // In later case, it takes time of O(<number of childlen>) but the case nit: In the latter case https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.h:60: // In later case, it takes time of O(<number of childlen>). nit: ditto
Rather than remembering index in container node, it is better to return |BeforeAnchor| type of position.
BTW, do we really need to use PositionIterator? It is essentially doing nextPositionOf()/previousPosition().
On 2015/10/08 05:19:17, Yosi_UTC9 wrote: > Rather than remembering index in container node, it is better > to return |BeforeAnchor| type of position. Assume that we have "<span a><span b></span></span>". Replacing inParentBeforeNode(<span b>) with BeforeAnchor(<span b>) seems good because (<span a>, 0) equals to before(<span b>) visually. However, it is not because isVisuallyEquivalentCandidateAlgorithm and localCaretRectOfPosition refer anchorNode(). That means (<span a>, 0) and before(<span b>) result different in those functions. That is if <span b> is display:none, before(<span b>) is not candidate but (<span a>, 0) is candidate. This is very strange so we should fix the behavior? in_reply_to: 5639274879778816
On 2015/10/08 06:07:27, Yosi_UTC9 wrote: > BTW, do we really need to use PositionIterator? > It is essentially doing nextPositionOf()/previousPosition(). It calls Traversal::countChildren(*node), which is O(n).
On 2015/10/08 at 07:10:27, yoichio wrote: > On 2015/10/08 06:07:27, Yosi_UTC9 wrote: > > BTW, do we really need to use PositionIterator? > > It is essentially doing nextPositionOf()/previousPosition(). > > It calls Traversal::countChildren(*node), which is O(n). Yes, first we change nextPositionOf()/previousPosition() to return BeforeAnchor position rather than OffsetInAnchor position. Intention of introducing PositionAnchorType is get rid of using OffsetInAnchor other than Text node.
On 2015/10/08 at 07:09:46, yoichio wrote: > On 2015/10/08 05:19:17, Yosi_UTC9 wrote: > > Rather than remembering index in container node, it is better > > to return |BeforeAnchor| type of position. > > Assume that we have "<span a><span b></span></span>". > Replacing inParentBeforeNode(<span b>) with BeforeAnchor(<span b>) seems good because > (<span a>, 0) equals to before(<span b>) visually. > However, it is not because isVisuallyEquivalentCandidateAlgorithm and localCaretRectOfPosition > refer anchorNode(). That means (<span a>, 0) and before(<span b>) result different in > those functions. > > That is if <span b> is display:none, before(<span b>) is not candidate > but (<span a>, 0) is candidate. > This is very strange so we should fix the behavior? > in_reply_to: 5639274879778816 This means implementations isVisuallyEquivalentCandidateAlgorithm and localCaretRectOfPosition are wrong. They should return same result for (<span a>, 0) and before(<span b>).
Description was changed from ========== [Editing] Speed up PositionIterator::computePosition PositionIterator::computePosition is slow if position is before a node. That is because |PositionTemplate<Strategy>::inParentBeforeNode(node)| calculates index of |node| by counting siblings, which takes O(n) time. To avoid that, this CL let PositionIterator to remember and count index within increment() because the function usually moves position to next sibling. Then, computePosition uses the index instead of inParentBeforeNode so it takes O(1) time. -- Implementation detail -- |Vector<int> m_offsetsInAnchorNode| stores indexes within each anchor node in a path from root to position. |m_depthToAnchorNode| is a current depth of anchor node. To delay initialize each index(because we may not use all index value instantly), we initialize |m_offsetsInAnchorNode| -1 and initialize if it needs in increment(). Since this implementation supposes DOM tree doesn't change in traversal, I introduce |m_domTreeVersion| to check tree is not changed. This assumption works because PositionIterator is used on stack and DOM mutaion must not happen in traversal. BUG=514193 ========== to ========== [Editing] Speed up PositionIterator::computePosition PositionIterator::computePosition is slow if position is before a node. That is because |PositionTemplate<Strategy>::inParentBeforeNode(node)| calculates index of |node| by counting siblings, which takes O(n) time. To avoid that, this CL let PositionIterator to remember and count index within increment() because the function usually moves position to next sibling. Then, computePosition uses the index instead of inParentBeforeNode so it takes O(1) time. -- Implementation detail -- |Vector<int> m_offsetsInAnchorNode| stores indexes within each anchor node in a path from root to position. |m_depthToAnchorNode| is a current depth of anchor node. To delay initialize each index(because we may not use all index value instantly), we initialize |m_offsetsInAnchorNode| -1 and initialize if it needs in increment(). Since this implementation supposes DOM tree doesn't change in traversal, I introduce |m_domTreeVersion| to check tree is not changed. This assumption works because PositionIterator is used on stack and DOM mutaion must not happen in traversal. BUG=514193,543779 ==========
> This means implementations isVisuallyEquivalentCandidateAlgorithm and localCaretRectOfPosition are > wrong. They should return same result for (<span a>, 0) and before(<span b>). isVisuallyEquivalentCandidateAlgorithm are used from following functions at least: nextCandidate, previousCandidate, nextVisuallyDistinctCandidate, previousVisuallyDistinctCandidate You know all these functions are core of VisibleUnits.h, which is critical for Selection and Editing. Thus I guess cleaning up isVisuallyEquivalentCandidateAlgorithm about PositionAnchorType may be huge. This CL fixes stable-blocker and needs to be merged. How about to ship this in M47 merged and clean up step by step?
yoichio@chromium.org changed reviewers: + tkent@chromium.org
Add tkent@ as second opinion.
On 2015/10/20 at 07:00:44, yoichio wrote: > This CL fixes stable-blocker and needs to be merged. > How about to ship this in M47 merged and clean up step by step? This approach looks reasonable to me. We have a significant regression affecting users, and we should fix it ASAP with lower risk.
Patchset #2 (id:20001) has been deleted
Ping. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:38: m_depthToAnchorNode = 0; On 2015/10/08 at 04:57:27, hajimehoshi wrote: > m_depthToAnchorNode can be initialized the same way as the other member variables. Done. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:41: // but let delay to calculate the index until it is needed. On 2015/10/08 at 04:57:27, hajimehoshi wrote: > let's? Done. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:60: { On 2015/10/08 at 04:57:27, hajimehoshi wrote: > m_depthToAnchorNode is not initialized in this case. Is this OK? No. Done. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:105: // We have following DOM tree: On 2015/10/08 at 04:57:27, hajimehoshi wrote: > Assume that we have the following DOM tree: Done. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:115: // Let |anchor| as |m_anchorNode| and On 2015/10/08 at 04:57:27, hajimehoshi wrote: > No breaking line here. No. I prefer comment in 80 columns. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:120: // Let |anchor| is A and |child| is B, On 2015/10/08 at 04:57:27, hajimehoshi wrote: > I prefer least breaking-lines, so in this case, I wouldn't break the line after the comma. WDYT? Ditto. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.cpp:172: // We have following DOM tree: On 2015/10/08 at 04:57:27, hajimehoshi wrote: > ditto Done. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/PositionIterator.h (right): https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.h:54: // increment() takes O(1) other than increment into new parent. On 2015/10/08 at 04:57:27, hajimehoshi wrote: > I don't understand this sentence. Update https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.h:55: // In later case, it takes time of O(<number of childlen>) but the case On 2015/10/08 at 04:57:27, hajimehoshi wrote: > nit: In the latter case Done. https://codereview.chromium.org/1372153007/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/PositionIterator.h:60: // In later case, it takes time of O(<number of childlen>). On 2015/10/08 at 04:57:27, hajimehoshi wrote: > nit: ditto Done.
https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:40: // Each m_offsetsInAnchorNode[offset] should be index of node, should be an index of node in parent node. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:41: // but let's delay to calculate the index until it is needed. Please add a reason why we want to postpone. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:42: m_offsetsInAnchorNode.append(-1); Could you name |-1|? https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:43: m_depthToAnchorNode++; nit: prefer prefix: |++m_depthToAnchorNode|. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:45: if (m_nodeAfterPositionInAnchor) nit: early return? https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:59: , m_domTreeVersion(0) m_domTreeVersion(anchorNode->document().domTreeVersion()) https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:67: ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion()); Having function for checking is better, e.g. |EphemeralRange|. We may want to have base class for it to share code between |PositionIterator| and |EphemeralRange|, in another patch. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:70: ASSERT(m_offsetsInAnchorNode[m_depthToAnchorNode] >= 0); Once we have |kInvalidOffset|, or another, we can write ASSERT(m_offsetInAnchorNode[m_depthToAnchorNode] != kInvalidOffset); https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:99: // FIXME: This should be s/FIXME/TODO(yoichio)/ https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:100: // PositionTemplate<Strategy>(m_anchorNode, PositionAnchorType::BeforeAnchor); Not sure meaning of this comment. Do you try to say "equivalent to BeforeAnchor"? https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:143: m_depthToAnchorNode++; nit: prefer prefix form: |++m_depthToAnchorNode|. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:144: if (m_depthToAnchorNode >= m_offsetsInAnchorNode.size()) m_depthToAnchorNode == m_offsetsInAnchorNode.size()? Do we have m_depthToAnchorNode > m_offsetsInAnchorNode.size()? Should we fill zero(?)? https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:145: m_offsetsInAnchorNode.append(0); why zero? https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:170: m_depthToAnchorNode--; nit: prefer prefix form. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:176: m_offsetsInAnchorNode[m_depthToAnchorNode]++; nit: prefer prefix form. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.h (right): https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.h:77: // TOOD: Replace |m_offsetInAnchor| with nit: s/TODO:/TODO(yoichio):/ https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.h:78: // m_offsetOfNodeAfterPositionInAnchor[m_depthToAnchorNode]. Not sure meaning of this comment.
https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:40: // Each m_offsetsInAnchorNode[offset] should be index of node, On 2015/10/21 at 06:01:15, Yosi_UTC9 wrote: > should be an index of node in parent node. Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:41: // but let's delay to calculate the index until it is needed. On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > Please add a reason why we want to postpone. Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:42: m_offsetsInAnchorNode.append(-1); On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > Could you name |-1|? Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:43: m_depthToAnchorNode++; On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > nit: prefer prefix: |++m_depthToAnchorNode|. Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:45: if (m_nodeAfterPositionInAnchor) On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > nit: early return? We need initialize |m_OffsetsInAnchorNode| and |m_depthToAnchorNode| though |m_nodeAfterPositionInAnchor| is null. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:59: , m_domTreeVersion(0) On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > m_domTreeVersion(anchorNode->document().domTreeVersion()) Because anchorNode is null we can't. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:67: ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion()); On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > Having function for checking is better, e.g. |EphemeralRange|. > We may want to have base class for it to share code between |PositionIterator| > and |EphemeralRange|, in another patch. Add comment. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:70: ASSERT(m_offsetsInAnchorNode[m_depthToAnchorNode] >= 0); On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > Once we have |kInvalidOffset|, or another, we can write > ASSERT(m_offsetInAnchorNode[m_depthToAnchorNode] != kInvalidOffset); Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:99: // FIXME: This should be On 2015/10/21 at 06:01:15, Yosi_UTC9 wrote: > s/FIXME/TODO(yoichio)/ Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:100: // PositionTemplate<Strategy>(m_anchorNode, PositionAnchorType::BeforeAnchor); On 2015/10/21 at 06:01:15, Yosi_UTC9 wrote: > Not sure meaning of this comment. > Do you try to say "equivalent to BeforeAnchor"? Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:143: m_depthToAnchorNode++; On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > nit: prefer prefix form: |++m_depthToAnchorNode|. Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:144: if (m_depthToAnchorNode >= m_offsetsInAnchorNode.size()) On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > m_depthToAnchorNode == m_offsetsInAnchorNode.size()? > Do we have m_depthToAnchorNode > m_offsetsInAnchorNode.size()? > Should we fill zero(?)? Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:145: m_offsetsInAnchorNode.append(0); On 2015/10/21 at 06:01:15, Yosi_UTC9 wrote: > why zero? Because m_nodeAfterPositionInAnchor is firstChild of parent anchornode. Read this code block and comment. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:170: m_depthToAnchorNode--; On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > nit: prefer prefix form. Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:176: m_offsetsInAnchorNode[m_depthToAnchorNode]++; On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > nit: prefer prefix form. Done. https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.h (right): https://codereview.chromium.org/1372153007/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.h:78: // m_offsetOfNodeAfterPositionInAnchor[m_depthToAnchorNode]. On 2015/10/21 at 06:01:16, Yosi_UTC9 wrote: > Not sure meaning of this comment. Removed.
https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:71: ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion()); Let's introduce isTreeClean() or another name rather than repeating this equality expression. https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:139: // Case #1. Case #1: Move to firstChild() https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:223: m_depthToAnchorNode++; nit: prefer prefix form. https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:227: m_offsetsInAnchorNode[m_depthToAnchorNode] = m_offsetInAnchor; Optional: early return? https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:258: ++m_depthToAnchorNode; Optional: early return? https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:265: m_offsetInAnchor = uncheckedPreviousOffset(m_anchorNode, m_offsetInAnchor); Optional: early return?
https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:71: ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion()); On 2015/10/22 at 05:26:09, Yosi_UTC9 wrote: > Let's introduce isTreeClean() or another name rather than repeating > this equality expression. Done. https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:139: // Case #1. On 2015/10/22 at 05:26:09, Yosi_UTC9 wrote: > Case #1: Move to firstChild() Done. https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:223: m_depthToAnchorNode++; On 2015/10/22 at 05:26:09, Yosi_UTC9 wrote: > nit: prefer prefix form. Done. https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:227: m_offsetsInAnchorNode[m_depthToAnchorNode] = m_offsetInAnchor; On 2015/10/22 at 05:26:09, Yosi_UTC9 wrote: > Optional: early return? Done. https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:258: ++m_depthToAnchorNode; On 2015/10/22 at 05:26:09, Yosi_UTC9 wrote: > Optional: early return? Done. https://codereview.chromium.org/1372153007/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:265: m_offsetInAnchor = uncheckedPreviousOffset(m_anchorNode, m_offsetInAnchor); On 2015/10/22 at 05:26:09, Yosi_UTC9 wrote: > Optional: early return? Done.
Description was changed from ========== [Editing] Speed up PositionIterator::computePosition PositionIterator::computePosition is slow if position is before a node. That is because |PositionTemplate<Strategy>::inParentBeforeNode(node)| calculates index of |node| by counting siblings, which takes O(n) time. To avoid that, this CL let PositionIterator to remember and count index within increment() because the function usually moves position to next sibling. Then, computePosition uses the index instead of inParentBeforeNode so it takes O(1) time. -- Implementation detail -- |Vector<int> m_offsetsInAnchorNode| stores indexes within each anchor node in a path from root to position. |m_depthToAnchorNode| is a current depth of anchor node. To delay initialize each index(because we may not use all index value instantly), we initialize |m_offsetsInAnchorNode| -1 and initialize if it needs in increment(). Since this implementation supposes DOM tree doesn't change in traversal, I introduce |m_domTreeVersion| to check tree is not changed. This assumption works because PositionIterator is used on stack and DOM mutaion must not happen in traversal. BUG=514193,543779 ========== to ========== [Editing] Speed up PositionIterator::computePosition PositionIterator::computePosition is slow if position is before a node. That is because |PositionTemplate<Strategy>::inParentBeforeNode(node)| calculates index of |node| by counting siblings, which takes O(n) time. To avoid that, this CL let PositionIterator to remember and count index within increment() because the function usually moves position to next sibling. Then, computePosition uses the index instead of inParentBeforeNode so it takes O(1) time. -- Implementation detail -- |Vector<int> m_offsetsInAnchorNode| stores indexes within each anchor node in a path from root to position. |m_depthToAnchorNode| is a current depth of anchor node. To delay initialize each index(because we may not use all index value instantly), we initialize |m_offsetsInAnchorNode| -1 and initialize if it needs in increment(). Since this implementation supposes DOM tree doesn't change in traversal, I introduce |m_domTreeVersion| to check tree is not changed. This assumption works because PositionIterator is used on stack and DOM mutaion must not happen in traversal. BUG=514193,543779, 545170 ==========
lgtm w/ small nits https://codereview.chromium.org/1372153007/diff/80001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/80001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:124: ASSERT(isTreeClean()); nit: We should assert start of function. Since m_anchorNode == nullptr doesn't mean PositionIterator for null position. e.g. we can have m_anchorNode == nullptr after multiple increment()/decrement() calls.
The CQ bit was checked by yoichio@chromium.org
Thanks. https://codereview.chromium.org/1372153007/diff/80001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/PositionIterator.cpp (right): https://codereview.chromium.org/1372153007/diff/80001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/PositionIterator.cpp:124: ASSERT(isTreeClean()); On 2015/10/22 at 07:20:35, Yosi_UTC9 wrote: > nit: We should assert start of function. > Since m_anchorNode == nullptr doesn't mean PositionIterator for null position. > e.g. we can have m_anchorNode == nullptr after multiple increment()/decrement() calls. Done.
The patchset sent to the CQ was uploaded after l-g-t-m from yosin@chromium.org Link to the patchset: https://codereview.chromium.org/1372153007/#ps100001 (title: "Update assert")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1372153007/100001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1372153007/100001
Message was sent while issue was closed.
Committed patchset #5 (id:100001)
Message was sent while issue was closed.
Patchset 5 (id:??) landed as https://crrev.com/b6d97fc86439a6a4d164ad8caf588d67d5f635e2 Cr-Commit-Position: refs/heads/master@{#355517} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
