P4C
The P4 Compiler
Loading...
Searching...
No Matches
enumerator.h
1/*
2 * SPDX-FileCopyrightText: 2013 Barefoot Networks, Inc.
3 * Copyright 2013-present Barefoot Networks, Inc.
4 *
5 * SPDX-License-Identifier: Apache-2.0
6 */
7
8/* -*-c++-*-
9 C#-like enumerator interface */
10
11#ifndef LIB_ENUMERATOR_H_
12#define LIB_ENUMERATOR_H_
13
14#include <cstdint>
15#include <functional>
16#include <initializer_list>
17#include <iterator>
18#include <memory>
19#include <stdexcept>
20#include <string>
21#include <type_traits>
22#include <vector>
23
24#include "iterator_range.h"
25
26namespace P4::Util {
27enum class EnumeratorState { NotStarted, Valid, PastEnd };
28
29template <typename T>
30class Enumerator;
31
32template <typename T>
33using EnumeratorPtr = std::shared_ptr<Enumerator<T>>;
34
38// FIXME: It is not a proper iterator (see reference type above) and should be removed
39// in favor of more standard approach. Note that Enumerator<T>::getCurrent() always
40// returns element by value, so more or less suitable only for copyable types that are cheap
41// to copy.
42template <typename T>
43class EnumeratorHandle {
44 private:
45 Enumerator<T> *enumerator = nullptr; // when nullptr it represents end()
46 explicit EnumeratorHandle(Enumerator<T> *enumerator) : enumerator(enumerator) {}
47 template <typename U>
48 friend EnumeratorHandle<U> begin(const EnumeratorPtr<U> &enumerator);
49 template <typename U>
50 friend EnumeratorHandle<U> end(const EnumeratorPtr<U> &enumerator);
51
52 public:
53 using iterator_category = std::input_iterator_tag;
54 using difference_type = std::ptrdiff_t;
55 using value_type = T;
56 using reference = T;
57 using pointer = void;
58
59 reference operator*() const;
60 const EnumeratorHandle<T> &operator++();
61 bool operator==(const EnumeratorHandle<T> &other) const;
62 bool operator!=(const EnumeratorHandle<T> &other) const;
63};
64
66template <class T>
67class Enumerator : public std::enable_shared_from_this<Enumerator<T>> {
68 protected:
69 EnumeratorState state = EnumeratorState::NotStarted;
70
71 // This is a weird oddity of C++: this class is a friend of itself with different templates
72 template <class S>
73 friend class Enumerator;
74
75 static std::vector<T> emptyVector;
76 template <typename S>
77 friend class EnumeratorHandle;
78
79 public:
80 using value_type = T;
81
82 Enumerator() { this->reset(); }
83
84 virtual ~Enumerator() = default;
85
88 virtual bool moveNext() = 0;
90 virtual T getCurrent() const = 0;
92 virtual void reset() { this->state = EnumeratorState::NotStarted; }
93
94 const char *stateName() const {
95 switch (this->state) {
96 case EnumeratorState::NotStarted:
97 return "NotStarted";
98 case EnumeratorState::Valid:
99 return "Valid";
100 case EnumeratorState::PastEnd:
101 return "PastEnd";
102 }
103 throw std::logic_error("Unexpected state " + std::to_string(static_cast<int>(this->state)));
104 }
105
107 template <typename Container>
108 [[deprecated(
109 "Use Util::enumerate() instead")]] static EnumeratorPtr<typename Container::value_type>
110 createEnumerator(const Container &data);
111 static EnumeratorPtr<T> emptyEnumerator(); // empty data
112 template <typename Iter>
113 [[deprecated("Use Util::enumerate() instead")]] static EnumeratorPtr<typename Iter::value_type>
114 createEnumerator(Iter begin, Iter end);
115 template <typename Iter>
116 [[deprecated("Use Util::enumerate() instead")]] static EnumeratorPtr<typename Iter::value_type>
117 createEnumerator(iterator_range<Iter> range);
118
120 template <typename Filter>
121 EnumeratorPtr<T> where(Filter filter);
123 template <typename Mapper>
124 EnumeratorPtr<std::invoke_result_t<Mapper, T>> map(Mapper map);
126 template <typename S>
127 EnumeratorPtr<S> as();
129 virtual EnumeratorPtr<T> concat(EnumeratorPtr<T> other);
131 static EnumeratorPtr<T> concatAll(EnumeratorPtr<EnumeratorPtr<T>> inputs);
132
133 std::vector<T> toVector() {
134 std::vector<T> result;
135 while (moveNext()) result.push_back(getCurrent());
136 return result;
137 }
138
140 uint64_t count() {
141 uint64_t found = 0;
142 while (this->moveNext()) found++;
143 return found;
144 }
145
147 bool any() { return this->moveNext(); }
148
150 T single() {
151 bool next = moveNext();
152 if (!next) throw std::logic_error("There is no element for `single()'");
153 T result = getCurrent();
154 next = moveNext();
155 if (next) throw std::logic_error("There are multiple elements when calling `single()'");
156 return result;
157 }
158
162 bool next = moveNext();
163 if (!next) return T{};
164 T result = getCurrent();
165 next = moveNext();
166 if (next) throw std::logic_error("There are multiple elements when calling `single()'");
167 return result;
168 }
169
172 bool next = moveNext();
173 if (!next) return T{};
174 return getCurrent();
175 }
176
178 T next() {
179 bool next = moveNext();
180 if (!next) throw std::logic_error("There is no element for `next()'");
181 return getCurrent();
182 }
183};
184
186// the implementation must be in the header file due to the templates
187
190
192template <typename Iter>
193class IteratorEnumerator : public Enumerator<typename std::iterator_traits<Iter>::value_type> {
194 protected:
195 Iter begin;
196 Iter end;
197 Iter current;
198 const char *name;
199 friend class Enumerator<typename std::iterator_traits<Iter>::value_type>;
200
201 public:
202 IteratorEnumerator(Iter begin, Iter end, const char *name)
203 : Enumerator<typename std::iterator_traits<Iter>::value_type>(),
204 begin(begin),
205 end(end),
206 current(begin),
207 name(name) {}
208
209 [[nodiscard]] std::string toString() const {
210 return std::string(this->name) + ":" + this->stateName();
211 }
212
213 bool moveNext() override {
214 switch (this->state) {
215 case EnumeratorState::NotStarted:
216 this->current = this->begin;
217 if (this->current == this->end) {
218 this->state = EnumeratorState::PastEnd;
219 return false;
220 } else {
221 this->state = EnumeratorState::Valid;
222 }
223 return true;
224 case EnumeratorState::PastEnd:
225 return false;
226 case EnumeratorState::Valid:
227 ++this->current;
228 if (this->current == this->end) {
229 this->state = EnumeratorState::PastEnd;
230 return false;
231 }
232 return true;
233 }
234
235 throw std::runtime_error("Unexpected enumerator state");
236 }
237
238 typename std::iterator_traits<Iter>::value_type getCurrent() const override {
239 switch (this->state) {
240 case EnumeratorState::NotStarted:
241 throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
242 case EnumeratorState::PastEnd:
243 throw std::logic_error("You cannot call 'getCurrent' past the collection end");
244 case EnumeratorState::Valid:
245 return *this->current;
246 }
247 throw std::runtime_error("Unexpected enumerator state");
248 }
249};
250
251template <typename Iter>
252IteratorEnumerator(Iter begin, Iter end, const char *name) -> IteratorEnumerator<Iter>;
253
255
256template <typename T>
257class SingleEnumerator : public Enumerator<T> {
258 T value;
259
260 public:
261 explicit SingleEnumerator(T v) : Enumerator<T>(), value(v) {}
262 bool moveNext() {
263 switch (this->state) {
264 case EnumeratorState::NotStarted:
265 this->state = EnumeratorState::Valid;
266 return true;
267 case EnumeratorState::PastEnd:
268 return false;
269 case EnumeratorState::Valid:
270 this->state = EnumeratorState::PastEnd;
271 return false;
272 }
273 throw std::runtime_error("Unexpected enumerator state");
274 }
275 T getCurrent() const {
276 switch (this->state) {
277 case EnumeratorState::NotStarted:
278 throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
279 case EnumeratorState::PastEnd:
280 throw std::logic_error("You cannot call 'getCurrent' past the collection end");
281 case EnumeratorState::Valid:
282 return this->value;
283 }
284 throw std::runtime_error("Unexpected enumerator state");
285 }
286};
287
289
291template <typename T>
292class EmptyEnumerator : public Enumerator<T> {
293 public:
294 [[nodiscard]] std::string toString() const { return "EmptyEnumerator"; }
296 bool moveNext() override { return false; }
297 T getCurrent() const override {
298 throw std::logic_error("You cannot call 'getCurrent' on an EmptyEnumerator");
299 }
300};
301
303
309template <typename T, typename Filter>
310class FilterEnumerator final : public Enumerator<T> {
311 EnumeratorPtr<T> input;
312 Filter filter;
313 T current; // must prevent repeated evaluation
314
315 public:
316 FilterEnumerator(EnumeratorPtr<T> input, Filter filter)
317 : input(input), filter(std::move(filter)) {}
318
319 private:
320 bool advance() {
321 this->state = EnumeratorState::Valid;
322 while (this->input->moveNext()) {
323 this->current = this->input->getCurrent();
324 bool match = this->filter(this->current);
325 if (match) return true;
326 }
327 this->state = EnumeratorState::PastEnd;
328 return false;
329 }
330
331 public:
332 [[nodiscard]] std::string toString() const {
333 return "FilterEnumerator(" + this->input->toString() + "):" + this->stateName();
334 }
335
336 void reset() {
337 this->input->reset();
339 }
340
341 bool moveNext() {
342 switch (this->state) {
343 case EnumeratorState::NotStarted:
344 case EnumeratorState::Valid:
345 return this->advance();
346 case EnumeratorState::PastEnd:
347 return false;
348 }
349 throw std::runtime_error("Unexpected enumerator state");
350 }
351
352 T getCurrent() const {
353 switch (this->state) {
354 case EnumeratorState::NotStarted:
355 throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
356 case EnumeratorState::PastEnd:
357 throw std::logic_error("You cannot call 'getCurrent' past the collection end");
358 case EnumeratorState::Valid:
359 return this->current;
360 }
361 throw std::runtime_error("Unexpected enumerator state");
362 }
363};
364
366
368template <typename T, typename S>
369class AsEnumerator final : public Enumerator<S> {
370 S getCurrentImpl() const {
371 T current = input->getCurrent();
372 using Target = typename std::pointer_traits<S>::element_type;
373 if constexpr (requires { current->template to<Target>(); }) {
374 return current ? current->template to<Target>() : nullptr;
375 } else {
376 return dynamic_cast<S>(current);
377 }
378 }
379
380 protected:
381 EnumeratorPtr<T> input;
382
383 public:
384 explicit AsEnumerator(EnumeratorPtr<T> input) : input(input) {}
385
386 std::string toString() const {
387 return "AsEnumerator(" + this->input->toString() + "):" + this->stateName();
388 }
389
390 void reset() override {
392 this->input->reset();
393 }
394
395 bool moveNext() override {
396 bool result = this->input->moveNext();
397 if (result)
398 this->state = EnumeratorState::Valid;
399 else
400 this->state = EnumeratorState::PastEnd;
401 return result;
402 }
403
404 S getCurrent() const override { return getCurrentImpl(); }
405};
406
408
410template <typename T, typename S, typename Mapper>
411class MapEnumerator final : public Enumerator<S> {
412 protected:
413 EnumeratorPtr<T> input;
414 Mapper map;
415 S current;
416
417 public:
418 MapEnumerator(EnumeratorPtr<T> input, Mapper map) : input(input), map(std::move(map)) {}
419
420 void reset() {
421 this->input->reset();
423 }
424
425 [[nodiscard]] std::string toString() const {
426 return "MapEnumerator(" + this->input->toString() + "):" + this->stateName();
427 }
428
429 bool moveNext() {
430 switch (this->state) {
431 case EnumeratorState::NotStarted:
432 case EnumeratorState::Valid: {
433 bool success = input->moveNext();
434 if (success) {
435 T currentInput = this->input->getCurrent();
436 this->current = this->map(currentInput);
437 this->state = EnumeratorState::Valid;
438 return true;
439 } else {
440 this->state = EnumeratorState::PastEnd;
441 return false;
442 }
443 }
444 case EnumeratorState::PastEnd:
445 return false;
446 }
447 throw std::runtime_error("Unexpected enumerator state");
448 }
449
450 S getCurrent() const {
451 switch (this->state) {
452 case EnumeratorState::NotStarted:
453 throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
454 case EnumeratorState::PastEnd:
455 throw std::logic_error("You cannot call 'getCurrent' past the collection end");
456 case EnumeratorState::Valid:
457 return this->current;
458 }
459 throw std::runtime_error("Unexpected enumerator state");
460 }
461};
462
463template <typename T, typename Mapper>
464MapEnumerator(EnumeratorPtr<T>,
465 Mapper) -> MapEnumerator<T, typename std::invoke_result_t<Mapper, T>, Mapper>;
466
468
470template <typename T>
471class ConcatEnumerator final : public Enumerator<T> {
472 std::vector<EnumeratorPtr<T>> inputs;
473 T currentResult;
474
475 public:
476 ConcatEnumerator() = default;
477 // We take ownership of the vector
478 explicit ConcatEnumerator(std::vector<EnumeratorPtr<T>> &&inputs) : inputs(std::move(inputs)) {
479 for (const auto &currentInput : inputs)
480 if (currentInput == nullptr) throw std::logic_error("Null iterator in concatenation");
481 }
482
483 ConcatEnumerator(std::initializer_list<EnumeratorPtr<T>> inputs) : inputs(inputs) {
484 for (const auto &currentInput : inputs)
485 if (currentInput == nullptr) throw std::logic_error("Null iterator in concatenation");
486 }
487 explicit ConcatEnumerator(EnumeratorPtr<EnumeratorPtr<T>> inputs)
488 : ConcatEnumerator(inputs->toVector()) {}
489
490 [[nodiscard]] std::string toString() const { return "ConcatEnumerator:" + this->stateName(); }
491
492 private:
493 bool advance() {
494 this->state = EnumeratorState::Valid;
495 for (const auto &currentInput : inputs) {
496 if (currentInput->moveNext()) {
497 this->currentResult = currentInput->getCurrent();
498 return true;
499 }
500 }
501
502 this->state = EnumeratorState::PastEnd;
503 return false;
504 }
505
506 public:
507 EnumeratorPtr<T> concat(EnumeratorPtr<T> other) override {
508 // Too late to add
509 if (this->state == EnumeratorState::PastEnd)
510 throw std::runtime_error("Invalid enumerator state to concatenate");
511
512 inputs.push_back(other);
513
514 return this->shared_from_this();
515 }
516
517 void reset() override {
518 for (const auto &currentInput : inputs) currentInput->reset();
520 }
521
522 bool moveNext() override {
523 switch (this->state) {
524 case EnumeratorState::NotStarted:
525 case EnumeratorState::Valid:
526 return this->advance();
527 case EnumeratorState::PastEnd:
528 return false;
529 }
530 throw std::runtime_error("Unexpected enumerator state");
531 }
532
533 T getCurrent() const override {
534 switch (this->state) {
535 case EnumeratorState::NotStarted:
536 throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
537 case EnumeratorState::PastEnd:
538 throw std::logic_error("You cannot call 'getCurrent' past the collection end");
539 case EnumeratorState::Valid:
540 return this->currentResult;
541 }
542 throw std::runtime_error("Unexpected enumerator state");
543 }
544};
545
547
548template <typename T>
549template <typename Mapper>
550EnumeratorPtr<std::invoke_result_t<Mapper, T>> Enumerator<T>::map(Mapper map) {
551 return std::make_shared<MapEnumerator<T, std::invoke_result_t<Mapper, T>, Mapper>>(
552 this->shared_from_this(), std::move(map));
553}
554
555template <typename T>
556template <typename S>
557EnumeratorPtr<S> Enumerator<T>::as() {
558 return std::make_shared<AsEnumerator<T, S>>(this->shared_from_this());
559}
560
561template <typename T>
562template <typename Filter>
563EnumeratorPtr<T> Enumerator<T>::where(Filter filter) {
564 return std::make_shared<FilterEnumerator<T, Filter>>(this->shared_from_this(),
565 std::move(filter));
566}
567
568template <typename T>
569template <typename Container>
570EnumeratorPtr<typename Container::value_type> Enumerator<T>::createEnumerator(
571 const Container &data) {
572 return std::make_shared<IteratorEnumerator<decltype(data.begin())>>(data.begin(), data.end(),
573 typeid(Container).name());
574}
575
576template <typename T>
577EnumeratorPtr<T> Enumerator<T>::emptyEnumerator() {
578 return std::make_shared<EmptyEnumerator<T>>();
579}
580
581template <typename T>
582template <typename Iter>
583EnumeratorPtr<typename Iter::value_type> Enumerator<T>::createEnumerator(Iter begin, Iter end) {
584 return std::make_shared<IteratorEnumerator<Iter>>(begin, end, "iterator");
585}
586
587template <typename T>
588template <typename Iter>
589EnumeratorPtr<typename Iter::value_type> Enumerator<T>::createEnumerator(
590 iterator_range<Iter> range) {
591 return std::make_shared<IteratorEnumerator<Iter>>(range.begin(), range.end(), "range");
592}
593
594template <typename T>
595EnumeratorPtr<T> Enumerator<T>::concatAll(EnumeratorPtr<EnumeratorPtr<T>> inputs) {
596 return std::make_shared<ConcatEnumerator<T>>(inputs);
597}
598
599template <typename T>
600EnumeratorPtr<T> Enumerator<T>::concat(EnumeratorPtr<T> other) {
601 return std::make_shared<ConcatEnumerator<T>>(
602 std::initializer_list<EnumeratorPtr<T>>{this->shared_from_this(), other});
603}
604
606
607template <typename T>
608T EnumeratorHandle<T>::operator*() const {
609 if (enumerator == nullptr) throw std::logic_error("Dereferencing end() iterator");
610 return enumerator->getCurrent();
611}
612
613template <typename T>
614const EnumeratorHandle<T> &EnumeratorHandle<T>::operator++() {
615 enumerator->moveNext();
616 return *this;
617}
618
619template <typename T>
620bool EnumeratorHandle<T>::operator==(const EnumeratorHandle<T> &other) const {
621 return !(*this != other);
622}
623
624template <typename T>
625bool EnumeratorHandle<T>::operator!=(const EnumeratorHandle<T> &other) const {
626 if (this->enumerator == other.enumerator) return true;
627 if (other.enumerator != nullptr) throw std::logic_error("Comparison with different iterator");
628 return this->enumerator->state == EnumeratorState::Valid;
629}
630
631template <typename Iter>
632EnumeratorPtr<typename std::iterator_traits<Iter>::value_type> enumerate(Iter begin, Iter end) {
633 return std::make_shared<IteratorEnumerator<Iter>>(begin, end, "iterator");
634}
635
636template <typename Iter>
637EnumeratorPtr<typename std::iterator_traits<Iter>::value_type> enumerate(
638 iterator_range<Iter> range) {
639 return std::make_shared<IteratorEnumerator<Iter>>(range.begin(), range.end(), "range");
640}
641
642template <typename Container>
643EnumeratorPtr<typename Container::value_type> enumerate(const Container &data) {
644 using std::begin;
645 using std::end;
646 return std::make_shared<IteratorEnumerator<decltype(begin(data))>>(begin(data), end(data),
647 typeid(data).name());
648}
649
650// TODO: Flatten ConcatEnumerator's during concatenation
651template <typename T>
652EnumeratorPtr<T> concat(std::initializer_list<EnumeratorPtr<T>> inputs) {
653 return std::make_shared<ConcatEnumerator<T>>(inputs);
654}
655
656template <typename... Args>
657auto concat(Args &&...inputs) {
658 using FirstEnumeratorTy =
659 typename std::decay_t<std::tuple_element_t<0, std::tuple<Args...>>>::element_type;
660 std::initializer_list<EnumeratorPtr<typename FirstEnumeratorTy::value_type>> init{
661 std::forward<Args>(inputs)...};
662 return concat(init);
663}
664
667template <typename T>
668EnumeratorHandle<T> begin(const EnumeratorPtr<T> &enumerator) {
669 enumerator->moveNext();
670 return EnumeratorHandle<T>(enumerator.get());
671}
672
673template <typename T>
674EnumeratorHandle<T> end(const EnumeratorPtr<T> &) {
675 return EnumeratorHandle<T>(nullptr);
676}
677
678} // namespace P4::Util
679
680#endif /* LIB_ENUMERATOR_H_ */
S getCurrent() const override
Get current element in the collection.
Definition enumerator.h:404
void reset() override
Move back to the beginning of the collection.
Definition enumerator.h:390
bool moveNext() override
Definition enumerator.h:395
void reset() override
Move back to the beginning of the collection.
Definition enumerator.h:517
EnumeratorPtr< T > concat(EnumeratorPtr< T > other) override
Append all elements of other after all elements of this.
Definition enumerator.h:507
bool moveNext() override
Definition enumerator.h:522
T getCurrent() const override
Get current element in the collection.
Definition enumerator.h:533
Always empty iterator (equivalent to end())
Definition enumerator.h:292
bool moveNext() override
Always returns false.
Definition enumerator.h:296
T getCurrent() const override
Get current element in the collection.
Definition enumerator.h:297
Definition enumerator.h:43
Type-erased Enumerator interface.
Definition enumerator.h:67
virtual bool moveNext()=0
T nextOrDefault()
Next element, or the default value if none exists.
Definition enumerator.h:171
virtual EnumeratorPtr< T > concat(EnumeratorPtr< T > other)
Append all elements of other after all elements of this.
Definition enumerator.h:600
T single()
The only next element; throws if the enumerator does not have exactly 1 element.
Definition enumerator.h:150
EnumeratorPtr< S > as()
Cast to an enumerator of S objects.
Definition enumerator.h:557
EnumeratorPtr< std::invoke_result_t< Mapper, T > > map(Mapper map)
Apply specified function to all elements of this enumerator.
Definition enumerator.h:550
EnumeratorPtr< T > where(Filter filter)
Return an enumerator returning all elements that pass the filter.
Definition enumerator.h:563
virtual void reset()
Move back to the beginning of the collection.
Definition enumerator.h:92
bool any()
True if the enumerator has at least one element.
Definition enumerator.h:147
static EnumeratorPtr< T > concatAll(EnumeratorPtr< EnumeratorPtr< T > > inputs)
Concatenate all these collections into a single one.
Definition enumerator.h:595
virtual T getCurrent() const =0
Get current element in the collection.
T next()
Next element; throws if there are no elements.
Definition enumerator.h:178
uint64_t count()
Enumerate all elements and return the count.
Definition enumerator.h:140
T singleOrDefault()
Definition enumerator.h:161
T getCurrent() const
Get current element in the collection.
Definition enumerator.h:352
void reset()
Move back to the beginning of the collection.
Definition enumerator.h:336
bool moveNext()
Definition enumerator.h:341
A generic iterator returning elements of type T.
Definition enumerator.h:193
bool moveNext() override
Definition enumerator.h:213
std::iterator_traits< Iter >::value_type getCurrent() const override
Get current element in the collection.
Definition enumerator.h:238
void reset()
Move back to the beginning of the collection.
Definition enumerator.h:420
bool moveNext()
Definition enumerator.h:429
S getCurrent() const
Get current element in the collection.
Definition enumerator.h:450
bool moveNext()
Definition enumerator.h:262
T getCurrent() const
Get current element in the collection.
Definition enumerator.h:275
Definition iterator_range.h:44
Definition tofino/bf-asm/target.h:196
STL namespace.