<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div dir="auto">
<div>Simon's insight is great: if deep dependencies are captured by shallow dependencies then the cloud build system is correct even if only direct shallow inputs are tracked.</div>
<div dir="auto"><br>
</div>
<div dir="auto">That's a very non-trivial invariant, and I guess this means we can't rely on fsatrace linting for GHC compilation rules, because all deep dependencies will be reported as untracked. </div>
<div dir="auto"><br>
</div>
<div dir="auto">Cheers, </div>
<div dir="auto">Andrey<br>
<div class="gmail_extra" dir="auto"><br>
<div class="gmail_quote">On 27 Mar 2019 18:27, Simon Peyton Jones <simonpj@microsoft.com> wrote:<br type="attribution">
<blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>
<div>
<p style="margin-left:36pt">With that in mind, and considering a cloud build system where "<b><span style="color:#1f497d">all direct inputs and direct outputs must be declared</span></b>"</p>
<p> </p>
<p><b><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:red">But I question that assumption</span></b><span style="font-size:11pt;font-family:'calibri' , sans-serif">.   As I mentioned, with GHC at least, the if a deep dependency changes
 then one of the shallow dependencies will change.  So I claim that even for cloud build it should be enough to depend only on shallow dependencies.</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif">This is only true because GHC offers this guarantee.  We’d need to be sure that every deep dependency was either ‘needed’ or was reflected in the contents (perhaps via a fingerprint) another
 ‘needed’ thing.</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif">Simon</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif"> </span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4pt">
<div>
<div style="border:none;border-top:solid #e1e1e1 1pt;padding:3pt 0cm 0cm 0cm">
<p><b><span style="font-size:11pt;font-family:'calibri' , sans-serif">From:</span></b><span style="font-size:11pt;font-family:'calibri' , sans-serif"> ghc-devs <ghc-devs-bounces@haskell.org>
<b>On Behalf Of </b>David Eichmann<br>
<b>Sent:</b> 27 March 2019 17:12<br>
<b>To:</b> Andrey Mokhov <andrey.mokhov@newcastle.ac.uk>; Neil Mitchell <ndmitchell@gmail.com><br>
<b>Cc:</b> GHC developers <ghc-devs@haskell.org><br>
<b>Subject:</b> Re: Hadrian Transitive Dependencies</span></p>
</div>
</div>
<p> </p>
<p>Hello,<span style="font-size:11pt"></span></p>
<p>To reiterate some definitions consider this scenario:</p>
<ul type="disc">
<li>A.hs imports B.hs and B.hs imports C.hs</li><li>`ghc -M A.hs` reports that A.o depends on: A.hs, B.hi</li><li>`ghc -c A.hs` produces A.o and accesses A.hs, B.hi, and C.hi</li></ul>
<p>There seems to be some confusion about the term "Direct Dependency" I'll use these definitions:</p>
<p>"Shallow Dependency": With respect to a haskell object file X.o, the shallow dependencies are the source file X.hs and interface files Y.hi for all modules Y imported by X.</p>
<ul type="disc">
<li>These are the dependencies of X.o as reported by `ghc -M X.hs`</li><li>In the above scenario:</li></ul>
<ul type="disc">
<li>
<ul type="circle">
<li>A.o depends on: A.hs, B.hi</li></ul>
</li></ul>
<p>"Deep Dependency": With respect to a haskell object file X.o, the deep dependencies are all hi files required by ghc to build X.o excluding direct dependencies:</p>
<ul type="disc">
<li>This is a subset of modules transitively imported by X</li><li>These dependencies are NOT reported by `ghc -M X.hs`</li></ul>
<p>"Direct Dependency": if the command to create file X accesses file Y, then X directly depends on Y (= Y is a direct dependency of X).</p>
<ul type="disc">
<li>In the above scenario:</li></ul>
<ul type="disc">
<li>
<ul type="circle">
<li>A.o directly depends on: A.hs, B.hi, and C.hi</li></ul>
</li></ul>
<ul type="disc">
<li>SPJ noted that .hi files list direct dependencies.</li><li>The direct dependencies of a haskell object file is the union of its shallow and deep dependencies.</li></ul>
<p>"Direct Output": All files created by a rule.</p>
<p>With that in mind, and considering a cloud build system where "<b><span style="color:#1f497d">all direct inputs and direct outputs must be declared</span></b>" (where this agrees with the definitions above) can we do the following for the build rule of a
 haskell object file X.o?</p>
