[vlc-devel] [PATCH 0/5] mkv: introduced EbmlTypeDispatcher [ introductional explanation ]

Filip Roséen filip at videolabs.io
Tue Mar 8 15:13:56 CET 2016


Since we are stuck in C++03 land, a few "weird" constructs has been
incorporated into the code to make things work. In this cover-letter I will
try to explain the theoretical basics behind the approach.

Please see patch #1 for a more technical summary.

---------------------------------------------------------------------------
What are we after?
---------------------------------------------------------------------------

We would like to have a way to effectivelly construct a switch-like entity
that will do different things depending on some property of some object. One
way of doing this would be to introduce something like the below.

    #include <map>
    #include <iostream>
    
    int handle_even  (int n, int& status);
    int handle_odd   (int n, int& status);
    int handle_large (int n, int& status);
    
    enum HandlerType { ODD, EVEN, LARGE };
    
    int main () {
        std::map<HandlerType, int(*)(int, int&)> lookup;
    
        lookup.insert( std::make_pair(   ODD, &handle_odd ) );
        lookup.insert( std::make_pair(  EVEN, &handle_even ) );
        lookup.insert( std::make_pair( LARGE, &handle_large ) );
    
        HandlerType handler;
    
        int x = ...;
        int status;
    
        if      (x   > 1000) { handler = LARGE; }
        else if (x % 2 == 0) { handler = EVEN;  }
        else if (x % 2 == 1) { handler = ODD;   }
    
        int result = lookup.find (handler)->second (x, status);
    
        std::cout << result << " " << status << std::endl;
    }

The above is a rather contrived example, but there are a few key points:

    1. The definition for the different handlers are distant (meaning that we
       cannot know what they are doing unless we actually go to their
       definition).

    2. Even though handle_{even,odd,large} are only used inside main, there is
       no way to declare such intent. Surely, code reuse is golden--but if we
       are never going to use them elsewhere there is no point having them
       pollute the global namespace.

    3. We need to manually register each handler in our lookup. This can be
       written cleaner by first creating an array, and then iterating through
       that array to register the functions.
     
       The problem is that we still needs to do this manual work in order to
       actually initialize our map.

Sure, we could put the code for the different handlers directly in the if-else
tree, but given the fact that demux/mkv has (nested) trees that span several
hundred lines of code that is not really a viable alternative.


In C++11 we could use a std::initializer_list, std::function + lambdas (with
captures) to directly initialize our std::map; while also being able to access
variables in the sourrounding scope (such as "status" in the previous
example).

In C++03 there is no such functionality out of the box, but we can emulate the
behavior by automatically registering our functions where they are written.

---------------------------------------------------------------------------
How can we make the compiler do the work for us?
---------------------------------------------------------------------------

Even in C++03 we are allowed to create local structs that can include a
constructor, data-members, member-functions (including _static_), etc.. This
can effectivelly allow us to execute some code whenever such struct is
created.

So in order for us to "automatically" register a function without having the
declaration/definition in another scope inside our lookup we could utilize
something as the below.

    #include <map>
    #include <iostream>
    
    enum HandlerType { ODD, EVEN, LARGE };
    
    struct LookupWrapper {
        typedef std::map<HandlerType, int(*)(int, int&)> lookup_t;
        static lookup_t lookup;
    };
    
    LookupWrapper::lookup_t LookupWrapper::lookup;
    
    
    int main () {
        struct NumberHandlers : LookupWrapper {
            struct OddHandler {
                OddHandler() {
                    lookup[ODD] = &NumberHandlers::odd_callback;
                }
            } a;
            static int odd_callback(int n, int& capture) {
                capture = 42; return n * 2;
            }
    
            struct EvenHandler {
                EvenHandler () {
                    lookup[EVEN] = &NumberHandlers::even_callback;
                }
            } b;
            static int even_callback(int n, int& capture) {
                capture = 10; return n + 1;
            }
    
            struct LargeHandler {
                LargeHandler() {
                    lookup[LARGE] = &NumberHandlers::large_callback;
                }
            } c;
            static int large_callback(int n, int& capture) {
                capture = 10; return n / 20;
            }
        };
    
        int      x = 5;
        int status = 0;
        int result = NumberHandlers().lookup.find (ODD)->second (x, status);
    
        std::cout << status << " " << result << std::endl; // "42 10"
    }

Key points:

    - Since LookupWrapper::lookup is static all of the handlers have access to
      it since the NumberHandler-wrapper inherits from LookupWrapper, and will
      effectively register their handler to the same entity.

    - The Handlers will register themselves in their constructor, which is run
      (in order) when "a", "b", and "c" are created.

