General definitions of deeply nested functions without SetDelayed, "UpUpValues"

Question

I'd like to assign an "UpUpValue" in a way generalized to any nested head surrounding the value for which the UpUpValue would be defined. That is, if a function h[x] is called and it is nested within another two functions f[g[h[x]]], I'd like it to have a specific behavior generalizable to any head g.

I had thought this would work:

h /: f[g_[h[x_]]] := (f[x] + g[x] + h[x])

However, TagSetDelayed is limited to 2nd level specification (such that it returns that "TagSetDelayed::tagpos : "Tag h in f[g_[h[x_]]] is too deep for an assigned rule to be found."). I then tried bypassing this by defining it manually using:

UpValues[g] = {HoldPattern[f[h_[g[x]]]] :> HoldPattern[f[x] + h[x] + g[x]]}

However, it seems this does not fire successfully.

The following using UpSetDelayed also doesn't work:

f[g_[h[x_]]] ^:= (f[x] + g[x] + h[x])

As this seeks to apply the rule to specific heads only (not general g that can be used on the RHS).

Can anyone conceive of a way to accomplish this in a way that preserves generality in the head of g? For any single function g, I could simply define an UpValue or DownValue, but I would like to do so in a general way such that it is applied to any function g when it is fed the head h.

Clarification on SetDelayed:

xzczd pointed out that the following would work in principal:

f[g_[h[x_]]] := (f[x] + g[x] + h[x])

However, this associates a DownValue with the symbol f. DownValues are checked exhaustively upon calling a function, such that making many additions to DownValues of a function f that is called many times can become inefficient when compared to making UpValues (or "UpUpValues") associated with a more rarely used function h.

For example, if you wanted to define special handling for 1000 different functions sitting in h's position, this would define 1000 different DownValues of f that must be checked each time f is called, rather than one "UpUpValue" for each unique function sitting in h's spot.

Answer 1

If you can stand a slight tweak:

ClearAll[h];
h /: g_[h[x_]] := h[g, x];
h /: f[h[g_, x_]] := f[x] + g[x] + h[x];
MakeBoxes[h[g_, x_], form_] := MakeBoxes[g[h[x]], form];

f[g[h[x]]]

(*  f[x] + g[x] + h[x]  *)

r[h[y]]
FullForm[%]
f[%%]

(*
  r[h[y]]   <-- Output form 
  h[r, y]   <-- Internal form 
  f[y] + h[y] + r[y]
*)

It's just a bit unclear how this is supposed to work: Just what is h[x]? Does it evaluate to something else or is h inert? Keeping it from evaluating may be hard if g is arbitrary. Consider this simplified example:

ClearAll[hh];
hh /: ff[hh[x_]] := ff[x] + hh[x];
hh[x_] := x^2;

ff[hh[x]]

(*  ff[x^2]  *)

The arguments of ff are evaluated individually before upvalues for hh are searched. The upvalue fails to be applied. However, if ff holds its argument, then the upvalue works:

SetAttributes[ff, HoldAll];
ff[hh[x]]

(*  x^2 + ff[x]  *)

Addendum: Comment on performance

Performance is one on the motivating factors in the OP's desire for an UpUpValue. Let's examine it.

First, make a 1000 symbols to serve as our potential h's.

syms = Table[Unique[], {1000}];
sym0 = syms[[500]]

(*  $591  <-- will vary *)

A comparison of the standard downvalue approach with the upvalue approach above shows that the OP has some justification:

ClearAll[fDown]; ClearAll @@ syms;
(fDown[g_[#[x_]]] := fDown[x] + g[x] + #[x]) & /@ syms;

fDown[Sin[Cos[x]]] // RepeatedTiming
fDown[Sin[sym0[x]]] // RepeatedTiming

(*
  {2.*10^-8, fDown[Sin[Cos[x]]]}
  {0.000068, fDown[x] + Sin[x] + $591[x]}
*)

ClearAll @@ syms;
(# /: g_[#[x_]] := #[g, x];
 # /: fUp[#[g_, x_]] := fUp[x] + g[x] + #[x];) & /@ syms;

fUp[Sin[Cos[x]]] // RepeatedTiming
fUp[Sin[sym0[x]]] // RepeatedTiming

(*
  {3.1*10^-8, fUp[Sin[Cos[x]]]}           <-- same
  {3.1*10^-6, fUp[x] + Sin[x] + $591[x]}  <-- faster
*)

Now, let's consider another downvalue method, which is just as fast as the upvalue method:

ClearAll[fDown2]; ClearAll @@ syms;
SetAttributes[fDown2, HoldAll];
assoc = AssociationThread[syms -> True]; 
fDown2[g_[h_[x_]]] /; Lookup[assoc, h, False] := 
 fDown2[x] + g[x] + h[x];

fDown2[Sin[Cos[x]]] // RepeatedTiming
fDown2[Sin[sym0[x]]] // RepeatedTiming

(*
  {3.1*10^-8, fDown2[Sin[Cos[x]]]}
  {2.2*10^-6, fDown2[x] + Sin[x] + $591[x]}
*)