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