mergiraf/mergiraf
mergiraf/mergiraf
9
213
Fork 45
Code Issues 51 Pull requests 7 Releases 19 Activity Actions

feat(mgf_dev): Commutative tree isomorphism checking #254

Merged
ada4a merged 16 commits from 197-commutative-isomorphism into main 2025-03-13 10:05:00 +01:00
Conversation 7 Commits 16 Files changed 6 +145 -7
wetneb commented 2025-03-09 15:38:32 +01:00
Owner
Copy link

Closes #197.

This is a rather expensive isomorphism checking algorithm, so
it's not meant to be integrated in the merge process.

The main algorithm isn't super readable. If you have suggestions to reformulate it, feel free to push directly to the branch (which I created in the official repo).

Closes #197. This is a rather expensive isomorphism checking algorithm, so it's not meant to be integrated in the merge process. The main algorithm isn't super readable. If you have suggestions to reformulate it, feel free to push directly to the branch (which I created in the official repo).
feat: Commutative tree isomorphism checking
All checks were successful
/ test (pull_request) Successful in 53s
Details
1d4a23dd4a 
Closes #197.

This is a rather expensive isomorphism checking algorithm, so
it's not meant to be integrated in the merge process.
wetneb reviewed 2025-03-09 15:40:27 +01:00
src/tree.rs Outdated
@ -335,0 +382,4 @@
.children
.iter()
.map(|child| (child.grammar_name, *child))
.collect();
wetneb commented 2025-03-09 15:40:27 +01:00
Author
Owner
Copy link

This grouping of the children by type is likely not super useful to reduce the time complexity, because checking the equality of grammar types is the first thing we do at the beginning of the recursive method call anyway.

This grouping of the children by type is likely not super useful to reduce the time complexity, because checking the equality of grammar types is the first thing we do at the beginning of the recursive method call anyway.
ada4a commented 2025-03-09 19:25:29 +01:00
Owner
Copy link

And MultiMap with its double hashing is not the most efficient data structure either...

And `MultiMap` with its double hashing is not the most efficient data structure either...
wetneb commented 2025-03-10 14:21:40 +01:00
Author
Owner
Copy link

Yeah, so I've removed it for now.

Yeah, so I've removed it for now.
ada4a marked this conversation as resolved
wetneb changed title from feat: Commutative tree isomorphism checking to feat(mgf_dev): Commutative tree isomorphism checking 2025-03-09 15:41:13 +01:00
ada4a commented 2025-03-09 19:28:47 +01:00
Owner
Copy link

Here's a couple of miscellaneous changes

Here's a couple of miscellaneous changes
typo
All checks were successful
/ test (pull_request) Successful in 54s
Details
29e330ff16
use parens for clearer formatting
All checks were successful
/ test (pull_request) Successful in 54s
Details
25dcb57988
ada4a reviewed 2025-03-09 20:16:13 +01:00
src/tree.rs Outdated
@ -335,0 +360,4 @@
// two isomorphic leaves
t2.children.is_empty() && self.source == t2.source
} else if !self.children.is_empty()
&& (self.children.iter())
ada4a commented 2025-03-09 20:16:13 +01:00
Owner
Copy link

Shouldn't one check for an equal length here? I understand that the current form would rightfully ignore a trailing separator for example, but it can also incorrectly fail to reject two arrays just because the first couple of elements match. Well, an array in particular won't have this problem, since its closing delimiter (]) will fire a mismatch -- take any CommutativeParent::without_delimiters instead. Let me try to go and add a test case for this.

Shouldn't one check for an equal length here? I understand that the current form would rightfully ignore a trailing separator for example, but it can also incorrectly fail to reject two arrays just because the first couple of elements match. Well, an array in particular won't have this problem, since its closing delimiter (`]`) will fire a mismatch -- take any `CommutativeParent::without_delimiters` instead. Let me try to go and add a test case for this.
wetneb commented 2025-03-09 20:17:40 +01:00
Author
Owner
Copy link

Ah yes of course, because the zip function will truncate the longer list of children. Good catch!

Ah yes of course, because the zip function will truncate the longer list of children. Good catch!
❤️ 1
ada4a commented 2025-03-09 20:21:05 +01:00
Owner
Copy link

The only reason I even found this case is that all the ifs &&s and ||s got really confusing, so I tried to enumerate all the possible cases by hand 😅 Let's see if I find anything else!

The only reason I even found this case is that all the `if`s `&&`s and `||`s got really confusing, so I tried to enumerate all the possible cases by hand 😅 Let's see if I find anything else!
ada4a commented 2025-03-09 20:28:26 +01:00
Owner
Copy link

Test added!

Test added!
ada4a marked this conversation as resolved
fix: ensure equal lengths in the pairwise-commutatively-isomorphic case
All checks were successful
/ test (pull_request) Successful in 52s
Details
b6e1c1e916
split the if-chain into three parts
All checks were successful
/ test (pull_request) Successful in 54s
Details
194cfd6cb1 
I think this better represents the cases that we're looking for. Notable
changes include:
- put the length check at the beginning, for symmetry
  - the third case could also have had it, but at least for current
