Method Resolution Order (MRO) in Python with Sanyam Khurana

Hi

Speaker 1: everyone. I hope you have been enjoying the amazing lineup of talks. Hopefully you learned something new today in this talk about MRO method resolution order in Python. A bit about me. I'm one of you, a part of the community. I have a master's degree from Georgia Tech. I maintain a few open source projects including Django Phone Verify, Django Sites, Django Project. com. I'm a Bhakti Raja for CPython, contributor to Mozilla. You can reach me out on Twitter at ERCM Kurana or GitHub on Curious Learner. And before I begin this talk, I would like to tell you that this talk contains examples on MRO of Python. And we'll do examples for both the DLR algorithm, which is the old one, and the new C3 linearization algorithm.

Speaker 1: So I want you to pay close attention to the screen because this talk is about building the mental model of multiple inheritance in Python and how MRO works. Um you're more than welcome to take notes. Uh but if you want these slides, I've already tweeted a link on my Twitter. So let's talk about method resolution order. Imagine implementing inheritance in a programming language. At first it looks like all the methods and all the attributes that are inside your class. Will be inherited in all your child classes. While it works for the majority of scenarios, things become a little bit different when we hit the case of multiple inheritance And deciding which particular method or attribute will take precedence becomes a daunting task.

Speaker 1: This particular inheritance problem with multiple inheritance is famously known as the diamond problem. While some languages use algorithms such as write-first depth-first search to solve this, Python 2 used it the depth first left to right, which is DLR algorithm, and Python 3 used C3 linearization algorithm Now getting hold of this particular information will help you not succumbing to the common pitfalls with the arrangement of name lookups hierarchy, name lookups in the class hierarchy. The goal of this talk is to understand how and why MRO evolved the way it is now. Do not get tripped ever by multiple inheritance. And if you're using multiple intents in your code, whether in Python or Django, you use it in a more meaningful way, always going from specialized to more generic classes.

Speaker 1: And hopefully, this will also make you understand the advice that we have all across the Python community, like inheriting mix-ins before the concrete classes. So multiple inheritance is hard. Languages like Java, C do not support multiple inheritance at all. They do not want to get caught up by diamond problem. But Python actually solves this problem. So let's take a look at this diamond problem. So let's say we have these four classes over here. D has parent B and C. B and C each of the classes have just one parent A Now if I make it in terms of Python code, I would have something like this. Each of the class has a method, who am I, which just prints the name of the class it belongs to.

Speaker 1: The D class does not have this method. So now If I make an object of class T and I try to call the OMI method, which particular method should be called? So this is what we will be trying to figure out and this is what MRO is all about. The solution for this problem is method resolution order, which actually defines the class search path used by Python to search for the right attribute or method to use in classes having multiple inheritance So there are actually two algorithms to solve this problem. There is the old MRO algorithm and then there is the new MRO algorithm. The old one is step first left-to-right algorithm It was used prior to 2. 2 and it was used in old style classes.

Speaker 1: The newer one is C3 linearization algorithm and it was introduced in Python 2. 3, long way back, of course, I know. And It's use in new cell classes. Before we proceed further, I would like to just have a look at old cell and new cell classes. So by old style classes, I mean the base class does not inherit from the root class of object, right? And whenever I talk about new style classes, I'm talking about the base class which is Which which basically uh is inheriting from the object. So uh the newer classes will always use C3 linearization algorithm

Speaker 1: and uh There is a gotcha that you have to remember. I don't know how many of us are still stuck with legacy code bases, but if you are one of those people , And you're using old style classes in Python 2. 3 to 3, but you're using like old style classes in the code, you'll be using the DLR algorithm rather than the new algorithm. So this is one of the things that you have to remember. So let's try to have the example and we'll do this uh DLR example on the diamond problem itself. So we have our code over here And now the rule is depth first left to right. So if I call the method on class D, how would Python go about searching which particular method or attribute to call?

Speaker 1: So First, it will start looking in the class itself, which is the class D. If it does not found it in class D, it will look at the first parent of D, which is B in this case. Now, if it is not found in B, it will look at its parent, which is A in this case. And if it is not found in A, then it look at B's other parent, which of course is Nothing. So now it has no choice but to go to look at D's other parent, which is C in this case. So it goes to C, asks, do you have this particular method or attribute I want to call If it is at the if if that's the case, you're done. But if that's not the case, then it will start looking at

