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

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

Index: third_party/WebKit/Source/core/page/FrameTree.cpp
diff --git a/third_party/WebKit/Source/core/page/FrameTree.cpp b/third_party/WebKit/Source/core/page/FrameTree.cpp
index c218e8b0f95a0bb7b3a1206b5158dc434674bcae..da272d97a28a4279a38303a19bd02ae4c94d0ca1 100644
--- a/third_party/WebKit/Source/core/page/FrameTree.cpp
+++ b/third_party/WebKit/Source/core/page/FrameTree.cpp
@@ -27,6 +27,7 @@
 #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"
@@ -51,29 +52,43 @@ 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;
 }
 
@@ -123,10 +138,18 @@ Frame* FrameTree::lastChild() const
     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;
@@ -136,25 +159,18 @@ AtomicString FrameTree::calculateUniqueNameForNewChildFrame(
     const AtomicString& name,
     const AtomicString& fallbackName) const
 {
-    return calculateUniqueNameForChildFrame(false, name, fallbackName);
-}
+    AtomicString uniqueName = calculateUniqueNameForChildFrame(nullptr, name, fallbackName);
 
-AtomicString FrameTree::calculateUniqueNameForChildFrame(
-    bool existingChildFrame,
-    const AtomicString& name,
-    const AtomicString& fallbackName) const
-{
-    const AtomicString& requestedName = name.isEmpty() ? fallbackName : name;
-    if (!requestedName.isEmpty() && !uniqueNameExists(requestedName) && requestedName != "_blank")
-        return requestedName;
+    // 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));
 
-    // 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.
+    return uniqueName;
+}
 
+AtomicString FrameTree::generateOldStyleMaybeUniqueName(bool existingChildFrame) const
+{
     const char framePathPrefix[] = "<!--framePath ";
     const int framePathPrefixLength = 14;
     const int framePathSuffixLength = 3;
@@ -183,9 +199,146 @@ AtomicString FrameTree::calculateUniqueNameForChildFrame(
     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;