Skip to main content

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}