/*******************************************************************************
 * Copyright (c) 2012, 2017 Ericsson and others
 *
 * All rights reserved. This program and the accompanying materials are
 * made available under the terms of the Eclipse Public License 2.0 which
 * accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *   Alexandre Montplaisir - Initial API and implementation
 *   Patrick Tasse - Add message to exceptions
 *******************************************************************************/

package org.eclipse.tracecompass.internal.statesystem.core;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.regex.Pattern;

import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.tracecompass.common.core.log.TraceCompassLog;
import org.eclipse.tracecompass.common.core.log.TraceCompassLogUtils;
import org.eclipse.tracecompass.common.core.log.TraceCompassLogUtils.ScopeLog;
import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition;
import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition;
import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder;
import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend;
import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException;
import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException;
import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException;
import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval;
import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue;
import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue.Type;
import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;

import com.google.common.collect.ImmutableCollection.Builder;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;

/**
 * This is the core class of the Generic State System. It contains all the
 * methods to build and query a state history. It's exposed externally through
 * the IStateSystemQuerier and IStateSystemBuilder interfaces, depending if the
 * user needs read-only access or read-write access.
 *
 * When building, DON'T FORGET to call .closeHistory() when you are done
 * inserting intervals, or the storage backend will have no way of knowing it
 * can close and write itself to disk, and its thread will keep running.
 *
 * @author Alexandre Montplaisir
 *
 */
public class StateSystem implements ITmfStateSystemBuilder {

    private static final int MAX_STACK_DEPTH = 100000;
    private static final String PARENT = ".."; //$NON-NLS-1$
    private static final String WILDCARD = "*"; //$NON-NLS-1$

    private static final @NonNull Logger LOGGER = TraceCompassLog.getLogger(StateSystem.class);

    /* References to the inner structures */
    private final AttributeTree attributeTree;
    private final TransientState transState;
    private final IStateHistoryBackend backend;

    /* Latch tracking if the state history is done building or not */
    private final CountDownLatch finishedLatch = new CountDownLatch(1);

    private boolean buildCancelled = false;
    private boolean isDisposed = false;

    /**
     * New-file constructor. For when you build a state system with a new file,
     * or if the back-end does not require a file on disk.
     *
     * @param backend
     *            Back-end plugin to use
     */
    public StateSystem(@NonNull IStateHistoryBackend backend) {
        this.backend = backend;
        this.transState = new TransientState(backend);
        this.attributeTree = new AttributeTree(this);
    }

    /**
     * General constructor
     *
     * @param backend
     *            The "state history storage" back-end to use.
     * @param newFile
     *            Put true if this is a new history started from scratch. It is
     *            used to tell the state system where to get its attribute tree.
     * @throws IOException
     *             If there was a problem creating the new history file
     */
    public StateSystem(@NonNull IStateHistoryBackend backend, boolean newFile)
            throws IOException {
        this.backend = backend;
        this.transState = new TransientState(backend);

        if (newFile) {
            attributeTree = new AttributeTree(this);
        } else {
            /* We're opening an existing file */
            this.attributeTree = new AttributeTree(this, backend.supplyAttributeTreeReader());
            transState.setInactive();
            finishedLatch.countDown(); /* The history is already built */
        }
    }

    @Override
    public String getSSID() {
        return backend.getSSID();
    }

    @Override
    public boolean isCancelled() {
        return buildCancelled;
    }

    @Override
    public void waitUntilBuilt() {
        try {
            finishedLatch.await();
        } catch (InterruptedException e) {
            // Do nothing
        }
    }

    @Override
    public boolean waitUntilBuilt(long timeout) {
        boolean ret = false;
        try {
            ret = finishedLatch.await(timeout, TimeUnit.MILLISECONDS);
        } catch (InterruptedException e) {
            // Do nothing
        }
        return ret;
    }

    @Override
    public synchronized void dispose() {
        isDisposed = true;
        if (transState.isActive()) {
            transState.setInactive();
            buildCancelled = true;
        }
        backend.dispose();
    }

    // --------------------------------------------------------------------------
    // General methods related to the attribute tree
    // --------------------------------------------------------------------------

    /**
     * Get the attribute tree associated with this state system. This should be
     * the only way of accessing it (and if subclasses want to point to a
     * different attribute tree than their own, they should only need to
     * override this).
     *
     * @return The attribute tree
     */
    public AttributeTree getAttributeTree() {
        return attributeTree;
    }

