<commit_before>/* Soot - a J*va Optimization Framework
 * Copyright (C) 2002 <NAME>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

package soot;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

import soot.jimple.SpecialInvokeExpr;
import soot.util.ConcurrentHashMultiMap;
import soot.util.MultiMap;


/** Represents the class hierarchy.  It is closely linked to a Scene,
 * and must be recreated if the Scene changes. 
 *
 * This version supercedes the old soot.Hierarchy class.
 *
 * @author <NAME>
 */
public class FastHierarchy
{    
    /** This map holds all key,value pairs such that 
     * value.getSuperclass() == key. This is one of the three maps that hold
     * the inverse of the relationships given by the getSuperclass and
     * getInterfaces methods of SootClass. */
    protected MultiMap<SootClass,SootClass> classToSubclasses =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map holds all key,value pairs such that value is an interface 
     * and key is in value.getInterfaces(). This is one of the three maps 
     * that hold the inverse of the relationships given by the getSuperclass 
     * and getInterfaces methods of SootClass. */
    protected MultiMap<SootClass,SootClass> interfaceToSubinterfaces =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map holds all key,value pairs such that value is a class 
     * (NOT an interface) and key is in value.getInterfaces(). This is one of 
     * the three maps that hold the inverse of the relationships given by the 
     * getSuperclass and getInterfaces methods of SootClass. */
    protected MultiMap<SootClass,SootClass> interfaceToImplementers =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map is a transitive closure of interfaceToSubinterfaces,
     * and each set contains its superinterface itself. */
    protected MultiMap<SootClass,SootClass> interfaceToAllSubinterfaces =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map gives, for an interface, all concrete classes that
     * implement that interface and all its subinterfaces, but
     * NOT their subclasses. */
    protected MultiMap<SootClass,SootClass> interfaceToAllImplementers =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** For each class (NOT interface), this map contains a Interval, which is
     * a pair of numbers giving a preorder and postorder ordering of classes
     * in the inheritance tree. */
    protected Map<SootClass, Interval> classToInterval = new HashMap<SootClass, Interval>();

    protected Scene sc;

    protected class Interval {
        int lower;
        int upper;
        boolean isSubrange( Interval potentialSubrange ) {
        	if (potentialSubrange == null) return false;
            if( lower > potentialSubrange.lower ) return false;
            if( upper < potentialSubrange.upper ) return false;
            return true;
        }
    }
    protected int dfsVisit( int start, SootClass c ) {
        Interval r = new Interval();
        r.lower = start++;
        Collection<SootClass> col = classToSubclasses.get(c);
        if( col != null ) {
            for (SootClass sc : col) {
                // For some awful reason, Soot thinks interface are subclasses
                // of java.lang.Object
                if( sc.isInterface() ) continue;
                start = dfsVisit( start, sc );
            }
        }
        r.upper = start++;
        if( c.isInterface() ) {
            throw new RuntimeException( "Attempt to dfs visit interface "+c );
        }
        if(!classToInterval.containsKey(c))
        	classToInterval.put( c, r );
        return start;
    }

    /** Constructs a hierarchy from the current scene. */
    public FastHierarchy()
    {
        this.sc = Scene.v();

        /* First build the inverse maps. */
        for(  final SootClass cl : sc.getClasses() ) {
            if( cl.resolvingLevel() < SootClass.HIERARCHY ) continue;
            if( !cl.isInterface() && cl.hasSuperclass() ) {
            	classToSubclasses.put(cl.getSuperclass(), cl);
            }
            for( final SootClass supercl : cl.getInterfaces() ) {
                if( cl.isInterface() ) {
                    interfaceToSubinterfaces.put( supercl, cl );
                } else {
                    interfaceToImplementers.put( supercl, cl );
                }
            }
        }

        /* Now do a dfs traversal to get the Interval numbers. */
        dfsVisit( 0, Scene.v().getSootClass( "java.lang.Object" ) );
        /* also have to traverse for all phantom classes because they also
         * can be roots of the type hierarchy
         */
        for(SootClass phantomClass: Scene.v().getPhantomClasses()) {
        	if(!phantomClass.isInterface())
        		dfsVisit( 0, phantomClass );
        }
    }

    /** Return true if class child is a subclass of class parent, neither of
     * them being allowed to be interfaces. */
    public boolean isSubclass( SootClass child, SootClass parent ) {
        child.checkLevel(SootClass.HIERARCHY);
        parent.checkLevel(SootClass.HIERARCHY);
        Interval parentInterval = classToInterval.get( parent );
        Interval childInterval = classToInterval.get( child );
        return parentInterval.isSubrange( childInterval );
    }

