re-enable support for resolving conflicts across orders

This feature was silently dropped in Pyramid 1.4 when deferred
discriminators were added.

It is re-introduced such that it's possible to override an action in
order X by defining an action in order Y where Y <= X with a
non-conflicting includepath.

This also takes special care to avoid undeferring the discriminator for
an action until the execution engine is ready to start executing
actions of the same order. This gives time for required actions to
execute prior, allowing the discriminator to depend on earlier actions.

fixes #2697

2 files changed, 133 insertions, 106 deletions

diff --git a/pyramid/config/__init__.py b/pyramid/config/__init__.py
index 553f32c9b..958526386 100644
--- a/pyramid/config/__init__.py
+++ b/pyramid/config/__init__.py
@@ -27,7 +27,6 @@ from pyramid.compat import (
     text_,
     reraise,
     string_types,
-    zip_longest,
     )
 
 from pyramid.events import ApplicationCreated
@@ -1110,29 +1109,8 @@ class ActionState(object):
         try:
             all_actions = []
             executed_actions = []
-            pending_actions = iter([])
-
-            # resolve the new action list against what we have already
-            # executed -- if a new action appears intertwined in the list
-            # of already-executed actions then someone wrote a broken
-            # re-entrant action because it scheduled the action *after* it
-            # should have been executed (as defined by the action order)
-            def resume(actions):
-                for a, b in zip_longest(actions, executed_actions):
-                    if b is None and a is not None:
-                        # common case is that we are executing every action
-                        yield a
-                    elif b is not None and a != b:
-                        raise ConfigurationError(
-                            'During execution a re-entrant action was added '
-                            'that modified the planned execution order in a '
-                            'way that is incompatible with what has already '
-                            'been executed.')
-                    else:
-                        # resolved action is in the same location as before,
-                        # so we are in good shape, but the action is already
-                        # executed so we skip it
-                        assert b is not None and a == b
+            action_iter = iter([])
+            conflict_state = ConflictResolverState()
 
             while True:
                 # We clear the actions list prior to execution so if there
@@ -1141,26 +1119,14 @@ class ActionState(object):
                 # ensures that the previously executed actions have no new
                 # conflicts.
                 if self.actions:
-                    # Only resolve the new actions against executed_actions
-                    # and pending_actions instead of everything to avoid
-                    # redundant checks.
-                    # Assume ``actions = resolveConflicts([A, B, C])`` which
-                    # after conflict checks, resulted in ``actions == [A]``
-                    # then we know action A won out or a conflict would have
-                    # been raised. Thus, when action D is added later, we only
-                    # need to check the new action against A.
-                    # ``actions = resolveConflicts([A, D]) should drop the
-                    # number of redundant checks down from O(n^2) closer to
-                    # O(n lg n).
                     all_actions.extend(self.actions)
-                    pending_actions = resume(resolveConflicts(
-                        executed_actions +
-                        list(pending_actions) +
-                        self.actions
-                    ))
+                    action_iter = resolveConflicts(
+                        self.actions,
+                        state=conflict_state,
+                    )
                     self.actions = []
 
-                action = next(pending_actions, None)
+                action = next(action_iter, None)
                 if action is None:
                     # we are done!
                     break
@@ -1176,9 +1142,7 @@ class ActionState(object):
                 try:
                     if callable is not None:
                         callable(*args, **kw)
