lyte/
query.rs

1use crate::{
2    ErrorHandler, Generics, ImplID, Mapping, TEnv, Type, TypeContext, TypeData, TypeKind, Types,
3    TypesBuf,
4};
5use itertools::Itertools;
6use smallvec::SmallVec;
7use std::collections::HashMap;
8use std::fmt;
9
10pub type AssociatedTypes<D> = Vec<(<D as TypeData>::Generic, Type<D>)>;
11
12#[derive(Debug)]
13pub struct Impl<D: TypeData> {
14    pub forall: Generics<D>,
15    pub trait_type_params: TypesBuf<D>,
16    pub impltor: Type<D>,
17
18    pub implid: ImplID,
19    pub associated: AssociatedTypes<D>,
20}
21
22#[derive(Default)]
23pub struct TraitIndex<D: TypeData> {
24    trids: HashMap<D::Trait, Variants<D>>,
25    count: usize,
26}
27
28#[derive(Debug)]
29struct Variants<D: TypeData> {
30    concrete: HashMap<D::Concrete, Vec<Impl<D>>>,
31    object: HashMap<D::Trait, Vec<Impl<D>>>,
32    blanked: Vec<Impl<D>>,
33
34    default: Option<Impl<D>>,
35}
36
37pub struct QuerySuccess<'a, D: TypeData> {
38    pub impl_: &'a Impl<D>,
39    pub mapping: Mapping<D>,
40    pub tenv: TEnv<D>,
41    pub unified_impltor: Type<D>,
42}
43
44impl<D: TypeData> TraitIndex<D> {
45    pub fn new() -> Self {
46        TraitIndex {
47            trids: HashMap::new(),
48            count: 0,
49        }
50    }
51
52    pub fn implement(
53        &mut self,
54        generics: Generics<D>,
55        trid: D::Trait,
56        trtp: TypesBuf<D>,
57        impltor: Type<D>,
58        associated: AssociatedTypes<D>,
59    ) {
60        let tvariant = self.trids.entry(trid).or_insert_with(Variants::new);
61
62        let constr = impltor.constr.clone();
63
64        #[cfg(debug_assertions)]
65        impltor.map_constr(&mut |_, con| match con {
66            TypeKind::Ref(_) | TypeKind::Self_ => {
67                panic!("invalid constructor for implementor of trait: {:?}", con)
68            }
69            other => other.clone(),
70        });
71
72        let implid = ImplID(self.count);
73        self.count += 1;
74
75        let impl_ = Impl {
76            forall: generics,
77            trait_type_params: trtp,
78            impltor,
79            associated,
80            implid,
81        };
82
83        match constr {
84            TypeKind::Generic(_) => tvariant.blanked.push(impl_),
85            TypeKind::Concrete(c) => tvariant
86                .concrete
87                .entry(c)
88                .or_insert_with(Vec::new)
89                .push(impl_),
90            TypeKind::Object(trid) => tvariant
91                .object
92                .entry(trid)
93                .or_insert_with(Vec::new)
94                .push(impl_),
95            _ => unreachable!(),
96        }
97    }
98
99    pub fn select(
100        &self,
101        tenv: &TEnv<D>,
102        trait_: D::Trait,
103        trait_params: &Types<D>,
104        impltor: &Type<D>,
105    ) -> Result<SmallVec<[QuerySuccess<'_, D>; 1]>, Vec<Contender>> {
106        let variants = match self.trids.get(&trait_) {
107            None => return Err(vec![]),
108            Some(variants) => variants,
109        };
110
111        Selection {
112            tenv,
113            // trait_,
114            trait_params,
115            traits: self,
116        }
117        .run(impltor, variants)
118    }
119}
120
121struct Selection<'a, D: TypeData> {
122    tenv: &'a TEnv<D>,
123    traits: &'a TraitIndex<D>,
124    // trait_: D::Trait,
125    trait_params: &'a Types<D>,
126}
127
128impl<'a, D: TypeData> Selection<'a, D> {
129    fn run<'s>(
130        &mut self,
131        impltor: &Type<D>,
132        variants: &'s Variants<D>,
133    ) -> Result<SmallVec<[QuerySuccess<'s, D>; 1]>, Vec<Contender>> {
134        let mut results = SmallVec::new();
135        let mut contenders = Vec::new();
136
137        match &impltor.constr {
138            TypeKind::Generic(_) => self.filter_suitible(&variants.blanked, impltor, &mut results, &mut contenders),
139            TypeKind::Concrete(c) => {
140                if let Some(impls) = variants.concrete.get(c) {
141                    self.filter_suitible(impls, impltor, &mut results, &mut contenders);
142                }
143                self.filter_suitible(&variants.blanked, impltor, &mut results, &mut contenders);
144            },
145            TypeKind::Self_ => todo!("I think this should just be a panicky branch? or perhaps we want to get the assigned in tenv?"),
146            TypeKind::Object(trid) => {
147                if let Some(impls) = variants.object.get(trid) {
148                    self.filter_suitible(impls, impltor, &mut results, &mut contenders);
149                }
150                self.filter_suitible(&variants.blanked, impltor,  &mut results, &mut contenders);
151            }
152
153            TypeKind::Ref(rid) => match self.tenv.get_type(*rid) {
154                    Some(impltor) => return self.run(impltor, variants),
155                    None => todo!("here we need to check more aggressively in a slow-path to see whichever can be compatible and thereby infer?"),
156                }
157        }
158
159        if results.is_empty() {
160            if let Some(default) = variants.default.as_ref() {
161                match self.is_suitible(default, impltor) {
162                    Ok(success) => results.push(success),
163                    Err(contender) => contenders.push(contender),
164                }
165            }
166        }
167
168        if results.is_empty() {
169            Err(contenders)
170        } else {
171            Ok(results)
172        }
173    }
174
175    fn filter_suitible<'i>(
176        &self,
177        impls: &'i [Impl<D>],
178        impltor: &Type<D>,
179        results: &mut SmallVec<[QuerySuccess<'i, D>; 1]>,
180        contenders: &mut Vec<Contender>,
181    ) {
182        // I guess it might make sense to not allocate contenders and
183        // re-iterate the impls as a cold path on errors?
184        for impl_ in impls {
185            match self.is_suitible(impl_, impltor) {
186                Ok(success) => results.push(success),
187                Err(contender) => contenders.push(contender),
188            }
189        }
190    }
191
192    fn is_suitible<'i>(
193        &self,
194        impl_: &'i Impl<D>,
195        impltor: &Type<D>,
196    ) -> Result<QuerySuccess<'i, D>, Contender> {
197        let mut tenv = self.tenv.clone();
198
199        let mapping = impl_.forall.to_mapping(&mut tenv);
200        let unified_trtp = mapping.apply_types(&impl_.trait_type_params);
201        let unified_impltor = mapping.apply_type(&impl_.impltor);
202
203        #[cfg(debug_assertions)]
204        if self.trait_params.len() != unified_trtp.len() {
205            panic!("missmatched amount of trait parameters");
206        }
207
208        let mut checker = TypeContext::new(&mut tenv, self.traits, ErrorHandler::Cheap);
209        checker
210            .check_types(self.trait_params, &unified_trtp)
211            .map_err(|_| Contender::InvalidTraitParams)?;
212        checker
213            .check(impltor, &unified_impltor)
214            .map_err(|_| Contender::InvalidImpltor)?;
215
216        Ok(QuerySuccess {
217            impl_,
218            mapping,
219            tenv,
220            unified_impltor,
221        })
222    }
223}
224
225impl<D: TypeData> Variants<D> {
226    fn new() -> Self {
227        Self {
228            default: None,
229            concrete: HashMap::new(),
230            object: HashMap::new(),
231            blanked: Vec::new(),
232        }
233    }
234}
235
236/// Why the comparison against an implementation failed
237#[derive(Clone, Copy, PartialEq, Eq, Debug)]
238pub enum Contender {
239    InvalidTraitParams,
240    InvalidImpltor,
241}
242
243impl<D: TypeData> fmt::Debug for TraitIndex<D> {
244    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
245        if self.trids.is_empty() {
246            "![]!".fmt(f)
247        } else {
248            writeln!(f, "![")?;
249            for (trid, variants) in &self.trids {
250                if !variants.concrete.is_empty() {
251                    "concrete:".fmt(f)?;
252                }
253                for impls in variants.concrete.values() {
254                    for impl_ in impls {
255                        fmt_impl(trid, impl_, f)?;
256                    }
257                }
258
259                if !variants.blanked.is_empty() {
260                    "blanked:".fmt(f)?;
261                }
262                for impl_ in &variants.blanked {
263                    fmt_impl(trid, impl_, f)?;
264                }
265            }
266            write!(f, "\n]!")
267        }
268    }
269}
270
271fn fmt_impl<D: TypeData>(trid: &D::Trait, impl_: &Impl<D>, f: &mut fmt::Formatter) -> fmt::Result {
272    writeln!(
273        f,
274        "  impl {}{} for {}",
275        trid,
276        if impl_.trait_type_params.is_empty() {
277            String::new()
278        } else {
279            impl_.trait_type_params.iter().format(" ").to_string()
280        },
281        impl_.impltor
282    )
283}
lyte/query.rs

lyte/
query.rs
