我有一个包含数千个后代的目录(至少 1,000,可能不超过 20,000)。给定一个文件路径(保证存在),我想知道在该目录中可以找到该文件的位置——包括通过符号链接(symbolic link)。
例如,给定:
/base
. /elsewhere/myfile
. /base
是指向 /realbase
的符号链接(symbolic link)/realbase/foo
是指向 /elsewhere
的符号链接(symbolic link). /realbase/bar/baz
是指向 /elsewhere/myfile
的符号链接(symbolic link). 我想找到路径
/base/foo/myfile
和 /base/bar/baz
.我可以通过递归检查
/base
中的每个符号链接(symbolic link)来做到这一点。 ,但这会很慢。我希望有一个更优雅的解决方案。动机
这是一个 Sublime Text 插件。当用户保存文件时,我们要检测它是否在 Sublime 配置目录中。特别是,即使文件是从 config 目录内部进行符号链接(symbolic link)的,并且用户正在其物理路径(例如,在他们的 Dropbox 目录中)编辑文件,我们也希望这样做。可能还有其他应用程序。
Sublime 可在 Linux、Windows 和 Mac OS 上运行,理想情况下该解决方案也应如此。
最佳答案
像许多事情一样,这比表面上看起来要复杂得多。
文件系统中的每个实体都指向一个 inode
,它描述了文件的内容。实体是你看到的东西——文件、目录、套接字、 block 设备、字符设备等......
可以通过一个或多个路径访问单个"file"的内容——这些路径中的每一个都称为“硬链接(hard link)”。硬链接(hard link)只能指向同一文件系统上的文件,不能跨越文件系统的边界。
路径也可以指向“符号链接(symbolic link)”,它可以指向另一个路径——该路径不一定存在,它可以是另一个符号链接(symbolic link),它可以在另一个文件系统上,或者它可以指向回在产生无限循环的原始路径上。
如果不扫描整个树,就不可能定位指向特定实体的所有链接(符号链接(symbolic link)或硬链接(hard link))。
在我们进入这个之前......一些评论:
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
,那么您可以看到仅查看符号链接(symbolic link)(并忽略硬链接(hard link))会导致我们错过 ./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'}
该演示的完整源代码如下。请注意,我使用了相对路径来保持简单,但将其更新为使用绝对路径是明智的。此外,指向树外的任何符号链接(symbolic link)当前都没有相应的
link
……这是给读者的练习。在填充树时收集数据也可能是一个想法(如果这对您的过程有用)...您可以使用
inotify
很好地处理这个问题 - 甚至还有一个 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 池,可以使用大量数据。诚然,这在低规范系统上运行速度会稍慢……
一些需要考虑的基准:
这在不到 3.5 秒内运行,后续运行约 80 毫秒
这在不到 30 秒内运行,后续运行约 300 毫秒
这在大约 60 秒内运行,后续运行约 800 毫秒
使用简单的数学计算,大约是 1140
stat()
每秒调用一次,缓存为空,或 ~90k stat()
一旦缓存被填满,每秒调用一次 - 我不认为 stat()
和你想象的一样慢!
关于python - 确定文件相对于目录的路径,包括符号链接(symbolic link),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54835749/