<ol start="1" type="1">
<li>`need` the shallow dependencies as reported by `ghc -M`. This guarantees that all shallow and deep dependencies (i.e. all direct dependencies) are built.</li><li>build X.o and X.hi</li><li>Inspect X.hi to derive the direct dependencies (and hence deep dependencies)</li><li>`needed` the deep dependencies</li></ol>
<p>Is there already an easy way to inspect *.hi files in this way? Is this use of `needed` valid?</p>
<p>- David E</p>
<p> </p>
<div>
<p>On 3/27/19 3:05 PM, Andrey Mokhov wrote:</p>
</div>
<blockquote style="margin-top:5pt;margin-bottom:5pt">
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Hi David,</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">We had a discussion about this with Neil some time ago, and I think we had the following list of progressively more complex invariants for different types of build systems:</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<ul type="disc" style="margin-top:0cm">
<li style="margin-left:0cm"><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Non-cloud build systems: *<b>all direct inputs must be declared</b>*. If you miss a direct input dependency then a build may complete successfully but
 with an incorrect result.</span></li></ul>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<ul type="disc" style="margin-top:0cm">
<li style="margin-left:0cm"><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Cloud build systems: *<b>all direct inputs and direct outputs must be declared</b>*. If you miss a direct output then a build may fail because the cloud
 will not be able to restore the corresponding output.</span></li></ul>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<ul type="disc" style="margin-top:0cm">
<li style="margin-left:0cm"><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Cloud build systems with shallow (deferred) materialisation of build artefacts: *<b>all transitive inputs and direct outputs must be declared</b>*. Let’s
 say you’d like to download the resulting GHC binary directly, without materialising any intermediate artefacts. Then you’ll need to know GHC’s ultimate transitive inputs.</span></li></ul>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">I think for now we are really keen to make Hadrian a cloud build system, but whether shallow builds are valuable enough is not clear. Maybe not. Therefore, I’d say we don’t need
 to track transitive inputs right now. Furthermore, if we were to track all transitive inputs, we would lose the desirable early cutoff property, which prevents rebuilding after adding a comment in a file on which a lot of other files transitively depend on.</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Having said that, if we really access a file during compilation, then I think it is *<b>not</b>* a transitive dependency by definition! Any file which is accessed during a build
 rule is a direct dependency.</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">> GHC is reading *.hi files that are not reported as dependencies by</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">> `ghc -M  -include-pkg-deps`. This is because they are not direct, but transitive</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">> dependencies!</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">So, here I’m confused. If we read a file A when compiling a file B, then it’s by definition a direct dependency. Perhaps we just read too much? Maybe the solution is to switch
 to fine-grained `ghc -M` mode, to analyse import dependencies for a single module instead of doing it transitively, which I believe was discussed in a ticket some time ago? I can’t find this ticket, but I think Alp was looking into it at some point. Alp: do
 you remember it?</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Thank you for all your work on Hadrian!</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Cheers,</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d">Andrey</span></p>
