feat: speed up resolving by including optional resolver hints

[LisoUseInAIKyrios]

Type

Functionality

Issue

Everytime resolving happens, it searches thru all classes and methods until it finds a match.

But since most patches work only for a few app versions, that means the match for the fingerprint can found, saved, and then bundled with the patch data.

Then on future patching attempts, the previously found class/method can be used as a 'hint' during resolving and the hinted class is tried first.

In other words, first try resolving a method signature against the class listed in the patch resolver hints. And then only if the hinted class / method does not match (ie: patching a non target app version, or a patch was changed but the hints file is not yet updated), then and only then search thru all the classes as usual.

Feature

Add an optional patcher flag 'save resolving hints'. When enabled, after finding a match for each method signature, record which class/method it matched against.

After patching completes, write out to a separate file the class and/or method each signature matched to. This hint file could support only a single target app version to keep the file simple and lightweight - no hassle of managing multiple app versions in the hints file.

Stick this generated file somewhere in the patches project, and when building include it with the patches jar file.

This creation of this 'resolver hints' would need to be done by a developer (and not automated here on GitHub), since it would require the target apk.

The only maintenance to this file, is the developer would update the resolver hints file before a merging a branch with lots of patch changes (ie: before merging dev to main), or when the preferred target app version changes.

This feature probably should not be used for apps with only a few patches (little performance gain for the cost of manually checking in a generated file). Similarly this feature should not be used for apps with no target version.

But for YouTube or any app with more than a dozen patches and a single preferred target app version, this feature could dramatically speed up the patching process.

Motivation

Speed up the patching process for both developers and the end users.

Additional context

No response

Acknowledgements

• I have searched the existing issues and this is a new and no duplicate or related to another open issue.
• I have written a short but informative title.
• I filled out all of the requested information in this issue properly.

[oSumAtrIX]

Multiple techniques can be used. One that comes to mind is, for example, using a breadth-first search through classes starting at the approximate location of a method. The reason is that members of classes often either stay in the same classes or shift to the next or previous class, depending on the change. This approach may not work in all cases; in that case, other metadata would be needed to collect enough "resolver hints."

[LisoUseInAIKyrios]

I wrote up a proof of concept, found here:
https://github.com/LisoUseInAIKyrios/revanced-patcher/tree/cached_resolving

And the performance improvements are quite noticeable.

Before (without cached resolving):

INFO: Reading dex files 
NFO: Resolving classes using no hints 
INFO: Decoding AndroidManifest.xml only, because resources are not needed 
-- default patches applied --
INFO: Compiling resources 
INFO: Writing modified dex files 
INFO: Aligning youtube.apk to revanced_aligned.apk 
INFO: Signing revanced_aligned.apk to revanced_signed.apk 
INFO: Found existing keystore: revanced.keystore 
INFO: Copying revanced_signed.apk to revanced.apk 
INFO: Cleaned up cache directory 
INFO: Finished 
Elapsed time: 62 seconds

After (with cached resolving):

INFO: Reading dex files 
INFO: Resolving classes using cached lookup hints 
INFO: Decoding AndroidManifest.xml only, because resources are not needed 
-- default patches applied --
INFO: Compiling resources 
INFO: Writing modified dex files 
INFO: Aligning youtube.apk to revanced_aligned.apk 
INFO: Signing revanced_aligned.apk to revanced_signed.apk 
INFO: Found existing keystore: revanced.keystore 
INFO: Copying revanced_signed.apk to revanced.apk 
INFO: Cleaned up cache directory 
INFO: Finished 
Elapsed time: 40 seconds

[indrastorms]

Isn't it implemented long ago?

[LisoUseInAIKyrios]

Isn't it implemented long ago?

I implemented it a while ago on the branch listed above, and I used it for a while as it did speed things up a lot.

But since then the patching process has been sped up in other ways, and the benefit of this change is not a big difference anymore. I've stopped merging changes to it since the time spent continually merging was greater than the 5-10 seconds saved during patching everytime.

The only thing I still find useful, is the json method lookup file makes it very easy to inspect a patched apk because it lists what class/method each fingerprint resolved to. But that alone could be added separately without the need for a persistent lookup map. It could even be a standard output file in the build temp directory, to remove the need for extra patcher options.

A better use might be to add KMP searching to the opcode pattern matching. It's a great candidate because KMP works best when a search pattern has many repeating or common substrings, which definitely is the case with op codes and it's copy paste like patterns that appear. But that idea is outside of this issue.