possible logic error in standard side filter

[iceiceice]

I noticed in the C++ a logic error regarding the implementation of [allied_with] and [enemy_of] in a standard side filter:

https://github.com/wesnoth/wesnoth/blob ... r.cpp#L172
https://github.com/wesnoth/wesnoth/blob ... r.cpp#L184

These lines cause that, if the filter in an [allied_with] or [enemy_of] tag is vacuous (matches no sides), then the entire construction is declared to be false. Instead I think such a filter should be vacuously true, as is the case with all other filters that I am aware of.

To see why it is strange, think about the meaning of the tag -- for a side to match [allied_with] / [enemy_of] , it must be an ally / enemy of every side matching the given filter. So as that secondary filter gets more permissive / matching more sides, it becomes harder and harder for any side to satisfy the [allied_with] / [enemy_of] condition. If the secondary filter matches no sides, one would therefore expect that it should be easy to satisfy the [allied_with] / [enemy_of]. However with the current behavior it is instead *impossible*, suggesting that there is some sort of discontinuity.

As another example, consider writing a standard side filter in two ways

Code: Select all

[allied_with]
[has_unit]
type=Orcish Grunt
[/has_unit]
[or]
[has_unit]
type=Troll Whelp
[/has_unit]
[/or]
[/allied_with]

Code: Select all

[allied_with]
[has_unit]
type=Orcish Grunt
[/has_unit]
[/allied_with]
[allied_with]
[has_unit]
type=Troll Whelp
[/has_unit]
[/allied_with]

At least naively the meaning of these two should be the same -- they should match any side allied with every side that has either a Grunt or a Troll. However in practice they will actually be different because of the behavior I described earlier -- if there are no Orcish Grunts on the map, the second version can never be satisfied, while the first one can.

Is there some reason that the current behavior is desired / necessary? Otherwise I will push a bugfix to 1.12 and master by deleting the two lines highlighted.

[Anonymissimus]

I am very likely the one who did put that line there in the first place, search the commit log. Perhaps I wrote about the reason too.
I found the thread that led to the tags and this behavior: http://forums.wesnoth.org/viewtopic.php ... 07#p506907 (and the following posts by Sapient and myself) Seems this behavior was Sapient's wish and that I instead suggested to ignore such a case (without diving into it too deeply).

That being said, you intend to quickly change the behavior of some wml here, which may potentially break lots of scenarios.

[iceiceice]

Regarding: http://forums.wesnoth.org/viewtopic.php ... 07#p506907

I think the most natural thing might be to have alternate tags [has_ally] / [has_enemy] which would be the logical OR...
so it is true if there is any ally which matches the filter, and false otherwise, and make [allied_with] / [enemy_of] be unambiguously the logical AND.

If that is deemed to break too much compatibility then maybe in 1.13 we could deprecate [allied_with] / [enemy_of] and replace with e.g. [allied_with_all] / [enemy_of_all]

[Anonymissimus]

TBH I don't understand your last post. Maybe I'm confused, or you are ?
And not so many tags please, the two existing ones are already almost redundant. If you aren't an enemy, you should be an alli, right ? Since wesnoth knows only about war or alliance as diplomatic statuses. But [not][enemy_of] isn't the exact same as [allied_with], also due to that I let myself influence by Sapient's lobbyist-ish wishes...

[iceiceice]

I think I just wrote unclearly. Let me try again.

I think there are two "natural" meanings of

Code: Select all

[allied_with]
    F
[/allied_with]

when it is matched against a side s. They are:

(1) "Does there exist a side s' matching F which is allied with s?"

and

(2) "Is every side s' matching F allied with s?"

I guess that formerly we had the second one, until we added the C++ lines I referred to, and now we have:

"Is there at least one side matching F and also is every such side allied with s?"

There's nothing intrinsically wrong with this, it's just that usually you will want to know either one or the other of these, and so when you use it carefully you will have to write a bunch of extra code to figure out which part is going to be relevant. (Or just ignore it, and later be surprised.)

(1) allows you to say things like

Code: Select all

[allied_with]
    F
    [or]
        F'
    [/or]
[/allied_with]

is equivalent to

Code: Select all

[allied_with]
    F
[/allied_with]
[or]
    [allied_with]
        F'
    [/allied_with]
[/or]

(2) allows you to say things like

Code: Select all

