FAQ
Are their any existing libraries that either directly, or are a good
reference to, help solve the problem of resolving versioned package
dependencies?

There is a project I am spec'ing to rewrite in Go, that deals with
resolving custom package dependencies with version ranges, and I'm
wondering if there are any higher level solutions available? I've seen a
couple of graphing libs out there, but I thought I might ask about this
specific problem first, since I am not much of an algorithms genius and
figured smarter people must have solved this before me.

In searching, I have come across terms like "constraint satisfaction", and
suggestions of using topological sorts via graphing libs, but nothing in
terms of existing Go libs that deal with this specific problem domain at a
higher level. Even if a specific solution doesn't already exist, any
pointers or references to other projects would be really helpful.

-- justin

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Egon at Aug 7, 2014 at 5:16 am

    On Thursday, 7 August 2014 03:31:24 UTC+3, Justin Israel wrote:
    Are their any existing libraries that either directly, or are a good
    reference to, help solve the problem of resolving versioned package
    dependencies?

    There is a project I am spec'ing to rewrite in Go, that deals with
    resolving custom package dependencies with version ranges, and I'm
    wondering if there are any higher level solutions available? I've seen a
    couple of graphing libs out there, but I thought I might ask about this
    specific problem first, since I am not much of an algorithms genius and
    figured smarter people must have solved this before me.
    Yup, the answer is that, resolving dependencies is unsolvable in the
    general case (practice). Or if the modules are side effect free, then
    NP-Hard.

    In searching, I have come across terms like "constraint satisfaction", and
    suggestions of using topological sorts via graphing libs, but nothing in
    terms of existing Go libs that deal with this specific problem domain at a
    higher level. Even if a specific solution doesn't already exist, any
    pointers or references to other projects would be really helpful.
    How large dependencies are you thinking of? For what language? Which kinds
    of constraints the dependencies have additionally to version numbers?

    Bundler has some code for it:
    https://github.com/bundler/bundler/blob/master/lib/bundler/resolver.rb

    Also if you are looking for some more interesting approaches, then Cabal is
    probably a better reference:
    https://www.youtube.com/watch?v=yf412XHb5W0
    http://docis.info/docis/lib/goti/rclis/dbl/jfulop/(2001)11%253A5%253C557%253AMLSFCS%253E/www.cse.ogi.edu%252FPacSoft%252Fpublications%252Fphaseiiiq10papers%252Fmodular_lazy_search.pdf

    I guess you could also search how maven handles it.

    I also found AC-3 algorithm for constraint propagation:
    http://en.wikipedia.org/wiki/AC-3_algorithm

    + egon

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Egon at Aug 7, 2014 at 5:26 am

    On Thursday, 7 August 2014 08:16:39 UTC+3, egon wrote:

    On Thursday, 7 August 2014 03:31:24 UTC+3, Justin Israel wrote:

    Are their any existing libraries that either directly, or are a good
    reference to, help solve the problem of resolving versioned package
    dependencies?

    There is a project I am spec'ing to rewrite in Go, that deals with
    resolving custom package dependencies with version ranges, and I'm
    wondering if there are any higher level solutions available? I've seen a
    couple of graphing libs out there, but I thought I might ask about this
    specific problem first, since I am not much of an algorithms genius and
    figured smarter people must have solved this before me.
    Yup, the answer is that, resolving dependencies is unsolvable in the
    general case (practice). Or if the modules are side effect free, then
    NP-Hard.
    PS. read this
    https://groups.google.com/forum/#!topic/golang-nuts/sfshThQ_wrA

    In searching, I have come across terms like "constraint satisfaction", and
    suggestions of using topological sorts via graphing libs, but nothing in
    terms of existing Go libs that deal with this specific problem domain at a
    higher level. Even if a specific solution doesn't already exist, any
    pointers or references to other projects would be really helpful.
    How large dependencies are you thinking of? For what language? Which kinds
    of constraints the dependencies have additionally to version numbers?

    Bundler has some code for it:
    https://github.com/bundler/bundler/blob/master/lib/bundler/resolver.rb

    Also if you are looking for some more interesting approaches, then Cabal
    is probably a better reference:
    https://www.youtube.com/watch?v=yf412XHb5W0

    http://docis.info/docis/lib/goti/rclis/dbl/jfulop/(2001)11%253A5%253C557%253AMLSFCS%253E/www.cse.ogi.edu%252FPacSoft%252Fpublications%252Fphaseiiiq10papers%252Fmodular_lazy_search.pdf

    I guess you could also search how maven handles it.

    I also found AC-3 algorithm for constraint propagation:
    http://en.wikipedia.org/wiki/AC-3_algorithm

    + egon
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Justin Israel at Aug 7, 2014 at 8:34 am
    On Thu, Aug 7, 2014 at 5:26 PM, egon wrote:
    On Thursday, 7 August 2014 08:16:39 UTC+3, egon wrote:


    On Thursday, 7 August 2014 03:31:24 UTC+3, Justin Israel wrote:

    Are their any existing libraries that either directly, or are a good
    reference to, help solve the problem of resolving versioned package
    dependencies?

    There is a project I am spec'ing to rewrite in Go, that deals with
    resolving custom package dependencies with version ranges, and I'm
    wondering if there are any higher level solutions available? I've seen a
    couple of graphing libs out there, but I thought I might ask about this
    specific problem first, since I am not much of an algorithms genius and
    figured smarter people must have solved this before me.
    Yup, the answer is that, resolving dependencies is unsolvable in the
    general case (practice). Or if the modules are side effect free, then
    NP-Hard.
    PS. read this
    https://groups.google.com/forum/#!topic/golang-nuts/sfshThQ_wrA
    Yea, I can definitely understand how there is no way to provide a general
    solution, since there are different criteria for what is an "acceptable"
    resolution for different situations.

    From that link, this is most applicable: "Roughly that each package
    declares its version and the versions of all its needed dependencies.
    Circular incompatible transitive dependencies should fail."

    In searching, I have come across terms like "constraint satisfaction",
    and suggestions of using topological sorts via graphing libs, but nothing
    in terms of existing Go libs that deal with this specific problem domain at
    a higher level. Even if a specific solution doesn't already exist, any
    pointers or references to other projects would be really helpful.
    How large dependencies are you thinking of? For what language? Which
    kinds of constraints the dependencies have additionally to version numbers?
    I wouldn't say its language specific. These are generic "package
    descriptions" for an internal environment management system, that may only
    declare environment options such as locations to executables, and may or
    may not have ranged dependencies using semantic versioning (i.e. foobar
    1.0.0 - 1.2.3, or foobar 1.2.3 - *). Currently there could be as many as
    400 packages that have to be resolved together into versions (not all
    declare dependencies). But this would probably be reduced to less than 50
    max in the future implementation. Either they can resolve to a solution or
    they fail, and the package combinations are validated up front.

    Bundler has some code for it:
    https://github.com/bundler/bundler/blob/master/lib/bundler/resolver.rb

    Also if you are looking for some more interesting approaches, then Cabal
    is probably a better reference:
    https://www.youtube.com/watch?v=yf412XHb5W0
    http://docis.info/docis/lib/goti/rclis/dbl/jfulop/(2001)
    11%253A5%253C557%253AMLSFCS%253E/www.cse.ogi.edu%
    252FPacSoft%252Fpublications%252Fphaseiiiq10papers%
    252Fmodular_lazy_search.pdf

    I guess you could also search how maven handles it.

    I also found AC-3 algorithm for constraint propagation:
    http://en.wikipedia.org/wiki/AC-3_algorithm
    Got it. So the answer is that there isn't any real starting point from
    existing work already done in Go, since other solutions would most likely
    be too specific. I will research the bundler resolver and these other
    links. I guess I was just crossing my fingers that someone else had done
    some work with these resolvers / algorithms in Go already. Thanks!

    + egon
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Egon at Aug 7, 2014 at 8:52 am

    On Thursday, 7 August 2014 11:35:09 UTC+3, Justin Israel wrote:



    On Thu, Aug 7, 2014 at 5:26 PM, egon <egon...@gmail.com <javascript:>>
    wrote:
    On Thursday, 7 August 2014 08:16:39 UTC+3, egon wrote:


    On Thursday, 7 August 2014 03:31:24 UTC+3, Justin Israel wrote:

    Are their any existing libraries that either directly, or are a good
    reference to, help solve the problem of resolving versioned package
    dependencies?

    There is a project I am spec'ing to rewrite in Go, that deals with
    resolving custom package dependencies with version ranges, and I'm
    wondering if there are any higher level solutions available? I've seen a
    couple of graphing libs out there, but I thought I might ask about this
    specific problem first, since I am not much of an algorithms genius and
    figured smarter people must have solved this before me.
    Yup, the answer is that, resolving dependencies is unsolvable in the
    general case (practice). Or if the modules are side effect free, then
    NP-Hard.
    PS. read this
    https://groups.google.com/forum/#!topic/golang-nuts/sfshThQ_wrA
    Yea, I can definitely understand how there is no way to provide a general
    solution, since there are different criteria for what is an "acceptable"
    resolution for different situations.

    From that link, this is most applicable: "Roughly that each package
    declares its version and the versions of all its needed dependencies.
    Circular incompatible transitive dependencies should fail."

    In searching, I have come across terms like "constraint satisfaction",
    and suggestions of using topological sorts via graphing libs, but nothing
    in terms of existing Go libs that deal with this specific problem domain at
    a higher level. Even if a specific solution doesn't already exist, any
    pointers or references to other projects would be really helpful.
    How large dependencies are you thinking of? For what language? Which
    kinds of constraints the dependencies have additionally to version numbers?
    I wouldn't say its language specific. These are generic "package
    descriptions" for an internal environment management system, that may only
    declare environment options such as locations to executables, and may or
    may not have ranged dependencies using semantic versioning (i.e. foobar
    1.0.0 - 1.2.3, or foobar 1.2.3 - *). Currently there could be as many as
    400 packages that have to be resolved together into versions (not all
    declare dependencies). But this would probably be reduced to less than 50
    max in the future implementation. Either they can resolve to a solution or
    they fail, and the package combinations are validated up front.
    Then it might be doable with brute force, also set a time limit, e.g. if it
    doesn't complete in 10 minutes say the automatic resolution failed. Not
    sure how well it will work for your case, but it should be fairly easy to
    write and test. Of course this assumes you have a list of dependencies for
    each package version.

    Bundler has some code for it:
    https://github.com/bundler/bundler/blob/master/lib/bundler/resolver.rb

    Also if you are looking for some more interesting approaches, then Cabal
    is probably a better reference:
    https://www.youtube.com/watch?v=yf412XHb5W0
    http://docis.info/docis/lib/goti/rclis/dbl/jfulop/(2001)
    11%253A5%253C557%253AMLSFCS%253E/www.cse.ogi.edu%
    252FPacSoft%252Fpublications%252Fphaseiiiq10papers%
    252Fmodular_lazy_search.pdf

    I guess you could also search how maven handles it.

    I also found AC-3 algorithm for constraint propagation:
    http://en.wikipedia.org/wiki/AC-3_algorithm
    <http://www.google.com/url?q=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FAC-3_algorithm&sa=D&sntz=1&usg=AFQjCNH7OVa8aUT_Kl-hWpFQSRxII5vNwA>
    Got it. So the answer is that there isn't any real starting point
    At least I haven't noticed any on the forums.

    from existing work already done in Go, since other solutions would most
    likely be too specific. I will research the bundler resolver and these
    other links. I guess I was just crossing my fingers that someone else had
    done some work with these resolvers / algorithms in Go already. Thanks!

    + egon
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Justin Israel at Aug 22, 2014 at 8:35 pm
    Just as a follow up to this thread, after searching around and trying to
    gather info I read more on the world of SAT Solvers. I've started writing
    some code around the Go bindings to picosat <http://fmv.jku.at/picosat/> (
    PiGoSAT <https://github.com/wkschwartz/pigosat>), and it seems to be doing
    what I want so far. Once I modeled by data properly, I am seemingly able to
    resolve package dependencies with it.

    On Thu, Aug 7, 2014 at 8:50 PM, egon wrote:


    On Thursday, 7 August 2014 11:35:09 UTC+3, Justin Israel wrote:



    On Thu, Aug 7, 2014 at 5:26 PM, egon wrote:


    On Thursday, 7 August 2014 08:16:39 UTC+3, egon wrote:


    On Thursday, 7 August 2014 03:31:24 UTC+3, Justin Israel wrote:

    Are their any existing libraries that either directly, or are a good
    reference to, help solve the problem of resolving versioned package
    dependencies?

    There is a project I am spec'ing to rewrite in Go, that deals with
    resolving custom package dependencies with version ranges, and I'm
    wondering if there are any higher level solutions available? I've seen a
    couple of graphing libs out there, but I thought I might ask about this
    specific problem first, since I am not much of an algorithms genius and
    figured smarter people must have solved this before me.
    Yup, the answer is that, resolving dependencies is unsolvable in the
    general case (practice). Or if the modules are side effect free, then
    NP-Hard.
    PS. read this https://groups.google.com/forum/#!topic/golang-nuts/
    sfshThQ_wrA
    Yea, I can definitely understand how there is no way to provide a general
    solution, since there are different criteria for what is an "acceptable"
    resolution for different situations.

    From that link, this is most applicable: "Roughly that each package
    declares its version and the versions of all its needed dependencies.
    Circular incompatible transitive dependencies should fail."

    In searching, I have come across terms like "constraint satisfaction",
    and suggestions of using topological sorts via graphing libs, but nothing
    in terms of existing Go libs that deal with this specific problem domain at
    a higher level. Even if a specific solution doesn't already exist, any
    pointers or references to other projects would be really helpful.
    How large dependencies are you thinking of? For what language? Which
    kinds of constraints the dependencies have additionally to version numbers?
    I wouldn't say its language specific. These are generic "package
    descriptions" for an internal environment management system, that may only
    declare environment options such as locations to executables, and may or
    may not have ranged dependencies using semantic versioning (i.e. foobar
    1.0.0 - 1.2.3, or foobar 1.2.3 - *). Currently there could be as many as
    400 packages that have to be resolved together into versions (not all
    declare dependencies). But this would probably be reduced to less than 50
    max in the future implementation. Either they can resolve to a solution or
    they fail, and the package combinations are validated up front.
    Then it might be doable with brute force, also set a time limit, e.g. if
    it doesn't complete in 10 minutes say the automatic resolution failed. Not
    sure how well it will work for your case, but it should be fairly easy to
    write and test. Of course this assumes you have a list of dependencies for
    each package version.

    Bundler has some code for it:
    https://github.com/bundler/bundler/blob/master/lib/bundler/resolver.rb

    Also if you are looking for some more interesting approaches, then
    Cabal is probably a better reference:
    https://www.youtube.com/watch?v=yf412XHb5W0
    http://docis.info/docis/lib/goti/rclis/dbl/jfulop/(2001)11%
    253A5%253C557%253AMLSFCS%253E/www.cse.ogi.edu%252FPacSoft%
    252Fpublications%252Fphaseiiiq10papers%252Fmodular_lazy_search.pdf

    I guess you could also search how maven handles it.

    I also found AC-3 algorithm for constraint propagation:
    http://en.wikipedia.org/wiki/AC-3_algorithm
    <http://www.google.com/url?q=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FAC-3_algorithm&sa=D&sntz=1&usg=AFQjCNH7OVa8aUT_Kl-hWpFQSRxII5vNwA>
    Got it. So the answer is that there isn't any real starting point
    At least I haven't noticed any on the forums.

    from existing work already done in Go, since other solutions would most
    likely be too specific. I will research the bundler resolver and these
    other links. I guess I was just crossing my fingers that someone else had
    done some work with these resolvers / algorithms in Go already. Thanks!

    + egon
    --
    You received this message because you are subscribed to the Google
    Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an email to golang-nuts...@googlegroups.com.

    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedAug 7, '14 at 12:31a
activeAug 22, '14 at 8:35p
posts6
users2
websitegolang.org

2 users in discussion

Justin Israel: 3 posts Egon: 3 posts

People

Translate

site design / logo © 2022 Grokbase