[26/53] [abbrv] hive git commit: HIVE-11316 : Use datastructure that doesnt duplicate any part of string for ASTNode::toStringTree() (Hari Subramaniyan, reviewed by Jesus Camacho Rodriguez)

[se...@apache.org]

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/llap
Commit: 2910b2a5f672d3d6133166ead4901755e39f5077
Parents: 8b2cd2a
Author: Hari Subramaniyan <ha...@apache.org>
Authored: Mon Aug 3 09:58:12 2015 -0700
Committer: Hari Subramaniyan <ha...@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);
+  }
 }