// 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_