Skip to content
This repository has been archived by the owner on Mar 29, 2022. It is now read-only.

Split eq out of Ord and put it in Eq. #8

Closed
otrho opened this issue Jan 10, 2022 · 21 comments
Closed

Split eq out of Ord and put it in Eq. #8

otrho opened this issue Jan 10, 2022 · 21 comments
Labels
enhancement New feature or request good first issue Good for newcomers

Comments

@otrho
Copy link

otrho commented Jan 10, 2022

We need eq for bool, but lt and gt don't make sense for bool, so I think we need an Eq trait for eq.

@adlerjohn
Copy link
Contributor

adlerjohn commented Jan 10, 2022

Is this an issue with the core library? If so, maybe should be transferred to https://github.com/FuelLabs/sway-lib-core? Oh wait it's already here 😂

@ControlCplusControlV
Copy link
Contributor

Already have a small path on my Fork, still testing to ensure it's non-breaking

@ControlCplusControlV
Copy link
Contributor

@otrho would you also want a patch to give booleans the Eq trait so they can be compared using an "eq" function?

@adlerjohn
Copy link
Contributor

also want a patch to give booleans the Eq trait so they can be compared using an "eq" function?

Yes, that makes sense. Ideally in a separate PR from splitting up Eq and Ord ❤️

@ControlCplusControlV
Copy link
Contributor

Working with a new approach atm, as moving Eq breaks some of Ord's ge, le, neq methods. So to fix this I've changed how some of those functions work to a pure assembly implementation rather than relying on function calls to a specific eq method

@otrho
Copy link
Author

otrho commented Jan 13, 2022

Yep, OK, I don't think it's possible to do this 'properly' at the moment since we need 'Supertraits'. e.g.,

pub trait Ord: Eq {
...
}

I was hoping initially that we could skirt around it, but it doesn't seem possible.

The only alternative, as @ControlCplusControlV has hinted at, is to implement le and ge with asm blocks, which would be duplicating the code directly from the Eq impls for each type. Obviously not desirable.

Does this sound right to you @sezna?

@ControlCplusControlV
Copy link
Contributor

ControlCplusControlV commented Jan 13, 2022

@otrho I actually remembered a mistake Fuel made in Yul+, and I am determined to not let it happen again!

Yul+ initially implemented the way Sway has right now

function lte(x, y) -> result {
   if or(lt(x, y), eq(x, y)) {
     result := 0x01
   }
   }

However this approach uses 3 opcodes, and was optimized down to with the help of me and t11's

  function lte(x, y) -> result {
     result := iszero(gt(x, y))
     }
ie we really shouldn't be using the equal operator at all for ge and le because it's inefficient

@ControlCplusControlV
Copy link
Contributor

ControlCplusControlV commented Jan 13, 2022

So implementing along the lines of would be the best way. Will work on a patch and test tomorrow

    fn le(self, other: Self) -> bool {
        asm(r1: self, r2: other, r3, r4 ,r5){
            gt r3 r1 r2;
            not r4 r3;

            r4: bool
        }
    }
    ```

@adlerjohn
Copy link
Contributor

adlerjohn commented Jan 13, 2022

Is there a case where >= is not the same as !<? Integers this always holds, but does it hold for everything?

Edit: answered my own question: https://doc.rust-lang.org/stable/src/core/cmp.rs.html#432

@ControlCplusControlV Just like the above in Rust, instead of implementing le in assembly, why don't you just implement lt, gt, eq, and not in assembly, then use Sway to compose?

@ControlCplusControlV
Copy link
Contributor

ControlCplusControlV commented Jan 13, 2022

@adlerjohn I can try to test, the issue we were running into is the implementation of le and ge would have to require the implementation of lt, eq, and not which it currently can't atm

@adlerjohn
Copy link
Contributor

Ah right. Then as a temporary workaround, sure re-implementing these simple functions is probably fine.

@otrho
Copy link
Author

otrho commented Jan 13, 2022

The point of having the default implementations in a trait, as le and ge are in the Ord trait, is for them to remain generic in terms of the lt and gt trait functions. So we want to guarantee that ge and le will work for every single impl of Ord based on the assumptions that lt and gt give us. This is why le and ge were implemented originally only using lt, gt and eq.

It's preferable to leave micro-optimisations, such as using !lt() for ge() to the compiler itself. This is a pattern we can recognise and transform during optimisation passes.

BUT! This is all in an ideal world, of course. Sway isn't quite there yet, but we really want it to get there eventually, so it's good to think in terms of the ideal situation.

Perhaps a compromise, until we have the ability to use 'supertraits', we could just literally use !lt() rather than ASM blocks (as John suggested above)? I think the ! operator has been implemented now, though perhaps we haven't updated the libraries to reflect that.

@otrho
Copy link
Author

otrho commented Jan 13, 2022

Is there a case where >= is not the same as !<? Integers this always holds, but does it hold for everything?

The canonical example I think of is floats and NaN, which is why Rust has PartialEq. Sway doesn't have floats, but there may be other types out there like this. People can implement Ord for whatever they like...

@otrho
Copy link
Author

otrho commented Jan 13, 2022

And if we don't have ! then maybe calling lt() and then using an ASM block just for the not is OK.

@sezna
Copy link
Contributor

sezna commented Jan 13, 2022

! is only available outside of core. Within core you have to directly call not

@otrho
Copy link
Author

otrho commented Jan 13, 2022

Ahh, chicken and egg in core. Tricky.

@sezna
Copy link
Contributor

sezna commented Jan 13, 2022

Yep, this is exactly why core exists, so you can use operators within the standard library.

@nfurfaro
Copy link

Just curious if this is still moving forward or on hold for now.
I'm all for a temporary working solution so I can use impl Eq for Address sooner rather than later if possible.

@ControlCplusControlV
Copy link
Contributor

If this is needed for a temporary solution I can get one done in a couple of hours, was placed on a bit of hold since a proper implementation wasn't available atm, but will whip out a quick asm implementation

@ControlCplusControlV
Copy link
Contributor

Fixed in #9 should be good once that is merged

@ControlCplusControlV
Copy link
Contributor

We should close this issue

Repository owner moved this from Todo to Done in Fuel Network Feb 11, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
enhancement New feature or request good first issue Good for newcomers
Projects
Archived in project
Development

No branches or pull requests

5 participants