In this post we will discuss Liskov Substitution Principle of Object Oriented Design in details, and review a real design found in Android Open Source Project in order to understand its importance.

This post is part of a series that describe SOLID principles of Object Oriented Design. If you have difficulties understanding the examples, please read the introduction article.

Liskov Substitution Principle (LSP):

LSP is named after Barbara Liskov, who is a recognized computer scientist, a winner of 2008 Turing Award, and, judging by videos featuring her, a great teacher and a very nice lady.

The concepts underlying LSP had been initially introduced in Liskov’s 1988 paper titled “Data Abstraction and Hierarchy”, and were later restated and given a rigorous mathematical formulation in 1999 paper by Barbara Liskov and Jeannette Wing titled Behavioral Subtyping Using Invariants and Constraints.

Robert Martin, in one of his papers, summarized LSP as follows:

Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it

Robert C. Martin

In context of the following diagram, adherence to LSP means that ClientClass, which depends on SuperClass, can work seamlessly with instances of both SuperClass and SubClass, and should not be concerned with the distinction between the two:

The short summary given above captures the main idea of LSP, but it is not self-sufficient by itself. It lacks a definition of practical rules that should be followed by developers in order to achieve such an interoperability between a superclass and its subclasses.

Liskov Substitution Principle Rules:

A set of rules that must be followed in order to achieve interoperability between the superclass and its subclasses can be found in the aforementioned paper Behavioral Subtyping Using Invariants and Constraints:

As you can see, the paper uses mathematical notation extensively, which makes it difficult to read and understand it without some (recent) mathematical background.

In order to make these rules more digestible, in the following sections we are going to express them in a more human readable format and discuss their implications.

Contravariance of overridden method arguments:

Methods of a subclass that override methods of a superclass must have exactly the same number of arguments. Each argument of the overriding method must be either the same type, or a supertype of the type of the corresponding argument in the superclass method.

This rule ensures that overridden method in subclass will have signature that is compatible with superclass method, and will be able to handle all argument types that are valid for superclass method.

Covariance of overridden method return type:

If a subclass overrides method that doesn’t have return value, the overriding method mustn’t have a return value either. If the superclass method does have a return value, then the overriding method must have a return value, and the type of the return value in the overriding method must be either the same type, or subtype of the return value in the superclass method.

This rule ensures that the return value of the overriding method is compatible with the return value of the superclass method, and that the clients of the superclass method will be able to handle the value returned from subclass method.

Overridden method exceptions:

The set of types of exceptions thrown from overriding method of a subclass must be the same (including exceptions’ subtypes) as the set of types of exceptions thrown from the method of the superclass.

This rule ensures that the clients of a superclass method will not get exceptions that they are not prepared for.

This rule is of critical importance in languages that support unchecked exceptions because these exceptions are not reflected in method’s signature. This makes it technically possible to throw new types of exceptions from the overriding method, and the compiler will not flag this as an error. Doing so will silently violate LSP, and can make existing systems that rely on superclass’ contract fail when integrated with subclasses that throw new exception types.

Overriden method pre-conditions:

The pre-conditions enforced by the subclass must not be more restrictive than the pre-conditions enforced by the superclass.

An example of violation of pre-condition rule is when a superclass method can accept null as an argument, but subclass method can’t. In this situation, clients of a superclass method that expect that it can handle null value, can pass this value to the subclass method which can’t handle this input.

Overriden method post-conditions:

The post-conditions enforced by the subclass must not be more permissive than the post-conditions enforced by the superclass.

An example of violation of post-condition rule is when a superclass method can’t return null, but subclass method can. In this situation, clients of a superclass that do not expect to get null return value can actually get this value if the subclass is used.

Invariant rule:

The invariants enforced by the subclass imply the invariants of a superclass too.

This means that whatever condition is enforced by the superclass in any state (for example the values returned by getA() and getB() methods are never equal), the same condition must be also enforced by the subclass in any state.

This rule is important because subclass can have more methods than superclass, and if any of these methods mutates the subclass such that superclass invariant is not enforced, then the clients of a superclass can fail when integrated with violating subclasses.

Constraint rule:

The history properties enforced by the subclass imply the history properties of the superclass too.

For example, if the superclass has a constraint stating that the value returned by getA() method never changes, the subclass must satisfy this constraint too.

Like the invariant rule above, this rule is important because the subclass can have more methods than the superclass and it is possible to accidentally break some superclass history constraint by mutating the state of the subclass.

Liskov Substitution Principle and Effective Java:

To my best knowledge, the only “item” in the classical book Effective Java (2nd edition) that explicitly mentions LSP is “Item 8: Obey the general contract when overriding equals”.

However, there is another item that implicitly discusses LSP violations in great details: “Item 16: Favor composition over inheritance”. In this “item”, Joshua Bloch demonstrates how class inheritance can lead to subtle, but very serious APIs compatibility issues.

Many issues described in this item are directly related to violation of the above LSP rules. As an exercise, you can read this item and attempt to map the issues described in the book to LSP rules violations.

Armed with our newly acquired deep understanding of LSP, we can summarize this 6 page “item” with just several sentences:

Favor composition over inheritance because it is hard to implement subclasses that obey LSP. Furthermore, even if subclasses obey LSP at some point in time, subsequent uncoordinated modifications of superclass can lead to violation of one or more of LSP’s rules and cause very nasty bugs. Uncoordinated modifications of superclass can also break the additional functionality introduced by subclasses.

Vasiliy Zukanov, restating Effective Java’s “Item 16: Favor composition over inheritance”

