diff --git a/lib/compiler/implementation/lib/web.dart b/lib/compiler/implementation/lib/web.dart
new file mode 100644
index 0000000..a75db7b
--- /dev/null
+++ b/lib/compiler/implementation/lib/web.dart
@@ -0,0 +1,9 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+#library("web");
+
+String htmlEscape(String text) {
+  throw "Unimplemented: web::htmlEscape(String).";
+}
diff --git a/lib/compiler/implementation/lib/web.dartp b/lib/compiler/implementation/lib/web.dartp
new file mode 100644
index 0000000..c3ba2ad
--- /dev/null
+++ b/lib/compiler/implementation/lib/web.dartp
@@ -0,0 +1,13 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// Patch file for dart:web
+
+/*patch*/ String htmlEscape(String text) {
+  return text.replaceAll("&", "&amp;")
+             .replaceAll("<", "&lt;")
+             .replaceAll(">", "&gt;")
+             .replaceAll('"', "&quot;")
+             .replaceAll("'", "&apos;");  // Different from original.
+}
diff --git a/lib/dom/templates/html/dartium/factoryprovider__Elements.darttemplate b/lib/dom/templates/html/dartium/factoryprovider__Elements.darttemplate
new file mode 100644
index 0000000..8fe27e5
--- /dev/null
+++ b/lib/dom/templates/html/dartium/factoryprovider__Elements.darttemplate
@@ -0,0 +1,7 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+class _Elements {
+
+$!FACTORY_METHODS}
diff --git a/lib/dom/templates/html/dartium/impl_EventTarget.darttemplate b/lib/dom/templates/html/dartium/impl_EventTarget.darttemplate
new file mode 100644
index 0000000..1b4a00d
--- /dev/null
+++ b/lib/dom/templates/html/dartium/impl_EventTarget.darttemplate
@@ -0,0 +1,106 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+class _EventsImpl implements Events {
+  // TODO(podivilov): add type.
+  final _ptr;
+
+  final Map<String, EventListenerList> _listenerMap;
+
+  _EventsImpl(this._ptr) : _listenerMap = <EventListenerList>{};
+
+  EventListenerList operator [](String type) {
+    return _listenerMap.putIfAbsent(type,
+      () => new _EventListenerListImpl(_ptr, type));
+  }
+}
+
+class _EventListenerWrapper {
+  final EventListener raw;
+  final Function wrapped;
+  final bool useCapture;
+  _EventListenerWrapper(this.raw, this.wrapped, this.useCapture);
+}
+
+class _EventListenerListImpl implements EventListenerList {
+  // TODO(podivilov): add type.
+  final _ptr;
+  final String _type;
+  List<_EventListenerWrapper> _wrappers;
+
+  _EventListenerListImpl(this._ptr, this._type) :
+    // TODO(jacobr): switch to <_EventListenerWrapper>[] when the VM allow it.
+    _wrappers = new List<_EventListenerWrapper>();
+
+  EventListenerList add(EventListener listener, [bool useCapture = false]) {
+    _add(listener, useCapture);
+    return this;
+  }
+
+  EventListenerList remove(EventListener listener, [bool useCapture = false]) {
+    _remove(listener, useCapture);
+    return this;
+  }
+
+  bool dispatch(Event evt) {
+    // TODO(jacobr): what is the correct behavior here. We could alternately
+    // force the event to have the expected type.
+    assert(evt.type == _type);
+    return _ptr.$dom_dispatchEvent(evt);
+  }
+
+  void _add(EventListener listener, bool useCapture) {
+    _ptr.$dom_addEventListener(_type,
+                          _findOrAddWrapper(listener, useCapture),
+                          useCapture);
+  }
+
+  void _remove(EventListener listener, bool useCapture) {
+    Function wrapper = _removeWrapper(listener, useCapture);
+    if (wrapper !== null) {
+      _ptr.$dom_removeEventListener(_type, wrapper, useCapture);
+    }
+  }
+
+  Function _removeWrapper(EventListener listener, bool useCapture) {
+    if (_wrappers === null) {
+      return null;
+    }
+    for (int i = 0; i < _wrappers.length; i++) {
+      _EventListenerWrapper wrapper = _wrappers[i];
+      if (wrapper.raw === listener && wrapper.useCapture == useCapture) {
+        // Order doesn't matter so we swap with the last element instead of
+        // performing a more expensive remove from the middle of the list.
+        if (i + 1 != _wrappers.length) {
+          _wrappers[i] = _wrappers.removeLast();
+        } else {
+          _wrappers.removeLast();
+        }
+        return wrapper.wrapped;
+      }
+    }
+    return null;
+  }
+
+  Function _findOrAddWrapper(EventListener listener, bool useCapture) {
+    if (_wrappers === null) {
+      _wrappers = <_EventListenerWrapper>[];
+    } else {
+      for (_EventListenerWrapper wrapper in _wrappers) {
+        if (wrapper.raw === listener && wrapper.useCapture == useCapture) {
+          return wrapper.wrapped;
+        }
+      }
+    }
+    final wrapped = (e) { listener(e); };
+    _wrappers.add(new _EventListenerWrapper(listener, wrapped, useCapture));
+    return wrapped;
+  }
+}
+
+class $CLASSNAME$EXTENDS$IMPLEMENTS$NATIVESPEC {
+/*
+$!MEMBERS
+*/
+}
diff --git a/lib/dom/templates/html/frog/factoryprovider__Elements.darttemplate b/lib/dom/templates/html/frog/factoryprovider__Elements.darttemplate
new file mode 100644
index 0000000..8fe27e5
--- /dev/null
+++ b/lib/dom/templates/html/frog/factoryprovider__Elements.darttemplate
@@ -0,0 +1,7 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+class _Elements {
+
+$!FACTORY_METHODS}
diff --git a/lib/dom/templates/html/frog/impl_EventTarget.darttemplate b/lib/dom/templates/html/frog/impl_EventTarget.darttemplate
new file mode 100644
index 0000000..893f3d2
--- /dev/null
+++ b/lib/dom/templates/html/frog/impl_EventTarget.darttemplate
@@ -0,0 +1,61 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+class _EventsImpl implements Events {
+  /* Raw event target. */
+  // TODO(jacobr): it would be nice if we could specify this as
+  // _EventTargetImpl or EventTarget
+  final Dynamic _ptr;
+
+  _EventsImpl(this._ptr);
+
+  _EventListenerListImpl operator [](String type) {
+    return new _EventListenerListImpl(_ptr, type);
+  }
+}
+
+class _EventListenerListImpl implements EventListenerList {
+  
+  // TODO(jacobr): make this _EventTargetImpl
+  final Dynamic _ptr;
+  final String _type;
+
+  _EventListenerListImpl(this._ptr, this._type);
+
+  // TODO(jacobr): implement equals.
+
+  _EventListenerListImpl add(EventListener listener,
+      [bool useCapture = false]) {
+    _add(listener, useCapture);
+    return this;
+  }
+
+  _EventListenerListImpl remove(EventListener listener,
+      [bool useCapture = false]) {
+    _remove(listener, useCapture);
+    return this;
+  }
+
+  bool dispatch(Event evt) {
+    // TODO(jacobr): what is the correct behavior here. We could alternately
+    // force the event to have the expected type.
+    assert(evt.type == _type);
+    return _ptr.$dom_dispatchEvent(evt);
+  }
+
+  void _add(EventListener listener, bool useCapture) {
+    _ptr.$dom_addEventListener(_type, listener, useCapture);
+  }
+
+  void _remove(EventListener listener, bool useCapture) {
+    _ptr.$dom_removeEventListener(_type, listener, useCapture);
+  }
+}
+
+
+class $CLASSNAME$EXTENDS$IMPLEMENTS$NATIVESPEC {
+
+  Events get on() => new _EventsImpl(this);
+$!MEMBERS
+}
diff --git a/tools/VERSION b/tools/VERSION
index 453bc99..0a54219 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -1,4 +1,4 @@
 MAJOR 0
-MINOR 1
-BUILD 2
+MINOR 5
+BUILD 12
 PATCH 0
