Home

OSH 0.2 - Parsing One Million Lines of Shell

I've released version 0.2 of OSH, a bash-compatible shell:

• https://www.oilshell.org/download/oil-0.2.0.tar.xz (gzip version)

To build and run it, follow the instructions in INSTALL.txt.

Please try it on your shell scripts and report bugs!

Caveat: it's still too big and too slow. However, this release takes the first steps toward rectifying that. Read on for details.

Contributors

This is the first release where someone besides me has changed either the OSH runtime or the test suite. Several others have sent build patches in the past, but I view this as a new milestone.

Looking at the changelog:

• Isaac Carroll fixed OSH behavior when argv[0] is -osh, which is how login shells are invoked.
• He also implemented -e and -h for the test / [ builtin.
• Linus Heckemann contributed a failing spec test case using an expression like ${x:-}.

OSH is well-tested, and a good test case should get us 50% of the way to a fix. So, if you don't have time to dive into the code, I still appreciate patches like this. Fixing OSH bugs is a high priority.

If you're interested in contributing, see the instructions on the Wiki. Let me know if you run into problems.

Other contributions:

• timetoplatypus on lobste.rs contributed an Arch Linux package for OSH. I started a Wiki page listing Oil deployments.

Parser Correctness

I mentioned in the last status update that I want OSH to run the shell scripts that build Alpine Linux. However, I immediately hit two problems:

1. The parser is too slow.
2. I can't optimize the parser before it's correct. Optimizing code with known bugs is a bad idea!

The good news is that this release largely fixes problem #2. I rewrote the wild test harness and fixed all unhandled exceptions uncovered by the "fuzzing". Here are the results:

• /release/0.2.0/test/wild.wwz/

The page above shows OSH parsing over a million lines of shell scripts foudn in the wild. This includes every APKBUILD file in Alpine Linux, which is 5,106 shell scripts totalling 254,565 lines of code.

It also includes:

• Tens of thousands of lines of shell scripts from cloud projects like Kubernetes and Docker.
• Esoteric projects, including multiple Lisp interpreters written in bash.
• The FreeBSD and Minix source trees
• Various shell frameworks and libraries

The OSH Language is Nearly Defined

Given the volume and diversity of the scripts that the OSH can handle, I would say that the OSH language is almost completely defined.

(The architecture of the parser is strict and principled, but the details must be determined empirically. That is, we have to parse many scripts and see what fails.)

The blue box at the top of the wild test results says that there are 229 scripts that OSH can't parse. However, most of these aren't problems with OSH.

I need to sort through these in detail, but many of these are:

• Actual shell syntax errors that OSH should flag.
• Scripts with an .sh extension that aren't shell scripts (e.g. ld-version.sh in the Linux kernel is an Awk script.)
• Shell scripts with invalid code after an exit statement.
• ksh constructs in Illumos and FreeBSD. For example, $(( x > 3.5 )) is a syntax error because we don't support floating point numbers, but ksh does.
• Constructs that I've intentionally defined out of OSH. I started documenting these in a nascent OSH manual.
  • For example, the problem I wrote about with $(( appears in perf-with-kcore.sh in the Linux kernel.

There are still a few OSH bugs, like incorrect parsing of bash's regex literals, but most of the 229 errors have other causes.

Parser Performance: Here Doc Optimization

I uncovered three performance bottlenecks by profiling OSH, described in the last status update.

I addressed the first issue in this release by optimized the parsing of here documents. Surprisingly, I also found correctness errors which led me to change the algorithm. (In the next post, I'll issue a correction to How To Parse Here Documents.)

I also have parser benchmarks that show this change. I made a dummy 0.2.alpha release to compare against the optimized 0.2.0 release:

• /release/0.2.alpha1/benchmarks/osh-parser.wwz/
• /release/0.2.0/benchmarks/osh-parser.wwz/

The bad news is that OSH is hundreds of times slower than other shells. But it got a lot faster! Parsing a configure script went from 14.8 seconds to 8.5 seconds on a fast machine, and from 32.0 to 23.0 seconds on a slow machine!

My goal is for OSH to parse scripts as fast as other shells, while statically parsing the entire program and producting a more detailed representation of it.

Other Changes

Looking at the changelog, here are some other notable changes:

• Miscellaneous features driven by user usage:
  • $UID and $EUID
  • test -r and -w
• Parse the extended glob syntax. (They're not yet interpreted by the OSH runtime.)
• Statically parse assignments more accurately. declare x=1 and readonly x=1 are parsed differently than declare -p or readonly -p. The former are assignment statements; the latter are commands that print the shell's state.
• Usability: Add location information to a lot of error messages.

• Test suite enahncements and reorganization.

• I added a better error emssage for packagers. NOTE For packagers: issue 47, don't strip binary! If you package it, remember See Oil deployments.

What's Next?

Although this release led to several digressions:

• R programming, and an abstraction for serializing tables/logs
• wwz, FastCGI, and shared hosting

I want to keep my eye on the ball and keep making the parser faster. I knocked one of the three parser bottlenecks identified in the last status update.

I plan to fix the remaining two issues:

• Lexer code gen with re2c
• ASDL code gen

Appendix A: Project Metrics

In this section, we compare this release vs. the previous one. I put significant work into the scripts creating the oilshell.org/release/$VERSION/ trees

Spec Tests

• OSH 0.1: 836 total tests, 662 passing, 123 failing.
• OSH 0.2: 863 total tests, 685 passing, 124 failing.

What improves the spec test metrics is implementing new features like the getopts builtin. In this release, I did more work on the parser, so the numbers haven't moved as much.

Line Counts

• OSH 0.1: 13,984 lines of code in the shell itself
• OSH 0.2: 14,298 lines of code in the shell itself

The shell is getting faster and more functional while not growing too much.

Most of the work in this release went toward the supporting infrastructure, which I summarize here (OSH 0.2 only):

# Lines  Category
  2,380  Build Automation
  5,242  Test Automation
    970  Benchmarks
    974  Web (used by tests and benchmarks)
  -----  -----
  9,566  TOTAL

  7,116  Spec Tests
  4,253  Oil Unit Tests
    543  Other Unit Tests
  -----  -----
 11,912  TOTAL

The supporting code adds up to 21,478 lines of code, dwarfing OSH itself! I view this is as a good thing. It keeps the project on track, but adds no weight to what we ship!

This gives me confidence that OVM can be made smaller and lighter, which will make OSH smaller and lighter.