/*******************************************************************************
 * Copyright (c) 2008, 2020 SAP AG and IBM Corporation.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *    SAP AG - initial API and implementation
 *    Andrew Johnson (IBM Corporation)- for comparisons
 *******************************************************************************/
package org.eclipse.mat.inspections;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;

import org.eclipse.core.runtime.Status;
import org.eclipse.mat.SnapshotException;
import org.eclipse.mat.collect.ArrayInt;
import org.eclipse.mat.collect.ArrayIntBig;
import org.eclipse.mat.collect.BitField;
import org.eclipse.mat.internal.MATPlugin;
import org.eclipse.mat.internal.Messages;
import org.eclipse.mat.query.Bytes;
import org.eclipse.mat.query.Column;
import org.eclipse.mat.query.ContextProvider;
import org.eclipse.mat.query.IContextObject;
import org.eclipse.mat.query.IContextObjectSet;
import org.eclipse.mat.query.IQuery;
import org.eclipse.mat.query.IResult;
import org.eclipse.mat.query.IResultTable;
import org.eclipse.mat.query.ResultMetaData;
import org.eclipse.mat.query.annotations.Argument;
import org.eclipse.mat.query.annotations.Category;
import org.eclipse.mat.query.annotations.CommandName;
import org.eclipse.mat.query.annotations.Icon;
import org.eclipse.mat.snapshot.ClassHistogramRecord;
import org.eclipse.mat.snapshot.ClassLoaderHistogramRecord;
import org.eclipse.mat.snapshot.Histogram;
import org.eclipse.mat.snapshot.IMultiplePathsFromGCRootsComputer;
import org.eclipse.mat.snapshot.ISnapshot;
import org.eclipse.mat.snapshot.MultiplePathsFromGCRootsRecord;
import org.eclipse.mat.snapshot.model.IClass;
import org.eclipse.mat.snapshot.model.IObject;
import org.eclipse.mat.util.IProgressListener;
import org.eclipse.mat.util.MessageUtil;

import com.ibm.icu.text.NumberFormat;

@CommandName("find_leaks")
@Category(Category.HIDDEN)
@Icon("/META-INF/icons/leak.gif")
public class FindLeaksQuery implements IQuery
{

    // ///////////////////////////////////////////
    //
    // static fields
    //
    // ///////////////////////////////////////////

    private final static Set<String> REFERENCE_FIELD_SET = new HashSet<String>(Arrays
                    .asList(new String[] { "referent" })); //$NON-NLS-1$
    private final static int MAX_DEPTH = 1000;

    // ////////////////////////////////////////////
    //
    // Command parameters
    //
    // ////////////////////////////////////////////

    @Argument
    public ISnapshot snapshot;

    @Argument(isMandatory = false)
    public int threshold_percent = 20;

    @Argument(isMandatory = false)
    public int max_paths = 10000;

    // @Argument(isMandatory = false, flag = "big_drop_ratio")
    public double big_drop_ratio = 0.7;

    public IResult execute(IProgressListener listener) throws Exception
    {
        long totalHeap;
        int[] topDominators;

        totalHeap = snapshot.getSnapshotInfo().getUsedHeapSize();
        topDominators = snapshot.getImmediateDominatedIds(-1);
        long threshold = threshold_percent * totalHeap / 100;

        /*
         * find suspect single objects
         */
        listener.subTask(Messages.FindLeaksQuery_SearchingSingleObjects);

        ArrayInt suspiciousObjects = new ArrayInt();
        Set<String> suspectNames = new HashSet<String>();
        int i = 0;
        while (i < topDominators.length && snapshot.getRetainedHeapSize(topDominators[i]) > threshold)
        {
            suspiciousObjects.add(topDominators[i]);
            suspectNames.add(snapshot.getClassOf(topDominators[i]).getName());
            i++;
        }

        if (listener.isCanceled())
            throw new IProgressListener.OperationCanceledException();

        /*
         * Find suspect classes
         */
        listener.subTask(Messages.FindLeaksQuery_SearchingGroupsOfObjects);

        Histogram histogram = groupByClasses(topDominators, listener);
        ArrayList<ClassHistogramRecord> suspiciousClasses = new ArrayList<ClassHistogramRecord>();

        ClassHistogramRecord[] classRecords = histogram.getClassHistogramRecords().toArray(new ClassHistogramRecord[0]);
        Arrays.sort(classRecords, Histogram.reverseComparator(Histogram.COMPARATOR_FOR_RETAINEDHEAPSIZE));

        int k = 0;
        while (k < classRecords.length && classRecords[k].getRetainedHeapSize() > threshold)
        {
            // avoid showing class-suspect for s.th. which was found on object
            // level
            if (!suspectNames.contains(classRecords[k].getLabel()))
            {
                suspiciousClasses.add(classRecords[k]);
            }
            k++;
        }

        if (listener.isCanceled())
            throw new IProgressListener.OperationCanceledException();

        /*
         * build the results
         */
        return buildResult(suspiciousObjects, suspiciousClasses, totalHeap, listener);

    }

