Composition over inheritance when adding functionality to a foreign object

Question

Note: I am not sure of the correct terminology for what I am describing, so if you have suggestions for a better title please feel free to edit it.

"Favor composition over inheritance" is generally a good rule to follow, but there are some cases where inheritance is a must, like in the following case:

Node a = ...
Node b = ...
List<Node> path = GraphUtil.shortestPath(a,b);

Here we have a hypothetical graph library that provides some nice functionality for us, but we would like to augment it with some extra properties, like color or something. If we use inheritance, our code can be like this:

MyNode a = ...
MyNode b = ...
List<MyNode> path = (List<MyNode>)GraphUtil.shortestPath(a,b);
// highlight the path:
for (MyNode n : path) { n.color = "green"; }

This is still not totally amazing due to a runtime cast, but it gets the job done.

However, if we were to use composition, this won't work at all. We would need some kind of external map in order to achieve this (in C++ maybe some pointer hackery).

The question is: are there any existing strategies to achieve this behavior via composition that do not involve things like external maps or pointer hackery?

Of course the obvious answer is "just use inheritance", but if the Node class is made by a factory or is otherwise inconvenient to inherit from, what are the alternatives? Obviously a map is one option, but that is very inconvenient and messy, and not to mention slow.

Answer 1

Composition over inheritance

[A] Composition over inheritance is generally a good rule to follow,
[B] but there are some cases where inheritance is a must

Your conclusion in B implies that you are understanding A to mean "composition should always be used instead of inheritance". This interpretation is not correct.

There are some cases where inheritance is the only reasonable working solution. There are some cases where composition is the only reasonable working solution. Neither of these cases are relevant when considering "composition over inheritance".

There are some cases where composition and inheritance are both reasonable working solutions. "Composition over inheritance" advises that in these specific cases where either would a viable solution, that you should favor composition because it's not as likely for you to end up having painted yourself in a corner later on in the development cycle.

The example you bring to the table is one where inheritance is the only reasonable workable solution, and is therefore irrelevant as to the "composition over inheritance" guideline.
Similarly, the hypothetical you present is one where composition is the only reasonable workable solution, and is therefore equally irrelevant as to the "composition over inheritance" guideline.

The core of the question is irrespective of composition over inheritance. You're essentially asking "how to do A, which only works in situation X, while at the same time doing B, which only works in situation !X". By definition, you can't.

The question is: are there any existing strategies to achieve this behavior via composition that do not involve things like external maps or pointer hackery?

You already pre-empted the response, but in cases where only inheritance makes sense and not composition, just use inheritance.

Using the wrong solution for your scenario means that any difficulties you encounter from doing so are a self-imposed hurdle, and trying to make it work without addressing that hurdle turns into an XY problem really quickly.

Of course the obvious answer is "just use inheritance", but if the Node class is made by a factory or is otherwise inconvenient to inherit from, what are the alternatives? Obviously a map is one option, but that is very inconvenient and messy, and not to mention slow.

If the Node class is maintained by you, then this is another self-imposed hurdle. The obvious solution is to adapt the Node implementation so that it is inheritance-friendly.

If the Node class is maintained by the library developer, the same advice applies as it does for any complaint about the library you're using: either find another library to use, get the library developer to change their library, or deal with it. That last option then also entails letting go of the fact that it's going to require a dirty hack to get it working the way you need it to.

If the library designer chose to make it impossible to derive the Node class, or unknowingly designed their library in a way that makes it impossible, then that's how the library is designed. Any circumvention of that design is therefore by definition a hack.

An informal way to define a hack is that it is an inferior/shoddy solution when a better solution is available. The corollary here is that if there are no better solutions to the problem, then it's not a hack.

Answer 2

After I wrote most parts of my answer, you added this question:

are there any existing strategies to achieve this behavior via composition that do not involve things like external maps

Short answer: no, there isn't!.

