Code fragment context building functionality

[josevalim]

Hi @scohen and @scottming! (cc @lukaszsamson)

I would discuss some of the context building functionality that you mentioned. I have specific questions in this document that I would like your input on.

When we are working on a file, we need to provide completion on variable names, imports and so on. For example, take this buffer:

defmodule Foo do
  import Baz

  def bat do
    var = 123
    {<CURSOR>
  end

  def local_function do
    ...
  end
end

Where <CURSOR> is where the mouse cursor is. In order to provide completion, we need three things:

1. A parser that is robust to syntax failures

2. Build a local context with imports, variables, aliases, local functions, etc

3. Understand which kind of completion we should provide (alias? function call? variable name?).

We only provide step 3 at the moment via cursor_context. My goal for now is to focus on step 2 (and then we can discuss step 1). To build a local context, we have 3 main sources of data: lexical, variables, and module data. Let's discuss them one by one.

import, aliases, requires

This is the easiest information to gather. It can be done by 1. traversing the AST and then 2. defensively expanding all AST node, collecting all imports, aliases, and requires along the way.

Building the AST can be done with container_cursor_to_quoted. We don't have at the moment a safe way to expand its nodes. This could be provided.

Variables

Variables are trickier because they have more complex scoping rules than imports, aliases, requires. There are two ways we could attempt to collect variables:

1. Simply traverse the AST and collect all {atom, meta, atom} nodes.

2. Try to use the same approach as import, aliases, requires, but that would be tricky and I suspect it would also be brittle.

QUESTION: Which approach do you prefer? 1 definitely sounds simpler.

QUESTION: The biggest issue with collecting variables in both cases is deciding when a function starts. If we have this code:

some_var = 123

def bat do
  {<CURSOR>
end

some_var is not immediately visible inside bat. It is easy to detect those cases for def, defp and friends, but remember anyone can define their own "def"-like function, like Nx defines defn. So how to handle this? One option is to ignore the problem and show "some_var" anyway, for two reasons: they are not common, so the rate of false positive is low, and they can be accessed inside a function if we use unquote.

Module information

Something else we may want to complete is local function names and module attributes. Local function names is the trickier one, so let's focus on that.

All information so far (imports, aliases, variables) have to be defined before the cursor. Local functions are trickier because, even if local_function is defined after the cursor, we may still want to suggest it. How to gather this information?

1. One option is to only suggest local functions defined in a previously compiled version of this module. So if we have defmodule Foo do previously compiled and it had def local_function in it, we know it exists and we can suggest it.

2. Another option is to provide a heuristic. Similar to variables, we can look at the AST and collect all nodes {atom, meta, list}. If those nodes exist, it means they were either: previously imported, which we can check on the imports information, or they were locally defined. This has two additional complexities:

   • Given we want to traverse the whole AST, it is not enough to build a parser that builds the AST up until cursor. We need to always attempt to build the AST for the whole file (see Add string_to_quoted in Code.Fragment #11967)

   • Because of macros such as |>, we cannot look at {atom, meta, list} to fetch the arity because the macro will add one additional argument. So we need a heuristic to expand certain AST nodes in order to fetch the real arity (a simple heuristic is to expand all operators)

QUESTION: I believe the best solution in this case is actually a mixture of both 1 and 2. Use the heuristic to build as much information as possible and then refine the heuristic with information from a compiled version of the module (for example, the compiled version can have docs, types, metadata, etc). Do you agree? Anything to add?

Any additional thoughts?

[scohen]

José, great start here. I'm going to answer from the perspective of Lexical, which is slightly different than that of elixir-ls, mainly due to as-you-type compilation. Because of this, lexical can rely on modules being compiled correctly to complete things like function names (I don't think it's terrible to wait until a clean compile of the current file before we can see the name of a function, as this is only a matter of seconds, and the user will say "Wait, why can't I see the name of the function with the red squigglies under it? Oh right, it's not compiled. ")

To answer your questions:

Variables:

Which approach do you prefer?

I'd prefer #2, since it would respect elixir's scoping rules, which i don't think are respected presently in elixir_sense. I can understand why it'd be brittle though.

Something else we may want to complete is local function names and module attributes

Definitely, we currently complete both, thanks to elixir_sense, though I would like to move off of that library in the near future. Help there would be appreciated, though I vaguely remember module attributes being available as a beam attribute, yes?

some_var is not immediately visible inside bat

Is that legal elixir though? My perspective with the code above is that there would be no completions, as you haven't given any hint yet, but even if you had, I'm ok with not returning a completion.

Module Information

Do you agree:

Lexical is totally fine with relying on previously compiled modules for its completion of functions, submodules, etc. I know that elixir-ls would not be OK with this, as you have to save in order for it to compile your code, and there can be a lot of time that elapses between saves, and all the while, your current completions get more and more out of date.

Additional thoughts:

I would like to have blessed access to the tokenizer, or better yet, I would like to have access to an API that tells me where I am in code. Today, I've been playing around with Code.Fragment modules, and have been consistently confused by the results I get. I think it's because they're doing thinking for me that I don't expect them to do. For example, say I have the following context (the cursor is a pipe | in my examples):

calling cursor_context("%Foo.Bar") gives me {:struct, 'Foo.Bar'}. Ok, good enough, i suppose. Logically, for lexical, this tells me that I need to complete a struct with the prefix of Foo.Bar

calling cursor_context("%Foo.Bar{) gives me :expr. To me, this is confusing. :expr doesn't tell me anything about how I should complete this. Ideally, it'd tell me "Hey steve, you're inside of a struct's constructor arguments. Maybe you'd like to put a field name in there?". I've then thought "ok, maybe I need the surround context. Well, OK then, so I give it surround_context("%Foo.Bar{", {1, 10}), and I get :none. Backing this down to {1, 9}, which highlights the { gives me what I expect, that i'm in a struct.

Imagine I have the following:

%Foo.Bar.Baz{   |

My cursor_context is :expr and my surround_context(code, {1, 13}) is :none. Neither tell me anything useful and I think this makes them not suitable for my needs. I would like the surround_context to say something like {:struct_arguments, {:struct, {:alias, 'Foo.Bar.Baz'}}}. Overall, no matter where I am in code, I would like one of those two functions to tell me something about where I am lexically.

Something I've explored by using the tokenizer directly is creating backtracking expanding contexts (something I thought I could get with cursor_context). Consider the following:

alias Foo.Bar.{Baz, Quux|}

The cursor is inside of a module alias, inside of a multiple alias, which is itself inside of a call to Kernel.alias All of these contexts would be helpful to me, because the server will do different things based on the surrounding context. Here, it would be awesome for the server to not suggest function names because you're aliasing a module, whereas inside of a function, the server should suggest modules, functions and macros.

[josevalim]

Definitely, we currently complete both, thanks to elixir_sense, though I would like to move off of that library in the near future

I believe the long term goal is for elixir_sense to no longer exist, by moving part of its logic into Elixir, and the other half into the LS projects themselves. So we should be aligned here!

some_var is not immediately visible inside bat
Is that legal elixir though?

If you have this:

some_var = 123

def bat do
  {unquote(some_<CURSOR>
end

some_var would be valid completion and valid Elixir. Given implementing 100% accurate variable visibility is most likely impossible, I am currently more inclined to list some_var as a valid completion, regardless if you are inside unquote or not. From a glance, it will be the simplest approach to maintain and implement too.

"Hey steve, you're inside of a struct's constructor arguments. Maybe you'd like to put a field name in there?"

For this use case, we use container_cursor_to_quoted. It returns the AST up to the current cursor, which you can traverse up to find more information about its enclosing. Here is how we use it in autocomplete: https://github.com/elixir-lang/elixir/blob/main/lib/iex/lib/iex/autocomplete.ex#L323

To give more context: the goal of cursor_context is to be super fast and parse only the current line, so we don't traverse the AST. However, in order to say we are inside a struct, we need to traverse the AST (because the struct could have been opened in a previous line), then you need to use AST building functions.

surround_context is for mouse-over highlighting. The word "surround" in this case refers to the limits of the code being highlighted. Perhaps not the best of names. We thought about calling it highlight_context or mouse_over_context but we didn't want to necessarily imply how it would be used. But I see how it is confusing to you.

[scohen]

defmodule Test do
  some_var = 3

  def foo do
    some_var + 1
  end
end

Compiling 1 file (.ex)
warning: variable "some_var" is unused (if the variable is not meant to be used, prefix it with an underscore)
  lib/lexical/server/code_intelligence/completion/test.ex:2: Test

warning: variable "some_var" does not exist and is being expanded to "some_var()", please use parentheses to remove the ambiguity or change the variable name
  lib/lexical/server/code_intelligence/completion/test.ex:5: Test.foo/0


== Compilation error in file lib/lexical/server/code_intelligence/completion/test.ex ==
** (CompileError) lib/lexical/server/code_intelligence/completion/test.ex:5: undefined function some_var/0 (expected Test to define such a function or for it to be imported, but none are available)

I know who I'm speaking to here ;), but what am I missing?

For this use case, we use container_cursor_to_quoted

Ah, I see. I read the to in that function name as a conversion, not a limit (the name uses "to" as in "from the start, to the cursor position, not as in "convert the cursor position to quoted"). I'm still a little confused as to what the word "container" represents here. I still find it confusing and inconsistent that some of the APIs in Fragment return AST, while others return a higher-level construct. As someone developing a language server, the higher-level construct is more appealing to me than parsing AST all the time, but i might just need to bite that bullet.

As a refinement, it would be easier for me, personally, to be able to pass in a position to each of the functions rather than assuming the end of the document is the cursor position. The most common behavior of a language server is someone editing a document somewhere in the middle rather than appending to the end. Right now, it's very easy for me to have a position and a document's text rather than the substring of the document from the beginning to where the cursor is inserting text. If this isn't in the cards, not all is lost, I can easily make my document abstraction return what's needed, it'd just be so much easier for me to do:

document 
|> Document.to_string()
|> Code.Fragment.container_cursor_to_quoted(cursor_position: {env.position.line, env.position.character})

but I could easily make this happen too:

document
|> Document.fragment(end: env.position)
|> Code.Fragment.container_cursor_to_quoted()

I'll give the above things a shot and see if I can use this newfound knowledge of Code.Fragment to replace my usage of the tokenizer. I think i can make things a lot more clear by using Code.Fragment.container_to_quoted and the Sourceror library.

[josevalim]

I know who I'm speaking to here ;), but what am I missing?

As mentioned above, you can unquote it:

defmodule Test do
  some_var = 3

  def foo do
    unquote(some_var) + 1
  end
end

As someone developing a language server, the higher-level construct is more appealing to me than parsing AST all the time, but i might just need to bite that bullet.

I completely understand that but we have been building from the bottom-up. The immediate goal is to provide a bunch of low-level functions so you no longer need to rely on private APIs. The existing functions solve specific concerns instead of the whole thing. You want a Ferrari, but first we have to build the wheels, the engine... :)

[josevalim]

I'm still a little confused as to what the word "container" represents here.

Container means we return information about the parent container of the current node where the cursor is rather than the cursor itself.

I still find it confusing and inconsistent that some of the APIs in Fragment return AST, while others return a higher-level construct.

That's natural. The Code module is a collection of functions too, some AST related, some low-level and some high-level. PRs to improve the docs are always appreciated.

[scohen]

You want a Ferrari, but first we have to build the wheels, the engine... :)

Well yes, it's just surprising to see an exhaust, half a frame and seventeen cylinders over in the corner ;). Right now, I'd take a gas powered pogo stick.

Container means we return information about the parent (i.e. the container) of the current node where the cursor is rather than the cursor itself.

Yes, but I'm going to quibble here (and naming is subjective), since most nodes are containers. This feels more like you're building the AST until you get to the cursor, which is then marked. This isn't the biggest deal in the world, and can be improved with documentation.

PRs to improve the docs are always appreciated.

Yep, this module definitely needs some help there. I'll use my ignorance of it to improve the docs, though it's really hard when you don't know the intention of the functions. I'm still coming to grips with them, and how to use them. That said, I'll give it a shot.

Just as I was going to submit this, I stumbled upon the following.

I thought that contianer_context_to_quoted would help me determine aliases, but for this is again confusing me.

"alias MyThing.Other" |> Code.Fragment.container_cursor_to_quoted
{:ok, {:__cursor__, [line: 1], []}}

Where's the rest? I was expecting to see the alias call, the module name, but I only have the cursor.

My goal is to determine if I'm inside of an alias call, in its many forms. What is the algorithm I should use to do that?

[josevalim]

Well yes, it's just surprising to see an exhaust, half a frame and seventeen cylinders over in the corner ;)

Or alternatively you could have nothing, not even a half frame, and only use private APIs which may break on every new Elixir release. :)

Anyway, my main point was not the metaphor. But to acknowledge that, although those functions are low-level, they do have their uses and they have been helpful to IEx, Livebook, and parts of Elixir LS. Now let's continue moving forward.

Where's the rest? I was expecting to see the alias call, the module name, but I only have the cursor.

There is no container in this case. As the docs explain: “A container is any Elixir expression starting with (, {, and [. This includes function calls, tuples, lists, maps, and so on”. But I would need to understand a bit more what you want to achieve. Why do you want to know if you are inside an alias call?

[scohen]

Or alternatively you could have nothing

Jose, I'm being silly here, that was meant to amuse, not insult :)

Why do you want to know if you are inside an alias call?

Because I would like to determine which completions are relevant to the user. If I'm inside of an alias call, I will not suggest functions, for example. This really improves the user experience quite a bit. Lexical does this now, but it uses the tokenizer and backtracks, which isn't the easiest thing to understand and code.

[josevalim]

Because I would like to determine which completions are relevant to the user.

Right. You don't need to know if you are in an alias for this, the fact the current token is an alias is enough:

iex(1)> "alias MyThing.Other" |> Code.Fragment.cursor_context
{:alias, ~c"MyThing.Other"}

Or this tells you are at the beginning of an alias call:

iex(1)> "alias " |> Code.Fragment.cursor_context
{:local_call, ~c"alias"}

Check IEx.Autocomplete for more examples. The general goal for autocompletion is: use cursor_context to find what you need to complete. If ambiguous, use container_cursor_to_quoted to find more surrounding information. Exactly how you complete it we can't help right now.

[scohen]

In general, I'm trying to build language server that's easy for people to contribute to, and to that end, I've made some abstractions around completion, visible in the Completion.Env module. It currently has a bunch of predicate functions about the current context, called in_context?. You can see the implementation for :alias here. Alias is by far, the most complex version of this function, and i'd be great if I could get something like container_cursor_to_quoted that didn't care so much about containers, but was more general.

I'll also point out that including parenthesis makes the definition of container fairly arbitrary in a language like elixir, as they can be left out with a formatter configuration, which would mean that it's possible that a container differs from project to project.

[scohen]

The general goal for autocompletion is: use cursor_context to find what you need to complete

I don't really like that though. There are cases where it's telling me alias, but I don't want to complete just aliases.

I don't like or use the pattern below, but I've seen it a bunch and the above logic will fail.

alias :et|

with the inevitable goal of

alias :ets, as: Ets

I get {:unquoted_atom, 'module'} which is something that can appear in a lot of places. I really see having contextual information as being incredibly helpful to the language server. Building this logic into a core function means someone else gets to decide what the language server's user experience is.

Currently, iex will show me functions if I type alias Module.| I don't want lexical to do that. I want it to provide relevant help given the overall context of the completion.

[josevalim]

Currently, iex will show me functions if I type alias Module.| I don't want lexical to do that. I want it to provide relevant help given the overall context of the completion.

Ah, that was the example I was missing. Let me think a bit more about this. :)

[lukaszsamson]

Where is where the mouse cursor is. In order to provide completion, we need three things

Completions are only one of the 3 main aspects. The second one is ability to identify what the symbol under cursor is given the context. Is this a variable or attribute? Can we statically evaluate it? Third one is identifying the context itself. Are we inside a function body/header/list/map/module/type.

1. A parser that is robust to syntax failures

I know this is tricky to achieve, especially with elixir being lisp like. It would have to be smarter than container_cursor_to_quited which as I understand it blindly inserts closing tokens. It would need to take into account indentation and common formatting style. elixir_sense tries to do that with regex but the code is nasty and only works in certain cases.

2. Build a local context with imports, variables, aliases, local functions, etc

I'd add attributes, types, structs, records, sigils. elixir_sense extract that information from AST only but the code is pretty complex and tends to break every release. Having a stable interface would be nice. It has another shortcoming - it only understands a handful of builtin macros as it's not doing expansion. Being able to leverage complier here would also increase accuracy and make understanding of ecto/phoenix/my_fancy_one_use_dsl work out of the box in more cases

3. Understand which kind of completion we should provide (alias? function call? variable name?)

Context or scope is important

We only provide step 3 at the moment via cursor_context

Most elixirLS completions already uses it and I plan to migrate some more after a bump to min 1.14. It works pretty well besides occasional :expr return. Sometimes it's possible to statically evaluate the expression.

import, aliases, requires

Like above elixir_sense has its own engine extracting those from AST

Building the AST can be done with container_cursor_to_quoted. We don't have at the moment a safe way to expand its nodes

elixir_sense can expand use macro but this requires the module to be compiled

Variables

Sure, vars are tricky but I'd say aliases come close. Simply collecting references is trivial doesn't help much. Actually understanding where variable is defined and where referenced is much better and elixir_sense does that. It allows for navigation to variable definition, finding usages, better contextual completions. elixir_sense also tries to infer the type of the variable (only a handful of types is supported). I envision it should be able to access type info when types land in elixir.

The simple approach may be enough for IEx but it's definitely not sufficient for IDEs.

The biggest issue with collecting variables in both cases is deciding when a function starts. If we have this code

No problem with false positives - they will be filtered out by the user or will trigger compile diagnostics later. It's false negatives that are more frustrating.

Module information

elixir_sense extracts local functions, typespecs and structs from AST.

even if local_function is defined after the cursor, we may still want to suggest it

Yep, global dictionary for funs/types/structs/modules vs code position based scope for alias/import/require/vars/attributes. I know there are a few exceptions here (e.g. private macros are only available after the definition in module body)

One option is to only suggest local functions defined in a previously compiled version of this module

That was the approach in original alchemist server (based on IEx). The main problem was it only was aware of public funs. I integrated AST based completions in elixir_sense. I plan to integrate tracer info here but it's not trivial when there are 2 sources of truth.

So we need a heuristic to expand certain AST nodes in order to fetch the real arity

Arity is tricky. Macros are one thing, |> is the other (in elixir_sense pipes are transformed to non piped form). Multiple function definitions and default args are fun as well.

I believe the best solution in this case is actually a mixture of both 1 and 2. Use the heuristic to build as much information as possible and then refine the heuristic with information from a compiled version of the module

Sounds good but it might be difficult

[lukaszsamson]

Regarding alias expressions there are irritating cases where Code.Fragment.cursor_context is not helpful

iex(6)> "alias MyThing.Other.{" |> Code.Fragment.cursor_context
:expr
iex(8)> "alias MyThing.Other.{A, " |> Code.Fragment.cursor_context
:expr

[scohen]

@lukaszsamson Yep, that's exactly the same thing you get if you're inside of a struct reference. The nested context matters to us.

[scohen]

I've been playing around with the Sourceror library, and what would be cool to me would be a function like: Code.Fragment.zipper_at_cursor(source, {line, character}), which would return a Sourceror.Zipper at the cursor position. if I had that, determining if the cursor is in an alias is just a couple function calls.
...but that's a pretty big change.

Really want to second everything Lukasz said three comments up. He has a lot better handle on the domain than I do, but everything he said tracks.

[josevalim]

I'd add attributes, types, structs, records, sigils. elixir_sense extract that information from AST only but the code is pretty complex and tends to break every release. Having a stable interface would be nice. It has another shortcoming - it only understands a handful of builtin macros as it's not doing expansion.

So if I get it right, in order to understand structs, you parse the AST explicitly looking for defstruct? Which means if there is a library such as typedstruct or Ecto, you may not see its struct definition until the module is compiled?

Sure, vars are tricky but I'd say aliases come close. Simply collecting references is trivial doesn't help much. Actually understanding where variable is defined and where referenced is much better and elixir_sense does that.

Can you expand on how ElixirSense does it? AST traversal? Do you expand macros as you do it?

Multiple function definitions and default args are fun as well.

Good call on default args.

Regarding alias expressions there are irritating cases where Code.Fragment.cursor_context is not helpful

This can be solved with container_cursor_to_quoted (exactly how we solve it for structs/maps). But I am thinking how to improve it given @scohen's earlier example. The optional parens really trips things up in his case.

[lukaszsamson]

So if I get it right, in order to understand structs, you parse the AST explicitly looking for defstruct? Which means if there is a library such as typedstruct or Ecto, you may not see its struct definition until the module is compiled?

Exactly

Can you expand on how ElixirSense does it? AST traversal? Do you expand macros as you do it?

No macro expansion here, only AST traversal with scoping rules. The first occurrence is treated as variable definition, all later as usages. elixir_sense also traverses =, ->, <- and to some extent for and with to see what is on the other side and infer type

[josevalim]

Ah, that was the example I was missing. Let me think a bit more about this. :)

This is now supported on Elixir main branch. A combination of container_cursor_to_quoted and Macro.path will tell you where you are in a completion (inside the first argument of alias, inside the :as, or inside a tuple in the first argument). Code snippets:

iex(4)> demo = fn arg ->  arg |> Code.Fragment.container_cursor_to_quoted |> elem(1) |> Macro.path(&match?({:__cursor__, _, []}, &1)) end
#Function<42.125776118/1 in :erl_eval.expr/6>
iex(5)> demo.("alias ")
[
  {:__cursor__, [line: 1], []},
  {:alias, [line: 1], [{:__cursor__, [line: 1], []}]}
]
iex(6)> demo.("alias Foo.Bar.")
[
  {:__cursor__, [line: 1], []},
  {:alias, [line: 1], [{:__cursor__, [line: 1], []}]}
]
iex(7)> demo.("alias Foo.Bar.Bar, as: DAS")
[
  {:__cursor__, [line: 1], []},
  {:as, {:__cursor__, [line: 1], []}},
  [as: {:__cursor__, [line: 1], []}],
  {:alias, [line: 1],
   [
     {:__aliases__, [line: 1], [:Foo, :Bar, :Bar]},
     [as: {:__cursor__, [line: 1], []}]
   ]}
]
iex(8)> demo.("alias Foo.Bar.{Baz,")
[
  {:__cursor__, [line: 1], []},
  {{:., [line: 1], [{:__aliases__, [line: 1], [:Foo, :Bar]}, :{}]}, [line: 1],
   [{:__aliases__, [line: 1], [:Baz]}, {:__cursor__, [line: 1], []}]},
  {:alias, [line: 1],
   [
     {{:., [line: 1], [{:__aliases__, [line: 1], [:Foo, :Bar]}, :{}]},
      [line: 1],
      [{:__aliases__, [line: 1], [:Baz]}, {:__cursor__, [line: 1], []}]}
   ]}
]
iex(9)> demo.("alias Foo.Bar.{")
[
  {:__cursor__, [line: 1], []},
  {{:., [line: 1], [{:__aliases__, [line: 1], [:Foo, :Bar]}, :{}]}, [line: 1],
   [{:__cursor__, [line: 1], []}]},
  {:alias, [line: 1],
   [
     {{:., [line: 1], [{:__aliases__, [line: 1], [:Foo, :Bar]}, :{}]},
      [line: 1], [{:__cursor__, [line: 1], []}]}
   ]}
]

You can match on those code snippets to answer your questions. You can even provide this as a general framework I think where you tell users if they are on the first argument, second, inside a keyword, etc.

Currently, iex will show me functions if I type alias Module.| I don't want lexical to do that. I want it to provide relevant help given the overall context of the completion.

I plan to implement this for import, alias, and require in IEx tomorrow as an example.

---

So in a nutshell, for code completion, we need:

• where in the token we are completing (answered by cursor_context) (I was used to say this is the "what" but I like this better)
• where in the ast we are completing (answered by container_cursor_to_quoted)
• how we are completing (that's what this issue is about)

---

@lukaszsamson now that container_cursor_to_quoted supports operators, we may need to strip them in some cases. Here is the change I had to do to how we detect if we are in a bitstring modifier: ca0d6ad#diff-9e9de7d847547ae049e1297f35e4f7cd0f7d99d6f4cbcf8fa4b90c7c532ee035R385 - this change should be backwards compatible (i.e. if you do this change, code in 1.14 still works)

[josevalim]

Here is how aliases work: b59907e - For IEx, we only need to look at the container when there is a dot (which is ambiguous) and when nothing was written.

[Sleepful]

Great conversation! I only have a small note to add on all this:

There might be a slight difference in alignment between the goals of an LSP and the goals of IEX & Livebook.

LSP focuses heavily on navigation, in contrast IEX & Livebook care more about auto_completion.

These two are very similar but not equal:

• auto_completion does not require a high degree of accuracy, auto_completion works fine with heuristics and approximate results, the user easily filters out the incorrect information.
• navigation on the other hand requires high accuracy, incorrect results in navigation create misleading scenarios for the user.