Re: Interesting containers problem.

["Randy Brukardt" <randy@rrsoftware.com>]

"Peter Chapin" <PChapin@vtc.vsc.edu> wrote in message 
news:alpine.CYG.2.11.1504171506500.2268@WIL414CHAPIN.vtc.vsc.edu...
> On Fri, 17 Apr 2015, Shark8 wrote:
>
>> Ok, so let's say we have a type for Identifiers:
>
> [snip]
>
>> And that's all well and good; however, there is one limitation here that 
>> is revealed when you need nesting scopes -- there is, apparently, no way 
>> to define an Element_Type to feed to Indefinite_Ordered_Maps which is an 
>> instance of Indefinite_Ordered_Maps.Maps or an instance of Variable_Data 
>> (by way of a variant record; even one which is forward declared).
>>
>> What would be the proper way to handle this sort of situation?
>
> Perhaps using access types directly? What if the Element_Type of the Map 
> is an access type that points at an incomplete type, where the completion 
> follows the instantiation of the Maps generic?

Bleech. Using access types means that you have to handle the memory 
management, defeating the #1 value of the containers. Typically, you can use 
cursors as references between related containers, and I think that is 
preferable.

To answer the OPs question, a symbol table for a language like Ada is a 
multiway tree. That's one reason I pushed for a multiway tree container in 
Ada, as it seems to be a common data structure. So I'd use a multiway tree 
as the basic structure. Identifier lookups would use a map (as you noted), 
and the things that each identifier points at is a list of the symbol table 
nodes associated with that identifier. So the lookup data is a map of lists 
of tree cursors. Hiding then is dealt with by checking the relationship of 
the nodes, or possibly by maintaining a visibility flag in the symbol 
records.

Note that for Ada, one does not prune the lists of identifiers immediately; 
that's the job of the resolver mechanism (because of homographs). The above 
is essentially how Janus/Ada deals with the symboltable (using access types 
since there were no containers in 1981!). Dealing with hiding isn't pretty 
and I don't think there is any way to make it pretty. Perhaps there is 
something elegant that can be done for a simpler language, but since there 
is only one language that matters, who cares? ;-)

                                           Randy.