774795 - Implement navigator.spell

Status: RESOLVED WONTFIX

(Core :: DOM: Device Interfaces, defect)

Description

[Gregor Wagner [:gwagner]]

The benchmark results from bug 773366 suggest to use a native implementation for spell-check / predictive text. 

We want an async API with basically 2 functions:
 - isValidWord(word) checks if the word is in the DB.
 - getSuggestions(word, optional proximityInfo) returns an array of words with ranking that are similar to word. The proximity info which contains the touch-location is optional.

Jonas, Mounir: is DOMRequest the right way for async?

We also need a way to load dictionaries.

Comment 1

[Mounir Lamouri (:mounir)]

(In reply to Gregor Wagner [:gwagner] from comment #0)
> Jonas, Mounir: is DOMRequest the right way for async?

Yes.

Comment 2

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

This makes me sad but gotta do what you gotta do.

(In reply to Gregor Wagner [:gwagner] from comment #0)
>
> We also need a way to load dictionaries.

For a v1 we could key off of navigator.language or whatever that is.  (Or the setting, I forget what we prefer now.)

Comment 3

[Andreas Gal :gal]

We should create a C++ service with the engine and then a thin JS DOM implementation. Can you specify the proximityInfo.

Comment 4

[Andreas Gal :gal]

Please add a sync and async API to the service so we can use this to bypass and replace hunspell. We probably don't want both active at the same time.

Comment 5

[Andreas Gal :gal]

How are we doing here?

Comment 6

[Christoph Kerschbaumer [:ckerschb]]

We do have a basic implementation where we can call from JS into native code and return suggestions back to JS. Some values are still hardcoded. Gregory and I will go back to the whiteboard and will clarify when the dictionary is loaded and also define the exact interface.

Comment 7

[Andreas Gal :gal]

Please post the IDL asap. Thanks!

Comment 8

[Christoph Kerschbaumer [:ckerschb]]

Attachment: idl draft

Comment 9

[Philipp von Weitershausen [:philikon]]

Comment on attachment 644185 [details] [diff] [review]
idl draft

Nit: use `long` instead of `PRUint32` in IDLs.

Comment 10

[Andreas Gal :gal]

Comment on attachment 644185 [details] [diff] [review]
idl draft

Review of attachment 644185 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/predictivetext/nsIDOMPredictiveTextManager.idl
@@ +17,5 @@
> +  attribute PRUint32    gridWidth;
> +  attribute PRUint32    gridHeight;
> +  attribute jsval       proximityCharsArray;     // Uint32[]
> +  attribute PRUint32    keyCount;
> +  attribute jsval       keyXCoordinateArray;     // Uint32[]

These many arrays look wonky. Should we have an array of another struct here? Assuming all these arrays are the same length.

Comment 11

[Christoph Kerschbaumer [:ckerschb]]

Attachment: modified idl file

Comment 12

[Andreas Gal :gal]

Comment on attachment 644972 [details] [diff] [review]
modified idl file

Review of attachment 644972 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/predictivetext/nsIDOMPredictiveTextManager.idl
@@ +16,5 @@
> +
> +[scriptable, uuid(51348de0-d4ea-11e1-9b23-0800200c9a66)]
> +interface nsIDOMDisplayInfo : nsISupports
> +{
> +  attribute unsigned long    maxProximityCharsSize;

what exactly is this?

@@ +17,5 @@
> +[scriptable, uuid(51348de0-d4ea-11e1-9b23-0800200c9a66)]
> +interface nsIDOMDisplayInfo : nsISupports
> +{
> +  attribute unsigned long    maxProximityCharsSize;
> +  attribute unsigned long    displayWidth;

this is available internally right? we don't need an api here

@@ +28,5 @@
> +[scriptable, uuid(a641a020-d4ea-11e1-9b23-0800200c9a66)]
> +interface nsIDOMKeyInfo : nsISupports
> +{
> +  attribute unsigned long    keyCount;
> +  attribute jsval            keyXCoordinateArray;     // Uint32[]

shouldn't this be an array of key info structs?

Comment 13

[Gregor Wagner [:gwagner]]

Christoph is adding comments to all fields.

(In reply to Andreas Gal :gal from comment #12)
> Comment on attachment 644972 [details] [diff] [review]
> modified idl file
> 
> Review of attachment 644972 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: dom/predictivetext/nsIDOMPredictiveTextManager.idl
> @@ +16,5 @@
> > +
> > +[scriptable, uuid(51348de0-d4ea-11e1-9b23-0800200c9a66)]
> > +interface nsIDOMDisplayInfo : nsISupports
> > +{
> > +  attribute unsigned long    maxProximityCharsSize;
> 
> what exactly is this?

The name is not perfect. This field is needed to set the maximum number of alternative keys you can provide for a given character. 
The keyboard is then presented as an array of keys with 'maxProximityCharsSize' holes for proximity chars. For example for the keys 'a', 'b' you can get
'a', 's', 'q', 'w', 'z', empty, empty, 'b', 'v', ...
with maxProximityCharsSize:6 

Most of the information should be pretty stable. We should figure out what parts belong together and don't have to be created all the time if we don't change the orientation for example. 

I think the array representation for keyXCoordinateArray is an optimization because we have to iterate over them but we should check if it makes any difference if we create a keyInfoStruct that holds the x,y value and maybe other info.

Rudy might have some comments on how easy it is to use this API.

Comment 14

[Andreas Gal :gal]

Please make the API as simple and small as possible. I am sure Rudy can work with any iteration of this.

Comment 15

[Christoph Kerschbaumer [:ckerschb]]

Attachment: added description for every attribute in the idl

What I've seen Rudy already has an almost complete model of the Android's Java part of the code.

Comment 16

[Christoph Kerschbaumer [:ckerschb]]

we just got back from the whiteboard and changed the interface to proposed structs following andreas's suggestion!

Comment 17

[Christoph Kerschbaumer [:ckerschb]]

Attachment: updated arrays keyInfos and bundled them together in a struct

Comment 18

[Christoph Kerschbaumer [:ckerschb]]

Attachment: diff instead of idl file

Comment 19

[Andreas Gal :gal]

can you post the new idl?

Comment 20

[Christoph Kerschbaumer [:ckerschb]]

see attachment

Comment 21

[Andreas Gal :gal]

Comment on attachment 645065 [details] [diff] [review]
diff instead of idl file

Review of attachment 645065 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/predictivetext/nsIDOMPredictiveTextManager.idl
@@ +11,5 @@
> +interface nsIDOMPredictiveTextResult : nsISupports
> +{
> +  /*
> +   * uint32[] outWords holds the returned words of getSuggestions
> +   * words are delimited either bei maxWordLength or 0

aren't words strings?

@@ +40,5 @@
> +  readonly attribute unsigned long    maxProximityCharsSize;
> +  
> +
> +   // width of the display
> +  readonly attribute unsigned long    displayWidth;

we know displayWidth in the code, why ask it to be passed in here?

@@ +48,5 @@
> +  readonly attribute unsigned long    displayHeight;
> +  
> +
> +   // width of the grid
> +  readonly attribute unsigned long    gridWidth;

whats the grid?

@@ +65,5 @@
> +[scriptable, uuid(a641a020-d4ea-11e1-9b23-0800200c9a66)]
> +interface nsIDOMKeyInfo : nsISupports
> +{
> +   // x coordinate for key
> +  readonly attribute unsigned long    keyXCoordinate;

why keyXCoordinate? why not x, y, width, height, keyCode, sweetSpot = { x, y, radius }

@@ +96,5 @@
> +  attribute nsIDOMDisplayInfo         displayInfo;
> +
> +  // number of keys of the current keyboard layout
> +  // length of keyInfos[]
> +  attribute unsigned long             keyCount;

why do we need count? the array below should do

Comment 22

[Christoph Kerschbaumer [:ckerschb]]

Attachment: updated idl

Comment 23

[Christoph Kerschbaumer [:ckerschb]]

> > +   * uint32[] outWords holds the returned words of getSuggestions
> > +   * words are delimited either bei maxWordLength or 0
> 
> aren't words strings?
yes, I updated that.


> > +   // width of the display
> > +  readonly attribute unsigned long    displayWidth;
> 
> we know displayWidth in the code, why ask it to be passed in here?

displayWidth is actually keyboardWidth, wrong naming, I updated that.


> > +   // width of the grid
> > +  readonly attribute unsigned long    gridWidth;
> 
> whats the grid?
both, keyboarWidth, and gridWidth are used for Android's internals. I am trying to follow their interface.


> > +   // x coordinate for key
> > +  readonly attribute unsigned long    keyXCoordinate;
> 
> why keyXCoordinate? why not x, y, width, height, keyCode, sweetSpot = { x,
> y, radius }
updated.

> > +  // number of keys of the current keyboard layout
> > +  // length of keyInfos[]
> > +  attribute unsigned long             keyCount;
> 
> why do we need count? the array below should do

yes correct, I modified that.

Comment 24

[Christoph Kerschbaumer [:ckerschb]]

Attachment: interface for predictive text

Comment 25

[Andreas Gal :gal]

Comment on attachment 645395 [details] [diff] [review]
interface for predictive text

Review of attachment 645395 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/predictivetext/nsIDOMPredictiveTextManager.idl
@@ +28,5 @@
> +{
> +  [implicit_jscontext]
> +  nsIDOMDOMRequest getSuggestions(in nsIDOMProximityInfo proximityInfo,
> +                                  in unsigned long xCoordinatesArrayLength,
> +                                  [array, size_is(xCoordinatesArrayLength)] in PRUint32 xCoordinatesArray,

I think you want a jsval here where you pass { proximity-info-object}, [{x, y}, {x, y}, ...], input, flags). Looks good otherwise. Just beat XPCOM into shape to make it match the JS API you want. Going via jsval is probably easier.

Comment 26

[Christoph Kerschbaumer [:ckerschb]]

Attachment: idl file using dictionaries

Comment 27

[Boris Zbarsky [:bzbarsky]]

I have to ask:  Is there a reason we're using XPIDL here and not WebIDL?

Comment 28

[Boris Zbarsky [:bzbarsky]]

> Going via jsval is probably easier.

Whenever someone says that, they're probably wrong.

Comment 29

[Gregor Wagner [:gwagner]]

(In reply to Boris Zbarsky (:bz) from comment #28)
> > Going via jsval is probably easier.
> 
> Whenever someone says that, they're probably wrong.

Our problem is that we have to create this giant ProximityInfo object in JS and pass it somehow into the c++ implementation. Many fields in this structs are optional and the whole thing is also pretty stable but it can change. We don't want to create it for every getSuggestion call but we have to pass it somehow to the implementation. Using a separate set function is also not a good idea.

We tried with constructors but that seems a big overhead.
mrbkap had the idea with dictionaries. So now the question is whether dictionaries are the right way to go and if we use it the right way. Is there a similar example in the code where we have to create a big struct in JS and pass it into c++ land?

Comment 30

[Boris Zbarsky [:bzbarsky]]

In general, dictionaries are supposed to address the use case you describe.

What issues did you run into with constructors?

Also, see comment 27.

Comment 31

[Gregor Wagner [:gwagner]]

(In reply to Boris Zbarsky (:bz) from comment #30)
> In general, dictionaries are supposed to address the use case you describe.
> 
> What issues did you run into with constructors?

We didn't want to add a global Constructor.
Our ProximityInfo is basically a combination of substructs. 
The createInstance would work of course but the fact that we can't use it like a constructor and we always have to call an init function with many optional arguments felt wired and annoying.
> 
> Also, see comment 27.

Mostly consistency with other webapis and I never used WebIDL before, but no particular reason. Would it be easier?

Comment 32

[Boris Zbarsky [:bzbarsky]]

> We didn't want to add a global Constructor.

I'm not sure I follow... What code pattern were you seeing?

As for WebIDL, we're working on converting everything web-facing to using that, since all we specs are written in terms of WebIDL.  So the work will have to be done at some point.  The only question is whether it should be done now or later.  Now is preferable, to avoid doing the work twice, unless there's a really good reason to not use WebIDL here.

Comment 33

[Christoph Kerschbaumer [:ckerschb]]

Attachment: idl

Comment 34

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Is there really no way we can build this into the keyboard app itself? It seems highly unlikely that any app, or even any other keyboard app, would want to use this API.

Also, why does the API expose so many parameters? Why would an app want to tweak all those parameters? Is the keyboard app going to be passing in different values for these parameters?

Comment 35

[Gregor Wagner [:gwagner]]

(In reply to Jonas Sicking (:sicking) from comment #34)
> Is there really no way we can build this into the keyboard app itself? It
> seems highly unlikely that any app, or even any other keyboard app, would
> want to use this API.

We need all this information in the backend so we have to fill it in the keyboard app and pass it to the implementation.
This also contains isValidWord and this might be used by several applications.
I don't think we should split the getSuggestions and isValidWord since they share one dictionary.

> 
> Also, why does the API expose so many parameters? Why would an app want to
> tweak all those parameters? Is the keyboard app going to be passing in
> different values for these parameters?

yes :( if the orientation changes for example you will have different parameters. Switching languages also influences the keyboard layout.

Comment 36

[Christoph Kerschbaumer [:ckerschb]]

Attachment: alternative idl

Update: As of today, we can perform async calls to 'getSuggestions' and 'isValidWord'. On Tuesday, Jonas, Gregor and I are going to meet to finalize the IDL.

Comment 37

[Christoph Kerschbaumer [:ckerschb]]

Attachment: first implementation for predictive text

Comment 38

[Christoph Kerschbaumer [:ckerschb]]

Attachment: first implementation for predictive text

(100,000 word dict, 615,554 bytes)

RUN   CUR            JS         NATIVE
  1   w              1,078 ms   46 ms 
  2   wa             1,473 ms   32 ms
  3   was              893 ms  357 ms
  4   wash             353 ms   47 ms
  5   washi            290 ms   55 ms
  6   washin           222 ms   33 ms
  7   washing          201 ms   43 ms
  8   washingt         197 ms   28 ms
  9   washingto        207 ms   21 ms
 10   washington       211 ms   32 ms

Comment 39

[Christoph Kerschbaumer [:ckerschb]]

Attachment: finalized idl file

Comment 40

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 650778 [details] [diff] [review]
finalized idl file

Review of attachment 650778 [details] [diff] [review]:
-----------------------------------------------------------------

There's a bunch of things that I would do differently if we were designing a predictive text API from scratch, but since this is intended to be a bridge to the Android API we need to deal with the shortcomings of that API.

If we ever end up writing our own implementation, I think we should do a few things differently, but we can deal with that if that time comes.

For now I think this is the right thing to do, to keep it simple and map pretty closely to the Android backend. However we should figure out the details of the various parameters, like the grid ones, and make sure everything is documented.

Comment 41

[Christoph Kerschbaumer [:ckerschb]]

Attachment: revised implementation

Comment 42

[Christoph Kerschbaumer [:ckerschb]]

Attachment: predictive text native implementation

Comment 43

[Andreas Gal :gal]

I landed a pure JS implementation of a predictive text engine. Please text against your implementation w.r.t. quality and speed. So far my impression is that the JS code is fast enough and good enough. If you disagree, please request block basecamp for this. Otherwise we will WFM this bug.

Comment 44

[Andreas Gal :gal]

Gaia pull request:

https://github.com/mozilla-b2g/gaia/pull/3836

A couple evaluation criteria:
- I need about 1.6mb for the dictionary (English US). Measure the memory consumption you add as well.
- Lookup times are around 2-4ms on desktop and usually < 25ms on mobile. Again, compare to this code.

Comment 45

[Christoph Kerschbaumer [:ckerschb]]

I performed a detailed comparison between predictJS and the current native implementation:

1) SPEED:

   DESKTOP:
     run  cur            predict.js     native
      1   w              5 ms           2 ms 
      2   wa             2 ms           6 ms
      3   was            1 ms           7 ms
      4   wash           1 ms           1 ms
      5   washi          1 ms           1 ms
      6   washin         1 ms           0 ms
      7   washing        1 ms           1 ms
      8   washingt       1 ms           1 ms
      9   washingto      1 ms           0 ms
     10   washington     1 ms           0 ms

   OTORO:
     run  cur            predict.js     native
      1   w              48 ms            9 ms 
      2   wa             37 ms          239 ms
      3   was            30 ms           31 ms
      4   wash           22 ms           23 ms
      5   washi          21 ms           21 ms
      6   washin         64 ms           21 ms
      7   washing        48 ms           37 ms
      8   washingt       48 ms           21 ms
      9   washingto      71 ms           20 ms
     10   washington     47 ms           20 ms

2) SIZE:
   
   DICTIONARY            predict.js     native
   en_wordlict.dict      ~1.7 MB        ~1.1 MB


3) QUALITY:
Android's version seems to return slightly more sophisticated results, e.g. 

a) Abbreviations: For 'HP' predict.js returns [HP, JP, VP, HPV, ...] whereas the native implementation suggests 'Hewlett-Packard' or 'HyperCard'. (Note: For this comparison I checked all possible candidates predict.js uses internally).

b) Typos: For 'tshi' predict.js returns [Thai, tusk, Theo, ...] whereas the native version suggests 'this'.

c) Word-completions: For 'corp' returns [crop, grip, CTOL, group, ...] whereas the native version suggests 'corporate', 'corporation'.

d) Typos and word-completion: For'higs' predict.js returns [gigs, jigs, hugs, hogs, hits, tugs, togs, ...] whereas the native version suggests 'highest'.

e) Number of returned results: In certain cases predict.js returns only 3 or 4 suggestions.
For 'pub' it returns [pub, PKB, pun, pubs] whereas the native version always returns as many suggestions as provided in the maxWords variable. In this case [public, published, publishing, Public, publisher, publicly, ...]

Comment 46

[Andreas Gal :gal]

I fixed b) in https://github.com/andreasgal/gaia/compare/predict-transpose (needs to be reviewed + merged).

Comment 47

[Christoph Kerschbaumer [:ckerschb]]

This bug is outdated, because we use a different approach for our predictive text!
Check: https://bugzilla.mozilla.org/show_bug.cgi?id=838227

I guess we can close this one!