Namespace funnyqt.pmatch

Graph Pattern Matching on arbitrary models.

Other Namespaces

Show/Hide
funnyqt.bidi
Bidirectional transformations (BX).
funnyqt.coevo.tg
Co-Evolution transformations on TGraphs.
funnyqt.edn
Printing/persisting and reading/loading query results and transformation traces as EDN.
funnyqt.emf
Core functions for accessing and manipulating EMF models.
funnyqt.extensional
Specify models extensionally.
funnyqt.generic
Generic protocols extended upon many different types, and generic functions.
funnyqt.in-place
In-place transformation stuff.
funnyqt.model2model
Rule-base out-place transformations similar to ATL or QVTo.
funnyqt.polyfns
Polymorphic functions dispatching on types of model elements.
funnyqt.query
Generic query functions like regular path expressions & quantified expressions.
funnyqt.query.emf
EMF-specific query functions
funnyqt.query.tg
TG-specific query functions
funnyqt.relational
Relational Model Querying.
funnyqt.tg
Core functions for accessing and manipulating TGraphs.
funnyqt.utils
Generic utility functions, e.g., for signaling errors, debugging, and profiling,
funnyqt.visualization
Model visualization functions.
funnyqt.xmltg
Convert XML to DOM-like TGraphs.
Index Page
Alphabetic Var Index

Public Vars

Usage Documentation

Show/Hide
Graph Pattern Matching on arbitrary models.
Back to top

Details of Public Vars

Macro: defpattern

Arglists:
=========

  (defpattern name doc-string? attr-map? [args] [pattern])
  (defpattern name doc-string? attr-map? ([args] [pattern]) +)

