Re: Further C++ operators for position

[Matthew Fernandez]

> On Nov 3, 2019, at 22:52, Akim Demaille <address@hidden> wrote:
> 
> Hi Matthew,
> 
>> Le 4 nov. 2019 à 05:27, Matthew Fernandez <address@hidden> a écrit :
>> 
>> Hello Bison folk,
>> 
>> I recently had a use case for comparing source positions coming out of a C++ 
>> Bison-produced parser. While operator== and operator!= are implemented on 
>> the position class [0], the ordering operators (<, <=, >, >=) are not. It 
>> was relatively straightforward to implement these myself, but I was 
>> wondering if these were of wider use and should live upstream in Bison’s 
>> position implementation. Perhaps there is some history behind this or some 
>> deliberate omission of these operators? Just wanted to ask if there’s a 
>> reason these don’t already exist before thinking about posting a patch. I’m 
>> not subscribed to the list, so please CC me in replies.
> 
> The semantics for line and columns are quite clear, so comparing Positions in 
> the same file is quite well defined.
> 
> But what should you do when the files are different?  (And Locations are 
> intervals, so there's no way to compare them totally in a natural order.)
> 
> What we can do, though, is offer implementations for std::less, that would 
> blindly apply the lexicographic order in both cases.
> 
> But the case of file names remains troublesome: should we compare the pointer 
> addresses (super fast, but non deterministic) or the pointees (super slow, 
> but deterministic)?

The implementation I had in mind had all operators returning false when the 
filenames differed. However maybe this is insufficient for defining a partial 
order? Some internet reading suggests these operators cannot be used to define 
a partial order and things like std::sort will malfunction.

I was not suggesting implementing any new operators for Locations, which I 
agree are orderable this way.

The std::less implementation you suggest is to also lexicographically compare 
the filenames themselves? I’m not sure this makes sense, because source 
positions from two different files aren’t really orderable at all.

My preliminary conclusion is that these C++ operators are not usable for 
defining a partial order and what I proposed is probably not a good idea. Some 
wisdom from foonathan [1] that I found helpful:

> Rule: The comparison operators should implement a total ordering.
> 
> If you don’t follow this rule, you might accidentally use your type in a set 
> or sort algorithm without specifying a custom comparison predicate. Your code 
> will still compile, but it will not work, as the algorithms expect a total 
> ordering. So in order to prevent this mistake, the comparison should be total.
> 
> ...
> 
> Rule: The comparison operators should implement the intuitive, obvious total 
> order for your type.
> 
> If there isn’t one, don’t overload the comparison operators.
> 
> ...
> 
> Rule: Implement a preorder or partial order by writing a named predicate 
> function that returns true if two arguments are less than or equal.
> 
> You have no choice: You can’t implement a preorder / partial order with <: it 
> will not allow deducing equivalence. So you have to use <=.
> 

  [1]: https://foonathan.net/2018/07/ordering-relations-programming/