Implement Parameter interpolation

Parameters can now reference each other, and resolution happens in
topological order. This is done in two steps: while merging already
walks the entire dictionary, a list of references and their occurrences
is kept. After merging is complete, interpolate() is called on the
instance, which recursively resolves the references found during
merging. If a referenced value itself contains other references, those
are resolved first (which is the topological ordering).

Signed-off-by: martin f. krafft <madduck@madduck.net>
diff --git a/reclass/datatypes/parameters.py b/reclass/datatypes/parameters.py
index 363e508..d897366 100644
--- a/reclass/datatypes/parameters.py
+++ b/reclass/datatypes/parameters.py
@@ -6,21 +6,34 @@
 # Copyright © 2007–13 martin f. krafft <madduck@madduck.net>
 # Released under the terms of the Artistic Licence 2.0
 #
+import types
+
 from reclass.defaults import PARAMETER_INTERPOLATION_DELIMITER
+from reclass.utils.dictpath import DictPath
+from reclass.utils.refvalue import RefValue
+from reclass.errors import InfiniteRecursionError, UndefinedVariableError
 
 class Parameters(object):
     '''
-    A class to hold nested dictionaries with the following speciality:
+    A class to hold nested dictionaries with the following specialities:
 
-    "merging" a dictionary (the "new" dictionary) into the current Parameters
-    causes a recursive walk of the new dict, during which
+      1. "merging" a dictionary (the "new" dictionary) into the current
+         Parameters causes a recursive walk of the new dict, during which
 
-       - scalars (incl. tuples) are replaced with the value from the new
-         dictionary;
-       - lists are extended, not replaced;
-       - dictionaries are updated (using dict.update), not replaced;
+         - scalars (incl. tuples) are replaced with the value from the new
+           dictionary;
+         - lists are extended, not replaced;
+         - dictionaries are updated (using dict.update), not replaced;
 
-    To support this speciality, this class only exposes very limited
+      2. "interpolating" a dictionary means that values within the dictionary
+         can reference other values in the same dictionary. Those references
+         are collected during merging and then resolved during interpolation,
+         which avoids having to walk the dictionary twice. If a referenced
+         value contains references itself, those are resolved first, in
+         topological order. Therefore, deep references work. Cyclical
+         references cause an error.
+
+    To support these specialities, this class only exposes very limited
     functionality and does not try to be a really mapping object.
     '''
     DEFAULT_PATH_DELIMITER = PARAMETER_INTERPOLATION_DELIMITER
@@ -30,6 +43,7 @@
             delimiter = Parameters.DEFAULT_PATH_DELIMITER
         self._delimiter = delimiter
         self._base = {}
+        self._refs = {}
         if mapping is not None:
             # we initialise by merging, otherwise the list of references might
             # not be updated
@@ -54,23 +68,33 @@
     def as_dict(self):
         return self._base.copy()
 
-    def _update_scalar(self, cur, new, delim, parent):
-        if delim is None:
+    def _register_ref_occurrence(self, path, ref):
+        self._refs[path] = ref
+
+    def _update_scalar(self, cur, new, path):
+        if self.delimiter is None or not isinstance(new, types.StringTypes):
             return new
 
         else:
-            return new #TODO
+            ret = RefValue(new, self.delimiter)
+            if not ret.has_references():
+                # do not replace with RefValue instance if there are no
+                # references
+                return new
 
-    def _extend_list(self, cur, new, delim, parent):
+            self._register_ref_occurrence(path, ret)
+            return ret
+
+    def _extend_list(self, cur, new, path):
         if isinstance(cur, list):
             ret = cur
         else:
             ret = [cur]
-        for i in new:
-            ret.append(self._merge_recurse(None, i, delim, parent))
+        for i in xrange(len(new)):
+            ret.append(self._merge_recurse(None, new[i], path.new_subpath(i)))
         return ret
 
-    def _merge_dict(self, cur, new, delim, parent):
+    def _merge_dict(self, cur, new, path):
         if isinstance(cur, dict):
             ret = cur
         else:
@@ -78,7 +102,7 @@
             raise TypeError('Cannot merge dict into {0} '
                             'objects'.format(type(cur)))
 
-        if delim is None:
+        if self.delimiter is None:
             # a delimiter of None indicates that there is no value
             # processing to be done, and since there is no current
             # value, we do not need to walk the new dictionary:
@@ -86,23 +110,26 @@
             return ret
 
         for key, newvalue in new.iteritems():
-            ret[key] = self._merge_recurse(ret.get(key), newvalue, delim,
-                                           (ret, key))
+            ret[key] = self._merge_recurse(ret.get(key), newvalue,
+                                           path.new_subpath(key))
         return ret
 
-    def _merge_recurse(self, cur, new, delim, parent=None):
+    def _merge_recurse(self, cur, new, path=None):
+        if path is None:
+            path = DictPath(self.delimiter)
+
         if isinstance(new, dict):
             if cur is None:
                 cur = {}
-            return self._merge_dict(cur, new, delim, parent)
+            return self._merge_dict(cur, new, path)
 
         elif isinstance(new, list):
             if cur is None:
                 cur = []
