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