The assumption here seems to be that the compiler/analyzer is only able to look at one function at a time. This makes no sense. Safety is a whole-program concern and you should analyze the whole program to check it. If anything as simple as the following needs lifetime annotations then your proposed solution will not be used by anyone: const int& f4(std::map & map, const int& key) { return map[key]; }
Whole-program analysis is not tractable (i.e., not scalable), and Rust has already proven that function signatures are enough, and does actually scale. The analysis can be performed locally at each call site, and doesn't have to recurse into callees. Your function would look like this in Rust: fn f4 (map: &'a Map , key: &i32) -> &'a i32 { ... } You don't need much more than a superficial understanding of Rust's lifet…
Some amount of non-local inference might also be possible for templated C++ code that already lack a proper separate compilation story.