{"action":"created","comment":{"url":"https://api.github.com/repos/rust-lang/cargo/pulls/comments/38328691","id":38328691,"diff_hunk":"@@ -298,109 +244,213 @@ fn activate(mut cx: Box<Context>,\n         Method::Everything => None,\n     };\n \n-    activate_deps(cx, registry, parent, platform, deps.iter(), 0,\n-                  &mut |mut cx, registry| {\n-        cx.visited.remove(id);\n-        finished(cx, registry)\n-    })\n+    Ok(Some(DepsFrame{\n+        parent: parent,\n+        remaining_siblings: RcVecIter::new(deps),\n+        platform: platform.map(|s| s.to_string()),\n+        id: id,\n+    }))\n }\n \n-/// Activates the dependencies for a package, one by one in turn.\n-///\n-/// This function will attempt to activate all possible candidates for each\n-/// dependency of the package specified by `parent`. The `deps` iterator\n-/// provided is an iterator over all dependencies where each element yielded\n-/// informs us what the candidates are for the dependency in question.\n-///\n-/// The `platform` argument is the target platform that the dependencies are\n-/// being activated for.\n+#[derive(Clone)]\n+struct RcVecIter<Elem> {\n+    vec: Rc<Vec<Elem>>,\n+    next_index: usize,\n+}\n+\n+impl<Elem> RcVecIter<Elem> {\n+    fn new(vec: Vec<Elem>) -> RcVecIter<Elem> {\n+        RcVecIter {\n+            vec: Rc::new(vec),\n+            next_index: 0\n+        }\n+    }\n+    fn next(&mut self) -> Option<(usize, &Elem)> {\n+        match self.vec.get(self.next_index) {\n+            None => None,\n+            Some(val) => {\n+                let index = self.next_index;\n+                self.next_index += 1;\n+                Some((index, val))\n+            }\n+        }\n+    }\n+}\n+\n+#[derive(Clone)]\n+struct DepsFrame {\n+    parent: Rc<Summary>,\n+    remaining_siblings: RcVecIter<DepInfo>,\n+    platform: Option<String>,\n+    id: PackageId,\n+}\n+type RemainingDeps = Vec<DepsFrame>;\n+\n+struct BacktrackFrame {\n+    context_backup: Context,\n+    deps_backup: RemainingDeps,\n+    remaining_candidates: RcVecIter<Rc<Summary>>,\n+    // For building an activation error:\n+    parent: Rc<Summary>,\n+    cur: usize,\n+    dep: Rc<Dependency>,\n+    prev_active: Vec<Rc<Summary>>,\n+    all_candidates: Vec<Rc<Summary>>,\n+}\n+\n+/// Recursively activates the dependencies for `top`, in depth-first order,\n+/// backtracking across possible candidates for each dependency as necessary.\n ///\n /// If all dependencies can be activated and resolved to a version in the\n-/// dependency graph the `finished` callback is invoked with the current state\n-/// of the world.\n-fn activate_deps<'a>(cx: Box<Context>,\n-                     registry: &mut Registry,\n-                     parent: &Summary,\n-                     platform: Option<&'a str>,\n-                     mut deps: slice::Iter<'a, DepInfo>,\n-                     cur: usize,\n-                     finished: &mut FnMut(Box<Context>, &mut Registry) -> ResolveResult)\n-                     -> ResolveResult {\n-    let &(dep, ref candidates, ref features) = match deps.next() {\n-        Some(info) => info,\n-        None => return finished(cx, registry),\n-    };\n+/// dependency graph, cx.resolve is returned.\n+fn activate_deps_loop(mut cx: Context,\n+                      registry: &mut Registry,\n+                      top: Rc<Summary>,\n+                      top_method: &Method) -> CargoResult<Resolve> {\n+    let mut backtrack_stack: Vec<BacktrackFrame> = Vec::new();\n+    let mut remaining_deps: RemainingDeps = Vec::new();\n+    remaining_deps.extend(\n+        try!(activate(&mut cx, registry, top, &top_method)));\n+    loop {\n+        // Retrieves the next dependency to try, from `remaining_deps`.\n+        let (parent, platform, cur, dep, candidates, features) =\n+            match remaining_deps.pop() {\n+                None => break,\n+                Some(mut deps_frame) => {\n+                    let info =\n+                        match deps_frame.remaining_siblings.next() {\n+                            Some((cur, &(ref dep, ref candidates, ref features))) =>\n+                                (deps_frame.parent.clone(), deps_frame.platform.clone(),\n+                                 cur, dep.clone(),\n+                                 candidates.clone(), features.clone()),\n+                            None => {\n+                                cx.visited.remove(&deps_frame.id);\n+                                continue;\n+                            }\n+                        };\n+                    remaining_deps.push(deps_frame);\n+                    info\n+                }\n+            };","path":"src/cargo/core/resolver/mod.rs","position":257,"original_position":257,"commit_id":"252b09298ba9e024310a1265927922c2a6784f0c","original_commit_id":"252b09298ba9e024310a1265927922c2a6784f0c","user":{"login":"alexcrichton","id":64996,"avatar_url":"https://avatars.githubusercontent.com/u/64996?v=3","gravatar_id":"","url":"https://api.github.com/users/alexcrichton","html_url":"https://github.com/alexcrichton","followers_url":"https://api.github.com/users/alexcrichton/followers","following_url":"https://api.github.com/users/alexcrichton/following{/other_user}","gists_url":"https://api.github.com/users/alexcrichton/gists{/gist_id}","starred_url":"https://api.github.com/users/alexcrichton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexcrichton/subscriptions","organizations_url":"https://api.github.com/users/alexcrichton/orgs","repos_url":"https://api.github.com/users/alexcrichton/repos","events_url":"https://api.github.com/users/alexcrichton/events{/privacy}","received_events_url":"https://api.github.com/users/alexcrichton/received_events","type":"User","site_admin":false},"body":"Stylistically Cargo also tends to prefer something like:\r\n\r\n```rust\r\nlet foo = match bar {\r\n    Some(p) => p,\r\n    None => { ... }\r\n};\r\n```","created_at":"2015-08-31T16:17:12Z","updated_at":"2015-08-31T16:17:12Z","html_url":"https://github.com/rust-lang/cargo/pull/1941#discussion_r38328691","pull_request_url":"https://api.github.com/repos/rust-lang/cargo/pulls/1941","_links":{"self":{"href":"https://api.github.com/repos/rust-lang/cargo/pulls/comments/38328691"},"html":{"href":"https://github.com/rust-lang/cargo/pull/1941#discussion_r38328691"},"pull_request":{"href":"https://api.github.com/repos/rust-lang/cargo/pulls/1941"}}},"pull_request":{"url":"https://api.github.com/repos/rust-lang/cargo/pulls/1941","id":43362770,"html_url":"https://github.com/rust-lang/cargo/pull/1941","diff_url":"https://github.com/rust-lang/cargo/pull/1941.diff","patch_url":"https://github.com/rust-lang/cargo/pull/1941.patch","issue_url":"https://api.github.com/repos/rust-lang/cargo/issues/1941","number":1941,"state":"open","locked":false,"title":"Make the resolver non-recursive","user":{"login":"jyasskin","id":83420,"avatar_url":"https://avatars.githubusercontent.com/u/83420?v=3","gravatar_id":"","url":"https://api.github.com/users/jyasskin","html_url":"https://github.com/jyasskin","followers_url":"https://api.github.com/users/jyasskin/followers","following_url":"https://api.github.com/users/jyasskin/following{/other_user}","gists_url":"https://api.github.com/users/jyasskin/gists{/gist_id}","starred_url":"https://api.github.com/users/jyasskin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jyasskin/subscriptions","organizations_url":"https://api.github.com/users/jyasskin/orgs","repos_url":"https://api.github.com/users/jyasskin/repos","events_url":"https://api.github.com/users/jyasskin/events{/privacy}","received_events_url":"https://api.github.com/users/jyasskin/received_events","type":"User","site_admin":false},"body":"I'm very new to Rust, so lots of this probably has the wrong style, misses lifetime optimizations, etc. Let me know what to fix.\r\n\r\nThis passes the cargo tests, but let me know if there are other validations to run. Cargo has no benchmarks, so I'm currently downloading Servo to time `cargo update` on it before and after this patch.","created_at":"2015-08-26T04:20:18Z","updated_at":"2015-08-31T16:17:12Z","closed_at":null,"merged_at":null,"merge_commit_sha":"49136c28cd6ba8cc46d9f02d69874b4471aeea31","assignee":{"login":"alexcrichton","id":64996,"avatar_url":"https://avatars.githubusercontent.com/u/64996?v=3","gravatar_id":"","url":"https://api.github.com/users/alexcrichton","html_url":"https://github.com/alexcrichton","followers_url":"https://api.github.com/users/alexcrichton/followers","following_url":"https://api.github.com/users/alexcrichton/following{/other_user}","gists_url":"https://api.github.com/users/alexcrichton/gists{/gist_id}","starred_url":"https://api.github.com/users/alexcrichton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexcrichton/subscriptions","organizations_url":"https://api.github.com/users/alexcrichton/orgs","repos_url":"https://api.github.com/users/alexcrichton/repos","events_url":"https://api.github.com/users/alexcrichton/events{/privacy}","received_events_url":"https://api.github.com/users/alexcrichton/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/rust-lang/cargo/pulls/1941/commits","review_comments_url":"https://api.github.com/repos/rust-lang/cargo/pulls/1941/comments","review_comment_url":"https://api.github.com/repos/rust-lang/cargo/pulls/comments{/number}","comments_url":"https://api.github.com/repos/rust-lang/cargo/issues/1941/comments","statuses_url":"https://api.github.com/repos/rust-lang/cargo/statuses/252b09298ba9e024310a1265927922c2a6784f0c","head":{"label":"jyasskin:non-recursive-activate","ref":"non-recursive-activate","sha":"252b09298ba9e024310a1265927922c2a6784f0c","user":{"login":"jyasskin","id":83420,"avatar_url":"https://avatars.githubusercontent.com/u/83420?v=3","gravatar_id":"","url":"https://api.github.com/users/jyasskin","html_url":"https://github.com/jyasskin","followers_url":"https://api.github.com/users/jyasskin/followers","following_url":"https://api.github.com/users/jyasskin/following{/other_user}","gists_url":"https://api.github.com/users/jyasskin/gists{/gist_id}","starred_url":"https://api.github.com/users/jyasskin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jyasskin/subscriptions","organizations_url":"https://api.github.com/users/jyasskin/orgs","repos_url":"https://api.github.com/users/jyasskin/repos","events_url":"https://api.github.com/users/jyasskin/events{/privacy}","received_events_url":"https://api.github.com/users/jyasskin/received_events","type":"User","site_admin":false},"repo":{"id":41399909,"name":"cargo","full_name":"jyasskin/cargo","owner":{"login":"jyasskin","id":83420,"avatar_url":"https://avatars.githubusercontent.com/u/83420?v=3","gravatar_id":"","url":"https://api.github.com/users/jyasskin","html_url":"https://github.com/jyasskin","followers_url":"https://api.github.com/users/jyasskin/followers","following_url":"https://api.github.com/users/jyasskin/following{/other_user}","gists_url":"https://api.github.com/users/jyasskin/gists{/gist_id}","starred_url":"https://api.github.com/users/jyasskin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jyasskin/subscriptions","organizations_url":"https://api.github.com/users/jyasskin/orgs","repos_url":"https://api.github.com/users/jyasskin/repos","events_url":"https://api.github.com/users/jyasskin/events{/privacy}","received_events_url":"https://api.github.com/users/jyasskin/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jyasskin/cargo","description":"The Rust package manager","fork":true,"url":"https://api.github.com/repos/jyasskin/cargo","forks_url":"https://api.github.com/repos/jyasskin/cargo/forks","keys_url":"https://api.github.com/repos/jyasskin/cargo/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jyasskin/cargo/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jyasskin/cargo/teams","hooks_url":"https://api.github.com/repos/jyasskin/cargo/hooks","issue_events_url":"https://api.github.com/repos/jyasskin/cargo/issues/events{/number}","events_url":"https://api.github.com/repos/jyasskin/cargo/events","assignees_url":"https://api.github.com/repos/jyasskin/cargo/assignees{/user}","branches_url":"https://api.github.com/repos/jyasskin/cargo/branches{/branch}","tags_url":"https://api.github.com/repos/jyasskin/cargo/tags","blobs_url":"https://api.github.com/repos/jyasskin/cargo/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jyasskin/cargo/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jyasskin/cargo/git/refs{/sha}","trees_url":"https://api.github.com/repos/jyasskin/cargo/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jyasskin/cargo/statuses/{sha}","languages_url":"https://api.github.com/repos/jyasskin/cargo/languages","stargazers_url":"https://api.github.com/repos/jyasskin/cargo/stargazers","contributors_url":"https://api.github.com/repos/jyasskin/cargo/contributors","subscribers_url":"https://api.github.com/repos/jyasskin/cargo/subscribers","subscription_url":"https://api.github.com/repos/jyasskin/cargo/subscription","commits_url":"https://api.github.com/repos/jyasskin/cargo/commits{/sha}","git_commits_url":"https://api.github.com/repos/jyasskin/cargo/git/commits{/sha}","comments_url":"https://api.github.com/repos/jyasskin/cargo/comments{/number}","issue_comment_url":"https://api.github.com/repos/jyasskin/cargo/issues/comments{/number}","contents_url":"https://api.github.com/repos/jyasskin/cargo/contents/{+path}","compare_url":"https://api.github.com/repos/jyasskin/cargo/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jyasskin/cargo/merges","archive_url":"https://api.github.com/repos/jyasskin/cargo/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jyasskin/cargo/downloads","issues_url":"https://api.github.com/repos/jyasskin/cargo/issues{/number}","pulls_url":"https://api.github.com/repos/jyasskin/cargo/pulls{/number}","milestones_url":"https://api.github.com/repos/jyasskin/cargo/milestones{/number}","notifications_url":"https://api.github.com/repos/jyasskin/cargo/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jyasskin/cargo/labels{/name}","releases_url":"https://api.github.com/repos/jyasskin/cargo/releases{/id}","created_at":"2015-08-26T02:33:38Z","updated_at":"2015-08-26T02:33:39Z","pushed_at":"2015-08-26T04:13:33Z","git_url":"git://github.com/jyasskin/cargo.git","ssh_url":"git@github.com:jyasskin/cargo.git","clone_url":"https://github.com/jyasskin/cargo.git","svn_url":"https://github.com/jyasskin/cargo","homepage":"http://crates.io/","size":8098,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"rust-lang:master","ref":"master","sha":"6192ef578b45d7c625c52548ac04e1e18051e703","user":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"repo":{"id":17420913,"name":"cargo","full_name":"rust-lang/cargo","owner":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=3","gravatar_id":"","url":"https://api.github.com/users/rust-lang","html_url":"https://github.com/rust-lang","followers_url":"https://api.github.com/users/rust-lang/followers","following_url":"https://api.github.com/users/rust-lang/following{/other_user}","gists_url":"https://api.github.com/users/rust-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/rust-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rust-lang/subscriptions","organizations_url":"https://api.github.com/users/rust-lang/orgs","repos_url":"https://api.github.com/users/rust-lang/repos","events_url":"https://api.github.com/users/rust-lang/events{/privacy}","received_events_url":"https://api.github.com/users/rust-lang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/rust-lang/cargo","description":"The Rust package manager","fork":false,"url":"https://api.github.com/repos/rust-lang/cargo","forks_url":"https://api.github.com/repos/rust-lang/cargo/forks","keys_url":"https://api.github.com/repos/rust-lang/cargo/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rust-lang/cargo/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rust-lang/cargo/teams","hooks_url":"https://api.github.com/repos/rust-lang/cargo/hooks","issue_events_url":"https://api.github.com/repos/rust-lang/cargo/issues/events{/number}","events_url":"https://api.github.com/repos/rust-lang/cargo/events","assignees_url":"https://api.github.com/repos/rust-lang/cargo/assignees{/user}","branches_url":"https://api.github.com/repos/rust-lang/cargo/branches{/branch}","tags_url":"https://api.github.com/repos/rust-lang/cargo/tags","blobs_url":"https://api.github.com/repos/rust-lang/cargo/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rust-lang/cargo/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rust-lang/cargo/git/refs{/sha}","trees_url":"https://api.github.com/repos/rust-lang/cargo/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rust-lang/cargo/statuses/{sha}","languages_url":"https://api.github.com/repos/rust-lang/cargo/languages","stargazers_url":"https://api.github.com/repos/rust-lang/cargo/stargazers","contributors_url":"https://api.github.com/repos/rust-lang/cargo/contributors","subscribers_url":"https://api.github.com/repos/rust-lang/cargo/subscribers","subscription_url":"https://api.github.com/repos/rust-lang/cargo/subscription","commits_url":"https://api.github.com/repos/rust-lang/cargo/commits{/sha}","git_commits_url":"https://api.github.com/repos/rust-lang/cargo/git/commits{/sha}","comments_url":"https://api.github.com/repos/rust-lang/cargo/comments{/number}","issue_comment_url":"https://api.github.com/repos/rust-lang/cargo/issues/comments{/number}","contents_url":"https://api.github.com/repos/rust-lang/cargo/contents/{+path}","compare_url":"https://api.github.com/repos/rust-lang/cargo/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rust-lang/cargo/merges","archive_url":"https://api.github.com/repos/rust-lang/cargo/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rust-lang/cargo/downloads","issues_url":"https://api.github.com/repos/rust-lang/cargo/issues{/number}","pulls_url":"https://api.github.com/repos/rust-lang/cargo/pulls{/number}","milestones_url":"https://api.github.com/repos/rust-lang/cargo/milestones{/number}","notifications_url":"https://api.github.com/repos/rust-lang/cargo/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rust-lang/cargo/labels{/name}","releases_url":"https://api.github.com/repos/rust-lang/cargo/releases{/id}","created_at":"2014-03-04T23:20:42Z","updated_at":"2015-08-31T08:49:20Z","pushed_at":"2015-08-31T10:25:41Z","git_url":"git://github.com/rust-lang/cargo.git","ssh_url":"git@github.com:rust-lang/cargo.git","clone_url":"https://github.com/rust-lang/cargo.git","svn_url":"https://github.com/rust-lang/cargo","homepage":"http://crates.io/","size":27722,"stargazers_count":1272,"watchers_count":1272,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":282,"mirror_url":null,"open_issues_count":182,"forks":282,"open_issues":182,"watchers":1272,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/rust-lang/cargo/pulls/1941"},"html":{"href":"https://github.com/rust-lang/cargo/pull/1941"},"issue":{"href":"https://api.github.com/repos/rust-lang/cargo/issues/1941"},"comments":{"href":"https://api.github.com/repos/rust-lang/cargo/issues/1941/comments"},"review_comments":{"href":"https://api.github.com/repos/rust-lang/cargo/pulls/1941/comments"},"review_comment":{"href":"https://api.github.com/repos/rust-lang/cargo/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/rust-lang/cargo/pulls/1941/commits"},"statuses":{"href":"https://api.github.com/repos/rust-lang/cargo/statuses/252b09298ba9e024310a1265927922c2a6784f0c"}}}}