------------------------------------------------------------------------------
--                                                                          --
--                         GNAT COMPILER COMPONENTS                         --
--                                                                          --
--               S Y S T E M . S E C O N D A R Y _ S T A C K                --
--                                                                          --
--                                 S p e c                                  --
--                                                                          --
--          Copyright (C) 1992-2019, Free Software Foundation, Inc.         --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
--                                                                          --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception,   --
-- version 3.1, as published by the Free Software Foundation.               --
--                                                                          --
-- You should have received a copy of the GNU General Public License and    --
-- a copy of the GCC Runtime Library Exception along with this program;     --
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
-- <http://www.gnu.org/licenses/>.                                          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

pragma Compiler_Unit_Warning;

with System.Parameters;
with System.Storage_Elements;

package System.Secondary_Stack is
   pragma Preelaborate;

   package SP  renames System.Parameters;
   package SSE renames System.Storage_Elements;

   use type SP.Size_Type;

   type SS_Stack (Default_Chunk_Size : SP.Size_Type) is private;
   --  An abstraction for a heap structure maintained in a stack-like fashion.
   --  The structure is comprised of chunks which accommodate allocations of
   --  varying sizes. See the private part of the package for further details.
   --  Default_Chunk_Size indicates the size of the static chunk, and provides
   --  a minimum size for all dynamic chunks.

   type SS_Stack_Ptr is access all SS_Stack;
   --  A reference to a secondary stack

   type Mark_Id is private;
   --  An abstraction for tracking the state of the secondary stack

   procedure SS_Init
     (Stack : in out SS_Stack_Ptr;
      Size  : SP.Size_Type := SP.Unspecified_Size);
   --  Initialize or reuse a secondary stack denoted by reference Stack. If
   --  Stack is null, create a new stack of size Size in the following manner:
   --
   --    * If Size denotes Unspecified_Size, allocate the stack from the binder
   --      generated pool as long as the pool has not been exhausted.
   --
   --    * Otherwise allocate the stack from the heap.
   --
   --  If Stack is not null, reset the state of the stack. No existing chunks
   --  are freed because they may be reused again.

   procedure SS_Allocate
     (Addr         : out Address;
      Storage_Size : SSE.Storage_Count);
   --  Allocate enough space on the secondary stack of the invoking task to
   --  accommodate an alloction of size Storage_Size. Return the address of the
   --  first byte of the allocation in Addr. The routine may carry out one or
   --  more of the following actions:
   --
   --    * Reuse an existing chunk that is big enough to accommodate the
   --      requested Storage_Size.
   --
   --    * Free an existing chunk that is too small to accommodate the
   --      requested Storage_Size.
   --
   --    * Create a new chunk that fits the requested Storage_Size.

   procedure SS_Free (Stack : in out SS_Stack_Ptr);
   --  Free all dynamic chunks of secondary stack Stack. If possible, free the
   --  stack itself.

   function SS_Mark return Mark_Id;
   --  Capture and return the state of the invoking task's secondary stack

   procedure SS_Release (M : Mark_Id);
   --  Restore the state of the invoking task's secondary stack to mark M

   function SS_Get_Max return Long_Long_Integer;
   --  Return the high water mark of the invoking task's secondary stack, in
   --  bytes.

   generic
      with procedure Put_Line (S : String);
   procedure SS_Info;
   --  Debugging procedure for outputting the internals of the invoking task's
   --  secondary stack. This procedure is generic in order to avoid a direct
   --  dependence on a particular IO package. Instantiate with Text_IO.Put_Line
   --  for example.

