diff --git a/internal/core/validate/validate.go b/internal/core/validate/validate.go
new file mode 100644
index 0000000..2f20f82
--- /dev/null
+++ b/internal/core/validate/validate.go
@@ -0,0 +1,110 @@
+// Copyright 2020 CUE Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package validate
+
+import (
+	"cuelang.org/go/cue/errors"
+	"cuelang.org/go/cue/token"
+	"cuelang.org/go/internal/core/adt"
+	"cuelang.org/go/internal/core/debug"
+)
+
+type Config struct {
+	// Concrete, if true, requires that all values be concrete.
+	Concrete bool
+
+	// DisallowCycles indicates that there may not be cycles.
+	DisallowCycles bool
+
+	// AllErrors continues descending into a Vertex, even if errors are found.
+	AllErrors bool
+
+	// TODO: omitOptional, if this is becomes relevant.
+}
+
+// Validate checks that a value has certain properties. The value must have
+// been evaluated.
+func Validate(r adt.Runtime, v *adt.Vertex, cfg *Config) *adt.Bottom {
+	if cfg == nil {
+		cfg = &Config{}
+	}
+	x := validator{Config: *cfg, runtime: r}
+	x.validate(v)
+	return x.err
+}
+
+type validator struct {
+	Config
+	err          *adt.Bottom
+	inDefinition int
+	runtime      adt.Runtime
+}
+
+func (v *validator) add(b *adt.Bottom) {
+	if !v.AllErrors {
+		v.err = adt.CombineErrors(nil, v.err, b)
+		return
+	}
+	if !b.ChildError {
+		v.err = adt.CombineErrors(nil, v.err, b)
+	}
+}
+
+func (v *validator) validate(x *adt.Vertex) {
+	if b, _ := x.Value.(*adt.Bottom); b != nil {
+		switch b.Code {
+		case adt.CycleError:
+			if v.Concrete || v.DisallowCycles {
+				v.add(b)
+			}
+
+		case adt.IncompleteError, adt.NotExistError:
+			if v.Concrete {
+				v.add(b)
+			}
+
+		default:
+			v.add(b)
+		}
+		if !b.HasRecursive {
+			return
+		}
+
+	} else if v.Concrete && v.inDefinition == 0 && !adt.IsConcrete(x) {
+		p := token.NoPos
+		if src := x.Value.Source(); src != nil {
+			p = src.Pos()
+		}
+		// TODO: use ValueError to get full path.
+		v.add(&adt.Bottom{
+			Code: adt.IncompleteError,
+			Err: errors.Newf(p, "incomplete value %v",
+				debug.NodeString(v.runtime, x.Value, nil)),
+		})
+	}
+
+	for _, a := range x.Arcs {
+		if !v.AllErrors && v.err != nil {
+			break
+		}
+		if a.Label.IsRegular() {
+			v.validate(a)
+		} else {
+			v.inDefinition++
+			v.validate(a)
+			v.inDefinition--
+		}
+	}
+}
diff --git a/internal/core/validate/validate_test.go b/internal/core/validate/validate_test.go
new file mode 100644
index 0000000..ab70286
--- /dev/null
+++ b/internal/core/validate/validate_test.go
@@ -0,0 +1,180 @@
+// Copyright 2020 CUE Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package validate
+
+import (
+	"fmt"
+	"strings"
+	"testing"
+
+	"cuelang.org/go/cue/errors"
+	"cuelang.org/go/cue/parser"
+	"cuelang.org/go/internal/core/adt"
+	"cuelang.org/go/internal/core/compile"
+	"cuelang.org/go/internal/core/eval"
+	"cuelang.org/go/internal/core/runtime"
+	"github.com/google/go-cmp/cmp"
+)
+
+func TestValidate(t *testing.T) {
+	testCases := []struct {
+		desc   string
+		in     string
+		out    string
+		lookup string
+		cfg    *Config
+	}{{
+		desc: "no error, but not concrete, even with definition label",
+		cfg:  &Config{Concrete: true},
+		in: `
+		#foo: { use: string }
+		`,
+		lookup: "#foo",
+		out:    "incomplete\nincomplete value string",
+	}, {
+		desc: "definitions not considered for completeness",
+		cfg:  &Config{Concrete: true},
+		in: `
+		#foo: { use: string }
+		`,
+	}, {
+		desc: "hidden fields not considered for completeness",
+		cfg:  &Config{Concrete: true},
+		in: `
+		_foo: { use: string }
+		`,
+	}, {
+		desc: "hidden fields not considered for completeness",
+		in: `
+		_foo: { use: string }
+		`,
+	}, {
+		desc: "evaluation error at top",
+		in: `
+		1 & 2
+		`,
+		out: "eval\nincompatible values 2 and 1",
+	}, {
+		desc: "evaluation error in field",
+		in: `
+		x: 1 & 2
+		`,
+		out: "eval\nincompatible values 2 and 1",
+	}, {
+		desc: "first error",
+		in: `
+		x: 1 & 2
+		y: 2 & 4
+		`,
+		out: "eval\nincompatible values 2 and 1",
+	}, {
+		desc: "all errors",
+		cfg:  &Config{AllErrors: true},
+		in: `
+		x: 1 & 2
+		y: 2 & 4
+		`,
+		out: `eval
+incompatible values 2 and 1
+incompatible values 4 and 2`,
+	}, {
+		desc: "incomplete",
+		cfg:  &Config{Concrete: true},
+		in: `
+		y: 2 + x
+		x: string
+		`,
+		out: "incomplete\nnon-concrete value string in operand to +:\n    test:2:6",
+	}, {
+		desc: "allowed incomplete cycle",
+		in: `
+		y: x
+		x: y
+		`,
+	}, {
+		desc: "allowed incomplete when disallowing cycles",
+		cfg:  &Config{DisallowCycles: true},
+		in: `
+		y: string
+		x: y
+		`,
+	}, {
+		desc: "disallow cycle",
+		cfg:  &Config{DisallowCycles: true},
+		in: `
+		y: x + 1
+		x: y - 1
+		`,
+		out: "cycle\ncycle error",
+	}, {
+		desc: "disallow cycle",
+		cfg:  &Config{DisallowCycles: true},
+		in: `
+		a: b - 100
+		b: a + 100
+		c: [c[1], c[0]]		`,
+		out: "cycle\ncycle error",
+	}, {
+		desc: "treat cycles as incomplete when not disallowing",
+		cfg:  &Config{},
+		in: `
+		y: x + 1
+		x: y - 1
+		`,
+	}, {
+		// Note: this is already handled by evaluation, as terminal errors
+		// are percolated up.
+		desc: "catch most serious error",
+		cfg:  &Config{Concrete: true},
+		in: `
+		y: string
+		x: 1 & 2
+		`,
+		out: "eval\nincompatible values 2 and 1",
+	}}
+
+	r := runtime.New()
+	ctx := eval.NewContext(r, nil)
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			f, err := parser.ParseFile("test", tc.in)
+			if err != nil {
+				t.Fatal(err)
+			}
+			v, err := compile.Files(nil, r, f)
+			if err != nil {
+				t.Fatal(err)
+			}
+			ctx.Unify(ctx, v, adt.Finalized)
+			if tc.lookup != "" {
+				v = v.Lookup(adt.MakeIdentLabel(r, tc.lookup))
+			}
+
+			b := Validate(r, v, tc.cfg)
+
+			w := &strings.Builder{}
+			if b != nil {
+				fmt.Fprintln(w, b.Code)
+				errors.Print(w, b.Err, nil)
+			}
+
+			got := strings.TrimSpace(w.String())
+			if tc.out != got {
+				t.Error(cmp.Diff(tc.out, got))
+			}
+		})
+	}
+}