[Oil-dev] Brace Expansion

[Andy Chu]

OK, it was easier than expected to integrate brace expansion, and I fixed a
lot of other stuff along the way:

https://github.com/oilshell/oil/commit/700c223847f001be55f572187feeb19e0bd83ded

I'm trying to make the commit messages more informative now -- let me know
if I've succeeded or not :)  We now pass a lot more tests and run real code
using brace expansion in ./count.sh.

http://www.oilshell.org/git-branch/master/700c2238/andy-home/spec/RESULTS.html

A week or two ago, there were 478 total test cases, with OSH passing on 249
and failing on 168.  Now there are 517 test cases, with OSH passing on 295
and failing on 168.  (Although that 168 is NOT the same, I fixed some and
left some brace expansion tests broken for now.)  I like this way of
keeping track of progress!

In case people are not familiar with brace expansion, this kind of
summarizes it:

$ echo -{a,={b,c}=d}.{e,f}-
-a.e- -a.f- -=b=d.e- -=b=d.f- -=c=d.e- -=c=d.f-

I've only ever used something like {core,osh}/*.py.  But you can have
adjacent alternatives which makes the "cartesian product":

$ echo {a,b}-{c,d}
a-c a-d b-c b-d

Or you can have nested alternatives which "sum";

$ echo -{a,={b,c}=,d}-
-a- -=b=- -=c=- -d-

And these two constructs can be combined.  There are also numbered ranges
like {1..10..2} in certain shells, and character ranges in bash only.

-----

The conclusion I draw from this change is that both ASDL and spec tests
have paid off.  I expanded the test suite to be pretty exhaustive:

http://www.oilshell.org/git-branch/master/700c2238/andy-home/spec/brace-expansion.html

The FAILs at the bottom for osh are because I didn't implement {1..10..2}
yet.  I'm trying to exhaustively test things, to get the architecture
right, and then prioritize implementation based on real scripts.  I don't
have any real scripts that use {1..10..2} yet.

I like ASDL because the schema shows concisely what happened:

https://github.com/oilshell/oil/commit/700c223847f001be55f572187feeb19e0bd83ded#diff-c2e3a0611d4c3347d43c4d3b94e0095f

I added a new kind of word -- BracedWordTree.  And three new word parts --
BracedAltPart, BracedNumRangePart, and BracedCharRangePart, only the first
of which is used now.

I'm separating the process into brace detection and brace expansion to
respect the LST concept.  The LST represents the code as written, but with
structure on top.  This will help us  convert brace expansions to Oil too.

So detection happens at parse time, and expansion at runtime.  Although we
could actually have a "middle" constant-folding stage that does brace
expansion and a few other things that are independent of runtime
variables.  That would be like an LST -> AST compiler.

----

What's next?  Well I added this gold-test.sh file -- take a peek, it's
tiny.  That is a fourth kind of tests I suppose, after "unit", "wild", and
"spec".  I run some real code with bash and osh and compare stdout.

I mentioned a globbing problem at the end of last blog post:
http://www.oilshell.org/blog/2017/03/09.html

I still have to fix that.  The brace expansion came about because I was
rethinking the representations for globbing.  I realized I hadn't preserved
enough information across the word evaluation pipeline.

And I found a new bug -- now that brace expansion succeeds in ./count.sh
all, I realized it ignores the "return" statement in the all() function.
So I have to implement that!

So overall I like this strategy of running our own code first.  It helps me
figure out what to work on.

I should talk about the "pre-structuring" feature of the lexer at some
point... that played into brace expansion, and will also likely play into
globbing.  The idea is that we shouldn't be rescanning strings at every
stage like a lot of shells do.  Instead we should represent code as
structured data -- the word_part and word variants are a key part of that.

Let me know if this is helpful or not!

thanks,
Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.oilshell.org/pipermail/oil-dev-oilshell.org/attachments/20170313/e9d7a0ab/attachment.htm>