Pegged uses an associative array to prevent infinite recursion [1]. This fails on some input, but only when used in CTFE [2]. The reduced case follows. I presume this is a bug?

[1] https://github.com/PhilippeSigaud/Pegged/blob/master/pegged/dev/introspection.d#L281
[2] https://github.com/PhilippeSigaud/Pegged/issues/166

Below, in the first case of the switch statement, a string is added to the maybeLeftRecursive AA. In the second case, evaluated right after, there is a test whether the AA contains the string or not. This results TRUE at compile time, but FALSE at run time:

struct ParseTree
{
    string name;
    string match;
    ParseTree[] children;
}

enum LeftRecursive { no, direct, hidden, indirect }

pure LeftRecursive[string] ruleInfo(ParseTree p)
{
    assert(p.name == "Grammar");

    LeftRecursive[string] result;
    ParseTree[string] rules;
    bool[string] maybeLeftRecursive;

    pure LeftRecursive leftRecursion(ParseTree p, string target)
    {
        switch (p.name)
        {
            case "Expression": // Choices are left-recursive if any choice is left-recursive
                maybeLeftRecursive[target] = true;
                foreach(seq; p.children)
                {
                    auto lr = leftRecursion(seq, target);
                    if (lr != LeftRecursive.no)
                        return lr;
                }
                maybeLeftRecursive[target] = false;
                return LeftRecursive.no;
            case "RhsName":
                if (p.match == target)
                    return LeftRecursive.direct;
                if (p.match in maybeLeftRecursive && maybeLeftRecursive[p.match])
                    return LeftRecursive.indirect;
                if (p.match in maybeLeftRecursive)
                    return LeftRecursive.indirect;
                /*if (p.match in rules && leftRecursion(rules[p.match], target) != LeftRecursive.no)
                    return LeftRecursive.indirect;*/
                return LeftRecursive.no;
            default:
                return LeftRecursive.no;
        }
    }

    foreach(definition; p.children)
        if (definition.name == "Definition")
        {
            rules[definition.match] = definition.children[0];
            result[definition.match] = LeftRecursive.no;
        }

    foreach(name, tree; rules)
        result[name] = leftRecursion(tree, name);

    return result;
}

void main(string[] args)
{
    enum ParseTree tree = ParseTree("Grammar", "Left", [
        ParseTree("Definition", "L" /*<- P*/, [
            ParseTree("Expression", "P", [
                ParseTree("RhsName", "P", [])
            ])
        ]),
        ParseTree("Definition", "P" /*<- P / L*/, [
            ParseTree("Expression", "P", [
                ParseTree("RhsName", "P", []),
                ParseTree("RhsName", "L", [])
            ])
        ])
    ]);
    auto rtInfo = ruleInfo(tree);
    assert(rtInfo["L"] == LeftRecursive.indirect);
    assert(rtInfo["P"] == LeftRecursive.direct);

    enum ctInfo = ruleInfo(tree);
    static assert(ctInfo["L"] == LeftRecursive.indirect); // Fails, is LeftRecursive.no
    static assert(ctInfo["P"] == LeftRecursive.direct);   // Fails, is LeftRecursive.no
}

On Tuesday, 24 November 2015 at 07:54:24 UTC, Bastiaan Veelo wrote:
> This results TRUE at compile time, but FALSE  at run time.

Sorry, that should be the reverse: TRUE at run time, FALSE at compile time. Compile time exhibits the unexpected behaviour.

On 11/24/15 2:59 AM, Bastiaan Veelo wrote:
> On Tuesday, 24 November 2015 at 07:54:24 UTC, Bastiaan Veelo wrote:
>> This results TRUE at compile time, but FALSE  at run time.
>
> Sorry, that should be the reverse: TRUE at run time, FALSE at compile
> time. Compile time exhibits the unexpected behaviour.

If CTFE associative arrays perform differently, then that is a bug. I am not sure if this is the case, but you should file a bug anyway, someone can take a look at it.

If you can narrow it down to a minimal case where it breaks down, that would be helpful.

-Steve

On Tuesday, 24 November 2015 at 14:23:38 UTC, Steven Schveighoffer wrote:
> If CTFE associative arrays perform differently, then that is a bug. I am not sure if this is the case, but you should file a bug anyway, someone can take a look at it.
>
> If you can narrow it down to a minimal case where it breaks down, that would be helpful.
>
> -Steve

Thanks. After narrowing it down further I discovered a mistake in my code, which caused undesired behaviour dependent on the order in which elements on an AA are traversed by foreach.

As it turns out, the order in which foreach traverses elements of an AA at compile time differs from the order at run time. So yes, associative arrays behave differently, but it is hardly a bug since "in a foreach loop the order in which the elements are iterated is unspecified." [1]

[1] http://dlang.org/hash-map.html

On 11/24/15 2:43 PM, Bastiaan Veelo wrote:
> On Tuesday, 24 November 2015 at 14:23:38 UTC, Steven Schveighoffer wrote:
>> If CTFE associative arrays perform differently, then that is a bug. I
>> am not sure if this is the case, but you should file a bug anyway,
>> someone can take a look at it.
>>
>> If you can narrow it down to a minimal case where it breaks down, that
>> would be helpful.
>>
>> -Steve
>
> Thanks. After narrowing it down further I discovered a mistake in my
> code, which caused undesired behaviour dependent on the order in which
> elements on an AA are traversed by foreach.
>
> As it turns out, the order in which foreach traverses elements of an AA
> at compile time differs from the order at run time. So yes, associative
> arrays behave differently, but it is hardly a bug since "in a foreach
> loop the order in which the elements are iterated is unspecified." [1]
>
> [1] http://dlang.org/hash-map.html

Ah yes, that is very true.

Thanks for looking at it further!

If you need traversal to be consistent, there is std.container.rbtree, but it's not very friendly to use as a map.

-Steve