Re: Associative arrays and memory

Re: Associative arrays and memory

[Sven Wischnowsky]

Bart Schaefer wrote:

> ...
> 
> On Nov 16, 10:54am, Sven Wischnowsky wrote:
> } Subject: Re: Associative arrays and memory
> }
> } (Every time I think about this I can't help remembering the discussion 
> } about a new option system, am I the only one?)
> 
> You are not.  However, I thought the "new options system" mainly meant
> new syntax for "namespaces"?  In which case it doesn't really help with
> any of these questions about special parameters.  It could remove one
> level of indirection in the save/restore loops, I guess.
> 

Yep. This is just another place where I could imagine assoc arrays to
be used.

> ...
>
> The problem (with or without your magic [(x)...] syntax) is that an
> associative array is unordered, but presumably we want some fixed order
> to the interpretation of completions when multiple patterns match the
> command.  (If we're using an associative array for completions, how do
> you implement the equivalent of the -tc option?)

Right, I forgot about that.

> } (the question is: are there other uses
> } where such a feature might be interesting to have
> 
> I think for a shell-script-level feature, this has gone over the edge of
> reasonable complexity.  If perl doesn't have this feature, we should avoid
> it too. :-}
> 
> } and: if we have a
> } way to get a list of matching entries, should we make this with a new
> } modifier flag that can be combined with `i', `I', `r', and `R' so that 
> } all of them give a list, not only the first matching one?).
> 
> Maybe it's because it's 4:30am, but I don't understand that part at all.

I was thinking about something like the `g' history modifier:

  % typeset -A foo
  % foo[a]=hello
  % foo[b]=world
  % echo $foo[(i)?]
  a
  % echo $foo[(r)*l*]
  hello
  % echo $foo[(xi)*l*]
  a b
  % echo $foo[(xr)*l*]
  hello world

As a side effect, we could use `$foo[(xi)*]' instead of `${(k)foo}'
but the latter would still be faster.

Bye
 Sven


--
Sven Wischnowsky                         wischnow@informatik.hu-berlin.de

Re: Associative arrays and memory

[Bart Schaefer]

On Nov 16, 10:54am, Sven Wischnowsky wrote:
} Subject: Re: Associative arrays and memory
}
} (Every time I think about this I can't help remembering the discussion 
} about a new option system, am I the only one?)

You are not.  However, I thought the "new options system" mainly meant
new syntax for "namespaces"?  In which case it doesn't really help with
any of these questions about special parameters.  It could remove one
level of indirection in the save/restore loops, I guess.

} Two more things about assoc arrays:
} 
}   typeset -A foo
}   foo[hello]=world
}   echo $foo[(i)w*]
} 
} gives `1', this should be `hello'.

Yes, I wondered about this.  (Does ksh93 have any equivalent syntax?)
The problem at present is that $foo is the array of values, not of both
values and keys.  So for example:

	% bar=($foo)
	% echo $bar[$foo[(i)w*]]
	hello

That would fail if $foo[(i)w*] substituted "hello" instead of "1".
(Actually, there appears to be a bug in this code; the correct index is
not always substituted.  Patch hopefully to follow.)

Then there are these examples:

	% echo ${(k)foo[@]}
	hello
	% echo ${(k)foo[(i)h*]}
	1
	% echo $foo[(kv)*]
	hello world
	% echo $foo[(kvi)w*]
	2

} And if we use an assoc array for completion command name patterns we
} would need pattern matching the other way round: the keys are taken as 
} patterns and `$funcs[(x)$cmdstr]' (for some value of `x') should give
} the values of all entries whose key (taken as a pattern) match the
} value of $cmdstr.  But of course we could use a simple array for the
} patterns and loop through it

I was planning to add something using the hashtable pattern interface to
take the input key as a pattern and return the values whose keys match,
but I wasn't thinking of turning it inside out like that.

I think the way I'd do the above would be the (equivalent of the) loop:
	for pat in ${(k)funcs[@]}
	do
	    if [[ $cmdstr = $pat ]]
	    then
	    	completions=($completions $funcs[$pat])
	    fi
	done

The problem (with or without your magic [(x)...] syntax) is that an
associative array is unordered, but presumably we want some fixed order
to the interpretation of completions when multiple patterns match the
command.  (If we're using an associative array for completions, how do
you implement the equivalent of the -tc option?)

} (the question is: are there other uses
} where such a feature might be interesting to have