You want to avoid inheriting from Node, but carry some extra attributes for each nodes around. Assumed you cannot add the attributes to those nodes by inheritance, and assumed there is no other designated extension mechanism in the Node class (as mentioned by @pjc50), it is necessary to store the extra attributes somewhere outside. And to reach the related extension attributes for a given node, some kind of map or Dictionary<Node,Color> is the straightforward, canonical and most simple solution.

Of course, this requires Node objects to be "hashable" a.k.a. suitable as keys for a dictionary or map, or having an Id which can serve as a key to distinguish between them. Here is a short sketch in C#:

Dictionary<Node,Color> nodeColors = ... (init this for all nodes)

Node a = ...
Node b = ...

List<Node> path = GraphUtil.shortestPath(a,b);

for (Node n : path) { nodeColors[n]=Color.Green; }

Nodes in a graph will usually provide some way of identifying them in a unique way (maybe by some Id, maybe by guaranteeing fixed object references), so this should usually work for most real-world cases.

If you want to make use of Composition, you can combine this with the dictionary approach:

class MyNode
{
     Node node;
     Color color;
}

Using a dictionary Dictionary <Node,MyNode> instead of Dictionary <Node,Color> might be useful when you need the extra attributes together with the related Node object for further processing in multiple places.

With this, you can encapsulate the shortestPath function like this:

class MyGraphUtil
{
   // init this during construction of MyGraphUtil for all nodes);
   private Dictionary<Node,MyNode> nodeDict;

   public List<MyNode> path shortestPath(MyNode a,MyNode b)
   {
         return GraphUtil.shortestPath(a.node, b.node)
                         .Select(n => nodeDict[n]).ToList();
   }
}

so the dictionary will only be visible in one place.

(Maybe that was what @candied_orange meant, I am not really sure.)

Answer 3

There is a solution from the pre-OO era that is still commonly used in C when handling things like callbacks, and that is for the library object to provide an "any other data" field. In C, this is usually a pointer to void; in OO languages you would use a reference to the base Object type. Sometimes this is an integer instead of a pointer or reference.

Effectively the Node class should support being composed with any other object type in order to be useful without inheritance.

For example, Microsoft have used this technique to link the items in List controls with the underlying data objects of any type. C# : https://docs.microsoft.com/en-us/dotnet/api/system.windows.controls.itemscontrol?view=net-5.0 or C: https://docs.microsoft.com/en-us/windows/win32/controls/lvm-insertitem

The C implementation uses Windows messages, which are a fantastic example of how to do composition over inheritance in a language that doesn't support inheritance at all!

Answer 4

This is really a question about how to implement polymorphic data structures, and we can use the standard Java answer: generics. The Node class could be declared as a generic, with the parameter type used as the “metadata” for each node:

class Node<T> {
    public T metadata;
}

class MyMetadata {
    public Color color;
}

List<Node<MyMetadata>> path = graph.shortestPath(...);
for (Node<MyMetadata> node: path) {
    node.metadata.color = Color.GREEN;
}

Of course, this is up to the library designer. In Java, the annoying bit would be initializing the metadata field for each node polymorphically; you could supply a Callable to do that when constructing the graph as one option. In a language like Rust or Haskell, you could also use traits/type classes to specify that the metadata parameter should be constructible in some way.

Answer 5

Design decisions are most often made for you when you use an existing library. As @pcj50 notes, some libraries provide support for composition by adding a field to structures whose content can be defined by the user.

But if the author of the graph library did not foresee the need (or preferred inheritance over composition), you're essentially forced to do it their way and implement workarounds where that isn't feasible.

Answer 6

To answer that question we need to find out the main reason why the "Favor composition over inheritance" advice is important: it solves the hard coupling between the base class and the child class caused by inheritance. Composition allows us to use an interface to reference one class into another, thus solving the coupling problem.

However, in your case it seems to me that you are trying to inherit only data from the Node class. And data is, by itself, already fully customizable. That is, you can "mock" any data inside a field or property. This is different from a method that can only have its behaviour substituted when it is behind an interface.

So it is totally fine to use inheritance as long as there is no behavior being inherited, in the end you are just reusing some data fields.