Quick navigation in DocC Render

Hi everyone! I made an overview and some designs of how the Quick Navigation in DocC Render could work.

The idea here is to design and implement a feature that allows the user to easily navigate the documentation symbols and file through searching and filter capabilities. Similar to what most IDEs and some web apps have, a modal with a search bar presented to the user at the center of the screen, for example, Xcode has Open Quickly that you can enable by pressing ⌘ + shift + o.

1. Search

So the main function of this Quick Navigation feature would be to list the symbol names that match the user input, this can be accomplished using fuzzy search.

2. Filter by type

Another function that I found in some IDE and thought might be useful (but not sure if it fits inside the project scope) is to add a Filter by symbol type functionality, similar to the normal search, this will show the symbols that it type matches the user input, this functionality would be activated when the user types the : character at the beginning of the input.

3. Keyboard navigation

To make the Quick Navigation feature accessible and easy to navigate I came up with different keyboard shortcuts to move around

  • To open the Quick Navigation search bar ⌘ + shift + o just like in Xcode
  • To navigate the result list up and down arrow keys
  • To access the file

Questions for the community

  1. There's any standard for organizing the results in this type of searching element? I could notice from different IDEs there's a pattern where the exact match goes on top of the list and the partial ones go at the end, but I was wondering if there's any documentation from W3 or any other organization regarding this. Also for ordering the result elements when they have the same match relevance, it should be alphabetically ordered? ordered by symbol type?

  2. In the design I added the symbol path next to the name, tried to follow the same structure as the sidebar, but idk if it makes sense to put it there since there could be multiple paths for a single symbol (SlothGenerator for example). Maybe following the page routing and using that for the symbols paths could work for this?

  3. Regarding the Filter by Type functionality, do you think there's a benefit and is a good addition to the feature? like, do you see yourself needing to filter by type? And if the answer is yes, there should be any type of partial string matching between the user input and the results? I kinda see it more like a total match

@marinaaisa @beatriz I was wondering if there's any problem if I contact you privately to get some feedback on my proposal before submitting it, also if anyone else would like to take a look lmk, It would be huge help.

Any other ideas or feedback would be appreciated! Have a great day :smile:

5 Likes

Hey @sofiaromorales,

Just wanted to say the designs look awesome and I think that Quick Navigation would be a great feature to have and would greatly improve the experience of using DocC Render and make it more IDE like.

Answers:

  1. I don't think there is any standard, and even if there is one I don't know that it is worth following it. I do think that if and when possible it makes sense to display more "relevant" results nearer the top. I don't have a good answer to what is relevant beyond that exact matches should definitely be at the top of the list.
  2. There should be only a single path for a given symbol AFAIK. I don't know that it is particularly helpful as the user wouldn't be interested in the path of the symbol in the vast majority of use cases.
  3. I don't see myself filtering by type specifically. However it might be interesting to add additional filters in the quick search using similar syntax to what you describe. Maybe filtering by language of the symbol would be interesting given that DocC is gaining support for documenting Objective-C (Extending Swift-DocC to support Objective-C documentation - #17 by franklin). This would be useful in frameworks that are multi-language.
1 Like

Hi @sofiaromorales! These mockups are super cool. The examples you picked to showcase the functionality are very clear and helpful. The outline of the key functionality also is spot on.

You’ve touched on one of the most challenging parts of this project. I agree with @daniel-grumberg that there’s no perfect standard right now. My advice is that whatever logic you end up picking should feel predictable and consistent to users.

I think this is worth exploring. Might be a tool that’s helpful at the least to understand someone else’s code. Or to narrow down results if you don’t remember the exact name of something.

To help determine what types of filters are the most useful, one tool you can consider using are user flows. It helps to think about different scenarios, define what a user is trying to achieve, and how easy or hard it is to get there.

Some other open questions and thoughts:

  1. How are you thinking about discoverability of this feature? How should users know it’s there and how to access it?
  2. Right now, the UI looks very similar to native Mac and Xcode’s. This might be confusing, could be worth exploring making it more visually different.
  3. I know you’re at the early stages of design, but I noticed the text and background doesn’t have enough contrast right now. If you’re curious, I typically use this contrast checker to verify the colors are accessible.

Marina and I would be happy to check out your proposal! I’m starting a group chat here in forums with the 3 of us.

