确定文件相对于目录的路径，包括符号链接

Question

我有一个目录，上面有数千个后代（至少1000个，可能不超过20000个）。给定一个文件路径（保证存在），我想知道该文件可以在该目录中的何处找到——包括通过符号链接。在

例如，给定：

• 目录路径是/base。在
• 真正的文件路径是/elsewhere/myfile。在
• /base是/realbase的符号链接
• /realbase/foo是/elsewhere的符号链接。在
• /realbase/bar/baz是/elsewhere/myfile的符号链接。在

我想找到路径/base/foo/myfile和/base/bar/baz。在

我可以通过递归检查/base中的每个符号链接来完成这项工作，但这将非常缓慢。我希望有一个更优雅的解决方案。在

---

动机

这是一个崇高的文本插件。当用户保存一个文件时，我们要检测它是否在Sublime配置目录中。特别是，即使文件是从config目录中符号链接的，并且用户在其物理路径（例如在他们的Dropbox目录中）编辑文件，我们也希望这样做。可能还有其他应用程序。在

Sublime可以在Linux、Windows和Mac操作系统上运行，所以理想的解决方案应该是这样。在

Answer 1

这和很多事情一样，比表面看起来更复杂。在

文件系统中的每个实体都指向一个inode，它描述文件的内容。实体就是你看到的东西-文件、目录、套接字、块设备、字符设备等等。。。在

单个“文件”的内容可以通过一个或多个路径访问-这些路径中的每一个都称为“硬链接”。硬链接只能指向同一文件系统上的文件，它们不能跨越文件系统的边界。在

一个路径也可以寻址一个“符号链接”，它可以指向另一个路径-该路径不必存在，可以是另一个符号链接，也可以在另一个文件系统上，或者可以指向产生无限循环的原始路径。在

如果不扫描整个树，就不可能定位指向特定实体的所有链接（符号链接或硬链接）。在

---

在我们进入这之前。。。一些评论：

1. 请看最后的一些基准。我不相信这是一个重要的问题，尽管无可否认，这个文件系统在一个6磁盘的ZFS阵列上，在i7上，所以使用较低规格的系统需要更长的时间。。。在
2. 考虑到在某个时刻，如果不在每个文件上调用stat()，这是不可能的，那么您将很难找到一个不太复杂的更好的解决方案（例如维护一个索引数据库，以及由此带来的所有问题）

---

如前所述，我们必须对整个树进行扫描（索引）。我知道这不是你想做的，但不这样做是不可能的。。。在

为此，您需要收集索引节点，而不是文件名，并在事后检查它们。。。这里可能有一些优化，但我尽量保持简单，以优先考虑理解。在

以下功能将为我们生成此结构：

def get_map(scan_root):
    # this dict will have device IDs at the first level (major / minor) ...
    # ... and inodes IDs at the second level
    # each inode will have the following keys:
    #   - 'type'     the entity's type - i.e: dir, file, socket, etc...
    #   - 'links'    a list of all found hard links to the inode
    #   - 'symlinks' a list of all found symlinks to the inode
    # e.g: entities[2049][4756]['links'][0]     path to a hard link for inode 4756
    #      entities[2049][4756]['symlinks'][0]  path to a symlink that points at an entity with inode 4756
    entity_map = {}

    for root, dirs, files in os.walk(scan_root):
        root = '.' + root[len(scan_root):]
        for path in [ os.path.join(root, _) for _ in files ]:
            try:
                p_stat = os.stat(path)
            except OSError as e:
                if e.errno == 2:
                    print('Broken symlink [%s]... skipping' % ( path ))
                    continue
                if e.errno == 40:
                    print('Too many levels of symbolic links [%s]... skipping' % ( path ))
                    continue
                raise

            p_dev = p_stat.st_dev
            p_ino = p_stat.st_ino

            if p_dev not in entity_map:
                entity_map[p_dev] = {}
            e_dev = entity_map[p_dev]

            if p_ino not in e_dev:
                e_dev[p_ino] = {
                    'type': get_type(p_stat.st_mode),
                    'links': [],
                    'symlinks': [],
                }
            e_ino = e_dev[p_ino]

            if os.lstat(path).st_ino == p_ino:
                e_ino['links'].append(path)
            else:
                e_ino['symlinks'].append(path)

    return entity_map

我制作了一个示例树，如下所示：

^{pr2}$

此函数的输出为：

$ places
Broken symlink [./6]... skipping
Too many levels of symbolic links [./5]... skipping
Too many levels of symbolic links [./4]... skipping
{201: {67679: {'links': ['./a/1', './c/3'],
               'symlinks': ['./b/2'],
               'type': 'file'},
       67688: {'links': ['./d/4'], 'symlinks': [], 'type': 'file'}}}

如果我们对./c/3感兴趣，那么您可以看到仅仅查看符号链接（忽略硬链接）就会导致我们错过./a/1。。。在

通过随后搜索我们感兴趣的路径，我们可以在此树中找到所有其他引用：

def filter_map(entity_map, filename):
    for dev, inodes in entity_map.items():
        for inode, info in inodes.items():
            if filename in info['links'] or filename in info['symlinks']:
                return info

$ places ./a/1
Broken symlink [./6]... skipping
Too many levels of symbolic links [./5]... skipping
Too many levels of symbolic links [./4]... skipping
{'links': ['./a/1', './c/3'], 'symlinks': ['./b/2'], 'type': 'file'}

---

此演示的完整源代码如下。请注意，我使用了相对路径来保持简单，但最好将其更新为使用绝对路径。另外，任何指向树外部的符号链接当前都没有相应的link。。。这是给读者的练习。在

也可以在填充树时收集数据（如果这是与您的过程一起工作的话）。。。您可以使用^{}很好地处理这个问题—甚至还有一个python module。在

