From: Mark Wooding <mdw@distorted.org.uk>
Date: Sun, 27 May 2018 01:28:20 +0000 (+0100)
Subject: peerdb/tripe-newpeers.in: Fix memoization while resolving inheritance.
X-Git-Tag: 1.5.0~71
X-Git-Url: https://git.distorted.org.uk/~mdw/tripe/commitdiff_plain/886350e8acb1116bf39bec5e5c411cc1db377d31

peerdb/tripe-newpeers.in: Fix memoization while resolving inheritance.

The memoization never worked properly.  It's clear, because the code
tries to store old values in the `map' dictionary, that it /wants/ to
optimize repeated visits to the same parent section, but unfortunately
nothing actually picks these saved values up again.  I can't tell any
more, but I think this is because the memoization map never stored the
path, so a second visit would return an unhelpful truncated path.

Also, the per-lookup memoization isn't really very effective: we
pointlessly walk the inheritance graph afresh for each `get' call.

Replace this with a per-section cache of inheritance-resolved lookups,
complete with path information.
---

diff --git a/peerdb/tripe-newpeers.in b/peerdb/tripe-newpeers.in
index 8b4d800c..4b9fe1f8 100644
--- a/peerdb/tripe-newpeers.in
+++ b/peerdb/tripe-newpeers.in
@@ -180,8 +180,25 @@ class ConfigSection (object):
 
   def __init__(me, name, cp):
     """Initialize a new, empty section with a given NAME and parent CP."""
+
+    ## The cache maps item keys to entries, which consist of a pair of
+    ## objects.  There are four possible states for a cache entry:
+    ##
+    ##   * missing -- there is no entry at all with this key, so we must
+    ##     search for it;
+    ##
+    ##   * None, None -- we are actively trying to resolve this key, so if we
+    ##     encounter this state, we have found a cycle in the inheritance
+    ##     graph;
+    ##
+    ##   * None, [] -- we know that this key isn't reachable through any of
+    ##     our parents;
+    ##
+    ##   * VALUE, PATH -- we know that the key resolves to VALUE, along the
+    ##     PATH from us (exclusive) to the defining parent (inclusive).
     me.name = name
     me._itemmap = dict()
+    me._cache = dict()
     me._cp = cp
 
   def _expand(me, string, resolvep):
@@ -206,7 +223,7 @@ class ConfigSection (object):
     for name in names.replace(',', ' ').split():
       yield me._cp.section(name)
 
-  def _get(me, key, map = None, path = None):
+  def _get(me, key, path = None):
     """
     Low-level option-fetching method.
 
@@ -218,9 +235,7 @@ class ConfigSection (object):
     Returns None if no value could be found.
     """
 
-    ## If we weren't given a memoization map or path, then we'd better make
-    ## one.
-    if map is None: map = {}
+    ## If we weren't given a path, then we'd better make one.
     if path is None: path = []
 
     ## Extend the path to cover us, but remember to remove us again when
@@ -229,29 +244,33 @@ class ConfigSection (object):
     path.append(me.name)
     try:
 
-      ## If we've been this way before on another pass through then return
-      ## the value we found then.  If we're still thinking about it then
-      ## we've found a cycle.
-      try: threadp, value = map[me.name]
+      ## If we've been this way before on another pass through then return the
+      ## value we found then.  If we're still thinking about it then we've
+      ## found a cycle.
+      try: v, p = me._cache[key]
       except KeyError: pass
       else:
-        if threadp: raise InheritanceCycleError(key, path[:])
+        if p is None: raise InheritanceCycleError(key, path[:])
+        else: return v, path + p
 
       ## See whether the answer is ready waiting for us.
       try: v = me._itemmap[key]
       except KeyError: pass
-      else: return v, path[:]
+      else:
+        p = path[:]
+        me._cache[key] = v, []
+        return v, p
 
       ## Initially we have no idea.
       value = None
-      winner = None
+      winner = []
 
       ## Go through our parents and ask them what they think.
-      map[me.name] = True, None
+      me._cache[key] = None, None
       for p in me._parents():
 
         ## See whether we get an answer.  If not, keep on going.
-        v, pp = p._get(key, map, path)
+        v, pp = p._get(key, path)
         if v is None: continue
 
         ## If we got an answer, check that it matches any previous ones.
@@ -262,7 +281,7 @@ class ConfigSection (object):
           raise AmbiguousOptionError(key, winner, value, pp, v)
 
       ## That's the best we could manage.
-      map[me.name] = False, value
+      me._cache[key] = value, winner[len(path):]
       return value, winner
 
     finally: