Module: PredictionContextFunctions::Methods

Defined in:: lib/antlr4/PredictionContext.rb

Instance Method Summary collapse

#calculateListsHashCode(parents, returnStates) ⇒ Object
#combineCommonParents(parents) ⇒ Object

Make pass over all M parents; merge any equals() ones.
#getAllContextNodes(context, nodes = nil, visited = nil) ⇒ Object

# extra structures, but cut/paste/morphed works, so leave it.
#getCachedPredictionContext(context, contextCache, visited) ⇒ Object
#merge(a, b, rootIsWildcard, mergeCache) ⇒ Object

def merge(a:PredictionContext, b:PredictionContext, rootIsWildcard:bool, mergeCache:dict):.
#mergeArrays(a, b, rootIsWildcard, mergeCache) ⇒ Object

Merge two ArrayPredictionContext instances.
#mergeRoot(a, b, rootIsWildcard) ⇒ Object

Handle case where at least one of a or b is #EMPTY.
#mergeSingletons(a, b, rootIsWildcard, mergeCache) ⇒ Object

Merge two SingletonPredictionContext instances.
#PredictionContextFromRuleContext(atn, outerContext = nil) ⇒ Object

Instance Method Details

#calculateListsHashCode(parents, returnStates) ⇒ `Object`

# File 'lib/antlr4/PredictionContext.rb', line 291

def calculateListsHashCode(parents, returnStates)
        str_parents = parents.map{|parent| parent.to_s }
        str_rs = returnStates.map{|r| r.to_s }
        return [str_parents,str_rs].flatten.join('').hash 
end

#combineCommonParents(parents) ⇒ `Object`

Make pass over all M parents; merge any equals() ones. /

# File 'lib/antlr4/PredictionContext.rb', line 589

def combineCommonParents(parents)
    uniqueParents = Hash.new

    parents.each{|parent| 
        if not uniqueParents.has_key? parent
            uniqueParents[parent] = parent
        end
    }
    parents.each_index {|p|
        parents[p] = uniqueParents[parents[p]]
    }
end

#getAllContextNodes(context, nodes = nil, visited = nil) ⇒ `Object`

# extra structures, but cut/paste/morphed works, so leave it. # seems to do a breadth-first walk public static List<PredictionContext> getAllNodes(PredictionContext context) { Map<PredictionContext, PredictionContext> visited = new IdentityHashMap<PredictionContext, PredictionContext>(); Deque<PredictionContext> workList = new ArrayDeque<PredictionContext>(); workList.add(context); visited.put(context, context); List<PredictionContext> nodes = new ArrayList<PredictionContext>(); while (!workList.isEmpty()) { PredictionContext current = workList.pop(); nodes.add(current); for (int i = 0; i < current.size(); i++) { PredictionContext parent = current.getParent(i); if ( parent!=null && visited.put(parent, parent) == null) { workList.push(parent); } } } return nodes; } ter’s recursive version of Sam’s getAllNodes()

# File 'lib/antlr4/PredictionContext.rb', line 670

def getAllContextNodes(context, nodes=nil, visited=nil)
    if nodes.nil? 
        nodes = Array.new
        return getAllContextNodes(context, nodes, visited)
    elsif visited.nil? 
        visited = Hash.new
        return getAllContextNodes(context, nodes, visited)
    else
        if context.nil? or visited.has_key? context
            return nodes
        end
        visited[context] =  context
        nodes.add(context)
        for i in 0..context.length do
            getAllContextNodes(context.getParent(i), nodes, visited)
        end
        return nodes
    end
end

#getCachedPredictionContext(context, contextCache, visited) ⇒ `Object`

# File 'lib/antlr4/PredictionContext.rb', line 601

def getCachedPredictionContext(context, contextCache, visited)
    if context.isEmpty()
        return context
    end
    existing = visited[context]
    return existing unless existing.nil? 
    existing = contextCache.get(context)
    if not existing.nil? then 
        visited[context] = existing
        return existing
    end
    changed = false
    parents = Array.new context.length()
    parents.each_index do |i| 
        parent = getCachedPredictionContext(context.getParent(i), contextCache, visited)
        if changed or parent != context.getParent(i)
            if not changed then
                parents = Array.new context.length()
                context.each_index {|j| #for j in range(0, len(context)):
                    parents[j] = context.getParent(j)
                }
                changed = true
            end
            parents[i] = parent
        end
    end
    if not changed
        contextCache.add(context)
        visited[context] = context
        return context
    end
    updated = nil
    if parents.length == 0
        updated = PredictionContext.EMPTY
    elsif parents.length == 1
        updated = SingletonPredictionContext.create(parents[0], context.getReturnState(0))
    else
        updated = ArrayPredictionContext.new(parents, context.returnStates)
    end

    contextCache.add(updated)
    visited[updated] = updated
    visited[context] = updated

    return updated
