• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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