functional-list.h

Go to the documentation of this file.

// Copyright 2018 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_COMPILER_FUNCTIONAL_LIST_H_
#define V8_COMPILER_FUNCTIONAL_LIST_H_
 
#include "src/base/iterator.h"
#include "src/zone/zone.h"
 
namespace v8 {
namespace internal {
namespace compiler {
 
// A generic stack implemented with a singly-linked list, which results in an
// O(1) copy operation. It can be used to model immutable lists like those in
// functional languages. Compared to typical functional lists, this also caches
// the length of the list in each node.
// Note: The underlying implementation is mutable, so if you want to use this as
// an immutable list, make sure to create a copy by passing it by value and
// operate on the copy.
// TODO(turbofan): Use this implementation also for RedundancyElimination.
template <class A>
class FunctionalList {
 private:
  struct Cons : ZoneObject {
    Cons(A top, Cons* rest)
        : top(std::move(top)), rest(rest), size(1 + (rest ? rest->size : 0)) {}
    A const top;
    Cons* const rest;
    size_t const size;
  };
 
 public:
  FunctionalList() : elements_(nullptr) {}
 
  bool operator==(const FunctionalList<A>& other) const {
    if (Size() != other.Size()) return false;
    iterator it = begin();
    iterator other_it = other.begin();
    while (true) {
      if (it == other_it) return true;
      if (*it != *other_it) return false;
      ++it;
      ++other_it;
    }
  }
  bool operator!=(const FunctionalList<A>& other) const {
    return !(*this == other);
  }
 
  bool TriviallyEquals(const FunctionalList<A>& other) const {
    return elements_ == other.elements_;
  }
 
  const A& Front() const {
    DCHECK_GT(Size(), 0);
    return elements_->top;
  }
 
  FunctionalList Rest() const {
    FunctionalList result = *this;
    result.DropFront();
    return result;
  }
 
  void DropFront() {
    CHECK_GT(Size(), 0);
    elements_ = elements_->rest;
  }
 
  void PushFront(A a, Zone* zone) {
    elements_ = zone->New<Cons>(std::move(a), elements_);
  }
 
  // If {hint} happens to be exactly what we want to allocate, avoid allocation
  // by reusing {hint}.
  void PushFront(A a, Zone* zone, FunctionalList hint) {
    if (hint.Size() == Size() + 1 && hint.Front() == a &&
        hint.Rest() == *this) {
      *this = hint;
    } else {
      PushFront(a, zone);
    }
  }
 
  // Drop elements until the current stack is equal to the tail shared with
  // {other}. The shared tail must not only be equal, but also refer to the
  // same memory.
  void ResetToCommonAncestor(FunctionalList other) {
    while (other.Size() > Size()) other.DropFront();
    while (other.Size() < Size()) DropFront();
    while (elements_ != other.elements_) {
      DropFront();
      other.DropFront();
    }
  }
 
  size_t Size() const { return elements_ ? elements_->size : 0; }
 
  void Clear() { elements_ = nullptr; }
 
  class iterator : public base::iterator<std::forward_iterator_tag, A> {
   public:
    explicit iterator(Cons* cur) : current_(cur) {}
 
    const A& operator*() const { return current_->top; }
    iterator& operator++() {
      current_ = current_->rest;
      return *this;
    }
    bool operator==(const iterator& other) const {
      return this->current_ == other.current_;
    }
    bool operator!=(const iterator& other) const { return !(*this == other); }
 
   private:
    Cons* current_;
  };
 
  iterator begin() const { return iterator(elements_); }
  iterator end() const { return iterator(nullptr); }
 
 private:
  Cons* elements_;
};
 
}  // namespace compiler
}  // namespace internal
}  // namespace v8
 
#endif  // V8_COMPILER_FUNCTIONAL_LIST_H_