www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - AA behaves differently in CTFE?

reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
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
}
Nov 23 2015
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
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.
Nov 23 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Nov 24 2015
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
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
Nov 24 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Nov 24 2015