from functools import reduce

from .transitions import merge_transitions


class CFGSliceToSink:
    """
    The representation of a slice of a CFG.
    """
    def __init__(self, target, transitions=None):
        """
        :param angr.knowledge_plugins.functions.function.Function target:
            The targeted sink, to which every path in the slice leads.
        :param Dict[int,List[int]] transitions:
            A mapping representing transitions in the graph.
            Indexes are source addresses and values a list of destination addresses, for which there exists a transition
            in the slice from source to destination.
        """
        self._target = target
        self._transitions = transitions or {}

    @property
    def transitions(self):
        """
        :return Dict[int,List[int]]: The transitions in the slice.
        """
        return self._transitions

    @property
    def transitions_as_tuples(self):
        """
        :return List[Tuple[int,int]]: The list of transitions as pairs of (source, destination).
        """
        return reduce(
            lambda acc, source: acc + [ (source, destination) for destination in self._transitions[source] ],
            self._transitions.keys(),
            []
        )

    @property
    def target(self):
        """
        :return angr.knowledge_plugins.functions.function.Function:
            The targeted sink function, from which the slice is constructed.
        """
        return self._target

    @property
    def _origins(self):
        return set(self._transitions.keys())

    @property
    def _destinations(self):
        return set(reduce(
            lambda acc, destinations: acc + destinations,
            self._transitions.values(),
            []
        ))

    @property
    def nodes(self):
        """
        :return List[int]: The complete list of addresses present in the slice.
        """
        return list(self._origins | self._destinations)

    @property
    def entrypoints(self):
        """
        Entrypoints are all source addresses that are not the destination address of any transition.

        :return List[int]: The list of entrypoints addresses.
        """
        return sorted(list(self._origins - self._destinations))

    def add_transitions(self, transitions):
        """
        Add the given transitions to the current slice.

        :param Dict[int,List[int]] transitions:
            The list of transitions to be added to `self.transitions`.

        :return Dict[int,List[int]]: Return the updated list of transitions.
        """
        self._transitions = merge_transitions(transitions, self._transitions)
        return self._transitions

    def is_empty(self):
        """
        Test if a given slice does not contain any transition.

        :return bool: True if the <CFGSliceToSink> instance does not contain any transitions. False otherwise.
        """
        return not bool(self._transitions)

    def path_between(self, source, destination, visited=None):
        """
        Check the existence of a path in the slice between two given node adresses.

        :param int source: The source address.
        :param int destination: The destination address.
        :param List[int] visited: Used to avoid infinite recursion if loops are present in the slice.

        :return bool:
            True if there is a path between the source and the destination in the CFG, False if not,
            or if we have been unable to decide (because of loops).
        """
        _visited = visited or []

        if source not in self._transitions.keys() or source in _visited:
            return False
        _visited += [source]

        direct_successors = self._transitions[source]

        if destination in direct_successors:
            return True
        else:
            return any(list(map(
                lambda s: self.path_between(s, destination, _visited),
                direct_successors
            )))

@@ -1,12 +1,56 @@
+from typing import Optional, Set, Any, List%0A
 from functoo
@@ -1846,32 +1846,45 @@
  def nodes(self)
+ -%3E List%5Bint%5D
 :%0A        %22%22%22%0A  
@@ -1892,34 +1892,24 @@
      :return
- List%5Bint%5D
 : The comple
@@ -3044,24 +3044,29 @@
 self, source
+: int
 , destinatio
@@ -3066,16 +3066,21 @@
 tination
+: int
 , visite
@@ -3080,22 +3080,50 @@
  visited
-=None)
+: Optional%5BSet%5BAny%5D%5D=None) -%3E bool
 :%0A      
@@ -3228,20 +3228,16 @@
  :param 
-int 
 source: 
@@ -3275,12 +3275,8 @@
 ram 
-int 
 dest
@@ -3323,26 +3323,16 @@
   :param
- List%5Bint%5D
  visited
@@ -3417,21 +3417,16 @@
  :return
- bool
 :%0A      
@@ -3623,21 +3623,45 @@
 d = 
+set() if visited is None else 
 visited
- or %5B%5D
 %0A%0A  
@@ -3700,23 +3700,16 @@
 nsitions
-.keys()
  or sour
@@ -3769,20 +3769,20 @@
 ited
- += %5B
+.add(
 source
-%5D
+)
 %0A%0A  
@@ -3940,21 +3940,16 @@
 urn any(
-list(
 map(%0A   
@@ -4064,10 +4064,9 @@
       ))
-)
 %0A

Optimize CFGSliceToSink.path_between(). (#2534)