frame.h

#ifndef SOURCEMETA_BLAZE_FRAME_H_
#define SOURCEMETA_BLAZE_FRAME_H_
 
 
#ifndef SOURCEMETA_BLAZE_FRAME_EXPORT
#include <sourcemeta/blaze/frame_export.h>
#endif
 
// NOLINTBEGIN(misc-include-cleaner)
#include <sourcemeta/blaze/frame_error.h>
// NOLINTEND(misc-include-cleaner)
 
#include <sourcemeta/blaze/foundation.h>
 
#include <sourcemeta/core/json.h>
#include <sourcemeta/core/jsonpointer.h>
 
#include <concepts>      // std::invocable
#include <cstdint>       // std::uint8_t
#include <functional>    // std::reference_wrapper
#include <map>           // std::map
#include <optional>      // std::optional
#include <set>           // std::set
#include <tuple>         // std::tuple
#include <unordered_map> // std::unordered_map
#include <unordered_set> // std::unordered_set
#include <utility>       // std::pair
#include <vector>        // std::vector
 
namespace sourcemeta::blaze {
 
class SOURCEMETA_BLAZE_FRAME_EXPORT SchemaFrame {
public:
  enum class Mode : std::uint8_t { Locations, References };
 
  SchemaFrame(const Mode mode) : mode_{mode} {}
 
  // We rely on internal caches that would be dangling otherwise
  SchemaFrame(const SchemaFrame &) = delete;
  auto operator=(const SchemaFrame &) -> SchemaFrame & = delete;
  SchemaFrame(SchemaFrame &&) = delete;
  auto operator=(SchemaFrame &&) -> SchemaFrame & = delete;
 
  // Query the current mode that the schema frame was configured with
  [[nodiscard]] auto mode() const noexcept -> Mode { return this->mode_; }
 
  struct ReferencesEntry {
    std::string_view original;
    // TODO: This one is tricky to turn into a view, as there is no
    // location entry to point to if it is an external unresolved reference
    sourcemeta::core::JSON::String destination;
    // Empty means no base
    std::string_view base;
    std::optional<std::string_view> fragment;
  };
 
  using References =
      std::map<std::pair<SchemaReferenceType, sourcemeta::core::WeakPointer>,
               ReferencesEntry>;
 
#if defined(__GNUC__)
#pragma GCC diagnostic push
// GCC believes that a member of an enum class (which is namespaced by
// definition), can shadow an alias defined even on a different namespace.
#pragma GCC diagnostic ignored "-Wshadow"
#endif
  enum class LocationType : std::uint8_t {
    Resource,
    Anchor,
    // TODO: Distinguish between a Pointer and a Keyword
    Pointer,
    Subschema
  };
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
 
  struct Location {
    std::optional<sourcemeta::core::WeakPointer> parent;
    LocationType type;
    std::string_view base;
    sourcemeta::core::WeakPointer pointer;
    std::size_t relative_pointer;
    std::string_view dialect;
    SchemaBaseDialect base_dialect;
    bool property_name;
    bool orphan;
  };
 
  // TODO: Consider replacing std::map with std::flat_map once libc++
  // supports it (__cpp_lib_flat_map) for better cache locality
  using Locations =
      // While it might seem weird that we namespace the location URIs with a
      // reference type, it is essential for distinguishing schema resource URIs
      // from `$recursiveRef: true` on another place of the schema schema
      // resource, as otherwise they would both have the exact same URI, but
      // point to different places.
      std::map<std::pair<SchemaReferenceType, sourcemeta::core::JSON::String>,
               Location>;
 
  using Paths = std::vector<sourcemeta::core::WeakPointer>;
 
  [[nodiscard]] auto to_json(
      const std::optional<sourcemeta::core::PointerPositionTracker> &tracker =
          std::nullopt) const -> sourcemeta::core::JSON;
 
  auto analyse(const sourcemeta::core::JSON &root, const SchemaWalker &walker,
               const SchemaResolver &resolver,
               std::string_view default_dialect = "",
               std::string_view default_id = "",
               const Paths &paths = {sourcemeta::core::empty_weak_pointer})
      -> void;
 
