В ревизии 8169 я внес изменения в алгоритм разрешения перегрузок методов. Теперь (надеюсь) он справляется со всеми случаями перегрузки с которыми справился бы C#.

Суть изменений:

В процессе разрешения перегрузки может возникнуть ситуация когда в параметрах метода содержится код типы которого зависят от конкретной перегрузки.

Простой пример:

_ = orders.Select(o => (o, o.Details.Sum(d => d.Quantity))).Where((o, total) =>  total > 10);

Проблема в том, что методы Select и Where имеют по четыре перегрузки, а метод Sum вообще 40 (30 из которых, правда отбрасывалось оригинальным алгоритмом, но 10 все равно не хило).
Вот список перегрузок для Sum (привожу описание только для 10 методов):

  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, int]) : int;
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, Nullable[int]]) : Nullable[int];
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, long]) : long;
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, Nullable[long]]) : Nullable[long];
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, float]) : float;
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, Nullable[float]]) : Nullable[float];
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, double]) : double;
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, Nullable[double]]) : Nullable[double];
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, decimal]) : decimal;
  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, Nullable[decimal]]) : Nullable[decimal];

А вот список перегрузок для Select:

  Select[TSource, TResult](this source : IEnumerable[TSource], selector : Func[TSource, int, TResult]) : IEnumerable[TResult];
  Select[TSource, TResult](this source : IEnumerable[TSource], selector : Func[TSource, TResult]) : IEnumerable[TResult];

Проблема этих функций в том, что понять какую из них нужно использовать можно только если вычислить тип выражения передающегося во второй параметр (т.е. лямбды) — "d => d.Quantity". А вычислить его можно только если подставить это выражение в конкретный вариант перегрузки и попытаться его типизировать. Мы отчетливо видим, что первые параметры у перегрузок одинаковые, но компилятор не может видеть. Он обрабатывать все перегрузки исходя из того, что в них может различаться все от начала до конца.
Так вот, когда компилятор встречает код:

orders.Select(o => (o, o.Details.Sum(d => d.Quantity)))

Он сначала пытается типизировать параметры метода Select вне контекста какой либо из перегрузок. Но при этом он фактически не может вычислить никакие типы. Тип "o" не определен, а значит неизвестно что такое o.Details, стало быть неизвестно что такое o.Details.Sum, и естественно, что говорить о разрешении перегрузки Sum уже совсем не приходится.
Что же делает компилятор в таком случае? Он генерирует объекты отложеной типизации, а переменным назначает "свободные" переменные типа (которые потенциально могут соответствовать любому типу).
Таким образом мы получаем типизированное дерево следующего вида (псевдокод):

o : ? => (o, DelayedMemberAccess(DelayedMemberAccess(o.Details).Sum)(d : ? => DelayedMemberAccess(d.Quantity)))

В результате типом такого выражения становится свободная переменная типа (выражаемая визуально знаком "?").

При попытке типизации перегрузки ему в качестве ожидаемого типа передается "?" и стало быть все перегрузки становятся подходящими.

Я изменил алгоритм так чтобы в момент разрешения каждой перегрузки производилась спекулятивная попытка вычислить объекты отложенной типизации.
Вот как это происходит.
Компилятор берет перегрузку:

  Select[TSource, TResult](this source : IEnumerable[TSource], selector : Func[TSource, int, TResult]) : IEnumerable[TResult];

и начинает сопоставлять ей типы параметров.
Сначала он сопоставляет первый аргумент (его тип взятый из формального описания и тип выражения в него подставленного). Это объект orders тип которого IEnumerable[Orders].
Теперь компилятор может сделать вывод, что тип TSource равен Order.
Теперь компилятор сопоставляет типы для второго аргумента. Хотя он уже знает, что первый параметр имеет тип Order, и что лябда переданная в качестве параметра имеет один аргумент, но этот аргумент ведь может быть кортежем Order * int. Так что отбросить этот метод сразу нельзя. Тело же хранит недотипизированное выражение о котором можно с уверенностью сказать только то, что оно возвращает кортеж состоящий из первого параметра функции и чего-то недотипизированного.
На этом исходный алгоритм Немерла и заканчивал свою работу сообщая нам, что возникла неоднозначность и требуется вручную указать типы.
Мое первое изменение

