Why doesn't Cases match all instances of XMLElement, given Infinity levelspec?

Question

Why doesn't Cases match all instances of XMLElement, given Infinity levelspec?

Column@ Cases[
Import["http://www.weather.gov/data/current_obs/KOAK.xml","XMLObject"],
XMLElement[tag:_,_,value:_]:> (tag-> value),Infinity
] 

(* ==>
credit->{NOAA's National Weather Service}
credit_URL->{http://weather.gov/}
url->{http://weather.gov/images/xml_logo.gif}
title->{NOAA's National Weather Service}
link->{http://weather.gov}
image->{XMLElement[url,{},{http://weather.gov/images/xml_logo.gif}],XMLElement[title,{},{NOAA's National Weather Service}],XMLElement[link,{},{http://weather.gov}]}
suggested_pickup->{15 minutes after the hour}
suggested_pickup_period->{60}
location->{Oakland, CA}
station_id->{KOAK}
latitude->{37.7}
longitude->{-122.22}
observation_time->{Last Updated on Apr 11 2012, 12:53 pm PDT}
observation_time_rfc822->{Wed, 11 Apr 2012 12:53:00 -0700}
weather->{Mostly Cloudy}
temperature_string->{60.0 F (15.6 C)}
temp_f->{60.0}
temp_c->{15.6}
relative_humidity->{62}
wind_string->{Southwest at 13.8 MPH (12 KT)}
wind_dir->{Southwest}
wind_degrees->{220}
wind_mph->{13.8}
wind_gust_mph->{0.0}
wind_kt->{12}
wind_gust_kt->{0}
pressure_string->{1014.2 mb}
pressure_mb->{1014.2}
pressure_in->{29.95}
dewpoint_string->{46.9 F (8.3 C)}
dewpoint_f->{46.9}
dewpoint_c->{8.3}
windchill_string->{58 F (14 C)}
windchill_f->{58}
windchill_c->{14}
visibility_mi->{10.00}
icon_url_base->{http://weather.gov/images/fcicons/}
two_day_history_url->{http://www.weather.gov/data/obhistory/KOAK.html}
icon_url_name->{bkn.jpg}
ob_url->{http://www.weather.gov/data/METAR/KOAK.1.txt}
disclaimer_url->{http://weather.gov/disclaimer.html}
copyright_url->{http://weather.gov/disclaimer.html}
privacy_policy_url->{http://weather.gov/notice.html}
current_observation->{XMLElement[credit,{},{NOAA's National Weather Service}],XMLElement[credit_URL,{},{http://weather.gov/}],XMLElement[image,{},{XMLElement[url,{},{http://weather.gov/images/xml_logo.gif}],XMLElement[title,{},{NOAA's National Weather Service}],XMLElement[link,{},{http://weather.gov}]}],XMLElement[suggested_pickup,{},{15 minutes after the hour}],XMLElement[suggested_pickup_period,{},{60}],XMLElement[location,{},{Oakland, CA}],XMLElement[station_id,{},{KOAK}],XMLElement[latitude,{},{37.7}],XMLElement[longitude,{},{-122.22}],XMLElement[observation_time,{},{Last Updated on Apr 11 2012, 12:53 pm PDT}],XMLElement[observation_time_rfc822,{},{Wed, 11 Apr 2012 12:53:00 -0700}],XMLElement[weather,{},{Mostly Cloudy}],XMLElement[temperature_string,{},{60.0 F (15.6 C)}],XMLElement[temp_f,{},{60.0}],XMLElement[temp_c,{},{15.6}],XMLElement[relative_humidity,{},{62}],XMLElement[wind_string,{},{Southwest at 13.8 MPH (12 KT)}],XMLElement[wind_dir,{},{Southwest}],XMLElement[wind_degrees,{},{220}],XMLElement[wind_mph,{},{13.8}],XMLElement[wind_gust_mph,{},{0.0}],XMLElement[wind_kt,{},{12}],XMLElement[wind_gust_kt,{},{0}],XMLElement[pressure_string,{},{1014.2 mb}],XMLElement[pressure_mb,{},{1014.2}],XMLElement[pressure_in,{},{29.95}],XMLElement[dewpoint_string,{},{46.9 F (8.3 C)}],XMLElement[dewpoint_f,{},{46.9}],XMLElement[dewpoint_c,{},{8.3}],XMLElement[windchill_string,{},{58 F (14 C)}],XMLElement[windchill_f,{},{58}],XMLElement[windchill_c,{},{14}],XMLElement[visibility_mi,{},{10.00}],XMLElement[icon_url_base,{},{http://weather.gov/images/fcicons/}],XMLElement[two_day_history_url,{},{http://www.weather.gov/data/obhistory/KOAK.html}],XMLElement[icon_url_name,{},{bkn.jpg}],XMLElement[ob_url,{},{http://www.weather.gov/data/METAR/KOAK.1.txt}],XMLElement[disclaimer_url,{},{http://weather.gov/disclaimer.html}],XMLElement[copyright_url,{},{http://weather.gov/disclaimer.html}],XMLElement[privacy_policy_url,{},{http://weather.gov/notice.html}]}
*)

Answer 1

The reason your approach fails is because Cases works slightly differently than what you've intended in the question. Cases does a depth-first scanning and once it finds its first match, it transforms it and starts traversing the tree backwards, looking for other matches. Consider this simple example:

list = {p[1, 2], q, {p[3, 4], p[5, p[6, 7]]}};
Cases[list, p[a_, b_] :> f[a, b], Infinity]
(* Out[1]= {f[1, 2], f[3, 4], f[6, 7], f[5, p[6, 7]]} *)

You can see that all 4 instances of p[_, _] are found by Cases, but the rule replacement is only done to the output before returning — i.e., the tree is not modified in place — so when it walks back up a node, it does not see the replacement to the deeper p[_, _] because the tree was never modified.

The TreeForm below gives an idea of how the last two matches are handled. The third match is the deepest one, p[6, 7] which returns f[6, 7] and in the second one, the one just above it is matched without modifying the inner p[_, _] (because that's the replacement rule given).

This is exactly the case in your situation, where one XMLElement has another within it.

One possible solution is to extract them all first with Cases and then use ReplaceRepeated:

Cases[list, _p, Infinity] //. p[a_, b_] :> f[a, b]
(* Out[2]= {f[1, 2], f[3, 4], f[6, 7], f[5, f[6, 7]]} *)

So for the example in the question, it would be:

Cases[Import["http://www.weather.gov/data/current_obs/KOAK.xml","XMLObject"],
XMLElement, _XMLElement, Infinity] //. XMLElement[tag:_, _, value:_] :> (tag -> value)

---

As Albert Retey rightly points out (also, thanks to him for the helpful suggestions and corrections), what Cases does with a rule replacement is the same as Cases with no rule, followed by ReplaceAll:

Cases[list, _p, Infinity] /. p[a_, b_] :> f[a, b]

whereas ReplaceRepeated is what's needed here.

Answer 2

Mathematica does match all instances. There is, however, one XMLElement (current_observation) that contains all other XMLElements. So after the deepest XMLElements are matched MMA goes one step up and matches the containing XMLElement, which is then returned, and it shows the other XMLElements.

A simple example:

Cases[
 {XMLElement["test", "BlahBlah", 
     {XMLElement["YAT", "Rubarber", "Ajax"], XMLElement["YATT", {}, "pipo"]}
  ]},
 XMLElement[tag : _, _, value : _] :> (tag -> value), Infinity
 ]

(*
==> {"YAT" -> "Ajax", "YATT" -> "pipo", 
 "test" -> {XMLElement["YAT", "Rubarber", "Ajax"], 
   XMLElement["YATT", {}, "pipo"]}}
*)

If you want to get rid of the highest XMLElement change the levelspec to a range excluding the top level:

Cases[
 {XMLElement["test", 
   "BlahBlah", {XMLElement["YAT", "Rubarber", "Ajax"], 
    XMLElement["YATT", {}, "pipo"]}]},
 XMLElement[tag : _, _, value : _] :> (tag -> value), {2, Infinity}
 ]

(*
==> {"YAT" -> "Ajax", "YATT" -> "pipo"}
*)

To answer your comment: you can get rid of all occurrences of XMLElement using Replace:

Column@Replace[
  Cases[Import["http://www.weather.gov/data/current_obs/KOAK.xml", 
    "XMLObject"], XMLElement[tag : _, _, value : _] :> (tag -> value),
    Infinity],
  XMLElement[tag : _, _, value : _] :> (tag -> value), Infinity
  ]