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]>

5 files changed, 186 insertions, 113 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#"
diff --git a/crates/ra_syntax/src/ast/expr_extensions.rs b/crates/ra_syntax/src/ast/expr_extensions.rs
index 8284f1b25..cf5b6f251 100644
--- a/crates/ra_syntax/src/ast/expr_extensions.rs
+++ b/crates/ra_syntax/src/ast/expr_extensions.rs
@@ -102,10 +102,6 @@ pub enum BinOp {
     BitwiseOr,
     /// The `&` operator for bitwise AND
     BitwiseAnd,
-    /// The `..` operator for right-open ranges
-    RangeRightOpen,
-    /// The `..=` operator for right-closed ranges
-    RangeRightClosed,
     /// The `=` operator for assignment
     Assignment,
     /// The `+=` operator for assignment after addition
@@ -132,41 +128,40 @@ pub enum BinOp {
 
 impl ast::BinExpr {
     fn op_details(&self) -> Option<(SyntaxToken, BinOp)> {
-        self.syntax().children_with_tokens().filter_map(|it| it.into_token()).find_map(|c| match c
-            .kind()
-        {
-            T![||] => Some((c, BinOp::BooleanOr)),
-            T![&&] => Some((c, BinOp::BooleanAnd)),
-            T![==] => Some((c, BinOp::EqualityTest)),
-            T![!=] => Some((c, BinOp::NegatedEqualityTest)),
-            T![<=] => Some((c, BinOp::LesserEqualTest)),
-            T![>=] => Some((c, BinOp::GreaterEqualTest)),
-            T![<] => Some((c, BinOp::LesserTest)),
-            T![>] => Some((c, BinOp::GreaterTest)),
-            T![+] => Some((c, BinOp::Addition)),
-            T![*] => Some((c, BinOp::Multiplication)),
-            T![-] => Some((c, BinOp::Subtraction)),
-            T![/] => Some((c, BinOp::Division)),
-            T![%] => Some((c, BinOp::Remainder)),
-            T![<<] => Some((c, BinOp::LeftShift)),
-            T![>>] => Some((c, BinOp::RightShift)),
-            T![^] => Some((c, BinOp::BitwiseXor)),
-            T![|] => Some((c, BinOp::BitwiseOr)),
-            T![&] => Some((c, BinOp::BitwiseAnd)),
-            T![..] => Some((c, BinOp::RangeRightOpen)),
-            T![..=] => Some((c, BinOp::RangeRightClosed)),
-            T![=] => Some((c, BinOp::Assignment)),
-            T![+=] => Some((c, BinOp::AddAssign)),
-            T![/=] => Some((c, BinOp::DivAssign)),
-            T![*=] => Some((c, BinOp::MulAssign)),
-            T![%=] => Some((c, BinOp::RemAssign)),
-            T![>>=] => Some((c, BinOp::ShrAssign)),
-            T![<<=] => Some((c, BinOp::ShlAssign)),
-            T![-=] => Some((c, BinOp::SubAssign)),
-            T![|=] => Some((c, BinOp::BitOrAssign)),
-            T![&=] => Some((c, BinOp::BitAndAssign)),
-            T![^=] => Some((c, BinOp::BitXorAssign)),
-            _ => None,
+        self.syntax().children_with_tokens().filter_map(|it| it.into_token()).find_map(|c| {
+            let bin_op = match c.kind() {
+                T![||] => BinOp::BooleanOr,
+                T![&&] => BinOp::BooleanAnd,
+                T![==] => BinOp::EqualityTest,
+                T![!=] => BinOp::NegatedEqualityTest,
+                T![<=] => BinOp::LesserEqualTest,
+                T![>=] => BinOp::GreaterEqualTest,
+                T![<] => BinOp::LesserTest,
+                T![>] => BinOp::GreaterTest,
+                T![+] => BinOp::Addition,
+                T![*] => BinOp::Multiplication,
+                T![-] => BinOp::Subtraction,
+                T![/] => BinOp::Division,
+                T![%] => BinOp::Remainder,
+                T![<<] => BinOp::LeftShift,
+                T![>>] => BinOp::RightShift,
+                T![^] => BinOp::BitwiseXor,
+                T![|] => BinOp::BitwiseOr,
+                T![&] => BinOp::BitwiseAnd,
+                T![=] => BinOp::Assignment,
+                T![+=] => BinOp::AddAssign,
+                T![/=] => BinOp::DivAssign,
+                T![*=] => BinOp::MulAssign,
+                T![%=] => BinOp::RemAssign,
+                T![>>=] => BinOp::ShrAssign,
+                T![<<=] => BinOp::ShlAssign,
+                T![-=] => BinOp::SubAssign,
+                T![|=] => BinOp::BitOrAssign,
+                T![&=] => BinOp::BitAndAssign,
+                T![^=] => BinOp::BitXorAssign,
+                _ => return None,
+            };
+            Some((c, bin_op))
         })
     }
 
@@ -194,6 +189,15 @@ impl ast::BinExpr {
     }
 }
 
+impl ast::IndexExpr {
+    pub fn base(&self) -> Option<ast::Expr> {
+        children(self).nth(0)
+    }
+    pub fn index(&self) -> Option<ast::Expr> {
+        children(self).nth(1)
+    }
+}
+
 pub enum ArrayExprKind {
     Repeat { initializer: Option<ast::Expr>, repeat: Option<ast::Expr> },
     ElementList(AstChildren<ast::Expr>),