Skip to content

Ghidra is a software reverse engineering (SRE) framework

7.9 KB
Raw Blame
/* ###
 * IP: GHIDRA
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package functioncalls.graph.job;

import java.awt.geom.Point2D;
import java.util.*;
import java.util.stream.Collectors;

import org.apache.commons.collections4.IterableUtils;
import org.apache.commons.collections4.map.LazyMap;

import edu.uci.ics.jung.algorithms.layout.Layout;
import functioncalls.graph.*;
import ghidra.graph.viewer.GraphViewer;
import util.CollectionUtils;

/**
 * A container to house all newly added vertices (those being arranged) and the sources, or 
 * 'from' vertices, of the new vertices.
 *   
 * <P>This offers existing vertices and new vertices pre-sorted by position in the graph in
 * order to minimize edge crossings.  Specifically, the new vertices will be sorted 
 * by the level of the parent and then the x-value of the parent so that the
 * immediate parent level will be preferred, with the x-value dictating where to place 
 * the child so that we can minimize edge crossings.
 */
public class FcgExpandingVertexCollection {

	private Comparator<FcgVertex> sourceVertexComparator = this::compareVerticesByLayoutPosition;
	private Comparator<FcgVertex> addressComparator =
		(v1, v2) -> v1.getAddress().compareTo(v2.getAddress());

	private Map<FcgVertex, TreeSet<FcgVertex>> newVerticesBySource = LazyMap.lazyMap(
		new TreeMap<>(sourceVertexComparator), () -> new TreeSet<>(addressComparator));

	private GraphViewer<FcgVertex, FcgEdge> viewer;
	private FcgLevel parentLevel;
	private FcgLevel expandingLevel;
	private Set<FcgVertex> newVertices;
	private Set<FcgEdge> newEdges;
	private Set<FcgEdge> indirectEdges = Collections.emptySet();
	private boolean isIncoming;
	private Iterable<FcgVertex> sources;

	/**
	 * Constructor
	 * 
	 * @param sources all vertices that are the source of the expansion.  This will be either a
	 *        single vertex, clicked by the user, or all vertices of a source level being expanded
	 * @param parentLevel a.k.a, the source vertex level for the vertex that is the source of the 
	 * 		  new vertices
	 * @param expandingLevel the level of the new vertices
	 * @param newVertices the expanding vertices; those that are emanating from the parent
	 * @param newEdges the new edges being added as a result of adding the new vertices
	 * @param allParentLevelEdges all edges from all siblings of the parent vertex
	 * @param isIncoming true if the newly added vertices are callers of the source vertex; 
	 * 		  false if the newly added vertices are called by the source vertex
	 * @param viewer the viewer that is painting the graph.  This is needed to sort by layout
	 *        position
	 */
	public FcgExpandingVertexCollection(Iterable<FcgVertex> sources, FcgLevel parentLevel,
			FcgLevel expandingLevel, Set<FcgVertex> newVertices, Set<FcgEdge> newEdges,
			Set<FcgEdge> allParentLevelEdges, boolean isIncoming,
			GraphViewer<FcgVertex, FcgEdge> viewer) {

		this.sources = sources;
		this.parentLevel = parentLevel;
		this.newVertices = newVertices;
		this.newEdges = newEdges;
		this.isIncoming = isIncoming;
		this.viewer = viewer;
		this.expandingLevel = expandingLevel;

		// we need to use the parent edges to generate the siblings of the newly
		// added vertices, as well as to sort the new vertices amongst their siblings		
		for (FcgEdge e : allParentLevelEdges) {

			FcgVertex start = e.getStart();
			FcgVertex end = e.getEnd();
			FcgLevel startLevel = start.getLevel();
			FcgLevel endLevel = end.getLevel();

			if (expandingLevel.equals(startLevel)) {
				if (expandingLevel.equals(endLevel)) {
					// self-loop
					newVerticesBySource.get(start).add(end);
					newVerticesBySource.get(end).add(start);
				}
				else {
					newVerticesBySource.get(end).add(start);
				}
			}
			else {
				newVerticesBySource.get(start).add(end);
			}
		}
	}

