Fix lane count calculation - use Scheme structs to avoid re-reading/re-interpreting tags

BudgieInWA commented 2 years ago

I am submitting this draft PR to get input on the new approach to driving_lane_directions, rust style and tests.yml. This PR is aiming towards ~~#69~~ #72.

Are we happy with this overall structure for `driving_lane_directions`?

bf5df9d8abdad9b72b4a5b64d558784d6695d1e8 shows the concise version, and dc5de27a3ee539cf25735219d2fdd2c8ffc7e677 shows how useful tag validation warnings can be added (thinking about #101 and how an editor would like to use tags_to_lanes).

Any feedback on my rust style?

I want to fit into this project, more than anything else, but couldn't help trying out is_some_and and using lots of unwrap_or.

How do the roundtrip tests work?

I couldn't figure it out just yet. Some guidance in the docs about writing and running tests.yml tests would be super awesome. (I figured out cargo test --feature tests, which I'll add to the docs if I get there first.)

droogmic commented 2 years ago

but couldn't help trying out is_some_and and using lots of unwrap_or

Looks pretty idiomatic to me, but then again I am not expert.

droogmic commented 2 years ago

I figured out cargo test --feature tests

This was a bug, it should be fixed now.

You should be able to run all the tests with just cargo test

The roundtrip works by taking the output (only the output), and checking that you can get back to the same spec by going to tags and back again (round trip).

Why not tags -> spec -> tags? Well: spec to tags is a one to many mapping, so this shouldn't guarantee a roundtrip.

Documentation is very welcome!

droogmic commented 2 years ago

Agreed, the content and location of the warnings appears correct.

On Sun, 27 Mar 2022, 07:52 Ben Ritter, @.***> wrote:

@.**** commented on this pull request.

In rust/osm2lanes/src/transform/tags_to_lanes/mod.rs https://github.com/a-b-street/osm2lanes/pull/111#discussion_r835855425:

.get("lanes:bus")

.and_then(|num| num.parse::().ok());

