Try harder to make sure that blink::FrameTree::m_uniqueName is truly unique.

third_party/WebKit/Source/core/page/FrameTree.cpp

 /*
  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
  * Copyright (C) 2006 Apple Computer, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Library General Public License for more details.
  *
  * You should have received a copy of the GNU Library General Public License
  * along with this library; see the file COPYING.LIB.  If not, write to
  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  * Boston, MA 02110-1301, USA.
  */
 
 #include "core/page/FrameTree.h"
 
 #include "core/dom/Document.h"
 #include "core/frame/FrameClient.h"
 #include "core/frame/FrameView.h"
 #include "core/frame/LocalFrame.h"
 #include "core/frame/RemoteFrame.h"
 #include "core/frame/RemoteFrameView.h"
 #include "core/page/Page.h"
+#include "wtf/Assertions.h"
 #include "wtf/Vector.h"
 #include "wtf/text/CString.h"
 #include "wtf/text/StringBuilder.h"
 
 using std::swap;
 
 namespace blink {
 
 namespace {
 
 const unsigned invalidChildCount = ~0U;
 
 } // namespace
 
 FrameTree::FrameTree(Frame* thisFrame)
     : m_thisFrame(thisFrame)
     , m_scopedChildCount(invalidChildCount)
 {
 }
 
 FrameTree::~FrameTree()
 {
 }
 
-void FrameTree::setName(const AtomicString& name, const AtomicString& fallbackName)
+void FrameTree::setName(const AtomicString& name)
 {
     m_name = name;
-    if (!parent()) {
-        m_uniqueName = name;
-        return;
-    }
 
-    // Remove our old frame name so it's not considered in calculateUniqueNameForChildFrame.
+    // Remove our old frame name so it's not considered in calculateUniqueNameForChildFrame
+    // and ensureUniquenessOfUniqueName calls below.
     m_uniqueName = AtomicString();
 
-    m_uniqueName = parent()->tree().calculateUniqueNameForChildFrame(true, name, fallbackName);
+    // Calculate a new unique name based on inputs.
+    if (parent()) {
+        setUniqueName(
+            parent()->tree().calculateUniqueNameForChildFrame(m_thisFrame, name, nullAtom));
+    } else if (name.isEmpty() || !uniqueNameExists(name)) {
+        // Only main frame can have an empty unique name, so for main frames
+        // emptiness guarantees uniquness.
+        setUniqueName(name);
+    } else {
+        setUniqueName(ensureUniquenessOfUniqueName(
+            name, "<!--framePosition"));
+    }
 }
 
 void FrameTree::setPrecalculatedName(const AtomicString& name, const AtomicString& uniqueName)
 {
     if (!parent()) {
-        ASSERT(uniqueName == name);
+        DCHECK(uniqueName == name);
     } else {
-        ASSERT(!uniqueName.isEmpty());
+        DCHECK(!uniqueName.isEmpty());
     }
 
     m_name = name;
+
+    // TODO(lukasza): We would like to assert uniqueness below (i.e. by calling
+    // setUniqueName), but
+    // 1) uniqueness is currently violated by provisional/old frame pairs.
+    // 2) there is an unresolved race between 2 OOPIFs, that can result in a
+    //    non-unique |uniqueName| - see https://crbug.com/558680#c14.
     m_uniqueName = uniqueName;
 }
 
 Frame* FrameTree::parent() const
 {
     if (!m_thisFrame->client())
         return nullptr;
     return m_thisFrame->client()->parent();
 }
 
@@ skipping 29 matching lines @@
     return m_thisFrame->client()->firstChild();
 }
 
 Frame* FrameTree::lastChild() const
 {
     if (!m_thisFrame->client())
         return nullptr;
     return m_thisFrame->client()->lastChild();
 }
 