	private int compareVerticesByLayoutPosition(FcgVertex v1, FcgVertex v2) {

		Layout<FcgVertex, FcgEdge> layout = viewer.getGraphLayout();

		FcgLevel l1 = v1.getLevel();
		FcgLevel l2 = v2.getLevel();
		int result = l1.compareTo(l2);
		if (result != 0) {

			//  prefer the parent level over all
			if (l1.equals(parentLevel)) {
				return -1;
			}
			else if (l2.equals(parentLevel)) {
				return 1;
			}

			return result;
		}

		Point2D p1 = layout.apply(v1);
		Point2D p2 = layout.apply(v2);
		return (int) (p1.getX() - p2.getX());
	}

	/**
	 * Returns all vertices at the given level
	 * 
	 * @param level the level to filter on
	 * @return the vertices
	 */
	public List<FcgVertex> getVerticesByLevel(FcgLevel level) {

		// note: these are sorted, since they are housed in a TreeMap
		Set<FcgVertex> existingVertices = newVerticesBySource.keySet();

		//@formatter:off		
		List<FcgVertex> verticesAtLevel = existingVertices
			.stream()
			.filter(v -> v.getLevel().equals(level))
			.collect(Collectors.toList())
			;					
		//@formatter:on

		return verticesAtLevel;
	}

	/**
	 * Returns all vertices that have just been added to the graph; those now being arranged
	 * 
	 * @return all vertices that have just been added to the graph; those now being arranged 
	 */
	public List<FcgVertex> getAllVerticesAtNewLevel() {

		// note: these are sorted, since they are housed in a TreeMap
		Set<FcgVertex> existingVertices = newVerticesBySource.keySet();

		//@formatter:off		
		LinkedHashSet<FcgVertex> sortedVertices = existingVertices
			.stream()
			.map(v -> newVerticesBySource.get(v))
	        .flatMap(set -> set.stream())
	        .filter(v -> v.getLevel().equals(expandingLevel)) // only include vertices not in graph
	        .collect(Collectors.toCollection(LinkedHashSet::new)) // unique, sorted by traversal from above
			;
		//@formatter:on

		return new ArrayList<>(sortedVertices);
	}

	/**
	 * Returns all vertices being added to the graph
	 * @return the vertices
	 */
	public Set<FcgVertex> getNewVertices() {
		return newVertices;
	}

	/**
	 * Returns all new edges being added to the graph
	 * @return the edges
	 */
	public Iterable<FcgEdge> getNewEdges() {
		return IterableUtils.chainedIterable(newEdges, indirectEdges);
	}

	/**
	 * Returns all edges that are being added to existing nodes
	 * @return the edges
	 */
	public Set<FcgEdge> getIndirectEdges() {
		return indirectEdges;
	}

	/**
	 * Returns the number of newly added edges
	 * @return the number of newly added edges
	 */
	public int getNewEdgeCount() {
		return newEdges.size() + indirectEdges.size();
	}

	/**
	 * Sets indirect edges--those edges that are not a direct link between the source 
	 * vertices and the newly added vertices
	 * @param indirectEdges the edges
	 */
	public void setIndirectEdges(Set<FcgEdge> indirectEdges) {
		this.indirectEdges = CollectionUtils.asSet(indirectEdges);
	}

	/**
	 * Returns the level of the newly added vertices, which is the level that is being expanded
	 * @return the level
	 */
	public FcgLevel getExpandingLevel() {
		return expandingLevel;
	}

	/**
	 * Returns the direction of the expansion
	 * @return the direction of the expansion
	 */
	public FcgDirection getExpandingDirection() {
		return expandingLevel.getDirection();
	}

	/**
	 * All vertices that are the source of the expansion
	 * @return the source vertices
	 */
	public Iterable<FcgVertex> getSources() {
		return sources;
	}

	/**
	 * Returns true if the newly added vertices are callers of the source vertex; false if
	 * the newly added vertices are called by the source vertex
	 * 
	 * @return true if the new vertices are incoming calls
	 */
	public boolean isIncoming() {
		return isIncoming;
	}
}