[duplicates] enable duplicates analysis in PyCharm/WebStorm/PhpStorm/RubyMine
[idea/community.git] / platform / core-impl / src / com / intellij / psi / impl / source / tree / LightTreeUtil.java
1 /*
2  * Copyright 2000-2015 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.psi.impl.source.tree;
17
18 import com.intellij.lang.LighterAST;
19 import com.intellij.lang.LighterASTNode;
20 import com.intellij.lang.LighterASTTokenNode;
21 import com.intellij.lang.LighterLazyParseableNode;
22 import com.intellij.openapi.diagnostic.Logger;
23 import com.intellij.openapi.progress.ProgressManager;
24 import com.intellij.psi.tree.IElementType;
25 import com.intellij.psi.tree.TokenSet;
26 import com.intellij.util.SmartList;
27 import org.jetbrains.annotations.NotNull;
28 import org.jetbrains.annotations.Nullable;
29
30 import java.util.Arrays;
31 import java.util.Collections;
32 import java.util.List;
33 import java.util.function.BiConsumer;
34
35 @SuppressWarnings("ForLoopReplaceableByForEach")
36 public class LightTreeUtil {
37
38   @Nullable
39   public static LighterASTNode firstChildOfType(@NotNull LighterAST tree, @Nullable LighterASTNode node, @NotNull IElementType type) {
40     if (node == null) return null;
41
42     List<LighterASTNode> children = tree.getChildren(node);
43     for (int i = 0; i < children.size(); ++i) {
44       LighterASTNode child = children.get(i);
45       if (child.getTokenType() == type) return child;
46     }
47     return null;
48   }
49
50   @Nullable
51   public static LighterASTNode firstChildOfType(@NotNull LighterAST tree, @Nullable LighterASTNode node, @NotNull TokenSet types) {
52     if (node == null) return null;
53
54     List<LighterASTNode> children = tree.getChildren(node);
55     for (int i = 0; i < children.size(); ++i) {
56       LighterASTNode child = children.get(i);
57       if (types.contains(child.getTokenType())) return child;
58     }
59
60     return null;
61   }
62
63   @NotNull
64   public static LighterASTNode requiredChildOfType(@NotNull LighterAST tree, @NotNull LighterASTNode node, @NotNull IElementType type) {
65     LighterASTNode child = firstChildOfType(tree, node, type);
66     assert child != null : "Required child " + type + " not found in " + node.getTokenType() + ": " + tree.getChildren(node);
67     return child;
68   }
69
70   @NotNull
71   public static LighterASTNode requiredChildOfType(@NotNull LighterAST tree, @NotNull LighterASTNode node, @NotNull TokenSet types) {
72     LighterASTNode child = firstChildOfType(tree, node, types);
73     assert child != null : "Required child " + types + " not found in " + node.getTokenType() + ": " + tree.getChildren(node);
74     return child;
75   }
76
77   @NotNull
78   public static List<LighterASTNode> getChildrenOfType(@NotNull LighterAST tree, @NotNull LighterASTNode node, @NotNull IElementType type) {
79     List<LighterASTNode> result = null;
80
81     List<LighterASTNode> children = tree.getChildren(node);
82     for (int i = 0, size = children.size(); i < size; ++i) {
83       LighterASTNode child = children.get(i);
84       if (child.getTokenType() == type) {
85         if (result == null) result = new SmartList<>();
86         result.add(child);
87       }
88     }
89
90     return result != null ? result: Collections.emptyList();
91   }
92
93   @NotNull
94   public static List<LighterASTNode> getChildrenOfType(@NotNull LighterAST tree, @NotNull LighterASTNode node, @NotNull TokenSet types) {
95     List<LighterASTNode> children = tree.getChildren(node);
96     List<LighterASTNode> result = null;
97
98     for (int i = 0, size = children.size(); i < size; ++i) {
99       LighterASTNode child = children.get(i);
100       if (types.contains(child.getTokenType())) {
101         if (result == null) result = new SmartList<>();
102         result.add(child);
103       }
104     }
105
106     return result != null ? result: Collections.emptyList();
107   }
108
109   @NotNull
110   public static String toFilteredString(@NotNull LighterAST tree, @NotNull LighterASTNode node, @Nullable TokenSet skipTypes) {
111     int length = node.getEndOffset() - node.getStartOffset();
112     if (length < 0) {
113       length = 0;
114       Logger.getInstance(LightTreeUtil.class).error("tree=" + tree + " node=" + node);
115     }
116     StringBuilder buffer = new StringBuilder(length);
117     toBuffer(tree, node, buffer, skipTypes);
118     return buffer.toString();
119   }
120
121   public static void toBuffer(@NotNull LighterAST tree, @NotNull LighterASTNode node, @NotNull StringBuilder buffer, @Nullable TokenSet skipTypes) {
122     if (skipTypes != null && skipTypes.contains(node.getTokenType())) {
123       return;
124     }
125
126     if (node instanceof LighterASTTokenNode) {
127       buffer.append(((LighterASTTokenNode)node).getText());
128       return;
129     }
130
131     if (node instanceof LighterLazyParseableNode) {
132       buffer.append(((LighterLazyParseableNode)node).getText());
133       return;
134     }
135
136     List<LighterASTNode> children = tree.getChildren(node);
137     for (int i = 0, size = children.size(); i < size; ++i) {
138       toBuffer(tree, children.get(i), buffer, skipTypes);
139     }
140   }
141
142   @Nullable
143   public static LighterASTNode getParentOfType(@NotNull LighterAST tree, @Nullable LighterASTNode node,
144                                                 @NotNull TokenSet types, @NotNull TokenSet stopAt) {
145     if (node == null) return null;
146     node = tree.getParent(node);
147     while (node != null) {
148       final IElementType type = node.getTokenType();
149       if (types.contains(type)) return node;
150       if (stopAt.contains(type)) return null;
151       node = tree.getParent(node);
152     }
153     return null;
154   }
155
156   public static void processLeavesAtOffsets(int[] offsets, @NotNull LighterAST tree, @NotNull BiConsumer<LighterASTTokenNode, Integer> consumer) {
157     if (offsets.length == 0) return;
158
159     int[] sortedOffsets = offsets.clone();
160     Arrays.sort(sortedOffsets);
161     new RecursiveLighterASTNodeWalkingVisitor(tree) {
162       int nextIndex = 0;
163       int nextOffset = sortedOffsets[0];
164
165       @Override
166       public void visitNode(@NotNull LighterASTNode element) {
167         if (containsNextOffset(element)) {
168           super.visitNode(element);
169         }
170       }
171
172       @Override
173       public void visitTokenNode(@NotNull LighterASTTokenNode node) {
174         if (containsNextOffset(node)) {
175           consumer.accept(node, nextOffset);
176           while (containsNextOffset(node)) {
177             advanceOffset();
178           }
179         }
180       }
181
182       private boolean containsNextOffset(@NotNull LighterASTNode element) {
183         ProgressManager.checkCanceled();
184         return nextIndex < sortedOffsets.length && element.getStartOffset() <= nextOffset && nextOffset < element.getEndOffset();
185       }
186
187       private void advanceOffset() {
188         nextIndex++;
189         if (nextIndex < sortedOffsets.length) {
190           nextOffset = sortedOffsets[nextIndex];
191         }
192       }
193     }.visitNode(tree.getRoot());
194   }
195 }