Changeset 11447 in josm


Ignore:
Timestamp:
2017-01-09T23:57:47+01:00 (2 months ago)
Author:
Don-vip
Message:

fix #14217 - replace recursive filter parsing by iterative approach to avoid StackOverflowError for very long filters (~3000 logical operators)

Location:
trunk
Files:
2 added
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java

    r11446 r11447  
    88import java.io.StringReader;
    99import java.text.Normalizer;
     10import java.util.ArrayList;
    1011import java.util.Arrays;
    1112import java.util.Collection;
     
    16321633
    16331634    /**
    1634      * Parse expression. This is a recursive method.
     1635     * Parse expression.
    16351636     *
    16361637     * @return match determined by parsing expression
    1637      * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError if search expression cannot be parsed
     1638     * @throws ParseError if search expression cannot be parsed
    16381639     */
    16391640    private Match parseExpression() throws ParseError {
    1640         Match factor = parseFactor();
    1641         if (factor == null)
    1642             // empty search string
    1643             return null;
    1644         if (tokenizer.readIfEqual(Token.OR))
    1645             return new Or(factor, parseExpression(tr("Missing parameter for OR")));
    1646         else if (tokenizer.readIfEqual(Token.XOR))
    1647             return new Xor(factor, parseExpression(tr("Missing parameter for XOR")));
    1648         else {
    1649             Match expression = parseExpression();
    1650             if (expression == null)
    1651                 // reached end of search string, no more recursive calls
    1652                 return factor;
    1653             else
    1654                 // the default operator is AND
    1655                 return new And(factor, expression);
    1656         }
    1657     }
    1658 
    1659     /**
    1660      * Parse expression, showing the specified error message if parsing fails.
    1661      *
    1662      * @param errorMessage to display if parsing error occurs
    1663      * @return match determined by parsing expression
    1664      * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError if search expression cannot be parsed
    1665      * @see #parseExpression()
    1666      */
    1667     private Match parseExpression(String errorMessage) throws ParseError {
    1668         Match expression = parseExpression();
    1669         if (expression == null)
    1670             throw new ParseError(errorMessage);
    1671         else
    1672             return expression;
     1641        // Step 1: parse the whole expression and build a list of factors and logical tokens
     1642        List<Object> list = parseExpressionStep1();
     1643        // Step 2: iterate the list in reverse order to build the logical expression
     1644        // This iterative approach avoids StackOverflowError for long expressions (see #14217)
     1645        return parseExpressionStep2(list);
     1646    }
     1647
     1648    private List<Object> parseExpressionStep1() throws ParseError {
     1649        Match factor;
     1650        String token = null;
     1651        String errorMessage = null;
     1652        List<Object> list = new ArrayList<>();
     1653        do {
     1654            factor = parseFactor();
     1655            if (factor != null) {
     1656                if (token != null) {
     1657                    list.add(token);
     1658                }
     1659                list.add(factor);
     1660                if (tokenizer.readIfEqual(Token.OR)) {
     1661                    token = "OR";
     1662                    errorMessage = tr("Missing parameter for OR");
     1663                } else if (tokenizer.readIfEqual(Token.XOR)) {
     1664                    token = "XOR";
     1665                    errorMessage = tr("Missing parameter for XOR");
     1666                } else {
     1667                    token = "AND";
     1668                    errorMessage = null;
     1669                }
     1670            } else if (errorMessage != null) {
     1671                throw new ParseError(errorMessage);
     1672            }
     1673        } while (factor != null);
     1674        return list;
     1675    }
     1676
     1677    private Match parseExpressionStep2(List<Object> list) {
     1678        Match result = null;
     1679        for (int i = list.size() - 1; i >= 0; i--) {
     1680            Object o = list.get(i);
     1681            if (o instanceof Match && result == null) {
     1682                result = (Match) o;
     1683            } else if (o instanceof String && i > 0) {
     1684                Match factor = (Match) list.get(i-1);
     1685                switch ((String) o) {
     1686                case "OR":
     1687                    result = new Or(factor, result);
     1688                    break;
     1689                case "XOR":
     1690                    result = new Xor(factor, result);
     1691                    break;
     1692                case "AND":
     1693                    result = new And(factor, result);
     1694                    break;
     1695                default: throw new IllegalStateException(tr("Unexpected token: {0}", o));
     1696                }
     1697                i--;
     1698            } else {
     1699                throw new IllegalStateException("i=" + i + "; o=" + o);
     1700            }
     1701        }
     1702        return result;
    16731703    }
    16741704
     
    16771707     *
    16781708     * @return match determined by parsing factor string
    1679      * @throws org.openstreetmap.josm.actions.search.SearchCompiler.ParseError if search expression cannot be parsed
     1709     * @throws ParseError if search expression cannot be parsed
    16801710     */
    16811711    private Match parseFactor() throws ParseError {
  • trunk/test/unit/org/openstreetmap/josm/actions/search/SearchCompilerTest.java

    r11324 r11447  
    44import static org.junit.Assert.assertEquals;
    55import static org.junit.Assert.assertFalse;
     6import static org.junit.Assert.assertNotNull;
    67import static org.junit.Assert.assertTrue;
    78import static org.junit.Assert.fail;
    89
     10import java.nio.charset.StandardCharsets;
     11import java.nio.file.Files;
     12import java.nio.file.Paths;
     13
    914import org.junit.Rule;
    1015import org.junit.Test;
     16import org.openstreetmap.josm.TestUtils;
    1117import org.openstreetmap.josm.actions.search.SearchAction.SearchSetting;
    1218import org.openstreetmap.josm.actions.search.SearchCompiler.Match;
     
    8389    }
    8490
    85     protected OsmPrimitive newPrimitive(String key, String value) {
     91    private static OsmPrimitive newPrimitive(String key, String value) {
    8692        final Node p = new Node();
    8793        p.put(key, value);
     
    466472        SearchCompiler.compile(setting);
    467473    }
     474
     475    /**
     476     * Non-regression test for <a href="https://josm.openstreetmap.de/ticket/14217">Bug #14217</a>.
     477     * @throws Exception never
     478     */
     479    @Test
     480    public void testTicket14217() throws Exception {
     481        assertNotNull(SearchCompiler.compile(new String(Files.readAllBytes(
     482                Paths.get(TestUtils.getRegressionDataFile(14217, "filter.txt"))), StandardCharsets.UTF_8)));
     483    }
    468484}
Note: See TracChangeset for help on using the changeset viewer.