Opened 12 years ago

Last modified 8 years ago

#3926 enhancement new

— at twisted.positioning -- a better positioning frameworkVersion 18

Reported by: lvh Owned by:
Priority: normal Milestone:
Component: core Keywords: protocols gps positioning
Cc: ashfall Branch:
Author: lvh

Description (last modified by lvh)

As some of you have undoubtedly noticed, Twisted's current GPS support (twisted.protocols.gps) has issues:

  1. The public API sucks:
    1. Fourteen arguments? All of them positional? Really?
    2. fooReceived methods are organized by what happens to be easy for NMEA sentences, not what makes sense
    3. It's hard to extend, raw objects are passed instead of pretty wrappers that abstract technology details away
    4. It's very protocol centric: the API changes between NMEA and Zodiac, a good API would look the same for any positioning technology
  2. There are no unit tests.
  3. It assumes we're using satellite navigation (well, not really, but only because there's no interface that says what it does)

This ticket is about a proposed alternative, twisted.positioning, which hopefully will:

  1. deprecate the existing code
  2. support more than satellite-based navigation (such as cell triangulation) or maybe just more than GPS (Galileo comes to mind)

After reviewing preliminary code and discussing the issue, we came to the following conclusions:

We need to have an interface (tentative name: IPositioningDataReceiver) that implements a number of methods, such as:

  1. positionRecieved(self, position)
  2. altitudeReceived(self, altitude)
  3. headingReceived(self, heading)
  4. ...

The parameters of these methods should not be simple objects (like floats or strs or bools), but Position, Heading... objects so that more API can be added later as required.

The classes that implement this should not continuously update their own state. Doing that is the job of the application that uses the framework.

Originally we thought it would be cool if accuracy data came together with positioning data, however this idea was dropped because it was unrealistic with real world positioning devices.

We should try to keep this API as general as possible (making as few assumptions about the underlying protocol as possible).

First thing to do should probably be finalizing the IPositioningReceiver interface. Getting it right is extremely important and has big implementation consequences: NMEA might present data in an illogical or useless order, but this shouldn't change our interface significantly.

This raises problems with the fooReceived methods, since data that is made available in chunks (headingRecieved doing both magnetic and true headings for example) might not have that data made available in the underlying implementation (some NMEA sentences only provide true heading, some proprietary ones only provide magnetic heading, and some sentences provide both -- it doesn't make sense to ignore the data from the first two types of sentence simply because they didn't have both kinds of heading).

The easy way out is to make the objects that the interface deals with as abstract as possible. With enough eyes, every problem is tiny, so your comments are much appreciated as usual.

You can find the code on Github: http://www.github.com/lvh/twisted has a positioning-3926 branch.

Change History (20)

comment:1 Changed 12 years ago by lvh

Summary: twisted.protocols.positioning -- a better positioning frameworkjktwisted.protocols.positioning -- a better positioning framework

comment:2 Changed 12 years ago by Glyph

A minor musing: perhaps it would be best to put this new, expanded framework into its own package, 'twisted.position' let's say, to get it a bit more visibility? (It may be best to forestall this discussion until the code's already written, because it's just a distraction, and I think there will be distutils implications; but, I wanted to get the suggestion up here before I forget.)

comment:3 Changed 12 years ago by lvh

Sounds like a great idea, but I didn't really think that it was important enough to warrant a toplevel package :-D Also "positioning" isn't nearly a crazy enough name for a top level twisted package. </silly>

Include margin of error information in callbacks, or keep it separate?

I was thinking about what glyph said in earlier discussion about messages that have potential error information, such as:

  • positionReceived
  • altitudeReceived
  • ...

... might want to get that error information there, rather than in a separate callback. After all, you don't care about a position measurement if it has an error that makes it irrelevant to your application.

The counterargument was mainly that, well, NMEA just doesn't want to do that -- there is no single NMEA sentence that is open (in the sense of "not proprietary"), widely supported, and provides you with all data. (For the interested reader: there are no such sentences that are proprietary, either.) For more information on the subject: http://esr.ibiblio.org/?p=801 (sort of funny, worth a read or quick skim if you're not yet convinced that talking to GPS devices sucks).

