📂

std::directory_iterator に注意せよ

2022/12/29に公開

C++

tech

しっかりはまってとっても苦労したのでメモ。

実装・検証用のコードは Enchan1207/DirIterImpl に置いてあります。

ディレクトリを走査してくれる関数

std::directory_iterator は C++17より追加されたライブラリ filesystem により提供される関数であり、指定されたパス(std::filesystem::path)内にあるファイルを走査するイテレータを構築してくれるというものです:

#include <filesystem>
#include <iostream>

namespace fs = std::filesystem;

int main(int argc, char const* argv[]) {
    const fs::path targetPath("/usr");
    const auto dirIter = fs::directory_iterator(targetPath);
    for (const fs::path& path : dirIter) {
        std::cout << path.filename().string() << std::endl;
    }
    return 0;
}

実行結果例:

$ ./src/main
bin
libexec
sbin
local
lib
share

directory_iterator - cpprefjp C++日本語リファレンスによれば

ファイルの走査順序は未規定であり、ファイル名の辞書順に走査される保証はない。

とあり、実際 ls -la を実行した時とは異なる順番で出力されます:

$ ls -la /usr
total 0
drwxr-xr-x@   11 root  wheel    352 10 13 15:06 .
drwxr-xr-x    20 root  wheel    640 10 13 15:06 ..
drwxr-xr-x  1012 root  wheel  32384 10 13 15:06 bin
drwxr-xr-x    31 root  wheel    992 10 13 15:06 lib
drwxr-xr-x   311 root  wheel   9952 10 13 15:06 libexec
drwxr-xr-x    16 root  wheel    512 11  4 23:36 local
drwxr-xr-x   233 root  wheel   7456 10 13 15:06 sbin
drwxr-xr-x    45 root  wheel   1440 10 13 15:06 share

OS別の挙動比較

さまざまな環境を用意し、この関数の挙動を比較してみましょう。

std::filesystem::temp_directory_path() により取得したパスに net.enchan-lab.IterdirTest という名称のディレクトリを作成し、以下に示す各条件で関数を実行します。
なお、関数実行前に親ディレクトリごと削除・再作成を行うものとします。

条件:

名称を "a", "b", "c", "aa", "ab", "ac" とした 6つのファイルを作成
名称を "5", "4", "3", "2", "1" とした 5つのファイルを作成

ビルド環境:

macOS 11 (Big Sur), clang
Ubuntu 20.04, gcc
Windows Server 2022, Visual Studio 17 2022

~~WindowsでのMSVCを用いたビルド方法がわからなかった~~ 条件を揃える ため、全ての環境でcmakeを用いてビルドを行なっています。

以上6パターンで動作確認を行います。

1. macOS

Contents of /private/var/folders/24/8k48jl6d249_n_qfxwsl6xvm0000gn/T/net.enchan-lab.IterdirTest
ac
ab
a
aa
c
b

Contents of /private/var/folders/24/8k48jl6d249_n_qfxwsl6xvm0000gn/T/net.enchan-lab.IterdirTest
1
4
3
2
5

作成順でもなく、辞書順でもない順番で出力されています。

2. Ubuntu

Contents of /tmp/net.enchan-lab.IterdirTest
ac
aa
a
b
ab
c

Contents of /tmp/net.enchan-lab.IterdirTest
3
1
5
2
4

こちらも何か決まった順番があるわけではない様子。macOSともまた異なった順番です。

3. Windows

Contents of C:\Users\runneradmin\AppData\Local\Temp\net.enchan-lab.IterdirTest
a
aa
ab
ac
b
c

Contents of C:\Users\runneradmin\AppData\Local\Temp\net.enchan-lab.IterdirTest
1
2
3
4
5

辞書順です。 作成順でもなく、macOSやUbuntuのような謎の順番でもなく 清々しいほどに綺麗な辞書順です。

結果

Windowsだけが~~謎の融通を効かせて~~辞書順に出力してくれました。
ちょっとググれば日本語の情報も出てくるので勘違いする可能性はかなり低いと思いますが、Visual Studioなどで開発しているデベロッパが「あっ、この子は辞書順で返してくれるんだな」と思い込んだまま他のプラットフォームに流用するとエラいことになります。要注意。

対処

std::set にねじ込めば、プラットフォームによらず辞書順になってくれます。

// 対象のパスが targetPath で渡っているものとします

std::set<fs::path> contentsOfDirectory;
for (const auto& path : fs::directory_iterator(targetPath)) {
    contentsOfDirectory.insert(path);
}

for (const auto& path : contentsOfDirectory) {
    std::cout << path.filename().string() << std::endl;
}

これは、std::set の 要素はコンテナの構築時に設定された狭義の弱順序基準に従って小さいものから大きいものへとソートされる ため ^[1] であり、std::filesystem::path の operator< が内部で std::filesystem::path::compare を読んでいるから^[2] ~~のはず~~です。

