Project :  Bookshelf

Program :  lsadjust

Date Updated : August 28, 1997

Author: Gerry Kovan, University of Toronto


Table of Contents
-----------------

How to read this document.................................. 1.0
Purpose of Program ........................................ 2.0
Syntax of Program ......................................... 3.0
Description of Argumentemts to program .................... 4.0
Description of Nested Layout Model ........................ 5.0
Description of Client Server Layout Model.................. 6.0
Parsing the <tuple files> ................................. 7.0
Parsing the <layout file> ................................. 8.0
Description of Program .................................... 9.0
Glossary ................................................. 10.0


1.0 How to read this document :
-------------------------------

This document is a combination of a man page, and a technical document.
Sections 2.0 through 8.0 contain information on the purpose and 
usage of the program.  Section 9.0 gives a thorough description of
how the program works.  The glossary will probably have to be referred
to often as this document uses some specialized terms.


2.0 Purpose of Program:
-----------------------

Given: 1) old tuple file  2) and its associated old layout file
       3) new tuple file  3) new layout file ( this is OUTPUT of program )
       
 the program will adjust the old layout file so that it corresponds to
 the new tuple file.

This means that:  1) STATIC entities will appear in the new layout file
                     with the same (or slightly adjusted) attributes
                     compared to its attributes in the old layout file 
                                       
                  2) OLD entities will NOT appear in the new layout file
                  
                  3) NEW entities will be layed out and placed in the
                     new layout file


3.0 Syntax of Program:
----------------------

lsadjust [options] <old tuple file> <old layout file>
                   <new tuple file> <new layout file>


4.0 Description of Arguments to program:
----------------------------------------

<old tuple file>  - tuple file that must contain the FACT TUPLE section
                    of the TA grammer
                      
              note : (only relevant for client server layout model)
                     
                     if -so option is not used then the subsystem name
                     is taken from the <old tuple file>.  The subsystem
                     name is built by concatenating the prefix of the 
                     file name part of <old tuple file> with ".ss"
                     
                    e.g
                    
                    <old tuple file> is  "./../bookshelf/LINUX/kernel.tup"
             
                    the name of the subsystem would be "kernel.ss"
                      
                   
                   note: Once the name of the subsystem is determined
                         the program searches its symbol/entity table to 
                         find an entity with that name.  If it does
                         not find one then the program ends with an
                         error message.

              
              note : with -r option the <old tuple file> should only
                     contain relation tuples
                     
                     i.e. 'FACT TUPLE :' header is not required AND
                           $INSTANCE tuples are not required


<old layout file>   - layout file that corresponds to the <old tuple file>
                    - layout file contains the position attributes for
                      each entity in the layout
                    - layout entry is of the form:
                                  
                       
                       entity_name {
                               x = ?
                               y = ?
                          height = ?
                           width = ?
                       }
                       
                     
                               
<new tuple file>  - tuple file that must contain the FACT TUPLE section
                    of the TA grammer


              note : if -sn option is not used then the subsystem name
                     is taken from the <old tuple file>.  The subsystem
                     name is built by concatenating the prefix of the 
                     file name part of <old tuple file> with ".ss"
                     
                    e.g
                    
                    <old tuple file> is  "./../bookshelf/LINUX/kernel.tup"
             
                    the name of the subsystem would be "kernel.ss"
                      
                   
                   note: Once the name of the subsystem is determined
                         the program searches its symbol/entity table to 
                         find an entity with that name.  If it does
                         not find one then the program ends with an
                         error message.

              
              note : with -r option the <new tuple file> should only
                     contain relation tuples
                     
                     i.e. 'FACT TUPLE :' header is not required AND
                           $INSTANCE tuples are not required


<new layout file> - this file will contain the output of the program
                  - this layout will correspond to the <new tuple file>
                  - same format as <old layout file>


[options]



