struct environment

struct environment

[David Carlton]

As I e-mailed a couple of weeks ago, I'd like to work on reworking the
namespace support in GDB.  But, before working on namespaces proper,
there's a fair amount of existing code in GDB that is relevant to this
task that I'd like to clean up.  Specifically, I think that namespace
support will be much saner if all existing symbol lookup mechanisms
are unified into some sort of 'environment' interface.

The existing mechanisms in question are:

1) The members 'hashtable', 'nsyms', and 'sym' of 'struct block'.
2) The global environment: global symbols, partial symbols, minimal
   symbols.
3) The members '{n,}fields' in 'struct type'.

Namespaces are similar in many ways to the global environment, so
taming the global environment code will be very helpful when reworking
namespaces.  And once we handle 'using' declarations, symbol lookups
won't always proceed up a straightforward line of inheritance of
blocks that ends in the global environment, so I suspect that having
blocks, the global environment, and namespaces all be accessible via
the same sort of object will make code simpler.  (Exactly why the
third case above should be handled in the same way is another story,
but I don't want to go into that now.)

So I want to add a type 'struct environment' to GDB.  It will be
completely opaque, with a variety of internal implementations
available (similar to the way that 'struct block' allows you to use
either a hash table or a simple list of symbols) sharing a common
external interface.  I want to start by converting 'struct block' over
to using this, then converting the global environment over to using
this, then (probably) 'struct type', and finally getting namespaces to
work well.

I think I'll soon be ready to start converting over 'struct block',
and I'd like feedback from people about whether or not this is a good
idea, and about what the parts of the interface to 'struct
environment' that are relevant to 'struct block' should look like.
Here are some design issues that arise:

* What constructors/destructors should there be?  buildsym.c will need
  constructors that create environments of a fixed size on an obstack
  that are implemented using either a hashtable or a list.  jv-lang.c
  and mdebugread.c both need constructors for environments allocated
  using xmalloc whose final size isn't known initially; these will
  need destructors, and perhaps some sort of 'finalize' function to
  call once we know everything's been added to the environments in
  question.  (I'll look into those situations more closely soon.)

* There needs to be a way to add symbols to an environment while
  constructing it.  Maybe

    void env_add_symbol(struct environment *, struct symbol *);

* There should be a shallow lookup function, i.e. one that looks up a
  symbol just in one environment, without going up to a parent
  environment.  (The latter will get added in once we get to
  converting over the global environment.)  Maybe

    struct symbol *env_lookup_shallow(struct environment *,
                                      const char *);

* There should probably be iterators that allow one to examine every
  symbol in an environment.  One possibility, to save on memory
  management headaches, would be to allow only one active iterator per
  environment, and have that stored as part of the environment; so we
  would have

    struct symbol *env_lookup_first(struct environment *);
    struct symbol *env_lookup_next(struct environment *);

  (Where these return NULL if we've seen all the symbols in the
  environment.)  I'll have to double-check to make sure that existing
  use of iteration over symbols blocks is compatible with this, but
  I'm almost positive it is.

* It's vaguely possible that some code might need to count the number
  of symbols in an environment, but I don't think so; presumably
  that's only used by iterators or by code that could be moved to the
  inside of struct environment.

* When scanning GDB for uses of 'struct block', I noticed that some
  code wants to sort symbols in the block.  I'll have to look at where
  and why that's happening, but I don't think it's anything serious.
  (When it's necessary, it can presumably be added to a 'finalize'
  function as in the discussion of constructors above.)

I think that's about it.

That describes how I would like things to look once I've switched
'struct block' over to using a 'struct environment' member (replacing
its current members 'hashtable', 'nsyms', and 'sym').  And presumably
most or all of this portion of the interface will remain once the
global environment has been converted over, though of course the
interface will grow in order to handle the global environment.

The question remains of how to get from here to there.  I'm pretty
sure that I can convert 'struct block' over to using environments in
an incremental fashion.  Describing that process will take a fair
amount of time, though, so I'll send it in a separate e-mail, probably
some time tomorrow but maybe Monday.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Jacobowitz]

On Thu, Sep 05, 2002 at 01:50:40PM -0700, David Carlton wrote:
> As I e-mailed a couple of weeks ago, I'd like to work on reworking the
> namespace support in GDB.  But, before working on namespaces proper,
> there's a fair amount of existing code in GDB that is relevant to this
> task that I'd like to clean up.  Specifically, I think that namespace
> support will be much saner if all existing symbol lookup mechanisms
> are unified into some sort of 'environment' interface.
> 
> The existing mechanisms in question are:
> 
> 1) The members 'hashtable', 'nsyms', and 'sym' of 'struct block'.
> 2) The global environment: global symbols, partial symbols, minimal
>    symbols.
> 3) The members '{n,}fields' in 'struct type'.
> 
> Namespaces are similar in many ways to the global environment, so
> taming the global environment code will be very helpful when reworking
> namespaces.  And once we handle 'using' declarations, symbol lookups
> won't always proceed up a straightforward line of inheritance of
> blocks that ends in the global environment, so I suspect that having
> blocks, the global environment, and namespaces all be accessible via
> the same sort of object will make code simpler.  (Exactly why the
> third case above should be handled in the same way is another story,
> but I don't want to go into that now.)
> 
> So I want to add a type 'struct environment' to GDB.  It will be
> completely opaque, with a variety of internal implementations
> available (similar to the way that 'struct block' allows you to use
> either a hash table or a simple list of symbols) sharing a common
> external interface.  I want to start by converting 'struct block' over
> to using this, then converting the global environment over to using
> this, then (probably) 'struct type', and finally getting namespaces to
> work well.

Why do you want to have multiple available implementations?  I think
the overhead for always hashing is small enough.  There are only two
reasons struct block allows hash tables or linked lists:
  - overloading of the meaning of that list to represent a list of
    function arguments, which is ordered
  - warts in mdebugread that I was not patient enough to overcome when
    I finally merged in hash table support

I suppose the first reason is a legitimate one for multiple
implementations; we could mark an environment as 'ordered'.  Or we
could stop overloading the meaning of the list that way.  I don't know
which is better.

> I think I'll soon be ready to start converting over 'struct block',
> and I'd like feedback from people about whether or not this is a good
> idea, and about what the parts of the interface to 'struct
> environment' that are relevant to 'struct block' should look like.
> Here are some design issues that arise:
> 
> * What constructors/destructors should there be?  buildsym.c will need
>   constructors that create environments of a fixed size on an obstack
>   that are implemented using either a hashtable or a list.  jv-lang.c
>   and mdebugread.c both need constructors for environments allocated
>   using xmalloc whose final size isn't known initially; these will
>   need destructors, and perhaps some sort of 'finalize' function to
>   call once we know everything's been added to the environments in
>   question.  (I'll look into those situations more closely soon.)

More preferably, just a finalize method that copies them onto the
obstack.  I'm not sure if pointers to symbol entries are saved in the
process of constructing the list, which would make that hard; hopefully
not.

There is no reason to be concerned about performance of the finalize
method in this case.  If someone is concerned they can fix the way
mdebugread generates symbol lists so that it uses the same hash tables
everyone else does.

> * There needs to be a way to add symbols to an environment while
>   constructing it.  Maybe
> 
>     void env_add_symbol(struct environment *, struct symbol *);

Does there?  Right now most lists are constructed first into a pending
list, and only then hashed into an environment.  I'd rather not have to
use growable hash tables.

> * There should be a shallow lookup function, i.e. one that looks up a
>   symbol just in one environment, without going up to a parent
>   environment.  (The latter will get added in once we get to
>   converting over the global environment.)  Maybe
> 
>     struct symbol *env_lookup_shallow(struct environment *,
>                                       const char *);

You may need more information than this.  Sometimes lookup_block_symbol
needs to look up the symbol (i.e. demangled) which has a particular
mangled name - this is a wart and not one I'm fond of but it isn't
quite ready to die yet.

> * There should probably be iterators that allow one to examine every
>   symbol in an environment.  One possibility, to save on memory
>   management headaches, would be to allow only one active iterator per
>   environment, and have that stored as part of the environment; so we
>   would have
> 
>     struct symbol *env_lookup_first(struct environment *);
>     struct symbol *env_lookup_next(struct environment *);
> 
>   (Where these return NULL if we've seen all the symbols in the
>   environment.)  I'll have to double-check to make sure that existing
>   use of iteration over symbols blocks is compatible with this, but
>   I'm almost positive it is.

In most cases yes.  See the ALL_BLOCK_SYMBOLS macro.  There are a
couple of places where I could not use it for some reason, though.

> * It's vaguely possible that some code might need to count the number
>   of symbols in an environment, but I don't think so; presumably
>   that's only used by iterators or by code that could be moved to the
>   inside of struct environment.
> 
> * When scanning GDB for uses of 'struct block', I noticed that some
>   code wants to sort symbols in the block.  I'll have to look at where
>   and why that's happening, but I don't think it's anything serious.
>   (When it's necessary, it can presumably be added to a 'finalize'
>   function as in the discussion of constructors above.)

It's irrelevant - it was only for speeding up searching.  Note that
hashed blocks are never sorted and blocks with a function are never
sorted.  mdebugread-style blocks are simply legacy.

> The question remains of how to get from here to there.  I'm pretty
> sure that I can convert 'struct block' over to using environments in
> an incremental fashion.  Describing that process will take a fair
> amount of time, though, so I'll send it in a separate e-mail, probably
> some time tomorrow but maybe Monday.

Great.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[David Carlton]

Daniel Jacobowitz <drow@mvista.com> writes:
> On Thu, Sep 05, 2002 at 01:50:40PM -0700, David Carlton wrote:

>> So I want to add a type 'struct environment' to GDB.  It will be
>> completely opaque, with a variety of internal implementations
>> available (similar to the way that 'struct block' allows you to use
>> either a hash table or a simple list of symbols) sharing a common
>> external interface.  I want to start by converting 'struct block' over
>> to using this, then converting the global environment over to using
>> this, then (probably) 'struct type', and finally getting namespaces to
>> work well.

> Why do you want to have multiple available implementations?  I think
> the overhead for always hashing is small enough.  There are only two
> reasons struct block allows hash tables or linked lists:
>   - overloading of the meaning of that list to represent a list of
>     function arguments, which is ordered
>   - warts in mdebugread that I was not patient enough to overcome when
>     I finally merged in hash table support

> I suppose the first reason is a legitimate one for multiple
> implementations; we could mark an environment as 'ordered'.  Or we
> could stop overloading the meaning of the list that way.  I don't know
> which is better.

The global block in jv-lang.c may also pose similar problems to those
in mdebugread.c, for what that's worth.  (I'm not sure: it might be
cleaner than mdebugread.c.)  But you've basically put your finger on
it: some blocks currently have a reason to be ordered, and some pieces
of code try to construct the environments on the fly, growing them as
necessary.  Which, incidentally, I don't think we should discourage:
instead of requiring code to calculate the size of environments before
building them, we might as well support environments that can be built
incrementally and then finalized.  That way the common bookkeeping
code gets moved into the environment stuff, so people don't have to
keep on redoing it.

And there's another, even more important reason: the global
environment (and, in the future, namespaces).  The global environment
spans multiple files, uses lazy evaluation (i.e. partial_symbols), and
there's even minimal_symbols to shoehorn in there somehow.  So it's
going to need its own special implementation (which will be much more
complicated than the implementations for blocks).

At some point in the future, it might be possible to use a single
implementation for everything; it would have to support:

* Growing as needed
* Fast lookups
* Being able to retrieve all entries in the order in which they were
  added
* Whatever extra cruft is necessary to support environments like the
  global environment.

This is certainly possible (heaps solve the first two problems, for
example), but I think moving over to a single implementation can and
should be postponed until much later in the game.  It'll be easy
enough to do, if desirable, once existing code gets converted over to
using environments.

>> * What constructors/destructors should there be?  buildsym.c will need
>> constructors that create environments of a fixed size on an obstack
>> that are implemented using either a hashtable or a list.  jv-lang.c
>> and mdebugread.c both need constructors for environments allocated
>> using xmalloc whose final size isn't known initially; these will
>> need destructors, and perhaps some sort of 'finalize' function to
>> call once we know everything's been added to the environments in
>> question.  (I'll look into those situations more closely soon.)

> More preferably, just a finalize method that copies them onto the
> obstack.

Good idea.

> I'm not sure if pointers to symbol entries are saved in the process
> of constructing the list, which would make that hard; hopefully not.

> There is no reason to be concerned about performance of the finalize
> method in this case.  If someone is concerned they can fix the way
> mdebugread generates symbol lists so that it uses the same hash tables
> everyone else does.

>> * There needs to be a way to add symbols to an environment while
>> constructing it.  Maybe
>> 
>> void env_add_symbol(struct environment *, struct symbol *);

> Does there?  Right now most lists are constructed first into a pending
> list, and only then hashed into an environment.

I was thinking of env_add_symbol as the way to hash the symbols into
the environment.  I'll look at how the pending lists work; if all the
code uses the same data structure, then of course there should be a
constructor that takes the entire pending list rather than requiring
each symbol to be added individually.

> I'd rather not have to use growable hash tables.

Indeed.  On the other hand, as I mentioned above, it seems plausible
to me that the responsibility for managing the lists of pending
symbols should, in the future, be tranferred to environments rather
than the code that builds the blocks.  So it seems plausible to me to
have a linked list implementation of environments that is great for
adding new symbols and lousy for lookups, and then have finalize
functions that convert linked list implementations to either hash
tables or arrays (depending on whether or not you needed ordering),
which could no longer grow.

>> * There should be a shallow lookup function, i.e. one that looks up a
>> symbol just in one environment, without going up to a parent
>> environment.  (The latter will get added in once we get to
>> converting over the global environment.)  Maybe
>> 
>> struct symbol *env_lookup_shallow(struct environment *,
>> const char *);

> You may need more information than this.  Sometimes
> lookup_block_symbol needs to look up the symbol (i.e. demangled)
> which has a particular mangled name - this is a wart and not one I'm
> fond of but it isn't quite ready to die yet.

I think that I'm tentatively planning to defer issues like mangled
vs. demangled names until I convert over the global environment: that
will be the time to think about exactly what sorts of deep lookup
functions will be necessary, for example.  Having said that, I just
looked at lookup_block_symbol more closely, and I'm not sure that my
planned iterators would be quite enough to handle it.  (But I might be
able to delete the relevant code, see below.)

>> * There should probably be iterators that allow one to examine every
>> symbol in an environment.  One possibility, to save on memory
>> management headaches, would be to allow only one active iterator per
>> environment, and have that stored as part of the environment; so we
>> would have
>> 
>> struct symbol *env_lookup_first(struct environment *);
>> struct symbol *env_lookup_next(struct environment *);
>> 
>> (Where these return NULL if we've seen all the symbols in the
>> environment.)  I'll have to double-check to make sure that existing
>> use of iteration over symbols blocks is compatible with this, but
>> I'm almost positive it is.

> In most cases yes.  See the ALL_BLOCK_SYMBOLS macro.

Right, that's what I was thinking of: this could replace that easily
enough as long as there weren't two copies of ALL_BLOCK_SYMBOLS
running on the same block simultaneously, which seems plausible to
me.

> There are a couple of places where I could not use it for some
> reason, though.

>> * It's vaguely possible that some code might need to count the number
>> of symbols in an environment, but I don't think so; presumably
>> that's only used by iterators or by code that could be moved to the
>> inside of struct environment.
>> 
>> * When scanning GDB for uses of 'struct block', I noticed that some
>> code wants to sort symbols in the block.  I'll have to look at where
>> and why that's happening, but I don't think it's anything serious.
>> (When it's necessary, it can presumably be added to a 'finalize'
>> function as in the discussion of constructors above.)

> It's irrelevant - it was only for speeding up searching.  Note that
> hashed blocks are never sorted and blocks with a function are never
> sorted.  mdebugread-style blocks are simply legacy.

Great.  That probably means that I can just skip the sorting and
delete code in functions like lookup_block_symbols that handles sorted
linear blocks as a special case.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Jacobowitz]

On Fri, Sep 06, 2002 at 10:20:38AM -0700, David Carlton wrote:
> Daniel Jacobowitz <drow@mvista.com> writes:
> > On Thu, Sep 05, 2002 at 01:50:40PM -0700, David Carlton wrote:
> 
> >> So I want to add a type 'struct environment' to GDB.  It will be
> >> completely opaque, with a variety of internal implementations
> >> available (similar to the way that 'struct block' allows you to use
> >> either a hash table or a simple list of symbols) sharing a common
> >> external interface.  I want to start by converting 'struct block' over
> >> to using this, then converting the global environment over to using
> >> this, then (probably) 'struct type', and finally getting namespaces to
> >> work well.
> 
> > Why do you want to have multiple available implementations?  I think
> > the overhead for always hashing is small enough.  There are only two
> > reasons struct block allows hash tables or linked lists:
> >   - overloading of the meaning of that list to represent a list of
> >     function arguments, which is ordered
> >   - warts in mdebugread that I was not patient enough to overcome when
> >     I finally merged in hash table support
> 
> > I suppose the first reason is a legitimate one for multiple
> > implementations; we could mark an environment as 'ordered'.  Or we
> > could stop overloading the meaning of the list that way.  I don't know
> > which is better.
> 
> The global block in jv-lang.c may also pose similar problems to those
> in mdebugread.c, for what that's worth.  (I'm not sure: it might be
> cleaner than mdebugread.c.)  But you've basically put your finger on
> it: some blocks currently have a reason to be ordered, and some pieces
> of code try to construct the environments on the fly, growing them as
> necessary.  Which, incidentally, I don't think we should discourage:
> instead of requiring code to calculate the size of environments before
> building them, we might as well support environments that can be built
> incrementally and then finalized.  That way the common bookkeeping
> code gets moved into the environment stuff, so people don't have to
> keep on redoing it.