-bool FrameTree::uniqueNameExists(const AtomicString& name) const
+bool FrameTree::uniqueNameExists(const AtomicString& uniqueNameCandidate) const
 {
+    // This method is currently O(N), where N = number of frames in the tree.
+
+    // Before recalculating or checking unique name, we set m_uniqueName
+    // to an empty string (so the soon-to-be-removed name does not count
+    // as a collision).  This means that uniqueNameExists would return
+    // false positives when called with an empty |name|.
+    DCHECK(!uniqueNameCandidate.isEmpty());
+
     for (Frame* frame = top(); frame; frame = frame->tree().traverseNext()) {
-        if (frame->tree().uniqueName() == name)
+        if (frame->tree().uniqueName() == uniqueNameCandidate)
             return true;
     }
     return false;
 }
 
 AtomicString FrameTree::calculateUniqueNameForNewChildFrame(
     const AtomicString& name,
     const AtomicString& fallbackName) const
 {
-    return calculateUniqueNameForChildFrame(false, name, fallbackName);
+    AtomicString uniqueName = calculateUniqueNameForChildFrame(nullptr, name, fallbackName);
+
+    // Caller will likely set the name via setPrecalculatedName, which
+    // unfortunately cannot currently assert uniqueness of the name - let's
+    // therefore assert the uniqueness here.
+    DCHECK(!uniqueNameExists(uniqueName));
+
+    return uniqueName;
 }
 
-AtomicString FrameTree::calculateUniqueNameForChildFrame(
-    bool existingChildFrame,
-    const AtomicString& name,
-    const AtomicString& fallbackName) const
+AtomicString FrameTree::generateOldStyleMaybeUniqueName(bool existingChildFrame) const
 {
-    const AtomicString& requestedName = name.isEmpty() ? fallbackName : name;
-    if (!requestedName.isEmpty() && !uniqueNameExists(requestedName) && requestedName != "_blank")
-        return requestedName;
-
-    // Create a repeatable name for a child about to be added to us. The name must be
-    // unique within the frame tree. The string we generate includes a "path" of names
-    // from the root frame down to us. For this path to be unique, each set of siblings must
-    // contribute a unique name to the path, which can't collide with any HTML-assigned names.
-    // We generate this path component by index in the child list along with an unlikely
-    // frame name that can't be set in HTML because it collides with comment syntax.
-
     const char framePathPrefix[] = "<!--framePath ";
     const int framePathPrefixLength = 14;
     const int framePathSuffixLength = 3;
 
     // Find the nearest parent that has a frame with a path in it.
     HeapVector<Member<Frame>, 16> chain;
     Frame* frame;
     for (frame = m_thisFrame; frame; frame = frame->tree().parent()) {
         if (frame->tree().uniqueName().startsWith(framePathPrefix))
             break;
         chain.append(frame);
     }
     StringBuilder uniqueName;
     uniqueName.append(framePathPrefix);
     if (frame) {
         uniqueName.append(frame->tree().uniqueName().getString().substring(framePathPrefixLength,
             frame->tree().uniqueName().length() - framePathPrefixLength - framePathSuffixLength));
     }
     for (int i = chain.size() - 1; i >= 0; --i) {
         frame = chain[i];
         uniqueName.append('/');
         uniqueName.append(frame->tree().uniqueName());
     }
 
     uniqueName.appendLiteral("/<!--frame");
     uniqueName.appendNumber(childCount() - (existingChildFrame ? 1 : 0));
     uniqueName.appendLiteral("-->-->");
 
+    // NOTE: This name might not be unique - see http://crbug.com/588800.
     return uniqueName.toAtomicString();
 }
 
