1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
/**
* Copyright (C) 2016 MongoDB Inc.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License, version 3,
* as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* As a special exception, the copyright holders give permission to link the
* code of portions of this program with the OpenSSL library under certain
* conditions as described in each individual source file and distribute
* linked combinations including the program with the OpenSSL library. You
* must comply with the GNU Affero General Public License in all respects for
* all of the code used other than as permitted herein. If you modify file(s)
* with this exception, you may extend this exception to your version of the
* file(s), but you are not obligated to do so. If you do not wish to do so,
* delete this exception statement from your version. If you delete this
* exception statement from all source files in the program, then also delete
* it in the license file.
*/
#pragma once
#include <boost/optional.hpp>
#include <vector>
#include "mongo/base/status.h"
#include "mongo/db/namespace_string.h"
#include "mongo/db/query/collation/collator_interface.h"
#include "mongo/stdx/unordered_map.h"
#include "mongo/stdx/unordered_set.h"
#include "mongo/util/string_map.h"
namespace mongo {
class ViewDefinition;
/**
* Represents the dependencies of views on other namespaces and validates that this graph is acyclic
* and smaller than the maximum diameter. It also checks that the views in each connected component
* have compatible collations, and that all possible view pipelines stay within the maximum size in
* bytes.
*
* This is owned and managed by the ViewCatalog.
*/
class ViewGraph {
MONGO_DISALLOW_COPYING(ViewGraph);
public:
static const int kMaxViewDepth;
static const int kMaxViewPipelineSizeBytes;
ViewGraph() = default;
/**
* Inserts a new node for 'view' in the graph, which must not already be present. 'refs'
* contains the list of namespaces referred to by the view in its "viewOn" or "pipeline".
* 'pipelineSize' is the size of the view's pipeline, in bytes. If inserting the view would
* violate one of the graph's validity properties, the insertion is reverted and a non-OK status
* is returned.
*
* This method is intended for validating a view that is created or modified by a user
* operation.
*/
Status insertAndValidate(const ViewDefinition& view,
const std::vector<NamespaceString>& refs,
int pipelineSize);
/**
* Like insertAndValidate(), inserts a new node for 'view' in the graph, which must not already
* be present. However, no validation is performed. The insertion is not rolled back even if it
* puts the graph into an invalid state.
*
* This method is intended for quickly repopulating the graph with view definitions that are
* assumed to be already valid.
*/
void insertWithoutValidating(const ViewDefinition& view,
const std::vector<NamespaceString>& refs,
int pipelineSize);
/**
* Called when a view is removed from the catalog. If the view does not exist in the graph it is
* a no-op. The view may also have a cycle or max diameter through it.
*/
void remove(const NamespaceString& viewNss);
/**
* Deletes the view graph and all references to namespaces.
*/
void clear();
/**
* Returns the number of namespaces tracked by the view graph. Only exposed for testing.
*/
size_t size() const;
private:
// A graph node represents a namespace. We say that a node A is a parent of B if A is a view and
// it references B via its "viewOn" or $lookup/$graphLookup/$facet in its "pipeline".
//
// This node represents a view namespace if and only if 'children' is nonempty and 'collator' is
// set.
struct Node {
/**
* Returns true if this node represents a view.
*/
bool isView() const {
invariant(children.empty() == !static_cast<bool>(collator));
return !children.empty();
}
// The fully-qualified namespace that this node represents.
std::string ns;
// Represents the namespaces depended on by this view. A view may refer to the same child
// more than once, but we store the children as a set because each namespace need not be
// traversed more than once.
stdx::unordered_set<uint64_t> children;
// Represents the views that depend on this namespace.
stdx::unordered_set<uint64_t> parents;
// When set, this is an unowned pointer to the view's collation, or nullptr if the view has
// the binary collation. When not set, this namespace is not a view and we don't care about
// its collator.
boost::optional<const CollatorInterface*> collator;
// The size of this view's "pipeline", in bytes.
int size = 0;
};
// Bookkeeping for graph traversals.
struct NodeStats {
bool checked = false;
int height = 0;
int cumulativeSize = 0;
};
using StatsMap = stdx::unordered_map<uint64_t, NodeStats>;
/**
* Recursively validates the parents of 'currentId', filling out statistics about the node
* represented by that id in 'statsMap'. The recursion level is tracked in 'currentDepth' to
* limit recursive calls.
*
* A non-OK status is returned if 'currentId' or its parents violate any of the graph's
* validity properties.
*/
Status _validateParents(uint64_t currentId, int currentDepth, StatsMap* statsMap);
/**
* Recursively validates the children of 'currentId', filling out statistics about the node
* represented by that id in 'statsMap'. The recursion level is tracked in 'currentDepth' to
* limit recursive calls. Both 'startingId' and 'traversalIds' are used to detect cycles.
*
* A non-OK status is returned if 'currentId' or its children violate any of the graph's
* validity properties.
*/
Status _validateChildren(uint64_t startingId,
uint64_t currentId,
int currentDepth,
StatsMap* statsMap,
std::vector<uint64_t>* traversalIds);
/**
* Gets the id for this namespace, and creates an id if it doesn't exist.
*/
uint64_t _getNodeId(const NamespaceString& ns);
// Maps namespaces to an internal node id. A mapping exists for every namespace referenced,
// i.e. existing views, collections, and non-existing namespaces.
StringMap<uint64_t> _namespaceIds;
// Maps node ids to nodes. There is a 1-1 correspondence with _namespaceIds, hence the lifetime
// of a node is the same as the lifetime as its corresponding node id.
stdx::unordered_map<uint64_t, Node> _graph;
uint64_t _idCounter = 0;
};
} // namespace mongo
|
