ndn-cxx/name.hpp

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2013-2024 Regents of the University of California.
 *
 * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
 *
 * ndn-cxx library is free software: you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later version.
 *
 * ndn-cxx 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 Lesser General Public License for more details.
 *
 * You should have received copies of the GNU General Public License and GNU Lesser
 * General Public License along with ndn-cxx, e.g., in COPYING.md file.  If not, see
 * <http://www.gnu.org/licenses/>.
 *
 * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
 */

#ifndef NDN_CXX_NAME_HPP
#define NDN_CXX_NAME_HPP

#include "ndn-cxx/name-component.hpp"

#include <iterator>
#include <limits>
#include <optional>

namespace ndn {

class Name;

/**
 * @brief Represents an arbitrary sequence of name components.
 */
using PartialName = Name;

/**
 * @brief Represents an absolute name.
 * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html
 */
class Name : private boost::totally_ordered<Name>
{
public: // nested types
  using Component = name::Component;
  using Error = Component::Error;

  // Name appears as an ordered sequence of name components
  using value_type             = Component;
  using allocator_type         = void;
  using reference              = Component&;
  using const_reference        = const Component&;
  using pointer                = Component*;
  using const_pointer          = const Component*;
  using iterator               = const Component*; // disallow modifying via iterator
  using const_iterator         = const Component*;
  using reverse_iterator       = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  using difference_type        = std::vector<Component>::difference_type;
  using size_type              = std::vector<Component>::size_type;

public: // constructors, encoding, decoding
  /**
   * @brief Create an empty name.
   * @post empty() == true
   */
  Name();

  /**
   * @brief Create Name from wire encoding.
   * @param wire TLV element of type tlv::Name
   *
   * This is equivalent to:
   * @code
   * Name name;
   * name.wireDecode(wire);
   * @endcode
   *
   * @throw tlv::Error The wire encoding is invalid.
   */
  explicit
  Name(const Block& wire);

  /**
   * @brief Create name from NDN URI.
   * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#ndn-uri-scheme
   */
  explicit
  Name(std::string_view uri);

  /**
   * @brief Create name from NDN URI.
   * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#ndn-uri-scheme
   * @note This constructor enables implicit conversion from a string literal.
   */
  Name(const char* uri)
    : Name(std::string_view(uri))
  {
  }

  /**
   * @brief Create name from NDN URI.
   * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#ndn-uri-scheme
   * @note This constructor enables implicit conversion from `std::string`.
   */
  Name(const std::string& uri)
    : Name(std::string_view(uri))
  {
  }

  /**
   * @brief Write URI representation of the name to the output stream.
   * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#ndn-uri-scheme
   */
  void
  toUri(std::ostream& os, name::UriFormat format = name::UriFormat::DEFAULT) const;

  /**
   * @brief Get URI representation of the name.
   * @return URI representation; the "ndn:" scheme identifier is not included.
   * @note To print the URI representation to a stream, it is more efficient to use `os << name`.
   * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#ndn-uri-scheme
   */
  std::string
  toUri(name::UriFormat format = name::UriFormat::DEFAULT) const;

  /**
   * @brief Check if this instance already has wire encoding.
   */
  bool
  hasWire() const noexcept
  {
    return m_wire.hasWire();
  }

  /**
   * @brief Prepend wire encoding to @p encoder.
   */
  template<encoding::Tag TAG>
  size_t
  wireEncode(EncodingImpl<TAG>& encoder) const;

  /**
   * @brief Perform wire encoding, or return existing (cached) wire encoding.
   * @post hasWire() == true
   */
  const Block&
  wireEncode() const;

  /**
   * @brief Decode name from wire encoding.
   * @throw tlv::Error The wire encoding is invalid.
   * @post hasWire() == true
   */
  void
  wireDecode(const Block& wire);

