System`Private`*Entry* and *Valid*, or: How does Mathematica know which expression is which?

Goal

The answers to this question are intended to be a place to describe the behavior and mechanism of the undocumented functions of the form `System`Private`*Entry*` and `System`Private`*Valid*` (and any related functions). This is in somewhat the same style as the `Language`*` documentation project, but much more tightly focused, and maybe without the need to document each function individually (as many seem closely related).

I’m looking for detailed insight into what’s happening internally, as opposed to simply how I might use such functions in an "engineering" way.

Rough Overview

The `*Entry*` functions are used to change (and detect) the way Mathematica traverses an expression, but not an expression "in the abstract" as we’re used to it—an actual, specific instance of an expression in memory(?). Not all `a[1]`‘s are the same!

The `Valid` functions can be used to set an internal flag on the same (and read it).

Are there other functions which ought to be included in this which also modify specific instances of data, or perhaps set different flags other than `Valid`?

If anyone wants to just contribute bits and pieces of knowledge, that’s also welcome! I’ll try to compile any such contributions in a CW and include anything I find out personally.

Motivation

`System`Private`SetNoEntry`

`SetNoEntry` lets us declare a specific instance of a Mathematica expression as atomic (`AtomQ`), and so prevents Mathematica from "entering" the expression somehow (e.g. for part extraction). I was reading this answer by Leonid Shifrin, and this comprehensive answer by Mr. Wizard, and started wondering if there are any systematic rules that tell us when Mathematica considers an expression "the same" internally.

Consider

``t1 = a[1] t2 = t1 t3 = (# &)[t1] Block[{a}, t4 = t1] t5 = ReplacePart[t1, 1 -> 1] t6 = MapAt[Identity, t1, 1]  System`Private`SetNoEntry[t1];  AtomQ /@ {t1, t2, t3, t4, t5, t6, a[1]}  (* Out: {True, True, True, True, True, False, False} *) ``

All of these successfully refer to "the" `a[1]` in `t1`‘s `OwnValues`, except for a different instance of `a[1]`, and one that’s been altered by an evaluation. A close look at the evaluation of `ReplacePart` shows us that it (apparently) determined that the first part of `a[1]` was already `1`, and didn’t re-evaluate `a[1]`; so, it "didn’t change". (A chained, nontrivial `ReplacePart[ReplacePart[t1, 1 -> 0], 1 -> 1]` does indeed change the expression identity, so this isn’t intrinsic to `ReplacePart`.)

So, any complete-enough documentation of the behavior of these functions should be able to at least suggest how to approach the following: how do we check if two expressions are strictly the same internally or not? (Note that `SameQ[t1, a[1]]` gives `True`.)

In the same spirit, it seems that `t1`‘s ownvalues refer to some specific expression in memory, as opposed to simply being a rule that reconstructs an expression. This forces us to expand the "everything is an expression" abstraction a little bit, and makes us ask: when is it detectable that we’re making a reference to a specific data structure in memory? How and when does Mathematica pin down certain expressions in memory, and when are we acting "in place" as opposed to making a copy?

`System`Private`SetValid`

A partial solution for how to check if two expressions are "really" the same is given in this answer by b3m2a1: set a `System`Private`SetValid` flag, and see when it disappears.

Note that these flags seem impervious to `Block`, suggesting, at the very least, that this flag is not among the dynamic properties typically attachable to a symbol:

``Block[{s}, System`Private`SetValid[s]]; System`Private`ValidQ[s] (* Out: True *) ``

One would need to manually extract the state of each of the two expressions under the `ValidQ` functions, clear them both, set the flag of one of them, see if the other has it too, then restore the original `Valid` states. This seems doable, if a little tedious—but is there a better way, which somehow accesses the "identity" of the expression, and provides some insight on what’s going on where?

Function list

Here’s a list of all such functions. Many might be essentially redundant (easily explained based on the behavior of another), but here they all are anyway.

Note: except for `System`Private`ValidMeijerGQ`, which seems unrelated.

`System`Private`*Entry*`

• `System`Private`SetNoEntry`
• `System`Private`EntryQ`
• `System`Private`NoEntryQ`
• `System`Private`HoldSetNoEntry`
• `System`Private`HoldEntryQ`
• `System`Private`HoldNoEntryQ`
• `System`Private`ConstructNoEntry`

`System`Private`*Valid*`

• `System`Private`SetValid`
• `System`Private`ValidQ`
• `System`Private`NotValidQ`
• `System`Private`HoldSetValid`
• `System`Private`HoldValidQ`
• `System`Private`HoldNotValidQ`

The functions here of the form `System`Private`*Hold*` might well be the same as the ones without `Hold` in the name, except for the `HoldAllComplete` attribute, and might just perform the relevant {action on/assignment of flags to} a held argument instead of a fully-evaluated argument. So, they might not need any special treatment or documentation.

Likewise, the `*Q` functions might be straightforward given other info, but it could be a good chance to document under what circumstances they will evaluate to `True`.