db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Knut Anders Hatlen (JIRA)" <j...@apache.org>
Subject [jira] Commented: (DERBY-4421) Allow Visitors to process the nodes bottom-up
Date Fri, 23 Oct 2009 12:02:00 GMT

    [ https://issues.apache.org/jira/browse/DERBY-4421?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12769189#action_12769189

Knut Anders Hatlen commented on DERBY-4421:

I propose that we add a method to the Visitor interface to control whether the visitor should
visit parents or children first:

	 * Method that is called to see if {@code visit()} should be called on
	 * the children of {@code node} before it is called on {@code node} itself.
	 * If this method always returns {@code true}, the visitor will walk the
	 * tree bottom-up. If it always returns {@code false}, the tree is visited
	 * top-down.
	 * @param node the top node of a sub-tree about to be visited
	 * @return {@code true} if {@code node}'s children should be visited
	 * before {@code node}, {@code false} otherwise
	boolean visitChildrenFirst(Visitable node);

QueryTreeNode.accept() must be changed to check the return value of this method, and all the
existing visitors must implement the method (should return false, since all the current visitors
walk the tree top-down).

> Allow Visitors to process the nodes bottom-up
> ---------------------------------------------
>                 Key: DERBY-4421
>                 URL: https://issues.apache.org/jira/browse/DERBY-4421
>             Project: Derby
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions:
>            Reporter: Knut Anders Hatlen
>            Priority: Minor
> Currently, QueryTreeNode.accept() walks the tree top-down, always calling
> visit() on the parent before it calls visit() on the children. Although this
> is fine in most cases, there are use cases where visiting the nodes
> bottom-up would be better. One example is mentioned in DERBY-4416. The
> visitor posted there looks for binary comparison operators and checks
> whether both operands are constants. If they are, the operator is replaced
> with a boolean constant.
> Take this expression as an example: (1<2)=(2>1)
> The query tree looks like this:
>        =
>      /   \
>     /     \
>    <       >
>   / \     / \
>  /   \   /   \
> 1     2 2     1
> If we walk the tree top-down with the said visitor, the = node doesn't have
> constant operands when it's visited. The < and > operators do have constant
> operands, and they're both replaced with constant TRUE. This means the
> expression (1<2)=(2>1) is rewritten to TRUE=TRUE, and that's how far the
> transformation goes.
> If the tree had been processed bottom-up, we would start with the < and >
> operators, and again replace them with TRUE. The query tree would therefore
> have been transformed to this intermediate form when the = operator was
> visited:
>        =
>      /   \
>     /     \
> This is the same as the end result when visiting top-down, but now the =
> operator hasn't been visited yet. Since both the operands of the = operator
> are constants, the visitor will perform yet another transformation so the
> tree is simplified further and ends up as:
>     TRUE

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message