nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
25 kB
715 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/// Describes one of a number of situations where references can be generated.
15/// See each variant for an explanation.
16#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
17pub enum ReferenceKind {
18 /// A type or value which is referenced using the qualified syntax, along with
19 /// some information about the qualifier which is used for tracking module name
20 /// references. For example:
21 /// ```gleam
22 /// import gleam/option.{Some}
23 ///
24 /// pub fn main() -> option.Option(Int) {
25 /// // ^^^^^^ `module_location` covers this
26 /// Some(1)
27 /// }
28 /// ```
29 ///
30 /// Here, `module_alias` is `option`, as that's what's being used as a
31 /// qualifier.
32 ///
33 ///
34 /// ```gleam
35 /// import gleam/int as integer
36 ///
37 /// pub fn main() {
38 /// integer.add(1, 2)
39 /// //^^^^^^^ `module_location` covers this
40 /// }
41 /// ```
42 ///
43 /// In this case, `module_alias` is `integer`, due to the aliased import.
44 ///
45 Qualified {
46 module_alias: EcoString,
47 module_location: SrcSpan,
48 },
49 /// A type or value is being referenced using unqualified syntax. This may
50 /// be due to being imported unqualified, or because it's from the same
51 /// module. For example:
52 ///
53 /// ```gleam
54 /// import gleam/option.{None}
55 ///
56 /// pub fn main() {
57 /// none()
58 /// //^^^^ Unqualified
59 /// }
60 ///
61 /// fn none() {
62 /// None
63 /// //^^^^ Unqualified
64 /// }
65 /// ```
66 ///
67 Unqualified,
68 /// A value or type is being referenced inside an unqualified import. For
69 /// example:
70 /// ```gleam
71 /// import gleam/option.{None}
72 /// // ^^^^ Import
73 /// import gleam/dynamic/decode.{type Dynamic}
74 /// // ^^^^^^^ Import
75 /// ```
76 Import,
77 /// The original definition location of a type or value. This also counts as
78 /// a reference for renaming and "find references" purposes. For example:
79 ///
80 /// ```gleam
81 /// pub type Wibble {
82 /// // ^^^^^^ Definition
83 /// Wibble(Int)
84 /// //^^^^^^ Definition
85 /// }
86 ///
87 /// pub fn extract(w: Wibble) {
88 /// // ^^^^^^^ Definition
89 /// let Wibble(x) = w
90 /// x
91 /// }
92 /// ```
93 Definition,
94 /// A value or type is being referenced using unqualified syntax, with a
95 /// name other than its original definition. This can be due to importing it
96 /// using an alias, or due to referencing it through a type alias. For example:
97 ///
98 /// ```gleam
99 /// import gleam/option.{None as Nothing, type Option as Maybe}
100 ///
101 /// pub fn nothing() -> Maybe(_) {
102 /// // ^^^^^ Alias
103 /// Nothing
104 /// //^^^^^^^ Alias
105 /// }
106 /// ```
107 ///
108 Alias,
109}
110
111#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
112pub struct Reference {
113 pub location: SrcSpan,
114 pub kind: ReferenceKind,
115}
116
117/// A reference to a module name. This is similar to a `Reference`, which covers
118/// types and values, but it is separate because we care about slightly different
119/// pieces of information when, for example, renaming modules vs. renaming types
120/// or values.
121///
122#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
123pub enum ModuleNameReference {
124 /// The location of a module name in a `ModuleSelect`, when the module name
125 /// is not aliased. For example:
126 /// ```gleam
127 /// import gleam/option
128 ///
129 /// pub fn main() -> option.Option(_) {
130 /// // ^^^^^^ ModuleSelect
131 /// option.None
132 /// //^^^^^^ ModuleSelect
133 /// }
134 /// ```
135 ///
136 ModuleSelect(SrcSpan),
137 /// The location of a module name in a `ModuleSelect`, when the module name
138 /// *is* aliased. For example:
139 /// ```gleam
140 /// import gleam/option as maybe
141 ///
142 /// pub fn main() -> maybe.Option(_) {
143 /// // ^^^^^ AliasedModuleSelect
144 /// maybe.None
145 /// //^^^^^ AliasedModuleSelect
146 /// }
147 /// ```
148 ///
149 AliasedModuleSelect(SrcSpan),
150 /// The location of a module name in an `import` statement, when the module
151 /// name is not aliased. For example:
152 /// ```gleam
153 /// import gleam/option.{None, Some}
154 /// // ^^^^^^^^^^^^ Import ^ `import_end`
155 /// ```
156 ///
157 Import {
158 module_location: SrcSpan,
159 import_end: u32,
160 },
161 /// The location of a module name in an `import` statement, when the module
162 /// name *is* aliased. Also stores the location of the alias (including the
163 /// `as` keyword), and what the alias is. For example:
164 /// ```gleam
165 /// import gleam/option.{None, Some} as maybe
166 /// // ^^^^^^^^^^^^ `module_location`
167 /// // ^^^^^^^^ `alias_location`
168 /// ```
169 /// In this example, `alias` would be `maybe`.
170 ///
171 AliasedImport {
172 module_location: SrcSpan,
173 alias_location: SrcSpan,
174 alias: EcoString,
175 },
176}
177
178pub type ReferenceMap = HashMap<(EcoString, EcoString), Vec<Reference>>;
179
180#[derive(Debug, Clone)]
181pub struct EntityInformation {
182 pub origin: SrcSpan,
183 pub kind: EntityKind,
184}
185
186/// Information about an "Entity". This determines how we warn about an entity
187/// being unused.
188#[derive(Debug, Clone, Eq, PartialEq)]
189pub enum EntityKind {
190 Function,
191 Constant,
192 Constructor,
193 Type,
194 ImportedModule { module_name: EcoString },
195 ModuleAlias { module: EcoString },
196 ImportedConstructor { module: EcoString },
197 ImportedType { module: EcoString },
198 ImportedValue { module: EcoString },
199}
200
201/// Like `ast::Layer`, this type differentiates between different scopes. For example,
202/// there can be a `wibble` value, a `wibble` module and a `wibble` type in the same
203/// scope all at once!
204///
205#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
206enum EntityLayer {
207 /// An entity which exists in the type layer: a custom type, type variable
208 /// or type alias.
209 Type,
210 /// An entity which exists in the value layer: a constant, function or
211 /// custom type variant constructor.
212 Value,
213 /// An entity which has been shadowed. This allows us to keep track of unused
214 /// imports even if they have been shadowed by another value in the current
215 /// module.
216 /// This extra variant is needed because we used `Entity` as a key in a hashmap,
217 /// and so a duplicate key would not be able to exist.
218 /// We also would not want to get this shadowed entity when performing a lookup
219 /// of a named entity; we only want it to register it as an entity in the
220 /// `unused` function.
221 Shadowed,
222 /// The name of an imported module. Modules are separate to values!
223 Module,
224}
225
226#[derive(Debug, Clone, PartialEq, Eq, Hash)]
227pub struct Entity {
228 pub name: EcoString,
229 layer: EntityLayer,
230}
231
232#[derive(Debug, Default)]
233pub struct ReferenceTracker {
234 /// A call-graph which tracks which values are referenced by which other value,
235 /// used for dead code detection.
236 graph: StableGraph<(), (), Directed>,
237 entities: BiMap<Entity, NodeIndex>,
238 current_node: NodeIndex,
239 public_entities: HashSet<Entity>,
240 entity_information: HashMap<Entity, EntityInformation>,
241
242 /// The locations of the references to each value in this module, used for
243 /// renaming and go-to reference.
244 pub value_references: ReferenceMap,
245 /// The locations of the references to each type in this module, used for
246 /// renaming and go-to reference.
247 pub type_references: ReferenceMap,
248 /// The locations of the references to each imported module, used for
249 /// renaming and go-to reference.
250 pub module_references: HashMap<EcoString, Vec<ModuleNameReference>>,
251
252 /// This map is used to access the nodes of modules that were not
253 /// aliased, given their name.
254 /// We need this to keep track of references made to imports by unqualified
255 /// values/types: when an unqualified item is used we want to add an edge
256 /// pointing to the import it comes from, so that if the item is used the
257 /// import won't be marked as unused:
258 ///
259 /// ```gleam
260 /// import wibble/wobble.{used}
261 ///
262 /// pub fn main() {
263 /// used
264 /// }
265 /// ```
266 ///
267 /// And each imported entity carries around the _name of the module_ and not
268 /// just the alias (here it would be `wibble/wobble` and not just `wobble`).
269 ///
270 module_name_to_node: HashMap<EcoString, NodeIndex>,
271}
272
273impl ReferenceTracker {
274 pub fn new() -> Self {
275 Self::default()
276 }
277
278 fn get_or_create_node(&mut self, name: EcoString, layer: EntityLayer) -> NodeIndex {
279 let entity = Entity { name, layer };
280
281 match self.entities.get_by_left(&entity) {
282 Some(index) => *index,
283 None => {
284 let index = self.graph.add_node(());
285 _ = self.entities.insert(entity, index);
286 index
287 }
288 }
289 }
290
291 fn create_node(&mut self, name: EcoString, layer: EntityLayer) -> NodeIndex {
292 let entity = Entity { name, layer };
293 let index = self.graph.add_node(());
294
295 self.create_node_and_maybe_shadow(entity, index);
296
297 index
298 }
299
300 fn create_node_and_maybe_shadow(&mut self, entity: Entity, index: NodeIndex) {
301 match self.entities.insert(entity, index) {
302 Overwritten::Neither => {}
303 Overwritten::Left(mut entity, index)
304 | Overwritten::Right(mut entity, index)
305 | Overwritten::Pair(mut entity, index)
306 | Overwritten::Both((mut entity, index), _) => {
307 // If an entity with the same name as this already exists,
308 // we still need to keep track of its usage! Thought it cannot
309 // be referenced anymore, it still might have been used before this
310 // point, or need to be marked as unused.
311 // To do this, we keep track of a "Shadowed" entity in `entity_information`.
312 if let Some(information) = self.entity_information.get(&entity) {
313 entity.layer = EntityLayer::Shadowed;
314 _ = self
315 .entity_information
316 .insert(entity.clone(), information.clone());
317 _ = self.entities.insert(entity, index);
318 }
319 }
320 }
321 }
322
323 /// This function exists because of a specific edge-case where constants
324 /// can shadow imported values. For example:
325 /// ```gleam
326 /// import math.{pi}
327 ///
328 /// pub const pi = pi
329 /// ```
330 /// Here, the new `pi` constant shadows the imported `pi` value, but it still
331 /// references it, so it should not be marked as unused.
332 /// In order for this to work, we must first set the `current_function` field
333 /// so that the `pi` value is referenced by the public `pi` constant.
334 /// However, we can't insert the `pi` constant into the name scope yet, since
335 /// then it would count as referencing itself. We first need to set `current_function`,
336 /// then once we have analysed the right-hand-side of the constant, we can
337 /// register it in the scope using `register_constant`.
338 ///
339 pub fn begin_constant(&mut self) {
340 self.current_node = self.graph.add_node(());
341 }
342
343 pub fn register_constant(&mut self, name: EcoString, location: SrcSpan, publicity: Publicity) {
344 let entity = Entity {
345 name,
346 layer: EntityLayer::Value,
347 };
348 self.create_node_and_maybe_shadow(entity.clone(), self.current_node);
349 match publicity {
350 Publicity::Public | Publicity::Internal { .. } => {
351 let _ = self.public_entities.insert(entity.clone());
352 }
353 Publicity::Private => {}
354 }
355
356 _ = self.entity_information.insert(
357 entity,
358 EntityInformation {
359 kind: EntityKind::Constant,
360 origin: location,
361 },
362 );
363 }
364
365 pub fn register_value(
366 &mut self,
367 name: EcoString,
368 kind: EntityKind,
369 location: SrcSpan,
370 publicity: Publicity,
371 ) {
372 self.current_node = self.create_node(name.clone(), EntityLayer::Value);
373 self.register_module_reference_from_imported_entity(&kind);
374
375 let entity = Entity {
376 name,
377 layer: EntityLayer::Value,
378 };
379 match publicity {
380 Publicity::Public | Publicity::Internal { .. } => {
381 let _ = self.public_entities.insert(entity.clone());
382 }
383 Publicity::Private => {}
384 }
385
386 _ = self.entity_information.insert(
387 entity,
388 EntityInformation {
389 kind,
390 origin: location,
391 },
392 );
393 }
394
395 pub fn set_current_node(&mut self, name: EcoString) {
396 self.current_node = self.get_or_create_node(name, EntityLayer::Value);
397 }
398
399 pub fn register_type(
400 &mut self,
401 name: EcoString,
402 kind: EntityKind,
403 location: SrcSpan,
404 publicity: Publicity,
405 ) {
406 self.current_node = self.create_node(name.clone(), EntityLayer::Type);
407 self.register_module_reference_from_imported_entity(&kind);
408
409 let entity = Entity {
410 name,
411 layer: EntityLayer::Type,
412 };
413 match publicity {
414 Publicity::Public | Publicity::Internal { .. } => {
415 let _ = self.public_entities.insert(entity.clone());
416 }
417 Publicity::Private => {}
418 }
419
420 _ = self.entity_information.insert(
421 entity,
422 EntityInformation {
423 kind,
424 origin: location,
425 },
426 );
427 }
428
429 pub fn register_aliased_module(
430 &mut self,
431 used_name: EcoString,
432 module_name: EcoString,
433 alias_location: SrcSpan,
434 import_location: SrcSpan,
435 module_location: SrcSpan,
436 ) {
437 // We first record a node for the module being aliased.
438 self.register_module(
439 used_name.clone(),
440 module_name.clone(),
441 import_location,
442 module_location,
443 Some(alias_location),
444 );
445
446 // Then we create a node for the alias, as the alias itself might be
447 // unused!
448 self.current_node = self.create_node(used_name.clone(), EntityLayer::Module);
449 // Also we want to register the fact that if this alias is used then the
450 // import is used: so we add a reference from the alias to the import
451 // we've just added.
452 self.register_module_reference(module_name.clone());
453
454 // Finally we can add information for this alias:
455 let entity = Entity {
456 name: used_name,
457 layer: EntityLayer::Module,
458 };
459 _ = self.entity_information.insert(
460 entity,
461 EntityInformation {
462 kind: EntityKind::ModuleAlias {
463 module: module_name,
464 },
465 origin: alias_location,
466 },
467 );
468 }
469
470 pub fn register_module(
471 &mut self,
472 used_name: EcoString,
473 module_name: EcoString,
474 location: SrcSpan,
475 module_location: SrcSpan,
476 alias_location: Option<SrcSpan>,
477 ) {
478 self.current_node = self.create_node(used_name.clone(), EntityLayer::Module);
479 let _ = self
480 .module_name_to_node
481 .insert(module_name.clone(), self.current_node);
482
483 let reference = if let Some(alias_location) = alias_location {
484 ModuleNameReference::AliasedImport {
485 module_location,
486 alias_location,
487 alias: used_name.clone(),
488 }
489 } else {
490 ModuleNameReference::Import {
491 module_location,
492 import_end: location.end,
493 }
494 };
495
496 self.register_module_name_reference(module_name.clone(), reference);
497
498 let entity = Entity {
499 name: used_name,
500 layer: EntityLayer::Module,
501 };
502
503 _ = self.entity_information.insert(
504 entity,
505 EntityInformation {
506 kind: EntityKind::ImportedModule { module_name },
507 origin: location,
508 },
509 );
510 }
511
512 fn register_module_reference_from_imported_entity(&mut self, entity_kind: &EntityKind) {
513 match entity_kind {
514 EntityKind::Function
515 | EntityKind::Constant
516 | EntityKind::Constructor
517 | EntityKind::Type
518 | EntityKind::ImportedModule { .. }
519 | EntityKind::ModuleAlias { .. } => (),
520
521 EntityKind::ImportedConstructor { module }
522 | EntityKind::ImportedType { module }
523 | EntityKind::ImportedValue { module } => {
524 self.register_module_reference(module.clone())
525 }
526 }
527 }
528
529 pub fn register_value_reference(
530 &mut self,
531 module: EcoString,
532 name: EcoString,
533 referenced_name: &EcoString,
534 location: SrcSpan,
535 kind: ReferenceKind,
536 ) {
537 match &kind {
538 ReferenceKind::Qualified {
539 module_alias,
540 module_location,
541 } => {
542 let last_module_segment = module.split('/').next_back().unwrap_or(&module);
543 let reference = if last_module_segment == module_alias {
544 ModuleNameReference::ModuleSelect(*module_location)
545 } else {
546 ModuleNameReference::AliasedModuleSelect(*module_location)
547 };
548 self.register_module_name_reference(module.clone(), reference);
549 }
550 ReferenceKind::Import | ReferenceKind::Definition => {}
551 ReferenceKind::Alias | ReferenceKind::Unqualified => {
552 let target = self.get_or_create_node(referenced_name.clone(), EntityLayer::Value);
553 _ = self.graph.add_edge(self.current_node, target, ());
554 }
555 }
556
557 self.value_references
558 .entry((module, name))
559 .or_default()
560 .push(Reference { location, kind });
561 }
562
563 pub fn register_type_reference(
564 &mut self,
565 module: EcoString,
566 name: EcoString,
567 referenced_name: &EcoString,
568 location: SrcSpan,
569 kind: ReferenceKind,
570 ) {
571 match &kind {
572 ReferenceKind::Qualified {
573 module_alias,
574 module_location,
575 } => {
576 let last_module_segment = module.split('/').next_back().unwrap_or(&module);
577 let reference = if last_module_segment == module_alias {
578 ModuleNameReference::ModuleSelect(*module_location)
579 } else {
580 ModuleNameReference::AliasedModuleSelect(*module_location)
581 };
582 self.register_module_name_reference(module.clone(), reference);
583 }
584 ReferenceKind::Import | ReferenceKind::Definition => {}
585 ReferenceKind::Alias | ReferenceKind::Unqualified => {
586 self.register_type_reference_in_call_graph(referenced_name.clone())
587 }
588 }
589
590 self.type_references
591 .entry((module, name))
592 .or_default()
593 .push(Reference { location, kind });
594 }
595
596 /// Register a reference to a module in the code. This is separate to
597 /// `register_module_reference`, as references to modules can be created
598 /// implicitly, for example when using unqualified imports. This only register
599 /// explicit references in the source code, when the module name or local
600 /// alias is written.
601 pub fn register_module_name_reference(
602 &mut self,
603 module: EcoString,
604 reference: ModuleNameReference,
605 ) {
606 self.module_references
607 .entry(module)
608 .or_default()
609 .push(reference);
610 }
611
612 /// Like `register_type_reference`, but doesn't modify `self.type_references`.
613 /// This is used when we define a constructor for a custom type. The constructor
614 /// doesn't actually "reference" its type, but if the constructor is used, the
615 /// type should also be considered used. The best way to represent this relationship
616 /// is to make a connection between them in the call graph.
617 ///
618 pub fn register_type_reference_in_call_graph(&mut self, name: EcoString) {
619 let target = self.get_or_create_node(name, EntityLayer::Type);
620 _ = self.graph.add_edge(self.current_node, target, ());
621 }
622
623 pub fn register_module_reference(&mut self, name: EcoString) {
624 let target = match self.module_name_to_node.get(&name) {
625 Some(target) => *target,
626 None => self.get_or_create_node(name, EntityLayer::Module),
627 };
628 _ = self.graph.add_edge(self.current_node, target, ());
629 }
630
631 pub fn unused(&self) -> HashMap<Entity, EntityInformation> {
632 let mut unused_values = HashMap::with_capacity(self.entities.len());
633
634 for (entity, information) in self.entity_information.iter() {
635 _ = unused_values.insert(entity.clone(), information.clone());
636 }
637 for entity in self.public_entities.iter() {
638 if let Some(index) = self.entities.get_by_left(entity) {
639 self.mark_entity_as_used(&mut unused_values, entity, *index);
640 }
641 }
642
643 for (entity, _) in self.entities.iter() {
644 let Some(index) = self.entities.get_by_left(entity) else {
645 continue;
646 };
647
648 if self.public_entities.contains(entity) {
649 self.mark_entity_as_used(&mut unused_values, entity, *index);
650 } else {
651 // If the entity is not public, we still want to mark referenced
652 // imports as used.
653 self.mark_referenced_imports_as_used(&mut unused_values, entity, *index);
654 }
655 }
656
657 unused_values
658 }
659
660 fn mark_entity_as_used(
661 &self,
662 unused: &mut HashMap<Entity, EntityInformation>,
663 entity: &Entity,
664 index: NodeIndex,
665 ) {
666 if unused.remove(entity).is_some() {
667 for node in self.graph.neighbors_directed(index, Direction::Outgoing) {
668 if let Some(entity) = self.entities.get_by_right(&node) {
669 self.mark_entity_as_used(unused, entity, node);
670 }
671 }
672 }
673 }
674
675 fn mark_referenced_imports_as_used(
676 &self,
677 unused: &mut HashMap<Entity, EntityInformation>,
678 entity: &Entity,
679 index: NodeIndex,
680 ) {
681 // If the entity is a module there's no way it can reference other
682 // modules so we just ignore it.
683 // This also means that module aliases do not count as using a module!
684 if entity.layer == EntityLayer::Module {
685 return;
686 }
687
688 for node in self.graph.neighbors_directed(index, Direction::Outgoing) {
689 // We only want to mark referenced modules as used, so if the node
690 // is not a module we just skip it.
691 let Some(
692 module @ Entity {
693 layer: EntityLayer::Module,
694 ..
695 },
696 ) = self.entities.get_by_right(&node)
697 else {
698 continue;
699 };
700
701 // If the value appears in the module import list, it doesn't count
702 // as using it!
703 let is_imported_type = self
704 .type_references
705 .contains_key(&(module.name.clone(), entity.name.clone()));
706 let is_imported_value = self
707 .value_references
708 .contains_key(&(module.name.clone(), entity.name.clone()));
709 let appears_in_module_import_list = is_imported_type || is_imported_value;
710 if !(appears_in_module_import_list) {
711 self.mark_entity_as_used(unused, module, node);
712 }
713 }
714 }
715}