-            return self._extend_list(cur, new, delim, parent)
+            return self._extend_list(cur, new, path)
 
         else:
-            return self._update_scalar(cur, new, delim, parent)
+            return self._update_scalar(cur, new, path)
 
     def merge(self, other):
         if isinstance(other, dict):
@@ -110,8 +137,34 @@
 
         elif isinstance(other, self.__class__):
             self._base = self._merge_recurse(self._base, other._base,
-                                             other.delimiter)
+                                             None)
+            self._refs.update(other._refs)
 
         else:
             raise TypeError('Cannot merge %s objects into %s' % (type(other),
                             self.__class__.__name__))
+
+    def interpolate(self):
+        while len(self._refs) > 0:
+            path, refvalue = self._refs.iteritems().next()
+            self._refs[path] = None
+            self._interpolate_inner(path, refvalue)
+
+    def _interpolate_inner(self, path, refvalue):
+        for ref in refvalue.get_references():
+            path_from_ref = DictPath(self.delimiter, ref)
+            try:
+                refvalue_inner = self._refs[path_from_ref]
+                if refvalue_inner is None:
+                    raise InfiniteRecursionError(path, ref)
+                self._interpolate_inner(path_from_ref,
+                                        self._refs[path_from_ref])
+            except KeyError as e:
+                pass
+        try:
+            new = refvalue.render(self._base)
+            path.set_value(self._base, new)
+            del self._refs[path]
+        except UndefinedVariableError as e:
+            raise UndefinedVariableError(e.var, path)
+
diff --git a/reclass/datatypes/tests/test_parameters.py b/reclass/datatypes/tests/test_parameters.py
index dde5573..5732018 100644
--- a/reclass/datatypes/tests/test_parameters.py
+++ b/reclass/datatypes/tests/test_parameters.py
@@ -7,6 +7,8 @@
 # Released under the terms of the Artistic Licence 2.0
 #
 from reclass.datatypes import Parameters
+from reclass.defaults import PARAMETER_INTERPOLATION_SENTINELS
+from reclass.errors import InfiniteRecursionError
 import unittest
 try:
     import unittest.mock as mock
@@ -186,7 +188,47 @@
         p.merge(Parameters(mergee))
         self.assertDictEqual(p.as_dict(), mergee)
 
-    test_cur = test_merge_scalar_over_dict
+    def test_interpolate_single(self):
+        v = 42
+        d = {'foo': 'bar'.join(PARAMETER_INTERPOLATION_SENTINELS),
+             'bar': v}
+        p = Parameters(d)
+        p.interpolate()
+        self.assertEqual(p.as_dict()['foo'], v)
+
+    def test_interpolate_multiple(self):
+        v = '42'
+        d = {'foo': 'bar'.join(PARAMETER_INTERPOLATION_SENTINELS) + 'meep'.join(PARAMETER_INTERPOLATION_SENTINELS),
+             'bar': v[0],
+             'meep': v[1]}
+        p = Parameters(d)
+        p.interpolate()
+        self.assertEqual(p.as_dict()['foo'], v)
+
+    def test_interpolate_multilevel(self):
+        v = 42
+        d = {'foo': 'bar'.join(PARAMETER_INTERPOLATION_SENTINELS),
+             'bar': 'meep'.join(PARAMETER_INTERPOLATION_SENTINELS),
+             'meep': v}
+        p = Parameters(d)
+        p.interpolate()
+        self.assertEqual(p.as_dict()['foo'], v)
+
+    def test_interpolate_list(self):
+        l = [41,42,43]
+        d = {'foo': 'bar'.join(PARAMETER_INTERPOLATION_SENTINELS),
+             'bar': l}
+        p = Parameters(d)
+        p.interpolate()
+        self.assertEqual(p.as_dict()['foo'], l)
+
+    def test_interpolate_infrecursion(self):
+        v = 42
+        d = {'foo': 'bar'.join(PARAMETER_INTERPOLATION_SENTINELS),
+             'bar': 'foo'.join(PARAMETER_INTERPOLATION_SENTINELS)}
+        p = Parameters(d)
+        with self.assertRaises(InfiniteRecursionError):
+            p.interpolate()
 
 if __name__ == '__main__':
     unittest.main()
diff --git a/reclass/errors.py b/reclass/errors.py
index 544cb15..5bec2c1 100644
--- a/reclass/errors.py
+++ b/reclass/errors.py
@@ -93,3 +93,11 @@
         msg = "Missing '%s' to end reference: %s" % \
                 (end_sentinel, string.join(PARAMETER_INTERPOLATION_SENTINELS))
         super(IncompleteInterpolationError, self).__init__(msg)
+
+
+class InfiniteRecursionError(InterpolationError):
+
+    def __init__(self, path, ref):
+        msg = "Infinite recursion while resolving %s at %s" \
+                % (ref.join(PARAMETER_INTERPOLATION_SENTINELS), path)
+        super(InfiniteRecursionError, self).__init__(msg)