microsoft / microsoft/STL

`<functional>`: `boyer_moore_searcher` and `boyer_moore_horspool_searcher` should accept ADL-incompatible element types

Open
#4,380 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
C++
Stars
11.2k
Forks
1.7k
Avg merge
4d 15h
Merged PRs (30d)
22

Description

Describe the bug

The following program doesn't compile with MSVC STL due to ADL which attempts to complete a bad type.

#include <algorithm>
#include <functional>

template <class T>
struct holder {
    T t;
};

struct incomplete;

int main() {
    using validator = holder<incomplete>*;
    validator varr[1]{};
    (void) std::search(varr, varr + 1, std::boyer_moore_searcher<const validator*>{varr, varr + 1});
    (void) std::search(varr, varr + 1, std::boyer_moore_horspool_searcher<const validator*>{varr, varr + 1});
}

After the changes in #4379, the bug of MSVC STL comes from allocator comparison and iterator operations in unordered_map which is internally used by both searchers.

https://github.com/microsoft/STL/blob/192a84008a59ac4d2e55681e1ffac73535788674/stl/inc/functional#L2541

Command-line test case

Godbolt link.

Other standard library implementations seem to be buggy due to similar reasons.

Expected behavior

This example compiles.

STL version

Microsoft Visual Studio Community 2022
Version 17.9.0 Preview 5.0

Additional context

_STD-qualification doesn't work for this case. We may need to change the type of the unordered_map to avoid undesired ADL, which may be dangerous for ABI-compatibility.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with stl/inc/functional and the boyer_moore_searcher implementations, then reproduce the ADL failure using the provided Godbolt example. Trace the internally used unordered_map's allocator comparison and iterator operations, while considering the noted ABI-compatibility concern; done means the example compiles with both searchers.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
devtools
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.