    private Histogram groupByClasses(int[] dominated, IProgressListener listener) throws SnapshotException
    {
        Histogram histogram = snapshot.getHistogram(dominated, listener);
        if (listener.isCanceled())
            throw new IProgressListener.OperationCanceledException();

        Collection<ClassHistogramRecord> records = histogram.getClassHistogramRecords();
        ClassHistogramRecord[] arr = new ClassHistogramRecord[records.size()];
        int i = 0;

        for (ClassHistogramRecord record : records)
        {
            record.setRetainedHeapSize(sumRetainedSize(record.getObjectIds(), snapshot));
            arr[i++] = record;
            if (i % 10 == 0 && listener.isCanceled())
                throw new IProgressListener.OperationCanceledException();
        }

        Collection<ClassLoaderHistogramRecord> loaderRecords = histogram.getClassLoaderHistogramRecords();
        ClassLoaderHistogramRecord[] loaderArr = new ClassLoaderHistogramRecord[loaderRecords.size()];
        i = 0;

        for (ClassLoaderHistogramRecord record : loaderRecords)
        {
            long retainedSize = 0;
            for (ClassHistogramRecord classRecord : record.getClassHistogramRecords())
            {
                retainedSize += classRecord.getRetainedHeapSize();
            }

            record.setRetainedHeapSize(retainedSize);
            loaderArr[i++] = record;
        }

        return histogram;

    }

    private long sumRetainedSize(int[] objectIds, ISnapshot snapshot) throws SnapshotException
    {
        long sum = 0;
        for (int id : objectIds)
        {
            sum += snapshot.getRetainedHeapSize(id);
        }
        return sum;
    }

    private AccumulationPoint findAccumulationPoint(int bigObjectId) throws SnapshotException
    {
        int dominator = bigObjectId;
        double dominatorRetainedSize = snapshot.getRetainedHeapSize(dominator);
        int dominated[] = snapshot.getImmediateDominatedIds(dominator);

        int depth = 0;
        while (dominated != null && dominated.length != 0 && depth < MAX_DEPTH)
        {
            double dominatedRetainedSize = snapshot.getRetainedHeapSize(dominated[0]);
            if (dominatedRetainedSize / dominatorRetainedSize < big_drop_ratio) { return new AccumulationPoint(snapshot
                            .getObject(dominator)); }

            dominatorRetainedSize = dominatedRetainedSize;
            dominator = dominated[0];
            dominated = snapshot.getImmediateDominatedIds(dominator);
            depth++;
        }

        if (dominated == null || dominated.length == 0)
            return new AccumulationPoint(snapshot.getObject(dominator));

        return null;
    }

