///////////////////////////////////////////////////////////////////////////////////////////////
// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
// Copyright (C) 2001-2023 the original author or authors.
//
// 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
///////////////////////////////////////////////////////////////////////////////////////////////

package com.puppycrawl.tools.checkstyle;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.stream.Collectors;

import org.antlr.v4.runtime.BufferedTokenStream;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.ParserRuleContext;
import org.antlr.v4.runtime.Token;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.tree.TerminalNode;

import com.puppycrawl.tools.checkstyle.api.TokenTypes;
import com.puppycrawl.tools.checkstyle.grammar.java.JavaLanguageLexer;
import com.puppycrawl.tools.checkstyle.grammar.java.JavaLanguageParser;
import com.puppycrawl.tools.checkstyle.grammar.java.JavaLanguageParserBaseVisitor;
import com.puppycrawl.tools.checkstyle.utils.TokenUtil;

/**
 * Visitor class used to build Checkstyle's Java AST from the parse tree produced by
 * {@link JavaLanguageParser}. In each {@code visit...} method, we visit the children of a node
 * (which correspond to subrules) or create terminal nodes (tokens), and return a subtree as a
 * result.
 *
 * <p>Example:</p>
 *
 * <p>The following package declaration:</p>
 * <pre>
 * package com.puppycrawl.tools.checkstyle;
 * </pre>
 *
 * <p>
 * Will be parsed by the {@code packageDeclaration} rule from {@code JavaLanguageParser.g4}:
 * </p>
 * <pre>
 * packageDeclaration
 *     : annotations[true] LITERAL_PACKAGE qualifiedName SEMI
 *     ;
 * </pre>
 *
 * <p>
 * We override the {@code visitPackageDeclaration} method generated by ANTLR in
 * {@link JavaLanguageParser} at
 * {@link JavaAstVisitor#visitPackageDeclaration(JavaLanguageParser.PackageDeclarationContext)}
 * to create a subtree based on the subrules and tokens found in the {@code packageDeclaration}
 * subrule accordingly, thus producing the following AST:
 * </p>
 * <pre>
 * PACKAGE_DEF -&gt; package
 * |--ANNOTATIONS -&gt; ANNOTATIONS
 * |--DOT -&gt; .
 * |   |--DOT -&gt; .
 * |   |   |--DOT -&gt; .
 * |   |   |   |--IDENT -&gt; com
 * |   |   |   `--IDENT -&gt; puppycrawl
 * |   |   `--IDENT -&gt; tools
 * |   `--IDENT -&gt; checkstyle
 * `--SEMI -&gt; ;
 * </pre>
 * <p>
 * See <a href="https://github.com/checkstyle/checkstyle/pull/10434">#10434</a>
 * for a good example of how
 * to make changes to Checkstyle's grammar and AST.
 * </p>
 * <p>
 * The order of {@code visit...} methods in {@code JavaAstVisitor.java} and production rules in
 * {@code JavaLanguageParser.g4} should be consistent to ease maintenance.
 * </p>
 */
public final class JavaAstVisitor extends JavaLanguageParserBaseVisitor<DetailAstImpl> {

    /** String representation of the left shift operator. */
    private static final String LEFT_SHIFT = "<<";

    /** String representation of the unsigned right shift operator. */
    private static final String UNSIGNED_RIGHT_SHIFT = ">>>";

    /** String representation of the right shift operator. */
    private static final String RIGHT_SHIFT = ">>";

    /**
     * The tokens here are technically expressions, but should
     * not return an EXPR token as their root.
     */
    private static final int[] EXPRESSIONS_WITH_NO_EXPR_ROOT = {
        TokenTypes.CTOR_CALL,
        TokenTypes.SUPER_CTOR_CALL,
        TokenTypes.LAMBDA,
    };

    /** Token stream to check for hidden tokens. */
    private final BufferedTokenStream tokens;

    /**
     * Constructs a JavaAstVisitor with given token stream.
     *
     * @param tokenStream the token stream to check for hidden tokens
     */
    public JavaAstVisitor(CommonTokenStream tokenStream) {
        tokens = tokenStream;
    }

    @Override
    public DetailAstImpl visitCompilationUnit(JavaLanguageParser.CompilationUnitContext ctx) {
        final DetailAstImpl compilationUnit;
        // 'EOF' token is always present; therefore if we only have one child, we have an empty file
        final boolean isEmptyFile = ctx.children.size() == 1;
        if (isEmptyFile) {
            compilationUnit = null;
        }
        else {
            compilationUnit = createImaginary(TokenTypes.COMPILATION_UNIT);
            // last child is 'EOF', we do not include this token in AST
            processChildren(compilationUnit, ctx.children.subList(0, ctx.children.size() - 1));
        }
        return compilationUnit;
    }

    @Override
    public DetailAstImpl visitPackageDeclaration(
            JavaLanguageParser.PackageDeclarationContext ctx) {
        final DetailAstImpl packageDeclaration =
                create(TokenTypes.PACKAGE_DEF, (Token) ctx.LITERAL_PACKAGE().getPayload());
        packageDeclaration.addChild(visit(ctx.annotations()));
        packageDeclaration.addChild(visit(ctx.qualifiedName()));
        packageDeclaration.addChild(create(ctx.SEMI()));
        return packageDeclaration;
    }

    @Override
    public DetailAstImpl visitImportDec(JavaLanguageParser.ImportDecContext ctx) {
        final DetailAstImpl importRoot = create(ctx.start);

        // Static import
        final TerminalNode literalStaticNode = ctx.LITERAL_STATIC();
        if (literalStaticNode != null) {
            importRoot.setType(TokenTypes.STATIC_IMPORT);
            importRoot.addChild(create(literalStaticNode));
        }

        // Handle star imports
        final boolean isStarImport = ctx.STAR() != null;
        if (isStarImport) {
            final DetailAstImpl dot = create(ctx.DOT());
            dot.addChild(visit(ctx.qualifiedName()));
            dot.addChild(create(ctx.STAR()));
            importRoot.addChild(dot);
        }
        else {
            importRoot.addChild(visit(ctx.qualifiedName()));
        }

        importRoot.addChild(create(ctx.SEMI()));
        return importRoot;
    }

    @Override
    public DetailAstImpl visitSingleSemiImport(JavaLanguageParser.SingleSemiImportContext ctx) {
        return create(ctx.SEMI());
    }

    @Override
    public DetailAstImpl visitTypeDeclaration(JavaLanguageParser.TypeDeclarationContext ctx) {
        final DetailAstImpl typeDeclaration;
        if (ctx.type == null) {
            typeDeclaration = create(ctx.semi.get(0));
            ctx.semi.subList(1, ctx.semi.size())
                    .forEach(semi -> addLastSibling(typeDeclaration, create(semi)));
        }
        else {
            typeDeclaration = visit(ctx.type);
        }
        return typeDeclaration;
    }

