# encoding: utf-8
# frozen_string_literal: true

require "tsort"
require "forwardable"

module Carbon
  module Concrete
    # A list of all of the "items" in the global context of Carbon.  Items are
    # mostly functions and data definitions.  This keeps track of them and
    # their dependencies, so that they can be built later.  Indexes are also
    # designed to be easily serialized if needed (which is likely the case,
    # for libraries).
    class Index
      include TSort
      extend Forwardable

      # We can't use these methods because we don't fit the bill - we don't
      # define a `tsort_each_node`, since we don't need it.  We only use
      # `each_strongly_connected_component_from`, which only requires
      # `tsort_each_child`.  We could use the module function
      # `TSort.each_strongly_connected_component_from`, but that only appears
      # in Ruby versions 2.1.0 and higher.  It's not guarenteed to be there.
      # However, everything else in TSort is expected to be there, even since
      # Ruby 1.8.7, and do exactly as expected.
      undef_method :tsort
      undef_method :each_strongly_connected_component
      undef_method :strongly_connected_components

      # Initialize the index with the given data.
      #
      # @api public
      # @param data [{::Symbol => ::Object}] The data to initialize with.
      # @option data [::Hash] :items ({}) The definitions.
      # @option data [::String] :id (#id) The ID of the index.  This is
      #   completely derived from the index itself; or, rather, what's defined
      #   on the index.  See {#id}.
      def initialize(data = {})
        @items = Concurrent::Hash.new.merge(data.fetch(:items, {}))
        @mutex = Mutex.new
        @id = data.fetch(:id) { id }
      end

      # @overload fetch(name, default = CANARY)
      #   Retrieves the item with the given symbol name.  If no item with the
      #   given name exists, it tries the following: first, if a block is
      #   given, the item name is yielded to the block, and the result is
      #   returned.  Second, if the second argument is passed (i.e. isn't
      #   `CANARY`), then that is returned instead.  Third, if neither is
      #   true, then the method raises `KeyError`.
      #
      #   @api public
      #   @example Successful fetch.
      #     index.fetch("Carbon::Integer") # => #<Carbon::Concrete::Item::Base>
      #   @example Failed fetch with argument.
      #     index.fetch("Carbon::Foo", false) # => false
      #   @example Failed fetch with block.
      #     index.fetch("Carbon::Foo") { |n| n.sub("F", "B") }
      #       # => "Carbon::Boo"
      #   @example Failed fetch with both.
      #     index.fetch("Carbon::Foo", false) { |n| n.sub("F", "B") }
      #       # => "Carbon::Boo"
      #   @param name [::Object] The key of the item to fetch.
      #   @param default [::Object] The value to return if the key doesn't match
      #     an item and a block wasn't given.
      #   @yield [name] If the key doesn't match an item, the method yields.
      #   @yieldparam name [::Object] The name of the item.
      #   @return [::Object] The item, if the key matched; otherwise, the result
      #     of the block, if given; otherwise, the value of the `default`
      #     parameter.
      #   @raise [KeyError] If the key doesn't match an item and neither a
      #     block nor the second argument were passed.
      def fetch(*options, &block)
        @mutex.synchronize { @items.fetch(*options, &block) }
      end

      # @overload [](key)
      #   Retrieves the item with the given symbol name.  If no item exists,
      #   it returns `nil`.
      #
      #   @api public
      #   @example Successful retrieval.
      #     index["Carbon::Integer"] # => #<Carbon::Concrete::Item::Base>
      #   @example Unsuccessful retrieval.
      #     index["Carbon::Foo"] # => nil
      #   @param key [::Object] The key of the item to lookup.
      #   @return [::Object] The item, if it exists;
      #   @return [nil] Otherwise.
      def [](*options)
        @mutex.synchronize { @items[*options] }
      end

      # @overload key?(key)
      #   Determines whether or not the key exists, and an item is paired
      #   with it.
      #
      #   @api public
      #   @example Existing key.
      #     index.key?("Carbon::Integer") # => true
      #   @example Non-existant key.
      #     index.key?("Carbon::Foo") # => false
      #   @param key [::Object] The key of the item to check.
      #   @return [::Boolean] Whether the key exists or not.
      def key?(*options)
        @mutex.synchronize { @items.key?(*options) }
      end

      # Returns all of the keys in the index.  The keys and the array itself
      # are both frozen.
      #
      # @api public
      # @example
      #   index.keys # => ["Carbon::Boolean", "Carbon::Integer"]
      # @return [<::String>] The keys in the index.
      def keys
        @mutex.synchronize { @items.keys.deep_freeze! }
      end

      # Returns all of the values (actual items) in the index.  The items, and
      # the array containing them, are frozen.
      #
      # @api public
      # @example
      #   index.values.map(&:class) # => [Carbon::Concrete::Item::Internal, ...]
      # @return [<Item::Base>] The values in the index.
      def values
        @mutex.synchornize { @items.values.freeze }
      end

      # The digest of the ID.  This uses the SHA256 base58 digest of the items
      # defined on the current index.  This includes both defined and merged
      # items.
      #
      # @api public
      # @example
      #   index.items # => {}
      #   index.id # => "gjNT5GbSC-81KmUPncw-hzQAGV3GU-eAXafmkMP-Bw2GMHWM"
      # @return [::String]
      def id
        @id ||= Carbon.hash(items.keys.join("\n"))
      end

      # The items of the index.  This is a frozen duplicate of the items.
      # Therefore, this is not guarenteed to be up to date.
      #
      # @api public
      # @example Items
      #   index.items
      #     # => {"Carbon::Integer" => #<Carbon::Concrete::Item::Base>}
      # @return [{::String => Item::Base}] The items of the index.
      def items
        @mutex.synchronize { @items.dup.deep_freeze! }
      end

      # Adds a defined item to the index.  The item just has to respond to
      # the item API (see {Concrete::Item}).  This clears the index's cache,
      # such that the ID ({#id}) and item list ({#items}) are reset and have
      # to be recalculated.
      #
      # @api public
      # @example Adding an item.
      #   index << item
      #   index.key?(item.intern) # => true
      # @example Merging an index.
      #   other.is_a?(Carbon::Concrete::Index) # => true
      #   index << other
      #   index.items.keys.to_set <= other.items.keys.to_set
      # @note
      #   If the item is an index instead, it passes it to {#merge} and
      #   returns.  This usage is not recommended for {#add}, but can be
      #   used for {#<<}.
      # @param item [Concrete::Item::Base] The item to add.
      # @return [self]
      def add(item)
        return merge(item) if item.is_a?(Index)
        @mutex.synchronize do
          @items[item.intern] = item
          clear!
        end
      end

      alias_method :<<, :add

      # Merges items from another index into the merged items of this index.
      # This clears the index's cache, such that the ID ({#id}) have to be
      # recalculated.
      #
      # @api public
      # @example Merging.
      #   index.merge(other)
      #   index.items.keys.to_set <= other.items.keys.to_set
      # @param index [Index] The index to merge.
      # @return [self]
      def merge(index)
        @mutex.synchronize do
          @items.merge(index.items)
          clear!
        end
      end

      # Used only for {#define}.  This maps item "names" to the classes that
      # represent them.
      #
      # @api private
      # @return [{::Symbol => Item::Base}]
      ITEMS = {
        internal: Concrete::Item::Internal,
        function: Concrete::Item::Function,
        struct: Concrete::Item::Struct,
        trait: Concrete::Item::Trait
      }.freeze

      # Defines a type.  This is mostly a shorthand method.  The purpose of
      # this is to make it easy to define items on the index.  The only
      # parameter, data, is a hash.  The key is the name of the type of the
      # item; this corresponds to the keys in the {ITEMS} hash.  The value is
      # the {Concrete::Type} that is being defined. The method then yields a
      # hash that is later used to define the item.
      #
      # @api semipublic
      # @example
      #   index.class # => Carbon::Concrete::Index
      #   index.define(internal: Carbon::Boolean) do |bool|
      #     bool[:size] = 1
      #     bool[:kind] = :integer
      #     bool[:implements] << Carbon::Type("Carbon::Numeric")
      #     bool[:implements] << Carbon::Type("Carbon::Boolean")
      #   end
      #   internal = index[Carbon::Boolean]
      #   internal.name # => "Carbon::Boolean"
      # @param data [{::Symbol => Concrete::Type}] The name and
      #   item type information.  There should only be one key
      #   pair; any more will cause an error.
      # @yield [data] To construct the data.  At the end of the block, the data
      #   should contain all the information needed to create the item.
      # @yieldparam data [{::Symbol => ::Object}] The data to be passed to the
      #   item's intializer.
      # @raise [ArgumentError] if more than one key-value pair is provided for
      #   the `data` argument.
      # @return [void]
      def define(data)
        fail ArgumentError, "Expected only one pair" if data.size > 1
        data.each do |itype, name|
          item = ITEMS.fetch(itype)
          opts = item.from(Carbon::Type(name))
          yield opts
          self << item.new(opts)
        end
      end

      # Yields the builds that need to be built for the given item.  This uses
      # the TSort module in order to determine all of the dependencies the
      # given item has, and yields each; and finally, yields the last item.
      # The item may not have any generics, even if they are fully formed
      # generics (e.g. have a definition).  If any items have a cyclic
      # depdendency, it fails.
      #
      # @api semipublic
      # @example Build request.
      #   request.intern # => "Main"
      #   request.generics # => []
      #   index.build(request).to_a # => [...]
      # @param item [Item::Base] The item to build.  The {Item::Base} module
      #   contains behavior that is required by this method (namely,
      #   {Item::Base#corrected_dependencies}, {Item::Base#intern}, and
      #   {Item::Base#generics}).
      # @return [::Enumerable] The build items, if no block is given.
      # @return [void] If a block is given.
      # @yield [dep] Multiple times, each with a dependency.
      # @yieldparam dep [Request] A request.
      def build(item)
        @mutex.lock
        fail ArgumentError, "Passed item cannot be generic" if \
          item.generics.any?
        return to_enum(:build, item) unless block_given?
        request = Request.new(item.intern, [])

        build_from_request(request, &Proc.new)
      ensure
        @mutex.unlock
      end

    private

      # rubocop:disable Metrics/MethodLength
      def build_from_request(request)
        components = to_enum(:each_strongly_connected_component_from, request)
        components.each do |group|
          fail TSort::Cyclic, "cyclic dependencies: #{group.join(', ')}" if \
            group.size > 1
          begin
            @mutex.unlock
            yield group.first
          ensure
            @mutex.lock
          end
        end
      end
      # rubocop:enable Metrics/MethodLength

      # Iterates over all of the "children" of a node.  This iterates over all
      # of the corrected dependencies of a node, allowing the TSort module
      # to build a dependency map.
      #
      # @api private
      # @param node [#intern] The item.
      # @yield [request] Yields each corrected dependency of the item.
      # @yieldparam request [Request]
      # @return [void]
      def tsort_each_child(node, &block)
        @items.fetch(node.intern).corrected_dependencies(node, &block)
      end

      # Clears the cache, forcing the id to be rebuilt on next call.
      #
      # @api private
      # @return [self]
      def clear!
        @id = nil
        self
      end
    end
  end
end