[C++]de Bruijn sequenceを用いたLSB/MSB位置検出テクニック

de Bruijn sequence(ド・ブラウン列)

de Bruijn sequenceとは、いくつかの文字である長さの文字列を作ることを考えた時、その組み合わせの全てを含んだ文字列のことを言います。

例えば、文字a, bを使った長さ3の文字列はaaa, aab, aba, baa, abb, bab, bbb, bbaの8通りなので、このde Bruijn sequenceはaaababbbになります。
この文字列を先頭から3文字、1文字づつ右にずらしながら見ていくと(途中で巡回する)、確かに8通りの組み合わせ全てを含んでおり、重複が無い事が分かります。

aaababbb
aaa|||||
 aab||||
  aba|||
   bab||
    abb|
     bbb
      bba (先頭へ戻る
       baa

文字a, b0, 1に置き換えてやれば、2進数列のde Bruijn sequenceを考える事ができそうです。

de Bruijn sequenceによるLSB位置検出

この2進数列のde Bruijn sequenceを用いて、高速にLSB位置を検出するアルゴリズムがあります。

Wikipediaより

unsigned int v;   
int r;

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

これによって符号なし32bit整数値の最下位ビット位置を得ることができます。
何やってるのかさっぱりわかりません・・・

なにがおきているの?

少しコードを整理してみます(ついでにC++的になおします)。

int lsb_pos(unsigned int v) {

  //1
  static constexpr int MultiplyDeBruijnBitPosition[32] = 
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };

  //2
  std::uint32_t pop_lsb = (v & -v);

  //3
  std::uint32_t hash = std::uint32_t(pop_lsb * 0x077CB531U) >> 27;

  //4
  int r = MultiplyDeBruijnBitPosition[hash];

  return r;
}

少し見やすくなったでしょうか、番号を振ってあるところを順に見て行きますと

  1. 謎の配列、ここに入ってる値がビット位置になっている様子
  2. 謎のビット演算テク、これは最下位ビットだけを残すポピュラーなテクニック
  3. 一番意味分からない所、後続の処理を見るにどうやら[0, 31]の数値を出力している
  4. 3の結果をインデックスとして1の配列を参照。参照先がビット位置に対応している

3番以外は何やってるのかわかるのではないかと思います。3番が分からないので全部わからないのですが・・・

しかし、整理したコードをよく見るとこのアルゴリズムはハッシュテーブルによって高速にビット位置を求めていることが見えてきます。
すると、意味分からない3番目の処理はハッシュ値を求めている事に相当しそうです。そして、その入力は最下位ビットのみが立っている状態になっています。

つまり3番目の処理は、最下位ビットだけが立った値に対して完全ハッシュ(ダブりが無いハッシュ)を求めていることになります。

de Bruijn sequenceによる完全ハッシュ

//3
std::uint32_t hash = std::uint32_t(pop_lsb * 0x077CB531U) >> 27;

3番目の処理に出てくる謎の数字0x077CB531ですが、これが実はde Bruijn sequenceになっています。2進数に直して5文字づつ見て行くと確かに[0, 31]の数字(2進数列)がすべて含まれ、なおかつ重複がないことが確認できるでしょう(右から4ビットの所は先頭へ循環して見る必要があります)。

5文字・・・2^5 = 32であることに気付くと、27ビット右シフトというのは最上位5ビット分を残す処理である事が分かります(32 - 5 = 27)。

すると残った所はde Bruijn sequenceとpop_lsbのかけ算です。普通の数値のかけ算なら結果がどうなるかを考えるのは少し難しいですが、pop_lsbはどこか1ビットだけが立った値です。
つまり、その値は必ず2^nの値になります。その2のべき乗数値との掛け算はすなわちnビット左シフトに相当します。

ここでの2進de Bruijn sequenceは左から5桁づつ重複なく5ビットの表現全てを含んでいます。
整数型のビット数(今は32)未満であれば、nビット左シフトして左から5桁分を数値として読み取ると、n毎に異なった値が得られます。
しかも、5ビット数値なので2^5 = 32未満 = [0, 31]の値が得られます。

今、入力は最下位ビットのみが立った値であり、32ビット符号なし整数型なら取りえる値は32個だけです。従って、そのビット位置に応じた[0, 31]の個別の値をこの一行は計算しています。
あとは、テーブルによってその値をそのビット位置を示す数字に対応させてやれば、処理は完了です。つまり、1番初めに宣言されている配列はこの対応を取っているものである事が分かります。

8ビットの例

文字だけだと分からないので例を見てみましょう、しかし32ビットは長いので8ビットで見てみます。
8ビットの値は8桁なので、3ビットでその位置を表現可能です。従って、0, 1を使った3文字を尽くすような長さ8のde Bruijn sequenceが必要になります(元論文から拾ってきます・・・)。

先ほどの3番目の処理は以下のようになります。

std::uint8_t hash = std::uint8_t(pop_lsb * 0x1DU) >> 5;

当然ですがpop_lsbはどこか1ビットだけが立った8ビット符号なし整数値であることを前提とします。
つまり、入力となるpop_lsbは8個の値しかとりえません。それぞれについて処理を見てみると以下のようになります。

pop_lsb pop_lsb * 0x1D hash index
1 0001 1101 000 0
2 0011 1010 001 1
4 0111 0100 011 3
8 1110 1000 111 7
16 1101 0000 110 6
32 1010 0000 101 5
64 0100 0000 010 2
128 1000 0000 100 4

こうしてみるとどこか1ビットだけが立った値をうまいこと3ビット数値に押し込めた完全ハッシュになっている事が分かるでしょう。
後はこのindex位置に、対応する桁数を持つような配列を用意してあげるだけです。

constexpr int table[8] = { 1, 2, 7, 3, 8, 6, 5, 4 };

上の表で得られたindextable[index]として値を取得すると、元のpop_lsbの立っているビットの位置が得られる事が分かるでしょう。

Nビット整数への一般化

Nは2のべき乗である必要がありますが、上記アルゴリズムは以下のようにNビットへ一般化できます。

hash(x) = (x * debruijn) >> (N - log_2(N))

ここで、Nは符号なし整数型の幅、debruijn0, 1を使ったlog_2(N)文字の組み合わせを尽くすような長さNの適切なde Bruijn sequenceです。
そのようなde Bruijn sequenceを求める方法はいくつかあるようです。しかし良く分からない・・・

なお、使用するde Bruijn sequenceは先頭log_2(N)桁が0で始まる必要があります。これはオーバーフロー対策と、掛け算(左シフト演算)時に全体が自然に循環するようにするためです。

64ビット数値のLSB/MSB位置を求める

では、64ビット符号なし整数型の最上位/最下位ビット位置を求める処理をC++で実装してみます。

最下位はここまでやってきたことの流れで実装できますが、最上位ビット位置は少し違った処理が必要です。
とはいっても、最上位ビット位置だけを残すビット演算テクニックが必要になるだけで、幸いそれはネットに落ちてました。

64bitで使用するde Bruijn sequenceは0x03F566ED27179461になります。これもネットに落ちてました・・・

最後の右シフト量は上記式から64 - log_2(64) = 58と求められます。

最終的に桁位置に写すテーブルは簡単な計算で求められます

constexpr auto hash_64(std::uint64_t x) -> int {
  return std::uint64_t(x * 0x03F566ED27179461UL) >> 58;
}

inline constexpr char hash2pos[] = {1, 2, 60, 3, 61, 41, 55, 4, 62, 33, 50, 42, 56, 20, 36, 5, 63, 53, 31, 34, 51, 13, 15, 43, 57, 17, 28, 21, 37, 24, 45, 6, 64, 59, 40, 54, 32, 49, 19, 35, 52, 30, 12, 14, 16, 27, 23, 44, 58, 39, 48, 18, 29, 11, 26, 22, 38, 47, 10, 25, 46, 9, 8, 7};

constexpr auto msb_pos(std::uint64_t x) -> int {
  if (x == 0) return 0;

  //最上位ビットだけを残す
  x |= (x >> 1);
  x |= (x >> 2);
  x |= (x >> 4);
  x |= (x >> 8);
  x |= (x >> 16);
  x |= (x >> 32);
  x = x ^ (x >> 1);

  int h = hash_64(x);

  return hash2pos[h];
}

