aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Cargo.lock121
-rw-r--r--crates/ra_hir/Cargo.toml6
-rw-r--r--crates/ra_hir/src/code_model_api.rs6
-rw-r--r--crates/ra_hir/src/db.rs31
-rw-r--r--crates/ra_hir/src/generics.rs11
-rw-r--r--crates/ra_hir/src/ids.rs12
-rw-r--r--crates/ra_hir/src/resolve.rs3
-rw-r--r--crates/ra_hir/src/source_binder.rs11
-rw-r--r--crates/ra_hir/src/ty.rs112
-rw-r--r--crates/ra_hir/src/ty/infer.rs52
-rw-r--r--crates/ra_hir/src/ty/infer/unify.rs122
-rw-r--r--crates/ra_hir/src/ty/lower.rs37
-rw-r--r--crates/ra_hir/src/ty/method_resolution.rs223
-rw-r--r--crates/ra_hir/src/ty/tests.rs2
-rw-r--r--crates/ra_hir/src/ty/traits.rs223
-rw-r--r--crates/ra_hir/src/ty/traits/chalk.rs333
-rw-r--r--crates/ra_ide_api/src/completion/complete_dot.rs2
17 files changed, 1027 insertions, 280 deletions
diff --git a/Cargo.lock b/Cargo.lock
index de6e9ec9a..98c349dec 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -144,6 +144,61 @@ version = "0.1.7"
144source = "registry+https://github.com/rust-lang/crates.io-index" 144source = "registry+https://github.com/rust-lang/crates.io-index"
145 145
146[[package]] 146[[package]]
147name = "chalk-engine"
148version = "0.9.0"
149source = "git+https://github.com/rust-lang/chalk.git#17fb07e43b23d721f9c1adba289eac71b25f38ef"
150dependencies = [
151 "chalk-macros 0.1.1 (git+https://github.com/rust-lang/chalk.git)",
152 "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
153 "stacker 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
154]
155
156[[package]]
157name = "chalk-ir"
158version = "0.1.0"
159source = "git+https://github.com/rust-lang/chalk.git#17fb07e43b23d721f9c1adba289eac71b25f38ef"
160dependencies = [
161 "chalk-engine 0.9.0 (git+https://github.com/rust-lang/chalk.git)",
162 "chalk-macros 0.1.1 (git+https://github.com/rust-lang/chalk.git)",
163 "lalrpop-intern 0.15.1 (registry+https://github.com/rust-lang/crates.io-index)",
164]
165
166[[package]]
167name = "chalk-macros"
168version = "0.1.1"
169source = "git+https://github.com/rust-lang/chalk.git#17fb07e43b23d721f9c1adba289eac71b25f38ef"
170dependencies = [
171 "lazy_static 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
172]
173
174[[package]]
175name = "chalk-rust-ir"
176version = "0.1.0"
177source = "git+https://github.com/rust-lang/chalk.git#17fb07e43b23d721f9c1adba289eac71b25f38ef"
178dependencies = [
179 "chalk-engine 0.9.0 (git+https://github.com/rust-lang/chalk.git)",
180 "chalk-ir 0.1.0 (git+https://github.com/rust-lang/chalk.git)",
181 "chalk-macros 0.1.1 (git+https://github.com/rust-lang/chalk.git)",
182]
183
184[[package]]
185name = "chalk-solve"
186version = "0.1.0"
187source = "git+https://github.com/rust-lang/chalk.git#17fb07e43b23d721f9c1adba289eac71b25f38ef"
188dependencies = [
189 "chalk-engine 0.9.0 (git+https://github.com/rust-lang/chalk.git)",
190 "chalk-ir 0.1.0 (git+https://github.com/rust-lang/chalk.git)",
191 "chalk-macros 0.1.1 (git+https://github.com/rust-lang/chalk.git)",
192 "chalk-rust-ir 0.1.0 (git+https://github.com/rust-lang/chalk.git)",
193 "derive-new 0.5.6 (registry+https://github.com/rust-lang/crates.io-index)",
194 "ena 0.10.1 (registry+https://github.com/rust-lang/crates.io-index)",
195 "failure 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
196 "itertools 0.7.11 (registry+https://github.com/rust-lang/crates.io-index)",
197 "petgraph 0.4.13 (registry+https://github.com/rust-lang/crates.io-index)",
198 "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
199]
200
201[[package]]
147name = "chrono" 202name = "chrono"
148version = "0.4.6" 203version = "0.4.6"
149source = "registry+https://github.com/rust-lang/crates.io-index" 204source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -308,6 +363,14 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
308 363
309[[package]] 364[[package]]
310name = "ena" 365name = "ena"
366version = "0.10.1"
367source = "registry+https://github.com/rust-lang/crates.io-index"
368dependencies = [
369 "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
370]
371
372[[package]]
373name = "ena"
311version = "0.11.0" 374version = "0.11.0"
312source = "registry+https://github.com/rust-lang/crates.io-index" 375source = "registry+https://github.com/rust-lang/crates.io-index"
313dependencies = [ 376dependencies = [
@@ -363,6 +426,11 @@ dependencies = [
363] 426]
364 427
365[[package]] 428[[package]]
429name = "fixedbitset"
430version = "0.1.9"
431source = "registry+https://github.com/rust-lang/crates.io-index"
432
433[[package]]
366name = "flexi_logger" 434name = "flexi_logger"
367version = "0.11.4" 435version = "0.11.4"
368source = "registry+https://github.com/rust-lang/crates.io-index" 436source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -542,6 +610,14 @@ dependencies = [
542 610
543[[package]] 611[[package]]
544name = "itertools" 612name = "itertools"
613version = "0.7.11"
614source = "registry+https://github.com/rust-lang/crates.io-index"
615dependencies = [
616 "either 1.5.2 (registry+https://github.com/rust-lang/crates.io-index)",
617]
618
619[[package]]
620name = "itertools"
545version = "0.8.0" 621version = "0.8.0"
546source = "registry+https://github.com/rust-lang/crates.io-index" 622source = "registry+https://github.com/rust-lang/crates.io-index"
547dependencies = [ 623dependencies = [
@@ -596,6 +672,11 @@ dependencies = [
596] 672]
597 673
598[[package]] 674[[package]]
675name = "lalrpop-intern"
676version = "0.15.1"
677source = "registry+https://github.com/rust-lang/crates.io-index"
678
679[[package]]
599name = "lazy_static" 680name = "lazy_static"
600version = "1.3.0" 681version = "1.3.0"
601source = "registry+https://github.com/rust-lang/crates.io-index" 682source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -790,6 +871,11 @@ version = "0.2.2"
790source = "registry+https://github.com/rust-lang/crates.io-index" 871source = "registry+https://github.com/rust-lang/crates.io-index"
791 872
792[[package]] 873[[package]]
874name = "ordermap"
875version = "0.3.5"
876source = "registry+https://github.com/rust-lang/crates.io-index"
877
878[[package]]
793name = "owning_ref" 879name = "owning_ref"
794version = "0.4.0" 880version = "0.4.0"
795source = "registry+https://github.com/rust-lang/crates.io-index" 881source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -863,6 +949,15 @@ dependencies = [
863] 949]
864 950
865[[package]] 951[[package]]
952name = "petgraph"
953version = "0.4.13"
954source = "registry+https://github.com/rust-lang/crates.io-index"
955dependencies = [
956 "fixedbitset 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)",
957 "ordermap 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)",
958]
959
960[[package]]
866name = "proc-macro2" 961name = "proc-macro2"
867version = "0.4.28" 962version = "0.4.28"
868source = "registry+https://github.com/rust-lang/crates.io-index" 963source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -979,6 +1074,9 @@ name = "ra_hir"
979version = "0.1.0" 1074version = "0.1.0"
980dependencies = [ 1075dependencies = [
981 "arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)", 1076 "arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)",
1077 "chalk-ir 0.1.0 (git+https://github.com/rust-lang/chalk.git)",
1078 "chalk-rust-ir 0.1.0 (git+https://github.com/rust-lang/chalk.git)",
1079 "chalk-solve 0.1.0 (git+https://github.com/rust-lang/chalk.git)",
982 "ena 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)", 1080 "ena 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
983 "flexi_logger 0.11.4 (registry+https://github.com/rust-lang/crates.io-index)", 1081 "flexi_logger 0.11.4 (registry+https://github.com/rust-lang/crates.io-index)",
984 "insta 0.7.4 (registry+https://github.com/rust-lang/crates.io-index)", 1082 "insta 0.7.4 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1499,6 +1597,17 @@ version = "1.1.1"
1499source = "registry+https://github.com/rust-lang/crates.io-index" 1597source = "registry+https://github.com/rust-lang/crates.io-index"
1500 1598
1501[[package]] 1599[[package]]
1600name = "stacker"
1601version = "0.1.5"
1602source = "registry+https://github.com/rust-lang/crates.io-index"
1603dependencies = [
1604 "cc 1.0.35 (registry+https://github.com/rust-lang/crates.io-index)",
1605 "cfg-if 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
1606 "libc 0.2.51 (registry+https://github.com/rust-lang/crates.io-index)",
1607 "winapi 0.3.7 (registry+https://github.com/rust-lang/crates.io-index)",
1608]
1609
1610[[package]]
1502name = "strsim" 1611name = "strsim"
1503version = "0.8.0" 1612version = "0.8.0"
1504source = "registry+https://github.com/rust-lang/crates.io-index" 1613source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1888,6 +1997,11 @@ dependencies = [
1888"checksum cargo_metadata 0.7.4 (registry+https://github.com/rust-lang/crates.io-index)" = "178d62b240c34223f265a4c1e275e37d62da163d421fc8d7f7e3ee340f803c57" 1997"checksum cargo_metadata 0.7.4 (registry+https://github.com/rust-lang/crates.io-index)" = "178d62b240c34223f265a4c1e275e37d62da163d421fc8d7f7e3ee340f803c57"
1889"checksum cc 1.0.35 (registry+https://github.com/rust-lang/crates.io-index)" = "5e5f3fee5eeb60324c2781f1e41286bdee933850fff9b3c672587fed5ec58c83" 1998"checksum cc 1.0.35 (registry+https://github.com/rust-lang/crates.io-index)" = "5e5f3fee5eeb60324c2781f1e41286bdee933850fff9b3c672587fed5ec58c83"
1890"checksum cfg-if 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "11d43355396e872eefb45ce6342e4374ed7bc2b3a502d1b28e36d6e23c05d1f4" 1999"checksum cfg-if 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "11d43355396e872eefb45ce6342e4374ed7bc2b3a502d1b28e36d6e23c05d1f4"
2000"checksum chalk-engine 0.9.0 (git+https://github.com/rust-lang/chalk.git)" = "<none>"
2001"checksum chalk-ir 0.1.0 (git+https://github.com/rust-lang/chalk.git)" = "<none>"
2002"checksum chalk-macros 0.1.1 (git+https://github.com/rust-lang/chalk.git)" = "<none>"
2003"checksum chalk-rust-ir 0.1.0 (git+https://github.com/rust-lang/chalk.git)" = "<none>"
2004"checksum chalk-solve 0.1.0 (git+https://github.com/rust-lang/chalk.git)" = "<none>"
1891"checksum chrono 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)" = "45912881121cb26fad7c38c17ba7daa18764771836b34fab7d3fbd93ed633878" 2005"checksum chrono 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)" = "45912881121cb26fad7c38c17ba7daa18764771836b34fab7d3fbd93ed633878"
1892"checksum ci_info 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "e5e881307a989a3a5e20d52a32cc05950e3c2178cccfcc9428271a6cde09f902" 2006"checksum ci_info 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "e5e881307a989a3a5e20d52a32cc05950e3c2178cccfcc9428271a6cde09f902"
1893"checksum clap 2.33.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5067f5bb2d80ef5d68b4c87db81601f0b75bca627bc2ef76b141d7b846a3c6d9" 2007"checksum clap 2.33.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5067f5bb2d80ef5d68b4c87db81601f0b75bca627bc2ef76b141d7b846a3c6d9"
@@ -1907,6 +2021,7 @@ dependencies = [
1907"checksum drop_bomb 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "69b26e475fd29098530e709294e94e661974c851aed42512793f120fed4e199f" 2021"checksum drop_bomb 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "69b26e475fd29098530e709294e94e661974c851aed42512793f120fed4e199f"
1908"checksum dtoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "6d301140eb411af13d3115f9a562c85cc6b541ade9dfa314132244aaee7489dd" 2022"checksum dtoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "6d301140eb411af13d3115f9a562c85cc6b541ade9dfa314132244aaee7489dd"
1909"checksum either 1.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "5527cfe0d098f36e3f8839852688e63c8fff1c90b2b405aef730615f9a7bcf7b" 2023"checksum either 1.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "5527cfe0d098f36e3f8839852688e63c8fff1c90b2b405aef730615f9a7bcf7b"
2024"checksum ena 0.10.1 (registry+https://github.com/rust-lang/crates.io-index)" = "25b4e5febb25f08c49f1b07dc33a182729a6b21edfb562b5aef95f78e0dbe5bb"
1910"checksum ena 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f56c93cc076508c549d9bb747f79aa9b4eb098be7b8cad8830c3137ef52d1e00" 2025"checksum ena 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f56c93cc076508c549d9bb747f79aa9b4eb098be7b8cad8830c3137ef52d1e00"
1911"checksum encode_unicode 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "90b2c9496c001e8cb61827acdefad780795c42264c137744cae6f7d9e3450abd" 2026"checksum encode_unicode 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "90b2c9496c001e8cb61827acdefad780795c42264c137744cae6f7d9e3450abd"
1912"checksum error-chain 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "07e791d3be96241c77c43846b665ef1384606da2cd2a48730abe606a12906e02" 2027"checksum error-chain 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "07e791d3be96241c77c43846b665ef1384606da2cd2a48730abe606a12906e02"
@@ -1914,6 +2029,7 @@ dependencies = [
1914"checksum failure_derive 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "ea1063915fd7ef4309e222a5a07cf9c319fb9c7836b1f89b85458672dbb127e1" 2029"checksum failure_derive 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "ea1063915fd7ef4309e222a5a07cf9c319fb9c7836b1f89b85458672dbb127e1"
1915"checksum fake-simd 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "e88a8acf291dafb59c2d96e8f59828f3838bb1a70398823ade51a84de6a6deed" 2030"checksum fake-simd 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "e88a8acf291dafb59c2d96e8f59828f3838bb1a70398823ade51a84de6a6deed"
1916"checksum filetime 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)" = "2f8c63033fcba1f51ef744505b3cad42510432b904c062afa67ad7ece008429d" 2031"checksum filetime 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)" = "2f8c63033fcba1f51ef744505b3cad42510432b904c062afa67ad7ece008429d"
2032"checksum fixedbitset 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "86d4de0081402f5e88cdac65c8dcdcc73118c1a7a465e2a05f0da05843a8ea33"
1917"checksum flexi_logger 0.11.4 (registry+https://github.com/rust-lang/crates.io-index)" = "73de04baa435682b03677bb28f7b3e9d72b0489a551da5ba413c9b29f7979a19" 2033"checksum flexi_logger 0.11.4 (registry+https://github.com/rust-lang/crates.io-index)" = "73de04baa435682b03677bb28f7b3e9d72b0489a551da5ba413c9b29f7979a19"
1918"checksum fs_extra 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5f2a4a2034423744d2cc7ca2068453168dcdb82c438419e639a26bd87839c674" 2034"checksum fs_extra 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5f2a4a2034423744d2cc7ca2068453168dcdb82c438419e639a26bd87839c674"
1919"checksum fsevent 0.2.17 (registry+https://github.com/rust-lang/crates.io-index)" = "c4bbbf71584aeed076100b5665ac14e3d85eeb31fdbb45fbd41ef9a682b5ec05" 2035"checksum fsevent 0.2.17 (registry+https://github.com/rust-lang/crates.io-index)" = "c4bbbf71584aeed076100b5665ac14e3d85eeb31fdbb45fbd41ef9a682b5ec05"
@@ -1934,6 +2050,7 @@ dependencies = [
1934"checksum inotify-sys 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "e74a1aa87c59aeff6ef2cc2fa62d41bc43f54952f55652656b18a02fd5e356c0" 2050"checksum inotify-sys 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "e74a1aa87c59aeff6ef2cc2fa62d41bc43f54952f55652656b18a02fd5e356c0"
1935"checksum insta 0.7.4 (registry+https://github.com/rust-lang/crates.io-index)" = "03e7d88a87d342ce8bd698516151be43e6eb2e84b683db528696cb4a382f734a" 2051"checksum insta 0.7.4 (registry+https://github.com/rust-lang/crates.io-index)" = "03e7d88a87d342ce8bd698516151be43e6eb2e84b683db528696cb4a382f734a"
1936"checksum iovec 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "dbe6e417e7d0975db6512b90796e8ce223145ac4e33c377e4a42882a0e88bb08" 2052"checksum iovec 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "dbe6e417e7d0975db6512b90796e8ce223145ac4e33c377e4a42882a0e88bb08"
2053"checksum itertools 0.7.11 (registry+https://github.com/rust-lang/crates.io-index)" = "0d47946d458e94a1b7bcabbf6521ea7c037062c81f534615abcad76e84d4970d"
1937"checksum itertools 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5b8467d9c1cebe26feb08c640139247fac215782d35371ade9a2136ed6085358" 2054"checksum itertools 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5b8467d9c1cebe26feb08c640139247fac215782d35371ade9a2136ed6085358"
1938"checksum itoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1306f3464951f30e30d12373d31c79fbd52d236e5e896fd92f96ec7babbbe60b" 2055"checksum itoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1306f3464951f30e30d12373d31c79fbd52d236e5e896fd92f96ec7babbbe60b"
1939"checksum jemalloc-ctl 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "4e93b0f37e7d735c6b610176d5b1bde8e1621ff3f6f7ac23cdfa4e7f7d0111b5" 2056"checksum jemalloc-ctl 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "4e93b0f37e7d735c6b610176d5b1bde8e1621ff3f6f7ac23cdfa4e7f7d0111b5"
@@ -1941,6 +2058,7 @@ dependencies = [
1941"checksum jemallocator 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "9f0cd42ac65f758063fea55126b0148b1ce0a6354ff78e07a4d6806bc65c4ab3" 2058"checksum jemallocator 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "9f0cd42ac65f758063fea55126b0148b1ce0a6354ff78e07a4d6806bc65c4ab3"
1942"checksum join_to_string 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "4dc7a5290e8c2606ce2be49f456d50f69173cb96d1541e4f66e34ac8b331a98f" 2059"checksum join_to_string 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "4dc7a5290e8c2606ce2be49f456d50f69173cb96d1541e4f66e34ac8b331a98f"
1943"checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d" 2060"checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d"
2061"checksum lalrpop-intern 0.15.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cc4fd87be4a815fd373e02773983940f0d75fb26fde8c098e9e45f7af03154c0"
1944"checksum lazy_static 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "bc5729f27f159ddd61f4df6228e827e86643d4d3e7c32183cb30a1c08f604a14" 2062"checksum lazy_static 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "bc5729f27f159ddd61f4df6228e827e86643d4d3e7c32183cb30a1c08f604a14"
1945"checksum lazycell 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b294d6fa9ee409a054354afc4352b0b9ef7ca222c69b8812cbea9e7d2bf3783f" 2063"checksum lazycell 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b294d6fa9ee409a054354afc4352b0b9ef7ca222c69b8812cbea9e7d2bf3783f"
1946"checksum libc 0.2.51 (registry+https://github.com/rust-lang/crates.io-index)" = "bedcc7a809076656486ffe045abeeac163da1b558e963a31e29fbfbeba916917" 2064"checksum libc 0.2.51 (registry+https://github.com/rust-lang/crates.io-index)" = "bedcc7a809076656486ffe045abeeac163da1b558e963a31e29fbfbeba916917"
@@ -1965,6 +2083,7 @@ dependencies = [
1965"checksum number_prefix 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "dbf9993e59c894e3c08aa1c2712914e9e6bf1fcbfc6bef283e2183df345a4fee" 2083"checksum number_prefix 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "dbf9993e59c894e3c08aa1c2712914e9e6bf1fcbfc6bef283e2183df345a4fee"
1966"checksum numtoa 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b8f8bdf33df195859076e54ab11ee78a1b208382d3a26ec40d142ffc1ecc49ef" 2084"checksum numtoa 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b8f8bdf33df195859076e54ab11ee78a1b208382d3a26ec40d142ffc1ecc49ef"
1967"checksum opaque-debug 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "93f5bb2e8e8dec81642920ccff6b61f1eb94fa3020c5a325c9851ff604152409" 2085"checksum opaque-debug 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "93f5bb2e8e8dec81642920ccff6b61f1eb94fa3020c5a325c9851ff604152409"
2086"checksum ordermap 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "a86ed3f5f244b372d6b1a00b72ef7f8876d0bc6a78a4c9985c53614041512063"
1968"checksum owning_ref 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "49a4b8ea2179e6a2e27411d3bca09ca6dd630821cf6894c6c7c8467a8ee7ef13" 2087"checksum owning_ref 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "49a4b8ea2179e6a2e27411d3bca09ca6dd630821cf6894c6c7c8467a8ee7ef13"
1969"checksum parking_lot 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ab41b4aed082705d1056416ae4468b6ea99d52599ecf3169b00088d43113e337" 2088"checksum parking_lot 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ab41b4aed082705d1056416ae4468b6ea99d52599ecf3169b00088d43113e337"
1970"checksum parking_lot_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "94c8c7923936b28d546dfd14d4472eaf34c99b14e1c973a32b3e6d4eb04298c9" 2089"checksum parking_lot_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "94c8c7923936b28d546dfd14d4472eaf34c99b14e1c973a32b3e6d4eb04298c9"
@@ -1973,6 +2092,7 @@ dependencies = [
1973"checksum pest_derive 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "833d1ae558dc601e9a60366421196a8d94bc0ac980476d0b67e1d0988d72b2d0" 2092"checksum pest_derive 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "833d1ae558dc601e9a60366421196a8d94bc0ac980476d0b67e1d0988d72b2d0"
1974"checksum pest_generator 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "63120576c4efd69615b5537d3d052257328a4ca82876771d6944424ccfd9f646" 2093"checksum pest_generator 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "63120576c4efd69615b5537d3d052257328a4ca82876771d6944424ccfd9f646"
1975"checksum pest_meta 2.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f249ea6de7c7b7aba92b4ff4376a994c6dbd98fd2166c89d5c4947397ecb574d" 2094"checksum pest_meta 2.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f249ea6de7c7b7aba92b4ff4376a994c6dbd98fd2166c89d5c4947397ecb574d"
2095"checksum petgraph 0.4.13 (registry+https://github.com/rust-lang/crates.io-index)" = "9c3659d1ee90221741f65dd128d9998311b0e40c5d3c23a62445938214abce4f"
1976"checksum proc-macro2 0.4.28 (registry+https://github.com/rust-lang/crates.io-index)" = "ba92c84f814b3f9a44c5cfca7d2ad77fa10710867d2bbb1b3d175ab5f47daa12" 2096"checksum proc-macro2 0.4.28 (registry+https://github.com/rust-lang/crates.io-index)" = "ba92c84f814b3f9a44c5cfca7d2ad77fa10710867d2bbb1b3d175ab5f47daa12"
1977"checksum proptest 0.9.2 (registry+https://github.com/rust-lang/crates.io-index)" = "24f5844db2f839e97e3021980975f6ebf8691d9b9b2ca67ed3feb38dc3edb52c" 2097"checksum proptest 0.9.2 (registry+https://github.com/rust-lang/crates.io-index)" = "24f5844db2f839e97e3021980975f6ebf8691d9b9b2ca67ed3feb38dc3edb52c"
1978"checksum quick-error 1.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "9274b940887ce9addde99c4eee6b5c44cc494b182b97e73dc8ffdcb3397fd3f0" 2098"checksum quick-error 1.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "9274b940887ce9addde99c4eee6b5c44cc494b182b97e73dc8ffdcb3397fd3f0"
@@ -2019,6 +2139,7 @@ dependencies = [
2019"checksum smallvec 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)" = "c4488ae950c49d403731982257768f48fada354a5203fe81f9bb6f43ca9002be" 2139"checksum smallvec 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)" = "c4488ae950c49d403731982257768f48fada354a5203fe81f9bb6f43ca9002be"
2020"checksum smol_str 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "d077b3367211e9c6e2e012fb804c444e0d80ab5a51ae4137739b58e6446dcaef" 2140"checksum smol_str 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "d077b3367211e9c6e2e012fb804c444e0d80ab5a51ae4137739b58e6446dcaef"
2021"checksum stable_deref_trait 1.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "dba1a27d3efae4351c8051072d619e3ade2820635c3958d826bfea39d59b54c8" 2141"checksum stable_deref_trait 1.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "dba1a27d3efae4351c8051072d619e3ade2820635c3958d826bfea39d59b54c8"
2142"checksum stacker 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "fb79482f57cf598af52094ec4cc3b3c42499d3ce5bd426f2ac41515b7e57404b"
2022"checksum strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a" 2143"checksum strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a"
2023"checksum superslice 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ab16ced94dbd8a46c82fd81e3ed9a8727dac2977ea869d217bcc4ea1f122e81f" 2144"checksum superslice 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ab16ced94dbd8a46c82fd81e3ed9a8727dac2977ea869d217bcc4ea1f122e81f"
2024"checksum syn 0.15.32 (registry+https://github.com/rust-lang/crates.io-index)" = "846620ec526c1599c070eff393bfeeeb88a93afa2513fc3b49f1fea84cf7b0ed" 2145"checksum syn 0.15.32 (registry+https://github.com/rust-lang/crates.io-index)" = "846620ec526c1599c070eff393bfeeeb88a93afa2513fc3b49f1fea84cf7b0ed"
diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml
index a2858dad9..68ffcb2e9 100644
--- a/crates/ra_hir/Cargo.toml
+++ b/crates/ra_hir/Cargo.toml
@@ -19,7 +19,11 @@ ra_db = { path = "../ra_db" }
19mbe = { path = "../ra_mbe", package = "ra_mbe" } 19mbe = { path = "../ra_mbe", package = "ra_mbe" }
20tt = { path = "../ra_tt", package = "ra_tt" } 20tt = { path = "../ra_tt", package = "ra_tt" }
21test_utils = { path = "../test_utils" } 21test_utils = { path = "../test_utils" }
22ra_prof = {path = "../ra_prof" } 22ra_prof = { path = "../ra_prof" }
23
24chalk-solve = { git = "https://github.com/rust-lang/chalk.git" }
25chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git" }
26chalk-ir = { git = "https://github.com/rust-lang/chalk.git" }
23 27
24[dev-dependencies] 28[dev-dependencies]
25flexi_logger = "0.11.0" 29flexi_logger = "0.11.0"
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 8f1ed1086..9dcae50a5 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -9,7 +9,7 @@ use crate::{
9 type_ref::TypeRef, 9 type_ref::TypeRef,
10 nameres::{ModuleScope, Namespace, ImportId, CrateModuleId}, 10 nameres::{ModuleScope, Namespace, ImportId, CrateModuleId},
11 expr::{Body, BodySourceMap}, 11 expr::{Body, BodySourceMap},
12 ty::InferenceResult, 12 ty::{ TraitRef, InferenceResult},
13 adt::{EnumVariantId, StructFieldId, VariantDef}, 13 adt::{EnumVariantId, StructFieldId, VariantDef},
14 generics::HasGenericParams, 14 generics::HasGenericParams,
15 docs::{Documentation, Docs, docs_from_ast}, 15 docs::{Documentation, Docs, docs_from_ast},
@@ -696,6 +696,10 @@ impl Trait {
696 db.trait_data(self) 696 db.trait_data(self)
697 } 697 }
698 698
699 pub fn trait_ref(self, db: &impl HirDatabase) -> TraitRef {
700 TraitRef::for_trait(db, self)
701 }
702
699 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { 703 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
700 let r = self.module(db).resolver(db); 704 let r = self.module(db).resolver(db);
701 // add generic params, if present 705 // add generic params, if present
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 398e00c42..8aaf0375a 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -1,4 +1,4 @@
1use std::sync::Arc; 1use std::sync::{Arc, Mutex};
2 2
3use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast}; 3use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast};
4use ra_db::{SourceDatabase, salsa}; 4use ra_db::{SourceDatabase, salsa};
@@ -8,16 +8,16 @@ use crate::{
8 Function, FnSignature, ExprScopes, TypeAlias, 8 Function, FnSignature, ExprScopes, TypeAlias,
9 Struct, Enum, StructField, 9 Struct, Enum, StructField,
10 Const, ConstSignature, Static, 10 Const, ConstSignature, Static,
11 DefWithBody, 11 DefWithBody, Trait,
12 ids,
12 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, 13 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap},
13 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig}, 14 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor},
14 adt::{StructData, EnumData}, 15 adt::{StructData, EnumData},
15 impl_block::{ModuleImplBlocks, ImplSourceMap}, 16 impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock},
16 generics::{GenericParams, GenericDef}, 17 generics::{GenericParams, GenericDef},
17 type_ref::TypeRef, 18 type_ref::TypeRef,
18 traits::TraitData, Trait, ty::TraitRef, 19 traits::TraitData,
19 lang_item::{LangItems, LangItemTarget}, 20 lang_item::{LangItems, LangItemTarget},
20 ids
21}; 21};
22 22
23#[salsa::query_group(DefDatabaseStorage)] 23#[salsa::query_group(DefDatabaseStorage)]
@@ -39,6 +39,12 @@ pub trait DefDatabase: SourceDatabase {
39 #[salsa::interned] 39 #[salsa::interned]
40 fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId; 40 fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId;
41 41
42 // Interned IDs for Chalk integration
43 #[salsa::interned]
44 fn intern_type_ctor(&self, type_ctor: TypeCtor) -> ids::TypeCtorId;
45 #[salsa::interned]
46 fn intern_impl_block(&self, impl_block: ImplBlock) -> ids::GlobalImplId;
47
42 #[salsa::invoke(crate::ids::macro_def_query)] 48 #[salsa::invoke(crate::ids::macro_def_query)]
43 fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>; 49 fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>;
44 50
@@ -144,8 +150,17 @@ pub trait HirDatabase: DefDatabase {
144 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)] 150 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
145 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>; 151 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
146 152
147 #[salsa::invoke(crate::ty::traits::implements)] 153 #[salsa::invoke(crate::ty::traits::impls_for_trait)]
148 fn implements(&self, trait_ref: TraitRef) -> Option<crate::ty::traits::Solution>; 154 fn impls_for_trait(&self, krate: Crate, trait_: Trait) -> Arc<[ImplBlock]>;
155
156 /// This provides the Chalk trait solver instance. Because Chalk always
157 /// works from a specific crate, this query is keyed on the crate; and
158 /// because Chalk does its own internal caching, the solver is wrapped in a
159 /// Mutex and the query is marked volatile, to make sure the cached state is
160 /// thrown away when input facts change.
161 #[salsa::invoke(crate::ty::traits::solver)]
162 #[salsa::volatile]
163 fn solver(&self, krate: Crate) -> Arc<Mutex<crate::ty::traits::Solver>>;
149} 164}
150 165
151#[test] 166#[test]
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 1c71e21ea..2e52c5871 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -9,7 +9,7 @@ use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner};
9 9
10use crate::{ 10use crate::{
11 db::DefDatabase, 11 db::DefDatabase,
12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef 12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef
13}; 13};
14 14
15/// Data about a generic parameter (to a function, struct, impl, ...). 15/// Data about a generic parameter (to a function, struct, impl, ...).
@@ -157,6 +157,15 @@ impl From<Container> for GenericDef {
157 } 157 }
158} 158}
159 159
160impl From<crate::adt::AdtDef> for GenericDef {
161 fn from(adt: crate::adt::AdtDef) -> Self {
162 match adt {
163 AdtDef::Struct(s) => s.into(),
164 AdtDef::Enum(e) => e.into(),
165 }
166 }
167}
168
160pub trait HasGenericParams { 169pub trait HasGenericParams {
161 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>; 170 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>;
162} 171}
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index 4102951c9..ff4a81e59 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -354,3 +354,15 @@ impl MacroCallId {
354 ) 354 )
355 } 355 }
356} 356}
357
358/// This exists just for Chalk, because Chalk just has a single `StructId` where
359/// we have different kinds of ADTs, primitive types and special type
360/// constructors like tuples and function pointers.
361#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
362pub struct TypeCtorId(salsa::InternId);
363impl_intern_key!(TypeCtorId);
364
365/// This exists just for Chalk, because our ImplIds are only unique per module.
366#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
367pub struct GlobalImplId(salsa::InternId);
368impl_intern_key!(GlobalImplId);
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs
index bc9170cdc..707556ef8 100644
--- a/crates/ra_hir/src/resolve.rs
+++ b/crates/ra_hir/src/resolve.rs
@@ -6,7 +6,7 @@ use ra_syntax::ast;
6use rustc_hash::FxHashMap; 6use rustc_hash::FxHashMap;
7 7
8use crate::{ 8use crate::{
9 ModuleDef, 9 ModuleDef, Trait,
10 code_model_api::Crate, 10 code_model_api::Crate,
11 MacroCallId, 11 MacroCallId,
12 MacroCallLoc, 12 MacroCallLoc,
@@ -18,7 +18,6 @@ use crate::{
18 expr::{scope::{ExprScopes, ScopeId}, PatId}, 18 expr::{scope::{ExprScopes, ScopeId}, PatId},
19 impl_block::ImplBlock, 19 impl_block::ImplBlock,
20 path::Path, 20 path::Path,
21 Trait,
22}; 21};
23 22
24#[derive(Debug, Clone, Default)] 23#[derive(Debug, Clone, Default)]
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 2959e3eca..2ec1a7692 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -350,7 +350,16 @@ impl SourceAnalyzer {
350 name: Option<&Name>, 350 name: Option<&Name>,
351 callback: impl FnMut(&Ty, Function) -> Option<T>, 351 callback: impl FnMut(&Ty, Function) -> Option<T>,
352 ) -> Option<T> { 352 ) -> Option<T> {
353 ty.iterate_method_candidates(db, &self.resolver, name, callback) 353 // There should be no inference vars in types passed here
354 // FIXME check that?
355 let canonical = crate::ty::Canonical { value: ty, num_vars: 0 };
356 crate::ty::method_resolution::iterate_method_candidates(
357 &canonical,
358 db,
359 &self.resolver,
360 name,
361 callback,
362 )
354 } 363 }
355 364
356 #[cfg(test)] 365 #[cfg(test)]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 12e10c751..f4eee835f 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -13,9 +13,10 @@ mod infer;
13pub(crate) mod display; 13pub(crate) mod display;
14 14
15use std::sync::Arc; 15use std::sync::Arc;
16use std::ops::Deref;
16use std::{fmt, mem}; 17use std::{fmt, mem};
17 18
18use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait}; 19use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams};
19use display::{HirDisplay, HirFormatter}; 20use display::{HirDisplay, HirFormatter};
20 21
21pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig}; 22pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig};
@@ -81,13 +82,13 @@ pub enum TypeCtor {
81 /// fn foo() -> i32 { 1 } 82 /// fn foo() -> i32 { 1 }
82 /// let bar: fn() -> i32 = foo; 83 /// let bar: fn() -> i32 = foo;
83 /// ``` 84 /// ```
84 FnPtr, 85 FnPtr { num_args: u16 },
85 86
86 /// The never type `!`. 87 /// The never type `!`.
87 Never, 88 Never,
88 89
89 /// A tuple type. For example, `(i32, bool)`. 90 /// A tuple type. For example, `(i32, bool)`.
90 Tuple, 91 Tuple { cardinality: u16 },
91} 92}
92 93
93/// A nominal type with (maybe 0) type parameters. This might be a primitive 94/// A nominal type with (maybe 0) type parameters. This might be a primitive
@@ -118,9 +119,14 @@ pub enum Ty {
118 /// surrounding impl, then the current function). 119 /// surrounding impl, then the current function).
119 idx: u32, 120 idx: u32,
120 /// The name of the parameter, for displaying. 121 /// The name of the parameter, for displaying.
122 // FIXME get rid of this
121 name: Name, 123 name: Name,
122 }, 124 },
123 125
126 /// A bound type variable. Only used during trait resolution to represent
127 /// Chalk variables.
128 Bound(u32),
129
124 /// A type variable used during type checking. Not to be confused with a 130 /// A type variable used during type checking. Not to be confused with a
125 /// type parameter. 131 /// type parameter.
126 Infer(InferTy), 132 Infer(InferTy),
@@ -150,14 +156,6 @@ impl Substs {
150 Substs(self.0.iter().cloned().take(n).collect::<Vec<_>>().into()) 156 Substs(self.0.iter().cloned().take(n).collect::<Vec<_>>().into())
151 } 157 }
152 158
153 pub fn iter(&self) -> impl Iterator<Item = &Ty> {
154 self.0.iter()
155 }
156
157 pub fn len(&self) -> usize {
158 self.0.len()
159 }
160
161 pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { 159 pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
162 // Without an Arc::make_mut_slice, we can't avoid the clone here: 160 // Without an Arc::make_mut_slice, we can't avoid the clone here:
163 let mut v: Vec<_> = self.0.iter().cloned().collect(); 161 let mut v: Vec<_> = self.0.iter().cloned().collect();
@@ -173,6 +171,30 @@ impl Substs {
173 } 171 }
174 &self.0[0] 172 &self.0[0]
175 } 173 }
174
175 /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
176 pub fn identity(generic_params: &GenericParams) -> Substs {
177 Substs(
178 generic_params
179 .params_including_parent()
180 .into_iter()
181 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
182 .collect::<Vec<_>>()
183 .into(),
184 )
185 }
186
187 /// Return Substs that replace each parameter by a bound variable.
188 pub fn bound_vars(generic_params: &GenericParams) -> Substs {
189 Substs(
190 generic_params
191 .params_including_parent()
192 .into_iter()
193 .map(|p| Ty::Bound(p.idx))
194 .collect::<Vec<_>>()
195 .into(),
196 )
197 }
176} 198}
177 199
178impl From<Vec<Ty>> for Substs { 200impl From<Vec<Ty>> for Substs {
@@ -181,6 +203,14 @@ impl From<Vec<Ty>> for Substs {
181 } 203 }
182} 204}
183 205
206impl Deref for Substs {
207 type Target = [Ty];
208
209 fn deref(&self) -> &[Ty] {
210 &self.0
211 }
212}
213
184/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait. 214/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
185/// Name to be bikeshedded: TraitBound? TraitImplements? 215/// Name to be bikeshedded: TraitBound? TraitImplements?
186#[derive(Clone, PartialEq, Eq, Debug, Hash)] 216#[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -192,10 +222,29 @@ pub struct TraitRef {
192 222
193impl TraitRef { 223impl TraitRef {
194 pub fn self_ty(&self) -> &Ty { 224 pub fn self_ty(&self) -> &Ty {
195 &self.substs.0[0] 225 &self.substs[0]
226 }
227
228 pub fn subst(mut self, substs: &Substs) -> TraitRef {
229 self.substs.walk_mut(&mut |ty_mut| {
230 let ty = mem::replace(ty_mut, Ty::Unknown);
231 *ty_mut = ty.subst(substs);
232 });
233 self
196 } 234 }
197} 235}
198 236
237/// Basically a claim (currently not validated / checked) that the contained
238/// type / trait ref contains no inference variables; any inference variables it
239/// contained have been replaced by bound variables, and `num_vars` tells us how
240/// many there are. This is used to erase irrelevant differences between types
241/// before using them in queries.
242#[derive(Debug, Clone, PartialEq, Eq, Hash)]
243pub(crate) struct Canonical<T> {
244 pub value: T,
245 pub num_vars: usize,
246}
247
199/// A function signature as seen by type inference: Several parameter types and 248/// A function signature as seen by type inference: Several parameter types and
200/// one return type. 249/// one return type.
201#[derive(Clone, PartialEq, Eq, Debug)] 250#[derive(Clone, PartialEq, Eq, Debug)]
@@ -250,7 +299,7 @@ impl Ty {
250 Ty::Apply(ApplicationTy { ctor, parameters }) 299 Ty::Apply(ApplicationTy { ctor, parameters })
251 } 300 }
252 pub fn unit() -> Self { 301 pub fn unit() -> Self {
253 Ty::apply(TypeCtor::Tuple, Substs::empty()) 302 Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
254 } 303 }
255 304
256 pub fn walk(&self, f: &mut impl FnMut(&Ty)) { 305 pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
@@ -260,7 +309,7 @@ impl Ty {
260 t.walk(f); 309 t.walk(f);
261 } 310 }
262 } 311 }
263 Ty::Param { .. } | Ty::Infer(_) | Ty::Unknown => {} 312 Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
264 } 313 }
265 f(self); 314 f(self);
266 } 315 }
@@ -270,7 +319,7 @@ impl Ty {
270 Ty::Apply(a_ty) => { 319 Ty::Apply(a_ty) => {
271 a_ty.parameters.walk_mut(f); 320 a_ty.parameters.walk_mut(f);
272 } 321 }
273 Ty::Param { .. } | Ty::Infer(_) | Ty::Unknown => {} 322 Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
274 } 323 }
275 f(self); 324 f(self);
276 } 325 }
@@ -303,7 +352,9 @@ impl Ty {
303 352
304 pub fn as_tuple(&self) -> Option<&Substs> { 353 pub fn as_tuple(&self) -> Option<&Substs> {
305 match self { 354 match self {
306 Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple, parameters }) => Some(parameters), 355 Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple { .. }, parameters }) => {
356 Some(parameters)
357 }
307 _ => None, 358 _ => None,
308 } 359 }
309 } 360 }
@@ -331,7 +382,7 @@ impl Ty {
331 fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> { 382 fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> {
332 match self { 383 match self {
333 Ty::Apply(a_ty) => match a_ty.ctor { 384 Ty::Apply(a_ty) => match a_ty.ctor {
334 TypeCtor::FnPtr => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)), 385 TypeCtor::FnPtr { .. } => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)),
335 TypeCtor::FnDef(def) => { 386 TypeCtor::FnDef(def) => {
336 let sig = db.callable_item_signature(def); 387 let sig = db.callable_item_signature(def);
337 Some(sig.subst(&a_ty.parameters)) 388 Some(sig.subst(&a_ty.parameters))
@@ -362,16 +413,20 @@ impl Ty {
362 pub fn subst(self, substs: &Substs) -> Ty { 413 pub fn subst(self, substs: &Substs) -> Ty {
363 self.fold(&mut |ty| match ty { 414 self.fold(&mut |ty| match ty {
364 Ty::Param { idx, name } => { 415 Ty::Param { idx, name } => {
365 if (idx as usize) < substs.0.len() { 416 substs.get(idx as usize).cloned().unwrap_or(Ty::Param { idx, name })
366 substs.0[idx as usize].clone()
367 } else {
368 Ty::Param { idx, name }
369 }
370 } 417 }
371 ty => ty, 418 ty => ty,
372 }) 419 })
373 } 420 }
374 421
422 /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
423 pub fn subst_bound_vars(self, substs: &Substs) -> Ty {
424 self.fold(&mut |ty| match ty {
425 Ty::Bound(idx) => substs.get(idx as usize).cloned().unwrap_or(Ty::Bound(idx)),
426 ty => ty,
427 })
428 }
429
375 /// Returns the type parameters of this type if it has some (i.e. is an ADT 430 /// Returns the type parameters of this type if it has some (i.e. is an ADT
376 /// or function); so if `self` is `Option<u32>`, this returns the `u32`. 431 /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
377 fn substs(&self) -> Option<Substs> { 432 fn substs(&self) -> Option<Substs> {
@@ -413,17 +468,17 @@ impl HirDisplay for ApplicationTy {
413 write!(f, "&{}{}", m.as_keyword_for_ref(), t.display(f.db))?; 468 write!(f, "&{}{}", m.as_keyword_for_ref(), t.display(f.db))?;
414 } 469 }
415 TypeCtor::Never => write!(f, "!")?, 470 TypeCtor::Never => write!(f, "!")?,
416 TypeCtor::Tuple => { 471 TypeCtor::Tuple { .. } => {
417 let ts = &self.parameters; 472 let ts = &self.parameters;
418 if ts.0.len() == 1 { 473 if ts.len() == 1 {
419 write!(f, "({},)", ts.0[0].display(f.db))?; 474 write!(f, "({},)", ts[0].display(f.db))?;
420 } else { 475 } else {
421 write!(f, "(")?; 476 write!(f, "(")?;
422 f.write_joined(&*ts.0, ", ")?; 477 f.write_joined(&*ts.0, ", ")?;
423 write!(f, ")")?; 478 write!(f, ")")?;
424 } 479 }
425 } 480 }
426 TypeCtor::FnPtr => { 481 TypeCtor::FnPtr { .. } => {
427 let sig = FnSig::from_fn_ptr_substs(&self.parameters); 482 let sig = FnSig::from_fn_ptr_substs(&self.parameters);
428 write!(f, "fn(")?; 483 write!(f, "fn(")?;
429 f.write_joined(sig.params(), ", ")?; 484 f.write_joined(sig.params(), ", ")?;
@@ -440,7 +495,7 @@ impl HirDisplay for ApplicationTy {
440 CallableDef::Function(_) => write!(f, "fn {}", name)?, 495 CallableDef::Function(_) => write!(f, "fn {}", name)?,
441 CallableDef::Struct(_) | CallableDef::EnumVariant(_) => write!(f, "{}", name)?, 496 CallableDef::Struct(_) | CallableDef::EnumVariant(_) => write!(f, "{}", name)?,
442 } 497 }
443 if self.parameters.0.len() > 0 { 498 if self.parameters.len() > 0 {
444 write!(f, "<")?; 499 write!(f, "<")?;
445 f.write_joined(&*self.parameters.0, ", ")?; 500 f.write_joined(&*self.parameters.0, ", ")?;
446 write!(f, ">")?; 501 write!(f, ">")?;
@@ -456,7 +511,7 @@ impl HirDisplay for ApplicationTy {
456 } 511 }
457 .unwrap_or_else(Name::missing); 512 .unwrap_or_else(Name::missing);
458 write!(f, "{}", name)?; 513 write!(f, "{}", name)?;
459 if self.parameters.0.len() > 0 { 514 if self.parameters.len() > 0 {
460 write!(f, "<")?; 515 write!(f, "<")?;
461 f.write_joined(&*self.parameters.0, ", ")?; 516 f.write_joined(&*self.parameters.0, ", ")?;
462 write!(f, ">")?; 517 write!(f, ">")?;
@@ -472,6 +527,7 @@ impl HirDisplay for Ty {
472 match self { 527 match self {
473 Ty::Apply(a_ty) => a_ty.hir_fmt(f)?, 528 Ty::Apply(a_ty) => a_ty.hir_fmt(f)?,
474 Ty::Param { name, .. } => write!(f, "{}", name)?, 529 Ty::Param { name, .. } => write!(f, "{}", name)?,
530 Ty::Bound(idx) => write!(f, "?{}", idx)?,
475 Ty::Unknown => write!(f, "{{unknown}}")?, 531 Ty::Unknown => write!(f, "{{unknown}}")?,
476 Ty::Infer(..) => write!(f, "_")?, 532 Ty::Infer(..) => write!(f, "_")?,
477 } 533 }
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index c7772a7f6..edce1afe7 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -44,9 +44,12 @@ use crate::{
44}; 44};
45use super::{ 45use super::{
46 Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef, 46 Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
47 traits::{ Solution, Obligation, Guidance}, 47 traits::{Solution, Obligation, Guidance},
48 method_resolution,
48}; 49};
49 50
51mod unify;
52
50/// The entry point of type inference. 53/// The entry point of type inference.
51pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> { 54pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
52 db.check_canceled(); 55 db.check_canceled();
@@ -321,30 +324,29 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
321 fn resolve_obligations_as_possible(&mut self) { 324 fn resolve_obligations_as_possible(&mut self) {
322 let obligations = mem::replace(&mut self.obligations, Vec::new()); 325 let obligations = mem::replace(&mut self.obligations, Vec::new());
323 for obligation in obligations { 326 for obligation in obligations {
324 // FIXME resolve types in the obligation first 327 let (solution, canonicalized) = match &obligation {
325 let (solution, var_mapping) = match &obligation {
326 Obligation::Trait(tr) => { 328 Obligation::Trait(tr) => {
327 let (tr, var_mapping) = super::traits::canonicalize(tr.clone()); 329 let canonicalized = self.canonicalizer().canonicalize_trait_ref(tr.clone());
328 (self.db.implements(tr), var_mapping) 330 (
331 super::traits::implements(
332 self.db,
333 self.resolver.krate().unwrap(),
334 canonicalized.value.clone(),
335 ),
336 canonicalized,
337 )
329 } 338 }
330 }; 339 };
331 match solution { 340 match solution {
332 Some(Solution::Unique(substs)) => { 341 Some(Solution::Unique(substs)) => {
333 for (i, subst) in substs.0.iter().enumerate() { 342 canonicalized.apply_solution(self, substs.0);
334 let uncanonical = var_mapping[i];
335 // FIXME the subst may contain type variables, which would need to be mapped back as well
336 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
337 }
338 } 343 }
339 Some(Solution::Ambig(Guidance::Definite(substs))) => { 344 Some(Solution::Ambig(Guidance::Definite(substs))) => {
340 for (i, subst) in substs.0.iter().enumerate() { 345 canonicalized.apply_solution(self, substs.0);
341 let uncanonical = var_mapping[i];
342 // FIXME the subst may contain type variables, which would need to be mapped back as well
343 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
344 }
345 self.obligations.push(obligation); 346 self.obligations.push(obligation);
346 } 347 }
347 Some(_) => { 348 Some(_) => {
349 // FIXME use this when trying to resolve everything at the end
348 self.obligations.push(obligation); 350 self.obligations.push(obligation);
349 } 351 }
350 None => { 352 None => {
@@ -737,14 +739,14 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
737 }; 739 };
738 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown)); 740 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
739 741
740 let inner_tys = args 742 let inner_tys: Substs = args
741 .iter() 743 .iter()
742 .zip(expectations_iter) 744 .zip(expectations_iter)
743 .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm)) 745 .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
744 .collect::<Vec<_>>() 746 .collect::<Vec<_>>()
745 .into(); 747 .into();
746 748
747 Ty::apply(TypeCtor::Tuple, Substs(inner_tys)) 749 Ty::apply(TypeCtor::Tuple { cardinality: inner_tys.len() as u16 }, inner_tys)
748 } 750 }
749 Pat::Ref { pat, mutability } => { 751 Pat::Ref { pat, mutability } => {
750 let expectation = match expected.as_reference() { 752 let expectation = match expected.as_reference() {
@@ -877,9 +879,16 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
877 generic_args: Option<&GenericArgs>, 879 generic_args: Option<&GenericArgs>,
878 ) -> Ty { 880 ) -> Ty {
879 let receiver_ty = self.infer_expr(receiver, &Expectation::none()); 881 let receiver_ty = self.infer_expr(receiver, &Expectation::none());
880 let resolved = receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver); 882 let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone());
883 let resolved = method_resolution::lookup_method(
884 &canonicalized_receiver.value,
885 self.db,
886 method_name,
887 &self.resolver,
888 );
881 let (derefed_receiver_ty, method_ty, def_generics) = match resolved { 889 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
882 Some((ty, func)) => { 890 Some((ty, func)) => {
891 let ty = canonicalized_receiver.decanonicalize_ty(ty);
883 self.write_method_resolution(tgt_expr, func); 892 self.write_method_resolution(tgt_expr, func);
884 ( 893 (
885 ty, 894 ty,
@@ -1064,7 +1073,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
1064 .autoderef(self.db) 1073 .autoderef(self.db)
1065 .find_map(|derefed_ty| match derefed_ty { 1074 .find_map(|derefed_ty| match derefed_ty {
1066 Ty::Apply(a_ty) => match a_ty.ctor { 1075 Ty::Apply(a_ty) => match a_ty.ctor {
1067 TypeCtor::Tuple => { 1076 TypeCtor::Tuple { .. } => {
1068 let i = name.to_string().parse::<usize>().ok(); 1077 let i = name.to_string().parse::<usize>().ok();
1069 i.and_then(|i| a_ty.parameters.0.get(i).cloned()) 1078 i.and_then(|i| a_ty.parameters.0.get(i).cloned())
1070 } 1079 }
@@ -1175,7 +1184,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
1175 ty_vec.push(self.infer_expr(*arg, &Expectation::none())); 1184 ty_vec.push(self.infer_expr(*arg, &Expectation::none()));
1176 } 1185 }
1177 1186
1178 Ty::apply(TypeCtor::Tuple, Substs(ty_vec.into())) 1187 Ty::apply(
1188 TypeCtor::Tuple { cardinality: ty_vec.len() as u16 },
1189 Substs(ty_vec.into()),
1190 )
1179 } 1191 }
1180 Expr::Array(array) => { 1192 Expr::Array(array) => {
1181 let elem_ty = match &expected.ty { 1193 let elem_ty = match &expected.ty {
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
new file mode 100644
index 000000000..8ca7e957d
--- /dev/null
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -0,0 +1,122 @@
1//! Unification and canonicalization logic.
2
3use crate::db::HirDatabase;
4use crate::ty::{Ty, Canonical, TraitRef, InferTy};
5use super::InferenceContext;
6
7impl<'a, D: HirDatabase> InferenceContext<'a, D> {
8 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
9 where
10 'a: 'b,
11 {
12 Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() }
13 }
14}
15
16pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
17where
18 'a: 'b,
19{
20 ctx: &'b mut InferenceContext<'a, D>,
21 free_vars: Vec<InferTy>,
22 /// A stack of type variables that is used to detect recursive types (which
23 /// are an error, but we need to protect against them to avoid stack
24 /// overflows).
25 var_stack: Vec<super::TypeVarId>,
26}
27
28pub(super) struct Canonicalized<T> {
29 pub value: Canonical<T>,
30 free_vars: Vec<InferTy>,
31}
32
33impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D>
34where
35 'a: 'b,
36{
37 fn add(&mut self, free_var: InferTy) -> usize {
38 self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
39 let next_index = self.free_vars.len();
40 self.free_vars.push(free_var);
41 next_index
42 })
43 }
44
45 fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty {
46 ty.fold(&mut |ty| match ty {
47 Ty::Infer(tv) => {
48 let inner = tv.to_inner();
49 if self.var_stack.contains(&inner) {
50 // recursive type
51 return tv.fallback_value();
52 }
53 if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() {
54 self.var_stack.push(inner);
55 let result = self.do_canonicalize_ty(known_ty.clone());
56 self.var_stack.pop();
57 result
58 } else {
59 let free_var = InferTy::TypeVar(self.ctx.var_unification_table.find(inner));
60 let position = self.add(free_var);
61 Ty::Bound(position as u32)
62 }
63 }
64 _ => ty,
65 })
66 }
67
68 fn do_canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> TraitRef {
69 let substs = trait_ref
70 .substs
71 .iter()
72 .map(|ty| self.do_canonicalize_ty(ty.clone()))
73 .collect::<Vec<_>>();
74 TraitRef { trait_: trait_ref.trait_, substs: substs.into() }
75 }
76
77 fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
78 Canonicalized {
79 value: Canonical { value: result, num_vars: self.free_vars.len() },
80 free_vars: self.free_vars,
81 }
82 }
83
84 pub fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
85 let result = self.do_canonicalize_ty(ty);
86 self.into_canonicalized(result)
87 }
88
89 pub fn canonicalize_trait_ref(mut self, trait_ref: TraitRef) -> Canonicalized<TraitRef> {
90 let result = self.do_canonicalize_trait_ref(trait_ref);
91 self.into_canonicalized(result)
92 }
93}
94
95impl<T> Canonicalized<T> {
96 pub fn decanonicalize_ty(&self, ty: Ty) -> Ty {
97 ty.fold(&mut |ty| match ty {
98 Ty::Bound(idx) => {
99 if (idx as usize) < self.free_vars.len() {
100 Ty::Infer(self.free_vars[idx as usize].clone())
101 } else {
102 Ty::Bound(idx)
103 }
104 }
105 ty => ty,
106 })
107 }
108
109 pub fn apply_solution(
110 &self,
111 ctx: &mut InferenceContext<'_, impl HirDatabase>,
112 solution: Canonical<Vec<Ty>>,
113 ) {
114 // the solution may contain new variables, which we need to convert to new inference vars
115 let new_vars =
116 (0..solution.num_vars).map(|_| ctx.new_type_var()).collect::<Vec<_>>().into();
117 for (i, ty) in solution.value.into_iter().enumerate() {
118 let var = self.free_vars[i].clone();
119 ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
120 }
121 }
122}
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 7fac084ce..8bab7e54b 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -29,7 +29,10 @@ impl Ty {
29 TypeRef::Tuple(inner) => { 29 TypeRef::Tuple(inner) => {
30 let inner_tys = 30 let inner_tys =
31 inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); 31 inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
32 Ty::apply(TypeCtor::Tuple, Substs(inner_tys.into())) 32 Ty::apply(
33 TypeCtor::Tuple { cardinality: inner_tys.len() as u16 },
34 Substs(inner_tys.into()),
35 )
33 } 36 }
34 TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path), 37 TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path),
35 TypeRef::RawPtr(inner, mutability) => { 38 TypeRef::RawPtr(inner, mutability) => {
@@ -53,7 +56,7 @@ impl Ty {
53 let inner_tys = 56 let inner_tys =
54 params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); 57 params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
55 let sig = Substs(inner_tys.into()); 58 let sig = Substs(inner_tys.into());
56 Ty::apply(TypeCtor::FnPtr, sig) 59 Ty::apply(TypeCtor::FnPtr { num_args: sig.len() as u16 - 1 }, sig)
57 } 60 }
58 TypeRef::Error => Ty::Unknown, 61 TypeRef::Error => Ty::Unknown,
59 } 62 }
@@ -238,6 +241,11 @@ impl TraitRef {
238 let segment = path.segments.last().expect("path should have at least one segment"); 241 let segment = path.segments.last().expect("path should have at least one segment");
239 substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true) 242 substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true)
240 } 243 }
244
245 pub(crate) fn for_trait(db: &impl HirDatabase, trait_: Trait) -> TraitRef {
246 let substs = Substs::identity(&trait_.generic_params(db));
247 TraitRef { trait_, substs }
248 }
241} 249}
242 250
243/// Build the declared type of an item. This depends on the namespace; e.g. for 251/// Build the declared type of an item. This depends on the namespace; e.g. for
@@ -299,7 +307,7 @@ fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig {
299/// function body. 307/// function body.
300fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { 308fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty {
301 let generics = def.generic_params(db); 309 let generics = def.generic_params(db);
302 let substs = make_substs(&generics); 310 let substs = Substs::identity(&generics);
303 Ty::apply(TypeCtor::FnDef(def.into()), substs) 311 Ty::apply(TypeCtor::FnDef(def.into()), substs)
304} 312}
305 313
@@ -341,7 +349,7 @@ fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty {
341 return type_for_struct(db, def); // Unit struct 349 return type_for_struct(db, def); // Unit struct
342 } 350 }
343 let generics = def.generic_params(db); 351 let generics = def.generic_params(db);
344 let substs = make_substs(&generics); 352 let substs = Substs::identity(&generics);
345 Ty::apply(TypeCtor::FnDef(def.into()), substs) 353 Ty::apply(TypeCtor::FnDef(def.into()), substs)
346} 354}
347 355
@@ -357,7 +365,7 @@ fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant)
357 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) 365 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
358 .collect::<Vec<_>>(); 366 .collect::<Vec<_>>();
359 let generics = def.parent_enum(db).generic_params(db); 367 let generics = def.parent_enum(db).generic_params(db);
360 let substs = make_substs(&generics); 368 let substs = Substs::identity(&generics);
361 let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs); 369 let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs);
362 FnSig::from_params_and_return(params, ret) 370 FnSig::from_params_and_return(params, ret)
363} 371}
@@ -369,36 +377,25 @@ fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) ->
369 return type_for_enum(db, def.parent_enum(db)); // Unit variant 377 return type_for_enum(db, def.parent_enum(db)); // Unit variant
370 } 378 }
371 let generics = def.parent_enum(db).generic_params(db); 379 let generics = def.parent_enum(db).generic_params(db);
372 let substs = make_substs(&generics); 380 let substs = Substs::identity(&generics);
373 Ty::apply(TypeCtor::FnDef(def.into()), substs) 381 Ty::apply(TypeCtor::FnDef(def.into()), substs)
374} 382}
375 383
376fn make_substs(generics: &GenericParams) -> Substs {
377 Substs(
378 generics
379 .params_including_parent()
380 .into_iter()
381 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
382 .collect::<Vec<_>>()
383 .into(),
384 )
385}
386
387fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { 384fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty {
388 let generics = s.generic_params(db); 385 let generics = s.generic_params(db);
389 Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) 386 Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
390} 387}
391 388
392fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { 389fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty {
393 let generics = s.generic_params(db); 390 let generics = s.generic_params(db);
394 Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) 391 Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
395} 392}
396 393
397fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty { 394fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty {
398 let generics = t.generic_params(db); 395 let generics = t.generic_params(db);
399 let resolver = t.resolver(db); 396 let resolver = t.resolver(db);
400 let type_ref = t.type_ref(db); 397 let type_ref = t.type_ref(db);
401 let substs = make_substs(&generics); 398 let substs = Substs::identity(&generics);
402 let inner = Ty::from_hir(db, &resolver, &type_ref); 399 let inner = Ty::from_hir(db, &resolver, &type_ref);
403 inner.subst(&substs) 400 inner.subst(&substs)
404} 401}
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index ea6e0dc0f..607e9ba79 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -16,7 +16,7 @@ use crate::{
16 generics::HasGenericParams, 16 generics::HasGenericParams,
17 ty::primitive::{UncertainIntTy, UncertainFloatTy} 17 ty::primitive::{UncertainIntTy, UncertainFloatTy}
18}; 18};
19use super::{TraitRef, Substs}; 19use super::{TraitRef, Canonical};
20 20
21/// This is used as a key for indexing impls. 21/// This is used as a key for indexing impls.
22#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] 22#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -130,124 +130,122 @@ fn def_crate(db: &impl HirDatabase, cur_crate: Crate, ty: &Ty) -> Option<Crate>
130 } 130 }
131} 131}
132 132
133impl Ty { 133/// Look up the method with the given name, returning the actual autoderefed
134 /// Look up the method with the given name, returning the actual autoderefed 134/// receiver type (but without autoref applied yet).
135 /// receiver type (but without autoref applied yet). 135pub(crate) fn lookup_method(
136 pub(crate) fn lookup_method( 136 ty: &Canonical<Ty>,
137 self, 137 db: &impl HirDatabase,
138 db: &impl HirDatabase, 138 name: &Name,
139 name: &Name, 139 resolver: &Resolver,
140 resolver: &Resolver, 140) -> Option<(Ty, Function)> {
141 ) -> Option<(Ty, Function)> { 141 iterate_method_candidates(ty, db, resolver, Some(name), |ty, f| Some((ty.clone(), f)))
142 self.iterate_method_candidates(db, resolver, Some(name), |ty, f| Some((ty.clone(), f))) 142}
143 }
144 143
145 // This would be nicer if it just returned an iterator, but that runs into 144// This would be nicer if it just returned an iterator, but that runs into
146 // lifetime problems, because we need to borrow temp `CrateImplBlocks`. 145// lifetime problems, because we need to borrow temp `CrateImplBlocks`.
147 pub(crate) fn iterate_method_candidates<T>( 146pub(crate) fn iterate_method_candidates<T>(
148 self, 147 ty: &Canonical<Ty>,
149 db: &impl HirDatabase, 148 db: &impl HirDatabase,
150 resolver: &Resolver, 149 resolver: &Resolver,
151 name: Option<&Name>, 150 name: Option<&Name>,
152 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 151 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
153 ) -> Option<T> { 152) -> Option<T> {
154 // For method calls, rust first does any number of autoderef, and then one 153 // For method calls, rust first does any number of autoderef, and then one
155 // autoref (i.e. when the method takes &self or &mut self). We just ignore 154 // autoref (i.e. when the method takes &self or &mut self). We just ignore
156 // the autoref currently -- when we find a method matching the given name, 155 // the autoref currently -- when we find a method matching the given name,
157 // we assume it fits. 156 // we assume it fits.
158 157
159 // Also note that when we've got a receiver like &S, even if the method we 158 // Also note that when we've got a receiver like &S, even if the method we
160 // find in the end takes &self, we still do the autoderef step (just as 159 // find in the end takes &self, we still do the autoderef step (just as
161 // rustc does an autoderef and then autoref again). 160 // rustc does an autoderef and then autoref again).
162 161
163 let krate = resolver.krate()?; 162 let krate = resolver.krate()?;
164 for derefed_ty in self.autoderef(db) { 163 for derefed_ty in ty.value.clone().autoderef(db) {
165 if let Some(result) = 164 let derefed_ty = Canonical { value: derefed_ty, num_vars: ty.num_vars };
166 derefed_ty.iterate_inherent_methods(db, name, krate, &mut callback) 165 if let Some(result) = iterate_inherent_methods(&derefed_ty, db, name, krate, &mut callback)
167 { 166 {
168 return Some(result); 167 return Some(result);
169 } 168 }
170 if let Some(result) = 169 if let Some(result) =
171 derefed_ty.iterate_trait_method_candidates(db, resolver, name, &mut callback) 170 iterate_trait_method_candidates(&derefed_ty, db, resolver, name, &mut callback)
172 { 171 {
173 return Some(result); 172 return Some(result);
174 }
175 } 173 }
176 None
177 } 174 }
175 None
176}
178 177
179 fn iterate_trait_method_candidates<T>( 178fn iterate_trait_method_candidates<T>(
180 &self, 179 ty: &Canonical<Ty>,
181 db: &impl HirDatabase, 180 db: &impl HirDatabase,
182 resolver: &Resolver, 181 resolver: &Resolver,
183 name: Option<&Name>, 182 name: Option<&Name>,
184 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 183 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
185 ) -> Option<T> { 184) -> Option<T> {
186 'traits: for t in resolver.traits_in_scope() { 185 let krate = resolver.krate()?;
187 let data = t.trait_data(db); 186 'traits: for t in resolver.traits_in_scope() {
188 // we'll be lazy about checking whether the type implements the 187 let data = t.trait_data(db);
189 // trait, but if we find out it doesn't, we'll skip the rest of the 188 // we'll be lazy about checking whether the type implements the
190 // iteration 189 // trait, but if we find out it doesn't, we'll skip the rest of the
191 let mut known_implemented = false; 190 // iteration
192 for item in data.items() { 191 let mut known_implemented = false;
193 match item { 192 for item in data.items() {
194 &TraitItem::Function(m) => { 193 match item {
195 let sig = m.signature(db); 194 &TraitItem::Function(m) => {
196 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { 195 let sig = m.signature(db);
197 if !known_implemented { 196 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
198 let trait_ref = TraitRef { 197 if !known_implemented {
199 trait_: t, 198 let trait_ref = canonical_trait_ref(db, t, ty.clone());
200 substs: fresh_substs_for_trait(db, t, self.clone()), 199 // FIXME cache this implements check (without solution) in a query?
201 }; 200 if super::traits::implements(db, krate, trait_ref).is_none() {
202 let (trait_ref, _) = super::traits::canonicalize(trait_ref); 201 continue 'traits;
203 if db.implements(trait_ref).is_none() {
204 continue 'traits;
205 }
206 }
207 known_implemented = true;
208 if let Some(result) = callback(self, m) {
209 return Some(result);
210 } 202 }
211 } 203 }
204 known_implemented = true;
205 if let Some(result) = callback(&ty.value, m) {
206 return Some(result);
207 }
212 } 208 }
213 _ => {}
214 } 209 }
210 _ => {}
215 } 211 }
216 } 212 }
217 None
218 } 213 }
214 None
215}
219 216
220 fn iterate_inherent_methods<T>( 217fn iterate_inherent_methods<T>(
221 &self, 218 ty: &Canonical<Ty>,
222 db: &impl HirDatabase, 219 db: &impl HirDatabase,
223 name: Option<&Name>, 220 name: Option<&Name>,
224 krate: Crate, 221 krate: Crate,
225 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 222 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
226 ) -> Option<T> { 223) -> Option<T> {
227 let krate = match def_crate(db, krate, self) { 224 let krate = match def_crate(db, krate, &ty.value) {
228 Some(krate) => krate, 225 Some(krate) => krate,
229 None => return None, 226 None => return None,
230 }; 227 };
231 let impls = db.impls_in_crate(krate); 228 let impls = db.impls_in_crate(krate);
232 229
233 for impl_block in impls.lookup_impl_blocks(self) { 230 for impl_block in impls.lookup_impl_blocks(&ty.value) {
234 for item in impl_block.items(db) { 231 for item in impl_block.items(db) {
235 match item { 232 match item {
236 ImplItem::Method(f) => { 233 ImplItem::Method(f) => {
237 let sig = f.signature(db); 234 let sig = f.signature(db);
238 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { 235 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
239 if let Some(result) = callback(self, f) { 236 if let Some(result) = callback(&ty.value, f) {
240 return Some(result); 237 return Some(result);
241 }
242 } 238 }
243 } 239 }
244 _ => {}
245 } 240 }
241 _ => {}
246 } 242 }
247 } 243 }
248 None
249 } 244 }
245 None
246}
250 247
248impl Ty {
251 // This would be nicer if it just returned an iterator, but that runs into 249 // This would be nicer if it just returned an iterator, but that runs into
252 // lifetime problems, because we need to borrow temp `CrateImplBlocks`. 250 // lifetime problems, because we need to borrow temp `CrateImplBlocks`.
253 pub fn iterate_impl_items<T>( 251 pub fn iterate_impl_items<T>(
@@ -271,15 +269,26 @@ impl Ty {
271} 269}
272 270
273/// This creates Substs for a trait with the given Self type and type variables 271/// This creates Substs for a trait with the given Self type and type variables
274/// for all other parameters. This is kind of a hack since these aren't 'real' 272/// for all other parameters, to query Chalk with it.
275/// type variables; the resulting trait reference is just used for the 273fn canonical_trait_ref(
276/// preliminary method candidate check. 274 db: &impl HirDatabase,
277fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs { 275 trait_: Trait,
276 self_ty: Canonical<Ty>,
277) -> Canonical<TraitRef> {
278 let mut substs = Vec::new(); 278 let mut substs = Vec::new();
279 let generics = tr.generic_params(db); 279 let generics = trait_.generic_params(db);
280 substs.push(self_ty); 280 let num_vars = self_ty.num_vars;
281 substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map( 281 substs.push(self_ty.value);
282 |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))), 282 substs.extend(
283 )); 283 generics
284 substs.into() 284 .params_including_parent()
285 .into_iter()
286 .skip(1)
287 .enumerate()
288 .map(|(i, _p)| Ty::Bound((i + num_vars) as u32)),
289 );
290 Canonical {
291 num_vars: substs.len() - 1 + self_ty.num_vars,
292 value: TraitRef { trait_, substs: substs.into() },
293 }
285} 294}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index c76a5012f..0aecde37c 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2140,7 +2140,7 @@ fn test() {
2140[102; 127) '{ ...d(); }': () 2140[102; 127) '{ ...d(); }': ()
2141[108; 109) 'S': S<u32>(T) -> S<T> 2141[108; 109) 'S': S<u32>(T) -> S<T>
2142[108; 115) 'S(1u32)': S<u32> 2142[108; 115) 'S(1u32)': S<u32>
2143[108; 124) 'S(1u32...thod()': {unknown} 2143[108; 124) 'S(1u32...thod()': u32
2144[110; 114) '1u32': u32"### 2144[110; 114) '1u32': u32"###
2145 ); 2145 );
2146} 2146}
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 06f483899..a1ed0c028 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -1,47 +1,65 @@
1//! Stuff that will probably mostly replaced by Chalk. 1//! Trait solving using Chalk.
2use std::collections::HashMap; 2use std::sync::{Arc, Mutex};
3 3
4use crate::{db::HirDatabase, generics::HasGenericParams}; 4use log::debug;
5use super::{TraitRef, Substs, infer::{TypeVarId, InferTy}, Ty}; 5use chalk_ir::cast::Cast;
6 6
7// Copied (and simplified) from Chalk 7use crate::{Crate, Trait, db::HirDatabase, ImplBlock};
8use super::{TraitRef, Ty, Canonical};
8 9
9#[derive(Clone, Debug, PartialEq, Eq)] 10use self::chalk::{ToChalk, from_chalk};
10/// A (possible) solution for a proposed goal. Usually packaged in a `Result`,
11/// where `Err` represents definite *failure* to prove a goal.
12pub enum Solution {
13 /// The goal indeed holds, and there is a unique value for all existential
14 /// variables.
15 Unique(Substs),
16 11
17 /// The goal may be provable in multiple ways, but regardless we may have some guidance 12mod chalk;
18 /// for type inference. 13
19 Ambig(Guidance), 14pub(crate) type Solver = chalk_solve::Solver;
15
16#[derive(Debug, Copy, Clone)]
17struct ChalkContext<'a, DB> {
18 db: &'a DB,
19 krate: Crate,
20} 20}
21 21
22#[derive(Clone, Debug, PartialEq, Eq)] 22pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>> {
23/// When a goal holds ambiguously (e.g., because there are multiple possible 23 // krate parameter is just so we cache a unique solver per crate
24/// solutions), we issue a set of *guidance* back to type inference. 24 let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 10 };
25pub enum Guidance { 25 Arc::new(Mutex::new(solver_choice.into_solver()))
26 /// The existential variables *must* have the given values if the goal is 26}
27 /// ever to hold, but that alone isn't enough to guarantee the goal will
28 /// actually hold.
29 Definite(Substs),
30 27
31 /// There are multiple plausible values for the existentials, but the ones 28/// Collects impls for the given trait in the whole dependency tree of `krate`.
32 /// here are suggested as the preferred choice heuristically. These should 29pub(crate) fn impls_for_trait(
33 /// be used for inference fallback only. 30 db: &impl HirDatabase,
34 Suggested(Substs), 31 krate: Crate,
32 trait_: Trait,
33) -> Arc<[ImplBlock]> {
34 let mut impls = Vec::new();
35 // We call the query recursively here. On the one hand, this means we can
36 // reuse results from queries for different crates; on the other hand, this
37 // will only ever get called for a few crates near the root of the tree (the
38 // ones the user is editing), so this may actually be a waste of memory. I'm
39 // doing it like this mainly for simplicity for now.
40 for dep in krate.dependencies(db) {
41 impls.extend(db.impls_for_trait(dep.krate, trait_).iter());
42 }
43 let crate_impl_blocks = db.impls_in_crate(krate);
44 impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_));
45 impls.into()
46}
35 47
36 /// There's no useful information to feed back to type inference 48fn solve(
37 Unknown, 49 db: &impl HirDatabase,
50 krate: Crate,
51 goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal>>,
52) -> Option<chalk_solve::Solution> {
53 let context = ChalkContext { db, krate };
54 let solver = db.solver(krate);
55 let solution = solver.lock().unwrap().solve(&context, goal);
56 debug!("solve({:?}) => {:?}", goal, solution);
57 solution
38} 58}
39 59
40/// Something that needs to be proven (by Chalk) during type checking, e.g. that 60/// Something that needs to be proven (by Chalk) during type checking, e.g. that
41/// a certain type implements a certain trait. Proving the Obligation might 61/// a certain type implements a certain trait. Proving the Obligation might
42/// result in additional information about inference variables. 62/// result in additional information about inference variables.
43///
44/// This might be handled by Chalk when we integrate it?
45#[derive(Clone, Debug, PartialEq, Eq)] 63#[derive(Clone, Debug, PartialEq, Eq)]
46pub enum Obligation { 64pub enum Obligation {
47 /// Prove that a certain type implements a trait (the type is the `Self` type 65 /// Prove that a certain type implements a trait (the type is the `Self` type
@@ -49,67 +67,94 @@ pub enum Obligation {
49 Trait(TraitRef), 67 Trait(TraitRef),
50} 68}
51 69
52/// Rudimentary check whether an impl exists for a given type and trait; this 70/// Check using Chalk whether trait is implemented for given parameters including `Self` type.
53/// will actually be done by chalk. 71pub(crate) fn implements(
54pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> { 72 db: &impl HirDatabase,
55 // FIXME use all trait impls in the whole crate graph 73 krate: Crate,
56 let krate = trait_ref.trait_.module(db).krate(db); 74 trait_ref: Canonical<TraitRef>,
57 let krate = match krate { 75) -> Option<Solution> {
58 Some(krate) => krate, 76 let goal: chalk_ir::Goal = trait_ref.value.to_chalk(db).cast();
59 None => return None, 77 debug!("goal: {:?}", goal);
60 }; 78 let env = chalk_ir::Environment::new();
61 let crate_impl_blocks = db.impls_in_crate(krate); 79 let in_env = chalk_ir::InEnvironment::new(&env, goal);
62 let mut impl_blocks = crate_impl_blocks 80 let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT);
63 .lookup_impl_blocks_for_trait(&trait_ref.trait_) 81 let canonical =
64 // we don't handle where clauses at all, waiting for Chalk for that 82 chalk_ir::Canonical { value: in_env, binders: vec![parameter; trait_ref.num_vars] };
65 .filter(|impl_block| impl_block.generic_params(db).where_predicates.is_empty()); 83 // We currently don't deal with universes (I think / hope they're not yet
66 impl_blocks 84 // relevant for our use cases?)
67 .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?)) 85 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
86 let solution = solve(db, krate, &u_canonical);
87 solution.map(|solution| solution_from_chalk(db, solution))
68} 88}
69 89
70pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) { 90fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -> Solution {
71 let mut canonical = HashMap::new(); // mapping uncanonical -> canonical 91 let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| {
72 let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense) 92 let value = subst
73 let mut substs = trait_ref.substs.0.to_vec(); 93 .value
74 for ty in &mut substs { 94 .parameters
75 ty.walk_mut(&mut |ty| match ty { 95 .into_iter()
76 Ty::Infer(InferTy::TypeVar(tv)) => { 96 .map(|p| {
77 let tv: &mut TypeVarId = tv; 97 let ty = match p {
78 *tv = *canonical.entry(*tv).or_insert_with(|| { 98 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
79 let i = uncanonical.len(); 99 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
80 uncanonical.push(*tv); 100 };
81 TypeVarId(i as u32) 101 ty
82 }); 102 })
83 } 103 .collect();
84 _ => {} 104 let result = Canonical { value, num_vars: subst.binders.len() };
85 }); 105 SolutionVariables(result)
106 };
107 match solution {
108 chalk_solve::Solution::Unique(constr_subst) => {
109 let subst = chalk_ir::Canonical {
110 value: constr_subst.value.subst,
111 binders: constr_subst.binders,
112 };
113 Solution::Unique(convert_subst(subst))
114 }
115 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst)) => {
116 Solution::Ambig(Guidance::Definite(convert_subst(subst)))
117 }
118 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst)) => {
119 Solution::Ambig(Guidance::Suggested(convert_subst(subst)))
120 }
121 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown) => {
122 Solution::Ambig(Guidance::Unknown)
123 }
86 } 124 }
87 (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical)
88} 125}
89 126
90fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> { 127#[derive(Clone, Debug, PartialEq, Eq)]
91 if tr1.trait_ != tr2.trait_ { 128pub(crate) struct SolutionVariables(pub Canonical<Vec<Ty>>);
92 return None; 129
93 } 130#[derive(Clone, Debug, PartialEq, Eq)]
94 let mut solution_substs = Vec::new(); 131/// A (possible) solution for a proposed goal.
95 for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) { 132pub(crate) enum Solution {
96 // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass 133 /// The goal indeed holds, and there is a unique value for all existential
97 match (t1, t2) { 134 /// variables.
98 (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => { 135 Unique(SolutionVariables),
99 // type variable (or similar) in the impl, we just assume it works 136
100 } 137 /// The goal may be provable in multiple ways, but regardless we may have some guidance
101 (Ty::Infer(InferTy::TypeVar(v1)), _) => { 138 /// for type inference. In this case, we don't return any lifetime
102 // type variable in the query and fixed type in the impl, record its value 139 /// constraints, since we have not "committed" to any particular solution
103 solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown); 140 /// yet.
104 solution_substs[v1.0 as usize] = t2.clone(); 141 Ambig(Guidance),
105 } 142}
106 _ => { 143
107 // check that they're equal (actually we'd have to recurse etc.) 144#[derive(Clone, Debug, PartialEq, Eq)]
108 if t1 != t2 { 145/// When a goal holds ambiguously (e.g., because there are multiple possible
109 return None; 146/// solutions), we issue a set of *guidance* back to type inference.
110 } 147pub(crate) enum Guidance {
111 } 148 /// The existential variables *must* have the given values if the goal is
112 } 149 /// ever to hold, but that alone isn't enough to guarantee the goal will
113 } 150 /// actually hold.
114 Some(Solution::Unique(solution_substs.into())) 151 Definite(SolutionVariables),
152
153 /// There are multiple plausible values for the existentials, but the ones
154 /// here are suggested as the preferred choice heuristically. These should
155 /// be used for inference fallback only.
156 Suggested(SolutionVariables),
157
158 /// There's no useful information to feed back to type inference
159 Unknown,
115} 160}
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
new file mode 100644
index 000000000..8b77d21b4
--- /dev/null
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -0,0 +1,333 @@
1//! Conversion code from/to Chalk.
2use std::sync::Arc;
3
4use log::debug;
5
6use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
7use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum};
8
9use ra_db::salsa::{InternId, InternKey};
10
11use crate::{
12 Trait, HasGenericParams, ImplBlock,
13 db::HirDatabase,
14 ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs},
15};
16use super::ChalkContext;
17
18pub(super) trait ToChalk {
19 type Chalk;
20 fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk;
21 fn from_chalk(db: &impl HirDatabase, chalk: Self::Chalk) -> Self;
22}
23
24pub(super) fn from_chalk<T, ChalkT>(db: &impl HirDatabase, chalk: ChalkT) -> T
25where
26 T: ToChalk<Chalk = ChalkT>,
27{
28 T::from_chalk(db, chalk)
29}
30
31impl ToChalk for Ty {
32 type Chalk = chalk_ir::Ty;
33 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Ty {
34 match self {
35 Ty::Apply(apply_ty) => {
36 let struct_id = apply_ty.ctor.to_chalk(db);
37 let name = TypeName::TypeKindId(struct_id.into());
38 let parameters = apply_ty.parameters.to_chalk(db);
39 chalk_ir::ApplicationTy { name, parameters }.cast()
40 }
41 Ty::Param { idx, .. } => {
42 PlaceholderIndex { ui: UniverseIndex::ROOT, idx: idx as usize }.to_ty()
43 }
44 Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize),
45 Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
46 // FIXME this is clearly incorrect, but probably not too incorrect
47 // and I'm not sure what to actually do with Ty::Unknown
48 Ty::Unknown => PlaceholderIndex { ui: UniverseIndex::ROOT, idx: 0 }.to_ty(),
49 }
50 }
51 fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self {
52 match chalk {
53 chalk_ir::Ty::Apply(apply_ty) => {
54 match apply_ty.name {
55 TypeName::TypeKindId(TypeKindId::StructId(struct_id)) => {
56 let ctor = from_chalk(db, struct_id);
57 let parameters = from_chalk(db, apply_ty.parameters);
58 Ty::Apply(ApplicationTy { ctor, parameters })
59 }
60 // FIXME handle TypeKindId::Trait/Type here
61 TypeName::TypeKindId(_) => unimplemented!(),
62 TypeName::AssociatedType(_) => unimplemented!(),
63 TypeName::Placeholder(idx) => {
64 assert_eq!(idx.ui, UniverseIndex::ROOT);
65 Ty::Param { idx: idx.idx as u32, name: crate::Name::missing() }
66 }
67 }
68 }
69 chalk_ir::Ty::Projection(_) => unimplemented!(),
70 chalk_ir::Ty::UnselectedProjection(_) => unimplemented!(),
71 chalk_ir::Ty::ForAll(_) => unimplemented!(),
72 chalk_ir::Ty::BoundVar(idx) => Ty::Bound(idx as u32),
73 chalk_ir::Ty::InferenceVar(_iv) => panic!("unexpected chalk infer ty"),
74 }
75 }
76}
77
78impl ToChalk for Substs {
79 type Chalk = Vec<chalk_ir::Parameter>;
80
81 fn to_chalk(self, db: &impl HirDatabase) -> Vec<Parameter> {
82 self.iter().map(|ty| ty.clone().to_chalk(db).cast()).collect()
83 }
84
85 fn from_chalk(db: &impl HirDatabase, parameters: Vec<chalk_ir::Parameter>) -> Substs {
86 parameters
87 .into_iter()
88 .map(|p| match p {
89 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
90 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
91 })
92 .collect::<Vec<_>>()
93 .into()
94 }
95}
96
97impl ToChalk for TraitRef {
98 type Chalk = chalk_ir::TraitRef;
99
100 fn to_chalk(self: TraitRef, db: &impl HirDatabase) -> chalk_ir::TraitRef {
101 let trait_id = self.trait_.to_chalk(db);
102 let parameters = self.substs.to_chalk(db);
103 chalk_ir::TraitRef { trait_id, parameters }
104 }
105
106 fn from_chalk(db: &impl HirDatabase, trait_ref: chalk_ir::TraitRef) -> Self {
107 let trait_ = from_chalk(db, trait_ref.trait_id);
108 let substs = from_chalk(db, trait_ref.parameters);
109 TraitRef { trait_, substs }
110 }
111}
112
113impl ToChalk for Trait {
114 type Chalk = chalk_ir::TraitId;
115
116 fn to_chalk(self, _db: &impl HirDatabase) -> chalk_ir::TraitId {
117 self.id.into()
118 }
119
120 fn from_chalk(_db: &impl HirDatabase, trait_id: chalk_ir::TraitId) -> Trait {
121 Trait { id: trait_id.into() }
122 }
123}
124
125impl ToChalk for TypeCtor {
126 type Chalk = chalk_ir::StructId;
127
128 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::StructId {
129 db.intern_type_ctor(self).into()
130 }
131
132 fn from_chalk(db: &impl HirDatabase, struct_id: chalk_ir::StructId) -> TypeCtor {
133 db.lookup_intern_type_ctor(struct_id.into())
134 }
135}
136
137impl ToChalk for ImplBlock {
138 type Chalk = chalk_ir::ImplId;
139
140 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ImplId {
141 db.intern_impl_block(self).into()
142 }
143
144 fn from_chalk(db: &impl HirDatabase, impl_id: chalk_ir::ImplId) -> ImplBlock {
145 db.lookup_intern_impl_block(impl_id.into())
146 }
147}
148
149fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
150 chalk_ir::Binders {
151 value,
152 binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
153 }
154}
155
156impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
157where
158 DB: HirDatabase,
159{
160 fn associated_ty_data(&self, _ty: TypeId) -> Arc<AssociatedTyDatum> {
161 unimplemented!()
162 }
163 fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
164 debug!("trait_datum {:?}", trait_id);
165 let trait_: Trait = from_chalk(self.db, trait_id);
166 let generic_params = trait_.generic_params(self.db);
167 let bound_vars = Substs::bound_vars(&generic_params);
168 let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db);
169 let flags = chalk_rust_ir::TraitFlags {
170 // FIXME set these flags correctly
171 auto: false,
172 marker: false,
173 upstream: trait_.module(self.db).krate(self.db) != Some(self.krate),
174 fundamental: false,
175 };
176 let where_clauses = Vec::new(); // FIXME add where clauses
177 let associated_ty_ids = Vec::new(); // FIXME add associated tys
178 let trait_datum_bound =
179 chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids };
180 let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) };
181 Arc::new(trait_datum)
182 }
183 fn struct_datum(&self, struct_id: chalk_ir::StructId) -> Arc<StructDatum> {
184 debug!("struct_datum {:?}", struct_id);
185 let type_ctor = from_chalk(self.db, struct_id);
186 // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor
187 // FIXME extract this to a method on Ty
188 let (num_params, upstream) = match type_ctor {
189 TypeCtor::Bool
190 | TypeCtor::Char
191 | TypeCtor::Int(_)
192 | TypeCtor::Float(_)
193 | TypeCtor::Never
194 | TypeCtor::Str => (0, true),
195 TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => (1, true),
196 TypeCtor::FnPtr { num_args } => (num_args as usize + 1, true),
197 TypeCtor::Tuple { cardinality } => (cardinality as usize, true),
198 TypeCtor::FnDef(_) => unimplemented!(),
199 TypeCtor::Adt(adt) => {
200 let generic_params = adt.generic_params(self.db);
201 (
202 generic_params.count_params_including_parent(),
203 adt.krate(self.db) != Some(self.krate),
204 )
205 }
206 };
207 let flags = chalk_rust_ir::StructFlags {
208 upstream,
209 // FIXME set fundamental flag correctly
210 fundamental: false,
211 };
212 let where_clauses = Vec::new(); // FIXME add where clauses
213 let self_ty = chalk_ir::ApplicationTy {
214 name: TypeName::TypeKindId(type_ctor.to_chalk(self.db).into()),
215 parameters: (0..num_params).map(|i| chalk_ir::Ty::BoundVar(i).cast()).collect(),
216 };
217 let struct_datum_bound = chalk_rust_ir::StructDatumBound {
218 self_ty,
219 fields: Vec::new(), // FIXME add fields (only relevant for auto traits)
220 where_clauses,
221 flags,
222 };
223 let struct_datum = StructDatum { binders: make_binders(struct_datum_bound, num_params) };
224 Arc::new(struct_datum)
225 }
226 fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> {
227 debug!("impl_datum {:?}", impl_id);
228 let impl_block: ImplBlock = from_chalk(self.db, impl_id);
229 let generic_params = impl_block.generic_params(self.db);
230 let bound_vars = Substs::bound_vars(&generic_params);
231 let trait_ref = impl_block
232 .target_trait_ref(self.db)
233 .expect("FIXME handle unresolved impl block trait ref")
234 .subst(&bound_vars);
235 let impl_type = if impl_block.module().krate(self.db) == Some(self.krate) {
236 chalk_rust_ir::ImplType::Local
237 } else {
238 chalk_rust_ir::ImplType::External
239 };
240 let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
241 // FIXME handle negative impls (impl !Sync for Foo)
242 trait_ref: chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref.to_chalk(self.db)),
243 where_clauses: Vec::new(), // FIXME add where clauses
244 associated_ty_values: Vec::new(), // FIXME add associated type values
245 impl_type,
246 };
247 let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) };
248 Arc::new(impl_datum)
249 }
250 fn impls_for_trait(&self, trait_id: chalk_ir::TraitId) -> Vec<ImplId> {
251 debug!("impls_for_trait {:?}", trait_id);
252 let trait_ = from_chalk(self.db, trait_id);
253 self.db
254 .impls_for_trait(self.krate, trait_)
255 .iter()
256 // FIXME temporary hack -- as long as we're not lowering where clauses
257 // correctly, ignore impls with them completely so as to not treat
258 // impl<T> Trait for T where T: ... as a blanket impl on all types
259 .filter(|impl_block| impl_block.generic_params(self.db).where_predicates.is_empty())
260 .map(|impl_block| impl_block.to_chalk(self.db))
261 .collect()
262 }
263 fn impl_provided_for(
264 &self,
265 auto_trait_id: chalk_ir::TraitId,
266 struct_id: chalk_ir::StructId,
267 ) -> bool {
268 debug!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id);
269 false // FIXME
270 }
271 fn type_name(&self, _id: TypeKindId) -> Identifier {
272 unimplemented!()
273 }
274 fn split_projection<'p>(
275 &self,
276 projection: &'p ProjectionTy,
277 ) -> (Arc<AssociatedTyDatum>, &'p [Parameter], &'p [Parameter]) {
278 debug!("split_projection {:?}", projection);
279 unimplemented!()
280 }
281 fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause> {
282 debug!("custom_clauses");
283 vec![]
284 }
285 fn all_structs(&self) -> Vec<chalk_ir::StructId> {
286 debug!("all_structs");
287 // FIXME
288 vec![]
289 }
290}
291
292fn id_from_chalk<T: InternKey>(chalk_id: chalk_ir::RawId) -> T {
293 T::from_intern_id(InternId::from(chalk_id.index))
294}
295fn id_to_chalk<T: InternKey>(salsa_id: T) -> chalk_ir::RawId {
296 chalk_ir::RawId { index: salsa_id.as_intern_id().as_u32() }
297}
298
299impl From<chalk_ir::TraitId> for crate::ids::TraitId {
300 fn from(trait_id: chalk_ir::TraitId) -> Self {
301 id_from_chalk(trait_id.0)
302 }
303}
304
305impl From<crate::ids::TraitId> for chalk_ir::TraitId {
306 fn from(trait_id: crate::ids::TraitId) -> Self {
307 chalk_ir::TraitId(id_to_chalk(trait_id))
308 }
309}
310
311impl From<chalk_ir::StructId> for crate::ids::TypeCtorId {
312 fn from(struct_id: chalk_ir::StructId) -> Self {
313 id_from_chalk(struct_id.0)
314 }
315}
316
317impl From<crate::ids::TypeCtorId> for chalk_ir::StructId {
318 fn from(type_ctor_id: crate::ids::TypeCtorId) -> Self {
319 chalk_ir::StructId(id_to_chalk(type_ctor_id))
320 }
321}
322
323impl From<chalk_ir::ImplId> for crate::ids::GlobalImplId {
324 fn from(impl_id: chalk_ir::ImplId) -> Self {
325 id_from_chalk(impl_id.0)
326 }
327}
328
329impl From<crate::ids::GlobalImplId> for chalk_ir::ImplId {
330 fn from(impl_id: crate::ids::GlobalImplId) -> Self {
331 chalk_ir::ImplId(id_to_chalk(impl_id))
332 }
333}
diff --git a/crates/ra_ide_api/src/completion/complete_dot.rs b/crates/ra_ide_api/src/completion/complete_dot.rs
index e34ddf24a..2e8084699 100644
--- a/crates/ra_ide_api/src/completion/complete_dot.rs
+++ b/crates/ra_ide_api/src/completion/complete_dot.rs
@@ -24,7 +24,7 @@ fn complete_fields(acc: &mut Completions, ctx: &CompletionContext, receiver: Ty)
24 } 24 }
25 } 25 }
26 // FIXME unions 26 // FIXME unions
27 TypeCtor::Tuple => { 27 TypeCtor::Tuple { .. } => {
28 for (i, ty) in a_ty.parameters.iter().enumerate() { 28 for (i, ty) in a_ty.parameters.iter().enumerate() {
29 acc.add_pos_field(ctx, i, ty); 29 acc.add_pos_field(ctx, i, ty);
30 } 30 }