// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef SRC_DEVICES_BIN_DRIVER_MANAGER_BINDING_INTERNAL_H_
#define SRC_DEVICES_BIN_DRIVER_MANAGER_BINDING_INTERNAL_H_

#include <stdio.h>

#include <ddk/binding.h>
#include <ddk/device.h>
#include <ddk/driver.h>
#include <fbl/array.h>
#include <fbl/macros.h>

#include "composite_device.h"
#include "coordinator.h"
#include "device.h"

namespace internal {

struct BindProgramContext {
  const fbl::Array<const zx_device_prop_t>* props;
  uint32_t protocol_id;
  size_t binding_size;
  const zx_bind_inst_t* binding;
  const char* name;
  uint32_t autobind;
};

uint32_t LookupBindProperty(BindProgramContext* ctx, uint32_t id);
bool EvaluateBindProgram(BindProgramContext* ctx);

template <typename T>
bool EvaluateBindProgram(const fbl::RefPtr<T>& device, const char* drv_name,
                         const fbl::Array<const zx_bind_inst_t>& bind_program, bool autobind) {
  BindProgramContext ctx;
  ctx.props = &device->props();
  ctx.protocol_id = device->protocol_id();
  ctx.binding = bind_program.data();
  ctx.binding_size = bind_program.size() * sizeof(bind_program[0]);
  ctx.name = drv_name;
  ctx.autobind = autobind ? 1 : 0;
  return EvaluateBindProgram(&ctx);
}

// Represents the number of match chains found by a run of MatchParts()
enum class Match : uint8_t {
  None = 0,
  One,
  Many,
};

// Performs saturating arithmetic on Match values
Match SumMatchCounts(Match m1, Match m2);

// Internal bookkeeping for finding composite device fragment matches
class FragmentMatchState {
 public:
  FragmentMatchState() = default;
  FragmentMatchState(const FragmentMatchState&) = delete;
  FragmentMatchState& operator=(const FragmentMatchState&) = delete;

  FragmentMatchState(FragmentMatchState&&) = default;
  FragmentMatchState& operator=(FragmentMatchState&&) = default;

  // Create the bookkeeping state for the fragment matching algorithm.  This
  // preinitializes the state with Match::None,
  static zx_status_t Create(size_t fragments_count, size_t devices_count,
                            FragmentMatchState* out) {
    FragmentMatchState state;
    state.fragments_count_ = fragments_count;
    state.devices_count_ = devices_count;
    // If we wanted to reduce the memory usage here, we could avoid
    // bookkeeping for the perimeter of the array, in which all entries
    // except for the starting point are 0s.
    state.matches_ = std::make_unique<Match[]>(devices_count * fragments_count);
    *out = std::move(state);
    return ZX_OK;
  }

  Match get(size_t fragment, size_t ancestor) const {
    return matches_[devices_count_ * fragment + ancestor];
  }

  void set(size_t fragment, size_t ancestor, Match value) {
    matches_[devices_count_ * fragment + ancestor] = value;
  }