The question is whether those partial environments should be treated as
environments as all - do we even need to do lookups on them?  I believe
we never should.

> And there's another, even more important reason: the global
> environment (and, in the future, namespaces).  The global environment
> spans multiple files, uses lazy evaluation (i.e. partial_symbols), and
> there's even minimal_symbols to shoehorn in there somehow.  So it's
> going to need its own special implementation (which will be much more
> complicated than the implementations for blocks).

This is why I don't like the environment == list-of-symbols thing.  An
environment may HAVE a list of symbols, but it is not its list of
symbols.  You shouldn't grow the list of symbols in the global
environment when a new file is added.  Instead you should associate a
new list of symbols with it.  Files can be removed as well as added,
remember.  We don't do that very well right now.

Search the archives of this list for:
  Date: 11 Jun 2001 12:55:42 -0400
  From: Daniel Berlin <dan@cgsoftware.com>
  Subject: [RFC] Symbol table improvements

for some other suggested reading on this topic.  I like this
architecture he describes, even if we're not quite ready for it yet.
We could be.

> At some point in the future, it might be possible to use a single
> implementation for everything; it would have to support:
> 
> * Growing as needed
> * Fast lookups
> * Being able to retrieve all entries in the order in which they were
>   added
> * Whatever extra cruft is necessary to support environments like the
>   global environment.
> 
> This is certainly possible (heaps solve the first two problems, for
> example), but I think moving over to a single implementation can and
> should be postponed until much later in the game.  It'll be easy
> enough to do, if desirable, once existing code gets converted over to
> using environments.

I don't see the benefit of maintaining order-added information in the
general case; we want it only for specific small lists.

> > I'm not sure if pointers to symbol entries are saved in the process
> > of constructing the list, which would make that hard; hopefully not.
> 
> > There is no reason to be concerned about performance of the finalize
> > method in this case.  If someone is concerned they can fix the way
> > mdebugread generates symbol lists so that it uses the same hash tables
> > everyone else does.
> 
> >> * There needs to be a way to add symbols to an environment while
> >> constructing it.  Maybe
> >> 
> >> void env_add_symbol(struct environment *, struct symbol *);
> 
> > Does there?  Right now most lists are constructed first into a pending
> > list, and only then hashed into an environment.
> 
> I was thinking of env_add_symbol as the way to hash the symbols into
> the environment.  I'll look at how the pending lists work; if all the
> code uses the same data structure, then of course there should be a
> constructor that takes the entire pending list rather than requiring
> each symbol to be added individually.

Look at buildsym.c:add_symbol_to_list, find_symbol_in_list, and
finish_block.

> > I'd rather not have to use growable hash tables.
> 
> Indeed.  On the other hand, as I mentioned above, it seems plausible
> to me that the responsibility for managing the lists of pending
> symbols should, in the future, be tranferred to environments rather
> than the code that builds the blocks.  So it seems plausible to me to

It already is centralized in buildsym, for all but the crufty readers.

> have a linked list implementation of environments that is great for
> adding new symbols and lousy for lookups, and then have finalize
> functions that convert linked list implementations to either hash
> tables or arrays (depending on whether or not you needed ordering),
> which could no longer grow.

We've pretty much got this already.  That's finish_block; you just
described its purpose.

> >> * There should be a shallow lookup function, i.e. one that looks up a
> >> symbol just in one environment, without going up to a parent
> >> environment.  (The latter will get added in once we get to
> >> converting over the global environment.)  Maybe
> >> 
> >> struct symbol *env_lookup_shallow(struct environment *,
> >> const char *);
> 
> > You may need more information than this.  Sometimes
> > lookup_block_symbol needs to look up the symbol (i.e. demangled)
> > which has a particular mangled name - this is a wart and not one I'm
> > fond of but it isn't quite ready to die yet.
> 
> I think that I'm tentatively planning to defer issues like mangled
> vs. demangled names until I convert over the global environment: that
> will be the time to think about exactly what sorts of deep lookup
> functions will be necessary, for example.  Having said that, I just
> looked at lookup_block_symbol more closely, and I'm not sure that my
> planned iterators would be quite enough to handle it.  (But I might be
> able to delete the relevant code, see below.)

Unlikely.  The case I'm talking about is tied to some of our C++
evilness; there are multiple global symbols with the same demangled
name, and it is vital that we know how to breakpoint the correct one,
or the breakpoint will not be hit.

That said this needs cleanups elsewhere.  We might be able to handle it
some other way...

> Right, that's what I was thinking of: this could replace that easily
> enough as long as there weren't two copies of ALL_BLOCK_SYMBOLS
> running on the same block simultaneously, which seems plausible to
> me.

Probably.  And you could add assertions to ensure this.

> > There are a couple of places where I could not use it for some
> > reason, though.
> 
> >> * It's vaguely possible that some code might need to count the number
> >> of symbols in an environment, but I don't think so; presumably
> >> that's only used by iterators or by code that could be moved to the
> >> inside of struct environment.
> >> 
> >> * When scanning GDB for uses of 'struct block', I noticed that some
> >> code wants to sort symbols in the block.  I'll have to look at where
> >> and why that's happening, but I don't think it's anything serious.
> >> (When it's necessary, it can presumably be added to a 'finalize'
> >> function as in the discussion of constructors above.)
> 
> > It's irrelevant - it was only for speeding up searching.  Note that
> > hashed blocks are never sorted and blocks with a function are never
> > sorted.  mdebugread-style blocks are simply legacy.
> 
> Great.  That probably means that I can just skip the sorting and
> delete code in functions like lookup_block_symbols that handles sorted
> linear blocks as a special case.

Eventually, I hope so.  Yes.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[David Carlton]

Daniel Jacobowitz <drow@mvista.com> writes:
> On Fri, Sep 06, 2002 at 10:20:38AM -0700, David Carlton wrote:

>> instead of requiring code to calculate the size of environments
>> before building them, we might as well support environments that
>> can be built incrementally and then finalized.  That way the common
>> bookkeeping code gets moved into the environment stuff, so people
>> don't have to keep on redoing it.

> The question is whether those partial environments should be treated
> as environments as all - do we even need to do lookups on them?  I
> believe we never should.

Fair enough: partial environments should be a separate concept, and
one which might not even be necessary (see below).

>> And there's another, even more important reason: the global
>> environment (and, in the future, namespaces).  The global
>> environment spans multiple files, uses lazy evaluation
>> (i.e. partial_symbols), and there's even minimal_symbols to
>> shoehorn in there somehow.  So it's going to need its own special
>> implementation (which will be much more complicated than the
>> implementations for blocks).

> This is why I don't like the environment == list-of-symbols thing.
> An environment may HAVE a list of symbols, but it is not its list of
> symbols.  You shouldn't grow the list of symbols in the global
> environment when a new file is added.  Instead you should associate
> a new list of symbols with it.  Files can be removed as well as
> added, remember.  We don't do that very well right now.

> Search the archives of this list for:
>   Date: 11 Jun 2001 12:55:42 -0400
>   From: Daniel Berlin <dan@cgsoftware.com>
>   Subject: [RFC] Symbol table improvements

> for some other suggested reading on this topic.  I like this
> architecture he describes, even if we're not quite ready for it yet.
> We could be.

Thanks for the pointer.  Certainly I'm not at all thrilled with the
way that the global symbol lookup functions work currently.  One
thought that I had was to use a growable but quickly-searchable data
structure for global lookups; but that has the problems that it makes
removing individual files complicated (incidentally, I had been
wondering if that could happen, but I guess from your response above
that the answer is 'yes') and it might make psymtab->symtab conversion
a bit trickier.

Skimming the message you're referring to, it seems like Daniel Berlin
is proposing keeping the idea that the global environment is made out
of a bunch of blocks from different files, but speeding up the process
of going from a symbol name to the specific blocks to search.  That
sounds like a good idea: it's still fast, but it still allows a
per-file granularity which seems like it would be useful.

>> At some point in the future, it might be possible to use a single
>> implementation for everything; it would have to support:

>> * Growing as needed
>> * Fast lookups
>> * Being able to retrieve all entries in the order in which they were
>> added
>> * Whatever extra cruft is necessary to support environments like the
>> global environment.

> I don't see the benefit of maintaining order-added information in the
> general case; we want it only for specific small lists.

I think I agree.  For now, I'd prefer to have a choice between
fixed-size hash tables or fixed-size small lists, rather than a single
general structure: having multiple internal implementations is easy
enough to do, and there's no need to pay the extra costs of the
general structure if it's not necessary.

>> I'll look at how the pending lists work; if all the code uses the
>> same data structure, then of course there should be a constructor
>> that takes the entire pending list rather than requiring each
>> symbol to be added individually.

> Look at buildsym.c:add_symbol_to_list, find_symbol_in_list, and
> finish_block.
...
> It already is centralized in buildsym, for all but the crufty readers.
...
> We've pretty much got this already.  That's finish_block; you just
> described its purpose.

Great.  So, modulo jv-lang.c and mdebugread.c, there's no need for
incremental construction of environments.  The only question, then, is
whether it would be easier to convert those special cases to
buildsym's mechanisms, or to handle them specially in the environment
code; if both are equally easy, then obviously the former is
preferable.

