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