1 // Copyright 2016-2017 the nyan authors, LGPLv3+. See copying.md for legal info.
2
3 #include "c3.h"
4
5 #include "compiler.h"
6 #include "object_state.h"
7 #include "util.h"
8
9
10 namespace nyan {
11
12
linearize(const fqon_t & name,const objstate_fetch_t & get_obj)13 std::vector<fqon_t> linearize(const fqon_t &name, const objstate_fetch_t &get_obj) {
14 std::unordered_set<fqon_t> seen;
15 return linearize_recurse(name, get_obj, &seen);
16 }
17
18
19 /*
20 * Implementation of c3 inheritance linearization.
21 *
22 * c3 linearization of cls(a, b, ...):
23 * c3(cls) = [cls] + merge(c3(a), c3(b), ..., [a, b, ...])
24 *
25 * merge: take first head of lists which is not in any tail of all lists.
26 * that head can be the first for multiple lists, pick it from all them.
27 * if valid, add to output and remove from all lists where it is head.
28 * repeat until all lists are empty.
29 * if all heads of the lists appear somewhere in a tail,
30 * no linearization exists.
31 */
32 std::vector<fqon_t>
linearize_recurse(const fqon_t & name,const objstate_fetch_t & get_obj,std::unordered_set<fqon_t> * seen)33 linearize_recurse(const fqon_t &name,
34 const objstate_fetch_t &get_obj,
35 std::unordered_set<fqon_t> *seen) {
36
37 using namespace std::string_literals;
38
39 // test for inheritance loops
40 if (seen->find(name) != std::end(*seen)) {
41 throw C3Error{
42 "recursive inheritance loop detected: '"s + name + "' already in {"
43 + util::strjoin(", ", *seen)
44 + "}"
45 };
46 } else {
47 seen->insert(name);
48 }
49
50 // get raw ObjectState of this object at the requested time
51 const ObjectState &obj_state = get_obj(name);
52
53 // calculate a new linearization in this list
54 std::vector<fqon_t> linearization;
55
56 // The current object is always the first in the returned list
57 linearization.push_back(name);
58
59 // Get parents of object.
60 const auto &parents = obj_state.get_parents();
61
62 // Calculate the parent linearization recursively
63 std::vector<std::vector<fqon_t>> par_linearizations;
64 par_linearizations.reserve(parents.size() + 1);
65
66 for (auto &parent : parents) {
67 // Recursive call to get the linearization of the parent
68 par_linearizations.push_back(
69 linearize_recurse(parent, get_obj, seen)
70 );
71 }
72
73 // And at the end, add all parents of this object to the merge-list.
74 par_linearizations.push_back(
75 {std::begin(parents), std::end(parents)}
76 );
77
78 // remove current name from the seen set
79 // we only needed it for the recursive call above.
80 seen->erase(name);
81
82 // Index to start with in each list
83 // On a side note, I used {} instead of () for some time.
84 // But that, unfortunately was buggy.
85 // What the bug was is left as a fun challenge for the reader.
86 std::vector<size_t> sublists_heads(par_linearizations.size(), 0);
87
88 // For each loop, find a candidate to add to the result.
89 while (true) {
90 const fqon_t *candidate;
91 bool candidate_ok = false;
92 size_t sublists_available = par_linearizations.size();
93
94 // Try to find a head that is not element of any tail
95 for (size_t i = 0; i < par_linearizations.size(); i++) {
96 const auto &par_linearization = par_linearizations[i];
97 const size_t headpos = sublists_heads[i];
98
99 // The head position has reached the end (i.e. the list is "empty")
100 if (headpos >= par_linearization.size()) {
101 sublists_available -= 1;
102 continue;
103 }
104
105 // Pick a head
106 candidate = &par_linearization[headpos];
107 candidate_ok = true;
108
109 // Test if the candidate is in any tail
110 for (size_t j = 0; j < par_linearizations.size(); j++) {
111
112 // The current list will never contain the candidate again.
113 if (j == i) {
114 continue;
115 }
116
117 const auto &tail = par_linearizations[j];
118 const size_t headpos_try = sublists_heads[j];
119
120 // Start one slot after the head
121 // and check that the candidate is not in that tail.
122 for (size_t k = headpos_try + 1; k < tail.size(); k++) {
123
124 // The head is in that tail, so we fail
125 if (unlikely(*candidate == tail[k])) {
126 candidate_ok = false;
127 break;
128 }
129 }
130
131 // Don't try further tails as one already failed.
132 if (unlikely(not candidate_ok)) {
133 break;
134 }
135 }
136
137 // The candidate was not in any tail
138 if (candidate_ok) {
139 break;
140 } else {
141 // Try the next candidate,
142 // this means to select the next par_lin list.
143 continue;
144 }
145 }
146
147 // We found a candidate, add it to the return list
148 if (candidate_ok) {
149 linearization.push_back(*candidate);
150
151 // Advance all the lists where the candidate was the head
152 for (size_t i = 0; i < par_linearizations.size(); i++) {
153 const auto &par_linearization = par_linearizations[i];
154 const size_t headpos = sublists_heads[i];
155
156 if (headpos < par_linearization.size()) {
157 if (par_linearization[headpos] == *candidate) {
158 sublists_heads[i] += 1;
159 }
160 }
161 }
162 }
163
164 // No more sublists have any entry
165 if (sublists_available == 0) {
166 // linearization is finished!
167 return linearization;
168 }
169
170 if (not candidate_ok) {
171 throw C3Error{
172 "Can't find consistent C3 resolution order for "s
173 + name + " for bases " + util::strjoin(", ", parents)
174 };
175 }
176 }
177
178 // should not be reached :)
179 throw InternalError{"C3 internal error"};
180 }
181
182
C3Error(const std::string & msg)183 C3Error::C3Error(const std::string &msg)
184 :
185 Error{msg} {}
186
187
188 } // namespace nyan
189