    private SuspectRecord buildSuspectRecordGroupOfObjects(ClassHistogramRecord record, IProgressListener listener)
                    throws SnapshotException
    {
        int[] objectIds = getRandomIds(record.getObjectIds());
        IObject suspectClass = snapshot.getObject(record.getClassId());

        // calculate the shortest paths to all
        // avoid weak paths
        Map<IClass, Set<String>> excludeMap = new HashMap<IClass, Set<String>>();
        Collection<IClass> classes = snapshot.getClassesByName("java.lang.ref.WeakReference", true); //$NON-NLS-1$
        if (classes != null)
            for (IClass clazz : classes)
            {
                excludeMap.put(clazz, REFERENCE_FIELD_SET);
            }

        IMultiplePathsFromGCRootsComputer comp = snapshot.getMultiplePathsFromGCRoots(objectIds, excludeMap);

        MultiplePathsFromGCRootsRecord[] records = comp.getPathsByGCRoot(listener);
        ArrayIntBig commonPath = new ArrayIntBig();

        if (listener.isCanceled())
            throw new IProgressListener.OperationCanceledException();

        int numPaths = comp.getAllPaths(listener).length;
        int diff = objectIds.length - numPaths;
        if (diff > 0)
        {
            listener.sendUserMessage(IProgressListener.Severity.INFO, MessageUtil.format(
                            Messages.FindLeaksQuery_PathNotFound, diff, objectIds.length), null);
        }
        setRetainedSizesForMPaths(records, snapshot);
        Arrays.sort(records, MultiplePathsFromGCRootsRecord.getComparatorByNumberOfReferencedObjects());

        MultiplePathsFromGCRootsRecord parentRecord = records[0];

        // parentRecord.getReferencedRetainedSize()
        int threshold = (int) (0.8 * objectIds.length);

        while (parentRecord.getCount() > threshold)
        {
            // System.out.println("count: " + parentRecord.getCount());
            commonPath.add(parentRecord.getObjectId());

            MultiplePathsFromGCRootsRecord[] children = parentRecord.nextLevel();
            if (children == null || children.length == 0)
            {
                // reached the end ?! report the parent as it is big enough
                AccumulationPoint accPoint = new AccumulationPoint(snapshot.getObject(parentRecord.getObjectId()));
                SuspectRecordGroupOfObjects result = new SuspectRecordGroupOfObjects(suspectClass, record
                                .getObjectIds(), record.getRetainedHeapSize(), accPoint, commonPath.toArray(), comp);
                return result;
            }
            setRetainedSizesForMPaths(children, snapshot);
            Arrays.sort(children, MultiplePathsFromGCRootsRecord.getComparatorByNumberOfReferencedObjects());

            if ((double) children[0].getReferencedRetainedSize() / (double) parentRecord.getReferencedRetainedSize() < big_drop_ratio)
            {
                // there is a big drop here - return the parent
                AccumulationPoint accPoint = new AccumulationPoint(snapshot.getObject(parentRecord.getObjectId()));
                SuspectRecordGroupOfObjects result = new SuspectRecordGroupOfObjects(suspectClass, record
                                .getObjectIds(), record.getRetainedHeapSize(), accPoint, commonPath.toArray(), comp);
                return result;
            }

            // no big drop - take the biggest child and try again
            parentRecord = children[0];
        }

        // return a SuspectRecord without an accumulation point
        return new SuspectRecordGroupOfObjects(suspectClass, record.getObjectIds(), record.getRetainedHeapSize(), null,
                        commonPath.toArray(), comp);
    }

    private void setRetainedSizesForMPaths(MultiplePathsFromGCRootsRecord[] records, ISnapshot snapshot)
                    throws SnapshotException
    {
        for (MultiplePathsFromGCRootsRecord rec : records)
        {
            int[] referencedObjects = rec.getReferencedObjects();
            long retained = 0;
            for (int objectId : referencedObjects)
            {
                retained += snapshot.getRetainedHeapSize(objectId);
            }
            rec.setReferencedRetainedSize(retained);
        }
    }