>> I think that I'm tentatively planning to defer issues like mangled
>> vs. demangled names until I convert over the global environment:
>> that will be the time to think about exactly what sorts of deep
>> lookup functions will be necessary, for example.  Having said that,
>> I just looked at lookup_block_symbol more closely, and I'm not sure
>> that my planned iterators would be quite enough to handle it.  (But
>> I might be able to delete the relevant code, see below.)

> The case I'm talking about is tied to some of our C++ evilness;
> there are multiple global symbols with the same demangled name, and
> it is vital that we know how to breakpoint the correct one, or the
> breakpoint will not be hit.

> That said this needs cleanups elsewhere.  We might be able to handle
> it some other way...

Hmm.  Clearly I'll need to examine this more closely.

>> Right, that's what I was thinking of: this could replace that easily
>> enough as long as there weren't two copies of ALL_BLOCK_SYMBOLS
>> running on the same block simultaneously, which seems plausible to
>> me.

> Probably.  And you could add assertions to ensure this.

I'm not sure that we can use assertions to help here.  The issue, as I
see it, is:

* If you're willing to make sure that you tell the iterator when
  you're done with it, then you might as well make it possible to keep
  around multiple iterators: that's more flexible.

* If you're not willing to make sure that you tell the iterator when
  you're done with it, then it's easiest if you one have iterator
  active on any given environment at any one time, because otherwise
  you have to take care to avoid memory leaks.

It seems to me that we're in the latter situation: currently, GDB has
code that does an ALL_BLOCK_SYMBOLS and that, once it's found the
symbol that it's looking for, breaks out of the ALL_BLOCK_SYMBOLS by
returning from the function.  So we'd have to modify those situations
to discard the iterator before returning, and it would be easy for
future users of ALL_BLOCK_SYMBOLS to forget that.

But, if we're in the latter situation, I don't see how to get
assertions to work.

At some point, I'll give it a look: ALL_BLOCK_SYMBOLS is only used in
29 places, so it should be tractable to survey them by hand.

Actually, now that I think about it, there's another possibility that
would avoid memory leaks: if we can make sure that all memory used by
the iterator gets put on the stack then we're set.  We could do this
with code like

  struct env_iterator it;

  for (env_iterator_initialize (env, &it);
       env_iterator_not_done (&it);
       env_iterator_advance (&it)) {
    do_something_with env_iterator_current_symbol (&it);
  }

This works fine even if the body of the for loop exists in an
unexpected manner.  And that idiom could be encapsulated with a macro
like ALL_BLOCK_SYMBOLS, of course.  I'm not thrilled with this idea,
but it's certainly workable.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Berlin]

> one which might not even be necessary (see below).
> 
> >> And there's another, even more important reason: the global
> >> environment (and, in the future, namespaces).  The global
> >> environment spans multiple files, uses lazy evaluation
> >> (i.e. partial_symbols), and there's even minimal_symbols to
> >> shoehorn in there somehow.  So it's going to need its own special
> >> implementation (which will be much more complicated than the
> >> implementations for blocks).
> 
> > This is why I don't like the environment == list-of-symbols thing.
> > An environment may HAVE a list of symbols, but it is not its list of
> > symbols.  You shouldn't grow the list of symbols in the global
> > environment when a new file is added.  Instead you should associate
> > a new list of symbols with it.

This makes lookup dependent on two things, instead of one (number of 
files, and number of names, vs number of names).
Bad idea when you can avoid it.
If you want to know what blocks go with which files, than store *that* 
information.
Removal is *not* the common case.




> Files can be removed as well as added, remember.  We don't do that very well right now.
We don't do it at all, actually, because of obstacks. 
Only when we blow everything (IE all files) away at once, or something.

> 
> > Search the archives of this list for:
> >   Date: 11 Jun 2001 12:55:42 -0400
> >   From: Daniel Berlin <dan@cgsoftware.com>
> >   Subject: [RFC] Symbol table improvements
> 
> > for some other suggested reading on this topic.  I like this
> > architecture he describes, even if we're not quite ready for it yet.
> > We could be.
> 
> Thanks for the pointer.  Certainly I'm not at all thrilled with the
> way that the global symbol lookup functions work currently.  One
> thought that I had was to use a growable but quickly-searchable data
> structure for global lookups; but that has the problems that it makes
> removing individual files complicated (incidentally, I had been
> wondering if that could happen, but I guess from your response above
> that the answer is 'yes')

No, but we *should* be working towards this.
> and it might make psymtab->symtab conversion
> a bit trickier.
psymtabs are useless for things besides stabs and maybe one or two other 
minor debug formats. Almost every one, including DWARF2, HP's, etc, have a 
fast way to access the full symbol given a name or address, without having 
to construct some auxillary structure to do it.
psymtabs exist because STABS *can't* do this.
They, in actuality, should become specific to the STABS reader, and an 
internal mechanism *it* uses to do fast lookup.
For most other debug formats, it wastes memory, but their is no defined 
mechanism to bypass them (IE the interface to lazy lookup is through 
psymtabs directly, rather than abstracted in a way that lets you use 
DWARF2 pubnames/aranges, or the various structures present in other debug 
formats).

> > Skimming the message you're referring to, it seems like Daniel Berlin
> is proposing keeping the idea that the global environment is made out
> of a bunch of blocks from different files, but speeding up the process
> of going from a symbol name to the specific blocks to search.

This is what is slow in GDB.
As for whether it maps well to namespaces, the global environment really 
doesn't.
But in addition to being *much* faster, it's also easier to deal with 
namespaces in this kind of scheme, since you know all the blocks in which 
a name exists, and you can use a language dependent scheme to determine 
which is the name you want.
Before, you would no way to figure out this information except by brute 
force, if you wanted to look at names outside of the current scopes as 
well (because you wouldn't know what other scopes they exist in).
>sounds like a good idea: it's still fast, but it still allows a 
> per-file granularity which seems like it would be useful.

I studied this problem extensively while trying to speed up GDB, and 
reduce it's memory usage.
In fact, I had the dwarf2 reader able to drop and read files at will, but 
it required bypassing psymtabs.

Note that this wasn't the first time someone wanted to do this.  HP has a 
whole "FAT_FREE_PSYMTABS" thing in WDB.

Re: struct environment

[Daniel Jacobowitz]

On Fri, Sep 06, 2002 at 03:34:34PM -0400, Daniel Berlin wrote:
> 
> 
> > one which might not even be necessary (see below).
> > 
> > >> And there's another, even more important reason: the global
> > >> environment (and, in the future, namespaces).  The global
> > >> environment spans multiple files, uses lazy evaluation
> > >> (i.e. partial_symbols), and there's even minimal_symbols to
> > >> shoehorn in there somehow.  So it's going to need its own special
> > >> implementation (which will be much more complicated than the
> > >> implementations for blocks).
> > 
> > > This is why I don't like the environment == list-of-symbols thing.
> > > An environment may HAVE a list of symbols, but it is not its list of
> > > symbols.  You shouldn't grow the list of symbols in the global
> > > environment when a new file is added.  Instead you should associate
> > > a new list of symbols with it.
> 
> This makes lookup dependent on two things, instead of one (number of 
> files, and number of names, vs number of names).
> Bad idea when you can avoid it.
> If you want to know what blocks go with which files, than store *that* 
> information.
> Removal is *not* the common case.

Well, what I had in mind when I wrote that was the same sort of thing
you originally described - with a cached mapping of symbols -> blocks. 
I do need to sit down and think about how namespaces interact here
however... gets a little peculiar.


> Note that this wasn't the first time someone wanted to do this.  HP has a 
> whole "FAT_FREE_PSYMTABS" thing in WDB.

Yeah.  Killing psymtabs in general would be nice but that's tabled
behind stub methods (which I am slowing quashing).

What's the current status of the location expression stuff, by the
way?

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[Daniel Berlin]

On Friday, September 6, 2002, at 03:41  PM, Daniel Jacobowitz wrote:

> On Fri, Sep 06, 2002 at 03:34:34PM -0400, Daniel Berlin wrote:
>>
>>
>>> one which might not even be necessary (see below).
>>>
>>>>> And there's another, even more important reason: the global
>>>>> environment (and, in the future, namespaces).  The global
>>>>> environment spans multiple files, uses lazy evaluation
>>>>> (i.e. partial_symbols), and there's even minimal_symbols to
>>>>> shoehorn in there somehow.  So it's going to need its own special
>>>>> implementation (which will be much more complicated than the
>>>>> implementations for blocks).
>>>
>>>> This is why I don't like the environment == list-of-symbols thing.
>>>> An environment may HAVE a list of symbols, but it is not its list of
>>>> symbols.  You shouldn't grow the list of symbols in the global
>>>> environment when a new file is added.  Instead you should associate
>>>> a new list of symbols with it.
>>
>> This makes lookup dependent on two things, instead of one (number of
>> files, and number of names, vs number of names).
>> Bad idea when you can avoid it.
>> If you want to know what blocks go with which files, than store *that*
>> information.
>> Removal is *not* the common case.
>
> Well, what I had in mind when I wrote that was the same sort of thing
> you originally described - with a cached mapping of symbols -> blocks.
> I do need to sit down and think about how namespaces interact here
> however... gets a little peculiar.
>
>
>> Note that this wasn't the first time someone wanted to do this.  HP 
>> has a
>> whole "FAT_FREE_PSYMTABS" thing in WDB.
>
> Yeah.  Killing psymtabs in general would be nice but that's tabled
> behind stub methods (which I am slowing quashing).
>
> What's the current status of the location expression stuff, by the
> way?

I've been too busy with law school and interviews (2nd year law 
students have interviews for summer jobs in late august and early 
september. Absurd, no?) to work on it.
I did make sure Peter Sofa and Jim Blandy know this, and that if they 
want it done anytime soon, to work on it themselves.
The changes Jim requested probably wouldn't take more than a day or two 
to implement, i just don't have that day or two right now.

>
> -- 
> Daniel Jacobowitz
> MontaVista Software                         Debian GNU/Linux Developer
>

Re: struct environment

[David Carlton]

On 06 Sep 2002 11:56:14 -0700, David Carlton
<carlton@math.Stanford.EDU> said:

> At some point, I'll give it a look: ALL_BLOCK_SYMBOLS is only used
> in 29 places, so it should be tractable to survey them by hand.

And of course it turns out that, in at least one place,
ALL_BLOCK_SYMBOLS calls a function that, in turn, calls
ALL_BLOCK_SYMBOLS over the exact same block.  Oops.

But I think I was making too much of the memory-management
difficulties: I'll do iterators correctly (so you can have as many of
them active as you want), and just write an ALL_ENV_SYMBOLS macro that
allocates them on the stack using alloca().

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Jacobowitz]

On Wed, Sep 11, 2002 at 11:33:08AM -0700, David Carlton wrote:
> On 06 Sep 2002 11:56:14 -0700, David Carlton
> <carlton@math.Stanford.EDU> said:
> 
> > At some point, I'll give it a look: ALL_BLOCK_SYMBOLS is only used
> > in 29 places, so it should be tractable to survey them by hand.
> 
> And of course it turns out that, in at least one place,
> ALL_BLOCK_SYMBOLS calls a function that, in turn, calls
> ALL_BLOCK_SYMBOLS over the exact same block.  Oops.
> 
> But I think I was making too much of the memory-management
> difficulties: I'll do iterators correctly (so you can have as many of
> them active as you want), and just write an ALL_ENV_SYMBOLS macro that
> allocates them on the stack using alloca().

Or you could just require an iterator to be declared in the function
which uses ALL_BLOCK_SYMBOLS.... why bring alloca into it?  The pointer
you allocate into would need to be a local variable so the iterator
might as well just be a local variable.  Sure, it makes them a tiny bit
less opaque.  But make them opaque -in practice-.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[David Carlton]

On Wed, 11 Sep 2002 14:36:28 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> On Wed, Sep 11, 2002 at 11:33:08AM -0700, David Carlton wrote:

>> But I think I was making too much of the memory-management
>> difficulties: I'll do iterators correctly (so you can have as many
>> of them active as you want), and just write an ALL_ENV_SYMBOLS
>> macro that allocates them on the stack using alloca().

> Or you could just require an iterator to be declared in the function
> which uses ALL_BLOCK_SYMBOLS.... why bring alloca into it?  The
> pointer you allocate into would need to be a local variable so the
> iterator might as well just be a local variable.  Sure, it makes
> them a tiny bit less opaque.  But make them opaque -in practice-.

I know, I'm too in love with opacity right now.  Chalk it up to the
bad influence of C++, or something.  (What, I can't just store my
pointer in a std::auto_ptr and have its contents deleted automatically
when it goes out of scope?)

Having said that, there's a bit more reason for these types to be
opaque than normal.  There will be multiple implementations of
environments: currently fixed-size hash, fixed-size linear, and
expandable linear (for use by jv-lang.c and mdebugread.c, sigh), plus
two temporary implementions using struct block that will only exist
until all the block code is switched over to using environments.  And
once I tackle global symbols, there will be at least one new permanent
environment implementation and one new temporary environment
implementation to handle that, too.  Also, there is literally no
information that is common to all the different implementations, so it
simply doesn't make sense to have publically-accessible macros to get
at parts of the environment, for example.  So it would be nice if,
say, adding new implementations was all localized to environment.c
plus adding one creation function prototype to symtab.h, rather than
polluting symtab.h with lots of data that only environment.c will use.

But, on the other hand, alloca() should still be avoided if possible.
And it's not like the solution using alloca() is all that clean: in an
opaque implementation, I can't alloca(sizeof struct env_iterator), so
I would have to provide a function call env_sizeof_iterator() to
return that information.  And I suspect that, once we move on to the
global environment, we'll want to add a 'parent environment' member to
environments that will be there for all implementations, so it might
make sense to make environments slightly less opaque.  It's even
possible that, for performance reasons, some of the functions will
have to be turned into macros eventually.

