/*
 * JBoss, Home of Professional Open Source.
 * See the COPYRIGHT.txt file distributed with this work for information
 * regarding copyright ownership.  Some portions may be licensed
 * to Red Hat, Inc. under one or more contributor license agreements.
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301 USA.
 * Modified by
 * @author  Data Virtuality GmbH
 * @date    $Date$
 *  
 */
// https://issues.jboss.org/browse/TEIID-2626
// https://issues.jboss.org/browse/TEIID-2707
// https://issues.jboss.org/browse/TEIID-2900
// https://issues.jboss.org/browse/TEIID-2902
// https://issues.jboss.org/browse/TEIID-2457
// https://issues.jboss.org/browse/TEIID-2942
// https://github.com/teiid/teiid/commit/f840ed8283aad9cbe8d3019467a88d951d695659
// https://issues.jboss.org/browse/TEIID-2482
// https://issues.jboss.org/browse/TEIID-2346
// https://issues.jboss.org/browse/TEIID-2430
// https://issues.jboss.org/browse/TEIID-2731
// https://issues.jboss.org/browse/TEIID-2747
// https://issues.jboss.org/browse/TEIID-2946
// https://issues.jboss.org/browse/TEIID-3716
// https://issues.jboss.org/browse/TEIID-4237
// https://issues.jboss.org/browse/TEIID-3973
// https://issues.jboss.org/browse/TEIID-4144
// https://issues.jboss.org/browse/TEIID-5152
// https://issues.jboss.org/browse/TEIID-2245
// https://issues.jboss.org/browse/TEIID-4812
// https://issues.redhat.com/browse/TEIID-3156
// https://issues.redhat.com/browse/TEIID-4129
package org.teiid.query.optimizer.relational.rules;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.teiid.api.exception.query.QueryMetadataException;
import org.teiid.api.exception.query.QueryPlannerException;
import org.teiid.core.TeiidComponentException;
import org.teiid.query.QueryPlugin;
import org.teiid.query.analysis.AnalysisRecord;
import org.teiid.query.metadata.QueryMetadataInterface;
import org.teiid.query.metadata.TempMetadataAdapter;
import org.teiid.query.optimizer.capabilities.CapabilitiesFinder;
import org.teiid.query.optimizer.relational.OptimizerRule;
import org.teiid.query.optimizer.relational.RuleStack;
import org.teiid.query.optimizer.relational.plantree.NodeConstants;
import org.teiid.query.optimizer.relational.plantree.NodeConstants.Info;
import org.teiid.query.optimizer.relational.plantree.NodeEditor;
import org.teiid.query.optimizer.relational.plantree.NodeFactory;
import org.teiid.query.optimizer.relational.plantree.PlanNode;
import org.teiid.query.processor.relational.JoinNode.JoinStrategyType;
import org.teiid.query.processor.relational.MergeJoinStrategy.SortOption;
import org.teiid.query.processor.relational.RelationalNode;
import org.teiid.query.sql.lang.CompareCriteria;
import org.teiid.query.sql.lang.Criteria;
import org.teiid.query.sql.lang.JoinType;
import org.teiid.query.sql.lang.OrderBy;
import org.teiid.query.sql.symbol.ElementSymbol;
import org.teiid.query.sql.symbol.Expression;
import org.teiid.query.sql.symbol.GroupSymbol;
import org.teiid.query.sql.util.SymbolMap;
import org.teiid.query.sql.visitor.GroupsUsedByElementsVisitor;
import org.teiid.query.util.CommandContext;


/**
 * Inserts sort nodes for specific join strategies.
 */
public class RuleImplementJoinStrategy implements OptimizerRule {
        