<p><span style="font-size:11pt;font-family:'calibri' , sans-serif;color:#1f497d"> </span></p>
<div>
<div style="border:none;border-top:solid #e1e1e1 1pt;padding:3pt 0cm 0cm 0cm">
<p><b><span style="font-size:11pt;font-family:'calibri' , sans-serif">From:</span></b><span style="font-size:11pt;font-family:'calibri' , sans-serif"> David Eichmann [<a href="mailto:davide@well-typed.com">mailto:davide@well-typed.com</a>]
<br>
<b>Sent:</b> 27 March 2019 12:54<br>
<b>To:</b> Neil Mitchell <a href="mailto:ndmitchell@gmail.com"><ndmitchell@gmail.com></a>; Andrey Mokhov
<a href="mailto:andrey.mokhov@newcastle.ac.uk"><andrey.mokhov@newcastle.ac.uk></a>; GHC developers
<a href="mailto:ghc-devs@haskell.org"><ghc-devs@haskell.org></a><br>
<b>Subject:</b> Hadrian Transitive Dependencies</span></p>
</div>
</div>
<p> </p>
<p>Hello Shake/Hadrian contributors and the like,</p>
<p>Recently I've been putting Hadrian's fsatrace linting feature to good use, tracking down missing dependencies in Hadrian. Ultimately, we want to use shake's cloud build / shared cache feature and ensure it works across CI builds. Unfortunately the feature
 isn't working smoothly with Hadrian: see <a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2Fissues%2F16295&data=02%7C01%7Csimonpj%40microsoft.com%7Cbd87a25e08f441fe763d08d6b2d76b25%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636893035618959820&sdata=BomxywLkHm7mriTubSnCql6YJDJBR96K1tQbskKBMn4%3D&reserved=0">
#16295</a>. This is very desirable to improve CI build times. It is my understanding that in order to get caching to work:</p>
<p>1. All accessed files must declared with `need` AND<br>
2. All created files must be declared with `produces` (or be the target of the build rule)
</p>
<p>Is my understanding correct? Or is there a weaker condition (perhaps only 2 is necessary)?</p>
<p>If I'm correct, this amounts to fixing all fsatrace lint errors. See <a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2Fissues%2F16400%23note_188901&data=02%7C01%7Csimonpj%40microsoft.com%7Cbd87a25e08f441fe763d08d6b2d76b25%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636893035618969820&sdata=Kmnd%2B8%2FATQBw0AfCTvvl7oix5syXbPAeV7h473t8H7E%3D&reserved=0">
here</a> for a breakdown of lint errors / missing dependencies. A large portion of these are Haskell interface files (i.e. *.hi files). Before building a Haskell object file, dependencies are discovered via `ghc` using the `-M  -include-pkg-deps` options. Unfortunately,
 shake's fsatrace linting complains about other *.hi files being accessed! For example when building `stage1/libraries/mtl/build/Control/Monad/RWS/Class.o` we get the following dependencies from ghc:</p>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : libraries/mtl/Control/Monad/RWS/Class.hs</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/Prelude.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/Data/Monoid.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/RWS/Strict.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/RWS/Lazy.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Identity.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Maybe.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Except.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Error.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/lib/../lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Class.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/libraries/mtl/build/Control/Monad/Writer/Class.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/libraries/mtl/build/Control/Monad/State/Class.hi</pre>