  /**
   * @brief Make a deep copy of the name, reallocating the underlying memory buffer.
   */
  Name
  deepCopy() const;

public: // access
  /**
   * @brief Checks if the name is empty, i.e., has no components.
   */
  [[nodiscard]] bool
  empty() const noexcept
  {
    return m_wire.elements().empty();
  }

  /**
   * @brief Returns the number of components.
   */
  size_t
  size() const noexcept
  {
    return m_wire.elements_size();
  }

  /**
   * @brief Returns an immutable reference to the component at the specified index.
   * @param i zero-based index of the component to return;
   *          if negative, it is interpreted as offset from the end of the name
   * @warning No bounds checking is performed, using an out-of-range index is undefined behavior.
   */
  const Component&
  get(ssize_t i) const noexcept
  {
    if (i < 0) {
      i += static_cast<ssize_t>(size());
    }
    return static_cast<const Component&>(m_wire.elements()[static_cast<size_t>(i)]);
  }

  /**
   * @brief Equivalent to get().
   */
  const Component&
  operator[](ssize_t i) const noexcept
  {
    return get(i);
  }

  /**
   * @brief Returns an immutable reference to the component at the specified index,
   *        with bounds checking.
   * @param i zero-based index of the component to return;
   *          if negative, it is interpreted as offset from the end of the name
   * @throws Error The index is out of bounds.
   */
  const Component&
  at(ssize_t i) const;

  /** @brief Extracts some components as a sub-name (PartialName).
   *  @param iStartComponent zero-based index of the first component;
   *                         if negative, size()+iStartComponent is used instead
   *  @param nComponents number of desired components, starting at @p iStartComponent;
   *                     use #npos to return all components until the end of the name
   *  @return a new PartialName containing the extracted components
   *
   *  If @p iStartComponent is positive and indexes out of bounds, returns an empty PartialName.
   *  If @p iStartComponent is negative and indexes out of bounds, the sub-name will start from
   *  the beginning of the name instead. If @p nComponents is out of bounds, returns all components
   *  until the end of the name.
   */
  PartialName
  getSubName(ssize_t iStartComponent, size_t nComponents = npos) const;

  /** @brief Returns a prefix of the name.
   *  @param nComponents number of components; if negative, size()+nComponents is used instead
   *
   *  Returns a new PartialName containing a prefix of this name up to `size() - nComponents`.
   *  For example, `getPrefix(-1)` returns the name without the final component.
   */
  PartialName
  getPrefix(ssize_t nComponents) const
  {
    if (nComponents < 0)
      return getSubName(0, size() + nComponents);
    else
      return getSubName(0, nComponents);
  }

public: // iterators
  /** @brief Begin iterator.
   */
  const_iterator
  begin() const noexcept
  {
    return reinterpret_cast<const_iterator>(m_wire.elements().data());
  }

  /** @brief End iterator.
   */
  const_iterator
  end() const noexcept
  {
    return reinterpret_cast<const_iterator>(m_wire.elements().data() + m_wire.elements().size());
  }

  /** @brief Reverse begin iterator.
   */
  const_reverse_iterator
  rbegin() const noexcept
  {
    return const_reverse_iterator(end());
  }

  /** @brief Reverse end iterator.
   */
  const_reverse_iterator
  rend() const noexcept
  {
    return const_reverse_iterator(begin());
  }

public: // modifiers
  /** @brief Replace the component at the specified index.
   *  @param i zero-based index of the component to replace;
   *           if negative, it is interpreted as offset from the end of the name
   *  @param component the new component to use as a replacement
   *  @return A reference to this Name, to allow chaining.
   *  @warning No bounds checking is performed, using an out-of-range index is undefined behavior.
   */
  Name&
  set(ssize_t i, const Component& component);

  /** @brief Replace the component at the specified index.
   *  @param i zero-based index of the component to replace;
   *           if negative, it is interpreted as offset from the end of the name
   *  @param component the new component to use as a replacement
   *  @return A reference to this Name, to allow chaining.
   *  @warning No bounds checking is performed, using an out-of-range index is undefined behavior.
   */
  Name&
  set(ssize_t i, Component&& component);

