typeck_lang/mono.rs
1//! The monomorphization plan: which instances of generic items a program
2//! needs, and how each is compiled.
3//!
4//! A generic item is compiled either as a **copy** per instantiation (every
5//! placeholder replaced by a concrete type: fastest code, more code), or
6//! **shared** through dictionary passing (one body; the implementations its
7//! bounds need are passed at run time). LANGUAGES.md's Iron asks for a
8//! *selective* policy: copy small (or explicitly marked) generics, share the
9//! rest. The plan lists every instance reachable from the program's
10//! non-generic code, with its strategy; trait-method calls on placeholders
11//! are resolved to the implementing method of each instance.
12
13use alloc::vec::Vec;
14
15use hir_lang::{ExprId, ItemId};
16
17use crate::types::TypeId;
18
19/// How a generic item is compiled.
20///
21/// # Examples
22///
23/// ```
24/// use typeck_lang::Strategy;
25///
26/// assert_ne!(Strategy::Copy, Strategy::Shared);
27/// ```
28#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
29pub enum Strategy {
30 /// One copy per instantiation, with concrete types.
31 Copy,
32 /// One shared body; the implementations its bounds need are passed as
33 /// dictionaries.
34 Shared,
35}
36
37/// Which generic items a profile copies and which it shares.
38///
39/// [`Checker::declare_mono_attribute`](crate::Checker::declare_mono_attribute)
40/// lets an attribute on an item override the policy (a language's
41/// `@inline` or `@hot`).
42///
43/// # Examples
44///
45/// ```
46/// use typeck_lang::MonoPolicy;
47///
48/// let iron = MonoPolicy::Selective { max_nodes: 64 };
49/// assert_ne!(iron, MonoPolicy::Copy);
50/// ```
51#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
52#[non_exhaustive]
53pub enum MonoPolicy {
54 /// Copy every generic item (Rust, Kraken).
55 Copy,
56 /// Share every generic item (dictionary passing everywhere).
57 Shared,
58 /// Copy generic items whose body has at most `max_nodes` HIR nodes;
59 /// share the rest (Iron).
60 Selective {
61 /// The largest body, in live HIR nodes, that is copied.
62 max_nodes: u32,
63 },
64}
65
66/// One instance in a [`MonoPlan`].
67///
68/// # Examples
69///
70/// ```
71/// use typeck_lang::{Instance, Strategy};
72///
73/// fn describe(i: Instance<'_>) -> usize {
74/// if i.strategy == Strategy::Copy { i.args.len() } else { 0 }
75/// }
76/// # let _ = describe;
77/// ```
78#[derive(Clone, Copy, Debug, PartialEq, Eq)]
79pub struct Instance<'a> {
80 /// The generic item (a function, possibly a method of a generic impl or
81 /// interface).
82 pub item: ItemId,
83 /// The item's placeholders, in order, replaced by concrete types (owner
84 /// placeholders first: an interface's `Self` and the owner's parameters,
85 /// then the item's own). For a [`Strategy::Shared`] item reached only
86 /// from other shared code, the item's own placeholders.
87 pub args: &'a [TypeId],
88 /// How the instance is compiled.
89 pub strategy: Strategy,
90}
91
92/// The instances a program needs.
93///
94/// # Examples
95///
96/// ```
97/// use hir_lang::Builder;
98/// use typeck_lang::{check, Profile};
99///
100/// let mut b = Builder::new();
101/// let root = b.module(None, &[]);
102/// let hir = b.finish(root)?;
103/// let typed = check(&hir, &Profile::static_inferred()).unwrap();
104/// assert!(typed.mono_plan().is_empty());
105/// # Ok::<(), hir_lang::HirError>(())
106/// ```
107#[derive(Clone, Debug, Default, PartialEq, Eq)]
108pub struct MonoPlan {
109 pub(crate) instances: Vec<(ItemId, u32, u32, Strategy)>,
110 pub(crate) args: Vec<TypeId>,
111}
112
113impl MonoPlan {
114 /// The number of instances.
115 ///
116 /// # Examples
117 ///
118 /// ```
119 /// assert_eq!(typeck_lang::MonoPlan::default().len(), 0);
120 /// ```
121 #[must_use]
122 pub fn len(&self) -> usize {
123 self.instances.len()
124 }
125
126 /// Whether the plan has no instances (the program uses no generic
127 /// function).
128 ///
129 /// # Examples
130 ///
131 /// ```
132 /// assert!(typeck_lang::MonoPlan::default().is_empty());
133 /// ```
134 #[must_use]
135 pub fn is_empty(&self) -> bool {
136 self.instances.is_empty()
137 }
138
139 /// The instances, in discovery order (breadth first from the program's
140 /// non-generic items).
141 ///
142 /// # Examples
143 ///
144 /// ```
145 /// let plan = typeck_lang::MonoPlan::default();
146 /// assert_eq!(plan.instances().count(), 0);
147 /// ```
148 pub fn instances(&self) -> impl Iterator<Item = Instance<'_>> + '_ {
149 self.instances
150 .iter()
151 .map(|&(item, start, len, strategy)| Instance {
152 item,
153 args: self
154 .args
155 .get(start as usize..(start as usize).saturating_add(len as usize))
156 .unwrap_or(&[]),
157 strategy,
158 })
159 }
160
161 /// The instances of one item.
162 ///
163 /// # Examples
164 ///
165 /// ```
166 /// let plan = typeck_lang::MonoPlan::default();
167 /// let item = hir_lang::ItemId::from_index(0).unwrap();
168 /// assert_eq!(plan.instances_of(item).count(), 0);
169 /// ```
170 pub fn instances_of(&self, item: ItemId) -> impl Iterator<Item = Instance<'_>> + '_ {
171 self.instances().filter(move |i| i.item == item)
172 }
173}
174
175/// How a call reaches its callee.
176///
177/// # Examples
178///
179/// ```
180/// use typeck_lang::Dispatch;
181///
182/// assert_ne!(Dispatch::Static, Dispatch::Dynamic);
183/// ```
184#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
185#[non_exhaustive]
186pub enum Dispatch {
187 /// The callee is known here.
188 Static,
189 /// An interface method called on a placeholder (inside a generic item):
190 /// the implementing method depends on the instance (resolved per
191 /// instance in the [`MonoPlan`], or through the dictionary of a shared
192 /// item).
193 Bound,
194 /// An interface method called on a `dyn` value: dispatched at run time.
195 Dynamic,
196}
197
198/// The generic item an expression uses and its arguments: a path to a
199/// generic function, a method call, a constructor of a generic type.
200///
201/// # Examples
202///
203/// ```
204/// use typeck_lang::{Dispatch, Instantiation};
205///
206/// fn is_virtual(i: Instantiation<'_>) -> bool {
207/// i.dispatch == Dispatch::Dynamic
208/// }
209/// # let _ = is_virtual;
210/// ```
211#[derive(Clone, Copy, Debug, PartialEq, Eq)]
212pub struct Instantiation<'a> {
213 /// The item used.
214 pub item: ItemId,
215 /// Its placeholders' arguments (they may mention the placeholders of the
216 /// item the expression is in).
217 pub args: &'a [TypeId],
218 /// How the call is dispatched.
219 pub dispatch: Dispatch,
220}
221
222/// One recorded use of an item, for the plan.
223#[derive(Clone, Copy, Debug)]
224pub(crate) struct Use {
225 pub(crate) at: ExprId,
226 /// The item whose body contains the use (`None`: a constant context).
227 pub(crate) owner: Option<ItemId>,
228 pub(crate) callee: ItemId,
229 pub(crate) args: (u32, u32),
230 pub(crate) dispatch: Dispatch,
231}