37 

    38 def successorssets(repo, initialnode, cache=None):

    39     """Return set of all latest successors of initial nodes

    40 

    41     The successors set of a changeset A are the group of revisions that succeed

    42     A. It succeeds A as a consistent whole, each revision being only a partial

    43     replacement. The successors set contains non-obsolete changesets only.

    44 

    45     This function returns the full list of successor sets which is why it

    46     returns a list of tuples and not just a single tuple. Each tuple is a valid

    47     successors set. Note that (A,) may be a valid successors set for changeset A

    48     (see below).

    49 

    50     In most cases, a changeset A will have a single element (e.g. the changeset

    51     A is replaced by A') in its successors set. Though, it is also common for a

    52     changeset A to have no elements in its successor set (e.g. the changeset

    53     has been pruned). Therefore, the returned list of successors sets will be

    54     [(A',)] or [], respectively.

    55 

    56     When a changeset A is split into A' and B', however, it will result in a

    57     successors set containing more than a single element, i.e. [(A',B')].

    58     Divergent changesets will result in multiple successors sets, i.e. [(A',),

    59     (A'')].

    60 

    61     If a changeset A is not obsolete, then it will conceptually have no

    62     successors set. To distinguish this from a pruned changeset, the successor

    63     set will contain itself only, i.e. [(A,)].

    64 

    65     Finally, successors unknown locally are considered to be pruned (obsoleted

    66     without any successors).

    67 

    68     The optional `cache` parameter is a dictionary that may contain precomputed

    69     successors sets. It is meant to reuse the computation of a previous call to

    70     `successorssets` when multiple calls are made at the same time. The cache

    71     dictionary is updated in place. The caller is responsible for its life

    72     span. Code that makes multiple calls to `successorssets` *must* use this

    73     cache mechanism or suffer terrible performance.

    74     """

    75 

    76     succmarkers = repo.obsstore.successors

    77 

    78     # Stack of nodes we search successors sets for

    79     toproceed = [initialnode]

    80     # set version of above list for fast loop detection

    81     # element added to "toproceed" must be added here

    82     stackedset = set(toproceed)

    83     if cache is None:

    84         cache = {}

    85 

    86     # This while loop is the flattened version of a recursive search for

    87     # successors sets

    88     #

    89     # def successorssets(x):

    90     #    successors = directsuccessors(x)

    91     #    ss = [[]]

    92     #    for succ in directsuccessors(x):

    93     #        # product as in itertools cartesian product

    94     #        ss = product(ss, successorssets(succ))

    95     #    return ss

    96     #

    97     # But we can not use plain recursive calls here:

    98     # - that would blow the python call stack

    99     # - obsolescence markers may have cycles, we need to handle them.

   100     #

   101     # The `toproceed` list act as our call stack. Every node we search

   102     # successors set for are stacked there.

   103     #

   104     # The `stackedset` is set version of this stack used to check if a node is

   105     # already stacked. This check is used to detect cycles and prevent infinite

   106     # loop.

   107     #

   108     # successors set of all nodes are stored in the `cache` dictionary.

   109     #

   110     # After this while loop ends we use the cache to return the successors sets

   111     # for the node requested by the caller.

   112     while toproceed:

   113         # Every iteration tries to compute the successors sets of the topmost

   114         # node of the stack: CURRENT.

   115         #

   116         # There are four possible outcomes:

   117         #

   118         # 1) We already know the successors sets of CURRENT:

   119         #    -> mission accomplished, pop it from the stack.

   120         # 2) Node is not obsolete:

   121         #    -> the node is its own successors sets. Add it to the cache.

   122         # 3) We do not know successors set of direct successors of CURRENT:

   123         #    -> We add those successors to the stack.

   124         # 4) We know successors sets of all direct successors of CURRENT:

   125         #    -> We can compute CURRENT successors set and add it to the

   126         #       cache.

   127         #

   128         current = toproceed[-1]

   129         if current in cache:

   130             # case (1): We already know the successors sets

   131             stackedset.remove(toproceed.pop())

   132         elif current not in succmarkers:

   133             # case (2): The node is not obsolete.

   134             if current in repo:

   135                 # We have a valid last successors.

   136                 cache[current] = [(current,)]

   137             else:

   138                 # Final obsolete version is unknown locally.

   139                 # Do not count that as a valid successors

   140                 cache[current] = []

   141         else:

   142             # cases (3) and (4)

   143             #

   144             # We proceed in two phases. Phase 1 aims to distinguish case (3)

   145             # from case (4):

   146             #

   147             #     For each direct successors of CURRENT, we check whether its

   148             #     successors sets are known. If they are not, we stack the

   149             #     unknown node and proceed to the next iteration of the while

   150             #     loop. (case 3)

   151             #

   152             #     During this step, we may detect obsolescence cycles: a node

   153             #     with unknown successors sets but already in the call stack.

   154             #     In such a situation, we arbitrary set the successors sets of

   155             #     the node to nothing (node pruned) to break the cycle.

   156             #

   157             #     If no break was encountered we proceed to phase 2.

   158             #

   159             # Phase 2 computes successors sets of CURRENT (case 4); see details

   160             # in phase 2 itself.

   161             #

   162             # Note the two levels of iteration in each phase.

   163             # - The first one handles obsolescence markers using CURRENT as

   164             #   precursor (successors markers of CURRENT).

   165             #

   166             #   Having multiple entry here means divergence.

   167             #

   168             # - The second one handles successors defined in each marker.

   169             #

   170             #   Having none means pruned node, multiple successors means split,

   171             #   single successors are standard replacement.

   172             #

   173             for mark in sorted(succmarkers[current]):

   174                 for suc in mark[1]:

   175                     if suc not in cache:

   176                         if suc in stackedset:

   177                             # cycle breaking

   178                             cache[suc] = []

   179                         else:

   180                             # case (3) If we have not computed successors sets

   181                             # of one of those successors we add it to the

   182                             # `toproceed` stack and stop all work for this

   183                             # iteration.

   184                             toproceed.append(suc)

   185                             stackedset.add(suc)

   186                             break

   187                 else:

   188                     continue

   189                 break

   190             else:

   191                 # case (4): we know all successors sets of all direct

   192                 # successors

   193                 #

   194                 # Successors set contributed by each marker depends on the

   195                 # successors sets of all its "successors" node.

   196                 #

   197                 # Each different marker is a divergence in the obsolescence

   198                 # history. It contributes successors sets distinct from other

   199                 # markers.

   200                 #

   201                 # Within a marker, a successor may have divergent successors

   202                 # sets. In such a case, the marker will contribute multiple

   203                 # divergent successors sets. If multiple successors have

   204                 # divergent successors sets, a Cartesian product is used.

   205                 #

   206                 # At the end we post-process successors sets to remove

   207                 # duplicated entry and successors set that are strict subset of

   208                 # another one.

   209                 succssets = []

   210                 for mark in sorted(succmarkers[current]):

   211                     # successors sets contributed by this marker

   212                     markss = [[]]

   213                     for suc in mark[1]:

   214                         # cardinal product with previous successors

   215                         productresult = []

   216                         for prefix in markss:

   217                             for suffix in cache[suc]:

   218                                 newss = list(prefix)

   219                                 for part in suffix:

   220                                     # do not duplicated entry in successors set

   221                                     # first entry wins.

   222                                     if part not in newss:

   223                                         newss.append(part)

   224                                 productresult.append(newss)

   225                         markss = productresult

   226                     succssets.extend(markss)

   227                 # remove duplicated and subset

   228                 seen = []

   229                 final = []

   230                 candidate = sorted(((set(s), s) for s in succssets if s),

   231                                    key=lambda x: len(x[1]), reverse=True)

   232                 for setversion, listversion in candidate:

   233                     for seenset in seen:

   234                         if setversion.issubset(seenset):

   235                             break

   236                     else:

   237                         final.append(listversion)

   238                         seen.append(setversion)

   239                 final.reverse() # put small successors set first

   240                 cache[current] = final

   241     return cache[initialnode]