[Due for payment 2025-05-27] [Due for payment 2025-05-22] [Due for payment 2025-05-14] Investigate codebase for potential endless loops

[mountiny]

If you haven’t already, check out our contributing guidelines for onboarding and email [email protected] to request to join our Slack channel!

---

Version Number:
Reproducible in staging?:
Reproducible in production?:
If this was caught on HybridApp, is this reproducible on New Expensify Standalone?:
If this was caught during regression testing, add the test name, ID and link from TestRail:
Email or phone of affected tester (no customers):
Logs: https://stackoverflow.com/c/expensify/questions/4856
Expensify/Expensify Issue URL:
Issue reported by: @JmillsExpensify
Slack conversation (hyperlinked to channel name): https://expensify.slack.com/archives/C05LX9D6E07/p1745490519573089

Action Performed:

Break down in numbered steps

1. Go to Reports
2. Search some query

Expected Result:

Describe what you think should've happened

User gets valid reponse

Actual Result:

Describe what actually happened

The browser just hangs as there is some js loop

Workaround:

Can the user still use Expensify without this being fixed? Have you informed them of the workaround?

Platforms:

Select the officially supported platforms where the issue was reproduced:

• Android: Standalone
• Android: HybridApp
• Android: mWeb Chrome
• iOS: Standalone
• iOS: HybridApp
• iOS: mWeb Safari
• Windows: Chrome
• MacOS: Chrome / Safari
• MacOS: Desktop

Platforms Tested:

On which of our officially supported platforms was this issue tested:

• Android: Standalone
• Android: HybridApp
• Android: mWeb Chrome
• iOS: Standalone
• iOS: HybridApp
• iOS: mWeb Safari
• Windows: Chrome
• MacOS: Chrome / Safari
• MacOS: Desktop

Screenshots/Videos

Add any screenshot/video evidence

View all open jobs on GitHub

Issue Owner

Current Issue Owner: @alexpensify

[melvin-bot]

Triggered auto assignment to @alexpensify (Bug), see https://stackoverflow.com/c/expensify/questions/14418 for more details. Please add this bug to a GH project, as outlined in the SO.

[melvin-bot]

Triggered auto assignment to @aldo-expensify (AutoAssignerNewDotQuality)

[mountiny]

@aldo-expensify Check out the slack thread, the idea here is that someone from Callstack will jump on this and try to investigate the codebase around search for some possible endless loops

[sosek108]

Hi, I'm Hubert from Callstack and I would like to take a look at this issue.

[aldo-expensify]

👋 @sosek108 how is this going?

[sosek108]

On slack conversation we diagnosed that potential cause for problem is SuffixUkkonenTree algorithm. There is no endless loop, but a lot of calls for finite loops

I have proposal for minor fixes to that algorithm,

[sosek108]

🚨 Edited by proposal-police: This proposal was edited at 2025-04-28 13:06:15 UTC.

Proposal

Please re-state the problem that we are trying to solve in this issue.

The convertToBase26 function incorrectly divides by 32 using a bitwise shift (>> 5) instead of properly dividing by 26. This causes wrong base-26 conversions for many numbers, especially above 26, and leads to incorrect results. Additionally, the caching mechanism incorrectly stores results under the wrong key due to modifying the input num inside the function.

What is the root cause of that problem?

The root cause is twofold:

Misuse of bitwise shifting (>> 5) under the false assumption that it mimics division by 26, while it actually divides by 32.

Caching the result after modifying the input parameter, resulting in wrong cache keys and cache misses.

What changes do you think we should make in order to solve the problem?

Replace the bitwise shift (num >>= 5) with correct integer division (Math.floor(num / 26)).

Preserve the original num value in a separate variable before any mutation, and use the original number as the key when caching the result.

Slightly improve readability by avoiding mutation of the input parameter directly.

What specific scenarios should we cover in automated tests to prevent reintroducing this issue in the future?

Validate that numbers around 26, 32, 52, 53, and 63 correctly convert to base-26 arrays.

Add tests for small numbers (e.g., 1, 2, 25, 26, 27) to ensure basic behavior.

Include tests with numbers where division by 26 and division by 32 would differ to specifically catch this kind of error

Add a test ensuring that negative inputs throw the correct error message.

These tests ensure correctness of logic for both typical cases and edge cases, and will immediately fail if future changes accidentally introduce wrong division logic again.

What alternative solutions did you explore? (Optional)

N/A

[aldo-expensify]

Sounds good, have you been able to reproduce the slowness?

[Nodonisko]

I spent some time trying to reproduce hangs using Jason's Onyx state, but no luck. I will continue with optimizing search tree creating which I hope may resolve slowness because search tree is now recreated many times when user types into input. #51150

[aldo-expensify]

can Jason reproduce consistently? Maybe we can create an adhoc build and ask him to test with it.

[sosek108]

@aldo-expensify @alexpensify

Here is my PR with changes proposed in this comment.

Do you think that I should add any other test cases?

@Nodonisko good catch with that division by 32 instead of 26. Results are indeed different

[melvin-bot]

Reviewing label has been removed, please complete the "BugZero Checklist".

[melvin-bot]

The solution for this issue has been 🚀 deployed to production 🚀 in version 9.1.41-1 and is now subject to a 7-day regression period 📆. Here is the list of pull requests that resolve this issue:

