cetus - Cetus is a simple wallpaper setting tool written in Go

summary refs log tree commit diff stats

Branch	Commit message	Author	Age
master	Update LICENSE Year	Andinus	4 years

Tag	Download	Author	Age
v0.6.8	cetus-0.6.8.tar.gz	Andinus	5 years
v0.6.7	cetus-0.6.7.tar.gz	Andinus	5 years
v0.6.6	cetus-0.6.6.tar.gz	Andinus	5 years
v0.6.5	cetus-0.6.5.tar.gz	Andinus	5 years
v0.6.4	cetus-0.6.4.tar.gz	Andinus	5 years
v0.6.3	cetus-0.6.3.tar.gz	Andinus	5 years
v0.6.2	cetus-0.6.2.tar.gz	Andinus	5 years
v0.6.1	cetus-0.6.1.tar.gz	Andinus	5 years
v0.6.0	cetus-0.6.0.tar.gz	Andinus	5 years
v0.5.2	cetus-0.5.2.tar.gz	Andinus	5 years
[...]

Age	Commit message	Author	Files	Lines
2020-03-14	Bump version to v0.4.1 v0.4.1	Andinus	1	-1/+3
2020-03-14	Add version flag	Andinus	3	-12/+43
2020-03-14	Build linux image with gitlab-ci	Andinus	1	-0/+2
2020-03-14	Fix gitlab-cli error	Andinus	1	-3/+5
2020-03-14	Beautify readme	Andinus	1	-2/+2
2020-03-14	Add gitlab-ci build files	Andinus	1	-0/+21
2020-03-14	Add project related links to readme	Andinus	1	-1/+5
2020-03-14	Add css styles in heading	Andinus	1	-0/+2
2020-03-14	Add cetus-nasa program v0.4.0	Andinus	3	-0/+245
2020-03-14	Split project into multiple programs	Andinus	3	-173/+7
[...]

Clone
https://git.tilde.institute/andinus/cetus

committer Andreas Rumpf <rumpf_a@web.de> 2018-11-07 18:36:52 +0100 make Nim take roughly 100MB less RAM for bootstrapping via a new compiler switch -d:leanCompiler; useful for the Raberry PI' href='/ahoang/Nim/commit/compiler/sigmatch.nim?h=devel&id=cb4d81065967e9b40b1e488fc66f1d926f19f536'>cb4d81065 ^

aa88e150d ^

fdde4d3a9 ^

3e9dcc8be ^

cac259cdf ^

e25474154 ^

e5bd3b5b9 ^

a74ad869e ^

326b7dc55 ^

6408646b0 ^

e9a3ffbc3 ^

9d77f6103 ^

74a80988d ^

729e048a3 ^

299cefdc9 ^

a1f677980 ^

63ac32e6d ^

fdde4d3a9 ^

8f3d5a25a ^

fdde4d3a9 ^

740527813 ^

1afdefcbe ^

63ac32e6d ^

05cbbac4e ^

38ab30d15 ^

4b7655fd1 ^

13cdad881 ^

b0b716fca ^

29c075299 ^

8cd5f1f8f ^

6408646b0 ^

4adc31ee3 ^

74a80988d ^

326b7dc55 ^

6408646b0 ^

e9a3ffbc3 ^

a802d7245 ^

fdde4d3a9 ^

4fbba0a65 ^

6da8c7857 ^

a158053ae ^

4fbba0a65 ^

4741e8f9a ^

cac259cdf ^

d4c91bbd8 ^

cac259cdf ^

84bc04ba3 ^

c7158af75 ^

05cbbac4e ^

299cefdc9 ^

e25474154 ^

e25474154 ^

38ab30d15 ^

e2f8d9129 ^

6c2050912 ^

299cefdc9 ^

6c2050912 ^

09f122f68 ^

95f8ed038 ^

57bc8d73b ^

09f122f68 ^

740527813 ^

299cefdc9 ^

4adc31ee3 ^

299cefdc9 ^

6c2050912 ^

8f3d5a25a ^

3a9500f7b ^

8f3d5a25a ^

dae545094 ^

6408646b0 ^

1afdefcbe ^

6c2050912 ^

438703f59 ^

6c2050912 ^

e2594f44b ^

84bc04ba3 ^

6c2050912 ^

299cefdc9 ^

f760bc243 ^

4b7655fd1 ^

cac259cdf ^

299cefdc9 ^

e25474154 ^

d13bcf657 ^

fd1687556 ^

d13bcf657 ^

2c91e999e ^

d13bcf657 ^

0ead36dae ^

201589535 ^

ea409fb15 ^

d13bcf657 ^

13701c095 ^

fd1687556 ^

13701c095 ^

fd1687556 ^

13701c095 ^

d13bcf657 ^

d13bcf657 ^

2c91e999e ^

560cfd48f ^

13701c095 ^

70ea45cdb ^

bda8a6c1b ^

fd1687556 ^

d13bcf657 ^

9c6fe59b5 ^

fd1687556 ^

b92fd3028 ^

201589535 ^

6fbde1f4f ^

1efb5174f ^

e1828733f ^

2c91e999e ^

e40b66789 ^

d13bcf657 ^

1efb5174f ^

d13bcf657 ^

1efb5174f ^

70ea45cdb ^

1efb5174f ^

0a3efccb5 ^

1efb5174f ^

70ea45cdb ^

1efb5174f ^

d13bcf657 ^

13701c095 ^

feef109e6 ^

13701c095 ^

5131b3cea ^

e25474154 ^

5131b3cea ^

e25474154 ^

5131b3cea ^

e25474154 ^

5131b3cea ^

e25474154 ^

5131b3cea ^

e25474154 ^

d1d5fc825 ^

e2f8d9129 ^

d13bcf657 ^

636e74fe3 ^

e25474154 ^

7a4894271 ^

ed56b8c17 ^

7a4894271 ^

70ea45cdb ^

ed56b8c17 ^

7a4894271 ^

6ff66bfd5 ^

ed56b8c17 ^

7a4894271 ^

ed56b8c17 ^

7a4894271 ^

3e79e9f98 ^

f18b3af9d ^

ed56b8c17 ^

cac259cdf ^

dbc5048a9 ^

6ff66bfd5 ^

1d44fee39 ^

ed56b8c17 ^

5b0d8246f ^

4483cefa0 ^

ed56b8c17 ^

6ff66bfd5 ^

7a4894271 ^

e25474154 ^

3e79e9f98 ^

90e882d55 ^

a802d7245 ^

c7de1a252 ^

e25474154 ^

121d4e0fc ^

e25474154 ^

b0b716fca ^

abb2c2104 ^

de3b7cd41 ^

e25474154 ^

cac259cdf ^

e2f8d9129 ^

e424e13bd ^

c95f6f117 ^

79aaf213d ^

84bc04ba3 ^

c7de1a252 ^

79aaf213d ^

e25474154 ^

cac259cdf ^

e25474154 ^

2900ceae3 ^

4fbba0a65 ^

cac259cdf ^

4fbba0a65 ^

a4e2b0c15 ^

2900ceae3 ^

4fbba0a65 ^

20774ad43 ^

e2d38a57e ^

71df1b060 ^

20774ad43 ^

4fbba0a65 ^

71df1b060 ^

a4e2b0c15 ^

4fbba0a65 ^

e25474154 ^

2900ceae3 ^

286f89528 ^

2900ceae3 ^

7056ceda6 ^

e25474154 ^

7056ceda6 ^

4fbba0a65 ^

7056ceda6 ^

4fbba0a65 ^

cf689f747 ^

74c24f3e6 ^

cf689f747 ^

e25474154 ^

cac259cdf ^

568c95406 ^

2ac7f5238 ^

568c95406 ^

90e882d55 ^

568c95406 ^

3a13706d7 ^

7bf98411b ^

92e1a21b2 ^

e2f8d9129 ^

3a13706d7 ^

cac259cdf ^

92e1a21b2 ^

3a13706d7 ^

e2f8d9129 ^

568c95406 ^

e2f8d9129 ^

3a13706d7 ^

e25474154 ^

d779a9b72 ^

09f122f68 ^

764668d09 ^

d779a9b72 ^

764668d09 ^

d779a9b72 ^

09f122f68 ^

d779a9b72 ^

ea409fb15 ^

d779a9b72 ^

09f122f68 ^

764668d09 ^

90e882d55 ^

764668d09 ^

d779a9b72 ^

09f122f68 ^

764668d09 ^

568c95406 ^

09f122f68 ^

568c95406 ^

764668d09 ^

d779a9b72 ^

568c95406 ^

764668d09 ^

cac259cdf ^

e25474154 ^

cac259cdf ^

5d75ce2f2 ^

e25474154 ^

1efb5174f ^

674c05f42 ^

e25474154 ^

5d75ce2f2 ^

cac259cdf ^

f18b3af9d ^

e2f8d9129 ^

b2ad7b30d ^

e25474154 ^

674c05f42 ^

f18b3af9d ^

e25474154 ^

84bc04ba3 ^

674c05f42 ^

66a255652 ^

abb738146 ^

4741e8f9a ^

ccd2934e4 ^

dae545094 ^

a158053ae ^

201589535 ^

a158053ae ^

74f490143 ^

6da8c7857 ^

74f490143 ^

a158053ae ^

6da8c7857 ^

a158053ae ^

74f490143 ^

a158053ae ^

74f490143 ^

cac259cdf ^

a158053ae ^

9b98add6c ^

a158053ae ^

6da8c7857 ^

a158053ae ^

1efb5174f ^

74f490143 ^

1efb5174f ^

a158053ae ^

6da8c7857 ^

74f490143 ^

849208d77 ^

74f490143 ^

a158053ae ^

cac259cdf ^

1efb5174f ^

cac259cdf ^

a158053ae ^

849208d77 ^

2633e3fb2 ^

849208d77 ^

cac259cdf ^

74f490143 ^

70ea45cdb ^

74f490143 ^

cac259cdf ^

849208d77 ^

74f490143 ^

849208d77 ^

ffcbe19cd ^

849208d77 ^

ffcbe19cd ^

74f490143 ^

849208d77 ^

ffcbe19cd ^

61db30727 ^

328e7a100 ^

3b69a8d27 ^

ffcbe19cd ^

dd9ad9e49 ^

b731e6ef1 ^

2633e3fb2 ^

b731e6ef1 ^

6da8c7857 ^

2633e3fb2 ^

ffcbe19cd ^

9f38ff0c6 ^

443a46b40 ^

1efb5174f ^

249dd7027 ^

73c6efdf6 ^

849208d77 ^

3cb3813ee ^

f29225fc6 ^

77f33db3e ^

a65e9c0e2 ^

77f33db3e ^

a65e9c0e2 ^

77f33db3e ^

a95316f78 ^

a65e9c0e2 ^

a95316f78 ^

a65e9c0e2 ^

f29225fc6 ^

101f23f3a ^

f29225fc6 ^

77f33db3e ^

f29225fc6 ^

3cb3813ee ^

90e82f8ec ^

74a80988d ^

90e82f8ec ^

a74ad869e ^

cd0256136 ^

84bc04ba3 ^

cd0256136 ^

a6a18be08 ^

a6a18be08 ^

cd0256136 ^

e686ca252 ^

cd0256136 ^

a6a18be08 ^

66e0f0e19 ^

a6a18be08 ^

70ea45cdb ^

a6a18be08 ^

05cbbac4e ^

90e82f8ec ^

05cbbac4e ^

39ebe2175 ^

328e7a100 ^

05cbbac4e ^

cbf66e99a ^

76c663f69 ^

cbf66e99a ^

675c629fe ^

e9a3ffbc3 ^

a6a18be08 ^

66e0f0e19 ^

74a80988d ^

669a56449 ^

74a80988d ^

fe48dd1cb ^

74a80988d ^

6408646b0 ^

a74ad869e ^

e9a3ffbc3 ^

74a80988d ^

669a56449 ^

74a80988d ^

74a80988d ^

669a56449 ^

dae545094 ^

fe48dd1cb ^

e9a3ffbc3 ^

74a80988d ^

cbf66e99a ^

74a80988d ^

669a56449 ^

4adc31ee3 ^

675c629fe ^

6408646b0 ^

e9a3ffbc3 ^

33f4e6975 ^

66e0f0e19 ^

c605d5757 ^

66e0f0e19 ^

33f4e6975 ^

a74ad869e ^

33f4e6975 ^

a6a18be08 ^

84bc04ba3 ^

8a0509b3b ^

40ec7be45 ^

8a0509b3b ^

40ec7be45 ^

8a0509b3b ^

84bc04ba3 ^

8a0509b3b ^

84bc04ba3 ^

8a0509b3b ^

0f2c4be12 ^

da36a847a ^

0f2c4be12 ^

da36a847a ^

dfbafff2e ^

0f2c4be12 ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

0f2c4be12 ^

dfbafff2e ^

0f2c4be12 ^

dfbafff2e ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

4d5cce988 ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

e9a3ffbc3 ^

0f2c4be12 ^

e9a3ffbc3 ^

0f2c4be12 ^

dfbafff2e ^

cd0256136 ^

2da4a4fbe ^

dfbafff2e ^

e9a3ffbc3 ^

dfbafff2e ^

0f2c4be12 ^

84bc04ba3 ^

0f2c4be12 ^

84bc04ba3 ^

0f2c4be12 ^

d57881596 ^

0f2c4be12 ^

dfbafff2e ^

0f2c4be12 ^

a4e2b0c15 ^

0f2c4be12 ^

a4e2b0c15 ^

0f2c4be12 ^

a4e2b0c15 ^

0f2c4be12 ^

a4e2b0c15 ^

0f2c4be12 ^

f348671ba ^

ea409fb15 ^

f348671ba ^

a802d7245 ^

ea409fb15 ^

a802d7245 ^

ea409fb15 ^

a802d7245 ^

7a95c961a ^

a802d7245 ^

3dab0877d ^

bd1dfa4b3 ^

ea409fb15 ^

90e882d55 ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

1d02f2ea5 ^

e25474154 ^

cac259cdf ^

b92fd3028 ^

09f122f68 ^

3f71b7f1f ^

66a255652 ^

8cd5f1f8f ^

cd0256136 ^

8cd5f1f8f ^

644d645ea ^

96de224a6 ^

8cd5f1f8f ^

e879da579 ^

8cd5f1f8f ^

8cd5f1f8f ^

90e882d55 ^

8cd5f1f8f ^

84bc04ba3 ^

8cd5f1f8f ^

675c629fe ^

8cd5f1f8f ^

a802d7245 ^

2ac7f5238 ^

8a0509b3b ^

cac259cdf ^

201589535 ^

cd0256136 ^

2ac7f5238 ^

c95f6f117 ^

72291875b ^

e2f8d9129 ^

5d75ce2f2 ^

eab1d0cc0 ^

de3b7cd41 ^

1efb5174f ^

09f122f68 ^

de3b7cd41 ^

8e0941576 ^

60b187513 ^

8e0941576 ^

de3b7cd41 ^

c981284dd ^

de3b7cd41 ^

1efb5174f ^

de3b7cd41 ^

a802d7245 ^

1efb5174f ^

c981284dd ^

de3b7cd41 ^

c981284dd ^

de3b7cd41 ^

a802d7245 ^

1efb5174f ^

c981284dd ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

e12946691 ^

9cc25f8b7 ^

9e4e1949e ^

16eb4b1fe ^

9e4e1949e ^

16eb4b1fe ^

73c6efdf6 ^

de3b7cd41 ^

e25474154 ^

1d02f2ea5 ^

90db9171a ^

1d02f2ea5 ^

b2ad7b30d ^

e25474154 ^

95faae2c0 ^

70b5efa98 ^

e2f8d9129 ^

95faae2c0 ^

3cb3813ee ^

da36a847a ^

3cb3813ee ^

d912d1837 ^

20774ad43 ^

b2ad7b30d ^

201589535 ^

a802d7245 ^

f348671ba ^

e6c5622aa ^

e25474154 ^

e6c5622aa ^

b2814df5c ^

76c663f69 ^

b2814df5c ^

09f122f68 ^

b2814df5c ^

f4e73344d ^

3979e83a5 ^

3dab0877d ^

51d81c4e2 ^

3dab0877d ^

51d81c4e2 ^

3dab0877d ^

f4e73344d ^

e9a3ffbc3 ^

0f2c4be12 ^

cd0256136 ^

0f2c4be12 ^

d57881596 ^

a4e2b0c15 ^

d57881596 ^

73c6efdf6 ^

0ead36dae ^

0171566c9 ^

cabbcd411 ^

987b52207 ^

b92fd3028 ^

f4e73344d ^

b731e6ef1 ^

0171566c9 ^

e2f8d9129 ^

e25474154 ^

e6c5622aa ^

cac259cdf ^

f4e73344d ^

cac259cdf ^

f4e73344d ^

f3b8a3cbb ^

87c8d586b ^

cabbcd411 ^

87c8d586b ^

73c6efdf6 ^

ccd2934e4 ^

b731e6ef1 ^

ccd2934e4 ^

e25474154 ^

ccd2934e4 ^

f4e73344d ^

d4c91bbd8 ^

dae545094 ^

73c6efdf6 ^

296ef0795 ^

4741e8f9a ^

d912d1837 ^

de3b7cd41 ^

ca3a4ce67 ^

55a5dcf8a ^

c7158af75 ^

ea409fb15 ^

e25474154 ^

cac259cdf ^

5d75ce2f2 ^

e2f8d9129 ^

90db9171a ^

8f3d5a25a ^

e2f8d9129 ^

3a13706d7 ^

e2f8d9129 ^

de1ede77f ^

e97d640ce ^

dd6598679 ^

e97d640ce ^

e2e4df170 ^

ea409fb15 ^

