{"action":"created","comment":{"url":"https://api.github.com/repos/rust-lang/cargo/pulls/comments/38807428","id":38807428,"diff_hunk":"@@ -244,149 +190,240 @@ struct Context {\n /// Builds the list of all packages required to build the first argument.\n pub fn resolve(summary: &Summary, method: &Method,\n                registry: &mut Registry) -> CargoResult<Resolve> {\n-    trace!(\"resolve; summary={}\", summary.package_id());\n+    debug!(\"resolve; summary={}\", summary.package_id());\n     let summary = Rc::new(summary.clone());\n \n-    let cx = Box::new(Context {\n+    let cx = Context {\n         resolve: Resolve::new(summary.package_id().clone()),\n         activations: HashMap::new(),\n         visited: HashSet::new(),\n-    });\n+    };\n     let _p = profile::start(format!(\"resolving: {}\", summary.package_id()));\n-    match try!(activate(cx, registry, &summary, method, &mut |cx, _| Ok(Ok(cx)))) {\n-        Ok(cx) => {\n-            debug!(\"resolved: {:?}\", cx.resolve);\n-            Ok(cx.resolve)\n-        }\n-        Err(e) => Err(e),\n-    }\n+    activate_deps_loop(cx, registry, summary, method)\n }\n \n /// Attempts to activate the summary `parent` in the context `cx`.\n ///\n /// This function will pull dependency summaries from the registry provided, and\n /// the dependencies of the package will be determined by the `method` provided.\n-/// Once the resolution of this package has finished **entirely**, the current\n-/// context will be passed to the `finished` callback provided.\n-fn activate(mut cx: Box<Context>,\n+/// If `parent` was activated, this function returns the dependency frame to\n+/// iterate through next.\n+fn activate(cx: &mut Context,\n             registry: &mut Registry,\n-            parent: &Rc<Summary>,\n-            method: &Method,\n-            finished: &mut FnMut(Box<Context>, &mut Registry) -> ResolveResult)\n-            -> ResolveResult {\n+            parent: Rc<Summary>,\n+            method: &Method)\n+            -> CargoResult<Option<DepsFrame>> {\n     // Dependency graphs are required to be a DAG, so we keep a set of\n     // packages we're visiting and bail if we hit a dupe.\n-    let id = parent.package_id();\n+    let id = parent.package_id().clone();\n     if !cx.visited.insert(id.clone()) {\n         return Err(human(format!(\"cyclic package dependency: package `{}` \\\n                                   depends on itself\", id)))\n     }\n \n     // If we're already activated, then that was easy!\n-    if cx.flag_activated(parent, method) {\n-        cx.visited.remove(id);\n-        return finished(cx, registry)\n+    if cx.flag_activated(&parent, method) {\n+        cx.visited.remove(&id);\n+        return Ok(None);\n     }\n-    trace!(\"activating {}\", parent.package_id());\n+    debug!(\"activating {}\", parent.package_id());\n \n-    let deps = try!(cx.build_deps(registry, parent, method));\n+    let deps = try!(cx.build_deps(registry, &parent, method));\n \n-    activate_deps(cx, registry, parent, deps.iter(), 0, &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+        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+#[derive(Clone)]\n+struct RcVecIter<Elem> {\n+    vec: Rc<Vec<Elem>>,\n+    rest: Range<usize>,\n+}\n+\n+impl<Elem> RcVecIter<Elem> {\n+    fn new(vec: Vec<Elem>) -> RcVecIter<Elem> {\n+        RcVecIter {\n+            rest: 0..vec.len(),\n+            vec: Rc::new(vec),\n+        }\n+    }\n+}\n+impl<Elem> Iterator for RcVecIter<Elem> where Elem: Clone {\n+    type Item = (usize, Elem);\n+    fn next(&mut self) -> Option<(usize, Elem)> {\n+        self.rest.next().and_then(|i| self.vec.get(i).map(|val| (i, val.clone())))\n+    }\n+}\n+\n+#[derive(Clone)]\n+struct DepsFrame {\n+    parent: Rc<Summary>,\n+    remaining_siblings: RcVecIter<DepInfo>,\n+    id: PackageId,\n+}\n+\n+struct BacktrackFrame {\n+    context_backup: Context,\n+    deps_backup: Vec<DepsFrame>,","path":"src/cargo/core/resolver/mod.rs","position":204,"original_position":204,"commit_id":"87f0c914aa013d0f9405a467a72d1015da2a0e6e","original_commit_id":"87f0c914aa013d0f9405a467a72d1015da2a0e6e","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 believe you're suggesting that `DepsFrame` hold an `Option<Rc<RefCell<DepsFrame>>>` to implement the linked list, and `BacktrackFrame` hold an `Rc<RefCell<DepsFrame>>` tracking the top of the `remaining_deps` stack when the `BacktrackFrame` (call it `bf`) was pushed. Unfortunately, the algorithm will pop the `remaining_deps` past the level `bf` is holding, and mutate its `remaining_siblings` in order to finish traversing the dependencies. If we then backtrack past `bf`, it'll reset the `remaining_deps` stack to hold a bunch of frames whose siblings have been exhausted, instead of remembering to revisit them with the new candidate.\r\n\r\nWe could reduce the size of `DepsFrame` by changing `RcVecIter` back to holding the next index instead of a `Range`. Other than that, I think the biggest memory savings might come from changing `Context` so it doesn't need to be copied for each `BacktrackFrame`. I'm not volunteering to implement the necessary persistent maps and sets though. :)","created_at":"2015-09-05T04:48:52Z","updated_at":"2015-09-05T04:48:52Z","html_url":"https://github.com/rust-lang/cargo/pull/1941#discussion_r38807428","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/38807428"},"html":{"href":"https://github.com/rust-lang/cargo/pull/1941#discussion_r38807428"},"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-09-05T04:48:52Z","closed_at":null,"merged_at":null,"merge_commit_sha":"a42e8ed03ef5b631e752aac91728de2e2844c859","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/87f0c914aa013d0f9405a467a72d1015da2a0e6e","head":{"label":"jyasskin:non-recursive-activate","ref":"non-recursive-activate","sha":"87f0c914aa013d0f9405a467a72d1015da2a0e6e","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-09-01T05:06:55Z","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":8138,"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":"71240c3d5b6805ab6535dca58866ddf1cb95a95c","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-09-03T19:01:50Z","pushed_at":"2015-09-04T23:44:04Z","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":28063,"stargazers_count":1277,"watchers_count":1277,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":284,"mirror_url":null,"open_issues_count":177,"forks":284,"open_issues":177,"watchers":1277,"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/87f0c914aa013d0f9405a467a72d1015da2a0e6e"}}}}