Bug 29178 – Geolocation should be refactored to use a single map to store all notifiers

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Steve Block]

Currently the Geolocation object stores its notifier objects in two data structures. A set for the one-shot notifiers, and a map (from watch ID to notifier) for the watcher notifiers.

The logic could be simplified if a single data structure were used. We could assign IDs to one-shot notifiers as well as watcher notifiers, and store both in a single maps.

This refactoring would also help solve the problem of looking up watchers by ID, encountered in Bug 27944.

[Steve Block]

Created attachment 40361 [details]
Patch 1 for bug 29178

[Eric Seidel (no email)]

Who else has worked on Geolocation in WebKit and should be thus CC'd on this bug?  I'm really not a geolocation expert, but I can take a look at this.

[Steve Block]

> Who else has worked on Geolocation in WebKit and should be thus CC'd on this
> bug?  I'm really not a geolocation expert, but I can take a look at this.
Greg Bolsinga is the only other person who's worked on Geolocation, but he's not a reviewer. This bug was created as a result of Bug 27944, which Darin Adler is reviewing. I've CC'ed them both.

[Eric Seidel (no email)]

Thank you.

[Eric Seidel (no email)]

Hum... I wasn't sure from the ChangeLog "why" we were doing this change, although it makes a bit more sense now reading the bug.  Still feels a little strange to me to use positive/negative to denote type here.

Why m_id instead of m_requestId or similar, as you seem to suggest it could/should be called in your changelog comments.

"id" is a reserved word in Obj-C, so if this header was included by Objective-C code, that could be an issue.

I didn't stare at the details of the change particularly closely.  Overall it looked fine.  I'm still slightly confused as to why, but really whichever of you is maintaining the geolocation code these days (you, greg, both, neither?) are in a better place to assess the "why".

[Darin Adler]

Comment on attachment 40361 [details]
Patch 1 for bug 29178

It's a little inelegant to use positive and negative numbers to make the map do two different things. It's the sort of "cleverness" we often try to avoid. I'll point out that the same thing can be done with unsigned integers just by choosing an arbitrary large number and having both sets of IDs go up. The large number approach avoids having to write the comment about avoiding the magic number -1. You also would need a function isValidWatchId to use instead of the "> 0" and "<= 0" checks, but this is actually an advantage rather than a disadvantage, since the code will be easier to read. A function like that would be good even if we do stick with the negative numbers.

In both cases, the real issue is guaranteeing the number won't wrap around. I'd like to see a comment explaining why overflow is known to not be an issue. Can't people intentionally do something in a tight loop and create the overflow?

I suppose we can live with it.

Normally I like to name the global something like lastUsedWatchID or nextAvailableWatchID rather than watchID to make it more clear why it's a global variable.

> +    GeoNotifierMap::const_iterator end = m_notifiers.end();
> +    for (GeoNotifierMap::const_iterator it = m_notifiers.begin(); it != end; ++it) {
> +        RefPtr<GeoNotifier> notifier = it->second;
>          notifier->m_timer.stop();
>      }

This is an unnecessary bit of reference count churn. I suggest writing it like this:

    it->second->notifier->m_timer.stop();

or like this:

    const RefPtr<GeoNotifier>& notifier = it->second;
    notifier->m_timer.stop();

or like this:

    GeoNotifier* notifier = it->second.get();
    notifier->m_timer.stop();

r=me

[Greg Bolsinga]

Looks good to me. I agree with Eric, if you can remove 'id' as a variable name, Obj-C++ will appreciate it.

Also, the single "< 0" test in Geolocation::clearOneShots may benefit from a comment similar to the one in the header. Alternately, could you create a inline method like "bool isOneShot()"?

[Eric Seidel (no email)]

Comment on attachment 40361 [details]
Patch 1 for bug 29178

Since there were modifications suggested by Gavin and Darin, this can't be landed by the bot.  cq-.  You can either post a new version, or make the suggested fixes when you land.

[Steve Block]

Created attachment 40716 [details]
Patch 2 for Bug 29178

