bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "mro.h"
3
4#include "runtime.h"
5
6namespace py {
7
8// Fills merge_lists with the MROs of the parents, followed by the parents list.
9static word populateMergeLists(Thread* thread, const MutableTuple& merge_lists,
10 const Tuple& parents,
11 Vector<word>* merge_list_indices /* out */) {
12 word num_parents = parents.length();
13 DCHECK(merge_lists.length() == num_parents + 1,
14 "merge the linearizations of each parent with the parent list");
15 HandleScope scope(thread);
16 word new_mro_length = 2; // C + ... + object
17 for (word i = 0; i < num_parents; i++) {
18 Type parent_class(&scope, parents.at(i)); // B_i
19 Tuple parent_mro(&scope, parent_class.mro()); // L[B_i]
20
21 new_mro_length += parent_mro.length();
22 merge_lists.atPut(i, *parent_mro);
23 merge_list_indices->push_back(0);
24 }
25 merge_lists.atPut(num_parents, *parents); // B_1 B_2 ... B_n
26 merge_list_indices->push_back(0);
27 return new_mro_length - num_parents; // all parent MROs end with object
28}
29
30// Returns true if there is an i such that mro->at(i) == cls, i > head_idx.
31static bool tailContains(const Tuple& mro, const Object& cls, word head_idx) {
32 for (word i = head_idx + 1, length = mro.length(); i < length; i++) {
33 if (mro.at(i) == *cls) {
34 return true;
35 }
36 }
37 return false;
38}
39
40// Looks for a head class in merge_lists (i.e. the class indicated by the
41// corresponding index in merge_list_indices) which does not appear in any of
42// the merge_lists at a position *after* the head class of that list.
43static RawObject findNext(Thread* thread, const Tuple& merge_lists,
44 const Vector<word>& merge_list_indices) {
45 HandleScope scope(thread);
46 Object candidate_head(&scope, Unbound::object());
47 for (word i = 0, length = merge_lists.length(); i < length; i++) {
48 word cur_idx = merge_list_indices[i];
49 Tuple cur_mro(&scope, merge_lists.at(i));
50
51 if (cur_idx >= cur_mro.length()) {
52 continue;
53 }
54
55 candidate_head = cur_mro.at(cur_idx);
56 for (word j = 0; j < length; j++) {
57 if (j == i) {
58 continue;
59 }
60 Tuple other_mro(&scope, merge_lists.at(j));
61 if (tailContains(other_mro, candidate_head, merge_list_indices[j])) {
62 candidate_head = Error::notFound();
63 break;
64 }
65 }
66 if (!candidate_head.isError()) {
67 return *candidate_head;
68 }
69 }
70 return Error::notFound();
71}
72
73RawObject computeMro(Thread* thread, const Type& type) {
74 HandleScope scope(thread);
75 Runtime* runtime = thread->runtime();
76
77 Tuple parents(&scope, type.bases());
78 word num_parents = parents.length();
79 DCHECK(num_parents > 0, "must have at least 1 parent");
80
81 Vector<word> merge_list_indices;
82 word merge_list_length = num_parents + 1;
83 merge_list_indices.reserve(merge_list_length);
84 MutableTuple merge_lists(&scope, runtime->newMutableTuple(merge_list_length));
85 word new_mro_length =
86 populateMergeLists(thread, merge_lists, parents, &merge_list_indices);
87 DCHECK(merge_list_indices.size() == merge_list_length,
88 "expected %ld indices, got %ld", merge_list_length,
89 merge_list_indices.size());
90
91 // The length of new_mro will be longer than necessary when there is overlap
92 // between the MROs of the parents.
93 MutableTuple new_mro(&scope, runtime->newMutableTuple(new_mro_length));
94
95 word next_idx = 0;
96 new_mro.atPut(next_idx, *type);
97 next_idx++;
98
99 // To compute the MRO, repeatedly look for a head of one or more
100 // MROs, which is not in the tail of any other MROs, and consume
101 // all matching heads. This is O(n^2) as implemented, but so is
102 // CPython's implementation, so we can rest assured no real program
103 // is going to cause a major problem here.
104 RawObject next_head = Error::notFound();
105 while (!(next_head = findNext(thread, merge_lists, merge_list_indices))
106 .isError()) {
107 Type next_head_cls(&scope, next_head);
108 for (word i = 0; i < merge_list_length; i++) {
109 auto& cur_idx = merge_list_indices[i];
110 Tuple cur_mro(&scope, merge_lists.at(i));
111 if (cur_idx < cur_mro.length() && cur_mro.at(cur_idx) == *next_head_cls) {
112 cur_idx++;
113 }
114 }
115 new_mro.atPut(next_idx, *next_head_cls);
116 next_idx++;
117 }
118
119 for (word i = 0; i < merge_list_length; i++) {
120 if (merge_list_indices[i] != Tuple::cast(merge_lists.at(i)).length()) {
121 MutableTuple names(&scope, runtime->newMutableTuple(num_parents));
122 Type parent(&scope, runtime->typeAt(LayoutId::kNoneType));
123 for (word j = 0; j < num_parents; j++) {
124 parent = parents.at(j);
125 names.atPut(j, parent.name());
126 }
127 Str sep(&scope, SmallStr::fromCStr(", "));
128 Tuple names_immutable(&scope, names.becomeImmutable());
129 Object bases(&scope,
130 runtime->strJoin(thread, sep, names_immutable, num_parents));
131 return thread->raiseWithFmt(LayoutId::kTypeError,
132 "Cannot create a consistent method "
133 "resolution order (MRO) for bases %S",
134 &bases);
135 }
136 }
137
138 for (word i = 0, length = parents.length(); i < length; i++) {
139 for (word j = i + 1; j < length; j++) {
140 if (parents.at(i) == parents.at(j)) {
141 Type superclass_type(&scope, parents.at(i));
142 Str superclass_type_name(&scope, superclass_type.name());
143 return thread->raiseWithFmt(LayoutId::kTypeError,
144 "duplicate base class %S",
145 &superclass_type_name);
146 }
147 }
148 }
149
150 // Copy the mro to an array of exact size. (new_mro_length is an upper bound).
151 return runtime->tupleSubseq(thread, new_mro, 0, next_idx);
152}
153
154} // namespace py