nash-can 0.14.0

Canonicalize a nash source tree, resolving symbols, re-ordering definitions, and preparing a module for type inference.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
pub mod dups;
pub mod foreign;
pub mod local;

use std::collections::BTreeMap;

use bumpalo::Bump;
use nash_ast::{Associativity, CtorOpts, ModuleName, Precedence, Type as CanType};
use nash_region::{Located, Region};

use crate::Error;

/// A resolved name: either uniquely identified or ambiguous across modules.
#[derive(Clone, Debug)]
pub enum Info<'a, T> {
    Specific(ModuleName<'a>, T),
    Ambiguous(ModuleName<'a>, Vec<ModuleName<'a>>),
}

/// Unqualified name -> resolution.
pub type Exposed<'a, T> = BTreeMap<&'a str, Info<'a, T>>;

/// Module prefix -> name -> resolution (for `Module.name` lookups).
pub type Qualified<'a, T> = BTreeMap<&'a str, BTreeMap<&'a str, Info<'a, T>>>;

#[derive(Clone, Copy, Debug)]
pub struct TraitInfo<'a> {
    pub home: ModuleName<'a>,
    pub name: &'a str,
    pub parameters: &'a [&'a str],
    pub kinds: &'a [&'a nash_ast::Kind<'a>],
    pub supers: &'a [nash_ast::Pred<'a>],
    pub methods: &'a [MethodInfo<'a>],
}

#[derive(Clone, Copy, Debug)]
pub struct MethodInfo<'a> {
    pub name: &'a str,
    pub annotation: &'a nash_ast::Annotation<'a>,
    pub has_default: bool,
}

/// Resolution metadata retained for every impl, including private declarations.
#[derive(Clone, Copy, Debug)]
pub struct ImplInfo<'a> {
    pub variables: &'a [&'a str],
    pub home: ModuleName<'a>,
    pub region: Region,
    pub trait_: nash_ast::QualifiedName<'a>,
    pub context: &'a [nash_ast::Pred<'a>],
    pub heads: &'a [Located<nash_ast::Head<'a>>],
    pub methods: &'a [&'a str],
}

pub type ImplTable<'a> = BTreeMap<nash_ast::ImplKey<'a>, &'a ImplInfo<'a>>;

#[derive(Clone, Debug, Default)]
pub struct Tables<'a> {
    /// Field projection is limited to constructors visible in this module.
    pub fields: BTreeMap<nash_ast::QualifiedName<'a>, LabeledUnion<'a>>,
    /// Additional constructor visibility granted only by tests-block imports.
    pub test_fields: BTreeMap<nash_ast::QualifiedName<'a>, LabeledUnion<'a>>,
    pub kinds: crate::kinds::KindEnv<'a>,
    pub traits: BTreeMap<nash_ast::QualifiedName<'a>, &'a TraitInfo<'a>>,
    pub impls: ImplTable<'a>,
}

#[derive(Clone, Copy, Debug)]
pub struct LabeledUnion<'a> {
    pub parameters: &'a [&'a str],
    pub fields: &'a [nash_ast::FieldType<'a>],
}

pub fn visible_fields<'a>(
    bump: &'a Bump,
    env: &Env<'a>,
) -> BTreeMap<nash_ast::QualifiedName<'a>, LabeledUnion<'a>> {
    let mut fields = BTreeMap::new();
    for info in env
        .ctors
        .values()
        .chain(env.q_ctors.values().flat_map(|ctors| ctors.values()))
    {
        if let Info::Specific(
            _,
            Ctor::Union {
                home,
                type_name,
                union,
                ..
            },
        ) = info
            && let Some(labels) = union.labeled_fields()
        {
            fields
                .entry(nash_ast::QualifiedName {
                    home: *home,
                    name: type_name,
                })
                .or_insert_with(|| LabeledUnion {
                    parameters: union.parameters,
                    fields: bump.alloc_slice_fill_iter(labels),
                });
        }
    }
    fields
}

