// Copyright 2017 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef THIRD_PARTY_BLINK_PUBLIC_COMMON_UNIQUE_NAME_UNIQUE_NAME_HELPER_H_
#define THIRD_PARTY_BLINK_PUBLIC_COMMON_UNIQUE_NAME_UNIQUE_NAME_HELPER_H_

#include <string>
#include <vector>

#include "base/macros.h"
#include "base/strings/string_piece.h"
#include "third_party/blink/public/common/common_export.h"

namespace blink {

// Frame helper that manages the details of generating a quasi-stable unique
// name for the frame. The name is unique within a page, and is used for:
// - matching up session history items with recreated frames
// - web test results
//
// Description of the current unique name format
// ---------------------------------------------
// Changing the format of unique name has a high cost, because it breaks
// backwards compatibility of session history (which stores unique names
// generated in the past on user's disk). The evolution of unique name in a
// mostly backwards-compatible way has resulted in the rather baroque format...
//
// uniqueName ::= <nullForMainFrame> | <assignedName> | <generatedName>
// Note: generatedName is used if assignedName is non-unique / conflicts with
// other frame's unique name.
//
// assignedName ::= value of iframe's name attribute
//                  or value assigned to window.name
// Note: The name must be assigned *before* the first real commit: afterwards,
// the unique name is immutable.
//
// generatedName ::= oldGeneratedName newUniqueSuffix?
// Note: newUniqueSuffix is only present if oldGeneratedName is not unique.
//
// oldGeneratedName ::= "<!--framePath //" ancestorChain
//                      "/<!--frame" childCount "-->-->"
// Note: oldGeneratedName is generated by the internal GenerateCandidate()
// method.
//
// 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
// Note: Two examples are provided below, with each portion of the name from a
// distinct ancestor annotated.
//
// Example ancestor chain #1:
//     "grandparent/parent"
//     |    #1     |  #2  |
// Example ancestor chain #2:
//     "<!--framePath //foo/bar/<!--frame42-->-->/blah/foobar"
//     |                    #1                   | #2 |  #3  |
//
// newUniqueSuffix ::= "<!--framePosition" framePosition "/" retryNumber "-->"
//
// framePosition ::= "-" numberOfSiblingsBeforeChild
//                   [ framePosition-forParent? ]
//
// retryNumber ::= smallest non-negative integer resulting in unique name
class BLINK_COMMON_EXPORT UniqueNameHelper {
 public:
  // Adapter class so UniqueNameHelper can be used with both RenderFrameImpl and
  // ExplodedFrameState.
  class BLINK_COMMON_EXPORT FrameAdapter {
   public:
    FrameAdapter() {}
    virtual ~FrameAdapter();

    virtual bool IsMainFrame() const = 0;
    virtual bool IsCandidateUnique(base::StringPiece name) const = 0;
    // Returns the number of sibling frames of this frame. Note this should not
    // include this frame in the count.
    virtual int GetSiblingCount() const = 0;
    virtual int GetChildCount() const = 0;
    // Sets the reference point for iterations that walk up the frame tree.
    enum class BeginPoint {
      // This should be the default: it indicates the logical iteration
      // operation began on this frame and the walking logic should retrieve the
      // parent frame as normal.
      kParentFrame,
      // For implementing the pending child frame adapter, which delegates to
      // its future parent's FrameAdapter. Walking up the tree should not skip
      // this frame; instead it should treat this frame as the parent, since the
      // logical iteration began with a pending child frame.
      kThisFrame,
    };
    // Returns a vector of the strings representing the name of each frame in
    // the chain from this frame to the root frame. |begin_point| indicates the
    // reference point for starting the collection. |should_stop| is a
    // boolean predicate that indicates when to stop collection of names.
    virtual std::vector<std::string> CollectAncestorNames(
        BeginPoint begin_point,
        bool (*should_stop)(base::StringPiece)) const = 0;
    // Returns a vector of ints representing the child index of each frame in
    // the chain from this frame to the root.
    virtual std::vector<int> GetFramePosition(BeginPoint begin_point) const = 0;

