The `constexpr` Problem That Took Me 5 Years To Fix!

橫跨五年，穿越時空的問題，全靠神秘江湖一點訣瞬間爆破!

太勁爆了!

所以到底是啥問題?

假設今天我們想要在編譯期使用一個const char*來生成一個std::string(通常會要做一些處理)，這件事情可行嗎?

從理論上應該是可行吧，畢竟constexpr std::string這東西已經喊了N百年了，總該實裝了吧
- 的確是實裝了沒錯，但沒有你想的那麼簡單
奇怪的是，我們可以編譯期求constexpr std::string的長度，但是死活都不能變出那個std::string......

consteval auto make_string(std::string_view base, const int repeat) {
    std::string retval;
    for (int times = 0 ; times < repeat ; ++times) 
        retval += base ;

    return retval.size() ;
} // make_string()

int main () {
    constexpr auto result = make_string("hello world,", 3) ;
    std::cout << result << std::endl ;
    return 0 ;
}

執行結果會回傳36，符合預期，但是改成直接return std::string就翻車了......

consteval auto make_string(std::string_view base, const int repeat) {
    std::string retval;
    for (int times = 0 ; times < repeat ; ++times) 
        retval += base ;

    return retval ;
} // make_string()

int main () {
    constexpr auto result = make_string("hello world,", 3) ;
    std::cout << result << std::endl ;
    return 0 ;
}

錯誤訊息為

1 2	error: 'make_string(std::string_view, int)(3)' is not a constant expression because it refers to a result of 'operator new' return static_cast<_Tp>(::operator new(__n sizeof(_Tp)));

refers to a result of 'operator new'，蛤? 不是都變成constexpr std::string了?

compile time的東西到底算不算個"東西"?

問題出在那? 問題出在這個"Hello world," repeat 3次的std::string，他的生成發生在compile time，問題來了
- 如果今天我們想要印出他(好比說透過std::cout)，那這個std::string勢必一定要出現在executable的某處(因為它是constexpr std::string)
- 所以我們要生成一個std::string出來，可是
  - std::string是不定長度的容器阿，想要生成一定要透過operator new這一關
- 所以問題有二
  - 不知道這個constexpr std::string要放在binary的那裡
  - 不知道該用多長的空間放它

所以一個解決問題的思路就是，不知道要放哪，那好辦我直接用一個std::array<char, 超級大>，O你娘塞爆不就解決了?

consteval auto make_string(std::string_view base, const int repeat) {
    std::string retval;
    std::array<char, 1024*1024*1024> buffer;

    for (int times = 0 ; times < repeat ; ++times) 
        retval += base ;

    std::copy(retval.begin(), retval.end(), buffer.begin());

    return buffer ;
} // make_string()

int main () {
    constexpr auto result = make_string("hello world,", 3) ;
    std::cout << std::string_view(result.begin(), result.end()) << std::endl ;
    return 0 ;
}

這確實會是一個辦法，但你仔細看出來的asm

main:
        push    rbp
        mov     edx, 1073741824
        xor     esi, esi
        push    rbx
        sub     rsp, 1073741832
        mov     rdi, rsp
        call    memset

大事不妙，我們明明就只要36 bytes的空間，居然要初始化那個超級大array，雖然縮小長度可以解決問題，但我們不禁要問

有沒有可以配置剛剛好大小的辦法呢?

還真的有，只是看起來有點廢

constexpr auto make_data(std::string_view base, const int repeat) {
    std::string retval;

    for (int times = 0 ; times < repeat ; ++times) 
        retval += base ;

    return retval ;
}

consteval auto string_length(const std::string& s) {
    return s.size();
}

template <size_t LEN>
consteval auto make_array() {
    return std::array<char, LEN>{} ;
}

template <size_t LEN>
constexpr auto make_string(const std::string& str) {
    auto buffer = make_array<LEN>() ;
    std::copy(str.begin(), str.end(), buffer.begin());

    return buffer ;
} // make_string()

int main () {
    constexpr static auto length = string_length(make_data("hello world,", 3)) ;
    constexpr auto result = make_string<length>(make_data("hello world,", 3)) ;
    std::cout << result.size() << ' ' << std::string_view(result.begin(), result.end()) << std::endl ;
    return 0 ;
}

我們做了兩次相同的make_data()，一次為了知道長度，另外一次是為了實際生成一個array，然後把東西放進去
的確array的長度剛剛好了，但我們還能不能做得更好一點?
截至目前為止我們有兩個可行的辦法
- O你娘塞爆法
- 同樣的演兩次法

各自有各自的缺陷，但似乎我們可以把這兩種方式做一個組合

constexpr auto make_data(std::string_view base, const int repeat) {
    std::string retval;

    for (int times = 0 ; times < repeat ; ++times) 
        retval += base ;

    return retval ;
}

constexpr auto make_string(const std::string& str) {
    auto buffer = std::make_pair(std::array<char, 1024*1024>{}, str.size());

    std::copy(str.begin(), str.end(), buffer.first.begin());

    return buffer ;
} // make_string()

int main () {
    constexpr auto result = make_string(make_data("hello world,", 3)) ;
    std::cout << std::string_view(result.first.begin(), result.first.begin() + result.second) << std::endl ;
    return 0 ;
}

影片中是用一個struct來記array與size，我這裡換成了一個pair，雖然不用call兩遍了，但記憶體浪費的問題還是一樣沒有改變，我們得再繼續想想辦法

接下來該怎麼辦?

做到這邊，相信大家也跟我一樣想著要是能直接寫一個constexpr std::string，就直接全劇終了，根本不會有這麼多破事

有一個很讚的方法是，用一個workaround去繞他