    /** 
     * @see org.teiid.query.optimizer.relational.OptimizerRule#execute(org.teiid.query.optimizer.relational.plantree.PlanNode, org.teiid.query.metadata.QueryMetadataInterface, org.teiid.query.optimizer.capabilities.CapabilitiesFinder, org.teiid.query.optimizer.relational.RuleStack, org.teiid.query.analysis.AnalysisRecord, org.teiid.query.util.CommandContext)
     */
    public PlanNode execute(PlanNode plan,
                            QueryMetadataInterface metadata,
                            CapabilitiesFinder capabilitiesFinder,
                            RuleStack rules,
                            AnalysisRecord analysisRecord,
                            CommandContext context) throws QueryPlannerException,
                                                   QueryMetadataException,
                                                   TeiidComponentException {
    	
    	for (PlanNode sourceNode : NodeEditor.findAllNodes(plan, NodeConstants.Types.SOURCE, NodeConstants.Types.ACCESS)) {
    		SymbolMap references = (SymbolMap)sourceNode.getProperty(NodeConstants.Info.CORRELATED_REFERENCES);
	        if (references != null) {
	        	Set<GroupSymbol> groups = GroupsUsedByElementsVisitor.getGroups(references.getValues());
	        	PlanNode joinNode = NodeEditor.findParent(sourceNode, NodeConstants.Types.JOIN, NodeConstants.Types.SOURCE);
	        	while (joinNode != null) {
	        		if (joinNode.getGroups().containsAll(groups)) {
	        			joinNode.setProperty(NodeConstants.Info.JOIN_STRATEGY, JoinStrategyType.NESTED_TABLE);
	        			Info info = Info.RIGHT_NESTED_REFERENCES;
	        			if (!FrameUtil.findJoinSourceNode(joinNode.getFirstChild()).getGroups().containsAll(groups)) {
					        throw new AssertionError(QueryPlugin.Util.gs(QueryPlugin.Event.DVCORE301233));
	        			}
				        SymbolMap map = (SymbolMap) joinNode.getProperty(info);
        				if (map == null) {
        					map = new SymbolMap();
        				}
        				joinNode.setProperty(info, map);
	        			map.asUpdatableMap().putAll(references.asMap());
		        		if (joinNode.getProperty(NodeConstants.Info.DEPENDENT_VALUE_SOURCE) != null) {
		        			//sanity check
		        			throw new AssertionError(QueryPlugin.Util.gs(QueryPlugin.Event.DVCORE301247));
		        		}
	        			break;
	        		}
	        		joinNode = NodeEditor.findParent(joinNode, NodeConstants.Types.JOIN, NodeConstants.Types.SOURCE);
	        	}
	        }
    	}

        for (PlanNode joinNode : NodeEditor.findAllNodes(plan, NodeConstants.Types.JOIN, NodeConstants.Types.ACCESS)) {
            JoinStrategyType stype = (JoinStrategyType) joinNode.getProperty(NodeConstants.Info.JOIN_STRATEGY);
            if (!JoinStrategyType.MERGE.equals(stype)) {
            	continue;
            } 

            List<Expression> leftExpressions = (List<Expression>) joinNode.getProperty(NodeConstants.Info.LEFT_EXPRESSIONS);
            List<Expression> rightExpressions = (List<Expression>) joinNode.getProperty(NodeConstants.Info.RIGHT_EXPRESSIONS);
            int origExpressionCount = leftExpressions.size();

            //check index information on each side
            //TODO: don't do null order compensation - in fact we should check what the order actually is, but we don't have that metadata
            Object key = null;
            boolean right = true;
            //we check the right first, since it should be larger
            if (joinNode.getLastChild().getType() == NodeConstants.Types.ACCESS && NewCalculateCostUtil.isSingleTable(joinNode.getLastChild())) {
            	key = NewCalculateCostUtil.getKeyUsed(rightExpressions, null, metadata, null);
            }
            if (key == null && joinNode.getFirstChild().getType() == NodeConstants.Types.ACCESS && NewCalculateCostUtil.isSingleTable(joinNode.getFirstChild())) {
            	key = NewCalculateCostUtil.getKeyUsed(leftExpressions, null, metadata, null);
            	right = false;
            }
            JoinType joinType = (JoinType) joinNode.getProperty(NodeConstants.Info.JOIN_TYPE);
            /**
             * Don't push sorts for unbalanced inner joins, we prefer to use a processing time cost based decision 
             */
            boolean pushLeft = true;
            boolean pushRight = true;
            if ((joinType == JoinType.JOIN_INNER || joinType == JoinType.JOIN_LEFT_OUTER) && context != null) {
            	float leftCost = NewCalculateCostUtil.computeCostForTree(joinNode.getFirstChild(), metadata);
            	float rightCost = NewCalculateCostUtil.computeCostForTree(joinNode.getLastChild(), metadata);
            	if (leftCost != NewCalculateCostUtil.UNKNOWN_VALUE && rightCost != NewCalculateCostUtil.UNKNOWN_VALUE 
            			&& (leftCost > context.getProcessorBatchSize() || rightCost > context.getProcessorBatchSize())) {
            		//we use a larger constant here to ensure that we don't unwisely prevent pushdown
            		pushLeft = leftCost < context.getProcessorBatchSize() || leftCost / rightCost < 8 || (key != null && !right);
            		pushRight = rightCost < context.getProcessorBatchSize() || rightCost / leftCost < 8 || joinType == JoinType.JOIN_LEFT_OUTER || (key != null && right);
            	}
            }
            // EXTENSION
            // ISSUE: DVCORE-2572
            // FIXED BY: Roman Pedchenko
            // DATE: 2014.11.19
            // ADOPTED FROM: https://issues.jboss.org/browse/TEIID-2190
            // if (key != null) {
            if (key != null && joinNode.getProperty(NodeConstants.Info.DEPENDENT_VALUE_SOURCE) == null) {
            // END EXTENSION
            	//redo the join predicates based upon the key alone
            	List<Object> keyCols = metadata.getElementIDsInKey(key);
            	int[] reorder = new int[keyCols.size()];
            	// EXTENSION
            	// ISSUE: DVCORE-2572
            	// FIXED BY: Roman Pedchenko
            	// DATE: 2014.11.19
            	// ADOPTED FROM: https://issues.jboss.org/browse/TEIID-2190
            	// List<Integer> toCriteria = new ArrayList<Integer>(rightExpressions.size() - keyCols.size()); 
            	LinkedHashSet<Integer> toCriteria = new LinkedHashSet<Integer>();
            	// END EXTENSION
            	List<Expression> keyExpressions = right?rightExpressions:leftExpressions;
            	// EXTENSION
            	// ISSUE: DVCORE-2572
            	// FIXED BY: Roman Pedchenko
            	// DATE: 2014.11.19,2015.01.22
            	// ADOPTED FROM: https://issues.jboss.org/browse/TEIID-2190,https://issues.jboss.org/browse/TEIID-3296
            	// for (int j = 0; j < keyExpressions.size(); j++) {
            	// 	Expression ses = keyExpressions.get(j);
            	// 	if (!(ses instanceof ElementSymbol)) {
            	Map<Object, Integer> indexMap = new LinkedHashMap<Object, Integer>();
            	for (int i = 0; i < keyExpressions.size(); i++) {
            		Expression ses = keyExpressions.get(i);
            		if (!(ses instanceof ElementSymbol)) {
            			toCriteria.add(i);
            	// END EXTENSION
						continue;
					}
        		// EXTENSION
        		// ISSUE: DVCORE-2572
        		// FIXED BY: Roman Pedchenko
        		// DATE: 2014.11.19
        		// ADOPTED FROM: https://issues.jboss.org/browse/TEIID-2190
        		// 	ElementSymbol es = (ElementSymbol)ses;
        		// 	boolean found = false;
        		// 	for (int i = 0; !found && i < keyCols.size(); i++) {
        		// 		if (es.getMetadataID().equals(keyCols.get(i))) {
        		// 			reorder[i] = j;
        		// 			found = true;
            		Integer existing = indexMap.put(((ElementSymbol)ses).getMetadataID(), i);
            		if (existing != null) {
            			toCriteria.add(existing);
            		}
            	}
            	boolean found = true;
        		for (int i = 0; i < keyCols.size(); i++) {
        			Object id = keyCols.get(i);
        			Integer index = indexMap.remove(id);
        			if (index == null) {
        				found = false;
        				break;
        			}
        			reorder[i] = index;
				}
        		if (found) {
        			toCriteria.addAll(indexMap.values());
	        		List<Criteria> joinCriteria = (List<Criteria>) joinNode.getProperty(Info.NON_EQUI_JOIN_CRITERIA);
	        		for (int index : toCriteria) {
						Expression lses = leftExpressions.get(index);
						Expression rses = rightExpressions.get(index);
						CompareCriteria cc = new CompareCriteria(lses, CompareCriteria.EQ, rses);
						if (joinCriteria == null || joinCriteria.isEmpty()) {
							joinCriteria = new ArrayList<Criteria>();
        		// END EXTENSION
						}
// EXTENSION
// ISSUE: DVCORE-2572
// FIXED BY: Roman Pedchenko
// DATE: 2014.11.19
// ADOPTED FROM: https://issues.jboss.org/browse/TEIID-2190
//     				}
//     				if (!found) {
//     					toCriteria.add(j);
//     				}
//     			}
//         		List<Criteria> joinCriteria = (List<Criteria>) joinNode.getProperty(Info.NON_EQUI_JOIN_CRITERIA);
//         		for (int index : toCriteria) {
//     				Expression lses = leftExpressions.get(index);
//     				Expression rses = rightExpressions.get(index);
//     				CompareCriteria cc = new CompareCriteria(lses, CompareCriteria.EQ, rses);
//     				if (joinCriteria == null || joinCriteria.isEmpty()) {
//     					joinCriteria = new ArrayList<Criteria>();
// END EXTENSION
						joinCriteria.add(cc);
					}
        		// EXTENSION
        		// ISSUE: DVCORE-2572
        		// FIXED BY: Roman Pedchenko
        		// DATE: 2014.11.19
        		// ADOPTED FROM: https://issues.jboss.org/browse/TEIID-2190
        		// }
        		// joinNode.setProperty(Info.NON_EQUI_JOIN_CRITERIA, joinCriteria);
        		// leftExpressions = RelationalNode.projectTuple(reorder, leftExpressions);
        		// rightExpressions = RelationalNode.projectTuple(reorder, rightExpressions);
        		// joinNode.setProperty(NodeConstants.Info.LEFT_EXPRESSIONS, leftExpressions);
        		// joinNode.setProperty(NodeConstants.Info.RIGHT_EXPRESSIONS, rightExpressions);
	        		joinNode.setProperty(Info.NON_EQUI_JOIN_CRITERIA, joinCriteria);
	        		leftExpressions = RelationalNode.projectTuple(reorder, leftExpressions);
	            	rightExpressions = RelationalNode.projectTuple(reorder, rightExpressions);
	            	joinNode.setProperty(NodeConstants.Info.LEFT_EXPRESSIONS, leftExpressions);
	            	joinNode.setProperty(NodeConstants.Info.RIGHT_EXPRESSIONS, rightExpressions);
        		}
        		// END EXTENSION
            }

			boolean pushedLeft = insertSort(joinNode.getFirstChild(), leftExpressions, joinNode, metadata, capabilitiesFinder, pushLeft, context);
			
			//TODO: this check could be performed, as it implies we're using enhanced and can back out of the sort
			//      but this not valid in all circumstances
			//if (!pushedLeft && joinNode.getProperty(NodeConstants.Info.DEPENDENT_VALUE_SOURCE) != null && joinType == JoinType.JOIN_INNER) {
				//pushRight = true; //this sort will not be used if more than one source command is generated
			//}
			
	        if (origExpressionCount == 1 
	        		&& joinType == JoinType.JOIN_INNER 
	        		&& joinNode.getProperty(NodeConstants.Info.DEPENDENT_VALUE_SOURCE) != null
	        		&& !joinNode.hasCollectionProperty(Info.NON_EQUI_JOIN_CRITERIA)) {
	        	Collection<Expression> output = (Collection<Expression>) joinNode.getProperty(NodeConstants.Info.OUTPUT_COLS);
	        	Collection<GroupSymbol> groups = GroupsUsedByElementsVisitor.getGroups(output);
	        	if (Collections.disjoint(groups, FrameUtil.findJoinSourceNode(joinNode.getFirstChild()).getGroups())) {
	        		pushRight = false;
	        		joinNode.setProperty(Info.IS_SEMI_DEP, Boolean.TRUE);
	        	}
			}

			boolean pushedRight = insertSort(joinNode.getLastChild(), rightExpressions, joinNode, metadata, capabilitiesFinder, pushRight, context);
        	if ((!pushedRight || !pushedLeft) && (joinType == JoinType.JOIN_INNER || (joinType == JoinType.JOIN_LEFT_OUTER && !pushedLeft))) {
        		joinNode.setProperty(NodeConstants.Info.JOIN_STRATEGY, JoinStrategyType.ENHANCED_SORT);
        	}
        }
        
        return plan;
    }

