[MSBuild Binary Log Query Language] Hand-off documentation

### What has been done

1. Binary log reader that reads build events from `.binlog` files. Currently, events related to
* projects,
* targets,
* tasks,
* messages,
* warnings, and
* errors

are supported.

2. Definitions of "components" and "logs". Here, by "components" I mean
* projects,
* targets, and
* tasks.

By "logs", I mean
* messages,
* warnings,
* errors.

Both "components" and "logs" are called "query results" in the context of this project. The properties and fields of these classes can be found in the `Result` folder.

3. Construction of dependency graphs of projects and targets, where
* projects have "before-this" relationships, and
* targets have both "before-this" and "after-this" relationships.

Here,
* "A before B" means that B depends on A and hence A must be run before the execution of B. This is represented by the "DependOn" and "BeforeTarget" attributes in MSBuild.
* "A after B" means that if B runs, then A runs. This is represented by the "AfterTarget" attribute in MSBuild.

_**Note**_: "A before B" and "B after A" are _not_ the reverse of each other.

4. Basic structures of directed acyclic graphs (DAG) and DAG nodes. Operations supported include:
* topological sorting,
* reversed graph, and
* computing all reachable nodes from a specific node.

5. Scanning of language, i.e. translating a expression string to a list of tokens. The scanning is implemented manually (i.e., not using lexical analyzer generators). Currently supported tokens can be found in the `Token` folder.

6. Parsing of language, i.e. translating a list of tokens to abstract syntax trees (AST). The parser is manually implemented as a recursive descent parser, a.k.a. LL(1) parser, and we don't use parser generators. Currently supported AST nodes can be found in the `Ast` folder. I will explain AST nodes in detail in a later section.

7. Currently supported features:
* Filtering of projects, targets and tasks by name, id and path. For instance,
```
/Project
/Project[Name="MSBuildBinLogQuery"]
/Project[Id=1]/Target[Name="CoreCompile"]
/Task[Name="RestoreTask"] (equivalent to /Project/Target/Task["RestoreTask"])
```
* Messages, warnings and errors.
_**Note**_: Here,
* a single slash (`/`) means messages, warnings and errors _directly_ emitted by the containing component, but _not_ by their descendants.
* a double slash (`//`) means messages, warnings and errors emitted by all components contained in the current component, including the current one, either directly or indirectly.

For instance,
```
/Message (messages directly emitted by MSBuild)
//Message (all messages)
/Project[Id=1]/Warning (warnings directly emitted by project instance #1
/Project[Id=1]//Warning (all warnings emitted under project instance #1)
/Task[Name="Csc"]//Error (all errors emitted by tasks named "Csc")
```
* Direct "Before" dependency queries on projects. Here, the word "direct" means that the relationship is directly specified in the project file and therefore revealed in build events from `.binlog` files. For instance,
```
/Project[Before=[/Project[Name="MSBuildBinLogQuery.Demo"]]]
```
queries all projects that must run directly before the project named `MSBuildBinLogQuery.Demo`; i.e., it queries all projects that the project named `MSBuildBinLogQuery.Demo` depends on.

_**Note:**_ This part is in branch `yuchong-pan:dependency-queries` and PR #85.

### What is planned but has not been done

1. Full support for the "Before", "After" and "DependOn" constraints for projects and targets. Here, the "Before" and "After" relationships have been discussed above, and the "DependOn" relationship is the reverse of the "Before" relationship. Additionally, both direct and indirect queries should be supported for all three kinds of relationships. The meaning of "direct" has been described above, and the word "indirect" means that the relationship is from a walk along several directed edges on the dependency graph. That is, it can be queried by computing all reachable nodes on the DAG, which has been implemented.

The proposed syntax is as follows:
```
/Project[DependOn=[/Project[Name="MSBuildBinLogQuery"]]]
/Project[*DependOn=[/Project[Name="MSBuildBinLogQuery"]]]
```
Here, the first expression queries projects that _directly_ depend on the project named `MSBuildBinLogQuery`, and the second expression queries _all_ projects that depend on the project named `MSBuildBinLogQuery`, either directly or indirectly.

The syntax for targets and the other two types of constraints is analog. The proposed syntax is subject to discussion.

2. Queries on components based on their descendants. For instance, something similar to the following expression queries all project instances that have a target named `CoreCompile`.
```
/Project[Child=[/Target[Name="CoreCompile"]]]
```

3. Queries on the properties, global properties and items of projects, and properties of tasks, etc. The proposed syntax is given as follows. The syntax is subject to change.
```
/Project[Properties={TargetFramework:"netcoreapp3.0", RuntimeIdentifier:"win-x64"}]
/Project[GlobalProperties={RuntimeIdentifier:"win-x64"}]
/Project[Items={PackageReference:"Microsoft.Win32.Registry"}] (is there a way to specify the version?)
/Task[Parameters={BuildInParallel="True"}] (or, allow Boolean values)
```

4. Queries on messages based on errors and warnings. We may have something like
```
//Error[Text="; is missing"]/Message
```
However, I'm not sure if this can be read from binary logs. @rainersigwald Could you confirm this?

