gcc/rust/typecheck/rust-tyty-variance-analysis-private.h

   1 #ifndef RUST_TYTY_VARIANCE_ANALYSIS_PRIVATE_H
   2 #define RUST_TYTY_VARIANCE_ANALYSIS_PRIVATE_H
   3
   4 #include "rust-tyty-variance-analysis.h"
   5
   6 #include "rust-tyty-visitor.h"
   7
   8 namespace Rust {
   9 namespace TyTy {
  10 namespace VarianceAnalysis {
  11
  12 using SolutionIndex = uint32_t;
  13
  14 /** Term descibing variance relations. */
  15 struct Term
  16 {
  17   enum Kind : uint8_t
  18   {
  19     CONST,
  20     REF,
  21     TRANSFORM,
  22   };
  23
  24   Kind kind;
  25   union
  26   {
  27     struct
  28     {
  29       Term *lhs;
  30       Term *rhs;
  31     } transform;
  32     SolutionIndex ref;
  33     Variance const_val;
  34   };
  35
  36   Term () {}
  37
  38   Term (Variance variance) : kind (CONST), const_val (variance) {}
  39
  40   WARN_UNUSED_RESULT bool is_const () const { return kind == CONST; }
  41
  42   static Term make_ref (SolutionIndex index);
  43
  44   static Term make_transform (Term lhs, Term rhs);
  45 };
  46
  47 /** Variance constraint of a type parameter. */
  48 struct Constraint
  49 {
  50   SolutionIndex target_index;
  51   Term *term;
  52 };
  53
  54 /** Abstract variance visitor context. */
  55 template <typename VARIANCE> class VarianceVisitorCtx
  56 {
  57 public:
  58   virtual ~VarianceVisitorCtx () = default;
  59
  60   virtual void add_constraints_from_ty (BaseType *ty, VARIANCE variance) = 0;
  61   virtual void add_constraints_from_region (const Region &region,
  62                                             VARIANCE variance)
  63     = 0;
  64   void add_constraints_from_mutability (BaseType *type, Mutability mutability,
  65                                         VARIANCE variance)
  66   {
  67     switch (mutability)
  68       {
  69       case Mutability::Imm:
  70         return add_constraints_from_ty (type, variance);
  71       case Mutability::Mut:
  72         return add_constraints_from_ty (type, Variance::invariant ());
  73       }
  74   }
  75   virtual void
  76   add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
  77                                      VARIANCE variance, bool invariant_args)
  78     = 0;
  79   virtual void add_constrints_from_param (ParamType &param, VARIANCE variance)
  80     = 0;
  81   virtual VARIANCE contra (VARIANCE variance) = 0;
  82 };
  83
  84 template <typename VARIANCE> class VisitorBase final : public TyVisitor
  85 {
  86   VarianceVisitorCtx<VARIANCE> &ctx;
  87   VARIANCE variance;
  88
  89 public:
  90   VisitorBase (VarianceVisitorCtx<VARIANCE> &ctx, VARIANCE variance)
  91     : ctx (ctx), variance (variance)
  92   {}
  93
  94   void visit (BoolType &type) override {}
  95   void visit (CharType &type) override {}
  96   void visit (IntType &type) override {}
  97   void visit (UintType &type) override {}
  98   void visit (FloatType &type) override {}
  99   void visit (USizeType &type) override {}
 100   void visit (ISizeType &type) override {}
 101   void visit (StrType &type) override {}
 102   void visit (NeverType &type) override {}
 103
 104   void visit (ClosureType &type) override {}
 105   void visit (FnType &type) override
 106   {
 107     for (auto &region : type.get_used_arguments ().get_regions ())
 108       ctx.add_constraints_from_region (region, Variance::invariant ());
 109   }
 110
 111   void visit (ReferenceType &type) override
 112   {
 113     ctx.add_constraints_from_region (type.get_region (), variance);
 114     ctx.add_constraints_from_mutability (type.get_base (), type.mutability (),
 115                                          variance);
 116   }
 117   void visit (ArrayType &type) override
 118   {
 119     ctx.add_constraints_from_ty (type.get_element_type (), variance);
 120   }
 121   void visit (SliceType &type) override
 122   {
 123     ctx.add_constraints_from_ty (type.get_element_type (), variance);
 124   }
 125   void visit (PointerType &type) override
 126   {
 127     ctx.add_constraints_from_ty (type.get_base (), variance);
 128     ctx.add_constraints_from_mutability (type.get_base (), type.mutability (),
 129                                          variance);
 130   }
 131   void visit (TupleType &type) override
 132   {
 133     for (auto &elem : type.get_fields ())
 134       ctx.add_constraints_from_ty (elem.get_tyty (), variance);
 135   }
 136   void visit (ADTType &type) override
 137   {
 138     ctx.add_constraints_from_generic_args (type.get_orig_ref (), type, variance,
 139                                            false);
 140   }
 141   void visit (ProjectionType &type) override
 142   {
 143     ctx.add_constraints_from_generic_args (type.get_orig_ref (), type, variance,
 144                                            true);
 145   }
 146   void visit (ParamType &type) override
 147   {
 148     ctx.add_constrints_from_param (type, variance);
 149   }
 150   void visit (FnPtr &type) override
 151   {
 152     auto contra = ctx.contra (variance);
 153
 154     for (auto &param : type.get_params ())
 155       {
 156         ctx.add_constraints_from_ty (param.get_tyty (), contra);
 157       }
 158
 159     ctx.add_constraints_from_ty (type.get_return_type (), variance);
 160   }
 161
 162   void visit (ErrorType &type) override {}
 163
 164   void visit (PlaceholderType &type) override { rust_unreachable (); }
 165   void visit (InferType &type) override { rust_unreachable (); }
 166
 167   void visit (DynamicObjectType &type) override
 168   {
 169     // TODO
 170   }
 171 };
 172
 173 /** Per crate context for generic type variance analysis. */
 174 class GenericTyPerCrateCtx
 175 {
 176 public: // External API
 177   /** Add a type to context and process its variance constraints. */
 178   void process_type (ADTType &ty);
 179
 180   /**
 181    * Solve for all variance constraints and clear temporary data.
 182    *
 183    * Only keeps the results.
 184    */
 185   void solve ();
 186
 187   /** Prints solution debug output. To be called after solve. */
 188   void debug_print_solutions ();
 189
 190   tl::optional<SolutionIndex> lookup_type_index (HirId orig_ref);
 191
 192 public: // Module internal API
 193   /** Format term tree to string. */
 194   WARN_UNUSED_RESULT std::string to_string (const Term &term) const;
 195
 196   /** Formats as <type ident>`[`<param index>``]` */
 197   WARN_UNUSED_RESULT std::string to_string (SolutionIndex index) const;
 198
 199   /** Evaluate a variance relation expression (term tree). */
 200   Variance evaluate (Term *term);
 201
 202   std::vector<Variance> query_generic_variance (const ADTType &type);
 203
 204   std::vector<size_t> query_field_regions (const ADTType *parent,
 205                                            size_t variant_index,
 206                                            size_t field_index,
 207                                            const FreeRegions &parent_regions);
 208
 209   std::vector<Region> query_type_regions (BaseType *base);
 210
 211 public: // Data used by visitors.
 212   // This whole class is private, therfore members can be public.
 213
 214   /** Current solutions. Initiated to bivariant. */
 215   std::vector<Variance> solutions;
 216
 217   /** Constrains on solutions. Iteratively applied until fixpoint. */
 218   std::vector<Constraint> constraints;
 219
 220   /** Maps TyTy::orig_ref to an index of first solution for this type. */
 221   std::unordered_map<HirId, SolutionIndex> map_from_ty_orig_ref;
 222 };
 223
 224 /** Visitor context for generic type variance analysis used for processing of a
 225  * single type. */
 226 class GenericTyVisitorCtx : VarianceVisitorCtx<Term>
 227 {
 228   using Visitor = VisitorBase<Term>;
 229
 230 public:
 231   explicit GenericTyVisitorCtx (GenericTyPerCrateCtx &ctx) : ctx (ctx) {}
 232   /** Entry point: Add a type to context and process its variance constraints.
 233    */
 234   void process_type (ADTType &ty);
 235
 236 private:
 237   /** Resolve a type from a TyTy::ref. */
 238   SolutionIndex lookup_or_add_type (HirId hir_id);
 239
 240   /** Visit an inner type and add its constraints. */
 241   void add_constraints_from_ty (BaseType *ty, Term variance) override;
 242
 243   void add_constraint (SolutionIndex index, Term term);
 244
 245   void add_constraints_from_region (const Region &region, Term term) override;
 246
 247   void add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
 248                                           Term variance,
 249                                           bool invariant_args) override;
 250
 251   void add_constrints_from_param (ParamType &type, Term variance) override;
 252
 253   /** Construct a term for type in contravaraint position. */
 254   Term contra (Term variance) override;
 255
 256 private:
 257   GenericTyPerCrateCtx &ctx;
 258
 259 private: // Per type processing context
 260   /** Index of the solution first **lifetime param** for the current type. */
 261   SolutionIndex first_lifetime = 0;
 262
 263   /** Index of the solution first **type param** for the current type. */
 264   SolutionIndex first_type = 0;
 265
 266   /** Maps type param names to index among type params. */
 267   std::vector<std::string> param_names;
 268 };
 269
 270 /** Visitor context for basic type variance analysis. */
 271 class TyVisitorCtx : public VarianceVisitorCtx<Variance>
 272 {
 273 public:
 274   using Visitor = VisitorBase<Variance>;
 275
 276   TyVisitorCtx (GenericTyPerCrateCtx &ctx) : ctx (ctx) {}
 277
 278   std::vector<Variance> collect_variances (BaseType &ty)
 279   {
 280     add_constraints_from_ty (&ty, Variance::covariant ());
 281     return variances;
 282   }
 283
 284   std::vector<Region> collect_regions (BaseType &ty)
 285   {
 286     add_constraints_from_ty (&ty, Variance::covariant ());
 287     return regions;
 288   }
 289
 290   void add_constraints_from_ty (BaseType *ty, Variance variance) override;
 291   void add_constraints_from_region (const Region &region,
 292                                     Variance variance) override;
 293   void add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
 294                                           Variance variance,
 295                                           bool invariant_args) override;
 296   void add_constrints_from_param (ParamType &param, Variance variance) override
 297   {}
 298   Variance contra (Variance variance) override;
 299
 300 private:
 301   GenericTyPerCrateCtx &ctx;
 302   std::vector<Variance> variances;
 303   std::vector<Region> regions;
 304 };
 305
 306 /** Extracts regions of a field from regions of parent ADT. */
 307 class FieldVisitorCtx : public VarianceVisitorCtx<Variance>
 308 {
 309 public:
 310   using Visitor = VisitorBase<Variance>;
 311
 312   std::vector<size_t> collect_regions (BaseType &ty);
 313
 314   FieldVisitorCtx (GenericTyPerCrateCtx &ctx, const SubstitutionRef &subst,
 315                    const FreeRegions &parent_regions)
 316     : ctx (ctx), subst (subst), parent_regions (parent_regions)
 317   {}
 318
 319   void add_constraints_from_ty (BaseType *ty, Variance variance) override;
 320   void add_constraints_from_region (const Region &region,
 321                                     Variance variance) override;
 322   void add_constraints_from_generic_args (HirId ref, SubstitutionRef &subst,
 323                                           Variance variance,
 324                                           bool invariant_args) override{};
 325   void add_constrints_from_param (ParamType &param, Variance variance) override;
 326
 327   Variance contra (Variance variance) override
 328   {
 329     return Variance::transform (variance, Variance::contravariant ());
 330   }
 331
 332 private:
 333   GenericTyPerCrateCtx &ctx;
 334   const SubstitutionRef &subst;
 335   std::vector<size_t> regions;
 336   FreeRegions parent_regions;
 337   std::vector<size_t> type_param_ranges;
 338 };
 339
 340 } // namespace VarianceAnalysis
 341
 342 } // namespace TyTy
 343 } // namespace Rust
 344
 345 #endif // RUST_TYTY_VARIANCE_ANALYSIS_PRIVATE_H