What's the purpose of ElementFilterExpression parsing?

[smichel17]

StreetComplete/app/src/main/java/de/westnordost/streetcomplete/quests/tactile_paving/AddTactilePavingCrosswalk.kt

Lines 14 to 26 in 5409e04

	private val crossingFilter by lazy { """
	nodes with
	(
	highway = traffic_signals and crossing = traffic_signals and foot != no
	or highway = crossing and foot != no
	)
	and (
	!tactile_paving
	or tactile_paving = unknown
	or tactile_paving = no and tactile_paving older today -4 years
	or tactile_paving = yes and tactile_paving older today -8 years
	)
	""".toElementFilterExpression() }

Naively, I'd assume that once you parsed the elements into Kotlin objects, you'd filter them directly with Kotlin code. And indeed, under the hood that's what happens — the string is parsed into an ElementFilterExpression whose matches() function does exactly that.

So what's the purpose of the extra level of abstraction, writing them as strings? Is it to match query syntax from somewhere else in the OSM ecosystem (e.g. overpass)? (In more academic terms, why write a DSL instead of a library?)

[matkoniecz]

So what's the purpose of the extra level of abstraction, writing them as strings?

It makes it easier to edit/read it? How else it would be written? As instantiation of several objects and putting them together?

[smichel17]

How else it would be written?

As a function. Here's a naive conversion, just for illustration:

private val crossingFilter: Element.() -> Boolean = {
    return type == NODE &&
    (
        tags["highway"] == "traffic_signals" && tags["crossing"] == traffic_signals && tags["foot"] != "no"
        || tags["highway"] == "crossing" && tags["foot"] != "no"
    )
    && (
        tags["tactile_paving"] == null
        || tags["tactile_paving"] == "unknown"
        || tags["tactile_paving"] == "no" && tagOlderThan("tactile_paving", 4 * YEARS)
        || tags["tactile_paving"] == "yes" && tagOlderThan("tactile_paving", 8 * YEARS)
    )
}

Which could then be refactored to something more like this:

// AddTactilePavingCrosswalk.kt
private val crossingFilter: Element -> Boolean = {
    it is Node
    && it.isFoot
    && (it.isTrafficSignals || it.isCrossing)
    && it.getWithAge("tactile_paving").let { tag ->
        tag.value == null
        || tag.value == "unknown"
        || tag.value == "no" && tag.age > 4 * YEARS
        || tag.value == "yes" && tag.age > 8 * YEARS
    }
}

// In a module, shared between quests
private val Element.isFoot = tags["foot"] != "no"
private val Element.isTrafficSignals =
    tags["highway"] == "traffic_signals" && tags["crossing"] == traffic_signals
private val Element.isCrossing = tags["highway"] == "crossing" && tags["foot"] != "no"
data class ValueAndAge(value: String, age: Int)
private fun Element.getWithAge(tag: String): ValueAndAge {
    // ...implementation
    return ValueAndAge(value, age)
}

[matkoniecz]

In my personal opinion it is far, far, far less readable

[smichel17]

Hmm. I suppose. To me the current way is more readable on the happy path and less at the margins. What I mean is that I already understand Kotlin semantics, and how it will handle edge cases. In StreetComplete filter expressions, there's another layer of code I have to go digging through to see how they're actually getting parsed and executed.

For a simple example, I don't know if the age filter is inclusive or not (> vs >=). Also, the older today -8 years part was confusing to me. It wasn't until just now that I realized it's supposed to be read as "older than today, minus eight years"; I was reading it as "negative eight years older than today", which seems backwards since in English I'd say "eight years ago".

For a more meaningful example, it's hard to reason about the performance of these queries, because I don't know what type of code they're generating; it's another ~1200 LoC to understand (and maintain).

[mnalis]

Best used 1200 LoC ever, then (in my opinion)! 😄

The first example is nice, compact, simple, readable and understandable immediately with basically no effort to anybody with even most rudimentary programming experience in virtually any programming language (BASIC, Pascal, FORTRAN, dBase, Awk, C, C++, Java, Rust, Ruby, Javascript, Lua, PHP, ASP.NET, TCL, Perl, Python, Go, Scala, R, POSIX Shell, SQL, Verilog, ... heck even simple LibreCalc/Excel formulas).
It's just a bunch of simple comparisons connected with boolean operators. No specific programming language is even needed: if you know basic math and have heard of boolean algebra, you'll be able to read what it does, and even know how to write different one which does what you want instead.

The second example, on the other hand, is utterly incomprehensible even to read (and much, much harder to write!) for anybody who has not heavily invested into at least few months (or years) of learning Kotlin programming specifically. And it's longer.

[smichel17]

Part of my motivation for asking this question was: The way filter expressions are currently written, there's very little shared code. For something like #3301, the same logic would need to be duplicated for each quest which should have the same restrictions. That makes it hard to ensure that quests which target the same "base" set of elements do so consistently.

There's good reasons to be cautious about de-duplicating here. Surely, there's lots of incidental duplication, which would only tie together otherwise-unrelated functions if we tried to pull out the common code. But I think it's at least still worth exploring.

With the current approach, it's technically *possible* to split up and re-use sections of a filter.

val isFoot = "foot != no"
val isTrafficSignals = "highway = traffic_signals and crossing = traffic_signals"
val isCrossing = "highway = crossing"

private val crossingFilter by lazy { """ 
    nodes with 
      ( 
        $isTrafficSignals and $isFoot 
        or $isCrossing and $isFoot  
      ) 
""".toElementFilterExpression() } 

However, at that point, in my opinion, we've thrown away any readability advantage compared to what I wrote in the thread above (converted to an extension function)

private val crossingFilter: Element.() -> Boolean = {
    this is Node &&
    (
        isTrafficSignals && isFoot
        || isCrossing && isFoot
    )
}

[matkoniecz]

Note that actually complex parts are already handled via Kotlin code - see address quest, construction resurvey quest. Though most is quite quest-specific.

Tag filters are quite simple so gains from deduplication are not significant.

[smichel17]

Ah, I see. Thanks for the context, that makes sense. Although now I wonder if a few infix functions could produce nearly the same readability, with the added benefit of compile-time checking. E.g.

infix fun Boolean.and(that: Boolean): Boolean = this && that
infix fun Boolean.or(that: Boolean): Boolean = this || that

class ElementFilterExpression {
    private infix fun String.is(other: String): Boolean { /* ... */ }
    private infix fun String.isNot(other: String): Boolean { /* ... */ }
}

private val crossingFilter: Element.() -> Boolean = {
    this is Node and
    (
        "highway" is "traffic_signals" and "crossing" is "traffic_signals" and "foot" isNot "no"
        or "highway" is "crossing" and "foot" isNot "no"
    )
}

(not sure if this particular example would actually work with overloading is, but the general idea…)

Anyway, not going to worry about it further now; I have my answer.