Instead of reimplementing chained hash tables, just use maps.

Use bool instead of uint8 for variables only set to 0 or 1.

Fix parsing of `import foo "foo" // indirect` lines.  Previously, this
was treated as an import of package path `"foo" // indirect`, which
could result in the cycle-detection code failing to detect a cycle
because it would be treated as a separate package from `"foo"`.

Also, since there are theoretically multiple quoted forms for a
package path, use strconv.Unquote to normalize them.  Side benefit:
Unquote will complain if any trailing comments sneak back in.

Aside: For most Go archives, Go package data is only present in the
__.PKGDEF member, but unless -u is used, ldpkg is only called on the
_go_.6 member.  Consequently, importcycles is a no-op when -u isn't
used as it has no package data to inspect.

Change-Id: I7076cf91a66726a8d9c5676adfea13c5532001fa
Reviewed-on: https://go-review.googlesource.com/7002Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Rob Pike <r@golang.org>

The imageutil.DrawYCbCr function lives in an internal package because it
is needed by both the image/draw and image/jpeg packages, but it doesn't
seem right for one of those two to depend on the other.

It could eventually go into the image package, but that would require
committing to an API for the rest of Go 1.x.

Change-Id: I7b12555c970d86409365e99eef9360702aaffa30
Reviewed-on: https://go-review.googlesource.com/7925Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Rob Pike <r@golang.org>

Previously, running 'go get' with a local path would correctly
download the package but fail to install it.
This is because a sticky error - resulting from discovering that the
package needed to be downloaded - was still around.
Theoretically, such sticky errors would be cleared but they weren't
because the map tracking these errors were indexed with the correct
canonical import path of the package (e.g. "ex.com/x/pkg") whereas the
clearing was done with the local path (e.g. "./pkg".)

Always use the canonical import path.

Fixes #9767

Change-Id: Ia0e8a51ac591d4c833d11285da5b767ef7ed8ad2
Reviewed-on: https://go-review.googlesource.com/6266Reviewed-by: Rob Pike <r@golang.org>

Fixes #10224

Change-Id: I21037379b4667575e51ab0b6b683138c505c3f68
Reviewed-on: https://go-review.googlesource.com/7960Reviewed-by: David Crawshaw <crawshaw@golang.org>

Change-Id: I4d35a96ace71b68a91561c08fd7331859d9dd19d
Reviewed-on: https://go-review.googlesource.com/5593Reviewed-by: Dmitry Vyukov <dvyukov@google.com>

Change-Id: Ie45d45649ea978becf84eb911cf4ace1dd237d9e
Reviewed-on: https://go-review.googlesource.com/7918Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: Ib8df771957f9a5bf00bee7eb8cb361d4acd5813f
Reviewed-on: https://go-review.googlesource.com/7911Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

This test was introduced in cl/5130 and broke the darwin/arm builder.

Also check some errors, which was making the failure hard to decipher.

Change-Id: Ifb1d60b9971782cf8d2e979d83f8a81249d7ee9b
Reviewed-on: https://go-review.googlesource.com/7932Reviewed-by: Rob Pike <r@golang.org>

Since there is internal usage of svg files in cmd/trace served via
HTTP, add it to the (small) map of mime types.

MIME type as documented at http://www.w3.org/TR/SVG11/mimereg.html

Change-Id: If14f07cbe2e55d8d68af663f30920a530e2e7974
Reviewed-on: https://go-review.googlesource.com/7942Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>

This is a port of RE2's bitstate backtracker, which triggers under
the same conditions that the RE2 backtracker triggers.  However I wasn't
sure how to port over some of the optimizations in the RE2 backtracker,
and there is a ~2% penalty on benchmarks that don't trigger the backtracker.