-                except (KeyboardInterrupt, SystemExit): # pragma: no cover
-                    raise
-                except:
+                except Exception:
                     t, v, tb = sys.exc_info()
                     try:
                         reraise(ConfigurationExecutionError,
@@ -1193,65 +1157,102 @@ class ActionState(object):
 
                 executed_actions.append(action)
 
+            self.actions = all_actions
+            return executed_actions
+
         finally:
             if clear:
-                del self.actions[:]
-            else:
-                self.actions = all_actions
+                self.actions = []
+
+
+class ConflictResolverState(object):
+    def __init__(self):
+        # keep a set of resolved discriminators to test against to ensure
+        # that a new action does not conflict with something already executed
+        self.resolved_ainfos = {}
+
+        # actions left over from a previous iteration
+        self.remaining_actions = []
+
+        # after executing an action we memoize its order to avoid any new
+        # actions sending us backward
+        self.min_order = None
+
+        # unique tracks the index of the action so we need it to increase
+        # monotonically across invocations to resolveConflicts
+        self.start = 0
+
 
 # this function is licensed under the ZPL (stolen from Zope)
-def resolveConflicts(actions):
+def resolveConflicts(actions, state=None):
     """Resolve conflicting actions
 
     Given an actions list, identify and try to resolve conflicting actions.
     Actions conflict if they have the same non-None discriminator.
+
     Conflicting actions can be resolved if the include path of one of
     the actions is a prefix of the includepaths of the other
     conflicting actions and is unequal to the include paths in the
     other conflicting actions.
+
+    Actions are resolved on a per-order basis because some discriminators
+    cannot be computed until earlier actions have executed. An action in an
+    earlier order may execute successfully only to find out later that it was
+    overridden by another action with a smaller include path. This will result
+    in a conflict as there is no way to revert the original action.
+
+    ``state`` may be an instance of ``ConflictResolverState`` that
+    can be used to resume execution and resolve the new actions against the
+    list of executed actions from a previous call.
+
     """
+    if state is None:
+        state = ConflictResolverState()
+
+    # pick up where we left off last time, but track the new actions as well
+    state.remaining_actions.extend(normalize_actions(actions))
+    actions = state.remaining_actions
 
     def orderandpos(v):
         n, v = v
-        if not isinstance(v, dict):
-            # old-style tuple action
-            v = expand_action(*v)
         return (v['order'] or 0, n)
 
-    sactions = sorted(enumerate(actions), key=orderandpos)
-
     def orderonly(v):
         n, v = v
-        if not isinstance(v, dict):
-            # old-style tuple action
-            v = expand_action(*v)
         return v['order'] or 0
 
+    sactions = sorted(enumerate(actions, start=state.start), key=orderandpos)
     for order, actiongroup in itertools.groupby(sactions, orderonly):
         # "order" is an integer grouping. Actions in a lower order will be
         # executed before actions in a higher order.  All of the actions in
         # one grouping will be executed (its callable, if any will be called)
         # before any of the actions in the next.
-        
-        unique = {}
         output = []
+        unique = {}
+
+        # error out if we went backward in order
+        if state.min_order is not None and order < state.min_order:
+            r = ['Actions were added to order={0} after execution had moved '
+                 'on to order={1}. Conflicting actions: '
+                 .format(order, state.min_order)]
+            for i, action in actiongroup:
+                for line in str(action['info']).rstrip().split('\n'):
+                    r.append("  " + line)
+            raise ConfigurationError('\n'.join(r))
 
         for i, action in actiongroup:
             # Within an order, actions are executed sequentially based on
             # original action ordering ("i").
 
-            if not isinstance(action, dict):
-                # old-style tuple action
-                action = expand_action(*action)
-
-            # "ainfo" is a tuple of (order, i, action) where "order" is a
-            # user-supplied grouping, "i" is an integer expressing the relative
-            # position of this action in the action list being resolved, and
-            # "action" is an action dictionary.  The purpose of an ainfo is to
-            # associate an "order" and an "i" with a particular action; "order"
-            # and "i" exist for sorting purposes after conflict resolution.
-            ainfo = (order, i, action)
+            # "ainfo" is a tuple of (i, action) where "i" is an integer
+            # expressing the relative position of this action in the action
+            # list being resolved, and "action" is an action dictionary.  The
+            # purpose of an ainfo is to associate an "i" with a particular
+            # action; "i" exists for sorting after conflict resolution.
+            ainfo = (i, action)
 
+            # wait to defer discriminators until we are on their order because
+            # the discriminator may depend on state from a previous order
             discriminator = undefer(action['discriminator'])
             action['discriminator'] = discriminator
 
@@ -1266,28 +1267,39 @@ def resolveConflicts(actions):
 
         # Check for conflicts
         conflicts = {}
-
         for discriminator, ainfos in unique.items():
-            # We use (includepath, order, i) as a sort key because we need to
+            # We use (includepath, i) as a sort key because we need to
             # sort the actions by the paths so that the shortest path with a
             # given prefix comes first.  The "first" action is the one with the
-            # shortest include path.  We break sorting ties using "order", then
-            # "i".
+            # shortest include path.  We break sorting ties using "i".
             def bypath(ainfo):
-                path, order, i = ainfo[2]['includepath'], ainfo[0], ainfo[1]
+                path, i = ainfo[1]['includepath'], ainfo[0]
                 return path, order, i
 
             ainfos.sort(key=bypath)
             ainfo, rest = ainfos[0], ainfos[1:]
-            output.append(ainfo)
-            _, _, action = ainfo
-            basepath, baseinfo, discriminator = (
-                action['includepath'],
-                action['info'],
-                action['discriminator'],
-                )
+            _, action = ainfo
+
+            # ensure this new action does not conflict with a previously
+            # resolved action from an earlier order / invocation
+            prev_ainfo = state.resolved_ainfos.get(discriminator)
+            if prev_ainfo is not None:
+                _, paction = prev_ainfo
+                basepath, baseinfo = paction['includepath'], paction['info']
+                includepath = action['includepath']
+                # if the new action conflicts with the resolved action then
+                # note the conflict, otherwise drop the action as it's
+                # effectively overriden by the previous action
+                if (includepath[:len(basepath)] != basepath or
+                        includepath == basepath):
+                    L = conflicts.setdefault(discriminator, [baseinfo])
+                    L.append(action['info'])
+
+            else:
+                output.append(ainfo)
 
-            for _, _, action in rest:
+            basepath, baseinfo = action['includepath'], action['info']
+            for _, action in rest:
                 includepath = action['includepath']
                 # Test whether path is a prefix of opath
                 if (includepath[:len(basepath)] != basepath or  # not a prefix
@@ -1298,14 +1310,30 @@ def resolveConflicts(actions):
         if conflicts:
             raise ConfigurationConflictError(conflicts)
 
-        # sort conflict-resolved actions by (order, i) and yield them one
-        # by one
-        for a in [x[2] for x in sorted(output, key=operator.itemgetter(0, 1))]:
-            yield a
+        # sort resolved actions by "i" and yield them one by one
+        for i, action in sorted(output, key=operator.itemgetter(0)):
+            # do not memoize the order until we resolve an action inside it
+            state.min_order = action['order']
+            state.start = i + 1
+            state.remaining_actions.remove(action)
+            state.resolved_ainfos[action['discriminator']] = (i, action)
+            yield action
 
 
-def expand_action(discriminator, callable=None, args=(), kw=None,
-                  includepath=(), info=None, order=0, introspectables=()):
+def normalize_actions(actions):
+    """Convert old-style tuple actions to new-style dicts."""
+    result = []
+    for v in actions:
+        if not isinstance(v, dict):
+            v = expand_action_tuple(*v)
+        result.append(v)
+    return result
+
+
+def expand_action_tuple(
+    discriminator, callable=None, args=(), kw=None, includepath=(),
+    info=None, order=0, introspectables=(),
+):
     if kw is None:
         kw = {}
     return dict(
@@ -1319,4 +1347,5 @@ def expand_action(discriminator, callable=None, args=(), kw=None,
         introspectables=introspectables,
         )
 
+
 global_registries = WeakOrderedSet()
diff --git a/pyramid/tests/test_config/test_init.py b/pyramid/tests/test_config/test_init.py
index 7e1a856cf..7078d7e26 100644
--- a/pyramid/tests/test_config/test_init.py
+++ b/pyramid/tests/test_config/test_init.py
@@ -1728,15 +1728,14 @@ class Test_resolveConflicts(unittest.TestCase):
 
     def test_it_success_dicts(self):
         from pyramid.tests.test_config import dummyfactory as f
-        from pyramid.config import expand_action
         result = self._callFUT([
-            expand_action(None, f),
-            expand_action(1, f, (1,), {}, (), 'first'),
-            expand_action(1, f, (2,), {}, ('x',), 'second'),
-            expand_action(1, f, (3,), {}, ('y',), 'third'),
-            expand_action(4, f, (4,), {}, ('y',), 'should be last', 99999),
-            expand_action(3, f, (3,), {}, ('y',)),
-            expand_action(None, f, (5,), {}, ('y',)),
+            (None, f),
+            (1, f, (1,), {}, (), 'first'),
+            (1, f, (2,), {}, ('x',), 'second'),
+            (1, f, (3,), {}, ('y',), 'third'),
+            (4, f, (4,), {}, ('y',), 'should be last', 99999),
+            (3, f, (3,), {}, ('y',)),
+            (None, f, (5,), {}, ('y',)),
             ])
         result = list(result)
         self.assertEqual(
@@ -1802,17 +1801,16 @@ class Test_resolveConflicts(unittest.TestCase):
 
     def test_it_with_actions_grouped_by_order(self):
         from pyramid.tests.test_config import dummyfactory as f
-        from pyramid.config import expand_action
         result = self._callFUT([
-            expand_action(None, f),                                 # X
-            expand_action(1, f, (1,), {}, (), 'third', 10),         # X
-            expand_action(1, f, (2,), {}, ('x',), 'fourth', 10),
-            expand_action(1, f, (3,), {}, ('y',), 'fifth', 10),
-            expand_action(2, f, (1,), {}, (), 'sixth', 10),         # X
-            expand_action(3, f, (1,), {}, (), 'seventh', 10),       # X
-            expand_action(5, f, (4,), {}, ('y',), 'eighth', 99999), # X
-            expand_action(4, f, (3,), {}, (), 'first', 5),          # X
-            expand_action(4, f, (5,), {}, ('y',), 'second', 5),
+            (None, f),                                 # X
+            (1, f, (1,), {}, (), 'third', 10),         # X
+            (1, f, (2,), {}, ('x',), 'fourth', 10),
+            (1, f, (3,), {}, ('y',), 'fifth', 10),
+            (2, f, (1,), {}, (), 'sixth', 10),         # X
+            (3, f, (1,), {}, (), 'seventh', 10),       # X
+            (5, f, (4,), {}, ('y',), 'eighth', 99999), # X
+            (4, f, (3,), {}, (), 'first', 5),          # X
+            (4, f, (5,), {}, ('y',), 'second', 5),
             ])
         result = list(result)
         self.assertEqual(len(result), 6)