/*-------------------------------------------------------------------------+
|                                                                          |
| Copyright 2005-2011 the ConQAT Project                                   |
|                                                                          |
| Licensed under the Apache License, Version 2.0 (the "License");          |
| you may not use this file except in compliance with the License.         |
| You may obtain a copy of the License at                                  |
|                                                                          |
|    http://www.apache.org/licenses/LICENSE-2.0                            |
|                                                                          |
| Unless required by applicable law or agreed to in writing, software      |
| distributed under the License is distributed on an "AS IS" BASIS,        |
| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| See the License for the specific language governing permissions and      |
| limitations under the License.                                           |
+-------------------------------------------------------------------------*/
package eu.cqse.check.framework.preprocessor.c;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.EnumSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.function.Predicate;
import java.util.regex.Pattern;

import javax.annotation.Nonnull;

import org.apache.logging.log4j.LogManager;
import org.conqat.lib.commons.assertion.CCSMAssert;
import org.conqat.lib.commons.cache4j.ICache;
import org.conqat.lib.commons.cache4j.SynchronizedCache;
import org.conqat.lib.commons.cache4j.backend.ECachingStrategy;
import org.conqat.lib.commons.collections.CollectionUtils;
import org.conqat.lib.commons.collections.UnmodifiableList;
import org.conqat.lib.commons.error.NeverThrownRuntimeException;
import org.conqat.lib.commons.factory.ForwardingFactory;
import org.conqat.lib.commons.region.RegionSet;
import org.conqat.lib.commons.string.StringUtils;

import eu.cqse.check.framework.preprocessor.IPreprocessor;
import eu.cqse.check.framework.scanner.ETokenType;
import eu.cqse.check.framework.scanner.IToken;
import eu.cqse.check.framework.shallowparser.TokenStreamUtils;

/**
 * Base class of the C preprocessor that deals with macro handling and the
 * overall parsing.
 *
 * The design of the preprocessor uses inheritance to separate the aspects macro
 * handling, include handling, and conditionals to separate classes. This is
 * meant to keep the classes small and easier to understand, while still
 * providing a final common class, that can be easily extended by subclassing
 * and overriding certain methods, which would be hard when using
 * delegation/composition.
 */
public abstract class MacroHandlingCPreprocessorBase implements IPreprocessor {

        /** The cache used for storing macro tokens. */
        @SuppressWarnings("unchecked")
        private static final ICache<ObtainMacroTokensKey, UnmodifiableList<IToken>, NeverThrownRuntimeException> MACRO_TOKEN_CACHE = new SynchronizedCache<>(
                        "MACRO-TOKEN-CACHE", ForwardingFactory.INSTANCE,
                        ECachingStrategy.LRU.<ObtainMacroTokensKey, UnmodifiableList<IToken>>getBackend(500));

        /** Default name for the varargs parameter. */
        private static final String DEFAULT_VAR_ARGS_NAME = "__VA_ARGS__";

        /** Patterns used for finding if directives (and ifdef, ifndef, ...). */
        private static final Pattern IF_DIRECTIVE_START_PATTERN = Pattern.compile("^#\\s*if");

        /**
         * Patterns used for finding pragma directives. #pragma is the old C pragma
         * directive. _pragma (...) is a newer C99 pattern which is replaced with
         * #pragma by the compiler.
         */
        private static final Pattern PRAGMA_DIRECTIVE_START_PATTERN = Pattern.compile("^(#|__|_)pragma",
                        Pattern.CASE_INSENSITIVE);

        /**
         * Maximal number of nested expansions, used to defend against infinite
         * recursion.
         */
        private static final int EXPANSION_LIMIT = 30;

        /**
         * Maximal number of nested inclusions, used to defend against infinite
         * recursion.
         */
        private static final int INCLUSION_LIMIT = 20;

        /** The origin name used for macro tokens. */
        public static final String MACRO_ORIGIN = "##macro##";

        /** Returns whether the given token is inserted by macro expansion. */
        public static final Predicate<IToken> IS_MACRO_TOKEN = token -> MACRO_ORIGIN.equals(token.getOriginId());

        /** The macro provider used. */
        protected final OverlayMacroProvider macroProvider;