4b7655fd1 ^

cac259cdf ^

1efb5174f ^

e25474154 ^

cac259cdf ^

e2f8d9129 ^

cac259cdf ^

e25474154 ^

d0f013477 ^

ea409fb15 ^

d0f013477 ^

4196757de ^

a802d7245 ^

f348671ba ^

682543083 ^

d4c91bbd8 ^

d0f013477 ^

73c6efdf6 ^

ccd2934e4 ^

ea409fb15 ^

e2f8d9129 ^

d4c91bbd8 ^

ea409fb15 ^

d4c91bbd8 ^

ea409fb15 ^

e25474154 ^

d4c91bbd8 ^

ccd2934e4 ^

8d99753d6 ^

d0f013477 ^

73c6efdf6 ^

cac259cdf ^

e25474154 ^

cac259cdf ^

d4c91bbd8 ^

dae545094 ^

73c6efdf6 ^

ccd2934e4 ^

e25474154 ^

b731e6ef1 ^

d4c91bbd8 ^

ccd2934e4 ^

0da91aa74 ^

ccd2934e4 ^

4196757de ^

3308d2658 ^

0ead36dae ^

a4e2b0c15 ^

3308d2658 ^

73c6efdf6 ^

de3b7cd41 ^

b47d9b7b9 ^

de3b7cd41 ^

201589535 ^

e97d640ce ^

de3b7cd41 ^

e9a3ffbc3 ^

ae901b327 ^

e9a3ffbc3 ^

a802d7245 ^

57bc8d73b ^

1f7f0908e ^

90e882d55 ^

e9a3ffbc3 ^

90e882d55 ^

a802d7245 ^

7a95c961a ^

a802d7245 ^

7a95c961a ^

a802d7245 ^

0aede22e8 ^

90e882d55 ^

a802d7245 ^

7a95c961a ^

a802d7245 ^

e9a3ffbc3 ^

a802d7245 ^

e9a3ffbc3 ^

e9a3ffbc3 ^

3e52bb653 ^

e9a3ffbc3 ^

3e52bb653 ^

e4aa140d2 ^

e9a3ffbc3 ^

57bc8d73b ^

e9a3ffbc3 ^

ae901b327 ^

30ccadfe4 ^

e9a3ffbc3 ^

de3b7cd41 ^

8e0941576 ^

88714e77d ^

09f122f68 ^

57b8664a0 ^

09f122f68 ^

de3b7cd41 ^

c95f6f117 ^

4ef96a743 ^

5f515410a ^

e9a3ffbc3 ^

d57881596 ^

5f515410a ^

e9a3ffbc3 ^

90e882d55 ^

e9a3ffbc3 ^

764668d09 ^

c95f6f117 ^

fd62116f6 ^

73c6efdf6 ^

4a35d2b57 ^

c94647aec ^

0774af169 ^

90e882d55 ^

5131b3cea ^

508e8bd68 ^

3a13706d7 ^

d0ec83eaa ^

3a13706d7 ^

d0ec83eaa ^

508e8bd68 ^

5131b3cea ^

508e8bd68 ^

e25474154 ^

f18b3af9d ^

57b8664a0 ^

508e8bd68 ^

84bc04ba3 ^

508e8bd68 ^

95f8ed038 ^

cac259cdf ^

568c95406 ^

c94647aec ^

2f9a698e8 ^

568c95406 ^

d0ec83eaa ^

de3b7cd41 ^

8e0941576 ^

b34bd3b16 ^

8e0941576 ^

1efb5174f ^

4d5c0027e ^

1efb5174f ^

de3b7cd41 ^

8e0941576 ^

1efb5174f ^

9c00f6dec ^

8e0941576 ^

9c00f6dec ^

1efb5174f ^

9c00f6dec ^

1efb5174f ^

4d5c0027e ^

1efb5174f ^

9c00f6dec ^

de3b7cd41 ^

8e0941576 ^

cac259cdf ^

8e0941576 ^

de3b7cd41 ^

8e0941576 ^

540914212 ^

de3b7cd41 ^

09f122f68 ^

de3b7cd41 ^

1d02f2ea5 ^

8e0941576 ^

1d02f2ea5 ^

a20a8e6ad ^

8fb04b320 ^

a20a8e6ad ^

09f122f68 ^

1d02f2ea5 ^

1d02f2ea5 ^

0b0a3e5f2 ^

bf4ce87e5 ^

a6006e56a ^

90e82f8ec ^

bf4ce87e5 ^

eab1d0cc0 ^

a27eb5153 ^

8e0941576 ^

e97d640ce ^

0378f9980 ^

e97d640ce ^

a27eb5153 ^

e97d640ce ^

09f122f68 ^

e97d640ce ^

bf4ce87e5 ^

3f71b7f1f ^

e2f8d9129 ^

251c44ff0 ^

8ba062d95 ^

8682ed9bd ^

cac259cdf ^

ca3a4ce67 ^

49b0440c4 ^

d912d1837 ^

ca3a4ce67 ^

dae545094 ^

ca3a4ce67 ^

13cdad881 ^

03172bef6 ^

13cdad881 ^

03172bef6 ^

13cdad881 ^

1efb5174f ^

9d8b4d602 ^

ca3a4ce67 ^

90e882d55 ^

d912d1837 ^

9c00f6dec ^

c7de1a252 ^

a1c217a2d ^

c7de1a252 ^

a1c217a2d ^

09f122f68 ^

9c00f6dec ^

01ccb52a0 ^

1d02f2ea5 ^

251c44ff0 ^

37b199d34 ^

251c44ff0 ^

c7de1a252 ^

37b199d34 ^

09f122f68 ^

1efb5174f ^

251c44ff0 ^

e25474154 ^

251c44ff0 ^

e25474154 ^

251c44ff0 ^

3dab0877d ^

edab4aaad ^

13a18663d ^

fb27357b6 ^

09f122f68 ^

8443e3f6b ^

fb27357b6 ^

367d23235 ^

13a18663d ^

442dc3092 ^

edab4aaad ^

442dc3092 ^

8cd5f1f8f ^

8cd5f1f8f ^

675c629fe ^

8cd5f1f8f ^

22dc76a36 ^

289c975d8 ^

4d3846e26 ^

5bcf8bcb5 ^

c1f1f8419 ^

22dc76a36 ^

c1f1f8419 ^

cac259cdf ^

c1f1f8419 ^

09f122f68 ^

22dc76a36 ^

4d3846e26 ^

cac259cdf ^

b92fd3028 ^

c735b75f6 ^

09f122f68 ^

3a5cf3d63 ^

cac259cdf ^

c7158af75 ^

ac271e76b ^

247af96b0 ^

da36a847a ^

d508384d3 ^

da36a847a ^

d508384d3 ^

da36a847a ^

d508384d3 ^

84bc04ba3 ^

ac271e76b ^

cac259cdf ^

e55f5d1fd ^

ac271e76b ^

84bc04ba3 ^

cac259cdf ^

57bc8d73b ^

cac259cdf ^

299cefdc9 ^

afddae5aa ^

299cefdc9 ^

e25474154 ^

b21b72dc1 ^

e25474154 ^

b21b72dc1 ^

e25474154 ^

674c05f42 ^

84bc04ba3 ^

674c05f42 ^

cac259cdf ^

e25474154 ^

c7158af75 ^

05cbbac4e ^

c7158af75 ^

84bc04ba3 ^

2a7fc84c8 ^

e25474154 ^

cac259cdf ^

e25474154 ^

f18b3af9d ^

e25474154 ^

38ab30d15 ^

5c5388c0a ^

0da91aa74 ^

16a70c84a ^

aa1cdebdc ^

16a70c84a ^

cac259cdf ^

38ab30d15 ^

c50a04adc ^

84bc04ba3 ^

e25474154 ^

38ab30d15 ^

e25474154 ^

16a70c84a ^

5c5388c0a ^

16a70c84a ^

5c5388c0a ^

c5c4da4f3 ^

e25474154 ^

c02320e23 ^

c5c4da4f3 ^

a22c1f444 ^

e25474154 ^

cac259cdf ^

de338526e ^

27f174379 ^

121519301 ^

98859a724 ^

121519301 ^

be4748eb5 ^

121519301 ^

0171566c9 ^

121519301 ^

0171566c9 ^

22dc76a36 ^

019faf00b ^

6da8c7857 ^

019faf00b ^

a3f19c87f ^

8cd5f1f8f ^

6378fbd66 ^

4cea15d27 ^

edab4aaad ^

4cea15d27 ^

8cd5f1f8f ^

72291875b ^

33f4e6975 ^

edab4aaad ^

cac259cdf ^

ea409fb15 ^

37b199d34 ^

ea409fb15 ^

8cd5f1f8f ^

37b199d34 ^

8cd5f1f8f ^

bf612a7f1 ^

c605d5757 ^

bf612a7f1 ^

f0953db3b ^

7dcf6ff50 ^

b8d2f79ef ^

ba61e7e3a ^

815724db7 ^

e98e21442 ^

8cd5f1f8f ^

815724db7 ^

992fd3848 ^

b92fd3028 ^

992fd3848 ^

121b9e26f ^

992fd3848 ^

085b339b8 ^

6da8c7857 ^

d68181246 ^

6da8c7857 ^

1a61c4d46 ^

6da8c7857 ^

e25474154 ^

edab4aaad ^

e25474154 ^

cac259cdf ^

4fbba0a65 ^

1786e3099 ^

4fbba0a65 ^

e25474154 ^

cac259cdf ^

e25474154 ^

179d82c55 ^

4fbba0a65 ^

1efb5174f ^

a158053ae ^

1a61c4d46 ^

9dd753f21 ^

47658cd42 ^

9dd753f21 ^

a158053ae ^

e6b0b7ecc ^

a158053ae ^

1efb5174f ^

3a5cf3d63 ^

e25474154 ^

cac259cdf ^

729761390 ^

e98e21442 ^

26eae7d00 ^

cac259cdf ^

b7f11b8b0 ^

cac259cdf ^

6da8c7857 ^

4fbba0a65 ^

cac259cdf ^

e25474154 ^

cac259cdf ^

90e882d55 ^

26eae7d00 ^

c7158af75 ^

d4573f176 ^

05cbbac4e ^

79aaf213d ^

05cbbac4e ^

cac259cdf ^

a3f19c87f ^

2a7fc84c8 ^

a3f19c87f ^

cac259cdf ^

0171566c9 ^

e25474154 ^

0171566c9 ^

ee89ba6bd ^

0171566c9 ^

e2f8d9129 ^

0171566c9 ^

a55817f9a ^

0171566c9 ^

a55817f9a ^

0171566c9 ^

a55817f9a ^

80107b360 ^

ee89ba6bd ^

80107b360 ^

ee89ba6bd ^

80107b360 ^

0171566c9 ^

d4573f176 ^

bec06a064 ^

afddae5aa ^

a22c1f444 ^

3c9e3a6a7 ^

afddae5aa ^

cac259cdf ^

e25474154 ^

299cefdc9 ^

7bf98411b ^

299cefdc9 ^

e25474154 ^

e7fe8edab ^

bdcb72959 ^

e25474154 ^

1efb5174f ^

1be0022e7 ^

1efb5174f ^

019faf00b ^

1efb5174f ^

1efb5174f ^

cac259cdf ^

019faf00b ^

e25474154 ^

cac259cdf ^

e25474154 ^

cac259cdf ^

019faf00b ^

74f490143 ^

e25474154 ^

74f490143 ^

e25474154 ^

bdcb72959 ^

cac259cdf ^

e25474154 ^

cac259cdf ^

84bc04ba3 ^

ab5b8f539 ^

b92fd3028 ^

ab5b8f539 ^

b92fd3028 ^

ab5b8f539 ^

e25474154 ^

84bc04ba3 ^

6e8ed8c6f ^

afddae5aa ^

e2f8d9129 ^

df4d5b77a ^

e25474154 ^

cac259cdf ^

790652729 ^

e25474154 ^

790652729 ^

e25474154 ^

eebee0eff ^

b92fd3028 ^

eebee0eff ^

49471440e ^

6f7b891bd ^

b92fd3028 ^

49471440e ^

085b339b8 ^

eebee0eff ^

0440aea69 ^

eebee0eff ^

3051c52f5 ^

eebee0eff ^

0440aea69 ^

eebee0eff ^

40ec7be45 ^

eebee0eff ^

40ec7be45 ^

eebee0eff ^

865a43050 ^

b78029b5a ^

865a43050 ^

201589535 ^

865a43050 ^

b78029b5a ^

865a43050 ^

b78029b5a ^

865a43050 ^

39ebe2175 ^

b92fd3028 ^

cabbcd411 ^

a22c1f444 ^

cac259cdf ^

60b187513 ^

a1f677980 ^

4a6d699bc ^

d4bca58b7 ^

4a6d699bc ^

c50a04adc ^

4a6d699bc ^

c50a04adc ^

d4bca58b7 ^

995727ffd ^

d4bca58b7 ^

f760bc243 ^

c50a04adc ^

f760bc243 ^

70cf34cbd ^

e25474154 ^

f760bc243 ^

e25474154 ^

e25474154 ^

cabbcd411 ^

f760bc243 ^

e5bd3b5b9 ^

e678a4285 ^

be22071b2 ^

b74faf354 ^

aa7ad8897 ^

b74faf354 ^

bbf7e18e5 ^

b74faf354 ^

cabbcd411 ^

e25474154 ^

40ec7be45 ^

cac259cdf ^

84bc04ba3 ^

e25474154 ^

0694c9080 ^

cac259cdf ^

e25474154 ^

cac259cdf ^

e25474154 ^

0694c9080 ^

cac259cdf ^

00c486120 ^

e25474154 ^

cac259cdf ^

e25474154 ^

c6671776a ^

eebee0eff ^

c50a04adc ^

b159fc3b3 ^

eebee0eff ^

e25474154 ^

0694c9080 ^

a1f677980 ^

cac259cdf ^

c4eddb3fd ^

865a43050 ^

e25474154 ^

c4eddb3fd ^

e25474154 ^

c4eddb3fd ^

eebee0eff ^

e25474154 ^

eebee0eff ^

e25474154 ^

438703f59 ^

e25474154 ^

eebee0eff ^

5b0d8246f ^

84bc04ba3 ^

eebee0eff ^

e25474154 ^

0d804c205 ^

cabbcd411 ^

e25474154 ^

c6671776a ^

be22071b2 ^

eebee0eff ^

c50a04adc ^

e5bd3b5b9 ^

c4eddb3fd ^

e25474154 ^

865a43050 ^

7ee184713 ^

eebee0eff ^

e25474154 ^

eebee0eff ^

e25474154 ^

eebee0eff ^

cac259cdf ^

84bc04ba3 ^

674c05f42 ^

e25474154 ^

c4eddb3fd ^

00c486120 ^

e25474154 ^

cac259cdf ^

875132bf4 ^

c4eddb3fd ^

650b20dc5 ^

875132bf4 ^

26eae7d00 ^

875132bf4 ^

eebee0eff ^

875132bf4 ^

c6671776a ^

875132bf4 ^

c50a04adc ^

875132bf4 ^

326b7dc55 ^

875132bf4 ^

ab47a870b ^

875132bf4 ^

987b52207 ^

875132bf4 ^

ab47a870b ^

875132bf4 ^

ab47a870b ^

58e0dad37 ^

ab47a870b ^

7ee184713 ^

e25474154 ^

310faca72 ^

eebee0eff ^

70ea45cdb ^

eebee0eff ^

e5bd3b5b9 ^

310faca72 ^

ade67f1ab ^

e5bd3b5b9 ^

310faca72 ^

e5bd3b5b9 ^

1afdefcbe ^

8ef66b973 ^

e01e0a4b4 ^

df4d5b77a ^

8ef66b973 ^

ade67f1ab ^

e5bd3b5b9 ^

310faca72 ^

0171566c9 ^

310faca72 ^

2df9b442c ^

0171566c9 ^

b74faf354 ^

56015e52b ^

7bf98411b ^

326b7dc55 ^

7bf98411b ^

0171566c9 ^

e12946691 ^

31651ecd6 ^

dc4b2c920 ^

f713e730c ^

5bcf8bcb5 ^

dc4b2c920 ^

e25474154 ^

8cd5f1f8f ^

c7158af75 ^

44d82d949 ^

a22c1f444 ^

299cefdc9 ^

2a7fc84c8 ^

a22c1f444 ^

44d82d949 ^

1b7cf3df5 ^

746da12d7 ^

1b7cf3df5 ^

a22c1f444 ^

78f371c03 ^

f5fa5dae8 ^

1088814e5 ^

f5fa5dae8 ^

02b78d3f9 ^

f5fa5dae8 ^

e9a3ffbc3 ^

78f371c03 ^

dee8e6e98 ^

1088814e5 ^

02b78d3f9 ^

1088814e5 ^

3aa7c2232 ^

1088814e5 ^

c7158af75 ^

1e26047c3 ^

bf557a7cd ^

60b187513 ^

bf557a7cd ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

1efb5174f ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

1e26047c3 ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

cac259cdf ^

de3b7cd41 ^

1
2

10
11

25
26

28
29

35
36

37
38
39

40
41
42

43
44

48
49

50
51
52

53
54

55
56

72
73
74

93
94

95
96

99
100

104
105

106
107
108

116
117

121
122

123
124
125

133
134

138
139

142
143

159
160
161

171
172
173

175
176
177

193
194
195

198
199

203
204

205
206
207

214
215

220
221

234
235

237
238

240
241

243
244
245

246
247

262
263

286
287

288
289
290

291
292
293

301
302

306
307

312
313

316
317
318

320
321
322

323
324

329
330

336
337
338

339
340
341

363
364
365

368
369
370

377
378

382
383