    /**
     * Method used by the attribute tree when creating new attributes, to keep
     * the attribute count in the transient state in sync.
     */
    public void addEmptyAttribute() {
        transState.addEmptyEntry();
    }

    @Override
    public int getNbAttributes() {
        return getAttributeTree().getNbAttributes();
    }

    @Override
    public String getAttributeName(int attributeQuark) {
        return getAttributeTree().getAttributeName(attributeQuark);
    }

    @Override
    public String getFullAttributePath(int attributeQuark) {
        return getAttributeTree().getFullAttributeName(attributeQuark);
    }

    @Override
    public String[] getFullAttributePathArray(int attributeQuark) {
        return getAttributeTree().getFullAttributePathArray(attributeQuark);
    }

    // --------------------------------------------------------------------------
    // Methods related to the storage backend
    // --------------------------------------------------------------------------

    @Override
    public long getStartTime() {
        return backend.getStartTime();
    }

    @Override
    public long getCurrentEndTime() {
        return backend.getEndTime();
    }

    @Override
    public void closeHistory(long endTime) throws TimeRangeException {
        File attributeTreeFile;
        long attributeTreeFilePos;
        long realEndTime = endTime;

        if (realEndTime < backend.getEndTime()) {
            /*
             * This can happen (empty nodes pushing the border further, etc.)
             * but shouldn't be too big of a deal.
             */
            realEndTime = backend.getEndTime();
        }
        transState.closeTransientState(realEndTime);
        backend.finishedBuilding(realEndTime);

        attributeTreeFile = backend.supplyAttributeTreeWriterFile();
        attributeTreeFilePos = backend.supplyAttributeTreeWriterFilePosition();
        if (attributeTreeFile != null) {
            /*
             * If null was returned, we simply won't save the attribute tree,
             * too bad!
             */
            getAttributeTree().writeSelf(attributeTreeFile, attributeTreeFilePos);
        }
        finishedLatch.countDown(); /* Mark the history as finished building */
    }

    // --------------------------------------------------------------------------
    // Quark-retrieving methods
    // --------------------------------------------------------------------------

    @Override
    public int getQuarkAbsolute(String... attribute)
            throws AttributeNotFoundException {
        int quark = getAttributeTree().getQuarkDontAdd(ROOT_ATTRIBUTE, attribute);
        if (quark == INVALID_ATTRIBUTE) {
            throw new AttributeNotFoundException(getSSID() + " Path:" + Arrays.toString(attribute)); //$NON-NLS-1$
        }
        return quark;
    }

    @Override
    public int optQuarkAbsolute(String... attribute) {
        return getAttributeTree().getQuarkDontAdd(ROOT_ATTRIBUTE, attribute);
    }

    @Override
    public int getQuarkAbsoluteAndAdd(String... attribute) {
        return getAttributeTree().getQuarkAndAdd(ROOT_ATTRIBUTE, attribute);
    }

    @Override
    public int getQuarkRelative(int startingNodeQuark, String... subPath)
            throws AttributeNotFoundException {
        int quark = getAttributeTree().getQuarkDontAdd(startingNodeQuark, subPath);
        if (quark == INVALID_ATTRIBUTE) {
            throw new AttributeNotFoundException(getSSID() + " Quark:" + startingNodeQuark + ", SubPath:" + Arrays.toString(subPath)); //$NON-NLS-1$ //$NON-NLS-2$
        }
        return quark;
    }

    @Override
    public int optQuarkRelative(int startingNodeQuark, String... subPath) {
        return getAttributeTree().getQuarkDontAdd(startingNodeQuark, subPath);
    }

    @Override
    public int getQuarkRelativeAndAdd(int startingNodeQuark, String... subPath) {
        return getAttributeTree().getQuarkAndAdd(startingNodeQuark, subPath);
    }

    @Override
    public List<@NonNull Integer> getSubAttributes(int quark, boolean recursive) {
        return getAttributeTree().getSubAttributes(quark, recursive);
    }

    @Override
    public List<@NonNull Integer> getSubAttributes(int quark, boolean recursive, String pattern) {
        List<Integer> all = getSubAttributes(quark, recursive);
        List<@NonNull Integer> ret = new LinkedList<>();
        Pattern regex = Pattern.compile(pattern, Pattern.MULTILINE | Pattern.DOTALL);
        for (Integer attQuark : all) {
            String name = getAttributeName(attQuark.intValue());
            if (regex.matcher(name).matches()) {
                ret.add(attQuark);
            }
        }
        return ret;
    }