benchmark                                 old ns/op      new ns/op      delta
BenchmarkLiteral                          312            189            -39.42%
BenchmarkNotLiteral                       4435           3001           -32.33%
BenchmarkMatchClass                       5758           4378           -23.97%
BenchmarkMatchClass_InRange               5385           4084           -24.16%
BenchmarkReplaceAll                       5291           3505           -33.76%
BenchmarkAnchoredLiteralShortNonMatch     190            200            +5.26%
BenchmarkAnchoredLiteralLongNonMatch      189            194            +2.65%
BenchmarkAnchoredShortMatch               479            304            -36.53%
BenchmarkAnchoredLongMatch                478            499            +4.39%
BenchmarkOnePassShortA                    791            798            +0.88%
BenchmarkNotOnePassShortA                 3202           1571           -50.94%
BenchmarkOnePassShortB                    614            633            +3.09%
BenchmarkNotOnePassShortB                 2685           881            -67.19%
BenchmarkOnePassLongPrefix                152            154            +1.32%
BenchmarkOnePassLongNotPrefix             505            533            +5.54%
BenchmarkMatchEasy0_32                    139            171            +23.02%
BenchmarkMatchEasy0_1K                    653            1797           +175.19%
BenchmarkMatchEasy0_32K                   12032          13346          +10.92%
BenchmarkMatchEasy0_1M                    462882         461272         -0.35%
BenchmarkMatchEasy0_32M                   15015339       15365238       +2.33%
BenchmarkMatchEasy1_32                    122            168            +37.70%
BenchmarkMatchEasy1_1K                    3339           2612           -21.77%
BenchmarkMatchEasy1_32K                   72330          71721          -0.84%
BenchmarkMatchEasy1_1M                    2545410        2652284        +4.20%
BenchmarkMatchEasy1_32M                   80072063       82609750       +3.17%
BenchmarkMatchMedium_32                   2359           1980           -16.07%
BenchmarkMatchMedium_1K                   75939          58593          -22.84%
BenchmarkMatchMedium_32K                  2450907        2501106        +2.05%
BenchmarkMatchMedium_1M                   78707697       80174418       +1.86%
BenchmarkMatchMedium_32M                  2535146010     2570896441     +1.41%
BenchmarkMatchHard_32                     4297           2960           -31.11%
BenchmarkMatchHard_1K                     133592         88997          -33.38%
BenchmarkMatchHard_32K                    4240445        4336907        +2.27%
BenchmarkMatchHard_1M                     136187006      139350238      +2.32%
BenchmarkMatchHard_32M                    4350855890     4478537306     +2.93%

benchmark                    old MB/s     new MB/s     speedup
BenchmarkMatchEasy0_32       228.74       186.11       0.81x
BenchmarkMatchEasy0_1K       1565.91      569.64       0.36x
BenchmarkMatchEasy0_32K      2723.31      2455.10      0.90x
BenchmarkMatchEasy0_1M       2265.32      2273.22      1.00x
BenchmarkMatchEasy0_32M      2234.68      2183.79      0.98x
BenchmarkMatchEasy1_32       261.08       190.22       0.73x
BenchmarkMatchEasy1_1K       306.59       391.91       1.28x
BenchmarkMatchEasy1_32K      453.03       456.88       1.01x
BenchmarkMatchEasy1_1M       411.95       395.35       0.96x
BenchmarkMatchEasy1_32M      419.05       406.18       0.97x
BenchmarkMatchMedium_32      13.56        16.16        1.19x
BenchmarkMatchMedium_1K      13.48        17.48        1.30x
BenchmarkMatchMedium_32K     13.37        13.10        0.98x
BenchmarkMatchMedium_1M      13.32        13.08        0.98x
BenchmarkMatchMedium_32M     13.24        13.05        0.99x
BenchmarkMatchHard_32        7.45         10.81        1.45x
BenchmarkMatchHard_1K        7.67         11.51        1.50x
BenchmarkMatchHard_32K       7.73         7.56         0.98x
BenchmarkMatchHard_1M        7.70         7.52         0.98x
BenchmarkMatchHard_32M       7.71         7.49         0.97x

Fixes #4154

Change-Id: Iff7fb9507f0872b320d08afc08679751ed1b28bc
Reviewed-on: https://go-review.googlesource.com/2153Reviewed-by: Russ Cox <rsc@golang.org>

On Unix, when placing a child in a new process group, allow that group
to become the foreground process group. Also, allow a child process to
join a specific process group.

When setting the foreground process group, Ctty is used as the file
descriptor of the controlling terminal. Ctty has been added to the BSD
and Solaris SysProcAttr structures and the handling of Setctty changed
to match Linux.

Change-Id: I18d169a6c5ab8a6a90708c4ff52eb4aded50bc8c
Reviewed-on: https://go-review.googlesource.com/5130
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>

Issue #10043 was resolved by https://golang.org/cl/7072.
This test now passes.

Change-Id: I7bdef63d9ee4edcede23613a14a2ddce14018f34
Reviewed-on: https://go-review.googlesource.com/7931Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Fixes #10214.

Change-Id: If29d26c590eb53d4976e0a6ace0ed33aaf0c3e80
Reviewed-on: https://go-review.googlesource.com/7924Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Alex Brainman <alex.brainman@gmail.com>

ServeContent ignored zero time.Time{} values when generating
Last-Modified response headers and checking If-Modified-Since request
headers. Do the same for a time.Time representing the Unix epoch zero
value, as this is a common bogus value. Callers who really want to
send that value (incredibly unlikely) can add a nanosecond to it and
it will be truncated to second granularity anyway.

Fixes #9842

Change-Id: I69f697bfc4017404a92a34e3fe57e2711c1e299d
Reviewed-on: https://go-review.googlesource.com/7915Reviewed-by: David Symonds <dsymonds@golang.org>