391
392

414
415

418
419
420

425
426

443
444
445

446
447

448
449

452
453

455
456
457

460
461

464
465

475
476
477

482
483

484
485
486

493
494
495

499
500
501

503
504

508
509

521
522

523
524
525

526
527

530
531
532

577
578

579
580

586
587

593
594

598
599

600
601

612
613

626
627

631
632
633

639
640

654
655

664
665

678
679
680

682
683

684
685

686
687

690
691
692

694
695
696

740
741
742

746
747
748

773
774

775
776

778
779
780

782
783

791
792

799
800

801
802

818
819
820

826
827
828

833
834

839
840
841

843
844

847
848
849

854
855

858
859

875
876
877

879
880
881

887
888
889

899
900

902
903

905
906
907

909
910
911

917
918

919
920

927
928
929

961
962
963

964
965

966
967
968

982
983

987
988

989
990

995
996

997
998

1022
1023

1034
1035

1036
1037

1044
1045
1046

1052
1053
1054

1056
1057

1066
1067

1068
1069

1070
1071

1072
1073

1076
1077

1079
1080

1081
1082

1083
1084
1085

1087
1088

1107
1108

1109
1110

1112
1113

1115
1116
1117

1122
1123

1127
1128

1131
1132

1159
1160

1168
1169
1170

1172
1173
1174

1176
1177

1181
1182

1193
1194

1207
1208
1209

1210
1211

1232
1233

1234
1235

1236
1237

1239
1240
1241

1242
1243

1248
1249

1263
1264

1267
1268

1275
1276

1277
1278
1279

1287
1288
1289

1297
1298

1304
1305

1322
1323

1329
1330

1346
1347

1375
1376
1377

1378
1379

1381
1382
1383

1386
1387

1392
1393

1403
1404

1408
1409
1410

1411
1412
1413

1417
1418

1424
1425
1426

1431
1432

1437
1438

1451
1452

1453
1454
1455

1456
1457

1458
1459

1466
1467

1476
1477

1481
1482

1484
1485

1532
1533
1534

1550
1551

1567
1568

1571
1572

1576
1577

1578
1579
1580

1582
1583
1584

1586
1587

1594
1595

1601
1602

1612
1613
1614

1642
1643

1657
1658
1659

1661
1662

1668
1669

1678
1679
1680

1697
1698

1706
1707
1708

1710
1711

1717
1718

1720
1721
1722

1732
1733

1738
1739

1748
1749
1750

1751
1752

1760
1761

1763
1764

1765
1766
1767

1794
1795

1796
1797
1798

1800
1801

1805
1806
1807

1808
1809

1813
1814

1838
1839

1846
1847
1848

1859
1860

1861
1862

1865
1866

1874
1875
1876

1877
1878

1886
1887
1888

1891
1892
1893

1894
1895
1896

1901
1902
1903

1914
1915

1916
1917

1923
1924
1925

1931
1932
1933

1934
1935
1936

1968
1969

1970
1971
1972

1973
1974

1977
1978

1981
1982

2010
2011
2012

2014
2015
2016

2049
2050

2056
2057

2065
2066

2067
2068
2069

2073
2074

2077
2078

2082
2083

2085
2086

2087
2088
2089

2094
2095

2098
2099

2107
2108

2121
2122

2127
2128

2129
2130

2144
2145

2148
2149

2163
2164
2165

2166
2167
2168

2170
2171
2172

2176
2177
2178

2185
2186

2192
2193

2197
2198

2204
2205

2211
2212

2224
2225
2226

2228
2229
2230

2232
2233

2234
2235

2236
2237
2238

2239
2240

2241
2242
2243

2247
2248

2250
2251
2252

2254
2255

2259
2260

2266
2267

2268
2269

2276
2277

2293
2294
2295

2296
2297

2311
2312

2321
2322

2324
2325
2326

2328
2329

2338
2339

2348
2349

2351
2352

2362
2363

2369
2370

2374
2375
2376

2386
2387

2389
2390
2391

2394
2395

2409
2410

2412
2413

2419
2420

2423
2424

2428
2429

2436
2437
2438

2440
2441

2443
2444
2445

2457
2458
2459

2464
2465

2473
2474
2475

2477
2478

2496
2497
2498

2502
2503

2508
2509

2510
2511
2512

2524
2525

2526
2527
2528

2529
2530

2543
2544
2545

2547
2548

2554
2555

2558
2559

2572
2573

2574
2575

2582
2583

2646
2647

2660
2661

2672
2673
2674

2696
2697

#
#
#           The Nim Compiler
#        (c) Copyright 2013 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## This module implements the signature matching for resolving
## the call to overloaded procs, generic procs and operators.

import
  intsets, ast, astalgo, semdata, types, msgs, renderer, lookups, semtypinst,
  magicsys, condsyms, idents, lexer, options, parampatterns, strutils, trees,
  linter, lineinfos, lowerings, modulegraphs

when (defined(booting) or defined(nimsuggest)) and not defined(leanCompiler):
  import docgen

type
  TCandidateState* = enum
    csEmpty, csMatch, csNoMatch

  CandidateError* = object
    sym*: PSym
    unmatchedVarParam*, firstMismatch*: int
    diagnostics*: seq[string]
    enabled*: bool

  CandidateErrors* = seq[CandidateError]

  TCandidate* = object
    c*: PContext
    exactMatches*: int       # also misused to prefer iters over procs
    genericMatches: int      # also misused to prefer constraints
    subtypeMatches: int
    intConvMatches: int      # conversions to int are not as expensive
    convMatches: int
    state*: TCandidateState
    callee*: PType           # may not be nil!
    calleeSym*: PSym         # may be nil
    calleeScope*: int        # scope depth:
                             # is this a top-level symbol or a nested proc?
    call*: PNode             # modified call
    bindings*: TIdTable      # maps types to types
    magic*: TMagic           # magic of operation
    baseTypeMatch: bool      # needed for conversions from T to openarray[T]
                             # for example
    fauxMatch*: TTypeKind    # the match was successful only due to the use
                             # of error or wildcard (unknown) types.
                             # this is used to prevent instantiations.
    genericConverter*: bool  # true if a generic converter needs to
                             # be instantiated
    coerceDistincts*: bool   # this is an explicit coercion that can strip away
                             # a distrinct type
    typedescMatched*: bool
    isNoCall*: bool          # misused for generic type instantiations C[T]
    mutabilityProblem*: uint8 # tyVar mismatch
    inferredTypes: seq[PType] # inferred types during the current signature
                              # matching. they will be reset if the matching
                              # is not successful. may replace the bindings
                              # table in the future.
    diagnostics*: seq[string] # \
                              # when diagnosticsEnabled, the matching process
                              # will collect extra diagnostics that will be
                              # displayed to the user.
                              # triggered when overload resolution fails
                              # or when the explain pragma is used. may be
                              # triggered with an idetools command in the
                              # future.
    inheritancePenalty: int   # to prefer closest father object type
    firstMismatch*: int       # position of the first type mismatch for
                              # better error messages
    diagnosticsEnabled*: bool

  TTypeRelFlag* = enum
    trDontBind
    trNoCovariance

  TTypeRelFlags* = set[TTypeRelFlag]

  TTypeRelation* = enum      # order is important!
    isNone, isConvertible,
    isIntConv,
    isSubtype,
    isSubrange,              # subrange of the wanted type; no type conversion
                             # but apart from that counts as ``isSubtype``
    isBothMetaConvertible    # generic proc parameter was matched against
                             # generic type, e.g., map(mySeq, x=>x+1),
                             # maybe recoverable by rerun if the parameter is
                             # the proc's return value
    isInferred,              # generic proc was matched against a concrete type
    isInferredConvertible,   # same as above, but requiring proc CC conversion
    isGeneric,
    isFromIntLit,            # conversion *from* int literal; proven safe
    isEqual

const
  isNilConversion = isConvertible # maybe 'isIntConv' fits better?

proc markUsed*(conf: ConfigRef; info: TLineInfo, s: PSym; usageSym: var PSym)

template hasFauxMatch*(c: TCandidate): bool = c.fauxMatch != tyNone

proc initCandidateAux(ctx: PContext,
                      c: var TCandidate, callee: PType) {.inline.} =
  c.c = ctx
  c.exactMatches = 0
  c.subtypeMatches = 0
  c.convMatches = 0
  c.intConvMatches = 0
  c.genericMatches = 0
  c.state = csEmpty
  c.callee = callee
  c.call = nil
  c.baseTypeMatch = false
  c.genericConverter = false
  c.inheritancePenalty = 0

proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PType) =
  initCandidateAux(ctx, c, callee)
  c.calleeSym = nil
  initIdTable(c.bindings)

proc put(c: var TCandidate, key, val: PType) {.inline.} =
  when false:
    let old = PType(idTableGet(c.bindings, key))
    if old != nil:
      echo "Putting ", typeToString(key), " ", typeToString(val), " and old is ", typeToString(old)
      if typeToString(old) == "seq[string]":
        writeStackTrace()
    if c.c.module.name.s == "temp3":
      echo "binding ", key, " -> ", val
  idTablePut(c.bindings, key, val.skipIntLit)

proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PSym,
                    binding: PNode, calleeScope = -1,
                    diagnosticsEnabled = false) =
  initCandidateAux(ctx, c, callee.typ)
  c.calleeSym = callee
  if callee.kind in skProcKinds and calleeScope == -1:
    if callee.originatingModule == ctx.module:
      c.calleeScope = 2
      var owner = callee
      while true:
        owner = owner.skipGenericOwner
        if owner.kind == skModule: break
        inc c.calleeScope
    else:
      c.calleeScope = 1
  else:
    c.calleeScope = calleeScope
  c.diagnostics = @[] # if diagnosticsEnabled: @[] else: nil
  c.diagnosticsEnabled = diagnosticsEnabled
  c.magic = c.calleeSym.magic
  initIdTable(c.bindings)
  if binding != nil and callee.kind in routineKinds:
    var typeParams = callee.ast[genericParamsPos]
    for i in 1..min(sonsLen(typeParams), sonsLen(binding)-1):
      var formalTypeParam = typeParams.sons[i-1].typ
      var bound = binding[i].typ
      if bound != nil:
        if formalTypeParam.kind == tyTypeDesc:
          if bound.kind != tyTypeDesc:
            bound = makeTypeDesc(ctx, bound)
        else:
          bound = bound.skipTypes({tyTypeDesc})
        put(c, formalTypeParam, bound)

proc newCandidate*(ctx: PContext, callee: PSym,
                   binding: PNode, calleeScope = -1): TCandidate =
  initCandidate(ctx, result, callee, binding, calleeScope)

proc newCandidate*(ctx: PContext, callee: PType): TCandidate =
  initCandidate(ctx, result, callee)

proc copyCandidate(a: var TCandidate, b: TCandidate) =
  a.c = b.c
  a.exactMatches = b.exactMatches
  a.subtypeMatches = b.subtypeMatches
  a.convMatches = b.convMatches
  a.intConvMatches = b.intConvMatches
  a.genericMatches = b.genericMatches
  a.state = b.state
  a.callee = b.callee
  a.calleeSym = b.calleeSym
  a.call = copyTree(b.call)
  a.baseTypeMatch = b.baseTypeMatch
  copyIdTable(a.bindings, b.bindings)

proc sumGeneric(t: PType): int =
  # count the "genericness" so that Foo[Foo[T]] has the value 3
  # and Foo[T] has the value 2 so that we know Foo[Foo[T]] is more
  # specific than Foo[T].
  var t = t
  var isvar = 1
  while true:
    case t.kind
    of tyGenericInst, tyArray, tyRef, tyPtr, tyDistinct, tyUncheckedArray,
        tyOpenArray, tyVarargs, tySet, tyRange, tySequence, tyGenericBody,
        tyLent, tyOwned:
      t = t.lastSon
      inc result
    of tyOr:
      var maxBranch = 0
      for branch in t.sons:
        let branchSum = sumGeneric(branch)
        if branchSum > maxBranch: maxBranch = branchSum
      inc result, maxBranch
      break
    of tyVar:
      t = t.sons[0]
      inc result
      inc isvar
    of tyTypeDesc:
      t = t.lastSon
      if t.kind == tyEmpty: break
      inc result
    of tyGenericInvocation, tyTuple, tyProc, tyAnd:
      result += ord(t.kind in {tyGenericInvocation, tyAnd})
      for i in 0 ..< t.len:
        if t.sons[i] != nil:
          result += sumGeneric(t.sons[i])
      break
    of tyStatic:
      return sumGeneric(t.sons[0]) + 1
    of tyGenericParam, tyUntyped, tyTyped: break
    of tyAlias, tySink: t = t.lastSon
    of tyBool, tyChar, tyEnum, tyObject, tyPointer,
        tyString, tyCString, tyInt..tyInt64, tyFloat..tyFloat128,
        tyUInt..tyUInt64, tyCompositeTypeClass:
      return isvar
    else:
      return 0

#var ggDebug: bool

proc complexDisambiguation(a, b: PType): int =
  # 'a' matches better if *every* argument matches better or equal than 'b'.
  var winner = 0
  for i in 1 ..< min(a.len, b.len):
    let x = a.sons[i].sumGeneric
    let y = b.sons[i].sumGeneric
    #if ggDebug:
    #echo "came herA ", typeToString(a.sons[i]), " ", x
    #echo "came herB ", typeToString(b.sons[i]), " ", y
    if x != y:
      if winner == 0:
        if x > y: winner = 1
        else: winner = -1
      elif x > y:
        if winner != 1:
          # contradiction
          return 0
      else:
        if winner != -1:
          return 0
  result = winner
  when false:
    var x, y: int
    for i in 1 ..< a.len: x += a.sons[i].sumGeneric
    for i in 1 ..< b.len: y += b.sons[i].sumGeneric
    result = x - y

proc writeMatches*(c: TCandidate) =
  echo "Candidate '", c.calleeSym.name.s, "' at ", c.c.config $ c.calleeSym.info
  echo "  exact matches: ", c.exactMatches
  echo "  generic matches: ", c.genericMatches
  echo "  subtype matches: ", c.subtypeMatches
  echo "  intconv matches: ", c.intConvMatches
  echo "  conv matches: ", c.convMatches
  echo "  inheritance: ", c.inheritancePenalty

proc cmpCandidates*(a, b: TCandidate): int =
  result = a.exactMatches - b.exactMatches
  if result != 0: return
  result = a.genericMatches - b.genericMatches
  if result != 0: return
  result = a.subtypeMatches - b.subtypeMatches
  if result != 0: return
  result = a.intConvMatches - b.intConvMatches
  if result != 0: return
  result = a.convMatches - b.convMatches
  if result != 0: return
  # the other way round because of other semantics:
  result = b.inheritancePenalty - a.inheritancePenalty
  if result != 0: return
  # prefer more specialized generic over more general generic:
  result = complexDisambiguation(a.callee, b.callee)
  # only as a last resort, consider scoping:
  if result != 0: return
  result = a.calleeScope - b.calleeScope

proc argTypeToString(arg: PNode; prefer: TPreferedDesc): string =
  if arg.kind in nkSymChoices:
    result = typeToString(arg[0].typ, prefer)
    for i in 1 ..< arg.len:
      result.add(" | ")
      result.add typeToString(arg[i].typ, prefer)
  elif arg.typ == nil:
    result = "void"
  else:
    result = arg.typ.typeToString(prefer)

proc describeArgs*(c: PContext, n: PNode, startIdx = 1;
                   prefer: TPreferedDesc = preferName): string =
  result = ""
  for i in startIdx ..< n.len:
    var arg = n.sons[i]
    if n.sons[i].kind == nkExprEqExpr:
      add(result, renderTree(n.sons[i].sons[0]))
      add(result, ": ")
      if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo}:
        # XXX we really need to 'tryExpr' here!
        arg = c.semOperand(c, n.sons[i].sons[1])
        n.sons[i].typ = arg.typ
        n.sons[i].sons[1] = arg
    else:
      if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo, nkElse,
                                           nkOfBranch, nkElifBranch,
                                           nkExceptBranch}:
        arg = c.semOperand(c, n.sons[i])
        n.sons[i] = arg
    if arg.typ != nil and arg.typ.kind == tyError: return
    add(result, argTypeToString(arg, prefer))
    if i != sonsLen(n) - 1: add(result, ", ")

proc typeRel*(c: var TCandidate, f, aOrig: PType,
              flags: TTypeRelFlags = {}): TTypeRelation

proc concreteType(c: TCandidate, t: PType; f: PType = nil): PType =
  case t.kind
  of tyNil:
    result = nil              # what should it be?
  of tyTypeDesc:
    if c.isNoCall: result = t
    else: result = nil
  of tySequence, tySet:
    if t.sons[0].kind == tyEmpty: result = nil
    else: result = t
  of tyGenericParam, tyAnything:
    result = t
    while true:
      result = PType(idTableGet(c.bindings, t))
      if result == nil:
        break # it's ok, no match
        # example code that triggers it:
        # proc sort[T](cmp: proc(a, b: T): int = cmp)
      if result.kind != tyGenericParam: break
  of tyGenericInvocation:
    result = t
    doAssert(false, "cannot resolve type: " & typeToString(t))
  of tyOwned:
    # bug #11257: the comparison system.`==`[T: proc](x, y: T) works
    # better without the 'owned' type:
    if f != nil and f.len > 0 and f.sons[0].skipTypes({tyBuiltInTypeClass}).kind == tyProc:
      result = t.lastSon
    else:
      result = t
  else:
    result = t                # Note: empty is valid here

