From ec841971e5496ebbf56813f985de492bcd2c725f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Johannes=20M=C3=BCller?= Date: Mon, 3 Feb 2025 15:16:18 +0100 Subject: [PATCH 1/7] Fix make touch `shard.lock` when `SHARDS=false` (#667) --- Makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/Makefile b/Makefile index 5c9793f4..48c74472 100644 --- a/Makefile +++ b/Makefile @@ -109,7 +109,7 @@ lib: shard.lock $(SHARDS) install || (curl -L $(MOLINILLO_URL) | tar -xzf - -C lib/molinillo --strip-components=1) shard.lock: shard.yml - [ $(SHARDS) = false ] || $(SHARDS) update + ([ $(SHARDS) = false ] && touch $@) || $(SHARDS) update man/%.gz: man/% gzip -c -9 $< > $@ From c3831a9fb7d9bf4e9462bc473ec1dafc5611c49a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Johannes=20M=C3=BCller?= Date: Wed, 12 Feb 2025 16:52:50 +0100 Subject: [PATCH 2/7] Add make recipe `install_dlls` (#668) Adapted from crystal's Makefile: https://github.com/crystal-lang/crystal/blob/0da17469fe1d3ea0078585707db8809722813aec/Makefile#L186-L191 --- Makefile | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/Makefile b/Makefile index 48c74472..5092b20b 100644 --- a/Makefile +++ b/Makefile @@ -83,6 +83,13 @@ install: bin/shards$(EXE) man/shards.1.gz man/shard.yml.5.gz $(INSTALL) -m 0644 man/shards.1.gz "$(MANDIR)/man1" $(INSTALL) -m 0644 man/shard.yml.5.gz "$(MANDIR)/man5" +ifeq ($(WINDOWS),1) +.PHONY: install_dlls +install_dlls: bin/shards$(EXE) ## Install the dependent DLLs at DESTDIR (Windows only) + $(INSTALL) -d -m 0755 "$(BINDIR)/" + @ldd bin/shards$(EXE) | grep -iv ' => /c/windows/system32' | sed 's/.* => //; s/ (.*//' | xargs -t -i $(INSTALL) -m 0755 '{}' "$(BINDIR)/" +endif + .PHONY: uninstall uninstall: ## Uninstall shards uninstall: From cccd47a4eb87d87fa65df96ae8f549ac64592a65 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Johannes=20M=C3=BCller?= Date: Thu, 13 Feb 2025 10:00:51 +0100 Subject: [PATCH 3/7] Expand `DESTDIR` outside of prefixed dir variables (#669) Per convention, `DESTDIR` should only be expanded directly in the install/uninstall targets, not prefixed into the directory variables. --- Makefile | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/Makefile b/Makefile index 5092b20b..1f08f0ce 100644 --- a/Makefile +++ b/Makefile @@ -42,8 +42,8 @@ SHARDS_CONFIG_BUILD_COMMIT := $(shell git rev-parse --short HEAD 2> /dev/null) SHARDS_VERSION := $(shell cat VERSION) SOURCE_DATE_EPOCH := $(shell (git show -s --format=%ct HEAD || stat -c "%Y" Makefile || stat -f "%m" Makefile) 2> /dev/null) EXPORTS := SHARDS_CONFIG_BUILD_COMMIT="$(SHARDS_CONFIG_BUILD_COMMIT)" SOURCE_DATE_EPOCH="$(SOURCE_DATE_EPOCH)" -BINDIR ?= $(DESTDIR)$(PREFIX)/bin -MANDIR ?= $(DESTDIR)$(PREFIX)/share/man +BINDIR ?= $(PREFIX)/bin +MANDIR ?= $(PREFIX)/share/man INSTALL ?= /usr/bin/install MOLINILLO_VERSION = $(shell $(CRYSTAL) eval 'require "yaml"; puts YAML.parse(File.read("shard.lock"))["shards"]["molinillo"]["version"]') @@ -78,10 +78,10 @@ bin/shards$(EXE): $(SOURCES) $(TEMPLATES) lib .PHONY: install install: ## Install shards install: bin/shards$(EXE) man/shards.1.gz man/shard.yml.5.gz - $(INSTALL) -m 0755 -d "$(BINDIR)" "$(MANDIR)/man1" "$(MANDIR)/man5" - $(INSTALL) -m 0755 bin/shards$(EXE) "$(BINDIR)" - $(INSTALL) -m 0644 man/shards.1.gz "$(MANDIR)/man1" - $(INSTALL) -m 0644 man/shard.yml.5.gz "$(MANDIR)/man5" + $(INSTALL) -m 0755 -d "$(DESTDIR)$(BINDIR)" "$(DESTDIR)$(MANDIR)/man1" "$(DESTDIR)$(MANDIR)/man5" + $(INSTALL) -m 0755 bin/shards$(EXE) "$(DESTDIR)$(BINDIR)" + $(INSTALL) -m 0644 man/shards.1.gz "$(DESTDIR)$(MANDIR)/man1" + $(INSTALL) -m 0644 man/shard.yml.5.gz "$(DESTDIR)$(MANDIR)/man5" ifeq ($(WINDOWS),1) .PHONY: install_dlls @@ -93,9 +93,9 @@ endif .PHONY: uninstall uninstall: ## Uninstall shards uninstall: - rm -f "$(BINDIR)/shards" - rm -f "$(MANDIR)/man1/shards.1.gz" - rm -f "$(MANDIR)/man5/shard.yml.5.gz" + rm -f "$(DESTDIR)$(BINDIR)/shards" + rm -f "$(DESTDIR)$(MANDIR)/man1/shards.1.gz" + rm -f "$(DESTDIR)$(MANDIR)/man5/shard.yml.5.gz" .PHONY: test test: ## Run all tests From 02ff388c5761199da7e8a563c5a8258275e54abc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Johannes=20M=C3=BCller?= Date: Sat, 22 Feb 2025 14:43:10 +0100 Subject: [PATCH 4/7] Vendor `lib/molinillo` (#663) Commits the dependency code into this repository, as suggested in https://github.com/crystal-lang/crystal/pull/15344#issuecomment-2592886590. We're already doing the same in https://github.com/crystal-lang/crystal. This simplifies the build process. All code required for building shards is contained in this repository (except for Crystal stdlib). There's no need to bootstrap the initial installation of the molinillo dependency anymore. --- .gitignore | 1 - Makefile | 14 +- Makefile.win | 13 +- README.md | 11 +- lib/.shards.info | 6 + lib/molinillo/.editorconfig | 9 + lib/molinillo/.github/workflows/crystal.yml | 18 + lib/molinillo/.gitignore | 9 + lib/molinillo/.gitmodules | 3 + lib/molinillo/.travis.yml | 6 + lib/molinillo/LICENSE | 22 + lib/molinillo/README.md | 43 + lib/molinillo/lib | 1 + lib/molinillo/shard.yml | 9 + .../spec/dependency_graph/log_spec.cr | 38 + lib/molinillo/spec/dependency_graph_spec.cr | 76 ++ lib/molinillo/spec/resolver_spec.cr | 115 +++ lib/molinillo/spec/spec_helper.cr | 5 + lib/molinillo/spec/spec_helper/fixture.cr | 20 + lib/molinillo/spec/spec_helper/gem.cr | 41 + lib/molinillo/spec/spec_helper/index.cr | 64 ++ .../spec/spec_helper/specification.cr | 44 + lib/molinillo/spec/spec_helper/ui.cr | 15 + lib/molinillo/spec/spec_helper/versions.cr | 232 +++++ lib/molinillo/spec/state_spec.cr | 29 + lib/molinillo/src/molinillo.cr | 5 + .../molinillo/delegates/resolution_state.cr | 55 ++ .../delegates/specification_provider.cr | 78 ++ .../src/molinillo/dependency_graph.cr | 190 ++++ .../src/molinillo/dependency_graph/action.cr | 21 + .../dependency_graph/add_edge_no_circular.cr | 36 + .../molinillo/dependency_graph/add_vertex.cr | 35 + .../molinillo/dependency_graph/delete_edge.cr | 33 + .../dependency_graph/detach_vertex_named.cr | 42 + .../src/molinillo/dependency_graph/log.cr | 85 ++ .../molinillo/dependency_graph/set_payload.cr | 22 + .../src/molinillo/dependency_graph/tag.cr | 42 + .../src/molinillo/dependency_graph/vertex.cr | 58 ++ lib/molinillo/src/molinillo/errors.cr | 142 +++ .../modules/specification_provider.cr | 99 ++ lib/molinillo/src/molinillo/modules/ui.cr | 71 ++ lib/molinillo/src/molinillo/resolution.cr | 857 ++++++++++++++++++ lib/molinillo/src/molinillo/resolver.cr | 41 + lib/molinillo/src/molinillo/state.cr | 64 ++ 44 files changed, 2785 insertions(+), 35 deletions(-) create mode 100644 lib/.shards.info create mode 100644 lib/molinillo/.editorconfig create mode 100644 lib/molinillo/.github/workflows/crystal.yml create mode 100644 lib/molinillo/.gitignore create mode 100644 lib/molinillo/.gitmodules create mode 100644 lib/molinillo/.travis.yml create mode 100644 lib/molinillo/LICENSE create mode 100644 lib/molinillo/README.md create mode 120000 lib/molinillo/lib create mode 100644 lib/molinillo/shard.yml create mode 100644 lib/molinillo/spec/dependency_graph/log_spec.cr create mode 100644 lib/molinillo/spec/dependency_graph_spec.cr create mode 100644 lib/molinillo/spec/resolver_spec.cr create mode 100644 lib/molinillo/spec/spec_helper.cr create mode 100644 lib/molinillo/spec/spec_helper/fixture.cr create mode 100644 lib/molinillo/spec/spec_helper/gem.cr create mode 100644 lib/molinillo/spec/spec_helper/index.cr create mode 100644 lib/molinillo/spec/spec_helper/specification.cr create mode 100644 lib/molinillo/spec/spec_helper/ui.cr create mode 100644 lib/molinillo/spec/spec_helper/versions.cr create mode 100644 lib/molinillo/spec/state_spec.cr create mode 100644 lib/molinillo/src/molinillo.cr create mode 100644 lib/molinillo/src/molinillo/delegates/resolution_state.cr create mode 100644 lib/molinillo/src/molinillo/delegates/specification_provider.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/action.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/add_edge_no_circular.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/add_vertex.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/delete_edge.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/detach_vertex_named.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/log.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/set_payload.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/tag.cr create mode 100644 lib/molinillo/src/molinillo/dependency_graph/vertex.cr create mode 100644 lib/molinillo/src/molinillo/errors.cr create mode 100644 lib/molinillo/src/molinillo/modules/specification_provider.cr create mode 100644 lib/molinillo/src/molinillo/modules/ui.cr create mode 100644 lib/molinillo/src/molinillo/resolution.cr create mode 100644 lib/molinillo/src/molinillo/resolver.cr create mode 100644 lib/molinillo/src/molinillo/state.cr diff --git a/.gitignore b/.gitignore index e50b04af..8e4ba06b 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,5 @@ /.crystal /.shards -/lib /bin/shards /bin/shards.dwarf /bin/shards.exe diff --git a/Makefile b/Makefile index 1f08f0ce..e072fcff 100644 --- a/Makefile +++ b/Makefile @@ -46,9 +46,6 @@ BINDIR ?= $(PREFIX)/bin MANDIR ?= $(PREFIX)/share/man INSTALL ?= /usr/bin/install -MOLINILLO_VERSION = $(shell $(CRYSTAL) eval 'require "yaml"; puts YAML.parse(File.read("shard.lock"))["shards"]["molinillo"]["version"]') -MOLINILLO_URL = "https://github.com/crystal-lang/crystal-molinillo/archive/v$(MOLINILLO_VERSION).tar.gz" - # MSYS2 support (native Windows should use `Makefile.win` instead) ifeq ($(OS),Windows_NT) EXE := .exe @@ -71,7 +68,7 @@ clean: ## Remove build artifacts clean: clean_docs rm -f bin/shards$(EXE) -bin/shards$(EXE): $(SOURCES) $(TEMPLATES) lib +bin/shards$(EXE): $(SOURCES) $(TEMPLATES) @mkdir -p bin $(EXPORTS) $(CRYSTAL) build $(FLAGS) src/shards.cr -o "$@" @@ -103,7 +100,7 @@ test: test_unit test_integration .PHONY: test_unit test_unit: ## Run unit tests -test_unit: lib +test_unit: $(CRYSTAL) spec ./spec/unit/ $(if $(skip_fossil),--tag ~fossil) $(if $(skip_git),--tag ~git) $(if $(skip_hg),--tag ~hg) .PHONY: test_integration @@ -111,13 +108,6 @@ test_integration: ## Run integration tests test_integration: bin/shards$(EXE) $(CRYSTAL) spec ./spec/integration/ -lib: shard.lock - mkdir -p lib/molinillo - $(SHARDS) install || (curl -L $(MOLINILLO_URL) | tar -xzf - -C lib/molinillo --strip-components=1) - -shard.lock: shard.yml - ([ $(SHARDS) = false ] && touch $@) || $(SHARDS) update - man/%.gz: man/% gzip -c -9 $< > $@ diff --git a/Makefile.win b/Makefile.win index f5900d11..b737ec30 100644 --- a/Makefile.win +++ b/Makefile.win @@ -48,9 +48,6 @@ SHARDS_CONFIG_BUILD_COMMIT := $(shell git rev-parse --short HEAD) SOURCE_DATE_EPOCH := $(shell git show -s --format=%ct HEAD) export_vars = $(eval export SHARDS_CONFIG_BUILD_COMMIT SOURCE_DATE_EPOCH) -MOLINILLO_VERSION = $(shell $(CRYSTAL) eval 'require "yaml"; puts YAML.parse(File.read("shard.lock"))["shards"]["molinillo"]["version"]') -MOLINILLO_URL = "https://github.com/crystal-lang/crystal-molinillo/archive/v$(MOLINILLO_VERSION).tar.gz" - prefix ?= $(or $(ProgramW6432),$(ProgramFiles))\crystal## Install path prefix BINDIR ?= $(prefix) @@ -65,7 +62,7 @@ clean: ## Remove build artifacts clean: $(call RM,"bin\shards.exe") -bin\shards.exe: $(SOURCES) $(TEMPLATES) lib +bin\shards.exe: $(SOURCES) $(TEMPLATES) @$(call MKDIR,"bin") $(call export_vars) $(CRYSTAL) build $(FLAGS) -o bin\shards.exe src\shards.cr @@ -89,7 +86,6 @@ test: test_unit test_integration .PHONY: test_unit test_unit: ## Run unit tests -test_unit: lib $(CRYSTAL) spec $(if $(skip_fossil),--tag ~fossil )$(if $(skip_git),--tag ~git )$(if $(skip_hg),--tag ~hg ).\spec\unit .PHONY: test_integration @@ -97,13 +93,6 @@ test_integration: ## Run integration tests test_integration: bin\shards.exe $(CRYSTAL) spec .\spec\integration -lib: shard.lock - $(call MKDIR,"lib\molinillo") - $(SHARDS) install || (curl -L $(MOLINILLO_URL) | tar -xzf - -C lib\molinillo --strip-components=1) - -shard.lock: shard.yml - if not "$(SHARDS)" == "false" $(SHARDS) update - .PHONY: help help: ## Show this help @setlocal EnableDelayedExpansion &\ diff --git a/README.md b/README.md index 5a05c30a..385c1e71 100644 --- a/README.md +++ b/README.md @@ -67,13 +67,6 @@ These requirements are only necessary for compiling Shards. Please refer to for instructions for your operating system. -* `molinillo` - - The shard `molinillo` needs to be in the Crystal path. - It is available at - You can install it either with a pre-existing `shards` binary (running `shards install`) - or just check out the repository at `lib/crystal-molinillo` (`make lib`). - * libyaml On Debian/Ubuntu Linux you may install the `libyaml-dev` package. @@ -90,9 +83,7 @@ These requirements are only necessary for compiling Shards. ### Getting started It is strongly recommended to use `make` for building shards and developing it. -The [`Makefile`](./Makefile) contains recipes for compiling and testing. Building -with `make` also ensures the source dependency `molinillo` is installed. You don't -need to take care of this yourself. +The [`Makefile`](./Makefile) contains recipes for compiling and testing. Run `make bin/shards` to build the binary. * `release=1` for a release build (applies optimizations) diff --git a/lib/.shards.info b/lib/.shards.info new file mode 100644 index 00000000..c0d0af75 --- /dev/null +++ b/lib/.shards.info @@ -0,0 +1,6 @@ +--- +version: 1.0 +shards: + molinillo: + git: https://github.com/crystal-lang/crystal-molinillo.git + version: 0.2.0 diff --git a/lib/molinillo/.editorconfig b/lib/molinillo/.editorconfig new file mode 100644 index 00000000..163eb75c --- /dev/null +++ b/lib/molinillo/.editorconfig @@ -0,0 +1,9 @@ +root = true + +[*.cr] +charset = utf-8 +end_of_line = lf +insert_final_newline = true +indent_style = space +indent_size = 2 +trim_trailing_whitespace = true diff --git a/lib/molinillo/.github/workflows/crystal.yml b/lib/molinillo/.github/workflows/crystal.yml new file mode 100644 index 00000000..49c8d4f6 --- /dev/null +++ b/lib/molinillo/.github/workflows/crystal.yml @@ -0,0 +1,18 @@ +name: Crystal CI + +on: [push] + +jobs: + build: + + runs-on: ubuntu-latest + + container: + image: crystallang/crystal + + steps: + - uses: actions/checkout@v2 + - name: Install dependencies + run: shards install + - name: Run tests + run: crystal spec diff --git a/lib/molinillo/.gitignore b/lib/molinillo/.gitignore new file mode 100644 index 00000000..0bbd4a9f --- /dev/null +++ b/lib/molinillo/.gitignore @@ -0,0 +1,9 @@ +/docs/ +/lib/ +/bin/ +/.shards/ +*.dwarf + +# Libraries don't need dependency lock +# Dependencies will be locked in applications that use them +/shard.lock diff --git a/lib/molinillo/.gitmodules b/lib/molinillo/.gitmodules new file mode 100644 index 00000000..39c50c56 --- /dev/null +++ b/lib/molinillo/.gitmodules @@ -0,0 +1,3 @@ +[submodule "spec/fixture"] + path = spec/fixture + url = https://github.com/CocoaPods/Resolver-Integration-Specs diff --git a/lib/molinillo/.travis.yml b/lib/molinillo/.travis.yml new file mode 100644 index 00000000..765f0e9c --- /dev/null +++ b/lib/molinillo/.travis.yml @@ -0,0 +1,6 @@ +language: crystal + +# Uncomment the following if you'd like Travis to run specs and check code formatting +# script: +# - crystal spec +# - crystal tool format --check diff --git a/lib/molinillo/LICENSE b/lib/molinillo/LICENSE new file mode 100644 index 00000000..b977a143 --- /dev/null +++ b/lib/molinillo/LICENSE @@ -0,0 +1,22 @@ +This project is licensed under the MIT license. + +Copyright (c) 2020 Manas Technology Solutions +Copyright (c) 2014 Samuel E. Giddins segiddins@segiddins.me + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/lib/molinillo/README.md b/lib/molinillo/README.md new file mode 100644 index 00000000..8e09c51e --- /dev/null +++ b/lib/molinillo/README.md @@ -0,0 +1,43 @@ +# crystal-molinillo + +A port of [Molinillo](https://github.com/CocoaPods/Molinillo/) (generic dependency resolution algorithm) to [Crystal](https://crystal-lang.org) + +## Installation + +1. Add the dependency to your `shard.yml`: + + ```yaml + dependencies: + molinillo: + github: crystal-lang/crystal-molinillo + ``` + +2. Run `shards install` + +## Usage + +```crystal +require "molinillo" +``` + +This was built to be used by [Shards](https://github.com/crystal-lang/shards). Check [`MolinilloSolver`](https://github.com/crystal-lang/shards/blob/master/src/molinillo_solver.cr) for an example of integration. + +## Development + +This code uses a subrepository with test fixtures. Make sure you clone the repository with `--recursive` before running tests: + +``` +git clone --recursive https://github.com/crystal-lang/crystal-molinillo +``` + +## Contributing + +1. Fork it () +2. Create your feature branch (`git checkout -b my-new-feature`) +3. Commit your changes (`git commit -am 'Add some feature'`) +4. Push to the branch (`git push origin my-new-feature`) +5. Create a new Pull Request + +## Contributors + +- [Juan Wajnerman](https://github.com/waj) - creator and maintainer diff --git a/lib/molinillo/lib b/lib/molinillo/lib new file mode 120000 index 00000000..a96aa0ea --- /dev/null +++ b/lib/molinillo/lib @@ -0,0 +1 @@ +.. \ No newline at end of file diff --git a/lib/molinillo/shard.yml b/lib/molinillo/shard.yml new file mode 100644 index 00000000..11b09219 --- /dev/null +++ b/lib/molinillo/shard.yml @@ -0,0 +1,9 @@ +name: molinillo +version: 0.2.0 + +authors: + - Juan Wajnerman + +crystal: ">= 0.35.0, < 2.0.0" + +license: MIT diff --git a/lib/molinillo/spec/dependency_graph/log_spec.cr b/lib/molinillo/spec/dependency_graph/log_spec.cr new file mode 100644 index 00000000..0f102df8 --- /dev/null +++ b/lib/molinillo/spec/dependency_graph/log_spec.cr @@ -0,0 +1,38 @@ +# frozen_string_literal: true + +require "../spec_helper" + +alias DG = Molinillo::DependencyGraph(Int32, Int32) + +def shared_examples_for_replay(prepare) + it "replays the log" do + copy = DG.new + graph = DG.new.tap { |g| prepare.call(g) } + graph.log.each &.up(copy) + copy.should eq(graph) + end + + it "can undo to an empty graph" do + graph = DG.new + tag = Reference.new + graph.tag(tag) + prepare.call(graph) + graph.rewind_to(tag) + graph.should eq(DG.new) + end +end + +describe Molinillo::DependencyGraph::Log do + describe "with empty log" do + shared_examples_for_replay ->(g : DG) {} + end + + describe "with some graph" do + shared_examples_for_replay ->(g : DG) do + g.add_child_vertex("Foo", 1, [nil] of String?, 4) + g.add_child_vertex("Bar", 2, ["Foo", nil], 3) + g.add_child_vertex("Baz", 3, %w(Foo Bar), 2) + g.add_child_vertex("Foo", 4, [] of String?, 1) + end + end +end diff --git a/lib/molinillo/spec/dependency_graph_spec.cr b/lib/molinillo/spec/dependency_graph_spec.cr new file mode 100644 index 00000000..1bb871b8 --- /dev/null +++ b/lib/molinillo/spec/dependency_graph_spec.cr @@ -0,0 +1,76 @@ +require "./spec_helper" + +private def test_dependency_graph + graph = Molinillo::DependencyGraph(String, String).new + root = graph.add_vertex("Root", "Root", true) + root2 = graph.add_vertex("Root2", "Root2", true) + child = graph.add_child_vertex("Child", "Child", %w(Root), "Child") + {graph: graph, root: root, root2: root2, child: child} +end + +describe Molinillo::DependencyGraph do + describe "in general" do + it "returns root vertices by name" do + data = test_dependency_graph + data[:graph].root_vertex_named("Root").should eq(data[:root]) + end + + it "returns vertices by name" do + data = test_dependency_graph + data[:graph].vertex_named("Root").should eq(data[:root]) + data[:graph].vertex_named("Child").should eq(data[:child]) + end + + it "returns nil for non-existent root vertices" do + data = test_dependency_graph + data[:graph].root_vertex_named("missing").should be_nil + end + + it "returns nil for non-existent vertices" do + data = test_dependency_graph + data[:graph].vertex_named("missing").should be_nil + end + end + + describe "detaching a vertex" do + it "detaches a root vertex without successors" do + graph = Molinillo::DependencyGraph(String, String).new + root = graph.add_vertex("root", "root", true) + graph.detach_vertex_named(root.name) + graph.vertex_named(root.name).should be_nil + graph.vertices.should be_empty + end + + it "detaches a root vertex with successors" do + graph = Molinillo::DependencyGraph(String, String).new + root = graph.add_vertex("root", "root", true) + child = graph.add_child_vertex("child", "child", %w(root), "child") + graph.detach_vertex_named(root.name) + graph.vertex_named(root.name).should be_nil + graph.vertex_named(child.name).should be_nil + graph.vertices.should be_empty + end + + it "detaches a root vertex with successors with other parents" do + graph = Molinillo::DependencyGraph(String, String).new + root = graph.add_vertex("root", "root", true) + root2 = graph.add_vertex("root2", "root2", true) + child = graph.add_child_vertex("child", "child", %w(root root2), "child") + graph.detach_vertex_named(root.name) + graph.vertex_named(root.name).should be_nil + graph.vertex_named(child.name).should eq(child) + child.predecessors.should eq([root2]) + graph.vertices.size.should eq(2) + end + + it "detaches a vertex with predecessors" do + graph = Molinillo::DependencyGraph(String, String).new + parent = graph.add_vertex("parent", "parent", true) + child = graph.add_child_vertex("child", "child", %w(parent), "child") + graph.detach_vertex_named(child.name) + graph.vertex_named(child.name).should be_nil + graph.vertices.should eq({parent.name => parent}) + parent.outgoing_edges.should be_empty + end + end +end diff --git a/lib/molinillo/spec/resolver_spec.cr b/lib/molinillo/spec/resolver_spec.cr new file mode 100644 index 00000000..7c5a5fd0 --- /dev/null +++ b/lib/molinillo/spec/resolver_spec.cr @@ -0,0 +1,115 @@ +require "./spec_helper" + +module Molinillo + FIXTURE_CASE_DIR = FIXTURE_DIR / "case" + + class TestCase + getter fixture : Fixture + getter name : String + @index : SpecificationProvider(Gem::Dependency | TestSpecification, TestSpecification)? + @requested : Array(Gem::Dependency | TestSpecification)? + @result : DependencyGraph(TestSpecification?, TestSpecification?)? + @conflicts : Set(String)? + @@all : Array(TestCase)? + + def self.from_fixture(fixture_path) + fixture = File.open(fixture_path) { |f| Fixture.from_json(f) } + new(fixture) + end + + def initialize(@fixture) + @name = fixture.name + end + + def index + @index ||= TestIndex.from_fixture(@fixture.index || "awesome") + end + + def requested + @requested ||= @fixture.requested.map do |(name, reqs)| + Gem::Dependency.new(name.delete("\x01"), reqs.split(',').map(&.chomp)).as(Gem::Dependency | TestSpecification) + end + end + + def add_dependencies_to_graph(graph : DependencyGraph(P, P), parent, hash, all_parents = Set(DependencyGraph::Vertex(P, P)).new) forall P + name = hash.name + version = hash.version # Gem::Version.new(hash['version']) + dependency = index.specs[name].find { |s| Shards::Versions.compare(s.version, version) == 0 }.not_nil! + vertex = if parent + graph.add_vertex(name, dependency).tap do |v| + graph.add_edge(parent, v, dependency) + end + else + graph.add_vertex(name, dependency, true) + end + return unless all_parents.add?(vertex) + hash.dependencies.each do |dep| + add_dependencies_to_graph(graph, vertex, dep, all_parents) + end + end + + def result + @result ||= @fixture.resolved.reduce(DependencyGraph(TestSpecification?, TestSpecification?).new) do |graph, r| + graph.tap do |g| + add_dependencies_to_graph(g, nil, r) + end + end + end + + def base + @fixture.base.reduce(DependencyGraph(Gem::Dependency | TestSpecification, Gem::Dependency | TestSpecification).new) do |graph, r| + graph.tap do |g| + add_dependencies_to_graph(g, nil, r) + end + end + end + + def conflicts + @conflicts ||= @fixture.conflicts.to_set + end + + def self.all + @@all ||= Dir.glob(FIXTURE_CASE_DIR.to_s + "**/*.json").map { |fixture| TestCase.from_fixture(fixture) } + end + + def resolve(index_class) + index = index_class.new(self.index.specs) + resolver = Resolver(Gem::Dependency | TestSpecification, TestSpecification).new(index, TestUI.new) + resolver.resolve(requested, base) + end + + def run(index_class) + it name do + # skip 'does not yet reliably pass' if test_case.ignore?(index_class) + if fixture.conflicts.any? + error = expect_raises(ResolverError) { resolve(index_class) } + names = case error + when CircularDependencyError + error.vertices.map &.name + when VersionConflict + error.conflicts.keys + else + fail "Unexpected error type: #{error}" + end.to_set + names.should eq(self.conflicts) + else + result = resolve(index_class) + + result.should eq(self.result) + end + end + end + end + + describe Resolver do + describe "dependency resolution" do + describe "with the TestIndex index" do + TestCase.all.each &.run(TestIndex) + end + end + end +end + +# it "list all cases" do +# pp Molinillo::TestCase.all +# end diff --git a/lib/molinillo/spec/spec_helper.cr b/lib/molinillo/spec/spec_helper.cr new file mode 100644 index 00000000..3fd05991 --- /dev/null +++ b/lib/molinillo/spec/spec_helper.cr @@ -0,0 +1,5 @@ +require "spec" +require "../src/molinillo" +require "./spec_helper/*" + +FIXTURE_DIR = Path.new("spec/fixture") diff --git a/lib/molinillo/spec/spec_helper/fixture.cr b/lib/molinillo/spec/spec_helper/fixture.cr new file mode 100644 index 00000000..364f85a3 --- /dev/null +++ b/lib/molinillo/spec/spec_helper/fixture.cr @@ -0,0 +1,20 @@ +require "json" + +class Molinillo::Fixture + include JSON::Serializable + + property name : String + property index : String? + property requested : Hash(String, String) + property base : Array(Dependency) + property resolved : Array(Dependency) + property conflicts : Array(String) +end + +class Molinillo::Fixture::Dependency + include JSON::Serializable + + property name : String + property version : String + property dependencies : Array(Dependency) +end diff --git a/lib/molinillo/spec/spec_helper/gem.cr b/lib/molinillo/spec/spec_helper/gem.cr new file mode 100644 index 00000000..3bee2ecd --- /dev/null +++ b/lib/molinillo/spec/spec_helper/gem.cr @@ -0,0 +1,41 @@ +module Gem + class Dependency + property name : String + property requirement : Requirement + + def initialize(@name, requirements : Array(String)) + @requirement = Requirement.new(requirements) + end + + def prerelease? + requirement.prerelease? + end + + def to_s(io) + io << name + end + end + + class Requirement + property requirements : Array(String) + + def initialize(@requirements) + end + + def satisfied_by?(version : String) + requirements.all? do |req| + Shards::Versions.matches?(version, req) + end + end + + def prerelease? + requirements.any? { |r| Shards::Versions.prerelease?(r) } + end + + def inspect(io) + io << '"' + io << requirements.join ", " + io << '"' + end + end +end diff --git a/lib/molinillo/spec/spec_helper/index.cr b/lib/molinillo/spec/spec_helper/index.cr new file mode 100644 index 00000000..bdd827e0 --- /dev/null +++ b/lib/molinillo/spec/spec_helper/index.cr @@ -0,0 +1,64 @@ +require "./specification" + +module Molinillo + FIXTURE_INDEX_DIR = FIXTURE_DIR / "index" + + class TestIndex + getter specs : Hash(String, Array(TestSpecification)) + include SpecificationProvider(Gem::Dependency | TestSpecification, TestSpecification) + + def self.from_fixture(fixture_name) + new(TestIndex.specs_from_fixture(fixture_name)) + end + + @@specs_from_fixture = {} of String => Hash(String, Array(TestSpecification)) + + def self.specs_from_fixture(fixture_name) + @@specs_from_fixture[fixture_name] ||= begin + lines = File.read_lines(FIXTURE_INDEX_DIR / (fixture_name + ".json")) + lines = lines.map { |line| line.partition("//")[0] } + Hash(String, Array(TestSpecification)).from_json(lines.join '\n').tap do |all_specs| + all_specs.each do |name, specs| + specs.sort! { |a, b| Shards::Versions.compare(b.version, a.version) } + end + end + end + end + + def initialize(@specs) + end + + def requirement_satisfied_by?(requirement, activated, spec) + if Shards::Versions.prerelease?(spec.version) && !requirement.prerelease? + vertex = activated.vertex_named!(spec.name) + return false if vertex.requirements.none?(&.prerelease?) + end + + case requirement + when TestSpecification + requirement.version == spec.version + when Gem::Dependency + requirement.requirement.satisfied_by?(spec.version) + end + end + + def search_for(dependency : R) + case dependency + when Gem::Dependency + specs.fetch(dependency.name) { Array(TestSpecification).new }.select do |spec| + dependency.requirement.satisfied_by?(spec.version) + end + else + raise "BUG: Unexpected dependency type: #{dependency}" + end + end + + def name_for(dependency) + dependency.name + end + + def dependencies_for(specification : S) + specification.dependencies + end + end +end diff --git a/lib/molinillo/spec/spec_helper/specification.cr b/lib/molinillo/spec/spec_helper/specification.cr new file mode 100644 index 00000000..b2e6b195 --- /dev/null +++ b/lib/molinillo/spec/spec_helper/specification.cr @@ -0,0 +1,44 @@ +require "json" + +module Molinillo + class TestSpecification + include JSON::Serializable + + property name : String + property version : String + @[JSON::Field(converter: Molinillo::DepConverter)] + property dependencies : Array(Gem::Dependency | TestSpecification) + + def to_s(io) + io << "#{name} (#{version})" + end + + def prerelease? + Shards::Versions.prerelease?(version) + end + end + + module DepConverter + def self.from_json(parser) + deps = + if parser.kind.begin_object? + Hash(String, String).new(parser) + else + Hash(String, String).new.tap do |deps| + parser.read_array do + parser.read_begin_array + key = parser.read_string + value = parser.read_string + parser.read_end_array + deps[key] = value + end + end + end + + deps.map do |name, requirement| + requirements = requirement.split(',').map(&.chomp) + Gem::Dependency.new(name, requirements).as(Gem::Dependency | TestSpecification) + end + end + end +end diff --git a/lib/molinillo/spec/spec_helper/ui.cr b/lib/molinillo/spec/spec_helper/ui.cr new file mode 100644 index 00000000..4ca1bcfd --- /dev/null +++ b/lib/molinillo/spec/spec_helper/ui.cr @@ -0,0 +1,15 @@ +module Molinillo + class TestUI + include UI + + @output : IO? + + def output + @output ||= if debug? + STDERR + else + File.open("/dev/null", "w") + end + end + end +end diff --git a/lib/molinillo/spec/spec_helper/versions.cr b/lib/molinillo/spec/spec_helper/versions.cr new file mode 100644 index 00000000..f209e7e9 --- /dev/null +++ b/lib/molinillo/spec/spec_helper/versions.cr @@ -0,0 +1,232 @@ +module Shards + module Versions + # :nodoc: + struct Segment + NON_ALPHANUMERIC = /[^a-zA-Z0-9]/ + NATURAL_SORT_EXTRACT_NEXT_CHARS_AND_DIGITS = /^(\D*)(\d*)(.*)$/ + + protected getter! segment : String + + def initialize(@str : String) + if index = @str.index('+') + @str = @str[0...index] + end + end + + def next + @segment, _, @str = @str.partition(NON_ALPHANUMERIC) + segment + end + + def empty? + segment.empty? + end + + def to_i? + segment.to_i?(whitespace: false) + end + + def <=>(b : self) + natural_sort(segment, b.segment) + end + + # Original natural sorting algorithm from: + # https://github.com/sourcefrog/natsort/blob/master/natcmp.rb + # Copyright (C) 2003 by Alan Davies . + private def natural_sort(a, b) + if (a_num = a.to_i?(whitespace: false)) && (b_num = b.to_i?(whitespace: false)) + return a_num <=> b_num + end + + loop do + return 0 if a.empty? && b.empty? + + a =~ NATURAL_SORT_EXTRACT_NEXT_CHARS_AND_DIGITS + a_chars, a_digits, a = $1, $2, $3 + + b =~ NATURAL_SORT_EXTRACT_NEXT_CHARS_AND_DIGITS + b_chars, b_digits, b = $1, $2, $3 + + ret = a_chars <=> b_chars + return ret unless ret == 0 + + a_num = a_digits.to_i?(whitespace: false) + b_num = b_digits.to_i?(whitespace: false) + + if a_num && b_num + ret = a_num.to_i <=> b_num.to_i + return ret unless ret == 0 + else + ret = a_digits <=> b_digits + return ret unless ret == 0 + end + end + end + + def only_zeroes? + return if empty? + yield unless to_i? == 0 + + loop do + self.next + + return if empty? + yield unless to_i? == 0 + end + end + + def prerelease? + segment.each_char.any?(&.ascii_letter?) + end + + def inspect(io) + @segment.inspect(io) + end + end + + def self.sort(versions) + versions.sort { |a, b| compare(a, b) } + end + + def self.compare(a, b) + if a == b + return 0 + end + + a_segment = Segment.new(a) + b_segment = Segment.new(b) + + loop do + # extract next segment from version number ("1.0.2" => "1" then "0" then "2"): + a_segment.next + b_segment.next + + # accept unbalanced version numbers ("1.0" == "1.0.0.0", "1.0" < "1.0.1") + if a_segment.empty? + b_segment.only_zeroes? { return b_segment.prerelease? ? -1 : 1 } + return 0 + end + + # accept unbalanced version numbers ("1.0.0.0" == "1.0", "1.0.1" > "1.0") + if b_segment.empty? + a_segment.only_zeroes? { return a_segment.prerelease? ? 1 : -1 } + return 0 + end + + # try to convert segments to numbers: + a_num = a_segment.to_i? + b_num = b_segment.to_i? + + ret = + if a_num && b_num + # compare numbers (for natural 1, 2, ..., 10, 11 ordering): + b_num <=> a_num + elsif a_num + # b is preliminary version: + a_segment.only_zeroes? do + return b_segment <=> a_segment if a_segment.prerelease? + return -1 + end + return -1 + elsif b_num + # a is preliminary version: + b_segment.only_zeroes? do + return b_segment <=> a_segment if b_segment.prerelease? + return 1 + end + return 1 + else + # compare strings: + b_segment <=> a_segment + end + + # if different return the result (older or newer), otherwise continue + # to the next segment: + return ret unless ret == 0 + end + end + + def self.prerelease?(str) + str.each_char do |char| + return true if char.ascii_letter? + break if char == '+' + end + false + end + + protected def self.without_prereleases(versions) + versions.reject { |v| prerelease?(v) } + end + + def self.resolve(versions, requirements : Enumerable(String), prereleases = false) + unless prereleases || requirements.any? { |r| prerelease?(r) } + versions = without_prereleases(versions) + end + + matching_versions = requirements + .map { |requirement| resolve(versions, requirement) } + .reduce(versions) { |a, e| a & e } + + sort(matching_versions) + end + + def self.resolve(versions, requirement : String) + case requirement + when "*", "" + versions + when /~>\s*([^\s]+)/ + ver = if idx = $1.rindex('.') + $1[0...idx] + else + $1 + end + versions.select { |version| matches_approximate?(version, $1, ver) } + when /\s*(~>|>=|<=|>|<|=)\s*([^~<>=\s]+)\s*/ + versions.select { |version| matches_operator?(version, $1, $2) } + else + versions.select { |version| matches_operator?(version, "=", requirement) } + end + end + + def self.matches?(version : String, requirement : String) + case requirement + when "*", "" + true + when /~>\s*([^\s]+)\d*/ + ver = if idx = $1.rindex('.') + $1[0...idx] + else + $1 + end + matches_approximate?(version, $1, ver) + when /\s*(~>|>=|<=|>|<|!=|=)\s*([^~<>=\s]+)\s*/ + matches_operator?(version, $1, $2) + else + matches_operator?(version, "=", requirement) + end + end + + private def self.matches_approximate?(version, requirement, ver) + version.starts_with?(ver) && + !version[ver.size]?.try(&.ascii_alphanumeric?) && + (compare(version, requirement) <= 0) + end + + private def self.matches_operator?(version, operator, requirement) + case operator + when ">=" + compare(version, requirement) <= 0 + when "<=" + compare(version, requirement) >= 0 + when ">" + compare(version, requirement) < 0 + when "<" + compare(version, requirement) > 0 + when "!=" + compare(version, requirement) != 0 + else + compare(version, requirement) == 0 + end + end + end +end diff --git a/lib/molinillo/spec/state_spec.cr b/lib/molinillo/spec/state_spec.cr new file mode 100644 index 00000000..4592939a --- /dev/null +++ b/lib/molinillo/spec/state_spec.cr @@ -0,0 +1,29 @@ +require "./spec_helper" + +module Molinillo + describe ResolutionState do + describe DependencyState do + it "pops a possibility state" do + possibility1 = Resolver::Resolution::PossibilitySet(String, String).new(%w(), %w(possibility1)) + possibility = Resolver::Resolution::PossibilitySet(String, String).new(%w(), %w(possibility)) + state = DependencyState(String, String).new( + "name", + %w(requirement1 requirement2 requirement3), + DependencyGraph(Resolver::Resolution::PossibilitySet(String, String) | String | Nil, String).new, + "requirement", + [possibility1, possibility], + 0, + {} of String => Resolver::Resolution::Conflict(String, String), + [] of Resolver::Resolution::UnwindDetails(String, String) + ) + possibility_state = state.pop_possibility_state + {% for attr in %w(name requirements activated requirement conflicts) %} + possibility_state.{{ attr.id }}.should eq(state.{{ attr.id }}) + {% end %} + possibility_state.should be_a(PossibilityState(String, String)) + possibility_state.depth.should eq(state.depth + 1) + possibility_state.possibilities.should eq([possibility]) + end + end + end +end diff --git a/lib/molinillo/src/molinillo.cr b/lib/molinillo/src/molinillo.cr new file mode 100644 index 00000000..c2502ca4 --- /dev/null +++ b/lib/molinillo/src/molinillo.cr @@ -0,0 +1,5 @@ +module Molinillo + VERSION = "0.2.0" +end + +require "./molinillo/**" diff --git a/lib/molinillo/src/molinillo/delegates/resolution_state.cr b/lib/molinillo/src/molinillo/delegates/resolution_state.cr new file mode 100644 index 00000000..bbadf8b7 --- /dev/null +++ b/lib/molinillo/src/molinillo/delegates/resolution_state.cr @@ -0,0 +1,55 @@ +module Molinillo + # @!visibility private + module Delegates + # Delegates all {Molinillo::ResolutionState} methods to a `#state` property. + module ResolutionState(R, S) + # (see Molinillo::ResolutionState#name) + def name + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.name + end + + # (see Molinillo::ResolutionState#requirements) + def requirements + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.requirements + end + + # (see Molinillo::ResolutionState#activated) + def activated + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.activated + end + + # (see Molinillo::ResolutionState#requirement) + def requirement + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.requirement + end + + # (see Molinillo::ResolutionState#possibilities) + def possibilities + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.possibilities + end + + # (see Molinillo::ResolutionState#depth) + def depth + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.depth + end + + # (see Molinillo::ResolutionState#conflicts) + def conflicts + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.conflicts + end + + # (see Molinillo::ResolutionState#unused_unwind_options) + def unused_unwind_options + current_state = state || Molinillo::ResolutionState(R, S).empty + current_state.unused_unwind_options + end + end + end +end diff --git a/lib/molinillo/src/molinillo/delegates/specification_provider.cr b/lib/molinillo/src/molinillo/delegates/specification_provider.cr new file mode 100644 index 00000000..92deb45b --- /dev/null +++ b/lib/molinillo/src/molinillo/delegates/specification_provider.cr @@ -0,0 +1,78 @@ +module Molinillo + module Delegates + # Delegates all {Molinillo::SpecificationProvider} methods to a + # `#specification_provider` property. + module SpecificationProvider + # (see Molinillo::SpecificationProvider#search_for) + def search_for(dependency) + with_no_such_dependency_error_handling do + specification_provider.search_for(dependency) + end + end + + # (see Molinillo::SpecificationProvider#dependencies_for) + def dependencies_for(specification) + with_no_such_dependency_error_handling do + specification_provider.dependencies_for(specification) + end + end + + # (see Molinillo::SpecificationProvider#requirement_satisfied_by?) + def requirement_satisfied_by?(requirement, activated, spec) + with_no_such_dependency_error_handling do + specification_provider.requirement_satisfied_by?(requirement, activated, spec) + end + end + + # (see Molinillo::SpecificationProvider#name_for) + def name_for(dependency) + with_no_such_dependency_error_handling do + specification_provider.name_for(dependency) + end + end + + # (see Molinillo::SpecificationProvider#name_for_explicit_dependency_source) + def name_for_explicit_dependency_source + with_no_such_dependency_error_handling do + specification_provider.name_for_explicit_dependency_source + end + end + + # (see Molinillo::SpecificationProvider#name_for_locking_dependency_source) + def name_for_locking_dependency_source + with_no_such_dependency_error_handling do + specification_provider.name_for_locking_dependency_source + end + end + + # (see Molinillo::SpecificationProvider#sort_dependencies) + def sort_dependencies(dependencies, activated, conflicts) + with_no_such_dependency_error_handling do + specification_provider.sort_dependencies(dependencies, activated, conflicts) + end + end + + # (see Molinillo::SpecificationProvider#allow_missing?) + def allow_missing?(dependency) + with_no_such_dependency_error_handling do + specification_provider.allow_missing?(dependency) + end + end + + # Ensures any raised {NoSuchDependencyError} has its + # {NoSuchDependencyError#required_by} set. + # @yield + private def with_no_such_dependency_error_handling + yield + rescue error : NoSuchDependencyError + if state + # TODO + # vertex = activated.vertex_named(name_for(error.dependency)) + # error.required_by += vertex.incoming_edges.map { |e| e.origin.name } + # error.required_by << name_for_explicit_dependency_source unless vertex.explicit_requirements.empty? + end + raise error + end + end + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph.cr b/lib/molinillo/src/molinillo/dependency_graph.cr new file mode 100644 index 00000000..b473239b --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph.cr @@ -0,0 +1,190 @@ +class Molinillo::DependencyGraph(P, R) +end + +require "./dependency_graph/log" +require "./dependency_graph/vertex" + +class Molinillo::DependencyGraph(P, R) + # Enumerates through the vertices of the graph. + # @return [Array] The graph's vertices. + def each + # return vertices.values.each unless block_given? + vertices.values.each { |v| yield v } + end + + getter log : Log(P, R) + getter vertices : Hash(String, Vertex(P, R)) + + # A directed edge of a {DependencyGraph} + # @attr [Vertex] origin The origin of the directed edge + # @attr [Vertex] destination The destination of the directed edge + # @attr [Object] requirement The requirement the directed edge represents + record Edge(P, R), origin : Vertex(P, R), destination : Vertex(P, R), requirement : R + + def initialize + @vertices = {} of String => Vertex(P, R) + @log = Log(P, R).new + end + + # Tags the current state of the dependency as the given tag + # @param [Object] tag an opaque tag for the current state of the graph + # @return [Void] + def tag(tag : Symbol | Reference) + log.tag(self, tag) + end + + # Rewinds the graph to the state tagged as `tag` + # @param [Object] tag the tag to rewind to + # @return [Void] + def rewind_to(tag) + log.rewind_to(self, tag) + end + + def inspect + "#" + end + + def to_dot + dot_vertices = [] of String + dot_edges = [] of String + vertices.each do |n, v| + dot_vertices << " #{n} [label=\"{#{n}|#{v.payload}}\"]" + v.outgoing_edges.each do |e| + label = e.requirement + dot_edges << " #{e.origin.name} -> #{e.destination.name} [label=#{label.to_s.dump}]" + end + end + + dot_vertices.uniq! + dot_vertices.sort! + dot_edges.uniq! + dot_edges.sort! + + dot = dot_vertices.unshift("digraph G {").push("") + dot_edges.push("}") + dot.join("\n") + end + + def ==(other) + super || begin + return false unless vertices.keys.to_set == other.vertices.keys.to_set + vertices.each do |name, vertex| + other_vertex = other.vertex_named(name) + return false unless other_vertex + return false unless vertex.payload == other_vertex.payload + return false unless other_vertex.successors.to_set == vertex.successors.to_set + end + true + end + end + + # @param [String] name + # @param [Object] payload + # @param [Array] parent_names + # @param [Object] requirement the requirement that is requiring the child + # @return [void] + def add_child_vertex(name : String, payload : P, parent_names : Array(String?), requirement : R) + root = !(parent_names.delete(nil) || true) + vertex = add_vertex(name, payload, root) + vertex.explicit_requirements << requirement if root + parent_names.each do |parent_name| + parent_vertex = vertex_named!(parent_name) + add_edge(parent_vertex, vertex, requirement) + end + vertex + end + + # Adds a vertex with the given name, or updates the existing one. + # @param [String] name + # @param [Object] payload + # @return [Vertex] the vertex that was added to `self` + def add_vertex(name : String, payload : P, root : Bool = false) + log.add_vertex(self, name, payload, root) + end + + # Detaches the {#vertex_named} `name` {Vertex} from the graph, recursively + # removing any non-root vertices that were orphaned in the process + # @param [String] name + # @return [Array] the vertices which have been detached + def detach_vertex_named(name) + log.detach_vertex_named(self, name) + end + + # @param [String] name + # @return [Vertex,nil] the vertex with the given name + def vertex_named(name) : Vertex(P, R)? + vertices[name]? + end + + # @param [String] name + # @return [Vertex,nil] the vertex with the given name + def vertex_named!(name) : Vertex(P, R) + vertices[name] + end + + # @param [String] name + # @return [Vertex,nil] the root vertex with the given name + def root_vertex_named(name) : Vertex(P, R)? + vertex = vertex_named(name) + vertex if vertex && vertex.root + end + + # Adds a new {Edge} to the dependency graph + # @param [Vertex] origin + # @param [Vertex] destination + # @param [Object] requirement the requirement that this edge represents + # @return [Edge] the added edge + def add_edge(origin : Vertex(P, R), destination : Vertex(P, R), requirement : R) + if destination.path_to?(origin) + raise CircularDependencyError(P, R).new(path(destination, origin)) + end + add_edge_no_circular(origin, destination, requirement) + end + + # Sets the payload of the vertex with the given name + # @param [String] name the name of the vertex + # @param [Object] payload the payload + # @return [Void] + def set_payload(name, payload) + log.set_payload(self, name, payload) + end + + # Adds a new {Edge} to the dependency graph without checking for + # circularity. + # @param (see #add_edge) + # @return (see #add_edge) + private def add_edge_no_circular(origin, destination, requirement) + log.add_edge_no_circular(self, origin.name, destination.name, requirement) + end + + # Returns the path between two vertices + # @raise [ArgumentError] if there is no path between the vertices + # @param [Vertex] from + # @param [Vertex] to + # @return [Array] the shortest path from `from` to `to` + def path(from, to) + distances = Hash(String, Int32).new(vertices.size + 1) + distances[from.name] = 0 + predecessors = {} of Vertex(P, R) => Vertex(P, R) + each do |vertex| + vertex.successors.each do |successor| + if distances[successor.name] > distances[vertex.name] + 1 + distances[successor.name] = distances[vertex.name] + 1 + predecessors[successor] = vertex + end + end + end + + path = [to] + while before = predecessors[to]? + path << before + to = before + break if to == from + end + + unless path.last == from + raise ArgumentError.new("There is no path from #{from.name} to #{to.name}") + end + + path.reverse + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/action.cr b/lib/molinillo/src/molinillo/dependency_graph/action.cr new file mode 100644 index 00000000..84e8b207 --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/action.cr @@ -0,0 +1,21 @@ +module Molinillo + # An action that modifies a {DependencyGraph} that is reversible. + # @abstract + abstract class DependencyGraph::Action(P, R) + # Performs the action on the given graph. + # @param [DependencyGraph] graph the graph to perform the action on. + # @return [Void] + abstract def up(graph : DependencyGraph(P, R)) + + # Reverses the action on the given graph. + # @param [DependencyGraph] graph the graph to reverse the action on. + # @return [Void] + abstract def down(graph : DependencyGraph(P, R)) + + # @return [Action,Nil] The previous action + property previous : Action(P, R)? + + # @return [Action,Nil] The next action + property next : Action(P, R)? + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/add_edge_no_circular.cr b/lib/molinillo/src/molinillo/dependency_graph/add_edge_no_circular.cr new file mode 100644 index 00000000..71cce9a5 --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/add_edge_no_circular.cr @@ -0,0 +1,36 @@ +require "./action" + +class Molinillo::DependencyGraph + class AddEdgeNoCircular(P, R) < Action(P, R) + getter origin : String + getter destination : String + getter requirement : R + + def initialize(@origin : String, @destination : String, @requirement : R) + end + + def up(graph) + edge = make_edge(graph) + edge.origin.outgoing_edges << edge + edge.destination.incoming_edges << edge + edge + end + + def down(graph) + edge = make_edge(graph) + delete_first(edge.origin.outgoing_edges, edge) + delete_first(edge.destination.incoming_edges, edge) + end + + # @param [DependencyGraph] graph the graph to find vertices from + # @return [Edge] The edge this action adds + def make_edge(graph) + Edge(P, R).new(graph.vertex_named!(origin), graph.vertex_named!(destination), requirement) + end + + private def delete_first(array, item) + return unless index = array.index(item) + array.delete_at(index) + end + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/add_vertex.cr b/lib/molinillo/src/molinillo/dependency_graph/add_vertex.cr new file mode 100644 index 00000000..97c58e46 --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/add_vertex.cr @@ -0,0 +1,35 @@ +require "./action" + +class Molinillo::DependencyGraph + class AddVertex(P, R) < Action(P, R) + getter name : String + getter payload : P + getter root : Bool + + @existing : {payload: P, root: Bool}? + + def initialize(@name, @payload : P, @root) + end + + def up(graph) + if existing = graph.vertices[name]? + @existing = {payload: existing.payload, root: existing.root} + end + vertex = existing || Vertex(P, R).new(name, payload) + graph.vertices[vertex.name] = vertex + vertex.payload ||= payload + vertex.root ||= root + vertex + end + + def down(graph) + if existing = @existing + vertex = graph.vertices[name] + vertex.payload = existing[:payload] + vertex.root = existing[:root] + else + graph.vertices.delete(name) + end + end + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/delete_edge.cr b/lib/molinillo/src/molinillo/dependency_graph/delete_edge.cr new file mode 100644 index 00000000..97fbb174 --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/delete_edge.cr @@ -0,0 +1,33 @@ +require "./action" + +class Molinillo::DependencyGraph + class DeleteEdge(P, R) < Action(P, R) + getter origin_name : String + getter destination_name : String + getter requirement : R + + def initialize(@origin_name, @destination_name, @requirement) + end + + def up(graph) + edge = make_edge(graph) + edge.origin.outgoing_edges.delete(edge) + edge.destination.incoming_edges.delete(edge) + end + + def down(graph) + edge = make_edge(graph) + edge.origin.outgoing_edges << edge + edge.destination.incoming_edges << edge + edge + end + + private def make_edge(graph) + Edge(P, R).new( + graph.vertex_named(origin_name), + graph.vertex_named(destination_name), + requirement + ) + end + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/detach_vertex_named.cr b/lib/molinillo/src/molinillo/dependency_graph/detach_vertex_named.cr new file mode 100644 index 00000000..a1592d96 --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/detach_vertex_named.cr @@ -0,0 +1,42 @@ +require "./action" + +class Molinillo::DependencyGraph + class DetachVertexNamed(P, R) < Action(P, R) + getter name : String + @vertex : Vertex(P, R)? + + def initialize(@name) + end + + def up(graph) + return [] of Vertex(P, R) unless vertex = @vertex = graph.vertices.delete(name) + + removed_vertices = [vertex] of Vertex(P, R) + vertex.outgoing_edges.each do |e| + v = e.destination + v.incoming_edges.delete(e) + if !v.root && v.incoming_edges.empty? + removed_vertices.concat graph.detach_vertex_named(v.name) + end + end + + vertex.incoming_edges.each do |e| + v = e.origin + v.outgoing_edges.delete(e) + end + + removed_vertices + end + + def down(graph) + return unless vertex = @vertex + graph.vertices[vertex.name] = vertex + vertex.outgoing_edges.each do |e| + e.destination.incoming_edges << e + end + vertex.incoming_edges.each do |e| + e.origin.outgoing_edges << e + end + end + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/log.cr b/lib/molinillo/src/molinillo/dependency_graph/log.cr new file mode 100644 index 00000000..ba10d38e --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/log.cr @@ -0,0 +1,85 @@ +require "./add_vertex" +require "./add_edge_no_circular" + +class Molinillo::DependencyGraph::Log(P, R) + @current_action : Action(P, R)? + @first_action : Action(P, R)? + + def tag(graph, tag) + push_action(graph, Tag(P, R).new(tag)) + end + + def add_vertex(graph, name : String, payload : P, root) + push_action(graph, AddVertex(P, R).new(name, payload, root)) + end + + def detach_vertex_named(graph, name) + push_action(graph, DetachVertexNamed(P, R).new(name)) + end + + def add_edge_no_circular(graph, origin, destination, requirement) + push_action(graph, AddEdgeNoCircular(P, R).new(origin, destination, requirement)) + end + + # {include:DependencyGraph#delete_edge} + # @param [Graph] graph the graph to perform the action on + # @param [String] origin_name + # @param [String] destination_name + # @param [Object] requirement + # @return (see DependencyGraph#delete_edge) + def delete_edge(graph, origin_name, destination_name, requirement) + push_action(graph, DeleteEdge.new(origin_name, destination_name, requirement)) + end + + # @macro action + def set_payload(graph, name, payload) + push_action(graph, SetPayload(P, R).new(name, payload)) + end + + # Pops the most recent action from the log and undoes the action + # @param [DependencyGraph] graph + # @return [Action] the action that was popped off the log + def pop!(graph) + return unless action = @current_action + unless @current_action = action.previous + @first_action = nil + end + action.down(graph) + action + end + + # Enumerates each action in the log + # @yield [Action] + def each + action = @first_action + loop do + break unless action + yield action + action = action.next + end + self + end + + def rewind_to(graph, tag) + tag_value = Tag::Value.new(tag) + loop do + action = pop!(graph) + raise "No tag #{tag.inspect} found" unless action + break if action.is_a?(Tag(P, R)) && action.tag == tag_value + end + end + + # Adds the given action to the log, running the action + # @param [DependencyGraph] graph + # @param [Action] action + # @return The value returned by `action.up` + private def push_action(graph, action) + action.previous = @current_action + if current_action = @current_action + current_action.next = action + end + @current_action = action + @first_action ||= action + action.up(graph) + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/set_payload.cr b/lib/molinillo/src/molinillo/dependency_graph/set_payload.cr new file mode 100644 index 00000000..d590755c --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/set_payload.cr @@ -0,0 +1,22 @@ +require "./action" + +class Molinillo::DependencyGraph + class SetPayload(P, R) < Action(P, R) + getter name : String + getter payload : P + @old_payload : P? + + def initialize(@name, @payload) + end + + def up(graph) + vertex = graph.vertex_named!(name) + @old_payload = vertex.payload + vertex.payload = payload + end + + def down(graph) + graph.vertex_named!(name).payload = @old_payload + end + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/tag.cr b/lib/molinillo/src/molinillo/dependency_graph/tag.cr new file mode 100644 index 00000000..fd325213 --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/tag.cr @@ -0,0 +1,42 @@ +require "./action" + +class Molinillo::DependencyGraph + class Tag(P, R) < Action(P, R) + abstract struct Value + def self.new(value : Reference) + ReferenceValue.new(value) + end + + def self.new(value : Symbol) + OtherValue.new(value) + end + end + + struct ReferenceValue < Value + @value : UInt64 + + def initialize(value : Reference) + @value = value.object_id + end + end + + struct OtherValue < Value + @value : Symbol + + def initialize(@value) + end + end + + getter tag : Value + + def up(graph) + end + + def down(graph) + end + + def initialize(tag) + @tag = Value.new(tag) + end + end +end diff --git a/lib/molinillo/src/molinillo/dependency_graph/vertex.cr b/lib/molinillo/src/molinillo/dependency_graph/vertex.cr new file mode 100644 index 00000000..55037039 --- /dev/null +++ b/lib/molinillo/src/molinillo/dependency_graph/vertex.cr @@ -0,0 +1,58 @@ +class Molinillo::DependencyGraph::Vertex(P, R) + property root = false + property name : String + property payload : P + getter explicit_requirements : Array(R) + getter outgoing_edges : Array(Edge(P, R)) + getter incoming_edges : Array(Edge(P, R)) + + def initialize(@name, @payload : P) + @explicit_requirements = Array(R).new + @outgoing_edges = Array(Edge(P, R)).new + @incoming_edges = Array(Edge(P, R)).new + end + + # @return [Array] all of the requirements that required + # this vertex + def requirements + (incoming_edges.map(&.requirement) + explicit_requirements).uniq + end + + # @return [Array] the vertices of {#graph} that have an edge with + # `self` as their {Edge#destination} + def predecessors + incoming_edges.map &.origin + end + + # @return [Array] the vertices of {#graph} that have an edge with + # `self` as their {Edge#origin} + def successors + outgoing_edges.map &.destination + end + + def ==(other) + super || ( + name == other.name && + payload == other.payload && + successors.to_set == other.successors.to_set + ) + end + + def_hash @name + + # Is there a path from `self` to `other` following edges in the + # dependency graph? + # @return true iff there is a path following edges within this {#graph} + def path_to?(other) + _path_to?(other) + end + + # @param [Vertex] other the vertex to check if there's a path to + # @param [Set] visited the vertices of {#graph} that have been visited + # @return [Boolean] whether there is a path to `other` from `self` + protected def _path_to?(other, visited = Set(self).new) + return false unless visited.add?(self) + return true if self == other + successors.any? { |v| v._path_to?(other, visited) } + end +end diff --git a/lib/molinillo/src/molinillo/errors.cr b/lib/molinillo/src/molinillo/errors.cr new file mode 100644 index 00000000..2915c9ef --- /dev/null +++ b/lib/molinillo/src/molinillo/errors.cr @@ -0,0 +1,142 @@ +require "./delegates/specification_provider" + +module Molinillo + # An error that occurred during the resolution process + class ResolverError < Exception; end + + # An error caused by searching for a dependency that is completely unknown, + # i.e. has no versions available whatsoever. + class NoSuchDependencyError < ResolverError + # @return [Object] the dependency that could not be found + getter dependency : String + + # @return [Array] the specifications that depended upon {#dependency} + getter required_by : Array(String) + + # Initializes a new error with the given missing dependency. + # @param [Object] dependency @see {#dependency} + # @param [Array] required_by @see {#required_by} + def initialize(dependency, required_by = [] of S) + @dependency = dependency + @required_by = required_by.uniq + super + end + + # The error message for the missing dependency, including the specifications + # that had this dependency. + def message + sources = required_by.map { |r| "`#{r}`" }.join(" and ") + message = "Unable to find a specification for `#{dependency}`" + message += " depended upon by #{sources}" unless sources.empty? + message + end + end + + # An error caused by attempting to fulfil a dependency that was circular + # + # @note This exception will be thrown iff a {Vertex} is added to a + # {DependencyGraph} that has a {DependencyGraph::Vertex#path_to?} an + # existing {DependencyGraph::Vertex} + class CircularDependencyError(P, R) < ResolverError + # [Set] the dependencies responsible for causing the error + getter vertices : Array(DependencyGraph::Vertex(P, R)) + + # Initializes a new error with the given circular vertices. + # @param [Array] vertices the vertices in the dependency + # that caused the error + def initialize(@vertices) + super "There is a circular dependency between #{vertices.map(&.name).join(" and ")}" + # @dependencies = vertices.map { |vertex| vertex.payload.possibilities.last }.to_set + end + end + + # An error caused by conflicts in version + class VersionConflict(R, S) < ResolverError + # @return [{String => Resolution::Conflict}] the conflicts that caused + # resolution to fail + getter conflicts : Hash(String, Resolver::Resolution::Conflict(R, S)) + + # @return [SpecificationProvider] the specification provider used during + # resolution + getter specification_provider : SpecificationProvider(R, S) + + # Initializes a new error with the given version conflicts. + # @param [{String => Resolution::Conflict}] conflicts see {#conflicts} + # @param [SpecificationProvider] specification_provider see {#specification_provider} + def initialize(conflicts, specification_provider) + pairs = [] of {R, S | String} + conflicts.values.flatten.flat_map(&.requirements).each do |conflicting| + conflicting.each do |source, conflict_requirements| + conflict_requirements.each do |c| + pairs << {c, source} + end + end + end + + super "Unable to satisfy the following requirements:\n\n" \ + "#{pairs.map { |r, d| "- `#{r}` required by `#{d}`" }.join("\n")}" + + @conflicts = conflicts + @specification_provider = specification_provider + end + + include Delegates::SpecificationProvider + + # @return [String] An error message that includes requirement trees, + # which is much more detailed & customizable than the default message + # @param [Hash] opts the options to create a message with. + # @option opts [String] :solver_name The user-facing name of the solver + # @option opts [String] :possibility_type The generic name of a possibility + # @option opts [Proc] :reduce_trees A proc that reduced the list of requirement trees + # @option opts [Proc] :printable_requirement A proc that pretty-prints requirements + # @option opts [Proc] :additional_message_for_conflict A proc that appends additional + # messages for each conflict + # @option opts [Proc] :version_for_spec A proc that returns the version number for a + # possibility + def message_with_trees(opts = {} of Symbol => String) + solver_name = opts.delete(:solver_name) { self.class.name.split("::").first } + possibility_type = opts.delete(:possibility_type) { "possibility named" } + reduce_trees = opts.delete(:reduce_trees) { proc { |trees| trees.uniq.sort_by(&:to_s) } } + printable_requirement = opts.delete(:printable_requirement) { proc { |req| req.to_s } } + additional_message_for_conflict = opts.delete(:additional_message_for_conflict) { proc { } } + version_for_spec = opts.delete(:version_for_spec) { proc(&:to_s) } + incompatible_version_message_for_conflict = opts.delete(:incompatible_version_message_for_conflict) do + proc do |name, _conflict| + %(#{solver_name} could not find compatible versions for #{possibility_type} "#{name}":) + end + end + + conflicts.sort.reduce("".dup) do |o, (name, conflict)| + o << "\n" << incompatible_version_message_for_conflict.call(name, conflict) << "\n" + if conflict.locked_requirement + o << %( In snapshot (#{name_for_locking_dependency_source}):\n) + o << %( #{printable_requirement.call(conflict.locked_requirement)}\n) + o << %(\n) + end + o << %( In #{name_for_explicit_dependency_source}:\n) + trees = reduce_trees.call(conflict.requirement_trees) + + o << trees.map do |tree| + t = "".dup + depth = 2 + tree.each do |req| + t << " " * depth << req.to_s + unless tree.last == req + if spec = conflict.activated_by_name[name_for(req)] + t << %( was resolved to #{version_for_spec.call(spec)}, which) + end + t << %( depends on) + end + t << %(\n) + depth += 1 + end + t + end.join("\n") + + additional_message_for_conflict.call(o, name, conflict) + + o + end.strip + end + end +end diff --git a/lib/molinillo/src/molinillo/modules/specification_provider.cr b/lib/molinillo/src/molinillo/modules/specification_provider.cr new file mode 100644 index 00000000..8582dfcf --- /dev/null +++ b/lib/molinillo/src/molinillo/modules/specification_provider.cr @@ -0,0 +1,99 @@ +module Molinillo + # Provides information about specifcations and dependencies to the resolver, + # allowing the {Resolver} class to remain generic while still providing power + # and flexibility. + # + # This module contains the methods that users of Molinillo must to implement, + # using knowledge of their own model classes. + module SpecificationProvider(R, S) + # Search for the specifications that match the given dependency. + # The specifications in the returned array will be considered in reverse + # order, so the latest version ought to be last. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `dependency` parameter. + # + # @param [Object] dependency + # @return [Array] the specifications that satisfy the given + # `dependency`. + def search_for(dependency : R) + [] of S + end + + # Returns the dependencies of `specification`. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `specification` parameter. + # + # @param [Object] specification + # @return [Array] the dependencies that are required by the given + # `specification`. + def dependencies_for(specification : S) + [] of R + end + + # Determines whether the given `requirement` is satisfied by the given + # `spec`, in the context of the current `activated` dependency graph. + # + # @param [Object] requirement + # @param [DependencyGraph] activated the current dependency graph in the + # resolution process. + # @param [Object] spec + # @return [Boolean] whether `requirement` is satisfied by `spec` in the + # context of the current `activated` dependency graph. + def requirement_satisfied_by?(requirement : R, activated : DependencyGraph, spec : S) + true + end + + # Returns the name for the given `dependency`. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `dependency` parameter. + # + # @param [Object] dependency + # @return [String] the name for the given `dependency`. + def name_for(dependency : R) + dependency.to_s + end + + # @return [String] the name of the source of explicit dependencies, i.e. + # those passed to {Resolver#resolve} directly. + def name_for_explicit_dependency_source + "user-specified dependency" + end + + # @return [String] the name of the source of 'locked' dependencies, i.e. + # those passed to {Resolver#resolve} directly as the `base` + def name_for_locking_dependency_source + "Lockfile" + end + + # Sort dependencies so that the ones that are easiest to resolve are first. + # Easiest to resolve is (usually) defined by: + # 1) Is this dependency already activated? + # 2) How relaxed are the requirements? + # 3) Are there any conflicts for this dependency? + # 4) How many possibilities are there to satisfy this dependency? + # + # @param [Array] dependencies + # @param [DependencyGraph] activated the current dependency graph in the + # resolution process. + # @param [{String => Array}] conflicts + # @return [Array] a sorted copy of `dependencies`. + def sort_dependencies(dependencies : Array(R), activated : DependencyGraph, conflicts) + dependencies.sort_by do |dependency| + name = name_for(dependency) + { + activated.vertex_named!(name).payload ? 0 : 1, + conflicts[name]? ? 0 : 1, + } + end + end + + # Returns whether this dependency, which has no possible matching + # specifications, can safely be ignored. + # + # @param [Object] dependency + # @return [Boolean] whether this dependency can safely be skipped. + def allow_missing?(dependency : R) + false + end + end +end diff --git a/lib/molinillo/src/molinillo/modules/ui.cr b/lib/molinillo/src/molinillo/modules/ui.cr new file mode 100644 index 00000000..a3eed3de --- /dev/null +++ b/lib/molinillo/src/molinillo/modules/ui.cr @@ -0,0 +1,71 @@ +module Molinillo + # Conveys information about the resolution process to a user. + module UI + # The {IO} object that should be used to print output. `STDOUT`, by default. + # + # @return [IO] + def output + STDOUT + end + + # Called roughly every {#progress_rate}, this method should convey progress + # to the user. + # + # @return [void] + def indicate_progress + output.print '.' unless debug? + end + + # How often progress should be conveyed to the user via + # {#indicate_progress}, in seconds. A third of a second, by default. + # + # @return [Float] + def progress_rate + 0.33 + end + + # Called before resolution begins. + # + # @return [void] + def before_resolution + output.print "Resolving dependencies..." + end + + # Called after resolution ends (either successfully or with an error). + # By default, prints a newline. + # + # @return [void] + def after_resolution + output.puts + end + + # Conveys debug information to the user. + # + # @param [Integer] depth the current depth of the resolution process. + # @return [void] + def debug(depth = 0) + if debug? + debug_info = yield + debug_info = debug_info.inspect unless debug_info.is_a?(String) + debug_info = debug_info.split("\n").map { |s| ":#{depth.to_s.rjust 4}: #{s}" } + debug_info.each { |line| output.puts line } + end + end + + @debug_mode : Bool? + + # Whether or not debug messages should be printed. + # By default, whether or not the `MOLINILLO_DEBUG` environment variable is + # set. + # + # @return [Boolean] + def debug? + debug_mode = @debug_mode + if debug_mode == nil + @debug_mode = ENV.has_key?("MOLINILLO_DEBUG") + else + debug_mode + end + end + end +end diff --git a/lib/molinillo/src/molinillo/resolution.cr b/lib/molinillo/src/molinillo/resolution.cr new file mode 100644 index 00000000..2d40c3b1 --- /dev/null +++ b/lib/molinillo/src/molinillo/resolution.cr @@ -0,0 +1,857 @@ +require "./delegates/*" + +module Molinillo + class Resolver(R, S) + # A specific resolution from a given {Resolver} + class Resolution(R, S) + # A conflict that the resolution process encountered + # @attr [Object] requirement the requirement that immediately led to the conflict + # @attr [{String,Nil=>[Object]}] requirements the requirements that caused the conflict + # @attr [Object, nil] existing the existing spec that was in conflict with + # the {#possibility} + # @attr [Object] possibility_set the set of specs that was unable to be + # activated due to a conflict. + # @attr [Object] locked_requirement the relevant locking requirement. + # @attr [Array>] requirement_trees the different requirement + # trees that led to every requirement for the conflicting name. + # @attr [{String=>Object}] activated_by_name the already-activated specs. + # @attr [Object] underlying_error an error that has occurred during resolution, and + # will be raised at the end of it if no resolution is found. + class Conflict(R, S) + getter requirement : R + getter requirements : Hash(String | S, Array(R)) + getter existing : S? + getter possibility_set : PossibilitySet(R, S)? + getter locked_requirement : R? + getter requirement_trees : Array(Array(R)) + getter activated_by_name : Hash(String, S) + getter underlying_error : Exception? + + def initialize(@requirement, @requirements, @existing, @possibility_set, + @locked_requirement, @requirement_trees, @activated_by_name, @underlying_error) + end + + # @return [Object] a spec that was unable to be activated due to a conflict + def possibility + if s = possibility_set + s.latest_version + end + end + end + + # A collection of possibility states that share the same dependencies + class PossibilitySet(R, S) + # @attr [Array] dependencies the dependencies for this set of possibilities + getter dependencies : Array(R) + # @attr [Array] possibilities the possibilities + getter possibilities : Array(S) + + def initialize(@dependencies, @possibilities) + end + + # String representation of the possibility set, for debugging + def to_s(io) + io << "[#{possibilities.join(", ")}]" + end + + # @return [Object] most up-to-date dependency in the possibility set + def latest_version + possibilities.last + end + + def latest_version? + possibilities.last? + end + end + + # Details of the state to unwind to when a conflict occurs, and the cause of the unwind + # @attr [Integer] state_index the index of the state to unwind to + # @attr [Object] state_requirement the requirement of the state we're unwinding to + # @attr [Array] requirement_tree for the requirement we're relaxing + # @attr [Array] conflicting_requirements the requirements that combined to cause the conflict + # @attr [Array] requirement_trees for the conflict + # @attr [Array] requirements_unwound_to_instead array of unwind requirements that were chosen over this unwind + class UnwindDetails(R, S) + getter state_index : Int32 + getter state_requirement : R? + getter requirement_tree : Array(R) + getter conflicting_requirements : Array(R) + getter requirement_trees : Array(Array(R)) + getter requirements_unwound_to_instead : Array(R?) + + include Comparable(UnwindDetails(R, S)) + + def initialize(@state_index, @state_requirement, @requirement_tree, + @conflicting_requirements, @requirement_trees, @requirements_unwound_to_instead) + end + + # We compare UnwindDetails when choosing which state to unwind to. If + # two options have the same state_index we prefer the one most + # removed from a requirement that caused the conflict. Both options + # would unwind to the same state, but a `grandparent` option will + # filter out fewer of its possibilities after doing so - where a state + # is both a `parent` and a `grandparent` to requirements that have + # caused a conflict this is the correct behaviour. + # @param [UnwindDetail] other UnwindDetail to be compared + # @return [Integer] integer specifying ordering + def <=>(other) + if state_index > other.state_index + 1 + elsif state_index == other.state_index + reversed_requirement_tree_index <=> other.reversed_requirement_tree_index + else + -1 + end + end + + # @return [Integer] index of state requirement in reversed requirement tree + # (the conflicting requirement itself will be at position 0) + def reversed_requirement_tree_index + @reversed_requirement_tree_index ||= + if state_requirement + requirement_tree.reverse.index(state_requirement).not_nil! + else + 999_999 + end + end + + # @return [Boolean] where the requirement of the state we're unwinding + # to directly caused the conflict. Note: in this case, it is + # impossible for the state we're unwinding to to be a parent of + # any of the other conflicting requirements (or we would have + # circularity) + def unwinding_to_primary_requirement? + requirement_tree.last == state_requirement + end + + @requirements_to_avoid : Array(R)? + + # @return [Array] array of sub-dependencies to avoid when choosing a + # new possibility for the state we've unwound to. Only relevant for + # non-primary unwinds + def sub_dependencies_to_avoid + @requirements_to_avoid ||= + requirement_trees.map do |tree| + index = tree.index(state_requirement) + tree[index + 1] if index + end.compact + end + + @all_requirements : Array(R)? + + # @return [Array] array of all the requirements that led to the need for + # this unwind + def all_requirements + @all_requirements ||= requirement_trees.flatten + end + end + + # @return [SpecificationProvider] the provider that knows about + # dependencies, requirements, specifications, versions, etc. + getter specification_provider : SpecificationProvider(R, S) + + # @return [UI] the UI that knows how to communicate feedback about the + # resolution process back to the user + getter resolver_ui : UI + + # @return [DependencyGraph] the base dependency graph to which + # dependencies should be 'locked' + getter base : DependencyGraph(R, R) + + # @return [Array] the dependencies that were explicitly required + getter original_requested : Array(R) + + # Initializes a new resolution. + # @param [SpecificationProvider] specification_provider + # see {#specification_provider} + # @param [UI] resolver_ui see {#resolver_ui} + # @param [Array] requested see {#original_requested} + # @param [DependencyGraph] base see {#base} + def initialize(specification_provider, resolver_ui, requested, base) + @specification_provider = specification_provider + @resolver_ui = resolver_ui + @original_requested = requested + @base = base + @states = Array(ResolutionState(R, S)).new + @iteration_counter = 0 + @parents_of = Hash(R, Array(Int32)).new { |h, k| h[k] = [] of Int32 } + end + + # Resolves the {#original_requested} dependencies into a full dependency + # graph + # @raise [ResolverError] if successful resolution is impossible + # @return [DependencyGraph] the dependency graph of successfully resolved + # dependencies + def resolve + start_resolution + + while st = state + break if !st.requirement && st.requirements.empty? + indicate_progress + if st.is_a?(DependencyState) # DependencyState + debug(depth) { "Creating possibility state for #{requirement} (#{possibilities.size} remaining)" } + st.pop_possibility_state.tap do |s| + if s + states.push(s) + activated.tag(s) + end + end + end + process_topmost_state + end + + resolve_activated_specs + ensure + end_resolution + end + + # @return [Integer] the number of resolver iterations in between calls to + # {#resolver_ui}'s {UI#indicate_progress} method + private property iteration_rate : Int32? + + # @return [Time] the time at which resolution began + private property started_at : Time? + + # @return [Array] the stack of states for the resolution + private getter states : Array(ResolutionState(R, S)) + + # Sets up the resolution process + # @return [void] + private def start_resolution + @started_at = Time.local + + push_initial_state + + debug { "Starting resolution (#{@started_at})\nUser-requested dependencies: #{original_requested}" } + resolver_ui.before_resolution + end + + private def resolve_activated_specs + activated.vertices.each do |_, vertex| + next unless payload = vertex.payload + + latest_version = check_possibility_set(vertex).possibilities.reverse_each.find do |possibility| + vertex.requirements.all? { |req| requirement_satisfied_by?(req, activated, possibility) } + end + + activated.set_payload(vertex.name, latest_version) + end + activated + end + + # Ends the resolution process + # @return [void] + private def end_resolution + resolver_ui.after_resolution + debug do + "Finished resolution (#{@iteration_counter} steps) " \ + "(Took #{(ended_at = Time.local) - @started_at.not_nil!} seconds) (#{ended_at})" + end + debug { "Unactivated: " + activated.vertices.reject { |_n, v| v.payload }.keys.join(", ") } if state + debug { "Activated: " + activated.vertices.select { |_n, v| v.payload }.keys.join(", ") } if state + end + + include Molinillo::Delegates::ResolutionState(R, S) + include Molinillo::Delegates::SpecificationProvider + + # Processes the topmost available {RequirementState} on the stack + # @return [void] + private def process_topmost_state + if possibilities.last? + attempt_to_activate + else + create_conflict + unwind_for_conflict + end + rescue underlying_error : CircularDependencyError + create_conflict(underlying_error) + unwind_for_conflict + end + + # @return [Object] the current possibility that the resolution is trying + # to activate + private def possibility + possibilities.last + end + + # @return [RequirementState] the current state the resolution is + # operating upon + private def state + states.last? + end + + private def state! + states.last + end + + # Creates and pushes the initial state for the resolution, based upon the + # {#requested} dependencies + # @return [void] + private def push_initial_state + graph = DependencyGraph(PossibilitySet(R, S) | S | Nil, R).new.tap do |dg| + original_requested.each do |requested| + vertex = dg.add_vertex(name_for(requested), nil, true) + vertex.explicit_requirements << requested + end + dg.tag(:initial_state) + end + + push_state_for_requirements(original_requested, true, graph) + end + + # Unwinds the states stack because a conflict has been encountered + # @return [void] + private def unwind_for_conflict + details_for_unwind = build_details_for_unwind + unwind_options = unused_unwind_options + debug(depth) { "Unwinding for conflict: #{requirement} to #{details_for_unwind.state_index / 2}" } + conflicts.tap do |c| + sliced_states = states.delete_at((details_for_unwind.state_index + 1)..-1) + raise_error_unless_state(c) + activated.rewind_to(sliced_states.first || :initial_state) if sliced_states + state!.conflicts = c + state!.unused_unwind_options = unwind_options + filter_possibilities_after_unwind(details_for_unwind) + index = states.size - 1 + @parents_of.each { |_, a| a.reject! { |i| i >= index } } + state!.unused_unwind_options.reject! { |uw| uw.state_index >= index } + end + end + + # Raises a VersionConflict error, or any underlying error, if there is no + # current state + # @return [void] + private def raise_error_unless_state(conflicts) + return if state + + error = conflicts.values.map(&.underlying_error).compact.first? + raise error || VersionConflict(R, S).new(conflicts, specification_provider) + end + + # @return [UnwindDetails] Details of the nearest index to which we could unwind + private def build_details_for_unwind + # Get the possible unwinds for the current conflict + current_conflict = conflicts[name] + binding_requirements = binding_requirements_for_conflict(current_conflict) + unwind_details = unwind_options_for_requirements(binding_requirements) + + last_detail_for_current_unwind = unwind_details.sort.last + current_detail = last_detail_for_current_unwind + + # Look for past conflicts that could be unwound to affect the + # requirement tree for the current conflict + relevant_unused_unwinds = unused_unwind_options.select do |alternative| + intersecting_requirements = + last_detail_for_current_unwind.all_requirements & + alternative.requirements_unwound_to_instead + next if intersecting_requirements.empty? + # Find the highest index unwind whilst looping through + current_detail = alternative if alternative > current_detail + alternative + end + + # Add the current unwind options to the `unused_unwind_options` array. + # The "used" option will be filtered out during `unwind_for_conflict`. + state!.unused_unwind_options += unwind_details.reject { |detail| detail.state_index == -1 } + + # Update the requirements_unwound_to_instead on any relevant unused unwinds + relevant_unused_unwinds.each { |d| d.requirements_unwound_to_instead << current_detail.state_requirement } + unwind_details.each { |d| d.requirements_unwound_to_instead << current_detail.state_requirement } + + current_detail + end + + # @param [Array] binding_requirements array of requirements that combine to create a conflict + # @return [Array] array of UnwindDetails that have a chance + # of resolving the passed requirements + private def unwind_options_for_requirements(binding_requirements) + unwind_details = [] of UnwindDetails(R, S) + + trees = [] of Array(R) + binding_requirements.reverse_each do |r| + partial_tree = [r] + trees << partial_tree + unwind_details << UnwindDetails(R, S).new(-1, nil, partial_tree, binding_requirements, trees, [] of R?) + + # If this requirement has alternative possibilities, check if any would + # satisfy the other requirements that created this conflict + requirement_state = find_state_for(r) + if conflict_fixing_possibilities?(requirement_state, binding_requirements) + unwind_details << UnwindDetails(R, S).new( + states.index(requirement_state).not_nil!, + r, + partial_tree, + binding_requirements, + trees, + [] of R? + ) + end + + # Next, look at the parent of this requirement, and check if the requirement + # could have been avoided if an alternative PossibilitySet had been chosen + parent_r = parent_of(r) + next if parent_r.nil? + partial_tree.unshift(parent_r) + requirement_state = find_state_for(parent_r).not_nil! + if requirement_state.possibilities.any? { |set| !set.dependencies.includes?(r) } + unwind_details << UnwindDetails(R, S).new( + states.index(requirement_state).not_nil!, + parent_r, + partial_tree, + binding_requirements, + trees, + [] of R? + ) + end + + # Finally, look at the grandparent and up of this requirement, looking + # for any possibilities that wouldn't create their parent requirement + grandparent_r = parent_of(parent_r) + until grandparent_r.nil? + partial_tree.unshift(grandparent_r) + requirement_state = find_state_for(grandparent_r).not_nil! + if requirement_state.possibilities.any? { |set| !set.dependencies.includes?(parent_r) } + unwind_details << UnwindDetails(R, S).new( + states.index(requirement_state).not_nil!, + grandparent_r, + partial_tree, + binding_requirements, + trees, + [] of R? + ) + end + parent_r = grandparent_r + grandparent_r = parent_of(parent_r) + end + end + + unwind_details + end + + # @param [DependencyState] state + # @param [Array] binding_requirements array of requirements + # @return [Boolean] whether or not the given state has any possibilities + # that could satisfy the given requirements + private def conflict_fixing_possibilities?(state, binding_requirements) + return false unless state + + state.possibilities.any? do |possibility_set| + possibility_set.possibilities.any? do |poss| + possibility_satisfies_requirements?(poss, binding_requirements) + end + end + end + + # Filter's a state's possibilities to remove any that would not fix the + # conflict we've just rewound from + # @param [UnwindDetails] unwind_details details of the conflict just + # unwound from + # @return [void] + private def filter_possibilities_after_unwind(unwind_details) + return unless state && !state!.possibilities.empty? + + if unwind_details.unwinding_to_primary_requirement? + filter_possibilities_for_primary_unwind(unwind_details) + else + filter_possibilities_for_parent_unwind(unwind_details) + end + end + + # Filter's a state's possibilities to remove any that would not satisfy + # the requirements in the conflict we've just rewound from + # @param [UnwindDetails] unwind_details details of the conflict just unwound from + # @return [void] + private def filter_possibilities_for_primary_unwind(unwind_details) + unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index } + unwinds_to_state << unwind_details + unwind_requirement_sets = unwinds_to_state.map(&.conflicting_requirements) + + state!.possibilities.reject! do |possibility_set| + possibility_set.possibilities.none? do |poss| + unwind_requirement_sets.any? do |requirements| + possibility_satisfies_requirements?(poss, requirements) + end + end + end + end + + # @param [Object] possibility a single possibility + # @param [Array] requirements an array of requirements + # @return [Boolean] whether the possibility satisfies all of the + # given requirements + private def possibility_satisfies_requirements?(possibility, requirements) + name = name_for(possibility) + + activated.tag(:swap) + activated.set_payload(name, possibility) if activated.vertex_named(name) + satisfied = requirements.all? { |r| requirement_satisfied_by?(r, activated, possibility) } + activated.rewind_to(:swap) + + satisfied + end + + # Filter's a state's possibilities to remove any that would (eventually) + # create a requirement in the conflict we've just rewound from + # @param [UnwindDetails] unwind_details details of the conflict just unwound from + # @return [void] + private def filter_possibilities_for_parent_unwind(unwind_details) + unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index } + unwinds_to_state << unwind_details + + primary_unwinds = unwinds_to_state.select(&.unwinding_to_primary_requirement?).uniq + parent_unwinds = unwinds_to_state.uniq - primary_unwinds + + allowed_possibility_sets = primary_unwinds.flat_map do |unwind| + states[unwind.state_index].possibilities.select do |possibility_set| + possibility_set.possibilities.any? do |poss| + possibility_satisfies_requirements?(poss, unwind.conflicting_requirements) + end + end + end + + requirements_to_avoid = parent_unwinds.flat_map(&.sub_dependencies_to_avoid) + + state!.possibilities.reject! do |possibility_set| + !allowed_possibility_sets.includes?(possibility_set) && + (requirements_to_avoid - possibility_set.dependencies).empty? + end + end + + # @param [Conflict] conflict + # @return [Array] minimal array of requirements that would cause the passed + # conflict to occur. + private def binding_requirements_for_conflict(conflict) + return [conflict.requirement] if conflict.possibility.nil? + + possible_binding_requirements = conflict.requirements.values.flatten.uniq + + # When there’s a `CircularDependency` error the conflicting requirement + # (the one causing the circular) won’t be `conflict.requirement` + # (which won’t be for the right state, because we won’t have created it, + # because it’s circular). + # We need to make sure we have that requirement in the conflict’s list, + # otherwise we won’t be able to unwind properly, so we just return all + # the requirements for the conflict. + return possible_binding_requirements if conflict.underlying_error + + possibilities = search_for(conflict.requirement) + + # If all the requirements together don't filter out all possibilities, + # then the only two requirements we need to consider are the initial one + # (where the dependency's version was first chosen) and the last + if binding_requirement_in_set?(nil, possible_binding_requirements, possibilities) + return [conflict.requirement, requirement_for_existing_name(name_for(conflict.requirement))].compact + end + + # Loop through the possible binding requirements, removing each one + # that doesn't bind. Use a `reverse_each` as we want the earliest set of + # binding requirements, and don't use `reject!` as we wish to refine the + # array *on each iteration*. + binding_requirements = possible_binding_requirements.dup + possible_binding_requirements.reverse_each do |req| + next if req == conflict.requirement + unless binding_requirement_in_set?(req, binding_requirements, possibilities) + binding_requirements -= [req] + end + end + + binding_requirements + end + + # @param [Object] requirement we wish to check + # @param [Array] possible_binding_requirements array of requirements + # @param [Array] possibilities array of possibilities the requirements will be used to filter + # @return [Boolean] whether or not the given requirement is required to filter + # out all elements of the array of possibilities. + private def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities) + possibilities.any? do |poss| + possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement]) + end + end + + # @param [Object] requirement + # @return [Object] the requirement that led to `requirement` being added + # to the list of requirements. + private def parent_of(requirement) + return unless requirement + return unless index = @parents_of[requirement].last? + return unless parent_state = @states[index] + parent_state.requirement + end + + # @param [String] name + # @return [Object] the requirement that led to a version of a possibility + # with the given name being activated. + private def requirement_for_existing_name(name) + return nil unless vertex = activated.vertex_named(name) + return nil unless vertex.payload + states.find { |s| s.name == name }.not_nil!.requirement + end + + # @param [Object] requirement + # @return [ResolutionState] the state whose `requirement` is the given + # `requirement`. + private def find_state_for(requirement) + return nil unless requirement + states.find { |i| requirement == i.requirement } + end + + # @param [Object] underlying_error + # @return [Conflict] a {Conflict} that reflects the failure to activate + # the {#possibility} in conjunction with the current {#state} + private def create_conflict(underlying_error = nil) + vertex = activated.vertex_named!(name) + locked_requirement = locked_requirement_named(name) + + requirements = Hash(String | S, Array(R)).new + unless vertex.explicit_requirements.empty? + requirements[name_for_explicit_dependency_source] = vertex.explicit_requirements + end + requirements[name_for_locking_dependency_source] = [locked_requirement] if locked_requirement + vertex.incoming_edges.each do |edge| + (requirements[check_possibility_set(edge.origin).latest_version] ||= [] of R).unshift(edge.requirement) + end + + activated_by_name = {} of String => S + activated.each { |v| activated_by_name[v.name] = check_possibility_set(v).latest_version if v.payload } + conflicts[name.not_nil!] = Conflict(R, S).new( + requirement.not_nil!, + requirements, + if vertex.payload + check_possibility_set(vertex).latest_version + end, + possibilities.last?, + locked_requirement, + requirement_trees, + activated_by_name, + underlying_error + ) + end + + # @return [Array>] The different requirement + # trees that led to every requirement for the current spec. + private def requirement_trees + vertex = activated.vertex_named!(name) + vertex.requirements.map { |r| requirement_tree_for(r) } + end + + # @param [Object] requirement + # @return [Array] the list of requirements that led to + # `requirement` being required. + private def requirement_tree_for(requirement) + tree = [] of R + while requirement + tree.unshift(requirement) + requirement = parent_of(requirement) + end + tree + end + + @progress_rate : Float64? + + # Indicates progress roughly once every second + # @return [void] + def indicate_progress + @iteration_counter += 1 + # @progress_rate ||= resolver_ui.progress_rate + # if iteration_rate.nil? + # if Time.now - @started_at.not_nil! >= @progress_rate.not_nil! + # self.iteration_rate = @iteration_counter + # end + # end + + # if iteration_rate && (@iteration_counter % iteration_rate) == 0 + # resolver_ui.indicate_progress + # end + end + + # Calls the {#resolver_ui}'s {UI#debug} method + # @param [Integer] depth the depth of the {#states} stack + # @param [Proc] block a block that yields a {#to_s} + # @return [void] + private def debug(depth = 0) + resolver_ui.debug(depth) { yield } + end + + # Attempts to activate the current {#possibility} + # @return [void] + private def attempt_to_activate + debug(depth) { "Attempting to activate " + possibility.to_s } + existing_vertex = activated.vertex_named!(name) + if existing_vertex.payload + debug(depth) { "Found existing spec (#{existing_vertex.payload})" } + attempt_to_filter_existing_spec(existing_vertex) + else + latest = possibility.latest_version + possibility.possibilities.select! do |possibility| + requirement_satisfied_by?(requirement.not_nil!, activated.not_nil!, possibility) + end + if !possibility.latest_version? + # ensure there's a possibility for better error messages + possibility.possibilities << latest if latest + create_conflict + unwind_for_conflict + else + activate_new_spec + end + end + end + + # Attempts to update the existing vertex's `PossibilitySet` with a filtered version + # @return [void] + private def attempt_to_filter_existing_spec(vertex) + filtered_set = filtered_possibility_set(vertex) + if !filtered_set.possibilities.empty? + activated.set_payload(name.not_nil!, filtered_set) + new_requirements = requirements.dup + push_state_for_requirements(new_requirements, false) + else + create_conflict + debug(depth) { "Unsatisfied by existing spec (#{vertex.payload})" } + unwind_for_conflict + end + end + + # Generates a filtered version of the existing vertex's `PossibilitySet` using the + # current state's `requirement` + # @param [Object] vertex existing vertex + # @return [PossibilitySet] filtered possibility set + private def filtered_possibility_set(vertex) + payload = check_possibility_set(vertex) + PossibilitySet(R, S).new(payload.dependencies, payload.possibilities & possibility.possibilities) + end + + # @param [String] requirement_name the spec name to search for + # @return [Object] the locked spec named `requirement_name`, if one + # is found on {#base} + private def locked_requirement_named(requirement_name) + vertex = base.vertex_named(requirement_name) + vertex && vertex.payload + end + + # Add the current {#possibility} to the dependency graph of the current + # {#state} + # @return [void] + private def activate_new_spec + conflicts.delete(name) + debug(depth) { "Activated #{name} at #{possibility}" } + activated.set_payload(name.not_nil!, possibility) + require_nested_dependencies_for(possibility) + end + + # Requires the dependencies that the recently activated spec has + # @param [Object] possibility_set the PossibilitySet that has just been + # activated + # @return [void] + private def require_nested_dependencies_for(possibility_set) + nested_dependencies = dependencies_for(possibility_set.latest_version) + debug(depth) { "Requiring nested dependencies (#{nested_dependencies.join(", ")})" } + nested_dependencies.each do |d| + activated.add_child_vertex(name_for(d), nil, [name_for(possibility_set.latest_version)], d) + parent_index = states.size - 1 + parents = @parents_of[d] + parents << parent_index if parents.empty? + end + + push_state_for_requirements(requirements + nested_dependencies, !nested_dependencies.empty?) + end + + # Pushes a new {DependencyState} that encapsulates both existing and new + # requirements + # @param [Array] new_requirements + # @param [Boolean] requires_sort + # @param [Object] new_activated + # @return [void] + private def push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated) + new_requirements = sort_dependencies(new_requirements.uniq, new_activated, conflicts) if requires_sort + new_requirement = nil + loop do + new_requirement = new_requirements.shift? + break if new_requirement.nil? || states.none? { |s| s.requirement == new_requirement } + end + new_name = new_requirement ? name_for(new_requirement) : "" + possibilities = possibilities_for_requirement(new_requirement) + handle_missing_or_push_dependency_state DependencyState(R, S).new( + new_name, new_requirements, new_activated, + new_requirement, possibilities, depth, conflicts.dup, unused_unwind_options.dup + ) + end + + # Checks a proposed requirement with any existing locked requirement + # before generating an array of possibilities for it. + # @param [Object] requirement the proposed requirement + # @param [Object] activated + # @return [Array] possibilities + private def possibilities_for_requirement(requirement, activated = self.activated) + return [] of PossibilitySet(R, S) unless requirement + if locked_requirement_named(name_for(requirement)) + return locked_requirement_possibility_set(requirement, activated) + end + + group_possibilities(search_for(requirement)) + end + + # @param [Object] requirement the proposed requirement + # @param [Object] activated + # @return [Array] possibility set containing only the locked requirement, if any + private def locked_requirement_possibility_set(requirement, activated = self.activated) + all_possibilities = search_for(requirement) + locked_requirement = locked_requirement_named(name_for(requirement)).not_nil! + + # Longwinded way to build a possibilities array with either the locked + # requirement or nothing in it. Required, since the API for + # locked_requirement isn't guaranteed. + locked_possibilities = all_possibilities.select do |possibility| + requirement_satisfied_by?(locked_requirement, activated, possibility) + end + + group_possibilities(locked_possibilities) + end + + # Build an array of PossibilitySets, with each element representing a group of + # dependency versions that all have the same sub-dependency version constraints + # and are contiguous. + # @param [Array] possibilities an array of possibilities + # @return [Array] an array of possibility sets + private def group_possibilities(possibilities) + possibility_sets = [] of PossibilitySet(R, S) + current_possibility_set = nil + + possibilities.reverse_each do |possibility| + dependencies = dependencies_for(possibility) + if current_possibility_set && current_possibility_set.dependencies == dependencies + current_possibility_set.possibilities.unshift(possibility) + else + possibility_sets.unshift(PossibilitySet(R, S).new(dependencies, [possibility])) + current_possibility_set = possibility_sets.first + end + end + + possibility_sets + end + + # Pushes a new {DependencyState}. + # If the {#specification_provider} says to + # {SpecificationProvider#allow_missing?} that particular requirement, and + # there are no possibilities for that requirement, then `state` is not + # pushed, and the vertex in {#activated} is removed, and we continue + # resolving the remaining requirements. + # @param [DependencyState] state + # @return [void] + private def handle_missing_or_push_dependency_state(state) + if (req = state.requirement) && state.possibilities.empty? && allow_missing?(req) + state.activated.detach_vertex_named(state.name.not_nil!) + push_state_for_requirements(state.requirements.dup, false, state.activated) + else + states.push(state).tap { activated.tag(state) } + end + end + + private def check_possibility_set(vertex) + payload = vertex.payload + raise "BUG: unexpected payload: #{payload}" unless payload.is_a?(PossibilitySet) + payload + end + end + end +end diff --git a/lib/molinillo/src/molinillo/resolver.cr b/lib/molinillo/src/molinillo/resolver.cr new file mode 100644 index 00000000..cce86fe2 --- /dev/null +++ b/lib/molinillo/src/molinillo/resolver.cr @@ -0,0 +1,41 @@ +# require "./resolution" + +module Molinillo + # This class encapsulates a dependency resolver. + # The resolver is responsible for determining which set of dependencies to + # activate, with feedback from the {#specification_provider} + # + # + class Resolver(R, S) + # @return [SpecificationProvider] the specification provider used + # in the resolution process + getter specification_provider : SpecificationProvider(R, S) + + # @return [UI] the UI module used to communicate back to the user + # during the resolution process + getter resolver_ui : UI + + # Initializes a new resolver. + # @param [SpecificationProvider] specification_provider + # see {#specification_provider} + # @param [UI] resolver_ui + # see {#resolver_ui} + def initialize(@specification_provider, @resolver_ui) + end + + # Resolves the requested dependencies into a {DependencyGraph}, + # locking to the base dependency graph (if specified) + # @param [Array] requested an array of 'requested' dependencies that the + # {#specification_provider} can understand + # @param [DependencyGraph,nil] base the base dependency graph to which + # dependencies should be 'locked' + def resolve(requested : Array(R), base = DependencyGraph(R, R).new) + Resolution(R, S).new( + specification_provider, + resolver_ui, + requested, + base) + .resolve + end + end +end diff --git a/lib/molinillo/src/molinillo/state.cr b/lib/molinillo/src/molinillo/state.cr new file mode 100644 index 00000000..45eb2061 --- /dev/null +++ b/lib/molinillo/src/molinillo/state.cr @@ -0,0 +1,64 @@ +module Molinillo + # A state that a {Resolution} can be in + # @attr [String] name the name of the current requirement + # @attr [Array] requirements currently unsatisfied requirements + # @attr [DependencyGraph] activated the graph of activated dependencies + # @attr [Object] requirement the current requirement + # @attr [Object] possibilities the possibilities to satisfy the current requirement + # @attr [Integer] depth the depth of the resolution + # @attr [Hash] conflicts unresolved conflicts, indexed by dependency name + # @attr [Array] unused_unwind_options unwinds for previous conflicts that weren't explored + class ResolutionState(R, S) + property name : String? + property requirements : Array(R) + property activated : DependencyGraph(Resolver::Resolution::PossibilitySet(R, S)? | S, R) + property requirement : R? + property possibilities : Array(Resolver::Resolution::PossibilitySet(R, S)) + property depth : Int32 + property conflicts : Hash(String, Resolver::Resolution::Conflict(R, S)) + property unused_unwind_options : Array(Resolver::Resolution::UnwindDetails(R, S)) + + def initialize(@name, @requirements, @activated, @requirement, + @possibilities, @depth, @conflicts, @unused_unwind_options) + end + + # Returns an empty resolution state + # @return [ResolutionState] an empty state + def self.empty + new(nil, Array(R).new, DependencyGraph(Resolver::Resolution::PossibilitySet(R, S)? | S, R).new, nil, + Array(Resolver::Resolution::PossibilitySet(R, S)).new, 0, Hash(String, Resolver::Resolution::Conflict(R, S)).new, Array(Resolver::Resolution::UnwindDetails(R, S)).new) + end + end + + # A state that encapsulates a set of {#requirements} with an {Array} of + # possibilities + class DependencyState(R, S) < ResolutionState(R, S) + # Removes a possibility from `self` + # @return [PossibilityState] a state with a single possibility, + # the possibility that was removed from `self` + def pop_possibility_state + new_pos = if possibilities.size > 0 + [possibilities.pop] + else + [] of Resolver::Resolution::PossibilitySet(R, S) + end + PossibilityState(R, S).new( + name, + requirements.dup, + activated, + requirement, + new_pos, + depth + 1, + conflicts.dup, + unused_unwind_options.dup + ).tap do |state| + state.activated.tag(state) + end + end + end + + # A state that encapsulates a single possibility to fulfill the given + # {#requirement} + class PossibilityState(R, S) < ResolutionState(R, S) + end +end From e74e050020790f05e345ee6939dc80aee180d407 Mon Sep 17 00:00:00 2001 From: "renovate[bot]" <29139614+renovate[bot]@users.noreply.github.com> Date: Sat, 15 Mar 2025 11:01:24 +0100 Subject: [PATCH 5/7] Update actions/checkout action to v4 (#670) Co-authored-by: renovate[bot] <29139614+renovate[bot]@users.noreply.github.com> --- lib/molinillo/.github/workflows/crystal.yml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/molinillo/.github/workflows/crystal.yml b/lib/molinillo/.github/workflows/crystal.yml index 49c8d4f6..a6eeb08e 100644 --- a/lib/molinillo/.github/workflows/crystal.yml +++ b/lib/molinillo/.github/workflows/crystal.yml @@ -11,7 +11,7 @@ jobs: image: crystallang/crystal steps: - - uses: actions/checkout@v2 + - uses: actions/checkout@v4 - name: Install dependencies run: shards install - name: Run tests From 76db9e2b96fb838e46711dc7e8e6cb549642d4a3 Mon Sep 17 00:00:00 2001 From: Michael Nikitochkin Date: Wed, 4 Jun 2025 09:34:58 +0200 Subject: [PATCH 6/7] Show the package name associated with shard errors (#674) --- spec/integration/install_spec.cr | 2 +- src/cli.cr | 4 ++-- src/package.cr | 2 +- 3 files changed, 4 insertions(+), 4 deletions(-) diff --git a/spec/integration/install_spec.cr b/spec/integration/install_spec.cr index 4b08ed0a..981f0684 100644 --- a/spec/integration/install_spec.cr +++ b/spec/integration/install_spec.cr @@ -855,7 +855,7 @@ describe "install" do with_shard(metadata) do ex = expect_raises(FailedCommand) { run "shards install --no-color" } ex.stdout.should contain <<-ERROR - E: Could not find executable "nonexistent" + E: Could not find executable "nonexistent" for "executable_missing" ERROR end end diff --git a/src/cli.cr b/src/cli.cr index 0ace4160..a0e87a2f 100644 --- a/src/cli.cr +++ b/src/cli.cr @@ -176,12 +176,12 @@ end begin Shards.run rescue ex : OptionParser::InvalidOption - Shards::Log.fatal { ex.message } + Shards::Log.fatal(exception: ex) { ex.message } exit 1 rescue ex : Shards::ParseError ex.to_s(STDERR) exit 1 rescue ex : Shards::Error - Shards::Log.error { ex.message } + Shards::Log.error(exception: ex) { ex.message } exit 1 end diff --git a/src/package.cr b/src/package.cr index 09f8a70b..08fa6219 100644 --- a/src/package.cr +++ b/src/package.cr @@ -114,7 +114,7 @@ module Shards spec.executables.each do |name| exe_name = find_executable_file(Path[install_path], name) unless exe_name - raise Shards::Error.new("Could not find executable #{name.inspect}") + raise Shards::Error.new("Could not find executable #{name.inspect} for #{@name.inspect}") end Log.debug { "Install #{exe_name}" } source = File.join(install_path, exe_name) From a25e2aba75c928d7ba30d25b8c81a1933ca08f1e Mon Sep 17 00:00:00 2001 From: Michael Nikitochkin Date: Thu, 5 Jun 2025 09:13:34 +0200 Subject: [PATCH 7/7] Add dependency name in the logs (#676) In certain cases, it's unclear which package causes an error during shard installation. The log output now indicates the package context for each message. ``` Fetching https://github.com/sija/retriable.cr.git [retriable] git config --get remote.origin.mirror [nbchannel] git fetch --all --quiet [splay_tree_map] git fetch --all --quiet ``` --- spec/integration/install_spec.cr | 3 +- src/commands/prune.cr | 11 +++--- src/logger.cr | 7 ++-- src/molinillo_solver.cr | 39 +++++++++++++--------- src/package.cr | 57 ++++++++++++++++++-------------- 5 files changed, 70 insertions(+), 47 deletions(-) diff --git a/spec/integration/install_spec.cr b/spec/integration/install_spec.cr index 981f0684..66a8e160 100644 --- a/spec/integration/install_spec.cr +++ b/spec/integration/install_spec.cr @@ -925,7 +925,8 @@ describe "install" do with_shard(metadata) do stdout = run "shards install --no-color -v" assert_installed "noshardyml", "0.2.0" - stdout.should contain(%(D: Missing "shard.yml" for "noshardyml" at tag v0.1.0)) + stdout.should contain(%(D: [noshardyml] git ls-tree -r --full-tree --name-only refs/tags/v0.1.0 -- shard.yml)) + stdout.should contain(%(D: [noshardyml] Missing "shard.yml" for "noshardyml" at tag v0.1.0)) end end diff --git a/src/commands/prune.cr b/src/commands/prune.cr index eb397cb6..12499e45 100644 --- a/src/commands/prune.cr +++ b/src/commands/prune.cr @@ -13,11 +13,14 @@ module Shards next unless File.directory?(path) if locks.shards.none? { |d| d.name == name } - Log.debug { "rm -rf '#{Process.quote(path)}'" } - Shards::Helpers.rm_rf(path) + Log.with_context do + Log.context.set package: name + Log.debug { "rm -rf '#{Process.quote(path)}'" } + Shards::Helpers.rm_rf(path) - Shards.info.installed.delete(name) - Log.info { "Pruned #{File.join(File.basename(Shards.install_path), name)}" } + Shards.info.installed.delete(name) + Log.info { "Pruned #{File.join(File.basename(Shards.install_path), name)}" } + end end end diff --git a/src/logger.cr b/src/logger.cr index 51bc751e..95680588 100644 --- a/src/logger.cr +++ b/src/logger.cr @@ -30,8 +30,9 @@ module Shards FORMATTER = ::Log::Formatter.new do |entry, io| message = entry.message - + package_name = entry.context[:package]? if @@colors + io << "[" << package_name.colorize(:blue).to_s << "] " if package_name && entry.severity <= ::Log::Severity::Debug io << if color = LOGGER_COLORS[entry.severity]? if idx = message.index(' ') message[0...idx].colorize(color).to_s + message[idx..-1] @@ -42,7 +43,9 @@ module Shards message end else - io << entry.severity.label[0] << ": " << message + io << entry.severity.label[0] << ": " + io << "[" << package_name << "] " if package_name && entry.severity <= ::Log::Severity::Debug + io << message end end end diff --git a/src/molinillo_solver.cr b/src/molinillo_solver.cr index 9c2fffdd..4af8b502 100644 --- a/src/molinillo_solver.cr +++ b/src/molinillo_solver.cr @@ -61,7 +61,10 @@ module Shards end spawn do begin - dep.resolver.update_local_cache if dep.resolver.is_a? GitResolver + Log.with_context do + Log.context.set package: dep.name + dep.resolver.update_local_cache if dep.resolver.is_a? GitResolver + end ch.send(nil) rescue ex : Exception ch.send(ex) @@ -81,9 +84,12 @@ module Shards prefetch_local_caches(deps) deps.each do |dep| - if lock = lock_index[dep.name]? - next unless dep.matches?(lock.version) - add_lock(base, lock_index, dep) + Log.with_context do + Log.context.set package: dep.name + if lock = lock_index[dep.name]? + next unless dep.matches?(lock.version) + add_lock(base, lock_index, dep) + end end end end @@ -170,20 +176,23 @@ module Shards @specs = Hash({String, Version}, Spec).new def search_for(dependency : R) : Array(S) - check_single_resolver_by_name dependency.resolver - - @search_results[{dependency.name, dependency.requirement}] ||= begin - resolver = dependency.resolver - versions = Versions.sort(versions_for(dependency, resolver)).reverse - result = versions.map do |version| - @specs[{dependency.name, version}] ||= begin - resolver.spec(version).tap do |spec| - spec.version = version + Log.with_context do + Log.context.set package: dependency.name + check_single_resolver_by_name dependency.resolver + + @search_results[{dependency.name, dependency.requirement}] ||= begin + resolver = dependency.resolver + versions = Versions.sort(versions_for(dependency, resolver)).reverse + result = versions.map do |version| + @specs[{dependency.name, version}] ||= begin + resolver.spec(version).tap do |spec| + spec.version = version + end end end - end - result + result + end end end diff --git a/src/package.cr b/src/package.cr index 08fa6219..df0c4f64 100644 --- a/src/package.cr +++ b/src/package.cr @@ -58,15 +58,19 @@ module Shards end def install - cleanup_install_directory + Log.with_context do + Log.context.set package: name + + cleanup_install_directory - # install the shard: - resolver.install_sources(version, install_path) + # install the shard: + resolver.install_sources(version, install_path) - # link the project's lib path as the shard's lib path, so the dependency - # can access transitive dependencies: - unless resolver.is_a?(PathResolver) - install_lib_path + # link the project's lib path as the shard's lib path, so the dependency + # can access transitive dependencies: + unless resolver.is_a?(PathResolver) + install_lib_path + end end Shards.info.installed[name] = self @@ -111,24 +115,27 @@ module Shards Dir.mkdir_p(Shards.bin_path) - spec.executables.each do |name| - exe_name = find_executable_file(Path[install_path], name) - unless exe_name - raise Shards::Error.new("Could not find executable #{name.inspect} for #{@name.inspect}") - end - Log.debug { "Install #{exe_name}" } - source = File.join(install_path, exe_name) - destination = File.join(Shards.bin_path, File.basename(exe_name)) - - if File.exists?(destination) - next if File.same?(destination, source) - File.delete(destination) - end - - begin - File.link(source, destination) - rescue File::Error - FileUtils.cp(source, destination) + Log.with_context do + Log.context.set package: name + spec.executables.each do |name| + exe_name = find_executable_file(Path[install_path], name) + unless exe_name + raise Shards::Error.new("Could not find executable #{name.inspect} for #{@name.inspect}") + end + Log.debug { "Install #{exe_name}" } + source = File.join(install_path, exe_name) + destination = File.join(Shards.bin_path, File.basename(exe_name)) + + if File.exists?(destination) + next if File.same?(destination, source) + File.delete(destination) + end + + begin + File.link(source, destination) + rescue File::Error + FileUtils.cp(source, destination) + end end end end