Sequence equality #249

frenchy64 · 2025-02-07T06:35:32Z

Closes #243
Closes #250
Closes #251
Closes #274

It would be nice to replace nullptr returns with nil in sequenceable but it enables important optimizations for calls to sequenceable member functions. I did not investigate returning option types.

jeaye

Lots of good fixes in here. I think there are some introduced bugs though. I tried to pick them out.

jeaye · 2025-02-22T19:05:06Z

compiler+runtime/src/cpp/jank/runtime/core.cpp

-      return !lhs;
+      return false;


Why change this? Right now, it would treat two null object ptrs as equal. This would also carry over to us removing nullptr support for boxes, such that two nils would be equal.

Thanks, I missed that box overloaded !.

Actually, could you look at this again? At this point we already know !lhs is false, so I think returning either is equivalent.

Would this be another way of writing the test?

if(!lhs != !rhs) return false

EDIT: No, because that is false when both are null.

Added assertions to point out my reasoning.

jeaye · 2025-02-22T19:09:15Z

compiler+runtime/src/cpp/jank/runtime/obj/chunked_cons.cpp

-        return true;
+        return seq == nullptr;


I don't think this is correct. In the case where this is a shorter seq than o, we would finish our for loop and then need to check if there is some seq left over.

In the case where this is a shorter seq than o, we would finish our for loop and then need to check if there is some seq left over.

This is my attempt at adding that check. At this point, we've already called next_in_place(seq), and seq will be nullptr if there's none left over.

We're talking about the same diff, right?

- return true; + return seq == nullptr;

I think I saw the opposite diff. 🤷 My mistake!

jeaye · 2025-02-22T19:11:55Z

compiler+runtime/src/cpp/jank/runtime/obj/cons.cpp

