1// Copyright 2014 The Chromium 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 SANDBOX_LINUX_BPF_DSL_CONS_H_
6#define SANDBOX_LINUX_BPF_DSL_CONS_H_
7
8#include "base/macros.h"
9#include "base/memory/ref_counted.h"
10#include "sandbox/sandbox_export.h"
11
12namespace sandbox {
13namespace cons {
14
15// Namespace cons provides an abstraction for immutable "cons list"
16// data structures as commonly provided in functional programming
17// languages like Lisp or Haskell.
18//
19// A cons list is a linked list consisting of "cells", each of which
20// have a "head" and a "tail" element. A cell's head element contains
21// a user specified value, while the tail element contains a (possibly
22// null) pointer to another cell.
23//
24// An empty list (idiomatically referred to as "nil") can be
25// constructed as "cons::List<Foo>()" or simply as "nullptr" if Foo
26// can be inferred from context (e.g., calling a function that has a
27// "cons::List<Foo>" parameter).
28//
29// Existing lists (including empty lists) can be extended by
30// prepending new values to the front using the "Cons(head, tail)"
31// function, which will allocate a new cons cell. Notably, cons lists
32// support creating multiple lists that share a common tail sequence.
33//
34// Lastly, lists support iteration via C++11's range-based for loop
35// construct.
36//
37// Examples:
38//
39//   // basic construction
40//   const cons::List<char> kNil = nullptr;
41//   cons::List<char> ba = Cons('b', Cons('a', kNil));
42//
43//   // common tail sequence
44//   cons::List<char> cba = Cons('c', ba);
45//   cons::List<char> dba = Cons('d', ba);
46//
47//   // iteration
48//   for (const char& ch : cba) {
49//     // iterates 'c', 'b', 'a'
50//   }
51//   for (const char& ch : dba) {
52//     // iterates 'd', 'b', 'a'
53//   }
54
55// Forward declarations.
56template <typename T>
57class Cell;
58template <typename T>
59class ListIterator;
60
61// List represents a (possibly null) pointer to a cons cell.
62template <typename T>
63using List = scoped_refptr<const Cell<T>>;
64
65// Cons extends a cons list by prepending a new value to the front.
66template <typename T>
67List<T> Cons(const T& head, const List<T>& tail) {
68  return List<T>(new const Cell<T>(head, tail));
69}
70
71// Cell represents an individual "cons cell" within a cons list.
72template <typename T>
73class Cell : public base::RefCounted<Cell<T>> {
74 public:
75  Cell(const T& head, const List<T>& tail) : head_(head), tail_(tail) {}
76
77  // Head returns this cell's head element.
78  const T& head() const { return head_; }
79
80  // Tail returns this cell's tail element.
81  const List<T>& tail() const { return tail_; }
82
83 private:
84  virtual ~Cell() {}
85
86  T head_;
87  List<T> tail_;
88
89  friend class base::RefCounted<Cell<T>>;
90  DISALLOW_COPY_AND_ASSIGN(Cell);
91};
92
93// Begin returns a list iterator pointing to the first element of the
94// cons list. It's provided to support range-based for loops.
95template <typename T>
96ListIterator<T> begin(const List<T>& list) {
97  return ListIterator<T>(list);
98}
99
100// End returns a list iterator pointing to the "past-the-end" element
101// of the cons list (i.e., nil). It's provided to support range-based
102// for loops.
103template <typename T>
104ListIterator<T> end(const List<T>& list) {
105  return ListIterator<T>();
106}
107
108// ListIterator provides C++ forward iterator semantics for traversing
109// a cons list.
110template <typename T>
111class ListIterator {
112 public:
113  ListIterator() : list_() {}
114  explicit ListIterator(const List<T>& list) : list_(list) {}
115
116  const T& operator*() const { return list_->head(); }
117
118  ListIterator& operator++() {
119    list_ = list_->tail();
120    return *this;
121  }
122
123  friend bool operator==(const ListIterator& lhs, const ListIterator& rhs) {
124    return lhs.list_ == rhs.list_;
125  }
126
127 private:
128  List<T> list_;
129};
130
131template <typename T>
132bool operator!=(const ListIterator<T>& lhs, const ListIterator<T>& rhs) {
133  return !(lhs == rhs);
134}
135
136}  // namespace cons
137}  // namespace sandbox
138
139#endif  // SANDBOX_LINUX_BPF_DSL_CONS_H_
140