tools/fidl/fidlc/include/fidl/recursion_detector.h

// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <algorithm>
#include <optional>
#include <vector>

#ifndef TOOLS_FIDL_FIDLC_INCLUDE_FIDL_RECURSION_DETECTOR_H_
#define TOOLS_FIDL_FIDLC_INCLUDE_FIDL_RECURSION_DETECTOR_H_

// |RecursionDetector| is a data structure that can be used to detect recursive/reentrant function
// calls. It keeps a stack of objects (pointers) that have been encountered before; if you attempt
// to re-add an already-encountered object to the stack, this is a signal that you have re-entered
// the same function.
//
// You can use this class to track recursion for more than just function calls. For example, the
// TypeShape visitor classes recursively call the same function, and that's OK; instead, they use
// this RecursionDetector class to detect whether the _parameter_ passed to the recursive function
// call is the same, in which case those functions have seen that object before, and need to break
// the recursion.
//
// To use this class:
//
// * Create a RecursionDetector object.
// * Call the Enter() method on entry to your function.
// * Pass in a pointer of any type to Enter(): the pointer serves as a "I've now encountered the
//   pointed-to object" marker to the current structure that you're traversing over.
// * Enter() will return a std::optional<Guard> object that you should assign to a local variable.
//   The Guard object will automatically pop the object off the recursion stack when your function
//   exits, via RAII.
// * If you pass in a pointer to Enter() that you've passed in before--i.e. that has been pushed
//   onto RecursionDetector's stack, and hasn't been popped yet--Enter() will return an empty
//   std::optional, which indicates that recursion has occurred.
// * Internally, the pointer you pass is cast to a void*.
class RecursionDetector {
 public:
  // See the comment on the RecursionDetector class for how to use this Guard class.
  class Guard {
   public:
    Guard() = delete;
    Guard(RecursionDetector* parent, const void* object) : parent_(parent) {
      parent_->seen_objects_.push_back(object);
    }

    Guard(const Guard&) = delete;
    Guard(const Guard&&) = delete;

    ~Guard() { parent_->seen_objects_.pop_back(); }

   private:
    RecursionDetector* parent_;
  };

  // See the comment on the RecursionDetector class for how to use this Enter() method.
  //
  // This method is templated for all pointer types, so that callers don't have to do an explicit
  // cast to const void* before passing in their pointer.
  template <typename T>
  [[nodiscard]] std::optional<Guard> Enter(const T* object) {
    const void* ptr = static_cast<const void*>(object);
    const bool seen_object =
        std::find(seen_objects_.cbegin(), seen_objects_.cend(), ptr) != seen_objects_.cend();
    if (seen_object) {
      return std::optional<Guard>();
    }

    return std::make_optional<Guard>(this, ptr);
  }

 private:
  std::vector<const void*> seen_objects_;
};

#endif  // TOOLS_FIDL_FIDLC_INCLUDE_FIDL_RECURSION_DETECTOR_H_