Speaker 1: uh the parent of class C, which is A in this case. So your MRO becomes D B A C A in this case. You can remove the duplicates from the end. So ultimately it becomes D B A C. That is the class lookup hierarchy Right, so before we begin and move on to our C3 linearization algorithm, let's have a look at the history of MRO, how MRO actually evolved. So it all began with a mail that was written to the Python dev mailing list back in 2002 by Samuel Pedroni. I hope I'm pronouncing their name correctly. Apologies if I'm not And he said that he was trying to wrap his head around the MRO computation, specifically

Speaker 1: how it works in Python 2. 2. And it obviously led to long lists of emails, and ultimately, Guido Win Rosum, who is the creator of the Python programming language, said that he has read the proposal and He agrees that we should adopt C3. But why this decision was made? This decision or this conclusion was made because of something known as monotonicity. So Python 2. 2 DLR algorithm was not monotonic. To be specific, it wasn't consistent. So, what exactly is this consistency criteria? So If C1 precedes C2 in linearization or the class precedence list of C, then C1 precedes C2 in linearization of any subclasses of C.

Speaker 1: Well, a lot of jargon over there. Let me simplify it. So, in simple terms, this is to say that the parent class cannot come before child class in the inheritance hierarchy So it will always try to look upwards, right? It cannot happen that, you know, it it will look at the parent first and then come to the child. So now let's understand this with the help of an example. So we have an example of hierarchy inheritance chain over here where D has parents P and C, C has parents P and A. So if I Try to say what is the MRO of A. If I'm trying to look for a particular method or attribute, I would just have to find it in the class A itself because it does not inherit from anything, right

Speaker 1: Similar case is for class B. Now, interesting bit starts when there is a case of multiple inheritance. So when I have a look in class C, I will first look for the method in class C, then its first parent which is B, and then its second parent, which is A. So far, so good. Now we'll talk about class D. Now what will happen is I will start looking at the method in class D, then the first parent which is B, then the second parent, which is C And now, since C also is a subclass, I will now go depth first, left to right. So I will go for B and then A. So the The MRO becomes DBCBA.

Speaker 1: Now, if you realize over here, B is the parent of C. Yet it appears before C in the MRO of D. This is non this is non-monotonic. So that is why we moved on to C3 linearization algorithm. Well, C3 actually got its name because it is consistent with three properties. It has a consistent uh extended precedence graph. preservation of local precedence order and it fits a monotonicity criterion. We already discussed about monotonicity, so let's actually look at what C3 actually is. So As I said before, it's the list of ancestors of class C, including the class C itself, ordered from the nearest ancestor to the farthest

Speaker 1: And it's it's called the class precedence list or you can call it linearization of C or you can also call it MRO of C. One and the same thing. Now, before we move on learning with uh what C3 is all about, let's actually have a look at the notations. Um we'll be using symptotic notation to Um, you know, write this algorithm out. So imagine you have this list of classes C1 through Cn. So these are your list of classes. The very first class in this list will always be the head of the list If your list just contains one class, then it means it has no tail, but it just has one head. So the classes C2, 3, C till C N are forms the tail of the list

Speaker 1: Now, if we want to add two lists, so we can write it in symptotic notation such as this. We want to add this class C. with an existing list of C1 through C N. So we can just write it as follows, right? So this basically is depicting how the search would happen. Now, let's assume we have a class C which inherits from multiple classes, multiple base classes B1 through Bn. Right. So now the linearization of C, which is the MRO of C, what it is. So it is defined by asymptotic formula over here. And I depict it with L of C. C inherits from B1 through Bn classes, right? So I'm writing linearization of C And now I say

Speaker 1: it will be the class C itself because that is the very first class that I would like to have or look at, right? If I'm searching for a particular method or attribute, that is the particular class that I will have a look at. I will say that okay, do you have this particular method or attribute? If not, then I will start exploring further up in the hierarchy, right? So it will be class C itself. Plus the merge of now here is the interesting bit. Now the merge is the merge of um you know a lot of lists. So it's the list of all the linearization of all the parents, which is linearization of B1, linearization of B2, until linearization of Bn, right? And then at the last, the very last list becomes uh The list of parents themselves.

