[
https://issues.apache.org/jira/browse/GEODE-10508?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18042565#comment-18042565
]
ASF subversion and git services commented on GEODE-10508:
---------------------------------------------------------
Commit 05104a977e2b4d84e1737fea75e89e25e1ec78f0 in geode's branch
refs/heads/develop from Jinwoo Hwang
[ https://gitbox.apache.org/repos/asf?p=geode.git;h=05104a977e ]
[GEODE-10508] Remedation of ANTLR nondeterminism warnings in OQL grammar (#7942)
* GEODE-10508: Fix ANTLR nondeterminism warnings in OQL grammar
This commit resolves four nondeterminism warnings generated by ANTLR during
the OQL grammar compilation process. These warnings indicated parser ambiguity
that could lead to unpredictable parsing behavior.
Problem Analysis:
-----------------
1. Lines 574 & 578 (projection rule):
The parser could not distinguish between aggregateExpr and expr alternatives
when encountering aggregate function keywords (sum, avg, min, max, count).
These keywords are valid both as:
- Aggregate function identifiers: sum(field)
- Regular identifiers in expressions: sum as a field name
Without lookahead, ANTLR could not deterministically choose which production
rule to apply, resulting in nondeterminism warnings.
2. Lines 961 & 979 (aggregateExpr rule):
Optional 'distinct' keyword created ambiguity in aggregate function parsing.
The parser could not decide whether to:
- Match the optional 'distinct' keyword, or
- Skip it and proceed directly to the expression
Both paths were valid, but ANTLR's default behavior doesn't specify
preference, causing nondeterminism.
Solution Implemented:
--------------------
1. Added syntactic predicates to projection rule (lines 574, 578):
Predicate: (('sum'|'avg'|'min'|'max'|'count') TOK_LPAREN)=>
This instructs the parser to look ahead and check if an aggregate keyword
is followed by a left parenthesis. If true, it chooses aggregateExpr;
otherwise, it chooses expr. This resolves the ambiguity by providing
explicit lookahead logic.
2. Added greedy option to aggregateExpr rule (lines 961, 979):
Option: options {greedy=true;}
This tells the parser to greedily match the 'distinct' keyword whenever
it appears, rather than being ambiguous about whether to match or skip.
The greedy option eliminates the nondeterminism by establishing clear
matching priority.
3. Updated test to use token constants (AbstractCompiledValueTestJUnitTest):
Changed: hardcoded value 89 -> OQLLexerTokenTypes.LITERAL_or
Rationale: Adding syntactic predicates changes ANTLR's token numbering
in the generated lexer (LITERAL_or shifted from 89 to 94). Using the
constant ensures test correctness regardless of future grammar changes.
This is a best practice for maintaining test stability.
Impact:
-------
- Zero nondeterminism warnings from ANTLR grammar generation
- No changes to OQL syntax or semantics (fully backward compatible)
- No runtime behavior changes (modifications only affect parser generation)
- All existing tests pass with updated token reference
- Improved parser determinism and maintainability
Technical Details:
-----------------
- Syntactic predicates (=>) are standard ANTLR 2 feature for lookahead
- Greedy option is standard ANTLR feature for optional subrule disambiguation
- Token constant usage follows best practices for generated code references
- Changes are compile-time only with no runtime performance impact
Files Modified:
--------------
- geode-core/src/main/antlr/org/apache/geode/cache/query/internal/parse/oql.g
-
geode-core/src/test/java/org/apache/geode/cache/query/internal/AbstractCompiledValueTestJUnitTest.java
* GEODE-10508: Apply code formatting to test file
Fix line length formatting for improved readability.
> Remediation of ANTLR Nondeterminism Warnings in OQL Grammar
> -----------------------------------------------------------
>
> Key: GEODE-10508
> URL: https://issues.apache.org/jira/browse/GEODE-10508
> Project: Geode
> Issue Type: Improvement
> Reporter: Jinwoo Hwang
> Assignee: Jinwoo Hwang
> Priority: Major
> Fix For: 2.1.0
>
>
> h2. Summary
> Fix nondeterminism warnings generated by ANTLR during compilation of the OQL
> (Object Query Language) grammar file. The warnings indicate ambiguity in the
> parser that prevents it from deterministically choosing between alternative
> production rules.
> h2. Problem Statement
> h3. Current Behavior
> During the {{generateGrammarSource}} task, ANTLR produces the following
> nondeterminism warnings:
> {noformat}
> > Task :geode-core:generateGrammarSource
> /home/runner/work/geode/geode/geode-core/src/main/antlr/org/apache/geode/cache/query/internal/parse/oql.g:574:40:
>
> warning:nondeterminism between alts 1 and 2 of block upon
> k==1:"sum","avg","min","max","count"
> k==2:TOK_LPAREN
> /home/runner/work/geode/geode/geode-core/src/main/antlr/org/apache/geode/cache/query/internal/parse/oql.g:578:13:
>
> warning:nondeterminism between alts 1 and 2 of block upon
> k==1:"sum","avg","min","max","count"
> k==2:TOK_LPAREN
> /home/runner/work/geode/geode/geode-core/src/main/antlr/org/apache/geode/cache/query/internal/parse/oql.g:961:26:
>
> warning:nondeterminism between alts 1 and 2 of block upon
> k==1:"distinct"
> k==2:TOK_LPAREN,TOK_PLUS,TOK_MINUS,TOK_DOLLAR,...
> /home/runner/work/geode/geode/geode-core/src/main/antlr/org/apache/geode/cache/query/internal/parse/oql.g:979:17:
>
> warning:nondeterminism between alts 1 and 2 of block upon
> k==1:"distinct"
> k==2:TOK_LPAREN,TOK_PLUS,TOK_MINUS,TOK_DOLLAR,...
> {noformat}
> h3. Root Cause Analysis
> *Lines 574 & 578 (projection rule):*
> The parser cannot distinguish between {{aggregateExpr}} and {{expr}}
> alternatives when it encounters aggregate function keywords ({{{}sum{}}},
> {{{}avg{}}}, {{{}min{}}}, {{{}max{}}}, {{{}count{}}}) because:
> * These keywords can start an aggregate expression like {{sum(field)}}
> * The same keywords can also be used as identifiers in regular expressions
> * Without lookahead, the parser cannot determine which production rule to
> apply
> *Lines 961 & 979 (aggregateExpr rule):*
> The optional {{distinct}} keyword creates ambiguity:
> * The parser cannot decide whether to match the optional {{distinct}}
> keyword or skip it and proceed directly to the expression
> * This is because both alternatives are valid, and the default behavior
> doesn't specify preference
> h2. Proposed Solution
> h3. 1. Add Syntactic Predicates (Lines 574 & 578)
> Use ANTLR syntactic predicates to perform lookahead and resolve ambiguity in
> the {{projection}} rule:
> {code}
> Unable to find source-code formatter for language: antlr. Available languages
> are: actionscript, ada, applescript, bash, c, c#, c++, cpp, css, erlang, go,
> groovy, haskell, html, java, javascript, js, json, lua, none, nyan, objc,
> perl, php, python, r, rainbow, ruby, scala, sh, sql, swift, visualbasic, xml,
> yaml// Before:
> ( tok1:aggregateExpr{node = #tok1;} | tok2:expr{node = #tok2;})
> // After:
> ( (("sum"|"avg"|"min"|"max"|"count") TOK_LPAREN)=> tok1:aggregateExpr{node =
> #tok1;} | tok2:expr{node = #tok2;})
> {code}
> The predicate {{(("sum"|"avg"|"min"|"max"|"count") TOK_LPAREN)=>}} tells the
> parser:
> * Look ahead to check if an aggregate keyword is followed by a left
> parenthesis
> * If true, choose the {{aggregateExpr}} alternative
> * Otherwise, choose the {{expr}} alternative
> h3. 2. Add Greedy Option (Lines 961 & 979)
> Use the {{greedy}} option for optional {{distinct}} keywords in the
> {{aggregateExpr}} rule:
> {code}
> Unable to find source-code formatter for language: antlr. Available languages
> are: actionscript, ada, applescript, bash, c, c#, c++, cpp, css, erlang, go,
> groovy, haskell, html, java, javascript, js, json, lua, none, nyan, objc,
> perl, php, python, r, rainbow, ruby, scala, sh, sql, swift, visualbasic, xml,
> yaml// Before:
> TOK_LPAREN ("distinct"! {distinctOnly = true;} ) ? tokExpr1:expr TOK_RPAREN
> // After:
> TOK_LPAREN (options {greedy=true;}: "distinct"! {distinctOnly = true;} ) ?
> tokExpr1:expr TOK_RPAREN
> {code}
> The {{greedy}} option instructs the parser to match the {{distinct}} keyword
> whenever it appears, removing ambiguity.
> h3. 3. Fix Test Compatibility Issue
> The grammar changes will alter token numbering in the generated lexer. Update
> {{AbstractCompiledValueTestJUnitTest.java}} to use constants instead of
> hardcoded token values:
> {code:java}
> // Before:
> new CompiledJunction(new CompiledValue[] {compiledValue1, compiledValue2}, 89)
> // After:
> import org.apache.geode.cache.query.internal.parse.OQLLexerTokenTypes;
> ...
> new CompiledJunction(new CompiledValue[] {compiledValue1, compiledValue2},
> OQLLexerTokenTypes.LITERAL_or)
> {code}
> *Rationale:* Adding syntactic predicates changes token numbering (e.g.,
> {{LITERAL_or}} changes from 89 to 94). Using the constant ensures tests
> remain correct regardless of future grammar modifications.
> h2. Implementation Plan
> h3. Phase 1: Grammar Modifications
> # Update
> {{geode-core/src/main/antlr/org/apache/geode/cache/query/internal/parse/oql.g}}
> # Add syntactic predicates to the {{projection}} rule (2 locations)
> # Add {{greedy}} option to {{aggregateExpr}} rule (2 locations)
> # Add inline comments explaining the reasoning for each change
> h3. Phase 2: Test Updates
> # Update {{AbstractCompiledValueTestJUnitTest.java}}
> # Add import for {{OQLLexerTokenTypes}}
> # Replace hardcoded value {{89}} with {{OQLLexerTokenTypes.LITERAL_or}}
> # Add comments explaining why the constant is used
> h3. Phase 3: Validation
> # Run {{./gradlew :geode-core:generateGrammarSource}} to verify no warnings
> # Run {{./gradlew :geode-core:test --tests
> "org.apache.geode.cache.query.internal.parse.*"}} to verify parser tests pass
> # Run {{./gradlew :geode-core:test --tests
> "org.apache.geode.cache.query.internal.Abstract*"}} to verify updated test
> passes
> # Run full {{geode-core}} test suite to ensure no regressions
> h2. Expected Outcomes
> h3. Success Criteria
> (/) Zero nondeterminism warnings from ANTLR grammar generation
> (/) All existing query parsing tests pass
> (/) {{AbstractCompiledValueTestJUnitTest}} passes with updated token usage
> (/) No behavior changes to OQL query parsing or execution
> (/) Token numbering is stable and predictable
> h3. Impact Assessment
> *Risk Level:* Low
> * Changes only affect parser generation, not runtime behavior
> * Syntactic predicates and greedy options are standard ANTLR features
> * All test coverage validates correct parsing behavior
> *Performance Impact:* None
> * Grammar changes only affect compile-time parser generation
> * No runtime performance impact
> *Compatibility:* Maintained
> * No changes to OQL syntax or semantics
> * Fully backward compatible with existing queries
> h2. Files to be Modified
> #
> {{geode-core/src/main/antlr/org/apache/geode/cache/query/internal/parse/oql.g}}
> (Grammar file)
> #
> {{geode-core/src/test/java/org/apache/geode/cache/query/internal/AbstractCompiledValueTestJUnitTest.java}}
> (Test file)
> h2. References
> * [ANTLR 2 Documentation - Syntactic
> Predicates|https://www.antlr2.org/doc/predicates.html]
> * [ANTLR 2 Documentation - Greedy
> Subrules|https://www.antlr2.org/doc/options.html]
> * Apache Geode OQL Documentation
> h2. Testing Strategy
> h3. Unit Tests
> * Verify all query parser tests pass
> * Verify aggregate function parsing works correctly
> * Verify distinct keyword handling in aggregate functions
> h3. Integration Tests
> * Run OQL query tests with aggregate functions
> * Test queries with projection containing aggregate expressions
> * Test queries mixing aggregate and non-aggregate projections
> h3. Regression Tests
> * Run full geode-core test suite
> * Verify no changes to generated parser behavior
> * Confirm token numbering stability
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
