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 
12 namespace sandbox {
13 namespace 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.
56 template <typename T>
57 class Cell;
58 template <typename T>
59 class ListIterator;
60 
61 // List represents a (possibly null) pointer to a cons cell.
62 template <typename T>
63 using List = scoped_refptr<const Cell<T>>;
64 
65 // Cons extends a cons list by prepending a new value to the front.
66 template <typename T>
Cons(const T & head,const List<T> & tail)67 List<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.
72 template <typename T>
73 class Cell : public base::RefCounted<Cell<T>> {
74  public:
Cell(const T & head,const List<T> & tail)75   Cell(const T& head, const List<T>& tail) : head_(head), tail_(tail) {}
76 
77   // Head returns this cell's head element.
head()78   const T& head() const { return head_; }
79 
80   // Tail returns this cell's tail element.
tail()81   const List<T>& tail() const { return tail_; }
82 
83  private:
~Cell()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.
95 template <typename T>
begin(const List<T> & list)96 ListIterator<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.
103 template <typename T>
end(const List<T> & list)104 ListIterator<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.
110 template <typename T>
111 class ListIterator {
112  public:
ListIterator()113   ListIterator() : list_() {}
ListIterator(const List<T> & 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 
131 template <typename T>
132 bool 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