淺聊泛型常量參數(shù)Const Generic

引題

最近有網(wǎng)友私信我討論：若使用規(guī)則宏編譯時(shí)統(tǒng)計(jì)token tree序列的長度，如何繞開由宏遞歸自身局限性造成的：

• 被統(tǒng)計(jì)序列不能太長
• 編譯延時(shí)顯著拖長

的問題。然后，就貼出了如下的一段例程代碼1：

fn main() { macro_rules! count_tts { ($_a:tt $($tail: tt)*) => { 1_usize + count_tts!($($tail)*) }; () => { 0_usize }; } assert_eq!(10, count_tts!(,,,,,,,,,,)); }

嚯！這段短小精悍的代碼餒餒地演示了Incremental TT Muncher設(shè)計(jì)模式的精髓。贊！

首先，宏遞歸深度是有極限的（默認(rèn)是128層）。所以，若每次遞歸僅新統(tǒng)計(jì)一個(gè)token，那么被統(tǒng)計(jì)序列的最大長度自然不能超過128。否則，突破上限，編譯失敗！ 其次，尾遞歸優(yōu)化是運(yùn)行時(shí)壓縮函數(shù)調(diào)用棧的技術(shù)手段，卻做不到編譯時(shí)抑制宏調(diào)用棧的膨脹。所以，巧用#![recursion_limit="…"]元屬性強(qiáng)制調(diào)高宏遞歸深度上限很可能會(huì)導(dǎo)致編譯器棧溢出。 由此，如果僅追求快速繞過問題，那最經(jīng)濟(jì)實(shí)惠的作法是：在每次宏遞歸期間，多統(tǒng)計(jì)幾個(gè)token例程2（而不是一次一個(gè)）。從算數(shù)上，將總遞歸次數(shù)降下來，和使計(jì)數(shù)更長的token tree序列成為可能。

fn main() { // 這代碼看著就“傻乎乎的”。 macro_rules! count_tts { ($_a: tt $_b: tt $_c: tt $_d: tt $_e: tt $_f: tt // 一次遞歸統(tǒng)計(jì) 6 個(gè)。 $($tail: tt)*) => { 6_usize + count_tts!($($tail)*) }; ($_a: tt $_b: tt $_c: // 一次遞歸統(tǒng)計(jì) 3 個(gè)。 tt $($tail: tt)*) => { 3_usize + count_tts!($($tail)*) }; ($_a: tt // 一次遞歸統(tǒng)計(jì) 1 個(gè)。 $($tail: tt)*) => { 1_usize + count_tts!($($tail)*) }; () => { 0_usize }; // 結(jié)束了，統(tǒng)計(jì)完成 } println!("token tree 個(gè)數(shù)是 {}", count_tts!(,,,,,,,,,,)); } 倘若要標(biāo)本兼治地解決問題，將遞歸調(diào)用變形成循環(huán)結(jié)構(gòu)才是正途，因?yàn)檠h(huán)本身不會(huì)增加調(diào)用棧的深度。這涵蓋了：

1. 宏循環(huán)結(jié)構(gòu)將token tree序列變形成數(shù)組字面量。
2. 常量函數(shù)調(diào)用觸發(fā)編譯器對數(shù)組字面量的類型推導(dǎo)。
3. 因?yàn)?code style="background:rgb(251,241,199);font-family:'Source Code Pro', 'Fira Code', Menlo, Monaco, Consolas, 'DejaVu Sans Mono', Inconsolata, 'Courier New', monospace;">rust數(shù)組在編譯時(shí)明確大小，所以數(shù)組長度被編入了數(shù)據(jù)類型定義內(nèi)。
4. 泛型常量參數(shù)從數(shù)據(jù)類型定義中提取出數(shù)組長度值，并作為序列長度返回。

全套操作被統(tǒng)稱為Array length設(shè)計(jì)模式。它帶入了兩個(gè)技術(shù)難點(diǎn)：

1. 如何觸發(fā)rustc對數(shù)組字面量的類型推導(dǎo)，和從推導(dǎo)結(jié)果中提取出數(shù)組長度信息。
2. 如何撇開遞歸的“吐吞模式”（即，吐Incremental TT Muncher和吞Push-down Accumulation），僅憑宏循環(huán)結(jié)構(gòu)，將token tree序列變形成為數(shù)組字面量。

第一個(gè)難點(diǎn)源于自rustc 1.51才穩(wěn)定的新語言特性“泛型常量參數(shù)Const Generic”。而第二個(gè)難點(diǎn)的解決就多樣化了

