Add lowering of array lengths in types

Now e.g.

```rust
fn a(b: [u8; 2]) {
}
```

will know about the length of b.

10 files changed, 114 insertions, 79 deletions

diff --git a/crates/hir_def/src/type_ref.rs b/crates/hir_def/src/type_ref.rs
index ea29da5da..00c09a23d 100644
--- a/crates/hir_def/src/type_ref.rs
+++ b/crates/hir_def/src/type_ref.rs
@@ -2,6 +2,7 @@
 //! be directly created from an ast::TypeRef, without further queries.
 
 use hir_expand::{name::Name, AstId, InFile};
+use std::convert::TryInto;
 use syntax::ast;
 
 use crate::{body::LowerCtx, path::Path};
@@ -79,7 +80,7 @@ pub enum TypeRef {
     Path(Path),
     RawPtr(Box<TypeRef>, Mutability),
     Reference(Box<TypeRef>, Option<LifetimeRef>, Mutability),
-    Array(Box<TypeRef> /*, Expr*/),
+    Array(Box<TypeRef>, ConstScalar),
     Slice(Box<TypeRef>),
     /// A fn pointer. Last element of the vector is the return type.
     Fn(Vec<TypeRef>, bool /*varargs*/),
@@ -140,7 +141,12 @@ impl TypeRef {
                 TypeRef::RawPtr(Box::new(inner_ty), mutability)
             }
             ast::Type::ArrayType(inner) => {
-                TypeRef::Array(Box::new(TypeRef::from_ast_opt(&ctx, inner.ty())))
+                let len = inner
+                    .expr()
+                    .map(ConstScalar::usize_from_literal_expr)
+                    .unwrap_or(ConstScalar::Unknown);
+
+                TypeRef::Array(Box::new(TypeRef::from_ast_opt(&ctx, inner.ty())), len)
             }
             ast::Type::SliceType(inner) => {
                 TypeRef::Slice(Box::new(TypeRef::from_ast_opt(&ctx, inner.ty())))
@@ -212,7 +218,7 @@ impl TypeRef {
                 }
                 TypeRef::RawPtr(type_ref, _)
                 | TypeRef::Reference(type_ref, ..)
-                | TypeRef::Array(type_ref)
+                | TypeRef::Array(type_ref, _)
                 | TypeRef::Slice(type_ref) => go(&type_ref, f),
                 TypeRef::ImplTrait(bounds) | TypeRef::DynTrait(bounds) => {
                     for bound in bounds {
@@ -298,3 +304,44 @@ impl TypeBound {
         }
     }
 }
+
+/// A concrete constant value
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum ConstScalar {
+    // for now, we only support the trivial case of constant evaluating the length of an array
+    // Note that this is u64 because the target usize may be bigger than our usize
+    Usize(u64),
+
+    /// Case of an unknown value that rustc might know but we don't
+    Unknown,
+}
+
+impl std::fmt::Display for ConstScalar {
+    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
+        match self {
+            ConstScalar::Usize(us) => write!(fmt, "{}", us),
+            ConstScalar::Unknown => write!(fmt, "_"),
+        }
+    }
+}
+
+impl ConstScalar {
+    fn usize_from_literal_expr(expr: ast::Expr) -> ConstScalar {
+        match expr {
+            ast::Expr::Literal(lit) => {
+                let lkind = lit.kind();
+                match lkind {
+                    ast::LiteralKind::IntNumber(num)
+                        if num.suffix() == None || num.suffix() == Some("usize") =>
+                    {
+                        num.value().and_then(|v| v.try_into().ok())
+                    }
+                    _ => None,
+                }
+            }
+            _ => None,
+        }
+        .map(ConstScalar::Usize)
+        .unwrap_or(ConstScalar::Unknown)
+    }
+}
diff --git a/crates/hir_ty/src/consts.rs b/crates/hir_ty/src/consts.rs
deleted file mode 100644
index 0044b1cff..000000000
--- a/crates/hir_ty/src/consts.rs
+++ /dev/null
@@ -1,21 +0,0 @@
-//! Handling of concrete const values
-
-/// A concrete constant value
-#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
-pub enum ConstScalar {
-    // for now, we only support the trivial case of constant evaluating the length of an array
-    // Note that this is u64 because the target usize may be bigger than our usize
-    Usize(u64),
-
-    /// Case of an unknown value that rustc might know but we don't
-    Unknown,
-}
-
-impl std::fmt::Display for ConstScalar {
-    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
-        match self {
-            ConstScalar::Usize(us) => write!(fmt, "{}", us),
-            ConstScalar::Unknown => write!(fmt, "_"),
-        }
-    }
-}
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 8a4296697..7bbd1a1f7 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -962,11 +962,10 @@ impl HirDisplay for TypeRef {
                 write!(f, "{}", mutability)?;
                 inner.hir_fmt(f)?;
             }
