[RFC PATCH 00/28] cli: Add a new shell

* [RFC PATCH 00/28] cli: Add a new shell
@ 2021-07-01  6:15 Sean Anderson
  2021-07-01  6:15 ` [RFC PATCH 01/28] Add Zlib License Sean Anderson
                   ` (29 more replies)
  0 siblings, 30 replies; 107+ messages in thread
From: Sean Anderson @ 2021-07-01  6:15 UTC (permalink / raw)
  To: u-boot, Tom Rini
  Cc: Marek Behún, Wolfgang Denk, Simon Glass, Roland Gaudig,
	Heinrich Schuchardt, Kostas Michalopoulos, Sean Anderson

Well, this has been sitting on my hard drive for too long without feedback
("Release early, release often"), so here's the first RFC. This is not ready to
merge (see the "Future work" section below), but the shell is functional and at
least partially tested.

The goal is to have 0 bytes gained over Hush. Currently we are around 800 bytes
over on sandbox.

add/remove: 90/54 grow/shrink: 3/7 up/down: 12834/-12042 (792)

= Getting started

Enable CONFIG_LIL. If you would like to run tests, enable CONFIG_LIL_FULL. Note
that dm_test_acpi_cmd_dump and setexpr_test_str_oper will fail. CONFIG_LIL_POOLS
is currently broken (with what appears to be a double free).

For an overview of the language as a whole, refer to the original readme [1].

[1] http://runtimeterror.com/tech/lil/readme.txt

== Key patches

The following patches are particularly significant for reviewing and
understanding this series:

cli: Add LIL shell
	This contains the LIL shell as originally written by Kostas with some
	major deletions and some minor additions.
cli: lil: Wire up LIL to the rest of U-Boot
	This allows you to use LIL as a shell just like Hush.
cli: lil: Document structures
	This adds documentation for the major structures of LIL. It is a good
	place to start looking at the internals.
test: Add tests for LIL
	This adds some basic integration tests and provides some examples of
	LIL code.
cli: lil: Add a distinct parsing step
	This adds a parser separate from the interpreter. This patch is the
	largest original work in this series.
cli: lil: Load procs from the environment
	This allows procedures to be saved and loaded like variables.

= A new shell

This series adds a new shell for U-Boot. The aim is to eventually replace Hush
as the primary shell for all boards which currently use it. Hush should be
replaced because it has several major problems:

- It has not had a major update in two decades, resulting in duplication of
  effort in finding bugs. Regarding a bug in variable setting, Wolfgang remarks

    So the specific problem has (long) been fixed in upstream, and
    instead of adding a patch to our old version, thus cementing the
    broken behaviour, we should upgrade hush to recent upstream code.

    -- Wolfgang Denk [2]

  These lack of updates are further compounded by a significant amount of
  ifdef-ing in the Hush code. This makes the shell hard to read and debug.
  Further, the original purpose of such ifdef-ing (upgrading to a newer Hush)
  has never happened.

- It was designed for a preempting OS which supports pipes and processes. This
  fundamentally does not match the computing model of U-Boot where there is
  exactly one thread (and every other CPU is spinning or sleeping). Working
  around these design differences is a significant cause of the aformentioned
  ifdef-ing.

- It lacks many major features expected of even the most basic shells, such
  as functions and command substitution ($() syntax). This makes it difficult
  to script with Hush. While it is desirable to write some code in C, much code
  *must* be written in C because there is no way to express the logic in Hush.

I believe that U-Boot should have a shell which is more featureful, has cleaner
code, and which is the same size as Hush (or less). The ergonomic advantages
afforded by a new shell will make U-Boot easier to use and customize.

[2] https://lore.kernel.org/u-boot/872080.1614764732@gemini.denx.de/

= Open questions

While the primary purpose of this series is of course to get feedback on the
code I have already written, there are several decisions where I am not sure
what the best course of action is.

- What should be done about 'expr'? The 'expr' command is a significant portion
  of the final code size. It cannot be removed outright, because it is used by
  several builtin functions like 'if', 'while', 'for', etc. The way I see it,
  there are two general approaches to take

  - Rewrite expr to parse expressions and then evaluate them. The parsing could
    re-use several of the existing parse functions like how parse_list does.
    This could reduce code, as instead of many functions each with their own
    while/switch statements, we could have two while/switch statements (one to
    parse, and one to evaluate). However, this may end up increasing code size
    (such as when the main language had evaluation split from parsing).

  - Don't parse infix expressions, and just make arithmetic operators normal
    functions. This would affect ergonomics a bit. For example, instead of

	if {$i < 10} { ... }

    one would need to write

	if {< $i 10} { ... }

    and instead of

	if {$some_bool} { ... }

    one would need to write

	if {quote $some_bool} { ... }

    Though, given how much setexpr is used (not much), this may not be such a
    big price to pay. This route is almost certain to reduce code size.

