1
2 /**
3 * Copyright (C) 2018-present MongoDB, Inc.
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the Server Side Public License, version 1,
7 * as published by MongoDB, Inc.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * Server Side Public License for more details.
13 *
14 * You should have received a copy of the Server Side Public License
15 * along with this program. If not, see
16 * <http://www.mongodb.com/licensing/server-side-public-license>.
17 *
18 * As a special exception, the copyright holders give permission to link the
19 * code of portions of this program with the OpenSSL library under certain
20 * conditions as described in each individual source file and distribute
21 * linked combinations including the program with the OpenSSL library. You
22 * must comply with the Server Side Public License in all respects for
23 * all of the code used other than as permitted herein. If you modify file(s)
24 * with this exception, you may extend this exception to your version of the
25 * file(s), but you are not obligated to do so. If you do not wish to do so,
26 * delete this exception statement from your version. If you delete this
27 * exception statement from all source files in the program, then also delete
28 * it in the license file.
29 */
30
31 #include "mongo/platform/basic.h"
32
33 #include "mongo/bson/bson_comparator_interface_base.h"
34
35 #include <boost/functional/hash.hpp>
36
37 #include "mongo/base/simple_string_data_comparator.h"
38 #include "mongo/bson/bsonelement.h"
39 #include "mongo/bson/bsonobj.h"
40 #include "mongo/bson/simple_bsonobj_comparator.h"
41
42 namespace mongo {
43
44 template <typename T>
hashCombineBSONObj(size_t & seed,const BSONObj & objToHash,ComparisonRulesSet rules,const StringData::ComparatorInterface * stringComparator)45 void BSONComparatorInterfaceBase<T>::hashCombineBSONObj(
46 size_t& seed,
47 const BSONObj& objToHash,
48 ComparisonRulesSet rules,
49 const StringData::ComparatorInterface* stringComparator) {
50
51 if (rules & ComparisonRules::kIgnoreFieldOrder) {
52 BSONObjIteratorSorted iter(objToHash);
53 while (iter.more()) {
54 hashCombineBSONElement(seed, iter.next(), rules, stringComparator);
55 }
56 } else {
57 for (auto elem : objToHash) {
58 hashCombineBSONElement(seed, elem, rules, stringComparator);
59 }
60 }
61 }
62
63 template <typename T>
hashCombineBSONElement(size_t & hash,BSONElement elemToHash,ComparisonRulesSet rules,const StringData::ComparatorInterface * stringComparator)64 void BSONComparatorInterfaceBase<T>::hashCombineBSONElement(
65 size_t& hash,
66 BSONElement elemToHash,
67 ComparisonRulesSet rules,
68 const StringData::ComparatorInterface* stringComparator) {
69 boost::hash_combine(hash, elemToHash.canonicalType());
70
71 const StringData fieldName = elemToHash.fieldNameStringData();
72 if ((rules & ComparisonRules::kConsiderFieldName) && !fieldName.empty()) {
73 SimpleStringDataComparator::kInstance.hash_combine(hash, fieldName);
74 }
75
76 switch (elemToHash.type()) {
77 case mongo::EOO:
78 case mongo::Undefined:
79 case mongo::jstNULL:
80 case mongo::MaxKey:
81 case mongo::MinKey:
82 // These are valueless types
83 break;
84
85 case mongo::Bool:
86 boost::hash_combine(hash, elemToHash.boolean());
87 break;
88
89 case mongo::bsonTimestamp:
90 boost::hash_combine(hash, elemToHash.timestamp().asULL());
91 break;
92
93 case mongo::Date:
94 boost::hash_combine(hash, elemToHash.date().asInt64());
95 break;
96
97 case mongo::NumberDecimal: {
98 const Decimal128 dcml = elemToHash.numberDecimal();
99 if (dcml.toAbs().isGreater(Decimal128(std::numeric_limits<double>::max(),
100 Decimal128::kRoundTo34Digits,
101 Decimal128::kRoundTowardZero)) &&
102 !dcml.isInfinite() && !dcml.isNaN()) {
103 // Normalize our decimal to force equivalent decimals
104 // in the same cohort to hash to the same value
105 Decimal128 dcmlNorm(dcml.normalize());
106 boost::hash_combine(hash, dcmlNorm.getValue().low64);
107 boost::hash_combine(hash, dcmlNorm.getValue().high64);
108 break;
109 }
110 // Else, fall through and convert the decimal to a double and hash.
111 // At this point the decimal fits into the range of doubles, is infinity, or is NaN,
112 // which doubles have a cheaper representation for.
113 }
114 case mongo::NumberDouble:
115 case mongo::NumberLong:
116 case mongo::NumberInt: {
117 // This converts all numbers to doubles, which ignores the low-order bits of
118 // NumberLongs > 2**53 and precise decimal numbers without double representations,
119 // but that is ok since the hash will still be the same for equal numbers and is
120 // still likely to be different for different numbers. (Note: this issue only
121 // applies for decimals when they are outside of the valid double range. See
122 // the above case.)
123 // SERVER-16851
124 const double dbl = elemToHash.numberDouble();
125 if (std::isnan(dbl)) {
126 boost::hash_combine(hash, std::numeric_limits<double>::quiet_NaN());
127 } else {
128 boost::hash_combine(hash, dbl);
129 }
130 break;
131 }
132
133 case mongo::jstOID:
134 elemToHash.__oid().hash_combine(hash);
135 break;
136
137 case mongo::String: {
138 if (stringComparator) {
139 stringComparator->hash_combine(hash, elemToHash.valueStringData());
140 } else {
141 SimpleStringDataComparator::kInstance.hash_combine(hash,
142 elemToHash.valueStringData());
143 }
144 break;
145 }
146
147 case mongo::Code:
148 case mongo::Symbol:
149 SimpleStringDataComparator::kInstance.hash_combine(hash, elemToHash.valueStringData());
150 break;
151
152 case mongo::Object:
153 case mongo::Array:
154 hashCombineBSONObj(hash,
155 elemToHash.embeddedObject(),
156 rules | ComparisonRules::kConsiderFieldName,
157 stringComparator);
158 break;
159
160 case mongo::DBRef:
161 case mongo::BinData:
162 // All bytes of the value are required to be identical.
163 SimpleStringDataComparator::kInstance.hash_combine(
164 hash, StringData(elemToHash.value(), elemToHash.valuesize()));
165 break;
166
167 case mongo::RegEx:
168 SimpleStringDataComparator::kInstance.hash_combine(hash, elemToHash.regex());
169 SimpleStringDataComparator::kInstance.hash_combine(hash, elemToHash.regexFlags());
170 break;
171
172 case mongo::CodeWScope: {
173 SimpleStringDataComparator::kInstance.hash_combine(
174 hash, StringData(elemToHash.codeWScopeCode(), elemToHash.codeWScopeCodeLen()));
175 hashCombineBSONObj(hash,
176 elemToHash.codeWScopeObject(),
177 rules | ComparisonRules::kConsiderFieldName,
178 &SimpleStringDataComparator::kInstance);
179 break;
180 }
181 }
182 }
183
184 template class BSONComparatorInterfaceBase<BSONObj>;
185 template class BSONComparatorInterfaceBase<BSONElement>;
186
187 } // namespace mongo
188