StackOverflowError in CatmullRomSpline.generateSamples #131246
Description
Is there an existing issue for this?
- I have searched the existing issues
- I have read the guide to filing a bug
Steps to reproduce
I am using CatMullRomSpline to generate a smooth path that goes between some points.
In production, I see rare StackoverflowErrors thrown in CatmullRomSpline.generateSamples (
This is the Stacktrace:
StackOverflowError: Stack Overflow
File "curves.dart", in CatmullRomSpline._initializeIfNeeded
File "curves.dart", in CatmullRomSpline.transformInternal
File "curves.dart", in ParametricCurve.transform
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples.sample
... (repeated many times)
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples.sample
File "curves.dart", in Curve2D.generateSamples
File "graph_line_events_painter.dart", in drawSmoothPath
File "graph_line_events_painter.dart", in GraphLineAndEventsPainter.paint
File "custom_paint.dart", in RenderCustomPaint._paintWithPainter
File "custom_paint.dart", in RenderCustomPaint.paint
File "object.dart", in RenderObject._paintWithContext
File "object.dart", in PaintingContext.paintChild
File "layout_builder.dart", in _RenderLayoutBuilder.paint
File "object.dart", in RenderObject._paintWithContext
File "object.dart", in PaintingContext._repaintCompositedChild
File "object.dart", in PipelineOwner.flushPaint
File "binding.dart", in RendererBinding.drawFrame
File "binding.dart", in WidgetsBinding.drawFrame
File "binding.dart", in RendererBinding._handlePersistentFrameCallback
File "binding.dart", in SchedulerBinding._invokeFrameCallback
File "binding.dart", in SchedulerBinding.handleDrawFrame
File "binding.dart", in SchedulerBinding._handleDrawFrame
File "hooks.dart", in _invoke
File "platform_dispatcher.dart", in PlatformDispatcher._drawFrame
File "hooks.dart", in _drawFrame
This only seems to happen rarely with specific values, I did not find a way to reproduce it yet.
I am using a tolerance value of 0.1 (much higher than the default of 1e-10), so the recursion should not go that deep.
This is either a bug in the sample function of CatmullRomspline, where the recursion cannot progress for some reason, or the recursive implementation is just prone to stack overflow errors.
I suspect it's the latter, and suggest to to use a Stack to avoid relying o the callstack.
e.g. instead of
void sample(Curve2DSample p, Curve2DSample q, {bool forceSubdivide = false}) {
// Pick a random point somewhat near the center, which avoids aliasing
// problems with periodic curves.
final double t = p.t + (0.45 + 0.1 * rand.nextDouble()) * (q.t - p.t);
final Curve2DSample r = Curve2DSample(t, transform(t));
if (!forceSubdivide && isFlat(p.value, q.value, r.value)) {
samples.add(q);
} else {
sample(p, r);
sample(r, q);
}
}
use something like
void sample(Curve2DSample p, Curve2DSample q, {bool forceSubdivide = false}) {
List<Curve2DSample> stack = [q, p]; // Stack for non-recursive DFS
while (stack.isNotEmpty) {
Curve2DSample q = stack.removeLast();
Curve2DSample p = stack.removeLast();
// Pick a random point somewhat near the center, which avoids aliasing
// problems with periodic curves.
final double t = p.t + (0.45 + 0.1 * rand.nextDouble()) * (q.t - p.t);
final Curve2DSample r = Curve2DSample(t, transform(t));
if (!forceSubdivide && isFlat(p.value, q.value, r.value)) {
samples.add(q);
} else {
stack.add(q);
stack.add(r);
stack.add(r);
stack.add(p);
}
}
}Expected results
The function call should not overflow within reasonable sample lenghts and such a high tolerance.
Actual results
It overflows the call stack
Code sample
I am unable to produce a minimal reproducible sample at this time, as I only have cash reports.
Flutter Doctor output
Doctor output
[!] Flutter (Channel stable, 3.10.3, on macOS 13.4.1 22F770820d darwin-arm64, locale en-GB)
• Flutter version 3.10.3 on channel stable at /Users/kami/fvm/versions/3.10.3
! Warning: `flutter` on your path resolves to /Users/kami/fvm/versions/stable/bin/flutter, which is not inside your current Flutter SDK checkout at /Users/kami/fvm/versions/3.10.3. Consider adding /Users/kami/fvm/versions/3.10.3/bin to the front of your path.
! Warning: `dart` on your path resolves to /Users/kami/fvm/versions/stable/bin/dart, which is not inside your current Flutter SDK checkout at /Users/kami/fvm/versions/3.10.3. Consider adding /Users/kami/fvm/versions/3.10.3/bin to the front of your path.
• Upstream repository https://github.com/flutter/flutter.git
• Framework revision f92f44110e (8 weeks ago), 2023-06-01 18:17:33 -0500
• Engine revision 2a3401c9bb
• Dart version 3.0.3
• DevTools version 2.23.1
• If those were intentional, you can disregard the above warnings; however it is recommended to use "git" directly to perform update checks and upgrades.
[✓] Android toolchain - develop for Android devices (Android SDK version 30.0.3)
• Android SDK at /Users/kami/Library/Android/sdk
• Platform android-33, build-tools 30.0.3
• Java binary at: /Applications/Android Studio.app/Contents/jbr/Contents/Home/bin/java
• Java version OpenJDK Runtime Environment (build 17.0.6+0-17.0.6b802.4-9586694)
• All Android licenses accepted.
[✓] Xcode - develop for iOS and macOS (Xcode 14.2)
• Xcode at /Applications/Xcode.app/Contents/Developer
• Build 14C18
• CocoaPods version 1.12.1
[✓] Chrome - develop for the web
• Chrome at /Applications/Google Chrome.app/Contents/MacOS/Google Chrome
[✓] Android Studio (version 2022.2)
• Android Studio at /Applications/Android Studio.app/Contents
• Flutter plugin can be installed from:
🔨 https://plugins.jetbrains.com/plugin/9212-flutter
• Dart plugin can be installed from:
🔨 https://plugins.jetbrains.com/plugin/6351-dart
• Java version OpenJDK Runtime Environment (build 17.0.6+0-17.0.6b802.4-9586694)
[✓] IntelliJ IDEA Community Edition (version 2021.3)
• IntelliJ at /Applications/IntelliJ IDEA CE.app
• Flutter plugin can be installed from:
🔨 https://plugins.jetbrains.com/plugin/9212-flutter
• Dart plugin can be installed from:
🔨 https://plugins.jetbrains.com/plugin/6351-dart
[✓] VS Code (version 1.80.0)
• VS Code at /Applications/Visual Studio Code.app/Contents
• Flutter extension version 3.68.0
[✓] VS Code (version 1.79.0-insider)
• VS Code at /Applications/Visual Studio Code - Insiders.app/Contents
• Flutter extension can be installed from:
🔨 https://marketplace.visualstudio.com/items?itemName=Dart-Code.flutterMetadata
Metadata
Assignees
Labels
Important issues not at the top of the work listError messages from the Flutter frameworkIssues experienced in live production appsStack traces logged to the consoleUI glitches reported at the engine/skia or impeller rendering levelflutter/packages/flutter repository. See also f: labels.Issue is closed as already fixed in a newer versionOwned by Framework teamTriaged by Framework teamA fix is in flight