-
Notifications
You must be signed in to change notification settings - Fork 1.2k
/
dependency_tracker.cc
288 lines (253 loc) · 10.7 KB
/
dependency_tracker.cc
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
#include "drake/systems/framework/dependency_tracker.h"
#include <algorithm>
#include "drake/common/unused.h"
namespace drake {
namespace systems {
namespace {
// For debugging use, provide an indent of 2*depth characters.
std::string Indent(int depth) {
std::string s;
for (int i = 0; i < depth; ++i) s += "| ";
return s;
}
} // namespace
// Our associated value has initiated a change (e.g. the associated value is
// time and someone advanced time). Short circuit if this is part of a change
// event that we have already heard about. Otherwise, let the subscribers know
// that things have changed. Update statistics.
void DependencyTracker::NoteValueChange(int64_t change_event) const {
DRAKE_LOGGER_DEBUG("Tracker '{}' value change event {} ...",
GetPathDescription(), change_event);
DRAKE_ASSERT(change_event > 0);
++num_value_change_notifications_received_;
if (last_change_event_ == change_event) {
++num_ignored_notifications_;
DRAKE_LOGGER_DEBUG(
"... ignoring repeated value change notification same change event.");
return;
}
last_change_event_ = change_event;
NotifySubscribers(change_event, 0);
}
// A prerequisite says it has changed. Short circuit if we've already heard
// about this change event. Otherwise, invalidate the associated cache entry and
// then pass on the bad news to our subscribers. Update statistics.
void DependencyTracker::NotePrerequisiteChange(
int64_t change_event,
const DependencyTracker& prerequisite,
int depth) const {
unused(Indent); // Avoid warning in non-Debug builds.
DRAKE_LOGGER_DEBUG(
"{}Tracker '{}': prerequisite '{}' changed (event {}) ...",
Indent(depth), GetPathDescription(), prerequisite.GetPathDescription(),
change_event);
DRAKE_ASSERT(change_event > 0);
DRAKE_ASSERT(HasPrerequisite(prerequisite)); // Expensive.
++num_prerequisite_notifications_received_;
if (last_change_event_ == change_event) {
++num_ignored_notifications_;
DRAKE_LOGGER_DEBUG(
"{}... ignoring repeated prereq change notification same change event.",
Indent(depth));
return;
}
last_change_event_ = change_event;
// Invalidate associated cache entry value if any.
cache_value_->mark_out_of_date();
// Follow up with downstream subscribers.
NotifySubscribers(change_event, depth);
}
void DependencyTracker::NotifySubscribers(int64_t change_event,
int depth) const {
DRAKE_LOGGER_DEBUG("{}... {} downstream subscribers.{}", Indent(depth),
num_subscribers(),
num_subscribers() > 0 ? " Notifying:" : "");
DRAKE_ASSERT(change_event > 0);
DRAKE_ASSERT(depth >= 0);
for (const DependencyTracker* subscriber : subscribers_) {
DRAKE_ASSERT(subscriber != nullptr);
DRAKE_LOGGER_DEBUG("{}->{}", Indent(depth),
subscriber->GetPathDescription());
subscriber->NotePrerequisiteChange(change_event, *this, depth + 1);
}
num_downstream_notifications_sent_ += num_subscribers();
}
// Given a DependencyTracker that is supposed to be a prerequisite to this
// one, subscribe to it. This is done only at Context allocation and copying
// so we can afford Release-build checks and general mucking about to make
// runtime execution fast.
void DependencyTracker::SubscribeToPrerequisite(
DependencyTracker* prerequisite) {
DRAKE_DEMAND(prerequisite != nullptr);
DRAKE_LOGGER_DEBUG("Tracker '{}' subscribing to prerequisite '{}'",
GetPathDescription(), prerequisite->GetPathDescription());
// Make sure we haven't already added this prerequisite.
DRAKE_ASSERT(!HasPrerequisite(*prerequisite)); // Expensive.
prerequisites_.push_back(prerequisite);
prerequisite->AddDownstreamSubscriber(*this);
}
void DependencyTracker::AddDownstreamSubscriber(
const DependencyTracker& subscriber) {
DRAKE_LOGGER_DEBUG("Tracker '{}' adding subscriber '{}'",
GetPathDescription(), subscriber.GetPathDescription());
// Make sure we haven't already added this subscriber.
DRAKE_ASSERT(!HasSubscriber(subscriber)); // Expensive.
// Subscriber must have *already* recorded this prerequisite.
DRAKE_ASSERT(subscriber.HasPrerequisite(*this)); // Expensive.
subscribers_.push_back(&subscriber);
}
namespace {
// Convenience function for linear search of a vector to see if it contains
// a given value.
template <typename T>
bool Contains(const T& value, const std::vector<T>& to_search) {
return std::find(to_search.begin(), to_search.end(), value)
!= to_search.end();
}
// Look for the given value and erase it. Fail if not found.
template <typename T>
void Remove(const T& value, std::vector<T>* to_search) {
auto found = std::find(to_search->begin(), to_search->end(), value);
DRAKE_DEMAND(found != to_search->end());
to_search->erase(found);
}
} // namespace
// Remove a subscription that we made earlier.
void DependencyTracker::UnsubscribeFromPrerequisite(
DependencyTracker* prerequisite) {
DRAKE_DEMAND(prerequisite != nullptr);
DRAKE_LOGGER_DEBUG("Tracker '{}' unsubscribing from prerequisite '{}'",
GetPathDescription(), prerequisite->GetPathDescription());
// Make sure we have already added this prerequisite.
DRAKE_ASSERT(HasPrerequisite(*prerequisite)); // Expensive.
Remove<const DependencyTracker*>(prerequisite, &prerequisites_);
prerequisite->RemoveDownstreamSubscriber(*this);
}
void DependencyTracker::RemoveDownstreamSubscriber(
const DependencyTracker& subscriber) {
DRAKE_LOGGER_DEBUG("Tracker '{}' removing subscriber '{}'",
GetPathDescription(), subscriber.GetPathDescription());
// Make sure we already added this subscriber.
DRAKE_ASSERT(HasSubscriber(subscriber)); // Expensive.
// Subscriber must have *already* removed this prerequisite.
DRAKE_ASSERT(!subscriber.HasPrerequisite(*this)); // Expensive.
Remove<const DependencyTracker*>(&subscriber, &subscribers_);
}
std::string DependencyTracker::GetPathDescription() const {
return GetSystemPathname() + ":" + description();
}
bool DependencyTracker::HasPrerequisite(
const DependencyTracker& prerequisite) const {
return Contains(&prerequisite, prerequisites_);
}
bool DependencyTracker::HasSubscriber(
const DependencyTracker& subscriber) const {
return Contains(&subscriber, subscribers_);
}
void DependencyTracker::ThrowIfBadDependencyTracker(
const internal::ContextMessageInterface* owning_subcontext,
const CacheEntryValue* cache_value) const {
if (owning_subcontext_ == nullptr) {
// Can't use FormatName() here because that depends on us having an owning
// context to talk to.
throw std::logic_error("DependencyTracker(" + description() + ")::" +
__func__ +
"(): tracker has no owning subcontext.");
}
if (owning_subcontext && owning_subcontext_ != owning_subcontext) {
throw std::logic_error(FormatName(__func__) + "wrong owning subcontext.");
}
if (cache_value_ == nullptr) {
throw std::logic_error(
FormatName(__func__) +
"no associated cache entry value (should at least be a dummy).");
}
if (cache_value && cache_value_ != cache_value) {
throw std::logic_error(FormatName(__func__) +
"wrong associated cache entry value.");
}
if (!ticket_.is_valid()) {
throw std::logic_error(FormatName(__func__) +
"dependency ticket invalid.");
}
if (last_change_event_ < -1) {
throw std::logic_error(FormatName(__func__) +
"last change event has an absurd value.");
}
if (num_value_change_notifications_received_ < 0 ||
num_prerequisite_notifications_received_ < 0 ||
num_ignored_notifications_ < 0 ||
num_downstream_notifications_sent_ < 0) {
throw std::logic_error(FormatName(__func__) +
"a counter has a negative value.");
}
}
void DependencyTracker::RepairTrackerPointers(
const DependencyTracker& source,
const DependencyTracker::PointerMap& tracker_map,
const internal::ContextMessageInterface* owning_subcontext, Cache* cache) {
DRAKE_DEMAND(owning_subcontext != nullptr);
DRAKE_DEMAND(cache != nullptr);
owning_subcontext_ = owning_subcontext;
// Set the cache entry pointer to refer to the new cache, either to a real
// CacheEntryValue or the cache's dummy value.
DRAKE_DEMAND(has_associated_cache_entry_ ==
source.has_associated_cache_entry_);
if (has_associated_cache_entry_) {
const CacheIndex source_index(source.cache_value_->cache_index());
cache_value_ = &cache->get_mutable_cache_entry_value(source_index);
DRAKE_LOGGER_DEBUG(
"Cloned tracker '{}' repairing cache entry {} invalidation to {:#x}.",
GetPathDescription(), source.cache_value_->cache_index(),
size_t(cache_value_));
} else {
cache_value_ = &cache->dummy_cache_entry_value();
}
// Set the subscriber pointers.
DRAKE_DEMAND(num_subscribers() == source.num_subscribers());
for (int i = 0; i < num_subscribers(); ++i) {
DRAKE_ASSERT(subscribers_[i] == nullptr);
auto map_entry = tracker_map.find(source.subscribers()[i]);
DRAKE_DEMAND(map_entry != tracker_map.end());
subscribers_[i] = map_entry->second;
}
// Set the prerequisite pointers.
DRAKE_DEMAND(num_prerequisites() == source.num_prerequisites());
for (int i = 0; i < num_prerequisites(); ++i) {
DRAKE_ASSERT(prerequisites_[i] == nullptr);
auto map_entry = tracker_map.find(source.prerequisites()[i]);
DRAKE_DEMAND(map_entry != tracker_map.end());
prerequisites_[i] = map_entry->second;
}
// This should never happen, but ...
ThrowIfBadDependencyTracker();
}
void DependencyGraph::AppendToTrackerPointerMap(
const DependencyGraph& clone,
DependencyTracker::PointerMap* tracker_map) const {
DRAKE_DEMAND(tracker_map != nullptr);
DRAKE_DEMAND(clone.trackers_size() == trackers_size());
for (DependencyTicket ticket(0); ticket < trackers_size(); ++ticket) {
if (!has_tracker(ticket))
continue;
const bool added = tracker_map->emplace(&get_tracker(ticket),
&clone.get_tracker(ticket)).second;
DRAKE_DEMAND(added); // Shouldn't have been there.
}
}
void DependencyGraph::RepairTrackerPointers(
const DependencyGraph& source,
const DependencyTracker::PointerMap& tracker_map,
const internal::ContextMessageInterface* owning_subcontext,
Cache* new_cache) {
DRAKE_DEMAND(owning_subcontext != nullptr);
owning_subcontext_ = owning_subcontext;
for (DependencyTicket ticket(0); ticket < trackers_size(); ++ticket) {
if (!has_tracker(ticket))
continue;
get_mutable_tracker(ticket).RepairTrackerPointers(
source.get_tracker(ticket), tracker_map, owning_subcontext, new_cache);
}
}
} // namespace systems
} // namespace drake