text: # 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.
  
  import queue
  import string
  import threading
  import time
  
  import keystoneauth1
  from keystoneauth1 import discover
  
  from openstack import _log
  from openstack import exceptions
  
  
  def urljoin(*args):
      """A custom version of urljoin that simply joins strings into a path.
  
      The real urljoin takes into account web semantics like when joining a url
      like /path this should be joined to http://host/path as it is an anchored
      link. We generally won't care about that in client.
      """
      return '/'.join(str(a or '').strip('/') for a in args)
  
  
  def iterate_timeout(timeout, message, wait=2):
      """Iterate and raise an exception on timeout.
  
      This is a generator that will continually yield and sleep for
      wait seconds, and if the timeout is reached, will raise an exception
      with <message>.
  
      """
      log = _log.setup_logging('openstack.iterate_timeout')
  
      try:
          # None as a wait winds up flowing well in the per-resource cache
          # flow. We could spread this logic around to all of the calling
          # points, but just having this treat None as "I don't have a value"
          # seems friendlier
          if wait is None:
              wait = 2
          elif wait == 0:
              # wait should be < timeout, unless timeout is None
              wait = 0.1 if timeout is None else min(0.1, timeout)
          wait = float(wait)
      except ValueError:
          raise exceptions.SDKException(
              "Wait value must be an int or float value. {wait} given"
              " instead".format(wait=wait))
  
      start = time.time()
      count = 0
      while (timeout is None) or (time.time() < start + timeout):
          count += 1
          yield count
          log.debug('Waiting %s seconds', wait)
          time.sleep(wait)
      raise exceptions.ResourceTimeout(message)
  
  
  def get_string_format_keys(fmt_string, old_style=True):
      """Gets a list of required keys from a format string
  
      Required mostly for parsing base_path urls for required keys, which
      use the old style string formatting.
      """
      if old_style:
          class AccessSaver:
              def __init__(self):
                  self.keys = []
  
              def __getitem__(self, key):
                  self.keys.append(key)
  
          a = AccessSaver()
          fmt_string % a
  
          return a.keys
      else:
          keys = []
          for t in string.Formatter().parse(fmt_string):
              if t[1] is not None:
                  keys.append(t[1])
          return keys
  
  
  def supports_microversion(adapter, microversion):
      """Determine if the given adapter supports the given microversion.
  
      Checks the min and max microversion asserted by the service and checks
      to make sure that ``min <= microversion <= max``.
  
      :param adapter:
          :class:`~keystoneauth1.adapter.Adapter` instance.
      :param str microversion:
          String containing the desired microversion.
      :returns: True if the service supports the microversion.
      :rtype: bool
      """
  
      endpoint_data = adapter.get_endpoint_data()
      if (endpoint_data.min_microversion
              and endpoint_data.max_microversion
              and discover.version_between(
                  endpoint_data.min_microversion,
                  endpoint_data.max_microversion,
                  microversion)):
          return True
      return False
  
  
  def pick_microversion(session, required):
      """Get a new microversion if it is higher than session's default.
  
      :param session: The session to use for making this request.
      :type session: :class:`~keystoneauth1.adapter.Adapter`
      :param required: Version that is required for an action.
      :type required: String or tuple or None.
      :return: ``required`` as a string if the ``session``'s default is too low,
          the ``session``'s default otherwise. Returns ``None`` of both
          are ``None``.
      :raises: TypeError if ``required`` is invalid.
      """
      if required is not None:
          required = discover.normalize_version_number(required)
  
      if session.default_microversion is not None:
          default = discover.normalize_version_number(
              session.default_microversion)
  
          if required is None:
              required = default
          else:
              required = (default if discover.version_match(required, default)
                          else required)
  
      if required is not None:
          return discover.version_to_string(required)
  
  
  def maximum_supported_microversion(adapter, client_maximum):
      """Determinte the maximum microversion supported by both client and server.
  
      :param adapter: :class:`~keystoneauth1.adapter.Adapter` instance.
      :param client_maximum: Maximum microversion supported by the client.
          If ``None``, ``None`` is returned.
  
      :returns: the maximum supported microversion as string or ``None``.
      """
      if client_maximum is None:
          return None
  
      # NOTE(dtantsur): if we cannot determine supported microversions, fall back
      # to the default one.
      try:
          endpoint_data = adapter.get_endpoint_data()
      except keystoneauth1.exceptions.discovery.DiscoveryFailure:
          endpoint_data = None
  
      if endpoint_data is None:
          log = _log.setup_logging('openstack')
          log.warning('Cannot determine endpoint data for service %s',
                      adapter.service_type or adapter.service_name)
          return None
  
      if not endpoint_data.max_microversion:
          return None
  
      client_max = discover.normalize_version_number(client_maximum)
      server_max = discover.normalize_version_number(
          endpoint_data.max_microversion)
  
      if endpoint_data.min_microversion:
          server_min = discover.normalize_version_number(
              endpoint_data.min_microversion)
          if client_max < server_min:
              # NOTE(dtantsur): we may want to raise in this case, but this keeps
              # the current behavior intact.
              return None
  
      result = min(client_max, server_max)
      return discover.version_to_string(result)
  
  
  class TinyDAG:
      """Tiny DAG
  
      Bases on the Kahn's algorithm, and enables parallel visiting of the nodes
      (parallel execution of the workflow items).
      """
  
      def __init__(self, data=None):
          self._reset()
          self._lock = threading.Lock()
          if data and isinstance(data, dict):
              self.from_dict(data)
  
      def _reset(self):
          self._graph = dict()
          self._wait_timeout = 120
  
      @property
      def graph(self):
          """Get graph as adjacency dict
          """
          return self._graph
  
      def add_node(self, node):
          self._graph.setdefault(node, set())
  
      def add_edge(self, u, v):
          self._graph[u].add(v)
  
      def from_dict(self, data):
          self._reset()
          for k, v in data.items():
              self.add_node(k)
              for dep in v:
                  self.add_edge(k, dep)
  
      def walk(self, timeout=None):
          """Start the walking from the beginning.
          """
          if timeout:
              self._wait_timeout = timeout
          return self
  
      def __iter__(self):
          self._start_traverse()
          return self
  
      def __next__(self):
          # Start waiting if it is expected to get something
          # (counting down from graph length to 0).
          if (self._it_cnt > 0):
              self._it_cnt -= 1
              try:
                  res = self._queue.get(
                      block=True,
                      timeout=self._wait_timeout)
                  return res
  
              except queue.Empty:
                  raise exceptions.SDKException('Timeout waiting for '
                                                'cleanup task to complete')
          else:
              raise StopIteration
  
      def node_done(self, node):
          """Mark node as "processed" and put following items into the queue"""
          self._done.add(node)
  
          for v in self._graph[node]:
              self._run_in_degree[v] -= 1
              if self._run_in_degree[v] == 0:
                  self._queue.put(v)
  
      def _start_traverse(self):
          """Initialize graph traversing"""
          self._run_in_degree = self._get_in_degree()
          self._queue = queue.Queue()
          self._done = set()
          self._it_cnt = len(self._graph)
  
          for k, v in self._run_in_degree.items():
              if v == 0:
                  self._queue.put(k)
  
      def _get_in_degree(self):
          """Calculate the in_degree (count incoming) for nodes"""
          _in_degree = dict()
          _in_degree = {u: 0 for u in self._graph.keys()}
          for u in self._graph:
              for v in self._graph[u]:
                  _in_degree[v] += 1
  
          return _in_degree
  
      def topological_sort(self):
          """Return the graph nodes in the topological order"""
          result = []
          for node in self:
              result.append(node)
              self.node_done(node)
  
          return result
  
      def size(self):
          return len(self._graph.keys())
  