impl<'a> Tables<'a> {
    /// ImplKey orders the trait before its head slice. The empty slice is the
    /// first possible head key, so lookup visits only this trait's candidates.
    pub fn impls_for(
        &self,
        trait_: nash_ast::QualifiedName<'a>,
    ) -> impl Iterator<Item = (&nash_ast::ImplKey<'a>, &&'a ImplInfo<'a>)> {
        self.impls
            .range(nash_ast::ImplKey { trait_, heads: &[] }..)
            .take_while(move |(key, _)| key.trait_ == trait_)
    }

    pub fn has_structural_eq(&self) -> bool {
        self.traits.contains_key(&nash_ast::primitives::eq_trait())
    }

    pub fn has_reflexive_lift(&self) -> bool {
        self.traits
            .contains_key(&nash_ast::primitives::lift_trait())
    }
}

/// A value variable in scope.
#[derive(Clone, Debug)]
pub enum Var<'a> {
    Method {
        trait_: nash_ast::QualifiedName<'a>,
        annotation: &'a nash_ast::Annotation<'a>,
        local_region: Option<Region>,
    },
    TopLevel(Region),
    /// Imported from another module, like Elm's `Foreign home annotation`.
    /// The annotation comes from the defining module's (post-solve)
    /// interface.
    Foreign(ModuleName<'a>, &'a nash_ast::Annotation<'a>),
    /// Ambiguous import: same name imported from multiple modules.
    Foreigns(ModuleName<'a>, Vec<ModuleName<'a>>),
}

#[derive(Clone, Copy, Debug)]
pub struct QualifiedValue<'a> {
    pub annotation: &'a nash_ast::Annotation<'a>,
    pub trait_: Option<nash_ast::QualifiedName<'a>>,
}

/// A type in scope (alias or union).
#[derive(Clone, Copy, Debug)]
pub enum Type<'a> {
    Alias {
        arity: usize,
        home: ModuleName<'a>,
        parameters: &'a [&'a str],
        typ: &'a Located<CanType<'a>>,
    },
    Union {
        arity: usize,
        home: ModuleName<'a>,
    },
}

/// A data constructor in scope.
#[derive(Clone, Copy, Debug)]
pub enum Ctor<'a> {
    /// Union constructor (e.g., `Just` from `type Maybe a = Just a | Nothing`).
    Union {
        home: ModuleName<'a>,
        type_name: &'a str,
        type_vars: &'a [&'a str],
        union: &'a nash_ast::Union<'a>,
        index: u16,
        arity: u16,
        arguments: &'a [&'a Located<CanType<'a>>],
        options: CtorOpts,
        alternatives: u16,
    },
    /// Primitive.bool constructor (False or True from nash/base).
    /// Separated from `Union` so pattern/expression canonicalization can
    /// emit `CanPattern::Bool` / synthesize the annotation without string checks.
    Bool {
        home: ModuleName<'a>,
        union: &'a nash_ast::Union<'a>,
        index: u16,
    },
    /// Record alias ctor (e.g., `Point` from `type alias Point = { x : Int, y : Int }`).
    /// Elm creates these automatically for non-extensible record aliases.
    /// Like Elm's `Env.RecordCtor home vars tipe`, the complete curried
    /// function type is built up front.
    RecordCtor {
        home: ModuleName<'a>,
        alias_name: &'a str,
        type_vars: &'a [&'a str],
        typ: &'a Located<CanType<'a>>,
        fields: &'a [nash_ast::FieldType<'a>],
    },
}

