- Timestamp:
- 12/19/2021 04:30:10 PM (3 years ago)
- Branches:
- ablfs-more, legacy, trunk
- Children:
- 141d072
- Parents:
- e0bbc6e
- git-author:
- Pierre Labastie <pierre.labastie@…> (12/19/2021 04:24:52 PM)
- git-committer:
- Pierre Labastie <pierre.labastie@…> (12/19/2021 04:30:10 PM)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
BLFS/libs/func_dependencies
re0bbc6e ra78cfc9 30 30 # on A with a "before" qualifier, C may need B to be able to use A. So the # 31 31 # only safe way to consider "after" qualifiers is to consider that they are # 32 # "before" deps for any parent of the packages considered. # 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. # 33 35 # We'll therefore have a 3 pass procedure. First build the set of nodes # 34 36 # reachable from the root set. Second, remove dangling edges (those pointing # … … 74 76 # - The qualifier (for printing) # 75 77 # # 78 # Pass 2: graph transformation # 79 # ============================ # 80 # We now have three loops over nodes of the graph # 81 # Loop 1: Remove dead edges # 82 # ------------------------- # 83 # Since some nodes have not been created because the edge leading to them # 84 # had too high a weight, the edges leading to them have to be suppressed. # 85 # For each existing node file, we make a list of lines to remove by # 86 # testing whether the destination exists. We then remove the lines. # 87 # Another approach would be to make a temporary file and output only # 88 # lines that should stay, then rename the file. This would save a loop. # 89 # All in all it is an N*e process, where N is the number of nodes and e # 90 # the average number of edges originating from a node. # 91 # Loop 2: Treat "after" edges # 92 # --------------------------- # 93 # If a node is the origin of edges qualified as "after", we want the # 94 # nodes which are the destination of those edges to be built after # 95 # the origin node, but before any node that depend on the origin # 96 # node. For that, the general rule is to change: # 97 # P---b--->A---a--->D # 98 # to: # 99 # P---b--->Agroupxx---b--->A # 100 # | # 101 # ---b--->D # 102 # But there is a problem if D depends on P, possibly through a chain, # 103 # because we create a cycle which shouldn't exist. If this is the case, # 104 # we leave A as a dependency of P: # 105 # P---b--->A # 106 # # 107 # Agroupxx---b--->A # 108 # | # 109 # ---b--->D # 110 # Doing so, it may happen that Agroupxx has no parent. We then add # 111 # Agroupxx as a dependency of root. The problem with this algorithm is # 112 # the search for paths from D to A, which may be exponential in the # 113 # number of nodes in the graph. # 76 114 # TODO: document other passes # 77 115 # TODO: needs also to document the .tree files #
Note:
See TracChangeset
for help on using the changeset viewer.