+String FrameTree::generateLikelyUniqueSuffix(Frame* child) const
+{
+    // This method is currently O(N), where N = number of frames in the tree.
+
+    StringBuilder likelyUniqueSuffixBuilder;
+    likelyUniqueSuffixBuilder.append("<!--framePosition");
+
+    if (!child) {

[dcheng, 2016/05/31 19:57:47]

When will child be null?

[Łukasz Anforowicz, 2016/05/31 23:50:20]

|child| will be null in cases when we need to calculate unique name *before* a
child frame is created (i.e. before we call m_client->createChildFrame).  Such
cases have been introduced by https://codereview.chromium.org/1635873003/
(Replicating WebFrame::uniqueName across renderers).  Right now the only call to
FrameTree::calculateUniqueNameForNewChildFrame is in
WebLocalFrameImpl::createChildFrame.

+        likelyUniqueSuffixBuilder.append('-');
+        likelyUniqueSuffixBuilder.appendNumber(childCount());
+        child = m_thisFrame;
+    }
+
+    while (child->tree().parent()) {
+        int numberOfSiblingsBeforeChild = 0;
+        Frame* sibling = child->tree().previousSibling();
+        while (sibling) {
+            sibling = sibling->tree().previousSibling();
+            numberOfSiblingsBeforeChild++;
+        }
+
+        likelyUniqueSuffixBuilder.append('-');
+        likelyUniqueSuffixBuilder.appendNumber(numberOfSiblingsBeforeChild);
+
+        child = child->tree().parent();
+    }
+
+    // NOTE: The generated suffix is not guaranteed to be unique, but should
+    // have a better chance of being unique than the string generated by
+    // generateOldStyleMaybeUniqueName, because we embed extra information
+    // into the string:
+    // 1) we walk the full chain of ancestors, all the way to the main frame
+    // 2) we use frame-position-within-parent (aka |numberOfSiblingsBeforeChild|)
+    return likelyUniqueSuffixBuilder.toString();
+}
+
+AtomicString FrameTree::ensureUniquenessOfUniqueName(
+    const AtomicString& notYetUniqueName,
+    const String& likelyUniqueSuffix) const
+{
+    // Verify that we are not doing unnecessary work.
+    DCHECK(uniqueNameExists(notYetUniqueName));
+
+    // We want unique name to be stable across page reloads - this is why
+    // we use a deterministic |numberOfTries| rather than a random number
+    // (a random number would be more likely to avoid a collision, but
+    // would change after every page reload).
+    int numberOfTries = 0;
+
+    // Keep trying |notYetUniqueName| + |likelyUniqueSuffix| + |numberOfTries|
+    // concatenations until we get a truly unique name.
+    AtomicString uniqueNameCandidate;
+    do {
+        StringBuilder uniqueNameBuilder;
+        uniqueNameBuilder.append(notYetUniqueName);
+        uniqueNameBuilder.append(likelyUniqueSuffix);
+        uniqueNameBuilder.append('/');
+        uniqueNameBuilder.appendNumber(numberOfTries++);
+        uniqueNameBuilder.append("-->");
+
+        uniqueNameCandidate = uniqueNameBuilder.toAtomicString();
+    } while (uniqueNameExists(uniqueNameCandidate));
+    return uniqueNameCandidate;
+}
+
+AtomicString FrameTree::calculateUniqueNameForChildFrame(
+    Frame* child,
+    const AtomicString& assignedName,
+    const AtomicString& fallbackName) const
+{
+    // Try to use |assignedName| (i.e. window.name or iframe.name) or |fallbackName| if possible.
+    const AtomicString& requestedName = assignedName.isEmpty() ? fallbackName : assignedName;
+    if (!requestedName.isEmpty() && !uniqueNameExists(requestedName) && requestedName != "_blank")
+        return requestedName;
+
+    AtomicString uniqueNameCandidate = generateOldStyleMaybeUniqueName(child);
+    if (!uniqueNameExists(uniqueNameCandidate))
+        return uniqueNameCandidate;
+
+    return ensureUniquenessOfUniqueName(uniqueNameCandidate, generateLikelyUniqueSuffix(child));
+
+    // Description of the current unique name format

[Łukasz Anforowicz, 2016/05/27 16:55:27]

I am not sure if I am happy with the comment here:

1. This is based on reverse-engineering and it is quite likely that I've made
   some mistakes.

2. For ultimate format answer, one has to inspect the code anyway.

So - we might want to discuss:

A) whether to keep the documentation at all