    /**
     * Insert a sort node under the merge join node.  If necessary, also insert a project
     * node to handle function evaluation.  
     * @param expressions The expressions that need to be sorted on 
     * @param jnode The planner merge join node to attach to
     * @return returns true if a project node needs added
     * @throws TeiidComponentException 
     * @throws QueryMetadataException 
     */
    static boolean insertSort(PlanNode childNode, List<Expression> expressions, PlanNode jnode, QueryMetadataInterface metadata, CapabilitiesFinder capFinder,
    		boolean attemptPush, CommandContext context) throws QueryMetadataException, TeiidComponentException {
        Set<Expression> orderSymbols = new LinkedHashSet<Expression>(expressions); 

        PlanNode sourceNode = FrameUtil.findJoinSourceNode(childNode);
        PlanNode joinNode = childNode.getParent();

        Set<Expression> outputSymbols = new LinkedHashSet<Expression>((List<Expression>)sourceNode.getProperty(NodeConstants.Info.OUTPUT_COLS));
        
        int oldSize = outputSymbols.size();
        
        outputSymbols.addAll(expressions);

	    //TODO: generally we're compensating for expressions used in predicates
	    //and end up pulling redundant values
	    boolean needsCorrection = outputSymbols.size() > oldSize;
                
        PlanNode sortNode = createSortNode(new ArrayList<Expression>(orderSymbols), outputSymbols);
        
        boolean distinct = false;
        if (sourceNode.getFirstChild() != null && sourceNode.getType() == NodeConstants.Types.SOURCE && outputSymbols.size() == expressions.size() && outputSymbols.containsAll(expressions)) {
        	PlanNode setOp = NodeEditor.findNodePreOrder(sourceNode.getFirstChild(), NodeConstants.Types.SET_OP, NodeConstants.Types.SOURCE);
        	if (setOp != null) {
        		if (!setOp.hasBooleanProperty(NodeConstants.Info.USE_ALL)) {
        			distinct = true;
        		}
        	} else if (NodeEditor.findNodePreOrder(sourceNode.getFirstChild(), NodeConstants.Types.DUP_REMOVE, NodeConstants.Types.PROJECT) != null) {
	        	distinct = true;
	        }
        }
        
        boolean sort = true;
        
        if (sourceNode.getType() == NodeConstants.Types.ACCESS) {
	        boolean usesKey = NewCalculateCostUtil.usesKey(sourceNode, expressions, metadata);
	        if (distinct || usesKey) {
                joinNode.setProperty(joinNode.getFirstChild() == childNode ? NodeConstants.Info.IS_LEFT_DISTINCT : NodeConstants.Info.IS_RIGHT_DISTINCT, true);
        	}
	        if (!usesKey && RuleRaiseAccess.getModelIDFromAccess(sourceNode, metadata) == TempMetadataAdapter.TEMP_MODEL) {
		        attemptPush = false;
	        }
	        if (attemptPush && RuleRaiseAccess.canRaiseOverSort(sourceNode, metadata, capFinder, sortNode, null, false, context, true)) {
	            sourceNode.getFirstChild().addAsParent(sortNode);
	            
	            if (needsCorrection) {
	            	correctOutputElements(joinNode, expressions, sortNode.getParent());
	            }
	            return true;
	        }
        } else if (sourceNode.getType() == NodeConstants.Types.GROUP) {
        	sourceNode.addAsParent(sortNode);
        	sort = false; // the grouping columns must contain all of the ordering columns
        }
        
        if (distinct) {
            joinNode.setProperty(joinNode.getFirstChild() == childNode ? NodeConstants.Info.IS_LEFT_DISTINCT : NodeConstants.Info.IS_RIGHT_DISTINCT, true);
    	}
        
        if (sort) {
        	joinNode.setProperty(joinNode.getFirstChild() == childNode ? NodeConstants.Info.SORT_LEFT : NodeConstants.Info.SORT_RIGHT, SortOption.SORT);
        }        
        
        if (needsCorrection) {
            PlanNode projectNode = NodeFactory.getNewNode(NodeConstants.Types.PROJECT);
            projectNode.setProperty(NodeConstants.Info.PROJECT_COLS, new ArrayList(outputSymbols));
            projectNode.setProperty(NodeConstants.Info.OUTPUT_COLS, new ArrayList<Expression>(outputSymbols));
	        sourceNode.addAsParent(projectNode);
            correctOutputElements(joinNode, expressions, projectNode.getParent());
        }        
        return false;
    }

