9 files changed, 131 insertions, 39 deletions

diff --git a/crates/cli/src/main.rs b/crates/cli/src/main.rs
index b6e9139c7..fc28691fc 100644
--- a/crates/cli/src/main.rs
+++ b/crates/cli/src/main.rs
@@ -10,7 +10,7 @@ use std::{
 };
 use clap::{App, Arg, SubCommand};
 use tools::collect_tests;
-use libeditor::{File, syntax_tree, file_symbols};
+use libeditor::{File, syntax_tree, file_structure};
 
 type Result<T> = ::std::result::Result<T, failure::Error>;
 
@@ -51,7 +51,7 @@ fn main() -> Result<()> {
         }
         ("symbols", _) => {
             let file = file()?;
-            for s in file_symbols(&file) {
+            for s in file_structure(&file) {
                 println!("{:?}", s);
             }
         }
diff --git a/crates/libeditor/src/lib.rs b/crates/libeditor/src/lib.rs
index e5933cbd6..b40db2c66 100644
--- a/crates/libeditor/src/lib.rs
+++ b/crates/libeditor/src/lib.rs
@@ -19,7 +19,7 @@ pub use libsyntax2::{File, TextRange, TextUnit};
 pub use self::{
     line_index::{LineIndex, LineCol},
     extend_selection::extend_selection,
-    symbols::{FileSymbol, file_symbols},
+    symbols::{StructureNode, file_structure, FileSymbol, file_symbols},
     edit::{EditBuilder, Edit, AtomEdit},
     code_actions::{flip_comma},
 };
diff --git a/crates/libeditor/src/symbols.rs b/crates/libeditor/src/symbols.rs
index f1d5222f4..43f4164da 100644
--- a/crates/libeditor/src/symbols.rs
+++ b/crates/libeditor/src/symbols.rs
@@ -4,22 +4,58 @@ use libsyntax2::{
     ast::{self, NameOwner},
     algo::{
         visit::{visitor, Visitor},
-        walk::{walk, WalkEvent},
+        walk::{walk, WalkEvent, preorder},
     },
+    SyntaxKind::*,
 };
 use TextRange;
 
 #[derive(Debug)]
-pub struct FileSymbol {
+pub struct StructureNode {
     pub parent: Option<usize>,
-    pub name: SmolStr,
-    pub name_range: TextRange,
+    pub label: String,
+    pub navigation_range: TextRange,
     pub node_range: TextRange,
     pub kind: SyntaxKind,
 }
 
+#[derive(Debug)]
+pub struct FileSymbol {
+    pub name: SmolStr,
+    pub node_range: TextRange,
+    pub kind: SyntaxKind,
+}
 
 pub fn file_symbols(file: &ast::File) -> Vec<FileSymbol> {
+    let syntax = file.syntax();
+    preorder(syntax.as_ref())
+        .filter_map(to_symbol)
+        .collect()
+}
+
+fn to_symbol(node: SyntaxNodeRef) -> Option<FileSymbol> {
+    fn decl<'a, N: NameOwner<&'a SyntaxRoot>>(node: N) -> Option<FileSymbol> {
+        let name = node.name()?;
+        Some(FileSymbol {
+            name: name.text(),
+            node_range: node.syntax().range(),
+            kind: node.syntax().kind(),
+        })
+    }
+    visitor()
+        .visit(decl::<ast::FnDef<_>>)
+        .visit(decl::<ast::StructDef<_>>)
+        .visit(decl::<ast::EnumDef<_>>)
+        .visit(decl::<ast::TraitDef<_>>)
+        .visit(decl::<ast::Module<_>>)
+        .visit(decl::<ast::TypeDef<_>>)
+        .visit(decl::<ast::ConstDef<_>>)
+        .visit(decl::<ast::StaticDef<_>>)
+        .accept(node)?
+}
+
+
+pub fn file_structure(file: &ast::File) -> Vec<StructureNode> {
     let mut res = Vec::new();
     let mut stack = Vec::new();
     let syntax = file.syntax();
@@ -27,7 +63,7 @@ pub fn file_symbols(file: &ast::File) -> Vec<FileSymbol> {
     for event in walk(syntax.as_ref()) {
         match event {
             WalkEvent::Enter(node) => {
-                match to_symbol(node) {
+                match structure_node(node) {
                     Some(mut symbol) => {
                         symbol.parent = stack.last().map(|&n| n);
                         stack.push(res.len());
@@ -37,7 +73,7 @@ pub fn file_symbols(file: &ast::File) -> Vec<FileSymbol> {
                 }
             }
             WalkEvent::Exit(node) => {
-                if to_symbol(node).is_some() {
+                if structure_node(node).is_some() {
                     stack.pop().unwrap();
                 }
             }
@@ -46,13 +82,13 @@ pub fn file_symbols(file: &ast::File) -> Vec<FileSymbol> {
     res
 }
 
-fn to_symbol(node: SyntaxNodeRef) -> Option<FileSymbol> {
-    fn decl<'a, N: NameOwner<&'a SyntaxRoot>>(node: N) -> Option<FileSymbol> {
+fn structure_node(node: SyntaxNodeRef) -> Option<StructureNode> {
+    fn decl<'a, N: NameOwner<&'a SyntaxRoot>>(node: N) -> Option<StructureNode> {
         let name = node.name()?;
-        Some(FileSymbol {
+        Some(StructureNode {
             parent: None,
-            name: name.text(),
-            name_range: name.syntax().range(),
+            label: name.text().to_string(),
+            navigation_range: name.syntax().range(),
             node_range: node.syntax().range(),
             kind: node.syntax().kind(),
         })
@@ -67,5 +103,29 @@ fn to_symbol(node: SyntaxNodeRef) -> Option<FileSymbol> {
         .visit(decl::<ast::TypeDef<_>>)
         .visit(decl::<ast::ConstDef<_>>)
         .visit(decl::<ast::StaticDef<_>>)
+        .visit(|im: ast::ImplItem<_>| {
+            let mut label = String::new();
+            let brace = im.syntax().children()
+                .find(|it| {
+                    let stop = it.kind() == L_CURLY;
+                    if !stop {
+                        label.push_str(&it.text());
+                    }
+                    stop
+                })?;
+            let navigation_range = TextRange::from_to(
+                im.syntax().range().start(),
+                brace.range().start(),
+            );
+
+            let node = StructureNode {
+                parent: None,
+                label,
+                navigation_range,
+                node_range: im.syntax().range(),
+                kind: im.syntax().kind(),
+            };
+            Some(node)
+        })
         .accept(node)?
 }
diff --git a/crates/libeditor/tests/test.rs b/crates/libeditor/tests/test.rs
index fab2e4ad3..97fa30e1f 100644
--- a/crates/libeditor/tests/test.rs
+++ b/crates/libeditor/tests/test.rs
@@ -9,7 +9,7 @@ use itertools::Itertools;
 use libsyntax2::AstNode;
 use libeditor::{
     File, TextUnit, TextRange,
-    highlight, runnables, extend_selection, file_symbols, flip_comma,
+    highlight, runnables, extend_selection, file_structure, flip_comma,
 };
 
 #[test]
@@ -66,7 +66,7 @@ fn test_foo() {}
 }
 
 #[test]
-fn symbols() {
+fn test_structure() {
     let file = file(r#"
 struct Foo {
     x: i32
@@ -80,16 +80,22 @@ enum E { X, Y(i32) }
 type T = ();
 static S: i32 = 92;
 const C: i32 = 92;
+
+impl E {}
+
+impl fmt::Debug for E {}
 "#);
-    let symbols = file_symbols(&file);
+    let symbols = file_structure(&file);
     dbg_eq(
-        r#"[FileSymbol { parent: None, name: "Foo", name_range: [8; 11), node_range: [1; 26), kind: STRUCT_DEF },
-            FileSymbol { parent: None, name: "m", name_range: [32; 33), node_range: [28; 53), kind: MODULE },
-            FileSymbol { parent: Some(1), name: "bar", name_range: [43; 46), node_range: [40; 51), kind: FN_DEF },
-            FileSymbol { parent: None, name: "E", name_range: [60; 61), node_range: [55; 75), kind: ENUM_DEF },
-            FileSymbol { parent: None, name: "T", name_range: [81; 82), node_range: [76; 88), kind: TYPE_DEF },
-            FileSymbol { parent: None, name: "S", name_range: [96; 97), node_range: [89; 108), kind: STATIC_DEF },
-            FileSymbol { parent: None, name: "C", name_range: [115; 116), node_range: [109; 127), kind: CONST_DEF }]"#,
+        r#"[StructureNode { parent: None, label: "Foo", navigation_range: [8; 11), node_range: [1; 26), kind: STRUCT_DEF },
+           StructureNode { parent: None, label: "m", navigation_range: [32; 33), node_range: [28; 53), kind: MODULE },
+           StructureNode { parent: Some(1), label: "bar", navigation_range: [43; 46), node_range: [40; 51), kind: FN_DEF },
+           StructureNode { parent: None, label: "E", navigation_range: [60; 61), node_range: [55; 75), kind: ENUM_DEF },
+           StructureNode { parent: None, label: "T", navigation_range: [81; 82), node_range: [76; 88), kind: TYPE_DEF },
+           StructureNode { parent: None, label: "S", navigation_range: [96; 97), node_range: [89; 108), kind: STATIC_DEF },
+           StructureNode { parent: None, label: "C", navigation_range: [115; 116), node_range: [109; 127), kind: CONST_DEF },
+           StructureNode { parent: None, label: "impl E ", navigation_range: [129; 136), node_range: [129; 138), kind: IMPL_ITEM },
+           StructureNode { parent: None, label: "impl fmt::Debug for E ", navigation_range: [140; 162), node_range: [140; 164), kind: IMPL_ITEM }]"#,
         &symbols,
     )
 }
diff --git a/crates/libsyntax2/src/ast/generated.rs b/crates/libsyntax2/src/ast/generated.rs
index b347a05b4..13668b803 100644
--- a/crates/libsyntax2/src/ast/generated.rs
+++ b/crates/libsyntax2/src/ast/generated.rs
@@ -86,6 +86,24 @@ impl<R: TreeRoot> AstNode<R> for FnDef<R> {
 impl<R: TreeRoot> ast::NameOwner<R> for FnDef<R> {}
 impl<R: TreeRoot> FnDef<R> {}
 
+// ImplItem
+#[derive(Debug, Clone, Copy)]
+pub struct ImplItem<R: TreeRoot = Arc<SyntaxRoot>> {
+    syntax: SyntaxNode<R>,
+}
+
+impl<R: TreeRoot> AstNode<R> for ImplItem<R> {
+    fn cast(syntax: SyntaxNode<R>) -> Option<Self> {
+        match syntax.kind() {
+            IMPL_ITEM => Some(ImplItem { syntax }),
+            _ => None,
+        }
+    }
+    fn syntax(&self) -> &SyntaxNode<R> { &self.syntax }
+}
+
+impl<R: TreeRoot> ImplItem<R> {}
+
 // Module
 #[derive(Debug, Clone, Copy)]
 pub struct Module<R: TreeRoot = Arc<SyntaxRoot>> {
diff --git a/crates/libsyntax2/src/ast/mod.rs b/crates/libsyntax2/src/ast/mod.rs
index 18a9f5d17..f001d340e 100644
--- a/crates/libsyntax2/src/ast/mod.rs
+++ b/crates/libsyntax2/src/ast/mod.rs
@@ -10,8 +10,9 @@ use {
 };
 pub use self::generated::*;
 
-pub trait AstNode<R: TreeRoot>: Sized {
-    fn cast(syntax: SyntaxNode<R>) -> Option<Self>;
+pub trait AstNode<R: TreeRoot> {
+    fn cast(syntax: SyntaxNode<R>) -> Option<Self>
+        where Self: Sized;
     fn syntax(&self) -> &SyntaxNode<R>;
 }
 
diff --git a/crates/libsyntax2/src/grammar.ron b/crates/libsyntax2/src/grammar.ron
index ef56761fd..ebd7d3943 100644
--- a/crates/libsyntax2/src/grammar.ron
+++ b/crates/libsyntax2/src/grammar.ron
@@ -229,6 +229,7 @@ Grammar(
         "ConstDef": ( traits: ["NameOwner"] ),
         "StaticDef": ( traits: ["NameOwner"] ),
         "TypeDef": ( traits: ["NameOwner"] ),
+        "ImplItem": (),
         "Name": (),
         "NameRef": (),
     },
diff --git a/crates/server/src/conv.rs b/crates/server/src/conv.rs
index 3aa255e6a..3ddce5fb3 100644
--- a/crates/server/src/conv.rs
+++ b/crates/server/src/conv.rs
@@ -36,6 +36,7 @@ impl Conv for SyntaxKind {
             SyntaxKind::TYPE_DEF => SymbolKind::TypeParameter,
             SyntaxKind::STATIC_DEF => SymbolKind::Constant,
             SyntaxKind::CONST_DEF => SymbolKind::Constant,
+            SyntaxKind::IMPL_ITEM => SymbolKind::Object,
             _ => SymbolKind::Variable,
         }
     }
diff --git a/crates/server/src/main_loop/handlers.rs b/crates/server/src/main_loop/handlers.rs
index bfdfcb51e..8789ef0d2 100644
--- a/crates/server/src/main_loop/handlers.rs
+++ b/crates/server/src/main_loop/handlers.rs
@@ -48,29 +48,34 @@ pub fn handle_document_symbol(
     let file = world.file_syntax(&path)?;
     let line_index = world.file_line_index(&path)?;
 
-    let mut res: Vec<DocumentSymbol> = Vec::new();
+    let mut parents: Vec<(DocumentSymbol, Option<usize>)> = Vec::new();
 
-    for symbol in libeditor::file_symbols(&file) {
-        let name = symbol.name.to_string();
+    for symbol in libeditor::file_structure(&file) {
         let doc_symbol = DocumentSymbol {
-            name: name.clone(),
-            detail: Some(name),
+            name: symbol.label,
+            detail: Some("".to_string()),
             kind: symbol.kind.conv(),
             deprecated: None,
             range: symbol.node_range.conv_with(&line_index),
-            selection_range: symbol.name_range.conv_with(&line_index),
+            selection_range: symbol.navigation_range.conv_with(&line_index),
             children: None,
         };
-        if let Some(idx) = symbol.parent {
-            let children = &mut res[idx].children;
-            if children.is_none() {
-                *children = Some(Vec::new());
+        parents.push((doc_symbol, symbol.parent));
+    }
+    let mut res = Vec::new();
+    while let Some((node, parent)) = parents.pop() {
+        match parent {
+            None => res.push(node),
+            Some(i) => {
+                let children = &mut parents[i].0.children;
+                if children.is_none() {
+                    *children = Some(Vec::new());
+                }
+                children.as_mut().unwrap().push(node);
             }
-            children.as_mut().unwrap().push(doc_symbol);
-        } else {
-            res.push(doc_symbol);
         }
     }
+
     Ok(Some(req::DocumentSymbolResponse::Nested(res)))
 }