B) whether to have the documentation here or elsewhere (e.g. in the doc linked
from the bug)

C) whether to tweak the code to make the documentation/format prettier, at the
cost of making the code slightly more complex (i.e. oldGeneratedName doesn't
apply to main frame - for non-unique main frame's name the code concatenates
assignedName and newUniqueSuffix).

My opinion:

A) no opinion

B) slight preference for keeping the doc next to the code

C) strong preference toward keeping the code simple
I can also move the description to the doc and link from here.

[dcheng, 2016/05/31 19:57:47]

This is fine. It's far better than not having anything at all.

[Łukasz Anforowicz, 2016/05/31 23:50:20]

Acknowledged.

+    // ---------------------------------------------
+    //
+    // Changing the format of unique name is undesirable, because it breaks
+    // backcompatibility of session history (which stores unique names
+    // generated in the past on user's disk).  This incremental,
+    // backcompatibility-aware approach has resulted so far in the following
+    // rather baroque format... :
+    //
+    //   uniqueName ::= <assignedName> | <generatedName>
+    //                 (generatedName is used if assignedName is
+    //                 1) non-unique / conflicts with other frame's unique name or
+    //                 2) assignedName is empty for a non-main frame)
+    //
+    //   assignedName ::= value of iframe's name attribute
+    //                 or value assigned to window.name
+    //
+    //   generatedName ::= oldGeneratedName newUniqueSuffix?
+    //                  (newUniqueSuffix is only present if oldGeneratedName was
+    //                  not unique after all)
+    //
+    //   oldGeneratedName ::= "<!--framePath //" ancestorChain "/<!--frame" childCount "-->-->"
+    //                  (main frame is special - oldGeneratedName for main frame
+    //                  is always the frame's assignedName)
+    //
+    //   childCount ::= current number of siblings
+    //
+    //   ancestorChain ::= concatenated unique names of ancestor chain,
+    //                     terminated on the first ancestor (if any) starting with "<!--framePath"
+    //                     each ancestor's unique name is separated by "/" character
+    //   ancestorChain example1: "grandparent/parent"
+    //  (ancestor's unique names :   #1--^   | #2-^ )
+    //   ancestorChain example2: "<!--framePath //foo/bar/<!--frame42-->-->/blah/foobar"
+    //  (ancestor's unique names :        ^--#1--^                         | #2 | #3-^ )
+    //
+    //   newUniqueSuffix ::= "<!--framePosition" framePosition "/" retryNumber "-->"
+    //
+    //   framePosition ::= "-" numberOfSiblingsBeforeChild [ framePosition-forParent? ]
+    //                   | <empty string for main frame>
+    //
+    //   retryNumber ::= smallest non-negative integer resulting in unique name
+}
+
+void FrameTree::setUniqueName(const AtomicString& uniqueName)
+{
+    // Main frame is the only frame that can have an empty unique name.
+    if (parent()) {
+        DCHECK(!uniqueName.isEmpty() && !uniqueNameExists(uniqueName));
+    } else {
+        DCHECK(uniqueName.isEmpty() || !uniqueNameExists(uniqueName));
+    }
+
+    m_uniqueName = uniqueName;
+}
+
 Frame* FrameTree::scopedChild(unsigned index) const
 {
     unsigned scopedIndex = 0;
     for (Frame* child = firstChild(); child; child = child->tree().nextSibling()) {
         if (child->client()->inShadowTree())
             continue;
         if (scopedIndex == index)
             return child;
         scopedIndex++;
     }
@@ skipping 223 matching lines @@
 {
     if (!frame) {
         printf("Null input frame\n");
         return;
     }
 
     printFrames(frame->tree().top(), frame, 0);
 }
 
 #endif