end

#merge(a, b, rootIsWildcard, mergeCache) ⇒ `Object`

def merge(a:PredictionContext, b:PredictionContext, rootIsWildcard:bool, mergeCache:dict):

# File 'lib/antlr4/PredictionContext.rb', line 297

def merge(a, b, rootIsWildcard, mergeCache)
    #assert a is not None and b is not None # must be empty context, never null

    # share same graph if both same
    return a if a==b

    if a.kind_of? SingletonPredictionContext and b.kind_of? SingletonPredictionContext
        return mergeSingletons(a, b, rootIsWildcard, mergeCache)
    end

    # At least one of a or b is array
    # If one is $ and rootIsWildcard, return $ as# wildcard
    if rootIsWildcard then
        return a if  a.kind_of? EmptyPredictionContext 
        return b if b.kind_of? EmptyPredictionContext 
    end
    # convert singleton so both are arrays to normalize
    if a.kind_of? SingletonPredictionContext 
        a = ArrayPredictionContext.new(a)
    end
    if b.kind_of? SingletonPredictionContext
        b = ArrayPredictionContext.new(b)
    end
    return mergeArrays(a, b, rootIsWildcard, mergeCache)
end

#mergeArrays(a, b, rootIsWildcard, mergeCache) ⇒ `Object`

Merge two ArrayPredictionContext instances.

Different tops, different parents.
<embed src=“images/ArrayMerge_DiffTopDiffPar.svg” type=“image/svg+xml”/>

Shared top, same parents.
<embed src=“images/ArrayMerge_ShareTopSamePar.svg” type=“image/svg+xml”/>

Shared top, different parents.
<embed src=“images/ArrayMerge_ShareTopDiffPar.svg” type=“image/svg+xml”/>

Shared top, all shared parents.
<embed src=“images/ArrayMerge_ShareTopSharePar.svg” type=“image/svg+xml”/>

Equal tops, merge parents and reduce top to SingletonPredictionContext.
<embed src=“images/ArrayMerge_EqualTop.svg” type=“image/svg+xml”/> / def mergeArrays(a:ArrayPredictionContext, b:ArrayPredictionContext, rootIsWildcard:bool, mergeCache:dict):

# File 'lib/antlr4/PredictionContext.rb', line 496

def mergeArrays(a, b, rootIsWildcard, mergeCache)
    if mergeCache 
        previous = mergeCache.get(a,b)
        return previous unless previous.nil?
        previous = mergeCache.get(b,a)
        return previous unless previous.nil?
    end
    # merge sorted payloads a + b => M
    i = 0 # walks a
    j = 0 # walks b
    k = 0 # walks target M array

    mergedReturnStates = Array.new(a.returnState.length + b.returnStates.length)
    mergedParents = Array.new(mergedReturnStates.length)
    # walk and merge to yield mergedParents, mergedReturnStates
    while i<a.returnStates.length and j<b.returnStates.length do
        a_parent = a.parents[i]
        b_parent = b.parents[j]
        if a.returnStates[i]==b.returnStates[j] then
            # same payload (stack tops are equal), must yield merged singleton
            payload = a.returnStates[i]
            # $+$ = $
            bothDollars = (payload == PredictionContext::EMPTY_RETURN_STATE and \
                            a_parent.nil? and b_parent.nil? )
            ax_ax = ( ! a_parent.nil? and ! b_parent.nil?) and a_parent==b_parent # ax+ax -> ax
            if bothDollars or ax_ax
                mergedParents[k] = a_parent # choose left
                mergedReturnStates[k] = payload
            else # ax+ay -> a'[x,y]
                mergedParent = merge(a_parent, b_parent, rootIsWildcard, mergeCache)
                mergedParents[k] = mergedParent
                mergedReturnStates[k] = payload
            end
            i = i + 1 # hop over left one as usual
            j = j + 1 # but also skip one in right side since we merge
        elsif a.returnStates[i]<b.returnStates[j] # copy a[i] to M
            mergedParents[k] = a_parent
            mergedReturnStates[k] = a.returnStates[i]
            i = i + 1 
        else # b > a, copy b[j] to M
            mergedParents[k] = b_parent
            mergedReturnStates[k] = b.returnStates[j]
            j = j + 1 
        end
        k = k + 1
    end
    # copy over any payloads remaining in either array
    if i < a.returnStates.length then
        for p in i..a.returnStates.length()-1 do 
            mergedParents[k] = a.parents[p]
            mergedReturnStates[k] = a.returnStates[p]
            k = k + 1
        end
    else
        for p in j..b.returnStates.length()-1  do
            mergedParents[k] = b.parents[p]
            mergedReturnStates[k] = b.returnStates[p]
            k = k + 1
        end
    end

    # trim merged if we combined a few that had same stack tops
    if k < mergedParents.length() # write index < last position; trim
        if k == 1 # for just one merged element, return singleton top
            a_ = SingletonPredictionContext.create(mergedParents[0], mergedReturnStates[0])
            mergeCache.put(a,b,a_) if mergeCache 
            return a_
        end
        mergedParents = mergedParents[0..k-1]
        mergedReturnStates = mergedReturnStates[0..k-1]
    end
    capM = ArrayPredictionContext.new(mergedParents, mergedReturnStates)

    # if we created same array as a or b, return that instead
    # TODO: track whether this is possible above during merge sort for speed
    if capM==a
        mergeCache.put(a,b,a) if mergeCache 
        return a
    end
    if capM==b
        mergeCache.put(a,b,b) if mergeCache 
        return b
    end
    combineCommonParents(mergedParents)

    mergeCache.put(a,b,capM) if mergeCache 
    return capM
