如何用Perl哈希表示文件系统的符号链接？

Question

在Server Fault上，如何列出符号链接链？（不是我的问题）讨论了列出所有符号链接并跟随它们的方法。为了使这可行，让我们首先考虑一个单独的目录。

我想编写一个简短的实用程序来完成这个任务。将符号链接对放入哈希表中，然后处理哈希表似乎很容易。

但是我可能会遇到以下情况：

ls -l
total 0
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 08:48 a -> b
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 08:48 b -> c
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:03 c -> a
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:17 trap -> b
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:17 x -> y
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:17 y -> b

显然，a->b->c是一个循环，而陷阱点指向循环，但要知道x是否指向循环，我需要跟随一位。

其中一种哈希表示为：

a => b
b => c
c => a
trap => b
x => y
y => b

但是，一旦我知道循环的内容，反向表示法更适合标记到错误的起始点的循环。

所以这里有几个问题：

• 散列表是代表符号链接的最佳结构吗？
• 分离文件系统图以告诉循环组件与树组件和带循环类型部件的分支的最佳方法是什么？
• 是否有比手动搜索所有起始点的所有循环更好的算法？
• 从图论角度来看 - 这种事情在 CPAN 中已经有了吗？如果没有，有哪些好的辅助模块？

- Paul

---

鼓励提交样例代码来解决问题。 - Paul

展示一下你目前尝试过的内容也是鼓励的。 :) - brian d foy

@brian 哎呀！我把这个问题大多数看作是别人的好玩的难题，没有尝试去解决它，只是认识到了一些陷阱。 - Paul

Answer 1

在CPAN上有一个图形(Graph)模块，您可以按以下方式使用：

#! /usr/bin/perl

use warnings;
use strict;

use Graph;

my $g = Graph->new;
my $dir = @ARGV ? shift : ".";

opendir my $dh, $dir or die "$0: opendir $dir: $!";
while (defined(my $name = readdir $dh)) {
  my $path = $dir . "/" . $name;

  if (-l $path) {
    my $dest = readlink $path;
    die "$0: readlink $path: $!" unless defined $dest;

    $g->add_edge($name => $dest);
  }
  else {
    $g->add_vertex($name);
  }
}

my @cycle = $g->find_a_cycle;
if (@cycle) {
  $" = ' -> '; #" # highlighting error
  print "$0: $dir: at least one cycle: @cycle\n";
}
else {
  print "$0: $dir: no cycles\n";
}

例如，在一个类似于你问题中的目录结构中，输出结果如下：

$ ../has-cycle 
../has-cycle: .: 至少存在一个循环: c -> a -> b

- Greg Bacon

---

谢谢您发布这篇文章。我打算研究一下图形相关的其他需求，并且复习这方面的知识。 - Paul

Answer 2

请看CPAN模块File::Spec::Link。该模块的resolve方法可以遍历链接以找到链接目标。

模块的resolve方法如下所述:

resolve($link)：通过重复调用linked返回最终链接到的非链接 $link。如果无法解析该链接，则返回undef。

我使用了这个模块来查找符号链接的目标，而目标本身又是一个符号链接，依此类推。但是，我不确定它是否能检测到循环符号链接。

- sateesh

Answer 3

你需要存储的不仅仅是链接的名称。如果你的文件系统支持，可以获取inode号码或其他唯一的特征。如果不存在这样的特征，那么考虑创建自己的特征，例如通过对名称/创建日期/最后修改日期进行校验和。无论哪种方式，你都需要一些方法来唯一标识每个链接。我见过一些工具只是将链接数量限制在8到255之间，并将超出此限制的任何内容声明为循环，但我总是认为那是“走捷径”。 :)

- TMN