chiark / gitweb /
peerdb/tripe-newpeers.in, peerdb/peers.in.5.in: Multiple inheritance.
authorMark Wooding <mdw@distorted.org.uk>
Mon, 22 Dec 2014 20:32:58 +0000 (20:32 +0000)
committerMark Wooding <mdw@distorted.org.uk>
Fri, 8 May 2015 18:26:46 +0000 (19:26 +0100)
Allow a section to `@inherit' from more than one other section.  All
traversals of the inheritance dag which find a value must report the
same one.  Cycles are diagnosed when they're encountered, but not
otherwise.

peerdb/peers.in.5.in
peerdb/tripe-newpeers.in

index c92dabb..c718fb1 100644 (file)
@@ -98,14 +98,32 @@ There is a simple concept of
 for sections.  If a section contains an assignment
 .IP
 .BI "@inherit = " parent
+.RB [[,]
+.I parent
+\&...]
 .PP
 then any lookups which can't be satisfied in that section will be
-satisfied instead from the
+satisfied instead from its
 .I parent
-section (and, if necessary, its parent in turn, and so on).  Note that
+sections (and, if necessary, their parents in turn, and so on).
+.PP
+.hP \*o
+If a value can be found for a key via multiple parents then all of them
+must report the
+.I same
+value.  This restriction may be relaxed somewhat, if it turns out that a
+more flexible notion of multiple inheritance is useful.
+.hP \*o
+It's not allowed for a section to inherit, possibly indirectly, from
+itself.  Currently errors of this kind are only diagnosed when a cycle
+is encountered while looking up a key and none of the sections on the
+path from the original section up to and round the cycle define a value
+for it.  Future versions of this program might be more picky.
+.PP
+Note that
 .BI $( key )
 substitutions in the resulting value will be satisfied from the original
-section (though falling back to scanning the parent section).  For
+section (though falling back to scanning parent sections).  For
 example, given the sections
 .VS
 [parent]
index d22aff7..a40d438 100644 (file)
@@ -110,6 +110,34 @@ r_ref = RX.compile(r'\$\(([^)]+)\)')
 ## Match a $[HOST] name resolution reference; group 1 is the HOST.
 r_resolve = RX.compile(r'\$\[([^]]+)\]')
 
+def _fmt_path(path):
+  return ' -> '.join(["`%s'" % hop for hop in path])
+
+class AmbiguousOptionError (Exception):
+  def __init__(me, key, patha, vala, pathb, valb):
+    me.key = key
+    me.patha, me.vala = patha, vala
+    me.pathb, me.valb = pathb, valb
+  def __str__(me):
+    return "Ambiguous answer resolving key `%s': " \
+        "path %s yields `%s' but %s yields `%s'" % \
+        (me.key, _fmt_path(me.patha), me.vala, _fmt_path(me.pathb), me.valb)
+
+class InheritanceCycleError (Exception):
+  def __init__(me, key, path):
+    me.key = key
+    me.path = path
+  def __str__(me):
+    return "Found a cycle %s looking up key `%s'" % \
+        (_fmt_path(me.path), me.key)
+
+class MissingKeyException (Exception):
+  def __init__(me, sec, key):
+    me.sec = sec
+    me.key = key
+  def __str__(me):
+    return "Key `%s' not found in section `%s'" % (me.key, me.sec)
+
 class MyConfigParser (CP.RawConfigParser):
   """
   A more advanced configuration parser.
@@ -180,44 +208,94 @@ class MyConfigParser (CP.RawConfigParser):
 
     This version of the method properly handles the @inherit key.
     """
-    return CP.RawConfigParser.has_option(me, sec, key) or \
-           (CP.RawConfigParser.has_option(me, sec, '@inherit') and
-            me.has_option(CP.RawConfigParser.get(me, sec, '@inherit'), key))
+    return key == 'name' or me._get(sec, key)[0] is not None
 
-  def _get(me, basesec, sec, key, resolvep):
+  def _get(me, sec, key, map = None, path = None):
     """
     Low-level option-fetching method.
 
     Fetch the value for the named KEY from section SEC, or maybe
-    (recursively) the section which SEC inherits from.
+    (recursively) a section which SEC inherits from.
 
-    The result is expanded, by _expend; RESOLVEP is passed to _expand to
-    control whether $[...] should be expanded in the result.
+    Returns a pair VALUE, PATH.  The value is not expanded; nor do we check
+    for the special `name' key.  The caller is expected to do these things.
+    Returns None if no value could be found.
+    """
 