diff --git a/utils/pub/pub.Makefile b/utils/pub/pub.Makefile
new file mode 100644
index 0000000..c1d628d
--- /dev/null
+++ b/utils/pub/pub.Makefile
@@ -0,0 +1,6 @@
+# This file is generated by gyp; do not edit.
+
+export builddir_name ?= dart/utils/pub/out
+.PHONY: all
+all:
+	$(MAKE) -C ../.. pub
diff --git a/utils/pub/pub.target.mk b/utils/pub/pub.target.mk
new file mode 100644
index 0000000..6ddab0c
--- /dev/null
+++ b/utils/pub/pub.target.mk
@@ -0,0 +1,38 @@
+# This file is generated by gyp; do not edit.
+
+TOOLSET := target
+TARGET := pub
+### Rules for action "generate_pub_snapshot":
+quiet_cmd_dart_utils_pub_pub_gyp_pub_target_generate_pub_snapshot = ACTION dart_utils_pub_pub_gyp_pub_target_generate_pub_snapshot $@
+cmd_dart_utils_pub_pub_gyp_pub_target_generate_pub_snapshot = LD_LIBRARY_PATH=$(builddir)/lib.host:$(builddir)/lib.target:$$LD_LIBRARY_PATH; export LD_LIBRARY_PATH; cd utils/pub; mkdir -p $(obj)/gen; "$(builddir)/dart" "--package-root=$(builddir)/packages/" "--generate-script-snapshot=$(obj)/gen/pub.dart.snapshot" ../../sdk/lib/_internal/pub/bin/pub.dart
+
+$(obj)/gen/pub.dart.snapshot: obj := $(abs_obj)
+$(obj)/gen/pub.dart.snapshot: builddir := $(abs_builddir)
+$(obj)/gen/pub.dart.snapshot: TOOLSET := $(TOOLSET)
+$(obj)/gen/pub.dart.snapshot: $(builddir)/dart sdk/lib/_internal/pub/bin/pub.dart sdk/lib/_internal/pub/lib/src/http.dart sdk/lib/_internal/pub/lib/src/utils.dart sdk/lib/_internal/pub/lib/src/git_source.dart sdk/lib/_internal/pub/lib/src/command_install.dart sdk/lib/_internal/pub/lib/src/exit_codes.dart sdk/lib/_internal/pub/lib/src/command.dart sdk/lib/_internal/pub/lib/src/source_registry.dart sdk/lib/_internal/pub/lib/src/pubspec.dart sdk/lib/_internal/pub/lib/src/command_help.dart sdk/lib/_internal/pub/lib/src/oauth2.dart sdk/lib/_internal/pub/lib/src/command_uploader.dart sdk/lib/_internal/pub/lib/src/error_group.dart sdk/lib/_internal/pub/lib/src/directory_tree.dart sdk/lib/_internal/pub/lib/src/sdk.dart sdk/lib/_internal/pub/lib/src/hosted_source.dart sdk/lib/_internal/pub/lib/src/version.dart sdk/lib/_internal/pub/lib/src/git.dart sdk/lib/_internal/pub/lib/src/io.dart sdk/lib/_internal/pub/lib/src/system_cache.dart sdk/lib/_internal/pub/lib/src/safe_http_server.dart sdk/lib/_internal/pub/lib/src/command_update.dart sdk/lib/_internal/pub/lib/src/command_version.dart sdk/lib/_internal/pub/lib/src/validator.dart sdk/lib/_internal/pub/lib/src/command_cache.dart sdk/lib/_internal/pub/lib/src/source.dart sdk/lib/_internal/pub/lib/src/command_lish.dart sdk/lib/_internal/pub/lib/src/package.dart sdk/lib/_internal/pub/lib/src/log.dart sdk/lib/_internal/pub/lib/src/entrypoint.dart sdk/lib/_internal/pub/lib/src/lock_file.dart sdk/lib/_internal/pub/lib/src/path_source.dart sdk/lib/_internal/pub/lib/src/validator/name.dart sdk/lib/_internal/pub/lib/src/validator/size.dart sdk/lib/_internal/pub/lib/src/validator/pubspec_field.dart sdk/lib/_internal/pub/lib/src/validator/compiled_dartdoc.dart sdk/lib/_internal/pub/lib/src/validator/directory.dart sdk/lib/_internal/pub/lib/src/validator/utf8_readme.dart sdk/lib/_internal/pub/lib/src/validator/dependency.dart sdk/lib/_internal/pub/lib/src/validator/license.dart sdk/lib/_internal/pub/lib/src/validator/lib.dart sdk/lib/_internal/pub/lib/src/solver/version_solver.dart sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart sdk/lib/_internal/pub/test/command_line_config.dart sdk/lib/_internal/pub/test/version_test.dart sdk/lib/_internal/pub/test/io_test.dart sdk/lib/_internal/pub/test/pub_cache_test.dart sdk/lib/_internal/pub/test/test_pub.dart sdk/lib/_internal/pub/test/lock_file_test.dart sdk/lib/_internal/pub/test/real_version_test.dart sdk/lib/_internal/pub/test/directory_tree_test.dart sdk/lib/_internal/pub/test/dev_dependency_test.dart sdk/lib/_internal/pub/test/pubspec_test.dart sdk/lib/_internal/pub/test/pub_test.dart sdk/lib/_internal/pub/test/version_solver_test.dart sdk/lib/_internal/pub/test/descriptor.dart sdk/lib/_internal/pub/test/error_group_test.dart sdk/lib/_internal/pub/test/pub_uploader_test.dart sdk/lib/_internal/pub/test/lish/cloud_storage_upload_doesnt_redirect_test.dart sdk/lib/_internal/pub/test/lish/cloud_storage_upload_provides_an_error_test.dart sdk/lib/_internal/pub/test/lish/upload_form_provides_an_error_test.dart sdk/lib/_internal/pub/test/lish/utils.dart sdk/lib/_internal/pub/test/lish/package_creation_provides_a_malformed_error_test.dart sdk/lib/_internal/pub/test/lish/package_validation_has_a_warning_and_is_canceled_test.dart sdk/lib/_internal/pub/test/lish/force_cannot_be_combined_with_dry_run_test.dart sdk/lib/_internal/pub/test/lish/upload_form_fields_is_not_a_map_test.dart sdk/lib/_internal/pub/test/lish/package_creation_provides_invalid_json_test.dart sdk/lib/_internal/pub/test/lish/package_creation_provides_a_malformed_success_test.dart sdk/lib/_internal/pub/test/lish/package_creation_provides_an_error_test.dart sdk/lib/_internal/pub/test/lish/upload_form_is_missing_url_test.dart sdk/lib/_internal/pub/test/lish/force_does_not_publish_if_there_are_errors_test.dart sdk/lib/_internal/pub/test/lish/upload_form_is_missing_fields_test.dart sdk/lib/_internal/pub/test/lish/package_validation_has_an_error_test.dart sdk/lib/_internal/pub/test/lish/preview_package_validation_has_a_warning_test.dart sdk/lib/_internal/pub/test/lish/package_validation_has_a_warning_and_continues_test.dart sdk/lib/_internal/pub/test/lish/force_publishes_if_tests_are_no_warnings_or_errors_test.dart sdk/lib/_internal/pub/test/lish/preview_package_validation_has_no_warnings_test.dart sdk/lib/_internal/pub/test/lish/archives_and_uploads_a_package_test.dart sdk/lib/_internal/pub/test/lish/upload_form_url_is_not_a_string_test.dart sdk/lib/_internal/pub/test/lish/force_publishes_if_there_are_warnings_test.dart sdk/lib/_internal/pub/test/lish/upload_form_fields_has_a_non_string_value_test.dart sdk/lib/_internal/pub/test/lish/upload_form_provides_invalid_json_test.dart sdk/lib/_internal/pub/test/update/pub_update_test.dart sdk/lib/_internal/pub/test/update/git/do_not_update_if_unneeded_test.dart sdk/lib/_internal/pub/test/update/git/update_to_incompatible_pubspec_test.dart sdk/lib/_internal/pub/test/update/git/update_to_nonexistent_pubspec_test.dart sdk/lib/_internal/pub/test/update/git/update_locked_test.dart sdk/lib/_internal/pub/test/update/git/update_one_locked_test.dart sdk/lib/_internal/pub/test/update/hosted/fail_gracefully_on_missing_package_test.dart sdk/lib/_internal/pub/test/update/hosted/unlock_dependers_test.dart sdk/lib/_internal/pub/test/update/hosted/unlock_if_necessary_test.dart sdk/lib/_internal/pub/test/update/hosted/fail_gracefully_on_url_resolve_test.dart sdk/lib/_internal/pub/test/update/hosted/remove_removed_transitive_dependency_test.dart sdk/lib/_internal/pub/test/update/hosted/update_removed_constraints_test.dart sdk/lib/_internal/pub/test/update/hosted/remove_removed_dependency_test.dart sdk/lib/_internal/pub/test/validator/license_test.dart sdk/lib/_internal/pub/test/validator/utils.dart sdk/lib/_internal/pub/test/validator/pubspec_field_test.dart sdk/lib/_internal/pub/test/validator/dependency_test.dart sdk/lib/_internal/pub/test/validator/directory_test.dart sdk/lib/_internal/pub/test/validator/name_test.dart sdk/lib/_internal/pub/test/validator/lib_test.dart sdk/lib/_internal/pub/test/validator/size_test.dart sdk/lib/_internal/pub/test/validator/utf8_readme_test.dart sdk/lib/_internal/pub/test/validator/compiled_dartdoc_test.dart sdk/lib/_internal/pub/test/oauth2/utils.dart sdk/lib/_internal/pub/test/oauth2/with_server_rejected_credentials_authenticates_again_test.dart sdk/lib/_internal/pub/test/oauth2/with_a_server_rejected_refresh_token_authenticates_again_test.dart sdk/lib/_internal/pub/test/oauth2/with_no_credentials_authenticates_and_saves_credentials_test.dart sdk/lib/_internal/pub/test/oauth2/with_an_expired_credentials_refreshes_and_saves_test.dart sdk/lib/_internal/pub/test/oauth2/with_a_pre_existing_credentials_does_not_authenticate_test.dart sdk/lib/_internal/pub/test/oauth2/with_an_expired_credentials_without_a_refresh_token_authenticates_again_test.dart sdk/lib/_internal/pub/test/oauth2/with_a_malformed_credentials_authenticates_again_test.dart sdk/lib/_internal/pub/test/descriptor/tar.dart sdk/lib/_internal/pub/test/descriptor/git.dart sdk/lib/_internal/pub/test/install/pub_install_test.dart sdk/lib/_internal/pub/test/install/relative_symlink_test.dart sdk/lib/_internal/pub/test/install/broken_symlink_test.dart sdk/lib/_internal/pub/test/install/switch_source_test.dart sdk/lib/_internal/pub/test/install/git/check_out_transitive_test.dart sdk/lib/_internal/pub/test/install/git/unlock_if_incompatible_test.dart sdk/lib/_internal/pub/test/install/git/require_pubspec_test.dart sdk/lib/_internal/pub/test/install/git/check_out_with_trailing_slash_test.dart sdk/lib/_internal/pub/test/install/git/dependency_name_match_pubspec_test.dart sdk/lib/_internal/pub/test/install/git/check_out_branch_test.dart sdk/lib/_internal/pub/test/install/git/stay_locked_if_compatible_test.dart sdk/lib/_internal/pub/test/install/git/check_out_and_update_test.dart sdk/lib/_internal/pub/test/install/git/check_out_twice_test.dart sdk/lib/_internal/pub/test/install/git/check_out_test.dart sdk/lib/_internal/pub/test/install/git/lock_version_test.dart sdk/lib/_internal/pub/test/install/git/require_pubspec_name_test.dart sdk/lib/_internal/pub/test/install/git/check_out_revision_test.dart sdk/lib/_internal/pub/test/install/git/different_repo_name_test.dart sdk/lib/_internal/pub/test/install/hosted/unlock_if_incompatible_test.dart sdk/lib/_internal/pub/test/install/hosted/fail_gracefully_on_missing_package_test.dart sdk/lib/_internal/pub/test/install/hosted/do_not_update_on_removed_constraints_test.dart sdk/lib/_internal/pub/test/install/hosted/stay_locked_test.dart sdk/lib/_internal/pub/test/install/hosted/install_test.dart sdk/lib/_internal/pub/test/install/hosted/stay_locked_if_compatible_test.dart sdk/lib/_internal/pub/test/install/hosted/install_transitive_test.dart sdk/lib/_internal/pub/test/install/hosted/fail_gracefully_on_url_resolve_test.dart sdk/lib/_internal/pub/test/install/hosted/remove_removed_transitive_dependency_test.dart sdk/lib/_internal/pub/test/install/hosted/unlock_if_new_is_unsatisfied_test.dart sdk/lib/_internal/pub/test/install/hosted/stay_locked_if_new_is_satisfied_test.dart sdk/lib/_internal/pub/test/install/hosted/remove_removed_dependency_test.dart sdk/lib/_internal/pub/test/install/hosted/cached_pubspec_test.dart sdk/lib/_internal/pub/test/install/hosted/resolve_constraints_test.dart sdk/lib/_internal/pub/test/install/hosted/repair_cache_test.dart sdk/lib/_internal/pub/test/install/path/nonexistent_dir_test.dart sdk/lib/_internal/pub/test/install/path/absolute_path_test.dart sdk/lib/_internal/pub/test/install/path/relative_symlink_test.dart sdk/lib/_internal/pub/test/install/path/shared_dependency_test.dart sdk/lib/_internal/pub/test/install/path/shared_dependency_symlink_test.dart sdk/lib/_internal/pub/test/install/path/absolute_symlink_test.dart sdk/lib/_internal/pub/test/install/path/no_pubspec_test.dart sdk/lib/_internal/pub/test/install/path/relative_path_test.dart sdk/lib/_internal/pub/test/install/path/path_is_file_test.dart sdk/lib/_internal/libraries.dart sdk/lib/_internal/compiler/compiler.dart sdk/lib/_internal/compiler/implementation/dart_types.dart sdk/lib/_internal/compiler/implementation/string_validator.dart sdk/lib/_internal/compiler/implementation/world.dart sdk/lib/_internal/compiler/implementation/typechecker.dart sdk/lib/_internal/compiler/implementation/filenames.dart sdk/lib/_internal/compiler/implementation/dart2js.dart sdk/lib/_internal/compiler/implementation/patch_parser.dart sdk/lib/_internal/compiler/implementation/constants.dart sdk/lib/_internal/compiler/implementation/script.dart sdk/lib/_internal/compiler/implementation/library_loader.dart sdk/lib/_internal/compiler/implementation/enqueue.dart sdk/lib/_internal/compiler/implementation/compiler.dart sdk/lib/_internal/compiler/implementation/diagnostic_listener.dart sdk/lib/_internal/compiler/implementation/warnings.dart sdk/lib/_internal/compiler/implementation/source_file_provider.dart sdk/lib/_internal/compiler/implementation/tree_validator.dart sdk/lib/_internal/compiler/implementation/apiimpl.dart sdk/lib/_internal/compiler/implementation/native_handler.dart sdk/lib/_internal/compiler/implementation/constant_system_dart.dart sdk/lib/_internal/compiler/implementation/dart2jslib.dart sdk/lib/_internal/compiler/implementation/compile_time_constants.dart sdk/lib/_internal/compiler/implementation/closure.dart sdk/lib/_internal/compiler/implementation/code_buffer.dart sdk/lib/_internal/compiler/implementation/source_file.dart sdk/lib/_internal/compiler/implementation/deferred_load.dart sdk/lib/_internal/compiler/implementation/resolved_visitor.dart sdk/lib/_internal/compiler/implementation/colors.dart sdk/lib/_internal/compiler/implementation/source_map_builder.dart sdk/lib/_internal/compiler/implementation/constant_system.dart sdk/lib/_internal/compiler/implementation/util/characters.dart sdk/lib/_internal/compiler/implementation/util/util.dart sdk/lib/_internal/compiler/implementation/util/uri_extras.dart sdk/lib/_internal/compiler/implementation/util/link_implementation.dart sdk/lib/_internal/compiler/implementation/util/link.dart sdk/lib/_internal/compiler/implementation/util/util_implementation.dart sdk/lib/_internal/compiler/implementation/tools/mini_parser.dart sdk/lib/_internal/compiler/implementation/dart_backend/utils.dart sdk/lib/_internal/compiler/implementation/dart_backend/dart_backend.dart sdk/lib/_internal/compiler/implementation/dart_backend/emitter.dart sdk/lib/_internal/compiler/implementation/dart_backend/backend.dart sdk/lib/_internal/compiler/implementation/dart_backend/placeholder_collector.dart sdk/lib/_internal/compiler/implementation/dart_backend/renamer.dart sdk/lib/_internal/compiler/implementation/js_backend/minify_namer.dart sdk/lib/_internal/compiler/implementation/js_backend/namer.dart sdk/lib/_internal/compiler/implementation/js_backend/emitter.dart sdk/lib/_internal/compiler/implementation/js_backend/runtime_types.dart sdk/lib/_internal/compiler/implementation/js_backend/constant_system_javascript.dart sdk/lib/_internal/compiler/implementation/js_backend/emitter_no_eval.dart sdk/lib/_internal/compiler/implementation/js_backend/js_backend.dart sdk/lib/_internal/compiler/implementation/js_backend/backend.dart sdk/lib/_internal/compiler/implementation/js_backend/native_emitter.dart sdk/lib/_internal/compiler/implementation/js_backend/constant_emitter.dart sdk/lib/_internal/compiler/implementation/lib/string_helper.dart sdk/lib/_internal/compiler/implementation/lib/collection_patch.dart sdk/lib/_internal/compiler/implementation/lib/js_rti.dart sdk/lib/_internal/compiler/implementation/lib/core_patch.dart sdk/lib/_internal/compiler/implementation/lib/js_array.dart sdk/lib/_internal/compiler/implementation/lib/mirrors_patch.dart sdk/lib/_internal/compiler/implementation/lib/isolate_patch.dart sdk/lib/_internal/compiler/implementation/lib/async_patch.dart sdk/lib/_internal/compiler/implementation/lib/collection_dev_patch.dart sdk/lib/_internal/compiler/implementation/lib/js_helper.dart sdk/lib/_internal/compiler/implementation/lib/scalarlist_patch.dart sdk/lib/_internal/compiler/implementation/lib/native_helper.dart sdk/lib/_internal/compiler/implementation/lib/io_patch.dart sdk/lib/_internal/compiler/implementation/lib/js_number.dart sdk/lib/_internal/compiler/implementation/lib/regexp_helper.dart sdk/lib/_internal/compiler/implementation/lib/isolate_helper.dart sdk/lib/_internal/compiler/implementation/lib/constant_map.dart sdk/lib/_internal/compiler/implementation/lib/typed_data_patch.dart sdk/lib/_internal/compiler/implementation/lib/math_patch.dart sdk/lib/_internal/compiler/implementation/lib/js_string.dart sdk/lib/_internal/compiler/implementation/lib/json_patch.dart sdk/lib/_internal/compiler/implementation/lib/foreign_helper.dart sdk/lib/_internal/compiler/implementation/lib/interceptors.dart sdk/lib/_internal/compiler/implementation/mirrors/mirrors.dart sdk/lib/_internal/compiler/implementation/mirrors/util.dart sdk/lib/_internal/compiler/implementation/mirrors/dart2js_mirror.dart sdk/lib/_internal/compiler/implementation/mirrors/mirrors_util.dart sdk/lib/_internal/compiler/implementation/resolution/scope.dart sdk/lib/_internal/compiler/implementation/resolution/resolution.dart sdk/lib/_internal/compiler/implementation/resolution/secret_tree_element.dart sdk/lib/_internal/compiler/implementation/resolution/members.dart sdk/lib/_internal/compiler/implementation/ssa/ssa.dart sdk/lib/_internal/compiler/implementation/ssa/bailout.dart sdk/lib/_internal/compiler/implementation/ssa/codegen.dart sdk/lib/_internal/compiler/implementation/ssa/types.dart sdk/lib/_internal/compiler/implementation/ssa/validate.dart sdk/lib/_internal/compiler/implementation/ssa/invoke_dynamic_specializers.dart sdk/lib/_internal/compiler/implementation/ssa/optimize.dart sdk/lib/_internal/compiler/implementation/ssa/types_propagation.dart sdk/lib/_internal/compiler/implementation/ssa/codegen_helpers.dart sdk/lib/_internal/compiler/implementation/ssa/nodes.dart sdk/lib/_internal/compiler/implementation/ssa/value_set.dart sdk/lib/_internal/compiler/implementation/ssa/builder.dart sdk/lib/_internal/compiler/implementation/ssa/tracer.dart sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart sdk/lib/_internal/compiler/implementation/js/precedence.dart sdk/lib/_internal/compiler/implementation/js/nodes.dart sdk/lib/_internal/compiler/implementation/js/builder.dart sdk/lib/_internal/compiler/implementation/js/printer.dart sdk/lib/_internal/compiler/implementation/js/js.dart sdk/lib/_internal/compiler/implementation/types/types.dart sdk/lib/_internal/compiler/implementation/types/type_mask.dart sdk/lib/_internal/compiler/implementation/types/concrete_types_inferrer.dart sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart sdk/lib/_internal/compiler/implementation/elements/elements.dart sdk/lib/_internal/compiler/implementation/elements/modelx.dart sdk/lib/_internal/compiler/implementation/universe/selector_map.dart sdk/lib/_internal/compiler/implementation/universe/universe.dart sdk/lib/_internal/compiler/implementation/universe/function_set.dart sdk/lib/_internal/compiler/implementation/universe/full_function_set.dart sdk/lib/_internal/compiler/implementation/scanner/byte_array_scanner.dart sdk/lib/_internal/compiler/implementation/scanner/byte_strings.dart sdk/lib/_internal/compiler/implementation/scanner/scannerlib.dart sdk/lib/_internal/compiler/implementation/scanner/scanner_implementation.dart sdk/lib/_internal/compiler/implementation/scanner/listener.dart sdk/lib/_internal/compiler/implementation/scanner/class_element_parser.dart sdk/lib/_internal/compiler/implementation/scanner/parser_task.dart sdk/lib/_internal/compiler/implementation/scanner/scanner.dart sdk/lib/_internal/compiler/implementation/scanner/keyword.dart sdk/lib/_internal/compiler/implementation/scanner/scanner_task.dart sdk/lib/_internal/compiler/implementation/scanner/partial_parser.dart sdk/lib/_internal/compiler/implementation/scanner/token.dart sdk/lib/_internal/compiler/implementation/scanner/parser.dart sdk/lib/_internal/compiler/implementation/scanner/array_based_scanner.dart sdk/lib/_internal/compiler/implementation/scanner/string_scanner.dart sdk/lib/_internal/compiler/implementation/tree/visitors.dart sdk/lib/_internal/compiler/implementation/tree/prettyprint.dart sdk/lib/_internal/compiler/implementation/tree/unparser.dart sdk/lib/_internal/compiler/implementation/tree/tree.dart sdk/lib/_internal/compiler/implementation/tree/nodes.dart sdk/lib/_internal/compiler/implementation/tree/dartstring.dart sdk/lib/_internal/compiler/samples/leap/leap_leg.dart sdk/lib/_internal/compiler/samples/leap/request_cache.dart sdk/lib/_internal/compiler/samples/leap/leap_script.dart sdk/lib/_internal/compiler/samples/leap/leap_server.dart sdk/lib/_internal/compiler/samples/leap/leap.dart pkg/intl/lib/number_symbols.dart pkg/intl/lib/intl.dart pkg/intl/lib/number_format.dart pkg/intl/lib/date_format.dart pkg/intl/lib/number_symbols_data.dart pkg/intl/lib/date_symbol_data_http_request.dart pkg/intl/lib/intl_browser.dart pkg/intl/lib/bidi_utils.dart pkg/intl/lib/date_symbol_data_local.dart pkg/intl/lib/date_time_patterns.dart pkg/intl/lib/message_lookup_by_library.dart pkg/intl/lib/date_symbol_data_file.dart pkg/intl/lib/extract_messages.dart pkg/intl/lib/generate_localized.dart pkg/intl/lib/bidi_formatter.dart pkg/intl/lib/date_symbols.dart pkg/intl/lib/intl_standalone.dart pkg/intl/lib/src/date_format_helpers.dart pkg/intl/lib/src/http_request_data_reader.dart pkg/intl/lib/src/file_data_reader.dart pkg/intl/lib/src/date_format_internal.dart pkg/intl/lib/src/intl_message.dart pkg/intl/lib/src/intl_helpers.dart pkg/intl/lib/src/date_format_field.dart pkg/intl/lib/src/lazy_locale_data.dart pkg/intl/lib/src/data/dates/localeList.dart pkg/intl/test/date_time_format_local_odd_test.dart pkg/intl/test/data_directory.dart pkg/intl/test/date_time_format_local_even_test.dart pkg/intl/test/intl_message_basic_example_test.dart pkg/intl/test/number_test_data.dart pkg/intl/test/bidi_utils_test.dart pkg/intl/test/date_time_format_test_data.dart pkg/intl/test/number_closure_test.dart pkg/intl/test/date_time_format_file_even_test.dart pkg/intl/test/number_format_test.dart pkg/intl/test/intl_test.dart pkg/intl/test/find_default_locale_standalone_test.dart pkg/intl/test/date_time_format_test_core.dart pkg/intl/test/date_time_format_http_request_test.dart pkg/intl/test/date_time_format_uninitialized_test.dart pkg/intl/test/date_time_format_test_stub.dart pkg/intl/test/find_default_locale_browser_test.dart pkg/intl/test/bidi_format_test.dart pkg/intl/test/date_time_format_file_odd_test.dart pkg/intl/test/message_extraction/generate_from_json.dart pkg/intl/test/message_extraction/sample_with_messages.dart pkg/intl/test/message_extraction/make_hardcoded_translation.dart pkg/intl/test/message_extraction/part_of_sample_with_messages.dart pkg/intl/test/message_extraction/extract_to_json.dart pkg/intl/test/message_extraction/message_extraction_test.dart pkg/intl/tool/generate_locale_data_files.dart pkg/intl/example/basic/basic_example_runner.dart pkg/intl/example/basic/basic_example.dart pkg/intl/example/basic/messages_de.dart pkg/intl/example/basic/messages_all.dart pkg/intl/example/basic/messages_th_th.dart pkg/serialization/lib/serialization.dart pkg/serialization/lib/src/format.dart pkg/serialization/lib/src/serialization_rule.dart pkg/serialization/lib/src/serialization_helpers.dart pkg/serialization/lib/src/mirrors_helpers.dart pkg/serialization/lib/src/basic_rule.dart pkg/serialization/lib/src/reader_writer.dart pkg/serialization/test/serialization_test.dart pkg/serialization/test/test_models.dart pkg/serialization/test/polyfill_identity_map_test.dart pkg/serialization/test/no_library_test.dart pkg/analyzer_experimental/bin/analyzer.dart pkg/analyzer_experimental/lib/options.dart pkg/analyzer_experimental/lib/analyzer.dart pkg/analyzer_experimental/lib/src/generated/constant.dart pkg/analyzer_experimental/lib/src/generated/utilities_dart.dart pkg/analyzer_experimental/lib/src/generated/instrumentation.dart pkg/analyzer_experimental/lib/src/generated/source_io.dart pkg/analyzer_experimental/lib/src/generated/ast.dart pkg/analyzer_experimental/lib/src/generated/sdk.dart pkg/analyzer_experimental/lib/src/generated/element.dart pkg/analyzer_experimental/lib/src/generated/engine.dart pkg/analyzer_experimental/lib/src/generated/scanner.dart pkg/analyzer_experimental/lib/src/generated/java_core.dart pkg/analyzer_experimental/lib/src/generated/java_engine.dart pkg/analyzer_experimental/lib/src/generated/java_io.dart pkg/analyzer_experimental/lib/src/generated/parser.dart pkg/analyzer_experimental/lib/src/generated/java_junit.dart pkg/analyzer_experimental/lib/src/generated/sdk_io.dart pkg/analyzer_experimental/lib/src/generated/html.dart pkg/analyzer_experimental/lib/src/generated/java_engine_io.dart pkg/analyzer_experimental/lib/src/generated/error.dart pkg/analyzer_experimental/lib/src/generated/source.dart pkg/analyzer_experimental/lib/src/generated/resolver.dart pkg/analyzer_experimental/test/options_test.dart pkg/analyzer_experimental/test/generated/resolver_test.dart pkg/analyzer_experimental/test/generated/scanner_test.dart pkg/analyzer_experimental/test/generated/element_test.dart pkg/analyzer_experimental/test/generated/ast_test.dart pkg/analyzer_experimental/test/generated/test_support.dart pkg/analyzer_experimental/test/generated/parser_test.dart pkg/analyzer_experimental/example/scanner_driver.dart pkg/analyzer_experimental/example/resolver_driver.dart pkg/analyzer_experimental/example/parser_driver.dart pkg/webdriver/lib/webdriver.dart pkg/webdriver/lib/src/base64decoder.dart pkg/webdriver/test/webdriver_test.dart pkg/fixnum/lib/fixnum.dart pkg/fixnum/lib/src/int64.dart pkg/fixnum/lib/src/intx.dart pkg/fixnum/lib/src/int32.dart pkg/fixnum/test/int_32_test.dart pkg/fixnum/test/int_64_vm_test.dart pkg/fixnum/test/int_64_test.dart pkg/pathos/lib/path.dart pkg/pathos/test/pathos_test.dart pkg/pathos/test/pathos_windows_test.dart pkg/pathos/test/pathos_posix_test.dart pkg/meta/lib/meta.dart pkg/oauth2/lib/oauth2.dart pkg/oauth2/lib/src/utils.dart pkg/oauth2/lib/src/expiration_exception.dart pkg/oauth2/lib/src/credentials.dart pkg/oauth2/lib/src/authorization_exception.dart pkg/oauth2/lib/src/authorization_code_grant.dart pkg/oauth2/lib/src/handle_access_token_response.dart pkg/oauth2/lib/src/client.dart pkg/oauth2/test/utils.dart pkg/oauth2/test/handle_access_token_response_test.dart pkg/oauth2/test/authorization_code_grant_test.dart pkg/oauth2/test/client_test.dart pkg/oauth2/test/utils_test.dart pkg/oauth2/test/credentials_test.dart pkg/http/lib/http.dart pkg/http/lib/testing.dart pkg/http/lib/src/io_client.dart pkg/http/lib/src/utils.dart pkg/http/lib/src/base_request.dart pkg/http/lib/src/streamed_response.dart pkg/http/lib/src/byte_stream.dart pkg/http/lib/src/base_client.dart pkg/http/lib/src/streamed_request.dart pkg/http/lib/src/base_response.dart pkg/http/lib/src/mock_client.dart pkg/http/lib/src/response.dart pkg/http/lib/src/request.dart pkg/http/lib/src/client.dart pkg/http/lib/src/multipart_file.dart pkg/http/lib/src/multipart_request.dart pkg/http/test/mock_client_test.dart pkg/http/test/utils.dart pkg/http/test/streamed_request_test.dart pkg/http/test/multipart_test.dart pkg/http/test/client_test.dart pkg/http/test/http_test.dart pkg/http/test/request_test.dart pkg/http/test/response_test.dart pkg/http/test/safe_http_server.dart pkg/expect/lib/expect.dart pkg/logging/lib/logging.dart pkg/logging/test/logging_test.dart pkg/stack_trace/lib/stack_trace.dart pkg/stack_trace/lib/src/utils.dart pkg/stack_trace/lib/src/trace.dart pkg/stack_trace/lib/src/frame.dart pkg/stack_trace/test/frame_test.dart pkg/stack_trace/test/trace_test.dart pkg/yaml/lib/yaml.dart pkg/yaml/lib/src/composer.dart pkg/yaml/lib/src/utils.dart pkg/yaml/lib/src/yaml_exception.dart pkg/yaml/lib/src/deep_equals.dart pkg/yaml/lib/src/visitor.dart pkg/yaml/lib/src/yaml_map.dart pkg/yaml/lib/src/parser.dart pkg/yaml/lib/src/model.dart pkg/yaml/lib/src/constructor.dart pkg/yaml/test/yaml_test.dart pkg/scheduled_test/lib/scheduled_test.dart pkg/scheduled_test/lib/scheduled_process.dart pkg/scheduled_test/lib/scheduled_server.dart pkg/scheduled_test/lib/descriptor.dart pkg/scheduled_test/lib/src/utils.dart pkg/scheduled_test/lib/src/schedule_error.dart pkg/scheduled_test/lib/src/task.dart pkg/scheduled_test/lib/src/substitute_future.dart pkg/scheduled_test/lib/src/scheduled_future_matchers.dart pkg/scheduled_test/lib/src/value_future.dart pkg/scheduled_test/lib/src/mock_clock.dart pkg/scheduled_test/lib/src/future_group.dart pkg/scheduled_test/lib/src/schedule.dart pkg/scheduled_test/lib/src/scheduled_server/handler.dart pkg/scheduled_test/lib/src/scheduled_server/safe_http_server.dart pkg/scheduled_test/lib/src/descriptor/directory_descriptor.dart pkg/scheduled_test/lib/src/descriptor/async_descriptor.dart pkg/scheduled_test/lib/src/descriptor/nothing_descriptor.dart pkg/scheduled_test/lib/src/descriptor/descriptor.dart pkg/scheduled_test/lib/src/descriptor/file_descriptor.dart pkg/scheduled_test/lib/src/descriptor/pattern_descriptor.dart pkg/scheduled_test/test/utils.dart pkg/scheduled_test/test/substitute_future_test.dart pkg/scheduled_test/test/scheduled_server_test.dart pkg/scheduled_test/test/scheduled_future_matchers_test.dart pkg/scheduled_test/test/metatest.dart pkg/scheduled_test/test/value_future_test.dart pkg/scheduled_test/test/scheduled_process_test.dart pkg/scheduled_test/test/descriptor/utils.dart pkg/scheduled_test/test/descriptor/file_test.dart pkg/scheduled_test/test/descriptor/nothing_test.dart pkg/scheduled_test/test/descriptor/pattern_test.dart pkg/scheduled_test/test/descriptor/directory_test.dart pkg/scheduled_test/test/descriptor/async_test.dart pkg/scheduled_test/test/scheduled_test/current_schedule_state_test.dart pkg/scheduled_test/test/scheduled_test/current_schedule_current_task_test.dart pkg/scheduled_test/test/scheduled_test/nested_task_test.dart pkg/scheduled_test/test/scheduled_test/on_exception_test.dart pkg/scheduled_test/test/scheduled_test/task_return_value_test.dart pkg/scheduled_test/test/scheduled_test/abort_test.dart pkg/scheduled_test/test/scheduled_test/timeout_test.dart pkg/scheduled_test/test/scheduled_test/out_of_band_task_test.dart pkg/scheduled_test/test/scheduled_test/wrap_async_test.dart pkg/scheduled_test/test/scheduled_test/capture_stack_traces_test.dart pkg/scheduled_test/test/scheduled_test/wrap_future_test.dart pkg/scheduled_test/test/scheduled_test/signal_error_test.dart pkg/scheduled_test/test/scheduled_test/set_up_test.dart pkg/scheduled_test/test/scheduled_test/on_complete_test.dart pkg/scheduled_test/test/scheduled_test/simple_test.dart pkg/scheduled_test/test/scheduled_test/current_schedule_errors_test.dart pkg/unittest/lib/unittest.dart pkg/unittest/lib/html_individual_config.dart pkg/unittest/lib/vm_config.dart pkg/unittest/lib/html_enhanced_config.dart pkg/unittest/lib/matcher.dart pkg/unittest/lib/interactive_html_config.dart pkg/unittest/lib/mock.dart pkg/unittest/lib/html_config.dart pkg/unittest/lib/compact_vm_config.dart pkg/unittest/lib/src/expect.dart pkg/unittest/lib/src/basematcher.dart pkg/unittest/lib/src/string_matchers.dart pkg/unittest/lib/src/core_matchers.dart pkg/unittest/lib/src/interfaces.dart pkg/unittest/lib/src/description.dart pkg/unittest/lib/src/future_matchers.dart pkg/unittest/lib/src/numeric_matchers.dart pkg/unittest/lib/src/iterable_matchers.dart pkg/unittest/lib/src/map_matchers.dart pkg/unittest/lib/src/config.dart pkg/unittest/lib/src/test_case.dart pkg/unittest/lib/src/operator_matchers.dart pkg/unittest/test/mock_regexp_negative_test.dart pkg/unittest/test/matchers_test.dart pkg/unittest/test/unittest_test.dart pkg/unittest/test/test_utils.dart pkg/unittest/test/instance_test.dart pkg/unittest/test/mock_test.dart pkg/unittest/test/mock_stepwise_negative_test.dart pkg/args/lib/args.dart pkg/args/lib/src/parser.dart pkg/args/lib/src/usage.dart pkg/args/test/args_test.dart pkg/args/test/usage_test.dart pkg/args/test/command_test.dart pkg/args/test/parse_test.dart pkg/args/example/test_runner.dart pkg/source_maps/lib/span.dart pkg/source_maps/lib/source_maps.dart pkg/source_maps/lib/parser.dart pkg/source_maps/lib/builder.dart pkg/source_maps/lib/printer.dart pkg/source_maps/lib/src/utils.dart pkg/source_maps/lib/src/vlq.dart pkg/source_maps/test/vlq_test.dart pkg/source_maps/test/run.dart pkg/source_maps/test/builder_test.dart pkg/source_maps/test/utils_test.dart pkg/source_maps/test/common.dart pkg/source_maps/test/parser_test.dart pkg/source_maps/test/printer_test.dart pkg/source_maps/test/span_test.dart pkg/source_maps/test/end2end_test.dart FORCE_DO_CMD
+	$(call do_cmd,dart_utils_pub_pub_gyp_pub_target_generate_pub_snapshot)
+
+all_deps += $(obj)/gen/pub.dart.snapshot
+action_dart_utils_pub_pub_gyp_pub_target_generate_pub_snapshot_outputs := $(obj)/gen/pub.dart.snapshot
+
+
+### Rules for final target.
+# Build our special outputs first.
+$(obj).target/utils/pub/pub.stamp: | $(action_dart_utils_pub_pub_gyp_pub_target_generate_pub_snapshot_outputs)
+
+# Preserve order dependency of special output on deps.
+$(action_dart_utils_pub_pub_gyp_pub_target_generate_pub_snapshot_outputs): | $(builddir)/dart $(obj).target/pkg/pkg_packages.stamp
+
+$(obj).target/utils/pub/pub.stamp: TOOLSET := $(TOOLSET)
+$(obj).target/utils/pub/pub.stamp: $(builddir)/dart $(obj).target/pkg/pkg_packages.stamp FORCE_DO_CMD
+	$(call do_cmd,touch)
+
+all_deps += $(obj).target/utils/pub/pub.stamp
+# Add target alias
+.PHONY: pub
+pub: $(obj).target/utils/pub/pub.stamp
+
+# Add target alias to "all" target.
+.PHONY: all
+all: pub
+
diff --git a/utils/pub/solver/greedy_solver.dart b/utils/pub/solver/greedy_solver.dart
new file mode 100644
index 0000000..e664ea2
--- /dev/null
+++ b/utils/pub/solver/greedy_solver.dart
@@ -0,0 +1,556 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/// Attempts to resolve a set of version constraints for a package dependency
+/// graph and select an appropriate set of best specific versions for all
+/// dependent packages. It works iteratively and tries to reach a stable
+/// solution where the constraints of all dependencies are met. If it fails to
+/// reach a solution after a certain number of iterations, it assumes the
+/// dependency graph is unstable and reports and error.
+///
+/// There are two fundamental operations in the process of iterating over the
+/// graph:
+///
+/// 1.  Changing the selected concrete version of some package. (This includes
+///     adding and removing a package too, which is considering changing the
+///     version to or from "none".) In other words, a node has changed.
+/// 2.  Changing the version constraint that one package places on another. In
+///     other words, and edge has changed.
+///
+/// Both of these events have a corresponding (potentional) async operation and
+/// roughly cycle back and forth between each other. When we change the version
+/// of package changes, we asynchronously load the pubspec for the new version.
+/// When that's done, we compare the dependencies of the new version versus the
+/// old one. For everything that differs, we change those constraints between
+/// this package and that dependency.
+///
+/// When a constraint on a package changes, we re-calculate the overall
+/// constraint on that package. I.e. with a shared dependency, we intersect all
+/// of the constraints that its depending packages place on it. If that overall
+/// constraint changes (say from "<3.0.0" to "<2.5.0"), then the currently
+/// picked version for that package may fall outside of the new constraint. If
+/// that happens, we find the new best version that meets the updated constraint
+/// and then the change the package to use that version. That cycles back up to
+/// the beginning again.
+library version_solver1;
+
+import 'dart:async';
+import 'dart:collection' show Queue;
+import 'dart:math' as math;
+
+import '../lock_file.dart';
+import '../log.dart' as log;
+import '../package.dart';
+import '../source.dart';
+import '../source_registry.dart';
+import '../version.dart';
+import 'version_solver.dart';
+
+class GreedyVersionSolver extends VersionSolver {
+  final _packages = <String, DependencyNode>{};
+  final _work = new Queue<WorkItem>();
+  int _numIterations = 0;
+
+  GreedyVersionSolver(SourceRegistry sources, Package root, LockFile lockFile,
+                      List<String> useLatest)
+      : super(sources, root, lockFile, useLatest);
+
+  /// The non-backtracking solver always only tries one solution.
+  int get attemptedSolutions => 1;
+
+  void forceLatestVersion(String package) {
+    // TODO(nweiz): How do we want to detect and handle unknown dependencies
+    // here?
+    getDependency(package).useLatestVersion = true;
+  }
+
+  Future<List<PackageId>> runSolver() {
+    // Kick off the work by adding the root package at its concrete version to
+    // the dependency graph.
+    enqueue(new AddConstraint('(entrypoint)', new PackageRef.root(root)));
+
+    Future processNextWorkItem(_) {
+      while (true) {
+        // Stop if we are done.
+        if (_work.isEmpty) return new Future.value(buildResults());
+
+        // If we appear to be stuck in a loop, then we probably have an unstable
+        // graph, bail. We guess this based on a rough heuristic that it should
+        // only take a certain number of steps to solve a graph with a given
+        // number of connections.
+        // TODO(rnystrom): These numbers here are magic and arbitrary. Tune
+        // when we have a better picture of real-world package topologies.
+        _numIterations++;
+        if (_numIterations > math.max(50, _packages.length * 5)) {
+          throw new CouldNotSolveException();
+        }
+
+        // Run the first work item.
+        var future = _work.removeFirst().process(this);
+
+        // If we have an async operation to perform, chain the loop to resume
+        // when it's done. Otherwise, just loop synchronously.
+        if (future != null) {
+          return future.then(processNextWorkItem);
+        }
+      }
+    }
+
+    return processNextWorkItem(null);
+  }
+
+  void enqueue(WorkItem work) {
+    _work.add(work);
+  }
+
+  DependencyNode getDependency(String package) {
+    // There can be unused dependencies in the graph, so just create an empty
+    // one if needed.
+    _packages.putIfAbsent(package, () => new DependencyNode(package));
+    return _packages[package];
+  }
+
+  /// Sets the best selected version of [package] to [version].
+  void setVersion(String package, Version version) {
+    _packages[package].version = version;
+  }
+
+  /// Returns the most recent version of [dependency] that satisfies all of its
+  /// version constraints.
+  Future<Version> getBestVersion(DependencyNode dependency) {
+    return cache.getVersions(dependency.name,
+        dependency.source, dependency.description).then((versions) {
+      var best = null;
+      for (var ref in versions) {
+        if (dependency.useLatestVersion ||
+            dependency.constraint.allows(ref.version)) {
+          if (best == null || ref.version > best) best = ref.version;
+        }
+      }
+
+      // TODO(rnystrom): Better exception.
+      if (best == null) {
+        if (tryUnlockDepender(dependency)) return null;
+        throw new NoVersionException(dependency.name, dependency.constraint,
+            dependency.toList());
+      } else if (!dependency.constraint.allows(best)) {
+        if (tryUnlockDepender(dependency)) return null;
+        throw new CouldNotUpdateException(
+            dependency.name, dependency.constraint, best);
+      }
+
+      return best;
+    });
+  }
+
+  /// Looks for a package that depends (transitively) on [dependency] and has
+  /// its version locked in the lockfile. If one is found, enqueues an
+  /// [UnlockPackage] work item for it and returns true. Otherwise, returns
+  /// false.
+  ///
+  /// This does a breadth-first search; immediate dependers will be unlocked
+  /// first, followed by transitive dependers.
+  bool tryUnlockDepender(DependencyNode dependency, [Set<String> seen]) {
+    if (seen == null) seen = new Set();
+    // Avoid an infinite loop if there are circular dependencies.
+    if (seen.contains(dependency.name)) return false;
+    seen.add(dependency.name);
+
+    for (var dependerName in dependency.dependers) {
+      var depender = getDependency(dependerName);
+      var locked = lockFile.packages[dependerName];
+      if (locked != null && depender.version == locked.version &&
+          depender.source.name == locked.source.name) {
+        enqueue(new UnlockPackage(depender));
+        return true;
+      }
+    }
+
+    return dependency.dependers.map(getDependency).any((subdependency) =>
+        tryUnlockDepender(subdependency, seen));
+  }
+
+  List<PackageId> buildResults() {
+    return _packages.values
+        .where((dep) => dep.isDependedOn)
+        .map(_dependencyToPackageId)
+        .toList();
+  }
+
+  PackageId _dependencyToPackageId(DependencyNode dep) {
+    var description = dep.description;
+
+    // If the lockfile contains a fully-resolved description for the package,
+    // use that. This allows e.g. Git to ensure that the same commit is used.
+    var lockedPackage = lockFile.packages[dep.name];
+    if (lockedPackage != null && lockedPackage.version == dep.version &&
+        lockedPackage.source.name == dep.source.name &&
+        dep.source.descriptionsEqual(
+            description, lockedPackage.description)) {
+      description = lockedPackage.description;
+    }
+
+    return new PackageId(dep.name, dep.source, dep.version, description);
+  }
+}
+
+/// The constraint solver works by iteratively processing a queue of work items.
+/// Each item is a single atomic change to the dependency graph. Handling them
+/// in a queue lets us handle asynchrony (resolving versions requires
+/// information from servers) as well as avoid deeply nested recursion.
+abstract class WorkItem {
+  /// Processes this work item. Returns a future that completes when the work is
+  /// done. If `null` is returned, that means the work has completed
+  /// synchronously and the next item can be started immediately.
+  Future process(GreedyVersionSolver solver);
+}
+
+/// The best selected version for a package has changed to [version]. If the
+/// previous version of the package is `null`, that means the package is being
+/// added to the graph. If [version] is `null`, it is being removed.
+class ChangeVersion implements WorkItem {
+  /// The name of the package whose version is being changed.
+  final String package;
+
+  /// The source of the package whose version is changing.
+  final Source source;
+
+  /// The description identifying the package whose version is changing.
+  final description;
+
+  /// The new selected version.
+  final Version version;
+
+  ChangeVersion(this.package, this.source, this.description, this.version);
+
+  Future process(GreedyVersionSolver solver) {
+    log.fine("Changing $package to version $version.");
+
+    var dependency = solver.getDependency(package);
+    var oldVersion = dependency.version;
+    solver.setVersion(package, version);
+
+    // The dependencies between the old and new version may be different. Walk
+    // them both and update any constraints that differ between the two.
+    return Future.wait([
+        getDependencyRefs(solver, oldVersion),
+        getDependencyRefs(solver, version)]).then((list) {
+      var oldDependencyRefs = list[0];
+      var newDependencyRefs = list[1];
+
+      for (var oldRef in oldDependencyRefs.values) {
+        if (newDependencyRefs.containsKey(oldRef.name)) {
+          // The dependency is in both versions of this package, but its
+          // constraint may have changed.
+          var newRef = newDependencyRefs.remove(oldRef.name);
+          solver.enqueue(new AddConstraint(package, newRef));
+        } else {
+          // The dependency is not in the new version of the package, so just
+          // remove its constraint.
+          solver.enqueue(new RemoveConstraint(package, oldRef.name));
+        }
+      }
+
+      // Everything that's left is a depdendency that's only in the new
+      // version of the package.
+      for (var newRef in newDependencyRefs.values) {
+        solver.enqueue(new AddConstraint(package, newRef));
+      }
+    });
+  }
+
+  /// Get the dependencies at [version] of the package being changed.
+  Future<Map<String, PackageRef>> getDependencyRefs(VersionSolver solver,
+      Version version) {
+    // If there is no version, it means no package, so no dependencies.
+    if (version == null) {
+      return new Future<Map<String, PackageRef>>.value(<String, PackageRef>{});
+    }
+
+    var id = new PackageId(package, source, version, description);
+    return solver.cache.getPubspec(id).then((pubspec) {
+      var dependencies = <String, PackageRef>{};
+      for (var dependency in pubspec.dependencies) {
+        dependencies[dependency.name] = dependency;
+      }
+
+      // Include dev dependencies only from the root package.
+      if (id.isRoot) {
+        for (var dependency in pubspec.devDependencies) {
+          dependencies[dependency.name] = dependency;
+        }
+      }
+
+      return dependencies;
+    });
+  }
+}
+
+/// A constraint that a depending package places on a dependent package has
+/// changed.
+///
+/// This is an abstract class that contains logic for updating the dependency
+/// graph once a dependency has changed. Changing the dependency is the
+/// responsibility of subclasses.
+abstract class ChangeConstraint implements WorkItem {
+  Future process(GreedyVersionSolver solver);
+
+  void undo(GreedyVersionSolver solver);
+
+  Future _processChange(GreedyVersionSolver solver,
+                        DependencyNode oldDependency,
+                        DependencyNode newDependency) {
+    var name = newDependency.name;
+    var source = oldDependency.source != null ?
+      oldDependency.source : newDependency.source;
+    var description = oldDependency.description != null ?
+      oldDependency.description : newDependency.description;
+    var oldConstraint = oldDependency.constraint;
+    var newConstraint = newDependency.constraint;
+
+    // If the package is over-constrained, i.e. the packages depending have
+    // disjoint constraints, then try unlocking a depender that's locked by the
+    // lockfile. If there are no remaining locked dependencies, throw an error.
+    if (newConstraint != null && newConstraint.isEmpty) {
+      if (solver.tryUnlockDepender(newDependency)) {
+        undo(solver);
+        return null;
+      }
+
+      throw new DisjointConstraintException(name, newDependency.toList());
+    }
+
+    // If this constraint change didn't cause the overall constraint on the
+    // package to change, then we don't need to do any further work.
+    if (oldConstraint == newConstraint) return null;
+
+    // If the dependency has been cut free from the graph, just remove it.
+    if (!newDependency.isDependedOn) {
+      solver.enqueue(new ChangeVersion(name, source, description, null));
+      return null;
+    }
+
+    // If the dependency is on the root package, then we don't need to do
+    // anything since it's already at the best version.
+    if (name == solver.root.name) {
+      solver.enqueue(new ChangeVersion(
+          name, source, description, solver.root.version));
+      return null;
+    }
+
+    // If the dependency is on a package in the lockfile, use the lockfile's
+    // version for that package if it's valid given the other constraints.
+    var lockedPackage = solver.lockFile.packages[name];
+    if (lockedPackage != null && newDependency.source == lockedPackage.source) {
+      var lockedVersion = lockedPackage.version;
+      if (newConstraint.allows(lockedVersion)) {
+        solver.enqueue(
+            new ChangeVersion(name, source, description, lockedVersion));
+        return null;
+      }
+    }
+
+    // The constraint has changed, so see what the best version of the package
+    // that meets the new constraint is.
+    return solver.getBestVersion(newDependency).then((best) {
+      if (best == null) {
+        undo(solver);
+      } else if (newDependency.version != best) {
+        solver.enqueue(new ChangeVersion(name, source, description, best));
+      }
+    });
+  }
+}
+
+/// The constraint given by [ref] is being placed by [depender].
+class AddConstraint extends ChangeConstraint {
+  /// The package that has the dependency.
+  final String depender;
+
+  /// The package being depended on and the constraints being placed on it. The
+  /// source, version, and description in this ref are all considered
+  /// constraints on the dependent package.
+  final PackageRef ref;
+
+  AddConstraint(this.depender, this.ref);
+
+  Future process(GreedyVersionSolver solver) {
+    log.fine("Adding $depender's constraint $ref.");
+
+    var dependency = solver.getDependency(ref.name);
+    var oldDependency = dependency.clone();
+    dependency.placeConstraint(depender, ref);
+    return _processChange(solver, oldDependency, dependency);
+  }
+
+  void undo(GreedyVersionSolver solver) {
+    solver.getDependency(ref.name).removeConstraint(depender);
+  }
+}
+
+/// [depender] is no longer placing a constraint on [dependent].
+class RemoveConstraint extends ChangeConstraint {
+  /// The package that was placing a constraint on [dependent].
+  String depender;
+
+  /// The package that was being depended on.
+  String dependent;
+
+  /// The constraint that was removed.
+  PackageRef _removed;
+
+  RemoveConstraint(this.depender, this.dependent);
+
+  Future process(GreedyVersionSolver solver) {
+    log.fine("Removing $depender's constraint ($_removed) on $dependent.");
+
+    var dependency = solver.getDependency(dependent);
+    var oldDependency = dependency.clone();
+    _removed = dependency.removeConstraint(depender);
+    return _processChange(solver, oldDependency, dependency);
+  }
+
+  void undo(GreedyVersionSolver solver) {
+    solver.getDependency(dependent).placeConstraint(depender, _removed);
+  }
+}
+
+/// [package]'s version is no longer constrained by the lockfile.
+class UnlockPackage implements WorkItem {
+  /// The package being unlocked.
+  DependencyNode package;
+
+  UnlockPackage(this.package);
+
+  Future process(GreedyVersionSolver solver) {
+    log.fine("Unlocking ${package.name}.");
+
+    solver.lockFile.packages.remove(package.name);
+    return solver.getBestVersion(package).then((best) {
+      if (best == null) return null;
+      solver.enqueue(new ChangeVersion(
+          package.name, package.source, package.description, best));
+    });
+  }
+}
+
+/// Describes one [Package] in the [DependencyGraph] and keeps track of which
+/// packages depend on it and what constraints they place on it.
+class DependencyNode {
+  /// The name of the this dependency's package.
+  final String name;
+
+  /// The [PackageRefs] that represent constraints that depending packages have
+  /// placed on this one.
+  final Map<String, PackageRef> _refs;
+
+  /// The currently-selected best version for this dependency.
+  Version version;
+
+  /// Whether this dependency should always select the latest version.
+  bool useLatestVersion = false;
+
+  /// Gets whether or not any other packages are currently depending on this
+  /// one. If `false`, then it means this package is not part of the dependency
+  /// graph and should be omitted.
+  bool get isDependedOn => !_refs.isEmpty;
+
+  /// The names of all the packages that depend on this dependency.
+  Iterable<String> get dependers => _refs.keys;
+
+  /// Gets the overall constraint that all packages are placing on this one.
+  /// If no packages have a constraint on this one (which can happen when this
+  /// package is in the process of being added to the graph), returns `null`.
+  VersionConstraint get constraint {
+    if (_refs.isEmpty) return null;
+    return new VersionConstraint.intersection(
+        _refs.values.map((ref) => ref.constraint));
+  }
+
+  /// The source of this dependency's package.
+  Source get source {
+     var canonical = _canonicalRef();
+     if (canonical == null) return null;
+     return canonical.source;
+  }
+
+  /// The description of this dependency's package.
+  get description {
+     var canonical = _canonicalRef();
+     if (canonical == null) return null;
+     return canonical.description;
+  }
+
+  /// Return the PackageRef that has the canonical source and description for
+  /// this package. If any dependency is on the root package, that will be used;
+  /// otherwise, it will be the source and description that all dependencies
+  /// agree upon.
+  PackageRef _canonicalRef() {
+    if (_refs.isEmpty) return null;
+    var refs = _refs.values;
+    for (var ref in refs) {
+      if (ref.isRoot) return ref;
+    }
+    return refs.first;
+  }
+
+  DependencyNode(this.name)
+      : _refs = <String, PackageRef>{};
+
+  DependencyNode._clone(DependencyNode other)
+      : name = other.name,
+        version = other.version,
+        _refs = new Map<String, PackageRef>.from(other._refs);
+
+  /// Creates a copy of this dependency.
+  DependencyNode clone() => new DependencyNode._clone(this);
+
+  /// Places [ref] as a constraint from [package] onto this.
+  void placeConstraint(String package, PackageRef ref) {
+    var requiredDepender = _requiredDepender();
+    if (requiredDepender != null) {
+      var required = _refs[requiredDepender];
+      if (required.source.name != ref.source.name) {
+        throw new SourceMismatchException(name, [
+            new Dependency(requiredDepender, required),
+            new Dependency(package, ref)]);
+      } else if (!required.descriptionEquals(ref)) {
+        throw new DescriptionMismatchException(name, [
+            new Dependency(requiredDepender, required),
+            new Dependency(package, ref)]);
+      }
+    }
+
+    _refs[package] = ref;
+  }
+
+  /// Returns the name of a package whose constraint source and description
+  /// all other constraints must match. Returns null if there are no
+  /// requirements on new constraints.
+  String _requiredDepender() {
+    if (_refs.isEmpty) return null;
+
+    var dependers = _refs.keys.toList();
+    if (dependers.length == 1) {
+      var depender = dependers[0];
+      if (_refs[depender].isRoot) return null;
+      return depender;
+    }
+
+    return dependers[1];
+  }
+
+  /// Removes the constraint from [package] onto this.
+  PackageRef removeConstraint(String package) => _refs.remove(package);
+
+  /// Converts this to a list of [Dependency] objects like the error types
+  /// expect.
+  List<Dependency> toList() {
+    var result = <Dependency>[];
+    _refs.forEach((name, ref) {
+      result.add(new Dependency(name, ref));
+    });
+    return result;
+  }
+}