Implementation Module 1 Protected Records Operator Visibility Child Packages January 1991 Ada 9X Mapping/Revision Team Copyright (C) 1991,1992 Intermetrics, Inc. Copying permitted if accompanied by this statement Note to the reader (February 1992): Some of the material in these implementation modules is out of date. Please refer to the most recent Mapping Specification (version 4.0) for the definition of the semantics for the features. However, many of the implementation models suggested still apply, even though the definitions of the features have been improved and tightened over the past year. Note that the "MI"s (Mapping Issues) referenced are not widely available, but the relevant material has all been extracted either into the Mapping Rationale (Version 3.1) or the Mapping Specification (version 4.0). Protected_Records_With_Simple_Requeue 1.1 Overview_of_Protected_Records For Ada 9X, we propose to provide an intermediate-level building block for the user definition of synchronization mechanisms. This building block is oriented around shared data, rather than around a thread of control. We propose to have a specialized record type; the language implementation will guarantee the mutu- ally exclusive access to its components. This record type is referred to as a protected record type. Each instance of this type will be associated with a single lock. Locking operations on the instance are distinguished syntactically, by being declared as visible or private components of the protected record (all of the data components are private), and called using a pre- fix notation much like a task entry call. Locking operations are either functions, procedures, or entries. Each locking operation takes the "prefix" object as an implicit parameter, implicitly in for functions, and implicitly in out for procedures and entries. Entries have a barrier expression (guard) associated with them. The caller of the entry will not proceed (to perform the entry body) until the expression evaluates to True. 1.2 Purpose This implementation module describes the basic protected record feature, with minimal interaction with other features. Only the simple requeue (i.e. non-abortable) is described here. We are interested in feedback on the following issues: * Clarity, completeness, and consistency of the semantic specification. * The feasibility of efficient implementations, and possible adjustments to improve it. * Ease of integration with the rest of the RTS, and interac- tions with other features of Ada83 tasking. * The ability to implement protected records without an addi- tional layer of low-level locks. Also, the validation of the claim that all protected record instances can be allo- cated and initialized by the generated code. 1.3 Proposed_Change 1.3.1 Proposed Syntax Protected Records protected_declaration ::= protected_specification; protected_specification ::= protected [type] identifier [discriminant_part] is { protected_operation_declaration } { representation_clause } [ private { protected_operation_declaration } { representation_clause } ] record component_list end [ protected_simple_name ] protected_operation_declaration ::= subprogram_specification ; | entry_declaration protected_body ::= protected body protected_simple_name is { protected_operation_body } end [ protected_simple_name ]; protected_operation_body ::= subprogram_body | entry_body entry_body ::= entry identifier [(for identifier in discrete_range)] [ formal_part ] when condition [ is [ declarative_part ] begin sequence_of_statements [ exception . . . ] end [ entry_simple_name ]]; requeue_statement ::= requeue entry_name; 1.3.2 Terminology 1.3.2.1 Non-Locking Operations Non-locking operations are those operations which are defined in the enclosing package of the type and have an operand or a result of the type. 1.3.2.2 Suspension (of a task) Suspension of a task involves the runtime system (RTS) scheduler, and represents a state change in the RTS. Suspension usually occurs when a task is waiting for an event, and it is not known how long it will be before the event occurs. Examples are accepts, entry calls when the barrier is false, delays, etc. In these cases it is common to allow the task to relinquish control of the processor and wait for the event in one of the RTS maintained queues. 1.3.2.3 Contention (for a resource) Contention is distinct from suspension, and happens only in multi-processor environ- ments. In a single-processor, the contention state is a deadlock. When more than one processor (or a task which runs on it) wishes to gain a mutual exclusive access to a resource, and it is known that the duration of which each processor will hold the resource is short and bounded, then the common way to achieve that is through busy-waiting. Usually, the system bus is the arbitrator in these cases, and the runtime system in not involved. Therefore, it may be possible for interrupt handlers (in the generic sense) on multi-processors to contend for such access, but usually they are not allowed to suspend themselves (due to the unknown state in which the RTS was interrupted). It is also obvious that unless special hardware support exists, no priority rules are honored in this state, and starvation is pos- sible. It is commonly the responsibility of the system and software design to ensure that these consequences are dealt with. 1.3.3 Rules Locking procedures and entries are mutually exclusive with all other locking operations. Locking functions may operate in parallel with one another. In addition, an entry has an "entry barrier" expressed as a boolean condition. A call on a protected record entry is suspended until the entry barrier evaluates to True and then the operation is performed under mutual exclusion. The barrier expression may depend on the protected record data, data global to the protected record type, and the entry family index. The barrier expression is always evaluated under the protection of the lock. The code in the locking subprograms and entry bodies may depend on the parameters in addition to the above data. The normal rules about asynchronous access to shared variables apply here to the access to data global to the pro- tected record type. 1.3.4 Notes on Syntax The syntax is intentionally similar to the syntax for tasks. It allows for a "singleton" protected record, as well as a protected type (just as tasks do). The pro- tected record as a whole may be referred to from within the pro- tected body by using the protected body identifier (i.e. the type or singleton-object name), as with a task type. Only subprograms and entry bodies may be declared in a pro- tected body, Every entry body must include an entry barrier, specified as a when condition. The entry body will not be entered until the condition is true. If no body is provided after the entry bar- rier, the entry has no side effects, and is strictly used as a barrier. Subprograms which have protected records as their formal parameters, when declared outside the protected type specification are not immediately locking, but can still be derivable subprograms of the type, if declared in the package specification enclosing the protected type specification. Locking subprograms and entries declared after the keyword private in the spec of a protected record type are private to the immediately enclosing package. Protected types are considered limited types, as tasks are. Furthermore, they are required to be passed and returned by reference. The syntax "(for identifier in discrete_range)" is used to refer to the family member index within the barrier expression or the entry body. The discrete_range denotes the entry family. 1.3.5 Requeuing Entry bodies may exit using the requeue statement. The specified entry must have the same parameter pro- file as the enclosing entry, or be parameterless. Its net effect is to resuspend the caller until the entry barrier of the new entry is satisfied, and then perform the associated entry body. 1.3.6 Mutual-Exclusion Control Locking procedures and func- tions are non-preemptable (with respect to their ceiling priority levels -- see below), and hence never require a queue for a mono-processor, but may have to contend for the lock on a multi- processor. Barrier evaluation is also non-preemptable, as are the entry bodies once started, but they may requeue on another entry rather than returning. Non-preemptability is guaranteed by associating (via a pragma) a ceiling priority with a protected type/record. A run- time (or compile-time) error will result if a task requests a lock on a protected record when its priority exceeds the ceiling priority of the protected record. While inside the protected body, the task operates at this ceiling priority non-preemptively (i.e. no time-slicing/round-robin), so no other potential user of the protected record can preempt it. As a default, the ceiling priority of a protected record will be the maximum non-interrupt priority level (System.Priority'LAST); this level will ensure non-preemption but will not mask interrupts. If a different priority is needed, then pragma PRIORITY (or INTERRUPT_PRIORITY, see below) may be used. 1.3.7 Interrupt Masking In addition to specifying a ceiling priority, a lock may mask one, or more, specific interrupts. This permits one of its locking procedures to be called from the interrupt level. Specific masking is not strictly necessary if ceiling priorities in the range reserved for interrupts are allowed, and have the effect of masking interrupts at the associ- ated levels and below. Pragma INTERRUPT_PRIORITY may be used instead of PRIORITY to specify priorities in this range. Speci- fying Interrupt_Priority'LAST is equivalent to completely disabling interrupts. Since on some architectures, specific masking is efficient and desirable, pragma MASKED may be speci- fied; its effect will be to mask the specific attached interrupt whenever the protected record is locked (in addition to raising the priority to the specified ceiling prior- ity). Finally, on some architectures (which support arbitrary locked bus cycles), the most efficient protected record uses bus locks, and does not normally have entries, only locking subpro- grams. Declarations of such protected types would normally have to be provided by the vendor, such as a test-and-set type. Such a protected type would be specified as being implemented with a bus lock, and all of the locking operations defined as intrinsics. (see MI-IO03.Intrinsic). A vendor may supply another pragma, BUS_LOCK, to allow the creation of protected records with arbi- trary code, protected using bus locks, if supported by the archi- tecture. 1.3.8 Restriction on Locked Code When holding a lock, a task may not suspend for any reason, including an entry call, an accept, a selective wait (without an else part), a delay state- ment, task activation or termination, etc. 1.3.9 Synchronization Points Each use of a locking state- changing operation would be synchronizing with other tasks per- forming any locking operation on the same protected record instance. 1.3.10 Reliance on Protected Record State The straight- forward way to describe the behavior when a protected record changes its state is that after the change, and without releasing the lock, barrier expressions are evaluated for all entries with non-empty queues, (in priority order), and each true evaluation causes the corresponding entry body to be executed, until there are no more waiters with a satisfied barrier. This model suggests that the task which changes the state of a protected record is the one that actually evaluates all the expressions and executes all the bodies. This is not required though, and other implementations may be provided as long as the invariant is maintained that callers queued at the time of the state-changing operation whose barrier evaluates to true are ser- viced without allowing other intervening operations to lock this protected record, including as part of queuing new entry callers. 1.3.11 Timed/Conditional Entry Calls An extension to the pro- tected record idea which is not described in this module, is the incorporation of protected records with timed/conditional calls. We provide a description of this capability here in order to give it an early exposure, and to allow both implementors and users to prepare and plan for this extension. Entry calls on protected records will be treated just like tasking entry calls, and will be allowed in conditional and timed entry call constructs. If the call cannot proceed immediately then: * If the call is conditional, it will be cancelled, and the else part will execute. * If the call is timed, it will be queued (if not already timed-out). If the timeout expires before the entry body can execute (i.e. before the corresponding barrier is true), the call will be cancelled, and the sequence_of_statements after the delay will execute. 1.4 Implementation 1.4.1 General The general model of implementation is one in which the compiler, after allocating and initializing the appropriate data-structures, calls the RTS to accomplish the pro- cessing. We assume out-of-line calls to the runtime system but this is not the only way to implement it. In fact, we predict that major portions of the processing could be inlined including the barrier expression evaluation and the entry body execution. We have chosen the out-of-line approach for clarity reasons only. Because no new data or entries may be declared in a pro- tected type body, the compiler has all the information to allo- cate and initialize the data structures for any protected record instance given visibility only on the protected type specifica- tion. Therefore allocation does not require an extra level of indirection, and can be made on the stack (or on a heap, if new is used). In this context, when we say "protected record data structure," we refer to a structure containing both the user data components, and the necessary fields for the RTS support. Parameters for entries will be passed in memory rather than registers, so they can easily be accessed after suspension by another task performing the entry body on their behalf, without requiring a complete context-switch. The barrier expression will be transformed into a boolean func- tion. Locking subprograms, entry bodies, and the barrier functions will have an implicit parameter which is the protected record instance. For entry families, entry bodies and barrier functions will additionally have the member index as a parameter. All internal operations on protected records such as queu- ing, dequeuing, and evaluating barrier expressions, should be performed under the protection of the associated lock. We ignore here the possibility of aborting a task while it is holding the lock. This is mainly for simplicity reasons. Other proposed changes address this issue specifically, and con- tain specific semantics for the treatment of abortion. Those changes are beyond the scope of this module. 1.4.2 Single-Processor vs Multi-Processor Implementation It is important to distinguish between single and multi-processor implementations. On a monoprocessor, no locks need to actually exist; raising the priority, checking the ceiling rules, inhibit- ing preemption, and possibly masking certain interrupts, would be adequate to ensure exclusive access to the protected record instance. For multi-processors, a data-structure for the lock needs to exist and be addressable from all CPU's (allocated in uncached storage if there exist multiple inconsistent caches). This data structure will have a test-and-set word, and/or possibly a reader count. 1.4.3 Data Structures (for the general MP case): 1.4.3.1 General Description In the canonical implementation model described below, we assume the following data structures: * Qel (queue element): Instances of this type are moved around on the various queues. All Qel's can be allocated and often initialized by the compiler. A Qel contains: A pointer to the protected record instance on which it is queued, a pointer to the call parameters, the entry id and family index, and various links. * PR_Rec: This is the data structure containing the actual components of the protected record instance plus all the fields needed for the RTS support such as: The PR priority and exclusion information, a pointer to a type descriptor, and a queue head for waiting tasks. * Both barrier expressions and entry bodies' code are represented as pointers to the appropriate code segments. Arrays of such pointers are filled in by the compiler for each distinct protected record type. * Each entry is represented by a record containing two fields: The Entry_Name_Index which serves as a pointer to the code pointers array, and Entry_Family_Index which is a parameter for the barrier expression function. * Queues: each protected record instance will have a queue head associated with it which contains all waiting callers on entries of this instance. This queue is a two- dimensional priority queue of Qel's. The row is a priority based list of callers for different entries. Each Qel in this row is the queue head of callers on the same entry, sorted in a priority order. The guard expression has always the same value for an entire column. Alternative implementations might use arrays and/or more sophisticated prioritized queues. We have proposed this two-dimensional linked list structure for simplicity. 1.4.3.2 Ada Specifications type Storage_Element is range 0..2**System.Storage_Unit-1; type Storage_Array is array(Positive range <>) of Storage_Element; type Entry_Name_Index is range 0..Integer'LAST; type Entry_Family_Index is range 0..Integer'LAST; type Entry_Desc_Rec is -- Unique identification of a single entry or member of entry family record Entry_ID : Entry_Name_Index; Member_ID : Entry_Family_Index; -- "0" means not in a family end record; type PR_Rec (Num_Entries : Entry_Name_Index; Component_Size : Natural); type PR_Access is access PR_Rec; type Param_Access is access ..; -- A pointer to the parameter area type Barrier_Function is access function ( Pr_Data : PR_Access; Family_Index : Entry_Family_Index ) return Boolean; -- This is a general access pointer to a boolean function. The two -- formal parameters are the address of the protected record and -- the family member index. The function body itself is generated -- by the compiler. type Operation_Procedure is access procedure ( Pr_Data : PR_Access; Family_Index : Entry_Family_Index; Parameters : Param_Access ); -- This is a general access pointer to a procedure. The formal parameters -- are the address of the protected record, the family member index, and -- a pointer to the parameters area. type Barrier_Pointers_Array is array (Entry_Name_Index range <>) of Barrier_Function; type Operation_Pointers_Array is array (Entry_Name_Index range <>) of Operation_Procedure; type Pr_Type_Desc (Num_Entries : Entry_Name_Index) is -- A descriptor for each unique protected record type -- Filled in by the compiler record Barriers : Barrier_Pointers_Array (1..Num_Entries); Operations : Operation_Pointers_Array (1..Num_Entries); end record; type P_Pr_Type_Desc is access Pr_Type_Desc; type Exclusion_Enum is (None, Non_Interruptible, Maskable, Non_Preemptable); -- This is an enumeration of the various ways to achieve the mutual -- exclusion of access to the protected record instance (derived from -- defaults, pragmas, and priorities). type Exclusion_Info is record Exclusion : Exclusion_Enum; Interrupt : Interrupt_ID; -- If a specific interrupt has to be disabled/masked when the -- protected record instance is accessed (determined when the -- object is created), the Interrupt_ID will be recorded here. Test_And_Set_Word : Integer; Lock_Pr : System.Priority; -- The lock's ceiling priority Owner : TCB_ID; -- The owning task of this QEL. end record; type PR_Rec (Num_Entries : Entry_Name_Index; Component_Size : Natural) is -- This is the data structure created by the compiler per each protected -- record instance record Type_Desc : P_Pr_Type_Desc; -- A pointer to the protected record's -- type descriptor Ex : Exclusion_Info; Queue_Head : P_Qel; -- This queue may be FIFO or priority-based, depending on the -- queuing policy in effect. Components : Storage_Array(Component_Size); -- The actual declared components of the Prot. Rec. end record; type Qel_Rec; type P_Qel is access Qel_Rec; type Double_Link_Rec is record Forward_Link : P_Qel; Backward_Link : P_Qel; end record; type Qel_Rec is record Which_Pr : P_Pr; -- Which PR is called Entry_Desc : Entry_Desc_Rec; Parameters : Param_Access; Exception_Raised : Exception_ID := No_Exception; -- If exception was raised during the barrier evaluation or OP -- (entry body) execution. Next_Entry : Double_Link_Rec; -- link across row of entries Next_Caller_Same_Entry : Double_Link_Rec; -- link down column of callers end record; 1.4.4 Creating an Instance of a Protected Record Since the size of the protected record is known to the compiler, it will be able to allocate it either on the stack or on the heap depending on whether an object is declared or allocated via new. All the fields will be initialized (queue-headers will be initialized to be empty). A separate proposed change (MI-RT11.IntHand) discusses the association of protected records with interrupts. Usually (except when the association is static via a pragma), the partic- ular Interrupt_ID is not known at the time of object creation, so only a place-holder will be allocated, to be filled later by the BIND operation. 1.4.5 Mutual Exclusion We assume the presence of Lock/Unlock primitives which are being used by the rest of the code: procedure Lock (PR : P_Pr); procedure Unlock (PR : P_Pr); As mentioned above, these primitives will work quite differently in a single- processor environment or in a multi-processor one. Lock will: * Compare the priorities of the calling task and the protected record instance, and if the former is higher, raise a Lock_Error. * Raise the priority of the calling task to that of the pro- tected record instance. * Based on the Exclusion_Info of the instance, will either disable interrupts, mask a specific one, disable preemption, use BUS-LOCKs, etc. * On a multi-processor, contend for the lock, (e.g. by test- and-set.) When the lock is acquired, this fact will be recorded in the object. There are many ways to optimize this part depending on the characteristics of the system (number of CPU's, type of bus, etc.). Since failing to get the lock may be quite rare, the contending task may continue with the busy-wait, or, alternatively, lower the priority to the original value, and call the Dispatcher to find somebody else to run. Unlock will do the reverse. 1.4.6 Locking Procedures and Functions Locking procedures and functions have the protected record as an additional implicit parameter. For procedures, this parameter is in out, and for functions, it is in. The checks in the latter case are done at compile time just like any other subprogram's in parameter. On multi-processors, if the hardware supports it, shared-read locks may be used when locking functions are called. However, this is not required, and the model is consistent with either implementa- tion technique. Generating code for a locking subprograms is similar to gen- erating code for any other subprograms with the addition that the protected record instance is locked upon entry. On function epi- logue, it will be unlocked. On procedure epilogue, since the state of the protected record instance might have been changed, all the non-empty queues of the object must be checked, and pos- sibly their operations performed (see below). Finally, the lock will be released. The scanning step can be optimized away, if it can be determined that the state has not been changed. 1.4.7 Entry Calls After contending for the lock, the barrier expression is evaluated, and if true, the entry body will be exe- cuted just as a locking procedure with the same epilogue process- ing. In general, the barrier expression needs to be evaluated only if the corresponding queue is empty (this latter check is safe since the object is locked). It cannot be the case that the queue is non-empty and the barrier is true. (This invariant has to be maintained in the presence of exceptions and aborts.) How- ever, based on the proposed queue structure, it is faster to first evaluate the guard, and only if false, to actually walk the queue and place the Qel in the appropriate location. Then the lock is released, and the task suspended. The entry body will be executed later by another task, see below. If an exception is raised while evaluating the barrier expression, the lock should be released, and the exception pro- pagated to the caller. (It cannot be the case that other callers exist on that entry if the evaluation raises an exception. They must have been removed before.) If an exception is raised while executing the entry body, the exception should be propagated to the caller, after scanning the queues, since the state of the protected record might have been changed. 1.4.8 Requeue The requeue statement may only appear immedi- ately within an entry body. (We have proposed a requeue for accept bodies as well.) There are two distinct cases here: * If the requeue is for an entry of the same protected record instance, then the lock is already held. The same process- ing as with entry call occurs. Note that the same Qel is used for the new requeue, and its components are modified accordingly (no additional storage allocation is needed). * If the requeue is for an entry on a different protected record instance. Then the other instance's lock should be acquired (the priority rules guarantee that no deadlock will result from this nested locking). Similarly to a regular entry call, the barrier should be evaluated, and if true the other entry body should be performed. A normal epilogue should then be done on that instance. After that epilogue, the epilogue for the original entry should be done, and its lock released. If the other barrier evaluates to false, the QEL should be placed on the queue, and the lock released. Then the epilogue of the original entry is performed, and the calling task is suspended. In summary, the processing of the other entry call is very similar to a regular one, except that instead of suspension, an indication is returned whether the entry was executed or not. 1.4.9 Scanning the Queues After an Operation The following section describes the processing that occurs each time the state of a protected record instance changes (i.e. after a locking pro- cedure or the execution of an entry body). Before the lock is released the implementation will scan all non-empty queues (we are here assuming priority order, though FIFO is also possible), evaluate corresponding barrier expressions based on the new state of the object, and perform all "ready" entry bodies on behalf of their original callers. Finally, each task whose entry call has completed is resumed. Each queued call will be processed independently, i.e. after a candidate with a true barrier is chosen, its entry body is performed, and since the state of the object might have been changed, evaluation of barriers starts again. As mentioned above in the semantics description, we assume a model in which a task that modifies the state of a protected record instance, is also responsible for performing the bodies of all waiting entry calls with a true barrier until no more such callers exist, and then release the lock. This is the model that we want to allow the user to rely on. However, other implementa- tions techniques may be possible. In particular, for real-time implementations, it might be possible for the state-changing task to perform the operations of only higher priority callers, and to let the rest execute later, but without releasing the lock. The proposed two-dimensional structure of the queue ensures that a simple walk will visit callers in a priority order, even if more than one entry has callers currently suspended on it. If an exception is raised while evaluating a barrier expres- sion, all currently pending callers need to be released and the exception propagated to them. If an exception is raised while performing the body on behalf of another task, only that task has to be released, and the exception propagated. Since the state of the object was potentially modified, the process of checking other candidates should continue. 1.4.10 Releasing Tasks Whenever the execution of the entry body is done, the corresponding caller has to be woken. As part of this process, exceptions and other states (e.g. timeouts and aborts) have to be checked. Also, since this operation is usu- ally done while a lock is being held, special attention has to be given to ensure a correct implementation of the task suspension primitives. The two major race conditions that have to be avoided are: 1. When a task is released just before it is about to suspend itself. 2. When a timeout or abort occurs just after the completion of the entry body (not yet discussed in this module). 1.4.11 Checking Restrictions Some of the restrictions on the kinds of constructs that may appear in locking subprograms may be checked at compile-time. However, there are many circumstances that can only be checked at run-time. When a task holds a lock, it cannot suspend itself (it can be preempted or requeued though). This check can be simply accomplished by having a "Suspendable" flag, which is tested on each, potentially suspend- ing operation. Most of the ceiling priority rules must also be checked at run-time. Since the ceiling priority of each protected record instance is recorded in its data-structure, any attempt to lock it must verify that the priority of the calling task is not higher than that of the protected record. Regarding accessibility of data; all the restrictions are to be enforced at compile-time. 1.4.12 Timed/Conditional Entry Calls The possibility of timed or conditional entry calls can substantially affect the implemen- tation of protected records. That is why we provide here an early exposure to these ideas to allow the design to take them into account. The presence of the else clause requires the primitive that checks a barrier and then either performs the entry body or queues the caller, to have an additional parameter, and be prepared to do neither (and return an appropriate status upon its return). The presence of the delay alternative introduces the possi- bility of more race conditions if the timeout expires just before the entry body is about to start or just after it finishes. These race conditions have to be dealt with. 1.5 References_and_Dependencies 1.5.1 References to MI's Note that the following MI's are not necessary for the implementation of this module. They are men- tioned here for reference and general background only. 1. MI-RT05.RWLocks 2. MI-RT06.PerTask 3. MI-RT08.SharedVar 4. MI-RT09.DynPr 5. MI-RT11.IntHand 6. MI-OO10.LimType 7. MI-OO03.Finalize 8. MI-IO03.Intrinsic 9. MI-OO11.LoopInit 1.5.2 References to Ada 9X Requirements, December 1990 1. R5.2-A(1) Alternative Scheduling Algorithms 2. R5.2-A(2) Common Real-Time Paradigms 3. R5.4-A(1) Non-Blocking Communication 4. Study Topic S5.4-B(1) Asynchronous Multicast 1.5.3 References to Revision Requests RR-0016, RR-0078, RR- 0084, RR-0121, RR-0151, RR-0170, RR-0185, RR-0278, RR-0379, RR- 0543, RR-0658, RR-0697, RR-0737, RR-0241, RR-0434, RR-0515, RR- 0461, RR-0590 Operator_Visibility_ 2.1 Overview This module proposes three changes related to the Ada visibility rules: * Changes to allow derivable or predefined operators defined on a type to be directly visible wherever objects of the type are visible, allowing infix notation to be used in expressions without requiring use clauses. * Changes that allow user-defined operators for a type to be used within a generic instantiation, instead of having the pre-defined operators re-emerge. * Changes that implicitly declare operations on composite types as compositions of the appropriate operators defined for the component types. Note that declarations of operators outside of the package specification defining the type are "second-class citizens" as far as these changes are concerned. Only the primitive operators (those defined where the type is defined) are being given special status. This is because there may be multiple non-primitive declarations, and defining a rule for disambiguating them would be very difficult. The purpose of this implementation module is to provide feedback on the difficulty of this modification, and the impact of the change on existing programs. In particular: * How helpful is it to be provided with the detailed algorithm which is supplied below? * Were you able to use this algorithm within the existing framework of the compiler? * Do the new visibility rules break existing programs, or are they equivalent to the old rules for all practical purposes? * Do the new rules effectively solve the perceived problem with use clauses. 2.2 Basic_Concepts As part of defining derived types, the concept of derivable sub- program is introduced. This is the set of subprograms with an operand or result of the type, that are explicitly or implicitly declared in the visible part of the package spec in which the type is declared (presuming it is declared in a package spec). For the purposes of discussion, we will call the basic operations, predefined operators, derivable subprograms, and enumeration literals the primitive operations of a type. An operation is considered immediately visible within the immediate scope of its declaration. An operation is considered use-visible in the scope of use clause referencing the package where the operation is declared. 2.3 Proposed_Changes 2.3.1 Primitive Visibility The relevant Mapping Issue, MI- OO04.OpVis, proposes that all primitive operations which do not have an identifier as their name (i.e., have an operator symbol, some basic operation construct, or a character literal) are potentially directly visible throughout the scope of the type. To distinguish this visibity from Ada 83 direct visibility, we will call it primitive visibility. It is intended to be similar to that visibility that is afforded to basic operations such as ":=" or "and then". When an operator has primitive visibility, it is not equivalent to saying that it is directly visible throughout its (extended) scope. This is in order to maintain backward compati- bility, and to reduce the flooding of the name space. Consider the following example: function "+"(Left : Integer; Right : My_Int) return My_Int; If this is declared in the same package as My_Int, it becomes primitively visible. However, we do not want expressions like "X+5", where "X" is of type Integer, to suddenly become ambiguous just because this declaration exists in some "far away" package, even though reachable through a chain of of with dependencies. To prevent this situation, primitively visible declarations are only considered after immediately and use-visible declara- tions. Another way of looking at this is that primitively visi- ble declarations need only be considered as candidates when the compiler can determine that an operation has an operand or result of the associated type. In Ada-83 names brought in through use clauses can be hidden by names immediately visible, but not vice-versa. This distinc- tion should be maintained for primitively visible operations as well. That is, a primitively visible operation, within its immediate scope, hides use-visible names. 2.3.2 Primitive Visibility and Generics LRM 12.1.2:14 defines the meaning of an operator within a generic instantiation to be the pre-defined operator of the actual type parameter, as opposed to any user-defined operator which might hide it. We propose that primitive operators which hide predefined operators do so within generic instantiations as well. This means that a type with overridden predefined operators will not have its predefined operators reemerge within a generic. Instead, the user-defined primitive operators will be used. Note, however, that if the "with function ... is <>;" declaration is used to import user-defined operators explicitly, the normal visibility rules will be applied which would allow a local declaration or use-visible declaration to hide the primitive user-defined operator. The difficulty of implementing this proposal is presumably dependent on the mechanisms used to implement generic instantia- tion. The presence of a user-defined primitive operator for an actual type parameter will generally prevent sharing with an instantiation which compiles in calls to predefined operations. Macro expansion implementations of generics will be less affected, since implicit properties of an actual parameter must already be considered when performing basic operations. This proposal makes primitive operators more like basic operations, in that they come along "for free" into a generic instantiation. 2.3.3 Composition of Primitive Operations Finally, we propose that user-defined primitive operators be used rather than prede- fined operators when defining operations on composite types. In particular: 1. Record and array equality and assignment will be based on component primitive equality and assignment, and will be implicitly declared whenever all components define an equal- ity operator or assignment operation as a primitive. 2. Array relationals will be based on component primitive equality and relational operators, and will be implicitly declared whenever the component type provides primitively both equality and the corresponding relational operator. 3. Logical array operations will be based on component primi- tive logical operators, and will be implicitly declared whenever the component type provides as a primitive the corresponding logical operator. 2.4 Implementation 2.4.1 Algorithm for Primitive Visibility Here is a proposed algorithm for handling visibility, implicit conversions, and overload resolution. We expect that the algorithm may not be the most straightforward way to implement the new rules in an existing compiler. Implementers may deviate from this algorithm if it makes more sense, so long as the externally visible effects are (nearly) identical. In any case, we are interested in what algorithm you devise, as well as suggestions toward deriving a more formal description of the rules which would be more appropriate for the Ada Reference Manual. Hopefully this algorithm will provide ideas as to how to imple- ment primitive visibility, and will elucidate the intended effect in a fashion understandable to implementers. We have included a discussion of implicit conversion, even though it doesn't directly bear on primitive visibility, because we have proposed another MI which involves generalization of the concept of universal types (see MI-OO01.ExtPoly). Informally, the rules we are trying to support are: 1. Primitive operators (predefined and derivable) are primi- tively visible throughout their scope, very much like basic operations such as := and and then. 2. Never use an operation of a universal type when an operation of a non-universal type is possible instead. Equivalently, convert from a universal type as close to the "leaves" of the expression tree as possible (as soon as the target type is known unambiguously), and convert to a universal type only when absolutely necessary. 3. Immediately visible declarations hide use-visible declara- tions, which in turn hide declarations visible due only to their being primitive operators. Overloadable use-visible declarations do not hide one another (as in Ada 83). Our other criteria for selecting this algorithm: A. The algorithm should be relatively simple and efficient. B. It should never be necessary to scan all reachable packages to resolve an expression (reachable includes all directly and indirectly withed units). C. Primitive operators and basic operations should not need to be accessible in the symbol table except via the type (or types) with which they are associated. I.e., they don't need to appear separately in the symbol table like stand- alone declarations. D. Implicitly declared operations of universal types (i.e. those inherited from the non-universal type) should only be accessible via the universal type, rather than cluttering up the symbol table like stand-alone declarations. E. No resolution should depend on there being a unique, directly visible type of a particular class (e.g. the famous for I in -1 .. 10 problem). F. Ambiguities should be identifiable in a way that enables the programmer to resolve them easily. G. The rules should not change the resolution of any existing legal Ada 83 expression to a new different legal meaning. The rules may cause a legal Ada 83 expression to become ambiguous or undefined (due to less aggressive overload resolution). However, very few expressions from normal Ada 83 programs should be rejected due to this new algorithm. The Algorithm Assume the input has been parsed, an abstract syntax tree (AST) of nodes has been built, but no semantic checking has been per- formed. At this stage, assume that all constructs involving a prefix followed by a parenthesized list are represented as an Apply node, corresponding to a subprogram application, array indexing or slicing, or type conversion. Also, assume that all infix uses of operators are converted into prefix notation, and also represented as Apply nodes. Finally, assume that all other nodes are represented as either simple names, selected names, or Apply nodes with a specially recognizable prefix to identify the basic operation. Apply nodes have a child node for the prefix, and one or more child nodes for the operands. Simple name nodes have no children, and consist of a single identifier, designator, or literal. Selected name nodes have a single child node for the prefix, and an identifier, designator, or character literal for the selector. The visibility/implicit-conversion/overload resolution is performed with two passes, first a bottom-up walk of the tree, followed by a top-down pass. The two passes perform similar pro- cessing on each node. 2.4.1.1 Generating Interpretations When processing a node of the tree in either pass, a list of possible interpretations of the node is generated, using interpretations of child nodes if any and the result context. The list of interpretations is stored with the node on the bottom-up pass for use by the parent node on both the bottom-up and the later top-down pass. The result context consists of the desired result type (or type class), and additional information to indicate whether the node appears in a context where implicit dereferencing of an access value is permissible. Note that implicit calling of a parameterless (or fully defaulted) subprogram is always permit- ted. In the bottom-up pass, the result type is generally unknown, and will be represented as simply "any type." However, for the top node, the context of the whole expression may determine a smaller class (e.g. "any boolean" for condition expressions in if and while statements). In the top-down pass, the result type of a node will gen- erally be known (though it may be a universal type -- see MI- OO01.ExtPoly). The possible interpretations of child nodes are those remembered from the bottom-up pass. For uniformity, we will represent a class of types by the universal type for the class. For example, "any boolean" will be represented by Boolean'CLASS. 2.4.1.2 Augmenting and Pruning Interpretations Using the result context information, the list of possible interpretations will be augmented by implicit calls, and by implicit dereferenc- ing where allowed. The list will be pruned to those intepreta- tions which are consistent with the result type. Interpretations requiring any implicit conversion (other than to match "any type") are ignored if there is at least one interpretation which doesn't require implicit conversions. Before adding an interpretation to the list, it is checked whether it hides or is hidden by some other interpretation already on the list, and if so, the hidden interpretation is pruned out. If the resulting list of interpretations is empty, then, on the bottom-up pass, the node returns the single interpretation "any type" (presuming that on the top-down pass more result- context may be available). On the top-down pass, a node is con- sidered undefined if there are no interpretations, and ambiguous if there are more than one. 2.4.1.3 Simple names When processing simple name nodes, the identifier or designator is looked up in the enclosing declara- tive regions, and then, if no non-overloadable declaration is found, in the used packages At this point, primitively-visible operators are ignored. In addition, implicitly-declared opera- tions of a universal type are ignored unless the desired result type is that universal type, and the operation can appear parame- terless (e.g. is an enumeration literal or parameterless func- tion). The list of interpretations are augmented and pruned as described above. 2.4.1.4 Selected Names When processing selected name nodes, the list of interpretations of the prefix are considered, and for each which may be followed by a selector, the given selector is looked up in the appropriate declarative region and each possible interpretation of the selected name is added to the list for the node. As above, primitively-visible operators are ignored, as are implicitly-declared universal operations, unless they may appear parameterless and the desired result type is a universal type declared in the same declarative region. The list of interpretations are augmented and pruned as described above. 2.4.1.5 Apply Nodes Processing apply nodes is the most com- plicated. Given the lists of interpretations for the prefix and the operands, each possible combination of interpretations of the operands is considered in turn. For each such combination, the possible interpretations of the prefix are then considered. An interpretation for the apply node as a whole is added for each prefix which is compatible with the operand combination, taking into account defaulted and named parameters. If the prefix is an operator symbol, or is a selected name where the selector is an operator symbol, then primitively- visible interpretations of the prefix must be considered, since they were not included on the original list of prefix interpreta- tions. The type for an operand interpretation, or the desired result type, may be used to locate primitively-visible operators. If the prefix is a selected name, then the operand or result types which are not declared in the region identified by the pre- fix of the selected name are ignored. For each appropriate operand and result type, the set of primitively-visible operators of the type with the same designa- tor as the prefix, and which match this operand or result without conversion, and match the other operands or result as well, are included as interpretations for the apply node. Similar processing is performed for implicitly-declared operations of a universal type, if one of the operands or the result type is a universal type. However, these interpretations are ignored if they require implicit conversion for matching, or if there are ultimately other interpretations for the apply node that require no implicit conversion and are not implicitly- declared universal operations. The list of interpretations are then augmented and pruned as described above. 2.4.1.6 Bottom-Up Pass (first pass) A bottom-up tree walk is performed, generating, augmenting, and pruning the list of interpretations for a child before processing the parent node. 2.4.1.7 Top-Down Pass (second pass) Ultimately one or more interpretations bubble up to the top node, with the resolution of the top node using as its result type/class that provided by the context in which the expression appears. The top-down pass selects interpretations for nodes using essentially the same algorithm as the first pass. Because gen- erally more information is known about the result type, a unique interpretation should result for any semantically correct pro- gram. If on the second pass, any node ends up with zero, or more than one interpretations, the expression is considered undefined or ambiguous, respectively. When the node can be reduced to a single interpretation, then the chosen operand interpretations are passed down to be result types in the operand nodes. If an implicit conversion is required to match an operand, then the formal parameter type is passed down as the result type rather than the operand type ori- ginally passed up. Because a more specific result type is being passed down, additional primitive operations will be considered in the second pass, meaning that the chosen interpretation may not be among those originally passed up. 2.4.2 Generics and Primitive Visibility There is no single implementation model which will necessarily work for this propo- sal, as different implementation of generics will have different difficulties with our proposal. 2.4.2.1 Shared Generics The most difficult situation is prob- ably when generic bodies are always shared among all instantia- tions. This implementation strategy will require that all predefined operators be called through a descriptor. However, most implementations of sharing only share when the actual param- eters of two instantiations are "sufficiently alike." With this proposal, the presence of user-defined primitive operators hiding predefined operators must be considered when determining if two instantiations are sufficiently alike. 2.4.2.2 Macro Expansion after Semantic Analysis A common implementation of generics is to macro-expand a new abstract syn- tax tree (AST) based on a semantically analyzed AST for the gen- eric. This technique relies on the promises made by the generic contract model. Where the language fails to support the model, special case processing is required. In this technique the pre-defined operators are most likely represented by some operator in the tree. They are not resolved into references to declared subprograms. In order to implement the new rules, special processing needs to be added to the the compiler phase which implements the dynamic semantics. This phase would have to check the type when an operator is encoun- tered and translate the operation to the appropriate subprogram call, instead of the intermediate form normally used for the pre-defined operation. The difficulty of this translation is dependent on the implementation of a particular compiler. This kind of translation may be useful for implementing other Ada 9X features, so a general mechanism is desirable. In general, it may be valuable to have a bit vector associ- ated with each type to indicate which of its predefined operators are hidden by user-defined primitive operators. This should allow an easy determination of whether any special processing is required when the type is used as a generic actual parameter, or a component of a type which might have an implicitly declared composite operation (see below). 2.4.2.3 Macro Expansion before Semantic Analysis If an imple- mentation does semantic analysis on each expanded instantiation, then this analysis should naturally implement the desired seman- tics. This is a case where the Ada '83 semantics might have been more troublesome to implement. 2.4.3 Composition of Primitive Operations Providing component-wise semantics for composite types with components that have user-defined primitive operators may not be a major imple- mentation effort. There are already a number of operations within the language which require component-wise operations -- initialization, representation conversion, size calculation, etc., and so the appropriate mechanisms may already exist. As mentioned above, it may be helpful to maintain a bit vector with each type to indicate which predefined operators are over- ridden by user-defined primitive operators. 2.5 References_To_MI's The following MI's should provide a deeper understanding and a motivation for these changes. However, it should not be neces- sary to read the MI's in order to implement the changes. 1. MI-OO01.ExtPoly 2. MI-OO04.OpVis 3. MI-OO05.UDAssign 4. MI-GE01.Contract 5. MI-GE02.GenParams 6. MI-UN09.OverLoadRes Hierarchical_Program_Libraries 3.1 Overview This module proposes three changes relating to program library structure and separate compilation: 1. The restriction that subunits within the same library unit have distinct simple names (even if their expanded names are unique) is removed. 2. Library units may form a hierarchy. A child library unit has full visibility on its parent's private declarations. A child library unit may be declared private, making it inac- cessible outside its parent's sub-hierarchy. 3. Subunit stubs may appear in the private part of a package spec. 3.2 Proposed_Change 3.2.1 Hierarchical Library Units This MI proposes that the structure of a program library be generalized into a hierarchy with the flexibility of with-clause composition at every level. Here is the new syntax for a library package declaration: library_package_declaration ::= [private] package [parent_unit_name .] identifier is ... end [[parent_unit_name .] simple_name]; Analogous changes are supported for library subprograms and bodies. Since library units now may be specified using an expanded name, the name used in a with-clause may now contain dots. The new with-clause syntax would be: with_clause ::= with library_unit_name {, library_unit_name}; A child library unit has visibility to the visible and private part of its parent unit, which must be a library package. A library unit is only visible if it is referenced by a with-clause. This makes the unit visible as though it had been declared within its parent. A non-private library unit may be withed by: 1. The declaration of another library unit with the same parent 2. Any unit which may with its parent unit. A private library unit may be withed by the declaration of another private library unit with the same parent In addition, a private or non-private library unit may be withed by: 1. The body of its parent unit. 2. The body of a unit whose parent unit body may with it. 3. The declaration of a unit whose parent unit declaration may with it. For child library units of a library package: 1. The visible part (or subprogram spec) of a visible child library unit has the same visibility as if it were inserted at the end of the visible part of its parent. 2. Private child library units, and the private part of visible child library packages, behave as if they were inserted after the private part of their parent. Child library subprograms are never considered "derivable subpro- grams," even if they have as a parameter or result a type declared in the visible part of their parent. Child library packages may contain derivations from types declared in the visible part of their parent, and may contain deferred constant declarations for private types declared in their parent. 3.2.2 Subunit Stubs in A Private Part In addition we would allow for the declaration of a subunit stub within the private part of a package spec. Users of inline subprograms or generic units would be dependent on the separate subunit body only, and not on the body of the enclosing package. No special syntax would be introduced for this facility. The only new rule would allow a body_stub to appear in the private part of a package spec. 3.2.3 Unique Subunit Names Given that the program library implementations will have to deal with a general hierarchical name-space for library units, we propose to remove the restric- tion that the simple name of a subunit must be unique within its library unit. 3.3 Implementation The implementation issues are all isolated to program-library management and front-end symbol table processing. Restrictions on unit names in the database associated with a program library may have to be removed to accommodate the "dot- ted" names for units. Withing child units is no different than withing parent units, in so far as symbol table processing is concerned. With processing will have to be modified to enforce the new rules associated with private packages. Child packages must see the full type definition for private types. This basically requires that the symbol table be set up for child packages just as it is for package bodies. Removing the restriction on names of separately compiled units should help simplify implementations which allow simultane- ous compilation into the same program library. The current rules require reserving names in order to guarantee that a subunit name will be unique. This will no longer be necessary. 3.4 References_to_MI's A complete discussion of this proposal, including more extensive changes and a rationale, can be found in MI-SC01.HierLib.