However, this feels like I'm mangling the interface just to make it easier for NMEA. This sounds like a bad idea. For example, when you're reading from a gpsd server, you can get all of this information (from now on called TPV+E -- time, position, velocity + errors, which is what you care about 90% of the time, the only thing that's missing is heading/course) at once.

gpsd does this by keeping internal state. We've already decided that keeping internal state would be bad for us, but unfortunately getting meaningful data from an NMEA-spewing GPS appears to be an inherently stateful problem.

So, the question is simple: what's worse? Keeping state, or changing the interface?

The alternative interface which does not keep state has multiple callbacks, like:

  • positionReceived(self, latitude, longitude)
  • positionErrorReceived(self, horizontalError, verticalError)
  • altitudeReceived(self, altitude)
  • altitudeErrorReceived(self, altitudeError)

If we kept state, we could do this instead:

  • positionReceived(self, latitude, longitude, horizontalError, verticalError)
  • altitudeReceived(self, altitudeReceived, altitudeError)

Personally I'm slightly more of a fan of the former because it keeps the NMEA implementation stateless. Then again, I'm stark raving mad.

comment:4 Changed 12 years ago by lvh

Alternative interface design

Hi.

This comment is a boiled down version from the ad-hoc code review from last night for which I'd like to really thank the culprits (exarkun, dash, tazle).

The interface as it exists now is pretty dumb, since the class that has lineReceived and fooReceived is the same thing, so either we change how it works or we remove the interface and just add stubs on the subclass.

A proposed solution by tazle involves splitting the current NMEAReceiver class up into two components: the receiver itself, which produces NMEA-centric data in a barely-better-than-raw form (so methods like GPRMCReceived), the interface, and then an NMEA-to-generic-interface adapter that keeps the necessary state to produce data in the useful form.

The only thing I don't like about it is that this is just the same thing as before (keeping state sucks) except it happens in the adapter instead of the receiver. Also, the receiver would be a fairly trivial piece of code: I'm guessing all it would do checksum verification, splitting and then call getattr(self, sentenceType + "Received")(splitSentence). The advantage is that people could do all sorts of gnarly stuff to the raw NMEA data, which I suppose could be useful.

Any comments?

comment:5 Changed 12 years ago by lvh

Update on the gpsd thing:

Development on the old protocol handler has halted, esr has said that a new fancy protocol will happen Soon(TM) (time frame: less than a month, more than a week). It's JSON based, and it's much nicer than this thing.

The old protocol won't be going away, but it will be deprecated.

Similarly, "watcher mode" (where you just listen instead of query + wait for response) will become the default. Obviously this is a lot better for an asynchronous framework like Twisted.

comment:6 Changed 12 years ago by lvh

Keywords: review removed
Owner: changed from Glyph to lvh

Removed for review, since it shouldn't have been in the first place. Uploading a proper patch later.

comment:7 Changed 12 years ago by lvh

Keywords: review added
Owner: lvh deleted

Hi!

Patch up for review, enjoy.

Comments on the points raised in previous comments on this ticket are still welcome of course :-)

comment:8 Changed 12 years ago by lvh

Things that I've seen myself that need reviewing:

  • t.p.nmea.NMEAAdapter
    • _cleanCurrentSentence: what would be the best way to guarantee fixer order? I think I can write the fixers in a way that order doesn't matter, but that isn't pretty (at the fixer level). It seems a bit ridiculous to have an entire dependency graph, on the other hand relying on the fact that lexicographical == proper order sucks too, prefixing the fixers with weights sucks. Perhaps an extra dict from fixers to weights or something?

  • t.p.nmea.NMEA
    • it seems like it has two ways of getting things to the NMEAAdapter. I'm guessing one of these has to go, but I'm not sure which.
      • the callbacks (nmea_GGA, nmea_RMC...)
      • explicitly, through self.receiver.sentenceReceived

comment:9 Changed 12 years ago by lvh

Hi!

Major update, changed the diff.

Again, any serious review should be against my launchpad branch, not patches. Here's an update anyway.

There's only one or two warts left in nmea.py, I'm not 100% sure how to fix them properly yet, but on the plus side this shouldn't change API when I do figure out how to fix it :-)

Changed 12 years ago by lvh

Attachment: positioning.diff added

comment:10 Changed 12 years ago by Jean-Paul Calderone

Keywords: review removed
Owner: set to lvh

