1#!/usr/bin/env python
2# -*- coding: utf-8 -*-
3
4#
5# Copyright 2017, Data61
6# Commonwealth Scientific and Industrial Research Organisation (CSIRO)
7# ABN 41 687 119 230.
8#
9# This software may be distributed and modified according to the terms of
10# the BSD 2-Clause license. Note that NO WARRANTY is provided.
11# See "LICENSE_BSD2.txt" for details.
12#
13# @TAG(DATA61_BSD)
14#
15
16'''
17Hash functions safe for use with persistent caches used by camkes.
18
19This is based on how Python's native hash function
20works (at time of writing). We need to deviate from the native
21functionality in order to be able to hash lists and deterministically
22hash strings.
23'''
24
25from camkes.internal.strhash import strhash
26import six, types, collections
27
28INITIAL_HASH_VALUE = 0x345678
29
30def hash_extend(current, extra):
31    return (current ^ extra) * 1000003
32
33def camkes_hash(value):
34    '''
35    Hash a value in a manner compatible with camkes' persistant compilation cache:
36    - strings are hashed deterministically
37    - lists/tuples/dicts are hashed based on their contents
38    '''
39
40    # As some types of expected values are intersecting, types are checked in
41    # a specific order.
42
43    if value is None:
44        # This can return anything, as long as it's consistent across invocations.
45        return hash("None")
46    if isinstance(value, six.string_types):
47        # Strings are iterable, but are hashed differently
48        # from other iterables.
49        return strhash(value)
50    elif isinstance(value, (tuple, types.GeneratorType)):
51        # Tuples and generators are hashable, so check
52        # for them before checking for Hashable as they
53        # must be hashed differently.
54        return hash_iterable(value)
55    elif isinstance(value, collections.Hashable):
56        # Some camkes ast objects have a Mapping interface,
57        # but are also hashable, and should be hashed normally.
58        # This case also catches general hashable types (e.g. int).
59        return hash(value)
60    elif isinstance(value, collections.Mapping):
61        # Dicts and other Mappings that aren't hashable
62        return hash_mapping(value)
63    elif isinstance(value, collections.Iterable):
64        # Lists and other iterables that aren't hashable
65        return hash_iterable(value)
66    else:
67        raise ValueError("Unexpected value: %s" % value)
68
69def hash_iterable(i):
70    h = INITIAL_HASH_VALUE
71    for v in i:
72        h = hash_extend(h, camkes_hash(v))
73    return h
74
75def hash_mapping(m):
76    h = INITIAL_HASH_VALUE
77
78    keys = list(m.keys())
79    keys.sort()
80
81    for k in keys:
82        h = hash_extend(h, strhash(k))
83        h = hash_extend(h, camkes_hash(m[k]))
84    return h
85