5. Support for built-in functions. This will be very useful to filter components. I imagine the syntax for functions will be something like the following one.
```
//Message[Text=Contains("Hello World")]
//Error[Text=EndsWith("is missing")]
/Project[GlobalProperties=Contains({RuntimeIdentifier:"win-x64"})]
```

6. Intersections and unions of constraints. The syntax for this feature has not been discussed. Currently, we use the standard comma (`,`) to indicate intersections.

7. Intersections and unions of query results. The proposed syntax is given as follows.
```
/Target[Name="Compile"] | /Target[Name="Optimize"]
/Project[Before=[/Project=[Id=1]]] & /Project[Before=[/Project=[Id=2]]]
```

7. Integrate the library into the [MSBuild Binary and Structured Log Viewer](http://msbuildlog.com/).

8. Create a console app based on this library for queries on MSBuild binary logs.

9. Other `TODO` items in the codebase.

### Design and philosophy of query language

The design of the query language generally follows the syntax of [XPath (XML Path Language)](https://en.wikipedia.org/wiki/XPath). However, there are significant differences that I would like to highlight.

1. XPath allows arbitrary nodes in XML. In this query language, we only allow nodes of `Project`, `Target`, `Task`, `Message`, `Warning` and `Error`, and these are considered as keywords of the language.

2. XPath allows `/` to select directly from the current node and `//` to selects all descendants of the current node. However, the component structure is very strict; it always follow the three-level `Project`-`Target`-`Task` structure. Hence, in our query language only the single slash (`/`) is allowed before `Project`, `Target` and `Task`.

However, `Message`, `Warning` and `Error` can be emitted by any level in the above structure, so it is reasonable to query those directly emitted by a component, or emitted by descendants of a component. Hence, we use `/` to query those directly emitted by a component, and `//` to query those emitted by descendants of a component, either directly or indirectly.

In addition, because the component structure is very strict, we may omit components that do not have constraints. Hence, we may desugar expressions to complete the omitted nodes. For instance,
```
/Task[Name="Csc"]
```
can be desugared to
```
/Project/Target/Task[Name="Csc"]
```
The desugaring is handled during parsing.

### Formal grammar

The context-free grammar of the query language is given as follows. Note that only the syntax of the features that have already been implemented is included. Also note that this language is designed to be case-insensitive.

```
::= "/"
| "//"
::= "message"
| "warning"
| "error"
::= "/" "task"
| "/" "task"
::= "/" "target"
| "/" "target"
| "/" "target"
::= "/" "project"
| "/" "project"
| "/" "project"
| "/" "project"
::=
|
|
|
::= "name" "="
::= "id" "="
::= "path" "="
::= "before" "=" "[" "]"
| "*" "before" "=" "[" "]"
::=
|
::=
| ","
::= empty
| "[" "]
::=
|
::=
| ","
::= empty
| "[" "]
::=
|
|
::=
| ","
::= empty
| "[" "]
```

Since we use a recursive descent parser (i.e., LL(1) parser), we need to refactor the grammar above to an LL(1) grammar.

```
::= "/"
| "//"
::= "message"
| "warning"
| "error"
::=
::= empty
|
::=
|
::= empty
| "/"
| "//"
::=
|
|
::= empty
| "/"
| "//"
::=
|
|
|
::= "/"
| "//"
::= "project"
::= "target"
::= "task"
::= "name" "="
::= "id" "="
::= "path" "="
::= "before" "=" "[" "/" "]"
| "*" "before" "=" "[" "/" "]"
::=
|
::= empty
|
::= empty
| ","
::= empty
| "[" "]
::=
|
::= empty
|
::= empty
| ","
::= empty
| "[" "]"
::=
|
|
::= empty
|
::= empty
| ","
::= empty
| "[" "]"
```

### Detailed explanations of codebase

I have to admit that the codebase is hard to understand and my apologies for this. Hence, I plan to explain the codebase and the design philosophy behind it in detail.

1. `Utility`

This folder contains two classes, `ItemManager` and `PropertyManager`. These two classes are basically wrappers for `Dictionary>` and `Dictionary` and hence are very easy to understand.

2. `Token`

This folder specifies all tokens used to perform lexical analysis of query expressions. As you may have noticed, many of the tokens do not contain values. Hence, we use the [singleton pattern](https://en.wikipedia.org/wiki/Singleton_pattern) to reduce the memory allocated when using the instances of these tokens. The only tokens that have values are `IntegerToken`, `StringToken` and `PathToken`, which we override `Equals` and `GetHashCode` for the equality comparison.

3. `Scan`

This folder contains a scanner (a.k.a. lexical analyzer, or lexer) that performs lexical analysis on query expressions. That is, it translates source query expression code to a list of tokens that are defined in the `Token` folder. The scanner is implemented manually (i.e., not using a lexical analyzer generator). The implementation of the scanner is very easy to undestand and generally follows the implementation of the XPath scanner, which is available at https://github.com/dotnet/corefx/blob/0cc22ccba707d7552159363d586262fa9c4e8a2a/src/System.Private.Xml/src/System/Xml/XPath/Internal/XPathScanner.cs.

4. `Result`

This folder consists of three parts:
1. `Component`: Components include `Build`, `Project`, `Target` and `Task`. Here, projects, targets and tasks are standard MSBuild concepts, and builds are essentially collections of projects. Each component has a parent which follows the strict three-level component structure described above, and contains lists of messages, warnings and errors. To support efficient queries on indirect messages, warnings and errors, each component also contains lists of _all_ messages, warnings and errors that occur under the current component, either directly or indirectly.
2. `Log`: Logs include `Message`, `Warning` and `Error`. Each log has a field for its text and a field for its containing component. Additionally, each `Message` has a field for its importance.
3. Interfaces: To allow filtering of components and increase code reuse, several interfaces are introduced, including `IResultWithId`, `IResultWithName`, `IResultWithPath` and `IResultWithBeforeThis`. Each of the interfaces is implemented by components and/or logs that contain the corresponding field.

5. `Parse`

This folder contains a parser that parses lists of tokens generated by the scanner. That is, it translates a list of tokens to an abstract syntax tree (AST). The AST nodes are defined in the `Ast` folder and will be explained in detail in a later section. The parser is a recursive descent parser (a.k.a. LL(1) parser) and is implemented manually (i.e., not using a parser generator). The parser uses the LL(1) grammar specified above and its implementation generally follows the implementation of the XPath parser, which is available at https://github.com/dotnet/corefx/blob/0cc22ccba707d7552159363d586262fa9c4e8a2a/src/System.Private.Xml/src/System/Xml/XPath/Internal/XPathParser.cs.

6. `Interpret`

This folder simply contains a wrapper of the `Filter` method of the AST nodes.

7. `Graph`

This folder contains a general directed acyclic graph (DAG) definition, a general DAG node definition and several nodes for project and target dependencies.

* The `DirectedAcyclicGraph` class represents a DAG and supports the following operations:
* topological sorting,
* reachable nodes from a specific node, and
* reversed graph.
* The `IDirectedAcyclicGraphNode` class represents a DAG node and is essentially a list of adjacent nodes. The two interfaces `INodeWithComponent` and `IShallowCopyableGraphNode` allow fetching the corresponding component of a node and computing the reversed graph, respectively.
* `ProjectNode_BeforeThis`, `TargetNode_AfterThis` and `TargetNode_BeforeThis` are DAG node definitions that represent the "Before" relationship of projects, the "After" relationship of targets and the "Before" relationship of targets, respectively.

8. `Construction`

This folder contains a binary log reader that reads a list of build events from `.binlog` files, and a graph builder that constructs project and target dependency graphs from a list of build events. The implementations of these two classes should be easy to follow.

9. `Ast`

This folder contains definitions of AST nodes used to parse query expressions. This is probably the most complicated part of code in the codebase because of many generic type parameters used. The reason of using many generic type parameters is to reduce runtime checks and increase compile-time checks. Following are detailed explanations of each type parameter, which have the same meanings across this folder.

* `TIn`: the type of every entry in the input list before filtering.
* `TOut`: the type of every entry in the output list after filtering.
* `TThis`: the type of the corresponding component of the current node.
* `TBefore`: the parent type (in the three-level component structure) of the corresponding component of the current node.
* `TParent`: the corresponding component type of the parent AST node of the current constraint node.
* `TGraphNode`: the type of the corresponding DAG node of the current dependency constraint.
* `TAstNode`: the type of the corresponding AST node of the current dependency constraint.

_**Note:**_ Be aware of the difference between `TBefore` and `TParent`.

With this information in mind, it is hopefully easy to explain the meanings of each class and interface.

* `IFilter` is used to extract corresponding components from parent components in the three-level component structure, implemented by each component node and in the future by each log node.
* `IFilter` is used to filter same-level components, implemented by each constraint node.
* `IAstNode` is implemented by all AST nodes.
* `IAstNode` represents an AST node that _may_ have `TBefore` as the parent type. The reason to have this as an interface is that `MessageNode`, `WarningNode` and `ErrorNode` may have any of `Build`, `Project`, `Target` and `Task` as the parent type.
* `IAstNode` represents an AST component node with the meanings of the two type parameters described above.
* `ConstraintNode` represents a constraint, including `Id`, `Name`, `Path` and dependency constraints.
* `DependencyNode` represents a dependency constraint, including the `Before`, `After` and `DependOn` constraints.
* `ComponentNode` represents a component node, including `Project`, `Target` and `Task`.
* `LogNode` represents a logde no, including `Message`, `Warning` and `Error`.

### Contact information of original author

In case there is confusion about the codebase, the design of the code structure, the design of the DSL, etc., I am always happy to help. As I have left Microsoft by the time you read this document, following is my personal contact information:

* Email: panyuchong@gmail.com
* GitHub: @yuchong-pan

Please feel free to contact me regarding this project.