<div dir="ltr">So, there aren't "heuristics" to tweak here. The algorithm just encodes the rules for trying package combinations (usually, latest version first) and then backtracks to a previous point when an unresolvable conflict is found. This is quite different from something like a SAT solver where it does use heuristics to come up with a matching scenario quickly.<div><br></div><div>I don't think developers need to tweak heuristics in either case. You just pick your SAT solver and it has reasonable heuristics built in, right?</div><div><div><div><div><br></div><div>Thanks,</div><div>Justin</div></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 10, 2017 at 4:03 PM, David Cournapeau <span dir="ltr"><<a href="mailto:cournape@gmail.com" target="_blank">cournape@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="">On Fri, Feb 10, 2017 at 3:52 PM, David Cournapeau <span dir="ltr"><<a href="mailto:cournape@gmail.com" target="_blank">cournape@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Fri, Feb 10, 2017 at 2:33 PM, Justin Cappos <span dir="ltr"><<a href="mailto:jcappos@nyu.edu" target="_blank">jcappos@nyu.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Yes, don't use a SAT solver. It requires all metadata from all packages (~30MB uncompressed) and gives hard to predict results in some cases. </div></blockquote><div><br></div></span><div>I doubt there exists an algorithm where this is not the case.</div><span><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"> Also the lack of fixed dependencies is a substantial problem for a SAT solver. Overall, we think it makes more sense to use a simple backtracking dependency resolution algorithm.</div></blockquote><div><br></div></span><div>As soon as you want to deal with version ranges and ensure consistency of the installed packages, backtracking stops being simple rather quickly.</div><div><br></div><div>I agree lack of fixed dependencies is an issue, but I doubt it is specific to a SAT solver. SAT solvers have been used successfully in many cases now: composer (php), dnf (Red Hat/Fedora), conda or our own packages manager at Enthought in python, 0install.</div><div><br></div><div>I would certainly be interested in seeing a proper comparison with other algorithms.</div></div></div></div></blockquote><div><br></div></span><div>I don't have experience implementing non SAT dependency solvers, but I suspect that whatever algorithm you end up using, the "core" is the simple part, and tweaking heuristics will be the hard, developer-time consuming part.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>David </div></font></span><div><div class="h5"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class="m_2356714624206145265HOEnZb"><font color="#888888"><div><br></div><div>David</div></font></span><div><div class="m_2356714624206145265h5"><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>Sebastien Awwad (CCed) has been looking at a bunch of data around the speed and other tradeoffs of the different algos. Sebastien: Sometime next week, can you write it up in a way that is suitable for sharing? <span class="m_2356714624206145265m_7961252675465371559HOEnZb"><font color="#888888"><br><div><br></div><div>Justin</div></font></span></div></div><div class="m_2356714624206145265m_7961252675465371559HOEnZb"><div class="m_2356714624206145265m_7961252675465371559h5"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 10, 2017 at 1:59 PM, Wes Turner <span dir="ltr"><<a href="mailto:wes.turner@gmail.com" target="_blank">wes.turner@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">From the discussion on <a href="https://github.com/pypa/pip/issues/988#issuecomment-279033079" target="_blank">https://github.com/pypa/pip/is<wbr>sues/988#issuecomment-27903307<wbr>9</a>:<div><br></div><div><ul style="box-sizing:border-box;padding-left:2em;color:rgb(51,51,51);font-family:-apple-system,blinkmacsystemfont,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:14px;margin-top:0px;margin-bottom:0px"><li style="box-sizing:border-box;margin-left:0px"><a href="https://github.com/ContinuumIO/pycosat" style="box-sizing:border-box;background-color:transparent;color:rgb(64,120,192);text-decoration:none" target="_blank">https://github.com/ContinuumIO<wbr>/pycosat</a> (picosat)<ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:0px"><li style="box-sizing:border-box;margin-left:0px"><a href="https://github.com/ContinuumIO/pycosat/blob/master/pycosat.c" style="box-sizing:border-box;background-color:transparent;color:rgb(64,120,192);text-decoration:none" target="_blank">https://github.com/ContinuumIO<wbr>/pycosat/blob/master/pycosat.c</a><wbr> (C)</li><li style="box-sizing:border-box;margin-top:0.25em;margin-left:0px"><a href="https://github.com/ContinuumIO/pycosat/blob/master/picosat.c" style="box-sizing:border-box;background-color:transparent;color:rgb(64,120,192);text-decoration:none" target="_blank">https://github.com/ContinuumIO<wbr>/pycosat/blob/master/picosat.c</a></li><li style="box-sizing:border-box;margin-top:0.25em;margin-left:0px"><a href="https://github.com/ContinuumIO/pycosat/tree/master/examples" style="box-sizing:border-box;background-color:transparent;color:rgb(64,120,192);text-decoration:none" target="_blank">https://github.com/ContinuumIO<wbr>/pycosat/tree/master/examples</a></li></ul></li><li style="box-sizing:border-box;margin-top:0.25em;margin-left:0px"><a href="https://github.com/enthought/sat-solver" style="box-sizing:border-box;background-color:transparent;color:rgb(64,120,192);text-decoration:none" target="_blank">https://github.com/enthought/s<wbr>at-solver</a> (MiniSat)</li><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:0px"><li style="box-sizing:border-box;margin-left:0px"><a href="https://github.com/enthought/sat-solver/tree/master/simplesat/tests" style="box-sizing:border-box;background-color:transparent;color:rgb(64,120,192);text-decoration:none" target="_blank">https://github.com/enthought/s<wbr>at-solver/tree/master/simplesa<wbr>t/tests</a></li><li style="box-sizing:border-box;margin-top:0.25em;margin-left:0px"><a href="https://github.com/enthought/sat-solver/blob/master/requirements.txt" style="box-sizing:border-box;background-color:transparent;color:rgb(64,120,192);text-decoration:none" target="_blank">https://github.com/enthought/s<wbr>at-solver/blob/master/requirem<wbr>ents.txt</a> (PyYAML, enum34)</li></ul></ul><div><font color="#333333" face="-apple-system, blinkmacsystemfont, segoe ui, helvetica, arial, sans-serif, apple color emoji, segoe ui emoji, segoe ui symbol"><span style="font-size:14px"><br></span></font></div></div><div><font color="#333333" face="-apple-system, blinkmacsystemfont, segoe ui, helvetica, arial, sans-serif, apple color emoji, segoe ui emoji, segoe ui symbol"><span style="font-size:14px">Is there a better way than SAT?</span></font></div></div><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104HOEnZb"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104h5"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 10, 2017 at 12:20 PM, Pradyun Gedam <span dir="ltr"><<a href="mailto:pradyunsg@gmail.com" target="_blank">pradyunsg@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">Yay! Thank you so much for a prompt and positive response! I'm pretty excited and looking forward to this.</div><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972HOEnZb"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972h5"><span>
</span><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="gmail_quote m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div dir="ltr" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">On Thu, Feb 9, 2017, 20:23 Donald Stufft <<a href="mailto:donald@stufft.io" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" target="_blank">donald@stufft.io</a>> wrote:<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"></div><blockquote class="gmail_quote m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">I’ve never done it before, but I’m happy to provide mentoring on this.</div><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><blockquote type="cite" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"></blockquote></div></div><div style="word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><blockquote type="cite" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">On Feb 8, 2017, at 9:15 PM, Pradyun Gedam <<a href="mailto:pradyunsg@gmail.com" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" target="_blank">pradyunsg@gmail.com</a>> wrote:</div><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546m_3275078904521864441m_6600394735712870104Apple-interchange-newline m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"></blockquote></div></div><div style="word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><blockquote type="cite" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div dir="ltr" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div dir="ltr" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div dir="ltr" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div dir="ltr" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">Hello Everyone!<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">Ralf Gommers suggested that I put this proposal here on this list, for
feedback and for seeing if anyone would be willing to mentor me. So, here it is.<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">-----<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">My name is Pradyun Gedam. I'm currently a first year student VIT University in India.<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">I would like to apply for GSoC 2017 under PSF.<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">I currently have a project in mind - the "pip needs a dependency resolver" issue [1]. I would like to take on this specific project but am willing to do some other project as well.<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">For some background, around mid 2016, I started contributing to pip. The first issue I tackled was #59 [2] - a request for upgrade command and an upgrade-all command that has been open for over 5.5 years. Over the months following that, I've have had the opportunity to work with and understand multiple parts of pip's codebase while working on this issue and a few others. This search on GitHub issues [3] also provides a good summary of what work I've done on pip.<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">[2]: <a href="https://github.com/pypa/pip/issues/988" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" target="_blank">https://github.com/pypa/pip/is<wbr>sues/988</a><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">[2]: <a href="https://github.com/pypa/pip/issues/59" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" target="_blank">https://github.com/pypa/pip/is<wbr>sues/59</a><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">[3]: <a href="https://github.com/pypa/pip/issues?q=author%3Apradyunsg" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" target="_blank">https://github.com/pypa/pip/is<wbr>sues?q=author%3Apradyunsg</a><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">Eagerly-waiting-for-a-response<wbr>-ly,<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">Pradyun Gedam</div></div></div></div></div></blockquote></div></div><div style="word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><blockquote type="cite" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">
______________________________<wbr>_________________<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">Distutils-SIG maillist - <a href="mailto:Distutils-SIG@python.org" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" target="_blank">Distutils-SIG@python.org</a><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><a href="https://mail.python.org/mailman/listinfo/distutils-sig" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg" target="_blank">https://mail.python.org/mailma<wbr>n/listinfo/distutils-sig</a><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"></div></blockquote></div></div><div style="word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><blockquote type="cite" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"></div></blockquote></div><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">
<div style="color:rgb(0,0,0);font-family:Helvetica;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-variant-numeric:normal;font-variant-alternates:normal;font-variant-east-asian:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">—</div></div></div><div style="word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><div style="color:rgb(0,0,0);font-family:Helvetica;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-variant-numeric:normal;font-variant-alternates:normal;font-variant-east-asian:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;word-wrap:break-word" class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"><br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg">Donald Stufft<br class="m_2356714624206145265m_7961252675465371559m_-4755732619968403104m_6186889061556752972m_-3193125452219004546gmail_msg"></div></div></div></blockquote></div>
</div></div><br>______________________________<wbr>_________________<br>
Distutils-SIG maillist - <a href="mailto:Distutils-SIG@python.org" target="_blank">Distutils-SIG@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/distutils-sig" rel="noreferrer" target="_blank">https://mail.python.org/mailma<wbr>n/listinfo/distutils-sig</a><br>
<br></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Distutils-SIG maillist - <a href="mailto:Distutils-SIG@python.org" target="_blank">Distutils-SIG@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/distutils-sig" rel="noreferrer" target="_blank">https://mail.python.org/mailma<wbr>n/listinfo/distutils-sig</a><br>
<br></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
Distutils-SIG maillist - <a href="mailto:Distutils-SIG@python.org" target="_blank">Distutils-SIG@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/distutils-sig" rel="noreferrer" target="_blank">https://mail.python.org/mailma<wbr>n/listinfo/distutils-sig</a><br>
<br></blockquote></div></div></div><br></div></div>
</blockquote></div></div></div><br></div></div>
</blockquote></div><br></div>