001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2015 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.Check;
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 * </table>
068 *
069 * <p>
070 * Example:
071 * </p>
072 * <p>To configure the check so that it matches default Eclipse formatter configuration
073 *    (tested on Kepler, Luna and Mars):</p>
074 * <ul>
075 *     <li>group of static imports is on the top</li>
076 *     <li>groups of non-static imports: &quot;java&quot; then &quot;javax&quot;
077 *         packages first, then &quot;org&quot; and then all other imports</li>
078 *     <li>imports will be sorted in the groups</li>
079 *     <li>groups are separated by, at least, one blank line</li>
080 * </ul>
081 *
082 * <pre>
083 * &lt;module name=&quot;ImportOrder&quot;&gt;
084 *    &lt;property name=&quot;groups&quot; value=&quot;/^javax?\./,org&quot;/&gt;
085 *    &lt;property name=&quot;ordered&quot; value=&quot;true&quot;/&gt;
086 *    &lt;property name=&quot;separated&quot; value=&quot;true&quot;/&gt;
087 *    &lt;property name=&quot;option&quot; value=&quot;above&quot;/&gt;
088 *    &lt;property name=&quot;sortStaticImportsAlphabetically&quot; value=&quot;true&quot;/&gt;
089 * &lt;/module&gt;
090 * </pre>
091 *
092 * <p>To configure the check so that it matches default IntelliJ IDEA formatter configuration
093 *    (tested on v14):</p>
094 * <ul>
095 *     <li>group of static imports is on the bottom</li>
096 *     <li>groups of non-static imports: all imports except of &quot;javax&quot; and
097 *         &quot;java&quot;, then &quot;javax&quot; and &quot;java&quot;</li>
098 *     <li>imports will be sorted in the groups</li>
099 *     <li>groups are separated by, at least, one blank line</li>
100 * </ul>
101 *
102 *         <p>
103 *         Note: &quot;separated&quot; option is disabled because IDEA default has blank line
104 *         between &quot;java&quot; and static imports, and no blank line between
105 *         &quot;javax&quot; and &quot;java&quot;
106 *         </p>
107 *
108 * <pre>
109 * &lt;module name=&quot;ImportOrder&quot;&gt;
110 *     &lt;property name=&quot;groups&quot; value=&quot;*,javax,java&quot;/&gt;
111 *     &lt;property name=&quot;ordered&quot; value=&quot;true&quot;/&gt;
112 *     &lt;property name=&quot;separated&quot; value=&quot;false&quot;/&gt;
113 *     &lt;property name=&quot;option&quot; value=&quot;bottom&quot;/&gt;
114 *     &lt;property name=&quot;sortStaticImportsAlphabetically&quot; value=&quot;true&quot;/&gt;
115 * &lt;/module&gt;
116 * </pre>
117 *
118 * <p>To configure the check so that it matches default NetBeans formatter configuration
119 *    (tested on v8):</p>
120 * <ul>
121 *     <li>groups of non-static imports are not defined, all imports will be sorted
122 *         as a one group</li>
123 *     <li>static imports are not separated, they will be sorted along with other imports</li>
124 * </ul>
125 *
126 * <pre>
127 * &lt;module name=&quot;ImportOrder&quot;&gt;
128 *     &lt;property name=&quot;option&quot; value=&quot;inflow&quot;/&gt;
129 * &lt;/module&gt;
130 * </pre>
131 *
132 * <p>
133 * Group descriptions enclosed in slashes are interpreted as regular
134 * expressions. If multiple groups match, the one matching a longer
135 * substring of the imported name will take precedence, with ties
136 * broken first in favor of earlier matches and finally in favor of
137 * the first matching group.
138 * </p>
139 *
140 * <p>
141 * There is always a wildcard group to which everything not in a named group
142 * belongs. If an import does not match a named group, the group belongs to
143 * this wildcard group. The wildcard group position can be specified using the
144 * {@code *} character.
145 * </p>
146 *
147 * <p>Check also has on option making it more flexible:
148 * <b>sortStaticImportsAlphabetically</b> - sets whether static imports grouped by
149 * <b>top</b> or <b>bottom</b> option should be sorted alphabetically or
150 * not, default value is <b>false</b>. It is applied to static imports grouped
151 * with <b>top</b> or <b>bottom</b> options.<br>
152 * This option is helping in reconciling of this Check and other tools like
153 * Eclipse's Organize Imports feature.
154 * </p>
155 * <p>
156 * To configure the Check allows static imports grouped to the <b>top</b>
157 * being sorted alphabetically:
158 * </p>
159 *
160 * <pre>
161 * {@code
162 * import static java.lang.Math.abs;
163 * import static org.abego.treelayout.Configuration.AlignmentInLevel; // OK, alphabetical order
164 *
165 * import org.abego.*;
166 *
167 * import java.util.Set;
168 *
169 * public class SomeClass { ... }
170 * }
171 * </pre>
172 *
173 *
174 * @author Bill Schneider
175 * @author o_sukhodolsky
176 * @author David DIDIER
177 * @author Steve McKay
178 * @author <a href="mailto:nesterenko-aleksey@list.ru">Aleksey Nesterenko</a>
179 */
180public class ImportOrderCheck
181    extends Check {
182
183    /**
184     * A key is pointing to the warning message text in "messages.properties"
185     * file.
186     */
187    public static final String MSG_SEPARATION = "import.separation";
188
189    /**
190     * A key is pointing to the warning message text in "messages.properties"
191     * file.
192     */
193    public static final String MSG_ORDERING = "import.ordering";
194
195    /** The special wildcard that catches all remaining groups. */
196    private static final String WILDCARD_GROUP_NAME = "*";
197
198    /** Empty array of pattern type needed to initialize check. */
199    private static final Pattern[] EMPTY_PATTERN_ARRAY = new Pattern[0];
200
201    /** List of import groups specified by the user. */
202    private Pattern[] groups = EMPTY_PATTERN_ARRAY;
203    /** Require imports in group be separated. */
204    private boolean separated;
205    /** Require imports in group. */
206    private boolean ordered = true;
207    /** Should comparison be case sensitive. */
208    private boolean caseSensitive = true;
209
210    /** Last imported group. */
211    private int lastGroup;
212    /** Line number of last import. */
213    private int lastImportLine;
214    /** Name of last import. */
215    private String lastImport;
216    /** If last import was static. */
217    private boolean lastImportStatic;
218    /** Whether there was any imports. */
219    private boolean beforeFirstImport;
220    /** Whether static imports should be sorted alphabetically or not. */
221    private boolean sortStaticImportsAlphabetically;
222
223    /** The policy to enforce. */
224    private ImportOrderOption option = ImportOrderOption.UNDER;
225
226    /**
227     * Set the option to enforce.
228     * @param optionStr string to decode option from
229     * @throws ConversionException if unable to decode
230     */
231    public void setOption(String optionStr) {
232        try {
233            option = ImportOrderOption.valueOf(optionStr.trim().toUpperCase(Locale.ENGLISH));
234        }
235        catch (IllegalArgumentException iae) {
236            throw new ConversionException("unable to parse " + optionStr, iae);
237        }
238    }
239
240    /**
241     * Gets option set.
242     * @return the {@code option} set
243     */
244    public ImportOrderOption getAbstractOption() {
245        // WARNING!! Do not rename this method to getOption(). It breaks
246        // BeanUtils, which will silently not call setOption. Very annoying!
247        return option;
248    }
249
250    /**
251     * Sets the list of package groups and the order they should occur in the
252     * file.
253     *
254     * @param packageGroups a comma-separated list of package names/prefixes.
255     */
256    public void setGroups(String... packageGroups) {
257        groups = new Pattern[packageGroups.length];
258
259        for (int i = 0; i < packageGroups.length; i++) {
260            String pkg = packageGroups[i];
261            final StringBuilder pkgBuilder = new StringBuilder(pkg);
262            Pattern grp;
263
264            // if the pkg name is the wildcard, make it match zero chars
265            // from any name, so it will always be used as last resort.
266            if (WILDCARD_GROUP_NAME.equals(pkg)) {
267                // matches any package
268                grp = Pattern.compile("");
269            }
270            else if (CommonUtils.startsWithChar(pkg, '/')) {
271                if (!CommonUtils.endsWithChar(pkg, '/')) {
272                    throw new IllegalArgumentException("Invalid group");
273                }
274                pkg = pkg.substring(1, pkg.length() - 1);
275                grp = Pattern.compile(pkg);
276            }
277            else {
278                if (!CommonUtils.endsWithChar(pkg, '.')) {
279                    pkgBuilder.append('.');
280                }
281                grp = Pattern.compile("^" + Pattern.quote(pkgBuilder.toString()));
282            }
283
284            groups[i] = grp;
285        }
286    }
287
288    /**
289     * Sets whether or not imports should be ordered within any one group of
290     * imports.
291     *
292     * @param ordered
293     *            whether lexicographic ordering of imports within a group
294     *            required or not.
295     */
296    public void setOrdered(boolean ordered) {
297        this.ordered = ordered;
298    }
299
300    /**
301     * Sets whether or not groups of imports must be separated from one another
302     * by at least one blank line.
303     *
304     * @param separated
305     *            whether groups should be separated by oen blank line.
306     */
307    public void setSeparated(boolean separated) {
308        this.separated = separated;
309    }
310
311    /**
312     * Sets whether string comparison should be case sensitive or not.
313     *
314     * @param caseSensitive
315     *            whether string comparison should be case sensitive.
316     */
317    public void setCaseSensitive(boolean caseSensitive) {
318        this.caseSensitive = caseSensitive;
319    }
320
321    /**
322     * Sets whether static imports (when grouped using 'top' and 'bottom' option)
323     * are sorted alphabetically or according to the package groupings.
324     * @param sortAlphabetically true or false.
325     */
326    public void setSortStaticImportsAlphabetically(boolean sortAlphabetically) {
327        sortStaticImportsAlphabetically = sortAlphabetically;
328    }
329
330    @Override
331    public int[] getDefaultTokens() {
332        return getAcceptableTokens();
333    }
334
335    @Override
336    public int[] getAcceptableTokens() {
337        return new int[] {TokenTypes.IMPORT, TokenTypes.STATIC_IMPORT};
338    }
339
340    @Override
341    public int[] getRequiredTokens() {
342        return new int[] {TokenTypes.IMPORT};
343    }
344
345    @Override
346    public void beginTree(DetailAST rootAST) {
347        lastGroup = Integer.MIN_VALUE;
348        lastImportLine = Integer.MIN_VALUE;
349        lastImport = "";
350        lastImportStatic = false;
351        beforeFirstImport = true;
352    }
353
354    @Override
355    public void visitToken(DetailAST ast) {
356        final FullIdent ident;
357        final boolean isStatic;
358
359        if (ast.getType() == TokenTypes.IMPORT) {
360            ident = FullIdent.createFullIdentBelow(ast);
361            isStatic = false;
362        }
363        else {
364            ident = FullIdent.createFullIdent(ast.getFirstChild()
365                    .getNextSibling());
366            isStatic = true;
367        }
368
369        final boolean isStaticAndNotLastImport = isStatic && !lastImportStatic;
370        final boolean isLastImportAndNonStatic = lastImportStatic && !isStatic;
371        final ImportOrderOption abstractOption = getAbstractOption();
372
373        // using set of IF instead of SWITCH to analyze Enum options to satisfy coverage.
374        // https://github.com/checkstyle/checkstyle/issues/1387
375        if (abstractOption == ImportOrderOption.TOP) {
376
377            if (isLastImportAndNonStatic) {
378                lastGroup = Integer.MIN_VALUE;
379                lastImport = "";
380            }
381            doVisitToken(ident, isStatic, isStaticAndNotLastImport);
382
383        }
384        else if (abstractOption == ImportOrderOption.BOTTOM) {
385
386            if (isStaticAndNotLastImport) {
387                lastGroup = Integer.MIN_VALUE;
388                lastImport = "";
389            }
390            doVisitToken(ident, isStatic, isLastImportAndNonStatic);
391
392        }
393        else if (abstractOption == ImportOrderOption.ABOVE) {
394            // previous non-static but current is static
395            doVisitToken(ident, isStatic, isStaticAndNotLastImport);
396
397        }
398        else if (abstractOption == ImportOrderOption.UNDER) {
399            doVisitToken(ident, isStatic, isLastImportAndNonStatic);
400
401        }
402        else if (abstractOption == ImportOrderOption.INFLOW) {
403            // "previous" argument is useless here
404            doVisitToken(ident, isStatic, true);
405
406        }
407        else {
408            throw new IllegalStateException(
409                    "Unexpected option for static imports: " + abstractOption);
410        }
411
412        lastImportLine = ast.findFirstToken(TokenTypes.SEMI).getLineNo();
413        lastImportStatic = isStatic;
414        beforeFirstImport = false;
415    }
416
417    /**
418     * Shares processing...
419     *
420     * @param ident the import to process.
421     * @param isStatic whether the token is static or not.
422     * @param previous previous non-static but current is static (above), or
423     *                  previous static but current is non-static (under).
424     */
425    private void doVisitToken(FullIdent ident, boolean isStatic,
426            boolean previous) {
427        final String name = ident.getText();
428        final int groupIdx = getGroupNumber(name);
429        final int line = ident.getLineNo();
430
431        if (!beforeFirstImport && isAlphabeticallySortableStaticImport(isStatic)
432                || groupIdx == lastGroup) {
433            doVisitTokenInSameGroup(isStatic, previous, name, line);
434        }
435        else if (groupIdx > lastGroup) {
436            if (!beforeFirstImport && separated && line - lastImportLine < 2) {
437                log(line, MSG_SEPARATION, name);
438            }
439        }
440        else {
441            log(line, MSG_ORDERING, name);
442        }
443
444        lastGroup = groupIdx;
445        lastImport = name;
446    }
447
448    /**
449     * Checks whether static imports grouped by <b>top</b> or <b>bottom</b> option
450     * are sorted alphabetically or not.
451     * @param isStatic if current import is static.
452     * @return true if static imports should be sorted alphabetically.
453     */
454    private boolean isAlphabeticallySortableStaticImport(boolean isStatic) {
455        return isStatic && sortStaticImportsAlphabetically
456                && (getAbstractOption() == ImportOrderOption.TOP
457                    || getAbstractOption() == ImportOrderOption.BOTTOM);
458    }
459
460    /**
461     * Shares processing...
462     *
463     * @param isStatic whether the token is static or not.
464     * @param previous previous non-static but current is static (above), or
465     *     previous static but current is non-static (under).
466     * @param name the name of the current import.
467     * @param line the line of the current import.
468     */
469    private void doVisitTokenInSameGroup(boolean isStatic,
470            boolean previous, String name, int line) {
471        if (!ordered) {
472            return;
473        }
474
475        if (getAbstractOption() == ImportOrderOption.INFLOW) {
476            // out of lexicographic order
477            if (compare(lastImport, name, caseSensitive) > 0) {
478                log(line, MSG_ORDERING, name);
479            }
480        }
481        else {
482            final boolean shouldFireError =
483                // current and previous static or current and
484                // previous non-static
485                !(lastImportStatic ^ isStatic)
486                &&
487                        // and out of lexicographic order
488                        compare(lastImport, name, caseSensitive) > 0
489                ||
490                // previous non-static but current is static (above)
491                // or
492                // previous static but current is non-static (under)
493                previous;
494
495            if (shouldFireError) {
496                log(line, MSG_ORDERING, name);
497            }
498        }
499    }
500
501    /**
502     * Finds out what group the specified import belongs to.
503     *
504     * @param name the import name to find.
505     * @return group number for given import name.
506     */
507    private int getGroupNumber(String name) {
508        int bestIndex = groups.length;
509        int bestLength = -1;
510        int bestPos = 0;
511
512        // find out what group this belongs in
513        // loop over groups and get index
514        for (int i = 0; i < groups.length; i++) {
515            final Matcher matcher = groups[i].matcher(name);
516            while (matcher.find()) {
517                final int length = matcher.end() - matcher.start();
518                if (length > bestLength
519                    || length == bestLength && matcher.start() < bestPos) {
520                    bestIndex = i;
521                    bestLength = length;
522                    bestPos = matcher.start();
523                }
524            }
525        }
526
527        return bestIndex;
528    }
529
530    /**
531     * Compares two strings.
532     *
533     * @param string1
534     *            the first string.
535     * @param string2
536     *            the second string.
537     * @param caseSensitive
538     *            whether the comparison is case sensitive.
539     * @return the value {@code 0} if string1 is equal to string2; a value
540     *         less than {@code 0} if string1 is lexicographically less
541     *         than the string2; and a value greater than {@code 0} if
542     *         string1 is lexicographically greater than string2.
543     */
544    private static int compare(String string1, String string2,
545            boolean caseSensitive) {
546        int result;
547        if (caseSensitive) {
548            result = string1.compareTo(string2);
549        }
550        else {
551            result = string1.compareToIgnoreCase(string2);
552        }
553
554        return result;
555    }
556}