Bash – eval limitation with piped commands

bashpipeshell

We have a shell script that builds a long piped command chain in a variable and executes it with eval (the following code is simplified to the essential):

 cmd="cat /some/files | grep -v \"this\" | grep -v \"that\""
 cmd="$cmd | grep -v \"much more dynamical filter with variables\""
 ...
 result=`eval $cmd`

All worked fine so far but now it seems that the content of the cmd variable exceeds a limit. When it exceeds about 95970 bytes I will receive the error (although syntax is correct):

eval: line ...: syntax error near unexpected token `|'

I did some research, but I didn't get a clue (getconf ARG_MAX echoes 2621440, ulimit -a doesn't helped me, too).

Could someone please explain which limit this could be and maybe how to increase the limit or what is the best way to avoid it?

EDIT: I have tested it now on three different servers (centos) with a designated script. On all servers I ended up reaching 3333 pipes in one command with eval.

And I have found another page where someone experienced the same but without eval. So it seems to be just a limit of pipes.

Knowing that the limitation is probably caused by the number of pipes will help me to workaround the problem. So this is not the question anymore.

But I am still interested in how this limit is set or at least how to detect the value of the limit (probably not on every system 3333) without running a script for that.

It can be reproduced with:

yes cat | head -n 3334 | paste -sd '|' - | bash

Best Answer

The problem here is actually an issue with the bash parser. There is no workaround other than editing and recompiling bash, and the 3333 limit is likely to be the same on all platforms.

The bash parser is generated with yacc (or, typically, with bison but in yacc mode). yacc parsers are bottom-up parsers, using the LALR(1) algorithm which builds a finite state machine with a pushdown stack. Loosely speaking, the stack contains all not-yet-reduced symbols, along with enough information to decide which productions to use to reduce the symbols.

Such parsers are optimized for left-recursive grammar rules. In the context of an expression grammar, a left-recursive rule applies to a left-associative operator, such as a−b in ordinary mathematics. That's left associative because the expression a−b−c groups ("associates") to the left, making it equal to (a−b)−c rather than a−(b−c). By contrast, exponentiation is right-associative, so that a^{b^c} is by convention evaluated as a^{(b^c)} rather than (a^b)^{^c}.

bash operators are process operators, rather than arithmetic operators; these include short-circuit booleans (&& and ||) and pipes (| and |&), as well as sequencing operators ; and &. Like mathematical operators, most of these associate to the left, but the pipe operators associate to the right, so that cmd1 | cmd2 | cmd3 is parsed as though it were cmd1 | { cmd2 | cmd3 ; } as opposed to { cmd1 | cmd2 ; } | cmd3. (Most of the time the difference is not important, but it is observable. [See Note 1])

To parse an expression which is a sequence of left associative operators, you only need a small parser stack. Every time you hit an operator, you can reduce (parenthesize, if you like) the expression to the left of it. By contrast, parsing an expression which is a sequence of right associative operators requires that you put all of the symbols onto the parser stack until you reach the end of the expression, because only then can you start reducing (inserting parentheses). (That explanation involves quite a bit of hand-waving, since it was intended to be non-technical, but it is based on the working of the real algorithm.)

Yacc parsers will resize their parser stack at runtime, but there is a compile-time maximum stack size, which by default is 10000 slots. If the stack reaches the maximum size, any attempt to expand it will trigger an out-of-memory error. Because | is right associative, an expression of the form:

statement | statement | ... | statement

will eventually trigger this error. If it were parsed in the obvious way, that would happen after 5,000 pipe symbols (with 5,000 statements). But because of the way the bash parser handles newlines, the actual grammar used is (roughly):

pipeline: command '|' optional_newlines pipeline

with the consequence that there is an optional_newlines grammar symbol after every |, so each pipe occupies three stack slots. Hence, the out-of-memory error is generated after 3,333 pipe symbols.

The yacc parser detects and signals the stack overflow, which it signals by calling yyerror("memory exhausted"). However, the bash implementation of yyerror tosses away the provided error message, and substitutes a message like "syntax error detected near unexpected token...". That's a bit confusing in this case.

Notes

The difference in associativity is most easily observed using the |& operator, which pipes both stderr and stdout. (Or, more accurately, duplicates stdout into stderr after establishing the pipe.) For a simple example, suppose that the file foo does not exist in the current directory. Then

# There is a race condition in this example. But it's not relevant.
$ ls foo | ls foo |& tr n-za-m a-z
ls: cannot access foo: No such file or directory
yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel
# Associated to the left:
$ { ls foo | ls foo ; } |& tr n-za-m a-z
yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel
yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel
# Associated to the right:
$ ls foo | { ls foo |& tr n-za-m a-z ; }
ls: cannot access foo: No such file or directory
yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel

Related Solutions

Bash – Variable as command; eval vs bash -c

eval "$1" executes the command in the current script. It can set and use shell variables from the current script, set environment variables for the current script, set and use functions from the current script, set the current directory, umask, limits and other attributes for the current script, and so on. bash -c "$1" executes the command in a completely separate script, which inherits environment variables, file descriptors and other process environment (but does not transmit any change back) but does not inherit internal shell settings (shell variables, functions, options, traps, etc.).

There is another way, (eval "$1"), which executes the command in a subshell: it inherits everything from the calling script but does not transmit any change back.

For example, assuming that the variable dir isn't exported and $1 is cd "$foo"; ls, then:

cd /starting/directory; foo=/somewhere/else; eval "$1"; pwd lists the content of /somewhere/else and prints /somewhere/else.
cd /starting/directory; foo=/somewhere/else; (eval "$1"); pwd lists the content of /somewhere/else and prints /starting/directory.
cd /starting/directory; foo=/somewhere/else; bash -c "$1"; pwd lists the content of /starting/directory (because cd "" doesn't change the current directory) and prints /starting/directory.

Bash – Is it safe to eval $BASH_COMMAND

One possibility is to make a wrapper function that will at the same time print the command and execute it, as follows:

debug() {
    # This function prints (to stdout) its arguments and executes them
    local args=() idx=0 IFS=' ' c
    for c; do printf -v args[idx++] '%q' "$c"; done
    printf "%s\n" "${args[*]}"
    # Execute!
    "$@"
}

So that in your script you can do:

debug echo "$ARG"

No need to fiddle with the trap. The drawback is that it adds some debug keywords all over your code (but that should be fine, it's common to have such stuff, like asserts, etc.).

You can even add a global variable DEBUG and modify the debug function like so:

debug() {
    # This function prints (to stdout) its arguments if DEBUG is non-null
    # and executes them
    if [[ $DEBUG ]]; then
        local args=() idx=0 IFS=' ' c
        for c; do printf -v args[idx++] '%q' "$c"; done
        printf "%s\n" "${args[*]}"
    fi
    # Execute!
    "$@"
}

Then you can call your script as:

$ DEBUG=yes ./myscript

$ DEBUG= ./myscript

or just

$ ./myscript

depending whether you want to have the debug info or not.

I capitalized the DEBUG variable because it should be treated as an environment variable. DEBUG is a trivial and common name, so this might clash with other commands. Maybe call it GNIOURF_DEBUG or MARTIN_VON_WITTICH_DEBUG or UNICORN_DEBUG if you like unicorns (and then you probably like ponies too).

Note. In the debug function, I carefully formatted each argument with printf '%q' so that the output will be correctly escaped and quoted so as to be reusable verbatim with a direct copy and paste. It will also show you exactly what the shell saw as you'll be able to figure out each argument (in case of spaces or other funny symbols). This function also uses direct assignment with the -v switch of printf so as to avoid unnecessary subshells.

Best Answer

Notes

Related Solutions

Bash – Variable as command; eval vs bash -c

Bash – Is it safe to eval $BASH_COMMAND

Related Question