proc handleRange(f, a: PType, min, max: TTypeKind): TTypeRelation =
  if a.kind == f.kind:
    result = isEqual
  else:
    let ab = skipTypes(a, {tyRange})
    let k = ab.kind
    if k == f.kind: result = isSubrange
    elif k == tyInt and f.kind in {tyRange, tyInt8..tyInt64,
                                   tyUInt..tyUInt64} and
        isIntLit(ab) and ab.n.intVal >= firstOrd(nil, f) and
                         ab.n.intVal <= lastOrd(nil, f):
      # passing 'nil' to firstOrd/lastOrd here as type checking rules should
      # not depent on the target integer size configurations!
      # integer literal in the proper range; we want ``i16 + 4`` to stay an
      # ``int16`` operation so we declare the ``4`` pseudo-equal to int16
      result = isFromIntLit
    elif f.kind == tyInt and k in {tyInt8..tyInt32}:
      result = isIntConv
    elif f.kind == tyUInt and k in {tyUInt8..tyUInt32}:
      result = isIntConv
    elif k >= min and k <= max:
      result = isConvertible
    elif a.kind == tyRange and
      # Make sure the conversion happens between types w/ same signedness
      (f.kind in {tyInt..tyInt64} and a[0].kind in {tyInt..tyInt64} or
       f.kind in {tyUInt8..tyUInt32} and a[0].kind in {tyUInt8..tyInt32}) and
      a.n[0].intVal >= firstOrd(nil, f) and a.n[1].intVal <= lastOrd(nil, f):
      # passing 'nil' to firstOrd/lastOrd here as type checking rules should
      # not depent on the target integer size configurations!
      result = isConvertible
    else: result = isNone

proc isConvertibleToRange(f, a: PType): bool =
  # be less picky for tyRange, as that it is used for array indexing:
  if f.kind in {tyInt..tyInt64, tyUInt..tyUInt64} and
     a.kind in {tyInt..tyInt64, tyUInt..tyUInt64}:
    case f.kind
    of tyInt, tyInt64: result = true
    of tyInt8: result = a.kind in {tyInt8, tyInt}
    of tyInt16: result = a.kind in {tyInt8, tyInt16, tyInt}
    of tyInt32: result = a.kind in {tyInt8, tyInt16, tyInt32, tyInt}
    of tyUInt, tyUInt64: result = true
    of tyUInt8: result = a.kind in {tyUInt8, tyUInt}
    of tyUInt16: result = a.kind in {tyUInt8, tyUInt16, tyUInt}
    of tyUInt32: result = a.kind in {tyUInt8, tyUInt16, tyUInt32, tyUInt}
    else: result = false
  elif f.kind in {tyFloat..tyFloat128} and
       a.kind in {tyFloat..tyFloat128}:
    result = true

proc handleFloatRange(f, a: PType): TTypeRelation =
  if a.kind == f.kind:
    result = isEqual
  else:
    let ab = skipTypes(a, {tyRange})
    var k = ab.kind
    if k == f.kind: result = isSubrange
    elif isFloatLit(ab): result = isFromIntLit
    elif isIntLit(ab): result = isConvertible
    elif k >= tyFloat and k <= tyFloat128:
      # conversion to "float32" is not as good:
      if f.kind == tyFloat32: result = isConvertible
      else: result = isIntConv
    else: result = isNone

proc genericParamPut(c: var TCandidate; last, fGenericOrigin: PType) =
  if fGenericOrigin != nil and last.kind == tyGenericInst and
     last.len-1 == fGenericOrigin.len:
    for i in 1 ..< sonsLen(fGenericOrigin):
      let x = PType(idTableGet(c.bindings, fGenericOrigin.sons[i]))
      if x == nil:
        put(c, fGenericOrigin.sons[i], last.sons[i])

proc isObjectSubtype(c: var TCandidate; a, f, fGenericOrigin: PType): int =
  var t = a
  assert t.kind == tyObject
  var depth = 0
  var last = a
  while t != nil and not sameObjectTypes(f, t):
    assert t.kind == tyObject
    t = t.sons[0]
    if t == nil: break
    last = t
    t = skipTypes(t, skipPtrs)
    inc depth
  if t != nil:
    genericParamPut(c, last, fGenericOrigin)
    result = depth
  else:
    result = -1

type
  SkippedPtr = enum skippedNone, skippedRef, skippedPtr

proc skipToObject(t: PType; skipped: var SkippedPtr): PType =
  var r = t
  # we're allowed to skip one level of ptr/ref:
  var ptrs = 0
  while r != nil:
    case r.kind
    of tyGenericInvocation:
      r = r.sons[0]
    of tyRef:
      inc ptrs
      skipped = skippedRef
      r = r.lastSon
    of tyPtr:
      inc ptrs
      skipped = skippedPtr
      r = r.lastSon
    of tyGenericBody, tyGenericInst, tyAlias, tySink, tyOwned:
      r = r.lastSon
    else:
      break
  if r.kind == tyObject and ptrs <= 1: result = r

proc isGenericSubtype(c: var TCandidate; a, f: PType, d: var int, fGenericOrigin: PType): bool =
  assert f.kind in {tyGenericInst, tyGenericInvocation, tyGenericBody}
  var askip = skippedNone
  var fskip = skippedNone
  var t = a.skipToObject(askip)
  let r = f.skipToObject(fskip)
  if r == nil: return false
  var depth = 0
  var last = a
  # XXX sameObjectType can return false here. Need to investigate
  # why that is but sameObjectType does way too much work here anyway.
  while t != nil and r.sym != t.sym and askip == fskip:
    t = t.sons[0]
    if t == nil: break
    last = t
    t = t.skipToObject(askip)
    inc depth
  if t != nil and askip == fskip:
    genericParamPut(c, last, fGenericOrigin)
    d = depth
    result = true

proc minRel(a, b: TTypeRelation): TTypeRelation =
  if a <= b: result = a
  else: result = b

proc recordRel(c: var TCandidate, f, a: PType): TTypeRelation =
  result = isNone
  if sameType(f, a):
    result = isEqual
  elif sonsLen(a) == sonsLen(f):
    result = isEqual
    let firstField = if f.kind == tyTuple: 0
                     else: 1
    for i in firstField ..< sonsLen(f):
      var m = typeRel(c, f.sons[i], a.sons[i])
      if m < isSubtype: return isNone
      result = minRel(result, m)
    if f.n != nil and a.n != nil:
      for i in 0 ..< sonsLen(f.n):
        # check field names:
        if f.n.sons[i].kind != nkSym: return isNone
        elif a.n.sons[i].kind != nkSym: return isNone
        else:
          var x = f.n.sons[i].sym
          var y = a.n.sons[i].sym
          if f.kind == tyObject and typeRel(c, x.typ, y.typ) < isSubtype:
            return isNone
          if x.name.id != y.name.id: return isNone

proc allowsNil(f: PType): TTypeRelation {.inline.} =
  result = if tfNotNil notin f.flags: isSubtype else: isNone

proc allowsNilDeprecated(c: TCandidate, f: PType): TTypeRelation =
  if optNilSeqs in c.c.config.options:
    result = allowsNil(f)
  else:
    result = isNone

proc inconsistentVarTypes(f, a: PType): bool {.inline.} =
  result = f.kind != a.kind and (f.kind in {tyVar, tyLent} or a.kind in {tyVar, tyLent})

proc procParamTypeRel(c: var TCandidate, f, a: PType): TTypeRelation =
  ## For example we have:
  ## .. code-block:: nim
  ##   proc myMap[T,S](sIn: seq[T], f: proc(x: T): S): seq[S] = ...
  ##   proc innerProc[Q,W](q: Q): W = ...
  ## And we want to match: myMap(@[1,2,3], innerProc)
  ## This proc (procParamTypeRel) will do the following steps in
  ## three different calls:
  ## - matches f=T to a=Q. Since f is metatype, we resolve it
  ##    to int (which is already known at this point). So in this case
  ##    Q=int mapping will be saved to c.bindings.
  ## - matches f=S to a=W. Both of these metatypes are unknown, so we
  ##    return with isBothMetaConvertible to ask for rerun.
  ## - matches f=S to a=W. At this point the return type of innerProc
  ##    is known (we get it from c.bindings). We can use that value
  ##    to match with f, and save back to c.bindings.
  var
    f = f
    a = a

  if a.isMetaType:
    let aResolved = PType(idTableGet(c.bindings, a))
    if aResolved != nil:
      a = aResolved
  if a.isMetaType:
    if f.isMetaType:
      # We are matching a generic proc (as proc param)
      # to another generic type appearing in the proc
      # signature. There is a change that the target
      # type is already fully-determined, so we are
      # going to try resolve it
      if c.call != nil:
        f = generateTypeInstance(c.c, c.bindings, c.call.info, f)
      else:
        f = nil
      if f == nil or f.isMetaType:
        # no luck resolving the type, so the inference fails
        return isBothMetaConvertible
    # Note that this typeRel call will save a's resolved type into c.bindings
    let reverseRel = typeRel(c, a, f)
    if reverseRel >= isGeneric:
      result = isInferred
      #inc c.genericMatches
  else:
    # Note that this typeRel call will save f's resolved type into c.bindings
    # if f is metatype.
    result = typeRel(c, f, a)

  if result <= isSubtype or inconsistentVarTypes(f, a):
    result = isNone

  #if result == isEqual:
  #  inc c.exactMatches

proc procTypeRel(c: var TCandidate, f, a: PType): TTypeRelation =
  case a.kind
  of tyProc:
    if sonsLen(f) != sonsLen(a): return
    result = isEqual      # start with maximum; also correct for no
                          # params at all

    template checkParam(f, a) =
      result = minRel(result, procParamTypeRel(c, f, a))
      if result == isNone: return

    # Note: We have to do unification for the parameters before the
    # return type!
    for i in 1 ..< f.sonsLen:
      checkParam(f.sons[i], a.sons[i])

    if f.sons[0] != nil:
      if a.sons[0] != nil:
        checkParam(f.sons[0], a.sons[0])
      else:
        return isNone
    elif a.sons[0] != nil:
      return isNone

    if tfNoSideEffect in f.flags and tfNoSideEffect notin a.flags:
      return isNone
    elif tfThread in f.flags and a.flags * {tfThread, tfNoSideEffect} == {} and
        optThreadAnalysis in c.c.config.globalOptions:
      # noSideEffect implies ``tfThread``!
      return isNone
    elif f.flags * {tfIterator} != a.flags * {tfIterator}:
      return isNone
    elif f.callConv != a.callConv:
      # valid to pass a 'nimcall' thingie to 'closure':
      if f.callConv == ccClosure and a.callConv == ccDefault:
        result = if result == isInferred: isInferredConvertible
                 elif result == isBothMetaConvertible: isBothMetaConvertible
                 else: isConvertible
      else:
        return isNone
    when useEffectSystem:
      if compatibleEffects(f, a) != efCompat: return isNone

  of tyNil:
    result = f.allowsNil
  else: discard

proc typeRangeRel(f, a: PType): TTypeRelation {.noinline.} =
  template checkRange[T](a0, a1, f0, f1: T): TTypeRelation =
    if a0 == f0 and a1 == f1:
      isEqual
    elif a0 >= f0 and a1 <= f1:
      isConvertible
    elif a0 <= f1 and f0 <= a1:
      # X..Y and C..D overlap iff (X <= D and C <= Y)
      isConvertible
    else:
      isNone

  if f.isOrdinalType:
    checkRange(firstOrd(nil, a), lastOrd(nil, a), firstOrd(nil, f), lastOrd(nil, f))
  else:
    checkRange(firstFloat(a), lastFloat(a), firstFloat(f), lastFloat(f))


proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType =
  var
    c = m.c
    typeClass = ff.skipTypes({tyUserTypeClassInst})
    body = typeClass.n[3]
    matchedConceptContext: TMatchedConcept
    prevMatchedConcept = c.matchedConcept
    prevCandidateType = typeClass[0][0]

  if prevMatchedConcept != nil:
    matchedConceptContext.prev = prevMatchedConcept
    matchedConceptContext.depth = prevMatchedConcept.depth + 1
    if prevMatchedConcept.depth > 4:
      localError(m.c.graph.config, body.info, $body & " too nested for type matching")
      return nil

  openScope(c)
  matchedConceptContext.candidateType = a
  typeClass[0].sons[0] = a
  c.matchedConcept = addr(matchedConceptContext)
  defer:
    c.matchedConcept = prevMatchedConcept
    typeClass[0].sons[0] = prevCandidateType
    closeScope(c)

  var typeParams: seq[(PSym, PType)]

  if ff.kind == tyUserTypeClassInst:
    for i in 1 ..< (ff.len - 1):
      var
        typeParamName = ff.base.sons[i-1].sym.name
        typ = ff.sons[i]
        param: PSym
        alreadyBound = PType(idTableGet(m.bindings, typ))

      if alreadyBound != nil: typ = alreadyBound

      template paramSym(kind): untyped =
        newSym(kind, typeParamName, typeClass.sym, typeClass.sym.info, {})

      block addTypeParam:
        for prev in typeParams:
          if prev[1].id == typ.id:
            param = paramSym prev[0].kind
            param.typ = prev[0].typ
            break addTypeParam

        case typ.kind
        of tyStatic:
          param = paramSym skConst
          param.typ = typ.exactReplica
          if typ.n == nil:
            param.typ.flags.incl tfInferrableStatic
          else:
            param.ast = typ.n
        of tyUnknown:
          param = paramSym skVar
          param.typ = typ.exactReplica
        else:
          param = paramSym skType
          param.typ = if typ.isMetaType:
                        c.newTypeWithSons(tyInferred, @[typ])
                      else:
                        makeTypeDesc(c, typ)

        typeParams.add((param, typ))

      addDecl(c, param)

  var
    oldWriteHook: type(m.c.config.writelnHook)
    diagnostics: seq[string]
    errorPrefix: string
    flags: TExprFlags = {}
    collectDiagnostics = m.diagnosticsEnabled or
                         sfExplain in typeClass.sym.flags

  if collectDiagnostics:
    oldWriteHook = m.c.config.writelnHook
    # XXX: we can't write to m.diagnostics directly, because
    # Nim doesn't support capturing var params in closures
    diagnostics = @[]
    flags = {efExplain}
    m.c.config.writelnHook = proc (s: string) =
      if errorPrefix.len == 0: errorPrefix = typeClass.sym.name.s & ":"
      let msg = s.replace("Error:", errorPrefix)
      if oldWriteHook != nil: oldWriteHook msg
      diagnostics.add msg

  var checkedBody = c.semTryExpr(c, body.copyTree, flags)

  if collectDiagnostics:
    m.c.config.writelnHook = oldWriteHook
    for msg in diagnostics:
      m.diagnostics.add msg
      m.diagnosticsEnabled = true

  if checkedBody == nil: return nil

  # The inferrable type params have been identified during the semTryExpr above.
  # We need to put them in the current sigmatch's binding table in order for them
  # to be resolvable while matching the rest of the parameters
  for p in typeParams:
    put(m, p[1], p[0].typ)

  if ff.kind == tyUserTypeClassInst:
    result = generateTypeInstance(c, m.bindings, typeClass.sym.info, ff)
  else:
    result = copyType(ff, ff.owner, true)

  result.n = checkedBody

proc shouldSkipDistinct(m: TCandidate; rules: PNode, callIdent: PIdent): bool =
  # XXX This is bad as 'considerQuotedIdent' can produce an error!
  if rules.kind == nkWith:
    for r in rules:
      if considerQuotedIdent(m.c, r) == callIdent: return true
    return false
  else:
    for r in rules:
      if considerQuotedIdent(m.c, r) == callIdent: return false
    return true

proc maybeSkipDistinct(m: TCandidate; t: PType, callee: PSym): PType =
  if t != nil and t.kind == tyDistinct and t.n != nil and
     shouldSkipDistinct(m, t.n, callee.name):
    result = t.base
  else:
    result = t

proc tryResolvingStaticExpr(c: var TCandidate, n: PNode,
                            allowUnresolved = false): PNode =
  # Consider this example:
  #   type Value[N: static[int]] = object
  #   proc foo[N](a: Value[N], r: range[0..(N-1)])
  # Here, N-1 will be initially nkStaticExpr that can be evaluated only after
  # N is bound to a concrete value during the matching of the first param.
  # This proc is used to evaluate such static expressions.
  let instantiated = replaceTypesInBody(c.c, c.bindings, n, nil,
                                        allowMetaTypes = allowUnresolved)
  result = c.c.semExpr(c.c, instantiated)