    private IResult buildResult(ArrayInt suspiciousObjects, ArrayList<ClassHistogramRecord> suspiciousClasses,
                    long totalHeap, IProgressListener listener) throws SnapshotException
    {
        SuspectRecord[] allSuspects = new SuspectRecord[suspiciousObjects.size() + suspiciousClasses.size()];
        int j = 0;
        int[] suspectObjIds = suspiciousObjects.toArray();
        for (int objectId : suspectObjIds)
        {
            if (listener.isCanceled())
                throw new IProgressListener.OperationCanceledException();

            IObject suspectObject = snapshot.getObject(objectId);
            AccumulationPoint accPoint = findAccumulationPoint(objectId);
            SuspectRecord r = new SuspectRecord(suspectObject, suspectObject.getRetainedHeapSize(), accPoint);

            allSuspects[j++] = r;
        }

        for (ClassHistogramRecord record : suspiciousClasses)
        {
            if (listener.isCanceled())
                throw new IProgressListener.OperationCanceledException();

            SuspectRecord r = buildSuspectRecordGroupOfObjects(record, /*
                                                                        * (long)
                                                                        * (
                                                                        * threshold
                                                                        * 0.7),
                                                                        */listener);
            allSuspects[j++] = r;
        }

        return new SuspectsResultTable(allSuspects, totalHeap);
    }

    private int[] getRandomIds(int[] objectIds)
    {
        if (objectIds.length <= max_paths)
            return objectIds;

        MATPlugin.log(new Status(Status.INFO, MATPlugin.PLUGIN_ID, MessageUtil.format(
                        Messages.FindLeaksQuery_TooManySuspects,
                        objectIds.length, max_paths)));

        Random random = new Random();
        int length = objectIds.length;
        BitField visited = new BitField(length);

        int[] result = new int[max_paths];
        for (int i = 0; i < max_paths; i++)
        {
            int index = random.nextInt(length);
            while (visited.get(index))
                index = random.nextInt(length);

            visited.set(index);
            result[i] = objectIds[index];
        }
        return result;
    }

    public static class AccumulationPoint
    {
        IObject object;

        public AccumulationPoint(IObject object)
        {
            this.object = object;
        }

        public IObject getObject()
        {
            return object;
        }

        public long getRetainedHeapSize()
        {
            return getObject().getRetainedHeapSize();
        }
    }

    public static class AccumulationPointOfGroupOfObject extends AccumulationPoint
    {
        int[] commonPath;
        IMultiplePathsFromGCRootsComputer pathsComputer;

        public AccumulationPointOfGroupOfObject(IObject object, int[] commonPath,
                        IMultiplePathsFromGCRootsComputer pathsComputer)
        {
            super(object);
            this.commonPath = commonPath;
            this.pathsComputer = pathsComputer;
        }

        public int[] getCommonPath()
        {
            return commonPath;
        }

        public IMultiplePathsFromGCRootsComputer getPathsComputer()
        {
            return pathsComputer;
        }
    }

    public static class SuspectRecordGroupOfObjects extends SuspectRecord
    {
        int[] commonPath;
        IMultiplePathsFromGCRootsComputer pathsComputer;
        int[] suspectInstances;

        SuspectRecordGroupOfObjects(IObject suspect, int[] suspectInstances, long suspectRetained,
                        AccumulationPoint accumulationPoint, int[] commonPath,
                        IMultiplePathsFromGCRootsComputer pathsComputer)
        {
            super(suspect, suspectRetained, accumulationPoint);
            this.suspectInstances = suspectInstances;
            this.commonPath = commonPath;
            this.pathsComputer = pathsComputer;
        }

        public int[] getCommonPath()
        {
            return commonPath;
        }

        public IMultiplePathsFromGCRootsComputer getPathsComputer()
        {
            return pathsComputer;
        }

        public int[] getSuspectInstances()
        {
            return suspectInstances;
        }

    }

    public static class SuspectRecord
    {
        IObject suspect;

        Bytes suspectRetained;
        AccumulationPoint accumulationPoint;

        SuspectRecord(IObject suspect, long suspectRetained, AccumulationPoint accumulationPoint)
        {
            this.suspect = suspect;
            this.suspectRetained = new Bytes(suspectRetained);
            this.accumulationPoint = accumulationPoint;
        }

        public IObject getSuspect()
        {
            return suspect;
        }

        public long getSuspectRetained()
        {
            return suspectRetained.getValue();
        }

        public AccumulationPoint getAccumulationPoint()
        {
            return accumulationPoint;
        }
    }

    public static class SuspectsResultTable implements IResultTable
    {
        SuspectRecord[] data;
        long totalHeap;

        public SuspectsResultTable(SuspectRecord[] data, long totalHeap)
        {
            this.data = data;
            this.totalHeap = totalHeap;
        }

