fix(assertions): stack overflow while parsing template#26767
fix(assertions): stack overflow while parsing template#26767mergify[bot] merged 2 commits intoaws:mainfrom
Conversation
aws-cdk-automation
left a comment
There was a problem hiding this comment.
The pull request linter has failed. See the aws-cdk-automation comment below for failure reasons. If you believe this pull request should receive an exemption, please comment and provide a justification.
A comment requesting an exemption should contain the text Exemption Request. Additionally, if clarification is needed add Clarification Request to a comment.
|
exemption request please 🙂 |
| }).toThrow(/dependency cycle/); | ||
| }); | ||
|
|
||
| test('throws when given a more complex template with cyclic dependencies', () => { |
There was a problem hiding this comment.
While i can see how the change in cyclic.ts makes the recurse function more efficient, this test isn't going to show that one way or another right? the test will succeed with the old code as well?
I'm prepared to just approve as is anyway, because this looks low risk and is hard to test, but want to make sure i have the whole picture first.
There was a problem hiding this comment.
I initially ran the test with the old code (unchanged) and it fails for me because of a stackoverflow error.
I think the call stack in the test case I added ends up looking like this (without the fix applied):
findCycle(deps)
recurse("Res1", ["Res1"])
recurse("Res2", ["Res1", "Res2"])
recurse("Res3", ["Res1", "Res2", "Res3"])
recurse("Res2", ["Res1", "Res2", "Res3", "Res2"])
recurse("Res3", ["Res1", "Res2", "Res3", "Res2", "Res3"])
...
✅ Updated pull request passes all PRLinter validations. Dismissing previous PRLinter review.
|
@kaizencc I updated the description 🙏 |
|
Thank you for contributing! Your pull request will be updated from main and then merged automatically (do not update manually, and be sure to allow changes to be pushed to your fork). |
AWS CodeBuild CI Report
Powered by github-codebuild-logs, available on the AWS Serverless Application Repository |
|
Thank you for contributing! Your pull request will be updated from main and then merged automatically (do not update manually, and be sure to allow changes to be pushed to your fork). |
Closes #26766
The function
findCycletries to find a cycle by using a depth-first search (DFS). The DFS is implemented recursively in the recurse function. For each node, it tries to find a path that eventually leads back to the start of the path. If such a path is found, a cycle exists, and the nodes forming this cycle are returned.One of the bugs in the current implementation is that it only checks whether the current dependency
depis equal to the first node of the current pathpath[0]. This means it will only detect a cycle if the cycle includes the first node of the search, which might not always be the case.To fix this, the function should check whether the current dependency
depis already somewhere in the current pathpath. If it is, then a cycle has been found.By submitting this pull request, I confirm that my contribution is made under the terms of the Apache-2.0 license