-            TypeRef::Array(inner) => {
+            TypeRef::Array(inner, len) => {
                 write!(f, "[")?;
                 inner.hir_fmt(f)?;
-                // FIXME: Array length?
-                write!(f, "; _]")?;
+                write!(f, "; {}]", len)?;
             }
             TypeRef::Slice(inner) => {
                 write!(f, "[")?;
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 2178ffd07..5e9420752 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -8,6 +8,7 @@ use hir_def::{
     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};
@@ -15,9 +16,7 @@ use stdx::always;
 use syntax::ast::RangeOp;
 
 use crate::{
-    autoderef,
-    consts::ConstScalar,
-    dummy_usize_const,
+    autoderef, dummy_usize_const,
     lower::lower_to_chalk_mutability,
     mapping::from_chalk,
     method_resolution, op,
@@ -737,7 +736,8 @@ impl<'a> InferenceContext<'a> {
                                 TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner),
                             ),
                         );
-                        // FIXME: support length for Repeat array expressions
+                        // FIXME: we don't know the length here because hir Exprs don't actually
+                        // get the value out of the AST, even though it is there.
                         None
                     }
                 };
diff --git a/crates/hir_ty/src/interner.rs b/crates/hir_ty/src/interner.rs
index 4cbc9cd4f..7b4119747 100644
--- a/crates/hir_ty/src/interner.rs
+++ b/crates/hir_ty/src/interner.rs
@@ -1,11 +1,12 @@
 //! Implementation of the Chalk `Interner` trait, which allows customizing the
 //! representation of the various objects Chalk deals with (types, goals etc.).
 
-use crate::{chalk_db, consts::ConstScalar, tls, GenericArg};
+use crate::{chalk_db, tls, GenericArg};
 use base_db::salsa::InternId;
 use chalk_ir::{Goal, GoalData};
 use hir_def::{
     intern::{impl_internable, InternStorage, Internable, Interned},
+    type_ref::ConstScalar,
     TypeAliasId,
 };
 use smallvec::SmallVec;
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index d23eff513..be3f55bdf 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -12,7 +12,6 @@ mod chalk_db;
 mod chalk_ext;
 mod infer;
 mod interner;
-mod consts;
 mod lower;
 mod mapping;
 mod op;
@@ -38,9 +37,13 @@ use chalk_ir::{
     interner::HasInterner,
     UintTy,
 };
-use hir_def::{expr::ExprId, type_ref::Rawness, TypeParamId};
+use hir_def::{
+    expr::ExprId,
+    type_ref::{ConstScalar, Rawness},
+    TypeParamId,
+};
 
-use crate::{consts::ConstScalar, db::HirDatabase, display::HirDisplay, utils::generics};
+use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
 
 pub use autoderef::autoderef;
 pub use builder::TyBuilder;
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index 9751b45e4..f7015e5ff 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -9,7 +9,9 @@ use std::cell::{Cell, RefCell};
 use std::{iter, sync::Arc};
 
 use base_db::CrateId;
