src/main/java/com/android/tools/r8/retrace/RetraceStackTrace.java - r8 - Git at Google

 // Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 package com.android.tools.r8.retrace;

 import static com.android.tools.r8.retrace.RetraceUtils.methodDescriptionFromMethodReference;
 import static com.google.common.base.Predicates.not;

 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.MethodReference;
 import com.android.tools.r8.references.Reference;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.google.common.collect.ImmutableList;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.function.Predicate;

 public final class RetraceStackTrace {

   public static class StackTraceNode {

     private final List<StackTraceLine> lines;

     StackTraceNode(List<StackTraceLine> lines) {
       this.lines = lines;
       assert !lines.isEmpty();
       assert lines.size() == 1 || lines.stream().allMatch(StackTraceLine::isAtLine);
     }

     public void append(List<String> strings) {
       assert !lines.isEmpty();
       if (lines.size() == 1) {
         strings.add(lines.get(0).toString());
         return;
       }
       // We must have an inlining or ambiguous match here, thus all lines are at-lines.
       assert lines.stream().allMatch(StackTraceLine::isAtLine);
       assert lines.stream()
           .allMatch(line -> line.asAtLine().isAmbiguous == lines.get(0).asAtLine().isAmbiguous);
       if (lines.get(0).asAtLine().isAmbiguous) {
         lines.sort(new AtStackTraceLineComparator());
       }
       boolean shouldPrintOr = false;
       for (StackTraceLine line : lines) {
         assert line.isAtLine();
         AtLine atLine = line.asAtLine();
         if (atLine.isAmbiguous && shouldPrintOr) {
           String atLineString = atLine.toString();
           int firstNonWhitespaceCharacter = StringUtils.firstNonWhitespaceCharacter(atLineString);
           strings.add(
               atLineString.substring(0, firstNonWhitespaceCharacter)
                   + "<OR> "
                   + atLineString.substring(firstNonWhitespaceCharacter));
         } else {
           strings.add(atLine.toString());
         }
         shouldPrintOr = true;
       }
     }
   }

   static class AtStackTraceLineComparator extends AmbiguousComparator<StackTraceLine> {

     AtStackTraceLineComparator() {
       super(
           (line, t) -> {
             assert line.isAtLine();
             AtLine atLine = line.asAtLine();
             switch (t) {
               case CLASS:
                 return atLine.clazz;
               case METHOD:
                 return atLine.method;
               case SOURCE:
                 return atLine.fileName;
               case LINE:
                 return atLine.linePosition + "";
               default:
                 assert false;
             }
             throw new RuntimeException("Comparator key is unknown");
           });
     }
   }

   private final RetraceBase retraceBase;
   private final List<String> stackTrace;
   private final DiagnosticsHandler diagnosticsHandler;
   private final boolean verbose;

   RetraceStackTrace(
       RetraceBase retraceBase,
       List<String> stackTrace,
       DiagnosticsHandler diagnosticsHandler,
       boolean verbose) {
     this.retraceBase = retraceBase;
     this.stackTrace = stackTrace;
     this.diagnosticsHandler = diagnosticsHandler;
     this.verbose = verbose;
   }

   public RetraceCommandLineResult retrace() {
     ArrayList<StackTraceNode> result = new ArrayList<>();
     retraceLine(stackTrace, 0, result);
     List<String> retracedStrings = new ArrayList<>();
     for (StackTraceNode node : result) {
       node.append(retracedStrings);
     }
     return new RetraceCommandLineResult(retracedStrings);
   }

   private void retraceLine(List<String> stackTrace, int index, List<StackTraceNode> result) {
     if (stackTrace.size() <= index) {
       return;
     }
     StackTraceLine stackTraceLine = parseLine(index + 1, stackTrace.get(index));
     List<StackTraceLine> retraced = stackTraceLine.retrace(retraceBase, verbose);
     StackTraceNode node = new StackTraceNode(retraced);
     result.add(node);
     retraceLine(stackTrace, index + 1, result);
   }

   abstract static class StackTraceLine {

     abstract List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose);

     static int firstNonWhiteSpaceCharacterFromIndex(String line, int index) {
       return firstFromIndex(line, index, not(Character::isWhitespace));
     }

     static int firstCharFromIndex(String line, int index, char ch) {
       return firstFromIndex(line, index, c -> c == ch);
     }

     static int firstFromIndex(String line, int index, Predicate<Character> predicate) {
       for (int i = index; i < line.length(); i++) {
         if (predicate.test(line.charAt(i))) {
           return i;
         }
       }
       return line.length();
     }

     boolean isAtLine() {
       return false;
     }

     AtLine asAtLine() {
       return null;
     }

     boolean isExceptionLine() {
       return false;
     }

     ExceptionLine asExceptionLine() {
       return null;
     }
   }

   /**
    * Captures a stack trace line of the following formats:
    *
    * <ul>
    *   <li>com.android.r8.R8Exception
    *   <li>com.android.r8.R8Exception: Problem when compiling program
    *   <li>Caused by: com.android.r8.R8InnerException: You have to write the program first
    *   <li>com.android.r8.R8InnerException: You have to write the program first
    * </ul>
    *
    * <p>This will also contains false positives, such as
    *
    * <pre>
    *   W( 8207) VFY: unable to resolve static method 11: Lprivateinterfacemethods/I$-CC;....
    * </pre>
    *
    * <p>The only invalid chars for type-identifiers for a java type-name is ';', '[' and '/', so we
    * cannot really disregard the above line.
    *
    * <p>Caused by and Suppressed seems to not change based on locale, so we use these as markers.
    */
   static class ExceptionLine extends StackTraceLine {

     private static final String CAUSED_BY = "Caused by: ";
     private static final String SUPPRESSED = "Suppressed: ";

     private final String initialWhiteSpace;
     private final String description;
     private final String exceptionClass;
     private final String message;

     ExceptionLine(
         String initialWhiteSpace, String description, String exceptionClass, String message) {
       this.initialWhiteSpace = initialWhiteSpace;
       this.description = description;
       this.exceptionClass = exceptionClass;
       this.message = message;
     }

     static ExceptionLine tryParse(String line) {
       if (line.isEmpty()) {
         return null;
       }
       int firstNonWhiteSpaceChar = firstNonWhiteSpaceCharacterFromIndex(line, 0);
       String description = "";
       if (line.startsWith(CAUSED_BY, firstNonWhiteSpaceChar)) {
         description = CAUSED_BY;
       } else if (line.startsWith(SUPPRESSED, firstNonWhiteSpaceChar)) {
         description = SUPPRESSED;
       }
       int exceptionStartIndex = firstNonWhiteSpaceChar + description.length();
       int messageStartIndex = firstCharFromIndex(line, exceptionStartIndex, ':');
       String className = line.substring(exceptionStartIndex, messageStartIndex);
       if (!DescriptorUtils.isValidJavaType(className)) {
         return null;
       }
       return new ExceptionLine(
           line.substring(0, firstNonWhiteSpaceChar),
           description,
           className,
           line.substring(messageStartIndex));
     }

     @Override
     List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
       List<StackTraceLine> exceptionLines = new ArrayList<>();
       retraceBase
           .retrace(Reference.classFromTypeName(exceptionClass))
           .forEach(
               element ->
                   exceptionLines.add(
                       new ExceptionLine(
                           initialWhiteSpace,
                           description,
                           element.getClassReference().getTypeName(),
                           message)));
       return exceptionLines;
     }

     @Override
     public String toString() {
       return initialWhiteSpace + description + exceptionClass + message;
     }

     @Override
     boolean isExceptionLine() {
       return true;
     }

     @Override
     ExceptionLine asExceptionLine() {
       return this;
     }
   }

   /**
    * Captures a stack trace line on the following form
    *
    * <ul>
    *   <li>at dalvik.system.NativeStart.main(NativeStart.java:99)
    *   <li>at dalvik.system.NativeStart.main(:99)
    *   <li>at dalvik.system.NativeStart.main(Foo.java:)
    *   <li>at dalvik.system.NativeStart.main(Native Method)
    *   <li>at classloader/named_module@version/foo.bar.baz(:20)
    *   <li>at classloader//foo.bar.baz(:20)
    * </ul>
    *
    * <p>Empirical evidence suggests that the "at" string is never localized.
    */
   static class AtLine extends StackTraceLine {

     private static final int NO_POSITION = -2;
     private static final int INVALID_POSITION = -1;

     private final String startingWhitespace;
     private final String at;
     private final String classLoaderName;
     private final String moduleName;
     private final String clazz;
     private final String method;
     private final String methodAsString;
     private final String fileName;
     private final int linePosition;
     private final boolean isAmbiguous;

     private AtLine(
         String startingWhitespace,
         String at,
         String classLoaderName,
         String moduleName,
         String clazz,
         String method,
         String methodAsString,
         String fileName,
         int linePosition,
         boolean isAmbiguous) {
       this.startingWhitespace = startingWhitespace;
       this.at = at;
       this.classLoaderName = classLoaderName;
       this.moduleName = moduleName;
       this.clazz = clazz;
       this.method = method;
       this.methodAsString = methodAsString;
       this.fileName = fileName;
       this.linePosition = linePosition;
       this.isAmbiguous = isAmbiguous;
     }

     static AtLine tryParse(String line) {
       // Check that the line is indented with some amount of white space.
       if (line.length() == 0 || !Character.isWhitespace(line.charAt(0))) {
         return null;
       }
       // Find the first non-white space character and check that we have the sequence 'a', 't', ' '.
       int firstNonWhiteSpace = firstNonWhiteSpaceCharacterFromIndex(line, 0);
       if (firstNonWhiteSpace + 2 >= line.length()
           || line.charAt(firstNonWhiteSpace) != 'a'
           || line.charAt(firstNonWhiteSpace + 1) != 't'
           || line.charAt(firstNonWhiteSpace + 2) != ' ') {
         return null;
       }
       int classClassLoaderOrModuleStartIndex =
           firstNonWhiteSpaceCharacterFromIndex(line, firstNonWhiteSpace + 2);
       if (classClassLoaderOrModuleStartIndex >= line.length()
           || classClassLoaderOrModuleStartIndex != firstNonWhiteSpace + 3) {
         return null;
       }
       int parensStart = firstCharFromIndex(line, classClassLoaderOrModuleStartIndex, '(');
       if (parensStart >= line.length()) {
         return null;
       }
       int parensEnd = firstCharFromIndex(line, parensStart, ')');
       if (parensEnd >= line.length()) {
         return null;
       }
       if (firstNonWhiteSpaceCharacterFromIndex(line, parensEnd) == line.length()) {
         return null;
       }
       int methodSeparator = line.lastIndexOf('.', parensStart);
       if (methodSeparator <= classClassLoaderOrModuleStartIndex) {
         return null;
       }
       // Check if we have a filename and position.
       String fileName = "";
       int position = NO_POSITION;
       int separatorIndex = firstCharFromIndex(line, parensStart, ':');
       if (separatorIndex < parensEnd) {
         fileName = line.substring(parensStart + 1, separatorIndex);
         try {
           String positionAsString = line.substring(separatorIndex + 1, parensEnd);
           position = Integer.parseInt(positionAsString);
         } catch (NumberFormatException e) {
           position = INVALID_POSITION;
         }
       } else {
         fileName = line.substring(parensStart + 1, parensEnd);
       }
       String classLoaderName = null;
       String moduleName = null;
       int classStartIndex = classClassLoaderOrModuleStartIndex;
       int classLoaderOrModuleEndIndex =
           firstCharFromIndex(line, classClassLoaderOrModuleStartIndex, '/');
       if (classLoaderOrModuleEndIndex < methodSeparator) {
         int moduleEndIndex = firstCharFromIndex(line, classLoaderOrModuleEndIndex + 1, '/');
         if (moduleEndIndex < methodSeparator) {
           // The stack trace contains both a class loader and module
           classLoaderName =
               line.substring(classClassLoaderOrModuleStartIndex, classLoaderOrModuleEndIndex);
           moduleName = line.substring(classLoaderOrModuleEndIndex + 1, moduleEndIndex);
           classStartIndex = moduleEndIndex + 1;
         } else {
           moduleName =
               line.substring(classClassLoaderOrModuleStartIndex, classLoaderOrModuleEndIndex);
           classStartIndex = classLoaderOrModuleEndIndex + 1;
         }
       }
       String className = line.substring(classStartIndex, methodSeparator);
       String methodName = line.substring(methodSeparator + 1, parensStart);
       return new AtLine(
           line.substring(0, firstNonWhiteSpace),
           line.substring(firstNonWhiteSpace, classClassLoaderOrModuleStartIndex),
           classLoaderName,
           moduleName,
           className,
           methodName,
           className + "." + methodName,
           fileName,
           position,
           false);
     }

     private boolean hasLinePosition() {
       return linePosition > -1;
     }

     @Override
     List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
       List<StackTraceLine> lines = new ArrayList<>();
       String retraceClassLoaderName = classLoaderName;
       if (retraceClassLoaderName != null) {
         ClassReference classLoaderReference = Reference.classFromTypeName(retraceClassLoaderName);
         retraceBase
             .retrace(classLoaderReference)
             .forEach(
                 classElement -> {
                   retraceClassAndMethods(
                       retraceBase, verbose, lines, classElement.getClassReference().getTypeName());
                 });
       } else {
         retraceClassAndMethods(retraceBase, verbose, lines, retraceClassLoaderName);
       }
       return lines;
     }

     private void retraceClassAndMethods(
         RetraceBase retraceBase,
         boolean verbose,
         List<StackTraceLine> lines,
         String classLoaderName) {
       ClassReference classReference = Reference.classFromTypeName(clazz);
       RetraceMethodResult retraceResult = retraceBase.retrace(classReference).lookupMethod(method);
       if (linePosition != NO_POSITION && linePosition != INVALID_POSITION) {
         retraceResult = retraceResult.narrowByLine(linePosition);
       }
       retraceResult.forEach(
           methodElement -> {
             MethodReference methodReference = methodElement.getMethodReference();
             lines.add(
                 new AtLine(
                     startingWhitespace,
                     at,
                     classLoaderName,
                     moduleName,
                     methodReference.getHolderClass().getTypeName(),
                     methodReference.getMethodName(),
                     methodDescriptionFromMethodReference(methodReference, verbose),
                     retraceBase.retraceSourceFile(
                         classReference, fileName, methodReference.getHolderClass(), true),
                     hasLinePosition()
                         ? methodElement.getOriginalLineNumber(linePosition)
                         : linePosition,
                     methodElement.getRetraceMethodResult().isAmbiguous()));
           });
     }

     @Override
     public String toString() {
       StringBuilder sb = new StringBuilder(startingWhitespace);
       sb.append(at);
       if (classLoaderName != null) {
         sb.append(classLoaderName);
         sb.append("/");
       }
       if (moduleName != null) {
         sb.append(moduleName);
         sb.append("/");
       }
       sb.append(methodAsString);
       sb.append("(");
       sb.append(fileName);
       if (linePosition != NO_POSITION) {
         sb.append(":");
       }
       if (linePosition > INVALID_POSITION) {
         sb.append(linePosition);
       }
       sb.append(")");
       return sb.toString();
     }

     @Override
     boolean isAtLine() {
       return true;
     }

     @Override
     AtLine asAtLine() {
       return this;
     }
   }

   static class MoreLine extends StackTraceLine {
     private final String line;

     MoreLine(String line) {
       this.line = line;
     }

     static StackTraceLine tryParse(String line) {
       int dotsSeen = 0;
       boolean isWhiteSpaceAllowed = true;
       for (int i = 0; i < line.length(); i++) {
         char ch = line.charAt(i);
         if (Character.isWhitespace(ch) && isWhiteSpaceAllowed) {
           continue;
         }
         isWhiteSpaceAllowed = false;
         if (ch != '.') {
           return null;
         }
         if (++dotsSeen == 3) {
           return new MoreLine(line);
         }
       }
       return null;
     }

     @Override
     List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
       return ImmutableList.of(new MoreLine(line));
     }

     @Override
     public String toString() {
       return line;
     }
   }

   static class CircularReferenceLine extends StackTraceLine {

     private final String startWhitespace;
     private final String exceptionClass;
     private final String endBracketAndWhitespace;

     private static final String CIRCULAR_REFERENCE = "[CIRCULAR REFERENCE:";

     public CircularReferenceLine(
         String startWhitespace, String exceptionClass, String endBracketAndWhitespace) {
       this.startWhitespace = startWhitespace;
       this.exceptionClass = exceptionClass;
       this.endBracketAndWhitespace = endBracketAndWhitespace;
     }

     static StackTraceLine tryParse(String line) {
       // Check that the line is indented with some amount of white space.
       if (line.length() == 0 || !Character.isWhitespace(line.charAt(0))) {
         return null;
       }
       // Find the first non-white space character and check that we have the sequence
       // '[CIRCULAR REFERENCE:Exception]'.
       int firstNonWhiteSpace = firstNonWhiteSpaceCharacterFromIndex(line, 0);
       if (!line.startsWith(CIRCULAR_REFERENCE, firstNonWhiteSpace)) {
         return null;
       }
       int exceptionStartIndex = firstNonWhiteSpace + CIRCULAR_REFERENCE.length();
       int lastBracketPosition = firstCharFromIndex(line, exceptionStartIndex, ']');
       if (lastBracketPosition == line.length()) {
         return null;
       }
       int onlyWhitespaceFromLastBracket =
           firstNonWhiteSpaceCharacterFromIndex(line, lastBracketPosition + 1);
       if (onlyWhitespaceFromLastBracket != line.length()) {
         return null;
       }
       return new CircularReferenceLine(
           line.substring(0, firstNonWhiteSpace),
           line.substring(exceptionStartIndex, lastBracketPosition),
           line.substring(lastBracketPosition));
     }

     @Override
     List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
       List<StackTraceLine> exceptionLines = new ArrayList<>();
       retraceBase
           .retrace(Reference.classFromTypeName(exceptionClass))
           .forEach(
               element ->
                   exceptionLines.add(
                       new CircularReferenceLine(
                           startWhitespace,
                           element.getClassReference().getTypeName(),
                           endBracketAndWhitespace)));
       return exceptionLines;
     }

     @Override
     public String toString() {
       return startWhitespace + CIRCULAR_REFERENCE + exceptionClass + endBracketAndWhitespace;
     }
   }

   static class UnknownLine extends StackTraceLine {
     private final String line;

     UnknownLine(String line) {
       this.line = line;
     }

     @Override
     List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
       return ImmutableList.of(new UnknownLine(line));
     }

     @Override
     public String toString() {
       return line;
     }
   }

   private StackTraceLine parseLine(int lineNumber, String line) {
     if (line == null) {
       diagnosticsHandler.error(RetraceInvalidStackTraceLineDiagnostics.createNull(lineNumber));
       throw new Retrace.RetraceAbortException();
     }
     // Most lines are 'at lines' so attempt to parse it first.
     StackTraceLine parsedLine = AtLine.tryParse(line);
     if (parsedLine != null) {
       return parsedLine;
     }
     parsedLine = ExceptionLine.tryParse(line);
     if (parsedLine != null) {
       return parsedLine;
     }
     parsedLine = CircularReferenceLine.tryParse(line);
     if (parsedLine != null) {
       return parsedLine;
     }
     parsedLine = MoreLine.tryParse(line);
     if (parsedLine == null) {
       diagnosticsHandler.warning(
           RetraceInvalidStackTraceLineDiagnostics.createParse(lineNumber, line));
     }
     parsedLine = new UnknownLine(line);
     return parsedLine;
   }
 }
	// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	package com.android.tools.r8.retrace;

	import static com.android.tools.r8.retrace.RetraceUtils.methodDescriptionFromMethodReference;
	import static com.google.common.base.Predicates.not;

	import com.android.tools.r8.DiagnosticsHandler;
	import com.android.tools.r8.references.ClassReference;
	import com.android.tools.r8.references.MethodReference;
	import com.android.tools.r8.references.Reference;
	import com.android.tools.r8.utils.DescriptorUtils;
	import com.android.tools.r8.utils.StringUtils;
	import com.google.common.collect.ImmutableList;
	import java.util.ArrayList;
	import java.util.List;
	import java.util.function.Predicate;

	public final class RetraceStackTrace {

	public static class StackTraceNode {

	private final List<StackTraceLine> lines;

	StackTraceNode(List<StackTraceLine> lines) {
	this.lines = lines;
	assert !lines.isEmpty();
	assert lines.size() == 1 \|\| lines.stream().allMatch(StackTraceLine::isAtLine);
	}

	public void append(List<String> strings) {
	assert !lines.isEmpty();
	if (lines.size() == 1) {
	strings.add(lines.get(0).toString());
	return;
	}
	// We must have an inlining or ambiguous match here, thus all lines are at-lines.
	assert lines.stream().allMatch(StackTraceLine::isAtLine);
	assert lines.stream()
	.allMatch(line -> line.asAtLine().isAmbiguous == lines.get(0).asAtLine().isAmbiguous);
	if (lines.get(0).asAtLine().isAmbiguous) {
	lines.sort(new AtStackTraceLineComparator());
	}
	boolean shouldPrintOr = false;
	for (StackTraceLine line : lines) {
	assert line.isAtLine();
	AtLine atLine = line.asAtLine();
	if (atLine.isAmbiguous && shouldPrintOr) {
	String atLineString = atLine.toString();
	int firstNonWhitespaceCharacter = StringUtils.firstNonWhitespaceCharacter(atLineString);
	strings.add(
	atLineString.substring(0, firstNonWhitespaceCharacter)
	+ "<OR> "
	+ atLineString.substring(firstNonWhitespaceCharacter));
	} else {
	strings.add(atLine.toString());
	}
	shouldPrintOr = true;
	}
	}
	}

	static class AtStackTraceLineComparator extends AmbiguousComparator<StackTraceLine> {

	AtStackTraceLineComparator() {
	super(
	(line, t) -> {
	assert line.isAtLine();
	AtLine atLine = line.asAtLine();
	switch (t) {
	case CLASS:
	return atLine.clazz;
	case METHOD:
	return atLine.method;
	case SOURCE:
	return atLine.fileName;
	case LINE:
	return atLine.linePosition + "";
	default:
	assert false;
	}
	throw new RuntimeException("Comparator key is unknown");
	});
	}
	}

	private final RetraceBase retraceBase;
	private final List<String> stackTrace;
	private final DiagnosticsHandler diagnosticsHandler;
	private final boolean verbose;

	RetraceStackTrace(
	RetraceBase retraceBase,
	List<String> stackTrace,
	DiagnosticsHandler diagnosticsHandler,
	boolean verbose) {
	this.retraceBase = retraceBase;
	this.stackTrace = stackTrace;
	this.diagnosticsHandler = diagnosticsHandler;
	this.verbose = verbose;
	}

	public RetraceCommandLineResult retrace() {
	ArrayList<StackTraceNode> result = new ArrayList<>();
	retraceLine(stackTrace, 0, result);
	List<String> retracedStrings = new ArrayList<>();
	for (StackTraceNode node : result) {
	node.append(retracedStrings);
	}
	return new RetraceCommandLineResult(retracedStrings);
	}

	private void retraceLine(List<String> stackTrace, int index, List<StackTraceNode> result) {
	if (stackTrace.size() <= index) {
	return;
	}
	StackTraceLine stackTraceLine = parseLine(index + 1, stackTrace.get(index));
	List<StackTraceLine> retraced = stackTraceLine.retrace(retraceBase, verbose);
	StackTraceNode node = new StackTraceNode(retraced);
	result.add(node);
	retraceLine(stackTrace, index + 1, result);
	}

	abstract static class StackTraceLine {

	abstract List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose);

	static int firstNonWhiteSpaceCharacterFromIndex(String line, int index) {
	return firstFromIndex(line, index, not(Character::isWhitespace));
	}

	static int firstCharFromIndex(String line, int index, char ch) {
	return firstFromIndex(line, index, c -> c == ch);
	}

	static int firstFromIndex(String line, int index, Predicate<Character> predicate) {
	for (int i = index; i < line.length(); i++) {
	if (predicate.test(line.charAt(i))) {
	return i;
	}
	}
	return line.length();
	}

	boolean isAtLine() {
	return false;
	}

	AtLine asAtLine() {
	return null;
	}

	boolean isExceptionLine() {
	return false;
	}

	ExceptionLine asExceptionLine() {
	return null;
	}
	}

	/**
	* Captures a stack trace line of the following formats:
	*
	* <ul>
	* <li>com.android.r8.R8Exception
	* <li>com.android.r8.R8Exception: Problem when compiling program
	* <li>Caused by: com.android.r8.R8InnerException: You have to write the program first
	* <li>com.android.r8.R8InnerException: You have to write the program first
	* </ul>
	*
	* <p>This will also contains false positives, such as
	*
	* <pre>
	* W( 8207) VFY: unable to resolve static method 11: Lprivateinterfacemethods/I$-CC;....
	* </pre>
	*
	* <p>The only invalid chars for type-identifiers for a java type-name is ';', '[' and '/', so we
	* cannot really disregard the above line.
	*
	* <p>Caused by and Suppressed seems to not change based on locale, so we use these as markers.
	*/
	static class ExceptionLine extends StackTraceLine {

	private static final String CAUSED_BY = "Caused by: ";
	private static final String SUPPRESSED = "Suppressed: ";

	private final String initialWhiteSpace;
	private final String description;
	private final String exceptionClass;
	private final String message;

	ExceptionLine(
	String initialWhiteSpace, String description, String exceptionClass, String message) {
	this.initialWhiteSpace = initialWhiteSpace;
	this.description = description;
	this.exceptionClass = exceptionClass;
	this.message = message;
	}

	static ExceptionLine tryParse(String line) {
	if (line.isEmpty()) {
	return null;
	}
	int firstNonWhiteSpaceChar = firstNonWhiteSpaceCharacterFromIndex(line, 0);
	String description = "";
	if (line.startsWith(CAUSED_BY, firstNonWhiteSpaceChar)) {
	description = CAUSED_BY;
	} else if (line.startsWith(SUPPRESSED, firstNonWhiteSpaceChar)) {
	description = SUPPRESSED;
	}
	int exceptionStartIndex = firstNonWhiteSpaceChar + description.length();
	int messageStartIndex = firstCharFromIndex(line, exceptionStartIndex, ':');
	String className = line.substring(exceptionStartIndex, messageStartIndex);
	if (!DescriptorUtils.isValidJavaType(className)) {
	return null;
	}
	return new ExceptionLine(
	line.substring(0, firstNonWhiteSpaceChar),
	description,
	className,
	line.substring(messageStartIndex));
	}

	@Override
	List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
	List<StackTraceLine> exceptionLines = new ArrayList<>();
	retraceBase
	.retrace(Reference.classFromTypeName(exceptionClass))
	.forEach(
	element ->
	exceptionLines.add(
	new ExceptionLine(
	initialWhiteSpace,
	description,
	element.getClassReference().getTypeName(),
	message)));
	return exceptionLines;
	}

	@Override
	public String toString() {
	return initialWhiteSpace + description + exceptionClass + message;
	}

	@Override
	boolean isExceptionLine() {
	return true;
	}

	@Override
	ExceptionLine asExceptionLine() {
	return this;
	}
	}

	/**
	* Captures a stack trace line on the following form
	*
	* <ul>
	* <li>at dalvik.system.NativeStart.main(NativeStart.java:99)
	* <li>at dalvik.system.NativeStart.main(:99)
	* <li>at dalvik.system.NativeStart.main(Foo.java:)
	* <li>at dalvik.system.NativeStart.main(Native Method)
	* <li>at classloader/named_module@version/foo.bar.baz(:20)
	* <li>at classloader//foo.bar.baz(:20)
	* </ul>
	*
	* <p>Empirical evidence suggests that the "at" string is never localized.
	*/
	static class AtLine extends StackTraceLine {

	private static final int NO_POSITION = -2;
	private static final int INVALID_POSITION = -1;

	private final String startingWhitespace;
	private final String at;
	private final String classLoaderName;
	private final String moduleName;
	private final String clazz;
	private final String method;
	private final String methodAsString;
	private final String fileName;
	private final int linePosition;
	private final boolean isAmbiguous;

	private AtLine(
	String startingWhitespace,
	String at,
	String classLoaderName,
	String moduleName,
	String clazz,
	String method,
	String methodAsString,
	String fileName,
	int linePosition,
	boolean isAmbiguous) {
	this.startingWhitespace = startingWhitespace;
	this.at = at;
	this.classLoaderName = classLoaderName;
	this.moduleName = moduleName;
	this.clazz = clazz;
	this.method = method;
	this.methodAsString = methodAsString;
	this.fileName = fileName;
	this.linePosition = linePosition;
	this.isAmbiguous = isAmbiguous;
	}

	static AtLine tryParse(String line) {
	// Check that the line is indented with some amount of white space.
	if (line.length() == 0 \|\| !Character.isWhitespace(line.charAt(0))) {
	return null;
	}
	// Find the first non-white space character and check that we have the sequence 'a', 't', ' '.
	int firstNonWhiteSpace = firstNonWhiteSpaceCharacterFromIndex(line, 0);
	if (firstNonWhiteSpace + 2 >= line.length()
	\|\| line.charAt(firstNonWhiteSpace) != 'a'
	\|\| line.charAt(firstNonWhiteSpace + 1) != 't'
	\|\| line.charAt(firstNonWhiteSpace + 2) != ' ') {
	return null;
	}
	int classClassLoaderOrModuleStartIndex =
	firstNonWhiteSpaceCharacterFromIndex(line, firstNonWhiteSpace + 2);
	if (classClassLoaderOrModuleStartIndex >= line.length()
	\|\| classClassLoaderOrModuleStartIndex != firstNonWhiteSpace + 3) {
	return null;
	}
	int parensStart = firstCharFromIndex(line, classClassLoaderOrModuleStartIndex, '(');
	if (parensStart >= line.length()) {
	return null;
	}
	int parensEnd = firstCharFromIndex(line, parensStart, ')');
	if (parensEnd >= line.length()) {
	return null;
	}
	if (firstNonWhiteSpaceCharacterFromIndex(line, parensEnd) == line.length()) {
	return null;
	}
	int methodSeparator = line.lastIndexOf('.', parensStart);
	if (methodSeparator <= classClassLoaderOrModuleStartIndex) {
	return null;
	}
	// Check if we have a filename and position.
	String fileName = "";
	int position = NO_POSITION;
	int separatorIndex = firstCharFromIndex(line, parensStart, ':');
	if (separatorIndex < parensEnd) {
	fileName = line.substring(parensStart + 1, separatorIndex);
	try {
	String positionAsString = line.substring(separatorIndex + 1, parensEnd);
	position = Integer.parseInt(positionAsString);
	} catch (NumberFormatException e) {
	position = INVALID_POSITION;
	}
	} else {
	fileName = line.substring(parensStart + 1, parensEnd);
	}
	String classLoaderName = null;
	String moduleName = null;
	int classStartIndex = classClassLoaderOrModuleStartIndex;
	int classLoaderOrModuleEndIndex =
	firstCharFromIndex(line, classClassLoaderOrModuleStartIndex, '/');
	if (classLoaderOrModuleEndIndex < methodSeparator) {
	int moduleEndIndex = firstCharFromIndex(line, classLoaderOrModuleEndIndex + 1, '/');
	if (moduleEndIndex < methodSeparator) {
	// The stack trace contains both a class loader and module
	classLoaderName =
	line.substring(classClassLoaderOrModuleStartIndex, classLoaderOrModuleEndIndex);
	moduleName = line.substring(classLoaderOrModuleEndIndex + 1, moduleEndIndex);
	classStartIndex = moduleEndIndex + 1;
	} else {
	moduleName =
	line.substring(classClassLoaderOrModuleStartIndex, classLoaderOrModuleEndIndex);
	classStartIndex = classLoaderOrModuleEndIndex + 1;
	}
	}
	String className = line.substring(classStartIndex, methodSeparator);
	String methodName = line.substring(methodSeparator + 1, parensStart);
	return new AtLine(
	line.substring(0, firstNonWhiteSpace),
	line.substring(firstNonWhiteSpace, classClassLoaderOrModuleStartIndex),
	classLoaderName,
	moduleName,
	className,
	methodName,
	className + "." + methodName,
	fileName,
	position,
	false);
	}

	private boolean hasLinePosition() {
	return linePosition > -1;
	}

	@Override
	List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
	List<StackTraceLine> lines = new ArrayList<>();
	String retraceClassLoaderName = classLoaderName;
	if (retraceClassLoaderName != null) {
	ClassReference classLoaderReference = Reference.classFromTypeName(retraceClassLoaderName);
	retraceBase
	.retrace(classLoaderReference)
	.forEach(
	classElement -> {
	retraceClassAndMethods(
	retraceBase, verbose, lines, classElement.getClassReference().getTypeName());
	});
	} else {
	retraceClassAndMethods(retraceBase, verbose, lines, retraceClassLoaderName);
	}
	return lines;
	}

	private void retraceClassAndMethods(
	RetraceBase retraceBase,
	boolean verbose,
	List<StackTraceLine> lines,
	String classLoaderName) {
	ClassReference classReference = Reference.classFromTypeName(clazz);
	RetraceMethodResult retraceResult = retraceBase.retrace(classReference).lookupMethod(method);
	if (linePosition != NO_POSITION && linePosition != INVALID_POSITION) {
	retraceResult = retraceResult.narrowByLine(linePosition);
	}
	retraceResult.forEach(
	methodElement -> {
	MethodReference methodReference = methodElement.getMethodReference();
	lines.add(
	new AtLine(
	startingWhitespace,
	at,
	classLoaderName,
	moduleName,
	methodReference.getHolderClass().getTypeName(),
	methodReference.getMethodName(),
	methodDescriptionFromMethodReference(methodReference, verbose),
	retraceBase.retraceSourceFile(
	classReference, fileName, methodReference.getHolderClass(), true),
	hasLinePosition()
	? methodElement.getOriginalLineNumber(linePosition)
	: linePosition,
	methodElement.getRetraceMethodResult().isAmbiguous()));
	});
	}

	@Override
	public String toString() {
	StringBuilder sb = new StringBuilder(startingWhitespace);
	sb.append(at);
	if (classLoaderName != null) {
	sb.append(classLoaderName);
	sb.append("/");
	}
	if (moduleName != null) {
	sb.append(moduleName);
	sb.append("/");
	}
	sb.append(methodAsString);
	sb.append("(");
	sb.append(fileName);
	if (linePosition != NO_POSITION) {
	sb.append(":");
	}
	if (linePosition > INVALID_POSITION) {
	sb.append(linePosition);
	}
	sb.append(")");
	return sb.toString();
	}

	@Override
	boolean isAtLine() {
	return true;
	}

	@Override
	AtLine asAtLine() {
	return this;
	}
	}

	static class MoreLine extends StackTraceLine {
	private final String line;

	MoreLine(String line) {
	this.line = line;
	}

	static StackTraceLine tryParse(String line) {
	int dotsSeen = 0;
	boolean isWhiteSpaceAllowed = true;
	for (int i = 0; i < line.length(); i++) {
	char ch = line.charAt(i);
	if (Character.isWhitespace(ch) && isWhiteSpaceAllowed) {
	continue;
	}
	isWhiteSpaceAllowed = false;
	if (ch != '.') {
	return null;
	}
	if (++dotsSeen == 3) {
	return new MoreLine(line);
	}
	}
	return null;
	}

	@Override
	List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
	return ImmutableList.of(new MoreLine(line));
	}

	@Override
	public String toString() {
	return line;
	}
	}

	static class CircularReferenceLine extends StackTraceLine {

	private final String startWhitespace;
	private final String exceptionClass;
	private final String endBracketAndWhitespace;

	private static final String CIRCULAR_REFERENCE = "[CIRCULAR REFERENCE:";

	public CircularReferenceLine(
	String startWhitespace, String exceptionClass, String endBracketAndWhitespace) {
	this.startWhitespace = startWhitespace;
	this.exceptionClass = exceptionClass;
	this.endBracketAndWhitespace = endBracketAndWhitespace;
	}

	static StackTraceLine tryParse(String line) {
	// Check that the line is indented with some amount of white space.
	if (line.length() == 0 \|\| !Character.isWhitespace(line.charAt(0))) {
	return null;
	}
	// Find the first non-white space character and check that we have the sequence
	// '[CIRCULAR REFERENCE:Exception]'.
	int firstNonWhiteSpace = firstNonWhiteSpaceCharacterFromIndex(line, 0);
	if (!line.startsWith(CIRCULAR_REFERENCE, firstNonWhiteSpace)) {
	return null;
	}
	int exceptionStartIndex = firstNonWhiteSpace + CIRCULAR_REFERENCE.length();
	int lastBracketPosition = firstCharFromIndex(line, exceptionStartIndex, ']');
	if (lastBracketPosition == line.length()) {
	return null;
	}
	int onlyWhitespaceFromLastBracket =
	firstNonWhiteSpaceCharacterFromIndex(line, lastBracketPosition + 1);
	if (onlyWhitespaceFromLastBracket != line.length()) {
	return null;
	}
	return new CircularReferenceLine(
	line.substring(0, firstNonWhiteSpace),
	line.substring(exceptionStartIndex, lastBracketPosition),
	line.substring(lastBracketPosition));
	}

	@Override
	List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
	List<StackTraceLine> exceptionLines = new ArrayList<>();
	retraceBase
	.retrace(Reference.classFromTypeName(exceptionClass))
	.forEach(
	element ->
	exceptionLines.add(
	new CircularReferenceLine(
	startWhitespace,
	element.getClassReference().getTypeName(),
	endBracketAndWhitespace)));
	return exceptionLines;
	}

	@Override
	public String toString() {
	return startWhitespace + CIRCULAR_REFERENCE + exceptionClass + endBracketAndWhitespace;
	}
	}

	static class UnknownLine extends StackTraceLine {
	private final String line;

	UnknownLine(String line) {
	this.line = line;
	}

	@Override
	List<StackTraceLine> retrace(RetraceBase retraceBase, boolean verbose) {
	return ImmutableList.of(new UnknownLine(line));
	}

	@Override
	public String toString() {
	return line;
	}
	}

	private StackTraceLine parseLine(int lineNumber, String line) {
	if (line == null) {
	diagnosticsHandler.error(RetraceInvalidStackTraceLineDiagnostics.createNull(lineNumber));
	throw new Retrace.RetraceAbortException();
	}
	// Most lines are 'at lines' so attempt to parse it first.
	StackTraceLine parsedLine = AtLine.tryParse(line);
	if (parsedLine != null) {
	return parsedLine;
	}
	parsedLine = ExceptionLine.tryParse(line);
	if (parsedLine != null) {
	return parsedLine;
	}
	parsedLine = CircularReferenceLine.tryParse(line);
	if (parsedLine != null) {
	return parsedLine;
	}
	parsedLine = MoreLine.tryParse(line);
	if (parsedLine == null) {
	diagnosticsHandler.warning(
	RetraceInvalidStackTraceLineDiagnostics.createParse(lineNumber, line));
	}
	parsedLine = new UnknownLine(line);
	return parsedLine;
	}
	}