    @Override
    public DetailAstImpl visitModifier(JavaLanguageParser.ModifierContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitVariableModifier(JavaLanguageParser.VariableModifierContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitClassDeclaration(JavaLanguageParser.ClassDeclarationContext ctx) {
        return createTypeDeclaration(ctx, TokenTypes.CLASS_DEF, ctx.mods);
    }

    @Override
    public DetailAstImpl visitRecordDeclaration(JavaLanguageParser.RecordDeclarationContext ctx) {
        return createTypeDeclaration(ctx, TokenTypes.RECORD_DEF, ctx.mods);
    }

    @Override
    public DetailAstImpl visitRecordComponentsList(
            JavaLanguageParser.RecordComponentsListContext ctx) {
        final DetailAstImpl lparen = create(ctx.LPAREN());

        // We make a "RECORD_COMPONENTS" node whether components exist or not
        if (ctx.recordComponents() == null) {
            addLastSibling(lparen, createImaginary(TokenTypes.RECORD_COMPONENTS));
        }
        else {
            addLastSibling(lparen, visit(ctx.recordComponents()));
        }
        addLastSibling(lparen, create(ctx.RPAREN()));
        return lparen;
    }

    @Override
    public DetailAstImpl visitRecordComponents(JavaLanguageParser.RecordComponentsContext ctx) {
        final DetailAstImpl recordComponents = createImaginary(TokenTypes.RECORD_COMPONENTS);
        processChildren(recordComponents, ctx.children);
        return recordComponents;
    }

    @Override
    public DetailAstImpl visitRecordComponent(JavaLanguageParser.RecordComponentContext ctx) {
        final DetailAstImpl recordComponent = createImaginary(TokenTypes.RECORD_COMPONENT_DEF);
        processChildren(recordComponent, ctx.children);
        return recordComponent;
    }

    @Override
    public DetailAstImpl visitLastRecordComponent(
            JavaLanguageParser.LastRecordComponentContext ctx) {
        final DetailAstImpl recordComponent = createImaginary(TokenTypes.RECORD_COMPONENT_DEF);
        processChildren(recordComponent, ctx.children);
        return recordComponent;
    }

    @Override
    public DetailAstImpl visitRecordBody(JavaLanguageParser.RecordBodyContext ctx) {
        final DetailAstImpl objBlock = createImaginary(TokenTypes.OBJBLOCK);
        processChildren(objBlock, ctx.children);
        return objBlock;
    }

    @Override
    public DetailAstImpl visitCompactConstructorDeclaration(
            JavaLanguageParser.CompactConstructorDeclarationContext ctx) {
        final DetailAstImpl compactConstructor = createImaginary(TokenTypes.COMPACT_CTOR_DEF);
        compactConstructor.addChild(createModifiers(ctx.mods));
        compactConstructor.addChild(visit(ctx.id()));
        compactConstructor.addChild(visit(ctx.constructorBlock()));
        return compactConstructor;
    }

    @Override
    public DetailAstImpl visitClassExtends(JavaLanguageParser.ClassExtendsContext ctx) {
        final DetailAstImpl classExtends = create(ctx.EXTENDS_CLAUSE());
        classExtends.addChild(visit(ctx.type));
        return classExtends;
    }

    @Override
    public DetailAstImpl visitImplementsClause(JavaLanguageParser.ImplementsClauseContext ctx) {
        final DetailAstImpl classImplements = create(TokenTypes.IMPLEMENTS_CLAUSE,
                (Token) ctx.LITERAL_IMPLEMENTS().getPayload());
        classImplements.addChild(visit(ctx.typeList()));
        return classImplements;
    }

    @Override
    public DetailAstImpl visitTypeParameters(JavaLanguageParser.TypeParametersContext ctx) {
        final DetailAstImpl typeParameters = createImaginary(TokenTypes.TYPE_PARAMETERS);
        typeParameters.addChild(create(TokenTypes.GENERIC_START, (Token) ctx.LT().getPayload()));
        // Exclude '<' and '>'
        processChildren(typeParameters, ctx.children.subList(1, ctx.children.size() - 1));
        typeParameters.addChild(create(TokenTypes.GENERIC_END, (Token) ctx.GT().getPayload()));
        return typeParameters;
    }

    @Override
    public DetailAstImpl visitTypeParameter(JavaLanguageParser.TypeParameterContext ctx) {
        final DetailAstImpl typeParameter = createImaginary(TokenTypes.TYPE_PARAMETER);
        processChildren(typeParameter, ctx.children);
        return typeParameter;
    }

    @Override
    public DetailAstImpl visitTypeUpperBounds(JavaLanguageParser.TypeUpperBoundsContext ctx) {
        // In this case, we call 'extends` TYPE_UPPER_BOUNDS
        final DetailAstImpl typeUpperBounds = create(TokenTypes.TYPE_UPPER_BOUNDS,
                (Token) ctx.EXTENDS_CLAUSE().getPayload());
        // 'extends' is child[0]
        processChildren(typeUpperBounds, ctx.children.subList(1, ctx.children.size()));
        return typeUpperBounds;
    }

    @Override
    public DetailAstImpl visitTypeBound(JavaLanguageParser.TypeBoundContext ctx) {
        final DetailAstImpl typeBoundType = visit(ctx.typeBoundType(0));
        final Iterator<JavaLanguageParser.TypeBoundTypeContext> typeBoundTypeIterator =
                ctx.typeBoundType().listIterator(1);
        ctx.BAND().forEach(band -> {
            addLastSibling(typeBoundType, create(TokenTypes.TYPE_EXTENSION_AND,
                                (Token) band.getPayload()));
            addLastSibling(typeBoundType, visit(typeBoundTypeIterator.next()));
        });
        return typeBoundType;
    }

    @Override
    public DetailAstImpl visitTypeBoundType(JavaLanguageParser.TypeBoundTypeContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitEnumDeclaration(JavaLanguageParser.EnumDeclarationContext ctx) {
        return createTypeDeclaration(ctx, TokenTypes.ENUM_DEF, ctx.mods);
    }

    @Override
    public DetailAstImpl visitEnumBody(JavaLanguageParser.EnumBodyContext ctx) {
        final DetailAstImpl objBlock = createImaginary(TokenTypes.OBJBLOCK);
        processChildren(objBlock, ctx.children);
        return objBlock;
    }

    @Override
    public DetailAstImpl visitEnumConstants(JavaLanguageParser.EnumConstantsContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitEnumConstant(JavaLanguageParser.EnumConstantContext ctx) {
        final DetailAstImpl enumConstant =
                createImaginary(TokenTypes.ENUM_CONSTANT_DEF);
        processChildren(enumConstant, ctx.children);
        return enumConstant;
    }

    @Override
    public DetailAstImpl visitEnumBodyDeclarations(
            JavaLanguageParser.EnumBodyDeclarationsContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitInterfaceDeclaration(
            JavaLanguageParser.InterfaceDeclarationContext ctx) {
        return createTypeDeclaration(ctx, TokenTypes.INTERFACE_DEF, ctx.mods);
    }

    @Override
    public DetailAstImpl visitInterfaceExtends(JavaLanguageParser.InterfaceExtendsContext ctx) {
        final DetailAstImpl interfaceExtends = create(ctx.EXTENDS_CLAUSE());
        interfaceExtends.addChild(visit(ctx.typeList()));
        return interfaceExtends;
    }

    @Override
    public DetailAstImpl visitClassBody(JavaLanguageParser.ClassBodyContext ctx) {
        final DetailAstImpl objBlock = createImaginary(TokenTypes.OBJBLOCK);
        processChildren(objBlock, ctx.children);
        return objBlock;
    }

    @Override
    public DetailAstImpl visitInterfaceBody(JavaLanguageParser.InterfaceBodyContext ctx) {
        final DetailAstImpl objBlock = createImaginary(TokenTypes.OBJBLOCK);
        processChildren(objBlock, ctx.children);
        return objBlock;
    }

    @Override
    public DetailAstImpl visitEmptyClass(JavaLanguageParser.EmptyClassContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitClassBlock(JavaLanguageParser.ClassBlockContext ctx) {
        final DetailAstImpl classBlock;
        if (ctx.LITERAL_STATIC() == null) {
            // We call it an INSTANCE_INIT
            classBlock = createImaginary(TokenTypes.INSTANCE_INIT);
        }
        else {
            classBlock = create(TokenTypes.STATIC_INIT, (Token) ctx.LITERAL_STATIC().getPayload());
            classBlock.setText(TokenUtil.getTokenName(TokenTypes.STATIC_INIT));
        }
        classBlock.addChild(visit(ctx.block()));
        return classBlock;
    }

    @Override
    public DetailAstImpl visitMethodDeclaration(JavaLanguageParser.MethodDeclarationContext ctx) {
        final DetailAstImpl methodDef = createImaginary(TokenTypes.METHOD_DEF);
        methodDef.addChild(createModifiers(ctx.mods));

        // Process all children except C style array declarators
        processChildren(methodDef, ctx.children.stream()
                .filter(child -> !(child instanceof JavaLanguageParser.ArrayDeclaratorContext))
                .collect(Collectors.toList()));

        // We add C style array declarator brackets to TYPE ast
        final DetailAstImpl typeAst = (DetailAstImpl) methodDef.findFirstToken(TokenTypes.TYPE);
        ctx.cStyleArrDec.forEach(child -> typeAst.addChild(visit(child)));

        return methodDef;
    }

    @Override
    public DetailAstImpl visitMethodBody(JavaLanguageParser.MethodBodyContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitThrowsList(JavaLanguageParser.ThrowsListContext ctx) {
        final DetailAstImpl throwsRoot = create(ctx.LITERAL_THROWS());
        throwsRoot.addChild(visit(ctx.qualifiedNameList()));
        return throwsRoot;
    }

    @Override
    public DetailAstImpl visitConstructorDeclaration(
            JavaLanguageParser.ConstructorDeclarationContext ctx) {
        final DetailAstImpl constructorDeclaration = createImaginary(TokenTypes.CTOR_DEF);
        constructorDeclaration.addChild(createModifiers(ctx.mods));
        processChildren(constructorDeclaration, ctx.children);
        return constructorDeclaration;
    }

    @Override
    public DetailAstImpl visitFieldDeclaration(JavaLanguageParser.FieldDeclarationContext ctx) {
        final DetailAstImpl dummyNode = new DetailAstImpl();
        // Since the TYPE AST is built by visitVariableDeclarator(), we skip it here (child [0])
        // We also append the SEMI token to the first child [size() - 1],
        // until https://github.com/checkstyle/checkstyle/issues/3151
        processChildren(dummyNode, ctx.children.subList(1, ctx.children.size() - 1));
        dummyNode.getFirstChild().addChild(create(ctx.SEMI()));
        return dummyNode.getFirstChild();
    }

    @Override
    public DetailAstImpl visitInterfaceBodyDeclaration(
            JavaLanguageParser.InterfaceBodyDeclarationContext ctx) {
        final DetailAstImpl returnTree;
        if (ctx.SEMI() == null) {
            returnTree = visit(ctx.interfaceMemberDeclaration());
        }
        else {
            returnTree = create(ctx.SEMI());
        }
        return returnTree;
    }

    @Override
    public DetailAstImpl visitInterfaceMethodDeclaration(
            JavaLanguageParser.InterfaceMethodDeclarationContext ctx) {
        final DetailAstImpl methodDef = createImaginary(TokenTypes.METHOD_DEF);
        methodDef.addChild(createModifiers(ctx.mods));

        // Process all children except C style array declarators and modifiers
        final List<ParseTree> children = ctx.children
                .stream()
                .filter(child -> !(child instanceof JavaLanguageParser.ArrayDeclaratorContext))
                .collect(Collectors.toList());
        processChildren(methodDef, children);

        // We add C style array declarator brackets to TYPE ast
        final DetailAstImpl typeAst = (DetailAstImpl) methodDef.findFirstToken(TokenTypes.TYPE);
        ctx.cStyleArrDec.forEach(child -> typeAst.addChild(visit(child)));

        return methodDef;
    }

    @Override
    public DetailAstImpl visitVariableDeclarators(
            JavaLanguageParser.VariableDeclaratorsContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitVariableDeclarator(
            JavaLanguageParser.VariableDeclaratorContext ctx) {
        final DetailAstImpl variableDef = createImaginary(TokenTypes.VARIABLE_DEF);
        variableDef.addChild(createModifiers(ctx.mods));

        final DetailAstImpl type = visit(ctx.type);
        variableDef.addChild(type);
        variableDef.addChild(visit(ctx.id()));

        // Add C style array declarator brackets to TYPE ast
        ctx.arrayDeclarator().forEach(child -> type.addChild(visit(child)));

        // If this is an assignment statement, ASSIGN becomes the parent of EXPR
        final TerminalNode assignNode = ctx.ASSIGN();
        if (assignNode != null) {
            final DetailAstImpl assign = create(assignNode);
            variableDef.addChild(assign);
            assign.addChild(visit(ctx.variableInitializer()));
        }
        return variableDef;
    }

    @Override
    public DetailAstImpl visitVariableDeclaratorId(
            JavaLanguageParser.VariableDeclaratorIdContext ctx) {
        final DetailAstImpl root = new DetailAstImpl();
        root.addChild(createModifiers(ctx.mods));
        final DetailAstImpl type = visit(ctx.type);
        root.addChild(type);

        final DetailAstImpl declaratorId;
        if (ctx.LITERAL_THIS() == null) {
            declaratorId = visit(ctx.qualifiedName());
        }
        else if (ctx.DOT() == null) {
            declaratorId = create(ctx.LITERAL_THIS());
        }
        else {
            declaratorId = create(ctx.DOT());
            declaratorId.addChild(visit(ctx.qualifiedName()));
            declaratorId.addChild(create(ctx.LITERAL_THIS()));
        }

        root.addChild(declaratorId);
        ctx.arrayDeclarator().forEach(child -> type.addChild(visit(child)));

        return root.getFirstChild();
    }

    @Override
    public DetailAstImpl visitArrayInitializer(JavaLanguageParser.ArrayInitializerContext ctx) {
        final DetailAstImpl arrayInitializer = create(TokenTypes.ARRAY_INIT, ctx.start);
        // ARRAY_INIT was child[0]
        processChildren(arrayInitializer, ctx.children.subList(1, ctx.children.size()));
        return arrayInitializer;
    }

    @Override
    public DetailAstImpl visitClassOrInterfaceType(
            JavaLanguageParser.ClassOrInterfaceTypeContext ctx) {
        final DetailAstPair currentAST = new DetailAstPair();
        DetailAstPair.addAstChild(currentAST, visit(ctx.id()));
        DetailAstPair.addAstChild(currentAST, visit(ctx.typeArguments()));

        // This is how we build the annotations/ qualified name/ type parameters tree
        for (ParserRuleContext extendedContext : ctx.extended) {
            final DetailAstImpl dot = create(extendedContext.start);
            DetailAstPair.makeAstRoot(currentAST, dot);
            extendedContext.children
                .forEach(child -> DetailAstPair.addAstChild(currentAST, visit(child)));
        }

        // Create imaginary 'TYPE' parent if specified
        final DetailAstImpl returnTree;
        if (ctx.createImaginaryNode) {
            returnTree = createImaginary(TokenTypes.TYPE);
            returnTree.addChild(currentAST.root);
        }
        else {
            returnTree = currentAST.root;
        }
        return returnTree;
    }

    @Override
    public DetailAstImpl visitSimpleTypeArgument(
            JavaLanguageParser.SimpleTypeArgumentContext ctx) {
        final DetailAstImpl typeArgument =
                createImaginary(TokenTypes.TYPE_ARGUMENT);
        typeArgument.addChild(visit(ctx.typeType()));
        return typeArgument;
    }

    @Override
    public DetailAstImpl visitWildCardTypeArgument(
            JavaLanguageParser.WildCardTypeArgumentContext ctx) {
        final DetailAstImpl typeArgument = createImaginary(TokenTypes.TYPE_ARGUMENT);
        typeArgument.addChild(visit(ctx.annotations()));
        typeArgument.addChild(create(TokenTypes.WILDCARD_TYPE,
                (Token) ctx.QUESTION().getPayload()));

        if (ctx.upperBound != null) {
            final DetailAstImpl upperBound = create(TokenTypes.TYPE_UPPER_BOUNDS, ctx.upperBound);
            upperBound.addChild(visit(ctx.typeType()));
            typeArgument.addChild(upperBound);
        }
        else if (ctx.lowerBound != null) {
            final DetailAstImpl lowerBound = create(TokenTypes.TYPE_LOWER_BOUNDS, ctx.lowerBound);
            lowerBound.addChild(visit(ctx.typeType()));
            typeArgument.addChild(lowerBound);
        }

        return typeArgument;
    }

    @Override
    public DetailAstImpl visitQualifiedNameList(JavaLanguageParser.QualifiedNameListContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitFormalParameters(JavaLanguageParser.FormalParametersContext ctx) {
        final DetailAstImpl lparen = create(ctx.LPAREN());

        // We make a "PARAMETERS" node whether parameters exist or not
        if (ctx.formalParameterList() == null) {
            addLastSibling(lparen, createImaginary(TokenTypes.PARAMETERS));
        }
        else {
            addLastSibling(lparen, visit(ctx.formalParameterList()));
        }
        addLastSibling(lparen, create(ctx.RPAREN()));
        return lparen;
    }

    @Override
    public DetailAstImpl visitFormalParameterList(
            JavaLanguageParser.FormalParameterListContext ctx) {
        final DetailAstImpl parameters = createImaginary(TokenTypes.PARAMETERS);
        processChildren(parameters, ctx.children);
        return parameters;
    }

    @Override
    public DetailAstImpl visitFormalParameter(JavaLanguageParser.FormalParameterContext ctx) {
        final DetailAstImpl variableDeclaratorId =
                visitVariableDeclaratorId(ctx.variableDeclaratorId());
        final DetailAstImpl parameterDef = createImaginary(TokenTypes.PARAMETER_DEF);
        parameterDef.addChild(variableDeclaratorId);
        return parameterDef;
    }

    @Override
    public DetailAstImpl visitLastFormalParameter(
            JavaLanguageParser.LastFormalParameterContext ctx) {
        final DetailAstImpl parameterDef =
                createImaginary(TokenTypes.PARAMETER_DEF);
        parameterDef.addChild(visit(ctx.variableDeclaratorId()));
        final DetailAstImpl ident = (DetailAstImpl) parameterDef.findFirstToken(TokenTypes.IDENT);
        ident.addPreviousSibling(create(ctx.ELLIPSIS()));
        // We attach annotations on ellipses in varargs to the 'TYPE' ast
        final DetailAstImpl type = (DetailAstImpl) parameterDef.findFirstToken(TokenTypes.TYPE);
        type.addChild(visit(ctx.annotations()));
        return parameterDef;
    }

    @Override
    public DetailAstImpl visitQualifiedName(JavaLanguageParser.QualifiedNameContext ctx) {
        final DetailAstImpl ast = visit(ctx.id());
        final DetailAstPair currentAst = new DetailAstPair();
        DetailAstPair.addAstChild(currentAst, ast);

        for (ParserRuleContext extendedContext : ctx.extended) {
            final DetailAstImpl dot = create(extendedContext.start);
            DetailAstPair.makeAstRoot(currentAst, dot);
            final List<ParseTree> childList = extendedContext
                    .children.subList(1, extendedContext.children.size());
            processChildren(dot, childList);
        }
        return currentAst.getRoot();
    }

    @Override
    public DetailAstImpl visitLiteral(JavaLanguageParser.LiteralContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitIntegerLiteral(JavaLanguageParser.IntegerLiteralContext ctx) {
        final int[] longTypes = {
            JavaLanguageLexer.DECIMAL_LITERAL_LONG,
            JavaLanguageLexer.HEX_LITERAL_LONG,
            JavaLanguageLexer.OCT_LITERAL_LONG,
            JavaLanguageLexer.BINARY_LITERAL_LONG,
        };

        final int tokenType;
        if (TokenUtil.isOfType(ctx.start.getType(), longTypes)) {
            tokenType = TokenTypes.NUM_LONG;
        }
        else {
            tokenType = TokenTypes.NUM_INT;
        }

        return create(tokenType, ctx.start);
    }

    @Override
    public DetailAstImpl visitFloatLiteral(JavaLanguageParser.FloatLiteralContext ctx) {
        final DetailAstImpl floatLiteral;
        if (TokenUtil.isOfType(ctx.start.getType(),
                JavaLanguageLexer.DOUBLE_LITERAL, JavaLanguageLexer.HEX_DOUBLE_LITERAL)) {
            floatLiteral = create(TokenTypes.NUM_DOUBLE, ctx.start);
        }
        else {
            floatLiteral = create(TokenTypes.NUM_FLOAT, ctx.start);
        }
        return floatLiteral;
    }

    @Override
    public DetailAstImpl visitTextBlockLiteral(JavaLanguageParser.TextBlockLiteralContext ctx) {
        final DetailAstImpl textBlockLiteralBegin = create(ctx.TEXT_BLOCK_LITERAL_BEGIN());
        textBlockLiteralBegin.addChild(create(ctx.TEXT_BLOCK_CONTENT()));
        textBlockLiteralBegin.addChild(create(ctx.TEXT_BLOCK_LITERAL_END()));
        return textBlockLiteralBegin;
    }

    @Override
    public DetailAstImpl visitAnnotations(JavaLanguageParser.AnnotationsContext ctx) {
        final DetailAstImpl annotations;

        if (!ctx.createImaginaryNode && ctx.anno.isEmpty()) {
            // There are no annotations, and we don't want to create the empty node
            annotations = null;
        }
        else {
            // There are annotations, or we just want the empty node
            annotations = createImaginary(TokenTypes.ANNOTATIONS);
            processChildren(annotations, ctx.anno);
        }

        return annotations;
    }

    @Override
    public DetailAstImpl visitAnnotation(JavaLanguageParser.AnnotationContext ctx) {
        final DetailAstImpl annotation = createImaginary(TokenTypes.ANNOTATION);
        processChildren(annotation, ctx.children);
        return annotation;
    }

    @Override
    public DetailAstImpl visitElementValuePairs(JavaLanguageParser.ElementValuePairsContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitElementValuePair(JavaLanguageParser.ElementValuePairContext ctx) {
        final DetailAstImpl elementValuePair =
                createImaginary(TokenTypes.ANNOTATION_MEMBER_VALUE_PAIR);
        processChildren(elementValuePair, ctx.children);
        return elementValuePair;
    }

    @Override
    public DetailAstImpl visitElementValue(JavaLanguageParser.ElementValueContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitElementValueArrayInitializer(
            JavaLanguageParser.ElementValueArrayInitializerContext ctx) {
        final DetailAstImpl arrayInit =
                create(TokenTypes.ANNOTATION_ARRAY_INIT, (Token) ctx.LCURLY().getPayload());
        processChildren(arrayInit, ctx.children.subList(1, ctx.children.size()));
        return arrayInit;
    }

    @Override
    public DetailAstImpl visitAnnotationTypeDeclaration(
            JavaLanguageParser.AnnotationTypeDeclarationContext ctx) {
        return createTypeDeclaration(ctx, TokenTypes.ANNOTATION_DEF, ctx.mods);
    }

    @Override
    public DetailAstImpl visitAnnotationTypeBody(
            JavaLanguageParser.AnnotationTypeBodyContext ctx) {
        final DetailAstImpl objBlock = createImaginary(TokenTypes.OBJBLOCK);
        processChildren(objBlock, ctx.children);
        return objBlock;
    }

    @Override
    public DetailAstImpl visitAnnotationTypeElementDeclaration(
            JavaLanguageParser.AnnotationTypeElementDeclarationContext ctx) {
        final DetailAstImpl returnTree;
        if (ctx.SEMI() == null) {
            returnTree = visit(ctx.annotationTypeElementRest());
        }
        else {
            returnTree = create(ctx.SEMI());
        }
        return returnTree;
    }

    @Override
    public DetailAstImpl visitAnnotationField(JavaLanguageParser.AnnotationFieldContext ctx) {
        final DetailAstImpl dummyNode = new DetailAstImpl();
        // Since the TYPE AST is built by visitAnnotationMethodOrConstantRest(), we skip it
        // here (child [0])
        processChildren(dummyNode, Collections.singletonList(ctx.children.get(1)));
        // We also append the SEMI token to the first child [size() - 1],
        // until https://github.com/checkstyle/checkstyle/issues/3151
        dummyNode.getFirstChild().addChild(create(ctx.SEMI()));
        return dummyNode.getFirstChild();
    }

    @Override
    public DetailAstImpl visitAnnotationType(JavaLanguageParser.AnnotationTypeContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitAnnotationMethodRest(
            JavaLanguageParser.AnnotationMethodRestContext ctx) {
        final DetailAstImpl annotationFieldDef =
                createImaginary(TokenTypes.ANNOTATION_FIELD_DEF);
        annotationFieldDef.addChild(createModifiers(ctx.mods));
        annotationFieldDef.addChild(visit(ctx.type));

        // Process all children except C style array declarators
        processChildren(annotationFieldDef, ctx.children.stream()
                .filter(child -> !(child instanceof JavaLanguageParser.ArrayDeclaratorContext))
                .collect(Collectors.toList()));

        // We add C style array declarator brackets to TYPE ast
        final DetailAstImpl typeAst =
                (DetailAstImpl) annotationFieldDef.findFirstToken(TokenTypes.TYPE);
        ctx.cStyleArrDec.forEach(child -> typeAst.addChild(visit(child)));

        return annotationFieldDef;
    }

    @Override
    public DetailAstImpl visitDefaultValue(JavaLanguageParser.DefaultValueContext ctx) {
        final DetailAstImpl defaultValue = create(ctx.LITERAL_DEFAULT());
        defaultValue.addChild(visit(ctx.elementValue()));
        return defaultValue;
    }

    @Override
    public DetailAstImpl visitConstructorBlock(JavaLanguageParser.ConstructorBlockContext ctx) {
        final DetailAstImpl slist = create(TokenTypes.SLIST, ctx.start);
        // SLIST was child [0]
        processChildren(slist, ctx.children.subList(1, ctx.children.size()));
        return slist;
    }

    @Override
    public DetailAstImpl visitExplicitCtorCall(JavaLanguageParser.ExplicitCtorCallContext ctx) {
        final DetailAstImpl root;
        if (ctx.LITERAL_THIS() == null) {
            root = create(TokenTypes.SUPER_CTOR_CALL, (Token) ctx.LITERAL_SUPER().getPayload());
        }
        else {
            root = create(TokenTypes.CTOR_CALL, (Token) ctx.LITERAL_THIS().getPayload());
        }
        root.addChild(visit(ctx.typeArguments()));
        root.addChild(visit(ctx.arguments()));
        root.addChild(create(ctx.SEMI()));
        return root;
    }

    @Override
    public DetailAstImpl visitPrimaryCtorCall(JavaLanguageParser.PrimaryCtorCallContext ctx) {
        final DetailAstImpl primaryCtorCall = create(TokenTypes.SUPER_CTOR_CALL,
                (Token) ctx.LITERAL_SUPER().getPayload());
        // filter 'LITERAL_SUPER'
        processChildren(primaryCtorCall, ctx.children.stream()
                   .filter(child -> !child.equals(ctx.LITERAL_SUPER()))
                   .collect(Collectors.toList()));
        return primaryCtorCall;
    }

    @Override
    public DetailAstImpl visitBlock(JavaLanguageParser.BlockContext ctx) {
        final DetailAstImpl slist = create(TokenTypes.SLIST, ctx.start);
        // SLIST was child [0]
        processChildren(slist, ctx.children.subList(1, ctx.children.size()));
        return slist;
    }

    @Override
    public DetailAstImpl visitLocalVar(JavaLanguageParser.LocalVarContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitBlockStat(JavaLanguageParser.BlockStatContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitAssertExp(JavaLanguageParser.AssertExpContext ctx) {
        final DetailAstImpl assertExp = create(ctx.ASSERT());
        // child[0] is 'ASSERT'
        processChildren(assertExp, ctx.children.subList(1, ctx.children.size()));
        return assertExp;
    }

    @Override
    public DetailAstImpl visitIfStat(JavaLanguageParser.IfStatContext ctx) {
        final DetailAstImpl ifStat = create(ctx.LITERAL_IF());
        // child[0] is 'LITERAL_IF'
        processChildren(ifStat, ctx.children.subList(1, ctx.children.size()));
        return ifStat;
    }

    @Override
    public DetailAstImpl visitForStat(JavaLanguageParser.ForStatContext ctx) {
        final DetailAstImpl forInit = create(ctx.start);
        // child[0] is LITERAL_FOR
        processChildren(forInit, ctx.children.subList(1, ctx.children.size()));
        return forInit;
    }

    @Override
    public DetailAstImpl visitWhileStat(JavaLanguageParser.WhileStatContext ctx) {
        final DetailAstImpl whileStatement = create(ctx.start);
        // 'LITERAL_WHILE' is child[0]
        processChildren(whileStatement, ctx.children.subList(1, ctx.children.size()));
        return whileStatement;
    }

    @Override
    public DetailAstImpl visitDoStat(JavaLanguageParser.DoStatContext ctx) {
        final DetailAstImpl doStatement = create(ctx.start);
        // 'LITERAL_DO' is child[0]
        doStatement.addChild(visit(ctx.statement()));
        // We make 'LITERAL_WHILE' into 'DO_WHILE'
        doStatement.addChild(create(TokenTypes.DO_WHILE, (Token) ctx.LITERAL_WHILE().getPayload()));
        doStatement.addChild(visit(ctx.parExpression()));
        doStatement.addChild(create(ctx.SEMI()));
        return doStatement;
    }

    @Override
    public DetailAstImpl visitTryStat(JavaLanguageParser.TryStatContext ctx) {
        final DetailAstImpl tryStat = create(ctx.start);
        // child[0] is 'LITERAL_TRY'
        processChildren(tryStat, ctx.children.subList(1, ctx.children.size()));
        return tryStat;
    }

    @Override
    public DetailAstImpl visitTryWithResourceStat(
            JavaLanguageParser.TryWithResourceStatContext ctx) {
        final DetailAstImpl tryWithResources = create(ctx.LITERAL_TRY());
        // child[0] is 'LITERAL_TRY'
        processChildren(tryWithResources, ctx.children.subList(1, ctx.children.size()));
        return tryWithResources;
    }

    @Override
    public DetailAstImpl visitYieldStat(JavaLanguageParser.YieldStatContext ctx) {
        final DetailAstImpl yieldParent = create(ctx.LITERAL_YIELD());
        // LITERAL_YIELD is child[0]
        processChildren(yieldParent, ctx.children.subList(1, ctx.children.size()));
        return yieldParent;
    }

    @Override
    public DetailAstImpl visitSyncStat(JavaLanguageParser.SyncStatContext ctx) {
        final DetailAstImpl syncStatement = create(ctx.start);
        // child[0] is 'LITERAL_SYNCHRONIZED'
        processChildren(syncStatement, ctx.children.subList(1, ctx.children.size()));
        return syncStatement;
    }

    @Override
    public DetailAstImpl visitReturnStat(JavaLanguageParser.ReturnStatContext ctx) {
        final DetailAstImpl returnStat = create(ctx.LITERAL_RETURN());
        // child[0] is 'LITERAL_RETURN'
        processChildren(returnStat, ctx.children.subList(1, ctx.children.size()));
        return returnStat;
    }

    @Override
    public DetailAstImpl visitThrowStat(JavaLanguageParser.ThrowStatContext ctx) {
        final DetailAstImpl throwStat = create(ctx.LITERAL_THROW());
        // child[0] is 'LITERAL_THROW'
        processChildren(throwStat, ctx.children.subList(1, ctx.children.size()));
        return throwStat;
    }

    @Override
    public DetailAstImpl visitBreakStat(JavaLanguageParser.BreakStatContext ctx) {
        final DetailAstImpl literalBreak = create(ctx.LITERAL_BREAK());
        // child[0] is 'LITERAL_BREAK'
        processChildren(literalBreak, ctx.children.subList(1, ctx.children.size()));
        return literalBreak;
    }

    @Override
    public DetailAstImpl visitContinueStat(JavaLanguageParser.ContinueStatContext ctx) {
        final DetailAstImpl continueStat = create(ctx.LITERAL_CONTINUE());
        // child[0] is 'LITERAL_CONTINUE'
        processChildren(continueStat, ctx.children.subList(1, ctx.children.size()));
        return continueStat;
    }

    @Override
    public DetailAstImpl visitEmptyStat(JavaLanguageParser.EmptyStatContext ctx) {
        return create(TokenTypes.EMPTY_STAT, ctx.start);
    }

    @Override
    public DetailAstImpl visitExpStat(JavaLanguageParser.ExpStatContext ctx) {
        final DetailAstImpl expStatRoot = visit(ctx.statementExpression);
        addLastSibling(expStatRoot, create(ctx.SEMI()));
        return expStatRoot;
    }

    @Override
    public DetailAstImpl visitLabelStat(JavaLanguageParser.LabelStatContext ctx) {
        final DetailAstImpl labelStat = create(TokenTypes.LABELED_STAT,
                (Token) ctx.COLON().getPayload());
        labelStat.addChild(visit(ctx.id()));
        labelStat.addChild(visit(ctx.statement()));
        return labelStat;
    }

    @Override
    public DetailAstImpl visitSwitchExpressionOrStatement(
            JavaLanguageParser.SwitchExpressionOrStatementContext ctx) {
        final DetailAstImpl switchStat = create(ctx.LITERAL_SWITCH());
        switchStat.addChild(visit(ctx.parExpression()));
        switchStat.addChild(create(ctx.LCURLY()));
        switchStat.addChild(visit(ctx.switchBlock()));
        switchStat.addChild(create(ctx.RCURLY()));
        return switchStat;
    }

    @Override
    public DetailAstImpl visitSwitchRules(JavaLanguageParser.SwitchRulesContext ctx) {
        final DetailAstImpl dummyRoot = new DetailAstImpl();
        ctx.switchLabeledRule().forEach(switchLabeledRuleContext -> {
            final DetailAstImpl switchRule = visit(switchLabeledRuleContext);
            final DetailAstImpl switchRuleParent = createImaginary(TokenTypes.SWITCH_RULE);
            switchRuleParent.addChild(switchRule);
            dummyRoot.addChild(switchRuleParent);
        });
        return dummyRoot.getFirstChild();
    }

    @Override
    public DetailAstImpl visitSwitchBlocks(JavaLanguageParser.SwitchBlocksContext ctx) {
        final DetailAstImpl dummyRoot = new DetailAstImpl();
        ctx.groups.forEach(group -> dummyRoot.addChild(visit(group)));

        // Add any empty switch labels to end of statement in one 'CASE_GROUP'
        if (!ctx.emptyLabels.isEmpty()) {
            final DetailAstImpl emptyLabelParent =
                    createImaginary(TokenTypes.CASE_GROUP);
            ctx.emptyLabels.forEach(label -> emptyLabelParent.addChild(visit(label)));
            dummyRoot.addChild(emptyLabelParent);
        }
        return dummyRoot.getFirstChild();
    }

    @Override
    public DetailAstImpl visitSwitchLabeledExpression(
            JavaLanguageParser.SwitchLabeledExpressionContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitSwitchLabeledBlock(
            JavaLanguageParser.SwitchLabeledBlockContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitSwitchLabeledThrow(
            JavaLanguageParser.SwitchLabeledThrowContext ctx) {
        final DetailAstImpl switchLabel = visit(ctx.switchLabel());
        addLastSibling(switchLabel, create(ctx.LAMBDA()));
        final DetailAstImpl literalThrow = create(ctx.LITERAL_THROW());
        literalThrow.addChild(visit(ctx.expression()));
        literalThrow.addChild(create(ctx.SEMI()));
        addLastSibling(switchLabel, literalThrow);
        return switchLabel;
    }

    @Override
    public DetailAstImpl visitElseStat(JavaLanguageParser.ElseStatContext ctx) {
        final DetailAstImpl elseStat = create(ctx.LITERAL_ELSE());
        // child[0] is 'LITERAL_ELSE'
        processChildren(elseStat, ctx.children.subList(1, ctx.children.size()));
        return elseStat;
    }

    @Override
    public DetailAstImpl visitCatchClause(JavaLanguageParser.CatchClauseContext ctx) {
        final DetailAstImpl catchClause = create(TokenTypes.LITERAL_CATCH,
                (Token) ctx.LITERAL_CATCH().getPayload());
        // 'LITERAL_CATCH' is child[0]
        processChildren(catchClause, ctx.children.subList(1, ctx.children.size()));
        return catchClause;
    }

    @Override
    public DetailAstImpl visitCatchParameter(JavaLanguageParser.CatchParameterContext ctx) {
        final DetailAstImpl catchParameterDef = createImaginary(TokenTypes.PARAMETER_DEF);
        catchParameterDef.addChild(createModifiers(ctx.mods));
        // filter mods
        processChildren(catchParameterDef, ctx.children.stream()
                .filter(child -> !(child instanceof JavaLanguageParser.VariableModifierContext))
                .collect(Collectors.toList()));
        return catchParameterDef;
    }

    @Override
    public DetailAstImpl visitCatchType(JavaLanguageParser.CatchTypeContext ctx) {
        final DetailAstImpl type = createImaginary(TokenTypes.TYPE);
        processChildren(type, ctx.children);
        return type;
    }

    @Override
    public DetailAstImpl visitFinallyBlock(JavaLanguageParser.FinallyBlockContext ctx) {
        final DetailAstImpl finallyBlock = create(ctx.LITERAL_FINALLY());
        // child[0] is 'LITERAL_FINALLY'
        processChildren(finallyBlock, ctx.children.subList(1, ctx.children.size()));
        return finallyBlock;
    }

    @Override
    public DetailAstImpl visitResourceSpecification(
            JavaLanguageParser.ResourceSpecificationContext ctx) {
        final DetailAstImpl resourceSpecification =
                createImaginary(TokenTypes.RESOURCE_SPECIFICATION);
        processChildren(resourceSpecification, ctx.children);
        return resourceSpecification;
    }

    @Override
    public DetailAstImpl visitResources(JavaLanguageParser.ResourcesContext ctx) {
        final DetailAstImpl firstResource = visit(ctx.resource(0));
        final DetailAstImpl resources = createImaginary(TokenTypes.RESOURCES);
        resources.addChild(firstResource);
        processChildren(resources, ctx.children.subList(1, ctx.children.size()));
        return resources;
    }

    @Override
    public DetailAstImpl visitResourceDeclaration(
            JavaLanguageParser.ResourceDeclarationContext ctx) {
        final DetailAstImpl resource = createImaginary(TokenTypes.RESOURCE);
        resource.addChild(visit(ctx.variableDeclaratorId()));

        final DetailAstImpl assign = create(ctx.ASSIGN());
        resource.addChild(assign);
        assign.addChild(visit(ctx.expression()));
        return resource;
    }

    @Override
    public DetailAstImpl visitVariableAccess(JavaLanguageParser.VariableAccessContext ctx) {
        final DetailAstImpl resource;
        if (ctx.accessList.isEmpty()) {
            resource = createImaginary(TokenTypes.RESOURCE);
            resource.addChild(visit(ctx.id()));
        }
        else {
            final DetailAstPair currentAst = new DetailAstPair();
            ctx.accessList.forEach(fieldAccess -> {
                DetailAstPair.addAstChild(currentAst, visit(fieldAccess.expr()));
                DetailAstPair.makeAstRoot(currentAst, create(fieldAccess.DOT()));
            });
            resource = createImaginary(TokenTypes.RESOURCE);
            resource.addChild(currentAst.root);
            if (ctx.LITERAL_THIS() == null) {
                resource.getFirstChild().addChild(visit(ctx.id()));
            }
            else {
                resource.getFirstChild().addChild(create(ctx.LITERAL_THIS()));
            }
        }
        return resource;
    }

    @Override
    public DetailAstImpl visitSwitchBlockStatementGroup(
            JavaLanguageParser.SwitchBlockStatementGroupContext ctx) {
        final DetailAstImpl caseGroup = createImaginary(TokenTypes.CASE_GROUP);
        processChildren(caseGroup, ctx.switchLabel());
        final DetailAstImpl sList = createImaginary(TokenTypes.SLIST);
        processChildren(sList, ctx.slists);
        caseGroup.addChild(sList);
        return caseGroup;
    }

    @Override
    public DetailAstImpl visitCaseLabel(JavaLanguageParser.CaseLabelContext ctx) {
        final DetailAstImpl caseLabel = create(ctx.LITERAL_CASE());
        // child [0] is 'LITERAL_CASE'
        processChildren(caseLabel, ctx.children.subList(1, ctx.children.size()));
        return caseLabel;
    }

    @Override
    public DetailAstImpl visitDefaultLabel(JavaLanguageParser.DefaultLabelContext ctx) {
        final DetailAstImpl defaultLabel = create(ctx.LITERAL_DEFAULT());
        if (ctx.COLON() != null) {
            defaultLabel.addChild(create(ctx.COLON()));
        }
        return defaultLabel;
    }

    @Override
    public DetailAstImpl visitCaseConstants(JavaLanguageParser.CaseConstantsContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitCaseConstant(JavaLanguageParser.CaseConstantContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitEnhancedFor(JavaLanguageParser.EnhancedForContext ctx) {
        final DetailAstImpl leftParen = create(ctx.LPAREN());
        final DetailAstImpl enhancedForControl =
                 visit(ctx.enhancedForControl());
        final DetailAstImpl forEachClause = createImaginary(TokenTypes.FOR_EACH_CLAUSE);
        forEachClause.addChild(enhancedForControl);
        addLastSibling(leftParen, forEachClause);
        addLastSibling(leftParen, create(ctx.RPAREN()));
        return leftParen;
    }

    @Override
    public DetailAstImpl visitForFor(JavaLanguageParser.ForForContext ctx) {
        final DetailAstImpl dummyRoot = new DetailAstImpl();
        dummyRoot.addChild(create(ctx.LPAREN()));

        if (ctx.forInit() == null) {
            final DetailAstImpl imaginaryForInitParent =
                    createImaginary(TokenTypes.FOR_INIT);
            dummyRoot.addChild(imaginaryForInitParent);
        }
        else {
            dummyRoot.addChild(visit(ctx.forInit()));
        }

        dummyRoot.addChild(create(ctx.SEMI(0)));

        final DetailAstImpl forCondParent = createImaginary(TokenTypes.FOR_CONDITION);
        forCondParent.addChild(visit(ctx.forCond));
        dummyRoot.addChild(forCondParent);
        dummyRoot.addChild(create(ctx.SEMI(1)));

        final DetailAstImpl forItParent = createImaginary(TokenTypes.FOR_ITERATOR);
        forItParent.addChild(visit(ctx.forUpdate));
        dummyRoot.addChild(forItParent);

        dummyRoot.addChild(create(ctx.RPAREN()));

        return dummyRoot.getFirstChild();
    }

    @Override
    public DetailAstImpl visitForInit(JavaLanguageParser.ForInitContext ctx) {
        final DetailAstImpl forInit = createImaginary(TokenTypes.FOR_INIT);
        processChildren(forInit, ctx.children);
        return forInit;
    }

    @Override
    public DetailAstImpl visitEnhancedForControl(
            JavaLanguageParser.EnhancedForControlContext ctx) {
        final DetailAstImpl variableDeclaratorId =
                 visit(ctx.variableDeclaratorId());
        final DetailAstImpl variableDef = createImaginary(TokenTypes.VARIABLE_DEF);
        variableDef.addChild(variableDeclaratorId);

        addLastSibling(variableDef, create(ctx.COLON()));
        addLastSibling(variableDef, visit(ctx.expression()));
        return variableDef;
    }

    @Override
    public DetailAstImpl visitParExpression(JavaLanguageParser.ParExpressionContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitExpressionList(JavaLanguageParser.ExpressionListContext ctx) {
        final DetailAstImpl elist = createImaginary(TokenTypes.ELIST);
        processChildren(elist, ctx.children);
        return elist;
    }

    @Override
    public DetailAstImpl visitExpression(JavaLanguageParser.ExpressionContext ctx) {
        return buildExpressionNode(ctx.expr());
    }

    @Override
    public DetailAstImpl visitRefOp(JavaLanguageParser.RefOpContext ctx) {
        final DetailAstImpl bop = create(ctx.bop);
        final DetailAstImpl leftChild = visit(ctx.expr());
        final DetailAstImpl rightChild = create(TokenTypes.IDENT, ctx.stop);
        bop.addChild(leftChild);
        bop.addChild(rightChild);
        return bop;
    }

    @Override
    public DetailAstImpl visitSuperExp(JavaLanguageParser.SuperExpContext ctx) {
        final DetailAstImpl bop = create(ctx.bop);
        bop.addChild(visit(ctx.expr()));
        bop.addChild(create(ctx.LITERAL_SUPER()));
        DetailAstImpl superSuffixParent = visit(ctx.superSuffix());

        if (superSuffixParent == null) {
            superSuffixParent = bop;
        }
        else {
            DetailAstImpl firstChild = superSuffixParent;
            while (firstChild.getFirstChild() != null) {
                firstChild = firstChild.getFirstChild();
            }
            firstChild.addPreviousSibling(bop);
        }

        return superSuffixParent;
    }

    @Override
    public DetailAstImpl visitInstanceOfExp(JavaLanguageParser.InstanceOfExpContext ctx) {
        final DetailAstImpl literalInstanceOf = create(ctx.LITERAL_INSTANCEOF());
        literalInstanceOf.addChild(visit(ctx.expr()));
        final ParseTree patternOrType = ctx.getChild(2);

        final DetailAstImpl patternDef;
        if (patternOrType instanceof JavaLanguageParser.ParenPatternContext) {
            // Parenthesized pattern has a `PATTERN_DEF` parent
            patternDef = createImaginary(TokenTypes.PATTERN_DEF);
            patternDef.addChild(visit(patternOrType));
        }
        else {
            patternDef = visit(patternOrType);
        }
        literalInstanceOf.addChild(patternDef);
        return literalInstanceOf;
    }

    @Override
    public DetailAstImpl visitBitShift(JavaLanguageParser.BitShiftContext ctx) {
        final DetailAstImpl shiftOperation;

        // We determine the type of shift operation in the parser, instead of the
        // lexer as in older grammars. This makes it easier to parse type parameters
        // and less than/ greater than operators in general.
        if (ctx.LT().size() == LEFT_SHIFT.length()) {
            shiftOperation = create(TokenTypes.SL, (Token) ctx.LT(0).getPayload());
            shiftOperation.setText(LEFT_SHIFT);
        }
        else if (ctx.GT().size() == UNSIGNED_RIGHT_SHIFT.length()) {
            shiftOperation = create(TokenTypes.BSR, (Token) ctx.GT(0).getPayload());
            shiftOperation.setText(UNSIGNED_RIGHT_SHIFT);
        }
        else {
            shiftOperation = create(TokenTypes.SR, (Token) ctx.GT(0).getPayload());
            shiftOperation.setText(RIGHT_SHIFT);
        }

        shiftOperation.addChild(visit(ctx.expr(0)));
        shiftOperation.addChild(visit(ctx.expr(1)));
        return shiftOperation;
    }

    @Override
    public DetailAstImpl visitNewExp(JavaLanguageParser.NewExpContext ctx) {
        final DetailAstImpl newExp = create(ctx.LITERAL_NEW());
        // child [0] is LITERAL_NEW
        processChildren(newExp, ctx.children.subList(1, ctx.children.size()));
        return newExp;
    }

    @Override
    public DetailAstImpl visitPrefix(JavaLanguageParser.PrefixContext ctx) {
        final int tokenType;
        switch (ctx.prefix.getType()) {
            case JavaLanguageLexer.PLUS:
                tokenType = TokenTypes.UNARY_PLUS;
                break;
            case JavaLanguageLexer.MINUS:
                tokenType = TokenTypes.UNARY_MINUS;
                break;
            default:
                tokenType = ctx.prefix.getType();
        }
        final DetailAstImpl prefix = create(tokenType, ctx.prefix);
        prefix.addChild(visit(ctx.expr()));
        return prefix;
    }

    @Override
    public DetailAstImpl visitCastExp(JavaLanguageParser.CastExpContext ctx) {
        final DetailAstImpl cast = create(TokenTypes.TYPECAST, (Token) ctx.LPAREN().getPayload());
        // child [0] is LPAREN
        processChildren(cast, ctx.children.subList(1, ctx.children.size()));
        return cast;
    }

    @Override
    public DetailAstImpl visitIndexOp(JavaLanguageParser.IndexOpContext ctx) {
        // LBRACK -> INDEX_OP is root of this AST
        final DetailAstImpl indexOp = create(TokenTypes.INDEX_OP,
                (Token) ctx.LBRACK().getPayload());

        // add expression(IDENT) on LHS
        indexOp.addChild(visit(ctx.expr(0)));

        // create imaginary node for expression on RHS
        final DetailAstImpl expr = visit(ctx.expr(1));
        final DetailAstImpl imaginaryExpr = createImaginary(TokenTypes.EXPR);
        imaginaryExpr.addChild(expr);
        indexOp.addChild(imaginaryExpr);

        // complete AST by adding RBRACK
        indexOp.addChild(create(ctx.RBRACK()));
        return indexOp;
    }

    @Override
    public DetailAstImpl visitInvOp(JavaLanguageParser.InvOpContext ctx) {
        final DetailAstPair currentAst = new DetailAstPair();

        final DetailAstImpl returnAst = visit(ctx.expr());
        DetailAstPair.addAstChild(currentAst, returnAst);
        DetailAstPair.makeAstRoot(currentAst, create(ctx.bop));

        DetailAstPair.addAstChild(currentAst,
                 visit(ctx.nonWildcardTypeArguments()));
        DetailAstPair.addAstChild(currentAst, visit(ctx.id()));
        final DetailAstImpl lparen = create(TokenTypes.METHOD_CALL,
                (Token) ctx.LPAREN().getPayload());
        DetailAstPair.makeAstRoot(currentAst, lparen);

        // We always add an 'ELIST' node
        final DetailAstImpl expressionList = Optional.ofNullable(visit(ctx.expressionList()))
                .orElseGet(() -> createImaginary(TokenTypes.ELIST));

        DetailAstPair.addAstChild(currentAst, expressionList);
        DetailAstPair.addAstChild(currentAst, create(ctx.RPAREN()));

        return currentAst.root;
    }

    @Override
    public DetailAstImpl visitInitExp(JavaLanguageParser.InitExpContext ctx) {
        final DetailAstImpl dot = create(ctx.bop);
        dot.addChild(visit(ctx.expr()));
        final DetailAstImpl literalNew = create(ctx.LITERAL_NEW());
        literalNew.addChild(visit(ctx.nonWildcardTypeArguments()));
        literalNew.addChild(visit(ctx.innerCreator()));
        dot.addChild(literalNew);
        return dot;
    }

    @Override
    public DetailAstImpl visitSimpleMethodCall(JavaLanguageParser.SimpleMethodCallContext ctx) {
        final DetailAstImpl methodCall = create(TokenTypes.METHOD_CALL,
                (Token) ctx.LPAREN().getPayload());
        methodCall.addChild(visit(ctx.id()));
        // We always add an 'ELIST' node
        final DetailAstImpl expressionList = Optional.ofNullable(visit(ctx.expressionList()))
                .orElseGet(() -> createImaginary(TokenTypes.ELIST));

        methodCall.addChild(expressionList);
        methodCall.addChild(create((Token) ctx.RPAREN().getPayload()));
        return methodCall;
    }

    @Override
    public DetailAstImpl visitLambdaExp(JavaLanguageParser.LambdaExpContext ctx) {
        final DetailAstImpl lambda = create(ctx.LAMBDA());
        lambda.addChild(visit(ctx.lambdaParameters()));

        final JavaLanguageParser.BlockContext blockContext = ctx.block();
        final DetailAstImpl rightHandLambdaChild;
        if (blockContext != null) {
            rightHandLambdaChild = visit(blockContext);
        }
        else {
            // Lambda expression child is built the same way that we build
            // the initial expression node in visitExpression, i.e. with
            // an imaginary EXPR node. This results in nested EXPR nodes
            // in the AST.
            rightHandLambdaChild = buildExpressionNode(ctx.expr());
        }
        lambda.addChild(rightHandLambdaChild);
        return lambda;
    }

    @Override
    public DetailAstImpl visitThisExp(JavaLanguageParser.ThisExpContext ctx) {
        final DetailAstImpl bop = create(ctx.bop);
        bop.addChild(visit(ctx.expr()));
        bop.addChild(create(ctx.LITERAL_THIS()));
        return bop;
    }

    @Override
    public DetailAstImpl visitPrimaryExp(JavaLanguageParser.PrimaryExpContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitPostfix(JavaLanguageParser.PostfixContext ctx) {
        final DetailAstImpl postfix;
        if (ctx.postfix.getType() == JavaLanguageLexer.INC) {
            postfix = create(TokenTypes.POST_INC, ctx.postfix);
        }
        else {
            postfix = create(TokenTypes.POST_DEC, ctx.postfix);
        }
        postfix.addChild(visit(ctx.expr()));
        return postfix;
    }

    @Override
    public DetailAstImpl visitMethodRef(JavaLanguageParser.MethodRefContext ctx) {
        final DetailAstImpl doubleColon = create(TokenTypes.METHOD_REF,
                (Token) ctx.DOUBLE_COLON().getPayload());
        final List<ParseTree> children = ctx.children.stream()
                .filter(child -> !child.equals(ctx.DOUBLE_COLON()))
                .collect(Collectors.toList());
        processChildren(doubleColon, children);
        return doubleColon;
    }

    @Override
    public DetailAstImpl visitTernaryOp(JavaLanguageParser.TernaryOpContext ctx) {
        final DetailAstImpl root = create(ctx.QUESTION());
        processChildren(root, ctx.children.stream()
                .filter(child -> !child.equals(ctx.QUESTION()))
                .collect(Collectors.toList()));
        return root;
    }

    @Override
    public DetailAstImpl visitBinOp(JavaLanguageParser.BinOpContext ctx) {
        final DetailAstImpl bop = create(ctx.bop);

        // To improve performance, we iterate through binary operations
        // since they are frequently deeply nested.
        final List<JavaLanguageParser.BinOpContext> binOpList = new ArrayList<>();
        ParseTree firstExpression = ctx.expr(0);
        while (firstExpression instanceof JavaLanguageParser.BinOpContext) {
            // Get all nested binOps
            binOpList.add((JavaLanguageParser.BinOpContext) firstExpression);
            firstExpression = ((JavaLanguageParser.BinOpContext) firstExpression).expr(0);
        }

        if (binOpList.isEmpty()) {
            final DetailAstImpl leftChild = visit(ctx.children.get(0));
            bop.addChild(leftChild);
        }
        else {
            // Map all descendants to individual AST's since we can parallelize this
            // operation
            final Queue<DetailAstImpl> descendantList = binOpList.parallelStream()
                    .map(this::getInnerBopAst)
                    .collect(Collectors.toCollection(ConcurrentLinkedQueue::new));

            bop.addChild(descendantList.poll());
            DetailAstImpl pointer = bop.getFirstChild();
            // Build tree
            for (DetailAstImpl descendant : descendantList) {
                pointer.getFirstChild().addPreviousSibling(descendant);
                pointer = descendant;
            }
        }

        bop.addChild(visit(ctx.children.get(2)));
        return bop;
    }

    /**
     * Builds the binary operation (binOp) AST.
     *
     * @param descendant the BinOpContext to build AST from
     * @return binOp AST
     */
    private DetailAstImpl getInnerBopAst(JavaLanguageParser.BinOpContext descendant) {
        final DetailAstImpl innerBop = create(descendant.bop);
        final JavaLanguageParser.ExprContext expr = descendant.expr(0);
        if (!(expr instanceof JavaLanguageParser.BinOpContext)) {
            innerBop.addChild(visit(expr));
        }
        innerBop.addChild(visit(descendant.expr(1)));
        return innerBop;
    }

    @Override
    public DetailAstImpl visitMethodCall(JavaLanguageParser.MethodCallContext ctx) {
        final DetailAstImpl methodCall = create(TokenTypes.METHOD_CALL,
                (Token) ctx.LPAREN().getPayload());
        // We always add an 'ELIST' node
        final DetailAstImpl expressionList = Optional.ofNullable(visit(ctx.expressionList()))
                .orElseGet(() -> createImaginary(TokenTypes.ELIST));

        final DetailAstImpl dot = create(ctx.DOT());
        dot.addChild(visit(ctx.expr()));
        dot.addChild(visit(ctx.id()));
        methodCall.addChild(dot);
        methodCall.addChild(expressionList);
        methodCall.addChild(create((Token) ctx.RPAREN().getPayload()));
        return methodCall;
    }

    @Override
    public DetailAstImpl visitTypeCastParameters(
            JavaLanguageParser.TypeCastParametersContext ctx) {
        final DetailAstImpl typeType = visit(ctx.typeType(0));
        for (int i = 0; i < ctx.BAND().size(); i++) {
            addLastSibling(typeType, create(TokenTypes.TYPE_EXTENSION_AND,
                                (Token) ctx.BAND(i).getPayload()));
            addLastSibling(typeType, visit(ctx.typeType(i + 1)));
        }
        return typeType;
    }

    @Override
    public DetailAstImpl visitSingleLambdaParam(JavaLanguageParser.SingleLambdaParamContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitFormalLambdaParam(JavaLanguageParser.FormalLambdaParamContext ctx) {
        final DetailAstImpl lparen = create(ctx.LPAREN());

        // We add an 'PARAMETERS' node here whether it exists or not
        final DetailAstImpl parameters = Optional.ofNullable(visit(ctx.formalParameterList()))
                .orElseGet(() -> createImaginary(TokenTypes.PARAMETERS));
        addLastSibling(lparen, parameters);
        addLastSibling(lparen, create(ctx.RPAREN()));
        return lparen;
    }

    @Override
    public DetailAstImpl visitMultiLambdaParam(JavaLanguageParser.MultiLambdaParamContext ctx) {
        final DetailAstImpl lparen = create(ctx.LPAREN());
        addLastSibling(lparen, visit(ctx.multiLambdaParams()));
        addLastSibling(lparen, create(ctx.RPAREN()));
        return lparen;
    }

    @Override
    public DetailAstImpl visitMultiLambdaParams(JavaLanguageParser.MultiLambdaParamsContext ctx) {
        final DetailAstImpl parameters = createImaginary(TokenTypes.PARAMETERS);
        parameters.addChild(createLambdaParameter(ctx.id(0)));

        for (int i = 0; i < ctx.COMMA().size(); i++) {
            parameters.addChild(create(ctx.COMMA(i)));
            parameters.addChild(createLambdaParameter(ctx.id(i + 1)));
        }
        return parameters;
    }

    /**
     * Creates a 'PARAMETER_DEF' node for a lambda expression, with
     * imaginary modifier and type nodes.
     *
     * @param ctx the IdContext to create imaginary nodes for
     * @return DetailAstImpl of lambda parameter
     */
    private DetailAstImpl createLambdaParameter(JavaLanguageParser.IdContext ctx) {
        final DetailAstImpl ident = visitId(ctx);
        final DetailAstImpl parameter = createImaginary(TokenTypes.PARAMETER_DEF);
        final DetailAstImpl modifiers = createImaginary(TokenTypes.MODIFIERS);
        final DetailAstImpl type = createImaginary(TokenTypes.TYPE);
        parameter.addChild(modifiers);
        parameter.addChild(type);
        parameter.addChild(ident);
        return parameter;
    }

    @Override
    public DetailAstImpl visitParenPrimary(JavaLanguageParser.ParenPrimaryContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitTokenPrimary(JavaLanguageParser.TokenPrimaryContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitClassRefPrimary(JavaLanguageParser.ClassRefPrimaryContext ctx) {
        final DetailAstImpl dot = create(ctx.DOT());
        final DetailAstImpl primaryTypeNoArray = visit(ctx.type);
        dot.addChild(primaryTypeNoArray);
        if (TokenUtil.isOfType(primaryTypeNoArray, TokenTypes.DOT)) {
            // We append '[]' to the qualified name 'TYPE' `ast
            ctx.arrayDeclarator()
                    .forEach(child -> primaryTypeNoArray.addChild(visit(child)));
        }
        else {
            ctx.arrayDeclarator()
                    .forEach(child -> addLastSibling(primaryTypeNoArray, visit(child)));
        }
        dot.addChild(create(ctx.LITERAL_CLASS()));
        return dot;
    }

    @Override
    public DetailAstImpl visitPrimitivePrimary(JavaLanguageParser.PrimitivePrimaryContext ctx) {
        final DetailAstImpl dot = create(ctx.DOT());
        final DetailAstImpl primaryTypeNoArray = visit(ctx.type);
        dot.addChild(primaryTypeNoArray);
        ctx.arrayDeclarator().forEach(child -> dot.addChild(visit(child)));
        dot.addChild(create(ctx.LITERAL_CLASS()));
        return dot;
    }

    @Override
    public DetailAstImpl visitCreator(JavaLanguageParser.CreatorContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitCreatedNameObject(JavaLanguageParser.CreatedNameObjectContext ctx) {
        final DetailAstPair currentAST = new DetailAstPair();
        DetailAstPair.addAstChild(currentAST, visit(ctx.annotations()));
        DetailAstPair.addAstChild(currentAST, visit(ctx.id()));
        DetailAstPair.addAstChild(currentAST, visit(ctx.typeArgumentsOrDiamond()));

        // This is how we build the type arguments/ qualified name tree
        for (ParserRuleContext extendedContext : ctx.extended) {
            final DetailAstImpl dot = create(extendedContext.start);
            DetailAstPair.makeAstRoot(currentAST, dot);
            final List<ParseTree> childList = extendedContext
                    .children.subList(1, extendedContext.children.size());
            processChildren(dot, childList);
        }

        return currentAST.root;
    }

    @Override
    public DetailAstImpl visitCreatedNamePrimitive(
            JavaLanguageParser.CreatedNamePrimitiveContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitInnerCreator(JavaLanguageParser.InnerCreatorContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitArrayCreatorRest(JavaLanguageParser.ArrayCreatorRestContext ctx) {
        final DetailAstImpl arrayDeclarator = create(TokenTypes.ARRAY_DECLARATOR,
                (Token) ctx.LBRACK().getPayload());
        final JavaLanguageParser.ExpressionContext expression = ctx.expression();
        final TerminalNode rbrack = ctx.RBRACK();
        // child[0] is LBRACK
        for (int i = 1; i < ctx.children.size(); i++) {
            if (ctx.children.get(i) == rbrack) {
                arrayDeclarator.addChild(create(rbrack));
            }
            else if (ctx.children.get(i) == expression) {
                // Handle '[8]', etc.
                arrayDeclarator.addChild(visit(expression));
            }
            else {
                addLastSibling(arrayDeclarator, visit(ctx.children.get(i)));
            }
        }
        return arrayDeclarator;
    }

    @Override
    public DetailAstImpl visitBracketsWithExp(JavaLanguageParser.BracketsWithExpContext ctx) {
        final DetailAstImpl dummyRoot = new DetailAstImpl();
        dummyRoot.addChild(visit(ctx.annotations()));
        final DetailAstImpl arrayDeclarator =
                create(TokenTypes.ARRAY_DECLARATOR, (Token) ctx.LBRACK().getPayload());
        arrayDeclarator.addChild(visit(ctx.expression()));
        arrayDeclarator.addChild(create(ctx.stop));
        dummyRoot.addChild(arrayDeclarator);
        return dummyRoot.getFirstChild();
    }

    @Override
    public DetailAstImpl visitClassCreatorRest(JavaLanguageParser.ClassCreatorRestContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitDiamond(JavaLanguageParser.DiamondContext ctx) {
        final DetailAstImpl typeArguments =
                createImaginary(TokenTypes.TYPE_ARGUMENTS);
        typeArguments.addChild(create(TokenTypes.GENERIC_START,
                (Token) ctx.LT().getPayload()));
        typeArguments.addChild(create(TokenTypes.GENERIC_END,
                (Token) ctx.GT().getPayload()));
        return typeArguments;
    }

    @Override
    public DetailAstImpl visitTypeArgs(JavaLanguageParser.TypeArgsContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitNonWildcardDiamond(
            JavaLanguageParser.NonWildcardDiamondContext ctx) {
        final DetailAstImpl typeArguments =
                createImaginary(TokenTypes.TYPE_ARGUMENTS);
        typeArguments.addChild(create(TokenTypes.GENERIC_START,
                (Token) ctx.LT().getPayload()));
        typeArguments.addChild(create(TokenTypes.GENERIC_END,
                (Token) ctx.GT().getPayload()));
        return typeArguments;
    }

    @Override
    public DetailAstImpl visitNonWildcardTypeArguments(
            JavaLanguageParser.NonWildcardTypeArgumentsContext ctx) {
        final DetailAstImpl typeArguments = createImaginary(TokenTypes.TYPE_ARGUMENTS);
        typeArguments.addChild(create(TokenTypes.GENERIC_START, (Token) ctx.LT().getPayload()));
        typeArguments.addChild(visit(ctx.typeArgumentsTypeList()));
        typeArguments.addChild(create(TokenTypes.GENERIC_END, (Token) ctx.GT().getPayload()));
        return typeArguments;
    }

    @Override
    public DetailAstImpl visitTypeArgumentsTypeList(
            JavaLanguageParser.TypeArgumentsTypeListContext ctx) {
        final DetailAstImpl firstIdent = visit(ctx.typeType(0));
        final DetailAstImpl firstTypeArgument = createImaginary(TokenTypes.TYPE_ARGUMENT);
        firstTypeArgument.addChild(firstIdent);

        for (int i = 0; i < ctx.COMMA().size(); i++) {
            addLastSibling(firstTypeArgument, create(ctx.COMMA(i)));
            final DetailAstImpl ident = visit(ctx.typeType(i + 1));
            final DetailAstImpl typeArgument = createImaginary(TokenTypes.TYPE_ARGUMENT);
            typeArgument.addChild(ident);
            addLastSibling(firstTypeArgument, typeArgument);
        }
        return firstTypeArgument;
    }

    @Override
    public DetailAstImpl visitTypeList(JavaLanguageParser.TypeListContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitTypeType(JavaLanguageParser.TypeTypeContext ctx) {
        final DetailAstImpl type = createImaginary(TokenTypes.TYPE);
        processChildren(type, ctx.children);

        final DetailAstImpl returnTree;
        if (ctx.createImaginaryNode) {
            returnTree = type;
        }
        else {
            returnTree = type.getFirstChild();
        }
        return returnTree;
    }

    @Override
    public DetailAstImpl visitArrayDeclarator(JavaLanguageParser.ArrayDeclaratorContext ctx) {
        final DetailAstImpl arrayDeclarator = create(TokenTypes.ARRAY_DECLARATOR,
                (Token) ctx.LBRACK().getPayload());
        arrayDeclarator.addChild(create(ctx.RBRACK()));

        final DetailAstImpl returnTree;
        final DetailAstImpl annotations = visit(ctx.anno);
        if (annotations == null) {
            returnTree = arrayDeclarator;
        }
        else {
            returnTree = annotations;
            addLastSibling(returnTree, arrayDeclarator);
        }
        return returnTree;
    }

    @Override
    public DetailAstImpl visitPrimitiveType(JavaLanguageParser.PrimitiveTypeContext ctx) {
        return create(ctx.start);
    }

    @Override
    public DetailAstImpl visitTypeArguments(JavaLanguageParser.TypeArgumentsContext ctx) {
        final DetailAstImpl typeArguments = createImaginary(TokenTypes.TYPE_ARGUMENTS);
        typeArguments.addChild(create(TokenTypes.GENERIC_START, (Token) ctx.LT().getPayload()));
        // Exclude '<' and '>'
        processChildren(typeArguments, ctx.children.subList(1, ctx.children.size() - 1));
        typeArguments.addChild(create(TokenTypes.GENERIC_END, (Token) ctx.GT().getPayload()));
        return typeArguments;
    }

    @Override
    public DetailAstImpl visitSuperSuffixDot(JavaLanguageParser.SuperSuffixDotContext ctx) {
        final DetailAstImpl root;
        if (ctx.LPAREN() == null) {
            root = create(ctx.DOT());
            root.addChild(visit(ctx.id()));
        }
        else {
            root = create(TokenTypes.METHOD_CALL, (Token) ctx.LPAREN().getPayload());

            final DetailAstImpl dot = create(ctx.DOT());
            dot.addChild(visit(ctx.id()));
            root.addChild(dot);

            final DetailAstImpl expressionList = Optional.ofNullable(visit(ctx.expressionList()))
                    .orElseGet(() -> createImaginary(TokenTypes.ELIST));
            root.addChild(expressionList);

            root.addChild(create(ctx.RPAREN()));
        }

        return root;
    }

    @Override
    public DetailAstImpl visitArguments(JavaLanguageParser.ArgumentsContext ctx) {
        final DetailAstImpl lparen = create(ctx.LPAREN());

        // We always add an 'ELIST' node
        final DetailAstImpl expressionList = Optional.ofNullable(visit(ctx.expressionList()))
                .orElseGet(() -> createImaginary(TokenTypes.ELIST));
        addLastSibling(lparen, expressionList);
        addLastSibling(lparen, create(ctx.RPAREN()));
        return lparen;
    }

    @Override
    public DetailAstImpl visitPattern(JavaLanguageParser.PatternContext ctx) {
        final JavaLanguageParser.InnerPatternContext innerPattern = ctx.innerPattern();
        final ParserRuleContext primaryPattern = innerPattern.primaryPattern();
        final ParserRuleContext recordPattern = innerPattern.recordPattern();
        final boolean isSimpleTypePattern = primaryPattern != null
                && primaryPattern.getChild(0) instanceof JavaLanguageParser.TypePatternContext;

        final DetailAstImpl pattern;

        if (recordPattern != null) {
            pattern = visit(recordPattern);
        }
        else if (isSimpleTypePattern) {
            // For simple type pattern like 'Integer i`, we do not add `PATTERN_DEF` parent
            pattern = visit(primaryPattern);
        }
        else {
            pattern = createImaginary(TokenTypes.PATTERN_DEF);
            pattern.addChild(visit(ctx.getChild(0)));
        }
        return pattern;
    }

    @Override
    public DetailAstImpl visitInnerPattern(JavaLanguageParser.InnerPatternContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitGuardedPattern(JavaLanguageParser.GuardedPatternContext ctx) {
        final DetailAstImpl guardAstNode = flattenedTree(ctx.guard());
        guardAstNode.addChild(visit(ctx.primaryPattern()));
        guardAstNode.addChild(visit(ctx.expr()));
        return guardAstNode;
    }

    @Override
    public DetailAstImpl visitParenPattern(JavaLanguageParser.ParenPatternContext ctx) {
        final DetailAstImpl lparen = create(ctx.LPAREN());
        final ParseTree innerPattern = ctx.getChild(1);
        lparen.addChild(visit(innerPattern));
        lparen.addChild(create(ctx.RPAREN()));
        return lparen;
    }

    @Override
    public DetailAstImpl visitRecordPatternDef(JavaLanguageParser.RecordPatternDefContext ctx) {
        return flattenedTree(ctx);
    }

    @Override
    public DetailAstImpl visitTypePattern(
            JavaLanguageParser.TypePatternContext ctx) {
        final DetailAstImpl type = visit(ctx.type);
        final DetailAstImpl patternVariableDef = createImaginary(TokenTypes.PATTERN_VARIABLE_DEF);
        patternVariableDef.addChild(createModifiers(ctx.mods));
        patternVariableDef.addChild(type);
        patternVariableDef.addChild(visit(ctx.id()));
        return patternVariableDef;
    }

    @Override
    public DetailAstImpl visitRecordPattern(JavaLanguageParser.RecordPatternContext ctx) {
        final DetailAstImpl recordPattern = createImaginary(TokenTypes.RECORD_PATTERN_DEF);
        recordPattern.addChild(createModifiers(ctx.mods));
        processChildren(recordPattern,
                ctx.children.subList(ctx.mods.size(), ctx.children.size()));
        return recordPattern;
    }

    @Override
    public DetailAstImpl visitRecordComponentPatternList(
            JavaLanguageParser.RecordComponentPatternListContext ctx) {
        final DetailAstImpl recordComponents =
                createImaginary(TokenTypes.RECORD_PATTERN_COMPONENTS);
        processChildren(recordComponents, ctx.children);
        return recordComponents;
    }

    @Override
    public DetailAstImpl visitPermittedSubclassesAndInterfaces(
            JavaLanguageParser.PermittedSubclassesAndInterfacesContext ctx) {
        final DetailAstImpl literalPermits =
                create(TokenTypes.PERMITS_CLAUSE, (Token) ctx.LITERAL_PERMITS().getPayload());
        // 'LITERAL_PERMITS' is child[0]
        processChildren(literalPermits, ctx.children.subList(1, ctx.children.size()));
        return literalPermits;
    }

    @Override
    public DetailAstImpl visitId(JavaLanguageParser.IdContext ctx) {
        return create(TokenTypes.IDENT, ctx.start);
    }

    /**
     * Builds the AST for a particular node, then returns a "flattened" tree
     * of siblings. This method should be used in rule contexts such as
     * {@code variableDeclarators}, where we have both terminals and non-terminals.
     *
     * @param ctx the ParserRuleContext to base tree on
     * @return flattened DetailAstImpl
     */
    private DetailAstImpl flattenedTree(ParserRuleContext ctx) {
        final DetailAstImpl dummyNode = new DetailAstImpl();
        processChildren(dummyNode, ctx.children);
        return dummyNode.getFirstChild();
    }

    /**
     * Adds all the children from the given ParseTree or JavaParserContext
     * list to the parent DetailAstImpl.
     *
     * @param parent the DetailAstImpl to add children to
     * @param children the list of children to add
     */
    private void processChildren(DetailAstImpl parent, List<? extends ParseTree> children) {
        children.forEach(child -> {
            if (child instanceof TerminalNode) {
                // Child is a token, create a new DetailAstImpl and add it to parent
                parent.addChild(create((TerminalNode) child));
            }
            else {
                // Child is another rule context; visit it, create token, and add to parent
                parent.addChild(visit(child));
            }
        });
    }

    /**
     * Create a DetailAstImpl from a given token and token type. This method
     * should be used for imaginary nodes only, i.e. 'OBJBLOCK -&gt; OBJBLOCK',
     * where the text on the RHS matches the text on the LHS.
     *
     * @param tokenType  the token type of this DetailAstImpl
     * @return new DetailAstImpl of given type
     */
    private static DetailAstImpl createImaginary(int tokenType) {
        final DetailAstImpl detailAst = new DetailAstImpl();
        detailAst.setType(tokenType);
        detailAst.setText(TokenUtil.getTokenName(tokenType));
        return detailAst;
    }

    /**
     * Create a DetailAstImpl from a given token and token type. This method
     * should be used for literal nodes only, i.e. 'PACKAGE_DEF -&gt; package'.
     *
     * @param tokenType the token type of this DetailAstImpl
     * @param startToken the first token that appears in this DetailAstImpl.
     * @return new DetailAstImpl of given type
     */
    private DetailAstImpl create(int tokenType, Token startToken) {
        final DetailAstImpl ast = create(startToken);
        ast.setType(tokenType);
        return ast;
    }

    /**
     * Create a DetailAstImpl from a given token. This method should be
     * used for terminal nodes, i.e. {@code LCURLY}, when we are building
     * an AST for a specific token, regardless of position.
     *
     * @param token the token to build the DetailAstImpl from
     * @return new DetailAstImpl of given type
     */
    private DetailAstImpl create(Token token) {
        final int tokenIndex = token.getTokenIndex();
        final List<Token> tokensToLeft =
                tokens.getHiddenTokensToLeft(tokenIndex, JavaLanguageLexer.COMMENTS);
        final List<Token> tokensToRight =
                tokens.getHiddenTokensToRight(tokenIndex, JavaLanguageLexer.COMMENTS);

        final DetailAstImpl detailAst = new DetailAstImpl();
        detailAst.initialize(token);
        if (tokensToLeft != null) {
            detailAst.setHiddenBefore(tokensToLeft);
        }
        if (tokensToRight != null) {
            detailAst.setHiddenAfter(tokensToRight);
        }
        return detailAst;
    }

    /**
     * Create a DetailAstImpl from a given TerminalNode. This method should be
     * used for terminal nodes, i.e. {@code @}.
     *
     * @param node the TerminalNode to build the DetailAstImpl from
     * @return new DetailAstImpl of given type
     */
    private DetailAstImpl create(TerminalNode node) {
        return create((Token) node.getPayload());
    }

    /**
     * Creates a type declaration DetailAstImpl from a given rule context.
     *
     * @param ctx ParserRuleContext we are in
     * @param type the type declaration to create
     * @param modifierList respective modifiers
     * @return type declaration DetailAstImpl
     */
    private DetailAstImpl createTypeDeclaration(ParserRuleContext ctx, int type,
                                                List<? extends ParseTree> modifierList) {
        final DetailAstImpl typeDeclaration = createImaginary(type);
        typeDeclaration.addChild(createModifiers(modifierList));
        processChildren(typeDeclaration, ctx.children);
        return typeDeclaration;
    }

    /**
     * Builds the modifiers AST.
     *
     * @param modifierList the list of modifier contexts
     * @return "MODIFIERS" ast
     */
    private DetailAstImpl createModifiers(List<? extends ParseTree> modifierList) {
        final DetailAstImpl mods = createImaginary(TokenTypes.MODIFIERS);
        processChildren(mods, modifierList);
        return mods;
    }

    /**
     * Add new sibling to the end of existing siblings.
     *
     * @param self DetailAstImpl to add last sibling to
     * @param sibling DetailAstImpl sibling to add
     */
    private static void addLastSibling(DetailAstImpl self, DetailAstImpl sibling) {
        DetailAstImpl nextSibling = self;
        if (nextSibling != null) {
            while (nextSibling.getNextSibling() != null) {
                nextSibling = nextSibling.getNextSibling();
            }
            nextSibling.setNextSibling(sibling);
        }
    }

    @Override
    public DetailAstImpl visit(ParseTree tree) {
        DetailAstImpl ast = null;
        if (tree != null) {
            ast = tree.accept(this);
        }
        return ast;
    }

    /**
     * Builds an expression node. This is used to build the root of an expression with
     * an imaginary {@code EXPR} node.
     *
     * @param exprNode expression to build node for
     * @return expression DetailAstImpl node
     */
    private DetailAstImpl buildExpressionNode(ParseTree exprNode) {
        final DetailAstImpl expression = visit(exprNode);

        final DetailAstImpl exprRoot;
        if (TokenUtil.isOfType(expression, EXPRESSIONS_WITH_NO_EXPR_ROOT)) {
            exprRoot = expression;
        }
        else {
            // create imaginary 'EXPR' node as root of expression
            exprRoot = createImaginary(TokenTypes.EXPR);
            exprRoot.addChild(expression);
        }
        return exprRoot;
    }

    /**
     * Used to swap and organize DetailAstImpl subtrees.
     */
    private static final class DetailAstPair {

        /** The root DetailAstImpl of this pair. */
        private DetailAstImpl root;

        /** The child (potentially with siblings) of this pair. */
        private DetailAstImpl child;

        /**
         * Moves child reference to the last child.
         */
        private void advanceChildToEnd() {
            while (child.getNextSibling() != null) {
                child = child.getNextSibling();
            }
        }

        /**
         * Returns the root node.
         *
         * @return the root node
         */
        private DetailAstImpl getRoot() {
            return root;
        }

        /**
         * This method is used to replace the {@code ^} (set as root node) ANTLR2
         * operator.
         *
         * @param pair the DetailAstPair to use for swapping nodes
         * @param ast the new root
         */
        private static void makeAstRoot(DetailAstPair pair, DetailAstImpl ast) {
            ast.addChild(pair.root);
            pair.child = pair.root;
            pair.advanceChildToEnd();
            pair.root = ast;
        }

        /**
         * Adds a child (or new root) to the given DetailAstPair.
         *
         * @param pair the DetailAstPair to add child to
         * @param ast the child to add
         */
        private static void addAstChild(DetailAstPair pair, DetailAstImpl ast) {
            if (ast != null) {
                if (pair.root == null) {
                    pair.root = ast;
                }
                else {
                    pair.child.setNextSibling(ast);
                }
                pair.child = ast;
            }
        }
    }
}
