[Toybox] expr / test / find

[Andy Chu]

I'm forking this thread to discuss this one part of Rob's message:

"""
I want to genericize find.c plumbing to have expr.c and maybe test.c do
parenthesization and prioritization and such the same way, but despite
sitting down to think it through more than once haven't come up with a
clean way to factor out the common code yet. I should just do expr.c and
then try to cleanup common code (if any) afterwards. (Yes there's an
expr.c in pending, and when I sat down to try to clean it up I hit
http://landley.net/notes-2014.html#02-12-2014 and then
http://landley.net/notes-2015.html#30-01-2015 and and it's on the todo
list.)
"""

I just sent a patch to fix the operator precedence in expr.c.  There
are 3-4 possible algorithms, but precedence climbing definitely
results in the fewest lines of code, and I think is elegant.

https://en.wikipedia.org/wiki/Operator-precedence_parser

FWIW busybox and coreutils expr both use recursive descent, with a
function per precedence level.

The algorithm that was already there seemed kinda like precedence
climbing, except that it didn't have equivalent levels.  So the
problem is that * and / are not associative because / is INTEGER
division (while + and - are associative).

The algorithm is small, and I don't think C is a good language for
common algorithms... I am interested in doing 'test' though after I
fix the remaining bugs in expr.  test does not implement compound
expressions yet: AND (-a) / OR (-o) / ! / ().  I think it can be done
in the same style as expr and there won't be too much duplication.

FWIW I looked at the expression parsing in "find" and was a bit
confused... It's hard to tell if it actually implemented precedence of
-a and -o.  Though I guess I can just test it...

BTW, coreutils is retarded and + is actually ALSO an escaping
character for reserved words like "match", which toybox doesn't have.
I have NO IDEA why they chose +, since that's also an operator.

That's why ni coreutils:

expr match  # syntax error, operator has no arg
expr + match => match  # escaped operator as string

expr + 1 => 1 # works, escaping 1
expr - 1  # syntax error, - is binary operator

expr +1 => +1  # because this is a single string token


expr +  # syntax error, nothing follows the escape operator
expr - => -
expr * => *   # etc.  these are treated as literal strings and not operators
expr a => a


With all these WTFs, I'm beginning to see why toybox is a masochistic
project :)  But thankfully this + escaping char is not in POSIX, and
we don't need it because we don't have match / index / substr /
length.

Andy