Implement some trivial size_hints for various iterators

This also implements ExactSizeIterator where applicable.

Addresses most of the Iterator traits mentioned in #23708.

2 files changed, 18 insertions, 0 deletions

diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
index 54565afa4c6..28e3180063c 100644
--- a/src/librustc_data_structures/bitvec.rs
+++ b/src/librustc_data_structures/bitvec.rs
@@ -132,6 +132,11 @@ impl<'a> Iterator for BitVectorIter<'a> {
         self.idx += offset + 1;
         return Some(self.idx - 1);
     }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let (_, upper) = self.iter.size_hint();
+        (0, upper)
+    }
 }
 
 impl FromIterator<bool> for BitVector {
diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index 1945b82c031..e2b393071ff 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -334,6 +334,11 @@ impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
         self.next = edge.next_edge[self.direction.repr];
         Some((edge_index, edge))
     }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        // At most, all the edges in the graph.
+        (0, Some(self.graph.len_edges()))
+    }
 }
 
 pub struct DepthFirstTraversal<'g, N, E>
@@ -383,8 +388,16 @@ impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
         }
         next
     }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        // We will visit every node in the graph exactly once.
+        let remaining = self.graph.len_nodes() - self.visited.count();
+        (remaining, Some(remaining))
+    }
 }
 
+impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {}
+
 impl<E> Edge<E> {
     pub fn source(&self) -> NodeIndex {
         self.source