RangeDomain

java.lang.Object
- cetus.analysis.RangeDomain

All Implemented Interfaces:

Domain, java.lang.Cloneable
```
public class RangeDomain
extends java.lang.Object
implements java.lang.Cloneable, Domain
```
RangeDomain provides symbolic environment for symbolic expression comparison. An object of this class keeps track of mapping from a symbol to its corresponding expression that represents valid value range of the symbol. It is guaranteed that, at each program point, this mapping is always true. A range domain object is usually created after the range analysis but an empty range domain is still useful as it can compare simple symbolic values such as e and e+1. The result of expression comparison is recorded in a Relation object and the relation provides check methods that return the relationship encoded in the object.
Following example shows the usage of range domain when comparing two expressions. Suppose the range domain rd was computed with range analysis and rd contains the specified value ranges.
```
 Map<Statement, RangeDomain> range_map = RangeAnalysis.getRanges(proc);
 RangeDomain rd = range_map.get(stmt);
 // rd = { i=[1:10], j=[i:20] }
 Relation rel = rd.compare(i, j); 
 // rel.isLE() will return true since i<=j<=20.
 // rel.isGT() will return false since i<=j<=20.
 
```

Constructor Summary

Constructors
Constructor and Description

RangeDomain()
Constructs an empty range domain.

RangeDomain(RangeDomain other)
Constructs a new range domain with the given range domain other.

