/proc/self/cwd/external/com_google_googletest/googlemock/src/gmock-matchers.cc
Line | Count | Source (jump to first uncovered line) |
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 | 0 | const Strings& param_values) { |
54 | 0 | std::string result = ConvertIdentifierNameToWords(matcher_name); |
55 | 0 | if (param_values.size() >= 1) result += " " + JoinAsTuple(param_values); |
56 | 0 | return negation ? "not (" + result + ")" : result; |
57 | 0 | } |
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 | 0 | right_(graph_->RhsSize(), kUnused) {} |
127 | | |
128 | | // Returns the edges of a maximal match, each in the form {left, right}. |
129 | 0 | ElementMatcherPairs Compute() { |
130 | | // 'seen' is used for path finding { 0: unseen, 1: seen }. |
131 | 0 | ::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 | 0 | 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 | 0 | GTEST_CHECK_(left_[ilhs] == kUnused) |
148 | 0 | << "ilhs: " << ilhs << ", left_[ilhs]: " << left_[ilhs]; |
149 | | // 'seen' initialized to 'graph_->RhsSize()' copies of 0. |
150 | 0 | seen.assign(graph_->RhsSize(), 0); |
151 | 0 | TryAugment(ilhs, &seen); |
152 | 0 | } |
153 | 0 | ElementMatcherPairs result; |
154 | 0 | for (size_t ilhs = 0; ilhs < left_.size(); ++ilhs) { |
155 | 0 | size_t irhs = left_[ilhs]; |
156 | 0 | if (irhs == kUnused) continue; |
157 | 0 | result.push_back(ElementMatcherPair(ilhs, irhs)); |
158 | 0 | } |
159 | 0 | return result; |
160 | 0 | } |
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 | 0 | bool TryAugment(size_t ilhs, ::std::vector<char>* seen) { |
182 | 0 | for (size_t irhs = 0; irhs < graph_->RhsSize(); ++irhs) { |
183 | 0 | if ((*seen)[irhs]) continue; |
184 | 0 | if (!graph_->HasEdge(ilhs, irhs)) continue; |
185 | | // There's an available edge from ilhs to irhs. |
186 | 0 | (*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 | 0 | if (right_[irhs] == kUnused || TryAugment(right_[irhs], seen)) { |
198 | | // Add flow from left_[ilhs] to right_[irhs]. |
199 | 0 | left_[ilhs] = irhs; |
200 | 0 | right_[irhs] = ilhs; |
201 | 0 | return true; |
202 | 0 | } |
203 | 0 | } |
204 | 0 | return false; |
205 | 0 | } |
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 | 0 | GTEST_API_ ElementMatcherPairs FindMaxBipartiteMatching(const MatchMatrix& g) { |
226 | 0 | return MaxBipartiteMatchState(g).Compute(); |
227 | 0 | } |
228 | | |
229 | | static void LogElementMatcherPairVec(const ElementMatcherPairs& pairs, |
230 | 0 | ::std::ostream* stream) { |
231 | 0 | typedef ElementMatcherPairs::const_iterator Iter; |
232 | 0 | ::std::ostream& os = *stream; |
233 | 0 | os << "{"; |
234 | 0 | const char* sep = ""; |
235 | 0 | for (Iter it = pairs.begin(); it != pairs.end(); ++it) { |
236 | 0 | os << sep << "\n (" |
237 | 0 | << "element #" << it->first << ", " |
238 | 0 | << "matcher #" << it->second << ")"; |
239 | 0 | sep = ","; |
240 | 0 | } |
241 | 0 | os << "\n}"; |
242 | 0 | } |
243 | | |
244 | 0 | bool MatchMatrix::NextGraph() { |
245 | 0 | for (size_t ilhs = 0; ilhs < LhsSize(); ++ilhs) { |
246 | 0 | for (size_t irhs = 0; irhs < RhsSize(); ++irhs) { |
247 | 0 | char& b = matched_[SpaceIndex(ilhs, irhs)]; |
248 | 0 | if (!b) { |
249 | 0 | b = 1; |
250 | 0 | return true; |
251 | 0 | } |
252 | 0 | b = 0; |
253 | 0 | } |
254 | 0 | } |
255 | 0 | return false; |
256 | 0 | } |
257 | | |
258 | 0 | void MatchMatrix::Randomize() { |
259 | 0 | for (size_t ilhs = 0; ilhs < LhsSize(); ++ilhs) { |
260 | 0 | for (size_t irhs = 0; irhs < RhsSize(); ++irhs) { |
261 | 0 | char& b = matched_[SpaceIndex(ilhs, irhs)]; |
262 | 0 | b = static_cast<char>(rand() & 1); // NOLINT |
263 | 0 | } |
264 | 0 | } |
265 | 0 | } |
266 | | |
267 | 0 | std::string MatchMatrix::DebugString() const { |
268 | 0 | ::std::stringstream ss; |
269 | 0 | const char* sep = ""; |
270 | 0 | for (size_t i = 0; i < LhsSize(); ++i) { |
271 | 0 | ss << sep; |
272 | 0 | for (size_t j = 0; j < RhsSize(); ++j) { |
273 | 0 | ss << HasEdge(i, j); |
274 | 0 | } |
275 | 0 | sep = ";"; |
276 | 0 | } |
277 | 0 | return ss.str(); |
278 | 0 | } |
279 | | |
280 | | void UnorderedElementsAreMatcherImplBase::DescribeToImpl( |
281 | 0 | ::std::ostream* os) const { |
282 | 0 | switch (match_flags()) { |
283 | 0 | case UnorderedMatcherRequire::ExactMatch: |
284 | 0 | if (matcher_describers_.empty()) { |
285 | 0 | *os << "is empty"; |
286 | 0 | return; |
287 | 0 | } |
288 | 0 | if (matcher_describers_.size() == 1) { |
289 | 0 | *os << "has " << Elements(1) << " and that element "; |
290 | 0 | matcher_describers_[0]->DescribeTo(os); |
291 | 0 | return; |
292 | 0 | } |
293 | 0 | *os << "has " << Elements(matcher_describers_.size()) |
294 | 0 | << " and there exists some permutation of elements such that:\n"; |
295 | 0 | break; |
296 | 0 | case UnorderedMatcherRequire::Superset: |
297 | 0 | *os << "a surjection from elements to requirements exists such that:\n"; |
298 | 0 | break; |
299 | 0 | case UnorderedMatcherRequire::Subset: |
300 | 0 | *os << "an injection from elements to requirements exists such that:\n"; |
301 | 0 | break; |
302 | 0 | } |
303 | | |
304 | 0 | const char* sep = ""; |
305 | 0 | for (size_t i = 0; i != matcher_describers_.size(); ++i) { |
306 | 0 | *os << sep; |
307 | 0 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
308 | 0 | *os << " - element #" << i << " "; |
309 | 0 | } else { |
310 | 0 | *os << " - an element "; |
311 | 0 | } |
312 | 0 | matcher_describers_[i]->DescribeTo(os); |
313 | 0 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
314 | 0 | sep = ", and\n"; |
315 | 0 | } else { |
316 | 0 | sep = "\n"; |
317 | 0 | } |
318 | 0 | } |
319 | 0 | } |
320 | | |
321 | | void UnorderedElementsAreMatcherImplBase::DescribeNegationToImpl( |
322 | 0 | ::std::ostream* os) const { |
323 | 0 | switch (match_flags()) { |
324 | 0 | case UnorderedMatcherRequire::ExactMatch: |
325 | 0 | if (matcher_describers_.empty()) { |
326 | 0 | *os << "isn't empty"; |
327 | 0 | return; |
328 | 0 | } |
329 | 0 | if (matcher_describers_.size() == 1) { |
330 | 0 | *os << "doesn't have " << Elements(1) << ", or has " << Elements(1) |
331 | 0 | << " that "; |
332 | 0 | matcher_describers_[0]->DescribeNegationTo(os); |
333 | 0 | return; |
334 | 0 | } |
335 | 0 | *os << "doesn't have " << Elements(matcher_describers_.size()) |
336 | 0 | << ", or there exists no permutation of elements such that:\n"; |
337 | 0 | break; |
338 | 0 | case UnorderedMatcherRequire::Superset: |
339 | 0 | *os << "no surjection from elements to requirements exists such that:\n"; |
340 | 0 | break; |
341 | 0 | case UnorderedMatcherRequire::Subset: |
342 | 0 | *os << "no injection from elements to requirements exists such that:\n"; |
343 | 0 | break; |
344 | 0 | } |
345 | 0 | const char* sep = ""; |
346 | 0 | for (size_t i = 0; i != matcher_describers_.size(); ++i) { |
347 | 0 | *os << sep; |
348 | 0 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
349 | 0 | *os << " - element #" << i << " "; |
350 | 0 | } else { |
351 | 0 | *os << " - an element "; |
352 | 0 | } |
353 | 0 | matcher_describers_[i]->DescribeTo(os); |
354 | 0 | if (match_flags() == UnorderedMatcherRequire::ExactMatch) { |
355 | 0 | sep = ", and\n"; |
356 | 0 | } else { |
357 | 0 | sep = "\n"; |
358 | 0 | } |
359 | 0 | } |
360 | 0 | } |
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 | 0 | const MatchMatrix& matrix, MatchResultListener* listener) const { |
370 | 0 | bool result = true; |
371 | 0 | ::std::vector<char> element_matched(matrix.LhsSize(), 0); |
372 | 0 | ::std::vector<char> matcher_matched(matrix.RhsSize(), 0); |
373 | |
|
374 | 0 | for (size_t ilhs = 0; ilhs < matrix.LhsSize(); ilhs++) { |
375 | 0 | for (size_t irhs = 0; irhs < matrix.RhsSize(); irhs++) { |
376 | 0 | char matched = matrix.HasEdge(ilhs, irhs); |
377 | 0 | element_matched[ilhs] |= matched; |
378 | 0 | matcher_matched[irhs] |= matched; |
379 | 0 | } |
380 | 0 | } |
381 | |
|
382 | 0 | if (match_flags() & UnorderedMatcherRequire::Superset) { |
383 | 0 | const char* sep = |
384 | 0 | "where the following matchers don't match any elements:\n"; |
385 | 0 | for (size_t mi = 0; mi < matcher_matched.size(); ++mi) { |
386 | 0 | if (matcher_matched[mi]) continue; |
387 | 0 | result = false; |
388 | 0 | if (listener->IsInterested()) { |
389 | 0 | *listener << sep << "matcher #" << mi << ": "; |
390 | 0 | matcher_describers_[mi]->DescribeTo(listener->stream()); |
391 | 0 | sep = ",\n"; |
392 | 0 | } |
393 | 0 | } |
394 | 0 | } |
395 | |
|
396 | 0 | if (match_flags() & UnorderedMatcherRequire::Subset) { |
397 | 0 | const char* sep = |
398 | 0 | "where the following elements don't match any matchers:\n"; |
399 | 0 | const char* outer_sep = ""; |
400 | 0 | if (!result) { |
401 | 0 | outer_sep = "\nand "; |
402 | 0 | } |
403 | 0 | for (size_t ei = 0; ei < element_matched.size(); ++ei) { |
404 | 0 | if (element_matched[ei]) continue; |
405 | 0 | result = false; |
406 | 0 | if (listener->IsInterested()) { |
407 | 0 | *listener << outer_sep << sep << "element #" << ei << ": " |
408 | 0 | << element_printouts[ei]; |
409 | 0 | sep = ",\n"; |
410 | 0 | outer_sep = ""; |
411 | 0 | } |
412 | 0 | } |
413 | 0 | } |
414 | 0 | return result; |
415 | 0 | } |
416 | | |
417 | | bool UnorderedElementsAreMatcherImplBase::FindPairing( |
418 | 0 | const MatchMatrix& matrix, MatchResultListener* listener) const { |
419 | 0 | ElementMatcherPairs matches = FindMaxBipartiteMatching(matrix); |
420 | |
|
421 | 0 | size_t max_flow = matches.size(); |
422 | 0 | if ((match_flags() & UnorderedMatcherRequire::Superset) && |
423 | 0 | max_flow < matrix.RhsSize()) { |
424 | 0 | if (listener->IsInterested()) { |
425 | 0 | *listener << "where no permutation of the elements can satisfy all " |
426 | 0 | "matchers, and the closest match is " |
427 | 0 | << max_flow << " of " << matrix.RhsSize() |
428 | 0 | << " matchers with the pairings:\n"; |
429 | 0 | LogElementMatcherPairVec(matches, listener->stream()); |
430 | 0 | } |
431 | 0 | return false; |
432 | 0 | } |
433 | 0 | if ((match_flags() & UnorderedMatcherRequire::Subset) && |
434 | 0 | max_flow < matrix.LhsSize()) { |
435 | 0 | if (listener->IsInterested()) { |
436 | 0 | *listener |
437 | 0 | << "where not all elements can be matched, and the closest match is " |
438 | 0 | << max_flow << " of " << matrix.RhsSize() |
439 | 0 | << " matchers with the pairings:\n"; |
440 | 0 | LogElementMatcherPairVec(matches, listener->stream()); |
441 | 0 | } |
442 | 0 | return false; |
443 | 0 | } |
444 | | |
445 | 0 | if (matches.size() > 1) { |
446 | 0 | if (listener->IsInterested()) { |
447 | 0 | const char* sep = "where:\n"; |
448 | 0 | for (size_t mi = 0; mi < matches.size(); ++mi) { |
449 | 0 | *listener << sep << " - element #" << matches[mi].first |
450 | 0 | << " is matched by matcher #" << matches[mi].second; |
451 | 0 | sep = ",\n"; |
452 | 0 | } |
453 | 0 | } |
454 | 0 | } |
455 | 0 | return true; |
456 | 0 | } |
457 | | |
458 | | } // namespace internal |
459 | | } // namespace testing |