• 要么，采用“循環(huán)替換設(shè)計(jì)模式Repetition Replacement(RR)”
• 要么，啟用試驗(yàn)階段語言特性“元變量表達(dá)式Meta-variable Expression”

接下來，它們會(huì)被逐一地講解分析。

泛型常量參數(shù)

從rustc 1.51+起，【泛型常量參數(shù) 】允許泛型項(xiàng)（類或函數(shù)）接受常量值或常量表達(dá)式為泛型參數(shù)。根據(jù)泛型常量參數(shù)出現(xiàn)的位置不同（請見下圖例程3），它又細(xì)分為

• 泛型常量參數(shù)的形參
• 泛型常量參數(shù)的實(shí)參

下文分別將它們簡稱為“泛型常量形參”與“泛型常量實(shí)參”。

泛型參數(shù)的分類

于是，已知的泛型參數(shù)就包含有三種類型：

泛型常量參數(shù)的數(shù)據(jù)類型

可用作【泛型常量參數(shù)】的數(shù)據(jù)類型包括兩類：

• 整數(shù)數(shù)字類型：u8，u16，u32，u64，u128，usize，i8，i16，i32，i64，i128，isize
• 可數(shù)字化類型：char，bool

泛型常量參數(shù)的“怪癖”

首先，就“同名沖突”而言，若【泛型常量形參】與【類型】同名并作為另一個(gè)泛型項(xiàng)的泛型參數(shù)實(shí)參，那么rustc會(huì)優(yōu)先將該泛型參數(shù)當(dāng)作類型帶入程序上下文。多數(shù)情況下，這會(huì)造成程序編譯失敗。解決方案是使用塊表達(dá)式{...}包裝泛型常量參數(shù)，以向rustc標(biāo)注此同名參數(shù)是泛型常量參數(shù)而不是類型名例程4。

其次，就“聲明和使用”而言，泛型常量形參允許僅被聲明，而不被使用。對另兩種泛型參數(shù)而言，這卻會(huì)導(dǎo)致編譯失敗例程5。 最后，泛型常量實(shí)參的trait實(shí)現(xiàn)不會(huì)因?yàn)楦F舉了全部備選形參值而自動(dòng)過渡給泛型常量形參。如下例程6（左），即便泛型項(xiàng)struct Foo顯示地給泛型常量形參B的每個(gè)可能的（實(shí)參）值true / false都實(shí)現(xiàn)的同一個(gè)trait Bar，編譯器也不會(huì)“聰明地”歸納出該trait Bar已經(jīng)被此泛型項(xiàng)的泛型常量形參充分實(shí)現(xiàn)了，因?yàn)榫幾g器可不會(huì)“歸納法”方法論（不確定chatGPT是否能做到？）。相反，每個(gè)實(shí)參上的trait實(shí)現(xiàn)都被視作不相關(guān)的個(gè)例。正確地作法是：泛型項(xiàng)必須明確地給泛型常量形參實(shí)現(xiàn)trait例程7（右）。

泛型常量參數(shù)的適用位置

泛型常量參數(shù)原則上可出現(xiàn)于常量項(xiàng)適用的全部位置，包括但不限于：

• 運(yùn)行時(shí)求值表達(dá)式#1— 模糊了編譯時(shí)泛型參數(shù)與運(yùn)行時(shí)值之間的界限。
• 常量表達(dá)式#2
• 關(guān)聯(lián)常量#2
• 關(guān)聯(lián)類型#3
• 結(jié)構(gòu)體字段 或 綁定變量的數(shù)據(jù)類型#4。比如，編譯時(shí)參數(shù)化數(shù)組長度。
• 結(jié)構(gòu)體字段 或 綁定變量的值#5

上述列表內(nèi)的#1 ~ #5，可在下面例程8源碼內(nèi)找到對應(yīng)的代碼行。