        /**
         * The currently processed uniform path (for error reporting).
         */
        private String uniformPath = "";

        /**
         * Tokens that must not be expanded any further. The C++ Spec Section 16.3.4
         * [cpp.rescan] paragraph 2 specifies that tokens that are ignored once are no
         * longer available for further macro replacements.
         */
        private HashSet<IToken> ignoredTokens = new HashSet<>();

        /** Constructor. */
        protected MacroHandlingCPreprocessorBase(IMacroProvider macroProvider) {
                this.macroProvider = new OverlayMacroProvider(macroProvider);
        }

        /** {@inheritDoc} */
        @Override
        public List<IToken> preprocess(String uniformPath, List<IToken> tokens) {
                return preprocess(uniformPath, new ArrayList<>(tokens), INCLUSION_LIMIT, new HashSet<>());
        }

        /**
         * Sets the uniform path which is used in warning messages.
         */
        public void setUniformPath(String uniformPath) {
                this.uniformPath = uniformPath;
        }

        /**
         * Performs the actual preprocessing of the given tokens. The given list of
         * tokens might be changed.
         *
         * @param uniformPath
         *            may be null if this information is not available.
         */
        protected List<IToken> preprocess(String uniformPath, List<IToken> tokens, int inclusionLimit,
                        Set<String> seenPaths) {
                ignoredTokens.clear();
                List<IToken> result = new ArrayList<>();
                if (uniformPath != null && seenPaths.contains(uniformPath)) {
                        return result;
                } else if (uniformPath != null) {
                        seenPaths.add(uniformPath);
                }
                RegionSet ignoredRegions = new RegionSet();

                for (int i = 0; i < tokens.size(); ++i) {
                        if (ignoredRegions.contains(i)) {
                                continue;
                        }

                        IToken token = tokens.get(i);
                        if (isPragmaDirective(token)) {
                                i = handlePragmaDirective(tokens, i);
                                continue;
                        }
                        switch (token.getType()) {
                        case PREPROCESSOR_INCLUDE:
                                handleInclude(uniformPath, token, result, inclusionLimit, seenPaths);
                                break;
                        case PREPROCESSOR_DIRECTIVE:
                                if (isIfDirective(token)) {
                                        processIfDirective(tokens, i, ignoredRegions);
                                } else {
                                        handleMacroPreprocessorDirective(token, result);
                                }
                                break;
                        case CONCATENATION:
                                if (i <= 0 || i >= tokens.size() - 1) {
                                        result.add(token);
                                        break;
                                }
                                IToken left = tokens.get(i - 1);
                                IToken right = tokens.get(i + 1);
                                tokens.set(i - 1, left.newToken(ETokenType.IDENTIFIER, left.getOffset(), left.getLineNumber(),
                                                left.getText() + right.getText(), MACRO_ORIGIN));
                                if (CollectionUtils.getLast(result).equals(left)) {
                                        result.remove(result.size() - 1);
                                }
                                tokens.remove(i); // remove the CONCATENATION token
                                tokens.remove(i); // remove right
                                i -= 2; // restart at new token
                                break;
                        case IDENTIFIER:
                                if (macroProvider.isDefined(token.getText())) {
                                        i = expandMacro(tokens, i, result);
                                        break;
                                }
                                // fall-through in else-case intended
                        default:
                                result.add(token);
                        }
                }
                return result;
        }

        /**
         * Skips tokens belonging to a pragma directive
         */
        private static int handlePragmaDirective(List<IToken> tokens, int i) {
                CCSMAssert.isTrue(
                                MacroHandlingCPreprocessorBase.PRAGMA_DIRECTIVE_START_PATTERN.matcher(tokens.get(i).getText()).find(),
                                "This method handles only pragma directives.");
                if (tokens.get(i).getType() == ETokenType.PREPROCESSOR_DIRECTIVE) {
                        // simply ignore this token (pragma arguments are included in the token)
                        return i;
                }
                // this is a "_pragma (...)" pragma (or starting with __)
                if (tokens.size() > i + 1 && tokens.get(i + 1).getType() == ETokenType.LPAREN) {
                        int closingIndex = TokenStreamUtils.findFirstTopLevel(tokens, i + 2, EnumSet.of(ETokenType.RPAREN),
                                        Collections.singletonList(ETokenType.LPAREN), Collections.singletonList(ETokenType.RPAREN));
                        if (closingIndex != TokenStreamUtils.NOT_FOUND) {
                                return closingIndex;
                        }
                }
                // simply ignore this token (_pragma without arguments)
                return i;
        }

