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