-H<type><val>      - specify minimum height of <type> to be <val>
                   - default Height for each <type> is 30
                   - description of <type>
                     e - entities in container
                     c - client entities (if client server model used)
                     s - server entities (if client server model used)


   This switch applies only if switch -c2 or -c3 is set ( by default 
   -c3 is set).
   
   The program will shrink the STATIC entities until 
   one of three conditions occur:
       
       1) -sufficient space is created so the NEW entity(ies) can fit with
           with a height greater then or equal to <val>
       
       2) if -c2 is set
       
          -height of the STATIC entities has shrunk/compressed to the 
           point where if shrunk any more the height of one or more 
           STATIC entities will be less then <val>
          -this means that the height of the NEW entity(ies) 
           will be less then <val> - which is not good but that's life
          
       3) if -c3 is set
       
          -a collision occurs
          -a collision can occur when shrinking the attributes
           (x,y,height,width) of the STATIC entities, it is possible
           for the entities to overlap each other
           
   Because there can be many levels of containment the value <val> is 
   used only for the top containment level. For every other containment level
   the minimum height is calculated.  The following is an example 
   showing how the program does this:
   
   e.g. if -He30 is set in command line of the lsadjust program
   
   example graph layout
   --------------------
   ----------------------
  | ROOT h=200           |
  |   ---------------    |
  |  | A  h=100      |   |
  |  |   ---------   |   |
  |  |  | B  h=50 |  |   |
  |  |  |         |  |   |
  |  |  |         |  |   |
  |  |   ---------   |   |
  |  |               |   |
  |   ---------------    |
  |                      |
   ----------------------
  
  -if a NEW entity 'N1' exists and is contained by 'ROOT' then the program
   will try to adjust the entities contained by 'ROOT' in order to make
   the height of 'N1' >= 30
   
  -if a NEW entity 'N2' exists and is contained by 'A' then the program
   will try to adjust the entities contained by 'A' in order to make the
   height of 'N2' >=  ( 30 * 100 / 200 = 15 )  
                                        ----
                                         --
   General formula program uses to calcule minimum desired height for each 
   containment level:
    
         <val>        MIN HEIGHT FOR CON LEVEL 
      -----------  =  ------------------------ 
      ROOT height       container height
                                               
                                             <val> * container height
   therefore,  MIN HEIGHT FOR CON LEVEL =   --------------------------
                                                   ROOT HEIGHT


  
  note:  If type of layout model is set to the client server model ( -m2 )
         and if min. height of container entities is set to 30 ( -He30 ) 
         then the value 30 applies to the entities contained directly 
         by the subsystem.  For every other container the above formula
         is applied to calculate the min height. 



-S<val>      - when fitting in new entities shrink by <val>% each iteration
               until enough space is created
             - Range: 0 < val < 100  , Default value: 1


  - implications of increasing the value of <val> : 
      
      1) program runs faster
      
      2) loss of precision in STATIC AND NEW entity attributes
           
           - for example if minimum height of contained entities is
             set to 30 ( -He30 ) and if shrink value is 1 ( -S1 ) then 
             the value of the height of the NEW entity(ies) will be 
             slightly above 30 OR the height of the STATIC entities will be
             slighly above 30
           
           - if mininum height of contained entities is
             set to 30 ( -He30 ) and if shrink value is 10 ( -S10 ) then 
             the value of the height of the NEW entity(ies) could be 
             much larger then 30 OR the height of the STATIC entities could
             be much larger 30
           
         

-c<1 | 2 | 3>      - specify method to compress STATIC entities in
                     order to create enough space to fit in NEW entities.
                   - default compress type is 3
                   - description of compress types:
                     
                     1 - none
                         
                         - STATIC entity attributes are not adjusted
                         - NEW entities will be fit into the existing space
                       
                     2 - min (relative position and size of all entities is maintained)
                           
                         - all the attributes of an entity (STATIC) are adjusted by an the same
                           percentage  
                                
                         - compression/shrinking ends when
                           
                            first STATIC entity gets shrunk to the point where
                            it's height is less then the minimal allowable
                            -- which is set by the -H switch 
                            
                                     OR
                                     
                            sufficient space is created so the NEW entity(ies) can fit with
                            with a height greater then or equal to minimum height set
                            by -H switch
                         
                               
                         - this option maintains relative position and size of all
                           STATIC entities in the layout 
                         
                     3 - max. (relative position is maintained however relative size is not)
                         
                          - the x,y attributes of an entity are adjusted by a potentially
                            different percentage then the height, width attributes
                          
                          - compression/shrinking ends when 
                          
                            sufficient space is created so the NEW entity(ies) can fit
                            with a height greater then or equal to minimum height set
                            by -H switch
                            
                                     OR
                                     
                            during the shrinking/compressing process  a collision between
                            two entities occurs
                            
                                     OR
                                     
                            the STATIC entities in a container are shrunk X times
                            ( X is set to 100 in the program)