        /**
         * Expands the macro at the given position in the token stream. Appends the
         * results to the given result list and returns the index to continue at.
         */
        private int expandMacro(List<IToken> tokens, int index, List<IToken> result) {
                List<IToken> expanded = new ArrayList<>();
                int tokensConsumed = expandMacro(tokens, index, expanded, EXPANSION_LIMIT, new HashSet<String>());

                // skip pragma directives in expanded macro
                List<IToken> expandedFiltered = new ArrayList<>();
                for (int i = 0; i < expanded.size(); i++) {
                        if (isPragmaDirective(expanded.get(i))) {
                                i = handlePragmaDirective(expanded, i);
                        } else {
                                expandedFiltered.add(expanded.get(i));
                        }
                }

                // in some cases we need a full rescan of the generated tokens
                if (containsFurtherMacros(expandedFiltered, tokens.subList(index, index + 1 + tokensConsumed))
                                || TokenStreamUtils.containsAny(expandedFiltered, ETokenType.CONCATENATION)) {
                        index = mergeExpansionIntoTokens(tokens, index, expandedFiltered, tokensConsumed);
                } else {
                        result.addAll(expandedFiltered);
                        index += tokensConsumed;
                }
                return index;
        }

        /**
         * Merges the expanded tokens back into the tokens. The size of the tokens list
         * will be preserved, but parts before <code>index</code> might be replaced with
         * null.
         *
         * @return one before the index to continue scanning from.
         */
        protected static int mergeExpansionIntoTokens(List<IToken> tokens, int index, List<IToken> expanded,
                        int tokensConsumed) {
                expanded.addAll(tokens.subList(index + tokensConsumed + 1, tokens.size()));
                int padding = Math.max(0, tokens.size() - expanded.size());
                tokens.clear();
                tokens.addAll(Collections.nCopies(padding, null));
                tokens.addAll(expanded);
                return padding - 1;
        }

        /**
         * Returns whether the given list of tokens contains any potential macros that
         * need expansion and that have not been before in the list of known tokens.
         */
        private boolean containsFurtherMacros(List<IToken> tokens, List<IToken> knownTokens) {
                Set<String> knownIdentifiers = new HashSet<>(CollectionUtils.filterAndMap(knownTokens,
                                token -> token.getType() == ETokenType.IDENTIFIER, IToken::getText));

                return tokens.stream().anyMatch(token -> token.getType() == ETokenType.IDENTIFIER
                                && !knownIdentifiers.contains(token.getText()) && macroProvider.isDefined(token.getText()));
        }

        /** Returns whether the given token is an if/ifdef/ifndef directive. */
        protected static boolean isIfDirective(IToken token) {
                return IF_DIRECTIVE_START_PATTERN.matcher(token.getText()).find();
        }

        /** Returns whether the given token is the start of a pragma directive. */
        protected static boolean isPragmaDirective(IToken token) {
                return PRAGMA_DIRECTIVE_START_PATTERN.matcher(token.getText()).find();
        }

        /**
         * Handles the include directive.
         *
         * @param uniformPath
         *            the uniform path of the file with the include.
         */
        protected abstract void handleInclude(String uniformPath, IToken token, List<IToken> result, int inclusionLimit,
                        Set<String> seenPaths);

        /**
         * Processes an if/ifdef/ifndef directive. This only updates ignored regions, to
         * exclude parts of the tokens.
         *
         * @param tokens
         *            the tokens being processed.
         * @param ifIndex
         *            the index in the tokens list, where the if directive is found.
         * @param ignoredRegions
         *            the regions of indexes to be ignored during parsing.
         */
        protected abstract void processIfDirective(List<IToken> tokens, int ifIndex, RegionSet ignoredRegions);

