Overload resolution on generic method doesn't work as expected

Question

Last year I asked how to traverse and print jagged arrays, without having to write an overloaded function for each dimension that gets added. Generic printing of jagged arrays.
I picked up the problem again and was able to solve it like this. It is similar to one of the answers I got, but not quite the same.

static string Print<T>(T[] array)
{
    string str = "[ ";

    for (int i = 0; i < array.Length; i++)
    {
        str += array[i];
        if (i < array.Length - 1)
            str += ", ";
    }

    return str + " ]\n";
}

static string Print<T>(T[][] array)
{
    string str = "";

    for (int i = 0; i < array.Length; i++)
    {
        var sub = array[i];

        if (sub.Length != 0 && sub[0] is Array)
            str += PrintDynamic(sub);
        else
            str += Print(sub);
    }

    return str + "\n";
}

private static string PrintDynamic(dynamic array)
{
    return Print(array);
}

It works fine and I get the correct output:

var twoDim = new int[][]
{ 
    new int[] { 0, 1, 2, 3 },
    new int[] { 0, 1, 2 },
    new int[] { 0 }
};
var threeDim = new int[][][] { twoDim, twoDim }

Console.WriteLine(Print(threeDim));
// Output:
// [ 0, 1, 2, 3]
// [ 0, 1, 2]
// [ 0 ]
// 
// [ 0, 1, 2, 3]
// [ 0, 1, 2]
// [ 0 ]

But I'm still not satisfied, because it would be a lot nicer if I didnt't need PrintDynamic() and if I could just write

str += Print(sub);

instead of

str += PrintDynamic(sub);

That's where my question comes from. If I change that one line, I do not get any errors, but the output becomes

// [ System.Int32[], System.Int32[], System.Int32[], System.Int32[]]
// [ System.Int32[], System.Int32[], System.Int32[]]
// [ System.Int32[] ]
// 
// [ System.Int32[], System.Int32[], System.Int32[], System.Int32[]]
// [ System.Int32[], System.Int32[], System.Int32[]]
// [ System.Int32[] ]

because Print<T>(T[] array) gets called instead of Print<T>(T[][] array). How does the compiler know which Print<T>() to use, when it's called from PrintDynamic(dynamic array), but doesn't when it's called from within Print<T>()?

In short - the compiler doesn't know in the case of `dynamic`. The DLR resolves it at runtime using reflection. — Baldrick, Jun 19 '18 at 12:47
So even though `Print(T[][] array)` accepts jagged arrays of more than 2 dimensions as a parameter, it will still think that `array[i]` is always a 1 dimensional array and therefore the compiler will always call `Print(T[] array)`? So which of the 2 methods is called is not really resolved at runtime? — Alexander Moser, Jun 19 '18 at 12:56
@AlexanderMoser: Yep, I've explained with a second answer, which properly describes why your code behaves that way. — Baldrick, Jun 19 '18 at 13:10

Baldrick · Accepted Answer · 2018-06-19T13:22:49.647

To answer your original question. When you call:

str += Print(sub)

and the original object for the method was int[][][], then the <T> for the method is int[]. So you are calling Print(sub) with T[], where T is int[].

Therefore, the T[] overload of Print is selected, with T as int[] - and everything follows as expected. This is compile time resolved, and is the best the compiler can do with the information it has.

Remember, a generic method is only compiled to IL once - you don't get 'different versions' for different ways it happens to be called (unlike with C++ templates). The generic method's behaviour must be valid for all possible inputs. So if the method receives T[][], and you extract sub-elements internally, it can only consider the sub-object type to be T[]. It can't detect at runtime that 'oh, actually, T is an int[], so I'll call a different overload'. The method will only ever call the T[] overload of Print(sub), no matter what the input.

However, in the case where you use dynamic, you're ignoring all the generic type information baked in at compile time, and saying 'what is this type actually NOW, at runtime, using reflection. Which method is the best match now? Use that one!'. This behaviour has a significant overhead, and therefore must be explicitly requested by using the dynamic keyword.

score 0 · Answer 2 · answered Jun 14 '18 at 13:35

"How does the compiler know which Print() to use, when it's called from PrintDynamic(dynamic array)"

The answer is virtual function tables. Since you are working with C#, all types inherit from the class "object". A simple call to Print() attempts to print the objects themselves and not their content. Why? Because the ToString() method is called for the object since a more appropriate method has not been overloaded. Whenever you're working with strongly typed OOP languages such as C#, each object is a pointer to it's data structure (generally on the heap), and the first entry of this data structure is a pointer to the virtual function table for that object. A virtual function table is essentially an array of function pointers for each respective function that the class supports. Since by calling PrintDynamic you are actually passing the pointer of your object, the resolution of your object's pointer maps back to the virtual function table of its class. Then, the appropriate overloaded functions can be called. This is a high level description of the process. The concept is similar in languages such as C++. I hope this helps you understand a bit more about what the compiler is actually doing behind the scenes. I'd recommend some academic reading or perhaps the following link for some more details.

https://en.wikipedia.org/wiki/Virtual_method_table

I think I get how the function pointer and virtual function table work now, thanks. But I still dont get why the function 'Print(T[] array)' is chosen over 'Print(T[][] array)', when I call Print(array) from inside, but not if I call it from 'PrintDynamic()'? — Alexander Moser, Jun 14 '18 at 14:49

Baldrick · Answer 3 · 2018-06-14T14:32:34.850

If I were you, as this is a problem that can't really be resolved at compile time for arbitrary dimensions, I'd avoid using generics altogether:

public static string Print(Array array)
{
    string str = "[ ";
    for (int i = 0; i < array.Length; i++)
    {
        var element = array.GetValue(i);

        if (element is Array)
            str += Print(element as Array);
        else
        {
            str += element;
            if (i < array.Length - 1)
                str += ", ";
        }
    }

    return str + " ]";
}

This produces nested output, which I think is nicer, and it will nest arbitrarily as the depth increases.

[ [ [ 0, 1, 2, 3 ][ 0, 1, 2 ][ 0 ] ][ [ 0, 1, 2, 3 ][ 0, 1, 2 ][ 0 ] ] ]

Thanks for the answer. While this is a nice way to solve my previous problem, it unfortunately doesn't satisfy my curiosity of why the program doesn't behave the way I expected it to. — Alexander Moser, Jun 19 '18 at 12:32

Overload resolution on generic method doesn't work as expected

3 Answers3