-e                 - output parse warnings

     
     - Examples of parse warnings are:
        
        1) An "$INSTANCE" is declared twice for the same entity
        
        2) AN "$INSTANCE" is NOT declared for an entity but the
           entity exists in one or more relation tuples.
     

-m<1 | 2>          - select a layout model (default is 1)
                     1 - nested layout
                     2 - client, server, subsystem layout
                     
                            
  - Descriptions of the two layout models are given below in sections:
  
    'Description of Nested Layout Model'
    
        AND
    
    'Description of Client Server Layout Model`




-s<o | n> <name>   - name of subsystem (only for client/server layout model)
                     o -  old tuple file
                     n -  new tuple file

    - The program must know what the name of the subsystem
      entity is for the <old tuple file> and the <new tuple file>.
      The program finds out in 1 of 2 ways:
      
      1) if -s option is used the subsystem name is directly 
         passed to the program from the command line.
         
      2) if -s option NOT USED then see description of 
         <old tuple file> and <new tuple file>
             
      NOTE: Once the name of the subsystem for each tuple file 
            is determined the program searches its symbol table 
            to find an entity with that name.  If it does not
            find one then the program ends with a error message.



-r                 - <tuple files> only contain relation tuples


    - with -r option the <old tuple file> and <new tuple file> should only
      contain relation tuples
             
      i.e. "FACT TUPLE :" header is not required AND
           $INSTANCE tuples are not required


-x                 - debug mode (creates a file called lsadjust.debug)




5.0 Description of Nested Layout Model :
----------------------------------------

 --------------------------------------
|                                      |
|                                      |
|          --------------              |
|         | A  -----     |             |
|         |   |A.a  |    |             |
|         |   |     |    |             |
|         |    -----     |             |
|         |              |             |
|         |    -----     |             |
|         |   |A.B  |    |             |
|         |   |     |    |             |
|         |    -----     |             |
|          --------------              |
|                                      |
|                                      |
|                                      |
|          --------------              |
|         | B  -----     |             |
|         |   |B.a  |    |             |
|         |   |     |    |             |
|         |    -----     |             |
|         |              |             |
|         |    -----     |             |
|         |   |B.b  |    |             |
|         |   |     |    |             |
|         |    -----     |             |
|          --------------              |
|                                      |
|                                      |
 --------------------------------------

- This is the most general layout model.  The model consists of a number
  of entities that may or may not contain other entities that may or may not
  contain other entities and so on.

- In this layout model all the entities are treated equal.

Note: A flat layout is the same as a nested layout with a nesting 
      level of 0.



6.0 Description of Client Server Layout Model:
----------------------------------------------

 -----------------------------------------
|     ----          ----       ----        |
|    |    |        |    |     |    | <-----|---------  client entities
|     ----          ----       ----        |
|     --------------------------------     |
|    |                                |    |
|    |              ----              |    | 
|    |             |    |             |    |
|    |              ----              |    |
|    |                                |    |
|    |  ----        ----      ----    |    |
|    | |    |      |    |    |    |   |<---|---------- subsystem
|    |  ----        ----      ----    |    |
|    |                                |    |
|    |  ----        ----              |    |
|    | |    |      |    |<------------|----|---------- subsystem entities
|    |  ----        ----              |    |
|    |                                |    |
|     --------------------------------     |
|     ----          ----       ----        |
|    |    |        |    |     |    | <-----|---------- server entities
|     ----          ----       ----        |
 ------------------------------------------

