luau/Analysis/include/Luau/ConstraintSolver.h

313 lines
13 KiB
C
Raw Permalink Normal View History

// This file is part of the Luau programming language and is licensed under MIT License; see LICENSE.txt for details
#pragma once
2022-06-17 02:05:14 +01:00
#include "Luau/Constraint.h"
Sync to upstream/release/603 (#1097) # What's changed? - Record the location of properties for table types (closes #802) - Implement stricter UTF-8 validations as per the RFC (https://github.com/luau-lang/rfcs/pull/1) - Implement `buffer` as a new type in both the old and new solvers. - Changed errors produced by some `buffer` builtins to be a bit more generic to avoid platform-dependent error messages. - Fixed a bug where `Unifier` would copy some persistent types, tripping some internal assertions. - Type checking rules on relational operators is now a little bit more lax. - Improve dead code elimination for some `if` statements with complex always-false conditions ## New type solver - Dataflow analysis now generates phi nodes on exit of branches. - Dataflow analysis avoids producing a new definition for locals or properties that are not owned by that loop. - If a function parameter has been constrained to `never`, report errors at all uses of that parameter within that function. - Switch to using the new `Luau::Set` to replace `std::unordered_set` to alleviate some poor allocation characteristics which was negatively affecting overall performance. - Subtyping can now report many failing reasons instead of just the first one that we happened to find during the test. - Subtyping now also report reasons for type pack mismatches. - When visiting `if` statements or expressions, the resulting context are the common terms in both branches. ## Native codegen - Implement support for `buffer` builtins to its IR for x64 and A64. - Optimized `table.insert` by not inserting a table barrier if it is fastcalled with a constant. ## Internal Contributors Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Arseny Kapoulkine <arseny@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-11-10 21:10:07 +00:00
#include "Luau/DenseHash.h"
#include "Luau/Error.h"
Sync to upstream/release/603 (#1097) # What's changed? - Record the location of properties for table types (closes #802) - Implement stricter UTF-8 validations as per the RFC (https://github.com/luau-lang/rfcs/pull/1) - Implement `buffer` as a new type in both the old and new solvers. - Changed errors produced by some `buffer` builtins to be a bit more generic to avoid platform-dependent error messages. - Fixed a bug where `Unifier` would copy some persistent types, tripping some internal assertions. - Type checking rules on relational operators is now a little bit more lax. - Improve dead code elimination for some `if` statements with complex always-false conditions ## New type solver - Dataflow analysis now generates phi nodes on exit of branches. - Dataflow analysis avoids producing a new definition for locals or properties that are not owned by that loop. - If a function parameter has been constrained to `never`, report errors at all uses of that parameter within that function. - Switch to using the new `Luau::Set` to replace `std::unordered_set` to alleviate some poor allocation characteristics which was negatively affecting overall performance. - Subtyping can now report many failing reasons instead of just the first one that we happened to find during the test. - Subtyping now also report reasons for type pack mismatches. - When visiting `if` statements or expressions, the resulting context are the common terms in both branches. ## Native codegen - Implement support for `buffer` builtins to its IR for x64 and A64. - Optimized `table.insert` by not inserting a table barrier if it is fastcalled with a constant. ## Internal Contributors Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Arseny Kapoulkine <arseny@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-11-10 21:10:07 +00:00
#include "Luau/Location.h"
#include "Luau/Module.h"
#include "Luau/Normalize.h"
#include "Luau/ToString.h"
#include "Luau/Type.h"
Sync to upstream/release/588 (#992) Type checker/autocomplete: * `Luau::autocomplete` no longer performs typechecking internally, make sure to run `Frontend::check` before performing autocomplete requests * Autocomplete string suggestions without "" are now only suggested inside the "" * Autocomplete suggestions now include `function (anonymous autofilled)` key with a full suggestion for the function expression (with arguments included) stored in `AutocompleteEntry::insertText` * `AutocompleteEntry::indexedWithSelf` is provided for function call suggestions made with `:` * Cyclic modules now see each other type exports as `any` to prevent memory use-after-free (similar to module return type) Runtime: * Updated inline/loop unroll cost model to better handle assignments (Fixes https://github.com/Roblox/luau/issues/978) * `math.noise` speed was improved by ~30% * `table.concat` speed was improved by ~5-7% * `tonumber` and `tostring` now have fastcall paths that execute ~1.5x and ~2.5x faster respectively (fixes #777) * Fixed crash in `luaL_typename` when index refers to a non-existing value * Fixed potential out of memory scenario when using `string.sub` or `string.char` in a loop * Fixed behavior of some fastcall builtins when called without arguments under -O2 to match original functions * Support for native code execution in VM is now enabled by default (note: native code still has to be generated explicitly) * `Codegen::compile` now accepts `CodeGen_OnlyNativeModules` flag. When set, only modules that have a `--!native` hot-comment at the top will be compiled to native code In our new typechecker: * Generic type packs are no longer considered to be variadic during unification * Timeout and cancellation now works in new solver * Fixed false positive errors around 'table' and 'function' type refinements * Table literals now use covariant unification rules. This is sound since literal has no type specified and has no aliases * Fixed issues with blocked types escaping the constraint solver * Fixed more places where error messages that should've been suppressed were still reported * Fixed errors when iterating over a top table type In our native code generation (jit): * 'DebugLuauAbortingChecks' flag is now supported on A64 * LOP_NEWCLOSURE has been translated to IR
2023-07-28 16:13:53 +01:00
#include "Luau/TypeCheckLimits.h"
Sync to upstream/release/603 (#1097) # What's changed? - Record the location of properties for table types (closes #802) - Implement stricter UTF-8 validations as per the RFC (https://github.com/luau-lang/rfcs/pull/1) - Implement `buffer` as a new type in both the old and new solvers. - Changed errors produced by some `buffer` builtins to be a bit more generic to avoid platform-dependent error messages. - Fixed a bug where `Unifier` would copy some persistent types, tripping some internal assertions. - Type checking rules on relational operators is now a little bit more lax. - Improve dead code elimination for some `if` statements with complex always-false conditions ## New type solver - Dataflow analysis now generates phi nodes on exit of branches. - Dataflow analysis avoids producing a new definition for locals or properties that are not owned by that loop. - If a function parameter has been constrained to `never`, report errors at all uses of that parameter within that function. - Switch to using the new `Luau::Set` to replace `std::unordered_set` to alleviate some poor allocation characteristics which was negatively affecting overall performance. - Subtyping can now report many failing reasons instead of just the first one that we happened to find during the test. - Subtyping now also report reasons for type pack mismatches. - When visiting `if` statements or expressions, the resulting context are the common terms in both branches. ## Native codegen - Implement support for `buffer` builtins to its IR for x64 and A64. - Optimized `table.insert` by not inserting a table barrier if it is fastcalled with a constant. ## Internal Contributors Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Arseny Kapoulkine <arseny@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-11-10 21:10:07 +00:00
#include "Luau/TypeFwd.h"
#include "Luau/Variant.h"
Sync to upstream/release/603 (#1097) # What's changed? - Record the location of properties for table types (closes #802) - Implement stricter UTF-8 validations as per the RFC (https://github.com/luau-lang/rfcs/pull/1) - Implement `buffer` as a new type in both the old and new solvers. - Changed errors produced by some `buffer` builtins to be a bit more generic to avoid platform-dependent error messages. - Fixed a bug where `Unifier` would copy some persistent types, tripping some internal assertions. - Type checking rules on relational operators is now a little bit more lax. - Improve dead code elimination for some `if` statements with complex always-false conditions ## New type solver - Dataflow analysis now generates phi nodes on exit of branches. - Dataflow analysis avoids producing a new definition for locals or properties that are not owned by that loop. - If a function parameter has been constrained to `never`, report errors at all uses of that parameter within that function. - Switch to using the new `Luau::Set` to replace `std::unordered_set` to alleviate some poor allocation characteristics which was negatively affecting overall performance. - Subtyping can now report many failing reasons instead of just the first one that we happened to find during the test. - Subtyping now also report reasons for type pack mismatches. - When visiting `if` statements or expressions, the resulting context are the common terms in both branches. ## Native codegen - Implement support for `buffer` builtins to its IR for x64 and A64. - Optimized `table.insert` by not inserting a table barrier if it is fastcalled with a constant. ## Internal Contributors Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Arseny Kapoulkine <arseny@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-11-10 21:10:07 +00:00
#include <utility>
#include <vector>
namespace Luau
{
struct DcrLogger;
// TypeId, TypePackId, or Constraint*. It is impossible to know which, but we
// never dereference this pointer.
using BlockedConstraintId = Variant<TypeId, TypePackId, const Constraint*>;
struct HashBlockedConstraintId
{
size_t operator()(const BlockedConstraintId& bci) const;
};
struct ModuleResolver;
2022-08-04 23:35:33 +01:00
struct InstantiationSignature
{
TypeFun fn;
std::vector<TypeId> arguments;
std::vector<TypePackId> packArguments;
bool operator==(const InstantiationSignature& rhs) const;
bool operator!=(const InstantiationSignature& rhs) const
{
return !((*this) == rhs);
}
};
struct HashInstantiationSignature
{
size_t operator()(const InstantiationSignature& signature) const;
};
struct ConstraintSolver
{
NotNull<TypeArena> arena;
NotNull<BuiltinTypes> builtinTypes;
InternalErrorReporter iceReporter;
NotNull<Normalizer> normalizer;
2022-08-04 23:35:33 +01:00
// The entire set of constraints that the solver is trying to resolve.
std::vector<NotNull<Constraint>> constraints;
2022-07-29 05:24:07 +01:00
NotNull<Scope> rootScope;
ModuleName currentModuleName;
2022-08-04 23:35:33 +01:00
// Constraints that the solver has generated, rather than sourcing from the
// scope tree.
std::vector<std::unique_ptr<Constraint>> solverConstraints;
// This includes every constraint that has not been fully solved.
// A constraint can be both blocked and unsolved, for instance.
2022-06-17 02:05:14 +01:00
std::vector<NotNull<const Constraint>> unsolvedConstraints;
// A mapping of constraint pointer to how many things the constraint is
// blocked on. Can be empty or 0 for constraints that are not blocked on
// anything.
2022-06-17 02:05:14 +01:00
std::unordered_map<NotNull<const Constraint>, size_t> blockedConstraints;
// A mapping of type/pack pointers to the constraints they block.
std::unordered_map<BlockedConstraintId, std::vector<NotNull<const Constraint>>, HashBlockedConstraintId> blocked;
2022-08-04 23:35:33 +01:00
// Memoized instantiations of type aliases.
DenseHashMap<InstantiationSignature, TypeId, HashInstantiationSignature> instantiatedAliases{{}};
Sync to upstream/release/603 (#1097) # What's changed? - Record the location of properties for table types (closes #802) - Implement stricter UTF-8 validations as per the RFC (https://github.com/luau-lang/rfcs/pull/1) - Implement `buffer` as a new type in both the old and new solvers. - Changed errors produced by some `buffer` builtins to be a bit more generic to avoid platform-dependent error messages. - Fixed a bug where `Unifier` would copy some persistent types, tripping some internal assertions. - Type checking rules on relational operators is now a little bit more lax. - Improve dead code elimination for some `if` statements with complex always-false conditions ## New type solver - Dataflow analysis now generates phi nodes on exit of branches. - Dataflow analysis avoids producing a new definition for locals or properties that are not owned by that loop. - If a function parameter has been constrained to `never`, report errors at all uses of that parameter within that function. - Switch to using the new `Luau::Set` to replace `std::unordered_set` to alleviate some poor allocation characteristics which was negatively affecting overall performance. - Subtyping can now report many failing reasons instead of just the first one that we happened to find during the test. - Subtyping now also report reasons for type pack mismatches. - When visiting `if` statements or expressions, the resulting context are the common terms in both branches. ## Native codegen - Implement support for `buffer` builtins to its IR for x64 and A64. - Optimized `table.insert` by not inserting a table barrier if it is fastcalled with a constant. ## Internal Contributors Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Arseny Kapoulkine <arseny@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-11-10 21:10:07 +00:00
// Breadcrumbs for where a free type's upper bound was expanded. We use
// these to provide more helpful error messages when a free type is solved
// as never unexpectedly.
DenseHashMap<TypeId, std::vector<std::pair<Location, TypeId>>> upperBoundContributors{nullptr};
2022-06-17 02:05:14 +01:00
Sync to upstream/release/601 (#1084) ## What's changed - `bit32.byteswap` added ([RFC](https://github.com/luau-lang/rfcs/blob/4f543ec23b6a1b53396e0803dd253c83041bae62/docs/function-bit32-byteswap.md)) - Buffer library implementation ([RFC](https://github.com/luau-lang/rfcs/blob/4f543ec23b6a1b53396e0803dd253c83041bae62/docs/type-byte-buffer.md)) - Fixed a missing `stdint.h` include - Fixed parser limiter for recursive type annotations being kind of weird (fixes #645) ### Native Codegen - Fixed a pair of issues when lowering `bit32.extract` - Fixed a narrow edge case that could result in an infinite loop without an interruption - Fixed a negative array out-of-bounds access issue - Temporarily reverted linear block predecessor value propagation ### New type solver - We now type check assignments to annotated variables - Fixed some test cases under local type inference - Moved `isPending` checks for type families to improve performance - Optimized our process for testing if a free type is sufficiently solved - Removed "none ptr" from lea instruction disassembly logging ### Build system & tooling - CMake configuration now validates dependencies to maintain separation between components - Improvements to the fuzzer coverage - Deduplicator for fuzzed callstacks --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Vighnesh Vijay <vvijay@roblox.com>
2023-10-27 22:18:41 +01:00
// A mapping from free types to the number of unresolved constraints that mention them.
DenseHashMap<TypeId, size_t> unresolvedConstraints{{}};
// Recorded errors that take place within the solver.
ErrorVec errors;
NotNull<ModuleResolver> moduleResolver;
std::vector<RequireCycle> requireCycles;
DcrLogger* logger;
Sync to upstream/release/588 (#992) Type checker/autocomplete: * `Luau::autocomplete` no longer performs typechecking internally, make sure to run `Frontend::check` before performing autocomplete requests * Autocomplete string suggestions without "" are now only suggested inside the "" * Autocomplete suggestions now include `function (anonymous autofilled)` key with a full suggestion for the function expression (with arguments included) stored in `AutocompleteEntry::insertText` * `AutocompleteEntry::indexedWithSelf` is provided for function call suggestions made with `:` * Cyclic modules now see each other type exports as `any` to prevent memory use-after-free (similar to module return type) Runtime: * Updated inline/loop unroll cost model to better handle assignments (Fixes https://github.com/Roblox/luau/issues/978) * `math.noise` speed was improved by ~30% * `table.concat` speed was improved by ~5-7% * `tonumber` and `tostring` now have fastcall paths that execute ~1.5x and ~2.5x faster respectively (fixes #777) * Fixed crash in `luaL_typename` when index refers to a non-existing value * Fixed potential out of memory scenario when using `string.sub` or `string.char` in a loop * Fixed behavior of some fastcall builtins when called without arguments under -O2 to match original functions * Support for native code execution in VM is now enabled by default (note: native code still has to be generated explicitly) * `Codegen::compile` now accepts `CodeGen_OnlyNativeModules` flag. When set, only modules that have a `--!native` hot-comment at the top will be compiled to native code In our new typechecker: * Generic type packs are no longer considered to be variadic during unification * Timeout and cancellation now works in new solver * Fixed false positive errors around 'table' and 'function' type refinements * Table literals now use covariant unification rules. This is sound since literal has no type specified and has no aliases * Fixed issues with blocked types escaping the constraint solver * Fixed more places where error messages that should've been suppressed were still reported * Fixed errors when iterating over a top table type In our native code generation (jit): * 'DebugLuauAbortingChecks' flag is now supported on A64 * LOP_NEWCLOSURE has been translated to IR
2023-07-28 16:13:53 +01:00
TypeCheckLimits limits;
explicit ConstraintSolver(NotNull<Normalizer> normalizer, NotNull<Scope> rootScope, std::vector<NotNull<Constraint>> constraints,
Sync to upstream/release/588 (#992) Type checker/autocomplete: * `Luau::autocomplete` no longer performs typechecking internally, make sure to run `Frontend::check` before performing autocomplete requests * Autocomplete string suggestions without "" are now only suggested inside the "" * Autocomplete suggestions now include `function (anonymous autofilled)` key with a full suggestion for the function expression (with arguments included) stored in `AutocompleteEntry::insertText` * `AutocompleteEntry::indexedWithSelf` is provided for function call suggestions made with `:` * Cyclic modules now see each other type exports as `any` to prevent memory use-after-free (similar to module return type) Runtime: * Updated inline/loop unroll cost model to better handle assignments (Fixes https://github.com/Roblox/luau/issues/978) * `math.noise` speed was improved by ~30% * `table.concat` speed was improved by ~5-7% * `tonumber` and `tostring` now have fastcall paths that execute ~1.5x and ~2.5x faster respectively (fixes #777) * Fixed crash in `luaL_typename` when index refers to a non-existing value * Fixed potential out of memory scenario when using `string.sub` or `string.char` in a loop * Fixed behavior of some fastcall builtins when called without arguments under -O2 to match original functions * Support for native code execution in VM is now enabled by default (note: native code still has to be generated explicitly) * `Codegen::compile` now accepts `CodeGen_OnlyNativeModules` flag. When set, only modules that have a `--!native` hot-comment at the top will be compiled to native code In our new typechecker: * Generic type packs are no longer considered to be variadic during unification * Timeout and cancellation now works in new solver * Fixed false positive errors around 'table' and 'function' type refinements * Table literals now use covariant unification rules. This is sound since literal has no type specified and has no aliases * Fixed issues with blocked types escaping the constraint solver * Fixed more places where error messages that should've been suppressed were still reported * Fixed errors when iterating over a top table type In our native code generation (jit): * 'DebugLuauAbortingChecks' flag is now supported on A64 * LOP_NEWCLOSURE has been translated to IR
2023-07-28 16:13:53 +01:00
ModuleName moduleName, NotNull<ModuleResolver> moduleResolver, std::vector<RequireCycle> requireCycles, DcrLogger* logger,
TypeCheckLimits limits);
// Randomize the order in which to dispatch constraints
void randomize(unsigned seed);
/**
* Attempts to dispatch all pending constraints and reach a type solution
2022-06-17 02:05:14 +01:00
* that satisfies all of the constraints.
**/
void run();
bool isDone();
void finalizeModule();
/** Attempt to dispatch a constraint. Returns true if it was successful. If
* tryDispatch() returns false, the constraint remains in the unsolved set
* and will be retried later.
2022-07-01 00:52:43 +01:00
*/
2022-06-17 02:05:14 +01:00
bool tryDispatch(NotNull<const Constraint> c, bool force);
2022-07-01 00:52:43 +01:00
2022-06-17 02:05:14 +01:00
bool tryDispatch(const SubtypeConstraint& c, NotNull<const Constraint> constraint, bool force);
bool tryDispatch(const PackSubtypeConstraint& c, NotNull<const Constraint> constraint, bool force);
bool tryDispatch(const GeneralizationConstraint& c, NotNull<const Constraint> constraint, bool force);
bool tryDispatch(const InstantiationConstraint& c, NotNull<const Constraint> constraint, bool force);
bool tryDispatch(const IterableConstraint& c, NotNull<const Constraint> constraint, bool force);
2022-06-24 02:56:00 +01:00
bool tryDispatch(const NameConstraint& c, NotNull<const Constraint> constraint);
2022-08-04 23:35:33 +01:00
bool tryDispatch(const TypeAliasExpansionConstraint& c, NotNull<const Constraint> constraint);
bool tryDispatch(const FunctionCallConstraint& c, NotNull<const Constraint> constraint);
2022-09-23 20:17:25 +01:00
bool tryDispatch(const PrimitiveTypeConstraint& c, NotNull<const Constraint> constraint);
bool tryDispatch(const HasPropConstraint& c, NotNull<const Constraint> constraint);
bool tryDispatch(const SetPropConstraint& c, NotNull<const Constraint> constraint, bool force);
bool tryDispatch(const SetIndexerConstraint& c, NotNull<const Constraint> constraint, bool force);
bool tryDispatch(const SingletonOrTopTypeConstraint& c, NotNull<const Constraint> constraint);
bool tryDispatch(const UnpackConstraint& c, NotNull<const Constraint> constraint);
Sync to upstream/release/577 (#934) Lots of things going on this week: * Fix a crash that could occur in the presence of a cyclic union. We shouldn't be creating cyclic unions, but we shouldn't be crashing when they arise either. * Minor cleanup of `luau_precall` * Internal change to make L->top handling slightly more uniform * Optimize SETGLOBAL & GETGLOBAL fallback C functions. * https://github.com/Roblox/luau/pull/929 * The syntax to the `luau-reduce` commandline tool has changed. It now accepts a script, a command to execute, and an error to search for. It no longer automatically passes the script to the command which makes it a lot more flexible. Also be warned that it edits the script it is passed **in place**. Do not point it at something that is not in source control! New solver * Switch to a greedier but more fallible algorithm for simplifying union and intersection types that are created as part of refinement calculation. This has much better and more predictable performance. * Fix a constraint cycle in recursive function calls. * Much improved inference of binary addition. Functions like `function add(x, y) return x + y end` can now be inferred without annotations. We also accurately typecheck calls to functions like this. * Many small bugfixes surrounding things like table indexers * Add support for indexers on class types. This was previously added to the old solver; we now add it to the new one for feature parity. JIT * https://github.com/Roblox/luau/pull/931 * Fuse key.value and key.tt loads for CEHCK_SLOT_MATCH in A64 * Implement remaining aliases of BFM for A64 * Implement new callinfo flag for A64 * Add instruction simplification for int->num->int conversion chains * Don't even load execdata for X64 calls * Treat opcode fallbacks the same as manually written fallbacks --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-05-19 20:37:30 +01:00
bool tryDispatch(const RefineConstraint& c, NotNull<const Constraint> constraint, bool force);
Sync to upstream/release/600 (#1076) ### What's Changed - Improve readability of unions and intersections by limiting the number of elements of those types that can be presented on a single line (gated under `FFlag::LuauToStringSimpleCompositeTypesSingleLine`) - Adds a new option to the compiler `--record-stats` to record and output compilation statistics - `if...then...else` expressions are now optimized into `AND/OR` form when possible. ### VM - Add a new `buffer` type to Luau based on the [buffer RFC](https://github.com/Roblox/luau/pull/739) and additional C API functions to work with it; this release does not include the library. - Internal C API to work with string buffers has been updated to align with Lua version more closely ### Native Codegen - Added support for new X64 instruction (rev) and new A64 instruction (bswap) in the assembler - Simplified the way numerical loop condition is translated to IR ### New Type Solver - Operator inference now handled by type families - Created a new system called `Type Paths` to explain why subtyping tests fail in order to improve the quality of error messages. - Systematic changes to implement Data Flow analysis in the new solver (`Breadcrumb` removed and replaced with `RefinementKey`) --- Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Vighnesh Vijay <vvijay@roblox.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com> --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com>
2023-10-21 02:10:30 +01:00
bool tryDispatch(const SetOpConstraint& c, NotNull<const Constraint> constraint, bool force);
Sync to upstream/release/576 (#928) * `ClassType` can now have an indexer defined on it. This allows custom types to be used in `t[x]` expressions. * Fixed search for closest executable breakpoint line. Previously, breakpoints might have been skipped in `else` blocks at the end of a function * Fixed how unification is performed for two optional types `a? <: b?`, previously it might have unified either 'a' or 'b' with 'nil'. Note that this fix is not enabled by default yet (see the list in `ExperimentalFlags.h`) In the new type solver, a concept of 'Type Families' has been introduced. Type families can be thought of as type aliases with custom type inference/reduction logic included with them. For example, we can have an `Add<T, U>` type family that will resolve the type that is the result of adding two values together. This will help type inference to figure out what 'T' and 'U' might be when explicit type annotations are not provided. In this update we don't define any type families, but they will be added in the near future. It is also possible for Luau embedders to define their own type families in the global/environment scope. Other changes include: * Fixed scope used to find out which generic types should be included in the function generic type list * Fixed a crash after cyclic bound types were created during unification And in native code generation (jit): * Use of arm64 target on M1 now requires macOS 13 * Entry into native code has been optimized. This is especially important for coroutine call/pcall performance as they involve going through a C call frame * LOP_LOADK(X) translation into IR has been improved to enable type tag/constant propagation * arm64 can use integer immediate values to synthesize floating-point values * x64 assembler removes duplicate 64bit numbers from the data section to save space * Linux `perf` can now be used to profile native Luau code (when running with --codegen-perf CLI argument)
2023-05-12 18:50:47 +01:00
bool tryDispatch(const ReduceConstraint& c, NotNull<const Constraint> constraint, bool force);
bool tryDispatch(const ReducePackConstraint& c, NotNull<const Constraint> constraint, bool force);
// for a, ... in some_table do
// also handles __iter metamethod
bool tryDispatchIterableTable(TypeId iteratorTy, const IterableConstraint& c, NotNull<const Constraint> constraint, bool force);
// for a, ... in next_function, t, ... do
bool tryDispatchIterableFunction(
TypeId nextTy, TypeId tableTy, TypeId firstIndexTy, const IterableConstraint& c, NotNull<const Constraint> constraint, bool force);
Sync to upstream/release/577 (#934) Lots of things going on this week: * Fix a crash that could occur in the presence of a cyclic union. We shouldn't be creating cyclic unions, but we shouldn't be crashing when they arise either. * Minor cleanup of `luau_precall` * Internal change to make L->top handling slightly more uniform * Optimize SETGLOBAL & GETGLOBAL fallback C functions. * https://github.com/Roblox/luau/pull/929 * The syntax to the `luau-reduce` commandline tool has changed. It now accepts a script, a command to execute, and an error to search for. It no longer automatically passes the script to the command which makes it a lot more flexible. Also be warned that it edits the script it is passed **in place**. Do not point it at something that is not in source control! New solver * Switch to a greedier but more fallible algorithm for simplifying union and intersection types that are created as part of refinement calculation. This has much better and more predictable performance. * Fix a constraint cycle in recursive function calls. * Much improved inference of binary addition. Functions like `function add(x, y) return x + y end` can now be inferred without annotations. We also accurately typecheck calls to functions like this. * Many small bugfixes surrounding things like table indexers * Add support for indexers on class types. This was previously added to the old solver; we now add it to the new one for feature parity. JIT * https://github.com/Roblox/luau/pull/931 * Fuse key.value and key.tt loads for CEHCK_SLOT_MATCH in A64 * Implement remaining aliases of BFM for A64 * Implement new callinfo flag for A64 * Add instruction simplification for int->num->int conversion chains * Don't even load execdata for X64 calls * Treat opcode fallbacks the same as manually written fallbacks --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-05-19 20:37:30 +01:00
std::pair<std::vector<TypeId>, std::optional<TypeId>> lookupTableProp(
TypeId subjectType, const std::string& propName, bool suppressSimplification = false);
std::pair<std::vector<TypeId>, std::optional<TypeId>> lookupTableProp(
Sync to upstream/release/603 (#1097) # What's changed? - Record the location of properties for table types (closes #802) - Implement stricter UTF-8 validations as per the RFC (https://github.com/luau-lang/rfcs/pull/1) - Implement `buffer` as a new type in both the old and new solvers. - Changed errors produced by some `buffer` builtins to be a bit more generic to avoid platform-dependent error messages. - Fixed a bug where `Unifier` would copy some persistent types, tripping some internal assertions. - Type checking rules on relational operators is now a little bit more lax. - Improve dead code elimination for some `if` statements with complex always-false conditions ## New type solver - Dataflow analysis now generates phi nodes on exit of branches. - Dataflow analysis avoids producing a new definition for locals or properties that are not owned by that loop. - If a function parameter has been constrained to `never`, report errors at all uses of that parameter within that function. - Switch to using the new `Luau::Set` to replace `std::unordered_set` to alleviate some poor allocation characteristics which was negatively affecting overall performance. - Subtyping can now report many failing reasons instead of just the first one that we happened to find during the test. - Subtyping now also report reasons for type pack mismatches. - When visiting `if` statements or expressions, the resulting context are the common terms in both branches. ## Native codegen - Implement support for `buffer` builtins to its IR for x64 and A64. - Optimized `table.insert` by not inserting a table barrier if it is fastcalled with a constant. ## Internal Contributors Co-authored-by: Aaron Weiss <aaronweiss@roblox.com> Co-authored-by: Alexander McCord <amccord@roblox.com> Co-authored-by: Andy Friesen <afriesen@roblox.com> Co-authored-by: Arseny Kapoulkine <arseny@roblox.com> Co-authored-by: Aviral Goel <agoel@roblox.com> Co-authored-by: Lily Brown <lbrown@roblox.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-11-10 21:10:07 +00:00
TypeId subjectType, const std::string& propName, bool suppressSimplification, DenseHashSet<TypeId>& seen);
2022-06-17 02:05:14 +01:00
void block(NotNull<const Constraint> target, NotNull<const Constraint> constraint);
/**
* Block a constraint on the resolution of a Type.
2022-06-17 02:05:14 +01:00
* @returns false always. This is just to allow tryDispatch to return the result of block()
*/
bool block(TypeId target, NotNull<const Constraint> constraint);
bool block(TypePackId target, NotNull<const Constraint> constraint);
Sync to upstream/release/577 (#934) Lots of things going on this week: * Fix a crash that could occur in the presence of a cyclic union. We shouldn't be creating cyclic unions, but we shouldn't be crashing when they arise either. * Minor cleanup of `luau_precall` * Internal change to make L->top handling slightly more uniform * Optimize SETGLOBAL & GETGLOBAL fallback C functions. * https://github.com/Roblox/luau/pull/929 * The syntax to the `luau-reduce` commandline tool has changed. It now accepts a script, a command to execute, and an error to search for. It no longer automatically passes the script to the command which makes it a lot more flexible. Also be warned that it edits the script it is passed **in place**. Do not point it at something that is not in source control! New solver * Switch to a greedier but more fallible algorithm for simplifying union and intersection types that are created as part of refinement calculation. This has much better and more predictable performance. * Fix a constraint cycle in recursive function calls. * Much improved inference of binary addition. Functions like `function add(x, y) return x + y end` can now be inferred without annotations. We also accurately typecheck calls to functions like this. * Many small bugfixes surrounding things like table indexers * Add support for indexers on class types. This was previously added to the old solver; we now add it to the new one for feature parity. JIT * https://github.com/Roblox/luau/pull/931 * Fuse key.value and key.tt loads for CEHCK_SLOT_MATCH in A64 * Implement remaining aliases of BFM for A64 * Implement new callinfo flag for A64 * Add instruction simplification for int->num->int conversion chains * Don't even load execdata for X64 calls * Treat opcode fallbacks the same as manually written fallbacks --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-05-19 20:37:30 +01:00
// Block on every target
template<typename T>
bool block(const T& targets, NotNull<const Constraint> constraint)
{
for (TypeId target : targets)
block(target, constraint);
return false;
}
Sync to upstream/release/568 (#865) * A small subset of control-flow refinements have been added to recognize type options that are unreachable after a conditional/unconditional code block. (Fixes https://github.com/Roblox/luau/issues/356). Some examples: ```lua local function f(x: string?) if not x then return end -- x is 'string' here end ``` Throwing calls like `error` or `assert(false)` instead of 'return' are also recognized. Existing complex refinements like type/typeof and tagged union checks are expected to work, among others. To enable this feature, `LuauTinyControlFlowAnalysis` exclusion has to be removed from `ExperimentalFlags.h`. If will become enabled unconditionally in the near future. * Linter has been integrated into the typechecker analysis so that type-aware lint warnings can work in any mode `Frontend::lint` methods were deprecated, `Frontend::check` has to be used instead with `runLintChecks` option set. Resulting lint warning are located inside `CheckResult`. * Fixed large performance drop and increased memory consumption when array is filled at an offset (Fixes https://github.com/Roblox/luau/issues/590) * Part of [Type error suppression RFC](https://github.com/Roblox/luau/blob/master/rfcs/type-error-suppression.md) was implemented making subtyping checks with `any` type transitive. --- In our work on the new type-solver: * `--!nocheck` mode no longer reports type errors * New solver will not be used for `--!nonstrict` modules until all issues with strict mode typechecking are fixed * Added control-flow aware type refinements mentioned earlier In native code generation: * `LOP_NAMECALL` has been translated to IR * `type` and `typeof` builtin fastcalls have been translated to IR/assembly * Additional steps were taken towards arm64 support
2023-03-17 19:20:37 +00:00
/**
* For all constraints that are blocked on one constraint, make them block
* on a new constraint.
* @param source the constraint to copy blocks from.
* @param addition the constraint that other constraints should now block on.
*/
void inheritBlocks(NotNull<const Constraint> source, NotNull<const Constraint> addition);
Sync to upstream/release/577 (#934) Lots of things going on this week: * Fix a crash that could occur in the presence of a cyclic union. We shouldn't be creating cyclic unions, but we shouldn't be crashing when they arise either. * Minor cleanup of `luau_precall` * Internal change to make L->top handling slightly more uniform * Optimize SETGLOBAL & GETGLOBAL fallback C functions. * https://github.com/Roblox/luau/pull/929 * The syntax to the `luau-reduce` commandline tool has changed. It now accepts a script, a command to execute, and an error to search for. It no longer automatically passes the script to the command which makes it a lot more flexible. Also be warned that it edits the script it is passed **in place**. Do not point it at something that is not in source control! New solver * Switch to a greedier but more fallible algorithm for simplifying union and intersection types that are created as part of refinement calculation. This has much better and more predictable performance. * Fix a constraint cycle in recursive function calls. * Much improved inference of binary addition. Functions like `function add(x, y) return x + y end` can now be inferred without annotations. We also accurately typecheck calls to functions like this. * Many small bugfixes surrounding things like table indexers * Add support for indexers on class types. This was previously added to the old solver; we now add it to the new one for feature parity. JIT * https://github.com/Roblox/luau/pull/931 * Fuse key.value and key.tt loads for CEHCK_SLOT_MATCH in A64 * Implement remaining aliases of BFM for A64 * Implement new callinfo flag for A64 * Add instruction simplification for int->num->int conversion chains * Don't even load execdata for X64 calls * Treat opcode fallbacks the same as manually written fallbacks --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-05-19 20:37:30 +01:00
// Traverse the type. If any pending types are found, block the constraint
// on them.
2022-09-23 20:17:25 +01:00
//
// Returns false if a type blocks the constraint.
//
// FIXME: This use of a boolean for the return result is an appalling
// interface.
Sync to upstream/release/577 (#934) Lots of things going on this week: * Fix a crash that could occur in the presence of a cyclic union. We shouldn't be creating cyclic unions, but we shouldn't be crashing when they arise either. * Minor cleanup of `luau_precall` * Internal change to make L->top handling slightly more uniform * Optimize SETGLOBAL & GETGLOBAL fallback C functions. * https://github.com/Roblox/luau/pull/929 * The syntax to the `luau-reduce` commandline tool has changed. It now accepts a script, a command to execute, and an error to search for. It no longer automatically passes the script to the command which makes it a lot more flexible. Also be warned that it edits the script it is passed **in place**. Do not point it at something that is not in source control! New solver * Switch to a greedier but more fallible algorithm for simplifying union and intersection types that are created as part of refinement calculation. This has much better and more predictable performance. * Fix a constraint cycle in recursive function calls. * Much improved inference of binary addition. Functions like `function add(x, y) return x + y end` can now be inferred without annotations. We also accurately typecheck calls to functions like this. * Many small bugfixes surrounding things like table indexers * Add support for indexers on class types. This was previously added to the old solver; we now add it to the new one for feature parity. JIT * https://github.com/Roblox/luau/pull/931 * Fuse key.value and key.tt loads for CEHCK_SLOT_MATCH in A64 * Implement remaining aliases of BFM for A64 * Implement new callinfo flag for A64 * Add instruction simplification for int->num->int conversion chains * Don't even load execdata for X64 calls * Treat opcode fallbacks the same as manually written fallbacks --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-05-19 20:37:30 +01:00
bool blockOnPendingTypes(TypeId target, NotNull<const Constraint> constraint);
bool blockOnPendingTypes(TypePackId target, NotNull<const Constraint> constraint);
2022-09-23 20:17:25 +01:00
2022-06-17 02:05:14 +01:00
void unblock(NotNull<const Constraint> progressed);
void unblock(TypeId progressed, Location location);
void unblock(TypePackId progressed, Location location);
void unblock(const std::vector<TypeId>& types, Location location);
void unblock(const std::vector<TypePackId>& packs, Location location);
2022-06-17 02:05:14 +01:00
/**
* @returns true if the TypeId is in a blocked state.
*/
bool isBlocked(TypeId ty);
/**
* @returns true if the TypePackId is in a blocked state.
*/
bool isBlocked(TypePackId tp);
/**
* Returns whether the constraint is blocked on anything.
* @param constraint the constraint to check.
*/
2022-06-17 02:05:14 +01:00
bool isBlocked(NotNull<const Constraint> constraint);
/**
* Creates a new Unifier and performs a single unification operation. Commits
2022-06-17 02:05:14 +01:00
* the result.
* @param subType the sub-type to unify.
* @param superType the super-type to unify.
* @returns optionally a unification too complex error if unification failed
*/
std::optional<TypeError> unify(NotNull<Scope> scope, Location location, TypeId subType, TypeId superType);
/**
* Creates a new Unifier and performs a single unification operation. Commits
2022-06-17 02:05:14 +01:00
* the result.
* @param subPack the sub-type pack to unify.
* @param superPack the super-type pack to unify.
*/
ErrorVec unify(NotNull<Scope> scope, Location location, TypePackId subPack, TypePackId superPack);
2022-06-17 02:05:14 +01:00
2022-08-04 23:35:33 +01:00
/** Pushes a new solver constraint to the solver.
* @param cv the body of the constraint.
**/
NotNull<Constraint> pushConstraint(NotNull<Scope> scope, const Location& location, ConstraintV cv);
/**
* Attempts to resolve a module from its module information. Returns the
* module-level return type of the module, or the error type if one cannot
* be found. Reports errors to the solver if the module cannot be found or
* the require is illegal.
* @param module the module information to look up.
* @param location the location where the require is taking place; used for
* error locations.
**/
TypeId resolveModule(const ModuleInfo& module, const Location& location);
2022-08-04 23:35:33 +01:00
void reportError(TypeErrorData&& data, const Location& location);
void reportError(TypeError e);
/**
* Checks the existing set of constraints to see if there exist any that contain
* the provided free type, indicating that it is not yet ready to be replaced by
* one of its bounds.
* @param ty the free type that to check for related constraints
* @returns whether or not it is unsafe to replace the free type by one of its bounds
*/
bool hasUnresolvedConstraints(TypeId ty);
2022-06-17 02:05:14 +01:00
private:
/** Helper used by tryDispatch(SubtypeConstraint) and
* tryDispatch(PackSubtypeConstraint)
*
* Attempts to unify subTy with superTy. If doing so would require unifying
* BlockedTypes, fail and block the constraint on those BlockedTypes.
*
* If unification fails, replace all free types with errorType.
*
* If unification succeeds, unblock every type changed by the unification.
*/
template <typename TID>
bool tryUnify(NotNull<const Constraint> constraint, TID subTy, TID superTy);
/**
* Bind a BlockedType to another type while taking care not to bind it to
* itself in the case that resultTy == blockedTy. This can happen if we
* have a tautological constraint. When it does, we must instead bind
* blockedTy to a fresh type belonging to an appropriate scope.
*
* To determine which scope is appropriate, we also accept rootTy, which is
* to be the type that contains blockedTy.
*/
void bindBlockedType(TypeId blockedTy, TypeId resultTy, TypeId rootTy, Location location);
2022-06-17 02:05:14 +01:00
/**
* Marks a constraint as being blocked on a type or type pack. The constraint
* solver will not attempt to dispatch blocked constraints until their
* dependencies have made progress.
* @param target the type or type pack pointer that the constraint is blocked on.
* @param constraint the constraint to block.
**/
void block_(BlockedConstraintId target, NotNull<const Constraint> constraint);
/**
* Informs the solver that progress has been made on a type or type pack. The
* solver will wake up all constraints that are blocked on the type or type pack,
* and will resume attempting to dispatch them.
* @param progressed the type or type pack pointer that has progressed.
**/
void unblock_(BlockedConstraintId progressed);
TypeId errorRecoveryType() const;
TypePackId errorRecoveryTypePack() const;
Sync to upstream/release/577 (#934) Lots of things going on this week: * Fix a crash that could occur in the presence of a cyclic union. We shouldn't be creating cyclic unions, but we shouldn't be crashing when they arise either. * Minor cleanup of `luau_precall` * Internal change to make L->top handling slightly more uniform * Optimize SETGLOBAL & GETGLOBAL fallback C functions. * https://github.com/Roblox/luau/pull/929 * The syntax to the `luau-reduce` commandline tool has changed. It now accepts a script, a command to execute, and an error to search for. It no longer automatically passes the script to the command which makes it a lot more flexible. Also be warned that it edits the script it is passed **in place**. Do not point it at something that is not in source control! New solver * Switch to a greedier but more fallible algorithm for simplifying union and intersection types that are created as part of refinement calculation. This has much better and more predictable performance. * Fix a constraint cycle in recursive function calls. * Much improved inference of binary addition. Functions like `function add(x, y) return x + y end` can now be inferred without annotations. We also accurately typecheck calls to functions like this. * Many small bugfixes surrounding things like table indexers * Add support for indexers on class types. This was previously added to the old solver; we now add it to the new one for feature parity. JIT * https://github.com/Roblox/luau/pull/931 * Fuse key.value and key.tt loads for CEHCK_SLOT_MATCH in A64 * Implement remaining aliases of BFM for A64 * Implement new callinfo flag for A64 * Add instruction simplification for int->num->int conversion chains * Don't even load execdata for X64 calls * Treat opcode fallbacks the same as manually written fallbacks --------- Co-authored-by: Arseny Kapoulkine <arseny.kapoulkine@gmail.com> Co-authored-by: Vyacheslav Egorov <vegorov@roblox.com>
2023-05-19 20:37:30 +01:00
TypePackId anyifyModuleReturnTypePackGenerics(TypePackId tp);
Sync to upstream/release/588 (#992) Type checker/autocomplete: * `Luau::autocomplete` no longer performs typechecking internally, make sure to run `Frontend::check` before performing autocomplete requests * Autocomplete string suggestions without "" are now only suggested inside the "" * Autocomplete suggestions now include `function (anonymous autofilled)` key with a full suggestion for the function expression (with arguments included) stored in `AutocompleteEntry::insertText` * `AutocompleteEntry::indexedWithSelf` is provided for function call suggestions made with `:` * Cyclic modules now see each other type exports as `any` to prevent memory use-after-free (similar to module return type) Runtime: * Updated inline/loop unroll cost model to better handle assignments (Fixes https://github.com/Roblox/luau/issues/978) * `math.noise` speed was improved by ~30% * `table.concat` speed was improved by ~5-7% * `tonumber` and `tostring` now have fastcall paths that execute ~1.5x and ~2.5x faster respectively (fixes #777) * Fixed crash in `luaL_typename` when index refers to a non-existing value * Fixed potential out of memory scenario when using `string.sub` or `string.char` in a loop * Fixed behavior of some fastcall builtins when called without arguments under -O2 to match original functions * Support for native code execution in VM is now enabled by default (note: native code still has to be generated explicitly) * `Codegen::compile` now accepts `CodeGen_OnlyNativeModules` flag. When set, only modules that have a `--!native` hot-comment at the top will be compiled to native code In our new typechecker: * Generic type packs are no longer considered to be variadic during unification * Timeout and cancellation now works in new solver * Fixed false positive errors around 'table' and 'function' type refinements * Table literals now use covariant unification rules. This is sound since literal has no type specified and has no aliases * Fixed issues with blocked types escaping the constraint solver * Fixed more places where error messages that should've been suppressed were still reported * Fixed errors when iterating over a top table type In our native code generation (jit): * 'DebugLuauAbortingChecks' flag is now supported on A64 * LOP_NEWCLOSURE has been translated to IR
2023-07-28 16:13:53 +01:00
void throwTimeLimitError();
void throwUserCancelError();
ToStringOptions opts;
};
2022-07-29 05:24:07 +01:00
void dump(NotNull<Scope> rootScope, struct ToStringOptions& opts);
} // namespace Luau