  /**
   * @brief Append a name component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  append(const Component& component)
  {
    m_wire.push_back(component);
    return *this;
  }

  /**
   * @brief Append a name component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  append(Component&& component)
  {
    m_wire.push_back(std::move(component));
    return *this;
  }

  /**
   * @brief Append a `NameComponent` of TLV-TYPE @p type, copying the TLV-VALUE from @p value.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  append(uint32_t type, span<const uint8_t> value)
  {
    return append(Component(type, value));
  }

  /**
   * @brief Append a `GenericNameComponent`, copying the TLV-VALUE from @p value.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  append(span<const uint8_t> value)
  {
    return append(Component(tlv::GenericNameComponent, value));
  }

  /**
   * @brief Append a `NameComponent` of TLV-TYPE @p type, copying the TLV-VALUE from a range.
   * @tparam Iterator an @c InputIterator dereferencing to a one-octet value type. More efficient
   *                  implementation is available when it is a @c RandomAccessIterator.
   * @param type      the TLV-TYPE.
   * @param first     beginning of the range.
   * @param last      past-end of the range.
   * @return A reference to this Name, to allow chaining.
   */
  template<class Iterator>
  Name&
  append(uint32_t type, Iterator first, Iterator last)
  {
    return append(Component(type, first, last));
  }

  /**
   * @brief Append a `GenericNameComponent`, copying the TLV-VALUE from a range.
   * @tparam Iterator an @c InputIterator dereferencing to a one-octet value type. More efficient
   *                  implementation is available when it is a @c RandomAccessIterator.
   * @param first     beginning of the range.
   * @param last      past-end of the range.
   * @return A reference to this Name, to allow chaining.
   */
  template<class Iterator>
  Name&
  append(Iterator first, Iterator last)
  {
    return append(Component(tlv::GenericNameComponent, first, last));
  }

  /**
   * @brief Append a `GenericNameComponent`, copying the TLV-VALUE from a null-terminated string.
   * @param str a null-terminated string. Bytes from the string are copied as is, and not
   *            interpreted as a URI component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  append(const char* str)
  {
    return append(Component(str));
  }

  /**
   * @brief Append a PartialName.
   * @param name the components to append
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  append(const PartialName& name);

  /**
   * @brief Append a component with a NonNegativeInteger.
   * @return A reference to this Name, to allow chaining.
   * @sa https://docs.named-data.net/NDN-packet-spec/0.3/tlv.html#non-negative-integer-encoding
   */
  Name&
  appendNumber(uint64_t number)
  {
    return append(Component::fromNumber(number));
  }

  /**
   * @brief Append a component with a marked number.
   * @param marker 1-octet marker
   * @param number the number
   *
   * The component is encoded as a 1-octet marker, followed by a NonNegativeInteger.
   *
   * @return A reference to this Name, to allow chaining.
   * @sa NDN Naming Conventions revision 1 (obsolete)
   *     https://named-data.net/wp-content/uploads/2014/08/ndn-tr-22-ndn-memo-naming-conventions.pdf
   */
  Name&
  appendNumberWithMarker(uint8_t marker, uint64_t number)
  {
    return append(Component::fromNumberWithMarker(marker, number));
  }

  /**
   * @brief Append a segment number (sequential) component.
   * @return A reference to this Name, to allow chaining.
   * @sa NDN Naming Conventions
   *     https://named-data.net/publications/techreports/ndn-tr-22-3-ndn-memo-naming-conventions/
   */
  Name&
  appendSegment(uint64_t segmentNo)
  {
    return append(Component::fromSegment(segmentNo));
  }

  /**
   * @brief Append a byte offset component.
   * @return A reference to this Name, to allow chaining.
   * @sa NDN Naming Conventions
   *     https://named-data.net/publications/techreports/ndn-tr-22-3-ndn-memo-naming-conventions/
   */
  Name&
  appendByteOffset(uint64_t offset)
  {
    return append(Component::fromByteOffset(offset));
  }