Constructors
Constructor and Description
`RangeDomain()` Constructs an empty range domain.
`RangeDomain(RangeDomain other)` Constructs a new range domain with the given range domain `other`.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`clear()` Cleans up the fields of RangeDomain.
`RangeDomain`	`clone()` Returns a clone of the range domain.
`Relation`	`compare(Expression e1, Expression e2)` Returns the relation between the two expressions under the constraints implied by the set of value ranges in the RangeDomain object.
`static Relation`	`compare(Expression e1, RangeDomain rd1, Expression e2, RangeDomain rd2)` Compares two expressions symbolically with the given range domain
`Domain`	`diffStrong(Domain other)` Returns the result of strong difference.
`Domain`	`diffWeak(Domain other)` Returns the result of weak difference.
`boolean`	`encloses(Expression e1, Expression e2)`
`boolean`	`equals(Domain other)` Pairwise comparison between two RangeDomain objects.
`boolean`	`equals(RangeDomain other)`
`int`	`evaluateLogic(Expression e)` Evaluates the given logical expression using the constraints.
`Expression`	`expandSymbol(Expression e, Symbol var)` Eliminates all occurrences of the specified variable from the expression by replacing them with their value ranges.
`Expression`	`expandSymbols(Expression e, java.util.Set<Symbol> vars)` Eliminates all occurrences of the specified variables from the expression by replacing them with their value ranges.
`Expression`	`getRange(Symbol var)` Returns the value range for the specified variable.
`java.util.Set<Symbol>`	`getSymbols()` Returns the set of variables whose value ranges are present.
`Domain`	`intersect(Domain other)` Returns intersection of the two domains.
`static Expression`	`intersectRanges(Expression e1, RangeDomain rd1, Expression e2, RangeDomain rd2)` Computes the intersection of the two expressions with the given range domains.
`void`	`intersectRanges(RangeDomain other)` Intersects two sets of value ranges using current range domain.
`boolean`	`isEmptyRange(Expression e)`
`boolean`	`isEQ(Expression e1, Expression e2)`
`boolean`	`isGE(Expression e1, Expression e2)`
`boolean`	`isGT(Expression e1, Expression e2)`
`boolean`	`isLE(Expression e1, Expression e2)`
`boolean`	`isLT(Expression e1, Expression e2)`
`void`	`kill(java.util.Set<Symbol> vars)` Kills the data containing the specified set of symbols.
`void`	`killGlobal()` Kills any ranges containing global variables.
`void`	`killGlobalAnd(java.util.Set<Symbol> and)` Kills any ranges containing global variables and the specified set of variables.
`void`	`killLocal()` Kill any var:range mappings containing local variables.
`void`	`killLocalExcept(java.util.Set<Symbol> except)` Kills any ranges containing local variables except for the specified set of variables.
`void`	`killOrphan()` Kills any ranges containing variables from which Program node is not accessible.
`Domain`	`merge(Domain other)` Returns merge of the two domains (join operation).
`void`	`narrowRanges(RangeDomain other)` Narrows all value ranges of "other" range domain with this range domain.
`void`	`removeRange(Symbol var)` Removes the value range for the specified variable.
`void`	`removeRangeWith(java.util.Set<Symbol> vars)` Removes value ranges containing the specified set of symbols.
`void`	`removeRangeWith(Symbol var)` Removes value ranges containing the specified variable including the range of the variable.
`void`	`removeSymbols(java.util.Set<Symbol> vars)` Removes the ranges for the speicfied variables in the map by replacing them with their value ranges.
`Expression`	`replaceSymbol(Expression e, Symbol var, Expression with)` Replace all occurrences of the specified variable in the given expression with the new expression.
`void`	`replaceSymbol(Symbol var, Expression with)` Replaces all occurrences of the specified variable in the map with the given expression.
`void`	`setRange(Symbol var, Expression value)` Updates the value range for the specified variable.
`int`	`size()` Returns the number of value ranges in the map.
`void`	`substituteForward()` Applies `substituteForward(Expression)` to the range expressions kept in the range domain.
`Expression`	`substituteForward(Expression e)` Substitute all occurrences of the symbols that appear in the expression.
`Expression`	`substituteForward(Expression e, java.util.Set<Symbol> vars)` Substitute all occrrences of the given set of symbols in the expression.
`Expression`	`substituteForward(Expression e, Symbol var)` Substitute all occurrences of the given symbol in the expression with its symbolic values.
`void`	`substituteForwardRange()` Applies `getForwardRange(Symbol)` to the range expressions kept in the range domain.
`Expression`	`substituteForwardRange(Expression e)` Replaces variables within the given expression with their value ranges from the existing range domain.
`RangeDomain`	`substituteForwardRange(RangeDomain rd)` Performs `substituteForwardRange(Expression)` on the value ranges within the given range domain.
`Expression`	`toExpression()` Converts this range domain to an equivalent logical expression.
`java.lang.String`	`toString()` Returns string for this range domain.
`Domain`	`union(Domain other)` Returns union of the two domains if applicable.
`static Expression`	`unionRanges(Expression e1, RangeDomain rd1, Expression e2, RangeDomain rd2)` Computes the union of the two expressions with the given range domains.
`void`	`unionRanges(RangeDomain other)` Merges two sets of value ranges using current range domain (union operation).
`void`	`widenAffectedRanges(RangeDomain other, java.util.Set<Symbol> vars)` Widens subset of value ranges in "other" that contains the specified symbols either in keys or in value ranges.
`void`	`widenRanges(RangeDomain other)` Widens all value ranges of "other" range domain with this range domain.

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - RangeDomain
```
public RangeDomain()
```
    Constructs an empty range domain.
  - RangeDomain
```
public RangeDomain(RangeDomain other)
```
    Constructs a new range domain with the given range domain other. Unlike clone(), this constructor reuses the expression contained in other.
    
    Parameters:
    other - the original range domain
- Method Detail
  - clone
```
public RangeDomain clone()
```
    Returns a clone of the range domain.
    
    Specified by:
    
    clone in interface Domain
    
    Overrides:
    
    clone in class java.lang.Object
    
    Returns:
    the cloned range domain.
  - clear
```
public void clear()
```
    Cleans up the fields of RangeDomain.
  - size
```
public int size()
```
    Returns the number of value ranges in the map.
    
    Returns:
    the number of value ranges.
  - setRange
```
public void setRange(Symbol var,
            Expression value)
```
    Updates the value range for the specified variable.
    
    Parameters:
    var - the variable whose value range is updated.
    value - the new value range of the variable.
  - getRange
