Dependency managers



    In this article, I will tell you what dependency managers (package manager) are similar in terms of internal structure, operation algorithm, and what are their fundamental differences. I’ve considered package managers designed for development under iOS / OS X, but the content of the article with some assumptions applies to others.

    Varieties of Addiction Managers


    • System dependency managers - install the missing utilities in the operating system. For example, Homebrew .
    • Managers of language dependencies - collect the source code written in one of the programming languages ​​into final executable programs. For example, go build .
    • Project dependency managers - manage dependencies in the context of a specific project. That is, their tasks include the description of dependencies, downloading, updating their source code. This, for example, Cocoapods .

    The main difference between them is who they "serve." The system MH is for users, the MH of the project is for the developers, and the MH of the language is both for those and for all at once.

    Next, I will consider the project dependency managers - we use them most often, and they are easier to understand.

    Project schema using dependency manager


    Consider the example of the popular package manager Cocoapods .
    Usually we run the conditional command pod install , and then the dependency manager does everything for us. Consider what the project should consist of in order for this command to complete successfully.



    1. There is our code in which we use a particular dependency, say, the Alamofire library .
    2. From the manifest file, the dependency manager knows which dependencies we use in the source code. If we forget to specify a library there, the dependency will not be established, and the project will not be collected as a result.
    3. Lock-file - a file of a specific format generated by the dependency manager, which lists all the dependencies successfully installed in the project.
    4. The dependency code is an external source code that “pulls up” the dependency manager and which will be called from our code.

    This would not be possible without a specific algorithm that runs every time after a dependency installation command.

    All 4 components are listed one after another because the subsequent component is formed on the basis of the previous one.



    Not all dependency managers have all 4 components, but taking into account the functions of the dependency manager, having all is the best option.

    After installing the dependencies, all 4 components go to the input to the compiler or interpreter, depending on the language.



    I also note that the developers are responsible for the first two components - we are writing this code, and for the remaining two - the dependency manager itself - it generates the file (s) and downloads the source code of the dependencies.



    Algorithm of dependency manager


    We have dealt with the component parts more or less; now we turn to the algorithmic part of the work of the Ministry of Health.

    A typical work algorithm looks like this:

    1. Validation of the project and environment. The object named Analyzer is responsible for this .
    2. Construction of the graph. From dependencies MOH should build a graph. This is what the Resolver object does .
    3. Downloading dependencies. Obviously, the source code of dependencies must be downloaded so that we use it in our source code.
    4. Integration of dependencies. The fact that the source code of dependencies lies in a neighboring directory on the disk may not be enough, so they still need to be attached to our project.
    5. Update dependencies. This step is not performed immediately after step 4, but if necessary, upgrade to a new version of the libraries. There are some peculiarities here, so I selected them in a separate step - about them further.

    Validation of the project and environment


    Validation includes verification of OS versions, auxiliary utilities that the dependency manager needs, as well as the lining of the project settings and the manifest file: from the syntax check to the incompatible settings.

    Typical podfile

    source 'https://github.com/CocoaPods/Specs.git'
    source 'https://github.com/RedMadRobot/cocoapods-specs'
    platform :ios, '10.0'
    use_frameworks!
    project 'Project.xcodeproj'
    workspace 'Project.xcworkspace'
    target 'Project'do
        project 'Project.xcodeproj'
        pod 'Alamofire'
        pod 'Fabric'
        pod 'GoogleMaps'end

    Possible warnings and errors when checking the podfile:

    • No dependency found in any of the spec repositories ;
    • Explicitly not specified operating system and version;
    • Invalid workspace or project name.

    Building a dependency graph


    Since the dependencies that are necessary for our project may have their own dependencies, and those in turn have their own nested dependencies or subdependencies, the manager used the correct versions. Schematically, all dependencies as a result should line up in a directed acyclic graph .



    The construction of a directed acyclic graph is reduced to the problem of topological sorting. She has several solution algorithms.

    1. Kahn's algorithm - iteration of vertices, complexity O (n).
    2. Tarjan's algorithm - based on a deep search, complexity O (n).
    3. Demucron's algorithm is a layered partitioning of a graph.
    4. Parallel algorithms using a polynomial number of processors. In this case, the complexity "falls" to O (log (n) ^ 2)

    The task itself is NP-complete, the same algorithm is used in compilers and machine learning.

    The result of the solution is a created lock-file that fully describes the relationship between dependencies.



    What problems may arise when running this algorithm? Consider an example: there is a project with dependencies A, B, E with nested dependencies C, F, D.



    Dependencies A and B have a common dependency C. And here C must meet the requirements of dependencies A and B. Some dependency manager allows for the installation of separate versions, if necessary, but cocoapods, for example, do not. Therefore, in case of incompatibility of requirements: A requires a version equal to 2.0 depending on C, and B requires version 1.0, the installation will complete with an error. And if A dependencies need version 1.0 and higher to version 2.0, and dependencies B version 1.2 or less to 1.0, the maximum compatible version for A and B version 1.2 will be installed. Do not forget that there may be a situation of cyclical dependence, even if not directly - in this case, the installation will also end with an error.



    Consider how it looks in the code of the most popular dependency managers for iOS.

    Carthage


    typealiasDependencyGraph = [Dependency: Set<Dependency>]
    publicenumDependency{
        /// A repository hosted on GitHub.com or GitHub Enterprise.case gitHub(Server, Repository)
        /// An arbitrary Git repository.case git(GitURL)
        /// A binary-only frameworkcase binary(URL)
    }
    /// Protocol for resolving acyclic dependency graphs.publicprotocolResolverProtocol{
        init(
            versionsForDependency: @escaping (Dependency) -> SignalProducer<PinnedVersion, CarthageError>,
            dependenciesForDependency: @escaping (Dependency, PinnedVersion) -> SignalProducer<(Dependency, VersionSpecifier), CarthageError>,
            resolvedGitReference: @escaping (Dependency, String) -> SignalProducer<PinnedVersion, CarthageError>
        )
        funcresolve(
            dependencies: [Dependency: VersionSpecifier],
            lastResolved: [Dependency: PinnedVersion]?,
            dependenciesToUpdate: [String]?
        ) -> SignalProducer<[Dependency: PinnedVersion], CarthageError>
    }
    

    The implementation of Resolver is here , and NewResolver is here , the Analyzer itself is not.

    Cocoapods


    The implementation of the graph construction algorithm is allocated to a separate repository . Here is the implementation of the graph and Resolver . In Analyzer, you can find that the correspondence of the cocoapods versions of the system and the lock file is checked.

    defvalidate_lockfile_version!if lockfile && lockfile.cocoapods_version > Version.new(VERSION)
         STDERR.puts '[!] The version of CocoaPods used to generate ' \
          "the lockfile (#{lockfile.cocoapods_version}) is "\
          "higher than the version of the current executable (#{VERSION}). " \
          'Incompatibility issues may arise.'.yellow
        endend

    From the source you can also see that the Analyzer generates targeting for dependencies.

    A typical cocoapods lock file looks like this:

    PODS:
      - Alamofire (4.7.0)
      - Fabric (1.7.5)
      - GoogleMaps (2.6.0):
        - GoogleMaps/Maps (= 2.6.0)
      - GoogleMaps/Base (2.6.0)
      - GoogleMaps/Maps (2.6.0):
        - GoogleMaps/Base
    SPEC CHECKSUMS:Alamofire:907e0a98eb68cdb7f9d1f541a563d6ac5dc77b25
      Fabric: ae7146a5f505ea370a1e44820b4b1dc8890e2890GoogleMaps:42f91c68b7fa2f84d5c86597b18ceb99f5414c7f
    PODFILE CHECKSUM:5294972c5dd60a892bfcc35329cae74e46aac47b
    COCOAPODS:1.4.0

    The PODS section lists direct and nested dependencies with an indication of the versions, then their checksums are calculated separately and the version of cocoapods that was used for the installation is indicated.

    Downloading dependencies


    After successfully building the graph and creating the lock-file, the dependency manager proceeds to download them. Optionally, these will be source codes, these can also be executable files or compiled frameworks. Also, all dependency managers usually support the ability to install on a local path.



    There is nothing difficult to download via the link (which, of course, needs to be taken from somewhere), so I will not tell how the download itself happens, but will focus on the issues of centralization and security.

    Centralization


    In simple terms, the dependency manager has two ways when downloading dependencies:

    1. Go to some list of available dependencies and get a link to download by name.
    2. We must explicitly indicate the source for each dependency in the manifest file.

    On the first path are centralized dependency managers, on the second - decentralized.



    Security


    If you download dependencies via https or ssh, you can sleep well. However, developers often provide http links to their official libraries. And here we can face the man-in-the-middle attack when an attacker replaces the source code, the executable file, or the framework. Some dependency managers are not protected from this, and some do it as follows.

    Homebrew

    Check curl in outdated OS X versions.

    defcheck_for_bad_curlreturnunless MacOS.version <= "10.8"returnif Formula["curl"].installed?
        <<~EOS
          The system curl on 10.8and below is often incapable of supporting
          modern secure connections & will fail on fetching formulae.
          We recommend you:
              brew install curl
        EOS
    end

    There is also a SHA256 hash check when downloading via http.

    defcurl_http_content_headers_and_checksum(url, hash_needed:false, user_agent::default)
      max_time = hash_needed ? "600" : "25"
      output, = curl_output(
        "--connect-timeout", "15", "--include", "--max-time", max_time, "--location", url,
        user_agent: user_agent
      )
      status_code = :unknownwhile status_code == :unknown|| status_code.to_s.start_with?("3")
        headers, _, output = output.partition("\r\n\r\n")
        status_code = headers[%r{HTTP\/.* (\d+)}, 1]
      end
      output_hash = Digest::SHA256.digest(output) if hash_needed
      {
        status: status_code,
        etag: headers[%r{ETag: ([wW]\/)?"(([^"]|\\")*)"}, 2],
        content_length: headers[/Content-Length: (\d+)/, 1],
        file_hash: output_hash,
        file: output,
      }
    end

    And you can also disable unsafe redirects to http (variable HOMEBREW_NO_INSECURE_REDIRECT ).

    Carthage and Cocoapods

    Here, everything is simpler - you can not use http on executable files.

    guard binaryURL.scheme == "file" || binaryURL.scheme == "https"else { return .failure(BinaryJSONError.nonHTTPSURL(binaryURL)) }


    defvalidate_source_url(spec)returnif spec.source.nil? || spec.source[:http].nil?
      url = URI(spec.source[:http])
      returnif url.scheme == 'https'|| url.scheme == 'file'
      warning('http', "The URL (`#{url}`) doesn't use the encrypted HTTPs protocol. " \
                  'It is crucial for Pods to be transferred over a secure protocol to protect your users from man-in-the-middle attacks. '\
                  'This will be an error in future releases. Please update the URL to use https.')
    end

    The full code is here .

    Swift Package Manager

    At the moment, nothing related to security could not be found, but in the development proposals there is a short mention of a certain mechanism for signing packages using certificates.

    Dependency Integration


    By integration, I mean connecting dependencies to a project in such a way that we can easily use them, and they compile with the main application code.
    Integration can be either manual (Carthage) or automatic (Cocoapods). Advantages of automatic - a minimum of gestures from the developer, but may add a lot of magic to the project.

    Diff after installing dependencies in a project using Cocoapods
    --- a/PODInspect/PODInspect.xcodeproj/project.pbxproj+++ b/PODInspect/PODInspect.xcodeproj/project.pbxproj@@ -12,6 +12,7 @@
     		5132347E1FE94F0900031F77 /* Main.storyboard in Resources */ = {isa = PBXBuildFile; fileRef = 5132347C1FE94F0900031F77 /* Main.storyboard */; };
     		513234801FE94F0900031F77 /* Assets.xcassets in Resources */ = {isa = PBXBuildFile; fileRef = 5132347F1FE94F0900031F77 /* Assets.xcassets */; };
     		513234831FE94F0900031F77 /* LaunchScreen.storyboard in Resources */ = {isa = PBXBuildFile; fileRef = 513234811FE94F0900031F77 /* LaunchScreen.storyboard */; };
    +		80BFE252F8CC89026D002347 /* Pods_PODInspect.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = F92C797D84680452FD95785F /* Pods_PODInspect.framework */; };
     /* End PBXBuildFile section */
     /* Begin PBXFileReference section */
    @@ -22,6 +23,9 @@
     		5132347F1FE94F0900031F77 /* Assets.xcassets */ = {isa = PBXFileReference; lastKnownFileType = folder.assetcatalog; path = Assets.xcassets; sourceTree = "<group>"; };
     		513234821FE94F0900031F77 /* Base */ = {isa = PBXFileReference; lastKnownFileType = file.storyboard; name = Base; path = Base.lproj/LaunchScreen.storyboard; sourceTree = "<group>"; };
     		513234841FE94F0900031F77 /* Info.plist */ = {isa = PBXFileReference; lastKnownFileType = text.plist.xml; path = Info.plist; sourceTree = "<group>"; };
    +		700D806167013759DC590135 /* Pods-PODInspect.debug.xcconfig */ = {isa = PBXFileReference; includeInIndex = 1; lastKnownFileType = text.xcconfig; name = "Pods-PODInspect.debug.xcconfig"; path = "Pods/Target Support Files/Pods-PODInspect/Pods-PODInspect.debug.xcconfig"; sourceTree = "<group>"; };+		E03230E2AEDEF09BD80A4BCB /* Pods-PODInspect.release.xcconfig */ = {isa = PBXFileReference; includeInIndex = 1; lastKnownFileType = text.xcconfig; name = "Pods-PODInspect.release.xcconfig"; path = "Pods/Target Support Files/Pods-PODInspect/Pods-PODInspect.release.xcconfig"; sourceTree = "<group>"; };+		F92C797D84680452FD95785F /* Pods_PODInspect.framework */ = {isa = PBXFileReference; explicitFileType = wrapper.framework; includeInIndex = 0; path = Pods_PODInspect.framework; sourceTree = BUILT_PRODUCTS_DIR; };
     /* End PBXFileReference section */
     /* Begin PBXFrameworksBuildPhase section */
    @@ -29,6 +33,7 @@
     			isa = PBXFrameworksBuildPhase;
     			buildActionMask = 2147483647;
     			files = (
    +				80BFE252F8CC89026D002347 /* Pods_PODInspect.framework in Frameworks */,
     			);
     			runOnlyForDeploymentPostprocessing = 0;
     		};
    @@ -40,6 +45,8 @@
     			children = (
     				513234771FE94F0900031F77 /* PODInspect */,
     				513234761FE94F0900031F77 /* Products */,
    +				78E8125D6DC3597E7EBE4521 /* Pods */,+				7DB1871A5E08D43F92A5D931 /* Frameworks */,
     			);
     			sourceTree = "<group>";
     		};
    @@ -64,6 +71,23 @@
     			path = PODInspect;
     			sourceTree = "<group>";
     		};
    +		78E8125D6DC3597E7EBE4521 /* Pods */ = {+			isa = PBXGroup;+			children = (+				700D806167013759DC590135 /* Pods-PODInspect.debug.xcconfig */,+				E03230E2AEDEF09BD80A4BCB /* Pods-PODInspect.release.xcconfig */,+			);+			name = Pods;+			sourceTree = "<group>";+		};+		7DB1871A5E08D43F92A5D931 /* Frameworks */ = {+			isa = PBXGroup;+			children = (+				F92C797D84680452FD95785F /* Pods_PODInspect.framework */,+			);+			name = Frameworks;+			sourceTree = "<group>";+		};
     /* End PBXGroup section */
     /* Begin PBXNativeTarget section */
    @@ -71,9 +95,12 @@
     			isa = PBXNativeTarget;
     			buildConfigurationList = 513234871FE94F0900031F77 /* Build configuration list for PBXNativeTarget "PODInspect" */;
     			buildPhases = (
    +				5A5E7D86F964C22F5DF60143 /* [CP] Check Pods Manifest.lock */,
     				513234711FE94F0900031F77 /* Sources */,
     				513234721FE94F0900031F77 /* Frameworks */,
     				513234731FE94F0900031F77 /* Resources */,
    +				5FD616368597C8B1F8138B2B /* [CP] Embed Pods Frameworks */,+				F5ECBE5F431B568B7F8C9B0B /* [CP] Copy Pods Resources */,
     			);
     			buildRules = (
     			);
    @@ -131,6 +158,62 @@
     		};
     /* End PBXResourcesBuildPhase section */
    +/* Begin PBXShellScriptBuildPhase section */+		5A5E7D86F964C22F5DF60143 /* [CP] Check Pods Manifest.lock */ = {+			isa = PBXShellScriptBuildPhase;+			buildActionMask = 2147483647;+			files = (+			);+			inputPaths = (+				"${PODS_PODFILE_DIR_PATH}/Podfile.lock",+				"${PODS_ROOT}/Manifest.lock",+			);+			name = "[CP] Check Pods Manifest.lock";+			outputPaths = (+				"$(DERIVED_FILE_DIR)/Pods-PODInspect-checkManifestLockResult.txt",+			);+			runOnlyForDeploymentPostprocessing = 0;+			shellPath = /bin/sh;+			shellScript = "diff \"${PODS_PODFILE_DIR_PATH}/Podfile.lock\" \"${PODS_ROOT}/Manifest.lock\" > /dev/null\nif [ $? != 0 ] ; then\n    # print error to STDERR\n    echo \"error: The sandbox is not in sync with the Podfile.lock. Run 'pod install' or update your CocoaPods installation.\" >&2\n    exit 1\nfi\n# This output is used by Xcode 'outputs' to avoid re-running this script phase.\necho \"SUCCESS\" > \"${SCRIPT_OUTPUT_FILE_0}\"\n";+			showEnvVarsInLog = 0;+		};+		5FD616368597C8B1F8138B2B /* [CP] Embed Pods Frameworks */ = {+			isa = PBXShellScriptBuildPhase;+			buildActionMask = 2147483647;+			files = (+			);+			inputPaths = (+				"${SRCROOT}/Pods/Target Support Files/Pods-PODInspect/Pods-PODInspect-frameworks.sh",+				"${BUILT_PRODUCTS_DIR}/Alamofire/Alamofire.framework",+				"${BUILT_PRODUCTS_DIR}/HTTPTransport/HTTPTransport.framework",+			);+			name = "[CP] Embed Pods Frameworks";+			outputPaths = (+				"${TARGET_BUILD_DIR}/${FRAMEWORKS_FOLDER_PATH}/Alamofire.framework",+				"${TARGET_BUILD_DIR}/${FRAMEWORKS_FOLDER_PATH}/HTTPTransport.framework",+			);+			runOnlyForDeploymentPostprocessing = 0;+			shellPath = /bin/sh;+			shellScript = "\"${SRCROOT}/Pods/Target Support Files/Pods-PODInspect/Pods-PODInspect-frameworks.sh\"\n";+			showEnvVarsInLog = 0;+		};+		F5ECBE5F431B568B7F8C9B0B /* [CP] Copy Pods Resources */ = {+			isa = PBXShellScriptBuildPhase;+			buildActionMask = 2147483647;+			files = (+			);+			inputPaths = (+			);+			name = "[CP] Copy Pods Resources";+			outputPaths = (+			);+			runOnlyForDeploymentPostprocessing = 0;+			shellPath = /bin/sh;+			shellScript = "\"${SRCROOT}/Pods/Target Support Files/Pods-PODInspect/Pods-PODInspect-resources.sh\"\n";+			showEnvVarsInLog = 0;+		};+/* End PBXShellScriptBuildPhase section */+
     /* Begin PBXSourcesBuildPhase section */
     		513234711FE94F0900031F77 /* Sources */ = {
     			isa = PBXSourcesBuildPhase;
    @@ -272,6 +355,7 @@
     		};
     		513234881FE94F0900031F77 /* Debug */ = {
     			isa = XCBuildConfiguration;
    +			baseConfigurationReference = 700D806167013759DC590135 /* Pods-PODInspect.debug.xcconfig */;
     			buildSettings = {
     				ASSETCATALOG_COMPILER_APPICON_NAME = AppIcon;
     				CODE_SIGN_STYLE = Automatic;
    @@ -287,6 +371,7 @@
     		};
     		513234891FE94F0900031F77 /* Release */ = {
     			isa = XCBuildConfiguration;
    +			baseConfigurationReference = E03230E2AEDEF09BD80A4BCB /* Pods-PODInspect.release.xcconfig */;
     			buildSettings = {
     				ASSETCATALOG_COMPILER_APPICON_NAME = AppIcon;
     				CODE_SIGN_STYLE = Automatic;


    In the case of manual, you, following, for example, this instruction Carthage, fully control the process of adding dependencies to the project. Reliable, but longer.

    Dependency update


    You can control the source code of dependencies in a project using their versions.
    There are 3 ways in dependency managers:
    1. Versions of the library. The most convenient and common method. You can specify either a specific version or an interval. Quite predictable way to maintain dependency compatibility provided correct version changes by the authors of libraries.
    2. Branch. When updating the branch and further updating the dependencies, we cannot predict what changes will occur.
    3. Commit or tag When executing an update command, dependencies with links to a specific commit or tag (if they are not changed) will never be updated.

    Conclusion


    In the article I gave a superficial understanding of the internal structure of dependency managers. If you want to learn more, you should dig into the package manager'a source code. The easiest way to find one that is written in a familiar language. The described scheme is typical, but there may be something missing in a separate dependency manager or vice versa a new one will appear.
    Comments and discussion in the comments is welcome.

    Also popular now: