bool IRList::structural_equals()

in libredex/IRList.cpp [639:752]

• 95 lines of code
• 40 McCabe index (conditional complexity)

bool IRList::structural_equals(
    const IRList& other, const InstructionEquality& instruction_equals) const {
  auto it1 = m_list.begin();
  auto it2 = other.begin();

  std::unordered_map<const MethodItemEntry*, const MethodItemEntry*> matches;
  std::unordered_map<const MethodItemEntry*, const MethodItemEntry*>
      delayed_matches;
  auto may_match = [&](const MethodItemEntry* mie1,
                       const MethodItemEntry* mie2) {
    always_assert(mie1 && mie1->type != MFLOW_DEBUG &&
                  mie1->type != MFLOW_POSITION &&
                  mie1->type != MFLOW_SOURCE_BLOCK);
    always_assert(mie2 && mie2->type != MFLOW_DEBUG &&
                  mie2->type != MFLOW_POSITION &&
                  mie2->type != MFLOW_SOURCE_BLOCK);
    auto it = matches.find(mie1);
    if (it != matches.end()) {
      return it->second == mie2;
    }
    auto p = delayed_matches.emplace(mie1, mie2);
    return p.second || p.first->second == mie2;
  };
  for (; it1 != m_list.end() && it2 != other.end();) {
    always_assert(it1->type != MFLOW_DEX_OPCODE);
    always_assert(it2->type != MFLOW_DEX_OPCODE);
    // Skip debug, position, and source block
    if (it1->type == MFLOW_DEBUG || it1->type == MFLOW_POSITION ||
        it1->type == MFLOW_SOURCE_BLOCK) {
      ++it1;
      continue;
    }

    if (it2->type == MFLOW_DEBUG || it2->type == MFLOW_POSITION ||
        it2->type == MFLOW_SOURCE_BLOCK) {
      ++it2;
      continue;
    }

    if (it1->type != it2->type) {
      return false;
    }

    auto it = delayed_matches.find(&*it1);
    if (it != delayed_matches.end()) {
      if (it->second != &*it2) {
        return false;
      }
      delayed_matches.erase(it);
    }
    matches.emplace(&*it1, &*it2);

    if (it1->type == MFLOW_OPCODE) {
      if (!instruction_equals(*it1->insn, *it2->insn)) {
        return false;
      }
    } else if (it1->type == MFLOW_TARGET) {
      auto target1 = it1->target;
      auto target2 = it2->target;

      if (target1->type != target2->type) {
        return false;
      }

      if (target1->type == BRANCH_MULTI &&
          target1->case_key != target2->case_key) {
        return false;
      }

      // Do these targets point back to the same branch instruction?
      if (!may_match(target1->src, target2->src)) {
        return false;
      }

    } else if (it1->type == MFLOW_TRY) {
      auto try1 = it1->tentry;
      auto try2 = it2->tentry;

      if (try1->type != try2->type) {
        return false;
      }

      // Do these `try`s correspond to the same catch block?
      if (!may_match(try1->catch_start, try2->catch_start)) {
        return false;
      }
    } else if (it1->type == MFLOW_CATCH) {
      auto catch1 = it1->centry;
      auto catch2 = it2->centry;

      if (catch1->catch_type != catch2->catch_type) {
        return false;
      }

      if ((catch1->next == nullptr && catch2->next != nullptr) ||
          (catch1->next != nullptr && catch2->next == nullptr)) {
        return false;
      }

      // Do these `catch`es have the same catch after them?
      if (catch1->next != nullptr && may_match(catch1->next, catch2->next)) {
        return false;
      }
    }
    ++it1;
    ++it2;
  }

  if (it1 == this->end() && it2 == other.end()) {
    always_assert(delayed_matches.empty());
    return true;
  }
  return false;
}