content: /*
   *
   *
   *
   *                                   Apache License
   *                             Version 2.0, January 2004
   *                          http://www.apache.org/licenses/
   *
   *     TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
   *
   *     1. Definitions.
   *
   *        "License" shall mean the terms and conditions for use, reproduction,
   *        and distribution as defined by Sections 1 through 9 of this document.
   *
   *        "Licensor" shall mean the copyright owner or entity authorized by
   *        the copyright owner that is granting the License.
   *
   *        "Legal Entity" shall mean the union of the acting entity and all
   *        other entities that control, are controlled by, or are under common
   *        control with that entity. For the purposes of this definition,
   *        "control" means (i) the power, direct or indirect, to cause the
   *        direction or management of such entity, whether by contract or
   *        otherwise, or (ii) ownership of fifty percent (50%) or more of the
   *        outstanding shares, or (iii) beneficial ownership of such entity.
   *
   *        "You" (or "Your") shall mean an individual or Legal Entity
   *        exercising permissions granted by this License.
   *
   *        "Source" form shall mean the preferred form for making modifications,
   *        including but not limited to software source code, documentation
   *        source, and configuration files.
   *
   *        "Object" form shall mean any form resulting from mechanical
   *        transformation or translation of a Source form, including but
   *        not limited to compiled object code, generated documentation,
   *        and conversions to other media types.
   *
   *        "Work" shall mean the work of authorship, whether in Source or
   *        Object form, made available under the License, as indicated by a
   *        copyright notice that is included in or attached to the work
   *        (an example is provided in the Appendix below).
   *
   *        "Derivative Works" shall mean any work, whether in Source or Object
   *        form, that is based on (or derived from) the Work and for which the
   *        editorial revisions, annotations, elaborations, or other modifications
   *        represent, as a whole, an original work of authorship. For the purposes
   *        of this License, Derivative Works shall not include works that remain
   *        separable from, or merely link (or bind by name) to the interfaces of,
   *        the Work and Derivative Works thereof.
   *
   *        "Contribution" shall mean any work of authorship, including
   *        the original version of the Work and any modifications or additions
   *        to that Work or Derivative Works thereof, that is intentionally
   *        submitted to Licensor for inclusion in the Work by the copyright owner
   *        or by an individual or Legal Entity authorized to submit on behalf of
   *        the copyright owner. For the purposes of this definition, "submitted"
   *        means any form of electronic, verbal, or written communication sent
   *        to the Licensor or its representatives, including but not limited to
   *        communication on electronic mailing lists, source code control systems,
   *        and issue tracking systems that are managed by, or on behalf of, the
   *        Licensor for the purpose of discussing and improving the Work, but
   *        excluding communication that is conspicuously marked or otherwise
   *        designated in writing by the copyright owner as "Not a Contribution."
   *
   *        "Contributor" shall mean Licensor and any individual or Legal Entity
   *        on behalf of whom a Contribution has been received by Licensor and
   *        subsequently incorporated within the Work.
   *
   *     2. Grant of Copyright License. Subject to the terms and conditions of
   *        this License, each Contributor hereby grants to You a perpetual,
   *        worldwide, non-exclusive, no-charge, royalty-free, irrevocable
   *        copyright license to reproduce, prepare Derivative Works of,
   *        publicly display, publicly perform, sublicense, and distribute the
   *        Work and such Derivative Works in Source or Object form.
   *
   *     3. Grant of Patent License. Subject to the terms and conditions of
   *        this License, each Contributor hereby grants to You a perpetual,
   *        worldwide, non-exclusive, no-charge, royalty-free, irrevocable
   *        (except as stated in this section) patent license to make, have made,
   *        use, offer to sell, sell, import, and otherwise transfer the Work,
   *        where such license applies only to those patent claims licensable
   *        by such Contributor that are necessarily infringed by their
   *        Contribution(s) alone or by combination of their Contribution(s)
   *        with the Work to which such Contribution(s) was submitted. If You
   *        institute patent litigation against any entity (including a
   *        cross-claim or counterclaim in a lawsuit) alleging that the Work
   *        or a Contribution incorporated within the Work constitutes direct
   *        or contributory patent infringement, then any patent licenses
   *        granted to You under this License for that Work shall terminate
   *        as of the date such litigation is filed.
   *
   *     4. Redistribution. You may reproduce and distribute copies of the
   *        Work or Derivative Works thereof in any medium, with or without
   *        modifications, and in Source or Object form, provided that You
   *        meet the following conditions:
   *
   *        (a) You must give any other recipients of the Work or
   *            Derivative Works a copy of this License; and
   *
   *        (b) You must cause any modified files to carry prominent notices
   *            stating that You changed the files; and
   *
   *        (c) You must retain, in the Source form of any Derivative Works
   *            that You distribute, all copyright, patent, trademark, and
   *            attribution notices from the Source form of the Work,
   *            excluding those notices that do not pertain to any part of
   *            the Derivative Works; and
   *
   *        (d) If the Work includes a "NOTICE" text file as part of its
   *            distribution, then any Derivative Works that You distribute must
   *            include a readable copy of the attribution notices contained
   *            within such NOTICE file, excluding those notices that do not
   *            pertain to any part of the Derivative Works, in at least one
   *            of the following places: within a NOTICE text file distributed
   *            as part of the Derivative Works; within the Source form or
   *            documentation, if provided along with the Derivative Works; or,
   *            within a display generated by the Derivative Works, if and
   *            wherever such third-party notices normally appear. The contents
   *            of the NOTICE file are for informational purposes only and
   *            do not modify the License. You may add Your own attribution
   *            notices within Derivative Works that You distribute, alongside
   *            or as an addendum to the NOTICE text from the Work, provided
   *            that such additional attribution notices cannot be construed
   *            as modifying the License.
   *
   *        You may add Your own copyright statement to Your modifications and
   *        may provide additional or different license terms and conditions
   *        for use, reproduction, or distribution of Your modifications, or
   *        for any such Derivative Works as a whole, provided Your use,
   *        reproduction, and distribution of the Work otherwise complies with
   *        the conditions stated in this License.
   *
   *     5. Submission of Contributions. Unless You explicitly state otherwise,
   *        any Contribution intentionally submitted for inclusion in the Work
   *        by You to the Licensor shall be under the terms and conditions of
   *        this License, without any additional terms or conditions.
   *        Notwithstanding the above, nothing herein shall supersede or modify
   *        the terms of any separate license agreement you may have executed
   *        with Licensor regarding such Contributions.
   *
   *     6. Trademarks. This License does not grant permission to use the trade
   *        names, trademarks, service marks, or product names of the Licensor,
   *        except as required for reasonable and customary use in describing the
   *        origin of the Work and reproducing the content of the NOTICE file.
   *
   *     7. Disclaimer of Warranty. Unless required by applicable law or
   *        agreed to in writing, Licensor provides the Work (and each
   *        Contributor provides its Contributions) on an "AS IS" BASIS,
   *        WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
   *        implied, including, without limitation, any warranties or conditions
   *        of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
   *        PARTICULAR PURPOSE. You are solely responsible for determining the
   *        appropriateness of using or redistributing the Work and assume any
   *        risks associated with Your exercise of permissions under this License.
   *
   *     8. Limitation of Liability. In no event and under no legal theory,
   *        whether in tort (including negligence), contract, or otherwise,
   *        unless required by applicable law (such as deliberate and grossly
   *        negligent acts) or agreed to in writing, shall any Contributor be
   *        liable to You for damages, including any direct, indirect, special,
   *        incidental, or consequential damages of any character arising as a
   *        result of this License or out of the use or inability to use the
   *        Work (including but not limited to damages for loss of goodwill,
   *        work stoppage, computer failure or malfunction, or any and all
   *        other commercial damages or losses), even if such Contributor
   *        has been advised of the possibility of such damages.
   *
   *     9. Accepting Warranty or Additional Liability. While redistributing
   *        the Work or Derivative Works thereof, You may choose to offer,
   *        and charge a fee for, acceptance of support, warranty, indemnity,
   *        or other liability obligations and/or rights consistent with this
   *        License. However, in accepting such obligations, You may act only
   *        on Your own behalf and on Your sole responsibility, not on behalf
   *        of any other Contributor, and only if You agree to indemnify,
   *        defend, and hold each Contributor harmless for any liability
   *        incurred by, or claims asserted against, such Contributor by reason
   *        of your accepting any such warranty or additional liability.
   *
   *     END OF TERMS AND CONDITIONS
   *
   *     APPENDIX: How to apply the Apache License to your work.
   *
   *        To apply the Apache License to your work, attach the following
   *        boilerplate notice, with the fields enclosed by brackets "[]"
   *        replaced with your own identifying information. (Don't include
   *        the brackets!)  The text should be enclosed in the appropriate
   *        comment syntax for the file format. We also recommend that a
   *        file or class name and description of purpose be included on the
   *        same "printed page" as the copyright notice for easier
   *        identification within third-party archives.
   *
   *     Copyright 2016 Alibaba Group
   *
   *     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.
   *
   *
   */
  
  package com.taobao.android.builder.dependency.parser;
  
  import com.android.utils.ILogger;
  import com.google.common.collect.HashMultimap;
  import com.google.common.collect.Multimap;
  import org.apache.commons.lang.StringUtils;
  import org.gradle.api.artifacts.ModuleVersionIdentifier;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  
  /**
   * Loop dependent detection class
   * <p>
   *     The dependence is detected by simple notation
   * </p>
   * @author shenghua.nish on 2015-12-18 On the morning of the assembling.
   */
  public class CircleDependencyCheck {
  
      private final DependencyNode rootDependencyNode;
  
      public CircleDependencyCheck(ModuleVersionIdentifier identifier){
          String name = getIdentifier(identifier);
          rootDependencyNode = new DependencyNode(name, 0);
          rootDependencyNode.parent = null;
      }
  
      /**
       * Gain roots
       * @return
       */
      public DependencyNode getRootDependencyNode() {
          return rootDependencyNode;
      }
  
      /**
       * Join the rely on
       * @param identifier
       * @param parent
       * @param ident
       * @return Determine if there is a circular dependency, and if any, return true
       */
      public DependencyNode addDependency(ModuleVersionIdentifier identifier, DependencyNode parent, int ident) {
          String name = getIdentifier(identifier);
          DependencyNode node = new DependencyNode(name, ident);
          node.parent = parent;
          if (null != parent) {
              parent.children.add(node);
          }
          return node;
      }
  
      /**
       * dependent
       * @param identifier
       * @return
       */
      private String getIdentifier(ModuleVersionIdentifier identifier) {
          StringBuilder sb = new StringBuilder();
          sb.append(identifier.getGroup()).append(":");
          sb.append(identifier.getName()).append(":");
          sb.append(identifier.getVersion());
          return sb.toString();
      }
  
      static final String ARROW = "=>";
  
      /**
       * Determine whether there are circular dependencies
       * @return
       */
      public CircleResult checkCircle(ILogger logger) {
          CircleResult circleResult = new CircleResult();
          circleResult.hasCircle = false;
          Multimap<String, String> dependenciesMap = HashMultimap.create();
          Map<String, String> identifierMap = new HashMap<String, String>();
          // First, all the node tags
          createIdentifier(rootDependencyNode);
          fillDepenciesMap(logger, rootDependencyNode, dependenciesMap, identifierMap, 0);
          // dumpDependencyMap(logger, dependenciesMap);
  
          // Query dependency
          for (String key : dependenciesMap.keySet()) {
              // if(null != logger) logger.verbose("****** CHECK CIRCLE: " + key);
              Collection<String> dependencyLevels = dependenciesMap.get(key);
              Set<CircleDep> circleSet = circleLevels(dependencyLevels);
  
              /*if(null != logger) {
                  logger.verbose("DEPENDENCY_LVLS:");
                  for (String dl : dependencyLevels) {
                      logger.verbose(dl);
                  }
              }*/
  
              if (circleSet.size() > 0) { // There is a cycle of dependency
                  circleResult.hasCircle = true;
                  // if(null != logger) logger.verbose("[WARN] HAS CIRCLE");
                  for (CircleDep circleDep : circleSet) {
                      // if(null != logger) logger.verbose(" CIRCLE_DEP: " + circleDep.level1 + ", " + circleDep.level2);
                      StringBuilder sb = new StringBuilder();
                      sb.append(key);
                      String parentLevel = circleDep.level1.substring(0, circleDep.level1.length() - 1);
                      while (StringUtils.isNotBlank(parentLevel)) {
                          // logger.warning(" PARENT_LVL: " + parentLevel);
                          String parentDepStr = identifierMap.get(parentLevel);
                          // logger.warning(" PARENT_DEP: " + parentDepStr);
                          sb.append(ARROW).append(parentDepStr);
                          parentLevel = parentLevel.substring(0, parentLevel.length() - 1);
                      }
                      circleResult.detail.add(sb.toString());
                  }
  
              } else {
                  // if(null != logger) logger.verbose("[OK] NO_CIRCLE");
              }
          }
          return circleResult;
      }
  
      private Set<CircleDep> circleLevels(Collection<String> dependencyLevels) {
          Set<CircleDep> list = new HashSet<CircleDep>();
          for (String dependencyLevel : dependencyLevels) {
              for (String level : dependencyLevels) {
                  if (!dependencyLevel.equals(level) && dependencyLevel.startsWith(level)) {
                      CircleDep circleDep = new CircleDep(dependencyLevel, level);
                      list.add(circleDep);
                  }
              }
          }
          return list;
      }
  
      class CircleDep {
  
          String level1; // Depending on the hierarchy
          String level2; // Depending on the hierarchy
  
          public CircleDep(String level1, String level2){
              this.level1 = level1;
              this.level2 = level2;
          }
  
          @Override
          public boolean equals(Object o) {
              if (this == o) {
                  return true;
              }
              if (o == null || getClass() != o.getClass()) {
                  return false;
              }
  
              CircleDep circleDep = (CircleDep) o;
  
              if (level1 != null ? !level1.equals(circleDep.level1) : circleDep.level1 != null) {
                  return false;
              }
              return !(level2 != null ? !level2.equals(circleDep.level2) : circleDep.level2 != null);
  
          }
  
          @Override
          public int hashCode() {
              int result = level1 != null ? level1.hashCode() : 0;
              result = 31 * result + (level2 != null ? level2.hashCode() : 0);
              return result;
          }
      }
  
      /**
       * Fill a dependent tree
       * @param logger
       * @param node
       * @param dependenciesMap
       * @param identifierMap
       * @param indent
       */
      private void fillDepenciesMap(ILogger logger, DependencyNode node, Multimap<String, String> dependenciesMap,
                                    Map<String, String> identifierMap, int indent) {
          StringBuilder sb = new StringBuilder();
          for (int i = 0; i < indent; i++) {
              sb.append(" ");
          }
          sb.append(node.name);
          if (null != logger) {
              logger.verbose(sb.toString());
          }
  
          dependenciesMap.put(node.name, node.identifier);
          identifierMap.put(node.identifier, node.name);
          for (DependencyNode child : node.children) {
              fillDepenciesMap(logger, child, dependenciesMap, identifierMap, indent + 1);
          }
      }
  
      /**
       * Generate all dependent flags
       */
      private void createIdentifier(DependencyNode node) {
          if (null == node.parent) {
              node.identifier = "1";
          }
          List<DependencyNode> children = node.children;
          for (int i = 1; i <= children.size(); i++) {
              DependencyNode child = children.get(i - 1);
              if (i >= 10) {
                  // if adding divider between each num, consider 1-1-10 and 1-1-1, which will
                  // be treated as circle-dependency mistakenly.
                  child.identifier = String.format("%s(%s)", node.identifier, i);
              } else {
                  child.identifier = node.identifier + i;
              }
              createIdentifier(child);
          }
      }
  
      /**
       * The results of circular detection
       */
      public static class CircleResult {
  
          public boolean      hasCircle;
          public List<String> detail = new ArrayList<String>();
      }
  
      /**
       * Depend on the node
       */
      public static class DependencyNode {
  
          public String               name;
          public int                  indent;
          public DependencyNode       parent;
          public String               identifier;
          public List<DependencyNode> children = new ArrayList<DependencyNode>();
  
          public DependencyNode(String name, int indent){
              this.name = name;
              this.indent = indent;
          }
  
          @Override
          public boolean equals(Object o) {
              if (this == o) {
                  return true;
              }
              if (o == null || getClass() != o.getClass()) {
                  return false;
              }
  
              DependencyNode that = (DependencyNode) o;
  
              if (indent != that.indent) {
                  return false;
              }
              return !(name != null ? !name.equals(that.name) : that.name != null);
  
          }
  
          @Override
          public int hashCode() {
              int result = name != null ? name.hashCode() : 0;
              result = 31 * result + indent;
              return result;
          }
      }
  }
  