/// Build the curried constructor type for a record alias, mirroring Elm's
/// `toRecordCtor`: `field1 -> field2 -> ... -> Alias args (Open record)`,
/// with fields in source order (`fieldsToList` sorts by index).
pub fn make_record_ctor<'a>(
    bump: &'a Bump,
    home: ModuleName<'a>,
    alias_name: &'a str,
    parameters: &'a [&'a str],
    record_type: &'a Located<CanType<'a>>,
    fields: &'a [nash_ast::FieldType<'a>],
) -> Ctor<'a> {
    let arguments =
        bump.alloc_slice_fill_iter(parameters.iter().map(|var| nash_ast::AliasArgument {
            name: var,
            typ: bump.alloc(Located::at(Region::zero(), CanType::Var(var))),
        }));
    let result: &'a Located<CanType<'a>> = bump.alloc(Located::at(
        Region::zero(),
        CanType::Alias {
            remaining: &[],
            reference: nash_ast::QualifiedName {
                home,
                name: alias_name,
            },
            arguments,
            target: nash_ast::AliasType::Open(record_type),
        },
    ));

    let mut fields_in_source_order: Vec<&nash_ast::FieldType<'a>> = fields.iter().collect();
    fields_in_source_order.sort_by_key(|f| f.index);

    let mut typ = result;
    for field in fields_in_source_order.into_iter().rev() {
        typ = bump.alloc(Located::at(
            Region::zero(),
            CanType::Lambda {
                from: field.typ,
                to: typ,
            },
        ));
    }

    Ctor::RecordCtor {
        home,
        alias_name,
        type_vars: parameters,
        typ,
        fields,
    }
}

/// A binary operator in scope. Mirrors Elm's
/// `Env.Binop op home name annotation associativity precedence`.
///
/// Like Elm, only IMPORTED operators are in scope: the defining module's
/// own `infix` declarations do not enter its env, so a module calls the
/// underlying function or method directly. Local function annotations
/// become available after solving; trait method schemes are checked earlier.
#[derive(Clone, Copy, Debug)]
pub struct Binop<'a> {
    pub symbol: &'a str,
    pub home: ModuleName<'a>,
    pub function: nash_ast::QualifiedName<'a>,
    pub annotation: &'a nash_ast::Annotation<'a>,
    pub associativity: Associativity,
    pub precedence: Precedence,
}

/// Module information for canonicalization, built from imports and top-level
/// definitions. Local expression bindings live in Scope and never mutate it.
#[derive(Clone)]
pub struct Env<'a> {
    pub kinds: crate::kinds::KindEnv<'a>,
    pub traits: Exposed<'a, &'a TraitInfo<'a>>,
    pub q_traits: Qualified<'a, &'a TraitInfo<'a>>,
    pub home: ModuleName<'a>,
    pub vars: BTreeMap<&'a str, Var<'a>>,
    pub types: Exposed<'a, Type<'a>>,
    pub ctors: Exposed<'a, Ctor<'a>>,
    pub binops: Exposed<'a, Binop<'a>>,
    /// Qualified values carry their scheme and, for methods, their owning trait.
    pub q_vars: Qualified<'a, QualifiedValue<'a>>,
    pub q_types: Qualified<'a, Type<'a>>,
    pub q_ctors: Qualified<'a, Ctor<'a>>,
}

/// Local bindings borrow module information and their parent scope. Scope exit,
/// including an early error return, cannot change a sibling or ancestor.
pub struct Scope<'scope, 'a> {
    pub module: &'scope Env<'a>,
    parent: Option<&'scope Scope<'scope, 'a>>,
    bindings: &'scope BTreeMap<&'a str, Region>,
}