I'll think about it some more.  It might well be the case that all
iterators would just need a struct environment *, a struct symbol **,
and an integer: so they all have the same data, but use it in
different ways depending on how the struct environment is
implemented.  If that's the case, it would be perverse to use
alloca(): I can certainly break opaqueness to that extent.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[David Carlton]

On Fri, 6 Sep 2002 11:06:20 -0400, Daniel Jacobowitz <drow@mvista.com>
said:

> - warts in mdebugread that I was not patient enough to overcome when
>   I finally merged in hash table support

How hard do you think it would be to convert mdebugread over to using
the mechanisms from buildsym?  (I looked at mdebugread myself, but my
brain seems to be overflowing with GDB code right now; I'll try again
next week, but if you can give me an easy answer, so much the better.)
It seems to me like it shouldn't be too hard to convert it over to my
environment mechanism using the partially-constructed environments +
finalize ideas that we'd talked about earlier; but if it could just as
easily be converted to using buildsym, so much the better.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Jacobowitz]

On Fri, Sep 06, 2002 at 02:41:02PM -0700, David Carlton wrote:
> On Fri, 6 Sep 2002 11:06:20 -0400, Daniel Jacobowitz <drow@mvista.com>
> said:
> 
> > - warts in mdebugread that I was not patient enough to overcome when
> >   I finally merged in hash table support
> 
> How hard do you think it would be to convert mdebugread over to using
> the mechanisms from buildsym?  (I looked at mdebugread myself, but my
> brain seems to be overflowing with GDB code right now; I'll try again
> next week, but if you can give me an easy answer, so much the better.)
> It seems to me like it shouldn't be too hard to convert it over to my
> environment mechanism using the partially-constructed environments +
> finalize ideas that we'd talked about earlier; but if it could just as
> easily be converted to using buildsym, so much the better.

I think, very easy.  But I no longer have (easy) access to any system
which uses it, so I was reluctant to mess around.  You should just be
able to make it build a pending list instead of doing the work
in-place...

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

mdebugread.c (was Re: struct environment)

[David Carlton]

On Fri, 6 Sep 2002 17:46:32 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> On Fri, Sep 06, 2002 at 02:41:02PM -0700, David Carlton wrote:

>> How hard do you think it would be to convert mdebugread over to using
>> the mechanisms from buildsym?

> I think, very easy.  But I no longer have (easy) access to any system
> which uses it, so I was reluctant to mess around.

Yeah, that's something that I'm worried about too.  Is there anybody
else that's reading this that can help with changes to that file?
Who's the appropriate maintainer; is it Andrew?

David Carlton
carlton@math.stanford.edu

Re: mdebugread.c (was Re: struct environment)

[Daniel Jacobowitz]

On Fri, Sep 06, 2002 at 02:55:56PM -0700, David Carlton wrote:
> On Fri, 6 Sep 2002 17:46:32 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> > On Fri, Sep 06, 2002 at 02:41:02PM -0700, David Carlton wrote:
> 
> >> How hard do you think it would be to convert mdebugread over to using
> >> the mechanisms from buildsym?
> 
> > I think, very easy.  But I no longer have (easy) access to any system
> > which uses it, so I was reluctant to mess around.
> 
> Yeah, that's something that I'm worried about too.  Is there anybody
> else that's reading this that can help with changes to that file?
> Who's the appropriate maintainer; is it Andrew?

Alpha still uses it under some circumstances; and old-ish or properly
(improperly? :) configured MIPS tools may also.  You might be able to
find a MIPS simulator target that works to test this but it'd be a bit
of a pain.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[David Carlton]

On Fri, 6 Sep 2002 11:06:20 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> On Thu, Sep 05, 2002 at 01:50:40PM -0700, David Carlton wrote:

>> * There should be a shallow lookup function, i.e. one that looks up a
>> symbol just in one environment, without going up to a parent
>> environment.  (The latter will get added in once we get to
>> converting over the global environment.)  Maybe
>> 
>> struct symbol *env_lookup_shallow(struct environment *,
>> const char *);

> You may need more information than this.  Sometimes
> lookup_block_symbol needs to look up the symbol (i.e. demangled)
> which has a particular mangled name - this is a wart and not one I'm
> fond of but it isn't quite ready to die yet.

Fair enough; for now, that function has the exact same arguments as
lookup_block_symbol (i.e. including the demangled name and the
namespace).

But, speaking of warts in lookup_block_symbol, what's going on with
this code?

	      /* If SYM has aliases, then use any alias that is active
	         at the current PC.  If no alias is active at the current
	         PC, then use the main symbol.

	         ?!? Is checking the current pc correct?  Is this routine
	         ever called to look up a symbol from another context?

		 FIXME: No, it's not correct.  If someone sets a
		 conditional breakpoint at an address, then the
		 breakpoint's `struct expression' should refer to the
		 `struct symbol' appropriate for the breakpoint's
		 address, which may not be the PC.

		 Even if it were never called from another context,
		 it's totally bizarre for lookup_symbol's behavior to
		 depend on the value of the inferior's current PC.  We
		 should pass in the appropriate PC as well as the
		 block.  The interface to lookup_symbol should change
		 to require the caller to provide a PC.  */

	      if (SYMBOL_ALIASES (sym))
		sym = find_active_alias (sym, read_pc ());

	      sym_found = sym;
	      if (SYMBOL_CLASS (sym) != LOC_ARG &&
		  SYMBOL_CLASS (sym) != LOC_LOCAL_ARG &&
		  SYMBOL_CLASS (sym) != LOC_REF_ARG &&
		  SYMBOL_CLASS (sym) != LOC_REGPARM &&
		  SYMBOL_CLASS (sym) != LOC_REGPARM_ADDR &&
		  SYMBOL_CLASS (sym) != LOC_BASEREG_ARG)
		{
		  break;
		}

Is the SYMBOL_ALIASES bit some sort of stabs mess?  And is that if
expression an attempt to make sure that function arguments whose names
are shadowed by local variables don't get returned?

For now, I'm planning just to copy all that to env_lookup_shallow, but
I do wish I understood a little better what it's doing.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Jacobowitz]

On Tue, Sep 10, 2002 at 05:25:56PM -0700, David Carlton wrote:
> On Fri, 6 Sep 2002 11:06:20 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> > On Thu, Sep 05, 2002 at 01:50:40PM -0700, David Carlton wrote:
> 
> >> * There should be a shallow lookup function, i.e. one that looks up a
> >> symbol just in one environment, without going up to a parent
> >> environment.  (The latter will get added in once we get to
> >> converting over the global environment.)  Maybe
> >> 
> >> struct symbol *env_lookup_shallow(struct environment *,
> >> const char *);
> 
> > You may need more information than this.  Sometimes
> > lookup_block_symbol needs to look up the symbol (i.e. demangled)
> > which has a particular mangled name - this is a wart and not one I'm
> > fond of but it isn't quite ready to die yet.
> 
> Fair enough; for now, that function has the exact same arguments as
> lookup_block_symbol (i.e. including the demangled name and the
> namespace).
> 
> But, speaking of warts in lookup_block_symbol, what's going on with
> this code?

My memory is hazy, but if you search the archives I suspect you'll see
hints that this all can be deleted.  I believe the SYMBOL_ALIASES stuff
has all died; it was never in a standard FSF GCC, just in a Cygnus
product.  We'll need to handle something along these lines in the
fortold day of wonders, when we actually have thought of something
clever to do when debugging inlined functions; but for now I doubt
anyone would miss this.

Can anyone confirm my memory?

> 
> 	      /* If SYM has aliases, then use any alias that is active
> 	         at the current PC.  If no alias is active at the current
> 	         PC, then use the main symbol.
> 
> 	         ?!? Is checking the current pc correct?  Is this routine
> 	         ever called to look up a symbol from another context?
> 
> 		 FIXME: No, it's not correct.  If someone sets a
> 		 conditional breakpoint at an address, then the
> 		 breakpoint's `struct expression' should refer to the
> 		 `struct symbol' appropriate for the breakpoint's
> 		 address, which may not be the PC.
> 
> 		 Even if it were never called from another context,
> 		 it's totally bizarre for lookup_symbol's behavior to
> 		 depend on the value of the inferior's current PC.  We
> 		 should pass in the appropriate PC as well as the
> 		 block.  The interface to lookup_symbol should change
> 		 to require the caller to provide a PC.  */
> 
> 	      if (SYMBOL_ALIASES (sym))
> 		sym = find_active_alias (sym, read_pc ());
> 
> 	      sym_found = sym;
> 	      if (SYMBOL_CLASS (sym) != LOC_ARG &&
> 		  SYMBOL_CLASS (sym) != LOC_LOCAL_ARG &&
> 		  SYMBOL_CLASS (sym) != LOC_REF_ARG &&
> 		  SYMBOL_CLASS (sym) != LOC_REGPARM &&
> 		  SYMBOL_CLASS (sym) != LOC_REGPARM_ADDR &&
> 		  SYMBOL_CLASS (sym) != LOC_BASEREG_ARG)
> 		{
> 		  break;
> 		}
> 
> Is the SYMBOL_ALIASES bit some sort of stabs mess?  And is that if
> expression an attempt to make sure that function arguments whose names
> are shadowed by local variables don't get returned?
> 
> For now, I'm planning just to copy all that to env_lookup_shallow, but
> I do wish I understood a little better what it's doing.
> 
> David Carlton
> carlton@math.stanford.edu
> 

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[David Carlton]

On Tue, 10 Sep 2002 20:31:32 -0400, Daniel Jacobowitz <drow@mvista.com> said:

> I believe the SYMBOL_ALIASES stuff has all died; it was never in a
> standard FSF GCC, just in a Cygnus product.  We'll need to handle
> something along these lines in the fortold day of wonders, when we
> actually have thought of something clever to do when debugging
> inlined functions; but for now I doubt anyone would miss this.

Thanks for the pointer:
<http://sources.redhat.com/ml/gdb/2002-03/msg00232.html> says
something similar, and asks for permission to delete it (together with
SYMBOL_RANGES).  But I guess it was never deleted (and the
LOC_COMPUTED stuff that that message refers to hasn't yet been
implemented).

For now, I'll just leave out that part of the code (or, better,
include it but #if 0 it out and add an explanatory comment).

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Jacobowitz]

On Wed, Sep 11, 2002 at 10:29:34AM -0700, David Carlton wrote:
> On Tue, 10 Sep 2002 20:31:32 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> 
> > I believe the SYMBOL_ALIASES stuff has all died; it was never in a
> > standard FSF GCC, just in a Cygnus product.  We'll need to handle
> > something along these lines in the fortold day of wonders, when we
> > actually have thought of something clever to do when debugging
> > inlined functions; but for now I doubt anyone would miss this.
> 
> Thanks for the pointer:
> <http://sources.redhat.com/ml/gdb/2002-03/msg00232.html> says
> something similar, and asks for permission to delete it (together with
> SYMBOL_RANGES).  But I guess it was never deleted (and the
> LOC_COMPUTED stuff that that message refers to hasn't yet been
> implemented).

Hasn't yet been polished and integrated, rather - you can find the code
in the list archives for a month or two ago.

> For now, I'll just leave out that part of the code (or, better,
> include it but #if 0 it out and add an explanatory comment).

Sounds fine to me.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[Daniel Berlin]

On 11 Sep 2002, David Carlton wrote:

> On Tue, 10 Sep 2002 20:31:32 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> 
> > I believe the SYMBOL_ALIASES stuff has all died; it was never in a
> > standard FSF GCC, just in a Cygnus product.  We'll need to handle
> > something along these lines in the fortold day of wonders, when we
> > actually have thought of something clever to do when debugging
> > inlined functions; but for now I doubt anyone would miss this.
> 
> Thanks for the pointer:
> <http://sources.redhat.com/ml/gdb/2002-03/msg00232.html> says
> something similar, and asks for permission to delete it (together with
> SYMBOL_RANGES).  But I guess it was never deleted (and the
> LOC_COMPUTED stuff that that message refers to hasn't yet been
> implemented).
Implemented yes, but i've not time to make the requested  minor changes 
necessary to get approval.
Law school and all that jazz.

Feel free to do so if you like, the patches/what is necessary is on 
gdb-patches.
Shouldn't take but a day.

> 
> For now, I'll just leave out that part of the code (or, better,
> include it but #if 0 it out and add an explanatory comment).

> 
> David Carlton
> carlton@math.stanford.edu
> 
> 

Re: struct environment

[David Carlton]

On 10 Sep 2002 17:25:56 -0700, David Carlton <carlton@math.Stanford.EDU> said:

> 	      sym_found = sym;
> 	      if (SYMBOL_CLASS (sym) != LOC_ARG &&
> 		  SYMBOL_CLASS (sym) != LOC_LOCAL_ARG &&
> 		  SYMBOL_CLASS (sym) != LOC_REF_ARG &&
> 		  SYMBOL_CLASS (sym) != LOC_REGPARM &&
> 		  SYMBOL_CLASS (sym) != LOC_REGPARM_ADDR &&
> 		  SYMBOL_CLASS (sym) != LOC_BASEREG_ARG)
> 		{
> 		  break;
> 		}

> is that if expression an attempt to make sure that function
> arguments whose names are shadowed by local variables don't get
> returned?

Ah, I missed an earlier comment: 

  /* Note that parameter symbols do not always show up last in the
     list; this loop makes sure to take anything else other than
     parameter symbols first; it only uses parameter symbols as a
     last resort.  Note that this only takes up extra computation
     time on a match.  */

