UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A domain specific language for encoding design rules Morgan, Clinton Alan 2006

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


831-ubc_2007-0196a.pdf [ 1.72MB ]
JSON: 831-1.0052056.json
JSON-LD: 831-1.0052056-ld.json
RDF/XML (Pretty): 831-1.0052056-rdf.xml
RDF/JSON: 831-1.0052056-rdf.json
Turtle: 831-1.0052056-turtle.txt
N-Triples: 831-1.0052056-rdf-ntriples.txt
Original Record: 831-1.0052056-source.json
Full Text

Full Text

A Domain Specific Language for Encoding Design Rules by Clinton Alan Morgan B.Sc, University of New Mexico, 2004 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Master of Science i n The Faculty of Graduate Studies (Computer Science) The University Of British Columbia December, 2006 © Clinton Alan Morgan 2006 Abst rac t Design rules express constraints on the behavior and structure of a program. These rules can help ensure that a program follows a set of established practices, and avoids certain classes of errors. Design rules often crosscut program structure and enforcing them is emerging as an important application domain for Aspect Oriented Program-ming. For many interesting design rules, current general purpose A O P lan-guages lack the expressiveness to characterize them statically and enforce them at compile time. We have developed a domain specific language called Program Descrip-tion Logic (PDL). P D L allows succinct declarative definitions of program-matic structures which correspond to design rule violations. P D L is based on a fully static and expressive pointcut language. P D L pointcuts allow characterizing a wide range of design rules without sacrificing static verifi-cation. We evaluate P D L by comparing it to FxCop, an industrial strength tool for checking design rules. T a b l e o f C o n t e n t s Abstract ii Table of Contents iii List of Tables v List of Figures vi Acknowledgements vii Dedicat ion viii 1 Introduction 1 2 The P D L Language 4 2.1 Untyped P D L 4 2.2 Typed P D L 12 2.2.1 Typing Derivations 12 2.2.2 Soundness 15 3 Implementation 17 3.1 Code Generation • • • • ^ 3.2 Optimization 19 4 Comparison with FxCop 21 4.1 Expressiveness 21 4.2 Conciseness 24 4.3 Performance 24 5 Related Work 27 6 Conclusion 29 m Table of Contents B i b l i o g r a p h y ' 30 iv List of Tables 2.1 Selected unary primitives , 8 2.2 The semantics of selected binary primitives. Semantics are described with respect to the parametric pointcut p 9 2.3 P D L joinpoint types 14 4.1 Overview of the FxCop rules encoded in P D L 22 4.2 Overview of the reasons P D L was unable to express FxCop rules. Column J is due to the joinpoint model, P is due to a lack of primitives, C is due to a complex analysis, and O is other 23 4.3 Performance comparison of P D L and FxCop on several dif-ferent programs. The numbers shown are time in seconds (averages of 10 runs) 25 v Lis t of Figures 2.1 The syntax for a simplified version of the P D L pointcut lan-guage in B N F 5 2.2 Denotational semantics for untyped P D L 6 2.3 Typing rules for pointcuts and binary relations 13 2.4 Typed semantics for P D L (only the clauses which differ from the untyped semantics are shown 16 4.1 Performance comparison between P D L with and without op-timizations as a function of the number of rules 26 vi Acknowledgements I would like to thank Kris De Voider and Eric Wohlstadter who provided excellent advise and encouragment throughout this process. Navjot Singh also paricipated in numerouse helpful discussions. This work was supported by a Microsoft Phoenix - Excellence in Programming Award and by the University of British Columbia. i vii Dedicat ion This thesis is dedicated to Ullr, the Norse God of snow. I hope that it pleases him and he continues to provide blessings of bountiful powder. viii Chapter 1 Introduct ion Design rules constrain the structure or behavior of a program and express desirable programming practices. Examples include stylistic guidelines, li-brary usage rules, and correctness properties. Design rule checkers take a design rule specification, and statically check a program for violations. This allows defects to be caught early in the development process (i.e., compilation), and may catch errors that are not evident in testing. To encourage this practice, programmers must be allowed to easily encode design rules in a form that can be consumed by a checker. A commonly used approach to building a design rule checker is as a framework with an API which provides a means of inspecting the program. Examples of this approach include FxCop [1] and FindBugs [17]. These rule checking frameworks come with a large number of generic, predefined rules. However, because of the complexity of the APIs and the imperative nature of the rule definitions, adding new rules is difficult. Aspect Oriented Programming (AOP) is emerging as a more declarative alternative to imperative rule checking frameworks. Recent A O P literature has explored using Aspect J [19], a general purpose A O P language with a dynamic joinpoint model, to encode design rules but have found that it lacks the ability to express some static properties. For example, in [21], the Law of Demeter was encoded using Aspect J. Variants of this design rule are expressed in terms of static program elements and thus could in theory be checked statically. However, limitations in the pointcut and advice model in AspectJ prevented static checking. The authors argue for extensions to AspectJ-namely, static pointcuts and advice-which allow static aspects. Also, in [25] it is shown how aspects can be used to enforce certain design rules in a program. Several examples of how this can be done in AspectJ are given. The authors also describe some rules which cannot be expressed in AspectJ. These examples motivate the need for additional pointcuts on static program elements. The authors conclude that an A O P approach to encode and enforce designs is desirable, but AspectJ's joinpoint and pointcut mechanism does not allow for sufficient static expressibility. In this paper we present a domain specific aspect language called Pro-1 Chapter 1. Introduction gram Description Logic (PDL). P D L is designed for the specific purpose of statically checking design rules. A P D L program consists of a list of point-cut advice-pairs. Each pointcut-advice pair represents a design rule. The pointcut matches violations of a design rule, and the advice specifices a cor-responding error message. Below is an example of a simple P D L design rule definition: f i e l d ( s o u r c e T y p e ) && p u b l i c : "Do not d e c l a r e v i s i b l e i n s t a n c e f i e l d s " The syntax of P D L pointcuts is similar to AspectJ. However, the P D L join-point model, unlike Aspect J's, is. static. In other words, joinpoints in P D L are static program entities such as classes, fields, methods, and instruc-tions in the byte-code. Consequently, P D L pointcuts can be fully evaluated statically. Given the purpose of P D L , the only kind of advice is emission of compile-time error messages. Thus a P D L advice body is just an error message. P D L is implemented as a bytecode tool which analyzes . N E T as-semblies, finds matches to the pointcuts, and prints the corresponding error messages. To evaluate P D L , we compare it to FxCop [1], an industrial design rule checker which analyzes programs for conformance to the . N E T Framework Design Guidelines [ 2 ] . FxCop is typical of the framework approach to build-ing a design rule checker. It comes with an extensive set of prepackaged rules, but the complexity of its APIs and imperative nature make it hard to write custom rules. P D L , on the other hand, allows concise declarative rule definitions. As expected, the declarative specification limits expressibility. However, we show that we can still express a substantial and useful portion of the FxCop rules in P D L . We also consider the performance of P D L which is an important concern for a rule checking tool. The checking process must be efficient enough that it can be placed inside of the edit-compile-debug loop that forms a programmers primary work cycle. Moreover, P D L must be able to scale up to check a large collection of rules on a large program. Our implementation of P D L is a source to source compiler which results in minimal overhead when running the rules. Additionally, the declarative nature of P D L rules allow optimizations not otherwise possible. In particu-lar, our implementation detects intermediate results .which are shared among rules and merges the rules together to avoid repeated computations. We car-ried out performance measurements which shows that our implmentation of P D L performs comparably to FxCop. The main contribution of this paper is the design and implementation of 2 Chapter 1. Introduction P D L , a domain specific aspect language for the specific purpose of encoding design rules. We believe this is a useful contribution by itself and also comprises a number of more specific, smaller contributions which we discuss below. First P D L has a useful static type checker that assigns types to pointcuts based on the types of joinpoints which they can match. We believe the' type checker can detect many nonsensical pointcuts without being overly restrictive. We have formalized the type-system and proven its soundness. The formalization gave rise to some interesting insights into the semantics of ! pointcuts. We believe these static typing related contributions have independent value and could be applied to other pointcut languages, for example AspectJ, which has a similar syntactic and semantic structure to untyped P D L . Second the syntax of P D L also harbors a number of novel ideas, such as quantifiers inspired by description logics. These could be useful additions to other pointcut languages and will likely mesh well with any pointcut syntax inspired by AspectJ (i.e., the majority). Third, we performed a detailed comparison between declarative P D L and an imperative, industrial strength design-rule checker in terms of per-formance and expressiveness. Other comparable work on using declarative notations for design-rules have not performed such a comparison. This is unfortunate since we believe that such industrial tools are their most im-portant competitors in practice. Fourth, P D L exemplifies the idea of applying database optimization tech-niques in the context of pointcut language optimization. While the similarity between pointcut languages and query-languages is relatively apparent and has been pointed out before (e.g., [12], [15]) real examples that exploit this idea for optimization are currently few. The remainder of this thesis is organized as follows. Chapter 2 provides a description of the P D L language and semantics. Chapter 3 discusses rule evaluation and optimization techniques. Chapter 4 provides a comparison between P D L and FxCop in terms of expressibility, conciseness, and perfor-mance. Chapter 5 presents related work. Finally, Chapter 6 concludes and discusses future work. 3 Chapter 2 The P D L Language A P D L program consists of a series of pointcut-advice pairs. Pointcuts are predicates which match joinpoints. P D L has a static joinpoint model. This means that P D L joinpoints are static program elements and that P D L pointcuts identify (match) sets of static program elements. In this section we present the details of the P D L pointcut language, including a formal semantics and typing rules. We present the semantics in two stages. We first present a simplified, untyped version of P D L and then discuss how static typing is added. 2.1 Untyped P D L Pointcuts in P D L are declarative expressions with a syntax inspired from Aspect J and Description Logics [4, 6]. Pointcut expressions are built up from unary and binary primitives and can be combined using and, or, and not operators (&;&, || , and !). There are forms for several types of quantification including existential and universal. A simplified syntax for the P D L pointcut language is shown in Figure 2.1. A pointcut expression matches a joinpoint, or equivalently, defines a set of joinpoints for a given program. This section describes pointcut semantics in terms of sets of joinpoints; we also say that a pointcut matches a joinpoint if the joinpoint is a member of the pointcut's set. Figure 2.2 presents the denotational semantics of P D L pointcuts. The remainder of this section will elaborate on the syntax and semantics and provide examples. Primitives P D L provides a number of predefined primitives. Primitives are classified as either unary or binary depending on the number of joinpoints considered for a match. Unary primitives match a joinpoint based on various properties (e.g., the access permissions of a field). Binary primitives match a joinpoint pair and express binary relations between joinpoints (e.g., the members of a type). Unary primitives specify a set of joinpoints. The unary primitive sourceType 4 Chapter 2. The PDL Language P Pointcut p := u U N A R Y 1 KP) BINARY 1 pkkp A N D 1 P II P OR 1 !p N O T 1 exists b . p EXISTS 1 forall b . p F O R A L L 1 <n b LESS u Unary Pointcut u := id U N A R Y - P R I M I T I V E | 'pat' P A T T E R N b Binary Relation b := id BINARY-PRIMITIVE | b+ T R A N S I T I V E 1 b*b C O M P O S E id : Identifier n : Natural number pat : Signature Pattern Figure 2.1: The syntax for a simplified version of the P D L pointcut language in B N F . 5 Chapter 2. The PDL Language 3 := The set of all joinpoints in a program j , ji G J P : Pointcut -> V(3) P{uj = U{uj • E - U N A R Y H K P ) } = {Ji I tiuh) € B { b l j 2 € P\p\) E -BINARY P [ p i P2] = Plpii n P b 2 ] E - A N D Pfa i II.P2] = P b i ] U P b 2 ] E - O R P[! P] = {j I J £ P b l > E - A N D P'[exists b.p] = {j2 | SU1J2) £ # ] : j i € ? b ] } E-EXISTS P[forall b . pj = fj 2.1 V(ji, j 2 ) j i € Pb]} E - F O R A L L P[< n 61 = {j 2 I |0'i I (Ji. J'2) e P[6]}| < n} E-LESS U : Unary Pointcut —> P(J) [/[id] = primitive E - U N A R Y - P R I M I T I V E U{paV] = {j I j matches pat) E - P A T T E R N B : Binary Relation —> P(J x J) Pfzd] = primitive E - B I N A R Y - P R I M I T V E B\b+\ = {(jl,jn) I (Juh), • • • , ( j n -1 , j n ) G E - T R A N S I T I V E * 62] = {Uuh) I U1J2) G 5[61], ( J 2 , j 3 ) e E - C O M P O S E Figure 2.2: Denotational semantics for untyped P D L . 6 Chapter 2. The PDL Language denotes the set of all types declared in the program. Similarly, the publ ic primitive denotes all program elements that are declared with publ ic access— this includes types, fields, and methods. A unary primitive is used in a pointcut expression by simply writing its name. The following is a simple design rule using unary pointcuts: sourceType && p u b l i c && nes ted : "Nested types s h o u l d not be v i s i b l e " The logical operator connects the three primitives so that the compound pointcut will only match joinpoints that match all of the primitives (i.e., the resulting joinpoint set is the intersection of the three pointcuts). A binary relation expresses a relationship between two joinpoints. P D L provides a number of primitive binary relations as well as methods for cre-ating new binary relations from existing ones (these will be presented in subsequent paragraphs). To construct a pointcut from a binary relation b, we supply the relation a pointuct p to serve as its parameter. This is written as b(p). A joinpoint j matches the binary pointcut b(p) if there is a joinpoint related to j via the binary relation b that matches the parametric pointcut p. As an example, consider the design rule Abstract types should not have public constructors. We encode this in P D L by writing a pointcut which matches violations—a pointcut which specifies the set of public constructors of abstract types. We use the binary relation constructor to relate types to their constructors. The P D L rule is shown below. c o n s t r u c t o r ( s o u r c e T y p e && a b s t r a c t ) && p u b l i c : " A b s t r a c t type s h o u l d not have . . . " Notice that the parametric notation of binary pointcuts in P D L is similar to the cf low pointcut in AspectJ. The cf low pointcut is parametric because it takes another pointcut as a parameter. In contrast, the c a l l pointcut in AspectJ takes only a method signature as a parameter. In P D L , c a l l is a binary relation, so its parameter is an arbitrary P D L pointcut. This allows for the expression of more complex constraints on the callee method. For example, in the expression c a l l ( m e t h o d ( f o r a l l f i e l d s t a t i c ) ) the pointcut m e t h o d ( f o r a l l f i e l d . s t a t i c ) 7 Chapter 2. The PDL Language N a m e Matches sourceType types defined in the program sourceNamespace namespaces defined in the program publ ic public types, or members pr ivate private (internal) types, or members sealed sealed types and members interface interface types generic generic types and methods v i r t u a l virtual members abstract abstract types or members s t a t i c static members -nested nested types Table 2.1: Selected unary primitives acts as the parameter. The semantics of the forall expression will be ex-plained later. For now, we will say that the expression matches methods of types whose fields are all static. Thus, the c a l l pointcut will match meth-ods that call a method declared in a type whose fields are all static. Note that such a complex constraint is not allowed in AspectJ. P D L defines a variety of native pointcuts that we found useful for ex-pressing design rules. A selection of these pointcuts is described in Tables 2.1 and 2.2. Pointcuts in P D L roughly correspond to the types of operations provided in a typical API for program inspection. For example, an inspec-tion API would have operations to examine the declaration's of a program element (e.g., check if a type is public, abstract, or sealed). These meth-ods correspond to unary primitives in P D L . The inspection API would also provide relationships between elements (e.g., get the members of a type). These relationships correspond to binary primitives in P D L . Many of the primitives in P D L are static versions of AspectJ pointcuts AspectJ. For example, the AspectJ version of set matches runtime field writes, while the P D L version of set matches bytecodes corresponding to field writes. Similarly, the AspectJ version of cflow encodes a runtime relationship whereby one joinpoint is in the dynamic extent of the other. In contrast, the P D L version cflow uses a static approximation—reachability in the call graph. 8 Chapter 2. The PDL Language N a m e Matches member (p) members declared in a type that matches p method(p) methods declared in a type that matches p constructor (p) constructors declared in a type that matches p field(p) fields declared in a type that matches p call(p) methods or bytecodes which call a method that matches p cflow(p) methods or bytecode which could be in the dynamic extent of a method matched by p within(p) bytecodes that implement a method which matches p type(p) types of a field, property, or namespace that matches p derivedType(p) types that are derived from a type which matches p baseType(p) types that are derived by a type which matches p argument (p) arguments of a method that-matches p attribute(p) attributes of a type, method, field, property, or event that matches p set(p) bytecodes which set a field that matches p Table 2.2: The semantics of selected binary primitives. Semantics are de-scribed with respect to the parametric pointcut p. 9 Chapter 2. The PDL Language Signature Patterns. In order for pointcuts to refer to specific types, methods, constructors, or fields, P D L provides a notation for signature pat-tern pointcuts. Signature patterns are written enclosed in single quotes with a form similar to that used in AspectJ. In P D L , signature patterns can be thought of as special unary pointcuts which match joinpoints based on their signature. For example, the expression ' v o i d * .Set * (*) ' creates a pointcut which matches methods declared in any type, which return void, whose name starts with "Set" and takes a single argument. Signatures are a useful mechanism to match specific elements from a set of joinpoints. For example, we often want to focus a design rule on a particular method. To encode the design rule Finalizers should be protected, we use a method signature to select only the finalization methods. method(sourceType) && ' v o i d * . F i n a l i z e ( ) ' && ! p r o t e c t e d : " F i n a l i z e r s s h o u l d be p r o t e c t e d " In AspectJ signature patterns are used as parameters to pointcuts such as c a l l and set. However, in P D L , signature patterns are first-class citizens— they are pointcut expressions. This is possible because PDL's joinpoint model includes the elements matched by the signature pattern (i.e., types, methods, and fields). Thus signature patterns can be used as any part of a P D L pointcut expression, as opposed to in AspectJ where they are limited to serving as parameters to a fixed number of expressions. Note that it is this generalization which allows P D L to make pointcuts like c a l l and set parametric (as discussed previously) . Quantification. In order to allow for more complex reasoning about join-points and their relationships, P D L supports several forms of pointcut quan-tification. The general form of these expressions was inspired from the De-scription Logics [4] formalism which provides a concise syntax and clean semantics for representing knowledge. In Description Logic, expressions are constructed from unary and binary predicates. This meshes nicely with PDL's concepts of unary pointcuts and binary relations. Quantification in P D L involves checking some condition on a range of values. In practice, this allows a pointcut to match a joinpoint based on properties of related joinpoints. For example, the pointcut f o r a l l f i e l d s t a t i c 10 Chapter 2. The PDL Language matches types whose fields are all static. Quantification expressions take a binary relation, called the range, which generates the range of the quantification. For a joinpoint j , using range R (a binary relation), the range of a quantification is defined as all values x such that (x,j) G R. An existentially or universally quantified expression takes a binary point-cut (the range), and a pointcut expression (the condition). A n exists (sim-ilarly, forall) expression matches joinpoint j if one (similarly, all) of the range values x matches the condition pointcut C (i.e., x € C). Consider the design rule Override GetHashCode() upon overriding Equals(). A violation of the rule is a type which declares a method (i.e., there exists a method) for Equals, but does not declare a GetHashCode method. We can express this in P D L as sourceType &&L e x i s t s method . 'boo l * . Equa l s ( obj e c t ) ' && ! e x i s t s method . ' i n t * . G e t H a s h C o d e ( ) ' : " O v e r r i d e GetHashCode and Equals" Another type of quantification expression is the cardinality limit. It takes a range and a natural number, and checks that the number of values in the range is below, above, or equal-to the bound. Cardinality limit expressions have the form [<,>,=] n range where n is the integer bound. A design rule that makes use of the cardinality limit is Namespaces should contain 5 or more types. We can encode this with the following rule: sourceNamespace kk, < 5 type : " A v o i d namespaces wi th few types" The pointcut sourceNamespace matches all namespaces declared in the as-sembly. The range-type-is used to generate all of the types declared in a namespace, and the pointcut will match if there are less than 5 such types. Composi t ion. The composition of two binary relations is denoted by plac-ing the * operator between the two binary relations expressions. Thus, the expression f*g(x) is equivalent to f(g(x)). This notation can be used as syntactic sugar to remove nested parenthesis. However, a composition is required when a single binary relation is called for (e.g., as the range in an exists expression). 11 Chapter 2. The PDL Language For example, to get a binary relation which matches pairs of types and the types of the fields they contain, we would write type*f i e l d . We use this composed pointcut to check the design rule Types with disposable fields should also be disposable. Checking the rule will involve looking at the type of a field (hence the composition) and is written as follows sourceType &&; e x i s t s t y p e * f i e l d . i m p l e m e n t s ( ' S y s t e m . I D i s p o s a b l e ' ) && ! i m p l e m e n t s ( ' S y s t e m . I D i s p o s a b l e ' ) : "Types wi th d i s p o s a b l e f i e l d s s h o u l d \ be d i s p o s a b l e " This pointcut is explained as follows. The first line will match all types declared in the program. The exists expression in the second and third lines will match only those types with a field which is of a type that implements the IDisposable interface. Finally, the last line of the pointcut matches those types which do not implement IDisposable and so violate the rule. Transitive closures. The (anti-symmetric) transitive closure of a binary relation may be obtained by appending + to the expression. Transitive closures allow P D L to express a limited means of recursion. For exam-ple, the subtype relation may be obtained as the transitive closure of the derivedType relation: d e r i v e d T y p e + This provides a convenient way to define new binary relations over the graph of certain program structures. 2.2 Typed P D L So far we have considered all joinpoints to be of the same type. We now present a static type system for P D L that distinguishes between different types of joinpoints and assigns static types to pointcut expressions based on the types of joinpoints they can match. 2.2 .1 Typ ing Derivations PDL's type system distinguishes between different types of joinpoints such as type, method, field, and bytecode. All joinpoint types supported by the current implementation of P D L are shown in Table 2.3. Each of these 12 Chapter 2. The PDL Language T = {type, method, field,...} M i e T a,ffi , (72 6 P(T) 6,0!, fa e P ( T x T ) b : 8 v : cr 6(p) : {ii I (h,t2) &8,t2 ea} Pi • Q~l P2 • Q~2 pi kk p2 : o\ n (72 Pi : CTI p 2 : c7 2 .. f 0 if CTI = 0 or CT 2 = 0 Pi \\ P2 '• \ I u\ U c2 otherwise p : a I , p : cr 6 : /3 p : a forall b.p : {t2 \ (h,t2) € 8,h e a] b : 8 p : a exists b.p : {t2 \ (ti,t2) € 8, t\ € cr} b:B < nb : {t2 I (t!,t 2) 6 /?} bj_0 b+ : {(ii, i n ) I (ti,t2), • • • , ( t n - i , t„) S /?} : ft fr2 : ft h * 62 : {(ti, t 3) I (ii, i 2 ) G A , fe, is) € ft} T-BINARY T - A N D T - O R T - N O T T - F O R A L L T-EXISTS T-LESS T - T R A N S I T I V E T - C O M P O S E Figure 2.3: Typing rules for pointcuts and binary relations. 13 Chapter 2. The PDL Language Joinpoint Type Description namespace type method argument field property event attribute generic Argument bytecode Namespace Type Method (including constructors) Method argument Field Property Event Attribute of a program element Type argument (to a generic type) Instruction in the program Table 2.3: P D L joinpoint types joinpoint types corresponds to a disjoint subset of joinpoints in the program. In general, a single pointcut may match joinpoints of several different types. Therefore, the type system assigns a set of joinpoint types as the type of a pointcut. Similarly, because the semantics of binary relations is in terms of pairs of joinpoints, the type of a binary relation is the pairs of joinpoint types it could match. P D L primitives come annotated with their type. For example, the point-cut publ ic has type {type, method, field, property} signifying that it matches joinpoints of type type, method, field, or property. Sim-ilarly, the binary relation member relates method, fields, or properties to their declaring type, and thus has type {(method, type), (field, type), (property, type)}. In typed-PDL, a pointcut expression's type is derived by building up from the known types of the primitives. The typing rules are shown in Figure 2.3. Any pointcut expression or binary relation that gets assigned 0 as a type is considered a type error. This confirms to the intuition that pointcut expressions which could never yield results are not meaningful. A subtlety in the T - O R rule is that we have to treat 0 as a special case to ensure that an expression which contains an erroneous subexpression is itself considered erroneous. As an example, the type system determines the type of sourceType Mz interface by taking the intersection of the two primitive types. Thus, the pointcut 14 Chapter 2. The PDL Language has type {type}. While, for the pointcut sourceType && v i r t u a l the intersection of the two primitive types is 0, and so P D L would generate an error message when the pointcut is compiled. 2.2.2 Soundness It is interesting to note that the static typing rules given here are unsound with respect to the untyped semantics given in Figure 2.2. For example, the typing rule T - N O T is unsound. To see this, consider the pointcut ! interface. Our type system assigns the pointcut type {type} (the same type as interface). However, the untyped semantics does not explicitly or implicitly limit the range of matched joinpoints to be of type type. The pointcut thus matches all kinds of joinpoints that aren't even types, for ex-ample, it matches any joinpoint which is of type method (since no method is an interface). One possible way to address this issue would be to use an alternative, sound typing rule: We didn't adopt the above typing rule because it seems overly permissive. For example, an expression like f i e l d ( s o u r c e T y p e ) && ! " c a l l ( ' v o i d * . f o o ( ) ' ) would pass type-checking. We felt that such expressions rather shouldn't pass type-checking since fields never call anything so a pointcut intent on matching fields that do not call a particular method seem ill-conceived. Thus, instead of making the type system sound by adopting some overly relaxed typing rules we decided to keep the more restrictive typing rules and restore soundness by adopting a different typed semantics which is shown in Figure 2.4. The typed semantics restricts matched joinpoints to those that are in the static type derived for the pointcut. Not all evaluation clauses need to be changed. Intuitively, the problem arises only where the untyped semantics allow a joinpoint to match because it is not an element of a pointcut. In such cases we cannot assign a sound type that is more restrictive than T (the set of all types). v : a T - N O T sound 15 Chapter 2. The PDL Language •= {j;| J' • t} all of the joinpoints of a given type t€<7 M O P)--*] = {J I 3 e T[a],j $ Prlp : a]} E T - N O T PT[(forall b . p) : a)} = {j2 | j 2 G Tfaj, V(Ji, 32) G ^ [6] : j i 6 P r M } E T - F O R A L L Pr[(< n 6) : a] = {j 2 | j 2 G T[a], I 0 i , j 2 ) G B [ & l } | <n} E T - L E S S Figure 2.4: Typed semantics for P D L (only the clauses which differ from the untyped semantics are shown At first sight, this our typed semantics may seem like "an ugly patch job". However we believe that is actually a more intuitive semantics, in the sense that where the typed and untyped semantics differ, the typed semantics usually reflects the meaning we would expect whereas the untyped semantics does not. For example, consider the pointcut a b s t r a c t &&; ! i m p l e m e n t s ( ' I S e r i a l i z a b l e ' ) Under the typed semantics it matches abstract types that do not implement an I S e r i a l i z a b l e interface. However, under the untyped semantics it also matches all abstract methods. With the typed semantics we can formulate the following soundness the-orem. T h e o r e m 1 ( S o u n d n e s s ) p : o - , c r ^ 0 => P r b : t f ] G T [ c r ] The proof is straightforward by structural induction on typing derivations. 16 C h a p t e r 3 Implementation This section provides an overview of the implementation of the P D L rule checker. The checker takes a set of P D L design rules and looks for viola-tions (matches to the pointcuts) in a . N E T assembly. Our implementation is a source-to-source compiler. The compiler performs type checking and optimization. The output of the compiler is C# code which performs the analysis encoded in the P D L rules. The resulting C # code is then compiled to bytecode and the analysis is run on a program to find violations of the design rules. We see the following advantages to our implementation. First, by gen-erating (relatively straightforward) imperative code we achieve good perfor-mance when the code is compiled to bytecode. The code we generate also provides a convenient way to inspect the output of the pointcut-compiler to verify its correctness. Second, our primitives are defined in terms of imper-ative methods which makes it relatively easy to extend the language with new primitives. Finally, because we often have multiple options on how to generate code, the compiler has flexibility to chose an efficient plan to perform the analysis. 3.1 Code Generation The C # code produced by the compiler makes calls to an abstract inter-face for program introspection. The introspection interface represents var-ious types of program elements (e.g., types, methods, fields) and provides methods for examining their properties and relationships. The introspection interface was defined to allow multiple back-ends to implement it. We cur-rently have a complete implementation using Microsoft C C I 1 , and partial implementations using Microsoft Phoenix2, and Mono Cecil 3 . A back-end is specified by the user at execution time. 1 Included as part of the FxCop framework 2http://research.microsoft.com/phoenix/ (verified September 2006) 3http: / /www.mono-project.com/Cecil (verified September 2006) 17 Chapter 3. Implementation To implement P D L pointcuts with imperative code, we represent join-points as objects in the introspection API, and use methods of these ob-jects to implement the primitive pointcuts. P D L allows primitives to be implemented by a number of different strategies. For example, the unary primitive sourceType can be implemented with a method that generates all of the types declared in the program, or with a method that takes a type as a parameter and returns a boolean representing if it was declared in the program. This allows the compiler to chose an appropriate method to call depending on the context. For example, in a context where types are being enumerated for another reason, code that does something with source types could be f o r e a c h (Type t i n . . . ) i f ( I sSourceType ( t ) ) // Do something with source type Whereas, in another context source types could be enumerated from scratch f o r e a c h (Type t i n SourceTypes ( ) ) // Do something with source type The P D L implementation makes it easy to define new primitives. P D L has an extension API with which to register a binding between a name of a primitive and a method in the introspection API that provides an imple-mentation of the primitive. No additional meta-data needs to be provided. All necessary information (e.g., type information for the purpose of type checking) is derived from the signature of the method. To compile a pointcut, we must first decide on a plan for analyzing the program to find the matching joinpoints. We call this intermediate repre-sentation an execution plan. Its structure and interpretation is similar to the operator tree representation used in databases [7]. In P D L , an execution plan is a graph-based model of the analysis required to find matches to a joinpoint. Edges represent streams of joinpoints, and nodes transform the streams., A given pointcut may have many equivalent execution plans, and opti-mization techniques may be used to determine the most efficient plan. The main optimization done by the current implementation of P D L is to merge shared subexpression. This is described in the next section.. To compile an execution plan, we generate C # code which performs the encoded analysis. For example, the P D L pointcut method(sourceType &&: sea led) && v i r t u a l 18 Chapter 3. Implementation is compiled to code similar to the following (simplified for presentation): f o r e a c h (Type t i n SourceTypes ( ) ) i f (t . I s S e a l e d Q ) f o r e a c h ( M e t h o d m in t . M e t h o d s ( ) ) i f ( m . I s V i r t u a l ( ) ) // Record m as violation 3.2 Optimization There is a similarity between P D L rule checking and database query evaluation-P D L pointcuts are program queries, and rule checking amounts to accessing the program to find elements which match the query. Because P D L rules are often run at the same time in a large batch, we can use techniques from database multiple-query optimization [24] to improve performance. Multiple-query optimization involves examining the execution plan to detect- subtrees that produce the same result. Then, the two pieces are merged together to avoid a redundant calculation. As an example, consider the design rules Do not declare virtual methods on sealed types, and Do not declare protected methods on sealed types. We encode these rules as method(sourceType && sea led) && v i r t u a l : " r u l e l " method(sourceType && sea led) && p r o t e c t e d : "ru le2" The merging optimization detects the redundancy in computing methods of sealed types. This computation is then merged to generate code like the following: f o r e a c h (Type t i n SourceTypes ( ) ) i f (t . I s S e a l e d Q ) f o r e a c h (Method m i n t .Methods Q ) { i f ( m . I s V i r t u a l ( ) ) // Record m as a violation to rulel i f . ( m . I s P r o t e c t e d ( ) ) // Record m as a violation to rule2 } Rule checking frameworks typically achieve a similar effect of sharing by implementing rules as visitors to certain code elements. The framework 19 Chapter 3. Implementation will iterate through each code element, and pass the element to the Vis i t ( ) method for each rule. Thus, the cost of retrieving each element is amortized over all of the rules. In a typical framework, the visit-able elements are fixed to a small num-ber of basic code elements (e.g., types, methods and fields). However, there is often sharing between rules at a granularity not supported by the frame-work. , For example, imagine there are several rules which govern the way interface I should be implemented. In such a case, there are two options to encode the rules using the visitor pattern: 1. Implement each rule as a separate type visitor. Each visitor first checks if the type implements I, the does the rest of its checking. 2. Combine all of the rules into a single type visitor. When checking a type, the visitor first checks whether the type implements I. If so, the combined rule can check each of its constituent rules. The first option maintains modularity (the rules are all separately encoded), while sacrificing performance (each rule separately calculates the same con-dition). The second option makes the opposite trade-off. By using a declarative language like P D L , combined with the merging optimization, we can achieve both modularity and performance. We can encode the rules separately and rely on the compiler to weave them together. 20 Chapter 4 Comparison with F x C o p We evaluate P D L by comparing it to FxCop 4 , an industrial strength checker for the . N E T Framework. FxCop comes with 201 predefined rules most dealing with the . N E T Framework Design Guidelines [2]. Rules in FxCop are implemented in C # using a visitor pattern. We use FxCop to provide several points of comparison with P D L . First, we investigate expressibility. Using a declarative language like P D L , we expect a loss of expressibility over a general-purpose approach. Comparing with FxCop allows us to quantify this loss, in terms of the fraction of FxCop rules that we can express in P D L . Next, we investigate the conciseness; we expect the declarative approach of P D L to result in more compact rule definitions. Finally, we compare performance. 4.1 Expressiveness To evaluate the expressiveness of P D L , we went through all of the FxCop rules and attempted to encode them in P D L . Some rules were straightfor-ward to encode in P D L , while others were obviously not suitable. The results of this process are shown in Table 4.1. In total there are 201 rules defined in FxCop divided into 9 sections. We encoded 75 of the FxCop rules in P D L . P D L is best able to capture the design and usage rule categories; in both of these categories we are able to encode at least half of the FxCop rules. While we are able to express 75 of the FxCop rules, we must emphasize that the analysis encoded in P D L sometimes differs from that encoded by FxCop. This is not unexpected because design rule checkers like FxCop and those defined with P D L are essentially opportunistic in nature. Rather than actually encoding the truly interesting property, which is often dynamic and intractably hard to verify statically, design rule checkers are opportunistic in that they encode an analysis which checks some approximation of the interesting property that easily checkable with the available machinery. In 4 Version 1.35 21 Chapter 4. Comparison with FxCop Category # rules # in P D L ratio Design 59 39 .66 Globalization 7 2 .29 Interoperability 16 2 .13 Mobility 2 0 0 Naming 26 3 .08 Performance 22 4 .18 Portability 3 0 0 Security 26 5 .19 Usage 40 20 .50 Tota l 201 75 .37 Table 4.1: Overview of the FxCop rules encoded in P D L . some cases, the P D L version is closer to the "spirit" of the design rule, and in other cases, FxCop does a better job. For an example of a rule where FxCop performs a more accurate analysis consider the rule Dispose methods should call base class dispose. The analysis encoded in P D L simply check that there exists a call to the base class method within the dispose method. However, FxCop uses a more precise data and control flow analysis to determine if the base class method is called on all paths through the method. Examples where P D L is more accurate are those using a cflow pointcut. FxCop uses a fairly crude approximation by considering call-chains of at most length 2 whereas P D L considers call-chains of any length. To understand the differences in the results produced by FxCop and P D L we ran the 75 rules in each tool on the Spring Framework [3] and compared the results. This resulted in 110 violations found by FxCop and 158 by P D L . The two tools agreed on 108 violations, while P D L reported 49 that FxCop did not, and FxCop reported 1 that P D L did not. This suggests that, in practice, when the FxCop rules are encoded in P D L , they are able to find most of the violations found by FxCop. Of the rules that P D L can not express, there are three general reasons— either the rule deals with elements missing from P D L joinpoint model, P D L lacks the primitives to express an analysis, or there is an intrinsic complexity in the rule that was not expressible in P D L . Table 4.2 provides a breakdown of the FxCop rules that P D L could not express. 22 Chapter 4. Comparison with FxCop Category Total J P C O Design 20 6 7 7 0 Globalization • 5 1 0 4 0 Interoperability 14 0 13 1 0 Mobility 2 0 0 2 0 Naming 24 2 4 14 4 Performance 18 3 8 4 3 Portability 3 0 1 0 2 Security 21 2 13 6 0 Usage 20 3 9 8 0 Total 127 17 55 46 9 Table 4.2: Overview of the reasons P D L was unable to express FxCop rules. Column J is due to the joinpoint model, P is due to a lack of primitives, C is due to a complex analysis, and O is other. Missing joinpoint type. Some FxCop rules deal with program elements for which there is no corresponding joinpoint in P D L . This includes rules dealing with assemblies, local variables, and literals. Naturally, P D L is unable to express these rules. Lack of primitives. Some of the FxCop rules deal with program ele-ments which P D L has joinpoints for, however P D L currently lacks the prim-itives to check the relevant properties of the joinpoints. A n example of this sort of rule is Do not catch general exception types which requires checking the type of a catch expression to determine if it is of type Exception or ApplicationException. P D L lacks primitives which can pick out catch exceptions and examine their type, and so it is impossible to express this rule. This could be remedied by adding the appropriate primitives. One option would be to add a binary primitive catches where catches(p) matches a bytecode catch instruction if the type it catches matches pointcut p. Then the rule could be expressed as w i t h i n ( s o u r c e T y p e ) && c a t c h e s ( ' E x c e p t i o n ' | | ' A p p l i c a t i o n E x c e p t i o n ' ) : "Do not c a t c h g e n e r a l except ions" 23 Chapter 4. Comparison with FxCop Excessive complexity. Some of the FxCop rules fall into the broad cate-gory of excessive complexity. Examples of such rules range from spell check-ing and parsing, to more complex relationships between multiple program elements. The majority of FxCop's naming rules require spell and case checking on identifiers, and so were not expressible in P D L . As an example of a complex relationship not expressible in P D L , consider the rule Members should differ by more than return types. Checking this rule involves checking pairs of methods to determine if they have the same argument types in the same order. Because P D L reasons about joinpoints in terms of sets, there is no way to capture this ordering relationship. 4.2 Conciseness We evaluate conciseness by comparing the length of the rules encoded in P D L and FxCop. Of the 75 rules' in P D L , the average length is 4 lines (including the line for the error message). Because we do not have the source of FxCop available, we cannot measure the length of the FxCop encodings. However, .we can, with the help of a disassembler, examine the rule assembly and get an approximate idea of the length. We conclude that the smallest FxCop rules are on the order of 10 lines, and the largest on the order of several hundred. Thus, as expected, it is clear that the declarative P D L encodings are much more concise than those of imperative FxCop. 4.3 Performance We compare performance of P D L and FxCop. The Microsoft CCI back-end is used for P D L , which is the same back-end used by FxCop. We measure the time it takes to evaluate a set of rules ignoring the time to initialize the checking infrastructure and load the assembly. This measurement does not reflect the time needed to compile the P D L rules which could be done once and amortized over subsequent checks. Our first set of experiments measures the time to run the 75 rules on programs of various sizes. The results are shown in Table 4.3. Compared to FxCop, P D L apparently executes considerably faster. However it should be acknowledged that it is hard to attribute this speed-up completely to the superiority of PDL's implementation. As pointed out earlier there are semantic differences for some rules expressed in P D L versus FxCop. These semantic differences likely account for some of the performance difference. Also, FxCop does some additional work, such as storing data to later gener-24 Chapter 4. Comparison with FxCop Assembly Size P D L PDL-opt FxCop Spring.Core 296K 2.4 2.1 10.7 SharpDevelop .Core 1.3M 7.7 7.0 32.7 .NET mscorlib 4.2M 9.4 8.4 72.6 Table 4.3: Performance comparison of PDL and FxCop on several different programs. The numbers shown are time in seconds (averages of 10 runs). ate a report. We believe these functionalities only marginally contribute to the difference in running time, but because FxCop is closed-source we had no way of disabling or otherwise objectively measuring the effects of these features on FxCop's running time. We also note that the merging optimization increases the performance of PDL by around 10 percent. In order to measure scalability of PDL with respect to the rule set size and the effect of the merging optimization, we vary the number of rules being evaluated from 1 to 75. For each size n, we randomly select 50 samples of size n from the complete rule set. We then check these rules on mscorlib using PDL with and without optimizations. The times reported for each size is the average of the 50 samples. The results are shown in Figure 4.1. As expected, the merging optimiza-tion becomes more effective as more rules are added to the system. This is because, as the number of rules increases, there is a greater number of intermediate results, and hence a greater opportunity for merging. There is an performance anomaly between sizes 45 and 65 where the speedup in the optimized version is almost lost. We attribute this effect to differing memory usage patterns5 which staggers the affect of the .NET garbage collector's adaptations (which we are unable to control). 5 The optimized version creates fewer objects, with longer lifetimes. 25 Chapter 4. Comparison with FxCop I 1 I I I I I I : I I 0 10 20 30 40 50 60 70 80 number of rules Figure 4.1: Performance comparison between P D L with and without opti-mizations as a function of the number of rules. 26 Chapter 5 Related Work There is a large body of work that deals with tools to check and verify pro-grams to find errors. Approaches can be distinguished based on whether they perform static or dynamic checking. Example of ah approach that uses dynamic checking are jmlc andjmlunit [20]. We are mostly interested in static techniques. In the discussion below we distinguish static approaches based on whether their emphasis is on (static verification of) dynamic prop-erties or structural properties. The former tend to allow developers to cap-ture interesting behavioral properties more precisely but scale less well to larger code-bases. Our work falls in the latter category. In the first category we find approaches which use model checking and automated theorem proving techniques. For example S L A M [5], E S C / E S C -Java [11, 14], Vault [10], Alloy [18], and P Q L [22]. Compared to our work, these approaches are more ambitious with respect to the kinds of properties they intend to verify and how these properties are specified by the devel-oper. Each approach provides different notations for specifying constraints that should hold over the execution of a program and provides an analyzer that attempts to statically verify whether these execution-time constraints hold. While such an approach allows developers to more directly and pre-cisely express dynamic properties they are interested in, the static analyzers tend to be complex and scale less well to larger code-bases. Our approach is radically opposed to these approaches. P D L has a purely static joinpoint model and takes the premise that P D L rules are assertions about static code elements rather than runtime behavior. Thus, a developer using our language cannot directly express runtime properties. Instead they may be able to code-up a P D L rule that is a static approximation of it that is guar-anteed to be relatively easy to check. In this way P D L trades off expressive power and precision for scalability. Examples of approaches which are similar to P D L and share its emphasis on static/structural properties are S A B E R [23], FindBugs [17], FxCop [1], Metal [16], ASTLog [9], SOUL [26], and J T L [8]. S A B E R [23], FindBugs [17], and FxCop [1] are rule-checking frameworks which allow developers to implement checkers in an imperative language. 27 Chapter 5. Related Work The study presented in this paper compares P D L to FxCop. It shows how P D L trades off flexibility to express a wider variety of structural properties for concise definitions and more efficient checking. We believe FxCop is representative for this type of approach. Other approaches that, like P D L , have taken a declarative approach to reasoning about a program's structure are ASTLog [9], S O U L [26] and J T L [8]. S O U L and ASTLog use a declarative language that is similar in syntax and expressiveness to Prolog (i.e., Turing complete). In contrast P D L limits expressiveness. This guarantees that all P D L programs terminate and can be executed in polynomial time (assuming that all PDL's defined primitives are terminating/polynomial). J T L [8] is a logic language for querying Java programs. It is probably the approach that is most similar in nature to P D L . There is strong similarity between the underlying semantics of both J T L and P D L . However the syntax of J T L and P D L are quite different and follow a different philosophy. JTL's syntax is designed to mimic the code elements which they match. P D L syntax is designed to be similar to AspectJ syntax. We believe that because of the differences, some rules would be easier to express with P D L whereas other would be easier to express in J T L but we have not performed a detailed comparison to try to quantify the practical impact of this. In Metal [16], rules are expressed as state machines which are applied to the execution paths of each function in a program. This allows for a natural definition of, for example, rules of the form call X after calling Y which makes behavioral rules more natural. This is contrasted with P D L where rules are essentially queries over structural properties of the program. As we noted in Section 1, researchers are beginning to explore A O P as a mechanism to express and enforce design rules. In addition to the work on AspectJ discussed earlier, [13] presents a checker built as a framework on top of an library for AOP. In this system, rules are encoded imperatively as type visitors which make calls to the A O P interface to inspect the class. In contrast, P D L provides a declarative approach. Other research has focused on the performance of program queries. In [15], a DataLog language for program queries and an accompanying database sys-tem is presented. The system, CodeQuest, aims to efficiently execute Dat-aLog queries over a program by storing the relevant relations in a database and leveraging existing database technology. We see this work as compli-mentary to P D L , as it would be possible to target CodeQuest as another P D L back-end. Currently, the back-ends for P D L are all introspection en-gines. 28 Chapter 6 Conclusion We have presented P D L , an aspect language to declaratively encode de-sign rules. P D L was inspired from the pointcut language in AspectJ, with syntactic additions reminiscent of description logics. P D L introduces a type system to detect meaningless pointcuts and modify the semantics to provide a more appropriate behavior. We demonstrated that P D L can concisely express a non-trivial subset of the rules checked by FxCop. Performance experiments show that our approach is comparable to FxCop, and can scale to large codebases. There are several opportunities for future work on P D L . The results of our evaluation suggest that the expressibility of P D L would benefit by adding new types to the joinpoint model, and expanding the set of prim-itives. Additionally, we plan to explore using P D L to encode application-specific rules. We believe that using a concise, declarative language like P D L could allow the developer to encode design rules as they are encoun-tered in the code. Finally, there is much room for optimizations in the P D L compiler. For example, we plan on expanding our search through the space of equivalent plans to discover plans which are more efficient execution or allow additional opportunities for merging. 29 Bibliography [1] FxCop Team Page. http://gotdotnet.com/team/fxcop, verified September 2006. [2] . N E T Framework Design Guidelines, http://msdn2.microsoft.com/ en-us/library/ms229042. aspx, verified September 2006. [3] Spring . N E T Application Framework, http: //www. springf ramework. net, verified September 2006. [4] Franz Baader, Diego Calvanese, Deborah L . McGuinness, Daniele Nardi, and Peter F . Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge Uni-versity Press, 2003. [5] Thomas Ball and Sriram K. Rajamani. The S L A M project: debugging system software via static analysis. Proceedings of the 29th SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 02), 37(l):l-3, January 2002. [6] Alexander Borgida. Description logics in data management. IEEE Transactions on Knowledge and Data Engineering, 7(5):671-682, 1995. [7] Surajit Chaudhuri. An overview of query optimization in relational systems. In PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 34-43, New York, NY, USA, 1998. A C M Press. [8] Tal Cohen, Joseph (Yossi) Gil, and Italy Maman. Jtl-the Java tools language. In (to appear) OOP SLA '06: Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 2006. [9] Roger F. Crew. A S T L O G : A language for examining abstract syntax trees. In In Proceedings of the USENIX Conference on Domain-Specific Languages, pages 229-242, 1997. 30 Bibliography [10] Robert DeLine and Manuel Fahndrich. Enforcing high-level protocols in low-level software. In SIGPLAN Conference on Programming Language Design and Implementation, pages 59-69, 2001. [11] David L . Detlefs, K. Rustan M . Leino, Greg Nelson, and James B. Saxe. Extended static checking. Technical Report Technical Report T R SRC-159, C O M P A Q SRC, Palo Alto, USA, 1998. [12] Michael Eichberg, Mira Mezini, and Klaus Ostermann. Pointcuts as functional queries. In Wei-Ngan Chin, editor, Programming Languages and Systems: Second Asian Symposium, APLAS 2004, Lecture Notes in Computer Science, pages 366-382, Taipei, Taiwan, November 2004. Springer-Verlag Heidelberg. [13] Michael Eichberg, Mira Mezini, Thorsten Schafer, Claus Beringer, and Karl Matthias Hamel. Enforcing system-wide properties. In ASWEC '04-' Proceedings of the 2004 Australian Software Engineering Confer-ence (ASWEC'04), page 158, Washington, D C , USA, 2004. I E E E Com-puter Society. [14] Cormac Flanagan, K. Rustan M . Leino, Mark Lillibridge, Greg Nelson, James B. Saxe, and Raymie Stata. Extended static checking for Java. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI'2002), volume 37:5, pages 234-245, June 2002. [15] Elnar Hajiyev, Mathieu Verbaere, Oege de Moor, and Kris De Voider. Codequest: querying source code with datalog. In OOPSLA '05: Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 102— 103, New York, NY, USA, 2005. A C M Press. [16] S. Hallem, B. Chelf, Y . Xie, and D. Engler. A system and language for building system-specific static analyses, June, 2002. [17] David Hovemeyer and William Pugh. Finding bugs is easy. SIGPLAN Not, 39(12):92-106, 2004. [18] Daniel Jackson. Alloy: a lightweight object modelling notation. Soft-ware Engineering and Methodology, ll(2):256-290, 2002. [19] Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm, and William G. Griswold. An overview of AspectJ. Lecture Notes in Computer Science, 2072:327-355, 2001. 31 Bibliography [20] G. Leavens and Y . Cheon. Design by contract with J M L , 2003. [21] Karl Lieberherr, David H. Lorenz, and Pengcheng Wu. A case for stat-ically executable advice: checking the law of demeter with aspectj. In AOSD '03: Proceedings of the 2nd international conference on Aspect-oriented software development, pages 40-49, New York, NY, USA, 2003. A C M Press. [22] Michael Martin, Benjamin Livshits, and Monica S. Lam. Finding appli-cation errors and security flaws using pql: a program query language. In OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN con-ference on Object oriented programming systems languages and appli-cations, pages 365-383, New York, NY, USA, 2005. A C M Press. [23] Darrell Reimer, Edith Schonberg, Kavitha Srinivas, Harini Srinivasan, Bowen Alpern, Robert D. Johnson, Aaron Kershenbaum, and Larry Koved. Saber: smart analysis based error reduction. In ISSTA '04: Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, pages 243-251, New York, NY, USA, 2004. A C M Press. [24] Timos K. Sellis. Multiple-query optimization. ACM Trans. Database Syst, 13(l):23-52, 1988. [25] Mati Shomrat and Amiram Yehudai. Obvious or not?: regulating ar-chitectural decisions using aspect-oriented programming. In AOSD '02: Proceedings of the 1st international conference on A sped-oriented soft-ware development, pages 3-9, New York, NY, USA, 2002. A C M Press. [26] Roel Wuyts. Declarative reasoning about the structure object-oriented systems. In Proceedings of the TOOLS USA '98. Conference, pages 112-124. I E E E Computer Society Press, 1998. 32 


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items