[allied_with]
    F
    [or]
        F'
    [/or]
[/allied_with]

is equivalent to

Code: Select all

[allied_with]
    F
[/allied_with]
[and]
    [allied_with]
        F'
    [/allied_with]
[/and]

These things work because (1) is a logical OR of a predicate over all teams, and (2) is a logical AND. What we have right now is somewhere in between -- it behaves like an AND usually, but it behaves like an OR if the set of teams matching the predicate is empty.

Since we are pretty close to (2) and that was your original intention I guess, I would think we would want to switch to that -- this kind of alternate behavior is pretty subtle and my guess is most users would be surprised by it, although it does strictly speaking break compatibility. On the other hand there is an argument for (1) instead:

20140705 14:28:13< zookeeper> "for a side to match [allied_with] / [enemy_of] , it must be an ally / enemy of every side matching the given filter"
20140705 14:28:34< zookeeper> iceiceice, ^ btw, i find that pretty... odd. shouldn't it be "of any side matching the given filter"? :x
20140705 14:28:51< zookeeper> i know that's how it's documented and thus probably intended, but it seems weird
20140705 14:29:20< iceiceice> idk
20140705 14:29:26< iceiceice> i mean i guess you could use [not] and write it however you like
20140705 14:29:36< zookeeper> "is this side allied with a side having trolls" vs "is this side allied with every side having trolls"
20140705 14:29:47< iceiceice> i dont have enoguh experience to know which is more useful in a campaign
20140705 14:31:04< zookeeper> i don't even know who implemented those
20140705 14:31:13< zookeeper> anonymissimus added them to the wiki, but...
20140705 14:32:57< zookeeper> i don't know whether it really makes a difference in any but rare cases, but it's just that all other filters that i can think of operate on the basis of "whether a matching unit/whatever exists"
20140705 14:33:31< zookeeper> it just instantly ties my brain into a knot because i'm not used to thinking about a filter that way

Also based on Sapient's post -- it might be that (1) is typically closer to what people actually need to use?

We don't have to pick just one or the other, we could include both if we felt it allows us to write code that reads more naturally. If we were going to do that I would suggest that
(1) = [has_ally] F [/has_ally]
(2) = [allied_with_all] F [/allied_with_all]

We currently have the [enemy_of] tag also. You might think that you could write this in terms of [allied_with], but as you pointed out it can't be done in part because we changed the behavior from (2).

If we have (1) and (2) we can write [has_enemy] as:

Code: Select all

[not]
    [allied_with_all]
        [not]
            F
        [/not]
    [/allied_with_all]
[/not]

and [enemy_of_all] as:

Code: Select all

[not]
    [has_ally]
        [not]
            F
        [/not]
    [/has_ally]
[/not]

So if you don't mind writing [not], then you definitely only need one of [has_ally] and [enemy_of_all], and only one of [has_enemy] and [allied_with_all].

There's no easy way to write [has_enemy] in terms of [has_ally], so I don't think you can get away with less than two tags. (I think you would have to store the sides and search manually, or use a different WML feature.)

But I guess we could reasonably decide that that we will just have [has_ally] and [has_enemy], and that would be pretty simple. I don't feel strongly about what we pick, except that I know I would find it somewhat cumbersome to use / think about the current version, and I think users could easily be confused, since the fact that the thing I mentioned in the first post fails is fairly surprising.

Edit: I also don't see a reason why we can't have all four, if people think being able to write [enemy_of_all] makes their code more clear. (Then again, they can also use a macro.) Like I said, I don't feel strongly.

(Btw: Sorry Zookeeper that your emoticon is rendering strangely but I don't know how to fix it. )

[zookeeper]

I'm unable to discuss the finer points, so all I can really say (again) is that I do find it weird that we only have a filter for checking "whether all sides this side is allied with match the filter" instead of the more intuitive and familiar "whether this side is allied with a side which matches the filter". It just seems to operate in a completely different mindset than everything else.

We shouldn't change the current behavior, but I think adding [has_ally] and [has_enemy] as iceiceice suggests would be a good thing.

[Anonymissimus]

IIRC I originally coded (2), and changed it to what we now have later on, yes.

all I can really say (again) is that I do find it weird that we only have a filter for checking "whether all sides this side is allied with match the filter" instead of the more intuitive and familiar "whether this side is allied with a side which matches the filter".

IIRC I never wondered about multiple sides matching the filter, only just one...if there's only one such side there's no difference.
But this behavior could be added with a control key. For instance, require_all=yes/no (def yes). My heart (and head) aches about adding more confusing tags.

[Sapient]

This whole discussion is a bit confusing... but here are a few responses to some of the points:

1) The Troll/Grunt example you gave in your original post does not seem like a wrong behavior to me. Consecutive [allied_with] filters should be mutually required (logical AND), just like everywhere else that supports consecutive filters, (e.g. consecutive [filter_adjacent]).