 private:
  std::unique_ptr<Match[]> matches_;
  size_t fragments_count_ = 0;
  size_t devices_count_ = 0;
};

// Return a list containing the device and all of its ancestors.  The 0th entry is the |device|
// itself, the 1st is its parent, etc.  Composite devices have no ancestors for the
// purpose of this function.
template <typename T>
void MakeDeviceList(const fbl::RefPtr<T>& device, fbl::Array<fbl::RefPtr<T>>* out) {
  size_t device_count = 0;
  fbl::RefPtr<T> dev = device;
  while (dev) {
    ++device_count;
    dev = dev->parent();
  }

  fbl::Array<fbl::RefPtr<T>> devices(new fbl::RefPtr<T>[device_count], device_count);
  size_t i = 0;
  for (dev = device; dev != nullptr; ++i, dev = dev->parent()) {
    devices[i] = dev;
  }
  ZX_DEBUG_ASSERT(i == device_count);
  *out = std::move(devices);
}

DECLARE_HAS_MEMBER_FN_WITH_SIGNATURE(has_props, props,
                                     const fbl::Array<const zx_device_prop_t>& (C::*)() const);
DECLARE_HAS_MEMBER_FN_WITH_SIGNATURE(has_topo_prop, topo_prop,
                                     const zx_device_prop_t* (C::*)() const);
DECLARE_HAS_MEMBER_FN_WITH_SIGNATURE(has_parent, parent, const fbl::RefPtr<T>& (C::*)());
DECLARE_HAS_MEMBER_FN_WITH_SIGNATURE(has_protocol_id, protocol_id, uint32_t (C::*)() const);

// Evaluates whether |device| and its ancestors match the sequence of binding
// programs described in |parts|.
//
// We consider a match to be found if the following hold:
// 1) For every part p_i, there is a device d that matches the bind program in
//    that part (we'll refer to this as a part/device pair (p_i, d)).
// 2) In (p_0, d), d must be the root device.
// 3) In (p_(N-1), d), d must be the leaf device.
// 4) If we have pairs (p_i, d) and (p_j, e), and i < j, then d is an ancestor
//    of e.  That is, the devices must match in the same sequence as the parts.
// 5) For every ancestor of the leaf device that has a BIND_TOPO_* property,
//    there exists a part that matches matches it.
// 6) There is a unique pairing that satisfies properties 1-5.
//
// The high-level idea of the rules above is that we want an unambiguous
// matching of the parts to the devices that is allowed to skip over ancestors
// that do not have topological properties.  We do not allow skipping over
// devices with topological properties, since the intent of this mechanism is to
// allow the description of devices that correspond to particular pieces of
// hardware.
//
// If all of these properties hold, MatchParts() returns Match::One.  If all of
// the properties except for property 6 hold, it returns Match::Many.
// Otherwise, it returns Match::None.
template <typename T>
Match MatchParts(const fbl::RefPtr<T>& device, const FragmentPartDescriptor* parts,
                 uint32_t parts_count) {
  static_assert(has_props<T>::value && has_topo_prop<T>::value && has_parent<T>::value &&
                has_protocol_id<T>::value);

  if (parts_count == 0) {
    return Match::None;
  }

  auto& first_part = parts[0];
  auto& last_part = parts[parts_count - 1];
  // The last part must match this device exactly
  bool match =
      EvaluateBindProgram(device, "composite_binder", last_part.match_program, true /* autobind */);
  if (!match) {
    return Match::None;
  }

  fbl::Array<fbl::RefPtr<T>> device_list;
  MakeDeviceList(device, &device_list);

  // If we have fewer device nodes than parts, we can't possibly match
  if (device_list.size() < parts_count) {
    return Match::None;
  }

  // Special-case for a single part: can only happen if one device
  if (parts_count == 1) {
    if (device_list.size() != 1) {
      return Match::None;
    }
    return Match::One;
  }

  // The first part must match the final ancestor
  match = EvaluateBindProgram(device_list[device_list.size() - 1], "composite_binder",
                              first_part.match_program, true /* autobind */);
  if (!match) {
    return Match::None;
  }

  // We now need to find if there exists a unique chain from parts[1] to
  // parts[parts_count - 2] such that each bind program has a match, and every
  // ancestor that has a BIND_TOPO property has a match.

  // If we have only two parts, we need to see if there are any unmatched
  // topological nodes.
  if (parts_count == 2) {
    // We've matched on the first and last device already, so check everything in-between
    for (size_t i = 1; i < device_list.size() - 1; ++i) {
      if (device_list[i]->topo_prop() != nullptr) {
        return Match::None;
      }
    }
    return Match::One;
  }

  ZX_DEBUG_ASSERT(device_list.size() >= 2 && parts_count >= 2);

  FragmentMatchState state;
  // For the matching state, we're focused on all of the devices between the
  // leaf device and the root device.
  zx_status_t status = FragmentMatchState::Create(parts_count, device_list.size(), &state);
  if (status != ZX_OK) {
    return Match::None;
  }
  // Record that we have a single match for the leaf.
  state.set(parts_count - 1, 0, Match::One);

  // We need to find a match for each intermediate part.  We'll move from the
  // closest to the leaf to the furthest.
  for (size_t part_idx = parts_count - 2; part_idx >= 1; --part_idx) {
    const FragmentPartDescriptor& part = parts[part_idx];

    // The number of matches we have so far is the sum of the number of
    // matches from the last iteration (i.e. of the chain of fragments from
    // part_idx+1 to to the end of the parts list) that did not make use of
    // this device or any of its ancestors.
    Match match_count = Match::None;

    // We iterate from the leaf device to the final ancestor.
    for (size_t device_idx = 1; device_idx < device_list.size() - 1; ++device_idx) {
      match_count = SumMatchCounts(match_count, state.get(part_idx + 1, device_idx - 1));

      // If there were no matches yet, this chain can't exist.
      if (match_count == Match::None) {
        continue;
      }

      match = EvaluateBindProgram(device_list[device_idx], "composite_binder", part.match_program,
                                  true /* autobind */);
      if (match) {
        // Propagate the current match_count.  Any chain that got here
        // is being extended by this latest match, so the number of
        // matching chains is unchanged.
        state.set(part_idx, device_idx, match_count);
      }

      // Move on to the next fragment, since we cannot cross a
      // topological property without matching against it.
      if (device_list[device_idx]->topo_prop() != nullptr) {
        break;
      }
    }
  }

  // Any chains we have found will be in the state with part_idx=1.  We need
  // to find how many of those chains have no devices with topological
  // properties between the last matching device in the chain and the root
  // device.
  Match match_count = Match::None;
  for (size_t i = device_list.size() - 2; i >= parts_count - 2; --i) {
    match_count = SumMatchCounts(match_count, state.get(1, i));
    if (device_list[i]->topo_prop() != nullptr) {
      break;
    }
  }
  return match_count;
}

}  // namespace internal

#endif  // SRC_DEVICES_BIN_DRIVER_MANAGER_BINDING_INTERNAL_H_