Speaker 1: So this is your formula. Now please don't get overwhelmed by this symptotic notation I promise things will look a lot easier with help of examples, but this was essential so that you you understand the symptotic notation a bit. So, one more thing that we want to remember is if C is your object class, which is at the top of the hierarchy chain, and if you try to do linearization of that particular object class, it will be the object class itself, right. And further down in the presentation, whenever I discuss um any of the base classes, so if C class does not inherit from anything , Rather than saying it the MRO is C and then object, I will just say the MRO is C. So now let's discuss how to find this merge.

Speaker 1: What is this merge operation So merge operation happens because it's it's a list of lists, right? So we take the head of the first list, and if the head is not in tail of any other list, we We add it to linearization of C and we will remove it from the list in the merge. And then we will sort of start clearing up whatever is in the merge operation. Once we do that Um we can proceed further, but otherwise we look at the head of the next list to see if it is a good head. What's a good head? Good head means that If I'm picking head of the very first list, it should not be there in detail of any other lists

Speaker 1: So now I will repeat it until all the classes are removed or it is impossible to remove or it is impossible to find a good head. And in this case, when you don't you know have an option to find a good head anymore, Python 2. 3 will actually raise an exception in this case and it will say that you know there are no more good heads. So There cannot be a consistent MRO possible over here. So now let's try to run down MRO. Um The C3 on diamond problem itself. So I have written down the formula over here for you. Now we will do linearization of A, which is the class A itself. The linearization of B will be B. which is the class itself plus

Speaker 1: merge of linearization of all its parents, which is linearization of A, and the list of parents, which is just A in this case So far, so good. Now let's try to resolve this merge. So linearization of A, I just replace it with the value we discussed. And now if we take the head of the very first list, which is A in this case, and try to see it in tail of all the other lists, right? We will see that it's it's not present in the tail because if you Uh C in the second uh list, right? It's just contained one element, which is A in this case. So it does not have a tail at all. So now According to C3 linearization, I can take this A out of the equation. So I can say B and A, and then

Speaker 1: I can remove wherever A is occurring in all the list in the merge operation. So I can basically get rid of the merge operation itself. So linearization of B becomes B and A. Now similar thing will happen for When I am doing this with class C because it is having the kind of same you know hierarchy. So C plus merge of linearization is linearization of A and the class A itself So I get the linearization of C as C A. Now the interesting bit starts over here. When I try to search for linearization of class D Now when I say I want to find linearization of class D, it means the class D itself plus merge of linearization of all its parents which is linearization of B, then linearization of C and then the list of all parents which is B and C in this case.

Speaker 1: If I replace it with the actual values, I will get something like this. Now let's run down the merge operation one more time and we'll understand how C3 actually does its thing So we'll pick up the head of the very first list, which is B in this case, and now I will find if B happens to be there in the tail of any other list, right? So I inspect it and Of course, it is not there. So I can basically get B out of the equation, out of the merge operation, right? And remove it from all the list that uh The merge operation contains. So once I take B out of it, I am left with A, C A, and C. Now I will take the head of the very first list, which is A in this case.

Speaker 1: And I try to look at the tail of all the other lists. Does A happen to be in the tail of any other list? Of course, it does. So now, since A is in the tail of the list This is not a good head. We cannot take it out of the merge operation. So now we move on to the next head, right? Remember, it's an iterative process. So now we move on to the next uh head of uh we move on to the head of the next list which is c in this case and now we try to see if c happens to be there in the list of uh in the tail of any other list It does not right because if you have a look at the third list, it is just C element, right? So C is just the head. There is no tail over there. So it's since there is no tail

Speaker 1: I can take C out of the equation. So my MRO becomes D B C and I'm left with merge of A and A, which is of course we have discussed A itself. So now I get The MRO with on C3 is DBCA. If you remember, uh once we uh did the depth-first left-to-right algorithm, it it was DBAC, right? It was always a depth-first search, but in In C3 it is kind of a breath first search. So now The C3 MRO will always traverse parents at the same level before going through their ancestors further up the hierarchy, which is the same as saying, you know, this is a breadth-first search instead of a depth-first search, which was prior to Python 2.