    @Override
    public int getParentAttributeQuark(int quark) {
        return getAttributeTree().getParentAttributeQuark(quark);
    }

    @Override
    public List<@NonNull Integer> getQuarks(String... pattern) {
        return getQuarks(ROOT_ATTRIBUTE, pattern);
    }

    @Override
    public List<@NonNull Integer> getQuarks(int startingNodeQuark, String... pattern) {
        Builder<@NonNull Integer> builder = ImmutableSet.builder();
        if (pattern.length > 0) {
            getQuarks(builder, startingNodeQuark, Arrays.asList(pattern));
        } else {
            builder.add(startingNodeQuark);
        }
        return builder.build().asList();
    }

    private void getQuarks(Builder<@NonNull Integer> builder, int quark, List<String> pattern) {
        String element = pattern.get(0);
        if (element == null) {
            return;
        }
        List<String> remainder = pattern.subList(1, pattern.size());
        if (remainder.isEmpty()) {
            if (element.equals(WILDCARD)) {
                builder.addAll(getSubAttributes(quark, false));
            } else if (element.equals(PARENT)) {
                builder.add(getParentAttributeQuark(quark));
            } else {
                int subQuark = optQuarkRelative(quark, element);
                if (subQuark != INVALID_ATTRIBUTE) {
                    builder.add(subQuark);
                }
            }
        } else {
            if (element.equals(WILDCARD)) {
                getSubAttributes(quark, false).forEach(subquark -> getQuarks(builder, subquark, remainder));
            } else if (element.equals(PARENT)) {
                getQuarks(builder, getParentAttributeQuark(quark), remainder);
            } else {
                int subQuark = optQuarkRelative(quark, element);
                if (subQuark != INVALID_ATTRIBUTE) {
                    getQuarks(builder, subQuark, remainder);
                }
            }
        }
    }

    // --------------------------------------------------------------------------
    // Methods related to insertions in the history
    // --------------------------------------------------------------------------

    @Override
    public void modifyAttribute(long t, Object value, int attributeQuark)
            throws TimeRangeException, StateValueTypeException {
        transState.processStateChange(t, value, attributeQuark);
    }

    @Override
    public void pushAttribute(long t, Object value, int attributeQuark)
            throws TimeRangeException, StateValueTypeException {
        int stackDepth;
        int subAttributeQuark;
        Object previousSV = transState.getOngoingStateValue(attributeQuark);

        if (previousSV == null) {
            /*
             * If the StateValue was null, this means this is the first time we
             * use this attribute. Leave stackDepth at 0.
             */
            stackDepth = 0;
        } else if (previousSV instanceof Integer) {
            /* Previous value was an integer, all is good, use it */
            stackDepth = (int) previousSV;
        } else {
            /* Previous state of this attribute was another type? Not good! */
            throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Type:" + previousSV.getClass() + ", Expected:" + Type.INTEGER); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
        }

        if (stackDepth >= MAX_STACK_DEPTH) {
            /*
             * Limit stackDepth to 100000, to avoid having Attribute Trees grow
             * out of control due to buggy insertions
             */
            String message = " Stack limit reached, not pushing"; //$NON-NLS-1$
            throw new IllegalStateException(getSSID() + " Quark:" + attributeQuark + message); //$NON-NLS-1$
        }

        stackDepth++;
        subAttributeQuark = getQuarkRelativeAndAdd(attributeQuark, String.valueOf(stackDepth));

        modifyAttribute(t, stackDepth, attributeQuark);
        modifyAttribute(t, value, subAttributeQuark);
    }

    @Override
    public ITmfStateValue popAttribute(long t, int attributeQuark)
            throws TimeRangeException, StateValueTypeException {
        Object pop = popAttributeObject(t, attributeQuark);
        return pop != null ? TmfStateValue.newValue(pop) : null;
    }

