Repository: geldata/gel
Pull request: Fix several issues related to schema loading in declarative
The main change is a new schema where if we can't figure out the type
of an expression in a path, create weak dependencies to all pointers
with the same name.

This doesn't always work but in practice it will do very well.

I have some ideas for how we could incorporate correct typechecking
into schema loading, but in the mean time this probably solves 90% of
the problem at least.

In this PR there is also a commit that adds a system for categorizing
objects so that things without expressions will go first, and things
with expressions will be prioritized based on whether they can be
referred to.
I wound up reverting it because it isn't needed to fix the issues that
weak pointers fix, and other than those, I think it mostly would work
around bugs that could be fixed in straightforward ways.

Fixes #4683. Fixes #5163.

Problem statement:
Migrations fail when abstract properties are referenced in globals
<!-- Please search existing issues to avoid creating duplicates. -->
- EdgeDB Version: 2.6
- OS Version: macOS 13.0

Steps to Reproduce:

1. Create the schema below
2. Run `edgedb migration create`

Expected behavior: Migration should run successfully.
Actual behavior: This produces the error `error: object type 'default::Role' has no link or property 'slug'`

<!-- If the issue is about a query error, please also provide your schema -->
Schema:

```
module default {
  global current_user_id -> uuid;
  global current_user := (
    select User filter .id = global current_user_id
  );
  global current_user_role := (
    (global current_user).role.slug
  );

  abstract type WithSlug {
    property slug -> str
  }

  type Role extending WithSlug {
    property description -> str
  }

  type User {
    required link role -> Role;
  }
}
```

assert_exists makes the compiler claim "object type ... has no link or property ..."
<!-- Please search existing issues to avoid creating duplicates. -->

<!--
For the EdgeDB Version: run `edgedb query 'select sys::get_version_as_str()'` from your project directory (or run `select sys::get_version_as_str();` in the EdgeDB interactive shell).
For the EdgeDB CLI Version: Run `edgedb --version` from anywhere
-->

- EdgeDB Version: "2.12+815c3e2"
- EdgeDB CLI Version: EdgeDB CLI 2.3.1+5d93f42
- OS Version: MacOS 13.0

Steps to Reproduce:
`edgedb migration create`

```
error: object type 'default::DataEntry' has no link or property 'branch'
  ┌─ dbschema/common.esdl:7:45
  │
7 │         link branch := .datapoint.data_entry.branch;
  │                                             ^^^^^^^ error

edgedb error: cannot proceed until .esdl files are fixed
```

<!-- If the issue is about a query error, please also provide your schema -->

Schema:

```
module default {
    type Branch{
    }
    type CO2DataPoint{
        required link datapoint -> DataPoint;
        link branch := .datapoint.data_entry.branch; # THIS LINE
    }
    type DataPoint{
        required link data_entry := assert_exists(.<data_points[is DataEntry]); # THIS GIVES ERROR BUT ONLY IF THE LINE ABOVE IS UNCOMMENTED
        # link data_entry := .<data_points[is DataEntry]; # THIS WORKS
    }

    type DataEntry{
        required link branch -> Branch;
        multi link data_points -> DataPoint;
    }
}
```

Hints from issue discussion:
This is probably an instance of the more general problem that we are trying to sort the items in the schema before we can properly typecheck expressions in them.
Possibly `current_user` just isn't getting checked properly and can be fixed.
I've got two ideas. The first doesn't technically always work but would probably work very well in practice:
1. Always sort everything with an expression in it after everything without an expression. And always sort things with expressions that can't be referenced (indexes, rewrites, defaults, triggers, policies) after things that can be. Then maybe add weak dependencies based on pointer names.
2. Interleave the declarative ordering with the construction of the schema; use the schema in declarative as a source of truth alongside inferred state. Like above, process everything without expressions first. When trying to sort things with expressions, defer expressions that the simplified inference system can't fully understand and retry them after having built more of the schema.
Probably this is a result of bad sorting in `declarative`

