OSH Word Evaluation Algorithm - oilshell/oil GitHub Wiki

OBSOLETE, See http://www.oilshell.org/release/latest/doc/simple-word-eval.html

This page documents a portion of the OSH implementation. It differs significantly from other shells in this respect.

  • They tend to use a homogeneous tree with various flags on nodes (e.g. nosplit, assignment, etc.).
  • OSH uses a typed, heterogeneous tree (now statically checked with MyPy).

For example:

word_part = 
  Literal(...)
| BracedVarSub(...)
| CommandSub(...)
| SingleQuoted(...)
| DoubleQuoted(...) 
| ...

https://github.com/oilshell/oil/blob/master/frontend/syntax.asdl#L107

Notes:

  • Specifying ML-like data structures with ASDL was an implementation style borrowed from CPython itself: see posts tagged #ASDL.
  • Smoosh is written in OCaml and Lem and also uses a typed, heterogeneous tree in some places. However, it also has a notion of "control codes", probably inherited from libdash, and word expansion operates on these control codes (section 4.2 of the paper).

Preliminaries

  1. As much parsing as possible is done in a single pass, with lexer modes.
  2. There are subsequent tweaks for detecting assignments, tildes, etc. They re-write small parts of the syntax tree, but are not a full parsing pass.
  3. There is a "metaprogramming" pass for brace expansion: i=0; echo {$((i++)),foo,bar}. (Bash brace expansion syntax is more like metaprogramming, whereas zsh implements it more like word evaluation.)

Word Evaluation Algorithm

There are three stages (not four as in POSIX). EvalWordSequence2 in osh/word_eval.py is a tiny function that shows the stages explicitly.

  1. Evaluation of the typed tree.
    • There is also a restricted variant of word evaluation for completion, e.g. so arbitrary processes aren't run with you hit TAB.
    • part_value = String(...) | Array(...) in osh/runtime.asdl is an important intermediate data type.
  2. Splitting with IFS. Ths is specified with a state machine in osh/split.py. (I think OSH is unique in this regard too.)
    • Splitting involves the concept of "frames", to handle things like x='a b'; y='c d'; echo $x"${@}"$y. The last part of $x has to be joined with argv[0], and argv[n-1] has to be joined with $y.
  3. Globbing.

There is no such thing as "quote removal" in OSH (e.g. any more than a Python or JavaScript interpreter has "quote removal"). It's just evaluation.

  • Caveat: Bug with IFS='\'
    1. Splitting and globbing are separate stages, but have "dependencies" because of statements like echo $prefix_that_could_be_split/"constant string"*.sh
    2. Internally, splitting and globbing both use \ to inhibit "evaluation". That is, \* is an escaped glob. And \ is an escaped space (IFS character).
    3. This causes problems when IFS='\'. I think I could choose a different character for OSH, maybe even the NUL byte.

Motivation

OSH wants to treat all sublanguages uniformly. (Command, Word, Arith, and the non-POSIX bool [[) are the main sublanguages.)

For some "dynamic" sublanguages like builtin flag syntax, we fall a bit short, but that could change in the future.

This matters for interactive completion, where it would be useful to understand every sublanguage statically.

For example, note that you can have variable references in several sublanguages:

Static:

  1. x=1 -- assignments are in the command language
  2. echo ${x:-${x:-$y}} -- word language
  3. echo $(( x == y )) -- arithmetic language
  4. [ $x -eq $y ](/oilshell/oil/wiki/-$x--eq-$y-) -- boolean language

Dynamic:

  1. code='x=1'; readonly $code -- the dynamic builtin language
  2. Other builtins that manage variables:
    • getopts
    • read
    • unset
    • printf -v in bash
  3. Variable references in ${!x} in bash/ksh

Oil Language

Claim: There should only be one step to word evaluation! I prefer to get rid of multi-stage "expansion" as a notion in shell.

The Oil language will statically parse globs, and I may add something like shopt -s static-glob to OSH in the short term.