1 Like

The kotlin doc search looks nice and could serve as inspiration.


1 Like

Hi @daniel-grumberg, thank you so much for your feedback!

I don't think there is any standard, and even if there is one I don't know that it is worth following it. I do think that if and when possible it makes sense to display more "relevant" results nearer the top. I don't have a good answer to what is relevant beyond that exact matches should definitely be at the top of the list.

I found that fuzzy search uses a similarity metric to decide which are the most relevant results for a giving input, this metric is calculated using the Levenshtein Algorithm. After comparing it to "Open Quickly" in Xcode and "Quick Open" in VSCode it seems like these tools use this algorithm, here is a resource from IBM explaining how it works. But as you said, it might not be worth the effort to implement it in the DocC render website, maybe there's a simplified version of the Levenshtein Algorithm that gets the work done.

There should be only a single path for a given symbol AFAIK. I don't know that it is particularly helpful as the user wouldn't be interested in the path of the symbol in the vast majority of use cases.

Yeap, I found that the path for each symbol is unique and it matches the page URL, regarding if it's helpful or not, the only reason I can think of where is worth having it is if the search functionality gets extended to also match the symbol path like most of the IDEs does, I'm wondering if @marinaaisa and @beatriz have already thought about this

I don't see myself filtering by type specifically. However it might be interesting to add additional filters in the quick search using similar syntax to what you describe. Maybe filtering by language of the symbol would be interesting given that DocC is gaining support for documenting Objective-C

This seems interesting to explore at some point but I need to test how DocC behaves with multilanguage codebases before integrating it into the quick navigation feature, cool to see that Swift-DocC now supports Objective-C :star_struck:

Thanks for the feedback @beatriz!

You’ve touched on one of the most challenging parts of this project. I agree with @daniel-grumberg that there’s no perfect standard right now. My advice is that whatever logic you end up picking should feel predictable and consistent to users.

I found that fuzzy search uses an algorithm to calculate the relevance of exact and partial matching string similarity = 1 - (edit_distance / min (len(term), len(word))) where edit_distance is calculated using the Levenshtein Distance algorithm, but as I mentioned to @daniel-grumberg this is probably over-engineering the solution that could end up affecting the website performance, so maybe there's a simple way of achieving this

How are you thinking about discoverability of this feature? How should users know it’s there and how to access it?

What I'm thinking regarding this is using the same command that is used to activate "Open Quickly" in Xcode ⌘ + shift + o. The reason why this might solve the discoverability issue relies on Jakob’s Law which states that "Users spend most of their time on other sites. This means that users prefer your site to work the same way as all the other sites they already know", if the user comes from developing in Xcode there's a big chance they will expect the same search functionality by pressing the same keyboard shortcut. Other options are to add a magnifier glass icon on the top right of the screen that triggers the modal on click like the one at Nuxt website, or implement what @Paulo_Faria suggested, a cheat sheet with all the website shortcuts.

Right now, the UI looks very similar to native Mac and Xcode’s. This might be confusing, could be worth exploring making it more visually different. I know you’re at the early stages of design, but I noticed the text and background doesn’t have enough contrast right now. If you’re curious, I typically use this contrast checker to verify the colors are accessible

Is great that you point this out bc I was designing it as similar to the native Mac search bar as possible, also thanks for the resource, I found that the codebase has its own color schema so I'm using those as a guide, I will do another iteration on the design and make it match as much as possible to the website, will share it over here once I have it.

I do like the idea of implementing a fuzzy search here, it seems like it would provide a great user experience. If this cannot be implemented fully on the DocC Render side, I wonder if the DocC compiler could emit some kind of efficient mapping of page titles and their "fuzzy derivations" in a file, so that DocC Render can more quickly find the page you're looking for without much computation. We'd want to look into the size of these mapping files, though, as I suspect they could get quite large for large frameworks.

1 Like

I don't think using Levenshtein distance is over-engineering things. It definitely seems appropriate. What I thought was being discussed was using knowledge about documentation users' needs to alter the rankings. For example, let's say I am a SlothCreator developer and I type "o Gen" then I might be interested in the properties of SlothGenerator ahead of something like FoodGenerator. It might make sense to display some associated symbols for every match. The popup could look something like:
User types "O Gen"

  • SlothGenerator
    • func generateSloth(in: Habitat) throws -> Sloth
    • Habitat
  • FoodGenerator
    • //stuff associated with FoodGenerator