        /** Handles any preprocessor directives affecting macro definitions. */
        private void handleMacroPreprocessorDirective(IToken token, List<IToken> result) {
                // strip leading '#'
                String content = token.getText().trim().substring(1);

                List<IToken> subTokens = parseMacroContent(content);
                if (subTokens.isEmpty()) {
                        return;
                }

                switch (subTokens.get(0).getText()) {
                case "define":
                        if (subTokens.size() > 1) {
                                macroProvider.define(subTokens.get(1).getText(),
                                                StringUtils.stripPrefix(content.trim(), "define").trim());
                        }
                        break;
                case "undef":
                        if (subTokens.size() > 1) {
                                macroProvider.undefine(subTokens.get(1).getText());
                        }
                        break;
                default:
                        // ignore other/unknown directives
                        result.add(token);
                }
        }

        /** Parses a macor's content. */
        protected static List<IToken> parseMacroContent(String content) {
                return MACRO_TOKEN_CACHE.obtain(new ObtainMacroTokensKey(content));
        }

        /**
         * Expands the macro at the given start position in the token stream.
         *
         * @param tokens
         *            the input token stream where the macros was found.
         * @param macroIndex
         *            the index in the token stream where the macro was found.
         * @param result
         *            the list to append any new tokens to.
         * @param expansionLimit
         *            the maximal number of expansion performed
         * @param ignoreMacros
         *            macro names that will not be expanded (necessary to handle macro
         *            nesting correctly)
         * @return the additional number of tokens consumed (besides the macro name
         *         itself).
         */
        private int expandMacro(List<IToken> tokens, int macroIndex, List<IToken> result, int expansionLimit,
                        HashSet<String> ignoreMacros) {
                IToken macroNameToken = tokens.get(macroIndex);
                String name = macroNameToken.getText();
                String definition = macroProvider.getDefinition(name);
                if (expansionLimit <= 0) {
                        result.clear();
                        return 0;
                }
                if (definition == null || ignoreMacros.contains(name) || ignoredTokens.contains(macroNameToken)) {
                        result.add(macroNameToken);
                        ignoredTokens.add(macroNameToken);
                        return 0;
                }
                expansionLimit -= 1;

                List<IToken> definitionTokens = parseMacroContent(definition);
                int indexOfFirstExpandedToken = result.size();
                if (isFunctionMacro(definitionTokens)) {
                        if (tokens.size() <= macroIndex + 1 || tokens.get(macroIndex + 1).getType() != ETokenType.LPAREN) {
                                result.add(macroNameToken);
                                return 0;
                        }

                        Map<String, Integer> parameterNameToPosition = determineParameterNames(definitionTokens);
                        List<List<IToken>> actualArguments = extractActualArguments(tokens, macroIndex);
                        List<IToken> macroContent = definitionTokens
                                        .subList(1 + determineParameterTokenCount(parameterNameToPosition), definitionTokens.size());
                        expandMacroContent(name, macroContent, parameterNameToPosition, actualArguments, result, expansionLimit,
                                        ignoreMacros);
                        correctExpandedTokenOffsetsAndLines(macroNameToken, result, indexOfFirstExpandedToken);
                        return determineArgumentTokenCount(actualArguments);
                }
                expandMacroContent(name, definitionTokens.subList(1, definitionTokens.size()),
                                CollectionUtils.<String, Integer>emptyMap(), CollectionUtils.<List<IToken>>emptyList(), result,
                                expansionLimit, ignoreMacros);
                correctExpandedTokenOffsetsAndLines(macroNameToken, result, indexOfFirstExpandedToken);
                return 0;
        }

