ploidy_core/ir/views/
mod.rs

1//! Graph-aware views of IR types.
2//!
3//! Views are cheap, read-only types that pair a node with its cooked graph,
4//! so they can answer questions about an IR type and its relationships.
5//! The submodules document the OpenAPI concept that each view represents.
6//!
7//! # The `View` trait
8//!
9//! All view types implement [`View`], which provides graph traversal methods:
10//!
11//! * [`View::inlines()`] iterates over inline types nested within this type.
12//!   Use this to emit inline type definitions alongside their parent.
13//! * [`View::used_by()`] iterates over operations that reference this type.
14//!   Useful for generating per-operation imports or feature gates.
15//! * [`View::dependencies()`] iterates over all types that this type
16//!   transitively depends on. Use this for import lists, feature gates,
17//!   and topological ordering.
18//! * [`View::dependents()`] iterates over all types that transitively depend on
19//!   this type. Useful for impact analysis or invalidation.
20//! * [`View::traverse()`] traverses the graph breadth-first with a filter that
21//!   controls which nodes to yield and explore.
22//!
23//! # Extensions
24//!
25//! [`ExtendableView`] attaches a type-erased extension map to each view node.
26//! Codegen backends use this to store and retrieve arbitrary metadata.
27
28use std::{any::TypeId, fmt::Debug};
29
30use atomic_refcell::{AtomicRef, AtomicRefMut};
31use petgraph::{
32    Direction,
33    graph::NodeIndex,
34    visit::{Bfs, EdgeFiltered, EdgeRef},
35};
36use ref_cast::{RefCastCustom, ref_cast_custom};
37
38use super::{
39    graph::{CookedGraph, EdgeKind, Extension, ExtensionMap, Traversal, Traverse},
40    types::GraphType,
41};
42
43pub mod any;
44pub mod container;
45pub mod enum_;
46pub mod inline;
47pub mod ir;
48pub mod operation;
49pub mod primitive;
50pub mod schema;
51pub mod struct_;
52pub mod tagged;
53pub mod untagged;
54
55use self::{inline::InlineTypeView, ir::TypeView, operation::OperationView};
56
57/// A view of a type in the graph.
58pub trait View<'a> {
59    /// Returns an iterator over all the inline types that are
60    /// contained within this type.
61    fn inlines(&self) -> impl Iterator<Item = InlineTypeView<'a>> + use<'a, Self>;
62
63    /// Returns an iterator over the operations that use this type.
64    ///
65    /// This is backward propagation: each operation depends on this type.
66    fn used_by(&self) -> impl Iterator<Item = OperationView<'a>> + use<'a, Self>;
67
68    /// Returns an iterator over all the types that this type transitively depends on.
69    /// This is forward propagation: this type depends on each reachable type.
70    ///
71    /// Complexity: O(n), where `n` is the number of dependency types.
72    fn dependencies(&self) -> impl Iterator<Item = TypeView<'a>> + use<'a, Self>;
73
74    /// Returns an iterator over all the types that transitively depend on this type.
75    /// This is backward propagation: each returned type depends on this type.
76    ///
77    /// Complexity: O(n), where `n` is the number of dependent types.
78    fn dependents(&self) -> impl Iterator<Item = TypeView<'a>> + use<'a, Self>;
79
80    /// Traverses this type's dependencies or dependents breadth-first,
81    /// using `filter` to control which nodes are yielded and explored.
82    ///
83    /// The filter receives the [`EdgeKind`] describing how the node
84    /// was reached, and returns a [`Traversal`].
85    ///
86    /// A node reachable via multiple edge kinds may be yielded more
87    /// than once, once per distinct edge kind.
88    ///
89    /// Complexity: O(V + E) over the visited subgraph.
90    fn traverse<F>(
91        &self,
92        reach: Reach,
93        filter: F,
94    ) -> impl Iterator<Item = TypeView<'a>> + use<'a, Self, F>
95    where
96        F: Fn(EdgeKind, &TypeView<'a>) -> Traversal;
97}
98
99/// A view of a graph type with extended data.
100///
101/// Codegen backends use extended data to decorate types with extra information.
102/// For example, Rust codegen stores a unique identifier on each schema type,
103/// so that names never collide after case conversion.
104pub trait ExtendableView<'a>: View<'a> {
105    /// Returns a reference to this type's extended data.
106    fn extensions(&self) -> &ViewExtensions<Self>
107    where
108        Self: Sized;
109
110    /// Returns a mutable reference to this type's extended data.
111    fn extensions_mut(&mut self) -> &mut ViewExtensions<Self>
112    where
113        Self: Sized;
114}
115
116impl<'a, T> View<'a> for T
117where
118    T: ViewNode<'a>,
119{
120    #[inline]
121    fn inlines(&self) -> impl Iterator<Item = InlineTypeView<'a>> + use<'a, T> {
122        let cooked = self.cooked();
123        // Only include edges to other inline schemas.
124        let filtered = EdgeFiltered::from_fn(&cooked.graph, |e| {
125            matches!(cooked.graph[e.target()], GraphType::Inline(_))
126        });
127        let mut bfs = Bfs::new(&cooked.graph, self.index());
128        std::iter::from_fn(move || bfs.next(&filtered)).filter_map(|index| {
129            match cooked.graph[index] {
130                GraphType::Inline(ty) => Some(InlineTypeView::new(cooked, index, ty)),
131                _ => None,
132            }
133        })
134    }
135
136    #[inline]
137    fn used_by(&self) -> impl Iterator<Item = OperationView<'a>> + use<'a, T> {
138        let cooked = self.cooked();
139        let meta = &cooked.metadata.schemas[self.index().index()];
140        meta.used_by.iter().map(|op| OperationView::new(cooked, op))
141    }
142
143    #[inline]
144    fn dependencies(&self) -> impl Iterator<Item = TypeView<'a>> + use<'a, T> {
145        let cooked = self.cooked();
146        let meta = &cooked.metadata.schemas[self.index().index()];
147        meta.dependencies
148            .ones()
149            .map(NodeIndex::new)
150            .map(|index| TypeView::new(cooked, index))
151    }
152
153    #[inline]
154    fn dependents(&self) -> impl Iterator<Item = TypeView<'a>> + use<'a, T> {
155        let cooked = self.cooked();
156        let meta = &cooked.metadata.schemas[self.index().index()];
157        meta.dependents
158            .ones()
159            .map(NodeIndex::new)
160            .map(move |index| TypeView::new(cooked, index))
161    }
162
163    #[inline]
164    fn traverse<F>(
165        &self,
166        reach: Reach,
167        filter: F,
168    ) -> impl Iterator<Item = TypeView<'a>> + use<'a, T, F>
169    where
170        F: Fn(EdgeKind, &TypeView<'a>) -> Traversal,
171    {
172        let cooked = self.cooked();
173        let t = Traverse::from_neighbors(
174            &cooked.graph,
175            self.index(),
176            match reach {
177                Reach::Dependencies => Direction::Outgoing,
178                Reach::Dependents => Direction::Incoming,
179            },
180        );
181        t.run(move |kind, index| {
182            let view = TypeView::new(cooked, index);
183            filter(kind, &view)
184        })
185        .map(|index| TypeView::new(cooked, index))
186    }
187}
188
189impl<'a, T> ExtendableView<'a> for T
190where
191    T: ViewNode<'a>,
192{
193    #[inline]
194    fn extensions(&self) -> &ViewExtensions<Self> {
195        ViewExtensions::new(self)
196    }
197
198    #[inline]
199    fn extensions_mut(&mut self) -> &mut ViewExtensions<Self> {
200        ViewExtensions::new_mut(self)
201    }
202}
203
204pub(crate) trait ViewNode<'a> {
205    fn cooked(&self) -> &'a CookedGraph<'a>;
206    fn index(&self) -> NodeIndex<usize>;
207}
208
209impl<'graph, T> internal::Extendable<'graph> for T
210where
211    T: ViewNode<'graph>,
212{
213    #[inline]
214    fn ext<'view>(&'view self) -> AtomicRef<'view, ExtensionMap>
215    where
216        'graph: 'view,
217    {
218        self.cooked().metadata.schemas[self.index().index()]
219            .extensions
220            .borrow()
221    }
222
223    #[inline]
224    fn ext_mut<'b>(&'b mut self) -> AtomicRefMut<'b, ExtensionMap>
225    where
226        'graph: 'b,
227    {
228        self.cooked().metadata.schemas[self.index().index()]
229            .extensions
230            .borrow_mut()
231    }
232}
233
234/// Extended data attached to a graph type.
235#[derive(RefCastCustom)]
236#[repr(transparent)]
237pub struct ViewExtensions<X>(X);
238
239impl<X> ViewExtensions<X> {
240    #[ref_cast_custom]
241    fn new(view: &X) -> &Self;
242
243    #[ref_cast_custom]
244    fn new_mut(view: &mut X) -> &mut Self;
245}
246
247impl<'a, X: internal::Extendable<'a>> ViewExtensions<X> {
248    /// Returns a reference to a value of an arbitrary type that was
249    /// previously inserted into this extended data.
250    #[inline]
251    pub fn get<'b, T: Send + Sync + 'static>(&'b self) -> Option<AtomicRef<'b, T>>
252    where
253        'a: 'b,
254    {
255        AtomicRef::filter_map(self.0.ext(), |ext| {
256            Some(
257                ext.get(&TypeId::of::<T>())?
258                    .as_ref()
259                    .downcast_ref::<T>()
260                    .unwrap(),
261            )
262        })
263    }
264
265    /// Inserts a value of an arbitrary type into this extended data,
266    /// and returns the previous value for that type.
267    #[inline]
268    pub fn insert<T: Send + Sync + 'static>(&mut self, value: T) -> Option<T> {
269        self.0
270            .ext_mut()
271            .insert(TypeId::of::<T>(), Box::new(value))
272            .and_then(|old| *Extension::into_inner(old).downcast().unwrap())
273    }
274}
275
276impl<X> Debug for ViewExtensions<X> {
277    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
278        f.debug_tuple("ViewExtensions").finish_non_exhaustive()
279    }
280}
281
282/// Selects which edge direction to follow during traversal.
283#[derive(Clone, Copy, Debug, Eq, PartialEq)]
284pub enum Reach {
285    /// Traverse out toward types that this node depends on.
286    Dependencies,
287    /// Traverse in toward types that depend on this node.
288    Dependents,
289}
290
291mod internal {
292    use atomic_refcell::{AtomicRef, AtomicRefMut};
293
294    use super::ExtensionMap;
295
296    pub trait Extendable<'graph> {
297        // These lifetime requirements might look redundant, but they're not:
298        // we're shortening the lifetime of the `AtomicRef` from `'graph` to `'view`,
299        // to prevent overlapping mutable borrows of the underlying `AtomicRefCell`
300        // at compile time.
301        //
302        // (`AtomicRefCell` panics on these illegal borrows at runtime, which is
303        // always memory-safe; we just want some extra type safety).
304        //
305        // This approach handles the obvious case of overlapping borrows from
306        // `ext()` and `ext_mut()`, and the `AtomicRefCell` avoids plumbing
307        // mutable references to the graph through every IR layer.
308
309        fn ext<'view>(&'view self) -> AtomicRef<'view, ExtensionMap>
310        where
311            'graph: 'view;
312
313        fn ext_mut<'view>(&'view mut self) -> AtomicRefMut<'view, ExtensionMap>
314        where
315            'graph: 'view;
316    }
317}
ploidy_core/ir/views/mod.rs

ploidy_core/ir/views/
mod.rs
