[PATCH 1 of 2] util: add method to hash nested combination of python data structures

[Matt Mackall]

On Wed, 2015-07-01 at 17:05 -0700, Laurent Charignon wrote:
> # HG changeset patch
> # User Laurent Charignon <lcharignon at fb.com>
> # Date 1435794507 25200
> #      Wed Jul 01 16:48:27 2015 -0700
> # Node ID 6a7e4701a5214f3a6143ced979896ff51b6ea331
> # Parent  2748bf78a5bf610da4f2d90fd1eea19a3b360c04
> util: add method to hash nested combination of python data structures
> 
> The goal of this series of patches is to have a method to compute the hash of
> config objects. This will enable restarting the command server when the config
> change.
> This patch adds a method to compute the hash of nested combination of basic
> data structure, it will be used to enable computing the hash of a sortdict and
> in turn compute the hash of a config.
> 
> Implementation modified from:
> http://stackoverflow.com/questions/5884066/hashing-a-python-dictionary
> 
> diff --git a/mercurial/util.py b/mercurial/util.py
> --- a/mercurial/util.py
> +++ b/mercurial/util.py
> @@ -21,6 +21,7 @@ import re as remod
>  import os, time, datetime, calendar, textwrap, signal, collections
>  import imp, socket, urllib
>  import gc
> +import copy
>  
>  if os.name == 'nt':
>      import windows as platform
> @@ -2333,6 +2334,25 @@ class dirs(object):
>  if safehasattr(parsers, 'dirs'):
>      dirs = parsers.dirs
>  
> +def makehash(o):
> +    """
> +    Makes a hash from a dictionary, list, tuple or set to any level, containing
> +    only other hashable types (including any lists, tuples, sets, and
> +    dictionaries).
> +    """
> +
> +    if isinstance(o, (set, tuple, list)):
> +        return hash(tuple([makehash(e) for e in o]))
> +
> +    elif not isinstance(o, dict):
> +        return hash(o)
> +
> +    new_o = copy.deepcopy(o)
> +    for k, v in new_o.items():
> +        new_o[k] = makehash(v)
> +
> +    return hash(tuple(frozenset(sorted(new_o.items()))))

Wants a doctest. Also, we can implement this without doing a deep copy
pretty easily:

    if isinstance(x, dict):
        return makehash(x.iteritems())
    if hasattr(x, '__iter__'):
        return sum(makehash(i) for i in x)
    return hash(x)

-- 
Mathematics is the supreme nostalgia of our time.