bash - Create a 'tree' structure when recursively searching items - Stack Overflow

admin管理员组

文章数量:1390285

I work on Azure devops & in there there is a concept of templates (similar to functions in bash). So, one templates will use other template(s) to perform some actions.

The top most templates (which are not used by any other templates) are exttemplates & the file names have the text exttemplate in them.

I am trying to do build a 'tree' of sorts (like the tree command) indicating which templates are used in exttemplates and then which templates are used in those templates & so on.

I have the function below to recursively look for template references (other templates are always called with the line starting with text - template:)

The input to the function is the array of exttemplates (whcih we can get using the find command). Adding the dot and removing the "\n" is needed because of the way templates are called.

string_template() {
  array_of_files_to_search=("$@")

  for file_to_search in "${array_of_files_to_search[@]}"; do
    if [[ "$file_to_search" = '/'* ]]; then
      file_to_search=$(echo ".${file_to_search}" | tr -d '\n')
    fi
    if [[ $file_to_search = *"exttemplate"* ]]; then
      echo -e "\e[34mSearching in $file_to_search & its refereneced templates\e[0m"
    else
      echo -e "\e[33mSearching in $file_to_search & its refereneced templates\e[0m"
    fi
    
    readarray references < <(grep -E "^\s*\- template:.*" "$file_to_search" | sed 's/#.*//' | sed 's/- template://' | awk '{$1=$1;print}')
    
    if [ "${#references[@]}" -gt 0 ]; then
      string_template "${references[@]}"
    else
      echo "This $file_to_search does not use any other templates"
    fi
  done
}

The function is working fine and all the templates are found. However, what I am not able to accomplish is the generating the tree structure.

What I am getting now is like below. Since the exttemplates have unique name, I can identify them & print them in a different color. But this is not possible for the other templates. How to keep track of the 'levels' while recursing? In the pic (I have hand marked some lines to illustrate), the lines with red mark at the end should be level 2 & the ones with blue mark should be level 3 (assuming the exttemplates are at level 0). How to achieve keeping track of the 'levels'?

Update based on comments

question Can you have the same template used in several other templates at different tree levels? If yes what do you want to do? Repeat it in the tree with all its sub-templates? answer Yes. If this happens, Repeat it in the tree with all its sub-templates.

I work on Azure devops & in there there is a concept of templates (similar to functions in bash). So, one templates will use other template(s) to perform some actions.

The top most templates (which are not used by any other templates) are exttemplates & the file names have the text exttemplate in them.

I am trying to do build a 'tree' of sorts (like the tree command) indicating which templates are used in exttemplates and then which templates are used in those templates & so on.

I have the function below to recursively look for template references (other templates are always called with the line starting with text - template:)

The input to the function is the array of exttemplates (whcih we can get using the find command). Adding the dot and removing the "\n" is needed because of the way templates are called.

string_template() {
  array_of_files_to_search=("$@")

  for file_to_search in "${array_of_files_to_search[@]}"; do
    if [[ "$file_to_search" = '/'* ]]; then
      file_to_search=$(echo ".${file_to_search}" | tr -d '\n')
    fi
    if [[ $file_to_search = *"exttemplate"* ]]; then
      echo -e "\e[34mSearching in $file_to_search & its refereneced templates\e[0m"
    else
      echo -e "\e[33mSearching in $file_to_search & its refereneced templates\e[0m"
    fi
    
    readarray references < <(grep -E "^\s*\- template:.*" "$file_to_search" | sed 's/#.*//' | sed 's/- template://' | awk '{$1=$1;print}')
    
    if [ "${#references[@]}" -gt 0 ]; then
      string_template "${references[@]}"
    else
      echo "This $file_to_search does not use any other templates"
    fi
  done
}

The function is working fine and all the templates are found. However, what I am not able to accomplish is the generating the tree structure.

What I am getting now is like below. Since the exttemplates have unique name, I can identify them & print them in a different color. But this is not possible for the other templates. How to keep track of the 'levels' while recursing? In the pic (I have hand marked some lines to illustrate), the lines with red mark at the end should be level 2 & the ones with blue mark should be level 3 (assuming the exttemplates are at level 0). How to achieve keeping track of the 'levels'?

