Changeset abadee3
- Timestamp:
- 12/30/2021 01:20:43 PM (2 years ago)
- Branches:
- ablfs-more, legacy, trunk
- Children:
- 20051e0
- Parents:
- f81d8bd
- File:
-
- 1 edited
-
BLFS/libs/func_dependencies (modified) (4 diffs)
Legend:
- Unmodified
- Added
- Removed
-
BLFS/libs/func_dependencies
rf81d8bd rabadee3 18 18 # We should consider only edges with weight lower or equal to that # 19 19 # specified by the user, but see below. # 20 # - we do not want to build the whole book. The user specifies a set of#21 # packages, and we have to consider only nodes reachable from this set#20 # - we do not want to build the whole book. The user requests a set of # 21 # packages, and we'd like to consider only nodes reachable from this set # 22 22 # using edges of weight not exceeding the specified weight. # 23 # - we do not want to rebuild packages already built. But we still have to # 24 # generate the full dependency graph, because if A depends on B, which is # 25 # already built, and B depends on C, which is not built, or needs to be # 26 # updated, then A may depends on C. We therefore have to remove already # 27 # built (and up to date) packages from the graph, but need to keep the # 28 # dependency chain. # 23 29 # - when doing the topological sort, we want to consider all the edges and # 24 30 # not only those not exceeding the specified weight: If a package A in the # 25 31 # reachable subgraph depends optionally on another package B in the same # 26 # subgraph, we want to build B before A. But this means we'll have to # 27 # remove cycles for all weights. # 28 # - dependencies have another qualifier: before or after. The problem: if a # 29 # package A depends on B with an "after" qualifier, and a package C depends # 30 # on A with a "before" qualifier, C may need B to be able to use A. So the # 31 # only safe way to consider "after" qualifiers is to consider that they are # 32 # "before" deps for any parent of the packages considered. There is an # 33 # exception to that rule: if B depends on C (possibly through a chain of # 34 # several dependencies), then C should still be built before B. # 32 # subgraph, we want to build B before A if possible. But this means we'll # 33 # have to remove cycles for all weights. # 34 # - dependencies have another qualifier: before, after, or first. We use # 35 # it as follows: for "after", we can build the dependency after the # 36 # package, but if a package A depends on B with an "after" qualifier, and # 37 # a package C depends on A with a "before" qualifier, C may need B to be # 38 # able to use A. So the only safe way to consider "after" qualifiers is to # 39 # consider that they are "before" deps for any parent of the packages # 40 # considered. There is an exception to that rule: if B depends on C # 41 # (possibly through a chain of several dependencies), then C should still # 42 # be built before B. For "after", the dependency has to be built both # 43 # before and after the package. So we duplicate the dependency as a # 44 # "-pass1" package, and change the graph accordingly. # 35 45 # We'll therefore have a 3 pass procedure. First build the set of nodes # 36 46 # reachable from the root set. Second, remove dangling edges (those pointing # 37 47 # to packages outside the node set), and move "after" edges to "before" edges # 38 # originating from the parents . Third remove cycles and generate a#39 # topological sort.#48 # originating from the parents as well as creating the "-pass1" nodes. Third # 49 # remove cycles and generate a topological sort. # 40 50 # # 41 51 # Pass 1: graph generation # … … 43 53 # Data layout for pass 1 # 44 54 # ---------------------- # 45 # A node of the treeis represented by a text file <nodeName>.dep. Each edge #55 # A node of the graph is represented by a text file <nodeName>.dep. Each edge # 46 56 # starting from this node is represented by a line in this file. We keep # 47 57 # those files in the same directory. We introduce a special node named root, # … … 81 91 # Loop 1: Remove dead edges # 82 92 # ------------------------- # 83 # Since some nodes have not been created because the edge leading to them#84 # had too high a weight, th e edges leading to them have to be suppressed.#93 # Since some nodes have not been created because the edges leading to them # 94 # had too high a weight, those edges have to be suppressed. # 85 95 # For each existing node file, we make a list of lines to remove by # 86 96 # testing whether the destination exists. We then remove the lines. # … … 112 122 # the search for paths from D to A, which may be exponential in the # 113 123 # number of nodes in the graph. # 114 # TODO: document other passes # 124 # # 125 # Loop 3: Add -pass1 nodes # 126 # ------------------------ # 127 # Sometimes there is no way to escape a cycle. A package A needs B, and B # 128 # needs A. In that case, it is often possible to build a degraded version # 129 # of package A, then B, then rebuild A. The book indicates this with the # 130 # following dependency chain, using a qualifier of "first": # 131 # B---f--->A---b--->X...Y---b--->B # 132 # where the X...Y notation represents a chain of dependencies from A to B. # 133 # So the third loop is over nodes containing "f" qualifiers, and does the # 134 # following: it creates a new node A-pass1, which is a copy of A, and # 135 # remove from A-pass1 all the dependencies leading to B through a chain, # 136 # to obtain: # 137 # A---b--->X...Y---b--->B---b--->A-pass1 # 138 # It may then happen that nothing depends on A. So this is tested, and A # 139 # is added to the root node if it is orphaned. # 140 # TODO: document the third pass # 115 141 # TODO: needs also to document the .tree files # 116 142 # TODO: The following is obsolete #
Note:
See TracChangeset
for help on using the changeset viewer.