  /**
   * @brief Append a version component.
   * @param version the version number to append; if nullopt, the current UNIX time
   *                in milliseconds is used
   * @return A reference to this Name, to allow chaining.
   * @sa NDN Naming Conventions
   *     https://named-data.net/publications/techreports/ndn-tr-22-3-ndn-memo-naming-conventions/
   */
  Name&
  appendVersion(const std::optional<uint64_t>& version = std::nullopt);

  /**
   * @brief Append a timestamp component.
   * @param timestamp the timestamp to append; if nullopt, the current system time is used
   * @return A reference to this Name, to allow chaining.
   * @sa NDN Naming Conventions
   *     https://named-data.net/publications/techreports/ndn-tr-22-3-ndn-memo-naming-conventions/
   */
  Name&
  appendTimestamp(const std::optional<time::system_clock::time_point>& timestamp = std::nullopt);

  /**
   * @brief Append a sequence number component.
   * @return A reference to this Name, to allow chaining.
   * @sa NDN Naming Conventions
   *     https://named-data.net/publications/techreports/ndn-tr-22-3-ndn-memo-naming-conventions/
   */
  Name&
  appendSequenceNumber(uint64_t seqNo)
  {
    return append(Component::fromSequenceNumber(seqNo));
  }

  /**
   * @brief Append an `ImplicitSha256Digest` component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  appendImplicitSha256Digest(ConstBufferPtr digest)
  {
    return append(Component(tlv::ImplicitSha256DigestComponent, std::move(digest)));
  }

  /**
   * @brief Append an `ImplicitSha256Digest` component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  appendImplicitSha256Digest(span<const uint8_t> digestBytes)
  {
    return append(Component(tlv::ImplicitSha256DigestComponent, digestBytes));
  }

  /**
   * @brief Append a `ParametersSha256Digest` component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  appendParametersSha256Digest(ConstBufferPtr digest)
  {
    return append(Component(tlv::ParametersSha256DigestComponent, std::move(digest)));
  }

  /**
   * @brief Append a `ParametersSha256Digest` component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  appendParametersSha256Digest(span<const uint8_t> digestBytes)
  {
    return append(Component(tlv::ParametersSha256DigestComponent, digestBytes));
  }

  /**
   * @brief Append a placeholder for a `ParametersSha256Digest` component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  appendParametersSha256DigestPlaceholder();

  /**
   * @brief Append a keyword component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  appendKeyword(span<const uint8_t> keyword)
  {
    return append(Component(tlv::KeywordNameComponent, keyword));
  }

  /**
   * @brief Append a keyword component.
   * @return A reference to this Name, to allow chaining.
   */
  Name&
  appendKeyword(std::string_view keyword)
  {
    return append(Component(tlv::KeywordNameComponent,
                            {reinterpret_cast<const uint8_t*>(keyword.data()), keyword.size()}));
  }

  /**
   * @brief Erase the component at the specified index.
   * @param i zero-based index of the component to erase;
   *          if negative, it is interpreted as offset from the end of the name
   * @warning No bounds checking is performed, using an out-of-range index is undefined behavior.
   */
  void
  erase(ssize_t i);

  /**
   * @brief Remove all components.
   * @post `empty() == true`
   */
  void
  clear();

public: // algorithms
  /** @brief Get the successor of a name.
   *
   *  The successor of a name is defined as follows:
   *
   *      N represents the set of NDN Names, and X,Y ∈ N.
   *      Operator < is defined by canonical order on N.
   *      Y is the successor of X, if (a) X < Y, and (b) ∄ Z ∈ N s.t. X < Z < Y.
   *
   *  In plain words, successor of a name is the same name, but with its last component
   *  advanced to a next possible value.
   *
   *  Examples:
   *
   *  - successor of `/` is
   *    `/sha256digest=0000000000000000000000000000000000000000000000000000000000000000`.
   *  - successor of `/sha256digest=0000000000000000000000000000000000000000000000000000000000000000`
   *    is `/sha256digest=0000000000000000000000000000000000000000000000000000000000000001`.
   *  - successor of `/sha256digest=ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff`
   *    is `/2=...`.
   *  - successor of `/P/A` is `/P/B`.
   *  - successor of `/Q/%FF` is `/Q/%00%00`.
   *
   *  @return a new Name containing the successor
   */
  Name
  getSuccessor() const;

