001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2016 the original author or authors.
004//
005// This library is free software; you can redistribute it and/or
006// modify it under the terms of the GNU Lesser General Public
007// License as published by the Free Software Foundation; either
008// version 2.1 of the License, or (at your option) any later version.
009//
010// This library is distributed in the hope that it will be useful,
011// but WITHOUT ANY WARRANTY; without even the implied warranty of
012// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013// Lesser General Public License for more details.
014//
015// You should have received a copy of the GNU Lesser General Public
016// License along with this library; if not, write to the Free Software
017// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
018////////////////////////////////////////////////////////////////////////////////
019
020package com.puppycrawl.tools.checkstyle.checks.imports;
021
022import java.util.Locale;
023import java.util.regex.Matcher;
024import java.util.regex.Pattern;
025
026import org.apache.commons.beanutils.ConversionException;
027
028import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
029import com.puppycrawl.tools.checkstyle.api.DetailAST;
030import com.puppycrawl.tools.checkstyle.api.FullIdent;
031import com.puppycrawl.tools.checkstyle.api.TokenTypes;
032import com.puppycrawl.tools.checkstyle.utils.CommonUtils;
033
034/**
035 * <ul>
036 * <li>groups imports: ensures that groups of imports come in a specific order
037 * (e.g., java. comes first, javax. comes second, then everything else)</li>
038 * <li>adds a separation between groups : ensures that a blank line sit between
039 * each group</li>
040 * <li>sorts imports inside each group: ensures that imports within each group
041 * are in lexicographic order</li>
042 * <li>sorts according to case: ensures that the comparison between import is
043 * case sensitive</li>
044 * <li>groups static imports: ensures that static imports are at the top (or the
045 * bottom) of all the imports, or above (or under) each group, or are treated
046 * like non static imports (@see {@link ImportOrderOption}</li>
047 * </ul>
048 *
049 * <pre>
050 * Properties:
051 * </pre>
052 * <table summary="Properties" border="1">
053 *   <tr><th>name</th><th>Description</th><th>type</th><th>default value</th></tr>
054 *   <tr><td>option</td><td>policy on the relative order between regular imports and static
055 *       imports</td><td>{@link ImportOrderOption}</td><td>under</td></tr>
056 *   <tr><td>groups</td><td>list of imports groups (every group identified either by a common
057 *       prefix string, or by a regular expression enclosed in forward slashes (e.g. /regexp/)</td>
058 *       <td>list of strings</td><td>empty list</td></tr>
059 *   <tr><td>ordered</td><td>whether imports within group should be sorted</td>
060 *       <td>Boolean</td><td>true</td></tr>
061 *   <tr><td>separated</td><td>whether imports groups should be separated by, at least,
062 *       one blank line</td><td>Boolean</td><td>false</td></tr>
063 *   <tr><td>caseSensitive</td><td>whether string comparison should be case sensitive or not.
064 *       Case sensitive sorting is in ASCII sort order</td><td>Boolean</td><td>true</td></tr>
065 *   <tr><td>sortStaticImportsAlphabetically</td><td>whether static imports grouped by top or
066 *       bottom option are sorted alphabetically or not</td><td>Boolean</td><td>false</td></tr>
067 *   <tr><td>useContainerOrderingForStatic</td><td>whether to use container ordering
068 *       (Eclipse IDE term) for static imports or not</td><td>Boolean</td><td>false</td></tr>
069 * </table>
070 *
071 * <p>
072 * Example:
073 * </p>
074 * <p>To configure the check so that it matches default Eclipse formatter configuration
075 *    (tested on Kepler, Luna and Mars):</p>
076 * <ul>
077 *     <li>group of static imports is on the top</li>
078 *     <li>groups of non-static imports: &quot;java&quot; then &quot;javax&quot;
079 *         packages first, then &quot;org&quot; and then all other imports</li>
080 *     <li>imports will be sorted in the groups</li>
081 *     <li>groups are separated by, at least, one blank line</li>
082 * </ul>
083 *
084 * <pre>
085 * &lt;module name=&quot;ImportOrder&quot;&gt;
086 *    &lt;property name=&quot;groups&quot; value=&quot;/^javax?\./,org&quot;/&gt;
087 *    &lt;property name=&quot;ordered&quot; value=&quot;true&quot;/&gt;
088 *    &lt;property name=&quot;separated&quot; value=&quot;true&quot;/&gt;
089 *    &lt;property name=&quot;option&quot; value=&quot;above&quot;/&gt;
090 *    &lt;property name=&quot;sortStaticImportsAlphabetically&quot; value=&quot;true&quot;/&gt;
091 * &lt;/module&gt;
092 * </pre>
093 *
094 * <p>To configure the check so that it matches default IntelliJ IDEA formatter configuration
095 *    (tested on v14):</p>
096 * <ul>
097 *     <li>group of static imports is on the bottom</li>
098 *     <li>groups of non-static imports: all imports except of &quot;javax&quot; and
099 *         &quot;java&quot;, then &quot;javax&quot; and &quot;java&quot;</li>
100 *     <li>imports will be sorted in the groups</li>
101 *     <li>groups are separated by, at least, one blank line</li>
102 * </ul>
103 *
104 *         <p>
105 *         Note: &quot;separated&quot; option is disabled because IDEA default has blank line
106 *         between &quot;java&quot; and static imports, and no blank line between
107 *         &quot;javax&quot; and &quot;java&quot;
108 *         </p>
109 *
110 * <pre>
111 * &lt;module name=&quot;ImportOrder&quot;&gt;
112 *     &lt;property name=&quot;groups&quot; value=&quot;*,javax,java&quot;/&gt;
113 *     &lt;property name=&quot;ordered&quot; value=&quot;true&quot;/&gt;
114 *     &lt;property name=&quot;separated&quot; value=&quot;false&quot;/&gt;
115 *     &lt;property name=&quot;option&quot; value=&quot;bottom&quot;/&gt;
116 *     &lt;property name=&quot;sortStaticImportsAlphabetically&quot; value=&quot;true&quot;/&gt;
117 * &lt;/module&gt;
118 * </pre>
119 *
120 * <p>To configure the check so that it matches default NetBeans formatter configuration
121 *    (tested on v8):</p>
122 * <ul>
123 *     <li>groups of non-static imports are not defined, all imports will be sorted
124 *         as a one group</li>
125 *     <li>static imports are not separated, they will be sorted along with other imports</li>
126 * </ul>
127 *
128 * <pre>
129 * &lt;module name=&quot;ImportOrder&quot;&gt;
130 *     &lt;property name=&quot;option&quot; value=&quot;inflow&quot;/&gt;
131 * &lt;/module&gt;
132 * </pre>
133 *
134 * <p>
135 * Group descriptions enclosed in slashes are interpreted as regular
136 * expressions. If multiple groups match, the one matching a longer
137 * substring of the imported name will take precedence, with ties
138 * broken first in favor of earlier matches and finally in favor of
139 * the first matching group.
140 * </p>
141 *
142 * <p>
143 * There is always a wildcard group to which everything not in a named group
144 * belongs. If an import does not match a named group, the group belongs to
145 * this wildcard group. The wildcard group position can be specified using the
146 * {@code *} character.
147 * </p>
148 *
149 * <p>Check also has on option making it more flexible:
150 * <b>sortStaticImportsAlphabetically</b> - sets whether static imports grouped by
151 * <b>top</b> or <b>bottom</b> option should be sorted alphabetically or
152 * not, default value is <b>false</b>. It is applied to static imports grouped
153 * with <b>top</b> or <b>bottom</b> options.<br>
154 * This option is helping in reconciling of this Check and other tools like
155 * Eclipse's Organize Imports feature.
156 * </p>
157 * <p>
158 * To configure the Check allows static imports grouped to the <b>top</b>
159 * being sorted alphabetically:
160 * </p>
161 *
162 * <pre>
163 * {@code
164 * import static java.lang.Math.abs;
165 * import static org.abego.treelayout.Configuration.AlignmentInLevel; // OK, alphabetical order
166 *
167 * import org.abego.*;
168 *
169 * import java.util.Set;
170 *
171 * public class SomeClass { ... }
172 * }
173 * </pre>
174 *
175 *
176 * @author Bill Schneider
177 * @author o_sukhodolsky
178 * @author David DIDIER
179 * @author Steve McKay
180 * @author <a href="mailto:nesterenko-aleksey@list.ru">Aleksey Nesterenko</a>
181 * @author Andrei Selkin
182 */
183public class ImportOrderCheck
184    extends AbstractCheck {
185
186    /**
187     * A key is pointing to the warning message text in "messages.properties"
188     * file.
189     */
190    public static final String MSG_SEPARATION = "import.separation";
191
192    /**
193     * A key is pointing to the warning message text in "messages.properties"
194     * file.
195     */
196    public static final String MSG_ORDERING = "import.ordering";
197
198    /** The special wildcard that catches all remaining groups. */
199    private static final String WILDCARD_GROUP_NAME = "*";
200
201    /** Empty array of pattern type needed to initialize check. */
202    private static final Pattern[] EMPTY_PATTERN_ARRAY = new Pattern[0];
203
204    /** List of import groups specified by the user. */
205    private Pattern[] groups = EMPTY_PATTERN_ARRAY;
206    /** Require imports in group be separated. */
207    private boolean separated;
208    /** Require imports in group. */
209    private boolean ordered = true;
210    /** Should comparison be case sensitive. */
211    private boolean caseSensitive = true;
212
213    /** Last imported group. */
214    private int lastGroup;
215    /** Line number of last import. */
216    private int lastImportLine;
217    /** Name of last import. */
218    private String lastImport;
219    /** If last import was static. */
220    private boolean lastImportStatic;
221    /** Whether there was any imports. */
222    private boolean beforeFirstImport;
223    /** Whether static imports should be sorted alphabetically or not. */
224    private boolean sortStaticImportsAlphabetically;
225    /** Whether to use container ordering (Eclipse IDE term) for static imports or not. */
226    private boolean useContainerOrderingForStatic;
227
228    /** The policy to enforce. */
229    private ImportOrderOption option = ImportOrderOption.UNDER;
230
231    /**
232     * Set the option to enforce.
233     * @param optionStr string to decode option from
234     * @throws ConversionException if unable to decode
235     */
236    public void setOption(String optionStr) {
237        try {
238            option = ImportOrderOption.valueOf(optionStr.trim().toUpperCase(Locale.ENGLISH));
239        }
240        catch (IllegalArgumentException iae) {
241            throw new ConversionException("unable to parse " + optionStr, iae);
242        }
243    }
244
245    /**
246     * Sets the list of package groups and the order they should occur in the
247     * file.
248     *
249     * @param packageGroups a comma-separated list of package names/prefixes.
250     */
251    public void setGroups(String... packageGroups) {
252        groups = new Pattern[packageGroups.length];
253
254        for (int i = 0; i < packageGroups.length; i++) {
255            String pkg = packageGroups[i];
256            final StringBuilder pkgBuilder = new StringBuilder(pkg);
257            final Pattern grp;
258
259            // if the pkg name is the wildcard, make it match zero chars
260            // from any name, so it will always be used as last resort.
261            if (WILDCARD_GROUP_NAME.equals(pkg)) {
262                // matches any package
263                grp = Pattern.compile("");
264            }
265            else if (CommonUtils.startsWithChar(pkg, '/')) {
266                if (!CommonUtils.endsWithChar(pkg, '/')) {
267                    throw new IllegalArgumentException("Invalid group");
268                }
269                pkg = pkg.substring(1, pkg.length() - 1);
270                grp = Pattern.compile(pkg);
271            }
272            else {
273                if (!CommonUtils.endsWithChar(pkg, '.')) {
274                    pkgBuilder.append('.');
275                }
276                grp = Pattern.compile("^" + Pattern.quote(pkgBuilder.toString()));
277            }
278
279            groups[i] = grp;
280        }
281    }
282
283    /**
284     * Sets whether or not imports should be ordered within any one group of
285     * imports.
286     *
287     * @param ordered
288     *            whether lexicographic ordering of imports within a group
289     *            required or not.
290     */
291    public void setOrdered(boolean ordered) {
292        this.ordered = ordered;
293    }
294
295    /**
296     * Sets whether or not groups of imports must be separated from one another
297     * by at least one blank line.
298     *
299     * @param separated
300     *            whether groups should be separated by oen blank line.
301     */
302    public void setSeparated(boolean separated) {
303        this.separated = separated;
304    }
305
306    /**
307     * Sets whether string comparison should be case sensitive or not.
308     *
309     * @param caseSensitive
310     *            whether string comparison should be case sensitive.
311     */
312    public void setCaseSensitive(boolean caseSensitive) {
313        this.caseSensitive = caseSensitive;
314    }
315
316    /**
317     * Sets whether static imports (when grouped using 'top' and 'bottom' option)
318     * are sorted alphabetically or according to the package groupings.
319     * @param sortAlphabetically true or false.
320     */
321    public void setSortStaticImportsAlphabetically(boolean sortAlphabetically) {
322        sortStaticImportsAlphabetically = sortAlphabetically;
323    }
324
325    /**
326     * Sets whether to use container ordering (Eclipse IDE term) for static imports or not.
327     * @param useContainerOrdering whether to use container ordering for static imports or not.
328     */
329    public void setUseContainerOrderingForStatic(boolean useContainerOrdering) {
330        useContainerOrderingForStatic = useContainerOrdering;
331    }
332
333    @Override
334    public int[] getDefaultTokens() {
335        return getAcceptableTokens();
336    }
337
338    @Override
339    public int[] getAcceptableTokens() {
340        return new int[] {TokenTypes.IMPORT, TokenTypes.STATIC_IMPORT};
341    }
342
343    @Override
344    public int[] getRequiredTokens() {
345        return new int[] {TokenTypes.IMPORT};
346    }
347
348    @Override
349    public void beginTree(DetailAST rootAST) {
350        lastGroup = Integer.MIN_VALUE;
351        lastImportLine = Integer.MIN_VALUE;
352        lastImport = "";
353        lastImportStatic = false;
354        beforeFirstImport = true;
355    }
356
357    @Override
358    public void visitToken(DetailAST ast) {
359        final FullIdent ident;
360        final boolean isStatic;
361
362        if (ast.getType() == TokenTypes.IMPORT) {
363            ident = FullIdent.createFullIdentBelow(ast);
364            isStatic = false;
365        }
366        else {
367            ident = FullIdent.createFullIdent(ast.getFirstChild()
368                    .getNextSibling());
369            isStatic = true;
370        }
371
372        final boolean isStaticAndNotLastImport = isStatic && !lastImportStatic;
373        final boolean isLastImportAndNonStatic = lastImportStatic && !isStatic;
374
375        // using set of IF instead of SWITCH to analyze Enum options to satisfy coverage.
376        // https://github.com/checkstyle/checkstyle/issues/1387
377        if (option == ImportOrderOption.TOP) {
378
379            if (isLastImportAndNonStatic) {
380                lastGroup = Integer.MIN_VALUE;
381                lastImport = "";
382            }
383            doVisitToken(ident, isStatic, isStaticAndNotLastImport);
384
385        }
386        else if (option == ImportOrderOption.BOTTOM) {
387
388            if (isStaticAndNotLastImport) {
389                lastGroup = Integer.MIN_VALUE;
390                lastImport = "";
391            }
392            doVisitToken(ident, isStatic, isLastImportAndNonStatic);
393
394        }
395        else if (option == ImportOrderOption.ABOVE) {
396            // previous non-static but current is static
397            doVisitToken(ident, isStatic, isStaticAndNotLastImport);
398
399        }
400        else if (option == ImportOrderOption.UNDER) {
401            doVisitToken(ident, isStatic, isLastImportAndNonStatic);
402
403        }
404        else if (option == ImportOrderOption.INFLOW) {
405            // "previous" argument is useless here
406            doVisitToken(ident, isStatic, true);
407
408        }
409        else {
410            throw new IllegalStateException(
411                    "Unexpected option for static imports: " + option);
412        }
413
414        lastImportLine = ast.findFirstToken(TokenTypes.SEMI).getLineNo();
415        lastImportStatic = isStatic;
416        beforeFirstImport = false;
417    }
418
419    /**
420     * Shares processing...
421     *
422     * @param ident the import to process.
423     * @param isStatic whether the token is static or not.
424     * @param previous previous non-static but current is static (above), or
425     *                  previous static but current is non-static (under).
426     */
427    private void doVisitToken(FullIdent ident, boolean isStatic,
428            boolean previous) {
429        final String name = ident.getText();
430        final int groupIdx = getGroupNumber(name);
431        final int line = ident.getLineNo();
432
433        if (groupIdx == lastGroup
434            || !beforeFirstImport && isAlphabeticallySortableStaticImport(isStatic)) {
435            doVisitTokenInSameGroup(isStatic, previous, name, line);
436        }
437        else if (groupIdx > lastGroup) {
438            if (!beforeFirstImport && separated && line - lastImportLine < 2) {
439                log(line, MSG_SEPARATION, name);
440            }
441        }
442        else {
443            log(line, MSG_ORDERING, name);
444        }
445
446        lastGroup = groupIdx;
447        lastImport = name;
448    }
449
450    /**
451     * Checks whether static imports grouped by <b>top</b> or <b>bottom</b> option
452     * are sorted alphabetically or not.
453     * @param isStatic if current import is static.
454     * @return true if static imports should be sorted alphabetically.
455     */
456    private boolean isAlphabeticallySortableStaticImport(boolean isStatic) {
457        return isStatic && sortStaticImportsAlphabetically
458                && (option == ImportOrderOption.TOP
459                    || option == ImportOrderOption.BOTTOM);
460    }
461
462    /**
463     * Shares processing...
464     *
465     * @param isStatic whether the token is static or not.
466     * @param previous previous non-static but current is static (above), or
467     *     previous static but current is non-static (under).
468     * @param name the name of the current import.
469     * @param line the line of the current import.
470     */
471    private void doVisitTokenInSameGroup(boolean isStatic,
472            boolean previous, String name, int line) {
473        if (ordered) {
474            if (option == ImportOrderOption.INFLOW) {
475                if (isWrongOrder(name, isStatic)) {
476                    log(line, MSG_ORDERING, name);
477                }
478            }
479            else {
480                final boolean shouldFireError =
481                    // previous non-static but current is static (above)
482                    // or
483                    // previous static but current is non-static (under)
484                    previous
485                        ||
486                        // current and previous static or current and
487                        // previous non-static
488                        lastImportStatic == isStatic
489                    && isWrongOrder(name, isStatic);
490
491                if (shouldFireError) {
492                    log(line, MSG_ORDERING, name);
493                }
494            }
495        }
496    }
497
498    /**
499     * Checks whether import name is in wrong order.
500     * @param name import name.
501     * @param isStatic whether it is a static import name.
502     * @return true if import name is in wrong order.
503     */
504    private boolean isWrongOrder(String name, boolean isStatic) {
505        final boolean result;
506        if (isStatic && useContainerOrderingForStatic) {
507            result = compareContainerOrder(lastImport, name, caseSensitive) > 0;
508        }
509        else {
510            // out of lexicographic order
511            result = compare(lastImport, name, caseSensitive) > 0;
512        }
513        return result;
514    }
515
516    /**
517     * Compares two import strings.
518     * We first compare the container of the static import, container being the type enclosing
519     * the static element being imported. When this returns 0, we compare the qualified
520     * import name. For e.g. this is what is considered to be container names:
521     * <p>
522     * import static HttpConstants.COLON     => HttpConstants
523     * import static HttpHeaders.addHeader   => HttpHeaders
524     * import static HttpHeaders.setHeader   => HttpHeaders
525     * import static HttpHeaders.Names.DATE  => HttpHeaders.Names
526     * </p>
527     * <p>
528     * According to this logic, HttpHeaders.Names would come after HttpHeaders.
529     *
530     * For more details, see <a href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=473629#c3">
531     * static imports comparison method</a> in Eclipse.
532     * </p>
533     *
534     * @param importName1 first import name.
535     * @param importName2 second import name.
536     * @param caseSensitive whether the comparison of fully qualified import names is case
537     *                      sensitive.
538     * @return the value {@code 0} if str1 is equal to str2; a value
539     *         less than {@code 0} if str is less than the str2 (container order
540     *         or lexicographical); and a value greater than {@code 0} if str1 is greater than str2
541     *         (container order or lexicographically).
542     */
543    private static int compareContainerOrder(String importName1, String importName2,
544                                             boolean caseSensitive) {
545        final String container1 = getImportContainer(importName1);
546        final String container2 = getImportContainer(importName2);
547        final int compareContainersOrderResult;
548        if (caseSensitive) {
549            compareContainersOrderResult = container1.compareTo(container2);
550        }
551        else {
552            compareContainersOrderResult = container1.compareToIgnoreCase(container2);
553        }
554        final int result;
555        if (compareContainersOrderResult == 0) {
556            result = compare(importName1, importName2, caseSensitive);
557        }
558        else {
559            result = compareContainersOrderResult;
560        }
561        return result;
562    }
563
564    /**
565     * Extracts import container name from fully qualified import name.
566     * An import container name is the type which encloses the static element being imported.
567     * For example, HttpConstants, HttpHeaders, HttpHeaders.Names are import container names:
568     * <p>
569     * import static HttpConstants.COLON     => HttpConstants
570     * import static HttpHeaders.addHeader   => HttpHeaders
571     * import static HttpHeaders.setHeader   => HttpHeaders
572     * import static HttpHeaders.Names.DATE  => HttpHeaders.Names
573     * </p>
574     * @param qualifiedImportName fully qualified import name.
575     * @return import container name.
576     */
577    private static String getImportContainer(String qualifiedImportName) {
578        final int lastDotIndex = qualifiedImportName.lastIndexOf('.');
579        return qualifiedImportName.substring(0, lastDotIndex);
580    }
581
582    /**
583     * Finds out what group the specified import belongs to.
584     *
585     * @param name the import name to find.
586     * @return group number for given import name.
587     */
588    private int getGroupNumber(String name) {
589        int bestIndex = groups.length;
590        int bestLength = -1;
591        int bestPos = 0;
592
593        // find out what group this belongs in
594        // loop over groups and get index
595        for (int i = 0; i < groups.length; i++) {
596            final Matcher matcher = groups[i].matcher(name);
597            while (matcher.find()) {
598                final int length = matcher.end() - matcher.start();
599                if (length > bestLength
600                    || length == bestLength && matcher.start() < bestPos) {
601                    bestIndex = i;
602                    bestLength = length;
603                    bestPos = matcher.start();
604                }
605            }
606        }
607
608        return bestIndex;
609    }
610
611    /**
612     * Compares two strings.
613     *
614     * @param string1
615     *            the first string.
616     * @param string2
617     *            the second string.
618     * @param caseSensitive
619     *            whether the comparison is case sensitive.
620     * @return the value {@code 0} if string1 is equal to string2; a value
621     *         less than {@code 0} if string1 is lexicographically less
622     *         than the string2; and a value greater than {@code 0} if
623     *         string1 is lexicographically greater than string2.
624     */
625    private static int compare(String string1, String string2,
626            boolean caseSensitive) {
627        final int result;
628        if (caseSensitive) {
629            result = string1.compareTo(string2);
630        }
631        else {
632            result = string1.compareToIgnoreCase(string2);
633        }
634
635        return result;
636    }
637}