```
public Expression getRange(Symbol var)
```
    Returns the value range for the specified variable.
    
    Parameters:
    var - the variable whose value range is asked for.
    
    Returns:
    the value range for the variable.
  - removeRange
```
public void removeRange(Symbol var)
```
    Removes the value range for the specified variable.
    
    Parameters:
    var - the variable whose value range is being removed.
  - removeRangeWith
```
public void removeRangeWith(Symbol var)
```
    Removes value ranges containing the specified variable including the range of the variable.
    
    Parameters:
    var - the variable whose containers are removed.
  - removeRangeWith
```
public void removeRangeWith(java.util.Set<Symbol> vars)
```
    Removes value ranges containing the specified set of symbols.
    
    Parameters:
    vars - the variables whose containers are removed.
  - getSymbols
```
public java.util.Set<Symbol> getSymbols()
```
    Returns the set of variables whose value ranges are present.
    
    Returns:
    the set of variables.
  - toString
```
public java.lang.String toString()
```
    Returns string for this range domain.
    
    Overrides:
    
    toString in class java.lang.Object
    
    Returns:
    string representation of this object.
  - toExpression
```
public Expression toExpression()
```
    Converts this range domain to an equivalent logical expression. e.g., a=[-INF,b] becomes a&lt=b.
    
    Returns:
    the equivalent logical expression.
  - isGT
```
public boolean isGT(Expression e1,
           Expression e2)
```
  - isGE
```
public boolean isGE(Expression e1,
           Expression e2)
```
  - isLT
```
public boolean isLT(Expression e1,
           Expression e2)
```
  - isLE
```
public boolean isLE(Expression e1,
           Expression e2)
```
  - isEQ
```
public boolean isEQ(Expression e1,
           Expression e2)
```
  - compare
```
public Relation compare(Expression e1,
               Expression e2)
```
    Returns the relation between the two expressions under the constraints implied by the set of value ranges in the RangeDomain object. For a single call to this method, a new cache is created to speed up the comparison.
    
    Parameters:
    e1 - the first expression being compared
    e2 - the second expression being compared
    
    Returns:
    the Relation that stores the result of comparison
  - compare
```
public static Relation compare(Expression e1,
               RangeDomain rd1,
               Expression e2,
               RangeDomain rd2)
```
    Compares two expressions symbolically with the given range domain
    
    Parameters:
    e1 - first expression
    rd1 - first range domain
    e2 - second expression
    rd2 - second range domain
    
    Returns:
    Relation of the two expressions
  - evaluateLogic
```
public int evaluateLogic(Expression e)
```
    Evaluates the given logical expression using the constraints.
    
    Parameters:
    e - the logical expression.
    
    Returns:
    the evaluation result; -1 for unknown, 0 for false, 1 for true.
  - substituteForward
```
public Expression substituteForward(Expression e,
                           Symbol var)
```
    Substitute all occurrences of the given symbol in the expression with its symbolic values. The substitution is performed only if there is a non-cyclic substitution order which produces a valid forward substitution.
    
    Parameters:
    e - the expression to be substituted.
    var - the symbol to be replaced.
    
    Returns:
    the forward-substituted expression.
  - substituteForward
```
public Expression substituteForward(Expression e,
                           java.util.Set<Symbol> vars)
```
    Substitute all occrrences of the given set of symbols in the expression.
    
    Parameters:
    e - the expression to be substituted.
    vars - the set of symbols to be replaced.
    
    Returns:
    the forward-substituted expression.
  - substituteForward
```
public Expression substituteForward(Expression e)
```
    Substitute all occurrences of the symbols that appear in the expression.
    
    Parameters:
    e - the expression to be substituted.
    
    Returns:
    the resulting expression.
  - substituteForward
```
public void substituteForward()
```
    Applies substituteForward(Expression) to the range expressions kept in the range domain.
  - substituteForwardRange