  [[nodiscard]] auto locations() const noexcept -> const Locations &;
 
  [[nodiscard]] auto references() const noexcept -> const References &;
 
  [[nodiscard]] auto
  reference(const SchemaReferenceType type,
            const sourcemeta::core::WeakPointer &pointer) const
      -> std::optional<std::reference_wrapper<const ReferencesEntry>>;
 
  [[nodiscard]] auto standalone() const noexcept -> bool;
 
  [[nodiscard]] auto root() const noexcept
      -> const sourcemeta::core::JSON::String &;
 
  [[nodiscard]] auto vocabularies(const Location &location,
                                  const SchemaResolver &resolver) const
      -> Vocabularies;
 
  [[nodiscard]] auto
  uri(const Location &location,
      const sourcemeta::core::WeakPointer &relative_schema_location =
          sourcemeta::core::empty_weak_pointer) const
      -> sourcemeta::core::JSON::String;
 
  [[nodiscard]] auto
  traverse(const Location &location,
           const sourcemeta::core::WeakPointer &relative_schema_location) const
      -> const Location &;
 
  [[nodiscard]] auto traverse(const std::string_view uri) const
      -> std::optional<std::reference_wrapper<const Location>>;
 
  [[nodiscard]] auto
  traverse(const sourcemeta::core::WeakPointer &pointer) const
      -> std::optional<std::reference_wrapper<const Location>>;
 
  [[nodiscard]] auto traverse(const sourcemeta::core::WeakPointer &pointer,
                              const LocationType type) const
      -> std::optional<std::reference_wrapper<const Location>>;
 
  [[nodiscard]] auto uri(const sourcemeta::core::WeakPointer &pointer) const
      -> std::optional<
          std::reference_wrapper<const sourcemeta::core::JSON::String>>;
 
  [[nodiscard]] auto
  dereference(const Location &location,
              const sourcemeta::core::WeakPointer &relative_schema_location =
                  sourcemeta::core::empty_weak_pointer) const
      -> std::pair<SchemaReferenceType,
                   std::optional<std::reference_wrapper<const Location>>>;
 
  template <std::invocable<std::string_view> F>
  auto for_each_resource_uri(const F &callback) const -> void {
    for (const auto &[key, location] : this->locations_) {
      if (location.type == LocationType::Resource) {
        callback(key.second);
      }
    }
  }
 
  template <std::invocable<const sourcemeta::core::WeakPointer &,
                           const ReferencesEntry &>
                F>
  auto for_each_unresolved_reference(const F &callback) const -> void {
    for (const auto &[key, reference] : this->references_) {
      if (!this->traverse(reference.destination).has_value()) {
        callback(key.second, reference);
      }
    }
  }
 
  [[nodiscard]] auto
  has_references_to(const sourcemeta::core::WeakPointer &pointer) const -> bool;
 
  [[nodiscard]] auto
  has_references_through(const sourcemeta::core::WeakPointer &pointer) const
      -> bool;
  [[nodiscard]] auto
  has_references_through(const sourcemeta::core::WeakPointer &pointer,
                         const sourcemeta::core::WeakPointer::Token &tail) const
      -> bool;
 
  [[nodiscard]] auto relative_instance_location(const Location &location) const
      -> sourcemeta::core::WeakPointer;
 
  [[nodiscard]] auto empty() const noexcept -> bool;
 
  auto reset() -> void;
 
