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