So it seems that my guess about the meaning of that 'if' expression is
correct.  I wish I understood why parameter symbols don't always show
up last in the list, though.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Andrew Cagney]

> 
> Why do you want to have multiple available implementations?  I think
> the overhead for always hashing is small enough.  There are only two
> reasons struct block allows hash tables or linked lists:
>   - overloading of the meaning of that list to represent a list of
>     function arguments, which is ordered
>   - warts in mdebugread that I was not patient enough to overcome when
>     I finally merged in hash table support
> 
> I suppose the first reason is a legitimate one for multiple
> implementations; we could mark an environment as 'ordered'.  Or we
> could stop overloading the meaning of the list that way.  I don't know
> which is better.

Daniel's observation is correct.  The last thing we need is something 
totally overengineered.  Is there any reason to not start out with a 
very simple implementation and get it working first?

Only once the structure is working correctly should we be thinking about 
making it work fast.

Andrew

Re: struct environment

[David Carlton]

On 05 Sep 2002 13:50:40 -0700, David Carlton <carlton@math.Stanford.EDU> said:

> The question remains of how to get from here to there.  I'm pretty
> sure that I can convert 'struct block' over to using environments in
> an incremental fashion.  Describing that process will take a fair
> amount of time, though, so I'll send it in a separate e-mail,
> probably some time tomorrow but maybe Monday.

Here's the basic idea as to how to convert struct block over to
environments incrementally.

As I commented before, environments will have various internal
implementations.  Current candidates for implementations are:

* Fixed-size hash tables.
* Fixed-size lists.
* Some sort of growing implementation (necessary for jv-lang.c,
  alas).

But while we're in the middle of converting over 'struct block', there
will be one more implementation:

* An implementation that keeps a pointer to a struct block, and does
  all lookups by accessing that struct block.

The advantage of that latter implementation is that, given blocks
whose environments use that implementation, all symbol lookups can be
done either by the old-fashioned methods or by the new environment
lookup methods, with identical results.  So, broadly speaking, the
implementation process will have three steps:

1) Convert existing block creators to use environments that are
   implemented via a pointer to 'struct block'.
2) Convert all block symbol lookups from the old accessors to the new
   accessors.
3) Convert the block creators to use one of the implementations other
   than 'struct block'.


That's the basic idea.  Here's the gory details:

** Step 0: Implement environments.

Create a new file 'environment.c' to contain all of the
environment-managing code.  (Side note: I just realized that GDB
already has a (little-used) 'struct environ' and a file 'environ.c'.
Oops.  If anybody thinks that adding 'struct environment' to this
would create confusion and has a better name to suggest, I'm all
ears.)

Implement the various constructors/accessors/etc. for environments,
for each of the various internal implementations mentioned above.
(Actually, at this stage it's only necessary to implement the
constructors for the 'struct block' internal implementation; the
accessors could be deferred until just before step 2, and the other
internal implementations could be deferred until just before step 3,
if desired.)


** Step 1: Convert existing block creators to use environments that are
implemented via a pointer to 'struct block'.

So we start by adding a struct environment * member to struct block.
Then, we have to make sure it gets initialized correctly, via an
environment that points to the block in question.  There are, I
believe, 3 cases here:

* The default case.  This is for blocks allocated via buildsym.c.
  This should be straightforward to implement: the complete list of
  symbols to be added to the blocks is already known.

* mdebugread.c.  Frankly, my brain can't handle that file right now.
  I'll try looking at it again next week, but if somebody familiar
  with that file could give me an indication as to what is proper to
  do with it, I'd appreciate it.  For all I know, it would be easy
  enough to convert it over to using the buildsym.c mechanisms; if
  not, I'll have to do some sort of special-case code for doing
  partially-constructed environments that then get finalized and
  hashed.

* jv-lang.c.  This constructs one separate block that can grow
  indefinitely.  (It contains names of classes, and I see no
  particular reason that we'll ever be able to tell that we're done
  adding classes.)  So this will need to use a special implementation.

Each case should be dealt with by a single patch, and the three
patches should be logically independent of each other.  The first and
third patches should be easy; it seems plausible to me that the
mdebugread.c patch might be a pain in the neck.


** Step 2: Convert all block symbol lookups from the old accessors to
the new accessors.

At the end of step 1, the environment data in blocks should be able to
be accessed in two different ways: either via the old mechanisms
(BLOCK_HASHTABLE, BLOCK_NSYMS, BLOCK_SYM, BLOCK_BUCKETS, BLOCK_BUCKET,
ALL_BLOCK_SYMBOLS, etc.) or via new mechanisms (env_lookup_shallow(),
whatever iterators get decided upon, etc.)

So the goal here is to track down every single reference to the old
mechanisms and convert them to the new mechanisms.  E.g. uses of
ALL_BLOCK_SYMBOLS should be replaced by uses of a new macro which goes
through the new iterators for the environment objects.  Or
lookup_block_symbol() will call env_lookup_shallow().  Indeed, calls
to lookup_block_symbol() might be replaced to calls to
env_lookup_shallow(); note, however, that Daniel Jacobowitz warns that
I'll have to be careful with mangled vs. demangled names there, so
lookup functions will have to handle that (and possibly there will
need to be two different env_lookup_shallow functions).

Also, in the middle of this, I'll probably delete all references to
BLOCK_SHOULD_SORT, and all sorting of linear blocks.  Blocks created
by buildsym.c never satisfy BLOCK_SHOULD_SORT; block created in other
ways can either be rewritten to be created by buildsym.c or just live
with having unsorted linear environments.  (Incidentally, the global
block in jv-lang.c probably satisfies BLOCK_SHOULD_SORT, but I'm
fairly sure it never gets sorted.)

This step can be implemented by lots of patches in almost any order:
either the old methods or the new methods work during this step, so
there's no need to worry about being consistent here.


** Step 3: Convert the block creators to use one of the
implementations other than 'struct block'.

At the end of step 2, all lookups are going through the new
accessors.  So now the old accessors can be deleted; and then the
code from step 1 can be converted over to using one of the permanent
implementations, rather than using implementation via 'struct block'.
Then the members hashtable, nsyms, and sym of 'struct block' can be
removed.


David Carlton
carlton@math.stanford.edu

Re: struct environment

[Tom Tromey]

>>>>> "David" == David Carlton <carlton@math.stanford.edu> writes:

David> * Some sort of growing implementation (necessary for jv-lang.c,
David>   alas).

I'm not familiar with the code in jv-lang.c.  But are you sure it is
really necessary?  Could it be that the code there is a workaround for
the existing lack of namespaces?  I seem to recall reading that the
gcj support in gdb had such hacks.  I don't know either way; I've just
seen this mentioned a few times recently and I wanted to make sure
that the possibility is considered.

I think Per Bothner <bothner@bothner.com> may be able to answer
questions about this code.  He wrote it and he's still involved with
gcj.

Tom

Re: struct environment

[David Carlton]

On 06 Sep 2002 17:38:37 -0600, Tom Tromey <tromey@redhat.com> said:
>>>>>> "David" == David Carlton <carlton@math.stanford.edu> writes:

David> * Some sort of growing implementation (necessary for jv-lang.c,
David> alas).

> I'm not familiar with the code in jv-lang.c.  But are you sure it is
> really necessary?  Could it be that the code there is a workaround
> for the existing lack of namespaces?  I seem to recall reading that
> the gcj support in gdb had such hacks.  I don't know either way;
> I've just seen this mentioned a few times recently and I wanted to
> make sure that the possibility is considered.

I would be surprised if it weren't some sort of hack as you suggest.
What's going on is that there seems to be a block created whose sole
purpose is to contain symbols giving the names of classes.  They're
all getting plunked in the global namespace, even though they include
package names; presumably the package name hierarchy should eventually
be reflected in the way that GDB stores that information.

One interesting thing that's going on is that the classes in question
are all apparently "dynamically loaded".  It might be the case that
this is somewhat unexpected to the rest of GDB; I'm really not sure.
Also, if my dim memory of Java is correct, "global symbols" are kind
of rare in Java: probably each file only contains one symbol that's
really global in any sense (that symbol being a class whose name is
the same as the file), and of course that symbol probably actually
lives in a package.  So maybe the fact that almost everything in Java
lives in a class affects the way that GDB's Java code handles
symbols.  I dunno.

It seems to me that, in the short term, the thing to do is to just
deal with making the minimal number of changes to jv-lang.c as is;
it's a lot easier to handle it as a special case for now and postpone
properly handling it until we're about to start seriously thinking
about reworking C++ namespaces.  But certainly this should be reworked
at an appropriate stage of this process.

> I think Per Bothner <bothner@bothner.com> may be able to answer
> questions about this code.  He wrote it and he's still involved with
> gcj.

Good idea; I'll do that on Monday.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Per Bothner]

David Carlton wrote:
> One interesting thing that's going on is that the classes in question
> are all apparently "dynamically loaded".

Yes.  This code date back the the very early days of gcj, when we were
basing it on the Kaffe run-time, which was JIT-based.  Even the days
it is possible for a class to be generated on-the-fly, or loaded from
a .jar file containing bytecodes.  Such a class will not have dwarf
or other static symbols.  So this was an attempt to extract the type
information from a class from the run-time type information for a
class instead of or in addition to the static symbols.

Such an attempt runs into various assumptions of gdb, such as how
symtabs are managed and reclaimed, so it was never very solid.
We can't debug interpreted bytecode anyway, so it's not much use.
Feel tree to tear this code out, but keep in mind that new Java
classes may be created on the fly.

I think the correct way to handle on-the-fly Java classes is to
use a model similar to dynamically linked libraries.  In both
cases a program can execute library functions that bring in new
code and new global symbols.  The main difference is that there
may be many more Java classes that are dynamically loaded then
the number of shared libraries, which may effect the strategy
used.  Though if most classes are pre-compiled, we're talking
at most hundreds, rather than thousands.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/per/

Re: struct environment

[Daniel Jacobowitz]

On Sat, Sep 07, 2002 at 10:27:58AM -0700, Per Bothner wrote:
> David Carlton wrote:
> >One interesting thing that's going on is that the classes in question
> >are all apparently "dynamically loaded".
> 
> Yes.  This code date back the the very early days of gcj, when we were
> basing it on the Kaffe run-time, which was JIT-based.  Even the days
> it is possible for a class to be generated on-the-fly, or loaded from
> a .jar file containing bytecodes.  Such a class will not have dwarf
> or other static symbols.  So this was an attempt to extract the type
> information from a class from the run-time type information for a
> class instead of or in addition to the static symbols.
> 
> Such an attempt runs into various assumptions of gdb, such as how
> symtabs are managed and reclaimed, so it was never very solid.
> We can't debug interpreted bytecode anyway, so it's not much use.
> Feel tree to tear this code out, but keep in mind that new Java
> classes may be created on the fly.
> 
> I think the correct way to handle on-the-fly Java classes is to
> use a model similar to dynamically linked libraries.  In both
> cases a program can execute library functions that bring in new
> code and new global symbols.  The main difference is that there
> may be many more Java classes that are dynamically loaded then
> the number of shared libraries, which may effect the strategy
> used.  Though if most classes are pre-compiled, we're talking
> at most hundreds, rather than thousands.

OK.  At this point, then, I think the thing to do is ignore the Java
dynamic loading for now.  If your changes break compilation of it, we
can #if 0 it out.  Somewhere down the road, after when shared library
support has been multi-arched :), we can redo it that way.

Actually, this has potential - it would be nice to support multiple
dynamic loading mechanisms.  See the XFree86 loader patches on
gdb-patches a while ago...

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[David Carlton]

On Sat, 7 Sep 2002 13:32:00 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> On Sat, Sep 07, 2002 at 10:27:58AM -0700, Per Bothner wrote:
>> David Carlton wrote:

>>> One interesting thing that's going on is that the classes in question
>>> are all apparently "dynamically loaded".

>> Yes.  This code date back the the very early days of gcj, when we
>> were basing it on the Kaffe run-time, which was JIT-based.  Even
>> the days it is possible for a class to be generated on-the-fly, or
>> loaded from a .jar file containing bytecodes.  Such a class will
>> not have dwarf or other static symbols.  So this was an attempt to
>> extract the type information from a class from the run-time type
>> information for a class instead of or in addition to the static
>> symbols.

Thanks for the info.

> OK.  At this point, then, I think the thing to do is ignore the Java
> dynamic loading for now.

I'd prefer to handle the Java stuff instead of ignore it.  It should
only take an hour or two of work: it's pretty clean, so it should just
involve adding one simple variant of struct environment and futzing
with symtab.free_ptr slightly.  (Which seems to currently only be used
in this specific situation, admittedly a bit of a space waste...)

Certainly if I were looking for pieces of code to ignore over the
course of this process, mdebugread.c would be a much higher priority
for me...

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Andrew Cagney]

Just BTW, is there another name?  ``environment'' can also refer to the 
processes environment as seen in the existing environ.[hc] code.

Andrew

Re: struct environment

[David Carlton]

On Thu, 12 Sep 2002 15:26:38 -0400, Andrew Cagney <ac131313@ges.redhat.com> said:

> Just BTW, is there another name?  ``environment'' can also refer to
> the processes environment as seen in the existing environ.[hc] code.

How about 'dictionary'?  It seems to me that the idea of looking up a
variable name to find out the information contained in its symbol
isn't too different from the idea of looking up a word to find out its
meaning.