<pre>_build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o : _build/stage1/libraries/mtl/build/Control/Monad/Reader/Class.hi</pre>
<p>And shake complains of the following missing deps:</p>
<pre>_build/stage0/bin/ghc -Wall -hisuf hi -osuf o -hcsuf hc -static -hide-all-packages -no-user-package-db '-package-db _build/stage1/lib/package.conf.d' '-this-unit-id mtl-2.2.2' '-package-id base-4.13.0.0' '-package-id transformers-0.5.5.0' -i -i_build/stage1/libraries/mtl/build -i_build/stage1/libraries/mtl/build/autogen -ilibraries/mtl/. -Iincludes -I_build/generated -I_build/stage1/libraries/mtl/build -I/home/david/ghc/_build/stage1/lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/include -I/home/david/ghc/_build/stage1/lib/x86_64-linux-ghc-8.9.20190325/integer-gmp-1.0.2.0/include -I/home/david/ghc/_build/stage1/lib/x86_64-linux-ghc-8.9.20190325/rts-1.0/include -I_build/generated -optc-I_build/generated -optP-include -optP_build/stage1/libraries/mtl/build/autogen/cabal_macros.h -outputdir _build/stage1/libraries/mtl/build -Wnoncanonical-monad-instances -optc-Werror=unused-but-set-variable -optc-Wno-error=inline -c libraries/mtl/Control/Monad/RWS/Class.hs -o _build/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o -O2 -H32m -Wall -fno-warn-unused-imports -fno-warn-warnings-deprecations -Wcompat -Wnoncanonical-monad-instances -Wnoncanonical-monadfail-instances -XHaskell2010 -XSafe -ghcversion-file=/home/david/MEGA/File_Dump/Well-Typed/GHC/_nosync_git/ghc/_build/generated/ghcversion.h -Wno-deprecated-flags</pre>
<pre>Lint checking error - _build/HEAD_default/stage1/libraries/mtl/build/Control/Monad/RWS/Class.o - 22 values were used but not depended upon:</pre>
<pre>  Used:  _build/HEAD_default/stage0/lib/settings</pre>
<pre>  Used:  _build/HEAD_default/stage0/lib/platformConstants</pre>
<pre>  Used:  _build/HEAD_default/stage0/lib/llvm-targets</pre>
<pre>  Used:  _build/HEAD_default/stage0/lib/llvm-passes</pre>
<pre>  Used:  _build/HEAD_default/stage0/lib/package.conf.d/package.cache</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/package.conf.d/package.cache</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/GHC/Float.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/GHC/Base.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/ghc-prim-0.5.3/GHC/Types.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/GHC/Maybe.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Writer/Lazy.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Writer/Strict.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/State/Lazy.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/State/Strict.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Reader.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/List.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/transformers-0.5.5.0/Control/Monad/Trans/Cont.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/ghc-prim-0.5.3/GHC/Tuple.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/GHC/IO/Exception.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/integer-gmp-1.0.2.0/GHC/Integer/Type.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/Data/Either.hi</pre>
<pre>  Used:  _build/HEAD_default/stage1/lib/x86_64-linux-ghc-8.9.20190325/base-4.13.0.0/GHC/Natural.hi</pre>
<p>GHC is reading *.hi files that are not reported as dependencies by `ghc -M  -include-pkg-deps`. This is because they are not direct, but
<i>transitive</i> dependencies! How do we fix these lint errors (again with the goal of using shakes shared cache feature)? Some ideas:</p>
<p>* Wildly over approximate dependencies. This may be easier to implement but cause unneeded recompilation (when a false dependency changes). Either:<br>
    * `need` all dependent packages' interface files recursively as well as transitive dependencies reported by `ghc -M  -include-pkg-deps` within the current package. OR<br>
    * OR `need` all transitive dependencies reported by `ghc -M  -include-pkg-deps`. This will likely result in fewer dependencies but requires a bit more work in recovering dependent packages' dependency graphs.<br>
* Perhaps transitive dependencies are not important for shared caching to work. Change shakes linting feature to allow (untracked?) transitive dependencies to be accessed.
</p>
<p>Feed back would be greatly appreciated.</p>
<p>David Eichmann</p>
<p> </p>
<pre>-- </pre>
<pre>David Eichmann, Haskell Consultant</pre>
<pre>Well-Typed LLP, <a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.well-typed.com&data=02%7C01%7Csimonpj%40microsoft.com%7Cbd87a25e08f441fe763d08d6b2d76b25%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636893035618979828&sdata=ZUSCHtfKiOsTYbS%2Bo%2FAuhSuXwtM5TKnzVPubJjZd6RI%3D&reserved=0">http://www.well-typed.com</a></pre>
<pre> </pre>
<pre>Registered in England & Wales, OC335890</pre>
<pre>118 Wymering Mansions, Wymering Road, London W9 2NF, England </pre>
</blockquote>
<pre>-- </pre>
<pre>David Eichmann, Haskell Consultant</pre>
<pre>Well-Typed LLP, <a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.well-typed.com&data=02%7C01%7Csimonpj%40microsoft.com%7Cbd87a25e08f441fe763d08d6b2d76b25%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636893035618989837&sdata=QxSKBt9C1rO8AwS0C8%2FIPhK43naICuuJ8ebdIzaudnQ%3D&reserved=0">http://www.well-typed.com</a></pre>
<pre> </pre>
<pre>Registered in England & Wales, OC335890</pre>
<pre>118 Wymering Mansions, Wymering Road, London W9 2NF, England </pre>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</div>
</body>
</html>