Abstract:
A system, method and media for allowing a first thread exclusive access to the first type; resolving the first type to a first stage by the first thread; and creating a first version of the first type based on the resolving. This abstract is not intended to be a complete description of, or limit the scope of, the invention. Other features, aspects and objects of the invention can be obtained from a review of the specification, the figures and the claims.

Description:
CLAIM OF PRIORITY  
       [0001]     This application claims benefit from U.S. Provisional Patent Application No. 60/703,988 entitled MULTI-THREADED RESOLVER, by Timothy Hanson, Jesse Michael Garms, Timothy Allen Wagner, filed Jul. 29, 2005 (Attorney Docket No. BEAS-1831US0), which is hereby incorporated by reference in its entirety. 
     
    
     CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0002]     This application is related to the following application(s) which are each hereby incorporated by reference in their entirety:  
         [0003]     U.S. Application No. ______, entitled SYSTEM AND METHOD FOR MULTI-THREADED RESOLVER WITH DEADLOCK DETECTION, by Timothy Hanson, Jesse Michael Garms, Timothy Allen Wagner, filed ______ (Attorney Docket No. BEAS- 1832US 1).  
         [0004]     U.S. Application No. ______, entitled SYSTEM AND METHOD FOR MULTI-THREADED RESOLVER WITH VERSIONING, by Timothy Hanson, Jesse Michael Garms, Timothy Allen Wagner, filed ______(Attorney Docket No. BEAS-1833US1).  
       FIELD OF THE DISCLOSURE  
       [0005]     The present disclosure relates generally to a means for resolving symbol names during program compilation and, more particularly, a multi-threaded means for doing so.  
       BACKGROUND  
       [0006]     Traditional command line programming language compilers are single threaded due to the batch-oriented nature of their work. In the context of user-interactive tools, however, many threads make requests of compiler services. For example, user interface views read and modify compiler data structures, file watching threads push file changes onto the compiler, and interactive editing triggers incremental compilation. In a programming language that has a global type system, threads performing type resolution need information from more than one file. This can lead to duplication of work and race conditions between the threads. What is needed is a way to make type resolution “thread safe” while at the same time preventing threads from becoming deadlocked. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]      FIG. 1  is an illustration of a programming language compilation phases in which embodiments of this invention can be practiced.  
         [0008]      FIG. 2  is an illustration of type versions in accordance to an embodiment.  
         [0009]      FIG. 3   a  is an illustration of a deadlock situation that can arise between two threads that are resolving interdependent types.  
         [0010]      FIG. 3   b  is an illustration of deadlock avoidance between two threads in accordance to an embodiment.  
         [0011]      FIG. 4   a  is an illustration of a deadlock involving resolution of super types.  
         [0012]      FIG. 4   b  is an illustration of a type dependency graph containing a cycle.  
         [0013]      FIG. 5  is an illustration of an algorithm for detecting cycles in between resolution threads in accordance to an embodiment.  
         [0014]      FIG. 6  is a flow diagram for performing type resolution in accordance to an embodiment.  
     
    
     DETAILED DESCRIPTION  
       [0015]     The invention is illustrated by way of example and not by way of limitation in the figures of the accompanying drawings in which like references indicate similar items. References to embodiments in this disclosure are not necessarily to the same embodiment, and such references mean at least one. While specific implementations are discussed, it is understood that this is done for illustrative purposes only. A person skilled in the relevant art will recognize that other components and configurations may be used without departing from the scope and spirit of the invention.  
         [0016]     In the following description, numerous specific details are set forth to provide a thorough description of the invention. However, it will be apparent to one skilled in the art that the invention may be practiced without these specific details. In other instances, well-known features have not been described in detail so as not to obscure the invention.  
         [0017]     Examples are given in terms of the Java® programming language, however those of skill in the art will recognize that the teachings herein are applicable to any programming language with a global type system, including without limitation C# and XML/Schema. (Java® is a registered trademark of Sun Microsystems, Inc.) Likewise, while interactive software development tools can be enriched by using embodiments described herein, the teachings are naturally applicable to many disciplines which are fully within the scope and spirit of the present disclosure.  
         [0018]      FIG. 1  is an illustration of a programming language compilation phases in which embodiments of this invention can be practiced. Compilation phases can include lexing, parsing, semantic analysis, code generation and optimization. Source code  100  consisting of one or more (complete or incomplete) programming language statements is provide in whole or in part to lexical analyzer  102  which analyzes the source and emits tokens  104 . Tokens are processed by syntactic analyzer  106  which in turn creates a syntax tree  108  representation of the source code by analyzing the token stream for structure and symbols. The syntax tree is examined by the semantic analyzer  110  which performs type resolution (or “resolution”) by matching occurrences of symbol names with corresponding definitions. The result is a qualified syntax tree  112  which is provided to code generator  114 . The code generator produces intermediate code  116  (sometimes called “object code”) which can be optimized by optimizer  118  to produce target code  120  for a particular runtime environment.  
         [0019]     In various embodiments, resolution of a type can progress in discrete stages. By way of illustration, resolution of a type in the Java programming language can include a plurality of the stages as described in Table 1 below.  
                         TABLE 1                           Resolution Stages for a Type            RESOLUTION STAGE   DESCRIPTION               1   Type Modifiers (e.g., public, static, final,           transient, volatile)       2   Super Types       3   Member Types (e.g., inner types for members)       4   Methods/Fields       5   Constants                  
 
         [0020]     In aspects of these embodiments, resolution information for each stage can be added to a resolved version of the type. For example, consider the following Java type declaration:  
                                                   public class A extends Z {             public A ( ) {               field1 = 0;             }             private integer field1;           } ;                      
 
         [0021]     If resolution of type A progresses to stage  2 , a version of the type would contain information pertaining to A&#39;s modifiers and supertypes (i.e., public and Z, respectively). Likewise, if resolution reached stage  5 , a version of the type would additionly contain the constructor method A( ) and field field 1 .  
         [0022]     In one embodiment, there is a lock or other suitable mechanism associated with each type that can be used to prevent two or more threads from interfering with each other during resolution. In aspects of this embodiment, a thread can acquire a lock for the type before beginning a resolution stage. The thread can then retrieve the latest version of the type from a type repository or other suitable store, create a new copy of that version that can be modified and include additional information for the current stage. The thread can then mark the new copy as immutable, update the type repository with the new version, and release the lock associated with the type. While a type is locked, other threads can inspect prior versions of the type. Having the versions immutable guarantees that any thread examining a type version never sees inconsistent results (i.e., a version cannot be changed underfoot by another thread).  
         [0023]      FIG. 2  is an illustration of type versions in accordance to an embodiment. In one embodiment, a thread creates a new version of a type when it advances resolution of the type. If a thread needs resolved information for a type such as its fields and methods it can first see if there is a version of the type resolved to the appropriate stage. If the version exists, the thread only needs to retrieve it from the type repository. Otherwise, the thread can acquire a lock on the type and move resolution forward to the required stage. As discussed above, this will create a new immutable version of the type that is available to all threads.  
         [0024]     Type A  200  in the figure has four versions ( 202 - 208 ) associated with it. Each version was created by a thread and not necessarily the same thread. Version  1  ( 202 ) of A is resolved to stage  1 , version  2  ( 204 ) is also resolved to stage  2 , version  3  ( 206 ) is resolved to stage  4  and version  4  ( 208 ) is resolved to stage  5 . Depending on the stage of a version and by way of illustration, a version can contain information including (but not limited to) one or more of the following: a type&#39;s modifiers, super types, member types, methods, fields and constants. Versions of a type can be persisted in a type repository or other suitable storage means.  
         [0025]     Type versions can be used to avoid duplicating resolution work. For example, a second thread is blocked waiting for the lock associated with a type. Once the first thread releases the lock, the second thread will attempt to acquire the lock. By checking the latest version of the type before beginning resolution, the second thread will either do nothing (having its requirements met by the work done on the first thread) or will move resolution forward—beginning where the previous thread left off.  
         [0026]      FIG. 3   a  is an illustration of a deadlock situation that can arise between two threads that are resolving interdependent types. By way of illustration, assume types A and B are declared as follows:  
                                                   Type A   Type B                           public class A   public class B             B field1;     A field2;           }  ;   }  ;                        
         [0027]     Field field 1  in class A depends on class B. Likewise, field field 2  in class B depends on class A. With reference to  FIG. 3   a , Thread  1  is resolving type A at stage  4 . Thread  2  is resolving type B also at stage  4 . A deadlock will occur if Thread  1  held the lock on type A, and then attempted to acquire the lock on type B; and Thread  2  held the lock on type B, and then attempted to acquire the lock on type A. The result: Thread land Thread  2  block indefinitely waiting on the other to release its lock.  
         [0028]      FIG. 3   b  is an illustration of deadlock avoidance between two threads in accordance to an embodiment. As with  FIG. 3   a , field 1  in class A depends on type B and field 2  in class B depends on type A. Both threads are resolving their respective types at stage  4 . If a thread does not require a version of an interdependent type at the same stage or greater as the type it is currently resolving, deadlock can be avoided. In our example, while resolving the fields of type A (stage  4 ), Thread  1  will request resolution of type B, but it will only request information about the super types of B (stage  2 ). Thus deadlock will never occur because before Thread  1  requests B at stage  2 , Thread  2  is resolving B at stage  3 . The same holds true for Thread  2 . The requests require no work since versions of A and B at stage  2  already exist—the requests are satisfied from the type repository without the need to acquire the type locks.  
         [0029]     An exception to this rule involves the resolution of interdependent super types. For example, consider the following types:  
                                                   Type A   Type B                           public class A extends B   public class B extends A             B field1;     A field2;           }  ;   }  ;                      
 
         [0030]     If type A extends type B and vice versa, this could cause a deadlock between thread T 1  (resolving A at stage  2 ) and thread T 2  (resolving B at stage  2 ) as shown in  FIG. 4   a  since both types are being resolved at the same stage. Although this is not allowed by the Java programming language, for example, it is still possible to create such a program. In one embodiment, this situation can be avoided by checking for a possible deadlock before acquiring the lock associated with a type. If acquiring the lock would cause deadlock, the type can be marked as having illegal circular inheritance.  
         [0031]      FIG. 4   b  is an illustration of a type dependency graph containing a cycle. Assume that in various embodiments a thread holding a lock on a given type can determine which other threads are waiting to acquire that lock. Thus, a thread is related/connected to other threads based on which threads are trying to acquire its lock. In this way, type resolution threads can be viewed as a graph. If a cycle exists in the graph then there is a deadlock between two or more threads. In this figure, thread T 1  which holds a lock on type A, wishes to determine if by trying to assert a lock on type B (the “target type”), a deadlock will arise.  
         [0032]     In one embodiment, detecting a cycle begins with traversing the graph at a current thread T 1 . All possible paths from T 1  are those threads that are waiting to acquire a lock on type A. In this case, thread T 8  (which is resolving type E) and thread T 2  (which is resolving type G) are waiting for T 1  to release its lock on type A. Thread T 8  has two paths leading to it from threads T 6  and T 7 . These paths are dead-ends, since no other thread is waiting to acquire a lock on type H or F. However, from thread T 2  it is possible to traverse to the target type B via threads T 3  (type C) and T 4  (type D). Thus, a cycle (A→B→D→C→G→A) would exist if thread T 1  were to attempt to acquire a lock on B.  
         [0033]     In another embodiment, this algorithm can be implemented as a recursive function/method for depth-first traversal of the graph as illustrated in  FIG. 5 . (It will be apparent to those of the art that this algorithm can also be implemented in a non-recursive, iterative fashion.) In starting block  500 , it is determined which threads are waiting to acquire a lock on the current type which is initially the type that is being resolved. For each iteration of loop  508 , a different one of these thread(s) (represented by T) is processed. Block  502  determines whether or not the type that is locked by T is the target type. If so, a cyclic dependency exception is raised. Otherwise, block  500  is recursively invoked with the current type set to the type that T is holding the lock on. As recursive calls return, block  506  determines if there are any more threads T to evaluate. If not, the function/method returns. Otherwise, T is set to the next thread and the algorithm continues at block  502 . The target type remains the same across all invocations.  
         [0034]      FIG. 6  is a flow diagram for performing type resolution in accordance to an embodiment. Although this figure depicts processing in a particular order for purposes of illustration, one skilled in the art will appreciate that various processes portrayed in this figure can be omitted, rearranged, performed in parallel, combined and/or adapted in various ways as will be apparent to those of skill in the art.  
         [0035]     Resolution begins at block  600  wherein it is determined whether or not there already exists a version of the type in the type repository at the desired stage. If so, the version is returned and current resolution thread completes. Otherwise, in block  602  an attempt is made at acquiring the lock for the type. If the lock is already held by another thread, the current thread can block until the lock is released. Once the lock is acquired, it is determined whether or not a super type will be resolved. If so, a determination is made in block  604  as to whether attempting to resolve the super type will cause a deadlock. If so, an exception is raised and the lock is released. In one embodiment (not illustrated), the problematic super type can be dynamically replaced with a global super type (e.g., “Object” in the Java programming language) which will allow compilation to recover and continue past the error.  
         [0036]     If no potential deadlock is detected, the type repository is again checked in block  606  to see if another thread has created a version of the type at the desired stage in the time since the current thread acquired the lock. If so, the version is returned and the current resolution thread completes. Otherwise, the latest version of the type is obtained from the type repository (block  608 ) and copied to create a new, modifiable version in block  610 . The type is then resolved to the desired stage and the new version is updated to include any pertinent information in block  612 . The new version is marked as immutable and then placed in the type repository (block  614 ). Finally, the type lock is released in block  616 .  
         [0037]     Resolution of constants can also involve circularity. For example, considering the following type declarations:  
                                                   Type A   Type B                           public class A   public class B             public static int C1 = B.C2;     public static int C2 = A.C1;           }  ;   }  ;                      
 
         [0038]     In one embodiment, constants can be resolved using per-field locking. If a deadlock would arise if one thread was to assert a lock on another thread, the constant&#39;s value is set to zero.  
         [0039]     Although a diagram may depict components as logically separate, such depiction is merely for illustrative purposes. It will be apparent to those skilled in the art that the components portrayed can be combined or divided into separate software, firmware and/or hardware components. Furthermore, it will also be apparent to those skilled in the art that such components, regardless of how they are combined or divided, can execute on the same computing device or can be distributed among different computing devices connected by one or more networks or other suitable communication means.  
         [0040]     Various embodiments may be implemented using a conventional general purpose or specialized digital computer(s) and/or processor(s) programmed according to the teachings of the present disclosure, as will be apparent to those skilled in the computer art. Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present disclosure, as will be apparent to those skilled in the software art. The invention may also be implemented by the preparation of integrated circuits and/or by interconnecting an appropriate network of conventional component circuits, as will be readily apparent to those skilled in the art.  
         [0041]     Various embodiments include a computer program product which is a storage medium (media) having instructions stored thereon/in which can be used to program a general purpose or specialized computing processor(s)/device(s) to perform any of the features presented herein. The storage medium can include, but is not limited to, one or more of the following: any type of physical media including floppy disks, optical discs, DVDs, CD-ROMs, microdrives, magneto-optical disks, holographic storage, ROMs, RAMs, PRAMS, EPROMs, EEPROMs, DRAMs, VRAMs, flash memory devices, magnetic or optical cards, nanosystems (including molecular memory ICs); paper or paper-based media; and any type of media or device suitable for storing instructions and/or information. Various embodiments include a computer program product that can be transmitted in whole or in parts and over one or more public and/or private networks wherein the transmission includes instructions which can be used by one or more processors to perform any of the features presented herein. In various embodiments, the transmission may include a plurality of separate transmissions.  
         [0042]     Stored one or more of the computer readable medium (media), the present disclosure includes software for controlling both the hardware of general purpose/specialized computer(s) and/or processor(s), and for enabling the computer(s) and/or processor(s) to interact with a human user or other mechanism utilizing the results of the present invention. Such software may include, but is not limited to, device drivers, operating systems, execution environments/containers, user interfaces and applications.  
         [0043]     The foregoing description of the preferred embodiments of the present invention has been provided for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to the practitioner skilled in the art. Embodiments were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the relevant art to understand the invention. It is intended that the scope of the invention be defined by the following claims and their equivalents.