copy-down-method causes incorrect selection

[pedro-w]

This was found when looking at method selection in the implementation of map-into. The following is a simplified example; it may not be minimal. Given the class hierarchy:

  <c>
  / \
<s> <x>
 |
<l>

and methods defined on

define generic m(a :: <c>, b :: <c>);

define method m(a :: <c>, b :: <c>) ... end;
define method m(a :: <c>, b :: <s>) ... end;
define method m(a :: <s>, b :: <c>) ... end;

called with args of type (<x>, <l>), then the method selected is m(a :: <c>, b :: <s>), as expected. If a copy-down method is added on (a :: <c>, b :: <l>) then the method selected is m(a :: <s>, b :: <c>) which is wrong, since <x> is not a subclass of <s>

[pedro-w]

Note: I am not 100% sure what copy-down-method does. In my understanding, if you add one, it looks at the signature at compile time and finds the specific method that would have been called, then it copies the body of that method as if you had defined it there. The compiler can then apply more optimizations as it has more specific arg types to work with.

[pedro-w]

Example code (needs \copy-down-method-definer importing from module dylan-extensions of library dylan)

define class <c> (<object>)
end;

define class <s> (<c>)
end;

define class <x> (<c>)
end;

define class <l> (<s>)
end;

define generic without-cd(a :: <c>, b :: <c>);

define method without-cd(a :: <c>, b :: <c>);
  format-out("<c>, <c>\n");
end;

define method without-cd(a :: <c>, b :: <s>)
  format-out("<c>, <s>\n");
end;

define method without-cd(a :: <s>, b :: <c>)
  format-out("<s>, <c>\n");
end;

define generic with-cd(a :: <c>, b :: <c>);

define method with-cd(a :: <c>, b :: <c>);
  format-out("<c>, <c>\n");
end;

define method with-cd(a :: <c>, b :: <s>)
  format-out("<c>, <s>\n");
end;

define method with-cd(a :: <s>, b :: <c>)
  format-out("<s>, <c>\n");
end;

define copy-down-method with-cd(a :: <c>, b :: <l>);

define function main
    (name :: <string>, arguments :: <vector>)
  let a0 = make(<x>);
  let a1 = make(<l>);
  let (sorted, unsorted) = sorted-applicable-methods(without-cd, a0, a1);
  format-out("Without copy down\nSorted: %s\nUnsorted: %s\nInvocation: ", sorted, unsorted);  
  without-cd(a0, a1); 
  let (sorted, unsorted) = sorted-applicable-methods(with-cd, a0, a1);
  format-out("\n\nWith copy down\nSorted: %s\nUnsorted: %s\nInvocation: ", sorted, unsorted);  
  with-cd(a0, a1); 
  exit-application(0);
end function main;

main(application-name(), application-arguments());

Compiler gives this warning (which I think may be wrong, there is no ambiguity)