-use chalk_ir::{cast::Cast, fold::Shift, interner::HasInterner, Mutability, Safety};
+use chalk_ir::{
+    cast::Cast, fold::Shift, interner::HasInterner, Mutability, Safety, Scalar, UintTy,
+};
 use hir_def::{
     adt::StructKind,
     body::{Expander, LowerCtx},
@@ -30,16 +32,15 @@ use syntax::ast;
 
 use crate::{
     db::HirDatabase,
-    dummy_usize_const,
     mapping::ToChalk,
     static_lifetime, to_assoc_type_id, to_chalk_trait_id, to_placeholder_idx,
     utils::{
         all_super_trait_refs, associated_type_by_name_including_super_traits, generics, Generics,
     },
-    AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig,
-    FnSubst, ImplTraitId, Interner, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause,
-    QuantifiedWhereClauses, ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution,
-    TraitEnvironment, TraitRef, TraitRefExt, Ty, TyBuilder, TyKind, WhereClause,
+    AliasEq, AliasTy, Binders, BoundVar, CallableSig, ConstData, ConstValue, DebruijnIndex, DynTy,
+    FnPointer, FnSig, FnSubst, ImplTraitId, Interner, OpaqueTy, PolyFnSig, ProjectionTy,
+    QuantifiedWhereClause, QuantifiedWhereClauses, ReturnTypeImplTrait, ReturnTypeImplTraits,
+    Substitution, TraitEnvironment, TraitRef, TraitRefExt, Ty, TyBuilder, TyKind, WhereClause,
 };
 
 #[derive(Debug)]
@@ -172,11 +173,16 @@ impl<'a> TyLoweringContext<'a> {
                 let inner_ty = self.lower_ty(inner);
                 TyKind::Raw(lower_to_chalk_mutability(*mutability), inner_ty).intern(&Interner)
             }
-            TypeRef::Array(inner) => {
+            TypeRef::Array(inner, len) => {
                 let inner_ty = self.lower_ty(inner);
-                // FIXME: we don't have length info here because we don't store an expression for
-                // the length
-                TyKind::Array(inner_ty, dummy_usize_const()).intern(&Interner)
+
+                let const_len = ConstData {
+                    ty: TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner),
+                    value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: *len }),
+                }
+                .intern(&Interner);
+
+                TyKind::Array(inner_ty, const_len).intern(&Interner)
             }
             TypeRef::Slice(inner) => {
                 let inner_ty = self.lower_ty(inner);
diff --git a/crates/hir_ty/src/tests/coercion.rs b/crates/hir_ty/src/tests/coercion.rs
index aad3d610e..c2afaf6ec 100644
--- a/crates/hir_ty/src/tests/coercion.rs
+++ b/crates/hir_ty/src/tests/coercion.rs
@@ -64,42 +64,42 @@ fn coerce_places() {
             81..92 '{ loop {} }': T
             83..90 'loop {}': !
             88..90 '{}': ()
-            121..132 '{ loop {} }': *mut [T; _]
+            121..132 '{ loop {} }': *mut [T; 2]
             123..130 'loop {}': !
             128..130 '{}': ()
             159..172 '{     gen() }': *mut [U]
-            165..168 'gen': fn gen<U>() -> *mut [U; _]
-            165..170 'gen()': *mut [U; _]
+            165..168 'gen': fn gen<U>() -> *mut [U; 2]
+            165..170 'gen()': *mut [U; 2]
             185..419 '{     ...rr); }': ()
-            195..198 'arr': &[u8; _]
+            195..198 'arr': &[u8; 1]
             211..215 '&[1]': &[u8; 1]
             212..215 '[1]': [u8; 1]
             213..214 '1': u8
             226..227 'a': &[u8]
-            236..239 'arr': &[u8; _]
+            236..239 'arr': &[u8; 1]
             249..250 'b': u8
             253..254 'f': fn f<u8>(&[u8]) -> u8
             253..259 'f(arr)': u8
-            255..258 'arr': &[u8; _]
+            255..258 'arr': &[u8; 1]
             269..270 'c': &[u8]
             279..286 '{ arr }': &[u8]
-            281..284 'arr': &[u8; _]
+            281..284 'arr': &[u8; 1]
             296..297 'd': u8
             300..301 'g': fn g<u8>(S<&[u8]>) -> u8
             300..315 'g(S { a: arr })': u8
             302..314 'S { a: arr }': S<&[u8]>
-            309..312 'arr': &[u8; _]
-            325..326 'e': [&[u8]; _]
+            309..312 'arr': &[u8; 1]
+            325..326 'e': [&[u8]; 1]
             340..345 '[arr]': [&[u8]; 1]
-            341..344 'arr': &[u8; _]
-            355..356 'f': [&[u8]; _]
+            341..344 'arr': &[u8; 1]
+            355..356 'f': [&[u8]; 2]
             370..378 '[arr; 2]': [&[u8]; _]
-            371..374 'arr': &[u8; _]
+            371..374 'arr': &[u8; 1]
             376..377 '2': usize
             388..389 'g': (&[u8], &[u8])
             406..416 '(arr, arr)': (&[u8], &[u8])
-            407..410 'arr': &[u8; _]
-            412..415 'arr': &[u8; _]
+            407..410 'arr': &[u8; 1]
+            412..415 'arr': &[u8; 1]
         "#]],
     );
 }
