[clangd][StdSymbolMap] Prefer std::remove from algorithm

[kadircet]

Summary

std::remove from algorithm is a lot more common than the overload from
the cstdio (which deletes files). This patch introduces a set of symbols
for which we should prefer the overloaded versions.

[sammccall]

clang-tools-extra/clangd/StdSymbolMap.inc

958

Is the stdio version so uncommon we are willing to be wrong about it? For move we omit it from here and consider it case-by-case, I'd have imagined doing the same here

(BTW at some point we may want to extend this to list alternative headers for ambiguous symbols)

clang-tools-extra/clangd/include-mapping/cppreference_parser.py

140–142

This logic seems a bit weird and non-general: it allows us to accept any variant and reject any non-variant, but it doesn't allow us to accept a*specific* variant (they are named) and doesn't allow us to accept both (which currently would lead to the symbol being dropped as ambiguous).

[kadircet]

clang-tools-extra/clangd/StdSymbolMap.inc

958

Is the stdio version so uncommon we are willing to be wrong about it?

Waiting for permissions on a big codebase with lots of third_party code to perform some analysis.

For move we omit it from here and consider it case-by-case, I'd have imagined doing the same here

std::move is different, both occurrences are marked as variants. We don't really drop it during post-processing saying there are multiple options, it just never makes it to the final list.

move<>() (algorithm) (since C++11)
move<>() (utility) (since C++11)

I am not sure how we ended up with this ignore the varianted symbols behavior.

(BTW at some point we may want to extend this to list alternative headers for ambiguous symbols)

I agree, there is some room for improvement, like also listing different overloads with expected number of parameters and language versions.
It's unclear whether we need such detail today though.

clang-tools-extra/clangd/include-mapping/cppreference_parser.py

140–142

I was trying to keep the change to a minimum. Happy to go with a solution that accepts a dictionary in the form of (FQN, list_of_accepted_variants), where the list can have "" variant, or instead of a list we can also have a glob, but I don't think it'll provide much value considering the irregularity of std header names.

[kadircet]

1658	remove	NULL
1731	std::__u::remove	llvm/include/c++/v1/__algorithm/remove.h

for whatever reason I remembered the std::remove to have been referenced ~17k. looks like these two are much closer. I don't think it makes sense to prefer one or the other here.

I suggest moving forward with a mechanism that enables accepting certain variants and accepting both unnamed and algorithm variants for std::remove, hence it being rejected as an ambiguous symbol in the end. That way we won't have a special case to handle once we start including multiple options for a symbol.
WDYT?

[sammccall]

In D114724#3163579, @kadircet wrote:

for whatever reason I remembered the std::remove to have been referenced ~17k. looks like these two are much closer. I don't think it makes sense to prefer one or the other here.

Agree, for StdSymbolMap.inc this means neither version of remove should be there.

I suggest moving forward with a mechanism that enables accepting certain variants and accepting both unnamed and algorithm variants for std::remove, hence it being rejected as an ambiguous symbol in the end. That way we won't have a special case to handle once we start including multiple options for a symbol.
WDYT?