proc inferStaticParam*(c: var TCandidate, lhs: PNode, rhs: BiggestInt): bool =
  # This is a simple integer arithimetic equation solver,
  # capable of deriving the value of a static parameter in
  # expressions such as (N + 5) / 2 = rhs
  #
  # Preconditions:
  #
  #   * The input of this proc must be semantized
  #     - all templates should be expanded
  #     - aby constant folding possible should already be performed
  #
  #   * There must be exactly one unresolved static parameter
  #
  # Result:
  #
  #   The proc will return true if the static types was successfully
  #   inferred. The result will be bound to the original static type
  #   in the TCandidate.
  #
  if lhs.kind in nkCallKinds and lhs[0].kind == nkSym:
    case lhs[0].sym.magic
    of mUnaryLt:
      return inferStaticParam(c, lhs[1], rhs + 1)

    of mAddI, mAddU, mInc, mSucc:
      if lhs[1].kind == nkIntLit:
        return inferStaticParam(c, lhs[2], rhs - lhs[1].intVal)
      elif lhs[2].kind == nkIntLit:
        return inferStaticParam(c, lhs[1], rhs - lhs[2].intVal)

    of mDec, mSubI, mSubU, mPred:
      if lhs[1].kind == nkIntLit:
        return inferStaticParam(c, lhs[2], lhs[1].intVal - rhs)
      elif lhs[2].kind == nkIntLit:
        return inferStaticParam(c, lhs[1], rhs + lhs[2].intVal)

    of mMulI, mMulU:
      if lhs[1].kind == nkIntLit:
        if rhs mod lhs[1].intVal == 0:
          return inferStaticParam(c, lhs[2], rhs div lhs[1].intVal)
      elif lhs[2].kind == nkIntLit:
        if rhs mod lhs[2].intVal == 0:
          return inferStaticParam(c, lhs[1], rhs div lhs[2].intVal)

    of mDivI, mDivU:
      if lhs[1].kind == nkIntLit:
        if lhs[1].intVal mod rhs == 0:
          return inferStaticParam(c, lhs[2], lhs[1].intVal div rhs)
      elif lhs[2].kind == nkIntLit:
        return inferStaticParam(c, lhs[1], lhs[2].intVal * rhs)

    of mShlI:
      if lhs[2].kind == nkIntLit:
        return inferStaticParam(c, lhs[1], rhs shr lhs[2].intVal)

    of mShrI:
      if lhs[2].kind == nkIntLit:
        return inferStaticParam(c, lhs[1], rhs shl lhs[2].intVal)

    of mAshrI:
      if lhs[2].kind == nkIntLit:
        return inferStaticParam(c, lhs[1], ashr(rhs, lhs[2].intVal))

    of mUnaryMinusI:
      return inferStaticParam(c, lhs[1], -rhs)

    of mUnaryPlusI, mToInt, mToBiggestInt:
      return inferStaticParam(c, lhs[1], rhs)

    else: discard

  elif lhs.kind == nkSym and lhs.typ.kind == tyStatic and lhs.typ.n == nil:
    var inferred = newTypeWithSons(c.c, tyStatic, lhs.typ.sons)
    inferred.n = newIntNode(nkIntLit, rhs)
    put(c, lhs.typ, inferred)
    if c.c.matchedConcept != nil:
      # inside concepts, binding is currently done with
      # direct mutation of the involved types:
      lhs.typ.n = inferred.n
    return true

  return false

proc failureToInferStaticParam(conf: ConfigRef; n: PNode) =
  let staticParam = n.findUnresolvedStatic
  let name = if staticParam != nil: staticParam.sym.name.s
             else: "unknown"
  localError(conf, n.info, "cannot infer the value of the static param '" & name & "'")

proc inferStaticsInRange(c: var TCandidate,
                         inferred, concrete: PType): TTypeRelation =
  let lowerBound = tryResolvingStaticExpr(c, inferred.n[0],
                                          allowUnresolved = true)
  let upperBound = tryResolvingStaticExpr(c, inferred.n[1],
                                          allowUnresolved = true)
  template doInferStatic(e: PNode, r: BiggestInt) =
    var exp = e
    var rhs = r
    if inferStaticParam(c, exp, rhs):
      return isGeneric
    else:
      failureToInferStaticParam(c.c.config, exp)

  if lowerBound.kind == nkIntLit:
    if upperBound.kind == nkIntLit:
      if lengthOrd(c.c.config, concrete) == upperBound.intVal - lowerBound.intVal + 1:
        return isGeneric
      else:
        return isNone
    doInferStatic(upperBound, lengthOrd(c.c.config, concrete) + lowerBound.intVal - 1)
  elif upperBound.kind == nkIntLit:
    doInferStatic(lowerBound, upperBound.intVal + 1 - lengthOrd(c.c.config, concrete))

template subtypeCheck() =
  if result <= isSubrange and f.lastSon.skipTypes(abstractInst).kind in {
      tyRef, tyPtr, tyVar, tyLent, tyOwned}:
    result = isNone

proc isCovariantPtr(c: var TCandidate, f, a: PType): bool =
  # this proc is always called for a pair of matching types
  assert f.kind == a.kind

  template baseTypesCheck(lhs, rhs: PType): bool =
    lhs.kind notin {tyPtr, tyRef, tyVar, tyLent, tyOwned} and
      typeRel(c, lhs, rhs, {trNoCovariance}) == isSubtype

  case f.kind
  of tyRef, tyPtr, tyOwned:
    return baseTypesCheck(f.base, a.base)
  of tyGenericInst:
    let body = f.base
    return body == a.base and
           a.sonsLen == 3 and
           tfWeakCovariant notin body.sons[0].flags and
           baseTypesCheck(f.sons[1], a.sons[1])
  else:
    return false

when false:
  proc maxNumericType(prev, candidate: PType): PType =
    let c = candidate.skipTypes({tyRange})
    template greater(s) =
      if c.kind in s: result = c
    case prev.kind
    of tyInt: greater({tyInt64})
    of tyInt8: greater({tyInt, tyInt16, tyInt32, tyInt64})
    of tyInt16: greater({tyInt, tyInt32, tyInt64})
    of tyInt32: greater({tyInt64})

    of tyUInt: greater({tyUInt64})
    of tyUInt8: greater({tyUInt, tyUInt16, tyUInt32, tyUInt64})
    of tyUInt16: greater({tyUInt, tyUInt32, tyUInt64})
    of tyUInt32: greater({tyUInt64})

    of tyFloat32: greater({tyFloat64, tyFloat128})
    of tyFloat64: greater({tyFloat128})
    else: discard

template skipOwned(a) =
  if a.kind == tyOwned: a = a.skipTypes({tyOwned, tyGenericInst})

