forked from immutable-js/immutable-js
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Hash.js
234 lines (203 loc) · 5.9 KB
/
Hash.js
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
import { smi } from './Math';
const defaultValueOf = Object.prototype.valueOf;
export function hash(o) {
if (o == null) {
return hashNullish(o);
}
if (typeof o.hashCode === 'function') {
// Drop any high bits from accidentally long hash codes.
return smi(o.hashCode(o));
}
const v = valueOf(o);
if (v == null) {
return hashNullish(v);
}
switch (typeof v) {
case 'boolean':
// The hash values for built-in constants are a 1 value for each 5-byte
// shift region expect for the first, which encodes the value. This
// reduces the odds of a hash collision for these common values.
return v ? 0x42108421 : 0x42108420;
case 'number':
return hashNumber(v);
case 'string':
return v.length > STRING_HASH_CACHE_MIN_STRLEN
? cachedHashString(v)
: hashString(v);
case 'object':
case 'function':
return hashJSObj(v);
case 'symbol':
return hashSymbol(v);
default:
if (typeof v.toString === 'function') {
return hashString(v.toString());
}
throw new Error('Value type ' + typeof v + ' cannot be hashed.');
}
}
function hashNullish(nullish) {
return nullish === null ? 0x42108422 : /* undefined */ 0x42108423;
}
// Compress arbitrarily large numbers into smi hashes.
function hashNumber(n) {
if (n !== n || n === Infinity) {
return 0;
}
let hash = n | 0;
if (hash !== n) {
hash ^= n * 0xffffffff;
}
while (n > 0xffffffff) {
n /= 0xffffffff;
hash ^= n;
}
return smi(hash);
}
function cachedHashString(string) {
let hashed = stringHashCache[string];
if (hashed === undefined) {
hashed = hashString(string);
if (STRING_HASH_CACHE_SIZE === STRING_HASH_CACHE_MAX_SIZE) {
STRING_HASH_CACHE_SIZE = 0;
stringHashCache = {};
}
STRING_HASH_CACHE_SIZE++;
stringHashCache[string] = hashed;
}
return hashed;
}
// https://jsperf.com/hashing-strings
function hashString(string) {
// This is the hash from JVM
// The hash code for a string is computed as
// s[0] * 31 ^ (n - 1) + s[1] * 31 ^ (n - 2) + ... + s[n - 1],
// where s[i] is the ith character of the string and n is the length of
// the string. We "mod" the result to make it between 0 (inclusive) and 2^31
// (exclusive) by dropping high bits.
let hashed = 0;
for (let ii = 0; ii < string.length; ii++) {
hashed = (31 * hashed + string.charCodeAt(ii)) | 0;
}
return smi(hashed);
}
function hashSymbol(sym) {
let hashed = symbolMap[sym];
if (hashed !== undefined) {
return hashed;
}
hashed = nextHash();
symbolMap[sym] = hashed;
return hashed;
}
function hashJSObj(obj) {
let hashed;
if (usingWeakMap) {
hashed = weakMap.get(obj);
if (hashed !== undefined) {
return hashed;
}
}
hashed = obj[UID_HASH_KEY];
if (hashed !== undefined) {
return hashed;
}
if (!canDefineProperty) {
hashed = obj.propertyIsEnumerable && obj.propertyIsEnumerable[UID_HASH_KEY];
if (hashed !== undefined) {
return hashed;
}
hashed = getIENodeHash(obj);
if (hashed !== undefined) {
return hashed;
}
}
hashed = nextHash();
if (usingWeakMap) {
weakMap.set(obj, hashed);
} else if (isExtensible !== undefined && isExtensible(obj) === false) {
throw new Error('Non-extensible objects are not allowed as keys.');
} else if (canDefineProperty) {
Object.defineProperty(obj, UID_HASH_KEY, {
enumerable: false,
configurable: false,
writable: false,
value: hashed,
});
} else if (
obj.propertyIsEnumerable !== undefined &&
obj.propertyIsEnumerable === obj.constructor.prototype.propertyIsEnumerable
) {
// Since we can't define a non-enumerable property on the object
// we'll hijack one of the less-used non-enumerable properties to
// save our hash on it. Since this is a function it will not show up in
// `JSON.stringify` which is what we want.
obj.propertyIsEnumerable = function () {
return this.constructor.prototype.propertyIsEnumerable.apply(
this,
arguments
);
};
obj.propertyIsEnumerable[UID_HASH_KEY] = hashed;
} else if (obj.nodeType !== undefined) {
// At this point we couldn't get the IE `uniqueID` to use as a hash
// and we couldn't use a non-enumerable property to exploit the
// dontEnum bug so we simply add the `UID_HASH_KEY` on the node
// itself.
obj[UID_HASH_KEY] = hashed;
} else {
throw new Error('Unable to set a non-enumerable property on object.');
}
return hashed;
}
// Get references to ES5 object methods.
const isExtensible = Object.isExtensible;
// True if Object.defineProperty works as expected. IE8 fails this test.
const canDefineProperty = (function () {
try {
Object.defineProperty({}, '@', {});
return true;
} catch (e) {
return false;
}
})();
// IE has a `uniqueID` property on DOM nodes. We can construct the hash from it
// and avoid memory leaks from the IE cloneNode bug.
function getIENodeHash(node) {
if (node && node.nodeType > 0) {
switch (node.nodeType) {
case 1: // Element
return node.uniqueID;
case 9: // Document
return node.documentElement && node.documentElement.uniqueID;
}
}
}
function valueOf(obj) {
return obj.valueOf !== defaultValueOf && typeof obj.valueOf === 'function'
? obj.valueOf(obj)
: obj;
}
function nextHash() {
const nextHash = ++_objHashUID;
if (_objHashUID & 0x40000000) {
_objHashUID = 0;
}
return nextHash;
}
// If possible, use a WeakMap.
const usingWeakMap = typeof WeakMap === 'function';
let weakMap;
if (usingWeakMap) {
weakMap = new WeakMap();
}
const symbolMap = Object.create(null);
let _objHashUID = 0;
let UID_HASH_KEY = '__immutablehash__';
if (typeof Symbol === 'function') {
UID_HASH_KEY = Symbol(UID_HASH_KEY);
}
const STRING_HASH_CACHE_MIN_STRLEN = 16;
const STRING_HASH_CACHE_MAX_SIZE = 255;
let STRING_HASH_CACHE_SIZE = 0;
let stringHashCache = {};