vendor/chalk-ir/src/visit.rs

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