  [[nodiscard]] auto is_reachable(const Location &base,
                                  const Location &location,
                                  const SchemaWalker &walker,
                                  const SchemaResolver &resolver) const -> bool;
 
private:
  Mode mode_;
// Exporting symbols that depends on the standard C++ library is considered
// safe.
// https://learn.microsoft.com/en-us/cpp/error-messages/compiler-warnings/compiler-warning-level-2-c4275?view=msvc-170&redirectedfrom=MSDN
#if defined(_MSC_VER)
#pragma warning(disable : 4251 4275)
#endif
  sourcemeta::core::JSON::String root_;
  Locations locations_;
  References references_;
  // Custom meta-schemas that the resolver could not resolve but that were
  // found embedded in the analysed document itself. The values point into
  // the analysed document, which the frame must not outlive anyway
  std::unordered_map<sourcemeta::core::JSON::String,
                     const sourcemeta::core::JSON *>
      probed_metaschemas_;
  mutable std::unordered_map<
      std::reference_wrapper<const sourcemeta::core::WeakPointer>,
      std::vector<const Location *>, sourcemeta::core::WeakPointer::Hasher,
      sourcemeta::core::WeakPointer::Comparator>
      pointer_to_location_;
  mutable std::unordered_set<
      std::reference_wrapper<const sourcemeta::core::WeakPointer>,
      sourcemeta::core::WeakPointer::Hasher,
      sourcemeta::core::WeakPointer::Comparator>
      pointers_with_non_orphan_;
  using ReachabilityCache =
      std::unordered_map<const sourcemeta::core::WeakPointer *, bool>;
  struct ReachabilityKey {
    const sourcemeta::core::WeakPointer *pointer;
    bool orphan;
    auto operator==(const ReachabilityKey &other) const noexcept -> bool {
      return this->pointer == other.pointer && this->orphan == other.orphan;
    }
  };
  struct ReachabilityKeyHasher {
    auto operator()(const ReachabilityKey &key) const noexcept -> std::size_t {
      return std::hash<const void *>{}(key.pointer) ^
             (std::hash<bool>{}(key.orphan) << 1);
    }
  };
  mutable std::unordered_map<ReachabilityKey, ReachabilityCache,
                             ReachabilityKeyHasher>
      reachability_;
  mutable std::unordered_map<
      std::reference_wrapper<const sourcemeta::core::WeakPointer>,
      std::vector<const sourcemeta::core::WeakPointer *>,
      sourcemeta::core::WeakPointer::Hasher,
      sourcemeta::core::WeakPointer::Comparator>
      references_by_destination_;
  mutable std::unordered_set<
      std::reference_wrapper<const sourcemeta::core::WeakPointer>,
      sourcemeta::core::WeakPointer::Hasher,
      sourcemeta::core::WeakPointer::Comparator>
      location_members_children_;
  mutable std::unordered_map<
      std::reference_wrapper<const sourcemeta::core::WeakPointer>,
      std::vector<const Location *>, sourcemeta::core::WeakPointer::Hasher,
      sourcemeta::core::WeakPointer::Comparator>
      descendants_by_pointer_;
  struct PotentialSource {
    const sourcemeta::core::WeakPointer *source_pointer;
    sourcemeta::core::WeakPointer source_parent;
    bool crosses;
  };
  mutable std::unordered_map<const Location *, std::vector<PotentialSource>>
      potential_sources_by_location_;
  struct ReachabilityEdge {
    const Location *target;
    bool orphan_context_only;
    bool is_reference;
  };
  mutable std::unordered_map<const Location *, std::vector<ReachabilityEdge>>
      reachability_graph_;
  mutable std::unordered_map<
      std::reference_wrapper<const sourcemeta::core::WeakPointer>,
      const sourcemeta::core::WeakPointer *,
      sourcemeta::core::WeakPointer::Hasher,
      sourcemeta::core::WeakPointer::Comparator>
      canonical_pointer_;
  mutable std::unordered_map<const Location *,
                             const sourcemeta::core::WeakPointer *>
      location_to_canonical_;
  bool standalone_{false};
 
  auto populate_pointer_to_location() const -> void;
  auto populate_reference_graph() const -> void;
  auto populate_location_members(const SchemaWalker &walker,
                                 const SchemaResolver &resolver) const -> void;
  auto populate_descendants() const -> void;
  auto populate_potential_sources(const SchemaWalker &walker,
                                  const SchemaResolver &resolver) const -> void;
  auto populate_reachability_graph(const SchemaWalker &walker,
                                   const SchemaResolver &resolver) const
      -> void;
  auto populate_reachability(const Location &base, const SchemaWalker &walker,
                             const SchemaResolver &resolver) const
      -> const ReachabilityCache &;
#if defined(_MSC_VER)
#pragma warning(default : 4251 4275)
#endif
};
 
} // namespace sourcemeta::blaze
 
#endif