    /** For an interface parent (MUST be an interface), returns set of all
     * implementers of it but NOT their subclasses. */
    public Set<SootClass> getAllImplementersOfInterface( SootClass parent ) {
        parent.checkLevel(SootClass.HIERARCHY);
        if( !interfaceToAllImplementers.containsKey( parent ) ) {
            for(SootClass subinterface : getAllSubinterfaces( parent )) {
                if( subinterface == parent ) continue;
                interfaceToAllImplementers.putAll(parent,
                    getAllImplementersOfInterface( subinterface ) );
            }
            interfaceToAllImplementers.putAll(parent, 
                    interfaceToImplementers.get( parent ) );
        }
        return interfaceToAllImplementers.get( parent );<commit_msg>used snapshot iterators for constructing the FastHierarchy to allow concurrent modifications<commit_after>/* Soot - a J*va Optimization Framework
 * Copyright (C) 2002 <NAME>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

package soot;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

import soot.jimple.SpecialInvokeExpr;
import soot.util.ConcurrentHashMultiMap;
import soot.util.MultiMap;


/** Represents the class hierarchy.  It is closely linked to a Scene,
 * and must be recreated if the Scene changes. 
 *
 * This version supercedes the old soot.Hierarchy class.
 *
 * @author <NAME>
 */
public class FastHierarchy
{    
    /** This map holds all key,value pairs such that 
     * value.getSuperclass() == key. This is one of the three maps that hold
     * the inverse of the relationships given by the getSuperclass and
     * getInterfaces methods of SootClass. */
    protected MultiMap<SootClass,SootClass> classToSubclasses =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map holds all key,value pairs such that value is an interface 
     * and key is in value.getInterfaces(). This is one of the three maps 
     * that hold the inverse of the relationships given by the getSuperclass 
     * and getInterfaces methods of SootClass. */
    protected MultiMap<SootClass,SootClass> interfaceToSubinterfaces =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map holds all key,value pairs such that value is a class 
     * (NOT an interface) and key is in value.getInterfaces(). This is one of 
     * the three maps that hold the inverse of the relationships given by the 
     * getSuperclass and getInterfaces methods of SootClass. */
    protected MultiMap<SootClass,SootClass> interfaceToImplementers =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map is a transitive closure of interfaceToSubinterfaces,
     * and each set contains its superinterface itself. */
    protected MultiMap<SootClass,SootClass> interfaceToAllSubinterfaces =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** This map gives, for an interface, all concrete classes that
     * implement that interface and all its subinterfaces, but
     * NOT their subclasses. */
    protected MultiMap<SootClass,SootClass> interfaceToAllImplementers =
    		new ConcurrentHashMultiMap<SootClass,SootClass>();

    /** For each class (NOT interface), this map contains a Interval, which is
     * a pair of numbers giving a preorder and postorder ordering of classes
     * in the inheritance tree. */
    protected Map<SootClass, Interval> classToInterval = new HashMap<SootClass, Interval>();

    protected Scene sc;

    protected class Interval {
        int lower;
        int upper;
        boolean isSubrange( Interval potentialSubrange ) {
        	if (potentialSubrange == null) return false;
            if( lower > potentialSubrange.lower ) return false;
            if( upper < potentialSubrange.upper ) return false;
            return true;
        }
    }
    protected int dfsVisit( int start, SootClass c ) {
        Interval r = new Interval();
        r.lower = start++;
        Collection<SootClass> col = classToSubclasses.get(c);
        if( col != null ) {
            for (SootClass sc : col) {
                // For some awful reason, Soot thinks interface are subclasses
                // of java.lang.Object
                if( sc.isInterface() ) continue;
                start = dfsVisit( start, sc );
            }
        }
        r.upper = start++;
        if( c.isInterface() ) {
            throw new RuntimeException( "Attempt to dfs visit interface "+c );
        }
        if(!classToInterval.containsKey(c))
        	classToInterval.put( c, r );
        return start;
    }

    /** Constructs a hierarchy from the current scene. */
    public FastHierarchy()
    {
        this.sc = Scene.v();

        /* First build the inverse maps. */
        for (final Iterator<SootClass> clIt = sc.getClasses().snapshotIterator(); clIt.hasNext(); ) {
        	SootClass cl = clIt.next();
            if( cl.resolvingLevel() < SootClass.HIERARCHY ) continue;
            if( !cl.isInterface() && cl.hasSuperclass() ) {
            	classToSubclasses.put(cl.getSuperclass(), cl);
            }
            for( final SootClass supercl : cl.getInterfaces() ) {
                if( cl.isInterface() ) {
                    interfaceToSubinterfaces.put( supercl, cl );
                } else {
                    interfaceToImplementers.put( supercl, cl );
                }
            }
        }

        /* Now do a dfs traversal to get the Interval numbers. */
        dfsVisit( 0, Scene.v().getSootClass( "java.lang.Object" ) );
        /* also have to traverse for all phantom classes because they also
         * can be roots of the type hierarchy
         */
        for (final Iterator<SootClass> phantomClassIt = Scene.v().getPhantomClasses().snapshotIterator();
        		phantomClassIt.hasNext(); ) {
        	SootClass phantomClass = phantomClassIt.next();
        	if(!phantomClass.isInterface())
        		dfsVisit( 0, phantomClass );
        }
    }

    /** Return true if class child is a subclass of class parent, neither of
     * them being allowed to be interfaces. */
    public boolean isSubclass( SootClass child, SootClass parent ) {
        child.checkLevel(SootClass.HIERARCHY);
        parent.checkLevel(SootClass.HIERARCHY);
        Interval parentInterval = classToInterval.get( parent );
        Interval childInterval = classToInterval.get( child );
        return parentInterval.isSubrange( childInterval );
    }

    /** For an interface parent (MUST be an interface), returns set of all
     * implementers of it but NOT their subclasses. */
    public Set<SootClass> getAllImplementersOfInterface( SootClass parent ) {
        parent.checkLevel(SootClass.HIERARCHY);
        if( !interfaceToAllImplementers.containsKey( parent ) ) {
            for(SootClass subinterface : getAllSubinterfaces( parent )) {
                if( subinterface == parent ) continue;
                interfaceToAllImplementers.putAll(parent,
                    getAllImplementersOfInterface( subinterface ) );
            }
            interfaceToAllImplementers.putAll(parent, 
                    interfaceToImplementers.get( parent ) );
        }
        return interfaceToAllImplementers.get( parent );
{'fraction_non_alphanumeric': 0.08233564377231674, 'fraction_numerical': 0.00308058531120913, 'mean_word_length': 2.6475995914198163, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3192396', 'n_tokens_mistral': 3926, 'n_tokens_neox': 3768, 'n_words': 1322}