• Introduce fixes to Ukkonen tree's method convertToBase26 #61041

If no regressions arise, payment will be issued on 2025-05-14. 🎊

For reference, here are some details about the assignees on this issue:

• @sosek108 does not require payment (Contractor)

[sosek108]

@Nodonisko how did you find out memory leak in SearchAutocompleteList -> getParticipantsAutocompleteList?

I've found out that this massive memory leak is due to FastSearch objects in Memory tab of Dev tools. The path for these objects indeed pointed out to getParticipantsAutocompleteList but after I removed this method Dev Tools just pointed out to different place.

I've focused on adding disposal method to FastSearch object and properly calling it in useFastSearchFromOptions. See my PR: #61771

[Nodonisko]

@sosek108 For some reason there is retained reference from search -> getParticipantsAutocompleteList/onLayout/onArrowFocus and other component internals which will probably cause GC to not clean up old FastSearch trees. What's interesting that direction is opposite what you expect, you would expect component to retain reference on FastSearch tree but it's actually FastSearch retaining reference to component itself. As can see in screenshot that FastSearch is retaining reference to SearchAutocompleteList.

Your fix will help but I think it's treating only symptoms but not real cause that GC doesn't clean up old FastSearch classes, because if that worked your fix wouldn't be necessary. Memory leak still will be there because there will be uncleaned FastSearch classes only with empty ArrayBuffer so it will be much smaller and it will be few kB.

Not sure if it's worth looking for proper fix because I already spent quite a few hours investigating why it's being retained and I think it could easily take few more days to find real cause.

[sosek108]

@Nodonisko I agree with your opinion. I was also trying to find why these references are not cleared by GC.

[melvin-bot]

Payment Summary

Upwork Job

• Contributor: @sosek108 is from an agency-contributor and not due payment
• Reviewer: @ZhenjaHorbach owed $250 via NewDot

BugZero Checklist (@alexpensify)

• I have verified the correct assignees and roles are listed above and updated the necessary manual offers
• I have verified that there are no duplicate or incorrect contracts on Upwork for this job (https://www.upwork.com/ab/applicants//hired)
• I have paid out the Upwork contracts or cancelled the ones that are incorrect
• I have verified the payment summary above is correct

[Nodonisko]

@mountiny Are we fine with @sosek108 solution? I think it could be fine for now even when it's not fixing root cause. I already spent quite some time on tracking root cause but it's pretty hard problem and I can probably easily spent days on it. Should I continue?

[mountiny]

@Nodonisko agreed that we can evaluate if this has improved after that fix. Eventually we will want to improve this even further, but there might be some more useful areas with lower-hanging fruit at the moment

[melvin-bot]

Reviewing label has been removed, please complete the "BugZero Checklist".

[melvin-bot]

The solution for this issue has been 🚀 deployed to production 🚀 in version 9.1.45-21 and is now subject to a 7-day regression period 📆. Here is the list of pull requests that resolve this issue:

• [NoQA] Fix search navigator performance #61781

If no regressions arise, payment will be issued on 2025-05-22. 🎊

For reference, here are some details about the assignees on this issue:

• @sosek108 does not require payment (Contractor)
• @ZhenjaHorbach requires payment through NewDot Manual Requests

[melvin-bot]

@ZhenjaHorbach @alexpensify @ZhenjaHorbach The PR fixing this issue has been merged! The following checklist (instructions) will need to be completed before the issue can be closed. Please copy/paste the BugZero Checklist from here into a new comment on this GH and complete it. If you have the K2 extension, you can simply click: [this button]

[melvin-bot]

The solution for this issue has been 🚀 deployed to production 🚀 in version 9.1.46-12 and is now subject to a 7-day regression period 📆. Here is the list of pull requests that resolve this issue:

• Optimize Reports view to prevent memory leaks after long usage #61771

If no regressions arise, payment will be issued on 2025-05-27. 🎊

For reference, here are some details about the assignees on this issue:

• @sosek108 does not require payment (Contractor)
• @ZhenjaHorbach requires payment through NewDot Manual Requests

[melvin-bot]

@ZhenjaHorbach @alexpensify @ZhenjaHorbach The PR fixing this issue has been merged! The following checklist (instructions) will need to be completed before the issue can be closed. Please copy/paste the BugZero Checklist from here into a new comment on this GH and complete it. If you have the K2 extension, you can simply click: [this button]

[mountiny]

@Nodonisko @sosek108 do you have more PRs for this ticket or can we pay this out and close?

[Nodonisko]

@mountiny Nothing from my side I handed everything to @sosek108

But there is definitely room for more improvement, at least do not recreate search tree on every letter typed.

[mountiny]

that would be useful improvement for sure cc @sosek108

[sosek108]

No PR from my side at this moment.

But there is definitely room for more improvement, at least do not recreate search tree on every letter typed.

Yeah, I have that on my list but I think this is ok to have only one task opened -> #62106

[mountiny]

Yeah so I think we just need to pay out @ZhenjaHorbach could you please post a summary of the PRs to be paid out from this ticket?

[sosek108]

• Optimize Reports view to prevent memory leaks after long usage #61771
• Introduce fixes to Ukkonen tree's method convertToBase26 #61041