Build JPA Specification from tree

Question

I have created an API which allows users to build out queries using a tree. The tree is built from the SearchOperationRequest class.

@Data
@ApiModel(value = "SearchOperationRequest", description = "Condition for the query")
public class SearchOperationRequest {

    @ApiModelProperty(value = "Conditional statement for the where clause", allowableValues = "EQUALS, NOT_EQUALS, GREATER_THAN, LESS_THAN, LIKE, STARTS_WITH, ENDS_WITH, CONTAINS")
    private SearchConditionOperation condition;

    @ApiModelProperty(value = "Column name to be searched on")
    private String column;

    @ApiModelProperty(value = "Value of column")
    private Object value;

    @ApiModelProperty(value = "Value of OR / AND")
    private SearchComparator comparator;

    @ApiModelProperty(value = "Left node of comparator condition")
    private SearchOperationRequest left;

    @ApiModelProperty(value = "Right node of comparator condition")
    private SearchOperationRequest right;

    public boolean isTreeLeaf() {
        return left == null && right == null;
    }

    public boolean isComparator() {
        return comparator != null;
    }
}

So from this example I could create a SearchOperationRequest that asks for all WHERE hidden = false AND X = 88

"searchOperation": {
    "left": {
        "column": "Hidden",
        "condition": "EQUALS",
        "value": false
    },
    "comparator": "AND",
    "right": {
        "left": {
            "column": "X",
            "condition": "EQUALS",
            "value": 88
        },
        "comparator": "AND"
    }
}

This request is built into a specification using a generic specification builder.

public class GenericSpecificationsBuilder<U> {

    public Specification<U> buildSpecificationFromSearchOperationRequest(SearchOperationRequest root, Function<SpecificationSearchCriteria, Specification<U>> converter) {

        Stack<SearchOperationRequest> stack = new Stack<>();

        Stack<SearchOperationRequest> comparatorStack = new Stack<>();
        Deque<Specification<U>> specStack = new LinkedList<>();

        SearchOperationRequest pointer = root;

        while (pointer != null || !stack.empty()) {

            if (pointer.isTreeLeaf()) {
                specStack.push(converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue())));
            }

            if (pointer.isComparator()) {
                comparatorStack.push(pointer);
            }

            if (pointer.getRight() != null) {
                stack.push(pointer.getRight());
            }

            if (pointer.getLeft() != null) {
                pointer.setRight(pointer.getLeft());
                pointer.setLeft(null);
            } else if (!stack.empty()) {
                SearchOperationRequest temp = stack.pop();
                pointer.setRight(temp);
            }

            pointer = pointer.getRight();
        }


        while (specStack.size() <= comparatorStack.size()) {
            comparatorStack.pop();
        }

        while (!comparatorStack.empty()) {

            SearchOperationRequest searchOperationRequest = comparatorStack.pop();

            Specification<U> operand1 = specStack.pop();
            Specification<U> operand2 = specStack.pop();
            if (searchOperationRequest.getComparator().equals(SearchComparator.AND)) {
                specStack.push(Specification.where(operand1)
                        .and(operand2));
            } else if (searchOperationRequest.getComparator().equals(SearchComparator.OR)) {
                specStack.push(Specification.where(operand1)
                        .or(operand2));
            }
        }


        return specStack.pop();
    }
}

My current works great for RIGHT heavy tree's. Meaning queries such as:

WHERE X = 6 AND X = 9
WHERE Z = 5 OR T=9
WHERE Z = 5 OR T=9 OR H=6

But it does not work with building more complex trees where the criteria in braces should get precedence and executed first.

WHERE (X = 6 OR Z = 9) AND (T=6 OR H=8)

The model for this more complex SearchOperationRequest would be:

"searchOperation": {
    "left": {
        "left": {
            "column": "X",
            "condition": "EQUALS",
            "value": 6
        },
        "comparator": "AND",
        "right": {
            "column": "Z",
            "condition": "EQUALS",
            "value": 9
        }
    },
    "comparator": "AND",
    "right": {
        "left": {
            "column": "T",
            "condition": "EQUALS",
            "value": 6
        },
        "comparator": "AND",
        "right": {
            "column": "H",
            "condition": "EQUALS",
            "value": 8
        }
    }
}

How do I modify my GenericSpecificationsBuilder to be able to handle more complex SearchOperationRequest trees?