2) I still think the vacuous case should always be false for both allies and enemies. You can't be either an ally or an enemy of a side that doesn't exist. That should be a logically self-evident truth.

3) As a general rule, attributes which allow ranges or lists of comma-separated values should not be mutually required (logical OR). Unfortunately this principle was violated for [filter_vision] viewing_side= and then that mistake was carried forward with the SSF implementation (now [filter_vision]side=).

4) Similar to point #3, tags which can identify multiples of something should default to a one-or-more interpretation from the perspective of the containing tag. This is similar to how [filter_adjactent] count= defaults to "1-6". (For purposes of this discussion point, you may consider [filter_vision] to be the container of an implicit [filter_side] tag.)

5) It follows from point #4 that a side should be an enemy of one-or-more sides identified in an [enemy_of] filter to match the SSF. This could be altered with a count= attribute if needed.

[iceiceice]

2) I still think the vacuous case should always be false for both allies and enemies. You can't be either an ally or an enemy of a side that doesn't exist. That should be a logically self-evident truth.

Yes, but [allied_with] is defined by "am I allied with ALL sides that match ...". If the question is "am I the enemy of all foobars" and there are no foobars, then I didn't fail to be the enemy of any foobar, so I vacuously satisfied the condition.

1) The Troll/Grunt example you gave in your original post does not seem like a wrong behavior to me. Consecutive [allied_with] filters should be mutually required (logical AND), just like everywhere else that supports consecutive filters, (e.g. consecutive [filter_adjacent]).

The point was not that either behavior was wrong, just that the two cases (one using internal [or], one using external [and]) were different. That seems unnecessarily complicated and confusing. Whatever the "right" behavior is it should be the same in both cases, for simplicity, imho. Otherwise whenever I look at someone else's WML (and internally translate it to how I best understand it, like everyone does) I have to remember all these odd edge cases "what if filter A is empty, what if filter B is empty...".

5) It follows from point #4 that a side should be an enemy of one-or-more sides identified in an [enemy_of] filter to match the SSF. This could be altered with a count= attribute if needed.

I think that would be great behavior, that would correspond to version (1) in my post above. But that isn't what we have.

"side should be an enemy of one-or-more sides identified in an [enemy_of] filter to match the SSF" would mean we were taking a logical OR of the matches. But what we actually have is:

- If there are no matches to the [enemy_of] part, then we fail to match.
- If there are any matches there, then we must be an enemy of ALL of them or we fail to match.

I don't see that that has an analogue in the examples you gave.

Edit: What zookeeper proposed above is that, in addition to what we currently have, we add a tag [has_enemy] that does exactly what you said "side should be an enemy of one-or-more sides identified by a [has_enemy] filter to match the SSF", and similarly a [has_ally] tag.

[Sapient]

- If there are any matches there, then we must be an enemy of ALL of them or we fail to match.
I don't see that that has an analogue in the examples you gave.

If that's true then it's the same (flawed) behavior of the implicit side filter in [filter_vision].
And it should probably be fixed, although that could break some existing WML.

[iceiceice]

I see, now i understand what you were saying about side_filter.

So I checked how filter_vision is implemented, it seems that there's actually a discrepancy between how it works in a terrain_filter and how it works in a unit_filter. In a unit_filter, if the [filter_vision] child fails to match then we fail to match and don't process any further. In a terrain_filter, if that happens we just continue.

Here's how the unit_filter code looked before I started refactoring it:

https://github.com/wesnoth/wesnoth/comm ... 74544ab0b9

(here's the relevant line in the previous commit: https://github.com/wesnoth/wesnoth/blob ... .cpp#L1600)


Here's where the terrain_filter code came from:

https://github.com/wesnoth/wesnoth/commit/aa2a083f

Notice that that line is missing