end

#mergeRoot(a, b, rootIsWildcard) ⇒ `Object`

Handle case where at least one of a or b is #EMPTY. In the following diagrams, the symbol $ is used to represent #EMPTY.

<h2>Local-Context Merges</h2>

These local-context merge operations are used when rootIsWildcard is true.

#EMPTY is superset of any graph; return #EMPTY.
<embed src=“images/LocalMerge_EmptyRoot.svg” type=“image/svg+xml”/>

#EMPTY and anything is #EMPTY, so merged parent is #EMPTY; return left graph.
<embed src=“images/LocalMerge_EmptyParent.svg” type=“image/svg+xml”/>

Special case of last merge if local context.
<embed src=“images/LocalMerge_DiffRoots.svg” type=“image/svg+xml”/>

<h2>Full-Context Merges</h2>

These full-context merge operations are used when rootIsWildcard is false.

Must keep all contexts; #EMPTY in array is a special value (and null parent).
<embed src=“images/FullMerge_EmptyRoot.svg” type=“image/svg+xml”/>

otherwise false to indicate a full-context merge / def mergeRoot(a:SingletonPredictionContext, b:SingletonPredictionContext, rootIsWildcard:bool):

Parameters:

a —

the first SingletonPredictionContext
b —

the second SingletonPredictionContext
rootIsWildcard (@code true) —

if this is a local-context merge,

# File 'lib/antlr4/PredictionContext.rb', line 456

def mergeRoot(a, b, rootIsWildcard)
    if rootIsWildcard
        return PredictionContext.EMPTY if PredictionContext.EMPTY == a ## + b =#
        return PredictionContext.EMPTY if PredictionContext.EMPTY == b # a +# =#
    else
        if PredictionContext.EMPTY == a and PredictionContext.EMPTY == b then
            return PredictionContext.EMPTY # $ + $ = $
        elsif PredictionContext.EMPTY == a # $ + x = [$,x]
            payloads = [ b.returnState, PredictionContext::EMPTY_RETURN_STATE ]
            parents = [ b.parentCtx, nil ]
            return ArrayPredictionContext.new(parents, payloads)
        elsif PredictionContext.EMPTY == b # x + $ = [$,x] ($ is always first if present)
            payloads = [ a.returnState, PredictionContext::EMPTY_RETURN_STATE ]
            parents = [ a.parentCtx, nil ]
            return ArrayPredictionContext.new(parents, payloads)
        end
    end
    return nil
end

#mergeSingletons(a, b, rootIsWildcard, mergeCache) ⇒ `Object`

Merge two SingletonPredictionContext instances.

Stack tops equal, parents merge is same; return left graph.
<embed src=“images/SingletonMerge_SameRootSamePar.svg” type=“image/svg+xml”/>

Same stack top, parents differ; merge parents giving array node, then remainders of those graphs. A new root node is created to point to the merged parents.
<embed src=“images/SingletonMerge_SameRootDiffPar.svg” type=“image/svg+xml”/>

Different stack tops pointing to same parent. Make array node for the root where both element in the root point to the same (original) parent.
<embed src=“images/SingletonMerge_DiffRootSamePar.svg” type=“image/svg+xml”/>

Different stack tops pointing to different parents. Make array node for the root where each element points to the corresponding original parent.
<embed src=“images/SingletonMerge_DiffRootDiffPar.svg” type=“image/svg+xml”/>

