Custom eq & hash with consistency

[wdanilo]

This task is automatically imported from the old Task Issue Board and it was originally created by jaroslavtulach.
Original issue is here.

---

During inception review of #183338334 and #181027272 it turned out a custom equality & hash code is needed. This story describes what has to be done to support custom equality.

Acceptance Criteria

Scenario:
Given any enso object (even those with custom == and hash)
When when it is put into such a Map
Then it behaves properly and respects ==

Details

This story is blocked by #183338334 - e.g. make Any.== a builtin. Effective, concentrated at a single place for all builtins and known types implementation of == is a prerequisite. This story is using == to compare for example types and it is essential to avoid cycles in the implementation.

The Enso runtime system offers default implementation of _equality_
as well as capability to _compute hash code_ (for use in `Map`) automatically.
The default implementation is sufficient for most of the programming activities.
Especially when defining new type and its constructors, they get sensible
implementation of both functions.

Should there be a need to redefine the default implementation, here is a way:
Define function `comparator` in your `type` (**update on Jan 13**: experiment with `Comparator.from` conversion, that way the functionality will be more hidden) and return pointer to
another `type` that satisfies following definition:

```
type Comparator T
    compare : T -> T -> (Ordering | Nothing)
    hash : T -> (Integer | Nothing)
```

    Representation of _rational numbers_ as a pair of integers needs a
    special equality. Here is a way to define it:

    ```
    type Rational
        Fraction (numerator:Integer) (denominator:Integer)

     Comparable.from (_:Rational) = Rational_Ordering
    ```

    The `Comparable.from` definition (as seen in [this commit](https://github.com/enso-org/enso/commit/b34dd5e37cbc477720b4d12b2e093810c119cd0d) for example) redefines the conversion on `Any` defined by `Ordering` module and returns reference to following
    type:

    ```
    type Rational_Ordering
        compare self r1 r2 =
            v1 = r1.numerator * r2.denominator
            v2 = r2.numerator * r1.denominator
            if v1 < v2 then Ordering.Less else
                if v1 > v2 then Ordering.Greater else
                    Ordering.Equal
        hash self r1 = 42 # or something better
    ```

    By defining the `Rational_Ordering` and making it available via `Comparable.from (_ : Rational)`
    method all parts of the Enso system will use
    the custom `compare` and `hash` methods whenever equality or hash code
    is needed.

    The equality check of two objects:
    - verifies both objects share the same `comparator`
    - consults their `compare` method
    - if the result is `Ordering.Equal` the system also checks that both instances have the same `hash`
    - the `hash` code check may be done only from time to time to speed things up

The above text is available here formatted and ready to be used in Ordering.enso.

There is an experimental branch DefaultCustomEq that contains prototype implementation demonstrating implementability of the ideas.

Tasks:

• Take the Any.ordering API from the DefaultCustomEq branch.
• Modify Any.== builtin to honor custom ordering as demonstrated on the DefaultCustomEq branch with === operator
• Copy Eq_Spec.enso tests and modify them to use ==; write few new ones if needed
• Experiment with Comparable.from conversion rather than using ordering
• Once the comparator API is established, migrate all the stdlib types to the new API, instead of overriding == or compare_to.

Blockers:

#183338334 resolved
#181027272 resolved

Comments:

I just noticed that while we were talking about equality, then the compare actually returns an Ordering.

1. Surely we want to require an ordering always? I can imagine for many types it may make sense to define an equality with hashing but not necessarily define a linear order. For example TreeMaps - can be checked for equality, but imposing a linear order on such trees is very artificial.
2. Sometimes it may be just faster to just check for equals/not-equal instead of computing the whole less/equal/greater ordering - so shouldn't we allow the user to provide just an equality check? (Radosław Waśko - Jan 9, 2023)

---

It is also not completely clear what does it mean for the comparator to return `Nothing`? Could this be elaborated on within the design?

What happens if hash_code returns non-nothing integer, but compare actually does return Nothing? Is such a situation allowed? (Radosław Waśko - Jan 9, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-19):

Progress: Thinking about all the requirements, designing API. Partial ordering VS total ordering? How to "expose" hash code / equality to Java code within libs? Probably out of scope for this issue. It should be finished by 2023-01-25. (Enso Bot - Jan 19, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-20):

Progress: Meeting with Radek to find out the best possible Comparator API that would comply with all the requirements. We have agreed on a compromise. Implementation via Comparable.from conversion now seems more difficult, since users cannot override conversion, neither extension methods. We will probably have to bail out to Any.comparator again. Found out that Map visualization does not work - https://www.pivotaltracker.com/story/show/184280631. We should also think about providing a shared library between engine and std-base, std-table, etc - https://www.pivotaltracker.com/story/show/184074597 It should be finished by 2023-01-25. (Enso Bot - Jan 20, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-23):

Progress: Made some progress with the comparator API. It sort of resembles type classes. So far, exporting hash_code on Meta.hash_code as a way how to access the internal HashCodeNode directly. Playing with @BuiltinMethod annotation and how to hide that even more. Found out an inconsistency between 1 == "foo" and [1, "foo"].sort, where the former returns False, whereas the latter throws Incomparable_Values. It should be finished by 2023-01-25. (Enso Bot - Jan 23, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-24):

Progress: Implemented LessThanAnyNode that is a replacement for Any.< - default comparators have to use builtins to avoid an infinite recursion. More progress with the comparator API and its testing. Review for #4074 and fix node adoption in tests that I recently introduced there. It should be finished by 2023-01-25. (Enso Bot - Jan 24, 2023)

---

**Pavel Marek** reports a new **🔴 DELAY** for today (2023-01-25):

Summary: There is 6 days delay in implementation of the Custom eq & hash with consistency (#183945328) task.
It will cause 6 days delay for the delivery of this weekly plan.

Delay Cause: As discussed with Jaroslav, we found out that I am actually working on two issues at the same time: https://www.pivotaltracker.com/story/show/183945328 and https://www.pivotaltracker.com/story/show/183958734 - also providing support for total ordered comparators and partially ordered comparators. It will definitely take another 2, or 3 work days until the PR is ready for review. The scope got broader. (Enso Bot - Jan 25, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-25):

Progress: Any.< is another builtin. Discussed the implementation with Jaroslav. Now, I have approvements of the prototype from both Jaroslav and Radoslaw. Struggling with how to call a method from a custom comparator in a builtin method, in a sane and optimized way. Hide all the builtin methods inside Comparable type that is a special builtin itself. It should be finished by 2023-01-31. (Enso Bot - Jan 25, 2023)

---

The implementation of `Any.<` was originally supposed to be handled as #183958734 - I don't mind you are handling both pivotals at once. (jaroslavtulach - Jan 26, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-26):

Progress: Implement special handling once we encounter an atom with a custom comparator inside EqualsNode or HashCodeNode - with help of some builtin (hidden) methods. Implement checking of custom comparator and invocation of either Any.== or Comparable.hash_builtin from HashCodeNode and EqualsNode via cached Function targets. Abandoned the idea of implementing this special handling in Java and rather created Enso methods that are called from Java. Review for "enable asserts" PR. It should be finished by 2023-01-31. (Enso Bot - Jan 26, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-27):

Progress: Added bunch of specializations to EqualsNode and HashCodeNode. Migrate Array.sort to the new comparator API. Fixed bunch of tests for Any.== and Any.< and other comparison operators. It should be finished by 2023-01-31. (Enso Bot - Jan 27, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-30):

Progress: Fixing tests in stdlib and Tables. Removing old compare_to method and replacing it with comparators for all the stdlib types. It should be finished by 2023-01-31. (Enso Bot - Jan 30, 2023)

---

**Pavel Marek** reports a new **🔴 DELAY** for today (2023-01-31):

Summary: There is 8 days delay in implementation of the Custom eq & hash with consistency (#183945328) task.
It will cause 8 days delay for the delivery of this weekly plan.

Delay Cause: The scope of the changes is bigger than I originally expected. Just tonight, I migrated all the types to the new comparator API. Now, I have to fix all the tests - I expect another 2-3 days for that, unless something major breaks down in Table tests, and after that another 3 days for the review. This is rather a pessimistic estimate. (Enso Bot - Jan 31, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-01-31):

Progress: Migrated all the types to the new comparator API. Dealing with StackOverflow issues - fiddling with how to handle types with custom ordered / unordered comparators in EqualsNode, LessThanNode and HashCodeNode. Now I am going to focus on fixing all the failing tests. I hope there won't be any major problem in table tests. It should be finished by 2023-02-08. (Enso Bot - Jan 31, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-02-01):

Progress: Continue fixing some tests. Looking into book clubs and trying to reproduce various issues. It should be finished by 2023-02-08. (Enso Bot - Feb 1, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-02-02):

Progress: Bumped into blocker https://www.pivotaltracker.com/story/show/184380208. Working on the blocker, as it seems pretty straightforward. This blocks comparisons of polyglot values with enso objects, therefore, many tests are still failing. It should be finished by 2023-02-08. (Enso Bot - Feb 2, 2023)

---

**Pavel Marek** reports a new **STANDUP** for today (2023-02-03):

Progress: Struggling with combination of specializations and guards for the equality-related nodes. Do we simply want the guards to be strictly disjunctive (best practice)? Probably not. Bumping into weird issues once there is some initialized cache in the nodes, and execute method falls into unexpected, instantiated, specialization. Since the tests are still failing, I am not going to publish the PR yet. It should be finished by 2023-02-08.

Next Day: Next day I will be working on the same task. Discuss with Jaroslav how should we proceed with this task on Monday. I won't have time over the weekend, most probably. (Enso Bot - Feb 3, 2023)

---