if oneway.into() {

// TODO support oneway=-1

if tagged_backward.is_some() {

warn!("lanes:backwards tag on a oneway road")

}

if tagged_both_ways.is_some() {

warn!("lanes:both_ways tag on a oneway road")

}

match (tagged_lanes, tagged_forward) {

(Some(l), None) => (l, 0),

(Some(l), Some(f)) => {

if l != f {

warn!("lanes tag does not agree with lanes:forward on oneway road")

This does seem like the right place to generate most of these warnings, so I will upgrade all of the warn!s to instead feed into the RoadWarnings vec.

— Reply to this email directly, view it on GitHub https://github.com/a-b-street/osm2lanes/pull/111#discussion_r835855425, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACEL2Z6UD6DUGQ2WZS7ZFEDVB7ZRTANCNFSM5RTT6CFA . You are receiving this because you were mentioned.Message ID: @.***>

BudgieInWA commented 2 years ago

I am finding more and more out about Tags library and the parsing techniques and good RoadMsg construction, still a little way to go. But, there is a fundamental problem:

The problem with locking in a final guess on the lanes distribution at the start

We cannot assume or guess missing parts of the lanes:{forward,backward}= scheme without parsing everything else. See how 28300bc adds tons of code parsing other schemes. Definitely smelly.

We need a way to narrow down our guess as we go. Random thoughts:

Maybe we use Infer like values too keep track of guesses.
Maybe in guessing mode, start with the assumption that there is one normal lane in each direction, then add lanes instead of mutating existing lanes. Then at the end we can do a round of assuming (e.g. distribute remaining lanes).
Maybe each tagging scheme has its own struct type using Infered values, which remains internally consistent, to help in the code which validates each tag schema, checks for conflicts, and wants to jump between them in order to do these complicated guesses. Then the validated and consistent schemes are used to build the road. Maybe having code that defines the test and guesses for each requirement between schemes is exactly the right amount of code (e.g. lanes:bus:forward=2 requires at least 2 forward lanes, or increases the guesses forward lanes by 2), but it still feels a bit like double handling (the whole point of the Builder pattern is to keep track of the jumping between different inputs, right?)
It ties into validating: psv:lanes=designated| requires lanes=2 to parse properly, so it implies lanes=2 (and is an error if lanes!=2)
It feels a bit like Logic Programming where different tags are facts that work to collapse the possibility space.

droogmic commented 2 years ago

I agree with everything you say, but I also don't really know the best way forward.

but it still feels a bit like double handling (the whole point of the Builder pattern is to keep track of the jumping between different inputs, right?)

correct

Maybe in guessing mode, start with the assumption that there is one normal lane in each direction, then add lanes instead of mutating existing lanes.

I agree, that we should maybe try this instead. The downside is that all the other logic needs to account for this new system, so it will be a painful refactor :(.

A simplified version of the logic you have now should probably still exist, to populate a top level Infer field in roadbuilder that may get invalidated by clearer tags later (like your bus example)?

In any event, it sounds like you understand the problem. Now you just need to decide how hard you make the solution for yourself ;)

droogmic commented 2 years ago

I added you to the project, so hopefully I dont need to approve the CI anymore

BudgieInWA commented 2 years ago

In any event, it sounds like you understand the problem. Now you just need to decide how hard you make the solution for yourself ;)

This was just the right thing to hear :) There are a couple of hacky things that I could try, but I don't see them coming together, so I decided to make the solution very hard for myself :D

A simplified version of the logic you have now should probably still exist, to populate a top level Infer field in roadbuilder that may get invalidated by clearer tags later (like your bus example)?

In c9ca0eb I started breaking out schema parsing from road building, so that the lanes schema can have access to the already parsed bus lanes. It looks like a direction that I want to keep exploring... which leads to the "hard" part:

Then 0496070 I started writing the overall structure from scratch, as if I had access to Hunch and Scheme types, and I tried to plot a path through all the steps of assuming the value of some schema given the road, adding tags into the existing assumptions/requirements, etc.

I think Hunch needs breaking into two parts, as the comments hint at, but I am actually very happy with Scheme and how it helps be think about the problem:

Decide a canonical way to represent the scheme - e.g. all of the busway tags - in the context of oneway and oneway:bus can only boil down to: 'is there at least one lane" in each direction(and possibly if it is the opposite direction to expected, depending on interpretations of opposite_lane).
write default(&Road) -> Busway which looks at those dependant tags on the road
write set_tags(mut self, &Tags) which sets as much detail as possible (and possible makes other assumptions, even guesses), detects any conflicts with already recorded Implications (or should it just read the dependant schemes from the road again, to detect conflicts with implications)
write guess separately, with whatever crazy logic that I don't want anywhere near the strict-mode parsing path, etc.
write impl Road { update_lanes_with(&mut self, scheme: Busway) {} } based solely on the values that come out the the Hunches in a schema.

As we think about it more, we can figure out what ordering requirements we need to enforce between all of the Scheme updating, and road building steps. It feels like there are comfortable places to put all of the pieces of complexity that I have come across so far: none of the schemes or the assumptions or guesses are that complicated themselves, and this way of dividing the responsibility's up seems to allow each of those things to be expressed in the right context. E.g. "if lanes= is not tagged, assume there is one lane in each travel direction (more on freeways) in addition to those described by all the bus tags" is the straightforward assumption that we want to make to support naked busway tags and the like. By deciding that busway is handled first, and implementing the assumption logic separate from the tag parsing logic, that becomes the appropriately straightforward let total_bus_lanes_forward = sum_bus_lanes(); ( Assume(default_forward + total_bus_lanes), ...).

I would love for @droogmic and/or @dabreegster to have a read through road.rs to

see how close my attempts have approached your existing solution :P,
see if the way tags_to_lanes, Road, Scheme and Hunch fit together in a way is comprehensible, and if so
help decide what shape Hunch and some other types should have, and
weigh in on how to approach implementing this idea further.

Next steps are

decide viability / approach:
- rebuild: add 'strict mode output' to tests, so we can start from scratch and build up parsing of all schemes as written, then come back later to implement guesses (I am happy to get stuck into this kind of approach over some time)
- iterate: combine Hunch and Infer, change RoadBuilder to work with Scheme, then implement schemes one by one, including existing guessing (sounds sensible if the architectures are similar enough, and we are happy to sacrifice a few tricky tests to begin with)
implement type APIs and rust fiddlyness for Hunch and Scheme
modify existing RoadBuilder, or write a new one, to work with Schemes
rewrite all scheme parsing (!) in the new format (which might not be tooo horrible)

BudgieInWA commented 2 years ago

I'm having too much fun exploring the rust type system to get anything compiling yet, but that is my next step. I should be able to get Hunch, Theory and Scheme compiling easily enough, to start actually seeing if they are useful.

droogmic commented 2 years ago

At the moment my main concern is how you get such a big change integrated without needing to freeze all parallel development.

I think Hunch, and building lanes up from a base assumption of 1 (instead of converting them), are, if I understand correctly the 2 options that we can start with. I wonder to what extend we can deliver those now and expand to this more complete system over time. Things like Theory are probably something that can come later.

The reason I say this is that my current short term goal is to push quickly towards getting most roads working in the countries that abstreet and similar tools usually operate, and I think the current simple schema can get us there without too much of an issue.

BudgieInWA commented 2 years ago

Good ideas, but the scope has crept a bit ;) I'm catching up on everything now (and feeling a little bit lost)...

I told you I had chosen the hard option to look at :) I will keep this idea/practice going in a branch and get back to the task at hand on this one. Thanks for watching me figure out rust.

