Add more tests, refactor array lengths/consteval work

Fix #2922: add unknown length as a condition for a type having unknown.

Incorporate reviews:

* Extract some of the const evaluation workings into functions
* Add fixmes on the hacks
* Add tests for impls on specific array lengths (these work!!! 😁)
* Add tests for const generics (indeed we don't support it yet)

8 files changed, 223 insertions, 35 deletions

diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index c9ef4b420..d7065ff2b 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -52,7 +52,9 @@ use hir_def::{
 };
 use hir_expand::{diagnostics::DiagnosticSink, name::name, MacroDefKind};
 use hir_ty::{
-    autoderef, could_unify,
+    autoderef,
+    consteval::ConstExtension,
+    could_unify,
     method_resolution::{self, def_crates, TyFingerprint},
     primitive::UintTy,
     subst_prefix,
@@ -1910,6 +1912,7 @@ impl Type {
                     substs.iter(&Interner).filter_map(|a| a.ty(&Interner)).any(go)
                 }
 
+                TyKind::Array(_ty, len) if len.is_unknown() => true,
                 TyKind::Array(ty, _)
                 | TyKind::Slice(ty)
                 | TyKind::Raw(_, ty)
diff --git a/crates/hir_def/src/type_ref.rs b/crates/hir_def/src/type_ref.rs
index 00c09a23d..6a3259b27 100644
--- a/crates/hir_def/src/type_ref.rs
+++ b/crates/hir_def/src/type_ref.rs
@@ -80,6 +80,8 @@ pub enum TypeRef {
     Path(Path),
     RawPtr(Box<TypeRef>, Mutability),
     Reference(Box<TypeRef>, Option<LifetimeRef>, Mutability),
+    // FIXME: for full const generics, the latter element (length) here is going to have to be an
+    // expression that is further lowered later in hir_ty.
     Array(Box<TypeRef>, ConstScalar),
     Slice(Box<TypeRef>),
     /// A fn pointer. Last element of the vector is the return type.
@@ -141,6 +143,10 @@ impl TypeRef {
                 TypeRef::RawPtr(Box::new(inner_ty), mutability)
             }
             ast::Type::ArrayType(inner) => {
+                // FIXME: This is a hack. We should probably reuse the machinery of
+                // `hir_def::body::lower` to lower this into an `Expr` and then evaluate it at the
+                // `hir_ty` level, which would allow knowing the type of:
+                // let v: [u8; 2 + 2] = [0u8; 4];
                 let len = inner
                     .expr()
                     .map(ConstScalar::usize_from_literal_expr)
@@ -313,6 +319,10 @@ pub enum ConstScalar {
     Usize(u64),
 
     /// Case of an unknown value that rustc might know but we don't
+    // FIXME: this is a hack to get around chalk not being able to represent unevaluatable
+    // constants
+    // https://github.com/rust-analyzer/rust-analyzer/pull/8813#issuecomment-840679177
+    // https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/Handling.20non.20evaluatable.20constants'.20equality/near/238386348
     Unknown,
 }
 
@@ -326,6 +336,8 @@ impl std::fmt::Display for ConstScalar {
 }
 
 impl ConstScalar {
+    // FIXME: as per the comments on `TypeRef::Array`, this evaluation should not happen at this
+    // parse stage.
     fn usize_from_literal_expr(expr: ast::Expr) -> ConstScalar {
         match expr {
             ast::Expr::Literal(lit) => {
diff --git a/crates/hir_ty/src/consteval.rs b/crates/hir_ty/src/consteval.rs
new file mode 100644
index 000000000..a4a430f30
--- /dev/null
+++ b/crates/hir_ty/src/consteval.rs
@@ -0,0 +1,64 @@
+//! Constant evaluation details
+
+use std::convert::TryInto;
+
+use hir_def::{
+    builtin_type::BuiltinUint,
+    expr::{Expr, Literal},
+    type_ref::ConstScalar,
+};
+
+use crate::{Const, ConstData, ConstValue, Interner, TyKind};
+
+/// Extension trait for [`Const`]
+pub trait ConstExtension {
+    /// Is a [`Const`] unknown?
+    fn is_unknown(&self) -> bool;
+}
+
+impl ConstExtension for Const {
+    fn is_unknown(&self) -> bool {
+        match self.data(&Interner).value {
+            // interned Unknown
+            chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
+                interned: ConstScalar::Unknown,
+            }) => true,
+
+            // interned concrete anything else
+            chalk_ir::ConstValue::Concrete(..) => false,
+
+            _ => {
+                log::error!("is_unknown was called on a non-concrete constant value! {:?}", self);
+                true
+            }
+        }
+    }
+}
+
+/// Extension trait for [`Expr`]
+pub trait ExprEval {
+    /// Attempts to evaluate the expression as a target usize.
+    fn eval_usize(&self) -> Option<u64>;
+}
+
+impl ExprEval for Expr {
+    // FIXME: support more than just evaluating literals
+    fn eval_usize(&self) -> Option<u64> {
+        match self {
+            Expr::Literal(Literal::Uint(v, None))
+            | Expr::Literal(Literal::Uint(v, Some(BuiltinUint::Usize))) => (*v).try_into().ok(),
+            _ => None,
+        }
+    }
+}
+
+/// Interns a possibly-unknown target usize
+pub fn usize_const(value: Option<u64>) -> Const {
+    ConstData {
+        ty: TyKind::Scalar(chalk_ir::Scalar::Uint(chalk_ir::UintTy::Usize)).intern(&Interner),
+        value: ConstValue::Concrete(chalk_ir::ConcreteConst {
+            interned: value.map(|value| ConstScalar::Usize(value)).unwrap_or(ConstScalar::Unknown),
+        }),
+    }
+    .intern(&Interner)
+}
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 0b36ac861..04fc2f12b 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -1,18 +1,13 @@
 //! Type inference for expressions.
 
-use std::{
-    convert::TryInto,
-    iter::{repeat, repeat_with},
-};
+use std::iter::{repeat, repeat_with};
 use std::{mem, sync::Arc};
 
-use chalk_ir::{cast::Cast, fold::Shift, ConstData, Mutability, TyVariableKind};
+use chalk_ir::{cast::Cast, fold::Shift, Mutability, TyVariableKind};
 use hir_def::{
-    builtin_type::BuiltinUint,
     expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp},
     path::{GenericArg, GenericArgs},
     resolver::resolver_for_expr,
-    type_ref::ConstScalar,
     AssocContainerId, FieldId, Lookup,
 };
 use hir_expand::name::{name, Name};
@@ -21,6 +16,7 @@ use syntax::ast::RangeOp;
 
 use crate::{
     autoderef,
+    consteval::{self, ExprEval},
     lower::lower_to_chalk_mutability,
     mapping::from_chalk,
     method_resolution, op,
@@ -28,9 +24,8 @@ use crate::{
     static_lifetime, to_chalk_trait_id,
     traits::FnTrait,
     utils::{generics, Generics},
-    AdtId, Binders, CallableDefId, ConcreteConst, ConstValue, FnPointer, FnSig, FnSubst,
-    InEnvironment, Interner, ProjectionTyExt, Rawness, Scalar, Substitution, TraitRef, Ty,
-    TyBuilder, TyExt, TyKind,
+    AdtId, Binders, CallableDefId, FnPointer, FnSig, FnSubst, InEnvironment, Interner,
+    ProjectionTyExt, Rawness, Scalar, Substitution, TraitRef, Ty, TyBuilder, TyExt, TyKind,
 };
 
 use super::{
@@ -743,25 +738,11 @@ impl<'a> InferenceContext<'a> {
                         );
 
                         let repeat_expr = &self.body.exprs[*repeat];
-                        match repeat_expr {
-                            Expr::Literal(Literal::Uint(v, None))
-                            | Expr::Literal(Literal::Uint(v, Some(BuiltinUint::Usize))) => {
-                                (*v).try_into().ok()
-                            }
-                            _ => None,
-                        }
+                        repeat_expr.eval_usize()
                     }
                 };
 
-                let cd = ConstData {
-                    ty: TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner),
-                    value: ConstValue::Concrete(chalk_ir::ConcreteConst {
-                        interned: len
-                            .map(|len| ConstScalar::Usize(len))
-                            .unwrap_or(ConstScalar::Unknown),
-                    }),
-                };
-                TyKind::Array(elem_ty, cd.intern(&Interner)).intern(&Interner)
+                TyKind::Array(elem_ty, consteval::usize_const(len)).intern(&Interner)
             }
             Expr::Literal(lit) => match lit {
                 Literal::Bool(..) => TyKind::Scalar(Scalar::Bool).intern(&Interner),
@@ -772,13 +753,7 @@ impl<'a> InferenceContext<'a> {
                 Literal::ByteString(bs) => {
                     let byte_type = TyKind::Scalar(Scalar::Uint(UintTy::U8)).intern(&Interner);
 
-                    let len = ConstData {
-                        ty: TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner),
-                        value: ConstValue::Concrete(ConcreteConst {
-                            interned: ConstScalar::Usize(bs.len() as u64),
-                        }),
-                    }
-                    .intern(&Interner);
+                    let len = consteval::usize_const(Some(bs.len() as u64));
 
                     let array_type = TyKind::Array(byte_type, len).intern(&Interner);
                     TyKind::Ref(Mutability::Not, static_lifetime(), array_type).intern(&Interner)
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index be3f55bdf..15b61bedc 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -10,6 +10,7 @@ mod autoderef;
 mod builder;
 mod chalk_db;
 mod chalk_ext;
+pub mod consteval;
 mod infer;
 mod interner;
 mod lower;
diff --git a/crates/hir_ty/src/tests/simple.rs b/crates/hir_ty/src/tests/simple.rs
index 1032f09ac..a9cd42186 100644
--- a/crates/hir_ty/src/tests/simple.rs
+++ b/crates/hir_ty/src/tests/simple.rs
@@ -1271,12 +1271,14 @@ fn infer_array() {
 
             let b = [a, ["b"]];
             let x: [u8; 0] = [];
+            // FIXME: requires const evaluation/taking type from rhs somehow
+            let y: [u8; 2+2] = [1,2,3,4];
         }
         "#,
         expect![[r#"
             8..9 'x': &str
             17..18 'y': isize
-            27..292 '{     ... []; }': ()
+            27..395 '{     ...,4]; }': ()
             37..38 'a': [&str; 1]
             41..44 '[x]': [&str; 1]
             42..43 'x': &str
@@ -1326,6 +1328,12 @@ fn infer_array() {
             259..262 '"b"': &str
             274..275 'x': [u8; 0]
             287..289 '[]': [u8; 0]
+            368..369 'y': [u8; _]
+            383..392 '[1,2,3,4]': [u8; 4]
+            384..385 '1': u8
+            386..387 '2': u8
+            388..389 '3': u8
+            390..391 '4': u8
         "#]],
     );
 }
diff --git a/crates/hir_ty/src/tests/traits.rs b/crates/hir_ty/src/tests/traits.rs
index 47a1455fd..f80cf9879 100644
--- a/crates/hir_ty/src/tests/traits.rs
+++ b/crates/hir_ty/src/tests/traits.rs
@@ -3474,3 +3474,100 @@ fn main(){
         "#]],
     )
 }
+
+#[test]
+fn array_length() {
+    check_infer(
+        r#"
+trait T {
+    type Output;
+    fn do_thing(&self) -> Self::Output;
+}
+
+impl T for [u8; 4] {
+    type Output = usize;
+    fn do_thing(&self) -> Self::Output {
+        2
+    }
+}
+
+impl T for [u8; 2] {
+    type Output = u8;
+    fn do_thing(&self) -> Self::Output {
+        2
+    }
+}
+
+fn main() {
+    let v = [0u8; 2];
+    let v2 = v.do_thing();
+    let v3 = [0u8; 4];
+    let v4 = v3.do_thing();
+}
+"#,
+        expect![[r#"
+            44..48 'self': &Self
+            133..137 'self': &[u8; 4]
+            155..172 '{     ...     }': usize
+            165..166 '2': usize
+            236..240 'self': &[u8; 2]
+            258..275 '{     ...     }': u8
+            268..269 '2': u8
+            289..392 '{     ...g(); }': ()
+            299..300 'v': [u8; 2]
+            303..311 '[0u8; 2]': [u8; 2]
+            304..307 '0u8': u8
+            309..310 '2': usize
+            321..323 'v2': u8
+            326..327 'v': [u8; 2]
+            326..338 'v.do_thing()': u8
+            348..350 'v3': [u8; 4]
+            353..361 '[0u8; 4]': [u8; 4]
+            354..357 '0u8': u8
+            359..360 '4': usize
+            371..373 'v4': usize
+            376..378 'v3': [u8; 4]
+            376..389 'v3.do_thing()': usize
+        "#]],
+    )
+}
+
+// FIXME: We should infer the length of the returned array :)
+#[test]
+fn const_generics() {
+    check_infer(
+        r#"
+trait T {
+    type Output;
+    fn do_thing(&self) -> Self::Output;
+}
+
+impl<const L: usize> T for [u8; L] {
+    type Output = [u8; L];
+    fn do_thing(&self) -> Self::Output {
+        *self
+    }
+}
+
+fn main() {
+    let v = [0u8; 2];
+    let v2 = v.do_thing();
+}
+"#,
+        expect![[r#"
+            44..48 'self': &Self
+            151..155 'self': &[u8; _]
+            173..194 '{     ...     }': [u8; _]
+            183..188 '*self': [u8; _]
+            184..188 'self': &[u8; _]
+            208..260 '{     ...g(); }': ()
+            218..219 'v': [u8; 2]
+            222..230 '[0u8; 2]': [u8; 2]
+            223..226 '0u8': u8
+            228..229 '2': usize
+            240..242 'v2': [u8; _]
+            245..246 'v': [u8; 2]
+            245..257 'v.do_thing()': [u8; _]
+        "#]],
+    )
+}
diff --git a/crates/ide_assists/src/handlers/add_explicit_type.rs b/crates/ide_assists/src/handlers/add_explicit_type.rs
index 62db31952..36589203d 100644
--- a/crates/ide_assists/src/handlers/add_explicit_type.rs
+++ b/crates/ide_assists/src/handlers/add_explicit_type.rs
@@ -198,6 +198,34 @@ fn main() {
         )
     }
 
+    /// https://github.com/rust-analyzer/rust-analyzer/issues/2922
+    #[test]
+    fn regression_issue_2922() {
+        check_assist(
+            add_explicit_type,
+            r#"
+fn main() {
+    let $0v = [0.0; 2];
+}
+"#,
+            r#"
+fn main() {
+    let v: [f64; 2] = [0.0; 2];
+}
+"#,
+        );
+        // note: this may break later if we add more consteval. it just needs to be something that our
+        // consteval engine doesn't understand
+        check_assist_not_applicable(
+            add_explicit_type,
+            r#"
+fn main() {
+    let $0l = [0.0; 2+2];
+}
+"#,
+        );
+    }
+
     #[test]
     fn default_generics_should_not_be_added() {
         check_assist(