In practice we don't actually need the ability to accept specific variants, just variants in general.
(Maybe we'll need it later, but maybe not.)

clang-tools-extra/clangd/CSymbolMap.inc

701 ↗

(On Diff #390405)

hmm, I would expect this to still be in CSymbolMap, it's not ambiguous there.

clang-tools-extra/clangd/include-mapping/cppreference_parser.py

140–142

I'd just change this to variant or (ns + name in variants to accept)

That way we accept both versions of move, and end up dropping it as ambiguous.

168

we should have a comment on the symbol

1. std::remove<> template has variant "algorithm"

[kadircet]

• Change the variant acception mechanism to work with specific variants.

clang-tools-extra/clangd/StdSymbolMap.inc

 SYMBOL(regex_iterator, std::, <regex>)
 SYMBOL(regex_match, std::, <regex>)
 SYMBOL(regex_replace, std::, <regex>)
 SYMBOL(regex_search, std::, <regex>)
 SYMBOL(regex_token_iterator, std::, <regex>)
 SYMBOL(regex_traits, std::, <regex>)
 SYMBOL(reinterpret_pointer_cast, std::, <memory>)
 SYMBOL(remainder, std::, <cmath>)
-SYMBOL(remove, std::, <cstdio>)
 SYMBOL(remove_all_extents, std::, <type_traits>)
 SYMBOL(remove_all_extents_t, std::, <type_traits>)
 SYMBOL(remove_const, std::, <type_traits>)
 SYMBOL(remove_const_t, std::, <type_traits>)
 SYMBOL(remove_copy, std::, <algorithm>)
 SYMBOL(remove_copy_if, std::, <algorithm>)
 SYMBOL(remove_cv, std::, <type_traits>)
 SYMBOL(remove_cv_t, std::, <type_traits>)

clang-tools-extra/clangd/include-mapping/cppreference_parser.py

def _ParseIndexPage(index_page_html):
   symbols = []
   soup = BeautifulSoup(index_page_html, "html.parser")
   for symbol_href in soup.select("a[title]"):
     # Ignore annotated symbols like "acos<>() (std::complex)".
     # These tend to be overloads, and we the primary is more useful.
     # This accidentally accepts begin/end despite the (iterator) caption: the
     # (since C++11) note is first. They are good symbols, so the bug is unfixed.
     caption = symbol_href.next_sibling
-    variant = isinstance(caption, NavigableString) and "(" in caption
+    variant = None
+    if isinstance(caption, NavigableString) and "(" in caption:
+      variant = caption.text.strip(" ()")
     symbol_tt = symbol_href.find("tt")
     if symbol_tt:
       symbols.append((symbol_tt.text.rstrip("<>()"), # strip any trailing <>()
                       symbol_href["href"], variant))
   return symbols
 
 
 def _ReadSymbolPage(path, name):
   with open(path) as f:
     return _ParseSymbolPage(f.read(), name)
 
 
-def _GetSymbols(pool, root_dir, index_page_name, namespace):
+def _GetSymbols(pool, root_dir, index_page_name, namespace, variants_to_accept):
   """Get all symbols listed in the index page. All symbols should be in the
   given namespace.
 
   Returns a list of Symbols.
   """
 
   # Workflow steps:
   #   1. Parse index page which lists all symbols to get symbol
   #      name (unqualified name) and its href link to the symbol page which
   #      contains the defined header.
   #   2. Parse the symbol page to get the defined header.
   index_page_path = os.path.join(root_dir, index_page_name)
   with open(index_page_path, "r") as f:
     # Read each symbol page in parallel.
     results = [] # (symbol_name, promise of [header...])
     for symbol_name, symbol_page_path, variant in _ParseIndexPage(f.read()):
       # Variant symbols (e.g. the std::locale version of isalpha) add ambiguity.
       # FIXME: use these as a fallback rather than ignoring entirely.
-      if variant:
+      variants_for_symbol = variants_to_accept.get(
+          (namespace or "") + symbol_name, ())
+      if variant and variant not in variants_for_symbol:
         continue
       path = os.path.join(root_dir, symbol_page_path)
       results.append((symbol_name,
                       pool.apply_async(_ReadSymbolPage, (path, symbol_name))))
 
     # Build map from symbol name to a set of headers.
     symbol_headers = collections.defaultdict(set)
     for symbol_name, lazy_headers in results:
       symbol_headers[symbol_name].update(lazy_headers.get())
 
   symbols = []
   for name, headers in sorted(symbol_headers.items(), key=lambda t : t[0]):
     symbols.append(Symbol(name, namespace, list(headers)))
   return symbols
 
 
 def GetSymbols(parse_pages):
   """Get all symbols by parsing the given pages.
 
   Args:
     parse_pages: a list of tuples (page_root_dir, index_page_name, namespace)
   """
+  # By default we prefer the non-variant versions, as they're more common. But
+  # there are some symbols, whose variant is more common. This list describes
+  # those symbols.
+  variants_to_accept = {
+      # std::remove<> has variant algorithm.
+      "std::remove": ("algorithm"),
+  }
   symbols = []
   # Run many workers to process individual symbol pages under the symbol index.
   # Don't allow workers to capture Ctrl-C.
   pool = multiprocessing.Pool(
       initializer=lambda: signal.signal(signal.SIGINT, signal.SIG_IGN))
   try:
     for root_dir, page_name, namespace in parse_pages:
-      symbols.extend(_GetSymbols(pool, root_dir, page_name, namespace))
+      symbols.extend(_GetSymbols(pool, root_dir, page_name, namespace,
+                                 variants_to_accept))
   finally:
     pool.terminate()
     pool.join()
   return symbols