The part that mentions uncoordinated changes of superclasses is very important!

Joshua Bloch warns us that even if the inheritance tree adheres to LSP initially, any change of superclass logic has a potential of causing LSP violation. One example of such a change is addition of a new invariant to the superclass – even if existing subclasses enforce all former superclass’ invariants, they are not automatically guaranteed to enforce the newly added invariant.

The reason why I cross referenced LSP with Effective Java is because we need to understand that it is not a trivial task to adhere to LSP, and we should think about all the points discussed above every time we use inheritance.

Liskov Substitution Principle and Context:

Let’s see whether the inheritance tree of Context class in Android adheres to LSP. This inheritance tree looks as follows:

Fortunately, I don’t need to write lengthy explanations this time, because Dave Smith did an outstanding job and wrote Context, What Context? post. This post discusses use-cases for different subclasses of Context, and I strongly encourage all Android developers to read it.

In context of our current discussion, however, just one table that summarizes the capabilities of subclasses of Context from the aforementioned blog post will suffice. I further stripped down some non-essential information in order to simplify the table:

	Application	Activity	Service
Show a Dialog	NO	YES	NO
Start an Activity	NO	YES	NO
Layout Inflation	NO	YES	NO
Start a Service	YES	YES	YES
Bind to a Service	YES	YES	YES
Send a Broadcast	YES	YES	YES
Register BroadcastReceiver	YES	YES	YES
Load Resource Values	YES	YES	YES

The leftmost column lists some of the use-cases of Context objects. We have already discussed that Context and its subclasses are God objects that violate Single Responsibility Principle, therefore the vast difference between use-cases should not come as a surprise.

The three rightmost columns indicate whether Application, Activity and Service support the specific use-case. As you can see, use-cases related to application’s user interface are supported by Activity, but are not supported by Application and Service. The fact that Android developers need to think about which subclasses of Context work for each specific use case is a clear violation of LSP.

Part of the learning curve of Android developers is understanding how to choose the appropriate subclass of Context on the fly. There are numerous common bugs of various severity associated with usage of wrong subclass of Context. Some of these bugs cause incorrect rendering of user interface, others cause application crashes.

Memory Leaks and Context:

Yonatan Levin (Google Developer Expert for Android), in one of his presentations, shared the following piece of code that caused a memory leak in real production application (this refers to enclosing Activity):

mHeatMapEngine = new HeatMapEngine(
    new HeatMapEngine.Settings(
        heatMaps.getRefreshIntervalInMinutes() * 60 * 1000
    ),
    this, // enclosing Activity as Context
    map,
    mHeatEngineHandlerThread.getLooper(),
    DependencyInjector.getProtocol(),
    DependencyInjector.getLocationTracker()
);

In order to resolve this memory leak, Application was passed into the constructor instead of Activity:

mHeatMapEngine = new HeatMapEngine(
    new HeatMapEngine.Settings(
        heatMaps.getRefreshIntervalInMinutes() * 60 * 1000
    ),
    getApplicationContext(), // Application as Context
    map,
    mHeatEngineHandlerThread.getLooper(),
    DependencyInjector.getProtocol(),
    DependencyInjector.getLocationTracker()
);

This is yet another aspect of Context hierarchy tree that Android developers have no choice but get accustomed to – subclasses of Context have different scopes.

Application is “singleton-like” object and can be safely used in any scope, but a single incorrectly scoped reference to either Activity or Service can cause a massive memory leak. Such memory leaks often cause excessive memory consumption, until a point when applications crash with out-of-memory error.

I would like to state that this is an additional way of Context subclasses violating LSP, but that would be inaccurate.

See, one of the assumptions that Barbara Liskov and Jeannette Wing made in their 1999 paper (linked above) is that objects are never destroyed:

Therefore, while I’m certain that the fact that subclasses of Context have different scopes is a major design deficiency, I can’t relate it to LSP violation. However, I tend to believe that if LSP would be extended to deal with objects that have different scopes, this scope mismatch would be clearly considered an error.

Cost of Liskov Substitution Principle Violation:

Now let’s try to estimate the cost of LSP violation by Context hierarchy tree.

Let’s assume that an average Android developer spends a total of one hour on studying and debugging the bugs related to LSP violations. This is nowhere near the actual amount of time spent on these issues, but this is a simple number to work with.

How many Android developers are there in the world? Probably even Google themselves don’t know the exact number. The numbers found on the web are not very consistent, but all of the sources from 2016 that I found estimate the number of Android developers to be in several millions range. For the sake of argument, let’s assume that there are one million Android developers in the world.

Now, one million Android developers that waste one hour each due to LSP violation amounts to… ONE MILLION MAN HOURS. Take a moment and think about this number.

Since we used ridiculously low estimates both for the individual effort and for a total number of individuals, the actual waste is probably at least an order of magnitude larger.

Conclusion:

In this post we discussed Liskov Substitution Principle in details, and translated to human readable format the rules that should be followed when using class inheritance in object oriented languages.

We also saw how a widely accepted “favor composition over inheritance” rule is related to the complexity of LSP.

Inheritance tree of Context in Android framework was reviewed through a prism of LSP, and, though not strictly related to LSP, we also discussed the importance of scope matching in inheritance trees.

Finally, in order to understand the consequences of LSP violation quantitatively, we estimated that the cost of LSP violation by Context hierarchy tree in Android amounts to a waste of millions of man hours.

Please leave your comments and questions below, and subscribe to our blog if you liked the article.