private
   SS_Pool : Integer;
   --  Unused entity that is just present to ease the sharing of the pool
   --  mechanism for specific allocation/deallocation in the compiler.

   ------------------
   -- Introduction --
   ------------------

   --  The secondary stack is a runtime data structure managed in a stack-like
   --  fashion. It is part of the runtime support for functions that return
   --  results of caller-unknown size.
   --
   --  The secondary stack is utilized as follows:
   --
   --    * The compiler pushes the caller-unknown size result on the secondary
   --      stack as part of return statement or build-in-place semantics.
   --
   --    * The caller receives a reference to the result.
   --
   --    * Using the reference, the caller may "offload" the result into its
   --      primary stack, or use it in-place while still on the secondary
   --      stack.
   --
   --    * Once the caller has utilized the result, the compiler reclaims the
   --      memory occupied by the result by popping the secondary stack up to
   --      a safe limit.

   ------------
   -- Design --
   ------------

   --  1) Chunk
   --
   --  The secondary stack is a linked structure which consist of "chunks".
   --  A chunk is both a memory storage and a linked-list node. Addresses of
   --  allocated objects refer to addresses within the memory storage of a
   --  chunk. Chunks come in two variants - static and dynamic.
   --
   --  1.1) Static chunk
   --
   --  The secondary stack has exactly one static chunk that is created on the
   --  primary stack. The static chunk allows secondary-stack usage on targets
   --  where dynamic allocation is not available or desirable. The static chunk
   --  is always the "first" chunk and precedes all dynamic chunks.
   --
   --  1.2) Dynamic chunk
   --
   --  The secondary stack may have zero or more dynamic chunks, created on the
   --  heap. Dynamic chunks allow the secondary stack to grow beyond the limits
   --  of the initial static chunk. They provide a finer-grained management of
   --  the memory by means of reuse and deallocation.
   --
   --  2) Mark
   --
   --  The secondary stack captures its state in a "mark". The mark is used by
   --  the compiler to indicate how far the stack can be safely popped after a
   --  sequence of pushes has taken place.
   --
   --  3) Secondary stack
   --
   --  The secondary stack maintains a singly-linked list of chunks, starting
   --  with the static chunk, along with a stack pointer.
   --
   --  4) Allocation
   --
   --  The process of allocation equates to "pushing" on the secondary stack.
   --  Depending on whether dynamic allocation is allowed or not, there are
   --  two variants of allocation - static and dynamic.
   --
   --  4.1) Static allocation
   --
   --  In this case the secondary stack has only the static chunk to work with.
   --  The requested size is reserved on the static chunk and the stack pointer
   --  is advanced. If the requested size will overflow the static chunk, then
   --  Storage_Error is raised.
   --
   --  4.2) Dynamic allocation
   --
   --  In this case the secondary stack may carry out several actions depending
   --  on how much free memory is available in the chunk indicated by the stack
   --  pointer.
   --
   --    * If the indicated chunk is big enough, allocation is carried out on
   --      it.
   --
   --    * If the indicated chunk is too small, subsequent chunks (if any) are
   --      examined. If a subsequent chunk is big enough, allocation is carried
   --      out on it, otherwise the subsequent chunk is deallocated.
   --
   --    * If none of the chunks following and including the indicated chunk
   --      are big enough, a new chunk is created and the allocation is carried
   --      out on it.
   --
   --  This model of operation has several desirable effects:
   --
   --    * Leftover chunks from prior allocations, followed by at least one pop
   --      are either reused or deallocated. This compacts the memory footprint
   --      of the secondary stack.
   --
   --    * When a new chunk is created, its size is exactly the requested size.
   --      This keeps the memory usage of the secondary stack tight.
   --
   --    * Allocation is in general an expensive operation. Compaction is thus
   --      added to this cost, rather than penalizing mark and pop operations.
   --
   --  5) Marking
   --
   --  The process of marking involves capturing the secondary-stack pointer
   --  in a mark for later restore.
   --
   --  6) Releasing
   --
   --  The process of releasing equates to "popping" the secondary stack. It
   --  moves the stack pointer to a previously captured mark, causing chunks
   --  to become reusable or deallocatable during the allocation process.

   ------------------
   -- Architecture --
   ------------------

   --      Secondary stack
   --
   --      +------------+
   --      | Top.Byte  ------------------------+
   --      | Top.Chunk ------------------+     |
   --      |            |                |     |
   --      |            |                v     |
   --      +------------+   +--------+   +-----|--+   +--------+
   --      | Memory     |   | Memory |   | Memo|y |   | Memory |
   --      | #########  |   | #####  |   | ####|  |   | #####  |
   --      |            |   |        |   |        |   |        |
   --      | Next      ---> | Next  ---> | Next  ---> | Next  ---> x
   --      +------------+   +--------+   +--------+   +--------+
   --
   --       Static chunk     Chunk 2      Chunk 3      Chunk 4

   --------------------------
   -- Memory-related types --
   --------------------------

   subtype Memory_Size_With_Invalid is SP.Size_Type;
   --  Memory storage size which also includes an invalid negative range

   Invalid_Memory_Size : constant Memory_Size_With_Invalid := -1;

   subtype Memory_Size is
     Memory_Size_With_Invalid range 0 .. SP.Size_Type'Last;
   --  The memory storage size of a single chunk or the whole secondary stack.
   --  A non-negative size is considered a "valid" size.

   subtype Memory_Index is Memory_Size;
   --  Index into the memory storage of a single chunk

   type Chunk_Memory is array (Memory_Size range <>) of SSE.Storage_Element;
   for Chunk_Memory'Alignment use Standard'Maximum_Alignment;
   --  The memory storage of a single chunk. It utilizes maximum alignment in
   --  order to guarantee efficient operations.

   --------------
   -- SS_Chunk --
   --------------

   type SS_Chunk (Size : Memory_Size);
   --  Abstraction for a chunk. Size indicates the memory capacity of the
   --  chunk.

   type SS_Chunk_Ptr is access all SS_Chunk;
   --  Reference to the static or any dynamic chunk

   type SS_Chunk (Size : Memory_Size) is record
      Next : SS_Chunk_Ptr;
      --  Pointer to the next chunk. The direction of the pointer is from the
      --  static chunk to the first dynamic chunk, and so on.

      Size_Up_To_Chunk : Memory_Size;
      --  The size of the secondary stack up to, but excluding the current
      --  chunk. This value aids in calculating the total amount of memory
      --  the stack is consuming, for high-water-mark update purposes.

      Memory : Chunk_Memory (1 .. Size);
      --  The memory storage of the chunk. The 1-indexing facilitates various
      --  size and indexing calculations.
   end record;

   -------------------
   -- Stack_Pointer --
   -------------------

   --  Abstraction for a secondary stack pointer

   type Stack_Pointer is record
      Byte : Memory_Index;
      --  The position of the first free byte within the memory storage of
      --  Chunk.all. Byte - 1 denotes the last occupied byte within Chunk.all.

      Chunk : SS_Chunk_Ptr;
      --  Reference to the chunk that accommodated the most recent allocation.
      --  This could be the static or any dynamic chunk.
   end record;

   --------------
   -- SS_Stack --
   --------------

   type SS_Stack (Default_Chunk_Size : SP.Size_Type) is record
      Freeable : Boolean;
      --  Indicates whether the secondary stack can be freed

      High_Water_Mark : Memory_Size;
      --  The maximum amount of memory in use throughout the lifetime of the
      --  secondary stack.

      Top : Stack_Pointer;
      --  The stack pointer

      Static_Chunk : aliased SS_Chunk (Default_Chunk_Size);
      --  A special chunk with a default size. On targets that do not support
      --  dynamic allocations, this chunk represents the capacity of the whole
      --  secondary stack.
   end record;

   -------------
   -- Mark_Id --
   -------------

   type Mark_Id is record
      Stack : SS_Stack_Ptr;
      --  The secondary stack whose mark was taken

      Top : Stack_Pointer;
      --  The value of Stack.Top at the point in time when the mark was taken
   end record;

   ------------------
   -- Testing Aids --
   ------------------

   --  The following section provides lightweight versions of all abstractions
   --  used to implement a secondary stack. The contents of these versions may
   --  look identical to the original abstractions, however there are several
   --  important implications:
   --
   --    * The versions do not expose pointers.
   --
   --    * The types of the versions are all definite. In addition, there are
   --      no per-object constrained components. As a result, the versions do
   --      not involve the secondary stack or the heap in any way.
   --
   --    * The types of the versions do not contain potentially big components.

   subtype Chunk_Id_With_Invalid is Natural;
   --  Numeric Id of a chunk with value zero

   Invalid_Chunk_Id : constant Chunk_Id_With_Invalid := 0;

   subtype Chunk_Id is
     Chunk_Id_With_Invalid range 1 .. Chunk_Id_With_Invalid'Last;
   --  Numeric Id of a chunk. A positive Id is considered "valid" because a
   --  secondary stack will have at least one chunk (the static chunk).

   subtype Chunk_Count is Natural;
   --  Number of chunks in a secondary stack

   --  Lightweight version of SS_Chunk

   type Chunk_Info is record
      Size : Memory_Size_With_Invalid;
      --  The memory capacity of the chunk

      Size_Up_To_Chunk : Memory_Size_With_Invalid;
      --  The size of the secondary stack up to, but excluding the current
      --  chunk.
   end record;

   Invalid_Chunk : constant Chunk_Info :=
                     (Size             => Invalid_Memory_Size,
                      Size_Up_To_Chunk => Invalid_Memory_Size);

   --  Lightweight version of Stack_Pointer

   type Stack_Pointer_Info is record
      Byte : Memory_Index;
      --  The position of the first free byte within the memory storage of
      --  Chunk. Byte - 1 denotes the last occupied byte within Chunk.

      Chunk : Chunk_Id_With_Invalid;
      --  The Id of the chunk that accommodated the most recent allocation.
      --  This could be the static or any dynamic chunk.
   end record;

   --  Lightweight version of SS_Stack

   type Stack_Info is record
      Default_Chunk_Size : Memory_Size;
      --  The default memory capacity of a chunk

      Freeable : Boolean;
      --  Indicates whether the secondary stack can be freed

      High_Water_Mark : Memory_Size;
      --  The maximum amount of memory in use throughout the lifetime of the
      --  secondary stack.

      Number_Of_Chunks : Chunk_Count;
      --  The total number of static and dynamic chunks in the secondary stack

      Top : Stack_Pointer_Info;
      --  The stack pointer
   end record;

   function Get_Chunk_Info
     (Stack : SS_Stack_Ptr;
      C_Id  : Chunk_Id) return Chunk_Info;
   --  Obtain the information attributes of a chunk that belongs to secondary
   --  stack Stack and is identified by Id C_Id.

   function Get_Stack_Info (Stack : SS_Stack_Ptr) return Stack_Info;
   --  Obtain the information attributes of secondary stack Stack

end System.Secondary_Stack;