In this scheme to the top level matches would be derived using the similarity metric you described, but the second level matches would be derived using knowledge about the top-level matches. However ,I don't think this is within the scope of this proposal upon further reflection and I don't have an answer as to how easy this would be to implement and if it's useful at all.

1 Like

That is unfortunately not realistic, c.f., Levenshtein automata can be simple and fast. The automatons would grow large very quickly. Having just the "fuzzy derivations" would be even worse. Consider all the strings with Levenshtein distance of 1 from "SlothGenerator", there are already 32 of them and they aren't useful enough (e.g. the user typing in "SlathGenerator" or "SothGenerator" is more indicative of a typo than the user trying to match via a shorter string).

2 Likes

@daniel-grumberg @franklin thanks so much for your feedback!

After doing some research regarding fuzzy search and algorithms to calculate string distance and similarity I don't think that using Levenshtein Distance is the way to go, mainly because of the use case, Levenshtein Distance works great for typo tolerance, if the user types a string with a wrong character there's a good amount of possibility that the desired result is going to appear on the match list, but in our case what we want is help the user to find symbols more quickly even if they don't remember the complete name, so making it typo tolerable is not part of the feature goal in my opinion. After looking closely at how other IDE searching engines work I realized that they don't correct typos either, they require all the input characters to appear somewhere on the symbol name to be included on the matching result list and in the same order as the user's input. As an example, if we base Quick Navigation on the Levenshtein Distance algorithm the similarity between tone and tune would get a decent matching score, but making this match doesn't make sense to show it to the user as a potential result in our case.

Also, I'm concerned about the scalability of the algorithms used for the fuzzy search implementations, for larger codebases this could be a problem because most of the possible solutions point out to a quadratic time affecting the performance of the website, that's why we need to find a way to decrease as possible the possible words on a first scan before making an exhaustive search of possible matches. Making the Quick Navigation feature fast, predictable and consistent to work against large codebases is what we are trying to achieve :boom:

So coming up with a possible solution for this I first decided to set the conditions a string must pass to be considered a potential match for the user input x:

  1. The potential match should contain all characters of x
  2. The potential match should have the characters of x in the same order of appearance

Optionally if we want to be more restrictive and improve performance there are a couple of things we can apply too

  • If the user input contains a blank space the search will be an exact search instead of fuzzy
  • The user input must contain at least three characters to trigger the fuzzy search, this reduces the number of possible matches
  • At least three characters from the input must appear in consecutive order in the string to be a possible match

As a reference, these restrictions are used in "Open Quickly" in Xcode.

There's still the question regarding how the result list items will be ordered.

The order of the possible matches in the list from top to bottom could be as follows

  1. Exact match
  2. Consecutively matched characters
  3. CamelCase matched characters
  4. Matched characters (in non-consecutive order)

This algorithm is not fully tested but I feel like is a good approximation to what we need, the idea is to rank each of the possible matches with a number and then place them on the list from the one with the higher score to the lowest. The scoring rules are:

  1. For each consecutively matched character: +10
  2. Match leading character: +5
  3. CamelCase matched character: +3
  4. Matched character: 0
  5. Unmatched character: -1

I made a small test case for the input Sloth

Term Consecutive match Leading character match CamelCase match Unmatched character Total
Sloth 50 5 3 0 58
sloths 50 5 0 -1 54
Sloth.Color 50 5 3 -6 52
Sloth.Power 50 5 3 -6 52
SlothCreator 50 5 3 -7 51
slothGenerator 50 5 0 -9 46
sackcloth 40 5 0 -4 41
cheesecloth 40 0 0 -6 34
splotches 30 5 0 -4 31

A fuzzy search will never be as fast as doing exact string matching but hopefully, we can get a decent load time using the generated index.json file and restricting the search with certain criteria.

There's this article that I used to come up with this proposal Reverse Engineering Sublime Text’s Fuzzy Match.

I'm very interested in your thoughts about this :)

8 Likes

Hi @sofiaromorales, was reading your post and I think it is awesome!. I Wish you get the project in GSoC.

1 Like