    @Override
    public Object popAttributeObject(long t, int attributeQuark)
            throws TimeRangeException, StateValueTypeException {
        /* These are the state values of the stack-attribute itself */
        @Nullable Object previousSV = transState.getOngoingStateValue(attributeQuark);

        if (previousSV == null) {
            /*
             * Trying to pop an empty stack. This often happens at the start of
             * traces, for example when we see a syscall_exit, without having
             * the corresponding syscall_entry in the trace. Just ignore
             * silently.
             */
            return null;
        }


        int stackDepth = 0;

        if (previousSV instanceof Integer) {
            stackDepth = (int) previousSV;
        } else {
            /* This on the other hand should not happen... */
            throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Stack depth:" + stackDepth); //$NON-NLS-1$//$NON-NLS-2$
        }

        /* The attribute should already exist at this point */
        int subAttributeQuark;
        try {
            subAttributeQuark = getQuarkRelative(attributeQuark, String.valueOf(stackDepth));
        } catch (AttributeNotFoundException e) {
            String message = " Stack attribute missing sub-attribute for depth:" + stackDepth; //$NON-NLS-1$
            throw new IllegalStateException(getSSID() + " Quark:" + attributeQuark + message); //$NON-NLS-1$
        }
        Object poppedValue = queryOngoing(subAttributeQuark);

        /* Update the state value of the stack-attribute */
        Integer nextSV;
        if (--stackDepth == 0) {
            /* Store a null state value */
            nextSV = null;
        } else {
            nextSV = stackDepth;
        }
        modifyAttribute(t, nextSV, attributeQuark);

        /* Delete the sub-attribute that contained the user's state value */
        removeAttribute(t, subAttributeQuark);

        return poppedValue;
    }

    @Override
    public void removeAttribute(long t, int attributeQuark)
            throws TimeRangeException {
        /*
         * Nullify our children first, recursively. We pass 'false' because we
         * handle the recursion ourselves.
         */
        List<Integer> childAttributes = getSubAttributes(attributeQuark, false);
        for (int childNodeQuark : childAttributes) {
            if (attributeQuark == childNodeQuark) {
                /* Something went very wrong when building out attribute tree */
                throw new IllegalStateException();
            }
            removeAttribute(t, childNodeQuark);
        }
        /* Nullify ourselves */
        try {
            transState.processStateChange(t, null, attributeQuark);
        } catch (StateValueTypeException e) {
            /*
             * Will not happen since we're inserting null values only, but poor
             * compiler has no way of knowing this...
             */
            throw new IllegalStateException(e);
        }
    }

    // --------------------------------------------------------------------------
    // "Current" query/update methods
    // --------------------------------------------------------------------------

    @Override
    public ITmfStateValue queryOngoingState(int attributeQuark) {
        return TmfStateValue.newValue(queryOngoing(attributeQuark));
    }

    @Override
    public Object queryOngoing(int attributeQuark) {
        return transState.getOngoingStateValue(attributeQuark);
    }

    @Override
    public List<@Nullable Object> queryOngoing() {
        return transState.getOngoingStateValues();
    }

    @Override
    public long getOngoingStartTime(int attribute) {
        return transState.getOngoingStartTime(attribute);
    }

    @Override
    public void updateOngoingState(ITmfStateValue newValue, int attributeQuark) {
        transState.changeOngoingStateValue(attributeQuark, newValue.unboxValue());
    }

    @Override
    public void updateOngoingState(Object newValue, int attributeQuark) {
        transState.changeOngoingStateValue(attributeQuark, newValue);
    }

    /**
     * Modify the whole "ongoing state" (state values + start times). This can
     * be used when "seeking" a state system to a different point in the trace
     * (and restoring the known stateInfo at this location). Use with care!
     *
     * @param newStateIntervals
     *            The new List of state values to use as ongoing state info
     */
    protected void replaceOngoingState(@NonNull List<@NonNull ITmfStateInterval> newStateIntervals) {
        transState.replaceOngoingState(newStateIntervals);
    }

    // --------------------------------------------------------------------------
    // Regular query methods (sent to the back-end)
    // --------------------------------------------------------------------------

    @Override
    public List<ITmfStateInterval> queryFullState(long t)
            throws TimeRangeException, StateSystemDisposedException {
        if (isDisposed) {
            throw new StateSystemDisposedException();
        }

        try (ScopeLog log = new ScopeLog(LOGGER, Level.FINER, "StateSystem:FullQuery", //$NON-NLS-1$
                "ssid", getSSID(), "ts", t);) { //$NON-NLS-1$ //$NON-NLS-2$

            final int nbAttr = getNbAttributes();
            List<@Nullable ITmfStateInterval> stateInfo = new ArrayList<>(nbAttr);

            /*
             * Bring the size of the array to the current number of attributes
             */
            for (int i = 0; i < nbAttr; i++) {
                stateInfo.add(null);
            }

            /*
             * If we are currently building the history, also query the
             * "ongoing" states for stuff that might not yet be written to the
             * history.
             */
            if (transState.isActive()) {
                transState.doQuery(stateInfo, t);
            }

            /* Query the storage backend */
            backend.doQuery(stateInfo, t);

            /*
             * We should have previously inserted an interval for every
             * attribute.
             */
            for (ITmfStateInterval interval : stateInfo) {
                if (interval == null) {
                    throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
                }
            }
            return stateInfo;
        }
    }

