Merge pull request #13056 from xwu/much-of-a-muchness
[stdlib/Sema/AST] Adopt a commonly used implementation for combining hashes
diff --git a/include/swift/AST/ASTContext.h b/include/swift/AST/ASTContext.h
index e611b58..57a60d6 100644
--- a/include/swift/AST/ASTContext.h
+++ b/include/swift/AST/ASTContext.h
@@ -482,8 +482,8 @@
FuncDecl *getEqualIntDecl() const;
/// Retrieve the declaration of
- /// Swift._mixForSynthesizedHashValue (Int, Int) -> Int.
- FuncDecl *getMixForSynthesizedHashValueDecl() const;
+ /// Swift._combineHashValues(Int, Int) -> Int.
+ FuncDecl *getCombineHashValuesDecl() const;
/// Retrieve the declaration of Swift._mixInt(Int) -> Int.
FuncDecl *getMixIntDecl() const;
diff --git a/lib/AST/ASTContext.cpp b/lib/AST/ASTContext.cpp
index c07980a..d53d188 100644
--- a/lib/AST/ASTContext.cpp
+++ b/lib/AST/ASTContext.cpp
@@ -194,8 +194,8 @@
/// func ==(Int, Int) -> Bool
FuncDecl *EqualIntDecl = nullptr;
- /// func _mixForSynthesizedHashValue(Int, Int) -> Int
- FuncDecl *MixForSynthesizedHashValueDecl = nullptr;
+ /// func _combineHashValues(Int, Int) -> Int
+ FuncDecl *CombineHashValuesDecl = nullptr;
/// func _mixInt(Int) -> Int
FuncDecl *MixIntDecl = nullptr;
@@ -1048,9 +1048,9 @@
return decl;
}
-FuncDecl *ASTContext::getMixForSynthesizedHashValueDecl() const {
- if (Impl.MixForSynthesizedHashValueDecl)
- return Impl.MixForSynthesizedHashValueDecl;
+FuncDecl *ASTContext::getCombineHashValuesDecl() const {
+ if (Impl.CombineHashValuesDecl)
+ return Impl.CombineHashValuesDecl;
auto resolver = getLazyResolver();
auto intType = getIntDecl()->getDeclaredType();
@@ -1066,8 +1066,8 @@
};
auto decl = lookupLibraryIntrinsicFunc(
- *this, "_mixForSynthesizedHashValue", resolver, callback);
- Impl.MixForSynthesizedHashValueDecl = decl;
+ *this, "_combineHashValues", resolver, callback);
+ Impl.CombineHashValuesDecl = decl;
return decl;
}
diff --git a/lib/Sema/DerivedConformanceEquatableHashable.cpp b/lib/Sema/DerivedConformanceEquatableHashable.cpp
index 7a6bbea..d5b6ab6 100644
--- a/lib/Sema/DerivedConformanceEquatableHashable.cpp
+++ b/lib/Sema/DerivedConformanceEquatableHashable.cpp
@@ -745,34 +745,34 @@
return integerExpr;
}
-/// Returns a new assignment expression that mixes the hash value of an
+/// Returns a new assignment expression that combines the hash value of an
/// expression into a variable.
/// \p C The AST context.
-/// \p resultVar The variable into which the hash value will be mixed.
-/// \p exprToHash The expression whose hash value should be mixed in.
-/// \return The expression that mixes the hash value into the result variable.
-static Expr* mixInHashExpr_hashValue(ASTContext &C,
- VarDecl* resultVar,
- Expr *exprToHash) {
+/// \p resultVar The variable into which the hash value will be combined.
+/// \p exprToHash The expression whose hash value should be combined.
+/// \return The expression that combines the hash value into the variable.
+static Expr* combineHashValuesAssignmentExpr(ASTContext &C,
+ VarDecl* resultVar,
+ Expr *exprToHash) {
// <exprToHash>.hashValue
auto hashValueExpr = new (C) UnresolvedDotExpr(exprToHash, SourceLoc(),
C.Id_hashValue, DeclNameLoc(),
/*implicit*/ true);
- // _mixForSynthesizedHashValue(result, <exprToHash>.hashValue)
- auto mixinFunc = C.getMixForSynthesizedHashValueDecl();
- auto mixinFuncExpr = new (C) DeclRefExpr(mixinFunc, DeclNameLoc(),
- /*implicit*/ true);
+ // _combineHashValues(result, <exprToHash>.hashValue)
+ auto combineFunc = C.getCombineHashValuesDecl();
+ auto combineFuncExpr = new (C) DeclRefExpr(combineFunc, DeclNameLoc(),
+ /*implicit*/ true);
auto rhsResultExpr = new (C) DeclRefExpr(resultVar, DeclNameLoc(),
/*implicit*/ true);
- auto mixinResultExpr = CallExpr::createImplicit(
- C, mixinFuncExpr, { rhsResultExpr, hashValueExpr }, {});
+ auto combineResultExpr = CallExpr::createImplicit(
+ C, combineFuncExpr, { rhsResultExpr, hashValueExpr }, {});
- // result = _mixForSynthesizedHashValue(result, <exprToHash>.hashValue)
+ // result = _combineHashValues(result, <exprToHash>.hashValue)
auto lhsResultExpr = new (C) DeclRefExpr(resultVar, DeclNameLoc(),
/*implicit*/ true);
auto assignExpr = new (C) AssignExpr(lhsResultExpr, SourceLoc(),
- mixinResultExpr, /*implicit*/ true);
+ combineResultExpr, /*implicit*/ true);
return assignExpr;
}
@@ -853,9 +853,9 @@
// If the enum has no associated values, we use the ordinal alone as the
// hash value, because that is sufficient for a good distribution. If any
- // case do have associated values, then the ordinal is used as the first
- // term mixed into _mixForSynthesizedHashValue, and the final result after
- // mixing in the payload is passed to _mixInt to improve the distribution.
+ // case does have associated values, then the ordinal is used as the first
+ // term combined into _combineHashValues, and the final result after
+ // combining the payload is passed to _mixInt to improve the distribution.
// result = <ordinal>
{
@@ -868,13 +868,14 @@
}
if (!hasNoAssociatedValues) {
- // Generate a sequence of expressions that mix the payload's hash values
- // into result.
+ // Generate a sequence of expressions that combine the payload's hash
+ // values into result.
for (auto payloadVar : payloadVars) {
auto payloadVarRef = new (C) DeclRefExpr(payloadVar, DeclNameLoc(),
/*implicit*/ true);
- // result = _mixForSynthesizedHashValue(result, <payloadVar>.hashValue)
- auto mixExpr = mixInHashExpr_hashValue(C, resultVar, payloadVarRef);
+ // result = _combineHashValues(result, <payloadVar>.hashValue)
+ auto mixExpr = combineHashValuesAssignmentExpr(C, resultVar,
+ payloadVarRef);
mixExpressions.emplace_back(ASTNode(mixExpr));
}
@@ -953,7 +954,7 @@
auto storedProperties =
structDecl->getStoredProperties(/*skipInaccessible=*/true);
- // For each stored property, generate a statement that mixes its hash value
+ // For each stored property, generate a statement that combines its hash value
// into the result.
for (auto propertyDecl : storedProperties) {
auto propertyRef = new (C) DeclRefExpr(propertyDecl, DeclNameLoc(),
@@ -962,8 +963,9 @@
/*implicit*/ true);
auto selfPropertyExpr = new (C) DotSyntaxCallExpr(propertyRef, SourceLoc(),
selfRef);
- // result = _mixForSynthesizedHashValue(result, <property>.hashValue)
- auto mixExpr = mixInHashExpr_hashValue(C, resultVar, selfPropertyExpr);
+ // result = _combineHashValues(result, <property>.hashValue)
+ auto mixExpr = combineHashValuesAssignmentExpr(C, resultVar,
+ selfPropertyExpr);
statements.emplace_back(ASTNode(mixExpr));
}
@@ -1014,11 +1016,11 @@
// result = 0
// case B(let a0):
// result = 1
- // result = _mixForSynthesizedHashValue(result, a0.hashValue)
+ // result = _combineHashValues(result, a0.hashValue)
// case C(let a0, let a1):
// result = 2
- // result = _mixForSynthesizedHashValue(result, a0.hashValue)
- // result = _mixForSynthesizedHashValue(result, a1.hashValue)
+ // result = _combineHashValues(result, a0.hashValue)
+ // result = _combineHashValues(result, a1.hashValue)
// }
// result = _mixInt(result)
// return result
@@ -1030,8 +1032,8 @@
// var y: String
// @derived var hashValue: Int {
// var result: Int = 0
- // result = _mixForSynthesizedHashValue(result, x.hashValue)
- // result = _mixForSynthesizedHashValue(result, y.hashValue)
+ // result = _combineHashValues(result, x.hashValue)
+ // result = _combineHashValues(result, y.hashValue)
// result = _mixInt(result)
// return result
// }
diff --git a/stdlib/public/core/Hashing.swift b/stdlib/public/core/Hashing.swift
index 5a4ca72..116ba67 100644
--- a/stdlib/public/core/Hashing.swift
+++ b/stdlib/public/core/Hashing.swift
@@ -188,13 +188,21 @@
/// Returns a new value that combines the two given hash values.
///
+/// Combining is performed using [a hash function][ref] described by T.C. Hoad
+/// and J. Zobel, which is also adopted in the Boost C++ libraries.
+///
/// This function is used by synthesized implementations of `hashValue` to
/// combine the hash values of individual `struct` fields and associated values
/// of `enum`s. It is factored out into a standard library function so that the
/// specific hashing logic can be refined without requiring major changes to the
/// code that creates the synthesized AST nodes.
+///
+/// [ref]: http://goanna.cs.rmit.edu.au/~jz/fulltext/jasist-tch.pdf
@_transparent
public // @testable
-func _mixForSynthesizedHashValue(_ oldValue: Int, _ nextValue: Int) -> Int {
- return 31 &* oldValue &+ nextValue
+func _combineHashValues(_ firstValue: Int, _ secondValue: Int) -> Int {
+ let magic = 0x9e3779b9 as UInt // Based on the golden ratio.
+ var x = UInt(bitPattern: firstValue)
+ x ^= UInt(bitPattern: secondValue) &+ magic &+ (x &<< 6) &+ (x &>> 2)
+ return Int(bitPattern: x)
}
