How do I build a position index of a general held expression to arbitrary depth?

I have an expression which I would like to make a position index of, which for sake of argument will be this:

expr = f[q + g[x, y, z]];


Since it's not a list, and I want to build an index at all levels, PositionIndex is not my friend. Still, I have a solution using MapIndexed that's not too terrible and gets me the result I want:

Module[
{index = <||>},
MapIndexed[
(AppendTo[index, #2 -> #1]; #1) &,
expr,
index]

(* <|{0} -> f, {1,0}-> Plus, {1,1} -> q,
{1,2,0} -> g, {1,2,1} -> x, {1,2,2} -> y, {1,2,3} -> z,
{1,2} -> g[x,y,z], {1} -> q+g[x,y,z], {} -> f[q+g[x,y,z]]|>     *)


However, this all goes terribly wrong if I try to index a held expression while keeping things held:

heldExpr = HoldComplete[f[q + g[x, y, z]]];
Module[{index = <||>},
MapIndexed[
(AppendTo[index, #2 -> HoldComplete[#1]]; #1) &,
heldExpr,
index]
(* <|{0} -> HoldComplete[HoldComplete],
{} -> HoldComplete[HoldComplete[((AppendTo[index\$248139, #2 -> HoldComplete[#1]];
[many lines of garble omitted]
*)


I tried the Trott-Strzebonski trick, which did little to improve things:

Module[{index = <||>},
MapIndexed[
With[{eval = (AppendTo[index, #2 -> HoldComplete[#1]]; #1)},
eval /; True] &,
heldExpr,
index]

(*<|{0} -> HoldComplete[HoldComplete],
{1, 0} -> HoldComplete[f], {1, 1, 0} -> HoldComplete[Plus],
{1, 1, 1} -> HoldComplete[q], {1, 1, 2, 0} -> HoldComplete[g],
{1, 1, 2, 1} -> HoldComplete[x], {1, 1, 2, 2} -> HoldComplete[y],
{1, 1, 2, 3} -> HoldComplete[z],
[here's where it starts going wrong]
{1, 1, 2} ->  HoldComplete[(g /; True)[x /; True, y /; True, z /; True]]
[several more elements where non-atomic expressions have sprouted spurious
/; True conditions omitted] |> *)


In principle, I could probably use a rule replacement to strip the /; True stuff, but I don't see a way to do that without destroying legitimate vacuously true conditions (which may well be present in source code for any number of reasons). I suppose I could pre-transform the expression so every True is replaced with a unique symbol and then switch back, but that seems annoying and possibly error prone.

I think, MapIndexed is not really your friend here, because you can't easily force evaluation deep inside held expressions when using the functions of the Map family. The Trott-Strzebonski trick works for rules applied to entire expression, and the way you tried to use that construct could not have worked simply because that was a pure function, not a (r.h.s. of the) rule. OTOH, when rules are applied, they on their own have no information on part's position, which rules out a direct application of TS technique for this problem (pun intended).

Now, to the position index problem proper. I don't see a big advantage in having direct index position -> part, since positions are unique and one can get those parts out simply using Part or Extract. So I will provide a function to build the part -> position-list index, which seems more useful (PositionIndex is doing that too):

positionIndexNested[expr_] :=
{
Extract[Unevaluated @ expr, # , HoldComplete],
#
} & @ Position[Unevaluated @ expr, _]
]


The Unevaluated wrappers were used to enable things like this:

positionIndexNested[Unevaluated[Print[1 + 1, 2 + 2]]]

(*
<|
HoldComplete[Print] -> {{0}},
HoldComplete[Plus] -> {{1, 0}, {2, 0}},
HoldComplete[1] -> {{1, 1}, {1, 2}},
HoldComplete[1 + 1] -> {{1}},
HoldComplete[2] -> {{2, 1}, {2, 2}},
HoldComplete[2 + 2] -> {{2}},
HoldComplete[Print[1 + 1, 2 + 2]] -> {{}}
|>
*)


For the inverse position index (the one you asked for), simply permute the parts of the list inside Thread, namely Extract[...] and #.

There is a way to use MapIndexed to solve this problem, too, but it is way less direct and will effectively just reimplement the above in a more complex way. You basically first use MapIndexed to map some HoldAllComplete custom wrapper / symbol on all parts of the expression, then use Cases to collect all parts and remove the wrapper in their inner parts. I have the code for that, and can add it upon request, but just see no point.

• +1. In a similar vein: Position[expr, _] // Query[Association, # -> Extract[expr, #, HoldComplete] &] Commented Mar 13, 2020 at 23:22
• @WReach Yep, that works too. I instinctively try to avoid Query as I don't view it as a core language construct of the same level as list and assoc operations (i.e. with simple / clear semantics that is guaranteed to stay the same in the future), but I admit that it does sometimes make things a little more concise. Commented Mar 13, 2020 at 23:28
• # -> Extract[expr, #, HoldComplete] & /@ Position[expr, _] // Association if one prefers ;) Commented Mar 13, 2020 at 23:30
• @WReach I certainly do :) Commented Mar 13, 2020 at 23:32