(In reply to comment #5)
> Why m_id instead of m_requestId or similar, as you seem to suggest it
> could/should be called in your changelog comments.
>
> "id" is a reserved word in Obj-C, so if this header was included by
> Objective-C code, that could be an issue.
Fixed.

(In reply to comment #6)
> I'll
> point out that the same thing can be done with unsigned integers just by
> choosing an arbitrary large number and having both sets of IDs go up. The large
> number approach avoids having to write the comment about avoiding the magic
> number -1.
Yes, but it would complicate the logic in clearOneShots, which relies on the fact that one-shot IDs are smaller than watch IDs.

> You also would need a function isValidWatchId to use instead of the
> "> 0" and "<= 0" checks, but this is actually an advantage rather than a
> disadvantage, since the code will be easier to read. A function like that would
> be good even if we do stick with the negative numbers.
True, I've added isOneShotRequest().

> In both cases, the real issue is guaranteeing the number won't wrap around. I'd
> like to see a comment explaining why overflow is known to not be an issue.
> Can't people intentionally do something in a tight loop and create the
> overflow?
The existing code doesn't guard against overflow and I wasn't attempting to address it in this patch. Note that overflow is 'safe' in that when a request ID is re-used, the previously existing request will be stopped, so requests are not leaked. Of course, references to the old ID will now refer to the wrong request, which should be fixed. I've opened Bug 30122 to track this, as finding the right solution will probably require some discussion.

> Normally I like to name the global something like lastUsedWatchID or
> nextAvailableWatchID rather than watchID to make it more clear why it's a
> global variable.
Fixed.

> This is an unnecessary bit of reference count churn. I suggest writing it like
Fixed.

[Darin Adler]

(In reply to comment #9)
> (In reply to comment #6)
> > I'll
> > point out that the same thing can be done with unsigned integers just by
> > choosing an arbitrary large number and having both sets of IDs go up. The large
> > number approach avoids having to write the comment about avoiding the magic
> > number -1.
> Yes, but it would complicate the logic in clearOneShots, which relies on the
> fact that one-shot IDs are smaller than watch IDs.

Complicate in a good way. In my opinion, the current logic is unnecessarily subtle. It's the kind of cleverness that hurts maintainability over time. It would be easy to just add additional code in clearOneShots and not rely in that fact.

> > In both cases, the real issue is guaranteeing the number won't wrap around. I'd
> > like to see a comment explaining why overflow is known to not be an issue.
> > Can't people intentionally do something in a tight loop and create the
> > overflow?
> The existing code doesn't guard against overflow and I wasn't attempting to
> address it in this patch. Note that overflow is 'safe' in that when a request
> ID is re-used, the previously existing request will be stopped, so requests are
> not leaked. Of course, references to the old ID will now refer to the wrong
> request, which should be fixed. I've opened Bug 30122 to track this, as finding
> the right solution will probably require some discussion.

Also note that overflow will take us from positive IDs to negative IDs.

[Steve Block]

Created attachment 40742 [details]
Patch 3 for Bug 29178

(In reply to comment #10)
> Complicate in a good way. In my opinion, the current logic is unnecessarily
> subtle. It's the kind of cleverness that hurts maintainability over time. It
> would be easy to just add additional code in clearOneShots and not rely in that
> fact.
OK, I've updated the logic to use positive IDs for both one-shots and watchers. On wrap-around, we simply overwrite the previous request, to maintain the current behaviour.

[Adam Barth]

Comment on attachment 40742 [details]
Patch 3 for Bug 29178

This doesn't seem like a win to me.  The code isn't really getting any simpler, which you can approximate by noting that this patch adds roughly as many lines as it removes, but the code is getting more obscure.

I haven't studied your use case in detail, but maybe what you really want is a superclass with two subclasses, one for each type of object you wish to store.

At a higher level, I'm not sure this patch is solving a real problem.

[Steve Block]

> At a higher level, I'm not sure this patch is solving a real problem.
The problem being solved is the issue raised by Darin in Bug 27944, linked from the original description ...

---

>>>>> +    for (GeoNotifierMap::iterator iter = m_watchers.begin(); iter != m_watchers.end(); ++iter) {
>>>>> +        if (iter->second == notifier) {
>>>>> +            m_watchers.remove(iter);
>>>>> +            break;
>>>>> +        }
>>>>> +    }

>>>> Can a notifier have more than one watcher? It's unfortunate that we have to
>>>> iterate the map like this. Normally that's an anti-pattern -- we'd use a pair
>>>> of maps to avoid it.

>>> GeoNotifier represents a single request, which may be either a one-shot or a
>>> watcher. This structure maps from watch ID (type int) to watcher (type
>>> GeoNotifier). There's a one-to-one mapping between watch ID and watcher.
>>>
>>> An alternative to having to maintain a pair of maps would be to pass the watch
>>> ID to the GeoNotifier constructor. The GeoNotifier would then pass this watch
>>> ID, rather than its 'this' pointer, to this method. For one-shots, which don't
>>> have a watch ID, we could use either a single special value, or assign each a
>>> unique ID for internal use only. What do you think? This might be best done in
>>> a separate patch.

>> That sounds like a reasonable design. I don't feel that strongly but it's
>> always a warning sign when someone is iterating a map.

> OK, I'll refactor to use an ID to identify all notifiers. This will also
> simplify some of the logic. I've been wanting to do this for a while. I've
> opened Bug 29178, which block this bug, to address this.

---

(In reply to comment #12)
> (From update of attachment 40742 [details])
> This doesn't seem like a win to me.  The code isn't really getting any simpler,
> which you can approximate by noting that this patch adds roughly as many lines
> as it removes, but the code is getting more obscure.
It's true that overall, the code isn't any simpler. But the reason for the change is as described above - we want to pass a requestID, rather than GeoNotifier*, to Geolocation::requestTimedOut to avoid having to iterate the maps of watchers. I also think that identifying all requests (one-shots, as well as watchers) by ID, and storing all requests in a single map, is neater and makes things simpler when performing operations on all requests, such as in stopTimers.

> I haven't studied your use case in detail, but maybe what you really want is a
> superclass with two subclasses, one for each type of object you wish to store.
I don't think so. The two sets of GeoNotifier objects I'm storing are identical in nature - it's just that they're used differently by the Geolocation object.


Darin, are you happy with this approach? If not, I could resort to using a pair of maps for the watchers to avoid the look-up problem, which would probably require fewer changes.

[Eric Seidel (no email)]

Comment on attachment 40361 [details]
Patch 1 for bug 29178

Clearing Darin Adler's r+ on this obsolete patch.

[Steve Block]

Created attachment 41944 [details]
Patch 4 for Bug 29178

Now using a pair of maps.

[Darin Adler]

Comment on attachment 41944 [details]
Patch 4 for Bug 29178

r=me

> +    if (iter != m_idToNotifierMap.end()) {
> +        m_notifierToIdMap.remove(iter->second);
> +        m_idToNotifierMap.remove(iter);
> +    }

We normally prefer the early exit style, where this would return in the unusual failure case and the code would continue at the outer nesting level, rather than nesting the normal code flow path inside an if.

[Steve Block]

Comment on attachment 41944 [details]
Patch 4 for Bug 29178

cq- : Will land manually with Darin's minor change.

[Steve Block]

Committed r50159: <http://trac.webkit.org/changeset/50159>