如何在 bash 中解析文件，awk...以更有效的方式链接程序和子程序

在 TXR Lisp 中：

$ cat file1
A
B
C
E
L
$ cat file2
A|B C D E
B|F G
C|J K L
E|
K|Z
L|M N
Z|Y X
$ txr deps.tl file1 file2
A
;B
;;F
;;G
;C
;;J
;;K
;;;Z
;;;;Y
;;;;X
;;L
;;;M
;;;N
;D
;E
B
;F
;G
C
;J
;K
;;Z
;;;Y
;;;X
;L
;;M
;;N
E
L
;M
;N

代码如下所示：

(defstruct mod ()
  name
  children)

(defvarl mh (hash))

(defun resolve-names (m)
  (when (and m.children
             (stringp (first m.children)))
    (set m.children
         (append-each ((c m.children))
           (iflet ((cm [mh c]))
             (list cm))))))

(defun print-tree (m : path (prefix ""))
  (put-line `@prefix@{m.name}`)
  (unless (member m path)
    (let ((nprefix `;@prefix`)
          (npath (cons m path)))
      (each ((c m.children))
        (print-tree c npath nprefix)))))

(tree-bind (file1 file2) *args*
  (let ((used (file-get-lines "file1"))
        (deps (file-get-lines "file2")))
    ;; populate object hash with each definition
    (each ((d deps))
      (match `@left|@right` d
        ;; look up or create new node for left side
        (let ((m (or [mh left]
                     (set [mh left] (new mod name left))))
              (ch (tok #/\S+/ right)))
          ;; ensure node exists for each child
          (each ((c ch))
            (or [mh c] (set [mh c] (new mod name c))))
          ;; append children to left hand node
          (set m.children (append m.children ch)))))
    ;; convert child names to objects
    (dohash (n m mh)
      (resolve-names m))
    ;; print tree view for each used object
    (each ((u used))
      (iflet ((m [mh u]))
        (print-tree m)))))

对循环引用进行检查，但对重复项（菱形引用）不进行检查。print-tree

假设：

• 我们只为根程序生成树（根程序==其他程序未调用的程序）
• OP 有多个根程序
• OP 提到了两个文件 - 和 - 但在实际代码中使用了其他名称File1File2
• 我猜File2 == program_list
• 我们没有看到内容，所以我继续，好像不存在;OP 可能需要根据File1File1File1

我们将复制 OP 的示例数据以包含 2 个根程序（和）：AA1

$ cat program_list
A|B C D E
B|F G
C|J K L
E|
K|Z
L|M N
Z|Y X
A1|B1 C1 D1 E1
B1|F1 G1
C1|J1 K1 L1
E1|
K1|Z1
L1|M1 N1
Z1|Y1 X1

虽然其他语言将具有更好的性能，但这里有一种方法应该比 OP 的当前代码具有更好的性能（如果仅仅是因为它不调用任何子 shell）：bash

$ cat build_tree.bash
#!/bin/bash

unset   pc c p r                                 # just in case script is sourced
declare -A c p r                                 # associative arrays for p(arent), c(hild) and r(oot) nodes

#######
# parse data into p[], c[] and parent_child ( pc_<parent>[] ) arrays

while read -r line
do
    IFS='[ |]' read -ra a <<< "${line}"          # a[0]==parent, a[1-n]==children

    parent="${a[0]}"

    p[$parent]=1
    declare -n pc=pc_"${parent}"                 # nameref to create pc_<parent>=( children ) arrays, eg: pc_A=( B C D E )
    pc=()

    for ((i=1 ; i<${#a[@]} ; i++))               # loop through child nodes
    do
        child="${a[$i]}"
        c[$child]=1                              # add as index in c[] array; c[] used in next loop to determine which nodes are roots
        pc+=( "$child" )                         # add child to pc == pc_<parent>[] array
    done
done < program_list                              # process File2

#######
# determine root nodes

for node in "${!p[@]}"                           # loop through p[] array indices
do
    [[ -z "${c[$node]}" ]] && r[$node]=1         # if not an index in the c[] array then add as index in the r[] array
done

unset child                                      # no longer needed so go ahead and release memory

#######
# recursive function
#
# for a given parent:
# - loop through array of children
# - print a child and if the child has children then make recursive call

recurse() {
    local parent pfx pc child

    parent="$1"                                  # eg: A, B, D1
    pfx="$2"                                     # eg: ';', ';;', ';;;'

    declare -n pc=pc_"${parent}"                 # nameref for pc_<parent>[] array

    for child in "${pc[@]}"                      # loop through child nodes
    do
        echo "${pfx}${child}"                    # print child node

        # if child is also a parent then make recursive call

        [[ -n "${p[$child]}" ]] && recurse "${child}" "${pfx}${sep}"
    done
}

#######
# main step: loop through root nodes and make top-level recurse() calls

sep=';'

for root in "${!r[@]}"
do
    echo "########### new tree:"
    echo "${root}"
    recurse "${root}" "${sep}"
done

#######
# release memory ... just in case script is sourced

for parent in "${!p[@]}"
do
    declare -n pc=pc_"${parent}"                 # nameref for pc_<parent>[] array
    unset pc
done

unset c p r

笔记：

• 需要 NameRef （） 支持bash 4.2+declare -n

试驾：

$ ./build_tree.bash
########### new tree:
A
;B
;;F
;;G
;C
;;J
;;K
;;;Z
;;;;Y
;;;;X
;;L
;;;M
;;;N
;D
;E
########### new tree:
A1
;B1
;;F1
;;G1
;C1
;;J1
;;K1
;;;Z1
;;;;Y1
;;;;X1
;;L1
;;;M1
;;;N1
;D1
;E1

我会利用 GNU 来完成这个任务，让内容成为AWKfile.txt

A|B C D E
B|F G
C|J K L
E|
K|Z
L|M N
Z|Y X

然后

awk 'function getpath(name){return (name in arr)?sprintf("%-10s%-10s",getpath(arr[name]),name):sprintf("%-10s",name)}function printasrecord(path){patsplit(path,parts,/.{10}/);depth=length(parts);$0="";$depth=parts[depth];print}BEGIN{FS="[| ]";PROCINFO["sorted_in"]="@ind_str_asc";OFS=";"}/[|]./{for(i=2;i<=NF;i+=1){arr[$i]=$1}}END{for(i in arr){paths[getpath(i)]};for(j in paths){printasrecord(j)}}' file.txt

给出输出

;B         
;;F         
;;G         
;C         
;;J         
;;K         
;;;Z         
;;;;X         
;;;;Y         
;;L         
;;;M         
;;;N         
;D         
;E

解释：我处理并创建数组，其中 key 是子数组，value 是它的父数组。然后我使用最近的递归函数将所有路径作为其他数组的键，这些数组以固定宽度格式呈现，我选择了值 10，但是如果您有比这更长的值，请相应地调整它。这允许使用字母顺序排序来获得所需的输出。我通过设置 to 来通知 GNU，需要这样的排序（有关可能的值，请参阅控制扫描）。我以这种方式遍历路径数组，对于每个键（路径），我使用 patsplit 将其解析为多个部分，然后我将当前行 （） 设置为空字符串并将 th 字段设置为路径第 th 部分的值，这是最后一部分。请注意，输出与所呈现的期望输出略有不同，因为没有（没有父级），并且相同深度的顺序由字母排序决定，因此在 之前。file.txtarrgetpathAWKPROCINFO["sorted_in"]@ind_str_asc$0depthdepthAXY

免责声明：我的解决方案假设您正在使用有向、无环、连接的图，其中每个元素最多有 1 个直接祖先

（在 GNU Awk 5.1.0 中测试）