Merge #1694

1694: Implement initial type-inference support for Index r=flodiebold a=matklad

This doesn't actually infer indexing types, but at least it walks sub-expressions!

Initially, I wanted to make `Index` just a new kind of `BinOp` (b/c indexing is kind of a binary op), so I've refactoring binop handing a bit.

However, in the end I've decided to add a separate expr kind for Index, because `foo[0]`, `&foo[1]` and `&mut foo[1]` all seem to need slightly different handing, which is not binop-like

r? @flodiebold 

Co-authored-by: Aleksey Kladov <[email protected]>

4 files changed, 143 insertions, 74 deletions

diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir/src/expr.rs
index f33676655..a16561d11 100644
--- a/crates/ra_hir/src/expr.rs
+++ b/crates/ra_hir/src/expr.rs
@@ -245,6 +245,10 @@ pub enum Expr {
         rhs: ExprId,
         op: Option<BinaryOp>,
     },
+    Index {
+        base: ExprId,
+        index: ExprId,
+    },
     Lambda {
         args: Vec<PatId>,
         arg_types: Vec<Option<TypeRef>>,
@@ -257,7 +261,46 @@ pub enum Expr {
     Literal(Literal),
 }
 
-pub use ra_syntax::ast::BinOp as BinaryOp;
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum BinaryOp {
+    LogicOp(LogicOp),
+    ArithOp(ArithOp),
+    CmpOp(CmpOp),
+    Assignment { op: Option<ArithOp> },
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum LogicOp {
+    And,
+    Or,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum CmpOp {
+    Eq { negated: bool },
+    Ord { ordering: Ordering, strict: bool },
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum Ordering {
+    Less,
+    Greater,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum ArithOp {
+    Add,
+    Mul,
+    Sub,
+    Div,
+    Rem,
+    Shl,
+    Shr,
+    BitXor,
+    BitOr,
+    BitAnd,
+}
+
 pub use ra_syntax::ast::PrefixOp as UnaryOp;
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub enum Array {
@@ -360,6 +403,10 @@ impl Expr {
                 f(*lhs);
                 f(*rhs);
             }
+            Expr::Index { base, index } => {
+                f(*base);
+                f(*index);
+            }
             Expr::Field { expr, .. }
             | Expr::Await { expr }
             | Expr::Try { expr }
@@ -791,7 +838,7 @@ where
             ast::ExprKind::BinExpr(e) => {
                 let lhs = self.collect_expr_opt(e.lhs());
                 let rhs = self.collect_expr_opt(e.rhs());
-                let op = e.op_kind();
+                let op = e.op_kind().map(BinaryOp::from);
                 self.alloc_expr(Expr::BinaryOp { lhs, rhs, op }, syntax_ptr)
             }
             ast::ExprKind::TupleExpr(e) => {
@@ -848,10 +895,14 @@ where
                 };
                 self.alloc_expr(Expr::Literal(lit), syntax_ptr)
             }
+            ast::ExprKind::IndexExpr(e) => {
+                let base = self.collect_expr_opt(e.base());
+                let index = self.collect_expr_opt(e.index());
+                self.alloc_expr(Expr::Index { base, index }, syntax_ptr)
+            }
 
             // FIXME implement HIR for these:
             ast::ExprKind::Label(_e) => self.alloc_expr(Expr::Missing, syntax_ptr),
-            ast::ExprKind::IndexExpr(_e) => self.alloc_expr(Expr::Missing, syntax_ptr),
             ast::ExprKind::RangeExpr(_e) => self.alloc_expr(Expr::Missing, syntax_ptr),
             ast::ExprKind::MacroCall(e) => {
                 let ast_id = self
@@ -1038,6 +1089,50 @@ where
     }
 }
 
+impl From<ast::BinOp> for BinaryOp {
+    fn from(ast_op: ast::BinOp) -> Self {
+        match ast_op {
+            ast::BinOp::BooleanOr => BinaryOp::LogicOp(LogicOp::Or),
+            ast::BinOp::BooleanAnd => BinaryOp::LogicOp(LogicOp::And),
+            ast::BinOp::EqualityTest => BinaryOp::CmpOp(CmpOp::Eq { negated: false }),
+            ast::BinOp::NegatedEqualityTest => BinaryOp::CmpOp(CmpOp::Eq { negated: true }),
+            ast::BinOp::LesserEqualTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Less, strict: false })
+            }
+            ast::BinOp::GreaterEqualTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Greater, strict: false })
+            }
+            ast::BinOp::LesserTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Less, strict: true })
+            }
+            ast::BinOp::GreaterTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Greater, strict: true })
+            }
+            ast::BinOp::Addition => BinaryOp::ArithOp(ArithOp::Add),
+            ast::BinOp::Multiplication => BinaryOp::ArithOp(ArithOp::Mul),
+            ast::BinOp::Subtraction => BinaryOp::ArithOp(ArithOp::Sub),
+            ast::BinOp::Division => BinaryOp::ArithOp(ArithOp::Div),
+            ast::BinOp::Remainder => BinaryOp::ArithOp(ArithOp::Rem),
+            ast::BinOp::LeftShift => BinaryOp::ArithOp(ArithOp::Shl),
+            ast::BinOp::RightShift => BinaryOp::ArithOp(ArithOp::Shr),
+            ast::BinOp::BitwiseXor => BinaryOp::ArithOp(ArithOp::BitXor),
+            ast::BinOp::BitwiseOr => BinaryOp::ArithOp(ArithOp::BitOr),
+            ast::BinOp::BitwiseAnd => BinaryOp::ArithOp(ArithOp::BitAnd),
+            ast::BinOp::Assignment => BinaryOp::Assignment { op: None },
+            ast::BinOp::AddAssign => BinaryOp::Assignment { op: Some(ArithOp::Add) },
+            ast::BinOp::DivAssign => BinaryOp::Assignment { op: Some(ArithOp::Div) },
+            ast::BinOp::MulAssign => BinaryOp::Assignment { op: Some(ArithOp::Mul) },
+            ast::BinOp::RemAssign => BinaryOp::Assignment { op: Some(ArithOp::Rem) },
+            ast::BinOp::ShlAssign => BinaryOp::Assignment { op: Some(ArithOp::Shl) },
+            ast::BinOp::ShrAssign => BinaryOp::Assignment { op: Some(ArithOp::Shr) },
+            ast::BinOp::SubAssign => BinaryOp::Assignment { op: Some(ArithOp::Sub) },
+            ast::BinOp::BitOrAssign => BinaryOp::Assignment { op: Some(ArithOp::BitOr) },
+            ast::BinOp::BitAndAssign => BinaryOp::Assignment { op: Some(ArithOp::BitAnd) },
+            ast::BinOp::BitXorAssign => BinaryOp::Assignment { op: Some(ArithOp::BitXor) },
+        }
+    }
+}
+
 pub(crate) fn body_with_source_map_query(
     db: &impl HirDatabase,
     def: DefWithBody,
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 675df4a22..cca59538a 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -1265,9 +1265,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             Expr::BinaryOp { lhs, rhs, op } => match op {
                 Some(op) => {
                     let lhs_expectation = match op {
-                        BinaryOp::BooleanAnd | BinaryOp::BooleanOr => {
-                            Expectation::has_type(Ty::simple(TypeCtor::Bool))
-                        }
+                        BinaryOp::LogicOp(..) => Expectation::has_type(Ty::simple(TypeCtor::Bool)),
                         _ => Expectation::none(),
                     };
                     let lhs_ty = self.infer_expr(*lhs, &lhs_expectation);
@@ -1281,6 +1279,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
                 _ => Ty::Unknown,
             },
+            Expr::Index { base, index } => {
+                let _base_ty = self.infer_expr(*base, &Expectation::none());
+                let _index_ty = self.infer_expr(*index, &Expectation::none());
+                // FIXME: use `std::ops::Index::Output` to figure out the real return type
+                Ty::Unknown
+            }
             Expr::Tuple { exprs } => {
                 let mut ty_vec = Vec::with_capacity(exprs.len());
                 for arg in exprs.iter() {
diff --git a/crates/ra_hir/src/ty/op.rs b/crates/ra_hir/src/ty/op.rs
index 9ba868298..1b30a5b9b 100644
--- a/crates/ra_hir/src/ty/op.rs
+++ b/crates/ra_hir/src/ty/op.rs
@@ -1,37 +1,14 @@
 use super::{InferTy, Ty, TypeCtor};
-use crate::{expr::BinaryOp, ty::ApplicationTy};
+use crate::{
+    expr::{BinaryOp, CmpOp},
+    ty::ApplicationTy,
+};
 
 pub(super) fn binary_op_return_ty(op: BinaryOp, rhs_ty: Ty) -> Ty {
     match op {
-        BinaryOp::BooleanOr
-        | BinaryOp::BooleanAnd
-        | BinaryOp::EqualityTest
-        | BinaryOp::NegatedEqualityTest
-        | BinaryOp::LesserEqualTest
-        | BinaryOp::GreaterEqualTest
-        | BinaryOp::LesserTest
-        | BinaryOp::GreaterTest => Ty::simple(TypeCtor::Bool),
-        BinaryOp::Assignment
-        | BinaryOp::AddAssign
-        | BinaryOp::SubAssign
-        | BinaryOp::DivAssign
-        | BinaryOp::MulAssign
-        | BinaryOp::RemAssign
-        | BinaryOp::ShrAssign
-        | BinaryOp::ShlAssign
-        | BinaryOp::BitAndAssign
-        | BinaryOp::BitOrAssign
-        | BinaryOp::BitXorAssign => Ty::unit(),
-        BinaryOp::Addition
-        | BinaryOp::Subtraction
-        | BinaryOp::Multiplication
-        | BinaryOp::Division
-        | BinaryOp::Remainder
-        | BinaryOp::LeftShift
-        | BinaryOp::RightShift
-        | BinaryOp::BitwiseAnd
-        | BinaryOp::BitwiseOr
-        | BinaryOp::BitwiseXor => match rhs_ty {
+        BinaryOp::LogicOp(_) | BinaryOp::CmpOp(_) => Ty::simple(TypeCtor::Bool),
+        BinaryOp::Assignment { .. } => Ty::unit(),
+        BinaryOp::ArithOp(_) => match rhs_ty {
             Ty::Apply(ApplicationTy { ctor, .. }) => match ctor {
                 TypeCtor::Int(..) | TypeCtor::Float(..) => rhs_ty,
                 _ => Ty::Unknown,
@@ -39,49 +16,29 @@ pub(super) fn binary_op_return_ty(op: BinaryOp, rhs_ty: Ty) -> Ty {
             Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => rhs_ty,
             _ => Ty::Unknown,
         },
-        BinaryOp::RangeRightOpen | BinaryOp::RangeRightClosed => Ty::Unknown,
     }
 }
 
 pub(super) fn binary_op_rhs_expectation(op: BinaryOp, lhs_ty: Ty) -> Ty {
     match op {
-        BinaryOp::BooleanAnd | BinaryOp::BooleanOr => Ty::simple(TypeCtor::Bool),
-        BinaryOp::Assignment | BinaryOp::EqualityTest => match lhs_ty {
-            Ty::Apply(ApplicationTy { ctor, .. }) => match ctor {
-                TypeCtor::Int(..)
-                | TypeCtor::Float(..)
-                | TypeCtor::Str
-                | TypeCtor::Char
-                | TypeCtor::Bool => lhs_ty,
+        BinaryOp::LogicOp(..) => Ty::simple(TypeCtor::Bool),
+        BinaryOp::Assignment { op: None } | BinaryOp::CmpOp(CmpOp::Eq { negated: _ }) => {
+            match lhs_ty {
+                Ty::Apply(ApplicationTy { ctor, .. }) => match ctor {
+                    TypeCtor::Int(..)
+                    | TypeCtor::Float(..)
+                    | TypeCtor::Str
+                    | TypeCtor::Char
+                    | TypeCtor::Bool => lhs_ty,
+                    _ => Ty::Unknown,
+                },
+                Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => lhs_ty,
                 _ => Ty::Unknown,
-            },
-            Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => lhs_ty,
-            _ => Ty::Unknown,
-        },
-        BinaryOp::LesserEqualTest
-        | BinaryOp::GreaterEqualTest
-        | BinaryOp::LesserTest
-        | BinaryOp::GreaterTest
-        | BinaryOp::AddAssign
-        | BinaryOp::SubAssign
-        | BinaryOp::DivAssign
-        | BinaryOp::MulAssign
-        | BinaryOp::RemAssign
-        | BinaryOp::ShrAssign
-        | BinaryOp::ShlAssign
-        | BinaryOp::BitAndAssign
-        | BinaryOp::BitOrAssign
-        | BinaryOp::BitXorAssign
-        | BinaryOp::Addition
-        | BinaryOp::Subtraction
-        | BinaryOp::Multiplication
-        | BinaryOp::Division
-        | BinaryOp::Remainder
-        | BinaryOp::LeftShift
-        | BinaryOp::RightShift
-        | BinaryOp::BitwiseAnd
-        | BinaryOp::BitwiseOr
-        | BinaryOp::BitwiseXor => match lhs_ty {
+            }
+        }
+        BinaryOp::CmpOp(CmpOp::Ord { .. })
+        | BinaryOp::Assignment { op: Some(_) }
+        | BinaryOp::ArithOp(_) => match lhs_ty {
             Ty::Apply(ApplicationTy { ctor, .. }) => match ctor {
                 TypeCtor::Int(..) | TypeCtor::Float(..) => lhs_ty,
                 _ => Ty::Unknown,
@@ -89,6 +46,5 @@ pub(super) fn binary_op_rhs_expectation(op: BinaryOp, lhs_ty: Ty) -> Ty {
             Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => lhs_ty,
             _ => Ty::Unknown,
         },
-        _ => Ty::Unknown,
     }
 }
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 28727bb18..6c2d857bc 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2656,6 +2656,20 @@ fn test() -> u64 {
 }
 
 #[test]
+fn indexing_arrays() {
+    assert_snapshot_matches!(
+        infer("fn main() { &mut [9][2]; }"),
+        @r###"
+[10; 26) '{ &mut...[2]; }': ()
+[12; 23) '&mut [9][2]': &mut {unknown}
+[17; 20) '[9]': [i32;_]
+[17; 23) '[9][2]': {unknown}
+[18; 19) '9': i32
+[21; 22) '2': i32"###
+    )
+}
+
+#[test]
 fn infer_macros_expanded() {
     assert_snapshot_matches!(
         infer(r#"