impl<'scope, 'a> Scope<'scope, 'a> {
    pub fn new(
        module: &'scope Env<'a>,
        parent: Option<&'scope Scope<'scope, 'a>>,
        bindings: &'scope BTreeMap<&'a str, Region>,
    ) -> Result<Self, Vec<Error<'a>>> {
        let mut errors = Vec::new();
        for (&name, &region) in bindings {
            let original = parent.and_then(|scope| scope.local(name)).or_else(|| {
                match module.vars.get(name) {
                    Some(Var::TopLevel(original))
                    | Some(Var::Method {
                        local_region: Some(original),
                        ..
                    }) => Some(*original),
                    _ => None,
                }
            });
            if let Some(original) = original {
                errors.push(Error::Shadowing {
                    name,
                    original,
                    new: region,
                });
            }
        }
        if errors.is_empty() {
            Ok(Self {
                module,
                parent,
                bindings,
            })
        } else {
            Err(errors)
        }
    }

    pub fn add_locals<'child>(
        &'child self,
        bindings: &'child BTreeMap<&'a str, Region>,
    ) -> Result<Scope<'child, 'a>, Vec<Error<'a>>> {
        Scope::new(self.module, Some(self), bindings)
    }

    pub fn local(&self, name: &str) -> Option<Region> {
        let mut scope = Some(self);
        while let Some(current) = scope {
            if let Some(region) = current.bindings.get(name) {
                return Some(*region);
            }
            scope = current.parent;
        }
        None
    }

    pub fn possible_var_names(&self, bump: &'a Bump) -> crate::error::PossibleNames<'a> {
        let mut names: std::collections::BTreeSet<_> = self.module.vars.keys().copied().collect();
        let mut scope = Some(self);
        while let Some(current) = scope {
            names.extend(current.bindings.keys().copied());
            scope = current.parent;
        }
        let locals = bump.alloc_slice_fill_iter(names);
        let qualified =
            bump.alloc_slice_fill_iter(self.module.q_vars.iter().map(|(prefix, inner)| {
                let names = bump.alloc_slice_fill_iter(inner.keys().copied());
                (*prefix, names as &[&str])
            }));
        crate::error::PossibleNames { locals, qualified }
    }
}

impl<'a> Env<'a> {
    /// Compiler-generated calls use trait identity, independent of value names
    /// and import aliases in the source module.
    pub fn method_annotation(
        &self,
        trait_: nash_ast::QualifiedName<'a>,
        method: &str,
    ) -> Option<&'a nash_ast::Annotation<'a>> {
        self.traits
            .values()
            .chain(self.q_traits.values().flat_map(|traits| traits.values()))
            .find_map(|info| match info {
                Info::Specific(_, info) if info.home == trait_.home && info.name == trait_.name => {
                    info.methods
                        .iter()
                        .find(|info| info.name == method)
                        .map(|info| info.annotation)
                }
                _ => None,
            })
    }