Docstring:
==========

  Defines a pattern with `name`, optional `doc-string`, optional `attr-map`,
  an `args` vector, and a `pattern-spec` vector.  The first argument in `args`
  must denote the model which the pattern is applied to.

  When applied to a model, it returns the sequence of all matches.  By default,
  this seq is a lazy seq.

  Node and Edge Symbols
  =====================

  In the simplest case, `pattern-spec` contains only symbols for nodes and
  edges.

    v<V>            ; A node of type V identified as v
    v<V> -<:e>-> v  ; A node v of type V referencing itself with an e-reference

  V is a qualified name of a node type.  Edge types are either reference names
  given as keywords or qualified edge type names in case the model
  representation has first-class edges.  If it does, the edges can also be
  matched and added to the match results by adding an identifier.

    v<V> -e<E>-> v

  Every edge symbol in a pattern must have a node symbol at its start and at
  its end.

  There are also edge symbols which only match edges with containment
  semantics, e.g., v1 <>-- v2 matches a node v1 which contains a node v2, and
  the other way round, v1 --<> v2 matches a node v1 which is contained by a
  node v2.  Again, the edge can be restricted by type/role and have an
  identifier in case of first-class edges: v1 <:contents>hasContents-- v2.

  Anonymous Node and Edge Symbols
  ===============================

  Both the identifiers and the types enclosed in angle brackets are optional.
  So this is a valid pattern, too.

    [v --> <V> -<:e>-> <> --> x<X>]

  This pattern matches an arbitrary node v that is connected to an X-node x via
  some arbitrary reference leading to some V-node from which an e-reference
  leads some arbitrary other node from which another arbitrary reference leads
  to x.  There may be many such paths between v and x but anonymous nodes and
  edges specify only the existence of a matching node, edge, or path.

  Argument Node and Edge Symbols
  ==============================

  Patterns may also include the arguments given to the defpattern, in which
  case those are assumed to be bound to one single node or edge, depending on
  their usage in the pattern, e.g., arg must be a node and -arg-> must be an
  edge.

  For example, the following pattern receives an argument s which according to
  the usage in a pattern must be a node.

    (defpattern foobar [m s] [s --> t])

  The pattern returns matches of the form {:s s, :t t} where s is the node
  given as argument and t is a node referenced from s.

  Constraints
  ===========

  Patters may further include arbitrary constraints that must hold for a valid
  match using :when clauses:

    [v --> w
     :when (pred1? v)
     :when (not (pred2? w))]

  Negative Edges
  ==============

  Patterns may contain negative edges indicated by edge symbols with name !.
  Those must not exist for a match to succeed.  For example, the following
  declares that there must be a foo reference from v to w, but w must have no
  outgoing edges at all, and v must not reference w with its bar reference.

    [v -<:foo>-> w -!-> <>
     v -!<:bar>-> w]

  Isomorphic Matching
  ===================

  By default, FunnyQT performs homomorphic matching, i.e., in a pattern

    [v1<V> -<E>-> v2<V>]

  it is possible that both v1 and v2 are matched to the same node in the host
  graph in case an E-edge starts and ends at that node.  This behavior can be
  changed to isomorphic matching using the :isomorphic keyword.

    [v1<V> -<E>-> v2<V> :isomorphic]

  Here, v1 and v2 are guaranteed to be matched to different nodes.  This
  behavior applies to all non-anonymous nodes and edges in the pattern but not
  to local bindings and comprehension bindings (which see below).

  Local Bindings
  ==============

  Moreover, a pattern may bind further variables using :let and :when-let which
  also become part of the matches.

    [v --> w
     :let [a (foo v), b (bar v)]
     :when-let [c (baz w)]]

  Hereby, the variables bound by :let (a and b) are taken as-is whereas the
  variables bound by :when-let must be logically true in order to match.  That
  is, in the example above, a and b could be nil, but c has to be logically
  true (i.e., not nil and not false) for a match to occur.  a, b, and c are
  also part of the matches.

  Comprehension Bindings
  ======================

  Patterns may also contain usual comprehension binding forms using :for, i.e.,
  pairs of variables and expressions.

    [v --> w
     :for [u (p-seq w [p-+ [p-alt <>-- :someRef]])]]

  Again, u is also part of the matches.

  Pattern Inheritance
  ===================

  Patterns can be composed of other named patterns bound by either defpattern
  or letpattern using :extends clauses.

    (defpattern a-A [m] [a<A>])
    (defpattern b-B [m] [b<B>])
    (defpattern a-b2 [m] [:extends [a-A, (b-B :b b2)]
                          a --> b2])

  In the example above, the pattern a-b2 extends a-A, which means a-A's pattern
  is also part of a-b2's pattern.  It also extends b-B, however, the node named
  b in b-B should be named b2 in a-b2.  The pattern a-b2 is completely
  equivalent to the following definition.

    (defpattern a-b2* [m] [a<A> b2<B> a --> b2])

  Extend clauses may be transitive, and there may be multiple :extends clauses
  in a pattern.

  Extending patterns may also override the types of elements of the extended
  patterns.  For example,

    (defpattern b1-b2 [m] [:extends [(a-b2 :a b1)]
                           b1<B>]

  defines that b1-b2 extends a-b2 thereby renaming a to b1.  Additionally, b1's
  type is defined to be B instead of A as defined by a-b2.

  In case an extended pattern is overloaded on arity, the :extends clause may
  specify which pattern to take using [:extends [(some-pattern 1)]] where the 1
  denotes the pattern of the second version.  0, i.e., the first version, is
  the default.  After this index, the renamings follow.

  A pattern may also extend a different arity of itself like so:

    (defpattern p
      ([m] [cur<B> :extends [(p 1)]])
      ([m cur] [cur -<:t>-> next<C>]))

  The modifier keywords :isomorphic and :distinct as well as :as-clauses are
  not propagated from extended to extending patterns, thus it is up to the
  extending pattern to specify those if needed.

  Negative Patterns
  =================

  A pattern may include arbitrarily many negative patterns which implement
  negative application conditions (NACs).  In order for the pattern to match,
  all included negative patterns must not match.

    [b<B>
     :negative [b -<:t>-> c1<C> -<:t>-> a<A>
                b -<:t>-> c2<C> -<:t>-> a
                :isomorphic]]

  This pattern matches all B-nodes b which are not connected to two different
  C-nodes c1 and c2 that both reference the same A-node a.

  If a negative pattern is not connected to the surrounding pattern, then it
  acts as a global NAC.  Note that this is generally not a good idea since it
  will be checked for every match of the surrounding pattern.  That is, every
  check except the first one is needless effort unless the model is modified
  from another thread so that the value of the NAC might change in between.

  Positive Patterns
  =================

  A patter may include arbitrarily many positive patters which implement
  positive application conditions (PACs).  In order for the pattern to match,
  all included positive patterns must also match.  The main difference between
  PACs and including the PAC in the surrounding pattern is that the nodes and
  edges of the PACs are not part of the matches, and the number of the PACs
  matches also don't contribute to the number of matches of the surrounding
  pattern.

    [b<B>
     :negative [b -<:t>-> c1<C> -<:t>-> a<A>
                b -<:t>-> c2<C> -<:t>-> a
                :isomorphic]]

  This pattern matches all B-nodes b which are connected to two different
  C-nodes c1 and c2 that both reference the same A-node a.

  If a positive pattern is not connected to the surrounding pattern, then it
  acts as a global PAC.  Like with negative patterns, this is probably not a
  good idea since the PACs are checked for every match of the surrounding
  pattern so it is needless effort in case the value of the PAC cannot change
  in the mean-time.

  Also note that if two nodes of the outer pattern are only connected by
  elements in a PAC, there is a serious performance penalty because first the
  outer pattern is matched (with quadratic effort for two unconnected nodes),
  and only if a match has been found, the PACs are checked in its context.

  Logically Combined Patterns
  ===========================

  Logically combined patterns extend NACs/PACs with logical combinators.  The
  general syntax is :operator [[ps1] [ps2] ...] where :operator is one
  of :and, :or, :xor, :nor, or :nand, and psI are normal pattern
  specifications.  In order for the outer pattern to match, the logically
  combined pattern must match according to the given operator.

  For example, the pattern

    [c<C>
     :xor [[c -<:t>-> c]
           [c -<:t>-> <B>]]]

  matches all C-nodes c which either reference themselves or some B-node with
  their c-reference (but not both!).

  Like negative and positive patterns, logically combined pattern are mere
  constraints, i.e., the symbols contained in the pattern specs ps1, ps2 etc
  are not part of the surrounding outer pattern's matches.

  As said, logically combined patterns are just extensions to NACs/PACs.  These
  equivalences hold:

    [...
     :and [[ps1] [ps2]]]

  is equivalent to

    [...
     :positive [ps1]
     :positive [ps2]]

  and

    [...
     :nor [[ps1] [ps2]]]

  is equivalent to

    [...
     :negative [ps1]
     :negative [ps2]]

  Alternative Patterns
  ====================

  Alternative patterns allow to specify variable parts in a pattern.  In
  contrast to negative/positive and logically combined patterns, they are not
  only constraints but the elements matched by the alternative patterns are
  part of the outer pattern's matches.

  Take this example pattern spec:

    [c<C>
     :alternative [[c -<:t>-> a<A!>]
                   [c -<:t>-> x<A> -<:s>-> a<A!>]]
     a -<:t>-> b<B>]

  The pattern matches C-nodes c, A-nodes a, and B-nodes b where c references a
  with its t-reference (first alternative), or where c references an A-node x
  with its t-reference which in turn references a with its s-reference (second
  alternative).  Additionally, a references b with its t-reference.

  The matches of this pattern have the form {:c #<C>, :a #<A>, :x #<A>}, i.e.,
  they have an entry for every identifier contained in the outer pattern spec,
  and every identifier in any of the alternative pattern specs.  In case a
  match is produced by the first alternative, the value of the :x key is nil.

  Note that due to the implementation it is important that no node symbols that
  are ought to be matched by the alternative patterns occur before those.
  E.g., if the above pattern was written

    [c<C>
     a -<:t>-> b<B>
     :alternative [[c -<:t>-> a<A!>]
                   [c -<:t>-> x<A> -<:s>-> a<A!>]]]

  the alternatives would be tested for every combination of a C-node c and an
  arbitrary node a and all its B-nodes referenced by its t-reference.  Clearly,
  this is not performant.

  Also note that for implementation reasons, pattern inheritance is not
  available for alternative patterns, i.e., the alternative pattern specs must
  not contain an :extends clause.

  Nested Patterns
  ===============

  A pattern can include nested pattern using :nested clauses.  Each :nested
  clause contains arbitrary many symbol-pattern pairs.

    [a<A> -<:d>-> d<D>
     :nested [f1 [a -<:t>-> a1
                  :nested [f2 [a1 -<:t>-> a2]]]]]

  So in the example above, the outer pattern has one inner pattern whose
  matches are bound to f1.  The nested pattern has another nested pattern whose
  matches are bound to f2.  Each pattern has access to the preceeding variables
  in the outer patterns, i.e., the first nested pattern can see a and d (and
  actually uses a), and the innermost nested pattern can see a, d, and a1 (and
  actually uses a1).

  The matches of the pattern above have the following structure.

    {:a a
     :d d
     :f1 ({:a1 a1
           :f2 ({:a2 a2}
                ...)}
          ...)}

  As can be seen, by default the elements already matched by an outer pattern
  are omitted in the matches of inner patterns, e.g., the :f1 matches don't
  include :a, and the :f2 matches don't include :a1.

  The :f1 and :f2 values are lazy sequences of nested pattern matches.

  Match Representation
  ====================

  By default, the matches of a pattern are represented as maps from keywords
  named according to the pattern symbol identifiers to the matched elements.

    [v --> w
     :when-let [u (foobar w)]]

  So the example above is equivalent to the following pattern with an :as form.

    [v --> w
     :when-let [u (foobar w)]
     :as {:u u, :v v, :w w}]

  To represent matches as vectors, one could write :as [v w u].  There is also
  the shorthand :as :vector which represents matches as vectors where the
  values are ordered according their occurence in the pattern.
  Thus, :as :vector is equivalent to :as [v w u] here.  For reasons of
  symmetry, there is also the shorthand :as :map which is equivalent to
  omitting the :as clause, i.e., matches are represented as maps.

  Distinct Matches
  ================

  Finally, a pattern may contain a :distinct modifier which allows to omit
  duplicate matches.  By default, there cannot be duplicate matches anyway
  because anonymous nodes/edges have existence rather than "enumerate all"
  semantics, but duplicates may occur with custom :as clauses.  E.g., a pattern
  with spec

    [a --> b --> c :as #{a b c}]

  may have duplicates but

    [a --> b --> c :as #{a b c} :distinct]

  has not.

  Available Options
  =================

  The :eager option
  -----------------

  If ^:eager metadata is attached to `name` (or the :eager option is set to
  true in the `attr-map`), then the pattern is evaluated eagerly giving rise to
  parallel evaluation.  Here, the matches of the first node in the `pattern` is
  computed sequentially and put into a vector.  This vector is then partitioned
  and the remaining pattern matching process is performed in parallel on the
  individual partitions.  By default, the vector of matches of the first node
  in the pattern is partitioned so that there are approximately 32 partitions
  to be processed per CPU (keep CPUs busy!), however, every partition must have
  at least 32 elements (not too much contention!).  This seems to be a good
  heuristic, but of course it cannot be optimal in every situation.

  Therefore, the :eager option may also be set to a vector of the form

    [MIN-PARTITION-SIZE PARTITIONS-PER-CPU]

  where MIN-PARTITION-SIZE denotes the minimal number of elements in a
  partition, and PARTITIONS-PER-CPU denotes the maximum number of partitions to
  be processed per CPU.

  The :sequential option
  ----------------------

  The parallel evaluation induced by :eager may be suppressed using
  ^:sequential metadata (or by setting the :sequential option to true in
  `attr-map`).

  The :pattern-expansion-context option
  -------------------------------------

  The expansion of a pattern, i.e., if it expands into a generic query, a query
  on TGraphs, or a query on EMF models (or something else), is controlled by
  the option `:pattern-expansion-context` with possible values `:generic`,
  `:tg` or `:emf` which can be specified in the `attr-map` given to
  `defpattern` or as metadata.

  Instead of using that option for every rule, you can also set
  `:pattern-expansion-context` metadata to the namespace defining patterns, in
  which case that expansion context is used as default for all patterns in that
  namespace.  Individual pattern may still override this namespace-global value
  with their own attr-maps.

  The :transducers option
  -----------------------

  If this option is enabled, transducers are used in some parts of pattern
  evaluation (concretely, when evaluating sequences with anonymous elements
  such as in [a --> <> --> b]) instead of traditional lazy sequence functions.
  This can be faster in some cases and slower in other cases.  So it's best to
  measure with and without this option and then use whatever performs better in
  a concrete scenario.
Back to top View Source

Function: eget-1

Arglists:
=========

  (eget-1 eo r)

Docstring:
==========

  Only for internal use.
Back to top View Source

Macro: letpattern

Arglists:
=========

  (letpattern [patterns] attr-map? & body)

Docstring:
==========

  Establishes local patterns just like `letfn` establishes local functions.
  Every pattern in the `patterns` vector is specified as one of:

    (pattern-name attr-map? [args] [pattern])
    (pattern-name attr-map? ([args] [pattern])+)

  The `attr-map` of the letpattern serves as default for all patterns defined
  by it which may override the defaults with their own attr-maps.

  For the syntax and semantics of patterns, see the `defpattern` docs.
Back to top View Source

Macro: pattern

Arglists:
=========

  (pattern name? attr-map? [args] [pattern])
  (pattern name? attr-map? ([args] [pattern]) +)

Docstring:
==========

  Creates an anonymous patterns just like `fn` creates an anonymous functions.
  The syntax is:

    (pattern pattern-name? attr-map? [args] [pattern])
    (pattern pattern-name? attr-map? ([args] [pattern])+)

  For the syntax and semantics of patterns, see the `defpattern` docs.
Back to top View Source

Var: pattern-graph-transform-function-map

  A map from techspace to pattern graph transformers.
Back to top View Source

Function: pattern-spec-to-pattern-graph

Arglists:
=========

  (pattern-spec-to-pattern-graph pname argvec pattern-spec isomorphic)

Docstring:
==========

  No docs attached.
Back to top View Source

Function: pg-to-for+-bindings-emf

Arglists:
=========

  (pg-to-for+-bindings-emf pname argvec pg)

Docstring:
==========

  No docs attached.
Back to top View Source

Function: pg-to-for+-bindings-generic

Arglists:
=========

  (pg-to-for+-bindings-generic pname argvec pg)

Docstring:
==========

  No docs attached.
Back to top View Source

Function: pg-to-for+-bindings-only-refs

Arglists:
=========

  (pg-to-for+-bindings-only-refs
   pname
   argvec
   pg
   elements-fn
   role-fn
   neighbors-fn
   contents-fn
   container-fn)

Docstring:
==========

  Internal transformer function that given a pattern argument vector `argvec`,
  a pattern graph `pg` and an `elements-fn`, a `role-fn` and a `neighbors-fn`
  transforms the pattern graph to a comprehension binding form.
Back to top View Source

Function: pg-to-for+-bindings-tg

Arglists:
=========

  (pg-to-for+-bindings-tg pname argvec pg)

Docstring:
==========

  No docs attached.
Back to top View Source