@@ -159,7 +159,7 @@ fn infer_custom_coerce_unsized() {
         impl<'a, 'b: 'a, T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<&'a U> for &'b T {}
         impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<*mut U> for *mut T {}
         "#,
-        expect![[r"
+        expect![[r#"
             257..258 'x': A<[T]>
             278..283 '{ x }': A<[T]>
             280..281 'x': A<[T]>
@@ -169,23 +169,23 @@ fn infer_custom_coerce_unsized() {
             333..334 'x': C<[T]>
             354..359 '{ x }': C<[T]>
             356..357 'x': C<[T]>
-            369..370 'a': A<[u8; _]>
-            384..385 'b': B<[u8; _]>
-            399..400 'c': C<[u8; _]>
+            369..370 'a': A<[u8; 2]>
+            384..385 'b': B<[u8; 2]>
+            399..400 'c': C<[u8; 2]>
             414..480 '{     ...(c); }': ()
             424..425 'd': A<[{unknown}]>
             428..432 'foo1': fn foo1<{unknown}>(A<[{unknown}]>) -> A<[{unknown}]>
             428..435 'foo1(a)': A<[{unknown}]>
-            433..434 'a': A<[u8; _]>
+            433..434 'a': A<[u8; 2]>
             445..446 'e': B<[u8]>
             449..453 'foo2': fn foo2<u8>(B<[u8]>) -> B<[u8]>
             449..456 'foo2(b)': B<[u8]>
-            454..455 'b': B<[u8; _]>
+            454..455 'b': B<[u8; 2]>
             466..467 'f': C<[u8]>
             470..474 'foo3': fn foo3<u8>(C<[u8]>) -> C<[u8]>
             470..477 'foo3(c)': C<[u8]>
-            475..476 'c': C<[u8; _]>
-        "]],
+            475..476 'c': C<[u8; 2]>
+        "#]],
     );
 }
 
diff --git a/crates/hir_ty/src/tests/patterns.rs b/crates/hir_ty/src/tests/patterns.rs
index 33305f208..b36e77e91 100644
--- a/crates/hir_ty/src/tests/patterns.rs
+++ b/crates/hir_ty/src/tests/patterns.rs
@@ -345,19 +345,19 @@ fn infer_pattern_match_arr() {
         "#,
         expect![[r#"
             10..179 '{     ...   } }': ()
-            20..23 'arr': [f64; _]
+            20..23 'arr': [f64; 2]
             36..46 '[0.0, 1.0]': [f64; 2]
             37..40 '0.0': f64
             42..45 '1.0': f64
             52..177 'match ...     }': ()
-            58..61 'arr': [f64; _]
-            72..80 '[1.0, a]': [f64; _]
+            58..61 'arr': [f64; 2]
+            72..80 '[1.0, a]': [f64; 2]
             73..76 '1.0': f64
             73..76 '1.0': f64
             78..79 'a': f64
             84..110 '{     ...     }': ()
             98..99 'a': f64
-            120..126 '[b, c]': [f64; _]
+            120..126 '[b, c]': [f64; 2]
             121..122 'b': f64
             124..125 'c': f64
             130..171 '{     ...     }': ()
diff --git a/crates/hir_ty/src/tests/simple.rs b/crates/hir_ty/src/tests/simple.rs
index 8b09f2e4a..19775a4ec 100644
--- a/crates/hir_ty/src/tests/simple.rs
+++ b/crates/hir_ty/src/tests/simple.rs
@@ -1313,7 +1313,7 @@ fn infer_array() {
             255..256 'a': [&str; 1]
             258..263 '["b"]': [&str; 1]
             259..262 '"b"': &str
-            274..275 'x': [u8; _]
+            274..275 'x': [u8; 0]
             287..289 '[]': [u8; 0]
         "#]],
     );
@@ -2409,38 +2409,38 @@ fn infer_operator_overload() {
             320..422 '{     ...     }': V2
             334..335 'x': f32
             338..342 'self': V2
-            338..344 'self.0': [f32; _]
+            338..344 'self.0': [f32; 2]
             338..347 'self.0[0]': {unknown}
             338..358 'self.0...s.0[0]': f32
             345..346 '0': i32
             350..353 'rhs': V2
-            350..355 'rhs.0': [f32; _]
+            350..355 'rhs.0': [f32; 2]
             350..358 'rhs.0[0]': {unknown}
             356..357 '0': i32
             372..373 'y': f32
             376..380 'self': V2
-            376..382 'self.0': [f32; _]
+            376..382 'self.0': [f32; 2]
             376..385 'self.0[1]': {unknown}
             376..396 'self.0...s.0[1]': f32
             383..384 '1': i32
             388..391 'rhs': V2
-            388..393 'rhs.0': [f32; _]
+            388..393 'rhs.0': [f32; 2]
             388..396 'rhs.0[1]': {unknown}
             394..395 '1': i32
-            406..408 'V2': V2([f32; _]) -> V2
+            406..408 'V2': V2([f32; 2]) -> V2
             406..416 'V2([x, y])': V2
             409..415 '[x, y]': [f32; 2]
             410..411 'x': f32
             413..414 'y': f32
             436..519 '{     ... vb; }': ()
             446..448 'va': V2
-            451..453 'V2': V2([f32; _]) -> V2
+            451..453 'V2': V2([f32; 2]) -> V2
             451..465 'V2([0.0, 1.0])': V2
             454..464 '[0.0, 1.0]': [f32; 2]
             455..458 '0.0': f32
             460..463 '1.0': f32
             475..477 'vb': V2
-            480..482 'V2': V2([f32; _]) -> V2
+            480..482 'V2': V2([f32; 2]) -> V2
             480..494 'V2([0.0, 1.0])': V2
             483..493 '[0.0, 1.0]': [f32; 2]
             484..487 '0.0': f32