/* Ċ Ġ* ĠCopyright Ġ( C ) Ġ 2 0 2 1 ĠB os ch . IO ĠGmbH Ċ Ġ* Ċ Ġ* Ġ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 Ċ Ġ* Ċ Ġ* ĠĠĠĠ Ġhttps :// 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 . Ċ Ġ* Ċ Ġ* ĠSPDX - License - Identifier : ĠApache - 2 . 0 Ċ Ġ* ĠLicense - Filename : ĠLICENSE Ċ Ġ*/ Ċ Ċ package Ġorg . oss review toolkit . model . utils Ċ Ċ import Ġjava . util . LinkedList Ċ import Ġjava . util . Sorted Set Ċ Ċ import Ġorg . oss review toolkit . model . Dependency Graph Ċ import Ġorg . oss review toolkit . model . Dependency Graph Edge Ċ import Ġorg . oss review toolkit . model . Dependency Graph Node Ċ import Ġorg . oss review toolkit . model . Dependency Reference Ċ import Ġorg . oss review toolkit . model . Identifier Ċ import Ġorg . oss review toolkit . model . Or t Issue Ċ import Ġorg . oss review toolkit . model . Package Ċ import Ġorg . oss review toolkit . model . Package Link age Ċ import Ġorg . oss review toolkit . model . Root Dependency Index Ċ import Ġorg . oss review toolkit . utils . log Ċ Ċ /** Ċ Ġ* ĠInternal Ġclass Ġto Ġrepresent Ġthe Ġresult Ġof Ġa Ġsearch Ġin Ġthe Ġdependency Ġgraph . ĠThe Ġoutcome Ġof Ġthe Ġsearch Ċ Ġ* Ġdetermines Ġhow Ġto Ġintegrate Ġa Ġspecific Ġdependency Ġinto Ġthe Ġdependency Ġgraph . Ċ Ġ*/ Ċ private Ġsealed Ġclass ĠDependency Graph SearchResult Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġspecialized Ġ[ Dependency Graph SearchResult ] Ġthat Ġindicates Ġthat Ġthe Ġdependency Ġthat Ġwas Ġsearched Ġfor Ġis Ġalready ĊĠĠĠĠ Ġ* Ġpresent Ġin Ġthe Ġdependency Ġgraph . ĠThis Ġis Ġthe Ġeasiest Ġcase , Ġas Ġthe Ġ[ Dependency Reference ] Ġthat Ġwas Ġfound ĊĠĠĠĠ Ġ* Ġcan Ġdirectly Ġbe Ġreused . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġdata Ġclass ĠFound ( ĊĠĠĠĠĠĠĠ Ġ/** ĠThe Ġreference Ġto Ġthe Ġdependency Ġthat Ġwas Ġsearched Ġin Ġthe Ġgraph . Ġ*/ ĊĠĠĠĠĠĠĠ Ġval Ġref : ĠDependency Reference ĊĠĠĠ Ġ) Ġ: ĠDependency Graph SearchResult () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġspecialized Ġ[ Dependency Graph SearchResult ] Ġthat Ġindicates Ġthat Ġthe Ġdependency Ġthat Ġwas Ġsearched Ġfor Ġwas Ġnot ĊĠĠĠĠ Ġ* Ġfound Ġin Ġthe Ġdependency Ġgraph , Ġbut Ġa Ġfragment Ġhas Ġbeen Ġdetected , Ġto Ġwhich Ġit Ġcan Ġbe Ġadded . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġdata Ġclass ĠNotFound ( ĊĠĠĠĠĠĠĠ Ġ/** ĠThe Ġindex Ġof Ġthe Ġfragment Ġto Ġwhich Ġto Ġadd Ġthe Ġdependency . Ġ*/ ĊĠĠĠĠĠĠĠ Ġval Ġfragment Index : ĠInt ĊĠĠĠ Ġ) Ġ: ĠDependency Graph SearchResult () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġspecialized Ġ[ Dependency Graph SearchResult ] Ġthat Ġindicates Ġthat Ġthe Ġdependency Ġthat Ġwas Ġsearched Ġfor Ġin Ġits ĊĠĠĠĠ Ġ* Ġcurrent Ġform Ġcannot Ġbe Ġadded Ġto Ġany Ġof Ġthe Ġexisting Ġfragments . ĠThis Ġmeans Ġthat Ġeither Ġthere Ġare Ġno ĊĠĠĠĠ Ġ* Ġfragments Ġyet Ġor Ġeach Ġfragment Ġcontains Ġa Ġvariant Ġof Ġthe Ġdependency Ġwith Ġan Ġincompatible Ġdependency ĊĠĠĠĠ Ġ* Ġtree . ĠIn Ġthis Ġcase , Ġa Ġnew Ġfragment Ġhas Ġto Ġbe Ġadded Ġto Ġthe Ġgraph Ġto Ġhost Ġthis Ġspecial Ġvariant Ġof Ġthis ĊĠĠĠĠ Ġ* Ġdependency . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġobject ĠIn compatible Ġ: ĠDependency Graph SearchResult () Ċ } Ċ Ċ /** Ċ Ġ* ĠA Ġclass Ġthat Ġcan Ġconstruct Ġa Ġ[ Dependency Graph ] Ġfrom Ġa Ġset Ġof Ġdependencies Ġthat Ġprovides Ġan Ġefficient Ġstorage Ġformat Ċ Ġ* Ġfor Ġlarge Ġdependency Ġsets Ġin Ġmany Ġscopes . Ċ Ġ* Ċ Ġ* ĠFor Ġlarger Ġprojects Ġthe Ġnetwork Ġof Ġtrans itive Ġdependencies Ġt ends Ġto Ġbecome Ġcomplex . ĠSingle Ġpackages Ġcan Ġoccur Ġmany Ċ Ġ* Ġtimes Ġin Ġthis Ġstructure Ġif Ġthey Ġare Ġreferenced Ġby Ġmultiple Ġscopes Ġor Ġare Ġfundamental Ġlibraries , Ġon Ġwhich Ġmany Ġother Ċ Ġ* Ġpackages Ġdepend . ĠA Ġna ive Ġimplementation , Ġwhich Ġsimply Ġduplicates Ġthe Ġdependency Ġtrees Ġfor Ġeach Ġscope Ġand Ġpackage Ċ Ġ* Ġtherefore Ġleads Ġto Ġa Ġhigh Ġconsumption Ġof Ġmemory . ĠThis Ġclass Ġaddresses Ġthis Ġproblem Ġby Ġgenerating Ġan Ġoptimized Ċ Ġ* Ġstructure Ġthat Ġshares Ġthe Ġcomponents Ġof Ġthe Ġdependency Ġgraph Ġbetween Ġthe Ġscopes Ġas Ġfar Ġas Ġpossible . Ċ Ġ* Ċ Ġ* ĠThis Ġbuilder Ġclass Ġprovides Ġthe Ġ_ add Dependency () _ Ġfunction , Ġwhich Ġhas Ġto Ġbe Ġcalled Ġfor Ġall Ġthe Ġdirect Ġdependencies Ċ Ġ* Ġof Ġthe Ġdifferent Ġscopes . ĠFrom Ġthese Ġdependencies Ġit Ġconstructs Ġa Ġsingle , Ġoptimized Ġgraph Ġthat Ġis Ġreferenced Ġby Ġall Ċ Ġ* Ġscopes . ĠTo Ġreduce Ġthe Ġamount Ġof Ġmemory Ġrequired Ġeven Ġfurther , Ġpackage Ġidentifiers Ġare Ġreplaced Ġby Ġnumeric Ġindices , Ċ Ġ* Ġso Ġthat Ġreferences Ġin Ġthe Ġgraph Ġare Ġjust Ġnumbers . Ċ Ġ* Ċ Ġ* ĠIde ally , Ġthe Ġresulting Ġdependency Ġgraph Ġcontains Ġeach Ġdependency Ġexactly Ġonce . ĠThere Ġare , Ġhowever , Ġcases , Ġin Ġwhich Ċ Ġ* Ġpackages Ġoccur Ġmultiple Ġtimes Ġin Ġthe Ġproject 's Ġdependency Ġgraph Ġwith Ġdifferent Ġdependencies , Ġfor Ġinstance Ġif Ċ Ġ* Ġex clusions Ġfor Ġtrans itive Ġdependencies Ġare Ġused Ġor Ġa Ġversion Ġresolution Ġmechanism Ġcomes Ġinto Ġplay . ĠIn Ġsuch Ġcases , Ċ Ġ* Ġthe Ġcorresponding Ġpackages Ġneed Ġto Ġform Ġdifferent Ġnodes Ġin Ġthe Ġgraph , Ġso Ġthat Ġthey Ġcan Ġbe Ġdistingu ished , Ġand Ġfor Ċ Ġ* Ġpackages Ġdepending Ġon Ġthem , Ġit Ġmust Ġbe Ġens ured Ġthat Ġthe Ġcorrect Ġnode Ġis Ġreferenced . ĠIn Ġthe Ġtermin ology Ġof Ġthis Ġclass Ċ Ġ* Ġthis Ġis Ġreferred Ġto Ġas Ġ" fragment ation ": ĠA Ġfragment Ġis Ġa Ġconsistent Ġsub Ġgraph , Ġin Ġwhich Ġeach Ġpackage Ġoccurs Ġonly Ċ Ġ* Ġonce . ĠPackages Ġappearing Ġmultiple Ġtimes Ġwith Ġdifferent Ġdependencies Ġneed Ġto Ġbe Ġplaced Ġin Ġseparate Ġfragments . ĠIt Ġis Ċ Ġ* Ġthen Ġpossible Ġto Ġuniquely Ġidentify Ġa Ġspecific Ġpackage Ġby Ġa Ġcombination Ġof Ġits Ġnumeric Ġidentifier Ġand Ġthe Ġindex Ġof Ċ Ġ* Ġthe Ġfragment Ġit Ġbelongs Ġto . Ċ Ġ* Ċ Ġ* ĠThis Ġclass Ġimplements Ġthe Ġfull Ġlogic Ġto Ġconstruct Ġa Ġ[ Dependency Graph ], Ġindependent Ġon Ġthe Ġconcrete Ġrepresentation Ġof Ċ Ġ* Ġdependencies Ġ[ D ] Ġused Ġby Ġspecific Ġpackage Ġmanagers . ĠTo Ġmake Ġthis Ġclass Ġcompatible Ġwith Ġsuch Ġa Ġdependency Ċ Ġ* Ġrepresentation , Ġthe Ġpackage Ġmanager Ġimplementation Ġhas Ġto Ġprovide Ġa Ġ[ Dependency Handler ]. ĠV ia Ġthis Ġhandler , Ġall Ġthe Ċ Ġ* Ġrelevant Ġinformation Ġabout Ġdependencies Ġcan Ġbe Ġextracted . Ċ Ġ*/ Ċ class ĠDependency Graph Builder < D >( ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġ[ Dependency Handler ] Ġused Ġby Ġthis Ġbuilder Ġinstance Ġto Ġextract Ġinformation Ġfrom Ġthe Ġdependency Ġobjects Ġwhen ĊĠĠĠĠ Ġ* Ġconstructing Ġthe Ġ[ Dependency Graph ]. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġdependency Handler : ĠDependency Handler < D > Ċ ) Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġlist Ġstoring Ġthe Ġidentifiers Ġof Ġall Ġdependencies Ġadded Ġto Ġthis Ġbuilder . ĠThis Ġlist Ġis Ġthen Ġused Ġto Ġresolve ĊĠĠĠĠ Ġ* Ġdependencies Ġbased Ġon Ġtheir Ġindices . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġdependency Ids Ġ= Ġmutable ListOf < Identifier >() ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġset Ġstoring Ġthe Ġidentifiers Ġof Ġall Ġpackage Ġdependencies Ġwith Ġno Ġissues . ĠThis Ġis Ġused Ġto Ġcheck Ġwhether Ġthere ĊĠĠĠĠ Ġ* Ġare Ġreferences Ġto Ġpackages Ġnot Ġcontained Ġin Ġthis Ġbuilder 's Ġlist Ġof Ġpackages . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġvalid Package Dependencies Ġ= Ġmutable Set Of < Identifier >() ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġmapping Ġof Ġthe Ġidentifiers Ġof Ġthe Ġdependencies Ġknown Ġto Ġthis Ġbuilder Ġto Ġtheir Ġnumeric Ġindices . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġdependency Index Mapping Ġ= Ġmutable Map Of < Identifier , ĠInt >() ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠStores Ġall Ġthe Ġreferences Ġto Ġdependencies Ġthat Ġhave Ġbeen Ġadded Ġso Ġfar . ĠEach Ġelement Ġof Ġthe Ġlist Ġrepresents Ġa ĊĠĠĠĠ Ġ* Ġfragment Ġof Ġthe Ġdependency Ġgraph . ĠFor Ġeach Ġfragment , Ġthere Ġis Ġa Ġmapping Ġfrom Ġa Ġdependency Ġindex Ġto Ġthe ĊĠĠĠĠ Ġ* Ġreference Ġpointing Ġto Ġthe Ġcorresponding Ġdependency Ġtree . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġreference Mappings Ġ= Ġmutable ListOf < Mutable Map < Int , ĠDependency Reference >>() ĊĊĠĠĠ Ġ/** ĠThe Ġmapping Ġfrom Ġscopes Ġto Ġdependencies Ġconstructed Ġby Ġthis Ġbuilder . Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġscope Mapping Ġ= Ġmutable Map Of < String , ĠList < Root Dependency Index >>() ĊĊĠĠĠ Ġ/** ĠStores Ġall Ġpackages Ġencountered Ġin Ġthe Ġdependency Ġtree Ġassociated Ġby Ġtheir ĠID . Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġresolved Packages Ġ= Ġmutable Map Of < Identifier , ĠPackage >() ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġset Ġstoring Ġthe Ġpackages Ġthat Ġare Ġdirect Ġdependencies Ġof Ġone Ġof Ġthe Ġscopes . ĠThese Ġare Ġthe Ġentry Ġpoints Ġinto ĊĠĠĠĠ Ġ* Ġthe Ġdependency Ġgraph . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġdirect Dependencies Ġ= Ġmutable Set Of < Dependency Reference >() ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdd Ġthe Ġgiven Ġ[ dependency ] Ġfor Ġthe Ġscope Ġwith Ġthe Ġgiven Ġ[ scope Name ] Ġto Ġthis Ġbuilder . ĠThis Ġfunction Ġneeds Ġto Ġbe ĊĠĠĠĠ Ġ* Ġcalled Ġall Ġthe Ġdirect Ġdependencies Ġof Ġall Ġscopes . ĠThat Ġway Ġthe Ġbuilder Ġgets Ġsufficient Ġinformation Ġto Ġconstruct ĊĠĠĠĠ Ġ* Ġthe Ġ[ Dependency Graph ]. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd Dependency ( scope Name : ĠString , Ġdependency : ĠD ): ĠDependency Graph Builder < D > Ġ= ĊĠĠĠĠĠĠĠ Ġapply Ġ{ Ġadd Dependency To Graph ( scope Name , Ġdependency , Ġtrans itive Ġ= Ġfalse ) Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdd Ġthe Ġgiven Ġ[ packages ] Ġto Ġthis Ġbuilder . ĠThey Ġare Ġstored Ġinternally Ġand Ġalso Ġreturned Ġwhen Ġquerying Ġthe Ġset Ġof ĊĠĠĠĠ Ġ* Ġknown Ġpackages . ĠThis Ġfunction Ġcan Ġbe Ġused Ġby Ġpackage Ġmanagers Ġthat Ġhave Ġto Ġdeal Ġwith Ġpackages Ġnot Ġpart Ġof ĊĠĠĠĠ Ġ* Ġnormal Ġscope Ġdependencies . ĠOne Ġexample Ġwould Ġbe ĠY arn ; Ġhere Ġpackages Ġcan Ġbe Ġdefined Ġin Ġthe Ġworkspace Ġand Ġare Ġnot ĊĠĠĠĠ Ġ* Ġnecessarily Ġreferenced Ġby Ġmanifest Ġfiles . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd Packages ( packages : ĠCollection < Package >): ĠDependency Graph Builder < D > Ġ= ĊĠĠĠĠĠĠĠ Ġapply Ġ{ Ġresolved Packages Ġ+= Ġpackages . associate By Ġ{ Ġit . id Ġ} Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġthe Ġ[ Dependency Graph ] Ġfrom Ġthe Ġdependencies Ġpassed Ġto Ġthis Ġbuilder Ġso Ġfar . ĠIf Ġ[ check References ] Ġis ĊĠĠĠĠ Ġ* Ġ* true *, Ġcheck Ġwhether Ġall Ġdependency Ġreferences Ġused Ġin Ġthe Ġgraph Ġpoint Ġto Ġpackages Ġmanaged Ġby Ġthis Ġbuilder . ĊĠĠĠĠ Ġ* ĠThis Ġcheck Ġis Ġenabled Ġby Ġdefault Ġand Ġshould Ġbe Ġdone Ġfor Ġall Ġpackage Ġmanager Ġimplementations . ĠOnly Ġfor Ġspecial ĊĠĠĠĠ Ġ* Ġcases , Ġe . g . Ġthe Ġconversion Ġfrom Ġthe Ġdependency Ġtree Ġto Ġthe Ġdependency Ġgraph Ġformat , Ġit Ġneeds Ġto Ġbe Ġdisabled Ġas ĊĠĠĠĠ Ġ* Ġthe Ġconditions Ġdo Ġnot Ġhold Ġthen . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġbuild ( check References : ĠBoolean Ġ= Ġtrue ): ĠDependency Graph Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( check References ) Ġcheck References () ĊĊĠĠĠĠĠĠĠ Ġval Ġ( sorted Dependency Ids , Ġindex Mapping ) Ġ= Ġconstruct Sorted Dependency Ids ( dependency Ids ) ĊĠĠĠĠĠĠĠ Ġval Ġ( nodes , Ġedges ) Ġ= Ġdirect Dependencies . to Graph ( index Mapping ) ĊĊĠĠĠĠĠĠĠ Ġreturn ĠDependency Graph ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsorted Dependency Ids , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsorted Set Of (), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġconstruct Sorted Scope Mappings ( scope Mapping , Ġindex Mapping ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnodes , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġedges . remove Cycles () ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun ĠCollection < Dependency Graph Edge >. remove Cycles (): ĠList < Dependency Graph Edge > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġedges Ġ= Ġmap To ( mutable Set Of ()) Ġ{ Ġit . from Ġto Ġit . to Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġedges To Keep Ġ= Ġbreak Cycles ( edges ) ĊĠĠĠĠĠĠĠ Ġval Ġedges ToRemove Ġ= Ġedges Ġ- Ġedges To Keep ĊĊĠĠĠĠĠĠĠ Ġedges ToRemove . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis @ Dependency Graph Builder . log . warn Ġ{ Ġ" Removing Ġedge Ġ'${ it . first } Ġ-> Ġ${ it . second }' Ġto Ġbreak Ġa Ġcycle ." Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġfilter Ġ{ Ġit . from Ġto Ġit . to Ġin Ġedges To Keep Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcheck References () Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire ( resolved Packages . keys . contains All ( valid Package Dependencies )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ" The Ġfollowing Ġreferences Ġdo Ġnot Ġactually Ġrefer Ġto Ġpackages : Ġ" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ"${ valid Package Dependencies Ġ- Ġresolved Packages . keys } ." ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġpackage References Keys With Multiple Distinct Package References Ġ= Ġdirect Dependencies . groupBy Ġ{ Ġit . key Ġ}. filter Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit . value . distinct (). size Ġ> Ġ 1 ĊĠĠĠĠĠĠĠ Ġ}. keys ĊĊĠĠĠĠĠĠĠ Ġrequire ( package References Keys With Multiple Distinct Package References . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ" Found Ġmultiple Ġdistinct Ġpackage Ġreferences Ġfor Ġeach Ġof Ġthe Ġfollowing Ġpackage Ġ/ Ġfragment Ġindex Ġtuples Ġ" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ"${ package References Keys With Multiple Distinct Package References . join ToString ()} ." ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturn Ġa Ġset Ġwith Ġall Ġthe Ġpackages Ġthat Ġhave Ġbeen Ġencountered Ġfor Ġthe Ġcurrent Ġproject . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġpackages (): ĠSet < Package > Ġ= Ġresolved Packages . values . toSet () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturn Ġa Ġset Ġof Ġall Ġthe Ġscope Ġnames Ġknown Ġto Ġthis Ġbuilder Ġthat Ġstart Ġwith Ġthe Ġgiven Ġ[ prefix ]. ĠIf Ġ[ un qual ify ] Ġis ĊĠĠĠĠ Ġ* Ġ* true *, Ġremove Ġthis Ġprefix Ġfrom Ġthe Ġreturned Ġscope Ġnames . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġscopes For ( prefix : ĠString , Ġun qual ify : ĠBoolean Ġ= Ġtrue ): ĠSorted Set < String > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġqualified Scopes Ġ= Ġscope Mapping . keys . filter Ġ{ Ġit . startsWith ( prefix ) Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġ( qualified Scopes . take Unless Ġ{ Ġun qual ify Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ?: Ġqualified Scopes . map Ġ{ Ġit . substring ( prefix . length ) Ġ}). to Sorted Set () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturn Ġa Ġset Ġof Ġall Ġthe Ġscope Ġnames Ġknown Ġto Ġthis Ġbuilder Ġthat Ġare Ġqualified Ġwith Ġthe Ġgiven Ġ[ projectId ]. ĠIf ĊĠĠĠĠ Ġ* Ġ[ un qual ify ] Ġis Ġ* true *, Ġremove Ġthe Ġproject Ġqualifier Ġfrom Ġthe Ġreturned Ġscope Ġnames . ĠAs Ġdependency Ġgraphs Ġare ĊĠĠĠĠ Ġ* Ġshared Ġbetween Ġmultiple Ġprojects , Ġscope Ġnames Ġare Ġgiven Ġa Ġproject - specific Ġprefix Ġto Ġmake Ġthem Ġunique . ĠUsing ĊĠĠĠĠ Ġ* Ġthis Ġfunction , Ġthe Ġscope Ġnames Ġof Ġa Ġspecific Ġproject Ġcan Ġbe Ġretrieved . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġscopes For ( projectId : ĠIdentifier , Ġun qual ify : ĠBoolean Ġ= Ġtrue ): ĠSorted Set < String > Ġ= ĊĠĠĠĠĠĠĠ Ġscopes For ( Dependency Graph . qual ify Scope ( projectId , Ġ""), Ġun qual ify ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠUpdate Ġthe Ġdependency Ġgraph Ġby Ġadding Ġthe Ġgiven Ġ[ dependency ], Ġwhich Ġmay Ġbe Ġ[ trans itive ], Ġfor Ġthe Ġscope Ġwith Ġname ĊĠĠĠĠ Ġ* Ġ[ scope Name ]. ĠAll Ġthe Ġdependencies Ġof Ġthis Ġdependency Ġare Ġprocessed Ġrecursively . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġadd Dependency To Graph ( scope Name : ĠString , Ġdependency : ĠD , Ġtrans itive : ĠBoolean ): ĠDependency Reference Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġid Ġ= Ġdependency Handler . identifier For ( dependency ) ĊĠĠĠĠĠĠĠ Ġval Ġissues Ġ= Ġdependency Handler . issues For Dependency ( dependency ). to Mutable List () ĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġupdate Dependency Mapping And Packages ( id , Ġdependency , Ġissues ) ĊĊĠĠĠĠĠĠĠ Ġval Ġref Ġ= Ġwhen Ġ( val Ġresult Ġ= Ġfind Dependency In Graph ( index , Ġdependency )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠDependency Graph SearchResult . Found Ġ-> Ġresult . ref ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠDependency Graph SearchResult . NotFound Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinsert Into Graph ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġid , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠRoot Dependency Index ( index , Ġresult . fragment Index ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġscope Name , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdependency , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġissues , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrans itive ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠDependency Graph SearchResult . In compatible Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinsert Into New Fragment ( id , Ġindex , Ġscope Name , Ġdependency , Ġissues , Ġtrans itive ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġupdate Scope Mapping ( scope Name , Ġref , Ġtrans itive ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠUpdate Ġinternal Ġstate Ġfor Ġthe Ġgiven Ġdependency Ġ[ id ]. ĠCheck Ġwhether Ġthis ĠID Ġis Ġalready Ġknown . ĠIf Ġnot , Ġadd Ġit ĊĠĠĠĠ Ġ* Ġto Ġthe Ġdata Ġmanaged Ġby Ġthis Ġinstance , Ġresolve Ġthe Ġpackage , Ġand Ġupdate Ġthe Ġ[ issues ] Ġif Ġnecessary . ĠReturn Ġthe ĊĠĠĠĠ Ġ* Ġnumeric Ġindex Ġfor Ġthis Ġdependency . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġupdate Dependency Mapping And Packages ( id : ĠIdentifier , Ġdependency : ĠD , Ġissues : ĠMutable List < Or t Issue >): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdependency Index Ġ= Ġdependency Index Mapping [ id ] ĊĠĠĠĠĠĠĠ Ġif Ġ( dependency Index Ġ!= Ġnull ) Ġreturn Ġdependency Index ĊĊĠĠĠĠĠĠĠ Ġupdate Resolved Packages ( id , Ġdependency , Ġissues ) ĊĊĠĠĠĠĠĠĠ Ġreturn Ġdependency Ids . size . also Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdependency Ids Ġ+= Ġid ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdependency Index Mapping [ id ] Ġ= Ġit ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSearch Ġfor Ġthe Ġ[ dependency ] Ġwith Ġthe Ġgiven Ġ[ index ] Ġin Ġthe Ġfragments Ġof Ġthe Ġdependency Ġgraph . ĠReturn Ġa ĊĠĠĠĠ Ġ* Ġ[ Dependency Graph SearchResult ] Ġthat Ġindicates Ġhow Ġto Ġproceed Ġwith Ġthis Ġdependency . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġfind Dependency In Graph ( index : ĠInt , Ġdependency : ĠD ): ĠDependency Graph SearchResult Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmapping For Compatible Fragment Ġ= Ġreference Mappings . find Ġ{ Ġmapping Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmapping [ index ]?. take If Ġ{ Ġdependency Tree Equals ( it , Ġdependency ) Ġ} Ġ!= Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġcompatible Reference Ġ= Ġmapping For Compatible Fragment ?. let Ġ{ Ġit [ index ] Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġcompatible Reference ?. let Ġ{ ĠDependency Graph SearchResult . Found ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ?: Ġhandle No Compatible Dependency In Graph ( index ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠDetermine Ġhow Ġto Ġdeal Ġwith Ġthe Ġdependency Ġwith Ġthe Ġgiven Ġ[ index ], Ġfor Ġwhich Ġno Ġcompatible Ġvariant Ġwas Ġfound ĊĠĠĠĠ Ġ* Ġin Ġthe Ġdependency Ġgraph . ĠTry Ġto Ġfind Ġa Ġfragment , Ġin Ġwhich Ġthe Ġdependency Ġcan Ġbe Ġinserted . ĠIf Ġthis Ġfails , Ġa Ġnew ĊĠĠĠĠ Ġ* Ġfragment Ġhas Ġto Ġbe Ġadded . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġhandle No Compatible Dependency In Graph ( index : ĠInt ): ĠDependency Graph SearchResult Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmapping To Insert Ġ= Ġreference Mappings . with Index (). find Ġ{ Ġindex Ġ! in Ġit . value Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġmapping To Insert ?. let Ġ{ ĠDependency Graph SearchResult . NotFound ( it . index ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ?: ĠDependency Graph SearchResult . In compatible ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCheck Ġwhether Ġthe Ġdependency Ġtree Ġspawn ed Ġby Ġ[ dependency ] Ġmatches Ġthe Ġone Ġ[ ref ] Ġpoints Ġto . ĠUsing Ġthis Ġfunction , ĊĠĠĠĠ Ġ* Ġpackages Ġare Ġidentified Ġthat Ġoccur Ġmultiple Ġtimes Ġin Ġthe Ġdependency Ġgraph Ġwith Ġdifferent Ġsets Ġof Ġdependencies ; ĊĠĠĠĠ Ġ* Ġthese Ġhave Ġto Ġbe Ġplaced Ġin Ġseparate Ġfragments Ġof Ġthe Ġdependency Ġgraph . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġdependency Tree Equals ( ref : ĠDependency Reference , Ġdependency : ĠD ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdependencies Ġ= Ġdependency Handler . dependencies For ( dependency ) ĊĠĠĠĠĠĠĠ Ġif Ġ( ref . dependencies . size Ġ!= Ġdependencies . size ) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġval Ġdependencies 1 Ġ= Ġref . dependencies . map Ġ{ Ġdependency Ids [ it . pkg ] Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġdependencies 2 Ġ= Ġdependencies . associate By Ġ{ Ġdependency Handler . identifier For ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ(! dependencies 2 . keys . contains All ( dependencies 1 )) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġreturn Ġref . dependencies . all Ġ{ Ġref Dep Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdependencies 2 [ dependency Ids [ ref Dep . pkg ]] ?. let Ġ{ Ġdependency Tree Equals ( ref Dep , Ġit ) Ġ} Ġ?: Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdd Ġa Ġnew Ġfragment Ġto Ġthe Ġdependency Ġgraph Ġfor Ġthe Ġ[ dependency ] Ġwith Ġthe Ġgiven Ġ[ id ] Ġand Ġ[ index ], Ġwhich Ġmay Ġbe ĊĠĠĠĠ Ġ* Ġ[ trans itive ] Ġand Ġbelongs Ġto Ġthe Ġscope Ġwith Ġthe Ġgiven Ġ[ scope Name ]. ĠThis Ġfunction Ġis Ġcalled Ġfor Ġdependencies Ġthat ĊĠĠĠĠ Ġ* Ġcannot Ġbe Ġadded Ġto Ġalready Ġexisting Ġfragments . ĠTherefore , Ġcreate Ġa Ġnew Ġfragment Ġand Ġadd Ġthe Ġ[ dependency ] Ġto Ġit , ĊĠĠĠĠ Ġ* Ġtogether Ġwith Ġits Ġown Ġdependencies . ĠStore Ġthe Ġgiven Ġ[ issues ] Ġfor Ġthe Ġdependency . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġinsert Into New Fragment ( ĊĠĠĠĠĠĠĠ Ġid : ĠIdentifier , ĊĠĠĠĠĠĠĠ Ġindex : ĠInt , ĊĠĠĠĠĠĠĠ Ġscope Name : ĠString , ĊĠĠĠĠĠĠĠ Ġdependency : ĠD , ĊĠĠĠĠĠĠĠ Ġissues : ĠList < Or t Issue >, ĊĠĠĠĠĠĠĠ Ġtrans itive : ĠBoolean ĊĠĠĠ Ġ): ĠDependency Reference Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġfragment Mapping Ġ= Ġmutable Map Of < Int , ĠDependency Reference >() ĊĠĠĠĠĠĠĠ Ġval Ġdependency Index Ġ= ĠRoot Dependency Index ( index , Ġreference Mappings . size ) ĊĠĠĠĠĠĠĠ Ġreference Mappings Ġ+= Ġfragment Mapping ĊĊĠĠĠĠĠĠĠ Ġreturn Ġinsert Into Graph ( id , Ġdependency Index , Ġscope Name , Ġdependency , Ġissues , Ġtrans itive ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInsert Ġthe Ġ[ dependency ] Ġwith Ġthe Ġgiven Ġ[ id ] Ġand Ġ[ Root Dependency Index ][ index ], Ġwhich Ġbelongs Ġto Ġthe Ġscope Ġwith ĊĠĠĠĠ Ġ* Ġthe Ġgiven Ġ[ scope Name ] Ġand Ġmay Ġbe Ġ[ trans itive ] Ġinto Ġthe Ġdependency Ġgraph . ĠInsert Ġthe Ġdependencies Ġof Ġthis ĊĠĠĠĠ Ġ* Ġ[ dependency ] Ġrecursively . ĠCreate Ġa Ġnew Ġ[ Dependency Reference ] Ġfor Ġthe Ġdependency Ġand Ġinitialize Ġit Ġwith Ġthe Ġlist ĊĠĠĠĠ Ġ* Ġof Ġ[ issues ]. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġinsert Into Graph ( ĊĠĠĠĠĠĠĠ Ġid : ĠIdentifier , ĊĠĠĠĠĠĠĠ Ġindex : ĠRoot Dependency Index , ĊĠĠĠĠĠĠĠ Ġscope Name : ĠString , ĊĠĠĠĠĠĠĠ Ġdependency : ĠD , ĊĠĠĠĠĠĠĠ Ġissues : ĠList < Or t Issue >, ĊĠĠĠĠĠĠĠ Ġtrans itive : ĠBoolean ĊĠĠĠ Ġ): ĠDependency Reference Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġtrans itive Dependencies Ġ= Ġdependency Handler . dependencies For ( dependency ). map Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd Dependency To Graph ( scope Name , Ġit , Ġtrans itive Ġ= Ġtrue ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġfragment Mapping Ġ= Ġreference Mappings [ index . fragment ] ĊĠĠĠĠĠĠĠ Ġval Ġref Ġ= ĠDependency Reference ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpkg Ġ= Ġindex . root , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfragment Ġ= Ġindex . fragment , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdependencies Ġ= Ġtrans itive Dependencies . to Sorted Set (), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlink age Ġ= Ġdependency Handler . link age For ( dependency ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġissues Ġ= Ġissues ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġfragment Mapping [ index . root ] Ġ= Ġref ĊĊĠĠĠĠĠĠĠ Ġif Ġ( ref . issues . isEmpty () Ġ&& Ġref . link age Ġ! in ĠPackage Link age . PROJECT _ LINK AGE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalid Package Dependencies Ġ+= Ġid ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġupdate Direct Dependencies ( ref , Ġtrans itive ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġa Ġ[ Package ] Ġfor Ġthe Ġgiven Ġ[ id ] Ġthat Ġcorresponds Ġto Ġthe Ġgiven Ġ[ dependency ]. ĠIf Ġthe Ġpackage Ġis Ġalready ĊĠĠĠĠ Ġ* Ġavailable , Ġnothing Ġhas Ġto Ġbe Ġdone . ĠOtherwise , Ġcreate Ġa Ġnew Ġone Ġand Ġadd Ġit Ġto Ġthe Ġset Ġmanaged Ġby Ġthis Ġobject . ĠIf ĊĠĠĠĠ Ġ* Ġthis Ġfails , Ġrecord Ġa Ġcorresponding Ġmessage Ġin Ġ[ issues ]. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġupdate Resolved Packages ( id : ĠIdentifier , Ġdependency : ĠD , Ġissues : ĠMutable List < Or t Issue >) Ġ{ ĊĠĠĠĠĠĠĠ Ġresolved Packages . compute ( id ) Ġ{ Ġ_, Ġpkg Ġ-> Ġpkg Ġ?: Ġdependency Handler . create Package ( dependency , Ġissues ) Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdd Ġthe Ġgiven Ġ[ dependency Ġreference ][ ref ] Ġto Ġthe Ġset Ġof Ġdirect Ġdependencies Ġif Ġit Ġis Ġnot Ġ[ trans itive ]. ĠIf Ġone Ġof ĊĠĠĠĠ Ġ* Ġthe Ġdirect Ġdependencies Ġof Ġthis Ġpackage Ġis Ġin Ġthis Ġset , Ġit Ġis Ġremoved , Ġas Ġit Ġis Ġobviously Ġno Ġdirect Ġdependency . ĊĠĠĠĠ Ġ* ĠBecause Ġthis Ġfunction Ġis Ġcalled Ġfor Ġall Ġdependencies , Ġall Ġtrans itive Ġdependencies Ġare Ġeventually Ġremoved . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġupdate Direct Dependencies ( ref : ĠDependency Reference , Ġtrans itive : ĠBoolean ): ĠDependency Reference Ġ{ ĊĠĠĠĠĠĠĠ Ġdirect Dependencies . removeAll ( ref . dependencies ) ĊĠĠĠĠĠĠĠ Ġif Ġ(! trans itive ) Ġdirect Dependencies Ġ+= Ġref ĊĊĠĠĠĠĠĠĠ Ġreturn Ġref ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠUpdate Ġthe Ġscope Ġmapping Ġfor Ġthe Ġgiven Ġ[ scope Name ] Ġto Ġdepend Ġon Ġ[ ref ], Ġwhich Ġmay Ġbe Ġa Ġ[ trans itive ] Ġdependency . ĊĠĠĠĠ Ġ* ĠThe Ġscope Ġmapping Ġrecords Ġall Ġthe Ġdirect Ġdependencies Ġof Ġscopes . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġupdate Scope Mapping ( ĊĠĠĠĠĠĠĠ Ġscope Name : ĠString , Ġref : ĠDependency Reference , Ġtrans itive : ĠBoolean ĊĠĠĠ Ġ): ĠDependency Reference Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! trans itive ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġindex Ġ= ĠRoot Dependency Index ( ref . pkg , Ġref . fragment ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġscope Mapping . compute ( scope Name ) Ġ{ Ġ_, Ġids Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġids ?. let Ġ{ Ġit Ġ+ Ġindex Ġ} Ġ?: ĠlistOf ( index ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġref ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠConvert Ġthe Ġdirect Ġdependency Ġreferences Ġof Ġall Ġprojects Ġto Ġa Ġlist Ġof Ġnodes Ġand Ġedges Ġthat Ġrepresent Ġthe Ġfinal Ċ Ġ* Ġdependency Ġgraph . ĠApply Ġthe Ġgiven Ġ[ index Mapping ] Ġto Ġthe Ġindices Ġpointing Ġto Ġdependencies . Ċ Ġ*/ Ċ private Ġfun ĠCollection < Dependency Reference >. to Graph ( ĊĠĠĠ Ġindex Mapping : ĠInt Array Ċ ): ĠPair < List < Dependency Graph Node >, ĠList < Dependency Graph Edge >> Ġ{ ĊĠĠĠ Ġval Ġnodes Ġ= Ġmutable Set Of < Dependency Graph Node >() ĊĠĠĠ Ġval Ġedges Ġ= Ġmutable ListOf < Dependency Graph Edge >() ĊĠĠĠ Ġval Ġnode Indices Ġ= Ġmutable Map Of < Node Key , ĠInt >() ĊĊĠĠĠ Ġfun Ġget Or Add Node Index ( ref : ĠDependency Reference ): ĠInt Ġ= ĊĠĠĠĠĠĠĠ Ġnode Indices . get Or Put ( ref . key ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnodes Ġ+= ĠDependency Graph Node ( index Mapping [ ref . pkg ], Ġref . fragment , Ġref . link age , Ġref . issues ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnodes . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġvisit Each Ġ{ Ġfrom Ref Ġ-> ĊĠĠĠĠĠĠĠ Ġval Ġfrom Node Index Ġ= Ġget Or Add Node Index ( from Ref ) ĊĊĠĠĠĠĠĠĠ Ġfrom Ref . dependencies . forEach Ġ{ Ġto Ref Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġto Node Index Ġ= Ġget Or Add Node Index ( to Ref ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġedges Ġ+= ĠDependency Graph Edge ( from Node Index , Ġto Node Index ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġnodes . toList () Ġto Ġedges Ċ } Ċ Ċ private Ġfun ĠCollection < Dependency Reference >. visit Each ( visit : Ġ( ref : ĠDependency Reference ) Ġ-> ĠUnit ) Ġ{ ĊĠĠĠ Ġval Ġvisited Ġ= Ġmutable Set Of < Node Key >() ĊĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList ( this ) ĊĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġref Ġ= Ġqueue . remove First () ĊĊĠĠĠĠĠĠĠ Ġif Ġ( ref . key Ġ! in Ġvisited ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvisit ( ref ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvisited Ġ+= Ġref . key ĊĠĠĠĠĠĠĠĠĠĠĠ Ġqueue Ġ+= Ġref . dependencies ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġdata Ġclass ĠNode Key ( ĊĠĠĠ Ġval Ġpkg : ĠInt , ĊĠĠĠ Ġval Ġfragment : ĠInt Ċ ) Ċ Ċ private Ġval ĠDependency Reference . key : ĠNode Key ĊĠĠĠ Ġget () Ġ= ĠNode Key ( pkg , Ġfragment ) Ċ Ċ private Ġenum Ġclass ĠNode Color Ġ{ ĠWH ITE , ĠGR AY , ĠBLACK Ġ} Ċ Ċ /** Ċ Ġ* ĠA Ġdepth - first - search Ġ( DFS )- based Ġimplementation Ġwhich Ġbreaks Ġall Ġcycles Ġin ĠO ( V Ġ+ ĠE ). Ċ Ġ* ĠFind ing Ġa Ġminimal Ġsolution Ġis ĠNP - complete . Ċ Ġ*/ Ċ internal Ġfun Ġbreak Cycles ( edges : ĠCollection < Pair < Int , ĠInt >> ): ĠSet < Pair < Int , ĠInt >> Ġ{ ĊĠĠĠ Ġval Ġoutgoing Edges For Nodes Ġ= Ġedges . groupBy ({ Ġit . first Ġ}, Ġ{ Ġit . second Ġ}). map Values Ġ{ Ġit . value . to Mutable Set () Ġ} ĊĠĠĠ Ġval Ġcolor Ġ= Ġoutgoing Edges For Nodes . keys . associate With To ( mutable Map Of ()) Ġ{ ĠNode Color . WHITE Ġ} ĊĊĠĠĠ Ġfun Ġvisit ( u : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġcolor [ u ] Ġ= ĠNode Color . GRAY ĊĊĠĠĠĠĠĠĠ Ġval Ġnodes Closing Circle Ġ= Ġmutable Set Of < Int >() ĊĊĠĠĠĠĠĠĠ Ġoutgoing Edges For Nodes [ u ]. or Empty (). forEach Ġ{ Ġv Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( color [ v ] Ġ== ĠNode Color . WHITE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvisit ( v ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( color [ v ] Ġ== ĠNode Color . GRAY ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnodes Closing Circle Ġ+= Ġv ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġoutgoing Edges For Nodes [ u ]?. removeAll ( nodes Closing Circle ) ĊĊĠĠĠĠĠĠĠ Ġcolor [ u ] Ġ= ĠNode Color . BLACK ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList ( outgoing Edges For Nodes . keys ) ĊĊĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġqueue . remove First () ĊĊĠĠĠĠĠĠĠ Ġif Ġ( color . getValue ( v ) Ġ!= ĠNode Color . WHITE ) Ġcontinue ĊĊĠĠĠĠĠĠĠ Ġvisit ( v ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġoutgoing Edges For Nodes . flatMap To ( mutable Set Of ()) Ġ{ Ġ( from Node , Ġto Nodes ) Ġ-> ĊĠĠĠĠĠĠĠ Ġto Nodes . map Ġ{ Ġto Node Ġ-> Ġfrom Node Ġto Ġto Node Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠSort Ġthe Ġlist Ġof Ġ[ identifiers ][ ids ] Ġfor Ġthe Ġknown Ġdependencies Ġand Ġgenerate Ġa Ġmapping , Ġso Ġthat Ġall Ġindex - based Ċ Ġ* Ġreferences Ġcan Ġbe Ġadjusted Ġaccordingly . ĠThe Ġlatter Ġis Ġjust Ġan Ġarray Ġthat Ġcontains Ġat Ġindex Ġi Ġthe Ġnew Ġindex Ġfor Ġthe Ċ Ġ* Ġidentifier Ġthat Ġwas Ġoriginally Ġat Ġindex Ġi . Ċ Ġ*/ Ċ private Ġfun Ġconstruct Sorted Dependency Ids ( ids : ĠCollection < Identifier >): ĠPair < List < Identifier >, ĠInt Array > Ġ{ ĊĠĠĠ Ġval Ġsorted Ids Ġ= Ġids . with Index (). sorted By Ġ{ Ġit . value . to Coordinates () Ġ} ĊĠĠĠ Ġval Ġindex Mapping Ġ= ĠInt Array ( sorted Ids . size ) ĊĊĠĠĠ Ġvar ĠcurrentIndex Ġ= Ġ 0 ĊĠĠĠ Ġsorted Ids . forEach Ġ{ Ġindex Mapping [ it . index ] Ġ= ĠcurrentIndex ++ Ġ} ĊĊĠĠĠ Ġreturn Ġsorted Ids . map Ġ{ Ġit . value Ġ} Ġto Ġindex Mapping Ċ } Ċ Ċ /** ĠA ĠComparator Ġfor Ġordering Ġ[ Root Dependency Index ] Ġinstances . Ġ*/ Ċ private Ġval Ġroot Dependency Index Comparator Ġ= Ġcompare By ( Root Dependency Index :: root ). then By ( Root Dependency Index :: fragment ) Ċ Ċ /** Ċ Ġ* ĠSort Ġthe Ġgiven Ġ[ scope Mappings ] Ġby Ġscope Ġnames , Ġand Ġthe Ġlists Ġof Ġdependencies Ġper Ġscope Ġby Ġtheir Ġpackage Ġindices . Ċ Ġ* ĠAlso Ġapply Ġthe Ġgiven Ġ[ index Mapping ] Ġto Ġthe Ġdependency Ġindices . Ċ Ġ*/ Ċ private Ġfun Ġconstruct Sorted Scope Mappings ( ĊĠĠĠ Ġscope Mappings : ĠMap < String , ĠList < Root Dependency Index >>, ĊĠĠĠ Ġindex Mapping : ĠInt Array Ċ ): ĠMap < String , ĠList < Root Dependency Index >> Ġ{ ĊĠĠĠ Ġval Ġordered Mappings Ġ= Ġmutable Map Of < String , ĠList < Root Dependency Index >>() ĊĊĠĠĠ Ġscope Mappings . keys . to Sorted Set (). forEach Ġ{ Ġscope Ġ-> ĊĠĠĠĠĠĠĠ Ġordered Mappings [ scope ] Ġ= Ġscope Mappings . getValue ( scope ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġit . map Index ( index Mapping ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. sorted With ( root Dependency Index Comparator ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġordered Mappings Ċ } Ċ Ċ /** Ċ Ġ* ĠApply Ġthe Ġgiven Ġ[ index Mapping ] Ġto Ġthis Ġ[ Root Dependency Index ]. ĠIf Ġthere Ġis Ġa Ġchange , Ġreturn Ġa Ġnew Ġinstance Ġwith Ġan Ċ Ġ* Ġupdated Ġindex . Ċ Ġ*/ Ċ private Ġfun ĠRoot Dependency Index . map Index ( index Mapping : ĠInt Array ): ĠRoot Dependency Index Ġ= ĊĠĠĠ Ġtake If Ġ{ Ġindex Mapping [ root ] Ġ== Ġroot Ġ} Ġ?: Ġcopy ( root Ġ= Ġindex Mapping [ root ]) Ċ