proc typeRel(c: var TCandidate, f, aOrig: PType,
             flags: TTypeRelFlags = {}): TTypeRelation =
  # typeRel can be used to establish various relationships between types:
  #
  # 1) When used with concrete types, it will check for type equivalence
  # or a subtype relationship.
  #
  # 2) When used with a concrete type against a type class (such as generic
  # signature of a proc), it will check whether the concrete type is a member
  # of the designated type class.
  #
  # 3) When used with two type classes, it will check whether the types
  # matching the first type class are a strict subset of the types matching
  # the other. This allows us to compare the signatures of generic procs in
  # order to give preferrence to the most specific one:
  #
  # seq[seq[any]] is a strict subset of seq[any] and hence more specific.

  result = isNone
  assert(f != nil)

  if f.kind == tyUntyped:
    if aOrig != nil: put(c, f, aOrig)
    return isGeneric

  assert(aOrig != nil)

  var
    useTypeLoweringRuleInTypeClass = c.c.matchedConcept != nil and
                                     not c.isNoCall and
                                     f.kind != tyTypeDesc and
                                     tfExplicit notin aOrig.flags and
                                     tfConceptMatchedTypeSym notin aOrig.flags

    aOrig = if useTypeLoweringRuleInTypeClass:
          aOrig.skipTypes({tyTypeDesc})
        else:
          aOrig

  if aOrig.kind == tyInferred:
    let prev = aOrig.previouslyInferred
    if prev != nil:
      return typeRel(c, f, prev)
    else:
      var candidate = f

      case f.kind
      of tyGenericParam:
        var prev = PType(idTableGet(c.bindings, f))
        if prev != nil: candidate = prev
      of tyFromExpr:
        let computedType = tryResolvingStaticExpr(c, f.n).typ
        case computedType.kind
        of tyTypeDesc:
          candidate = computedType.base
        of tyStatic:
          candidate = computedType
        else:
          # XXX What is this non-sense? Error reporting in signature matching?
          discard "localError(f.n.info, errTypeExpected)"
      else:
        discard

      result = typeRel(c, aOrig.base, candidate)
      if result != isNone:
        c.inferredTypes.add aOrig
        aOrig.sons.add candidate
        result = isEqual
      return

  template doBind: bool = trDontBind notin flags

  # var, sink and static arguments match regular modifier-free types
  var a = maybeSkipDistinct(c, aOrig.skipTypes({tyStatic, tyVar, tyLent, tySink}), c.calleeSym)
  # XXX: Theoretically, maybeSkipDistinct could be called before we even
  # start the param matching process. This could be done in `prepareOperand`
  # for example, but unfortunately `prepareOperand` is not called in certain
  # situation when nkDotExpr are rotated to nkDotCalls

  if aOrig.kind in {tyAlias, tySink}:
    return typeRel(c, f, lastSon(aOrig))

  if a.kind == tyGenericInst and
      skipTypes(f, {tyVar, tyLent, tySink}).kind notin {
        tyGenericBody, tyGenericInvocation,
        tyGenericInst, tyGenericParam} + tyTypeClasses:
    return typeRel(c, f, lastSon(a))

  if a.isResolvedUserTypeClass:
    return typeRel(c, f, a.lastSon)

  template bindingRet(res) =
    if doBind:
      let bound = aOrig.skipTypes({tyRange}).skipIntLit
      put(c, f, bound)
    return res

  template considerPreviousT(body: untyped) =
    var prev = PType(idTableGet(c.bindings, f))
    if prev == nil: body
    else: return typeRel(c, prev, a)

  case a.kind
  of tyOr:
    # XXX: deal with the current dual meaning of tyGenericParam
    c.typedescMatched = true
    # seq[int|string] vs seq[number]
    # both int and string must match against number
    # but ensure that '[T: A|A]' matches as good as '[T: A]' (bug #2219):
    result = isGeneric
    for branch in a.sons:
      let x = typeRel(c, f, branch, flags + {trDontBind})
      if x == isNone: return isNone
      if x < result: result = x
    return

  of tyAnd:
    # XXX: deal with the current dual meaning of tyGenericParam
    c.typedescMatched = true
    # seq[Sortable and Iterable] vs seq[Sortable]
    # only one match is enough
    for branch in a.sons:
      let x = typeRel(c, f, branch, flags + {trDontBind})
      if x != isNone:
        return if x >= isGeneric: isGeneric else: x
    return isNone

  of tyNot:
    case f.kind
    of tyNot:
      # seq[!int] vs seq[!number]
      # seq[float] matches the first, but not the second
      # we must turn the problem around:
      # is number a subset of int?
      return typeRel(c, a.lastSon, f.lastSon)

    else:
      # negative type classes are essentially infinite,
      # so only the `any` type class is their superset
      return if f.kind == tyAnything: isGeneric
             else: isNone

  of tyAnything:
    if f.kind == tyAnything: return isGeneric
    else: return isNone

  of tyUserTypeClass, tyUserTypeClassInst:
    if c.c.matchedConcept != nil and c.c.matchedConcept.depth <= 4:
      # consider this: 'var g: Node' *within* a concept where 'Node'
      # is a concept too (tgraph)
      inc c.c.matchedConcept.depth
      let x = typeRel(c, a, f, flags + {trDontBind})
      if x >= isGeneric:
        return isGeneric
  else: discard

  case f.kind
  of tyEnum:
    if a.kind == f.kind and sameEnumTypes(f, a): result = isEqual
    elif sameEnumTypes(f, skipTypes(a, {tyRange})): result = isSubtype
  of tyBool, tyChar:
    if a.kind == f.kind: result = isEqual
    elif skipTypes(a, {tyRange}).kind == f.kind: result = isSubtype
  of tyRange:
    if a.kind == f.kind:
      if f.base.kind == tyNone: return isGeneric
      result = typeRel(c, base(f), base(a))
      # bugfix: accept integer conversions here
      #if result < isGeneric: result = isNone
      if result notin {isNone, isGeneric}:
        # resolve any late-bound static expressions
        # that may appear in the range:
        for i in 0..1:
          if f.n[i].kind == nkStaticExpr:
            f.n.sons[i] = tryResolvingStaticExpr(c, f.n[i])
        result = typeRangeRel(f, a)
    else:
      if skipTypes(f, {tyRange}).kind == a.kind:
        result = isIntConv
      elif isConvertibleToRange(skipTypes(f, {tyRange}), a):
        result = isConvertible  # a convertible to f
  of tyInt:      result = handleRange(f, a, tyInt8, tyInt32)
  of tyInt8:     result = handleRange(f, a, tyInt8, tyInt8)
  of tyInt16:    result = handleRange(f, a, tyInt8, tyInt16)
  of tyInt32:    result = handleRange(f, a, tyInt8, tyInt32)
  of tyInt64:    result = handleRange(f, a, tyInt, tyInt64)
  of tyUInt:     result = handleRange(f, a, tyUInt8, tyUInt32)
  of tyUInt8:    result = handleRange(f, a, tyUInt8, tyUInt8)
  of tyUInt16:   result = handleRange(f, a, tyUInt8, tyUInt16)
  of tyUInt32:   result = handleRange(f, a, tyUInt8, tyUInt32)
  of tyUInt64:   result = handleRange(f, a, tyUInt, tyUInt64)
  of tyFloat:    result = handleFloatRange(f, a)
  of tyFloat32:  result = handleFloatRange(f, a)
  of tyFloat64:  result = handleFloatRange(f, a)
  of tyFloat128: result = handleFloatRange(f, a)
  of tyVar, tyLent:
    if aOrig.kind == f.kind: result = typeRel(c, f.base, aOrig.base)
    else: result = typeRel(c, f.base, aOrig, flags + {trNoCovariance})
    subtypeCheck()
  of tyArray:
    case a.kind
    of tyArray:
      var fRange = f.sons[0]
      var aRange = a.sons[0]
      if fRange.kind == tyGenericParam:
        var prev = PType(idTableGet(c.bindings, fRange))
        if prev == nil:
          put(c, fRange, a.sons[0])
          fRange = a
        else:
          fRange = prev
      let ff = f.sons[1].skipTypes({tyTypeDesc})
      # This typeDesc rule is wrong, see bug #7331
      let aa = a.sons[1] #.skipTypes({tyTypeDesc})

      if f.sons[0].kind != tyGenericParam and aa.kind == tyEmpty:
        result = isGeneric
      else:
        result = typeRel(c, ff, aa)

      if result < isGeneric:
        if nimEnableCovariance and
           trNoCovariance notin flags and
           ff.kind == aa.kind and
           isCovariantPtr(c, ff, aa):
          result = isSubtype
        else:
          return isNone

      if fRange.rangeHasUnresolvedStatic:
        return inferStaticsInRange(c, fRange, a)
      elif c.c.matchedConcept != nil and aRange.rangeHasUnresolvedStatic:
        return inferStaticsInRange(c, aRange, f)
      else:
        if lengthOrd(c.c.config, fRange) != lengthOrd(c.c.config, aRange):
          result = isNone
    else: discard
  of tyUncheckedArray:
    if a.kind == tyUncheckedArray:
      result = typeRel(c, base(f), base(a))
      if result < isGeneric: result = isNone
    else: discard
  of tyOpenArray, tyVarargs:
    # varargs[expr] is special too but handled earlier. So we only need to
    # handle varargs[stmt] which is the same as varargs[typed]:
    if f.kind == tyVarargs:
      if tfVarargs in a.flags:
        return typeRel(c, f.base, a.lastSon)
      if f.sons[0].kind == tyTyped: return

    template matchArrayOrSeq(aBase: PType) =
      let ff = f.base
      let aa = aBase
      let baseRel = typeRel(c, ff, aa)
      if baseRel >= isGeneric:
        result = isConvertible
      elif nimEnableCovariance and
           trNoCovariance notin flags and
           ff.kind == aa.kind and
           isCovariantPtr(c, ff, aa):
        result = isConvertible

    case a.kind
    of tyOpenArray, tyVarargs:
      result = typeRel(c, base(f), base(a))
      if result < isGeneric: result = isNone
    of tyArray:
      if (f.sons[0].kind != tyGenericParam) and (a.sons[1].kind == tyEmpty):
        return isSubtype
      matchArrayOrSeq(a.sons[1])
    of tySequence:
      if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty):
        return isConvertible
      matchArrayOrSeq(a.sons[0])
    of tyString:
      if f.kind == tyOpenArray:
        if f.sons[0].kind == tyChar:
          result = isConvertible
        elif f.sons[0].kind == tyGenericParam and a.len > 0 and
            typeRel(c, base(f), base(a)) >= isGeneric:
          result = isConvertible
    else: discard
  of tySequence:
    case a.kind
    of tySequence:
      if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty):
        result = isSubtype
      else:
        let ff = f.sons[0]
        let aa = a.sons[0]
        result = typeRel(c, ff, aa)
        if result < isGeneric:
          if nimEnableCovariance and
             trNoCovariance notin flags and
             ff.kind == aa.kind and
             isCovariantPtr(c, ff, aa):
            result = isSubtype
          else:
            result = isNone
        elif tfNotNil in f.flags and tfNotNil notin a.flags:
          result = isNilConversion
    of tyNil: result = allowsNilDeprecated(c, f)
    else: discard
  of tyOrdinal:
    if isOrdinalType(a):
      var x = if a.kind == tyOrdinal: a.sons[0] else: a
      if f.sons[0].kind == tyNone:
        result = isGeneric
      else:
        result = typeRel(c, f.sons[0], x)
        if result < isGeneric: result = isNone
    elif a.kind == tyGenericParam:
      result = isGeneric
  of tyForward:
    #internalError("forward type in typeRel()")
    result = isNone
  of tyNil:
    skipOwned(a)
    if a.kind == f.kind: result = isEqual
  of tyTuple:
    if a.kind == tyTuple: result = recordRel(c, f, a)
  of tyObject:
    if a.kind == tyObject:
      if sameObjectTypes(f, a):
        result = isEqual
        # elif tfHasMeta in f.flags: result = recordRel(c, f, a)
      else:
        var depth = isObjectSubtype(c, a, f, nil)
        if depth > 0:
          inc(c.inheritancePenalty, depth)
          result = isSubtype
  of tyDistinct:
    a = a.skipTypes({tyOwned, tyGenericInst, tyRange})
    if a.kind == tyDistinct:
      if sameDistinctTypes(f, a): result = isEqual
      #elif f.base.kind == tyAnything: result = isGeneric  # issue 4435
      elif c.coerceDistincts: result = typeRel(c, f.base, a)
    elif a.kind == tyNil and f.base.kind in NilableTypes:
      result = f.allowsNil # XXX remove this typing rule, it is not in the spec
    elif c.coerceDistincts: result = typeRel(c, f.base, a)
  of tySet:
    if a.kind == tySet:
      if f.sons[0].kind != tyGenericParam and a.sons[0].kind == tyEmpty:
        result = isSubtype
      else:
        result = typeRel(c, f.sons[0], a.sons[0])
        if result <= isConvertible:
          result = isNone     # BUGFIX!
  of tyPtr, tyRef:
    skipOwned(a)
    if a.kind == f.kind:
      # ptr[R, T] can be passed to ptr[T], but not the other way round:
      if a.len < f.len: return isNone
      for i in 0..f.len-2:
        if typeRel(c, f.sons[i], a.sons[i]) == isNone: return isNone
      result = typeRel(c, f.lastSon, a.lastSon, flags + {trNoCovariance})
      subtypeCheck()
      if result <= isIntConv: result = isNone
      elif tfNotNil in f.flags and tfNotNil notin a.flags:
        result = isNilConversion
    elif a.kind == tyNil: result = f.allowsNil
    else: discard
  of tyProc:
    skipOwned(a)
    result = procTypeRel(c, f, a)
    if result != isNone and tfNotNil in f.flags and tfNotNil notin a.flags:
      result = isNilConversion
  of tyOwned:
    case a.kind
    of tyOwned:
      result = typeRel(c, lastSon(f), lastSon(a))
    of tyNil: result = f.allowsNil
    else: discard
  of tyPointer:
    skipOwned(a)
    case a.kind
    of tyPointer:
      if tfNotNil in f.flags and tfNotNil notin a.flags:
        result = isNilConversion
      else:
        result = isEqual
    of tyNil: result = f.allowsNil
    of tyProc:
      if a.callConv != ccClosure: result = isConvertible
    of tyPtr:
      # 'pointer' is NOT compatible to regionized pointers
      # so 'dealloc(regionPtr)' fails:
      if a.len == 1: result = isConvertible
    of tyCString: result = isConvertible
    else: discard
  of tyString:
    case a.kind
    of tyString:
      if tfNotNil in f.flags and tfNotNil notin a.flags:
        result = isNilConversion
      else:
        result = isEqual
    of tyNil: result = allowsNilDeprecated(c, f)
    else: discard
  of tyCString:
    # conversion from string to cstring is automatic:
    case a.kind
    of tyCString:
      if tfNotNil in f.flags and tfNotNil notin a.flags:
        result = isNilConversion
      else:
        result = isEqual
    of tyNil: result = f.allowsNil
    of tyString: result = isConvertible
    of tyPtr:
      # ptr[Tag, char] is not convertible to 'cstring' for now:
      if a.len == 1:
        let pointsTo = a.sons[0].skipTypes(abstractInst)
        if pointsTo.kind == tyChar: result = isConvertible
        elif pointsTo.kind == tyUncheckedArray and pointsTo.sons[0].kind == tyChar:
          result = isConvertible
        elif pointsTo.kind == tyArray and firstOrd(nil, pointsTo.sons[0]) == 0 and
            skipTypes(pointsTo.sons[0], {tyRange}).kind in {tyInt..tyInt64} and
            pointsTo.sons[1].kind == tyChar:
          result = isConvertible
    else: discard

  of tyEmpty, tyVoid:
    if a.kind == f.kind: result = isEqual

  of tyAlias, tySink:
    result = typeRel(c, lastSon(f), a)

  of tyGenericInst:
    var prev = PType(idTableGet(c.bindings, f))
    let origF = f
    var f = if prev == nil: f else: prev

    let roota = a.skipGenericAlias
    let rootf = f.skipGenericAlias

    var m = c
    if a.kind == tyGenericInst:
      if roota.base == rootf.base:
        let nextFlags = flags + {trNoCovariance}
        var hasCovariance = false
        # YYYY
        result = isEqual

        for i in 1 .. rootf.sonsLen-2:
          let ff = rootf.sons[i]
          let aa = roota.sons[i]
          let res = typeRel(c, ff, aa, nextFlags)
          if res != isEqual: result = isGeneric
          if res notin {isEqual, isGeneric}:
            if trNoCovariance notin flags and ff.kind == aa.kind:
              let paramFlags = rootf.base.sons[i-1].flags
              hasCovariance =
                if tfCovariant in paramFlags:
                  if tfWeakCovariant in paramFlags:
                    isCovariantPtr(c, ff, aa)
                  else:
                    ff.kind notin {tyRef, tyPtr} and res == isSubtype
                else:
                  tfContravariant in paramFlags and
                    typeRel(c, aa, ff) == isSubtype
              if hasCovariance:
                continue

            return isNone
        if prev == nil: put(c, f, a)
      else:
        let fKind = rootf.lastSon.kind
        if fKind in {tyAnd, tyOr}:
          result = typeRel(c, lastSon(f), a)
          if result != isNone: put(c, f, a)
          return

        var aAsObject = roota.lastSon

        if fKind in {tyRef, tyPtr}:
          if aAsObject.kind == tyObject:
            # bug #7600, tyObject cannot be passed
            # as argument to tyRef/tyPtr
            return isNone
          elif aAsObject.kind == fKind:
            aAsObject = aAsObject.base

        if aAsObject.kind == tyObject:
          let baseType = aAsObject.base
          if baseType != nil:
            c.inheritancePenalty += 1
            let ret = typeRel(c, f, baseType)
            return if ret == isEqual: isSubtype else: ret

        result = isNone
    else:
      assert lastSon(origF) != nil
      result = typeRel(c, lastSon(origF), a)
      if result != isNone and a.kind != tyNil:
        put(c, f, a)

  of tyGenericBody:
    considerPreviousT:
      if a == f or a.kind == tyGenericInst and a.sons[0] == f:
        bindingRet isGeneric
      let ff = lastSon(f)
      if ff != nil:
        result = typeRel(c, ff, a)

  of tyGenericInvocation:
    var x = a.skipGenericAlias
    var preventHack = false
    if x.kind == tyOwned and f.sons[0].kind != tyOwned:
      preventHack = true
      x = x.lastSon
    # XXX: This is very hacky. It should be moved back into liftTypeParam
    if x.kind in {tyGenericInst, tyArray} and
       c.calleeSym != nil and
       c.calleeSym.kind in {skProc, skFunc} and c.call != nil and not preventHack:
      let inst = prepareMetatypeForSigmatch(c.c, c.bindings, c.call.info, f)
      #echo "inferred ", typeToString(inst), " for ", f
      return typeRel(c, inst, a)

    var depth = 0
    if x.kind == tyGenericInvocation or f.sons[0].kind != tyGenericBody:
      #InternalError("typeRel: tyGenericInvocation -> tyGenericInvocation")
      # simply no match for now:
      discard
    elif x.kind == tyGenericInst and f.sons[0] == x.sons[0] and
          sonsLen(x) - 1 == sonsLen(f):
      for i in 1 ..< sonsLen(f):
        if x.sons[i].kind == tyGenericParam:
          internalError(c.c.graph.config, "wrong instantiated type!")
        elif typeRel(c, f.sons[i], x.sons[i]) <= isSubtype:
          # Workaround for regression #4589
          if f.sons[i].kind != tyTypeDesc: return
      result = isGeneric
    elif x.kind == tyGenericInst and isGenericSubtype(c, x, f, depth, f) and
          (sonsLen(x) - 1 == sonsLen(f)):
      # do not recurse here in order to not K bind twice for this code:
      #
      # type
      #   BaseFruit[T] = object of RootObj
      #   Banana[T] = object of BaseFruit[uint32] # Concrete type here, not T!
      # proc setColor[K](self: var BaseFruit[K])
      # var x: Banana[float64]
      # x.setColor()
      c.inheritancePenalty += depth
      result = isGeneric
    else:
      let genericBody = f.sons[0]
      var askip = skippedNone
      var fskip = skippedNone
      let aobj = x.skipToObject(askip)
      let fobj = genericBody.lastSon.skipToObject(fskip)
      var depth = -1
      if fobj != nil and aobj != nil and askip == fskip:
        depth = isObjectSubtype(c, aobj, fobj, f)
      result = typeRel(c, genericBody, x)
      if result != isNone:
        # see tests/generics/tgeneric3.nim for an example that triggers this
        # piece of code:
        #
        # proc internalFind[T,D](n: PNode[T,D], key: T): ref TItem[T,D]
        # proc internalPut[T,D](ANode: ref TNode[T,D], Akey: T, Avalue: D,
        #                       Oldvalue: var D): ref TNode[T,D]
        # var root = internalPut[int, int](nil, 312, 312, oldvalue)
        # var it1 = internalFind(root, 312) # cannot instantiate: 'D'
        #
        # we steal the generic parameters from the tyGenericBody:
        for i in 1 ..< sonsLen(f):
          let x = PType(idTableGet(c.bindings, genericBody.sons[i-1]))
          if x == nil:
            discard "maybe fine (for eg. a==tyNil)"
          elif x.kind in {tyGenericInvocation, tyGenericParam}:
            internalError(c.c.graph.config, "wrong instantiated type!")
          else:
            let key = f.sons[i]
            let old = PType(idTableGet(c.bindings, key))
            if old == nil:
              put(c, key, x)
            elif typeRel(c, old, x, flags + {trDontBind}) == isNone:
              return isNone

      if result == isNone:
        # Here object inheriting from generic/specialized generic object
        # crossing path with metatypes/aliases, so we need to separate them
        # by checking sym.id
        let genericSubtype = isGenericSubtype(c, x, f, depth, f)
        if not (genericSubtype and aobj.sym.id != fobj.sym.id) and aOrig.kind != tyGenericBody:
          depth = -1

      if depth >= 0:
        c.inheritancePenalty += depth
        # bug #4863: We still need to bind generic alias crap, so
        # we cannot return immediately:
        result = if depth == 0: isGeneric else: isSubtype
  of tyAnd:
    considerPreviousT:
      result = isEqual
      for branch in f.sons:
        let x = typeRel(c, branch, aOrig)
        if x < isSubtype: return isNone
        # 'and' implies minimum matching result:
        if x < result: result = x
      if result > isGeneric: result = isGeneric
      bindingRet result

  of tyOr:
    considerPreviousT:
      result = isNone
      let oldInheritancePenalty = c.inheritancePenalty
      var maxInheritance = 0
      for branch in f.sons:
        c.inheritancePenalty = 0
        let x = typeRel(c, branch, aOrig)
        maxInheritance = max(maxInheritance, c.inheritancePenalty)

        # 'or' implies maximum matching result:
        if x > result: result = x
      if result >= isSubtype:
        if result > isGeneric: result = isGeneric
        bindingRet result
      else:
        result = isNone
      c.inheritancePenalty = oldInheritancePenalty + maxInheritance

  of tyNot:
    considerPreviousT:
      for branch in f.sons:
        if typeRel(c, branch, aOrig) != isNone:
          return isNone

      bindingRet isGeneric

  of tyAnything:
    considerPreviousT:
      var concrete = concreteType(c, a)
      if concrete != nil and doBind:
        put(c, f, concrete)
      return isGeneric

  of tyBuiltInTypeClass:
    considerPreviousT:
      let targetKind = f.sons[0].kind
      let effectiveArgType = a.skipTypes({tyRange, tyGenericInst,
                                          tyBuiltInTypeClass, tyAlias, tySink, tyOwned})
      let typeClassMatches = targetKind == effectiveArgType.kind and
                             not effectiveArgType.isEmptyContainer
      if typeClassMatches or
        (targetKind in {tyProc, tyPointer} and effectiveArgType.kind == tyNil):
        put(c, f, a)
        return isGeneric
      else:
        return isNone

  of tyUserTypeClassInst, tyUserTypeClass:
    if f.isResolvedUserTypeClass:
      result = typeRel(c, f.lastSon, a)
    else:
      considerPreviousT:
        if aOrig == f: return isEqual
        var matched = matchUserTypeClass(c, f, aOrig)
        if matched != nil:
          bindConcreteTypeToUserTypeClass(matched, a)
          if doBind: put(c, f, matched)
          result = isGeneric
        else:
          result = isNone

  of tyCompositeTypeClass:
    considerPreviousT:
      let roota = a.skipGenericAlias
      let rootf = f.lastSon.skipGenericAlias
      if a.kind == tyGenericInst and roota.base == rootf.base:
        for i in 1 .. rootf.sonsLen-2:
          let ff = rootf.sons[i]
          let aa = roota.sons[i]
          result = typeRel(c, ff, aa)
          if result == isNone: return
          if ff.kind == tyRange and result != isEqual: return isNone
      else:
        result = typeRel(c, rootf.lastSon, a)
      if result != isNone:
        put(c, f, a)
        result = isGeneric

  of tyGenericParam:
    var x = PType(idTableGet(c.bindings, f))
    if x == nil:
      if c.callee.kind == tyGenericBody and
         f.kind == tyGenericParam and not c.typedescMatched:
        # XXX: The fact that generic types currently use tyGenericParam for
        # their parameters is really a misnomer. tyGenericParam means "match
        # any value" and what we need is "match any type", which can be encoded
        # by a tyTypeDesc params. Unfortunately, this requires more substantial
        # changes in semtypinst and elsewhere.
        if tfWildcard in a.flags:
          result = isGeneric
        elif a.kind == tyTypeDesc:
          if f.sonsLen == 0:
            result = isGeneric
          else:
            internalAssert c.c.graph.config, a.len > 0
            c.typedescMatched = true
            var aa = a
            while aa.kind in {tyTypeDesc, tyGenericParam} and aa.len > 0:
              aa = lastSon(aa)
            if aa.kind == tyGenericParam:
              return isGeneric
            result = typeRel(c, f.base, aa)
            if result > isGeneric: result = isGeneric
        elif c.isNoCall:
          if doBind:
            let concrete = concreteType(c, a, f)
            if concrete == nil: return isNone
            put(c, f, concrete)
          result = isGeneric
        else:
          result = isNone
      else:
        # check if 'T' has a constraint as in 'proc p[T: Constraint](x: T)'
        if f.sonsLen > 0 and f.sons[0].kind != tyNone:
          let oldInheritancePenalty = c.inheritancePenalty
          result = typeRel(c, f.sons[0], a, flags + {trDontBind})
          if doBind and result notin {isNone, isGeneric}:
            let concrete = concreteType(c, a, f)
            if concrete == nil: return isNone
            put(c, f, concrete)
          # bug #6526
          if result in {isEqual, isSubtype}:
            # 'T: Class' is a *better* match than just 'T'
            # but 'T: Subclass' is even better:
            c.inheritancePenalty = oldInheritancePenalty - c.inheritancePenalty -
                                  100 * ord(result == isEqual)
            result = isGeneric
        else:
          result = isGeneric

      if result == isGeneric:
        var concrete = a
        if tfWildcard in a.flags:
          a.sym.kind = skType
          a.flags.excl tfWildcard
        else:
          concrete = concreteType(c, a, f)
          if concrete == nil:
            return isNone
        if doBind:
          put(c, f, concrete)
      elif result > isGeneric:
        result = isGeneric
    elif a.kind == tyEmpty:
      result = isGeneric
    elif x.kind == tyGenericParam:
      result = isGeneric
    else:
      result = typeRel(c, x, a) # check if it fits
      if result > isGeneric: result = isGeneric
  of tyStatic:
    let prev = PType(idTableGet(c.bindings, f))
    if prev == nil:
      if aOrig.kind == tyStatic:
        if f.base.kind != tyNone:
          result = typeRel(c, f.base, a)
          if result != isNone and f.n != nil:
            if not exprStructuralEquivalent(f.n, aOrig.n):
              result = isNone
        else:
          result = isGeneric
        if result != isNone: put(c, f, aOrig)
      elif aOrig.n != nil and aOrig.n.typ != nil:
        result = if f.base.kind != tyNone: typeRel(c, f.lastSon, aOrig.n.typ)
                 else: isGeneric
        if result != isNone:
          var boundType = newTypeWithSons(c.c, tyStatic, @[aOrig.n.typ])
          boundType.n = aOrig.n
          put(c, f, boundType)
      else:
        result = isNone
    elif prev.kind == tyStatic:
      if aOrig.kind == tyStatic:
        result = typeRel(c, prev.lastSon, a)
        if result != isNone and prev.n != nil:
          if not exprStructuralEquivalent(prev.n, aOrig.n):
            result = isNone
      else: result = isNone
    else:
      # XXX endless recursion?
      #result = typeRel(c, prev, aOrig)
      result = isNone

  of tyInferred:
    let prev = f.previouslyInferred
    if prev != nil:
      result = typeRel(c, prev, a)
    else:
      result = typeRel(c, f.base, a)
      if result != isNone:
        c.inferredTypes.add f
        f.sons.add a

  of tyTypeDesc:
    var prev = PType(idTableGet(c.bindings, f))
    if prev == nil:
      # proc foo(T: typedesc, x: T)
      # when `f` is an unresolved typedesc, `a` could be any
      # type, so we should not perform this check earlier
      if a.kind != tyTypeDesc:
        if a.kind == tyGenericParam and tfWildcard in a.flags:
          # TODO: prevent `a` from matching as a wildcard again
          result = isGeneric
        else:
          result = isNone
      elif f.base.kind == tyNone:
        result = isGeneric
      else:
        result = typeRel(c, f.base, a.base)

      if result != isNone:
        put(c, f, a)
    else:
      if tfUnresolved in f.flags:
        result = typeRel(c, prev.base, a)
      elif a.kind == tyTypeDesc:
        result = typeRel(c, prev.base, a.base)
      else:
        result = isNone

  of tyTyped:
    if aOrig != nil:
      put(c, f, aOrig)
    result = isGeneric

  of tyProxy:
    result = isEqual

  of tyFromExpr:
    # fix the expression, so it contains the already instantiated types
    if f.n == nil or f.n.kind == nkEmpty: return isGeneric
    let reevaluated = tryResolvingStaticExpr(c, f.n)
    case reevaluated.typ.kind
    of tyTypeDesc:
      result = typeRel(c, a, reevaluated.typ.base)
    of tyStatic:
      result = typeRel(c, a, reevaluated.typ.base)
      if result != isNone and reevaluated.typ.n != nil:
        if not exprStructuralEquivalent(aOrig.n, reevaluated.typ.n):
          result = isNone
    else:
      localError(c.c.graph.config, f.n.info, "type expected")
      result = isNone

  of tyNone:
    if a.kind == tyNone: result = isEqual
  else:
    internalError c.c.graph.config, " unknown type kind " & $f.kind

