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

引題

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

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

的問(wèn)題。然后，就貼出了如下的一段例程代碼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ì)序列的最大長(zhǎng)度自然不能超過(guò)128。否則，突破上限，編譯失?。? 其次，尾遞歸優(yōu)化是運(yùn)行時(shí)壓縮函數(shù)調(diào)用棧的技術(shù)手段，卻做不到編譯時(shí)抑制宏調(diào)用棧的膨脹。所以，巧用#![recursion_limit="…"]元屬性強(qiáng)制調(diào)高宏遞歸深度上限很可能會(huì)導(dǎo)致編譯器棧溢出。 由此，如果僅追求快速繞過(guò)問(wèn)題，那最經(jīng)濟(jì)實(shí)惠的作法是：在每次宏遞歸期間，多統(tǒng)計(jì)幾個(gè)token例程2（而不是一次一個(gè)）。從算數(shù)上，將總遞歸次數(shù)降下來(lái)，和使計(jì)數(shù)更長(zhǎng)的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)本兼治地解決問(wèn)題，將遞歸調(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ā)編譯器對(duì)數(shù)組字面量的類(lèi)型推導(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ù)組長(zhǎng)度被編入了數(shù)據(jù)類(lèi)型定義內(nèi)。
4. 泛型常量參數(shù)從數(shù)據(jù)類(lèi)型定義中提取出數(shù)組長(zhǎng)度值，并作為序列長(zhǎng)度返回。

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

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

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

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

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

泛型常量參數(shù)

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

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

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

泛型參數(shù)的分類(lèi)

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

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

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

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

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

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

其次，就“聲明和使用”而言，泛型常量形參允許僅被聲明，而不被使用。對(duì)另兩種泛型參數(shù)而言，這卻會(huì)導(dǎo)致編譯失敗例程5。 最后，泛型常量實(shí)參的trait實(shí)現(xiàn)不會(huì)因?yàn)楦F舉了全部備選形參值而自動(dòng)過(guò)渡給泛型常量形參。如下例程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)類(lèi)型#3
• 結(jié)構(gòu)體字段 或 綁定變量的數(shù)據(jù)類(lèi)型#4。比如，編譯時(shí)參數(shù)化數(shù)組長(zhǎng)度。
• 結(jié)構(gòu)體字段 或 綁定變量的值#5

上述列表內(nèi)的#1 ~ #5，可在下面例程8源碼內(nèi)找到對(duì)應(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ù)類(lèi)型 —— 編譯時(shí)參數(shù)化數(shù)組長(zhǎng)度 // #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ù)類(lèi)型 —— 編譯時(shí)參數(shù)化數(shù)組長(zhǎng)度 ); impl<const N4: usize> Trait for Foo { type Output = [usize; N4]; // #3 關(guān)聯(lián)類(lèi)型 —— 編譯時(shí)參數(shù)化數(shù)組長(zhǎng)度 } 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)變量，無(wú)論是作為類(lèi)型定義的一部分，還是值#1
• 隔層使用。比如，在子函數(shù)內(nèi)引用由外層函數(shù)聲明的泛型常量形參#2。除了子函數(shù)，該規(guī)則也適用于在函數(shù)體內(nèi)定義的
  • 結(jié)構(gòu)體#3
  • 類(lèi)型別名#4

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

fn main() { fn outer<const N: usize>(input: usize) { // 泛型常量參數(shù)【不】可用于函數(shù)體內(nèi)的 // #1 常量定義 // - 既不能定義類(lèi)型 const BAD_CONST: [usize; N] = [1; N]; // - 既不能定義值 const BAD_CONST: usize = 1 + N; // #1 靜態(tài)變量定義 // - 既不能定義類(lè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ù)聲明的 // 泛型常量形參，無(wú)論是將其作為 // 變量類(lèi)型，還是常量值。 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 類(lèi)型別名內(nèi)不能引用外層函數(shù)聲明的 // 泛型常量形參。 type BadAlias = [usize; N]; // 相反，需要給類(lèi)型別名重新聲明泛型常量參數(shù) type BadAlias<const N: usize> = [usize; N]; } } 其次，泛型常量實(shí)參不接受包含了泛型常量形參的常量表達(dá)式例程10。

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

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

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

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

于是，循環(huán)替換設(shè)計(jì)模式Repetition Replacement(RR)與元變量表達(dá)式${ignore(識(shí)別符名)}都是被用來(lái)改善【宏循環(huán)結(jié)構(gòu)】的使用體驗(yàn)，以允許Rustacean對(duì)循環(huán)結(jié)構(gòu)中的循環(huán)重復(fù)項(xiàng)“宣而不用” —— 既遍歷token tree序列，同時(shí)又棄掉每個(gè)具體的token元素，最后還生成一個(gè)等長(zhǎng)的單位數(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í)別符名)}是前者的語(yǔ)法糖，允許Rustacean少敲幾行代碼。但因?yàn)樵兞勘磉_(dá)式是試驗(yàn)性的新語(yǔ)法，所以需要開(kāi)啟對(duì)應(yīng)的feature-gate開(kāi)關(guān)#![feature(macro_metavar_expr)]才能被使用。例程16

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

結(jié)束語(yǔ)

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

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

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