I think for a shell-script-level feature, this has gone over the edge of
reasonable complexity.  If perl doesn't have this feature, we should avoid
it too. :-}

} and: if we have a
} way to get a list of matching entries, should we make this with a new
} modifier flag that can be combined with `i', `I', `r', and `R' so that 
} all of them give a list, not only the first matching one?).

Maybe it's because it's 4:30am, but I don't understand that part at all.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Re: Associative arrays and memory

[Sven Wischnowsky]

Peter Stephenson wrote:

> ...
>
> So, the question is are there any uses for special hashes which would
> require tying them directly to an internal variable or function, or
> can they always be accessed by the standard parameter functions?  I
> would think the whole point of using assoc arrays is to avoid any
> unpleasantness of the former kind.  Probably Sven can answer that
> better than anyone.

When thinking about using assoc. arrays for completion (and zle
widgets) I think of two uses: the one Bart mentioned in his reply
(`zle[...]') for access to various zle internals and one for the
mapping of command strings or environments to function( name)s which
produce the matches. The second one would be fully user-controlled (in 
the sense that the user might use it if (s)he wishes but the
completion code wouldn't enforce it). Hence this one would make no
trouble.
The first use might cause some trouble, you already described the
current use of LBUFFER and so on. For the completion stuff I'm not yet 
sure if we really need/should have settable parameters. If they are
settable it shouldn't be too hard to access their values via the
normal parameter interface (although making them special would
probably make things cleaner and easier to add the new things we may
one day find interesting).

So, I would like to reduce it to the question if we should use an
assoc array for the zle information or not. Using an assoc array only
for this may look a bit queer unless we use them in other places, too.
(Every time I think about this I can't help remembering the discussion 
about a new option system, am I the only one?)

Two more things about assoc arrays:

  typeset -A foo
  foo[hello]=world
  echo $foo[(i)w*]

gives `1', this should be `hello'.

And if we use an assoc array for completion command name patterns we
would need pattern matching the other way round: the keys are taken as 
patterns and `$funcs[(x)$cmdstr]' (for some value of `x') should give
the values of all entries whose key (taken as a pattern) match the
value of $cmdstr. But of course we could use a simple array for the
patterns and loop through it (the question is: are there other uses
where such a feature might be interesting to have, and: if we have a
way to get a list of matching entries, should we make this with a new
modifier flag that can be combined with `i', `I', `r', and `R' so that 
all of them give a list, not only the first matching one?).

Bye
 Sven


--
Sven Wischnowsky                         wischnow@informatik.hu-berlin.de

Re: Associative arrays and memory

[Peter Stephenson]

"Bart Schaefer" wrote:
> Of course, a non-special associative array can contain special parameters.
> That was part of the idea of using a parameter hash as the implementation.
> And that would be the way to do it, rather than make the associative array
> itself special.

OK, I missed this point, then you're stuck with something of the
complexity of what you had if you want to restore it.  But what's
wrong with making the associative array special?  It could do some
sort of dispatch based on the values of the hash it stored.  Then you
could get away with doing only a shallow save of the assoc array at
this point (but see below), i.e. pretty much like what happens with
other special parameters.

Possibly in practice the parent AA will have to be marked as special,
even if its own functionality is as normal.  The alternatives to that
are (1) check all non-special AA's for special contents at the point
in question, which probably isn't on (2) the elements of the AA stop
being special, which is a bit counterintuitive.

> It doesn't matter that a whole array is being assigned to the hash, does
> it?  Even creating a scalar with the same parameter name would require
> that it be saved/restored.

That's true if the assoc array is not special, but its elements are.
If the AA is itself special, it retains that behaviour on set/restore.
Consider
   PATH=foo:bar builtin_or_func
--- here PATH still works the same way as always, just with special
save/restore.  Then assigning a scalar to zle would give some kind of
error.

> So the question is, should it ever be the case that
> 
>     zle=(? BUFFER "this is the command line" ... ?) builtin_or_func
> 
> causes the old command line to be restored following builtin_or_func?
> And if we save and restore such a hash by the simple stacking method, is
> $zle[BUFFER] going to give the right thing after builtin_or_func?

If the bits of the AA are special, and you want to restore them, then
as I said above it seems you'll need the full complexity of the
copyarams() mechanism because you can't guarantee restoring the state
otherwise.  Should it work?  Probably yes.  At some stage we will want
whole assoc array assignments like 'hash2=$hash1', which presumably
requires something like copyparams() anyway.  Maybe I'll just have to
bit the bullet and check for memory leaks properly :-(.

-- 
Peter Stephenson <pws@ibmth.df.unipi.it>       Tel: +39 050 844536
WWW:  http://www.ifh.de/~pws/
Dipartimento di Fisica, Via Buonarroti 2, 56100 Pisa, Italy

Re: Associative arrays and memory

[Bart Schaefer]

On Nov 14,  4:26pm, Peter Stephenson wrote:
} Subject: Re: Associative arrays and memory
}
} "Bart Schaefer" wrote:
} > zagzig<17> HISTSIZE=1000 
} > zagzig<18> HISTSIZE=0 echo hello
} > hello
} > zagzig<19> echo $HISTSIZE
} > 2
} 
} This seems to be OK after restoring the old behaviour, so I haven't
} look further into what had gone wrong.

I found it ... the assignment "pm = tpm;" was mistakenly deleted from
below the code that was replaced by the call to copyparam().  That is,
in save_params() in exec.c, it should look like

	tpm->nam = s;
	copyparam(tpm, pm);
	pm = tpm;

So copyparam() itself is OK.

} > } There are currently no special assoc arrays, of course, and it should
} > } probably be possible to prevent there being any
} > 
} > What about the discussion that started all this -- using an associative
} > array to give user access to shell-internal completion data?
} 
} Rats, I just looked at zle_params.c and you're right --- they're
} marked special.

Of course, a non-special associative array can contain special parameters.
That was part of the idea of using a parameter hash as the implementation.
And that would be the way to do it, rather than make the associative array
itself special.

} That doesn't mean assoc arrays need to be the same, though.  The case
} that needs worrying about is the following:
} 
}   hash=(?...?) builtin_or_func
} 
} where the ?...? represents whatever we pick for whole array
} assignments.

It doesn't matter that a whole array is being assigned to the hash, does
it?  Even creating a scalar with the same parameter name would require
that it be saved/restored.

Or are you talking *about* special parameters within the associative array
that need to be saved, and that's why whole-array assignment would matter?

} There's also no problem if the hash is simply used for storing
} information and is not tied to special variables or functions.  You
} only need a special mechanism for restoration for something like
} $path, where there's an internal variable that needs setting; simply
} restoring the struct param won't do that.

That is, you need to call the pm->sets functions when restoring specials,
which is what restore_params() does.  But my implementation does not call
anything equivalent to restore_params() on the parameter table stored in
the association, so it isn't helping to have save_params() copy it in the
first place.

} If we can agree that use of
} assoc arrays is simply going to be by direct access to the parameter
} we can avoid ever copying it: the above shell pseudocode simply makes
} the supplied $hash available for the duration of builtin_func.

I'm not entirely sure what you mean about "direct access."  If we're
going to put stuff like the present $BUFFER into an association, it needs
to be the case that assignment to (say) zle[BUFFER] actually modifies the
line editor state.

So the question is, should it ever be the case that

    zle=(? BUFFER "this is the command line" ... ?) builtin_or_func

causes the old command line to be restored following builtin_or_func?
And if we save and restore such a hash by the simple stacking method, is
$zle[BUFFER] going to give the right thing after builtin_or_func?

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Re: Associative arrays and memory

[Peter Stephenson]

"Bart Schaefer" wrote:
> } It does seem the existing ztrdup()'s in what's now copyparam() are
> } memory leaks.  This will need fixing in any case, independently from
> } assoc arrays.
> 
> I'm not so sure any more.  When restore_params() is called, it uses the
> pm->sets functions to assign directly to the struct param already in the
> paramtab.  So that memory is now owned by the paramtab and should be
> freed when the param next becomes unset ... right?

Yes, it looks like you're right.  Maybe it's still unnecessarily
confusing.  The struct param is really just a placeholder with a type
flag for the real information.

> zagzig<17> HISTSIZE=1000 
> zagzig<18> HISTSIZE=0 echo hello
> hello
> zagzig<19> echo $HISTSIZE
> 2

This seems to be OK after restoring the old behaviour, so I haven't
look further into what had gone wrong.

> } There are currently no special assoc arrays, of course, and it should
> } probably be possible to prevent there being any
> 
> What about the discussion that started all this -- using an associative
> array to give user access to shell-internal completion data?

Rats, I just looked at zle_params.c and you're right --- they're
marked special.  I had wrongly assumed it was just a case of setting
the value at the start and using it at the end, but there tied to
functions.

That doesn't mean assoc arrays need to be the same, though.  The case
that needs worrying about is the following:

  hash=(?...?) builtin_or_func

where the ?...? represents whatever we pick for whole array
assignments.  If there is none, there's no problem; that's the only
case where copying parameters is necessary.

There's also no problem if the hash is simply used for storing
information and is not tied to special variables or functions.  You
only need a special mechanism for restoration for something like
$path, where there's an internal variable that needs setting; simply
restoring the struct param won't do that.  If we can agree that use of
assoc arrays is simply going to be by direct access to the parameter
we can avoid ever copying it: the above shell pseudocode simply makes
the supplied $hash available for the duration of builtin_func.  It
would certainly keep things much simpler, and I can provide a patch
straight away.

So, the question is are there any uses for special hashes which would
require tying them directly to an internal variable or function, or
can they always be accessed by the standard parameter functions?  I
would think the whole point of using assoc arrays is to avoid any
unpleasantness of the former kind.  Probably Sven can answer that
better than anyone.

-- 
Peter Stephenson <pws@ibmth.df.unipi.it>       Tel: +39 050 844536
WWW:  http://www.ifh.de/~pws/
Dipartimento di Fisica, Via Buonarroti 2, 56100 Pisa, Italy

Re: Associative arrays and memory

[Bart Schaefer]

On Nov 13,  5:16pm, Peter Stephenson wrote:
} Subject: Associative arrays and memory
} 
} It does seem the existing ztrdup()'s in what's now copyparam() are
} memory leaks.  This will need fixing in any case, independently from
} assoc arrays.

I'm not so sure any more.  When restore_params() is called, it uses the
pm->sets functions to assign directly to the struct param already in the
paramtab.  So that memory is now owned by the paramtab and should be
freed when the param next becomes unset ... right?

} However, it looks like the only purpose of copyparam() is simply to
} save special parameters and only in the following case:
}   foo=bar some-builtin
} to restore $foo (it's separate from the usual local restore mechanism).

I appear to have broken it somehow, then:

zagzig<17> HISTSIZE=1000 
zagzig<18> HISTSIZE=0 echo hello
hello
zagzig<19> echo $HISTSIZE
2

Nonspecial variables work:

zagzig<23> FOO=before
zagzig<24> FOO=after echo hello
hello
zagzig<25> echo $FOO
before

} There are currently no special assoc arrays, of course, and it should
} probably be possible to prevent there being any

What about the discussion that started all this -- using an associative
array to give user access to shell-internal completion data?

} So I'd recommend removing all references to assoc
} arrays from copyparam(), i.e. putting that part of the code back how
} it was, maybe with a
}   DPUTS(PM_TYPE(pm->flags) == PM_HASHED, "attempt to copy assoc array")
} to be on the safe side.
} 
} Combining that with my other suggestion of separating assoc array
} returns out of getaparam() would be a big help in warding off possible
} memory leaks.  (Unless `shift hash', which is where getaparam() comes
} in, is really supposed to work? It does something at the moment, but
} what does it mean --- randomly remove element from hash??  Same goes
} for the call in `set -A': there's no point getting an array only to
} find you can't set it because it's the wrong type.)

If you have time and inclination, please go ahead and do this.  I'm not
going to be able to work on it again until tomorrow at the earliest.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Associative arrays and memory

[Peter Stephenson]

"Bart Schaefer" wrote:
> What I'm worried about is that copyparam() uses PERMALLOC, but I think
> the pointers that it returns are being placed in a heap-allocated array
> in some cases.  There's also a ztrdup() in scancopyparams().  MUSTUSEHEAP
> wouldn't report either problem.  This would come up e.g. when you have a
> local with the same name as an existing hash, so you have to save and
> restore the hash.

It does seem the existing ztrdup()'s in what's now copyparam() are
memory leaks.  This will need fixing in any case, independently from
assoc arrays.

However, it looks like the only purpose of copyparam() is simply to
save special parameters and only in the following case:
  foo=bar some-builtin
to restore $foo (it's separate from the usual local restore mechanism).
There are currently no special assoc arrays, of course, and it should
probably be possible to prevent there being any --- the fact that the
shell uses a parameter doesn't make it special, it's only necessary
when the parameter has an otherwise inappropriate relationship with a
shell variable, that's why a lot of parameters have recently been
despecialised.  So I'd recommend removing all references to assoc
arrays from copyparam(), i.e. putting that part of the code back how
it was, maybe with a
  DPUTS(PM_TYPE(pm->flags) == PM_HASHED, "attempt to copy assoc array")
to be on the safe side.

As an aside, the ordinary `local' mechanism never deletes or copies
anything, it just stacks the old parameters.  So there shouldn't be
any big issues there.

Combining that with my other suggestion of separating assoc array
returns out of getaparam() would be a big help in warding off possible
memory leaks.  (Unless `shift hash', which is where getaparam() comes
in, is really supposed to work? It does something at the moment, but
what does it mean --- randomly remove element from hash??  Same goes
for the call in `set -A': there's no point getting an array only to
find you can't set it because it's the wrong type.)

Taking this all into account, I don't believe proper use of assoc
arrays is going to cause memory leaks, even at present.  Ensuring
improper use doesn't either is the hard part.

-- 
Peter Stephenson <pws@ibmth.df.unipi.it>       Tel: +39 050 844536
WWW:  http://www.ifh.de/~pws/
Dipartimento di Fisica, Via Buonarroti 2, 56100 Pisa, Italy