gcc/rust/typecheck/rust-tyty-cmp.h

   1 // Copyright (C) 2020-2025 Free Software Foundation, Inc.
   2
   3 // This file is part of GCC.
   4
   5 // GCC is free software; you can redistribute it and/or modify it under
   6 // the terms of the GNU General Public License as published by the Free
   7 // Software Foundation; either version 3, or (at your option) any later
   8 // version.
   9
  10 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13 // for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with GCC; see the file COPYING3.  If not see
  17 // <http://www.gnu.org/licenses/>.
  18
  19 #ifndef RUST_TYTY_CMP_H
  20 #define RUST_TYTY_CMP_H
  21
  22 #include "rust-diagnostics.h"
  23 #include "rust-tyty.h"
  24 #include "rust-tyty-visitor.h"
  25 #include "rust-hir-map.h"
  26 #include "rust-hir-type-check.h"
  27
  28 namespace Rust {
  29 namespace TyTy {
  30
  31 class BaseCmp : public TyConstVisitor
  32 {
  33 public:
  34   virtual bool can_eq (const BaseType *other)
  35   {
  36     if (other->get_kind () == TypeKind::PARAM)
  37       {
  38         const ParamType *p = static_cast<const ParamType *> (other);
  39         other = p->resolve ();
  40       }
  41     if (other->get_kind () == TypeKind::PLACEHOLDER)
  42       {
  43         const PlaceholderType *p = static_cast<const PlaceholderType *> (other);
  44         if (p->can_resolve ())
  45           {
  46             other = p->resolve ();
  47           }
  48       }
  49     if (other->get_kind () == TypeKind::PROJECTION)
  50       {
  51         const ProjectionType *p = static_cast<const ProjectionType *> (other);
  52         other = p->get ();
  53       }
  54
  55     other->accept_vis (*this);
  56     return ok;
  57   }
  58
  59   virtual void visit (const TupleType &type) override
  60   {
  61     ok = false;
  62
  63     if (emit_error_flag)
  64       {
  65         location_t ref_locus = mappings->lookup_location (type.get_ref ());
  66         location_t base_locus
  67           = mappings->lookup_location (get_base ()->get_ref ());
  68         rich_location r (line_table, ref_locus);
  69         r.add_range (base_locus);
  70         rust_error_at (r, "expected [%s] got [%s]",
  71                        get_base ()->as_string ().c_str (),
  72                        type.as_string ().c_str ());
  73       }
  74   }
  75
  76   virtual void visit (const ADTType &type) override
  77   {
  78     ok = false;
  79     if (emit_error_flag)
  80       {
  81         location_t ref_locus = mappings->lookup_location (type.get_ref ());
  82         location_t base_locus
  83           = mappings->lookup_location (get_base ()->get_ref ());
  84         rich_location r (line_table, ref_locus);
  85         r.add_range (base_locus);
  86         rust_error_at (r, "expected [%s] got [%s]",
  87                        get_base ()->as_string ().c_str (),
  88                        type.as_string ().c_str ());
  89       }
  90   }
  91
  92   virtual void visit (const InferType &type) override
  93   {
  94     ok = false;
  95     if (emit_error_flag)
  96       {
  97         location_t ref_locus = mappings->lookup_location (type.get_ref ());
  98         location_t base_locus
  99           = mappings->lookup_location (get_base ()->get_ref ());
 100         rich_location r (line_table, ref_locus);
 101         r.add_range (base_locus);
 102         rust_error_at (r, "expected [%s] got [%s]",
 103                        get_base ()->as_string ().c_str (),
 104                        type.as_string ().c_str ());
 105       }
 106   }
 107
 108   virtual void visit (const FnType &type) override
 109   {
 110     ok = false;
 111     if (emit_error_flag)
 112       {
 113         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 114         location_t base_locus
 115           = mappings->lookup_location (get_base ()->get_ref ());
 116         rich_location r (line_table, ref_locus);
 117         r.add_range (base_locus);
 118         rust_error_at (r, "expected [%s] got [%s]",
 119                        get_base ()->as_string ().c_str (),
 120                        type.as_string ().c_str ());
 121       }
 122   }
 123
 124   virtual void visit (const FnPtr &type) override
 125   {
 126     ok = false;
 127     if (emit_error_flag)
 128       {
 129         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 130         location_t base_locus
 131           = mappings->lookup_location (get_base ()->get_ref ());
 132         rich_location r (line_table, ref_locus);
 133         r.add_range (base_locus);
 134         rust_error_at (r, "expected [%s] got [%s]",
 135                        get_base ()->as_string ().c_str (),
 136                        type.as_string ().c_str ());
 137       }
 138   }
 139
 140   virtual void visit (const ArrayType &type) override
 141   {
 142     ok = false;
 143     if (emit_error_flag)
 144       {
 145         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 146         location_t base_locus
 147           = mappings->lookup_location (get_base ()->get_ref ());
 148         rich_location r (line_table, ref_locus);
 149         r.add_range (base_locus);
 150         rust_error_at (r, "expected [%s] got [%s]",
 151                        get_base ()->as_string ().c_str (),
 152                        type.as_string ().c_str ());
 153       }
 154   }
 155
 156   virtual void visit (const SliceType &type) override
 157   {
 158     ok = false;
 159     if (emit_error_flag)
 160       {
 161         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 162         location_t base_locus
 163           = mappings->lookup_location (get_base ()->get_ref ());
 164         rich_location r (line_table, ref_locus);
 165         r.add_range (base_locus);
 166         rust_error_at (r, "expected [%s] got [%s]",
 167                        get_base ()->as_string ().c_str (),
 168                        type.as_string ().c_str ());
 169       }
 170   }
 171
 172   virtual void visit (const BoolType &type) override
 173   {
 174     ok = false;
 175     if (emit_error_flag)
 176       {
 177         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 178         location_t base_locus
 179           = mappings->lookup_location (get_base ()->get_ref ());
 180         rich_location r (line_table, ref_locus);
 181         r.add_range (base_locus);
 182         rust_error_at (r, "expected [%s] got [%s]",
 183                        get_base ()->as_string ().c_str (),
 184                        type.as_string ().c_str ());
 185       }
 186   }
 187
 188   virtual void visit (const IntType &type) override
 189   {
 190     ok = false;
 191     if (emit_error_flag)
 192       {
 193         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 194         location_t base_locus
 195           = mappings->lookup_location (get_base ()->get_ref ());
 196         rich_location r (line_table, ref_locus);
 197         r.add_range (base_locus);
 198         rust_error_at (r, "expected [%s] got [%s]",
 199                        get_base ()->as_string ().c_str (),
 200                        type.as_string ().c_str ());
 201       }
 202   }
 203
 204   virtual void visit (const UintType &type) override
 205   {
 206     ok = false;
 207     if (emit_error_flag)
 208       {
 209         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 210         location_t base_locus
 211           = mappings->lookup_location (get_base ()->get_ref ());
 212         rich_location r (line_table, ref_locus);
 213         r.add_range (base_locus);
 214         rust_error_at (r, "expected [%s] got [%s]",
 215                        get_base ()->as_string ().c_str (),
 216                        type.as_string ().c_str ());
 217       }
 218   }
 219
 220   virtual void visit (const USizeType &type) override
 221   {
 222     ok = false;
 223     if (emit_error_flag)
 224       {
 225         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 226         location_t base_locus
 227           = mappings->lookup_location (get_base ()->get_ref ());
 228         rich_location r (line_table, ref_locus);
 229         r.add_range (base_locus);
 230         rust_error_at (r, "expected [%s] got [%s]",
 231                        get_base ()->as_string ().c_str (),
 232                        type.as_string ().c_str ());
 233       }
 234   }
 235
 236   virtual void visit (const ISizeType &type) override
 237   {
 238     ok = false;
 239     if (emit_error_flag)
 240       {
 241         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 242         location_t base_locus
 243           = mappings->lookup_location (get_base ()->get_ref ());
 244         rich_location r (line_table, ref_locus);
 245         r.add_range (base_locus);
 246         rust_error_at (r, "expected [%s] got [%s]",
 247                        get_base ()->as_string ().c_str (),
 248                        type.as_string ().c_str ());
 249       }
 250   }
 251
 252   virtual void visit (const FloatType &type) override
 253   {
 254     ok = false;
 255     if (emit_error_flag)
 256       {
 257         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 258         location_t base_locus
 259           = mappings->lookup_location (get_base ()->get_ref ());
 260         rich_location r (line_table, ref_locus);
 261         r.add_range (base_locus);
 262         rust_error_at (r, "expected [%s] got [%s]",
 263                        get_base ()->as_string ().c_str (),
 264                        type.as_string ().c_str ());
 265       }
 266   }
 267
 268   virtual void visit (const ErrorType &type) override
 269   {
 270     ok = false;
 271     if (emit_error_flag)
 272       {
 273         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 274         location_t base_locus
 275           = mappings->lookup_location (get_base ()->get_ref ());
 276         rich_location r (line_table, ref_locus);
 277         r.add_range (base_locus);
 278         rust_error_at (r, "expected [%s] got [%s]",
 279                        get_base ()->as_string ().c_str (),
 280                        type.as_string ().c_str ());
 281       }
 282   }
 283
 284   virtual void visit (const CharType &type) override
 285   {
 286     ok = false;
 287     if (emit_error_flag)
 288       {
 289         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 290         location_t base_locus
 291           = mappings->lookup_location (get_base ()->get_ref ());
 292         rich_location r (line_table, ref_locus);
 293         r.add_range (base_locus);
 294         rust_error_at (r, "expected [%s] got [%s]",
 295                        get_base ()->as_string ().c_str (),
 296                        type.as_string ().c_str ());
 297       }
 298   }
 299
 300   virtual void visit (const ReferenceType &type) override
 301   {
 302     ok = false;
 303     if (emit_error_flag)
 304       {
 305         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 306         location_t base_locus
 307           = mappings->lookup_location (get_base ()->get_ref ());
 308         rich_location r (line_table, ref_locus);
 309         r.add_range (base_locus);
 310         rust_error_at (r, "expected [%s] got [%s]",
 311                        get_base ()->as_string ().c_str (),
 312                        type.as_string ().c_str ());
 313       }
 314   }
 315
 316   virtual void visit (const PointerType &type) override
 317   {
 318     ok = false;
 319     if (emit_error_flag)
 320       {
 321         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 322         location_t base_locus
 323           = mappings->lookup_location (get_base ()->get_ref ());
 324         rich_location r (line_table, ref_locus);
 325         r.add_range (base_locus);
 326         rust_error_at (r, "expected [%s] got [%s]",
 327                        get_base ()->as_string ().c_str (),
 328                        type.as_string ().c_str ());
 329       }
 330   }
 331
 332   virtual void visit (const StrType &type) override
 333   {
 334     ok = false;
 335     if (emit_error_flag)
 336       {
 337         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 338         location_t base_locus
 339           = mappings->lookup_location (get_base ()->get_ref ());
 340         rich_location r (line_table, ref_locus);
 341         r.add_range (base_locus);
 342         rust_error_at (r, "expected [%s] got [%s]",
 343                        get_base ()->as_string ().c_str (),
 344                        type.as_string ().c_str ());
 345       }
 346   }
 347
 348   virtual void visit (const NeverType &type) override
 349   {
 350     ok = false;
 351     if (emit_error_flag)
 352       {
 353         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 354         location_t base_locus
 355           = mappings->lookup_location (get_base ()->get_ref ());
 356         rich_location r (line_table, ref_locus);
 357         r.add_range (base_locus);
 358         rust_error_at (r, "expected [%s] got [%s]",
 359                        get_base ()->as_string ().c_str (),
 360                        type.as_string ().c_str ());
 361       }
 362   }
 363
 364   virtual void visit (const ProjectionType &type) override
 365   {
 366     ok = false;
 367     if (emit_error_flag)
 368       {
 369         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 370         location_t base_locus
 371           = mappings->lookup_location (get_base ()->get_ref ());
 372         rich_location r (line_table, ref_locus);
 373         r.add_range (base_locus);
 374         rust_error_at (r, "expected [%s] got [%s]",
 375                        get_base ()->as_string ().c_str (),
 376                        type.as_string ().c_str ());
 377       }
 378   }
 379
 380   virtual void visit (const PlaceholderType &type) override
 381   {
 382     // it is ok for types to can eq to a placeholder
 383     ok = true;
 384   }
 385
 386   virtual void visit (const ParamType &type) override
 387   {
 388     ok = false;
 389     if (emit_error_flag)
 390       {
 391         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 392         location_t base_locus
 393           = mappings->lookup_location (get_base ()->get_ref ());
 394         rich_location r (line_table, ref_locus);
 395         r.add_range (base_locus);
 396         rust_error_at (r, "expected [%s] got [%s]",
 397                        get_base ()->as_string ().c_str (),
 398                        type.as_string ().c_str ());
 399       }
 400   }
 401
 402   virtual void visit (const DynamicObjectType &type) override
 403   {
 404     ok = false;
 405     if (emit_error_flag)
 406       {
 407         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 408         location_t base_locus
 409           = mappings->lookup_location (get_base ()->get_ref ());
 410         rich_location r (line_table, ref_locus);
 411         r.add_range (base_locus);
 412         rust_error_at (r, "expected [%s] got [%s]",
 413                        get_base ()->as_string ().c_str (),
 414                        type.as_string ().c_str ());
 415       }
 416   }
 417
 418   virtual void visit (const ClosureType &type) override
 419   {
 420     ok = false;
 421     if (emit_error_flag)
 422       {
 423         location_t ref_locus = mappings->lookup_location (type.get_ref ());
 424         location_t base_locus
 425           = mappings->lookup_location (get_base ()->get_ref ());
 426         rich_location r (line_table, ref_locus);
 427         r.add_range (base_locus);
 428         rust_error_at (r, "expected [%s] got [%s]",
 429                        get_base ()->as_string ().c_str (),
 430                        type.as_string ().c_str ());
 431       }
 432   }
 433
 434 protected:
 435   BaseCmp (const BaseType *base, bool emit_errors)
 436     : mappings (Analysis::Mappings::get ()),
 437       context (Resolver::TypeCheckContext::get ()), ok (false),
 438       emit_error_flag (emit_errors)
 439   {}
 440
 441   Analysis::Mappings *mappings;
 442   Resolver::TypeCheckContext *context;
 443
 444   bool ok;
 445   bool emit_error_flag;
 446
 447 private:
 448   /* Returns a pointer to the ty that created this rule. */
 449   virtual const BaseType *get_base () const = 0;
 450 };
 451
 452 class InferCmp : public BaseCmp
 453 {
 454   using Rust::TyTy::BaseCmp::visit;
 455
 456 public:
 457   InferCmp (const InferType *base, bool emit_errors)
 458     : BaseCmp (base, emit_errors), base (base)
 459   {}
 460
 461   void visit (const BoolType &type) override
 462   {
 463     bool is_valid
 464       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 465     if (is_valid)
 466       {
 467         ok = true;
 468         return;
 469       }
 470
 471     BaseCmp::visit (type);
 472   }
 473
 474   void visit (const IntType &type) override
 475   {
 476     bool is_valid
 477       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
 478         || (base->get_infer_kind ()
 479             == TyTy::InferType::InferTypeKind::INTEGRAL);
 480     if (is_valid)
 481       {
 482         ok = true;
 483         return;
 484       }
 485
 486     BaseCmp::visit (type);
 487   }
 488
 489   void visit (const UintType &type) override
 490   {
 491     bool is_valid
 492       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
 493         || (base->get_infer_kind ()
 494             == TyTy::InferType::InferTypeKind::INTEGRAL);
 495     if (is_valid)
 496       {
 497         ok = true;
 498         return;
 499       }
 500
 501     BaseCmp::visit (type);
 502   }
 503
 504   void visit (const USizeType &type) override
 505   {
 506     bool is_valid
 507       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
 508         || (base->get_infer_kind ()
 509             == TyTy::InferType::InferTypeKind::INTEGRAL);
 510     if (is_valid)
 511       {
 512         ok = true;
 513         return;
 514       }
 515
 516     BaseCmp::visit (type);
 517   }
 518
 519   void visit (const ISizeType &type) override
 520   {
 521     bool is_valid
 522       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
 523         || (base->get_infer_kind ()
 524             == TyTy::InferType::InferTypeKind::INTEGRAL);
 525     if (is_valid)
 526       {
 527         ok = true;
 528         return;
 529       }
 530
 531     BaseCmp::visit (type);
 532   }
 533
 534   void visit (const FloatType &type) override
 535   {
 536     bool is_valid
 537       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
 538         || (base->get_infer_kind () == TyTy::InferType::InferTypeKind::FLOAT);
 539     if (is_valid)
 540       {
 541         ok = true;
 542         return;
 543       }
 544
 545     BaseCmp::visit (type);
 546   }
 547
 548   void visit (const ArrayType &type) override
 549   {
 550     bool is_valid
 551       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 552     if (is_valid)
 553       {
 554         ok = true;
 555         return;
 556       }
 557
 558     BaseCmp::visit (type);
 559   }
 560
 561   void visit (const SliceType &type) override
 562   {
 563     bool is_valid
 564       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 565     if (is_valid)
 566       {
 567         ok = true;
 568         return;
 569       }
 570
 571     BaseCmp::visit (type);
 572   }
 573
 574   void visit (const ADTType &type) override
 575   {
 576     bool is_valid
 577       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 578     if (is_valid)
 579       {
 580         ok = true;
 581         return;
 582       }
 583
 584     BaseCmp::visit (type);
 585   }
 586
 587   void visit (const TupleType &type) override
 588   {
 589     bool is_valid
 590       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 591     if (is_valid)
 592       {
 593         ok = true;
 594         return;
 595       }
 596
 597     BaseCmp::visit (type);
 598   }
 599
 600   void visit (const InferType &type) override
 601   {
 602     switch (base->get_infer_kind ())
 603       {
 604       case InferType::InferTypeKind::GENERAL:
 605         ok = true;
 606         return;
 607
 608         case InferType::InferTypeKind::INTEGRAL: {
 609           if (type.get_infer_kind () == InferType::InferTypeKind::INTEGRAL)
 610             {
 611               ok = true;
 612               return;
 613             }
 614           else if (type.get_infer_kind () == InferType::InferTypeKind::GENERAL)
 615             {
 616               ok = true;
 617               return;
 618             }
 619         }
 620         break;
 621
 622         case InferType::InferTypeKind::FLOAT: {
 623           if (type.get_infer_kind () == InferType::InferTypeKind::FLOAT)
 624             {
 625               ok = true;
 626               return;
 627             }
 628           else if (type.get_infer_kind () == InferType::InferTypeKind::GENERAL)
 629             {
 630               ok = true;
 631               return;
 632             }
 633         }
 634         break;
 635       }
 636
 637     BaseCmp::visit (type);
 638   }
 639
 640   void visit (const CharType &type) override
 641   {
 642     {
 643       bool is_valid
 644         = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 645       if (is_valid)
 646         {
 647           ok = true;
 648           return;
 649         }
 650
 651       BaseCmp::visit (type);
 652     }
 653   }
 654
 655   void visit (const ReferenceType &type) override
 656   {
 657     bool is_valid
 658       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 659     if (is_valid)
 660       {
 661         ok = true;
 662         return;
 663       }
 664
 665     BaseCmp::visit (type);
 666   }
 667
 668   void visit (const PointerType &type) override
 669   {
 670     bool is_valid
 671       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 672     if (is_valid)
 673       {
 674         ok = true;
 675         return;
 676       }
 677
 678     BaseCmp::visit (type);
 679   }
 680
 681   void visit (const ParamType &) override { ok = true; }
 682
 683   void visit (const DynamicObjectType &type) override
 684   {
 685     bool is_valid
 686       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 687     if (is_valid)
 688       {
 689         ok = true;
 690         return;
 691       }
 692
 693     BaseCmp::visit (type);
 694   }
 695
 696   void visit (const ClosureType &type) override
 697   {
 698     bool is_valid
 699       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
 700     if (is_valid)
 701       {
 702         ok = true;
 703         return;
 704       }
 705
 706     BaseCmp::visit (type);
 707   }
 708
 709 private:
 710   const BaseType *get_base () const override { return base; }
 711   const InferType *base;
 712 };
 713
 714 class FnCmp : public BaseCmp
 715 {
 716   using Rust::TyTy::BaseCmp::visit;
 717
 718 public:
 719   FnCmp (const FnType *base, bool emit_errors)
 720     : BaseCmp (base, emit_errors), base (base)
 721   {}
 722
 723   void visit (const InferType &type) override
 724   {
 725     ok = type.get_infer_kind () == InferType::InferTypeKind::GENERAL;
 726   }
 727
 728   void visit (const FnType &type) override
 729   {
 730     if (base->num_params () != type.num_params ())
 731       {
 732         BaseCmp::visit (type);
 733         return;
 734       }
 735
 736     for (size_t i = 0; i < base->num_params (); i++)
 737       {
 738         auto a = base->param_at (i).second;
 739         auto b = type.param_at (i).second;
 740
 741         if (!a->can_eq (b, emit_error_flag))
 742           {
 743             emit_error_flag = false;
 744             BaseCmp::visit (type);
 745             return;
 746           }
 747       }
 748
 749     if (!base->get_return_type ()->can_eq (type.get_return_type (),
 750                                            emit_error_flag))
 751       {
 752         emit_error_flag = false;
 753         BaseCmp::visit (type);
 754         return;
 755       }
 756
 757     ok = true;
 758   }
 759
 760 private:
 761   const BaseType *get_base () const override { return base; }
 762   const FnType *base;
 763 };
 764
 765 class FnptrCmp : public BaseCmp
 766 {
 767   using Rust::TyTy::BaseCmp::visit;
 768
 769 public:
 770   FnptrCmp (const FnPtr *base, bool emit_errors)
 771     : BaseCmp (base, emit_errors), base (base)
 772   {}
 773
 774   void visit (const InferType &type) override
 775   {
 776     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
 777       {
 778         BaseCmp::visit (type);
 779         return;
 780       }
 781
 782     ok = true;
 783   }
 784
 785   void visit (const FnPtr &type) override
 786   {
 787     if (base->num_params () != type.num_params ())
 788       {
 789         BaseCmp::visit (type);
 790         return;
 791       }
 792
 793     auto this_ret_type = base->get_return_type ();
 794     auto other_ret_type = type.get_return_type ();
 795     if (!this_ret_type->can_eq (other_ret_type, emit_error_flag))
 796       {
 797         BaseCmp::visit (type);
 798         return;
 799       }
 800
 801     for (size_t i = 0; i < base->num_params (); i++)
 802       {
 803         auto this_param = base->get_param_type_at (i);
 804         auto other_param = type.get_param_type_at (i);
 805         if (!this_param->can_eq (other_param, emit_error_flag))
 806           {
 807             BaseCmp::visit (type);
 808             return;
 809           }
 810       }
 811
 812     ok = true;
 813   }
 814
 815   void visit (const FnType &type) override
 816   {
 817     if (base->num_params () != type.num_params ())
 818       {
 819         BaseCmp::visit (type);
 820         return;
 821       }
 822
 823     auto this_ret_type = base->get_return_type ();
 824     auto other_ret_type = type.get_return_type ();
 825     if (!this_ret_type->can_eq (other_ret_type, emit_error_flag))
 826       {
 827         BaseCmp::visit (type);
 828         return;
 829       }
 830
 831     for (size_t i = 0; i < base->num_params (); i++)
 832       {
 833         auto this_param = base->get_param_type_at (i);
 834         auto other_param = type.param_at (i).second;
 835         if (!this_param->can_eq (other_param, emit_error_flag))
 836           {
 837             BaseCmp::visit (type);
 838             return;
 839           }
 840       }
 841
 842     ok = true;
 843   }
 844
 845 private:
 846   const BaseType *get_base () const override { return base; }
 847   const FnPtr *base;
 848 };
 849
 850 class ClosureCmp : public BaseCmp
 851 {
 852   using Rust::TyTy::BaseCmp::visit;
 853
 854 public:
 855   ClosureCmp (const ClosureType *base, bool emit_errors)
 856     : BaseCmp (base, emit_errors), base (base)
 857   {}
 858
 859   void visit (const InferType &type) override
 860   {
 861     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
 862       {
 863         BaseCmp::visit (type);
 864         return;
 865       }
 866
 867     ok = true;
 868   }
 869
 870   void visit (const ClosureType &type) override
 871   {
 872     if (base->get_def_id () != type.get_def_id ())
 873       {
 874         BaseCmp::visit (type);
 875         return;
 876       }
 877
 878     if (!base->get_parameters ().can_eq (&type.get_parameters (), false))
 879       {
 880         BaseCmp::visit (type);
 881         return;
 882       }
 883
 884     if (!base->get_result_type ().can_eq (&type.get_result_type (), false))
 885       {
 886         BaseCmp::visit (type);
 887         return;
 888       }
 889
 890     ok = true;
 891   }
 892
 893 private:
 894   const BaseType *get_base () const override { return base; }
 895   const ClosureType *base;
 896 };
 897
 898 class ArrayCmp : public BaseCmp
 899 {
 900   using Rust::TyTy::BaseCmp::visit;
 901
 902 public:
 903   ArrayCmp (const ArrayType *base, bool emit_errors)
 904     : BaseCmp (base, emit_errors), base (base)
 905   {}
 906
 907   void visit (const ArrayType &type) override
 908   {
 909     // check base type
 910     const BaseType *base_element = base->get_element_type ();
 911     const BaseType *other_element = type.get_element_type ();
 912     if (!base_element->can_eq (other_element, emit_error_flag))
 913       {
 914         BaseCmp::visit (type);
 915         return;
 916       }
 917
 918     ok = true;
 919   }
 920
 921   void visit (const InferType &type) override
 922   {
 923     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
 924       {
 925         BaseCmp::visit (type);
 926         return;
 927       }
 928
 929     ok = true;
 930   }
 931
 932 private:
 933   const BaseType *get_base () const override { return base; }
 934   const ArrayType *base;
 935 };
 936
 937 class SliceCmp : public BaseCmp
 938 {
 939   using Rust::TyTy::BaseCmp::visit;
 940
 941 public:
 942   SliceCmp (const SliceType *base, bool emit_errors)
 943     : BaseCmp (base, emit_errors), base (base)
 944   {}
 945
 946   void visit (const SliceType &type) override
 947   {
 948     // check base type
 949     const BaseType *base_element = base->get_element_type ();
 950     const BaseType *other_element = type.get_element_type ();
 951     if (!base_element->can_eq (other_element, emit_error_flag))
 952       {
 953         BaseCmp::visit (type);
 954         return;
 955       }
 956
 957     ok = true;
 958   }
 959
 960   void visit (const InferType &type) override
 961   {
 962     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
 963       {
 964         BaseCmp::visit (type);
 965         return;
 966       }
 967
 968     ok = true;
 969   }
 970
 971 private:
 972   const BaseType *get_base () const override { return base; }
 973   const SliceType *base;
 974 };
 975
 976 class BoolCmp : public BaseCmp
 977 {
 978   using Rust::TyTy::BaseCmp::visit;
 979
 980 public:
 981   BoolCmp (const BoolType *base, bool emit_errors)
 982     : BaseCmp (base, emit_errors), base (base)
 983   {}
 984
 985   void visit (const BoolType &type) override { ok = true; }
 986
 987   void visit (const InferType &type) override
 988   {
 989     ok = type.get_infer_kind () == InferType::InferTypeKind::GENERAL;
 990   }
 991
 992 private:
 993   const BaseType *get_base () const override { return base; }
 994   const BoolType *base;
 995 };
 996
 997 class IntCmp : public BaseCmp
 998 {
 999   using Rust::TyTy::BaseCmp::visit;
1000
1001 public:
1002   IntCmp (const IntType *base, bool emit_errors)
1003     : BaseCmp (base, emit_errors), base (base)
1004   {}
1005
1006   void visit (const InferType &type) override
1007   {
1008     ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
1009   }
1010
1011   void visit (const IntType &type) override
1012   {
1013     ok = type.get_int_kind () == base->get_int_kind ();
1014   }
1015
1016 private:
1017   const BaseType *get_base () const override { return base; }
1018   const IntType *base;
1019 };
1020
1021 class UintCmp : public BaseCmp
1022 {
1023   using Rust::TyTy::BaseCmp::visit;
1024
1025 public:
1026   UintCmp (const UintType *base, bool emit_errors)
1027     : BaseCmp (base, emit_errors), base (base)
1028   {}
1029
1030   void visit (const InferType &type) override
1031   {
1032     ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
1033   }
1034
1035   void visit (const UintType &type) override
1036   {
1037     ok = type.get_uint_kind () == base->get_uint_kind ();
1038   }
1039
1040 private:
1041   const BaseType *get_base () const override { return base; }
1042   const UintType *base;
1043 };
1044
1045 class FloatCmp : public BaseCmp
1046 {
1047   using Rust::TyTy::BaseCmp::visit;
1048
1049 public:
1050   FloatCmp (const FloatType *base, bool emit_errors)
1051     : BaseCmp (base, emit_errors), base (base)
1052   {}
1053
1054   void visit (const InferType &type) override
1055   {
1056     ok = type.get_infer_kind () != InferType::InferTypeKind::INTEGRAL;
1057   }
1058
1059   void visit (const FloatType &type) override
1060   {
1061     ok = type.get_float_kind () == base->get_float_kind ();
1062   }
1063
1064 private:
1065   const BaseType *get_base () const override { return base; }
1066   const FloatType *base;
1067 };
1068
1069 class ADTCmp : public BaseCmp
1070 {
1071   using Rust::TyTy::BaseCmp::visit;
1072
1073 public:
1074   ADTCmp (const ADTType *base, bool emit_errors)
1075     : BaseCmp (base, emit_errors), base (base)
1076   {}
1077
1078   void visit (const ADTType &type) override
1079   {
1080     if (base->get_adt_kind () != type.get_adt_kind ())
1081       {
1082         BaseCmp::visit (type);
1083         return;
1084       }
1085
1086     if (base->get_identifier ().compare (type.get_identifier ()) != 0)
1087       {
1088         BaseCmp::visit (type);
1089         return;
1090       }
1091
1092     if (base->number_of_variants () != type.number_of_variants ())
1093       {
1094         BaseCmp::visit (type);
1095         return;
1096       }
1097
1098     for (size_t i = 0; i < type.number_of_variants (); ++i)
1099       {
1100         TyTy::VariantDef *a = base->get_variants ().at (i);
1101         TyTy::VariantDef *b = type.get_variants ().at (i);
1102
1103         if (a->num_fields () != b->num_fields ())
1104           {
1105             BaseCmp::visit (type);
1106             return;
1107           }
1108
1109         for (size_t j = 0; j < a->num_fields (); j++)
1110           {
1111             TyTy::StructFieldType *base_field = a->get_field_at_index (j);
1112             TyTy::StructFieldType *other_field = b->get_field_at_index (j);
1113
1114             TyTy::BaseType *this_field_ty = base_field->get_field_type ();
1115             TyTy::BaseType *other_field_ty = other_field->get_field_type ();
1116
1117             if (!this_field_ty->can_eq (other_field_ty, emit_error_flag))
1118               {
1119                 BaseCmp::visit (type);
1120                 return;
1121               }
1122           }
1123       }
1124
1125     ok = true;
1126   }
1127
1128   void visit (const InferType &type) override
1129   {
1130     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
1131       {
1132         BaseCmp::visit (type);
1133         return;
1134       }
1135
1136     ok = true;
1137   }
1138
1139 private:
1140   const BaseType *get_base () const override { return base; }
1141   const ADTType *base;
1142 };
1143
1144 class TupleCmp : public BaseCmp
1145 {
1146   using Rust::TyTy::BaseCmp::visit;
1147
1148 public:
1149   TupleCmp (const TupleType *base, bool emit_errors)
1150     : BaseCmp (base, emit_errors), base (base)
1151   {}
1152
1153   void visit (const TupleType &type) override
1154   {
1155     if (base->num_fields () != type.num_fields ())
1156       {
1157         BaseCmp::visit (type);
1158         return;
1159       }
1160
1161     for (size_t i = 0; i < base->num_fields (); i++)
1162       {
1163         BaseType *bo = base->get_field (i);
1164         BaseType *fo = type.get_field (i);
1165
1166         if (!bo->can_eq (fo, emit_error_flag))
1167           {
1168             BaseCmp::visit (type);
1169             return;
1170           }
1171       }
1172
1173     ok = true;
1174   }
1175
1176   void visit (const InferType &type) override
1177   {
1178     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
1179       {
1180         BaseCmp::visit (type);
1181         return;
1182       }
1183
1184     ok = true;
1185   }
1186
1187 private:
1188   const BaseType *get_base () const override { return base; }
1189   const TupleType *base;
1190 };
1191
1192 class USizeCmp : public BaseCmp
1193 {
1194   using Rust::TyTy::BaseCmp::visit;
1195
1196 public:
1197   USizeCmp (const USizeType *base, bool emit_errors)
1198     : BaseCmp (base, emit_errors), base (base)
1199   {}
1200
1201   void visit (const InferType &type) override
1202   {
1203     ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
1204   }
1205
1206   void visit (const USizeType &type) override { ok = true; }
1207
1208 private:
1209   const BaseType *get_base () const override { return base; }
1210   const USizeType *base;
1211 };
1212
1213 class ISizeCmp : public BaseCmp
1214 {
1215   using Rust::TyTy::BaseCmp::visit;
1216
1217 public:
1218   ISizeCmp (const ISizeType *base, bool emit_errors)
1219     : BaseCmp (base, emit_errors), base (base)
1220   {}
1221
1222   void visit (const InferType &type) override
1223   {
1224     ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
1225   }
1226
1227   void visit (const ISizeType &type) override { ok = true; }
1228
1229 private:
1230   const BaseType *get_base () const override { return base; }
1231   const ISizeType *base;
1232 };
1233
1234 class CharCmp : public BaseCmp
1235 {
1236   using Rust::TyTy::BaseCmp::visit;
1237
1238 public:
1239   CharCmp (const CharType *base, bool emit_errors)
1240     : BaseCmp (base, emit_errors), base (base)
1241   {}
1242
1243   void visit (const InferType &type) override
1244   {
1245     ok = type.get_infer_kind () == InferType::InferTypeKind::GENERAL;
1246   }
1247
1248   void visit (const CharType &type) override { ok = true; }
1249
1250 private:
1251   const BaseType *get_base () const override { return base; }
1252   const CharType *base;
1253 };
1254
1255 class ReferenceCmp : public BaseCmp
1256 {
1257   using Rust::TyTy::BaseCmp::visit;
1258
1259 public:
1260   ReferenceCmp (const ReferenceType *base, bool emit_errors)
1261     : BaseCmp (base, emit_errors), base (base)
1262   {}
1263
1264   void visit (const ReferenceType &type) override
1265   {
1266     auto base_type = base->get_base ();
1267     auto other_base_type = type.get_base ();
1268
1269     bool mutability_ok = base->is_mutable () ? type.is_mutable () : true;
1270     if (!mutability_ok)
1271       {
1272         BaseCmp::visit (type);
1273         return;
1274       }
1275
1276     if (!base_type->can_eq (other_base_type, emit_error_flag))
1277       {
1278         BaseCmp::visit (type);
1279         return;
1280       }
1281
1282     ok = true;
1283   }
1284
1285   void visit (const InferType &type) override
1286   {
1287     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
1288       {
1289         BaseCmp::visit (type);
1290         return;
1291       }
1292
1293     ok = true;
1294   }
1295
1296 private:
1297   const BaseType *get_base () const override { return base; }
1298   const ReferenceType *base;
1299 };
1300
1301 class PointerCmp : public BaseCmp
1302 {
1303   using Rust::TyTy::BaseCmp::visit;
1304
1305 public:
1306   PointerCmp (const PointerType *base, bool emit_errors)
1307     : BaseCmp (base, emit_errors), base (base)
1308   {}
1309
1310   void visit (const PointerType &type) override
1311   {
1312     auto base_type = base->get_base ();
1313     auto other_base_type = type.get_base ();
1314
1315     bool mutability_ok = base->is_mutable () ? type.is_mutable () : true;
1316     if (!mutability_ok)
1317       {
1318         BaseCmp::visit (type);
1319         return;
1320       }
1321
1322     if (!base_type->can_eq (other_base_type, emit_error_flag))
1323       {
1324         BaseCmp::visit (type);
1325         return;
1326       }
1327
1328     ok = true;
1329   }
1330
1331   void visit (const InferType &type) override
1332   {
1333     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
1334       {
1335         BaseCmp::visit (type);
1336         return;
1337       }
1338
1339     ok = true;
1340   }
1341
1342 private:
1343   const BaseType *get_base () const override { return base; }
1344   const PointerType *base;
1345 };
1346
1347 class ParamCmp : public BaseCmp
1348 {
1349   using Rust::TyTy::BaseCmp::visit;
1350
1351 public:
1352   ParamCmp (const ParamType *base, bool emit_errors)
1353     : BaseCmp (base, emit_errors), base (base)
1354   {}
1355
1356   // param types are a placeholder we shouldn't have cases where we unify
1357   // against it. eg: struct foo<T> { a: T }; When we invoke it we can do either:
1358   //
1359   // foo<i32>{ a: 123 }.
1360   // Then this enforces the i32 type to be referenced on the
1361   // field via an hirid.
1362   //
1363   // rust also allows for a = foo{a:123}; Where we can use an Inference Variable
1364   // to handle the typing of the struct
1365   bool can_eq (const BaseType *other) override
1366   {
1367     if (!base->can_resolve ())
1368       return BaseCmp::can_eq (other);
1369
1370     auto lookup = base->resolve ();
1371     return lookup->can_eq (other, emit_error_flag);
1372   }
1373
1374   // imagine the case where we have:
1375   // struct Foo<T>(T);
1376   // Then we declare a generic impl block
1377   // impl <X>Foo<X> { ... }
1378   // both of these types are compatible so we mostly care about the number of
1379   // generic arguments
1380   void visit (const ParamType &) override { ok = true; }
1381
1382   void visit (const TupleType &) override { ok = true; }
1383
1384   void visit (const InferType &) override { ok = true; }
1385
1386   void visit (const FnType &) override { ok = true; }
1387
1388   void visit (const FnPtr &) override { ok = true; }
1389
1390   void visit (const ADTType &) override { ok = true; }
1391
1392   void visit (const ArrayType &) override { ok = true; }
1393
1394   void visit (const SliceType &) override { ok = true; }
1395
1396   void visit (const BoolType &) override { ok = true; }
1397
1398   void visit (const IntType &) override { ok = true; }
1399
1400   void visit (const UintType &) override { ok = true; }
1401
1402   void visit (const USizeType &) override { ok = true; }
1403
1404   void visit (const ISizeType &) override { ok = true; }
1405
1406   void visit (const FloatType &) override { ok = true; }
1407
1408   void visit (const CharType &) override { ok = true; }
1409
1410   void visit (const ReferenceType &) override { ok = true; }
1411
1412   void visit (const PointerType &) override { ok = true; }
1413
1414   void visit (const StrType &) override { ok = true; }
1415
1416   void visit (const NeverType &) override { ok = true; }
1417
1418   void visit (const DynamicObjectType &) override { ok = true; }
1419
1420   void visit (const PlaceholderType &type) override
1421   {
1422     ok = base->get_symbol ().compare (type.get_symbol ()) == 0;
1423   }
1424
1425 private:
1426   const BaseType *get_base () const override { return base; }
1427   const ParamType *base;
1428 };
1429
1430 class StrCmp : public BaseCmp
1431 {
1432   // FIXME we will need a enum for the StrType like ByteBuf etc..
1433   using Rust::TyTy::BaseCmp::visit;
1434
1435 public:
1436   StrCmp (const StrType *base, bool emit_errors)
1437     : BaseCmp (base, emit_errors), base (base)
1438   {}
1439
1440   void visit (const StrType &type) override { ok = true; }
1441
1442   void visit (const InferType &type) override
1443   {
1444     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
1445       {
1446         BaseCmp::visit (type);
1447         return;
1448       }
1449
1450     ok = true;
1451   }
1452
1453 private:
1454   const BaseType *get_base () const override { return base; }
1455   const StrType *base;
1456 };
1457
1458 class NeverCmp : public BaseCmp
1459 {
1460   using Rust::TyTy::BaseCmp::visit;
1461
1462 public:
1463   NeverCmp (const NeverType *base, bool emit_errors)
1464     : BaseCmp (base, emit_errors), base (base)
1465   {}
1466
1467   void visit (const NeverType &type) override { ok = true; }
1468
1469   void visit (const InferType &type) override
1470   {
1471     if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
1472       {
1473         BaseCmp::visit (type);
1474         return;
1475       }
1476
1477     ok = true;
1478   }
1479
1480 private:
1481   const BaseType *get_base () const override { return base; }
1482   const NeverType *base;
1483 };
1484
1485 class PlaceholderCmp : public BaseCmp
1486 {
1487   using Rust::TyTy::BaseCmp::visit;
1488
1489 public:
1490   PlaceholderCmp (const PlaceholderType *base, bool emit_errors)
1491     : BaseCmp (base, emit_errors), base (base)
1492   {}
1493
1494   bool can_eq (const BaseType *other) override
1495   {
1496     if (!base->can_resolve ())
1497       return BaseCmp::can_eq (other);
1498
1499     BaseType *lookup = base->resolve ();
1500     return lookup->can_eq (other, emit_error_flag);
1501   }
1502
1503   void visit (const TupleType &) override { ok = true; }
1504
1505   void visit (const ADTType &) override { ok = true; }
1506
1507   void visit (const InferType &) override { ok = true; }
1508
1509   void visit (const FnType &) override { ok = true; }
1510
1511   void visit (const FnPtr &) override { ok = true; }
1512
1513   void visit (const ArrayType &) override { ok = true; }
1514
1515   void visit (const BoolType &) override { ok = true; }
1516
1517   void visit (const IntType &) override { ok = true; }
1518
1519   void visit (const UintType &) override { ok = true; }
1520
1521   void visit (const USizeType &) override { ok = true; }
1522
1523   void visit (const ISizeType &) override { ok = true; }
1524
1525   void visit (const FloatType &) override { ok = true; }
1526
1527   void visit (const ErrorType &) override { ok = true; }
1528
1529   void visit (const CharType &) override { ok = true; }
1530
1531   void visit (const ReferenceType &) override { ok = true; }
1532
1533   void visit (const ParamType &) override { ok = true; }
1534
1535   void visit (const StrType &) override { ok = true; }
1536
1537   void visit (const NeverType &) override { ok = true; }
1538
1539   void visit (const SliceType &) override { ok = true; }
1540
1541 private:
1542   const BaseType *get_base () const override { return base; }
1543
1544   const PlaceholderType *base;
1545 };
1546
1547 class DynamicCmp : public BaseCmp
1548 {
1549   using Rust::TyTy::BaseCmp::visit;
1550
1551 public:
1552   DynamicCmp (const DynamicObjectType *base, bool emit_errors)
1553     : BaseCmp (base, emit_errors), base (base)
1554   {}
1555
1556   void visit (const DynamicObjectType &type) override
1557   {
1558     if (base->num_specified_bounds () != type.num_specified_bounds ())
1559       {
1560         BaseCmp::visit (type);
1561         return;
1562       }
1563
1564     location_t ref_locus = mappings->lookup_location (type.get_ref ());
1565     ok = base->bounds_compatible (type, ref_locus, false);
1566   }
1567
1568 private:
1569   const BaseType *get_base () const override { return base; }
1570
1571   const DynamicObjectType *base;
1572 };
1573
1574 } // namespace TyTy
1575 } // namespace Rust
1576
1577 #endif // RUST_TYTY_CMP_H