Автор: VladD2
Дата: 18.11.08

решало эту проблему за счет введения эвристики предпочитающей (в случае неоднозначности) структурно более близкий тип. В данном случае он отвергал рассматриваемую перегрузку в пользу второй, так как у нее тип был структурно ближе.
Однако эта эвристика оказалась неспособна решить более сложную проблему возникающую при вложенных лямбдах, как в примере продемонстрированном в начале этого сообщения. Даже выбрав вторую перегрузку для метода Select:

  Select[TSource, TResult](this source : IEnumerable[TSource], selector : Func[TSource, TResult]) : IEnumerable[TResult];

компилятор бы неспособен разрешить перегрузку для функции Sum, так как тип лямбды передаваемой в ее параметр нельзя установить в следствии того, что все ее подвыражения являются объектами отложенной типизации и имеют тип "?".

По новой стратегия после сопоставления типов выражений и параметров производится поиск вложенных в выражения объектов отложенной типизации, и если таковые существуют, им предлагается попытаться вычислить (разрешить отложенную типизацию). В отличии от принятого ранее сценария, сопоставление типов параметра и выражения делает известным часть типов этого выражения (в данном случае становится известным тип параметра "o" — Order). Это приводит к тому, что сначала получается разрешить тип для DelayedMemberAccess(o.Details) — у объекта типа Order есть только один член типа Details (это свойство). Вычисление типа o.Details делает возможным вычислить тип и для DelayedMemberAccess(o.Details.Sum). Тут все оказывается несколько сложнее, так как Sum имеет 10 перегрузок (отфильтрованных из 40) выбрать из которых можно только зная тип выражения передаваемого в качестве параметра этой функции. Но теперь мы знаем тип передаваемый в первый параметр — IEnumerable[Detail] — так как это тип свойства Details. Это позволяет вычислить тип для выражения DelayedMemberAccess(d.Quantity) — double. В свою очередь это позволят выбрать подходящую перегрузку функции Sum:

  Sum[TSource](this source : IEnumerable[TSource], selector : Func[TSource, double]) : double;

Попытки типизации других вариантов перегрузок терпят неудачу и мы получаем информацию о том какие из перегрузок можно использовать.

Все эти действия носят спекулятивный характер. Реально производится множество попыток типизации в надежде, что какие-то из них пройдут. Их цель только лишь отбраковать перегрузки которые ни при каких условиях не могут быть использованы.

Когда остается только один вариант перегрузки исходный алгоритм Немерле позволяет успешно закончить компиляцию.

В итоге мы получаем очень близкий по возможностям к C# алгоритм выбора перегрузки методов совместимый с отложенным выводом типов Немерле.

По началу я боялся, что рекурсивные спекулятивные вычисления отложенной типизации могут существенно замедлить работу компилятора. Однако на поверку оказалось, что скорость замедлилась совсем незначительно. Так до внесения изменений компилятор собирал сам себя за 1 минуту 34 секунд (на Core 2 Duo 2.5 Ггц — ноутбук). После приблизительно за 1 минуту 43 секунды. Однако код компилятора просто не содержит перегрузок с которыми борется расширенный алгоритм. Код, например, изобилующих "LINQ-запросами" может компилироваться существенно медленнее. Однако учитывая, что множественная вложенность функций редка, я думаю, что на практике время компиляции все же будет приемлемым. Ко всему прочему остается простор для оптимизаций. В том же LINQ массивно перегруженные функции подчиняются довольно простым правилам. Большинство перегрузок имеют сходные первые параметры, так что потенциально можно проверять частный случай и вычислять типы выражений передаваемых в качестве параметров не для каждой перегрузки по отдельности, а скопом. Ведь если, скажем, для Sum сопоставить тип первого параметра (который совпадает у всех вариантов перегрузки), то тип второго выражения можно будет вычислить без всяких спекуляций, за один проход. Далее придется только сопоставить тип второго выражения с типом второго параметра и отбросить все не совпадающие варианты. Таким образом потенциально можно сделать линейное вычисление перегрузки для частных случаев (которые так часто встречаются в ООП-библиотеках).