Here is some initial feedback that should keep your todo list from shrinking to nothing for a while. ;) They're based on a pretty superficial look at the code, so none of them are terribly interesting, but they're necessary to address nonetheless:

  1. A lot of the code is not covered by the unit tests. You can see this yourself by running trial --coverage twisted.positioning and looking at the files written to _trial_temp/coverage. You should aim for complete line coverage, which means that none of the twisted.positioning.*.cover files in that directory should have any lines beginning with >>>>>> (which indicates the line was not executed during the test suite).
  2. twisted/positioning/base.py
    1. The docstrings of BasePositioningReceiver are all pretty short on actual information. The fact that the class is declared to implement IPositioningReceiver tells the reader what all of those methods are implementations of. The class itself could use a docstring explaining that it's a good base for implementations of that interface, and that its methods all are no-ops.
    2. Heading.heading (that's a bit redundant, eh?) and Heading.variation seem to be in degrees, but this isn't documented.
    3. TODO in _clipAngle. Also, it probably doesn't matter, but % is a nice operator, isn't it?
    4. The = used to bind correctHeading needs some whitespace around it.
    5. I don't think @return and @rtype should go into a property doc string. Maybe @type belongs there, or maybe the class should just have @ivar and @type. Mess around with pydoctor a bit to see how different things render.
    6. Take a look at twisted.python.util.FancyEqMixin for defining __eq__
    7. I cast a skeptical eye upon Heading.__imul__
    8. Stray "o" in Speed.__init__.__doc__.
    9. Use symbolic names for latitute and longitude in Coordinate. It improves the docs and reduces the error rate.
    10. What's the range of Coordinate.angle? After the checks in Speed and Heading I expected to see something similar here.
    11. More whitespace in the definition of DOP_EXPRESSIONS
    12. TODO in BeaconInformation
    13. acchieve typo in PositioningBeacon.
    14. TODO in Satellite
  3. twisted/positioning/ipositioning.py
    1. climbReceived has a TODO in it.
    2. These receivers might want startup and shutdown methods, analogous to IProtocol.makeConnection and IProtocol.connectionLost.
  4. twisted/positioning/nmea.py
    1. from twisted.protocols.basic import LineReceiver would be excellent. ;)
    2. super usage in NMEASentence.__init__ is questionable. What multiple inheritance is this class expected to participate in? And why is it okay to change the signature of __init__ in this super call? Generally that's a big no-no. Also, if this is going to use super, it needs to be documented, since it's part of the public API.
    3. NMEAAdapter is missing some ivar docs.
  5. Just in general,
    1. Lots of C{} markup in these docstrings could be L{} markup instead. Use C{} for something you might evaluate (somehow - with Python, in a shell, whatever). Use L{} for the name of a Python object.
    2. No generator expressions allowed. Python 2.3 compatibility is still required for Twisted.
    3. Try to use \ for line continuation less. Parenthesis are your friend here.
    4. __all__ is kinda nice, you probably want to add it to some of these modules
    5. @since 9.0 should go into some module docstrings.

As I said, pretty superficial. Possibly I'll try for a deeper understanding of the code on a future review, although I found things mostly straightforward and well written. So, nice work so far. :)

(I reviewed revision 15356 of bzr+ssh://bazaar.launchpad.net/~lvh/twisted/positioning/)

comment:11 Changed 12 years ago by greywulf

I've tried using the code a bit and I think there's a structural problem in the PositioningReceiver interface.

Currently, splitting the data in several methods
positionReceived...
timeReceived...

loses all association between the data, that is what data belongs to which update.

Use case 1:
Suppose the user wants to gather a track with times included or any other time series. Is timeReceived called before or after the data that it's to be combined with?

Use case 2:
Suppose the user is just interested in positions. What happens if there are multiple NMEA messages with position information? For example, both a RMC and a GGA message (currently positionReceived is called multiple times)

comment:12 Changed 12 years ago by lvh

Hi Eero :-)

I've tried using the code a bit and I think there's a structural problem in the PositioningReceiver interface.

Currently, splitting the data in several methods positionReceived... timeReceived...

loses all association between the data, that is what data belongs to which update.

Yes, these are supposed to return the latest data when they are called -- or to put it in another way, they are supposed to fire whenever . What does update mean in this context? Reporting cycle or sentence?

Use case 1: Suppose the user wants to gather a track with times included or any other time series. Is timeReceived called before or after the data that it's to be combined with?

