1

I implemented a custom comparator for a map, but it seems not to work for inserting elements and finding keys.

Addition: I wonder if it is related to the implementation of STL. Since map::key_comp returns false reflexively for the two keys, which means they are equal, but map::find can find only one of them. This does not meet the specification of STL.

I tried to compare whether two function types are the same since I used function types as map's keys. The key point is to identify identical structures with different suffixes.

Therefore, I wrote this custom comparator. isTypeEqual is a static function.

struct cmp_func_type {
    bool operator()(FunctionType* a, FunctionType* b) {
        if (a->getNumParams() == b->getNumParams()) {
            if (isTypeEqual(a->getReturnType(), b->getReturnType())) {
                for (unsigned i = 0; i < a->getNumParams(); ++i) {
                    if (!isTypeEqual(a->getParamType(i), b->getParamType(i))) {
                        return a < b;
                    }
                }
                return false; // They are equal
            }
        }
        return a < b;
    }
};

In results, I found there are two types that should be equal according to my algorithm, but they seem not to share the same key. One is i32 (%struct.nvkm_bios.100694*, i8*, i32, i16), the other one is i32 (%struct.nvkm_bios*, i8*, i32, i16).

I used cmp_func_type()(a, b) and cmp_func_type()(b, a) to test the result, they all returned false.

Then I assigned a value to type a then used map.find(a) and map.find(b) to check whether they mapped to the same value. But only a could be found.

Lesterth
  • 77
  • 1
  • 6
  • 2
    Are you sure you want to compare the *pointers*? Unrelated pointers (like pointers to two different objects) doesn't really have any comparable relationship. – Some programmer dude Oct 24 '19 at 06:19
  • agree with @Someprogrammerdude. Please look at [this SO thread](https://stackoverflow.com/questions/5733254/how-can-i-create-my-own-comparator-for-a-map). – dorKKnight Oct 24 '19 at 06:24
  • Normally, in LLVM IR, the identical types share the same pointer and different types have different pointers. So the pointers are comparable. – Lesterth Oct 24 '19 at 06:25
  • An exception here is that, because of the different suffixes, the identical types may have different pointers. That's why I need to implement a custom comparator here. – Lesterth Oct 24 '19 at 06:28
  • I'm sorry for not being clearer, but for possible unrelated pointers the only sensible comparisons are really for equality or inequality. Comparing less-than or greater-than doesn't make sense generally. What does it mean that a pointer is "greater" than the other? – Some programmer dude Oct 24 '19 at 06:29
  • 2
    And are you sure that your function satisfies the [compare requirements](https://en.cppreference.com/w/cpp/named_req/Compare), including [strict weak ordering](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings)? – Some programmer dude Oct 24 '19 at 06:32
  • Unless all the pointers are pointing into the same array you are in Unspecified Behaviour land. See example ending with `assert(f(&x, &y) == f(&x, &y)); // may fire in a conforming implementation` from https://en.cppreference.com/w/cpp/language/operator_comparison – Richard Critten Oct 24 '19 at 06:33
  • And to nitpick a little, does it make sense to have ordering between "types"? Perhaps an unordered container (like `std::unordered_map`) would make more sense? – Some programmer dude Oct 24 '19 at 06:34
  • In my experience, pointers' address represents their declaration order in the file. The type which is declared earlier has a smaller pointer address. – Lesterth Oct 24 '19 at 06:34
  • @Lesterth Regarding declaration order, that's a very implementation specific detail, and doesn't hold up really. It's not uncommon that local variables have reversed that. And it all falls apart when you use dynamic allocation of objects. I think the bigger question for you is: Why do you need the types to be ordered to begin with? What problem is that supposed to solve? – Some programmer dude Oct 24 '19 at 06:35
  • These pointers are not local variables and will not change until the end of the program. They have a determined order after loading the file. In fact, I do not need ordered pointers, I just want to utilize map with a FunctionType* key. The problem is that the map does not identify the identical keys as my comparator expected. – Lesterth Oct 24 '19 at 06:42
  • Then your comparator probably doesn't follow the requirements I linked to above. Perhaps it would be easier to not use ordered containers if you don't really need it (especially considering all the problems there is with ordering of unrelated pointers, no matter what you think about it). – Some programmer dude Oct 24 '19 at 06:45
  • I have tried unordered_map but the result remains the same. `cmp_func_type` returns true when comparing two types but they still do not map to the same value. – Lesterth Oct 24 '19 at 07:13
  • 1
    @someprogrammer there are two type systems at play. LLVM defines types, and so does C++. LLVM types are objects in C++, and LLVM types can be equality-tested by testing pointer equality in C++. What Lesterth wants to do makes sense for an LLVM frontend. I'll try an answer later today. – arnt Oct 24 '19 at 07:13
  • I think the key point is that how does map find a key. In my opinion, when the comparator all returns false for a < b and b < a, it means a and b are the same key. But that seems not to be true. – Lesterth Oct 24 '19 at 07:15
  • I'm afraid I won't have time for an answer. A hint though: Mixing C++ pointer comparison with LLVM type comparison sounds like a trouble magnet; try changing your isTypeEquall() into something like ulong getTypeKey() that returns the same value if two types are equal and different if different, and use that as map key. Don't sort on pointer values sometimes and on contents sometimes. – arnt Oct 24 '19 at 07:22
  • You say that identical types may be represented by unequal pointers. Suppose pointers `A` and `B` represent such identical types; `A < B`, but your comparator declares them equivalent, so `cmp(A, B) == false`. There may exist an unrelated type, represented by a pointer `C`, such that `A < C && C < B`. In this case, your comparator is not transitive, and therefore doesn't satisfy *strict weak ordering* requirements, and therefore using it with `std::map` exhibits undefined behavior. – Igor Tandetnik Oct 24 '19 at 20:39
  • @RichardCritten While it's true that normal less-than operator is only defined on pointers into the same array, the approach could be salvaged by using `std::less` instead; it is required to induce a total order on all pointers of the same type. – Igor Tandetnik Oct 24 '19 at 20:46
  • But if A and B are identical types, only one of them can exist in the map as a key. Therefore, C will compare with only one of them. Furthermore, the main problem is A and B are not regarded as equal by map, although the comparator returns false reflexively. – Lesterth Oct 25 '19 at 01:14

0 Answers0