auto merge of #8656 : toddaaro/rust/idle-opt+cleaning, r=brson

Fixed a memory leak caused by the singleton idle callback failing to close correctly. The problem was that the close function requires running inside a callback in the event loop, but we were trying to close the idle watcher after the loop returned from run. The fix was to just call run again to process this callback. There is an additional tweak to move the initialization logic fully into bootstrap, so tasks that do not ever call run do not have problems destructing.

auto merge of #8631 : anasazi/rust/homing-io, r=brson

libuv handles are tied to the event loop that created them. In order to perform IO, the handle must be on the thread with its home event loop. Thus, when as task wants to do IO it must first go to the IO handle's home event loop and pin itself to the corresponding scheduler while the IO action is in flight. Once the IO action completes, the task is unpinned and either returns to its home scheduler if it is a pinned task, or otherwise stays on the current scheduler.

Making new blocking IO implementations (i.e. files) thread safe is rather simple. Add a home field to the IO handle's struct in uvio and implement the HomingIO trait. Wrap every IO call in the HomingIO.home_for_io method, which will take care of the scheduling.

I'm not sure if this remains thread safe in the presence of asynchronous IO at the libuv level. If we decide to do that, then this set up should be revisited.

Fixed a memory leak caused by the singleton idle callback failing to close correctly. The problem was that the close function requires running inside a callback in the event loop, but we were trying to close the idle watcher after the loop returned from run. The fix was to just call run again to process this callback. There is an additional tweak to move the initialization logic fully into bootstrap, so tasks that do not ever call run do not have problems destructing.

auto merge of #8563 : graydon/rust/2013-08-16-condition-tutorial, r=catamorphism

First cut of a tutorial on conditions.

cc: #6701

auto merge of #8519 : msullivan/rust/objects, r=catamorphism

r?

auto merge of #8328 : alexcrichton/rust/llvm-head, r=brson

The first commit message is pretty good, but whomever reviews this should probably also at least glance at the changes I made in LLVM. I basically reorganized our pending patch queue to be a bit more organized and clearer in what needs to go where. After this, our queue would be:

* Add the `no-split-stack` attribute
* Add the `fixedstacksegment` attribute
* Add split-stacks for arm android
* Add split-stacks for arm linux
* Add split stacks for mips

Then there's a patch which I added to get rust to build at all on LLVM-head, and I'm not quite sure why it's there, but nothing seems to be crashing for now! (famous last words).

Otherwise, I just updated code to reflect the changes I made in LLVM with the only major change being the advent of the new `no_split_stack` attribute. This is work towards #1226, but someone more familiar with the code should probably actually assign the attribute to the appropriate functions.

Also as a bonus, I've verified that this closes #5774

auto merge of #8566 : toddaaro/rust/idle-opt+cleaning, r=catamorphism,brson

Instead of a furious storm of idle callbacks we just have one. This is a major performance gain - around 40% on my machine for the ping pong bench.

Also in this PR is a cleanup commit for the scheduler code. Was previously up as a separate PR, but bors load + imminent merge hell led me to roll them together. Was #8549.

Fix LLVM compilation issues and use the new attrs

This implements #[no_split_stack] and also changes #[fast_ffi] to using the new
"fixedstacksegment" string attribute instead of integer attribute.

auto merge of #8463 : brson/rust/borrowck, r=nmatsakis,nikomatsakis

r? @nikomatsakis

auto merge of #8638 : pnkfelix/rust/fsk-visitor-vpar-defaults-step5, r=huonw

"non-mechanical" : there was lots more hacking than the other more-mechanical ports Felix did.

r? @huonw.  (Or @nikomatsakis ; I just want someone to sanity-check this.  Its not a thing of beauty.)

Followup to #8623.  (See #8527, which was step 1 of 5, for the full outline.  Part of #7081.)

Notes on the change follow.

