// Copyright 2014 the V8 project 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 V8_BASE_VECTOR_H_
#define V8_BASE_VECTOR_H_
#include <algorithm>
#include <cstring>
#include <iterator>
#include <limits>
#include <memory>
#include <ranges>
#include <type_traits>
#include "include/v8config.h"
#include "src/base/algorithm.h"
#include "src/base/hashing.h"
#include "src/base/logging.h"
#include "src/base/macros.h"
namespace v8::base {
template <typename T>
class Vector;
} // namespace v8::base
// Mark `Vector` as satisfying the `view` and `borrowed_range` concepts.
// This should be done before the definition of `Vector`, so that any
// inlined calls to range functionality use the correct specializations.
template <typename T>
inline constexpr bool std::ranges::enable_view<v8::base::Vector<T>> = true;
template <typename T>
inline constexpr bool std::ranges::enable_borrowed_range<v8::base::Vector<T>> =
true;
namespace v8::base {
template <typename T>
class Vector final {
public:
using value_type = T;
using iterator = T*;
using const_iterator = const T*;
constexpr Vector() : start_(nullptr), length_(0) {}
constexpr Vector(T* data V8_LIFETIME_BOUND, size_t length)
: start_(data), length_(length) {
DCHECK(length == 0 || data != nullptr);
}
static Vector<T> New(size_t length) {
return Vector<T>(new T[length], length);
}
// Returns a vector using the same backing storage as this one,
// spanning from and including 'from', to but not including 'to'.
Vector<T> SubVector(size_t from, size_t to) const {
DCHECK_LE(from, to);
DCHECK_LE(to, length_);
return Vector<T>(begin() + from, to - from);
}
Vector<T> SubVectorFrom(size_t from) const {
return SubVector(from, length_);
}
template <class U>
void OverwriteWith(Vector<U> other) {
DCHECK_EQ(size(), other.size());
base::Copy(other.begin(), other.end(), begin());
}
template <class U, size_t n>
void OverwriteWith(const std::array<U, n>& other) {
DCHECK_EQ(size(), other.size());
base::Copy(other.begin(), other.end(), begin());
}
// Returns the length of the vector. Only use this if you really need an
// integer return value. Use {size()} otherwise.
int length() const {
CHECK_GE(std::numeric_limits<int>::max(), length_);
return static_cast<int>(length_);
}
// Returns the length of the vector as a size_t.
constexpr size_t size() const { return length_; }
// Returns whether or not the vector is empty.
constexpr bool empty() const { return length_ == 0; }
// Access individual vector elements - checks bounds in debug mode.
T& operator[](size_t index) const {
DCHECK_LT(index, length_);
return start_[index];
}
const T& at(size_t index) const { return operator[](index); }
T& first() { return start_[0]; }
const T& first() const { return start_[0]; }
T& last() {
DCHECK_LT(0, length_);
return start_[length_ - 1];
}
const T& last() const {
DCHECK_LT(0, length_);
return start_[length_ - 1];
}
// Returns a pointer to the start of the data in the vector.
constexpr T* begin() const { return start_; }
constexpr const T* cbegin() const { return start_; }
// For consistency with other containers, do also provide a {data} accessor.
constexpr T* data() const { return start_; }
// Returns a pointer past the end of the data in the vector.
constexpr T* end() const { return start_ + length_; }
constexpr const T* cend() const { return start_ + length_; }
constexpr std::reverse_iterator<T*> rbegin() const {
return std::make_reverse_iterator(end());
}
constexpr std::reverse_iterator<T*> rend() const {
return std::make_reverse_iterator(begin());
}
void Truncate(size_t length) {
DCHECK_LE(length, length_);
length_ = length;
}
// Releases the array underlying this vector. Once disposed the
// vector is empty.
void Dispose() {
delete[] start_;
start_ = nullptr;
length_ = 0;
}
const Vector<T> operator+(size_t offset) const {
return SubVectorFrom(offset);
}
Vector<T> operator+=(size_t offset) {
DCHECK_LE(offset, length_);
start_ += offset;
length_ -= offset;
return *this;
}
// Implicit conversion from Vector<T> to Vector<const U> if
// - T* is convertible to const U*, and
// - U and T have the same size.
// Note that this conversion is only safe for `*const* U`; writes would
// violate covariance.
template <typename U>
requires std::is_convertible_v<T*, const U*> && (sizeof(U) == sizeof(T))
operator Vector<const U>() const {
return {start_, length_};
}
template <typename S>
static Vector<T> cast(Vector<S> input) {
// Casting is potentially dangerous, so be really restrictive here. This
// might be lifted once we have use cases for that.
static_assert(std::is_trivial_v<S> && std::is_standard_layout_v<S>);
static_assert(std::is_trivial_v<T> && std::is_standard_layout_v<T>);
DCHECK_EQ(0, (input.size() * sizeof(S)) % sizeof(T));
DCHECK_EQ(0, reinterpret_cast<uintptr_t>(input.begin()) % alignof(T));
return Vector<T>(reinterpret_cast<T*>(input.begin()),
input.size() * sizeof(S) / sizeof(T));
}
bool operator==(const Vector<T>& other) const {
return std::equal(begin(), end(), other.begin(), other.end());
}
template <typename TT = T>
requires(!std::is_const_v<TT>)
bool operator==(const Vector<const T>& other) const {
return std::equal(begin(), end(), other.begin(), other.end());
}
private:
T* start_;
size_t length_;
};
template <typename T>
V8_INLINE size_t hash_value(base::Vector<T> v) {
return hash_range(v.begin(), v.end());
}
template <typename T>
class OwnedVector final {
public:
OwnedVector() = default;
OwnedVector(std::unique_ptr<T[]> data, size_t length)
: data_(std::move(data)), length_(length) {
DCHECK_IMPLIES(length_ > 0, data_ != nullptr);
}
// Disallow copying.
OwnedVector(const OwnedVector&) = delete;
OwnedVector& operator=(const OwnedVector&) = delete;
// Move construction and move assignment from {OwnedVector<U>} to
// {OwnedVector<T>}, instantiable if {std::unique_ptr<U>} can be converted to
// {std::unique_ptr<T>}. Can also be used to convert {OwnedVector<T>} to
// {OwnedVector<const T>}.
// These also function as the standard move construction/assignment operator.
// {other} is left as an empty vector.
template <typename U>
requires std::is_convertible_v<std::unique_ptr<U>, std::unique_ptr<T>>
OwnedVector(OwnedVector<U>&& other) V8_NOEXCEPT {
*this = std::move(other);
}
template <typename U>
requires std::is_convertible_v<std::unique_ptr<U>, std::unique_ptr<T>>
OwnedVector& operator=(OwnedVector<U>&& other) V8_NOEXCEPT {
static_assert(sizeof(U) == sizeof(T));
data_ = std::move(other.data_);
length_ = other.length_;
DCHECK_NULL(other.data_);
other.length_ = 0;
return *this;
}
// Returns the length of the vector as a size_t.
constexpr size_t size() const { return length_; }
// Returns whether or not the vector is empty.
constexpr bool empty() const { return length_ == 0; }
constexpr T* begin() const V8_LIFETIME_BOUND {
DCHECK_IMPLIES(length_ > 0, data_ != nullptr);
return data_.get();
}
constexpr T* end() const V8_LIFETIME_BOUND { return begin() + length_; }
// In addition to {begin}, do provide a {data()} accessor for API
// compatibility with other sequential containers.
constexpr T* data() const V8_LIFETIME_BOUND { return begin(); }
constexpr std::reverse_iterator<T*> rbegin() const V8_LIFETIME_BOUND {
return std::make_reverse_iterator(end());
}
constexpr std::reverse_iterator<T*> rend() const V8_LIFETIME_BOUND {
return std::make_reverse_iterator(begin());
}
// Access individual vector elements - checks bounds in debug mode.
T& operator[](size_t index) const V8_LIFETIME_BOUND {
DCHECK_LT(index, length_);
return data_[index];
}
// Returns a {Vector<T>} view of the data in this vector.
Vector<T> as_vector() const V8_LIFETIME_BOUND { return {begin(), size()}; }
// Releases the backing data from this vector and transfers ownership to the
// caller. This vector will be empty afterwards.
std::unique_ptr<T[]> ReleaseData() {
length_ = 0;
return std::move(data_);
}
// Allocates a new vector of the specified size via the default allocator.
// Elements in the new vector are value-initialized.
static OwnedVector<T> New(size_t size) {
if (size == 0) return {};
return OwnedVector<T>(std::make_unique<T[]>(size), size);
}
// Allocates a new vector of the specified size via the default allocator and
// initializes all elements by assigning from `init`.
template <typename U>
static OwnedVector<T> New(size_t size, U init) {
if (size == 0) return {};
OwnedVector<T> vec = NewForOverwrite(size);
std::fill_n(vec.begin(), size, init);
return vec;
}
// Allocates a new vector of the specified size via the default allocator.
// Elements in the new vector are default-initialized.
static OwnedVector<T> NewForOverwrite(size_t size) {
if (size == 0) return {};
return OwnedVector<T>(std::make_unique_for_overwrite<T[]>(size), size);
}
// Allocates a new vector containing the specified collection of values.
template <typename U>
static OwnedVector<U> NewByCopying(const U* data, size_t size) {
auto result = OwnedVector<U>::NewForOverwrite(size);
base::Copy(data, data + size, result.begin());
return result;
}
bool operator==(std::nullptr_t) const { return data_ == nullptr; }
private:
template <typename U>
friend class OwnedVector;
std::unique_ptr<T[]> data_;
size_t length_ = 0;
};
// The vectors returned by {StaticCharVector}, {CStrVector}, or {OneByteVector}
// do not contain a null-termination byte. If you want the null byte, use
// {ArrayVector}.
// Known length, constexpr.
template <size_t N>
constexpr Vector<const char> StaticCharVector(
const char (&array V8_LIFETIME_BOUND)[N]) {
return {array, N - 1};
}
// Unknown length, not constexpr.
inline Vector<const char> CStrVector(const char* data V8_LIFETIME_BOUND) {
return {data, strlen(data)};
}
inline Vector<const char> StrVector(std::string_view str V8_LIFETIME_BOUND) {
return {str.data(), str.size()};
}
// OneByteVector is never constexpr because the data pointer is
// {reinterpret_cast}ed.
inline Vector<const uint8_t> OneByteVector(const char* data V8_LIFETIME_BOUND,
size_t length) {
return {reinterpret_cast<const uint8_t*>(data), length};
}
inline Vector<const uint8_t> OneByteVector(const char* data V8_LIFETIME_BOUND) {
return OneByteVector(data, strlen(data));
}
template <size_t N>
Vector<const uint8_t> StaticOneByteVector(
const char (&array V8_LIFETIME_BOUND)[N]) {
return OneByteVector(array, N - 1);
}
// For string literals, ArrayVector("foo") returns a vector ['f', 'o', 'o', \0]
// with length 4 and null-termination.
// If you want ['f', 'o', 'o'], use CStrVector("foo").
template <typename T, size_t N>
inline constexpr Vector<T> ArrayVector(T (&arr V8_LIFETIME_BOUND)[N]) {
return {arr, N};
}
// Construct a Vector from a start pointer and a size.
template <typename T>
inline constexpr Vector<T> VectorOf(T* start V8_LIFETIME_BOUND, size_t size) {
return {start, size};
}
// Construct a Vector from anything compatible with std::data and std::size (ie,
// an array, or a container providing a {data()} and {size()} accessor).
template <typename Container>
inline constexpr auto VectorOf(Container&& c V8_LIFETIME_BOUND)
-> decltype(VectorOf(std::data(c), std::size(c))) {
return VectorOf(std::data(c), std::size(c));
}
// Construct a Vector from an initializer list. The vector can obviously only be
// used as long as the initializer list is live. Valid uses include direct use
// in parameter lists: F(VectorOf({1, 2, 3}));
template <typename T>
inline constexpr Vector<const T> VectorOf(
std::initializer_list<T> list V8_LIFETIME_BOUND) {
return VectorOf(list.begin(), list.size());
}
// Construct an OwnedVector from a start pointer and a size.
// The data will be copied.
template <typename T>
inline OwnedVector<T> OwnedCopyOf(const T* data, size_t size) {
return OwnedVector<T>::NewByCopying(data, size);
}
// Construct an OwnedVector from anything compatible with std::data and
// std::size (e.g. an array, or a container providing a {data()} and {size()}
// accessor). The data will be copied.
template <typename Container>
inline auto OwnedCopyOf(const Container& c)
-> decltype(OwnedCopyOf(std::data(c), std::size(c))) {
return OwnedCopyOf(std::data(c), std::size(c));
}
// Container with a fixed storage for `kSize` elements.
template <typename T, size_t kSize>
class EmbeddedVector final {
public:
constexpr EmbeddedVector() = default;
constexpr explicit EmbeddedVector(const T& initial_value) {
std::fill_n(buffer_, kSize, initial_value);
}
EmbeddedVector(const EmbeddedVector&) = delete;
EmbeddedVector& operator=(const EmbeddedVector&) = delete;
constexpr Vector<T> SubVector(size_t from, size_t to) V8_LIFETIME_BOUND {
DCHECK_LE(from, to);
DCHECK_LE(to, length_);
return Vector<T>(buffer_ + from, to - from);
}
constexpr Vector<T> SubVectorFrom(size_t from) V8_LIFETIME_BOUND {
return SubVector(from, length_);
}
constexpr size_t size() const { return length_; }
constexpr T& operator[](size_t index) V8_LIFETIME_BOUND {
DCHECK_LT(index, length_);
return buffer_[index];
}
constexpr const T& operator[](size_t index) const V8_LIFETIME_BOUND {
DCHECK_LT(index, length_);
return buffer_[index];
}
constexpr T* begin() V8_LIFETIME_BOUND { return buffer_; }
constexpr const T* begin() const V8_LIFETIME_BOUND { return buffer_; }
constexpr T* data() V8_LIFETIME_BOUND { return buffer_; }
constexpr T* end() V8_LIFETIME_BOUND { return buffer_ + length_; }
constexpr const T* end() const V8_LIFETIME_BOUND { return buffer_ + length_; }
constexpr void Truncate(size_t length) {
DCHECK_LE(length, length_);
length_ = length;
}
constexpr const Vector<T> operator+(size_t offset) V8_LIFETIME_BOUND {
return SubVectorFrom(offset);
}
constexpr operator Vector<T>() V8_LIFETIME_BOUND {
return Vector<T>(buffer_, length_);
}
template <typename U>
requires std::is_convertible_v<T*, const U*> && (sizeof(U) == sizeof(T))
constexpr operator Vector<const U>() const V8_LIFETIME_BOUND {
return Vector<const U>(buffer_, length_);
}
private:
T buffer_[kSize];
size_t length_ = kSize;
};
} // namespace v8::base
#endif // V8_BASE_VECTOR_H_