001/* 002 * Copyright (C) 2009-2011 Mathias Doenitz 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package org.parboiled.support; 018 019import org.parboiled.Node; 020import org.parboiled.buffers.InputBuffer; 021import org.parboiled.common.Predicate; 022import org.parboiled.common.Predicates; 023import org.parboiled.common.StringUtils; 024 025import java.util.Collection; 026import java.util.List; 027 028import static org.parboiled.common.Preconditions.checkArgNotNull; 029import static org.parboiled.trees.GraphUtils.hasChildren; 030import static org.parboiled.trees.GraphUtils.printTree; 031 032/** 033 * General utility methods for operating on parse trees. 034 */ 035public final class ParseTreeUtils { 036 037 private ParseTreeUtils() {} 038 039 /** 040 * <p>Returns the parse tree node underneath the given parent that matches the given path.</p> 041 * <p>The path is a '/' separated list of node label prefixes describing the ancestor chain of the node to look for 042 * relative to the given parent node. If there are several nodes that match the given path the method 043 * returns the first one unless the respective path segments has the special prefix "last:". In this case the 044 * last matching node is returned. 045 * <p><b>Example:</b> "per/last:so/fix" will return the first node, whose label starts with "fix" under the last 046 * node, whose label starts with "so" under the first node, whose label starts with "per".</p> 047 * If parent is null or no node is found the method returns null. 048 * 049 * @param parent the parent Node 050 * @param path the path to the Node being searched for 051 * @return the Node if found or null if not found 052 */ 053 public static <V> Node<V> findNodeByPath(Node<V> parent, String path) { 054 checkArgNotNull(path, "path"); 055 return parent != null && hasChildren(parent) ? findNodeByPath(parent.getChildren(), path) : null; 056 } 057 058 /** 059 * Returns the node underneath the given parents that matches the given path. 060 * See {@link #findNodeByPath(Node, String)} )} for a description of the path argument. 061 * If the given collections of parents is null or empty or no node is found the method returns null. 062 * 063 * @param parents the parent Nodes to look through 064 * @param path the path to the Node being searched for 065 * @return the Node if found or null if not found 066 */ 067 public static <V> Node<V> findNodeByPath(List<Node<V>> parents, String path) { 068 checkArgNotNull(path, "path"); 069 if (parents != null && !parents.isEmpty()) { 070 int separatorIndex = path.indexOf('/'); 071 String prefix = separatorIndex != -1 ? path.substring(0, separatorIndex) : path; 072 int start = 0, step = 1; 073 if (prefix.startsWith("last:")) { 074 prefix = prefix.substring(5); 075 start = parents.size() - 1; 076 step = -1; 077 } 078 for (int i = start; 0 <= i && i < parents.size(); i += step) { 079 Node<V> child = parents.get(i); 080 if (StringUtils.startsWith(child.getLabel(), prefix)) { 081 return separatorIndex == -1 ? child : findNodeByPath(child, path.substring(separatorIndex + 1)); 082 } 083 } 084 } 085 return null; 086 } 087 088 /** 089 * Collects all nodes underneath the given parent that match the given path. 090 * The path is a '/' separated list of node label prefixes describing the ancestor chain of the node to look for 091 * relative to the given parent node. 092 * 093 * @param parent the parent Node 094 * @param path the path to the Nodes being searched for 095 * @param collection the collection to collect the found Nodes into 096 * @return the same collection instance passed as a parameter 097 */ 098 public static <V, C extends Collection<Node<V>>> C collectNodesByPath(Node<V> parent, String path, C collection) { 099 checkArgNotNull(path, "path"); 100 checkArgNotNull(collection, "collection"); 101 return parent != null && hasChildren(parent) ? 102 collectNodesByPath(parent.getChildren(), path, collection) : collection; 103 } 104 105 /** 106 * Collects all nodes underneath the given parents that match the given path. 107 * The path is a '/' separated list of node label prefixes describing the ancestor chain of the node to look for 108 * relative to the given parent nodes. 109 * 110 * @param parents the parent Nodes to look through 111 * @param path the path to the Nodes being searched for 112 * @param collection the collection to collect the found Nodes into 113 * @return the same collection instance passed as a parameter 114 */ 115 public static <V, C extends Collection<Node<V>>> C collectNodesByPath(List<Node<V>> parents, String path, 116 C collection) { 117 checkArgNotNull(path, "path"); 118 checkArgNotNull(collection, "collection"); 119 if (parents != null && !parents.isEmpty()) { 120 int separatorIndex = path.indexOf('/'); 121 String prefix = separatorIndex != -1 ? path.substring(0, separatorIndex) : path; 122 for (Node<V> child : parents) { 123 if (StringUtils.startsWith(child.getLabel(), prefix)) { 124 if (separatorIndex == -1) { 125 collection.add(child); 126 } else { 127 collectNodesByPath(child, path.substring(separatorIndex + 1), collection); 128 } 129 } 130 } 131 } 132 return collection; 133 } 134 135 /** 136 * Returns the first node underneath the given parent for which the given predicate evaluates to true. 137 * If parent is null or no node is found the method returns null. 138 * 139 * @param parent the parent Node 140 * @param predicate the predicate 141 * @return the Node if found or null if not found 142 */ 143 public static <V> Node<V> findNode(Node<V> parent, Predicate<Node<V>> predicate) { 144 checkArgNotNull(predicate, "predicate"); 145 if (parent != null) { 146 if (predicate.apply(parent)) return parent; 147 if (hasChildren(parent)) { 148 Node<V> found = findNode(parent.getChildren(), predicate); 149 if (found != null) return found; 150 } 151 } 152 return null; 153 } 154 155 /** 156 * Returns the first node underneath the given parents for which the given predicate evaluates to true. 157 * If parents is null or empty or no node is found the method returns null. 158 * 159 * @param parents the parent Nodes to look through 160 * @param predicate the predicate 161 * @return the Node if found or null if not found 162 */ 163 public static <V> Node<V> findNode(List<Node<V>> parents, Predicate<Node<V>> predicate) { 164 checkArgNotNull(predicate, "predicate"); 165 if (parents != null && !parents.isEmpty()) { 166 for (Node<V> child : parents) { 167 Node<V> found = findNode(child, predicate); 168 if (found != null) return found; 169 } 170 } 171 return null; 172 } 173 174 /** 175 * Returns the first node underneath the given parent for which matches the given label prefix. 176 * If parents is null or empty or no node is found the method returns null. 177 * 178 * @param parent the parent node 179 * @param labelPrefix the label prefix to look for 180 * @return the Node if found or null if not found 181 */ 182 public static <V> Node<V> findNodeByLabel(Node<V> parent, String labelPrefix) { 183 return findNode(parent, new LabelPrefixPredicate<V>(labelPrefix)); 184 } 185 186 /** 187 * Returns the first node underneath the given parents which matches the given label prefix. 188 * If parents is null or empty or no node is found the method returns null. 189 * 190 * @param parents the parent Nodes to look through 191 * @param labelPrefix the label prefix to look for 192 * @return the Node if found or null if not found 193 */ 194 public static <V> Node<V> findNodeByLabel(List<Node<V>> parents, String labelPrefix) { 195 return findNode(parents, new LabelPrefixPredicate<V>(labelPrefix)); 196 } 197 198 /** 199 * Returns the last node underneath the given parent for which the given predicate evaluates to true. 200 * If parent is null or no node is found the method returns null. 201 * 202 * @param parent the parent Node 203 * @param predicate the predicate 204 * @return the Node if found or null if not found 205 */ 206 public static <V> Node<V> findLastNode(Node<V> parent, Predicate<Node<V>> predicate) { 207 checkArgNotNull(predicate, "predicate"); 208 if (parent != null) { 209 if (predicate.apply(parent)) return parent; 210 if (hasChildren(parent)) { 211 Node<V> found = findLastNode(parent.getChildren(), predicate); 212 if (found != null) return found; 213 } 214 } 215 return null; 216 } 217 218 /** 219 * Returns the last node underneath the given parents for which the given predicate evaluates to true. 220 * If parents is null or empty or no node is found the method returns null. 221 * 222 * @param parents the parent Nodes to look through 223 * @param predicate the predicate 224 * @return the Node if found or null if not found 225 */ 226 public static <V> Node<V> findLastNode(List<Node<V>> parents, Predicate<Node<V>> predicate) { 227 checkArgNotNull(predicate, "predicate"); 228 if (parents != null && !parents.isEmpty()) { 229 int parentsSize = parents.size(); 230 for (int i = parentsSize - 1; i >= 0; i--) { 231 Node<V> found = findLastNode(parents.get(i), predicate); 232 if (found != null) return found; 233 } 234 } 235 return null; 236 } 237 238 /** 239 * Collects all nodes underneath the given parent for which the given predicate evaluates to true. 240 * 241 * @param parent the parent Node 242 * @param predicate the predicate 243 * @param collection the collection to collect the found Nodes into 244 * @return the same collection instance passed as a parameter 245 */ 246 public static <V, C extends Collection<Node<V>>> C collectNodes(Node<V> parent, 247 Predicate<Node<V>> predicate, 248 C collection) { 249 checkArgNotNull(predicate, "predicate"); 250 checkArgNotNull(collection, "collection"); 251 return parent != null && hasChildren(parent) ? 252 collectNodes(parent.getChildren(), predicate, collection) : collection; 253 } 254 255 /** 256 * Returns the input text matched by the given node, with error correction. 257 * 258 * @param node the node 259 * @param inputBuffer the underlying inputBuffer 260 * @return null if node is null otherwise a string with the matched input text (which can be empty) 261 */ 262 public static String getNodeText(Node<?> node, InputBuffer inputBuffer) { 263 checkArgNotNull(node, "node"); 264 checkArgNotNull(inputBuffer, "inputBuffer"); 265 if (node.hasError()) { 266 // if the node has a parse error we cannot simply cut a string out of the underlying input buffer, since we 267 // would also include illegal characters, so we need to build it constructively 268 StringBuilder sb = new StringBuilder(); 269 for (int i = node.getStartIndex(); i < node.getEndIndex(); i++) { 270 char c = inputBuffer.charAt(i); 271 switch (c) { 272 case Chars.DEL_ERROR: 273 i++; 274 break; 275 case Chars.INS_ERROR: 276 case Chars.EOI: 277 break; 278 case Chars.RESYNC_START: 279 i++; 280 while (inputBuffer.charAt(i) != Chars.RESYNC_END) i++; 281 break; 282 case Chars.RESYNC_END: 283 case Chars.RESYNC_EOI: 284 case Chars.RESYNC: 285 // we should only see proper RESYNC_START / RESYNC_END blocks 286 throw new IllegalStateException(); 287 default: 288 sb.append(c); 289 } 290 } 291 return sb.toString(); 292 } 293 return inputBuffer.extract(node.getStartIndex(), node.getEndIndex()); 294 } 295 296 /** 297 * Collects all nodes underneath the given parents for which the given predicate evaluates to true. 298 * 299 * @param parents the parent Nodes to look through 300 * @param predicate the predicate 301 * @param collection the collection to collect the found Nodes into 302 * @return the same collection instance passed as a parameter 303 */ 304 public static <V, C extends Collection<Node<V>>> C collectNodes(List<Node<V>> parents, 305 Predicate<Node<V>> predicate, 306 C collection) { 307 checkArgNotNull(predicate, "predicate"); 308 checkArgNotNull(collection, "collection"); 309 if (parents != null && !parents.isEmpty()) { 310 for (Node<V> child : parents) { 311 if (predicate.apply(child)) { 312 collection.add(child); 313 } 314 collectNodes(child, predicate, collection); 315 } 316 } 317 return collection; 318 } 319 320 /** 321 * Creates a readable string represenation of the parse tree in the given {@link ParsingResult} object. 322 * 323 * @param parsingResult the parsing result containing the parse tree 324 * @return a new String 325 */ 326 public static <V> String printNodeTree(ParsingResult<V> parsingResult) { 327 checkArgNotNull(parsingResult, "parsingResult"); 328 return printNodeTree(parsingResult, Predicates.<Node<V>>alwaysTrue(), Predicates.<Node<V>>alwaysTrue()); 329 } 330 331 /** 332 * Creates a readable string represenation of the parse tree in thee given {@link ParsingResult} object. 333 * The given filter predicate determines whether a particular node (incl. its subtree) is printed or not. 334 * 335 * @param parsingResult the parsing result containing the parse tree 336 * @param nodeFilter the predicate selecting the nodes to print 337 * @param subTreeFilter the predicate determining whether to descend into a given nodes subtree or not 338 * @return a new String 339 */ 340 public static <V> String printNodeTree(ParsingResult<V> parsingResult, Predicate<Node<V>> nodeFilter, 341 Predicate<Node<V>> subTreeFilter) { 342 checkArgNotNull(parsingResult, "parsingResult"); 343 checkArgNotNull(nodeFilter, "nodeFilter"); 344 checkArgNotNull(subTreeFilter, "subTreeFilter"); 345 return printTree(parsingResult.parseTreeRoot, new NodeFormatter<V>(parsingResult.inputBuffer), nodeFilter, 346 subTreeFilter); 347 } 348 349} 350