bashrecursion

Create a 'tree' structure when recursively searching items

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'?

enter image description here

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.

Solution

  • 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:

    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...