        /**
         * Corrects the offsets and names of tokens introduced during macro expansion.
         * These tokens get the offset/line of the macro-name token (the first token
         * that is replaced during expansion). This is necessary to generate a token
         * list with increasing (not strictly increasing) offsets/line numbers.
         *
         * This method assumes that all tokens from the given offset to the end of the
         * <code>result</code> list are macro-expansion tokens. All of these tokens will
         * be corrected/replaced.
         *
         * We also replace macro-parameter tokens (even though they come from the
         * non-expanded token list) since they can occur multiple times in the expansion
         * (<code>macro(X)</code> can be expanded to <code> foo(X,X);</code>).
         */
        private void correctExpandedTokenOffsetsAndLines(IToken macroNameToken, List<IToken> result,
                        int indexOfFirstExpandedToken) {
                for (int i = indexOfFirstExpandedToken; i < result.size(); i++) {
                        IToken currentToken = result.get(i);
                        IToken macroTokenReplacement = currentToken.newToken(currentToken.getType(), macroNameToken.getOffset(),
                                        macroNameToken.getLineNumber(), currentToken.getText(), MACRO_ORIGIN);
                        if (ignoredTokens.contains(currentToken)) {
                                // since we replace the token in the result list, we also need to replace it in
                                // the ignoredTokens list. This will not work if the token is inserted multiple
                                // times in the same expansion.
                                ignoredTokens.remove(currentToken);
                                ignoredTokens.add(macroTokenReplacement);
                        }
                        result.set(i, macroTokenReplacement);
                }
        }

        /** Returns the number of tokens used to represent the given arguments. */
        private static int determineParameterTokenCount(Map<String, Integer> parameterNameToPosition) {
                if (parameterNameToPosition.isEmpty()) {
                        return 2;
                }
                int result = 1 + 2 * parameterNameToPosition.size();
                for (Entry<String, Integer> entry : parameterNameToPosition.entrySet()) {
                        if (entry.getValue() < 0 && !DEFAULT_VAR_ARGS_NAME.equals(entry.getKey())) {
                                result += 1;
                        }
                }
                return result;
        }

        /**
         * Returns a mapping from parameter name to parameter index. A var args
         * parameter will be encoded using a negative index (decremented by 1 to make it
         * distinguishable from 0).
         */
        private static Map<String, Integer> determineParameterNames(List<IToken> definitionTokens) {
                Map<String, Integer> argumentNameToPosition = new HashMap<>();
                for (int i = 2; i < definitionTokens.size(); i += 2) {
                        if (definitionTokens.get(i - 1).getType() == ETokenType.RPAREN) {
                                break;
                        }
                        if (definitionTokens.get(i).getType() == ETokenType.IDENTIFIER) {
                                argumentNameToPosition.put(definitionTokens.get(i).getText(), i / 2 - 1);
                                if (i + 1 < definitionTokens.size() && definitionTokens.get(i + 1).getType() == ETokenType.ELLIPSIS) {
                                        argumentNameToPosition.put(definitionTokens.get(i).getText(), -(i / 2 - 1) - 1);
                                        break;
                                }
                        } else if (definitionTokens.get(i).getType() == ETokenType.ELLIPSIS) {
                                argumentNameToPosition.put(DEFAULT_VAR_ARGS_NAME, -(i / 2 - 1) - 1);
                        } else {
                                break;
                        }
                }
                return argumentNameToPosition;
        }

        /**
         * Returns the number of tokens that are used to describe the given macro
         * arguments.
         */
        private static int determineArgumentTokenCount(List<List<IToken>> actualArguments) {
                int additionalTokens = 1 + actualArguments.size();
                for (List<IToken> argument : actualArguments) {
                        additionalTokens += argument.size();
                }
                return additionalTokens;
        }

        /** Extracts the actual arguments to a macro. */
        private static List<List<IToken>> extractActualArguments(List<IToken> tokens, int macroIndex) {
                List<List<IToken>> actualArguments = new ArrayList<>();
                List<IToken> currentArgument = new ArrayList<>();
                int nesting = 0;
                for (int i = macroIndex + 2; i < tokens.size(); ++i) {
                        switch (tokens.get(i).getType()) {
                        case LPAREN:
                                nesting += 1;
                                currentArgument.add(tokens.get(i));
                                break;
                        case RPAREN:
                                if (nesting == 0) {
                                        actualArguments.add(currentArgument);
                                        return actualArguments;
                                }

                                nesting -= 1;
                                currentArgument.add(tokens.get(i));
                                break;
                        case COMMA:
                                if (nesting > 0) {
                                        currentArgument.add(tokens.get(i));
                                } else {
                                        actualArguments.add(currentArgument);
                                        currentArgument = new ArrayList<>();
                                }
                                break;
                        default:
                                currentArgument.add(tokens.get(i));
                        }
                }
                return actualArguments;
        }

