Finish off private intransitive dependencies with an implementation of
dependency replay.
For the sake of illustration, imagine a chain of requests
A -> B -> C -> ...
Supposing each request is never cached, then every invocation of the
compiler with the same inputs will always kick off the exact same set of
requests. For the purposes of dependency tracking, that also means every
single lookup request will run without issue, and all dependencies will
be accurately reported. But we live in a world with cached requests.
Suppose request B* is cached. The first time we encounter that request,
its evaluation order looks identical:
A -> B* -> C -> ...
If we are in a mode that compiles single primaries, this is not
a problem because every request graph will look like this.
But if we are in a mode where we are compiling multiple primaries, then
subsequent request graphs will *actually* hit the cache and never
execute request C or any of its dependent computations!
A -> B*
Supposing C was a lookup request, that means the name(s) looked up
downstream of B* will *never* be recorded in the referenced name tracker
which can lead to miscompilation. Note that this is not a problem
inherent to the design of the request evaluator - caches in the compiler
have *always* hidden dependent lookups. In fact, the request evaluator
provides us our first opportunity to resolve this correctness bug!
This was causing issues with MSVC. Have subclasses
be friends with all specializations of
AnyRequestBase, and define `getRawStorage` in
the base class to make it accessible to `friend`
top-level functions.
This wrapper is used to type erase a reference to
a request on the stack, and can be converted into
an AnyRequest when persistent storage is required.
Switch the evaluator over to using ActiveRequest
for its stack of active requests, meaning it now
only needs to heap allocate requests when they
enter the cache, or if it's building the (disabled
by default) dependency graph.
- No need to hash input values first
- Pass many values to a single hash_combine to save on intermediates
- Use hash_combine_range instead of a loop of hash_combines
No functionality change.
Use the "nearest source location" information on a request to map it
to a particular source buffer, then use that information in the
GraphViz dependency graphs so we can see cross-file dependencies more
clearly.
Visual Studio objects with the following:
```
AST/AnyRequest.h(243): error: C2580: 'swift::AnyRequest::AnyRequest(const swift::AnyRequest &)': multiple versions of a defaulted special member functions are not allowed
AST/AnyRequest(243): warning C4521: 'swift::AnyRequest': multiple copy constructors specified
```
Remove the non-const implementation, the default'ed definition should be
sufficient. Additionally, remove the nonsense const move constructor.
Because we cannot explicitly control which constructor is used, and Visual
Studio also instantiates the templated constructor (even with the copy and move
constructors available, we end up with ambiguity in the constructor when trying
to instantiate a `llvm::SetVector<AnyRequest>` in the Evaluator.
```
swift\include\swift\AST\AnyRequest.h(98): error C2027: use of undefined type 'swift::TypeID<Request>'
with
[
Request=ValueType
]
swift\include\swift\AST\AnyRequest.h(98): note: see declaration of 'swift::TypeID<Request>'
with
[
Request=ValueType
]
swift\include\swift\AST\AnyRequest.h(97): note: while compiling class template member function 'swift::AnyRequest::Holder<ValueType>::Holder(const Request &)'
with
[
Request=ValueType
]
swift\include\swift\AST\AnyRequest.h(167): note: see reference to function template instantiation 'swift::AnyRequest::Holder<ValueType>::Holder(const Request &)' being compiled
with
[
Request=ValueType
]
swift\include\swift\AST\AnyRequest.h(168): note: see reference to class template instantiation 'swift::AnyRequest::Holder<ValueType>' being compiled
C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.13.26128\include\xmemory0(917): note: see reference to function template instantiation 'swift::AnyRequest::AnyRequest<T&>(swift::AnyRequest&)' being compiled
with
[
T=swift::AnyRequest
]
C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.13.26128\include\xmemory(120): note: see reference to function template instantiation 'void std::_Default_allocator_traits<_Alloc>::construct<_Ty,T&>(_Alloc &,_Objty *const ,T &)' being compiled
with
[
_Alloc=std::allocator<swift::AnyRequest>,
_Ty=swift::AnyRequest,
T=swift::AnyRequest,
_Objty=swift::AnyRequest
]
C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.13.26128\include\xmemory(120): note: see reference to function template instantiation 'void std::_Default_allocator_traits<_Alloc>::construct<_Ty,T&>(_Alloc &,_Objty *const ,T &)' being compiled
with
[
_Alloc=std::allocator<swift::AnyRequest>,
_Ty=swift::AnyRequest,
T=swift::AnyRequest,
_Objty=swift::AnyRequest
]
C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.13.26128\include\xmemory(153): note: see reference to function template instantiation '_FwdIt std::_Uninitialized_copy_al_unchecked<_Iter,_Iter,_Alloc>(_InIt,_InIt,_FwdIt,_Alloc &,std::_General_ptr_iterator_tag,std::_Any_tag)' being compiled
with
[
_FwdIt=swift::AnyRequest *,
_Iter=swift::AnyRequest *,
_Alloc=std::allocator<swift::AnyRequest>,
_InIt=swift::AnyRequest *
]
C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.13.26128\include\vector(1939): note: see reference to function template instantiation '_FwdIt *std::_Uninitialized_copy<swift::AnyRequest*,swift::AnyRequest*,std::allocator<_Ty>>(_InIt,_InIt,_FwdIt,_Alloc &)' being compiled
with
[
_FwdIt=swift::AnyRequest *,
_Ty=swift::AnyRequest,
_InIt=swift::AnyRequest *,
_Alloc=std::allocator<swift::AnyRequest>
]
C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.13.26128\include\vector(1938): note: while compiling class template member function 'void std::vector<T,std::allocator<_Ty>>::_Umove_if_noexcept1(swift::AnyRequest *,swift::AnyRequest *,swift::AnyRequest *,std::false_type)'
with
[
T=swift::AnyRequest,
_Ty=swift::AnyRequest
]
C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.13.26128\include\vector(1944): note: see reference to function template instantiation 'void std::vector<T,std::allocator<_Ty>>::_Umove_if_noexcept1(swift::AnyRequest *,swift::AnyRequest *,swift::AnyRequest *,std::false_type)' being compiled
with
[
T=swift::AnyRequest,
_Ty=swift::AnyRequest
]
llvm\include\llvm\ADT\SetVector.h(49): note: see reference to class template instantiation 'std::vector<T,std::allocator<_Ty>>' being compiled
with
[
T=swift::AnyRequest,
_Ty=swift::AnyRequest
]
swift\include\swift\AST\Evaluator.h(208): note: see reference to class template instantiation 'llvm::SetVector<swift::AnyRequest,std::vector<T,std::allocator<_Ty>>,llvm::DenseSet<T,llvm::DenseMapInfo<swift::AnyRequest>>>' being compiled
with
[
T=swift::AnyRequest,
_Ty=swift::AnyRequest
]
swift\include\swift\AST\AnyRequest.h(97): error C2065: 'value': undeclared identifier
```
Hoist the type alias into the template specialization so that we can use that
in the SFINAE expression rather than duplicating it.
The default move constructor and move assignment operator of AnyRequest
would leave the source object in an odd state that’s destructible but
does not maintain the invariant that all “normal” states store a real
instance. This state breaks DenseMap, which assumes that a moved-from
object is still washable.
Introduce another form of debugging dump for the evaluator, rendering the
complete dependency graph using GraphViz, including all dependencies and
values cached within the evaluator.
Introduce a CRTP base class, SimpleRequest, which simplifies the task of
defining a new request kind by handling the storage of the values (in a
std::tuple), their hashing, equality, printing, etc. The values are passed
along to the subclass’s operator() so they’re mostly treated as (const)
parameters, making mutation of the request state impossible.
Extend AnyValue and AnyRequest with printing logic, so we can print any
request for debugging purposes, and
Meant as a replacement for the barely-started iterative type checker,
introduce a simpler "evaluator" that can evaluate individual requests
(essentially, function objects with some additional API), caching
results as appropriate and detecting cycles.