use rand::{thread_rng, Rng}; fn main() { fn foo1<const N1: usize>(input: usize) { // 在泛型函數(shù)內(nèi)，泛型常量參數(shù)的形參可用于 let sum = 1 + N1 * input; // #1 運(yùn)行時(shí)求值的表達(dá)式 let foo = Foo([input; N1]); // #5 結(jié)構(gòu)體字段的值 let arr: [usize; N1] = [input; N1]; // #4 綁定變量的數(shù)據(jù)類型 —— 編譯時(shí)參數(shù)化數(shù)組長度 // #5 綁定變量的值 println!("運(yùn)行時(shí)表達(dá)式：{sum}, 元組結(jié)構(gòu)體： {foo:?}, 數(shù)組： {arr:?}"); } trait Trait<const N2: usize> { const CONST: usize = N2 + 4; // #2 關(guān)聯(lián)常量 + 常量表達(dá)式 type Output; } #[derive(Debug)] struct Foo<const N3: usize>( [usize; N3] // #4 結(jié)構(gòu)體字段的數(shù)據(jù)類型 —— 編譯時(shí)參數(shù)化數(shù)組長度 ); impl<const N4: usize> Trait for Foo { type Output = [usize; N4]; // #3 關(guān)聯(lián)類型 —— 編譯時(shí)參數(shù)化數(shù)組長度 } let mut rng = thread_rng(); foo1::<2>(rng.gen_range::<usize, _>(1..10)); foo1::<{1 + 2}>(rng.gen_range::<usize, _>(1..10)); const K: usize = 3; foo1::(rng.gen_range::<usize, _>(1..10)); foo1::<{K * 2}>(rng.gen_range::<usize, _>(1..10)); }

泛型常量參數(shù)的不適用位置

首先，泛型常量形參不能：

• 定義常量和靜態(tài)變量，無論是作為類型定義的一部分，還是值#1
• 隔層使用。比如，在子函數(shù)內(nèi)引用由外層函數(shù)聲明的泛型常量形參#2。除了子函數(shù)，該規(guī)則也適用于在函數(shù)體內(nèi)定義的
  • 結(jié)構(gòu)體#3
  • 類型別名#4

上述列表內(nèi)的#1 ~ #4，可在下面例程9源碼內(nèi)找到對應(yīng)的代碼行。

fn main() { fn outer<const N: usize>(input: usize) { // 泛型常量參數(shù)【不】可用于函數(shù)體內(nèi)的 // #1 常量定義 // - 既不能定義類型 const BAD_CONST: [usize; N] = [1; N]; // - 既不能定義值 const BAD_CONST: usize = 1 + N; // #1 靜態(tài)變量定義 // - 既不能定義類型 static BAD_STATIC: [usize; N] = [N + 1; N]; // - 既不能定義值 static BAD_STATIC: usize = 1 + N; fn inner(bad_arg: [usize; N]) { // #2 在子函數(shù)內(nèi)不能引用外層函數(shù)聲明的 // 泛型常量形參，無論是將其作為 // 變量類型，還是常量值。 let bad_value = N * 2; } // #3 結(jié)構(gòu)體內(nèi)也不能引用外層函數(shù)聲明的 // 泛型常量形參。 struct BadStruct([usize; N]); // 相反，需要給結(jié)構(gòu)體重新聲明泛型常量參數(shù) struct BadStruct<const N: usize>([usize; N]); // #4 類型別名內(nèi)不能引用外層函數(shù)聲明的 // 泛型常量形參。 type BadAlias = [usize; N]; // 相反，需要給類型別名重新聲明泛型常量參數(shù) type BadAlias<const N: usize> = [usize; N]; } } 其次，泛型常量實(shí)參不接受包含了泛型常量形參的常量表達(dá)式例程10。

但是，泛型常量實(shí)參并不拒絕接受

• 獨(dú)立泛型常量形參例程11
• 不包含泛型常量形參的普通常量表達(dá)式例程12 題外話，不確定這么翻譯該術(shù)語lookahead是否正確。我借鑒了 @余晟 在《精通正則表達(dá)式》一書中對此詞條的譯文。
  • 被用作泛型常量實(shí)參的常量表達(dá)式必須被包裝在塊表達(dá)式{...}內(nèi)。避免編譯器在解析AST過程中陷入正向環(huán)視lookahead的無限循環(huán)中。

數(shù)組重復(fù)表達(dá)式與泛型常量參數(shù)

數(shù)組重復(fù)表達(dá)式[repeat_operand; length_operand]是數(shù)組字面量的一種形式。在數(shù)組重復(fù)表達(dá)式中，泛型常量形參

• 雖然既可用于左repeat操作數(shù)位置，也可用于右length操作數(shù)位置例程13
• 但在右length操作數(shù)位置上，泛型常量形參只能獨(dú)立出現(xiàn)例程14，而不能作為常量表達(dá)式的一部分 —— 等同于泛型常量實(shí)參的限制。

回到序列計(jì)數(shù)問題

類似于解析幾何中的“投影”方法，通過將高維物體（token tree序列）投影于低維平面（數(shù)組），以主動(dòng)舍棄若干信息項(xiàng)（每個(gè)token的具體值與數(shù)據(jù)類型）為代價(jià)，突出該物體更有價(jià)值的信息內(nèi)容（序列長度），便可降低從復(fù)雜結(jié)構(gòu)中摘取特定關(guān)注信息項(xiàng)的合計(jì)復(fù)雜度。這套“降維算法”帶來的啟發(fā)就是：

1. 既然讀取數(shù)組長度是簡單的，那為什么不先將token tree序列變形為數(shù)組呢？
   1. 答：投影token tree序列為數(shù)組
2. 既然token tree序列的內(nèi)容細(xì)節(jié)不被關(guān)注，那為什么還要糾結(jié)于數(shù)組的數(shù)據(jù)類型與填充值呢？全部充滿unit type豈不快哉！
   1. 再答：投影token tree序列為單位數(shù)組[(); N]。僅數(shù)組長度對我們有價(jià)值。

于是，循環(huán)替換設(shè)計(jì)模式Repetition Replacement(RR)與元變量表達(dá)式${ignore(識(shí)別符名)}都是被用來改善【宏循環(huán)結(jié)構(gòu)】的使用體驗(yàn)，以允許Rustacean對循環(huán)結(jié)構(gòu)中的循環(huán)重復(fù)項(xiàng)“宣而不用” —— 既遍歷token tree序列，同時(shí)又棄掉每個(gè)具體的token元素，最后還生成一個(gè)等長的單位數(shù)組[(); N]。否則，未被使用的“循環(huán)重復(fù)項(xiàng)”會(huì)導(dǎo)致error: attempted to repeat an expression containing no syntax variables matched as repeating at this depth的編譯錯(cuò)誤。

• 循環(huán)替換設(shè)計(jì)模式Repetition Replacement(RR)是以在宏循環(huán)體內(nèi)插入一層“空轉(zhuǎn)”宏調(diào)用，消費(fèi)掉consuming未被使用的“循環(huán)重復(fù)項(xiàng)”例程15
• 元變量表達(dá)式${ignore(識(shí)別符名)}是前者的語法糖，允許Rustacean少敲幾行代碼。但因?yàn)樵兞勘磉_(dá)式是試驗(yàn)性的新語法，所以需要開啟對應(yīng)的feature-gate開關(guān)#![feature(macro_metavar_expr)]才能被使用。例程16

然后，常量函數(shù)調(diào)用和函數(shù)形參觸發(fā)編譯器對單位數(shù)組字面量的類型推導(dǎo)。 接著，泛型常量形參從被推導(dǎo)出的數(shù)據(jù)類型定義內(nèi)提取出數(shù)組長度信息。 最后，將泛型常量形參作為常量函數(shù)的返回值輸出。 上圖，一圖抵千詞。

結(jié)束語

除了前文提及的【宏遞歸法】與Array Length設(shè)計(jì)模式，統(tǒng)計(jì)token tree序列長度還有

• Slice Length設(shè)計(jì)模式
  • 原理類似Array Length，但調(diào)用數(shù)組字面量的pub const fn len(&self) -> usize成員方法讀取長度值（而不是依賴類型推導(dǎo)和泛型參數(shù)提?。?。
• 枚舉計(jì)數(shù)法
  • 規(guī)則宏將token tree序列變形為“枚舉類”（而不是數(shù)組字面量），再由最后一個(gè)枚舉值的分辨因子discriminant值加1獲得序列長度。
  • 但，缺點(diǎn)也明顯。比如，token tree序列內(nèi)不能包含rust語法關(guān)鍵字與重復(fù)項(xiàng)。
• 比特計(jì)數(shù)法
  • 典型的算法優(yōu)化。從數(shù)學(xué)層面，將程序復(fù)雜度從O(n)降到O(log(n))。有些復(fù)雜，回頭單獨(dú)寫一篇文章分享之。

【規(guī)則宏】與【泛型參數(shù)】皆是rust編程語言提供的業(yè)務(wù)功能開發(fā)利器。宏循環(huán)結(jié)構(gòu)與泛型常量參數(shù)僅只是它們的冰山一角。此文既匯總分享與網(wǎng)友的討論成果，也對此話題拋磚引玉。希望有機(jī)會(huì)與路過的神仙哥哥和仙女妹妹們更深入地交流相關(guān)技術(shù)知識(shí)點(diǎn)與實(shí)踐經(jīng)驗(yàn)。 審核編輯：湯梓紅