Domains

Domains (Data structures)

We use the several data structures for the analysis. Since the data structures reflect the design of the analysis domain, it is crucial to understand the analysis.

Type

Type is the super-class of all types. It has several sub-classes.

• ObjType extends Type: ObjType is the class for abstract objects. Each FnType has one ObjType instance which represents all of its concrete objects. ObjType has instance variable props which is a mapping from string properties to AVals. We use null value to represent the unknown properties.
• PrimType extends Type : PrimType has 3 instances - PrimNumber, PrimString and PrimBoolean. We abstract each primitive value into one of the 3 instances.
• FnType extends ObjType : Since functions are also objects, FnType inherits ObjType. FnType has additional information specific for functions like list of parameters, abstract scope, lexical this and so on.
• ArrType extends ObjType : ArrType is the class for arrays.

AVal

Calcium basically collects possible types of expressions and variables into corresponding sets. AVals basically constitute not only type sets but also propagation graph.

• AVal's instance variable types collects its types.
• AVal's instance variable forwards collects its propagation targets. Here, a propagation target can be either AVal or CSTR.

Therefore, we know the propagation status from types and propagation graphs from forwards. AVal's two most important methods are :

• addType(type) : add a single type to this and also add type to each target in forwards.
• propagate(target) : add all the types it has to the target and adds target to its forwards.

VarBlock

VarBlock represents a syntactic block where we can declare variables. We collect basic information about block scopes into VarBlocks use it to construct Scope.

• Its instance variable paren is pointing to the parent varBlock.
• Its instance variable blockType denotes its type of block. Possible types of a block are globalBlock, oldFunctionBlock, arrowFunctionBlock, parameterBlock, catchBlock and normalBlock.
• Its instance variable paramVarNames has the array of its parameter variables, and localVarNames has the array of its local variables. These variables are used to create a varMap instance. varMap is a mapping from its variable names to their AVals.
• Its instance variable instances is a mapping from Context to varMap. Note that one varMap can be included by multiple Scope instances.
• The most important method is getScopeInstance(paren, delta) which returns a Scope instance whose parent Scope is paren and whose varMap is an instance for delta context.

Scope

Scope is the class for abstract scopes which we carry during constraint generation to obtain AVals for variables.

• Its instance variable paren has the parent Scope instance. We visit a finite list of Scopes to look up variables. Note that the graph of Shape induced by paren does not have any cycles.
• Its instance variable varMap has the mapping from variables to their AVals.
• The most important method is getAValOf(varName) that returns the AVal for variable named varName from varMap. It recursively visits parent Scope if the variable is not found in its varMap.

CallSiteContext

Calcium supports context sensitivity by distinguishing various AVals according to the context. The context information is a list of call-sites. CallSiteContext generates and manipulates the context information. To analyze functions that have never been called, we introduced nullContext and we insert fake calls from nullContext encountering functions' declarations. At nullContext, we do not propagate any types to arguments. Note that appending a call-site to nullContext gives again nullContext. You may regard nullContext as the bottom of all contexts.

Status

Status is the class for environmental information that we carry during the constraint generation. Each status instance has

• self : AVal for the current this
• ret : AVal for collecting return values
• exc : AVal for collecting exception values
• delta : CallSiteContext instance for current context
• sc : Scope instance for current scope We should change the Status when we visit functions, block, try block and so on. We provide deep equality for Status not to visit 'same' code with 'same' status.

AbsCache

For each analysis, we use only one instance AbsCache which is Ĉ. Ĉ is basically a mapping from program location and context to its corresponding AVal. It is useful when querying the analysis result since Ĉ has most of the data.

CSTR

CSTR is the super class of special constraints. A CSTR instance can be a target for type propagation since it has addType function. However, the behavior of addType is quite different from that of AVal. The following items are the subclasses of CSTR. Note that the parameters are the constructor's parameters.

• ReadProp(prop, to) : When an AVal for a receiver gets a new type, the AVal for the member access can get new types from the property of the new type. For such case, we generate a constraint from the AVal of the receiver to new ReadProp(prop, to) where prop is a string or null representing the property and to is the AVal for member access. When a type is added to the receiver AVal, addType(obj) is executed where obj being the new type. Due to JavaScript's prototype inheritance, in principle we should recursively generate similar constraints for all prototype types. However, we made an unsound choice : we stop visiting prototypes as soon as we find the property. The intention is to read out the property from the most closest types in the prototype chain. For assisting property names, often this unsound approach is faster and what users expect.
• WriteProp(prop, from) : Assume we have a property write statement. When the AVal for the receiver gets a new type, its property should contain the types of RHS. For such case, we generate a constraint from the AVal of the receiver to WriteProp(prop, from) where prop represents the property and from is the AVal of RHS.
• IsAdded(other, to) : For a binary addition, we generate a constraint from one operand to IsAdded(other, to) where other is the AVal of the other operand, and to is the AVal of the result of the addition. Basically, when a type is added to the operand, we look into the AVal of the other operand and conditionally add PrimString or PrimNumber to to AVal.
• IsCallee(self, args, ret, exc, delta) : For a method or a function call-site, we generate a constraint from the callee AVal to IsCallee(self, args, ret, exc, delta). Let us explain the meaning of each argument.
• self : self is the AVal of the receiver. When the call is not a method invocation, it will be an AVal containing the type for global object.
• args : args is an array of AVal where the i-th element is the AVal of the i-th argument of the call.
• ret : ret is the AVal for the call expression. Inside the function, we shall propagate the arguments of return statements to the AVal of ret.
• exc : exc is the AVal for collecting escaping exceptions. Those exceptions that can escape the callee should be collected in exc.
• delta : delta denotes the call-site context of the call. Whenever an instance of FnType is propagated to the callee AVal, the corresponding function gets analyzed using self, args, ret, exc and delta.
• IsCtor(args, ret, exc, delta) : We use this constraint for new expression. This constraint is quite similar to IsCallee except a few things.
• we do not need self since this will refer to the newly created instance.
• By default, ret will get propagated from this in the constructor.
• IfObjType(aval) : IfObjType(aval) is a wrapper of AVal aval. If an AVal is wrapped by IfObjType, only ObjType can be propagated to the AVal.