Is it possible to specify a context-sensitive, "depth-agnostic" rewrite rule?

Question

I'm using the term "depth-agnostic" in this post to describe structural patterns featuring a "target" sub-pattern that can occur "at any depth" relative to one or more "context" sub-patterns.

As a simple example of a "depth-agnostic" pattern, consider the following rewrite rule:

RR1

replace with the expression WRAP[X] any expression X_TGT contained somewhere within some expression _CTX.¹

Here the target and context sub-patterns are X_TGT and _CTX, respectively. The depth-agnostic bit comes in as the phrase "somewhere within".

In other words, RR1 says to find expressions that look like

… CTX[ … y0[ … y1[ … … yk[ … TGT[ … ] … ] … … ] … ] … ] …

...(where the number of nested subexpressions y0, y1, ..., yk is indeterminate), and rewrite them as

… CTX[ … y0[ … y1[ … … yk[ … WRAP[TGT[ … ]] … ] … … ] … ] … ] …

Thus, if we defined

ping = foo[{1, CTX[bar[2,  3, {TGT[0], 4} ]]}];
ding = foo[{1, CTX[bar[2, {3, {TGT[0], 4}}]]}];
pong = foo[{1, baz[bar[2,  3, {TGT[0], 4} ]]}];

then, according to RR1, ping would be changed to

foo[{1, CTX[bar[2,  3, {WRAP[TGT[0]], 4} ]]}]

...and ding would be changed to

foo[{1, CTX[bar[2, {3, {WRAP[TGT[0]], 4}}]]}]

On the other hand, pong would be unaffected by RR1, even though it contains an expression _TGT, because this expression does not occur "somewhere within an expression _CTX".

The problem is

how to implement a rewrite rule that features such a "depth-agnostic" pattern in Mathematica?

To see why "depth-agnosticity" is an issue, consider rewrite rule RR2 below, identical in every way to RR1, except that it specifies a single, unambiguous depth for the target relative to the context sub-pattern (IOW, it is not "depth-agnostic"):

RR2

replace with the expression WRAP[X] any expression X_TGT contained at a depth of 3 within some expression _CTX.

As shown below, implementing RR2 in Mathematica is straightforward (though, admittedly, a bit tedious), but unfortunately, it is nowhere as general as RR1 (e.g. RR2 affects only ping, not ding).

Here's one (rather uninspired) implementation of RR2 in action:

{ping, ding, pong} /.
  CTX[a1___, h1_[a2___, h2_[a3___, X_TGT, z3___], z2___], z1___] -> 
  CTX[a1, h1[a2, h2[a3, WRAP[X], z3], z2], z1] // TableForm

foo[{1, CTX[bar[2, 3, {WRAP[TGT[0]], 4}]]}]
foo[{1, CTX[bar[2, {3, {TGT[0], 4}}]]}]
foo[{1, baz[bar[2, 3, {TGT[0], 4}]]}]

This implementation fulfills the earlier assertions about RR2: it like RR1 with respect to ping (affects it) and pong (does not affect it), but not with respect to ding (RR1 affects ding but RR2 doesn't).

---

There are at least two important generalizations of the ideas described above. The first one is the situation in which there are multiple context sub-patterns that are themselves at indeterminate depths relative to each other. For example:

RR3

replace with the expression WRAP[X] any expression X_TGT and being contained somewhere within some expression _CTX that is itself contained somewhere within some expression _List.

The second generalization could be expressed as allowing "negative depths", or in other words, patterns in which the context sub-pattern is contained within the target subpattern. For example:

RR4

replace with the expression WRAP[X] any expression X_TGT containing somewhere within it some expression _CTX.

---

^{1In this post I will resort to Mathematica's notation for patterns. Namely, _H denotes a pattern matching any expression having head H, and X_H denotes a pattern matching any expression (henceforth referred to as X) having head H. I will abuse this notation slightly, writing "an expression _H" as shorthand for "an expression matching the pattern _H", and "an expression X_H" as shorthand for "an expression (henceforth referred to as X) matching the pattern _H.)}

Answer 1

ReplaceAll or /., which is what you used, replaces at all levels (or depths). If you need to target a particular level/depth, then use Replace. To target expressions that contain/don't contain a particular term, use FreeQ Here's how you can write your replacement rules for each of the cases (replace expr with whatever you have):

RR1: replace with the expression WRAP[X] any expression X_TGT contained somewhere within some expression _CTX

expr /. x_CTX :>  (x /. TGT :> Composition[WRAP, TGT])

or

expr /. x_CTX :> (x /. y_TGT :> WRAP[y])

---

RR2: replace with the expression WRAP[X] any expression X_TGT contained at a depth of 3 within some expression _CTX.

expr /. x_CTX :> Replace[x, y_TGT :> WRAP[y], {3}]

and similarly using Composition.

---

RR3: replace with the expression WRAP[X] any expression X_TGT and being contained somewhere within some expression _CTX that is itself contained somewhere within some expression _List.

expr /. l_List :> (l /. x_CTX :> (x /. y_TGT :> WRAP[y]))

---

RR4: replace with the expression WRAP[X] any expression X_TGT containing somewhere within it some expression _CTX.

expr /. y_TGT :> WRAP[y] /; ! FreeQ[y, CTX]