tests it's redundant
- in the third case, add a guard clause to reduce nesting

I realize this could've also been realized as closures without
arguments, which would simplify the signatures a lot -- maybe we could
do just that
Merge branch 'main' into 197-commutative-isomorphism
All checks were successful
/ test (pull_request) Successful in 53s
Details
f565ea2660
Drop the indexing of children by type
All checks were successful
/ test (pull_request) Successful in 55s
Details
756aaab079
use LangProfile getters
All checks were successful
/ test (pull_request) Successful in 53s
Details
4adf81de8a
ada4a reviewed 2025-03-10 14:26:36 +01:00
src/tree.rs Outdated
@ -335,0 +354,4 @@
}
// two isomorphic leaves
fn isomorphic_leaves(t1: &AstNode, t2: &AstNode) -> bool {
ada4a commented 2025-03-10 14:26:36 +01:00
Owner
Copy link

Copying my comment from 194cfd6cb1 here just in case it got missed:

I realize this could've also been realized as closures without arguments, which would simplify the signatures a lot -- maybe we could do just that

Copying my comment from 194cfd6cb11e6a38b98268e16fc1800d2d42039a here just in case it got missed: > I realize this could've also been realized as closures without arguments, which would simplify the signatures a lot -- maybe we could do just that
wetneb commented 2025-03-10 14:28:08 +01:00
Author
Owner
Copy link

Sure, that makes sense!

Sure, that makes sense!
ada4a marked this conversation as resolved
s/t2/other - a convention from std
All checks were successful
/ test (pull_request) Successful in 52s
Details
2240cfd6d1
use free-standing zip
All checks were successful
/ test (pull_request) Successful in 53s
Details
8de03370c7 
allows using the shorthand `&` instead of `.iter()`
wetneb commented 2025-03-13 09:31:40 +01:00
Author
Owner
Copy link

@ada4a is this good to go for you, apart from the conflict? (which mergiraf can solve, but I discovered #259)

@ada4a is this good to go for you, apart from the conflict? (which mergiraf can solve, but I discovered #259)
Merge branch 'main' into 197-commutative-isomorphism
Some checks failed
/ test (pull_request) Failing after 44s
Details
a1b447e89f
ada4a commented 2025-03-13 10:00:41 +01:00
Owner
Copy link

@wetneb wrote in #254 (comment):

@ada4a is this good to go for you, apart from the conflict? (which mergiraf can solve

Sure! The resolution is perfectly sensible too.

, but I discovered #259)

Finally we have a reproduction of this, thank you very much! This happened quite often actually, but I never bothered to record it.

I pushed a merge with formatting already dealt with, so we can merge this now.

@wetneb wrote in https://codeberg.org/mergiraf/mergiraf/pulls/254#issuecomment-3028459: > @ada4a is this good to go for you, apart from the conflict? (which mergiraf can solve Sure! The resolution is perfectly sensible too. > , but I discovered #259) Finally we have a reproduction of this, thank you very much! This happened quite often actually, but I never bothered to record it. I pushed a merge with formatting already dealt with, so we can merge this now.
clippy::use_self
All checks were successful
/ test (pull_request) Successful in 49s
Details
850dec1ad7
ada4a approved these changes 2025-03-13 10:04:20 +01:00
ada4a merged commit 20b000f358 into main 2025-03-13 10:05:00 +01:00
ada4a deleted branch 197-commutative-isomorphism 2025-03-13 10:05:02 +01:00
Sign in to join this conversation.
Reviewers
No reviewers
ada4a
Labels
Clear labels   
Compat/Breaking

Breaking change that won't be backward compatible

  
Kind
Bad merge
Examples where the merging algorithm doesn't work as well as it should

  
Kind
Bug
Something is not working

  
Kind
Documentation
Documentation changes

  
Kind
Enhancement
Improve existing functionality

  
Kind
Feature
New functionality

  
Kind
New language

  
Kind
Security
This is security issue

  
Kind
Testing
Issue or pull request related to testing

  
Priority
Critical
The priority is critical

  
Priority
High
The priority is high

  
Priority
Low
The priority is low

  
Priority
Medium
The priority is medium

  
Reviewed
Confirmed
Issue has been confirmed

  
Reviewed
Duplicate
This issue or pull request already exists

  
Reviewed
Invalid
Invalid issue

  
Reviewed
Won't Fix
This issue won't be fixed

  
Status
Abandoned
Somebody has started to work on this but abandoned work

  
Status
Blocked
Something is blocking this issue or pull request

  
Status
Need More Info
Feedback is required to reproduce issue or to continue work

No labels
Compat/Breaking
Kind
Bad merge
Kind
Bug
Kind
Documentation
Kind
Enhancement
Kind
Feature
Kind
New language
Kind
Security
Kind
Testing
Priority
Critical
Priority
High
Priority
Low
Priority
Medium
Reviewed
Confirmed
Reviewed
Duplicate
Reviewed
Invalid
Reviewed
Won't Fix
Status
Abandoned
Status
Blocked
Status
Need More Info
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
2 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: mergiraf/mergiraf#254
No description provided.
Delete branch "197-commutative-isomorphism"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?