Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

depsolver w/ conflict resolution work in progress

  • Loading branch information...
commit f28a2d1d2029ef6e9ede4a3e9a3a5168373744a4 1 parent b5854bd
@rtomayko authored
Showing with 204 additions and 19 deletions.
  1. +137 −0 doc/depsolver.md
  2. +63 −15 rpg-prepare.sh
  3. +2 −2 rpg-sh-setup.sh
  4. +2 −2 rpg-solve.sh
View
137 doc/depsolver.md
@@ -0,0 +1,137 @@
+Dependency Solving
+==================
+
+## Stuff
+
+#### Package Lists
+
+A package list is a simple text file where each line specifies a package
+matching rule. It looks like this:
+
+ <source> <SP> <package> <SP> <verspec> <SP> <version> <NL>
+
+The `<package>` is the package name, `<version>` is the package version, and
+`<verspec>` is one of: `<`, `<=`, `=`, `>=`, or `>`. The `<source>` field
+specifies where the requirement originated. This can be a package name (in case
+of dependencies), `~user` (in case of user install), or `-` to denote the
+requirement has no source or the source is unimportant.
+
+Example:
+
+ ~user rails > 2.2
+ ~user sinatra >= 0
+ rails activesupport = 2.2
+ rails activerecord = 2.2
+ sinatra rack >= 1.0
+ rails rack >= 1.0.1
+
+#### Package Indexes
+
+A package index is a simple text file where each line specifies a concrete
+package name and version. It looks like this:
+
+ <package> <SP> <version> <NL>
+
+Package indexes are usually sorted by `<package>` and then reverse by
+`<version>`. This allows efficient lookups for many packages in a single pass
+over a file.
+
+## How Dependencies and Conflicts are Solved
+
+### 1. Build Master Package List
+
+Build a standard format package list from all packages provided on the command
+line with `rpg-package-list(1)`. It looks like this, remember:
+
+ ~user <package> <verspec> <version>
+
+This is the _master package list_.
+
+### 1.5 Build Installed Package Index and Dependency Package List
+
+Build a package index for all packages currently installed on the system with,
+e.g., `rpg-package-index(1)`. This is the _installed package index_.
+
+Build a package list from all dependency lists of all installed packages
+*except* those that are included in the master package list. This is called the
+_existing dependency package list_
+
+ <source> <package> <verspec> <version>
+
+It's important that lines whose `<source>` is a package existing in the master
+package list are excluded. Otherwise, the dependency rules for already installed
+packages will constrain the resolver.
+
+### 2. Resolve Package Versions
+
+Concatenate the master package list and the installed package list through `rpg-solve(1)` to find the best versions of
+each package based on its requirements. The output is a concrete package index
+called the *solved package index*:
+
+ rails 2.3.1
+ sinatra 0.9.6
+
+The package index files passed into `rpg-solve` are as follows:
+
+ 1. The *solved package index*
+ 2. The *installed package index*
+ 3. The *release package index*
+
+If `rpg-install` is in upgrade mode, the *installed package index*
+is not used. This causes the all package rules to be resolved against
+the *release package index*, resulting in all packages included in the
+*master package list* being upgraded to the most recent compatible
+version.
+
+### 3. Register Packages
+
+Fetch each package in the *solved package index* with `rpg-fetch(1)` and
+register the package version in the package database with `rpg-register(1)`.
+
+__NOTE:__ `rpg-register(1)` just loads the packages spec data into the database.
+It doesn't install anything.
+
+### 4. Resolve Package Dependencies
+
+For each package resolved in step 2, add that package's dependencies to the
+master package list. Now maybe the master package list looks like this:
+
+ @user rails > 2.2
+ @user sinatra >= 0
+ sinatra rack > 1.0
+ rails rack >= 1.0.1
+ rails activerecord = 2.2
+
+Notice how there can be multiple entries for a single package in the package
+list. `rpg-solve(1)` returns the best match for a package given all the
+requirements.
+
+### 5. GOTO 2
+
+If the master package list at step 4 has changed from the master package list at
+step 2, go back and continue from step 2: resolve the new master package list
+down to a concrete package index, resolve dependencies, and come back here.
+
+If the master package did not change on this pass, continue on to the next step.
+
+### 6. Conflict Resolution
+
+A number of exceptional conditions can arise at this point:
+
+ 1. A package specified by the user or by dependency does not exist in any
+ package index. This could be due to a stale index or because a package
+ name is wrong.
+
+ 2. A package version meeting all of the criteria specified by the master
+ package list and the existing dependency package list could not be found.
+ This could be due to conflicting dependency specifications in multiple
+ packages.
+
+In either of the cases mentioned above, the `rpg-solve(1)` program will output
+a record whose version is "-". The front-end is then responsible for presenting
+this list to the user in some way. The user should be able to choose what should
+happen.
+
+ 1. Change the version of the package
+ 2. Force the package to be installed anyway (what package? what version?)
+ 3. Abort the installation
View
78 rpg-prepare.sh
@@ -29,6 +29,12 @@ packlist="$sessiondir"/package-list
rm -rf "$sessiondir"
mkdir -p "$sessiondir"
+# see if we need to sync the index
+rpg-sync -s
+
+# Master Package List
+# -------------------
+
notice "writing argv"
for arg in "$@"
do echo "$arg"
@@ -36,10 +42,30 @@ done > "$sessiondir"/argv
notice "writing user package-list"
rpg-package-list "$@" |
+sort -u |
sed "s/^/@user /" > "$packlist"
-# see if we need to sync the index
-rpg-sync -s
+# Installed Index and Existing Dependencies Package List
+# ------------------------------------------------------
+
+notice "creating installed packages index"
+rpg-package-index > "$sessiondir"/installed-index
+
+# TODO write package name in deps file so this can be a straight cat
+notice "create existing dependencies package list"
+for deps in "$RPGDB"/*/active/dependencies
+do
+ pack=$(basename ${deps%/active/dependencies})
+ grep ^runtime < "$deps" |
+ sed "s|^runtime|$pack|"
+done |
+sort -u |
+join -11 -22 -v 1 -o 1.1,1.2,1.3,1.4 - "$packlist" |
+tee "$sessiondir/installed-deps" |
+sort -k 2,4 > "$sessiondir/installed-deps-packs"
+
+# Dependency Resolution
+# ---------------------
# Tell the user we're about to begin.
numpacks=$(sed -n '$=' <"$packlist")
@@ -49,6 +75,8 @@ then packname=$(head -1 "$packlist" | cut -d ' ' -f 2)
else heed "calculating dependencies for $numpacks package(s) ..."
fi
+cat </dev/null >"$sessiondir"/solved
+
changed=true
runcount=0
while $changed
@@ -57,10 +85,27 @@ do
notice "this is depsolve run #$runcount"
cat </dev/null >"$packlist+"
- cut -d ' ' -f 2- "$packlist" |
- rpg-solve -u "$sessiondir/solved" |
+ # rebuild deps package list
+ if test -f "$sessiondir/solved"
+ then
+ join -v 2 -o 2.1,2.2,2.3,2.4 "$sessiondir/solved" "$sessiondir"/installed-deps |
+ tee "$sessiondir/installed-deps+" |
+ sort -k 2,4 > "$sessiondir/installed-deps-packs"
+ mv "$sessiondir"/installed-deps+ "$sessiondir"/installed-deps
+ fi
+
+ # add deps for installed packages
+ join -12 -22 -o 2.1,2.2,2.3,2.4 \
+ "$packlist" "$sessiondir"/installed-deps-packs |
+ cat "$packlist" - |
+ tee "$sessiondir"/merged-package-list |
+ cut -d ' ' -f 2- |
+ sort -u |
+ rpg-solve -u "$sessiondir/solved" \
+ "$sessiondir/installed-index" |
sort -b |
tee "$sessiondir/solved+" |
+ grep -v -- ' -$' |
xargs -P 4 -n 2 rpg-fetch >/dev/null
mv "$sessiondir/solved+" "$sessiondir/solved"
@@ -68,29 +113,32 @@ do
cat "$sessiondir/solved" |
while read package version
do
+ test "$version" = '-' && { cat "$packlist"; continue; }
gemfile=$(rpg-fetch "$package" "$version")
packagedir=$(rpg-package-register "$gemfile")
notice "adding $package $version deps to packlist"
grep '^runtime ' < "$packagedir"/dependencies |
- cut -d ' ' -f 2- |
- sed "s/^/$package /" |
+ sed "s/^runtime/$package/" |
cat "$packlist" -
done |
sort -b -u -k 2,4 >> "$packlist+"
if cmp -s "$packlist" "$packlist+"
- then
- notice "package list did not change"
- changed=false
- else
- notice "package list changed"
- changed=true
+ then notice "package list did not change"
+ changed=false
+ else notice "package list changed"
+ changed=true
fi
mv "$packlist+" "$packlist"
done
# Tell the user we're about to begin.
-numpacks=$(sed -n '$=' <"$packlist")
-heed "$numpacks package(s) ready for installation:
-$(cat "$sessiondir"/solved)"
+if badpacks=$(grep '\-$' <"$sessiondir"/solved)
+then heed "$(echo "$badpacks" |sed -n '$=') package(s) failed to resolve:
+$badpacks"
+fi
+
+goodpacks=$(grep -v -- '\-$' <"$sessiondir"/solved)
+heed "$(echo "$goodpacks" |sed -n '$=') package(s) ready for installation:
+$goodpacks"
View
4 rpg-sh-setup.sh
@@ -348,8 +348,8 @@ warn () { echo "$PROGNAME:" "$@" 1>&2; }
# Write an informationational message to stderr prefixed with the name
# of the current script. Don't use this, use `notice`.
heed () {
- printf "%20s %s\n" "${PROGNAME#rpg-}:" "$*" |
- sed 's/^\([^ ]\)/ \1/' 1>&2
+ printf "%17s %s\n" "${PROGNAME#rpg-}:" "$*" |
+ sed 's/^\([^ ]\)/ \1/' 1>&2
}
# We rewite the `notice` function to `head` if `RPGVERBOSE` is enabled
View
4 rpg-solve.sh
@@ -10,7 +10,7 @@ set -e
ARGV="$@"
USAGE '${PROGNAME} [-u] [<index>]...
Reads a package list on standard input and resolves to a list of concrete
-versions using the <index> specified. Multiple <index> arguments are
+versions using the <index>(es) specified. Multiple <index> arguments are
allowed. The main release index is used by default.
Options
@@ -51,7 +51,7 @@ resolve () {
if ! $found
then failed=$(( $failed + 1 ))
failedpacks="$failedpacks, $current"
- echo "$current != *"
+ echo "$current -"
notice "failed to resolve $current $expression"
fi
current=
Please sign in to comment.
Something went wrong with that request. Please try again.