- How should LIL functions integrate with the rest of U-Boot? At the moment, lil
  functions and procedures exist in a completely separate world from normal
  commands. I would like to integrate them more closely, but I am not sure the
  best way to go about this. At the very minimum, each LIL builtin function
  needs to get its hands on the LIL interpreter somehow. I'd rather this didn't
  happen through gd_t or similar so that it is easier to unit test.
  Additionally, LIL functions expect an array of lil_values instead of strings.
  We could strip them out, but I worry that might start to impact performance
  (from all the copying).

  The other half of this is adding LIL features into regular commands. The most
  important feature here is being able to return a string result. I took an
  initial crack at it [3], but I think with this series there is a stronger
  motivating factor (along with things like [4]).

[3] https://patchwork.ozlabs.org/project/uboot/list/?series=231377
[4] https://patchwork.ozlabs.org/project/uboot/list/?series=251013

= Future work

The series as presented today is incomplete. The following are the major issues
I see with it at the moment. I would like to address all of these issues, but
some of them might be postponed until after first merging this series.

- There is a serious error handling problem. Most original LIL code never
  checked errors. In almost every case, errors were silently ignored, even
  malloc failures! While I have designed new code to handle errors properly,
  there still remains a significant amount of original code which just ignores
  errors. In particular, I would like to ensure that the following categories of
  error conditions are handled:

  - Running out of memory.
  - Access to a nonexistant variable.
  - Passing the wrong number of arguments to a function.
  - Interpreting a value as the wrong type (e.g. "foo" should not have a numeric
    representation, instead of just being treated as 1).

- There are many deviations from TCL with no purpose. For example, the list
  indexing function is named "index" and not "lindex". It is perfectly fine to
  drop features or change semantics to reduce code size, make parsing easier,
  or make execution easier. But changing things for the sake of it should be
  avoided.

- The test suite is rather anemic compared with the amount of code this
  series introduces. I would like to expand it significantly. In particular,
  error conditions are not well tested (only the "happy path" is tested).

- While I have documented all new functions I have written, there are many
  existing functions which remain to be documented. In addition, there is no
  user documentation, which is critical in driving adoption of any new
  programming language. Some of this cover letter might be integrated with any
  documentation written.

- Some shell features such as command repetition and secondary shell prompts
  have not been implemented.

- Arguments to native lil functions are incompatible with U-Boot functions. For
  example, the command

	foo bar baz

  would be passed to a U-Boot command as

	{ "foo", "bar", "baz", NULL }

  but would be passed to a LIL function as

	{ "bar", "baz" }

  This makes it more difficult to use the same function to parse several
  different commands. At the moment this is solved by passing the command name
  in lil->env->proc, but I would like to switch to the U-Boot argument list
  style.

- Several existing tests break when using LIL because they expect no output on
  failure, but LIL produces some output notifying the user of the failure.

- Implement DISTRO_BOOT in LIL. I think this is an important proof-of-concept to
  show what can be done with LIL, and to determine which features should be
  moved to LIL_FULL.

= Why Lil?

When looking for a suitable replacement shell, I evaluated implementations using
the following criteria:

- It must have a GPLv2-compatible license.
- It must be written in C, and have no major external dependencies.
- It must support bare function calls. That is, a script such as 'foo bar'
  should invoke the function 'foo' with the argument 'bar'. This preserves the
  shell-like syntax we expect.
- It must be small. The eventual target is that it compiles to around 10KiB with
  -Os and -ffunction-sections.
- There should be good tests. Any tests at all are good, but a functioning suite
  is better.
- There should be good documentation
- There should be comments in the source.
- It should be "finished" or have only slow development. This will hopefully
  make it easier to port changes.

Notably absent from the above list is performance. Most scripts in U-Boot will
be run once on boot. As long as the time spent evaluating scripts is kept under
a reasonable threshold (a fraction of the time spend initializing hardware or
reading data from persistant storage), there is no need to optimize for speed.