応急処置的な対応としてはこれでも十分なのかな、と個人的には思います(メモリがかなり制限されている環境下で何百ものファイルをイテレーションしてなんらかの処理を行いたい等のケースでは問題になるかもしれませんが…)。

実装を読みに行く

環境によって出力される順番が異なること、setに突っ込めば辞書順になってくれることは分かりましたが、そうなると 出力順はどんな要素に影響されているのか が気になってきました。
名前順でも作成日時順でもなければパーミッション順でもない、となると一体何を基準にしているのでしょうか。

というわけで各OSの filesystem の実装を覗いていきます。ここからは完全に興味です。

Windows

とってもうれしいことに

Microsoft Visual Studio の C++ 標準ライブラリ (MSVC STL) は、2019 年 9 月にオープンソース化され、GitHub 上で更新の様子を追跡できるようになりました。

とのことなので、早速覗いていきます。(引用元: MSVC STL の最近の改良 - Zenn)

長いので省略

クラス directory_iterator の定義は stl/inc/filesystem にありました。

イテレータを進める operator++ では関数 _Advance_and_reset_if_no_more_files を呼んでいます。

定義は少し上にあります。関数 __std_fs_directory_iterator_advance を呼んでいるようです。

定義は stl/src/filesystem.cpp にあります:

最終的には fileapi.h の関数 FindNextFileW が呼ばれていました。
ここまで降りてくると、今度はSTLではなく microsoftのドキュメントにフォーカスが移ります。

このような記述がありました。

The order in which this function returns the file names is dependent on the file system type. With the NTFS file system and CDFS file systems, the names are usually returned in alphabetical order. With FAT file systems, the names are usually returned in the order the files were written to the disk, which may or may not be in alphabetical order. However, as stated previously, these behaviors are not guaranteed.

この関数がファイル名を返す順序は、ファイルシステムの種類に依存します。NTFSおよびCDFSにおいては、名前はアルファベット順で返されます。FATFSの場合、名前はファイルがディスクに書き込まれた順に返され、アルファベット順かどうかはわかりません。
ただし、前述のとおり、これらの動作は保証されていません。 (意訳)

つまり FS依存だが、保証されているわけではない ということになります。

macOS

clang (LLVM)なので、対象となるコードは llvm/llvm-projectであるはずです:
https://github.com/llvm/llvm-project

長いので省略

directory_iterator の定義は libcxx/include/__filesystem/directory_iterator.h にあり…

イテレータを進める operator++ 内部では関数 __increment を読んでいます。

関数の定義は libcxx/src/filesystem/directory_iterator.cpp にあり、そのメイン部分は関数advance　です。

関数の定義は少し上にあります。 posix_readdir　を呼び出し、諸々の処理を加えた上で返しているようです。

関数 posix_readdir 内部では、dirent.h の関数 readdirを呼んでいました。

dirent.h の関数 readdir がmacOS(というかclang)における directory_iteratorの核心部であるようです。
こちらも、ここまで降りてくるとmanページに話が移ります。

$ man readdir

The readdir() function returns a pointer to the next directory entry. The directory entry remains valid until the next call to readdir() or closedir() on the same directory stream. The function returns NULL upon reaching the end of the directory or on error. In the event of an error, errno may be set to any of the values documented for the getdirentries(2) system call. Note that the order of the directory entries vended by readdir() is not specified. Some filesystems may return entries in lexicographic sort order and others may not. Also note that not all filesystems will provide a value for d_type and may instead set the field to DT_UNKNOWN.

readdir()関数は、次のディレクトリエントリへのポインタを返します。ディレクトリエントリは、次に同じディレクトリストリームで readdir() または closedir() を呼び出すまで有効です。この関数は、ディレクトリの末尾に到達した場合、またはエラーが発生した場合、NULL を返し、エラーの場合は errno に getdirentries(2) システムコールで定義された値のいずれかが設定されます。 readdir() が返すディレクトリエントリの順序は指定されていないことに注意してください。ファイルシステムによっては、辞書式ソート順のエントリを返したり返さなかったりします。また、すべてのファイルシステムが d_type の値を提供するわけではなく、代わりに DT_UNKNOWN に設定するかもしれません。 (意訳)

FSに依存するという点はWindowsと同じようですが、順序については若干ぼかされている様子。

Linux

GCCかつ-std=c++17でコンパイルしているので、使用された標準ライブラリは libstdc++ であるはずです。ミラーがあるので活用しましょう。

長いので省略

directory_iterator の定義は include/bits/fs_dir.h にあります:

実装の内部、 src/c++17/fs_dir.cc をみていきます:

_M_Dir　は _Dir の std::__shared_ptrです:

_Dir の定義はここです:

関数 advance の実装はここです:

_Dir_base:

関数advance:

macOSと同じ dirent.h の関数 readdir を呼んでいます。

実装をもとに検証

