vendor/chalk-ir/src/visit.rs

   1 //! Traits for visiting bits of IR.
   2 use std::fmt::Debug;
   3 use std::ops::ControlFlow;
   4
   5 use crate::{
   6     BoundVar, Const, ConstValue, DebruijnIndex, DomainGoal, Goal, InferenceVar, Interner, Lifetime,
   7     LifetimeData, PlaceholderIndex, ProgramClause, Ty, TyKind, WhereClause,
   8 };
   9
  10 mod binder_impls;
  11 mod boring_impls;
  12 pub mod visitors;
  13
  14 pub use visitors::VisitExt;
  15
  16 /// Unwraps a `ControlFlow` or propagates its `Break` value.
  17 /// This replaces the `Try` implementation that would be used
  18 /// with `std::ops::ControlFlow`.
  19 #[macro_export]
  20 macro_rules! try_break {
  21     ($expr:expr) => {
  22         match $expr {
  23             std::ops::ControlFlow::Continue(c) => c,
  24             std::ops::ControlFlow::Break(b) => return std::ops::ControlFlow::Break(b),
  25         }
  26     };
  27 }
  28
  29 /// A "visitor" recursively folds some term -- that is, some bit of IR,
  30 /// such as a `Goal`, and computes a value as a result.
  31 ///
  32 ///
  33 /// To **apply** a visitor, use the `Visit::visit_with` method, like so
  34 ///
  35 /// ```rust,ignore
  36 /// let result = x.visit_with(&mut visitor, 0);
  37 /// ```
  38 pub trait Visitor<I: Interner> {
  39     /// The "break type" of the visitor, often `()`. It represents the result
  40     /// the visitor yields when it stops visiting.
  41     type BreakTy;
  42
  43     /// Creates a `dyn` value from this visitor. Unfortunately, this
  44     /// must be added manually to each impl of visitor; it permits the
  45     /// default implements below to create a `&mut dyn Visitor` from
  46     /// `Self` without knowing what `Self` is (by invoking this
  47     /// method). Effectively, this limits impls of `visitor` to types
  48     /// for which we are able to create a dyn value (i.e., not `[T]`
  49     /// types).
  50     fn as_dyn(&mut self) -> &mut dyn Visitor<I, BreakTy = Self::BreakTy>;
  51
  52     /// Top-level callback: invoked for each `Ty<I>` that is
  53     /// encountered when visiting. By default, invokes
  54     /// `super_visit_with`, which will in turn invoke the more
  55     /// specialized visiting methods below, like `visit_free_var`.
  56     fn visit_ty(&mut self, ty: &Ty<I>, outer_binder: DebruijnIndex) -> ControlFlow<Self::BreakTy> {
  57         ty.super_visit_with(self.as_dyn(), outer_binder)
  58     }
  59
  60     /// Top-level callback: invoked for each `Lifetime<I>` that is
  61     /// encountered when visiting. By default, invokes
  62     /// `super_visit_with`, which will in turn invoke the more
  63     /// specialized visiting methods below, like `visit_free_var`.
  64     fn visit_lifetime(
  65         &mut self,
  66         lifetime: &Lifetime<I>,
  67         outer_binder: DebruijnIndex,
  68     ) -> ControlFlow<Self::BreakTy> {
  69         lifetime.super_visit_with(self.as_dyn(), outer_binder)
  70     }
  71
  72     /// Top-level callback: invoked for each `Const<I>` that is
  73     /// encountered when visiting. By default, invokes
  74     /// `super_visit_with`, which will in turn invoke the more
  75     /// specialized visiting methods below, like `visit_free_var`.
  76     fn visit_const(
  77         &mut self,
  78         constant: &Const<I>,
  79         outer_binder: DebruijnIndex,
  80     ) -> ControlFlow<Self::BreakTy> {
  81         constant.super_visit_with(self.as_dyn(), outer_binder)
  82     }
  83
  84     /// Invoked for every program clause. By default, recursively visits the goals contents.
  85     fn visit_program_clause(
  86         &mut self,
  87         clause: &ProgramClause<I>,
  88         outer_binder: DebruijnIndex,
  89     ) -> ControlFlow<Self::BreakTy> {
  90         clause.super_visit_with(self.as_dyn(), outer_binder)
  91     }
  92
  93     /// Invoked for every goal. By default, recursively visits the goals contents.
  94     fn visit_goal(
  95         &mut self,
  96         goal: &Goal<I>,
  97         outer_binder: DebruijnIndex,
  98     ) -> ControlFlow<Self::BreakTy> {
  99         goal.super_visit_with(self.as_dyn(), outer_binder)
 100     }
 101
 102     /// Invoked for each domain goal.
 103     fn visit_domain_goal(
 104         &mut self,
 105         domain_goal: &DomainGoal<I>,
 106         outer_binder: DebruijnIndex,
 107     ) -> ControlFlow<Self::BreakTy> {
 108         domain_goal.super_visit_with(self.as_dyn(), outer_binder)
 109     }
 110
 111     /// If overridden to return true, then visiting will panic if a
 112     /// free variable is encountered. This should be done if free
 113     /// type/lifetime/const variables are not expected.
 114     fn forbid_free_vars(&self) -> bool {
 115         false
 116     }
 117
 118     /// Invoked for `BoundVar` instances that are not bound
 119     /// within the type being visited over:
 120     fn visit_free_var(
 121         &mut self,
 122         bound_var: BoundVar,
 123         outer_binder: DebruijnIndex,
 124     ) -> ControlFlow<Self::BreakTy> {
 125         if self.forbid_free_vars() {
 126             panic!(
 127                 "unexpected free variable `{:?}` with outer binder {:?}",
 128                 bound_var, outer_binder
 129             )
 130         } else {
 131             ControlFlow::Continue(())
 132         }
 133     }
 134
 135     /// If overridden to return true, we will panic when a free
 136     /// placeholder type/lifetime is encountered.
 137     fn forbid_free_placeholders(&self) -> bool {
 138         false
 139     }
 140
 141     /// Invoked for each occurrence of a placeholder type; these are
 142     /// used when we instantiate binders universally.
 143     fn visit_free_placeholder(
 144         &mut self,
 145         universe: PlaceholderIndex,
 146         _outer_binder: DebruijnIndex,
 147     ) -> ControlFlow<Self::BreakTy> {
 148         if self.forbid_free_placeholders() {
 149             panic!("unexpected placeholder type `{:?}`", universe)
 150         } else {
 151             ControlFlow::Continue(())
 152         }
 153     }
 154
 155     /// Invoked for each where clause.
 156     fn visit_where_clause(
 157         &mut self,
 158         where_clause: &WhereClause<I>,
 159         outer_binder: DebruijnIndex,
 160     ) -> ControlFlow<Self::BreakTy> {
 161         where_clause.super_visit_with(self.as_dyn(), outer_binder)
 162     }
 163
 164     /// If overridden to return true, inference variables will trigger
 165     /// panics when visited. Used when inference variables are
 166     /// unexpected.
 167     fn forbid_inference_vars(&self) -> bool {
 168         false
 169     }
 170
 171     /// Invoked for each occurrence of a inference type; these are
 172     /// used when we instantiate binders universally.
 173     fn visit_inference_var(
 174         &mut self,
 175         var: InferenceVar,
 176         _outer_binder: DebruijnIndex,
 177     ) -> ControlFlow<Self::BreakTy> {
 178         if self.forbid_inference_vars() {
 179             panic!("unexpected inference type `{:?}`", var)
 180         } else {
 181             ControlFlow::Continue(())
 182         }
 183     }
 184
 185     /// Gets the visitor's interner.
 186     fn interner(&self) -> I;
 187 }
 188
 189 /// Applies the given `visitor` to a value, producing a visited result
 190 /// of type `Visitor::Result`.
 191 pub trait Visit<I: Interner>: Debug {
 192     /// Apply the given visitor `visitor` to `self`; `binders` is the
 193     /// number of binders that are in scope when beginning the
 194     /// visitor. Typically `binders` starts as 0, but is adjusted when
 195     /// we encounter `Binders<T>` in the IR or other similar
 196     /// constructs.
 197     fn visit_with<B>(
 198         &self,
 199         visitor: &mut dyn Visitor<I, BreakTy = B>,
 200         outer_binder: DebruijnIndex,
 201     ) -> ControlFlow<B>;
 202 }
 203
 204 /// For types where "visit" invokes a callback on the `visitor`, the
 205 /// `SuperVisit` trait captures the recursive behavior that visits all
 206 /// the contents of the type.
 207 pub trait SuperVisit<I: Interner>: Visit<I> {
 208     /// Recursively visits the type contents.
 209     fn super_visit_with<B>(
 210         &self,
 211         visitor: &mut dyn Visitor<I, BreakTy = B>,
 212         outer_binder: DebruijnIndex,
 213     ) -> ControlFlow<B>;
 214 }
 215
 216 /// "visiting" a type invokes the `visit_ty` method on the visitor; this
 217 /// usually (in turn) invokes `super_visit_ty` to visit the individual
 218 /// parts.
 219 impl<I: Interner> Visit<I> for Ty<I> {
 220     fn visit_with<B>(
 221         &self,
 222         visitor: &mut dyn Visitor<I, BreakTy = B>,
 223         outer_binder: DebruijnIndex,
 224     ) -> ControlFlow<B> {
 225         visitor.visit_ty(self, outer_binder)
 226     }
 227 }
 228
 229 /// "Super visit" for a type invokes the more detailed callbacks on the type
 230 impl<I> SuperVisit<I> for Ty<I>
 231 where
 232     I: Interner,
 233 {
 234     fn super_visit_with<B>(
 235         &self,
 236         visitor: &mut dyn Visitor<I, BreakTy = B>,
 237         outer_binder: DebruijnIndex,
 238     ) -> ControlFlow<B> {
 239         let interner = visitor.interner();
 240         match self.kind(interner) {
 241             TyKind::BoundVar(bound_var) => {
 242                 if let Some(_) = bound_var.shifted_out_to(outer_binder) {
 243                     visitor.visit_free_var(*bound_var, outer_binder)
 244                 } else {
 245                     ControlFlow::Continue(())
 246                 }
 247             }
 248             TyKind::Dyn(clauses) => clauses.visit_with(visitor, outer_binder),
 249             TyKind::InferenceVar(var, _) => visitor.visit_inference_var(*var, outer_binder),
 250             TyKind::Placeholder(ui) => visitor.visit_free_placeholder(*ui, outer_binder),
 251             TyKind::Alias(proj) => proj.visit_with(visitor, outer_binder),
 252             TyKind::Function(fun) => fun.visit_with(visitor, outer_binder),
 253             TyKind::Adt(_id, substitution) => substitution.visit_with(visitor, outer_binder),
 254             TyKind::AssociatedType(_assoc_ty, substitution) => {
 255                 substitution.visit_with(visitor, outer_binder)
 256             }
 257             TyKind::Scalar(scalar) => scalar.visit_with(visitor, outer_binder),
 258             TyKind::Str => ControlFlow::Continue(()),
 259             TyKind::Tuple(arity, substitution) => {
 260                 try_break!(arity.visit_with(visitor, outer_binder));
 261                 substitution.visit_with(visitor, outer_binder)
 262             }
 263             TyKind::OpaqueType(opaque_ty, substitution) => {
 264                 try_break!(opaque_ty.visit_with(visitor, outer_binder));
 265                 substitution.visit_with(visitor, outer_binder)
 266             }
 267             TyKind::Slice(substitution) => substitution.visit_with(visitor, outer_binder),
 268             TyKind::FnDef(fn_def, substitution) => {
 269                 try_break!(fn_def.visit_with(visitor, outer_binder));
 270                 substitution.visit_with(visitor, outer_binder)
 271             }
 272             TyKind::Ref(mutability, lifetime, ty) => {
 273                 try_break!(mutability.visit_with(visitor, outer_binder));
 274                 try_break!(lifetime.visit_with(visitor, outer_binder));
 275                 ty.visit_with(visitor, outer_binder)
 276             }
 277             TyKind::Raw(mutability, ty) => {
 278                 try_break!(mutability.visit_with(visitor, outer_binder));
 279                 ty.visit_with(visitor, outer_binder)
 280             }
 281             TyKind::Never => ControlFlow::Continue(()),
 282             TyKind::Array(ty, const_) => {
 283                 try_break!(ty.visit_with(visitor, outer_binder));
 284                 const_.visit_with(visitor, outer_binder)
 285             }
 286             TyKind::Closure(id, substitution) => {
 287                 try_break!(id.visit_with(visitor, outer_binder));
 288                 substitution.visit_with(visitor, outer_binder)
 289             }
 290             TyKind::Generator(generator, substitution) => {
 291                 try_break!(generator.visit_with(visitor, outer_binder));
 292                 substitution.visit_with(visitor, outer_binder)
 293             }
 294             TyKind::GeneratorWitness(witness, substitution) => {
 295                 try_break!(witness.visit_with(visitor, outer_binder));
 296                 substitution.visit_with(visitor, outer_binder)
 297             }
 298             TyKind::Foreign(foreign_ty) => foreign_ty.visit_with(visitor, outer_binder),
 299             TyKind::Error => ControlFlow::Continue(()),
 300         }
 301     }
 302 }
 303
 304 impl<I: Interner> Visit<I> for Lifetime<I> {
 305     fn visit_with<B>(
 306         &self,
 307         visitor: &mut dyn Visitor<I, BreakTy = B>,
 308         outer_binder: DebruijnIndex,
 309     ) -> ControlFlow<B> {
 310         visitor.visit_lifetime(self, outer_binder)
 311     }
 312 }
 313
 314 impl<I: Interner> SuperVisit<I> for Lifetime<I> {
 315     fn super_visit_with<B>(
 316         &self,
 317         visitor: &mut dyn Visitor<I, BreakTy = B>,
 318         outer_binder: DebruijnIndex,
 319     ) -> ControlFlow<B> {
 320         let interner = visitor.interner();
 321         match self.data(interner) {
 322             LifetimeData::BoundVar(bound_var) => {
 323                 if let Some(_) = bound_var.shifted_out_to(outer_binder) {
 324                     visitor.visit_free_var(*bound_var, outer_binder)
 325                 } else {
 326                     ControlFlow::Continue(())
 327                 }
 328             }
 329             LifetimeData::InferenceVar(var) => visitor.visit_inference_var(*var, outer_binder),
 330             LifetimeData::Placeholder(universe) => {
 331                 visitor.visit_free_placeholder(*universe, outer_binder)
 332             }
 333             LifetimeData::Static | LifetimeData::Empty(_) | LifetimeData::Erased => {
 334                 ControlFlow::Continue(())
 335             }
 336             LifetimeData::Phantom(void, ..) => match *void {},
 337         }
 338     }
 339 }
 340
 341 impl<I: Interner> Visit<I> for Const<I> {
 342     fn visit_with<B>(
 343         &self,
 344         visitor: &mut dyn Visitor<I, BreakTy = B>,
 345         outer_binder: DebruijnIndex,
 346     ) -> ControlFlow<B> {
 347         visitor.visit_const(self, outer_binder)
 348     }
 349 }
 350
 351 impl<I: Interner> SuperVisit<I> for Const<I> {
 352     fn super_visit_with<B>(
 353         &self,
 354         visitor: &mut dyn Visitor<I, BreakTy = B>,
 355         outer_binder: DebruijnIndex,
 356     ) -> ControlFlow<B> {
 357         let interner = visitor.interner();
 358         match &self.data(interner).value {
 359             ConstValue::BoundVar(bound_var) => {
 360                 if let Some(_) = bound_var.shifted_out_to(outer_binder) {
 361                     visitor.visit_free_var(*bound_var, outer_binder)
 362                 } else {
 363                     ControlFlow::Continue(())
 364                 }
 365             }
 366             ConstValue::InferenceVar(var) => visitor.visit_inference_var(*var, outer_binder),
 367             ConstValue::Placeholder(universe) => {
 368                 visitor.visit_free_placeholder(*universe, outer_binder)
 369             }
 370             ConstValue::Concrete(_) => ControlFlow::Continue(()),
 371         }
 372     }
 373 }
 374
 375 impl<I: Interner> Visit<I> for Goal<I> {
 376     fn visit_with<B>(
 377         &self,
 378         visitor: &mut dyn Visitor<I, BreakTy = B>,
 379         outer_binder: DebruijnIndex,
 380     ) -> ControlFlow<B> {
 381         visitor.visit_goal(self, outer_binder)
 382     }
 383 }
 384
 385 impl<I: Interner> SuperVisit<I> for Goal<I> {
 386     fn super_visit_with<B>(
 387         &self,
 388         visitor: &mut dyn Visitor<I, BreakTy = B>,
 389         outer_binder: DebruijnIndex,
 390     ) -> ControlFlow<B> {
 391         let interner = visitor.interner();
 392         self.data(interner).visit_with(visitor, outer_binder)
 393     }
 394 }
 395
 396 impl<I: Interner> Visit<I> for ProgramClause<I> {
 397     fn visit_with<B>(
 398         &self,
 399         visitor: &mut dyn Visitor<I, BreakTy = B>,
 400         outer_binder: DebruijnIndex,
 401     ) -> ControlFlow<B> {
 402         visitor.visit_program_clause(self, outer_binder)
 403     }
 404 }
 405
 406 impl<I: Interner> Visit<I> for WhereClause<I> {
 407     fn visit_with<B>(
 408         &self,
 409         visitor: &mut dyn Visitor<I, BreakTy = B>,
 410         outer_binder: DebruijnIndex,
 411     ) -> ControlFlow<B> {
 412         visitor.visit_where_clause(self, outer_binder)
 413     }
 414 }
 415
 416 impl<I: Interner> Visit<I> for DomainGoal<I> {
 417     fn visit_with<B>(
 418         &self,
 419         visitor: &mut dyn Visitor<I, BreakTy = B>,
 420         outer_binder: DebruijnIndex,
 421     ) -> ControlFlow<B> {
 422         visitor.visit_domain_goal(self, outer_binder)
 423     }
 424 }