Quick navigation in DocC Render

Hi everyone! I'm very excited to be finally participating in this forum, this is my first interaction with the community through this platform so I'm kinda nervous but I'm also happy to show up :smile:

I'm interested in working on the GSoC project "Quick navigation in DocC Render" mentored by @beatriz and @ Marina Aisa (not sure which is her handle).

Context

DocC is a tool for building interactive and intuitive-looking documentation for your Swift frameworks, libraries, and packages. Is integrated into Xcode and creates a standardized UI with all the exposed symbols linked in a way that is very easy to navigate and understand what a certain package does and how is supposed to be used. At a high level, what this tool does is that it goes through the project files searching for documentation comments, scans the comments, formats them depending on the context, then attaches them into the build documentation. Besides of this it also supports articles and tutorials.

All this documentation can be exported into a .doccarchive package, containing all the needed files to display the documentation comments, tutorials, and articles, either on Xcode, or shared and distributed online, having it hosted on a server. The web app generated to share the documentation on the web is a Vue application. More info about the distribution process can be found here.

Project Overview

Until recently the renderer of the .docarchive on the web didn't provide an easy way to navigate through the project symbols like we do when we open the documentation in Xcode with the sidebar. This changed last month when the DocC team introduced a sidebar into the Swift-DocC-Render project (Swift-DocC-Render is the SPA powered by Vue.js used to create the code documentation website). The ideation process of the sidebar and more details about it can be read in the Swift forum Swift-DocC sidebar discussion, and the implementation details can be found on the Swift-DocC-Render GitHub repo.

Now, this sidebar doesn't have quick navigation or keyboard shortcuts to jump between symbols, so the idea here is to design and implement a natural way to accomplish this. Having quick navigation would help to move between documentation files faster in an intuitive way, increasing productivity and making the website more accessible to the user.

Use Cases

If I'm on the DocC render Documentation Web I might want to do the following using keyboard shortcuts:

  • Move one file up on the file tree
  • Move one file down on the file tree
  • Go back and forth between symbols I last visited
  • Focus the Filter in **DocC-name** search bar to look for a symbol
  • Filter a specific symbol type in the navigation sidebar
  • Open a quick file navigation bar with more symbol filter capabilities than the current Filter in **DocC-name** search bar has, similar to what most IDEs have (not sure if this is out of scope from the GSoC project statement)

Challenges

One of the biggest challenges I see is from the UX perspective. The design process must address which key combination results in the most intuitive shortcut for the user, creating a mnemonic combination that helps the user to learn it over time, and making the shortcut unique in a way that doesn't conflict with any of the browser or O.S native shortcuts.

Questions for the community

  1. Any other use case you can think of?
  2. There's an accessibility/web standard for designing these shortcuts?
  3. Which are your favorite/most used keyboard shortcuts when you are navigating through your code in an IDE or web app?
  4. Anything that I might be missing out from the problem prompt?
  5. For the mentors @beatriz @ marina, there's any additional insight, documentation, or previous discussion we should take into account for making this implementation?
  6. Any other general thoughts about this?

Any opinions and feedback are highly appreciated!

Rn, I'm setting up the project locally on my machine to have a better sense of how it's structured and how the sidebar was integrated, I'll be sharing any update once I get my investigation going.

I hope this is the perspective of the project that the GSoC mentors had in mind, if not pls pls point me in the right direction, I'm making my best to go out of my introvert bubble here :sweat_smile:

Thank y'all for bearing with me up to this point!!

Sofía Rodríguez :venezuela:

15 Likes

¡Hola @sofiaromorales ! :)
Thank you so much for showing your interest on this GSoC project! @beatriz and I are so happy to receive your message!

