FORM  4.2
smart.c
Go to the documentation of this file.
1 
12 /* #[ License : */
13 /*
14  * Copyright (C) 1984-2017 J.A.M. Vermaseren
15  * When using this file you are requested to refer to the publication
16  * J.A.M.Vermaseren "New features of FORM" math-ph/0010025
17  * This is considered a matter of courtesy as the development was paid
18  * for by FOM the Dutch physics granting agency and we would like to
19  * be able to track its scientific use to convince FOM of its value
20  * for the community.
21  *
22  * This file is part of FORM.
23  *
24  * FORM is free software: you can redistribute it and/or modify it under the
25  * terms of the GNU General Public License as published by the Free Software
26  * Foundation, either version 3 of the License, or (at your option) any later
27  * version.
28  *
29  * FORM is distributed in the hope that it will be useful, but WITHOUT ANY
30  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
31  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
32  * details.
33  *
34  * You should have received a copy of the GNU General Public License along
35  * with FORM. If not, see <http://www.gnu.org/licenses/>.
36  */
37 /* #] License : */
38 /*
39  #[ Includes : function.c
40 */
41 
42 #include "form3.h"
43 
44 /*
45  #] Includes :
46  #[ StudyPattern :
47 
48  Argument is a complete lhs of an id-statement
49  Its last word is a zero (new convention(18-may-1997)) to indicate
50  that no extra information is following. We can add there information
51  about the pattern that will help during the actual pattern matching.
52  Currently the WorkPointer points to just after this lhs.
53 
54  Task of this routine: To study the functions, their symmetry properties
55  and their wildcards to determine in which order the functions can
56  be matched best. If the order should be different we can change it here.
57 
58  Problem encountered 22-dec-2008 (JV): we don't take noncommuting
59  functions into account.
60 */
61 
62 int StudyPattern(WORD *lhs)
63 {
64  GETIDENTITY
65  WORD *fullproto, *pat, *p, *p1, *p2, *pstop, *info, f, nn;
66  int numfun = 0, numsym = 0, allwilds = 0, i, j, k, nc;
67  FUN_INFO *finf, *fmin, *f1, *f2, funscratch;
68 
69  fullproto = lhs + IDHEAD;
70 /* if ( *lhs == TYPEIF ) fullproto--; */
71  pat = fullproto + fullproto[1];
72  info = pat + *pat;
73 
74  p = pat + 1;
75  while ( p < info ) {
76  if ( *p >= FUNCTION ) {
77  numfun++;
78  nn = *p - FUNCTION;
79  if ( nn >= WILDOFFSET ) nn -= WILDOFFSET;
80 /*
81  We check here for cases that are not allowed like ?a inside
82  symmetric functions or tensors.
83 */
84  if ( ( functions[nn].symmetric == SYMMETRIC ) ||
85  ( functions[nn].symmetric == ANTISYMMETRIC ) ) {
86  p2 = p+p[1]; p1 = p+FUNHEAD;
87  if ( functions[nn].spec ) {
88  while ( p1 < p2 ) {
89  if ( *p1 == FUNNYWILD ) {
90  MesPrint("&Argument field wildcards are not allowed inside (anti)symmetric functions or tensors");
91  return(1);
92  }
93  p1++;
94  }
95  }
96  else {
97  while ( p1 < p2 ) {
98  if ( *p1 == -ARGWILD ) {
99  MesPrint("&Argument field wildcards are not allowed inside (anti)symmetric functions or tensors");
100  return(1);
101  }
102  NEXTARG(p1);
103  }
104  }
105  }
106  }
107  p += p[1];
108  }
109  if ( numfun == 0 ) return(0);
110  if ( ( lhs[2] & SUBMASK ) == SUBALL ) {
111  p = pat + 1;
112  while ( p < info ) {
113  if ( *p == SYMBOL || *p == VECTOR || *p == DOTPRODUCT || *p == INDEX ) {
114  MesPrint("&id,all can have only functions and/or tensors in the lhs.");
115  return(1);
116  }
117  p += p[1];
118  }
119  }
120 /*
121  We need now some room for the information about the functions
122 */
123  if ( numfun > AN.numfuninfo ) {
124  if ( AN.FunInfo ) M_free(AN.FunInfo,"funinfo");
125  AN.numfuninfo = numfun + 10;
126  AN.FunInfo = (FUN_INFO *)Malloc1(AN.numfuninfo*sizeof(FUN_INFO),"funinfo");
127  }
128 /*
129  Now collect the information. First the locations.
130 */
131  p = pat + 1; i = 0;
132  while ( p < info ) {
133  if ( *p >= FUNCTION ) AN.FunInfo[i++].location = p;
134  p += p[1];
135  }
136  for ( i = 0, finf = AN.FunInfo; i < numfun; i++, finf++ ) {
137  p = finf->location;
138  pstop = p + p[1];
139  f = *p;
140  if ( f > FUNCTION+WILDOFFSET ) f -= WILDOFFSET;
141  finf->numargs = finf->numfunnies = finf->numwildcards = 0;
142  finf->symmet = functions[f-FUNCTION].symmetric;
143  finf->tensor = functions[f-FUNCTION].spec;
144  finf->commute = functions[f-FUNCTION].commute;
145  if ( finf->tensor >= TENSORFUNCTION ) {
146  p += FUNHEAD;
147  while ( p < pstop ) {
148  if ( *p == FUNNYWILD ) {
149  finf->numfunnies++; p+= 2; continue;
150  }
151  else if ( *p < 0 ) {
152  if ( *p >= AM.OffsetVector + WILDOFFSET && *p < MINSPEC ) {
153  finf->numwildcards++;
154  }
155  }
156  else {
157  if ( *p >= AM.OffsetIndex + WILDOFFSET &&
158  *p <= AM.OffsetIndex + 2*WILDOFFSET ) finf->numwildcards++;
159  }
160  finf->numargs++;
161  p++;
162  }
163  }
164  else {
165  p += FUNHEAD;
166  while ( p < pstop ) {
167  if ( *p > 0 ) { finf->numargs++; p += *p; continue; }
168  if ( *p <= -FUNCTION ) {
169  if ( *p <= -FUNCTION - WILDOFFSET ) finf->numwildcards++;
170  p++;
171  }
172  else if ( *p == -SYMBOL ) {
173  if ( p[1] >= 2*MAXPOWER ) finf->numwildcards++;
174  p += 2;
175  }
176  else if ( *p == -INDEX ) {
177  if ( p[1] >= AM.OffsetIndex + WILDOFFSET &&
178  p[1] <= AM.OffsetIndex + 2*WILDOFFSET ) finf->numwildcards++;
179  p += 2;
180  }
181  else if ( *p == -VECTOR || *p == -MINVECTOR ) {
182  if ( p[1] >= AM.OffsetVector + WILDOFFSET && p[1] < MINSPEC ) {
183  finf->numwildcards++;
184  }
185  p += 2;
186  }
187  else if ( *p == -ARGWILD ) {
188  finf->numfunnies++;
189  p += 2;
190  }
191  else { p += 2; }
192  finf->numargs++;
193  }
194  }
195  if ( finf->symmet ) {
196  numsym++;
197  allwilds += finf->numwildcards + finf->numfunnies;
198  }
199  }
200  if ( numsym == 0 ) return(0);
201  if ( allwilds == 0 ) return(0);
202 /*
203  We have the information in the array AN.FunInfo.
204  We sort things and then write the sorted pattern.
205  Of course we may not play with the order of the noncommuting functions.
206  Of course we have to become even smarter in the future and look during
207  the sorting which wildcards are asigned when.
208  But for now this should do.
209 */
210  for ( nc = numfun-1; nc >= 0; nc-- ) { if ( AN.FunInfo[nc].commute ) break; }
211 
212  finf = AN.FunInfo;
213  for ( i = nc+2; i < numfun; i++ ) {
214  fmin = finf; finf++;
215  if ( ( finf->symmet < fmin->symmet ) || (
216  ( finf->symmet == fmin->symmet ) &&
217  ( ( finf->numwildcards+finf->numfunnies < fmin->numwildcards+fmin->numfunnies )
218  || ( ( finf->numwildcards+finf->numfunnies == fmin->numwildcards+fmin->numfunnies )
219  && ( finf->numwildcards < fmin->numfunnies ) ) ) ) ) {
220  funscratch = AN.FunInfo[i];
221  AN.FunInfo[i] = AN.FunInfo[i-1];
222  AN.FunInfo[i-1] = funscratch;
223  for ( j = i-1; j > nc && j > 0; j-- ) {
224  f1 = AN.FunInfo+j;
225  f2 = f1-1;
226  if ( ( f1->symmet < f2->symmet ) || (
227  ( f1->symmet == f2->symmet ) &&
228  ( ( f1->numwildcards+f1->numfunnies < f2->numwildcards+f2->numfunnies )
229  || ( ( f1->numwildcards+f1->numfunnies == f2->numwildcards+f2->numfunnies )
230  && ( f1->numwildcards < f2->numfunnies ) ) ) ) ) {
231  funscratch = AN.FunInfo[j];
232  AN.FunInfo[j] = AN.FunInfo[j-1];
233  AN.FunInfo[j-1] = funscratch;
234  }
235  else break;
236  }
237  }
238  }
239 /*
240  Now we rewrite the pattern. First into the space after it and then we
241  copy it back. Be careful with the non-commutative functions. There the
242  worst one should decide.
243 */
244  p = pat + 1;
245  p2 = info;
246  for ( i = 0; i < numfun; i++ ) {
247  if ( i == nc ) {
248  for ( k = 0; k <= nc; k++ ) {
249  if ( AN.FunInfo[k].commute ) {
250  p1 = AN.FunInfo[k].location; j = p1[1];
251  NCOPY(p2,p1,j)
252  }
253  }
254  }
255  else if ( AN.FunInfo[i].commute == 0 ) {
256  p1 = AN.FunInfo[i].location; j = p1[1];
257  NCOPY(p2,p1,j)
258  }
259  }
260  p = pat + 1; p1 = info;
261  while ( p1 < p2 ) *p++ = *p1++;
262 /*
263  And now we place the relevant information in the info part
264 */
265  p2 = info+1;
266  for ( i = 0; i < numfun; i++ ) {
267  if ( i == nc ) {
268  for ( k = 0; k <= nc; k++ ) {
269  if ( AN.FunInfo[k].commute ) {
270  finf = AN.FunInfo + k;
271  *p2++ = finf->numargs;
272  *p2++ = finf->numwildcards;
273  *p2++ = finf->numfunnies;
274  *p2++ = finf->symmet;
275  }
276  }
277  }
278  else if ( AN.FunInfo[i].commute == 0 ) {
279  finf = AN.FunInfo + i;
280  *p2++ = finf->numargs;
281  *p2++ = finf->numwildcards;
282  *p2++ = finf->numfunnies;
283  *p2++ = finf->symmet;
284  }
285  }
286  *info = p2-info;
287  lhs[1] = p2-lhs;
288  return(0);
289 }
290 
291 /*
292  #] StudyPattern :
293  #[ MatchIsPossible :
294 
295  We come here when there are functions and there is nontrivial
296  symmetry related wildcarding.
297 */
298 
299 int MatchIsPossible(WORD *pattern, WORD *term)
300 {
301  GETIDENTITY
302  WORD *info = pattern + *pattern;
303  WORD *t, *tstop, *tt, *inf, *p;
304  int numfun = 0, inpat, i, j, numargs;
305  FUN_INFO *finf;
306 /*
307  We need a list of functions and their number of arguments
308 */
309  GETSTOP(term,tstop);
310  t = term + 1;
311  while ( t < tstop ) {
312  if ( *t >= FUNCTION ) numfun++;
313  t += t[1];
314  }
315  if ( numfun == 0 ) goto NotPossible;
316  if ( *info == SETSET ) info += info[1];
317  inpat = (*info-1)/4;
318  if ( inpat > numfun ) goto NotPossible;
319 /*
320  We need now some room for the information about the functions
321 */
322  if ( numfun > AN.numfuninfo ) {
323  if ( AN.FunInfo ) M_free(AN.FunInfo,"funinfo");
324  AN.numfuninfo = numfun + 10;
325  AN.FunInfo = (FUN_INFO *)Malloc1(AN.numfuninfo*sizeof(FUN_INFO),"funinfo");
326  }
327  t = term + 1; finf = AN.FunInfo;
328  while ( t < tstop ) {
329  if ( *t >= FUNCTION ) {
330  finf->location = t;
331  if ( functions[*t-FUNCTION].spec >= TENSORFUNCTION ) {
332  numargs = t[1]-FUNHEAD;
333  t += t[1];
334  }
335  else {
336  numargs = 0;
337  tt = t + t[1];
338  t += FUNHEAD;
339  while ( t < tt ) {
340  numargs++;
341  NEXTARG(t)
342  }
343  }
344  finf->numargs = numargs;
345  finf++;
346  }
347  else t += t[1];
348  }
349 /*
350  Now we first find a partner for each function in the pattern
351  with a fixed number of arguments
352 */
353  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
354  if ( inf[2] ) continue;
355  if ( *p >= (FUNCTION+WILDOFFSET) ) continue;
356  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
357  if ( *p == *(finf->location) && *inf == finf->numargs ) {
358  finf->numargs = -finf->numargs-1;
359  break;
360  }
361  }
362  if ( j >= numfun ) goto NotPossible;
363  }
364  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
365  if ( inf[2] ) continue;
366  if ( *p < (FUNCTION+WILDOFFSET) ) continue;
367  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
368  if ( *inf == finf->numargs ) {
369  finf->numargs = -finf->numargs-1;
370  break;
371  }
372  }
373  if ( j >= numfun ) goto NotPossible;
374  }
375  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
376  if ( inf[2] == 0 ) continue;
377  if ( *p >= (FUNCTION+WILDOFFSET) ) continue;
378  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
379  if ( *p == *(finf->location) && (*inf-inf[2]) <= finf->numargs ) {
380  finf->numargs = -finf->numargs-1;
381  break;
382  }
383  }
384  if ( j >= numfun ) goto NotPossible;
385  }
386  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
387  if ( inf[2] == 0 ) continue;
388  if ( *p < (FUNCTION+WILDOFFSET) ) continue;
389  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
390  if ( (*inf-inf[2]) <= finf->numargs ) {
391  finf->numargs = -finf->numargs-1;
392  break;
393  }
394  }
395  if ( j >= numfun ) goto NotPossible;
396  }
397 /*
398  Thus far we have determined that for each function in the pattern
399  there is a potential partner with enough arguments.
400  For now the rest is up to the real pattern matcher.
401 
402  To undo the disabling of the number of arguments we need this code
403  for ( i = 0, finf = AN.FunInfo; i < numfun; i++, finf++ ) {
404  if ( finf->numargs < 0 ) finf->numargs = -finf->numargs-1;
405  }
406 */
407  return(1);
408 NotPossible:
409 /*
410  PrintTerm(pattern,"p");
411  PrintTerm(term,"t");
412 */
413  return(0);
414 }
415 
416 /*
417  #] MatchIsPossible :
418 */