1 /* 2 * Copyright (C) 2010 The Android Open Source Project 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.android.tradefed.command; 17 18 import com.android.tradefed.config.ConfigurationException; 19 import com.android.tradefed.error.HarnessRuntimeException; 20 import com.android.tradefed.log.LogUtil.CLog; 21 import com.android.tradefed.util.QuotationAwareTokenizer; 22 23 import java.io.BufferedReader; 24 import java.io.File; 25 import java.io.FileReader; 26 import java.io.IOException; 27 import java.util.Arrays; 28 import java.util.Collection; 29 import java.util.HashMap; 30 import java.util.HashSet; 31 import java.util.LinkedList; 32 import java.util.List; 33 import java.util.Map; 34 import java.util.Objects; 35 import java.util.regex.Matcher; 36 import java.util.regex.Pattern; 37 38 /** 39 * Parser for file that contains set of command lines. 40 * <p/> 41 * The syntax of the given file should be series of lines. Each line is a command; that is, a 42 * configuration plus its options: 43 * <pre> 44 * [options] config-name 45 * [options] config-name2 46 * ... 47 * </pre> 48 */ 49 public class CommandFileParser { 50 51 /** 52 * A pattern that matches valid macro usages and captures the name of the macro. 53 * Macro names must start with an alpha character, and may contain alphanumerics, underscores, 54 * or hyphens. 55 */ 56 private static final Pattern MACRO_PATTERN = Pattern.compile("([a-z][a-z0-9_-]*)\\(\\)", 57 Pattern.CASE_INSENSITIVE); 58 59 private Map<String, CommandLine> mMacros = new HashMap<String, CommandLine>(); 60 private Map<String, List<CommandLine>> mLongMacros = new HashMap<String, List<CommandLine>>(); 61 private List<CommandLine> mLines = new LinkedList<CommandLine>(); 62 63 private Collection<String> mIncludedFiles = new HashSet<String>(); 64 65 @SuppressWarnings("serial") 66 public static class CommandLine extends LinkedList<String> { 67 private final File mFile; 68 private final int mLineNumber; 69 CommandLine(File file, int lineNumber)70 CommandLine(File file, int lineNumber) { 71 super(); 72 mFile = file; 73 mLineNumber = lineNumber; 74 } 75 CommandLine(Collection<? extends String> c, File file, int lineNumber)76 CommandLine(Collection<? extends String> c, File file, int lineNumber) { 77 super(c); 78 mFile = file; 79 mLineNumber = lineNumber; 80 } 81 asArray()82 public String[] asArray() { 83 String[] arrayContents = new String[size()]; 84 int i = 0; 85 for (String a : this) { 86 arrayContents[i] = a; 87 i++; 88 } 89 return arrayContents; 90 } 91 getFile()92 public File getFile() { 93 return mFile; 94 } 95 getLineNumber()96 public int getLineNumber() { 97 return mLineNumber; 98 } 99 100 @Override equals(Object o)101 public boolean equals(Object o) { 102 if(o instanceof CommandLine) { 103 CommandLine otherLine = (CommandLine) o; 104 return super.equals(o) && 105 Objects.equals(otherLine.getFile(), mFile) && 106 otherLine.getLineNumber() == mLineNumber; 107 } 108 return false; 109 } 110 111 @Override hashCode()112 public int hashCode() { 113 int listHash = super.hashCode(); 114 return Objects.hash(listHash, mFile, mLineNumber); 115 } 116 } 117 118 /** 119 * Represents a bitmask. Useful because it caches the number of bits which are set. 120 */ 121 static class Bitmask { 122 private List<Boolean> mBitmask = new LinkedList<Boolean>(); 123 private int mNumBitsSet = 0; 124 Bitmask(int nBits)125 public Bitmask(int nBits) { 126 this(nBits, false); 127 } 128 Bitmask(int nBits, boolean initialValue)129 public Bitmask(int nBits, boolean initialValue) { 130 for (int i = 0; i < nBits; ++i) { 131 mBitmask.add(initialValue); 132 } 133 if (initialValue) { 134 mNumBitsSet = nBits; 135 } 136 } 137 138 /** 139 * Return the number of bits which are set (rather than unset) 140 */ getSetCount()141 public int getSetCount() { 142 return mNumBitsSet; 143 } 144 get(int idx)145 public boolean get(int idx) { 146 return mBitmask.get(idx); 147 } 148 set(int idx)149 public boolean set(int idx) { 150 boolean retVal = mBitmask.set(idx, true); 151 if (!retVal) { 152 mNumBitsSet++; 153 } 154 return retVal; 155 } 156 unset(int idx)157 public boolean unset(int idx) { 158 boolean retVal = mBitmask.set(idx, false); 159 if (retVal) { 160 mNumBitsSet--; 161 } 162 return retVal; 163 } 164 remove(int idx)165 public boolean remove(int idx) { 166 boolean retVal = mBitmask.remove(idx); 167 if (retVal) { 168 mNumBitsSet--; 169 } 170 return retVal; 171 } 172 add(int idx, boolean val)173 public void add(int idx, boolean val) { 174 mBitmask.add(idx, val); 175 if (val) { 176 mNumBitsSet++; 177 } 178 } 179 180 /** 181 * Insert a bunch of identical values in the specified spot in the mask 182 * 183 * @param idx the index where the first new value should be set. 184 * @param count the number of new values to insert 185 * @param val the parity of the new values 186 */ addN(int idx, int count, boolean val)187 public void addN(int idx, int count, boolean val) { 188 for (int i = 0; i < count; ++i) { 189 add(idx, val); 190 } 191 } 192 } 193 194 /** 195 * Checks if a line matches the expected format for a (short) macro: 196 * MACRO (name) = (token) [(token)...] 197 * This method verifies that: 198 * <ol> 199 * <li>Line is at least four tokens long</li> 200 * <li>The first token is "MACRO" (case-sensitive)</li> 201 * <li>The third token is an equal-sign</li> 202 * </ol> 203 * 204 * @return {@code true} if the line matches the macro format, {@false} otherwise 205 */ isLineMacro(CommandLine line)206 private static boolean isLineMacro(CommandLine line) { 207 return line.size() >= 4 && "MACRO".equals(line.get(0)) && "=".equals(line.get(2)); 208 } 209 210 /** 211 * Checks if a line matches the expected format for the opening line of a long macro: 212 * LONG MACRO (name) 213 * 214 * @return {@code true} if the line matches the long macro format, {@code false} otherwise 215 */ isLineLongMacro(CommandLine line)216 private static boolean isLineLongMacro(CommandLine line) { 217 return line.size() == 3 && "LONG".equals(line.get(0)) && "MACRO".equals(line.get(1)); 218 } 219 220 /** 221 * Checks if a line matches the expected format for an INCLUDE directive 222 * 223 * @return {@code true} if the line is an INCLUDE directive, {@code false} otherwise 224 */ isLineIncludeDirective(CommandLine line)225 private static boolean isLineIncludeDirective(CommandLine line) { 226 return line.size() == 2 && "INCLUDE".equals(line.get(0)); 227 } 228 229 /** 230 * Checks if a line should be parsed or ignored. Basically, ignore if the line is commented 231 * or is empty. 232 * 233 * @param line A {@link String} containing the line of input to check 234 * @return {@code true} if we should parse the line, {@code false} if we should ignore it. 235 */ shouldParseLine(String line)236 private static boolean shouldParseLine(String line) { 237 line = line.trim(); 238 return !(line.isEmpty() || line.startsWith("#")); 239 } 240 241 /** 242 * Return the command files included by the last parsed command file. 243 */ getIncludedFiles()244 public Collection<String> getIncludedFiles() { 245 return mIncludedFiles; 246 } 247 248 /** 249 * Does a single pass of the input CommandFile, storing input lines as macros, long macros, or 250 * commands. 251 * 252 * Note that this method may call itself recursively to handle the INCLUDE directive. 253 */ scanFile(File file)254 private void scanFile(File file) throws IOException, ConfigurationException { 255 if (mIncludedFiles.contains(file.getAbsolutePath())) { 256 // Repeated include; ignore 257 CLog.v("Skipping repeated include of file %s.", file.toString()); 258 return; 259 } else { 260 mIncludedFiles.add(file.getAbsolutePath()); 261 } 262 263 BufferedReader fileReader = createCommandFileReader(file); 264 String inputLine = null; 265 int lineNumber = 0; 266 try { 267 while ((inputLine = fileReader.readLine()) != null) { 268 lineNumber++; 269 inputLine = inputLine.trim(); 270 if (shouldParseLine(inputLine)) { 271 CommandLine lArgs = null; 272 try { 273 String[] args = QuotationAwareTokenizer.tokenizeLine(inputLine); 274 lArgs = new CommandLine(Arrays.asList(args), file, 275 lineNumber); 276 } catch (HarnessRuntimeException e) { 277 throw new ConfigurationException(e.getMessage(), e, e.getErrorId()); 278 } 279 280 if (isLineMacro(lArgs)) { 281 // Expected format: MACRO <name> = <token> [<token>...] 282 String name = lArgs.get(1); 283 CommandLine expansion = new CommandLine(lArgs.subList(3, lArgs.size()), 284 file, lineNumber); 285 CommandLine prev = mMacros.put(name, expansion); 286 if (prev != null) { 287 CLog.w("Overwrote short macro '%s' while parsing file %s", name, file); 288 CLog.w("value '%s' replaced previous value '%s'", expansion, prev); 289 } 290 } else if (isLineLongMacro(lArgs)) { 291 // Expected format: LONG MACRO <name>\n(multiline expansion)\nEND MACRO 292 String name = lArgs.get(2); 293 List<CommandLine> expansion = new LinkedList<CommandLine>(); 294 295 inputLine = fileReader.readLine(); 296 lineNumber++; 297 while (!"END MACRO".equals(inputLine)) { 298 if (inputLine == null) { 299 // Syntax error 300 throw new ConfigurationException(String.format( 301 "Syntax error: Unexpected EOF while reading definition " + 302 "for LONG MACRO %s.", name)); 303 } 304 if (shouldParseLine(inputLine)) { 305 // Store the tokenized line 306 CommandLine line = new CommandLine(Arrays.asList( 307 QuotationAwareTokenizer.tokenizeLine(inputLine)), 308 file, lineNumber); 309 expansion.add(line); 310 } 311 312 // Advance 313 inputLine = fileReader.readLine(); 314 lineNumber++; 315 } 316 CLog.d("Parsed %d-line definition for long macro %s", expansion.size(), 317 name); 318 319 List<CommandLine> prev = mLongMacros.put(name, expansion); 320 if (prev != null) { 321 CLog.w("Overwrote long macro %s while parsing file %s", name, file); 322 CLog.w("%d-line definition replaced previous %d-line definition", 323 expansion.size(), prev.size()); 324 } 325 } else if (isLineIncludeDirective(lArgs)) { 326 File toScan = new File(lArgs.get(1)); 327 if (toScan.isAbsolute()) { 328 CLog.d("Got an include directive for absolute path %s.", lArgs.get(1)); 329 } else { 330 File parent = file.getParentFile(); 331 toScan = new File(parent, lArgs.get(1)); 332 CLog.d("Got an include directive for relative path %s, using '%s' " + 333 "for parent dir", lArgs.get(1), parent); 334 } 335 scanFile(toScan); 336 } else { 337 mLines.add(lArgs); 338 } 339 } 340 } 341 } finally { 342 fileReader.close(); 343 } 344 } 345 346 /** 347 * Parses the commands contained in {@code file}, doing macro expansions as necessary 348 * 349 * @param file the {@link File} to parse 350 * @return the list of parsed commands 351 * @throws IOException if failed to read file 352 * @throws ConfigurationException if content of file could not be parsed 353 */ parseFile(File file)354 public List<CommandLine> parseFile(File file) throws IOException, 355 ConfigurationException { 356 // clear state from last call 357 mIncludedFiles.clear(); 358 mMacros.clear(); 359 mLongMacros.clear(); 360 mLines.clear(); 361 362 // Parse this cmdfile and all of its dependencies. 363 scanFile(file); 364 365 // remove original file from list of includes, as call above has side effect of adding it to 366 // mIncludedFiles 367 mIncludedFiles.remove(file.getAbsolutePath()); 368 369 // Now perform macro expansion 370 /** 371 * inputBitmask is used to stop iterating when we're sure there are no more macros to 372 * expand. It is a bitmask where the (k)th bit represents the (k)th element in 373 * {@code mLines.} 374 * <p> 375 * Each bit starts as {@code true}, meaning that each line in mLines may have macro calls to 376 * be expanded. We set bits of {@code inputBitmask} to {@code false} once we've determined 377 * that the corresponding lines of {@code mLines} have been fully expanded, which allows us 378 * to skip those lines on subsequent scans. 379 * <p> 380 * {@code inputBitmaskCount} stores the quantity of {@code true} bits in 381 * {@code inputBitmask}. Once {@code inputBitmaskCount == 0}, we are done expanding macros. 382 */ 383 Bitmask inputBitmask = new Bitmask(mLines.size(), true); 384 385 // Do a maximum of 20 iterations of expansion 386 // FIXME: make this configurable 387 for (int iCount = 0; iCount < 20 && inputBitmask.getSetCount() > 0; ++iCount) { 388 CLog.d("### Expansion iteration %d", iCount); 389 390 int inputIdx = 0; 391 while (inputIdx < mLines.size()) { 392 if (!inputBitmask.get(inputIdx)) { 393 // Skip this line; we've already determined that it doesn't contain any macro 394 // calls to be expanded. 395 CLog.d("skipping input line %s", mLines.get(inputIdx)); 396 ++inputIdx; 397 continue; 398 } 399 400 CommandLine line = mLines.get(inputIdx); 401 boolean sawMacro = expandMacro(line); 402 List<CommandLine> longMacroExpansion = expandLongMacro(line, !sawMacro); 403 404 if (longMacroExpansion == null) { 405 if (sawMacro) { 406 // We saw and expanded a short macro. This may have pulled in another macro 407 // to expand, so leave inputBitmask alone. 408 } else { 409 // We did not find any macros (long or short) to expand, thus all expansions 410 // are done for this CommandLine. Update inputBitmask appropriately. 411 inputBitmask.unset(inputIdx); 412 } 413 414 // Finally, advance. 415 ++inputIdx; 416 } else { 417 // We expanded a long macro. First, actually insert the expansion in place of 418 // the macro call 419 mLines.remove(inputIdx); 420 inputBitmask.remove(inputIdx); 421 mLines.addAll(inputIdx, longMacroExpansion); 422 inputBitmask.addN(inputIdx, longMacroExpansion.size(), true); 423 424 // And advance past the end of the expanded macro 425 inputIdx += longMacroExpansion.size(); 426 } 427 } 428 } 429 return mLines; 430 } 431 432 /** 433 * Performs one level of macro expansion for the first macro used in the line 434 */ expandLongMacro(CommandLine line, boolean checkMissingMacro)435 private List<CommandLine> expandLongMacro(CommandLine line, boolean checkMissingMacro) 436 throws ConfigurationException { 437 for (int idx = 0; idx < line.size(); ++idx) { 438 String token = line.get(idx); 439 Matcher matchMacro = MACRO_PATTERN.matcher(token); 440 if (matchMacro.matches()) { 441 // we hit a macro; expand it 442 List<CommandLine> expansion = new LinkedList<CommandLine>(); 443 String name = matchMacro.group(1); 444 List<CommandLine> longMacro = mLongMacros.get(name); 445 if (longMacro == null) { 446 if (checkMissingMacro) { 447 // If the expandMacro method hits an unrecognized macro, it will leave it in 448 // the stream for this method. If it's not recognized here, throw an 449 // exception 450 throw new ConfigurationException(String.format( 451 "Macro call '%s' does not match any macro definitions.", name)); 452 } else { 453 // At this point, it may just be a short macro 454 CLog.d("Macro call '%s' doesn't match any long macro definitions.", name); 455 return null; 456 } 457 } 458 459 LinkedList<String> prefix = new LinkedList<>(line.subList(0, idx)); 460 LinkedList<String> suffix = new LinkedList<>(line.subList(idx, line.size())); 461 suffix.remove(0); 462 for (CommandLine macroLine : longMacro) { 463 CommandLine expanded = new CommandLine(line.getFile(), 464 line.getLineNumber()); 465 expanded.addAll(prefix); 466 expanded.addAll(macroLine); 467 expanded.addAll(suffix); 468 expansion.add(expanded); 469 } 470 471 // Only expand a single macro usage at a time 472 return expansion; 473 } 474 } 475 return null; 476 } 477 478 /** 479 * Performs one level of macro expansion for every macro used in the line 480 * 481 * @return {@code true} if a macro was found and expanded, {@code false} if no macro was found 482 */ expandMacro(CommandLine line)483 private boolean expandMacro(CommandLine line) { 484 boolean sawMacro = false; 485 486 int idx = 0; 487 while (idx < line.size()) { 488 String token = line.get(idx); 489 Matcher matchMacro = MACRO_PATTERN.matcher(token); 490 if (matchMacro.matches() && mMacros.containsKey(matchMacro.group(1))) { 491 // we hit a macro; expand it 492 String name = matchMacro.group(1); 493 CommandLine macro = mMacros.get(name); 494 CLog.d("Gotcha! Expanding macro '%s' to '%s'", name, macro); 495 line.remove(idx); 496 line.addAll(idx, macro); 497 idx += macro.size(); 498 sawMacro = true; 499 } else { 500 ++idx; 501 } 502 } 503 return sawMacro; 504 } 505 506 /** 507 * Create a reader for the command file data. 508 * <p/> 509 * Exposed for unit testing. 510 * 511 * @param file the command {@link File} 512 * @return the {@link BufferedReader} 513 * @throws IOException if failed to read data 514 */ createCommandFileReader(File file)515 BufferedReader createCommandFileReader(File file) throws IOException { 516 return new BufferedReader(new FileReader(file)); 517 } 518 } 519