Answer 1

Let's follow the execution flow using your example tree.

         AND
      /       \
  leftOR     rightOR
  /    \     /    \ 
X=6   Z=9  T=6   H=8

When we exit the first while loop, our stacks look like:

stack = {}
comparatorStack = { AND, leftOR, rightOR }
specStack = { X=6, Z=9, T=6, H=8 }

The same state enters the final while loop.

while (!comparatorStack.empty()) {

    SearchOperationRequest searchOperationRequest = comparatorStack.pop();

    Specification<U> operand1 = specStack.pop();
    Specification<U> operand2 = specStack.pop();
    if (searchOperationRequest.getComparator().equals(SearchComparator.AND)) {
        specStack.push(Specification.where(operand1)
                .and(operand2));
    } else if (searchOperationRequest.getComparator().equals(SearchComparator.OR)) {
        specStack.push(Specification.where(operand1)
                .or(operand2));
    }
}

The problem here is you're pushing the result back on the specStack. So at the second iteration, you'll be popping off the result of the first iteration (the rightOR), as well as Z=9, and apply the leftOr logic to it.

Decomposing the tree

Let's take a step back and look at how you decompose the tree, more specifically:

if (pointer.getLeft() != null) {
    pointer.setRight(pointer.getLeft());
    pointer.setLeft(null);
} else if (!stack.empty()) {
    SearchOperationRequest temp = stack.pop();
    pointer.setRight(temp);
}

The problem with this code is you are altering the nodes in the tree. In the first example, at one time our pointer points to the node:

    Z=9      
  /     \ 
null   rightOR

That doesn't look right. Instead of decomposing the tree using a stack (Depth First Search), you could use a queue (Breadth First Search) and get the ordering you're after for free.

Does that solve the problem of applying each logical operator (comparator) to the right operands? Not quite, to be able to solve both layouts below, we could decompose the operators and operands in different workflows, instead of all of them together.

         AND                    |                    rootAND                 
      /       \                 |                  /         \    
  leftOR     rightOR            |              leftOR       rightOR  
  /    \     /    \             |              /    \       /    \   
X=6   Z=9  T=6   H=8            |            X=6    AND    Z=9   H=8   
                                |                 /    \      
                                |               T=6   Y=3 

Solution

The first json-like representation in your post has an illogical layout, as logical operators are expected to operate on both a left and right operand. Instead you had:

"right": {
    "left": {
        "column": "X",
        "condition": "EQUALS",
        "value": 88
    },
    "comparator": "AND"
}

Let's consider a solution for symmetrical representations, one where both a left and right operand are present for each logical operator.

First we process the tree Breadth First, level by level. Meanwhile, we put each comparator on a stack, so we get the last ones out first in our second while loop.

In the second loop we then use a new Queue to store our 'in-between-results' as we work our way back to the root.

Queue<SearchOperationRequest> queue = new LinkedList<>();
Deque<SearchOperationRequest> comparatorStack = new LinkedList<>();

if (root == null || !root.isComparator()) return;
queue.add(root);
while(!queue.isEmpty()){
    SearchOperationRequest node = queue.poll();
    comparatorStack.push(node);
    if(node.left != null && node.left.isComparator()) queue.add(node.left);
    if(node.right != null && node.right.isComparator()) queue.add(node.right);
}

Queue<Specification> specQueue = new LinkedList<>();
while(!comparatorStack.isEmpty()){
    SearchOperationRequest comparator = comparatorStack.pop();
    // reverse operand order so already computed values are polled correctly
    Specification operand2; 
    SearchOperationRequest pointer = comparator.getRight();
    if(pointer.isTreeLeaf()) {
        operand2 = converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue()));
    } else {
        operand2 = specQueue.poll();
    }
    Specification operand1; 
    pointer = comparator.getLeft();
    if(pointer.isTreeLeaf()) {
        operand1 = converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue()));
    } else {
        operand1 = specQueue.poll();
    }
    if (comparator.equals(SearchComparator.AND)) {
        specQueue.add(Specification.where(operand1).and(operand2));
    } else if (comparator.equals(SearchComparator.OR)) {
        specQueue.add(Specification.where(operand1).or(operand2));
    }
} 

return specQueue.poll();

I haven't tested the code, but you should be able to extract (and refactor) the workflows.