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 11 namespace v8 { 12 namespace internal { 13 namespace 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. 23 template <class A> 24 class FunctionalList { 25 private: 26 struct Cons : ZoneObject { ConsCons27 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: FunctionalList()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 TriviallyEquals(const FunctionalList<A> & other)52 bool TriviallyEquals(const FunctionalList<A>& other) const { 53 return elements_ == other.elements_; 54 } 55 Front()56 const A& Front() const { 57 DCHECK_GT(Size(), 0); 58 return elements_->top; 59 } 60 Rest()61 FunctionalList Rest() const { 62 FunctionalList result = *this; 63 result.DropFront(); 64 return result; 65 } 66 DropFront()67 void DropFront() { 68 CHECK_GT(Size(), 0); 69 elements_ = elements_->rest; 70 } 71 PushFront(A a,Zone * zone)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}. PushFront(A a,Zone * zone,FunctionalList 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. ResetToCommonAncestor(FunctionalList other)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 Size()99 size_t Size() const { return elements_ ? elements_->size : 0; } 100 Clear()101 void Clear() { elements_ = nullptr; } 102 103 class iterator : public base::iterator<std::forward_iterator_tag, A> { 104 public: iterator(Cons * cur)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 begin()121 iterator begin() const { return iterator(elements_); } end()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