nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
17 kB
501 lines
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2025 The Gleam contributors
3
4use std::collections::{HashMap, HashSet};
5
6use crate::ast::{Publicity, SrcSpan};
7use bimap::{BiMap, Overwritten};
8use ecow::EcoString;
9use petgraph::{
10 Directed, Direction,
11 stable_graph::{NodeIndex, StableGraph},
12};
13
14#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
15pub enum ReferenceKind {
16 Qualified,
17 Unqualified,
18 Import,
19 Definition,
20 Alias,
21}
22
23#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
24pub struct Reference {
25 pub location: SrcSpan,
26 pub kind: ReferenceKind,
27}
28
29pub type ReferenceMap = HashMap<(EcoString, EcoString), Vec<Reference>>;
30
31#[derive(Debug, Clone)]
32pub struct EntityInformation {
33 pub origin: SrcSpan,
34 pub kind: EntityKind,
35}
36
37/// Information about an "Entity". This determines how we warn about an entity
38/// being unused.
39#[derive(Debug, Clone, Eq, PartialEq)]
40pub enum EntityKind {
41 Function,
42 Constant,
43 Constructor,
44 Type,
45 ImportedModule { module_name: EcoString },
46 ModuleAlias { module: EcoString },
47 ImportedConstructor { module: EcoString },
48 ImportedType { module: EcoString },
49 ImportedValue { module: EcoString },
50}
51
52/// Like `ast::Layer`, this type differentiates between different scopes. For example,
53/// there can be a `wibble` value, a `wibble` module and a `wibble` type in the same
54/// scope all at once!
55///
56#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
57enum EntityLayer {
58 /// An entity which exists in the type layer: a custom type, type variable
59 /// or type alias.
60 Type,
61 /// An entity which exists in the value layer: a constant, function or
62 /// custom type variant constructor.
63 Value,
64 /// An entity which has been shadowed. This allows us to keep track of unused
65 /// imports even if they have been shadowed by another value in the current
66 /// module.
67 /// This extra variant is needed because we used `Entity` as a key in a hashmap,
68 /// and so a duplicate key would not be able to exist.
69 /// We also would not want to get this shadowed entity when performing a lookup
70 /// of a named entity; we only want it to register it as an entity in the
71 /// `unused` function.
72 Shadowed,
73 /// The name of an imported module. Modules are separate to values!
74 Module,
75}
76
77#[derive(Debug, Clone, PartialEq, Eq, Hash)]
78pub struct Entity {
79 pub name: EcoString,
80 layer: EntityLayer,
81}
82
83#[derive(Debug, Default)]
84pub struct ReferenceTracker {
85 /// A call-graph which tracks which values are referenced by which other value,
86 /// used for dead code detection.
87 graph: StableGraph<(), (), Directed>,
88 entities: BiMap<Entity, NodeIndex>,
89 current_node: NodeIndex,
90 public_entities: HashSet<Entity>,
91 entity_information: HashMap<Entity, EntityInformation>,
92
93 /// The locations of the references to each value in this module, used for
94 /// renaming and go-to reference.
95 pub value_references: ReferenceMap,
96 /// The locations of the references to each type in this module, used for
97 /// renaming and go-to reference.
98 pub type_references: ReferenceMap,
99
100 /// This map is used to access the nodes of modules that were not
101 /// aliased, given their name.
102 /// We need this to keep track of references made to imports by unqualified
103 /// values/types: when an unqualified item is used we want to add an edge
104 /// pointing to the import it comes from, so that if the item is used the
105 /// import won't be marked as unused:
106 ///
107 /// ```gleam
108 /// import wibble/wobble.{used}
109 ///
110 /// pub fn main() {
111 /// used
112 /// }
113 /// ```
114 ///
115 /// And each imported entity carries around the _name of the module_ and not
116 /// just the alias (here it would be `wibble/wobble` and not just `wobble`).
117 ///
118 module_name_to_node: HashMap<EcoString, NodeIndex>,
119}
120
121impl ReferenceTracker {
122 pub fn new() -> Self {
123 Self::default()
124 }
125
126 fn get_or_create_node(&mut self, name: EcoString, layer: EntityLayer) -> NodeIndex {
127 let entity = Entity { name, layer };
128
129 match self.entities.get_by_left(&entity) {
130 Some(index) => *index,
131 None => {
132 let index = self.graph.add_node(());
133 _ = self.entities.insert(entity, index);
134 index
135 }
136 }
137 }
138
139 fn create_node(&mut self, name: EcoString, layer: EntityLayer) -> NodeIndex {
140 let entity = Entity { name, layer };
141 let index = self.graph.add_node(());
142
143 self.create_node_and_maybe_shadow(entity, index);
144
145 index
146 }
147
148 fn create_node_and_maybe_shadow(&mut self, entity: Entity, index: NodeIndex) {
149 match self.entities.insert(entity, index) {
150 Overwritten::Neither => {}
151 Overwritten::Left(mut entity, index)
152 | Overwritten::Right(mut entity, index)
153 | Overwritten::Pair(mut entity, index)
154 | Overwritten::Both((mut entity, index), _) => {
155 // If an entity with the same name as this already exists,
156 // we still need to keep track of its usage! Thought it cannot
157 // be referenced anymore, it still might have been used before this
158 // point, or need to be marked as unused.
159 // To do this, we keep track of a "Shadowed" entity in `entity_information`.
160 if let Some(information) = self.entity_information.get(&entity) {
161 entity.layer = EntityLayer::Shadowed;
162 _ = self
163 .entity_information
164 .insert(entity.clone(), information.clone());
165 _ = self.entities.insert(entity, index);
166 }
167 }
168 }
169 }
170
171 /// This function exists because of a specific edge-case where constants
172 /// can shadow imported values. For example:
173 /// ```gleam
174 /// import math.{pi}
175 ///
176 /// pub const pi = pi
177 /// ```
178 /// Here, the new `pi` constant shadows the imported `pi` value, but it still
179 /// references it, so it should not be marked as unused.
180 /// In order for this to work, we must first set the `current_function` field
181 /// so that the `pi` value is referenced by the public `pi` constant.
182 /// However, we can't insert the `pi` constant into the name scope yet, since
183 /// then it would count as referencing itself. We first need to set `current_function`,
184 /// then once we have analysed the right-hand-side of the constant, we can
185 /// register it in the scope using `register_constant`.
186 ///
187 pub fn begin_constant(&mut self) {
188 self.current_node = self.graph.add_node(());
189 }
190
191 pub fn register_constant(&mut self, name: EcoString, location: SrcSpan, publicity: Publicity) {
192 let entity = Entity {
193 name,
194 layer: EntityLayer::Value,
195 };
196 self.create_node_and_maybe_shadow(entity.clone(), self.current_node);
197 match publicity {
198 Publicity::Public | Publicity::Internal { .. } => {
199 let _ = self.public_entities.insert(entity.clone());
200 }
201 Publicity::Private => {}
202 }
203
204 _ = self.entity_information.insert(
205 entity,
206 EntityInformation {
207 kind: EntityKind::Constant,
208 origin: location,
209 },
210 );
211 }
212
213 pub fn register_value(
214 &mut self,
215 name: EcoString,
216 kind: EntityKind,
217 location: SrcSpan,
218 publicity: Publicity,
219 ) {
220 self.current_node = self.create_node(name.clone(), EntityLayer::Value);
221 self.register_module_reference_from_imported_entity(&kind);
222
223 let entity = Entity {
224 name,
225 layer: EntityLayer::Value,
226 };
227 match publicity {
228 Publicity::Public | Publicity::Internal { .. } => {
229 let _ = self.public_entities.insert(entity.clone());
230 }
231 Publicity::Private => {}
232 }
233
234 _ = self.entity_information.insert(
235 entity,
236 EntityInformation {
237 kind,
238 origin: location,
239 },
240 );
241 }
242
243 pub fn set_current_node(&mut self, name: EcoString) {
244 self.current_node = self.get_or_create_node(name, EntityLayer::Value);
245 }
246
247 pub fn register_type(
248 &mut self,
249 name: EcoString,
250 kind: EntityKind,
251 location: SrcSpan,
252 publicity: Publicity,
253 ) {
254 self.current_node = self.create_node(name.clone(), EntityLayer::Type);
255 self.register_module_reference_from_imported_entity(&kind);
256
257 let entity = Entity {
258 name,
259 layer: EntityLayer::Type,
260 };
261 match publicity {
262 Publicity::Public | Publicity::Internal { .. } => {
263 let _ = self.public_entities.insert(entity.clone());
264 }
265 Publicity::Private => {}
266 }
267
268 _ = self.entity_information.insert(
269 entity,
270 EntityInformation {
271 kind,
272 origin: location,
273 },
274 );
275 }
276
277 pub fn register_aliased_module(
278 &mut self,
279 used_name: EcoString,
280 module_name: EcoString,
281 alias_location: SrcSpan,
282 import_location: SrcSpan,
283 ) {
284 // We first record a node for the module being aliased. We use its entire
285 // name to identify it in this case and keep track of the node it's
286 // associated with.
287 self.register_module(module_name.clone(), module_name.clone(), import_location);
288
289 // Then we create a node for the alias, as the alias itself might be
290 // unused!
291 self.current_node = self.create_node(used_name.clone(), EntityLayer::Module);
292 // Also we want to register the fact that if this alias is used then the
293 // import is used: so we add a reference from the alias to the import
294 // we've just added.
295 self.register_module_reference(module_name.clone());
296
297 // Finally we can add information for this alias:
298 let entity = Entity {
299 name: used_name,
300 layer: EntityLayer::Module,
301 };
302 _ = self.entity_information.insert(
303 entity,
304 EntityInformation {
305 kind: EntityKind::ModuleAlias {
306 module: module_name,
307 },
308 origin: alias_location,
309 },
310 );
311 }
312
313 pub fn register_module(
314 &mut self,
315 used_name: EcoString,
316 module_name: EcoString,
317 location: SrcSpan,
318 ) {
319 self.current_node = self.create_node(used_name.clone(), EntityLayer::Module);
320 let _ = self
321 .module_name_to_node
322 .insert(module_name.clone(), self.current_node);
323
324 let entity = Entity {
325 name: used_name,
326 layer: EntityLayer::Module,
327 };
328
329 _ = self.entity_information.insert(
330 entity,
331 EntityInformation {
332 kind: EntityKind::ImportedModule { module_name },
333 origin: location,
334 },
335 );
336 }
337
338 fn register_module_reference_from_imported_entity(&mut self, entity_kind: &EntityKind) {
339 match entity_kind {
340 EntityKind::Function
341 | EntityKind::Constant
342 | EntityKind::Constructor
343 | EntityKind::Type
344 | EntityKind::ImportedModule { .. }
345 | EntityKind::ModuleAlias { .. } => (),
346
347 EntityKind::ImportedConstructor { module }
348 | EntityKind::ImportedType { module }
349 | EntityKind::ImportedValue { module } => {
350 self.register_module_reference(module.clone())
351 }
352 }
353 }
354
355 pub fn register_value_reference(
356 &mut self,
357 module: EcoString,
358 name: EcoString,
359 referenced_name: &EcoString,
360 location: SrcSpan,
361 kind: ReferenceKind,
362 ) {
363 match kind {
364 ReferenceKind::Qualified | ReferenceKind::Import | ReferenceKind::Definition => {}
365 ReferenceKind::Alias | ReferenceKind::Unqualified => {
366 let target = self.get_or_create_node(referenced_name.clone(), EntityLayer::Value);
367 _ = self.graph.add_edge(self.current_node, target, ());
368 }
369 }
370
371 self.value_references
372 .entry((module, name))
373 .or_default()
374 .push(Reference { location, kind });
375 }
376
377 pub fn register_type_reference(
378 &mut self,
379 module: EcoString,
380 name: EcoString,
381 referenced_name: &EcoString,
382 location: SrcSpan,
383 kind: ReferenceKind,
384 ) {
385 match kind {
386 ReferenceKind::Qualified | ReferenceKind::Import | ReferenceKind::Definition => {}
387 ReferenceKind::Alias | ReferenceKind::Unqualified => {
388 self.register_type_reference_in_call_graph(referenced_name.clone())
389 }
390 }
391
392 self.type_references
393 .entry((module, name))
394 .or_default()
395 .push(Reference { location, kind });
396 }
397
398 /// Like `register_type_reference`, but doesn't modify `self.type_references`.
399 /// This is used when we define a constructor for a custom type. The constructor
400 /// doesn't actually "reference" its type, but if the constructor is used, the
401 /// type should also be considered used. The best way to represent this relationship
402 /// is to make a connection between them in the call graph.
403 ///
404 pub fn register_type_reference_in_call_graph(&mut self, name: EcoString) {
405 let target = self.get_or_create_node(name, EntityLayer::Type);
406 _ = self.graph.add_edge(self.current_node, target, ());
407 }
408
409 pub fn register_module_reference(&mut self, name: EcoString) {
410 let target = match self.module_name_to_node.get(&name) {
411 Some(target) => *target,
412 None => self.get_or_create_node(name, EntityLayer::Module),
413 };
414 _ = self.graph.add_edge(self.current_node, target, ());
415 }
416
417 pub fn unused(&self) -> HashMap<Entity, EntityInformation> {
418 let mut unused_values = HashMap::with_capacity(self.entities.len());
419
420 for (entity, information) in self.entity_information.iter() {
421 _ = unused_values.insert(entity.clone(), information.clone());
422 }
423 for entity in self.public_entities.iter() {
424 if let Some(index) = self.entities.get_by_left(entity) {
425 self.mark_entity_as_used(&mut unused_values, entity, *index);
426 }
427 }
428
429 for (entity, _) in self.entities.iter() {
430 let Some(index) = self.entities.get_by_left(entity) else {
431 continue;
432 };
433
434 if self.public_entities.contains(entity) {
435 self.mark_entity_as_used(&mut unused_values, entity, *index);
436 } else {
437 // If the entity is not public, we still want to mark referenced
438 // imports as used.
439 self.mark_referenced_imports_as_used(&mut unused_values, entity, *index);
440 }
441 }
442
443 unused_values
444 }
445
446 fn mark_entity_as_used(
447 &self,
448 unused: &mut HashMap<Entity, EntityInformation>,
449 entity: &Entity,
450 index: NodeIndex,
451 ) {
452 if unused.remove(entity).is_some() {
453 for node in self.graph.neighbors_directed(index, Direction::Outgoing) {
454 if let Some(entity) = self.entities.get_by_right(&node) {
455 self.mark_entity_as_used(unused, entity, node);
456 }
457 }
458 }
459 }
460
461 fn mark_referenced_imports_as_used(
462 &self,
463 unused: &mut HashMap<Entity, EntityInformation>,
464 entity: &Entity,
465 index: NodeIndex,
466 ) {
467 // If the entity is a module there's no way it can reference other
468 // modules so we just ignore it.
469 // This also means that module aliases do not count as using a module!
470 if entity.layer == EntityLayer::Module {
471 return;
472 }
473
474 for node in self.graph.neighbors_directed(index, Direction::Outgoing) {
475 // We only want to mark referenced modules as used, so if the node
476 // is not a module we just skip it.
477 let Some(
478 module @ Entity {
479 layer: EntityLayer::Module,
480 ..
481 },
482 ) = self.entities.get_by_right(&node)
483 else {
484 continue;
485 };
486
487 // If the value appears in the module import list, it doesn't count
488 // as using it!
489 let is_imported_type = self
490 .type_references
491 .contains_key(&(module.name.clone(), entity.name.clone()));
492 let is_imported_value = self
493 .value_references
494 .contains_key(&(module.name.clone(), entity.name.clone()));
495 let appears_in_module_import_list = is_imported_type || is_imported_value;
496 if !(appears_in_module_import_list) {
497 self.mark_entity_as_used(unused, module, node);
498 }
499 }
500 }
501}