If I am not mistaken, most GPSes will have reporting cycles that are short enough for this not to be a problem (1Hz or less or something), but perhaps this is not good enough for your particular application :-)

The problem is that a lot of the information that might be stored in time series might be presented in sentences that do not have time information. The most logical thing to do IMHO would be to implement an IPositioningReceiver that remebers the last presented time (eg an instanceattr that gets updated on timeReceived).

It would be possible to run the callbacks per sentence in a particular order, so that *if* the sentence contains a time, it is guaranteed that that is reported first. Again, I'm not 100% sure this will be a problem, but the latter solution will in all cases be at least as good as the data the GPS actually gives you :-)

Use case 2: Suppose the user is just interested in positions. What happens if there are multiple NMEA messages with position information? For example, both a RMC and > a GGA message (currently positionReceived is called multiple times)

Yep, the idea is that NMEAAdapter adapts an NMEAProtocol to an IPositioningReceiver, so it can't ignore things produced by the NMEAProtocol -- it does something with every bit of data (usually this means "fire a callback", sometimes it means "store a bit of stuff in intermediate state", sometimes it means "clear the current state, the gps has no idea where it is anymore"). Ignoring sentences based on some criterion should mostly be the job of the IPositioningReceiver.

If it turns out that people only want positioning, once the receiver is finished, they can always subclass the Adapter so that it doesn't waste time converting a bunch of stuff they don't really need, but that sounds like it should be a last step -- that's purely a performance tweak, not something that should implement new behavior. This is why the Adapter passes all the data from the protocol -- all the behavior is there, you usually want to filter so you get *less* data :-)

Regardless of what we end up doing, this should obviously be documented in the Lore docs (which don't exist yet), since graywulf knows his way around GPS stuff and all of this wasn't obvious from skimming the code (in all fairness, I only grokked it after glyph explained it to me twenty times :-)).

Thanks for your input! Laurens

comment:13 in reply to:  12 Changed 12 years ago by greywulf

Replying to lvh:

Okay, I've reunited with my copy of NMEA 0183.

I've tried using the code a bit and I think there's a structural problem in the PositioningReceiver interface.

Currently, splitting the data in several methods positionReceived... timeReceived...

loses all association between the data, that is what data belongs to which update.

Yes, these are supposed to return the latest data when they are called -- or to put it in another way, they are supposed to fire whenever . What does update mean in this context? Reporting cycle or sentence?

I was talking about the reporting cycle. You're right, these should be distinguished.

Use case 1: Suppose the user wants to gather a track with times included or any other time series. Is timeReceived called before or after the data that it's to be combined with?

If I am not mistaken, most GPSes will have reporting cycles that are short enough for this not to be a problem (1Hz or less or something), but perhaps this is not good enough for your particular application :-)

The problem is that a lot of the information that might be stored in time series might be presented in sentences that do not have time information. The most logical thing to do IMHO would be to implement an IPositioningReceiver that remebers the last presented time (eg an instanceattr that gets updated on timeReceived).

It would be possible to run the callbacks per sentence in a particular order, so that *if* the sentence contains a time, it is guaranteed that that is reported first. Again, I'm not 100% sure this will be a problem, but the latter solution will in all cases be at least as good as the data the GPS actually gives you :-)

Timing analysis is generally icky, noisy if you're behind a TCP/IP network connection, and impossible if you are just reading a NMEA logfile.

Actually implementing the current IPositioningReceiver interface would mean maintaining two states:[BR]one for the sentence and one for the report cycle.

Use case 2: Suppose the user is just interested in positions. What happens if there are multiple NMEA messages with position information? For example, both a RMC and > a GGA message (currently positionReceived is called multiple times)

Yep, the idea is that NMEAAdapter adapts an NMEAProtocol to an IPositioningReceiver, so it can't ignore things produced by the NMEAProtocol -- it does something with every bit of data (usually this means "fire a callback", sometimes it means "store a bit of stuff in intermediate state", sometimes it means "clear the current state, the gps has no idea where it is anymore"). Ignoring sentences based on some criterion should mostly be the job of the IPositioningReceiver.

If it turns out that people only want positioning, once the receiver is finished, they can always subclass the Adapter so that it doesn't waste time converting a bunch of stuff they don't really need, but that sounds like it should be a last step -- that's purely a performance tweak, not something that should implement new behavior. This is why the Adapter passes all the data from the protocol -- all the behavior is there, you usually want to filter so you get *less* data :-)