I've been reviewing the use cases that you proposed. They are great improvements, and made me think of a few questions:

  • Move one file up on the file tree
  • Move one file down on the file tree
  • Go back and forth between symbols I last visited
    • Visited symbols are part of the browser history, why not to use the native back and forth native buttons in the browser instead?
  • Focus the Filter in DocC-name search bar to look for a symbol
    • Do you mean a shortcut to focus the filter from anywhere in the page? This could be a really nice idea.
  • Filter a specific symbol type in the navigation sidebar
    • This is on the roadmap for sure but I'm not sure if it's scoped for this project
      You totally nailed it with the last use case which it's exactly what we are looking for:
      The proposal we would like to achieve is a search field presented as a modal element to elevate the searching experience to the main focus of the user.
      These are some examples that we can use as references, adapting them to the web platform:
  • "Quick Open" in VSCode
  • "Open Quickly" in Xcode

@beatriz and I haven't had any discussion about this feature yet so it would be a very good opportunity for you to be involved end-to-end. We have accessibility features across the page and we will continue having them as a big priority for this project.

Thanks again for your message, this is very exciting!

5 Likes

Hola @marinaaisa ! Thx you a lot for this! I took some time to set up the codebase locally and review some of the open PRs, the project seems very interesting

Do you mean navigating using the key arrows? I'm working on adding these accessibility features in this PR: [AX] Improve keyboard navigation when sidenav is enable by marinaaisa · Pull Request #79 · apple/swift-docc-render · GitHub Feel free to contribute to it too!

I forked your swift-docc-render repo and experimented navigating the sidebar with the keyboard, and is great, I especially liked being able to fold/unfold the nodes with the right/left arrows, and idk if it was part of that specific pr but being able to focus the sidebar with cmd + right/left arrow keys is :sparkles:

Visited symbols are part of the browser history, why not to use the native back and forth native buttons in the browser instead?

You are right, using ⌘ + [ and ⌘ + ] in Safari does the job :)

Do you mean a shortcut to focus the filter from anywhere in the page? This could be a really nice idea.

Yess, I feel like that would be nice to have, and combined with what you implemented here Pull Request #79 · apple/swift-docc-render · GitHub makes the keyboard navigation experience very complete. Sounds like a contribution I could make to get a hands-on on the code.

This is on the roadmap for sure but I'm not sure if it's scoped for this project

Yeah, thanks for clarifying what you are looking for in this project and sharing some references. I already have some ideas regarding the search field but I will do some research before sharing them to make sure that brings value to the DocC-render web-dev experience. As soon as I have something solid I will share it over here to know what you, @beatriz, and the rest of the community thinks.

@Marina I'm very excited too!

2 Likes

Do we have a keyboard shortcut to show all the keyboard shortcuts? Like on iPad, when you hold the command key and it shows a modal with all the shortcuts. I think "?" In some web apps also do this, when not focused on a text field, obviously :sweat_smile:. Not sure what is the best shortcut to activate this modal. I like the hold command on iPad, but not sure it would fit well with the web platform. Could also conflict with Safari on iPad too. I'm not sure I like "?", would be nice to do some research and find out if there is some kind of consensus overall that we could adopt.

1 Like

Hi @sofiaromorales !
Can't wait to see what you share with us!

Just as a reminder: contributor applications will open on Monday, April 4, 2022 at 18:00 UTC with Tuesday, April 19, 2022 18:00 UTC being the deadline to submit your application.

To get started, we recommend reading the materials provided by Summer of Code , including the Contributor / Student Guide , as well as Advice for Applying for GSoC .

I'm looking forward for your application soon! :slight_smile:

1 Like

Hi @Paulo_Faria !

Very interesting idea, thank you! :smiley:

I found that Wikipedia has a dedicated page to explain their own web shortcuts: Wikipedia:Keyboard shortcuts - Wikipedia

We may want to look into something similar for the Quick navigation in DocC Render.

As I told to Sofía, in case you are interested, remember that applications will be open on Monday, April 4, 2022 at 18:00 UTC with Tuesday, April 19, 2022 18:00 UTC being the deadline to submit your application.

To get started, we recommend reading the materials provided by Summer of Code , including the Contributor / Student Guide , as well as Advice for Applying for GSoC . :slight_smile:

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