1 //! Traits for transforming bits of IR. 2 3 use crate::*; 4 use std::fmt::Debug; 5 6 mod binder_impls; 7 mod boring_impls; 8 mod in_place; 9 pub mod shift; 10 mod subst; 11 12 pub use self::shift::Shift; 13 pub use self::subst::Subst; 14 15 /// A "folder" is a transformer that can be used to make a copy of 16 /// some term -- that is, some bit of IR, such as a `Goal` -- with 17 /// certain changes applied. The idea is that it contains methods that 18 /// let you swap types/lifetimes for new types/lifetimes; meanwhile, 19 /// each bit of IR implements the `Fold` trait which, given a 20 /// `Folder`, will reconstruct itself, invoking the folder's methods 21 /// to transform each of the types/lifetimes embedded within. 22 /// 23 /// # Usage patterns 24 /// 25 /// ## Substituting for free variables 26 /// 27 /// Most of the time, though, we are not interested in adjust 28 /// arbitrary types/lifetimes, but rather just free variables (even 29 /// more often, just free existential variables) that appear within 30 /// the term. 31 /// 32 /// For this reason, the `Folder` trait extends two other traits that 33 /// contain methods that are invoked when just those particular 34 /// 35 /// In particular, folders can intercept references to free variables 36 /// (either existentially or universally quantified) and replace them 37 /// with other types/lifetimes as appropriate. 38 /// 39 /// To create a folder `F`, one never implements `Folder` directly, but instead 40 /// implements one of each of these three sub-traits: 41 /// 42 /// - `FreeVarFolder` -- folds `BoundVar` instances that appear free 43 /// in the term being folded (use `DefaultFreeVarFolder` to 44 /// ignore/forbid these altogether) 45 /// - `InferenceFolder` -- folds existential `InferenceVar` instances 46 /// that appear in the term being folded (use 47 /// `DefaultInferenceFolder` to ignore/forbid these altogether) 48 /// - `PlaceholderFolder` -- folds universal `Placeholder` instances 49 /// that appear in the term being folded (use 50 /// `DefaultPlaceholderFolder` to ignore/forbid these altogether) 51 /// 52 /// To **apply** a folder, use the `Fold::fold_with` method, like so 53 /// 54 /// ```rust,ignore 55 /// let x = x.fold_with(&mut folder, 0); 56 /// ``` 57 pub trait Folder<I: Interner> { 58 /// The type this folder returns when folding fails. This is 59 /// commonly [`NoSolution`]. 60 type Error; 61 62 /// Creates a `dyn` value from this folder. Unfortunately, this 63 /// must be added manually to each impl of Folder; it permits the 64 /// default implements below to create a `&mut dyn Folder` from 65 /// `Self` without knowing what `Self` is (by invoking this 66 /// method). Effectively, this limits impls of `Folder` to types 67 /// for which we are able to create a dyn value (i.e., not `[T]` 68 /// types). as_dyn(&mut self) -> &mut dyn Folder<I, Error = Self::Error>69 fn as_dyn(&mut self) -> &mut dyn Folder<I, Error = Self::Error>; 70 71 /// Top-level callback: invoked for each `Ty<I>` that is 72 /// encountered when folding. By default, invokes 73 /// `super_fold_with`, which will in turn invoke the more 74 /// specialized folding methods below, like `fold_free_var_ty`. fold_ty(&mut self, ty: Ty<I>, outer_binder: DebruijnIndex) -> Result<Ty<I>, Self::Error>75 fn fold_ty(&mut self, ty: Ty<I>, outer_binder: DebruijnIndex) -> Result<Ty<I>, Self::Error> { 76 ty.super_fold_with(self.as_dyn(), outer_binder) 77 } 78 79 /// Top-level callback: invoked for each `Lifetime<I>` that is 80 /// encountered when folding. By default, invokes 81 /// `super_fold_with`, which will in turn invoke the more 82 /// specialized folding methods below, like `fold_free_var_lifetime`. fold_lifetime( &mut self, lifetime: Lifetime<I>, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>83 fn fold_lifetime( 84 &mut self, 85 lifetime: Lifetime<I>, 86 outer_binder: DebruijnIndex, 87 ) -> Result<Lifetime<I>, Self::Error> { 88 lifetime.super_fold_with(self.as_dyn(), outer_binder) 89 } 90 91 /// Top-level callback: invoked for each `Const<I>` that is 92 /// encountered when folding. By default, invokes 93 /// `super_fold_with`, which will in turn invoke the more 94 /// specialized folding methods below, like `fold_free_var_const`. fold_const( &mut self, constant: Const<I>, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>95 fn fold_const( 96 &mut self, 97 constant: Const<I>, 98 outer_binder: DebruijnIndex, 99 ) -> Result<Const<I>, Self::Error> { 100 constant.super_fold_with(self.as_dyn(), outer_binder) 101 } 102 103 /// Invoked for every program clause. By default, recursively folds the goals contents. fold_program_clause( &mut self, clause: ProgramClause<I>, outer_binder: DebruijnIndex, ) -> Result<ProgramClause<I>, Self::Error>104 fn fold_program_clause( 105 &mut self, 106 clause: ProgramClause<I>, 107 outer_binder: DebruijnIndex, 108 ) -> Result<ProgramClause<I>, Self::Error> { 109 clause.super_fold_with(self.as_dyn(), outer_binder) 110 } 111 112 /// Invoked for every goal. By default, recursively folds the goals contents. fold_goal( &mut self, goal: Goal<I>, outer_binder: DebruijnIndex, ) -> Result<Goal<I>, Self::Error>113 fn fold_goal( 114 &mut self, 115 goal: Goal<I>, 116 outer_binder: DebruijnIndex, 117 ) -> Result<Goal<I>, Self::Error> { 118 goal.super_fold_with(self.as_dyn(), outer_binder) 119 } 120 121 /// If overridden to return true, then folding will panic if a 122 /// free variable is encountered. This should be done if free 123 /// type/lifetime variables are not expected. forbid_free_vars(&self) -> bool124 fn forbid_free_vars(&self) -> bool { 125 false 126 } 127 128 /// Invoked for `TyKind::BoundVar` instances that are not bound 129 /// within the type being folded over: 130 /// 131 /// - `depth` is the depth of the `TyKind::BoundVar`; this has 132 /// been adjusted to account for binders in scope. 133 /// - `binders` is the number of binders in scope. 134 /// 135 /// This should return a type suitable for a context with 136 /// `binders` in scope. fold_free_var_ty( &mut self, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, Self::Error>137 fn fold_free_var_ty( 138 &mut self, 139 bound_var: BoundVar, 140 outer_binder: DebruijnIndex, 141 ) -> Result<Ty<I>, Self::Error> { 142 if self.forbid_free_vars() { 143 panic!( 144 "unexpected free variable with depth `{:?}` with outer binder {:?}", 145 bound_var, outer_binder 146 ) 147 } else { 148 let bound_var = bound_var.shifted_in_from(outer_binder); 149 Ok(TyKind::<I>::BoundVar(bound_var).intern(self.interner())) 150 } 151 } 152 153 /// As `fold_free_var_ty`, but for lifetimes. fold_free_var_lifetime( &mut self, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>154 fn fold_free_var_lifetime( 155 &mut self, 156 bound_var: BoundVar, 157 outer_binder: DebruijnIndex, 158 ) -> Result<Lifetime<I>, Self::Error> { 159 if self.forbid_free_vars() { 160 panic!( 161 "unexpected free variable with depth `{:?}` with outer binder {:?}", 162 bound_var, outer_binder 163 ) 164 } else { 165 let bound_var = bound_var.shifted_in_from(outer_binder); 166 Ok(LifetimeData::<I>::BoundVar(bound_var).intern(self.interner())) 167 } 168 } 169 170 /// As `fold_free_var_ty`, but for constants. fold_free_var_const( &mut self, ty: Ty<I>, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>171 fn fold_free_var_const( 172 &mut self, 173 ty: Ty<I>, 174 bound_var: BoundVar, 175 outer_binder: DebruijnIndex, 176 ) -> Result<Const<I>, Self::Error> { 177 if self.forbid_free_vars() { 178 panic!( 179 "unexpected free variable with depth `{:?}` with outer binder {:?}", 180 bound_var, outer_binder 181 ) 182 } else { 183 let bound_var = bound_var.shifted_in_from(outer_binder); 184 Ok(ConstData { 185 ty: ty.clone().fold_with(self.as_dyn(), outer_binder)?, 186 value: ConstValue::<I>::BoundVar(bound_var), 187 } 188 .intern(self.interner())) 189 } 190 } 191 192 /// If overridden to return true, we will panic when a free 193 /// placeholder type/lifetime/const is encountered. forbid_free_placeholders(&self) -> bool194 fn forbid_free_placeholders(&self) -> bool { 195 false 196 } 197 198 /// Invoked for each occurrence of a placeholder type; these are 199 /// used when we instantiate binders universally. Returns a type 200 /// to use instead, which should be suitably shifted to account 201 /// for `binders`. 202 /// 203 /// - `universe` is the universe of the `TypeName::ForAll` that was found 204 /// - `binders` is the number of binders in scope 205 #[allow(unused_variables)] fold_free_placeholder_ty( &mut self, universe: PlaceholderIndex, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, Self::Error>206 fn fold_free_placeholder_ty( 207 &mut self, 208 universe: PlaceholderIndex, 209 outer_binder: DebruijnIndex, 210 ) -> Result<Ty<I>, Self::Error> { 211 if self.forbid_free_placeholders() { 212 panic!("unexpected placeholder type `{:?}`", universe) 213 } else { 214 Ok(universe.to_ty::<I>(self.interner())) 215 } 216 } 217 218 /// As with `fold_free_placeholder_ty`, but for lifetimes. 219 #[allow(unused_variables)] fold_free_placeholder_lifetime( &mut self, universe: PlaceholderIndex, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>220 fn fold_free_placeholder_lifetime( 221 &mut self, 222 universe: PlaceholderIndex, 223 outer_binder: DebruijnIndex, 224 ) -> Result<Lifetime<I>, Self::Error> { 225 if self.forbid_free_placeholders() { 226 panic!("unexpected placeholder lifetime `{:?}`", universe) 227 } else { 228 Ok(universe.to_lifetime(self.interner())) 229 } 230 } 231 232 /// As with `fold_free_placeholder_ty`, but for constants. 233 #[allow(unused_variables)] fold_free_placeholder_const( &mut self, ty: Ty<I>, universe: PlaceholderIndex, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>234 fn fold_free_placeholder_const( 235 &mut self, 236 ty: Ty<I>, 237 universe: PlaceholderIndex, 238 outer_binder: DebruijnIndex, 239 ) -> Result<Const<I>, Self::Error> { 240 if self.forbid_free_placeholders() { 241 panic!("unexpected placeholder const `{:?}`", universe) 242 } else { 243 Ok(universe.to_const(self.interner(), ty.fold_with(self.as_dyn(), outer_binder)?)) 244 } 245 } 246 247 /// If overridden to return true, inference variables will trigger 248 /// panics when folded. Used when inference variables are 249 /// unexpected. forbid_inference_vars(&self) -> bool250 fn forbid_inference_vars(&self) -> bool { 251 false 252 } 253 254 /// Invoked for each occurrence of a inference type; these are 255 /// used when we instantiate binders universally. Returns a type 256 /// to use instead, which should be suitably shifted to account 257 /// for `binders`. 258 /// 259 /// - `universe` is the universe of the `TypeName::ForAll` that was found 260 /// - `binders` is the number of binders in scope 261 #[allow(unused_variables)] fold_inference_ty( &mut self, var: InferenceVar, kind: TyVariableKind, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, Self::Error>262 fn fold_inference_ty( 263 &mut self, 264 var: InferenceVar, 265 kind: TyVariableKind, 266 outer_binder: DebruijnIndex, 267 ) -> Result<Ty<I>, Self::Error> { 268 if self.forbid_inference_vars() { 269 panic!("unexpected inference type `{:?}`", var) 270 } else { 271 Ok(var.to_ty(self.interner(), kind)) 272 } 273 } 274 275 /// As with `fold_inference_ty`, but for lifetimes. 276 #[allow(unused_variables)] fold_inference_lifetime( &mut self, var: InferenceVar, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, Self::Error>277 fn fold_inference_lifetime( 278 &mut self, 279 var: InferenceVar, 280 outer_binder: DebruijnIndex, 281 ) -> Result<Lifetime<I>, Self::Error> { 282 if self.forbid_inference_vars() { 283 panic!("unexpected inference lifetime `'{:?}`", var) 284 } else { 285 Ok(var.to_lifetime(self.interner())) 286 } 287 } 288 289 /// As with `fold_inference_ty`, but for constants. 290 #[allow(unused_variables)] fold_inference_const( &mut self, ty: Ty<I>, var: InferenceVar, outer_binder: DebruijnIndex, ) -> Result<Const<I>, Self::Error>291 fn fold_inference_const( 292 &mut self, 293 ty: Ty<I>, 294 var: InferenceVar, 295 outer_binder: DebruijnIndex, 296 ) -> Result<Const<I>, Self::Error> { 297 if self.forbid_inference_vars() { 298 panic!("unexpected inference const `{:?}`", var) 299 } else { 300 Ok(var.to_const(self.interner(), ty.fold_with(self.as_dyn(), outer_binder)?)) 301 } 302 } 303 304 /// Gets the interner that is being folded from. interner(&self) -> I305 fn interner(&self) -> I; 306 } 307 308 /// Applies the given `Folder` to a value, producing a folded result 309 /// of type `Self::Result`. The result type is typically the same as 310 /// the source type, but in some cases we convert from borrowed 311 /// to owned as well (e.g., the folder for `&T` will fold to a fresh 312 /// `T`; well, actually `T::Result`). 313 pub trait Fold<I: Interner>: Debug { 314 /// The type of value that will be produced once folding is done. 315 /// Typically this is `Self`, unless `Self` contains borrowed 316 /// values, in which case owned values are produced (for example, 317 /// one can fold over a `&T` value where `T: Fold`, in which case 318 /// you get back a `T`, not a `&T`). 319 type Result; 320 321 /// Apply the given folder `folder` to `self`; `binders` is the 322 /// number of binders that are in scope when beginning the 323 /// folder. Typically `binders` starts as 0, but is adjusted when 324 /// we encounter `Binders<T>` in the IR or other similar 325 /// constructs. fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>326 fn fold_with<E>( 327 self, 328 folder: &mut dyn Folder<I, Error = E>, 329 outer_binder: DebruijnIndex, 330 ) -> Result<Self::Result, E>; 331 } 332 333 /// For types where "fold" invokes a callback on the `Folder`, the 334 /// `SuperFold` trait captures the recursive behavior that folds all 335 /// the contents of the type. 336 pub trait SuperFold<I: Interner>: Fold<I> { 337 /// Recursively folds the value. super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>338 fn super_fold_with<E>( 339 self, 340 folder: &mut dyn Folder<I, Error = E>, 341 outer_binder: DebruijnIndex, 342 ) -> Result<Self::Result, E>; 343 } 344 345 /// "Folding" a type invokes the `fold_ty` method on the folder; this 346 /// usually (in turn) invokes `super_fold_ty` to fold the individual 347 /// parts. 348 impl<I: Interner> Fold<I> for Ty<I> { 349 type Result = Ty<I>; 350 fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>351 fn fold_with<E>( 352 self, 353 folder: &mut dyn Folder<I, Error = E>, 354 outer_binder: DebruijnIndex, 355 ) -> Result<Self::Result, E> { 356 folder.fold_ty(self, outer_binder) 357 } 358 } 359 360 /// "Super fold" for a type invokes te more detailed callbacks on the type 361 impl<I> SuperFold<I> for Ty<I> 362 where 363 I: Interner, 364 { super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Ty<I>, E>365 fn super_fold_with<E>( 366 self, 367 folder: &mut dyn Folder<I, Error = E>, 368 outer_binder: DebruijnIndex, 369 ) -> Result<Ty<I>, E> { 370 let interner = folder.interner(); 371 Ok(match self.kind(interner) { 372 TyKind::BoundVar(bound_var) => { 373 if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) { 374 // This variable was bound outside of the binders 375 // that we have traversed during folding; 376 // therefore, it is free. Let the folder have a 377 // crack at it. 378 folder.fold_free_var_ty(bound_var1, outer_binder)? 379 } else { 380 // This variable was bound within the binders that 381 // we folded over, so just return a bound 382 // variable. 383 self 384 } 385 } 386 TyKind::Dyn(clauses) => TyKind::Dyn(clauses.clone().fold_with(folder, outer_binder)?) 387 .intern(folder.interner()), 388 TyKind::InferenceVar(var, kind) => { 389 folder.fold_inference_ty(*var, *kind, outer_binder)? 390 } 391 TyKind::Placeholder(ui) => folder.fold_free_placeholder_ty(*ui, outer_binder)?, 392 TyKind::Alias(proj) => TyKind::Alias(proj.clone().fold_with(folder, outer_binder)?) 393 .intern(folder.interner()), 394 TyKind::Function(fun) => TyKind::Function(fun.clone().fold_with(folder, outer_binder)?) 395 .intern(folder.interner()), 396 TyKind::Adt(id, substitution) => TyKind::Adt( 397 id.fold_with(folder, outer_binder)?, 398 substitution.clone().fold_with(folder, outer_binder)?, 399 ) 400 .intern(folder.interner()), 401 TyKind::AssociatedType(assoc_ty, substitution) => TyKind::AssociatedType( 402 assoc_ty.fold_with(folder, outer_binder)?, 403 substitution.clone().fold_with(folder, outer_binder)?, 404 ) 405 .intern(folder.interner()), 406 TyKind::Scalar(scalar) => { 407 TyKind::Scalar(scalar.fold_with(folder, outer_binder)?).intern(folder.interner()) 408 } 409 TyKind::Str => TyKind::Str.intern(folder.interner()), 410 TyKind::Tuple(arity, substitution) => TyKind::Tuple( 411 *arity, 412 substitution.clone().fold_with(folder, outer_binder)?, 413 ) 414 .intern(folder.interner()), 415 TyKind::OpaqueType(opaque_ty, substitution) => TyKind::OpaqueType( 416 opaque_ty.fold_with(folder, outer_binder)?, 417 substitution.clone().fold_with(folder, outer_binder)?, 418 ) 419 .intern(folder.interner()), 420 TyKind::Slice(substitution) => { 421 TyKind::Slice(substitution.clone().fold_with(folder, outer_binder)?) 422 .intern(folder.interner()) 423 } 424 TyKind::FnDef(fn_def, substitution) => TyKind::FnDef( 425 fn_def.fold_with(folder, outer_binder)?, 426 substitution.clone().fold_with(folder, outer_binder)?, 427 ) 428 .intern(folder.interner()), 429 TyKind::Ref(mutability, lifetime, ty) => TyKind::Ref( 430 mutability.fold_with(folder, outer_binder)?, 431 lifetime.clone().fold_with(folder, outer_binder)?, 432 ty.clone().fold_with(folder, outer_binder)?, 433 ) 434 .intern(folder.interner()), 435 TyKind::Raw(mutability, ty) => TyKind::Raw( 436 mutability.fold_with(folder, outer_binder)?, 437 ty.clone().fold_with(folder, outer_binder)?, 438 ) 439 .intern(folder.interner()), 440 TyKind::Never => TyKind::Never.intern(folder.interner()), 441 TyKind::Array(ty, const_) => TyKind::Array( 442 ty.clone().fold_with(folder, outer_binder)?, 443 const_.clone().fold_with(folder, outer_binder)?, 444 ) 445 .intern(folder.interner()), 446 TyKind::Closure(id, substitution) => TyKind::Closure( 447 id.fold_with(folder, outer_binder)?, 448 substitution.clone().fold_with(folder, outer_binder)?, 449 ) 450 .intern(folder.interner()), 451 TyKind::Generator(id, substitution) => TyKind::Generator( 452 id.fold_with(folder, outer_binder)?, 453 substitution.clone().fold_with(folder, outer_binder)?, 454 ) 455 .intern(folder.interner()), 456 TyKind::GeneratorWitness(id, substitution) => TyKind::GeneratorWitness( 457 id.fold_with(folder, outer_binder)?, 458 substitution.clone().fold_with(folder, outer_binder)?, 459 ) 460 .intern(folder.interner()), 461 TyKind::Foreign(id) => { 462 TyKind::Foreign(id.fold_with(folder, outer_binder)?).intern(folder.interner()) 463 } 464 TyKind::Error => TyKind::Error.intern(folder.interner()), 465 }) 466 } 467 } 468 469 /// "Folding" a lifetime invokes the `fold_lifetime` method on the folder; this 470 /// usually (in turn) invokes `super_fold_lifetime` to fold the individual 471 /// parts. 472 impl<I: Interner> Fold<I> for Lifetime<I> { 473 type Result = Lifetime<I>; 474 fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>475 fn fold_with<E>( 476 self, 477 folder: &mut dyn Folder<I, Error = E>, 478 outer_binder: DebruijnIndex, 479 ) -> Result<Self::Result, E> { 480 folder.fold_lifetime(self, outer_binder) 481 } 482 } 483 484 impl<I> SuperFold<I> for Lifetime<I> 485 where 486 I: Interner, 487 { super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Lifetime<I>, E>488 fn super_fold_with<E>( 489 self, 490 folder: &mut dyn Folder<I, Error = E>, 491 outer_binder: DebruijnIndex, 492 ) -> Result<Lifetime<I>, E> { 493 let interner = folder.interner(); 494 match self.data(interner) { 495 LifetimeData::BoundVar(bound_var) => { 496 if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) { 497 // This variable was bound outside of the binders 498 // that we have traversed during folding; 499 // therefore, it is free. Let the folder have a 500 // crack at it. 501 folder.fold_free_var_lifetime(bound_var1, outer_binder) 502 } else { 503 // This variable was bound within the binders that 504 // we folded over, so just return a bound 505 // variable. 506 Ok(self) 507 } 508 } 509 LifetimeData::InferenceVar(var) => folder.fold_inference_lifetime(*var, outer_binder), 510 LifetimeData::Placeholder(universe) => { 511 folder.fold_free_placeholder_lifetime(*universe, outer_binder) 512 } 513 LifetimeData::Static => Ok(LifetimeData::<I>::Static.intern(folder.interner())), 514 LifetimeData::Empty(ui) => Ok(LifetimeData::<I>::Empty(*ui).intern(folder.interner())), 515 LifetimeData::Erased => Ok(LifetimeData::<I>::Erased.intern(folder.interner())), 516 LifetimeData::Phantom(void, ..) => match *void {}, 517 } 518 } 519 } 520 521 /// "Folding" a const invokes the `fold_const` method on the folder; this 522 /// usually (in turn) invokes `super_fold_const` to fold the individual 523 /// parts. 524 impl<I: Interner> Fold<I> for Const<I> { 525 type Result = Const<I>; 526 fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>527 fn fold_with<E>( 528 self, 529 folder: &mut dyn Folder<I, Error = E>, 530 outer_binder: DebruijnIndex, 531 ) -> Result<Self::Result, E> { 532 folder.fold_const(self, outer_binder) 533 } 534 } 535 536 impl<I> SuperFold<I> for Const<I> 537 where 538 I: Interner, 539 { super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Const<I>, E>540 fn super_fold_with<E>( 541 self, 542 folder: &mut dyn Folder<I, Error = E>, 543 outer_binder: DebruijnIndex, 544 ) -> Result<Const<I>, E> { 545 let interner = folder.interner(); 546 let ConstData { ref ty, ref value } = self.data(interner); 547 let mut fold_ty = || ty.clone().fold_with(folder, outer_binder); 548 match value { 549 ConstValue::BoundVar(bound_var) => { 550 if let Some(bound_var1) = bound_var.shifted_out_to(outer_binder) { 551 folder.fold_free_var_const(ty.clone(), bound_var1, outer_binder) 552 } else { 553 Ok(self) 554 } 555 } 556 ConstValue::InferenceVar(var) => { 557 folder.fold_inference_const(ty.clone(), *var, outer_binder) 558 } 559 ConstValue::Placeholder(universe) => { 560 folder.fold_free_placeholder_const(ty.clone(), *universe, outer_binder) 561 } 562 ConstValue::Concrete(ev) => Ok(ConstData { 563 ty: fold_ty()?, 564 value: ConstValue::Concrete(ConcreteConst { 565 interned: ev.interned.clone(), 566 }), 567 } 568 .intern(folder.interner())), 569 } 570 } 571 } 572 573 /// Folding a goal invokes the `fold_goal` callback (which will, by 574 /// default, invoke super-fold). 575 impl<I: Interner> Fold<I> for Goal<I> { 576 type Result = Goal<I>; 577 fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>578 fn fold_with<E>( 579 self, 580 folder: &mut dyn Folder<I, Error = E>, 581 outer_binder: DebruijnIndex, 582 ) -> Result<Self::Result, E> { 583 folder.fold_goal(self, outer_binder) 584 } 585 } 586 587 /// Superfold folds recursively. 588 impl<I: Interner> SuperFold<I> for Goal<I> { super_fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>589 fn super_fold_with<E>( 590 self, 591 folder: &mut dyn Folder<I, Error = E>, 592 outer_binder: DebruijnIndex, 593 ) -> Result<Self::Result, E> { 594 let interner = folder.interner(); 595 Ok(Goal::new( 596 interner, 597 self.data(interner) 598 .clone() 599 .fold_with(folder, outer_binder)?, 600 )) 601 } 602 } 603 604 /// Folding a program clause invokes the `fold_program_clause` 605 /// callback on the folder (which will, by default, invoke the 606 /// `super_fold_with` method on the program clause). 607 impl<I: Interner> Fold<I> for ProgramClause<I> { 608 type Result = ProgramClause<I>; 609 fold_with<E>( self, folder: &mut dyn Folder<I, Error = E>, outer_binder: DebruijnIndex, ) -> Result<Self::Result, E>610 fn fold_with<E>( 611 self, 612 folder: &mut dyn Folder<I, Error = E>, 613 outer_binder: DebruijnIndex, 614 ) -> Result<Self::Result, E> { 615 folder.fold_program_clause(self, outer_binder) 616 } 617 } 618