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