[augeas-devel] Fixing ambiguous iteration errors

[David Lutterkort]

On Fri, 2011-10-14 at 08:39 -0700, Tom Limoncelli wrote:
> I'm trying to write a lens to parse Xen configuration files
> (xend-config.sxp) which is a very lisp-like format "(key value) (key2
> (key value))" and I'm getting nowhere.  I've learned a lot from
> working through the tutorials.  However I've also realized that I
> don't remember enough from my parsing and compilers class back in
> college :-).  (it was more than 20 years ago)
> 
> If you don't mind some noob questions....
> 
> 1. The Schema Tutorial (http://augeas.net/docs/writing-schemas.html)
> doesn't explain what |=| means.  I assume it is just a "pointer" to
> where the ambiguity starts.  Clarification, please?

Yes, that's exactly what it is. The '|=|' was just my attempt to mark
the position where stuff went wrong with something that's unlikely to be
in the original string. And take 'position where stuff went wrong' with
a grain of salt ... the position is generally not bad, but not always
perfect.

> 2.  I keep getting "ambiguous iteration" errors.  Unsurprisingly, I
> remember this being difficult for me to grasp when I was in college
> doing homework assignments in Yacc.  Is there a technique for
> diagnosing and fixing these?  A rule of thumb for avoiding them?

A very common reason to have ambiguous iteration errors is to star a
lens twice, i.e. write something like (l*)*, usually well hidden behind
a couple of let's.

Formally, ambiguous iteration means that you have a lens l* that matches
a word uv such that both u and v already match l; a very simple example:

        let l = [ key /a+/ ]
        let s = l*
        
The word 'aa' is ambiguous; applying s to it can yield the trees { 'a' }
{ 'a' } and { 'aa' }.

> The tutorials are great in that they go through the debugging process
> but they don't explain the thinking that leads to the changes made to
> fix the bugs as they are found.  I'd be glad to work with someone to
> improve them.

I'd love any suggestions in that direction; it's always bothered me that
ambiguity is such an important concept when writing lenses, and doesn't
have a very good intuitive explanation in the docs.

> P.S.  As an example, the error I'm dealing with right now is:

If you want to post the lens, I can try and see if I can find a
reasonable explanation for how to avoid the type check error.

> $ augparse -I. tests/test_xendconfsxp.aug Syntax error in lens
> definition./xendconfsxp.aug:25.0-.44:Failed to compile
> lns./xendconfsxp.aug:25.10-.44:exception: ambiguous iteration
> Iterated regexp: /\\([\t\n ]*[0-9A-Z\\a-z-]+[\t\n ]+[^\t\n ]+[\t\n
> ]*\\)|[\t ]*#[\t ]*([^\t\n ].*[^\t\n ]|[^\t\n ])[\t ]*\n|[\t ]*\n/
>  '(A\nA)#)\n' can be split into      '(A\nA)|=|#)\n'
>      and      '(A\nA)#)|=|\n'
>     Iterated lens: ./xendconfsxp.aug:25.12-.41:

In that error message, the '|=|' indicates how the input string would be
split: the first would apply lns to '(A\nA)' and again to '#)\n', the
second would do it to '(A\nA)#)' and then to '\n', yielding two
different trees.

David