I looked through the GDB sources, and it doesn't seem to be used
widely elsewhere, and even when it's used it's only used informally.
The main place where it's used is that infttrace has an important
static struct called 'memory_page_dictionary'; but, as naming
conflicts go, that's quite minimal.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Andrew Cagney]

David,

Per the original thread, this should be prototyped on a branch (you can 
then cut your self loose for a bit :-).

Having done this for regcache and reggroup it is worth it -> you get to 
see what actually works rather than what everyone else thinks should 
work.  You can also pick out the cleanups that will make the final 
change easier.  For instance - tightening up the way GDB creates symbol 
tables (DanielB suggested moving psymtab into stabs) an performs lookups 
on them.

--

Btw, try ``struct nametab''?  These are just tables for mapping a name 
onto a symbol?

--

Have a look at how I've been evolving ``struct frame_info'' and ``struct 
cmd_list_element[?]'':

- tighten up the existing interface so that you know how things are 
really used (rather than how you think things are used).  My trick was 
to do a temp rename of a field and then convert to accessor methods 
anything that didn't compile.

- with a tight interface, re-implement the internals.

--

Having also gone over the original thread, two things come to mind:

- what effect will this have on GDB's foot print?  The original proposal 
was to put these things everwhere (structs, unions, ...).  I don't think 
that is necessary and would cause serious bloat.  Instead, initially, I 
think these tables could be simple linear lists (that is what ``struct 
block'' currently implements so it can't be any worse :-) (just the 
global / final table is special :-).

- Am I correct to think that the objective is to create a directed 
acyclic graph of nametabs and have lookups search through each in turn.

--

In terms of operations, I would concentrate on determing exactly GDB 
needs (rather than you think it needs)   GDB is 15 years old so chance 
has it the operations have been identified already.  I know of two 
operations off hand:
	print foo
which gets turned into struct symbol *lookup("foo",``block'') and,
	print foo<tab>
which turns into ``const char **tabexpand("foo", ``block'')''.  Any others?

Andrew

Re: struct environment

[Daniel Jacobowitz]

On Tue, Sep 17, 2002 at 03:47:36AM -0400, Andrew Cagney wrote:
> Btw, try ``struct nametab''?  These are just tables for mapping a name 
> onto a symbol?

Hmm..

> Having also gone over the original thread, two things come to mind:
> 
> - what effect will this have on GDB's foot print?  The original proposal 
> was to put these things everwhere (structs, unions, ...).  I don't think 
> that is necessary and would cause serious bloat.  Instead, initially, I 
> think these tables could be simple linear lists (that is what ``struct 
> block'' currently implements so it can't be any worse :-) (just the 
> global / final table is special :-).

Why do you think this will cause any bloat?  This is why David
suggested a model of block with a linear list implementation.

> - Am I correct to think that the objective is to create a directed 
> acyclic graph of nametabs and have lookups search through each in turn.

Well, sort of.  It won't be a DAG necessarily (I think that mutual
"using" statements are legal in C++; I remember a GCC bug involving
them was fixed not long ago), and it will be somewhat complicated
figuring out which ones to look up (namespace links are different than
block scope links).

> In terms of operations, I would concentrate on determing exactly GDB 
> needs (rather than you think it needs)   GDB is 15 years old so chance 
> has it the operations have been identified already.  I know of two 
> operations off hand:
> 	print foo
> which gets turned into struct symbol *lookup("foo",``block'') and,
> 	print foo<tab>
> which turns into ``const char **tabexpand("foo", ``block'')''.  Any others?

At least iterate over all, search regexp.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[Andrew Cagney]

> On Tue, Sep 17, 2002 at 03:47:36AM -0400, Andrew Cagney wrote:
> 
>> Btw, try ``struct nametab''?  These are just tables for mapping a name 
>> onto a symbol?
> 
> 
> Hmm..
> 
> 
>> Having also gone over the original thread, two things come to mind:
>> 
>> - what effect will this have on GDB's foot print?  The original proposal 
>> was to put these things everwhere (structs, unions, ...).  I don't think 
>> that is necessary and would cause serious bloat.  Instead, initially, I 
>> think these tables could be simple linear lists (that is what ``struct 
>> block'' currently implements so it can't be any worse :-) (just the 
>> global / final table is special :-).
> 
> 
> Why do you think this will cause any bloat?  This is why David
> suggested a model of block with a linear list implementation.

That is good news, the early discussion was describing a totally generic 
implementation being applied to everything.  Can I assume that no one 
has immediate plans for adding this to the type system?

>> - Am I correct to think that the objective is to create a directed 
>> acyclic graph of nametabs and have lookups search through each in turn.
> 
> 
> Well, sort of.  It won't be a DAG necessarily (I think that mutual
> "using" statements are legal in C++; I remember a GCC bug involving
> them was fixed not long ago), and it will be somewhat complicated
> figuring out which ones to look up (namespace links are different than
> block scope links).

Don't forget that GDB doesn't need to model the language.  Just the 
namespace behavior at a given PC.  The effect of "using" would be to 
just grow a nametab in someway.

>> In terms of operations, I would concentrate on determing exactly GDB 
>> needs (rather than you think it needs)   GDB is 15 years old so chance 
>> has it the operations have been identified already.  I know of two 
>> operations off hand:
>> 	print foo
>> which gets turned into struct symbol *lookup("foo",``block'') and,
>> 	print foo<tab>
>> which turns into ``const char **tabexpand("foo", ``block'')''.  Any others?
> 
> 
> At least iterate over all, search regexp.

Yes (iterate over would come from things like ``info locals'').  Regex 
(I know it's used somewhere)?

Andrew

Re: struct environment

[Daniel Jacobowitz]

On Tue, Sep 17, 2002 at 11:59:05AM -0400, Andrew Cagney wrote:
> >On Tue, Sep 17, 2002 at 03:47:36AM -0400, Andrew Cagney wrote:
> >
> >>Btw, try ``struct nametab''?  These are just tables for mapping a name 
> >>onto a symbol?
> >
> >
> >Hmm..
> >
> >
> >>Having also gone over the original thread, two things come to mind:
> >>
> >>- what effect will this have on GDB's foot print?  The original proposal 
> >>was to put these things everwhere (structs, unions, ...).  I don't think 
> >>that is necessary and would cause serious bloat.  Instead, initially, I 
> >>think these tables could be simple linear lists (that is what ``struct 
> >>block'' currently implements so it can't be any worse :-) (just the 
> >>global / final table is special :-).
> >
> >
> >Why do you think this will cause any bloat?  This is why David
> >suggested a model of block with a linear list implementation.
> 
> That is good news, the early discussion was describing a totally generic 
> implementation being applied to everything.  Can I assume that no one 
> has immediate plans for adding this to the type system?

Not sure what you mean.  I don't see any problem with the way David
described it - a dictionary which could be ordered (list) or unordered
(hash) depending on the context.  I wouldn't call that overengineered.

> >>- Am I correct to think that the objective is to create a directed 
> >>acyclic graph of nametabs and have lookups search through each in turn.
> >
> >
> >Well, sort of.  It won't be a DAG necessarily (I think that mutual
> >"using" statements are legal in C++; I remember a GCC bug involving
> >them was fixed not long ago), and it will be somewhat complicated
> >figuring out which ones to look up (namespace links are different than
> >block scope links).
> 
> Don't forget that GDB doesn't need to model the language.  Just the 
> namespace behavior at a given PC.  The effect of "using" would be to 
> just grow a nametab in someway.

This is legal C++:

namespace D {}

namespace C { 
  using namespace D;
  int x, y;
}

namespace D {
  using namespace C;
  int x, z;
}

If using just grew a nametab we'd get into a great deal of trouble.

> >>In terms of operations, I would concentrate on determing exactly GDB 
> >>needs (rather than you think it needs)   GDB is 15 years old so chance 
> >>has it the operations have been identified already.  I know of two 
> >>operations off hand:
> >>	print foo
> >>which gets turned into struct symbol *lookup("foo",``block'') and,
> >>	print foo<tab>
> >>which turns into ``const char **tabexpand("foo", ``block'')''.  Any 
> >>others?
> >
> >
> >At least iterate over all, search regexp.
> 
> Yes (iterate over would come from things like ``info locals'').  Regex 
> (I know it's used somewhere)?

search_symbols?  The plan is not to stop with blocks; the point is to
use the same interface for the global symbol tables also.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[Andrew Cagney]

> Well, sort of.  It won't be a DAG necessarily (I think that mutual
>> >"using" statements are legal in C++; I remember a GCC bug involving
>> >them was fixed not long ago), and it will be somewhat complicated
>> >figuring out which ones to look up (namespace links are different than
>> >block scope links).
> 
>> 
>> Don't forget that GDB doesn't need to model the language.  Just the 
>> namespace behavior at a given PC.  The effect of "using" would be to 
>> just grow a nametab in someway.
> 
> 
> This is legal C++:
> 
> namespace D {}
> 
> namespace C { 
>   using namespace D;
>   int x, y;
> }
> 
> namespace D {
>   using namespace C;
>   int x, z;
> }
> 
> If using just grew a nametab we'd get into a great deal of trouble.

Depends on how you grow it :-)  Something like (assuming a real language 
:-):
	D:
	0: x, z
	1: x, y (from C)
	2: ...

Andrew

Re: struct environment

[Daniel Jacobowitz]

On Tue, Sep 17, 2002 at 01:54:07PM -0400, Andrew Cagney wrote:
> >Well, sort of.  It won't be a DAG necessarily (I think that mutual
> >>>"using" statements are legal in C++; I remember a GCC bug involving
> >>>them was fixed not long ago), and it will be somewhat complicated
> >>>figuring out which ones to look up (namespace links are different than
> >>>block scope links).
> >
> >>
> >>Don't forget that GDB doesn't need to model the language.  Just the 
> >>namespace behavior at a given PC.  The effect of "using" would be to 
> >>just grow a nametab in someway.
> >
> >
> >This is legal C++:
> >
> >namespace D {}
> >
> >namespace C { 
> >  using namespace D;
> >  int x, y;
> >}
> >
> >namespace D {
> >  using namespace C;
> >  int x, z;
> >}
> >
> >If using just grew a nametab we'd get into a great deal of trouble.
> 
> Depends on how you grow it :-)  Something like (assuming a real language 
> :-):
> 	D:
> 	0: x, z
> 	1: x, y (from C)
> 	2: ...

How you intend to do this efficiently I don't know.  Remember that C
uses D in turn, and that things "using"'d into D will therefore be
visible in C.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[Andrew Cagney]

>> Depends on how you grow it :-)  Something like (assuming a real language 
>> :-):
>> 	D:
>> 	0: x, z
>> 	1: x, y (from C)
>> 	2: ...
> 
> 
> How you intend to do this efficiently I don't know.

By efficiency did you mean speed or memory?  I don't see speed being an 
issue (except for the global table), just memory (GDB's foot print growing).

 >  Remember that C
 > uses D in turn, and that things "using"'d into D will therefore be
 > visible in C.

True, but I'm not the one implementing this.  I'm just trying to 
understand the core-gdb interface.

Andrew

Re: struct environment

[Daniel Jacobowitz]

On Tue, Sep 17, 2002 at 03:37:58PM -0400, Andrew Cagney wrote:
> 
> >>Depends on how you grow it :-)  Something like (assuming a real language 
> >>:-):
> >>	D:
> >>	0: x, z
> >>	1: x, y (from C)
> >>	2: ...
> >
> >
> >How you intend to do this efficiently I don't know.
> 
> By efficiency did you mean speed or memory?  I don't see speed being an 
> issue (except for the global table), just memory (GDB's foot print growing).

Either.  It's quite a hard problem, which is a reason why C++ compilers
generally use Koenig lookup through multiple blocks rather than growing
blocks.  And there's all sorts of other correctness issues.

> >  Remember that C
> > uses D in turn, and that things "using"'d into D will therefore be
> > visible in C.
> 
> True, but I'm not the one implementing this.  I'm just trying to 
> understand the core-gdb interface.
> 
> Andrew
> 
> 
> 

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[Andrew Cagney]

> On Tue, Sep 17, 2002 at 03:37:58PM -0400, Andrew Cagney wrote:
> 
>> 
> 
>> >>Depends on how you grow it :-)  Something like (assuming a real language 
>> >>:-):
>> >>	D:
>> >>	0: x, z
>> >>	1: x, y (from C)
>> >>	2: ...
> 
>> >
>> >
>> >How you intend to do this efficiently I don't know.
> 
>> 
>> By efficiency did you mean speed or memory?  I don't see speed being an 
>> issue (except for the global table), just memory (GDB's foot print growing).
> 
> 
> Either.  It's quite a hard problem, which is a reason why C++ compilers
> generally use Koenig lookup through multiple blocks rather than growing
> blocks.  And there's all sorts of other correctness issues.

{I'd better find out what a koenig lookup is.  I think I just tried to 
described one :-)

The correctness of course does need to come before the efficience.  So I 
guess (to back out) if the choice is between burning memory and having 
GDB print a correct value and being memory efficient but wrong, then the 
first is the correct choice.

Andrew


>> >  Remember that C
>> > uses D in turn, and that things "using"'d into D will therefore be
>> > visible in C.
> 
>> 
>> True, but I'm not the one implementing this.  I'm just trying to 
>> understand the core-gdb interface.
>> 
>> Andrew
>> 
>> 
>> 
> 
> 
> -- Daniel Jacobowitz MontaVista Software Debian GNU/Linux Developer 

Re: struct environment

[Daniel Berlin]

On Tuesday, September 17, 2002, at 02:02  PM, Daniel Jacobowitz wrote:

> On Tue, Sep 17, 2002 at 01:54:07PM -0400, Andrew Cagney wrote:
>>> Well, sort of.  It won't be a DAG necessarily (I think that mutual
>>>>> "using" statements are legal in C++; I remember a GCC bug involving
>>>>> them was fixed not long ago), and it will be somewhat complicated
>>>>> figuring out which ones to look up (namespace links are different 
>>>>> than
>>>>> block scope links).
>>>
>>>>
>>>> Don't forget that GDB doesn't need to model the language.  Just the
>>>> namespace behavior at a given PC.  The effect of "using" would be to
>>>> just grow a nametab in someway.
>>>
>>>
>>> This is legal C++:
>>>
>>> namespace D {}
>>>
>>> namespace C {
>>>  using namespace D;
>>>  int x, y;
>>> }
>>>
>>> namespace D {
>>>  using namespace C;
>>>  int x, z;
>>> }
>>>
>>> If using just grew a nametab we'd get into a great deal of trouble.
>>
>> Depends on how you grow it :-)  Something like (assuming a real 
>> language
>> :-):
>> 	D:
>> 	0: x, z
>> 	1: x, y (from C)
>> 	2: ...
>
> How you intend to do this efficiently I don't know.  Remember that C
> uses D in turn, and that things "using"'d into D will therefore be
> visible in C.