when false:
  var nowDebug = false
  var dbgCount = 0

  proc typeRel(c: var TCandidate, f, aOrig: PType,
              flags: TTypeRelFlags = {}): TTypeRelation =
    if nowDebug:
      echo f, " <- ", aOrig
      inc dbgCount
      if dbgCount == 2:
        writeStackTrace()
    result = typeRelImpl(c, f, aOrig, flags)
    if nowDebug:
      echo f, " <- ", aOrig, " res ", result

proc cmpTypes*(c: PContext, f, a: PType): TTypeRelation =
  var m: TCandidate
  initCandidate(c, m, f)
  result = typeRel(m, f, a)

proc getInstantiatedType(c: PContext, arg: PNode, m: TCandidate,
                         f: PType): PType =
  result = PType(idTableGet(m.bindings, f))
  if result == nil:
    result = generateTypeInstance(c, m.bindings, arg, f)
  if result == nil:
    internalError(c.graph.config, arg.info, "getInstantiatedType")
    result = errorType(c)

proc implicitConv(kind: TNodeKind, f: PType, arg: PNode, m: TCandidate,
                  c: PContext): PNode =
  result = newNodeI(kind, arg.info)
  if containsGenericType(f):
    if not m.hasFauxMatch:
      result.typ = getInstantiatedType(c, arg, m, f)
    else:
      result.typ = errorType(c)
  else:
    result.typ = f
  if result.typ == nil: internalError(c.graph.config, arg.info, "implicitConv")
  addSon(result, c.graph.emptyNode)
  addSon(result, arg)

proc userConvMatch(c: PContext, m: var TCandidate, f, a: PType,
                   arg: PNode): PNode =
  result = nil
  for i in 0 ..< len(c.converters):
    var src = c.converters[i].typ.sons[1]
    var dest = c.converters[i].typ.sons[0]
    # for generic type converters we need to check 'src <- a' before
    # 'f <- dest' in order to not break the unification:
    # see tests/tgenericconverter:
    let srca = typeRel(m, src, a)
    if srca notin {isEqual, isGeneric, isSubtype}: continue

    # What's done below matches the logic in ``matchesAux``
    let constraint = c.converters[i].typ.n[1].sym.constraint
    if not constraint.isNil and not matchNodeKinds(constraint, arg):
      continue
    if src.kind in {tyVar, tyLent} and not arg.isLValue:
      continue

    let destIsGeneric = containsGenericType(dest)
    if destIsGeneric:
      dest = generateTypeInstance(c, m.bindings, arg, dest)
    let fdest = typeRel(m, f, dest)
    if fdest in {isEqual, isGeneric} and not (dest.kind == tyLent and f.kind == tyVar):
      markUsed(c.config, arg.info, c.converters[i], c.graph.usageSym)
      var s = newSymNode(c.converters[i])
      s.typ = c.converters[i].typ
      s.info = arg.info
      result = newNodeIT(nkHiddenCallConv, arg.info, dest)
      addSon(result, s)
      # We build the call expression by ourselves in order to avoid passing this
      # expression trough the semantic check phase once again so let's make sure
      # it is correct
      var param: PNode = nil
      if srca == isSubtype:
        param = implicitConv(nkHiddenSubConv, src, copyTree(arg), m, c)
      elif src.kind == tyVar:
        # Analyse the converter return type
        param = newNodeIT(nkHiddenAddr, arg.info, s.typ[1])
        param.addSon(copyTree(arg))
      else:
        param = copyTree(arg)
      addSon(result, param)

      if dest.kind in {tyVar, tyLent}:
        dest.flags.incl tfVarIsPtr
        result = newDeref(result)

      inc(m.convMatches)
      if not m.genericConverter:
        m.genericConverter = srca == isGeneric or destIsGeneric
      return result

proc localConvMatch(c: PContext, m: var TCandidate, f, a: PType,
                    arg: PNode): PNode =
  # arg.typ can be nil in 'suggest':
  if isNil(arg.typ): return nil

  # sem'checking for 'echo' needs to be re-entrant:
  # XXX we will revisit this issue after 0.10.2 is released
  if f == arg.typ and arg.kind == nkHiddenStdConv: return arg

  var call = newNodeI(nkCall, arg.info)
  call.add(f.n.copyTree)
  call.add(arg.copyTree)
  result = c.semExpr(c, call)
  if result != nil:
    if result.typ == nil: return nil
    # resulting type must be consistent with the other arguments:
    var r = typeRel(m, f.sons[0], result.typ)
    if r < isGeneric: return nil
    if result.kind == nkCall: result.kind = nkHiddenCallConv
    inc(m.convMatches)
    if r == isGeneric:
      result.typ = getInstantiatedType(c, arg, m, base(f))
    m.baseTypeMatch = true

proc incMatches(m: var TCandidate; r: TTypeRelation; convMatch = 1) =
  case r
  of isConvertible, isIntConv: inc(m.convMatches, convMatch)
  of isSubtype, isSubrange: inc(m.subtypeMatches)
  of isGeneric, isInferred, isBothMetaConvertible: inc(m.genericMatches)
  of isFromIntLit: inc(m.intConvMatches, 256)
  of isInferredConvertible:
    inc(m.convMatches)
  of isEqual: inc(m.exactMatches)
  of isNone: discard

template matchesVoidProc(t: PType): bool =
  (t.kind == tyProc and t.len == 1 and t.sons[0] == nil) or
    (t.kind == tyBuiltInTypeClass and t.sons[0].kind == tyProc)

proc paramTypesMatchAux(m: var TCandidate, f, a: PType,
                        argSemantized, argOrig: PNode): PNode =
  var
    fMaybeStatic = f.skipTypes({tyDistinct})
    arg = argSemantized
    a = a
    c = m.c

  if tfHasStatic in fMaybeStatic.flags:
    # XXX: When implicit statics are the default
    # this will be done earlier - we just have to
    # make sure that static types enter here

    # Zahary: weaken tyGenericParam and call it tyGenericPlaceholder
    # and finally start using tyTypedesc for generic types properly.
    # Araq: This would only shift the problems around, in 'proc p[T](x: T)'
    # the T is NOT a typedesc.
    if a.kind == tyGenericParam and tfWildcard in a.flags:
      a.assignType(f)
      # put(m.bindings, f, a)
      return argSemantized

    if a.kind == tyStatic:
      if m.callee.kind == tyGenericBody and
         a.n == nil and
         tfGenericTypeParam notin a.flags:
        return newNodeIT(nkType, argOrig.info, makeTypeFromExpr(c, arg))
    else:
      var evaluated = c.semTryConstExpr(c, arg)
      if evaluated != nil:
        # Don't build the type in-place because `evaluated` and `arg` may point
        # to the same object and we'd end up creating recursive types (#9255)
        let typ = newTypeS(tyStatic, c)
        typ.sons = @[evaluated.typ]
        typ.n = evaluated
        arg.typ = typ
        a = typ
      else:
        if m.callee.kind == tyGenericBody:
          if f.kind == tyStatic and typeRel(m, f.base, a) != isNone:
            result = makeStaticExpr(m.c, arg)
            result.typ.flags.incl tfUnresolved
            result.typ.n = arg
            return

  let oldInheritancePenalty = m.inheritancePenalty
  var r = typeRel(m, f, a)

  # This special typing rule for macros and templates is not documented
  # anywhere and breaks symmetry. It's hard to get rid of though, my
  # custom seqs example fails to compile without this:
  if r != isNone and m.calleeSym != nil and
    m.calleeSym.kind in {skMacro, skTemplate}:
    # XXX: duplicating this is ugly, but we cannot (!) move this
    # directly into typeRel using return-like templates
    incMatches(m, r)
    if f.kind == tyTyped:
      return arg
    elif f.kind == tyTypeDesc:
      return arg
    elif f.kind == tyStatic and arg.typ.n != nil:
      return arg.typ.n
    else:
      return argSemantized # argOrig

  # If r == isBothMetaConvertible then we rerun typeRel.
  # bothMetaCounter is for safety to avoid any infinite loop,
  #  I don't have any example when it is needed.
  # lastBindingsLenth is used to check whether m.bindings remains the same,
  #  because in that case there is no point in continuing.
  var bothMetaCounter = 0
  var lastBindingsLength = -1
  while r == isBothMetaConvertible and
      lastBindingsLength != m.bindings.counter and
      bothMetaCounter < 100:
    lastBindingsLength = m.bindings.counter
    inc(bothMetaCounter)
    if arg.kind in {nkProcDef, nkFuncDef, nkIteratorDef} + nkLambdaKinds:
      result = c.semInferredLambda(c, m.bindings, arg)
    elif arg.kind != nkSym:
      return nil
    else:
      let inferred = c.semGenerateInstance(c, arg.sym, m.bindings, arg.info)
      result = newSymNode(inferred, arg.info)
    inc(m.convMatches)
    arg = result
    r = typeRel(m, f, arg.typ)

  case r
  of isConvertible:
    inc(m.convMatches)
    result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  of isIntConv:
    # I'm too lazy to introduce another ``*matches`` field, so we conflate
    # ``isIntConv`` and ``isIntLit`` here:
    inc(m.intConvMatches)
    result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  of isSubtype:
    inc(m.subtypeMatches)
    if f.kind == tyTypeDesc:
      result = arg
    else:
      result = implicitConv(nkHiddenSubConv, f, arg, m, c)
  of isSubrange:
    inc(m.subtypeMatches)
    if f.kind == tyVar:
      result = arg
    else:
      result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  of isInferred, isInferredConvertible:
    if arg.kind in {nkProcDef, nkFuncDef, nkIteratorDef} + nkLambdaKinds:
      result = c.semInferredLambda(c, m.bindings, arg)
    elif arg.kind != nkSym:
      return nil
    else:
      let inferred = c.semGenerateInstance(c, arg.sym, m.bindings, arg.info)
      result = newSymNode(inferred, arg.info)
    if r == isInferredConvertible:
      inc(m.convMatches)
      result = implicitConv(nkHiddenStdConv, f, result, m, c)
    else:
      inc(m.genericMatches)
  of isGeneric:
    inc(m.genericMatches)
    if arg.typ == nil:
      result = arg
    elif skipTypes(arg.typ, abstractVar-{tyTypeDesc}).kind == tyTuple or
         m.inheritancePenalty > oldInheritancePenalty:
      result = implicitConv(nkHiddenSubConv, f, arg, m, c)
    elif arg.typ.isEmptyContainer:
      result = arg.copyTree
      result.typ = getInstantiatedType(c, arg, m, f)
    else:
      result = arg
  of isBothMetaConvertible:
    # This is the result for the 101th time.
    result = nil
  of isFromIntLit:
    # too lazy to introduce another ``*matches`` field, so we conflate
    # ``isIntConv`` and ``isIntLit`` here:
    inc(m.intConvMatches, 256)
    result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  of isEqual:
    inc(m.exactMatches)
    result = arg
    if skipTypes(f, abstractVar-{tyTypeDesc}).kind == tyTuple or
      (arg.typ != nil and skipTypes(arg.typ, abstractVar-{tyTypeDesc}).kind == tyTuple):
      result = implicitConv(nkHiddenSubConv, f, arg, m, c)
  of isNone:
    # do not do this in ``typeRel`` as it then can't infer T in ``ref T``:
    if a.kind in {tyProxy, tyUnknown}:
      inc(m.genericMatches)
      m.fauxMatch = a.kind
      return arg
    elif a.kind == tyVoid and f.matchesVoidProc and argOrig.kind == nkStmtList:
      # lift do blocks without params to lambdas
      let p = c.graph
      let lifted = c.semExpr(c, newProcNode(nkDo, argOrig.info, body = argOrig,
          params = p.emptyNode, name = p.emptyNode, pattern = p.emptyNode,
          genericParams = p.emptyNode, pragmas = p.emptyNode, exceptions = p.emptyNode), {})
      if f.kind == tyBuiltInTypeClass:
        inc m.genericMatches
        put(m, f, lifted.typ)
      inc m.convMatches
      return implicitConv(nkHiddenStdConv, f, lifted, m, c)
    result = userConvMatch(c, m, f, a, arg)
    # check for a base type match, which supports varargs[T] without []
    # constructor in a call:
    if result == nil and f.kind == tyVarargs:
      if f.n != nil:
        # Forward to the varargs converter
        result = localConvMatch(c, m, f, a, arg)
      else:
        r = typeRel(m, base(f), a)
        case r
        of isGeneric:
          inc(m.convMatches)
          result = copyTree(arg)
          result.typ = getInstantiatedType(c, arg, m, base(f))
          m.baseTypeMatch = true
        of isFromIntLit:
          inc(m.intConvMatches, 256)
          result = implicitConv(nkHiddenStdConv, f[0], arg, m, c)
          m.baseTypeMatch = true
        of isEqual:
          inc(m.convMatches)
          result = copyTree(arg)
          m.baseTypeMatch = true
        of isSubtype: # bug #4799, varargs accepting subtype relation object
          inc(m.subtypeMatches)
          if base(f).kind == tyTypeDesc:
            result = arg
          else:
            result = implicitConv(nkHiddenSubConv, base(f), arg, m, c)
          m.baseTypeMatch = true
        else:
          result = userConvMatch(c, m, base(f), a, arg)
          if result != nil: m.baseTypeMatch = true

proc paramTypesMatch*(m: var TCandidate, f, a: PType,
                      arg, argOrig: PNode): PNode =
  if arg == nil or arg.kind notin nkSymChoices:
    result = paramTypesMatchAux(m, f, a, arg, argOrig)
  else:
    # CAUTION: The order depends on the used hashing scheme. Thus it is
    # incorrect to simply use the first fitting match. However, to implement
    # this correctly is inefficient. We have to copy `m` here to be able to
    # roll back the side effects of the unification algorithm.
    let c = m.c
    var x, y, z: TCandidate
    initCandidate(c, x, m.callee)
    initCandidate(c, y, m.callee)
    initCandidate(c, z, m.callee)
    x.calleeSym = m.calleeSym
    y.calleeSym = m.calleeSym
    z.calleeSym = m.calleeSym
    var best = -1
    for i in 0 ..< arg.len:
      if arg.sons[i].sym.kind in {skProc, skFunc, skMethod, skConverter,
                                  skIterator, skMacro, skTemplate}:
        copyCandidate(z, m)
        z.callee = arg.sons[i].typ
        if tfUnresolved in z.callee.flags: continue
        z.calleeSym = arg.sons[i].sym
        #if arg.sons[i].sym.name.s == "cmp":
        #  ggDebug = true
        #  echo "CALLLEEEEEEEE A ", typeToString(z.callee)
        # XXX this is still all wrong: (T, T) should be 2 generic matches
        # and  (int, int) 2 exact matches, etc. Essentially you cannot call
        # typeRel here and expect things to work!
        let r = typeRel(z, f, arg.sons[i].typ)
        incMatches(z, r, 2)
        #if arg.sons[i].sym.name.s == "cmp": # and arg.info.line == 606:
        #  echo "M ", r, " ", arg.info, " ", typeToString(arg.sons[i].sym.typ)
        #  writeMatches(z)
        if r != isNone:
          z.state = csMatch
          case x.state
          of csEmpty, csNoMatch:
            x = z
            best = i
          of csMatch:
            let cmp = cmpCandidates(x, z)
            if cmp < 0:
              best = i
              x = z
            elif cmp == 0:
              y = z           # z is as good as x

    if x.state == csEmpty:
      result = nil
    elif y.state == csMatch and cmpCandidates(x, y) == 0:
      if x.state != csMatch:
        internalError(m.c.graph.config, arg.info, "x.state is not csMatch")
      # ambiguous: more than one symbol fits!
      # See tsymchoice_for_expr as an example. 'f.kind == tyUntyped' should match
      # anyway:
      if f.kind in {tyUntyped, tyTyped}: result = arg
      else: result = nil
    else:
      # only one valid interpretation found:
      markUsed(m.c.config, arg.info, arg.sons[best].sym, m.c.graph.usageSym)
      onUse(arg.info, arg.sons[best].sym)
      result = paramTypesMatchAux(m, f, arg.sons[best].typ, arg.sons[best],
                                  argOrig)
  when false:
    if m.calleeSym != nil and m.calleeSym.name.s == "[]":
      echo m.c.config $ arg.info, " for ", m.calleeSym.name.s, " ", m.c.config $ m.calleeSym.info
      writeMatches(m)

proc setSon(father: PNode, at: int, son: PNode) =
  let oldLen = father.len
  if oldLen <= at:
    setLen(father.sons, at + 1)
  father.sons[at] = son
  # insert potential 'void' parameters:
  #for i in oldLen ..< at:
  #  father.sons[i] = newNodeIT(nkEmpty, son.info, getSysType(tyVoid))

