[ https://issues.apache.org/jira/browse/JENA-1113?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Andy Seaborne updated JENA-1113: -------------------------------- Description: {{FILTER(?x IN ( .... ))}} with a list of 60,000+ URIs causes a stack overflow during execution. The list was machine generated. {{?x IN(C1, C2, ...)}} is expanded to {{?x = C1 || ?x = C2 || .... }}. In many places, working with expressions is a tree walk ({{ExprWalker}}). The transformation is a left-deep tree: for a 4-long list: {noformat} (|| (|| (|| (= ?x C1) (= ?x C2)) (= ?x C3)) (= ?x C4)) {noformat} so the walk is as deep as the list is long. A transformation rewrite is 3 stack frames per level. The result is a huge number of stack frames until is exceeds the stack space available. A right-deep list would be better but only if all processing code is aware of this and does a loop for the right recursion. was: {{FILTER(?x IN ( .... ))}} with a list of 60,000+ URIs causes a stack overflow during execution. The list was machine generated. {{?x IN(C1, C2, ...}} is expanded to {{?x = C1 || ?x = C2 || .... }}. In many places, working with expressions is a tree walk ({{ExprWalker}}). The transformation is a left-deep tree: for a 4-long list: {noformat} (|| (|| (|| (= ?x C1) (= ?x C2)) (= ?x C3)) (= ?x C4)) {noformat} so the walk is as deep as the list is long. A transformation rewrite is 3 stack frames per level. The result is a huge number of stack frames until is exceeds the stack space available. A right-deep list would be better but only if all processing code is aware of this and does a loop for the right recursion. > FILTER(?x IN ( .... )) causes stackoverflow for very long lists of values. > -------------------------------------------------------------------------- > > Key: JENA-1113 > URL: https://issues.apache.org/jira/browse/JENA-1113 > Project: Apache Jena > Issue Type: Bug > Components: ARQ > Affects Versions: Jena 3.0.1 > Reporter: Andy Seaborne > Assignee: Andy Seaborne > Priority: Minor > > {{FILTER(?x IN ( .... ))}} with a list of 60,000+ URIs causes a stack > overflow during execution. The list was machine generated. > {{?x IN(C1, C2, ...)}} is expanded to {{?x = C1 || ?x = C2 || .... }}. In > many places, working with expressions is a tree walk ({{ExprWalker}}). > The transformation is a left-deep tree: for a 4-long list: > {noformat} > (|| > (|| > (|| (= ?x C1) > (= ?x C2)) > (= ?x C3)) > (= ?x C4)) > {noformat} > so the walk is as deep as the list is long. A transformation rewrite is 3 > stack frames per level. The result is a huge number of stack frames until is > exceeds the stack space available. > A right-deep list would be better but only if all processing code is aware of > this and does a loop for the right recursion. -- This message was sent by Atlassian JIRA (v6.3.4#6332)