Repository navigation
Match rules on AST instead of strings #447
Description
Today rules are matched by comparing printed strings. This does not work for NTTPs which have to be masked (#435). String printing also does not work for all AST shapes (llvm/llvm-project#217883, llvm/llvm-project#218420).
To fix this, do the matching at AST level. Take the following example:
std::vector<int> v;
v.push_back(3);
template <typename T1> void f1(std::vector<T1> &a0, const T1& a1) {
return a0.push_back(a1);
}- Extract the usage arguments (
[v, 3]) and its declaration (std::vector<int>::push_back(const int&)) - Apply the extracted arguments to the rule:
f1(v, 3)which instantiates tof1<int> - Take the declaration that
f1<int>'s return statement resolves to and compare it to the one from step 1 (std::vector<int>::push_back(const int&))
The entire matching is done on the AST. So there is no need for representing rules as strings. ir_src.json, cpp-rule-preprocessor and ToString disappear.
To implement this, rules are included in the translated TU. Only the rules that parse are kept. If the TU never included <map> then there are no rules for map. This is faster than the string matching approach.
Some rules take a type in a non-deduced context (a template parameter to the left of a ::, such as typename std::vector<T1>::iterator). Clang deduction does not work for them. Such rules are rewritten to take the iterator type itself (It) and compute T1 from it:
template <typename It,
typename T1 = typename std::iterator_traits<It>::value_type,
typename = typename std::enable_if<
std::is_same<It, typename std::vector<T1>::iterator>::value>::type>
typename std::vector<T1>::reference f2(It it) {
return it.operator*();
}How this works for f2(v.begin()):
Itis deduced as__gnu_cxx::__normal_iterator<int *, std::vector<int>>on libstdc++ andstd::__wrap_iter<int *>on libc++T1becomesint
At this step we got the mapping T1 = int but this is not enough. __normal_iterator or __wrap_iter are generic iterators, they are used for vector, list, string, etc. The final step is:
3. Choose this rule only if it's the iterator for vector: enable_if<is_same<It, vector::iterator>>
Most of this work will go into the new ast_matcher which replaces string_matcher. ir_src.json, cpp-rule-preprocessor and ToString will be deleted. C specific rules will need to live in src.c instead of src.cpp. Also rules will need to be guarded by the standard version they were introduced in.
Activity
Move C specific rules in src.c (#449)
nunoplopes commentedon Oct 4, 2026
Parsing c++ files is slow. I don't think we want to get rid of cpp-rule-preprocessor. Parsing thousands of files and headers is going to take a minute easily.
lucic71 commentedon Oct 5, 2026
The thing is that we don't parse STL headers with this approach. Rules that fail to parse in the current TU are not relevant, for example if rules for map fail to parse that's because the TU never included
map.This approach is really nice because it means no intermediate representation of rules and no hints for instantiating the rules in cpp-rule-preprocessor. I plan to spend some time thinking how can I make the proposed solution faster.
As I said in #451 it's 0.05 seconds for 1K rules and 0.5 seconds for 10K rules.
lucic71 commentedon Oct 5, 2026
I found a cheap way to implement this: instead of parsing all rules, scan the C++ program to only include the rules that it uses. I did a test with 100K dummy rules loaded for running the unit tests:
With full loading of the current string representation (ir_src.json) it takes on average 5s
Add standard-version ifdefs in rules (#448)
Selectively load rules in the same TU as the translated code (#451)
[NFC] Pass Converter to Mapper (#450)
Replace string matcher with AST matcher (Cpp2Rust#527)