Virtual Workspace
Problem
Design VirtualWorkspace, an in-memory workspace organized like folders. Nodes can be created, moved, selected by absolute or relative path, annotated with string metadata, and searched with combined query conditions. One selected node supplies the base for relative paths.
Requirements
- Canonical navigation. Resolve every path against the tree state at the start of its call.
/begins an absolute path; every other path is relative to the current node. Ignore empty segments and., apply..lexically before lookup, and reject any path that climbs above the root. A canonical path is absolute, uses one/between segments, and has no trailing/except at the root. - Unique children. Every node may have children, but sibling names are unique by exact, case-sensitive comparison. The root always exists at
/, has no parent, and cannot be created again. - Metadata replacement. Each node has at most one string value for a metadata key.
setMetadatacreates or replaces that entry. Keys and values are case-sensitive, and an empty value is present rather than missing. - Cycle-safe movement. Move and optionally rename one non-root subtree without changing its node identities, descendants, or metadata. Reject a destination that is the source or its descendant. Moving to the same parent with the same name succeeds without changing state.
- Current-node identity. Navigation selects a node rather than storing its path. Moving that node or any ancestor changes the path reported by
currentPath. Other operations do not change the current node. - Composable predicates. A
QueryExpressionis caller-owned immutable input. Validate the complete expression before evaluating it, including operands that Boolean short-circuiting could skip. Atomic operators use exact ASCII string comparison;and,or, andnotuse their standard Boolean meanings. - Query pipeline. A query includes its resolved start node and all descendants. Filter first, order all matches, then apply
offsetfollowed bylimit. Return canonical path strings captured during the call in a detached list. - Stable ordering. Ascending traversal order is depth-first pre-order, starting with the query root and visiting children by ascending name. Descending traversal reverses the complete filtered ascending traversal list. Path, name, and metadata primary keys use ASCII lexicographic order. A missing metadata key precedes every present value in ascending order and follows every present value in descending order. Name and metadata ties use canonical path ascending in both directions. Direction reverses only the primary key, except for traversal descending.
- Atomic failures. A failed call changes no hierarchy, metadata, or current node. Validate arguments from left to right before lookup, then apply the state-dependent check order shown below.
API
QueryExpression is supplied by the runtime template. All four fields are non-null and required.
| Field | Type | Meaning |
|---|---|---|
operator | string | A supported operator name. |
key | string | A metadata key when required, otherwise "". |
value | string | A comparison value when used, otherwise "". |
operands | QueryExpression[] | Child expressions when required, otherwise an empty list. |
| Operator | Required shape | Match |
|---|---|---|
all | Empty key, empty value, no operands | Every node |
name-equals | Empty key, no operands | Name equals value; the root name is "" |
name-prefix | Empty key, no operands | Name starts with value; "" matches every name |
metadata-equals | Valid key, no operands | Key is present and its value equals value |
metadata-exists | Valid key, empty value, no operands | Key is present, including with an empty value |
and | Empty key, empty value, 2 to 8 operands | Every operand matches |
or | Empty key, empty value, 2 to 8 operands | At least one operand matches |
not | Empty key, empty value, exactly 1 operand | Its operand does not match |
| Signature | Returns | Behavior |
|---|---|---|
VirtualWorkspace() | Not applicable | Creates only the root and selects it. |
createNode(parentPath: string, name: string) | string | Creates one empty child and returns its canonical path. |
navigate(path: string) | string | Selects the resolved node and returns its canonical path. |
currentPath() | string | Returns the selected node's current canonical path. |
setMetadata(path: string, key: string, value: string) | void | Creates or replaces one metadata entry on the resolved node. |
moveNode(sourcePath: string, destinationParentPath: string, newName: string) | string | Resolves both paths against the same pre-call current node, then returns the source node's resulting path. |
query(startPath: string, expression: QueryExpression, sortBy: string, direction: string, offset: integer, limit: integer) | string[] | Returns one page. sortBy is traversal, path, name, or metadata:<key>; direction is asc or desc. |
Public error types are InvalidArgumentError, NodeNotFoundError, NameConflictError, RootMoveError, and CycleError; their messages are not judged. Path validation includes lexical normalization. Expression validation is depth-first in operand order and checks each node's operator, key shape, value shape, then operands. A metadata:<key> sort validates its key suffix.
| Method | State-dependent checks after argument validation |
|---|---|
createNode | Parent exists, then sibling name is free |
navigate | Target exists |
setMetadata | Target exists |
moveNode | Source exists, source is not root, destination exists, destination is not the source or its descendant, then the destination name is free unless this is the unchanged slot |
query | Start node exists |
Malformed or out-of-range input raises InvalidArgumentError. A valid normalized path with no node raises NodeNotFoundError. An occupied destination name raises NameConflictError; moving the root raises RootMoveError; moving a node under itself or a descendant raises CycleError.
Examples
| Step | Operation | Result |
|---|---|---|
| 1 | createNode("/", "projects") | "/projects" |
| 2 | createNode("/projects", "alpha") | "/projects/alpha" |
| 3 | createNode("/projects", "beta") | "/projects/beta" |
| 4 | navigate("/projects//alpha/./") | "/projects/alpha" |
| 5 | createNode(".", "notes") | "/projects/alpha/notes" |
| 6 | navigate("notes") | "/projects/alpha/notes" |
| 7 | moveNode("/projects/alpha", "/projects/beta", "archived") | "/projects/beta/archived" |
| 8 | currentPath() | "/projects/beta/archived/notes" |
If /docs/report and /archive/report both have owner="ana", querying / with and(metadata-equals("owner", "ana"), not(name-prefix("draft"))), sorting by name ascending, offset 1, and limit 1 returns ["/docs/report"].
Constraints
- Node names match
[A-Za-z0-9._-]{1,32}except.and... - Metadata keys match
[A-Za-z][A-Za-z0-9._-]{0,31}. - Metadata values contain 0 to 64 printable ASCII characters, code points 32 through 126.
- Raw paths contain 1 to 1024 printable ASCII characters, and every ordinary segment is a valid node name.
- A workspace contains at most 10,000 nodes and at most 16 metadata keys per node.
- A testcase contains at most 1,000 public method calls.
- An expression contains at most 64 nodes and has depth at most 8, counting its root.
offsetis from 0 through 10,000;limitis from 1 through 1,000. Pagination arithmetic fits a signed 32-bit integer.- Returned paths are at most 1024 characters.
Notes
Official testcases use one thread and preserve its action order. Concurrent calls on one instance are outside scope, and separate instances or testcase processes must not share mutable state. Deletion, copying, recursive creation, wildcard paths, symbolic links, permissions, file contents, metadata removal, non-string metadata, locale-aware matching, caller-defined predicate functions, lazy cursors, persistence, and cross-query snapshots are outside scope.