-    The BASESEC is the section for which the original request was made.  This
-    will be different from SEC if we're recursing up the inheritance chain.
+    ## If we weren't given a memoization map or path, then we'd better make
+    ## one.
+    if map is None: map = {}
+    if path is None: path = []
 
-    We also provide the default value for `name' here.
-    """
+    ## 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.
+    path.append(sec)
+    try:
+      threadp, value = map[sec]
+    except KeyError:
+      pass
+    else:
+      if threadp:
+        raise InheritanceCycleError, (key, path)
+
+    ## See whether the answer is ready waiting for us.
     try:
-      raw = CP.RawConfigParser.get(me, sec, key)
+      v = CP.RawConfigParser.get(me, sec, key)
     except CP.NoOptionError:
-      if key == 'name':
-        raw = basesec
-      elif CP.RawConfigParser.has_option(me, sec, '@inherit'):
-        raw = me._get(basesec,
-                      CP.RawConfigParser.get(me, sec, '@inherit'),
-                      key,
-                      resolvep)
-      else:
-        raise
-    return me._expand(basesec, raw, resolvep)
+      pass
+    else:
+      p = path[:]
+      path.pop()
+      return v, p
+
+    ## No, apparently, not.  Find out our list of parents.
+    try:
+      parents = CP.RawConfigParser.get(me, sec, '@inherit').\
+          replace(',', ' ').split()
+    except CP.NoOptionError:
+      parents = []
+
+    ## Initially we have no idea.
+    value = None
+    winner = None
+
+    ## Go through our parents and ask them what they think.
+    map[sec] = True, None
+    for p in parents:
+
+      ## See whether we get an answer.  If not, keep on going.
+      v, pp = me._get(p, key, map, path)
+      if v is None: continue
+
+      ## If we got an answer, check that it matches any previous ones.
+      if value is None:
+        value = v
+        winner = pp
+      elif value != v:
+        raise AmbiguousOptionError, (key, winner, value, pp, v)
+
+    ## That's the best we could manage.
+    path.pop()
+    map[sec] = False, value
+    return value, winner
 
   def get(me, sec, key, resolvep = True):
     """
     Retrieve the value of KEY from section SEC.
     """
-    return me._get(sec, sec, key, resolvep)
+
+    ## Special handling for the `name' key.
+    if key == 'name':
+      try: value = CP.RawConfigParser.get(me, sec, key)
+      except CP.NoOptionError: value = sec
+    else:
+      value, _ = me._get(sec, key)
+      if value is None:
+        raise MissingKeyException, (sec, key)
+
+    ## Expand the value and return it.
+    return me._expand(sec, value, resolvep)
 
   def items(me, sec, resolvep = True):
     """
@@ -225,17 +303,30 @@ class MyConfigParser (CP.RawConfigParser):
 
     This extends the default method by handling the inheritance chain.
     """
+
+    ## Initialize for a depth-first walk of the inheritance graph.
     d = {}
+    visited = {}
     basesec = sec
-    while sec:
-      next = None
+    stack = [sec]
+
+    ## Visit nodes, collecting their keys.  Don't believe the values:
+    ## resolving inheritance is too hard to do like this.
+    while stack:
+      sec = stack.pop()
+      if sec in visited: continue
+      visited[sec] = True
+
       for key, value in CP.RawConfigParser.items(me, sec):
-        if key == '@inherit':
-          next = value
-        elif not key.startswith('@') and key not in d:
-          d[key] = me._expand(basesec, value, resolvep)
-      sec = next
-    return d.items()
+        if key == '@inherit': stack += value.replace(',', ' ').split()
+        else: d[key] = None
+
+    ## Now collect the values for the known keys, one by one.
+    items = []
+    for key in d: items.append((key, me.get(basesec, key, resolvep)))
+
+    ## And we're done.
+    return items
 
 ###--------------------------------------------------------------------------
 ### Command-line handling.