{"action":"created","issue":{"url":"https://api.github.com/repos/mxe/mxe/issues/1111","labels_url":"https://api.github.com/repos/mxe/mxe/issues/1111/labels{/name}","comments_url":"https://api.github.com/repos/mxe/mxe/issues/1111/comments","events_url":"https://api.github.com/repos/mxe/mxe/issues/1111/events","html_url":"https://github.com/mxe/mxe/issues/1111","id":124372179,"number":1111,"title":"Finding undeclared dependencies","user":{"login":"starius","id":920155,"avatar_url":"https://avatars.githubusercontent.com/u/920155?v=3","gravatar_id":"","url":"https://api.github.com/users/starius","html_url":"https://github.com/starius","followers_url":"https://api.github.com/users/starius/followers","following_url":"https://api.github.com/users/starius/following{/other_user}","gists_url":"https://api.github.com/users/starius/gists{/gist_id}","starred_url":"https://api.github.com/users/starius/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/starius/subscriptions","organizations_url":"https://api.github.com/users/starius/orgs","repos_url":"https://api.github.com/users/starius/repos","events_url":"https://api.github.com/users/starius/events{/privacy}","received_events_url":"https://api.github.com/users/starius/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":22,"created_at":"2015-12-30T16:51:53Z","updated_at":"2016-01-15T20:03:41Z","closed_at":null,"body":"Following on from #1110, #1039, 068e20243d2b531c032f04fcff07bd613594d9ce, 20342ed8294bdddb6de27d415b802640f340fc4d, 469ccb819c48bb24e67bf74fd4f7e45334fa326a, sometimes a package doesn't have all dependencies in its dependency list. A build may still succeed because the missing dependency happens to be built. Such bugs are hard to detect because they happen rarely.\r\n\r\nThere are two types of undeclared dependencies:\r\n1. undeclared requiremenets. If a requirement is absent, a following package or its descendant fails to build.\r\n2. Undeclared optional dependencies. Presence of optional dependency affects a following package or its descendant: sets of files differ or (harder to test) sets of features differ.\r\n\r\nI found two techniques to find undeclared dependencies.\r\n\r\nConsider two packages, a and b, such that each of them can be built without building another one. We call them *independent packages*.\r\n\r\n## Git branches (whitebox approach)\r\n\r\nWhen a package is built, the only built packages are its own dependencies. This can be implemented as a part of `build-pkg`: a git branch is created for each package; its parents are git branches of package direct dependencies. So build list is replaced with build graph. This approach guarantees that no independent packages of package `a` present when package `a` is built. So it solves problem 1 (undeclared requiremenets).\r\n\r\nIt can be enhanced to solve problem 2 as well (Undeclared optional dependencies). Having built all packages, rebuild each of them one more time, but use all packages except its followers as parents. Now all independent packages of package `a` present when package `a` is built. So each package has two builds: before independent packages and after independent packages. Compare files produced by these two builds and find discrepancies.\r\n\r\n## Many build lists (blackbox approach, not working atm)\r\n\r\n(This approach seems to be of thoretical value only.)\r\n\r\nTo detect effects between each pair of packages, one build is not sufficient. To make sure that `a` is not `b`'s undeclared dependency and vice versa, two builds are required. I studied if two builds are sufficient to cover all pairs of unrelated packages in any build graph. Unfortunately some build graphs require more than two builds to cover all unrelated pairs. For example, the following graph (\"heart\"):\r\n\r\n```\r\n      a -> b\r\n      |    |\r\n      v    |\r\n c -> d    |\r\n |         |\r\n v         v\r\n e ------> f\r\n\r\n```\r\n\r\nHere `a -> b` means \"b depends on a\". No pair of builds can cover all pairs of independent packages. However it can be covered in 3 builds:\r\n\r\n  * abcdef\r\n  * ceabfd\r\n  * acdebf\r\n\r\nI don't know efficient algorithm to find a minimum set of build lists covering all unrelated pairs. Nevertheless I created Lua library [toposort](https://github.com/starius/toposort) to deal with build graphs and build lists. It has heuristic algorithm in its function `toposort.coverUnrelated` which tries to generate small number of build lists covering all unrelated pairs. It's main idea is to shuffle list of packages and branch lists which are inputs of a normal toposort algorithm ([Tarjan's algorithm](https://en.wikipedia.org/wiki/Topological_sorting)). It is repeated N times on each step, after that one list is selected which reduces the number of uncovered pairs best of all. The list is added to the result and goes on untill all pairs are covered. So it is a greedy algorithm. The more N, the less the number of build lists in the result. So the less builds.\r\n\r\nI applied the algorithm to [MXE dependency graph](https://gist.github.com/59906bc0612759ba5291) for commit 815d8fe7e18deb2ae50ade063f98cfdd6d155581.\r\n\r\nNumber of builds is too large even for N=10000:\r\n\r\n```\r\n$ time luajit src/bin/cover_unrelated 1 < deps.txt > lists-1.txt\r\n\r\nreal    0m7.219s\r\nuser    0m7.084s\r\nsys     0m0.104s\r\n\r\n$ time luajit src/bin/cover_unrelated 10 < deps.txt > lists-10.txt\r\n\r\nreal    0m23.459s\r\nuser    0m23.217s\r\nsys     0m0.192s\r\n\r\n$ time luajit src/bin/cover_unrelated 100 < deps.txt > lists-100.txt\r\n\r\nreal    2m54.082s\r\nuser    2m52.331s\r\nsys     0m1.408s\r\n \r\n$ time luajit src/bin/cover_unrelated 1000 < deps.txt > lists-1000.txt\r\n\r\nreal    25m0.009s\r\nuser    24m43.813s\r\nsys     0m13.237s\r\n\r\n$ time luajit src/bin/cover_unrelated 10000 < deps.txt > lists-10000.txt\r\n\r\nreal    223m26.885s\r\nuser    221m3.205s\r\nsys     1m57.535s\r\n\r\n$ wc -l lists-1*\r\n     101 lists-10000.txt\r\n     116 lists-1000.txt\r\n     144 lists-100.txt\r\n     201 lists-10.txt\r\n     324 lists-1.txt\r\n\r\n$ gist lists-1*\r\nhttps://gist.github.com/d241a47c9fe71dc5d516\r\n```\r\n\r\nTwo improvements can be applied to this algorithm:\r\n\r\n  * use [MCMC](https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo) to make uniformly distributed build list;\r\n  * select the best edge instead of the best build list (the more build lists have an edge, the better it is); make the best build list by selecting edges one by one, until no independent edges remain.\r\n\r\nCan someone propose more efficient algorithm?"},"comment":{"url":"https://api.github.com/repos/mxe/mxe/issues/comments/172071057","html_url":"https://github.com/mxe/mxe/issues/1111#issuecomment-172071057","issue_url":"https://api.github.com/repos/mxe/mxe/issues/1111","id":172071057,"user":{"login":"starius","id":920155,"avatar_url":"https://avatars.githubusercontent.com/u/920155?v=3","gravatar_id":"","url":"https://api.github.com/users/starius","html_url":"https://github.com/starius","followers_url":"https://api.github.com/users/starius/followers","following_url":"https://api.github.com/users/starius/following{/other_user}","gists_url":"https://api.github.com/users/starius/gists{/gist_id}","starred_url":"https://api.github.com/users/starius/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/starius/subscriptions","organizations_url":"https://api.github.com/users/starius/orgs","repos_url":"https://api.github.com/users/starius/repos","events_url":"https://api.github.com/users/starius/events{/privacy}","received_events_url":"https://api.github.com/users/starius/received_events","type":"User","site_admin":false},"created_at":"2016-01-15T20:03:41Z","updated_at":"2016-01-15T20:03:41Z","body":"> wget is a case of 2 above (Undeclared optional dependencies). gnutls is missing libidn dependency #1183.\r\n\r\nThis case seems to be undeclared requirement for wget, because wget doesn't build without libidn. But for gnutls it is an optional dependency."}}