1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/optimizer/matcher/set_matcher.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include "duckdb/common/common.hpp"
12#include "duckdb/common/unordered_set.hpp"
13
14namespace duckdb {
15
16class SetMatcher {
17public:
18 //! The policy used by the SetMatcher
19 enum class Policy {
20 //! All entries have to be matched, and the matches have to be ordered
21 ORDERED,
22 //! All entries have to be matched, but the order of the matches does not matter
23 UNORDERED,
24 //! Only some entries have to be matched, the order of the matches does not matter
25 SOME,
26 //! Not initialized
27 INVALID
28 };
29
30 /* The double {{}} in the intializer for excluded_entries is intentional, workaround for bug in gcc-4.9 */
31 template <class T, class MATCHER>
32 static bool MatchRecursive(vector<unique_ptr<MATCHER>> &matchers, vector<reference<T>> &entries,
33 vector<reference<T>> &bindings, unordered_set<idx_t> excluded_entries, idx_t m_idx = 0) {
34 if (m_idx == matchers.size()) {
35 // matched all matchers!
36 return true;
37 }
38 // try to find a match for the current matcher (m_idx)
39 idx_t previous_binding_count = bindings.size();
40 for (idx_t e_idx = 0; e_idx < entries.size(); e_idx++) {
41 // first check if this entry has already been matched
42 if (excluded_entries.find(x: e_idx) != excluded_entries.end()) {
43 // it has been matched: skip this entry
44 continue;
45 }
46 // otherwise check if the current matcher matches this entry
47 if (matchers[m_idx]->Match(entries[e_idx], bindings)) {
48 // m_idx matches e_idx!
49 // check if we can find a complete match for this path
50 // first add e_idx to the new set of excluded entries
51 unordered_set<idx_t> new_excluded_entries;
52 new_excluded_entries = excluded_entries;
53 new_excluded_entries.insert(x: e_idx);
54 // then match the next matcher in the set
55 if (MatchRecursive(matchers, entries, bindings, new_excluded_entries, m_idx + 1)) {
56 // we found a match for this path! success
57 return true;
58 } else {
59 // we did not find a match! remove any bindings we added in the call to Match()
60 bindings.erase(bindings.begin() + previous_binding_count, bindings.end());
61 }
62 }
63 }
64 return false;
65 }
66
67 template <class T, class MATCHER>
68 static bool Match(vector<unique_ptr<MATCHER>> &matchers, vector<reference<T>> &entries,
69 vector<reference<T>> &bindings, Policy policy) {
70 if (policy == Policy::ORDERED) {
71 // ordered policy, count has to match
72 if (matchers.size() != entries.size()) {
73 return false;
74 }
75 // now entries have to match in order
76 for (idx_t i = 0; i < matchers.size(); i++) {
77 if (!matchers[i]->Match(entries[i], bindings)) {
78 return false;
79 }
80 }
81 return true;
82 } else {
83 if (policy == Policy::UNORDERED && matchers.size() != entries.size()) {
84 // unordered policy, count does not match: no match
85 return false;
86 } else if (policy == Policy::SOME && matchers.size() > entries.size()) {
87 // some policy, every matcher has to match a unique entry
88 // this is not possible if there are more matchers than entries
89 return false;
90 }
91 // now perform the actual matching
92 // every matcher has to match a UNIQUE entry
93 // we perform this matching in a recursive way
94 unordered_set<idx_t> excluded_entries;
95 if (!MatchRecursive(matchers, entries, bindings, excluded_entries)) {
96 return false;
97 }
98 return true;
99 }
100 }
101
102 template <class T, class MATCHER>
103 static bool Match(vector<unique_ptr<MATCHER>> &matchers, vector<unique_ptr<T>> &entries,
104 vector<reference<T>> &bindings, Policy policy) {
105 // convert vector of unique_ptr to vector of normal pointers
106 vector<reference<T>> ptr_entries;
107 for (auto &entry : entries) {
108 ptr_entries.push_back(*entry);
109 }
110 // then just call the normal match function
111 return Match(matchers, ptr_entries, bindings, policy);
112 }
113};
114
115} // namespace duckdb
116