1 // Copyright 2007, Google Inc.
2 // All rights reserved.
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
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
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.
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.
30 // Author: wan@google.com (Zhanyong Wan)
32 // Google Mock - a framework for writing C++ mock classes.
34 // This file implements Matcher<const string&>, Matcher<string>, and
35 // utilities for defining matchers.
37 #include "gmock/gmock-matchers.h"
38 #include "gmock/gmock-generated-matchers.h"
47 // Constructs a matcher that matches a const std::string& whose value is
49 Matcher
<const std::string
&>::Matcher(const std::string
& s
) { *this = Eq(s
); }
51 #if GTEST_HAS_GLOBAL_STRING
52 // Constructs a matcher that matches a const std::string& whose value is
54 Matcher
<const std::string
&>::Matcher(const ::string
& s
) {
55 *this = Eq(static_cast<std::string
>(s
));
57 #endif // GTEST_HAS_GLOBAL_STRING
59 // Constructs a matcher that matches a const std::string& whose value is
61 Matcher
<const std::string
&>::Matcher(const char* s
) {
62 *this = Eq(std::string(s
));
65 // Constructs a matcher that matches a std::string whose value is equal to
67 Matcher
<std::string
>::Matcher(const std::string
& s
) { *this = Eq(s
); }
69 #if GTEST_HAS_GLOBAL_STRING
70 // Constructs a matcher that matches a std::string whose value is equal to
72 Matcher
<std::string
>::Matcher(const ::string
& s
) {
73 *this = Eq(static_cast<std::string
>(s
));
75 #endif // GTEST_HAS_GLOBAL_STRING
77 // Constructs a matcher that matches a std::string whose value is equal to
79 Matcher
<std::string
>::Matcher(const char* s
) { *this = Eq(std::string(s
)); }
81 #if GTEST_HAS_GLOBAL_STRING
82 // Constructs a matcher that matches a const ::string& whose value is
84 Matcher
<const ::string
&>::Matcher(const std::string
& s
) {
85 *this = Eq(static_cast<::string
>(s
));
88 // Constructs a matcher that matches a const ::string& whose value is
90 Matcher
<const ::string
&>::Matcher(const ::string
& s
) { *this = Eq(s
); }
92 // Constructs a matcher that matches a const ::string& whose value is
94 Matcher
<const ::string
&>::Matcher(const char* s
) { *this = Eq(::string(s
)); }
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
));
101 // Constructs a matcher that matches a ::string whose value is equal to s.
102 Matcher
<::string
>::Matcher(const ::string
& s
) { *this = Eq(s
); }
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
109 // Constructs a matcher that matches a const absl::string_view& whose value is
111 Matcher
<const absl::string_view
&>::Matcher(const std::string
& s
) {
115 #if GTEST_HAS_GLOBAL_STRING
116 // Constructs a matcher that matches a const absl::string_view& whose value is
118 Matcher
<const absl::string_view
&>::Matcher(const ::string
& s
) { *this = Eq(s
); }
119 #endif // GTEST_HAS_GLOBAL_STRING
121 // Constructs a matcher that matches a const absl::string_view& whose value is
123 Matcher
<const absl::string_view
&>::Matcher(const char* s
) {
124 *this = Eq(std::string(s
));
127 // Constructs a matcher that matches a const absl::string_view& whose value is
129 Matcher
<const absl::string_view
&>::Matcher(absl::string_view s
) {
130 *this = Eq(std::string(s
));
133 // Constructs a matcher that matches a absl::string_view whose value is equal to
135 Matcher
<absl::string_view
>::Matcher(const std::string
& s
) { *this = Eq(s
); }
137 #if GTEST_HAS_GLOBAL_STRING
138 // Constructs a matcher that matches a absl::string_view whose value is equal to
140 Matcher
<absl::string_view
>::Matcher(const ::string
& s
) { *this = Eq(s
); }
141 #endif // GTEST_HAS_GLOBAL_STRING
143 // Constructs a matcher that matches a absl::string_view whose value is equal to
145 Matcher
<absl::string_view
>::Matcher(const char* s
) {
146 *this = Eq(std::string(s
));
149 // Constructs a matcher that matches a absl::string_view whose value is equal to
151 Matcher
<absl::string_view
>::Matcher(absl::string_view s
) {
152 *this = Eq(std::string(s
));
154 #endif // GTEST_HAS_ABSL
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.
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
);
168 return negation
? "not (" + result
+ ")" : result
;
171 // FindMaxBipartiteMatching and its helper class.
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.
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
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'.
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
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.
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.
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_.
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
213 // left[l] == kUnused or right[left[l]] == l
214 // right[r] == kUnused or left[right[r]] == r
219 // . ||\--> left[0]=1 ---\ right[0]=-1 ----\ .
221 // . |\---> left[1]=-1 \--> right[1]=0 ---\| .
223 // . \----> left[2]=2 ------> right[2]=2 --\|| .
225 // . elements matchers vvv .
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
{
235 explicit MaxBipartiteMatchState(const MatchMatrix
& graph
)
237 left_(graph_
->LhsSize(), kUnused
),
238 right_(graph_
->RhsSize(), kUnused
) {}
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
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
);
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
));
275 static const size_t kUnused
= static_cast<size_t>(-1);
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.
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
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.
293 bool TryAugment(size_t ilhs
, ::std::vector
<char>* seen
) {
294 for (size_t irhs
= 0; irhs
< graph_
->RhsSize(); ++irhs
) {
295 if ((*seen
)[irhs
]) continue;
296 if (!graph_
->HasEdge(ilhs
, irhs
)) continue;
297 // There's an available edge from ilhs to irhs.
299 // Next a search is performed to determine whether
300 // this edge is a dead end or leads to the sink.
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.
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].
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
323 // outflow from that node to a node on the right_ side. The values
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_
;
334 GTEST_DISALLOW_ASSIGN_(MaxBipartiteMatchState
);
337 const size_t MaxBipartiteMatchState::kUnused
;
339 GTEST_API_ ElementMatcherPairs
FindMaxBipartiteMatching(const MatchMatrix
& g
) {
340 return MaxBipartiteMatchState(g
).Compute();
343 static void LogElementMatcherPairVec(const ElementMatcherPairs
& pairs
,
344 ::std::ostream
* stream
) {
345 typedef ElementMatcherPairs::const_iterator Iter
;
346 ::std::ostream
& os
= *stream
;
348 const char* sep
= "";
349 for (Iter it
= pairs
.begin(); it
!= pairs
.end(); ++it
) {
351 << "element #" << it
->first
<< ", "
352 << "matcher #" << it
->second
<< ")";
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
)];
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
381 std::string
MatchMatrix::DebugString() const {
382 ::std::stringstream ss
;
383 const char* sep
= "";
384 for (size_t i
= 0; i
< LhsSize(); ++i
) {
386 for (size_t j
= 0; j
< RhsSize(); ++j
) {
394 void UnorderedElementsAreMatcherImplBase::DescribeToImpl(
395 ::std::ostream
* os
) const {
396 switch (match_flags()) {
397 case UnorderedMatcherRequire::ExactMatch
:
398 if (matcher_describers_
.empty()) {
402 if (matcher_describers_
.size() == 1) {
403 *os
<< "has " << Elements(1) << " and that element ";
404 matcher_describers_
[0]->DescribeTo(os
);
407 *os
<< "has " << Elements(matcher_describers_
.size())
408 << " and there exists some permutation of elements such that:\n";
410 case UnorderedMatcherRequire::Superset
:
411 *os
<< "a surjection from elements to requirements exists such that:\n";
413 case UnorderedMatcherRequire::Subset
:
414 *os
<< "an injection from elements to requirements exists such that:\n";
418 const char* sep
= "";
419 for (size_t i
= 0; i
!= matcher_describers_
.size(); ++i
) {
421 if (match_flags() == UnorderedMatcherRequire::ExactMatch
) {
422 *os
<< " - element #" << i
<< " ";
424 *os
<< " - an element ";
426 matcher_describers_
[i
]->DescribeTo(os
);
427 if (match_flags() == UnorderedMatcherRequire::ExactMatch
) {
435 void UnorderedElementsAreMatcherImplBase::DescribeNegationToImpl(
436 ::std::ostream
* os
) const {
437 switch (match_flags()) {
438 case UnorderedMatcherRequire::ExactMatch
:
439 if (matcher_describers_
.empty()) {
440 *os
<< "isn't empty";
443 if (matcher_describers_
.size() == 1) {
444 *os
<< "doesn't have " << Elements(1) << ", or has " << Elements(1)
446 matcher_describers_
[0]->DescribeNegationTo(os
);
449 *os
<< "doesn't have " << Elements(matcher_describers_
.size())
450 << ", or there exists no permutation of elements such that:\n";
452 case UnorderedMatcherRequire::Superset
:
453 *os
<< "no surjection from elements to requirements exists such that:\n";
455 case UnorderedMatcherRequire::Subset
:
456 *os
<< "no injection from elements to requirements exists such that:\n";
459 const char* sep
= "";
460 for (size_t i
= 0; i
!= matcher_describers_
.size(); ++i
) {
462 if (match_flags() == UnorderedMatcherRequire::ExactMatch
) {
463 *os
<< " - element #" << i
<< " ";
465 *os
<< " - an element ";
467 matcher_describers_
[i
]->DescribeTo(os
);
468 if (match_flags() == UnorderedMatcherRequire::ExactMatch
) {
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.
481 bool UnorderedElementsAreMatcherImplBase::VerifyMatchMatrix(
482 const ::std::vector
<std::string
>& element_printouts
,
483 const MatchMatrix
& matrix
, MatchResultListener
* listener
) const {
485 ::std::vector
<char> element_matched(matrix
.LhsSize(), 0);
486 ::std::vector
<char> matcher_matched(matrix
.RhsSize(), 0);
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
;
496 if (match_flags() & UnorderedMatcherRequire::Superset
) {
498 "where the following matchers don't match any elements:\n";
499 for (size_t mi
= 0; mi
< matcher_matched
.size(); ++mi
) {
500 if (matcher_matched
[mi
]) continue;
502 if (listener
->IsInterested()) {
503 *listener
<< sep
<< "matcher #" << mi
<< ": ";
504 matcher_describers_
[mi
]->DescribeTo(listener
->stream());
510 if (match_flags() & UnorderedMatcherRequire::Subset
) {
512 "where the following elements don't match any matchers:\n";
513 const char* outer_sep
= "";
515 outer_sep
= "\nand ";
517 for (size_t ei
= 0; ei
< element_matched
.size(); ++ei
) {
518 if (element_matched
[ei
]) continue;
520 if (listener
->IsInterested()) {
521 *listener
<< outer_sep
<< sep
<< "element #" << ei
<< ": "
522 << element_printouts
[ei
];
531 bool UnorderedElementsAreMatcherImplBase::FindPairing(
532 const MatchMatrix
& matrix
, MatchResultListener
* listener
) const {
533 ElementMatcherPairs matches
= FindMaxBipartiteMatching(matrix
);
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());
547 if ((match_flags() & UnorderedMatcherRequire::Subset
) &&
548 max_flow
< matrix
.LhsSize()) {
549 if (listener
->IsInterested()) {
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());
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
;
572 } // namespace internal
573 } // namespace testing