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