As mentioned in here http://esr.ibiblio.org/?p=801 , the NMEA standard does not specify the order of messages.

I checked the sentences and fortunately sentences with position data always have a UTC timestamp, so you can also always produce a position time series from sentences.

The same is not true for example velocity or satellite data. If you want parse a time series of those from logs, you either get have to know the order of messages, or have to go through the whole packet sniffer business like gpsd, if it's even possible on logs only.

I sketched a bit how I would actually like to use a sentence parser. It's small enough so I'm including it below:

class StatefulParser:
    def __init__(self):
        """The current report cycle is identified by the timestamp"""
        self.currentCycle = NoData
        self.lat = NoData # since null is a valid NMEA value
        self.lon = Nodata

    def process(self, nmealine):
        if not isValid(nmealine):
            return None # skip corrupted lines
        
        sen = Sentence(nmealine)
        t = time(sen)
        clearCycle() if self.currentCycle < t else self.currentCycle = t
        
        if sen.hasPositionData():
            self.lat = DDLat(s)
            self.lon = DDLon(s)

The approach is a bit different. I'd like to just ignore corrupted or unknown types of sentences instead of throwing exceptions. Also DDLat and DDLon have a more 'coercion' flavor, which was supposedly pythonic but apparently isn't in python 3.0

Have to go now, but lemme know what you think. Esr is right though, NMEA truly sucks.

comment:14 Changed 12 years ago by Glyph

So, it's been 8 months without an update. Is this effort still ongoing? What's the plan?

Changed 11 years ago by lvh

Attachment: positioning-3926.patch added

comment:15 Changed 11 years ago by lvh

Keywords: review added

Hi! See attached patch for review.

Questionable things:

There's a lot of x = property(x) calls that could be replaced by decorators.

A lot of things are defined by a particular implementation in t.p.base because I don't really think they're important enough to warrant an interface. The obvious rebuttal to that is that everything is important enough to warrant an interface. However, this can probably be done later (not in a different ticket, but after review :-)).

Accessing the hemisphere instanceattr on t.p.base.Coordinate instances raises ValueError when accessed on an invalid Coordinate. See t.p.test.test_base.CoordinateTests.badHemisphere. Although that could be classified as a case of GIGO, but maybe it should return None instead.

Support for gpsd was nuked. Can be added later. The old protocol that was partially implemented doesn't work anymore on current releases anyway, so it doesn't really matter.

Support for statistics in positioning was trashed. It's mostly academic anyway. Also, the math involved would be nearly impossible to review. Could be added in a later ticket but I doubt anyone cares.

Coverage is seemingly incomplete, but this is a lie:

Name                                     Stmts   Miss  Cover   Missing
----------------------------------------------------------------------
twisted/positioning/__init__                 0      0   100%   
twisted/positioning/base                   245      0   100%   
twisted/positioning/ipositioning            15      0   100%   
twisted/positioning/nmea                   219      1    99%   621
twisted/positioning/test/__init__            0      0   100%   
twisted/positioning/test/test_base         308      0   100%   
twisted/positioning/test/test_nmea         353      0   100%   
twisted/positioning/test/test_sentence      56      0   100%   
----------------------------------------------------------------------
TOTAL                                     1196      1    99%   

The offending line is the continue in:

if prn is None or snr is None:
    continue

I have asked Ned Batchelder about this. It is the consequence of the peephole optimizer. I have documented it as such in the code, and added a # pragma: no cover to the offending line so that coverage.py will correctly report full coverage.

Finally, _BaseSpeed looks like a last minute tack-on because it is. Unfortunately Climb subclassing Speed was a mistake, because although negative Speeds are nonsensical, negative Climbs just mean you're losing altitude. Oops. I introduced a superclass to have the comparison and unit conversion behavior, which is still identical between the two. __init__ warns about raising ValueError because Liskov.

comment:16 Changed 11 years ago by lvh

Owner: lvh deleted

comment:17 Changed 11 years ago by lvh

Oh, yes, and obviously #3953 needs to be merged into this before this can hit trunk...

comment:18 Changed 11 years ago by lvh

Description: modified (diff)
Summary: twisted.protocols.positioning -- a better positioning frameworktwisted.positioning -- a better positioning framework
Note: See TracTickets for help on using tickets.