Warning - Multiple applicable copy-down methods for method with-cd (a :: <c>, b :: <l>, #next next-method :: <object>) => (#rest results :: <object>), picking one at random
      ---------------------------------------------------
      define copy-down-method with-cd(a :: <c>, b :: <l>);
      ---------------------------------------------------

and running it gives

Without copy down
Sorted: #({method (<c>, <s>) => (#rest)}, {method (<c>, <c>) => (#rest)})
Unsorted: #()
Invocation: <c>, <s>

With copy down
Sorted: #({method (<c>, <l>) => (#rest)}, {method (<c>, <s>) => (#rest)}, {method (<c>, <c>) => (#rest)})
Unsorted: #()
Invocation: <s>, <c>

Note that sorted-applicable-methods seems to give the correct output but the method invoked is wrong.

[pedro-w]

Also when compiling the standard libraries, there are quite a few warnings relating to copy-down methods. I haven't looked to see if they are also spurious, but it suggests this issue does affect 'actual code'.

[cgay]

This won't be much help, but I have distant memories of the compiler folks at Harlequin talking about copy-down methods as a hack that really shouldn't need to exist.

[pedro-w]

Are any of them still around to ask? (they'd need long memories!) There's a name 'markt' next to the code. If I'm right, the copy-down-method calls could be removed without loss of functionality, it would just be a bit less optimized. Or there may be a simple fix; I haven't looked in detail yet.

[pedro-w]

The DFM file for those skilled in the art:

METHOD main (name :: <string>, arguments :: <vector>) => (#rest results)
  {{ a0 }} := [CONGRUENT-CALLg ^{<&generic> make}(^{<&class> <x>}, ^#[])]
  {{ a1 }} := [CONGRUENT-CALLg ^{<&generic> make}(^{<&class> <l>}, ^#[])]
  Vt15 := [STACK-VECTOR ({{ a0 }}, {{ a1 }})]
  *t16(2) := [METHOD-CALLi ^{<&method> sorted-applicable-methods (<generic-function>)}(^{<&generic> without-cd}, Vt15)]
  {{ sorted }} := *t16(2) [0]
  {{ unsorted }} := *t16(2) [1]
  Vt15 := [STACK-VECTOR ({{ sorted }}, {{ unsorted }})]
  [CONGRUENT-CALLi ^{<&method> format-out (<string>)}(^"Without copy down\nSorted: %s\nUnsorted: %s\nInvocation: ", Vt15)]
  [METHOD-CALLi ^{<&method> without-cd (<c>, <s>)}({{ a0 }}, {{ a1 }})]
  Vt16 := [STACK-VECTOR ({{ a0 }}, {{ a1 }})]
  *t17(2) := [METHOD-CALLi ^{<&method> sorted-applicable-methods (<generic-function>)}(^{<&generic> with-cd}, Vt16)]
  {{ sorted }} := *t17(2) [0]
  {{ unsorted }} := *t17(2) [1]
  Vt16 := [STACK-VECTOR ({{ sorted }}, {{ unsorted }})]
  [CONGRUENT-CALLi ^{<&method> format-out (<string>)}(^"\n\nWith copy down\nSorted: %s\nUnsorted: %s\nInvocation: ", Vt16)]
  [METHOD-CALLi ^{<&method> with-cd (<c>, <l>)}({{ a0 }}, {{ a1 }})]
  *t13(0,#rest) := [CONGRUENT-CALLi ^{<&method> exit-application (<integer>)}(^0)] // tail call
  return *t13(0,#rest)
END

It looks correct at this point - already selected an internal call to ^{<&method> with-cd (<c>, <l>)}

[pedro-w]

After a bit of poking in dfmc/optimizations/inlining.dylan and dispatch.dylan the logic seems to be:

• Gather all specialisations of the G.F.
• Filter out any that are definitely more specific than the argument types given
• Attempt to partition them into the ordered and unordered sets (same as runtime dispatch)
• If there's anything in the ordered sequence, copy down its first element
• Otherwise show the warning and pick one from the unordered set

So in this example the presence of the (<s>, <c>) specialisation causes the partitioning to throw everything into the unordered set (because it's ambiguous with (<c>, <s>)) - so there's nothing in the ordered sequence.

But (here I am getting a bit confused) - shouldn't the filter first take out any methods that aren't applicable to the argument type that were given to copy-down-method ? (here (<c>,<l>) , which would remove (<s>, <c>) from contention).

Any thoughts welcome.

[pedro-w]

I'm trying this:

diff --git a/sources/dfmc/optimization/inlining.dylan b/sources/dfmc/optimization/inlining.dylan
index c7379f5b..7b92f789 100644
--- a/sources/dfmc/optimization/inlining.dylan
+++ b/sources/dfmc/optimization/inlining.dylan
@@ -311,13 +311,12 @@ define method find-copy-downable-methods
          source-location: m.model-source-location);
   end;
   // Lose all methods that are known statically always to be more
-  // specific than ourselves, leaving only methods known to be
-  // less specific and those that are potentially more or less
-  // specific.
+  // specific than ourselves and those that are potentially more or less
+  // specific, leaving only methods known to be less specific.
   let methods
     = choose(method (them :: <&method>)
                them == m
-                 | ~guaranteed-method-precedes?(them, m, req-te*)
+                 | guaranteed-method-precedes?(m, them, req-te*)
              end method,
              methods-known);
   guaranteed-sorted-applicable-methods(methods, req-te*);

In other words excluding methods which might or might not be less specific. The function modified is only used in copy-down method processing so shouldn't have side-effects elsewhere.

[cgay]

Sadly, I think it's safe to assume no one who worked on the Harlequin Dylan compiler is going to be much help these days.

FWIW, if your fix above doesn't work out, I think getting rid of those warnings in exchange for a small slow-down would be a good exchange. Might be interesting to measure the difference in any case.

[pedro-w]

The above patch does remove some of the warnings but not all. It seems, in the remaining cases, that find-copy-downable-methods is still including methods that are not applicable in its analysis, and this results in a set of methods that can't always be ordered. I've got a new implementation of the criteria

--- a/sources/dfmc/optimization/inlining.dylan
+++ b/sources/dfmc/optimization/inlining.dylan
@@ -310,15 +310,16 @@ define method find-copy-downable-methods
          meth: m,
          source-location: m.model-source-location);
   end;
-  // Lose all methods that are known statically always to be more
-  // specific than ourselves and those that are potentially more or less
-  // specific, leaving only methods known to be less specific.
+  // Keep only 'real' methods whose specializers are all less specific than this one.
+  local method applicable?(candidate :: <&method>) => (well? :: <boolean>)
+          ~instance?(candidate, <&copy-down-method>) &
+            every?(guaranteed-preceding-specializer?,
+                   ^function-specializers(m),
+                   ^function-specializers(candidate),
+                   req-te*)
+        end;
   let methods
-    = choose(method (them :: <&method>)
-               them == m
-                 | guaranteed-method-precedes?(m, them, req-te*)
-             end method,
-             methods-known);
+    = choose(applicable?, methods-known);
   guaranteed-sorted-applicable-methods(methods, req-te*);
 end method;

which seems to remove almost all warnings, the ones that remain come from some methods specializing on <infinite-range> - here I think the copy-down was not used for optimization but to ensure that (for example) map with an infinite source calls a method which raises a condition rather than running forever. Example: https://github.com/dylan-lang/opendylan/blob/52898040d76a70b41c70980595af389ae73c7dbc/sources/dylan/range.dylan#L889-L901 AFAICS there are no adverse effects on test-fails or performance but will need to check more thoroughly.