Commit message: Generate weak deps in declarative when we don't know the type

If we can't figure out the type of an expression in a path,
create weak dependencies to all pointers with the same name.

This doesn't *always* work but in practice it will do pretty well.

Fixes #4683. Fixes #5163.

Patch to review:
diff --git a/edb/edgeql/declarative.py b/edb/edgeql/declarative.py
index cd73367503e..a98579747e0 100644
--- a/edb/edgeql/declarative.py
+++ b/edb/edgeql/declarative.py
@@ -70,6 +70,7 @@ class TraceContextBase:
     depstack: List[Tuple[qlast.DDLOperation, s_name.QualName]]
     modaliases: Dict[Optional[str], str]
     objects: Dict[s_name.QualName, Optional[qltracer.ObjectLike]]
+    pointers: Dict[s_name.UnqualName, Set[s_name.QualName]]
     parents: Dict[s_name.QualName, Set[s_name.QualName]]
     ancestors: Dict[s_name.QualName, Set[s_name.QualName]]
     defdeps: Dict[s_name.QualName, Set[s_name.QualName]]
@@ -86,6 +87,7 @@ def __init__(
         self.depstack = []
         self.modaliases = {}
         self.objects = {}
+        self.pointers = {}
         self.parents = {}
         self.ancestors = {}
         self.defdeps = defaultdict(set)
@@ -318,6 +320,7 @@ def __init__(
         schema: s_schema.Schema,
         ddlgraph: DDLGraph,
         objects: Dict[s_name.QualName, Optional[qltracer.ObjectLike]],
+        pointers: Dict[s_name.UnqualName, Set[s_name.QualName]],
         parents: Dict[s_name.QualName, Set[s_name.QualName]],
         ancestors: Dict[s_name.QualName, Set[s_name.QualName]],
         defdeps: Dict[s_name.QualName, Set[s_name.QualName]],
@@ -327,6 +330,7 @@ def __init__(
         super().__init__(schema, local_modules)
         self.ddlgraph = ddlgraph
         self.objects = objects
+        self.pointers = pointers
         self.parents = parents
         self.ancestors = ancestors
         self.defdeps = defdeps
@@ -430,7 +434,7 @@ def sdl_to_ddl(
     )
 
     tracectx = DepTraceContext(
-        schema, ddlgraph, ctx.objects, ctx.parents, ctx.ancestors,
+        schema, ddlgraph, ctx.objects, ctx.pointers, ctx.parents, ctx.ancestors,
         ctx.defdeps, ctx.constraints, ctx.local_modules,
     )
 
@@ -680,6 +684,7 @@ def _trace_item_layout(
             )
             ctx.objects[ptr_name] = ptr
             ctx.defdeps[fq_name].add(ptr_name)
+            ctx.pointers.setdefault(pn, set()).add(ptr_name)
 
             _trace_item_layout(
                 decl, obj=ptr, fq_name=ptr_name, ctx=ctx)
@@ -783,21 +788,27 @@ def trace_SetField(
     ctx: DepTraceContext,
 ) -> None:
     deps = set()
+    exprs = []
 
     assert node.value, "sdl SetField should always have value"
-    for dep in qltracer.trace_refs(
-        node.value,
-        schema=ctx.schema,
-        module=ctx.module,
-        objects=ctx.objects,
-        local_modules=ctx.local_modules,
-        params={},
-    ):
-        # ignore std module dependencies
-        if dep.get_module_name() not in s_schema.STD_MODULES:
-            deps.add(dep)
+    if node.name == 'default':
+        assert isinstance(node.value, qlast.Expr)
+        exprs.append(ExprDependency(expr=node.value))
+    else:
+        for dep in qltracer.trace_refs(
+            node.value,
+            schema=ctx.schema,
+            module=ctx.module,
+            objects=ctx.objects,
+            pointers=ctx.pointers,
+            local_modules=ctx.local_modules,
+            params={},
+        )[0]:
+            # ignore std module dependencies
+            if dep.get_module_name() not in s_schema.STD_MODULES:
+                deps.add(dep)
 
-    _register_item(node, deps=deps, ctx=ctx)
+    _register_item(node, deps=deps, hard_dep_exprs=exprs, ctx=ctx)
 
 
 @trace_dependencies.register
@@ -1066,6 +1077,8 @@ def _register_item(
     else:
         deps = set()
 
+    weak_deps: Set[s_name.QualName] = set()
+
     op = orig_op = copy.copy(decl)
 
     if ctx.depstack:
@@ -1183,66 +1196,73 @@ def _register_item(
                 else:
                     params = {}
 
-                tdeps = qltracer.trace_refs(
+                strong_tdeps, weak_tdeps = qltracer.trace_refs(
                     qlexpr,
                     schema=ctx.schema,
                     module=ctx.module,
                     path_prefix=source,
                     anchors=anchors,
                     objects=ctx.objects,
+                    pointers=ctx.pointers,
                     local_modules=ctx.local_modules,
                     params=params,
                 )
 
-                pdeps: MutableSet[s_name.QualName] = set()
-                for dep in tdeps:
-                    # ignore std module dependencies
-                    if dep.get_module_name() not in s_schema.STD_MODULES:
-                        # First check if the dep is a pointer that's
-                        # defined explicitly. If it's not explicitly
-                        # defined, check for ancestors and use them
-                        # instead.
-                        #
-                        # FIXME: Ideally we should use the closest
-                        # ancestor, instead of all of them, but
-                        # including all is still correct.
-                        if '@' in dep.name:
-                            pdeps |= _get_pointer_deps(dep, ctx=ctx)
-                        else:
-                            pdeps.add(dep)
-
-                # Handle the pre-processed deps now.
-                for dep in pdeps:
-                    deps.add(dep)
-
-                    if isinstance(
-                            decl, (qlast.CreateAlias, qlast.CreateGlobal)):
-                        # If the declaration is a view, we need to be
-                        # dependent on all the types and their props
-                        # used in the view.
-                        vdeps = {dep} | ctx.ancestors.get(dep, set())
-                        for vdep in vdeps:
-                            deps |= ctx.defdeps.get(vdep, set())
-
-                    if (
-                        isinstance(decl, (
-                            qlast.CreateConcretePointer, qlast.CreateGlobal))
-                        and isinstance(decl.target, qlast.Expr)
-                    ) or isinstance(
-                        decl, (qlast.CreateAccessPolicy, qlast.CreateTrigger)
-                    ):
-                        # If the declaration is a computable pointer/global
-                        # or access policy (XXX: trigger?),
-                        # we need to include the
-                        # possible constraints for every dependency
-                        # that it lists. This is so that any other
-                        # links/props that this computable uses has
-                        # all of their constraints defined before the
-                        # computable and the cardinality can be
-                        # inferred correctly.
-                        cdeps = {dep} | ctx.ancestors.get(dep, set())
-                        for cdep in cdeps:
-                            deps |= ctx.constraints.get(cdep, set())
+                for tdeps, strong in (
+                    (strong_tdeps, True), (weak_tdeps, False)
+                ):
+                    pdeps: MutableSet[s_name.QualName] = set()
+                    for dep in tdeps:
+                        # ignore std module dependencies
+                        if dep.get_module_name() not in s_schema.STD_MODULES:
+                            # First check if the dep is a pointer that's
+                            # defined explicitly. If it's not explicitly
+                            # defined, check for ancestors and use them
+                            # instead.
+                            #
+                            # FIXME: Ideally we should use the closest
+                            # ancestor, instead of all of them, but
+                            # including all is still correct.
+                            if '@' in dep.name:
+                                pdeps |= _get_pointer_deps(dep, ctx=ctx)
+                            else:
+                                pdeps.add(dep)
+
+                    # Handle the pre-processed deps now.
+                    cdeps = deps if strong else weak_deps
+                    for dep in pdeps:
+                        cdeps.add(dep)
+
+                        if isinstance(
+                                decl, (qlast.CreateAlias, qlast.CreateGlobal)):
+                            # If the declaration is a view, we need to be
+                            # dependent on all the types and their props
+                            # used in the view.
+                            vdeps = {dep} | ctx.ancestors.get(dep, set())
+                            for vdep in vdeps:
+                                cdeps |= ctx.defdeps.get(vdep, set())
+
+                        if (
+                            isinstance(decl, (
+                                qlast.CreateConcretePointer,
+                                qlast.CreateGlobal))
+                            and isinstance(decl.target, qlast.Expr)
+                        ) or isinstance(
+                            decl, (
+                                qlast.CreateAccessPolicy, qlast.CreateTrigger)
+                        ):
+                            # If the declaration is a computable pointer/global
+                            # or access policy (XXX: trigger?),
+                            # we need to include the
+                            # possible constraints for every dependency
+                            # that it lists. This is so that any other
+                            # links/props that this computable uses has
+                            # all of their constraints defined before the
+                            # computable and the cardinality can be
+                            # inferred correctly.
+                            con_deps = {dep} | ctx.ancestors.get(dep, set())
+                            for con_dep in con_deps:
+                                cdeps |= ctx.constraints.get(con_dep, set())
             else:
                 raise AssertionError(f'unexpected dependency type: {expr!r}')
 
@@ -1253,6 +1273,7 @@ def _register_item(
         parent_node.loop_control.add(fq_name)
 
     node.deps |= deps
+    node.weak_deps |= weak_deps - {fq_name}
 
 
 def _get_pointer_deps(
@@ -1287,6 +1308,10 @@ def _get_pointer_deps(
     # as their prefix. As a rule, the assumption is that depending on
     # a link typically comes as a package of depending on the link's
     # property.
+    # This will *also* grab any constraints on the pointer, which
+    # is is important for properly doing cardinality inference
+    # on expressions involving it.
+    # PERF: We should avoid actually searching all the objects.
     for propname in ctx.objects:
         if str(propname).startswith(str(pointer) + '@'):
             result.add(propname)
diff --git a/edb/edgeql/tracer.py b/edb/edgeql/tracer.py
index b6a73716066..ec4eeb4bb24 100644
--- a/edb/edgeql/tracer.py
+++ b/edb/edgeql/tracer.py
@@ -319,16 +319,21 @@ def trace_refs(
     path_prefix: Optional[sn.QualName] = None,
     module: str,
     objects: Dict[sn.QualName, Optional[ObjectLike]],
+    pointers: Mapping[sn.UnqualName, Set[sn.QualName]],
     params: Mapping[str, sn.QualName],
     local_modules: AbstractSet[str]
-) -> FrozenSet[sn.QualName]:
+) -> Tuple[FrozenSet[sn.QualName], FrozenSet[sn.QualName]]:
 
-    """Return a list of schema item names used in an expression."""
+    """Return a list of schema item names used in an expression.
+
+    First set is strong deps, second is weak.
+    """
 
     ctx = TracerContext(
         schema=schema,
         module=module,
         objects=objects,
+        pointers=pointers,
         anchors=anchors or {},
         path_prefix=path_prefix,
         modaliases={},
@@ -337,7 +342,7 @@ def trace_refs(
         local_modules=local_modules,
     )
     trace(qltree, ctx=ctx)
-    return frozenset(ctx.refs)
+    return frozenset(ctx.refs), frozenset(ctx.weak_refs)
 
 
 def resolve_name(
@@ -398,6 +403,7 @@ def __init__(
         schema: s_schema.Schema,
         module: str,
         objects: Dict[sn.QualName, Optional[ObjectLike]],
+        pointers: Mapping[sn.UnqualName, Set[sn.QualName]],
         anchors: Mapping[str, sn.QualName],
         path_prefix: Optional[sn.QualName],
         modaliases: Dict[Optional[str], str],
@@ -407,8 +413,10 @@ def __init__(
     ) -> None:
         self.schema = schema
         self.refs: Set[sn.QualName] = set()
+        self.weak_refs: Set[sn.QualName] = set()
         self.module = module
         self.objects = objects
+        self.pointers = pointers
         self.anchors = anchors
         self.path_prefix = path_prefix
         self.modaliases = modaliases
@@ -461,6 +469,8 @@ def _fork_context(ctx: TracerContext) -> TracerContext:
         schema=ctx.schema,
         module=ctx.module,
         objects=dict(ctx.objects),
+        # XXX?
+        pointers=ctx.pointers,
         anchors=ctx.anchors,
         path_prefix=ctx.path_prefix,
         modaliases=dict(ctx.modaliases),
@@ -469,6 +479,7 @@ def _fork_context(ctx: TracerContext) -> TracerContext:
         local_modules=ctx.local_modules,
     )
     nctx.refs = ctx.refs
+    nctx.weak_refs = ctx.weak_refs
 
     return nctx
 
@@ -522,6 +533,7 @@ def result_alias_context(
             schema=ctx.schema,
             module=ctx.module,
             objects=dict(ctx.objects),
+            pointers=ctx.pointers,
             anchors=ctx.anchors,
             path_prefix=ctx.path_prefix,
             modaliases=ctx.modaliases,
@@ -690,6 +702,13 @@ def trace_Path(
     ptr: Optional[Union[Pointer, s_pointers.Pointer]] = None
     plen = len(node.steps)
 
+    # HACK: This isn't very smart, and can't properly track types
+    # through arbitrary expressions. To try to mitigate the damage
+    # from this, when we have a pointer step but don't know the type,
+    # we track *weak* references to all pointers with that name.
+    # This won't always work (if there is a tangle of cyclic weak deps),
+    # but it works pretty well.
+
     for i, step in enumerate(node.steps):
         if isinstance(step, qlast.ObjectRef):
             # the ObjectRef without a module may be referring to an
@@ -706,6 +725,8 @@ def trace_Path(
                     tip = ctx.schema.get(refname, sourcectx=step.context)
 
         elif isinstance(step, qlast.Ptr):
+            pname = s_utils.ast_ref_to_unqualname(step.ptr)
+
             if i == 0:
                 # Abbreviated path.
                 if ctx.path_prefix in ctx.objects:
@@ -714,18 +735,20 @@ def trace_Path(
                         ptr = tip
                 else:
                     # We can't reason about this path.
-                    return None
+                    # Do a weak dependency on anything with the same name.
+                    ctx.weak_refs.update(ctx.pointers.get(pname, ()))
 
             if step.type == 'property':
                 if ptr is None:
-                    # This is either a computable def, or
-                    # unknown link, bail.
-                    return None
+                    # This is either a computable def or unknown link, bail.
+                    # Do a weak dependency on anything with the same name.
+                    ctx.weak_refs.update(ctx.pointers.get(pname, ()))
+                    tip = None
 
                 elif isinstance(ptr, (s_links.Link, Pointer)):
                     lprop = ptr.maybe_get_ptr(
                         ctx.schema,
-                        s_utils.ast_ref_to_unqualname(step.ptr),
+                        pname,
                     )
                     if lprop is None:
                         # Invalid link property reference, bail.
@@ -755,7 +778,9 @@ def trace_Path(
                         # it can be is "Object", which is trivial.
                         # However, we need to make it dependent on
                         # every link of the same name now.
-                        for fqname, obj in ctx.objects.items():
+                        for fqname in ctx.pointers.get(pname, ()):
+                            obj = ctx.objects.get(fqname)
+
                             # Ignore what appears to not be a link
                             # with the right name.
                             if (isinstance(obj, (s_pointers.Pointer,
@@ -773,7 +798,7 @@ def trace_Path(
                                     # name.
                                     ctx.refs.add(fqname)
 
-                        return None
+                        tip = ptr = None
                 else:
                     if isinstance(tip, (Source, s_sources.Source)):
                         ptr = tip.maybe_get_ptr(
@@ -814,7 +839,9 @@ def trace_Path(
 
                     else:
                         # We can't reason about this path.
-                        return None
+                        # Do a weak dependency on anything with the same name.
+                        ctx.weak_refs.update(ctx.pointers.get(pname, ()))
+                        tip = ptr = None
 
         elif isinstance(step, qlast.TypeIntersection):
             # This tip is determined from the type in the type
@@ -847,6 +874,7 @@ def trace_Path(
 
         else:
             tr = trace(step, ctx=ctx)
+            tip = ptr = None
             if tr is not None:
                 tip = tr
                 if isinstance(tip, Pointer):
diff --git a/tests/test_edgeql_data_migration.py b/tests/test_edgeql_data_migration.py
index 12fc03e9f33..b02c1dc5176 100644
--- a/tests/test_edgeql_data_migration.py
+++ b/tests/test_edgeql_data_migration.py
@@ -10959,6 +10959,20 @@ async def test_edgeql_migration_drop_constraint_03(self):
             }
         ''')
 
+        await self.migrate(r'''
+            type Foo {
+                required link foo -> C {
+                    default := (SELECT C FILTER .val = 'D00');
+                }
+            }
+
+            type C {
+                required property val -> str {
+                    constraint exclusive;
+                }
+            }
+        ''')
+
         await self.migrate('')
 
     async def test_edgeql_migration_drop_constraint_04(self):
diff --git a/tests/test_schema.py b/tests/test_schema.py
index 6b14878aa6c..8eadb179259 100644
--- a/tests/test_schema.py
+++ b/tests/test_schema.py
@@ -841,6 +841,70 @@ def test_schema_func_optional_variadic_01(self):
                 using (assert_exists(bar));
         """
 
+    def test_schema_hard_sorting_01(self):
+        # This is hard to sort properly because we don't understand the types.
+        # From #4683.
+        """
+            global current_user_id -> uuid;
+            global current_user := (
+              select User filter .id = global current_user_id
+            );
+            global current_user_role := (
+              (global current_user).role.slug
+            );
+
+            type Role {
+              property slug -> str;
+            }
+
+            type User {
+              required link role -> Role;
+            }
+        """
+
+    def test_schema_hard_sorting_02(self):
+        # This is hard to sort properly because we don't understand the types.
+        # From #5163
+        """
+            type Branch;
+            type CO2DataPoint{
+                required link datapoint -> DataPoint;
+                link branch := .datapoint.data_entry.branch;
+            }
+            type DataPoint{
+                required link data_entry := assert_exists(
+                    .<data_points[is DataEntry]);
+            }
+
+            type DataEntry{
+                required link branch -> Branch;
+                multi link data_points -> DataPoint;
+            }
+       """
+
+    def test_schema_hard_sorting_03(self):
+        # This is hard to sort properly because we don't understand the types.
+        """
+            type A {
+                property foo := assert_exists(B).bar;
+            };
+            type B {
+                property bar := 1;
+            };
+       """
+
+    def test_schema_hard_sorting_04(self):
+        # This is hard to sort properly because we don't understand the types.
+        """
+            type A {
+                property foo := (
+                    with Z := assert_exists(B) select Z.bar);
+            };
+            type B {
+                property bar := 1;
+            };
+       """
+
     def test_schema_refs_01(self):
         schema = self.load_schema("""
             type Object1;


Code review comments:
diff_hunk: @@ -461,6 +469,8 @@ def _fork_context(ctx: TracerContext) -> TracerContext:
         schema=ctx.schema,
         module=ctx.module,
         objects=dict(ctx.objects),
+        # XXX?
path: edb/edgeql/tracer.py
text: @user1:
Can you elaborate the XXX or remove it?