src/librustc_typeck/check/op.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Code related to processing overloaded binary and unary operators.
  12
  13 use super::FnCtxt;
  14 use hir::def_id::DefId;
  15 use rustc::ty::{Ty, TypeFoldable, PreferMutLvalue, TypeVariants};
  16 use rustc::ty::TypeVariants::{TyStr, TyRef};
  17 use rustc::infer::type_variable::TypeVariableOrigin;
  18 use errors;
  19 use syntax::ast;
  20 use syntax::symbol::Symbol;
  21 use rustc::hir;
  22
  23 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
  24     /// Check a `a <op>= b`
  25     pub fn check_binop_assign(&self,
  26                               expr: &'gcx hir::Expr,
  27                               op: hir::BinOp,
  28                               lhs_expr: &'gcx hir::Expr,
  29                               rhs_expr: &'gcx hir::Expr) -> Ty<'tcx>
  30     {
  31         let lhs_ty = self.check_expr_with_lvalue_pref(lhs_expr, PreferMutLvalue);
  32
  33         let lhs_ty = self.resolve_type_vars_with_obligations(lhs_ty);
  34         let (rhs_ty, return_ty) =
  35             self.check_overloaded_binop(expr, lhs_expr, lhs_ty, rhs_expr, op, IsAssign::Yes);
  36         let rhs_ty = self.resolve_type_vars_with_obligations(rhs_ty);
  37
  38         let ty = if !lhs_ty.is_ty_var() && !rhs_ty.is_ty_var()
  39                     && is_builtin_binop(lhs_ty, rhs_ty, op) {
  40             self.enforce_builtin_binop_types(lhs_expr, lhs_ty, rhs_expr, rhs_ty, op);
  41             self.tcx.mk_nil()
  42         } else {
  43             return_ty
  44         };
  45
  46         let tcx = self.tcx;
  47         if !tcx.expr_is_lval(lhs_expr) {
  48             struct_span_err!(
  49                 tcx.sess, lhs_expr.span,
  50                 E0067, "invalid left-hand side expression")
  51             .span_label(
  52                 lhs_expr.span,
  53                 &format!("invalid expression for left-hand side"))
  54             .emit();
  55         }
  56         ty
  57     }
  58
  59     /// Check a potentially overloaded binary operator.
  60     pub fn check_binop(&self,
  61                        expr: &'gcx hir::Expr,
  62                        op: hir::BinOp,
  63                        lhs_expr: &'gcx hir::Expr,
  64                        rhs_expr: &'gcx hir::Expr) -> Ty<'tcx>
  65     {
  66         let tcx = self.tcx;
  67
  68         debug!("check_binop(expr.id={}, expr={:?}, op={:?}, lhs_expr={:?}, rhs_expr={:?})",
  69                expr.id,
  70                expr,
  71                op,
  72                lhs_expr,
  73                rhs_expr);
  74
  75         let lhs_ty = self.check_expr(lhs_expr);
  76         let lhs_ty = self.resolve_type_vars_with_obligations(lhs_ty);
  77
  78         match BinOpCategory::from(op) {
  79             BinOpCategory::Shortcircuit => {
  80                 // && and || are a simple case.
  81                 let lhs_diverges = self.diverges.get();
  82                 self.demand_suptype(lhs_expr.span, tcx.mk_bool(), lhs_ty);
  83                 self.check_expr_coercable_to_type(rhs_expr, tcx.mk_bool());
  84
  85                 // Depending on the LHS' value, the RHS can never execute.
  86                 self.diverges.set(lhs_diverges);
  87
  88                 tcx.mk_bool()
  89             }
  90             _ => {
  91                 // Otherwise, we always treat operators as if they are
  92                 // overloaded. This is the way to be most flexible w/r/t
  93                 // types that get inferred.
  94                 let (rhs_ty, return_ty) =
  95                     self.check_overloaded_binop(expr, lhs_expr, lhs_ty,
  96                                                 rhs_expr, op, IsAssign::No);
  97
  98                 // Supply type inference hints if relevant. Probably these
  99                 // hints should be enforced during select as part of the
 100                 // `consider_unification_despite_ambiguity` routine, but this
 101                 // more convenient for now.
 102                 //
 103                 // The basic idea is to help type inference by taking
 104                 // advantage of things we know about how the impls for
 105                 // scalar types are arranged. This is important in a
 106                 // scenario like `1_u32 << 2`, because it lets us quickly
 107                 // deduce that the result type should be `u32`, even
 108                 // though we don't know yet what type 2 has and hence
 109                 // can't pin this down to a specific impl.
 110                 let rhs_ty = self.resolve_type_vars_with_obligations(rhs_ty);
 111                 if
 112                     !lhs_ty.is_ty_var() && !rhs_ty.is_ty_var() &&
 113                     is_builtin_binop(lhs_ty, rhs_ty, op)
 114                 {
 115                     let builtin_return_ty =
 116                         self.enforce_builtin_binop_types(lhs_expr, lhs_ty, rhs_expr, rhs_ty, op);
 117                     self.demand_suptype(expr.span, builtin_return_ty, return_ty);
 118                 }
 119
 120                 return_ty
 121             }
 122         }
 123     }
 124
 125     fn enforce_builtin_binop_types(&self,
 126                                    lhs_expr: &'gcx hir::Expr,
 127                                    lhs_ty: Ty<'tcx>,
 128                                    rhs_expr: &'gcx hir::Expr,
 129                                    rhs_ty: Ty<'tcx>,
 130                                    op: hir::BinOp)
 131                                    -> Ty<'tcx>
 132     {
 133         debug_assert!(is_builtin_binop(lhs_ty, rhs_ty, op));
 134
 135         let tcx = self.tcx;
 136         match BinOpCategory::from(op) {
 137             BinOpCategory::Shortcircuit => {
 138                 self.demand_suptype(lhs_expr.span, tcx.mk_bool(), lhs_ty);
 139                 self.demand_suptype(rhs_expr.span, tcx.mk_bool(), rhs_ty);
 140                 tcx.mk_bool()
 141             }
 142
 143             BinOpCategory::Shift => {
 144                 // result type is same as LHS always
 145                 lhs_ty
 146             }
 147
 148             BinOpCategory::Math |
 149             BinOpCategory::Bitwise => {
 150                 // both LHS and RHS and result will have the same type
 151                 self.demand_suptype(rhs_expr.span, lhs_ty, rhs_ty);
 152                 lhs_ty
 153             }
 154
 155             BinOpCategory::Comparison => {
 156                 // both LHS and RHS and result will have the same type
 157                 self.demand_suptype(rhs_expr.span, lhs_ty, rhs_ty);
 158                 tcx.mk_bool()
 159             }
 160         }
 161     }
 162
 163     fn check_overloaded_binop(&self,
 164                               expr: &'gcx hir::Expr,
 165                               lhs_expr: &'gcx hir::Expr,
 166                               lhs_ty: Ty<'tcx>,
 167                               rhs_expr: &'gcx hir::Expr,
 168                               op: hir::BinOp,
 169                               is_assign: IsAssign)
 170                               -> (Ty<'tcx>, Ty<'tcx>)
 171     {
 172         debug!("check_overloaded_binop(expr.id={}, lhs_ty={:?}, is_assign={:?})",
 173                expr.id,
 174                lhs_ty,
 175                is_assign);
 176
 177         let (name, trait_def_id) = self.name_and_trait_def_id(op, is_assign);
 178
 179         // NB: As we have not yet type-checked the RHS, we don't have the
 180         // type at hand. Make a variable to represent it. The whole reason
 181         // for this indirection is so that, below, we can check the expr
 182         // using this variable as the expected type, which sometimes lets
 183         // us do better coercions than we would be able to do otherwise,
 184         // particularly for things like `String + &String`.
 185         let rhs_ty_var = self.next_ty_var(TypeVariableOrigin::MiscVariable(rhs_expr.span));
 186
 187         let return_ty = self.lookup_op_method(expr, lhs_ty, vec![rhs_ty_var],
 188                                               Symbol::intern(name), trait_def_id,
 189                                               lhs_expr);
 190
 191         // see `NB` above
 192         let rhs_ty = self.check_expr_coercable_to_type(rhs_expr, rhs_ty_var);
 193
 194         let return_ty = match return_ty {
 195             Ok(return_ty) => return_ty,
 196             Err(()) => {
 197                 // error types are considered "builtin"
 198                 if !lhs_ty.references_error() {
 199                     if let IsAssign::Yes = is_assign {
 200                         struct_span_err!(self.tcx.sess, lhs_expr.span, E0368,
 201                                          "binary assignment operation `{}=` \
 202                                           cannot be applied to type `{}`",
 203                                          op.node.as_str(),
 204                                          lhs_ty)
 205                             .span_label(lhs_expr.span,
 206                                         &format!("cannot use `{}=` on type `{}`",
 207                                         op.node.as_str(), lhs_ty))
 208                             .emit();
 209                     } else {
 210                         let mut err = struct_span_err!(self.tcx.sess, lhs_expr.span, E0369,
 211                             "binary operation `{}` cannot be applied to type `{}`",
 212                             op.node.as_str(),
 213                             lhs_ty);
 214
 215                         if let TypeVariants::TyRef(_, ref ty_mut) = lhs_ty.sty {
 216                             if !self.infcx.type_moves_by_default(ty_mut.ty, lhs_expr.span) &&
 217                                 self.lookup_op_method(expr, ty_mut.ty, vec![rhs_ty],
 218                                     Symbol::intern(name), trait_def_id,
 219                                     lhs_expr).is_ok() {
 220                                 err.note(
 221                                     &format!(
 222                                         "this is a reference to a type that `{}` can be applied \
 223                                         to; you need to dereference this variable once for this \
 224                                         operation to work",
 225                                     op.node.as_str()));
 226                             }
 227                         }
 228
 229                         let missing_trait = match op.node {
 230                             hir::BiAdd    => Some("std::ops::Add"),
 231                             hir::BiSub    => Some("std::ops::Sub"),
 232                             hir::BiMul    => Some("std::ops::Mul"),
 233                             hir::BiDiv    => Some("std::ops::Div"),
 234                             hir::BiRem    => Some("std::ops::Rem"),
 235                             hir::BiBitAnd => Some("std::ops::BitAnd"),
 236                             hir::BiBitOr  => Some("std::ops::BitOr"),
 237                             hir::BiShl    => Some("std::ops::Shl"),
 238                             hir::BiShr    => Some("std::ops::Shr"),
 239                             hir::BiEq | hir::BiNe => Some("std::cmp::PartialEq"),
 240                             hir::BiLt | hir::BiLe | hir::BiGt | hir::BiGe =>
 241                                 Some("std::cmp::PartialOrd"),
 242                             _             => None
 243                         };
 244
 245                         if let Some(missing_trait) = missing_trait {
 246                             if missing_trait == "std::ops::Add" &&
 247                                 self.check_str_addition(expr, lhs_expr, lhs_ty,
 248                                                          rhs_expr, rhs_ty, &mut err) {
 249                                 // This has nothing here because it means we did string
 250                                 // concatenation (e.g. "Hello " + "World!"). This means
 251                                 // we don't want the note in the else clause to be emitted
 252                             } else {
 253                                 err.note(
 254                                     &format!("an implementation of `{}` might be missing for `{}`",
 255                                              missing_trait, lhs_ty));
 256                             }
 257                         }
 258                         err.emit();
 259                     }
 260                 }
 261                 self.tcx.types.err
 262             }
 263         };
 264
 265         (rhs_ty_var, return_ty)
 266     }
 267
 268     fn check_str_addition(&self,
 269                           expr: &'gcx hir::Expr,
 270                           lhs_expr: &'gcx hir::Expr,
 271                           lhs_ty: Ty<'tcx>,
 272                           rhs_expr: &'gcx hir::Expr,
 273                           rhs_ty: Ty<'tcx>,
 274                           mut err: &mut errors::DiagnosticBuilder) -> bool {
 275         // If this function returns true it means a note was printed, so we don't need
 276         // to print the normal "implementation of `std::ops::Add` might be missing" note
 277         let mut is_string_addition = false;
 278         if let TyRef(_, l_ty) = lhs_ty.sty {
 279             if let TyRef(_, r_ty) = rhs_ty.sty {
 280                 if l_ty.ty.sty == TyStr && r_ty.ty.sty == TyStr {
 281                     err.note("`+` can't be used to concatenate two `&str` strings");
 282                     let codemap = self.tcx.sess.codemap();
 283                     let suggestion =
 284                         match (codemap.span_to_snippet(lhs_expr.span),
 285                                 codemap.span_to_snippet(rhs_expr.span)) {
 286                             (Ok(lstring), Ok(rstring)) =>
 287                                 format!("{}.to_owned() + {}", lstring, rstring),
 288                             _ => format!("<expression>")
 289                         };
 290                     err.span_suggestion(expr.span,
 291                         &format!("to_owned() can be used to create an owned `String` \
 292                                   from a string reference. String concatenation \
 293                                   appends the string on the right to the string \
 294                                   on the left and may require reallocation. This \
 295                                   requires ownership of the string on the left."), suggestion);
 296                     is_string_addition = true;
 297                 }
 298
 299             }
 300
 301         }
 302
 303         is_string_addition
 304     }
 305
 306     pub fn check_user_unop(&self,
 307                            op_str: &str,
 308                            mname: &str,
 309                            trait_did: Option<DefId>,
 310                            ex: &'gcx hir::Expr,
 311                            operand_expr: &'gcx hir::Expr,
 312                            operand_ty: Ty<'tcx>,
 313                            op: hir::UnOp)
 314                            -> Ty<'tcx>
 315     {
 316         assert!(op.is_by_value());
 317         let mname = Symbol::intern(mname);
 318         match self.lookup_op_method(ex, operand_ty, vec![], mname, trait_did, operand_expr) {
 319             Ok(t) => t,
 320             Err(()) => {
 321                 self.type_error_message(ex.span, |actual| {
 322                     format!("cannot apply unary operator `{}` to type `{}`",
 323                             op_str, actual)
 324                 }, operand_ty);
 325                 self.tcx.types.err
 326             }
 327         }
 328     }
 329
 330     fn name_and_trait_def_id(&self,
 331                              op: hir::BinOp,
 332                              is_assign: IsAssign)
 333                              -> (&'static str, Option<DefId>) {
 334         let lang = &self.tcx.lang_items;
 335
 336         if let IsAssign::Yes = is_assign {
 337             match op.node {
 338                 hir::BiAdd => ("add_assign", lang.add_assign_trait()),
 339                 hir::BiSub => ("sub_assign", lang.sub_assign_trait()),
 340                 hir::BiMul => ("mul_assign", lang.mul_assign_trait()),
 341                 hir::BiDiv => ("div_assign", lang.div_assign_trait()),
 342                 hir::BiRem => ("rem_assign", lang.rem_assign_trait()),
 343                 hir::BiBitXor => ("bitxor_assign", lang.bitxor_assign_trait()),
 344                 hir::BiBitAnd => ("bitand_assign", lang.bitand_assign_trait()),
 345                 hir::BiBitOr => ("bitor_assign", lang.bitor_assign_trait()),
 346                 hir::BiShl => ("shl_assign", lang.shl_assign_trait()),
 347                 hir::BiShr => ("shr_assign", lang.shr_assign_trait()),
 348                 hir::BiLt | hir::BiLe |
 349                 hir::BiGe | hir::BiGt |
 350                 hir::BiEq | hir::BiNe |
 351                 hir::BiAnd | hir::BiOr => {
 352                     span_bug!(op.span,
 353                               "impossible assignment operation: {}=",
 354                               op.node.as_str())
 355                 }
 356             }
 357         } else {
 358             match op.node {
 359                 hir::BiAdd => ("add", lang.add_trait()),
 360                 hir::BiSub => ("sub", lang.sub_trait()),
 361                 hir::BiMul => ("mul", lang.mul_trait()),
 362                 hir::BiDiv => ("div", lang.div_trait()),
 363                 hir::BiRem => ("rem", lang.rem_trait()),
 364                 hir::BiBitXor => ("bitxor", lang.bitxor_trait()),
 365                 hir::BiBitAnd => ("bitand", lang.bitand_trait()),
 366                 hir::BiBitOr => ("bitor", lang.bitor_trait()),
 367                 hir::BiShl => ("shl", lang.shl_trait()),
 368                 hir::BiShr => ("shr", lang.shr_trait()),
 369                 hir::BiLt => ("lt", lang.ord_trait()),
 370                 hir::BiLe => ("le", lang.ord_trait()),
 371                 hir::BiGe => ("ge", lang.ord_trait()),
 372                 hir::BiGt => ("gt", lang.ord_trait()),
 373                 hir::BiEq => ("eq", lang.eq_trait()),
 374                 hir::BiNe => ("ne", lang.eq_trait()),
 375                 hir::BiAnd | hir::BiOr => {
 376                     span_bug!(op.span, "&& and || are not overloadable")
 377                 }
 378             }
 379         }
 380     }
 381
 382     fn lookup_op_method(&self,
 383                         expr: &'gcx hir::Expr,
 384                         lhs_ty: Ty<'tcx>,
 385                         other_tys: Vec<Ty<'tcx>>,
 386                         opname: ast::Name,
 387                         trait_did: Option<DefId>,
 388                         lhs_expr: &'a hir::Expr)
 389                         -> Result<Ty<'tcx>,()>
 390     {
 391         debug!("lookup_op_method(expr={:?}, lhs_ty={:?}, opname={:?}, \
 392                                  trait_did={:?}, lhs_expr={:?})",
 393                expr,
 394                lhs_ty,
 395                opname,
 396                trait_did,
 397                lhs_expr);
 398
 399         let method = match trait_did {
 400             Some(trait_did) => {
 401                 self.lookup_method_in_trait_adjusted(expr.span,
 402                                                      Some(lhs_expr),
 403                                                      opname,
 404                                                      trait_did,
 405                                                      0,
 406                                                      false,
 407                                                      lhs_ty,
 408                                                      Some(other_tys))
 409             }
 410             None => None
 411         };
 412
 413         match method {
 414             Some(method) => {
 415                 let method_ty = method.ty;
 416
 417                 // HACK(eddyb) Fully qualified path to work around a resolve bug.
 418                 let method_call = ::rustc::ty::MethodCall::expr(expr.id);
 419                 self.tables.borrow_mut().method_map.insert(method_call, method);
 420
 421                 // extract return type for method; all late bound regions
 422                 // should have been instantiated by now
 423                 let ret_ty = method_ty.fn_ret();
 424                 Ok(self.tcx.no_late_bound_regions(&ret_ty).unwrap())
 425             }
 426             None => {
 427                 Err(())
 428             }
 429         }
 430     }
 431 }
 432
 433 // Binary operator categories. These categories summarize the behavior
 434 // with respect to the builtin operationrs supported.
 435 enum BinOpCategory {
 436     /// &&, || -- cannot be overridden
 437     Shortcircuit,
 438
 439     /// <<, >> -- when shifting a single integer, rhs can be any
 440     /// integer type. For simd, types must match.
 441     Shift,
 442
 443     /// +, -, etc -- takes equal types, produces same type as input,
 444     /// applicable to ints/floats/simd
 445     Math,
 446
 447     /// &, |, ^ -- takes equal types, produces same type as input,
 448     /// applicable to ints/floats/simd/bool
 449     Bitwise,
 450
 451     /// ==, !=, etc -- takes equal types, produces bools, except for simd,
 452     /// which produce the input type
 453     Comparison,
 454 }
 455
 456 impl BinOpCategory {
 457     fn from(op: hir::BinOp) -> BinOpCategory {
 458         match op.node {
 459             hir::BiShl | hir::BiShr =>
 460                 BinOpCategory::Shift,
 461
 462             hir::BiAdd |
 463             hir::BiSub |
 464             hir::BiMul |
 465             hir::BiDiv |
 466             hir::BiRem =>
 467                 BinOpCategory::Math,
 468
 469             hir::BiBitXor |
 470             hir::BiBitAnd |
 471             hir::BiBitOr =>
 472                 BinOpCategory::Bitwise,
 473
 474             hir::BiEq |
 475             hir::BiNe |
 476             hir::BiLt |
 477             hir::BiLe |
 478             hir::BiGe |
 479             hir::BiGt =>
 480                 BinOpCategory::Comparison,
 481
 482             hir::BiAnd |
 483             hir::BiOr =>
 484                 BinOpCategory::Shortcircuit,
 485         }
 486     }
 487 }
 488
 489 /// Whether the binary operation is an assignment (`a += b`), or not (`a + b`)
 490 #[derive(Clone, Copy, Debug)]
 491 enum IsAssign {
 492     No,
 493     Yes,
 494 }
 495
 496 /// Returns true if this is a built-in arithmetic operation (e.g. u32
 497 /// + u32, i16x4 == i16x4) and false if these types would have to be
 498 /// overloaded to be legal. There are two reasons that we distinguish
 499 /// builtin operations from overloaded ones (vs trying to drive
 500 /// everything uniformly through the trait system and intrinsics or
 501 /// something like that):
 502 ///
 503 /// 1. Builtin operations can trivially be evaluated in constants.
 504 /// 2. For comparison operators applied to SIMD types the result is
 505 ///    not of type `bool`. For example, `i16x4==i16x4` yields a
 506 ///    type like `i16x4`. This means that the overloaded trait
 507 ///    `PartialEq` is not applicable.
 508 ///
 509 /// Reason #2 is the killer. I tried for a while to always use
 510 /// overloaded logic and just check the types in constants/trans after
 511 /// the fact, and it worked fine, except for SIMD types. -nmatsakis
 512 fn is_builtin_binop(lhs: Ty, rhs: Ty, op: hir::BinOp) -> bool {
 513     match BinOpCategory::from(op) {
 514         BinOpCategory::Shortcircuit => {
 515             true
 516         }
 517
 518         BinOpCategory::Shift => {
 519             lhs.references_error() || rhs.references_error() ||
 520                 lhs.is_integral() && rhs.is_integral()
 521         }
 522
 523         BinOpCategory::Math => {
 524             lhs.references_error() || rhs.references_error() ||
 525                 lhs.is_integral() && rhs.is_integral() ||
 526                 lhs.is_floating_point() && rhs.is_floating_point()
 527         }
 528
 529         BinOpCategory::Bitwise => {
 530             lhs.references_error() || rhs.references_error() ||
 531                 lhs.is_integral() && rhs.is_integral() ||
 532                 lhs.is_floating_point() && rhs.is_floating_point() ||
 533                 lhs.is_bool() && rhs.is_bool()
 534         }
 535
 536         BinOpCategory::Comparison => {
 537             lhs.references_error() || rhs.references_error() ||
 538                 lhs.is_scalar() && rhs.is_scalar()
 539         }
 540     }
 541 }