replacement - Safely nesting RuleDelayed

Say I have the following, straightforward-seeming functions:

makeARuleDelayed[a_, b_] :=
 With[{anotherRule = makeAnotherRuleDelayed[b]},
  v : a[b] :> ((v == 1 - v) /. anotherRule)];

makeAnotherRuleDelayed[x_] :=
  v : h_[x] :> foo[h, x];

If I use them to create a RuleDelayed, I get an error message:

a[b] /. makeARuleDelayed[a, b]

RuleDelayed::rhs: Pattern v$:h$_[b] appears on the right-hand side of rule v$:a[b]:>(v$==1-v$/. v$:h$_[b]:>foo[h$,b]) .

Examining the result indicates the problem:

v$ : a[b] :> (v$ == 1 - v$ /. v$ : h$_[b] :> foo[h$, b])

Using this rule fails in about the way you'd expect it to. The only workaround I could think of is adding a Module to the body of makeAnotherRule:

makeAnotherRuleDelayed[x_] :=

 Module[{v},
  v : h_[x] :> foo[h, x]]

This doesn't help at all; evidently there must be some sort of magical renaming going on somewhere inside of RuleDelayed that truncates the $nnn part of the name of the symbol generated by Module.

Without being able to nest rules without name clashes, I'm not sure how to go about creating nontrivial rules programmatically.

Answer

This is a renaming mechanism at work. I think, the "canonical" way to fool it is something like this:

makeARuleDelayed[a_, b_] :=
  With[{anotherRule = makeAnotherRuleDelayed[b]},
     v : a[b] :> ((v == 1 - v) /. anotherRule)];


makeAnotherRuleDelayed[x_] :=
  RuleDelayed @@ Hold[v : h_[x], foo[h, x]];

By using RuleDelayed@@Hold, we fool the renaming mechanism of With. Note that this whole issue is because With is a scoping construct which cares about inner scoping constructs and possible name collisions. You can use rules instead, which are much more intruding:

Clear[makeARuleDelayedAlt];
makeARuleDelayedAlt[a_, b_] :=
    v : a[b] :> ((v == 1 - v) /. makeAnotherRuleDelayed[b])

and then keep the original definition for makeAnotherRuleDelayed. I discussed these issues in more detail here.