constexpr auto make_data(std::string_view base, const int repeat) {
    std::string retval;

    for (int times = 0 ; times < repeat ; ++times) 
        retval += base ;

    return retval ;
}

template <typename Callable>
consteval auto make_string(Callable callable) {
    // constexpr auto str = callable() ;
    std::string str = callable() ;
    auto buffer = std::array<char, callable().size()>{};

    std::copy(str.begin(), str.end(), buffer.begin());
    return buffer ;
} // make_string()

int main () {
    auto str_gen = []() {
        return make_data("hello world,", 3);
    } ;

    constexpr static auto result = make_string(str_gen) ;
    std::cout << result.size() << std::endl ;
    std::cout << std::string_view(result.begin(), result.end()) << std::endl ;
    return 0 ;
}

我們知道constexpr function裡頭的std::string只能存在於compile time，他無法逃脫這個function

另外，你從外面把string作為parameter傳進去，同樣也不會被當成constant expression

/*行不通的 兄Day*/
consteval auto make_string(const std::string& str) {
    auto buffer = std::array<char, str.size()>{}; // 卡在這一步
    std::copy(str.begin(), str.end(), buffer.begin());
    return buffer ;
} // make_string()

但很神奇的，我們可以傳一個lambda進去，只要那個lambda本身能夠在compile time被evaluate，那一切就沒毛病
- 影片中，Jason Turner還是繼續用一個大array裝data，之後再做一次shrink，我有點搞不清楚他的用意，姑且我就一步做完了，只要我們不去直接return那個std::string我們就不會翻車

Cool，如此一來基本上問題就解得差不多了，唯一只剩下main裡頭我們還要自己把array轉string_view很惱人這點

聰明的小吉可能馬上就會說:那簡單，直接在function裡頭轉string_view出來就好

template <typename Callable>
consteval auto make_string(Callable callable) {
// constexpr auto str = callable() ;
    std::string str = callable() ;
    auto buffer = std::array<char, callable().size()>{};

    std::copy(str.begin(), str.end(), buffer.begin());
    return std::string_view(buffer.begin(), buffer.end()) ;
} // make_string()

int main (int argc, char* argv[]) {
    auto str_gen = []() {
        return make_data("hello world,", 3);
    } ;

    constexpr static auto result = make_string(str_gen) ;
    std::cout << result.size() << std::endl ;
    std::cout << result << std::endl ;
    return 0 ;
}

很可惜的，並不能這樣，抱歉惹洨吉QQ
- 問題出在於轉string_view的行為相當於要實體化本來只在compile time會出現的資料
  - 要注意make_string()的範圍內都還是compile time的範圍，此時沒有任何一個物件存在
  - 一直到main裡頭的constexpr static auto result = make_string(str_gen)我們的string data才會真的現身
- 那不就無解了?
仔細想想，之所以不能把buffer轉成string_view，是因為buffer在make_string()中並不存在實體(他是一個complie time的資源)
假設buffer是一個static array的話呢?
- constexpr function裡頭寫static一直到C++23才會出來，現階段還是沒有實作好的.....
- 那不就無解了!?

make_static的奧秘

現在就差最後一部，我們必須要想點辦法變出一個static array出來，這時就要來隆重介紹此影片最精華，最魔幻，最庸人自擾(?)的手法，make_static()

template <auto DATA>
consteval const auto& make_static() {
    return DATA;
}

constexpr auto make_array(auto callable) {
    std::string str = callable();
    auto buffer = std::array<char, callable().size()>{};
    std::copy(str.begin(), str.end(), buffer.begin());
    return buffer ;
}

consteval auto make_string(auto callable) {
    constexpr auto& static_buf = make_static<make_array(callable)>() ;
    return std::string_view{static_buf.begin(), static_buf.end()} ;
} // make_string()

對，真的就這樣

根據C++標準，非型別樣版參數（Non-Type Template Argument）具有static storage duration的特性

我們真的把static array變出來了，來看看asm出來什麼

template parameter object for std::array<char, 36ul>{char [36]{(char)104, (char)101, (char)108, (char)108, (char)111, (char)32, (char)119, (char)111, (char)114, (char)108, (char)100, (char)44, (char)104, (char)101, (char)108, (char)108, (char)111, (char)32, (char)119, (char)111, (char)114, (char)108, (char)100, (char)44, (char)104, (char)101, (char)108, (char)108, (char)111, (char)32, (char)119, (char)111, (char)114, (char)108, (char)100, (char)44}}:
    .ascii  "hello world,hello world,hello world,"
main::result:
    .quad   36
    .quad   template parameter object for std::array<char, 36ul>{char [36]{(char)104, (char)101, (char)108, (char)108, (char)111, (char)32, (char)119, (char)111, (char)114, (char)108, (char)100, (char)44, (char)104, (char)101, (char)108, (char)108, (char)111, (char)32, (char)119, (char)111, (char)114, (char)108, (char)100, (char)44, (char)104, (char)101, (char)108, (char)108, (char)111, (char)32, (char)119, (char)111, (char)114, (char)108, (char)100, (char)44}}

我們可以看到string data好好的變成了ascii string，太棒了!

重點是，即便我們用同樣的手法再搞一個main::result2，binary裡頭依然只會有一個template parameter object，不用擔心重複問題
而且現在我們有一個高彈性的手段，在compile time下產生字串了
完整的Code在這裡

參考資料

Stop Using constexpr (And Use This Instead!)
- 如果你不知道constexpr static是什麼咚咚的話可以先看看
Compiler support
Template non-type arguments

小結

太魔幻了八，不對，C++你要是有實作好我們那需要這樣?