source: BLFS/libs/func_dependencies@ bbabe74

ablfs-more legacy trunk
Last change on this file since bbabe74 was dd9ca56, checked in by Pierre Labastie <pierre.labastie@…>, 3 years ago

BLFS dependencies: better document the functions

First the function used in pass1. Also some nit in the function itself

  • Property mode set to 100644
File size: 22.1 KB
RevLine 
[3c10176]1#!/bin/bash
2#
3
[2140f22]4#-----------------------------------------------------------------------------#
5# This is a set of (recursive) functions for manipulating a dependency graph. #
6# We use algorithms and definitions from chapter 4 (mainly section 4.2) of #
7# https://algs4.cs.princeton.edu/. The graph we manipulate is the directed #
8# graph of the dependencies: nodes are packages in the BLFS book. A node A is #
9# connected to a node B if package A depends on B. A topological order (rev- #
10# erted) is exactly what we want for a build order. But a topological order #
11# only exists if the graph is acyclic. We'll therefore have to remove cycles. #
12# There are a number of other features we want to consider: #
13# - edges are weighted according to the dependency requirement: #
14# 1 for required #
15# 2 for recommended #
16# 3 for optional #
17# 4 for external #
18# We should consider only edges with weight lower or equal to that #
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 #
22# using edges of weight not exceeding the specified weight. #
23# - when doing the topological sort, we want to consider all the edges and #
24# not only those not exceeding the specified weight: If a package A in the #
25# 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. #
33# We'll therefore have a 3 pass procedure. First build the set of nodes #
34# reachable from the root set. Second, remove dangling edges (those pointing #
35# to packages outside the node set), and move "after" edges to "before" edges #
36# originating from the parents. Third remove cycles and generate a #
37# topological sort. #
38# #
[dd9ca56]39# Pass 1: graph generation #
40# ======================== #
41# Data layout for pass 1 #
42# ---------------------- #
[2140f22]43# A node of the tree is represented by a text file <nodeName>.dep. Each edge #
44# starting from this node is represented by a line in this file. We keep #
45# those files in the same directory. We introduce a special node named root, #
46# whose edges point to the list of nodes requested by the user. Each line #
47# contains three fields: #
48# - the weight of the edge #
[dd9ca56]49# - the qualifier: "before" (b), "after" (a), or "first" (f) #
50# - the name of the destination of the edge (without the ".dep" extension) #
51# #
52# Recursive function "generate_subgraph" #
53# -------------------------------------- #
54# This function treats a node of the graph that is not a leaf and that is #
55# seen for the first time in the DFS. The dependencies of this node are #
56# known, and stored in a .dep file. For each dependency in that file, there #
57# are three cases: #
58# - the weight of the edge leading to that dependency is higher than #
59# requested. This dependency is discarded (some information printed) #
60# - the weight of the edge is lower or equal to requested, but the node #
61# has already been visited (the .dep file exists). Discard too (some #
62# information printed) #
63# - the weight of the edge is lower or equal to requested, and the node #
64# has not been seen: then the dependencies of that node are generated, #
65# and there are two cases: #
66# - the node has no dependencies: just create an empty .dep file, so #
67# that we know the node has been visited #
68# - the node has dependencies: call generate_subgraph for that node #
69# #
70# This function takes four parameters: #
71# - The node filename: this is the only one useful for the algorithm #
72# - The depth: number of steps starting from root (for pretty print only) #
73# - The weight of the edge leading to that node (for printing) #
74# - The qualifier (for printing) #
75# #
76# TODO: document other passes #
77# TODO: needs also to document the .tree files #
78# TODO: The following is obsolete #
[d7c07e0]79# Circular dependencies: #
[7dc8595]80# #
[d7c07e0]81# In case we find a cirdular dependency, it has the form : #
82# parent->dependency_0->...->dependency_n->dependency_0 #
83# If we want to build dependency_n before dependency_0, no problem: #
84# we just prune the tree at dependency_n. If we want to build first #
85# dependency_0, we need to put dependency_n as a dependency of parent, #
86# then erase and rebuild the subtree from there. Now, we may have met #
87# another circular dependency in the subtree, and erasing the tree makes #
88# us forget the decision which was made. So, after first generating the #
89# list of dependencies from packages.xml, we keep the generated list in #
90# a file <nodeName>.odep, which we modify according to the decision which #
91# was made. #
[e4b1293]92#---------------------------------------------------------------------------#
93
94# Global variables:
[e576789]95# A string of spaces for indenting:
[3c10176]96declare -a spaceSTR=" "
[2140f22]97# When we are backing up from a circular dependency, `parentNode'
98# contains the node which has an edge entering the cycle
99declare parentNode
[3c10176]100
[2140f22]101#---------------------#
102generate_subgraph() { #
103#---------------------#
[3c10176]104: <<inline_doc
[2140f22]105 function: Create a subgraph of all the nodes reachable from the node
106 represented by the file whose name is $1. The edges considered
107 are those with maximal weight DEP_LEVEL (recursive function).
108 input vars: $1 : file name corresponding to the node whose edges will be
109 followed for the DFS
110 $2 : weight of the edge leading to this node
111 $3 : depth (root is 1)
[dd9ca56]112 $4 : qualifier (a for after, b for before, f for first)
[7ac11f0]113 externals: vars: DEP_LEVEL contains 1 if we want to build the
114 tree only for required dependencies,
115 2 if we want also recommended ones,
[2140f22]116 3 if we want also optional ones, but only
117 for the requested packages,
118 4 if we want all the dependencies
[dd9ca56]119 (excluding external of course)
[7ac11f0]120 MAIL_SERVER contains the name of the MTA we want to use.
121 files: ../xsl/dependencies.xsl: stylesheet for creating the
122 .dep files
[e91a15d]123 ../packages.xml: File containing packages id
[7ac11f0]124 and dependencies
[2140f22]125 returns: 0 if the tree has been successfully created
126 output: files: for each node reachable from $1, a file <node>.dep.
127 on error: nothing
128 on success: nothing
129inline_doc
130
131local depFile=$1
132local -i weight=$2
133local -i depth=$3
134local qualifier=$4
135local -i spacing=0
136local priostring
137local buildstring
138local id_of_dep
139local prio_of_dep
140local build_of_dep
141local dep_level
142
143if (( depth < 10 )); then spacing=1; fi
144case $weight in
145 1) priostring=required ;;
146 2) priostring=recommended ;;
147 3) priostring=optional ;;
148esac
149case $qualifier in
[dd9ca56]150 a) buildstring=runtime ;;
151 b|f) buildstring= ;;
[2140f22]152esac
153dep_level=$DEP_LEVEL
154if [ "$dep_level" = 3 ] && [ "$depth" -gt 2 ]; then dep_level=2; fi
155if [ "$dep_level" -gt 3 ]; then dep_level=3; fi
156echo -en "\nNode: $depth${spaceSTR:0:$(( depth + spacing ))}${RED}${depFile%.dep}${OFF} $priostring $buildstring"
157
158depth=$(( depth + 1 ))
159if (( depth < 10 )); then spacing=1; else spacing=0; fi
160# Start of loop
161{
162while read prio_of_dep build_of_dep id_of_dep; do
[e030049]163 case $prio_of_dep in
[2140f22]164 1) priostring=required ;;
165 2) priostring=recommended ;;
166 3) priostring=optional ;;
167 4) priostring=external ;;
[e030049]168 esac
169 case $build_of_dep in
[dd9ca56]170 a ) buildstring=runtime ;;
171 b|f) buildstring= ;;
[e030049]172 esac
173# Has this entry already been seen?
[dd9ca56]174# TODO: no there is no special case!
[e030049]175# We have a special case here: if the entry has been seen at depth > 2
176# and now depth=2 and DEP_LEVEL=3, optional deps have not been processed.
177# If this is the case, just consider it has not been seen.
[2140f22]178 if [ -f ${id_of_dep}.dep ] ; then
[e030049]179 case $depth$DEP_LEVEL in
180 23) ;;
181 *)
[2140f22]182# Just display it and proceed.
[e030049]183 echo -en "\nEdge: $depth${spaceSTR:0:$((depth + spacing))}${MAGENTA}${id_of_dep}${OFF} $priostring $buildstring"
184 continue
185 ;;
186 esac
[2140f22]187 fi
188# Is the weight higher than requested?
189 if [ "$prio_of_dep" -gt $dep_level ]; then
190# Just display it and proceed.
191 echo -en "\n Out: $depth${spaceSTR:0:$((depth + spacing))}${YELLOW}${id_of_dep}${OFF} $priostring $buildstring"
192 continue
193 fi
194# Otherwise, let's build the corresponding subgraph.
195 xsltproc --stringparam idofdep "$id_of_dep" \
196 --stringparam MTA "$MAIL_SERVER" \
197 -o ${id_of_dep}.dep \
198 ../xsl/dependencies.xsl ../packages.xml
199
200 if [[ -s ${id_of_dep}.dep ]]; then # this dependency has dependencies
201 generate_subgraph ${id_of_dep}.dep $prio_of_dep $depth $build_of_dep
202 else # id_of_dep has no dependencies, just touch the file and display
203 touch ${id_of_dep}.dep
204 echo -en "\nLeaf: $depth${spaceSTR:0:$((depth + spacing))}${CYAN}${id_of_dep}${OFF} $priostring $buildstring"
205 fi
206done
207} <$depFile
208depth=$(( depth - 1 ))
209if (( depth < 10 )); then spacing=1; else spacing=0; fi
210echo -en "\n End: $depth${spaceSTR:0:$((depth + spacing))}${GREEN}${depFile%.dep}${OFF}"
211return 0
212}
213
214#-----------#
215path_to() { #
216#-----------#
217: <<inline_doc
218 function: check whether there is a path from $1 to $2 on the graph
219 input vars: $1 contains the filename of the starting node.
220 $2 contains the name of the node to reach
221 $3 contains the weight above which we do not want to
222 follow an edge
223 "seen" (global) contains the list of already seen nodes
224 returns: 0 if the node has been found
225 1 if not
226 on error: nothing
227 on success: nothing
228inline_doc
229local start=$1
230local seek=$2
231local prio=$3
232local prio_of_dep
233local build_of_dep
234local id_of_dep
235local r
236
237if test "${start%.dep}" = "$seek"; then return 0; fi
[59afe73]238seen="$seen${start%.dep} "
[5afaf7c]239if test -s $start; then
[2140f22]240 {
241 while read prio_of_dep build_of_dep id_of_dep; do
242 if test "$prio" -lt "$prio_of_dep"; then continue; fi
[5afaf7c]243 if ! test "${seen% $id_of_dep *}" = "$seen"; then continue; fi
[2140f22]244 if path_to ${id_of_dep}.dep $seek $prio; then return 0; fi
245 done
246 } < $start
247fi
248return 1
249}
250#------------------#
251clean_subgraph() { #
252#------------------#
253: <<inline_doc
254 function: Remove dangling edges and create groups of deps for "after"
255 deps: A-before->B-after->C becomes:
256 A -before-> Bgroupxx -before-> B
257 \
258 -before-> C
259 the name of the group is chosen so that it is unlikely as
260 a package name (so that it is removed when building the
261 xml book).
262 input vars: None
263 files: <node>.dep files containing dangling edges and
264 "after" qualifiers
265 returns: 0
266 output: files: <node>.dep files containing no dangling edges and
267 no "after" qualifiers
268 on error: nothing
269 on success: nothing
270inline_doc
271
272local node
273local id_of_dep
274local prio_of_dep
275local build_of_dep
276local lines_to_remove
277local lines_to_change
278local parent
279local p
280local b
281local start
282local seen
283
284for node in $(ls *.dep); do
285 if test $node = root.dep; then continue; fi
[28546ae]286 echo Cleaning $node
[2140f22]287 lines_to_remove=
288 {
289 while read prio_of_dep build_of_dep id_of_dep; do
290 if ! test -f ${id_of_dep}.dep; then
291 lines_to_remove="$lines_to_remove $id_of_dep"
292 continue
293 fi
294 done
295 } <$node
296 for id_of_dep in $lines_to_remove; do
297 sed "/\ $id_of_dep\$/d" -i $node
298 done
299done
300for node in $(grep -l ' a ' *.dep); do
301 lines_to_remove=
[28546ae]302 echo Process "runtime" deps in $node
[2140f22]303 if ! [ -e ${node%.dep}groupxx.dep ]; then
[f1edc8e]304 b=0
[2140f22]305 for parent in $(grep -l ${node%.dep}\$ *); do
306 p=0
307 for start in $(grep ' a ' $node | cut -d' ' -f3); do
308 seen=" "
309 if path_to ${start}.dep ${parent%.dep} 3; then p=1; break; fi
310 done
311 if test $p = 0; then
[f1edc8e]312 b=1
[2140f22]313 sed -i "s/\ ${node%.dep}\$/&groupxx/" $parent
314 fi
315 done
316 echo "1 b ${node%.dep}" > ${node%.dep}groupxx.dep
[f1edc8e]317 if test $b = 0; then echo "1 b ${node%.dep}groupxx" >> root.dep; fi
[2140f22]318 fi
319 {
320 while read prio_of_dep build_of_dep id_of_dep; do
321 if test $build_of_dep = a; then
322 if ! grep -q ${id_of_dep} ${node%.dep}groupxx.dep; then
323 echo "$prio_of_dep b ${id_of_dep}" >> ${node%.dep}groupxx.dep
324 fi
325 lines_to_remove="$lines_to_remove $id_of_dep"
326 fi
327 done
328 } <$node
329 for id_of_dep in $lines_to_remove; do
330 sed "/\ $id_of_dep\$/d" -i $node
331 done
332done
333for node in $(grep -l ' f ' *); do
[28546ae]334 echo Process "first" deps in $node
[2140f22]335 lines_to_change=
336 {
337 while read prio_of_dep build_of_dep id_of_dep; do
338 if test $build_of_dep = f; then
339 if ! test -f ${id_of_dep}-pass1.dep; then
340 cp ${id_of_dep}{,-pass1}.dep;
341 fi
342 lines_to_change="$lines_to_change $id_of_dep"
343 unset lr
344 {
345 while read p b start; do
346 seen=" "
347 if path_to ${start}.dep ${node%.dep} $p; then
348 lr="$lr $start"
349 fi
350 done
351 } < ${id_of_dep}-pass1.dep
352 for p in $lr; do
353 sed "/\ $p\$/d" -i ${id_of_dep}-pass1.dep
354 done
355 fi
356 done
357 } <$node
358 for id_of_dep in $lines_to_change; do
[d80302b]359 sed "/\ $id_of_dep\$/"'{s/[[:digit:]] f /1 b /;s/$/-pass1/}' -i $node
[2140f22]360 done
361done
362} # End clean_subgraph
363
364#----------------------------#
365generate_dependency_tree() { #
366#----------------------------#
367: <<inline_doc
368 function: Create a subtree of the dependency tree
369 (recursive function)
370 input vars: $1 : file with a list of targets (child nodes)
371 the first line of the file is the link
372 $2 : priority (1=req, 2=rec, 3=opt)
[e4b1293]373 returns: 0 if the tree has been successfully created
374 1 if we are backing up to the parent of a circular dep
[2140f22]375 and there are only required deps in the cycle
376 2 if we are backing up to the parent of a circular dep
377 and there are recommended deps and no optional deps in the
378 cycle
379 3 if we are backing up to the parent of a circular dep
380 and there are optiional deps in the cycle
381 modifies: vars: ParentNode is set when return is not 0
[e4b1293]382 output: files: for each <pkg> with dependencies in $1,
[2140f22]383 a file <pkg>.tree and its dependencies
[3c10176]384 on error: nothing
385 on success: nothing
386inline_doc
387
[2140f22]388local depFile=$1
[7dc8595]389local priority=$2
[e576789]390local -a rootlink
[7dc8595]391local -a priolink
[e576789]392local -a otherlink
393local -i depth
394local -i count=0
395local id_of_dep
[2140f22]396local build_of_dep
397local prio_of_dep
[e576789]398local parent
399local lines_to_remove=
400local srootlink
[7dc8595]401local priostring
402local dpriostring
403local i
[e576789]404
405{
[2140f22]406read -a rootlink
[e576789]407depth=${#rootlink[*]}
[2140f22]408read -a priolink
[e576789]409srootlink="${rootlink[*]} "
[7dc8595]410case $priority in
411 1) priostring=required ;;
412 2) priostring=recommended ;;
413 3) priostring=optional ;;
414esac
[2140f22]415# start of depFile
416echo -en "\nNode: $depth${spaceSTR:0:$depth}${RED}${depFile%.tree}${OFF} $priostring"
[e576789]417
[2140f22]418while read prio_of_dep build_of_dep id_of_dep; do
419 case $prio_of_dep in
[7dc8595]420 1) dpriostring=required ;;
421 2) dpriostring=recommended ;;
422 3) dpriostring=optional ;;
[2140f22]423 esac
[e576789]424# count entries in file
425 (( count++ ))
426# Has this entry already been seen?
[2140f22]427 if [ -f ${id_of_dep}.tree ]; then # found ${id_of_dep}.tree already in tree
428 otherlink=($(head -n 1 ${id_of_dep}.tree))
[2e1c1c3]429 if [ -z "${otherlink[*]}" ]
[2140f22]430 then echo otherlink empty for $id_of_dep.tree
[e576789]431 echo This should not happen, but happens to happen...
432 exit 1
433 fi
[2140f22]434#Do not use "${rootlink[*]}" =~ "${otherlink[*]}": case rootlink=(1 11)
[e576789]435# and otherlink=(1 1)
[e4b1293]436 if [[ ${srootlink#"${otherlink[*]} "} != ${srootlink} ]]; then # cir. dep
[7dc8595]437 echo -en "\nCirc: $((depth+1))${spaceSTR:0:$((depth+1))}${YELLOW}${id_of_dep}${OFF} $dpriostring"
[2140f22]438# Find lowest priority in branch from parent to depFile:
[7dc8595]439 p2=0
440 for (( i=${#otherlink[*]}; i < $depth ; i++ )) ; do
441 if (( ${priolink[i]} > $p2 )); then p2=${priolink[i]}; fi
442 done
443 if (( $prio_of_dep >= $p2 )); then # prune
[e4b1293]444 lines_to_remove="$lines_to_remove $id_of_dep"
[2140f22]445 sed -i "/$id_of_dep/d" ${depFile/.tree/.dep}
446 else # find and set parent, then return lowest priority
447# The parent has the same link without the last entry.
448# We do not need otherlink anymore so just destroy the last element
449 unset otherlink[-1]
450 parentNode=$(grep ^"${otherlink[*]}"\$ -l *)
451 return $p2
[e4b1293]452 fi
[2140f22]453 else # not circular: prune tree (but not .dep, since it may happen that
[7ac11f0]454 # the tree is destroyed and rebuilt in another order)
[e576789]455 lines_to_remove="$lines_to_remove $id_of_dep"
[e4b1293]456 fi # circular or not
457 continue # this dependency has already been seen, and the associated
458 # subtree computed. We are done
459 fi # Has this entry already been seen?
[2140f22]460# So, this entry has not already been seen. Let's build the corresponding
461# subtree. First check there is a subtree...
462# Use -s, because it may happen that after removing lines, .dep exists
[d7c07e0]463# but is empty.
[2140f22]464 if [[ -s ${id_of_dep}.dep ]]; then # this dependency has dependencies
465 sed "1i${rootlink[*]} $count\\
466${priolink[*]} $prio_of_dep" < ${id_of_dep}.dep \
467 > ${id_of_dep}.tree # add link and priolink
468 generate_dependency_tree ${id_of_dep}.tree $prio_of_dep
[e576789]469# Test return value, in case we exchange dependencies
[2140f22]470 p2=$?
471 case $p2 in
472 0) # Normal return
473 ;;
474 $prio_of_dep) # we remove this dep, but since it may become unreachable,
475 # move it to be built later (as a dep of parent).
476 tree_erase ${id_of_dep}.tree
477 lines_to_remove="$lines_to_remove $id_of_dep"
478 sed -i "/${id_of_dep}/d" ${depFile/.tree/.dep}
479 echo "$prio_of_dep b $id_of_dep" >> $parentNode
480# must be added to .dep in case parentNode is destroyed when erasing
481# the tree
482 echo "$prio_of_dep b $id_of_dep" >> ${parentNode/.tree/.dep}
483 continue
484 ;;
485 *) # We are backing up
486 return $p2
487 ;;
488 esac
489 else # id_of_dep has no dependencies, just record the link in a file
490 # and print
491 echo "${rootlink[*]} $count" > ${id_of_dep}.tree
492 echo -en "\nLeaf: $(($depth+1))${spaceSTR:0:$(($depth+1))}${CYAN}${id_of_dep}${OFF} $dpriostring"
493 fi
[e576789]494done
[2140f22]495echo -en "\n End: $depth${spaceSTR:0:$depth}${GREEN}${depFile%.tree}${OFF}"
496} <$depFile
[e576789]497# It may happen that a file is created with several times
498# the same line. Normally, all those lines but one
499# would be flagged to be removed (or all of them if
[e4b1293]500# the dependency appeared before). A simple sed /$line/d
[e576789]501# destroys all the lines. We should instead remove
502# only one for each appearance of it in lines_to_remove.
[e4b1293]503# so first get the position of last line and then delete
[e576789]504# that line
505for line in $lines_to_remove
[2140f22]506 do lineno=$(sed -n /^[[:digit:]]\ b\ $line\$/= $depFile | tail -n1)
507 sed -i ${lineno}d $depFile
[e576789]508done
509return 0
510}
[3c10176]511
[2140f22]512
[e576789]513#---------------#
514tree_browse() { #
515#---------------#
516local file=$1
517local f
518
519#echo file=$file
[7dc8595]520for f in $(grep '[^0-9 ]' $file | sed 's/.* //'); do
[e576789]521# echo f=$f
[2140f22]522 if grep -q '[^0-9 ]' ${f}.tree ; then
523 tree_browse ${f}.tree
[3c10176]524 fi
[e576789]525 echo $f
526done
527}
[3c10176]528
[e576789]529#--------------#
530tree_erase() { #
531#--------------#
532local file=$1
533local f
[6c8095a]534local rootlink
[f37d08b]535local rootlink2
[e576789]536
537#echo file=$file
[6c8095a]538rootlink="$(head -n1 $file) "
[7dc8595]539for f in $(grep '[^0-9 ]' $file | sed 's/.* //'); do
[2140f22]540 if [ -f ${f}.tree ]; then
541 rootlink2="$(head -n1 ${f}.tree) "
[6c8095a]542# We want two things:
543# i) do not erase the file if it is in another branch
544# ii) do not erase the file if there is a circular dependency
545# for case i), we test that rootlink is contained in rootlink2
546# for case ii), we test that rootlink2 is not contained in
547# rootlink.
[f37d08b]548# See comment above about srootlink
[6c8095a]549 if [[ ${rootlink2#${rootlink}} != ${rootlink2} &&
550 ${rootlink#${rootlink2}} == ${rootlink} ]] ; then
[2140f22]551 tree_erase ${f}.tree
[e576789]552 fi
553 fi
554done
555rm -f $file
[3c10176]556}
Note: See TracBrowser for help on using the repository browser.