2022-12-11

Intertwine

The Intertwine Logo, by michael.gr

Abstract

A mechanism is described for automatically converting method invocations of any programmatic interface into a single-method normal form and converting back to invocations of the original interface, so that general-purpose operations can be performed on the normal form without explicit knowledge of the interface being invoked. Implementations are provided for C# and for Java.

(Useful pre-reading: About these papers)

The Problem

When creating software systems of nontrivial complexity we often need to be able to apply certain operations on the invocations that are being made between components of the system. Examples of such operations are:

  • Desynchronization: Queuing invocations for later execution, possibly on a different thread.
  • Synchronization: Obtaining and holding a lock for the duration of the invocation.
  • Remoting: Placing invocations across machine boundaries.
  • Transformation: Converting between invocation formats, e.g. method calls to REST and back.
  • Logging: Recording information about each invocation being made.
  • Multicasting: Delivering a single invocation to multiple recipients.

Ordinarily, the components doing the invocations are application-specific, and so the interfaces between them are application-specific, but the operators that we want to interject between them are general-purpose, so they need to remain agnostic of the application-specific details of the invocations, in a way analogous to how general-purpose sorting algorithms are agnostic of the application-specific format of the data that they sort.

Therefore, we need some way of expressing application-specific invocations in a general-purpose form, so that general-purpose operators can act upon the invocations.

Prior Art

  • Messages and message-passing: The mechanism historically used for expressing invocations in a general-purpose form is message-passing. Unfortunately, its use is extremely laborious, and it floods systems with debilitating amounts of incidental complexity. For more information, see michael.gr - On messages and message-passing.
  • Parameterless lambdas: Application-specific method calls can be wrapped inside parameterless lambdas, and since all parameterless lambdas look the same, they can be handled by general-purpose code which may for example add them to a queue, and later dequeue and invoke them. Unfortunately:
    • The wrapping of each application-specific method call inside a parameterless lambda must happen at each call site, which is cumbersome and reveals details about the underlying invocation delivery mechanism.
    • The evaluation of the parameters that are passed to the application-specific method happens at the moment that the lambda makes the call, not at the moment that the lambda is constructed, which can lead to insidious bugs even if the evaluations have no side-effects. (And woe to you on earth and sea if they do have side-effects.)
    • The parameterless lambda completely hides the values of the parameters that are being passed to the application-specific method, as well as the identity of the method itself. Thus, parameterless lambdas cannot be used in scenarios that require information about each call being made.

  • Dynamic Proxies: Both in Java and in C# there exist mechanisms that can be used to convert application-specific invocations to a general-purpose form, but not the other way around. These are java.lang.reflect.Proxy for Java, and various libraries like Castle's and LinFu for C#. The reverse operation can be achieved using reflection, but this involves a round-trip to native-land, which incurs a heavy performance penalty. Furthermore, these mechanisms suffer from additional issues, such as messing with exceptions, doing more work than necessary, etc.

The Solution

In order to be able to perform general-purpose operations on application-specific invocations we need a mechanism for converting application-specific invocations into a general-purpose form and back, so that the operators can act upon the general-purpose form. What follows is a description of such a mechanism, which I call Intertwine.

Intertwine introduces a general-purpose form for expressing invocations, which is called the normal form of invocations, and is represented by a single method of the following signature:

    Object AnyCall( MethodKey key, Object[] arguments );

  • In C#, AnyCall would be a delegate.
  • In Java, AnyCall would be a single-method interface, otherwise known as a functional interface.

This method signature represents the fact that every conceivable interface method call can be fully described in terms of:

  • A return value, of the common denominator type ‘Object’.
  • A unique key which identifies which method of the interface is being invoked.
  • An array containing arguments, of the common denominator type ‘Object’.

Please note that the method identifier is `MethodKey` in the Java implementation, but `int selector` in the C# implementation. This is because the Java implementation was made a considerable time after the C# implementation, and is therefore significantly more advanced.

The `MethodKey` used in the Java implementation allows the caller and the callee to unambiguously identify methods even in situations where binary compatibility between the caller and the callee is not guaranteed, and therefore an integer method index does not necessarily refer to the same method on both the caller and the callee.

