expr: Segmentation fault on big inputs

[RenjiSann]

This behaviour happens when the list of inputs is quite large (it starts happening on my machine around N=2850, but it's not absolute.

$ export N=3000
$ cargo run -p uu_expr -- $(seq -s" + " $N)
[1]    2144088 segmentation fault  cargo run -p uu_expr -- $(seq -s" + " $N)

[LouisDISPA]

Hello, I took a quick look into this issue. It seems to be related to the recursion implementation of the algorithm. The stack overflow when there is too much recursions. A quick fix is to use the recursive crate that automatically grow the stack when the function use to much of it. This might not be a viable solution as the platforms support could be limited.

This crate only supports those platforms that stacker supports. The Rust compiler itself uses stacker, so the platform you’re compiling on should always be fine, but for more obscure targets see its documentation.

The real solution is to use an iterative algorithm.

The diff with the recursive crate:

diff --git a/src/uu/expr/Cargo.toml b/src/uu/expr/Cargo.toml
index a16c37a6b..43b39949b 100644
--- a/src/uu/expr/Cargo.toml
+++ b/src/uu/expr/Cargo.toml
@@ -23,6 +23,7 @@ num-traits = { workspace = true }
 onig = { workspace = true }
 uucore = { workspace = true }
 thiserror = { workspace = true }
+recursive = "0.1.1"
 
 [[bin]]
 name = "expr"
diff --git a/src/uu/expr/src/syntax_tree.rs b/src/uu/expr/src/syntax_tree.rs
index 149f24bb2..f0747866e 100644
--- a/src/uu/expr/src/syntax_tree.rs
+++ b/src/uu/expr/src/syntax_tree.rs
@@ -8,6 +8,7 @@
 use num_bigint::{BigInt, ParseBigIntError};
 use num_traits::{ToPrimitive, Zero};
 use onig::{Regex, RegexOptions, Syntax};
+use recursive::recursive;
 
 use crate::{ExprError, ExprResult};
 
@@ -375,6 +376,7 @@ impl AstNode {
         })
     }
 
+    #[recursive]
     pub fn eval(&self) -> ExprResult<NumOrStr> {
         match self {
             Self::Evaluated { value } => Ok(value.clone()),

[RenjiSann]

How, I didn't think it would be that. Making the code iterative is indeed the more robust solution

[LouisDISPA]

I have 2 solutions that makes the code iterative with minimal changes by keeping the recursive logic. One is safer but with the decurse crate. And one less safe by using 2 vectors to store the stack informations.

I'll open a PR soon.