Speaker 1: 3. Now let's try to run down C3 on our last example and it will hopefully make things a lot clearer for us. So now I'll run uh C3 on this particular example. This is the same example that we ran uh DLR on. So linearization of A and linearization of B will be classes themselves Nothing fancy over here. So let's start with linearization of C. So it will be class C itself plus merge of linearization of all its parents and the list of its parents Now the linearization uh let me replace it by the values. So I have something like this. I have B A B A. And then if I inspect the very first element which is B in this case to resolve the merge and check it if it's in tail of any other list, it does not.

Speaker 1: I can take B out. I'm left with this and I get C B A. So The linearization of C becomes C B A. Now I run through linearization of D, which is now class D itself, linearization of B, the linearization of all its parents, and then the list of parents itself. So it becomes something like this. Now I take the very first value over here, which is B in this case, and I try to see if it is in tail of any other list. So B actually appears to be in tail of other lists, so it's not a good hit. So now let's move on to our next list. We have C in this case. So I try to see if C appears in the list, uh any other list, in tail of any other list, of course. It does.

Speaker 1: So it's not good head either. And now if even if I move to the third list, the head is B, right? We have already discussed B cannot be a good head. So now we have exhausted all the list. There are no more good heads. So now in Python 3 or maybe you know any Python which is greater than Python 2. 3 where we are using C3 linearization algorithm, now Python will raise a type error So you will get something like this and it would say cannot create a consistent method resolution order for uh bases B and C. Right? So in Python 2 it was possible to create this same hierarchy, but in Python 3 you cannot create that. Why? Because if you observe here. C uh D is basically a

Speaker 1: a child of B and C, but C is also a child of B, right? This is the same map we discussed earlier. So now that we understand C3 linearization algorithm, now let's have a look at uh special class attributes that Python actually provides us. We have the same uh diamond problem example over here. So one of the thing we have is a dunder MRO um attribute. Now this attribute is a couple of classes that are cons Considered when looking for base classes during the method resolution. So if I have this example and I do D dotdunderMRO, I will get whatever you know is the MRO. So I can I can if if I want to practice and if I want to tweak it around, I can actually go there and see what Python chooses the MRO to be. Now there is another attribute which is done to

Speaker 1: basis. What it does is it would basically tell you all the base classes that the particular class inherits from. So if we talk about D, it has basis of B and C We have a special method which is MRO, right? And this method is very special. It actually is just the result which is stored in under MRO And this method can be overridden by any meta class, so you can actually customize the MRO for any instances that will enter from it. So if I run d. mro method, you will see that it it's it's kind of the same what we get with dunder mro. Right. So if we talk about MRO specifically in Django, uh for f you you'll you'll see you know inheritance all over Django, even if you're writing your own code.

Speaker 1: For forms there is form class, there is model form class, for views there are template views, redirect view. For models, There are three ways you can inherit uh models, right? So you can you can use abstract base classes, multiple table inheritance, proxy models. So in case of uh multiple table inheritance, uh You know, you you'll observe MRO being in action. And uh now let's let's actually there is a gotcha uh which is in uh Django Docs. Uh you should have uh You should avoid having complex hierarchy in uh specifically in case of multiple table inheritance. So uh the model fields actually data inherited from inherit from multiple abstract uh Parent models are resolved in strict depth first

Speaker 1: order, which is opposed to what Python does, right? Python is breadth first now. So this is because the way fields are resolved during the class definition uh when when you're writing your models. And Model fields uh will always be in a strict depth first uh manner. And uh yeah, so the the the idea here is that uh You should always try to avoid complex hierarchy. And let's do a recap. We discussed about MRO. We discussed about uh Old MRO, we looked at new C3 linearization, history of MRO, examples on MRO, type error, how it raised in C3 , special class attributes, and finally MRO in Django.

Speaker 1: If you want to read more about it, there is this first reference. It actually contains a lot of code where you can play around with that particular code snippet. To understand how MRO plays in Python 2 as well as Python 3. If you have any questions, I'll be around. You can reach out to me on Twitter at ERCM Kurana. on GitHub Curious Learner and my email is Siam at sayamkurana. com. Thank you very much for coming to the talk. I hope you have learned something new today. And special thanks to Jeff and Carlton for reviewing the talk

Speaker 2: Thank you very much.