```
public void substituteForwardRange()
```
    Applies getForwardRange(Symbol) to the range expressions kept in the range domain.
  - substituteForwardRange
```
public Expression substituteForwardRange(Expression e)
```
    Replaces variables within the given expression with their value ranges from the existing range domain.
    
    Parameters:
    e - the expression to be manipulated.
    
    Returns:
    the resulting expression.
  - substituteForwardRange
```
public RangeDomain substituteForwardRange(RangeDomain rd)
```
    Performs substituteForwardRange(Expression) on the value ranges within the given range domain.
    
    Parameters:
    rd - the range domain to be manipulated.
    
    Returns:
    the resulting range domain.
  - removeSymbols
```
public void removeSymbols(java.util.Set<Symbol> vars)
```
    Removes the ranges for the speicfied variables in the map by replacing them with their value ranges.
    
    Parameters:
    vars - the set of variables being removed
  - replaceSymbol
```
public void replaceSymbol(Symbol var,
                 Expression with)
```
    Replaces all occurrences of the specified variable in the map with the given expression.
    
    Parameters:
    var - the variable being replaced
    with - the expression being replaced with
  - replaceSymbol
```
public Expression replaceSymbol(Expression e,
                       Symbol var,
                       Expression with)
```
    Replace all occurrences of the specified variable in the given expression with the new expression.
    
    Parameters:
    e - the expression being modified
    var - the variable being replaced
    with - the new expression being replaced with
  - expandSymbols
```
public Expression expandSymbols(Expression e,
                       java.util.Set<Symbol> vars)
```
    Eliminates all occurrences of the specified variables from the expression by replacing them with their value ranges.
    
    Parameters:
    e - the expression to be modified.
    vars - the set of symbols to be replaced by their ranges.
  - expandSymbol
```
public Expression expandSymbol(Expression e,
                      Symbol var)
```
    Eliminates all occurrences of the specified variable from the expression by replacing them with their value ranges.
    
    Parameters:
    e - the expression to be modified.
    var - the symbol to be replaced by its range.
  - intersectRanges
```
public void intersectRanges(RangeDomain other)
```
    Intersects two sets of value ranges using current range domain.
    
    Parameters:
    other - the range domain intersected with
  - unionRanges
```
public void unionRanges(RangeDomain other)
```
    Merges two sets of value ranges using current range domain (union operation).
    
    Parameters:
    other - the range domain merged with
  - widenRanges
```
public void widenRanges(RangeDomain other)
```
    Widens all value ranges of "other" range domain with this range domain.
    
    Parameters:
    other - value ranges being widened
  - widenAffectedRanges
```
public void widenAffectedRanges(RangeDomain other,
                       java.util.Set<Symbol> vars)
```
    Widens subset of value ranges in "other" that contains the specified symbols either in keys or in value ranges.
    
    Parameters:
    other - the range domain containing widening operands
    vars - set of symbols that trigger widening
  - narrowRanges
```
public void narrowRanges(RangeDomain other)
```
    Narrows all value ranges of "other" range domain with this range domain.
    
    Parameters:
    other - value ranges being narrowed.
  - intersectRanges
```
public static Expression intersectRanges(Expression e1,
                         RangeDomain rd1,
                         Expression e2,
                         RangeDomain rd2)
```
    Computes the intersection of the two expressions with the given range domains.
    
    Parameters:
    e1 - first expression
    rd1 - first range domain
    e2 - second expression
    rd2 - second range domain
    
    Returns:
    intersection of the two expressions
  - unionRanges
```
public static Expression unionRanges(Expression e1,
                     RangeDomain rd1,
                     Expression e2,
                     RangeDomain rd2)
```
    Computes the union of the two expressions with the given range domains.
    
    Parameters:
    e1 - first expression
    rd1 - first range domain
    e2 - second expression
    rd2 - second range domain
    
    Returns:
    union of the two expressions
  - isEmptyRange
```
public boolean isEmptyRange(Expression e)
```
  - encloses