#!/usr/bin/env python3

import os, sys, stat
from pprint import pprint

def get_type(mode):
    if stat.S_ISDIR(mode):
        return 'directory'
    if stat.S_ISCHR(mode):
        return 'character'
    if stat.S_ISBLK(mode):
        return 'block'
    if stat.S_ISREG(mode):
        return 'file'
    if stat.S_ISFIFO(mode):
        return 'fifo'
    if stat.S_ISLNK(mode):
        return 'symlink'
    if stat.S_ISSOCK(mode):
        return 'socket'
    return 'unknown'

def get_map(scan_root):
    # this dict will have device IDs at the first level (major / minor) ...
    # ... and inodes IDs at the second level
    # each inode will have the following keys:
    #   - 'type'     the entity's type - i.e: dir, file, socket, etc...
    #   - 'links'    a list of all found hard links to the inode
    #   - 'symlinks' a list of all found symlinks to the inode
    # e.g: entities[2049][4756]['links'][0]     path to a hard link for inode 4756
    #      entities[2049][4756]['symlinks'][0]  path to a symlink that points at an entity with inode 4756
    entity_map = {}

    for root, dirs, files in os.walk(scan_root):
        root = '.' + root[len(scan_root):]
        for path in [ os.path.join(root, _) for _ in files ]:
            try:
                p_stat = os.stat(path)
            except OSError as e:
                if e.errno == 2:
                    print('Broken symlink [%s]... skipping' % ( path ))
                    continue
                if e.errno == 40:
                    print('Too many levels of symbolic links [%s]... skipping' % ( path ))
                    continue
                raise

            p_dev = p_stat.st_dev
            p_ino = p_stat.st_ino

            if p_dev not in entity_map:
                entity_map[p_dev] = {}
            e_dev = entity_map[p_dev]

            if p_ino not in e_dev:
                e_dev[p_ino] = {
                    'type': get_type(p_stat.st_mode),
                    'links': [],
                    'symlinks': [],
                }
            e_ino = e_dev[p_ino]

            if os.lstat(path).st_ino == p_ino:
                e_ino['links'].append(path)
            else:
                e_ino['symlinks'].append(path)

    return entity_map

def filter_map(entity_map, filename):
    for dev, inodes in entity_map.items():
        for inode, info in inodes.items():
            if filename in info['links'] or filename in info['symlinks']:
                return info

entity_map = get_map(os.getcwd())

if len(sys.argv) == 2:
    entity_info = filter_map(entity_map, sys.argv[1])
    pprint(entity_info)
else:
    pprint(entity_map)

---

出于好奇，我在我的系统上运行了这个。它是i7-7700K上的一个6x磁盘的ZFS RAID-Z2池，有大量的数据可供使用。诚然，在低规格的系统上运行会慢一些。。。在

需要考虑的一些基准：

• 包含~850个目录中~3.1k文件和链接的数据集。 这将在不到3.5秒的时间内运行，后续运行约80毫秒
• 包含~2.2k目录中~30k个文件和链接的数据集。 这将在不到30秒的时间内运行，后续运行约300毫秒
• 包含~73.5k文件和~8k目录中链接的数据集。 这大约需要60秒，后续运行约800毫秒

用简单的数学计算，在一个空缓存中，每秒大约有1140个stat()个调用，或者一旦缓存被填满，每秒大约有~90k个stat()调用-我不认为{}像你想象的那么慢！在

Answer 2

符号链接不允许使用快捷方式。您必须了解所有可能指向感兴趣文件的相关FS条目。它对应于创建一个空目录，然后监听该目录下的所有文件创建事件，或者扫描当前位于该目录下的所有文件。运行以下命令。在

#! /usr/bin/env python

from pathlib import Path
import collections
import os
import pprint
import stat


class LinkFinder:

    def __init__(self):
        self.target_to_orig = collections.defaultdict(set)

    def scan(self, folder='/tmp'):
        for fspec, target in self._get_links(folder):
            self.target_to_orig[target].add(fspec)

    def _get_links(self, folder):
        for root, dirs, files in os.walk(Path(folder).resolve()):
            for file in files:
                fspec = os.path.join(root, file)
                if stat.S_ISLNK(os.lstat(fspec).st_mode):
                    target = os.path.abspath(os.readlink(fspec))
                    yield fspec, target


if __name__ == '__main__':
    lf = LinkFinder()
    for folder in '/base /realbase'.split():
        lf.scan(folder)
    pprint.pprint(lf.target_to_orig)

最后会得到一个从所有符号链接文件规范到一组别名的映射，通过这些别名可以访问该文件规范。在

符号链接目标可以是文件或目录，因此要在给定的filespec上正确使用映射，必须反复截断它，询问映射中是否出现父目录或祖先目录。在

悬挂的符号链接不是专门处理的，它们只是允许悬挂。在

您可以选择序列化映射，可能是按排序的顺序。如果您反复重新扫描一个大目录，就有机会在运行期间记住目录mod时间，并避免重新扫描该目录中的文件。不幸的是，您仍然需要递归到它的子目录中，以防任何的最近发生了更改。 您的子树可能显示出足够的结构，以避免递归超过K级，或者避免降到名称与某些正则表达式匹配的目录中。在

如果大多数FS更改是由少数程序（如包管理器或构建系统）生成的，那么让这些程序记录它们的操作可以获得性能上的胜利。也就是说，如果您在每个午夜进行一次完整扫描，然后在一千个目录中只运行make，那么您可以选择只重新扫描这对子树。在

Answer 3

我的第一反应是让操作系统或某些服务在文件系统树发生更改时通知您，而不是您查找更改。基本上不要重新发明轮子。在

也许：

• fswatch
• fschange
• inotify

特定于Windows：5 tools to monitor folder changes