ash: parser: Add syntax stack for recursive parsing

This closes 10821.

Upstream patch:

    From: Herbert Xu <herbert@gondor.apana.org.au>
    Date: Fri, 9 Mar 2018 00:14:02 +0800
    parser: Add syntax stack for recursive parsing

    Without a stack of syntaxes we cannot correctly these two cases
    together:

            "${a#'$$'}"
            "${a#"${b-'$$'}"}"

    A recursive parser also helps in some other corner cases such
    as nested arithmetic expansion with paratheses.

    This patch adds a syntax stack allocated from the stack using
    alloca.  As a side-effect this allows us to remove the naked
    backslashes for patterns within double-quotes, which means that
    EXP_QPAT also has to go.

    This patch also fixes removes any backslashes that precede right
    braces when they are present within a parameter expansion context,
    and backslashes that precede double quotes within inner double
    quotes inside a parameter expansion in a here-document context.

    The idea of a recursive parser is based on a patch by Harald van
    Dijk.

    Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

var_bash3, var_bash4 and var_bash6 tests are updated
with the output given by bash-4.3.43

With this patch, the following tests now pass for ash:

    dollar_repl_slash_bash2.tests
    squote_in_varexp2.tests
    squote_in_varexp.tests
    var_bash4.tests

function                                             old     new   delta
readtoken1                                          2615    2874    +259
synstack_push                                          -      54     +54
evalvar                                              574     571      -3
rmescapes                                            330     310     -20
subevalvar                                          1279    1258     -21
argstr                                              1146    1107     -39
------------------------------------------------------------------------------
(add/remove: 1/0 grow/shrink: 1/4 up/down: 313/-83)           Total: 230 bytes

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

10 files changed, 18 insertions, 12 deletions

diff --git a/shell/ash_test/ash-arith/arith_nested1.right b/shell/ash_test/ash-arith/arith_nested1.right
new file mode 100644
index 000000000..d00491fd7
--- /dev/null
+++ b/shell/ash_test/ash-arith/arith_nested1.right
@@ -0,0 +1 @@
+1
diff --git a/shell/ash_test/ash-arith/arith_nested1.tests b/shell/ash_test/ash-arith/arith_nested1.tests
new file mode 100755
index 000000000..28571b833
--- /dev/null
+++ b/shell/ash_test/ash-arith/arith_nested1.tests
@@ -0,0 +1 @@
+echo $(( ( $((1)) ) ))
diff --git a/shell/ash_test/ash-quoting/squote_in_varexp3.right b/shell/ash_test/ash-quoting/squote_in_varexp3.right
new file mode 100644
index 000000000..223b7836f
--- /dev/null
+++ b/shell/ash_test/ash-quoting/squote_in_varexp3.right
@@ -0,0 +1 @@
+B
diff --git a/shell/ash_test/ash-quoting/squote_in_varexp3.tests b/shell/ash_test/ash-quoting/squote_in_varexp3.tests
new file mode 100755
index 000000000..028a88fd9
--- /dev/null
+++ b/shell/ash_test/ash-quoting/squote_in_varexp3.tests
@@ -0,0 +1 @@
+x=\'B; echo "${x#\'}"
diff --git a/shell/ash_test/ash-vars/var_bash3.right b/shell/ash_test/ash-vars/var_bash3.right
index a97c850ea..8899d981c 100644
--- a/shell/ash_test/ash-vars/var_bash3.right
+++ b/shell/ash_test/ash-vars/var_bash3.right
@@ -1,6 +1,6 @@
 1 a041#c
 2 a041#c
-3 a\041#c
+3 a041#c
 4 a\041#c
 5 a\041#c
 6 a\041#c
@@ -17,4 +17,4 @@
 17 a\tc
 18 a\tc
 19 atc
-20 a\tc
+20 atc
diff --git a/shell/ash_test/ash-vars/var_bash4.right b/shell/ash_test/ash-vars/var_bash4.right
index 0ef1bf661..9067e58e6 100644
--- a/shell/ash_test/ash-vars/var_bash4.right
+++ b/shell/ash_test/ash-vars/var_bash4.right
@@ -3,26 +3,26 @@ Replace str:   _\\_\z_
 Pattern:       single backslash and star: "replace literal star"
 Unquoted:      a_\_z_b\*c
 Unquoted =:    a_\_z_b\*c
-Quoted:        a_\_\z_b\*c
-Quoted =:      a_\_\z_b\*c
+Quoted:        a_\_z_b\*c
+Quoted =:      a_\_z_b\*c
 Pattern:       double backslash and star: "replace backslash and everything after it"
 Unquoted:      a*b_\_z_
 Unquoted =:    a*b_\_z_
-Quoted:        a*b_\_\z_
-Quoted =:      a*b_\_\z_
+Quoted:        a*b_\_z_
+Quoted =:      a*b_\_z_
 
 Source:        a\bc
 Replace str:   _\\_\z_
 Pattern:       single backslash and b: "replace b"
 Unquoted:      a\_\_z_c
 Unquoted =:    a\_\_z_c
-Quoted:        a\_\_\z_c
-Quoted =:      a\_\_\z_c
+Quoted:        a\_\_z_c
+Quoted =:      a\_\_z_c
 Pattern:       double backslash and b: "replace backslash and b"
 Unquoted:      a_\_z_c
 Unquoted =:    a_\_z_c
-Quoted:        a_\_\z_c
-Quoted =:      a_\_\z_c
+Quoted:        a_\_z_c
+Quoted =:      a_\_z_c
 
 Source:        a\bc
 Replace str:   _\\_\z_ (as variable $s)
diff --git a/shell/ash_test/ash-vars/var_bash6.right b/shell/ash_test/ash-vars/var_bash6.right
index 63fc23df8..115ff8b04 100644
--- a/shell/ash_test/ash-vars/var_bash6.right
+++ b/shell/ash_test/ash-vars/var_bash6.right
@@ -1,5 +1,5 @@
 Expected Actual
 a*z    : a*z
-\z     : \z
+z      : z
 a1z a2z: a1z a2z
 z      : z
diff --git a/shell/ash_test/ash-vars/var_bash6.tests b/shell/ash_test/ash-vars/var_bash6.tests
index cf2e4f020..686834177 100755
--- a/shell/ash_test/ash-vars/var_bash6.tests
+++ b/shell/ash_test/ash-vars/var_bash6.tests
@@ -3,7 +3,7 @@
 >a1z; >a2z;
           echo 'Expected' 'Actual'
 v='a bz'; echo 'a*z    :' "${v/a*z/a*z}"
-v='a bz'; echo '\z     :' "${v/a*z/\z}"
+v='a bz'; echo 'z      :' "${v/a*z/\z}"
 v='a bz'; echo 'a1z a2z:' ${v/a*z/a*z}
 v='a bz'; echo 'z      :' ${v/a*z/\z}
 rm a1z a2z
diff --git a/shell/ash_test/ash-vars/var_bash7.right b/shell/ash_test/ash-vars/var_bash7.right
new file mode 100644
index 000000000..223b7836f
--- /dev/null
+++ b/shell/ash_test/ash-vars/var_bash7.right
@@ -0,0 +1 @@
+B
diff --git a/shell/ash_test/ash-vars/var_bash7.tests b/shell/ash_test/ash-vars/var_bash7.tests
new file mode 100755
index 000000000..c4ce03f7f
--- /dev/null
+++ b/shell/ash_test/ash-vars/var_bash7.tests
@@ -0,0 +1 @@
+x=AB; echo "${x#$'\x41'}"