    private static PlanNode createSortNode(List<Expression> orderSymbols,
                                           Collection outputElements) {
        PlanNode sortNode = NodeFactory.getNewNode(NodeConstants.Types.SORT);
        sortNode.setProperty(NodeConstants.Info.SORT_ORDER, new OrderBy(orderSymbols));
        sortNode.setProperty(NodeConstants.Info.OUTPUT_COLS, new ArrayList(outputElements));
        return sortNode;
    }

    private static void correctOutputElements(PlanNode endNode,
                                              Collection outputElements,
                                              PlanNode startNode) {
        while (startNode != endNode) {
        	LinkedHashSet<Expression> outputSymbols = new LinkedHashSet<Expression>((List<Expression>)startNode.getProperty(NodeConstants.Info.OUTPUT_COLS));
            outputSymbols.addAll(outputElements);
            startNode.setProperty(NodeConstants.Info.OUTPUT_COLS, new ArrayList<Expression>(outputSymbols));
			if (startNode.getProperty(NodeConstants.Info.PROJECT_COLS) != null)
	            startNode.setProperty(NodeConstants.Info.PROJECT_COLS, new ArrayList<Expression>(outputSymbols));
            startNode = startNode.getParent();
        }
    }
            
    /** 
     * @see java.lang.Object#toString()
     */
    public String toString() {
        return "ImplementJoinStrategy"; //$NON-NLS-1$
    }

}