  /** @brief Check if this name is a prefix of another name.
   *
   *  This name is a prefix of @p other if the N components of this name are same as the first N
   *  components of @p other.
   *
   *  @retval true this name is a prefix of @p other
   *  @retval false this name is not a prefix of @p other
   */
  bool
  isPrefixOf(const Name& other) const noexcept;

  /** @brief Check if this name equals another name.
   *
   *  Two names are equal if they have the same number of components, and components at each index
   *  are equal.
   */
  bool
  equals(const Name& other) const noexcept;

  /** @brief Compare this to the other Name using NDN canonical ordering.
   *
   *  If the first components of each name are not equal, this returns a negative value if
   *  the first comes before the second using the NDN canonical ordering for name
   *  components, or a positive value if it comes after.  If they are equal, this compares
   *  the second components of each name, etc. If both names are the same up to the size
   *  of the shorter name, this returns a negative value if the first name is shorter than
   *  the second or a positive value if it is longer.  For example, if you std::sort gives:
   *  /a/b/d /a/b/cc /c /c/a /bb .
   *  This is intuitive because all names with the prefix /a are next to each other.
   *  But it may be also be counter-intuitive because /c comes before /bb according
   *  to NDN canonical ordering since it is shorter.
   *
   *  @param other The other Name to compare with.
   *
   *  @retval negative this comes before other in canonical ordering
   *  @retval zero this equals other
   *  @retval positive this comes after other in canonical ordering
   *
   *  @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#canonical-order
   */
  int
  compare(const Name& other) const
  {
    return this->compare(0, npos, other);
  }

  /** @brief Compares `[pos1, pos1+count1)` components in this Name
   *         to `[pos2, pos2+count2)` components in @p other.
   *
   *  Equivalent to `getSubName(pos1, count1).compare(other.getSubName(pos2, count2))`.
   */
  int
  compare(size_t pos1, size_t count1,
          const Name& other, size_t pos2 = 0, size_t count2 = npos) const;

private: // non-member operators
  // NOTE: the following "hidden friend" operators are available via
  //       argument-dependent lookup only and must be defined inline.
  // boost::totally_ordered provides !=, <=, >=, and > operators.

  friend bool
  operator==(const Name& lhs, const Name& rhs) noexcept
  {
    return lhs.equals(rhs);
  }

  friend bool
  operator<(const Name& lhs, const Name& rhs)
  {
    return lhs.compare(rhs) < 0;
  }

  /**
   * @brief Print the URI representation of a name.
   * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#ndn-uri-scheme
   */
  friend std::ostream&
  operator<<(std::ostream& os, const Name& name)
  {
    name.toUri(os);
    return os;
  }

public:
  /**
   * @brief Indicates "until the end" in getSubName() and compare().
   */
  static constexpr size_t npos = std::numeric_limits<size_t>::max();

private:
  mutable Block m_wire{tlv::Name};
};

NDN_CXX_DECLARE_WIRE_ENCODE_INSTANTIATIONS(Name);

/**
 * @brief Parse URI from stream as Name.
 * @sa https://docs.named-data.net/NDN-packet-spec/0.3/name.html#ndn-uri-scheme
 */
std::istream&
operator>>(std::istream& is, Name& name);

} // namespace ndn

namespace std {

template<>
struct hash<ndn::Name>
{
  size_t
  operator()(const ndn::Name& name) const;
};

} // namespace std

#endif // NDN_CXX_NAME_HPP