In addition, I did not consider updating Hush from Busybox. The mismatch in
computing environment expectations (as noted in the "New shell" section above)
still applies. IMO, this mismatch is the biggest reason that things like
functions and command substitution have been excluded from the U-Boot's Hush.

== lil

- zLib
- TCL
- Compiles to around 10k with no builtins. To 25k with builtins.
- Some tests, but not organized into a suite with expected output. Some evidence
  that the author ran APL, but no harness.
- Some architectural documentation. Some for each functions, but not much.
- No comments :l
- 3.5k LoC

== picol

- 2-clause BSD
- TCL
- Compiles to around 25k with no builtins. To 80k with builtins.
- Tests with suite (in-language). No evidence of fuzzing.
- No documentation :l
- No comments :l
- 5k LoC

== jimtcl

- 2-clause BSD
- TCL
- Compiles to around 95k with no builtins. To 140k with builtins. Too big...

== boron

- LGPLv3+ (so this is right out)
- REBOL
- Compiles to around 125k with no builtins. To 190k with builtins. Too big...

== libmawk

- GPLv2
- Awk
- Compiles to around 225k. Too big...

== libfawk

- 3-clause BSD
- Uses bison+yacc...
- Awk; As it turns out, this has parentheses for function calls.
- Compiles to around 24-30k. Not sure how to remove builtins.
- Test suite (in-language). No fuzzing.
- Tutorial book. No function reference.
- No comments
- Around 2-4k LoC

== MicroPython

- MIT
- Python (but included for completeness)
- Compiles to around 300k. Too big...

== mruby/c

- 3-clause BSD
- Ruby
- Compiles to around 85k without builtins and 120k with. Too big...

== eLua

- MIT
- Lua
- Build system is a royal pain (custom and written in Lua with external deps)
- Base binary is around 250KiB and I don't want to deal with reducing it

So the interesting/viable ones are
- lil
- picol
- libfawk (maybe)

I started with LIL because it was the smallest. I have found several
issues with LIL along the way. Some of these are addressed in this series
already, while others remain unaddressed (see the section "Future Work").

Sean Anderson (28):
  Add Zlib License
  cli: Add LIL shell
  cli: lil: Replace strclone with strdup
  cli: lil: Remove most functions by default
  cli: lil: Rename some functions to be more like TCL
  cli: lil: Convert some defines to enums
  cli: lil: Simplify callbacks
  cli: lil: Handle commands with dots
  cli: lil: Use error codes
  cli: lil: Add printf-style format helper for errors
  cli: lil: Add several helper functions for errors
  cli: lil: Check for ctrl-c
  cli: lil: Wire up LIL to the rest of U-Boot
  cli: lil: Document structures
  cli: lil: Convert LIL_ENABLE_POOLS to Kconfig
  cli: lil: Convert LIL_ENABLE_RECLIMIT to KConfig
  test: Add tests for LIL
  cli: lil: Remove duplicate function bodies
  cli: lil: Add "symbol" structure
  cli: lil: Add config to enable debug output
  cli: lil: Add a distinct parsing step
  env: Add a priv pointer to hwalk_r
  cli: lil: Handle OOM for hm_put
  cli: lil: Make proc always take 3 arguments
  cli: lil: Always quote items in lil_list_to_value
  cli: lil: Allocate len even when str is NULL in alloc_value_len
  cli: lil: Add a function to quote values
  cli: lil: Load procs from the environment

 Licenses/README   |    1 +
 Licenses/zlib.txt |   14 +
 MAINTAINERS       |    7 +
 cmd/Kconfig       |   52 +-
 cmd/nvedit.c      |    8 +-
 common/Makefile   |    4 +
 common/cli.c      |  118 +-
 common/cli_lil.c  | 4321 +++++++++++++++++++++++++++++++++++++++++++++
 env/callback.c    |    4 +-
 env/flags.c       |    4 +-
 include/cli_lil.h |  202 +++
 include/search.h  |    2 +-
 lib/hashtable.c   |    5 +-
 test/cmd/Makefile |    1 +
 test/cmd/lil.c    |  306 ++++
 15 files changed, 5021 insertions(+), 28 deletions(-)
 create mode 100644 Licenses/zlib.txt
 create mode 100644 common/cli_lil.c
 create mode 100644 include/cli_lil.h
 create mode 100644 test/cmd/lil.c

-- 
2.32.0

^ permalink raw reply	[flat|nested] 107+ messages in thread