1 | // Copyright 2007, Google Inc. |
2 | // All rights reserved. |
3 | // |
4 | // Redistribution and use in source and binary forms, with or without |
5 | // modification, are permitted provided that the following conditions are |
6 | // met: |
7 | // |
8 | // * Redistributions of source code must retain the above copyright |
9 | // notice, this list of conditions and the following disclaimer. |
10 | // * Redistributions in binary form must reproduce the above |
11 | // copyright notice, this list of conditions and the following disclaimer |
12 | // in the documentation and/or other materials provided with the |
13 | // distribution. |
14 | // * Neither the name of Google Inc. nor the names of its |
15 | // contributors may be used to endorse or promote products derived from |
16 | // this software without specific prior written permission. |
17 | // |
18 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
19 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
20 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
21 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
22 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
23 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
24 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
25 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
26 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
27 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
28 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
29 | |
30 | |
31 | // Google Mock - a framework for writing C++ mock classes. |
32 | // |
33 | // This file implements Matcher<const string&>, Matcher<string>, and |
34 | // utilities for defining matchers. |
35 | |
36 | #include "gmock/gmock-matchers.h" |
37 | |
38 | #include <string.h> |
39 | #include <iostream> |
40 | #include <sstream> |
41 | #include <string> |
42 | |
43 | namespace testing { |
44 | namespace internal { |
45 | |
46 | // Returns the description for a matcher defined using the MATCHER*() |
47 | // macro where the user-supplied description string is "", if |
48 | // 'negation' is false; otherwise returns the description of the |
49 | // negation of the matcher. 'param_values' contains a list of strings |
50 | // that are the print-out of the matcher's parameters. |
51 | GTEST_API_ std::string FormatMatcherDescription(bool negation, |
52 | const char* matcher_name, |
53 | const Strings& param_values) { |
54 | std::string result = ConvertIdentifierNameToWords(matcher_name); |
55 | if (param_values.size() >= 1) result += " " + JoinAsTuple(param_values); |
56 | return negation ? "not (" + result + ")" : result; |
57 | } |
58 | |
59 | // FindMaxBipartiteMatching and its helper class. |
60 | // |
61 | // Uses the well-known Ford-Fulkerson max flow method to find a maximum |
62 | // bipartite matching. Flow is considered to be from left to right. |
63 | // There is an implicit source node that is connected to all of the left |
64 | // nodes, and an implicit sink node that is connected to all of the |
65 | // right nodes. All edges have unit capacity. |
66 | // |
67 | // Neither the flow graph nor the residual flow graph are represented |
68 | // explicitly. Instead, they are implied by the information in 'graph' and |
69 | // a vector<int> called 'left_' whose elements are initialized to the |
70 | // value kUnused. This represents the initial state of the algorithm, |
71 | // where the flow graph is empty, and the residual flow graph has the |
72 | // following edges: |
73 | // - An edge from source to each left_ node |
74 | // - An edge from each right_ node to sink |
75 | // - An edge from each left_ node to each right_ node, if the |
76 | // corresponding edge exists in 'graph'. |
77 | // |
78 | // When the TryAugment() method adds a flow, it sets left_[l] = r for some |
79 | // nodes l and r. This induces the following changes: |
80 | // - The edges (source, l), (l, r), and (r, sink) are added to the |
81 | // flow graph. |
82 | // - The same three edges are removed from the residual flow graph. |
83 | // - The reverse edges (l, source), (r, l), and (sink, r) are added |
84 | // to the residual flow graph, which is a directional graph |
85 | // representing unused flow capacity. |
86 | // |
87 | // When the method augments a flow (moving left_[l] from some r1 to some |
88 | // other r2), this can be thought of as "undoing" the above steps with |
89 | // respect to r1 and "redoing" them with respect to r2. |
90 | // |
91 | // It bears repeating that the flow graph and residual flow graph are |
92 | // never represented explicitly, but can be derived by looking at the |
93 | // information in 'graph' and in left_. |
94 | // |
95 | // As an optimization, there is a second vector<int> called right_ which |
96 | // does not provide any new information. Instead, it enables more |
97 | // efficient queries about edges entering or leaving the right-side nodes |
98 | // of the flow or residual flow graphs. The following invariants are |
99 | // maintained: |
100 | // |
101 | // left[l] == kUnused or right[left[l]] == l |
102 | // right[r] == kUnused or left[right[r]] == r |
103 | // |
104 | // . [ source ] . |
105 | // . ||| . |
106 | // . ||| . |
107 | // . ||\--> left[0]=1 ---\ right[0]=-1 ----\ . |
108 | // . || | | . |
109 | // . |\---> left[1]=-1 \--> right[1]=0 ---\| . |
110 | // . | || . |
111 | // . \----> left[2]=2 ------> right[2]=2 --\|| . |
112 | // . ||| . |
113 | // . elements matchers vvv . |
114 | // . [ sink ] . |
115 | // |
116 | // See Also: |
117 | // [1] Cormen, et al (2001). "Section 26.2: The Ford-Fulkerson method". |
118 | // "Introduction to Algorithms (Second ed.)", pp. 651-664. |
119 | // [2] "Ford-Fulkerson algorithm", Wikipedia, |
120 | // 'http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm' |
121 | class MaxBipartiteMatchState { |
122 | public: |
123 | explicit MaxBipartiteMatchState(const MatchMatrix& graph) |
124 | : graph_(&graph), |
125 | left_(graph_->LhsSize(), kUnused), |
126 | right_(graph_->RhsSize(), kUnused) {} |
127 | |
128 | // Returns the edges of a maximal match, each in the form {left, right}. |
129 | ElementMatcherPairs Compute() { |
130 | // 'seen' is used for path finding { 0: unseen, 1: seen }. |
131 | ::std::vector<char> seen; |
132 | // Searches the residual flow graph for a path from each left node to |
133 | // the sink in the residual flow graph, and if one is found, add flow |
134 | // to the graph. It's okay to search through the left nodes once. The |
135 | // edge from the implicit source node to each previously-visited left |
136 | // node will have flow if that left node has any path to the sink |
137 | // whatsoever. Subsequent augmentations can only add flow to the |
138 | // network, and cannot take away that previous flow unit from the source. |
139 | // Since the source-to-left edge can only carry one flow unit (or, |
140 | // each element can be matched to only one matcher), there is no need |
141 | // to visit the left nodes more than once looking for augmented paths. |
142 | // The flow is known to be possible or impossible by looking at the |
143 | // node once. |
144 | for (size_t ilhs = 0; ilhs < graph_->LhsSize(); ++ilhs) { |
145 | // Reset the path-marking vector and try to find a path from |
146 | // source to sink starting at the left_[ilhs] node. |
147 | GTEST_CHECK_(left_[ilhs] == kUnused) |
148 | << "ilhs: " << ilhs << ", left_[ilhs]: " << left_[ilhs]; |
149 | // 'seen' initialized to 'graph_->RhsSize()' copies of 0. |
150 | seen.assign(graph_->RhsSize(), 0); |
151 | TryAugment(ilhs, &seen); |
152 | } |
153 | ElementMatcherPairs result; |
154 | for (size_t ilhs = 0; ilhs < left_.size(); ++ilhs) { |
155 | size_t irhs = left_[ilhs]; |
156 | if (irhs == kUnused) continue; |
157 | result.push_back(ElementMatcherPair(ilhs, irhs)); |
158 | } |
159 | return result; |
160 | } |
161 | |
162 | private: |
163 | static const size_t kUnused = static_cast<size_t>(-1); |
164 | |
165 | // Perform a depth-first search from left node ilhs to the sink. If a |
166 | // path is found, flow is added to the network by linking the left and |
167 | // right vector elements corresponding each segment of the path. |
168 | // Returns true if a path to sink was found, which means that a unit of |
169 | // flow was added to the network. The 'seen' vector elements correspond |
170 | // to right nodes and are marked to eliminate cycles from the search. |
171 | // |
172 | // Left nodes will only be explored at most once because they |
173 | // are accessible from at most one right node in the residual flow |
174 | // graph. |
175 | // |
176 | // Note that left_[ilhs] is the only element of left_ that TryAugment will |
177 | // potentially transition from kUnused to another value. Any other |
178 | // left_ element holding kUnused before TryAugment will be holding it |
179 | // when TryAugment returns. |
180 | // |
181 | bool TryAugment(size_t ilhs, ::std::vector<char>* seen) { |
182 | for (size_t irhs = 0; irhs < graph_->RhsSize(); ++irhs) { |
183 | if ((*seen)[irhs]) continue; |
184 | if (!graph_->HasEdge(ilhs, irhs)) continue; |
185 | // There's an available edge from ilhs to irhs. |
186 | (*seen)[irhs] = 1; |
187 | // Next a search is performed to determine whether |
188 | // this edge is a dead end or leads to the sink. |
189 | // |
190 | // right_[irhs] == kUnused means that there is residual flow from |
191 | // right node irhs to the sink, so we can use that to finish this |
192 | // flow path and return success. |
193 | // |
194 | // Otherwise there is residual flow to some ilhs. We push flow |
195 | // along that path and call ourselves recursively to see if this |
196 | // ultimately leads to sink. |
197 | if (right_[irhs] == kUnused || TryAugment(right_[irhs], seen)) { |
198 | // Add flow from left_[ilhs] to right_[irhs]. |
199 | left_[ilhs] = irhs; |
200 | right_[irhs] = ilhs; |
201 | return true; |
202 | } |
203 | } |
204 | return false; |
205 | } |
206 | |
207 | const MatchMatrix* graph_; // not owned |
208 | // Each element of the left_ vector represents a left hand side node |
209 | // (i.e. an element) and each element of right_ is a right hand side |
210 | // node (i.e. a matcher). The values in the left_ vector indicate |
211 | // outflow from that node to a node on the right_ side. The values |
212 | // in the right_ indicate inflow, and specify which left_ node is |
213 | // feeding that right_ node, if any. For example, left_[3] == 1 means |
214 | // there's a flow from element #3 to matcher #1. Such a flow would also |
215 | // be redundantly represented in the right_ vector as right_[1] == 3. |
216 | // Elements of left_ and right_ are either kUnused or mutually |
217 | // referent. Mutually referent means that left_[right_[i]] = i and |
218 | // right_[left_[i]] = i. |
219 | ::std::vector<size_t> left_; |
220 | ::std::vector<size_t> right_; |
221 | }; |
222 | |
223 | const size_t MaxBipartiteMatchState::kUnused; |
224 | |
225 | GTEST_API_ ElementMatcherPairs FindMaxBipartiteMatching(const MatchMatrix& g) { |
226 | return MaxBipartiteMatchState(g).Compute(); |
227 | } |
228 | |
229 | static void LogElementMatcherPairVec(const ElementMatcherPairs& pairs, |
230 | ::std::ostream* stream) { |
231 | typedef ElementMatcherPairs::const_iterator Iter; |
232 | ::std::ostream& os = *stream; |
233 | os << "{" ; |
234 | const char* sep = "" ; |
235 | for (Iter it = pairs.begin(); it != pairs.end(); ++it) { |
236 | os << sep << "\n (" |
237 | << "element #" << it->first << ", " |
238 | << "matcher #" << it->second << ")" ; |
239 | sep = "," ; |
240 | } |
241 | os << "\n}" ; |
242 | } |
243 | |
244 | bool MatchMatrix::NextGraph() { |
245 | for (size_t ilhs = 0; ilhs < LhsSize(); ++ilhs) { |
246 | for (size_t irhs = 0; irhs < RhsSize(); ++irhs) { |
247 | char& b = matched_[SpaceIndex(ilhs, irhs)]; |
248 | if (!b) { |
249 | b = 1; |
250 | return true; |
251 | } |
252 | b = 0; |
253 | } |
254 | } |
255 | return false; |
256 | } |
257 | |
258 | void MatchMatrix::Randomize() { |
259 | for (size_t ilhs = 0; ilhs < LhsSize(); ++ilhs) { |
260 | for (size_t irhs = 0; irhs < RhsSize(); ++irhs) { |
261 | char& b = matched_[SpaceIndex(ilhs, irhs)]; |
262 | b = static_cast<char>(rand() & 1); // NOLINT |
263 | } |
264 | } |
265 | } |
266 | |
267 | std::string MatchMatrix::DebugString() const { |
268 | ::std::stringstream ss; |
269 | const char* sep = "" ; |
270 | for (size_t i = 0; i < LhsSize(); ++i) { |
271 | ss << sep; |
272 | for (size_t j = 0; j < RhsSize(); ++j) { |
273 | ss << HasEdge(i, j); |
274 | } |
275 | sep = ";" ; |
276 | } |
277 | return ss.str(); |
278 | } |
279 | |
280 | void UnorderedElementsAreMatcherImplBase::DescribeToImpl( |
281 | ::std::ostream* os) const { |
282 | switch (match_flags()) { |
283 | case UnorderedMatcherRequire::ExactMatch: |
284 | if (matcher_describers_.empty()) { |
285 | *os << "is empty" ; |
286 | return; |
287 | } |
288 | if (matcher_describers_.size() == 1) { |
289 | *os << "has " << Elements(1) << " and that element " ; |
290 | matcher_describers_[0]->DescribeTo(os); |
291 | return; |
292 | } |
293 | *os << "has " << Elements(matcher_describers_.size()) |
294 | << " and there exists some permutation of elements such that:\n" ; |
295 | break; |
296 | case UnorderedMatcherRequire::Superset: |
297 | *os << "a surjection from elements to requirements exists such that:\n" ; |
298 | break; |
299 | case UnorderedMatcherRequire::Subset: |
300 | *os << "an injection from elements to requirements exists such that:\n" ; |
301 | break; |
302 | } |
303 | |
304 | const char* sep = "" ; |
305 | for (size_t i = 0; i != matcher_describers_.size(); ++i) { |
306 | *os << sep; |
307 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
308 | *os << " - element #" << i << " " ; |
309 | } else { |
310 | *os << " - an element " ; |
311 | } |
312 | matcher_describers_[i]->DescribeTo(os); |
313 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
314 | sep = ", and\n" ; |
315 | } else { |
316 | sep = "\n" ; |
317 | } |
318 | } |
319 | } |
320 | |
321 | void UnorderedElementsAreMatcherImplBase::DescribeNegationToImpl( |
322 | ::std::ostream* os) const { |
323 | switch (match_flags()) { |
324 | case UnorderedMatcherRequire::ExactMatch: |
325 | if (matcher_describers_.empty()) { |
326 | *os << "isn't empty" ; |
327 | return; |
328 | } |
329 | if (matcher_describers_.size() == 1) { |
330 | *os << "doesn't have " << Elements(1) << ", or has " << Elements(1) |
331 | << " that " ; |
332 | matcher_describers_[0]->DescribeNegationTo(os); |
333 | return; |
334 | } |
335 | *os << "doesn't have " << Elements(matcher_describers_.size()) |
336 | << ", or there exists no permutation of elements such that:\n" ; |
337 | break; |
338 | case UnorderedMatcherRequire::Superset: |
339 | *os << "no surjection from elements to requirements exists such that:\n" ; |
340 | break; |
341 | case UnorderedMatcherRequire::Subset: |
342 | *os << "no injection from elements to requirements exists such that:\n" ; |
343 | break; |
344 | } |
345 | const char* sep = "" ; |
346 | for (size_t i = 0; i != matcher_describers_.size(); ++i) { |
347 | *os << sep; |
348 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
349 | *os << " - element #" << i << " " ; |
350 | } else { |
351 | *os << " - an element " ; |
352 | } |
353 | matcher_describers_[i]->DescribeTo(os); |
354 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
355 | sep = ", and\n" ; |
356 | } else { |
357 | sep = "\n" ; |
358 | } |
359 | } |
360 | } |
361 | |
362 | // Checks that all matchers match at least one element, and that all |
363 | // elements match at least one matcher. This enables faster matching |
364 | // and better error reporting. |
365 | // Returns false, writing an explanation to 'listener', if and only |
366 | // if the success criteria are not met. |
367 | bool UnorderedElementsAreMatcherImplBase::VerifyMatchMatrix( |
368 | const ::std::vector<std::string>& element_printouts, |
369 | const MatchMatrix& matrix, MatchResultListener* listener) const { |
370 | bool result = true; |
371 | ::std::vector<char> element_matched(matrix.LhsSize(), 0); |
372 | ::std::vector<char> matcher_matched(matrix.RhsSize(), 0); |
373 | |
374 | for (size_t ilhs = 0; ilhs < matrix.LhsSize(); ilhs++) { |
375 | for (size_t irhs = 0; irhs < matrix.RhsSize(); irhs++) { |
376 | char matched = matrix.HasEdge(ilhs, irhs); |
377 | element_matched[ilhs] |= matched; |
378 | matcher_matched[irhs] |= matched; |
379 | } |
380 | } |
381 | |
382 | if (match_flags() & UnorderedMatcherRequire::Superset) { |
383 | const char* sep = |
384 | "where the following matchers don't match any elements:\n" ; |
385 | for (size_t mi = 0; mi < matcher_matched.size(); ++mi) { |
386 | if (matcher_matched[mi]) continue; |
387 | result = false; |
388 | if (listener->IsInterested()) { |
389 | *listener << sep << "matcher #" << mi << ": " ; |
390 | matcher_describers_[mi]->DescribeTo(listener->stream()); |
391 | sep = ",\n" ; |
392 | } |
393 | } |
394 | } |
395 | |
396 | if (match_flags() & UnorderedMatcherRequire::Subset) { |
397 | const char* sep = |
398 | "where the following elements don't match any matchers:\n" ; |
399 | const char* outer_sep = "" ; |
400 | if (!result) { |
401 | outer_sep = "\nand " ; |
402 | } |
403 | for (size_t ei = 0; ei < element_matched.size(); ++ei) { |
404 | if (element_matched[ei]) continue; |
405 | result = false; |
406 | if (listener->IsInterested()) { |
407 | *listener << outer_sep << sep << "element #" << ei << ": " |
408 | << element_printouts[ei]; |
409 | sep = ",\n" ; |
410 | outer_sep = "" ; |
411 | } |
412 | } |
413 | } |
414 | return result; |
415 | } |
416 | |
417 | bool UnorderedElementsAreMatcherImplBase::FindPairing( |
418 | const MatchMatrix& matrix, MatchResultListener* listener) const { |
419 | ElementMatcherPairs matches = FindMaxBipartiteMatching(matrix); |
420 | |
421 | size_t max_flow = matches.size(); |
422 | if ((match_flags() & UnorderedMatcherRequire::Superset) && |
423 | max_flow < matrix.RhsSize()) { |
424 | if (listener->IsInterested()) { |
425 | *listener << "where no permutation of the elements can satisfy all " |
426 | "matchers, and the closest match is " |
427 | << max_flow << " of " << matrix.RhsSize() |
428 | << " matchers with the pairings:\n" ; |
429 | LogElementMatcherPairVec(matches, listener->stream()); |
430 | } |
431 | return false; |
432 | } |
433 | if ((match_flags() & UnorderedMatcherRequire::Subset) && |
434 | max_flow < matrix.LhsSize()) { |
435 | if (listener->IsInterested()) { |
436 | *listener |
437 | << "where not all elements can be matched, and the closest match is " |
438 | << max_flow << " of " << matrix.RhsSize() |
439 | << " matchers with the pairings:\n" ; |
440 | LogElementMatcherPairVec(matches, listener->stream()); |
441 | } |
442 | return false; |
443 | } |
444 | |
445 | if (matches.size() > 1) { |
446 | if (listener->IsInterested()) { |
447 | const char* sep = "where:\n" ; |
448 | for (size_t mi = 0; mi < matches.size(); ++mi) { |
449 | *listener << sep << " - element #" << matches[mi].first |
450 | << " is matched by matcher #" << matches[mi].second; |
451 | sep = ",\n" ; |
452 | } |
453 | } |
454 | } |
455 | return true; |
456 | } |
457 | |
458 | } // namespace internal |
459 | } // namespace testing |
460 | |