        /**
         * Returns whether the macro defined by the given tokens is a function macro.
         * This is the case if the second token is a parenthesis and follows
         * <b>without</b> any whitespace to the macro's name.
         */
        private static boolean isFunctionMacro(List<IToken> definitionTokens) {
                if (definitionTokens.size() < 2) {
                        return false;
                }

                IToken nameToken = definitionTokens.get(0);
                IToken secondToken = definitionTokens.get(1);

                return secondToken.getType() == ETokenType.LPAREN && nameToken.getEndOffset() + 1 == secondToken.getOffset();
        }

        /**
         * Expands a macro's content. This applies recursive macro expansion to both the
         * arguments and the completed expansion (also see
         * https://gcc.gnu.org/onlinedocs/cpp/Argument-Prescan.html for an explanation
         * of this).
         */
        private void expandMacroContent(String currentMacroName, List<IToken> macroContent,
                        Map<String, Integer> parameterNameToPosition, List<List<IToken>> actualArguments, List<IToken> result,
                        int expansionLimit, HashSet<String> ignoreMacros) {
                List<IToken> expansion = new ArrayList<>();

                for (int i = 0; i < macroContent.size(); ++i) {
                        IToken token = macroContent.get(i);
                        if (i + 2 < macroContent.size() && macroContent.get(i + 1).getType() == ETokenType.CONCATENATION) {
                                List<IToken> argument1 = getParameterValue(macroContent, parameterNameToPosition, actualArguments, i);
                                List<IToken> argument2 = getParameterValue(macroContent, parameterNameToPosition, actualArguments,
                                                i + 2);
                                appendMerged(argument1, argument2, expansion);
                                i += 2;
                        } else if (token.getType() == ETokenType.HASH && i + 1 < macroContent.size()) {
                                i += 1;
                                String text = toStringLiteral(
                                                getParameterValue(macroContent, parameterNameToPosition, actualArguments, i));
                                expansion.add(TokenStreamUtils.createToken(token, text, ETokenType.STRING_LITERAL));
                        } else if (token.getType() == ETokenType.IDENTIFIER
                                        && parameterNameToPosition.containsKey(token.getText())) {
                                expansion.addAll(
                                                expandParameter(token, parameterNameToPosition, actualArguments, ignoreMacros, expansionLimit));
                        } else {
                                expansion.add(token);
                        }
                }
                List<IToken> expanded = new ArrayList<>();
                ignoreMacros.add(currentMacroName);
                appendWithMacroExpansion(expansion, expansionLimit, ignoreMacros, expanded);
                ignoreMacros.remove(currentMacroName);
                result.addAll(expanded);
        }

        private static List<IToken> getParameterValue(List<IToken> macroContent,
                        Map<String, Integer> parameterNameToPosition, List<List<IToken>> actualArguments, int i) {
                String parameterName = macroContent.get(i).getText();
                if (parameterNameToPosition.containsKey(parameterName)) {
                        int parameterPosition = parameterNameToPosition.get(parameterName);
                        if (parameterPosition < 0) {
                                return extractVarArgs(actualArguments, parameterPosition);
                        }
                        return actualArguments.get(parameterPosition);
                }
                return Collections.singletonList(macroContent.get(i));
        }

        /**
         * Appends both token lists to the result list but merges the joining tokens.
         */
        private static void appendMerged(List<IToken> argument1, List<IToken> argument2, List<IToken> result) {
                if (argument1.isEmpty() || argument2.isEmpty()) {
                        result.addAll(argument1);
                        result.addAll(argument2);
                        return;
                }

                result.addAll(argument1.subList(0, argument1.size() - 1));

                IToken merge1 = CollectionUtils.getLast(argument1);
                IToken merge2 = argument2.get(0);
                result.addAll(parseMacroContent(merge1.getText() + merge2.getText()));

                result.addAll(argument2.subList(1, argument2.size()));
        }

