{"action":"created","comment":{"url":"https://api.github.com/repos/enthought/sat-solver/pulls/comments/43719166","id":43719166,"diff_hunk":"@@ -1,39 +1,179 @@\n import abc\n \n+from collections import Counter\n+from functools import partial\n+from itertools import count\n+\n import six\n \n from enstaller.collections import DefaultOrderedDict\n \n+from .priority_queue import PriorityQueue\n+\n \n class IPolicy(six.with_metaclass(abc.ABCMeta)):\n+\n+    @abc.abstractmethod\n+    def add_requirements(self, package_ids):\n+        \"\"\" Submit packages to the policy for consideration.\n+        \"\"\"\n+\n     @abc.abstractmethod\n     def get_next_package_id(self, assignments, clauses):\n         \"\"\" Returns a undecided variable (i.e. integer > 0) for the given sets\n-        of assignements and clauses.\n+        of assignments and clauses.\n+\n+        Parameters\n+        ----------\n+        assignments : OrderedDict\n+            The current assignments of each literal. Keys are variables\n+            (integer > 0) and values are one of (True, False, None).\n+        clauses : List of Clause\n+            The collection of Clause objects to satisfy.\n         \"\"\"\n \n \n class DefaultPolicy(IPolicy):\n+\n+    def __init__(self, *args):\n+        pass\n+\n+    def add_requirements(self, assignments):\n+        pass\n+\n     def get_next_package_id(self, assignments, _):\n         # Given a dictionary of partial assignments, get an undecided variable\n         # to be decided next.\n-        undecided = [\n+        undecided = (\n             package_id for package_id, status in six.iteritems(assignments)\n             if status is None\n-        ]\n-        return undecided[0]\n+        )\n+        return next(undecided)\n+\n \n+class PolicyLogger(IPolicy):\n+\n+    def __init__(self, PolicyFactory, pool, installed_repository):\n+        self._policy = PolicyFactory(pool, installed_repository)\n+        self._log_installed = list(installed_repository.iter_packages())\n+        self._log_suggestions = []\n+        self._log_required = []\n+        self._log_pool = pool\n+        self._log_assignment_changes = []\n+\n+    def get_next_package_id(self, assignments, clauses):\n+        self._log_assignment_changes.append(assignments._changelog.copy())\n+        pkg_id = self._policy.get_next_package_id(assignments, clauses)\n+        self._log_suggestions.append(pkg_id)\n+        return pkg_id\n+\n+    def add_requirements(self, package_ids):\n+        self._log_required.extend(package_ids)\n+        self._policy.add_requirements(package_ids)\n+\n+    def _log_histogram(self, pkg_ids):\n+        c = Counter(pkg_ids)\n+        lines = (\n+            \"{:>25} {}\".format(self._log_pretty_pkg_id(k), v)\n+            for k, v in sorted(c.items(), key=lambda p: p[1])\n+        )\n+        pretty = '\\n'.join(lines)\n+        return c, pretty\n+\n+    def _log_pretty_pkg_id(self, pkg_id):\n+        p = self._log_pool._id_to_package[pkg_id]\n+        return '{} {}'.format(p.name, p.version)\n+\n+\n+class _InstalledFirstPolicy(IPolicy):\n+\n+    CURRENT = count(-2e10)\n+    REQUIRED = count(-1e10)\n+\n+    def __init__(self, pool, installed_repository):\n+        self._pool = pool\n+        self._installed_pkg_ids = set(\n+            pool.package_id(package) for package in\n+            installed_repository.iter_packages()\n+        )\n+        self._seen_pkg_ids = set()\n+        self._required_pkg_ids = set()\n+        self._pkg_id_priority = {}\n+        self._unassigned_pkg_ids = PriorityQueue()\n+\n+    def _update_pkg_id_priority(self, assignments=None):\n+        assignments = assignments or {}\n+        pkg_id_priority = {}\n+        self._seen_pkg_ids.update(assignments.keys())\n+\n+        ordered_pkg_ids = sorted(\n+            self._seen_pkg_ids,\n+            key=lambda p: self._pool._id_to_package[p].version,\n+            reverse=True,\n+        )\n+\n+        for priority, pkg_id in enumerate(ordered_pkg_ids):\n+\n+            # Determine the new priority of this pkg\n+            if pkg_id in self._required_pkg_ids:\n+                new = next(self.REQUIRED)\n+            elif pkg_id in self._installed_pkg_ids:\n+                new = next(self.CURRENT)\n+            else:\n+                new = priority\n+\n+            if pkg_id in self._unassigned_pkg_ids:\n+                self._unassigned_pkg_ids.push(pkg_id, priority=new)\n+\n+            pkg_id_priority[pkg_id] = new\n+        self._pkg_id_priority = pkg_id_priority\n+\n+    def add_requirements(self, package_ids):\n+        self._required_pkg_ids.update(package_ids)\n+        self._seen_pkg_ids.update(package_ids)\n+        self._update_pkg_id_priority()\n+\n+    def get_next_package_id(self, assignments, clauses):\n+        self._update_cache_from_assignments(assignments)\n+\n+        # Grab the most interesting looking currently unassigned id\n+        return self._unassigned_pkg_ids.peek()\n+\n+    def _update_cache_from_assignments(self, assignments):\n+        for key, (old, new) in six.iteritems(assignments.get_changelog()):\n+            if key not in self._seen_pkg_ids:","path":"simplesat/sat/policy.py","position":148,"original_position":148,"commit_id":"d6aae0233024abf4e167522a4970e7d7d4b58292","original_commit_id":"d6aae0233024abf4e167522a4970e7d7d4b58292","user":{"login":"johntyree","id":108972,"avatar_url":"https://avatars.githubusercontent.com/u/108972?v=3","gravatar_id":"","url":"https://api.github.com/users/johntyree","html_url":"https://github.com/johntyree","followers_url":"https://api.github.com/users/johntyree/followers","following_url":"https://api.github.com/users/johntyree/following{/other_user}","gists_url":"https://api.github.com/users/johntyree/gists{/gist_id}","starred_url":"https://api.github.com/users/johntyree/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/johntyree/subscriptions","organizations_url":"https://api.github.com/users/johntyree/orgs","repos_url":"https://api.github.com/users/johntyree/repos","events_url":"https://api.github.com/users/johntyree/events{/privacy}","received_events_url":"https://api.github.com/users/johntyree/received_events","type":"User","site_admin":false},"body":"This is probably very cheap, but we don't *have* to do it every time. We could track whether we've updated this round or not.","created_at":"2015-11-03T06:18:51Z","updated_at":"2015-11-03T06:18:51Z","html_url":"https://github.com/enthought/sat-solver/pull/55#discussion_r43719166","pull_request_url":"https://api.github.com/repos/enthought/sat-solver/pulls/55","_links":{"self":{"href":"https://api.github.com/repos/enthought/sat-solver/pulls/comments/43719166"},"html":{"href":"https://github.com/enthought/sat-solver/pull/55#discussion_r43719166"},"pull_request":{"href":"https://api.github.com/repos/enthought/sat-solver/pulls/55"}}},"pull_request":{"url":"https://api.github.com/repos/enthought/sat-solver/pulls/55","id":49521557,"html_url":"https://github.com/enthought/sat-solver/pull/55","diff_url":"https://github.com/enthought/sat-solver/pull/55.diff","patch_url":"https://github.com/enthought/sat-solver/pull/55.patch","issue_url":"https://api.github.com/repos/enthought/sat-solver/issues/55","number":55,"state":"open","locked":false,"title":"A faster Installed-First policy","user":{"login":"johntyree","id":108972,"avatar_url":"https://avatars.githubusercontent.com/u/108972?v=3","gravatar_id":"","url":"https://api.github.com/users/johntyree","html_url":"https://github.com/johntyree","followers_url":"https://api.github.com/users/johntyree/followers","following_url":"https://api.github.com/users/johntyree/following{/other_user}","gists_url":"https://api.github.com/users/johntyree/gists{/gist_id}","starred_url":"https://api.github.com/users/johntyree/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/johntyree/subscriptions","organizations_url":"https://api.github.com/users/johntyree/orgs","repos_url":"https://api.github.com/users/johntyree/repos","events_url":"https://api.github.com/users/johntyree/events{/privacy}","received_events_url":"https://api.github.com/users/johntyree/received_events","type":"User","site_admin":false},"body":"This PR introduces a Policy that provides \"installed first\" behavior to the dependency solver, as well as a few helper classes.\r\n\r\nBenchmarks are in issue #52.\r\n\r\nIt is implemented as a giant priority queue where the priorities split into three bands, in order from highest to lowest:\r\n\r\n1. Installed packages\r\n  - Packages which are already installed on the system.\r\n2. Required packages\r\n  - Packages which have been explicitly requested.\r\n  - This is lower priority than the installed packages because we don't want to unnecessarily upgrade things.\r\n3. Everything else.\r\n\r\nWithin each group, packages are ordered descending by version, such that newer packages are tried first.\r\n\r\nI'm currently using the notion that version objects are always comparable to define an ordering over *all* packages and assign priorities based on that, rather than grouping packages by name. In addition to being fast, easy to write, and easy to understand, it leads to a few interesting properties:\r\n\r\n### Things it does\r\n-  it suggests packages with large version numbers earlier, i.e. `curl-7.3.0` comes well before `Biggus-0.7.0`.\r\n  - This was very easy to implement, but there's no good reason to do it this way. At best it doesn't hurt us. There are plenty of ways to make this smarter.\r\n- it suggests packages interleaved with each other, i.e. `pep8 1.4.6` then `scipy 0.15.0` then `pep8 0.6.1`,\r\n- high priority packages are suggested repeatedly until all options are exhausted,\r\n- not crash on #42,\r\n- it can totally ignore the `clause` literals and still be quite fast.\r\n\r\nTo see this play out, there's a `PolicyLogger` class that is currently wrapping `InstalledFirstPolicy` and keeping track of things.\r\n\r\n### Things it doesn't do\r\n- Anything smart by examining `clause` instances themselves,\r\n- Anything clever with package metadata (i.e. should we suggest packages with few or many dependencies first?)\r\n\r\nIt currently suffers from the unrelated backtracking bug that motivated #54, and passes all tox tests with that patch applied.\r\n\r\nIf this is suitable, I would think that this closes #42 and #52.","created_at":"2015-11-03T05:52:43Z","updated_at":"2015-11-03T06:18:51Z","closed_at":null,"merged_at":null,"merge_commit_sha":"c745d46ba640ab7b383d14b550e7ffb7b68b8554","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/enthought/sat-solver/pulls/55/commits","review_comments_url":"https://api.github.com/repos/enthought/sat-solver/pulls/55/comments","review_comment_url":"https://api.github.com/repos/enthought/sat-solver/pulls/comments{/number}","comments_url":"https://api.github.com/repos/enthought/sat-solver/issues/55/comments","statuses_url":"https://api.github.com/repos/enthought/sat-solver/statuses/d6aae0233024abf4e167522a4970e7d7d4b58292","head":{"label":"enthought:enh/optimize-installed-first","ref":"enh/optimize-installed-first","sha":"d6aae0233024abf4e167522a4970e7d7d4b58292","user":{"login":"enthought","id":539651,"avatar_url":"https://avatars.githubusercontent.com/u/539651?v=3","gravatar_id":"","url":"https://api.github.com/users/enthought","html_url":"https://github.com/enthought","followers_url":"https://api.github.com/users/enthought/followers","following_url":"https://api.github.com/users/enthought/following{/other_user}","gists_url":"https://api.github.com/users/enthought/gists{/gist_id}","starred_url":"https://api.github.com/users/enthought/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/enthought/subscriptions","organizations_url":"https://api.github.com/users/enthought/orgs","repos_url":"https://api.github.com/users/enthought/repos","events_url":"https://api.github.com/users/enthought/events{/privacy}","received_events_url":"https://api.github.com/users/enthought/received_events","type":"Organization","site_admin":false},"repo":{"id":27783212,"name":"sat-solver","full_name":"enthought/sat-solver","owner":{"login":"enthought","id":539651,"avatar_url":"https://avatars.githubusercontent.com/u/539651?v=3","gravatar_id":"","url":"https://api.github.com/users/enthought","html_url":"https://github.com/enthought","followers_url":"https://api.github.com/users/enthought/followers","following_url":"https://api.github.com/users/enthought/following{/other_user}","gists_url":"https://api.github.com/users/enthought/gists{/gist_id}","starred_url":"https://api.github.com/users/enthought/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/enthought/subscriptions","organizations_url":"https://api.github.com/users/enthought/orgs","repos_url":"https://api.github.com/users/enthought/repos","events_url":"https://api.github.com/users/enthought/events{/privacy}","received_events_url":"https://api.github.com/users/enthought/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/enthought/sat-solver","description":"SAT solver for use in Enstaller, based on the MiniSat implementation","fork":false,"url":"https://api.github.com/repos/enthought/sat-solver","forks_url":"https://api.github.com/repos/enthought/sat-solver/forks","keys_url":"https://api.github.com/repos/enthought/sat-solver/keys{/key_id}","collaborators_url":"https://api.github.com/repos/enthought/sat-solver/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/enthought/sat-solver/teams","hooks_url":"https://api.github.com/repos/enthought/sat-solver/hooks","issue_events_url":"https://api.github.com/repos/enthought/sat-solver/issues/events{/number}","events_url":"https://api.github.com/repos/enthought/sat-solver/events","assignees_url":"https://api.github.com/repos/enthought/sat-solver/assignees{/user}","branches_url":"https://api.github.com/repos/enthought/sat-solver/branches{/branch}","tags_url":"https://api.github.com/repos/enthought/sat-solver/tags","blobs_url":"https://api.github.com/repos/enthought/sat-solver/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/enthought/sat-solver/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/enthought/sat-solver/git/refs{/sha}","trees_url":"https://api.github.com/repos/enthought/sat-solver/git/trees{/sha}","statuses_url":"https://api.github.com/repos/enthought/sat-solver/statuses/{sha}","languages_url":"https://api.github.com/repos/enthought/sat-solver/languages","stargazers_url":"https://api.github.com/repos/enthought/sat-solver/stargazers","contributors_url":"https://api.github.com/repos/enthought/sat-solver/contributors","subscribers_url":"https://api.github.com/repos/enthought/sat-solver/subscribers","subscription_url":"https://api.github.com/repos/enthought/sat-solver/subscription","commits_url":"https://api.github.com/repos/enthought/sat-solver/commits{/sha}","git_commits_url":"https://api.github.com/repos/enthought/sat-solver/git/commits{/sha}","comments_url":"https://api.github.com/repos/enthought/sat-solver/comments{/number}","issue_comment_url":"https://api.github.com/repos/enthought/sat-solver/issues/comments{/number}","contents_url":"https://api.github.com/repos/enthought/sat-solver/contents/{+path}","compare_url":"https://api.github.com/repos/enthought/sat-solver/compare/{base}...{head}","merges_url":"https://api.github.com/repos/enthought/sat-solver/merges","archive_url":"https://api.github.com/repos/enthought/sat-solver/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/enthought/sat-solver/downloads","issues_url":"https://api.github.com/repos/enthought/sat-solver/issues{/number}","pulls_url":"https://api.github.com/repos/enthought/sat-solver/pulls{/number}","milestones_url":"https://api.github.com/repos/enthought/sat-solver/milestones{/number}","notifications_url":"https://api.github.com/repos/enthought/sat-solver/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/enthought/sat-solver/labels{/name}","releases_url":"https://api.github.com/repos/enthought/sat-solver/releases{/id}","created_at":"2014-12-09T19:31:39Z","updated_at":"2015-10-15T16:11:39Z","pushed_at":"2015-11-03T05:52:43Z","git_url":"git://github.com/enthought/sat-solver.git","ssh_url":"git@github.com:enthought/sat-solver.git","clone_url":"https://github.com/enthought/sat-solver.git","svn_url":"https://github.com/enthought/sat-solver","homepage":"","size":954,"stargazers_count":2,"watchers_count":2,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":15,"forks":1,"open_issues":15,"watchers":2,"default_branch":"master"}},"base":{"label":"enthought:master","ref":"master","sha":"8396670a81ec7780519a2aa6c2fb1778aa05230b","user":{"login":"enthought","id":539651,"avatar_url":"https://avatars.githubusercontent.com/u/539651?v=3","gravatar_id":"","url":"https://api.github.com/users/enthought","html_url":"https://github.com/enthought","followers_url":"https://api.github.com/users/enthought/followers","following_url":"https://api.github.com/users/enthought/following{/other_user}","gists_url":"https://api.github.com/users/enthought/gists{/gist_id}","starred_url":"https://api.github.com/users/enthought/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/enthought/subscriptions","organizations_url":"https://api.github.com/users/enthought/orgs","repos_url":"https://api.github.com/users/enthought/repos","events_url":"https://api.github.com/users/enthought/events{/privacy}","received_events_url":"https://api.github.com/users/enthought/received_events","type":"Organization","site_admin":false},"repo":{"id":27783212,"name":"sat-solver","full_name":"enthought/sat-solver","owner":{"login":"enthought","id":539651,"avatar_url":"https://avatars.githubusercontent.com/u/539651?v=3","gravatar_id":"","url":"https://api.github.com/users/enthought","html_url":"https://github.com/enthought","followers_url":"https://api.github.com/users/enthought/followers","following_url":"https://api.github.com/users/enthought/following{/other_user}","gists_url":"https://api.github.com/users/enthought/gists{/gist_id}","starred_url":"https://api.github.com/users/enthought/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/enthought/subscriptions","organizations_url":"https://api.github.com/users/enthought/orgs","repos_url":"https://api.github.com/users/enthought/repos","events_url":"https://api.github.com/users/enthought/events{/privacy}","received_events_url":"https://api.github.com/users/enthought/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/enthought/sat-solver","description":"SAT solver for use in Enstaller, based on the MiniSat implementation","fork":false,"url":"https://api.github.com/repos/enthought/sat-solver","forks_url":"https://api.github.com/repos/enthought/sat-solver/forks","keys_url":"https://api.github.com/repos/enthought/sat-solver/keys{/key_id}","collaborators_url":"https://api.github.com/repos/enthought/sat-solver/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/enthought/sat-solver/teams","hooks_url":"https://api.github.com/repos/enthought/sat-solver/hooks","issue_events_url":"https://api.github.com/repos/enthought/sat-solver/issues/events{/number}","events_url":"https://api.github.com/repos/enthought/sat-solver/events","assignees_url":"https://api.github.com/repos/enthought/sat-solver/assignees{/user}","branches_url":"https://api.github.com/repos/enthought/sat-solver/branches{/branch}","tags_url":"https://api.github.com/repos/enthought/sat-solver/tags","blobs_url":"https://api.github.com/repos/enthought/sat-solver/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/enthought/sat-solver/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/enthought/sat-solver/git/refs{/sha}","trees_url":"https://api.github.com/repos/enthought/sat-solver/git/trees{/sha}","statuses_url":"https://api.github.com/repos/enthought/sat-solver/statuses/{sha}","languages_url":"https://api.github.com/repos/enthought/sat-solver/languages","stargazers_url":"https://api.github.com/repos/enthought/sat-solver/stargazers","contributors_url":"https://api.github.com/repos/enthought/sat-solver/contributors","subscribers_url":"https://api.github.com/repos/enthought/sat-solver/subscribers","subscription_url":"https://api.github.com/repos/enthought/sat-solver/subscription","commits_url":"https://api.github.com/repos/enthought/sat-solver/commits{/sha}","git_commits_url":"https://api.github.com/repos/enthought/sat-solver/git/commits{/sha}","comments_url":"https://api.github.com/repos/enthought/sat-solver/comments{/number}","issue_comment_url":"https://api.github.com/repos/enthought/sat-solver/issues/comments{/number}","contents_url":"https://api.github.com/repos/enthought/sat-solver/contents/{+path}","compare_url":"https://api.github.com/repos/enthought/sat-solver/compare/{base}...{head}","merges_url":"https://api.github.com/repos/enthought/sat-solver/merges","archive_url":"https://api.github.com/repos/enthought/sat-solver/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/enthought/sat-solver/downloads","issues_url":"https://api.github.com/repos/enthought/sat-solver/issues{/number}","pulls_url":"https://api.github.com/repos/enthought/sat-solver/pulls{/number}","milestones_url":"https://api.github.com/repos/enthought/sat-solver/milestones{/number}","notifications_url":"https://api.github.com/repos/enthought/sat-solver/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/enthought/sat-solver/labels{/name}","releases_url":"https://api.github.com/repos/enthought/sat-solver/releases{/id}","created_at":"2014-12-09T19:31:39Z","updated_at":"2015-10-15T16:11:39Z","pushed_at":"2015-11-03T05:52:43Z","git_url":"git://github.com/enthought/sat-solver.git","ssh_url":"git@github.com:enthought/sat-solver.git","clone_url":"https://github.com/enthought/sat-solver.git","svn_url":"https://github.com/enthought/sat-solver","homepage":"","size":954,"stargazers_count":2,"watchers_count":2,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":15,"forks":1,"open_issues":15,"watchers":2,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/enthought/sat-solver/pulls/55"},"html":{"href":"https://github.com/enthought/sat-solver/pull/55"},"issue":{"href":"https://api.github.com/repos/enthought/sat-solver/issues/55"},"comments":{"href":"https://api.github.com/repos/enthought/sat-solver/issues/55/comments"},"review_comments":{"href":"https://api.github.com/repos/enthought/sat-solver/pulls/55/comments"},"review_comment":{"href":"https://api.github.com/repos/enthought/sat-solver/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/enthought/sat-solver/pulls/55/commits"},"statuses":{"href":"https://api.github.com/repos/enthought/sat-solver/statuses/d6aae0233024abf4e167522a4970e7d7d4b58292"}}}}