Source code

001/*-------------------------------------------------------------------------+
002|                                                                          |
003| Copyright (c) 2009-2017 CQSE GmbH                                        |
004|                                                                          |
005+-------------------------------------------------------------------------*/
006package eu.cqse.check.framework.util.javascript;
007
008import static eu.cqse.check.framework.scanner.ETokenType.DOCUMENTATION_COMMENT;
009import static eu.cqse.check.framework.shallowparser.SubTypeNames.GOOG_MODULE;
010import static eu.cqse.check.framework.shallowparser.SubTypeNames.GOOG_PROVIDE;
011import static eu.cqse.check.framework.shallowparser.SubTypeNames.GOOG_REQUIRE;
012import static eu.cqse.check.framework.util.javascript.ClosurePatterns.CLOSURE_CONSTRUCTOR_PATTERN;
013import static eu.cqse.check.framework.util.javascript.ClosurePatterns.DEPENDENCY_NAMESPACE_GROUP_INDEX;
014import static eu.cqse.check.framework.util.javascript.ClosurePatterns.GOOG_INHERITS_PATTERN;
015import static eu.cqse.check.framework.util.javascript.ClosurePatterns.NAMESPACE_CONSTANT_PATTERN;
016
017import java.util.ArrayList;
018import java.util.HashSet;
019import java.util.List;
020import java.util.Objects;
021import java.util.Set;
022import java.util.function.Function;
023
024import org.conqat.lib.commons.assertion.CCSMAssert;
025import org.conqat.lib.commons.collections.SetMap;
026import org.conqat.lib.commons.string.StringUtils;
027
028import eu.cqse.check.framework.scanner.IToken;
029import eu.cqse.check.framework.shallowparser.framework.ShallowEntity;
030import eu.cqse.check.framework.util.tokens.TokenPattern;
031import eu.cqse.check.framework.util.tokens.TokenPatternMatch;
032import eu.cqse.check.framework.util.tokens.TokenStream;
033
034/**
035 * Extracts namespaces (i.e., JS 'class declarations') from JavaScript that uses
036 * Google Closure (https://developers.google.com/closure/)
037 */
038public class ClosureJavaScriptDependencyExtractor {
039
040        /**
041         * The namespace (e.g. 'x.y.MyType') whose dependencies are currently being
042         * collected. Can be null, e.g. at the top of files or between two classes in
043         * one file.
044         */
045        private String currentNamespace;
046
047        /** Collects the dependency results. */
048        private ClosureDependencyResult result;
049
050        private TokenStream tokenStream;
051
052        /**
053         * Collects the real dependencies of the given entities, which might not match
054         * the ones declared with 'goog.require' in the file. The tokens are needed here
055         * because we also evaluate dependencies from comments.
056         */
057        public ClosureDependencyResult getActualDependencies(List<ShallowEntity> entities, List<IToken> tokens) {
058                result = new ClosureDependencyResult();
059
060                Set<String> validNamespaces = new HashSet<>(getDeclaredNamespaces(entities));
061                if (validNamespaces.isEmpty()) {
062                        return result;
063                }
064
065                addDependenciesFromGoogRequires(entities, validNamespaces);
066
067                tokenStream = new TokenStream(tokens, 0);
068
069                while (!tokenStream.isExhausted()) {
070                        if (foundNewNamespaceDeclaration(validNamespaces)) {
071                                continue;
072                        }
073                        if (currentNamespace == null || !consumedCurrentTokens()) {
074                                tokenStream.advancePosition(1);
075                        }
076                }
077
078                return result;
079        }
080
081        /**
082         * Stores the namespaces required via 'goog.require' in the current file (for
083         * each provided namespace).
084         *
085         * @param validNamespaces
086         *            all namespaces declared (via 'goog.provide') in the current file
087         *            (usually just one).
088         */
089        private void addDependenciesFromGoogRequires(List<ShallowEntity> entities, Set<String> validNamespaces) {
090                SetMap<String, IToken> requiredNamespaces = getStatedDependencies(entities);
091
092                // This loop looks expensive, but validNamespaces and
093                // getCollection(requiredNamespace) should usually be equal to 1.
094                for (String requiredNamespace : requiredNamespaces.getKeys()) {
095                        for (String providedNamespace : validNamespaces) {
096                                for (IToken dependencyToken : requiredNamespaces.getCollection(requiredNamespace)) {
097                                        result.addDependency(providedNamespace, requiredNamespace, dependencyToken);
098                                }
099                        }
100                }
101        }
102
103        /**
104         * Whether we found the declaration of a new namespace in the current file at
105         * the beginning of {@link #tokenStream}. If there is a match, the corresponding
106         * tokens will be removed from the stream, and true is returned.
107         */
108        private boolean foundNewNamespaceDeclaration(Set<String> validNamespaces) {
109                IToken firstToken = tokenStream.peekCurrent();
110                String nextNamespace = getNextNamespaceOrNull(validNamespaces);
111                if (nextNamespace == null || Objects.equals(nextNamespace, currentNamespace)) {
112                        return false;
113                }
114                result.addNamespace(nextNamespace, firstToken);
115                currentNamespace = nextNamespace;
116                tokenStream.advancePosition(1);
117                return true;
118        }
119
120        /**
121         * @return {@code true} if we found a dependency-related pattern at the
122         *         beginning of {@link #tokenStream} (which will remove the pattern's
123         *         tokens from the stream), {@code false} otherwise
124         */
125        private boolean consumedCurrentTokens() {
126                return processedCommentToken() || processedConstructor() || processedGoogInherits() || processedMethodcall()
127                                || processedConstant();
128        }
129
130        /**
131         * Looks for a static method call of a foreign namespace and consumes the
132         * corresponding tokens, if applicable. See {@link #processedSimplePattern}
133         */
134        private boolean processedMethodcall() {
135                return processedSimplePattern(ClosurePatterns.STATIC_METHOD_CALL_PATTERN,
136                                dependencyNamespace -> StringUtils.removeLastPart(dependencyNamespace, '.'));
137        }
138
139        /**
140         * Looks for an constructor of a foreign namespace and consumes the
141         * corresponding tokens, if applicable. See {@link #processedSimplePattern}
142         */
143        private boolean processedConstructor() {
144                return processedSimplePattern(ClosurePatterns.CONSTRUCTOR_PATTERN, null);
145        }
146
147        /**
148         * Looks for the given pattern and applies the given function to potential
149         * matches. If a match is found, stores the dependencies in {@link #result},
150         * removes the match's tokens from {@link #tokenStream}, and returns
151         * {@code true}. Otherwise, {@code false} is returned.
152         */
153        private boolean processedSimplePattern(TokenPattern dependencyPattern,
154                        Function<String, String> dependencyTextModifier) {
155                TokenPatternMatch patternMatch = dependencyPattern.matchAtCurrentPosition(tokenStream);
156                if (patternMatch == null) {
157                        return false;
158                }
159                String dependencyNamespace = patternMatch.groupString(DEPENDENCY_NAMESPACE_GROUP_INDEX);
160                if (dependencyTextModifier != null) {
161                        dependencyNamespace = dependencyTextModifier.apply(dependencyNamespace);
162                }
163                handlePatternMatch(dependencyNamespace, patternMatch);
164                return true;
165        }
166
167        /**
168         * Tries to find dependencies from JS-doc comments,
169         * e.g. @type{x.y.OtherNamespace}. Also see
170         * {@link #processedSimplePattern(TokenPattern, Function)}.
171         */
172        private boolean processedCommentToken() {
173
174                IToken currentToken = tokenStream.peekCurrent();
175                if (currentToken.getType() != DOCUMENTATION_COMMENT) {
176                        return false;
177                }
178
179                // These two JS doc parameters indicate that we right before the declaration of
180                // a constructor in the current file, which means that any dependencies found in
181                // this comment are dependencies of the *next* namespace.
182                boolean belongsToNextNamespace = currentToken.getText().contains("@extends")
183                                || currentToken.getText().contains("@constructor");
184
185                for (String commentDependency : ClosurePatterns.getDependenciesFromComment(currentToken)) {
186                        if (belongsToNextNamespace) {
187                                addDependencyForNextNamespace(commentDependency, currentToken);
188                        } else {
189                                addDependency(commentDependency, currentToken);
190                        }
191                }
192                tokenStream.advancePosition(1);
193                return true;
194        }
195
196        /**
197         * Tries to find the use of a constant at the beginning of {@link #tokenStream}.
198         * Returns {@code true} if such an expression was found and processed.
199         */
200        private boolean processedConstant() {
201                TokenPatternMatch namespaceConstantMatch = NAMESPACE_CONSTANT_PATTERN.matchAtCurrentPosition(tokenStream);
202                if (namespaceConstantMatch == null) {
203                        return false;
204                }
205                String namespace = namespaceConstantMatch.groupString(DEPENDENCY_NAMESPACE_GROUP_INDEX);
206                String lastPart = StringUtils.getLastPart(namespace, '.');
207                if (lastPart == null || !lastPart.matches("[A-Z0-9_]+")) {
208                        return false;
209                }
210                String calledNamespace = StringUtils.removeLastPart(namespace, '.');
211                handlePatternMatch(calledNamespace, namespaceConstantMatch);
212                return true;
213        }
214
215        /**
216         * Handles an actual dependency match by storing the dependency and removing the
217         * matches tokens from {@link #tokenStream}.
218         */
219        private void handlePatternMatch(String dependencyNamespace, TokenPatternMatch patternMatch) {
220                List<IToken> groupTokens = patternMatch.groupTokens(DEPENDENCY_NAMESPACE_GROUP_INDEX);
221                addDependency(dependencyNamespace, groupTokens.get(0));
222                removeTokensFromListStart(groupTokens);
223        }
224
225        /**
226         * Tries to find a goog.inherits() call at the beginning of
227         * {@link #tokenStream}. Returns {@code true} if such an expression was found
228         * and processed.
229         */
230        private boolean processedGoogInherits() {
231                TokenPatternMatch googInheritsMatch = GOOG_INHERITS_PATTERN.matchAtCurrentPosition(tokenStream);
232                if (googInheritsMatch == null || !("goog.inherits".equals(googInheritsMatch.groupString(1)))) {
233                        return false;
234                }
235                String inheritsFromNamespace = googInheritsMatch.groupString(DEPENDENCY_NAMESPACE_GROUP_INDEX);
236                handlePatternMatch(inheritsFromNamespace, googInheritsMatch);
237                return true;
238        }
239
240        /**
241         * Adds a dependency for the next namespace that will be declared in the current
242         * file. See
243         * {@link ClosureDependencyResult#addDependencyForNextNamespace(String, IToken)}
244         */
245        private void addDependencyForNextNamespace(String dependencyNamespace, IToken token) {
246                if (dependencyNamespace.contains(".")) {
247                        result.addDependencyForNextNamespace(dependencyNamespace, token);
248                }
249        }
250
251        /**
252         * Tries to identify the next namespace declared of the current file by looking
253         * for a Closure constructor. Can return null (e.g. between two classes)
254         */
255        private String getNextNamespaceOrNull(Set<String> validNamespaces) {
256                TokenPatternMatch constructorMatch = CLOSURE_CONSTRUCTOR_PATTERN.matchAtCurrentPosition(tokenStream);
257                if (constructorMatch == null) {
258                        return currentNamespace;
259                }
260                String newNamespace = constructorMatch.groupString(DEPENDENCY_NAMESPACE_GROUP_INDEX);
261                if (!validNamespaces.contains(newNamespace) || newNamespace.contains("prototype.") || (currentNamespace != null
262                                && (newNamespace.contains(currentNamespace) || currentNamespace.contains(newNamespace)))) {
263                        return null;
264                }
265                return newNamespace;
266        }
267
268        /**
269         * Removes the first n tokens from {@link #tokenStream}, where n is the size of
270         * tokensToRemove.
271         */
272        private void removeTokensFromListStart(List<IToken> tokensToRemove) {
273                tokenStream.advancePosition(tokensToRemove.size());
274        }
275
276        /**
277         * Adds the given dependecy namespace if it matches the general namespace format
278         * and is no sub-namespace of {@link #currentNamespace}.
279         */
280        private void addDependency(String dependencyNamespace, IToken token) {
281                if (currentNamespace != null && !dependencyNamespace.contains(currentNamespace)
282                                && dependencyNamespace.contains(".")) {
283                        result.addDependency(currentNamespace, dependencyNamespace, token);
284                }
285        }
286
287        /**
288         * Returns the dependencies of the given entity that are delclared via
289         * 'goog.require'). Note that these might not be complete (e.g. do not include
290         * 'comment-only' dependencies), or include unused imports.
291         */
292        public static SetMap<String, IToken> getStatedDependencies(List<ShallowEntity> entities) {
293                return collectGoogNamespaceStatements(entities, GOOG_REQUIRE);
294        }
295
296        /**
297         * Returns the declared namespaces (i.e., JS 'class declarations') in the given
298         * entities.
299         */
300        public static List<String> getDeclaredNamespaces(List<ShallowEntity> entities) {
301                ArrayList<String> result = new ArrayList<>();
302                result.addAll(collectGoogNamespaceStatements(entities, GOOG_PROVIDE).getKeys());
303                result.addAll(collectGoogNamespaceStatements(entities, GOOG_MODULE).getKeys());
304                return result;
305        }
306
307        /** @see #getDeclaredNamespaces(List) for the child entities. */
308        public static List<String> getOwnNamespaces(ShallowEntity entity) {
309                return getDeclaredNamespaces(entity.getChildren());
310        }
311
312        /**
313         * Collects the namespaces references (i.e. goog.requires, goog.provides,
314         * goog.module) from the given entities. The result contains the namespaces and
315         * the respective token of the reference.
316         */
317        private static SetMap<String, IToken> collectGoogNamespaceStatements(List<ShallowEntity> entities,
318                        String googSubType) {
319
320                CCSMAssert.isTrue(
321                                GOOG_REQUIRE.equals(googSubType) || GOOG_PROVIDE.equals(googSubType) || GOOG_MODULE.equals(googSubType),
322                                "Expected one of goog.require or goog.provide or goog.module but encountered " + googSubType);
323
324                SetMap<String, IToken> importAndTokens = new SetMap<>();
325                for (ShallowEntity entity : entities) {
326                        if (!entity.getSubtype().equals(googSubType)) {
327                                continue;
328                        }
329                        String quotedImport = entity.getName();
330                        importAndTokens.add(quotedImport.substring(1, quotedImport.length() - 1), entity.ownStartTokens().get(0));
331                }
332                return importAndTokens;
333        }
334}