1 use crate::cdsl::ast::{Def, DefIndex, DefPool, Var, VarIndex, VarPool};
2 use crate::cdsl::typevar::{DerivedFunc, TypeSet, TypeVar};
3
4 use std::collections::{HashMap, HashSet};
5 use std::iter::FromIterator;
6
7 #[derive(Debug, Hash, PartialEq, Eq)]
8 pub(crate) enum Constraint {
9 /// Constraint specifying that a type var tv1 must be wider than or equal to type var tv2 at
10 /// runtime. This requires that:
11 /// 1) They have the same number of lanes
12 /// 2) In a lane tv1 has at least as many bits as tv2.
13 WiderOrEq(TypeVar, TypeVar),
14
15 /// Constraint specifying that two derived type vars must have the same runtime type.
16 Eq(TypeVar, TypeVar),
17
18 /// Constraint specifying that a type var must belong to some typeset.
19 InTypeset(TypeVar, TypeSet),
20 }
21
22 impl Constraint {
translate_with<F: Fn(&TypeVar) -> TypeVar>(&self, func: F) -> Constraint23 fn translate_with<F: Fn(&TypeVar) -> TypeVar>(&self, func: F) -> Constraint {
24 match self {
25 Constraint::WiderOrEq(lhs, rhs) => {
26 let lhs = func(&lhs);
27 let rhs = func(&rhs);
28 Constraint::WiderOrEq(lhs, rhs)
29 }
30 Constraint::Eq(lhs, rhs) => {
31 let lhs = func(&lhs);
32 let rhs = func(&rhs);
33 Constraint::Eq(lhs, rhs)
34 }
35 Constraint::InTypeset(tv, ts) => {
36 let tv = func(&tv);
37 Constraint::InTypeset(tv, ts.clone())
38 }
39 }
40 }
41
42 /// Creates a new constraint by replacing type vars by their hashmap equivalent.
translate_with_map( &self, original_to_own_typevar: &HashMap<&TypeVar, TypeVar>, ) -> Constraint43 fn translate_with_map(
44 &self,
45 original_to_own_typevar: &HashMap<&TypeVar, TypeVar>,
46 ) -> Constraint {
47 self.translate_with(|tv| substitute(original_to_own_typevar, tv))
48 }
49
50 /// Creates a new constraint by replacing type vars by their canonical equivalent.
translate_with_env(&self, type_env: &TypeEnvironment) -> Constraint51 fn translate_with_env(&self, type_env: &TypeEnvironment) -> Constraint {
52 self.translate_with(|tv| type_env.get_equivalent(tv))
53 }
54
is_trivial(&self) -> bool55 fn is_trivial(&self) -> bool {
56 match self {
57 Constraint::WiderOrEq(lhs, rhs) => {
58 // Trivially true.
59 if lhs == rhs {
60 return true;
61 }
62
63 let ts1 = lhs.get_typeset();
64 let ts2 = rhs.get_typeset();
65
66 // Trivially true.
67 if ts1.is_wider_or_equal(&ts2) {
68 return true;
69 }
70
71 // Trivially false.
72 if ts1.is_narrower(&ts2) {
73 return true;
74 }
75
76 // Trivially false.
77 if (&ts1.lanes & &ts2.lanes).is_empty() {
78 return true;
79 }
80
81 self.is_concrete()
82 }
83 Constraint::Eq(lhs, rhs) => lhs == rhs || self.is_concrete(),
84 Constraint::InTypeset(_, _) => {
85 // The way InTypeset are made, they would always be trivial if we were applying the
86 // same logic as the Python code did, so ignore this.
87 self.is_concrete()
88 }
89 }
90 }
91
92 /// Returns true iff all the referenced type vars are singletons.
is_concrete(&self) -> bool93 fn is_concrete(&self) -> bool {
94 match self {
95 Constraint::WiderOrEq(lhs, rhs) => {
96 lhs.singleton_type().is_some() && rhs.singleton_type().is_some()
97 }
98 Constraint::Eq(lhs, rhs) => {
99 lhs.singleton_type().is_some() && rhs.singleton_type().is_some()
100 }
101 Constraint::InTypeset(tv, _) => tv.singleton_type().is_some(),
102 }
103 }
104
typevar_args(&self) -> Vec<&TypeVar>105 fn typevar_args(&self) -> Vec<&TypeVar> {
106 match self {
107 Constraint::WiderOrEq(lhs, rhs) => vec![lhs, rhs],
108 Constraint::Eq(lhs, rhs) => vec![lhs, rhs],
109 Constraint::InTypeset(tv, _) => vec![tv],
110 }
111 }
112 }
113
114 #[derive(Clone, Copy)]
115 enum TypeEnvRank {
116 Singleton = 5,
117 Input = 4,
118 Intermediate = 3,
119 Output = 2,
120 Temp = 1,
121 Internal = 0,
122 }
123
124 /// Class encapsulating the necessary bookkeeping for type inference.
125 pub(crate) struct TypeEnvironment {
126 vars: HashSet<VarIndex>,
127 ranks: HashMap<TypeVar, TypeEnvRank>,
128 equivalency_map: HashMap<TypeVar, TypeVar>,
129 pub constraints: Vec<Constraint>,
130 }
131
132 impl TypeEnvironment {
new() -> Self133 fn new() -> Self {
134 TypeEnvironment {
135 vars: HashSet::new(),
136 ranks: HashMap::new(),
137 equivalency_map: HashMap::new(),
138 constraints: Vec::new(),
139 }
140 }
141
register(&mut self, var_index: VarIndex, var: &mut Var)142 fn register(&mut self, var_index: VarIndex, var: &mut Var) {
143 self.vars.insert(var_index);
144 let rank = if var.is_input() {
145 TypeEnvRank::Input
146 } else if var.is_intermediate() {
147 TypeEnvRank::Intermediate
148 } else if var.is_output() {
149 TypeEnvRank::Output
150 } else {
151 assert!(var.is_temp());
152 TypeEnvRank::Temp
153 };
154 self.ranks.insert(var.get_or_create_typevar(), rank);
155 }
156
add_constraint(&mut self, constraint: Constraint)157 fn add_constraint(&mut self, constraint: Constraint) {
158 if self.constraints.iter().any(|item| *item == constraint) {
159 return;
160 }
161
162 // Check extra conditions for InTypeset constraints.
163 if let Constraint::InTypeset(tv, _) = &constraint {
164 assert!(
165 tv.base.is_none(),
166 "type variable is {:?}, while expecting none",
167 tv
168 );
169 assert!(
170 tv.name.starts_with("typeof_"),
171 "Name \"{}\" should start with \"typeof_\"",
172 tv.name
173 );
174 }
175
176 self.constraints.push(constraint);
177 }
178
179 /// Returns the canonical representative of the equivalency class of the given argument, or
180 /// duplicates it if it's not there yet.
get_equivalent(&self, tv: &TypeVar) -> TypeVar181 pub fn get_equivalent(&self, tv: &TypeVar) -> TypeVar {
182 let mut tv = tv;
183 while let Some(found) = self.equivalency_map.get(tv) {
184 tv = found;
185 }
186 match &tv.base {
187 Some(parent) => self
188 .get_equivalent(&parent.type_var)
189 .derived(parent.derived_func),
190 None => tv.clone(),
191 }
192 }
193
194 /// Get the rank of tv in the partial order:
195 /// - TVs directly associated with a Var get their rank from the Var (see register()).
196 /// - Internally generated non-derived TVs implicitly get the lowest rank (0).
197 /// - Derived variables get their rank from their free typevar.
198 /// - Singletons have the highest rank.
199 /// - TVs associated with vars in a source pattern have a higher rank than TVs associated with
200 /// temporary vars.
rank(&self, tv: &TypeVar) -> u8201 fn rank(&self, tv: &TypeVar) -> u8 {
202 let actual_tv = match tv.base {
203 Some(_) => tv.free_typevar(),
204 None => Some(tv.clone()),
205 };
206
207 let rank = match actual_tv {
208 Some(actual_tv) => match self.ranks.get(&actual_tv) {
209 Some(rank) => Some(*rank),
210 None => {
211 assert!(
212 !actual_tv.name.starts_with("typeof_"),
213 format!("variable {} should be explicitly ranked", actual_tv.name)
214 );
215 None
216 }
217 },
218 None => None,
219 };
220
221 let rank = match rank {
222 Some(rank) => rank,
223 None => {
224 if tv.singleton_type().is_some() {
225 TypeEnvRank::Singleton
226 } else {
227 TypeEnvRank::Internal
228 }
229 }
230 };
231
232 rank as u8
233 }
234
235 /// Record the fact that the free tv1 is part of the same equivalence class as tv2. The
236 /// canonical representative of the merged class is tv2's canonical representative.
record_equivalent(&mut self, tv1: TypeVar, tv2: TypeVar)237 fn record_equivalent(&mut self, tv1: TypeVar, tv2: TypeVar) {
238 assert!(tv1.base.is_none());
239 assert!(self.get_equivalent(&tv1) == tv1);
240 if let Some(tv2_base) = &tv2.base {
241 // Ensure there are no cycles.
242 assert!(self.get_equivalent(&tv2_base.type_var) != tv1);
243 }
244 self.equivalency_map.insert(tv1, tv2);
245 }
246
247 /// Get the free typevars in the current type environment.
free_typevars(&self, var_pool: &mut VarPool) -> Vec<TypeVar>248 pub fn free_typevars(&self, var_pool: &mut VarPool) -> Vec<TypeVar> {
249 let mut typevars = Vec::new();
250 typevars.extend(self.equivalency_map.keys().cloned());
251 typevars.extend(
252 self.vars
253 .iter()
254 .map(|&var_index| var_pool.get_mut(var_index).get_or_create_typevar()),
255 );
256
257 let set: HashSet<TypeVar> = HashSet::from_iter(
258 typevars
259 .iter()
260 .map(|tv| self.get_equivalent(tv).free_typevar())
261 .filter(|opt_tv| {
262 // Filter out singleton types.
263 opt_tv.is_some()
264 })
265 .map(|tv| tv.unwrap()),
266 );
267 Vec::from_iter(set)
268 }
269
270 /// Normalize by collapsing any roots that don't correspond to a concrete type var AND have a
271 /// single type var derived from them or equivalent to them.
272 ///
273 /// e.g. if we have a root of the tree that looks like:
274 ///
275 /// typeof_a typeof_b
276 /// \\ /
277 /// typeof_x
278 /// |
279 /// half_width(1)
280 /// |
281 /// 1
282 ///
283 /// we want to collapse the linear path between 1 and typeof_x. The resulting graph is:
284 ///
285 /// typeof_a typeof_b
286 /// \\ /
287 /// typeof_x
normalize(&mut self, var_pool: &mut VarPool)288 fn normalize(&mut self, var_pool: &mut VarPool) {
289 let source_tvs: HashSet<TypeVar> = HashSet::from_iter(
290 self.vars
291 .iter()
292 .map(|&var_index| var_pool.get_mut(var_index).get_or_create_typevar()),
293 );
294
295 let mut children: HashMap<TypeVar, HashSet<TypeVar>> = HashMap::new();
296
297 // Insert all the parents found by the derivation relationship.
298 for type_var in self.equivalency_map.values() {
299 if type_var.base.is_none() {
300 continue;
301 }
302
303 let parent_tv = type_var.free_typevar();
304 if parent_tv.is_none() {
305 // Ignore this type variable, it's a singleton.
306 continue;
307 }
308 let parent_tv = parent_tv.unwrap();
309
310 children
311 .entry(parent_tv)
312 .or_insert_with(HashSet::new)
313 .insert(type_var.clone());
314 }
315
316 // Insert all the explicit equivalency links.
317 for (equivalent_tv, canon_tv) in self.equivalency_map.iter() {
318 children
319 .entry(canon_tv.clone())
320 .or_insert_with(HashSet::new)
321 .insert(equivalent_tv.clone());
322 }
323
324 // Remove links that are straight paths up to typevar of variables.
325 for free_root in self.free_typevars(var_pool) {
326 let mut root = &free_root;
327 while !source_tvs.contains(&root)
328 && children.contains_key(&root)
329 && children.get(&root).unwrap().len() == 1
330 {
331 let child = children.get(&root).unwrap().iter().next().unwrap();
332 assert_eq!(self.equivalency_map[child], root.clone());
333 self.equivalency_map.remove(child);
334 root = child;
335 }
336 }
337 }
338
339 /// Extract a clean type environment from self, that only mentions type vars associated with
340 /// real variables.
extract(self, var_pool: &mut VarPool) -> TypeEnvironment341 fn extract(self, var_pool: &mut VarPool) -> TypeEnvironment {
342 let vars_tv: HashSet<TypeVar> = HashSet::from_iter(
343 self.vars
344 .iter()
345 .map(|&var_index| var_pool.get_mut(var_index).get_or_create_typevar()),
346 );
347
348 let mut new_equivalency_map: HashMap<TypeVar, TypeVar> = HashMap::new();
349 for tv in &vars_tv {
350 let canon_tv = self.get_equivalent(tv);
351 if *tv != canon_tv {
352 new_equivalency_map.insert(tv.clone(), canon_tv.clone());
353 }
354
355 // Sanity check: the translated type map should only refer to real variables.
356 assert!(vars_tv.contains(tv));
357 let canon_free_tv = canon_tv.free_typevar();
358 assert!(canon_free_tv.is_none() || vars_tv.contains(&canon_free_tv.unwrap()));
359 }
360
361 let mut new_constraints: HashSet<Constraint> = HashSet::new();
362 for constraint in &self.constraints {
363 let constraint = constraint.translate_with_env(&self);
364 if constraint.is_trivial() || new_constraints.contains(&constraint) {
365 continue;
366 }
367
368 // Sanity check: translated constraints should refer only to real variables.
369 for arg in constraint.typevar_args() {
370 let arg_free_tv = arg.free_typevar();
371 assert!(arg_free_tv.is_none() || vars_tv.contains(&arg_free_tv.unwrap()));
372 }
373
374 new_constraints.insert(constraint);
375 }
376
377 TypeEnvironment {
378 vars: self.vars,
379 ranks: self.ranks,
380 equivalency_map: new_equivalency_map,
381 constraints: Vec::from_iter(new_constraints),
382 }
383 }
384 }
385
386 /// Replaces an external type variable according to the following rules:
387 /// - if a local copy is present in the map, return it.
388 /// - or if it's derived, create a local derived one that recursively substitutes the parent.
389 /// - or return itself.
substitute(map: &HashMap<&TypeVar, TypeVar>, external_type_var: &TypeVar) -> TypeVar390 fn substitute(map: &HashMap<&TypeVar, TypeVar>, external_type_var: &TypeVar) -> TypeVar {
391 match map.get(&external_type_var) {
392 Some(own_type_var) => own_type_var.clone(),
393 None => match &external_type_var.base {
394 Some(parent) => {
395 let parent_substitute = substitute(map, &parent.type_var);
396 TypeVar::derived(&parent_substitute, parent.derived_func)
397 }
398 None => external_type_var.clone(),
399 },
400 }
401 }
402
403 /// Normalize a (potentially derived) typevar using the following rules:
404 ///
405 /// - vector and width derived functions commute
406 /// {HALF,DOUBLE}VECTOR({HALF,DOUBLE}WIDTH(base)) ->
407 /// {HALF,DOUBLE}WIDTH({HALF,DOUBLE}VECTOR(base))
408 ///
409 /// - half/double pairs collapse
410 /// {HALF,DOUBLE}WIDTH({DOUBLE,HALF}WIDTH(base)) -> base
411 /// {HALF,DOUBLE}VECTOR({DOUBLE,HALF}VECTOR(base)) -> base
canonicalize_derivations(tv: TypeVar) -> TypeVar412 fn canonicalize_derivations(tv: TypeVar) -> TypeVar {
413 let base = match &tv.base {
414 Some(base) => base,
415 None => return tv,
416 };
417
418 let derived_func = base.derived_func;
419
420 if let Some(base_base) = &base.type_var.base {
421 let base_base_tv = &base_base.type_var;
422 match (derived_func, base_base.derived_func) {
423 (DerivedFunc::HalfWidth, DerivedFunc::DoubleWidth)
424 | (DerivedFunc::DoubleWidth, DerivedFunc::HalfWidth)
425 | (DerivedFunc::HalfVector, DerivedFunc::DoubleVector)
426 | (DerivedFunc::DoubleVector, DerivedFunc::HalfVector) => {
427 // Cancelling bijective transformations. This doesn't hide any overflow issues
428 // since derived type sets are checked upon derivaion, and base typesets are only
429 // allowed to shrink.
430 return canonicalize_derivations(base_base_tv.clone());
431 }
432 (DerivedFunc::HalfWidth, DerivedFunc::HalfVector)
433 | (DerivedFunc::HalfWidth, DerivedFunc::DoubleVector)
434 | (DerivedFunc::DoubleWidth, DerivedFunc::DoubleVector)
435 | (DerivedFunc::DoubleWidth, DerivedFunc::HalfVector) => {
436 // Arbitrarily put WIDTH derivations before VECTOR derivations, since they commute.
437 return canonicalize_derivations(
438 base_base_tv
439 .derived(derived_func)
440 .derived(base_base.derived_func),
441 );
442 }
443 _ => {}
444 };
445 }
446
447 canonicalize_derivations(base.type_var.clone()).derived(derived_func)
448 }
449
450 /// Given typevars tv1 and tv2 (which could be derived from one another), constrain their typesets
451 /// to be the same. When one is derived from the other, repeat the constrain process until
452 /// a fixed point is reached.
constrain_fixpoint(tv1: &TypeVar, tv2: &TypeVar)453 fn constrain_fixpoint(tv1: &TypeVar, tv2: &TypeVar) {
454 loop {
455 let old_tv1_ts = tv1.get_typeset().clone();
456 tv2.constrain_types(tv1.clone());
457 if tv1.get_typeset() == old_tv1_ts {
458 break;
459 }
460 }
461
462 let old_tv2_ts = tv2.get_typeset();
463 tv1.constrain_types(tv2.clone());
464 // The above loop should ensure that all reference cycles have been handled.
465 assert!(old_tv2_ts == tv2.get_typeset());
466 }
467
468 /// Unify tv1 and tv2 in the given type environment. tv1 must have a rank greater or equal to tv2's
469 /// one, modulo commutations.
unify(tv1: &TypeVar, tv2: &TypeVar, type_env: &mut TypeEnvironment) -> Result<(), String>470 fn unify(tv1: &TypeVar, tv2: &TypeVar, type_env: &mut TypeEnvironment) -> Result<(), String> {
471 let tv1 = canonicalize_derivations(type_env.get_equivalent(tv1));
472 let tv2 = canonicalize_derivations(type_env.get_equivalent(tv2));
473
474 if tv1 == tv2 {
475 // Already unified.
476 return Ok(());
477 }
478
479 if type_env.rank(&tv2) < type_env.rank(&tv1) {
480 // Make sure tv1 always has the smallest rank, since real variables have the higher rank
481 // and we want them to be the canonical representatives of their equivalency classes.
482 return unify(&tv2, &tv1, type_env);
483 }
484
485 constrain_fixpoint(&tv1, &tv2);
486
487 if tv1.get_typeset().size() == 0 || tv2.get_typeset().size() == 0 {
488 return Err(format!(
489 "Error: empty type created when unifying {} and {}",
490 tv1.name, tv2.name
491 ));
492 }
493
494 let base = match &tv1.base {
495 Some(base) => base,
496 None => {
497 type_env.record_equivalent(tv1, tv2);
498 return Ok(());
499 }
500 };
501
502 if let Some(inverse) = base.derived_func.inverse() {
503 return unify(&base.type_var, &tv2.derived(inverse), type_env);
504 }
505
506 type_env.add_constraint(Constraint::Eq(tv1, tv2));
507 Ok(())
508 }
509
510 /// Perform type inference on one Def in the current type environment and return an updated type
511 /// environment or error.
512 ///
513 /// At a high level this works by creating fresh copies of each formal type var in the Def's
514 /// instruction's signature, and unifying the formal typevar with the corresponding actual typevar.
infer_definition( def: &Def, var_pool: &mut VarPool, type_env: TypeEnvironment, last_type_index: &mut usize, ) -> Result<TypeEnvironment, String>515 fn infer_definition(
516 def: &Def,
517 var_pool: &mut VarPool,
518 type_env: TypeEnvironment,
519 last_type_index: &mut usize,
520 ) -> Result<TypeEnvironment, String> {
521 let apply = &def.apply;
522 let inst = &apply.inst;
523
524 let mut type_env = type_env;
525 let free_formal_tvs = inst.all_typevars();
526
527 let mut original_to_own_typevar: HashMap<&TypeVar, TypeVar> = HashMap::new();
528 for &tv in &free_formal_tvs {
529 assert!(original_to_own_typevar
530 .insert(
531 tv,
532 TypeVar::copy_from(tv, format!("own_{}", last_type_index))
533 )
534 .is_none());
535 *last_type_index += 1;
536 }
537
538 // Update the mapping with any explicity bound type vars:
539 for (i, value_type) in apply.value_types.iter().enumerate() {
540 let singleton = TypeVar::new_singleton(value_type.clone());
541 assert!(original_to_own_typevar
542 .insert(free_formal_tvs[i], singleton)
543 .is_some());
544 }
545
546 // Get fresh copies for each typevar in the signature (both free and derived).
547 let mut formal_tvs = Vec::new();
548 formal_tvs.extend(inst.value_results.iter().map(|&i| {
549 substitute(
550 &original_to_own_typevar,
551 inst.operands_out[i].type_var().unwrap(),
552 )
553 }));
554 formal_tvs.extend(inst.value_opnums.iter().map(|&i| {
555 substitute(
556 &original_to_own_typevar,
557 inst.operands_in[i].type_var().unwrap(),
558 )
559 }));
560
561 // Get the list of actual vars.
562 let mut actual_vars = Vec::new();
563 actual_vars.extend(inst.value_results.iter().map(|&i| def.defined_vars[i]));
564 actual_vars.extend(
565 inst.value_opnums
566 .iter()
567 .map(|&i| apply.args[i].unwrap_var()),
568 );
569
570 // Get the list of the actual TypeVars.
571 let mut actual_tvs = Vec::new();
572 for var_index in actual_vars {
573 let var = var_pool.get_mut(var_index);
574 type_env.register(var_index, var);
575 actual_tvs.push(var.get_or_create_typevar());
576 }
577
578 // Make sure we start unifying with the control type variable first, by putting it at the
579 // front of both vectors.
580 if let Some(poly) = &inst.polymorphic_info {
581 let own_ctrl_tv = &original_to_own_typevar[&poly.ctrl_typevar];
582 let ctrl_index = formal_tvs.iter().position(|tv| tv == own_ctrl_tv).unwrap();
583 if ctrl_index != 0 {
584 formal_tvs.swap(0, ctrl_index);
585 actual_tvs.swap(0, ctrl_index);
586 }
587 }
588
589 // Unify each actual type variable with the corresponding formal type variable.
590 for (actual_tv, formal_tv) in actual_tvs.iter().zip(&formal_tvs) {
591 if let Err(msg) = unify(actual_tv, formal_tv, &mut type_env) {
592 return Err(format!(
593 "fail ti on {} <: {}: {}",
594 actual_tv.name, formal_tv.name, msg
595 ));
596 }
597 }
598
599 // Add any instruction specific constraints.
600 for constraint in &inst.constraints {
601 type_env.add_constraint(constraint.translate_with_map(&original_to_own_typevar));
602 }
603
604 Ok(type_env)
605 }
606
607 /// Perform type inference on an transformation. Return an updated type environment or error.
infer_transform( src: DefIndex, dst: &[DefIndex], def_pool: &DefPool, var_pool: &mut VarPool, ) -> Result<TypeEnvironment, String>608 pub(crate) fn infer_transform(
609 src: DefIndex,
610 dst: &[DefIndex],
611 def_pool: &DefPool,
612 var_pool: &mut VarPool,
613 ) -> Result<TypeEnvironment, String> {
614 let mut type_env = TypeEnvironment::new();
615 let mut last_type_index = 0;
616
617 // Execute type inference on the source pattern.
618 type_env = infer_definition(def_pool.get(src), var_pool, type_env, &mut last_type_index)
619 .map_err(|err| format!("In src pattern: {}", err))?;
620
621 // Collect the type sets once after applying the source patterm; we'll compare the typesets
622 // after we've also considered the destination pattern, and will emit supplementary InTypeset
623 // checks if they don't match.
624 let src_typesets = type_env
625 .vars
626 .iter()
627 .map(|&var_index| {
628 let var = var_pool.get_mut(var_index);
629 let tv = type_env.get_equivalent(&var.get_or_create_typevar());
630 (var_index, tv.get_typeset())
631 })
632 .collect::<Vec<_>>();
633
634 // Execute type inference on the destination pattern.
635 for (i, &def_index) in dst.iter().enumerate() {
636 let def = def_pool.get(def_index);
637 type_env = infer_definition(def, var_pool, type_env, &mut last_type_index)
638 .map_err(|err| format!("line {}: {}", i, err))?;
639 }
640
641 for (var_index, src_typeset) in src_typesets {
642 let var = var_pool.get(var_index);
643 if !var.has_free_typevar() {
644 continue;
645 }
646 let tv = type_env.get_equivalent(&var.get_typevar().unwrap());
647 let new_typeset = tv.get_typeset();
648 assert!(
649 new_typeset.is_subset(&src_typeset),
650 "type sets can only get narrower"
651 );
652 if new_typeset != src_typeset {
653 type_env.add_constraint(Constraint::InTypeset(tv.clone(), new_typeset.clone()));
654 }
655 }
656
657 type_env.normalize(var_pool);
658
659 Ok(type_env.extract(var_pool))
660 }
661