From 39d8252300015c26f1932cff42032613fdb36a09 Mon Sep 17 00:00:00 2001 From: Gil Date: Fri, 19 Jan 2018 12:27:11 -0800 Subject: Port comparison to C++ (#678) This reimplements our comparison functions as C++ Comparators and then provides compatibility shims for interoperating with existing Objective-C usage. A few specialized comparators aren't suitable for porting but only have a single usage (e.g. CompareBytes for comparing NSData * instances). In these cases I've moved them into the caller. * Use int32_t for typeof(ID) in FSTDocumentReference * Migrate callers of FSTComparison.h to Objective-C++ * Port comparison to C++ * Migrate usages of FSTComparison.h to C++ equivalents * Remove FSTComparison --- .../src/firebase/firestore/util/CMakeLists.txt | 3 + .../core/src/firebase/firestore/util/comparison.cc | 112 +++++++++++ .../core/src/firebase/firestore/util/comparison.h | 181 ++++++++++++++++++ .../src/firebase/firestore/util/string_apple.h | 13 ++ .../test/firebase/firestore/util/CMakeLists.txt | 1 + .../firebase/firestore/util/comparison_test.cc | 210 +++++++++++++++++++++ 6 files changed, 520 insertions(+) create mode 100644 Firestore/core/src/firebase/firestore/util/comparison.cc create mode 100644 Firestore/core/src/firebase/firestore/util/comparison.h create mode 100644 Firestore/core/test/firebase/firestore/util/comparison_test.cc (limited to 'Firestore/core') diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt index 737173b..09db164 100644 --- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt +++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt @@ -49,6 +49,7 @@ cc_library( string_apple.h DEPENDS FirebaseCore + absl_strings EXCLUDE_FROM_ALL ) @@ -106,6 +107,8 @@ cc_library( SOURCES autoid.cc autoid.h + comparison.cc + comparison.h config.h firebase_assert.h log.h diff --git a/Firestore/core/src/firebase/firestore/util/comparison.cc b/Firestore/core/src/firebase/firestore/util/comparison.cc new file mode 100644 index 0000000..4bef843 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/comparison.cc @@ -0,0 +1,112 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Firestore/core/src/firebase/firestore/util/comparison.h" + +#include + +#include + +namespace firebase { +namespace firestore { +namespace util { + +bool Comparator::operator()( + const absl::string_view& left, const absl::string_view& right) const { + // TODO(wilhuff): truncation aware comparison + return left < right; +} + +bool Comparator::operator()(double left, double right) const { + // NaN sorts equal to itself and before any other number. + if (left < right) { + return true; + } else if (left >= right) { + return false; + } else { + // One or both left and right is NaN. + return isnan(left) && !isnan(right); + } +} + +static constexpr double INT64_MIN_VALUE_AS_DOUBLE = + static_cast(std::numeric_limits::min()); + +static constexpr double INT64_MAX_VALUE_AS_DOUBLE = + static_cast(std::numeric_limits::max()); + +ComparisonResult CompareMixedNumber(double double_value, int64_t int64_value) { + // LLONG_MIN has an exact representation as double, so to check for a value + // outside the range representable by long, we have to check for strictly less + // than LLONG_MIN. Note that this also handles negative infinity. + if (double_value < INT64_MIN_VALUE_AS_DOUBLE) { + return ComparisonResult::Ascending; + } + + // LLONG_MAX has no exact representation as double (casting as we've done + // makes 2^63, which is larger than LLONG_MAX), so consider any value greater + // than or equal to the threshold to be out of range. This also handles + // positive infinity. + if (double_value >= INT64_MAX_VALUE_AS_DOUBLE) { + return ComparisonResult::Descending; + } + + // In Firestore NaN is defined to compare before all other numbers. + if (isnan(double_value)) { + return ComparisonResult::Ascending; + } + + auto double_as_int64 = static_cast(double_value); + ComparisonResult cmp = Compare(double_as_int64, int64_value); + if (cmp != ComparisonResult::Same) { + return cmp; + } + + // At this point the long representations are equal but this could be due to + // rounding. + double int64_as_double = static_cast(int64_value); + return Compare(double_value, int64_as_double); +} + +/** Helper to normalize a double and then return the raw bits as a uint64_t. */ +uint64_t DoubleBits(double d) { + if (isnan(d)) { + d = NAN; + } + + // Unlike C, C++ does not define type punning through a union type. + + // TODO(wilhuff): replace with absl::bit_cast + static_assert(sizeof(double) == sizeof(uint64_t), "doubles must be 8 bytes"); + uint64_t bits; + memcpy(&bits, &d, sizeof(bits)); + return bits; +} + +bool DoubleBitwiseEquals(double left, double right) { + return DoubleBits(left) == DoubleBits(right); +} + +size_t DoubleBitwiseHash(double d) { + uint64_t bits = DoubleBits(d); + // Note that x ^ (x >> 32) works fine for both 32 and 64 bit definitions of + // size_t + return static_cast(bits) ^ static_cast(bits >> 32); +} + +} // namespace util +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/src/firebase/firestore/util/comparison.h b/Firestore/core/src/firebase/firestore/util/comparison.h new file mode 100644 index 0000000..6fd1e2b --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/comparison.h @@ -0,0 +1,181 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_COMPARISON_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_COMPARISON_H_ + +#if __OBJC__ +#import +#endif + +#include +#include + +#include +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/string_apple.h" +#include "absl/strings/string_view.h" + +namespace firebase { +namespace firestore { +namespace util { + +/** + * An enumeration describing the result of a three-way comparison among + * strongly-ordered values (i.e. where comparison between values always yields + * less-than, equal-to, or greater-than). + * + * This is equivalent to: + * + * * NSComparisonResult from the iOS/macOS Foundation framework. + * * std::strong_ordering from C++20 + * + * The values of the constants are specifically chosen so as to make casting + * between this type and NSComparisonResult possible. + */ +enum class ComparisonResult { + /** The left hand side was less than the right. */ + Ascending = -1, + + /** The left hand side was equal to the right. */ + Same = 0, + + /** The left hand side was greater than the right. */ + Descending = 1 +}; + +/** + * Returns the reverse order (i.e. Ascending => Descending) etc. + */ +constexpr ComparisonResult ReverseOrder(ComparisonResult result) { + return static_cast(-static_cast(result)); +} + +/** + * A generalized comparator for types in Firestore, with ordering defined + * according to Firestore's semantics. This is useful as argument to e.g. + * std::sort. + * + * Comparators are only defined for the limited set of types for which + * Firestore defines an ordering. + */ +template +struct Comparator { + // By default comparison is not defined +}; + +/** Compares two strings. */ +template <> +struct Comparator { + bool operator()(const absl::string_view& left, + const absl::string_view& right) const; +}; + +/** Compares two bools: false < true. */ +template <> +struct Comparator : public std::less {}; + +/** Compares two int32_t. */ +template <> +struct Comparator : public std::less {}; + +/** Compares two int64_t. */ +template <> +struct Comparator : public std::less {}; + +/** Compares two doubles (using Firestore semantics for NaN). */ +template <> +struct Comparator { + bool operator()(double left, double right) const; +}; + +/** Compare two byte sequences. */ +// TODO(wilhuff): perhaps absl::Span would be better? +template <> +struct Comparator> + : public std::less> {}; + +/** + * Perform a three-way comparison between the left and right values using + * the appropriate Comparator for the values based on their type. + */ +template +ComparisonResult Compare(const T& left, const T& right) { + Comparator less_than; + if (less_than(left, right)) { + return ComparisonResult::Ascending; + } else if (less_than(right, left)) { + return ComparisonResult::Descending; + } else { + return ComparisonResult::Same; + } +} + +#if __OBJC__ +/** + * Returns true if the given ComparisonResult and NSComparisonResult have the + * same integer values (at compile time). + */ +constexpr bool EqualValue(ComparisonResult lhs, NSComparisonResult rhs) { + return static_cast(lhs) == static_cast(rhs); +} + +/** + * Performs a three-way comparison, identically to Compare, but converts the + * result to an NSComparisonResult. + * + * This function exists for interoperation with Objective-C++ and should + * eventually be removed. + */ +template +inline NSComparisonResult WrapCompare(const T& left, const T& right) { + static_assert(EqualValue(ComparisonResult::Ascending, NSOrderedAscending), + "Ascending invalid"); + static_assert(EqualValue(ComparisonResult::Same, NSOrderedSame), + "Same invalid"); + static_assert(EqualValue(ComparisonResult::Descending, NSOrderedDescending), + "Descending invalid"); + + return static_cast(Compare(left, right)); +} +#endif + +/** Compares a double and an int64_t. */ +ComparisonResult CompareMixedNumber(double doubleValue, int64_t longValue); + +/** Normalizes a double and then return the raw bits as a uint64_t. */ +uint64_t DoubleBits(double d); + +/** + * Compares the bitwise representation of two doubles, but normalizes NaN + * values. This is similar to what the backend and android clients do, including + * comparing -0.0 as not equal to 0.0. + */ +bool DoubleBitwiseEquals(double left, double right); + +/** + * Computes a bitwise hash of a double, but normalizes NaN values, suitable for + * use when using FSTDoublesAreBitwiseEqual for equality. + */ +size_t DoubleBitwiseHash(double d); + +} // namespace util +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_COMPARISON_H_ diff --git a/Firestore/core/src/firebase/firestore/util/string_apple.h b/Firestore/core/src/firebase/firestore/util/string_apple.h index e1be8c3..108ade7 100644 --- a/Firestore/core/src/firebase/firestore/util/string_apple.h +++ b/Firestore/core/src/firebase/firestore/util/string_apple.h @@ -17,8 +17,13 @@ #ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_APPLE_H_ #define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_APPLE_H_ +// Everything in this header exists for compatibility with Objective-C. +#if __OBJC__ + #import +#include "absl/strings/string_view.h" + namespace firebase { namespace firestore { namespace util { @@ -32,8 +37,16 @@ inline NSString* WrapNSStringNoCopy(const char* c_str) { freeWhenDone:NO]; } +// Creates an absl::string_view wrapper for the contents of the given NSString. +inline absl::string_view MakeStringView(NSString* str) { + return absl::string_view( + [str UTF8String], [str lengthOfBytesUsingEncoding:NSUTF8StringEncoding]); +} + } // namespace util } // namespace firestore } // namespace firebase +#endif // __OBJC__ + #endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_APPLE_H_ diff --git a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt index 468c62e..5e7612c 100644 --- a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt +++ b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt @@ -36,6 +36,7 @@ cc_test( firebase_firestore_util_test SOURCES autoid_test.cc + comparison_test.cc string_printf_test.cc DEPENDS firebase_firestore_util diff --git a/Firestore/core/test/firebase/firestore/util/comparison_test.cc b/Firestore/core/test/firebase/firestore/util/comparison_test.cc new file mode 100644 index 0000000..ecbed4a --- /dev/null +++ b/Firestore/core/test/firebase/firestore/util/comparison_test.cc @@ -0,0 +1,210 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Firestore/core/src/firebase/firestore/util/comparison.h" + +#include + +#include + +#include "Firestore/core/src/firebase/firestore/util/string_printf.h" +#include "gtest/gtest.h" + +namespace firebase { +namespace firestore { +namespace util { + +#define ASSERT_SAME(comparison) \ + do { \ + ASSERT_EQ(ComparisonResult::Same, comparison); \ + } while (0) + +#define ASSERT_ASCENDING(comparison) \ + do { \ + ASSERT_EQ(ComparisonResult::Ascending, comparison); \ + } while (0) + +#define ASSERT_DESCENDING(comparison) \ + do { \ + ASSERT_EQ(ComparisonResult::Descending, comparison); \ + } while (0) + +TEST(Comparison, ReverseOrder) { + ASSERT_ASCENDING(ReverseOrder(ComparisonResult::Descending)); + ASSERT_DESCENDING(ReverseOrder(ComparisonResult::Ascending)); + ASSERT_SAME(ReverseOrder(ComparisonResult::Same)); +} + +TEST(Comparison, StringCompare) { + ASSERT_ASCENDING(Compare("", "a")); + ASSERT_ASCENDING(Compare("a", "b")); + ASSERT_ASCENDING(Compare("a", "aa")); + + ASSERT_DESCENDING(Compare("a", "")); + ASSERT_DESCENDING(Compare("b", "a")); + ASSERT_DESCENDING(Compare("aa", "a")); + + ASSERT_SAME(Compare("", "")); + ASSERT_SAME(Compare("", std::string())); + ASSERT_SAME(Compare("a", "a")); +} + +TEST(Comparison, BooleanCompare) { + ASSERT_SAME(Compare(false, false)); + ASSERT_SAME(Compare(true, true)); + ASSERT_ASCENDING(Compare(false, true)); + ASSERT_DESCENDING(Compare(true, false)); +} + +TEST(Comparison, DoubleCompare) { + ASSERT_SAME(Compare(NAN, NAN)); + ASSERT_ASCENDING(Compare(NAN, 0)); + ASSERT_DESCENDING(Compare(0, NAN)); + + ASSERT_SAME(Compare(-INFINITY, -INFINITY)); + ASSERT_SAME(Compare(INFINITY, INFINITY)); + ASSERT_ASCENDING(Compare(-INFINITY, INFINITY)); + ASSERT_DESCENDING(Compare(INFINITY, -INFINITY)); + + ASSERT_SAME(Compare(0, 0)); + ASSERT_SAME(Compare(-0, -0)); + ASSERT_SAME(Compare(-0, 0)); +} + +#define ASSERT_BIT_EQUALS(expected, actual) \ + do { \ + uint64_t expectedBits = DoubleBits(expected); \ + uint64_t actualBits = DoubleBits(actual); \ + if (expectedBits != actualBits) { \ + std::string message = StringPrintf( \ + "Expected <%f> to compare equal to <%f> " \ + "with bits <%llX> equal to <%llX>", \ + actual, expected, actualBits, expectedBits); \ + FAIL() << message; \ + } \ + } while (0); + +#define ASSERT_MIXED_SAME(doubleValue, longValue) \ + do { \ + ComparisonResult result = CompareMixedNumber(doubleValue, longValue); \ + if (result != ComparisonResult::Same) { \ + std::string message = StringPrintf( \ + "Expected <%f> to compare equal to <%lld>", doubleValue, longValue); \ + FAIL() << message; \ + } \ + } while (0); + +#define ASSERT_MIXED_DESCENDING(doubleValue, longValue) \ + do { \ + ComparisonResult result = CompareMixedNumber(doubleValue, longValue); \ + if (result != ComparisonResult::Descending) { \ + std::string message = StringPrintf( \ + "Expected <%f> to compare equal to <%lld>", doubleValue, longValue); \ + FAIL() << message; \ + } \ + } while (0); + +#define ASSERT_MIXED_ASCENDING(doubleValue, longValue) \ + do { \ + ComparisonResult result = CompareMixedNumber(doubleValue, longValue); \ + if (result != ComparisonResult::Ascending) { \ + std::string message = StringPrintf( \ + "Expected <%f> to compare equal to <%lld>", doubleValue, longValue); \ + FAIL() << message; \ + } \ + } while (0); + +TEST(Comparison, MixedNumberCompare) { + // Infinities + ASSERT_MIXED_ASCENDING(-INFINITY, LLONG_MIN); + ASSERT_MIXED_ASCENDING(-INFINITY, LLONG_MAX); + ASSERT_MIXED_ASCENDING(-INFINITY, 0LL); + + ASSERT_MIXED_DESCENDING(INFINITY, LLONG_MIN); + ASSERT_MIXED_DESCENDING(INFINITY, LLONG_MAX); + ASSERT_MIXED_DESCENDING(INFINITY, 0LL); + + // NaN + ASSERT_MIXED_ASCENDING(NAN, LLONG_MIN); + ASSERT_MIXED_ASCENDING(NAN, LLONG_MAX); + ASSERT_MIXED_ASCENDING(NAN, 0LL); + + // Large values (note DBL_MIN is positive and near zero). + ASSERT_MIXED_ASCENDING(-DBL_MAX, LLONG_MIN); + + // Tests around LLONG_MIN + ASSERT_BIT_EQUALS((double)LLONG_MIN, -0x1.0p63); + ASSERT_MIXED_SAME(-0x1.0p63, LLONG_MIN); + ASSERT_MIXED_ASCENDING(-0x1.0p63, LLONG_MIN + 1); + + ASSERT_LT(-0x1.0000000000001p63, -0x1.0p63); + ASSERT_MIXED_ASCENDING(-0x1.0000000000001p63, LLONG_MIN); + ASSERT_MIXED_DESCENDING(-0x1.FFFFFFFFFFFFFp62, LLONG_MIN); + + // Tests around LLONG_MAX + // Note LLONG_MAX cannot be exactly represented by a double, so the system + // rounds it to the nearest double, which is 2^63. This number, in turn is + // larger than the maximum representable as a long. + ASSERT_BIT_EQUALS(0x1.0p63, (double)LLONG_MAX); + ASSERT_MIXED_DESCENDING(0x1.0p63, LLONG_MAX); + + // The largest value with an exactly long representation + ASSERT_EQ((int64_t)0x1.FFFFFFFFFFFFFp62, 0x7FFFFFFFFFFFFC00LL); + ASSERT_MIXED_SAME(0x1.FFFFFFFFFFFFFp62, 0x7FFFFFFFFFFFFC00LL); + + ASSERT_MIXED_DESCENDING(0x1.FFFFFFFFFFFFFp62, 0x7FFFFFFFFFFFFB00LL); + ASSERT_MIXED_DESCENDING(0x1.FFFFFFFFFFFFFp62, 0x7FFFFFFFFFFFFBFFLL); + ASSERT_MIXED_ASCENDING(0x1.FFFFFFFFFFFFFp62, 0x7FFFFFFFFFFFFC01LL); + ASSERT_MIXED_ASCENDING(0x1.FFFFFFFFFFFFFp62, 0x7FFFFFFFFFFFFD00LL); + + ASSERT_MIXED_ASCENDING(0x1.FFFFFFFFFFFFEp62, 0x7FFFFFFFFFFFFC00LL); + + // Tests around MAX_SAFE_INTEGER + ASSERT_MIXED_SAME(0x1.FFFFFFFFFFFFFp52, 0x1FFFFFFFFFFFFFLL); + ASSERT_MIXED_DESCENDING(0x1.FFFFFFFFFFFFFp52, 0x1FFFFFFFFFFFFELL); + ASSERT_MIXED_ASCENDING(0x1.FFFFFFFFFFFFEp52, 0x1FFFFFFFFFFFFFLL); + ASSERT_MIXED_ASCENDING(0x1.FFFFFFFFFFFFFp52, 0x20000000000000LL); + + // Tests around MIN_SAFE_INTEGER + ASSERT_MIXED_SAME(-0x1.FFFFFFFFFFFFFp52, -0x1FFFFFFFFFFFFFLL); + ASSERT_MIXED_ASCENDING(-0x1.FFFFFFFFFFFFFp52, -0x1FFFFFFFFFFFFELL); + ASSERT_MIXED_DESCENDING(-0x1.FFFFFFFFFFFFEp52, -0x1FFFFFFFFFFFFFLL); + ASSERT_MIXED_DESCENDING(-0x1.FFFFFFFFFFFFFp52, -0x20000000000000LL); + + // Tests around zero. + ASSERT_MIXED_SAME(-0.0, 0LL); + ASSERT_MIXED_SAME(0.0, 0LL); + + // The smallest representable positive value should be greater than zero + ASSERT_MIXED_DESCENDING(DBL_MIN, 0LL); + ASSERT_MIXED_ASCENDING(-DBL_MIN, 0LL); + + // Note that 0x1.0p-1074 is a hex floating point literal representing the + // minimum subnormal number: . + double minSubNormal = 0x1.0p-1074; + ASSERT_MIXED_DESCENDING(minSubNormal, 0LL); + ASSERT_MIXED_ASCENDING(-minSubNormal, 0LL); + + // Other sanity checks + ASSERT_MIXED_ASCENDING(0.5, 1LL); + ASSERT_MIXED_DESCENDING(0.5, 0LL); + ASSERT_MIXED_ASCENDING(1.5, 2LL); + ASSERT_MIXED_DESCENDING(1.5, 1LL); +} + +} // namespace util +} // namespace firestore +} // namespace firebase -- cgit v1.2.3