These types of problems are exactly why i said a lot of thought needs 
to be put into the design of the underlying structures, rather than 
just copying what we have because we have it.
It's hard to call it "overengineered" if how to do lookups efficiently 
with large numbers of names in namespaces hasn't been considered.
It's not really something you can bolt on later.
Hasn't this been proven by the fact that it hasn't been bolted on yet?
--Dan

Re: struct environment

[Daniel Jacobowitz]

On Tue, Sep 17, 2002 at 03:52:33PM -0400, Daniel Berlin wrote:
> 
> On Tuesday, September 17, 2002, at 02:02  PM, Daniel Jacobowitz wrote:
> 
> >On Tue, Sep 17, 2002 at 01:54:07PM -0400, Andrew Cagney wrote:
> >>>Well, sort of.  It won't be a DAG necessarily (I think that mutual
> >>>>>"using" statements are legal in C++; I remember a GCC bug involving
> >>>>>them was fixed not long ago), and it will be somewhat complicated
> >>>>>figuring out which ones to look up (namespace links are different 
> >>>>>than
> >>>>>block scope links).
> >>>
> >>>>
> >>>>Don't forget that GDB doesn't need to model the language.  Just the
> >>>>namespace behavior at a given PC.  The effect of "using" would be to
> >>>>just grow a nametab in someway.
> >>>
> >>>
> >>>This is legal C++:
> >>>
> >>>namespace D {}
> >>>
> >>>namespace C {
> >>> using namespace D;
> >>> int x, y;
> >>>}
> >>>
> >>>namespace D {
> >>> using namespace C;
> >>> int x, z;
> >>>}
> >>>
> >>>If using just grew a nametab we'd get into a great deal of trouble.
> >>
> >>Depends on how you grow it :-)  Something like (assuming a real 
> >>language
> >>:-):
> >>	D:
> >>	0: x, z
> >>	1: x, y (from C)
> >>	2: ...
> >
> >How you intend to do this efficiently I don't know.  Remember that C
> >uses D in turn, and that things "using"'d into D will therefore be
> >visible in C.
> 
> These types of problems are exactly why i said a lot of thought needs 
> to be put into the design of the underlying structures, rather than 
> just copying what we have because we have it.
> It's hard to call it "overengineered" if how to do lookups efficiently 
> with large numbers of names in namespaces hasn't been considered.
> It's not really something you can bolt on later.
> Hasn't this been proven by the fact that it hasn't been bolted on yet?

Absolutely.  But I've always thought that we'd still do it via
searching a succession of blocks, with some sort of global structure
for figuring out where to look; which means that at this point it's
been designed far enough.  I could be wrong :)

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[Daniel Berlin]

On Tuesday, September 17, 2002, at 04:34  PM, Daniel Jacobowitz wrote:

> On Tue, Sep 17, 2002 at 03:52:33PM -0400, Daniel Berlin wrote:
>>
>> On Tuesday, September 17, 2002, at 02:02  PM, Daniel Jacobowitz wrote:
>>
>>> On Tue, Sep 17, 2002 at 01:54:07PM -0400, Andrew Cagney wrote:
>>>>> Well, sort of.  It won't be a DAG necessarily (I think that mutual
>>>>>>> "using" statements are legal in C++; I remember a GCC bug 
>>>>>>> involving
>>>>>>> them was fixed not long ago), and it will be somewhat complicated
>>>>>>> figuring out which ones to look up (namespace links are different
>>>>>>> than
>>>>>>> block scope links).
>>>>>
>>>>>>
>>>>>> Don't forget that GDB doesn't need to model the language.  Just 
>>>>>> the
>>>>>> namespace behavior at a given PC.  The effect of "using" would be 
>>>>>> to
>>>>>> just grow a nametab in someway.
>>>>>
>>>>>
>>>>> This is legal C++:
>>>>>
>>>>> namespace D {}
>>>>>
>>>>> namespace C {
>>>>> using namespace D;
>>>>> int x, y;
>>>>> }
>>>>>
>>>>> namespace D {
>>>>> using namespace C;
>>>>> int x, z;
>>>>> }
>>>>>
>>>>> If using just grew a nametab we'd get into a great deal of trouble.
>>>>
>>>> Depends on how you grow it :-)  Something like (assuming a real
>>>> language
>>>> :-):
>>>> 	D:
>>>> 	0: x, z
>>>> 	1: x, y (from C)
>>>> 	2: ...
>>>
>>> How you intend to do this efficiently I don't know.  Remember that C
>>> uses D in turn, and that things "using"'d into D will therefore be
>>> visible in C.
>>
>> These types of problems are exactly why i said a lot of thought needs
>> to be put into the design of the underlying structures, rather than
>> just copying what we have because we have it.
>> It's hard to call it "overengineered" if how to do lookups efficiently
>> with large numbers of names in namespaces hasn't been considered.
>> It's not really something you can bolt on later.
>> Hasn't this been proven by the fact that it hasn't been bolted on yet?
>
> Absolutely.  But I've always thought that we'd still do it via
> searching a succession of blocks, with some sort of global structure
> for figuring out where to look; which means that at this point it's
> been designed far enough.  I could be wrong :)

This might be the case.
I'm just trying to make sure it *has* been considered.
I'm not saying it actually requires any changes to the proposed way of 
doing things.

In legal terms, i'm raising the objection to preserve it for a possible 
later appeal.
:)

--Dan

Re: struct environment

[Daniel Jacobowitz]

On Wed, Sep 18, 2002 at 12:51:46AM -0400, Daniel Berlin wrote:
> 
> On Tuesday, September 17, 2002, at 04:34  PM, Daniel Jacobowitz wrote:
> 
> >On Tue, Sep 17, 2002 at 03:52:33PM -0400, Daniel Berlin wrote:
> >>
> >>On Tuesday, September 17, 2002, at 02:02  PM, Daniel Jacobowitz wrote:
> >>
> >>>On Tue, Sep 17, 2002 at 01:54:07PM -0400, Andrew Cagney wrote:
> >>>>>Well, sort of.  It won't be a DAG necessarily (I think that mutual
> >>>>>>>"using" statements are legal in C++; I remember a GCC bug 
> >>>>>>>involving
> >>>>>>>them was fixed not long ago), and it will be somewhat complicated
> >>>>>>>figuring out which ones to look up (namespace links are different
> >>>>>>>than
> >>>>>>>block scope links).
> >>>>>
> >>>>>>
> >>>>>>Don't forget that GDB doesn't need to model the language.  Just 
> >>>>>>the
> >>>>>>namespace behavior at a given PC.  The effect of "using" would be 
> >>>>>>to
> >>>>>>just grow a nametab in someway.
> >>>>>
> >>>>>
> >>>>>This is legal C++:
> >>>>>
> >>>>>namespace D {}
> >>>>>
> >>>>>namespace C {
> >>>>>using namespace D;
> >>>>>int x, y;
> >>>>>}
> >>>>>
> >>>>>namespace D {
> >>>>>using namespace C;
> >>>>>int x, z;
> >>>>>}
> >>>>>
> >>>>>If using just grew a nametab we'd get into a great deal of trouble.
> >>>>
> >>>>Depends on how you grow it :-)  Something like (assuming a real
> >>>>language
> >>>>:-):
> >>>>	D:
> >>>>	0: x, z
> >>>>	1: x, y (from C)
> >>>>	2: ...
> >>>
> >>>How you intend to do this efficiently I don't know.  Remember that C
> >>>uses D in turn, and that things "using"'d into D will therefore be
> >>>visible in C.
> >>
> >>These types of problems are exactly why i said a lot of thought needs
> >>to be put into the design of the underlying structures, rather than
> >>just copying what we have because we have it.
> >>It's hard to call it "overengineered" if how to do lookups efficiently
> >>with large numbers of names in namespaces hasn't been considered.
> >>It's not really something you can bolt on later.
> >>Hasn't this been proven by the fact that it hasn't been bolted on yet?
> >
> >Absolutely.  But I've always thought that we'd still do it via
> >searching a succession of blocks, with some sort of global structure
> >for figuring out where to look; which means that at this point it's
> >been designed far enough.  I could be wrong :)
> 
> This might be the case.
> I'm just trying to make sure it *has* been considered.
> I'm not saying it actually requires any changes to the proposed way of 
> doing things.
> 
> In legal terms, i'm raising the objection to preserve it for a possible 
> later appeal.
> :)

Well then - it has been considered.  I'm not sure it's been considered
_enough_, but only time is going to answer that.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: struct environment

[David Carlton]

On Wed, 18 Sep 2002 00:51:46 -0400, Daniel Berlin <dberlin@dberlin.org> said:
> On Tuesday, September 17, 2002, at 04:34  PM, Daniel Jacobowitz wrote:

>> Absolutely.  But I've always thought that we'd still do it via
>> searching a succession of blocks, with some sort of global
>> structure for figuring out where to look; which means that at this
>> point it's been designed far enough.  I could be wrong :)

> This might be the case.  I'm just trying to make sure it *has* been
> considered.  I'm not saying it actually requires any changes to the
> proposed way of doing things.

Certainly.  I think my attitude now is that the organization of
searching has been considered enough for local uses of struct block;
but clearly more thought has to occur before the global environment
gets designed.  Whether or not that latter will continue to use struct
blocks is up in the air; it's a plausible design, but by no means the
only plausible design.

Wait a couple of weeks; we can have a nice big argument about all of
this then.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[David Carlton]

On Tue, 17 Sep 2002 09:40:57 -0400, Daniel Jacobowitz <drow@mvista.com> said:
> On Tue, Sep 17, 2002 at 03:47:36AM -0400, Andrew Cagney wrote:

>> - Am I correct to think that the objective is to create a directed
>> acyclic graph of nametabs and have lookups search through each in turn.

> Well, sort of.  It won't be a DAG necessarily (I think that mutual
> "using" statements are legal in C++; I remember a GCC bug involving
> them was fixed not long ago), and it will be somewhat complicated
> figuring out which ones to look up (namespace links are different
> than block scope links).

That last parenthetical comment is important.  (And I hope it will
only be 'somewhat' complicated...)

If you have a C++ file like this:

using namespace A;

int foo()
{
  // body of function
}

then 'foo' gets added to the global environment, but the 'using
namespace A' doesn't affect the global enviroment, just this
particular file.  (E.g. it modifies the search rules in the body of
the function.)  So 'using' statements only modify symbol lookups, they
don't modify symbol definitions.  In contrast, the curly braces around
the body of the function modify two things: they modify symbol
definitions (since new variables defined in the body _aren't_ visible
in the global environment), and they also modify symbol definitions.

So you have to be able to deal with language constructs that only
modify where symbols are looked up as well as language constructs that
modify where symbols are looked up _and_ where symbols are added; and,
in the former case, you have to make sure that you only modify where
symbols are looked up in one particular chunk of the code, not in the
entire enviroment where symbols are currently being added.  (And,
incidentally, 'using' isn't the only way that name lookup can get
modified in this sort of way.)

