Repository: hive Updated Branches: refs/heads/master 8b2cd2abf -> 2910b2a5f
HIVE-11316 : Use datastructure that doesnt duplicate any part of string for ASTNode::toStringTree() (Hari Subramaniyan, reviewed by Jesus Camacho Rodriguez) Project: http://git-wip-us.apache.org/repos/asf/hive/repo Commit: http://git-wip-us.apache.org/repos/asf/hive/commit/2910b2a5 Tree: http://git-wip-us.apache.org/repos/asf/hive/tree/2910b2a5 Diff: http://git-wip-us.apache.org/repos/asf/hive/diff/2910b2a5 Branch: refs/heads/master Commit: 2910b2a5f672d3d6133166ead4901755e39f5077 Parents: 8b2cd2a Author: Hari Subramaniyan <harisan...@apache.org> Authored: Mon Aug 3 09:58:12 2015 -0700 Committer: Hari Subramaniyan <harisan...@apache.org> Committed: Mon Aug 3 09:58:12 2015 -0700 ---------------------------------------------------------------------- .../apache/hadoop/hive/ql/parse/ASTNode.java | 139 ++++++++++++++++++- 1 file changed, 138 insertions(+), 1 deletion(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/hive/blob/2910b2a5/ql/src/java/org/apache/hadoop/hive/ql/parse/ASTNode.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/parse/ASTNode.java b/ql/src/java/org/apache/hadoop/hive/ql/parse/ASTNode.java index c8dbe97..136d481 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/parse/ASTNode.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/parse/ASTNode.java @@ -20,6 +20,7 @@ package org.apache.hadoop.hive.ql.parse; import java.io.Serializable; import java.util.ArrayList; +import java.util.List; import org.antlr.runtime.Token; import org.antlr.runtime.tree.CommonTree; @@ -31,8 +32,12 @@ import org.apache.hadoop.hive.ql.lib.Node; */ public class ASTNode extends CommonTree implements Node,Serializable { private static final long serialVersionUID = 1L; - + private transient StringBuffer astStr; private transient ASTNodeOrigin origin; + private transient int startIndx = -1; + private transient int endIndx = -1; + private transient ASTNode rootNode; + private transient boolean isValidASTStr; public ASTNode() { } @@ -81,6 +86,7 @@ public class ASTNode extends CommonTree implements Node,Serializable { * * @see org.apache.hadoop.hive.ql.lib.Node#getName() */ + @Override public String getName() { return (Integer.valueOf(super.getToken().getType())).toString(); } @@ -126,4 +132,135 @@ public class ASTNode extends CommonTree implements Node,Serializable { } return sb; } + + private ASTNode getRootNodeWithValidASTStr (boolean useMemoizedRoot) { + if (useMemoizedRoot && rootNode != null && rootNode.parent == null && + rootNode.hasValidMemoizedString()) { + return rootNode; + } + ASTNode retNode = this; + while (retNode.parent != null) { + retNode = (ASTNode) retNode.parent; + } + rootNode=retNode; + rootNode.astStr = new StringBuffer(); + rootNode.toStringTree(rootNode); + rootNode.isValidASTStr = true; + return retNode; + } + + private boolean hasValidMemoizedString() { + return isValidASTStr && astStr != null; + } + + private void resetRootInformation() { + // Reset the previously stored rootNode string + if (rootNode != null) { + rootNode.astStr = null; + rootNode.isValidASTStr = false; + } + // The root might have changed because of tree modifications. + // Compute the new root for this tree and set the astStr. + getRootNodeWithValidASTStr(false); + } + + private int getMemoizedStringLen() { + return astStr == null ? 0 : astStr.length(); + } + + private String getMemoizedSubString(int start, int end) { + return (astStr == null || start < 0 || end > astStr.length() || start >= end) ? null : + astStr.subSequence(start, end).toString(); + } + + private void addtoMemoizedString(String string) { + if (astStr == null) { + astStr = new StringBuffer(); + } + astStr.append(string); + } + + @Override + public void setParent(Tree t) { + super.setParent(t); + resetRootInformation(); + } + + @Override + public void addChild(Tree t) { + super.addChild(t); + resetRootInformation(); + } + + @Override + public void addChildren(List kids) { + super.addChildren(kids); + resetRootInformation(); + } + + @Override + public void setChild(int i, Tree t) { + super.setChild(i, t); + resetRootInformation(); + } + + @Override + public void insertChild(int i, Object t) { + super.insertChild(i, t); + resetRootInformation(); + } + + @Override + public Object deleteChild(int i) { + Object ret = super.deleteChild(i); + resetRootInformation(); + return ret; + } + + @Override + public void replaceChildren(int startChildIndex, int stopChildIndex, Object t) { + super.replaceChildren(startChildIndex, stopChildIndex, t); + resetRootInformation(); + } + + @Override + public String toStringTree() { + // The tree modifier functions invalidate the old astStr, rootNode, etc. + // Hence, we can use the memoized root node and string values here. + ASTNode rootNode = (ASTNode)this.getRootNodeWithValidASTStr(true); + + // If rootNotModified is false, then startIndx and endIndx will be stale. + if (startIndx >= 0 && endIndx <= rootNode.getMemoizedStringLen()) { + return rootNode.getMemoizedSubString(startIndx, endIndx); + } + return toStringTree(rootNode); + } + + private String toStringTree(ASTNode rootNode) { + this.rootNode = rootNode; + startIndx = rootNode.getMemoizedStringLen(); + // Leaf node + if ( children==null || children.size()==0 ) { + rootNode.addtoMemoizedString(this.toString()); + endIndx = rootNode.getMemoizedStringLen(); + return this.toString(); + } + if ( !isNil() ) { + rootNode.addtoMemoizedString("("); + rootNode.addtoMemoizedString(this.toString()); + rootNode.addtoMemoizedString(" "); + } + for (int i = 0; children!=null && i < children.size(); i++) { + ASTNode t = (ASTNode)children.get(i); + if ( i>0 ) { + rootNode.addtoMemoizedString(" "); + } + t.toStringTree(rootNode); + } + if ( !isNil() ) { + rootNode.addtoMemoizedString(")"); + } + endIndx = rootNode.getMemoizedStringLen(); + return rootNode.getMemoizedSubString(startIndx, endIndx); + } }
