Handle large, single direction timestamp outages when estimating time
Brian Smartt had the clever idea of taking the max of both directions.
This essentially warps any long stretches of time such that they always
stay above the other direction with more fresh timestamps. Because the
lines then don't cross, we can solve like we used to.
We only really need to introduce this concept into FindTimestamps.
Everything else works off a valid timestamp pair so it stays the same.
Add a test to reproduce this behavior (it happens occasionally in the
wild) and then fix it.
Change-Id: I999280fc1db1f178835092a8d024a9862144d7cb
Signed-off-by: Austin Schuh <austin.schuh@bluerivertech.com>
diff --git a/aos/events/logging/boot_timestamp.h b/aos/events/logging/boot_timestamp.h
index 7eead2e..d0fde73 100644
--- a/aos/events/logging/boot_timestamp.h
+++ b/aos/events/logging/boot_timestamp.h
@@ -19,6 +19,11 @@
return {boot, duration + d};
}
+ BootDuration operator-() const { return {boot, -duration}; }
+ BootDuration operator-(monotonic_clock::duration d) const {
+ return {boot, duration - d};
+ }
+
bool operator==(const BootDuration &m2) const {
return boot == m2.boot && duration == m2.duration;
}
diff --git a/aos/events/logging/logger_test.cc b/aos/events/logging/logger_test.cc
index ec273a8..bb5b41e 100644
--- a/aos/events/logging/logger_test.cc
+++ b/aos/events/logging/logger_test.cc
@@ -4297,6 +4297,58 @@
ConfirmReadable(filenames);
}
+// Tests that we properly handle what used to be a time violation in one
+// direction. This can occur when one direction goes down after sending some
+// data, but the other keeps working. The down direction ends up resolving to a
+// straight line in the noncausal filter, where the direction which is still up
+// can cross that line. Really, time progressed along just fine but we assumed
+// that the offset was a line when it could have deviated by up to 1ms/second.
+TEST_P(MultinodeLoggerTest, OneDirectionTimeDrift) {
+ std::vector<std::string> filenames;
+
+ CHECK_EQ(pi1_index_, 0u);
+ CHECK_EQ(pi2_index_, 1u);
+
+ time_converter_.AddNextTimestamp(
+ distributed_clock::epoch(),
+ {BootTimestamp::epoch(), BootTimestamp::epoch()});
+
+ const chrono::nanoseconds before_disconnect_duration =
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(1000), chrono::milliseconds(1000)});
+
+ const chrono::nanoseconds test_duration =
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(1000), chrono::milliseconds(1000)}) +
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(10000),
+ chrono::milliseconds(10000) - chrono::milliseconds(5)}) +
+ time_converter_.AddMonotonic(
+ {chrono::milliseconds(10000),
+ chrono::milliseconds(10000) + chrono::milliseconds(5)});
+
+ const std::string kLogfile =
+ aos::testing::TestTmpDir() + "/multi_logfile2.1/";
+ util::UnlinkRecursive(kLogfile);
+
+ {
+ LoggerState pi2_logger = MakeLogger(pi2_);
+ pi2_logger.StartLogger(kLogfile);
+ event_loop_factory_.RunFor(before_disconnect_duration);
+
+ pi2_->Disconnect(pi1_->node());
+
+ event_loop_factory_.RunFor(test_duration);
+ pi2_->Connect(pi1_->node());
+
+ event_loop_factory_.RunFor(chrono::milliseconds(5000));
+ pi2_logger.AppendAllFilenames(&filenames);
+ }
+
+ const std::vector<LogFile> sorted_parts = SortParts(filenames);
+ ConfirmReadable(filenames);
+}
+
} // namespace testing
} // namespace logger
} // namespace aos
diff --git a/aos/network/multinode_timestamp_filter.cc b/aos/network/multinode_timestamp_filter.cc
index 87b9a81..98ad185 100644
--- a/aos/network/multinode_timestamp_filter.cc
+++ b/aos/network/multinode_timestamp_filter.cc
@@ -73,8 +73,8 @@
clock_offset_filter_for_node_[node_a]) {
// There's something in this direction, so we don't need to check the
// opposite direction to confirm we have observations.
- if (!filter.filter->timestamps_empty(base_clock_[node_a].boot,
- base_clock_[filter.b_index].boot)) {
+ if (!filter.filter->timestamps_empty(
+ base_clock_[node_a].boot, base_clock_[filter.b_index].boot)) {
continue;
}
@@ -97,8 +97,8 @@
for (const struct FilterPair &filter : clock_offset_filter_for_node_[i]) {
// There's nothing in this direction, so there will be nothing to
// validate.
- if (filter.filter->timestamps_empty(base_clock_[i].boot,
- base_clock_[filter.b_index].boot)) {
+ if (filter.filter->timestamps_empty(
+ base_clock_[i].boot, base_clock_[filter.b_index].boot)) {
// For a boot to exist, we need to have some observations between it and
// another boot. We wouldn't bother to build a problem to solve for
// this node otherwise. Confirm that is true so we at least get
@@ -113,9 +113,11 @@
continue;
}
const bool iteration = filter.filter->ValidateSolution(
- filter.pointer, solution[i], solution[filter.b_index]);
+ filter.b_filter, filter.pointer, solution[i],
+ solution[filter.b_index]);
if (!iteration) {
- filter.filter->ValidateSolution(filter.pointer, solution[i], 0.0,
+ filter.filter->ValidateSolution(filter.b_filter, filter.pointer,
+ solution[i], 0.0,
solution[filter.b_index], 0.0);
}
@@ -164,8 +166,9 @@
const std::pair<NoncausalTimestampFilter::Pointer, double> offset_error =
filter.filter->OffsetError(
- filter.pointer, base_clock_[i], time_offsets(a_solution_index),
- base_clock_[filter.b_index], time_offsets(b_solution_index));
+ filter.b_filter, filter.pointer, base_clock_[i],
+ time_offsets(a_solution_index), base_clock_[filter.b_index],
+ time_offsets(b_solution_index));
const double error = 2.0 * (offset_error.second - kMinNetworkDelay);
filter.pointer = offset_error.first;
@@ -182,6 +185,12 @@
for (size_t i = 0; i < clock_offset_filter_for_node_.size(); ++i) {
for (const struct FilterPair &filter : clock_offset_filter_for_node_[i]) {
+ // If the gradient is 0, the hessian should also be 0.
+ if (filter.filter->timestamps_empty(base_clock_[i].boot,
+ base_clock_[filter.b_index].boot)) {
+ continue;
+ }
+
// Reminder, our cost function has the following form.
// ((tb - (1 + ma) ta - ba)^2
// We are ignoring the slope when taking the derivative and applying the
@@ -454,12 +463,12 @@
// report.
gradients[i].emplace_back(
std::string("- ") +
- filter.filter->DebugOffsetError(filter.pointer, base_clock_[i], 0.0,
- base_clock_[filter.b_index], 0.0, i,
- filter.b_index));
+ filter.filter->DebugOffsetError(
+ filter.b_filter, filter.pointer, base_clock_[i], 0.0,
+ base_clock_[filter.b_index], 0.0, i, filter.b_index));
gradients[filter.b_index].emplace_back(filter.filter->DebugOffsetError(
- filter.pointer, base_clock_[i], 0.0, base_clock_[filter.b_index],
- 0.0, i, filter.b_index));
+ filter.b_filter, filter.pointer, base_clock_[i], 0.0,
+ base_clock_[filter.b_index], 0.0, i, filter.b_index));
}
}
}
diff --git a/aos/network/multinode_timestamp_filter_test.cc b/aos/network/multinode_timestamp_filter_test.cc
index 49f20da..841ff4d 100644
--- a/aos/network/multinode_timestamp_filter_test.cc
+++ b/aos/network/multinode_timestamp_filter_test.cc
@@ -391,10 +391,10 @@
// Confirm that the error is almost equal for both directions. The solution
// is an integer solution, so there will be a little bit of error left over.
EXPECT_NEAR(
- a.OffsetError(NoncausalTimestampFilter::Pointer(),
+ a.OffsetError(nullptr, NoncausalTimestampFilter::Pointer(),
std::get<0>(result1)[0], 0.0, std::get<0>(result1)[1], 0.0)
.second -
- b.OffsetError(NoncausalTimestampFilter::Pointer(),
+ b.OffsetError(nullptr, NoncausalTimestampFilter::Pointer(),
std::get<0>(result1)[1], 0.0, std::get<0>(result1)[0],
0.0)
.second,
diff --git a/aos/network/timestamp_filter.cc b/aos/network/timestamp_filter.cc
index 1a7bc6d..de150c5 100644
--- a/aos/network/timestamp_filter.cc
+++ b/aos/network/timestamp_filter.cc
@@ -490,7 +490,8 @@
std::pair<Pointer, std::pair<std::tuple<BootTimestamp, BootDuration>,
std::tuple<BootTimestamp, BootDuration>>>
-NoncausalTimestampFilter::FindTimestamps(Pointer pointer, BootTimestamp ta_base,
+NoncausalTimestampFilter::FindTimestamps(const NoncausalTimestampFilter *other,
+ Pointer pointer, BootTimestamp ta_base,
double ta, size_t sample_boot) const {
CHECK_GE(ta, 0.0);
CHECK_LT(ta, 1.0);
@@ -498,7 +499,7 @@
// Since ta is less than an integer, and timestamps should be at least 1 ns
// apart, we can ignore ta if we make sure that the end of the segment is
// strictly > than ta_base.
- return FindTimestamps(pointer, ta_base, sample_boot);
+ return FindTimestamps(other, pointer, ta_base, sample_boot);
}
std::pair<
@@ -506,14 +507,68 @@
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
NoncausalTimestampFilter::SingleFilter::FindTimestamps(
- Pointer pointer, monotonic_clock::time_point ta_base, double ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const {
CHECK_GE(ta, 0.0);
CHECK_LT(ta, 1.0);
// Since ta is less than an integer, and timestamps should be at least 1 ns
// apart, we can ignore ta if we make sure that the end of the segment is
// strictly > than ta_base.
- return FindTimestamps(pointer, ta_base);
+ return FindTimestamps(other, pointer, ta_base);
+}
+
+std::pair<
+ Pointer,
+ std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
+NoncausalTimestampFilter::InterpolateWithOtherFilter(
+ Pointer pointer, monotonic_clock::time_point ta,
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t0,
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t1) {
+ // We have 2 timestamps bookending everything, and a list of points in the
+ // middle.
+ //
+ // There are really 3 cases. The time is before the hunk in the middle, after
+ // the hunk in the middle, or in the hunk in the middle.
+ if (ta <= std::get<0>(pointer.other_points_[0].second)) {
+ // We are before the hunk! Use the start point, and the beginning of the
+ // hunk.
+ t1 = pointer.other_points_[0].second;
+ CHECK_LE(
+ absl::int128(std::abs((std::get<1>(t1) - std::get<1>(t0)).count())) *
+ absl::int128(MaxVelocityRatio::den),
+ absl::int128((std::get<0>(t1) - std::get<0>(t0)).count()) *
+ absl::int128(MaxVelocityRatio::num))
+ << ": t0 " << TimeString(t0) << ", t1 " << TimeString(t1);
+ } else if (ta >
+ std::get<0>(pointer.other_points_[pointer.other_points_.size() - 1]
+ .second)) {
+ // We are after the hunk! Use the end point, and the end of the
+ // hunk.
+ t0 = pointer.other_points_[pointer.other_points_.size() - 1].second;
+ CHECK_LE(
+ absl::int128(std::abs((std::get<1>(t1) - std::get<1>(t0)).count())) *
+ absl::int128(MaxVelocityRatio::den),
+ absl::int128((std::get<0>(t1) - std::get<0>(t0)).count()) *
+ absl::int128(MaxVelocityRatio::num))
+ << ": t0 " << TimeString(t0) << ", t1 " << TimeString(t1);
+ } else {
+ // We are inside the hunk. Find the points bounding it.
+ CHECK_GT(pointer.other_points_.size(), 1u);
+
+ auto it = std::upper_bound(
+ pointer.other_points_.begin() + 1, pointer.other_points_.end() - 1, ta,
+ [](monotonic_clock::time_point ta,
+ std::pair<size_t, std::tuple<aos::monotonic_clock::time_point,
+ std::chrono::nanoseconds>>
+ t) { return ta < std::get<0>(t.second); });
+
+ t0 = (it - 1)->second;
+ t1 = it->second;
+ }
+ DCHECK_LT(std::get<0>(t0), std::get<0>(t1));
+ return std::make_pair(pointer, std::make_pair(t0, t1));
}
std::pair<
@@ -521,9 +576,13 @@
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
NoncausalTimestampFilter::SingleFilter::FindTimestamps(
- Pointer pointer, monotonic_clock::time_point ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const {
CHECK_GT(timestamps_size(), 1u);
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t0;
+ std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t1;
+
// boot_filter_ is non-null when the rest of the contents are valid. Make
// sure it's pointing to this filter, and the pointer is in bounds.
if (pointer.boot_filter_ != nullptr &&
@@ -557,13 +616,29 @@
<< std::get<1>(pointer.t1_).count() << "ns";
}
- std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t0 =
- timestamp(pointer.index_);
+ t0 = timestamp(pointer.index_);
if (ta >= std::get<0>(t0)) {
- std::tuple<monotonic_clock::time_point, chrono::nanoseconds> t1 =
- timestamp(pointer.index_ + 1);
+ t1 = timestamp(pointer.index_ + 1);
if (ta < std::get<0>(t1)) {
- return std::make_pair(pointer, std::make_pair(t0, t1));
+ if (pointer.other_points_.empty()) {
+ return std::make_pair(pointer, std::make_pair(t0, t1));
+ }
+
+ // Er, we shouldn't be able to have a non-empty other_points_ without
+ // having other and points...
+ CHECK(other != nullptr);
+ CHECK(!other->timestamps_empty());
+
+ // TODO(austin): Is there a cheaper way to verify nothing has changed?
+ // Should we add a generation counter of some sort?
+ for (const auto &point : pointer.other_points_) {
+ const auto other_point = other->timestamps_[point.first];
+ CHECK(std::get<0>(other_point) + std::get<1>(other_point) ==
+ std::get<0>(point.second))
+ << ": Cache changed";
+ }
+
+ return InterpolateWithOtherFilter(pointer, ta, t0, t1);
}
}
}
@@ -581,11 +656,65 @@
const size_t index = std::distance(timestamps_.begin(), it);
pointer.index_ = index - 1;
- std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t0 =
- pointer.t0_ = timestamp(index - 1);
- std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t1 =
- pointer.t1_ = timestamp(index);
+ t0 = timestamp(index - 1);
+ pointer.t0_ = t0;
+ t1 = timestamp(index);
+ pointer.t1_ = t1;
+ if (other != nullptr && !other->timestamps_empty()) {
+ // Ok, we now need to find all points within our range in the matched
+ // filter.
+ auto other_t0_it =
+ std::lower_bound(other->timestamps_.begin(), other->timestamps_.end(),
+ std::get<0>(pointer.t0_),
+ [](std::tuple<aos::monotonic_clock::time_point,
+ std::chrono::nanoseconds>
+ t,
+ monotonic_clock::time_point ta) {
+ return ta > std::get<0>(t) + std::get<1>(t);
+ });
+ auto other_t1_it = std::upper_bound(
+ other_t0_it, other->timestamps_.end(), std::get<0>(pointer.t1_),
+ [](monotonic_clock::time_point ta,
+ std::tuple<aos::monotonic_clock::time_point,
+ std::chrono::nanoseconds>
+ t) { return ta < std::get<0>(t) + std::get<1>(t); });
+
+ if (std::get<0>(*other_t0_it) + std::get<1>(*other_t0_it) <
+ std::get<0>(pointer.t1_)) {
+ pointer.other_points_.clear();
+
+ // Now, we've got a range. [other_t0_it, other_t1_it).
+ for (auto other_it = other_t0_it; other_it != other_t1_it; ++other_it) {
+ const std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>
+ flipped_point =
+ std::make_tuple(std::get<0>(*other_it) + std::get<1>(*other_it),
+ -std::get<1>(*other_it) - kMinNetworkDelay());
+
+ // If the new point from the opposite direction filter is below the
+ // interpolated value at that point, then the opposite direction point
+ // defines a new min and we should take it.
+ if (NoncausalTimestampFilter::InterpolateOffset(
+ pointer.t0_, pointer.t1_, std::get<0>(flipped_point)) >
+ std::get<1>(flipped_point)) {
+ // Add it to the list of points to consider.
+ pointer.other_points_.emplace_back(std::make_pair(
+ std::distance(other->timestamps_.begin(), other_it),
+ flipped_point));
+ }
+ }
+
+ if (pointer.other_points_.size() > 0) {
+ return InterpolateWithOtherFilter(pointer, ta, t0, t1);
+ }
+ }
+
+ // other_t0_it will always be > t0, even if it is at the end.
+ // 1) other_t0_it < t0
+ // 2) other_t0_it < t1
+ //
+ // t0_it will always be > x.
+ }
return std::make_pair(pointer, std::make_pair(t0, t1));
}
@@ -766,7 +895,8 @@
std::pair<Pointer, chrono::nanoseconds>
NoncausalTimestampFilter::SingleFilter::Offset(
- Pointer pointer, monotonic_clock::time_point ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const {
CHECK_GT(timestamps_size(), 0u);
if (IsOutsideSamples(ta, 0.)) {
// Special case when size = 1 or if we're asked to extrapolate to
@@ -781,7 +911,7 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta);
+ points = FindTimestamps(other, pointer, ta);
return std::make_pair(points.first,
NoncausalTimestampFilter::InterpolateOffset(
points.second.first, points.second.second, ta));
@@ -789,7 +919,8 @@
std::pair<Pointer, std::pair<chrono::nanoseconds, double>>
NoncausalTimestampFilter::SingleFilter::Offset(
- Pointer pointer, monotonic_clock::time_point ta_base, double ta) const {
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const {
CHECK_GT(timestamps_size(), 0u) << node_names_;
if (IsOutsideSamples(ta_base, ta)) {
// Special case size = 1 or ta_base before first timestamp or
@@ -809,7 +940,7 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta_base, ta);
+ points = FindTimestamps(other, pointer, ta_base, ta);
CHECK_LT(std::get<0>(points.second.first), std::get<0>(points.second.second));
// Return both the integer and double portion together to save a timestamp
// lookup.
@@ -823,13 +954,14 @@
}
std::pair<Pointer, double> NoncausalTimestampFilter::SingleFilter::OffsetError(
- Pointer pointer, aos::monotonic_clock::time_point ta_base, double ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base, double tb) const {
NormalizeTimestamps(&ta_base, &ta);
NormalizeTimestamps(&tb_base, &tb);
const std::pair<Pointer, std::pair<std::chrono::nanoseconds, double>> offset =
- Offset(pointer, ta_base, ta);
+ Offset(other, pointer, ta_base, ta);
// Compute the integer portion first, and the double portion second. Subtract
// the results of each. This handles large offsets without losing precision.
@@ -840,8 +972,9 @@
}
std::string NoncausalTimestampFilter::DebugOffsetError(
- Pointer pointer, BootTimestamp ta_base, double ta, BootTimestamp tb_base,
- double tb, size_t node_a, size_t node_b) const {
+ const NoncausalTimestampFilter *other, Pointer pointer,
+ BootTimestamp ta_base, double ta, BootTimestamp tb_base, double tb,
+ size_t node_a, size_t node_b) const {
NormalizeTimestamps(&ta_base, &ta);
NormalizeTimestamps(&tb_base, &tb);
@@ -869,7 +1002,13 @@
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>
- points = f->filter.FindTimestamps(pointer, ta_base.time, ta).second;
+ points = f->filter
+ .FindTimestamps(
+ other == nullptr
+ ? nullptr
+ : &other->filter(tb_base.boot, ta_base.boot)->filter,
+ pointer, ta_base.time, ta)
+ .second;
// As a reminder, our cost function is essentially:
// ((tb - ta - (ma ta + ba))^2
@@ -902,7 +1041,8 @@
}
bool NoncausalTimestampFilter::SingleFilter::ValidateSolution(
- Pointer pointer, aos::monotonic_clock::time_point ta_base, double ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base, double tb) const {
NormalizeTimestamps(&ta_base, &ta);
NormalizeTimestamps(&tb_base, &tb);
@@ -927,6 +1067,7 @@
// We want to do offset + ta > tb, but we need to do it with minimal
// numerical precision problems.
+ // See below for why this is a >=
if (static_cast<double>((offset_base + ta_base - tb_base).count()) >=
tb - ta - offset_remainder) {
LOG(ERROR) << node_names_ << " "
@@ -945,12 +1086,13 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta_base, ta);
+ points = FindTimestamps(other, pointer, ta_base, ta);
const chrono::nanoseconds offset_base =
NoncausalTimestampFilter::InterpolateOffset(
points.second.first, points.second.second, ta_base, ta);
const double offset = NoncausalTimestampFilter::InterpolateOffsetRemainder(
points.second.first, points.second.second, ta_base, ta);
+ // See below for why this is a >=
if (static_cast<double>((offset_base + ta_base - tb_base).count()) >=
tb - offset - ta) {
LOG(ERROR) << node_names_ << " "
@@ -964,7 +1106,8 @@
}
bool NoncausalTimestampFilter::SingleFilter::ValidateSolution(
- Pointer pointer, aos::monotonic_clock::time_point ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta,
aos::monotonic_clock::time_point tb) const {
CHECK_GT(timestamps_size(), 0u);
if (ta < std::get<0>(timestamp(0)) && has_popped_) {
@@ -981,6 +1124,9 @@
const chrono::nanoseconds offset =
NoncausalTimestampFilter::ExtrapolateOffset(reference_timestamp.second,
ta);
+ // Note: this needs to be >=. The simulation code doesn't give us a good
+ // way to preserve order well enough to have causality preserved when things
+ // happen at the same point in time.
if (offset + ta >= tb) {
LOG(ERROR) << node_names_ << " " << TimeString(ta, offset)
<< " > solution time " << tb;
@@ -993,10 +1139,14 @@
Pointer,
std::pair<std::tuple<monotonic_clock::time_point, chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, chrono::nanoseconds>>>
- points = FindTimestamps(pointer, ta);
+ points = FindTimestamps(other, pointer, ta);
const chrono::nanoseconds offset =
NoncausalTimestampFilter::InterpolateOffset(points.second.first,
points.second.second, ta);
+
+ // Note: this needs to be >=. The simulation code doesn't give us a good
+ // way to preserve order well enough to have causality preserved when things
+ // happen at the same point in time.
if (offset + ta >= tb) {
LOG(ERROR) << node_names_ << " " << TimeString(ta, offset)
<< " > solution time " << tb;
diff --git a/aos/network/timestamp_filter.h b/aos/network/timestamp_filter.h
index d85154e..fd430ce 100644
--- a/aos/network/timestamp_filter.h
+++ b/aos/network/timestamp_filter.h
@@ -25,6 +25,9 @@
return static_cast<double>(MaxVelocityRatio::num) /
static_cast<double>(MaxVelocityRatio::den);
}
+inline constexpr std::chrono::nanoseconds kMinNetworkDelay() {
+ return std::chrono::nanoseconds(2);
+}
// This class handles filtering differences between clocks across a network.
//
@@ -304,38 +307,58 @@
std::make_tuple(monotonic_clock::min_time, std::chrono::nanoseconds(0));
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t1_ =
std::make_tuple(monotonic_clock::min_time, std::chrono::nanoseconds(0));
+
+ // List of points and their associated times going the other way.
+ std::vector<std::pair<size_t, std::tuple<monotonic_clock::time_point,
+ std::chrono::nanoseconds>>>
+ other_points_;
};
// Returns the error between the offset in the provided timestamps, and the
// offset at ta. Also returns a pointer to the timestamps used for the
// lookup to be passed back in again for a more efficient second lookup.
- std::pair<Pointer, double> OffsetError(Pointer pointer,
+ std::pair<Pointer, double> OffsetError(const NoncausalTimestampFilter *other,
+ Pointer pointer,
logger::BootTimestamp ta_base,
double ta,
logger::BootTimestamp tb_base,
double tb) const {
const BootFilter *boot_filter = filter(pointer, ta_base.boot, tb_base.boot);
+ const SingleFilter *other_filter =
+ other == nullptr
+ ? nullptr
+ : other->maybe_single_filter(tb_base.boot, ta_base.boot);
std::pair<Pointer, double> result = boot_filter->filter.OffsetError(
- pointer, ta_base.time, ta, tb_base.time, tb);
+ other_filter, pointer, ta_base.time, ta, tb_base.time, tb);
result.first.boot_filter_ = boot_filter;
return result;
}
// Returns the string representation of 2 * OffsetError(ta, tb)
- std::string DebugOffsetError(Pointer pointer, logger::BootTimestamp ta_base,
+ std::string DebugOffsetError(const NoncausalTimestampFilter *other,
+ Pointer pointer, logger::BootTimestamp ta_base,
double ta, logger::BootTimestamp tb_base,
double tb, size_t node_a, size_t node_b) const;
// Confirms that the solution meets the constraints. Returns true on success.
- bool ValidateSolution(Pointer pointer, logger::BootTimestamp ta,
+ bool ValidateSolution(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta,
logger::BootTimestamp tb) const {
+ const SingleFilter *other_filter =
+ other == nullptr ? nullptr
+ : other->maybe_single_filter(tb.boot, ta.boot);
return filter(pointer, ta.boot, tb.boot)
- ->filter.ValidateSolution(pointer, ta.time, tb.time);
+ ->filter.ValidateSolution(other_filter, pointer, ta.time, tb.time);
}
- bool ValidateSolution(Pointer pointer, logger::BootTimestamp ta_base,
- double ta, logger::BootTimestamp tb_base,
- double tb) const {
+ bool ValidateSolution(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta_base, double ta,
+ logger::BootTimestamp tb_base, double tb) const {
+ const SingleFilter *other_filter =
+ other == nullptr
+ ? nullptr
+ : other->maybe_single_filter(tb_base.boot, ta_base.boot);
return filter(pointer, ta_base.boot, tb_base.boot)
- ->filter.ValidateSolution(pointer, ta_base.time, ta, tb_base.time, tb);
+ ->filter.ValidateSolution(other_filter, pointer, ta_base.time, ta,
+ tb_base.time, tb);
}
// Adds a new sample to our filtered timestamp list.
@@ -416,6 +439,10 @@
// Returns the next timestamp in the queue if available without incrementing
// the pointer. This, Consume, and FreezeUntil work together to allow
// tracking and freezing timestamps which have been combined externally.
+ //
+ // This doesn't report the virtual points added by the opposite filter
+ // because solving for them doesn't add any additional value. We will already
+ // be solving the other direction.
std::optional<std::tuple<logger::BootTimestamp, logger::BootDuration>>
Observe() const {
if (filters_.size() == 0u) {
@@ -478,20 +505,29 @@
// Public for testing.
// Returns the offset for the point in time, using the timestamps in the deque
// to form a polyline used to interpolate.
- logger::BootDuration Offset(Pointer pointer, logger::BootTimestamp ta,
+ logger::BootDuration Offset(const NoncausalTimestampFilter *other,
+ Pointer pointer, logger::BootTimestamp ta,
size_t sample_boot) const {
- return {
- sample_boot,
- filter(ta.boot, sample_boot)->filter.Offset(pointer, ta.time).second};
+ return {sample_boot,
+ filter(ta.boot, sample_boot)
+ ->filter
+ .Offset(other == nullptr
+ ? nullptr
+ : &other->filter(sample_boot, ta.boot)->filter,
+ pointer, ta.time)
+ .second};
}
- std::pair<logger::BootDuration, double> Offset(Pointer pointer,
- logger::BootTimestamp ta_base,
- double ta,
- size_t sample_boot) const {
+ std::pair<logger::BootDuration, double> Offset(
+ const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta_base, double ta, size_t sample_boot) const {
std::pair<Pointer, std::pair<std::chrono::nanoseconds, double>> result =
filter(ta_base.boot, sample_boot)
- ->filter.Offset(pointer, ta_base.time, ta);
+ ->filter.Offset(
+ other == nullptr
+ ? nullptr
+ : &other->filter(sample_boot, ta_base.boot)->filter,
+ pointer, ta_base.time, ta);
return std::make_pair(
logger::BootDuration{sample_boot, result.second.first},
result.second.second);
@@ -502,15 +538,18 @@
std::pair<Pointer,
std::pair<std::tuple<logger::BootTimestamp, logger::BootDuration>,
std::tuple<logger::BootTimestamp, logger::BootDuration>>>
- FindTimestamps(Pointer pointer, logger::BootTimestamp ta,
- size_t sample_boot) const {
+ FindTimestamps(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta, size_t sample_boot) const {
const BootFilter *boot_filter = filter(ta.boot, sample_boot);
std::pair<
Pointer,
std::pair<
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
- result = boot_filter->filter.FindTimestamps(pointer, ta.time);
+ result = boot_filter->filter.FindTimestamps(
+ other == nullptr ? nullptr
+ : &other->filter(sample_boot, ta.boot)->filter,
+ pointer, ta.time);
result.first.boot_filter_ = boot_filter;
return std::make_pair(
result.first,
@@ -529,7 +568,8 @@
std::pair<Pointer,
std::pair<std::tuple<logger::BootTimestamp, logger::BootDuration>,
std::tuple<logger::BootTimestamp, logger::BootDuration>>>
- FindTimestamps(Pointer pointer, logger::BootTimestamp ta_base, double ta,
+ FindTimestamps(const NoncausalTimestampFilter *other, Pointer pointer,
+ logger::BootTimestamp ta_base, double ta,
size_t sample_boot) const;
static std::chrono::nanoseconds InterpolateOffset(
@@ -585,14 +625,15 @@
std::pair<
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
- FindTimestamps(Pointer pointer, monotonic_clock::time_point ta) const;
+ FindTimestamps(const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const;
std::pair<
Pointer,
std::pair<
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
- FindTimestamps(Pointer pointer, monotonic_clock::time_point ta_base,
- double ta) const;
+ FindTimestamps(const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const;
// Check whether the given timestamp falls within our current samples
bool IsOutsideSamples(monotonic_clock::time_point ta_base, double ta) const;
@@ -603,11 +644,14 @@
GetReferenceTimestamp(monotonic_clock::time_point ta_base, double ta) const;
std::pair<Pointer, std::chrono::nanoseconds> Offset(
- Pointer pointer, monotonic_clock::time_point ta) const;
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta) const;
std::pair<Pointer, std::pair<std::chrono::nanoseconds, double>> Offset(
- Pointer pointer, monotonic_clock::time_point ta_base, double ta) const;
+ const SingleFilter *other, Pointer pointer,
+ monotonic_clock::time_point ta_base, double ta) const;
std::pair<Pointer, double> OffsetError(
- Pointer pointer, aos::monotonic_clock::time_point ta_base, double ta,
+ const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base, double tb) const;
bool has_unobserved_line() const;
@@ -675,9 +719,10 @@
}
// Confirms that the solution meets the constraints. Returns true on
// success.
- bool ValidateSolution(Pointer pointer, aos::monotonic_clock::time_point ta,
+ bool ValidateSolution(const SingleFilter *other, Pointer pointer,
+ aos::monotonic_clock::time_point ta,
aos::monotonic_clock::time_point tb) const;
- bool ValidateSolution(Pointer pointer,
+ bool ValidateSolution(const SingleFilter *other, Pointer pointer,
aos::monotonic_clock::time_point ta_base, double ta,
aos::monotonic_clock::time_point tb_base,
double tb) const;
@@ -819,6 +864,21 @@
return result;
}
+ static std::pair<
+ Pointer,
+ std::pair<
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>,
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds>>>
+ InterpolateWithOtherFilter(
+ Pointer pointer, monotonic_clock::time_point ta,
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t0,
+ std::tuple<monotonic_clock::time_point, std::chrono::nanoseconds> t1);
+
+ const SingleFilter *maybe_single_filter(int boota, int bootb) const {
+ const BootFilter *boot_filter = maybe_filter(boota, bootb);
+ return boot_filter == nullptr ? nullptr : &boot_filter->filter;
+ }
+
private:
std::vector<std::unique_ptr<BootFilter>> filters_;
diff --git a/aos/network/timestamp_filter_test.cc b/aos/network/timestamp_filter_test.cc
index bbfd437..5932e3d 100644
--- a/aos/network/timestamp_filter_test.cc
+++ b/aos/network/timestamp_filter_test.cc
@@ -956,110 +956,226 @@
filter.Sample(t2, o2);
filter.Sample(t3, o3);
- result = filter.FindTimestamps(Pointer(), e - chrono::microseconds(10), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e - chrono::microseconds(10), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e - chrono::microseconds(10), 0));
- result =
- filter.FindTimestamps(Pointer(), e - chrono::microseconds(10), 0.9, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e - chrono::microseconds(10), 0.9, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e - chrono::microseconds(10), 0.9, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e - chrono::microseconds(10), 0.9, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(0), 0);
+ result =
+ filter.FindTimestamps(nullptr, Pointer(), e + chrono::microseconds(0), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(0), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(0), 0.8, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(0), 0.8, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(0), 0.8, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(100), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(100), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(100), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(100), 0.7, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(100), 0.7, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t1, o1)),
::testing::Eq(std::make_tuple(t2, o2))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(100), 0.7, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(100), 0.7, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(1000), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1000), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(1000), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(1000), 0.0, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1000), 0.0, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(1000), 0.0, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(1000), 0.0, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(1500), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1500), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(1500), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(1500), 0.0, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(1500), 0.0, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(1500), 0.0, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(1500), 0.0, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(2000), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2000), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(2000), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(2000), 0.1, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2000), 0.1, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(2000), 0.1, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(2000), 0.1, 0));
- result = filter.FindTimestamps(Pointer(), e + chrono::microseconds(2500), 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2500), 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(result.first,
+ EXPECT_EQ(result, filter.FindTimestamps(nullptr, result.first,
e + chrono::microseconds(2500), 0));
- result =
- filter.FindTimestamps(Pointer(), e + chrono::microseconds(2500), 0.0, 0);
+ result = filter.FindTimestamps(nullptr, Pointer(),
+ e + chrono::microseconds(2500), 0.0, 0);
EXPECT_THAT(result.second,
::testing::Pair(::testing::Eq(std::make_tuple(t2, o2)),
::testing::Eq(std::make_tuple(t3, o3))));
- EXPECT_EQ(result, filter.FindTimestamps(
- result.first, e + chrono::microseconds(2500), 0.0, 0));
+ EXPECT_EQ(result,
+ filter.FindTimestamps(nullptr, result.first,
+ e + chrono::microseconds(2500), 0.0, 0));
+}
+
+// Tests that when we have a paired filter with overlapping lines, we properly
+// stay above the other filter.
+//
+// This is the case when we have a large outage one direction but not the other,
+// and the lines cross (time drifts, so the straight line assumption from the
+// side with the outage is not relevant.).
+TEST_F(NoncausalTimestampFilterTest, FindTimestampsWithOther) {
+ const BootTimestamp e{0, monotonic_clock::epoch()};
+ // Note: t1, t2, t3 need to be picked such that the slop is small so filter
+ // doesn't modify the timestamps.
+ const BootTimestamp t1_a = e + chrono::nanoseconds(0);
+ const BootDuration o1_a{0, chrono::nanoseconds(100)};
+ const BootTimestamp t2_a = e + chrono::microseconds(1000);
+ const BootDuration o2_a{0, chrono::nanoseconds(100)};
+
+ const BootTimestamp t1_b = e + chrono::nanoseconds(100);
+ const BootDuration o1_b{0, -chrono::nanoseconds(105)};
+ const BootTimestamp t2_b = e + chrono::microseconds(200);
+ const BootDuration o2_b{0, -chrono::nanoseconds(101)};
+ const BootTimestamp t3_b = e + chrono::microseconds(300);
+ const BootDuration o3_b{0, -chrono::nanoseconds(101)};
+
+ TestingNoncausalTimestampFilter filter_a(node_a, node_b);
+ TestingNoncausalTimestampFilter filter_b(node_b, node_a);
+
+ std::pair<Pointer,
+ std::pair<std::tuple<logger::BootTimestamp, logger::BootDuration>,
+ std::tuple<logger::BootTimestamp, logger::BootDuration>>>
+ result;
+
+ filter_a.Sample(t1_a, o1_a);
+ filter_a.Sample(t2_a, o2_a);
+
+ filter_b.Sample(t1_b, o1_b);
+ filter_b.Sample(t2_b, o2_b);
+ filter_b.Sample(t3_b, o3_b);
+
+ // Confirm the problem statement is reasonable... We've had enough trouble
+ // here in the past.
+ EXPECT_TRUE(
+ filter_a.ValidateSolution(&filter_b, Pointer(), t1_a, t1_a + o1_a + chrono::nanoseconds(1)));
+ EXPECT_TRUE(
+ filter_a.ValidateSolution(&filter_b, Pointer(), t2_a, t2_a + o2_a + chrono::nanoseconds(1)));
+
+ EXPECT_TRUE(
+ filter_b.ValidateSolution(&filter_a, Pointer(), t1_b, t1_b + o1_b + chrono::nanoseconds(1)));
+ EXPECT_TRUE(
+ filter_b.ValidateSolution(&filter_a, Pointer(), t2_b, t2_b + o2_b + chrono::nanoseconds(1)));
+ EXPECT_TRUE(
+ filter_b.ValidateSolution(&filter_a, Pointer(), t3_b, t3_b + o3_b + chrono::nanoseconds(1)));
+
+ // Before the start
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e - chrono::microseconds(10), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(t1_a, o1_a)),
+ ::testing::Eq(std::make_tuple(
+ t2_b + o2_b, -o2_b - kMinNetworkDelay()))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e - chrono::microseconds(10), 0));
+
+ // Before the first opposite point.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(10), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(t1_a, o1_a)),
+ ::testing::Eq(std::make_tuple(
+ t2_b + o2_b, -o2_b - kMinNetworkDelay()))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(10), 0));
+
+ // Between the two opposite points.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(250), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(
+ t2_b + o2_b, -o2_b - kMinNetworkDelay())),
+ ::testing::Eq(std::make_tuple(
+ t3_b + o3_b, -o3_b - kMinNetworkDelay()))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(250), 0));
+
+ // After the last opposite point.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(450), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(
+ t3_b + o3_b, -o3_b - kMinNetworkDelay())),
+ ::testing::Eq(std::make_tuple(t2_a, o2_a))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(450), 0));
+
+ // And after the end.
+ result = filter_a.FindTimestamps(&filter_b, Pointer(),
+ e + chrono::microseconds(1100), 0);
+ EXPECT_THAT(result.second,
+ ::testing::Pair(::testing::Eq(std::make_tuple(
+ t3_b + o3_b, -o3_b - kMinNetworkDelay())),
+ ::testing::Eq(std::make_tuple(t2_a, o2_a))));
+ EXPECT_EQ(result, filter_a.FindTimestamps(&filter_b, result.first,
+ e + chrono::microseconds(1100), 0));
}
// Tests that Offset returns results indicative of it calling InterpolateOffset
@@ -1087,57 +1203,61 @@
filter.Sample(t1, o1);
// 1 point is handled properly.
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0), o1);
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0.0, 0), std::make_pair(o1, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0), o1);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0.0, 0),
+ std::make_pair(o1, 0.0));
// Check if we ask for something away from point that we get an offset
// based on the MaxVelocity allowed
const double offset_pre = -(t1.time - e.time).count() * kMaxVelocity();
- EXPECT_EQ(filter.Offset(Pointer(), e, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0),
o1 + chrono::nanoseconds(static_cast<int64_t>(offset_pre)));
- EXPECT_EQ(filter.Offset(Pointer(), e, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0.0, 0),
std::make_pair(o1, offset_pre));
double offset_post = -(t2.time - t1.time).count() * kMaxVelocity();
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0),
o1 + chrono::nanoseconds(static_cast<int64_t>(offset_post)));
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0.0, 0),
std::make_pair(o1, offset_post));
filter.Sample(t2, o2);
filter.Sample(t3, o3);
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0), o1);
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0), o2);
- EXPECT_EQ(filter.Offset(Pointer(), t3, 0), o3);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0), o1);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0), o2);
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t3, 0), o3);
- EXPECT_EQ(filter.Offset(Pointer(), t1, 0.0, 0), std::make_pair(o1, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t1, 0.0, 0),
+ std::make_pair(o1, 0.0));
EXPECT_EQ(
- filter.Offset(Pointer(),
+ filter.Offset(nullptr, Pointer(),
e + (t2.time_since_epoch() + t1.time_since_epoch()) / 2,
0.0, 0),
std::make_pair(o1, (o2d - o1d) / 2.));
- EXPECT_EQ(filter.Offset(Pointer(), t2, 0.0, 0), std::make_pair(o2, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t2, 0.0, 0),
+ std::make_pair(o2, 0.0));
EXPECT_EQ(
- filter.Offset(Pointer(),
+ filter.Offset(nullptr, Pointer(),
e + (t2.time_since_epoch() + t3.time_since_epoch()) / 2,
0.0, 0),
std::make_pair(o2, (o2d + o3d) / 2. - o2d));
- EXPECT_EQ(filter.Offset(Pointer(), t3, 0.0, 0), std::make_pair(o3, 0.0));
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t3, 0.0, 0),
+ std::make_pair(o3, 0.0));
// Check that we still get same answer for times before our sample data...
- EXPECT_EQ(filter.Offset(Pointer(), e, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0),
o1 + chrono::nanoseconds(static_cast<int64_t>(offset_pre)));
- EXPECT_EQ(filter.Offset(Pointer(), e, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), e, 0.0, 0),
std::make_pair(o1, offset_pre));
// ... and after
offset_post = -(t4.time - t3.time).count() * kMaxVelocity();
- EXPECT_EQ(filter.Offset(Pointer(), t4, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t4, 0),
(o3 + chrono::nanoseconds(static_cast<int64_t>(offset_post))));
- EXPECT_EQ(filter.Offset(Pointer(), t4, 0.0, 0),
+ EXPECT_EQ(filter.Offset(nullptr, Pointer(), t4, 0.0, 0),
std::make_pair(o3, offset_post));
}