I will start with pre-parsing the schemes like c9ca0eb, then build up to guessing lanes= last. I think it turns out that the order that we consider each scheme matters, even in my experiment. That might be the heart of it, and we can test it with just the schemes that lanes= depends on (anything that hints at specific kinds of lanes).

At the moment my main concern is how you get such a big change integrated without needing to freeze all parallel development. ... Things like Theory are probably something that can come later.

Absolutely; I will merge main into here as needed once I go back to a compiling commit and we should only implement any ideas bit by bit (maybe we add what I was using in Hunch to Infer, maybe we add scheme structs with ::from(tags), etc.).

BudgieInWA commented 2 years ago

@droogmic I started focusing on solving the original problem again :)

This is almost ready to merge. Probably a few rust-isms to tweak.

I plan on refactoring all of the bus lane tag parsing to use the *Scheme pattern that I have used here, but would prefer not to block this PR on those. As long as the direction that this PR takes lanes_to_tags is the right direction, I'm happy to merge, now that most of the tests are passing.

BudgieInWA commented 2 years ago

Now we just need to

solve our understanding of the busway scheme, at least so the test passes, and
merge main in here.

@droogmic, I would be happy for you to do the merge, and arrange my new functions wherever you see fit. But if you prefer, I can do it when I have time during the week (my detours are the reason this turned into such a mammoth PR after all).

droogmic commented 2 years ago

