# How to debug this failing pattern-matching expression?

NB: this question is primarily about troubleshooting and debugging, and only secondarily about pattern-matching. IOW, I'm far less interested in getting an explanation for the situation described below than in learning ways to figure out the explanation by myself.

Below, the same expression is matched against two nearly identical patterns. I don't understand why only the first one of these matches succeeds.

Clear[f];

MatchQ[
RuleDelayed[HoldPattern[f[0]], 0],
HoldPattern[RuleDelayed[HoldPattern[_], _?AtomQ]]
]
(* True *)

MatchQ[
RuleDelayed[HoldPattern[f[0]], 0],
HoldPattern[RuleDelayed[HoldPattern[f[_]], _?AtomQ]]
]
(* False *)


I'm looking for tools/procedures/techniques for debugging this sort of problem systematically.

(I did try Trace, but it told me nothing.)

• To match the head HoldPattern, use Verbatim in the pattern form: Verbatim[HoldPattern][f[_]]. Jul 8, 2015 at 1:47

If your pattern is not very big, you could use "brute force". Replace a sub-pattern with more general sub-pattern and check whether pattern matches expression. Repeat it with some subset of possible sub-patterns.

This task can be automated using following function. It returns list of pairs. First element of pair is rule replacing position of sub-pattern with more general sub-pattern, second element of pair is held expression matched by replaced sub-pattern.

ClearAll[intInf, matchQDebug]
intInf = _Integer | Infinity;

Options[matchQDebug] = {
"ReplacedPattern" -> _,
"ReplacementPatterns" -> {_, __, ___}
};

matchQDebug[
expr_,
patt_,
Repeated[intInf | {Repeated[intInf, {1, 2}]}, {0, 1}],
Repeated[intInf, {0, 1}],
OptionsPattern[{matchQDebug, Position}]
] /;
MatchQ[expr, patt] = \$Failed;

matchQDebug[
expr_,
patt_,
levelspec : intInf | {Repeated[intInf, {1, 2}]} : {0, Infinity},
n : intInf : Infinity,
opts : OptionsPattern[{matchQDebug, Position}]
] :=
Module[{replPatts = OptionValue["ReplacementPatterns"], tag, name},
Cases[
Position[
patt,
OptionValue["ReplacedPattern"],
levelspec,
FilterRules[{opts}, Options[Position]]
] // Sort
,
pos_ :>
With[
{
matchedReplPatt =
SelectFirst[
replPatts,
MatchQ[expr, ReplacePart[patt, {pos} -> #]] &,
tag
]
}
,
{
{pos} -> matchedReplPatt,
Replace[
expr,
ReplacePart[patt, {pos} -> Pattern[name, matchedReplPatt]] :>
HoldComplete[name]]
} /; matchedReplPatt =!= tag
]
,
{1}
,
n
]
]


matchQDebug used on expression and failing pattern from question gives:

matchQDebug[HoldPattern[f[0]] :> 0, HoldPattern[HoldPattern[f[_]] :> _?AtomQ]]
(* {
{{{}} -> _, HoldComplete[HoldPattern[f[0]] :> 0]},
{{{1}} -> _, HoldComplete[HoldPattern[f[0]] :> 0]},
{{{1, 1}} -> _, HoldComplete[HoldPattern[f[0]]]},
{{{1, 1, 0}} -> _, HoldComplete[HoldPattern]},
{{{1, 1, 1}} -> _, HoldComplete[HoldPattern[f[0]]]},
{{{1, 1, 1, 0}} -> _, HoldComplete[HoldPattern]}
} *)


Which means that e.g. replacing part {1, 1, 1}, of given pattern, with _ will result in pattern that matches given expression. Substituted _ will match HoldPattern[f[0]] sub-expression. This output is not easy to read, so let's add some pretty-printing functions.

ClearAll[partRules]
partRules[{{}} -> extracted_List] := {{}} -> First[extracted]
partRules[part_: {__List} -> extracted_List] := Thread[part -> extracted]
partRules[rule_] := rule

ClearAll[stylePart]
stylePart[expr_, part_, styleSpec__] :=
ReplacePart[
expr,
partRules[part ->
Extract[
expr,
part,
Function[x, Style[HoldForm[x], styleSpec], HoldFirst]
]
]
]

ClearAll[matchQDebugTableForm]
matchQDebugTableForm[
expr_,
patt_,
levelspec : intInf | {Repeated[intInf, {1, 2}]} : {0, Infinity},
n : intInf : Infinity,
opts : OptionsPattern[{matchQDebug, Position}]
] :=
TableForm[
{
stylePart[patt, First[#1], Red],
ReplacePart[patt, MapAt[Style[#, Red] &, #1, {2}]],
HoldForm @@ #2
} & @@@
matchQDebug[expr, patt, levelspec, n, opts]
,
None,
{"Original pattern", "Matching pattern", "Expression matched by sub-pattern"}
}
]


Pretty-printed result for expression and pattern from question:

matchQDebugTableForm[
HoldPattern[f[0]] :> 0,
HoldPattern[HoldPattern[f[_]] :> _?AtomQ]
]


In first column we see original pattern, with part that needs to be replaced marked in red. In second column we have patterns after replacement with replaced sub-pattern marked in red. In third column are expression matched by replaced sub-pattern.

This won't tell you what precisely is "wrong" with your pattern, but it shows where to look for possible defects.

In third line from the end we can see that replacing inner HoldPattern, in original pattern, with _ causes pattern to match, _ sub-pattern matches HoldPattern head from expression. Without above replacement pattern does not match, so we see that HoldPattern used in pattern does not match HoldPattern from expression.

In second line from the end we see that replacing f[_] from pattern with _ causes pattern to match, _ sub-pattern matches whole HoldPattern[f[0]] not only f[0] which is another hint that HoldPattern from pattern does not match HoldPattern from expression.

Similar thing can be concluded from last line. _ inside inner HoldPattern in matching pattern matched HoldPattern from expression, which means that inner HoldPattern from pattern didn't match HoldPattern from expression.