@@ -77,12 +77,12 @@ namespace jank::runtime::obj
        for(auto it(fresh_seq()); it != nullptr;
            it = runtime::next_in_place(it), seq = runtime::next_in_place(seq))
        {
-          if(seq == nullptr || !runtime::equal(it, seq->first()))
+          if(seq == nullptr || !runtime::equal(it->first(), seq->first()))


This seems like a good fix. We'd need the same thing for chunked_cons above, though. I wonder where else this cropped up. I have a TODO for sequence equality having a lot of copy pasta.

We'd need the same thing for chunked_cons above, though.

Done.

I wonder where else this cropped up.

Several places. I think I reverted some of them accidentally when experimenting with replace nullptr with nil_const(), I'll have another look.

I have a TODO for sequence equality having a lot of copy pasta.

I wasn't sure how to tackle it, but I can at least write more tests so then the abstraction can be validated easily.

Don't worry about removing support for nullptr yet. Certainly not in this PR, which already has a lot going on.

I wasn't sure how to tackle it, but I can at least write more tests so then the abstraction can be validated easily.

I have some ideas for how to do it. The tests are very welcome, though.

compiler+runtime/test/cpp/jank/runtime/core/seq.cpp

frenchy64 · 2025-02-23T07:54:05Z

Found and fixed a couple more issues while I scanned everything. Lmk if I should pull them out.

apply_to isn't compatible with seqs that return fresh seqs from next_in_place. Not sure if they exist, but persistent_list is implemented that way.
removed transient cases to resolve Transients mutate in-place on persistent ops #274
- extra: conj case for seqables didn't seem right to me compared to Clojure, so I removed it. For one, it changes the type of the seqable to a seq.
added paranoid assertions for nil while the function/template ambiguity exists for runtime::{next,seq,next_in_place,fresh_seq}.

jeaye

Mostly a rehash of our slack discussion, but also called out some other concerns.

jeaye · 2025-02-23T19:56:39Z

compiler+runtime/src/cpp/jank/runtime/behavior/callable.cpp

@@ -878,88 +878,88 @@ namespace jank::runtime
          case 1:
            return dynamic_call(source, s->first());
          case 2:
-            return dynamic_call(source, s->first(), s->next_in_place()->first());
+            return dynamic_call(source, s->first(), (s = s->next_in_place())->first());


I have a local TODO that notes that persistent_list_sequence shouldn't exist, since persistent_list itself is a sequence.

This change is a big red flag, since this is an extremely hot code path. I don't want to impact its perf for this one case which needs to change anyway.

If you want to add a comment here noting that it doesn't work for persistent_list, that's ok. If you want to remove persistent_list_sequence, that's also ok, but let's do it in a separate PR.

Either way, let's please undo this file's changes.

jeaye · 2025-02-23T19:57:07Z

compiler+runtime/include/cpp/jank/runtime/var.hpp

      {
-        return !lhs;
+        assert(lhs);


As we discussed in slack, none of these assertions on native boxes are needed. It has its own.

jeaye · 2025-02-23T19:59:33Z

compiler+runtime/src/cpp/jank/runtime/core.cpp

-    else if(!rhs)
+    if(!rhs)


Why remove the else? I find it helps with the logical flow. Also, by having the else if, your assertion is proven by the compiler to be redundant.

jeaye · 2025-02-23T20:12:10Z

compiler+runtime/src/cpp/jank/runtime/obj/chunked_cons.cpp

+          assert(it != nil::nil_const());
+          assert(seq != nil::nil_const());


It's impossible for these assertions to be false, proven by the type system. I think you're concerned about the next_in_place(it) call somehow returning an object_ptr. But it could never do that, since it would result in a compiler error.

Now, the history is that next_in_place has been in flux for a year or so and I was making some changes which would allow for it to be optional. That never happened, but it's why we're not using it->next_in_place() here. Ultimately, it's doing the same thing and all of these can be changed back. I just haven't done that yet, since it's a perf change and I haven't been focusing on perf.

Either way, your concerns about this being nil should not be keeping you up. auto it(fresh_seq()); means that we'll have a fully typed it for the currently visited object. We cannot assign an object_ptr to it. C++ won't allow it.

jeaye · 2025-02-23T20:17:50Z

compiler+runtime/src/cpp/jank/runtime/obj/repeat.cpp

@@ -16,6 +16,7 @@ namespace jank::runtime::obj
    : value{ value }
    , count{ count }
  {
+    assert(0 < to_int(count));


Feels like this could be an exception, rather than assertion, since someone embedding jank may create it a repeat with 0 and we don't need to kill the whole program.

frenchy64 added 15 commits February 7, 2025 00:34

wip range equality

1fc35d5

wip

bbc06d0

test core::equal

a059c68

wip

701d79f

[skip ci]

8a1472e

[skip ci] rm

cbd354f

[skip ci]

3727186

tests

ddd82ac

wip

c2da550

[skip ci]

c035ee8

[skip ci]

4dc1d92

wip

b6d8889

wip

408ed65

fix

4529d26

[skip ci]

c227006

frenchy64 changed the title ~~[wip] range equality~~ [wip] sequence equality Feb 7, 2025

frenchy64 added 14 commits February 9, 2025 21:58

fix

f1d6e2c

[skip ci]

ca229f8

wip

3afba55

[skip ci]

c5f2e33

fmt

2dbbca6

Merge branch 'main' into sequence-equality

d081d74

Merge branch 'main' into sequence-equality

4819593

assert

fe6f1dd

Merge branch 'main' into sequence-equality

2deb82d

[skip ci]

c36ca8d

wip

acb06a4

[skip ci]

4a1620f

[skip ci]

b3ffc63

[skip ci] undo

8bf2c34

frenchy64 added 10 commits February 22, 2025 02:09

[skip ci]

4979e26

[skip ci]

5e1e9c3

[skip ci]

fc1ff00

[skip ci]

6a1919f

[skip ci]

10f4798

[skip ci]

bdecaf0

wip

2dc83fe

[skip ci] fmt

99728fa

wip

0b8c535

wip

dd3649e

frenchy64 changed the title ~~[wip] sequence equality~~ Sequence equality Feb 22, 2025

frenchy64 marked this pull request as ready for review February 22, 2025 08:49

frenchy64 requested a review from jeaye February 22, 2025 08:49

jeaye requested changes Feb 22, 2025

View reviewed changes

frenchy64 added 12 commits February 22, 2025 13:45

[skip ci] revert equal null check

674a8e9

[skip ci] fix first half of chunked cons

d754b74

[skip ci] add bang to next-in-place, fix comments

6132099

[skip ci] assert

7c16d3a

asserts

d9d6281

[skip ci] -else

e562511

add sequence_equal tests

0d27f83

apply-to

64a74a2

[skip ci]

eee2c29

tests

cea8422

fmt

2e08987

wip

35a8643

frenchy64 requested a review from jeaye February 23, 2025 07:54

jeaye requested changes Feb 23, 2025

View reviewed changes

[skip ci] undo equal changes

5aecb6e

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sequence equality #249

Sequence equality #249

frenchy64 commented Feb 7, 2025 •

edited

Loading

jeaye left a comment

jeaye Feb 22, 2025

frenchy64 Feb 22, 2025

frenchy64 Feb 23, 2025 •

edited

Loading

frenchy64 Feb 23, 2025

jeaye Feb 22, 2025

frenchy64 Feb 22, 2025

frenchy64 Feb 23, 2025

jeaye Feb 23, 2025

jeaye Feb 22, 2025

frenchy64 Feb 22, 2025

jeaye Feb 22, 2025

jeaye Feb 22, 2025 •

edited

Loading

frenchy64 commented Feb 23, 2025 •

edited

Loading

jeaye left a comment

jeaye Feb 23, 2025

jeaye Feb 23, 2025

jeaye Feb 23, 2025

jeaye Feb 23, 2025

jeaye Feb 23, 2025

		assert(it != nil::nil_const());
		assert(seq != nil::nil_const());

Sequence equality #249

Are you sure you want to change the base?

Sequence equality #249

Conversation

frenchy64 commented Feb 7, 2025 • edited Loading

jeaye left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

frenchy64 Feb 23, 2025 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jeaye Feb 22, 2025 • edited Loading

Choose a reason for hiding this comment

frenchy64 commented Feb 23, 2025 • edited Loading

jeaye left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

frenchy64 commented Feb 7, 2025 •

edited

Loading

frenchy64 Feb 23, 2025 •

edited

Loading

jeaye Feb 22, 2025 •

edited

Loading

frenchy64 commented Feb 23, 2025 •

edited

Loading