    @Override
    public ITmfStateInterval querySingleState(long t, int attributeQuark)
            throws TimeRangeException, StateSystemDisposedException {
        if (isDisposed) {
            throw new StateSystemDisposedException();
        }
        try (TraceCompassLogUtils.ScopeLog log = new TraceCompassLogUtils.ScopeLog(LOGGER, Level.FINER, "StateSystem:SingleQuery", //$NON-NLS-1$
                "ssid", this.getSSID(), //$NON-NLS-1$
                "ts", t, //$NON-NLS-1$
                "attribute", attributeQuark)) { //$NON-NLS-1$
            ITmfStateInterval ret = transState.getIntervalAt(t, attributeQuark);
            if (ret == null) {
                /*
                 * The transient state did not have the information, let's look
                 * into the backend next.
                 */
                ret = backend.doSingularQuery(t, attributeQuark);
            }

            if (ret == null) {
                /*
                 * If we did our job correctly, there should be intervals for
                 * every possible attribute, over all the valid time range.
                 */
                throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
            }
            return ret;
        }
    }

    @Override
    public Iterable<@NonNull ITmfStateInterval> query2D(Collection<@NonNull Integer> quarks, Collection<@NonNull Long> times)
            throws StateSystemDisposedException, TimeRangeException, IndexOutOfBoundsException {
        if (isDisposed) {
            throw new StateSystemDisposedException();
        }
        if (times.isEmpty()) {
            return Collections.emptyList();
        }

        TimeRangeCondition timeCondition = TimeRangeCondition.forDiscreteRange(times);
        return query2D(quarks, timeCondition, false);
    }

    @Override
    public Iterable<@NonNull ITmfStateInterval> query2D(Collection<@NonNull Integer> quarks, long start, long end)
            throws StateSystemDisposedException, TimeRangeException, IndexOutOfBoundsException {
        if (isDisposed) {
            throw new StateSystemDisposedException();
        }

        boolean reverse = (start > end) ? true : false;
        TimeRangeCondition timeCondition = TimeRangeCondition.forContinuousRange(Math.min(start, end), Math.max(start, end));
        return query2D(quarks, timeCondition, reverse);
    }

    private Iterable<@NonNull ITmfStateInterval> query2D(@NonNull Collection<@NonNull Integer> quarks, TimeRangeCondition timeCondition, boolean reverse)
            throws TimeRangeException, IndexOutOfBoundsException {
        if (timeCondition.min() < getStartTime()) {
            throw new TimeRangeException("Time conditions " + timeCondition.min() + " is lower than state system start time: " + getStartTime());  //$NON-NLS-1$ //$NON-NLS-2$
        }

        if (quarks.isEmpty()) {
            return Collections.emptyList();
        }

        IntegerRangeCondition quarkCondition = IntegerRangeCondition.forDiscreteRange(quarks);
        if (quarkCondition.min() < 0 || quarkCondition.max() >= getNbAttributes()) {
            throw new IndexOutOfBoundsException();
        }

        Iterable<@NonNull ITmfStateInterval> transStateIterable = transState.query2D(quarks, timeCondition);
        Iterable<@NonNull ITmfStateInterval> backendIterable = backend.query2D(quarkCondition, timeCondition, reverse);

        return Iterables.concat(transStateIterable, backendIterable);
    }

    @Override
    public void removeFiles() {
        backend.removeFiles();
    }

    // --------------------------------------------------------------------------
    // Debug methods
    // --------------------------------------------------------------------------

    static void logMissingInterval(int attribute, long timestamp) {
        Activator.getDefault().logInfo("No data found in history for attribute " + //$NON-NLS-1$
                attribute + " at time " + timestamp + //$NON-NLS-1$
                ", returning dummy interval"); //$NON-NLS-1$
    }
}