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