Now we just need to
* solve our understanding of the busway scheme, at least so [the test passes](https://github.com/a-b-street/osm2lanes/pull/111#discussion_r846289902), and

* merge `main` in here.
@droogmic, I would be happy for you to do the merge, and arrange my new functions wherever you see fit. But if you prefer, I can do it when I have time during the week (my detours are the reason this turned into such a mammoth PR after all).

to confirm, you want me to solve the merge conflict? it is indeed probably easier if I do it, given I caused it :P

BudgieInWA commented 2 years ago

to confirm, you want me to solve the merge conflict? it is indeed probably easier if I do it, given I caused it :P

Yes, I would appreciate it.

droogmic commented 2 years ago

The rust part is merged: https://github.com/BudgieInWA/osm2lanes/pull/1

Some kotlin and python stuff is still failing.

BudgieInWA commented 2 years ago

Thanks for merging the module restructure @droogmic, I have just merged the newer changes, so this should merge cleanly (currently :P).

I don't know anything about the kotlin tests, and the report linked here didn't show me what was wrong, so can someone else please look into that? Feel free to push commits directly to this branch (which I think is enabled by the "Allow edits by maintainers" checkbox that I have on).

I would like for this PR to be merged now, if we are happy with the direction it takes us. I am happy to be assigned followup issues (or be pinged in fixes to nitpicky issues so I can learn from them) in the interest of working from the same branch going forward. In future, my PRs will be more focused than this one: The detours and explorations that I did on this PR were valuable to me in learning rust and learning this codebase -- especially with your input -- but that's not the way I like to do PRs in general; and I don't plan on restructuring things out of the blue as I ended up doing in this PR.

dabreegster commented 2 years ago

Kotlin: I can't follow https://github.com/a-b-street/osm2lanes/blob/main/CONTRIBUTING.md#kotlin locally; gradle is throwing some unhelpful error. The test log shows it succeeded at YAML -> JSON, but then kotlinx.serialization.json.internal.JsonDecodingException at Test.kt:56. Unhelpfully, https://github.com/a-b-street/osm2lanes/blob/main/kotlin/src/test/kotlin/Test.kt doesn't have 56 lines, so it's maybe some test framework file?

BudgieInWA commented 2 years ago

I can agree to this once you look at what I have done and can justify why this is better.

How do we extend this to include taginfo.openstreetmap.org/keys/taxi:lanes? it feels a lot of the lane handling is hardcoded to bus and only bus?

My intention is to achieve a couple of things:

Separate tag parsing from road building, by introducing Scheme structs that represent the valid states described by smalls sets of tags. BuswayScheme is a good example: the busway tags are a complicated way of describing "is there a bus lane on the forward side, and is there a bus lane on the backward side", so we parse all those tags into BuswayScheme(Infer<(bool, bool)>) and never have to look up a busway tag value again.
Fix the guessing of the total number of lanes, by inverting the order that the tags are looked at.
Move towards tackling the ordering of looking at different tags at the top level tags_to_lanes. a.k.a. express the direction of dependencies between tags in one place. I have only taken a step in that direction, creating BuswayScheme, CentreTurnLaneScheme, and LanesScheme (which take other Scheme arguments to show dependencies), and constructing them in the right order at the top level.

These ideas would be further helped by:

Implementing a Scheme for every tag or set of tags that we parse (even Oneway has way more complexity that we don't support yet).
Bringing the guessing logic out of the Scheme constructors, and into road builder. Maybe Scheme constructors should not Infer::Guess at all, and only return Direct, Calculated (for internally calculated values, like lanes=lanes:forward + lanes:backward) and Default values. At the top level, or as a set of RoadBuilder methods, follow an ordered procedure for building up the road using the Schemes, but no tags.
- This would allow us to remove all dependencies from LanesScheme::new, (except maybe oneway) and figure out the guesses in a context which has access to a RoadBuilder with some lanes already added and the parsed LanesScheme (like https://github.com/a-b-street/osm2lanes/issues/136#issuecomment-1104149579). That step would treat Direct values in LanesScheme differently to Default values.

droogmic commented 2 years ago

Ok, but then I think we might be trying to do too much in one PR (which is where the difficulty is coming from).

Either we fix the lane counting, or we fix the scheme parsing. Doing both at the same time is blocking quick progress :)

droogmic commented 2 years ago

kotlin is probably failing in the tests.yml file, so I suggest bisecting the changes you made there until kotlin is happy?

droogmic commented 2 years ago

my bad, the button for close is very close to the one with comment :laughing:

dabreegster commented 2 years ago

Thanks for splitting into smaller PRs and pushing them through. Just checking in, was closing this PR intentional, or a side effect of the commit message there? Are any of the ideas in this PR still not merged in by one of the smaller PRs?

droogmic commented 2 years ago

A side-effect. I removed a lot of stuff from this PR that were not needed to make the tests pass

@BudgieInWA will probably want to go through the final status to reintroduce some of the less critical ideas he had (I removed the Infer::Guessed variant for example), preferably as a TDD when they become needed.

BudgieInWA commented 2 years ago

A side-effect. I removed a lot of stuff from this PR that were not needed to make the tests pass

@BudgieInWA will probably want to go through the final status to reintroduce some of the less critical ideas he had (I removed the Infer::Guessed variant for example), preferably as a TDD when they become needed.

This is a great outcome. Getting these ideas our into the open is probably the appropriate amount of progress for now.

a-b-street / osm2lanes