in src/org/intellij/grammar/analysis/BnfFirstNextAnalyzer.java [208:374]
public Set<BnfExpression> calcFirstInner(BnfExpression expression, Set<BnfExpression> result, Set<BnfExpression> visited, @Nullable Pair<Boolean, List<BnfExpression>> forcedNext) {
BnfFile file = (BnfFile)expression.getContainingFile();
if (expression instanceof BnfLiteralExpression) {
result.add(expression);
}
else if (expression instanceof BnfReferenceOrToken) {
BnfRule rule = file.getRule(expression.getText());
if (rule != null) {
if (ParserGeneratorUtil.Rule.isExternal(rule)) {
BnfExpression callExpr = ContainerUtil.getFirstItem(GrammarUtil.getExternalRuleExpressions(rule));
if (callExpr instanceof BnfReferenceOrToken && file.getRule(callExpr.getText()) == null) {
result.add(callExpr);
return result;
}
}
BnfExpression ruleExpression = rule.getExpression();
if (myPublicRuleOpaque && !ParserGeneratorUtil.Rule.isPrivate(rule) ||
!visited.add(ruleExpression)) {
if (!(ParserGeneratorUtil.Rule.firstNotTrivial(rule) instanceof BnfPredicate)) {
result.add(expression);
}
}
else {
calcFirstInner(ruleExpression, result, visited, forcedNext);
boolean removed = visited.remove(ruleExpression);
LOG.assertTrue(removed, "path corruption detected: " + ruleExpression.getText());
}
}
else {
result.add(expression);
}
}
else if (expression instanceof BnfParenthesized) {
calcFirstInner(((BnfParenthesized)expression).getExpression(), result, visited, forcedNext);
if (expression instanceof BnfParenOptExpression) {
result.add(BNF_MATCHES_EOF);
}
}
else if (expression instanceof BnfChoice) {
boolean matchesNothing = result.remove(BNF_MATCHES_NOTHING);
boolean matchesSomething = false;
for (BnfExpression child : ((BnfChoice)expression).getExpressionList()) {
calcFirstInner(child, result, visited, forcedNext);
matchesSomething |= !result.remove(BNF_MATCHES_NOTHING);
}
if (!matchesSomething || matchesNothing) result.add(BNF_MATCHES_NOTHING);
}
else if (expression instanceof BnfSequence) {
calcSequenceFirstInner(((BnfSequence)expression).getExpressionList(), result, visited);
}
else if (expression instanceof BnfQuantified) {
calcFirstInner(((BnfQuantified)expression).getExpression(), result, visited, forcedNext);
IElementType effectiveType = ParserGeneratorUtil.getEffectiveType(expression);
if (effectiveType == BnfTypes.BNF_OP_OPT || effectiveType == BnfTypes.BNF_OP_ZEROMORE) {
result.add(BNF_MATCHES_EOF);
}
}
else if (expression instanceof BnfExternalExpression) {
BnfExternalExpression externalExpression = (BnfExternalExpression)expression;
List<BnfExpression> arguments = externalExpression.getArguments();
if (arguments.isEmpty() && ParserGeneratorUtil.Rule.isMeta(ParserGeneratorUtil.Rule.of(expression))) {
result.add(expression);
}
else {
BnfExpression ruleRef = externalExpression.getRefElement();
Set<BnfExpression> metaResults = calcFirstInner(ruleRef, new LinkedHashSet<>(), visited, forcedNext);
List<String> params = null;
for (BnfExpression e : metaResults) {
if (e instanceof BnfExternalExpression) {
if (params == null) {
BnfRule metaRule = (BnfRule)ruleRef.getReference().resolve();
if (metaRule == null) {
LOG.error("ruleRef:" + ruleRef.getText() +", metaResult:" + metaResults);
continue;
}
params = GrammarUtil.collectMetaParameters(metaRule, metaRule.getExpression());
}
int idx = params.indexOf(e.getText());
if (idx > -1 && idx < arguments.size()) {
calcFirstInner(arguments.get(idx), result, visited, null);
}
}
else {
result.add(e);
}
}
}
}
else if ((myBackward || !myPredicateLookAhead) && expression instanceof BnfPredicate) {
result.add(BNF_MATCHES_EOF);
}
else if (expression instanceof BnfPredicate) {
IElementType elementType = ((BnfPredicate)expression).getPredicateSign().getFirstChild().getNode().getElementType();
BnfExpression predicateExpression = ParserGeneratorUtil.getNonTrivialNode(((BnfPredicate)expression).getExpression());
boolean skip = predicateExpression instanceof BnfSequence &&
((BnfSequence)predicateExpression).getExpressionList().size() > 1; // todo calc min length ?
// take only one token into account which is not exactly correct but better than nothing
Set<BnfExpression> conditions = calcFirstInner(predicateExpression, newExprSet(), visited, null);
Set<BnfExpression> next;
List<BnfExpression> externalCond = Collections.emptyList();
List<BnfExpression> externalNext = Collections.emptyList();
if (!visited.add(predicateExpression)) {
skip = true;
next = Collections.emptySet();
//result.add(BNF_MATCHES_NOTHING);
}
else {
if (forcedNext == null) {
next = calcNextInner(expression, new HashMap<>(), visited).keySet();
}
else {
next = calcSequenceFirstInner(forcedNext.second, newExprSet(), visited);
}
visited.remove(predicateExpression);
externalCond = filterExternalMethods(conditions);
externalNext = filterExternalMethods(next);
if (!skip) skip = !externalCond.isEmpty();
}
Set<BnfExpression> mixed;
if (elementType == BnfTypes.BNF_OP_AND) {
if (forcedNext != null && forcedNext.first) {
mixed = newExprSet(conditions);
}
else if (skip) {
mixed = exprSetUnion(next, externalCond);
mixed.remove(BNF_MATCHES_EOF);
}
else if (!conditions.contains(BNF_MATCHES_EOF)) {
if (next.contains(BNF_MATCHES_ANY)) {
mixed = newExprSet(conditions);
}
else {
if (externalNext.isEmpty()) {
mixed = exprSetIntersection(conditions, next);
if (mixed.isEmpty() && !involvesTextMatching(conditions)) {
mixed.add(BNF_MATCHES_NOTHING);
}
}
else {
mixed = newExprSet(conditions);
}
}
}
else {
mixed = newExprSet(next);
}
}
else {
if (skip) {
mixed = exprSetUnion(next, externalCond); // todo shall be actually inverted
mixed.remove(BNF_MATCHES_EOF);
}
else if (!conditions.contains(BNF_MATCHES_EOF)) {
mixed = exprSetDifference(next, conditions);
if (mixed.isEmpty() && !involvesTextMatching(conditions)) {
mixed.add(BNF_MATCHES_NOTHING);
}
}
else {
mixed = Collections.singleton(BNF_MATCHES_NOTHING);
}
}
result.addAll(mixed);
}
return result;
}