StackOverflow while parsing CNF expression #1576

Activity

1. manticore-projects commented on Jun 28, 2022

   

   manticore-projects

   on Jun 28, 2022

   Contributor

   More actions

   Greetings.

   Please use latest JSQLParser 4.5 Snapshot. The following SQL parsed without any problem.
   You can try it online here.

   SELECT ( ( 3.0 >= 4.0
                       AND 5.0 <= 6.0 )
                   OR ( 7.0 < 8.0
                           AND 9.0 > 10.0 )
                   OR ( 11.0 = 11.0
                           AND 19.0 > 20.0 )
                   OR ( 17.0 = 14.0
                           AND 19.0 > 17.0 )
                   OR ( 17.0 = 18.0
                           AND 20.0 > 20.0 )
                   OR ( 17.0 = 16.0
                           AND 19.0 > 20.0 )
                   OR ( 17.0 = 18.0
                           AND 19.0 > 20.0 )
                   OR ( 17.0 = 18.0
                           AND 19.0 > 20.0 )
                   OR ( 17.0 = 22.0
                           AND 19.0 > 20.0 )
                   OR ( 18.0 = 18.0
                           AND 22.0 > 20.0 )
                   OR ( 17.0 = 18.0
                           AND 19.0 > 20.0 )
                   OR ( 18.0 = 18.0
                           AND 22.0 > 20.0 )
                   OR ( 17.0 = 18.0
                           AND 19.0 > 20.0 ) )
   ;
2. deepak-ti commented on Jun 28, 2022

   

   deepak-ti

   on Jun 28, 2022

   Author

   More actions

   Thanks, but actually I am unable to find 4.5-snapshot dependency in maven central. Can you please point me to that ?
3. manticore-projects commented on Jun 28, 2022

   

   manticore-projects

   on Jun 28, 2022

   Contributor

   More actions

   <repositories>
        <repository>
            <id>jsqlparser-snapshots</id>
            <snapshots>
                <enabled>true</enabled>
            </snapshots>
            <url>https://oss.sonatype.org/content/groups/public/</url>
        </repository>
   </repositories>
4. deepak-ti commented on Jun 28, 2022

   

   deepak-ti

   on Jun 28, 2022

   Author

   More actions

   I have added the 4.5-SNAPSHOT version dependency in a sample and could see that API - CCJSqlParserUtil.parseCondExpression() is surviving but feeding the generated expression to -
   Expression result = CNFConverter.convertToCNF( expr ); and then calling result.toString() is throwing the StackOverfow error :

   java.lang.StackOverflowError
   at java.base/java.lang.StringBuilder.(StringBuilder.java:99)
   at net.sf.jsqlparser.expression.BinaryExpression.toString(BinaryExpression.java:66)

   PS: Following class i have used to reproduce the issue -

   package org.example;
   
   import static org.junit.Assert.assertTrue;
   import net.sf.jsqlparser.JSQLParserException;
   import net.sf.jsqlparser.expression.Expression;
   import net.sf.jsqlparser.parser.CCJSqlParserUtil;
   import net.sf.jsqlparser.util.cnfexpression.CNFConverter;
   import org.junit.Test;
   
   /**
    * Unit test for CNF.
    */
   public class CNFTest
   {
       /**
        * Test the CNF conversion and print it.
        */
       @Test
       public void testStackOverflow()
       {
           try{
           Expression expr = CCJSqlParserUtil.parseCondExpression(
                   "((3.0 >= 4.0 AND 5.0 <= 6.0) OR "
                           + "(7.0 < 8.0 AND 9.0 > 10.0) OR "
                           + "(11.0 = 11.0 AND 19.0 > 20.0) OR "
                           + "(17.0 = 14.0 AND 19.0 > 17.0) OR "
                           + "(17.0 = 18.0 AND 20.0 > 20.0) OR "
                           + "(17.0 = 16.0 AND 19.0 > 20.0) OR "
                           + "(17.0 = 18.0 AND 19.0 > 20.0) OR "
                           + "(17.0 = 18.0 AND 19.0 > 20.0) OR "
                           + "(17.0 = 22.0 AND 19.0 > 20.0) OR "
                           + "(18.0 = 18.0 AND 22.0 > 20.0) OR "
                           + "(17.0 = 18.0 AND 19.0 > 20.0) OR "
                           + "(18.0 = 18.0 AND 22.0 > 20.0) OR "
                           + "(18.0 = 19.0 AND 22.0 > 20.0) OR "
                           + "(17.0 = 18.0 AND 19.0 > 20.0))"
           );
   
           Expression result = CNFConverter.convertToCNF( expr );
   
           System.out.println(result);
           }catch (JSQLParserException e){
               e.printStackTrace();
           }catch(Exception e){
               e.printStackTrace();
           }
       }
   }
   
   
5. wumpz commented on Jul 7, 2022

   

   wumpz

   on Jul 7, 2022

   Member

   More actions

   Btw the length of the result, since there are 2 ^ 14 * (14 * 14 (estimated item length)), should be near 3 200 200 characters. However, at the moment I look into this Stackoverflow problem. Maybe you could increase the stack size to make it work. Nevertheless, the CNFConverter uses too much memory.
6. wumpz

   pinned this issue on Jul 7, 2022
7. wumpz

   closed this as completedin 48ea0e2on Jul 9, 2022
8. wumpz commented on Jul 9, 2022

   

   wumpz

   on Jul 9, 2022

   Last edited by wumpz

   Member

   More actions

   So the problem here was, how or ' ed expressions were build up in the end. This was a complete unbalanced tree like

   or 
     or 
        or 
          or 
             a
             b
          c
       d
     e
   

   So in the right expression was only a normal expression. Therefore to reach the first expression "a" we 2 ^14 stack calls and a bit deeper :). That broke the stack. I rewrote this expression building to form a balanced binary tree like

   or 
     or
       or 
           a
           b
       or
           c
           d
     e
   

   so now the tree log 2 ^ 14 (base 2) deep, means 14. So now you are facing heap issues since the result is very large.

   Your example results in a sql string with the length of 3448827 characters. I added (and disabled afterwards) a test with three more OR items, which results in 33685499 characters. You get the idea.
9. wumpz

   unpinned this issue on Jul 9, 2022
10. yadedoo

    added a commit that references this issue on May 11, 2024

    fixes JSQLParser#1576

    This issue will close once commit 48ea0e2 is merged into the 'master' branch.

    48ea0e2