Some very good points, especially about assignments. It's indeed an aspect that I hadn't considered. Now that you mentioned it, I had a closer look at it, both in the latest zsh (@1706805d4) and in ksh. I have many thoughts and comments but it will require some time to put them into writing. Maybe I can send them tonight, if not hopefully tomorrow.
For now, a few replies to some of your other points.
> Since the raison d'être of the -u option is to support passing variables by name, I'm getting convinced that -u is a property of the reference. And not only that. I'm now also convinced that the lookup should not be performed relative to the scope of where the reference is initialized but relative to where the reference is defined.
I actually implemented this at one point amid the other fixes for this
thread, but abandoned it because it violated your assertions about how
the nr-test output should appear.
Adopting this would not conflict with any of the previous K01 tests
and would appear to offer a compromise: A reference declared with -u
would automatically have "all the way up" behavior, because locallevel
would provide the order of declaration constraint. I have no
objection to adopting this.
Great to hear that. I think that "relative to definition place" rather than "relative to initialization place" makes so much more sense for -u that we should definitely adopt it. Sorry if I missed a proposed patch that did just that. Also, nr-test should definitely NOT be used as a reference of what's most desirable, especially for -u. Iirc, when I created it, -u suffered from bugs that made it behave in ways that looked completely random, even in relatively simple cases. The suggested behavior for nr-test just made it work in a predictable way that also kind of matched what non -u references did, without much regard towards whether that behavior was really useful/meaningful.
> Lastly, again because -u is intended to get access to a variable in the caller's scope, I think that if no variable is found there, it should default to an invalid reference that expends to the empty string or maybe even better to an error and not default, like currently, to whatever, if anything, is found in the current scope.
In any case you're forgetting about assignments.
That's right. We for sure want to support assignments. Should that work for not-yet-defined variables? Ideally, yes. More on that in my upcoming reply. If indeed yes, then obviously "no variable found" should not become an error.
That's not how it currently works. A parameter in the current scope
would be found only if the reference were first defined in a nested
scope to name a parameter that also existed in a (shallower) nested
scope, after which both of those nested scopes return.
That's not true, currently (@1706805d4) a parameter in the local scope is also found even if there are no calls to nested scopes:
() {
# scope with no parameters
() {
local -nu upref=$1
local var=at_upref
print -- $upref
} var
}
Note that this is literally the textbook example of how to use -u but it ends up doing something nonsensical. I thought that was a good reason to report an error for not-yet-defined variables but forgot about assignments. An alternative is to expand to the empty string but still allow assignment (more on that in my upcoming reply). Technically, it just means that for -u named references, when the lookup for var at the lookup scope S fails it returns nothing instead of defaulting to the outermost "var", if any.
> When a function is exited and the scope of named reference is updated because it referred to a local variable of the exited function, should its scope be set to the (new) current scope (i.e., the scope of the calling function) or should it be set all the way up to the scope of the next enclosing rname variable or the global scope if no such variable exists?
>
> The current implementation does the former. I think that the latter would be better.
I've experimented with the latter and concluded that it's just messy
but with no real benefit. It has to be done in two separate passes
over the parameter table so that the exiting scope is fully cleaned up
before any references are updated, it breaks (or at least changes in
what I feel to be confusing ways) the results of the modified nr-test
checks when the stack depth repeatedly grows and shrinks. But the
worst bit is that transitive references ($ref1 -> $ref2 -> $var) can't
be handled independently and appear to need exponentially complex
processing as the chain gets longer.
I disagree on the "with no real benefit". Currently, adding a local "var" in a nested function F can change what a "ref" initialized with "var" refers to in an unrelated nested function G where neither F nor F's "var" were ever visible. That doesn't sound good to me.
With the current implementation (as I understand it), it definitely requires more work than the current solution. Not sure about the two passes. I guess you mean one pass to drop the dead variables and one to update the dangling named references. Two passes look cleaner but one pass would obviously be more efficient. I don't really see why you couldn't combine them. "All the way up" requires updating the lookup scope to the scope of variables found at the scope of the calling function. You can do that even if the parameter table still contains some dead variables from the exited function.
Regarding the worst bit about transitive references, I agree that this looks ugly and I'm still not 100% sure on which starting references need to be considered and how exactly it should work but my impression is that this is orthogonal to whether "all the way up" is adopted or not.
> At any point in time, if ref=var, then consider the innermost scope that was already present when ref was initialized to var,
> - if var was locally defined in that scope before ref was initialized, then ref refers to it,
> - otherwise, ref refers to the first (strictly) enclosing var at that scope, if any and otherwise to the outermost var, if any.
This implies maintaining an order dependency on parameter
declarations, or (equivalently?) a per-reference stack of scopes at
which that reference may be resolved. (The parameter table is an
unordered hash.) I think this is putting too much effort into fixing
an undesirable programming paradigm (to wit, declaring a reference
without knowing where it will be initialized).
If I understand you correctly, then yes, we kind of need a per-reference stack of scopes at which that reference may be resolved. I say kind of because a proxy of that is enough and I think that we already have such a proxy.
My understanding is that the parameter table maps variable names (strings) to variable descriptors (instances of Param). Each Param has a field that contains the depth of the scope in which the variable was defined. Whenever a variable is defined with typeref, the table is looked up. If a Param is found and its scope is the current one, then it's reused (i.e., the new variable overwrites the old Param rather than creating a new Param to replace the old one). Otherwise, if the found Param is from an enclosing scope then a new Param is created with a link to the old Param and inserted into the table to replace the old Param. If no Param is found, a new one is created with no parent Param and inserted into the table.
If all this is indeed correct, then we already have a proxy for the per-reference stack of scopes, namely in the chain of Param instances. That's what I realized when you mentioned "all the way up" as a possible alternative in one of your replies (about nr-test iirc but in relation with -u).
When a function is exited, you look for named references that need to be updated, namely all the ones whose loopup scope has a greater depth that the current scope (the one from the calling function). For all these named references you update the lookup scope to be equal to the new current scope. "All the way up" requires instead to lookup var (in theory after all the variables from the closed scope have been removed, in practice you can just skip over them). If a Param is found, set the lookup scope to the scope of that Param, otherwise set it to the global scope. That's actually exactly the same as what you have to do when ref is initialized for the first time. So, yes, "all the way up" requires more work but it's "just" one extra lookup. No new data structure is needed.
If it is indeed correct that Param instances are reused rather than recreated when a variable is redefined in the same scope then "all the way up" also enables an optimization of named references. I guess that you already know that the current implementation of named references can suffer from slowdowns in some corner cases, namely when the referred variable is buried/hidden under/by many local variables in as many nested scopes. Here is a worst case example:
zmodload zsh/datetime;
function f() {
typeset var=$0;
typeset -n ref=var;
function g() {
local var="$0 $1" val start end;
if (($1 < 10 || $1 % 10 == 0)); then
start=$EPOCHREALTIME
repeat 10000; do
val=$ref$ref$ref$ref$ref$ref$ref$ref$ref$ref;
done;
end=$EPOCHREALTIME;
if ((!warmup)); then
printf "$0 $1: ref=$ref - %.4f\n" $((0.0+end-start));
fi;
fi;
if (($#funcstack < FUNCNEST)); then g $(($1+1)); fi;
}
warmup=1 FUNCNEST=50 g 1; # First round to warmup all CPU caches
warmup=0 FUNCNEST=999 g 1; # Higher values of FUNCNEST hit the recursion limit
}
f;
Output (shortened):
g 1: ref=f - 0.0160
g 2: ref=f - 0.0162
g 3: ref=f - 0.0157
g 4: ref=f - 0.0161
g 5: ref=f - 0.0167
…
g 100: ref=f - 0.0321
…
g 500: ref=f - 0.0997
…
g 990: ref=f - 0.3578
The default FUNCNEST is 500 on my machine. The slowdown is noticeable but probably not something we really need to worry about. However, with a different implementation, it could be entirely avoided and with that implementation "all the way up" becomes trivial.
Each Param corresponding to a named reference stores the depth of the lookup scope. The lookup scope is initially determined by looking up var and using the (definition) scope of the found Param. Each Param corresponding to a named reference could instead store a pointer to the found Param and null if none was found. When a named reference is expanded (or assigned), a lookup is only needed if the linked Param is null. If that lookup is successful, the found Param can be set as the linked Param of the named reference. When a scope is exited and the linked Param was defined in that scope, then it must simply be replaced by its parent Param, if any and null otherwise (no lookup or extra work needed).
With this implementation the deallocation of Param instances of dead variables becomes a little tricker. You would probably have to collect them while traversing the parameter table and only deallocate them at the end. Otherwise when you update a named reference it may link to a Param that has already been deallocated.
This implementation also requires that all hidden dangling references made possible via transitive references are updated. Indeed, failure to do so would now lead to use after free problems, while with the current implementation it only leads to named references referring to incorrect variables. So we either need a solid solution to that problem or a way to avoid the problem entirely.
At the moment, I'm not advocating for that implementation since I don't have a solid solution for hidden dangling references. I mention it because if we can solve that problem, this implementation has the potential of being both cleaner and more efficient.
Philippe