There's also a strange pattern that I hacked in to accommodate the
Outer/Inner traversal structure of the existing code (which was
previously encoding this by untying the Y-combinator style knot of the
vtable, and then retying it but superimposing new methods that "stop
at items").  I hope either I or someone else can come back in the
future and replace this ugliness with something more natural.

Added boilerplate macro; all the OuterLint definitions are the same
(but must be abstracted over implementing struct, thus the macro).

Revised lint.rs use declarations to make ast references explicit.
Also removed unused imports.

add line break post dbaupp review.

remove trailing whitespace to placate make tidy.

Port lint.rs from oldvisit to <V:Visit> trait API.  Less mechanical port.

That is, there was lots more hacking than the other more-mechanical
ports Felix did.

There's also a strange pattern that I hacked in to accommodate the
Outer/Inner traversal structure of the existing code (which was
previously encoding this by untying the Y-combinator style knot of the
vtable, and then retying it but superimposing new methods that "stop
at items").  I hope either I or someone else can come back in the
future and replace this ugliness with something more natural.

Added boilerplate macro; all the OuterLint definitions are the same
(but must be abstracted over implementing struct, thus the macro).

Revised lint.rs use declarations to make ast references explicit.
Also removed unused imports.

Upgrade llvm to current HEAD

* This has one workaround patch (everything's testing just fine...)
* I reworked the fixedstacksegment attribute to be specified with a string
  rather than using a keyword and an integer and modifying the parser
* I added a "no-split-stack" attribute along the same lines as the
  "fixedstacksegment" attribute for #1226

auto merge of #8548 : catamorphism/rust/unignore-rustpkg-tests, r=catamorphism

r? @brson This necessitated some cleanup to how we parse library filenames
when searching for libraries, since rustpkg may now create filenames
that contain '-' characters. Also cleaned up how rustpkg passes the
sysroot to a custom build script.

std: Restore dynamic borrow tracking

auto merge of #8584 : thestinger/rust/jemalloc, r=graydon

This reverts commit 371a316ec93a977f9dcd305b5f532cd394fa6885.

Closes #7217

jemalloc: use $(AR), not `ar`

regenerate configure

auto merge of #8500 : graydon/rust/2013-08-13-self-rollup, r=thestinger

close #8424 r=brson
close #8173 r=brson
close #8209 r=strcat

doc: add condition tutorial

Make IO thread-safe.

Each IO handle has a home event loop, which created it.
When a task wants to use an IO handle, it must first make sure it is on that home event loop.
It uses the scheduler handle in the IO handle to send itself there before starting the IO action.
Once the IO action completes, the task restores its previous home state.
If it is an AnySched task, then it will be executed on the new scheduler.
If it has a normal home, then it will return there before executing any more code after the IO action.

Homed UDP sockets

Working homing UDP socket prototype.

Instruct event loops to ignore SIGPIPE when constructed.

libuv does not always catch SIGPIPE.

Do not execute the callback before cleaning up resources.

Derive Clone for IpAddr and SocketAddr

rt: make jemalloc header conform to android signature.

rustpkg: Un-ignore most of the remaining tests

This necessitated some cleanup to how we parse library filenames
when searching for libraries, since rustpkg may now create filenames
that contain '-' characters. Also cleaned up how rustpkg passes the
sysroot to a custom build script.

compiletest: do not run tests in sub-threads if on valgrind.

Try to fix mac valgrind bot by disabling thread-heavy activities.

Add tests for cross-crate condition handling. Close #5446.

test: add testcase, close #4929 which was already fixed.

test: un-xfail now working run-pass/foreign-struct.rs, close #2334.

auto merge of #8623 : pnkfelix/rust/fsk-visitor-vpar-defaults-step4, r=nmatsakis

Follow up to #8619 (step 3 of 5).

(See #8527, which was step 1 of 5, for the full outline.)

Part of #7081.

auto merge of #8459 : thestinger/rust/checked, r=graydon

clean whitespace :/

Make supertrait methods callable on object types.

This requires changes to method search and to codegen. We now emit a
vtable for objects that includes methods from all supertraits.
Closes #4100.

Also, actually populate the cache for vtables, and also key it by type
so that it actually works.

Rangechange the log message truncation limit.

auto merge of #8619 : pnkfelix/rust/fsk-visitor-vpar-defaults-step3, r=nmatsakis

Follow up to #8539 (step 2 of 5).

(See  #8527, which was step 1 of 5, for the full outline.)

Part of #7081.

auto merge of #8539 : pnkfelix/rust/fsk-visitor-vpar-defaults-step2, r=graydon,nikomatsakis

r? @nikomatsakis

Follow up to #8527 (which was step 1 of 5).  See that for overall description

Part of #7081

auto merge of #8535 : nikomatsakis/rust/issue-3678-wrappers-be-gone-2, r=graydon

Long-standing branch to remove foreign function wrappers altogether. Calls to C functions are done "in place" with no stack manipulation; the scheme relies entirely on the correct use of `#[fixed_stack_segment]` to guarantee adequate stack space. A linter is added to detect when `#[fixed_stack_segment]` annotations are missing. An `externfn!` macro is added to make it easier to declare foreign fns and wrappers in one go: this macro may need some refinement, though, for example it might be good to be able to declare a group of foreign fns. I leave that for future work (hopefully somebody else's work :) ).

Fixes #3678.

Add externfn macro and correctly label fixed_stack_segments

Issue #3678: Remove wrappers and call foreign functions directly

auto merge of #8564 : alexcrichton/rust/ifmt+++, r=graydon

See discussion in #8489, but this selects option 3 by adding a `Default` trait to be implemented by various basic types.

Once this makes it into a snapshot I think it's about time to start overhauling all current use-cases of `fmt!` to move towards `ifmt!`. The goal is to replace `%X` with `{}` in 90% of situations, and this commit should enable that.

auto merge of #8556 : sfackler/rust/quote, r=alexcrichton

They previously required one called "ext_cx" to be in scope.

Fixes part of #7727

auto merge of #8565 : bblum/rust/select-bugfix, r=brson

@brson grilled me about how this bugfix worked the first time around, and it occurred to me that it didn't in the case where the task is unwinding. Now it will.

auto merge of #8561 : kballard/rust/do-block-internal-err-msg, r=thestinger

When using a `do` block to call an internal iterator, if you forgot to
return a value from the body, it would tell you

    error: Do-block body must return bool, but returns () here. Perhaps
    you meant to write a `for`-loop?

This advice no longer applies as `for` loops are now for external
iterators. Delete this message outright and let it use the default error
message

    error: mismatched types: expected `bool` but found `()`

r? @thestinger

auto merge of #8560 : kballard/rust/reserve-yield, r=pcwalton

Rename task::yield() to task::deschedule().

Fixes #8494.

auto merge of #8545 : blake2-ppc/rust/iterbytes, r=alexcrichton

Address issue #5257, for example these values all had the same hash value:

("aaa", "bbb", "ccc")
("aaab", "bb", "ccc")
("aaabbb", "", "ccc")

IterBytes for &[A] now includes the length, before calling iter_bytes on
each element.

IterBytes for &str is now terminated by a byte that does not appear in
UTF-8. This way only one more byte is processed when hashing strings.

quote_*! macros take an ExtCtx

They previously required one called "ext_cx" to be in scope.

Fixes part of #7727

auto merge of #8558 : kballard/rust/xorshift-seed, r=cmr

Fixes #8359.

std::hash: Add testcase for colliding hashes of tuples

Add a testcase that verifies that (s, t) and (u, v) don't collide even if
s + t == u + v (concatenation).

std::to_bytes: Implement IterBytes on 1- to 8-tuples

std::to_bytes: Delimit sequences &[A] and ~str when hashing

Address issue #5257, for example these values all had the same hash value:

("aaa", "bbb", "ccc")
("aaab", "bb", "ccc")
("aaabbb", "", "ccc")

IterBytes for &[A] now includes the length, before calling iter_bytes on
each element.

IterBytes for &str is now terminated by a byte that does not appear in
UTF-8. This way only one more byte is processed when hashing strings.

auto merge of #8555 : chris-morgan/rust/time-clone, r=huonw

I need `Clone` for `Tm` for my latest work on [rust-http](https://github.com/chris-morgan/rust-http) (static typing for headers, and headers like `Date` are a time), so here it is.

@huonw recommended deriving DeepClone while I was at it.

I also had to implement `DeepClone` for `~str` to get a derived implementation of `DeepClone` for `Tm`; I did `@str` while I was at it, for consistency.

auto merge of #8551 : huonw/rust/speling, r=alexcrichton

(This doesn't add/remove `u`s or change `ize` to `ise`, or anything like that.)

auto merge of #8550 : kballard/rust/token-start-err-msg, r=catamorphism

The span was fixed at some point to point to the correct character, but
the error message is still bad. Update it to emit the actual character
in question (potentially escaped).

Fixes #3747.

auto merge of #8547 : kballard/rust/trait-parse-err-msg, r=alexcrichton

When parsing a trait function, the function must end with either `;` or
`{` (signifying a default implementation). The error message incorrectly
stated that it must be `;` or `}`.

Fixes #6610.

auto merge of #8544 : dim-an/rust/fix-match-pipes, r=pcwalton

Pointers to bound variables shouldn't be stored before checking pattern,
otherwise piped patterns can conflict with each other (issue #6338).

Closes #6338.

Revert "Turn off jemalloc"

This reverts commit 371a316ec93a977f9dcd305b5f532cd394fa6885.

Closes #7217

More spelling corrections.

auto merge of #8554 : michaelwoerister/rust/generics, r=brson

This pull request includes support for generic functions and self arguments in methods, and combinations thereof. This also encompasses any kind of trait methods, regular and static, with and without default implementation. The implementation is backed up by a felt ton of test cases `:)`

This is a very important step towards being able to compile larger programs with debug info, since practically any generic function caused an ICE before.

One point worth discussing is that activating debug info now automatically (and silently) sets the `no_monomorphic_collapse` flag. Otherwise debug info would show wrong type names in all but one instance of the monomorphized function.

Another thing to note is that the handling of generic types does not strictly follow the DWARF specification. That is, variables with type `T` (where `T=int`) are described as having type `int` and not as having type `T`. In other words, we are losing information whether a variable has been declared with a type parameter as its type. In practice this should not make much of difference though since the concrete type is mostly what one is interested in. I'll post an issue later so this won't be forgotten.

Also included are a number of bug fixes:
* Closes #1758
* Closes #8513
* Closes #8443
* Fixes handling of field names in tuple structs
* Fixes and re-enables test case for option-like enums that relied on undefined behavior before
* Closes #1339 (should have been closed a while ago)

Cheers,
Michael

auto merge of #8433 : brson/rust/rm-more-oldrt-crud, r=brson

Just deleting more stuff.

auto merge of #8441 : erickt/rust/deny-warnings, r=erickt

This patch makes sure that code is warning-free for all of the rust libraries.

Deny warnings in stage1+ libsyntax/librustc/librustdoc/librusti/librust

Fix warnings it tests

Fix warnings in librustc and libsyntax

Fix warnings in tests

auto merge of #8272 : DaGenix/rust/digest-md5-impl-not-unrolled, r=cmr

An MD5 implementation was originally included in #8097, but, since there are a couple different implementations of that digest algorithm (@alco mentioned his implementation on the mailing list just before I opened that PR), it was suggested that I remove it from that PR and open up a new PR to discuss the different implementations and the best way forward. If anyone wants to discuss a different implementation, feel free to present it here and discuss and compare it to this one. I'll just discuss my implementation and I'll leave it to others to present details of theirs.

This implementation relies on the FixedBuffer struct from cryptoutil.rs for managing the input buffer, just like the Sha1 and Sha2 digest implementations do. I tried manually unrolling the loops in the compression function, but I got slightly worse performance when I did that.

Outside of the #[test]s, I also tested the implementation by generating 1,000 inputs of up to 10MB in size and checking the MD5 digest calculated by this code against the MD5 digest calculated by Java's implementation.

On my computer, I'm getting the following performance:

```
test md5::bench::md5_10 ... bench: 52 ns/iter (+/- 1) = 192 MB/s
test md5::bench::md5_1k ... bench: 2819 ns/iter (+/- 44) = 363 MB/s
test md5::bench::md5_64k ... bench: 178566 ns/iter (+/- 4927) = 367 MB/s
```

auto merge of #8053 : gavinb/rust/uuid_std, r=alexcrichton

Addresses part of #7104

This module adds the ability to generate UUIDs (on all Rust-supported platforms).

I reviewed the existing UUID support in libraries for a range of languages; Go, D, C#, Java and Boost++. The features were all very similar, and this patch essentially covers the union.  The implmentation is quite straightforward, and uses the underlying rng support which is assumed to be sufficiently strong for this purpose.

This patch is not complete, however I have put this up for review to gather feedback before finalising. It has tests for most features and documentation for most functions.

Outstanding issues:

* Only generates V4 (Random) UUIDs. Do we want to support the SHA-1 hash based flavour as well?
* Is it worth having the field-based struct public as well as the byte array?
* Formatting the string with '-' between groups not done yet.
* Parsing full string not done as there appears to be no regexp support yet. I can write a simple manual parser for now?
* D has a generator as well. This would be easy to add. However, given the simple interface for creating a new one, and the presence of the macro, is this useful?
* Is it worth having a separate UUID trait and specific implementation? Or should it just have a struct+impl with the same name? Currently it feels weird to have the trait (which can't be named UUID so as to conflict) a separate thing.
* Should the macro be visible at the top level scope?

As this is a first attempt, some code may not be idiomatic. Please comment below...

Thanks for all feedback!

auto merge of #8531 : brson/rust/test-waitpid-workaround, r=graydon

...er

I believe the calls to waitpid are interacting badly with the message passing that goes
on between schedulers and causing us to have very little parallelism in
the test suite. I don't fully understand the sequence of events that causes
the problem here but clearly blocking on waitpid is something that a
well-behaved task should not be doing.

Unfortunately this adds quite a bit of overhead to each test: one thread, two
tasks, three stacks, so there's a tradeoff. The time to execute run-pass on
my 4-core machine goes from ~750s to ~300s.

This should have a pretty good impact on cycle times.

cc @toddaaro

Crypto: Add tests for add_bytes_to_bits functions.

Crypto: update checked addition functions to use CheckedAdd intrinsic.

The shift_add_check_overflow and shift_add_check_overflow_tuple functions are
re-written to be more efficient and to make use of the CheckedAdd instrinsic
instead of manually checking for integer overflow.

* The invokation leading_zeros() is removed and replaced with simple integer
  comparison. The leading_zeros() method results in a ctpop LLVM instruction
  and it may not be efficient on all architectures; integer comparisons,
  however, are efficient on just about any architecture.
* The methods lose the ability for the caller to specify a particular shift
  value - that functionality wasn't being used and removing it allows for the
  code to be simplified.
* Finally, the methods are renamed to add_bytes_to_bits and
  add_bytes_to_bits_tuple to reflect their very specific purposes.

MD5: Create an implementation of MD5.

Crypto: Add little-endian versions of existing functions: read_u32v_le and write_u32_le.

A round of code cleaning for the primary scheduler code. Comments have been updated, a minor amount of support type restructing has happened, methods have been reordered, and some duplicate code has been purged.

Moved the logic for a pausible idle callback into a new type - PausibleIdleCallback and placed the appropriate signatures in rtio and implementation into uvio.

std::rt: Fix a race in UvRemoteCallback's dtor that misses callbacks

Full description in comments.

std::rt: Touch up idle logic

an attempt at a singleton pausible idle callback for each scheduler. suffers from nondeterministic deadlock and also pending scheduler messages on scheduler shutdown.

Delegate `{}` to Default instead of Poly

By using a separate trait this is overridable on a per-type basis and makes room
for the possibility of even more arguments passed in for the future.

Implement `{:s}` for ~str and @str as well

Remove obsolete error message regarding do-blocks with internal iters

When using a `do` block to call an internal iterator, if you forgot to
return a value from the body, it would tell you

    error: Do-block body must return bool, but returns () here. Perhaps
    you meant to write a `for`-loop?

This advice no longer applies as `for` loops are now for external
iterators. Delete this message outright and let it use the default error
message

    error: mismatched types: expected `bool` but found `()`

debuginfo: Added test cases for static struct and enum methods.

debuginfo: Test cases for [generic][default][static] methods and functions:

* closure-in-generic-function
* generic-functions-nested
* generic-method-on-generic-struct
* generic-trait-generic-static-default-method
* method-on-generic-struct
* self-in-generic-default-method
* trait-generic-static-default-method

Also, fixed an 'unused variable' warning in debuginfo.rs

debuginfo: Support for combinations of Self type and type parameters.

debuginfo: Add test case for issue #8513.

debuginfo: Implemented support for Self type parameter in trait methods with default implementation.

debuginfo: Added test cases for methods on structs, enums, traits, and tuple-structs.

Also new test cases for tuple structs and by-value parameter passing.

debuginfo: Added support for self parameter in methods.

debuginfo: Fixed crash occuring for parameterless closures.

debuginfo: Added test cases for generic structs and enums.

Also, always set no_monomorphic_collapse flags if debuginfo is generated.

debuginfo: Properly handle monomorphization of generic functions.

debuginfo: Generate template type parameters for generic functions.

Conflicts:
src/librustc/lib/llvm.rs
src/librustc/middle/trans/debuginfo.rs
src/rustllvm/RustWrapper.cpp
src/rustllvm/rustllvm.def.in

debuginfo: Fixed option-like-enum test case so it does not rely on undefined behavior.

Reserve 'yield' keyword

Rename task::yield() to task::deschedule().

Fixes #8494.

rt: Remove unused uv helpers

rt: Remove empty rust_upcall.h

rt: Remove unused rust_clone_type_desc declaration