src/support/inplace_vector.h

/*
 * Copyright 2026 WebAssembly Community Group participants
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// A vector of elements with a maximum size, storing them all in-place. This is
// similar to c++26's inplace_vector, and is basically a small_vector, except
// there is never any dynamic storage.
// TODO: remove when we have c++26
//

#ifndef wasm_support_inplace_vector_h
#define wasm_support_inplace_vector_h

#include <algorithm>
#include <array>
#include <cassert>
#include <iterator>
#include <type_traits>
#include <vector>

#include "support/parent_index_iterator.h"

namespace wasm {

template<typename T, size_t N> class inplace_vector {
  // fixed-space storage
  size_t usedFixed = 0;
  std::array<T, N> fixed{};

public:
  using value_type = T;

  inplace_vector() {}
  inplace_vector(const inplace_vector<T, N>& other)
    : usedFixed(other.usedFixed), fixed(other.fixed) {}
  inplace_vector(inplace_vector<T, N>&& other)
    : usedFixed(other.usedFixed), fixed(std::move(other.fixed)) {}
  inplace_vector(std::initializer_list<T> init) {
    for (const T& item : init) {
      push_back(item);
    }
  }
  inplace_vector(size_t initialSize) { resize(initialSize); }

  inplace_vector<T, N>& operator=(const inplace_vector<T, N>& other) {
    usedFixed = other.usedFixed;
    fixed = other.fixed;
    return *this;
  }

  inplace_vector<T, N>& operator=(inplace_vector<T, N>&& other) {
    usedFixed = other.usedFixed;
    fixed = std::move(other.fixed);
    return *this;
  }

  T& operator[](size_t i) { return fixed[i]; }

  const T& operator[](size_t i) const {
    return const_cast<inplace_vector<T, N>&>(*this)[i];
  }

  void push_back(const T& x) {
    assert(usedFixed < N);
    fixed[usedFixed++] = x;
  }

  template<typename... ArgTypes> void emplace_back(ArgTypes&&... Args) {
    assert(usedFixed < N);
    new (&fixed[usedFixed++]) T(std::forward<ArgTypes>(Args)...);
  }

  void pop_back() {
    assert(usedFixed > 0);
    usedFixed--;
  }

  T& back() {
    assert(usedFixed > 0);
    return fixed[usedFixed - 1];
  }

  const T& back() const {
    assert(usedFixed > 0);
    return fixed[usedFixed - 1];
  }

  size_t size() const { return usedFixed; }

  bool empty() const { return size() == 0; }

  void clear() { usedFixed = 0; }

  void resize(size_t newSize) {
    assert(newSize <= N);
    usedFixed = newSize;
  }

  size_t capacity() const { return N; }

  bool operator==(const inplace_vector<T, N>& other) const {
    if (usedFixed != other.usedFixed) {
      return false;
    }
    for (size_t i = 0; i < usedFixed; i++) {
      if (fixed[i] != other.fixed[i]) {
        return false;
      }
    }
    return true;
  }

  bool operator!=(const inplace_vector<T, N>& other) const {
    return !(*this == other);
  }

  // iteration

  struct Iterator : wasm::ParentIndexIterator<inplace_vector<T, N>*, Iterator> {
    using value_type = T;
    using pointer = T*;
    using reference = T&;

    Iterator(inplace_vector<T, N>* parent, size_t index)
      : wasm::ParentIndexIterator<inplace_vector<T, N>*, Iterator>{parent,
                                                                   index} {}

    T& operator*() const { return (*this->parent)[this->index]; }
    T* operator->() const { return &(*this->parent)[this->index]; }
  };

  struct ConstIterator
    : wasm::ParentIndexIterator<const inplace_vector<T, N>*, ConstIterator> {
    using value_type = const T;
    using pointer = const T*;
    using reference = const T&;

    ConstIterator(const inplace_vector<T, N>* parent, size_t index)
      : wasm::ParentIndexIterator<const inplace_vector<T, N>*, ConstIterator>{
          parent, index} {}
    ConstIterator(const Iterator& other)
      : wasm::ParentIndexIterator<const inplace_vector<T, N>*, ConstIterator>{
          other.parent, other.index} {}
    ConstIterator(const ConstIterator& other) = default;

    const T& operator*() const { return (*this->parent)[this->index]; }
    const T* operator->() const { return &(*this->parent)[this->index]; }
  };

  Iterator begin() { return Iterator(this, 0); }
  Iterator end() { return Iterator(this, size()); }
  ConstIterator begin() const { return ConstIterator(this, 0); }
  ConstIterator end() const { return ConstIterator(this, size()); }

  Iterator insert(ConstIterator pos, const T& x) {
    assert(usedFixed < N);
    assert(pos.index <= usedFixed);
    size_t index = pos.index;
    std::move_backward(fixed.begin() + index,
                       fixed.begin() + usedFixed,
                       fixed.begin() + usedFixed + 1);
    fixed[index] = x;
    usedFixed++;
    return Iterator(this, index);
  }

  Iterator erase(ConstIterator first, ConstIterator last) {
    assert(first.index <= last.index);
    assert(last.index <= usedFixed);
    size_t numToErase = last.index - first.index;
    if (numToErase > 0) {
      std::move(fixed.begin() + last.index,
                fixed.begin() + usedFixed,
                fixed.begin() + first.index);
      usedFixed -= numToErase;
    }
    return Iterator(this, first.index);
  }

  Iterator erase(Iterator first, Iterator last) {
    return erase(ConstIterator(this, first.index),
                 ConstIterator(this, last.index));
  }

  Iterator erase(ConstIterator pos) { return erase(pos, pos + 1); }

  Iterator erase(Iterator pos) { return erase(pos, pos + 1); }
};

namespace detail {

template<typename T> struct is_inplace_vector_or_derived {
private:
  template<typename U, size_t N>
  static std::true_type test(const inplace_vector<U, N>*);
  static std::false_type test(...);

public:
  static constexpr bool value = decltype(test(std::declval<T*>()))::value;
};

} // namespace detail

template<typename Vector, typename Pred>
  requires detail::is_inplace_vector_or_derived<Vector>::value
size_t erase_if(Vector& c, Pred pred) {
  auto it = std::remove_if(c.begin(), c.end(), pred);
  auto r = std::distance(it, c.end());
  c.erase(it, c.end());
  return r;
}

} // namespace wasm

namespace std {

template<typename Vector, typename Pred>
  requires wasm::detail::is_inplace_vector_or_derived<Vector>::value
size_t erase_if(Vector& c, Pred pred) {
  return wasm::erase_if(c, pred);
}

} // namespace std

#endif // wasm_support_inplace_vector_h