Trace works differently with different right-hand-side rules—bug?

Question

Bug introduced in 2.1 or earlier and persisting through 13.2

UPDATE: Wolfram Support has confirmed that this is a bug.

---

I noticed that Trace does the following strange thing (v 13.0.0.0):

Trace[a*a*2, x_ :> test]
(* Out: {test, test} *)

Trace[a*a*2, x_ :> x]
(* Out: {HoldForm[2*a^2], HoldForm[2*a^2], HoldForm[2*a^2]} *)

The first output has two elements, while the second has three. But shouldn't x_ be matched the same number of times in each?

What might be going on? Is this a bug?

---

Note: the original example used the rule x : Times[___] :> .... As MichaelE2 pointed out, this evaluates to x___ :> ...; in this case, all matched expressions are necessarily exactly one expression long, and so x_ reproduces the same behavior. So, I've modified the example to make it more minimal while still retaining the original character. The responses to this post were made before this edit, and thus may instead use x : Times[___] :> ...

---

Some more facts:

(maybe this should be moved to the community wiki? will re-evaluate in the morning...)

An even more minimal example: Trace[a*a, x_ :> x] returns {a^2, a^2}; Trace[a*a, x_ :> test] returns {}.

A discrepancy only seems to occur when either:

• the evaluation involves downvalues producing an expression which 1) is composite in some way 2) involves "nontrivial" replacement/substitution of patterns

• the evaluation involves rearranging due to an attribute, like Orderless or Flat.

(* easily test for discrepancies—True indicates a discrepancy *)
SetAttributes[DiscrepancyQ, HoldFirst]

DiscrepancyQ[expr_] := 
 Module[{test}, 
  Trace[expr, x_ :> test] =!= (Trace[expr, x_ :> x] /. HoldForm[_] -> test)]

(* Note: subvalues behave like downvalues in all respects that
   I've tested, but I didn't want to write them all out. *)

(* Discrepancies: *)

(* Orderless: *)
Block[{f},
 SetAttributes[f, Orderless];
 DiscrepancyQ[f[2,1]]
]

(* Flat: *)
Block[{f},
 SetAttributes[f, Flat];
 DiscrepancyQ[f[1, f[2]]]
]

(* Downvalues producing "composite" expressions
   and involving replacement are bad, and yield True: *)
Block[{f},
 f[a_] := {a};
 DiscrepancyQ[f[1]]
]

Block[{f},
 f[a_] := a[1];
 DiscrepancyQ[f[1]]
]

Block[{f, h},
 f[a_] := h[a];
 DiscrepancyQ[f[1]]
]

Block[{f},
 f[a_] := (a;1);
 DiscrepancyQ[f[1]]
]


(* No discrepancies: *)

(* Downvalues with no pattern replacement are fine: *)
Block[{f},
 f[a_] := 1;
 DiscrepancyQ[f[1]]
]

(* Downvalues of these particular "purely extractive" forms are fine: *)
Block[{f},
 f[a_] := a;
 DiscrepancyQ[f[1]]
]

Block[{f},
 f[a_, b_] := a; (* or b *)
 DiscrepancyQ[f[1, 2]]
]

(* Upvalues are fine: *)
Block[{a},
 a /: f_[a] := {f, a};
 DiscrepancyQ[f[1]]
]

(* Ownvalues are fine: *)
Block[{f},
 f := {Hold[f], 1};
 DiscrepancyQ[f[1]]
]

Answer 1

CW because it's too long a comment.

A small difference that is not even part of the traced evaluation causes the same behavior as in the OP:

nn = 0;
test := ++nn;  (* <-- the only difference *)
Trace[a*a*2, x : Times[___] :> test]

(*  {1,2,3}  *)

nn = 0;
test := nn;    (* <-- the only difference *)
Trace[a*a*2, x : Times[___] :> test]

(*  {0, 0}  *)

The following shows that it matches three times but only two test show up in the output.

ClearAll[test];
nn = 0;
Trace[a*a*2, x : Times[___] /; (nn++; True) :> test]
nn

(*
  {test, test}

  3
*)

I was trying to figure out which test was dropped in the output, first, second, or third. I couldn't.

I don't completely understand this bullet point from the docs for Trace:

• In general, form in Trace[expr,form] is compared both with each complete expression that is evaluated and with the tag associated with any transformation rule used in the evaluation.

The last half that mentions "transformation rule" would seem to apply to the OP's examples, but I don't know how.

Answer 2

The following shows that the pattern indeed matches and the transformation is applied three times, but one of the results is removed on a postprocessing step inside of Trace:

Reap[Trace[a*a*2, x : HoldPattern[Times[___]] :> (Sow[HoldForm@x]; e)]]

{{HoldForm[e], HoldForm[e]}, {{HoldForm[a*a*2], HoldForm[2*a*a], HoldForm[2*a^2]}}}

I think that this discrepancy already proves that it is a bug.

The parenthesis versus braces difference shown by Michael E2 in the comment sheds some light on the mechanism used for output filtering inside of Trace:

Trace[a*a*2, x : HoldPattern[Times[___]] :> {out}]
Trace[a*a*2, x : HoldPattern[Times[___]] :> {Null; out}]
Trace[a*a*2, x : HoldPattern[Times[___]] -> {Null; out}]
Trace[a*a*2, x : HoldPattern[Times[___]] :> Sequence @@ {out}]

{HoldForm[{out}], HoldForm[{out}]}

{HoldForm[{out}], HoldForm[{out}], HoldForm[{out}]}

{HoldForm[{out}], HoldForm[{out}], HoldForm[{out}]}

{HoldForm[out], HoldForm[out], HoldForm[out]}

Apparently, the filtering depends on whether the final expression has changed upon evaluation, or not.

I reproduce this behavior with Mathematica versions 13.0.0, 8.0.4 and 5.2 on Windows 10 x64.