| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
| |
Miscellania:
Miscellania is a small island off the northernmost part
of the Fremennik Isles - RunScape Wiki
Miscellanea:
A collection of miscellaneous objects or writings - Merriam-Webster
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
During large compilations runs, the large numbers of globally unique
fresh names for existentials captured from prefixes of `asSeenFrom`.
is a) somewhat wasteful (all these names are interned in the name table)
, and, b) form a pathological case for the current implementation of
`Names#hashValue`, which leads to overfull hash-buckets in the name table.
`hashValue` should probably be improved, but my attempts to do so have
shown a small performance degradation in some benchmarks. So this commit
starts by being more frugal with these names, only uniquely naming
within an `asSeenFrom` operation.
References scala/scala-dev#246
|
| |\
| |
| |
| |
| |
| |
| |
| |
| | |
Conflicts:
src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala
src/compiler/scala/tools/nsc/transform/Constructors.scala
src/compiler/scala/tools/nsc/typechecker/Contexts.scala
src/scaladoc/scala/tools/nsc/doc/html/page/Template.scala
src/scaladoc/scala/tools/nsc/doc/html/resource/lib/jquery.layout.js
|
| | |
| |
| |
| | |
The the word 'the' is often used twice. Fix that.
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Hash consing of trees within pattern match analysis was broken, and
considered `x1.foo#1` to be the same tree as `x1.foo#2`, even though
the two `foo`-s referred to different symbols.
The hash consing was based on `Tree#correspondsStructure`, but the
predicate in that function cannot veto correspondance, it can only
supplement the default structural comparison.
I've instead created a custom tree comparison method for use in
the pattern matcher that handles the tree shapes that we use.
|
| |/
|
|
|
|
|
|
|
|
| |
- Language imports are preceding other imports
- Deleted empty file: InlineErasure
- Removed some unused private[parallel] methods in
scala/collection/parallel/package.scala
This removes hundreds of warnings when compiling with
"-Xlint -Ywarn-dead-code -Ywarn-unused -Ywarn-unused-import".
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
- Any.scala: Link to the guide instead of the SIP.
- AnyVal.scala: Remove SIP link and align guide link to Any.scala.
- Commands.scala: Use a less out of date team link.
- Logic.scala: Link was broken. Substitute found.
- Process.scala: Links were 403 & 404. Fixed as this is a code sample.
- TypeMaps.scala: Move old EPFL Trac to JIRA.
- RedBlackTree.scala: Replaced broken link with substitutes based on site maintainer input [1].
[1] When asked where Data-Set-RBTree.html had gone Don@UNSW advised
"I think it's on the Haskell wiki now. It was Chris Okazaki's version".
The closest I could find to what this document probably was is this
paper by Hinze edited by Okasaki,
http://www.cs.ox.ac.uk/ralf.hinze/publications/WAAAPL99b.ps.gz
The paper cites the Okasaki document so I included a link to that as
well.
The Haskell Wiki does have a link to a RB document but that's broken
too,
https://wiki.haskell.org/Research_papers/Data_structures >
Constructing red-black trees
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Faster analysis of wide (but relatively flat) class hierarchies
by using a more efficient encoding of mutual exclusion.
The old CNF encoding for mutually exclusive symbols of a domain
added a quadratic number of clauses to the formula to satisfy.
E.g. if a domain has the symbols `a`, `b` and `c` then
the clauses
```
!a \/ !b /\
!a \/ !c /\
!b \/ !c
```
were added.
The first line prevents that `a` and `b` are both true at the same time, etc.
There's a simple, more efficient encoding that can be used instead: consider a
comparator circuit in hardware, that checks that out of `n` signals, at most 1
is true. Such a circuit can be built in the form of a sequential counter and
thus requires only 3n-4 additional clauses [1]. A comprehensible comparison of
different encodings can be found in [2].
[1]: http://www.carstensinz.de/papers/CP-2005.pdf
[2]: http://www.wv.inf.tu-dresden.de/Publications/2013/report-13-04.pdf
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
reachability analysis are too big to be solved in reasonable time, then we skip
the analysis. I also cleaned up warnings.
Why did `t9181.scala` work fine with 2.11.4, but is now running out of memory?
In order to ensure that the scrutinee is associated only with one of the 400
derived classes we add 400*400 / 2 ~ 80k clauses to ensure mutual exclusivity.
In 2.11.4 the translation into CNF used to fail, since it would blow up already
at this point in memory. This has been fixed in 2.11.5, but now the DPLL solver
is the bottleneck.
There's a check in the search for all models (exhaustivity) that it would avoid
a blow up, but in the search for a model (reachability), such a check is
missing.
|
| |\
| |
| | |
Fix many typos in docs and comments
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
This commit corrects many typos found in scaladocs, comments and
documentation. It should reduce a bit number of PRs which fix one
typo.
There are no changes in the 'real' code except one corrected name of
a JUnit test method and some error messages in exceptions. In the case
of typos in other method or field names etc., I just skipped them.
Obviously this commit doesn't fix all existing typos. I just generated
in IntelliJ the list of potential typos and looked through it quickly.
|
| | | |
|
| |/
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
The OOM could occur when all models are forcibly expanded in the DPLL solver.
The simplest solution would be to limit the number of returned models but then
we are back in non-determinism land (since the subset we get back depends on
which models were found first).
A better alternative is to create only the models that have corresponding
counter examples.
If this does not ring a bell, here's a longer explanation:
TThe models we get from the DPLL solver need to be mapped back to counter
examples. However there's no precalculated mapping model -> counter example.
Even worse, not every valid model corresponds to a valid counter example.
The reason is that restricting the valid models further would for example
require a quadratic number of additional clauses. So to keep the optimistic case
fast (i.e., all cases are covered in a pattern match), the infeasible counter
examples are filtered later.
The DPLL procedure keeps the literals that do not contribute to the solution
unassigned, e.g., for `(a \/ b)` only {a = true} or {b = true} is required and
the other variable can have any value. This function does a smart expansion of
the model and avoids models that have conflicting mappings.
For example for in case of the given set of symbols (taken from `t7020.scala`):
"V2=2#16"
"V2=6#19"
"V2=5#18"
"V2=4#17"
"V2=7#20"
One possibility would be to group the symbols by domain but
this would only work for equality tests and would not be compatible
with type tests.
Another observation leads to a much simpler algorithm:
Only one of these symbols can be set to true,
since `V2` can at most be equal to one of {2,6,5,4,7}.
TODO: How does this fare with mixed TypeConst/ValueConst assignments?
When the assignments are e.g., V2=Int | V2=2 | V2=4, only the assignments
to value constants are mutually exclusive.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
The exhaustivity checks in the pattern matcher build a propositional
formula that must be converted into conjunctive normal form (CNF) in
order to be amenable to the following DPLL decision procedure.
However, the simple conversion into CNF via negation normal form and
Shannon expansion that was used has exponential worst-case complexity
and thus even simple problems could become untractable.
A better approach is to use a transformation into an _equisatisfiable_
CNF-formula (by generating auxiliary variables) that runs with linear
complexity. The commonly known Tseitin transformation uses bi-
implication. I have choosen for an enhancement: the Plaisted
transformation which uses implication only, thus the resulting CNF
formula has (on average) only half of the clauses of a Tseitin
transformation.
The Plaisted transformation uses the polarities of sub-expressions to
figure out which part of the bi-implication can be omitted. However,
if all sub-expressions have positive polarity (e.g., after
transformation into negation normal form) then the conversion is
rather simple and the pseudo-normalization via NNF increases chances
only one side of the bi-implication is needed.
I implemented only optimizations that had a substantial
effect on formula size:
- formula simplification, extraction of multi argument operands
- if a formula is already in CNF then the Tseitin/Plaisted
transformation is omitted
- Plaisted via NNF
- omitted: (sharing of sub-formulas is also not implemented)
- omitted: (clause subsumption)
|
| |
|
|
| |
Signed-off-by: Gerard Basler <gerard.basler@gmail.com>
|
| |
|
|
| |
Remove redundant UniqueSym class.
|
| |
|
|
|
|
|
|
| |
to initial implementation).
Assuming that the DPLL procedure does not run into max recursion
depth, that workaround is not needed anymore, since the non-
determinism has been fixed.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Fixes non-determinism within the DPLL algorithm and disallows
infeasible counter examples directly in the formula.
The function to compute all solutions was flawed and thus only
returned a subset of the solutions. The algorithm would stop too soon
and thus depending on the ordering of the symbols return more or less
solutions. I also added printing a warning when the search was stopped
because the max recursion depth was reached. This is very useful as an
explanation of spuriously failing regression tests, since less counter
examples might be reported. In such a case the recursion depth should
be set to infinite by adding `-Ypatmat-exhaust-depth off`.
The mapping of the solutions of the DPLL algorithm to counter examples
has been adapted to take the additional solutions from the
solver into account:
Consider for example `t8430.scala`:
```Scala
sealed trait CL3Literal
case object IntLit extends CL3Literal
case object CharLit extends CL3Literal
case object BooleanLit extends CL3Literal
case object UnitLit extends CL3Literal
sealed trait Tree
case class LetL(value: CL3Literal) extends Tree
case object LetP extends Tree
case object LetC extends Tree
case object LetF extends Tree
object Test {
(tree: Tree) => tree match {case LetL(CharLit) => ??? }
}
```
This test contains 2 domains, `IntLit, CharLit, ...` and `LetL, LetP, ...`,
the corresponding formula to check exhaustivity looks like:
```
V1=LetC.type#13 \/ V1=LetF.type#14 \/ V1=LetL#11 \/ V1=LetP.type#15 /\
V2=BooleanLit.type#16 \/ V2=CharLit#12 \/ V2=IntLit.type#17 \/ V2=UnitLit.type#18 /\
-V1=LetL#11 \/ -V2=CharLit#12 \/ \/
```
The first two lines assign a value of the domain to the scrutinee (and
the correponding member in case of `LetL`) and prohibit the counter
example `LetL(CharLit)` since it's covered by the pattern match. The
used Boolean encoding allows that scrutinee `V1` can be equal to
`LetC` and `LetF` at the same time and thus, during enumeration of all
possible solutions of the formula, such a solution will be found,
since only one literal needs to be set to true, to satisfy that
clause. That means, if at least one of the literals of such a clause
was in the `unassigned` list of the DPLL procedure, we will get
solutions where the scrutinee is equal to more than one element of the
domain.
A remedy would be to add constraints that forbid both literals
to be true at the same time. His is infeasible for big domains (see
`pos/t8531.scala`), since we would have to add a quadratic number of
clauses (one clause for each pair in the domain). A much simpler
solution is to just filter the invalid results. Since both values for
`unassigned` literals are explored, we will eventually find a valid
counter example.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
In the enclosed test, t8611a.scala, the patterns `O.{A, B}` were
incorrect treated as equivelent by the combination of
`uniqueTpForTree` and `Const.uniqueTpForTree`.
`uniqueTpForTree` used `Type#narrow` to try to create a distinct
type for each new pattern tree it encountered. However, narrowing a
`RefinedType` does not create a distinct type as we are used to
when narrowing, e.g. a class type.
// Type
def narrow: Type =
if (phase.erasedTypes) this
else {
val cowner = commonOwner(this)
refinedType(this :: Nil, cowner, EmptyScope, cowner.pos).narrow
}
// CompoundType
override def narrow: Type = typeSymbol.thisType
This commit creates a fresh existential type symbol rather than
trying to use `narrow`.
I've included a unit test to show the sublteties of narrowing
refinment types.
|
| |\
| |
| | |
SI-8520 Fix -Dscalac.patmat.analysisBudget=off
|
| | |
| |
| |
| | |
Correctly parse "off" instead of throwing java.lang.NumberFormatException
|
| |/
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Another mole whacked on the head by using `LinkedHashMap`.
Caution: `LinkedHashMap` doesn't preserve its runtime type if
you map through the generic interface. I've noted this gotcha as
SI-8434. I've structured this patch to enforce that concrete
collection with types, which is a good idea anyway.
My method to track this down was to place breakpoints in
`Hash{Map,Set}`.{foreach,iterator}` to see where that was
used from within pattern match translation. This approach was
drastically faster than my previous rounds of whack-a-mole.
The counter-examples are still a bit off; I'm going to merge
that aspect of this ticket with SI-7746, in which we've
pinpointed the culpable part of the implementation, but haven't
had success in fixing the bug.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Not only does this save a big chunk of time on startup by avoiding
classloading and symbol table population, but it also seems to
improve steady state performance of the compiler.
Theory: JIT can optimize more aggressively without the
SynchronizedXxx decorators and the like being in the classloader.
See "Class Heirarchy Analyis" in [1]
This commit does this by:
- Avoiding use of FromString in pattern matcher, instead
using an established mechanism to parse system properties.
- Changes FromString back to use OptManifest. AFAICT, this
is now only a dependency of scala.tools.cmd.gen.Codegen,
so this is just a defensive measure.
The REPL still uses runtime reflection, so will pay a little
performance tax.
Benchmark:
avg shortest 10 times 744ms # before
avg shortest 10 times 675ms # after
[1] https://wikis.oracle.com/display/HotSpotInternals/PerformanceTechniques
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
The previous swing at determinism, ebb01e05cbe4, made decent
contact but apparently didn't hit it out of the park. The test
wavered every hundred or so runs, as witnessed occasionally in
nightly builds or pull request validation.
I setup a test to run neg/7020.scala a few hundred times, and
could trigger the failure reliably.
I then swept through the pattern matcher in search of HashMap and
HashSet creation, and changed them all to the Linked variety.
The results of that are published in retronym#ticket/7020-3 [1].
This commit represents the careful whittling down of that patch
to the minimal change required to exhibit determinism.
[1] https://github.com/retronym/scala/compare/ticket/7020-3
|
| |
|
|
|
|
|
|
|
|
|
| |
Moved ListOfNil somewhere more generally accessible. No
reason the compiler should hoard it for itself. Flitted
to a few locations with constructs like ".head.head" and
".tail.head" looking for code which could be rewritten. Found
some, admittedly not always making use of ListOfNil.
Made overdue moves of ConstantType(Constant(true|false|null))
to vals in Definitions.
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Confusing, now-it-happens now-it-doesn't mysteries lurk
in the darkness. When scala packages are declared like this:
package scala.collection.mutable
Then paths relative to scala can easily be broken via the unlucky
presence of an empty (or nonempty) directory. Example:
// a.scala
package scala.foo
class Bar { new util.Random }
% scalac ./a.scala
% mkdir util
% scalac ./a.scala
./a.scala:4: error: type Random is not a member of package util
new util.Random
^
one error found
There are two ways to play defense against this:
- don't use relative paths; okay sometimes, less so others
- don't "opt out" of the scala package
This commit mostly pursues the latter, with occasional doses
of the former.
I created a scratch directory containing these empty directories:
actors annotation ant api asm beans cmd collection compat
concurrent control convert docutil dtd duration event factory
forkjoin generic hashing immutable impl include internal io
logging macros man1 matching math meta model mutable nsc parallel
parsing partest persistent process pull ref reflect reify remote
runtime scalap scheduler script swing sys text threadpool tools
transform unchecked util xml
I stopped when I could compile the main src directories
even with all those empties on my classpath.
|
| |\
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Conflicts:
bincompat-forward.whitelist.conf
src/compiler/scala/tools/nsc/matching/Patterns.scala
src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
src/compiler/scala/tools/nsc/typechecker/Infer.scala
src/scaladoc/scala/tools/nsc/doc/model/ModelFactory.scala
test/files/neg/t5663-badwarneq.check
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
Unreachability analysis draws on the enumerated domain of types
(e.g sealed subclasses + null, or true/false), and also looks at all
stable identifier patterns tested for equality against the same 'slot'
in a pattern.
It was drawing the wrong conclusions about stable identifier patterns.
Unlike the domain constants, two such values may hold the same value,
so we can't assume that matching X precludes matching Y in the same
slot in a subsequent case.
For example:
val X: Boolean = true; val Y: Boolean = true
def m1(t1: Tuple1[Boolean]) = t1 match {
case Tuple1(true) =>
case Tuple1(false) =>
case Tuple1(false) => // correctly unreachable
}
def m2(t1: Tuple1[Boolean]) = t1 match {
case Tuple1(X) =>
case Tuple1(Y) => // spurious unreachable warning
}
//
// Before
//
reachability, vars:
V2: Boolean ::= true | false// Set(false, Y, X, true) // = x1._1
V1: (Boolean,) ::= null | ... // = x1
equality axioms:
V2=true#4 \/ V2=false#5 /\
-V2=false#5 \/ -V2=Y#3 /\
-V2=false#5 \/ -V2=X#2 /\
-V2=false#5 \/ -V2=true#4 /\
-V2=Y#3 \/ -V2=X#2 /\
-V2=Y#3 \/ -V2=true#4 /\
-V2=X#2 \/ -V2=true#4
//
// After
//
reachability, vars:
V2: Boolean ::= true | false// Set(false, Y, X, true) // = x1._1
V1: (Boolean,) ::= null | ... // = x1
equality axioms:
V2=true#4 \/ V2=false#5 /\
-V2=false#5 \/ -V2=true#4
|
| |\|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
topic/merge-2.10.x-to-v2.11.0-M2-74-g00e6c8b
Conflicts:
bincompat-backward.whitelist.conf
bincompat-forward.whitelist.conf
build.xml
src/compiler/scala/reflect/reify/utils/Extractors.scala
src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala
src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala
src/compiler/scala/tools/nsc/typechecker/Typers.scala
src/partest/scala/tools/partest/nest/ReflectiveRunner.scala
src/reflect/scala/reflect/internal/Types.scala
src/reflect/scala/reflect/runtime/JavaUniverse.scala
test/files/run/inline-ex-handlers.check
test/files/run/t6223.check
test/files/run/t6223.scala
test/scaladoc/scalacheck/IndexTest.scala
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
The fix for SI-6146 introduced `nestedMemberType` to
enumerate sealed subtypes based on the (prefixed) type
of the scrutinee and the symbols of its sealed subclasses.
That method needed to widen `ThisType(modSym)`s to
`ModuleTypeRef(modSym)` before calling `asSeenFrom`.
However, this could lead to confused in the match analysis,
which sees `ModuleTypeRef` as distinct from singleton types
on the same modules (after all, they aren't =:=). Spurious
warnings ensued.
This commit makes two changes:
- conditionally re-narrow the result of `asSeenFrom` in `nestedMemberType`.
- present `a.b.SomeModule.type` as `SomeModule` in warnings emitted
by the pattern matcher.
|
| |\ \
| | |
| | | |
Remove unrecognized doc comments
|
| | | |
| | |
| | |
| | |
| | | |
unmoored doc comment" warning when building distribution for
scala itself.
|
| |/ /
| |
| |
| |
| |
| | |
Mostly unused private code, unused imports, and points where
an extra pair of parentheses is necessary for scalac to have
confidence in our intentions.
|
| |\|
| |
| |
| |
| | |
Conflicts:
src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
|
| | | |
|
| | | | |
| | \ | |
| |\ \ \
| | |/
| |/|
| | | |
Fix check file for run/t7185.
|
| | |/ |
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
What would you prefer?
adaptToMemberWithArgs(tree, qual, name, mode, false, false)
Or:
adaptToMemberWithArgs(tree, qual, name, mode, reportAmbiguous = false, saveErrors = false)
|
| | | |
|
| |/
|
|
| |
With the exception of toString and the odd JavaBean getter.
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
| |
This brings the optimizations and the analyses closer together.
In the future we may consider using a solver in the optimizations.
For now, implication is checked ad-hoc using hash-consing and equality/subset tests...
NOTE: prepareNewAnalysis resets said hash-consing, so must be
called before approximating a match to propositions
|
| |
|
