时间戳

首页 > 解决方案 > 确定文件相对于目录的路径，包括符号链接

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

问题描述

我有一个包含数千个后代的目录（至少 1,000 个，可能不超过 20,000 个）。给定一个文件路径（保证存在），我想知道该文件在该目录中的位置——包括通过符号链接。

例如，给定：

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

我可以通过递归检查 中的每个符号链接来做到这一点/base，但这会非常慢。我希望有一个更优雅的解决方案。

动机

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

Sublime 可以在 Linux、Windows 和 Mac OS 上运行，理想情况下应该是这个解决方案。

标签： pythonpython-3.xfilesymlinkpython-3.3

解决方案

就像许多事情一样，这比表面上看起来要复杂得多。

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

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

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

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

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

  1. 有关一些基准，请参见末尾。我不相信这是一个重大问题，尽管这个文件系统在 i7 上的 6 磁盘 ZFS 阵列上，所以使用较低规格的系统需要更长的时间......
  2. 鉴于在某些时候不调用每个文件是不可能stat()的，您将很难想出一个不会更复杂的更好的解决方案（例如维护索引数据库，以及引入的所有问题）

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

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

以下函数将为我们生成此结构：

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

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

$ tree --inodes
.
├── [  67687]  4 -> 5
├── [  67676]  5 -> 4
├── [  67675]  6 -> dead
├── [  67676]  a
│   └── [  67679]  1
├── [  67677]  b
│   └── [  67679]  2 -> ../a/1
├── [  67678]  c
│   └── [  67679]  3
└── [  67687]  d
    └── [  67688]  4

4 directories, 7 files

这个函数的输出是：

$ 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的 ... 这是读者的练习。

在填充树时收集数据也可能是一个想法（如果这适用于您的流程）......您可以inotify很好地处理这个问题 - 甚至还有一个python 模块。

#!/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 毫秒

使用简单的数学计算，在stat()缓存为空的情况下每秒大约有 1140 次调用，或者stat()在缓存被填满后每秒调用约 90k 次——我认为这并不stat()像你想象的那么慢！

推荐阅读