#3700 Mysterious error in ssubst

[Neil Strickland]

I am using Maxima 5.43.2 with GCL 2.6.12 under Ubuntu 20.04.1 LTS. (This is what apt gives me as the latest version of maxima. I have not tried any other kind of installation.)

For certain long strings s containing many backslashes, ssubst("\\\\","\\",s) gives

`ssubst': unsuitable start or end position.
 -- an error.

More precisely, I start Maxima, then enter

s : <long thing as specified below>$
ssubst("\\\\","\\",s);
ssubst("\\\\","\\",s);

The first ssubst gives an error as described. The second (identical) ssubst gives an apparently correct answer, with all the backslashes in s doubled up. The string s (which I have tried to minimise) is as follows:

"[0,\"\",\"\\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)\",[[[A,false,\"\\\\(x\\\\)\",\"\"],[A,false,\"\\\\(x\\\\) \\\\(\\\\x\\\\)\",\"\\\\(\\\\x\\\\x\\\\)\\\\(\\\\x\\\\x\\\\x\\\\) \\\\(\\\\x\\\\x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\) \\\\(\\\\x\\\\) \\\\(x\\\\)\"],[A,true,\"\\\\(x\\\\)\",\"\"],[C,false,\"\\\\(x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\)\",\"\\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)\"]],[[C,false,\"\\\\(x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\)\",\"\\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)\"]],[[A,false,\"\\\\(x\\\\)\",\"\"],[A,false,\"\\\\(x\\\\) \\\\(\\\\x\\\\)\",\"\\\\(\\\\x\\\\x\\\\)\\\\(\\\\x\\\\x\\\\x\\\\) \\\\(\\\\x\\\\x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\) \\\\(\\\\x\\\\) \\\\(x\\\\)\"],[A,true,\"\\\\(x\\\\)\",\"\"]],[[C,false,\"\\\\(x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\)\",\"\\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)\"]],[C,false,\"\\\\(x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\)\",\"\\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)\"],\"\\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)\",\"\\\\(x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\)\\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\) \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\)  \\\\(x\\\\) \\\\(x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\) \\\\(x\\\\x\\\\x\\\\x\\\\)  \\\\(x\\\\x\\\\x\\\\x\\\\x\\\\) \\\\(x\\\\)  \\\\(x\\\""

[Neil Strickland]

Actually, here is a much simpler case. If we set s to be a string consisting of the letter "a" repeated 1355 (or more) times, and evaluate ssubst("b","a",s), then we get the same error. So in particular, special properties of the backslash character do not seem to be relevant.

I note that ssubst is defined at line 1129 of /usr/share/maxima/5.43.2/share/stringproc/stringproc.lisp, and that the definition is recursive, with one nested function invocation for each occurrence of the string to be substituted. I am not familiar with the internals of lisp. Is this really executed recursively, or is that optimised away somehow? Is the depth of the recursion likely to be a problem?

[Gunter Königsmann]

That might be a hint: which lisp are you using? Or better: what does the maxima command build_info() return?

Most lisps detect tail-recursive functions and convert them to loops. But not all do so and other types of recursion might not be converted to loops, at all.

[Leo Butler]

Neil, thanks for tracking this down.

Attached is a patched stringproc.lisp (and a diff of the changes).
I have eliminated the recursion in ssubst and replaced it with a while
loop, and I have introduced a minor optimization is ssubstfirst to
prevent a second search.

Can you confirm this works for you?

Thanks,
Leo

[Neil Strickland]

Thanks. I just replaced the file /usr/share/maxima/5.43.2/share/stringproc/stringproc.lisp with the one that you sent me; I am not sure if there is supposed to be a compiled version anywhere. This does indeed eliminate the bug for me. It is not very fast, though; 3 or 4 seconds for a string of length 16384.

[Leo Butler]

Ok, I will push the change and close this report shortly.

The lack of speed must be due to the function creating a fresh string
for each replacement.

Leo

"Neil Strickland" npstrick@users.sourceforge.net writes:

Thanks. I just replaced the file
/usr/share/maxima/5.43.2/share/stringproc/stringproc.lisp with the
one that you sent me; I am not sure if there is supposed to be a
compiled version anywhere. This does indeed eliminate the bug for
me. It is not very fast, though; 3 or 4 seconds for a string of length
16384.

[Neil Strickland]

Output of build_info() is as follows:

Maxima version: "5.43.2"
Maxima build date: "2020-02-21 05:22:38"
Host type: "x86_64-pc-linux-gnu"
Lisp implementation type: "GNU Common Lisp (GCL)"
Lisp implementation version: "GCL 2.6.12"
User dir: "/root/.maxima"
Temp dir: "/tmp"
Object dir: "/root/.maxima/binary/5_43_2/gcl/GCL_2_6_12"
Frontend: false

[Gunter Königsmann]

I personally use the maxima version from https://code.launchpad.net/~maxima-developers/+archive/ubuntu/maxima-nightly, that was compiled using sbcl. It is both newer than your maxima version and has been compiled using sbcl, not gcl. A string consisting of 10000 "a" is replaced to 10000 "b" characters just fine, for me.

=> The problem is either caused by gcl or by using the old maxima version.

[Gunter Königsmann]

Retried it with a string that was 200000 chars long, just to see if sbcl merely has a higher limit. But that worked fine, too.

[Leo Butler]

Fixed in commit 6f40fdce7.