Change-Id: I9968f53a8286a0e5ccc197a9b5fae499e2f95326
Reviewed-on: https://go-review.googlesource.com/7790Reviewed-by: Rob Pike <r@golang.org>

Change-Id: I5b057d16eed1b364e608ff0fd74de323da6492bc
Reviewed-on: https://go-review.googlesource.com/7679Reviewed-by: Minux Ma <minux@golang.org>

Implement runtime.atomicand8 for amd64p32 which was overlooked
in CL 7861.

Change-Id: Ic7eccddc6fd6c4682cac1761294893928f5428a2
Reviewed-on: https://go-review.googlesource.com/7920Reviewed-by: Minux Ma <minux@golang.org>

      to map element keys

Composite literals containing element values that are themselves composite
literals may leave away the element's literal types if they are identical
to the enclosing composite literal's element type.

(http://golang.org/ref/spec#Composite_literals)

When we made this change, we forgot to apply the analogous rule to map
literal keys. This change generalizes that rule. Added more examples,
including one showing the recursive application of the elision rules.

This is a fully backward-compatible language change. It was discussed
some time back.

Fixes #8589.

To be submitted once all compilers accept the extension.

Change-Id: I4d45b64b5970f0d5501572945d5a097e64a9458b
Reviewed-on: https://go-review.googlesource.com/2591Reviewed-by: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>

Change-Id: I5e11a76ebb20284618144be2ef5449d3202b6222
Reviewed-on: https://go-review.googlesource.com/7900Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Per pending https://go-review.googlesource.com/2591 .

Change-Id: I1ce9d1c629e9fc43dbd862b3433aa5840f46656c
Reviewed-on: https://go-review.googlesource.com/2621Reviewed-by: Alan Donovan <adonovan@google.com>

To use a pure Go implementation of the low-level arithmetic
functions (when no platform-specific assembly implementations
are available), set the build tag math_big_pure_go.

This will make it easy to vendor the math/big package where no
assembly is available (for instance for use with gc which relies
on 1.4 functionality for now).

Change-Id: I91e17c0fdc568a20ec1512d7c64621241dc60c17
Reviewed-on: https://go-review.googlesource.com/7856Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

These can be implemented with just a compare and a move instruction.
Do so, avoiding the overhead of a call into the runtime.

These assertions are a significant cost in Go code that uses interface{}
as a safe alternative to C's void* (or unsafe.Pointer), such as the
current version of the Go compiler.

*T here includes pointer to T but also any Go type represented as
a single pointer (chan, func, map). It does not include [1]*T or struct{*int}.
That requires more work in other parts of the compiler; there is a TODO.

Change-Id: I7ff681c20d2c3eb6ad11dd7b3a37b1f3dda23965
Reviewed-on: https://go-review.googlesource.com/7862Reviewed-by: Rob Pike <r@golang.org>

This CL moves the bulk of the code that has been copy-and-pasted
since the initial 386 port back into a shared place, cutting 5 copies to 1.

The motivation here is not cleanup per se but instead to reduce the
cost of introducing changes in shared concepts like regalloc or general
expression evaluation. For example, a change after this one will
implement x.(*T) without a call into the runtime. This CL makes that
followup work 5x easier.

The single copy still has more special cases for architecture details
than I'd like, but having them called out explicitly like this at least
opens the door to generalizing the conditions and smoothing out
the distinctions in the future.

This is a LARGE CL. I started by trying to pull in one function at a time
in a sequence of CLs and it became clear that everything was so
interrelated that it had to be moved as a whole. Apologies for the size.

It is not clear how many more releases this code will matter for;
eventually it will be replaced by Keith's SSA work. But as noted above,
the deduplication was necessary to reduce the cost of working on
the current code while we have it.

Passes tests on amd64, 386, arm, and ppc64le.
Can build arm64 binaries but not tested there.
Being able to build binaries means it is probably very close.

Change-Id: I735977f04c0614f80215fb12966dfe9bbd1f5861
Reviewed-on: https://go-review.googlesource.com/7853Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

text/template turned this into an error but html/template crashed.
Refactor text/template.Execute to export a new function,
text/template.DefinedTemplates, so html/template can get the same
helpful error message in this case, and invoke it when there is no
definition for a template being escaped.

Fixes #10204.

Change-Id: I1d04e9e7ebca829bc08509caeb65e75da969711f
Reviewed-on: https://go-review.googlesource.com/7855Reviewed-by: Russ Cox <rsc@golang.org>

Regular expression noteMarker requires the definition of a (who) section
when reading note from a sequence of comments.

Change-Id: I9635de9b86f00d20ec108097fee4d4a8f76237b2
Reviewed-on: https://go-review.googlesource.com/1952Reviewed-by: Russ Cox <rsc@golang.org>

Mkdir and OpenFile call Chmod internally on *BSD and Solaris,
because these OSes don't handle the sticky bit correctly.

However Chmod's error should be ignored. It shouldn't hide
the fact that a file itself is created.

Fixes #8383

Change-Id: Ia2e0b2ba72712d73a0a48ba5a263432e0fff31a5
Reviewed-on: https://go-review.googlesource.com/2057Reviewed-by: Russ Cox <rsc@golang.org>

Change-Id: I6b49ca1b7ee39d138aafad5875767ce93a6344f3
Reviewed-on: https://go-review.googlesource.com/7851Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>

- renamed (existing) Mpint -> Mpfix
- defined (new) Mpint using big.Int
- modified funcs mpxxx operating on new Mpint
- renamed funcs mpxxx -> _mpxxx if still needed with Mpfix
- left old (possibly unused) code in place for comparison

Passes all.bash.

Change-Id: I1fc7bba7dc4b6386f2f0950d745cec17c1e67615

cmd/internal/gc: renamed Mpint -> Mpfix

Change-Id: Ia06aeae1081ef29d5ad9b711fb57e4c5579ce29b
Reviewed-on: https://go-review.googlesource.com/7830Reviewed-by: Russ Cox <rsc@golang.org>

Currently, we only exit the getfull barrier if there is work on the
full list, even though the exit path will take work from either the
full or partial list. Change this to exit the barrier if there is work
on either the full or partial lists.

I believe it's currently safe to check only the full list, since
during mark termination there is no reason to put a workbuf on a
partial list. However, checking both is more robust.

Change-Id: Icf095b0945c7cad326a87ff2f1dc49b7699df373
Reviewed-on: https://go-review.googlesource.com/7840Reviewed-by: Rick Hudson <rlh@golang.org>

The barrier in gcDrain does not account for concurrent gcDrainNs
happening in gchelpwork, so it can actually return while there is
still work being done. It turns out this is okay, but for subtle
reasons involving gcDrainN always being run on the system
stack. Document these reasons.

Change-Id: Ib07b3753cc4e2b54533ab3081a359cbd1c3c08fb
Reviewed-on: https://go-review.googlesource.com/7736Reviewed-by: Rick Hudson <rlh@golang.org>

Updates #4943

Change-Id: I082b97ccd787cf91245d39b8d93783732db6f42c
Reviewed-on: https://go-review.googlesource.com/6171Reviewed-by: Nigel Tao <nigeltao@golang.org>

Make mask uint32, and move down one line to match atomic_arm64.go.

Change-Id: I4867de494bc4076b7c2b3bf4fd74aa984e3ea0c8
Reviewed-on: https://go-review.googlesource.com/7854Reviewed-by: Russ Cox <rsc@golang.org>

Change-Id: I652cc7a33a186d1041f62f6e7581421496832a27
Reviewed-on: https://go-review.googlesource.com/7747Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

Also clean up code a little.

Change-Id: I23b7d2b7871b31e0974f1305e54f0c18dcab05d9
Reviewed-on: https://go-review.googlesource.com/7746Reviewed-by: Dave Cheney <dave@cheney.net>
Reviewed-by: Rob Pike <r@golang.org>

The ProgInfo is loaded many times during each analysis pass.
Load it once at the beginning (in Flowstart if using that, or explicitly,
as in plive.go) and then refer to the cached copy.

Removes many calls to proginfo.

Makes Prog a little bigger, but the previous CL more than compensates.

Change-Id: If90a12fc6729878fdae10444f9c3bedc8d85026e
Reviewed-on: https://go-review.googlesource.com/7745Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

An interface{} is more in the spirit of the original union.
By my calculations, on 64-bit systems this reduces
Addr from 120 to 80 bytes, and Prog from 592 to 424 bytes.

Change-Id: I0d7b0981513c2a3c94c9ac76bb4f8816485b5a3c
Reviewed-on: https://go-review.googlesource.com/7744Reviewed-by: Rob Pike <r@golang.org>

We're skating on thin ice, and things are finally starting to melt around here.
(I want to avoid the debugging session that will happen when someone
uses atomicand8 expecting it to be atomic with respect to other operations.)

Change-Id: I254f1582be4eb1f2d7fbba05335a91c6bf0c7f02
Reviewed-on: https://go-review.googlesource.com/7861Reviewed-by: Minux Ma <minux@golang.org>

Change-Id: I847bf32bd0be913fad277c5e657f44df147eee14
Reviewed-on: https://go-review.googlesource.com/7729Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Minux Ma <minux@golang.org>

Change-Id: I99aee6dff97a4abcaf5a9cddb505ba90b65667ea
Reviewed-on: https://go-review.googlesource.com/7728Reviewed-by: Rob Pike <r@golang.org>

Fixes #9825.

Change-Id: Id7eeaa14c26201db34db0820371c92a63af485b0
Reviewed-on: https://go-review.googlesource.com/7604Reviewed-by: Rob Pike <r@golang.org>