        /**
         * Returns the expanded parameter. Returns the parameter name token itself, if
         * the name is not a valid parameter name.
         */
        private List<IToken> expandParameter(IToken parameterNameToken, Map<String, Integer> parameterNameToPosition,
                        List<List<IToken>> actualArguments, HashSet<String> ignoreMacros, int expansionLimit) {
                Integer index = parameterNameToPosition.get(parameterNameToken.getText());
                if (index == null) {
                        return Collections.singletonList(parameterNameToken);
                }
                if (index >= actualArguments.size()) {
                        return CollectionUtils.emptyList();
                }

                // handle var args
                if (index < 0) {
                        List<IToken> result = extractVarArgs(actualArguments, index);
                        List<IToken> expandedResult = new ArrayList<>();
                        appendWithRepeatedMacroExpansion(result, expansionLimit, ignoreMacros, expandedResult);
                        return expandedResult;
                }
                List<IToken> expandedResult = new ArrayList<>();
                appendWithRepeatedMacroExpansion(actualArguments.get(index), expansionLimit, ignoreMacros, expandedResult);
                return expandedResult;
        }

        /**
         * Extracts the var args from the given list of actual arguments. Var args are
         * specified by "..." in the list of formal arguments and used with __VA_ARGS__
         * in the macro replacement.
         *
         * @param varargsStart
         *            negated number (1-based) of the first varargs argument. E.g., in
         *            <code>#define FOO(a,b, ...)
         *                  FOO(1,2,3,4,5)</code>, varargsStart would be -3
         */
        @Nonnull
        private static List<IToken> extractVarArgs(List<List<IToken>> actualArguments, Integer varargsStart) {
                List<IToken> result = new ArrayList<>();
                for (int i = -(varargsStart + 1); i < actualArguments.size(); ++i) {
                        if (!result.isEmpty()) {
                                IToken last = CollectionUtils.getLast(result);
                                result.add(last.newToken(ETokenType.COMMA, last.getEndOffset(), last.getLineNumber(), ",",
                                                last.getOriginId()));
                        }
                        result.addAll(actualArguments.get(i));
                }
                return result;
        }

        /** Converts tokens to a string literal. */
        private static String toStringLiteral(List<IToken> tokens) {
                StringBuilder builder = new StringBuilder("\"");
                IToken previous = null;
                for (IToken token : tokens) {
                        if (previous != null) {
                                int count = token.getOffset() - previous.getEndOffset() - 1;
                                for (int i = 0; i < count; ++i) {
                                        builder.append(StringUtils.SPACE);
                                }
                        }

                        builder.append(token.getText());
                        previous = token;
                }
                builder.append("\"");
                return builder.toString();
        }

        /**
         * Appends the given input tokens to the result, applying macro expansion along
         * the way.
         */
        private void appendWithMacroExpansion(List<IToken> input, int expansionLimit, HashSet<String> ignoreMacros,
                        List<IToken> result) {
                for (int i = 0; i < input.size(); ++i) {
                        IToken token = input.get(i);
                        if (token.getType() == ETokenType.IDENTIFIER && macroProvider.isDefined(token.getText())) {
                                i += expandMacro(input, i, result, expansionLimit, ignoreMacros);
                        } else {
                                result.add(token);
                        }
                }
        }

        /**
         * Appends the given input tokens to the result, applying macro expansion as
         * often as possible (within the expansion limit).
         */
        private void appendWithRepeatedMacroExpansion(List<IToken> input, int expansionLimit, HashSet<String> ignoreMacros,
                        List<IToken> result) {
                Comparator<List<IToken>> tokenListComparator = CollectionUtils
                                .getListComparator(Comparator.comparing(IToken::getText));
                List<IToken> previousExpanded = new ArrayList<>();
                List<IToken> expanded = new ArrayList<>();

                appendWithMacroExpansion(input, expansionLimit, ignoreMacros, expanded);
                while (tokenListComparator.compare(previousExpanded, expanded) != 0) {
                        if (expanded.size() > input.size() * 100) {
                                // abort if expanded tokens gets much larger than initial tokens (explosion)
                                LogManager.getLogger()
                                                .warn("Preprocessing generated too many tokens in rescanning step of expanded tokens in file "
                                                                + uniformPath + " Ignoring partial expansion.");
                                result = input;
                                return;
                        }
                        previousExpanded = expanded;
                        expanded = new ArrayList<>();
                        appendWithMacroExpansion(previousExpanded, expansionLimit, ignoreMacros, expanded);
                }
                result.addAll(expanded);
        }
}