otherwise false to indicate a full-context merge / def mergeSingletons(a:SingletonPredictionContext, b:SingletonPredictionContext, rootIsWildcard:bool, mergeCache:dict):

Parameters:

a —

the first SingletonPredictionContext
b —

the second SingletonPredictionContext
rootIsWildcard (@code true) —

if this is a local-context merge,
mergeCache

# File 'lib/antlr4/PredictionContext.rb', line 351

def mergeSingletons(a, b, rootIsWildcard, mergeCache)
    if mergeCache then
        previous = mergeCache.get(a,b)
        if not previous.nil? 
            return previous
        end
        previous = mergeCache.get(b,a)
        if not previous.nil? 
            return previous
        end
    end
    rootMerge = mergeRoot(a, b, rootIsWildcard)
    if rootMerge then
        if mergeCache then
            mergeCache.put(a, b, rootMerge)
        end
        return rootMerge
    end

    if a.returnState==b.returnState then
        parent = merge(a.parentCtx, b.parentCtx, rootIsWildcard, mergeCache)
        # if parent is same as existing a or b parent or reduced to a parent, return it
        return a if parent == a.parentCtx # ax + bx = ax, if a=b
        return b if parent == b.parentCtx # ax + bx = bx, if a=b
        # else: ax + ay = a'[x,y]
        # merge parents x and y, giving array node with x,y then remainders
        # of those graphs.  dup a, a' points at merged array
        # new joined parent so create new singleton pointing to it, a'
        a_ = SingletonPredictionContext.create(parent, a.returnState)
        mergeCache.put(a, b, a_) if mergeCache 
        return a_
    else # a != b payloads differ
        # see if we can collapse parents due to $+x parents if local ctx
        singleParent = nil
        if a.equal?(b) or (a.parentCtx and a.parentCtx==b.parentCtx) # ax + bx = [a,b]x
            singleParent = a.parentCtx
        end
        if not singleParent.nil? # parents are same
            # sort payloads and use same parent
            payloads = [ a.returnState, b.returnState ]
            if a.returnState > b.returnState then
                payloads[0] = b.returnState
                payloads[1] = a.returnState
            end
            parents = [singleParent, singleParent]
            a_ = ArrayPredictionContext.new(parents, payloads)
            mergeCache.put(a, b, a_) if mergeCache 
            return a_
        end
        # parents differ and can't merge them. Just pack together
        # into array; can't merge.
        # ax + by = [ax,by]
        payloads = [ a.returnState, b.returnState ]
        parents = [ a.parentCtx, b.parentCtx ]
        if a.returnState > b.returnState # sort by payload
            payloads[0] = b.returnState
            payloads[1] = a.returnState
            parents = [ b.parentCtx, a.parentCtx ]
        end
        a_ = ArrayPredictionContext.new(parents, payloads)
        mergeCache.put(a, b, a_) if mergeCache 
        return a_
    end
end

#PredictionContextFromRuleContext(atn, outerContext = nil) ⇒ `Object`

# File 'lib/antlr4/PredictionContext.rb', line 274

def PredictionContextFromRuleContext(atn, outerContext=nil)
    outerContext = RuleContext.EMPTY if outerContext.nil?

    # if we are in RuleContext of start rule, s, then PredictionContext
    # is EMPTY. Nobody called us. (if we are empty, return empty)
    if outerContext.parentCtx.nil? or RuleContext.EMPTY == outerContext 
        return PredictionContext.EMPTY
    end

    # If we have a parent, convert it to a PredictionContext graph
    parent = PredictionContextFromRuleContext(atn, outerContext.parentCtx)
    state = atn.states[outerContext.invokingState]
    transition = state.transitions[0]
    return SingletonPredictionContext.create(parent, transition.followState.stateNumber)
end

Module: PredictionContextFunctions::Methods

Instance Method Summary collapse

Instance Method Details

#calculateListsHashCode(parents, returnStates) ⇒ Object

#combineCommonParents(parents) ⇒ Object

#getAllContextNodes(context, nodes = nil, visited = nil) ⇒ Object

#getCachedPredictionContext(context, contextCache, visited) ⇒ Object

#merge(a, b, rootIsWildcard, mergeCache) ⇒ Object

#mergeArrays(a, b, rootIsWildcard, mergeCache) ⇒ Object

#mergeRoot(a, b, rootIsWildcard) ⇒ Object

#mergeSingletons(a, b, rootIsWildcard, mergeCache) ⇒ Object

#PredictionContextFromRuleContext(atn, outerContext = nil) ⇒ Object