Home

OSH 0.2 - Parsing One Million Lines of Shell

2017-11-06

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

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.

Table of Contents

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:

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:

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:

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:

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:

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:

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:

What's Next?

Although this release led to several digressions:

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:

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

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

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.