   private:
    DISALLOW_COPY_AND_ASSIGN(FrameAdapter);
  };

  struct Replacement {
    Replacement(std::string old_name, std::string new_name);

    const std::string old_name;
    const std::string new_name;
  };

  explicit UniqueNameHelper(FrameAdapter* frame);
  ~UniqueNameHelper();

  // Returns the generated unique name.
  const std::string& value() const { return unique_name_; }

  // Used to propagate an already calculated unique name.
  //
  // TODO(lukasza): It would be nice to assert uniqueness of the propagated
  // name here 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 unique name: see https://crbug.com/558680#c14.
  void set_propagated_name(const std::string& name) { unique_name_ = name; }

  // Note: when creating a new child frame, the unique name needs to be
  // calculated before the child frame is created. To avoid this chicken and
  // egg problem, this method is designed to be called on the *parent* frame of
  // the future new child frame and return the value the new child frame should
  // use.
  //
  // |is_created_by_script| indicates if the new child is created via javascript
  // (as opposed to being created from static html). In this case, the new child
  // cannot be reliably identified in session history entries. To avoid
  // accidentally using incorrect session history entries such a child gets a
  // fresh, random, unique name every time it is created or recreated. See also
  // https://crbug.com/500260.
  std::string GenerateNameForNewChildFrame(const std::string& name,
                                           bool is_created_by_script) const;

  // Called after a browsing context name change to generate a new name. Note
  // that this should not be called if the frame is no longer displaying the
  // initial empty document, as unique name changes after that point will break
  // history navigations. See https://crbug.com/607205.
  void UpdateName(const std::string& name);

  // Prevents future changes of the unique name. This avoids changing the
  // unique name when the frame's assigned name changes in the future.
  //
  // Such freeze is desirable in case of frames created from javascript
  // (see |is_created_by_script| parameter of GenerateNameForNewChildFrame)
  // because their order of creation can be undeterministic and therefore
  // their unique name should NOT be derived from their assigned name
  // (because in case of a conflicting assigned name, their final unique
  // names would be undetetministic potentially leading to
  // https://crbug.com/500260).
  //
  // TODO(dcheng, lukasza): Consider making frame's unique name immutable (and
  // if this is possible remove the explicit Freeze method). For more context
  // see https://crbug.com/607205#c6.
  void Freeze() { frozen_ = true; }

  // Helper to update legacy names generated for PageState v24 and earlier. This
  // function should be invoked starting from the root of the tree, traversing
  // downwards. The exact traversal order is unimportant as long as this
  // function has been called on all ancestor frames of the node associated with
  // |legacy_name|. A single instance of |replacements| should be used per frame
  // tree.
  static std::string UpdateLegacyNameFromV24(
      std::string legacy_name,
      std::vector<Replacement>* replacements);

  static std::string CalculateLegacyNameForTesting(const FrameAdapter* frame,
                                                   const std::string& name);

  // Enters a mode causing future uses of GenerateNameForNewChildFrame to
  // preserve the original, stable unique name, so that it can be recovered
  // (e.g. for web tests) by ExtractStableNameForTesting method below. This
  // mode is not enabled by default, because it makes unique names longer, and
  // thus negatively affects memory usage.
  static void PreserveStableUniqueNameForTesting();

  // Removes the random components of |unique_name|, so it can be used in test
  // output that needs to be stable across test runs.
  //
  // Note: This method only works if |unique_name| was calculated after calling
  // PreserveStableUniqueNameForTesting (see above).
  static std::string ExtractStableNameForTesting(base::StringPiece unique_name);

 private:
  FrameAdapter* const frame_;
  std::string unique_name_;
  bool frozen_ = false;

  DISALLOW_COPY_AND_ASSIGN(UniqueNameHelper);
};

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_PUBLIC_COMMON_UNIQUE_NAME_UNIQUE_NAME_HELPER_H_