GitHub PullRequestReviewCommentEvent at 2014-09-25 10:01:23
Repository: rust
Actor: huonw
Payload: {"action":"created","comment":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/comments/18023705","id":18023705,"diff_hunk":"@@ -0,0 +1,1209 @@\n+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT\n+// file at the top-level directory of this distribution and at\n+// http://rust-lang.org/COPYRIGHT.\n+//\n+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or\n+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license\n+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your\n+// option. This file may not be copied, modified, or distributed\n+// except according to those terms.\n+\n+// This implementation is largely based on the high-level description and analysis of B-Trees\n+// found in *Open Data Structures* (ODS). Although our implementation does not use any of\n+// the source found in ODS, if one wishes to review the high-level design of this structure, it\n+// can be freely downloaded at http://opendatastructures.org/. Its contents are as of this\n+// writing (August 2014) freely licensed under the following Creative Commons Attribution\n+// License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/).\n+\n+use core::prelude::*;\n+\n+use super::node::*;\n+use std::hash::{Writer, Hash};\n+use core::default::Default;\n+use core::{iter, fmt, mem};\n+use core::fmt::Show;\n+\n+use {Deque, Map, MutableMap, Mutable, MutableSeq};\n+use ringbuf::RingBuf;\n+\n+\n+\n+/// A B-Tree\n+pub struct BTreeMap<K, V> {\n+    root: Node<K, V>,\n+    length: uint,\n+    depth: uint,\n+    b: uint,\n+}\n+\n+/// An abstract base over-which all other BTree iterators are built\n+struct AbsEntries<T> {\n+    lca: T,\n+    left: RingBuf<T>,\n+    right: RingBuf<T>,\n+    size: uint,\n+}\n+\n+/// An iterator over a BTreeMap's entries\n+pub struct Entries<'a, K, V> {\n+    inner: AbsEntries<Traversal<'a, K, V>>\n+}\n+\n+/// A mutable iterator over a BTreeMap's entries\n+pub struct MutEntries<'a, K, V> {\n+    inner: AbsEntries<MutTraversal<'a, K, V>>\n+}\n+\n+/// An owning iterator over a BTreeMap's entries\n+pub struct MoveEntries<K, V> {\n+    inner: AbsEntries<MoveTraversal<K, V>>\n+}\n+\n+/// An iterator over a BTreeMap's keys\n+pub type Keys<'a, K, V> = iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;\n+\n+/// An iterator over a BTreeMap's values\n+pub type Values<'a, K, V> = iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;\n+\n+/// A view into a single entry in a map, which may either be vacant or occupied\n+pub enum Entry<'a, K:'a, V:'a> {\n+    /// A vacant Entry\n+    Vacant(VacantEntry<'a, K, V>),\n+    /// An occupied Entry\n+    Occupied(OccupiedEntry<'a, K, V>),\n+}\n+\n+/// A vacant Entry\n+pub struct VacantEntry<'a, K:'a, V:'a> {\n+    key: K,\n+    stack: stack::SearchStack<'a, K, V>,\n+}\n+\n+/// An occupied Entry\n+pub struct OccupiedEntry<'a, K:'a, V:'a> {\n+    stack: stack::SearchStack<'a, K, V>,\n+}\n+\n+impl<K: Ord, V> BTreeMap<K, V> {\n+    /// Makes a new empty BTreeMap with a reasonable choice for B\n+    pub fn new() -> BTreeMap<K, V> {\n+        //FIXME(Gankro): Tune this as a function of size_of<K/V>?\n+        BTreeMap::with_b(6)\n+    }\n+\n+    /// Makes a new empty BTreeMap with the given B\n+    pub fn with_b(b: uint) -> BTreeMap<K, V> {\n+        BTreeMap {\n+            length: 0,\n+            depth: 1,\n+            root: Node::make_leaf_root(b),\n+            b: b,\n+        }\n+    }\n+}\n+\n+impl<K: Ord, V> Map<K, V> for BTreeMap<K, V> {\n+    // Searching in a B-Tree is pretty straightforward.\n+    //\n+    // Start at the root. Try to find the key in the current node. If we find it, return it.\n+    // If it's not in there, follow the edge *before* the smallest key larger than\n+    // the search key. If no such key exists (they're *all* smaller), then just take the last\n+    // edge in the node. If we're in a leaf and we don't find our key, then it's not\n+    // in the tree.\n+    fn find(&self, key: &K) -> Option<&V> {\n+        let mut cur_node = &self.root;\n+        loop {\n+            match cur_node.search(key) {\n+                Found(i) => return cur_node.val(i),\n+                GoDown(i) => match cur_node.edge(i) {\n+                    None => return None,\n+                    Some(next_node) => {\n+                        cur_node = next_node;\n+                        continue;\n+                    }\n+                }\n+            }\n+        }\n+    }\n+}\n+\n+impl<K: Ord, V> MutableMap<K, V> for BTreeMap<K, V> {\n+    // See `find` for implementation notes, this is basically a copy-paste with mut's added\n+    fn find_mut(&mut self, key: &K) -> Option<&mut V> {\n+        // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration\n+        let mut temp_node = &mut self.root;\n+        loop {\n+            let cur_node = temp_node;\n+            match cur_node.search(key) {\n+                Found(i) => return cur_node.val_mut(i),\n+                GoDown(i) => match cur_node.edge_mut(i) {\n+                    None => return None,\n+                    Some(next_node) => {\n+                        temp_node = next_node;\n+                        continue;\n+                    }\n+                }\n+            }\n+        }\n+    }\n+\n+    // Insertion in a B-Tree is a bit complicated.\n+    //\n+    // First we do the same kind of search described in `find`. But we need to maintain a stack of\n+    // all the nodes/edges in our search path. If we find a match for the key we're trying to\n+    // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,\n+    // we attempt to insert our key-value pair at the same location we would want to follow another\n+    // edge.\n+    //\n+    // If the node has room, then this is done in the obvious way by shifting elements. However,\n+    // if the node itself is full, we split node into two, and give its median key-value\n+    // pair to its parent to insert the new node with. Of course, the parent may also be\n+    // full, and insertion can propagate until we reach the root. If we reach the root, and\n+    // it is *also* full, then we split the root and place the two nodes under a newly made root.\n+    //\n+    // Note that we subtly deviate from Open Data Structures in our implementation of split.\n+    // ODS describes inserting into the node *regardless* of its capacity, and then\n+    // splitting *afterwards* if it happens to be overfull. However, this is inefficient.\n+    // Instead, we split beforehand, and then insert the key-value pair into the appropriate\n+    // result node. This has two consequences:\n+    //\n+    // 1) While ODS produces a left node of size B-1, and a right node of size B,\n+    // we may potentially reverse this. However, this shouldn't effect the analysis.\n+    //\n+    // 2) While ODS may potentially return the pair we *just* inserted after\n+    // the split, we will never do this. Again, this shouldn't effect the analysis.\n+\n+    fn swap(&mut self, key: K, mut value: V) -> Option<V> {\n+        // This is a stack of rawptrs to nodes paired with indices, respectively\n+        // representing the nodes and edges of our search path. We have to store rawptrs\n+        // because as far as Rust is concerned, we can mutate aliased data with such a\n+        // stack. It is of course correct, but what it doesn't know is that we will only\n+        // be popping and using these ptrs one at a time in child-to-parent order. The alternative\n+        // to doing this is to take the Nodes from their parents. This actually makes\n+        // borrowck *really* happy and everything is pretty smooth. However, this creates\n+        // *tons* of pointless writes, and requires us to always walk all the way back to\n+        // the root after an insertion, even if we only needed to change a leaf. Therefore,\n+        // we accept this potential unsafety and complexity in the name of performance.\n+        //\n+        // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap\n+        // by the stack module. All it can do is immutably read nodes, and ask the search stack\n+        // to proceed down some edge by index. This makes the search logic we'll be reusing in a\n+        // few different methods much neater, and of course drastically improves safety.\n+        let mut stack = stack::PartialSearchStack::new(self);\n+\n+        loop {\n+            // Same basic logic as found in `find`, but with PartialSearchStack mediating the\n+            // actual nodes for us\n+            match stack.next().search(&key) {\n+                Found(i) => unsafe {\n+                    // Perfect match, swap the values and return the old one\n+                    let next = stack.into_next();\n+                    mem::swap(next.unsafe_val_mut(i), &mut value);\n+                    return Some(value);\n+                },\n+                GoDown(i) => {\n+                    // We need to keep searching, try to get the search stack\n+                    // to go down further\n+                    stack = match stack.push(i) {\n+                        stack::Done(new_stack) => {\n+                            // We've reached a leaf, perform the insertion here\n+                            new_stack.insert(key, value);\n+                            return None;\n+                        }\n+                        stack::Grew(new_stack) => {\n+                            // We've found the subtree to insert this key/value pair in,\n+                            // keep searching\n+                            new_stack\n+                        }\n+                    };\n+                }\n+            }\n+        }\n+    }\n+\n+    // Deletion is the most complicated operation for a B-Tree.\n+    //\n+    // First we do the same kind of search described in\n+    // `find`. But we need to maintain a stack of all the nodes/edges in our search path.\n+    // If we don't find the key, then we just return `None` and do nothing. If we do find the\n+    // key, we perform two operations: remove the item, and then possibly handle underflow.\n+    //\n+    // # removing the item\n+    //      If the node is a leaf, we just remove the item, and shift\n+    //      any items after it back to fill the hole.\n+    //\n+    //      If the node is an internal node, we *swap* the item with the smallest item in\n+    //      in its right subtree (which must reside in a leaf), and then revert to the leaf\n+    //      case\n+    //\n+    // # handling underflow\n+    //      After removing an item, there may be too few items in the node. We want nodes\n+    //      to be mostly full for efficiency, although we make an exception for the root, which\n+    //      may have as few as one item. If this is the case, we may first try to steal\n+    //      an item from our left or right neighbour.\n+    //\n+    //      To steal from the left (right) neighbour,\n+    //      we take the largest (smallest) item and child from it. We then swap the taken item\n+    //      with the item in their mutual parent that separates them, and then insert the\n+    //      parent's item and the taken child into the first (last) index of the underflowed node.\n+    //\n+    //      However, stealing has the possibility of underflowing our neighbour. If this is the\n+    //      case, we instead *merge* with our neighbour. This of course reduces the number of\n+    //      children in the parent. Therefore, we also steal the item that separates the now\n+    //      merged nodes, and insert it into the merged node.\n+    //\n+    //      Merging may cause the parent to underflow. If this is the case, then we must repeat\n+    //      the underflow handling process on the parent. If merging merges the last two children\n+    //      of the root, then we replace the root with the merged node.\n+\n+    fn pop(&mut self, key: &K) -> Option<V> {\n+        // See `swap` for a more thorough description of the stuff going on in here\n+        let mut stack = stack::PartialSearchStack::new(self);\n+        loop {\n+            match stack.next().search(key) {\n+                Found(i) => {\n+                    // Perfect match. Terminate the stack here, and remove the entry\n+                    return Some(stack.seal(i).remove());\n+                },\n+                GoDown(i) => {\n+                    // We need to keep searching, try to go down the next edge\n+                    stack = match stack.push(i) {\n+                        stack::Done(_) => return None, // We're at a leaf; the key isn't in here\n+                        stack::Grew(new_stack) => {\n+                            new_stack\n+                        }\n+                    };\n+                }\n+            }\n+        }\n+    }\n+}\n+\n+/// The stack module provides a safe interface for constructing and manipulating a stack of ptrs\n+/// to nodes. By using this module much better safety guarantees can be made, and more search\n+/// boilerplate gets cut out.\n+mod stack {\n+    use core::prelude::*;\n+    use super::BTreeMap;\n+    use super::super::node::*;\n+    use core::ptr;\n+    use {MutableMap, MutableSeq};\n+    use vec::Vec;\n+\n+    type StackItem<K, V> = (*mut Node<K, V>, uint);\n+    type Stack<K, V> = Vec<StackItem<K, V>>;\n+\n+    /// A PartialSearchStack handles the construction of a search stack.\n+    pub struct PartialSearchStack<'a, K:'a, V:'a> {\n+        map: &'a mut BTreeMap<K, V>,\n+        stack: Stack<K, V>,\n+        next: *mut Node<K, V>,\n+    }\n+\n+    /// A SearchStack represents a full path to an element of interest. It provides methods\n+    /// for manipulating the element at the top of its stack.\n+    pub struct SearchStack<'a, K:'a, V:'a> {\n+        map: &'a mut BTreeMap<K, V>,\n+        stack: Stack<K, V>,\n+        top: StackItem<K, V>,\n+    }\n+\n+    /// The result of asking a PartialSearchStack to push another node onto itself. Either it\n+    /// Grew, in which case it's still Partial, or it found its last node was actually a leaf, in\n+    /// which case it seals itself and yields a complete SearchStack\n+    pub enum PushResult<'a, K:'a, V:'a> {\n+        Grew(PartialSearchStack<'a, K, V>),\n+        Done(SearchStack<'a, K, V>),\n+    }\n+\n+    impl<'a, K, V> PartialSearchStack<'a, K, V> {\n+        /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the\n+        /// root of the tree.\n+        pub fn new<'a>(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {\n+            let depth = map.depth;\n+\n+            PartialSearchStack {\n+                next: &mut map.root as *mut _,\n+                map: map,\n+                stack: Vec::with_capacity(depth),\n+            }\n+        }\n+\n+        /// Pushes the requested child of the stack's current top on top of the stack. If the child\n+        /// exists, then a new PartialSearchStack is yielded. Otherwise, a full SearchStack is\n+        /// yielded.\n+        pub fn push(self, edge: uint) -> PushResult<'a, K, V> {\n+            let map = self.map;\n+            let mut stack = self.stack;\n+            let next_ptr = self.next;\n+            let next_node = unsafe {\n+                &mut *next_ptr\n+            };\n+            let to_insert = (next_ptr, edge);\n+            match next_node.edge_mut(edge) {\n+                None => Done(SearchStack {\n+                    map: map,\n+                    stack: stack,\n+                    top: to_insert,\n+                }),\n+                Some(node) => {\n+                    stack.push(to_insert);\n+                    Grew(PartialSearchStack {\n+                        map: map,\n+                        stack: stack,\n+                        next: node as *mut _,\n+                    })\n+                },\n+            }\n+        }\n+\n+        /// Converts the stack into a mutable reference to its top\n+        pub fn into_next(self) -> &'a mut Node<K, V> {\n+            unsafe {\n+                &mut *self.next\n+            }\n+        }\n+\n+        /// Gets the top of the stack\n+        pub fn next(&self) -> &Node<K, V> {\n+            unsafe {\n+                &*self.next\n+            }\n+        }\n+\n+        /// Converts the PartialSearchStack into a SearchStack\n+        pub fn seal(self, index: uint) -> SearchStack<'a, K, V> {\n+            SearchStack {\n+                map: self.map,\n+                stack: self.stack,\n+                top: (self.next as *mut _, index),\n+            }\n+        }\n+    }\n+\n+    impl<'a, K, V> SearchStack<'a, K, V> {\n+        /// Get a reference to the value the stack points to\n+        pub fn peek(&self) -> &V {\n+            let (node_ptr, index) = self.top;\n+            unsafe {\n+                (*node_ptr).val(index).unwrap()\n+            }\n+        }\n+\n+        /// Get a mutable reference to the value the stack points to\n+        pub fn peek_mut(&mut self) -> &mut V {\n+            let (node_ptr, index) = self.top;\n+            unsafe {\n+                (*node_ptr).val_mut(index).unwrap()\n+            }\n+        }\n+\n+        /// Converts the stack into a mutable reference to the value it points to, with a lifetime\n+        /// tied to the original tree\n+        pub fn into_top(self) -> &'a mut V {\n+            let (node_ptr, index) = self.top;\n+            unsafe {\n+                (*node_ptr).val_mut(index).unwrap()\n+            }\n+        }\n+\n+        /// Inserts the key and value into the top element in the stack, and if that node has to\n+        /// split recursively inserts the split contents into the next element stack until\n+        /// splits stop.\n+        ///\n+        /// Assumes that the stack represents a search path from the root to a leaf.\n+        ///\n+        /// An &mut V is returned to the inserted value, for callers that want a reference to this.\n+        pub fn insert(self, key: K, val: V) -> &'a mut V {\n+            unsafe {\n+                let map = self.map;\n+                map.length += 1;\n+\n+                let mut stack = self.stack;\n+                // Insert the key and value into the leaf at the top of the stack\n+                let (node, index) = self.top;\n+                let (mut insertion, inserted_ptr) = {\n+                    (*node).insert_as_leaf(index, key, val)\n+                };\n+\n+                loop {\n+                    match insertion {\n+                        Fit => {\n+                            // The last insertion went off without a hitch, no splits! We can stop\n+                            // inserting now.\n+                            return &mut *inserted_ptr;\n+                        }\n+                        Split(key, val, right) => match stack.pop() {\n+                            // The last insertion triggered a split, so get the next element on the\n+                            // stack to revursively insert the split node into.\n+                            None => {\n+                                // The stack was empty; we've split the root, and need to make a\n+                                // a new one.\n+\n+                                // The unsafe optionless option dance\n+                                let root_ptr = &mut map.root as *mut _;\n+                                let root = ptr::read(root_ptr as *const _);\n+                                ptr::write(root_ptr,\n+                                    Node::make_internal_root(map.b, key, val, root, right));\n+\n+                                map.depth += 1;\n+                                return &mut *inserted_ptr;\n+                            }\n+                            Some((node, index)) => {\n+                                // The stack wasn't empty, do the insertion and recurse\n+                                insertion = (*node).insert_as_internal(index, key, val, right);\n+                                continue;\n+                            }\n+                        }\n+                    }\n+                }\n+            }\n+        }\n+\n+        /// Removes the key and value in the top element of the stack, then handles underflows as\n+        /// described in BTree's pop function.\n+        pub fn remove(mut self) -> V {\n+            // Ensure that the search stack goes to a leaf. This is necessary to perform deletion\n+            // in a BTree. Note that this may put the tree in an inconsistent state (further\n+            // described in leafify_stack's comments), but this is immediately fixed by the\n+            // removing the value we want to remove\n+            self.leafify();\n+\n+            let map = self.map;\n+            map.length -= 1;\n+\n+            let mut stack = self.stack;\n+\n+            // Remove the key-value pair from the leaf, check if the node is underfull, and then\n+            // promptly forget the leaf and ptr to avoid ownership issues","path":"src/libcollections/btree/map.rs","position":478,"original_position":478,"commit_id":"45b7aeec93b2eefc8fbc8848c1293c0d73363a41","original_commit_id":"45b7aeec93b2eefc8fbc8848c1293c0d73363a41","user":{"login":"huonw","id":1203825,"avatar_url":"https://avatars.githubusercontent.com/u/1203825?v=2","gravatar_id":"","url":"https://api.github.com/users/huonw","html_url":"https://github.com/huonw","followers_url":"https://api.github.com/users/huonw/followers","following_url":"https://api.github.com/users/huonw/following{/other_user}","gists_url":"https://api.github.com/users/huonw/gists{/gist_id}","starred_url":"https://api.github.com/users/huonw/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/huonw/subscriptions","organizations_url":"https://api.github.com/users/huonw/orgs","repos_url":"https://api.github.com/users/huonw/repos","events_url":"https://api.github.com/users/huonw/events{/privacy}","received_events_url":"https://api.github.com/users/huonw/received_events","type":"User","site_admin":false},"body":"What is the 'leaf and ptr' talking about here exactly?","created_at":"2014-09-25T10:01:23Z","updated_at":"2014-09-25T10:01:23Z","html_url":"https://github.com/rust-lang/rust/pull/17334#discussion_r18023705","pull_request_url":"https://api.github.com/repos/rust-lang/rust/pulls/17334","_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments/18023705"},"html":{"href":"https://github.com/rust-lang/rust/pull/17334#discussion_r18023705"},"pull_request":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/17334"}}},"pull_request":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/17334","id":21344633,"html_url":"https://github.com/rust-lang/rust/pull/17334","diff_url":"https://github.com/rust-lang/rust/pull/17334.diff","patch_url":"https://github.com/rust-lang/rust/pull/17334.patch","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/17334","number":17334,"state":"open","locked":false,"title":"complete btree rewrite","user":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=2","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"body":"Replaces BTree with BTreeMap and BTreeSet, which are completely new implementations.\r\nBTreeMap's internal Node representation is particularly inefficient at the moment to\r\nmake this first implementation easy to reason about and fairly safe. Both collections\r\nare also currently missing some of the tooling specific to sorted collections, which\r\nis planned as future work pending reform of these APIs. General implementation issues\r\nare discussed with TODOs internally\r\n\r\n[breaking-change]\r\n\r\nStill waiting on compilation/test/bench stuff locally, but the edit-distance on any errors should be very small at this point. This is ready to be reviewed.","created_at":"2014-09-17T04:39:44Z","updated_at":"2014-09-25T10:01:23Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0694afc6ff92eef62ec52560946a4c6f0336a61e","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/rust-lang/rust/pulls/17334/commits","review_comments_url":"https://api.github.com/repos/rust-lang/rust/pulls/17334/comments","review_comment_url":"https://api.github.com/repos/rust-lang/rust/pulls/comments/{number}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/17334/comments","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/45b7aeec93b2eefc8fbc8848c1293c0d73363a41","head":{"label":"Gankro:btree-vec","ref":"btree-vec","sha":"45b7aeec93b2eefc8fbc8848c1293c0d73363a41","user":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=2","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"repo":{"id":21621250,"name":"rust","full_name":"Gankro/rust","owner":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=2","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Gankro/rust","description":"a safe, concurrent, practical language","fork":true,"url":"https://api.github.com/repos/Gankro/rust","forks_url":"https://api.github.com/repos/Gankro/rust/forks","keys_url":"https://api.github.com/repos/Gankro/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Gankro/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Gankro/rust/teams","hooks_url":"https://api.github.com/repos/Gankro/rust/hooks","issue_events_url":"https://api.github.com/repos/Gankro/rust/issues/events{/number}","events_url":"https://api.github.com/repos/Gankro/rust/events","assignees_url":"https://api.github.com/repos/Gankro/rust/assignees{/user}","branches_url":"https://api.github.com/repos/Gankro/rust/branches{/branch}","tags_url":"https://api.github.com/repos/Gankro/rust/tags","blobs_url":"https://api.github.com/repos/Gankro/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Gankro/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Gankro/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/Gankro/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Gankro/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/Gankro/rust/languages","stargazers_url":"https://api.github.com/repos/Gankro/rust/stargazers","contributors_url":"https://api.github.com/repos/Gankro/rust/contributors","subscribers_url":"https://api.github.com/repos/Gankro/rust/subscribers","subscription_url":"https://api.github.com/repos/Gankro/rust/subscription","commits_url":"https://api.github.com/repos/Gankro/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/Gankro/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/Gankro/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/Gankro/rust/issues/comments/{number}","contents_url":"https://api.github.com/repos/Gankro/rust/contents/{+path}","compare_url":"https://api.github.com/repos/Gankro/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Gankro/rust/merges","archive_url":"https://api.github.com/repos/Gankro/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Gankro/rust/downloads","issues_url":"https://api.github.com/repos/Gankro/rust/issues{/number}","pulls_url":"https://api.github.com/repos/Gankro/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/Gankro/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/Gankro/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Gankro/rust/labels{/name}","releases_url":"https://api.github.com/repos/Gankro/rust/releases{/id}","created_at":"2014-07-08T16:53:48Z","updated_at":"2014-07-08T22:25:33Z","pushed_at":"2014-09-25T01:54:13Z","git_url":"git://github.com/Gankro/rust.git","ssh_url":"git@github.com:Gankro/rust.git","clone_url":"https://github.com/Gankro/rust.git","svn_url":"https://github.com/Gankro/rust","homepage":"http://www.rust-lang.org","size":162445,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"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":"8d3728fae0fa1979349836be112562aa6d455e76","user":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=2","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":724712,"name":"rust","full_name":"rust-lang/rust","owner":{"login":"rust-lang","id":5430905,"avatar_url":"https://avatars.githubusercontent.com/u/5430905?v=2","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/rust","description":"a safe, concurrent, practical language","fork":false,"url":"https://api.github.com/repos/rust-lang/rust","forks_url":"https://api.github.com/repos/rust-lang/rust/forks","keys_url":"https://api.github.com/repos/rust-lang/rust/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rust-lang/rust/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rust-lang/rust/teams","hooks_url":"https://api.github.com/repos/rust-lang/rust/hooks","issue_events_url":"https://api.github.com/repos/rust-lang/rust/issues/events{/number}","events_url":"https://api.github.com/repos/rust-lang/rust/events","assignees_url":"https://api.github.com/repos/rust-lang/rust/assignees{/user}","branches_url":"https://api.github.com/repos/rust-lang/rust/branches{/branch}","tags_url":"https://api.github.com/repos/rust-lang/rust/tags","blobs_url":"https://api.github.com/repos/rust-lang/rust/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rust-lang/rust/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rust-lang/rust/git/refs{/sha}","trees_url":"https://api.github.com/repos/rust-lang/rust/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rust-lang/rust/statuses/{sha}","languages_url":"https://api.github.com/repos/rust-lang/rust/languages","stargazers_url":"https://api.github.com/repos/rust-lang/rust/stargazers","contributors_url":"https://api.github.com/repos/rust-lang/rust/contributors","subscribers_url":"https://api.github.com/repos/rust-lang/rust/subscribers","subscription_url":"https://api.github.com/repos/rust-lang/rust/subscription","commits_url":"https://api.github.com/repos/rust-lang/rust/commits{/sha}","git_commits_url":"https://api.github.com/repos/rust-lang/rust/git/commits{/sha}","comments_url":"https://api.github.com/repos/rust-lang/rust/comments{/number}","issue_comment_url":"https://api.github.com/repos/rust-lang/rust/issues/comments/{number}","contents_url":"https://api.github.com/repos/rust-lang/rust/contents/{+path}","compare_url":"https://api.github.com/repos/rust-lang/rust/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rust-lang/rust/merges","archive_url":"https://api.github.com/repos/rust-lang/rust/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rust-lang/rust/downloads","issues_url":"https://api.github.com/repos/rust-lang/rust/issues{/number}","pulls_url":"https://api.github.com/repos/rust-lang/rust/pulls{/number}","milestones_url":"https://api.github.com/repos/rust-lang/rust/milestones{/number}","notifications_url":"https://api.github.com/repos/rust-lang/rust/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rust-lang/rust/labels{/name}","releases_url":"https://api.github.com/repos/rust-lang/rust/releases{/id}","created_at":"2010-06-16T20:39:03Z","updated_at":"2014-09-25T05:20:23Z","pushed_at":"2014-09-25T09:22:37Z","git_url":"git://github.com/rust-lang/rust.git","ssh_url":"git@github.com:rust-lang/rust.git","clone_url":"https://github.com/rust-lang/rust.git","svn_url":"https://github.com/rust-lang/rust","homepage":"http://www.rust-lang.org","size":471286,"stargazers_count":6520,"watchers_count":6520,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1294,"mirror_url":null,"open_issues_count":1919,"forks":1294,"open_issues":1919,"watchers":6520,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/17334"},"html":{"href":"https://github.com/rust-lang/rust/pull/17334"},"issue":{"href":"https://api.github.com/repos/rust-lang/rust/issues/17334"},"comments":{"href":"https://api.github.com/repos/rust-lang/rust/issues/17334/comments"},"review_comments":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/17334/comments"},"review_comment":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/rust-lang/rust/pulls/17334/commits"},"statuses":{"href":"https://api.github.com/repos/rust-lang/rust/statuses/45b7aeec93b2eefc8fbc8848c1293c0d73363a41"}}}}