>
> When I C-x C-f and start typing a TRAMP session to an SSH host, for 
> instance `/ssh:`, then hit <tab>, I see a list of known hosts proposed 
> for completion. This is the expected behavior. If I then enable 
> fido-mode and do the same, instead of having known hosts proposed when 
> hitting <tab>, I only get a list of TRAMP methods for completion, eg. 
> `ssh:`, `sshx:` and `sshfs:`. I would expect to also have known hosts on 
> fido-mode.
>
> To reproduce, open emacs -Q; then:
> C-x C-f /ssh: <tab>
> (This produces the expected behavior of proposing known hosts)
> M-x fido-mode
> C-x C-f /ssh: <tab>
> (Now, only TRAMP methods are proposed for completion)
>

There are two problems here:

1. fido-mode sets completion-styles to 'flex', and as indicated in the 
docstring of completion-styles "Tramp host name completion (e.g., 
"/ssh:ho<TAB>") currently doesn't work if this list doesn't contain at 
least one of `basic', `emacs22' or `emacs21'."  The workaround is to add 
this to your init file:

(advice-add #'icomplete--fido-mode-setup
 	    :after (lambda () (setq completion-styles '(flex basic))))

You could also ask for that change to be made in core.

2. Doing that is not enough, because of an incompatibility between Tramp 
and the 'flex' and 'substring' mechanisms.  The Tramp manual has a 
footnote which mentions that incompatibility: "Some completion styles, 
like `substring' or `flex', require to type at least one character after 
the trailing `:'."  A one-line patch to fix it was proposed, but rejected, 
a year and a half ago.  It is attached to this email, and you can use it 
locally.  As I said in the bug thread in which that patch was proposed: "I 
expect other bug reports from confused users".