Update based on comments

question Can you have the same template used in several other templates at different tree levels? If yes what do you want to do? Repeat it in the tree with all its sub-templates? answer Yes. If this happens, Repeat it in the tree with all its sub-templates.

• bash
• recursion

Share Improve this question Follow edited Mar 13 at 7:41 moys asked Mar 13 at 2:13 moysmoys 8,07533 gold badges1717 silver badges5050 bronze badges 9

• pass a level argument to string_template ? – jhnc Commented Mar 13 at 3:32
• @jhnc If I pass it as an argument, I can increment the levels as we go deeper. However, I would not be able to reset it back to level 0 after one exttemplate has been completely drilled down – moys Commented Mar 13 at 4:13
• 2 why do you think that? mkdir -p a/{b1,b2}/c/{d1,d2}; f(){ for f in "$2"/*; do echo "$1: $f"; [[ -d $f ]] && f $(($1+1)) "$f"; done; }; f 0 a – jhnc Commented Mar 13 at 4:25
• 1 if path is directory, recurse with level incremented and a new root. it's just a demo to show you could pass a level argument to string_template the same way I do with f (you can extract with shift or use "$1" and "${@:2}") – jhnc Commented Mar 13 at 5:43
• 1 don't increment the parent; pass an incremented value to the child – jhnc Commented Mar 13 at 5:47

 |  Show 4 more comments

1 Answer 1

Sorted by: Reset to default 2

You can probably do all this with just GNU awk (for its multidimensional associative arrays). The following GNU awk program assumes that your file names do not contain newline characters and that the list of files you want to start from is stored in a text file, one filename per line. It exits with an error message if any of the encountered files cannot be opened. It prints a simple tree with a 2 spaces indentation. If the extra text and ANSI codes of your example are really needed you will have to adapt.

We parse the provided text file and store all filenames found as keys of array to_visit. Then, in the END block:

• Pick a filename file in to_visit using a one-iteration for loop over the array keys: for(file in to_visit) { ...; break }.
• Open file and parse it. For each line, if the line matches the template definition:
  • store the included template filename in variable template, removing the comments, the leading and trailing spaces, and prepending a . if it starts with /,
  • if template is not the empty string, add an entry in 2 dimensions array includes where the first key is file and the second is template,
  • if it is not a key of the visited array, add also template to the to_visit array keys, such that we will also parse it.
• Close file, add it as a key of array visited (to avoid re-adding it to to_visit if we encounter it again as an included template), delete it from the keys of array to_visit, exit the one-iteration for loop.
• Repeat as long as the to_visit array is not empty.

For the final printing we use the walk recursive function that takes 2 parameters: a prefix string and a filename file. It prints prefix and file, and for each template template included in file (found in array includes) it calls itself on template with an augmented prefix.

$ cat foo.awk
function walk(prefix, file,    template) {
  printf("%s%s\n", prefix, file)
  for(template in includes[file]) walk("  " prefix, template)
}

{ to_visit[$0] }

END {
  while(length(to_visit)) {
    for(file in to_visit) {
      while ((error = (getline < file)) > 0) {
        if($0 ~ /^\s*- template:/) {
          gsub(/^\s*- template:\s*|\s*#.*/, "")
          template = ($0 ~ /^[/]/ ? "." : "") $0
          if(length(template)) includes[file][template]
          if(!(template in visited)) to_visit[template]
        }
      }
      if(error < 0) { print file ": cannot open"; exit(1) }
      close(file)
      visited[file]
      delete to_visit[file]
      break
    }
  }
  for(file in visited) if(file ~ /exttemplate/) walk("", file)
}

$ awk -f foo.awk files_to_search.txt
foo.exttemplate
  b/bar.template
    b/2/bar
    b/1/bar
    a/3/bar
  a/foo.template
    b/3/foo
    c/2/foo
    a/1/foo

Note that if you have a loop in the inclusions graph the walk function will enter an infinite loop...

本文标签： bashCreate a 39tree39 structure when recursively searching itemsStack Overflow