Stack overflow error when generating hashes

[JaimeLennox]

Hello!

After updating to 2.4.0, we've started seeing StackOverflowErrors when running generate-hashes (using modified-filepaths):

Exception in thread "main" java.lang.StackOverflowError
	at java.base/java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3963)
	at java.base/java.util.regex.Pattern$GroupHead.match(Pattern.java:4804)
	at java.base/java.util.regex.Pattern$Branch.match(Pattern.java:4749)
	at java.base/java.util.regex.Pattern$Branch.match(Pattern.java:4747)
	at java.base/java.util.regex.Pattern$Branch.match(Pattern.java:4747)
	at java.base/java.util.regex.Pattern$BranchConn.match(Pattern.java:4713)
	at java.base/java.util.regex.Pattern$GroupTail.match(Pattern.java:4863)
	at java.base/java.util.regex.Pattern$BmpCharPropertyGreedy.match(Pattern.java:4344)
	at java.base/java.util.regex.Pattern$GroupHead.match(Pattern.java:4804)
	at java.base/java.util.regex.Pattern$Branch.match(Pattern.java:4749)
	at java.base/java.util.regex.Pattern$Branch.match(Pattern.java:4747)
	at java.base/java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3964)
	at java.base/java.util.regex.Pattern$Start.match(Pattern.java:3619)
	at java.base/java.util.regex.Matcher.search(Matcher.java:1729)
	at java.base/java.util.regex.Matcher.find(Matcher.java:773)
	at java.base/java.util.Formatter.parse(Formatter.java:2702)
	at java.base/java.util.Formatter.format(Formatter.java:2655)
	at java.base/java.util.Formatter.format(Formatter.java:2609)
	at java.base/java.lang.String.format(String.java:2897)
	at com.bazel_diff.BazelRuleImpl.transformRuleInput(BazelRule.java:53)
	at com.bazel_diff.BazelRuleImpl.lambda$getRuleInputList$0(BazelRule.java:38)
	at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:195)
	at java.base/java.util.AbstractList$RandomAccessSpliterator.forEachRemaining(AbstractList.java:720)
	at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:484)
	at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:474)
	at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:913)
	at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
	at java.base/java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:578)
	at com.bazel_diff.BazelRuleImpl.getRuleInputList(BazelRule.java:39)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:101)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
	at com.bazel_diff.TargetHashingClientImpl.createDigestForRule(TargetHashingClient.java:106)
       (etc)

I had a look at the code and saw the recursive call in createDigestForRule which seems to be the culprit, however I'm also curious if we might be doing something wrong to get into this state, since I've not seen any complaints of similar issues yet.

Any thoughts?

[tinder-maxwellelliott]

Can you put together a small repo to reproduce the problem? I will also investigate on my side.

Also does it work when you use the -a flag on generate-hashes?

[tinder-maxwellelliott]

An aside, I am looking at potentially removing the modified file paths flag as it forks the logic pretty significantly. Is that going to be an issue for you in the future @JaimeLennox ?

[JaimeLennox]

Sure, I'll try and put together something, although since I'm not sure what is causing it for our whole monorepo it might take me a while to get a minimal repro 😅

Is it recommended to use -a instead of modified-filepaths? I was only using that as I thought it would be quicker not to have to hash everything (and -a is also marked as experimental).

[tinder-maxwellelliott]

Sure, I'll try and put together something, although since I'm not sure what is causing it for our whole monorepo it might take me a while to get a minimal repro 😅

Is it recommended to use -a instead of modified-filepaths? I was only using that as I thought it would be quicker not to have to hash everything (and -a is also marked as experimental).

The -a flag is no longer experimental, we use it on every Bazel job and its been very stable. Let me know if it either does not work or is unacceptably slower. Hopefully this can unblock you

[tinder-maxwellelliott]

@JaimeLennox were you able to repro this when using the latest version?

[JaimeLennox]

Unfortunately not - however I did managed to create a repro repo: https://github.com/JaimeLennox/bazel-diff-issue-71

I printed out the rule name that was being recursed into to find out what was going on, and it seems the grpc dependency eventually reaches //external:libuv, which for some reason has a dependency on itself, causing the endless recursion.

I've managed to fix this with this change: https://github.com/JaimeLennox/bazel-diff-issue-71/blob/master/bazel-diff.patch, which I'd be happy to turn into a merge request if it makes sense (it just checks make sure we don't recurse with a rule of the same name).

I'm still not really sure what causes the self-dependency though 😕

[tinder-maxwellelliott]

Unfortunately not - however I did managed to create a repro repo: https://github.com/JaimeLennox/bazel-diff-issue-71

I printed out the rule name that was being recursed into to find out what was going on, and it seems the grpc dependency eventually reaches //external:libuv, which for some reason has a dependency on itself, causing the endless recursion.

I've managed to fix this with this change: https://github.com/JaimeLennox/bazel-diff-issue-71/blob/master/bazel-diff.patch, which I'd be happy to turn into a merge request if it makes sense (it just checks make sure we don't recurse with a rule of the same name).

I'm still not really sure what causes the self-dependency though 😕

Thank you so much for the deep investigation. I would definitely accept that pull request