        public ResultMetaData getResultMetaData()
        {
            return new ResultMetaData.Builder() //

                            .addContext(new ContextProvider(Messages.FindLeaksQuery_LeakSuspect)
                            {
                                @Override
                                public IContextObject getContext(Object row)
                                {
                                    return getLeakSuspect(row);
                                }
                            }) //

                            .addContext(new ContextProvider(Messages.FindLeaksQuery_AccumulationPoint)
                            {
                                @Override
                                public IContextObject getContext(Object row)
                                {
                                    return getAccumulationPoint(row);
                                }
                            }) //

                            .build();
        }

        public Column[] getColumns()
        {
            return new Column[] { new Column(Messages.FindLeaksQuery_ColumnLeakSuspect), //
                            new Column(Messages.FindLeaksQuery_Column_NumObjects, Long.class), //
                            new Column(Messages.FindLeaksQuery_Column_SuspectRetainedHeap, Bytes.class), //
                            new Column(Messages.FindLeaksQuery_Column_SuspectPercent, Double.class).formatting(NumberFormat.getPercentInstance()), //
                            new Column(Messages.FindLeaksQuery_Column_AccumulationPoint), //
                            new Column(Messages.FindLeaksQuery_Column_AccPointRetainedHeap, Bytes.class), //
                            new Column(Messages.FindLeaksQuery_Column_AccPointPercent, Double.class).formatting(NumberFormat.getPercentInstance()) };
        }

        public int getRowCount()
        {
            return data.length;
        }

        public SuspectRecord getRow(int rowId)
        {
            return data[rowId];
        }

        public Object getColumnValue(Object row, int columnIndex)
        {
            SuspectRecord suspect = (SuspectRecord) row;
            switch (columnIndex)
            {
                case 0:
                    return suspect.suspect.getTechnicalName();
                case 1:
                    return suspect instanceof SuspectRecordGroupOfObjects ? ((SuspectRecordGroupOfObjects) suspect).suspectInstances.length
                                    : 1;
                case 2:
                    return suspect.suspectRetained;
                case 3:
                    return Double.valueOf((double) suspect.getSuspectRetained() / (double) totalHeap);
                case 4:
                    return suspect.accumulationPoint == null ? Messages.FindLeaksQuery_NotFound : suspect.accumulationPoint.getObject()
                                    .getTechnicalName();
                case 5:
                    return new Bytes(suspect.accumulationPoint == null ? 0 : suspect.accumulationPoint
                                    .getRetainedHeapSize());
                case 6:
                    return suspect.accumulationPoint == null ? 0 : Double.valueOf((double) suspect.accumulationPoint
                                    .getRetainedHeapSize()
                                    / (double) totalHeap);
            }

            return null;
        }

        public IContextObject getContext(final Object row)
        {
            return new IContextObject()
            {
                public int getObjectId()
                {
                    return ((SuspectRecord) row).suspect.getObjectId();
                }
            };
        }

        IContextObject getLeakSuspect(Object row)
        {
            final SuspectRecord suspect = (SuspectRecord) row;

            if (suspect instanceof SuspectRecordGroupOfObjects)
            {
                return new IContextObjectSet()
                {
                    public int getObjectId()
                    {
                        return suspect.suspect.getObjectId();
                    }

                    public int[] getObjectIds()
                    {
                        return ((SuspectRecordGroupOfObjects) suspect).suspectInstances;
                    }

                    public String getOQL()
                    {
                        return null;
                    }
                };
            }
            else
            {
                return new IContextObject()
                {
                    public int getObjectId()
                    {
                        return suspect.suspect.getObjectId();
                    }
                };
            }
        }

        IContextObject getAccumulationPoint(final Object row)
        {
            final SuspectRecord suspect = (SuspectRecord) row;

            if (suspect.accumulationPoint == null)
                return null;

            return new IContextObject()
            {
                public int getObjectId()
                {
                    return suspect.accumulationPoint.getObject().getObjectId();
                }
            };
        }

        public SuspectRecord[] getData()
        {
            return data;
        }

        public long getTotalHeap()
        {
            return totalHeap;
        }
    }
}