source: BLFS/libs/func_dependencies@ 0f4df7c

ablfs-more trunk
Last change on this file since 0f4df7c was 5156f51, checked in by Pierre Labastie <pierre.labastie@…>, 2 years ago

BLFS: remove only "a" lines for runtime deps

Presently, when the <node>groupxx file is created, we copy "a"
lines from <node> to <node>groupxx (changing "a" to "b") and
we remove all the lines containing the runtime dependency from
<node>. This may not always be what we want: for example, a
dependency can be both "required at runtime" and "optional for
tests". We should keep this information when cleaning the nodes.
Only when removing circular paths should the optional tie be broken
if necessary.

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