ここまでの動作確認はGitHub Actionsを用いて行っていた(特にWindowsについては手元に開発環境がない)ので、一旦アーティファクトの形でローカルに持ってきて検証してみます。

artifacts

GitHub Actions + CMake のビルド環境を構成すると複数プラットフォーム向けのビルドもスイスイ対応してくれるので本当にありがたいです。
諸君私は自動化が好きだ ^[3]

検証方法

検証OS:

Windows 10 Home (21H1, 19044.2251 富士通 LIFEBOOK UH75/B1)
macOS Monterey (12.6.1 MacBook Pro 2020)
Linux Mint (20.2 Cinnamon 富士通 LIFEBOOK UH75/B1)

検証FS:

NTFS
FAT32
HFS+ (MacOS拡張（ジャーナリング）) ^[4]
APFS (HFS+でフォーマット後、ディスクユーティリティより変換)
ext4

基本的に各OSでよく使われるコたちを集めました。

ストレージについては、こちらの

fossil-mmc

化石みたいな容量のSDカード^[5]をターゲットにします。

肝心の検証方法ですが、名称を e, d, c, b, a としたファイルをこの順で作成しておき、各OS向けにビルドしたプロジェクトを実行して出力された順番がどうだったかを記録していくという方針としました。

結果・考察

以下のようになりました。

	NTFS	FAT32	HFS+	APFS	ext4
Windows	📚	✏️	`-`	`-`	`-`
macOS	📚	✏️	📚	❓	`-`
Linux	📚	✏️	`-`	`-`	❓

凡例：

📚: 辞書順。今回の条件では a, b, c, d, e と出力された場合。
✏️: 作成順。今回の条件では e, d, c, b, a と出力された場合。
- (ハイフン): 検証不能。 OSが該当FSに対応していなかった場合、または対応するドライバを(私が)持っていない場合。
❓: 不明。ファイルシステムの実装によるようですが、検証できていません。

NTFSとFAT32のOS間ポータビリティがすごいです。 ~~FAT32はともかくNTFSはなんでこんなtうわなにするやめ~~

一番驚いたのは HFS+ → APFS の過程でファイルの配置順が変わっていることでしょうか。いろいろなパターンで検証したのですが、HFS+ では何度やっても辞書順に並んだように見えました。
ただ、manページに記述がある通り the order of the directory entries vended by readdir() is not specified. とのことなので、この結果も信用するべきではないのでしょう。

またファイルの容量やファイル名の文字数、そのドライブで過去にどのようなファイルが作成されたかなどのパラメータも関わってくる可能性があるため、完全に予測するのはほぼ不可能といってよいのでは、とも思います。

ただし、 NTFSに限ってはその限りではなさそうです:

In summary, therefore, Explorer sorts the items so you (a human) can find them. NTFS sorts the items so it (the computer) can find them. If you’re writing a program and you want the results of a directory listing to be sorted, then sort it yourself according to the criteria of your choice.

したがって、エクスプローラは人間向けにアイテムをソートし、探しやすくします。 NTFSはコンピュータ向けにアイテムをソートし、同様に探せるようにします。もしあなたがプログラムを作成していて、かつディレクトリリストの結果をソートしたい場合は、選択した基準に従って自分でソートしてください。

つまり… NTFSはNTFSで独自の規則を持ってディレクトリエントリを並べ替え、 FindNextFileW が呼ばれた際にそれを返してくれる…ということになります。
実際に確認された動作とも合致するのでこれはそう感がありますが、そうなるとなにゆえファイルシステムレベルでエントリを並べ替える必要があるのでしょうか…?

もはやC++の話ではなく、また書き手の知識的にこれ以上は何もわからないので
このあたりにとどめておきます。

まとめ

長くなりました。未既定の処理の追跡に10k文字は長すぎです。
さらにいうと、この記事を描き始めたのはクリスマス真っ只中です。人々がチキンとケーキとツリーを並べている最中に私はllvmとmsvcとlibstdc++を並べていました。どう考えても不審者。

LLVMもGCCもMSVCもそうですが、一部とはいえ実装そのものを追いかけるのは初めての体験です。同一の機能を実現するための実装がこれほど多彩であることに驚きました。

以上、おそまつさまでした。
よい年末を！

脚注

set - cpprefjp C++日本語リファレンス ↩︎
path::compare - cpprefjp C++日本語リファレンス ↩︎
自動化流行らせ隊指揮官のお言葉 (確か元ネタはTwitterだったはずですが、すぐに見つけられませんでした) ↩︎
Macのディスクユーティリティで利用できるファイルシステムフォーマット - Apple サポート (日本) ↩︎
フォーマットする前に中身を覗いたところ、内容的に3DSに入っていたもののようでした。懐かしいですね。 ↩︎

ディレクトリを走査してくれる関数

OS別の挙動比較

1. macOS

2. Ubuntu

3. Windows

結果

対処

実装を読みに行く

Windows

macOS

Linux

実装をもとに検証

検証方法

結果・考察

まとめ

Discussion