-In this model the top level view (shown in the diagram above) consists
 of the subsystem, subsystem entities, client entities and server entities.
 The subsystem is the focal point of this layout model.

-Clients are those entities that USE the subsystem - i.e. one or more
 relations exist between a client entity and a subsystem entity.
 
-Servers are those entities that are USED BY the subsystem - i.e. one
 or more relations exist between a subsystem entity and a server entity.

-The client, server and subsystem entities can contain other entities
 as well.  These will be layed out using the nested layout model 
 (i.e only the top level view will use the client server layout model). 



7.0 Parsing the <tuple files>
-----------------------------

When the -r switch is not used then the  program expects the
<tuple file> to have the following format:

FACT TUPLE :               // This is A TA section header 

$INSTANCE a module         // declare $INSTANCE for each entity
$INSTANCE b module
$INSTANCE ss subsystem    
                           
                           // relation tuples ( the order of the relations 
                                                 does not matter )
                                                 
contain ss a
contain ss b
call a b                      


If the "FACT TUPLE :" header is not read and EOF has been reached, the
program ends with an error message.

The $INSTANCE tuples must come before the relation tuples.

If an $INSTANCE is not declared for an entity and that entity is used
in a relation then the program treats the entity as if it was declared and
continues.  If the -e switch is specified then the program will output
an appropriate warning message then continue.

The philosophy taken is to be as lenient as possible when parsing
the input tuple files.


8.0 Parsing the <layout file>
-----------------------------

Format of the <layout file> :

entity_name {
      x = 10.5
      y = 56.7
  width = 66.5
 height = 39.9 
 
 [other attributes]
 
}

A layout file is a collection of entities with their attributes in the
format shown above. The attributes relevant for a layout are
the x, y, height and width.  

When parsing the attributes of an entity in a layout file the order
of the attributes does not matter.

There can be other attributes besides x, y, width and height; the program
will simply ignore them.

If a layout attribute (x,y,width,height) does not exist for an entity
then the program outputs an appropriate error message and quits.


9.0 Description of Program :
----------------------------
This program takes as input a <old tuple file> and its associated
<old layout file>, a <new tuple file> and a <new layout file>.  
The <new layout file> will contain the output of the program.

The program reads the <old tuple file> and stores all the entities in a 
internal symbol table ( implemented using a hash table ) called the
"old symbol table".

The <old layout file> is then read and the attributes ( x,y,height,width ) 
for each entity are stored in the "old symbol table".

The program then reads the <new tuple file> and stores all the entities 
in a "new symbol table".  

The NEW, OLD and STATIC entities are identified and marked.

The attributes of the entities identified as STATIC are copied from the
"old symbol table" to the "new symbol table"

The NEW entities ( entities in the "new symbol table" not marked as STATIC )
are lined up along the right hand side of its container without colliding
with any other entities.  See description of -c and -He switch to see how
the attributes (x, y, height and width) of the NEW entities are calculated.

If Client Server Layout model used:

   The NEW client entities are lined up horizontally between the STATIC
   clients and the subsystem.  See -c and -Hc switch to see how attributes
   (x, y, height, width) of NEW clients are calculated.

   The NEW server entities are lined up horizontally between the STATIC
   servers and the subsystem.  See -c and -Hs switch to see how attributes
   (x, y, height, width) of NEW servers are calculated.

The entities in the "new symbol table" are written to the <new layout file>
along with their attributes in the following format:

entity_name {
      x = 2.69
      y = 4.99
 height = 100
  width = 166
}

Note that the OLD entities won't get written to the <new layout file> as
the OLD entities do not exist in the "new symbol table".



10.0 Glossary:
--------------

STATIC entities - entities that EXIST in BOTH the old tuple file and the 
                  new tuple file
                  
                          AND
                  
                  its parent container in each of the tuple files is the same


OLD entities - entities that EXIST in the old tuple file but NOT in the
               new tuple file
               

NEW entities - entities that EXIST in the new tuple file but NOT in the
               old tuple file
               
                          OR
                          
               entities that EXIST in both the old tuple file and the
               new tuple file but have different parent containers