    pub fn find_trait(
        &self,
        bump: &'a Bump,
        region: Region,
        prefix: Option<&'a str>,
        name: &'a str,
    ) -> Result<&'a TraitInfo<'a>, Vec<Error<'a>>> {
        let found = match prefix {
            Some(prefix) => self
                .q_traits
                .get(prefix)
                .and_then(|traits| traits.get(name)),
            None => self.traits.get(name),
        };
        match found {
            Some(Info::Specific(_, info)) => Ok(info),
            Some(Info::Ambiguous(first, others)) => Err(vec![Error::AmbiguousTrait {
                region,
                prefix,
                name,
                first_module: *first,
                other_modules: bump.alloc_slice_copy(others),
            }]),
            None => Err(vec![Error::NotFoundTrait {
                region,
                prefix,
                name,
            }]),
        }
    }

    /// Insert into both the unqualified and self-qualified tables.
    /// Used by local.rs — local definitions overwrite imported ones.
    pub fn insert_local_type(&mut self, name: &'a str, typ: Type<'a>) {
        self.types.insert(name, Info::Specific(self.home, typ));
        self.q_types
            .entry(self.home.name)
            .or_default()
            .insert(name, Info::Specific(self.home, typ));
    }

    /// Insert into both the unqualified and self-qualified ctor tables.
    pub fn insert_local_ctor(&mut self, name: &'a str, ctor: Ctor<'a>) {
        self.ctors.insert(name, Info::Specific(self.home, ctor));
        self.q_ctors
            .entry(self.home.name)
            .or_default()
            .insert(name, Info::Specific(self.home, ctor));
    }

    /// Look up an unqualified constructor. Mirrors Elm's `Env.findCtor`.
    pub fn find_ctor(
        &self,
        bump: &'a Bump,
        region: Region,
        name: &'a str,
    ) -> Result<Ctor<'a>, Vec<Error<'a>>> {
        match self.ctors.get(name) {
            Some(Info::Specific(_, ctor)) => Ok(*ctor),
            Some(Info::Ambiguous(first, others)) => Err(vec![Error::AmbiguousCtor {
                region,
                prefix: None,
                name,
                first_module: *first,
                other_modules: bump.alloc_slice_fill_iter(others.iter().copied()),
            }]),
            None => Err(vec![Error::NotFoundCtor {
                region,
                prefix: None,
                name,
                suggestions: self.possible_ctor_names(bump),
            }]),
        }
    }

    /// Look up a qualified constructor. Mirrors Elm's `Env.findCtorQual`.
    pub fn find_ctor_qual(
        &self,
        bump: &'a Bump,
        region: Region,
        prefix: &'a str,
        name: &'a str,
    ) -> Result<Ctor<'a>, Vec<Error<'a>>> {
        let info = self
            .q_ctors
            .get(prefix)
            .and_then(|m| m.get(name))
            .ok_or_else(|| {
                vec![Error::NotFoundCtor {
                    region,
                    prefix: Some(prefix),
                    name,
                    suggestions: self.possible_ctor_names(bump),
                }]
            })?;
        match info {
            Info::Specific(_, ctor) => Ok(*ctor),
            Info::Ambiguous(first, others) => Err(vec![Error::AmbiguousCtor {
                region,
                prefix: Some(prefix),
                name,
                first_module: *first,
                other_modules: bump.alloc_slice_fill_iter(others.iter().copied()),
            }]),
        }
    }

    /// Look up a binop by symbol. Mirrors Elm's `Env.findBinop`.
    pub fn find_binop(
        &self,
        bump: &'a Bump,
        region: Region,
        symbol: &'a str,
    ) -> Result<Binop<'a>, Vec<Error<'a>>> {
        match self.binops.get(symbol) {
            Some(Info::Specific(_, binop)) => Ok(*binop),
            Some(Info::Ambiguous(first, others)) => Err(vec![Error::AmbiguousBinop {
                region,
                name: symbol,
                first_module: *first,
                other_modules: bump.alloc_slice_fill_iter(others.iter().copied()),
            }]),
            None => Err(vec![Error::NotFoundBinop {
                region,
                name: symbol,
                available: self.available_binops(bump),
            }]),
        }
    }

    fn available_binops(&self, bump: &'a Bump) -> &'a [&'a str] {
        bump.alloc_slice_fill_iter(self.binops.keys().copied())
    }

    pub fn possible_type_names(&self, bump: &'a Bump) -> crate::error::PossibleNames<'a> {
        let locals = bump.alloc_slice_fill_iter(self.types.keys().copied());
        let qualified = bump.alloc_slice_fill_iter(self.q_types.iter().map(|(prefix, inner)| {
            let names = bump.alloc_slice_fill_iter(inner.keys().copied());
            (*prefix, names as &[&str])
        }));
        crate::error::PossibleNames { locals, qualified }
    }

    pub fn possible_ctor_names(&self, bump: &'a Bump) -> crate::error::PossibleNames<'a> {
        let locals = bump.alloc_slice_fill_iter(self.ctors.keys().copied());
        let qualified = bump.alloc_slice_fill_iter(self.q_ctors.iter().map(|(prefix, inner)| {
            let names = bump.alloc_slice_fill_iter(inner.keys().copied());
            (*prefix, names as &[&str])
        }));
        crate::error::PossibleNames { locals, qualified }
    }
}

// --- Merge helpers (Elm's mergeInfo) ---

/// Twins have matching type/constructor arities and constructor order. Their
/// names differ only in the case of the initial ASCII letter.
pub(super) fn twin_unions(
    left: &str,
    left_arity: usize,
    left_ctors: &[&nash_ast::Ctor<'_>],
    right: &str,
    right_arity: usize,
    right_ctors: &[&nash_ast::Ctor<'_>],
) -> bool {
    let (Some(a), Some(b)) = (left.as_bytes().first(), right.as_bytes().first()) else {
        return false;
    };
    a != b
        && a.eq_ignore_ascii_case(b)
        && left.get(1..) == right.get(1..)
        && left_arity == right_arity
        && left_ctors.len() == right_ctors.len()
        && left_ctors
            .iter()
            .zip(right_ctors)
            .all(|(a, b)| a.name == b.name && a.arity == b.arity && a.labels == b.labels)
}

pub fn merge_exposed<'a, T: Clone>(
    table: &mut Exposed<'a, T>,
    name: &'a str,
    home: ModuleName<'a>,
    value: T,
) {
    use std::collections::btree_map::Entry;
    match table.entry(name) {
        Entry::Vacant(e) => {
            e.insert(Info::Specific(home, value));
        }
        Entry::Occupied(mut e) => match e.get() {
            // Elm's `mergeInfo` compares the full canonical name (package
            // and module) and keeps the FIRST value when they are equal.
            Info::Specific(existing, _) if *existing != home => {
                let first = *existing;
                e.insert(Info::Ambiguous(first, vec![home]));
            }
            // Like `OneOrMore.more`, appends are unconditional.
            Info::Ambiguous(..) => {
                if let Info::Ambiguous(_, others) = e.get_mut() {
                    others.push(home);
                }
            }
            _ => {}
        },
    }
}

pub fn merge_qualified<'a, T: Clone>(
    table: &mut Qualified<'a, T>,
    prefix: &'a str,
    name: &'a str,
    home: ModuleName<'a>,
    value: T,
) {
    let inner = table.entry(prefix).or_default();
    merge_exposed(inner, name, home, value);
}

#[cfg(test)]
mod tests {
    use super::*;
    use nash_ast::{Head, ImplKey, PackageName, QualifiedName};

    #[test]
    fn trait_candidates_match_full_map_filter_in_order() {
        let bump = Bump::new();
        let mut tables = Tables::default();
        let mut traits = Vec::new();
        for package in [
            None,
            Some(PackageName {
                author: "a",
                project: "b",
            }),
        ] {
            for module in ["A", "AA", "B"] {
                for name in ["A", "AA", "B"] {
                    let trait_ = QualifiedName {
                        home: ModuleName {
                            package,
                            name: module,
                        },
                        name,
                    };
                    traits.push(trait_);
                    for heads in [
                        vec![],
                        vec![Head::Var {
                            index: 0,
                            repr: nash_ast::primitives::ReprSet::ALL,
                        }],
                        vec![Head::Var {
                            index: 1,
                            repr: nash_ast::primitives::ReprSet::ALL,
                        }],
                        vec![
                            Head::Var {
                                index: 0,
                                repr: nash_ast::primitives::ReprSet::ALL,
                            },
                            Head::Var {
                                index: 1,
                                repr: nash_ast::primitives::ReprSet::ALL,
                            },
                        ],
                    ] {
                        let key = ImplKey {
                            trait_,
                            heads: bump.alloc_slice_copy(&heads),
                        };
                        let info = bump.alloc(ImplInfo {
                            variables: &[],
                            home: trait_.home,
                            region: Region::zero(),
                            trait_,
                            context: &[],
                            heads: &[],
                            methods: &[],
                        });
                        tables.impls.insert(key, info);
                    }
                }
            }
        }
        for module in ["", "AB", "Z"] {
            traits.push(QualifiedName {
                home: ModuleName {
                    package: None,
                    name: module,
                },
                name: "Missing",
            });
        }
        for trait_ in traits {
            let expected: Vec<_> = tables
                .impls
                .iter()
                .filter(|(key, _)| key.trait_ == trait_)
                .collect();
            let actual: Vec<_> = tables.impls_for(trait_).collect();
            assert_eq!(
                actual.iter().map(|(key, _)| *key).collect::<Vec<_>>(),
                expected.iter().map(|(key, _)| *key).collect::<Vec<_>>()
            );
            for ((_, actual), (_, expected)) in actual.into_iter().zip(expected) {
                assert!(std::ptr::eq(*actual, *expected));
            }
        }
    }
}