constexpr auto lsb_pos(std::uint64_t x) -> int {
  if (x == 0) return 0;

  std::uint64_t v = x & -x; //最下位ビットだけを残す

  int h = hash_64(v);

  return hash2pos[h];
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

なお、このテクニックを応用することで更なるビット演算黒魔術を行えるようです(1が2つ並んでいる最上位の位置を求めるとか・・・)。
また、de Bruijn sequenceは南京錠の様な対象への総当たり攻撃の効率化や、ハミルトン路を求める問題をオイラー路を求める問題へ変換するなど色々応用できるみたいです(良く分かってない)。

参考文献

この記事のMarkdownソース

[Meson]Meson for C++の苦闘記

MesonでC++プロジェクトをクロスプラットフォームにビルドできるようにしたときのメモです。C++以外の事は分かりません・・・

基本

基本的なビルドスクリプトは以下のようになります。

# 必ずproject()から始める
project('test_project', 'cpp', default_options : ['warning_level=3', 'werror=true', 'cpp_std=c++17'], meson_version : '>=0.50.0')

# インクルードディレクトリ指定
include_dir = include_directories('include', 'oher/include')

# 実行可能ファイルを出力
executable('test_project', 'test.cpp', include_directories : include_dir)

公式のリファレンスとか

コンパイラを検出する

meson.get_compiler('cpp')コンパイラオブジェクト?を取得して、そこからget_id()コンパイラ文字列を取得します。
あとはifで分岐するだけです。

if cppcompiler == 'msvc'
# msvc用の処理
elif cppcompiler == 'gcc'
# gcc用の処理
elif cppcompiler == 'clang'
# clang用の処理
endif

ちなみに、コンパイルオプションを主要3コンパイラで分けたいだけならば、get_argument_syntax()を使うと便利です。これによって得られる文字列は、オプションの互換性があるコンパイラで同一になります。

project('test_project', 'cpp', default_options : ['warning_level=3', 'werror=true', 'cpp_std=c++17'], meson_version : '>=0.50.0')
cppcompiler = meson.get_compiler('cpp').get_argument_syntax()

if cppcompiler == 'msvc'
    # MSVC,clang-cl,icc(windows)用
    options = ['/std:c++latest']
elif cppcompiler == 'gcc'
    # gcc,clang,icc(linux)用
    options = ['-std=c++2a']
else
    # その他
    options = []
endif

include_dir = include_directories('include', 'oher/include')

executable('test_project', 'test.cpp', include_directories : include_dir, cpp_args : options)

例えばこうしておくと、それぞれのコンパイラで言語バージョンの指定ができます。
(ただし、デフォルトオプションとして指定している言語バージョンもそのままになってしまうので、MSVC等では警告が出ます・・・)

以下のページにこれらの関数で取得できるコンパイラ文字列の一覧があります。

VC++プロジェクトの癖

仕方ないことなのかもしれませんが、Mesonの出力するVC++プロジェクトは少し変わっています・・・

  • VS同梱の開発者コマンドプロンプトからmeson build --backend vsを実行しないといけない
  • 出力されたVC++メインのプロジェクトのプロパティはほぼ空(デフォルト)
    • 指定したコンパイルオプション等はビルド時には渡されているが、プロパティからは見えない・・・
      • このため、インテリセンスがC++14準拠になってしまう
  • プロジェクトプロパティの変更は、ビルド時にmeson.buildが変更されていてプロジェクト再出力が自動で行われた場合にリセットされる
    • 基本的にはこれ便利なんですけどもね・・・

VC++プロジェクトにヘッダを含める

出力されるVC++プロジェクトには指定したソースファイルは含まれていますが、インクルードディレクトリ内のヘッダは含まれていません。
例えばそれらのファイルを編集したくてVS上で開いたとしても、プロジェクト外のファイルに対してはインテリセンスがうまく働きません。
そのため、プロジェクトにそれらのヘッダを含めたいことがあるでしょう・・・

その場合は、ソースファイルと同じようにヘッダファイルを指定してやれば出力プロジェクトに含めることができます。

executable()extra_filesにプロジェクトに含めたいファイルを指定してやると含めておくことができます。

project('test_project', 'cpp', default_options : ['warning_level=3', 'werror=true', 'cpp_std=c++17'], meson_version : '>=0.50.0')
cppcompiler = meson.get_compiler('cpp').get_argument_syntax()

files = ['include/header1.hpp', 'include/header2.hpp']

include_dir = include_directories('include', 'oher/include')

executable('test_project', 'test.cpp', extra_files : files, include_directories : include_dir)

残念ながらあるフォルダ内ファイルを列挙する手段はなさそうなので、1つづつ指定するしかなさそうな感じがします・・・。

依存ライブラリをダウンロードしてもらう

依存ライブラリの指定はsubproject()を使えば出来ます。これはインストール済みCMake(もしくはパッケージマネージャ)を検出して、そこから依存ライブラリ情報を取得してダウンロードして・・・と自動でやってくれる様子です。

でもWindowsだとそんなの入ってないし、githubから引っ張ってきたリポジトリとかでもよろしくやってほしいものです。
そのままだとこれは出来ない様子ですが、ラップファイルを用意してやることでやってもらえます。

meson.buildがあるフォルダにsubprojectsというフォルダを作り、その中にライブラリ名.wrapというファイルを用意しておきます。

例えば、doctestというライブラリを使いたいとしますと。

subprojects/doctest.wrapは以下のように書きます。

[wrap-git]
directory=doctest
url=https://github.com/onqtam/doctest.git
revision=2.3.4
clone-recursive=true

意味はなんとなくわかると思います。directory=の所を変えるとダウンロードされるディレクトリ名が変わるようです。revision=はダウンロードしてくるものの指定です。HEADとかコミットハッシュが使えるようです。

そして、meson.buildを以下のようにします。

project('test_project', 'cpp', default_options : ['warning_level=3', 'werror=true', 'cpp_std=c++17'], meson_version : '>=0.50.0')

#サブプロジェクトの指定
doctest_proj = subproject('doctest')
#依存オブジェクトの取得(名前が決まっている)
doctest_dep = doctest_proj.get_variable('doctest_dep')

files = ['test.cpp', 'include/header1.hpp', 'include/header2.hpp']

include_dir = include_directories('include', 'oher/include', 'subprojects/doctest')

executable('test_project', files, include_directories : include_dir, cpp_args : options, dependencies : doctest_dep)

subproject('プロジェクト名')で依存ライブラリを指定し(多分ここでダウンロード等がなされる)、その戻り値からget_variable('ライブラリ名_dep')で依存オブジェクト?を取得します。
この依存オブジェクトは、対象ライブラリの持つmeson.buildに書かれている名前を指定しなければなりません(慣例的にライブラリ名_depとなっているようです)。

最後に、executable()に依存オブジェクトを指定してあげます。もし静的ライブラリ等の出力がある場合はここで自動的に取り込まれるようです(対象ライブラリの持つmeson.buildが適切に書かれていれば)。

この方法、git submoduleで対象のライブラリを管理していても、なんだかよろしくやってくれます。

ちなみにこれらの時、ダウンロードしてきたプロジェクトのトップにmeson.buildが無いとたぶん上手くいきません・・・。 ただ、ヘッダーオンリーライブラリならインクルードパスの指定だけしてやればいい気がします(get_variable()してexecutable()で依存関係指定をしないで、subproject()だけしておく)

CI(Travis AppVeyar)

これはまだ試していないのでどうなるのかわかりませんが、公式サイトにTravisとAppVeyarに対するymlのサンプルがあります。この通りにやれば出来そうです。

参考文献

この記事のMarkdownソース

[C++]expression-equivalentのお気持ち

expression-equivalent??

標準ライブラリへのRangeの導入に伴って新たに追加された言葉で、次のように定義されています。

expressions that all have the same effects, either are all potentially-throwing ([except.spec]) or are all not potentially-throwing, and either are all constant subexpressions or are all not constant subexpressions

何となく噛み砕くと以下のような意味合いです

ある2つ以上の式は、次の全てを満たす場合にexpression-equivalentである

  • 式は同じ効果を持つ
  • 例外を投げるかどうかが同一
    • 全ての式は例外を投げない
    • もしくは、全ての式は例外を投げうる
  • 式が定数式で実行可能であるかも同一
    • 全ての式は、(部分式としても)定数実行可能である
    • もしくは、全ての式は(部分式としても)定数実行不可

これは要するに、式の効果と例外を投げるかどうか、および定数式で実行可能かどうか、が全く同一である時にexpression-equivalentの関係にある、という事です。

これは何?

これは主にRangeライブラリのカスタマイぜーションポイントオブジェクト(以下CPO)の効果の定義において頻出します。
大体以下の様な形式で書かれています。

The expression CPO-name(E) for some subexpression E is expression-equivalent to:

  • expression-equivalentとなる式 if 条件
  • Otherwise, expression-equivalentとなる式 if 条件
  • ...
  • Otherwise, CPO-name(E) is ill-formed.

ここでのCPO-nameは任意のカスタマイぜーションポイントオブジェクト名で、EとはそのCPOの呼び出しに引数として与えられている式のことです。
そしてこの文章は、引数EによってCPO-name(E)の呼び出しがどのような効果を持つか?をつらつらと書いています(大体最後はill-formedとなりますが、ならない場合もあります)。

これは、これまでの標準ライブラリ関数等ならばその効果(Effects)の定義において、Equivalent to :以下に書かれていたものです。
つまり、expression-equivalentはこれまで説明に使われていたEquivalent toをCPO用に置き換えているものだと言えます。

Equivalent toとの違い

Equivalent toでは、ある関数等の効果を別の式の効果と等価であるとして定義します。この時、その効果には式が例外を投げるのかどうか、また部分的にでも定数式で実行可能であるか、が含まれてはいないようです。
それらは式の効果ではなく、関数に指定されているものだからです。

Rangeライブラリのカスタマイゼーションポイントオブジェクトは名前空間スコープに定義された関数オブジェクトであり、その呼び出しではADL等の機構によりユーザーが定義した任意の型に対してさえも目的となる処理を行おうとします。 その結果として、CPOの効果は一通りではありません。

Rangeライブラリ利用ユーザーはCPOの持つ効果のどれかに引っかかるように巧妙に自分の持つ型をカスタマイズすれば、Rangeライブラリに定義されている処理に任意の型をアダプトできます。

効果が複数あり、しかも入ってくる型がどのようにその効果のいずれかに対してアダプトされているかはわかりません。そのため、CPOの呼び出しは定数実行できるのか?呼び出しに伴って例外を投げるのか?は実行される処理によります。

Equivalent toでは指定した式のconstexpr性及びnoexcept性は伝播されないので、Equivalent toで効果を指定するだけではCPOの呼び出しがconstexprであるかnoexceptであるかは未規定になってしまいます。

そのため、expression-equivalentが必要になります。expression-equivalentな関係にある2つの式は、効果だけではなくconstexpr性及びnoexcept性に関しても同一です。
従って、CPOの呼び出しの効果としてexpression-equivalentとされている式に呼び出された型を当てはめることで、その効果と定数実行可能であるか?例外を投げうるか?をも含めて表明することができます。

なにいってんだこいつという感じなので例として、std::ranges::begin()を見てみましょう。
std::begin()は関数ですが、これはカスタマイゼーションポイントオブジェクトです。その効果は次のようにあります。

The name ranges​::​begin denotes a customization point object. The expression ranges​::​​begin(E) for some subexpression E is expression-equivalent to:

  • E + 0 if E is an lvalue of array type ([basic.compound]).
  • Otherwise, if E is an lvalue, decay-copy(E.begin()) if it is a valid expression and its type I models input_­or_­output_­iterator.
  • Otherwise, decay-copy(begin(E)) if it is a valid expression and its type I models input_­or_­output_­iterator with overload resolution performed in a context that includes the declarations: template<class T> void begin(T&&) = delete;
    template<class T> void begin(initializer_list<T>&&) = delete;
    and does not include a declaration of ranges​::​begin.
  • Otherwise, ranges​::​begin(E) is ill-formed.

引数の式をEとしてstd::ranges::begin(E)のように呼び出したとき、その効果はEに応じてその下に書かれている4つのいずれかと等価(expression-equivalent)、という事を言っています。

ユーザーが自作する任意の型に対して作用するのはおそらく2つ目と3つ目のものです。それぞれ以下のように定義されます。

  • 2つ目は、引数Eの(結果となるオブジェクトの)メンバ関数として定義されているE.begin()を呼び出す。
  • 3つ目は、Eの(結果となるオブジェクトの)関連名前空間からADLで見つかるbegin()か、std::begin()を呼び出す。

このbegin()をアダプトしたつもりの自作の型Tのオブジェクトaで呼び出したときにexpression-equivalentであるとは

2つ目の形式にアダプトした場合、std::ranges::begin(a)の呼び出しがconstexprとなるかは(あなたが書いた)a.begin()の定義によって決まり、例外を投げるかも(あなたが書いた)a.begin()によって決まるという事です。

同様に、3つ目の形式にアダプトした場合も、ユーザーが定義した(あなたが書いた)フリー関数のbegin(a)constexprなのかnoexceptなのかでそれらが決定される訳です。

さらに、どちらの場合も結果となるイテレータdecay_copyされて返されますが、このdecay_copyの処理が同様にconstexprなのかnoexceptなのかも(おそらくあなたが定義しているであろう)返されたイテレータ型によるわけです。

つまりはとっても他力本願な定義の仕方なのです。

参考文献

謝辞

この記事の9割は以下の方によるご指摘によって成り立っています。

この記事のMarkdownソース

[C++]ラムダ式から関数参照への変換(単項*演算子)

状態を持たないラムダ式は単項+演算子を頭につけると明示的に対応する関数ポインタに変換することができます。では、ポインタではなく関数への参照に変換したい時はどうすれば良いのでしょうか?
+をつけないだけでは関数参照にはなってくれません・・・

template<typename F>
void invoke(F&& f) {
  std::cout << "call functor." << std::endl;
  std::cout << f() << std::endl;
}

void invoke(int(&f)(void)) {
  std::cout << "call function reference." << std::endl;
  std::cout << f() << std::endl;
}

int main()
{
  invoke( []{ return 10; });
  invoke(+[]{ return 20; });
}

/* 出力
call functor.
10
call functor.
20
*/

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

あるのかわからないですが、こういう時に関数の参照をとるオーバーロードが選ばれてほしい時、わざわざ関数ポインタの型をusingしてキャストして...としなくても次のように頭に*を付けることで解決できます。

template<typename F>
void invoke(F&& f) {
  std::cout << "call functor." << std::endl;
  std::cout << f() << std::endl;
}

void invoke(int(&f)(void)) {
  std::cout << "call function reference." << std::endl;
  std::cout << f() << std::endl;
}

int main()
{
  invoke( []{ return 10; });
  invoke(+[]{ return 20; });
  invoke(*[]{ return 30; });
}

/* 出力
call functor.
10
call functor.
20
call function reference.
30
*/

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

見た目からすると、ラムダの頭に*を付けることで明示的に関数参照へ変換しているように見えます。

なお、同じシグネチャの関数ポインタをとるオーバーロードがあるとオーバーロード解決に失敗します。関数参照は関数ポインタに暗黙変換可能であり、その変換はオーバーロード順位に影響を及ぼさない為です(これはC++17以上からの挙動のようです)。

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

組み込みの単項*演算子

C++17規格の組み込み単項*演算子について見てみると次のようにあります。

he unary * operator performs indirection: the expression to which it is applied shall be a pointer to an object type, or a pointer to a function type and the result is an lvalue referring to the object or function to which the expression points.

なんとなく訳すと(powered by google翻訳

単項*演算子は間接参照を行う。引数型はオブジェクト型へのポインタ、もしくは関数へのポインタでなければならず、結果は引数が指すオブジェクトまたは関数を参照するlvalueとなる。

つまり、ラムダ式*を適用すると、暗黙の型変換により関数ポインタに変換され、その関数ポインタ参照先の実体が参照として返されており、戻り値型は関数参照型となるわけです。

使いどころ?

正直わかりません。ほぼノーコストで対応する関数ポインタへ暗黙変換されるのでラムダ式に単項+を使いたくなるときに替わりに使っても良いかもしれません。
そのようなコードを持っていけば誰かにドヤ顔できるかもしれません・・・・

小ネタ

単項+は関数ポインタから関数ポインタへ、単項*は関数ポインタから関数参照へ、それぞれ変換するので、それらを複数組み合わせることができるはずです、そう幾つでも・・・

int main()
{
  invoke(*+*+*+*[]{ return 10; });
  invoke(+*+*+*[]{ return 20; });
  invoke(*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*[]{ return 30; });
  invoke(**************+ + + + + + + + + + + + + + + + + + + + + + +**************+*+ + +*+*+ + +[]{ return 40; });
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

残念ながら、+を複数繋げるとインクリメントになってしまうので間にスペースが必要です。*の連続適用は関数ポインタへ暗黙変換されるので問題ありません。

参考文献

この記事のMarkdownソース

[C++]constinit?🤔

constinit指定子

constinit指定子はC++20より変数に付けることができるようになるもので、constexpr変数がコンパイル時に初期化される事を保証するように、constinit変数が静的初期化、特に 定数初期化 されている事を保証します。

しかし、constexprとどう違うのか、なにが嬉しいのか、などは中々理解しづらいものがあります。

提案文書より、サンプルコード。

const char *g() { return "dynamic initialization"; }
constexpr const char *f(bool p) { return p ? "constant initializer" : g(); }
  
constinit const char *c = f(true);  // OK.
constinit const char *d = f(false); // ill-formed

一見すれば、初期化式が定数式で実行可能ではない時にエラーを起こしているように見えます。とするとやはり、constexpr指定との差がよくわかりません・・・

静的変数の初期化

グローバル(名前空間スコープの)変数やクラスの静的メンバ変数、関数ローカルのstatic変数など静的ストレージにあるものはプログラムの開始前に、スレッドローカルストレージにあるものはスレッドの開始前に、それぞれ初期化が完了しています。

それらの変数はまずコンパイル時に 静的初期化 され、実行時(プログラムロード時、スレッド起動時)に 動的初期化 されます。結果として、プログラム開始時もしくはスレッド開始時には初期化が完了しているように見えているわけです(正確には実装は変数が使用される直前まで初期化を遅延させることが許可されています)。

動的初期化はその初期化式が定数式で実行できない場合に実行時に行われるものです。ここでは重要では無いので深掘りしません。

静的初期化はコンパイル完了時までになんらかの値で初期化しておくもので、 定数初期化ゼロ初期化 の2段階で行われます。

静的初期化においてはまず、定数初期化が可能であるならば変数は定数初期化されます。これによってその変数の初期値は確定し、以降の初期化はスキップされます。
次に、定数初期化できなかった残り全ての変数をゼロ初期化します。ゼロ初期化は変数をゼロに相当する値によって初期化するものです(例えば、浮動小数点型の0.0、ポインタ型のnullptr等)。この時、クラス型のコンストラクタは無視され、その型を構成する全ての型が再帰的にゼロ初期化されます。
これにより、静的ストレージ・スレッドローカルストレージにある変数は全てとりあえずはなんらかの値で初期化されている状態でコンパイルが終了します。

静的初期化された値はプログラムイメージ(実行ファイルバイナリ、アセンブリ)の一部としてプログラム内のどこかに埋め込まれています。

動的初期化はこのように初期化されている変数に対して、実行時に実際の初期化式によって初期化を行います。

定数初期化(constant initialization)

定数初期化は静的初期化の中で、他のあらゆる初期化に先行して行われます。そして、定数初期化が完了すればその変数の初期化はそこで完了しており、その後一切の初期化処理は行われません。

定数初期化を行うためには、変数が静的ストレージかスレッドローカルストレージにあり、その初期化式が定数式でなくてはなりません。
それを満たせば全ての変数は定数初期化できます。constexprが付いていなくてもいいですし、constがなくても大丈夫です。初期化式がconstexpr/consteval関数を呼び出していても、初期化に当たって一時オブジェクトを生成しても構いません。

ただし、定数初期化されているconstな整数型と列挙型だけが他の定数式で利用でき、その他の種類の変数は定数初期化されただけでは定数式で使えません。

定数初期化コンストラク

定数初期化はもちろん任意のクラス型に対しても行えます。
そのクラスがリテラル型でなかったとしても、constexprコンストラクタを持ち、そのコンストラクタからメンバ変数を全て定数式で初期化できれば、そのクラスのオブジェクトは定数初期化できます。

これを利用しているクラスはSTLにも存在しており、std::mutexのデフォルトコンストラクタ、std::unique_ptrのデフォルトおよびnullptrを受けるコンストラクタなどが定数初期化コンストラクタを持っています(std::unique_ptrのこれらのコンストラクタになぜconstexprが付いているのか不思議に思った人は多いのではと思います、こういう事です)。

上でも述べていますが、定数初期化(静的初期化)は静的ストレージかスレッドローカルストレージにあるものが対象で、ローカル変数に対しては適用されません。

#include <mutex>
#include <memory>
#include <thread>

struct C {
  C() = default;

  C(int n) : m(n) {}

  operator int() const noexcept {
    return m;
  }

private:
  int m;
};

//全て定数初期化される
std::mutex m{};
std::unique_ptr<int> p1; 
std::unique_ptr<int> p2 = nullptr;
C c1{};

//これは動的初期化になる(切り替えられるかもしれない)
C c2{10};

int main() {
  std::lock_guard lock{m};

  int n = c1;
  int m = c2;

  //ローカル変数の初期化はまた別の話・・・
  std::unique_ptr<int> p3;
}

出力アセンブリ例 - Compiler Explorer

コンパイル結果を見ても静的初期化されてるのか動的初期化されてるのかはよくわからないですね・・・。gccの方は__static_initialization_and_destruction_0(int, int):なるセクションに突っ込まれているのはわかりますが・・・

動的初期化の静的初期化への切り替え

静的初期化(定数 or ゼロ初期化)は必ず行われた上でコンパイルが完了しています。
そして追加で、コンパイラは次の条件を満たす場合に動的初期化を静的初期化に切り替えることが許されています。

  • 動的初期化で実行される予定の初期化式は副作用を持たない
  • 静的初期化に切り替えても、動的初期化した場合と全く同じ値で初期化できることが保証できる
    • 他の静的変数の初期化式に依存している・されている場合でも結果が同じにならなくてはならない
    • すなわち、プログラム全体として初期化後の結果は切り替え前と全く同一でなければならない

すなわち、通常の初期化順序に沿って動的初期化を行った結果と(プログラム全体として)全く同じ結果になることがコンパイル時に分かる場合に、動的初期化を静的初期化に切り替えることが許されます。

動的初期化から切り替えてゼロ初期化するというケースは無いと思うので、実質的に定数初期化されることになります。
この初期化タイミングの切り替えは可能であっても必ず行われるとは限りません。コンパイラによります。

constinitの効能

変数を静的初期化、特に定数初期化しておくことのメリットは、その変数の初期化に関してデータ競合などを考える必要がないことです。

動的初期化では初期化処理はプログラム実行時(スレッド起動時)の一番最初に起こり、その初期化の順序及び初期値に依存するようなコードではデータ競合によって思わぬバグを仕込むことになる可能性があります。
翻訳単位を超えて動的初期化される変数を使っている場合などはその初期化順およびそれに起因するバグを理解することは非常に困難になるでしょう・・・

静的初期化では初期化処理はコンパイル時に完了しており、そこでは翻訳単位毎に宣言順で初期化されるためデータ競合は発生しません。プログラム開始時、動的初期化開始前にはその初期値は確定しており静的初期化された変数の初期値に依存するような処理を少しだけ安全に書くことができます。

通常の静的初期化は少なくともゼロ初期化が行われている事は間違い無いのですが、定数初期化が行なわれたかどうか、つまり変数が動的初期化されるのかどうかをコンパイル後に知る事は困難です。
前項の動的初期化からの切り替えも必ず行われるとは限りませんし、思わぬ変更から定数初期化しているつもりの初期化式が動的初期化になってしまっている事もありえます。本当に定数初期化されたかを見るのはアセンブリを確認するしかありません・・・

これはconsteval関数が導入された理由の一つと同じ問題です。つまり、constexpr変数の初期化以外の所でconstexpr関数が本当にコンパイル時に実行されたかどうかは容易には分からなかったのです。

constexpr変数・consteval関数と似たように、constinit変数は変数が動的初期化される場合にコンパイルエラーを起こします。別の言い方をすると、constinit指定子はconstinit変数が動的初期化されないことを保証します。
そして、constinit変数は確実に静的初期化によってコンパイル時に初期化が完了します。

利用例

前述のように、constinit指定は静的・スレッドローカルストレージにある変数に指定でき、その初期化式が定数式でなければなりません。
初期化式が無い場合、静的・スレッドローカルストレージにある変数はゼロ初期化され、実行すべき初期化式が無いために動的初期化されません。したがって、constinit変数に初期化式がない場合はゼロ初期化が保証されます。

静的初期化されるかどうかはリンケージ指定(static, extern)とは無関係ですが、別の翻訳単位で定義されている変数のextern宣言に対してのconstinit指定は未定義動作を引き起こすので注意が必要です(おそらくエラーにはなりません)。

#include <mutex>
#include <memory>
#include <random>

constinit const int N = 1;    //ok
constinit unsigned int M = N; //ok、constな整数型は定数式で利用可能

constinit thread_local static int Counter = 0; //ok

constinit const double PI = 3.1415; //ok
constinit double PI2 = PI + PI;     //ng、変数PIは定数式で利用不可

constinit static int L; //ok、ゼロ初期化される
constinit int Array[3]; //ok、ゼロ初期化される

constinit std::mutex m{};           //ok、定数初期化コンストラクタ呼び出し
constinit std::unique_ptr<int> p1;  //ok、定数初期化コンストラクタ呼び出し

constinit extern int def = 10;  //ok
constinit extern int ext;       //ng、おそらくエラーにはならないが未定義動作(診断不要)


struct S {
  constinit static const int x;
  static const int y;
  static constexpr int z = 56;
};

const int S::x = 12;            //ok、constinit変数なので定数初期化される
constinit const int S::y = 34;  //ok、constinit変数なので定数初期化される
constinit constexpr int S::z;   //エラーにはならないと思われるが意味がなく、インライン変数に対する多重定義
                                //constexpr静的メンバ変数に対するクラス外定義はC++17以降非推奨

int main() {
  constinit static std::unique_ptr<int> ptr = nullptr;                //ok、静的ローカル変数
  constinit thread_local std::mt19937 engine(std::random_device{}()); //ng、定数式で初期化できない

  constinit int local = 0;  //ng、ローカル変数
}

constinit指定は変数宣言に指定でき、その効果はその変数の初期化宣言に対して適用されます。通常の変数はその2つを分かつことができませんが、extern変数や静的メンバ変数のように宣言と定義(初期化宣言)が別れる場合、定義からconstinit宣言が到達不可能となると未定義動作(診断不要)です。

なお、名前にconstが付いているので紛らわしいかもしれませんが、constinit変数は暗黙constではなくconst変数にしか付けられないわけでもありません。
constinit変数はconstexpr変数とは異なり、明示的にconst修飾されていなければ実行時に値を変更することができます。

const一族

const constexpr consteval constinit
誕生時期 神代の頃 C++11 C++20 C++20
変数に付加 🔺
関数に付加 🔺
変数への効果 immutable化 定数式でも使用可能
実行時にconst
コンパイルエラー 静的初期化保証
関数への効果 const変数からのみ呼出可能 定数式でも使用可能 定数式でのみ使用可能 コンパイルエラー

参考文献

この記事のMarkdownソース

[C++]std::regexでパターンにマッチするすべての文字列を抽出する

std::regexを使う時多くの場合はstd::regex_searchを使うと思われますが、std::regex_searchはそのままだとマッチする1番最初の文字列しか得ることができません。
しかし、文字列の中からマッチする全ての要素が欲しいということはよくあることでしょう。調べても頑張ってずらしてもう一回searchだ!という方法しか出てきません。やはりスマートにやりたい・・・

std::match_results::suffix()

std::regex_searchの結果として得られるstd::match_resultssuffix()というメンバ関数を持っています。この関数は結果としてマッチした文字列を除いた残りの文字列(への参照)を返します。
その文字列に対してもう一度searchすれば2番目にマッチする部分文字列が得られ、それを繰り返せば残りのマッチング文字列を得ることができます。

#include <regex>

int main()
{
  std::string str = "1421, 34353, 7685, 12765, 976754";
  std::regex patern{R"(\d+)"};
  std::smatch match{};
  
  while (std::regex_search(str, match, patern)) {
    std::cout << match[0].str() << std::endl;
    str = match.suffix();
  }
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

とても簡単な方法ではありますが、一々コピーが発生するのと変更可能なstd::string等でしか使えないのが少し残念なところです。

std::sub_match::second

頑張ってずらしてもう一回searchだ!という方法を頑張らないでやる方法です。

std::match_resultsstd::sub_matchとしてパターン内各グループの結果を保持しており、一番最初のstd::sub_matchは見つかった文字列全体が得られます。
そして、std::sub_match::secondはそのサブマッチ文字列の次の位置を指すイテレータです。

つまり、一番最初のstd::sub_match::secondを始点としてもう一度std::regex_searchをすれば2番目にマッチする文字列が得られ、それを繰り返せば文字列内からパターンに一致する全ての部分文字列を抽出することができます。

#include <regex>

int main()
{
  constexpr char str[] = "1421, 34353, 7685, 12765, 976754";
  std::regex patern{R"(\d+)"};
  std::match_results<const char*> match{};
  
  for (bool ismatch = std::regex_search(str, match, patern); ismatch != false; ismatch = std::regex_search(match[0].second, match.suffix().second, match, patern)) {
    std::cout << match[0].str() << std::endl;
  }
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

for文の宣言部がとても長くて見づらいですが、std::regex_searchを繰り返し毎に実行し、その結果のbool値を見て終了判定しています。

そして、ループ中のstd::regex_searchmatch[0].secondから始めることでそれまでに一致した部分を飛ばして探索しています。なお、match.suffix().secondというのは元の文字列の終端(std::end(str)相当)に当たります(std::end(str)でも良いはずですが、型が合わないと怒られたのでこうしました・・・)。

この方法はイテレータを用いて元の文字列の参照範囲を変更して再検索しているだけなので、文字列のコピーは発生しません。

std::regex_iterator

上記std::sub_match::secondを用いる方法をラッピングしたイテレータstd::regex_iteratorとして標準に用意されています。

int main()
{
  constexpr char str[] = "1421, 34353, 7685, 12765, 976754";
  std::regex patern{R"(\d+)"};
  
  for (std::regex_iterator<const char*> itr{std::begin(str), std::end(str), patern}, last{}; itr != last; ++itr) {
    std::cout << (*itr).str() << std::endl;
  }
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

多少スッキリとし、基本的なイテレータ操作で書けているので処理も分かりやすいです。
先ほどのstd::sub_match::secondを使って次を検索、という部分をstd::regex_iteratorが中でよろしくやってくれています。

regex_searchesを作る

やはり、regex_searchのように一発でやりたいし、なんなら範囲for文使いたいです。なので綺麗にラッピングして少し便利にしてやりましょう。

template<typename Str>
auto regex_searches(Str& str, const std::regex& patern) {
  using std::begin;
  using std::end;
  using str_iterator_t = decltype(begin(str));
  
  struct wrap_regex_iterator {
    using iterator = std::regex_iterator<str_iterator_t>;
  
    auto begin() const noexcept -> iterator {
      return first;
    }
    
    auto end() const noexcept -> iterator {
      return last;
    }
    
    explicit operator bool() const noexcept {
      return first != last;
    }
    
    iterator first;
    iterator last;
  };
  
  return wrap_regex_iterator{{begin(str), end(str), patern}, {}};
}


int main() {
  const std::string str = "1421, 34353, 7685, 12765, 976754";
  std::regex patern{R"(\d+)"};
  
  for (auto&& match : regex_searches(str, patern)) {
    std::cout << match.str() << std::endl;
  }
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

ローカルクラス大好きなのでローカルクラスを使いましたが、外にあっても構いません。あとoperator boolはあくまでregex_searchのように戻り値を利用するために付けただけなのでなくてもいいです。というか範囲forで使う分にはほぼ無意味です。

入力となる型などを厳密にする場合は、std::regex_searchの各オーバーロードと同様にする必要がありますが、ここでは割愛・・・

書くことが多くなるので、数カ所で使うとかどうしても範囲forでーというときに多少便利になるかもしれません。

参考文献

謝辞

この記事の7割は以下の方によるご指摘によって成り立っています。

この記事のMarkdownソース

[C++]モジュール理論 上級編(魔境編)

※この記事はC++20を相談しながら調べる会 #2の成果です。

※この内容はC++20より有効なものです。C++20正式策定までの間に内容が変化する可能性があります。

前回記事で説明していることは説明しなおしません。

onihusube.hatenablog.com

importmoduleというキーワード

exportC++11以前に規定されていたテンプレートのエクスポートという機能のために使用されていたキーワードだったため、C++11以降もユーザーが使用することは出来ませんでした。
しかし、importmoduleというキーワードは予約もなにもされていなかったので以前から自由に使えます(C++20においても使用可能)。
しかしモジュールにおいても文脈依存キーワードとして使用するため以前の挙動が変化することがあります。

template<typename>
class import {};  //ok

import<int> f();  //ng!(C++17以前はok)
                  //C++20より、ヘッダーユニットのインポート宣言として解釈され、エラー
::import<int> g();//ok


class module;     //ok
module *m1;       //ng、モジュール宣言とみなされる(C++17以前はok
::module *m2;     //ok


class import {};  //ok(再宣言とかはとりあえず気にせず・・・
import j1;        //j1というモジュールをインポート(C++17以前は変数宣言
::import j2;      //変数宣言

詳細には、moduleexport moduleimportexport importのどれかで始まりその後に::が続かない宣言は、必ずモジュール宣言もしくはインポート宣言として扱われます。

すなわち、以下の様なものが存在している可能性があるのです・・・

module::C f1();         //module::C型を返す関数f1の宣言

export module::C f2();  //module::C型を返す関数f2のエクスポート宣言

import::T g1();         //import::T型を返すg1()の宣言

export import::T g2();  //import::T型を返すg2()のエクスポート宣言

これからはimportmoduleを何らかの名前にするのはやめましょう。

プリプロセッサの扱い

モジュール内部でも#include #defineをはじめとするプリプロセッサは使用可能です。importexportをマクロで生成・切り替えすることは特に禁止されていません(グローバルモジュールフラグメントの後のモジュール宣言は除く)。

しかし、従来のヘッダファイルのようにインクルード前に特定の#defineをしておくことでヘッダ内の挙動を変更する、というようなことは出来ません。

なぜなら、モジュールはそれそのものが一つの翻訳単位であり、importするころには個別に何らかの形にビルドされているからです。さらに言えば、import宣言はインポートする翻訳単位内宣言の可視・到達可能性にのみ影響するため、マクロがそれを介してモジュール内部に影響を与えることは不可能です。

ただし、モジュールのビルドに関しては何ら規定がなく完全に実装に一任されています。どの段階までビルドされているかは実装依存ですが、モジュール宣言の識別やexport宣言を確定させなければならない事から、少なくとも翻訳フェーズの4(プリプロセッサの実行とプリプロセッサディレクティブの削除)の完了まではビルドされているはずです。

マクロのエクスポート

通常の名前付きモジュール内でのexport宣言ではマクロをエクスポートすることは出来ません。

なぜなら、export出来るのは何らかの名前を導入する宣言のみでありマクロ定義そのものは宣言ではありません。もちろんマクロがプリプロセスの結果としてexport可能な宣言に置換される場合はその宣言の導入する名前がエクスポートされます。

///Mymodule.cpp
export module Mymodule;

export #define PI 3.14159     //ng、名前を導入する宣言でないのでコンパイルエラー
export #define STR(str) #str  //ng、名前を導入する宣言でないのでコンパイルエラー

//上記2つはエクスポート宣言として解釈される頃には以下のようになっている
//export
//export

#define E 2.718281

export const double e = E;    //ok、グローバル変数eのエクスポート

#ifdef PREDEFINED

export int f(); //ok、実装略

#else

export int g(); //ok、実装略

#endif


///main.cpp
#define PREDEFINED
import Mymodule;

int main() {
  //マクロのエクスポートがコンパイルエラーとなっていなかったとして
  double pi = PI;             //ng
  char str[] = STR(Modules);  //ng
  double e2 = 2.0 * e;        //ok
  int n = f();                //ng
  int m = g();                //ok
}

なお、ヘッダーユニットでは例外的にマクロをエクスポートすることができます。ヘッダーユニットの場合は、ヘッダーファイルを翻訳フェーズ7完了(テンプレート以外のコンパイル完了)までコンパイルされたモジュールとしてインポートすることになり、マクロはその際の翻訳フェーズ4終了直前にヘッダーユニット内に残っているものがエクスポートされます。

そのため、結局ヘッダーユニットでもマクロの事前定義によって内部に影響を与えることは出来ません。

名前が可視でなければ定義が到達可能でもないクラスの利用

一体何を言っているのでしょうか・・・

モジュール仕様の重箱の隅としてこのようなクラスが割と容易に存在できてしまいます。

///Othermodule.cpp
export module Other;

//宣言(型名)のみエクスポート
export struct hidden_def;

export hidden_def get_hidden_def();

module : private;

struct hidden_def {
  int n = 10;
};

hidden_def get_hidden_def() {
  return {20};
}


///Mymodule.cpp
export module Mymodule;
import Other;

//エクスポートしない
struct hidden_name {
  double d = 1.0;
};

export hidden_name get_hidden_name() {
  return {3.14};
}

export hidden_def* get_ptr() {
  static auto hd = get_hidden_def();
  return &hd;
}


///main.cpp
import Mymodule;

int main() {
  auto hn = get_hidden_name();  //ok
  auto* hd = get_ptr();         //ok

  hidden_name hn2 = get_hidden_name();  //ng、hidden_nameは可視ではない
  hidden_def* hd2 = get_ptr();          //ng、hidden_defは可視ではない

  double d = hn.d;  //ok、定義は到達可能
  int n = hd->n;    //ng、定義は到達可能ではない
}

このように、関数の戻り値型として付属してエクスポートされた型は、必ずしもその名前が可視にはならず、場合によっては定義も到達可能になりません。
例にあるように、autoで受けることで使用可能にはなるようです。そのメンバを利用するには定義が到達可能でなくてはなりません。

詳細は後述しますが、ADLによってこうした型に対する関数の探索は不思議な大ジャンプをすることがあります。

///Othermodule.cpp
export module Other;

namespace Other {

  //宣言(型名)のみエクスポート
  export struct hidden_def;

  export hidden_def get_hidden_def();

  export int f(hidden_def* phd);
}

module : private;

namespace Other {
  struct hidden_def {
    int n = 10;
  };

  hidden_def get_hidden_def() {
    return {20};
  }

  int f(hidden_def* phd) {
    return phd->n;
  }
}


///Mymodule.cpp
export module Mymodule;
import Other;

export hidden_def* get_ptr() {
  static auto hd = get_hidden_def();
  return &hd;
}


///main.cpp
import Mymodule;

int main() {
  auto* hd = get_ptr(); //ok

  int n = f(hd);        //ok、ADLによってモジュールOther内のOther::f()の宣言が見つかる
                        //Other::f()は外部リンケージを持つため呼び出し可能
}

このように、直接インポートしているわけではないのにも関わらず、翻訳単位を飛び越えてADLが関連名前空間の探索を行い、関数を見つけてきています。
この場合は探索のきっかけとなった型が直接所属する名前空間の範囲内にのみ起こり、見つかった宣言は外部リンケージを持っていないと呼び出せません。

inline変数・関数

モジュールにおいてもinline変数・関数の性質や意味合いに変化はありませんが、名前付きモジュールに属する宣言は同一かどうかに関わらず複数の定義を持つことは出来ません。
そのため、これまでのようにヘッダに書いてインクルードのようなことは出来ないことになります(モジュールはヘッダを置き換えるものなので当然ですが)。

モジュールにおいてのinline変数・関数は以下の規則の下宣言・定義できます。

  1. 名前付きモジュール内で定義は厳密に唯一つでなければならない
    • ただし、以前の定義が到達可能でなければエラーにならない
  2. ある変数・関数の定義が、それに対する最初のinline宣言の時点で到達可能であってはならない
    • inline指定は定義そのもの、もしくはそれより前の宣言で行うこと
  3. 外部・モジュールリンケージを持つinline変数・関数は、使用されるすべての翻訳単位でinline指定された宣言が到達可能でなければならない
  4. inline変数・関数の定義はそれが使用されるすべての翻訳単位(の末尾)から到達可能でなければならない
    • 定義が現れるよりも前に使用されていても良い

重要なのは1つ目と4つ目の規則で、残りは注意点の様なものです。
4つ目の規則は、inlineなものの名前の(翻訳単位外からの)参照は外部リンケージによる翻訳単位超えではなく、その定義に到達する事によって参照される、事を言っています。

これらの規則とODRから、モジュール内部でinline変数・関数を使用しようとする場合はその定義はそのモジュール内部でなされなければならず、モジュール外部で定義された、もしくは外部にも定義がある、という事は許されない事が分かります。

この様にモジュール内で定義され、エクスポートされたinline変数・関数の定義はその参照のために自動的に移動されます。その定義を行ったところではなく、エクスポートされた宣言がある翻訳単位において(プライベートモジュールフラグメントの外側で)定義されます。
これはすなわち、inline変数・関数をエクスポートする場合はそのインターフェース単位で定義を行わなくても、その定義はインポート先で到達可能となることを意味しています。
その際、その定義の本体から参照する事が出来るもの(可視となっている宣言等)に影響はありません。

///Mymodule_interfacepart.cpp(インターフェースパーティション
export module Mymodule:Interface;

export inline double g();

double use_g() {
  return g(); //ok、定義の移動によりこの翻訳単位で定義が到達可能
}

///Mymodule_implpart.cpp(実装パーティション
export module Mymodule:Part;
import :Interface;

//:Part内でのみ参照可能(インポートされない限り)
inline constexpr double PI = 3.141592;

//g()の定義はここではされず、Mymodule:Interface内へ移動する
inline double g() {
  return PI;  //ok、PIは参照可能
}


///Mymodule.cpp(プライマリインターフェース単位
export module Mymodule;
export import :Interface;

export int f(); //非inlineでエクスポート、この時点ではf()は非inline関数

inline int f(); //再宣言、以降f()はinline関数、この宣言はインポート先で到達可能

double use_f() {
  return f(); //ok、定義の移動によりこの翻訳単位で定義が到達可能
}


///Mymodule_impl.cpp(実装単位
module Mymodule;

//この実装単位内でのみ参照可能
inline constexpr int N = 10;

//f()の定義はここではされず、プライマリインターフェース単位へ移動する
inline int f() {
  return N * 10;  //ok、Nは参照可能
}


///OnefileModule.cpp
export module One;

export inline int h();

module : private;

int h_impl() {
  return 1;
}

//h()の定義はここではされず、プライベートモジュールフラグメント外へ移動する
inline int h() {
  return h_impl();  //ok、h_impl()は参照可能
}


///main.cpp
import MyModule;
import One;

int main() {
  int n = f();      //ok、定義はプライマリインターフェース単位にあり到達可能
  double pi = g();  //ok、定義はインターフェースパーティションにあり到達可能
  int m = h();      //ok、定義はプライベートモジュールフラグメント外にあり到達可能
}

NG例

///Mymodule_interfacepart.cpp(インターフェースパーティション
export module Mymodule:Interface;

export inline double g();
//2つの実装パーティションの定義はここに移動されるため
//以前の定義が到達可能な状態で異なった再定義をされることになり
//おそらくコンパイルエラーとなる


///Mymodule_impl1.cpp(実装パーティション1
export module Mymodule:Part1;
import :Interface;

inline double g() {
  return 3.141592;  //ng! 異なった複数の定義
}


///Mymodule_impl2.cpp(実装パーティション2
export module Mymodule:Part2;
import :Interface;

inline double g() {
  return 2.718281;  //ng! 異なった複数の定義
}


///Mymodule.cpp(プライマリインターフェース単位
export module Mymodule;
export import :Interface;

export int f() {
  return 10;
}

inline int f(); //ng! f()は既に非inlineとして定義されている

export inline int g(int n) {
  return 100 * n;
}


///Mymodule_impl.cpp(実装単位
module Mymodule;

//ng! 定義の重複は許されない
inline int g(int n) {
  return 100 * n;
}

なお、グローバルモジュール(すなわちモジュール外部)においてはこれまで通りにヘッダを用いるなどしてinline変数・関数を定義し、使用できます。ただし、その宣言・定義がモジュール内部のものとかち合ってしまうとODR違反となります。

グローバルモジュールフラグメントの利用

モジュール内でinline変数・関数を利用しようとすると、これまでのようにヘッダを用いることはできず、必ずモジュール内部で定義すること!と言うことを言っていましたが、実はこれには抜け穴があります。
グローバルモジュールフラグメントを利用すると、上記の規則を完全に満たしつつ今までとほぼ同様の書き方ができてしまいます。

///inline.hpp(ヘッダファイル
inline constexpr double PI = 3.141592;

inline int f() {
  return 10;
}

inline int g() {
  return 100;
}

///Mymodule.cpp
module;

//グローバルモジュールフラグメント内に展開された宣言はグローバルモジュールに属する
#include "inline.hpp"
//定義はこの場所、グローバルモジュールにおいてなされる

export module MyModule;

export bool check_addr(const double* p) {
  return &PI == p;  //ok、inline宣言も定義も到達可能
}

int use_f() {
  return f(); //ok、inline宣言も定義も到達可能
}

///main.cpp
import MyModule;      //PIとf()は可視ではないが、到達可能かは未規定(g()は破棄されている)
#include "inline.hpp" //PIとf(),g()の宣言と定義がコピペされ可視になる
                      //MyModule内定義が到達可能だったとしてもODR違反にはならない

int main() {
  double s = PI * 2 * 2;    //ok
  int n = f();              //ok
  bool b = check_addr(&PI); //ok、b == true
}

グローバルモジュール、すなわちモジュール外コードではこれまでにできていたことが出来るようになっています。すなわち、グローバルモジュールでは定義はその文字列及び意味が完全に同一ならば複数存在することができます。
それを踏まえて上記規則をそれぞれチェックしてみれば、問題ない事がわかるでしょう。

この様にすると、今までの様にヘッダ定義をインクルードすることによってinline変数・関数を定義でき、複数のモジュールおよび翻訳単位に渡ってその定義を1つにすることができます。
逆に言うと、複数のモジュールで同一のinline変数・関数を使用するにはこうする他にありません。

モジュールにおけるテンプレートのインスタンス

当然ですが、テンプレートはモジュールにおいても使用可能ですし、エクスポートもできます。エクスポートしたテンプレートはモジュールの外で使用されるタイミングでインスタンス化されます。

そのインスタンス化の際、そのテンプレートの内部(定義)から参照できるものがその定義したところ(モジュール内部)だけだとモジュールでエクスポートしたいテンプレートを書くときの制限がとても多くなってしまいます。
そのため、インスタンス化経路path of instantiation)というルールを導入し、この経路上にあるものがインスタンス化時に参照可能になっています。

インスタンス化時に利用されるものは、その定義されたところでもインスタンス化したところでも可視又は到達可能でなかったとしても、インスタンス化経路上のどこかの点で可視又は到達可能であれば使用することができます。
ただし、そのようなものはテンプレート引数に依存しているものだけです(依存名のみ)。そうでないものはこれまで通りに1度目の名前解決時に確定されます。

///S.hpp
struct S { 
  void f(); //実装略
};


///moduleA.cpp
export module A;

export template<typename T, typename U>
void f(T t, U u) { 
  t.f();
}


///moduleB.cpp
module;

//グローバルモジュールフラグメント内宣言、モジュールBからのみ可視
#include "S.hpp"

export module B;

import A;  //モジュールAのインポート(not エクスポート)

export template<typename U>
void g(U u) { 
  S s;
  f(s, u);
}


///moduleC.cpp
export module C;

import B;  //モジュールBのインポート(not エクスポート)

export template<typename U>
void h(const U &u) {
  g(u);
}

///main.cpp
import C;

int main() { 
  h(0);
}

このh(0)呼び出しに伴うインスタンス化経路は以下のようになり、h(0)呼び出しに伴うテンプレートのインスタンス化においてはこの経路上の各点で可視・到達可能な宣言がそのまま可視・到達可能とされます。

  1. void f(T t, U u)定義点(moduleA.cpp内、定義)
  2. モジュールBの末尾
    • f(s, u);(moduleB.cpp内、呼び出し)
    • void g(U u)(moduleB.cpp内、定義)
  3. モジュールCの末尾
    • g(u)(moduleC.cpp内、呼び出し)
    • void h(const U &u)(moduleC.cpp内、定義)
  4. h(0)呼び出し地点(main.cpp内、インスタンス化の起点)

この例でインスタンス化経路が効いているのは、モジュールA内のf<S, int>(S t, int u)の定義内(t,f();)です。
その点からは構造体Sの宣言及び定義は可視でも到達可能でもありませんのでそのメンバは可視ではありません。しかし、インスタンス化経路上の2番目の点、モジュールBからはグローバルモジュールフラグメントの宣言を介して可視であり到達可能です。
結果、インスタンス化経路を通してモジュールA内f<S, int>(S t, int u)の内部からもSの定義が可視となり、そのメンバも可視になります。
従って、このコードは無事にコンパイルできます。

あるいは、インスタンス化コンテキスト

インスタンス化経路はテンプレートのインスタンス化起点から構築していきます。そのグラフ上のあるテンプレートにおいてのインスタンス化経路はそのテンプレートの定義を終端として、そこから起点までを逆に辿った経路になります。
つまり、経路が分岐しているときにその分岐先の経路上からお互いの経路が参照可能になるわけではありません。

また、経路と言いつつ参照可能な宣言が決まるのはその経路上の点であるインスタンス化地点と呼ばれるあるポイントにおいてであり、重要なのはそのインスタンス化地点の方です。

なので、規格においてはインスタンス化地点に着目し、インスタンス化地点の集まりとしての インスタンス化コンテキストinstantiation context)によってインスタンス化経路は説明されています。

インスタンス化地点は基本的にはそのままの意味で、テンプレートが実体化されるソースコード上の点の事です。テンプレートの全てのテンプレートパラメータが確定するポイントの事で、テンプレートを使用した所とほぼ同じ意味です。

それに加えて、(メンバ)関数テンプレート及びクラステンプレートのメンバ関数(静的含む)は、次のどちらかをもう一つのインスタンス化地点として持ちます

  • インスタンス化地点がプライベートモジュールフラグメントの外にある場合、その翻訳単位内のプライベートモジュールフラグメントの直前の地点
    • プライベートモジュールフラグメントが無い(もしくはモジュール単位でない)場合は翻訳単位の末尾
  • インスタンス化地点がプライベートモジュールフラグメントの中にある場合、その翻訳単位の末尾

そして、インスタンス化コンテキストはそれらの地点に加えて次のように決定される地点の集まりとして定義されます

  1. あるテンプレートT1インスタンス化地点が別のテンプレートT2の中にあり、T2インスタンス化に伴ってT1インスタンス化されるときのインスタンス化コンテキストは以下の両方を含む
    • T2インスタンス化コンテキスト
    • T1がモジュールMのインターフェース単位で定義されており、Mのインターフェース単位内部でインスタンス化されていないとき、Mのプライマリインターフェース単位の末尾(プライベートモジュールフラグメントがあるならその直前)
  2. default指定された特殊メンバ関数の定義内で暗黙的にインスタンス化されるテンプレートのインスタンス化コンテキストは、そのdefault指定された特殊メンバ関数インスタンス化コンテキスト
  3. クラスの特殊メンバ関数が暗黙に定義されるとき、そのインスタンス化コンテキストは以下の両方を含む
    • クラス定義のインスタンス化コンテキスト(通常1点)
    • 特殊メンバ関数の暗黙定義のきっかけとなった構文からのインスタンス化コンテキスト
      • クラスの特殊メンバ関数odr-usedされるときに暗黙の定義がなされる。そのodr-usedしている構文のこと(C++20以降実は正しくない)
  4. 上記に当てはまらないテンプレートのインスタンス化コンテキストは、そのテンプレートのインスタンス化地点
    • 他のテンプレートとは無関係に独立してインスタンス化した場合など
  5. それ以外のケースの場合、プログラム内のある地点でのインスタンス化コンテキストはその地点を含む

あるテンプレートのインスタンス化においては、このように決定されたインスタンス化コンテキスト内の各点で可視・到達可能な宣言がそのまま可視・到達可能となります。
そして、これをテンプレートの定義点から順番に並べたものがインスタンス化経路となります。

なお、インスタンス化コンテキスト内の各点でODRに違反してはいないが同じ宣言に対する複数の異なる定義が見つかる可能性があります。そうなった場合はill-formedなのですが、コンパイルエラーにはならない可能性があります。すなわち未定義動作の世界・・・

規格書より、単純なサンプルコード。

///X.h
struct X { 
  int n;
};

X operator+(X x1, X x2) {
  return {x1.n + x2.n};
}


///moduleF.cpp
export module F;

export template<typename T>
void f(T t) {
  t + t;  //Xに対する二項+演算子はここでは可視でも到達可能でもない
}


///moduleM.cpp
module;

#include "X.h"  //クラスXの定義とXに対する二項+演算子が可視になる

export module M;
import F;

void g(X x) {
  f(x); //ok、モジュールFのf()がインスタンス化される
        //Xのoperator+はインスタンス化コンテキストで可視である
        //この場合はここの呼びだし地点で可視
}

インスタンス化コンテキスト決定の例。

///Ohtermodule.cpp(プライマリインターフェース単位
export module Other;

export template<typename T>
auto f(T* t) -> decltype(T->n) {
  return t->n;
}

struct S;

int use_f1(S* s) {
  return f(s);  //ng
  /*
  f<S>()のインスタンス化コンテキストは以下の点
  0. f<S>()の定義点
  1. この呼び出し地点
  2. この翻訳単位内プライベートモジュールフラグメント直前
  クラスSの定義はプライベートモジュールフラグメント内にあり、どの点からも可視でも到達可能でもない
  */
}

module : private; //これをコメントアウトするとuse_f1()はコンパイルできる

int use_f2(S* s) {
  return f(s);  //ok
  /*
  f<S>()のインスタンス化コンテキストは以下の点
  0. f<S>()の定義点
  1. この呼び出し地点
  2. この翻訳単位(Ohtermodule.cpp)末尾
  クラスSの定義は2の点から可視であるので、0の定義点からも可視かつ到達可能となる
  */
}

struct S {
  int n = 10;
};


///Mymodule.cpp(プライマリインターフェース単位
export module Mymodule;
import Other;

export template<typename T, typename U>
T* in_f(T* t, U* u) {
  t->n += f(u);  //u.nをt.nに足しこむ
  /*
  ここでのf<T>()のインスタンス化コンテキストは以下の点
  0. f<T>()の定義点(Ohtermodule.cpp内)
  1. この呼び出し地点
  2. in_f<T>()のインスタンス化コンテキスト(複数点)
  3. in_fがこのファイル以外でインスタンス化されるとき、この翻訳単位(Mymodule.cpp)末尾
  型引数Tの実引数の定義は、ここのどこかで可視であれば0の定義点から可視かつ到達可能
  */
  return t;
}

//宣言のみ
struct S2;

double use_f3(S2* s) {
  return f(s);  //ng
  /*
  f<S2>()のインスタンス化コンテキストは以下の点
  0. f<S2>()の定義点(Ohtermodule.cpp内)
  1. この呼び出し地点
  2. この翻訳単位(Mymodule.cpp)末尾
  クラスS2の定義は実装単位内にあり、どの点からも可視でも到達可能でもない
  */
}

export struct C {
  unsigned short n = 80;
};


///Mymodule_impl.cpp(実装単位
module Mymodule;

double use_f4(S2* s) {
  return f(s);  //ok
  /*
  f<S2>()のインスタンス化コンテキストは以下の点
  0. f<S2>()の定義点(Ohtermodule.cpp内)
  1. この呼び出し地点
  2. この翻訳単位(Mymodule_impl.cpp)末尾
  クラスS2の定義は2の点から可視であるので、0の定義点からも可視かつ到達可能となる
  */
}

struct S2 {
  double n = 1.0;
};


///main.cpp
import Myodule;

struct S3;

S3* use_in_f(S3* s, C* c) {
  return in_f(ss, c); //ok
  /*
  in_f<S3, C>()のインスタンス化コンテキストは以下の点
  0. in_f<S3, C>()の定義点(Ohtermodule.cpp内)
  1. この呼び出し地点
  2. この翻訳単位(main.cpp)末尾
  in_f<S3, C>()定義内では1及び2の点からCの定義が、2の点からS3の定義がそれぞれ可視となる
  
  その内側のf<C>()のインスタンス化コンテキストは上記を含んだ以下となる
  0. f<C>()の定義点(Ohtermodule.cpp内)
  1. in_f<S3, C>()内の呼び出し地点
  2. in_f<S3, C>()のインスタンス化コンテキスト
    0. in_f<S3, C>()の定義点(Mymodule.cpp内)
    1. この呼び出し地点
    2. この翻訳単位(main.cpp)末尾
  3. Mymodule.cpp末尾
  このうち、2.1, 2.2, 3の各点からクラスCの同一の定義が可視となるので、f<C>()の定義点からもCの定義が可視となる
  */
}

struct S3 {
  unsigned short n = 443;
};

int main() {
  S3 s{};
  C c{};

  S3 s3 = use_in_f(&s, &c); //ok
}

テンプレートのインスタンス化時にプライベートモジュールフラグメント内部へ侵入するには、そのテンプレートのインスタンス化がプライベートモジュールフラグメント内部で行われている必要があります。
これは、プライベートモジュールフラグメントに対応する(複数ファイル時)概念である実装単位においても同様です(実装パーティションの場合はインポートしてしまうという手もあります)。

推移的にインポートされたグローバルモジュールフラグメント・ヘッダーユニット

あるインスタンス化地点において、推移的にインポートされているグローバルモジュールフラグメントおよびヘッダーユニット内の宣言が可視及び到達可能となるかどうかは未規定であり、処理系に一任されています。

///S.hpp
struct S { 
  void f(); //実装略
};


///moduleB.cpp
module;

//グローバルモジュールフラグメント内宣言、モジュールBからのみ可視
#include "S.hpp"

export module B;

void use_s(const S& s) {
  s.f();
}


///moduleC.cpp
export module C;

import B;  //モジュールBのインポート(not エクスポート)

export template<typename U>
void h(const U &u) {
  u.f();
}

///main.cpp
import C; //モジュールBは推移的にインポートされている

struct S;

void q(const S& s) {
  h(s);
}

int main() {
}

この例では、main.cppからはクラスSの定義が到達可能ではないですが、インポートしているモジュールCから推移的にインポートされているモジュールBでは定義が可視であり到達可能となります。

しかし、Sの定義はB内部のグローバルモジュールフラグメント内にあり、グローバルモジュールフラグメント内の宣言が推移的にインポートされた翻訳単位から到達可能となるかは未規定(実装依存)とされています。ただし、そのような宣言は可視でるときは到達可能となります。

この場合、Sの宣言はmain.cpp内では可視ですがモジュールC内では可視ではなく、インスタンス化コンテキスト全体としてみればSの宣言は可視となります。しかし、それによって推移的なグローバルモジュールフラグメント内宣言が到達可能となるかは規定されず実装依存となります。

もう一つ例を見てみましょう。

//stuff.cpp
export module stuff;

export template<typename T, typename U>
void foo(T, U u) { 
  auto v = u;
}

export template<typename T, typename U>
void bar(T, U u) {
  auto v = *u;
}

//m1.cpp
export module M1;
import "defn.h";        // struct X {};の宣言と定義がある
import stuff;

export template<typename T>
void f(T t) {
  X x;
  foo(t, x);
}

//m2.cpp
export module M2;
import "decl.h";        // struct X;の宣言のみがある
import stuff;

export template<typename T>
void g(T t) {
  X *x;
  bar(t, x);
}

//Translation unit #4:
import M1;
import M2;

void test() {
  f(0); //ok
  g(0); //未規定
}

f(0)の呼び出しは有効であり何の問題もありません。

g(0)の呼び出しが有効かどうかは未規定であり、それはSの定義に到達可能かどうかが未規定であることによります。

g(0)の呼び出しにまつわるインスタンス化コンテキストは以下の点が含まれています。

  1. モジュールstuffの末尾
  2. モジュールM2の末尾
  3. g(0)の呼び出し地点

このうち、Sの宣言は2番目の地点(モジュールM2の末尾)からは可視ですが、定義はどこからも可視ではありません。
ただし、3番目の地点(main.cpp内)からはM1のインポートを通じてSの定義はヘッダーユニットから推移的にインポートされており、これに到達可能となるかは未規定です。 そのため、このインスタンス化コンテキスト全体としてSの定義が到達可能となるかも未規定となります。

どちらのケースも実装はこれを到達可能としても良いことになっています。ポータブルなコードを書くのであれば、これに依存しないように気を付ける必要があるかもしれません。

ADLとモジュールとテンプレートと

モジュール時代においてもADLは使用可能でほぼ従来通りに動作します。
ただ、モジュールに対してADLは以下のように少し深めの探索を行います

  • テンプレートのインスタンス化時にはそのインスタンス化コンテキスト内宣言を探索する(依存名に対して)
    • その際、別の翻訳単位でグローバルモジュールに属す形で宣言され、内部リンケージを持つか破棄されている宣言は無視される
  • 名前付きモジュールMのインターフェース内の名前空間を探索する時、関連エンティティと同じ名前空間内にある(別の名前空間に包まれていない)Mに属する宣言はすべて可視となる
    • inline名前空間になら包まれていてもいい(宣言を囲む最も内側の非inline名前空間に関連エンティティがあればいい)
    • 関連エンティティとは、ADLの足掛かりとなった実引数(の型)のこと
///Str.hpp(ヘッダーファイル
#include <iostream>

namespace STR {
  struct Str {
    const char* str = "hello world";
  };

  static void out(const Str& str) {
    std::cout << str.str << std::endl;
  }

  void out(const Str* str) {
    std::cout << str->str << std::endl;
  }
}


///Mymodule.cpp
module;

#include "Str.hpp"  //グローバルモジュールに属する

export module Mymodule;

namespace Mymodule {

  export struct S {
    int n = 10;
  };

  export int f(S s) {
    return s.n;
  }

  inline namespace Detail {
    export template<typename T>
    int g(S s, T t) {
      return s.n + int(t);
    }
  }

  namespace Inner {
    export int h(S s) {
      return s.n + 10;
    }
  }

}

export template<typename T>
auto f(T t1, T t2) {
  return get_n(t1) + get_n(t2);
}

export using string = STR::Str; //STR::Strは参照された

export template<typneame Str>
void print_ptr(const Str& str){
  out(&str);
}

export template<typneame Str>
void print_ref(const Str& str){
  out(str);
}
//STR::out(Str*)は参照されておらず破棄された


///main.cpp
import Mymodule;

#include "Str.hpp"  //グローバルモジュールに属する

namespace Main {
  struct C {
    unsigned short n = 80;

    operator int() const {
      return int(n);
    }
  };

  unsigned short get_n(C c) {
    return c.n;
  }
}

int main() {
  Mymodule::S s{100};
  Main::C c{};

  int n = f(s);     //ok、Sの定義名前空間で見つかる
  int m = g(s, c);  //ok、Sの定義名前空間で見つかる(inline名前空間)
  int l = h(s);     //ng、Sの定義名前空間に無い(さらに内側にある)
  auto s = f(c, c); //ok、エクスポートされているテンプレートf<C>()を呼び出す
                    //f<C>()内からはインスタンス化コンテキストに対するADLによりget_n()が見つかる
  
  string str{};     //ok
  print_ptr(str);   //ng、out(Str*)は破棄されているためADLで見つからない
  print_ref(str);   //ng、out(const Str&)は内部リンケージを持つためADLで見つからない
}

ADLで可視になるとはいっても、別の翻訳単位にある場合は外部リンケージを持つものしか呼び出すことは出来ません。

規格書より、少し複雑なサンプルコード。

///moduleM.cpp(Mのインターフェース
export module M;

namespace R {
  export struct X {};

  export void f(X);
}

namespace S {
  export void f(X, X);
}


///moduleN.cpp(Nのインターフェース
export module N;
import M;

export R::X make();

namespace R {
  static int g(X);
}

export template<typename T, typename U>
void apply(T t, U u) {
  f(t, u);
  g(t);
}

///moduleQ.cpp(Qの実装単位
module Q;
import N;

namespace S {
  struct Z { 
    template<typename T>
    operator T();
  };
}

void test() {
  auto x = make();  //ok、decltype(x) = R::XはモジュールMにあり可視ではないが名前を参照していないのでok
  R::f(x);          //ng、名前空間RもR::f()も可視では無い
  f(x);             //ok、R::f()がADLによってモジュールMのインターフェースから見つかる
  f(x, S::Z());     //ng、名前空間Sは探索の対象だがモジュールM内まで及ばず、S::f()は見つからない
  apply(x, S::Z()); //ok、S::f()はインスタンス化コンテキスト内で可視
                    //R::g()は内部リンケージを持つが、apply()定義内からは呼び出し可能
}

この例から分かるように、名前空間は翻訳単位を超えて定義できます(名前空間定義そのものはグローバルモジュールに属している)がADLはそれを超えるとは限りません。ただし、3番目の例のように型が直接所属する名前空間は翻訳単位を飛び越えて探索されます。

4番目の例のように、直接の名前空間になく、その翻訳単位から見える名前空間(この場合S)内にも見当たらない場合、翻訳単位を飛び越えて可視でない名前空間定義を探索はしません。

5番目の例では、モジュールN内ではM名前空間Sが可視であり、インスタンス化コンテキスト内でQ名前空間Sが可視になります。そのため、applyインスタンス化にあたっては両方の翻訳単位の名前空間Sが探索され、S::f()を見つけることができます。

規格書より、ADLとテンプレートによるモジュール内部への侵入サンプル。

//Module interface unit of Std:
export module Std;

export template<typename Iter>
void indirect_swap(Iter lhs, Iter rhs)
{
  swap(*lhs, *rhs); // このswapは非修飾名探索では見つからない、見つかるとしたらADLでのみ
}


//Module interface unit of M:
export module M;
import Std;

//共に実装省略
struct S { /* ...*/ };
void swap(S&, S&);      // #1

void f(S* p, S* q)
{
  indirect_swap(p, q);  //インスタンス化コンテキストを探索するADLを介して、 #1が見つかる
                        //indirect_swapはインスタンス化コンテキストにこの点とモジュール内の定義点を含む
                        //ここの点においてSに対するswapは可視であるのでindirect_swap内からのADLにおいても可視
}

この様に、モジュール内部でカスタマイゼーションポイントを提供し、それを使用するにはテンプレートとADLを用いる必要があります。

おまけ、モジュール史(2004 - 2019)

参考文献

この記事のMarkdownソース