# we are allowed to modify the calling node in the 'prepare*' procs:
proc prepareOperand(c: PContext; formal: PType; a: PNode): PNode =
  if formal.kind == tyUntyped and formal.len != 1:
    # {tyTypeDesc, tyUntyped, tyTyped, tyProxy}:
    # a.typ == nil is valid
    result = a
  elif a.typ.isNil:
    # XXX This is unsound! 'formal' can differ from overloaded routine to
    # overloaded routine!
    let flags = {efDetermineType, efAllowStmt}
                #if formal.kind == tyIter: {efDetermineType, efWantIterator}
                #else: {efDetermineType, efAllowStmt}
                #elif formal.kind == tyTyped: {efDetermineType, efWantStmt}
                #else: {efDetermineType}
    result = c.semOperand(c, a, flags)
  else:
    result = a
    considerGenSyms(c, result)

proc prepareOperand(c: PContext; a: PNode): PNode =
  if a.typ.isNil:
    result = c.semOperand(c, a, {efDetermineType})
  else:
    result = a
    considerGenSyms(c, result)

proc prepareNamedParam(a: PNode; c: PContext) =
  if a.sons[0].kind != nkIdent:
    var info = a.sons[0].info
    a.sons[0] = newIdentNode(considerQuotedIdent(c, a.sons[0]), info)

proc arrayConstr(c: PContext, n: PNode): PType =
  result = newTypeS(tyArray, c)
  rawAddSon(result, makeRangeType(c, 0, 0, n.info))
  addSonSkipIntLit(result, skipTypes(n.typ,
      {tyGenericInst, tyVar, tyLent, tyOrdinal}))

proc arrayConstr(c: PContext, info: TLineInfo): PType =
  result = newTypeS(tyArray, c)
  rawAddSon(result, makeRangeType(c, 0, -1, info))
  rawAddSon(result, newTypeS(tyEmpty, c)) # needs an empty basetype!

proc incrIndexType(t: PType) =
  assert t.kind == tyArray
  inc t.sons[0].n.sons[1].intVal

template isVarargsUntyped(x): untyped =
  x.kind == tyVarargs and x.sons[0].kind == tyUntyped

proc matchesAux(c: PContext, n, nOrig: PNode,
                m: var TCandidate, marker: var IntSet) =
  template checkConstraint(n: untyped) {.dirty.} =
    if not formal.constraint.isNil:
      if matchNodeKinds(formal.constraint, n):
        # better match over other routines with no such restriction:
        inc(m.genericMatches, 100)
      else:
        m.state = csNoMatch
        return

    if formal.typ.kind == tyVar:
      let argConverter = if arg.kind == nkHiddenDeref: arg[0] else: arg
      if argConverter.kind == nkHiddenCallConv:
        if argConverter.typ.kind != tyVar:
          m.state = csNoMatch
          m.mutabilityProblem = uint8(f-1)
          return
      elif not n.isLValue:
        m.state = csNoMatch
        m.mutabilityProblem = uint8(f-1)
        return

  var
    # iterates over formal parameters
    f = if m.callee.kind != tyGenericBody: 1
        else: 0
    # iterates over the actual given arguments
    a = 1
    arg: PNode # current prepared argument

  m.state = csMatch # until proven otherwise
  m.call = newNodeI(n.kind, n.info)
  m.call.typ = base(m.callee) # may be nil
  var formalLen = m.callee.n.len
  addSon(m.call, copyTree(n.sons[0]))
  var container: PNode = nil # constructed container
  var formal: PSym = if formalLen > 1: m.callee.n.sons[1].sym else: nil

  while a < n.len:
    if a >= formalLen-1 and f < formalLen and m.callee.n[f].typ.isVarargsUntyped:
      formal = m.callee.n.sons[f].sym
      incl(marker, formal.position)

      if n.sons[a].kind == nkHiddenStdConv:
        doAssert n.sons[a].sons[0].kind == nkEmpty and
                 n.sons[a].sons[1].kind in {nkBracket, nkArgList}
        # Steal the container and pass it along
        setSon(m.call, formal.position + 1, n.sons[a].sons[1])
      else:
        if container.isNil:
          container = newNodeIT(nkArgList, n.sons[a].info, arrayConstr(c, n.info))
          setSon(m.call, formal.position + 1, container)
        else:
          incrIndexType(container.typ)
        addSon(container, n.sons[a])
    elif n.sons[a].kind == nkExprEqExpr:
      # named param
      # check if m.callee has such a param:
      prepareNamedParam(n.sons[a], c)
      if n.sons[a].sons[0].kind != nkIdent:
        localError(c.config, n.sons[a].info, "named parameter has to be an identifier")
        m.state = csNoMatch
        m.firstMismatch = -a
        return
      formal = getSymFromList(m.callee.n, n.sons[a].sons[0].ident, 1)
      if formal == nil:
        # no error message!
        m.state = csNoMatch
        m.firstMismatch = -a
        return
      if containsOrIncl(marker, formal.position):
        # already in namedParams, so no match
        # we used to produce 'errCannotBindXTwice' here but see
        # bug #3836 of why that is not sound (other overload with
        # different parameter names could match later on):
        when false: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s)
        m.state = csNoMatch
        return
      m.baseTypeMatch = false
      m.typedescMatched = false
      n.sons[a].sons[1] = prepareOperand(c, formal.typ, n.sons[a].sons[1])
      n.sons[a].typ = n.sons[a].sons[1].typ
      arg = paramTypesMatch(m, formal.typ, n.sons[a].typ,
                                n.sons[a].sons[1], n.sons[a].sons[1])
      if arg == nil:
        m.state = csNoMatch
        m.firstMismatch = a
        return
      checkConstraint(n.sons[a].sons[1])
      if m.baseTypeMatch:
        #assert(container == nil)
        container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg))
        addSon(container, arg)
        setSon(m.call, formal.position + 1, container)
        if f != formalLen - 1: container = nil
      else:
        setSon(m.call, formal.position + 1, arg)
      inc f
    else:
      # unnamed param
      if f >= formalLen:
        # too many arguments?
        if tfVarargs in m.callee.flags:
          # is ok... but don't increment any counters...
          # we have no formal here to snoop at:
          n.sons[a] = prepareOperand(c, n.sons[a])
          if skipTypes(n.sons[a].typ, abstractVar-{tyTypeDesc}).kind==tyString:
            addSon(m.call, implicitConv(nkHiddenStdConv,
                  getSysType(c.graph, n.sons[a].info, tyCString),
                  copyTree(n.sons[a]), m, c))
          else:
            addSon(m.call, copyTree(n.sons[a]))
        elif formal != nil and formal.typ.kind == tyVarargs:
          # beware of the side-effects in 'prepareOperand'! So only do it for
          # varargs matching. See tests/metatype/tstatic_overloading.
          m.baseTypeMatch = false
          m.typedescMatched = false
          incl(marker, formal.position)
          n.sons[a] = prepareOperand(c, formal.typ, n.sons[a])
          arg = paramTypesMatch(m, formal.typ, n.sons[a].typ,
                                    n.sons[a], nOrig.sons[a])
          if arg != nil and m.baseTypeMatch and container != nil:
            addSon(container, arg)
            incrIndexType(container.typ)
            checkConstraint(n.sons[a])
          else:
            m.state = csNoMatch
            return
        else:
          m.state = csNoMatch
          return
      else:
        if m.callee.n.sons[f].kind != nkSym:
          internalError(c.config, n.sons[a].info, "matches")
          return
        formal = m.callee.n.sons[f].sym
        if containsOrIncl(marker, formal.position) and container.isNil:
          # already in namedParams: (see above remark)
          when false: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s)
          m.state = csNoMatch
          return

        if formal.typ.isVarargsUntyped:
          if container.isNil:
            container = newNodeIT(nkArgList, n.sons[a].info, arrayConstr(c, n.info))
            setSon(m.call, formal.position + 1, container)
          else:
            incrIndexType(container.typ)
          addSon(container, n.sons[a])
        else:
          m.baseTypeMatch = false
          m.typedescMatched = false
          n.sons[a] = prepareOperand(c, formal.typ, n.sons[a])
          arg = paramTypesMatch(m, formal.typ, n.sons[a].typ,
                                    n.sons[a], nOrig.sons[a])
          if arg == nil:
            m.state = csNoMatch
            m.firstMismatch = f
            return
          if m.baseTypeMatch:
            assert formal.typ.kind == tyVarargs
            #assert(container == nil)
            if container.isNil:
              container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg))
              container.typ.flags.incl tfVarargs
            else:
              incrIndexType(container.typ)
            addSon(container, arg)
            setSon(m.call, formal.position + 1,
                   implicitConv(nkHiddenStdConv, formal.typ, container, m, c))
            #if f != formalLen - 1: container = nil

            # pick the formal from the end, so that 'x, y, varargs, z' works:
            f = max(f, formalLen - n.len + a + 1)
          elif formal.typ.kind != tyVarargs or container == nil:
            setSon(m.call, formal.position + 1, arg)
            inc(f)
            container = nil
          else:
            # we end up here if the argument can be converted into the varargs
            # formal (eg. seq[T] -> varargs[T]) but we have already instantiated
            # a container
            #assert arg.kind == nkHiddenStdConv # for 'nim check'
            # this assertion can be off
            localError(c.config, n.sons[a].info, "cannot convert $1 to $2" % [
              typeToString(n.sons[a].typ), typeToString(formal.typ) ])
            m.state = csNoMatch
            return
        checkConstraint(n.sons[a])
    inc(a)

proc semFinishOperands*(c: PContext, n: PNode) =
  # this needs to be called to ensure that after overloading resolution every
  # argument has been sem'checked:
  for i in 1 ..< n.len:
    n.sons[i] = prepareOperand(c, n.sons[i])

proc partialMatch*(c: PContext, n, nOrig: PNode, m: var TCandidate) =
  # for 'suggest' support:
  var marker = initIntSet()
  matchesAux(c, n, nOrig, m, marker)

proc matches*(c: PContext, n, nOrig: PNode, m: var TCandidate) =
  if m.magic in {mArrGet, mArrPut}:
    m.state = csMatch
    m.call = n
    # Note the following doesn't work as it would produce ambiguities.
    # Instead we patch system.nim, see bug #8049.
    when false:
      inc m.genericMatches
      inc m.exactMatches
    return
  var marker = initIntSet()
  matchesAux(c, n, nOrig, m, marker)
  if m.state == csNoMatch: return
  # check that every formal parameter got a value:
  var f = 1
  while f < sonsLen(m.callee.n):
    var formal = m.callee.n.sons[f].sym
    if not containsOrIncl(marker, formal.position):
      if formal.ast == nil:
        if formal.typ.kind == tyVarargs:
          # For consistency with what happens in `matchesAux` select the
          # container node kind accordingly
          let cnKind = if formal.typ.isVarargsUntyped: nkArgList else: nkBracket
          var container = newNodeIT(cnKind, n.info, arrayConstr(c, n.info))
          setSon(m.call, formal.position + 1,
                 implicitConv(nkHiddenStdConv, formal.typ, container, m, c))
        else:
          # no default value
          m.state = csNoMatch
          m.firstMismatch = f
          break
      else:
        if formal.ast.kind == nkEmpty:
          # The default param value is set to empty in `instantiateProcType`
          # when the type of the default expression doesn't match the type
          # of the instantiated proc param:
          localError(c.config, m.call.info,
                     ("The default parameter '$1' has incompatible type " &
                      "with the explicitly requested proc instantiation") %
                      formal.name.s)
        if nfDefaultRefsParam in formal.ast.flags:
          m.call.flags.incl nfDefaultRefsParam
        var def = copyTree(formal.ast)
        if def.kind == nkNilLit:
          def = implicitConv(nkHiddenStdConv, formal.typ, def, m, c)
        if {tfImplicitTypeParam, tfGenericTypeParam} * formal.typ.flags != {}:
          put(m, formal.typ, def.typ)
        def.flags.incl nfDefaultParam
        setSon(m.call, formal.position + 1, def)
    inc(f)
  # forget all inferred types if the overload matching failed
  if m.state == csNoMatch:
    for t in m.inferredTypes:
      if t.sonsLen > 1: t.sons.setLen 1

proc argtypeMatches*(c: PContext, f, a: PType, fromHlo = false): bool =
  var m: TCandidate
  initCandidate(c, m, f)
  let res = paramTypesMatch(m, f, a, c.graph.emptyNode, nil)
  #instantiateGenericConverters(c, res, m)
  # XXX this is used by patterns.nim too; I think it's better to not
  # instantiate generic converters for that
  if not fromHlo:
    res != nil
  else:
    # pattern templates do not allow for conversions except from int literal
    res != nil and m.convMatches == 0 and m.intConvMatches in [0, 256]

proc instTypeBoundOp*(c: PContext; dc: PSym; t: PType; info: TLineInfo;
                      op: TTypeAttachedOp; col: int): PSym {.procvar.} =
  var m: TCandidate
  initCandidate(c, m, dc.typ)
  if col >= dc.typ.len:
    localError(c.config, info, "cannot instantiate: '" & dc.name.s & "'")
    return nil
  var f = dc.typ.sons[col]

  if op == attachedDeepCopy:
    if f.kind in {tyRef, tyPtr}: f = f.lastSon
  else:
    if f.kind == tyVar: f = f.lastSon
  #if c.config.selectedGC == gcDestructors and f.kind == tySequence:
  # use the canonical type to access the =sink and =destroy etc.
  #  f = c.graph.sysTypes[tySequence]
  #echo "YUP_---------Formal ", typeToString(f, preferDesc), " real ", typeToString(t, preferDesc), " ", f.id, " ", t.id

  if typeRel(m, f, t) == isNone:
    localError(c.config, info, "cannot instantiate: '" & dc.name.s & "'")
  else:
    result = c.semGenerateInstance(c, dc, m.bindings, info)
    if op == attachedDeepCopy:
      assert sfFromGeneric in result.flags

include suggest

when not declared(tests):
  template tests(s: untyped) = discard

tests:
  var dummyOwner = newSym(skModule, getIdent("test_module"), nil, UnknownLineInfo())

  proc `|` (t1, t2: PType): PType =
    result = newType(tyOr, dummyOwner)
    result.rawAddSon(t1)
    result.rawAddSon(t2)

  proc `&` (t1, t2: PType): PType =
    result = newType(tyAnd, dummyOwner)
    result.rawAddSon(t1)
    result.rawAddSon(t2)

  proc `!` (t: PType): PType =
    result = newType(tyNot, dummyOwner)
    result.rawAddSon(t)

  proc seq(t: PType): PType =
    result = newType(tySequence, dummyOwner)
    result.rawAddSon(t)

  proc array(x: int, t: PType): PType =
    result = newType(tyArray, dummyOwner)

    var n = newNodeI(nkRange, UnknownLineInfo())
    addSon(n, newIntNode(nkIntLit, 0))
    addSon(n, newIntNode(nkIntLit, x))
    let range = newType(tyRange, dummyOwner)

    result.rawAddSon(range)
    result.rawAddSon(t)

  suite "type classes":
    let
      int = newType(tyInt, dummyOwner)
      float = newType(tyFloat, dummyOwner)
      string = newType(tyString, dummyOwner)
      ordinal = newType(tyOrdinal, dummyOwner)
      any = newType(tyAnything, dummyOwner)
      number = int | float

    var TFoo = newType(tyObject, dummyOwner)
    TFoo.sym = newSym(skType, getIdent"TFoo", dummyOwner, UnknownLineInfo())

    var T1 = newType(tyGenericParam, dummyOwner)
    T1.sym = newSym(skType, getIdent"T1", dummyOwner, UnknownLineInfo())
    T1.sym.position = 0

    var T2 = newType(tyGenericParam, dummyOwner)
    T2.sym = newSym(skType, getIdent"T2", dummyOwner, UnknownLineInfo())
    T2.sym.position = 1

    setup:
      var c: TCandidate
      initCandidate(nil, c, nil)

    template yes(x, y) =
      test astToStr(x) & " is " & astToStr(y):
        check typeRel(c, y, x) == isGeneric

    template no(x, y) =
      test astToStr(x) & " is not " & astToStr(y):
        check typeRel(c, y, x) == isNone

    yes seq(any), array(10, int) | seq(any)
    # Sure, seq[any] is directly included

    yes seq(int), seq(any)
    yes seq(int), seq(number)
    # Sure, the int sequence is certainly
    # part of the number sequences (and all sequences)

    no seq(any), seq(float)
    # Nope, seq[any] includes types that are not seq[float] (e.g. seq[int])

    yes seq(int|string), seq(any)
    # Sure

    yes seq(int&string), seq(any)
    # Again

    yes seq(int&string), seq(int)
    # A bit more complicated
    # seq[int&string] is not a real type, but it's analogous to
    # seq[Sortable and Iterable], which is certainly a subset of seq[Sortable]

    no seq(int|string), seq(int|float)
    # Nope, seq[string] is not included in not included in
    # the seq[int|float] set

    no seq(!(int|string)), seq(string)
    # A sequence that is neither seq[int] or seq[string]
    # is obviously not seq[string]

    no seq(!int), seq(number)
    # Now your head should start to hurt a bit
    # A sequence that is not seq[int] is not necessarily a number sequence
    # it could well be seq[string] for example

    yes seq(!(int|string)), seq(!string)
    # all sequnece types besides seq[int] and seq[string]
    # are subset of all sequence types that are not seq[string]

    no seq(!(int|string)), seq(!(string|TFoo))
    # Nope, seq[TFoo] is included in the first set, but not in the second

    no seq(!string), seq(!number)
    # Nope, seq[int] in included in the first set, but not in the second

    yes seq(!number), seq(any)
    yes seq(!int), seq(any)
    no seq(any), seq(!any)
    no seq(!int), seq(!any)

    yes int, ordinal
    no  string, ordinal