The Java implementation of intertwine provides efficient means of converting back and forth between a `MethodKey` and any of the following:

  • The reflection "Method" object of the method. (This is `java.lang.reflect.Method` in Java, or System.Reflection.MethodInfo in C#.)
  • The string representation of the prototype of the method.
  • The zero-based method index of the method.

The sample code that follows was written for C#, so it uses an `int selector` instead of `MethodKey key`.

Note:

  • For methods of `void` return type the value returned by AnyCall is unspecified. (It will in all likelihood be `null`, but nobody should rely on this.)
  • Value types (primitives) are boxed and unboxed as necessary.
  • Certain features such as the `ref` and `out` parameters in C#, receive special handling.
  • Other features such as properties, indexers, virtual events, etc. are nothing but syntactic sugar which is implemented using regular method calls under the hood, so they require no special handling.

So, the problem can now be restated as follows:

How to convert any interface method invocation to an invocation of an AnyCall method, and how to convert back from an invocation of an AnyCall method to an invocation of the original interface method.

For this, Intertwine introduces two new concepts: Entwiners and Untwiners.

  • An Entwiner of interface T is a class which exposes (implements) interface T and delegates to an instance of AnyCall. It can also be thought of as a normalizer or generalizer or multiplexer.
  • An Untwiner of interface T is a class which exposes an AnyCall method and delegates to an instance of T. It can also be thought of as a denormalizer or specializer or demultiplexer.

More specifically:

  • The entwiner of T does the following:
    • Accepts an instance of `Anycall` as a constructor parameter and stores it in `final` field `exitPoint`.
    • Implements each method of T as follows:
      • Packs the parameters that were passed to the method into an array of `Object`, performing any boxing necessary.
      • Invokes `exitPoint` passing it a key that uniquely identifies the method, and the array of parameters.
      • Returns, possibly after unboxing, whatever was returned by the invocation of `exitPoint`.
  • The untwiner of T performs the opposite and complementary operation of the entwiner, namely:
    • Accepts an instance of T as a constructor parameter and stores it in `final` field `exitPoint`.
    • Implements the `anycall` method of the `Anycall` interface as follows:
    • It uses the supplied `MethodKey` to determine which method of T is being invoked, and for each method it does the following:
      • Unpacks the parameters from the array of `Object`, performing any unboxing necessary.
      • Invokes the corresponding method of `exitPoint`, passing it the unpacked parameters.
      • Returns, possibly after boxing, whatever was returned by the method, or `null` if the method was of `void` return type.

A hand-crafted implementation

Before we look at the automatic creation of entwiners and untwiners, let us take a look at an example of how we would implement an entwiner and untwiner for a certain interface if we were to do it by hand.

Let us consider the following interface:

interface IFooable
{
    void Moo( int i );
    void Boo( string s, bool b );
}

And let us consider the following class implementing that interface:

class FooImplementation: IFooable
{
    void IFooable.Moo( int i ) { Console.WriteLine( "i: " + i ); }
    void IFooable.Boo( string s, bool b ) { Console.WriteLine( "s: " + s + ", b: " + b ); }
}

And then let us consider the following method which invokes the interface:

void InvokeFoo( IFooable fooable )
{
    fooable.Moo( 42 );
    fooable.Boo( "fubar!", true );
}

The InvokeFoo method can be directly hooked up to an instance of the implementing class in a completely conventional way as follows:

void Run1()
{
    IFooable fooable = new FooImplementation();
    InvokeFoo( fooable );
}

Now, an entwiner for our IFooable interface could be hand-crafted as follows:

class EntwinerForFooable: IFooable
{
    private readonly AnyCall AnyCall;
    Constructor( AnyCall anycall ) { AnyCall = anycall; }
    void IFooable.Moo( int i ) { AnyCall( 0, new object[]{ i } ); }
    void IFooable.Boo( string s, bool b ) { AnyCall( 1, new object[]{ s, b } ); }
}

Whereas an untwiner for IFooable could be hand-crafted as follows:

class UntwinerForFooable
{
    public readonly IFooable Target;
    public Constructor( IFooable target ) { Target = target; }
    public object AnyCall( int selector, object[] args )
    {
        switch( selector )
        {
            case 0: Target.Moo( (int)args[0] ); break;
            case 1: Target.Boo( (string)args[0], (bool)args[1] ); break;
            default: throw new System.InvalidOperationException();
        }
        return null;
    }
}

With the above classes, we can now write the following piece of awesomeness:

void Run2()
{
    IFooable fooable = new FooImplementation();
    var untwiner = new UntwinerForFooable( fooable );
    var entwiner = new EntwinerForFooable( untwiner.AnyCall );
    InvokeFoo( entwiner );
}

Note that Run2() has exactly the same end-result as Run1(), but there is a big difference in what goes on under the hood: all outbound interface method calls from the InvokeFoo function are now arriving at the entwiner, which converts them to AnyCall invocations, which are then forwarded to the untwiner, which converts them back to IFooable calls, which are then forwarded to our FooImplementation object. This means that if we wanted to, we could interject a chain of objects between the entwiner and the untwiner, each one of these objects implementing an AnyCall delegate and invoking another AnyCall delegate, thus enabling us to perform any conceivable operation upon those invocations without having any built-in knowledge of the IFooable interface.

As the complexity of the interface increases, and as additional subtleties come into the picture, such as parameters passed with ref or out, coding entwiners and untwiners by hand can become very tedious and error-prone, so, obviously, we would like to have it automated.

Automating it with reflection

It is possible to write a general-purpose untwiner that does its job using reflection, but reflection is slow, so the result is going to suffer performance-wise. For the sake of completeness, here is a possible implementation for a general-purpose reflecting untwiner using reflection:

class ReflectingUntwiner //WARNING: SLOW AS MOLASSES
{
    private readonly object Target;
    private readonly System.Reflection.MethodInfo[] Methodinfos;
    public Constructor( Type twinee, object target )
    {
        Target = target;
        Methodinfos = twinee.GetMethods( BindingFlags.Public |
                BindingFlags.NonPublic | BindingFlags.Instance );
    }
    public object AnyCall( int selector, object[] arguments )
    {
        return Methodinfos[selector].Invoke( Target, arguments );
    }
}

Note that untwiner creation could be optimized by caching the MethodInfos of frequently used types, but that’s not the problem; the real bottleneck is the `MethodInfo.Invoke()` call. If you put a breakpoint on the target and examine the stack, you will see that between the AnyCall frame and the target frame there will be a managed-to-native transition and a native-to-managed transition, which is something to be avoided at all costs.

Also note: it is impossible to write a reflecting entwiner.

Automating it with Intertwine

The Intertwine library will automatically generate for us a pair of optimally-performing entwiner and untwiner classes for any interface. These classes are generated at runtime, so no extra build step is needed. To accomplish this, the C# implementation of Intertwine generates MSIL and creates assemblies from it; the Java Implementation generates bytecode and creates classes from it.

The following method of the Intertwine.Factory class creates an entwiner:

    public static T NewEntwiner<T>( AnyCall anycall );

For T we give the type of our interface, and for anycall we give a delegate of ours that will be receiving calls. This method returns a reference to an implementation of our interface, provided by an Entwiner-derived class that has been dynamically generated specifically for our interface, and instantiated to work with the given AnyCall instance. For every call received through a method of our interface, this special entwiner will be marshalling the arguments and forwarding the call to our AnyCall delegate.

The following method of the Intertwine.Factory class creates an untwiner:

    public static AnyCall NewUntwiner<T>( T target );

For target we give an implementation of our interface, and what we get is a reference to an AnyCall delegate implemented by an Untwiner-derived class that was dynamically generated specifically for our interface, and instantiated to work with the given target instance. For every call received through the AnyCall delegate, this special untwiner will be unmarshalling the arguments and forwarding the call to the appropriate method of our target interface.

So, with the dynamically generated entwiners and untwiners we can now do the following epicness:

void Run3()
{
    IFooable fooable = new FooImplementation();
    AnyCall untwiner = Intertwine.Factory.NewUntwiner<IFooable>( fooable );
    IFooable entwiner = Intertwine.Factory.NewEntwiner<IFooable>( untwiner );
    InvokeFoo( entwiner );
}

The actual implementation of Intertwine.Factory is pretty straightforward, so there is not much to talk about. As one might expect, the generated types are cached. A static factory method is generated with each generated type, for instantiating the type, so as to avoid having to call Activator.CreateInstance(), because that method uses reflection. The static factory method is invoked using Delegate.Invoke(), which does not use reflection. You will find the code-generating code choke-full of comments, explaining exactly what each emitted opcode does.

Intertwine for C#: https://github.com/mikenakis/IntertwineCSharp

Intertwine for Java: https://github.com/mikenakis/Public/tree/master/intertwine

Appendix: An example: Interface multicasts (events) in C#

If you are still with me you may be thinking that it is about time for a demonstration. What follows is not just an example, but actually a complete and useful application of intertwine which you may be able to start utilizing in your projects right away.

The C# language has built-in support for multicasts (events) but only delegates can be used as event observers. There are many cases, however, where interfaces would be more suitable. Java does not even have built-in support for multicasts, so programmers generally have to write their own, using single-method (functional) interfaces. In either language, if you want to achieve multicasting on multi-method interfaces, you have to rewrite the multicasting code for every single method of every single interface.

Consider the following interface:

interface ITableNotification
{
    void RowInserted( Fields fields );
    void RowDeleted( Key key );
    void RowUpdated( Key key, Fields fields );
}

And consider the following hypothetical (not actually possible) way of using it:

event ITableNotification tableNotificationEvent;
tableNotificationEvent += my_observer;
tableNotificationEvent.RowUpdated( key, fields );

The above does not work because events in C# work only with delegates, not with interfaces. However, with Intertwine, the next best thing is actually possible:

var tableNotificationEventManager = new InterfaceEventManager<ITableNotifcation>();
tableNotificationEventManager.Source.RegisterObserver( my_observer );
tableNotificationEventManager.Trigger.RowUpdated( key, fields );

This approach is self-explanatory, and the amount of code you have to write in order to use it is optimal; you do not need to deal with anything more than what is necessary, and if you ever add a notification, it will be a new interface method, so all existing implementations of that interface will automatically be flagged by the compiler as incomplete. With the help of Intertwine, this event manager is implemented in just 150 lines of code, including extensive comments.

End-notes

Originally posted in 2011, revised October 2015, November 2022

This post supersedes the original post: http://blog.michael.gr/2011/10/intertwine-normalizing-interface.html

Back in 2011 I posted a question on stackoverflow.com, titled Multiplexing interface method calls into a single delegate and demultiplexing asking if anyone knows of anything like Intertwine, but nobody did, so I built it myself.

No comments:

Post a Comment