AA behaves differently in CTFE?
Bastiaan Veelo via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Mon Nov 23 23:54:22 PST 2015
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
}
More information about the Digitalmars-d-learn
mailing list