```
public boolean encloses(Expression e1,
               Expression e2)
```
  - union
```
public Domain union(Domain other)
```
    Description copied from interface: Domain
    
    Returns union of the two domains if applicable.
    
    Specified by:
    
    union in interface Domain
    
    Parameters:
    other - the domain to be unioned.
    
    Returns:
    the resulting Domain.
  - merge
```
public Domain merge(Domain other)
```
    Description copied from interface: Domain
    
    Returns merge of the two domains (join operation).
    
    Specified by:
    
    merge in interface Domain
    
    Parameters:
    other - the domain to be merged.
    
    Returns:
    the resulting Domain.
  - intersect
```
public Domain intersect(Domain other)
```
    Description copied from interface: Domain
    
    Returns intersection of the two domains.
    
    Specified by:
    
    intersect in interface Domain
    
    Parameters:
    other - the domain to be intersected.
    
    Returns:
    the resulting Domain.
  - diffStrong
```
public Domain diffStrong(Domain other)
```
    Description copied from interface: Domain
    
    Returns the result of strong difference. Strong difference means d1-d2 = {} if the difference is not computatble.
    
    Specified by:
    
    diffStrong in interface Domain
    
    Parameters:
    other - the domain to be subtracted.
    
    Returns:
    the resulting Domain.
  - diffWeak
```
public Domain diffWeak(Domain other)
```
    Description copied from interface: Domain
    
    Returns the result of weak difference. Weak difference means d1-d2 = d1 if the difference is not computable.
    
    Specified by:
    
    diffWeak in interface Domain
    
    Parameters:
    other - the domain to be subtracted.
    
    Returns:
    the resulting Domain.
  - kill
```
public void kill(java.util.Set<Symbol> vars)
```
    Description copied from interface: Domain
    
    Kills the data containing the specified set of symbols.
    
    Specified by:
    
    kill in interface Domain
    
    Parameters:
    vars - the input set of symbols.
  - equals
```
public boolean equals(RangeDomain other)
```
  - equals
```
public boolean equals(Domain other)
```
    Pairwise comparison between two RangeDomain objects.
    
    Specified by:
    
    equals in interface Domain
    
    Parameters:
    other - the RangeDomain object being compared to this object.
    
    Returns:
    true if they are equal, false otherwise.
  - killLocal
```
public void killLocal()
```
    Kill any var:range mappings containing local variables.
  - killLocalExcept
```
public void killLocalExcept(java.util.Set<Symbol> except)
```
    Kills any ranges containing local variables except for the specified set of variables.
    
    Parameters:
    except - the set of variables not considered for kill.
  - killGlobal
```
public void killGlobal()
```
    Kills any ranges containing global variables.
  - killGlobalAnd
```
public void killGlobalAnd(java.util.Set<Symbol> and)
```
    Kills any ranges containing global variables and the specified set of variables.
    
    Parameters:
    and - the additional variables to be considered for kill.
  - killOrphan
```
public void killOrphan()
```
    Kills any ranges containing variables from which Program node is not accessible. Any formal parameters and other symbols for temporary purposes are killed.

Class RangeDomain

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

RangeDomain

RangeDomain

Method Detail

clone

clear

size

setRange

getRange

removeRange

removeRangeWith

removeRangeWith

getSymbols

toString

toExpression

isGT

isGE

isLT

isLE

isEQ

compare

compare

evaluateLogic

substituteForward

substituteForward

substituteForward

substituteForward

substituteForwardRange

substituteForwardRange

substituteForwardRange

removeSymbols

replaceSymbol

replaceSymbol

expandSymbols

expandSymbol

intersectRanges

unionRanges

widenRanges

widenAffectedRanges

narrowRanges

intersectRanges

unionRanges

isEmptyRange

encloses

union

merge

intersect

diffStrong

diffWeak

kill

equals

equals

killLocal

killLocalExcept

killGlobal

killGlobalAnd

killOrphan