Because of this, I don't think it's very useful to conflate these two
sorts of relationships between environments and just talk about a DAG.
There should be a tree reflecting the block structure (which we
already have, of course); and there should be some other data
structure reflecting additional symbol lookup rules.  And I'm not sure
yet exactly what that other data structure should look like, or how it
should interact with the block structure tree.  Or, for that matter,
whether either kind of data should stay within struct block or move
within struct dictionary.  (I'm leaving everything in the former until
I'm sure it should move.)

Obviously I need to read the relevant parts of the C++ standard before
working on namespaces proper.  For what it's worth, I think the
relevant buzzword is 'Koenig lookup', but I could be wrong.  And I
just hope and pray that other languages with complicated name lookup
rules use the same mechanisms as C++...

David Carlton
carlton@math.stanford.edu

Re: struct environment

[David Carlton]

On Tue, 17 Sep 2002 03:47:36 -0400, Andrew Cagney
<ac131313@ges.redhat.com> said:

Daniel's already chimed in on this, and I think I agree with
everything he's said, but let me throw in my own two cents as well.

> Per the original thread, this should be prototyped on a branch (you
> can then cut your self loose for a bit :-).

I thought about that; here's a question I have with regards to that.
It seems to me that, if I wanted to make large numbers of changes all
at once, then a branch would clearly be the way to go: nobody's going
to want to see a monolithic patch without having it be well-tested.

But nobody likes monolithic patches anyways; whenever somebody posts a
large patch, it's followed by complaints asking for the patch to be
broken up into smaller pieces, and the original poster then says it's
not possible.  If you want smaller pieces, then incremental changes
are are the way to go; I seem to recall that, in the original
discussion back in April, a branch was proposed because people didn't
believe that doing this incrementally was possible.

I'm confident that doing it incrementally is possible; that's why I'm
proposing adapting the existing functionality by first handling struct
block, and then handling the global environment; and, in turn, I'm
handling struct block in a three-phase process, such that the
semantics are unchanged after each phase and that, in turn, each phase
can be broken up into multiple patches so that, say, the Java
maintainers don't have to be confronted with changes to mdebugread.c.

I don't mind doing this on a branch, and even doing it incrementally
on a branch.  I'm not enough of an expert on CVS to know how easy it
is to merge in incremental branch changes to the mainline; but I
assume CVS will help me with that.  But it would still be a pain, I
think: if I'm going to do it incrementally, and take the care to leave
GDB in a useable state at all times, I'd rather do it on mainline.

> Having done this for regcache and reggroup it is worth it -> you get
> to see what actually works rather than what everyone else thinks
> should work.  You can also pick out the cleanups that will make the
> final change easier.  For instance - tightening up the way GDB
> creates symbol tables (DanielB suggested moving psymtab into stabs)
> an performs lookups on them.

Personally, I'd rather tighten up the interface to symbol lookups
first and only then move on to optimizations like changing how
reading in a part of the symbol information is implemented.

> Btw, try ``struct nametab''?  These are just tables for mapping a name
> onto a symbol?

Right, but "nametab" = "table of names", whereas it's really a table
of symbols, i.e. a symtab.  But that name's already used elsewhere.

> Have a look at how I've been evolving ``struct frame_info'' and
> ``struct cmd_list_element[?]'':

Thanks for the pointer; I'll give it a look.

> - tighten up the existing interface so that you know how things are
>   really used (rather than how you think things are used).  My trick
>   was to do a temp rename of a field and then convert to accessor
>   methods anything that didn't compile.

> - with a tight interface, re-implement the internals.

I think these are a pretty good description of what I'm actually
doing.  Except that, I've broken up your first step somewhat: rather
than renaming a field, I'm adding a new field that provides the same
functionality as existing fields, then converting the accessors over a
little more gradually, then deleting the existing field.  It lets me
make my patches a lot smaller.

> Having also gone over the original thread, two things come to mind:

> - what effect will this have on GDB's foot print?  The original
>   proposal was to put these things everwhere (structs, unions, ...).
>   I don't think that is necessary and would cause serious bloat.

I certainly want to put them in blocks, to use them to represent the
global environment, and to use them to represent namespaces; those are
the core name->symbol translation areas.

It seems to me that the main borderline issue is whether or not to use
them to represent fields in structures/classes.  The advantage of
that, from the C++ (and presumably Java) point of view, is that there
are times when you can refer to fields of structures as if they were
variables; the existing solution, namely the is_a_field_of_this
argument to lookup_symbol, is ugly, probably not flexible enough to
handle C++ and Java correctly (e.g. what about nested classes in
Java?), and complicates the interface for code that doesn't need this
functionality (e.g. when debugging C code).

But, as you say, that leads to code bloat: struct field really is
smaller than struct symbol, after all.  And it might well be the
casethat making struct field a special case of struct symbol would
make life more complicated for, say, C code that wants to use struct
field.

So no, I'm not proposing converting structs, unions, etc. over to
this; I don't think that's a good idea for now, and possibly not a
good idea ever.

>   Instead, initially, I think these tables could be simple linear
>   lists (that is what ``struct block'' currently implements so it
>   can't be any worse :-) (just the global / final table is special
>   :-).

For struct block, I'm tracking existing design extremely closely.
Currently, struct block has these options:

* Hash tables.  (Used almost everywhere.)
* Lists that aren't sorted by name.  (Used in blocks that are the body
  of functions, and in Java's dynamic class table.)
* Lists that are sorted by name.  (Used by mdebugread.c in places
  where hash tables should be used.)

Most of these can't grow, but jv-lang.c and mdebugread.c both have
code by which lists can grow.

When the struct block conversion is done, the only change will be that
sorted lists will go away (since they're only used by mdebugread.c,
which should be converted over to using hash tables instead), and that
the common code in jv-lang.c and mdebugread.c to allow lists that grow
will all be in one place.  No other changes: extremely similar data
structures, exactly the same algorithms.

> - Am I correct to think that the objective is to create a directed
>   acyclic graph of nametabs and have lookups search through each in
>   turn.

Not quite as Daniel has explained; C++'s name lookup rules are pretty
complicated.  Which isn't to say that we have to track those name
lookup rules perfectly: e.g. it's not the end of the world if we don't
notice that a name lookup is ambiguous where a C++ compiler would be
required to notice that.  But it is, I think, a bad idea if we miss a
symbol that we should find, or if we return the wrong symbol instead
of the right one.

> In terms of operations, I would concentrate on determing exactly GDB
> needs (rather than you think it needs) GDB is 15 years old so chance
> has it the operations have been identified already.  I know of two
> operations off hand:

> 	print foo
> which gets turned into struct symbol *lookup("foo",``block'') and,
> 	print foo<tab>
> which turns into ``const char **tabexpand("foo", ``block'')''.  Any others?

I don't see tabexpand anywhere.  Maybe it's been subsumed by
search_symbols?

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Daniel Berlin]

Having done this for regcache and reggroup it is worth it -> you get
>> to see what actually works rather than what everyone else thinks
>> should work.  You can also pick out the cleanups that will make the
>> final change easier.  For instance - tightening up the way GDB
>> creates symbol tables (DanielB suggested moving psymtab into stabs)
>> an performs lookups on them.
>
> Personally, I'd rather tighten up the interface to symbol lookups
> first and only then move on to optimizations like changing how
> reading in a part of the symbol information is implemented.

These are orthogonal issues. Reading in part of the symbol information 
is *not* an optimization (as the source stands now). It is a necessity 
controlled *by the symbol lookup*.
If psymtabs were private to stabs, then this would not be the cast 
anymore, but as it stands now, the readin of psymtabs and conversion to 
symtabs is controlled by the symbol lookup functions.
If your lookup doesn't do this as well, *and* you don't change how 
symbol tables are created (ie you do nothing), stuff will break.

>
>>   Instead, initially, I think these tables could be simple linear
>>   lists (that is what ``struct block'' currently implements so it
>>   can't be any worse :-) (just the global / final table is special
>>   :-).
>
> For struct block, I'm tracking existing design extremely closely.
>
No offense, but you shouldn't do that.
The current design does *not* scale. Or at least, not until hash tables 
were introduced, which happened in the past 3 months.
I've only tested scaling of hash tables up to 100 meg of debug info. 
Even then, due to the number of blocks one has to search, things start 
to get a bit slow.  There are plenty of projects these days with 500 or 
1 gig of debug info.
You *need* to be thinking about these things whenever you design the 
data structures and algorithms.
The reason GDB was so slow on these large cases before hash tables is 
precisely because nobody seemed to even consider what would happen 10 
years in the future.
It's perfectly reasonable to assume that in 10 years, we will have 10x 
as much debug info to deal with.
If we don't, great.
If we do, and we haven't even considered it, we are *really* screwed.

> Currently, struct block has these options:
>
> * Hash tables.  (Used almost everywhere.)
This is a new development.

> * Lists that aren't sorted by name.  (Used in blocks that are the body
>   of functions, and in Java's dynamic class table.)
> * Lists that are sorted by name.  (Used by mdebugread.c in places
>   where hash tables should be used.)
>
> Most of these can't grow, but jv-lang.c and mdebugread.c both have
> code by which lists can grow.
>
> When the struct block conversion is done, the only change will be that
> sorted lists will go away (since they're only used by mdebugread.c,
> which should be converted over to using hash tables instead), and that
> the common code in jv-lang.c and mdebugread.c to allow lists that grow
> will all be in one place.  No other changes: extremely similar data
> structures, exactly the same algorithms.

Which haven't served particularly well for the past 5 years (before 
that, maybe).
No offense, and not your fault.
And i'm not saying they *aren't* adequate.
It just needs more thought than "it's currently done this way, thus, we 
should do it that way in the future".
>
>> - Am I correct to think that the objective is to create a directed
>>   acyclic graph of nametabs and have lookups search through each in
>>   turn.
>
> Not quite as Daniel has explained; C++'s name lookup rules are pretty
> complicated.  Which isn't to say that we have to track those name
> lookup rules perfectly: e.g. it's not the end of the world if we don't
> notice that a name lookup is ambiguous where a C++ compiler would be
> required to notice that.
No, we should actually be able to do exactly this.
Even if we *don't*, we should be able to.
>  But it is, I think, a bad idea if we miss a
> symbol that we should find, or if we return the wrong symbol instead
> of the right one.
>
Which is what happens if you don't track the name lookup rules 
perfectly.
THe rules specify what is ill formed. If you find symbols you 
shouldn't, it's not only confusing to the user, it's the wrong symbol.

Re: struct environment

[David Carlton]

On Tue, 17 Sep 2002 15:49:57 -0400, Daniel Berlin <dberlin@dberlin.org> said:

>> Personally, I'd rather tighten up the interface to symbol lookups
>> first and only then move on to optimizations like changing how
>> reading in a part of the symbol information is implemented.

> These are [not? - DBC] orthogonal issues. Reading in part of the
> symbol information is *not* an optimization (as the source stands
> now). It is a necessity controlled *by the symbol lookup*.

> If psymtabs were private to stabs, then this would not be the cast
> anymore, but as it stands now, the readin of psymtabs and conversion
> to symtabs is controlled by the symbol lookup functions.

Right.  So you juggle the layers by which global symbol lookups
happen, leaving the implementation more or less the same as it
currently is but designing the interface so that it supports future
flexibility.  For example, we could modify the current design to,
rather than first search all the symtabs and then all the psymtabs,
search each file's symtab and psymtab (and minimal symbol table)
before moving on to the next file.  (And yes, I know that we have to
get rid of the idea of searching every single file: that's a somewhat
separate issue, and the above should only be taken as a general
illustration rather than a precise suggestion.)  That's 'tighten[ing]
up the interface to symbol lookups'.  Then, eventually, you think
about ways in which to actually use that flexibility to optimize the
process.

I'm not saying that the interface design shouldn't keep in mind future
possible changes.  I'm just saying that I don't want to wait until
those changes are in place before changing the interface.

>> For struct block, I'm tracking existing design extremely closely.

> No offense, but you shouldn't do that.  The current design does
> *not* scale. Or at least, not until hash tables were introduced,
> which happened in the past 3 months.

> I've only tested scaling of hash tables up to 100 meg of debug
> info. Even then, due to the number of blocks one has to search,
> things start to get a bit slow.  There are plenty of projects these
> days with 500 or 1 gig of debug info.

Yes.  But are there plenty of projects with a single block with a
gigabyte of debug info?  I put the words 'for struct block' in there
for a reason: the current design of the global environment doesn't
scale.  But I don't think struct block has the same problems right
now.

And, even if it does, I repeat what I said above: it makes sense to me
to first redesign the interface to make it more flexible, and to leave
less-pressing optimizations to a later stage.  (For global symbols,
not searching all files is more pressing whereas not requiring the
current psytab->symtab stuff is less pressing.)

Part of my motivation behind this design is to make it very easy to
change the way you're storing data in a dictionary.  So if, 5 years
from now, we run into blocks for which the current mechanisms really
don't work, the changes that I'm doing now will make it much easier to
change the way those blocks are implemented.

>> Most of these can't grow, but jv-lang.c and mdebugread.c both have
>> code by which lists can grow.

>> When the struct block conversion is done, the only change will be
>> that sorted lists will go away (since they're only used by
>> mdebugread.c, which should be converted over to using hash tables
>> instead), and that the common code in jv-lang.c and mdebugread.c to
>> allow lists that grow will all be in one place.  No other changes:
>> extremely similar data structures, exactly the same algorithms.

> Which haven't served particularly well for the past 5 years (before
> that, maybe).

> No offense, and not your fault.  And i'm not saying they *aren't*
> adequate.  It just needs more thought than "it's currently done this
> way, thus, we should do it that way in the future".

What do you think my motivations are for introducing a special case
just to handle mdebugread.c and jv-lang.c?  That last sentence of
yours above really isn't a very good representation of my thought
process.

>> But it is, I think, a bad idea if we miss a symbol that we should
>> find, or if we return the wrong symbol instead of the right one.

> Which is what happens if you don't track the name lookup rules
> perfectly.

> The rules specify what is ill formed. If you find symbols you
> shouldn't, it's not only confusing to the user, it's the wrong
> symbol.

Maybe.  But it's what we do right now: if we don't find a symbol in a
global block, we search all the static blocks.  My first reaction was
that that's a bad idea; after thinking about it for a while, I'm much
less sure.  Certainly when I get down to more concrete design on
global symbol stuff, I'll raise this issue on the mailing list.

David Carlton
carlton@math.stanford.edu

Re: struct environment

[Eli Zaretskii]

On 5 Sep 2002, David Carlton wrote:

> So I want to add a type 'struct environment' to GDB.  It will be
> completely opaque, with a variety of internal implementations
> available (similar to the way that 'struct block' allows you to use
> either a hash table or a simple list of symbols) sharing a common
> external interface.  I want to start by converting 'struct block' over
> to using this, then converting the global environment over to using
> this, then (probably) 'struct type', and finally getting namespaces to
> work well.

Please keep in mind the need to document this new mechanism.  TIA