Yeah I think this is a good scheme! we can iterate over the exact scoring algorithm later. If needed we could emit a file from DocC that contains just the available symbol names to speed this up, instead of having to parse the whole index.json and extract the symbol names.

1 Like

I love the way you do very good research and take time reflecting before replying. It is inspiring. This is something that I will try to incorporate when contributing to this forum. Nice work!

1 Like

@ahmdyasser @Paulo_Faria thanks! that's very encouraging! trying to get my head around how Quick Navigation could work to write a solid project proposal :blush:

1 Like

Thank you for your awesome work and engagement in this project!

I agree. I think it would be interesting to surface that functionality in a more explicit way somewhere, along the lines of what you suggested with the Nuxt website, for example, but being consistent with Xcode is a good way to start.

Excited to see the next steps of this!

2 Likes

I like the idea of using Xcode as a reference. However, since Swift is increasing its efforts towards other platforms, It could also be valuable to take a look at more "neutral" shortcuts, if they exist at all? Maybe it would be a good exercise creating some sort of table of popular softwares and their shortcuts and see if there's some sort of consensus? Might be overkill, though? Hard to think this would be a showstopper for some.

Hi @sofiaromorales
I loved your research regarding fuzzy search and algorithms. Amazing work :clap:
Thanks for sharing the article about Reverse Engineering Sublime Text’s Fuzzy Match too!

2 Likes

Congrats for being accepted :partying_face:, was sure you would nail it!

2 Likes

Hi folks! I'm very excited to announce that I will keep developing this project during the next couple of months as part of GSoC22 (:partying_face:) guided by the most amazing mentors @marinaaisa @beatriz and @franklin. With their support and the community feedback, I'll design and implement "Quick navigation in DocC Render" a new feature for the Swift-DocC-Render project that aims to help developers to navigate and discover documentation symbols easily (similar to what you achieve with “Open Quickly” in Xcode but for the web). Since this is a project for the community it would help me a lot to have your feedback during the process :)

Primarily how this will work is that the user will trigger the Quick Navigation modal either via a keyboard shortcut or a UI element, with the modal activated the user will be able to type a keyword and get a list with the symbols that have a matching name with the user input back. Something similar is already implemented on the navigator sidebar but Quick Navigation will let you make a deeper search using exact and fuzzy string matching.

I already have some designs on what this tool will look like, I was careful to follow the same style as the rest of the web to get a consistent UI but there is still a lot of point of variation where we can get creative and design something that feels native and user friendly.

The quick navigation modal itself can be in three different states, an empty state when it doesn't have any input, the results-found state when there's some input and we get some results back, and the no-matches state, when there are no matches for the user input.

The x-mark icon next to the input bar would be used to clear out the user input, and to dismiss the tool it would be either by clicking outside of the modal or selecting a symbol from the results list.

Even though there are a lot of similar tools already implemented on IDEs and web-based documentation I still have some questions regarding the UI/UX that I want to share with you

  • Which would be the best shortcut to trigger the modal in terms of discoverability and ease to remember? I've been going back and forth between ⌘ + shift + o, used in Xcode to trigger Open Quickly, and /, used in websites such as Nuxt, Tailwind, and Apollo GraphQL to activate the search bar. / is an easier one but we might want to keep persistent with Xcode

  • How many results we should show back to the user? the results are going to be ordered in a way that you will see the most relevant at the top, but from the entire list, how many listed results are a good amount? should this be a fixed number or maybe we should use some kind of percentage based on a similarity metric?

  • Been thinking that for performance reasons (considering very large documentation) we might want to trigger the search only when the user types a keyword of 3 or more characters (this is an idea that I got from Open Quickly in Xcode) if this is the case, which is the best way to let the user know this 3-characters rule?

I'm looking forward to having your feedback, either on the design or on the questions I made, and know what y'all think about this, thanks! :smile:

10 Likes

Sofía, so excited about your progress! This is looking great. I have some thoughts on your questions:

I think it would be interesting to stay consistent with Xcode since folks will often be using documentation in both places.

I'd start by using Xcode as a reference for consistency as well. It seems like the way that works is showing 8 at a time, and letting folks scroll down to see up to 20 results.

That sounds wise to me. That's pretty standard behavior for this type of component, I think folks will catch on quickly as they're using it and typing things out.