THOUGHTS
--------

LookupWrapper::lookup is static, meaning that it will retain its value across
function invocation (which is good, we want the map to be registered once).

The problem is that the handlers are not declared static, which means that
they will register themselves over and over. The behavior will be the same,
but they only need to register themselves once.

As a whole the code is somewhat what we are after, but it is _very_ verbose
and requires us to write a lot of boilerplate. There is also an issue with
functions that are entered more than one time.

    - If we would like to have more than one lookup-map (that handles ODD,
      EVEN, LARGE in different ways) we must declare another LookupWrapper in
      an accessible scope (otherwise we would register our handlers to the
      same map, which is not what we are after).

    - There is _a lot_ of boilerplate, which we can get rid of by introducing
      some minor MACROs that simply take care of the boilerplate.

SOLVING THE MANUAL TYPING ISSUE
-------------------------------

By introducing a MACRO as in the below example, we can shave of a lot of
manual typing in order to reach a very neat solution to our problem.

    /* ... same as before ... */

    #define NUMBER_HANDLER(Name_, Type_) \
        struct Name_ { \
            Name_ () {  \
                lookup[Type_] = &NumberHandlers:: Name_ ## _callback; \
            } \
        } Name_ ## _foo; \
        static int Name_ ## _callback(int n, int& capture) 
    
    int main () {
        struct NumberHandlers : LookupWrapper {
            NUMBER_HANDLER( OddHandler, ODD ) {
                capture = 42; return n * 2;
            }
            NUMBER_HANDLER( EvenHandler, EVEN ) {
                capture = 10; return n + 1;
            }
            NUMBER_HANDLER( LargeHandler, LARGE ) {
                capture = 10; return n / 20;
            }
        };
    
        int      x = 5;
        int status = 0;
        int result = NumberHandlers().lookup.find (ODD)->second (x, status);
    
        std::cout << status << " " << result << std::endl; // "42 10"
    }

SOLVING THE ISSUE WITH HAVING MORE THAN ONE LOOKUP-MAP
------------------------------------------------------

In C++03 you are not allowed to pass a local type as a template parameter,
this means that we cannot do something as the below to have a _static_ lookup
entity per group of handlers.

    template<class Tag>
    struct LookupWrapper {
        typedef std::map<HandlerType, int(*)(int, int&)> lookup_t;
        static lookup_t lookup;
    };
    
    template<class Tag>
    LookupWrapper<Tag>::lookup_t LookupWrapper<Tag>::lookup;
    
    ...

    int main () {
        struct NumberHandlers : LookupWrapper<NumberHandlers> {
            ...
        };
    }

However, we are allowed to pass the address of a variable with linkage as a
template-argument. Meaning that we can have a variablde declared `extern` and
have that serve as our per-handler-group unique Tag.

    template<int* Tag>
    struct LookupWrapper {
        typedef std::map<HandlerType, int(*)(int, int&)> lookup_t;
        static lookup_t lookup;
    };

    template<int* Tag>
    LookupWrapper<Tag>::lookup_t LookupWrapper<Tag>::lookup;

    ...

    int main () {
       extern int NumberHandlers_tag; 

       struct NumberHandlers : LookupWrapper<&NumberHandlers_tag> {

       };
    }

The above means that we can easily get a new static lookup-object by simply
introducing a new variable declared "extern" (since their addresses will be
unique).

    int main () {
        extern int NumberHandlerX_tag;
        struct NumberHandlerX_tag : LookupWrapper<NumberHandlerX_tag> {
            ...
        };

        extern int NumberHandlerY_tag;
        struct NumberHandlerY_tag : LookupWrapper<NumberHandlerY_tag> {
            ...
        };
    }

-------------------------------------------------------------------------------
CONCLUSION
-------------------------------------------------------------------------------

dispatcher.hpp + ebml_dispatcher.hpp uses the theory explained above, with a
few added tweaks to make it more versatile. However, if one understands that
is written in this message, understanding regarding the added tweaks should be
within reach.



------------------------------------------------------------------------------

On 16/03/08 15:11, Filip Roséen wrote:

> All of these patches are related to a new way of handling pointers to
> EbmlElements where the referred to object needs some processing dependent on
> the dynamic type of said object.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.videolan.org/pipermail/vlc-devel/attachments/20160308/6785da32/attachment-0001.html>


More information about the vlc-devel mailing list