1// Copyright 2018 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_COMPILER_FUNCTIONAL_LIST_H_
6#define V8_COMPILER_FUNCTIONAL_LIST_H_
7
8#include "src/base/iterator.h"
9#include "src/zone/zone.h"
10
11namespace v8 {
12namespace internal {
13namespace compiler {
14
15// A generic stack implemented with a singly-linked list, which results in an
16// O(1) copy operation. It can be used to model immutable lists like those in
17// functional languages. Compared to typical functional lists, this also caches
18// the length of the list in each node.
19// Note: The underlying implementation is mutable, so if you want to use this as
20// an immutable list, make sure to create a copy by passing it by value and
21// operate on the copy.
22// TODO(turbofan): Use this implementation also for RedundancyElimination.
23template <class A>
24class FunctionalList {
25 private:
26  struct Cons : ZoneObject {
27    Cons(A top, Cons* rest)
28        : top(std::move(top)), rest(rest), size(1 + (rest ? rest->size : 0)) {}
29    A const top;
30    Cons* const rest;
31    size_t const size;
32  };
33
34 public:
35  FunctionalList() : elements_(nullptr) {}
36
37  bool operator==(const FunctionalList<A>& other) const {
38    if (Size() != other.Size()) return false;
39    iterator it = begin();
40    iterator other_it = other.begin();
41    while (true) {
42      if (it == other_it) return true;
43      if (*it != *other_it) return false;
44      ++it;
45      ++other_it;
46    }
47  }
48  bool operator!=(const FunctionalList<A>& other) const {
49    return !(*this == other);
50  }
51
52  bool TriviallyEquals(const FunctionalList<A>& other) const {
53    return elements_ == other.elements_;
54  }
55
56  const A& Front() const {
57    DCHECK_GT(Size(), 0);
58    return elements_->top;
59  }
60
61  FunctionalList Rest() const {
62    FunctionalList result = *this;
63    result.DropFront();
64    return result;
65  }
66
67  void DropFront() {
68    CHECK_GT(Size(), 0);
69    elements_ = elements_->rest;
70  }
71
72  void PushFront(A a, Zone* zone) {
73    elements_ = zone->New<Cons>(std::move(a), elements_);
74  }
75
76  // If {hint} happens to be exactly what we want to allocate, avoid allocation
77  // by reusing {hint}.
78  void PushFront(A a, Zone* zone, FunctionalList hint) {
79    if (hint.Size() == Size() + 1 && hint.Front() == a &&
80        hint.Rest() == *this) {
81      *this = hint;
82    } else {
83      PushFront(a, zone);
84    }
85  }
86
87  // Drop elements until the current stack is equal to the tail shared with
88  // {other}. The shared tail must not only be equal, but also refer to the
89  // same memory.
90  void ResetToCommonAncestor(FunctionalList other) {
91    while (other.Size() > Size()) other.DropFront();
92    while (other.Size() < Size()) DropFront();
93    while (elements_ != other.elements_) {
94      DropFront();
95      other.DropFront();
96    }
97  }
98
99  size_t Size() const { return elements_ ? elements_->size : 0; }
100
101  void Clear() { elements_ = nullptr; }
102
103  class iterator : public base::iterator<std::forward_iterator_tag, A> {
104   public:
105    explicit iterator(Cons* cur) : current_(cur) {}
106
107    const A& operator*() const { return current_->top; }
108    iterator& operator++() {
109      current_ = current_->rest;
110      return *this;
111    }
112    bool operator==(const iterator& other) const {
113      return this->current_ == other.current_;
114    }
115    bool operator!=(const iterator& other) const { return !(*this == other); }
116
117   private:
118    Cons* current_;
119  };
120
121  iterator begin() const { return iterator(elements_); }
122  iterator end() const { return iterator(nullptr); }
123
124 private:
125  Cons* elements_;
126};
127
128}  // namespace compiler
129}  // namespace internal
130}  // namespace v8
131
132#endif  // V8_COMPILER_FUNCTIONAL_LIST_H_
133