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

[Laurent Charignon]

# 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()))))
+
 def finddirs(path):
     pos = path.rfind('/')
     while pos != -1: